Методы ядра для крупномасштабного набора данных

Question

Классификатор на основе ядра обычно требует времени обучения O (n ^ 3) из-за вычисления внутреннего продукта между двумя экземплярами. Чтобы ускорить обучение, значения внутреннего продукта могут быть предварительно вычислены и сохранены в двумерном массиве. Однако, когда нет. количество экземпляров очень велико, скажем, более 100 000, памяти не хватит для этого.

Значит, есть идея получше?

Answer 1

В современных реализациях машин опорных векторов масштабирование алгоритма обучения зависит от множества факторов, таких как характер данных обучения и ядро, которое вы используете. Коэффициент масштабирования O (n ^ 3) является аналитическим результатом и не особенно полезен для прогнозирования масштабирования обучения SVM в реальных ситуациях. Например, эмпирические оценки алгоритма обучения, используемого SVMLight, устанавливают масштабирование в зависимости от размера обучающего набора равным приблизительно O (n ^ 2) .

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

Answer 2

Я не числовой аналитик, но разве не QR-разложение , которое необходимо для обычной линейной регрессии наименьших квадратов, также O (n ^ 3)?

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

Answer 3

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