CS245 - CS II Chapter 11 - Artificial Intelligence

11.1 What is intelligence--artificial or not?

Thinking About Thinking Machines

"What is intelligence?"

Can Machines Think? - Turing Test

Machines Versus Humans
"It is not possible for a machine to think."
"Computers can only deal with zeros and ones"
"Only natural things like people and animals can have intelligence"
Performance Versus Simulation
mathematician - concern with performance
psychologist - concerned with understanding the processes of natural intelligence (simulation oriented)
"Is intelligence measured by the ability to win or the ability to be humanlike?"

1. Differences in size. The brain has a million more pieces than even a supercomputer.

2. Differences in structural organization. Random structure of nerve networks vs. Precise wiring of a computer.

3. Differences in reliability. Brain can operating for decades without serious malfunctioning.

4. Differences in logical organization. Brain is self-oganizing, can adapt to a variety of situations, has remarkable memory classification and access features.

5. Differences in input-ouput equipment.

Claud Shannon's five comparisons between the human brain and the computer

Intelligence as an Interior Characteristic
Turing Test
DOCTOR (Eliza / Dr. Sbaitso) - Rogerian Psychology

An "Intelligent Machine

consists of a gripper, video camera & a rubber finger to solve Rubik's cube
What is Artificial Intelligence?
"Artificial intelligence is the study of ideas which enable computers to do the things that make people seem intelligent." Patrick Henry Winston
"Artificial intelligence is the study of how to make computers do things at which, at the moment, people are better." Elaine Rich
"Artificial intelligence is the study of the computations that make it possible to perceive, reason, and act." Patrick Henry Winston
"Computers are very powerful, but very dumb.
Artificial intelligence just makes them less dumb." An Wang

Artificial Intelligence

Expert Systems
Robotics
Natural Language Processing
Voice Recognition
Voice Synthesis
Computer Vision
Fuzzy Logic
Neural Networks - self teaching

11.2 Fundmental Concepts in Artificial Intelligence

Modeling the Human Knowledge System

semantic networks - designed after the psychological model of the human associative memory
consists of objects, concepts, or situations connected by some type of relationship

(JOHN) 	isa 	(PLUMBER) 	isa 	(WORKER)
     |
 owner
    |
(OWN-1) 	ownee 	(FORD) 	isa 	(CAR) 
  |    |      |
  isa   |    - start-time 	(MAY 92) 	isa 	(TIME)
  |       - end-time 		(SEPT 93)  isa  ------------
  |
(OWNERSHIP) 	isa 	(SITUATION)

frames and scripts - attempts to create descriptions of objects or events in the environment which pertains to the knowledge in question. Scripts describe activities involving the knowledge in question, and also supply possible outcomes and scenarios.

Production Systems

production systems - better known as expert or rule-based systems are knowledge bases consisting of hundreds or thousands of IF (condition) THEN (action) rules.

collection of states: state - situation that might occur in the application environment (start state and goal state)
collection of productions - production - operation that transforms one state into another
control system - logic that solves the problem of moving from the start state to the goal state

Production rule: IF (it is raining AND you must go outside)
THEN (put on your raincoat)

solving the problem
Rubik's cube has over 180,000 different configurations

knowledge acquisition Putting information or knowledge into the system.

knowledge retrieval Finding the knowledge when it is needed.

reasoning Use the knowledge.

Knowledge Acquisition

chair - a piece of furniture consisting of a seat, legs and back, and often arms, designed for one person.
Knowledge Retrieval
Search Trees

root - start state & children of a node are those states reachable by applying a production
Problems of Efficiency

could be a lot of branches
1) depth-first search method vs. than breadth-first method
2) avoid redundancy to reduce size of tree (can assign a cost function to determine which redundancy to eliminate)
Brute Force Search
Heuristic Systems

heuristics (rules of thumb) - used to limit the number of items that must be searched in solving a problem

How to determine which option to pursue?

heuristic - quantitative measure by which a program can determine which of several states is considered closer to the goal

ex. Number of tiles out of position (how far out of position?)
Applying Heuristics - requires algorithms
Reasoning: shallow (based on heuristics or rule-based knowledge) and deep (deals with models of the problem obtained from analyzing the structure and function of the problem)

Learning Systems

Rote Learning - memorization
Learning by Instruction - student/teacher relationship
Learning by Deduction - drawing conclusions from certain premises
Learning by Induction
1. learning by example
2. learning by experimentation
3. learning by observation
4. learning by discovery
Learning by Analogy - combines deductive and inductive learning

Common Sense Reasoning

requires a knowledge base of about 100,000,000 axioms

11.3 Pattern Recognition

identifying recurring patterns in input data with the goal of understanding or categorizing that input

Speech/Voice Recognition
Fingerprint identification
Face identification
Handwriting identification
Optical Character Recognition (OCR)
Biological slide analysis
High-energy physics analysis
Meteorological data analysis
Surveillance satellite data reduction
Robot vision

Image Analysis - process of identifying objects & shapes

colorizing movies, piloting cruise missles
Optical Character Recognition (OCR)
POS devices, mail sorting, scanners
handwriting recognition (Pentop computers)
Automatic Speech Recognition
digitized voice - speaker independence, limited vocabulary, continuous speech
Talking Computers
speech synthesis
digitized speech and sound

Recognizing Printed Letters - position, orientation, fonts and styles

OCR - OmniPage
Three Dimensional Vision
Speech-Pattern Recognition

He walked to the store.
He walked to this door.

This issue revolves around a rather significant quotable quote on finding patterns.
The quote is from "Fluid Concepts & Creative Analogies," a book by Douglas R. Hofstadter and the Fluid Analogies Research Group (Basic Books, 1995) ISBN: 0465051545 (hardcover) ISBN: 0465024750 (paperback).
"Then there is what might be called 'pattern sensitivity,' which involves such activities as:
- noticing sameness... (e.g., one thing equals another)
- noticing simple relationships... (e.g., one thing follows after another)
- noticing analogies (e.g., this little pattern-fragment looks like that one)
- imposing consistency (e.g., let me alter this pattern-fragment so it looks more like that one)
- building abstractions (e.g., this shared pattern-fragment can be summarized in a template)
- shifting boundaries (e.g., this might better be grouped with this rather than with that)
- driving towards beauty (e.g., let me alter this pattern-fragment because it would be more balanced that way) and many others."

"Pattern perception, extrapolation, and generalization are the true crux of creativity."

11.4 Game Playing

X	X	X

O	O	O

HEXAPAWN GAME

If an opponent is diagonally opposite any of your pawns, then take the opponent's piece.
If any move results in winning, then make that move.

11.5 Natural Language Communication

The bark was irritating!

Machine Translation Traps (automatic translation using parsing programs)
"The spirit is willing, but the flesh is weak" --> "The wine is agreeable, but the meat is rotten"
"out of sight, out of mind" --> "blind and insane" or "invisible idiot"
Nonsense and Common Sense

syntax - set of rules for constructing sentences from words
semantics - underlying meaning of words and phrases (context)
translating from one language to another: requires parsing, semantic analysis & contextual analysis

ex. Do you know what time it is?
ex. Stampeding cattle can be dangerous.

ELIZA

11.6 Expert Systems

Expert system (Knowledge base system) - collection of if-then rules
data -> information -> knowledge

knowledge base - facts & system for determining & changing relationships between facts
Artificial Experts

expert system - software designed to replicate the decision making process of a human expert

knowledge engineer - specialist who interviews and observes experts and converts their "knowledge" into a knowledge base

MYCIN - prescribed treatment for infectious diseases
PROSPECTOR - analyzed geological information obtained from field observations
AMEX - credit checks
XCON - automatically determined optimal configurations of VAX computers according to customer needs and available options (over 4000 rules)
AARON - automated artist for drawing human figures
grammar checkers
MOLGEN - program that assists a molecular geneticist in planning scientific experiments (Stanford - 1979)
ACRONYM - locates objects in a picture (Stanford - 1981)
language translation programs
DISTRESS - diagnose emergency care patients in Malaysia

Expert systems

help train new employees
reduce number of human errors
take care of routine tasks
provide expertise when no experts are available
preserve knowledge of experts
combine knowledge of several experts
make knowledge available to more people

Expert system shells

The Expert System Shell: domain-independent software; components of an expert system shell; knowledge acquisition facility; knowledge engineer; domain expert; factual knowledge; rule; knowledge base; inference engine; user interface.

Structure of an Expert System
knowledge base (set of rules)

IF (it's raining outside) THEN (get an umbrella)
IF (getting an umbrella) THEN (go to umbrella rack)

inference engine (rule intepreter)

11.7 Neural Networks

Model of a Neural Network
neuron in the brain can receive 100,000 - 200,000 input signals from other neurons

Artificial neurons (processing elements) are modeled after real neurons with many weighted inputs and outputs

constructed from many individual processors (units) that models networks of neurons in living biological systems
neural network - collection of neurons which are interconnected. The output on one connects to others with different weights.

Training a Neural Network

output = 	1 if (vi * wi) > threashhold value 
		0 otherwise

where v's are inputs and w's are weights
example: destinquishing the difference between letter C and T
supervised training - use output from input data to modify weights

Neural Networks in Action
ex. Mortgage Risk Evaluator - increased profits of financial institution by 27%
SNOOPE - detects plastic explosives in luggage (costs $1.1 mill. And requires > 2.5 lbs of explosives)

11.8 Artificial Life

Artificial life (a-life) - phenomena in computers that have attributes of life.

Are computer viruses an example of a-life?

Complex Adaptive Systems

nonlinear systems that require a computer
parallel not serial
evolutionary rather than natural selection
emergent bahaviour (unpredictable)
contains simple rules
self-organizing

Chaos

The Genetic Algorithm

genetic algorithm (simulated evolution) - searching method based on genetics and evolution including mutations, crossover, and chromosomes

Controlling a gas pipeline
develop Kepler's 3rd Law (cube of planet's distance from the sun is proportional to the square of its period)

A-Life Goals and the Future

"Artificial life is a way of exploring how complex systems can exhibit self-organization, adaptation, evolution, co-evolution, metabolism, all sorts of stuff. It is a mimic of biology, although biologists don't know it yet. Out of it will emerge some sort of strange companion theory to biology...a particular substation of how living things works. This emerging discipline may be getting at what the logical structure is for living things." [Stuart Kauffman]

The Robot Revolution

What is a Robot?

robota - forced labor
robot - computer-controlled machine designed to perform specific manual tasks
input: vision, auditory, touch, heat, external control sensors
output: mechanical motion, voice

Advantages - save labor costs, improve quality and increase production, hazardous / uncomfortable jobs

Asimov's Laws of Robotics

(DEFUN SHRINK () ; Simple Rogerian therapist simulation
(PROG ()
(SETQ WWORDCOUNT 0)
(SETQ PUTCOUNT 0)
(PRINTM WELCOME TO MY SOFA)
LOOP (SETQ S (YOUMEMAP (READ)))
(COND
; the production rules follow
((MATCH ' (BYE) S)
(RETURN 'GOODBYE))
((MATCH '(YOU ARE (* X)) S)
(PRINTL (APPEND '(PLEASE TELL ME)
(LIST (WWORD))
'(YOU ARE)
X)))
((MATCH '(YOU HAVE (* X) S)
(PRINTL (APPEND '(HOW LONG HAVE YOU HAD) X)) )
((MATCH '(YOU FEEL (* X) S)
(PRINTM I SOMETIMES FEEL THE SAME WAY)
((MATCH '(BECAUSE (* X) S)
(PRINTM IS THAT REALLY THE REASON )
((MATCH '(YES (* X) S)
(PRINTL (APPEND '(HOW CAN YOU BE SO SURE) X)))
((MATCH '(ME ARE (* X) S)
(PRINTL (APPEND '(OH YEAH I AM ) X)) )
((MATCH NIL S)
(PRINTM PLEASE SAY SOMETHING)
:
:
(T (SETQ PUNTCOUNT (ADD1 PUNTCOUNT))
(COND ((EQUAL PUNTCOUNT 7)
(SETQ PUNTCOUNT 0)))
(PRINTL (GETNTH PUNTCOUNT PUNTS)) ) )
(GO LOOP) ) )

(SETQ PUNTS
'((PLEASE GO ON)
(TELL ME MORE)
(I SEE)
(WHAT DOES THAT INDICATE)
(BUT WHY BE CONCERNED ABOUT IT)
(JUST TELL ME HOW YOU FEEL) )

Exercises

pp. 319: #1, #5, #10
Do Lab 13: What can a computer do and not do? An introduction to AI at http://csc.ColumbusState.edu/summers/notes/CS101/Lab13.htm
E-mail journal due March 7 - general AI,
March 14 - Expert Systems,
March 28 - Neural Networks

knowledge acquisition	Putting information or knowledge into the system.
knowledge retrieval	Finding the knowledge when it is needed.
reasoning	Use the knowledge.