¿Existen versiones de t-SNE para el flujo de datos?

Question

Mi comprensión de t-SNE y la aproximación de Barnes-Hut es que todos los puntos de datos son necesarios para que todas las interacciones de fuerza puedan calcularse al mismo tiempo y cada punto pueda ajustarse en el mapa 2d (o de dimensión inferior).

¿Existen versiones de t-sne que puedan tratar eficazmente datos en flujo continuo? Así que si mis observaciones están llegando uno a la vez, se encuentra la mejor ubicación en el mapa 2d para colocar la nueva observación, o actualizar continuamente todos los puntos en el mapa 2d para tener en cuenta ht nueva observación.

¿Tendría esto algún sentido o iría en contra de la configuración de t-sne.

Answer 1

Yo tenía exactamente la misma pregunta y la publiqué en un vídeo de YouTube de una conferencia sobre CS231n impartida por Andrej Karpathy hace unas semanas. Aquí está la pregunta que publiqué seguida de la respuesta de Andrej:

https://www.youtube.com/watch?v=ta5fdaqDT3M&lc=z12ji3arguzwgxdm422gxnf54xaluzhcx

Q:

¿Necesita t-SNE un lote completo de crear el espacio de características de baja dimensión? Con PCA se puede crear un espacio de características de baja dimensión en un lote de datos y, a continuación, proyectar nuevos puntos de datos en ese mismo espacio sin tener que "reentrenar". ¿Es t-SNE?

Lo pregunto porque me di cuenta de que scikit-learn tiene t-SNE como parte de su clase manifold, pero ese módulo no tiene un método transform() como lo tiene PCA. Así que, al menos, en sklearn, parecería que esto no es posible.

Mi pregunta se reduce a lo siguiente. ¿Cómo se aplicaría t-SNE en un situación de streaming o en línea en la que desea actualizar continuamente la visualización con nuevas imágenes? Presumiblemente, uno no querría aplicar el algoritmo en todo el lote para cada nueva imagen.

A:

+Evan Zamir Sí, esto es posible con t-SNE, pero tal vez no sea compatible con las implementaciones regulares de t-SNE. Normalmente cada la ubicación de cada punto es un parámetro en la optimización, pero se puede puede crear un mapeo de alta-D -> baja-D (por ejemplo, red neuronal) y backprop a través de las ubicaciones. Entonces usted termina con la incrustación y puede proyectar nuevos puntos. Así que nada impide que esto en principio, pero algunas implementaciones podrían no soportarlo ya que es un caso de uso menos frecuente.

Answer 2

Al tratar con datos en flujo, puede que no desee/necesite incrustar todos los puntos del historial en un único mapa t-SNE. Como alternativa, puede realizar un incrustación en línea siguiendo estos sencillos pasos:

1. elija una ventana temporal de duración T, lo suficientemente larga como para que cada patrón de interés aparezca al menos un par de veces en la duración de la ventana.

2. Desplace la ventana a medida que entren los datos, con un paso de tiempo dt mucho menor que T. Para cada posición de la ventana, calcule una incrustación t-SNE de los puntos de datos en la ventana temporal.

3. sembrar cada incrustación con el resultado de la anterior. En t-SNE, hay que elegir las coordenadas iniciales de los puntos de datos en el espacio de baja dimensión. En nuestro caso, como elegimos dt mucho más pequeño que T, dos incrustaciones sucesivas comparten la mayoría de sus puntos de datos. Para todos los puntos de datos compartidos, hacer coincidir sus coordenadas iniciales en la incrustación actual con sus coordenadas finales en la incrustación anterior . Este paso garantizará que patrones similares tengan una representación coherente en las sucesivas incrustaciones. (en la implantación de sklearn en python, el parámetro semilla es "init". Por defecto, la implementación de sklearn establece la posición inicial de los puntos de forma aleatoria)

Nota 1: Es importante que los patrones de interés aparezcan al menos una vez en cualquier ventana temporal, para que la memoria de la representación no se pierda a medida que la ventana se desliza por el conjunto de datos. De hecho, t-SNE no suele converger a una solución única, sino sólo a un mínimo local, por lo que si se pierde la memoria, un patrón similar podría representarse de forma muy diferente en dos instancias de una incrustación.

Nota 2: Este método es especialmente pertinente cuando se trata de series temporales no estacionarias, en las que se desea seguir patrones que evolucionan lentamente a lo largo del tiempo. De hecho, cada incrustación se adapta específicamente a la pequeña ventana temporal en la que se calcula, lo que garantiza que captura la estructura temporal local de la mejor manera posible (a diferencia de una incrustación completa de todo el conjunto de datos no estacionarios).

Nota 3: En este método, las incrustaciones sucesivas no se pueden paralelizar, porque se necesita el resultado de la incrustación anterior para sembrar la siguiente. Sin embargo, como la semilla (es decir, las coordenadas iniciales de los puntos) está bien elegida para la mayoría de los puntos (todos los puntos compartidos entre las incrustaciones sucesivas), una incrustación suele converger muy rápidamente, en unas pocas iteraciones.

Para ver un ejemplo de aplicación de este método a series temporales no estacionarias, consulte este artículo ( ICLR 2016, Aprendizaje de representaciones estables en un mundo cambiante con t-SNE en línea: prueba de concepto en el pájaro cantor ), donde se aplicó con éxito para rastrear la aparición de sílabas a lo largo del desarrollo en el pájaro cantor.

Answer 3

Existe una variante publicada recientemente, denominada A-tSNE, que permite añadir nuevos datos de forma dinámica y refinar los clusters en función de las áreas de interés o mediante la introducción de datos por parte del usuario. El artículo enlazado más abajo contiene algunos buenos ejemplos:

Cita: arXiv:1512.01655

tSNE aproximado y dirigible por el usuario para el análisis visual progresivo Nicola Pezzotti, Boudewijn P.F. Lelieveldt, Laurens van der Maaten, Thomas Höllt, Elmar Eisemann, Anna Vilanova

Resumen:

El objetivo de la Analítica Visual Progresiva es mejorar la interactividad de las técnicas analíticas existentes mediante la visualización y la interacción con los resultados intermedios. Un método clave para el análisis de datos es la reducción de la dimensionalidad, por ejemplo, para producir incrustaciones 2D que puedan visualizarse y analizarse de manera eficiente. t-Distributed Stochastic Neighbor Embedding (tSNE) es una técnica muy adecuada para la visualización de varios datos de alta dimensión. tSNE puede crear resultados intermedios significativos, pero adolece de una inicialización lenta que limita su aplicación en Progressive Visual Analytics. Introducimos una aproximación tSNE controlable (A-tSNE), que compensa velocidad y precisión, para permitir la exploración interactiva de datos. Ofrecemos técnicas de visualización en tiempo real, incluyendo una solución basada en la densidad y una Lente Mágica para inspeccionar el grado de aproximación. Con esta retroalimentación, el usuario puede decidir sobre refinamientos locales y dirigir el nivel de aproximación durante el análisis. Demostramos nuestra técnica con varios conjuntos de datos, en un escenario de investigación del mundo real y para el análisis en tiempo real de flujos de alta dimensión, con el fin de ilustrar su eficacia para el análisis interactivo de datos.

Answer 4

La aproximación Barnes-Hut hace que t-SNE sea altamente escalable (al menos, se puede utilizar con 100 000 líneas, lo he probado). Se puede llamar desde R : Rtsne

La complejidad del algoritmo aplicado es $O(n\log(n))$ mientras que la aplicación ingenua tenía una complejidad de $O(n^2)$ . Los detalles de la aproximación subyacente pueden consultarse aquí Aceleración de t-SNE mediante algoritmos basados en árboles.

Answer 5

La aproximación Barnes-Hut es ahora el método por defecto en scikit-learn a partir de la versión 0.17.0:

Por defecto el algoritmo de cálculo del gradiente utiliza Barnes-Hut que se ejecuta en tiempo O(NlogN). method='exact' se ejecutará en tiempo algoritmo más lento, pero exacto, en tiempo O(N^2). El algoritmo exacto debe utilizarse cuando los errores del vecino más cercano deben ser superiores al 3%. Sin embargo, el método exacto no es escalable a millones de ejemplos. Nuevo en versión 0.17: Método de optimización aproximada a través de Barnes-Hut.