Métodos del núcleo para el conjunto de datos a gran escala

Question

El clasificador basado en kernel generalmente requiere O (n^3) tiempo de entrenamiento debido al cálculo del producto interno entre dos instancias. Para acelerar el entrenamiento, los valores del producto interno se pueden precalcular y almacenar en una matriz bidimensional. Sin embargo cuando el no. de instancias es muy grande, digamos más de 100,000, no habrá suficiente memoria para hacerlo.

¿Alguna idea mejor para esto?

Answer 1

Relevance Vector Machine tiene un modo de entrenamiento secuencial en el que no necesita mantener toda la matriz del kernel en la memoria. Básicamente se puede calcular una columna a la vez, determinar si parece relevante, y arrojarla de otro modo. No he tenido mucha suerte con eso, sin embargo, y el RVM tiene algunos otros problemas. Probablemente haya una mejor solución en el ámbito de los Procesos Gaussianos. Realmente no me he sentado mucho con ellos, pero he visto mención de un algoritmo en línea para eso.

Answer 2

No soy un analista numérico, pero no es el QR decomposition que necesita para hacer la regresión lineal ordinaria de mínimos cuadrados también O (n^3)?

De todos modos, es probable que desee buscar en la literatura (ya que esto es bastante nuevo) para aprendizaje en línea o versiones de aprendizaje activo del algoritmo que está utilizando. La idea general es descartar datos lejos de su límite de decisión o no incluirlos en primer lugar. El peligro es que puede quedar atrapado en un mal local máximo y luego su algoritmo en línea/activo ignorará los datos que lo ayudarán a salir.

Answer 3

Para implementaciones modernas de máquinas de vectores de soporte, la escala del algoritmo de entrenamiento depende de muchos factores, como la naturaleza de los datos de entrenamiento y el kernel que está utilizando. El factor de escala de O (n^3) es un resultado analítico y no es particularmente útil para predecir cómo se escalará el entrenamiento SVM en situaciones del mundo real. Por ejemplo, las estimaciones empíricas del algoritmo de entrenamiento utilizado por SVMLight ponen la escala contra el tamaño del conjunto de entrenamiento en approximately O(n^2).

Le sugiero que haga esta pregunta en el kernel machines forum. Creo que es más probable que obtengas una mejor respuesta que en Stack Overflow, que es más un sitio de programación de propósito general.