Ядро персептрона

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

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

Алгоритм перцептрона

Основная статья: Персептрон

Алгоритм персептрона — это алгоритм онлайн-обучения , который работает по принципу, называемому «обучение на основе ошибок». Он итеративно улучшает модель, запуская ее на обучающих выборках, а затем обновляя модель всякий раз, когда обнаруживает, что она выполнила неверную классификацию по отношению к контролируемому сигналу. Модель, изучаемая стандартным алгоритмом перцептрона, представляет собой линейный двоичный классификатор: вектор весов w (и, возможно, член-термин b , опущенный здесь для простоты), который используется для классификации вектора выборки x как класса «один» или класса «минус». один» согласно

${\hat {y}}=\operatorname {sgn}(\mathbf {w} ^{\top }\mathbf {x} )$

где ноль произвольно отображается в единицу или минус единицу. (Шляпа на ŷ обозначает приблизительную стоимость.)

В псевдокоде алгоритм перцептрона задается следующим образом:

Инициализируйте w нулевым вектором длины p , количества предикторов (функций).

Для некоторого фиксированного количества итераций или до тех пор, пока не будет выполнен некоторый критерий остановки:

Для каждого обучающего примера x _i с основной меткой истинности y _i ∈ {-1, 1 }:

Пусть ŷ = sn( w ^Т х _я ) .

Если ŷ ≠ y _i , обновить w ← w + y _i x _i .

Методы ядра

Основная статья: Методы ядра

В отличие от линейных моделей, изучаемых перцептроном, метод ядра — это классификатор, который хранит подмножество своих обучающих примеров x _i , связывает с каждым весовой коэффициент α _i и принимает решения для новых образцов x' путем оценки

$\operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )$.

Здесь K — некоторая функция ядра. Формально функция ядра — это неотрицательное полуопределенное ядро ​​(см. условие Мерсера ), представляющее внутренний продукт между выборками в многомерном пространстве, как если бы выборки были расширены для включения дополнительных признаков с помощью функции Φ : K ( x , Икс' ) = Φ( Икс ) · Φ( Икс' ) . Интуитивно это можно рассматривать как функцию сходства между выборками, поэтому машина ядра устанавливает класс новой выборки путем взвешенного сравнения с обучающим набором. Каждая функция x' ↦ K ( x _i , x' ) служит базовой функцией в классификации.

Алгоритм

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

$\mathbf {w} =\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}$

где α _i — количество раз, когда x _i был неправильно классифицирован, что привело к обновлению w ← w + y _i x _i . Используя этот результат, мы можем сформулировать алгоритм двойного персептрона, который, как и раньше, проходит по выборкам, делая прогнозы, но вместо сохранения и обновления вектора весов w он обновляет вектор «счетчика ошибок» α . Мы также должны переписать формулу прогнозирования, чтобы избавиться от w :

${\begin{aligned}{\hat {y}}&=\operatorname {sgn}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} )\\&=\operatorname {sgn} \left(\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}\right)^{\mathsf {T}}\mathbf {x} \\&=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}(\mathbf {x} _{i}\cdot \mathbf {x} )\end{aligned}}$

Включение этих двух уравнений в цикл обучения превращает его в алгоритм двойного персептрона .

Наконец, мы можем заменить скалярное произведение в двойном перцептроне произвольной функцией ядра, чтобы получить эффект карты признаков Φ без явного вычисления Φ( x ) для любых выборок. В результате получается алгоритм ядра перцептрона:

Инициализируйте α вектором из всех нулей длины n , количества обучающих выборок.

Для некоторого фиксированного количества итераций или до тех пор, пока не будет выполнен некоторый критерий остановки:

Для каждого обучающего примера x _j , y _j :

Позволять ${\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})$

Если ŷ ≠ y _j , выполните обновление, увеличив счетчик ошибок:

α _j ← α _j + 1

Варианты и расширения

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

Для решения этой проблемы был предложен вариант забытого ядра перцептрона. Он поддерживает активный набор примеров с ненулевым α _i , удаляя («забывая») примеры из активного набора, когда он превышает заранее определенный бюджет, и «сжимая» (снижая вес) старые примеры по мере продвижения новых. до ненулевого α _i .

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

Алгоритм проголосованного перцептрона Фрейнда и Шапира также распространяется на ядерный случай: давая границы обобщения, сравнимые с ядром SVM.