Videos

Some lectures will be recorded and can be accessed through Panopto with an Andrew ID.

Basic Information

Meeting Days, Times, Location: Tue/Thu 10:30am-11:50am, GHC 4307

Semester: Spring, Year: 2019

Units: 9/12, Section(s): 17-737/17-537

Instructor information

Name	Dr. Fei Fang
Contact Info	Email: feifang@cmu.edu
Office location	Wean Hall 4126
Office hours	Tue 1pm-2pm

TA Information

TA name	Shurui Zhou
TA Contact Info	Email: shuruiz@andrew.cmu.edu
Office location	Wean Hall 3130
Office hours	Thu 3pm-4pm

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. We will cover a wide range of topics in AI, including:

• Optimization [OPT]: convex optimization, mathematical programming
• Game theory and mechanism design [GT]: computational game theory, mechanism design with and without money, human behavior modeling
• Machine Learning [ML]: classification, clustering, probabilistic graphical models, deep learning
• Sequential Decision Making [RL]: 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.

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.

Exhibition of Course Projects

• An Adversarial Network Approach to Mitigate Mortgae Lending Approval Bias
  Emily Chen, Kashish Garg, Christian Manaog
• Modelling Pet Adoption Rate
  Si Pei Anita Chia, Loki Ravi, Yuhan Xiao
• Literature review of the applications of AI to road traffic analysis and optimization
  Karim Helmy, Vasily Potanin, Anita Yerneni
• Machine Learning and Game Theoretic Approaches to Fighting Crime
  Jiaqi Liu, Arvind Mahankali, Tyson Wang
• Robust Model-Based Reinforcement Learning for Environmental Sustainability
  Melrose Roderick
• Submodularity and Social Good
  Darshan Chakrabarti
• Using Machine Learning to Advance Space Exploration
  Samuel Zhao
• Literature Review: Intelligent Tutoring Systems
  Richard Gu
• Blackbox Model Inference for Robotics
  Afsoon Afzal
• Detecting illegal mining sites via satellite imagery
  Philipp Schneider
• Detecting Hate Speech and Identifying Underlying Topics
  Sheela Hanagal, Katia Villevald
• AI Methods to Aid in Finding New Refugee Resettlement Locations
  Christopher Smith, Tina Wu, Sydney Zheng
• Smart Cities: How Advancements in AI will Help Mold the City of the Future
  Rebecca Groves, Justin Okoro, Dennis Wang
• Dissemination of security and privacy information on Twitter
  Sruti Bhagavatula
• Assisting Post-Disaster Aid Deliveries Through Car Counting
  Omar Delen
• Matching Contributors and Projects on GitHub
  Sophie Qiu
• Classifying Trolls in Twitter Discourse on the Philippine Elections
  Joshua Uyheng

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 the evaluation criteria and methodologies of applying AI methods for social good
• Deliver written and oral presentation on research projects or research survey

Course Schedule

Date	Theme/Topic	Reminder	Class Material and Reference
1/15 (Tue)	Lecture 0: Introduction, Logistics, Course Project
1/17 (Thu)	Lecture 1 [OPT1]: Optimization Problems Cover: Convex optimization, Linear Programming (LP) and Mixed Integer Linear Programming (MILP)		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/22 (Tue)	Lecture 2 [OPT2]: Conservation Planning Cover: Wildlife corridor design		(PRA1) Solving Connected Subgraph Problems in Wildlife Conservation Bistra Dilkina & Carla P. Gomes Trade-offs and efficiencies in optimal budget-constrained multispecies corridor networks Bistra Dilkina, Rachel Houtman, Carla P. Gomes, Claire A. Montgomery, Kevin S. McKelvey, Katherine Kendall, Tabitha A. Graves, Richard Bernstein, Michael K. Schwartz 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/24 (Thu)	Lecture 3 [ML1]: Deep Learning Cover: Neural Networks, Convolutional NN (CNN), Faster RCNN, Detecting human and wildlife from UAV videos		Deep Learning, Chapter 6, 9 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
1/29 (Tue)	Lecture 4 [ML2]: Applications of Deep Learning Cover: Deep learning for developing countries		(PRA2) 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
1/31 (Thu)	Class canceled due to extreme weather conditions
2/5 (Tue)	Lecture 5 [GT1]: Basics of Game Theory Cover: Minimax theory, Nash Equilibrium, Stackelberg Equilibrium		Algorithmic Game Theory, Chapters 1-3 Editors: Noam Nisan,‎ Tim Roughgarden, Eva Tardos,‎ Vijay V. Vazirani (Cambridge University Press)
2/7 (Thu)	Lecture 6 [Ethics]: Guest Lecture by Prof. David Danks Cover: AI and Ethics		TBD
2/12 (Tue)	Lecture 7 [GT2]: Security Games Cover: Ferry protection, ranger patrol planning		(PRA3) Deployed ARMOR Protection: The Application of a Game Theoretic Model for Security at the Los Angeles International Airport 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/14 (Thu)	Lecture 8 [RL1] Markov Decision Process (MDP) Cover: Policy iteration, Value iteration, Partially Observable MDPs		Reinforcement Learning: An Introduction, Chapter 3 Richard S. Sutton and Andrew G. Barto 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
2/19 (Tue)	Lecture 9 [OPT3]: Influence Maximization Cover: Influence propagation models, submodular function optimization		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
2/21 (Thu)	Lecture 10 [ML3]: Regression Cover: Linear Regression, Regularization, Kernel Regression		Pattern Recognition and Machine Learning, Chapters 3, 6 Christopher Bishop
2/26 (Tue)	Lecture 11 [OPT4]: Guest Lecture by Prof. Tuomas Sandholm Cover: Kidney exchange		Optimization-Based AI Ethics: A Kidney Exchange Case Study in Combining Human Value Judgments and Machine Learning to Optimize in Dynamic Environments 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.
2/28 (Thu)	Lecture 12 [OPT5]: Guest Lecture by Amulya Yadav Cover: AI and Social Work; HIV prevention among homeless youth		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
3/5 (Tue)	Lecture 13 [ML4]: Decision Trees and Probabilistic Graphical Models Cover: Decision trees, k-means, Gaussian Mixture Models (GMMs), Dynamic Bayesian Networks (DBNs), Markov Random Fields (MRFs)		Pattern Recognition and Machine Learning, Chapters 4, 8, 9 Christopher Bishop
3/7 (Thu)	Lecture 14 [ML5]: Guest Lecture by Prof. Norman Sadeh Cover: Livehoods: understand city using social media		The Livehoods Project: Utilizing Social Media to Understand the Dynamics of a City Justin Cranshaw Raz Schwartz Jason I. Hong Norman Sadeh
3/12 (Tue)	Spring Break, no class
3/14 (Thu)	Spring Break, no class
3/19 (Tue)	Lecture 15 [GT3]: Human Behavior Modeling Cover: Prospect theory, Quantal response		“A Game of Thrones”: When Human Behavior Models Compete in Repeated Stackelberg Security Games Debarun Kar, Fei Fang, Francesco Maria Delle Fave, Nicole Sintov, Milind Tambe 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
3/21 (Thu)	Lecture 16 [ML6]: Predict Illegal Activities Cover: Predict poaching threat, predict urban crime		Keeping pace with criminals: Designing patrol allocation against adaptive opportunistic criminals Chao Zhang, Arunesh Sinha, Milind Tambe Taking it for a Test Drive: A Hybrid Spatio-temporal Model for Wildlife Poaching Prediction Evaluated through a Controlled Field Test Shahrzad Gholami, Benjamin Ford, Fei Fang, Andrew Plumptre, Milind Tambe, Margaret Driciru, Fred Wanyama, Aggrey Rwetsiba, Mustapha Nsubaga, Joshua Mabonga Cloudy with a Chance of Poaching: Adversary Behavior Modeling and Forecasting with Real-World Poaching Data 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
3/26 (Tue)	Lecture 17 [GT4]: Social Choice and Mechanism Design Cover: Voting Rules, Auctions		Algorithmic Game Theory, Chapters 9, 11 Editors: Noam Nisan,‎ Tim Roughgarden, Eva Tardos,‎ Vijay V. Vazirani (Cambridge University Press)
3/28 (Thu)	Lecture 18 [OPT6]: Guest Lecture by Prof. Jun Zhuang Cover: Fire Management		(TBD) Analysis of fire protection efficiency in the United States: a two-stage DEA-based approach Feng Li, Qingyuan Zhu, Jun Zhuang
4/2 (Tue)	Lecture 19 [ML7] Guest Lecture by Tanya Berger-Wolf Cover: Computer vision for wildlife identification		Wildbook: Crowdsourcing, computer vision, and data science for conservation T. Y. Berger-Wolf, D. I. Rubenstein, C. V. Stewart, J. Holmberg, J. Parham, S. Menon, J. Crall, J. Van Oast, E. Kiciman, L. JoppaAnimal Population Censusing at Scale with Citizen Science and Photographic Identification Jason Remington Parham, Jonathan Crall, Charles Stewart, Tanya Berger-Wolf, Daniel Rubenstein
4/4 (Thu)	Lecture 20 [GT5]: Guest Lecture by Prof. Kevin Leyton-Brown Cover: Mechanism design for social good		Designing and Evolving an Electronic Agricultural Marketplace in Uganda. N. Newman, K. Leyton-Brown, N. Immorlica, L. Bergquist, B. Lucier, J. Quinn, C. McIntosh, R. Ssekibuule
4/9 (Tue)	Lecture 21 [RL2] Basics of Reinforcement Learning Cover: Q-Learning, Policy Gradient		Reinforcement Learning: An Introduction, Chapter 6,13 Richard S. Sutton and Andrew G. Barto
4/11 (Thu)	No class (CMU Carnival)
4/16 (Tue)	Lecture 22 [RL3]: Applications of MDP and RL Cover: Invasive species management, Fire management, Forest protection		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 PAC Optimal Planning for Invasive Species Management: Improved Exploration for Reinforcement Learning from Simulator-Defined MDPs Thomas G. Dietterich, Majid Alkaee Taleghan, Mark Crowley Policy Learning for Continuous Space Security Games using Neural Networks Nitin Kamra, Umang Gupta, Fei Fang, Yan Liu, Milind Tambe
4/18 (Thu)	Lecture 23 [OPT7]: Combinatorial Optimization and Robust Optimization Cover: Duality, branch and price, maximin model, minimax regret, prevent illegal fishing		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
4/23 (Tue)	Lecture 24 [GT6]: Spatio-Temporal Pricing in Ridesharing Platforms Cover: scheduling and pricing, competitive equilibrium		Spatio-Temporal Pricing for Ridesharing Platforms Hongyao Ma, Fei Fang, David C. Parkes
4/25 (Thu	Lecture 25 [ML8]: Guest Lecture by Prof. Alexander Hauptmann Cover: Multimedia analysis for Human Rights and Public Safety		TBD
4/30 (Tue)	Course Project Presentation (Poster)		4405 GHC and the 4404 lobby area
5/2 (Thu)	Course Project Presentation (Oral)
5/10 (Fri)		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 participantion 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 the project report through Canvas and deliver an 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 the 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 the 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
    http://www.andrew.cmu.edu/user/feif/Publications/2018_IJCAI_SSGsurvey.pdf
  • Sample technical report: https://www.aaai.org/ocs/index.php/SSS/SSS12/paper/view/4310/4644
    https://aiforsocialgood.github.io/2018/pdfs/track1/24_aisg_neurips2018.pdf Other papers accepted to AI for Social Good Workshop at NeurIPS 2018
    https://aiforsocialgood.github.io/2018/acceptedpapers.htm

Students will be assigned the following final letter grades, based on calculations coming from the course assessment section.