- PVSM.RU - https://www.pvsm.ru -
Недавно на Хабре появилась публикация про алгоритм Хо-Кашьяпа [1] (Ho-Kashyap procedure, он же — алгоритм НСКО, наименьшей среднеквадратичной ошибки). Мне она показалась не очень понятной и я решил разобраться в теме сам. Выяснилось, что в русскоязычном интернете тема не очень хорошо разобрана, поэтому я решил оформить статью по итогам поисков.
Несмотря на бум нейросетей в машинном обучении, алгоритмы линейной классификации остаются гораздо более простыми в использовании и интерпретации. Но при этом иногда вовсе не хочется пользоваться сколько-нибудь продвинутыми методами, вроде метода опорных векторов [2] или логистической регрессии [3] и возникает искушение загнать все данные в одну большую линейную МНК-регрессию [4], тем более её прекрасно умеет строить даже MS Excel.
Проблема такого подхода в том, что даже если входные данные линейно разделимы, то получившийся классификатор может их не разделять. Например, для набора точек , получим разделяющую прямую (пример позаимствован из (1)):
Встаёт вопрос — можно ли как-то избавиться от этой особенности поведения?
Для начала формализуем предмет беседы.
Дана матрица , каждая строчка которой соответствует признаковому описанию объекта (включая константу ) и вектора меток классов , где — метка объекта . Мы хотим построить линейный классификатор вида .
>>> 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]])
Самый простой способ это сделать — построить МНК-регрессию для , то есть минимизировать сумму квадратов отклонений . Оптимальные веса можно найти по формуле , где — псевдообратная матрица. Таким образом получена картинка из начала статьи.
>>> 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]])
Для удобства записи мы поэлементно домножим каждую строчку неравенства на и назовём получившуюся в левой части матрицу (здесь означает построчное умножение). Тогда условие для МНК-регрессии сведётся к виду , а задача минимизации — к минимизации .
>>> Y = y * X
>>> Y
array([[ 6, 9, 1],
[ 5, 7, 1],
[ -5, -9, -1],
[ 0, -10, -1]])
На этом месте можно вспомнить, что условие разделения классов это или , и поскольку мы хотим разделять классы, то надо решать эту задачу.
Введём вектор , в котором отвечает за расстояние от элемента до разделяющей прямой (). Поскольку мы хотим, чтобы все элементы были классифицированы правильно, мы вводим условие . Тогда задача сведётся к и будет решаться как . Можно вручную подобрать такие значения , что получившаяся плоскость будет разделять нашу выборку:
>>> 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]])
Алгоритм Хо-Кашьяпа предназначен для того, чтобы подобрать автоматически. Схема алгоритма ( — номер шага, обычно берут равным [2]):
Вектор отступов хочется вычислить каким-нибудь путём вроде , поскольку это минимизирует функцию потерь . К сожалению, условие не даёт нам этого сделать, и вместо этого предлагается делать шаг по положительной части градиента функции потерь : , где — шаг градиентного спуска, уменьшающийся по ходу решения задачи.
>>> 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 имеет вид:
Таким образом, задача, решаемая алгоритмом Хо-Кашьяпа, представляет собой некоторый аналог SVM с квадратичной функцией потерь (она сильнее штрафует за выбросы далеко от разделяющей плоскости).
Можно вспомнить, что МНК-регрессия является аналогом двухклассового линейного дискриминанта Фишера [5] (их решения совпадают с точностью до константы). Алгоритм Хо-Кашьпяпа можно применить и для случая классов — в этом и становятся матрицами и размера и соотвественно, где — размерность задачи, а — число объектов. В этом случае в столбцах, соответствующих неверным классам, должны стоять отрицательные значения.
parpalak [6] за удобный редактор.
rocket3 [7] за оригинальную статью.
(1) http://www.csd.uwo.ca/~olga/Courses/CS434a_541a/Lecture10.pdf [8]
(2) http://research.cs.tamu.edu/prism/lectures/pr/pr_l17.pdf [9]
(3) http://web.khu.ac.kr/~tskim/PatternClass Lec Note 07-1.pdf [10]
(4) А.Е. Лепский, А.Г. Броневич Математические методы распознавания образов. Курс лекций
(5) Ту Дж., Гонсалес Р. Принципы распознавания образов
(6) Р.Дуда, П.Харт Распознавание образов и анализ сцен
Автор: Drino
Источник [11]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/199756
Ссылки в тексте:
[1] алгоритм Хо-Кашьяпа: https://habrahabr.ru/post/312600/
[2] метода опорных векторов: https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BE%D0%BF%D0%BE%D1%80%D0%BD%D1%8B%D1%85_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BE%D0%B2
[3] логистической регрессии: https://ru.wikipedia.org/wiki/%D0%9B%D0%BE%D0%B3%D0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F
[4] линейную МНК-регрессию: https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F
[5] линейного дискриминанта Фишера: http://www.machinelearning.ru/wiki/index.php?title=%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B8%D1%81%D0%BA%D1%80%D0%B8%D0%BC%D0%B8%D0%BD%D0%B0%D0%BD%D1%82_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0
[6] parpalak: https://habrahabr.ru/users/parpalak/
[7] rocket3: https://habrahabr.ru/users/rocket3/
[8] http://www.csd.uwo.ca/~olga/Courses/CS434a_541a/Lecture10.pdf: http://www.csd.uwo.ca/~olga/Courses/CS434a_541a/Lecture10.pdf
[9] http://research.cs.tamu.edu/prism/lectures/pr/pr_l17.pdf: http://research.cs.tamu.edu/prism/lectures/pr/pr_l17.pdf
[10] http://web.khu.ac.kr/~tskim/PatternClass Lec Note 07-1.pdf: http://web.khu.ac.kr/~tskim/PatternClass%20Lec%20Note%2007-1.pdf
[11] Источник: https://habrahabr.ru/post/312774/?utm_source=habrahabr&utm_medium=rss&utm_campaign=sandbox
Нажмите здесь для печати.