Hacia las estructuras matemáticas de las redes (de grandes datos)

La forma matemática de las cosas por venir

Los conjuntos de datos científicos se están volviendo más dinámicos, requiriendo nuevas técnicas matemáticas a la par con la invención del cálculo.

Quanta Magazine |  Tang Yau Hoong y Jennifer Ouellette



Simon DeDeo, un investigador en matemáticas aplicadas y sistemas complejos en el Instituto Santa Fe, tenía un problema. Colaboraba en un nuevo proyecto que analizaba 300 años de datos de los archivos de Old Bailey de Londres, la corte penal central de Inglaterra y Gales. Por supuesto, había datos limpios en el formato simple de hoja de cálculo de Excel, incluyendo variables tales como acusación, veredicto y sentencia para cada caso. Pero también hubo transcripciones completas de la corte, conteniendo unos 10 millones de palabras registradas durante poco menos de 200.000 ensayos.

-¿Cómo diablos analizas esos datos? -preguntó DeDeo. No era el tamaño del conjunto de datos que era desalentador; Por los grandes estándares de datos, el tamaño era bastante manejable. Fue la complejidad y la falta de estructura formal lo que planteó un problema. Estos "grandes datos" no se parecían a los tipos de conjuntos de datos tradicionales que el antiguo físico habría encontrado antes en su carrera, cuando el paradigma de investigación implicaba formar una hipótesis, decidir precisamente lo que se quería medir, construir un aparato para hacer esa medición tan preciso como sea posible.

Los grandes datos de hoy son ruidosos, desestructurados y dinámicos.

"En física, por lo general tiene un tipo de datos y usted conoce el sistema realmente bien", dijo DeDeo. "Ahora tenemos estos nuevos datos multimodales [extraídos] de sistemas biológicos y sistemas sociales humanos, y los datos se recogen antes incluso de tener una hipótesis". Los datos están ahí en toda su desordenada y multidimensional gloria, esperando ser consultados , Pero ¿cómo se sabe qué preguntas hacer cuando el método científico se ha vuelto en la cabeza?

DeDeo no es el único investigador que está haciendo frente a estos desafíos. A través de cada disciplina, los conjuntos de datos son cada vez más grandes y complejos, ya se trate de registros médicos, secuenciación genómica, redes neuronales en el cerebro, astrofísica, archivos históricos o redes sociales. Alessandro Vespignani, un físico de la Northeastern University que se especializa en aprovechar el poder de las redes sociales para modelar brotes de enfermedades, el comportamiento del mercado de valores, la dinámica social colectiva y los resultados electorales, ha recogido muchos terabytes de datos de redes sociales como Twitter, Crudo y no estructurado. "No definimos las condiciones de los experimentos, así que no sabemos lo que estamos capturando", dijo.


Gunnar Carlsson, un matemático de la Universidad de Stanford, utiliza el análisis de datos topológicos para encontrar estructura en conjuntos de datos complejos y no estructurados.

Los datos grandes de hoy en día son ruidosos, no estructurados y dinámicos en lugar de estáticos. También puede estar dañado o incompleto. "Creemos que los datos están compuestos de vectores, una serie de números y coordenadas", dijo Jesse Johnson, matemático de la Universidad Estatal de Oklahoma. Pero los datos de Twitter o Facebook, o los archivos de prueba del Old Bailey, no parecen nada de eso, lo que significa que los investigadores necesitan nuevas herramientas matemáticas para recoger información útil de los conjuntos de datos. "O se necesita una forma más sofisticada de traducirla en vectores, o se necesita encontrar una forma más generalizada de analizarla", dijo Johnson.

Vespignani utiliza una amplia gama de herramientas matemáticas y técnicas para dar sentido a sus datos, incluyendo el reconocimiento de texto. Él filtra a través de millones de tweets buscando las palabras más relevantes a cualquier sistema que está tratando de modelo. DeDeo adoptó un enfoque similar para el proyecto de archivos Old Bailey. Su solución fue reducir su conjunto de datos iniciales de 100.000 palabras agrupándolas en 1.000 categorías, utilizando palabras clave y sus sinónimos. "Ahora usted ha convertido el juicio en un punto en un espacio de 1000 dimensiones que le dice cuánto el juicio es acerca de la amistad, o la confianza, o la ropa", explicó.

Científicos como DeDeo y Vespignani hacen buen uso de este enfoque poco sistemático para el análisis de datos, pero el matemático de la Universidad de Yale, Ronald Coifman, dice que lo que realmente se necesita es el gran equivalente de datos de una revolución newtoniana, a la par del siglo XVII. Cree que ya está en marcha. No es suficiente, argumenta, simplemente recoger y almacenar cantidades masivas de datos; Deben ser comisariados inteligentemente, y eso requiere un marco global. "Tenemos todos los pedazos del rompecabezas - ahora cómo los montamos realmente así que podemos ver el cuadro grande?" Él dijo. "Puede que tengas un modelo muy simplista a pequeña escala local, pero el cálculo te permite tomar muchos modelos sencillos e integrarlos en un gran cuadro". De manera similar, Coifman cree que la matemática moderna -especialmente la geometría- puede ayudar a identificar los factores globales subyacentes Estructura de grandes conjuntos de datos. Un conjunto de datos podría estar organizado por geografía o clima, por ejemplo, cada uno de los cuales producirá un mapa de formas muy diferentes.

Nodos y enlaces

La ciudad prusiana de Königsberg (ahora Kalingrad), en el Mar Báltico, cuenta con cuatro regiones geográficas distintas divididas por el río Pregel, con siete puentes que conectan esas regiones. En el siglo XVIII, el matemático Leonhard Euler perplejo sobre un enigma popular de esa época: ¿Era posible caminar a través de todos los puentes de Königsberg, cruzar cada uno apenas una vez, y todavía terminar en su punto de partida original? Para resolver el rompecabezas, Euler redujo el problema a uno de los nodos y líneas: Las cuatro regiones terrestres eran los nodos, conectados por los puentes, representados por líneas. Él encontró que para cruzar todos los puentes solamente una vez, cada región de la tierra necesitaría un número par de puentes. Dado que ese no era el caso en Königsberg, tal viaje era imposible.

Los métodos topológicos se parecen mucho a la proyección de una sombra bidimensional de un objeto tridimensional en la pared.
Gunnar Carlsson

Entre las ideas más notables que Euler recogió del rompecabezas fue que las posiciones exactas de los puentes eran irrelevantes para la solución; Todo lo que importaba era el número de puentes y cómo estaban conectados. Los matemáticos ahora reconocen en esto las semillas del campo moderno de la topología.

Tomando una página del libro de ejercicios de Euler, Gunnar Carlsson, un matemático de la Universidad de Stanford, representa complejos y complejos grandes conjuntos de datos como una red de nodos y enlaces, creando un mapa intuitivo de datos basado únicamente en la similitud de los puntos de datos; Esto utiliza la distancia como una entrada que se traduce en una forma o red topológica. Cuanto más similares sean los puntos de datos, más cerca estarán unos de otros en el mapa resultante; Cuanto más diferentes sean, más distantes estarán en el mapa. Esta es la esencia del análisis de datos topológicos (TDA).

TDA es una consecuencia de la máquina de aprendizaje, un conjunto de técnicas que sirve como un caballo de batalla estándar de análisis de datos grandes. Muchos de los métodos de aprendizaje automático son más eficaces cuando se trabaja con matrices de datos, como una hoja de cálculo de Excel, pero ¿qué pasa si su conjunto de datos no se ajusta a ese marco? "El análisis de datos topológicos es una forma de obtener datos estructurados a partir de datos no estructurados para que los algoritmos de aprendizaje automático puedan actuar más directamente en él", dijo Carlsson.

Al igual que con los puentes de Euler, se trata de las conexiones. Las redes sociales trazan las relaciones entre las personas, con grupos de nombres (nodos) y conexiones (aristas) que ilustran cómo todos estamos conectados. Habrá grupos relacionados con la familia, compañeros de la universidad, los conocidos en el lugar de trabajo, y así sucesivamente. Carlsson piensa que es posible extender este enfoque a otros tipos de conjuntos de datos, como las secuencias genómicas. "Uno puede poner las secuencias al lado del otro y contar el número de lugares donde difieren", explicó. "Ese número se convierte en una medida de lo similar o disimilar que son, y se puede codificar como una función de distancia".

La idea es reducir conjuntos de datos grandes y crudos de muchas dimensiones a una representación comprimida en dimensiones inferiores sin sacrificar las propiedades topológicas más relevantes. Idealmente, esto revelará la forma subyacente de los datos. Por ejemplo, una esfera existe técnicamente en todas las dimensiones, pero sólo podemos percibir las tres dimensiones espaciales. Sin embargo, hay gafas matemáticas a través de las cuales uno puede recoger información sobre estas formas de dimensiones superiores, dijo Carlsson. "Una forma es un número infinito de puntos y una cantidad infinita de distancias entre esos puntos. Pero si usted está dispuesto a sacrificar un poco de redondez, puede representar [un círculo] por un hexágono con seis nodos y seis enlaces, y todavía es reconocible como una forma circular.

Esa es la base de la tecnología patentada que Carlsson ofrece a través de su empresa start-up, Ayasdi, que produce una representación comprimida de datos dimensionales altos en bits más pequeños, similar a un mapa del sistema de tubos de Londres. Tal mapa puede no representar exactamente la última característica de definición de la ciudad, pero destaca las regiones primarias y cómo estas regiones están conectadas. En el caso del software de Ayasdi, el mapa resultante no es sólo una visualización llamativa de los datos; También permite a los usuarios interactuar directamente con el conjunto de datos de la misma manera que utilizarían Photoshop o Illustrator. "Significa que no seremos enteramente fieles a los datos, pero si el conjunto de las representaciones inferiores tiene rasgos topológicos, es una buena indicación de que también hay características en los datos originales", dijo Carlsson.

Si su conjunto de datos de alta dimensión tiene 155 variables, ¿cómo empieza a consultarla de una manera que tenga en cuenta todas esas variables? Carlsson compara la tarea con la búsqueda de un martillo en un garaje oscuro. Si la única herramienta que tienes es una linterna, todo lo que puedes hacer es brillar la luz en una pequeña sección del garaje a la vez. Usted puede encontrar el martillo con el tiempo, pero también podría quedarse sin paciencia con el enfoque fragmentado. Sería mucho más eficiente encender una gran luz que ilumina todo el garaje, dándole una perspectiva global. No sólo va a detectar el martillo, pero también se dará cuenta de la caja de clavos sentados al lado de que no se dio cuenta de que era necesario. La tecnología de Ayasdi es similar a iluminar el garaje entero.

Como prueba de principio, Carlsson y colaboradores en Stanford y el Instituto de Estudios Avanzados de Princeton aplicaron este método a un conjunto de datos más tradicionales de un estudio holandés de genómica sobre pacientes con cáncer de mama realizado hace más de una década. Inicialmente se encontraba en la hoja de cálculo estándar de Excel, con 1.500 columnas y 272 filas correspondientes a las muestras genómicas proporcionadas por los sujetos. Una vez que esto se transformó en una red, el "mapa" resultante tomó la forma de una forma Y, codificada por color para indicar qué temas sobrevivieron (azul) y qué sujetos no (rojo). Los pacientes con peores pronósticos se agruparon en la rama izquierda del Y, con la rama derecha compuesta exclusivamente por el 8 al 9 por ciento de los sujetos que sobrevivieron. Una vez que ese grupo había sido identificado, los genetistas podrían analizar los genes más de cerca para determinar cuáles tenían más probabilidades de haber influido en su supervivencia.

El método es lo suficientemente flexible como para ser aplicado a sistemas muy diferentes. Uno de los internos de Carlsson Ayasdi era un nativo de Houston y un fan de los Rockets de Houston. Creó un conjunto de datos de todos los jugadores de la NBA a partir de 2010 y comparó sus medias de la liga en siete categorías estadísticas: puntos, rebotes, asistencias, robos, tiros bloqueados, pérdidas de balón y faltas personales, reducidos a intervalos de un minuto para asegurar que el tiempo de juego No ser un factor.

Si resulta que hay una vaca esférica al acecho debajo de todos sus datos, entonces TDA sería el camino a seguir. Pero si no está allí, ¿qué puedes hacer?
Benjamin Recht

Inicialmente presentó los datos en una hoja de cálculo estándar de Excel, con 400 filas para los jugadores y siete columnas para los puntos de datos, pero el software Ayasdi detectó patrones estadísticos ocultos entre los jugadores, vinculados a sus estilos de juego, y creó un mapa de estas conexiones. El mapa mostró que además de las cinco posiciones principales en el baloncesto - guardia de puntos, guardia de tiro, delantero de potencia, delantero pequeño y centro - había 13 posiciones "ocultas". Él dobló una categoría "protectores de la pintura," los jugadores que realizan bien en el rebote y el bloqueo, pero que acumulan más faltas que puntos. "Los protectores de pintura de puntuación" son similares, pero acumulan menos faltas y más puntos. Este trabajo ganó el premio a la Mejor Evolución del Deporte en la Conferencia MIT Sloan Sports Analytics anual, en parte debido a su potencial utilidad para la identificación de jugadores infravalorados.

Los métodos topológicos se parecen mucho a la proyección de una sombra bidimensional de un objeto tridimensional en la pared: nos permiten visualizar un conjunto de datos grandes y de gran dimensión proyectándolo en una dimensión inferior. El peligro es que, al igual que con las ilusiones creadas por los títeres de la sombra, uno podría estar viendo patrones e imágenes que no están realmente allí.

"Hay una broma matemática terrible que los topólogos no pueden diferenciar entre su parte trasera y una taza de café porque los dos son topológicamente equivalentes", dijo Benjamin Recht, un informático de la Universidad de California, Berkeley, que dice que es tan lejos No está claro cuando TDA funciona y cuando no. La técnica se basa en la suposición de que un conjunto de datos de alta dimensión grande tiene una estructura intrínseca de baja dimensión, y que es posible descubrir esa estructura matemáticamente. Recht cree que algunos conjuntos de datos son intrínsecamente altos en dimensión y no pueden ser reducidos por el análisis topológico. "Si resulta que hay una vaca esférica al acecho debajo de todos sus datos, entonces TDA sería el camino a seguir", dijo. "Pero si no está ahí, ¿qué puede hacer?" Y si su conjunto de datos está dañado o incompleto, los métodos topológicos producirán resultados igualmente dañados.

Bloques de Occam

En febrero de 2004, Emmanuel Candes, un matemático de la Universidad de Stanford, y su entonces postdoc, Justin Romberg, estaban jugando con una imagen mal mutilada en su computadora, el tipo utilizado por los científicos para probar los algoritmos de imágenes. Ellos estaban tratando de encontrar un método para mejorar las imágenes difusas, como las generadas por MRIs cuando no hay tiempo suficiente para completar un escáner. En una corazonada, Candes aplicó un algoritmo diseñado para limpiar imágenes difusas, esperando ver una ligera mejora. Lo que apareció en la pantalla de su computadora en cambio fue una imagen perfectamente renderizada. Candes compara la unlikeliness del resultado a ser dado apenas los tres primeros dígitos de un número de cuenta bancaria de 10 dígitos, y adivinar correctamente los siete dígitos restantes. Pero no fue una casualidad. Lo mismo ocurrió cuando aplicó la misma técnica a otras imágenes incompletas.


La idea detrás del análisis de datos topológicos es reducir los conjuntos de datos de alta dimensión a dimensiones más bajas sin sacrificar las propiedades topológicas más relevantes.

La clave del éxito de la técnica es un concepto conocido como escasez, que suele indicar la complejidad de una imagen, o su ausencia. Es una versión matemática de la navaja de Occam: Aunque puede haber millones de reconstrucciones posibles para una imagen difusa, mal definida, la versión más simple (sparsest) es probablemente el mejor ajuste. De este descubrimiento fortuito, nació la sensación comprimida.

Considere el caso de la transmisión de vídeo en línea. Los datos en bruto de un video son enormes: treinta cuadros de dos megapíxeles por segundo, por lo que los vídeos o las imágenes de las cámaras digitales se almacenan mediante algoritmos de compresión. Por lo general, para realizar la compresión, primero hay que recoger todos los bits y almacenarlos, para que uno pueda descartar los que son menos significativos. Con la detección comprimida, uno puede determinar qué bits son significativos sin primero tener que recoger y almacenarlos todos. Esto, dice Recht, "le permite adquirir imágenes médicas más rápido, hacer mejores sistemas de radar, o incluso tomar fotografías con cámaras de un solo píxel".

"Si examino una población de una enfermedad rara, ¿necesito tantos exámenes de sangre como individuos?", Dijo Candes. "La respuesta es no. Puedo hacer esto con menos pruebas. Mi señal es escasa, ya que sólo se espera que unas pocas personas prueben positivo. "Supongamos que hay una persona infectada en un grupo de 32, y la clínica agrupa las 32 muestras de sangre. Si la prueba es negativa, no hay personas infectadas. Pero si es positivo, ¿cómo puede determinar quién está infectado? Según Candes, usted podría tomar la mitad de las muestras (16) y volver a ejecutar la prueba. Si es positiva, la persona infectada está en este grupo; Si es negativo, el culpable está en la otra mitad. Puede continuar reduciendo las posibilidades dividiendo de nuevo al grupo por la mitad y volviendo a ejecutar la prueba. Este enfoque de "medición holística" le dará la respuesta dentro de cinco pruebas, en comparación con probar cada una de las 32 personas una por una. Esta es la esencia de la detección comprimida.

Usando algoritmos de detección comprimidos, es posible muestrear sólo 100.000 de, digamos, 1 millón de píxeles en una imagen, y todavía ser capaz de reconstruir en resolución completa - siempre que los elementos clave de la escasez y el agrupamiento (o "mediciones holísticas") sean presente. Es útil cada vez que uno encuentra un gran conjunto de datos en el que una fracción significativa de los datos falta o está incompleta. En el caso de los registros médicos, un sensor podría no registrar un punto de datos con precisión, o el personal del hospital podría estar demasiado ocupado para registrar todos los registros en el equipo o podrían registrar la información incorrectamente. Del mismo modo, la detección comprimida podría ser útil para combatir la oclusión en los sistemas de reconocimiento facial. Por ejemplo, usar gafas de sol podría ser problemático si los ojos son una variable clave en el análisis.

Este enfoque puede incluso ser útil para aplicaciones que no son, en sentido estricto, problemas de detección comprimidos, como el premio Netflix. En octubre de 2006, Netflix anunció un concurso que ofrece un gran premio de $ 1 millón a quien pueda mejorar el algoritmo de filtrado para su motor de recomendación cinematográfica en casa, Cinematch. Un equipo internacional de estadísticos, expertos en aprendizaje de máquinas e ingenieros informáticos obtuvo el gran premio en 2009, pero la comunidad académica en general también se benefició, ya que obtuvo acceso a Netflix muy grande, el conjunto de datos de alta calidad. Recht fue uno de los que lo manipularon. Su trabajo confirmó la viabilidad de aplicar el enfoque de detección comprimida al desafío de rellenar las calificaciones perdidas en el conjunto de datos.

Cinematch opera utilizando la retroalimentación de los clientes: Se recomienda a los usuarios que califiquen las películas que ven y basándose en esas calificaciones, el motor debe determinar cuánto le gustará a un usuario dado películas similares. El conjunto de datos es enorme, pero es incompleto: en promedio, los usuarios sólo clasifican alrededor de 200 películas, de casi 18.000 títulos. Dada la enorme popularidad de Netflix, incluso una mejora incremental en el algoritmo predictivo da como resultado un impulso sustancial a la línea de fondo de la compañía. Recht encontró que podía predecir con exactitud qué películas los clientes podían estar interesados ​​en comprar, siempre que él viera suficientes productos por persona. Entre 25 y 100 productos fueron suficientes para completar la matriz.

"Hemos demostrado matemáticamente que usted puede hacer esto con mucha precisión bajo ciertas condiciones mediante técnicas computacionales manejables", dijo Candes, y las lecciones aprendidas de esta prueba de principio están alimentando de nuevo a la comunidad de investigación, abordando problemas en física cuántica, Cristalografía de rayos y visión por ordenador, entre otras aplicaciones. En el futuro, los astrónomos que trabajan con telescopios sensibles a la luz infrarroja sólo necesitarán registrar el 20 por ciento de los píxeles que de otro modo necesitarían para obtener las mismas imágenes de alta resolución, porque la detección comprimida puede llenar los huecos.

Recht y Candes pueden defender enfoques como la detección comprimida, mientras que Carlsson y Coifman se alinean más con el enfoque topológico, pero fundamentalmente, estos dos métodos son complementarios y no competitivos. Hay varias otras herramientas matemáticas prometedoras que se están desarrollando para manejar este valiente nuevo mundo de datos grandes y complicados. Vespignani utiliza todo, desde el análisis de redes, creando redes de relaciones entre personas, objetos, documentos, etc., para descubrir la estructura dentro de los datos, el aprendizaje automático y las buenas estadísticas anticuadas.

Coifman afirma la necesidad de una teoría global subyacente a la par con el cálculo para permitir a los investigadores a ser mejores conservadores de grandes datos. De la misma manera, las diversas técnicas y herramientas que se están desarrollando necesitan integrarse bajo el paraguas de un modelo teórico más amplio. "Al final, la ciencia de los datos es más que la suma de sus partes metodológicas", insiste Vespignani, y lo mismo ocurre con sus herramientas analíticas. "Cuando se combinan muchas cosas se crea algo mayor que es nuevo y diferente."