¿Explicar los pasos del algoritmo LLE (incrustación lineal local)?

13

Entiendo que el principio básico detrás del algoritmo para LLE consta de tres pasos.

  1. Encontrar la vecindad de cada punto de datos por alguna métrica como k-nn.
  2. Encuentre pesos para cada vecino que denotan el efecto que tiene el vecino en el punto de datos.
  3. Construya la incrustación de baja dimensión de los datos en función de los pesos calculados.

Pero la explicación matemática de los pasos 2 y 3 es confusa en todos los libros de texto y recursos en línea que he leído. No puedo razonar por qué se usan las fórmulas.

¿Cómo se realizan estos pasos en la práctica? ¿Hay alguna forma intuitiva de explicar las fórmulas matemáticas utilizadas?

Referencias: http://www.cs.nyu.edu/~roweis/lle/publications.html

Usuario1234321232
fuente

Respuestas:

10

La incrustación lineal local (LLE) elimina la necesidad de estimar la distancia entre objetos distantes y recupera la estructura no lineal global mediante ajustes lineales locales. LLE es ventajoso porque no involucra parámetros tales como tasas de aprendizaje o criterios de convergencia. LLE también escala bien con la dimensionalidad intrínseca de Y . La función objetivo para LLE es

ζ(Y)=(YWY)2=Y(IW)(IW)Y
Loselementos dematriz de pesoWwij para los objetosi yj se ponen a cero sij no es un vecino más cercano dei , de lo contrario, los pesos para K- los vecinos más cercanos del objetoi se determinan mediante un ajuste de mínimos cuadrados de donde la variable dependientees una
U=Gβ
UK×1vector de unos, es una matriz Gram para todos los vecinos más cercanos del objeto , y es un vector de pesos que siguen restricciones de suma a la unidad. Sea una matriz de distancia semidefinida positiva simétrica para todos los pares de los vecinos K más cercanos del objeto -dimensional . Se puede demostrar que es igual a la matriz de distancia doblemente centrada con elementos GK×KiβK×1DK×KpxiGτ
τlm=12(dlm21Kldlm21Kmdlm2+lmdlm2).
Los coeficientes de regresión se determinan numéricamente usando y están marcados para confirmar que suman a la unidad. Los valores de están incrustados en la fila de en las diversas posiciones de columna correspondientes a los vecinos K más cercanos del objetoK
βK×1=(ττ)K×K1τUK×1,
βiWi, así como los elementos de transposición. Esto se repite para cada ésimo objeto en el conjunto de datos. Vale la pena señalar que si el número de vecinos más cercanos es demasiado bajo, entonces puede ser escaso, lo que puede dificultar el análisis propio. Se observó que vecinos más cercanos dieron como resultado matrices que no contenían patologías durante el análisis propio. La función objetivo se minimiza al encontrar los valores propios distintos de cero más pequeños de La forma reducida de está representada poriKWK=9W
(IW)(IW)E=ΛDE.
XY=E donde tiene dimensiones basadas en los dos valores propios más bajos de . En×2Λ

NXG Logic
fuente
"K = 9 vecinos más cercanos" ¿No depende esto de la dimensionalidad de ? Por ejemplo, si tiene menos de 9 dimensiones, entonces la matriz de peso no se determina de manera única. ¿Esto causa problemas con LLE? Y WYYW
Scott
Sí, pero si hay, digamos, 8 dimensiones, entonces, para datos aleatorios, literalmente, cada punto puede escribirse perfectamente como una combinación lineal de otros 9, en un número infinito de formas.
Scott el
Siempre hay escenarios de "qué pasaría si" al implementar una técnica, y es por eso que se usan restricciones de parámetros.
NXG Logic