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

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

(Различия между версиями)

Текущая версия

Содержание

1 Определение
- 1.1 Случай двух классов
- 1.2 Случай произвольного числа классов
2 Обучение линейного классификатора
3 Методы обучения линейных классификаторов
4 Связь с другими методами
5 Литература
6 Ссылки

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

Определение

Пусть объекты описываются 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).$

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

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

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

Литература

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

Ссылки

Машинное обучение (курс лекций, К.В.Воронцов)

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%82%D0%BE%D1%80»

Категории: Незавершённые статьи | Линейные классификаторы | Машинное обучение | Классификация | Энциклопедия анализа данных

@@ Строка 34: / Строка 34: @@
 построить алгоритм <tex>a:\; X\to Y</tex> указанного вида,
 минимизирующий ''фунционал эмпирического риска'':
-::<tex>Q(w,x) = \sum_{i=1}^m \bigl[ a(x_i,w) \neq y_i \bigr] \to \min_w.</tex>
+::<tex>Q(w) = \sum_{i=1}^m \bigl[ a(x_i,w) \neq y_i \bigr] \to \min_w.</tex>
 Методы обучения линейных классификаторов различаются подходами к решению данной оптимизационной задачи.
@@ Строка 40: / Строка 40: @@
 === Понятие отступа ===
 В случае двух классов, <tex>Y=\{-1,+1\}</tex>,
-удобно определить для произвольного обучающего объекта <tex>x_i\in X^m</tex> величину ''отступа'' (margin):
+удобно определить для произвольного обучающего объекта <tex>x_i\in X^m</tex> величину ''[[отступ]]а'' (margin):
 ::<tex>M(x_i) = y_i \langle x_i,w \rangle.</tex>
@@ Строка 51: / Строка 51: @@
 алгоритм <tex>a(x)</tex> допускает ошибку на объекте&nbsp;<tex>x_i</tex>.
 Это наблюдение позволяет записать фунционал [[эмпирический риск|эмпирического риска]] в следующем виде:
-::<tex>Q(w,x) = \sum_{i=1}^m \bigl[ M(x_i) < 0 \bigr].</tex>
+::<tex>Q(w) = \sum_{i=1}^m \bigl[ M(x_i) < 0 \bigr].</tex>
 === Замена пороговой функции потерь ===
-Минимизация функционала <tex>Q(w,x)</tex> по вектору весов сводится к поиску максимальной совместной подсистемы в системе неравенств.
+Минимизация функционала <tex>Q(w)</tex> по вектору весов сводится к поиску максимальной совместной подсистемы в системе неравенств.
 Эта задача является NP-полной и может иметь очень много решений, поскольку минимальное число ошибок может реализоваться на различных подмножествах объектов.
 Однако абсолютно точное решение этой задачи, и, тем более, нахождение всех её решений, в большинстве приложений не представляет практического интереса.
@@ Строка 65: / Строка 65: @@
 После замены функции потерь минимизируется не сам функционал [[эмпирический риск|эмпирического риска]], а его верхняя оценка.
-::<tex>Q(w,x) \leq \tilde Q(w,x) = \sum_{i=1}^m L\bigl( M(x_i) \bigr).</tex>
+::<tex>Q(w) \leq \tilde Q(w) = \sum_{i=1}^m L\bigl( M(x_i) \bigr).</tex>
 Применение аппроксимаций имеет ряд преимуществ.
@@ Строка 73: / Строка 73: @@
 === Регуляризация ===
 Наряду с заменой пороговой функции потерь, рекомендуется добавлять к функционалу штрафное слагаемое, запрещающее слишком большие значения нормы вектора весов:
-::<tex>Q(w,x) \leq \tilde Q(w,x) = \sum_{i=1}^m L\bigl( M(x_i) \bigr) + \gamma ||w||^p \to \min_w.</tex>
+::<tex>Q(w) \leq \tilde Q(w) = \sum_{i=1}^m L\bigl( M(x_i) \bigr) + \gamma ||w||^p \to \min_w.</tex>
 Добавление штрафного слагаемого или [[регуляризация]] снижает риск переобучения и повышает устойчивость вектора весов по отношению к малым изменениям обучающей выборки.
@@ Строка 85: / Строка 85: @@
 ''Степень регуляризатора'' <tex>p</tex> определяет класс методов оптимизации.
-* При <tex>p=2</tex> и гладком (по параметру <tex>w</tex>) функционале <tex>Q(w,x)</tex> можно применять стандартные градиентные методы минимизации.
+* При <tex>p=2</tex> и гладком (по параметру <tex>w</tex>) функционале <tex>Q(w)</tex> можно применять стандартные градиентные методы минимизации.
-* При <tex>p=1</tex> и выпуклом функционале <tex>Q(w,x)</tex> возникает задача выпуклого программирования с ограничениями типа неравенств. В&nbsp;результате её решения часть коэффициентов <tex>w_j</tex> обнуляются, что фактически означает [[Отбор признаков|отсев неинформативных признаков]].
+* При <tex>p=1</tex> и выпуклом функционале <tex>Q(w)</tex> возникает задача выпуклого программирования с ограничениями типа неравенств. В&nbsp;результате её решения часть коэффициентов <tex>w_j</tex> обнуляются, что фактически означает [[Отбор признаков|отсев неинформативных признаков]].
 == Методы обучения линейных классификаторов ==
@@ Строка 122: / Строка 122: @@
 При некоторых (достаточно сильных) предположениях о функциях правдоподобия классов минимизация эмпирического риска с такой функцией потерь эквивалентна [[Принцип максимума правдоподобия|максимизации правдоподобия]]. При этом линейный классификатор является [[Байесовский классификатор|оптимальным байесовским классификатором]], а значение линейной дискриминантной функции связано с апостериорной вероятностью классов (для случая двух классов):
-::<tex>\sigma\left( M(x) \right) = \sigma\left( y\langle w,x \rangle \right) = \mathbb{P}\{y|x\}.</tex>
+::<tex>\sigma\left( M(x) \right) = \sigma\left( y\langle w,x \rangle \right) = \mathbb{P}\{y|x\},</tex>
+где <tex>\sigma(z) = \frac1{1+e^{-z}}</tex> — [[сигмоидная функция]].
 Задача обучения решается градиентным методом второго порядка, что приводит к [[Метод наименьших квадратов с итеративным пересчетом весов|методу наименьших квадратов с итеративным пересчетом весов]] IRLS.
@@ Строка 151: / Строка 152: @@
 == Связь с другими методами ==
-[[Метод ближайшего соседа]] в пространстве признаков с евклидовой метрикой реализует линейный классификатор, если в обучающей выборке оставить по одному объекту от каждого класса.
+[[Метод ближайшего соседа]] в пространстве признаков с евклидовой метрикой определяет границу между классами как кусочно-линейную поверхность. В частности, метод реализует линейный классификатор, если в обучающей выборке оставить по одному объекту от каждого класса.
 == Литература ==