Introduction Models & Algorithms Results & Conclusions
Corpus-Based Incremental Intention Recognition via Bayesian Network Model Construction Han The Anh (
[email protected]) Luís Moniz Pereira (
[email protected]) /UNL
ICAPS "Goal, Activity and Plan Recognition" workshop Freiburg, Germany, 12 June, 2011 logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Intention Recognition
Outline 1
Introduction Intention Recognition
2
Models & Algorithms Bayesian Network Construction Operators for Handling Bayesian Networks for Intention Recognition (IRBNs) Relations Amongst Intentions
3
Results & Conclusions Evaluation Metrics Linux Plan Corpus Prisoner’s Dilemma Corpus logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Intention Recognition
Why Intention Recognition?
Intention recognition (IR): inferring intentions of a single agent (individual) or a group of agents (collective) based on their observed actions. Why IR is necessary? Acting on environment, agent may have to deal with other agents Ease interactions, improve cooperation and coordination, especially when communication is limited. Defend from potential hostile behaviors, plan in advance to take advantage. logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Intention Recognition
Intention recognition systems: Typical Components Sequence of Observed Actions
A1 A2 A3 ....... Observed Agent
Model
-Bayesian KB -Markov KB ....
Set of Intentions Plan Library Plan Corpus Action Theory
Recognized Intentions
With Rankings (Probabilistic) Without Rankings (Non-probabilistic) logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Intention Recognition
System Description Preprocessing Bayesian Network Fragments
Plan Corpus Experts' Knowledge
I
A
Unit Fragments Operators
A1 A2 A3 ....... Bayesian Network for Intention Recognition
Incremental Prediction
-Probability Inference -Simplification
-Selection -Combination -Remove ....
IRBNs logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Bayesian Network Construction Operators for Handling IRBNs Relations Amongst Intentions
Bayesian Network for Intention Recognition (IRBN) Causes/Reasons P(C1)
C-1
Subject to Changes
Actions Intentions
I-1
C-2
. . . .
. . .
A-1
P(A1|I1,IM) . . . .
I-M
A-P C-N
CPD table for each node X P(X|parents(X)) T.A.Han, L.M.Pereira
IR: Compute P(I-i|obs) i = 1,...,M Corpus-based Incremental Intention Recognition
logo
Introduction Models & Algorithms Results & Conclusions
Bayesian Network Construction Operators for Handling IRBNs Relations Amongst Intentions
Unit Fragments → Unit IRBN
Figure: Combine context-dependently selected unit fragments of a new action A. I1
. . . .
IN
A
A
I1
. . . .
A
IN
logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Bayesian Network Construction Operators for Handling IRBNs Relations Amongst Intentions
Integrate into the current model ... When a new action A3 arises, integrate it into the current model
Current IRBN
Unit IRBN for New Action
C-1
C-1 I-1
I-1 A-1 C-2
C-2
. . . .
A-3 I-2
I-2 A-2
. . . .
I-4
I-3 C-M
C-N
logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Bayesian Network Construction Operators for Handling IRBNs Relations Amongst Intentions
Remove Irrelevant Intentions If some intentions are found out to be irrelevant, e.g. when their probability is very small, they are removed from the model.
Current IRBN
After Removing I-3
C-1 C-1
I-1
A-1
A-1 I-1 C-2
Remove I-3
I-2
P(A|I1,I2,I3=F)
A-2
I-2
C-3
A-2 I-3
C-2
C-4
Very Unlikely
T.A.Han, L.M.Pereira
logo
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Bayesian Network Construction Operators for Handling IRBNs Relations Amongst Intentions
Incremental Intention Recognition Algorithm
Repeat until one intention remains or time limit is reached. 1
If new actions are observed: combine unit IRBNs for them with the current IRBN.
2
Compute conditional probability of each intention given current observed actions. Remove irrelevant intentions.
logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Bayesian Network Construction Operators for Handling IRBNs Relations Amongst Intentions
Relations Amongst Intentions: multiple intentions
In case agent pursues multiple intentions simultaneously, intentions may support or exclude each other. Two mutually exclusive intentions cannot be parents of an action: P(I1 = T , I2 = T ) = 0 → P(A|I1 , I2 , ...) is undefined. Need to combine mutually exclusive intentions in a single node.
logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Bayesian Network Construction Operators for Handling IRBNs Relations Amongst Intentions
Single Intention Case
In case agent pursues a single intention (Linux Plan corpus), all intentions are mutually exclusive. They are combined in a single node. A1 , ..., Am : current observed actions. Then, Q P(Ij ) m P(A |I ) i=1 P Qm i j P(I = Ij |A1 , ..., Am ) = n P(I ) j j=1 i=1 P(Ai |Ij ) The recognizer has linear complexity on the number of intentions being modeled. logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Evaluation Metrics Linux Plan Corpus Prisoner’s Dilemma Corpus
Evaluation Metrics Seq = a1 , ..., an : sequence of actions achieving intention I . N-best prediction: correct(A) = 1 if I is one of N most likely intentions, and 0 otherwise. n X precision(Seq) = ( correct(ai ))/z i=1 n X recall (Seq) = ( correct(ai ))/Z i=1
convergence(Seq) = (z − t + 1)/z z: #predictions; Z : #prediction opportunities; t: smallest number from that on correctly predicts. T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
logo
Introduction Models & Algorithms Results & Conclusions
Evaluation Metrics Linux Plan Corpus Prisoner’s Dilemma Corpus
Linux Plan Corpus
One of rare, often used, plan corpora available for evaluating intention/plan recognizers. goals = tasks in Linux (e.g., find a file, copy some files); actions = Linux commands (e.g., find, cp, cd, ls). 19 goals; 43 actions (commands); 547 sessions. Collected from Linux users.
logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Evaluation Metrics Linux Plan Corpus Prisoner’s Dilemma Corpus
Intention Recognition Results on Linux Plan Corpus τ – confidence level: make prediction only when probability ≥ τ . 0.8 0.8
Precision
Critical Values decreasing
0.6
1�best
0.5
Convergence
0.7 0.7
0.6
Critical Values decreasing
1�best
0.5
2�best 3�best
0.4
2�best 0.4
3�best
4�best
4�best 0.3
0.3 0.0
0.2
0.4
0.6
0.8
Τ
0.0
0.2
0.4
0.6
0.8
Τ
Figure: Precision and Convergence for τ ∈ [0, 1]; N = 1, 2, 3, 4. logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Evaluation Metrics Linux Plan Corpus Prisoner’s Dilemma Corpus
We obtained better results than existent corpus-based intention recognizers. N-best τ Precision Recall Converg.
1-best 0.95 0.786 0.308 0.722
2-best 0.5 0.847 0.469 0.799
3-best 0.45 0.870 0.518 0.822
4-best 0.42 0.883 0.612 0.824
Table: Intention Recognition Results on the Linux Plan Corpus
logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Evaluation Metrics Linux Plan Corpus Prisoner’s Dilemma Corpus
Iterated Prisoner’s Dilemma Corpus (IPD)
Prisoner’s Dilemma is a symmetric two-player non-zero game defined by the payoff matrix
C D
C R, R T,S
D S, T P, P
Intentions to be recognized are strategies in IPD: TFT, WSLS, GTFT, GRIM, FBF, etc. logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Evaluation Metrics Linux Plan Corpus Prisoner’s Dilemma Corpus
1.0
1.0
0.9
0.9
0.8
0.8
0.7 0.6
1�best
0.5
2�best
0.4
3�best
0.3
Convergence
Precision
Intention Recognition Results on IPD Plan Corpus
0.7 0.6
1�best
0.5
2�best
0.4
3�best
0.3 0.0
0.2
0.4
0.6
0.8
Τ
0.0
0.2
0.4
0.6
0.8
Τ
Figure: Precision and Convergence for τ ∈ [0, 1]; N = 1, 2, 3 logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Evaluation Metrics Linux Plan Corpus Prisoner’s Dilemma Corpus
Summary
Incremental IR model via incrementally constructing a Bayesian network model. Evaluated on Linux Plan corpus, obtaining better results than existent systems. Present a new benchmark for intention/plan recognition based on social dilemmas (Prisoner’s Dilemma, Stag hunt,...). Able to handle multiple intention case by representing relations amongst intention nodes. logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Evaluation Metrics Linux Plan Corpus Prisoner’s Dilemma Corpus
Future Work
Create plan corpora to evaluate multiple-intention recognition (suggestions of Planners for this purpose are greatly appreciated) Apply to explain the role of intention recognition for the evolution of cooperation (see our papers in refs). We have provided in another IPD benchmark corpus for testing context-dependent aspect (BMAW@UAI paper).
logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Evaluation Metrics Linux Plan Corpus Prisoner’s Dilemma Corpus
Thank you!
QUESTIONS?
logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Evaluation Metrics Linux Plan Corpus Prisoner’s Dilemma Corpus
IPD Plan Corpus Intentions are famous strategies in IPD: TFT, WSLS, GTFT, GRIM, FBF. There are infinite number of strategies. Corpus actions: s1 ...sM ξ, where si ∈ {E , R, T , S, P} – states of the M last interactions; ξ ∈ {C , D} – current move. Σ1 = {EC , RC , TC , SC , PC , ED, RD, TD, SD, PD} A plan session of TFT: [EC , RC , SD, PD, TD] 0
1
TFT : −
C
C
D
D
D
X: −
C
D
D
C
D
TFT-states : E
R
S
P
T
P
round :
2
3
4
5
logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
Introduction Models & Algorithms Results & Conclusions
Evaluation Metrics Linux Plan Corpus Prisoner’s Dilemma Corpus
Generating Training and Testing Datasets
7 strategies: AllC, AllD, TFT, GTFT, WSLS, GRIM and FBF. Training corpus is generated by playing with each strategy all the possible combinations 10 times (r = 5, . . . , 10). The testing dataset is generated by playing a random choice with each strategy in each round (r = 5, . . . , 10).
logo
T.A.Han, L.M.Pereira
Corpus-based Incremental Intention Recognition
