¿La maldición de la dimensionalidad afecta a algunos modelos más que a otros?

15

Los lugares que he estado leyendo sobre la maldición de la dimensionalidad lo explican conjuntamente con kNN principalmente, y los modelos lineales en general. Regularmente veo a los mejores clasificados en Kaggle usando miles de características en el conjunto de datos que apenas tiene 100k puntos de datos. Utilizan principalmente árboles potenciados y NN, entre otros. Que muchas características parecen demasiado altas y creo que se verían afectadas por la maldición de la dimensionalidad. Pero ese no parece ser el caso, ya que estos modelos los convierten en los mejores de la competencia. Entonces, volviendo a mi pregunta original: ¿algunos modelos se ven afectados por la maldición de la dimensionalidad más que otros?

Específicamente, estoy interesado en los siguientes modelos (solo porque estos son los que conozco / utilizo):

  • Regresión Lineal y Logística
  • Árboles de decisión / Bosque aleatorio / Árboles potenciados
  • Redes neuronales
  • SVM
  • kNN
  • k-significa agrupamiento
neural-networks svm k-means k-nearest-neighbour high-dimensional Dileep Kumar Patchigolla
fuente
La respuesta corta es definitivamente sí, pero ¿tal vez quieres modelos que realmente te interesen? Estoy seguro de que la comunidad de CV podría informarle sobre miles de diferentes tipos de modelos que se ven afectados por la maldición de la dimensionalidad. Por lo tanto, reducir su enfoque a cierto tipo de modelos puede ayudarlo a responder esta pregunta.
@RustyStatistician - He agregado algunos modelos que me interesan.
Dileep Kumar Patchigolla
Estoy bastante interesado en esta pregunta, pero quedó sin respuesta. ¿Cómo puedo mencionar esto en visibilidad para obtener respuestas?
Dileep Kumar Patchigolla

Respuestas:

17

En general, la maldición de la dimensionalidad hace que el problema de buscar en un espacio sea mucho más difícil y afecta a la mayoría de los algoritmos que "aprenden" a través de la división de su espacio vectorial. Cuanto mayor sea la dimensionalidad de nuestro problema de optimización, más datos necesitamos para llenar el espacio sobre el que estamos optimizando.

Modelos lineales generalizados

β^=(X′X)−1X′y

Árboles de
decisión Los árboles de decisión también sufren la maldición de la dimensionalidad. Los árboles de decisión dividen directamente el espacio muestral en cada nodo. A medida que aumenta el espacio muestral, aumenta la distancia entre los puntos de datos, lo que hace que sea mucho más difícil encontrar una división "buena".

Bosques al
azar Los bosques al azar usan una colección de árboles de decisión para hacer sus predicciones. Pero en lugar de usar todas las características de su problema, los árboles individuales solo usan un subconjunto de las características. Esto minimiza el espacio que cada árbol está optimizando y puede ayudar a combatir el problema de la maldición de la dimensionalidad.

Los
algoritmos de refuerzo de Boosted Tree , como AdaBoost, sufren la maldición de la dimensionalidad y tienden a sobreajustarse si no se utiliza la regularización. No profundizaré, porque la publicación ¿AdaBoost es menos o más propenso a sobreajustar? explica la razón por qué mejor de lo que podría

Redes neuronales
Las redes neuronales son raras en el sentido de que ambas son y no son impactadas por la maldición de la dimensionalidad dependiente de la arquitectura, activaciones, profundidad, etc. Por lo tanto, para reiterar la maldición de la dimensionalidad es el problema que una gran cantidad de puntos son necesarios en alta dimensiones para cubrir un espacio de entrada. Una forma de interpretar redes neuronales profundas es pensar que todas las capas esperan que la última capa haga una proyección complicada de un múltiple de alta dimensión en un múltiple de menor dimensión, donde luego la última capa se clasifica en la parte superior. Entonces, por ejemplo, en una red convolucional para clasificación donde la última capa es una capa softmax, podemos interpretar que la arquitectura realiza una proyección no lineal en una dimensión más pequeña y luego realiza una regresión logística multinomial (la capa softmax) en esa proyección. Entonces, en cierto sentido, la representación comprimida de nuestros datos nos permite evitar la maldición de la dimensionalidad. Una vez más, esta es una interpretación, en realidad la maldición de la dimensionalidad impacta las redes neuronales, pero no al mismo nivel que los modelos descritos anteriormente.

SVM
SVM tiende a no sobreajustarse tanto como los modelos lineales generalizados debido a la regularización excesiva que ocurre. Echa un vistazo a esta publicación SVM, Overfitting, curse of dimensionality para más detalles.

K-NN, K-medias

Tanto K-mean como K-NN se ven muy afectados por la maldición de la dimensionalidad, ya que ambos usan la medida de la distancia al cuadrado L2. A medida que aumenta la cantidad de dimensiones, también aumenta la distancia entre varios puntos de datos. Es por eso que necesita una mayor cantidad de puntos para cubrir más espacio con la esperanza de que la distancia sea más descriptiva.

Siéntase libre de preguntar detalles sobre los modelos, ya que mis respuestas son bastante generales. Espero que esto ayude.

Armen Aghajanyan
fuente
Hola, amén. Grandes explicaciones sucintas para todos los modelos que he pedido. Los problemas con los modelos lineales todavía no están claros para mí: ¿Los modelos lineales funcionan mejor o peor que los modelos k-NN y k-Means para el mismo número de dimensiones? Y cuando dijo que la colinealidad es un problema para los modelos lineales, ¿implica que sin colinealidad (o mínima), las altas dimensiones no son un problema con los modelos lineales?
Dileep Kumar Patchigolla
Es difícil cuantificar si los modelos lineales funcionarán mejor que k-nn o k-means para un problema arbitrario. Si su problema es linealmente separable, colocaría mis apuestas en el modelo lineal, mientras que si su espacio es un poco más complicado, elegiría k-nn. La colinealidad empeora el problema de la maldición de la dimensionalidad, incluso sin colinealidad, la maldición de la dimensionalidad todavía se aplica. Las medias K deberían sufrir en la misma medida que k-nn, ya que ambas son impulsadas por los vecinos, y generalmente usan la misma función de distancia. En realidad, es difícil cuantificar qué tan malo es el DQO. ¡Espero que esto ayude!
Armen Aghajanyan
¿Cuál es su definición de maldición de dimensionalidad (CoD)? Su respuesta parece sugerir que los modelos lineales son los que más sufren de CoD, esto es engañoso: al ser un método global, los modelos lineales sufren mucho menos que los métodos localizados como KNN.
Matifou