Какова связь между количеством опорных векторов и данными обучения и производительностью классификаторов?

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

Линейный SVM с жесткой маржой

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

Все опорные векторы лежат точно на краю. Независимо от количества измерений или размера набора данных, количество опорных векторов может быть всего 2.

Линейный SVM с мягкой маржой

Но что, если наш набор данных не является линейно разделимым? Мы вводим SVM с мягкой маржой. Мы больше не требуем, чтобы наши точки данных находились за пределами поля, мы позволяем некоторому их количеству отклоняться от линии на поле. Мы используем резервный параметр C, чтобы контролировать это. (nu в nu-SVM) Это дает нам более широкий запас и большую ошибку в обучающем наборе данных, но улучшает обобщение и/или позволяет нам найти линейное разделение данных, которое не является линейно разделимым.

Теперь количество опорных векторов зависит от допустимого резерва и распределения данных. Если мы допустим большой резерв, у нас будет большое количество векторов поддержки. Если мы допустим очень небольшой провис, у нас будет очень мало векторов поддержки. Точность зависит от нахождения правильного уровня резерва для анализируемых данных. Некоторые данные невозможно получить с высокой степенью точности, мы должны просто найти наилучшее соответствие, какое только можем.

Нелинейный SVM

Это подводит нас к нелинейному SVM. Мы все еще пытаемся линейно разделить данные, но теперь мы пытаемся сделать это в пространстве более высокого измерения. Это делается с помощью функции ядра, которая, конечно же, имеет собственный набор параметров. Когда мы переводим это обратно в исходное пространство признаков, результат оказывается нелинейным:

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

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

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

Хороший ресурс: A Tutorial on Support Векторные машины для распознавания образов

800 из 1000 в основном говорят вам, что SVM должен использовать почти каждый обучающий образец для кодирования обучающего набора. Это в основном говорит вам, что в ваших данных нет большой регулярности.

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

Как количество выборок, так и количество атрибутов могут влиять на количество опорных векторов, делая модель более сложной. Я полагаю, что вы используете слова или даже энграммы в качестве атрибутов, так что их довольно много, а модели естественного языка сами по себе очень сложны. Итак, 800 опорных векторов из 1000 выборок кажутся нормальными. (Также обратите внимание на комментарии @karenu о параметрах C/nu, которые также сильно влияют на количество SV).

Чтобы понять это, вспомните основную идею SVM. SVM работает в многомерном пространстве признаков и пытается найти гиперплоскость, которая разделяет все заданные выборки. Если у вас много образцов и только 2 функции (2 измерения), данные и гиперплоскость могут выглядеть так:

Здесь всего 3 опорных вектора, все остальные находятся за ними и не играют никакой роли. Обратите внимание, что эти опорные векторы определяются только двумя координатами.

Теперь представьте, что у вас есть трехмерное пространство и, таким образом, опорные векторы определяются тремя координатами.

Это означает, что нужно настроить еще один параметр (координату), и для этой настройки может потребоваться больше выборок, чтобы найти оптимальную гиперплоскость. Другими словами, в худшем случае SVM находит только 1 координату гиперплоскости на выборку.

Когда данные хорошо структурированы (т. е. достаточно хорошо удерживают шаблоны), может понадобиться только несколько опорных векторов — все остальные останутся позади них. Но текст — это очень и очень плохо структурированные данные. SVM делает все возможное, пытаясь подогнать выборку как можно лучше, и, таким образом, берет в качестве опорных векторов даже больше выборок, чем отбрасывает. С увеличением количества выборок эта «аномалия» уменьшается (появляются более незначительные выборки), но абсолютное число опорных векторов остается очень высоким.

Классификация SVM линейна по количеству опорных векторов (SV). Количество SV в худшем случае равно количеству обучающих выборок, поэтому 800/1000 — это еще не худший случай, но все равно довольно плохо.

Опять же, 1000 обучающих документов — это небольшой обучающий набор. Вы должны проверить, что происходит, когда вы масштабируете до 10000 или более документов. Если ситуация не улучшится, рассмотрите возможность использования линейных SVM, обученных с помощью LibLinear, для классификации документов; они масштабируются намного лучше (размер модели и время классификации линейны по количеству признаков и не зависят от количества обучающих выборок).

Существует некоторая путаница между источниками. В учебнике ISLR 6th Ed, например, C описывается как «бюджет нарушения границ», из чего следует, что более высокий C допускает большее количество нарушений границ и больше векторов поддержки. Но в реализациях svm в R и python параметр C реализуется как «наказание за нарушение», что является противоположностью, и тогда вы заметите, что для более высоких значений C меньше опорных векторов.