В машинном обучении перцептрон (или нейрон Маккаллоха-Питтса ) представляет собой алгоритм контролируемого обучения бинарных классификаторов . Бинарный классификатор — это функция, которая может решить, принадлежит ли входной сигнал, представленный вектором чисел, к какому-то конкретному классу. [1] Это тип линейного классификатора , то есть алгоритм классификации, который делает свои прогнозы на основе функции линейного предиктора , объединяющей набор весов с вектором признаков .
Персептрон был изобретен в 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]
Перцептрон был задуман как машина, а не программа, и хотя его первая реализация была в программном обеспечении для IBM 704 , впоследствии он был реализован на специально изготовленном оборудовании как «Персептрон Mark I» с названием проекта «Проект PARA». ", [12] предназначен для распознавания изображений . В настоящее время машина находится в Смитсоновском национальном музее американской истории . [13]
Персептрон Mark I имеет 3 слоя.
Розенблатт назвал эту трехслойную сеть перцептрона альфа-перцептроном , чтобы отличить ее от других моделей перцептрона, с которыми он экспериментировал. [7]
S-блоки подключаются к A-блокам случайным образом (согласно таблице случайных чисел) через коммутационную панель (см. фото), чтобы «устранить какое-либо конкретное преднамеренное смещение в перцептроне». Веса соединений фиксированы, а не изучены. Розенблатт был непреклонен в отношении случайных связей, поскольку он считал, что сетчатка связана со зрительной корой случайным образом, и хотел, чтобы его перцептронная машина напоминала зрительное восприятие человека. [14]
Блоки A соединены с блоками R, при этом регулируемые веса закодированы в потенциометрах , а обновление веса во время обучения выполнялось с помощью электродвигателей. [2] : 193 Подробная информация об аппаратном обеспечении приведена в руководстве оператора. [12]
На пресс-конференции 1958 года, организованной ВМС США, Розенблатт сделал заявления о перцептроне, вызвавшие горячие споры среди молодого сообщества ИИ ; Основываясь на заявлениях Розенблатта, газета «Нью-Йорк Таймс» сообщила, что перцептрон является «зародышем электронного компьютера, который, как ожидает [ВМФ], сможет ходить, говорить, видеть, писать, воспроизводить себя и осознавать свое существование». [15]
Розенблатт описал свои эксперименты со многими вариантами машины перцептрона в книге « Принципы нейродинамики» (1962). Книга представляет собой опубликованную версию отчета 1961 года. [16]
Среди вариантов:
Машина была отправлена из Корнелла в Смитсоновский институт в 1967 году по правительственной передаче, администрируемой Управлением военно-морских исследований. [8]
Хотя поначалу перцептрон казался многообещающим, быстро было доказано, что перцептроны невозможно научить распознавать многие классы шаблонов. Это привело к стагнации области исследований нейронных сетей на многие годы, прежде чем было признано, что нейронная сеть прямого распространения с двумя или более слоями (также называемая многослойным перцептроном ) имеет большую вычислительную мощность, чем перцептроны с одним слоем (также называемые однослойным перцептроном). слой перцептрона ).
Однослойные перцептроны способны изучать только линейно разделимые шаблоны. [17] Для задачи классификации с некоторой функцией пошаговой активации один узел будет иметь одну линию, разделяющую точки данных, образующие шаблоны. Больше узлов может создать больше разделительных линий, но эти линии необходимо каким-то образом объединить, чтобы сформировать более сложную классификацию. Второго слоя перцептронов или даже линейных узлов достаточно для решения многих неразделимых иначе проблем.
В 1969 году знаменитая книга Марвина Мински и Сеймура Пейперта под названием «Персептроны» показала, что эти классы сетей не могут изучить функцию XOR . Часто полагают (ошибочно), что они также предполагали, что аналогичный результат справедлив и для многослойной перцептронной сети. Однако это неправда, поскольку и Мински, и Паперт уже знали, что многослойные перцептроны способны создавать функцию XOR. (Для получения дополнительной информации см. страницу «Персептроны» (книга) .) Тем не менее, текст Мински/Пейперта, который часто неправильно трактуют, вызвал значительное снижение интереса и финансирования исследований нейронных сетей. Прошло еще десять лет, прежде чем в 1980-х годах исследования нейронных сетей возобновились. [17] Этот текст был переиздан в 1987 году как «Персептроны – Расширенное издание», где показаны и исправлены некоторые ошибки в исходном тексте.
Розенблатт продолжал работать над перцептронами, несмотря на сокращение финансирования. Последней попыткой стал Тобермори, построенный между 1961 и 1967 годами и предназначенный для распознавания речи. [18] Он занимал целую комнату. [19] Он имел 4 слоя с 12 000 весов, реализованных тороидальными магнитными сердечниками . К моменту его завершения моделирование на цифровых компьютерах стало быстрее, чем специально созданные перцептронные машины. [20] Он погиб в катастрофе в 1971 году.
Алгоритм ядра персептрона был представлен еще в 1964 году Айзерманом и др. [21] Гарантии границ маржи были даны для алгоритма Персептрона в общем неразделимом случае сначала Фрейндом и Шапире (1998), [1] и совсем недавно Мори и Ростамизаде (2013), которые расширили предыдущие результаты и дали новые и более благоприятные границы L1. [22] [23]
Персептрон — это упрощенная модель биологического нейрона . Хотя для полного понимания поведения нейронов часто требуется сложность моделей биологических нейронов , исследования показывают, что линейная модель, подобная перцептрону, может воспроизводить некоторое поведение, наблюдаемое в реальных нейронах. [24]
Пространства решений границ решения для всех бинарных функций и поведения обучения изучаются в [25] .
В современном смысле персептрон — это алгоритм обучения двоичному классификатору, называемому пороговой функцией : функция, которая сопоставляет свой вход ( вектор с действительным знаком ) с выходным значением (одиночное двоичное значение):
где – ступенчатая функция Хевисайда , – вектор действительных весов, – скалярное произведение , где m – количество входов в персептрон, а b – смещение . Смещение смещает границу решения от начала координат и не зависит ни от какого входного значения.
Эквивалентно, поскольку мы можем добавить термин смещения в качестве еще одного веса и добавить координату к каждому входу , а затем записать его как линейный классификатор, который передает начало координат:
Двоичное значение (0 или 1) используется для выполнения двоичной классификации как положительного, так и отрицательного экземпляра. В пространственном отношении смещение меняет положение (но не ориентацию) плоской границы решения .
В контексте нейронных сетей перцептрон — это искусственный нейрон , использующий ступенчатую функцию Хевисайда в качестве функции активации. Алгоритм персептрона также называют однослойным персептроном , чтобы отличить его от многослойного персептрона , который является неправильным названием для более сложной нейронной сети. В качестве линейного классификатора однослойный перцептрон представляет собой простейшую нейронную сеть прямого распространения .
С точки зрения теории информации , один перцептрон с K входами имеет емкость 2K бит информации. [26] Этот результат принадлежит Томасу Коверу . [27]
В частности, пусть это количество способов линейно разделить N точек в K измерениях, тогда
При работе только с двоичными входами персептрон называется линейно разделимой булевой функцией или пороговой булевой функцией. Последовательность номеров пороговых булевых функций на n входах — OEIS A000609. Значение известно только с точностью до регистра, но порядок величины известен совершенно точно: у него есть верхняя и нижняя границы . [28]
Любая булева линейная пороговая функция может быть реализована только с целочисленными весами. Кроме того, количество битов, необходимое и достаточное для представления одного целочисленного весового параметра, равно . [28]
Один персептрон может научиться классифицировать любое полупространство. Он не может решить никакие линейно неразделимые векторы, такие как булева проблема «исключающее ИЛИ» (знаменитая «проблема XOR»).
Сеть перцептрона с одним скрытым слоем может научиться сколь угодно точно классифицировать любое компактное подмножество. Точно так же он также может сколь угодно точно аппроксимировать любую непрерывную функцию с компактным носителем . По сути, это частный случай теорем Джорджа Цыбенко и Курта Хорника .
Перцептроны (Мински и Паперт, 1969) изучали виды сетей перцептронов, необходимые для изучения различных логических функций.
Рассмотрим сеть перцептрона с входными блоками, одним скрытым слоем и одним выходом, аналогичную перцептронной машине Mark I. Он вычисляет логическую функцию типа . Они вызывают конъюнктивно локальную функцию порядка , если существует сеть персептронов, в которой каждый элемент скрытого слоя соединяется не более чем с входными модулями.
Теорема. (Теорема 3.1.1): Функция четности конъюнктивно локальна порядка .
Теорема. (раздел 5.5): Функция связности конъюнктивно локальна порядка .
Ниже приведен пример алгоритма обучения однослойного перцептрона с одним выходным блоком. Для однослойного перцептрона с несколькими выходными блоками, поскольку веса одного выходного блока полностью отделены от всех остальных, один и тот же алгоритм можно запустить для каждого выходного блока.
Для многослойных перцептронов , где существует скрытый слой, необходимо использовать более сложные алгоритмы, такие как обратное распространение ошибки . Если функция активации или основной процесс, моделируемый перцептроном, нелинейны , можно использовать альтернативные алгоритмы обучения, такие как дельта-правило, при условии, что функция активации дифференцируема . Тем не менее, алгоритм обучения, описанный ниже, часто работает даже для многослойных персептронов с нелинейными функциями активации.
Когда несколько перцептронов объединяются в искусственную нейронную сеть, каждый выходной нейрон работает независимо от всех остальных; таким образом, изучение каждого результата можно рассматривать изолированно.
Сначала мы определяем некоторые переменные:
Мы показываем значения функций следующим образом:
Чтобы представить веса:
Чтобы показать зависимость от времени , мы используем:
Алгоритм обновляет веса после каждой обучающей выборки на шаге 2b.
Одиночный персептрон представляет собой линейный классификатор . Он может достичь стабильного состояния только в том случае, если все входные векторы правильно классифицированы. В случае, если обучающий набор D не является линейно разделимым , т. е. если положительные примеры не могут быть отделены от отрицательных примеров гиперплоскостью, то алгоритм не будет сходиться, поскольку решения нет. Следовательно, если линейная отделимость обучающего набора априори неизвестна, следует использовать один из приведенных ниже вариантов обучения. Подробный анализ и расширения теоремы о сходимости приведены в главе 11 книги «Персептроны» (1969).
Линейную разделимость можно проверить во времени , где – количество точек данных, а – размерность каждой точки. [29]
Если обучающее множество линейно разделимо, то персептрон гарантированно сходится после совершения конечного числа ошибок. [30] Теорема доказана Розенблаттом и др.
Теорема о сходимости перцептрона — Учитывая набор данных , такой , что и он линейно разделяется некоторым единичным вектором , с запасом :
Затем алгоритм обучения персептрона 0-1 сходится после совершения большинства ошибок, для любой скорости обучения и любого метода выборки из набора данных.
Следующее простое доказательство принадлежит Новикову (1962). Идея доказательства состоит в том, что весовой вектор всегда корректируется на ограниченную величину в направлении, с которым он имеет отрицательное скалярное произведение , и, таким образом, может быть ограничен сверху величиной O ( √t ) , где t — количество изменений в вектор веса. Однако его также можно ограничить снизу величиной O ( t ) , поскольку если существует (неизвестный) удовлетворительный весовой вектор, то каждое изменение продвигается в этом (неизвестном) направлении на положительную величину, которая зависит только от входного вектора.
Предположим, что на шаге перцептрон с весом допускает ошибку в точке данных , затем он обновляется до .
Если , аргумент симметричен, поэтому мы его опускаем.
WLOG , , затем , , и .
По предположению имеем разделение с полями:
Также
Поскольку мы начали с , допустив ошибки,
Объединив их, мы имеем
Хотя алгоритм перцептрона гарантированно сходится к некоторому решению в случае линейно разделимого обучающего набора, он все равно может выбрать любое решение, и проблемы могут допускать множество решений различного качества. [31] Для решения этой проблемы был разработан перцептрон оптимальной устойчивости, ныне более известный как линейная машина опорных векторов (Krauth and Mezard , 1987 ) . [32]
Когда набор данных не является линейно разделимым, единый перцептрон не может сойтись. Однако у нас еще есть [33]
Теорема о цикле перцептрона . Если набор данных имеет только конечное число точек, то существует число верхней границы , такое, что для любого начального весового вектора весь весовой вектор имеет норму, ограниченную
Первым это доказал Брэдли Эфрон . [34]
Рассмотрим набор данных, в котором взяты из , то есть вершины n-мерного гиперкуба с центром в начале координат, и . То есть все точки данных с положительным значением имеют , и наоборот. Согласно теореме о сходимости перцептрона, перцептрон сходится после совершения большинства ошибок.
Если бы мы написали логическую программу для выполнения одной и той же задачи, каждый положительный пример показал бы, что одна из координат является правильной, а каждый отрицательный пример показал бы, что ее дополнение является положительным примером. Собрав все известные положительные примеры, мы в конечном итоге исключаем все координаты, кроме одной, после чего набор данных изучается. [35]
Эта граница асимптотически точна в наихудшем случае. В худшем случае первый представленный пример совершенно новый и дает биты информации, но каждый последующий пример будет минимально отличаться от предыдущих примеров и дает по 1 биту каждый. После примеров идут биты информации, которых достаточно для перцептрона (с битами информации). [26]
Однако это не является жестким с точки зрения ожидания, если примеры представлены равномерно и случайным образом, поскольку первый будет давать биты, второй биты и так далее, если брать примеры в совокупности. [35]
Карманный алгоритм с храповым механизмом (Gallant, 1990) решает проблему стабильности обучения перцептрона, сохраняя лучшее из виденных до сих пор решений «в кармане». Затем карманный алгоритм возвращает решение в кармане, а не последнее решение. Его также можно использовать для неразделимых наборов данных, где цель состоит в том, чтобы найти персептрон с небольшим количеством ошибочных классификаций. Однако эти решения появляются чисто стохастически, и, следовательно, карманный алгоритм не приближается к ним постепенно в ходе обучения и не гарантирует их появление в течение заданного количества шагов обучения.
Алгоритм Максовера (Вендемут, 1995) является «надежным» в том смысле, что он сходится независимо от (предварительного) знания о линейной разделимости набора данных. [36] В линейно разделимом случае это позволит решить задачу обучения – при желании даже с оптимальной стабильностью ( максимальным запасом между классами). Для неразделимых наборов данных он вернет решение с небольшим количеством ошибок классификации. Во всех случаях алгоритм в процессе обучения постепенно приближается к решению, без запоминания предыдущих состояний и без стохастических скачков. Сходимость заключается в глобальной оптимальности для разделимых наборов данных и в локальной оптимальности для неразделимых наборов данных.
Голосуемый перцептрон (Freund and Schapire, 1999) представляет собой вариант, использующий несколько взвешенных перцептронов. Алгоритм запускает новый перцептрон каждый раз, когда пример неправильно классифицирован, инициализируя вектор весов окончательными весами последнего перцептрона. Каждому перцептрону также будет присвоен другой вес, соответствующий тому, сколько примеров он правильно классифицирует, прежде чем ошибочно классифицирует один, и в конце результатом будет взвешенное голосование по всем перцептронам.
В разделимых задачах обучение персептрона также может быть направлено на поиск наибольшего разделительного разрыва между классами. Так называемый перцептрон оптимальной устойчивости может быть определен с помощью итеративных схем обучения и оптимизации, таких как алгоритм Min-Over (Krauth и Mezard, 1987) [32] или AdaTron (Anlauf and Biehl, 1989)). [37] AdaTron использует тот факт, что соответствующая задача квадратичной оптимизации является выпуклой. Персептрон оптимальной устойчивости вместе с трюком ядра являются концептуальными основами машины опорных векторов .
-перцептрон дополнительно использовал уровень предварительной обработки фиксированных случайных весов с пороговыми единицами вывода. Это позволило перцептрону классифицировать аналоговые закономерности, проецируя их в двоичное пространство . Фактически, для проекционного пространства достаточно высокой размерности шаблоны могут стать линейно разделимыми.
Другой способ решения нелинейных задач без использования нескольких слоев — использовать сети более высокого порядка (модуль сигма-пи). В сети этого типа каждый элемент входного вектора расширяется каждой попарной комбинацией умноженных входов (второй порядок). Это можно распространить на сеть n -порядка.
Однако следует иметь в виду, что лучший классификатор – это не обязательно тот, который идеально классифицирует все обучающие данные. Действительно, если бы у нас было предварительное ограничение, согласно которому данные поступают из эквивариантных гауссовых распределений, линейное разделение во входном пространстве является оптимальным, а нелинейное решение переоснащается .
Другие алгоритмы линейной классификации включают Winnow , машину опорных векторов и логистическую регрессию .
Как и большинство других методов обучения линейных классификаторов, перцептрон естественным образом обобщается на многоклассовую классификацию . Здесь входные и выходные данные извлекаются из произвольных наборов. Функция представления признаков сопоставляет каждую возможную пару ввода/вывода с конечномерным вектором признаков с действительным знаком. Как и раньше, вектор признаков умножается на вектор весов , но теперь полученная оценка используется для выбора среди множества возможных выходных данных:
При повторном обучении повторяются примеры, прогнозируя результат для каждого, оставляя веса неизменными, когда прогнозируемый результат соответствует целевому, и изменяя их, когда это не так. Обновление становится:
Эта формулировка многоклассовой обратной связи сводится к исходному персептрону, когда - вектор с действительным знаком, выбранный из , и .
Для определенных задач представления и функции ввода/вывода могут быть выбраны так, чтобы их можно было эффективно найти, даже если они выбраны из очень большого или даже бесконечного набора.
С 2002 года обучение персептроном стало популярным в области обработки естественного языка для таких задач, как разметка частей речи и синтаксический анализ (Коллинз, 2002). Он также применялся для решения крупномасштабных задач машинного обучения в условиях распределенных вычислений . [38]