Доброго дня!
У цій статті я хочу розповісти про проблему класифікації даних методом опорних векторів (Support Vector Machine, SVM). Така класифікація має досить широке застосування: від розпізнавання образів або створення спам-фільтрів до обчислення розподілу гарячих алюмінієвих частинок в ракетних вихлопах.
Спочатку декілька слів про початкове завдання. Завдання класифікації полягає у визначенні до якого класу з, як мінімум, двох відомих відноситься даний об'єкт. Зазвичай таким об'єктом є вектор в n-мірному речовому просторі. Координати вектора описують окремі атрибути об'єкта. Наприклад, колір c, визначений у моделі RGB, є вектором у тривимірному просторі: c=(red, green, blue).
Якщо класів всього два («спам/не спам», «давати кредит/не давати кредит», «червоне/чорне»), то завдання називається бінарною класифікацією. Якщо класів декілька - багатокласова (мультикласова) класифікація. Також можуть бути зразки кожного класу - об'єкти, про які заздалегідь відомо до якого класу вони належать. Такі завдання називають навчанням з учителем, а відомі дані називаються навчальною вибіркою. (Примітка: якщо класи спочатку не задані, то перед нами завдання кластеризації.)
Метод опорних векторів, розглянутий у цій статті, належить до навчання з учителем.
Отже, математичне формулювання завдання класифікації таке: нехай X - простір об'єктів (наприклад,), Y - наші класи (наприклад, Y = {-1,1}). Дана навчальна вибірка: . Потрібно побудувати функцію (класифікатор), який співставляє клас y довільному об'єкту x.
Метод опорних векторів
Цей метод спочатку відноситься до бінарних класифікаторів, хоча існують способи змусити його працювати і для завдань мультикласифікації.
Ідея методу
Ідею методу зручно проілюструвати на наступному простому прикладі: дані точки на площині, розбиті на два класи (рис. 1). Проведемо лінію, що розділяє ці два класи (червона лінія на рис. 1). Далі, всі нові точки (не з навчальної вибірки) автоматично класифікуються наступним чином:
точка вище прямої потрапляє в клас A,
точка нижче прямої - в клас B.
Таку пряму назвемо розділяючою прямою. Однак, в просторах високих розмірностей пряма вже не буде розділяти наші класи, так як поняття «нижче прямої» або «вище прямої» втрачає всякий сенс. Тому замість прямих необхідно розглядати гіперплоскості - простори, розмірність яких на одиницю менша, ніж розмірність вихідного простору. Наприклад, гіперплоскість - це звичайна плоскість.
У нашому прикладі існує декілька прямих, які поділяють два класи (рис. 2):
З точки зору точності класифікації найкраще вибрати пряму, відстань від якої до кожного класу максимально. Іншими словами, виберемо ту пряму, яка поділяє класи найкращим чином (червона пряма на рис.2). Така пряма, а в загальному випадку - гіперплоскість, називається оптимальною гіперплоскістю.
Вектори, що лежать ближче всіх до гіперплоскості, називаються опорними векторами (support vectors). На малюнку 2 вони позначені червоним.
Трохи математики
Нехай є навчальна вибірка: .
Метод опорних векторів будує класифікуючу функцію F у вигляді,
де - скалярний твір, w - нормальний вектор до розділяє гіперплоскості, b - допоміжний параметр. Ті об'єкти, для яких F (x) = 1 потрапляють в один клас, а об'єкти з F (x) = -1 - в інший. Вибір саме такої функції невипадковий: будь-яка гіперплоскість може бути вказана у вигляді для деяких w і b.
Далі, ми хочемо вибрати такі w і b які максимізують відстань до кожного класу. Можна підрахувати, що дана відстань дорівнює. Проблема знаходження максимуму еквівалентна проблемі знаходження мінімуму. Запишемо все це у вигляді завдання оптимізації:
яка є стандартним завданням квадратичного програмування і вирішується за допомогою множників Лагранжа. Опис цього методу можна знайти у Вікіпедії.
Лінійна нероздільність
На практиці випадки, коли дані можна розділити гіперплоскістю, або, як ще кажуть, лінійно, досить рідкісні. Приклад лінійної нероздільності можна бачити на малюнку 3:
У цьому випадку чинять так: всі елементи навчальної вибірки вкладаються в простір X більш високої розмірності за допомогою спеціального відображення. При цьому відображення вибирається так, щоб у новому просторі X вибірка була лінійно розділима.
Класифікуюча функція F приймає вигляд. Вираз називається ядром класифікатора. З математичної точки зору ядром може служити будь-яка позитивно визначена симетрична функція двох змінних. Позитивна визначеність необхідно для того, щоб відповідна функція Лагранжа в завданні оптимізації була обмежена знизу, тобто завдання оптимізації була б коректно визначена.
Точність класифікатора залежить, зокрема, від вибору ядра. На відео можна побачити ілюстрірацію класифікації за допомогою поліноміального ядра:
Найчастіше на практиці зустрічаються наступні ядра:
Поліноміальне:
Радіальна базисна функція:
Гауссова радіальна базисна функція:
Сигмоїд:
Висновок і література
Серед інших класифікаторів хочу відзначити також метод релевантних векторів (Relevance Vector Machine, RVM). На відміну від SVM цей метод дає ймовірності, з якими об'єкт належить даному класу. Тобто. якщо SVM говорить «x належить класу А» «, то RVM скаже» x належить класу А з імовірністю p і класу B з імовірністю 1-p «».
1. Christopher M. Bishop. Pattern recognition and machine learning, 2006.
2. К. В. Воронцов. Лекції за методом опорних векторів.