Линейный классификатор

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

Определение

На картинке множества чёрных и белых шаров разделяются синей и красной линией. При этом красная линия проводит более точную классификацию, потому что она максимально отстоит от обоих множеств. Зелёная линия не является линейным классификатором, она не разделяет два множества.

Пусть вектор ${\vec {x}}$ из действительных чисел представляет собой входные данные, а на выходе классификатора вычисляется показатель y по формуле:

$y=f({\vec {w}}\cdot {\vec {x}})=f\left(\sum _{j}w_{j}x_{j}\right),$

здесь ${\vec {w}}$ - действительный вектор весов, а f - функция преобразования скалярного произведения. (Иными словами, вектор весов ${\vec {w}}$ - ковариантный вектор или линейная форма отображения ${\vec {x}}$ в R.) Значения весов вектора ${\vec {w}}$ определяются в ходе машинного обучения на подготовленных образцах. Функция f обычно простая пороговая функция, отделяющая один класс объектов от другого. В более сложных случаях Функция f имеет смысл вероятности того или иного решения.

Операцию линейной классификации для двух классов можно себе представить как отображение объектов в многомерном пространстве на гиперплоскость, в которой те объекты, которые попали по одну сторону разделяющей линии, относятся к первому классу ("да"), а объекты по другую сторону - ко второму классу ("нет")).

Линейный классификатор используется когда важно проводить быстрые вычисления с большой скоростью. Он неплохо работает, когда входной вектор ${\vec {x}}$ разрежен. Линейные классификаторы могут хорошо срабатывать в многомерном пространстве, например, для классификации документов по матрице встречаемости слов. В подобных случаях считается, что объекты хорошо регуляризируемы.

Генеративная и дискриминативная модели

Существует два подхода к определению параметров ${\vec {w}}$ для линейного классификатора - генеративные или дискриминативные модели.

Генеративная модель использует условное распределение $P({\vec {x}}|{\rm {class}})$. Например:

• Дискриминантный анализ (LDA) — предполагает нормальное распределение по Гауссу.
• Наивный байесовский классификатор с Бернуллиевской моделью событий.

Дискриминативные модели стремятся улучшить качество выходных данных на наборе образцов для обучения. Например:

• Логистическая регрессия — стремление достичь максимального сходства через вектор of ${\vec {w}}$ из предположения, что наблюдаемый набор образцов генерировался в виде биномиальной модели от выходных данных.
• Простой Перцептрон — алгоритм коррекции всех ошибок на входном наборе образцов.
• Метод опорных векторов — алгоритм расширения разделительной зоны в гиперплоскости решений между образцами входных данных.

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

Дискриминативное обучение

Обучение при использовании дискриминативных моделей строится через "Обучение с учителем" , то есть через процесс оптимизации выходных данных на заданных образцах для обучения. При этом определяется функция потерь, измеряющая несогласование между выходными данными и желаемыми результатами. Формально задача обучения (как оптимизации) записывается как:

${\underset {\mathbf {w} }{\arg \!\min }}\;R(\mathbf {w} )+C\sum _{i=1}^{N}L(y_{i},\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i})$

где

• w - искомый вектор весов классификатора,
• L(y_i, w^Tx_i) функция потерь (то есть, несоответствие между выходом классификатора и истинными значениями y_i для i-го образца),
• R(w) - функция регуляризации, которая не позволяет параметрам выходить за разумные пределы (по причине переобучения),
• C - константа, определяемая пользователем алгоритма обучения для балансировки между регуляризацией и функцией потерь.

Наиболее популярны кусочно-линейная функция и логарифмическая (Перекрёстная энтропия) функции потерь. Если функция регуляризации R выпуклая, то ставится проблема выпуклой оптимизации. Для решения этих задач используется много алгоритмов, в частности метод стохастического градиентного спуска, метод градиентного спуска, L-BFGS, метод координатного спуска и Метод Ньютона.

См. также

• Метод обратного распространения ошибки
• Линейная регрессия
• Перцептрон
• Метод опорных векторов

Литература

1. Y. Yang, X. Liu, "A re-examination of text categorization", Proc. ACM SIGIR Conference, pp. 42–49, (1999). paper @ citeseer
2. R. Herbrich, "Learning Kernel Classifiers: Theory and Algorithms," MIT Press, (2001). ISBN 0-262-08306-X