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

У галузі машинного навчання метою статистичної класифікації є використання характеристик об'єкту для ідентифікації класу (або групи), до якої він належить. Ліні́йний класифіка́тор (Шаблон:Lang-en) досягає цього ухваленням рішення про класифікацію на основі значення лінійної комбінації цих характеристик. Характеристики об'єкту відомі також як значення ознак, і зазвичай представляються машині у векторі, що називається вектором ознак. Такі класифікатори добре працюють для таких практичних задач, як класифікація документів, і, загальніше, для задач із багатьма змінними (ознаками), досягаючи рівнів точності, порівнянних з нелінійними класифікаторами, у той же час беручи менше часу на тренування та застосування.Шаблон:R

Визначення

В цьому випадку чорні та білі точки може бути класифіковано нескінченною кількістю лінійних класифікаторів. H1 (синій) класифікує їх правильно, як і H2 (червоний). H2 може вважатися «кращим» у тому сенсі, що він також є якнайдальшим від обох груп. H3 (зелений) не здатен правильно класифікувати ці точки.

Якщо вектор ознак на вході класифікатора є дійсним вектором $\overrightarrow{x}$, то вихідною оцінкою є

$y=f(\overrightarrow{w}\cdot \overrightarrow{x})=f\left(\sum _j{w}_j{x}_j\right),$

де $\overrightarrow{w}$ є дійсним вектором вагових коефіцієнтів, а f — функцією, яка перетворює скалярний добуток двох векторів на бажаний вихід. (Іншими словами, $\overrightarrow{w}$ є 1-формою, або лінійним функціоналом, що відображує $\overrightarrow{x}$ на R.) Ве́ктора вагових коефіцієнтів $\overrightarrow{w}$ навчаються з набору мічених тренувальних зразків. Часто f є простою функцією, яка відображує всі значення понад певний поріг до першого класу, а всі інші — до другого. Складніша f може давати ймовірність приналежності елемента до певного класу.

Для двокласової задачі класифікації роботу лінійного класифікатора можна візуалізувати розділенням вхідного простору високої вимірності гіперплощиною: всі точки по один бік від гіперплощини класифікуються як «так», а всі інші — як «ні».

Лінійний класифікатор часто застосовується в ситуаціях, коли швидкість класифікації є проблемою, оскільки часто він є найшвидшим класифікатором, особливо коли $\overrightarrow{x}$ є розрідженим. Лінійний класифікатор також часто дуже добре працює тоді, коли число вимірів $\overrightarrow{x}$ є великим, як у класифікації документів, де кожен з елементів $\overrightarrow{x}$ зазвичай є кількістю траплянь якогось слова в документі (див. документно-термінну матрицю). У таких випадках класифікатор повинен бути добре регуляризованим.

Породжувальні та розрізнювальні моделі

Є два широкі класи методів визначення параметрів лінійного класифікатора $\overrightarrow{w}$. Вони можуть бути породжувальними та розрізнювальними моделями. Методи першого класу моделюють функції умовної густини $P(\overrightarrow{x}|\mathrm{c}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s})$. До прикладів таких алгоритмів належать:

• Лінійний дискримінантний аналіз (або лінійний дискримінант Фішера) (ЛДА, Шаблон:Lang-en) — передбачає ґаусові моделі умовної густини.
• Наївний баєсів класифікатор з поліноміальними або багатовимірними моделями подій Бернуллі.

Другий набір методів включає розрізнювальні моделі, які намагаються максимізувати якість виходу на тренувальному наборі. Додаткові члени в тренувальній функції витрат можуть легко виконувати регуляризацію кінцевої моделі. До прикладів розрізнювального тренування лінійних класифікаторів належать:

• Логістична регресія — оцінка максимальної правдоподібності $\overrightarrow{w}$, виходячи з того, що спостережуваний тренувальний набір було породжено біноміальною моделлю, яка залежить від виходу класифікатора.
• Перцептрон — алгоритм, який намагається виправити всі помилки, що зустрілися в тренувальному наборі.
• Опорно-векторна машина — алгоритм, який максимізує розділення між гіперплощиною рішення та зразками тренувального набору.

Зауваження: Незважаючи на свою назву, ЛДА в цій систематиці не належить до класу розрізнювальних моделей. Проте його назва має сенс, коли ми порівнюємо ЛДА з іншим основним алгоритмом зниження розмірності, методом головних компонент (МГК, Шаблон:Lang-en). ЛДА є алгоритмом керованого навчання, який використовує мітки даних, тоді як МГК є алгоритмом некерованого навчання, який мітки ігнорує. У підсумку, ця назва є історичним артефактом.Шаблон:Rp

Розрізнювальне тренування часто видає вищу точність, ніж моделювання функцій умовної густини. Проте робота з пропущеними даними часто є простішою з моделями умовної густини.

Всі перелічені вище алгоритми лінійної класифікації може бути перетворено на нелінійні алгоритми, що діють на відмінному вхідному просторі $\phi (\overrightarrow{x})$, за допомогою ядрового трюку.

Розрізнювальне тренування

Розрізнювальне тренування лінійних класифікаторів, як правило, здійснюється керованим чином, за допомогою алгоритму оптимізації, якому надається тренувальний набір із бажаними виходами, та функція втрат, яка задає міру невідповідності між виходами класифікатора, та бажаними. Таким чином, алгоритм навчання розв'язує задачу оптимізації наступного вигляду:

$\arg \underset{𝐰}{\min }R(𝐰)+C\sum _{i=1}^{N}L(y_i,{𝐰}^{𝖳}{𝐱}_i)$

де

• Шаблон:Math — вектор параметрів класифікатора,
• Шаблон:Math — функція втрат, яка задає міру невідповідності між передбаченням класифікатора та справжнім виходом Шаблон:Mvar для Шаблон:Mvar-того тренувального зразка,
• Шаблон:Math — функція регуляризації, яка запобігає завеликим значенням параметрів (що спричиняє перенавчання), і
• Шаблон:Mvar — скалярна стала (встановлена користувачем алгоритму навчання), яка контролює баланс між регуляризацією та функцією втрат.

До популярних функцій втрат належать заві́сні втрати (для лінійних ОВМ) та Шаблон:Нп (для лінійної логістичної регресії). Якщо функція регуляризації Шаблон:Mvar є опуклою, то наведене вище є опуклою задачею.Шаблон:R Існує багато алгоритмів розв'язання таких задач; до популярних для лінійної класифікації належать (стохастичний) градієнтний спуск, Шаблон:Нп, координатний спуск та методи Ньютона.

Див. також

• Зворотне поширення
• Лінійна регресія
• Перцептрон
• Шаблон:Нп
• Опорно-векторні машини
• Шаблон:Нп

Література

1. Y. Yang, X. Liu, "A re-examination of text categorization", Proc. ACM SIGIR Conference, pp. 42–49, (1999). paper @ citeseer Шаблон:Webarchive Шаблон:Ref-en
2. R. Herbrich, "Learning Kernel Classifiers: Theory and Algorithms," MIT Press, (2001). ISBN 0-262-08306-X Шаблон:Ref-en