Вопрос по SVM

[GinGreen]

Здравствуйте.

В настоящий момент я занимаюсь реализацией классификатора SVM.

В качестве основного источника был взят Саймон Хайкин "Нейронные сети".

И всё бы хорошо, задача классификации сводится к задаче оптимизации со смешанными ограничениями, которая решается методом множителей Лагранжа. Да вот только сложность такого алгоритма становится катастрофически большой.

Например, для обучающей выборки из N векторов нужно решить 2 ^(2N) систем линейных уравнений с N + 1 неизвестными.

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

[Igor Borovikov]

На википедии есть набор ссылок, в т.ч. на алгоритм оптимизации для SVN, работающий за линейное по количеству обучающих векторов время (см. раздел Fast Training Algorithms на странице http://en.wikipedia.org/wiki/Support_vector_machine). Поиск по имени автора метода (Thorsten Joachims) дает ссылку на его страницу со статьями, исходниками и скомпилированной программой: http://svmlight.joachims.org/

[GinGreen]

Народ, подскажите всегда ли два множества разделимы SVM машиной с Гауссовым ядром ?

[neurofish]

если речь об обучающей выборке, то всегда. Но это не поможет, машина будет переобучена в общем случае

[K-3]

Цитата:

если речь об обучающей выборке, то всегда. Но это не поможет, машина будет переобучена в общем случае

А можно ссылку, где это поподробнее?

[neurofish]

Цитата:

А можно ссылку, где это поподробнее?

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

пара копеек на этот счет есть в книге Потапова С.А. "Распознавание образов и машинное восприятие"

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

[K-3]

Спасибо!

Про второе понятно. (Первое ведь также означает, что размерность Вапника-Червоненкиса - бесконечность, поэтому все плохо).

Но не понятно 1-е: почему можно разделить всегда любое конечное множество. Наверное, я не знаю, что такое гауссово ядро. Это то же самое, что и радиальное ядро?

[GinGreen]

K-3 писал(а):

Наверное, я не знаю, что такое гауссово ядро. Это то же самое, что и радиальное ядро?

Да, они очень похожи, только Гауссово ядро иеет вид:

GK = exp( -a * || X - Y||^2 )
а - некоторай параметр.