ФЭНДОМ



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

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



опубликованный оригинал (англ.)

Гарантированное формирование перцептроном пространства, которое удовлетворяет гипотезе компактности Править

Архитектура перцептрона, обеспечивающая компактность описания образов, Perceptron architecture ensuring pattern description compactnes, 2009, Scientific proceedings of Riga Technical University, RTU, Riga

Гипотеза компактности в искусственных нейронных сетях (ИНС) Править

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

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

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

Кроме того, разные задачи предъявляют разные требования к понятию компактности. Для одних задач нужно, чтобы близкими являлись образы, почти совпадающие при наложении (имеющие много общих точек), для других – образы, полученные друг из друга путем переноса и поворота, третьи задачи потребуют, чтобы близкими считались бы подобные фигуры (все треугольники или все многоугольники), в четвертых не сами образы, а их обобщенные характеристики, такие как четность, связность, выпуклость.

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

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

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

То, что такое пространство признаков не совпадает с пространством исходных данных, легко показывает задача «XOR», в которой пространство исходных данных становится линейно не разделимым. Также иногда ошибочно полагают, что наличие в ИНС скрытого слоя, в котором и формируется пространство признаков на основе пространства исходных данных, автоматически удовлетворяет гипотезе компактности (даже в уточненном здесь смысле). Легко показать, что при достаточно высоких порогах в элементах скрытого слоя (А - элементах) они просто перестают передавать сигнал на выходные элементы (R - элементы), и наоборот, при низких порогах и высокой заполненности входных элементов (S – элементов) сигналы становятся столь интенсивными, что стимулы перестают различаться. Также возможны определенные сочетания весовых коэффициентов, при которых невозможно построить пространство признаков, удовлетворяющее гипотезе компактности.

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

Перцептрон Розенблатта Править

Perceptron

Рис. 1. Архитектура перцептрона Розенблатта

Перцептрон Розенблатта [2, 3] состоит из элементов трёх типов: S-элементов, A-элементов и R-элементов (ниже для простоты рассматривается случай, когда R-элемент один). S-элементы это слой рецепторов. Эти рецепторы соединены с A-элементами с помощью возбуждающих и тормозящих связей. Каждый рецептор может находиться в одном из двух состояний — покоя или возбуждения. A-элементы представляют собой сумматоры с порогом (то есть формальные нейроны). Это означает, что A-элемент возбуждается, если алгебраическая сумма возбуждений, приходящих к нему от рецепторов, превышает определённую величину — его порог. Сигналы от возбудившихся A-элементов передаются в сумматор R, причём сигнал от i-го ассоциативного элемента передаётся с весовым коэффициентом $ v_i $.

Система связей между рецепторами S- и A-элементов, так же как и пороги A-элементов выбираются некоторым случайным, но фиксированным образом, а обучение состоит лишь в изменении коэффициентов $ v_i $.

Например, мы хотим научить перцептрон разделять два класса объектов, и потребуем, чтобы при предъявлении объектов первого класса выход был положительным, а при предъявлении объектов второго класса — отрицательным. Начальные коэффициенты $ v_i $ полагаем равными нулю. Далее предъявляем обучающую выборку: объекты (например, круги либо квадраты) с указанием класса, к которым они принадлежат. Показываем перцептрону объект первого класса. При этом некоторые A-элементы возбудятся. Коэффициенты $ v_i $ , соответствующие этим возбуждённым элементам, увеличиваем на 1. Затем предъявляем объект второго класса, и коэффициенты $ v_i $ тех A-элементов, которые возбуждаются при этом показе, уменьшаем на 1. Этот процесс продолжим для всей обучающей выборки. В результате обучения сформируются значения весов связей $ v_i $.

После обучения перцептрон готов работать в режиме распознавания. В этом режиме перцептрону предъявляются «незнакомые» объекты, и он должен установить, к какому классу они принадлежат. Работа перцептрона состоит в следующем: при предъявлении объекта возбудившиеся A-элементы передают R-элементу сигнал, равный сумме соответствующих коэффициентов $ v_i $. Если эта сумма положительна, то принимается решение, что данный объект принадлежит к первому классу, а если она отрицательна — ко второму.

Доказательства, сделанные Розенблаттом Править

В первую очередь, мы рассмотрим основные положения, доказанные Розенблаттом в [2], необходимые для последующего анализа. Была доказана следующая теорема:

«Теорема 3. Даны элементарный перцептрон, пространство стимулов W и какая-то классификация C(W). Тогда для существования решения для необходимо и достаточно, чтобы существовал некоторый вектор u , лежащий в том же ортанте, что и C(W) , и некоторый вектор x , такой, что $ Gx=u $

а также два прямых следствия из этой теоремы:

«Следствие 1. Даны элементарный перцептрон и пространство стимулов W . Тогда, если G - особенная матрица (детерминант которой равен нулю), то имеется некоторая классификация C(W) , для которой решения не существует.»

«Следствие 2. Если число стимулов в пространстве W больше числа А – элементов элементарного перцептрона, то существует некоторая классификация C(W) , для которой решения не существует».

Пространством стимулов Розенблатт называет пространство исходных данных. Особую роль в теореме и ее следствиях играет т.н. G - матрица, она имеет вид: $ G= ... $

, где n - число стимулов, а $ g_{ij} $ - коэффициент обобщения. Коэффициент обобщения показывает относительное число А – элементов, реагирующих как на стимул $ St_i $ , так и на стимул $ St_j $ . Например, при решении задачи XOR G - матрица может иметь вид $ G= ... $ , откуда видно, что имеется 3 стимула (строки – стимулы, столбцы – А-элементы), и например, на стимул $ St_1 $ и стимул $ St_3 $ реагирует только 1 общий А – элемент, в то время как отдельно на стимул $ St_3 $ реагируют 2 А – элемента, а на стимул $ St_1 $ один А – элемент. Теперь видно, что коэффициенты обобщения $ g_{ij} $ являются мерой пересечения множеств А – элементов, реагирующих на стимулы $ St_i $ и $ St_j $ . При этом G - матрица может быть получена из более простой А – матрицы. Они связаны соотношением $ G=AA^T $ ( $ A^T $ - транспонированная матрица). А – матрица имеет размер $ n x N_a $ , где n - число стимулов, $ N_a $ - число А – элементов, а ее элементы $ a_{ij}=1 $ , если А – элемент $ a_j $ реагирует на стимул $ St_i $ , и $ a_{ij}=0 $ в противоположном случае.

Учитывая, что в перцептроне весовые коэффициенты в первом слое связей фиксированы, видим, что А – матрица не изменяется со временем. При этом она показывает, какие из А – элементов будут активны при предъявлении перцептрону определенного стимула. Так, например, при решении задачи XOR А – матрица может иметь вид , откуда видно, что при стимуле №1 активен третий А-элемент, при стимуле №2 активен первый и третий А – элемент, а при стимуле №3 активен второй и третий А – элемент.

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

Условия, при которых перцептрон формирует пространство, удовлетворяющие гипотезе компактности Править

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

Но Розенблатт не провел полного анализа того, что это может означать на практике. Следствием этого стало недостаточно обоснованное утверждение Минского [4], что «перцептрон работает безупречно только при том условии, что множество исходных данных линейно разделимо».

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

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

Связь и А матриц перцептрона Править

Вначале перейдем от матрицы к матрице А (матрица А далее имеет размер , чтобы удовлетворить следствию 2), т.к. она удобнее для последующего анализа:

  1. Пусть матрица особенная, то есть . Тогда , получаем что  ; отсюда следует, что , т.е. матрица А особенная.
  2. Пусть матрица не особенная, то есть . Тогда , получаем что , отсюда следует, что , т.е. матрица А не особенная.
  3. Пусть . Найдем , , т.е. матрица особенная.
  4. Пусть . Найдем , , т.е. матрица не особенная.

Таким образом, получаем, что матрица особенна, тогда и только тогда, когда матрица А особенна.

Вероятность активности А – элементов Править

Из определения матрицы А видим, что она бинарная, и принимает значение 1, когда активен соответствующий А – элемент. Нас будет интересовать, какова вероятность появления в матрице единицы и, соответственно, какова вероятность нуля. Совершенно не обязательно, что это равновероятные события. Как говорилось выше, Розенблатт для этого исследовал так называемые Q - функции. Здесь мы рассмотрим только основные положения.

Рассмотрим биномиальную модель связей в первом слое. Она получается, если к каждому А – элементу подходит фиксированное количество связей от - элементов. Эти связи состоят из возбуждающих (вес +1) и тормозящих (вес -1). Порог фиксирован и одинаков для всех А – элементов. Начала связей, идущих к А – элементам, выбираются независимо друг о друга и распределены с равной вероятностью на всем множестве - элементов.


PerceptronMath2

Рис. 2. Зависимость вероятности активности А – элементов. а) влияние отношения x:y при $ \theta=1 $ ; б) влияние изменения числа связей при x=y и $ \theta=1 $ (заимствованно из [2] рис. 7)

В этой модели Q - функции не зависят от полного числа сенсорных элементов, а лишь от относительного числа освещенных - элементов. На рис. 2. показана зависимость вероятности активности А - элемента от величины освещенной площадки сетчатки. Заметим, что для моделей, у которых имеются только возбуждающие связи ( ) при высоком числе освещенных - элементов значение приближается к 1. То есть вероятность активности А – элементов находится в прямой зависимости от числа освещенных - элементов, что плохо влияет на распознавание относительно малых и больших изображений. Как будет показано ниже, это происходит из-за большой вероятности того, что А – матрица будет особенной. Поэтому для стабильности распознавания образов любых геометрических размеров надо так выбрать отношение , чтобы вероятность активности А – элементов как можно меньше бы зависела от числа освещенных -элементов.

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

В этом случае число единиц в матрице А будет описываться биномиальным распределением:

,

где - число элементов в матрице, - число единиц в матрице. В не равновероятном случае число единиц в матрице А будет описываться распределением Бернулли:

,

где - вероятность появления единицы.

На рис. 3 показано распределение для не особенных матриц размером 5х5 в зависимости от числа единиц в матрице.

PerceptronMath3

Рис. 3. Распределение числа матриц N в зависимости от количества единиц n в матрице, размером 5х5

Вероятность того, что А матрица особенная Править

PerceptronMathT1

Таблица 1. Вероятности появления особенных матриц в зависимости от их размера

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

Но есть рассчитанная последовательность А002884 [5], дающая нижнюю границу вероятности того, что матрица размера не будет особенной (у этих матриц определитель равен 1). Для случаев вероятность почти стабильная и уменьшается практически несущественно, и составляет 28,8788 %. Есть также последовательность А055165 [6], дающая вероятность именно того, что матрица размером не особенная. Но посчитать ее можно лишь перебором и это сделано до случаев .


Анализируя случай с равновероятностным появлением единицы и нуля в матрице, в таблице 1 и на рис. 4 показана вероятность того, что бинарная матрица не особенная в зависимости от ее размера. Первые 8 значений (P) – это точные расчетные данные, полученные используя последовательность А055165. Последующие же значения получены методом Монте-Карло, т.е. случайным образом выбираются 1000 матриц и рассчитывается, какой из них процент особенных. Таким образом проводятся 100 испытаний, и получаются нижняя и верхняя граница вероятности.

PerceptronMath4

Рис. 4. Вероятности появления особенных матриц в зависимости от их размера


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

Выводы Править

В 1965 году Ковер сформулировал теорему известную как теорема Ковера [7]: «Нелинейное преобразование сложной задачи классификации образов в пространство более высокой размерности повышает вероятность линейной разделимости образов». Она по сути описывает тот процесс, который происходит в первом слое перцептрона. Еще задолго до ее формулирования Ковером она используется для доказательства следствия 3 теоремы 3 Розенблатта [2], которое доказывает, по сути, то же самое, только по отношению к архитектуре перцептрона. Таким образом, Джозеф в 1960 году [8, 9] первый доказал данную теорему, а Розенблатт в 1962 году использовал ее для уточнения характеристик перцептрона. И только в 1965 году Ковер (видимо независимо) сформулировал данную теорему в современном виде.

С современным применением данной теоремы мы встречаемся в ряде ИНС, например, в сетях на основе радиальных базисных функций (RBF) [10]. Но учитывая то, что перцептрон задолго до них реализовывал суть данной теоремы – мы приходим к выводу, что RBF-сеть есть частный случай перцептрона, отличающейся, по сути, только особой функцией активации.

Таким образом, первый вывод, который мы можем сделать заключается в том, что приведенный математический анализ в работе позволяет понять, что RBF-сеть и некоторые современные ИНС являются лишь подвидами перцептрона Розенблатта. Это в свою очередь, позволяет их сравнивать аналитически, а не только экспериментально.

Второй вывод, который мы сделаем, заключается в том, что представленный в работе анализ позволяет понять, почему в ряде случаев исследователями делались несколько некорректные выводы по отношению к возможностям перцептронов. Так, например, в работе [11] утверждается, что “эксперименты свидетельствуют об ограниченной эффективности α-системы адаптации весов А-элементов”, а так же “отсутствие сходимости алгоритма адаптации весов А-элементов объясняется, очевидно, нелинейностью границ классов в пространстве А-элементов”. Данные выводы в корне ошибочны, т.к. представленный анализ нам четко указывает, что при соблюдении некоторых условий (см. выше) в пространстве А-элементов не может образоваться нелинейная граница классов. И проблема состоит не в архитектуре перцептрона и не в алгоритме адаптации весов, а в том, что экспериментатором не выполняются условия описанные в данной работе. Так, например, в рассматриваемом случае имелось только 20 А-элементов, в то время как теоретическая оценка говорит о том, что в перцептроне должно участвовать как минимум 30 А-элементов. Практически же надежнее иметь минимум порядка 100 А-элементов для исключения случая, когда G-матрица становится особенной.

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

СПИСОК ЛИТЕРАТУРЫ Править

  1. Бонгард М.М. (1967) Проблема узнавания. – Москва, «Наука».
  2. Розенблат Ф. (1965). Принципы нейродинамики (Перцептроны и теория механизмов мозга), Москва, «Мир».
  3. Проект Википедия – энциклопедия в интернете Перцептрон
  4. Минский М. (1971). Перцептроны, Москва, «Мир».
  5. Encyclopedia of Integer Sequences. “Number of nonsingular n x n matrices over GF(2)” http://www.research.att.com/~njas/sequences/A002884
  6. Encyclopedia of Integer Sequences. “Number of regular n x n matrices with rational entries” equal to 0 or 1. http://www.research.att.com/~njas/sequences/A055165
  7. Cover T.M. “Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition”, IEEE Transactions on Electronic Computers, 1965, vol EC-14, p.326-334
  8. Joseph R.D. “The number of orthants in n-space intersected by an s-dimensional subspace”, Technical Memo 8, Project PARA, Cornell Aeronautical Lab., Buffalo, NY, 1960
  9. Joseph R.D. “Contributions to Perceptron Theory”, Cornell Aeronautical Lab., № VG-1196-G-7, Buffalo, 1960
  10. Хайкин, С. «Нейронные сети: Полный курс», Neural Networks: A Comprehensive Foundation. — 2-е изд. — М.: «Вильямс», 2006. — 1104 с. — ISBN 0-13-273350-1
  11. А.Н. Борисов, В.Е. Голендер, «Выбор прототипов перцептрона», Кибернетика и диагностика, Рига, 1968, с. 93-102