Недавно на Хабре появилась публикация про [алгоритм Хо-Кашьяпа][1] (Ho-Kashyap procedure, он же — алгоритм НСКО, наименьшей среднеквадратичной ошибки). Мне она показалась не очень понятной и я решил разобраться в теме сам. Выяснилось, что в русскоязычном интернете тема не очень хорошо разобрана, поэтому я решил оформить статью по итогам поисков.

Несмотря на бум нейросетей в машинном обучении, алгоритмы линейной классификации остаются гораздо более простыми в использовании и интерпретации. Но при этом иногда вовсе не хочется пользоваться сколько-нибудь продвинутыми методами, вроде [метода опорных векторов][2] или [логистической регрессии][3] и возникает искушение загнать все данные в одну большую [линейную МНК-регрессию][4], тем более её прекрасно умеет строить даже MS Excel.

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

![Latex][8]

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

[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]: https://tex.s2cms.ru/svg/%20X%20%3D%20%5B(6%2C%209)%2C%20(5%2C%207)%2C%20(5%2C%209)%2C%20(10%2C%201)%5D%20
[6]: https://tex.s2cms.ru/svg/%20y%20%3D%20%5B1%2C%201%2C%20-1%2C%20-1%5D%20
[7]: https://tex.s2cms.ru/svg/(0.15x_1%20-%200.43x_2%20%2B%203.21)%20%3D%200%20
[8]: https://habrastorage.org/files/6f5/a40/b54/6f5a40b543d245898e13e6d5da843da2.png
[9]: https://habrahabr.ru/post/312774/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut