¿Es Pegasos un buen algoritmo para SVM no lineal?

Respuesta corta: puedes, pero no deberías. Utilice LIBSVM en su lugar.

Respuesta larga:

La capacitación de una máquina de vectores de soporte implica resolver un problema de optimización convexa. Este problema puede reformularse de muchas formas, dos de las más comunes son las denominadas formulaciones “primarias” y “duales”. En la formulación primaria, usted optimiza directamente sobre los términos pesos y sesgo b de la SVM, mientras que en la dual optimiza un problema aparentemente no relacionado sobre algunos coeficientes alfa dobles, pero que también puede usarse indirectamente para obtener predicciones de la SVM en la predicción tiempo, incluso si no tiene los pesos w.

Pegasos es esencialmente un algoritmo de optimización de Descenso de Subgradiente Estocástico (+ algunos trucos) que resuelve la formulación primaria, optimizando directamente los pesos w. Sin embargo, cuando se usa el truco del kernel, los pesos vivirán en el espacio del kernel, lo que en general significa que no puede tener una representación directa de ellos. Por lo tanto, es mucho más fácil resolver la formulación dual, donde aún puede optimizar sobre los coeficientes alfa dobles.

El artículo de Pegasos (http://ttic.uchicago.edu/~nati/P…) presenta una forma de modificar el algoritmo para resolver un SVM kernelized. Sin embargo, al hacerlo, el método pierde la mayor parte de su rendimiento y, por lo tanto, es mejor atenerse a los algoritmos que se desarrollaron específicamente para SVM kernelized. LIBSVM y su implementación del método de optimización secuencial mínima es probablemente la mejor opción allí

No, realmente no. Pegasos opera en el primario, lo que significa que necesita los vectores de características reales. Puede usarlo para entrenar un SVM no lineal solo si puede representar el núcleo como un producto de punto de vectores de características de dimensión finita. Esto significa que no puede usar Pegasos para entrenar un SVM Kernel RBF por ejemplo (que corresponde a vectores de características de dimensiones infinitas). Para aquellos, desea utilizar un método que funcione en un espacio dual, como SMO.

Parece que puede en la sección 4

http://ttic.uchicago.edu/~nati/P

Sin embargo, también me gusta el papel de Crammer

http://u.cs.biu.ac.il/~jkeshet/p

o en estos días solo viendo si se violó el margen (con pérdida de bisagra) y simplemente agregando el vector de soporte y algo simple como adagrad.

Por supuesto que es.

Excepto que el algoritmo también es para el caso de aprendizaje en línea, pero la evaluación en línea de los núcleos no es fácil.

EDITAR: Trataré de elaborar: un núcleo es una medida interna del producto en un espacio vectorial de alta dimensión. Este espacio puede tener dimensiones infinitas, pero los puntos de datos no lo son, si solo tiene N puntos de datos, entonces se pueden convertir de manera segura en un subespacio de N dimensiones sin perder información (cuando apunta a 2 puntos y un origen en el aire , siempre se pueden lanzar en un plano 2D). Entonces, todo lo que necesita es utilizar alguna técnica de incrustación de subespacio (factorización de matriz, por ejemplo) para convertir la matriz del núcleo en muchos vectores de baja D. Para lo cual todos los optimizadores SGD son nativos.

Tenga en cuenta que esta es solo una de las muchas formas de usar pegasos con kernel. Debería haber algunas publicaciones que permitan utilizar la actualización directamente en la matriz del núcleo. Y (no estoy seguro sobre esto) algunos de ellos pueden ser del mismo autor.

Sí, el kernel se usa con frecuencia en SVM. El propósito principal de usarlo en SVM es hacerlo lineal, luego puede encontrar un hiperplano entre las dos clases.

More Interesting

¿Cuál es el enfoque de este problema algorítmico a continuación?

¿Por qué me cuesta entender la recursividad?

¿Es posible escribir un método que muestre todos los elementos en una lista enlazada circular?

¿Se puede ordenar una lista de números en un número menor de pases que el indicado por la notación Big-O?

¿Cómo puedo cambiar el tamaño de una imagen a un ancho y alto específicos sin dejar de mantener su relación de aspecto? Estoy buscando ideas de algoritmos.

¿Cuáles son los ejemplos del mundo real que puedo usar para ilustrar la recursividad de mi clase de introducción CS?

¿Cómo se realiza la coincidencia de cadenas en SQL?

¿Cuál es la mejor manera de extrapolar una señal dispersa que proviene de un filtro de Kalman?

¿Cómo se distribuye el pagerank?

¿El algoritmo de Dios realmente funciona en el Cubo de Rubik 3x3x3?

¿Cuáles son ejemplos de la secuencia de Fibonacci en el campo de la ciencia y las artes liberales (economía, sociología, incluso historia, etc.)?

Estoy tomando un curso en línea, Algorithms Part 1 de Sedgewick y Wayne en Coursera. Conozco bastante a Java, pero me llevó más de un día llegar a la mitad de la resolución de la primera tarea de programación. ¿Debería dejarlo? ¿Todos sienten lo mismo mientras aprenden sobre algoritmos?

¿Cuál es la solución eficiente para SPOJ CCROSSX?

¿De qué manera es el capitalismo como un algoritmo?

Cómo calcular óptimamente grandes factoriales de orden 10 ^ 5 para operaciones repetidas (por ejemplo, encontrar permutaciones)