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

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

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

Версия 00:00, 1 сентября 2008

Содержание

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,x) = \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,x) = \sum_{i=1}^m \bigl[ M(x_i) < 0 \bigr].$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Однослойный перцептрон соответствует сигмоидной аппроксимации (хотя, возможны и другие варианты):

$\bigl[ M < 0 \bigr] \leq 2\sigma(-M) = \frac2{1+e^M}.$

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 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»

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

@@ Строка 1: / Строка 1: @@
-'''Линейный классификатор''' — алгоритм классификации, основанный на построении линейной разделяющей поверхности. {{S|В случае}} двух классов разделяющей поверхностью является гиперплоскость, которая делит пространство признаков на два полупространства.
+{{TOCright}}
+'''Линейный классификатор''' — алгоритм классификации, основанный на построении линейной разделяющей поверхности. В&nbsp;случае двух классов разделяющей поверхностью является гиперплоскость, которая делит пространство признаков на два полупространства.
+В&nbsp;случае большего числа классов разделяющая поверхность кусочно-линейна.
 == Определение ==
 Пусть объекты описываются ''n'' числовыми признаками
-<tex>f_j:\: X\to\mathbb{R}</tex>,  <tex>j=1,\ldots,n</tex>;
+<tex>f_j:\: X\to\mathbb{R},\; j=1,\ldots,n</tex>.
-Тогда пространство признаковых описаний объектов есть <tex>X=\mathbb{R}</tex>.
+Тогда пространство признаковых описаний объектов есть <tex>X=\mathbb{R}^n</tex>.
 Пусть <tex>Y</tex> — конечное множество номеров (имён, меток) классов.
-В случае двух классов, <tex>Y=\{-1,+1\}</tex>,
+=== Случай двух классов ===
-''линейным классификатором'' называется алгоритм классификации <tex>a:\; X\to Y</tex>, имеющий вид
+Положим <tex>Y=\{-1,+1\}</tex>.
-<center>
-<tex>a(x) = \mathrm{sign}\left( \sum_{j=1}^n w_j f_j(x) - w_0 \right) = \mathrm{sign}\langle x,w \rangle,</tex>
+''Линейным классификатором'' называется алгоритм классификации <tex>a:\; X\to Y</tex> вида
-</center>
+::<tex>a(x,w) = \mathrm{sign}\left( \sum_{j=1}^n w_j f_j(x) - w_0 \right) = \mathrm{sign}\langle x,w \rangle,</tex>
 где
-<tex>w_j</tex> — веса признаков,
+<tex>w_j</tex> — вес <tex>j</tex>-го признака,
 <tex>w_0</tex> — порог принятия решения,
 <tex>w=(w_0,w_1,\ldots,w_n)</tex> — вектор весов,
 <tex>\langle x,w \rangle</tex> — скалярное произведение признакового описания объекта на вектор весов.
-Предполагается, что искусственно введён «константный» нулевой признак:
+Предполагается, что искусственно введён «константный» нулевой признак: <tex>f_{0}(x)=-1</tex>.
-<tex>f_{0}(x)\equiv -1</tex>.
-В случае произвольного числа классов ''линейный классификатор'' определяется выражением
+=== Случай произвольного числа классов ===
-<center>
+''Линейный классификатор'' определяется выражением
-<tex>a(x) = \mathrm{arg}\max_{y\in Y} \sum_{j=1}^n w_{yj} f_j(x) = \mathrm{arg}\max_{y\in Y} \langle x,w_y \rangle,</tex>
+::<tex>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,</tex>
-</center>
+где каждому классу соотвествует свой вектор весов <tex>w_y=(w_{y0},w_{y1},\ldots,w_{yn})</tex>.
-где каждому классу соотвествует свой вектор весов <tex>w_y</tex>.
-Задача настройки (обучения) классификатора заключается в том, чтобы
+==  Обучение линейного классификатора ==
-по заданной [[выборка|обучающей выборке]] пар «объект, ответ»
-<tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}</tex>.
+=== Метод минимизации эмпирического риска ===
+Обучение (настройка) линейного классификатора методом [[Минимизация эмпирического риска|минимизации эмпирического риска]] заключается в том, чтобы по заданной [[выборка|обучающей выборке]] пар «объект, ответ»
+<tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}</tex>
 построить алгоритм <tex>a:\; X\to Y</tex> указанного вида,
-минимизирующий фунционал [[эмпирический риск|эмпирического риска]]:
+минимизирующий ''фунционал эмпирического риска'':
-<center>
+::<tex>Q(w,x) = \sum_{i=1}^m \bigl[ a(x_i,w) \neq y_i \bigr] \to \min_w.</tex>
-<tex>Q(w,x) = \sum_{i=1}^m \bigl[ a(x_i) \neq y_i \bigr].</tex>
-</center>
 Методы обучения линейных классификаторов различаются подходами к решению данной оптимизационной задачи.
-== Понятие отступа ==
+=== Понятие отступа ===
 В случае двух классов, <tex>Y=\{-1,+1\}</tex>,
-удобно определить для произвольного обучающего объекта <tex>x_i\in X^m</tex> величину отступа (margin):
+удобно определить для произвольного обучающего объекта <tex>x_i\in X^m</tex> величину ''отступа'' (margin):
-<center>
+::<tex>M(x_i) = y_i \langle x_i,w \rangle.</tex>
-<tex>M(x_i) = y_i \langle x_i,w \rangle.</tex>
-</center>
+В случае произвольного числа классов отступ определяется выражением
+::<tex>M(x_i) = \langle x_i,w_{y_i} \rangle - \!\max_{y\in Y,\, y\neq y_i}\! \langle x_i,w_y \rangle.</tex>
+Отступ можно понимать как «степень погруженности» объекта в свой класс.
+Чем меньше значение отступа <tex>M(x_i)</tex>, тем ближе объект подходит к границе классов, тем выше становится вероятность ошибки.
 Отступ <tex>M(x_i)</tex> отрицателен тогда и только тогда, когда
 алгоритм <tex>a(x)</tex> допускает ошибку на объекте&nbsp;<tex>x_i</tex>.
-Чем меньше значение отступа, тем «более ошибочным» является значение скалярного произведения
+Это наблюдение позволяет записать фунционал [[эмпирический риск|эмпирического риска]] в следующем виде:
-<tex>\langle x_i,w \rangle</tex>.
+::<tex>Q(w,x) = \sum_{i=1}^m \bigl[ M(x_i) < 0 \bigr].</tex>
-Это наблюдение позволяет обобщить фунционал [[эмпирический риск|эмпирического риска]]:
+=== Замена пороговой функции потерь ===
-<center>
+Минимизация функционала <tex>Q(w,x)</tex> по вектору весов сводится к поиску максимальной совместной подсистемы в системе неравенств.
-<tex>Q(w,x) = \sum_{i=1}^m L\bigl( M(x_i) \bigr),</tex>
+Эта задача является NP-полной и может иметь очень много решений, поскольку минимальное число ошибок может реализоваться на различных подмножествах объектов.
-</center>
+Однако абсолютно точное решение этой задачи, и, тем более, нахождение всех её решений, в большинстве приложений не представляет практического интереса.
+Обычно вполне устраивает приближённое решение, достаточно близкое к точному.
+Наиболее известные методы обучения линейного классификатора связаны с заменой пороговой функции потерь её различными непрерывными аппроксимациями:
+::<tex>\bigl[ M < 0 \bigr] \leq L(M)</tex>,
 где
-<tex>L(M)</tex> — функция потерь, зависящая от отступа.
+<tex>L:\:\mathbb{R}\to\mathbb{R}_{+}</tex>&nbsp;— непрерывная или гладкая функция, как правило, невозрастающая.
-Обычно используются непрерывные монотонно убывающие функции <tex>L(M)</tex>,
-что позволяет применять численные методы оптимизации для настройки весов линейного классификатора.
-Методы обучения линейных классификаторов различаются, в первую очередь, выбором функции <tex>L(M)</tex>.
+После замены функции потерь минимизируется не сам функционал [[эмпирический риск|эмпирического риска]], а его верхняя оценка.
+::<tex>Q(w,x) \leq \tilde Q(w,x) = \sum_{i=1}^m L\bigl( M(x_i) \bigr).</tex>
+Непрерывные аппроксимации позволяют применять известные численные методы оптимизации для настройки весов линейного классификатора, в частности, градиентные методы и методы выпуклого программирования.
+=== Регуляризация ===
+Наряду с заменой пороговой функции потерь, рекомендуется добавлять к функционалу штрафное слагаемое, запрещающее слишком большие значения нормы вектора весов:
+::<tex>Q(w,x) \leq \tilde Q(w,x) = \sum_{i=1}^m L\bigl( M(x_i) \bigr) + \gamma ||w|| \to \min_w.</tex>
+Добавление штрафного слагаемого или [[регуляризация]] снижает риск переобучения и повышает устойчивость вектора весов по отношению к малым изменениям обучающей выборки.
+Идея регуляризации предлагалась разными авторами, в разные годы, для разных алгоритмов, и называлась, соотвественно, по разному:
+[[сокращение весов]] (weght decay) — в нейронных сетях,
+[[гребневая регрессия]] (ridge regression) — в регрессионном анализе,
+[[сжатие весов]] (shrinkage).
+''Параметр регуляризации'' <tex>\gamma</tex> подбирается исходя из априорных соображений, либо по [[Скользящий контроль|скользящему контролю]].
+Существуют также теоретические оценки обобщающей способности линейного классификатора, позволяющие оценивать параметр регуляризации по явной формуле [Langford, McAllester].
 == Методы обучения линейных классификаторов ==
-*[[Линейный дискриминант Фишера]]
+Методы обучения линейных классификаторов различаются, главным образом, выбором функции <tex>L(M)</tex>, способом регуляризации и выбором численного метода оптимизации.
-*[[Однослойный персептрон]]
-*[[Метод опорных векторов]]
+=== Линейный дискриминант Фишера ===
-*[[Логистическая регрессия]]
+[[Линейный дискриминант Фишера]] соответствует квадратичной аппроксимации при условии, что из каждого вектора признаков предварительно вычитается вектор центра класса:
-*[[Метод ближайшего соседа]] реализует линейный классификатор, если в обучающей выборке оставить по одному объекту каждого класса.
+::<tex>\bigl[ M < 0 \bigr] \leq (1-M)^2.</tex>
+Задача обучения решается [[Метод наименьших квадратов|методом наименьших квадратов]].
+=== Однослойный перцептрон ===
+[[Однослойный перцептрон]] соответствует сигмоидной аппроксимации (хотя, возможны и другие варианты):
+::<tex>\bigl[ M < 0 \bigr] \leq 2\sigma(-M) = \frac2{1+e^M}.</tex>
+Задача обучения решается градиентными методами первого порядка.
+=== Метод опорных векторов ===
+[[Метод опорных векторов]] соответствует кусочно-линейной аппроксимации:
+::<tex>\bigl[ M < 0 \bigr] \leq (1-M)_{+}.</tex>
+При этом обязательно применяется регуляризация с квадратичной нормой.
+Задача обучения решается специализированными методами квадратичного программирования.
+=== Логистическая регрессия ===
+[[Логистическая регрессия]] соответствует логарифмической аппроксимации:
+::<tex>\bigl[ M < 0 \bigr] \leq \log_2(1+e^{-M}).</tex>
+При некоторых (достаточно сильных) предположениях о функциях правдоподобия классов минимизация эмпирического риска с такой функцией потерь эквивалентна [[Принцип максимума правдоподобия|максимизации правдоподобия]]. При этом линейный классификатор является [[Байесовский классификатор|оптимальным байесовским классификатором]], а значение линейной дискриминантной функции связано с апостериорной вероятностью классов (для случая двух классов):
+::<tex>\sigma\left( y\langle w,x \rangle \right) = \mathbb{P}\{y|x\}.</tex>
+Задача обучения решается градиентным методом второго порядка, что приводит к [[Метод наименьших квадратов с итеративным пересчетом весов|методу наименьших квадратов с итеративным пересчетом весов]] IRLS.
+== Связь с другими методами ==
+'''[[Метод ближайшего соседа]]''' в пространстве признаков с евклидовой метрикой реализует линейный классификатор, если в обучающей выборке оставить по одному объекту от каждого класса.
 == Литература ==
@@ Строка 74: / Строка 123: @@
 # ''Дуда Р., Харт П.'' Распознавание образов и анализ сцен. — М.: Мир, 1976.
 # {{П:Hastie 2001 The Elements of Statistical Learning}}
+# ''Langford J.'' Tutorial on Practical Prediction Theory for Classification. — 2005. — 28&nbsp;P.
+# ''McAllester D.'' Simplified PAC-Bayesian Margin Bounds. — 2003.
 == Ссылки ==