Персептрон

Алгоритм контролируемого обучения бинарных классификаторов

В машинном обучении перцептрон (или нейрон Маккаллоха-Питтса ) представляет собой алгоритм контролируемого обучения бинарных классификаторов . Бинарный классификатор — это функция, которая может решить, принадлежит ли входной сигнал, представленный вектором чисел, к какому-то конкретному классу. ^[1] Это тип линейного классификатора , то есть алгоритм классификации, который делает свои прогнозы на основе функции линейного предиктора , объединяющей набор весов с вектором признаков .

История

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

Перцептрон Mark 1, настраиваемый Чарльзом Вайтманом (инженером проекта Mark I Perceptron). ^[3] Сенсорные блоки слева, ассоциативные блоки в центре, а также панель управления и блоки реагирования крайне справа. Панель сенсорных ассоциаций находится за закрытой панелью справа от оператора. Буква «С» на передней панели — индикация текущего состояния сенсорного входа. ^[4]

Персептрон был изобретен в 1943 году Уорреном Маккалоком и Уолтером Питтсом . ^[5] Первой аппаратной реализацией была машина Mark I Perceptron, построенная в 1957 году в Корнеллской авиационной лаборатории Фрэнком Розенблаттом , ^{[6] финансируемая Отделением информационных систем} Управления военно-морских исследований США и Римским центром развития авиации . Впервые он был публично продемонстрирован 23 июня 1960 года. ^[7] Машина была «частью ранее секретной четырехлетней работы NPIC [ Национального центра интерпретации фотографий США ] с 1963 по 1966 год по разработке этого алгоритма в полезный инструмент для фотосъемки. -переводчики». ^[8]

Розенблатт описал детали перцептрона в статье 1958 года. ^[9] Его организация персептрона построена из трех видов клеток («единиц»): AI, AII, R, которые означают « проекцию », «ассоциацию» и «ответ».

Проект Розенблатта финансировался в рамках контракта Nonr-401(40) «Программа исследований когнитивных систем», который длился с 1959 по 1970 год, ^[10] и контракта Nonr-2381(00) «Проект PARA» («PARA» означает «Восприятие и распознавание»). Автоматы»), продолжавшийся с 1957 ^[6] по 1963 год. ^[11]

Машина Марк I Персептрон

Организация биологического мозга и перцептрона.

Перцептрон был задуман как машина, а не программа, и хотя его первая реализация была в программном обеспечении для IBM 704 , впоследствии он был реализован на специально изготовленном оборудовании как «Персептрон Mark I» с названием проекта «Проект PARA». ", ^[12] предназначен для распознавания изображений . В настоящее время машина находится в Смитсоновском национальном музее американской истории . ^[13]

Персептрон Mark I имеет 3 слоя.

• Массив из 400 фотоэлементов , расположенных в сетке 20x20, названных «сенсорными единицами» (S-единицы) или «входной сетчаткой». К каждому S-блоку можно подключить до 40 A-блоков.
• Скрытый слой из 512 перцептронов, названный «ассоциативными единицами» (А-единицы).
• Выходной слой из 8 перцептронов, названных «единицами ответа» (R-единицы).

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

S-блоки подключаются к A-блокам случайным образом (согласно таблице случайных чисел) через коммутационную панель (см. фото), чтобы «устранить какое-либо конкретное преднамеренное смещение в перцептроне». Веса соединений фиксированы, а не изучены. Розенблатт был непреклонен в отношении случайных связей, поскольку он считал, что сетчатка связана со зрительной корой случайным образом, и хотел, чтобы его перцептронная машина напоминала зрительное восприятие человека. ^[14]

Блоки A соединены с блоками R, при этом регулируемые веса закодированы в потенциометрах , а обновление веса во время обучения выполнялось с помощью электродвигателей. ^{[2] : 193} Подробная информация об аппаратном обеспечении приведена в руководстве оператора. ^[12]

Компоненты персептрона Mark I. Из руководства оператора. ^[12]

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

Принципы нейродинамики (1962)

Розенблатт описал свои эксперименты со многими вариантами машины перцептрона в книге « Принципы нейродинамики» (1962). Книга представляет собой опубликованную версию отчета 1961 года. ^[16]

Среди вариантов:

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

Машина была отправлена ​​из Корнелла в Смитсоновский институт в 1967 году по правительственной передаче, администрируемой Управлением военно-морских исследований. ^[8]

Перцептроны (1969)

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

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

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

Последующая работа

Розенблатт продолжал работать над перцептронами, несмотря на сокращение финансирования. Последней попыткой стал Тобермори, построенный между 1961 и 1967 годами и предназначенный для распознавания речи. ^[18] Он занимал целую комнату. ^[19] Он имел 4 слоя с 12 000 весов, реализованных тороидальными магнитными сердечниками . К моменту его завершения моделирование на цифровых компьютерах стало быстрее, чем специально созданные перцептронные машины. ^[20] Он погиб в катастрофе в 1971 году.

Изометрический вид Тобермори, фаза I. ^[19]

Алгоритм ядра персептрона был представлен еще в 1964 году Айзерманом и др. ^[21] Гарантии границ маржи были даны для алгоритма Персептрона в общем неразделимом случае сначала Фрейндом и Шапире (1998), ^[1] и совсем недавно Мори и Ростамизаде (2013), которые расширили предыдущие результаты и дали новые и более благоприятные границы L1. ^{[22] [23]}

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

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

Определение

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

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

${\displaystyle f(\mathbf {x} )=\theta (\mathbf {w} \cdot \mathbf {x} +b)}$

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

Эквивалентно, поскольку мы можем добавить термин смещения в качестве еще одного веса и добавить координату к каждому входу , а затем записать его как линейный классификатор, который передает начало координат: ${\displaystyle \mathbf {w} \cdot \mathbf {x} +b=(\mathbf {w} ,b)\cdot (\mathbf {x} ,1)}$ ${\displaystyle b}$ ${\displaystyle \mathbf {w} _{m+1}}$ ${\displaystyle 1}$ ${\displaystyle \mathbf {x} }$

$${\displaystyle f(\mathbf {x} )=\theta (\mathbf {w} \cdot \mathbf {x} )}$$

Двоичное значение (0 или 1) используется для выполнения двоичной классификации как положительного, так и отрицательного экземпляра. В пространственном отношении смещение меняет положение (но не ориентацию) плоской границы решения . ${\displaystyle f(\mathbf {x} )}$ ${\displaystyle \mathbf {x} }$

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

Представительская власть

Теория информации

С точки зрения теории информации , один перцептрон с K входами имеет емкость 2K бит информации. ^[26] Этот результат принадлежит Томасу Коверу . ^[27]

В частности, пусть это количество способов линейно разделить N точек в K измерениях, тогда ${\displaystyle T(N,K)}$

$${\displaystyle T(N,K)=\left\{{\begin{array}{cc}2^{N}&K\geq N\\2\sum _{k=0}^{K-1}\left({\begin{array}{c}N-1\\k\end{array}}\right)&K<N\end{array}}\right.}$$

K ${\displaystyle T(N,K)/2^{N}}$ ${\displaystyle N\leq 2K}$ ${\displaystyle N>2K}$ ${\displaystyle N\leq 2K}$ ${\displaystyle N>2K}$

Булева функция

При работе только с двоичными входами персептрон называется линейно разделимой булевой функцией или пороговой булевой функцией. Последовательность номеров пороговых булевых функций на n входах — OEIS A000609. Значение известно только с точностью до регистра, но порядок величины известен совершенно точно: у него есть верхняя и нижняя границы . ^[28] ${\displaystyle n=9}$ ${\displaystyle 2^{n^{2}-n\log _{2}n+O(n)}}$ ${\displaystyle 2^{n^{2}-n\log _{2}n-O(n)}}$

Любая булева линейная пороговая функция может быть реализована только с целочисленными весами. Кроме того, количество битов, необходимое и достаточное для представления одного целочисленного весового параметра, равно . ^[28] ${\displaystyle \Theta (n\ln n)}$

Универсальная аппроксимационная теорема

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

Сеть перцептрона с одним скрытым слоем может научиться сколь угодно точно классифицировать любое компактное подмножество. Точно так же он также может сколь угодно точно аппроксимировать любую непрерывную функцию с компактным носителем . По сути, это частный случай теорем Джорджа Цыбенко и Курта Хорника .

Конъюнктивно локальный перцептрон

Перцептроны (Мински и Паперт, 1969) изучали виды сетей перцептронов, необходимые для изучения различных логических функций.

Рассмотрим сеть перцептрона с входными блоками, одним скрытым слоем и одним выходом, аналогичную перцептронной машине Mark I. Он вычисляет логическую функцию типа . Они вызывают конъюнктивно локальную функцию порядка , если существует сеть персептронов, в которой каждый элемент скрытого слоя соединяется не более чем с входными модулями. ${\displaystyle n}$ ${\displaystyle f:2^{n}\to 2}$ ${\displaystyle k}$ ${\displaystyle k}$

Теорема. (Теорема 3.1.1): Функция четности конъюнктивно локальна порядка . ${\displaystyle n}$

Теорема. (раздел 5.5): Функция связности конъюнктивно локальна порядка . ${\displaystyle \Omega (n^{1/2})}$

Алгоритм обучения однослойного перцептрона

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

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

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

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

Определения

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

• ${\displaystyle r}$это скорость обучения перцептрона. Скорость обучения — это положительное число, обычно выбираемое меньше 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}}$— значение th признака th входного обучающего вектора . ${\displaystyle i}$ ${\displaystyle j}$
• ${\displaystyle x_{j,0}=1}$.

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

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

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

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

Шаги

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

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

Сходимость одного перцептрона на линейно разделимом наборе данных

Иллюстрация конвергенции перцептрона. На картинке, . Все точки данных имеют , поскольку отрицательные выборки эквивалентны после отражения через начало координат. По мере обучения вектор весов совершает несколько случайное блуждание в пространстве весов. Каждый шаг отклоняется как минимум на 90 градусов от текущего направления, что увеличивает его норму-квадрат не более чем на . Каждый шаг добавляет к выборке точку, и поскольку все выборки имеют , весовой вектор должен переместиться как минимум на . Поскольку норма растет как, а -компонент растет как , это в конечном итоге приведет к тому, что весовой вектор будет почти полностью указывать в направлении и, таким образом, будет достигнута сходимость. ${\displaystyle \gamma =0.01,R=1,r=1}$ ${\displaystyle y=+1}$ ${\displaystyle y=+1}$ ${\displaystyle R}$ ${\displaystyle w}$ ${\displaystyle x_{1}\geq 0.01}$ ${\displaystyle x_{1}}$ ${\displaystyle 0.01}$ ${\displaystyle {\sqrt {t}}}$ ${\displaystyle x_{1}}$ ${\displaystyle t}$ ${\displaystyle x_{1}}$

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

Линейную разделимость можно проверить во времени , где – количество точек данных, а – размерность каждой точки. ^[29] ${\displaystyle \min(O(n^{d/2}),O(d^{2n}),O(n^{d-1}\ln n))}$ ${\displaystyle n}$ ${\displaystyle d}$

Если обучающее множество линейно разделимо, то персептрон гарантированно сходится после совершения конечного числа ошибок. ^[30] Теорема доказана Розенблаттом и др.

Теорема о сходимости перцептрона  —  Учитывая набор данных , такой , что и он линейно разделяется некоторым единичным вектором , с запасом : ${\textstyle D}$ ${\textstyle \max _{(x,y)\in D}\|x\|_{2}=R}$ ${\textstyle w^{*}}$ ${\textstyle \gamma }$

$${\displaystyle \gamma :=\min _{(x,y)\in D}y(w^{*}\cdot x)}$$

Затем алгоритм обучения персептрона 0-1 сходится после совершения большинства ошибок, для любой скорости обучения и любого метода выборки из набора данных. ${\textstyle (R/\gamma )^{2}}$

Следующее простое доказательство принадлежит Новикову (1962). Идея доказательства состоит в том, что весовой вектор всегда корректируется на ограниченную величину в направлении, с которым он имеет отрицательное скалярное произведение , и, таким образом, может быть ограничен сверху величиной O ( √t ) , где t — количество изменений в вектор веса. Однако его также можно ограничить снизу величиной O ( t ) , поскольку если существует (неизвестный) удовлетворительный весовой вектор, то каждое изменение продвигается в этом (неизвестном) направлении на положительную величину, которая зависит только от входного вектора.

Доказательство

Предположим, что на шаге перцептрон с весом допускает ошибку в точке данных , затем он обновляется до . ${\textstyle t}$ ${\textstyle w_{t}}$ ${\textstyle (x,y)}$ ${\textstyle w_{t+1}=w_{t}+r(y-f_{w_{t}}(x))x}$

Если , аргумент симметричен, поэтому мы его опускаем. ${\textstyle y=0}$

WLOG , , затем , , и . ${\textstyle y=1}$ ${\textstyle f_{w_{t}}(x)=0}$ ${\textstyle f_{w^{*}}(x)=1}$ ${\textstyle w_{t+1}=w_{t}+rx}$

По предположению имеем разделение с полями:

$${\displaystyle w^{*}\cdot x\geq \gamma }$$

Таким образом,

$${\displaystyle w^{*}\cdot w_{t+1}-w^{*}\cdot w_{t}=w^{*}\cdot (rx)\geq r\gamma }$$

Также

$${\displaystyle \|w_{t+1}\|_{2}^{2}-\|w_{t}\|_{2}^{2}=\|w_{t}+rx\|_{2}^{2}-\|w_{t}\|_{2}^{2}=2r(w_{t}\cdot x)+r^{2}\|x\|_{2}^{2}}$$

а так как перцептрон ошибся, и так ${\textstyle w_{t}\cdot x\leq 0}$

$${\displaystyle \|w_{t+1}\|_{2}^{2}-\|w_{t}\|_{2}^{2}\leq \|x\|_{2}^{2}\leq r^{2}R^{2}}$$

Поскольку мы начали с , допустив ошибки, ${\textstyle w_{0}=0}$ ${\textstyle N}$

$${\displaystyle \|w\|_{2}\leq {\sqrt {Nr^{2}R^{2}}}}$$

но и

$${\displaystyle \|w\|_{2}\geq w\cdot w^{*}\geq Nr\gamma }$$

Объединив их, мы имеем ${\textstyle N\leq (R/\gamma )^{2}}$

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

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

Теорема о циклическом использовании перцептрона

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

Теорема о цикле перцептрона  .  Если набор данных имеет только конечное число точек, то существует число верхней границы , такое, что для любого начального весового вектора весь весовой вектор имеет норму, ограниченную ${\displaystyle D}$ ${\displaystyle M}$ ${\displaystyle w_{0}}$ ${\displaystyle w_{t}}$ ${\displaystyle \|w_{t}\|\leq \|w_{0}\|+M}$

Первым это доказал Брэдли Эфрон . ^[34]

Изучение логической функции

Рассмотрим набор данных, в котором взяты из , то есть вершины n-мерного гиперкуба с центром в начале координат, и . То есть все точки данных с положительным значением имеют , и наоборот. Согласно теореме о сходимости перцептрона, перцептрон сходится после совершения большинства ошибок. ${\displaystyle x}$ ${\displaystyle \{-1,+1\}^{n}}$ ${\displaystyle y=\theta (x_{i})}$ ${\displaystyle x_{i}}$ ${\displaystyle y=1}$ ${\displaystyle n}$

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

Эта граница асимптотически точна в наихудшем случае. В худшем случае первый представленный пример совершенно новый и дает биты информации, но каждый последующий пример будет минимально отличаться от предыдущих примеров и дает по 1 биту каждый. После примеров идут биты информации, которых достаточно для перцептрона (с битами информации). ^[26] ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle 2n}$ ${\displaystyle 2n}$

Однако это не является жестким с точки зрения ожидания, если примеры представлены равномерно и случайным образом, поскольку первый будет давать биты, второй биты и так далее, если брать примеры в совокупности. ^[35] ${\displaystyle n}$ ${\displaystyle n/2}$ ${\displaystyle O(\ln n)}$

Варианты

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

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

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

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

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

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

1. Фрейнд, Ю .; Шапире, RE (1999). «Классификация с большой маржой с использованием алгоритма перцептрона» (PDF) . Машинное обучение . 37 (3): 277–296. дои : 10.1023/А:1007662407062 . S2CID  5885617.
2. Бишоп, Кристофер М. (2006). Распознавание образов и машинное обучение . Спрингер. ISBN 0-387-31073-8.
3. Хехт-Нильсен, Роберт (1991). Нейрокомпьютинг (Переиздание с исправлениями под ред.). Ридинг (Массачусетс), Менло-Парк (Калифорния), Нью-Йорк [и др.]: Аддисон-Уэсли. п. 6, подпись к рисунку 1.3. ISBN 978-0-201-09355-1.
4. Блок, HD (1 января 1962 г.). «Персептрон: модель функционирования мозга. I» . Обзоры современной физики . 34 (1): 123–135. doi : 10.1103/RevModPhys.34.123. ISSN  0034-6861.
5. Маккалок, В; Питтс, W (1943). «Логическое исчисление идей, имманентных нервной деятельности». Вестник математической биофизики . 5 (4): 115–133. дои : 10.1007/BF02478259.
6. Розенблатт, Франк (1957). «Персептрон — воспринимающий и распознающий автомат» (PDF) . Отчет 85-460-1 . Корнеллская авиационная лаборатория.
7. Нильссон, Нильс Дж. (2009). «4.2.1. Перцептроны». В поисках искусственного интеллекта. Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-11639-8.
8. О'Коннор, Джек (21 июня 2022 г.). «Алгоритм под прикрытием: секретная глава в ранней истории искусственного интеллекта и спутниковых изображений» . Международный журнал разведки и контрразведки : 1–15. дои : 10.1080/08850607.2022.2073542. ISSN  0885-0607. S2CID  249946000.
9. Розенблатт, Ф. (1958). «Персептрон: вероятностная модель хранения и организации информации в мозге» . Психологический обзор . 65 (6): 386–408. дои : 10.1037/h0042519. ISSN  1939-1471.
10. Розенблатт, Фрэнк и КОРНЕЛЛСКИЙ УНИВЕРСИТЕТ ИТАКИ, НЬЮ-ЙОРК. Программа исследований когнитивных систем. Технический отчет, Корнелльский университет, 72, 1971 г.
11. Мюерле, Джон Людвиг и CORNELL AERONAUICAL LAB INC BUFFALO NY. Проект Пара, Автоматы восприятия и распознавания . Корнельская авиационная лаборатория, Инкорпорейтед, 1963 год.
12. Хэй, Джон Кэмерон (1960). Руководство оператора перцептрона Mark I (Проект PARA) / (PDF) . Буффало: Корнеллская авиационная лаборатория.
13. «Персептрон, Марк I». Национальный музей американской истории . Проверено 30 октября 2023 г.
14. Андерсон, Джеймс А.; Розенфельд, Эдвард, ред. (2000). Говорящие сети: устная история нейронных сетей. Массачусетский технологический институт Пресс. дои : 10.7551/mitpress/6626.003.0004. ISBN 978-0-262-26715-1.
15. Олазаран, Микель (1996). «Социологическое исследование официальной истории спора о перцептронах». Социальные исследования науки . 26 (3): 611–659. дои : 10.1177/030631296026003005. JSTOR  285702. S2CID  16786738.
16. Принципы нейродинамики: перцептроны и теория механизмов мозга , Фрэнк Розенблатт, номер отчета VG-1196-G-8, Корнельская авиационная лаборатория, опубликовано 15 марта 1961 года. Работа, представленная в этом томе, была выполнена по контракту. Nonr-2381 (00) (Проект PARA) в CAL и контракт Nonr-401 (40) в Корнельском университете.
17. Сейновски, Терренс Дж. (2018). Революция глубокого обучения. МТИ Пресс. п. 47. ИСБН 978-0-262-03803-4.
18. Розенблатт, Франк (1962). « Описание персептрона Тобермори ». Программа когнитивных исследований. Отчет № 4. Сборник технических статей, Том. 2. Под редакцией Фрэнка Розенблатта. Итака, Нью-Йорк: Корнельский университет.
19. Надь, Джордж. 1963. Системные и схемные решения перцептрона Тобермори . Технический отчет № 5, Программа исследований когнитивных систем, Корнелльский университет, Итака, Нью-Йорк.
20. Надь, Джордж. «Нейронные сети – тогда и сейчас». Транзакции IEEE в нейронных сетях 2.2 (1991): 316–318.
21. Айзерман, Массачусетс; Браверман, Э.М.; Розоноер, Л.И. (1964). «Теоретические основы метода потенциальных функций в обучении распознаванию образов». Автоматизация и дистанционное управление . 25 : 821–837.
22. Мори, Мехриар; Ростамизаде, Афшин (2013). «Границы ошибок перцептрона». arXiv : 1305.0208 [cs.LG].
23. [1] Основы машинного обучения, MIT Press (глава 8).
24. Кэш, Сидней; Юсте, Рафаэль (1999). «Линейное суммирование возбуждающих сигналов пирамидальными нейронами CA1». Нейрон . 22 (2): 383–394. дои : 10.1016/S0896-6273(00)81098-3 . ПМИД  10069343.
25. Лиу, Д.-Р.; Лиу, Ж.-В.; Лиу, К.-Ю. (2013). Изучение поведения перцептрона . АйКонцепт Пресс. ISBN 978-1-477554-73-9.
26. Маккей, Дэвид (25 сентября 2003 г.). Теория информации, логический вывод и алгоритмы обучения. Издательство Кембриджского университета . п. 483. ИСБН 9780521642989.
27. Обложка, Томас М. (июнь 1965 г.). «Геометрические и статистические свойства систем линейных неравенств с приложениями в распознавании образов» . Транзакции IEEE на электронных компьютерах . EC-14 (3): 326–334. дои : 10.1109/PGEC.1965.264137. ISSN  0367-7508.
28. Шима, Иржи; Орпонен, Пекка (1 декабря 2003 г.). «Универсальные вычисления с нейронными сетями: обзор результатов теории сложности». Нейронные вычисления . 15 (12): 2727–2778. дои : 10.1162/089976603322518731. ISSN  0899-7667.
29. «Введение в машинное обучение, Глава 3: Перцептрон». openlearninglibrary.mit.edu . Проверено 27 октября 2023 г.
30. Новикофф, Альберт Дж. (1963). «О доказательствах сходимости перцептронов». Управление военно-морских исследований .
31. Бишоп, Кристофер М. (17 августа 2006 г.). «Глава 4. Линейные модели классификации». Распознавание образов и машинное обучение . Спрингер Сайенс+Бизнес Медиа, ООО. п. 194. ИСБН 978-0387-31073-2.
32. Краут, В.; Мезард, М. (1987). «Алгоритмы обучения оптимальной устойчивости в нейронных сетях». Журнал физики A: Математический и общий . 20 (11): Л745–Л752. Бибкод : 1987JPhA...20L.745K. дои : 10.1088/0305-4470/20/11/013.
33. Блок, HD; Левин, С.А. (1970). «Об ограниченности итерационной процедуры решения системы линейных неравенств». Труды Американского математического общества . 26 (2): 229–235. дои : 10.1090/S0002-9939-1970-0265383-5 . ISSN  0002-9939.
34. Эфрон, Брэдли. «Процедура коррекции перцептрона в неразделимых ситуациях». Римское авиационное подразделение. Центр Тех. Док. Репт (1964).
35. Саймон, Герберт А.; Лэрд, Джон Э. (13 августа 2019 г.). «Ограничения скорости достижения концепции». «Науки об искусственном», переиздание третьего издания с новым введением Джона Лэрда (переиздание). Кембридж, Массачусетс, Лондон, Англия: MIT Press. ISBN 978-0-262-53753-7.
36. Вендемут, А. (1995). «Изучение необъяснимого». Журнал физики A: Математический и общий . 28 (18): 5423–5436. Бибкод : 1995JPhA...28.5423W. дои : 10.1088/0305-4470/28/18/030.
37. Анлауф, Дж. К.; Биль, М. (1989). «АдаТрон: алгоритм адаптивного перцептрона». Письма по еврофизике . 10 (7): 687–692. Бибкод : 1989EL.....10..687A. дои : 10.1209/0295-5075/10/7/014. S2CID  250773895.
38. Макдональд, Р.; Холл, К.; Манн, Г. (2010). «Стратегии распределенного обучения для структурированного перцептрона» (PDF) . Технологии человеческого языка: Ежегодная конференция Североамериканского отделения ACL 2010 года . Ассоциация компьютерной лингвистики. стр. 456–464.

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

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

Внешние ссылки

• Персептрон, реализованный в MATLAB для изучения двоичной функции NAND.
• Глава 3 Взвешенные сети — перцептрон и глава 4 Перцептронное обучение нейронных сетей — систематическое введение Рауля Рохаса ( ISBN 978-3-540-60505-8 ) 
• История перцептронов
• Математика многослойных перцептронов
• Применение модели перцептрона с помощью scikit-learn — https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.Perceptron.html