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

Определение

Пусть вектор ${\displaystyle {\vec {x}}}$ из действительных чисел представляет собой входные данные, а на выходе классификатора вычисляется показатель y по формуле:

${\displaystyle y=f({\vec {w}}\cdot {\vec {x}})=f\left(\sum _{j}w_{j}x_{j}\right),}$

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

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

Линейный классификатор используется когда важно проводить быстрые вычисления с большой скоростью. Он неплохо работает, когда входной вектор ${\displaystyle {\vec {x}}}$ разрежен. Линейные классификаторы могут хорошо срабатывать в многомерном пространстве, например, для классификации документов по матрице встречаемости слов . В подобных случаях считается, что объекты хорошо регуляризируемы .

Генеративная и дискриминативная модели

Существует два подхода к определению параметров ${\displaystyle {\vec {w}}}$ для линейного классификатора - генеративные или дискриминативные модели.

Генеративная модель использует условное распределение ${\displaystyle P({\vec {x}}|{\rm {class}})}$ . Например:

• Дискриминантный анализ (LDA) — предполагает нормальное распределение по Гауссу. ^:117
• Наивный байесовский классификатор с Бернуллиевской моделью событий.

Дискриминативные модели стремятся улучшить качество выходных данных на наборе образцов для обучения. Например:

• Логистическая регрессия — стремление достичь максимального сходства через вектор of ${\displaystyle {\vec {w}}}$ из предположения, что наблюдаемый набор образцов генерировался в виде биномиальной модели от выходных данных.
• Простой Перцептрон — алгоритм коррекции всех ошибок на входном наборе образцов.
• Метод опорных векторов — алгоритм расширения разделительной зоны в гиперплоскости решений между образцами входных данных.

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

Дискриминативное обучение

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

${\displaystyle {\underset {\mathbf {w} }{\arg \!\min }}\;R(\mathbf {w} )+C\sum _{i=1}^{N}L(y_{i},\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i})}$

где

• w - искомый вектор весов классификатора,
• L ( y _i , w ^T x _i ) функция потерь (то есть, несоответствие между выходом классификатора и истинными значениями y _i для i -го образца),
• R ( w ) - функция регуляризации, которая не позволяет параметрам выходить за разумные пределы (по причине переобучения ),
• C - константа, определяемая пользователем алгоритма обучения для балансировки между регуляризацией и функцией потерь.

Наиболее популярны кусочно-линейная функция и логарифмическая ( Перекрёстная энтропия ) функции потерь. Если функция регуляризации R выпуклая , то ставится проблема выпуклой оптимизации . Для решения этих задач используется много алгоритмов, в частности метод стохастического градиентного спуска, метод градиентного спуска , , и Метод Ньютона . ^{[ источник не указан 509 дней ]}

См. также

• Метод обратного распространения ошибки
• Линейная регрессия
• Перцептрон
• Метод опорных векторов

Примечания

1. T. Mitchell, от 24 февраля 2021 на Wayback Machine Draft Version, 2005
2. A. Y. Ng and M. I. Jordan. от 4 марта 2016 на Wayback Machine in NIPS 14, 2002.
3. R.O. Duda, P.E. Hart, D.G. Stork, "Pattern Classification", Wiley, (2001). ISBN 0-471-05669-3
4. ↑ Guo-Xun Yuan; Chia-Hua Ho; Chih-Jen Lin. Recent Advances of Large-Scale Linear Classification (англ.) // (англ.) ( : journal. — 2012. — Vol. 100 , no. 9 .

Литература

1. Y. Yang, X. Liu, "A re-examination of text categorization", Proc. ACM SIGIR Conference, pp. 42–49, (1999).
2. R. Herbrich, "Learning Kernel Classifiers: Theory and Algorithms," MIT Press, (2001). ISBN 0-262-08306-X