Главная

Зачем нужен алгоритм Хо-Кашьяпа?

2016-10-16 в 8:57, admin, рубрики: алгоритм хо-кашьяпа, Алгоритмы, ликбез, линейная регрессия, машинное обучение

Недавно на Хабре появилась публикация про алгоритм Хо-Кашьяпа (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)):

Встаёт вопрос — можно ли как-то избавиться от этой особенности поведения?

Задача линейной классификации

Для начала формализуем предмет беседы.

Дана матрица , каждая строчка X_i которой соответствует признаковому описанию объекта (включая константу ) и вектора меток классов , где $y_i in {+1, -1}$ — метка объекта . Мы хотим построить линейный классификатор вида 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=y на и назовём получившуюся в левой части матрицу 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_i отвечает за расстояние от элемента до разделяющей прямой ( Yw=b ). Поскольку мы хотим, чтобы все элементы были классифицированы правильно, мы вводим условие b > 0 . Тогда задача сведётся к min sum (w Y_i - b_i)^2 и будет решаться как $w=Y^{+} y$ . Можно вручную подобрать такие значения , что получившаяся плоскость будет разделять нашу выборку:

>>> 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^{(0)}$ обычно берут равным [2]):

Вычислить коэффициенты МНК-регрессии ( $w^{(k)}=Y^{+} b^{(k)}$ ).
Вычислить вектор отступов $b^{(k+1)}$ .
Если решение не сошлось ( $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}|)$ , где — шаг градиентного спуска, уменьшающийся по ходу решения задачи.

>>> 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.]])

В случае линейно-разделимой выборки алгоритм всегда сходится и сходится к разделяющей плоскости (если все элементы градиента по неотрицательны, то они все нулевые).

В случае линейно-неразделимой выборки, функция потерь может быть сколь угодно малой, поскольку достаточно домножить и на константу для изменения её значения и в принципе алгоритм может и не сойтись. Поиск не даёт никаких конкретных рекомендаций на эту тему.

Связь алгоритма Хо-Кашьяпа и линейного 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 - 2max(0, 1 - w Y_i)$

В свою очередь, функция потерь линейного SVM имеет вид:

$min_{w} lambda ||w||^2 + frac{1}{N} sum_{i} max(0, 1 - w Y_i)$

Таким образом, задача, решаемая алгоритмом Хо-Кашьяпа, представляет собой некоторый аналог SVM с квадратичной функцией потерь (она сильнее штрафует за выбросы далеко от разделяющей плоскости).

Многомерный случай

Можно вспомнить, что МНК-регрессия является аналогом двухклассового линейного дискриминанта Фишера (их решения совпадают с точностью до константы). Алгоритм Хо-Кашьпяпа можно применить и для случая классов — в этом и становятся матрицами и размера D times K и N times K соотвественно, где — размерность задачи, а — число объектов. В этом случае в столбцах, соответствующих неверным классам, должны стоять отрицательные значения.

Благодарности

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) http://web.khu.ac.kr/~tskim/PatternClass Lec Note 07-1.pdf
(4) А.Е. Лепский, А.Г. Броневич Математические методы распознавания образов. Курс лекций
(5) Ту Дж., Гонсалес Р. Принципы распознавания образов
(6) Р.Дуда, П.Харт Распознавание образов и анализ сцен

Автор: Drino

Источник