Transcript Dr. Eick`s Introduction to AI

COSC 4368 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 4368 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 4368 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 4368 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 4368 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 4368 and ‘What is AI?”
5
Topics Covered in COSC 4368
• More general topics:
– search algorithm in general
– logical reasoning (FOPL as a language)
• AI-specific Topics:
– heuristic search
– machine learning
– resolution / theorem proving
– reasoning in uncertain environments
– expert systems
Christoph F. Eick: COSC 4368 and ‘What is AI?”
6
2008 Organization COSC 4368
I Introduction to AI (Luger 1.1. 1.2, 1.3; what is AI, subfields of AI)
II Heuristic Search (Luger chapters 3 and 4; additional transparencies)
III Machine Learning (Luger Chapters 10, 11, 12; additional
transparencies)
IV Automated Reasoning (Predicate Calculus(Luger Section 2.3ff),
Luger Chapter 13)
V Strong Method Problem Solving (Luger chapter 8)
VI AI Languages --- LISP and PROLOG (Luger Chapter 15 and 16)
VII Reasoning in Uncertain Environments (Luger Chapters 5 and 9)
VIII History of AI & Last Words
Christoph F. Eick: COSC 4368 and ‘What is AI?”
7
AI in General and What Is not
Covered in COSC 4368
• Robotics is a quite important sub-field of AI, but very
few teach it in the graduate AI class.
• Intelligent Agents and AI for the Internet could/should
possibly be covered in a little more depth.
• Techniques employed in systems that automate
decision making in uncertain environments deserves
more attention (e.g. belief networks, fuzzy logic, rulebased programming languages and expert system
shells, fuzzy controllers).
• Natural Language Understanding
• Knowledge Representation
• Planning
Christoph F. Eick: COSC 4368 and ‘What is AI?”
8
Course Elements
• 21 Lectures
• 3 Exams
• Programming projects and assignments (will start
beginning of February)
• Graded and un-graded Homeworks
Christoph F. Eick: COSC 4368 and ‘What is AI?”
9
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 4368 and ‘What is AI?”
10
AI Research Labs
• http://ai.stanford.edu/ (Stanford)
• http://www.cs.cmu.edu/~softagents/ (CMU)
• http://www.csail.mit.edu/index.php (MIT)
Christoph F. Eick: COSC 4368 and ‘What is AI?”
11
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 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 4368 and ‘What is AI?”
13
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 4368 and ‘What is AI?”
14
Planning
Objective: Construct a sequence of actions
that will achieve a goal.
Example: John want to buy a house
Christoph F. Eick: COSC 4368 and ‘What is AI?”
15
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 4368 and ‘What is AI?”
16
Figure
Christoph F. Eick: COSC 4368 and ‘What is AI?”
17
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 4368 and ‘What is AI?”
18
Logical Reasoning
• Learn how to represents natural language
statements in logic (AI as language)
• Automated theorem proving
• Foundation for PROLOG
Christoph F. Eick: COSC 4368 and ‘What is AI?”
19
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 4368 and ‘What is AI?”
20
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 4368 and ‘What is AI?”
21
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 4368 and ‘What is AI?”
Classification
Algorithms
Classifier
(Model)
IF rank = ‘professor’
OR years > 6
THEN tenured = ‘yes’
22
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 4368 and ‘What is AI?”
Tenured?
23
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 4368 and ‘What is AI?”
24
Data Mining and Machine Learning Group (UH-DMML)
Dr. Christoph F. Eick, Dr. Ricardo Vilalta, Dr. Carlos Ordonez
Transforming Tons of Data Into Knowledge
Students 2006-2007
Wei Ding
Rachana Parmar
Ulvi Celepcikay
Ji Yeon Choo
Chun-Sheng Chen
Abraham Bagherjeiran
Soumya Ghosh
Zhibo Chen Ocegueda-Hernandez, Fr.
Sashi Kumar
Dan Jiang
Rachsuda Jiamthapthaksin
Justin Thomas
Chaofan Sun
Vadeerat Rinsurongkawong
Jing Wang
Meikang Wu
Waree Rinsurongkawong