Навіщо потрібен алгоритм Хо-Кашьяпа?

Нещодавно на Хабре з'явилася публікація про алгоритм Хо-Кашьяпа (Ho-Kashyap procedure, він же — алгоритм НСКО, найменшою середньоквадратичної помилки). Мені вона здалася не дуже зрозумілою і я вирішив розібратися в темі сам. З'ясувалося, що в російськомовному інтернеті тема не дуже добре розібрана, тому я вирішив оформити статтю за підсумками пошуків.

Незважаючи на бум нейромереж в машинному навчанні, алгоритми лінійної класифікації залишаються набагато більш простими у використанні та інтерпретації. Але при цьому іноді зовсім не хочеться користуватися скільки-небудь просунутими методами, начебто методу опорних векторів або логістичної регресії і виникає спокуса загнати всі дані в одну велику лінійну МНК-регресію, тим більше її прекрасно вміє будувати навіть MS Excel.

Проблема такого підходу в тому, що навіть якщо вхідні дані лінійно нероздільні, то отриманий класифікатор може не розділяти. Наприклад, для набору точок X = [(6, 9), (5, 7), (5, 9), (10, 1)], y = [1, 1, -1, -1]отримаємо розділяє пряму (0.15x_1 - 0.43x_2 + 3.21) = 0(приклад запозичений з (1)):

Latex

Постає питання — чи можна якось позбутися цієї особливості поведінки?

Завдання лінійної класифікації
Для початку формалізуємо предмет статті.

Дана матриця X, кожна строчка X_iякої відповідає признаковому опису об'єкта i(включаючи константу 1) і вектора міток класів y, де y_i \in \{+1, -1\}— мітка об'єкта i. Ми хочемо побудувати лінійний класифікатор виду sign(Xw) = y.

>>> import numpy as np
>>> X = np.array([[6, 9, 1], [5, 7, 1], [5, 9, 1], [0, 10, 1]])
>>> y = np.array([[1], [1], [-1], [-1]])

Найпростіший спосіб це зробити — побудувати МНК-регресію для Xw = y, тобто мінімізувати суму квадратів відхилень \min \sum (w X_i - y_i)^2. Оптимальні ваги можна знайти за формулою w = X^{+} y, де X^{+}— псевдообернена матриця. Таким чином отримана картинка з початку статті.

>>> w = np.dot(np.linalg.pinv(X), y)
>>> w
array([[ 0.15328467],
[-0.4379562 ],
[ 3.2189781 ]])
>>> np.dot(X, w)
array([[ 0.19708029],
[ 0.91970803],
[ 0.04379562],
[-1.16058394]])

Лінійна роздільність
Для зручності запису ми поелементно домножим кожну сходинку нерівності Xw = yyі назвемо отриману в лівій частині матрицю Y = y \times X(тут \timesозначає порядкове множення). Тоді умова для МНК-регресії зведеться до вигляду Yw = 1, а завдання мінімізації — до мінімізації \min \sum (w Y_i - 1)^2.

>>> Y = y * X
>>> Y
array([[ 6, 9, 1],
[ 5, 7, 1],
[ -5, -9, -1],
[ 0, -10, -1]])

На цьому місці можна згадати, що умова поділу класів sign(Xw) = yабо sign(Yw) = 1, і оскільки ми хочемо розділяти класи, то треба вирішувати цю задачу.

Введемо вектор b, в якому b_iвідповідає за відстань від елемента iдо розділяє прямий (Yw = b). Оскільки ми хочемо, щоб усі елементи були класифіковані правильно, ми вводимо умову b > 0. Тоді задача зведеться до \min \sum (w Y_i - b_i)^2і буде вирішуватися як w = Y^{+} y. Можна підібрати такі значення b, що вийшла площина буде розділяти нашу вибірку:

>>> b = np.ones([4, 1])
>>> b[3] = 10
>>> w = np.dot(np.linalg.pinv(Y), b)
>>> np.dot(Y, w)
array([[ 0.8540146 ],
[ 0.98540146],
[ 0.81021898],
[ 10.02919708]])

Алгоритм Хо-Кашьяпа
Алгоритм Хо-Кашьяпа призначений для того, щоб підібрати bавтоматично. Схема алгоритму (k— номер кроку, b^{(0)}зазвичай беруть рівним 1):

  1. Обчислити коефіцієнти МНК-регресії (w^{(k)} = Y^{+} b^{(k)}).
  2. Обчислити вектор відступів b^{(k+1)}.
  3. Якщо рішення не зійшлося (b^{(k)} \neq b^{(k+1)}), то повторити крок 1.
Вектор відступів хочеться обчислити яким-небудь шляхом зразок b^{(k+1)} = \max(Yw^{(k)}, 0), оскільки це мінімізує функцію втрат \min \sum (w Y_i - b_i)^2. На жаль, умова b > 0не дає нам цього зробити, і замість цього пропонується робити крок за позитивної частини градієнта функції втрат e^{(k)} = b^{k} - Yw^{(k)}: b^{(k+1)} = b^{(k)} - \mu (e^{(k)} - |e^{k}|), де \mu— крок градієнтного спуску, зменшується по ходу рішення задачі.

>>> e = -np.inf * np.ones([4, 1])
>>> b = np.ones([4, 1])
>>> while np.any(e < 0):
... w = np.dot(np.linalg.pinv(Y), b)
... e = b - np.dot(Y, w)
... b = b - e * (e < 0)
... 
>>> b
array([[ 1.],
[ 1.],
[ 1.],
[ 12.]])
>>> w
array([[ 2.],
[-1.],
[-2.]])



У випадку лінійно-разделимой вибірки алгоритм завжди сходиться і сходиться до розділяє площині (якщо всі елементи градієнта bневід'ємні, то вони всі нульові).

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

Зв'язок алгоритму Хо-Кашьяпа і лінійного SVM
Можна помітити, що якщо об'єкт класифікований правильно, то помилка в поставленої оптимізаційної задачі (\min \sum_{i} (w Y_i - b_i)^2) помилка на ньому може бути зведена до нуля. Якщо ж об'єкт класифікований неправильно, то мінімальна помилка на ньому дорівнює квадрату його відступу від розділяє прямий ((w Y_i)^2). Тоді функцію втрат можна переписати у вигляді:

\min_{w} \sum_{i} \max(0, 1 - w Y_i)^2 - 2\max(0, 1 - w Y_i)
У свою чергу, функція втрат лінійного SVM має вигляд:

\min_{w} \lambda ||w||^2 + \frac{1}{N} \sum_{i} \max(0, 1 - w Y_i)
Таким чином, задача, розв'язувана алгоритмом Хо-Кашьяпа, являє собою певний аналог SVM з квадратичною функцією втрат (вона сильніше штрафує за викиди далеко від розділяє площині).

Багатомірний випадок
Можна згадати, що МНК-регресія є аналогом двухклассового лінійного дискримінанта Фішера (їх вирішення збігаються з точністю до константи). Алгоритм Хо-Кашьпяпа можна застосувати і для випадку Kкласів — в цьому wbстають матрицями WBрозмір D \times KN \times Kвідповідно, де D— розмірність задачі, а N— число об'єктів. У цьому випадку в стовпцях, відповідних невірним класів, повинні стояти негативні значення.

Подяки
parpalak за зручний редактор.
rocket3 за оригінальну статтю.

Посилання
(1) http://www.csd.uwo.ca/~olga/Courses/CS434a_541a/Lecture10.pdf
(2) http://research.cs.tamu.edu/prism/lectures/pr/pr_l17.pdf
(3) <a href=«web.khu.ac.kr/~tskim/PatternClass%20Lec%20Note%2007-1.pdf>http://web.khu.ac.kr/~tskim/PatternClass Lec Note 07-1.pdf
(4) А. Е. Лепський, А. Р. Броневич Математичні методи розпізнавання образів. Курс лекцій
(5) Ту Дж., Гонсалес Р. Принципи розпізнавання образів
(6) Р. Дуда, П. Харт Розпізнавання образів та аналіз сцен
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.