2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Вопрос по SVM
Сообщение06.09.2007, 14:47 


02/12/06
5
Здравствуйте.

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

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

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

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

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

 Профиль  
                  
 
 
Сообщение15.09.2007, 04:39 


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

 Профиль  
                  
 
 
Сообщение08.10.2007, 09:14 


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

 Профиль  
                  
 
 
Сообщение09.10.2007, 16:19 


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

 Профиль  
                  
 
 
Сообщение12.10.2007, 19:34 


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


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

 Профиль  
                  
 
 
Сообщение12.10.2007, 23:16 


08/10/07
9
Цитата:
А можно ссылку, где это поподробнее?

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

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

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

 Профиль  
                  
 
 
Сообщение13.10.2007, 15:02 


10/11/06
64
Спасибо!

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

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

 Профиль  
                  
 
 
Сообщение24.10.2007, 15:59 


02/12/06
5
K-3 писал(а):
Наверное, я не знаю, что такое гауссово ядро. Это то же самое, что и радиальное ядро?


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group