Introduction to Artificial Intelligence Syllabus Overview
Prof. Hoang Kiem
Department of Computer Science
University of Information Technology
Vietnam National University
Lecturer:
Teaching Assistants:
27 June 2011
Ho Chi Minh City, Vietnam
• Introduction
Artificial Intelligence (AI), in general, is a very big field, which encompasses logic, probability, continuous mathematics, perception, reasoning, learning, and action. It contains the ideas of more than sixty years of extensive research. It is difficult or even impossible to explain each sub-field of AI in its own historical context. Hence, in the scope of this introductory course, instead of trying to cover everything that is related to AI, we strive to convey only the most central ideas in highly recognizable sub-fields. The theme of this course, therefore, concerns the idea of intelligent agents – systems that decide what to do, with respect to different situations, and do it efficiently.
In particular, the course explores different aspects of an intelligent system, including: methods for deciding what to do when one needs to think ahead several steps, different ways to integrate and represent human knowledge about the world into a computer program and how to logically reason with the knowledge. Further, it also extends knowledge representing and reasoning techniques in the presence of uncertainty about the world, as might be faced, for example, in designing intelligent system for medical diagnosis and treatment.
This course is primarily intended for undergraduate students. The main pre-requisite of this course is familiarity with fundamental concepts in algorithms, probability, data structures and complexity. As a minor requirement, programming skill at sophomore level is expected.
• Objectives
The primary objective of this course is to provide the students with a good understanding of Artificial Intelligence. During the course, the students will be introduced to basic concepts in knowledge representation and logical reasoning (propositional logic, first-order logic), searching techniques (depth-first search, breadth-first search, A*, mini-max search, constraint satisfaction), representing and reasoning methods in presence of uncertainty (Bayesian belief network, probabilistic inference).
Assignments and final project are also provided to get the students familiar with the concepts taught in class. Mid-term test and final exam (open-book) are designed to closely evaluate the students on most central ideas of AI. At the end of the course, the students are expected to have a deep understanding and concrete experience on AI. Further, they should be able to apply what they have learned in some practical problems.
Besides the main lectures, tutorials are conducted (by teaching assistants) on a weekly basis to help the students in their studying. Students who have troubles in understanding the material will find helpful instructions and guidance at those tutorial sessions. For any further issues, consultations with the lecturer are provided by appointment.
• Course Overview
• Resources
Any textbook in AI can be used for reference. However, the following textbook is considered our primary teaching material and hence, it is compulsory:
Artificial Intelligence: A Modern Approach, 2nd Edition , Russel and Norvig (RN)
For further reference, the following materials are suggested but not compulsory:
• Learning Bayesian Network, Neapolitan (N)
• Probabilistic Graphical Model, Daphne Koller, Nir Friedman (DN)
• Bayesian and Artificial Intelligence, Kevin B. Korb, Ann E. Nicholson (KA)
• Markov Chain Monte Carlo in Practice, W.R. Gilks, S. Richardson (WS)
• Grading policy
The evaluation of students’ performance in this course is organized as follow:
• Three written assignments (10% each): 30%
• Mid-term test (90 minutes, open-book): 20%
• Programming project: 20%
• Final exam (120 minutes, open-book): 30%
Assignments should be handed in to the lecturer during class time (on due date). Late submissions will not be accepted. Project submission is due in the 12 th week of the semester.
• Tentative schedule
• Project scope
The list of possible topics for the project will be released during the 3rd week of the semester. Students can either select one of the listed topics for their project or propose their own ideas. Students have to submit a project proposal (hard-copy, no more than 2 pages) (6th week) including what they intend to do and how they divide the work during weeks and between group members. Students can select their own group members (at least 2 and at most 3 people for each group).
Students have to submit a final report (hard-copy, no more than 10 pages, in the format of a research paper) to the lecturer in the 12th week. Finally, each group needs to prepare a 20-minute presentation of their project in the same week (12th week). The evaluation of the project is based on the final report (10%) and the presentation (10%).
• Lectures outline
• Searching techniques
Many problems in AI can be solved in theory by intelligently searching through the space of possible solutions. Reasoning in AI can, therefore, be reduced to performing a search in solution space. As an example, logical proof can be viewed as searching for a path that leads from premises to conclusions, where each step is the application of an inference rule. Planning algorithm search through trees of goals and sub-goals, attempting to find a least cost path to a target goal. Robotics algorithms for moving limbs and grasping objects use local searches in configuration space.
Clearly, searching is a crucial part of most AI algorithms. However, simple exhaustive searches are rarely sufficient for most real world problems: the size of the search space may grow exponentially with the number of interested parameters. As a result, the search may either too slow to meet real time constraint or never complete. The solution, for many problems, is to use heuristics to eliminate choices that are unlikely to lead to the optimal goal. Of course, such heuristic solution may not guarantee to find the best solution. However, the philosophy of solving real world problem is: finding a good enough solution is much more important than finding the best solution.
Thus, the course will provide the students with the most fundamental foundation on searching strategy, including principled searching techniques (DFS, BFS), which is efficiently applicable only in most theoretical situations, and several searching methods for real world problems which are capable of integrating prior knowledge to guide the process (A*). Some theoretical results are also discussed to provide students with more insightful intuitions.
• Logical representation and reasoning
Logic is a traditional way to represent knowledge in computer. Several different forms of logic are used in AI research. Propositional logic is the logic of statements, which can be either true or false. First-order logic extends propositional logic by allowing the use of quantifiers and predicates. It can express facts about objects, their properties and their relations with each other.
Logical rules are also introduced as part of the knowledge base. Those rules are often used for inference about facts, properties and relations among objects. Efficient algorithms are, therefore, needed to support the inference in a principled way. This course will introduce the students to the traditional framework of propositional and first-order logics. Several efficient and applicable inference algorithms are also discussed in great details.
• Probabilistic representation and inference
Many problems in AI (in reasoning, planning, learning, perceptron and robotics) require the system to operate with incomplete or uncertain information. In real world problems, the situation of incomplete information arises very often. Hence, it calls for the need of powerful frameworks that take into account uncertainty and perform optimally under such uncertainty.
A number of such powerful tools are developed by AI researcher from probability theory. Bayesian networks are very general framework that is applicable to a large number of problems. The essence of this framework is that it allows us to reason under uncertainty. It gives rise to many well-known probabilistic algorithms (in planning, predictions)
In this course, we aim to give the students the fundamental of probabilistic graphical model, in general. Particularly, we concentrate on Bayesian Belief Network, which is the most popular family of probabilistic graphical model. Further, we discuss several well-known probabilistic inference techniques (inference by variable elimination, inference by sampling) in details.
5. References
• Russel and Norvig, AI: A Modern Approach, 2nd Edition (RN)
• Neapolitan, Learning Bayesian Network (N)
• Daphne Koller, Nir Friedman, Probabilistic Graphical Model (DN)
• Kevin B. Korb, Ann E. Nicholson, Bayesian and Artificial Intelligence (KA)
• W.R. Gilks, S. Richardson, Markov Chain Monte Carlo in Practice (WS)