Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

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

Вы можете просмотреть и скопировать исходный текст этой страницы:

{{TOCright}} '''Линейный классификатор''' — алгоритм классификации, основанный на построении линейной разделяющей поверхности. В&nbsp;случае двух классов разделяющей поверхностью является гиперплоскость, которая делит пространство признаков на два полупространства. В&nbsp;случае большего числа классов разделяющая поверхность кусочно-линейна. == Определение == Пусть объекты описываются ''n'' числовыми признаками <tex>f_j:\: X\to\mathbb{R},\; j=1,\ldots,n</tex>. Тогда пространство признаковых описаний объектов есть <tex>X=\mathbb{R}^n</tex>. Пусть <tex>Y</tex> — конечное множество номеров (имён, меток) классов. === Случай двух классов === Положим <tex>Y=\{-1,+1\}</tex>. ''Линейным классификатором'' называется алгоритм классификации <tex>a:\; X\to Y</tex> вида ::<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>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>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> где каждому классу соотвествует свой вектор весов <tex>w_y=(w_{y0},w_{y1},\ldots,w_{yn})</tex>. == Обучение линейного классификатора == === Метод минимизации эмпирического риска === Обучение (настройка) линейного классификатора методом [[Минимизация эмпирического риска|минимизации эмпирического риска]] заключается в том, чтобы по заданной [[выборка|обучающей выборке]] пар «объект, ответ» <tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}</tex> построить алгоритм <tex>a:\; X\to Y</tex> указанного вида, минимизирующий ''фунционал эмпирического риска'': ::<tex>Q(w) = \sum_{i=1}^m \bigl[ a(x_i,w) \neq y_i \bigr] \to \min_w.</tex> Методы обучения линейных классификаторов различаются подходами к решению данной оптимизационной задачи. === Понятие отступа === В случае двух классов, <tex>Y=\{-1,+1\}</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) = \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>Q(w) = \sum_{i=1}^m \bigl[ M(x_i) < 0 \bigr].</tex> === Замена пороговой функции потерь === Минимизация функционала <tex>Q(w)</tex> по вектору весов сводится к поиску максимальной совместной подсистемы в системе неравенств. Эта задача является NP-полной и может иметь очень много решений, поскольку минимальное число ошибок может реализоваться на различных подмножествах объектов. Однако абсолютно точное решение этой задачи, и, тем более, нахождение всех её решений, в большинстве приложений не представляет практического интереса. Обычно вполне устраивает приближённое решение, достаточно близкое к точному. Наиболее известные методы обучения линейного классификатора связаны с заменой пороговой функции потерь её различными непрерывными аппроксимациями: ::<tex>\bigl[ M < 0 \bigr] \leq L(M)</tex>, где <tex>L:\:\mathbb{R}\to\mathbb{R}_{+}</tex>&nbsp;— непрерывная или гладкая функция, как правило, невозрастающая. После замены функции потерь минимизируется не сам функционал [[эмпирический риск|эмпирического риска]], а его верхняя оценка. ::<tex>Q(w) \leq \tilde Q(w) = \sum_{i=1}^m L\bigl( M(x_i) \bigr).</tex> Применение аппроксимаций имеет ряд преимуществ. * Некоторые аппроксимации способны улучшать обобщающую способность классификатора. В&nbsp;частности, известно, что [[пробит-функция|пробит-аппроксимация]] при некоторых условиях уменьшает вероятность ошибки [Langford, McAllester]. * Непрерывные аппроксимации позволяют применять известные численные методы оптимизации для настройки весов <tex>w_j</tex>, в&nbsp;частности, градиентные методы и методы выпуклого программирования. === Регуляризация === Наряду с заменой пороговой функции потерь, рекомендуется добавлять к функционалу штрафное слагаемое, запрещающее слишком большие значения нормы вектора весов: ::<tex>Q(w) \leq \tilde Q(w) = \sum_{i=1}^m L\bigl( M(x_i) \bigr) + \gamma ||w||^p \to \min_w.</tex> Добавление штрафного слагаемого или [[регуляризация]] снижает риск переобучения и повышает устойчивость вектора весов по отношению к малым изменениям обучающей выборки. Идея регуляризации предлагалась разными авторами, в разные годы, для разных алгоритмов, и называлась, соотвественно, по разному: [[сокращение весов]] (weght decay) — в нейронных сетях, [[гребневая регрессия]] (ridge regression) — в регрессионном анализе, [[сжатие весов]] (shrinkage). ''Параметр регуляризации'' <tex>\gamma</tex> подбирается исходя из априорных соображений, либо по [[Скользящий контроль|скользящему контролю]]. Существуют также теоретические оценки обобщающей способности линейного классификатора, позволяющие оценивать параметр регуляризации по явным формулам. ''Степень регуляризатора'' <tex>p</tex> определяет класс методов оптимизации. * При <tex>p=2</tex> и гладком (по параметру <tex>w</tex>) функционале <tex>Q(w)</tex> можно применять стандартные градиентные методы минимизации. * При <tex>p=1</tex> и выпуклом функционале <tex>Q(w)</tex> возникает задача выпуклого программирования с ограничениями типа неравенств. В&nbsp;результате её решения часть коэффициентов <tex>w_j</tex> обнуляются, что фактически означает [[Отбор признаков|отсев неинформативных признаков]]. == Методы обучения линейных классификаторов == Методы обучения линейных классификаторов различаются, главным образом, выбором функции <tex>L(M)</tex>, способом регуляризации и выбором численного метода оптимизации. === Линейный дискриминант Фишера === [[Линейный дискриминант Фишера]] соответствует квадратичной аппроксимации при условии, что из каждого вектора признаков предварительно вычитается вектор центра класса: ::<tex>\bigl[ M < 0 \bigr] \leq (1-M)^2.</tex> Задача обучения решается [[Метод наименьших квадратов|методом наименьших квадратов]]. === Однослойный перцептрон === Аппроксимация сигмоидной или [[логит-функция|логит-функцией]] иногда используется при настройке [[Однослойный перцептрон|однослойного перцептрона]] и [[Нейронная сеть|нейронных сетей]]: ::<tex>\bigl[ M < 0 \bigr] \leq \frac2{1+e^{\alpha M}}.</tex> где параметр <tex>\alpha</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( 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. Логистическая регрессия является частным случаем [[Обобщённая линейная модель|обобщённой линейной модели]] регрессии. === Пробит-аппроксимация === Аппроксимация [[пробит-функция|пробит-функцией]] обоснована в рамках байесовской теории вероятно приближённо корректного обучения (PAC-Bayesian approach) [Langford, McAllester]: ::<tex>\bigl[ M < 0 \bigr] \leq 2\Phi(-\alpha M),</tex> где <tex>\Phi(z)</tex> — функция нормального распределения с нулевым средним и единичной дисперсией; параметр <tex>\alpha</tex> вычисляется по явным формулам. Методы минимизации в теории не рассматриваются. Однако очевидно, что задача в общем случае многоэкстремальна, поскольку пробит-функция не выпукла. Кроме того, пробит-функция имеет горизонтальные асимптоты, что может приводить к [[Проблема паралича|проблеме паралича]] при использовании градиентных методов минимизации. Применение пробит-функции требует введения дополнительных эвристик для уменьшения переобучения (регуляризация, стохастические шаги для выбивания из локальных минимумов). === Экспоненциальная аппроксимация === Экспоненциальная аппроксимация используется в алгоритмах [[Бустинг|бустинга]], в&nbsp;частности, в&nbsp;[[Алгоритм AdaBoost|алгоритме AdaBoost]]: ::<tex>\bigl[ M < 0 \bigr] \leq \exp(-M).</tex> Недостаток этой аппроксимации в&nbsp;том, что она слишком сильно штрафует большие по абсолютной величине отрицательные отступы. Если в данных есть объекты-выбросы, то основные усилия процедуры обучения будут сосредоточены на увеличении небольшого числа сильно отрицательных отступов — вместо того, чтобы уменьшать число ошибок классификации путём увеличения основной массы отступов, близких к нулю. == Связь с другими методами == [[Метод ближайшего соседа]] в пространстве признаков с евклидовой метрикой определяет границу между классами как кусочно-линейную поверхность. В частности, метод реализует линейный классификатор, если в обучающей выборке оставить по одному объекту от каждого класса. == Литература == # ''Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д.'' Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989. # {{П:Вапник 74}} # {{П:Вапник 79}} # ''Дуда Р., Харт П.'' Распознавание образов и анализ сцен. — М.: Мир, 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. == Ссылки == * [[Машинное обучение (курс лекций, К.В.Воронцов)]] {{stub}} [[Категория:Линейные классификаторы]] [[Категория:Машинное обучение]] [[Категория:Классификация]] [[Категория:Энциклопедия анализа данных]]

• Шаблон:Nobr
• Шаблон:Stub
• Шаблон:TOCright
• Шаблон:ВсеАвторы
• Шаблон:Заготовка
• Шаблон:Книга
• Шаблон:Монография
• Шаблон:Переводы
• Шаблон:Подробнее
• Публикация:Hastie 2001 The Elements of Statistical Learning
• Публикация:Вапник 1974 Теория распознавания образов
• Публикация:Вапник 1979 Восстановление зависимостей
• Публикация:Вапник 74
• Публикация:Вапник 79

Возврат к странице Линейный классификатор.