IMT 3114: Fundamentos Matemáticos de Ciencia de Datos
Esta es la página oficial del curso IMT3114, segundo semestre de 2017, ofrecido por la Escuela de Ingeniería de la Pontificia Universidad Católica de Chile
Equipo Docente
Equipo Docente
- Profesor: Cristóbal Guzmán
- Ayudante: Max Levill
Horario
Horario
- Cátedras: Lunes y Viernes, 14:00-15:20
- Ayudantías: Miércoles, 14:00-15:20
- Trabajo Personal: 4 horas semanales
Objetivos del Curso
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
Contenidos
Contenidos
- Desigualdades de Concentración: 4 clases
- Aprendizaje PAC (probablemente, aproximadamente correcto): 3 clases
- Complejidad de Rademacher y Dimensión VC (Vapnik-Chervonenkis): 3 clases
- SVM (Support Vector Machines): 3 clases
- Kernels: 3 clases
- Boosting: 3 clases
- Aprendizaje convexo: 4 clases
- Aprendizaje en línea: 3 clases
- Reducción de dimensionalidad: 3 clases
Evaluaciones
Evaluaciones
- Tareas por cada capítulo
- Una tarea computacional
- Un proyecto final
Tareas
Tareas
- Hacer 2 ejercicios de su elección de la guía de desigualdades de concentración (NO los resueltos en ayudantía; a lo más uno entre el problema 9 y el 10). Entrega: Viernes 18 de Agosto en la clase
Proyectos
Proyectos
La evaluación final del curso es un proyecto, el cual pueden escoger entre los siguientes tópicos
- Deep Learning: El objetivo de este proyecto es presentar una introducción al aprendizaje de redes neuronales, y las técnicas de optimización que se usan actualmente para aprendizaje profundo (especialmente backpropagation y su interpretación como un método de gradiente estocástico). Finalmente, los alumnos deberán investigar situaciones que permiten un aprendizaje eficiente de redes profundas vía gradiente estocástico y/o situaciones donde este algoritmo falla. Referencias:
- Shalev-Shwartz: Slides de Deep Learning
- Zhang, Bengio, Hardt, Recht & Vinyals (ICLR'17): Understanding Deep Learning Requires Rethinking Generalization
- Shalev-Shwartz, Shamir & Shamma (ICML'17): Failures of Gradient-Based Deep Learning
- No-Discriminación en Aprendizaje: Se busca investigar nociones de justicia o no-discriminación en el contexto de aprendizaje supervisado, y aplicar dichas nociones a datos reales o ficticios. Los alumnos deberán ofrecer recomendaciones sobre la aplicabilidad de estas técnicas y sus alcances, con una mirada crítica. Referencias:
- Dwork, Hardt, Pitassi, Reingold & Zemel (ITCS'12): Fairness Through Awareness
- Hardt, Price & Srebro (NIPS'16): Equality of Opportunity in Supervised Learning
- Woodworth, Gunasekar, Ohannessian & Srebro (COLT'17): Learning Non-Discriminatory Predictors
- Kleinberg, Mullainathan & Raghavan (ITCS'17): Inherent Tradeoffs in the Fair Determination of Risk Scores
- Lectura Recomendada: Machine Bias: Risk Assesments in Criminal Sentencing (incluye link a datos reales usados en el estudio)
- Aprendizaje Robusto: Recientemente se han logrado avances significativos en desarrollar algoritmos eficientes de aprendizaje que son robustos ante la presencia de outliers, esto incluye problemas fundamentales como estimación de parámetros de distribuciones Gaussianas. El objetivo es investigar los desarrollos recientes en algoritmos de aprendizaje que son robustos a la presencia de outliers, e implementar estos métodos con datos reales o ficticios para aplicaciones de interés. Referencias:
- Lai, Rao & Vempala (FOCS'16): Agnostic Estimation of Mean and Covariance
- Diakonikolas, Kamath, Kane, Li, Moitra & Stewart: Robust Estimators in High Dimensions, without the Computational Intractability (FOCS'16), Being Robust (in High Dimensions) Can Be Practical (ICML'17)
- Steinhardt, Charikar & Valiant: Resilience: Learning from Untrusted Data (STOC'17)
- Reducción de Dimensionalidad: El objetivo es investigar algoritmos rápidos y determinísticos que exploten la geometría de los datos para mejorar la reducción de dimensionalidad. También se podrán investigar conexiones con otros problemas, como locality-sensitive hashing, clustering, compressed sensing, etc. Referencias:
- Nelson: Lecture Notes on Dimensionality Reduction (MADALGO'15)
- Dadush, Guzmán & Olver: Fast, Deterministic and Sparse Dimensionality Reduction
- Dasgupta: Learning Mixtures of Gaussians
- Charikar: Apuntes de Locality-Sensitive Hashing
- Privacidad Diferencial: Introducir las herramientas básicas de privacidad diferencial, y aplicarlas con datos reales o ficticios en aplicaciones de interés. El proyecto también podría incluir el estudio de análisis adaptativo de datos, como una herramienta para reutilizar el conjunto de testeo en problemas de aprendizaje.
- Dwork & Roth: The Algorithmic Foundations of Differential Privacy (lecture notes)
- Steinke: Apuntes de Adaptive Data Analysis
- Dwork, Feldman, Hardt, Pitassi, Reingold & Roth: The reusable holdout: Preserving validity in adaptive data analysis (Science'16), parts 1 and 2. Guilt Free Data Reuse (Comm. ACM'17)
Información de Interés
Información de Interés
Referencias
Referencias
Este curso se basa principalmente en los siguientes libros:
- Mohri, Rostamizadeh & Talwalkar: Foundations of Machine Learning
- Ben-David & Shalev-Shwartz: Understanding Machine Learning
Una lectura interesante en relación a los objetivos del curso
Otros cursos de teoría de aprendizaje y ciencia de datos
Otros cursos de teoría de aprendizaje y ciencia de datos
- Shai-Shalev Shwartz (Hebrew University, Jerusalem): http://www.cs.huji.ac.il/~shais/IML2014.html y https://www.cs.huji.ac.il/~shais/Advanced2011/AdvancedML.html
- Nina Balcan & Avrim Blum (CMU): http://www.cs.cmu.edu/%7Eninamf/courses/806/10-806-index.html
- Santosh Vempala (Georgia Tech): https://cs7545.wordpress.com/
- Philippe Rigollet (MIT): https://ocw.mit.edu/courses/mathematics/18-657-mathematics-of-machine-learning-fall-2015/
- Afonso Bandeira (NYU): http://www.cims.nyu.edu/~bandeira/Fall2015.18.S096.html
- Elad Hazan (Princeton): http://www.cs.princeton.edu/courses/archive/spring17/cos598E/
- Elad Hazan & Sanjeev Arora: http://www.cs.princeton.edu/courses/archive/fall16/cos402/
Principales conferencias del Área
Principales conferencias del Área