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

Question

Я использую LibSVM для классификации некоторых документов. Документы, кажется, немного сложно классифицировать, как показывают окончательные результаты. Тем не менее, я заметил кое-что во время тренировки моих моделей. и это: если мой тренировочный набор, например, 1000, то около 800 из них выбираются в качестве векторов поддержки. Я искал везде, чтобы найти, хорошо это или плохо. Я имею в виду, есть ли связь между количеством векторов поддержки и производительностью классификаторов? Я прочитал этот пост предыдущий пост . Однако я выполняю выбор параметров, а также уверен, что все атрибуты в векторах объектов упорядочены. Мне просто нужно знать отношение. Благодарю. p.s: я использую линейное ядро.

Answer 1

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

Линейный линейный SVM с жестким запасом

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

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

Линейный линейный SVM с мягким полем

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

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

Нелинейный SVM

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

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

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

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

Хороший ресурс: Учебное пособие по машинам опорных векторов для распознавания образов

Answer 2

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

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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

Answer 5

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