el informático de Harvard descubrió que el lema de Johnson-Lindenstrauss, un teorema de 30 años, es el mejor enfoque para preprocesar grandes datos en una dimensión manejablemente baja para el procesamiento algorítmico.
Cuando pensamos en la información digital, a menudo pensamos en el tamaño. Un boletín diario por correo electrónico, por ejemplo, puede tener un tamaño de 75 a 100 kilobytes. Pero los datos también tienen dimensiones, basadas en el número de variables en un dato.Un correo electrónico, por ejemplo, se puede ver como un vector de alta dimensión donde hay una coordenada para cada palabra en el diccionario y el valor en esa coordenada es el número de veces que se usa esa palabra en el correo electrónico. Entonces, un correo electrónico de 75 Kbes decir, 1,000 palabras de largo resultarían en un vector en millones.
Esta vista geométrica de los datos es útil en algunas aplicaciones, como el aprendizaje de clasificadores de correo no deseado, pero, cuantas más dimensiones, más tiempo puede llevar ejecutar un algoritmo y más memoria utiliza el algoritmo.
A medida que el procesamiento de datos se volvió más y más complejo a mediados y fines de la década de 1990, los informáticos recurrieron a las matemáticas puras para ayudar a acelerar el procesamiento algorítmico de datos. En particular, los investigadores encontraron una solución en un teorema probado en la década de 1980 pormatemática William B. Johnson y Joram Lindenstrauss trabajando en el área de análisis funcional.
Conocido como el lema Johnson-Lindenstrauss lema JL, los científicos informáticos han utilizado el teorema para reducir la dimensionalidad de los datos y ayudar a acelerar todo tipo de algoritmos en muchos campos diferentes, desde algoritmos de transmisión y búsqueda, hasta algoritmos de aproximación rápida paraálgebra estadística y lineal e incluso algoritmos para biología computacional.
Pero a medida que los datos se han hecho aún más grandes y complejos, muchos científicos informáticos han preguntado: ¿es el lema JL realmente el mejor enfoque para preprocesar grandes datos en una dimensión manejablemente baja para el procesamiento algorítmico?
Ahora, Jelani Nelson, el profesor asociado de ingeniería y ciencias aplicadas John L. Loeb de la Facultad de ingeniería y ciencias aplicadas John A. Paulson de Harvard, ha suspendido ese debate. En un documento presentado esta semana en el IEEE anualSimposio sobre fundamentos de la informática en Berkeley, California, Nelson y el coautor Kasper Green Larsen, de la Universidad de Aarhus en Dinamarca, descubrieron que el lema JL realmente es la mejor manera de reducir la dimensionalidad de los datos.
"Hemos demostrado que hay conjuntos de datos 'duros' para los cuales la reducción de la dimensionalidad más allá de lo que proporciona el lema JL es imposible", dijo Nelson.
Esencialmente, el lema JL mostró que para cualquier colección finita de puntos en alta dimensión, hay una colección de puntos en una dimensión mucho más baja que preserva todas las distancias entre los puntos, hasta una pequeña cantidad de distorsión. Años después de su originalimpacto en el análisis funcional, los informáticos descubrieron que el lema JL puede actuar como un paso de preprocesamiento, permitiendo que las dimensiones de los datos se reduzcan significativamente antes de ejecutar algoritmos.
En lugar de pasar por todas y cada una de las dimensiones, como los cientos de dimensiones en un correo electrónico, el lema JL utiliza un sistema de clasificación geométrica para acelerar las cosas. En esta geometría, las dimensiones individuales no importan tanto comolas similitudes entre ellos. Al mapear estas similitudes, la geometría de los datos y los ángulos entre los puntos de datos se conservan, solo que en menos dimensiones.
Por supuesto, el lema JL tiene una amplia gama de aplicaciones que van mucho más allá de los filtros de correo no deseado. Se utiliza en la detección comprimida para reconstruir señales dispersas usando pocas mediciones lineales; agrupando datos de alta dimensión; y la búsqueda de motivos de ADN en biología computacional.
"Todavía tenemos un largo camino por recorrer para comprender la mejor reducción de dimensión posible para conjuntos de datos específicos en lugar de comparar con el peor de los casos", dijo Nelson. "Creo que es una dirección muy interesante para el trabajo futuro. También hayAlgunas preguntas abiertas interesantes relacionadas con la rapidez con que podemos realizar la reducción de dimensionalidad, especialmente cuando nos enfrentamos a vectores de alta dimensión que son escasos, es decir, tienen muchas coordenadas iguales a cero. Este caso escaso es muy relevante en muchas aplicaciones prácticas. Por ejemplo, los vectoreslos correos electrónicos son extremadamente escasos, ya que un correo electrónico típico no contiene todas las palabras del diccionario ".
"El Lema de Johnson-Lindenstrauss es un resultado fundamental en la geometría de alta dimensión, pero se mantuvo una brecha logarítmica molesta entre los límites superior e inferior para la dimensión mínima posible requerida en función del número de puntos y la distorsión permitida", dijo NogaAlon, profesor de Matemáticas en la Universidad de Tel Aviv, que había demostrado el mejor límite inferior anterior para el problema ". El trabajo reciente de Jelani Nelson y Kasper Green Larsen resolvió el problema. Es una demostración refrescante del poder de una combinación inteligente derazonamiento combinatorio con herramientas geométricas en la solución de un problema clásico "
Fuente de la historia :
Materiales proporcionado por Harvard John A. Paulson School of Engineering and Applied Sciences . Nota: El contenido puede ser editado por estilo y longitud.
Cite esta página :