Advanced Introduction to Machine Learning

10-715, Fall 2018

Carnegie Mellon University

Maria-Florina Balcan

Recitations

Previous material

Course Project Guidelines

One of the course requirements is to do a project in a group of 3 or 4. Your class project is an opportunity for you to explore an interesting machine learning problem of your choice, whether empirically or theoretically. This can take one of the following forms. Conduct an experiment (pick some datasets, and apply an existing or new machine learning algorithm) Work on a theoretical question in machine learning Read a couple of machine learning papers and present the main ideas (these should be outside the topics covered in class, and the papers should be at an advanced level) If you are having trouble coming up with an idea, feel free to consult with a TA or the instructor. We provide several ideas below. Your project will consist of 25% of your final grade, and will have three deliverables: Proposal, Oct 10: 2-3 paragraphs (10%) Midway Report, Nov 5: 4 pages (20%) In-class Presentation, Nov 26 & 28: around 8 minutes, exact time TBD (20%) Final Report, Dec 12: 8 pages (50%) Each group should submit one proposal and final report. Your project will be evaluated based on a few criteria: If the project is experimental, it will be graded on the extensiveness of the study and experiments. Projects which have well-designed experiments and a thorough analysis of the results are scored higher. If the project is theoretical, it will be graded on the formulation of the questions and the quality of proofs. If the project is to look at a few papers, it will be graded on the clarity of the ideas, whether the report demonstrates a deep understanding of the papers, and whether the project displays an ability to synthesize the ideas from the related papers. See good examples of survey papers: (Representation Learning: A Review and New Perspectives, Multimodal Machine Learning: A Survey and Taxonomy) Projects that cleanly expresses the main ideas and concepts of the papers are scored higher. The writing style and the clarity of the written paper.

Project Proposal (Due Date: Oct 10) A list of suggested papers, projects, and data sets are posted below. Page limit: Proposals should be 2-3 paragraphs (excluding references), in NIPS format. Include the following information: Project title and teammates Project idea. This should be approximately two paragraphs. If it is an experimental project, list the potential datasets and the experiments you plan to run. If your project is to read a few papers, list the papers. Project goals: what do you expect to complete before the project presentations?
Midway Report (Due Date: Nov 5) This should be a 4 page (excluding references) report on your project, in NIPS format. Include the finalized project idea, background or related work, the main ideas behind the project, as well as any theoretical and/or empirical results and conclusions derived so far.
Presentation (Nov 26 & 28) You should prepare slides for a 8 minute presentation of your project, with 2 minutes for questions (exact time TBD). Your slides should contain a full summary of your project. Each group member should present part of the slides.
Final Report (Due Date: Dec 12) This should be a 8 page (excluding references) report on your project, in NIPS format. Include the project idea, any background or related work, the main ideas behind the project, results (if applicable), and conclusions. The final report should be of high quality. Since most of you are graduate students, we hope that many of these projects go on to become publications at top conferences like ICML, NIPS, COLT, ACL, EMNLP, CVPR, ICCV, AAAI etc.

Privacy K. Chaudhuri, C. Monteleoni, A. D. Sarwate. Differentially Private Empirical Risk Minimization. 2011. B. I. P. Rubinstein, P. L. Bartlett, L. Huang, N. Taft. Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning. 2012. C. Dwork. Differential Privacy: A Survey of Results. 2008. K. Chaudhuri, A. Sarwate. NIPS Tutorial on Differentially Private Machine Learning. NIPS 2017. Semi-Supervised Learning X. Zhu. Semi-Supervised Learning A. Carlson, J. Betteridge, R. Wang, E. Hruschka Jr., T. Mitchell. Coupled Semi-Supervised Learning for Information Extraction X. Zhu, Z. Ghahramani, J. Lafferty. Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions M.F. Balcan, and A. Blum. A Discriminative Model for Semi-Supervised Learning. Journal of the ACM 2010. Distributed Machine Learning M. Balcan, A. Blum, S. Fine, and Y. Mansour. Distributed Learning, Communication Complexity and Privacy M. Li et al. Scaling Distributed Machine Learning with the Parameter Server Y. Arjevani and O. Shamir. Communication Complexity of Distributed Convex Learning and Optimization. NIPS 2015. Y. Zhang, M. Wainwright and M. Jordan. Distributed Estimation of Generalized Matrix Rank: Efficient Algorithms and Lower Bounds. ICML 2015. O. Shamir, N. Srebro and T. Zhang. Communication Efficient Distributed Optimization using an Approximate Newton-type Method. ICML 2014. J.C. Duchi, M. Wainwright, and Y. Zhang. Communication-Efficient Algorithms for Statistical Optimization . JMLR 2013. M.F. Balcan, S. Ehrlich, and Y. Liang. Distributed Clustering on Graphs. NIPS 2013. M.F. Balcan, A. Blum, S. Fine, and Y. Mansour. Distributed Learning, Communication Complexity and Privacy. COLT 2012. Boosting R. Schapire. Explaining AdaBoost. 2015. A. Beygelzimer et al. Optimal and Adaptive Algorithms for Online Boosting. 2015. A. Beygelzimer, S. Kale and H. Luo. Optimal and Adaptive Algorithms for Online Boosting. ICML 2015. I. Mukherjee and R. E. Schapire. A theory of multiclass boosting. Journal of Machine Learning Research 2013 P. M. Long and R. A. Servedio. Random classification noise defeats all convex potential boosters. Machine Learning, 2010 V. Feldman. Distribution-Specific Agnostic Boosting. Innovations in Computer Science 2010. A. Tauman Kalai and R. Servedio. Boosting in the Presence of Noise . JCSS 2005. S. Dasgupta and P. M. Long. Boosting with diverse base classifiers. COLT 2003. Interactive Learning S. Dasgupta. Two Faces of Active Learning. 2015. M. Balcan, R. Urner Active Learning - Modern Learning Theory. 2015. A. Krishnamurthy, A. Ramdas, M. Balcan, A. Singh ICML 2015 Workshop on Advances in Active Learning - Bridging Theory and Practice. ICML 2015. M. Balcan, A. Blum. Clustering with Interactive Feedback P. Awasthi, R. Zadeh. Supervised Clustering K. Chaudhuri, S. Kakade, P. Netrapalli and S. Sanghavi. Convergence Rates of Active Learning for Maximum Likelihood Estimation. NIPS 2015. G. Dasarathy, R. Nowak and X. Zhu. S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification. COLT 2015. T.-K. Huang, A. Agarwal, D. Hsu, J. Langford, and R. Schapire, Efficient and Parsimonious Agnostic Active Learning. NIPS 2015. S. Hanneke. Theory of Disagreement-Based Active Learning. Foundations and Trends in Machine Learning, Vol. 7 (2-3), pp. 131-309. M.F. Balcan and P. Long. Active and Passive Learning of Linear Separators under Log-concave Distributions. COLT 2013. M.F. Balcan and S. Hanneke. Robust Interactive Learning. COLT 2012. M.F. Balcan, A. Beygelzimer, J. Langford. Agnostic active learning. JCSS 2009 (originally in ICML 2006). A. Beygelzimer, S. Dasgupta, and J. Langford. Importance-weighted active learning. ICML 2009. V. Koltchinskii Rademacher Complexities and Bounding the Excess Risk in Active Learning. Journal of Machine Learning Research 2010. S. Hanneke Rates of Convergence in Active Learning. The Annals of Statistics 2011. See also the ICML 2015 Workshop on Advances in Active Learning - Bridging Theory and Practice. Online Learning A. Blum. Online Algorithms in Machine Learning A. Blum, Y. Mansour. Learning, Regret Minimization, and Equilibria O. Dekel, J. Ding, T. Koren, Y. Peres: Bandits with switching costs: T^(2/3) regret. STOC 2014. U. Feige, T. Koren, M. Tennenholtz: Chasing Ghosts: Competing with Stateful Policies. FOCS 2014. Y. Mansour, A. Slivkins, V. Syrgkanis: Bayesian Incentive-Compatible Bandit Exploration. EC 2015. A. Rakhlin, K. Sridharan: Online Learning with Predictable Sequences. COLT 2013. A. Rakhlin, K. Sridharan: Optimization, Learning, and Games with Predictable Sequences. NIPS 2013. Clustering M.F. Balcan, A. Blum, A. Gupta. Clustering under Approximation Stability K. Voevodski et al. Min-Sum Clustering of Protein Sequences with Limited Distance Information J. Eldridge, M. Belkin, Y. Wang. Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering. COLT 2015. P. Awasthi and M.F. Balcan. Center Based Clustering: A Foundational Perspective. Book Chapter in Handbook of Cluster Analysis, 2015. Y. Li, K. He, D. Bindel, and J.E. Hopcroft. Uncovering the Small Community Structure in Large Networks: A Local Spectral Approach. WWW 2015. M. Ackerman and S. Dasgupta. Incremental clustering: the case for extra clusters. NIPS 2014. M.F. Balcan, C. Borgs, M. Braverman, J. Chayes, and S. Teng. Finding Endogenously Formed Communities. SODA 2013. D. Hsu and S.M. Kakade. Learning Mixtures of Spherical Gaussians: Moment Methods and Spectral Decompositions. ITCS 2013. S. Vassilvitskii and S. Venkatasubramanian. New Developments In The Theory Of Clustering. Tutorial at KDD 2010. M.F. Balcan and P. Gupta. Robust Hierarchical Clustering. COLT 2010. M.F. Balcan, A. Blum, and S. Vempala. A Discriminative Framework for Clustering via Similarity Functions. STOC 2008. See also full version. Adversarial Machine Learning I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial networks. NIPS 2014. A. Athalye, N. Carlini, D. Wagner. Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples. ICML 2018. E. Wong, J. Z. Kolter. Provable Defenses Against Adversarial Examples via the Convex Outer Adversarial Polytope. ICML 2018. Y. Liu, X. Chen, C. Liu, D. Song. Delving into Transferable Adversarial Examples and Black-box Attacks. ICLR 2017. M. Hein, M. Andriushchenko. Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation. NIPS 2017. P. Awasthi, M.F. Balcan, P.M. Long. The Power of Localization for Efficiently Learning Linear Separators with Noise. Journal of the ACM 2017. Contextual Bandit Learning A. Agarwal, J. Langford. ICML Tutorial on Real World Interactive Learning. ICML 2017 Text Generation I. Sutskever, O. Vinyals, and Q. V. Le. Sequence to sequence learning with neural networks. NIPS 2014. D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. ICLR 2015. Structured Prediction/Graphical Models D. P. Kingma, and M. Welling. Auto-Encoding Variational Bayes. ICLR 2014. M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul. An Introduction to Variational Methods for Graphical Models. Machine Learning 1999. Reinforcement Learning C. Szepesvari. Algorithms for reinforcement learning. 2010. L. Kaelbling, M. Littman, A. Moore. Reinforcement Learning: A Survey. JAIR 1996 V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing atari with deep reinforcement learning. 2013. D Silver, A Huang, C J Maddison, A Guez, L Sifre, G van den Driessche, J Schrittwieser, I Antonoglou, V Panneershelvam, M Lanctot, S Dieleman, D Grewe, J Nham, N Kalchbrenner, I Sutskever, T Graepel, T Lillicrap, M Leach, K Kavukcuoglu, D Hassabis. Mastering the game of Go with Deep Neural Networks and Tree Search. Nature 2016. D Silver et al. Mastering the game of Go without human knowledge. Nature 2017. Unsupervised Learning and Domain Adaptation for Machine Translation M. Artetxe, G. Labaka, E. Agirre, K. Cho. Unsupervised Neural Machine Translation. ICLR 2018. G. Lample, M. Ott, A. Conneau, L. Denoyer, M. Ranzato. Phrase-Based and Neural Unsupervised Machine Translation. EMNLP 2018. Y. Ganin, V. Lempitsky. Unsupervised Domain Adaptation by Backpropagation. ICML 2015. Brain Activity for Meanings of Nouns T.M. Mitchell, S. V. Shinkareva, A. Carlson, K. Chang, V.L. Malave, R.A. Mason, M. A. Just. Predicting Human Brain Activity Associated with the Meanings of Nouns. Science 2018. G. Bellec, D. Salaj, A. Subramoney, R. Legenstein, W. Maass. Long short-term memory and learning-to-learn in networks of spiking neurons. 2018. P. Welander, S. Karlsson, A. Eklund, Generative Adversarial Networks for Image-to-Image Translation on Multi-Contrast MR Images - A Comparison of CycleGAN and UNIT. 2018 Ethics and Fairness in Machine Learning M.F. Balcan, T. Dick, R. Noothigattu, and A.D. Procaccia. Envy-free Classification. 2018. T. B. Hashimoto, M. Srivastava, H. Namkoong, P. Liang. Fairness Without Demographics in Repeated Loss Minimization. ICML 2018. L.T. Liu, S. Dean, E. Rolf, M. Simchowitz, M. Hardt. Delayed Impact of Fair Machine Learning. ICML 2018. Understanding Recurrent Neural Networks Y. Chen, S. Gilroy, A. Maletti, J. May, K. Knight. Recurrent Neural Networks as Weighted Language Recognizers. ACL 2018. O. Levy, K. Lee, N. FitzGerald, L. Zettlemoyer. Long Short-Term Memory as a Dynamically Computed Element-wise Weighted Sum. ACL 2018. G. Weiss, Y. Goldberg, E. Yahav. Long Short-Term Memory as a Dynamically Computed Element-wise Weighted Sum. ACL 2018. B. Lake, M. Baroni. Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks. ICML 2018. Multimodal Learning A. Agrawal, J. Lu, S. Antol, M. Mitchell, C. L. Zitnick, D. Batra, D. Parikh. VQA: Visual Question Answering. ICCV 2015. A. Das, S. Datta, G. Gkioxari, S. Lee, D. Parikh, D. Batra. Embodied Question Answering. CVPR 2018. M. Tapaswi, Y. Zhu, R. Stiefelhagen, A. Torralba, R. Urtasun, S. Fidler. MovieQA: Understanding Stories in Movies through Question-Answering. CVPR 2016. Transfer Learning A. Zamir, A. Sax, W. Shen, L. Guibas, J. Malik, S. Savarese. Taskonomy: Disentangling Task Transfer Learning. CVPR 2018. J. Howard, S. Ruder. Universal Language Model Fine-tuning for Text Classification. ACL 2018. M.E. Peters, M. Neumann, M. Iyyer, M. Gardner, C. Clark, K. Lee, L. Zettlemoyer. Deep contextualized word representations. NAACL 2018.