###
CSC 550: Introduction to Artificial Intelligence

Spring 2004

Course Overview

Introduction/History
history of AI, Turing Test
philosophical extremes: neats vs. scruffies, GOFAI vs. emergent, strong vs. weak
GOFAI approach: problem solving = knowledge representation + search
Scheme and AI programming
S-expressions (atoms & lists), functional expressions
primitive functions: + - = equal? car cdr cons list length member ...
special forms: if cond let begin set! read display
full recursion vs. tail-recursion
AI programming examples
Eliza: knowledge representation, pattern-matching
automated deduction: predicate calculus, logic programming
AI as Search
state spaces
solve problem by defining states, specifying transitions, searching
control strategies
bold + uninformed: STUPID
tentative + uninformed: breadth-first, depth-first, iterative deepening
bold + informed: hill-climbing
tentative + informed: best-first
optimization problems
algorithm A, admissibility, algorithm A*
game playing
Minimax Theorem, game trees, minimax search, alpha-beta pruning
Knowledge Representation and AI
representation schemes:
logical (state spaces)
network (semantic nets, conceptual dependencies)
structured (frames, scripts)
procedural (expert systems) schemes
semantic nets
graphical representation, info retrieval as graph search, inheritance
conceptual dependency representation
defined richer set of links for networks, stores underlying concepts
frames
slot-filler model, inheritance, defaults, constraints, procedures
scripts
frame structure for representing events, utilized conceptual dependencies
expert systems
common characteristics
expert-level performance, domain specific, explanation, uncertainty, ...
layout: user interface, inference engine, knowledge base, case-specific data
rule application: depth vs. breadth, best vs. all, forward vs. backward, ...
uncertainty: probabilities, certainty factors, fuzzy logic, ...
alternatives to rule-based: case-based reasoning, model-based reasoning
Connectionist Models
based on brain metaphor
characteristics: distributed, parallel, sub-symbolic
application areas: pattern classification, prediction, control & optimization
central problems: learning, architecture, scaling, generalization
perceptron
simple model of neuron as processing unit (inputs, weights, output)
Perceptron Learning Algorithm, convergence theorem, linear separability
backpropogation nets
multi-layer, continuous activation function
generally effective (but not guaranteed) learning algorithm
Hopfield nets
associative memory, parallel relaxation
Emergent Models
based on evolution metaphor
genetic algorithms
biology analogies: chromosome, reproduction, mutation, natural selection
idea: start with population of random solutions, evolve better ones
application areas: NP-hard problems, scheduling, data mining
artificial life
study of man-made, lifelike organisms and systems
idea: model complex systems with interacting finite automata
cellular automata, Game of Life, artificial creatures, evolution
Student Presentations
Bioinformatics
Computer Chess
Natural Language Understanding