AI 筆記































Chapter 1 : Introduction

humanly rationally
Acting Turing Test law of thought
Think cognitive modeling rational agent

Chapter 2 : Intelligent Agent

Rational agent
1. Performance measure that defines degree of success
2. Percept Sequence
3. What the agent knows about the environment
4. The action that the agent can perform

Ideal rational agent :
An ideal rational agent should do whatever action is expected to maximize its performance measure, on the basis of the evidence provided by the percept sequence and whatever built-in knowledge the agent has.

percept sequence <--> action

ideal mapping :
Specifying which action an agent ought to take in response to any given percept sequence provides a design for an ideal agent.

A system is autonomous to the extent that its behavior is determined by its own experience, not some body tell him.

Agent architecture (easy memorize —> PAGE)
Percept :
Action :
Goal :
Environment :

Four type of agent :
Simple reflex agents
condition-action rule

Agents that keep track of the world
Needed two kind of information :
How the world evolves independently of the agent
How the agent's own action affect the world.

Goal-based agent
Goal information
Search or Planning

Utility-based agents

Properties of environment
accessible vs. inaccessible (chess vs. poker)
Accessible :
agent's sensor apparatus gives it access to the complete state of the environment.

deterministic vs. nondeterministic (chess
Deterministic :
next state of the environment is complete determined by the current state and the actions selected by the agents.

episodic vs. nonepisodic (Image analysis system vs. chess)
Episodic :
the agent's experience can be divided into "episodes".
static vs. dynamic (porker vs. taxi driving)
Dynamic :
the environment can change while an agent is deliberating.

discrete vs. continuous (chess vs. taxi driving)
Discrete :
there are limited number of distinct, clearly defined percepts and actions.

Chapter 3 Solving Problems by Searching

1. How an agent can act by establishing goals and considering sequences of actions that might achieve those goal. A goal and a set of means for achieving the goal is called a problem, and the process of exploring what the mean can do is called search.

Problem Formulation
State space :
(path:any sequence of actions leading by any sequence of actions.)

Single state problem :
whole world state is accessible.
Single state problem formulation
(datatype PROBLEM components :
initial state (where are we now ?)
operator (or successor function) set
(what's the possible next state ?) :
succ(stateNow) = { state | state that reachable from stateNow }
goal test : (is this state is goal ?)
state = goal_state ?
path cost(g(p)):
in most case, path cost = Σ(cost(vi, vi+1))
Output : solution, a path from the initial state to a state that satisfies the goal test.

Multiple state problem : the world state is not fully accessible.
initial state —> initial state set
state space —> state set space

Measure problem solving performance
total cost = search cost (time) + path cost (distance)
What is the exchange rate between time and distance ?

Abstraction : removing detail from a representation.
example : in routing , we don't consider the weather, law enforcement, traffic jamming…
Abstraction Principle :
removing as much detail as possible while retaining validity and ensuring that the abstract actions are easy to carry out.
Step 2 : Search.
Step 3 : Return solution in action sequence form.

Chapter 6 : Agent that reason logically

Syntax :
Describes the possible configurations that can constitute sentences.

Semantic :
Determines the facts in the world to which the sentences refer.
interpretation for syntax

Proof theory :
A set of axiom + a set of inference rule.

Proper reasoning should ensure that the new configurations represent facts that actually follow from the facts that the old configurations represent.

╞ (entail) (proof by truth table)

KB ╞ φ means for all case -KB|φ is always true

├ (derive) (proof by axiom and inference rule)

KB ├ φ means that we can derive φ from KB by axiom and inference rule.

Sound : An inference procedure i that generates only entailed sentences is called sound or truth-preserving.
!├ φ & -φ

Proof : The record of operation of a sound inference procedure is called a proof (proof theory).

1. KB + {φ1…φi-1} => φi ( φn = φ )
2. For every i≦n φi in KB or φi is an axiom.

Complete : An inference procedure is complete if it can find a proof for any sentence that is entailed.
if φ is valid then ├ φ

(Natural language have evolved more to meet the need of communication rather than representation.)

Shapir-Whorf hypothesis :
the language we speak profoundly influences the way in which we think and make decision.

Sentences ---> Sentence
↓ ↓
Facts ---> Fact

Valid sentence : (tautologies , analytic sentences)
A sentence that is true under all possible interpretations in all possible

Satisfiable sentence :
there is some interpretation in some world for which it is true.
PL : propositional logic
FOL : First Order Logic
TL : temporal logic
PT : probability theory
FL : Fuzzy logic

Ontological Commitment Epistemological Commitment
(What exist in the world) (What an agent believes about facts)
PL = (&,|,-) + proposition true/false/unknown
FOL = (&,|,-) + proposition
+ function + predicate true/false/unknown
TL = (&,|,-) + proposition
+ function + predicate
+ times true/false/unknown
PT = proposition degree of belief 0..1
FL = degree of truth degree of belief 0..1

Model : any world in which a sentence is true under a particular interpretation is called a model of the sentence under that interpretation.

A sentence φ is entailed by a KB if the models of KB are all models of φ.
ie : KB ╞ φ ==> ╞ KB=>φ, ie: KB=>φ is valid.

Prepositional logic :
Syntax :
1. A set of proportion {A, B, C,…} in this language
2. All form of P&Q, P|Q, -P (P=>Q) in this language
3. No other things is in this language
Semantic :
1. P => {T, F}
2. P Q -P P&Q P|Q P=>Q
A sentence is valid if it's true in all row of truth table.
Proof Theory
Inference rule :
Modus ponens : A=>B, A —> B
And Elimination : A1&A2…&An —> Ai
And Introduction : A1,A2,…An —> A1&A2…&An
OR Introduction : Ai —> A1|A2…|An
Double Negation : —A —> A
Unit Resolution : A|B, -B —> A
Resolution : A|B, -B|C —> A|C
implication form : -A=>B, B=>C —> -A=>C

Complexity of prepositional inference :
SAT problem in set NP-complete
Horn sentence : P1&P2…&Pn=>Q
HORN-SAT in set P

Monotonically :
if KB1╞A then (KB1 ∪ KB2)╞A

Chapter 7: First order logic

Constant + Predicate + Function = First Order Logic
Term : Constant , variable or Function
Ground Term : A term with no variable
Atomic Sentence : Predicate with parameter.
Complex Sentence : Sentence with logical connective.
Quantifier : $, #, #!,

Second Order Logic : $p φ

Situation calculus :
1. Special time sequence variable called situation :
S0,S1,S2,.. , St, …
2. Result(action, Si)=Si+1
3. Effect axiom : axioms that make the world change.
Ex: -Hold(x, Result(Release, s))
4. Frame axioms : axioms that describe how the world stay the same.
Ex: -Hold(x,s)^(a≠Grab├(Present(x,s)^Portable(x))=>-Hold(x,Result(a,s))
5. Successor-state axiom = Effect axiom + Frame axiom
Ex: Hold(x,Result(a,s))

Representational Frame Problem :
The proliferation of frame axioms (solved by Successor-state axiom)

Inferential Frame Problem :
When reasoning about the result or a long sequence of action in situation calculus, we have to carry each property through all intervening situation one step at a time, even if the property remain unchanged throughout.(this is why that special purpose reasoning system such as planning system is needed).

Qualification :
it’s difficult to define the circumstances under which a given action is guaranteed to work.

Ramification Problem :
it’s almost impossible to describe all the implicit consequence of actions.

Deduce Hidden Properties of the World

Synchronic rules :
relate properties of a world property of the world causes certain percepts to be generated.
(Type1) Causal rules : Conclusion => Environment
(Type2) Diagnostic rules : Percept => Conclusion

Chapter 8: Building a Knowledge Base

Five step of Knowledge Engineering :
(use circuit design as an example)
1.Decide what to talk about.
Example :
Circuit, Terminal, Signal, Gate, Gate-Type (AND, OR ..)

2.Decide on a vocabulary of predicates, functions and constants
Example :
Gate Name : Gate (X1, X2, .. ..)
Type Function : Type(X1), Type(X2).. ..
Input Predicate : IN(1, X1), IN(2, X2) .. ..

3.Encode general knowledge about the domain.
Example :
Connected(t1, t2)=>Signal(t1)=Signal(t2) (同線等電位)
Signal(t)=On | Signal(t)=Off (不是on就是 Off)
Type(g)=OR => Signal(Out(1,g))=On <=> Signal(Out(1,g))=Off
(OR gate的作用)

4.Encode a description of the specific problem instance.
Example :

5.Pose queries to the inference procedure and get answers.
Example :
Circuit verification, 用testing case測試是否正確。

本體論(一般型態) General Ontology
1. 分類 Categories :
By Unary Predicate : Tomato(x) ,
By reification : turning a predicate into an object ,
Tomatos, is(x, Tomatos)
Disjoint({Animals, Vegetables})
ExhaustiveDecompisition({American, Canadians, Mexicans},NorthAmericans)
Partition({Males, Females}, Animals)

2. 度量 Measures :
Unit function :
Order is important :
=> ExpectedScore(e1)<ExpectedScore(e2)

3. 組合 Composite objects :
PartOf(Bucharest, Romania)
Schema , script :
PartPartition({head, body, hand, leg}, person)
BunchOf({Apple1, Apple2, Apple3})

4. 時空改變 Time, Space, and Change :
5. 事件與過程 Events and Processes :
Situation calculus的不足:
1. 無法描述連續時間
2. 無法描述 Multiple Agent.

Event calculus : (situation calculus in continuous version)
An Event is just a “chunk” of this universe with both temporal and spatial extent.

Time Example : SubEvent(BattleOfBritian, WorldWarII)
SubEvent(WorldWarII, TwentiethCentury)
Place Example: In(NewYork, USA)
Minimization : (描述最小區域或最小時段)
Example: Loaction(x)=l <=> At(x,l)&$At(x,l2)=>In(l,l2)

Process (liquid event categories):
Event(Flying(Johnson, Yesterday))
Throughout(Closed(Supermarket1), BunchOf(Sundays))
Throughout(p&q,e) Throughout(p|q, e) Throughout(p xor q,e)
---- - -
---- --— — -

Meet(i,j)<=> Time(End(I))=Time(Start(j))
Before(i,j)<=> Time(End(I))<Time(End(j))
After(j,i)<=> Before(i,j)
During(i,j)<=> Time(Start(j))<=Time(Start(I))&Time(End(I)<=Time(End(j)))
Overlap(i,j)<= > #k During(k,i)&During(k,j)

Meet(i,j) i: ---
j: --
Before(i,j) i: -
j: --——

During(i,j) i: --
j: -

Overlap(i,j) i: --
j: -

6. 實體 Physical Objects :
Typical典型 : Typical(C) is subset of C :
若無特別指定(例外),則x in C => x in Typical(C)
Fluents Object 會隨時間改變的實體(temporal substance):
example : President(USA)
individuation 不可分割的實體 :
example : People

7. 物質 Substances :
可分割的實體stuff (spatial substance) (example : Butter)

8. 精神、信仰 Mental Objects and Beliefs
Believes(Agent,x) : x is referential opaque
example :
Superman=Clark ╞ (Believes(Lois, Flies(Superman))<=>
is not right.

Referential transparency :
The property of begin able to freely substitute a term for an equal term is called referential transparency.

Syntactic theory : Flies(clark) => [F,l,i,e,s,(,C,l,a,r,k,)]
Semantic :
Proof Theory :

Chapter 9: Inference in first order logic

SUBST(b, φ) :
the result of applying the substition b to the sentence φ.
b is a binding list
example : SUBST({x/Sam, y/Pam}, Likes(x,y)) = Likes(Sam, Pam)

Inference rule :

1. Universal elimination :
$v φ => SUBST({v, g}, φ) where g is any ground term.

2. Existential elimination :
#v φ => SUBST({v, k}, φ)
where k is a constant symbol that does not appear elsewhere.

3. Existential Introduction :
φ => #v SUBST({g/v}, φ) where g is a ground term, v is a variable.

Generalized Modus Ponens
if SUBST(theta, pi')=SUBST(theta, pi) then
p1',p2', …,pn', (p1&p2&…&pn=>q) => SUBST(theta, q)

Horn Sentence

UNIFY(p, q) = theta if SUBST(theta, p)=SUBST(theta, q)
where the UNIFY return the Most General Unifier (MGU)
UNIFY(Knows(John, x), Knows(y, z))
may have {y/John, x/z}, {y/John, x/John, z/John}…
but {y/John, x/z} use the least commitment

Forward Chaining Algorithm ( is a data-driven (data-directed) procedure)

Renaming : Likes(x, IceCream) = Likes(y, IceCream)
Composition : COMPOSE(theta1, theta2)
SUBST(COMPOSE(theta1, theta2), p) = SUBST(theta2, SUBST(theta1, p))

procedure FORWARD-CHAIN(KB, p)
if there is a sentence in KB that is a renaming of p then
Add p to KB // 新加入一條 fact, 盡可能的去觸發所有可能的 unification.
for each (p1&…&pn=>q) in KB
such that for some i, UNIFY(pi, p)= theta succeeds do
FIND-AND-INFER(KB, [p1,…,Pi-1,Pi+1,…Pn], q, theta)

procedure FIND-AND-INFER(KB, premoses, concolusion, theta)
if premise = [] then
// 本規則完全 unify 成功, 把 conclusion 也加入, 並看能否進一步觸發其它規則.
FORWARD-CHAIN(KB, SUBST(theta, conclusion))
else for each p' in KB such that UNIFY(p', SUBST(theta, FIRST(premises))) = theta2 do
// 把可以 unify 的規則一直 unify 到無法 unify 為止.
FIND-AND-INFER(KB, REST(premise), conclusion, COMPOSE(theta, theta2))

function BACK-CHAIN(KB, q) returns a set of substitutions

function BACK-CHAIN-LIST(KB, qlist, theta) returns a set of substitutions
input : KB, a knowledge base
qlist, a list of conjuncts forming a query (theta already applied)
theta, the current substitution
local variables : answers, a set of substitutions, initially empty

if qlist is empty then
return {theta}
q = FIRST(qlist)
for each qi' in KB such that theta i = UNIFY(qi, qi') succeeds do
Add COMPOSE(theta, theta i) to answer
for each sentence (p1&…&pn=>qi') in KB such that theta i = UNIFY(q, q') succeeds do
answers = BACK-CHAIN-LIST(KB, SUBST(theta i, [p1,…,pn]), COMPOSE(theta, theta i)) ∪ answers
return the union of BACK-CHAIN-LIST(KB, REST(qlist), theta) for each theta in answers.

KB :
American(x) & Weapon(y) & Nation(z) & Hostile(z) & Sells(x, z, y) => Criminal(x)
Owns(Nono, x) & Missile(x) => Sells( West, Nono, x)
Missile(x) => Weapon(x)
Enemy(x, America ) => Hostile(x)

Enemy(Nono, America)
Owns(Nono, M1)

Forward chaining example
{American(West)} & Weapon(y) & Nation(z) & Hostile(z) & Sells(West, z, y) => Criminal(West)
{Nation(Nono)} & American(x) & Weapon(y) & Hostile(z) & Sells(x, z, y) => Criminal(x)
{American(West) & Nation(Nono)} & Weapon(y) & Hostile(Nono) & Sells(x, z, y) => Criminal(West)
{Enemy(Nono, America)} … => Hostile(Nono)
{American(West) & Nation(Nono) & Hostile(Nono)} & Weapon(y) & Sells(West, Nono, y) => Criminal(West)
{Owns(Nono, M1) } & Missile(M1) => Sells( West, Nono, M1)
{Owns(Nono, M1) , Missile(M1) } … => Sells(West, Nono, M1)
{American(West) & Nation(Nono) & Hostile(Nono) & Sells(West, Nono, M1) } & Weapon(y) => Criminal(West)
{ Missile(M1) } …=> Weapon(M1)
{American(West) & Nation(Nono) & Hostile(Nono) & Sells(West, Nono, M1) & Weapon(M1)} …=> Criminal(West)
question sentence found.

Backward chaining example

? Criminal(West):?American(West)&?Weapon(y)&?Nation(z)&?Hostile(z)&?Sells(West, z, y): yes
? American(West) : yes-^ ^ ^ ^ ^
? Weapon(y) : ? Missile(y) : Missile(M1) {y/M1} | | |
? Nation(z) : Nation(Nono) {z/Nono}---+ | |
? Hostile(Nono) : yes
-------—+ |
? Sell(West, Nono, M1) : yes -

Forward chaining and Backward chaining is not complete
Proof :
In Case Analysis

KB :
$x P(x) => Q(x)
$x -P(x)=> R(x)
$x Q(x) => S(x)
$x R(x) => S(x)

KB ╞ $x S(x) but KB !╞ $x S(x) in Forward chaining and Backward chaining.

Complete : if KB╞φ then KB ├ φ by Resolution Procedure

Resolution in and/or form
(a|b) & (-b|c) => a|c

Resolution in implication form
(-a=>b & b=>c) => -a=>c

Generalized Resolution in and/or form
[p] = [p1|…pj…|pm]
[q] = [q1|…qk…|qn]

[p] &[q] => SUBST(theta, [p]-pj, [q]-qk)
where UNIFY(pj, -qk) = theta

Generalized Resolution in implication form
[p] = [p1&…pj…&pn1]
[r] = [r1|……..|rn2]
[s] = [s1&……..&sn3]
[q] = [q1|…qk…|qn4]

(([p] => [r]) & ([s] => [q])) => SUBST(theta, (([p]-pj)&[s])=>([r]|([q]-qk))))
(where UNIFY(pj, -qk) = theta )

Canonical form for resolution :
Conjunctive normal form (CNF)

Implicative Normal Form (INF)

P(w)=>Q(w) Q(y)=>S(y)
\ {y/w} /
P(w)=>S(w) True=>P(x)|R(x)
\ {w/x} /
True=>S(x)|R(x) R(z)=>S(z)
\ {x/A,z/A} /
True=>S(A) S(A)=>False
\ /

-P(w)|Q(w) -Q(y)|S(y)
\ {y/w} /
-P(w)|S(w) P(x)|R(x)
\ {w/x} /
S(x)|R(x) -R(z)|S(z)
\ {x/A,z/A} /
S(A) -S(A)
\ /

Conversion to Normal Form

Eliminate implication
(p=>q) ├ (-p|q)

Move - inwards
-(p|q) ├ (-p&-q)
-(p&q) ├ (-p|-q)
-($x,p)├ (#x -p)
—p ├ p

Standardize variables
rename variable in different scope with different name.

Move quantifiers left
p|$x q ├ $x p|q

Skolemize : removing # by elimination.
$x Person(x) => #y Heart(y)&Has(x, y)
->$x Person(x) => Heart(F(x))&Has(x, F(x))

Distribute & over | :
(a&b)|c -> (a|c)&(b|c)

Flatten nested conjunctions and disjunctions :
(a|b)|c -> (a|b|c)

Convert disjunctions to implications
(-a|-b|c|d) -> (a&b=>c|d)

Example Proof :
In implication normal form :

Axiom :
#x Dog(x)&Own(Jack, x)
$x(#y Dog(y)&Own(x, y))=>AnimalLover(x))
$x(AnimalLover(x)=>($y -Animal(y)=>-Kill(x,y)))
Own(Jack, D)
Kills(jack, Tuna)|Kills(Curiosity, Tuna)

In implication form:
$x(#y Dog(y)&Own(x, y))=>AnimalLover(x))
Own(Jack, D)
Kills(Jack, Tuna)|Kills(Curiosity, Tuna)

Dog(D) Dog(y)&Own(x, y)=>AnimalLover(x)
\ / {y/D}
Own(x, D)=>AnimalLover(x) Own(Jack, D)
{x/Jack} \ /
AnimalLover(x)=>(-Animal(y)=>-Kill(x, y)) AnimalLover(Jack)
\ /
Cat(Tuna) Cat(x)=>Animal(x) Animal(y)=>-Kill(Jack, y)
\ / /
Animal(Tuna) /
\ /
-Kill(Jack, Tuna) Kills(Jack, Tuna)|Kills(Curiosity, Tuna)
\ /
Kill(Curiosity, Tuna) -Kill(Curiosity, Tuna)
\ /

In conjunction normal form :

-Dog(y)|-Own(x, y)|AnimalLover(x)
Own(Jack, D)
Kills(Jack, Tuna)|Kills(Curiosity, Tuna)

Dog(D) -Dog(y)|-Own(x, y)|AnimalLover(x)
\ / {y/D}
-Own(x, D)|AnimalLover(x) Own(Jack, D)
{x/Jack} \ /
-AnimalLover(x)|-Animal(y)|Kill(x, y) AnimalLover(Jack)
\ /
Cat(Tuna) -Cat(x)|Animal(x) -Animal(y)|Kill(Jack, y)
\ / /
Animal(Tuna) /
\ /
-Kill(Jack, Tuna) Kills(Jack, Tuna)|Kills(Curiosity, Tuna)
\ /
Kill(Curiosity, Tuna) -Kill(Curiosity, Tuna)
\ /

Dealing with equality
A=B & P(A) cannot unify with P(B), it’s unreasonable.
Method 1 : Axiomize equality
$x x=x
$x,y x=y => y=x
$x,y,z x=y & y=z => x=z
$x,y x=y => (P1(x)<=>P1(y))
$w,x,y,z w=y&x=z => (F(w,x)=F(y,z))

Method 2 : Demodulation
UNIFY(x,z)= theta & x=y, (.. z .. ) => (.. SUBST(theta, y) ..)

Resolution strategy
Unit preference (Wos 1964): 短者優先
Set of support (Wos 1965):
1. identify set of support
2. combine(x,y) x in set of support, y in KB
Input resolution :
combine(x,y) x is input sentence, y in KB
In Horn clause , input resolution is complete.
Linear resolution (Loveland 1968):
if P=>..=>Q then Q, Q
then Unify(P,z), Unify(Q,z) should be done together.

Subsumption :
eliminates all sentences that are subsumed by an existing sentence in the KB.
Example : if P(x) in KB then P(A) should be deleted from axiom.

Normalize theorem
Any first order logic can be rewritten in normal form.
(Davis and Putnam 1960)

Resolution Complete Theorem :
if S is an unsatisfiable set of sentences in clausal form, then the application of a finite number of resolution steps to S will yield a contradiction.
Proof :
Herbrand universe Hs : Hs = constant symbol + function symbol
example :
P(x, F(x,A))&Q(x,A)=>R(x,B)
Hs = {A,B,F(A,A),F(A,B),F(B,A),F(B,B),F(A,F(A,A))..}
Hs = {F(x1,..Xt):xi in Hs or xi is constant}
Saturation Ps:
Ps = {P(x1,..Xt):xi in Hs} , P is a predicate.
Herbrand base :
Hs = {φi(x1..xt):xi in Hs} , φ is a sentence.
Resolution closure :
Rs = all clause derivable by resolution on S
Herbrand’s theorem :
if a set of ground clauses S’ in S is unsatisfiable then Rs(S’) contain False.
Proof : by contradiction

Collary : Ground Resolution Complete theorem :
Informal : resolution is complete for ground sentences
Formal : if Rs(S’) does not contain False then S’ is satisfiable.
Proof : if Rs’ does not contain False then T(S’) construct by the following algorithm satisfy S’

input : S’, {A1,..,At}
for i = 1 to t
if (φ in Hs(S) and literal(φ) = {A1,..,At}
and T(A1)=False,..,T(Ai-1)=False,
and -Ai in φ )
then T(Ai) <- False
else T(Ai) <- True
return : {T(S’)}
Example :
S’ = {P(A), P(A)=>Q(A), Q(A)=>False}
As’= {P(A), Q(A), False }
Rs’= {P(A), P(A)=>Q(A), Q(A)=>False, Q(A), P(A)=>False, False}

Lifting Lemma :
Informal : for any ground resolution proof, there is a corresponding proof using the first-order sentences from which the ground sentences were obtained.
Formal: Let C1 and C2 be two clauses with no shared variables, and let C1’ and C2’ be ground instance of C1 and C2. If C’ is a resolvent of C1’ and C2’ then there exist a clause C such that (1) C is a resolvent of C1 and C2 and (2) C’ is a ground instance of C.
Graph :
C = Resolvent(C1 ,C2 ) C, C1, C2 is first order sentence.
C’= Resolvent(C1’,C2’) C’,C1’,C2’ is ground sentence.

example :
C1 = P(x,F(x,A))&Q(x,A)=>R(x,B)
C2 = N(G(y),z) => P(H(y),z)
C1’= P(H(B),F(H(B),A))&Q(H(B),A)=>R(H(B),B)
C2’= N(G(B),F(H(B),A))=>P(H(B),F(H(B),A))
C’ = N(G(B),F(H(B),A))&Q(H(B),A)=>R(H(B),B)
C = N(G(y),F(H(y),A))&Q(H(y),A)=>R(H(y),B)

Godel’s Incompleteness Theorem

Number Theory : FOL + (0, S, +, *, ^)

We can number each sentence φ with a unique natural number #φ. Number theory contains a name for each of its own sentences.
Similarly, we can number each possible proof P with Godel number G(P), because a proof is simply a finite sequence of sentence.

Now we have a set of A of sentences that are true statements about the natural numbers. Recalling that A can be named by a given set of integers, we can imagine writing in our language a sentence

φ(j,A) :
In informal form :
$i i is not the Godel number of a proof of the sentence whose Godel number is j, where the proof use only premises in A.

In formal form :
k : Godel number of a proof of sentence j
i ≠ k
A : axiom set
I! = proof(A, j)
then proof(#proof, A) = ?
if proof(#proof, A)=True then
the procedure proof should return False
(by the definition of procedure proof)
ie : proof(#proof, A)=False ><

if proof(#proof, A)=False then
the procedure proof should return True
(by the definition of procedure proof)
ie: proof(#proof, A)=True ><

Chapter 11 Planning

1. Open up representation : (state, goal, action)
Precondition => Action => Effect
2. Free to add action : Planner is free to add action to the plan wherever they are needed, rather than in an incremental sequence starting at the initial state.
3. Independent : Most parts of the world are independent of most other part. May use Divide and Conquer .

Planning in Situation Calculus
Initial state :
Goal state :
#s At(Home,s)&Have(Milk,s)&Have(Bananas,s)&(Have(Drill,s)
Operators :
$a,s Have(Milk, Result(a,s)) <=>
[(a = Buy(Milk)&At(Supermarket,s)|(Have(Milk,s) & a≠Drop(Milk)))]

Basic assumpution :
$s Result([],s) = s
$a,p,s Result([a|p],s) = Result(p, Result(a,s))

1. s = Result(A-1, Result(A,s)) // 這種情形是做白工,必須避免。

STRIP Language :
State : conjunction of function free ground literal.
Goal : conjunction of literal may contain variable.
Operator : Precondition => Action => Effect

Progression planner :
search forward from initial state to goal state.

Regression planner :
search backward from goal state to initial state.

Partial planner :
expanding the partial plan into a complete plan.

Representations for plans

least commitment : one should only make choice about things that you currently care about, leaving the other choice to be worked out later.

Partial Order planner v.s. Total Order planner

Component of Plan :
1. Plan Steps : operator set.
Example :
Start :Op(ACTION:Start),
Finish :Op(ACTION:Finish,PRECOND:RightShoeOn & LeftShoeOn)}
2. Ordering constraint (Si < Sj)
Example : Start < Finish
3. Variable binding constraint

4. Causal links : Si –— (c) —> Sj
(Si achieve the precondition of Sj)
Start –
(LeftShoeOn, RightShoeOn)—-> Finish

Achieved : Si achieved a precondition c of the Sj iff
1. Si < Sj and C in EFFECTS(Si)
2. !# Sk, Si<Sk<Sj and (-c) in EFFECTS(Sk)

Contradiction :
Ordering contradiction : Si < Sj and Sj < Si
Binding contradiction : v = A and v = B

Complete Plan :
Every precondition of every step is achieved by some other step.

Consistent Plan :
No Contradiction in the ordering or binding constraint.

Partial Order Planning Algorithm
function POP(initial, goal, operator) returns plan
plan := MAKE-MINIMAL-PLAN(initial, goal)
loop do
if SOLUTION?(plan) then return plan
S[need], C := SELECT-SUBGOAL(plan)
CHOOSE-OPERATOR(plan, operators, S[need], C)

function SELECT-SUBGOAL(plan) return S[need], C
pick an plan step S[need] from STEPS(plan)
with a precondition C that has not been achieved
return S[need], C

procedure CHOOSE-OPERATOR(plan, operator, S[need], C)
choose a step S[add] from operators or STEPS(plan) that has C as effect
if there is no such step then fail
add the causal link S[add]-(c)-> S[need] to LINK(plan)
add the ordering constraint S[add]-(c)-> S[need] to ORDERINGS(plan)
if S[add] is a newly added step from operator then
add S[add] to STEPS(plan)
add Start < S[add] < Finish to ORDERINGS(plan)

procedure RESOLVE-THREATS(plan)
for each S[threat] that threatens a link Si (c)>Sj in LINK(plan) do
choose either
Promotion : Add S[threat] to ORDERINGS(plan)
Demotion : Add Sj < S[threat] to ORDERINGS(plan)
if not CONSISTENT(plan) then fail

example : Shoes and Socks Problem
Step : S[]
S[∞](ACTION:Finish, PRECOND:RightShoeOn & LeftShoeOn)
Operator : Op[]
OP[3]:(ACTION:LeftShoe, PRECOND:LeftSockOn, EFFECT:LeftShoeOn)
OP[4]:(ACTION:RightShoe, PRECOND:RightSockOn,EFFECT:RightShoeOn)
Condition : C[]
C[1] : LeftSockOn
C[2] : LeftShoeOn
C[3] : RightSockOn
C[4] : RightShoeOn

initial plan :
Plan = STEP:{Start :Op(ACTION:Start),
PRECOND:RightShoeOn & LeftShoeOn)}
ORDERING : {Start < Finish}
LINKS : {}

Start(S0) -(LeftShoeOn, RightShoeOn) -> Finish(S5)

2 : S[need], C = SELECT-SUBGOAL(plan)
S[need] = LeftShoeOn, C = NULL

3 : S[need], C = CHOOSE-OPERATOR(plan, op[], S[need], C)
S[need] = OP3(LeftShoe)
OP3(LeftShoe)(LeftShoeOn)> Finish //S[add](c)> S[need]

Chapter 12 Practical Planning

Operation Research : PERT chart, critical path method.

4 concept that STRIP does not support
Hierarchical Plans
STRIP doesn’t allow abstract step
example :
high level : Build(House)
middle level : Install(floor)
low level : Hammer(Nail)

Complex conditions
STRIP allow variable only use in limit way
example : $x ..

STRIP is based on situation calculus
example : concurrency , deadline, duration action

STRIP cannot handle constraints on resources efficiently.

Least commitment

Hierarchical Decomposition
example :
Own land Have house
Buy land ---> Build ---> Move in
Get loan --—-> House
Have money

Own land
Buy land>Obtain Permit↘Construct-> Pay Builder> Move in
Hire Builder↗ ↗
Get loan------

Primitive operator
ex : Hammer(Nail)
Nonprimitive operator
ex : Install(FloorBoards)

Decomposition Method : Decompose(operator, plan)
ex : Decompose(Construction,
ORDERING:{S1<S2<S3<S5, S2<S4<S5},
LINKS:{S1->S2, S2->S3, S2->S4, S3->S5, S4->S5}))

p correctly implement o iff
1. p is complete and consistent
2. Effect(o) in Effect(p)
3. Precondition(Pi) in (Effect(Pi) + Precondition(o))

function HD-POP(plan, operators, methods) returns plan
input : plan, an abstract plan with start and goal steps
loop do
if SOLUTION?(plan) then return plan
S[need], C := SELECT-SUB-GOAL(plan)
CHOOSE-OPERATOR(plan, operator, S[need], C)
S[nonprim] := SELECT-NONPRIMITIVE(plan)
CHOOSE-DECOMPOSITION(plan, methods, S[nonprim])

Data structure
STEPS += STEPS(Decompose(o,p)) - nonprim(o,p)
BINDING += BINDING(Decompose(o,p))
Sa < S[nonprim] => add Sa < Sm, ($j Sm !< Sj)
S[nonprim] < Sz => add Sm < Sz, ($j Sj !> Sm)
Si -(c)-> S[nonprim] => Si -(c)-> Sm($j Sm !< Sj)
S[nonprim] -(c)-> Si => Si -(c)-> Sm($j Sj !> Sm)

Analysis of Hierarchical Decomposition
downward solution property :
abstract-solution(p) => primitive-solution(x) & abstract(x,p)
upward solution property :
primitive-solution(x) => abstract-solution(p) & abstract(x,p)

Complexity of POP : b^s^d = O(b^s^d)
Complexity of HD-POP : Σbs^i = O(b*s^d)
b: branching factor
s: steps in a decomposition method
d: depth of the hierarchical plan

unique main subaction condition
Decompose(Operator, Plan(STEPS:{S1:..,S2:..,..}

Sharing : getMerried↗ honeyMoon

Critics : plan -> critics -> modified plan

Hierarchical Decomposition :
abstract, nonprimitive can be decomposed into a more complex network of step

Abstract Hierarchy (approximation hierarchy) :
critical condition in level1 ex : Buy1
critical condition in level1+level2 ex : Buy2

critical : 買奶粉時,可能找對商店很重要,買房子時,有錢才是most critical condition.

Confrontation (對質): -c’ when p,
may resolve threat by making sure that p doesn’t hold.

Negate :
unify(p, —p)
unify(-p, -p) & unify(-p, initial has no p)

Disjunctive precondition:
implement : e when p|q => e when p, e when q
如此可以使back track容易 implement。

Disjunctive goal :
ex: Flip(coin) => Heads(coin)|Tails(coin)
implement : 很難處理。

Universal quantification
example :
Op(ACTION: Carry(bag,x,y),
EFFECT: At(bag,x),-At(bag,x)&$i Item(i) => At(i,y)&-At(i,x)) when In(i,bag))
注意:加上universal quantifier後,仍然不是FOL,因為只允許finite, static, typed universe of object
static : object cannot change type or be destroyed.
Implement :
$x T(x) => C(x) —> C(x1)&C(x2)&..&C(xn)
example :
Initial state : Bag(B)&Milk(M1)&Milk(M2)&Milk(M3)
Expression : $x Milk(x) => In(x,B)
Expansion : In(M1,B)&In(M2,B)&In(M3,B)

actual - non actual object
加上actual property可以解決無法dynamic create object的問題。

Resource Constraint
measures fluents : 隨時間而變動的measures.
Example :
Effect: Cash := $(12.50) &
GasLevel := Gallons(5)

Rough Check : by minimum and maximum possible constraint
if minimum(x) < measure(x) < maximum(x) then go on
else fail
Temporal Constraint :
example :
suppose it takes 10 seconds to pump each gallon of gas ,
then the time consume by Fillup action is :
Time := Time + Minutes(3)

Chapter 13 Planning and Action

Conditional Planning (contingency planning) : (事先規劃)
including sensing action in the plan to test for the appropriate
example :
$x,s Tire(x)=>KnowsWhether(“Intact(x)”,Result(CheckTire(x),s))
Op(ACTION: CheckTire(x),
PRECOND: Tire(x),
EFFECT: KnowWhether(“Intact(x)”))
CheckTire(x) is called conditional step,
Links from CheckTire is called conditional link.

Parameterized plans :
example :
Color(Chair, c) & Color(Table, c)

Run time variable :
example :
$x,s #c KnowWhat(“Color(x,c)”, Result(SenseColor(x),s))

Op(ACTION: SenseColor(x),
EFFECT: KnowWhat(“Color(x,c)”))

Execution monitoring (replanning) : (事後治療)
monitoring is any things goes wrong, if “yes” then replanning.

Cause of plan failure :
Bounded indeterminacy (可事先列舉的):
Unbounded indeterminacy (不可事先列舉的):

Triangle table : 比較precondition of plan和percept
Action monitoring : 比較precondition of action 和percept

Situated agent continuously monitors the world, updating its world model from new percepts even if its deliberations are still continuing.
Example :
block world with impatient teacher move the block before agent move it and clumsy agent drop block in incorrect position.

Coercion (強制): reduce uncertainty about world by forcing it into a known state regard the initial state.
Example : paint table and chair together to make sure they are in the same color.

Abstraction : ignore detail of a problem about which it may not have exact and complete knowledge.
Example : Fly(London, Paris)

Aggregation : individual uncertainty eliminated by statistic.
Example : Government plan its cash flows.

Chapter 14 Uncertainty
- because of laziness or ignorance in complex, dynamic or inaccessible system.

Laziness : rule too much
Theoretical ignorance : 理論上不完備。
Practical ignorance : 實作上不符合成本。

Decision Theory = probability theory + utility theory ( measure by preference )

Axiom of Probability
axiom 1. 0 ≦ P(A) ≦ 1
axiom 2. P(True) = 1 P(False) = 0
axiom 3. P(A+B) = P(A) + P(B) - P(AB)

axiom 3 的意義為 : 若有人賭博不遵照 axiom 3 的比率下注,則對手一定可以找出一組解,使其必輸,請看下例:

Agent 對手 A&B A&-B -A&B -A&-B

A 0.4 A 4 to 6 -6 -6 4 4
B 0.3 B 3 to 7 -7 3 -7 3
A or B 0.8 A+B 2 to 8 2 2 2 -8

total -11 -1 -1 -1

Bayes' Rule
P(B|A) = P(A|B)P(B)/P(A)

P(Y|X,E) = P(X|Y,E)P(Y|E)/P(X|E)

= P(A|E1)* P(E2|E1A)/P(E2|E1)
= P(A)*P(E1|A)/P(E1)*P(E2|E1A)/P(E2|E1)
if conditional independence hold then
P(A|E1E2) = P(A)*P(E1|A)/P(E1)*P(E2|A)/P(E2|E1)

Chapter 13 : Planning and Acting
Conditional planning (contingency(偶然性的) planning):
sensing action :
Execution monitoring (replanning when monitor new event):

Chapter 15 : Probabilistic Reasoning Systems

Belief Network :
1. node (X) : X is a random variable.
2. link (X,Y) : X has a direct influence on Y
3. node (X) has conditional probability table
4. The graph has no directed cycles.

Burglary Earthquake
P(B)=0.1 P(E) = 0.2
↖ ↗
B E P(A)
T T 0.95
T F 0.94
F T 0.29
F F 0.001
↙ ↘
JohnCalls MaryCalls
A P(J) A P(M)
T 0.90 T 0.70
F 0.05 F 0.01

Incremental Belief Network Construction Algorithm
1. Choose the set of relevant variable Xi that describe the domain
2. Choose an ordering for variables
3. While there are available left :
(a) Pick a variable Xi and add a node to the network for it
(b) Set Parent(Xi) to some minimal set of nodes already in the net such that the conditional
independence property
P(Xi|Xi-1,…X1) = P(Xi|Parents(Xi))
(c) Define the conditional probability table for Xi.

Canonical Distribution (看看有沒有標準的機率分佈可以套用)。

D-seperation (direction-dependent separation)
用來決定一組 nodes X 與另一組 nodes Y 是否 independent.
If every undirected path from a node in X to a node in Y is d-separated by E, then X and Y are conditionally independent given E.

Blocked :


case1: *—*>z>*——*

case2: *—*<z>*——*

case3: *—*>z<*——*
↙ ↘
* *
If every undirected path from a node in X to a node in Y is blocked given E,
then X and Y is D-separate by E.

Answer queries Algorithm : calculate P(X|E)

P(X|Ex+) = Σ(P(X|u)*MUL(P(Ui|Eui\x)
P(X|Ex-) = b*MUL(Σ(P(Eyi-|yi))*Σ(P(yi|X,zi))*MUL(P(zij|Ezij\yi))
P(X|E) = a*P(Ex-|X)*P(X|Ex+)

Four Kind of Uncertain Reasoning
Diagnostic Inference (from effect to causes)
Causal Inference (from cause to effects)
Intercausal Inference (between causes of a common effect)
P(Burgery|Alarm and Earthquake)

Dempster-Shafer Theory

Belief function : Bel(X)
Case1 : Before examing/toss a coin, we don't know if it's unbiased.
Bel(Head) = Bel(-Head) = 0
No reason to accept it and no reason to decline it for gamble 10$ dollors.

Case2 : After examing a coin
Bel(Head) = Bel(-Head) = 0.45
No reason to accept it and no reason to decline it for gamble 10$ dollors.
But it's different, isn't it.

Probability interval interpretation :
Case1 : Bel(Head)= Bel(-Head)=0 ==>Prob. Interval =[0.. 1 ]
Case2 : Bel(Head)= Bel(-Head)=0.45==>Prob. Interval =[0.45.. 0.55]

My Idea : 是否可以使用極限值來定義 P(A<or>B) 呢?
P(Head0) = 0.5
P(Tail0) = 0.5
P(Head0<or>Tail0) = 1.0
P(Head0<or>Head1) = 1 - 0.5*0.5 = 0.75
關鍵在 Covariance.

The merit of deterministic logic reasoning
1. Monotonicity (累積遞增性):
The set of beliefs grow monotonically over time as new evidance arrives。

2. Locality (區域性)
只要看 A, A<imp>B 就可以確定 B, 與其他 rule 都無關,因為保證 consistent.

3. Detachment (可分離性)
A, A<imp>B ==> B, 一旦 B 產生了,我們就不需再管 B 是從哪裡來的了。

4. Truth functionality (計算簡易性)
The truth of complex sentences can be computed from the truth of the

Fuzzy Logic :
Fuzzy logic 與 Uncertain logic 是正交的,Fuzzy 處理的並非不確定性,
example :
Tall(John) = 167 cm
TallPerson(John) = 0.3
我們知道 John 確定的身高,只是人的思考模式並不是有確定分界的,並非二值邏
輯,因此、Fuzzy 實際上與 Uncertain 是正交的 model .

Chapter 16 : Making Simple Decisions

Utility Theory
Maximum expected utility principle (MEU)
Expected Utility :
EU(A|E) = Σ(P(Result_i(A)|E, Do(A))*U(Result_i(A)))
Lottories (樂透, 彩卷):
L = [p, A; 1-p, B]
A > B, A is preferred to B
A ~ B, indifferent between A and B
Expect monetary value (EMV(L))
U(S(L)) < U(SEMV(L))
Strict dominance in multiattribute utility function:
(x1, …, xn) ≧ (y1, … yn) iff xi≧yi for all i
Representation theorem
U(x1,…,Xn) = f[f1(x1),…,fn(xn)]
Stochastic Dominance
for all x, Integrate p1(x') dx' ≧ Integrate p2(x') dx'
Mutual preferential independence (MPI)
The preference of attributes set are not interfere by other attributes
V(S) = Σ(Vi(Xi(S)))
Utility independence
The utility of lotteries on the attributes are independent of other attributes
U = k1U1+k2U2+k3U3+k1k2U1U2+k1k2U1U2+k2k3U2U3+k3k1U3U1+k1k2k3U1U2U3
Value of perfect information (VPI)
EU(a|E) = max Σ U(Result_i(A))*P(Result_i(A)|E, Do(A), Ej)
VPI(Ej) = Σ P(Ej=ejk|E)*EU(a_ejk|E,Ej=ejk) - EU(a|E)
for all j, E VPI(Ej)≧0
VPI(Ej,Ek) ≠ VPI(Ej)+VPI(Ek)
Myopic agent : 只考慮 VPI 的 agent
The step to build a decision-theoretic expert system
1. Determine the scope of the problem
2. Lay out the topology
3. Assign probability
4. Assign utility
5. Enter available evidence
6. Evaluate the diagram
7. Obtain new evidence
8. Perform sensitivity analysis

Chapter 17 : Making Complex Decision

Policy :
A complete mapping from states to actions is called a policy.

Markov property
P(xk+1|xk,…x1) = P(xk+1|xk)

Markov decision problem (MDP)
Agent know exactly xk.

Partially observable Markov decision problems (POMDP)
Agent unsure xk, only know by probability.
U(A) = U(A|xk(1)) + … + U(A|xk(n))

Value Iteration

Calculate utility of each state, U(state), and use them to select
an optimal action in each state.

History of Policy :
H(state, policy) : the history tree starting from state and taking action according to policy.

U(i) = EU(H(i, policy*|M) = Σ P(H(i, policy*)|M) Uh(H(i, policy*))

History Separability :
Uh([s0, s1, …, sn]) = f(s0, Uh([s1,…,sn]))

History Additive :
Uh([s0, s1, … , sn]) = R(s0) + Uh([s1,…,sn])

Maximum Expected Utility Policy :

policy*(i) = arg max Σ Maij U(j)
a j

U(i) = R(i) + max Σ Maij U(j) — dynamic programming
a j
If environment histories are potentially of unbounded length because of loops, then

Ut+1(i) = R(i) + max Σ Maij Ut(j)
^ a
reward function

// 一直利用條件機率來預測改善整個 state U[i], 直到無法改善為止.
function VALUE-ITERATION(M, R) returns a utility function
input: M, a transition model
R, a reword function on states
local: U, utility functions , initially identical to R
U',utility function, initially identical to R
U = U'
for each state i do
U'[i] = R[i] + max Σ Maij Ut(j)
until CLOSE-ENOUGH(U, U') // Use Root Mean Square (RMS) to measure.
return U

Policy Iteration

function POLICY-ITERATION(M, R) returns a policy
inputs : M, a transition model
R, a reward function on states
local : U, a utility function, initially identical to R
P, a policy, initially optimal with respect to U
unchanged? = true
for each state i do
if max Σ Mij(a) U[j] > Σ Mij(P[i]) U[j] then

P[i] = arg max Σ Mij U[j]

unchanged ? = false
until unchanged?
return P

1. Ut+1(i) = R(i) + Σ Mij(Policy(i)) Ut(j)
// where policy(i) is the action suggested by the policy in state I

2. U(i) = R(i) + Σ Mij(P(i)) Ut(j)

Decision Theoretic Agent

function DECISION-THEORETIC-AGENT(Et) returns an action
inputs : Et, the percept at time t
static : BN, a belief network with node X
Bel(X), a vector of probabilities, updated over time
Bel(Xt) = Σ P(Xt|Xt-1=xt-1, At-1) Bel(Xt-1=xt-1) // may use belief network
Bel(Xt) = c P(Et|Xt) Bel(Xt) // may use kalman filtering
action = arg max Σ [ Bel(Xt=xt) Σ P(Xt+1 = xt+1 | Xt = xt, At) U(Xt+1) ]
At Xt Xt+1

return action

Sensing in uncertain worlds
step1 : build stationary sensor model : for all t P(Et|Xt) = P(E|X) include the possibility of sensor failure to handle it.
P(alarm | earthquake), P(alarm | burgeler )

step2 : break apart the generalized state and sensor variable into their components. The crucial thing is that the sensor values are conditionally independent of each other, given the actual value.
(Pressure * Temperature, Pressure/Temperature) —> (Pressure, Temperature)
sensor fusion (data fusion) :
Example :
Gauge Temperature(sensor1) = 13.6 accuracy of sensor1 = ± 0.5
Gauge Temperature(sensor2) = 14.4 accuracy of sensor2 = ± 0.5
inference : temperature range 13.9 ~ 14.1

Dynamic Belief Networks :
A belief network with one node for each state and sensor variable, for each time step.

Goal: calculate the probability distribution for the state at time t.

Probabilistic projection : predicate the probability distribution for State(t+1)

Markov chain (state evolution model) :
Prediction : Bel(Xt-1) -> Et-1 -> Bel(Xt)
Rollup : P(Et|Xt) , Bel(Xt) -> Bel(Xt)

Estimation : Bel(Xt) -> Et -> Xt+1

Dynamic Decision Network :

Add utility node on Dynamic Belief Network
Prediction : Bel(Xt-1) + Dt-1 -> Et-1 -> Bel(Xt)
Rollup : P(Et|Xt) , Bel(Xt) -> Bel(Xt) <—-+
^ |
Estimation : Bel(Xt) -> Et + Dt -> Bel(Xt+1) -+

Chapter 18 Learning From Observation

Critic <--- Sensor <-- E
| | N
| | V
Learning -
--> Performance I
element / element R
| / | O
| / | N
Problem / Effector -—> M
generator E
| N

Performance element
1. condition -> action
2. percept -> property
3. world(Xn) -> world(Xn+1)
4. world(Xn, action) -> world(Xn+1)
5. utility(world(Xn))
6. utility(world(Xn, action))
7. isGoal(world(Xn))

Supervised learning : got correct outcome from environment.
Reinforcement learning : got utility value from environment.
Unsupervised learning : use an internal utility function.

Pure inductive inference :
Given a collection of examples of f, return a function h (hypothesis) that approximate f.

Bias :
Any preference for one hypothesis over another, beyond mere consistency with the example, is called a bias.

Ockham's razor (奧砍剃刀) :
The most likely hypothesis is the simplest one that is the simplest one that is consistent with all observations — The world is inherently simple.

Decision tree :
Example :
+ X1,X3,X4,X6,X8,X12
- X2,X5,X7,X9,X10,X11
Patron ?
/ | None Some Full
+ +X1,X3,X6,X8 +X4,X12
- X7,X11 - X2,X5,X9,X10
Will wait? Will wait? Hungary?
= yes = no / Yes No
+X4,X12 +
-X2,X10 -X5,X9

Training & Measure Process :
1. Collect a large set of example.
2. Divide it into two disjoint sets : the training set and the test set.
3. Use the learning algorithm with the training set as examples to generate a hypothesis H.
4. Measure the percentage of examples in the test set that are correctly classified by H.
5. Repeat steps 1 to 4 for different size of training set and different randomly selected training sets of each size.

Choosing attribute by Information Theory

Average Information in an Answer :
p: positive example
n: negative example

Remainder information of attribute A:
Remainder(A) = Σ (pi+ni)/(p+n) * I(pi/(pi+ni), ni/(pi+ni))
Information gain of attribute A :
Gain(A) = I(p/(p+n), n/(p+n)) - Remainder(A)

1 *
0.5 * *
0 * *
0 p+n/2 p+n

Overfitting Problem : Find meaningless "regularity" in the data.

Decision tree pruning :
(use to eliminate noise and overfitting problem)
How to detect an irrelevant attribute ?

Unbiased estimate value :
pi' = p*(pi+ni)/(p+n) ni' = n*(pi+ni)/(p+n)

Deviation :
D = Σ ((pi-pi')^2/pi' + (ni-ni')^2/ni)

Chi-Square pruning
Use Chi-Square distribution with freedom degree v-1 to pruning the range that
out of the belief range (ex : 5% pruning).

Cross validation (use to eliminate noise and overfitting problem) :
Training data —build model —> hypothesis — estimate result of test data —> performance

Training data <== independent ==> Test data

Version space :

VersionSpace(examples) returns a version space
local variable : V, the version space
V= the set of all hypothesis
for each example e in examples do
if V is not empty then V=VersionSpaceUpdate(V,e)
return V

G-set :
the most general boundaryset , {G1,G2…}
S-set :
the most specific boundary set, {S1,S2…}

Version space update process
False positive for Si
情況:Si 預測 true, 實際為 false
動作:throw Si out of the S-set
False negative for Si
情況:Si 預測 false, 實際為true
動作:generalize Si
False positive for Gi
情況:Gi 預測 true, 實際為false
動作:specialize Gi
False negative for Gi
情況:Gi 預測 true, 實際為false
動作:throw Gi out of G-set

Belief Network :
Computational Learning Theory :
PAC(Probably Approximately Correct) learning :
Any hypothesis that is seriously wrong will almost certainly be “found out” with high probability after small number of examples.

Stationary assumption (introduced by Valiant):
the training set and test set are drawn randomly from the same population of examples using the same probability distribution.

How many example are needed :
問題:到底要給多少個example後,才能讓程式學到正確率 > 1-δ的hypothesis.
Ie: What’s minimal |s| s.t. P(error(h,h’(s)) < ε) > 1-δ ?

X : the set of all possible examples
D : the distribution from which examples are drawn
H : the set of possible hypothesis
m : the number of examples in the training set

error(h) = P(h(x)≠f(x)), x in D
h is approximately correct iff error(h) < ε
Hbad = H - εball
P(Hbad agree with m example) ≦ (1-ε)^m
P(Hbad contains a consistent hypothesis) ≦ |Hbad|*(1-ε)^m
≦ |H|*(1-ε)^m
|H|*(1-ε)^m < δ
|S| = m ≧ 1/ε(ln(1/δ)+ln(|H|))

Contingency(意外) problem (Chapter 13) :
Each branch of the tree deals with a possible contingency that might arise. (Solved by interleaving of search and execution.)

Chapter 19 : Learning in Neural and Belief Network
Step function :

Perceptron :

Hebb’s rule :

Linear separable function :

Proof that XOR cannot learn by perceptron

Back-Propagation Learning

Bayesian Learning

Chapter 20 Reinforcement Learning
在沒有正確答案的情況之下,Agent可經由operation的存活結果來做學習,叫做reward (reinforcement) learning.

Passive learner : just observe the world going by, tries to learn the utility of being in various states.

Active learner : act using the learned information, and use its problem generator to suggest explorations of unknown portions of environment.

Learn result :
1. learn utility function .
2. learn action-value function (Q-learning)

Passive Learning in a known Environment (Mij已知)
LMS(least mean square) approach
缺點:the utility of states are not independent
U(state) = ΣP(successor)*U(successor) + R(state)
U : utility, P: probability, R: reward

ADP(adaptive dynamic programming) approach
U(i) = R(i) + ΣMij*U(j)
優點: 有考慮model (Mij)

TD(temporal difference) approach
U(i) = U(i) + α * (R(i)+U(j)-U(i))
優點:快速、不需算 ΣMij*U(j)

Passive Learning in an Unknown Environment (Mij未知)

Prioritized-sweeping heuristic
prefer adjust states whose likely successor have just undergone a large adjustment in their own utility estimates.

Active Learning in a known Environment (Mij已知)
U(i) = R(i) + maxΣMija*U(j)

Wacky approach : act randomly, in the hope that it will eventually explore the entire environment.

Greedy approach : act to maximize its utility using current estimate.
缺點:stick to local optimal path.

Hybrid approach : agent should more wacky when it has little idea of the environment, and more greedy when it has a model that is closed to being corrent.

Bandit problems : n arm bandit problem
Las Vegas的電動,有一個n個手臂的海盜,改levers(槓桿) 的(on,off), 以期使得到的錢最多。

Optimistic approach
U+(i) = R(i) + max f(ΣMija*U+(j), N(a,i))
U+(i) : optimistic estimate of the utility (expected reward).
N(a,i): the number of times action a has been tried in state i.
f(u,n): exploration function.

Action Value Function learning

Q(a,i) : the value of doing action a in state I

U(i) = max Q(a,i)

ADP Q learning : Q(a,i) = R(i) + Q(a,i) ΣMija max Q(a’,j)
j a

TD Q learning : Q(a,i) = Q(a,i) + αR(i) + max Q(a’,j) - Q(a,i)

Implicit representation & input generalization:
U(I) = w1f1(i) + .. + wnfn(i)
w = w + α[r+Uw(j) - Uw(i)]▽wUw(i)

Chapter 21 Knowledge in Learning
Goal : learning when you already know something.

Entailment constraint :
Hypothesis & Description ╞ Classification

EBL (explanation based learning)
目的: 節省search的時間,事先導出有用的規則並記錄到到KB中。
Model :
Hypothesis & Description ╞ Classification
Background ╞ Hypothesis
Step 1: 建立proof tree.
Step 2: 建立variable proof tree.
Step 3: 將一個subtree 視為一個rule.
Step 4: 將與變數值無關的variable binding丟掉,用variable代替。

example :
Rule set :
Rewrite(u,v) & Simplify(v,w) => Simplify(u,w)
Primitive(u) => Simplify(u,u)
ArithmaticUnknown(u) => Primitive(u)
Number(u) => Primitive(u)

Proof : Simplify(1*(0+x),w)

Step 1 : build proof tree:
/ Rewrite(1*(0+X),v) Simplify(0+X,w)
Yes, {v/0+x} / Rewrite(0+X,v’) Simplify(X,w)
Yes, {v’/X} | {w/X}
Yes, {}

Step2 : build variable proof tree

/ Rewrite(x*(y+z),v) Simplify(y+z,w)
Yes, {x/1,v/y+z} / Rewrite(y+z,v’) Simplify(z,w)
Yes, {y/0,v’/z} | {w/z}
Yes, {}
Step 3 : extract subtree

Step 4 : generalize variable, x/1 -> x
Simplify(y+z,w) => simplify(1*(y+z),w)

RBL (relevance based learning) (Data Mining)
目的:找minimal consistent determination.
Model :
Hypothesis & Description ╞ Classifications
Background & Description & Classifications ╞ Hypothesis
Example : Material & Temperature => Conductance

RBDTL (relevance based decision tree learning)
目的:用decision tree algorithm 來找minimal consistent determination.

KBIL (knowledge based inductive learning)
ie : Inductive Logic Programming (ILP)
目的:Attribute based learning algorithms are incapable of learning relational predicates, so use KBIL to learn relational predicates.
Model :
Background & Hypothesis & Description |= Classifications

Inverse resolution :
Resolution : C1 ; C2 => C
Inverse resolution : C ; C1 => C2
example :
Parent(Elizabeth,y)=>Grandparent(George,y) T=>Parent(Elizabeth,Anne)
↖ ↙
T=>Grandparent(George,Anne) Grandparent(George,Anne)=>F
↖ ↙
True => False

Constructive induction : Algorithm that generate new predicates

FOIL(First order inductive learning) by decision tree
example :
Goal : ? => Grandfather(x,y)

reverse reasoning : Father(x,y) => Grandfather(x,y)
Parent(x,y) => Grandfather(x,y)
Father(x,z) => Grandfather(x,y)

Father(x,z)&Parent(z,y) => Grandfather(x,y)

名言: Russel & Whitehead , “Civilization advances by extending the number of important operations that we can do without thinking about them“.

Chapter 22 Agent that Communication
| |
製作工具 直立(鼻子離地太遠)
| 鼻子不夠靈敏 (無法辨認食物及方位)
| 用聲音代替(語言發展)
↓ ↓

Inform : There’s a breeze here in 3,4.
Query : Have you smelled the wumpus anywhere ?
Answer : Yes, I smelled the wumpus in 2,5
Request : Please help me carry the gold.
Promise : I’ll shoot the wumpus if you let me share the gold.
Acknowledge : OK
Share : Shoot when you smell smash is a good policy.

Communication Model
步驟 描述 範例
Speaker :
Intention S wants H to believe P Know(H, -Alive(Wumpus, S3)
Generation S choose word W “The Wumpus is dead”
Synthesis S utter the word W [thaxwahmphsihzdeyd]

Perception H perceives W’ “The wumpus is dead”
Analysis H infer that W’ has [[The(Article) wumpus(Noun)]
possible meaning [is(Verb) dead(adjective)]]
Disambiguation H infer that S intend -Alive(Wumpus,S3)
to convey Pi
Incorporation H decide to believe TELL(KB, -Alive(Wumpus,S3))
or reject or ignore Pi.

Language Class Sample Rule Sample Language
Recursive Enumerable AB->C any
Context sensitive AB->BA anbncn
Context free S->a S b anbn
Regular S->a S a*b*

Encoded message model (Shannon style):
P (encode)-> W (decode)> P

Situated language:
P(s)—(encode)-> W —(decode) —> P(s’)
is situation s’ = s ?

Communication Agent的 Knowledge base maintain 問題:
1. 同一symbol(s)在 A,B 中表示不同意義
解法:symbol 加上agent 的名稱。

2. A(s1) <- relation -> B(s2)
解法:用formula代替 symbol。
example : TELL(B.KB, “#p,s Pit(p) & At(p,[2,3],s)”)

3. bandwidth is limited (決定在有限的接觸時間下要溝通哪些問題呢?)
4. Agent may lie (欺騙問題)

Master-Slave model :
Slave execute the command of master.

Example :

Slave Master
I feel breeze go to 1,2
Nothing is here go north
I feel a breeze go east
I smell a stench ..
I see a glitter Grab it

translate BNF into First Order Logic
S->NP VP NP(s1)&VP(s2) => S(Append(s1,s2))
Noun->stench|.. (s=”stench”|..)=>Noun(s)

DCG (definite clause Grammar) : a restricted FOL Grammar

unargumented nonterminal + argumented nonterminal

variable representing a terminal + constant terminal

logical test

X->YZ.. Y(s1)&Z(s2)&.. => X(Append(s1,s2..))
X->word X([“word”])
X->Y|Z|.. Y’(s)|Z’(s)|..=>X(s)
Double->w w (s1=[w]&s2=[w])=>Double(Append(s1,s2))

Y’ : means the DCG expression of Y

Overgenerates : generate some sentence that are ungrammatical
Case : NP(case)->Pronoun(case) 進一步細分nonterminal category
Agreement : NPS ->PronounS , NPo->Pronouno

example :
S->NP(subjective) VP |.. (註:Augmentation)
NP(case) -> Pronoun(case) | Noun | Article Noun | .. (註:Case)
VP -> VP NP(Objective) | .. (註:Augmentation)
PP -> Preposition, NP(Objective)
Pronoun(Subjective) -> I | you | he | she |..(註:Augmentation)
Pronoun(Objective) -> me | you | him | her |.. (註:Augmentation)

Argumented Grammar > context free Grammar

example : argumented Grammar for anbncn
A(0)-> ε A(n+1)->a A(n)
B(0)-> ε B(n+1)->b B(n)
C(0)-> ε C(n+1)->c C(n)

Semantic Interpretation

Syntactic form -> Quesi-Logical form

example :
Grammar :
Name(Johnson) -> Johnson
Name(Fanny) -> Fanny
Verb(λyλx Loves(x,y)) -> Loves
quantified term : $a Agent(a)

Quesi logical form : #e e in Has([$d Dog(d)], Day(a), Now)

intermediate in quasi-logical form
example :
Category Type Example Quesi-Logical form
S sentence I sleep #e e in (Sleep,Speaker)
Adjective object->sentence smelly λx Smelly(x)
Adverb event->sentence today λe During(e,today)
Article Quantifier the #!
Conjunction sentence->sentence and λp,q (p&q)
Digit Number 7 7
Noun object->sentence wumpus λx Wumpus(x)
Preposition object->sentence in λxλy In(x,y)
Pronoun Object I Speaker
Verb object->sentence eats λxλy#e e in
NP Object a dog Dog(d)
PP object->sentence in [2,2] λx In(x,[2,2])
RelClause object->sentence that sees me λx #e e in
VP object->sentence sees me λx #e e in Sees(x,Speaker)

Semantic Parse Tree

S(#e e in Perceive([$a Agent(a)], [#w Wumpus(w), Nose)) & During(Now, e)
/ / VP(λx #e e in Perceive([#w Wumpus(w), Nose)) & During(Now,e)
NP([$a Agent(a)]) / \
/ \ / NP(Wumpus(w))
Article($) Noun(Agent) / / | | Verb(λyλx #e e in Article(#) Noun(Wumpus)
| | Perceive(x,y, Nose)) | |
| | & During(Now,e) | |
| | | | |
Every agent Smells a wumpus

parse tree :
“Johnson loves Fanny”
S(rel(obj)) -> NP(obj)VP(rel)
“loves Fanny” => λx Loves(x, Fanny)
“Johnson loves Fanny” => (λx Loves(x, Fanny))(Johnson)

S(Loves(Johnson, Fanny))
/ NP(Johnson) VP(λx Loves(x, Fanny))
| / Name(Johnson) Verb(λy, λx Loves(x, y)) Name(Fanny)
| | |
Johnson loves Fanny

Syntactic form - parse tree
intermediate form - Quesi-Logical form
Semantic form - First-Order logic

Quesi-logical form -> First Order Logic
transform rule :
[$x P(x)] -> $x P(x) => QLF
P(x) -> #x P(x) & QLF
example :
QLF : #e e in Has([$d Dog(d)], Day(a), Now)

FOL1: $d Dog(d) => #a Day(a) & #e e in Has(d, a, Now)
semantic : “each dog has his own day”

FOL2: #a Day(a) & $d Dog(d) => #e e in Has(d, a, Now)
semantic : “there is a special day that all dog share”

Pragmatic Interpretation (實際的解釋)
I -> Speaker
today -> Now

lexical ambiguity (一字多義)
example :
hot 1. 溫度高2. 很搶手

syntactic ambiguity (structural ambiguity) (語法性歧義)
example :
I smelled a wumpus in 2,2
I smelled [a wumpus in 2,2]
I [smelled a wumpus] in 2 2

semantic ambiguity (語意性歧義)
example :
A coast road.
1. 通往海岸的路。
2. 濱海公路。

referential ambiguity(指稱性歧異)
example :
1. it -> ?
2. Johnson -> Johnson Chen or Johnson Liu

pragmatic ambiguity(實用上的歧異)
example :
1. next Friday (本週五還是下週五呢?)

local ambiguity (地區性歧異)
A substring can be parsed several ways, but only one of those way fit into toe larger context of the whole string.

example :
1. the radio broadcast (information)
2. the radio broadcast (inform)
3. * in c++ means pointer or multiply.

example :
hot : 幾度以上算hot呢?

1. world model
2. mental model
3. language model
4. acoustic model (聽覺的模型)

Chapter 23 Practical Natural Language Processing

ELIZA : Simulate the behavior of a therapist

A Bit of a Dialogue with ELIZA:
Person : Men are all alike.
ELIZA : In what way ?
Person : They’re always bugging us about something or other.
ELIZA : Can you think of a specific example ?
Person : Well, my boyfriend made me come here.
ELIZA : Your boyfriend made you come here.
Person : He says I’m depressed much of the time.
ELIZA : I am sorry to hear you are depressed.
Person : It’s true. I am unhappy.
ELIZA : Do you think coming here will help you not to be unhappy?
Person : I need some help, that much seems certain.
ELIZA : What would it mean to you if you got some help?
Person : Perhaps I could learn to get along with my mother.
ELIZA : Tell me more about your family

Some Rules in ELIZA:

(X me Y) -> (X you Y)
(I remember X) -> (Why do remember X just now?)
(My {family-member} is Y) -> (Who else in your family is Y?)
(X {family-member} Y) -> (Tell me more about your family)

Efficient Parsing
Chart Parser :
1. keep a data structure “Chart”
2. use dynamic programming to avoid duplicate

function CHART-PARSE(string, grammar) returns chart
chart := [0,0,s’->.S]
while new edges can still be added do
edge := choose[I,j,A->α.Bβin chart
choose one of the three methods that will succeed
choose (B->γ) in RULES[grammer]
add [j,j,B->.γ] to chart
choose [j,k, B->F.] in chart
add [I,k,A->α.Bβ] to chart
if string[j+1] is of category B then
add [j,j+1, A->αB.β] to chart
return chart

Reproduce parse tree from chart
look chart[n] to for an edge that starts at 0
and recursively look at the children list to reproduce the complete tree.

[0,5 S->NP VP.]
[0,2,S->NP.VP] [2,5 VP->Verb NP.]
The agent feels a breeze
0 - 1 - 2 - 3 - 4 - 5

Lexical Processing

1. Tokenization : divide input into distinct token
2. Morphological Analysis :
describing a word in terms of the prefixes, suffixes, root form
1.Inflectional morphology :append s when plural
2.Derivational morphology : shortness -> short + ness)
3.Compounding : bookkeeper -> book + keeper)
3. Dictionary lookup
4. Error Recovery
1. Letter-based model :
1.insert 2.delete
2. Transposing to adjacent letters,
3. replacing one letter with another
2. Sound-based model :

Grammar Processing

1. Nominal Compounds (noun:noun)
Noun(λy#x sem1(x)&sem2(y)&NN(x,y))->Noun(sem1)Noun(sem2)
2. Apposition (NP:NP)
NP([q x sem1&sem2])->NP([q x sem1])NP([q x sem2])
3. Adjective Phrase
solve1 : Noun(λx sem1(x)&sem2(x))->Adj(sem1)Noun(sem2)
example: #w Smelly(w) & Wumpus(w)
solve2 : Noun(λx sem1(sem2(x)))->Adj(sem1)Noun(sem2)
example: #x (x in Fake(Guns))
4. Determiner
NP([q x noun(x)])->Det(q) Noun(noun)
example :
three dogs
=> [3 x Dog(x)]
=>#s Cardinality(s)=3 & $d((d in S => Dog(d))

5. Reference
人稱: I -> Person(1) , You -> Person(2), other -> Person(3)
NP(case, Person(3), number, [q x sem(x)])->Det(number, q)Noun(number, sem)
a dog, those dogs
S(rel(obj))->NP(subject, person, number, obj) VP(person, number, rel)
NP(case, Person(3), number, [#!x Name(x)=name])->Name(number, name)
Name(Singular, John) -> John

6. Relative Clauses
RelClause -> Pronoun(Relative)S(Gap(NP))
example :
[the Person]i[that [s you said[s you thought[s I gave the book to _i]]]]

7. Question
1. Subject-aux inversion : Yes/No question
example : Did you see that ?
8. Gapped : (Wh question)
example : What did you see _ ?
9. Echo
example : You saw what ?
4. Raising intonation
example : You see something ?
5. Yes/No with “be” : Is it safe ?
6. Wh subject : What is the frequency, Kenneth ?
7. Wh NP : [What book] did you read _?
8. Wh PP : [With what] did you see it _?
9. Wh PP : [Whence] did he come _?

Ambiguity :
Finding right interpretation involves reasoning with
uncertainty using the evidence provided by lexical syntactic,
semantic, and pragmatic sources.

Syntactic evidence : preferred most recent consistent.
Ex: Lee asked Kim to tell Toby to leave on Saturday.
Lexical evidence :
Ex: Lee [positioned] the dress [on the rack].
Ex: Kim wanted the [dress] [on the rack].
Semantic evidence :
Ex: Ball, diamond, bat, base
Ex: I ate spaghetti with meatballs (ingredient of spaghetti)
Ex: I ate spaghetti with salad (side dish of spaghetti)
Ex: I ate spaghetti with abandon (manner of eating)
Ex: I ate spaghetti with a fork (instrument of eating)
Ex: I ate spaghetti with a friend (accompanier of eating)
Metonymy :
Ex: Chrysler announce a new model.
#x,e Chrysler(x) & e in Announce(x, Past) – no good.
#m,x,e Chrysler(x) & Metonymy(m,x)&e in Announce(m,Past)
$m,x (m=x) => Metonymy(m,x)
$m,x Organization&Spokeperson(m,x)=>Metonymy(m,x)
Ex: I read Shakespeare ( Metonymy(author)=works )
Ex: I drive Honda ( Metonymy(producer)=product )
Metaphor :
Ex: Metaphor(more)=up & Altitude(Sales,High)
=> Quantity(Sales,Much)

Discourse Understanding : text understanding.
KB(n+1) = Discourse-Understanding(text, KB(n))
commutative is not true
example :
Discourse(A) Discourse(B)
I visit Paris I visited Paris
I bought you some expensive cologne Then I flew home
Then I flew home. I went to Kmart
I went to Kmart I bought you some expensive cologne
I bought some underwear I bought some underwear

解法: 用push down stack來記錄focus space
I visit Paris (paris)
I bought you some expensive cologne (paris)
Then I flew home. (paris, home)
I went to Kmart (paris, home, Kmart)
I bought some underwear (paris, home, Kmart)

example :
A funny thing happened yesterday
| (evaluation coherence)
John went to a fancy restaurant
| (enable coherence 起始)
He ordered the duck
| (causal coherence因果)
The bill came to $50
| (elaboration relation 精心製作)
John got a shock when the waiter came to collect the bill
| (explanation relation)
He realized he didn’t have a cent on him
| (elaboration relation)
He had left his wallet at home
The waiter said it was all right to pay later
| (causal relation by 5,6)
He was very embarrassed by his forgetfulness

Chapter 24 Perception
Speech Recognition
speaker utter > speech sound -> word ——> meaning
1 2 3
Problem of 1 : utter(原音) -> phones (音素)
Problem of 2 : homophone(同音字判別)
Problem of 3 : parse, analysis

Sample (by sampling rate) -> frames (block) -> feature vector
Model :
P(words|signal) = P(words)* P(signal | words) / P(signal)

Language model : P(word)
P(“bad boy”) » P(“pad boy”)
Acoustic model : P(signal | words)

Probabilistic context-free grammars (PCFGs)

P(w1,..,wn) = P(w1)P(w2|w1)P(w3|w1w2)..P(wn|w1..wn-1)
= ΠP(wi|w1..wi-1)
~ ΠP(wi|wi-1) // in bigram model
~ ΠP(wi|wi-1wi-2) // in trigram model
~ c1P(wi) + c2P(wi|wi-1) + c3P(wi|wi-1wi-2)
// in hybrid model

Acoustic model : P(signal | words)
Dialect : 不同地方的口音不同.
Example : “tomato” [tow mey tow] [tow maa tow]
P([tow mey tow]|”tomato”) = P([tow maa tow]|”tomato) = 0.5

Coarticulation :
因為發音太快以致舌頭未達正確位置, 或因物理干擾、衰減所造成的差異.
Example : [tow mey tow] -> [tah mey tow]
P([tah mey tow]|”[tow mey tow]”) = 0.2
P([tow mey tow]|”[tow mey tow]”) = 0.8

Markov model (HMM)
MM Word model with dialect variation

[t] -> [ow] -> [m] ↗[ey] ↘ [t] -> [ow]
↘[aa] ↗

MM Word model with coarticulation and dialect varaition

0.2 0.5
[t] ↗[ow] ↘ [m] ↗[ey] ↘ [t] -> [ow]
↘[ah] ↗ ↘[aa] ↗
0.8 0.5

Hidden Markov model
Phone HMM for [m]

0.3 0.7 0.9 0.1 0.4 0.6
-> Onset -> Mid -> End -> Final

Onset: Mid: End:
C1:0.5 C3:0.2 C4:0.1
C2:0.2 C4:0.7 C6:0.5
C3:0.3 C5:0.1 C7:0.4

P(C1C1C4C4C6C6) = P(C1C1C4C4C6C6|path)*P(path)

algorithm Viterbi
input : HMM model,[C1,..,Cn]
output: max(P(path))
method: dynamic programming
goal : find the most possible path

algorithm forward-backward(Baum&Welch)
input : a set of [signal, words] pairs
output: a HMM model for input set
goal : learn HMM from a training set of [signal, words] pairs

Threat : Steps that might delete the protected condition.

Protected : A causal link is protected by ensuring that threats are ordered to come before or after the protected link.

Threat Promotion Demotion

↙↘ S3
S1 ↙ -c
↓ S3 S1 S1
c -c ↓ ↓
S2 c c
↘↙ S2 S2

Chapter 26 Philosophical Funcation
Weak AI position
Can machine be made to act as if they were intelligent ?

Strong AI position
Can machine be act intelligently and have real, conscious mind ?

homunculi - miniature men : infinite regress

intentional stance : 可預測的計算程序即是belief
缺點:cannot distinguish among the implementation.

Correspondence theory
1. 當sensor感測到一事件時,該假設被建立。
2. 當sensor感測到一事件的反例時,該假設被消除。
3. 假設為行動之基礎。

Chapter 27 AI: Present and Future


Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License