Karteikarten
CS 580 - Intro to AI
Karten in diesem Stapel (123)
- 1What Is AI?The study of human intelligence via computer
models.
– The study of man-made computational
intelligence.
– The study of the architecture of intelligent
systems.
– The study of “user-friendly” systems. - 2Traditional AIIntelligence = ability to solve problems
- 3Traditional AIGoal Directed Symbol Manipulation
- 4General Problem Solver ExamplesGame playing
• Theorem proving
• Medical diagnosis
• Traveling from A to B
• Solving puzzles:
– Sudoku, logic, crossword, … - 5General Problem Solving ProcessGiven:
– Symbol set, operators
– Initial state, goal state
• Find:
– Sequence of operations that transform the
initial state into the goal state - 6General Problem Solving StrategyDevelop knowledge-intensive
techniques for efficiently constructing
the required problem-solving
sequences. - 7Game PlayingBoard is current state
Legal Moves are symbols
Start with Initial state
Well understood goal state - 8Game Trees
- 9Game Playing Problem SpaceChess: 10^120 board configs
Table Lookup/exhaustive search not feasible - 10Knowledge Directed SearchSTatic Eval Functions
Dynamic Look Ahead
Tree Pruning Heuristics - 11Chess StatusVery Strong Programs
Higher Level Concepts Missing
Brute Force Works - 6-8 levels look-ahead - 12AI Paradigm1. Identify problem humans solve
2. analyze activities
3. build a conceptual model
4. build a computational model
5. Implement
6. Simulate(Execute)
7. Revise - 13Knowledge Representation IssuesKnowledge:
1 Large/unwieldy
2 Difficult to Articulate
3 Inexact/Incorrect
4 Changes - 14Knowledge Representation Key FactorsMust Be:
1 Effecient
2 Useful
3 Support reasoning/generalization
4 Facilitate Acquisition
5. Understandable by humans - 15KR ApproachesNatural Language
Formal Logic
Production Rules
Semantic Nets
Frames, Scripts - 16AI SubdomainsNL Understanding
Scene Understanding
Multi-Sensor Integration
Robotics
Expert Systems
Machine Learning
... - 17Modern AI Perspective1 Agent Oriented
2 Sensors/Effectors - environmental interaction
3 open ended problem solving - 18AgentsEmbodied Intelligence
Sense-Think-Act
Meta Cognition - 19Common Threads1 Signal->Symbol 2Mapping
3 General Purpose vs Specialized systems
4 Knowledge Representation
5 Knowledge Acquisition
6 Learning - 20Turing TestImitation Game
Interrogator tries to figure out which is human, A or B, via conversation - 21Weak AIStudy of algorithms which enable computers to do tasks which previously only humans could perform
- 22Strong AIPursuit of research leading to the development of facsimiles of the human mind
- 23Major Areas of AIOptimization
Induction
Deduction
Interaction - 24AI Area: OptimizationProcess of wandering through an environment, hunting for samples which have the highest quality.
- 25AI Area: Stochastic OptimizationMetaheuristics - genetic algorithm, simulated annealing, ant colony optimization
- 26LISPSymbol Manipulation
Fundamental Data Objects - 27LISP: Symbols1 Manipulated as data
2 Fundamental distinction: Symbol names vs values
X, `X, "X" - 28LISP: Symbolic ExpressionsFormed from atomic elements and/or s expressions
Lists - (a (b c) d) - 29LISP: Underlying Representation1-way linked list of CONS cells with CAR, CDR fields
(a (b c) d) - 30LISP: list constructioncons, list, append
(setf L (cons a b))
(setf L (list 'a 'b)) - 31LISP: list traversalcar, cdr, caar, cadr
(print (car L)) - 32LISP - list manipulationShared, non-desctructive
- 33LISP functionsassume CAR specifies a function and CDR its arguments
- 34LISP Programcollection of s expressions to be manipulated or evaluated
- 35LISP control flowIF, COND, LOOP, DOLIST, DOTIMES, PROG, MAP
- 36LISP REPLread evaluate print loop
(loop (print (eval (read))) - 37AI GoalDevelop Knowledge Intensive techniques for efficiently constructing the required problem-solving sequences
"Heuristics" - 38Cognitive ApproachBuild a computational mode of human problem solving
- 39CS/Engineering ApproachBuild a computationally efficient problem solver
(not necessarily modeling human behavior/preference) - 40State Space Search Initial State:1. Root Node(of tree/graph)
2. Intermediate Nodes(partial solutions)
3. Leaf Nodes(solutions) - 41State Space Search Goal Statestopping condition. eg Tour of minimal cost in TSP
- 42State Space Search GeneratorDepth First
Breadth First - 43State Space Search TSPInitial State:
1 visited city
N-1 unvisited
Goal State:
Tour of minimal cost
Generator: Depth first by city - 44State Space Search TSP ProblemsSize of space:
(N-1)! leaf nodes
>(N-1)! interior nodes
Measuring efficiency:
nodes visited
Heuristics:
1 Closed Neighbor next(greedy)
2 No-overlapping paths - 45State Space Search Boolean SatInitial State:
N boolean variables unassigned
Goal State:
Entire expression evals to true
Generator:
Depth first by variable - 46General Search StrategiesData Driven vs Goal Directed
Uninformed vs Informed
Admissible vs Inadmissible Heuristics - 47Uninformed Search ExamplesDepth First
Breadth First
Depth Limited
Iterative Deepening
Breadth limited
bidirectional - 48Search: Informed Examplesw/ Static eval function
Hill Climbing
Greedy
Prioritized depth first
Prioritized breadth first
Best first - 49Search: Informed Examplesw/ a future cost estimator
A* - 50A*Total Est Cost = current cost + heuristic estimate
Keep "best so far" cost
prune if est.clost > bsf cost
Admissible if never overestimates future costs - 51Search: Informed ExamplesConstraint Violoation
Assumes constraints
Admissible
Efficiency
Constraint Issues - 52Search: Informed Look AheadSimulate Future Possibilities
extract useful information
make choices, via pruning - 53Special Search: Adversarial Gamesw/ Lookahead capability
goal:
1. Sim Future Poss
2. Extract Useful Info
3. Make choices, prune:
Minimax Algs
Alpha/Beta pruning - 54Game Tree
- 55MinimaxAssume symmetric static eval function
Max values, good for me
Min Values, bad for me
Opponent always chooses optmial min
Exhaustive search to fixed path - 56State Space ApproachGenerate & test with pruning
- 57Solution State SearchMove around in solution space rather than constructing solutions incrementally
- 58Solution Space search TSPSolution Space: All permutations
Move from one perm to another via
2 city swap
Segment inversion - 59Solution Space Search HeuristicsHill Climbing/descent
Greedy Ascent/Descent
Gradient ascent/descent - 60Special Search Natural ComputationSimulated Annealing
Evolutionary Computation
Ant Colony Optimization - 61Special Search: Natural Search: Simulated AnnealingEnergy levels <==> random jumps
initial "temperature high"
cool slowly - 62Special Search Natural Computation Evolutionary ComputationSimulate Darwinian Evolution
Survival of the fittest
Parental fitness -> offspring
Offspring inheritance - 63Special Search Natural Logic Ant Colony OptimizationDistributed problem solving
Initially parallel random search
Pheremone trails - 64Datadrive vs Goal DirectedForward Chaining vs backward chaining
- 65General Search Uninformed vs InformedBlind vs knowledge guided
- 66General Search Admissible vs InadmissibleProvably correct vs generally correct
- 67Uninformed Search Breadth Firstall nodes at each level expanded before next level
- 68Uninformed Search Breadth First - ProsComplete
- 69Uninformed Search Breadth-First ConsTime & Space
All nodes in memory - at 8 levels deep, need 1TB (1k per node, 10^9 nodes) - 70Uninformed Search Uniform-cost searchBreadth-First search which follows lowest cost node instead of all nodes at a level
- 71Uninformed Search Depth-first SearchExtends the deepest node on the current fringe of the tree
- 72Uninformed Search Depth-first search Pros & ConsLow memory Reqmts - only one path need be in memory
Can get stuck going down long or infinite path if it makes a wrong choice. Not complete or optimal. - 73Uninformed Search Depth- Limited SearchSet a depth l which we treat as if it has no successors. Use depth-first search but stop at l. depth-first is special case with l=d.
- 74Uninformed Search Dept-First Search Pros & ConsSolves infinite path problem
incomplete if ld.
useful for applying heuristics - like state-space diameter(known max step count) - 75Uninformed Search Iterative Deepening Depth First Searchfind the best depth limit by gradually increasing the limit - 0,1,2 etc. Repeating entire search each time.
- 76Uninformed Search Iterative Deepening depth-first searchPreferred uninformed search for large search space and unknown solution depth
- 77Uninformed Search Iterative Deepening Pros & ConsSmall memory requirements like depth first search, complete and optimal under right conditions like breadth first.
- 78Uninformed Search Bidirectional SearchTwo simultaneous searches, one forward from init state and one back from the goal, stopping when they meet.
- 79Uninformed Search Bidirectional Search Pros & ConsComplete and Optimal if both searches are breadth first.
Hard to know how to work back from goal in many cases. - 80Uninformed Search Strategies ComparisonBF: Complete, Optimal, Memory issues
UniformCost: Complete, Optimal, memory issues
DF: Not complete, not optimal, small memory
Depth-Limited: Not complete, not optimal, smaller memory
Iterative Deepening: Optimal, Complete, good memory use
Bidirectional: Complete, Optimal, if BF, hard to use - 81Informed SearchUse Problem Specific Knowledge beyond the problem description
- 82Heuristic functionEstimated cost of the cheapest path from node n to a goal node
- 83Greedy Best FirstExpand node that is closest to the goal, according to the heuristic function
- 84Greedy Best First Pros & ConsMinimizing cost is prone to false starts. May choose wrong path just because first step appears to get you closer than another.
Much like Depth First search - not complete or optimal. A good heuristic solves all. - 85Informed Search A*Combines g(n), the cost to reach thenode, and h(n) the cost from the node to the goal. Estimates the cheapest solution through n.
- 86A* HeuristicComplete and Optimal only if h(n) is admissible - that is, it never overestimates the cost to reach the goal
- 87Informed Search Hill ClimbingContinually moves in the direction of increasing value. Stops when no neighbor has higher value.
- 88Hill Climbing IssuesGet stuck because:
Local Maxima
Ridges
Plateaux - 89Gradient DescentMinimize cost by seeking minima
- 90Simulated AnnealingStart at high temperature(make a lot of random moves) and then decrease temperature until reaching steady state at solution.
- 91Solution State Search genetic algoritmstochastic hill climbing search in which a large population of states is maintained. new states generated by mutation and crossover.
- 92Natural Computation Evolutionary ComputationSimulate Darwin
Survival of fittest
Parent fitness <==> offspring
Offspring inheritance/variation(crossover and mutation) - 93Evolution Computation PseudocodeCreate initial population of solutions
until stopping condition:
select parents based on fitness
produce offspring
select individuals to die
end do
return result - 94Minimax algorithmComplete depth-first search of a game tree in order to backup values from each leaf node, labeling parent nodes with the best possible score on that path
- 95Alpha Beta PruningPrune nodes which result in a choice the player would never make. For MAX, prune away all but the branch with the highest low score(which MIN will optimally choose). Highly order dependent.
- 96KR Types of KnowledgeDeclarative(Facts)
Procedural(HowTo) - 97Properties of KnowledgeTemporal Extent
Context
Ambiguities, Conflicts - 98Knowledge Representation IssuesEase of Acquisition
Ease of use in problem solving
Ease of Maintenance
Handling Noise, inconsistencies
Generalization - 99KR ExtremesNatural Language
Formal Logics - 100KR - Practical SystemsRule-based
Network Representations
Logic Programming - 101Propositional LogicConstants: T,F
Operators: AND,OR,NOT,=>
Symbol Manipulation: DeMorgans Law
Truth Tables! - 102Truth TableSpecifies truth value for each possible assignment of true values to its components.
- 103Modus PonensA==>B, a / B
If A=>B and a is given, then B can be inferred. - 104And-EliminationFrom a conjunction, any conjunct can be inferred.
A^B/A.
if (A^B) is given, A can be inferred. - 105Biconditional Inference RulesA<=>B/(A=>B) ^ (B=>A)
also the reverse - 106deMorgan's Rule!(A^B) == (!A || !B)
!(A||B) == (!A ^ !B) - 107SatisifiabilityA sentence is satisfiable if it is true in some model
- 108Propositional Logic ValidityA sentence is valid if it is true in ALL models
- 109Propositional Logic Logical EquivalenceA and B are logically equivalent if they are true in the same set of models
- 110Propositional Logic MonotonicitySet of entailed sentences can only increase as information is added to the knowledge base
IF KB entails A, then KB ^ B entails A too.
"The conclusion of rules must follow regardless of what else is in the knowledge base". - 111Propositional Logic ResolutionApplies only to disjunctions of literals.
Uses inference rules to prove a series of statements. - 112Propositional Logic ResolutionTakes two clauses and produces a new clause containing all the literals of the two original clauses except the complimentary literals.
(L1 || L2) ^ (!L2 || L3) / (L1 || L3) - 113Conjunctive Normal Formevery sentence of propositional logic is logically equivalent to a conjunction of disjunctions of literals.
- 114CNF Sample ConversionB<=>(P12 | P21)
1. Eliminiate <=>
B=>(P12 | P21) ^ (P12 | P21) => B
2. Eliminate =>
Replace a=>b with !a | B
(!B | P12 | P21) ^ (!(P12 | P21) | B)
3. Move NOT inwards so it applies only to literals
(!B | P12 | P21) ^ ((!P12 ^ !P21) | B)
4. Distribute OR over AND
(!B | P12 | P21) ^ (!P12 | B) ^ (!P21 | B) - 115Forward Chaining Deductive ClosureFacts:
A, A=>B ^ C
B => R
C=> Q
Query: Q?
Yes - 116Backward ChainingFacts: A, A=>B &C, B=>R,C=>Q
Query: Q?
Q?: Q<=C
C?: B&C <=A
A?: A = yes. - 117KR Using Prop Logic LimitationsExpressiveness - No Variables
- 118first order logicPropositional Calculus plus ForAll and ThereExists
Variables, relations, functions. - 119FOL UnificationAgree to allow one variable to act as another.
Is Q(Mary) true?
If Q(Z) is true, and we unify Z and Mary, then Q(Mary) is true. - 120KR using Pred Logic FOL Example SimplificationFacts: FA m A(m), FAx A(x)=>B(x) ^ C(x)
FAy B(y)=>R(y)
FAz C(z)=>Q(z) - 121FOL PROS & ConsMuch more expressive
Computation Issues - 122PrologHORN Clauses
Only one variable on right side(no conjunctions)
Negation as Failure: If we can't find the answer query is false. Closed World. - 123FOL QuantifiersUniversal Quantification
"For All..."