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

Введение

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

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

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

С точки зрения теории информации, один перцептрон с K входами имеет емкость 2K бит информации. Этот результат принадлежит Томасу Коверу. В частности, пусть – число способов линейно разделить N точек в K измерениях, тогда при больших K, очень близко к единице, когда , но очень близко к нулю, когда . Иными словами, один перцептрон почти наверняка может запомнить случайное присвоение двоичных меток N точкам, когда , но почти наверняка не может, когда .

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

При работе только с бинарными входами перцептрон называется линейно разделяемой булевой функцией или пороговой булевой функцией. Последовательность чисел пороговых булевых функций на n входах соответствует OEIS A000609. Значение известно точно лишь для небольшого числа случаев, но порядок величины известен достаточно точно: он имеет верхнюю и нижнюю границы. Любую булеву линейную пороговую функцию можно реализовать, используя только целочисленные веса. Более того, количество бит, необходимое и достаточное для представления одного параметра веса, является целым числом. Если обучающий набор линейно разделяем, то перцептрон гарантированно сойдется после совершения конечного числа ошибок. Теорема доказана Розенблатом и др. Следующее простое доказательство приведено Новиковым (1962). Идея доказательства заключается в том, что вектор весов всегда корректируется на ограниченную величину в направлении, с которым он имеет отрицательное скалярное произведение, и, таким образом, может быть ограничен сверху , где t – число изменений вектора весов. Однако, он также может быть ограничен снизу как O(t), поскольку, если существует (неизвестный) удовлетворительный вектор весов, то каждое изменение приближает к нему на положительную величину, зависящую только от входного вектора. thumb|300px|Два класса точек и две из бесконечного множества линейных границ, разделяющих их. Даже если границы расположены почти под прямым углом друг к другу, алгоритм перцептрона не может выбрать между ними. Хотя алгоритм перцептрона гарантированно сходится к некоторому решению в случае линейно разделяемого обучающего набора, он все равно может выбрать любое решение, и для задач может существовать множество решений различного качества. Перцептрон оптимальной устойчивости, ныне более известный как линейная опорная векторная машина, был разработан для решения этой проблемы (Krauth и Mezard, 1987).

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

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

Изучение булевой функции

Рассмотрим набор данных, где элементы принадлежат , то есть являются вершинами n-мерного гиперкуба, центрированного в начале координат, и . То есть, все точки данных с положительным имеют , и наоборот. Согласно теореме о сходимости перцептрона, перцептрон сойдется после совершения не более ошибок. Если бы мы написали логическую программу для выполнения той же задачи, каждый положительный пример показывал бы, что одна из координат является правильной, а каждый отрицательный пример – что ее дополнение является положительным примером. Собирая все известные положительные примеры, мы в конечном итоге исключим все, кроме одной координаты, в этот момент набор данных будет изучен. Эта граница асимптотически точна в худшем случае. В худшем случае, первый представленный пример будет совершенно новым и предоставит битов информации, но каждый последующий пример будет минимально отличаться от предыдущих и предоставит по 1 биту каждый. После примеров будет доступно битов информации, чего достаточно для перцептрона (с битами информации). В случае линейной разделимости, он решит задачу обучения – при желании даже с оптимальной устойчивостью (максимальным зазором между классами). Для неразделимых наборов данных он вернет решение с небольшим количеством ошибок классификации. Во всех случаях алгоритм постепенно приближается к решению в процессе обучения, не запоминая предыдущие состояния и не совершая стохастических скачков. Сходимость гарантирует глобальную оптимальность для разделимых наборов данных и локальную оптимальность для неразделимых наборов данных. Voted Perceptron (Freund и Schapire, 1999) – это вариант, использующий несколько взвешенных перцептронов. Алгоритм запускает новый перцептрон каждый раз, когда пример классифицируется неверно, инициализируя вектор весов конечными весами последнего перцептрона. Каждому перцептрону также присваивается вес, соответствующий количеству примеров, которые он правильно классифицирует до первой ошибки, и в конце выдается взвешенное голосование всех перцептронов. В задачах линейной разделимости обучение перцептрона может быть направлено на поиск максимального разделительного зазора между классами. Так называемый перцептрон оптимальной устойчивости можно определить с помощью итеративных схем обучения и оптимизации, таких как алгоритм Min Over (Krauth и Mezard, 1987). AdaTron использует тот факт, что соответствующая задача квадратичной оптимизации является выпуклой. Перцептрон оптимальной устойчивости, вместе с методом ядер, являются концептуальной основой метода опорных векторов. Перцептрон также использовал предварительный слой обработки с фиксированными случайными весами и пороговыми выходными элементами. Это позволило перцептрону классифицировать аналоговые шаблоны, проецируя их в двоичное пространство. Фактически, для проекционного пространства достаточно высокой размерности шаблоны могут стать линейно разделимыми. Другой способ решения нелинейных задач без использования нескольких слоев – использование сетей высшего порядка (sigma-pi unit). В этом типе сети каждый элемент входного вектора расширяется каждой попарной комбинацией перемноженных входов (второго порядка). Это можно расширить до сети n-го порядка. Однако следует помнить, что лучший классификатор не обязательно тот, который идеально классифицирует все обучающие данные. Действительно, если бы у нас было априорное ограничение, что данные поступают из эквивариантных гауссовских распределений, линейное разделение во входном пространстве является оптимальным, а нелинейное решение приводит к переобучению. Другие алгоритмы линейной классификации включают Winnow, метод опорных векторов и логистическую регрессию.

Consider a dataset where the are from , that is, the vertices of an n dimensional hypercube centered at origin, and That is, all data points with positive have , and vice versa. By the perceptron convergence theorem, a perceptron would converge after making at most mistakes. If we were to write a logical program to perform the same task, each positive example shows that one of the coordinates is the right one, and each negative example shows that its complement is a positive example. By collecting all the known positive examples, we eventually eliminate all but one coordinate, at which point the dataset is learned. This bound is asymptotically tight in terms of the worst case. In the worst case, the first presented example is entirely new, and gives bits of information, but each subsequent example would differ minimally from previous examples, and gives 1 bit each. After examples, there are bits of information, which is sufficient for the perceptron (with bits of information). In the linearly separable case, it will solve the training problem – if desired, even with optimal stability (maximum margin between the classes). For non separable data sets, it will return a solution with a small number of misclassifications. In all cases, the algorithm gradually approaches the solution in the course of learning, without memorizing previous states and without stochastic jumps. Convergence is to global optimality for separable data sets and to local optimality for non separable data sets. The Voted Perceptron (Freund and Schapire, 1999), is a variant using multiple weighted perceptrons. The algorithm starts a new perceptron every time an example is wrongly classified, initializing the weights vector with the final weights of the last perceptron. Each perceptron will also be given another weight corresponding to how many examples do they correctly classify before wrongly classifying one, and at the end the output will be a weighted vote on all perceptrons. In separable problems, perceptron training can also aim at finding the largest separating margin between the classes. The so called perceptron of optimal stability can be determined by means of iterative training and optimization schemes, such as the Min Over algorithm (Krauth and Mezard, 1987) AdaTron uses the fact that the corresponding quadratic optimization problem is convex. The perceptron of optimal stability, together with the kernel trick, are the conceptual foundations of the support vector machine. The perceptron further used a pre processing layer of fixed random weights, with thresholded output units. This enabled the perceptron to classify analogue patterns, by projecting them into a binary space. In fact, for a projection space of sufficiently high dimension, patterns can become linearly separable. Another way to solve nonlinear problems without using multiple layers is to use higher order networks (sigma pi unit). In this type of network, each element in the input vector is extended with each pairwise combination of multiplied inputs (second order). This can be extended to an n order network. It should be kept in mind, however, that the best classifier is not necessarily that which classifies all the training data perfectly. Indeed, if we had the prior constraint that the data come from equi variant Gaussian distributions, the linear separation in the input space is optimal, and the nonlinear solution is overfitted. Other linear classification algorithms include Winnow, support vector machine, and logistic regression.

Перцептрон многоклассный

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

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

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