Линейный классификатор
Материал из MachineLearning.
м (→Регуляризация) |
(уточнения) |
||
(1 промежуточная версия не показана) | |||
Строка 34: | Строка 34: | ||
построить алгоритм <tex>a:\; X\to Y</tex> указанного вида, | построить алгоритм <tex>a:\; X\to Y</tex> указанного вида, | ||
минимизирующий ''фунционал эмпирического риска'': | минимизирующий ''фунционал эмпирического риска'': | ||
- | ::<tex>Q(w | + | ::<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>Y=\{-1,+1\}</tex>, | ||
- | удобно определить для произвольного обучающего объекта <tex>x_i\in X^m</tex> величину '' | + | удобно определить для произвольного обучающего объекта <tex>x_i\in X^m</tex> величину ''[[отступ]]а'' (margin): |
::<tex>M(x_i) = y_i \langle x_i,w \rangle.</tex> | ::<tex>M(x_i) = y_i \langle x_i,w \rangle.</tex> | ||
Строка 51: | Строка 51: | ||
алгоритм <tex>a(x)</tex> допускает ошибку на объекте <tex>x_i</tex>. | алгоритм <tex>a(x)</tex> допускает ошибку на объекте <tex>x_i</tex>. | ||
Это наблюдение позволяет записать фунционал [[эмпирический риск|эмпирического риска]] в следующем виде: | Это наблюдение позволяет записать фунционал [[эмпирический риск|эмпирического риска]] в следующем виде: | ||
- | ::<tex>Q(w | + | ::<tex>Q(w) = \sum_{i=1}^m \bigl[ M(x_i) < 0 \bigr].</tex> |
=== Замена пороговой функции потерь === | === Замена пороговой функции потерь === | ||
- | Минимизация функционала <tex>Q(w | + | Минимизация функционала <tex>Q(w)</tex> по вектору весов сводится к поиску максимальной совместной подсистемы в системе неравенств. |
Эта задача является NP-полной и может иметь очень много решений, поскольку минимальное число ошибок может реализоваться на различных подмножествах объектов. | Эта задача является NP-полной и может иметь очень много решений, поскольку минимальное число ошибок может реализоваться на различных подмножествах объектов. | ||
Однако абсолютно точное решение этой задачи, и, тем более, нахождение всех её решений, в большинстве приложений не представляет практического интереса. | Однако абсолютно точное решение этой задачи, и, тем более, нахождение всех её решений, в большинстве приложений не представляет практического интереса. | ||
Строка 65: | Строка 65: | ||
После замены функции потерь минимизируется не сам функционал [[эмпирический риск|эмпирического риска]], а его верхняя оценка. | После замены функции потерь минимизируется не сам функционал [[эмпирический риск|эмпирического риска]], а его верхняя оценка. | ||
- | ::<tex>Q(w | + | ::<tex>Q(w) \leq \tilde Q(w) = \sum_{i=1}^m L\bigl( M(x_i) \bigr).</tex> |
Применение аппроксимаций имеет ряд преимуществ. | Применение аппроксимаций имеет ряд преимуществ. | ||
Строка 73: | Строка 73: | ||
=== Регуляризация === | === Регуляризация === | ||
Наряду с заменой пороговой функции потерь, рекомендуется добавлять к функционалу штрафное слагаемое, запрещающее слишком большие значения нормы вектора весов: | Наряду с заменой пороговой функции потерь, рекомендуется добавлять к функционалу штрафное слагаемое, запрещающее слишком большие значения нормы вектора весов: | ||
- | ::<tex>Q(w | + | ::<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</tex> определяет класс методов оптимизации. | ||
- | * При <tex>p=2</tex> и гладком (по параметру <tex>w</tex>) функционале <tex>Q(w | + | * При <tex>p=2</tex> и гладком (по параметру <tex>w</tex>) функционале <tex>Q(w)</tex> можно применять стандартные градиентные методы минимизации. |
- | * При <tex>p=1</tex> и выпуклом функционале <tex>Q(w | + | * При <tex>p=1</tex> и выпуклом функционале <tex>Q(w)</tex> возникает задача выпуклого программирования с ограничениями типа неравенств. В результате её решения часть коэффициентов <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>\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. | Задача обучения решается градиентным методом второго порядка, что приводит к [[Метод наименьших квадратов с итеративным пересчетом весов|методу наименьших квадратов с итеративным пересчетом весов]] IRLS. | ||
Строка 151: | Строка 152: | ||
== Связь с другими методами == | == Связь с другими методами == | ||
- | [[Метод ближайшего соседа]] в пространстве признаков с евклидовой метрикой реализует линейный классификатор, если в обучающей выборке оставить по одному объекту от каждого класса. | + | [[Метод ближайшего соседа]] в пространстве признаков с евклидовой метрикой определяет границу между классами как кусочно-линейную поверхность. В частности, метод реализует линейный классификатор, если в обучающей выборке оставить по одному объекту от каждого класса. |
== Литература == | == Литература == |
Текущая версия
|
Линейный классификатор — алгоритм классификации, основанный на построении линейной разделяющей поверхности. В случае двух классов разделяющей поверхностью является гиперплоскость, которая делит пространство признаков на два полупространства. В случае большего числа классов разделяющая поверхность кусочно-линейна.
Определение
Пусть объекты описываются n числовыми признаками . Тогда пространство признаковых описаний объектов есть . Пусть — конечное множество номеров (имён, меток) классов.
Случай двух классов
Положим .
Линейным классификатором называется алгоритм классификации вида
где — вес -го признака, — порог принятия решения, — вектор весов, — скалярное произведение признакового описания объекта на вектор весов. Предполагается, что искусственно введён «константный» нулевой признак: .
Случай произвольного числа классов
Линейный классификатор определяется выражением
где каждому классу соотвествует свой вектор весов .
Обучение линейного классификатора
Метод минимизации эмпирического риска
Обучение (настройка) линейного классификатора методом минимизации эмпирического риска заключается в том, чтобы по заданной обучающей выборке пар «объект, ответ» построить алгоритм указанного вида, минимизирующий фунционал эмпирического риска:
Методы обучения линейных классификаторов различаются подходами к решению данной оптимизационной задачи.
Понятие отступа
В случае двух классов, , удобно определить для произвольного обучающего объекта величину отступа (margin):
В случае произвольного числа классов отступ определяется выражением
Отступ можно понимать как «степень погруженности» объекта в свой класс. Чем меньше значение отступа , тем ближе объект подходит к границе классов, тем выше становится вероятность ошибки. Отступ отрицателен тогда и только тогда, когда алгоритм допускает ошибку на объекте . Это наблюдение позволяет записать фунционал эмпирического риска в следующем виде:
Замена пороговой функции потерь
Минимизация функционала по вектору весов сводится к поиску максимальной совместной подсистемы в системе неравенств. Эта задача является NP-полной и может иметь очень много решений, поскольку минимальное число ошибок может реализоваться на различных подмножествах объектов. Однако абсолютно точное решение этой задачи, и, тем более, нахождение всех её решений, в большинстве приложений не представляет практического интереса. Обычно вполне устраивает приближённое решение, достаточно близкое к точному.
Наиболее известные методы обучения линейного классификатора связаны с заменой пороговой функции потерь её различными непрерывными аппроксимациями:
- ,
где — непрерывная или гладкая функция, как правило, невозрастающая.
После замены функции потерь минимизируется не сам функционал эмпирического риска, а его верхняя оценка.
Применение аппроксимаций имеет ряд преимуществ.
- Некоторые аппроксимации способны улучшать обобщающую способность классификатора. В частности, известно, что пробит-аппроксимация при некоторых условиях уменьшает вероятность ошибки [Langford, McAllester].
- Непрерывные аппроксимации позволяют применять известные численные методы оптимизации для настройки весов , в частности, градиентные методы и методы выпуклого программирования.
Регуляризация
Наряду с заменой пороговой функции потерь, рекомендуется добавлять к функционалу штрафное слагаемое, запрещающее слишком большие значения нормы вектора весов:
Добавление штрафного слагаемого или регуляризация снижает риск переобучения и повышает устойчивость вектора весов по отношению к малым изменениям обучающей выборки. Идея регуляризации предлагалась разными авторами, в разные годы, для разных алгоритмов, и называлась, соотвественно, по разному: сокращение весов (weght decay) — в нейронных сетях, гребневая регрессия (ridge regression) — в регрессионном анализе, сжатие весов (shrinkage).
Параметр регуляризации подбирается исходя из априорных соображений, либо по скользящему контролю. Существуют также теоретические оценки обобщающей способности линейного классификатора, позволяющие оценивать параметр регуляризации по явным формулам.
Степень регуляризатора определяет класс методов оптимизации.
- При и гладком (по параметру ) функционале можно применять стандартные градиентные методы минимизации.
- При и выпуклом функционале возникает задача выпуклого программирования с ограничениями типа неравенств. В результате её решения часть коэффициентов обнуляются, что фактически означает отсев неинформативных признаков.
Методы обучения линейных классификаторов
Методы обучения линейных классификаторов различаются, главным образом, выбором функции , способом регуляризации и выбором численного метода оптимизации.
Линейный дискриминант Фишера
Линейный дискриминант Фишера соответствует квадратичной аппроксимации при условии, что из каждого вектора признаков предварительно вычитается вектор центра класса:
Задача обучения решается методом наименьших квадратов.
Однослойный перцептрон
Аппроксимация сигмоидной или логит-функцией иногда используется при настройке однослойного перцептрона и нейронных сетей:
где параметр задаётся априори.
Задача минимизации в общем случае многоэкстремальна, поскольку логит-функция не выпукла. Кроме того, логит-функция имеет горизонтальные асимптоты, что может приводить к проблеме паралича при использовании градиентных методов минимизации. Применение логит-функции требует введения дополнительных эвристик для уменьшения переобучения (регуляризация, стохастические шаги для выбивания из локальных минимумов).
Метод опорных векторов
Метод опорных векторов соответствует кусочно-линейной аппроксимации:
При этом обязательно применяется регуляризация с квадратичной нормой. Задача обучения решается специализированными методами квадратичного программирования.
Логистическая регрессия
Логистическая регрессия соответствует логарифмической аппроксимации:
При некоторых (достаточно сильных) предположениях о функциях правдоподобия классов минимизация эмпирического риска с такой функцией потерь эквивалентна максимизации правдоподобия. При этом линейный классификатор является оптимальным байесовским классификатором, а значение линейной дискриминантной функции связано с апостериорной вероятностью классов (для случая двух классов):
где — сигмоидная функция.
Задача обучения решается градиентным методом второго порядка, что приводит к методу наименьших квадратов с итеративным пересчетом весов IRLS.
Логистическая регрессия является частным случаем обобщённой линейной модели регрессии.
Пробит-аппроксимация
Аппроксимация пробит-функцией обоснована в рамках байесовской теории вероятно приближённо корректного обучения (PAC-Bayesian approach) [Langford, McAllester]:
где — функция нормального распределения с нулевым средним и единичной дисперсией; параметр вычисляется по явным формулам.
Методы минимизации в теории не рассматриваются. Однако очевидно, что задача в общем случае многоэкстремальна, поскольку пробит-функция не выпукла. Кроме того, пробит-функция имеет горизонтальные асимптоты, что может приводить к проблеме паралича при использовании градиентных методов минимизации. Применение пробит-функции требует введения дополнительных эвристик для уменьшения переобучения (регуляризация, стохастические шаги для выбивания из локальных минимумов).
Экспоненциальная аппроксимация
Экспоненциальная аппроксимация используется в алгоритмах бустинга, в частности, в алгоритме AdaBoost:
Недостаток этой аппроксимации в том, что она слишком сильно штрафует большие по абсолютной величине отрицательные отступы. Если в данных есть объекты-выбросы, то основные усилия процедуры обучения будут сосредоточены на увеличении небольшого числа сильно отрицательных отступов — вместо того, чтобы уменьшать число ошибок классификации путём увеличения основной массы отступов, близких к нулю.
Связь с другими методами
Метод ближайшего соседа в пространстве признаков с евклидовой метрикой определяет границу между классами как кусочно-линейную поверхность. В частности, метод реализует линейный классификатор, если в обучающей выборке оставить по одному объекту от каждого класса.
Литература
- Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 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.