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

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

(Различия между версиями)
Перейти к: навигация, поиск
(переработка, дополнение)
Строка 1: Строка 1:
-
'''Линейный классификатор''' — алгоритм классификации, основанный на построении линейной разделяющей поверхности. {{S|В случае}} двух классов разделяющей поверхностью является гиперплоскость, которая делит пространство признаков на два полупространства.
+
{{TOCright}}
 +
'''Линейный классификатор''' — алгоритм классификации, основанный на построении линейной разделяющей поверхности. В случае двух классов разделяющей поверхностью является гиперплоскость, которая делит пространство признаков на два полупространства.
 +
В случае большего числа классов разделяющая поверхность кусочно-линейна.
== Определение ==
== Определение ==
Пусть объекты описываются ''n'' числовыми признаками
Пусть объекты описываются ''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</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_0</tex> — порог принятия решения,
<tex>w=(w_0,w_1,\ldots,w_n)</tex> — вектор весов,
<tex>w=(w_0,w_1,\ldots,w_n)</tex> — вектор весов,
<tex>\langle x,w \rangle</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> указанного вида,
построить алгоритм <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>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>M(x_i)</tex> отрицателен тогда и только тогда, когда
алгоритм <tex>a(x)</tex> допускает ошибку на объекте&nbsp;<tex>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.
# ''Дуда Р., Харт П.'' Распознавание образов и анализ сцен. — М.: Мир, 1976.
# {{П:Hastie 2001 The Elements of Statistical Learning}}
# {{П: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.
== Ссылки ==
== Ссылки ==

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

Содержание

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

Определение

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

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

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

Литература

  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.

Ссылки

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