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

«Персептроны» перенаправляются сюда. О книге 1969 года см. Персептроны (книга).

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

История

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

Смотрите также: История искусственного интеллекта § Персептроны и темная эра коннекционизма, и AI Winter § Отказ от коннекционизма в 1969 г.

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

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

На пресс-конференции 1958 года, организованной ВМС США, Розенблатт сделал заявления о перцептроне, которые вызвали жаркие споры среди молодых людей. AI сообщество; на основании утверждений Розенблатта, Нью-Йорк Таймс сообщил, что перцептрон является «эмбрионом электронного компьютера, который [ВМФ] ожидает, что он сможет ходить, говорить, видеть, писать, воспроизводить себя и осознавать свое существование».^[4]

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

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

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

В перцептрон ядра алгоритм был уже представлен в 1964 году Айзерманом и др.^[5] Гарантии границ маржи были даны для алгоритма Perceptron в общем неотделимом случае сначала Freund и Шапире (1998),^[1] и совсем недавно Mohri и Ростамизаде (2013), которые расширяют предыдущие результаты и дают новые границы L1.^[6]

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

Определение

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

${\displaystyle f(\mathbf {x} )={\begin{cases}1&{\text{if }}\ \mathbf {w} \cdot \mathbf {x} +b>0,\\0&{\text{otherwise}}\end{cases}}}$

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

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

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

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

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

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

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

Определения

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

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

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

• ${\displaystyle x_{j,i}}$ стоимость ${\displaystyle i}$-я особенность ${\displaystyle j}$й тренинг входной вектор.
• ${\displaystyle x_{j,0}=1}$.

Для представления весов:

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

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

• ${\displaystyle w_{i}(t)}$ это вес ${\displaystyle i}$ вовремя ${\displaystyle t}$.

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

Шаги

1. Инициализируйте веса и порог. Веса могут быть инициализированы 0 или небольшим случайным значением. В приведенном ниже примере мы используем 0.
2. Для каждого примера j в нашем обучающем наборе D, выполните следующие шаги над вводом ${\displaystyle \mathbf {x} _{j}}$ и желаемый результат ${\displaystyle d_{j}}$:
   1. Рассчитайте фактический выход:

      ${\displaystyle {\begin{aligned}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{aligned}}}$

   2. Обновите веса:
      ${\displaystyle w_{i}(t+1)=w_{i}(t)+r\cdot (d_{j}-y_{j}(t))x_{j,i}}$, для всех функций ${\displaystyle 0\leq i\leq n}$, ${\displaystyle r}$ это скорость обучения.
3. За автономное обучение, второй шаг может повторяться до появления ошибки итерации ${\displaystyle {\frac {1}{s}}\sum _{j=1}^{s}|d_{j}-y_{j}(t)|}$ меньше указанного пользователем порога ошибки ${\displaystyle \gamma }$, или предварительно определенное количество итераций было выполнено, где s это снова размер выборки.

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

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

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

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

Предположим, что входные векторы из двух классов можно разделить гиперплоскостью с запасом ${\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}$. Кроме того, пусть р обозначают максимальную норму входного вектора. Новиков (1962) доказал, что в этом случае алгоритм персептрона сходится после выполнения ${\displaystyle O(R^{2}/\gamma ^{2})}$ обновления. Идея доказательства состоит в том, что вектор весов всегда корректируется на ограниченную величину в направлении, в котором он имеет отрицательное значение. скалярное произведение, и, таким образом, может быть ограничена сверху О(√т), где т - количество изменений весового вектора. Однако снизу он также может быть ограничен величиной О(т) потому что, если существует (неизвестный) удовлетворительный вектор веса, то каждое изменение прогрессирует в этом (неизвестном) направлении на положительную величину, которая зависит только от входного вектора.

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

Хотя алгоритм персептрона гарантированно сходится на немного решение в случае линейно разделимой обучающей выборки, она все еще может выбрать любой Решение и проблемы могут допускать множество решений различного качества.^[10] В перцептрон оптимальной устойчивости, в настоящее время более известная как линейная Машина опорных векторов, был разработан для решения этой проблемы (Krauth and Mezard, 1987).^[11]

Варианты

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

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

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

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

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

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

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

Другие алгоритмы линейной классификации включают 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 года обучение перцептронов стало популярным в области обработка естественного языка для таких задач как теги части речи и синтаксический анализ (Коллинз, 2002). Он также был применен к крупномасштабным задачам машинного обучения в распределенных вычислений настройка.^[14]

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

1. Фройнд, Ю.; Шапире, Р. Э. (1999). «Классификация большой маржи с использованием алгоритма персептрона» (PDF). Машинное обучение. 37 (3): 277–296. Дои:10.1023 / А: 1007662407062. S2CID  5885617.
2. Епископ, Кристофер М. (2006). Распознавание образов и машинное обучение. Springer. ISBN  0-387-31073-8.
3. Розенблатт, Франк (1957). «Персептрон - воспринимающий и распознающий автомат». Отчет 85-460-1. Корнельская авиационная лаборатория.
4. Олазаран, Микель (1996). "Социологическое исследование официальной истории спора о персептронах". Социальные исследования науки. 26 (3): 611–659. Дои:10.1177/030631296026003005. JSTOR  285702. S2CID  16786738.
5. Айзерман, М. А .; Браверман, Э. М .; Розоноэр, Л. И. (1964). «Теоретические основы метода потенциальных функций в обучении распознаванию образов». Автоматизация и дистанционное управление. 25: 821–837.
6. Мохри, Мехриар; Ростамизаде, Афшин (2013). «Границы ошибки персептрона». arXiv:1305.0208 [cs.LG ].
7. Кэш, Сидней; Юсте, Рафаэль (1999). «Линейное суммирование возбуждающих входов пирамидальными нейронами CA1». Нейрон. 22 (2): 383–394. Дои:10.1016 / S0896-6273 (00) 81098-3. PMID  10069343.
8. Liou, D.-R .; Liou, J.-W .; Liou, C.-Y. (2013). Изучение поведения персептрона. iConcept Press. ISBN  978-1-477554-73-9.
9. Новиков, Альберт Дж. (1963). «О доказательствах сходимости перцептронов». Управление военно-морских исследований.
10. Епископ, Кристофер М. (17 августа 2006 г.). «Глава 4. Линейные модели для классификации». Распознавание образов и машинное обучение. Springer Science + Business Media, LLC. п. 194. ISBN  978-0387-31073-2.
11. Krauth, W .; Мезард М. (1987). «Алгоритмы обучения с оптимальной устойчивостью в нейронных сетях». J. Физики A: Математика. Gen. 20 (11): L745 – L752. Bibcode:1987JPhA ... 20L.745K. Дои:10.1088/0305-4470/20/11/013.
12. Вендемут, А. (1995). «Изучение неизученного». J. Физики A: Математика. Gen. 28 (18): 5423–5436. Bibcode:1995JPhA ... 28,5423 Вт. Дои:10.1088/0305-4470/28/18/030.
13. Anlauf, J. K .; Биль, М. (1989). «AdaTron: алгоритм адаптивного персептрона». Письма еврофизики. 10 (7): 687–692. Bibcode:1989EL ..... 10..687A. Дои:10.1209/0295-5075/10/7/014.
14. McDonald, R .; Холл, К .; Манн, Г. (2010). «Стратегии распределенного обучения для структурированного персептрона» (PDF). Технологии естественного языка: Ежегодная конференция Североамериканского отделения ACL 2010 г.. Ассоциация компьютерной лингвистики. С. 456–464.

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

• Айзерман, М.А., Браверман, Э.М., и Лев И. Розоноэр. Теоретические основы метода потенциальных функций в обучении распознаванию образов. Автоматика и телемеханика, 25: 821–837, 1964.
• Розенблатт, Франк (1958), Персептрон: вероятностная модель хранения и организации информации в мозге, Корнельская авиационная лаборатория, Психологическое обозрение, т. 65, № 6, стр. 386–408. Дои:10,1037 / ч0042519.
• Розенблатт, Франк (1962), Принципы нейродинамики. Вашингтон, округ Колумбия: Спартанские книги.
• Минский М. Л. и Паперт С. А. 1969. Персептроны. Кембридж, Массачусетс: MIT Press.
• Галлант, С. И. (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), основанные на персептронах алгоритмы и анализ, библиотека спектра, Университет Конкордия, Канада

внешняя ссылка

• Персептрон, реализованный в MATLAB для изучения двоичной функции И-НЕ
• Глава 3 Взвешенные сети - перцептрон и глава 4 Обучение персептрону из Нейронные сети - систематическое введение к Рауль Рохас (ISBN  978-3-540-60505-8)
• История перцептронов
• Математика многослойных персептронов
• Визуализируйте обучение нескольких вариантов перцептрона в браузере