Методы опорных векторов (SVM) для больших/очень больших наборов данных

Мне интересно, какова современная эффективная (приблизительная) реализация машин опорных векторов (SVM) для больших/очень больших наборов данных (5-15M+ строк) с нелинейной границей решения (например, гауссовское ядро) ?

Мне известны два конкретных подхода: с одной стороны, это исследование, в котором используется стохастический градиентный спуск и т. д.: http://cseweb.ucsd.edu/~akmenon/ResearchExam.pdf

С другой стороны, существуют подходы к базовым векторным машинам/шаровым векторным машинам: http://www.c2i.ntu.edu.sg/ivor/cvm.html

на этой странице мы можем найти две статьи, описывающие как базовые, так и шаровые векторные машины.

Другими словами, я считаю, что SVM вполне правдоподобны для рассматриваемой проблемы, но я ограничен размером выборки, если бы я использовал стандартную реализацию SVM (может быть сложностью до n ^ 3). Я ищу «приблизительную» реализацию, которая является достаточно точной, но при этом ниже n ^ 2 по временной сложности. Какие самые быстрые такие реализации? Хорошо ли они работают эмпирически или близки к оригинальному SVM по точности?


c++ bigdata svm large-data
person user2551507    schedule 28.10.2013    source источник
comment
Вопрос немного расплывчатый. Можете ли вы объяснить это подробнее, пожалуйста? Хотите больше информации о каждом подходе? или Вы ищете эталон между ними?   -  person Pedrom    schedule 28.10.2013
comment
Стандартный подход к квадратичному программированию может иметь сложность до n^3. Для больших наборов данных это маловероятно. Я ищу наиболее эффективную реализацию SVM для больших наборов данных, сохраняя при этом разумную точность (все еще достаточно близкую к исходной реализации SVM). Было бы очень полезно провести сравнительное сравнение таких приблизительных реализаций SVM. Обновлю вопрос для лучшего разъяснения.   -  person user2551507    schedule 29.10.2013
comment
Действительно, SVM имеет сложность N ^ 3, дело в том, что вы уже ответили на этот вопрос с предоставленными ссылками. И если вы прочитаете длинную бумажную версию Pegasos SVM (одна из ссылок из первой ссылки), у вас будет эталон современного состояния методов приближения SVM с использованием стохастического градиентного спуска. На самом деле вы можете найти ответ на оба вопроса в разделе результатов (стр. 16) длинной версии документа PegasosSVM (ttic.uchicago.edu/~nati/Publications/PegasosMPB.pdf)   -  person Pedrom    schedule 29.10.2013
comment
Большое спасибо за помощь; Я очень ценю это. Тем не менее, документ, который вы показали, был опубликован в 2007 году (из быстрого поиска, похоже, не упоминаются виртуальные машины core/ball). А обзорная статья, на которую я ссылаюсь, была написана в 2009 году. 4 года — это значительный срок. Даже если сложность не может быть значительно улучшена, точность аппроксимации может быть улучшена. Надеюсь на актуальные ответы.   -  person user2551507    schedule 30.10.2013
comment
Привет, я согласен с тем, что 4 года — это значительный срок, но имейте в виду, что в исследованиях — это среднее время с момента выпуска статьи до момента, когда люди, использующие ее в производстве, начинают показывать результаты или внедряются в основную библиотеку. . Так что я не удивлюсь, если эти документы будут самыми последними, которые вы можете получить.   -  person Pedrom    schedule 30.10.2013

Ответы (1)


arrow_upward
1
arrow_downward

Однажды я попробовал FaLK-SVM, и результаты оказались многообещающими. Подход похож на основные векторные машины / шаровые векторные машины, но использует k-ближайших соседей с деревьями (покрывающими деревьями) для разделения данных. Реализация libSVM доступна по ссылке. соответствующий документ описывает подход ядра и шара, но указывает k-ближайшего соседа (просто за разлуку!) быть лучше.

person user__42    schedule 20.02.2014
comment
Большое спасибо за ваши ответы! Рассмотрю это. - person user2551507; 23.02.2014