Персептрон - Perceptron

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

История

Mark I Perceptron machine, первая реализация алгоритма персептрона. Он был подключен к камере с фотоэлементами из сульфида кадмия 20 × 20 для получения изображения размером 400 пикселей. Основная видимая функция - это патч-панель, которая устанавливает различные комбинации входных функций. Справа - ряды потенциометров , в которых реализованы адаптивные веса.

Алгоритм персептрона был изобретен в 1958 году в Корнельской лаборатории аэронавтики по Розенблатту , финансируемые США Управление военно - морских исследований .

Перцептрон был задуман как машина, а не как программа, и хотя его первая реализация была в программном обеспечении для IBM 704 , впоследствии он был реализован в специально созданном оборудовании как «перцептрон Mark 1». Эта машина была разработана для распознавания изображений : она имела массив из 400 фотоэлементов , случайно подключенных к «нейронам». Веса кодировались с помощью потенциометров , а обновления веса во время обучения выполнялись с помощью электродвигателей.

На пресс-конференции 1958 года, организованной ВМС США, Розенблатт сделал заявления о перцептроне, которые вызвали жаркие споры среди молодого сообщества ИИ ; Основываясь на заявлениях Розенблатта, The New York Times сообщила, что перцептрон является «зародышем электронного компьютера, который [ВМФ] ожидает, что он сможет ходить, говорить, видеть, писать, воспроизводить себя и осознавать свое существование».

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

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

В 1969 году известная книга Марвина Мински и Сеймура Паперта под названием « Персептроны » показала, что для этих классов сетей невозможно изучить функцию XOR . Часто считается (ошибочно), что они также предположили, что аналогичный результат будет справедлив для многослойной сети персептронов. Однако это неправда, поскольку и Мински, и Паперт уже знали, что многослойные перцептроны способны выполнять функцию XOR. (См. Страницу о персептронах (книга) для получения дополнительной информации.) Тем не менее, часто неправильно цитируемый текст Мински / Пейперта вызвал значительное снижение интереса и финансирования исследований нейронных сетей. Прошло еще десять лет, прежде чем исследования нейронных сетей в 1980-х годах возродились. Этот текст был переиздан в 1987 году как «Перцептроны - расширенное издание», где показаны и исправлены некоторые ошибки в исходном тексте.

Ядро Персептрон алгоритма уже была введена в 1964 году Айзерманом и соавт. Гарантии границ маржи были даны для алгоритма Perceptron в общем неотделимом случае сначала Фройндом и Шапиром (1998), а позднее Мохри и Ростамизаде (2013), которые расширяют предыдущие результаты и дают новые границы L1.

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

Определение

В современном понимании персептрон - это алгоритм для изучения двоичного классификатора, называемого пороговой функцией : функция, которая отображает свой вход ( вектор с действительными значениями ) в выходное значение (одно двоичное значение): ${\ displaystyle \ mathbf {x}}$ ${\ Displaystyle е (\ mathbf {х})}$

{\ displaystyle f (\ mathbf {x}) = {\ begin {cases} 1 & {\ text {if}} \ \ mathbf {w} \ cdot \ mathbf {x} + b> 0, \\ 0 & {\ text {в противном случае}} \ end {case}}}

где - вектор действительных весов, - скалярное произведение , где $m$ - количество входов в перцептрон, а $b$ - смещение . Смещение сдвигает границу решения от начала координат и не зависит от входного значения. ${\ displaystyle \ mathbf {w}}$ ${\ displaystyle \ mathbf {w} \ cdot \ mathbf {x}}$ ${\ Displaystyle \ сумма _ {я = 1} ^ {м} ш_ {я} х_ {я}}$

Значение (0 или 1) используется для классификации как положительного или отрицательного экземпляра в случае проблемы двоичной классификации. Если $b$ отрицательно, то взвешенная комбинация входов должна давать положительное значение больше, чем для того, чтобы подтолкнуть нейрон классификатора к порогу 0. В пространственном отношении смещение изменяет положение (но не ориентацию) границы принятия решения . Алгоритм обучения персептрона не завершается, если обучающая выборка не является линейно разделимой . Если векторы не являются линейно разделяемыми, обучение никогда не достигнет точки, в которой все векторы классифицируются должным образом. Самый известный пример неспособности персептрона решать задачи с линейно неразрывными векторами - это логическая задача « исключающее ИЛИ». Пространства решений границ решений для всех бинарных функций и обучающего поведения изучаются в справочнике. ${\ Displaystyle е (\ mathbf {х})}$ ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle | b |}$

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

Алгоритм обучения

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

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

Определения

Сначала мы определяем некоторые переменные:

r - скорость обучения перцептрона. Скорость обучения составляет от 0 до 1, большие значения делают изменения веса более волатильными.
${\ Displaystyle у = е (\ mathbf {z})}$ обозначает выход перцептрона для входного вектора . ${\ displaystyle \ mathbf {z}}$
${\ Displaystyle D = \ {(\ mathbf {x} _ {1}, d_ {1}), \ dots, (\ mathbf {x} _ {s}, d_ {s}) \}}$ ${\ Displaystyle D = \ {(\ mathbf {x} _ {1}, d_ {1}), \ dots, (\ mathbf {x} _ {s}, d_ {s}) \}}$ является подготовка набора из образцов, где: ${\ displaystyle s}$ $s$
- ${\ displaystyle \ mathbf {x} _ {j}}$ является -мерном входного вектора. ${\ displaystyle n}$
- ${\ displaystyle d_ {j}}$ - желаемое выходное значение перцептрона для этого входа.

Мы показываем значения характеристик следующим образом:

${\ displaystyle x_ {j, i}}$ - это значение th функции вектора входных обучающих данных . ${\ displaystyle i}$ ${\ displaystyle j}$
${\ displaystyle x_ {j, 0} = 1}$ .

Чтобы представить веса:

${\ displaystyle w_ {i}}$ - ое значение в векторе весов , которое нужно умножить на значение ого входного признака. ${\ displaystyle i}$ ${\ displaystyle i}$
Потому что , по сути, это смещение, которое мы используем вместо константы смещения . ${\ displaystyle x_ {j, 0} = 1}$ ${\ displaystyle w_ {0}}$ ${\ displaystyle b}$

Чтобы показать зависимость от времени , мы используем: ${\ displaystyle \ mathbf {w}}$

${\ Displaystyle ш_ {я} (т)}$ это вес в момент времени . ${\ displaystyle i}$ ${\ displaystyle t}$

Шаги

Инициализируйте веса. Веса могут быть инициализированы 0 или небольшим случайным значением. В приведенном ниже примере мы используем 0.
Для каждого примера j в нашем обучающем наборе D выполните следующие шаги для ввода и желаемого вывода : ${\ displaystyle \ mathbf {x} _ {j}}$ ${\ mathbf {x}} _ {j}$ ${\ displaystyle d_ {j}}$ ${\ displaystyle d_ {j}}$
1. Рассчитайте фактический выход:
  ${\ Displaystyle {\ begin {align} y_ {j} (t) & = f [\ mathbf {w} (t) \ cdot \ mathbf {x} _ {j}] \\ & = f [w_ {0} (t) x_ {j, 0} + w_ {1} (t) x_ {j, 1} + w_ {2} (t) x_ {j, 2} + \ dotsb + w_ {n} (t) x_ { j, n}] \ end {выровнено}}}$
2. Обновите веса:
  ${\ displaystyle w_ {i} (t + 1) = w_ {i} (t) \; {\ boldsymbol {+}} \; r \ cdot (d_ {j} -y_ {j} (t)) x_ { j, i}}$ , Для всех функций , является скорость обучения . ${\ Displaystyle 0 \ Leq я \ Leq п}$ ${\ displaystyle r}$
Для автономного обучения второй шаг может повторяться до тех пор, пока ошибка итерации не станет меньше заданного пользователем порога ошибки , или пока не будет завершено заранее определенное количество итераций, где s снова является размером набора выборок. ${\ displaystyle {\ frac {1} {s}} \ sum _ {j = 1} ^ {s} | d_ {j} -y_ {j} (t) |}$ ${\ displaystyle \ gamma}$

Алгоритм обновляет веса после шагов 2a и 2b. Эти веса немедленно применяются к паре в обучающем наборе и впоследствии обновляются, вместо того, чтобы ждать, пока все пары в обучающем наборе пройдут эти шаги.

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

Соответствующие веса применяются к входам, и полученная взвешенная сумма передается функции, которая производит выход o.

Конвергенция

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

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

Предположим, что входные векторы из двух классов могут быть разделены гиперплоскостью с запасом , т.е. существует вектор весов и член смещения $b,$ такой, что для всех с и для всех с , где - желаемое выходное значение перцептрона. для ввода . Кроме того, пусть $R$ обозначает максимальную норму входного вектора. Новиков (1962) доказал, что в этом случае алгоритм персептрона сходится после внесения обновлений. Идея доказательства состоит в том, что весовой вектор всегда корректируется на ограниченную величину в направлении, в котором он имеет отрицательное скалярное произведение , и, таким образом, может быть ограничен сверху значением $O$ $($ $\sqrt$ $t$ $)$ , где $t$ - количество изменений в вектор веса. Однако он также может быть ограничен снизу $O$ $($ $t$ $),$ потому что, если существует (неизвестный) удовлетворительный вектор веса, то каждое изменение прогрессирует в этом (неизвестном) направлении на положительную величину, которая зависит только от входного вектора. ${\ displaystyle \ gamma}$ ${\ Displaystyle \ mathbf {w}, || \ mathbf {w} || = 1}$ ${\ displaystyle \ mathbf {w} \ cdot \ mathbf {x} _ {j}> \ gamma}$ ${\ displaystyle j}$ ${\ displaystyle d_ {j} = 1}$ ${\ displaystyle \ mathbf {w} \ cdot \ mathbf {x} _ {j} <- \ gamma}$ ${\ displaystyle j}$ ${\ displaystyle d_ {j} = 0}$ ${\ displaystyle d_ {j}}$ ${\ displaystyle j}$ ${\ Displaystyle О (R ^ {2} / \ gamma ^ {2})}$

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

Хотя алгоритм персептрона гарантированно сходится к некоторому решению в случае линейно разделяемой обучающей выборки, он все же может выбрать любое решение, а проблемы могут допускать множество решений различного качества. Персептрон оптимальной стабильности , в настоящее время более известный как линейная поддержка вектор машина , был разработан , чтобы решить эту проблему (Krauth и Mezard, 1987).

Варианты

Карманный алгоритм с храповым механизмом (Gallant, 1990) решает проблему стабильности обучения перцептрона, оставляя лучшее решение, которое до сих пор было замечено, «в своем кармане». Затем карманный алгоритм возвращает решение в кармане, а не последнее решение. Его также можно использовать для неотделимых наборов данных, где цель состоит в том, чтобы найти перцептрон с небольшим количеством ошибочных классификаций. Однако эти решения появляются чисто стохастически, и, следовательно, карманный алгоритм не приближается к ним постепенно в процессе обучения, и они не гарантированно появятся в течение заданного количества шагов обучения.

Алгоритм Максовера (Wendemuth, 1995) является «надежным» в том смысле, что он будет сходиться независимо от (предшествующего) знания о линейной разделимости набора данных. В случае линейно разделимой задачи он решит задачу обучения - при желании даже с оптимальной стабильностью ( максимальный запас между классами). Для неотделимых наборов данных он вернет решение с небольшим количеством ошибок классификации. Во всех случаях алгоритм постепенно приближается к решению в процессе обучения, без запоминания предыдущих состояний и без стохастических скачков. Конвергенция сводится к глобальной оптимальности для разделяемых наборов данных и к локальной оптимальности для неотделимых наборов данных.

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

В разделимых задачах обучение перцептрона также может быть направлено на поиск наибольшего разделяющего разрыва между классами. Так называемый перцептрон оптимальной устойчивости может быть определен с помощью итеративных схем обучения и оптимизации, таких как алгоритм Min-Over (Krauth and Mezard, 1987) или AdaTron (Anlauf and Biehl, 1989)). AdaTron использует тот факт, что соответствующая задача квадратичной оптимизации является выпуклой. Перцептрон оптимальной устойчивости вместе с трюком с ядром составляют концептуальную основу машины опорных векторов .

-Perceptron дополнительно использовала предварительную обработку слоя фиксированных случайных весов, с порогами выходных блоками. Это позволило перцептрону классифицировать аналоговые паттерны, проецируя их в двоичное пространство . Фактически, для проекционного пространства достаточно большой размерности шаблоны могут стать линейно разделяемыми. ${\ displaystyle \ alpha}$

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

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

Другие алгоритмы линейной классификации включают Winnow , машину опорных векторов и логистическую регрессию .

Мультиклассовый персептрон

Как и большинство других методов обучения линейных классификаторов, перцептрон естественным образом обобщается на мультиклассовую классификацию . Здесь вход и выход взяты из произвольных наборов. Функция представления признаков отображает каждую возможную пару вход / выход в конечномерный вещественный вектор признаков. Как и раньше, вектор признаков умножается на вектор весов , но теперь полученная оценка используется для выбора среди множества возможных выходных данных: ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle f (x, y)}$ ${\ displaystyle w}$

{\ displaystyle {\ hat {y}} = \ operatorname {argmax} _ {y} f (x, y) \ cdot w.}

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

{\ displaystyle w_ {t + 1} = w_ {t} + f (x, y) -f (x, {\ hat {y}}).}

Эта формулировка мультиклассовой обратной связи сводится к исходному персептрону, когда является вещественным вектором, выбранным из , и . ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle \ {0,1 \}}$ ${\ displaystyle f (x, y) = yx}$

Для некоторых задач можно выбрать представления и функции ввода / вывода, чтобы их можно было эффективно найти, даже если они выбраны из очень большого или даже бесконечного набора. ${\ displaystyle \ mathrm {argmax} _ {y} f (x, y) \ cdot w}$ ${\ displaystyle y}$

С 2002 года обучение перцептронов стало популярным в области обработки естественного языка для таких задач, как тегирование части речи и синтаксический анализ (Collins, 2002). Он также применялся к крупномасштабным задачам машинного обучения в среде распределенных вычислений .

использованная литература

дальнейшее чтение

Айзерман, М.А., Браверман, Е.М., и Лев И. Розоноэр. Теоретические основы метода потенциальных функций в обучении распознаванию образов. Автоматика и телемеханика, 25: 821–837, 1964.
Розенблатт, Франк (1958), Персептрон: вероятностная модель для хранения и организации информации в мозге, Корнельская авиационная лаборатория, Психологическое обозрение, т. 65, № 6, стр. 386–408. DOI : 10.1037 / h0042519 .
Розенблатт, Франк (1962), Принципы нейродинамики. Вашингтон, округ Колумбия: Спартанские книги.
Минский М.Л., Паперт С.А. 1969. Персептроны . Кембридж, Массачусетс: MIT Press.
Галлант, SI (1990). Алгоритмы обучения на основе персептрона. IEEE Transactions on Neural Networks, vol. 1, вып. 2. С. 179–191.
Мохри, Мехриар и Ростамизаде, Афшин (2013). Границы ошибки персептрона arXiv: 1305.0208, 2013.
Новиков, А.Б. (1962). О доказательствах сходимости на персептронах. Симпозиум по математической теории автоматов, 12, 615–622. Политехнический институт Бруклина.
Видроу, Б. , Лер, Массачусетс, « 30 лет адаптивных нейронных сетей: персептрон, мадалин и обратное распространение », Proc. IEEE , том 78, № 9, стр. 1415–1442, (1990).
Коллинз, М. 2002. Дискриминационные методы обучения скрытых марковских моделей: теория и эксперименты с алгоритмом персептрона в материалах конференции по эмпирическим методам обработки естественного языка (EMNLP '02).
Инь, Хунфэн (1996), алгоритмы и анализ на основе персептронов, библиотека спектра, Университет Конкордия, Канада

Languages

In other projects