What is AI
AI is categorized into four types
The textbook advocates “acting rationally”.
What is Turing test approach
A test based on indistinguishability from undeniably intelligent entities and human beings. The computer passes the test if a human interrogator, after posing some written questions, cannot tell whether the written responses come from a person or not.
What is agent
Anything that can be viewed as perceiving its environment through sensors and acting upon that environment through its actuators to maximize progress towards its goals.
PAGE: perceiving, environment, sensors, goals
What is rational agent
A rational agent chooses whichever action maximizes the expected value of the performance measure given the percept sequence to date and prior environment knowledge.
What is four elements of rational agents
PEAS
Examples of rational agent and its elements
Medical diagnosis system
Part-picking robot
Interactive English tutor
Agent structure
agent = architecture + program
Agent program components
Atomic, Factored and Structured.
Explanation:
Atomic: An atomic representation is one in which each state is treated as a black box.
Example:
atomicState == goal: Y/N
Explanation:
Y/N is the only question we can ask to a black box
Factored: A factored representation is one in which the states are defined by set of features.
Example:
factoredState{18} == goal{42}: N // Is goal reached?
diff( goal{42}, factoredState{18}) = 24 // How much is difference?
// some other questions.Explanation:
The simplest factored state must have at least one feature (of some type), that gives us ability to ask more questions. Normally it defines quantitative difference between states. The example has one feature of integer type.
Structured: A structured representation is one in which the states are expressed in form of objects and relations between them. Such knowledge about relations called facts.
Example:
11grade@schoolA{John(Math=A-), Marry(Music=A+), Job1(doMath)…} == goal{50% ready for jobs}
Explanation:
The key here - structured representation, allows higher level of formal logical reasoning at the search.
Agent types
How to define a problem (5 items)
Evaluation of search strategies
Note that:
- b b b: maximum branching factor of the search tree
- d d d: depth of the least-cost solution
- m m m: maximum depth of the state space
The basic framework of uniformed searching is (if it is a graph, then maintain a closed set):
def search(problem, fringe): -> a solution or falure
fringe.insert(make-node(problem.initial-state))
while:
if fringe is empty:
return fauilre
node = fringe.pop()
if problem.goal-test(node.state):
return node
fringe.insertall(expand(node,problem))
def expand(node, problem):
succesors = []
for action, state in Successor-fn(problem, node.state):
s = make-node(state)
s.parent = node
s.action = action
s.path-cost = node.path-cost + step-cost(node, action, s)
s.depth = node.depth + 1
succesors.append(s)
return successors
Breadth-first search
Fringe is a FIFO queue. Nodes are appended at the end of the fringe.
Uniform-cost search
Fringe is a Priority queue.
Depth-first search
Fringe is a FILO stack. Nodes are inserted at the head of the fringe.
Depth-limited search
DFS with depth limit l l l. That is to say, nodes at depth l l l have no successors.
Iterative deepening search
Run depth-limited search iteratively unless find a solution. Otherwise, dead loop.
BFS | UCS | DFS | DLS | IDS | |
---|---|---|---|---|---|
Completion | Y e s a Yes^a Yesa | Y e s a , b Yes^{a,b} Yesa,b | No | No | Yes |
Time | O ( b d + 1 ) O(b^{d+1}) O(bd+1) | O ( b ⌈ 1 + C ∗ / ϵ ⌉ ) O(b^{\lceil 1+C^*/\epsilon \rceil}) O(b⌈1+C∗/ϵ⌉) | O ( b m ) O(b^m) O(bm) | O ( b l ) O(b^l) O(bl) | O ( b d ) O(b^d) O(bd) |
Space | O ( b d + 1 ) O(b^{d+1}) O(bd+1) | O ( b ⌈ 1 + C ∗ / ϵ ⌉ ) O(b^{\lceil 1+C^*/\epsilon \rceil}) O(b⌈1+C∗/ϵ⌉) | O ( b m ) O(bm) O(bm) | O ( b l ) O(bl) O(bl) | O ( b d ) O(bd) O(bd) |
Optimal | Y e s c Yes^c Yesc | Yes | No | No | Y e s c Yes^c Yesc |
NOTE:
Y e s a Yes^a Yesa: Completion if branch is finite.
Y e s b Yes^b Yesb: Completion if step costs are non-negative (i.e., no-circle).
Y e s c Yes^c Yesc: Optimal if step costs are the identical.
b b b: maximum branching factor of the search tree
d d d: depth of the least-cost solution
m m m: maximum depth of the state space
l l l: depth limit
Heuristic function: denoted as h ( n ) h(n) h(n), which means the estimated cost of the cheapest path from node n n n to a goal node.
Greedy best-first: Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function: f ( n ) = h ( n ) f(n)=h(n) f(n)=h(n)
Evaluation function: f ( n ) = g ( n ) + h ( n ) f(n) = g(n) +h(n) f(n)=g(n)+h(n). Where g ( n ) g(n) g(n) is the so-far cost to reach n n n, h ( n ) h(n) h(n) is the estimated cost from n n n to the goal.
Admissible: A heuristic h ( n ) h(n) h(n) is admissible if for every node n n n, h ( n ) ≤ h ∗ ( n ) h(n)\le h^*(n) h(n)≤h∗(n), where h ∗ ( n ) h^*(n) h∗(n) is the true cost to reach the goal state from n n n.
Consistency: A heuristic is consistent if for every node
n
n
n, every successor
n
′
n'
n′, generated by any action
a
a
a, we have
h
(
n
)
≤
c
(
n
,
a
,
n
′
)
+
h
(
n
′
)
h(n)\le c(n,a,n') + h(n')
h(n)≤c(n,a,n′)+h(n′)
Thus,
f
(
n
′
)
=
g
(
n
′
)
+
h
(
n
′
)
=
g
(
n
)
+
c
(
n
,
a
,
n
′
)
+
h
(
n
′
)
≥
g
(
n
)
+
h
(
n
)
≥
f
(
n
)
f(n')=g(n')+h(n')=g(n)+c(n,a,n')+h(n')\ge g(n)+h(n)\ge f(n)
f(n′)=g(n′)+h(n′)=g(n)+c(n,a,n′)+h(n′)≥g(n)+h(n)≥f(n)
If a heuristic function is consistency then it is admissible
Proof by induction.
Dominance (占优问题): If h 2 ( n ) ≥ h 1 ( n ) h_2(n)\ge h_1(n) h2(n)≥h1(n) for all n n n (Assume h 2 ( x ) h_2(x) h2(x) and h 1 ( x ) h_1(x) h1(x) are both admissible). Then h 2 h_2 h2 dominates h 1 h_1 h1, and h 2 h_2 h2 is better for search.
Hill-climbing Search
Simulated annealing
def simulated_annealing(problem, schedule)
current = make-node(problem.initial-state)
for t in range(1, MAX):
Temperature = schedule[t]
if T = 0:
return current
successor = randomly choose successor of current
E = successor.value - current.value
if E > 0:
current = successor
else:
with probablity e ** (E/T), current = successor
Local beam search
Keep k k k states instead of 1; choose top k k k of all their successors. These successors are not the same, as k k k searches run in parallel. In a random-restart search, each search process runs independently of the others. In a local beam search, useful information is passed among the k parallel search threads.
Genetic algorithms
Single-player | Multi-player |
---|---|
Zero-sum | Non-zero-sum |
Deterministic | Non-deterministic |
Perfect information | Imperfect information |
Deterministic | Chance | |
---|---|---|
Perfect information | Chess, checkers(西洋跳棋), go, Othello | Backgammon西洋双陆棋, monopoly |
Imperfect information | Stratego, JunQi | Bridge, poker, scrabble拼字游戏, nuclear war |
def minimax-decision(state):
v = max-value(state)
return the action in successors(state) with value v
def max-value(state):
if terminal-test(state):
return utility(state)
v = MIN
# select the maximam value
for action, successor in successors(state):
v = max(v, min-value(successor))
return v
def min-value(state):
if terminal-test(state):
return utility(state)
v = MAX
for action, successor in successors(state):
v = min(v, max-value(successor))
return v
Check Alpha-Beta剪枝算法(人工智能)_哔哩哔哩_bilibili
def alpha-beta-search(state):
v = max-value(state, MIN, MAX)
return the action in successors(state) with value v
def max-value(state, alpha, beta):
if terminal-test(state):
return utility(state)
v = MIN
# select the maximam value
for action, successor in successors(state):
v = max(v, min-value(successor, alpha, beta))
if v >= beta:
return v
alpha = max(alpha, v)
return v
def min-value(state, alpha, beta):
if terminal-test(state):
return utility(state)
v = MAX
for action, successor in successors(state):
v = min(v, max-value(successor, alpha, beta))
if v <= alpha:
return v
beta = min(beta, v)
return v
Entailment/Inference
Completeness/Soundness
Syntax/Semantics
Syntax defines the sentences in the language
Semantics define the “meaning” of sentences: define truth of a sentence in a world
Logically equivalent
Two sentences are logically equivalent iff true in same models. That is to say: α ≡ β α ≡ \beta α≡β iff α ⊨ β α\vDash β α⊨β and β ⊨ α β\vDash α β⊨α.
NOTE:
Validity/Satisfiability
A sentence is valid if it is true in all models,
e.g., True, A ∨ ¬ A A\lor \neg A A∨¬A, A ⇒ A A \Rightarrow A A⇒A, ( A ∧ ( A ⇒ B ) ) ⇒ B (A \land (A \Rightarrow B)) \Rightarrow B (A∧(A⇒B))⇒B
Validity is connected to inference via the Deduction Theorem:
K B ⊨ α KB \vDash \alpha KB⊨α iff ( K B ⇒ α KB \Rightarrow α KB⇒α) is valid
A sentence is satisfiable if it is true in some model
e.g., A ∨ B A\lor B A∨B, C C C
A sentence is un-satisfiable if it is true in no models
e.g., A ∧ ¬ A A\land \neg A A∧¬A
Satisfiability is connected to inference via the following:
K B ⊨ α KB \vDash \alpha KB⊨α iff ( K B ∧ ¬ α KB \land \neg α KB∧¬α) is un-satisfiable (i.e., ( ¬ ( K B ∧ ¬ α ) \neg (KB \land \neg α) ¬(KB∧¬α)) is valid, i.e., ( ¬ K B ∨ α \neg KB\lor \alpha ¬KB∨α) is valid, )
Inference rules
NOTE:
Modus ponens (肯定前件)
Resolution
Conjunctive Normal Form (CNF) (合取范式)
( A ∨ B ) ∧ ( ¬ B ∨ C ∨ D ∨ ¬ E ) (A\lor B) \land (\neg B\lor C \lor D\lor \neg E) (A∨B)∧(¬B∨C∨D∨¬E)
Resolution
Before: ( A ∨ B ) ∧ ( ¬ B ∨ C ∨ D ∨ ¬ E ) (A\lor B) \land (\neg B\lor C \lor D\lor \neg E) (A∨B)∧(¬B∨C∨D∨¬E)
After: A ∨ C ∨ D ∨ ¬ E A \lor C \lor D\lor \neg E A∨C∨D∨¬E
Conversion to CNF
Resolution Algorithm
Show K B ∧ α KB\land \alpha KB∧α is un-satisfiable.
Horn Form: Conjunction of Horn clauses (clauses with ≤ 1 positive literal)
Forward Chaining
Backward Chaining
Forward Chaining vs. Backward Chaining
Definition
A simple, graphical notation for conditional independence assertions and hence for compact specification of full joint distributions
Semantics
Numeric semantic: full joint distribution of Bayesian networks
P
(
x
1
,
.
.
.
,
x
n
)
=
Π
i
=
1
n
P
(
x
i
∣
P
a
r
e
n
t
s
(
x
i
)
)
P(x_1,...,x_n)=\Pi_{i=1}^nP(x_i|Parents(x_i))
P(x1,...,xn)=Πi=1nP(xi∣Parents(xi))
Topological semantic: each node is independent of all others given its Markov blanket
Markov Blanket: Parents + Children + Children’s parents
Constructing Bayesian Networks
See if the new variable is independent of given variables.
Noisy-OR
Add a leak node as other unknown causes.
Inference tasks
Simple queries
P
(
X
i
∣
E
=
e
)
P(X_i|E=e)
P(Xi∣E=e)
Conjunctive queries
P
(
X
i
,
X
j
∣
E
=
e
)
=
P
(
X
i
∣
E
=
e
)
P
(
X
j
∣
X
i
,
E
=
e
)
P(X_i,X_j|E=e)=P(X_i|E=e)P(X_j|X_i,E=e)
P(Xi,Xj∣E=e)=P(Xi∣E=e)P(Xj∣Xi,E=e)
Exact Inference
Enumeration
P
(
B
∣
j
,
m
)
=
α
∑
e
∑
a
P
(
B
,
e
,
a
,
j
,
m
)
=
α
∑
e
∑
a
P
(
B
)
∗
P
(
e
)
∗
P
(
a
∣
B
,
e
)
∗
P
(
j
∣
a
)
∗
P
(
m
∣
a
)
=
α
P
(
B
)
∗
∑
e
P
(
e
)
∑
a
∗
P
(
a
∣
B
,
e
)
∗
P
(
j
∣
a
)
∗
P
(
m
∣
a
)
Variable elimination
Approximate Inference
Stochastic simulation
Sampling from an empty network
Rejection sampling: Selecting the samples agreeing with given evidence.
Likelihood weighting: Fix evidence variables, sample only nonevidence variables, and weight each sample by the likelihood it accords the evidence. Sample from parents.
Markov chain Monte Carlo
Sampling from Markov Blanket.
给三句话,用FOL表述。最后一个是每个爱动物的人都有一个人爱他
Game问题,很tricky,P1、P2用的不同效度函数,我的理解是P2让P1的效度少,P1让P2的效度少
密码问题
A*,求最短路径
贝叶斯网络(性质、概念、没有计算)
贝叶斯网络中的拒绝采样与似然采样,看起来很复杂,做起来相对容易。需要熟悉似然采样的流程