Videos
Some lectures will be recorded and can be accessed through Panopto with an Andrew ID [link].
Syllabus [pdf]
Basic Information
| Meeting Days, Times, Location: Tue/Thu 10:30am-11:50am, GHC 5222 |
| Semester: Spring, Year: 2018 |
| Units: 9/12, Section(s): 08-537/08-737 |
Instructor information
| Name | Dr. Fei Fang |
| Contact Info | Email: feifang@cmu.edu |
| Office location | Wean Hall 4126 |
| Office hours | Tue/Thu 1pm-2pm |
TA Information
| TA name | Chun Kai Ling |
| TA Contact Info | Email: chunkail@andrew.cmu.edu |
| Office location | GHC 6507 |
| Office hours | Wed/Fri 2pm-3pm |
Course Description
The rapid advance in artificial intelligence (AI) has opened up new possibilities of using AI to tackle the most challenging societal problems today. This course brings together a set of advanced AI methods that allow us to address such challenges and promote social good:
- Optimization: mathematical programming, robust optimization, influence maximization
- Game Theory and Mechanism Design: security games, human behavior modeling, auction and market equilibrium, citizen science
- Machine Learning: classification, clustering, probabilistic graphical models, deep learning
- Sequential Decision Making: Markov Decision Processes (MDPs), partially observable MDPs, online planning, reinforcement learning
In addition to providing a deep understanding of these methods, the course will introduce which societal challenges they can tackle and how, in the areas of (i) healthcare, (ii) social welfare, (iii) security and privacy, (iv) environmental sustainability. The course will also cover special topics such as AI and Ethics and AI and Humans. Example research projects and social good outcomes can be found at http://aiandsocialgood.org
The course content is designed to not have too much overlap with other AI courses offered at CMU. Although the course is listed within SCS, it should be of interest to students in several other departments, including ECE, EPP and SDS.
(9 Unit) The students in this 9-unit course are expected to have taken at least three mathematics courses covering linear algebra, calculus, and probability. The students will work in groups on a systematic literature review or a project exploring the possibility of applying existing AI tools to a societal problem, with a survey paper or technical report and presentation delivered at the end of the semester.
(12 Unit) This 12-unit course is only open to graduate students (master and Ph.D. students) with previous programming experience and background knowledge in artificial intelligence. The students will work in groups on a research project with a research-style paper and an oral presentation delivered at the end of the semester. Please see the instructor if you are unsure whether your background is suitable for the course.
Learning Objectives
At the end of the course, the students should be able to
- Identify societal challenges that can potentially be tackled by AI methods, and determine which AI methods can be applied
- Describe the AI methods covered in the course, including the basic concepts, the key algorithms, and the commonly-used implementation of the methods
- Model the societal challenges as mathematical problems that AI techniques can be applied and propose how to adjust and modify the AI techniques to fit the problems
- Describe evaluation criteria and methodologies of applying AI methods for social good
- Deliver written and oral presentation on research projects or research survey
Course Project Exhibition
- Study of Human Game-Playing with a Humanoid Robot
Team members: Aaron Roth, Tamara Amin, and Umang Bhatt
Advisory board: Afsaneh Doryab, Louis-Philippe Morency, Jeffrey Cohn, Fei Fang - Clusters Similarity Comparison of Privacy and Security Scales and Behaviors
Team members: Jessica Colnago
Advisory board: Alessandro Acquisti, and Lorrie F Cranor - Kiva Loan Applicants Poverty Prediction
Team members: Chi Fang, Tianyu Gu
Advisory board: Fei Fang - “Watchers”: Extending Patrol Algorithms into a Police Volunteer Patrol Organizer
Team members: Joseph Gnehm - A State-of-the-Art Review on Predictive Analytics in Healthcare
Team members: Antoine He, Ho Tae Noh - Bus Arrival Time Prediction [slides][report]
Team members: Brandon Houghton, Kenji Yonekawa
Advisory board: Fei Fang - Modeling Observability in Adaptive Systems to Defend Against Advanced Persistent Threats
Team members: Cody Kinneer
Collaborators: Ryan Wagner
Advisors: Fei Fang, Claire Le Goues, David Garlan - Optimizing Vehicle Routing for Air Quality Mobile Sampling [slides]
Team members: Quanyang Lu
Advisory board: Fei Fang - Leveraging Adversarial Machine Learning to Automate Defenses Against Operating-System Fingerprinting
Team members: Mahmood Sharif and Maggie Oates
Advisors: Lujo Bauer and Michael K. Reiter - Peer-to-peer ridesharing
Team members: Hoon Oh, Weilong Wang
Advisors: Alexandre Jacquillat, Fei Fang - Domain Registration Policy Strategies and the Fight against Online Crime
Team members: Janos Szurdi - Real-time stochastic control approach for traffic routing using reinforcement learning algorithm
Team members: Pinchao Zhang
Advisors: Sean Qian, Fei Fang
Course Schedule
| Date | Theme/Topic | Assignment Due | Class Material and Reference |
| 1/16 | M0: Introduction, Logistics, Course Project | Slides (pdf) | |
| 1/18 | M1-1 [Optimization]: Optimization Problems
Cover: Convex optimization, Linear Programming (LP) and Mixed Integer Linear Programming (MILP) |
Slides (pdf)
Convex Optimization, Chapters 1-4 Stephen Boyd and Lieven Vandenberghe (Cambridge University Press) Applied Mathematical Programming, Chapters 2, 9 Bradley, Hax, and Magnanti (Addison-Wesley, 1977) |
|
| 1/23 | M1-2 [Optimization]: Conservation Planning
Cover: Wildlife corridor design |
PRA1 due | Slides (pdf)
(PRA1) Solving Connected Subgraph Problems in Wildlife Conservation Bistra Dilkina & Carla P. Gomes Trade-offs and efficiencies in optimal budget-constrained multispecies corridor networks Robust Network Design for Multispecies Conservation Ronan Le Bras, Bistra Dilkina, Yexiang Xue, Carla P. Gomes, Kevin S. McKelvey, Michael K. Schwartz, Claire A. Montgomery |
| 1/25 | M2-1 [Game Theory]: Basics of Game Theory
Cover: Minimax theory, Nash Equilibrium, Stackelberg Equilibrium |
HW0 due
HW0 [pdf] |
Slides (pdf)
Algorithmic Game Theory, Chapters 1-3 Editors: Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani (Cambridge University Press) |
| 1/30 | M2-2 [Game Theory]: Security Games
Cover: Ferry protection, ranger patrol planning |
PRA2 due | Slides (pdf)
James Pita, Manish Jain, Janusz Marecki, Fernando Ordóñez, Christopher Portway, Milind Tambe, Craig Western, Praveen Paruchuri, Sarit Kraus Optimal Patrol Strategy for Protecting Moving Targets with Multiple Mobile Resources Fei Fang, Albert Xin Jiang, Milind Tambe Deploying PAWS: Field Optimization of the Protection Assistant for Wildlife Security Fei Fang, Thanh H. Nguyen, Rob Pickles, Wai Y. Lam, Gopalasamy R. Clements, Bo An, Amandeep Singh, Milind Tambe, Andrew Lemieux |
| 2/1 | M2-3 [Game Theory]: Human Behavior Modeling
Cover: Prospect theory, Quantal response |
HW1 due
HW1 [pdf] Submit Final Project Group Member List |
Slides (pdf)
(PRA4) Comparing Human Behavior Models in Repeated Stackelberg Security Games: An Extended Study Debarun Kar, Fei Fang, Francesco M. Delle Fave, Nicole Sintov, Milind Tambe, Arnaud Lyet Improving Resource Allocation Strategy Against Human Adversaries in Security Games Rong Yang, Christopher Kiekintveld, Fernando Ordonez, Milind Tambe, Richard John Predicting human behavior in unrepeated, simultaneous-move games James R. Wright, Kevin Leyton-Brown |
| 2/6 | Guest Lecture by Prof. Illah Nourbakhsh (Carnegie Mellon University)
AI and Ethics |
PRA3 due | (PRA3) The Rhetoric of Robotics
Illah Reza Nourbakhsh |
| 2/8 | M3-1 [Machine Learning]: Classification, Clustering, Probabilistic Graphical Models
Cover: Decision trees, k-means, Gaussian Mixture Models (GMMs), Dynamic Bayesian Networks (DBNs), Markov Random Fields (MRFs) |
PRA4 due | Slides (pdf)
Pattern Recognition and Machine Learning, Chapters 4, 8, 9 Christopher Bishop |
| 2/13 | M3-2 [Machine Learning]: Predict Illegal Activities
Cover: Predict poaching threat, predict urban crime |
HW2 due | Slides (pdf)
Chao Zhang, Shahrzad Gholami, Debarun Kar, Arunesh Sinha, Manish Jain, Ripple Goyal, Milind Tambe Shahrzad Gholami, Benjamin Ford, Fei Fang, Andrew Plumptre, Milind Tambe, Margaret Driciru, Fred Wanyama, Aggrey Rwetsiba, Mustapha Nsubaga, Joshua Mabonga Debarun Kar, Benjamin Ford, Shahrzad Gholami, Fei Fang, Andrew Plumptre, Milind Tambe, Margaret Driciru, Fred Wanyama, Aggrey Rwetsiba CAPTURE: A New Predictive Anti-Poaching Tool for Wildlife Protection Thanh H. Nguyen, Arunesh Sinha, Shahrzad Gholami, Andrew Plumptre, Lucas Joppa, Milind Tambe, Margaret Driciru, Fred Wanyama, Aggrey Rwetsiba, Rob Critchlow, Colin Beale |
| 2/15 | M4-1 [Sequential Decision Making] Markov Decision Process (MDP)
Cover: Policy iteration, Value iteration |
Project Proposal due | Slides (pdf)
Reinforcement Learning: An Introduction, Chapter 3 Richard S. Sutton and Andrew G. Barto |
| 2/20 | M3-2 [Machine Learning]: Predict Illegal Activities (continued)
(optional) M4-2 [Sequential Decision Making] Policy Gradient Cover: Policy Gradient Theorem, Fictitious Play, Policy learning in games, Forest protection |
PRA5 due | Slides (pdf)
Policy Learning for Continuous Space Security Games using Neural Networks Nitin Kamra, Umang Gupta, Fei Fang, Yan Liu, Milind Tambe
|
| 2/22 | M3-3 [Machine Learning]: Regression
Cover: Linear Regression, Regularization, Kernel Regression |
Slides (pdf)
Pattern Recognition and Machine Learning, Chapters 3, 6 Christopher Bishop |
|
| 2/27 | M1-3 [Optimization] Combinatorial Optimization and Robust Optimization
Cover: Duality, branch and price, maximin model, minimax regret, prevent illegal fishing |
HW3 due | Slides (pdf)
Combinatorial Optimization: Algorithms and Complexity, Chapters 3 Christos H. Papadimitriou, Kenneth Steiglitz Branch-and-price: Column generation for solving huge integer programs Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Martin W. P. Savelsbergh, Pamela H. Vance Robust protection of fisheries with COmPASS William Haskell, Debarun Kar, Fei Fang, Milind Tambe, Sam Cheung, Elizabeth Denicola |
| 3/1 | Guest Lecture by Prof. Tuomas Sandholm (Carnegie Mellon University)
Cover: Kidney exchange |
PRA6 due | (PRA6) FutureMatch: Combining Human Value Judgments and Machine Learning to Match in Dynamic Environments.
Dickerson, J. and Sandholm, T. In Proceedings of the AAAI Conference on Artificial Intelligence. Extended version with appendix. Position-Indexed Formulations for Kidney Exchange. Dickerson, J., Manlove, D., Plaut, B., Sandholm, T., and Trimble J. In Proceedings of the ACM Conference on Economics and Computation (EC). Extended version. |
| 3/6 | M4-3 [Sequential Decision Making]: Partially Observable MDPs
Cover: Online Planning, Monte-Carlo Tree Search (MCTS) |
Slides (pdf)
Planning and acting in partially observable stochastic domains Leslie Pack Kaelbling, Michael L. Littman, Anthony R. Cassandra Monte-Carlo Planning in Large POMDPs David Silver, Joel Veness Bandit based Monte-Carlo Planning Levente Kocsis and Csaba Szepesvari |
|
| 3/8 | Guest Lecture by Prof. Norman Sadeh (Carnegie Mellon University)
Cover: Security and privacy, Livehoods: understand city using social media |
PRA7 due | (PRA7) The Livehoods Project: Utilizing Social Media to Understand the Dynamics of a City
Justin Cranshaw Raz Schwartz Jason I. Hong Norman Sadeh |
| 3/13 | Spring Break, no class | HW4 due | |
| 3/15 | Spring Break, no class | ||
| 3/20 | Guest Lecture by Prof. Phebe Vayanos (University of Southern California)
Location: GHC 6115 Cover: Kidneys for translation, housing for homeless youth |
PRA8 due | Robust Multiclass Queuing Theory for Wait Time Estimation in Resource Allocation Systems
Chaithanya Bandi, Nikolaos Trichakis, Phebe Vayanos |
| 3/22 | Guest Lecture by Prof. Stephen Smith (Carnegie Mellon University)
Cover: Smart traffic light control |
HW5 due | (PRA8) Real-Time Traffic Control for Sustainable Urban Living
Xiao-Feng Xie, Stephen Smith, Ting-Wei Chen and Gregory Barlow |
| 3/27 | M4-4 [Sequential Decision Making]: Ecosystem Management
Cover: Invasive species management |
PRA9 due | Slides (pdf)
(PRA9) Simulator-Defined Markov Decision Processes: A Case Study in Managing Bio-invasions HJ Albers, TG Dietterich, KM Hall, KD Lee, and MA Taleghan PAC Optimal MDP Planning with Application to Invasive Species Management Majid Alkaee Taleghan, Thomas G. Dietterich, Mark Crowley, Kim Hall, H. Jo Albers Thomas G. Dietterich, Majid Alkaee Taleghan, Mark Crowley |
| 3/29 | M1-4 [Optimization]: Influence Maximization
Cover: Influence propagation models, submodular function optimization |
Project Progress Report due | Slides (pdf)
Maximizing the spread of influence through a social network David Kempe, Jon Kleinberg, Éva Tardos Submodular Functions: Extensions, Distributions, and Algorithms. A Survey Shaddin Dughmi Information and Influence Propagation in Social Networks Wei Chen, Laks V.S. Lakshmanan, Carlos Castillo |
| 4/3 | Guest Lecture by Prof. Milind Tambe (University of Southern California)
Cover: AI and Social Work; HIV prevention among homeless youth |
PRA10 due | (PRA10) Using Social Networks to Aid Homeless Shelters: Dynamic Influence Maximization under Uncertainty
Amulya Yadav, Hau Chan, Albert Jiang, Haifeng Xu, Eric Rice, Milind Tambe Influence Maximization in the Field: The Arduous Journey From Emerging to Deployed Application Amulya Yadav, Bryan Wilder, Eric Rice, Robin Petering, Jaih Craddock, Amanda Yoshioka-Maxwell, Mary Hemler, Laura Onasch-Vera, Milind Tambe, Darlene Woo Uncharted but not Uninfluenced: Influence Maximization with an Uncertain Network Bryan Wilder, Amulya Yadav, Nicole Immorlica, Eric Rice, Milind Tambe |
| 4/5 | M3-4 [Machine Learning]: Deep Learning
Cover: Neural Networks (NNs), Convolutional NN, Faster RCNN, Detecting human and wildlife from UAV videos |
HW6 due | Slides (pdf)
Ian Goodfellow and Yoshua Bengio and Aaron Courville Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks Shaoqing Ren, Kaiming He, Ross Girshick, Jian Sun SPOT Poachers in Action: Augmenting Conservation Drones with Automatic Detection in Near Real Time Elizabeth Bondi, Fei Fang, Mark Hamilton, Debarun Kar, Donnabell Dmello, Jongmoo Choi, Robert Hannaford, Arvind Iyer, Lucas Joppa, Milind Tambe, Ram Nevatia |
| 4/10 | Guest Lecture by Prof. Stefano Ermon (Stanford University)
Cover: Deep learning for developing countries |
PRA11 due | (PRA11) Combining satellite imagery and machine learning to predict poverty
Neal Jean, Marshall Burke, Michael Xie, Matthew Davis, David B. Lobell, Stefano Ermon Deep Gaussian Process for Crop Yield Prediction Based on Remote Sensing Data Jiaxuan You, Xiaocheng Li, Melvin Low, David Lobell, Stefano Ermon |
| 4/12 | M2-4 [Game Theory]: Mechanism Design with Money
Cover: Auction, Truthfulness, Price-of-Anarchy |
Slides (pdf)
Algorithmic Game Theory, Chapters 9, 11 Editors: Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani (Cambridge University Press) |
|
| 4/17 | M2-5 [Game Theory]: Spatio-Temporal Pricing in Ridesharing Platforms
Cover: scheduling and pricing, competitive equilibrium |
PRA12 due | Slides (pdf)
(PRA12) Spatio-Temporal Pricing for Ridesharing Platforms Hongyao Ma, Fei Fang, David C. Parkes |
| 4/19 | CMU’s Carnival, No class | ||
| 4/24 | Guest Lecture by Prof. David Danks (Carnegie Mellon University)
Cover: AI and Humans |
PRA13 due | (PRA13-a) Regulating Autonomous Systems: Beyond Standards
David Danks and Alex John London (PRA13-b) Finding trust and understanding in autonomous technologies David Danks |
| 4/26 | Guest Lecture by Yexiang Xue (Cornell University)
Cover: Citizen Science, Computational Sustainability |
HW7 due | (PRA14) Avicaching: A Two Stage Game for Bias Reduction in Citizen Science
Yexiang Xue, Ian Davies, Daniel Fink, Christopher Wood, Carla P. Gomes Behavior Identification in Two-stage Games for Incentivizing Citizen Science Exploration Yexiang Xue, Ian Davies, Daniel Fink, Christopher Wood, Carla P. Gomes Improving Your Chances: Boosting Citizen Science Discovery Yexiang Xue, Bistra Dilkina, Theodoros Damoulas, Daniel Fink, Carla P. Gomes and Steve Kelling |
| 5/1 | Course Project Presentation 1 | PRA14 due | |
| 5/3 | Course Project Presentation 2 | ||
| 5/10 | Final Project Report due |
Assessments
The final course grade will be calculated using the following categories:
| Assessment | Percentage of Final Grade |
| Class participation | 10 points |
| Paper Summaries | 20 points |
| Written Answers Assignment | 20 points |
| Final Project | 50 points |
- Class participation. The grading of the class participation will be mostly based on attendance, checked by in-class quizzes and asking and answering questions in class. Other factors include asking and answering questions on Canvas.
- Paper reading assignment. The course will require all students to complete weekly paper reading assignments individually. In each assignment, the students are required to provide a summary of the paper/article, a list of questions, and a few brainstorming ideas. The assignments will be submitted through Canvas and will be peer reviewed, but the final score will be provided by the instructor and the TA. For each student, the lowest scored assignment will be dropped.
- Written answers assignment. The course will require all students to complete biweekly written answers assignment individually. Each written answers assignment will involve checking the understanding of basic concepts and working through the algorithms presented in class on example problems. Most questions are multiple-choice questions or numerical answer questions. In addition to providing the answers, the students are required to provide explanations to the answers. The answers will be submitted and auto-graded through Canvas. The explanations will be checked through peer review. For each student, the lowest scored assignment will be dropped.
- Final project. The students will work in small groups (1-3 students in each group). The students are expected to focus on one or more societal challenges, summarize or propose models and AI-based solutions to tackle the challenges, and evaluate the solutions. The students are required to submit project report through Canvas and deliver oral presentation. The instructor will provide suggested project topics. The students can also propose their own projects topics related to AI and Social Good but they will need consent from the instructor. The progress of projects will be checked through Project Proposal, Project Progress Report, Project Presentation, and Final Project Report. The proposal and progress report will be peer reviewed. The presentation and the final report will be evaluated by instructor and TA directly.
- The students who choose the 12-unit section will work on a research project, with a research-style paper and an oral presentation delivered at the end of the semester. Ph.D. students may choose a paper format with the guidance of their advisors. For master students, a sample research-style paper can be found here: https://feifanginfo.files.wordpress.com/2016/11/2015_aaai_csworkshop_repeatedssg.pdf
- The students who choose the 9-unit section will work on a systematic literature review or a project exploring the possibility of applying existing AI tools to a social good problem, with a survey paper or technical report and presentation delivered at the end of the semester.
- Sample survey paper: http://www.sigecom.org/exchanges/volume_15/1/FANG.pdf
- Sample technical report: https://www.aaai.org/ocs/index.php/SSS/SSS12/paper/view/4310/4644
Students will be assigned the following final letter grades, based on calculations coming from the course assessment section.
Fei Fang 