Просмотр кода страницы Линейный классификатор

'''Линейный классификатор''' — способ решения [[Задача классификации|задач классификации]], когда  решение принимается на основании действия [[Линейный оператор|линейного оператора]] над входными данными. Класс задач, которые можно решать с помощью линейных классификаторов, обладают, соответственно, свойством  [[Линейная сепарабельность|линейной сепарабельности]].

== Определение ==
[[Image:Svm separating hyperplanes.png|thumb|right|На картинке множества чёрных и белых шаров разделяются синей и красной линией. При этом красная линия проводит более точную классификацию, потому что она максимально отстоит от обоих множеств. Зелёная линия не является линейным классификатором,  она не разделяет два множества.]]

Пусть вектор <math>\vec x</math> из действительных чисел представляет собой входные данные, а на выходе классификатора вычисляется показатель y по формуле:

:<math>y = f(\vec{w}\cdot\vec{x}) = f\left(\sum_j w_j x_j\right),</math>

здесь <math>\vec w</math> - действительный вектор весов, а  ''f'' - функция преобразования [[Скалярное произведение|скалярного произведения]]. (Иными словами, вектор весов <math>\vec{w}</math> - [[ковариантный вектор]] или [[линейная форма]] отображения  <math>\vec x</math> в '''R'''.) Значения весов вектора  <math>\vec w</math> определяются в ходе [[машинное обучение|машинного обучения]] на подготовленных образцах. Функция ''f'' обычно простая пороговая функция, отделяющая один класс объектов от другого. В более сложных случаях Функция ''f'' имеет смысл вероятности того или иного решения.

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

Линейный классификатор используется когда важно проводить быстрые вычисления с большой скоростью. Он неплохо работает, когда входной вектор  <math>\vec x</math> разрежен. Линейные классификаторы могут хорошо срабатывать в многомерном пространстве, например, для классификации документов по [[Терм-документная матрица|матрице встречаемости слов]]. В подобных случаях считается, что объекты [[регуляризация (математика)|хорошо регуляризируемы]].

== Генеративная и дискриминативная модели ==
Существует два подхода к определению параметров  <math>\vec w</math> для линейного классификатора - генеративные или дискриминативные модели.<ref>T. Mitchell, [http://www.cs.cmu.edu/~tom/mlbook/NBayesLogReg.pdf Generative and Discriminative Classifiers: Naive Bayes and Logistic Regression.] {{Wayback|url=http://www.cs.cmu.edu/~tom/mlbook/NBayesLogReg.pdf |date=20210224155910 }} Draft Version, 2005</ref><ref>A. Y. Ng and M. I. Jordan. [http://www.cs.berkeley.edu/~jordan/papers/ng-jordan-nips01.ps On Discriminative vs. Generative Classifiers: A comparison of logistic regression and Naive Bayes.] {{Wayback|url=http://www.cs.berkeley.edu/~jordan/papers/ng-jordan-nips01.ps |date=20160304200258 }}  in NIPS 14, 2002.</ref>

Генеративная модель использует [[условное распределение]] <math>P(\vec x|{\rm class})</math>. Например:
* [[Дискриминантный анализ]] (LDA) — предполагает [[нормальное распределение]] по Гауссу. <ref>R.O. Duda, P.E. Hart, D.G. Stork, "Pattern Classification", Wiley, (2001). ISBN 0-471-05669-3</ref>{{rp|117}}
* [[Наивный байесовский классификатор]] с Бернуллиевской моделью событий.

Дискриминативные модели стремятся улучшить качество выходных данных на наборе образцов для обучения. Например:
* [[Логистическая регрессия]] — стремление достичь максимального сходства через вектор of <math>\vec w</math> из предположения, что наблюдаемый набор образцов генерировался в виде биномиальной модели от выходных данных.
* Простой [[Перцептрон]] — алгоритм коррекции всех ошибок на входном наборе образцов.
* [[Метод опорных векторов]] — алгоритм расширения разделительной зоны в гиперплоскости решений между образцами входных данных.

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

=== Дискриминативное обучение ===
Обучение при использовании дискриминативных моделей строится через "[[Обучение с учителем]]" , то есть через процесс [[Оптимизация (математика)|оптимизации]] выходных данных на заданных образцах для обучения. При этом определяется [[функция потерь]], измеряющая несогласование между выходными данными и желаемыми результатами.  Формально задача обучения (как оптимизации) записывается как:
<ref name="ieee">{{статья |заглавие=Recent Advances of Large-Scale Linear Classification |издание={{Нп3|Proceedings of the IEEE|Proc. IEEE||Proceedings of the IEEE}} |том=100 |номер=9 |язык=en |тип=journal |автор=Guo-Xun Yuan; Chia-Hua Ho; Chih-Jen Lin |год=2012}}</ref>

:<math>\underset{\mathbf{w}}{\arg\!\min} \;R(\mathbf{w}) + C \sum_{i=1}^N L(y_i, \mathbf{w}^\mathsf{T} \mathbf{x}_i)</math>

где

* {{math|'''w'''}} - искомый  вектор весов классификатора,
* {{math|''L''(''y<sub>i</sub>'', '''w'''<sup>T</sup>'''x'''<sub>''i''</sub>)}} [[функция потерь]] (то есть, несоответствие между выходом классификатора и истинными значениями {{mvar|y<sub>i</sub>}} для {{mvar|i}}-го образца),
* {{math|''R''('''w''')}} - функция регуляризации, которая не позволяет параметрам выходить за разумные пределы (по причине [[переобучение|переобучения]]),
* {{mvar|C}} - константа, определяемая пользователем алгоритма обучения для балансировки между регуляризацией и функцией потерь.

Наиболее популярны  кусочно-линейная функция  и логарифмическая ([[Перекрёстная энтропия]]) функции потерь. Если функция регуляризации {{mvar|R}} [[Выпуклая функция|выпуклая]], то ставится проблема выпуклой оптимизации{{r|ieee}}. Для решения этих задач используется много алгоритмов, в частности метод стохастического градиентного спуска,  [[Градиентный спуск|метод градиентного спуска]], [[L-BFGS]], [[метод координатного спуска]] и [[Метод Ньютона]].{{Нет АИ|19|8|2022}}

== См. также ==
* [[Метод обратного распространения ошибки]]
* [[Линейная регрессия]]
* [[Перцептрон]]
* [[Метод опорных векторов]]

== Примечания ==
<references/>

== Литература ==
# Y. Yang, X. Liu, "A re-examination of text categorization", Proc. ACM SIGIR Conference, pp.&nbsp;42–49, (1999). [http://citeseer.ist.psu.edu/yang99reexamination.html paper @ citeseer]
# R. Herbrich, "Learning Kernel Classifiers: Theory and Algorithms," MIT Press, (2001). ISBN 0-262-08306-X

== Ссылки ==
{{Википедия|Линейный классификатор}}

{{DEFAULTSORT:Linear Classifier}}
[[Категория:Применение искусственного интеллекта]]
[[Категория:Машинное обучение]]