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

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

Версия от 18:45, 30 апреля 2008; Vokov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Содержание

Определение

Пусть объекты описываются n числовыми признаками f_j:\: X\to\mathbb{R}, j=1,\ldots,n; Тогда пространство признаковых описаний объектов есть X=\mathbb{R}. Пусть Y — конечное множество номеров (имён, меток) классов.

В случае двух классов, Y=\{-1,+1\}, линейным классификатором называется алгоритм классификации a:\; X\to Y, имеющий вид

a(x) = \mathrm{sign}\left( \sum_{j=1}^n w_j f_j(x) - w_0 \right) = \mathrm{sign}\langle x,w \rangle,

где w_j — веса признаков, w_0 — порог принятия решения, w=(w_0,w_1,\ldots,w_n) — вектор весов, \langle x,w \rangle — скалярное произведение признакового описания объекта на вектор весов. Предполагается, что искусственно введён «константный» нулевой признак: f_{0}(x)\equiv -1.

В случае произвольного числа классов линейный классификатор определяется выражением

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,

где каждому классу соотвествует свой вектор весов w_y.

Задача настройки (обучения) классификатора заключается в том, чтобы по заданной обучающей выборке пар «объект, ответ» 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) \neq y_i \bigr].

Методы обучения линейных классификаторов различаются подходами к решению данной оптимизационной задачи.

Понятие отступа

В случае двух классов, Y=\{-1,+1\}, удобно определить для произвольного обучающего объекта x_i\in X^m величину отступа (margin):

M(x_i) = y_i \langle x_i,w \rangle.

Отступ M(x_i) отрицателен тогда и только тогда, когда алгоритм a(x) допускает ошибку на объекте x_i. Чем меньше значение отступа, тем «более ошибочным» является значение скалярного произведения \langle x_i,w \rangle.

Это наблюдение позволяет обобщить фунционал эмпирического риска:

Q(w,x) = \sum_{i=1}^m L\bigl( M(x_i) \bigr),

где L(M) — функция потерь, зависящая от отступа. Обычно используются непрерывные монотонно убывающие функции L(M), что позволяет применять численные методы оптимизации для настройки весов линейного классификатора.

Методы обучения линейных классификаторов различаются, в первую очередь, выбором функции L(M).

Методы обучения линейных классификаторов


Литература

  1. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
  2. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974.
  3. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
  4. Дуда Р., Харт П. Распознавание образов и анализ сцен. — М.: Мир, 1976.
  5. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.

Ссылки

Источник — «http://www.recognition.su/wiki/index.php?title=%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%82%D0%BE%D1%80»