Transcript Main Areas of AI

COSC 6368 and “What is AI?”
1. Introduction to AI (today, and TH)
•
•
•
What is AI?
Sub-fields of AI
Problems investigated by AI research
2. Course Organization
3. Prerequisites, Schedules, Grading, General
Advice
Christoph F. Eick: COSC 6368 and ‘What is AI?”
1
Definitions of AI
• “AI centers on the simulation of intelligence using
computers”
• “AI develops programming paradigms, languages,
tools, and environments for application areas for which
conventional programming fails”
–
–
–
–
–
–
Symbolic programming (LISP)
Functional programming
Heuristic Programming
Logical Programming (PROLOG)
Rule-based Programming (Expert system shells)
Soft Computing (Belief network tools, fuzzy logic tool
boxes,…)
– Object-oriented programming (Smalltalk)
Christoph F. Eick: COSC 6368 and ‘What is AI?”
2
More Definitions of AI
• Rich/Knight: ”AI is the study of of how to make
computers do things which, at the moment, people
do better”
• Winston: “AI is the study of computations that
make it possible to perceive, reason, and act.
• Turing Test: If an artificial intelligent system is not
distinguishable from a human being, it is
definitely intelligent.
Christoph F. Eick: COSC 6368 and ‘What is AI?”
3
Physical Symbol System
Hypothesis
•
“What the brain does can be thought of at some
level as a kind of computation”
• Physical Symbol System Hypothesis (PSSH):
A physical symbol system has the sufficient and
necessary means for general, intelligent actions.
Remarks PSSH:
1.
2.
3.
Subjected to empirical validation
If false  AI is quite limited
Important for psychology and philosophy
Christoph F. Eick: COSC 6368 and ‘What is AI?”
4
Questions/Thoughts about AI
• What are the limitations of AI? Can computers only do what they are told?
Can computers be creative? Can computers think? What problems cannot be
solved by computers today?
• Computers show promise to control the current waste of energy and other
natural resources.
• Computer can work in environment that are unsuitable for human beings.
• If computers control everything --- who controls the computers?
• If computers are intelligent what civil rights should be given to computers?
• If computers can perform most of our work; what should the human beings
do?
• Only those things that can be represented in computers are important.
• It is fun to play with computers.
Christoph F. Eick: COSC 6368 and ‘What is AI?”
5
Topics Covered in COSC 6368
• More general topics:
– heuristic search and search algorithm in general
– logical reasoning (FOPL as a language)
– making sense out of data
• AI-specific Topics:
– resolution / theorem proving
– reasoning in uncertain environments and belief networks
– machine learning and data mining
– brief coverage of ontologies, evolutionary computing, AI and
the web, knowledge-based systems and philosophical aspects
of AI
– Exposure to AI tools (belief networks, decision trees,…)
Christoph F. Eick: COSC 6368 and ‘What is AI?”
6
2004 Organization COSC 6368
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Introduction AI and Course Information (1-2 classes)
Heuristic Search (3-4 classes)
Evolutionary Computing (1-2 classes)
FOPL, Logical Reasoning, PROLOG, and Resolution (4
classes)
Machine Learning and Data Mining (5 classes)
Ontologies, the Semantic Web and Intelligent Information
Retrieval (2 classes)
Belief Networks and Reasoning in Uncertain Environments (3
classes)
Knowledge-based Systems and Expert Systems (1 class)
General Aspects of AI (1 class)
Other Activities: Midterm exam (1 class), review (1 class),
group project (1 class), homework/project-related
discussions(1 class), paper walk-through (1 class).
Christoph F. Eick: COSC 6368 and ‘What is AI?”
7
AI in General and What Is not
Covered in COSC 6368
• Robotics is a quite important sub-field of AI, but very few
teach it in the graduate AI class.
• Planning and natural language understanding probably will not
be covered.
• Intelligent Agents and AI for the Internet could/should possibly
be covered in a little more depth.
• Artificial intelligence programming is not covered.
• Techniques employed in systems that automate decision
making in uncertain environments deserves more attention (e.g.
Fuzzy Logic, rule-based programming languages and expert
system shells, fuzzy controllers,
Christoph F. Eick: COSC 6368 and ‘What is AI?”
8
Positive Forces for AI
• Knowledge Discovery in Data and Data Mining (KDD)
• Intelligent Agents for WWW
• Robotics (Robot Soccer, Intelligent Driving, Robot
Waiters, industrial robots, rovers, toy robots…)
• Creating of Knowledge Bases and Sharing of Knowledge
(especially for Science and Engineering)
• Computer Chess and Computer Games --- AI for
Entertainment
Christoph F. Eick: COSC 6368 and ‘What is AI?”
9
UH Data Mining and Machine Learning Group
Lead by: Ricardo Vilalta and Christoph F. Eick
Topics investigated:
• Clustering for Classification
• Decision Trees / Nearest Neighbor Classifiers / Support Vector
Machines
• Theoretical Aspects of Classifiers and Classification Tasks
• Supervised Clustering
• Summary Generation
• Distance Function Learning
• Using Reinforcement Learning for Data Mining
• Making Sense of Data
• Database Clustering
• Feature Construction
• Meta-Learning
• Application of AI to Physics and Astronomy
Christoph F. Eick: COSC 6368 and ‘What is AI?”
10
Course Elements
• 22 Lectures
• 2 Exams (one Midterm, one Final Exam)
• 4 Graded Assignments (review questions, exam style
paper and pencil problems, a few more challenging
problems that might require programming; problems
that require using AI tools)
• Un-graded Homeworks (solutions will usually
discussed in class)
• 1 Paper Walk-Throughs
• Discussion of assignments and homeworks
Christoph F. Eick: COSC 6368 and ‘What is AI?”
11
Teaching 6368 in 2004 --what changed since 2002?
• The second edition of the Russel/Norvig book
came out in November 2002 (update of
teaching material; better transparencies)
• Some 2002 teaching material will be replaced
by other teaching material
• A lot more AI technique animations are
available now --- I will try to use some of those
for teaching purposes
• There will be some changes what will be
covered in 2004 (see webpage)
Christoph F. Eick: COSC 6368 and ‘What is AI?”
12
Knowledge Representation
AI Programming
Knowledge-based
and Expert Systems
Planning
Coping with Vague,
Incomplete and
Uncertain Knowledge
Logical Reasoning
& Theorem Proving
Searching
Intelligently
AI
Intelligent Agents
& Distributed AI
Learning & Knowledge Discovery
Communicating,
Perceiving and
Acting
Knowledge Representation
Problem: Can the above chess board be coverer by 31 domino pieces
that cover 2 fields?
AI’s contribution: object-oriented and frame-based systems, ontology
languages, logical knowledge representation frameworks, belief networks
Christoph F. Eick: COSC 6368 and ‘What is AI?”
14
Natural Language Understanding
• I saw the Golden Gate Bridge flying to San
Francisco.
• I ate dinner with a friend. I ate dinner with a
fork.
• John went to a restaurant. He ordered a
steak. After an hour John left happily.
• I went to three dentists this morning.
Christoph F. Eick: COSC 6368 and ‘What is AI?”
15
Planning
Objective: Construct a sequence of actions
that will achieve a goal.
Example: John want to buy a house
Christoph F. Eick: COSC 6368 and ‘What is AI?”
16
Heuristic Search
• Heuristo (greek): I find
• Copes with problems for which it is not feasible to
look at all solutions
• Heuristics: rules a thumb (help you to explore the
more promising solutions first), based on
experience, frequently fuzzy
• Main ideas of heuristics: search space reduction,
ordering solutions intelligently, simplifications of
computations
Example problems: puzzles, traveling salesman problem, …
Christoph F. Eick: COSC 6368 and ‘What is AI?”
17
Figure
Christoph F. Eick: COSC 6368 and ‘What is AI?”
18
Evolutionary Computing
• Evolutionary algorithms are global search techniques.
• They are built on Darwin’s theory of evolution by natural
selection.
• Numerous potential solutions are encoded in structures,
called chromosomes.
• During each iteration, the EA evaluates solutions adn
generates offspring based on the fitness of each solution in
the task.
• Substructures, or genes, of the solutions are then modified
through genetic operators such as mutation or
recombination.
• The idea: structures that led to good solutions in previous
evaluations can be mutated or combined to form even better
solutions.
Christoph F. Eick: COSC 6368 and ‘What is AI?”
19
Logical Reasoning
• Learn how to represents natural language
statements in logic (AI as language)
• Automated theorem proving
Christoph F. Eick: COSC 6368 and ‘What is AI?”
20
Soft Computing
Conventional Programming:
• Relies on two-valued logic
• Mostly uses a symbolic (non-numerical knowledge
representation framework)
Soft Computing (e.g. Fuzzy Logic, Belief Networks,..):
• Tolerance for uncertainty and imprecision
• Uses weights, probabilities, possibilities
• Strongly relies on numeric approximation and interpolation
Remark: There seem to be two worlds in computer science; one
views the world as consisting of numbers; the other views the
world as consisting of symbols.
Christoph F. Eick: COSC 6368 and ‘What is AI?”
21
Different Forms of Learning
• Learning agent receives feedback with
respect to its actions (e.g. using a teacher)
– Supervised Learning: feedback is received
with respect to all possible actions of the agent
– Reinforcement Learning: feedback is only
received with respect to the taken action of the
agent
• Unsupervised Learning: Learning without
feedback
Christoph F. Eick: COSC 6368 and ‘What is AI?”
22
Machine Learning ClassificationModel Construction (1)
Training
Data
NAME
M ike
M ary
B ill
Jim
D ave
Anne
RANK
YEARS TENURED
A ssistan t P ro f
3
no
A ssistan t P ro f
7
yes
P ro fesso r
2
yes
A sso ciate P ro f
7
yes
A ssistan t P ro f
6
no
A sso ciate P ro f
3
no
Christoph F. Eick: COSC 6368 and ‘What is AI?”
Classification
Algorithms
Classifier
(Model)
IF rank = ‘professor’
OR years > 6
THEN tenured = ‘yes’
23
Classification Process (2): Use
the Model in Prediction
Classifier
Testing
Data
Unseen Data
(Jeff, Professor, 4)
NAME
Tom
M erlisa
G eo rg e
Jo sep h
RANK
YEARS TENURED
A ssistan t P ro f
2
no
A sso ciate P ro f
7
no
P ro fesso r
5
yes
A ssistan t P ro f
7
yes
Christoph F. Eick: COSC 6368 and ‘What is AI?”
Tenured?
24
Knowledge Discovery in Data [and Data Mining] (KDD)
Let us find something interesting!
• Definition := “KDD is the non-trivial process of
identifying valid, novel, potentially useful, and
ultimately understandable patterns in data”
(Fayyad)
Christoph F. Eick: COSC 6368 and ‘What is AI?”
25
2004 Organization COSC 6368
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Introduction AI and Course Information (1-2 classes)
Heuristic Search (3-4 classes)
Evolutionary Computing (1-2 classes)
FOPL, Logical Reasoning, PROLOG, and Resolution (4
classes)
Machine Learning and Data Mining (5 classes)
Ontologies, the Semantic Web and Intelligent Information
Retrieval (2 classes)
Belief Networks and Reasoning in Uncertain Environments (3
classes)
Knowledge-based Systems and Expert Systems (1 class)
General Aspects of AI (1 class)
Other Activities: Midterm exam (1 class), review (1 class),
group project (1 class), homework/project-related
discussions(1 class), paper walk-through (1 class).
Christoph F. Eick: COSC 6368 and ‘What is AI?”
26