Функциональная декомпозиция - Functional decomposition

В математике функциональная декомпозиция это процесс разрешения функциональный отношения на его составные части таким образом, что исходная функция может быть восстановлена ​​(т. е. перекомпонована) из этих частей с помощью функциональная композиция.

Этот процесс разложения может быть предпринят, чтобы получить представление об идентичности составляющих компонентов, которые могут отражать отдельные представляющие интерес физические процессы. Также функциональная декомпозиция может привести к сжатому представлению глобальной функции, задача, которая выполнима только тогда, когда составляющие процессы обладают определенным уровнем модульность (т.е. независимость или невзаимодействие).

Взаимодействия^{[уточнить ]} между компонентами имеют решающее значение для функции коллекции. Все взаимодействия не могут быть наблюдаемый^{[уточнить ]}, но, возможно, выводится из повторяющихся восприятие^{[уточнить ]}, синтез, проверка и проверка сложного поведения.

Основное математическое определение

Пример слабо связанной структуры зависимостей. Направление причинного потока - вверх.

Для многомерной функции ${displaystyle y=f(x_{1},x_{2},dots ,x_{n})}$, функциональная декомпозиция обычно относится к процессу идентификации набора функций ${displaystyle {g_{1},g_{2},dots g_{m}}}$ такой, что

${displaystyle f(x_{1},x_{2},dots ,x_{n})=phi (g_{1}(x_{1},x_{2},dots ,x_{n}),g_{2}(x_{1},x_{2},dots ,x_{n}),dots g_{m}(x_{1},x_{2},dots ,x_{n}))}$

куда ${displaystyle phi }$ это какая-то другая функция.^{[требуется разъяснение ]} Таким образом, можно сказать, что функция ${displaystyle f}$ раскладывается на функции ${displaystyle {g_{1},g_{2},dots g_{m}}}$. Этот процесс по сути является иерархическим в том смысле, что мы можем (и часто делаем) стремиться к дальнейшей декомпозиции функций. ${displaystyle g_{i}}$ в набор составляющих функций ${displaystyle {h_{1},h_{2},dots h_{p}}}$ такой, что

${displaystyle g_{i}(x_{1},x_{2},dots ,x_{n})=gamma (h_{1}(x_{1},x_{2},dots ,x_{n}),h_{2}(x_{1},x_{2},dots ,x_{n}),dots h_{p}(x_{1},x_{2},dots ,x_{n}))}$

куда ${displaystyle gamma }$ это какая-то другая функция. Разложения такого рода интересны и важны по целому ряду причин. В общем, функциональная декомпозиция имеет смысл, когда существует определенная «разреженность» в структуре зависимостей; то есть, когда оказывается, что составляющие функции зависят приблизительно от непересекающиеся множества переменных. Так, например, если мы можем получить разложение ${displaystyle x_{1}=f(x_{2},x_{3},dots ,x_{6})}$ в иерархическую композицию функций ${displaystyle {g_{1},g_{2},g_{3}}}$ такой, что ${displaystyle x_{1}=g_{1}(x_{2})}$, ${displaystyle x_{2}=g_{2}(x_{3},x_{4},x_{5})}$, ${displaystyle x_{5}=g_{3}(x_{6})}$, как показано на рисунке справа, это, вероятно, будет считаться очень ценным разложением.

Пример: арифметика

Базовым примером функциональной декомпозиции является выражение четырех двоичных арифметических операций сложения, вычитания, умножения и деления в терминах двух двоичных операций сложения. ${displaystyle a+b}$ и умножение ${displaystyle a imes b,}$ и две унарные операции аддитивного обращения ${displaystyle -a}$ и мультипликативная инверсия ${displaystyle 1/a.}$ Затем вычитание может быть реализовано как композиция сложения и аддитивной инверсии, ${displaystyle a-b=a+(-b),}$ и деление может быть реализовано как композиция умножения и обратного умножения, ${displaystyle adiv b=a imes (1/b).}$ Это упрощает анализ вычитания и деления, а также упрощает аксиоматизацию этих операций в понятии поле, так как есть только две двоичные и две унарные операции, а не четыре двоичных операции.

Расширяя эти примитивные операции, существует обширная литература по теме полиномиальное разложение.

Пример: разложение непрерывных функций

Мотивация для разложения

Относительно Почему разложение ценное, причина двоякая. Во-первых, разложение функции на невзаимодействующие компоненты обычно позволяет более экономно представить функцию. Например, на наборе четвертичных (т. Е. 4-арных) переменных, представляющих полную функцию ${displaystyle x_{1}=f(x_{2},x_{3},dots ,x_{6})}$ требует хранения ${displaystyle 4^{5}=1024}$ values, значение функции для каждого элемента в Декартово произведение ${displaystyle {x_{2},x_{3},dots ,x_{6}}}$, т.е. каждая из 1024 возможных комбинаций для ${displaystyle {x_{2},x_{3},dots ,x_{6}}}$. Однако если разложение на ${displaystyle {g_{1},g_{2},g_{3}}}$ приведенное выше возможно, тогда ${displaystyle g_{1}=g_{1}(x_{2})}$ требует хранения 4 значений, ${displaystyle g_{2}=g_{2}(x_{3},x_{4},x_{5})}$ требует хранения ${displaystyle 4^{3}=64}$ ценности и ${displaystyle g_{3}=g_{3}(x_{6})}$ снова требует хранения всего 4 значений. Таким образом, в силу разложения нам нужно сохранить только ${displaystyle 4+64+4=72}$ значения, а не 1024 значения, значительная экономия.

Причинные влияния на движение по шоссе Вест-Сайд. Погода и движение по мосту GW отключения экрана другие влияния

Интуитивно это уменьшение размера представления достигается просто потому, что каждая переменная зависит только от подмножества других переменных. Таким образом, переменная ${displaystyle x_{1}}$ зависит только напрямую от переменной ${displaystyle x_{2}}$, а не в зависимости от весь набор переменных. Мы бы сказали, что переменная ${displaystyle x_{2}}$ экраны выключены Переменная ${displaystyle x_{1}}$ от остального мира. Практические примеры этого явления окружают нас, как обсуждается в «Философских соображениях» ниже, но давайте просто рассмотрим частный случай «движения в северном направлении на West Side Highway. "Допустим, эта переменная (${displaystyle {x_{1}}}$) принимает три возможных значения {"движется медленно", "движется очень медленно", "вообще не движется"}. Теперь допустим переменную ${displaystyle {x_{1}}}$ зависит от двух других переменных: "погода" со значениями {"солнце", "дождь", "снег"} и "GW Bridge трафик "со значениями {" 10 миль в час "," 5 миль в час "," 1 миль в час "}. Дело в том, что, хотя есть определенно много вторичных переменных, которые влияют на погодную переменную (например, система низкого давления над Канадой, хлопанье бабочки в Японии и т. д.) и переменной движения на мосту (например, авария на I-95, президентский кортеж и т. д.) все эти второстепенные переменные не имеют прямого отношения к движению по Вестсайдскому шоссе. Все, что нам нужно (гипотетически) для прогнозирования движения по West Side Highway - это погода и движение по мосту GW, потому что эти две переменные отключения экрана Движение по шоссе Вест-Сайд от всех других потенциальных воздействий. То есть действуют все остальные влияния через их.

Помимо чисто математических соображений, возможно, наибольшее значение функциональной декомпозиции состоит в том, чтобы проникнуть в суть структуры мира. Когда может быть достигнута функциональная декомпозиция, это обеспечивает онтологическую информацию о том, какие структуры действительно существуют в мире и как их можно предсказать и управлять ими. Например, на иллюстрации выше, если известно, что ${displaystyle {x_{1}}}$ напрямую зависит только от ${displaystyle {x_{2}}}$, это означает, что для целей прогнозирования ${displaystyle {x_{1}}}$, достаточно знать только ${displaystyle {x_{2}}}$. Более того, вмешательства с целью влияния ${displaystyle {x_{1}}}$ можно взять прямо на ${displaystyle {x_{2}}}$, и ничего дополнительного нельзя получить, вмешиваясь в переменные ${displaystyle {x_{3},x_{4},x_{5}}}$, поскольку они действуют только через ${displaystyle {x_{2}}}$ в любом слючае.

Философские соображения

Философские предшественники и разветвления функциональной декомпозиции довольно обширны, поскольку функциональная декомпозиция в том или ином виде лежит в основе всей современной науки. Здесь мы рассмотрим лишь некоторые из этих философских соображений.

Редукционистская традиция

Одно из основных различий, которое часто проводится между Восточная философия и Западная философия в том, что восточные философы были склонны поддерживать идеи, благоприятствующие холизм в то время как западные мыслители были склонны поддерживать идеи, благоприятствующие редукционизм. Это различие между Востоком и Западом похоже на другие философские различия (например, реализм против. антиреализм ). Некоторые примеры восточного холистического духа:

• «Открой рот, увеличь свою активность, начни различать вещи, и ты будешь вечно трудиться без надежды». - The Дао Дэ Цзин из Лао-цзы (Брайан Браун Уокер, переводчик)
• «Для [людей] нелегко понять смысл того факта, что все, включая нас самих, зависит от всего остального и не имеет постоянного самосуществования». — Маджхима Никая (Энн Банкрофт, переводчик)
• «Имя навязывается тому, что считается вещью или состоянием, и это отделяет его от других вещей и других состояний. Но когда вы преследуете то, что скрывается за именем, вы обнаруживаете все большую и большую утонченность, не имеющую разделения ... . " — Висуддхи Магга (Энн Банкрофт, переводчик)

Западная традиция, от ее истоков среди Греческие философы, предпочел позицию, в которой правильное определение различий, разделений и контрастов считалось вершиной понимания. в Аристотелевский /Порфирийский мировоззрение, чтобы иметь возможность различать (посредством строгих доказательств), какие качества вещи представляют ее сущность против. свойство против. авария против. определение, и в силу этого формального описания выделить эту сущность на ее надлежащее место в таксономии природы - это означало достичь высшей мудрости.

Характеристики иерархии и модульности

В естественных или искусственных системах, которые требуют, чтобы компоненты были интегрированы каким-либо образом, но где количество компонентов превышает то, что может быть разумно полностью взаимосвязано (из-за квадратного роста числа соединений (= n более двух или = n * (n - 1) / 2)), часто обнаруживается, что в решении необходимо использовать некоторую степень иерархичности. Общие преимущества разреженных иерархических систем перед системами с плотной связью - и количественные оценки этих преимуществ - представлены Резникофф (1989). Проще говоря, иерархия - это «совокупность элементов, которые законно объединяются в сложные целые, свойства которых зависят от свойств их составных частей», и в которой новизна «в основном комбинаторна, итеративна и прозрачна» (Макгинн 1994 ).

Важное понятие, которое всегда возникает в связи с иерархиями, - это модульность, которая эффективно подразумевается редкостью соединений в иерархических топологиях. В физических системах модуль обычно представляет собой набор взаимодействующих компонентов, которые связаны с внешним миром через очень ограниченный интерфейс, таким образом скрывая большинство аспектов своей внутренней структуры. В результате модификации, которые вносятся во внутреннюю часть модуля (например, для повышения эффективности), не обязательно создают эффект пульсации в остальной части системы (Фодор 1983 ). Эта функция делает эффективное использование модульности центральным элементом всей хорошей разработки программного и аппаратного обеспечения.

Неизбежность иерархии и модульности

Существует множество убедительных аргументов относительно преобладания и необходимости иерархии / модульности в природе (Кестлер 1973 ). Саймон (1996) указывает на то, что среди развивающихся систем только те, которым удастся получить и затем повторно использовать стабильные подузлы (модули), вероятно, смогут достаточно быстро провести поиск в ландшафте пригодности; таким образом, Саймон утверждает, что «среди возможных сложных форм иерархии - это те, у которых есть время для развития». Такой образ мышления привел к еще более сильному утверждению, что, хотя «мы не знаем, какие формы жизни развивались на других планетах во Вселенной ... мы можем с уверенностью предположить, что« где бы ни была жизнь, она должна быть иерархически организована '"(Кестлер 1967 ). Это было бы удачным положением дел, поскольку существование простых и изолируемых подсистем считается предпосылкой для успешной науки (Фодор 1983 ). В любом случае опыт определенно указывает на то, что большая часть мира обладает иерархической структурой.

Было высказано предположение, что само восприятие представляет собой процесс иерархической декомпозиции (Лейтон 1992 ), и те явления, которые по сути не являются иерархическими по своей природе, могут даже не быть «теоретически понятными» человеческому разуму (Макгинн 1994,Саймон 1996 ). По словам Саймона,

Таким образом, тот факт, что многие сложные системы имеют почти разлагаемую иерархическую структуру, является важным фактором, помогающим нам понимать, описывать и даже «видеть» такие системы и их части. Или, возможно, суждение следует поставить наоборот. Если в мире есть важные системы, которые сложны, но не иерархичны, они могут в значительной степени ускользнуть от нашего наблюдения и понимания. Анализ их поведения потребует таких подробных знаний и расчетов взаимодействий их элементарных частей, что это будет за пределами наших возможностей памяти или вычислений.

Приложения

Практическое применение функциональной декомпозиции можно найти в Байесовские сети, структурное моделирование уравнение, линейные системы, и системы баз данных.

Представление знаний

Процессы, связанные с функциональной декомпозицией, распространены во всех областях представление знаний и машинное обучение. Техники индукции иерархической модели, такие как Минимизация логической схемы, деревья решений, грамматический вывод, иерархическая кластеризация, и разложение квадродерева все примеры разложения функций. Обзор других приложений и декомпозицию функций можно найти в Zupan et al. (1997), где также представлены методы, основанные на теория информации и теория графов.

Много статистические выводы методы можно рассматривать как реализацию процесса декомпозиции функций в присутствии шума; то есть, где ожидается, что функциональные зависимости будут выполняться примерно. Среди таких моделей есть модели смеси и недавно популярные методы, называемые "причинным разложением" или Байесовские сети.

Теория баз данных

Видеть нормализация базы данных.

Машинное обучение

В практических научных приложениях практически никогда не удается достичь идеальной функциональной декомпозиции из-за невероятной сложности изучаемых систем. Эта сложность проявляется в наличии «шума», который является всего лишь обозначением всех нежелательных и неотслеживаемых влияний на наши наблюдения.

Однако, хотя совершенная функциональная декомпозиция обычно невозможна, дух живет в большом количестве статистических методов, предназначенных для работы с зашумленными системами. Когда естественная или искусственная система по своей сути иерархична, совместное распределение по системным переменным должно свидетельствовать об этой иерархической структуре. Задача наблюдателя, который стремится понять систему, состоит в том, чтобы вывести иерархическую структуру из наблюдений за этими переменными. Это идея иерархической декомпозиции совместного распределения, попытка восстановить что-то от внутренней иерархической структуры, которая породила это совместное распределение.

В качестве примера, Байесовская сеть методы пытаются разложить совместное распределение вдоль причинных линий разлома, таким образом «разрезая природу по швам». Существенная мотивация этих методов снова заключается в том, что в большинстве систем (естественных или искусственных) относительно небольшое количество компонентов / событий взаимодействуют друг с другом напрямую на равных основаниях (Саймон 1963 ). Скорее, можно наблюдать очаги плотных связей (прямых взаимодействий) между небольшими подмножествами компонентов, но только слабые связи между этими плотно связанными подмножествами. Таким образом, в физических системах существует понятие «причинной близости», при котором переменные естественным образом собираются в небольшие кластеры. Идентификация этих кластеров и их использование для представления соединения обеспечивает основу для высокой эффективности хранения (относительно полного совместного распределения), а также для эффективных алгоритмов вывода.

Архитектура программного обеспечения

Основная статья: Декомпозиция (информатика)

Функциональная декомпозиция - это метод проектирования, предназначенный для создания архитектурного описания компьютерной программы, не являющегося реализацией. Вместо того, чтобы гадать Объекты и добавлять к ним методы (ООП ), с каждым объектом, намеревающимся захватить некоторую службу программы, архитектор программного обеспечения сначала устанавливает серию функций и типов, которые решают основную проблему обработки компьютерной программы, разлагает каждый объект, чтобы выявить общие функции и типы, и, наконец, выводит модули из эта деятельность.

Например, дизайн редактора Emacs изначально можно рассматривать с точки зрения функций:

${displaystyle e,equiv { ext{state of the Emacs editor and running operating system}}}$
${displaystyle e',equiv e{ ext{ with some component/part of its state changed}}}$

${displaystyle f:(e,lisp,,expression)ightarrow e'}$

И возможный разложение функций из ж:

${displaystyle fromExpr:lisp,,expressionightarrow {egin{cases}object,&{ ext{if success}}error,&{ ext{if failure}}end{cases}}}$

${displaystyle evaluate:(object,e)ightarrow e'}$

${displaystyle print:(error,e)ightarrow e'}$

Это приводит к вероятному модулю, службе или объекту интерпретатора (содержащему функцию fromExpr). Разложение функций, возможно, дает представление о возможности повторного использования, например, если в ходе анализа две функции производят один и тот же тип, вполне вероятно, что общая функция /сквозная озабоченность находится в обоих. Напротив, в ООП, это обычная практика - предполагать модули перед рассмотрением такого разложения. Это, возможно, приводит к дорогостоящим рефакторинг потом. FD в некоторой степени снижает этот риск. Кроме того, возможно, то, что отличает FD от других методов проектирования, - это то, что он обеспечивает краткую высокоуровневую среду архитектурного дискурса, которая является сквозной, выявляя недостатки в восходящем направлении. требования и заранее выгодно раскрыть больше дизайнерских решений. И, наконец, известно, что FD уделяет приоритетное внимание развитию. Возможно, если FD верен, наиболее часто используемые и определяемые с точки зрения затрат части программы определяются намного раньше в цикле разработки.

Обработка сигналов

Функциональная декомпозиция используется при анализе многих обработка сигналов системы, такие как Системы LTI. Входной сигнал в систему LTI можно выразить как функцию, ${displaystyle f(t)}$. потом ${displaystyle f(t)}$ могут быть разложены на линейную комбинацию других функций, называемых компонентными сигналами:

${displaystyle f(t)=a_{1}cdot g_{1}(t)+a_{2}cdot g_{2}(t)+a_{3}cdot g_{3}(t)+dots +a_{n}cdot g_{n}(t)}$

Здесь, ${displaystyle {g_{1}(t),g_{2}(t),g_{3}(t),dots ,g_{n}(t)}}$ являются составляющими сигналами. Обратите внимание, что ${displaystyle {a_{1},a_{2},a_{3},dots ,a_{n}}}$ являются константами. Это разложение помогает в анализе, потому что теперь выход системы может быть выражен в терминах компонентов входа. Если мы позволим ${displaystyle T{}}$ представляют собой влияние системы, тогда выходной сигнал ${displaystyle T{f(t)}}$, который можно выразить как:

${displaystyle T{f(t)}=T{a_{1}cdot g_{1}(t)+a_{2}cdot g_{2}(t)+a_{3}cdot g_{3}(t)+dots +a_{n}cdot g_{n}(t)}}$

${displaystyle =a_{1}cdot T{g_{1}(t)}+a_{2}cdot T{g_{2}(t)}+a_{3}cdot T{g_{3}(t)}+dots +a_{n}cdot T{g_{n}(t)}}$

Другими словами, можно рассматривать систему как действующую отдельно на каждый из компонентов входного сигнала. Обычно используемые примеры этого типа разложения: Ряд Фурье и преобразование Фурье.

Системная инженерия

Функциональная декомпозиция в системная инженерия относится к процессу определения системы в функциональных терминах, затем к определению функций нижнего уровня и установлению взаимосвязей из этих функций системы более высокого уровня.^[1] Основная идея состоит в том, чтобы попытаться разделить систему таким образом, чтобы каждый блок блок-схема могут быть описаны без «и» или «или» в описании.

Это упражнение заставляет каждую часть системы иметь чистый функция. Когда система спроектирована как чистые функции, их можно использовать повторно или заменить. Обычным побочным эффектом является то, что интерфейсы между блоками становятся простыми и универсальными. Поскольку интерфейсы обычно становятся простыми, проще заменить чистую функцию связанной, аналогичной функцией.

Например, скажем, что нужно сделать стерео система. Функционально это можно разложить на компьютерные колонки, усилитель мощности, а магнитофон и передняя панель. Позже, когда другой модели потребуется аудио CD, вероятно, он может соответствовать тем же интерфейсам.

Смотрите также

• Байесовские сети
• Каррирование
• Нормализация базы данных
• Состав функций
• Индуктивный вывод
• Представление знаний

Примечания

1. Основы системной инженерии., Defense Acquisition University Press, Fort Belvoir, VA, январь 2001 г., стр. 45

Рекомендации

• Фодор, Джерри (1983), Модульность разума, Кембридж, Массачусетс: MIT Press

• Кестлер, Артур (1967), Призрак в машине, Нью-Йорк: Macmillan

• Кестлер, Атур (1973), «Дерево и свеча», у Грея, Уильяма; Риццо, Николас Д. (ред.), Единство через многообразие: Festschrift для Людвига фон Берталанфи, Нью-Йорк: Гордон и Бреч, стр. 287–314.

• Лейтон, Майкл (1992), Симметрия, Причинность, Разум, Кембридж, Массачусетс: MIT Press

• Макгинн, Колин (1994), "Проблема философии", Философские исследования, 76 (2–3): 133–156, Дои:10.1007 / BF00989821

• Ресникофф, Говард Л. (1989), Иллюзия реальности, Нью-Йорк: Springer

• Саймон, Герберт А. (1963), «Причинная упорядоченность и идентифицируемость», у Андо, Альберт; Фишер, Франклин М .; Саймон, Герберт А. (ред.), Очерки структуры моделей социальных наук, Кембридж, Массачусетс: MIT Press, стр. 5–31..
• Саймон, Герберт А. (1973), «Организация сложных систем», в Патти, Ховард Х. (ред.), Теория иерархии: вызов сложных систем, Нью-Йорк: Джордж Бразиллер, стр. 3–27..
• Саймон, Герберт А. (1996), "Архитектура сложности: иерархические системы", Науки об искусственном, Кембридж, Массачусетс: MIT Press, стр. 183–216..
• Тонг, Фред М. (1969), «Иерархические аспекты компьютерных языков», в Уайте, Закон Ланселота; Уилсон, Альберт Дж .; Уилсон, Донна (ред.), Иерархические структуры, Нью-Йорк: American Elsevier, стр. 233–251..
• Жупан, Блаж; Боханец, Марко; Братко, Иван; Демшар, Янез (1997), «Машинное обучение путем декомпозиции функций», Proc. 14-я Международная конференция по машинному обучению, Морган Кауфманн, стр. 421–429.