Transcript Review

Review Topics
Test 1
Background Topics
• Definitions of Artificial Intelligence & Turing
Test
• Physical symbol system hypothesis vs
connectionist approaches (neural nets,
fuzzy logic, genetic algorithms)
• Application Areas : game playing,
automated reasoning, expert systems,
natural language understanding, etc.
AI Topics
• State Space of Problem
– Graph model, States, Transitions, Problem
solution
– State space search : Backtrack, A* algorithm
‘Operates with 3 strings
‘ s is current path
‘ ns is states reached from current path
‘ de is states which are dead ends
Private Function extend() As Boolean
Dim ex As Boolean = False
Dim children As New Stack(Of String)
If ns.Count = 0 Then
lbHistory.Items.Add("Goal unreachable ")
Return ex
Exit Function
ElseIf nextV = CInt(goal) Then
lbHistory.Items.Add("Path to goal: " &
showS(s))
Return ex
Exit Function
End If
ex = True
children = NextChildren()
If children.Count = 0 Then
'backtrack
While s.Count > 0 And nextV = s.Peek
de.Push(nextV)
labels(CInt(nextV)) = "D"
s.Pop() 'remove first element of s
ns.Pop() 'remove first element of ns
nextV = ns.Peek
'
'ns.Pop()
End While
s.Push(nextV)
labels(nextV) = "S"
Else
'next level
Dim nc As Stack(Of String) = NextChildren()
For Each state In nc
'save children on ns
ns.Push(state)
labels(state) = "N"
Next
nextV = ns.Peek
'get next child
s.Push(nextV)
labels(nextV) = "S" End If
Return ex
End Function
Backtrack State Space Search
8
2
1
5
9
3
6
4
7
Start = 1
Goal = 7
1
0
0
0
Backtrack State Space Search
AI Topics
• Automated Reasoning
– Propositional Calculus
– Predicate Calculus
– Rules of Inference
– Unification
AI Topics
• Expert Systems
– Database model of expert knowledge
– Inference Engine
– CLIPS
• Fact List
• Rules which assert, modify, or retract facts
– Prolog – also has facts and rules
English
Every CS major must take Data Structures.
Bill is a CS major.
Bill must take Data Structures.
Predicate Logic
(x)( CS_Major(x)  Must_Take(x,Data_Structures) )
CS_Major(Bill)
Unification is substitution process of constants or variables for variables which
makes predicate calculus expressions identical – e.g. Bill/x.
Must_Take(Bill,Data_Structures) (modus ponens)
Prolog
CS_Major(Bill) (clause with empty body is fact)
Must_Take(X,Data_Structures) :- CS_Major(X) (rule)
?- Must_Take(Bill,Data_Structures)
CLIPS
(deftemplate CSMajor (slot student))
(deftemplate must_take (slot student)
(slot course))
DataStructures.txt
(deffacts Majors (CSMajor (student Bill)))
(defrule must_take
(CSMajor (student ?S))
=>
(printout t ?S " must take Data Structures" crlf)
(assert (must_take (student ?S) (course Data_Structures)))
)
AI Topics
• Natural Language Understanding & Semantics
– Syntactic models of language
– Syntax directed translation
• Planning and Robotics
– Motion planning using state space approach
• Neural Nets
– Neuron as binary input/output device with output
depending on whether weighted sum of inputs >
threshold
CLIPS program to emulate a neuron
Defines templates for threshold gate, for setting the inputs and for control
facts to keep rules from firing until inputs are specified
(deftemplate TGate (slot input1) (slot input2) (slot weight1) (slot weight2) (slot
threshold))
(deftemplate set1 (slot input1))
(deftemplate set2 (slot input2))
(deftemplate output (slot thresholdOut))
(deffacts blankInput (set1 (input1 -1))
(set2 (input2 -1)) )
(deffacts TGateKOR (TGate (input1 -1) (input2 -1) (weight1 1) (weight2 1)
(threshold 1)))
CLIPS program to emulate a neuron
Defines rules to set and apply inputs
(defrule setInput1
(set1 (input1 -1))
=>
(bind ?i1 (read))
(assert (set1 (input1 ?i1))) )
(defrule setInput2
(set2 (input2 -1))
=>
(bind ?i2 (read))
(assert (set2 (input2 ?i2))) )
(defrule applyInputs
?g <- (TGate (input1 -1) (input2 -1) (weight1 1) (weight2 1) (threshold 1))
(set1 (input1 ?i1))
(set2 (input2 ?i2))
(test (<> ?i1 -1))
(test (<> ?i2 -1))
=>
(retract ?g)
(assert (TGate (input1 ?i1) (input2 ?i2) (weight1 1) (weight2 1) (threshold 1)))
)
CLIPS program to emulate a neuron
Defines rule for zero output
((defrule TGateZeroOut
(TGate (input1 ?i1) (input2 ?i2) (weight1 ?w1) (weight2 ?w2) (threshold ?t))
(test (<> ?i1 -1))
(test (<> ?i2 -1))
(test (< (+ (* ?i1 ?w1) (* ?i2 ?w2)) ?t))
=>
(printout t "Output Zero" crlf)
(assert (output (thresholdOut 0)))
)
Exercise – Write rule for OneOut
AI Topics
• Genetic Algorithms
– Population individuals are candidate solutions
– Fitness function determines whether
individuals are selected for mating
– Mating produces child solutions with
operations of crossover and mutation
AI Topics
• Knowledge Representation
– Semantic Networks
• Network nodes, arcs
– Standardization of relations
• Case relations
– Conceptual Dependencies
• Four Primitive Concept Classes
– Actions, Objects, Action Modifiers, Object Modifiers
– 12 Primitive Action Classes – Atrans, Ptrans, etc.
AI Topics
• Knowledge Representation
– Scripts formalize a stereotyped sequence of
events
• Entry & termination conditions, Props, Roles,
Scenes
– Frames formalize stereotyped entities and
actions
• Frame ID, Relationship to other Frames, Labeled
Slots