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 Information
Christoph F. Eick: COSC 6368 and ‘What is AI?”
1
Part1a: 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 planning, evolutionary computing,
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
2009 Organization COSC 6368
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Introduction AI and Course Information (1-2 classes)
Heuristic Search (4-5 classes)
Evolutionary Computing (2 classes)
FOPL, Logical Reasoning, Resolution, and PROLOG (3-4
classes)
Inductive Learning, Reinforcement Learning, Brief Introduction
to Data Mining (4 classes)
Knowledge-based Systems and Expert Systems (1 class)
Planning (1-2 classes)
Ontologies and Philosophical Aspects of AI (1-2 classes)
Belief Networks and Reasoning in Uncertain Environments (34 classes)
Other Activities: midterm exam (1 class), review (2 classes),
homework/project-related discussions(1 class), possibly 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.
• 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 in General --- AI
for Entertainment
Christoph F. Eick: COSC 6368 and ‘What is AI?”
9
6368 Homepage
• http://www2.cs.uh.edu/~ceick/6368.html
IJCAI 2009 Homepage
http://ijcai-09.org/
Christoph F. Eick: COSC 6368 and ‘What is AI?”
10
Course Elements
• 21 Lectures
• 3 Exams (two midterms, 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; searching for something and reporting)
• Un-graded Homeworks (solutions will usually discussed in
class)
• 1 Paper Walk-Throughs (group activity) if class size <20
• Discussion of assignments and home works
• We will try to use more demos and animations --- we have
to see if this turns out to be useful
Christoph F. Eick: COSC 6368 and ‘What is AI?”
11
Knowledge Representation
AI Programming
Knowledge-based
and Expert Systems
Part1b:
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
Part1b: Examples of Problems
Investigated by Different
Subfields of AI
Christoph F. Eick: COSC 6368 and ‘What is AI?”
13
Knowledge Representation
Problem: Can the above chess board be cover 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
• Foundation for PROLOG
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/Learning from
Examples/Inductive 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
2. General Course Information
Course Id:
COSC 6368 Machine Learning
Time:
TU/TH 1-2:30
Instructor:
Christoph F. Eick
Classroom:
232 PGH
E-mail:
[email protected]
Homepage:
http://www2.cs.uh.edu/~ceick/
Christoph F. Eick: COSC 6368 and ‘What is AI?”
Prerequisites
Background
• Algorithms
– basic data structures, complexity…
• Sound programming skills (no knowledge of LISP or PROLOG
is requred)
• Ability to deal with “abstract mathematical concepts”
• Basic knowledge of logic would be helpful
Christoph F. Eick: COSC 6368 and ‘What is AI?”
Textbook
http://aima.cs.berkeley.edu/
Christoph F. Eick: COSC 6368 and ‘What is AI?”
Grading
2 Exams
4 Assignment
60%
40%
Remark: Weights are subject to change
NOTE: PLAGIARISM IS NOT TOLERATED.
Christoph F. Eick: COSC 6368 and ‘What is AI?”
Tentative 2009 Teaching Plan (Subject To Change)
Week
Topic
Jan 20
Introduction / Search
Jan 27
Search
Feb. 3
Search/Evolutionary Computing (EC)
Feb. 10
EC, Logical Reasoning (LR)
Feb. 17
LR
Feb. 24
LR/Learning from Examples(LFE)
March 3
LFE/Reinforcement Learning
March 10
Review,/Midterm Exam
March 24
Leftovers/Knowledge-based Systems
March 31
Ontologies/ Philosophical Foundations of AI
April 7
Planning
April 14
Reasoning in Uncertain Environments (RIE)
April 21
RIE
April 28
RIE/Review for Final Exam
Remark: Topics in brown color may be skipped or replaced by something else
Christoph F. Eick: COSC 6368 and ‘What is AI?”
Dates to Remember
Dates to remember
Events
Last day before Spring Break;
May 12
Exams
March 17 /19
No class (Spring Break)
Christoph F. Eick: COSC 6368 and ‘What is AI?”
Exams
 Will be open notes/textbook
 Will get a review list before the exam
 Exams will center (80% or more) on material that was covered in the
lecture
 Exam scores will be immediately converted into number grades
A few sample exams are available
Christoph F. Eick: COSC 6368 and ‘What is AI?”
Other UH-CS Courses with Overlapping Contents
•
•
•
COSC 6342: Machine Learning
• Strong Overlap: Decision Trees, Bayesian Belief Networks,
Learning from Examples in general
• Medium Overlap: Reinforcement Learning
COSC 6335: Data Mining
• Overlap: Decision trees, Learning from Examples in general
• Preprocessing/Exploratory DA, AdaBoost
COSC 6367: Evolutionary Computing
• Overlap: Search
• We also will have 2 lectures on Evolutionary Computing
Christoph F. Eick: COSC 6368 and ‘What is AI?”