Reducción de la dimensionalidad con t-SNE

Voy a explicar aquí lo que he aprendido recientemente sobre t-SNE, una técnica para reducir la dimensionalidad de conjuntos de datos. Es una alternativa moderna a MDS o PCA.

Partimos de puntos $latex x_1, \dots, x_n$ y buscamos otros $latex y_1, \dots, y_n$ en un espacio de menor dimensión. Para ello construiremos primero $latex n$ distribuciones de probabilidad, $latex p_i$ sobre los enteros $latex 1, \dots, n$ de forma que

$$ p_i(j) \propto d_x(x_i, x_j),$$

donde $latex d_x$ es una determinada distancia entre puntos en el espacio original. De la misma manera, construimos sendas distribuciones de probabilidad, $latex q_i$,

$$ q_i(j) \propto d_y(y_i, y_j),$$

donde $latex d_y$ es otra distancia entre puntos en el espacio de dimensión inferior.

Lo ideal sería encontrar puntos $latex y_1, \dots, y_n$ tales que cada $latex p_i$ sea lo más parecida posible a la correspondiente $q_i$. Por ejemplo, de entre todas las opciones posibles, de manera que la suma de las divergencias de Kullback-Leibler entre las parejas de distribuciones sea lo menor posible.

Minimícese esa suma, i.e., encuéntrense los puntos $latex y_1, \dots, y_n$ que la minimizan, y ya.

Más:

Nota curiosa: creo que he usado el adjetivo distributivo sendas por primera vez en la vida.

Fe de errores: donde arriba escribí distancia debí haber escrito similitud. Una similitud es una función decreciente de la distancia. Obviamente, se busca una similitud estrictamente positiva (como por la que optaron los creadores del algoritmo).

Nota para matemáticos: aparte del problema de que el mínimo pueda ser local y no global, es obvio que si las similitudes están basadas en distancias euclídeas (como es el caso en la implementación de los autores) la solución no es única: dada una solución, lo serán también traslaciones y rotaciones suyas.