CS 520: Introduction to Artificial Intelligence - Fall 2016
The class will introduce fundamental ideas that have emerged over the past fifty years of AI research. It will also provide a useful toolbox of AI algorithms. The main unifying theme is the idea of an intelligent agent: autonomous computational systems that receive percepts from the environment and perform actions or take decisions. The objective of the class is to (a) teach students how to identify the appropriate technique for designing such intelligent agents for different types of problems and (b) provide them experience in implementing such solutions on representative AI challenges.
The class will be split into three modules. Each module will focus on a different set of challenges and the corresponding techniques:
Part 1 - Deterministic Reasoning: Heuristic Search, Local Search, Adversarial Search, Constraint Satisfaction Problems, Logic-based Reasoning, Classical Planning, Motion Planning
Part 2 - Reasoning under Uncertainty: Bayesian Networks, Hidden Markov Models, Kalman and Particle Filters, (Partially Observable) Markov Decision Processes
Part 3 - Introduction to Machine Learning: Decision Trees, Expectation Maximization, Neural Networks, Support Vector Machines, Principles of Reinforcement Learning
Below follows a more detailed description of the above modules:
Part 1: Initially the focus will be on autonomous decision-making in deterministic environments. Search techniques (including dynamic programming algorithms, informed techniques like A* and local search methods, such as hill climbing and simulated annealing) will be presented. These methods reason over several steps into the future. The class will then discuss ways to represent knowledge about the world through logic and how to reason logically with that knowledge, especially for problems with constraints. The first part of the class will close with path planning algorithms in continuous spaces and action planning.
Part 2: This part will introduce a significant challenge, that of uncertainty. In this section, the intelligent agents do not have perfect knowledge of the world. They depend on probabilistic tools, such as the Bayes law, in order to reason about their state, the world and take decisions. For example Bayesian networks will be presented that provide a systematic way of representing independence and conditional independence relationships in order to simplify probabilistic representations of the world. They can be used in order to achieve inference under uncertainty. Building on these tools, we will present filtering variants of Hidden Markov Models (e.g. Kalman filter, particle filters) that are able to reason under uncertainty when the environment changes over time. Then through the tool of Markov Decision Processes we will show how it is possible to not only infer the world’s state under the presence of uncertainty but also to make decisions under uncertainty so as to maximize an expected utility function.
Part 3: The final part of the class involves even more challenging problems, where the environment is not just uncertain but unknown. In order for agents to be able to cope with such problems they depend on learning techniques that generate the knowledge required for decision-making. Inductive learning techniques use observations to create simple theories about the world. Statistical learning methods learn probabilistic models of the world when there is uncertainty in the measurements. Neural networks are biologically inspired and provide a way of inferring a world model. Finally, reinforcement learning techniques show how intelligent agents can learn from success and failure, from reward and punishment.
The class will conclude with the future prospects of AI.
Check Rutgers' Key Dates.
- Lecture 1 - Sept. 6: Introduction [Chapters 1.1-1.2-1.3-1.4-1.5-2.1-2.2-2.3-2.4-2.5]
- Lecture 2 - Sept. 9: Uninformed Search [Chapters 3.1-3.2-3.3-3.4]
- Lecture 3 - Sept. 13: Heuristic Search [Chapters 3.5 - 3.6]
- Lecture 4 - Sept. 16: Adversarial Search [Chapters 5.1-5.2-5.3-5.4-5.5]
- Lecture 5 - Sept. 20: Local Search [Chapters 4.1-4.2-4.5]
- Lecture 6 - Sept. 23: Constraint Satisfaction Problems [Chapters 6.1-6.2-6.3-6.4]
- Lecture 7 - Sept. 27: Logic-based Inference [Chapters 7.2-7.4-7.5-7.6]
- Lecture 8 - Sept. 30: Binary Satisfiability [Chapters 7.2-7.4-7.5-7.6]
- Lecture 9 - Oct. 4: Classical Planning [Chapters 10.1-10.2]
- Lecture 10 - Oct. 7: Probabilistic Reasoning [Chapters 13.2-13.3-13.4-13.5-13.6]
- Lecture 11 - Oct. 11: Bayesian Networks [Chapters 14.1-14.2-14.3]
- Lecture 12 - Oct. 14: Bayesian Inference [Chapters 14.4-14.5]
- Lecture 13 - Oct. 18: Temporal Models [Chapters 15.1-15.2]
- Lecture 14 - Oct. 21: HMMs: Smoothing, Most Likely Explanation [Chapters 15.3-15.4-15.5]
- Lecture 15 - Oct. 25: Kalman and Particle Filters - Intro to Utility Theory [Chapters 15.3-15.4-16.2-16.3-16.4]
- Lecture 16 - Oct. 28: Decision Networks - Intro to Markov Decision Processes [Chapters 16.5-16.6 - Chapter 17.1]
- Lecture 17 - Nov. 4: Value & Policy Iteration [Chapters 17.2-17.3]
- Lecture 18 - Nov. 8: Partially Observable Markov Decision Processes [Chapters 17.4]
- Lecture 19 - Nov. 11: Review of MDPs and POMPDs Markov Decision Processes [Chapter 17]
- Lecture 20 - Nov. 15: Supervised Learning and Decision Trees [Chapters 18.1-18.2-18.3-18.4]
- Lecture 21 - Nov. 18: Decision Trees [Chapters 18.1-18.2-18.3-18.4]
- Lecture 22 - Nov. 22: Neural Networks [Chapters 18.7]
- Lecture 23 - Nov. 29: Non-parametric Models and Support Vector Machines [Chapters 18.8-18.9-18.10]
- Lecture 24 - Dec. 2: Review of Supervised Learning: Regression and Classification [Chapter 18]
- Lecture 25 - Dec. 6: Statistical Learning [Chapters 20.1-20.2]
- Lecture 26 - Dec. 9: Expectation-Maximization [Chapters 20.3]
- Lecture 27 - Dec. 13: Future Prospects of AI and Application Domains
Midterm - Nov. 1
Final Exam: Dec 16, 2016, 12:00 PM - 3:00 PM
The class will primarily draw upon material from the following book:
- "Artificial Intelligence: A Modern Approach" by Stuart Russell and Peter Norvig (Third Edition), Prentice Hall Series in Artificial Intelligence
The slides presented during the lectures will cover a limited part of the material discussed in the classroom. The majority of the mathematical notions will be presented on the blackboard. Students are expected to take notes during the presentation of the material in the classroom and the recitations. Homeworks and exams will be based on the presented material.
There will be 2 exams: one midterm and one final. The first exam will cover the material of the first half of the course (approx. first 14 lectures), and the final will cover the remaining material. Check the tentative schedule on the webpage for the date of the midterm. Both exams are in-class exams.
A missed exam draws zero credit. Emergencies will be considered upon submitting a University-issued written verification to the Instructor; for assistance contact your Dean's Office. Also, check the definition of Final Exam Conflicts by SAS.
There will be multiple programming and homework assignments (~5). Each assignment may include extra credit questions.
The homeworks include practice questions which are intended to assist the student in mastering the course content. The assignments will also involve programming AI algorithms and testing their efficiency. Typically you will be asked to submit an electronic version of your code, test runs, a typeset report and demo your project to the teaching assistants.
Assignments should be completed by pairs of students. No additional credit will be given for students that complete a homework individually. Please inform the TAs about the members of your team. Students can switch teams between assignments but they are not required to. When the composition of a team changes, the students need to inform the TA.
Students will receive 10% extra credit if they typeset (in LaTeX) or 5% extra credit if they typewrite their answers (e.g., if a pair was to receive a score of 62/100 and they provide a typeset homework, then their score will be 68/100, i.e,. +10% of 62 points. Resources on how to use LaTeX are available on the course's
No late submission is allowed. If you don't submit an assignment on time, you get 0 points for that homework/project. Students can submit their assignments electronically via Sakai. Programming results must be demonstrated during pre-scheduled demo appointments. The project report must be forwarded in advance of the demo.
The final grade will be computed according to the following rule (this is tentative and can change):
- Assignments: 50 points total (approx. 10 points each)
- Midterm and Exam: 50 points (25 points each)
- Participation Bonus: 0 to 5 points
By default the participation bonus is 0, e.g., if you frequently come to the lectures/recitations but you rarely answer questions during the lectures, your participation grade will be 0. Typically, only few students receive a participation bonus: those that actively and positively participate during lectures. This grade is up to the discretion of the instructor and the TAs.
The mapping of scores to letter grades will be determined at the end of the semester. As a rough guide, the following rule may be used for the final grade (it will be adapted close to the end of the semester):
- A: > 89
- B+: 80-89
- B: 70-79
- C+: 60-69
- C: 50-59
- D: 40-49
- F: less than 40
Students interested in a recommendation letter by the instructor will be offered one only if they achieve a score above 95 after the completion of the course.
Questions about Grading
If you have a question or complaint regarding the points you received on specific parts of an assignment, or an exam, submit a request to the TA, stating specifically but very briefly what parts of that assignment you wish to be reviewed. Please refrain from verbal arguments about grades with the instructor or with any of the TAs. We will try to get back to you soon. The deadline for submitting such requests is the last lecture.
Exams are to be treated as individual efforts. Homeworks and projects are not to be treated as collective efforts beyond the participation of the team members! Discussions are not allowed on how to solve specific questions in homeworks between teams. Do not discuss assignments with students that are not currently taking the class.
A severe penalty will be given to any assignment which indicates collusion or cheating. The usual penalty for cheating on an assignment or an exam is failure in the course. Stealing another person's listing or having another person "ghost write" an assignment will be considered cheating.
Turning in work without properly citing the sources of the content included in your work is plagiarism. All kinds of sources are included in this definition, even those downloaded from the web, in which case an operable link must be cited. Plagiarism from the web or other sources is considered cheating and has the same effects. Even with a reference, submitting an answer to a homework question, verbatim from any source and without any contribution on your part, draws zero credit.
You should carefully study the website of Rutgers University on Academic Integrity and the corresponding policy, as well as the corresponding policy from the department of Computer Science. Your continued enrollment in this course implies that you have read these policies, and that you subscribe to the principles stated therein.
The first link describes many alternatives that are available for installing Tex on a Mac. The second link forwards to the MacTex package, one of the alternatives mentioned in the first website. MaxTex provides everything that you need to use Latex on Mac except from a text editor. It is, however, compatible with a wide variety of popular editors (e.g., Alpha, BBEdit, Emacs, VIM, iTeXMac, TeXShop). Note that MaxTex is a large package.
Carbon Emacs has been succesfully tested with MacTex. After installing MacTex, it is possible to directly compile and view *.tex files from Carbon Emacs's UI.
Note for Mac users: You will probably have problems previewing your PDF output when using the postscript images provided by the instructor for developing the notes. Nevertheless, the PDF file can be printed properly. Prepare your document without the images and then add them. You will probably still be able to preview the intermediate .dvi output file with the "xdvi" program.
You just have to download and install the proper packages described above (e.g., through apt-get), use your favorite editor (e.g., emacs) to prepare a *.tex file and then you compile (run at least two times: "latex filename.tex") to get the *.dvi output. You can go from dvi to postscript with the command "dvips" and you can convert postscript to pdf with the command "ps2pdf".
If you follow the instructions on the first link you should be able to get it working on a Windows system.