Aplicaciones de la dimensión efectiva a la complejidad comp(...).pdf

Aplicaciones de la dimensión efectiva a la complejidad computacional y a los algoritmos de comprensión de datos

López Valdés, María
Mayordomo Cámara, Elvira (dir.)

Universidad de Zaragoza, 2011

Resumen: Durante las últimas décadas, la tecnología de las computadoras y el uso que de ellas se hace ha progresado de forma increíble. Dentro de este ritmo de desarrollo, importantes aplicaciones en informática quedan obsoletas gracias a los nuevos recursos o a la aparición de soluciones más ingeniosas. Ahora bien, si además de generar resultados fuéramos capaces de entender el fundamento de estos resultados, el desarrollo podría ser mucho más estructurado y beneficioso. Este es el principal interés de la informática teórica: el sentar las bases formales de la informática para facilitar así un avance de conocimiento, proporcionar una visión global de los problemas y una intuición sobre futuras soluciones que puedan ser más adecuadas. Dentro de la informática teórica existen numerosas áreas de estudio como por ejemplo: - La teoría de la computabilidad: estudia si un problema puede resolverse con un procedimiento automático. - La teoría de la complejidad computacional: estudia si un problema se puede resolver de un modo eficiente. - La teoría de aprendizaje computacional: estudia la dificultad de que una máquina sea capaz de aprender a encontrar las soluciones de un determinado problema. - La teoría de la información: estudia la complejidad intrínseca de las secuencias (por ejemplo, de las soluciones de un determinado problema) así como lo que se pueden comprimir. En la búsqueda de nuevos conocimientos en cada una de estas áreas se han desarrollado numerosas herramientas formales. Por ejemplo, Lutz introdujo en el año 2000 la dimensión efectiva orientada inicialmente a obtener resultados en el área de la complejidad computacional. Ahora bien, entre las diversas áreas existen fuertes conexiones y por lo tanto, parece lógico que también existan conexiones entre las distintas herramientas formales que se utilizan. Encontrar estas conexiones permite trasladar resultados de unas áreas a otras y obtener un conocimiento mucho más profundo de los diversos problemas que pueden ser resueltos con un computador actual o incluso con un computador que pueda ser desarrollado en un futuro. En esta tesis se han estudiado las relaciones existentes entre la dimensión efectiva y la complejidad de Kolmogorov, los ratios de compresión o el rendimiento en algoritmos de aprendizaje. Esto ha permitido trasladar resultados de complejidad computacional a aprendizaje computacional o teoría de la información y viceversa, estableciendo nuevas cotas superiores e inferiores de complejidad para problemas y clases de problemas cuya dimensión se conoce, así como nuevos resultados sobre el tamaño de clases en función de su complejidad. Más concretamente: - Dimensión y complejidad de Kolmogorov: Ryabko, Staiger, Cai y Hartmanis fueron los primeros en estudiar la relación entre dimensión clásica de Hausdorff y complejidad de Kolmogorov. Con el desarrollo de la versión constructiva de la dimensión de Hausdorff, Mayordomo y Lutz demostraron que se conseguía una caracterización completa. En cuanto a los casos de dimensión calculable y dimensión en espacio polinómico, Hitchcock demostró que también es posible una caracterización completa. En este caso es necesario utilizar la versión de complejidad de Kolmogorov con recursos de espacio acotados. En esta tesis se generalizan todos estos resultados para la dimensión con escala (un refinamiento de la dimensión efectiva). Para demostrar estos resultados se ha desarrollado la dimensión con escala para secuencias finitas, de interés independiente. Intuitivamente, estos resultados presentan una estrecha relación entre el tamaño de una clase de problemas y la compresibilidad máxima alcanzable para cada uno de estos problemas, aún en el caso de una medida de tamaño muy ajustada al tipo concreto de problemas (dimensión con escala). Además, estos resultados se utilizan para estudiar el comportamiento de las reducciones P/poly-Turing en la clase ESPACE. - Dimensión y compresión: La relación entre dimensión en tiempo polinómico y complejidad de Kolmogorov no parece ser clara, por ese motivo, en esta tesis se utiliza la noción usual de algoritmo de compresión para secuencias finitas para caracterizar la dimensión en tiempo polinómico. Gracias a esta nueva caracterización, varios resultados conocidos para dimensión en tiempo polinómico se pueden interpretar como resultados de compresión. Por ejemplo, los lenguajes de una clase de p-dimensión 1 no pueden comprimirse (i.o.) en más que una cantidad sublineal. Así se obtienen resultados sobre la compresibilidad de lenguajes completos y autoreducibles, dos de los tipos de problemas de más interés en complejidad computacional. - Dimensión y aprendizaje: En esta tesis se estudian la relación de la dimensión con distintos modelos de aprendizaje. En relación con el aprendizaje on-line se obtiene una cota superior de la dimensión en tiempo polinómico de clases de conceptos que pueden aprenderse con algoritmos on-line en tiempo exponencial y con \alpha 2^n errores. Además se demuestra que esta cota superior es óptima. En relación con el aprendizaje PAC, se demuestra que la dimensión en espacio polinómico de clases de conceptos que son PAC-aprendibles es cero. Igualmente se demuestra que es cero para clases de conceptos que pueden aprenderse con un algoritmo basado en preguntas. Estos resultados han permitido obtener hipótesis que implican el no aprendizaje o la complejidad de las representaciones necesarias para aprender un concepto.