В области машинного обучения целью статистической классификации является использование характеристик объекта для определения того, к какому классу (или группе) он принадлежит. Линейный классификатор достигает этого путем принятия решения классификации , основанное на значении в линейной комбинации характеристик. Характеристики объекта также известны как значения признаков и обычно представляются машине в виде вектора, называемого вектором признаков . Такие классификаторы хорошо подходят для практических задач, таких как классификация документов , и в более общем плане для задач со многими переменными ( функциями), достигая уровней точности, сравнимых с нелинейными классификаторами, при этом требуется меньше времени на обучение и использование. [1]
Определение
Если входной вектор признаков для классификатора является действительным вектором, то результат будет
где - вещественный вектор весов, а f - функция, которая преобразует скалярное произведение двух векторов в желаемый результат. (Другими словами,является одной формой или линейный функционал отображенияна R. ) Весовой векторобучается из набора помеченных обучающих выборок. Часто f является пороговой функцией , которая отображает все значениявыше определенного порога для первого класса и всех остальных значений для второго класса; например,
Более сложное f может дать вероятность того, что предмет принадлежит определенному классу.
Для задачи двухклассовой классификации можно визуализировать работу линейного классификатора как разделение многомерного входного пространства гиперплоскостью : все точки на одной стороне гиперплоскости классифицируются как «да», а другие - как "нет".
Линейный классификатор часто используется в ситуациях, когда скорость классификации является проблемой, поскольку часто это самый быстрый классификатор, особенно когда редко. Кроме того, линейные классификаторы часто очень хорошо работают, когда количество измерений вбольшой, как в классификации документов , где каждый элемент вобычно представляет собой количество вхождений слова в документ (см. матрицу "документ-термин" ). В таких случаях классификатор должен быть хорошо упорядочен .
Генеративные модели против дискриминационных моделей
Существует два широких класса методов определения параметров линейного классификатора. . Это могут быть генеративные и дискриминационные модели. [2] [3] Методы модельных функций условной плотности первого класса . Примеры таких алгоритмов включают:
- Линейный дискриминантный анализ (LDA) - предполагает модели условной плотности Гаусса.
- Наивный байесовский классификатор с полиномиальными или многомерными моделями событий Бернулли.
Второй набор методов включает в себя дискриминационные модели , которые пытаются максимизировать качество выходных данных на обучающем наборе . Дополнительные члены в функции стоимости обучения могут легко выполнить регуляризацию окончательной модели. Примеры дискриминационного обучения линейных классификаторов включают:
- Логистическая регрессия - оценка максимального правдоподобия предполагая, что наблюдаемый обучающий набор был сгенерирован биномиальной моделью, которая зависит от выходных данных классификатора.
- Perceptron - алгоритм, который пытается исправить все ошибки, обнаруженные в обучающем наборе.
- Линейный дискриминантный анализ Фишера - алгоритм (отличный от «LDA»), который максимизирует отношение разброса между классами к разбросу внутри класса, без каких-либо других предположений. По сути, это метод уменьшения размерности для двоичной классификации. [4]
- Машина опорных векторов - алгоритм, который максимизирует разницу между гиперплоскостью решения и примерами в обучающем наборе.
Примечание: Несмотря на свое название, LDA не принадлежит к классу дискриминационных моделей в этой таксономии. Однако его название имеет смысл, когда мы сравниваем LDA с другим основным алгоритмом уменьшения линейной размерности : анализом главных компонентов (PCA). LDA - это алгоритм обучения с учителем , который использует метки данных, а PCA - это алгоритм обучения без учителя , который игнорирует метки. Подводя итог, название - исторический артефакт. [5] : 117
Дискриминационное обучение часто дает более высокую точность, чем моделирование функций условной плотности [ необходима цитата ] . Однако с моделями условной плотности часто проще обрабатывать недостающие данные [ необходима ссылка ] .
Все алгоритмы линейного классификатора, перечисленные выше, могут быть преобразованы в нелинейные алгоритмы, работающие в другом пространстве ввода. , используя трюк с ядром .
Дискриминационное обучение
Дискриминационное обучение линейных классификаторов обычно происходит под контролем с помощью алгоритма оптимизации, которому задается обучающий набор с желаемыми выходными данными и функцией потерь, которая измеряет несоответствие между выходными данными классификатора и желаемыми выходными данными. Таким образом, алгоритм обучения решает задачу оптимизации вида [1]
где
- w - вектор параметров классификатора,
- L ( y i , w T x i ) - функция потерь, которая измеряет несоответствие между предсказанием классификатора и истинным выходом y i для i -го обучающего примера,
- R ( w ) - этофункция регуляризации, которая не позволяет параметрам становиться слишком большими (вызывая переобучение ), и
- C - скалярная константа (устанавливается пользователем алгоритма обучения), которая контролирует баланс между регуляризацией и функцией потерь.
Популярные функции потерь включают потерю на шарнире (для линейных SVM) и логарифмическую потерю (для линейной логистической регрессии). Если функция регуляризации R является выпуклым , то выше , является выпуклой задачей . [1] Для решения таких проблем существует множество алгоритмов; популярные методы линейной классификации включают ( стохастический ) градиентный спуск , L-BFGS , координатный спуск и методы Ньютона .
Смотрите также
- Обратное распространение
- Линейная регрессия
- Перцептрон
- Квадратичный классификатор
- Опорные векторные машины
- Winnow (алгоритм)
Заметки
- ^ a b c Го-Сюнь Юань; Чиа-Хуа Хо; Чих-Джен Линь (2012). «Последние достижения крупномасштабной линейной классификации» (PDF) . Proc. IEEE . 100 (9).
- ^ Т. Митчелл, Генеративные и дискриминационные классификаторы: наивный байесовский метод и логистическая регрессия. Черновая версия, 2005 г.
- ↑ AY Ng и MI Jordan. О дискриминирующих и генеративных классификаторах: сравнение логистической регрессии и наивного Байеса. в НИПС 14, 2002.
- ^ RO Дуда, PE Hart, DG Аист "Pattern Классификация", Wiley, (2001). ISBN 0-471-05669-3
- ^ RO Дуда, PE Hart, DG Аист "Pattern Классификация", Wiley, (2001). ISBN 0-471-05669-3
дальнейшее чтение
- Y. Yang, X. Liu, "Пересмотр категоризации текста", Proc. Конференция ACM SIGIR, стр. 42–49, (1999). бумага @ citeseer
- Р. Хербрих, "Обучающиеся классификаторы ядра: теория и алгоритмы", MIT Press, (2001). ISBN 0-262-08306-X