SVM, Kernels

https://www.coursera.org/course/ml

После линейной регрессии была логистическая регрессия. А потом начались нейросети — Neural Networks. Потом нас учили правильно применять изученные алгоритмы (Advice for Applying Machine Learning). А потом нам рассказали про Support Vector Machines (SVMs) и Kernels. Это по типу логистической регрессии, только лучше, по крайней мере, в некоторых случаях.

SVM еще называют Large Margin Classificators, потому как результатом применения SVM становится такое решение классификатора, которое проводит разделительную черту между классами так, чтобы расстояние до черты было наибольшим. То есть SVM строит наиболее качественный классификатор (если применять метод правильно).

Основная идея SVM классификатора в том, что Cost Function несколько мофицируется, с тем, чтобы обеспечить обнуление цены при пороговых значениях полинома гипотезы.

Математика, стоящая за оптимизацией такой интересной Cost Function построена на работе с векторами их проекциями и длинами. Возможно поэтому метод и называется Support Vector Machine. При этом есть достаточное количество хороших библиотек для использования SVM «из коробки».

До сих пор вроде все хорошо, можно сделать вывод, что SVM лучше логистической регресси, ибо дает более четкое разделение на классы.

Но тут в тему ворвались Kernels. Как нам обьяснили, SVM + Kernels это прекрасно, ибо, в отличие от логистической регрессии или нейросетей, машина перемалывает вычисления этого комбо сравнительно быстро. И есть огромный плюс — легкость получения нелинейных классификаторов.

Что же такое Kernels? Это способ определения фич (переменных модели, коэффициентов полинома) для полинома в тех случаях, когда нужна нелинейная модель. Традиционно в этих случаях применяют создание новых фич из имеющихся путем возведения в степень — квдрат, куб и т. д. Но можно применить Kernels.

Если на пальцах, то Kernel Function это функция похожести (similarity) одной записи датасета на другую. Только в алгоритме вычисляют похожесть между записями датасета и «landmarks». Лендмарки — это набор точек в пространстве датасета. Если проще — образцовые записи из датасета.

И если в полиноме гипотезы заменить исходные фичи на значения этих Kernel Functions, то получим метод Kernels для вычисления значений гипотезы, и как результат оптимизации Cost Function для этой гипотезы — нелинейный классификатор.

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

Тем не менее, считается, что для некоторых случаев SVM + Kernels это здорово и круто.

Обычно применяют Gaussian Kernels — функция похожести дает холм Гауссова распределения.

Есть еще часто применяемый linear kernel aka no kernel, который дает обычный линейный классификатор.

В общем, если количество фич относительно мало, до 1000, а количество записей данных достаточно, первые десятки тысяч — можно использовать SVM + Gaussian Kernel. И это позволить выработать достойный нелинейный классификатор.

В остальных случаях (много фич и небольшой датасет, мало фич но датасет огромен) — используй SVM с линейным ядром или логистическая регрессия.

В практическом занятии мы строили распознавалку спама, используя SVM + Gaussian Kernel.

original post http://vasnake.blogspot.com/2014/06/svm-kernels.html