Комментарии 9
В случае детального изучения машины опорных векторов, конечно же: лучший способ что-то понять — сделать своими руками. А так как промышленная версия 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, я не согласен, что его ценность сводится исключительно к эвристикам. Он сравнительно хорошо будет работать и без эвристик, ну просто медленнее сходиться — для учебной имплементации это не проблема. Тем более, для учебных целей как раз очень хорошо, когда можно написать базовую версию и она уже что-то классифицирует. Потом куда проще при необходимости добавить сверху и эвристики, и ККТ, и всё что угодно. А вот когда есть только чистый лист и надо в один присест написать какую-то сложнющую штуку с десятком компонентов, то это беда.
Да и не такая уже и плохая та сходимость, если честно. Вот в приведённой вами статье один из тестов — цифра "2" против всех остальных классов. Признаться, я поленился доставать USPS и в точности повторять всю предобработку, вместо этого просто посмотрел "2" против всех остальных на MNIST, немного модифицировав свой тестовый код из статьи. Ясно, что с алгоритмом из статьи я так сравнивать не имею права, но вот с sklearn можно. При тестовой выборке 899 элементов, sklearn делает от 0 до 2-х ошибок от запуска к запуску (чаще 0). Если считать за итерацию один проход по дуальным переменным (цикл до max_iter у меня в коде), то приведённый в статье алгоритм делает 5 ошибок при 1 итерации, при 3-х итерациях от 0 до 3-х ошибок (чаще 2-3), а при 5 итерациях уже где-то как sklearn. Демо в начале статьи ограничено 60-ю итерациями, что также не сильно много. Я бы не сказал, что это настолько плохая сходимость, что аж срочно надо добавлять эвристики.
Из интересных особенностей алгоритма — отсутсвие нужды хранить матрицу Грама в памяти, рассчитывая парные ядра по ходу вычисления. Так как 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. Нигде проблем не обнаружил, рассчитывал, что их и не будет.
Машина опорных векторов в 30 строчек