Recientemente, ha habido un impulso hacia el aprendizaje automático demostrable dentro de CS teórico. Dos resultados que sobresalen como resultados seminales en el campo son:
- Probar que encontrar los parámetros exactos para una mezcla de modelo gaussiano (por ejemplo, ¡no el algoritmo EM!) Es polytime
- Probar que la factorización matricial no negativa admite un algoritmo de tiempo polinómico
Otro algoritmo que la gente pensaba que era “imposible” (aunque no está claro si hay fuentes que afirman que el problema no era polytime) es el cifrado totalmente homomórfico. (vea la respuesta del usuario de Quora a ¿Ha habido nuevos algoritmos brillantes de informática en los últimos 10 años?)
Mezcla de gaussianos
Una mezcla de gaussianos es una distribución [math] \ rho = \ sum_i w_i \ mathcal {N} (\ mu_i, \ Sigma_i) [/ math], donde
- [math] \ mathcal {N} (\ mu_i, \ Sigma_i) [/ math] es una normal multivariada con media [math] \ mu_i [/ math] y covarianza [math] \ Sigma_i [/ math]
- [math] w_i [/ math] es un peso de mezcla (proporción de muestras de este gaussiano)
El objetivo es recuperar los pesos de la mezcla [matemática] w_i [/ matemática] con polinomios muchas muestras de [matemática] \ rho [/ matemática]. Si bien se puede obtener una estimación muy rápida y sucia de los pesos ejecutando el algoritmo EM, estas soluciones son solo mínimos locales y no globales de su función de pérdida (por ejemplo, [matemática] \ ell ^ 2 [/ matemática] función de pérdida, o al menos cuadrícula)
En 2010, Moitra y Valiant [0] demostraron que este problema es definitivamente un tiempo polinómico. Lo hacen al mostrar que primero puede reducir el problema a inferir los parámetros de un conjunto de valores normales univariados (tiempo claramente polinómico) y luego usar un método de agrupamiento jerárquico para combinar los parámetros de estos valores normales univariados. Hay muchos casos degenerados / de esquina que hacen que sea muy difícil mostrar que este método funciona. En lugar de manejar cada caso individualmente, Moitra y Valiant construyeron un inteligente algoritmo de corrección de errores que se ejecuta en la parte superior del árbol de clúster de enlace único. Al mostrar que la sobrecarga de la corrección de errores es polinómica, pudieron deducir la complejidad de polimetro del algoritmo de inferencia completo.
Factorización de matriz no negativa
La factorización matricial no negativa es el proceso de descomposición de una matriz [matemática] A [/ matemática] en el producto de dos matrices [matemática] B, C [/ matemática] de modo que ambos [matemática] B, C [/ matemática] solamente tener entradas no negativas. En particular, uno puede ver [matemáticas] C [/ matemáticas] como una matriz de ‘distribuciones de probabilidad’ (temas) y [matemáticas] B [/ matemáticas] como una matriz de parámetros de mezcla para estos temas (la analogía con LDA es correcta : NMF es lo mismo que Asignación de Dirichlet Latente, ver [1]). Esto efectivamente se reduce a calcular una factorización matricial con una restricción. Dado que se sabe que muchas otras factorizaciones restringidas son NP completas (por ejemplo, la factorización de tensor, que está relacionada con NMF), la mayoría de los investigadores pensaron que la NMF exacta era un problema NP-completo. Tenga en cuenta que los usuarios más prácticos de NMF usan aproximaciones.
En 2012, Arora, Ge, Kannan y Moitra [AGKM] demostraron que la factorización matricial no negativa admite un algoritmo de tiempo polinómico [2]. Las técnicas que usan son bastante complicadas (realizan cierto tipo de optimización sobre conjuntos semi-algebraicos que codifican las restricciones no negativas), pero el resultado fue bastante sorprendente para muchos en el campo.
[0] [1004.4223v1] Establecimiento de la capacidad de aprendizaje polinomial de mezclas de gaussianos
[1] [1204.6703] Algoritmo espectral para la asignación de Dirichlet latente
[2] [1111.0952] Cálculo de una factorización matricial no negativa – Probablemente
