!
CMP2020M
ARTIFICIAL INTELLIGENCE
Marc Hanheide, Patrick Dickinson,
Bashir Al-Diri, Christian Dondrup
AI NEWS THIS WEEK
Professor Minsky, in 1959, co-founded the M.I.T. Ar tificial Intelligence Project (later the Artificial Intelligence Laboratory) with his colleague John McCarthy, who is credited with coining the term “artificial intelligence.”
http://www.nytimes.com/2016/01/26/business/mar vin-minsky-pioneer-in-ar tificial-intelligence-dies-at-88.html
AI NEWS THIS WEEK
https://googleblog.blogspot.co.uk/2016/01/alphago-machine-learning-game-go.html
!
http://lncn.eu/cmp2020m
AI QUIZ
AI QUIZ
‣ What is classical AI about?
A. The manipulation of symbols
B. Providing a physically plausible model of the brain
C. Developing models inspired by the neuronal system
D. Abstracting the world
E. Inferring new knowledge from given facts and rules
F. Search !
!
AI QUIZ
‣ What is needed to build a Knowledge-based System? A. Knowledge base
B. Interface
C. Machine Learning
D. Inference Engine E. Expert System
COMING…
Date of Lecture
Week
Topic
Lecturer for Friday Lecture
22/01/2016
1
Introduction
Marc Hanheide
29/01/2016
2
Knowledge Representations
Marc Hanheide
05/02/2016
3
Planning I
Marc Hanheide
12/02/2016
4
Planning II
Marc Hanheide
19/02/2016
5
Logic Programming
Bashir Al-Diri
26/02/2016
6
Logic Programming
Bashir Al-Diri
04/03/2016
7
Logic Programming
Bashir Al-Diri
11/03/2016
8
Games AI & Search
Patrick Dickinson
18/03/2016
9
Games AI & Search
Patrick Dickinson
25/03/2016
01/04/2016
08/04/2016
10
Games AI & Search
Patrick Dickinson
15/04/2016
11
Probabilistic AI
Christian Dondrup
22/04/2016
12
Probabilistic AI
Christian Dondrup
29/04/2016
13
Mock Exam
!
!
KNOWLEDGE REPRESENTATION
!
IBM’S WATSON
‣ Beat the best human players of
the gameshow Jeopardy
‣ Behind the scenes:
‣ Server park with 15 terabytes (=15,000GB) of RAM ‣ 200 million pages of data == knowledge base
‣ Developed by 4 computer scientists over 4 years
‣ Each possible solution is assigned a probability – if any answer’s probability reaches a threshold,Watson buzzes in..
!
WHAT IS KNOWLEDGE?
Versmold is a town in NRW NRW is a state in Germany towns are medium-size settlements
Marc is born in Versmold …
Versmold
86 101 114 115 109 111 108 100
!
WHAT IS KNOWLEDGE?
‣ “information in context, organised so that it can be readily applied to solving problems, perception and
learning” (Tanimoto, 1990)
‣ “understanding, awareness, or familiarity acquired through education or experience.The ability to use information” (Turban, 1992)
=> knowledge involves using information intelligently.To do this, knowledge must be efficiently organised and linked.
‣
!
SOME DIFFERENT KNOWLEDGE REPRESENTATION SCHEMES IN SYMBOLIC AI
‣ Logical representation schemes ‣ Facts and rules
‣ Procedural representation schemes ‣ Production systems
‣ Network representation schemes ‣ Semantic networks
‣ Structured representation schemes ‣ Frames, objects
!
LOGICAL REPRESENTATION SCHEMES
‣ Propositional logic (lecture 2)
‣ Predicate logic (lecture 3) – basis of the PROLOG
programming language (lecture 4)
‣ Emphasis on truth-preserving operations rather than the nature of human reasoning
!
NETWORK REPRESENTATION SCHEMES
‣ Associationist theories define the meaning of an object in terms of a network of associations with objects in a mind or knowledge base
‣ There is psychological evidence that humans also organize their knowledge hierarchically
‣ Collins and Quillian (1969) modelled human information storage and management using a semantic network
!
SEMANTIC NETWORKS
‣ The basic idea:
‣ The meaning of a concept is defined by its relationship to other concepts.
‣ A semantic network consists of a set of nodes that are connected by labeled arcs.
‣ Nodes represent concepts
‣ Arcs represent relations between concepts
‣ Inheritance is the main inference procedure
‣ Originally developed for natural language processing
!
Semantic network developed by Collins and Quillian
!
SEMANTIC NETWORKS
‣ Early semantic networks were vaguely defined
‣ e.g. the IS-A relationship could either mean “an instance of ” or “a subclass of ”
‣ Later versions support sub-class and instance relations ‣ Semantics using set theory:
‣ Class node – denotes a set of objects: e.g. elephant node refers to the set of all elephants
‣ Instance relationship – defined as set membership: e.g. Nellie is a member of the set of all elephants
‣ Subclass relationship – defined as a subset: e.g. the set of all elephants is a subset of all mammals
subclass
subclass
mammal
subclass
animal
Example semantic network with
subclass and instance relations
has-par t head
reptile
large
size instance
Nellie
colour grey instance
Clyde
elephant
!
apples
likes
CMP2020M: Lecture 5 – Knowledge Representation 1
!
CONVERSION TO PROLOG…
‣
‣
‣
‣
‣
‣
‣
‣
‣
instance(nellie, elephant).
instance(clyde, elephant).
subclass(elephant, mammal).
subclass(mammal, animal).
subclass(reptile, animal).
colour(elephant, grey).
size(elephant, large).
likes(nellie, apples).
haspart(mammal, head).
!
CONVERSION TO PROLOG…
‣ To represent the inheritance we need some rules: ‣ haspart(X, Part)
:- subclass(X,Y),haspart(Y,Part).
‣ colour(X, Col) :- instance(X, Y), colour(Y, Col).
‣size(X,S):- instance(X,Y),
size(Y,S).
‣ This is obviously not complete…
what’s missing?
!
ANOTHER EXAMPLE – CONCEPTNET
!
STRUCTURED REPRESENTATION SCHEMES
‣ Research has shown that humans organise information in broad conceptual structures and fill in particular details as needed
‣ For example, if somebody mentions “a wooden table” your brain will recall typical details, e.g:
‣ “Table” has four legs with a solid rectangular or circular top
‣ “Wood” is sturdy, brown, can be polished, etc.
‣ Frames were developed to mimic this human-like organisation of knowledge
‣ Inspiration behind object-oriented programming languages (though used for different things)
FRAMES
‣ Frame = data structure used to store all information relevant to a particular concept
‣ Slots – filled with specific instances of data (slot values)
‣ For example we could organise information about a wooden table as follows:
!
!
!
INFORMATION IN A FRAME
‣ Frame identification.
‣ Relationship to other frames.
‣ Descriptors of the requirements for frame match.
‣ e.g. chair has seat 20-40 cm from floor, back higher than 60cm, etc.
‣ Default information.
‣ e.g., assume chairs have 4 legs, unless told otherwise.
‣ New instance information.
RELATIONSHIP BETWEEN SEMANTIC NETS AND FRAMES
‣ Can represent similar information, e.g.
!
!
RELATIONSHIP BETWEEN SEMANTIC NETS AND FRAMES
!
INHERITANCE
‣ Allow a class to inherit properties of a superclass ‣ e.g. chimpanzee is a subclass of primate
‣ Economical representation of hierarchical knowledge ‣ Default values inherited from superclass
‣ Only need to specify exceptions at a lower level
‣ Type hierarchies:
‣ Trees – each type has only one supertype
‣ Lattice – support for multiple inheritance (need to handle conflicting default values)
!
INHERITANCE AND DEFAULT VALUES
* denotes a slot with a default value that can be over-ridden
DBPEDIA TOWARDS THE SEMANTIC WEB
‣ http://dbpedia.org/snorql/ ‣ Let play Watson!
‣ This famous physicist of the early 20th century was born in Ulm/Germany!
‣ Your answer? !
!
KNOWLEDGE ENGINEERING
‣ Where to get the knowledge from? ‣ The semantic web
‣ Wikipedia vs. Dbpedia
‣ Asking people, e.g. OMICS
‣ Learn through machine learning (hard!)
‣ How to represent it?
READING
‣ Luger, G.F., Ar tificial Intelligence – Structures and Strategies for Complex Problem Solving, 5th edition (Addison-Wesley, 2005).
‣ Chapter 7 (5th edition)
!
!
THANK YOU FOR LISTENING!