En el estudio titulado “Find a witness or shatter: the landscape of computable PAC learning” fue clave el trabajo de tres postdoctorandos internacionales que colaboraron con el académico Cristóbal Rojas. Los resultados serán presentados en la edición número 36 de COLT, evento que se desarrollará en julio en la ciudad india de Bangalore y en el que también fue aceptada una investigación donde participa el docente Cristóbal Guzmán. Además, otro paper que tiene como coautores a Guzmán y al estudiante de magíster Tomás González formará parte de la conferencia ICML 2023 que se efectuará en Hawai, Estados Unidos.
Cada año, desde 1988, la Asociación para el Aprendizaje Computacional (ACL, por su sigla en inglés) organiza un evento que hoy es considerado como uno de los más importantes del mundo en teoría de machine learning e inteligencia artificial. La Conferencia sobre Teoría del Aprendizaje (COLT) celebrará en julio próximo su versión número 36 en Bangalore, India y, tal como en ocasiones anteriores, considera la presentación de las mejores investigaciones en ese campo. En esta ocasión, esa selección incluirá dos papers elaborados por investigadores del Instituto de Ingeniería Matemática y Computacional (IMC).
Tal como señala la ACL, la teoría del aprendizaje es una disciplina “dedicada al estudio del diseño y análisis de algoritmos de aprendizaje automático. En particular, tales algoritmos apuntan a hacer predicciones o representaciones precisas basadas en observaciones”. Por ese motivo, agrega la entidad, COLT pone énfasis en el “análisis matemático riguroso utilizando técnicas de varios campos relacionados, como probabilidad, estadística, optimización, teoría de la información y geometría”. Además, indica ACL, si bien tiene raíces teóricas la teoría del aprendizaje también se destaca por poner “un fuerte énfasis en la computación eficiente”.
Precisamente, ese es el eje de la investigación titulada “Find a witness or shatter: the landscape of computable PAC learning” y que tiene entre sus autores a Valentino Delle Rose, Alexander Kozachinskiy y Tomasz Steifer -todos posdoctorandos internacionales del IMC- y Cristóbal Rojas, académico del Instituto y doctor en matemáticas y ciencias de la computación. Al menos uno de estos investigadores será el que viaje a India a exponer los detalles del paper, que aborda un marco teórico que se conoce como “Probably approximately correct learning” o “PAC learning”.
Alexander Kozachinskiy, doctor en matemáticas de la U. Estatal de Moscú, Rusia, y quien además es investigador de postdoctorado del Instituto Milenio Fundamentos de los Datos (IMFD) y del Centro Nacional de Inteligencia Artificial (CENIA), explica que PAC learning es un hito en la teoría de aprendizaje. “Entrega, en un marco determinado, una caracterización brillante y limpia de lo que se puede aprender y lo que no se puede aprender. Sin embargo, esto lo logra a costa de ignorar el costo computacional del aprendizaje. La teoría que se ocupa de ese costo se llama ‘teoría de aprendizaje computacional’. Nuestro paper contribuye a ese campo y COLT es el lugar más importante para mostrar resultados como estos”, indica.
Cristóbal Rojas, quien además es investigador de Cenia, agrega que PAC learning es un marco donde se “puede establecer claramente en qué consiste el problema de aprendizaje general, lo que permite estudiarlo desde un punto de vista matemático.. En este marco, el input del problema general consiste en un conjunto de datos y una clase de modelos posibles, y el objetivo es evaluar si esa clase es buena para esos datos. Si lo es, significa que dentro de la clase hay funciones que aproximan bien los datos observados, y que tienen alta probabilidad de aproximar correctamente datos aún no observados. Además, debe existir un algoritmo que mira los datos y encuentra la función que mejor los ‘explica’ en este sentido”.
Cristóbal Rojas (izquierda), junto a Alexander Kozachinskiy, Valentino Delle Rose y Pablo Barceló, director del IMC. Crédito: CENIA
En esta área de investigación, agrega el académico, hay varios elementos claves: “Primero, cuántos datos tiene que mirar el algoritmo, qué tan eficiente es y si tiene acceso a la cantidad de datos necesarios para encontrar la función. Existía una teoría que caracterizaba la relación entre esos parámetros, pero no se preocupaba de la parte en que la operación que mira los datos y encuentra la función que los aproxima tiene que ser un algoritmo; estaba hecha en un marco abstracto en donde esa operación se realizaba con una función cualquiera”. Más recientemente, indica Rojas, se empezó a estudiar qué es lo que pasaba cuando se “exige que esa operación pueda ser calculada por un algoritmo. Ahí el panorama se complicaba un poco y había resultados parciales; no existía una comprensión completa de la relación entre los distintos parámetros. Y en particular había tres preguntas abiertas, que habían aparecido en estudios anteriores presentados en la misma conferencia COLT”.
De acuerdo con el docente IMC, lo que hizo el equipo de investigadores fue “responder esas preguntas y con eso cerrar la teoría respecto de lo que se llama ‘computable PAC learning’ que es la misma teoría de antes, pero tomando en cuenta el hecho de que queremos que se pueda hacer por algoritmos”. Rojas agrega que el trabajo sirve principalmente como una comprensión conceptual de “cómo se relacionan distintos parámetros”. Entonces, si uno quiere estudiar un problema concreto esto opera como guía para las decisiones de modelamiento que hay que tomar. Además, se pone un marco para tener expectativas razonables respecto de lo que uno espera de la aplicación en concreto”.
El aporte de los postdoctorados
Más allá de haber logrado que el paper fuera aceptado en una conferencia del nivel de COLT 2023, Cristóbal Rojas destaca el aporte del equipo de estudiantes de postdoctorado provenientes de Rusia, Italia y Polonia. “Fue un trabajo en el que ellos se afiataron. Entre todos encontramos el tema y las preguntas. Después nos pusimos a trabajar y resultó que era justo un tema en el que nosotros nos sentimos cómodos. Yo más que nada los alenté a seguir adelante y aporté en algunas cosas, además de ayudar en la redacción del borrador final. Pero el trabajo duro lo hicieron ellos”, comenta el académico IMC.
Al respecto, Alexander Kozachinskiy señala que en el grupo que elaboró el paper hay personas con “formación en diferentes áreas, tales como sistemas dinámicos, lógica y complejidad de Kolmogórov. Además, estamos aprendiendo sobre machine learning e inteligencia artificial de una manera no convencional. Es interesante y desafiante y espero que eso influya de manera positiva en la investigación”.
Uno de los objetivos adicionales del estudio es que aporte de manera positiva a las demás organizaciones donde se desempeñan los estudiantes de postdoctorado. Al igual que Alexander, Valentino Delle Rose forma parte del IMFD y CENIA, mientras que Tomasz Steifer es integrante del IMFD. “La expectativa de esos centros es que parte del trabajo que hacen tribute a los objetivos de esas instituciones, los cuales en un principio están fuera de la formación de base que ellos traen. De alguna manera, les estamos pidiendo que se salgan de su zona de confort y que empiecen a estudiar estos problemas. De hecho, tuvimos suerte al encontrar lo que analizamos en el paper, porque está justo entre medio de lo que ellos y yo sabemos bien y esta teoría de aprendizaje o machine learning que es uno de los tópicos de todos estos institutos”, explica Cristóbal Rojas.
Tomasz Steifer. Crédito: IMFD
En ese sentido, añade el académico, la idea es seguir “encontrando puentes y conexiones para irnos metiendo más en este nuevo tema, aprender más y buscar la forma de exportar nuestra experticia a ese campo. Además, mientras más transitemos hacia ese lado, más interesante se va a volver para los estudiantes porque son los temas que están de moda y se encuentran detrás de todas las nuevas tecnologías”.
Uno de los investigadores postdoctorales que participa en el paper aceptado en COLT lleva en el IMC un año, mientras que los demás se incorporaron hace sólo unos meses. Sin embargo, Rojas indica que las expectativas ya son altas en cuanto al trabajo que puedan hacer: “Para mí al menos, hasta ahora su contribución ha sido enorme, pero se ha limitado a la investigación que han hecho conmigo, Pablo Barceló -director del IMC- y algunos otros académicos. Por eso, ahora el plan es empezar a involucrarlos en algunas clases, que dirijan grupos de estudio y que empiecen a juntarse con otros estudiantes para comenzar a construir de a poco un grupo de trabajo que sea más grande y transversal”.
La relevancia de COLT
El hecho de que el estudio elaborado por los estudiantes de postdoctorado y el académico Cristóbal Rojas haya sido aceptado en COLT es un logro relevante, indica Cristóbal Guzmán, docente IMC y doctor en algoritmos, combinatoria y optimización. “Comparada con eventos como, por ejemplo, NeurIPS, COLT es una conferencia más de nicho. Sólo se aceptan unos 100 papers y los participantes no superan los 500, por lo que la calidad de las publicaciones es muy superior. En mi experiencia, es mucho más difícil tener un paper aceptado en COLT que en otras conferencias, ya que hay una exigencia particular en cuanto a la contribución teórica de un trabajo”, comenta el investigador, quien es miembro senior del comité de programa de COLT y, además, forma parte de CENIA.
El trabajo de Guzmán que será presentado en India se titula “Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap” y tiene como coautores a Raef Bassily y Michael Menart, de la U. Estatal de Ohio (EE.UU.). El académico comenta que empezó a estudiar esta temática hace tres años, en plena pandemia: “Llevaba un tiempo trabajando en temas de optimización estocástica con privacidad diferencial. La optimización estocástica es relevante para el área de machine learning, pero empezaron a surgir otros problemas que también son relevantes desde el punto de vista del aprendizaje automático y uno de ellos se refiere a lo que llamamos encontrar puntos silla o resolver juegos de suma cero”.
Cristóbal Guzmán.
En machine learning, explica el académico IMC, esos problemas “tienen que ver con el hecho de que uno puede entrenar un modelo que después va a ser testeado contra un adversario que, por ejemplo, va a tratar de hacer fallar el algoritmo”. Estas nociones de robustez y adversarialidad, señala Guzmán, se pueden modelar parcial o completamente ocupando los llamados problemas de punto de silla que los investigadores en optimización conocen desde hace décadas. “La pregunta que me hice fue ‘¿Podemos resolver esa clase de problemas teniendo esta restricción de privacidad?’ Y resultó ser que la pregunta era mucho más difícil de lo que anticipaba. Me propuse intentar integrar cosas que ya sabemos del ámbito simplemente de optimización y ocupar técnicas de privacidad, para poder lograr que el algoritmo hiciera lo mismo pero con esta restricción de proteger la información privada de los individuos con los que se entrena el modelo”.
Guzmán cuenta que él y sus colega se propusieron revisar la literatura de lo que habían empezado a hacer otros investigadores en privacidad diferencial: “Nos dimos cuenta que había un cierto error particular de técnicas de optimización que sí enganchaban mejor con las técnicas de privacidad y al hacerlo logramos resolver esa pregunta que teníamos, que en el fondo apuntaba a cómo atacar lo que la gente llama el gap de dualidad fuerte para el problema de juego de suma cero”.
Si bien el estudio aborda esta temática de manera general, Guzmán señala que hay instancias donde tiene un gran potencial. Una de ellas es en la generación de datos sintéticos: “Por ejemplo, supongamos que algún estadístico a cargo del censo quiere compartir parte de esa información con otras agencias o tomadores de decisiones. Obviamente, surge la preocupación de que al liberar una cierta tabla, y aunque se elimine el RUT de las personas, se pueda reconstruir de alguna manera la información de las personas. De hecho, estos ataques son factibles de hacer, y no son difíciles de realizar en términos computacionales. Un compromiso que se podría adquirir es compartir un set de datos pero que no corresponde a los individuos reales sino que fabricados, pero garantizando que los resultados estadísticos que se van a obtener con esa muestra ficticia van a ser similares a los que se tendrían con la muestra real. Ese problema de generar datos ficticios para cierto conjunto estadístico o de consultas se puede modelar precisamente como un juego suma cero”.
Además de este paper, el académico IMC participa en otro trabajo que se presentará en la Conferencia Internacional de Machine Learning 2023 (ICML), que se efectuará en julio en Hawai, Estados Unidos. El paper se titula “Faster Rates of Convergence to Stationary Points in Differentially Private Optimization” y tiene como uno de sus coautores a Tomás González, ingeniero civil matemático y computacional y estudiante del Magíster en Ciencias de la Ingeniería bajo la supervisión de Guzmán.
“Este es un problema, que llevaba varios años estancado, pero que se acerca un poco más a como uno quisiera aplicar en la práctica un modelo de machine learning. Yo trabajo en optimización convexa, pero lo que la gente reclama en machine learning es que los problemas reales que uno quiere resolver, tales como entrenar redes neuronales, corresponden a funciones que son no convexas”, indica el investigador.
Tomás González.
El académico precisa que el estudio no busca resolver redes neuronales propiamente tales, pero sí señala que cuando se libera el “supuesto de convexidad se está quizá un paso más cerca de tomar modelos que sean los que en el fondo la gente sí le pueden interesar. Y en ese contexto fue precisamente lo que hicimos”. Guzmán señala que hasta este estudio él había trabajado en numerosos proyectos de optimización convexa con privacidad diferencial, pero en este caso se dedicó a revisar la literatura no convexa, donde lo que uno busca son puntos críticos. No necesariamente voy a estar minimizando la función, ya que podría estar en un punto que tiene direcciones de crecimiento y decrecimiento, lo que se conoce como un punto silla. Pero lo que quiero es buscar un punto estacionario, donde la función localmente no varía mucho”.
A medida que Tomás González avanzó en su proyecto de tesis de Magíster descubrió que había varios papers sobre el tema que tenían errores, por lo que hubo que revisar bien la teoría. “Nos dimos cuenta, por una parte, que este problema no se entendía muy bien. Entonces nos abocamos a tratar de revisitarlo y encontramos varias cosas. Una de ellas fue respecto de los resultados existentes, donde mejoramos las tasas existentes y las aceleramos. Después había otro resultado de un paper del 2020, el cual desafortunadamente después de corregir un gap en su análisis descubrimos que era mucho más débil de lo que inicialmente anunciaban” comenta Guzmán.
El académico IMC añade que al atacar el problema pudieron “obtener una tasa que es bastante buena, aunque todavía no sabemos si es óptima. En términos de las técnicas que usamos, no hay nada muy revolucionario. Sin embargo, se trata de una combinación correcta de técnicas que permiten hacer algo que antes no se podía hacer”. En ese sentido, los resultados del paper son satisfactorios porque “no solo proveen mejoras sustantivas sobre el estado del arte, si no que también lo hacemos con técnicas mucho más simples que las existentes”.