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