ФЭНДОМ



© Сергей Яковлев, 2006

Использование этой информации в коммерческих целях запрещенно. Но Вы можете копировать и перерабатывать данную статью в научных и образовательных целях, с последующим предоставлением результата на тех же правах. Для подробной информации см. Авторское право.



Линейность и инвариантность в искусственных нейронных сетях Править

Аннотация. В статье комментируются различные отдельные выводы, сделанные в работе Минского и Пейперта “Перцептроны”. Критически рассматривается обзор нейронных сетей, сделанный в работе Вассермана “Нейрокомпьютерная техника: теория и практика”, в той ее части, которая касается перцептрона. Показано, что выводы Вассермана сильно упрощены по сравнению с выводами Минского. Комментарии к работе Минского позволяют более точно понять некоторые аспекты математического аппарата Минского. Наибольшее внимание уделено тому, какую архитектуру имеет перцептрон, т.к. это важно для последующих выводов о его возможностях. Показано, что именно проблема инвариантности стоит перед перцептроном, а не проблема линейности, как утверждал Вассерман. Кроме того, утверждается, что проблема инвариантности свойственна не только перцептронам, а любым современным искусственным нейронным сетям. Таким образом, проблема распознавания инвариантных входных данных является основной теоретической проблемой всех искусственных нейронных сетей.

1. Введение Править

В данное время появилось устойчивое мнение, что архитектура перцептрона – это полносвязная однослойная нейронная сеть. Наиболее ранний источник такого мнения автор нашел в работе [3]. Это послужило основой для того, чтобы рассматривать перцептрон как сеть с серьезным недостатком, которая не в состоянии распознать нелинейные входные данные.

Такое мнение полностью противоречит работам Розенблатта [1] и Минского [2]. В отношении работы Минского могут возникать недоразумения, т.к. именно его работу приводят в качестве доказательства устоявшегося мнения о линейности перцептрона.

Поэтому первым делом мы постараемся убрать неточности, которые сложились сейчас вокруг науки о перцептроне, а уже после постараемся понять, о каких проблемах говорил Минский. Анализ этих проблем позволит наметить и переопределить задачи, которые способен решать перцептрон, и выделить тот круг задач, где перцептрон находится в затруднительном положении.

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

2. Особенности взглядов на перцептрон Править

Чтобы разобраться, какая все-таки архитектура у перцептрона, ниже будут рассмотрены мнения Розенблатта – создателя перцептрона, Минского – главного оппонента Розенблатта и Вассермана – как пример современного взгляда на перцептрон (к сожалению, из-за ограничений на размер, мы не можем привести ряд цитат, и вынуждены отослать читателя к первоисточникам [1], [2], [3]).

Первое, на что обратим внимание читателя – это схожесть рисунков в работе Розенблатта под номером “Фиг. 5. Типичная структурная схема элементарного перцептрона” и рисунка в работе Минского под номером “Рис. 0.1.”, который Минский по тексту комментирует так: “Простейшее представление о параллельном вычислении дает схема на рис.0.1.”. Так как это будет важно впоследствии, обоснуем эту схожесть подробней:

1. Входные данные

У Розенблатта на рисунке: “Сетчатка из S-элементов”, и по тексту комментарий “все сенсорные элементы расположены в точках двумерного поля, или “сетчатки”, а роль входных стимулов играют различные распределения освещенности на сетчатке”.

У Минского на рисунке: “R” и “X”, и по тексту комментарий: “Пусть R – обычная двумерная эвклидова плоскость, X – геометрическая фигура, нарисованная на R. Например, X может быть ... черно-белым наброском лица.”.

2. Выходные данные

У Розенблатта на рисунке: “Выходной сигнал (+1 или -1)”.

У Минского на рисунке: “ ”, а по тексту комментарий “Пусть – функция (от фигур X на R), принимающая только два значения. Обычно их считают равными нулю и единице”. Разницу в значениях –1 (у Розенблатта) и 0 (у Минского) можно считать непринципиальной.

Таким образом, определения входных и выходных данных можно считать эквивалентными.

3. Промежуточные вычисления

У Розенблатта на рисунке: “А - элементы“, для которых он дает “Определение 9”.

У Минского на рисунке: “ ”, и по тексту: “Рисунок показывает, как можно вычислить функцию в два этапа: сначала вычислить функции независимо одну от другой ...”.

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

4. Связи между входными данными и промежуточными вычислениями

У Розенблатта этому посвящен весь раздел 6.2. Основное, что следует выделить: “рассмотрены модели трех типов, которые различаются характером связей S- и A- элементов ... распределения входных сигналов А – элементов выражаются, соответственно, биномиальными, пуассоновскими и нормальным (гауссовым) законами”, следующие, что важно отметить: “... к каждому А-элементу подходит фиксированное количество связей от “сетчатки”. Эти связи состоят из x “возбуждающих” и y “тормозящих”. Каждая из возбуждающих связей имеет вес +1, а каждая тормозящая вес –1 ...”. И еще: “... Связи от S-элементов к А-элементам имеют фиксированные веса”.

У Минского в работе рассмотрены тоже различные вариации этих связей. Он выделяет:

  1. Перцептроны, ограниченные по диаметру (этому виду соответствует позднее изобретенный ... когнитрон [] );
  2. Перцептроны ограниченного порядка (вариант перцептрона, если бы связи выбирались не случайно, а фиксировано. Например, сейчас известен такой пример – под названием угловая классификация [Kak], относящийся к т.н. фильтрам);
  3. Перцептроны Гамбы (в современной терминологии класс полносвязных нейронный сетей (если еще точнее - то полносвязные фильтры));
  4. Ограниченные перцептроны (математическая абстракция с бесконечным числом функций ).

Наиболее интересными для нас являются:

“Случайные перцептроны. Именно эта модель наиболее подробно изучалась группой Розенблатта; предикаты представляют собой случайно выбранные булевы функции. Иначе говоря, случайные перцептроны являются перцептронами ограниченного порядка, а множество порождается случайным процессом с определенной функцией распределения.”

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

  1. Не является полносвязным, т.е. связи всех S-элементов со всеми А-элементами являются сугубо исключительным случаем, и если и рассматриваются, то только под названием “Перцептроны Гамбы” или еще как-то это специально оговаривается;
  2. Наличие “возбуждающих” и “тормозящих” связей у Розенблатта сведено практически к тому, что предикаты (А-элементы) представляют собой случайно выбранные булевы функции.
  3. Но вот сказать, что случайные перцептроны, являются перцептронами ограниченного порядка довольно сложно, т.к. в таком случае они свелись бы к понятию фильтра.

5. Решающий элемент

У Розенблатта на рисунке обозначен буквой “R”, и дано определение: “Определение 11. Простым R-элементом ...”.

У Минского на рисунке обозначен буквой “ ”, и даны следующие комментарии в тексте: “... объединить результаты при помощи функции от n переменных и получить значение . Чтобы такое определение имело смысл (или, точнее, было эффективным), необходимо наложить некоторые ограничения на функцию и множество функций Если не ввести ограничений, не получится теории ...”. И еще: “Этап 2. Алгоритм решения , который определяет , объединяя результаты вычислений, проведенных на этапе 1.”

Здесь мы видим, что данные определения так же как и для промежуточных вычислений, по сути сходны, с той разницей, что Розенблатт определяет (в терминах Минского “налагает ограничения”) эту функцию, а Минский, рассуждает более абстрактно, т.к. описывает принципиальную схему параллельных вычислений.

6. Связи между промежуточными вычислениями и решающим элементом

У Розенблатта: “веса связей от А-элементов к R-элементу переменны и зависят от ранее применявшихся подкреплений. ... В элементарном перцептроне, где единственными переменными связями являются связи от А-элементов к R-элементу, введем для веса связи от элемента к элементу R сокращенное обозначение ”. И еще: “имеют порог , равный нулю для R-элемента”.

У Минского: “Число называется порогом, а числа - коэффициентами, или весами. Обычно пишут сокращенно: тогда и только тогда, когда ”.

Таким образом, понимание этих связей у Розенблатта и у Минского эквивалентны. Теперь, проведя детальный анализ рисунков из работ Розенблатта и Минского, подведем некоторые итоги:

  1. По сути, понимание перцептрона Минским соответствует описанию перцептрона Розенблаттом;
  2. Но Минский вначале рассуждает более общо, без уточнений конкретного вида ряда функций, в отличие от Розенблатта;
  3. Более общие рассуждения Минского позволяют сделать важный вывод: Минский один из первых показывает принципиальную схему всех параллельных вычислений.
  4. Перцептрон Розенблатта полностью укладывается в схему параллельных вычислений, данную Минским. Таким образом, перцептрон просто является частным случаем любых параллельных вычислений. И как будет видно из дальнейшего, Минский это косвенно подтверждает.

Итак, почему же можно говорить лишь о косвенном подтверждении Минским того, что архитектура перцептрона является частным случаем любых параллельных вычислений. Это происходит оттого, что ряд фраз в работе Минского можно понимать двусмысленно. Так, например, переходя к уточнению понятия перцептрон, он пишет: “Перейдем теперь к рассмотрению частного случая этапа 2 – “взвешенного голосования”, или “линейной комбинации” предикатов этапа 1. Это так называемая схема перцептрона, и сейчас мы дадим окончательное определение.”

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

  1. Перцептрон является лишь частным случаем этапа 2 “взвешенного голосования” в схеме параллельных вычислений;
  2. Перцептроном также можно назвать “линейную комбинацию” предикатов этапа 1 в схеме параллельных вычислений.

Такая интерпретация появляется из-за того, что между “взвешенным голосованием” и “линейной комбинацией” стоит союз “или”. И далее утверждается, что одно из этого есть перцептронная схема. Но похоже, что для Минского перцептронная схема и сам перцептрон – разные понятия.

Далее мы покажем, что такая интерпретация в принципе не соответствует действительности. И, кроме того, позже будет видно, что именно эту интерпретацию положил в основу своего обзора Вассерман.

Предложим более точную, на авторский взгляд, интерпретацию этого утверждения:

  1. Минского в дальнейшем будет интересовать по отдельности “Этап 2” без рассмотрения “Этапа 1”, и наоборот;
  2. Рассматривая перцептрон, будет рассмотрен и частный случай схемы параллельных вычислений, делящийся на “Этап 1” и “Этап 2”.

Теперь приведем доводы в пользу авторской интерпретации. Перед этим еще раз напомним, что Минский под этапом 1 понимает нахождение функций , т.е. процесс взаимодействия:

“Входные данные” → “Связи” → “Промежуточные вычисления”.

Под этапом 2 Минский понимает: “Алгоритм решения , который определяет , объединяя результаты вычислений, проведенных на этапе 1.”, то есть процесс взаимодействия:

“Промежуточные вычисления”→ “Связи”→ “Решающий элемент” → “Выходные данные”.

Было бы, по меньшей мере, странно говорить о перцептроне, как частном случае, который начинает свою работу с промежуточных данных. И наконец, явное определение Розенблатта является противоречащим такой интерпретации.

Теперь покажем, что сам Минский не мог так интерпретировать перцептрон. Это видно из раздела “0.8. Перцептроны”: 1. На рис. 0.2., который не подписан, содержится некая схема, которую можно принять за архитектуру перцептрона. Но это было бы неверно, т.к. на самом деле изображены лишь структурные элементы этапа 2, а именно: “Промежуточные вычисления”→ “Связи”→ “Сумматор” → “Порог” → “Выходные данные”. Такой рисунок подтверждает мнение (п.1. в авторской интерпретации), что Минского интересовал лишь этап 2, детальный анализ которого он и приводит в своей работе. 2. Первое, что делает Минский, описывая перцептрон – это: 1. Конкретизирует “Решающий элемент”, которому соответствует “Сумматор” + “Порог”. И это находится в полном соответствии с элементом R, введенным Розенблаттом и определенным у него в “Определении 11.”; 2. Дает понятие того, что представляют собой связи между промежуточными вычислениями и решающим элементом, а именно вводит понятие весовых коэффициентов. И тоже в полном соответствии с Розенблаттом, что мы уже отмечали ранее; 3. Функции , остаются у Минского без точного определения, в отличие от Розенблатта. Единственное, что говорит о них Минский, - что они являются предикатами. Такая конкретизация понятий на основании общей схемы параллельных вычислений позволяет говорить, что Минский понимает под перцептроном частный случай параллельных вычислений (п.2. в авторской интерпретации). 3. И наконец, Минский дает определение перцептрона: “Перцептроном называется устройство, способное вычислять все предикаты, линейные относительно некоторого заданного множества частных предикатов. Иными словами, множество предикатов задано, а веса и порог выбираются свободно.”. Из этого становится понятным, почему Минского интересовал в основном этап 2. Это происходит оттого, что он считает: “множество предикатов задано ”. Таким образом, это определение перцептрона дается в явном предположении того, что “промежуточные вычисления” сделаны и результат получен.

Такое упрощение для анализа действительно полезно и возможно, т.к. связи между входными элементами (S-элементами по Розенблатту) и промежуточными вычислениями (А-элементы) Розенблатт постулирует фиксированными: “Связи от S-элементов к А-элементам имеют фиксированные веса”. Фиксированные связи означают, что для каждого стимула можно высчитать и сохранить результаты -функции. И далее, если учесть, что каждый А-элемент образно представляет собой некое определение того, является или нет набор некоторых точек из изображения неким понятием, то становится понятным, почему это понятие можно считать частным предикатом ограниченного порядка или диаметра (см. соответствующие определения перцептронов в работе Минского).

И далее, становится понятным, почему Минский говорит о перцептроне как устройстве, вычисляющем все предикаты, линейные относительно множества частных предикатов. Только надо иметь в виду, что под всеми вычисляемыми предикатами имеется в виду принадлежность того или другого стимула определенному классу. В данном случае могут быть только два класса. Поэтому точнее нужно было бы говорить, что перцептрон осуществляет дихотомию всех стимулов, на основании частных предикатов.

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

Итак, приведенные здесь комментарии приводят нас к следующим важным выводам: 1. Несмотря на некоторые нюансы интерпретации работы Розенблатта Минским, в целом они оба понимают под перцептроном одно и то же, но рассматривают его с разных углов зрения; 2. Неосторожно брошенные фразы в работе Минского могут вызвать неправильную интерпретацию в сложных местах теории последующими исследователями. В частности, далее мы рассмотрим интерпретацию перцептрона Вассерманом в его обзоре нейронных сетей [3].

Ссылаясь на работы Минского, Вассерман наверняка исходил из иной, нежели авторская, интерпретации архитектуры перцептрона. Вследствие этого: 1. Вассерман по сути вводит новое понятие однослойный перцептрон (это видно из рис. 2.2. и комментариев по тексту в его работе). Надо отметить, что как в оригинале у Розенблатта, так и у Минского рассматривается только трехслойный перцептрон, т.к. другие перцептроны не имеют смысла в параллельных вычислениях; 2. Это происходит из-за того, что Вассерман упрощает понятие частного предиката Минского просто до входных данных; 3. Как следствие, Вассерман описывает лишь частный случай этапа 2 параллельных вычислений; 4. Из-за этого Вассерман в дальнейшем подводит по сути свое упрощенное понятие линейности под более сложное, и если можно так выразиться, более тяжелое из-за многостороннего взгляда понятие линейности у Минского.

3. Линейность и инвариантность перцептрона Править

Вассерман пишет: “Один из самых пессимистических результатов Минского показывает, что однослойный перцептрон не может воспроизвести такую простую функцию, как “исключающее или””.

Тут важно понять, что если бы здесь дело было только в этом, то в такой интерпретации Розенблатт недостатков не видел, а Минскому не нужно было ничего показывать, т.к. это было само собой разумеющимся.

Так, уже в определении перцептрона Минский пишет: “Перцептроном называется устройство, способное вычислять все предикаты, линейные относительно некоторого заданного множества частных предикатов”.

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

Таким образом, в своем обзоре Вассерман не дает понимания того, в чем видел ограниченность применения перцептрона Минский, и о какой линейности или чем-то другом шла речь. Комментируя далее работу Минского, мы постараемся прояснить, о каких ограничениях перцептрона идет речь.

Итак, на самом деле, следует говорить не о линейности, а об инвариантности входных данных. Только так можно понять те ограничения применения перцептрона, которые следуют из анализа Минского. Хотя сам Минский с этим, возможно, и не согласился бы, так как пишет: “Перцептрон работает безупречно только при том условии, что множество исходных данных линейно разделимо”.

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

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

3.1. На пути создания математического аппарата для анализа перцептронов Править

В самом деле, о задаче, близкой к задаче “исключающего или”, и понятии линейности Минский упоминает в разделе “1.2. Функции, линейные относительно класса предикатов”. Так, в конце этого раздела как комментарий к рисунку он пишет:

“Для двухточечного пространства класс функций , линейных относительно одноточечных предикатов включает 14 из 16 возможных булевых функций. Для большого числа точек доля функций, линейных относительно одноточечных предикатов, очень быстро снижается”.

Заметим, что Минский здесь пишет о т.н. “одноточечных предикатах”, а из общего контекста работы можно понять, что речь идет о частных предикатах в общей схеме параллельных вычислений, частным случаем которых является перцептрон. Изобразим такой вырожденный перецептрон (рис.1.).


Рис. 1. Вырожденный перецептрон

Действительно, такой вырожденный перцептрон можно свести к однослойной нейронной сети, как это делает Вассерман. Но лишь в том случае, если считать, что связи между элементами S и A равны +1, т.е. сигнал просто передается без изменений. В данном случае, хоть это и не влияет на выводы Минского, эти связи еще могут быть равны -1. Когда же утверждается быстрое снижение возможных функций, линейных относительно одноточечных предикатов, Минский говорит лишь об увеличении числа точек в пространстве. Но никоим образом не рассматривает при этом увеличение числа связей между S и A элементами (т.е. предикаты остаются одноточечными), а снова говорит об одноточечных предикатах. Для перцептрона же естественным было бы увеличение числа связей между S и A элементами, что сразу снимает вопрос о такого рода линейности.

Только далее Минский начинает это анализировать, правда довольно особенным образом, а Вассерман, сведя перцептрон к однослойной сети, этой возможности не видит.

Чтобы формально разобраться в дальнейшем анализе Минского, нам нужно рассмотреть ряд введенных им понятий. Эти понятия нужны Минскому, т.к. он признает:

“Предикаты, носители которых невелики, чересчур локальны, а потому и не очень интересны сами по себе. Нас главным образом занимают предикаты, носителями которых служит все пространство R, но которые можно представить в виде линейных пороговых комбинаций предикатов с малыми носителями”.

Если учесть, что под величиной носителя Минский, по сути, понимает число связей между S и A элементами (в терминологии Розенблатта), то понятно, что говоря, что “предикаты, носители которых невелики, чересчур локальны, а потому и не очень интересны” он говорит, в частности, и о предыдущем примере с одноточечными предикатами. А не интересны т.к. они еще далеки от понятия перцептрона, в отличие от “предикатов, носителями которых служит все пространство R, но которые можно представить в виде линейных пороговых комбинаций предикатов с малыми носителями ”. Строя свой математический аппарат для анализа перцептрона, Минский вводит два важных понятия: порядок и маска, к рассмотрению которых мы и переходим.

3.2. Понятие порядка Править

Минский определяет понятие порядка, так:

“В общем случае порядок предиката есть наименьшее число , для которого можно найти множество предикатов, удовлетворяющих условиям:

для всех из , .

Следует отметить, что порядок предиката является свойством самого предиката и не имеет отношения к какому-либо конкретному множеству ”.

Из ранее данных определений мы видим, что - и есть мера величины носителя, которая определяется Минским так: “Нам понадобится в дальнейшем уметь выражать представление о том, что функция может зависеть только от какого-то определенного подмножества множества R. Обозначим такое подмножество через ”. Функцию Минский определяет так:

“Множество всех предикатов, которое при заданном можно определить ... выбором различных значений и чисел , обозначим ”.

Таким образом, выражение - означает, что решение найдено соответствующим перцептроном. А число означает число связей между S и А элементами, причем число самих частных предикатов для определения порядка неважно.

Получается, что для Минского понятие оптимальности перцептрона сводится к нахождению решения при наименьшем числе параметров у частных предикатов, но с любым числом самих предикатов. Розенблатт же в своей работе, напротив, не следит так пристально за числом связей у А – элемента (т.е. частного предиката), и приоритет в понимании оптимальности отдает числу А-элементов, это видно из следующих его слов: “Основные параметры, важные для этой главы: число S – элементов и число А – элементов ”.

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

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

“Пример 1. Среди 16 булевых функций двух переменных порядок 1 имеют все, кроме функции неравнозначности , и ее дополнения – функции логической эквивалентности , порядок которых равен 2:

где, например, - предикат с носителем, состоящим из двух точек (поэтому и порядок равен 2), и его значением будет «Истина» только тогда, когда принадлежит X, а нет”.

3.3. Понятие маска Править

Следующее важное понятие Минский вводит под названием маска и определяет таким образом:

“1.4. Маски и другие примеры линейного представления

Особую роль будут играть предикаты вида =[все элементы множества А принадлежат X]=[ ]. В общепринятых обозначениях булевой алгебры эти предикаты оказываются конъюнкциями: если , то , или, как обычно пишут, .

Назовем маской множества А. ...

Предложение. Все маски имеют порядок 1.

Доказательство. Пусть А – любое конечное множество, состоящие из точек. Для каждой точки определим как предикат . Тогда . ... Пример 2. Функцию можно представить в виде линейной комбинации масок: ”.

Здесь важно понимать, что маска является не выходным предикатом , а является частным предикатом . Поэтому имеет порядок 1 не потому, что имеет одну связь с входным полем (сетчаткой), как это было бы для предиката , а потому, что не содержит в себе других частных предикатов. И важно еще, что маска зависит только от одного подмножества точек.

Далее для нашего анализа ключевой является следующая теорема Минского:

“1.5. Теорема о положительной нормальной форме Порядок функции можно определить, представляя ее как линейную пороговую функцию относительно множества масок (теорема 1.5.3.).

Теорема 1.5.1. Каждый предикат является линейной пороговой функцией относительно множества всех масок, т.е. принадлежит (все маски).

Доказательство. Любую булеву функцию можно записать в дизъюнктивной нормальной форме , где - произведение (конъюнкция) , в котором каждое есть или , или . Так как для любого истинным может быть не более одного , то, используя арифметическую сумму, можно переписать в виде . Далее, к любому произведению, содержащему отрицание какой-нибудь буквы, можно применить следующую формулу: пусть Ђ и U означают любые цепочки букв, тогда Ђ U = Ђ(1- ) U = Ђ U - Ђ U . Если и дальше применять эту формулу, то можно уничтожить все отрицания, не увеличивая длины произведения. Избавившись от отрицаний и сгруппировав подобные члены, мы получим положительную нормальную форму , где каждый предикат является маской, а каждое число целое. Поскольку сумма равна нулю или единице, можно записать ”. Дальнейшие теоремы приведем без доказательства:

“Теорема 1.5.2. Положительная нормальная форма единственна.

Теорема 1.5.3. Предикат имеет порядок тогда и только тогда, когда есть наименьшее число, для которого существует множество масок, удовлетворяющих условиям для всех из , ”.

Приведем еще один пример Минского:

“Пример. Порядок булевой формы не превышает степени ее дизъюнктивной нормальной формы. Например, , отсюда видно, как исключить отрицание, не повышая порядка”.

3.4. Инвариантность входных данных. Предикат «Четность» Править

Здесь мы подошли к центральному понятию во всем математическом аппарате Минского. Важность теоремы об инвариантности подчеркивает и сам Минский:

“Сейчас, наконец, можно сформулировать и доказать нашу основную теорему. Из нее будет видно, что если предикат перцептрона инвариантен относительно группы G, то его коэффициенты должны зависеть только от классов G – эквивалентности соответствующим им предикатов . В дальнейших исследованиях эта теорема будет наиболее мощным нашим орудием ... ”.

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

Ниже приводятся более строгие теоремы из работы Минского, которые доказывают вышесказанное.

“Теорема об инвариантности относительно групп Пусть (1) G – конечная группа преобразований конечного пространства R; (2) - множество предикатов на R, замкнутое относительно G; (3) предикат принадлежит и инвариантен относительно G. Тогда существует линейное представление предиката . , для которого коэффициенты зависят только от класса G – эквивалентности предикатов , т.е. если , то .

Следствие 1. Любой инвариантный относительно группы предикат (порядка ), удовлетворяющий условиям теоремы, можно представить в виде , где - множество масок (степени не более ), а , если можно преобразовать в при помощи элемента группы G.

Следствие 2. Пусть - разбиение множества на классы эквивалентности по отношению к . Тогда если выполнены условия теоремы, то можно записать в виде , где , т.е. есть число эквивалентных относительно группы предикатов i-го типа, которым удовлетворяет Х”.

Далее, Минский демонстрирует наиболее яркий пример применения теоремы об инвариантности при решении задачи нахождения предиката четность (усложненная задача “исключающего или”). Вначале Минский доказывает следующую теорему:

“Теорема 3.1.1. Предикат четность имеет порядок .

Иными словами, для вычисления этого предиката требуется по крайней мере один частный предикат, носителем которого служит все пространство R”.

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

Этот факт Минский демонстрирует примером на рисунке, названным “Инвариантные относительно группы коэффициенты предиката четность при ” и комментариями по тексту:


Рис.2. Инвариантные относительно группы коэффициенты предиката четность при


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

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

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

4. Заключение Править

Итак, здесь мы сформируем утверждения, которые прямо следуют из рассмотренного в статье материала:

  1. Проблем с распознаванием нелинейных входных данных у перцептрона нет;
  2. Проблема возникает лишь тогда, когда входные данные оказываются инвариантными. Классическим примером является предикат четность;
  3. Проблема инвариантности свойственна всем известным синхронным искусственным нейронным сетям;
  4. Для асинхронных нейронных сетей есть некий выход из этой проблемы, т.к. они помимо пространственных связей, рассматривают временные связи. Это дает некую свободу, т.к. практически не могут существовать входные данные одновременно инвариантные как в пространстве, так и во времени. Но с асинхронными сетями связана другая проблема – устойчивости обучения, которой добиться намного сложнее;
  5. Так как перцептрон является частным случаем параллельных вычислений, то проблема инвариантности свойственна и вообще параллельным вычислениям. Так в ходе анализа Минский показывает, что для ряда задач, таких как четность или связанность, следует отказаться от параллельных вычислений, т.к. они не оптимальны, а использовать последовательные вычисления. Таким образом, Минский как бы показывает границы применимости параллельных и последовательных вычислений. Примечательно, что причиной для таких исследований послужил перцептрон, что неоднократно подчеркивал сам Минский.

Теперь, если мы вместе с Минским считаем, что: “всякое интересное геометрическое свойство является инвариантом некоторой группы преобразований”, то нам необходимо решать проблему инвариантности, и путей может быть два: (1) последовательные вычисления и (2) асинхронные сети.

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

5. Список литературы Править

  1. Розенблатт Ф. (1965). Принципы нейродинамики (Перцептроны и теория механизмов мозга), Мир, Москва.
  2. Минский М., Пейперт С. (1971). Перцептроны, Мир, Москва.
  3. Вассерман Ф. (1992). Нейрокомпьтерная техника: теория и практика, Мир, Москва.

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

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

Также на ФЭНДОМЕ

Случайная вики