Para comprender el problema de ANN, primero debemos comprender el problema de búsqueda del vecino más cercano (NN).
El problema NN es un problema de optimización que solicita puntos (o elementos de conjunto) que minimiza una métrica (d) a un punto de consulta (q) en algún espacio métrico (U).
[matemáticas] \ text {NN} (q) = \ text {argmin} _ {x \ en U} d (x, q) [/ math]
Este problema es muy común como subproblema de varios problemas en geometría computacional, aprendizaje automático, visión por computadora, bases de datos, gráficos por computadora, etc. (por ejemplo, clasificación, recomendación, agrupamiento, colisión de objetos). El desafío de NN llega cuando te enfrentas a grandes conjuntos de datos con puntos en un espacio de alta dimensión, ya que la fuerza bruta es [matemática] O (n ^ d) [/ matemática]. Después de décadas de esfuerzos, todos los algoritmos exactos adolecen de espacio exponencial o complejidad de tiempo.
- ¿Cuál es la diferencia entre ML y NLP?
- ¿Por qué no podemos hacer una puerta XOR con 1 neurona?
- ¿Cuál es el mejor artículo para entender cómo se mapea el vector de salida de RNN con un vocabulario para predecir la secuencia?
- ¿El bosque aleatorio funciona con variables categóricas?
- ¿Hasta dónde nos pueden llevar las redes neuronales / de aprendizaje profundo / IA para encontrar una solución al problema de las noticias falsas?
Una de las posibles ideas es que a medida que la dimensión crece, la distancia entre los puntos se vuelve más “indistinguible”, debido a la “maldición de la dimensionalidad” (la división del espacio en la cuadrícula da como resultado exponencialmente más puntos a medida que la dimensión crece). El fenómeno se observa en diversas situaciones teóricas y prácticas, por ejemplo, métodos sin muestreo para la integración de alta dimensión [1]. En una situación práctica, la distancia es solo un indicador de alguna otra medida (satisfacción del usuario, similitud de documentos) y puede aceptarse algún error en esta medida.
Entonces, ANN puede formularse como el problema de buscar NN, pero aceptando cierto grado de errores o alguna holgura en el cálculo de la distancia. Esta formulación es una relajación del problema NN y ha demostrado en la práctica y la teoría que ofrece un mejor rendimiento (aproximadamente [matemática] O (dn ^ {(1 / c)}) [/ matemática] complejidad de tiempo y espacio polinomial, donde c es la holgura en el cálculo de la distancia [2]).
[1] Sección 3.11 del Teorema del límite central, Ley de grandes números y Métodos de Monte Carlo.
[2] Más allá de LSH por Alex Andoni
