Topics:
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.
Outline
Check Rutgers’ Academic Calendar.
- Lecture 1 – Sep. 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 – Sep. 8: Stochastic Optimization – Gradient Descent [Chapters 4.1-4.2-4.5]
- Recitation 1: Stochastic Optimization (Rahul)
- Lecture 3 – Sep. 13: Stochastic Optimization – Genetic Algorithms [Chapters 4.1-4.2-4.5]
- Lecture 4 – Sep. 15: Supervised Learning: Regression and Classification [Chapters 18.1-18.2-18.3-18.4]
- Recitation 2: Regression and Classification (Chaitanya)
- Lecture 5 – Sep. 20: Decision Trees [Chapters 18.1-18.2-18.3-18.4]
- Lecture 6 – Sep. 22: Neural Networks [Chapters 18.7]
- Recitation 3: Neural Networks (Rahul)
- Lecture 7 – Sep. 27: Non-parametric Models and Support Vector Machines [Chapters 18.8-18.9-18.10]
- Lecture 8 – Sep. 29: Review of Supervised Learning [Chapter 18]
- Recitation 4: Neural Networks & SVMs (Chaitanya)
- Lecture 9 – Oct. 4: Intro to Decision Making – Search [Chapters 3.1-3.2-3.3-3.4]
- Lecture 10 – Oct. 6: Heuristic Search [Chapters 3.5 – 3.6]
- Recitation 5: Search Methods (Rahul)
- Lecture 11 – Oct. 11: Adversarial Search [Chapters 5.1-5.2-5.3-5.4-5.5]
- Lecture 12 – Oct. 13: Constraint Satisfaction Problems [Chapters 6.1-6.2-6.3-6.4]
- Recitation 6: Midterm preparation (Both TAs)
- Lecture 13 – Oct. 18: Logic-based Inference and Binary Satisfiability [Chapters 7.2-7.4-7.5-7.6]
- Midterm – Oct. 20 (TENTATIVE DATE)
- Recitation 7: Foundations of Logic (Chaitanya)
- Lecture 14 – Oct. 25: Classical Planning [Chapters 10.1-10.2]
- Lecture 15 – Oct. 27: Probabilistic Reasoning [Chapters 13.2-13.3-13.4-13.5-13.6]
- Recitation 8: Foundations of Probability Reasoning (Rahul)
- Lecture 16 – Nov. 1: Bayesian Networks [Chapters 14.1-14.2-14.3]
- Lecture 17 – Nov. 3: Bayesian Inference [Chapters 14.4-14.5]
- Recitation 9: Bayesian Networks and Inference (Rahul)
- Lecture 18 – Nov. 8: Statistical Learning [Chapters 20.1-20.2] ?
- Lecture 19 – Nov. 10: Statistical Learning / Expectation-Maximization [Chapters 20.1-20.2] ?
- Recitation 10: Filtering and Smoothing (Chaitanya)
- Lecture 20 – Nov. 15: Temporal Models [Chapters 15.1-15.2] ?
- Lecture 21 – Nov. 17: HMMs: Smoothing, Most Likely Explanation [Chapters 15.3-15.4-15.5] ?
- Recitation 11: Utility Theory Foundations (Chaitanya)
- Lecture 22 – Nov. 22: Kalman and Particle Filters – Intro to Utility Theory [Chapters 15.3-15.4-16.2-16.3-16.4]
- Recitation 12: Markov Decision Processes (Rahul)
- Lecture 23 – Nov. 29: Decision Networks – Intro to Markov Decision Processes [Chapters 16.5-16.6 – Chapter 17.1]
- Lecture 24 – Dec. 1: Value & Policy Iteration [Chapters 17.2-17.3]
- Recitation 13: POMDPs (Chaitanya)
- Lecture 25 – Dec. 6: Partially Observable Markov Decision Processes [Chapters 17.4]
- Lecture 26 – Dec. 8: Review of MDPs and POMPDs – Intro to Reinforcement Learning [Chapter 17]
- Recitation 14: Final preparation (Both TAs – only Wednesday)
- Lecture 27 – Dec. 13: Future Prospects of AI and Application Domains [Chapters 20.3] ?
Prerequisites
Courses:
- CS 205 Introduction to Discrete Structures I
Reading Material
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 black/whiteboard. Students are expected to take notes during the presentation of the material in the classroom and the recitations. Homeworks, programming assignments and exams will be based on the presented material.
Exams
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 last 2/3rds of the course (there will be some overlap with 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 corresponding Instructor; for assistance contact your Dean’s Office. Also, check the definition of Final Exam Conflicts by SAS.
Assignments
There will be multiple assignments (probably 4). You will be informed in advance when an assignment is due. Typically, each assignment will include opportunities for extra credit.
The assignments include practice questions which are intended to assist the student in mastering the course content. They 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 teams of students – two at most. 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
website.
Submission Rules
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.
Grading System
The final grade will be computed according to the following rule (this is tentative and can change):
- Assignments: 50 points total (approx. 8 to 12 points each depending on difficulty)
- Midterm and Exam: 50 points (25 points each)
- Participation: up to 5 points (this is up to the discretion of the instructors and the TAs)
By default your participation grade is 0, i.e., if you frequently come to the lectures/recitations but you rarely answer questions during the lectures or the recitations, your participation grade will be 0. Positive participation grades will be given to students that actively participate in lectures and recitations.
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.
Academic Standards
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. At a minimum your grade in the corresponding exam/assignment will be reduced. 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 similar effects to those mentioned above. 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, 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.
Latex Resources
General info on what you can do with LaTeX:
Getting Started with Latex
The Not So Short Introduction to Latex
Comprehensive List of Latex Symbols
Latex for Logicians
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.
Linux (Ubuntu)
Latex on Ubuntu
Tex Live
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”.
Windows
Latex for Windows help
MikTex (Latex for Windows)
If you follow the instructions on the first link you should be able to get it working on a Windows system.
You can find online Windows executables for the following programs (follow the order when installing): MiKTeX – Ghostscript – Ghostview – WinEdt.