Equipo Docente

• Profesor: Cristóbal Guzmán
• Ayudantes: Germán Cheuque y Patricio Ulloa

Objetivos del Curso

• Familiarizarse con la noción de aprendizaje estadístico
• Analizar algoritmos de aprendizaje en el contexto PAC (probablemente, aproximadamente correcto)
• Estudiar modelos y aplicaciones de la teoría de aprendizaje
• Implementar algoritmos de aprendizaje de forma rigurosa, teniendo en cuenta las distintas etapas de aprendizaje (entrenamiento, validación y testeo) y las técnicas para prevenir sobreajuste

Información Práctica

• Reglamento del curso
• Lista de escritores de apuntes
• Instrucciones para la redacción de apuntes
• Archivos de escritura de apuntes: Archivo TeX, Comandos, Bibliografía
• Fechas Interrogaciones: Jueves 12 de Septiembre, Viernes 15 de Noviembre

Evaluaciones

• Redacción de apuntes: cada clase un alumno tomará notas en LaTex (10%)
• 5 Tareas (30%)
• 2 Interrogaciones (30%)
• Proyecto final (30%): Los alumnos deberán trabajar por un periodo de un mes, en grupos de 2-3, investigando un problema reciente en teoría aprendizaje. Incluirá una lectura bibliográfica de temas avanzados, y el desarrollo de una solución original a un problema propuesto

Proyectos

Este curso no contará con un Examen como evaluación final. En cambio, los alumnos deberán estudiar, investigar y proponer soluciones a problemas de investigación actuales en teoría de aprendizaje. Se estima que el trabajo que deberán realizar los alumnos durará por al menos 1 mes, donde deberán reunirse regularmente con sus ayudantes y el profesor, para revisar sus avances.

Link para escoger proyectos aquí

Algunos de los proyectos que podrán desarrollar los alumnos son:

• Aprendizaje robusto a ejemplos adversariales: Recientemente se ha observado que en la práctica muchos algoritmos de aprendizaje pueden fallar catastroficamente ante la presencia de "ejemplos adversariales"; esto es, ejemplos con atributos o etiquetas modificados con el propósito de aumentar la el error de clasificación. La idea es investigar explicaciones rigurosas de este fenómeno, así como posibles mejoras algorítmicas para evitar estos ataques. Referencias: Adversarially robust generalization requires more data, adversarial examples from computational constraints, Rademacher complexity of adversarially robust generalization y VC classes are adversarially robustly learnable, but only improperly.
• Estadística Robusta: En el contexto de estadística clásica, tales como estimación, clasificación y regresión, una pregunta importante es cómo diseñar estadísticos que sean robustos a una corrupción arbitraria de una fracción pequeña de sus datos. La respuesta a esta incógnita fue resuelta en los 70's y 80's, por gente como Tukey, Donoho y Huber. Lamentablemente, todos los estadísticos resultantes de esta teoría involucran problemas NP-completos, por lo que quedaba la pregunta abierta de cómo hacer estadística robusta eficientemente. Esta pregunta ha sido resuelta recientemente, con variadas técnicas algorítmicas. El objetivo de este proyecto es resumir el estado del arte, presentar garantías teóricas de estadística robusta a problemas específicos, y aplicar estas técnicas a algún problema de interés. Agnostic Estimation of Mean and Covariance, Efficient Algorithms and Lower Bounds for Robust Linear Regression, Mean Estimation and Regression under Heavy-Tails, a survey.
• Clasificación Estratégica: Durante el curso asumimos que los modelos observados siguen una distribución i.i.d.; sin embargo, los sujetos de estudio (tipicamente humanos) pueden reaccionar de manera estratégica a las decisiones tomadas por un algoritmo de aprendizaje. Recientemente se han propuesto modelos de teoría de juegos para entender este efecto, pero esto es un área lejos de estar comprendida. Referencias: Strategic Classification, Strategic Classification from Revealed Preferences, Strategyproof Linear Regression in High Dimensions, How do Classifiers Induce Agents to Invest Effort Strategically.
• Juegos de Información Incompleta y Aplicaciones a Poker: Uno de los éxitos recientes del aprendizaje automático ha sido el de superar a humanos en juegos. En este proyecto en particular, nos enfocaremos en juegos secuenciales de información incompleta, y como ejemplo emblemático algoritmos para jugar poker. The State of the Art of Solving Large Incomplete Information Games, and Applications to Poker, Faster Algorithms for Extensive Form Game Solving via Improved Smoothing Functions, Superhuman AI for Multiplayer Poker.
• No-Discriminación en Aprendizaje: Con la masificación de métodos de aprendizaje automático en la sociedad, surge la preocupación por exacerbar sesgos y decisiones discriminatorias, ya sea por subrepresentación de grupos en los datos, sesgos humanos, o la tendencia a discriminación por un algoritmo en función de minimizar el riesgo. Este desafío ha llevado a estudiar las fuentes de discriminación algorítmica y como mitigar sus efectos. Equality of Opportunity in Supervised Learning, On Preserving Non-Discrimination when Combining Expert Advice, Fair Algorithms for Infinite and Contextual Bandits, Fairness Without Demographics in Repeated Loss Minimization.
• Fundamentos Matemáticos de Aprendizaje Profundo: Las redes neuronales han mostrado avances significativos en problemas tales como clasificación de imágenes y procesamiento de lenguaje natural; sin embargo, la teoría detrás de este éxito es aun limitada. Referencias: Gradient descent for one hidden layer neural networks: polynomial convergence and SQ lower bounds, Stronger generalization bounds for deep nets via compression, A convergence theory for deep learning via over-parameterization, The Implicit Bias of Depth: How Incremental Learning Drives Generalization.
• Aprendizaje con memoria limitada: Para algunos problemas de aprendizaje, como por ejemplo funciones de paridad, sólo se conocen algoritmos de aprendizaje que utilizan una cantidad cuadrática de memoria (en el caso de paridades, esto se debe a que el algoritmo debe resolver un sistema lineal). Sólo recientemente se ha logrado demostrar que esta cantidad de memoria es necesaria. Fast learning requires good memory: a time-space lower bound for parity learning, A time-space lower bound for a large class of learning problems, Mixing implies lower bounds for space bounded learning, Memory-sample tradeoffs for linear regression with small error y Space lower bounds for linear prediction in the streaming model.
• Bandidos: Muchas veces en la práctica, la información que podemos recolectar de un modelo es sumamente limitada. Cuando además debemos tomar decisiones 'en el vuelo,' esto puede ser modelado a través de los llamados modelos de bandidos. Esta es un área madura y desarrollada, por lo que el objetivo de este proyecto es diseñar una introducción al análisis de algoritmos en-línea con retroalimentación parcial (también llamados bandidos), e implementar algunos de estos algoritmos en problemas complejos de interés práctico. Referencias: Bandit Algorithms, Regret Analysis of Stochastic and Nonstochastic Multiarmed Bandit Problems.
• Transporte Óptimo: El problema de transporte óptimo se remonta al sigo XVIII, y consiste en el problema de convertir una distribución de probabilidad en otra, incurriendo en el mínimo costo de transportar su masa. Este problema ha sido estudiado en varios contextos, y recientemente se han encontrado aplicaciones en procesamiento de imágenes, aprendizaje automático y optimización bajo incertidumbre. Esta es un área madura y desarrollada, por lo que el objetivo de este proyecto es diseñar una introducción al problema de transporte óptimo y sus aplicaciones, y desarrollar métodos computacionales para resolver este problema. Referencias: Computational Optimal Transport, Statistical Aspects of Wasserstein Distances, Optimal Transport: Old and New.
• Concentración Matricial: Una aplicación importante de concentración de la medida es el caso de concentración del espectro de matrices. Este problema está relacionado con un número de aplicaciones y algoritmos aleatorizados para el análisis de datos y grafos (muchas veces llamadas técnicas de 'sketching'). La idea de este proyecto es presentar una introducción a la teoría de concentración matricial, así como aplicaciones y conexiones con otras áreas. Referencias: An Introduction to Matrix Concentration Inequalities, Matrix Concentration and Computational Linear Algebra, Sketching as a Tool for Numerical Linear Algebra, Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities.

Nota: Las referencias escogidas no representan todo el trabajo existente en el área. Se recomienda a los alumnos investigar más referencias sobre cada tema.