Maldición de la dimensión

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de abril de 2021; las comprobaciones requieren 4 ediciones .

La maldición de la dimensionalidad (CU) es un término utilizado en relación con una serie de propiedades de espacios de alta dimensión y problemas combinatorios . En primer lugar, se trata del crecimiento exponencial de los datos experimentales necesarios en función de la dimensión del espacio a la hora de resolver problemas de reconocimiento de patrones estadístico-probabilístico , aprendizaje automático , clasificación y análisis discriminante . Esto también se aplica al crecimiento exponencial en el número de opciones en problemas combinatorios dependiendo del tamaño de los datos iniciales, lo que conduce a un aumento correspondiente en la complejidad de los algoritmos de enumeración. La “maldición” también afecta a los métodos de optimización continua debido a la complejidad de la función objetivo multidimensional. En un sentido más amplio, el término se aplica a todas las propiedades "incómodas" o inusuales de los espacios de alta dimensión ya las dificultades de su estudio. En combinatoria, a menudo no significan la dimensión del espacio, sino el tamaño de los datos iniciales. En particular, en problemas de la teoría de Ramsey sería más exacto hablar de la '''maldición del tamaño''' de los datos iniciales incluso en el caso de problemas de dimensión mínima - el número de parámetros que definen el problema. El término fue introducido por primera vez por Richard Bellman en relación con el problema general de la programación dinámica [1] [2] . Esta expresión continúa utilizándose en trabajos sobre cibernética técnica, aprendizaje automático y análisis de sistemas complejos, incluso en los títulos de artículos científicos [3] .

Ejemplos típicos

• Supongamos que necesitamos restaurar la distribución de probabilidad de la variable aleatoria binaria más simple y con una precisión suficiente para nuestros objetivos, esto se puede hacer a partir de una muestra de mediciones u observaciones. Entonces, para restaurar la distribución de probabilidad de un vector a partir de variables aleatorias binarias con la misma precisión, se requiere una muestra de mediciones, lo que muchas veces resulta inaceptable en términos de costos de material o tiempo. El vector A -dimensional de cantidades binarias tiene valores posibles, y los intentos de restaurar su distribución rectilínea sobre la muestra experimental no son prometedores.
• En combinatoria, la enumeración de opciones en las computadoras modernas también es imposible. Por lo tanto, las soluciones exactas para problemas NP-difíciles y más complejos se pueden buscar por enumeración solo en el caso en que el tamaño de los datos iniciales se calcule en varias decenas de vértices del gráfico, requisitos, dispositivos, etc. El hecho de que algunos juegos con información completa , como el ajedrez, hoy son de interés, hay una consecuencia del PR.

En problemas de reconocimiento

En los problemas de reconocimiento probabilístico, hay dos situaciones en las que la maldición de la dimensionalidad se puede superar con la ayuda de enfoques generales.

1. Una situación es posible cuando la distribución de un vector de variables aleatorias interdependientes se concentra en un subespacio de menor dimensión, es decir, el vector puede ser bien aproximado por una función lineal de un número menor de variables. En este caso, el método de componentes principales permite reducir la dimensión. Además, las tareas establecidas de reconocimiento (discriminación) pueden resolverse ya en un espacio de baja dimensión.
2. Una situación es posible cuando las variables aleatorias de los vectores estudiados son independientes o, más realistas, débilmente interdependientes. En este caso, se pueden restaurar distribuciones unidimensionales de variables aleatorias y construir distribuciones multivariadas como sus productos. Además, utilizando la misma muestra de entrenamiento en el modo de examen deslizante, se puede restaurar la distribución unidimensional del cociente de las funciones de probabilidad de las clases diferenciables, lo que elimina el sesgo asociado con la interdependencia en la regla de decisión.

Usualmente, para el análisis de datos multidimensionales, se propone utilizar el método del vecino más cercano métrico [4] [5] . La ventaja del método es que formalmente puede aplicarse a muestras de cualquier tamaño, independientemente de la dimensión de los vectores. Pero el problema fundamentalmente aplicado de PR es que en una muestra limitada de datos no hay suficiente información sobre un objeto descrito por una gran cantidad de parámetros significativos. Y si esta descripción es realmente compleja y multidimensional, y la solución del problema requiere un análisis de todo el complejo de parámetros, entonces el problema resulta difícil y no puede resolverse por métodos generales.

Problemas de optimización

En los problemas de optimización también existen métodos que facilitan la solución de problemas de gran escala.

• En los problemas de optimización de enumeración discreta, el tiempo de ejecución de los algoritmos se puede reducir utilizando el método de bifurcación y límite y algoritmos heurísticos aproximados (consulte Esquema de tiempo polinomial aproximado ).
• En el método de optimización del descenso de gradientes para algunas funciones objetivo de muchas variables, el método de barrancos aumenta significativamente la eficiencia. [6]

Todos estos métodos de lucha no resuelven radicalmente el problema de las relaciones públicas y son efectivos solo en casos especiales.

En la teoría de Ramsey

Aunque los problemas de la teoría de Ramsey generalmente permiten generalizaciones multidimensionales, son difíciles incluso con dimensiones mínimas y tamaños de datos de entrada pequeños.

• En particular, no se conoce el número de Ramsey R (5,5), el tamaño mínimo de un grupo de personas en el que hay un grupo de 5 personas que se conocen en parejas o no se conocen en parejas. Pal Erdős señaló que, en caso de emergencia, la humanidad podría resolver este problema al concentrar las mejores mentes y el poder de cómputo en él. Pero la definición del número R(6,6) está más allá del poder de la humanidad moderna [7] .
• La conjetura del polígono de Szekeres-Erdős , que es tanto un problema de geometría combinatoria como un problema de la teoría de Ramsey, tampoco se ha probado hasta el día de hoy, incluso en la formulación bidimensional original del problema.

En geometría combinatoria

En geometría combinatoria, hay varios problemas estrictamente matemáticos difíciles relacionados directamente con la dimensión del espacio.

• El ejemplo más llamativo es el problema de Nelson-Erdős-Hadwiger sobre el número cromático de espacios métricos. A día de hoy (2013) no se conoce este número ni siquiera para el espacio euclidiano de dimensión 2. Solo se sabe que el número cromático del plano está en el intervalo [5,7] [8] . Por otro lado, para este problema se pudo probar el orden exponencial de crecimiento del número cromático para grandes dimensiones espaciales.
• Otro problema difícil es el problema de Borsuk . La conjetura de Borsuk ahora ha sido probada para espacios de dimensión 3 como máximo y refutada para espacios de dimensión 65 como mínimo. Por lo tanto, la cuestión sigue sin resolverse para un gran segmento de dimensiones espaciales. En este problema, ni siquiera se ha probado el supuesto crecimiento exponencial del número requerido de partes de la partición.

Algunas propiedades "inusuales" de los espacios multidimensionales

• Es fácil ver que si establecemos cualquier valor positivo , entonces la fracción del volumen de un cubo o bola multidimensional en la vecindad del límite tiende a 1 con un aumento ilimitado en la dimensión. Así, en cuerpos multidimensionales, la mayor parte del volumen está "cerca" del límite. Por lo tanto, los puntos de incluso muestras experimentales grandes, por regla general, son límites: se encuentran en el casco convexo del conjunto o cerca de él.
• Según la CLT , la probabilidad de que dos vectores aleatorios sean normales, dentro de cualquier error positivo predeterminado, tiende a 1 a medida que aumenta la dimensión del espacio.

Notas

1. ↑ Richard Ernest Bellman; corporación rand. Programación dinámica  (indefinida) . - Prensa de la Universidad de Princeton , 1957. - ISBN 978-0-691-07951-6 . ,
   republicado: Richard Ernest Bellman. Programación Dinámica  (indefinida) . — Publicaciones de Courier Dover , 2003. — ISBN 978-0-486-42809-3 .
2. ↑ Richard Ernest Bellman. Procesos de control adaptativo : una visita guiada  . — Prensa de la Universidad de Princeton , 1961.
3. ↑ Powell, Warren B. 2007. Programación dinámica aproximada: resolución de las maldiciones de la dimensionalidad. Wiley, ISBN 0-470-17155-3 .
4. ↑ Marimont, RB; Shapiro, MB Búsquedas de vecinos más cercanos y la maldición de la dimensionalidad  // IMA J Appl  Math : diario. - 1979. - vol. 24 , núm. 1 . - Pág. 59-70 . -doi : 10.1093 / imamat/24.1.59 .
5. ↑ Radovanovic, Milos; Nanopoulos, Alexandros; Ivanovic, Mirjana. Hubs en el espacio: Vecinos más cercanos populares en datos de alta dimensión  //  Journal of Machine Learning Research  : journal. - 2010. - Vol. 11 _ - Pág. 2487-2531 .
6. ↑ CONOCE EL INTUITO | Conferencia | El método de descenso más empinado. Método de Davidon-Fletcher-Powell. El problema del barranco. El problema de la multiextremidad . Consultado el 26 de abril de 2022. Archivado desde el original el 27 de diciembre de 2016. (indefinido)
7. ↑ Joel H. Spencer (1994), Diez conferencias sobre el método probabilístico , SIAM , p. 4, ISBN 978-0-89871-325-1 
8. ↑ Aubrey D.N.J. D.E. Grey. El número cromático del plano es al menos 5  // math.CO. — 2018. Archivado el 12 de julio de 2018.

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ACI LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG