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

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

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

Определение

Пусть объекты описываются n числовыми признаками f_j:\: X\to\mathbb{R},\; j=1,\ldots,n. Тогда пространство признаковых описаний объектов есть X=\mathbb{R}^n. Пусть Y — конечное множество номеров (имён, меток) классов.

Случай двух классов

Положим Y=\{-1,+1\}.

Линейным классификатором называется алгоритм классификации a:\; X\to Y вида

a(x,w) = \mathrm{sign}\left( \sum_{j=1}^n w_j f_j(x) - w_0 \right) = \mathrm{sign}\langle x,w \rangle,

где w_j — вес j-го признака, w_0 — порог принятия решения, w=(w_0,w_1,\ldots,w_n) — вектор весов, \langle x,w \rangle — скалярное произведение признакового описания объекта на вектор весов. Предполагается, что искусственно введён «константный» нулевой признак: f_{0}(x)=-1.

Случай произвольного числа классов

Линейный классификатор определяется выражением

a(x,w) = \mathrm{arg}\max_{y\in Y}\, \sum_{j=0}^n w_{yj} f_j(x) = \mathrm{arg}\max_{y\in Y}\, \langle x,w_y \rangle,

где каждому классу соотвествует свой вектор весов w_y=(w_{y0},w_{y1},\ldots,w_{yn}).

Обучение линейного классификатора

Метод минимизации эмпирического риска

Обучение (настройка) линейного классификатора методом минимизации эмпирического риска заключается в том, чтобы по заданной обучающей выборке пар «объект, ответ» X^m = \{(x_1,y_1),\dots,(x_m,y_m)\} построить алгоритм a:\; X\to Y указанного вида, минимизирующий фунционал эмпирического риска:

Q(w) = \sum_{i=1}^m \bigl[ a(x_i,w) \neq y_i \bigr] \to \min_w.

Методы обучения линейных классификаторов различаются подходами к решению данной оптимизационной задачи.

Понятие отступа

В случае двух классов, Y=\{-1,+1\}, удобно определить для произвольного обучающего объекта x_i\in X^m величину отступа (margin):

M(x_i) = y_i \langle x_i,w \rangle.

В случае произвольного числа классов отступ определяется выражением

M(x_i) = \langle x_i,w_{y_i} \rangle - \!\max_{y\in Y,\, y\neq y_i}\! \langle x_i,w_y \rangle.

Отступ можно понимать как «степень погруженности» объекта в свой класс. Чем меньше значение отступа M(x_i), тем ближе объект подходит к границе классов, тем выше становится вероятность ошибки. Отступ M(x_i) отрицателен тогда и только тогда, когда алгоритм a(x) допускает ошибку на объекте x_i. Это наблюдение позволяет записать фунционал эмпирического риска в следующем виде:

Q(w) = \sum_{i=1}^m \bigl[ M(x_i) < 0 \bigr].

Замена пороговой функции потерь

Минимизация функционала Q(w) по вектору весов сводится к поиску максимальной совместной подсистемы в системе неравенств. Эта задача является NP-полной и может иметь очень много решений, поскольку минимальное число ошибок может реализоваться на различных подмножествах объектов. Однако абсолютно точное решение этой задачи, и, тем более, нахождение всех её решений, в большинстве приложений не представляет практического интереса. Обычно вполне устраивает приближённое решение, достаточно близкое к точному.

Наиболее известные методы обучения линейного классификатора связаны с заменой пороговой функции потерь её различными непрерывными аппроксимациями:

\bigl[ M < 0 \bigr] \leq L(M),

где L:\:\mathbb{R}\to\mathbb{R}_{+} — непрерывная или гладкая функция, как правило, невозрастающая.

После замены функции потерь минимизируется не сам функционал эмпирического риска, а его верхняя оценка.

Q(w) \leq \tilde Q(w) = \sum_{i=1}^m L\bigl( M(x_i) \bigr).

Применение аппроксимаций имеет ряд преимуществ.

  • Некоторые аппроксимации способны улучшать обобщающую способность классификатора. В частности, известно, что пробит-аппроксимация при некоторых условиях уменьшает вероятность ошибки [Langford, McAllester].
  • Непрерывные аппроксимации позволяют применять известные численные методы оптимизации для настройки весов w_j, в частности, градиентные методы и методы выпуклого программирования.

Регуляризация

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

Q(w) \leq \tilde Q(w) = \sum_{i=1}^m L\bigl( M(x_i) \bigr) + \gamma ||w||^p \to \min_w.

Добавление штрафного слагаемого или регуляризация снижает риск переобучения и повышает устойчивость вектора весов по отношению к малым изменениям обучающей выборки. Идея регуляризации предлагалась разными авторами, в разные годы, для разных алгоритмов, и называлась, соотвественно, по разному: сокращение весов (weght decay) — в нейронных сетях, гребневая регрессия (ridge regression) — в регрессионном анализе, сжатие весов (shrinkage).

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

Степень регуляризатора p определяет класс методов оптимизации.

  • При p=2 и гладком (по параметру w) функционале Q(w) можно применять стандартные градиентные методы минимизации.
  • При p=1 и выпуклом функционале Q(w) возникает задача выпуклого программирования с ограничениями типа неравенств. В результате её решения часть коэффициентов w_j обнуляются, что фактически означает отсев неинформативных признаков.

Методы обучения линейных классификаторов

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

Линейный дискриминант Фишера

Линейный дискриминант Фишера соответствует квадратичной аппроксимации при условии, что из каждого вектора признаков предварительно вычитается вектор центра класса:

\bigl[ M < 0 \bigr] \leq (1-M)^2.

Задача обучения решается методом наименьших квадратов.

Однослойный перцептрон

Аппроксимация сигмоидной или логит-функцией иногда используется при настройке однослойного перцептрона и нейронных сетей:

\bigl[ M < 0 \bigr] \leq \frac2{1+e^{\alpha M}}.

где параметр \alpha задаётся априори.

Задача минимизации в общем случае многоэкстремальна, поскольку логит-функция не выпукла. Кроме того, логит-функция имеет горизонтальные асимптоты, что может приводить к проблеме паралича при использовании градиентных методов минимизации. Применение логит-функции требует введения дополнительных эвристик для уменьшения переобучения (регуляризация, стохастические шаги для выбивания из локальных минимумов).

Метод опорных векторов

Метод опорных векторов соответствует кусочно-линейной аппроксимации:

\bigl[ M < 0 \bigr] \leq (1-M)_{+}.

При этом обязательно применяется регуляризация с квадратичной нормой. Задача обучения решается специализированными методами квадратичного программирования.

Логистическая регрессия

Логистическая регрессия соответствует логарифмической аппроксимации:

\bigl[ M < 0 \bigr] \leq \log_2(1+e^{-M}).

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

\sigma\left( M(x) \right) = \sigma\left( y\langle w,x \rangle \right) = \mathbb{P}\{y|x\},

где \sigma(z) = \frac1{1+e^{-z}}сигмоидная функция.

Задача обучения решается градиентным методом второго порядка, что приводит к методу наименьших квадратов с итеративным пересчетом весов IRLS.

Логистическая регрессия является частным случаем обобщённой линейной модели регрессии.

Пробит-аппроксимация

Аппроксимация пробит-функцией обоснована в рамках байесовской теории вероятно приближённо корректного обучения (PAC-Bayesian approach) [Langford, McAllester]:

\bigl[ M < 0 \bigr] \leq 2\Phi(-\alpha M),

где \Phi(z) — функция нормального распределения с нулевым средним и единичной дисперсией; параметр \alpha вычисляется по явным формулам.

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

Экспоненциальная аппроксимация

Экспоненциальная аппроксимация используется в алгоритмах бустинга, в частности, в алгоритме AdaBoost:

\bigl[ M < 0 \bigr] \leq \exp(-M).

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


Связь с другими методами

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

Литература

  1. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
  2. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974. — 416 с.  (подробнее)
  3. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. — 448 с.  (подробнее)
  4. Дуда Р., Харт П. Распознавание образов и анализ сцен. — М.: Мир, 1976.
  5. Hastie, T., Tibshirani, R., Friedman, J. The Elements of Statistical Learning, 2nd edition. — Springer, 2009. — 533 p.  (подробнее)
  6. Langford J. Tutorial on Practical Prediction Theory for Classification. — 2005. — 28 P.
  7. McAllester D. Simplified PAC-Bayesian Margin Bounds. — 2003.

Ссылки

Личные инструменты