Transcript Lecture slides - Computer Science

Introduction to AI
&
AI Principles (Semester 1)
REVISION WEEK 1
(2008/09)
John Barnden
Professor of Artificial Intelligence
School of Computer Science
University of Birmingham, UK
TODAY (Tuesday)
 Nature of exam (refining the info given in Week 11)
 Review of material (extending the review in Week 11)
 Questions
 NB Office Hours:

Friday 1 May, 3:00-4:00

Friday 8 May, 4:00-5:00
Nature
of the Examination
Format of AI Principles Exam
 Three hours long.
 First half (1.5 hours): almost exactly the same as the Intro-AI
exam (see next slide).
 Second half: to be explained by Dean Petters in Revision Week 2.
 Use of material:

First half can be done on the basis entirely of my material.

Second half can be done on the basis entirely of Dean’s material.

But you’re free to use his material in my half or mine in his half as
appropriate.
Format of AI Intro Exam
One and a half hours long.
Do 5 out of 6 questions.
Most question parts: broadly similar in style to exercises
you did during Semester 1.
One question is essay-like and allows considerable
latitude as to what aspects of AI you address and what
material you bring to bear.
The rest are mostly on specific technical things, with a
couple of free-wheeling aspects here and there.
AI-Intro Material
 My own lecture material,
with some exclusions (see Week 11 part of Slides page)
 Answers / additional notes for Exercises.
 Andrea Arcuri’s lecture on learning, with some exclusions.
 Bullinaria slides (again with some exclusions):

Semantic Networks
(and my own notes on these slides)

Production Systems (and my own notes on these slides)

Expert Systems
 Textbook chapters (or chapter parts) in the Weekly Reading
Assignments on module webpage.
AI-Intro Material, contd
 Don't be spooked by previous examinations, especially those from
before 06-07!!
There have been a lot of changes. Also, quite a few since last year.
 Knowledge of textbook chapters or chapter parts other than those I've
listed ISN’T expected.
 Knowledge of Bullinaria slides other than those I point to from my list
of weekly lecture slides ISN’T expected.
 Knowledge of fine technical details in book chapters ISN’T expected.
(I’m only expecting the main concepts and overall grasp of main
examples.)
 But of course knowledge of all the above types could be helpful and
impressive.
REVIEW
of the material
Main Topics Covered
 Representation and reasoning, in



logic
production systems
semantic networks.
What we need to represent: entities (incl. situations, feelings, …),
properties, relationships, propositional structure, quantification, …
 Planning (a type of reasoning).
 Search.
 Natural Language difficulties as illustration of why AI is difficult.
 Knowledge and reasoning needed in natural language understanding
and operating in practical scenarios such as Hot Drinks and Shopping
Trip.
 Learning.
Main Detailed Techniques
Expressing information in logic.
Expressing information in semantic networks.
Applying production system rules (forwards or backwards,
but fine detail only expected in forwards case).
Doing simple logical proofs.
Search (fine detail not expected for best-first and A*).

Search as applied to route-finding.

Search as applied to planning delivery of a drink.
General Themes in AI
Why everyday AI is difficult.

Language processing, vision, planning, common-sense
reasoning, etc.
“Intelligence” and its connection to “stupidity”.

What looks like stupidity is often the understandably-incorrect
application of efficient heuristics (rules of thumb) without
which we and our AI cousins would be in a mess.
Contd. ……
General Themes in AI, contd.
Uncertain, vague, conflicting, missing, or diverse info.
Huge amounts of info, of varying relevance.
Hence: search, satisficing, graceful degradation, heuristics.
Context-sensitivity; incl. relativity to agents’ purposes (e.g.,
in vision and language interpretation).
Task variability, learning, adaptation, repair (e.g., of plans).
Declarative/procedural trade-off.
Goal-directedness (backwards chaining) in reasoning and
search.
A General Theme in AI
Uncertain, vague, conflicting, missing, diverse, extensive
info:

Amply shown by Hot Drinks, Shopping Trip and Crime
scenarios,
and by natural language examples.

Use of default rules and conflict resolution in PSs

Use of defaults and exceptions in SNs.

Contributes to need for search. Non-optimality (satisficing) in
(some) search.

Use of heuristics in search.

Need for learning.

Graceful degradation in (e.g.) neural networks.
A General Theme in AI
Search:

In planning (incl. route-finding, game-playing, …)

In deduction

In operation of Production Systems

In reasoning in Semantic Networks

In learning, particularly
genetic algorithms
automatically finding good weights for a neural network
General Theme: Heuristics
PS rules that leave out details and complications, and
that are at best DEFAULTS
Conflict resolution methods in PSs.
The information attached to actions in planning about
what changes (or doesn’t change) is typically defeasible.

On what doesn’t change: see the Planning 1 chapter in
Callan about the important frame problem.
In search in general:




Pruning
Action ordering in depth-first search
Evaluation functions in best-first search, incl.
Heuristic functions in A* search.
Choice of search strategy, incl. backwards vs. forwards.
Rough Sequence of Topics
Introduction:

what AI is

why we do it

how it differs from ordinary CS

application areas

expert versus everyday AI.
Topic Sequence contd: Challenge of AI
Introductory examples from language.

CAUTION CHILDREN

“John got to his front door but realized he didn’t have his key.”

Context-sensitivity of language; knowledge and reasoning
needed.
Knowledge and reasoning needed in Hot Drinks, Shopping
Trip and Crime scenarios.

Knowledge variety, uncertainty, vagueness, missing info, …
Vision and movement.

Context-sensitivity, purpose-sensitivity, ambiguity, …
Sequence of Topics, contd.
Detailed planning of delivery of one drink.

Search, forwards versus backwards chaining, goaldirectedness

Knowledge needed about preconditions and (non-)effects of
actions
Search: general nature, example applications.
Introduction to logic representation.
Reasoning about a static situation using Production
Systems.

CAUTION: different from planning, = reasoning about
moving between different possible situations.
Sequence of Topics, contd.
More on natural language difficulties.

vagueness

quantification subtleties

context-sensitivity

syntactic ambiguity, incl. PP attachment

some advanced topics: speech acts, mental states, metonymy,
metaphor
Sequence of Topics, contd.
Search detail (in route finding for Shopping Trip)

Different search strategies: depth-first, breadth-first, best-first,
A*

Optimality or otherwise

Ordering and pruning heuristics

Evaluation/heuristic functions.
Sequence of Topics, contd.
More on logic representation.
Logical deduction.

Inference rules in deduction versus production systems

Soundness

Fiddling around needed in deduction

Reduction of fiddling around by using Resolution

Reasoning by contradiction

Declarative/procedural trade-off.
Logical deduction versus using production systems.
Reasoning as search.
Sequence of Topics, contd.
Representation and reasoning in Semantic Networks

Localization of info at nodes

Different types of link

Taxonomy (instances and subtypes)

Defaults and exceptions

Intersection search
More on Production Systems.

Rule instantiations

Conflict resolution
Expert Systems
Sequence of Topics, contd.
Learning (Andrea Arcuri lecture in Week 9).

General characteristics

Neural Networks

Evolutionary Computation and Genetic Programming

Naïve Bayes Classifiers (not expected for exam)
Questions