Открыть список
Как стать автором
Обновить

Комментарии 9

Объясните мне, пожалуйста, в каких случаях может потребоваться разбираться в этом ворохе формул и использовать «упрощенную» версию SVM? Какая практическая польза этого поста?

В случае детального изучения машины опорных векторов, конечно же: лучший способ что-то понять — сделать своими руками. А так как промышленная версия SVM весьма сложна, то вполне разумно делать некоторую упрощённую версию, где сохранены только самые важные идеи. Здесь предлагается версия буквально на 30 строк Python — вполне подъёмно даже за полпары сделать.


К образованию есть разные подходы: от "вызываем эту функцию и чёрная магия делает всё за нас" до "детально разбираемся что и как работает". Я сторонник второго подхода и эта статья написана для студентов, которые тоже придерживаются мнения, что хорошему программисту нужна хорошая база и понимание что и как работает, а не просто лепить одну библиотеку к другой, авось взлетит. Конечно, каждый сам решает, насколько ему нужно фундаментальное образование — можно и ML заниматься "скачал чужую модель — запустил — не подошла — выбросил". Но мне как-то грустно, когда люди по 2 часа не могут развернуть связный список или конвертируют набор битов в число преобразуя его сначала в строку, а то и вообще матрицу на вектор с ошибками множат (всё реальные случаи).


По поводу "вороха формул". Я так понимаю, имеется в виду раздел "алгоритм SMO". Во-первых, это оригинальный вывод — такого больше нет нигде, ну разве что в моей же заметке на ResearchGate. Так что его в любом случае нужно было привести. Во-вторых, можете посмотреть как это всё выводят другие http://fourier.eng.hmc.edu/e176/lectures/ch9/node9.html и ворох покажется не таким уже и ворохом. Ну и в-третьих, формулы действительно важны. Сравните 30 строк имплементации по формулам в статье и как это имплементируют по стандартным формулам https://github.com/LasseRegin/SVM-w-SMO/blob/master/SVM.py (первый репозитарий, что нагуглился)

SMO очень элегантный алгоритм с быстрой сходимостью, если пользоваться эвристиками. Раз вы от них уже отказались, то можно вообще написать SVM буквально итерируя две строчки до сходимости (но нужен numpy). www.cs.unm.edu/~ismav/papers/sdm-musik.pdf (5.18)

Спасибо за ссылку. Не знал об этой работе, обязательно просмотрю детально.


По поводу SMO, я не согласен, что его ценность сводится исключительно к эвристикам. Он сравнительно хорошо будет работать и без эвристик, ну просто медленнее сходиться — для учебной имплементации это не проблема. Тем более, для учебных целей как раз очень хорошо, когда можно написать базовую версию и она уже что-то классифицирует. Потом куда проще при необходимости добавить сверху и эвристики, и ККТ, и всё что угодно. А вот когда есть только чистый лист и надо в один присест написать какую-то сложнющую штуку с десятком компонентов, то это беда.


Да и не такая уже и плохая та сходимость, если честно. Вот в приведённой вами статье один из тестов — цифра "2" против всех остальных классов. Признаться, я поленился доставать USPS и в точности повторять всю предобработку, вместо этого просто посмотрел "2" против всех остальных на MNIST, немного модифицировав свой тестовый код из статьи. Ясно, что с алгоритмом из статьи я так сравнивать не имею права, но вот с sklearn можно. При тестовой выборке 899 элементов, sklearn делает от 0 до 2-х ошибок от запуска к запуску (чаще 0). Если считать за итерацию один проход по дуальным переменным (цикл до max_iter у меня в коде), то приведённый в статье алгоритм делает 5 ошибок при 1 итерации, при 3-х итерациях от 0 до 3-х ошибок (чаще 2-3), а при 5 итерациях уже где-то как sklearn. Демо в начале статьи ограничено 60-ю итерациями, что также не сильно много. Я бы не сказал, что это настолько плохая сходимость, что аж срочно надо добавлять эвристики.

Я же как раз с вами и соглашаюсь, что SMO это элегантный алгоритм. У Джона Платта вся идея изложена всего на 2х страницах (6 и 7 [9]). Кстати, для полноты картины, можно было бы дать гиперссылку на статью в ссылке [9] выше www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-98-14.pdf Там и псевдокод есть в статье.
Из интересных особенностей алгоритма — отсутсвие нужды хранить матрицу Грама в памяти, рассчитывая парные ядра по ходу вычисления. Так как SVM это разряженная задача, после первого же прохода большая часть множителей Лагранжа обратится в ноль и пере-рассчитывать ядра почти и не придётся.

Недопонимание скорее всего возникло, что я не дал пояснения выше, а просто увидел, что вы в коде считаете всю матрицу Грама сразу и подумал, что тогда уж проще сделать код в две строчки с мультипликативными апдейтами (на что и сослался). Кстати тоже простой в имплементации алгоритм не требующий солвера для задачи квадратичного программирования и как таковой имеет дидактическую ценность. А ещё алгоритм Осуны, на который Платт ссылается, тоже довольно поучителен для обучения. Вот рассказываете студентам принцип опорных векторов в пространстве данных, где у вас всего $d$ параметров (по размерности вектора данных), и вдруг переходим в двойственное пространство и мало того, что параметров становится миллионы, если данных много, так еще же это все миллионы в квадрате (задача-то квадратичная). Красиво, конечно, — трюк с ядром теперь можно применять, но студент должен заинтересоваться а стоило ли того. И будет прав — во многих практических случаях не стоило и проще применять линейную SVM. Но если показать студенту алгоритм Осуны и потом его логическое завершение SMO. Потом уже студенты могут сами переходить к fastfood, но это уже совсем другая история ;)

Спасибо за хорошие замечания! Я поменял ссылку [9] — теперь все ссылки живые. Также очень хорошее замечание о размере матрицы. Я решил добавить про это один абзац в статью (конец раздела об имплементации)


Стоит обратить внимание, что главный потребитель данных из матрицы K — скалярные произведения с \lambda (кроме них на каждой итерации используется ещё только 4 значения для формирования матрицы Q). Это означает, что эффективно мы используем только те элементы K, что соответствуют ненулевым \lambda_i — остальные будут буквально умножены на ноль. Это важное замечание для больших размеров выборки: если количество переменных прямой задачи соответствовало размерности пространства (числу фич), то для дуальной задачи оно уже равно числу точек (размеру датасета) и квадратичная сложность по памяти может оказаться проблемой. К счастью, лишь небольшое число векторов станут опорными, а значит из всей огромной матрицы K нам понадобятся для расчётов всего несколько элементов, которые можно или пересчитывать каждый раз, или же использовать ленивые вычисления.
Невозможно объяснить, что такое Матрица машина опорных векторов… Ты должен увидеть это сам.
Error during service worker registration: s@https://codesandbox.io/static/js/sandbox.743f3294a.js:1:25435

Невозможно объяснить, почему на скриптах никогда ничего нигде не работает.

К сожалению, я недостаточно в этом разбираюсь, чтоб исправить (если это проблема скрипта). Всё что я мог — протестировать перед публикацией в доступных мне браузерах: Chrome, Firefox (Windows 10, Ubuntu 14), Edge (Windows 10) и дефолтном браузере на телефоне Honor. Нигде проблем не обнаружил, рассчитывал, что их и не будет.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.