Artificial Intelligence
Principal lecturer: Dr Sean Holden
Taken by: Part IB CST
Term: Easter
Hours: 12
Format: In-person lectures
Suggested hours of supervisions: 3
Prerequisites: Algorithms 1, Algorithms 2.
In addition the course requires some mathematics, in particular some use of vectors and some calculus. Part IA Natural Sciences Mathematics or equivalent and Discrete Mathematics are likely to be helpful although not essential. Similarly, elements of Machine Learning and Real World Data, Foundations of Data Science, Logic and Proof, Prolog and Complexity Theory are likely to be useful. This course is a prerequisite for the Part II courses Machine Learning and Bayesian Inference and Natural Language Processing.
This course is a prerequisite for: Natural Language Processing
Past exam questions, Moodle, timetable
Aims
The aim of this course is to provide an introduction to some fundamental issues and algorithms in artificial intelligence (AI). The course approaches AI from an algorithmic, computer science-centric perspective; relatively little reference is made to the complementary perspectives developed within psychology, neuroscience or elsewhere. The course aims to provide some fundamental tools and algorithms required to produce AI systems able to exhibit limited human-like abilities, particularly in the form of problem solving by search, game-playing, representing and reasoning with knowledge, planning, and learning.
Lectures
- Introduction. Alternate ways of thinking about AI. Agents as a unifying view of AI systems. [1 lecture]
- Search I. Search as a fundamental paradigm for intelligent problem-solving. Simple, uninformed search algorithms. Tree search and graph search. [1 lecture]
- Search II. More sophisticated heuristic search algorithms. The A* algorithm and its properties. Improving memory efficiency: the IDA* and recursive best first search algorithms. Local search and gradient descent. [1 lecture]
- Game-playing. Search in an adversarial environment. The minimax algorithm and its shortcomings. Improving minimax using alpha-beta pruning. [1 lecture]
- Constraint satisfaction problems (CSPs). Standardising search problems to a common format. The backtracking algorithm for CSPs. Heuristics for improving the search for a solution. Forward checking, constraint propagation and arc consistency. [1 lecture]
- Backjumping in CSPs. Backtracking, backjumping using Gaschnig’s algorithm, graph-based backjumping. [1 lecture]
- Knowledge representation and reasoning I. How can we represent and deal with commonsense knowledge and other forms of knowledge? Semantic networks, frames and rules. How can we use inference in conjunction with a knowledge representation scheme to perform reasoning about the world and thereby to solve problems? Inheritance, forward and backward chaining. [1 lecture]
- Knowledge representation and reasoning II. Knowledge representation and reasoning using first order logic. The frame, qualification and ramification problems. The situation calculus. [1 lecture]
- Planning I. Methods for planning in advance how to solve a problem. The STRIPS language. Achieving preconditions, backtracking and fixing threats by promotion or demotion: the partial-order planning algorithm. [1 lecture]
- Planning II. Incorporating heuristics into partial-order planning. Planning graphs. The GRAPHPLAN algorithm. Planning using propositional logic. Planning as a constraint satisfaction problem. [1 lecture]
- Neural Networks I. A brief introduction to supervised learning from examples. Learning as fitting a curve to data. The perceptron. Learning by gradient descent. [1 lecture]
- Neural Networks II. Multilayer perceptrons and the backpropagation algorithm. [1 lecture]
Objectives
At the end of the course students should:
- appreciate the distinction between the popular view of the field and the actual research results;
- appreciate the fact that the computational complexity of most AI problems requires us regularly to deal with approximate techniques;
- be able to design basic problem solving methods based on AI-based search, knowledge representation, reasoning, planning, and learning algorithms.
Recommended reading
The recommended text is:
* Russell, S. and Norvig, P. (2010). Artificial intelligence: a modern approach. Prentice Hall (3rd ed.).
There are many good books available on artificial intelligence; one alternative is:
Poole, D. L. and Mackworth, A. K. (2017). Artificial intelligence: foundations of computational agents. Cambridge University Press (2nd ed.).
For some of the material you might find it useful to consult more specialised texts, in particular:
Dechter, R. (2003). Constraint processing. Morgan Kaufmann.
Cawsey, A. (1998). The essence of artificial intelligence. Prentice Hall.
Ghallab, M., Nau, D. and Traverso, P. (2004). Automated planning: theory and practice. Morgan Kaufmann.
Bishop, C.M. (2006). Pattern recognition and machine learning. Springer.
Brachman, R.J and Levesque, H.J. (2004). Knowledge Representation and Reasoning. Morgan Kaufmann.