Completar la matriz es la tarea de completar las entradas faltantes de una matriz parcialmente observada. Una amplia gama de conjuntos de datos se organizan naturalmente en forma de matriz. Un ejemplo es la matriz de clasificación de películas, como aparece en el problema de Netflix : dada una matriz de clasificación en la que cada entrada representa la calificación de la película por el cliente , si el cliente ha visto una película y por lo demás falta, nos gustaría predecir las entradas restantes para poder hacer buenas recomendaciones a los clientes sobre qué ver a continuación. Otro ejemplo es la matriz término-documento : las frecuencias de palabras utilizadas en una colección de documentos se pueden representar como una matriz, donde cada entrada corresponde al número de veces que el término asociado aparece en el documento indicado.
Sin ninguna restricción sobre el número de grados de libertad en la matriz completa, este problema está subdeterminado, ya que a las entradas ocultas se les podrían asignar valores arbitrarios. Por lo tanto, necesitamos alguna suposición en la matriz para crear un problema bien planteado , como suponer que tiene un determinante máximo, es positivo definido o tiene un rango bajo. [1] [2]
Por ejemplo, se puede suponer que la matriz tiene una estructura de rango bajo y luego buscar la matriz de rango más bajo o, si se conoce el rango de la matriz completa, una matriz de rango que coincide con las entradas conocidas. La ilustración muestra que una matriz de rango 1 parcialmente revelada (a la izquierda) se puede completar con error cero (a la derecha) ya que todas las filas con entradas faltantes deben ser iguales a la tercera fila. En el caso del problema de Netflix, se espera que la matriz de calificaciones sea de rango bajo, ya que las preferencias del usuario a menudo se pueden describir mediante algunos factores, como el género de la película y el momento de lanzamiento. Otras aplicaciones incluyen la visión por computadora, donde los píxeles faltantes en las imágenes deben reconstruirse, la detección del posicionamiento global de los sensores en una red a partir de información de distancia parcial y el aprendizaje multiclase . El problema de compleción de la matriz es en general NP-hard , pero bajo supuestos adicionales existen algoritmos eficientes que logran una reconstrucción exacta con alta probabilidad.
Desde el punto de vista del aprendizaje estadístico, el problema de compleción de matrices es una aplicación de la regularización de matrices, que es una generalización de la regularización de vectores . Por ejemplo, en el problema de compleción de matrices de bajo rango, se puede aplicar la penalización de regularización tomando la forma de una norma nuclear.
Finalización de matriz de rango bajo
Una de las variantes del problema de compleción de la matriz es encontrar la matriz de rango más bajo que coincide con la matriz , que deseamos recuperar, para todas las entradas del conjunto de entradas observadas. La formulación matemática de este problema es la siguiente:
Candès y Recht [3] demostraron que con supuestos sobre el muestreo de las entradas observadas y suficientes entradas muestreadas, este problema tiene una solución única con alta probabilidad.
Una formulación equivalente, dado que la matriz a recuperar se sabe que es de rango , es resolver por dónde
Supuestos
Con frecuencia se hacen varios supuestos sobre el muestreo de las entradas observadas y el número de entradas muestreadas para simplificar el análisis y garantizar que el problema no esté subdeterminado .
Muestreo uniforme de entradas observadas
Para que el análisis sea manejable, a menudo se supone que el conjunto de las entradas observadas y la cardinalidad fija se muestrea uniformemente al azar de la colección de todos los subconjuntos de entradas de cardinalidad. Para simplificar aún más el análisis, se supone en cambio quese construye mediante muestreo de Bernoulli , es decir, que cada entrada se observa con probabilidad. Si se establece en dónde es la cardinalidad esperada deseada de, y son las dimensiones de la matriz (sea sin pérdida de generalidad), está dentro de con alta probabilidad, por lo que el muestreo de Bernoulli es una buena aproximación para un muestreo uniforme. [3] Otra simplificación es suponer que las entradas se muestrean de forma independiente y con reemplazo. [4]
Límite inferior del número de entradas observadas
Supongamos que por matriz (con ) que estamos tratando de recuperar tiene rango . Existe un límite inferior teórico de la información sobre cuántas entradas deben observarse antesse puede reconstruir de forma única. El conjunto de por matrices con rango menor o igual a es una variedad algebraica en con dimensión . Usando este resultado, se puede demostrar que al menos las entradas deben ser observadas para completar la matriz en tener una solución única cuando . [5]
En segundo lugar, debe haber al menos una entrada observada por fila y columna de . La descomposición de valores singulares de es dado por . Si fila no se observa, es fácil ver el vector singular derecho de , , se puede cambiar a algún valor arbitrario y aún así producir una coincidencia de matriz sobre el conjunto de entradas observadas. Del mismo modo, si la columna no es observado, el vector singular izquierdo de , puede ser arbitrario. Si asumimos el muestreo de Bernoulli del conjunto de entradas observadas, el efecto de colector de cupones implica que las entradas en el orden dedebe ser observado para asegurar que hay una observación de cada fila y columna con alta probabilidad. [6]
Combinando las condiciones necesarias y asumiendo que (una suposición válida para muchas aplicaciones prácticas), el límite inferior en el número de entradas observadas requeridas para evitar que el problema de la compleción de la matriz sea subdeterminado es del orden de .
Incoherencia
El concepto de incoherencia surgió en la detección comprimida . Se introduce en el contexto de la compleción de matrices para asegurar los vectores singulares deno son demasiado "escasas" en el sentido de que todas las coordenadas de cada vector singular son de magnitud comparable en lugar de que unas pocas coordenadas tengan magnitudes significativamente mayores. [7] [8] Los vectores de base estándar son entonces indeseables como vectores singulares, y el vector en es deseable. Como ejemplo de lo que podría salir mal si los vectores singulares son lo suficientemente "dispersos", considere el por matriz con descomposición de valor singular . Casi todas las entradas de debe tomarse una muestra antes de que pueda reconstruirse.
Candès y Recht [3] definen la coherencia de una matrizcon espacio de columna unsubespacio dimensional de como , dónde es la proyección ortogonal sobre. La incoherencia afirma entonces que dada la descomposición del valor singular de El por matriz ,
- Las entradas de tienen magnitudes superiores limitadas por
para algunos .
Terminación de matriz de rango bajo con ruido
En la aplicación del mundo real, a menudo se observan solo unas pocas entradas corrompidas al menos por una pequeña cantidad de ruido. Por ejemplo, en el problema de Netflix, las calificaciones son inciertas. Candès y Plan [9] demostraron que es posible completar las muchas entradas faltantes de matrices grandes de bajo rango a partir de unas pocas muestras ruidosas mediante la minimización de la norma nuclear. El modelo ruidoso asume que observamos
dónde es un término de ruido. Tenga en cuenta que el ruido puede ser estocástico o determinista. Alternativamente, el modelo se puede expresar como
dónde es un matriz con entradas por asumiendo que para algunos Para recuperar la matriz incompleta, intentamos solucionar el siguiente problema de optimización:
Entre todas las matrices consistentes con los datos, encuentre la que tenga la norma nuclear mínima. Candès y Plan [9] han demostrado que esta reconstrucción es precisa. Han demostrado que cuando se produce una recuperación perfecta sin ruido, la terminación de la matriz es estable frente a las perturbaciones. El error es proporcional al nivel de ruido.. Por lo tanto, cuando el nivel de ruido es pequeño, el error es pequeño. Aquí, el problema de compleción de la matriz no obedece a la propiedad de isometría restringida (RIP). Para matrices, el RIP supondría que el operador de muestreo obedece
para todas las matrices con rango suficientemente pequeño y suficientemente pequeño. Los métodos también son aplicables a problemas de recuperación de señal dispersa en los que el RIP no se mantiene.
Finalización de matriz de alto rango
La finalización de la matriz de alto rango en general es NP-Hard . Sin embargo, con ciertos supuestos, se puede completar alguna matriz de rango alto incompleta o incluso una matriz de rango completo.
Eriksson, Balzano y Nowak [10] han considerado el problema de completar una matriz con el supuesto de que las columnas de la matriz pertenecen a una unión de múltiples subespacios de rango bajo. Dado que las columnas pertenecen a una unión de subespacios, el problema puede verse como una versión de datos perdidos del problema de agrupamiento del subespacio . Dejar frijol matriz cuyas columnas (completas) se encuentran en una unión de como máximo subespacios, cada uno de y asumir . Eriksson, Balzano y Nowak [10] mostraron que bajo supuestos moderados cada columna de se puede recuperar perfectamente con alta probabilidad de una versión incompleta siempre que al menos entradas de se observan uniformemente al azar, con una constante que depende de las condiciones habituales de incoherencia, la disposición geométrica de los subespacios y la distribución de las columnas sobre los subespacios.
El algoritmo implica varios pasos: (1) vecindarios locales; (2) subespacios locales; (3) refinamiento subespacial; (4) finalización de matriz completa. Este método se puede aplicar a la identificación de topología y la compleción de matrices de distancia de Internet.
Algoritmos para completar matrices de bajo rango
Se han propuesto varios algoritmos de compleción de matrices. [8] Estos incluyen algoritmo basado en relajación convexa, [3] algoritmo basado en gradiente, [11] y algoritmo alternativo basado en minimización. [12]
Relajación convexa
El problema de la minimización de rango es NP-difícil . Un enfoque, propuesto por Candès y Recht, es formar una relajación convexa del problema y minimizar la norma nuclear. (que da la suma de los valores singulares de) en vez de (que cuenta el número de valores singulares distintos de cero de). [3] Esto es análogo a minimizar la norma L1 en lugar de la norma L0 para los vectores. La relajación convexa se puede resolver usando programación semidefinida (SDP) al notar que el problema de optimización es equivalente a
La complejidad de usar SDP para resolver la relajación convexa es. Los solucionadores de vanguardia como SDP3 solo pueden manejar matrices de tamaño de hasta 100 por 100 [13] Un método alternativo de primer orden que resuelve aproximadamente la relajación convexa es el algoritmo de umbral de valor singular introducido por Cai, Candès y Shen. [13]
Candès y Recht muestran, utilizando el estudio de variables aleatorias en espacios de Banach , que si el número de entradas observadas es del orden de (asumir sin pérdida de generalidad ), el problema de minimización de rango tiene una solución única que también resulta ser la solución de su relajación convexa con probabilidad por alguna constante . Si el rango de es pequeño (), el tamaño del conjunto de observaciones se reduce al orden de . Estos resultados son casi óptimos, ya que el número mínimo de entradas que deben observarse para que el problema de compleción de la matriz no sea subdeterminado es del orden de.
Este resultado ha sido mejorado por Candès y Tao. [6] Alcanzan límites que difieren de los límites óptimos solo por factores polilogarítmicos al fortalecer los supuestos. En lugar de la propiedad de incoherencia, asumen la propiedad de incoherencia fuerte con el parámetro. Esta propiedad establece que:
- por y por
- Las entradas de están delimitados en magnitud por
Intuitivamente, fuerte incoherencia de una matriz afirma que las proyecciones ortogonales de vectores base estándar para tiene magnitudes que tienen alta probabilidad si los vectores singulares se distribuyeran aleatoriamente. [7]
Candès y Tao descubren que cuando es y el número de entradas observadas es del orden de , el problema de minimización de rango tiene una solución única que también resulta ser la solución de su relajación convexa con probabilidad por alguna constante . Por arbitrario, el número de entradas observadas suficientes para que esta afirmación sea verdadera es del orden de
Descenso de gradiente
Keshavan, Montanari y Oh [11] consideran una variante de compleción de la matriz donde el rango del por matriz , que se va a recuperar, se sabe que . Asumen muestreo de Bernoulli de entradas, relación de aspecto constante, magnitud acotada de entradas de (deja que el límite superior sea ) y número de condición constante (dónde y son los valores singulares más grandes y más pequeños derespectivamente). Además, asumen que las dos condiciones de incoherencia se satisfacen con y dónde y son constantes. Dejar ser una matriz que coincida En el set de entradas observadas y es 0 en otros lugares. Luego proponen el siguiente algoritmo:
- Podar eliminando todas las observaciones de las columnas con un grado mayor que estableciendo las entradas en las columnas en 0. De manera similar, elimine todas las observaciones de las filas con un grado mayor que .
- Proyecto en su primera componentes principales . Llamar a la matriz resultante.
- Resolver dónde es una función de regularización por descenso de gradiente con búsqueda de línea . Inicializar a dónde . Colocar como alguna función obligando permanecer incoherente durante el descenso del gradiente si y son incoherentes.
- Devuelve la matriz.
Los pasos 1 y 2 del algoritmo producen una matriz muy cerca de la verdadera matriz (medido por la raíz del error cuadrático medio (RMSE) con alta probabilidad. En particular, con probabilidad, por alguna constante . denota la norma Frobenius . Tenga en cuenta que no se necesita el conjunto completo de suposiciones para que este resultado se mantenga. La condición de incoherencia, por ejemplo, solo entra en juego en la reconstrucción exacta. Por último, aunque el recorte puede parecer contrario a la intuición, ya que implica desechar información, asegura la proyección en su primera Los componentes principales dan más información sobre la matriz subyacente. que sobre las entradas observadas.
En el Paso 3, el espacio de matrices candidatas puede reducirse notando que el problema de minimización interna tiene la misma solución para como para dónde y son ortonormales por matrices. Luego, el descenso de gradiente se puede realizar sobre el producto cruzado de dos colectores de Grassman . Si y el conjunto de entradas observadas es del orden de , la matriz devuelta por el paso 3 es exactamente . Entonces el algoritmo es de orden óptimo, ya que sabemos que para que el problema de compleción de la matriz no esté subdeterminado, el número de entradas debe estar en el orden de.
Minimización de mínimos cuadrados alternos
La minimización alterna representa un enfoque ampliamente aplicable y empíricamente exitoso para encontrar matrices de bajo rango que se ajusten mejor a los datos dados. Por ejemplo, para el problema de completar la matriz de bajo rango, se cree que este método es uno de los más precisos y eficientes, y formó un componente importante de la entrada ganadora en el problema de Netflix. En el enfoque de minimización alterna, la matriz objetivo de rango bajo se escribe en forma bilineal :
;
el algoritmo luego alterna entre encontrar el mejor y lo mejor . Si bien el problema general no es convexo, cada subproblema suele ser convexo y se puede resolver de manera eficiente. Jain, Netrapalli y Sanghavi [12] han dado una de las primeras garantías para el desempeño de la minimización alterna tanto para la terminación de la matriz como para la detección de la matriz.
El algoritmo de minimización alterna se puede ver como una forma aproximada de resolver el siguiente problema no convexo:
El algoritmo AltMinComplete propuesto por Jain, Netrapalli y Sanghavi se enumera aquí: [12]
- Entrada : conjunto observado, valores
- Dividir dentro subconjuntos con cada elemento de perteneciente a uno de los con igual probabilidad (muestreo con reemplazo)
- es decir, superior vectores singulares izquierdos de
- Recorte : establezca todos los elementos de que tienen una magnitud mayor que a cero y ortonormalizar las columnas de
- por hacer
- final para
- Regreso
Demostraron que al observar entradas aleatorias de una matriz incoherente , El algoritmo AltMinComplete puede recuperar en pasos. En términos de complejidad de la muestra (), teóricamente, la minimización alterna puede requerir un mayor que la relajación convexa. Sin embargo, empíricamente, no parece ser el caso, lo que implica que los límites de complejidad de la muestra pueden ajustarse aún más. En términos de complejidad del tiempo, demostraron que AltMinComplete necesita tiempo
.
Vale la pena señalar que, aunque los métodos basados en la relajación convexa tienen un análisis riguroso, los algoritmos basados en la minimización alterna son más exitosos en la práctica. [ cita requerida ]
Aplicaciones
Candès y Plan [9] resumen varias aplicaciones de la compleción matricial de la siguiente manera:
Filtración colaborativa
El filtrado colaborativo es la tarea de realizar predicciones automáticas sobre los intereses de un usuario mediante la recopilación de información sobre los gustos de muchos usuarios. Empresas como Apple, Amazon, Barnes and Noble y Netflix están tratando de predecir las preferencias de sus usuarios a partir de un conocimiento parcial. En este tipo de problema de compleción de la matriz, la matriz completa desconocida a menudo se considera de rango bajo porque solo unos pocos factores contribuyen típicamente a los gustos o preferencias de un individuo.
Identificación del sistema
En control, a uno le gustaría ajustar un modelo de espacio de estado invariante en el tiempo lineal de tiempo discreto
a una secuencia de entradas y salidas . El vector es el estado del sistema en el momento y es el orden del modelo del sistema. Del par de entrada / salida, uno quisiera recuperar las matrices y el estado inicial . Este problema también puede verse como un problema de compleción de matrices de rango bajo.
Localización de Internet de las cosas (IoT)
El problema de localización (o posicionamiento global) surge de forma natural en las redes de sensores de IoT. El problema es recuperar el mapa del sensor en el espacio euclidiano a partir de un conjunto local o parcial de distancias por pares. Por lo tanto, es un problema de compleción de la matriz con rango dos si los sensores están ubicados en un plano 2-D y tres si están en un espacio 3-D. [14]
Ver también
- Regularización de matrices
- Premio Netflix
- Filtración colaborativa
- Identificación del sistema
- Optimizacion convexa
Referencias
- ^ Johnson, Charles R. (1990). "Problemas de finalización de la matriz: una encuesta". Teoría y aplicaciones de matrices . 40 : 171-198. doi : 10.1090 / psapm / 040/1059486 .
- ^ Laurent, Monique (2008). "Problemas de finalización de la matriz". Enciclopedia de Optimización . 3 : 221-229. doi : 10.1007 / 978-0-387-74759-0_355 .
- ^ a b c d e Candès, EJ; Recht, B. (2009). "Finalización exacta de la matriz mediante optimización convexa" . Fundamentos de la matemática computacional . 9 (6): 717–772. arXiv : 0805.4471 . doi : 10.1007 / s10208-009-9045-5 .
- ^ Recht, B. (2009). "Un enfoque más simple para completar la matriz" (PDF) . Revista de investigación sobre aprendizaje automático . 12 : 3413–3430. arXiv : 0910.0651 . Código Bibliográfico : 2009arXiv0910.0651R .
- ^ Xu, Zhiqiang (2018). "El número de medición mínimo para la recuperación de matrices de rango bajo". Análisis Armónico Computacional y Aplicado . 44 (2): 497–508. arXiv : 1505.07204 . doi : 10.1016 / j.acha.2017.01.005 .
- ^ a b Candès, EJ; Tao, T. (2010). "El poder de la relajación convexa: finalización de la matriz casi óptima". Transacciones IEEE sobre teoría de la información . 56 (5): 2053-2080. arXiv : 0903.1476 . doi : 10.1109 / TIT.2010.2044061 .
- ^ a b Tao, T. (10 de marzo de 2009). "El poder de la relajación convexa: finalización de la matriz casi óptima" . ¿Qué hay de nuevo ?
- ^ a b Nguyen, LT; Kim, J .; Shim, B. (10 de julio de 2019). "Finalización de la matriz de bajo rango: una encuesta contemporánea". Acceso IEEE . 7 (1): 94215–94237. arXiv : 1907.11705 . Código Bib : 2019arXiv190711705N . doi : 10.1109 / ACCESS.2019.2928130 .
- ^ a b c Candès, EJ; Plan, Y. (2010). "Terminación de matriz con ruido". Actas del IEEE . 98 (6): 925–936. arXiv : 0903.3131 . doi : 10.1109 / JPROC.2009.2035722 .
- ^ a b Eriksson, B .; Balzano, L .; Nowak, R. (2011). "Terminación de matriz de alto rango y agrupación de subespacios con datos faltantes". arXiv : 1112.5629 [ cs.IT ].
- ^ a b Keshavan, RH; Montanari,.; Oh, S. (2010). "Completar la matriz a partir de unas pocas entradas". Transacciones IEEE sobre teoría de la información . 56 (6): 2980–2998. arXiv : 0901.3150 . doi : 10.1109 / TIT.2010.2046205 .CS1 maint: nombres numéricos: lista de autores ( enlace )
- ^ a b c Jain, P .; Netrapalli, P .; Sanghavi, S. (2013). "Finalización de la matriz de rango bajo mediante la minimización alterna". Actas del 45º simposio anual de ACM sobre el Simposio sobre teoría de la computación . ACM. págs. 665–674. arXiv : 1212.0467 . doi : 10.1145 / 2488608.2488693 . ISBN 978-1-4503-2029-0.
- ^ a b Cai, J.-F .; Candès, EJ; Shen, Z. (2010). "Un algoritmo de umbral de valor singular para la finalización de la matriz". Revista SIAM de Optimización . 20 (4): 1956–1982. arXiv : 0810.3286 . doi : 10.1137 / 080738970 .
- ^ Nguyen, LT; Kim, J .; Kim, S .; Shim, B. (2019). "Localización de redes de IoT a través de la finalización de la matriz de bajo rango". Transacciones IEEE sobre comunicaciones . 67 (8): 5833–5847. doi : 10.1109 / TCOMM.2019.2915226 .