The EAST algorithm Scale up sHc )Idea 1: Restrict NI to involve only two neighbors of the latent varlable It operators on X4 X4 X7 AAAl2014 Tutorial Nevin L Zhang HKUST 16
AAAI 2014 Tutorial Nevin L. Zhang HKUST 16 Scale up SHC Idea 1: Restrict NI to involve only two neighbors of the latent variable it operators on The EAST Algorithm
Reachability How to go from the left to the right then with the restriction? ? X3 X6 First apply NI, and then Nr X1)(X2 X7 Each NI operation is followed by nr operations to compensate for the restriction on ni
How to go from the left to the right then with the restriction? First apply NI, and then NR Each NI operation is followed by NR operations to compensate for the restriction on NI. Reachability NI NR
Idea 2: Reducing Number of Candidate Models Not to use all the operators at once How? BIC: BIC(m D)=log P(D)m, 8*)-d/2 logN Improve the two terms alternately Ni and si improve the likelihood term? Let be m'obtained from m using ni or sI Then, m'includes m, hence has higher maximized likelihood log P(D/m, 8)>=log P(D)m, 87 SD and ND reduce the penalty term AAAl2014 Tutorial Nevin L Zhang HKUST 18
AAAI 2014 Tutorial Nevin L. Zhang HKUST 18 Idea 2: Reducing Number of Candidate Models Not to use ALL the operators at once. How? BIC: BIC(m|D) = log P(D|m, θ*) – d/2 logN Improve the two terms alternately NI and SI improve the likelihood term? Let be m’ obtained from m using NI or SI Then, m’ includes m, hence has higher maximized likelihood log P(D|m’, θ’*) >= log P(D|m, θ*) SD and ND reduce the penalty term
The EAsT Algorithm Chen et al. AlJ 2011) 1. Start with a simple initial model 2. Repeat until model score ceases to improve Expansion Search with node introduction(NI), and state introduction (SI) each ni operation is followed by nr operations to compensate for the restriction on NI.(See Slide 17 Adjustment Search with nr Simplification Search with node deletion(ND), and state deletion(SD) EAST: Expansion, Adjustment, Simplification until Termination AAAl2014 Tutorial Nevin L Zhang HKUST 19
AAAI 2014 Tutorial Nevin L. Zhang HKUST 19 The EAST Algorithm (Chen et al. AIJ 2011) 1. Start with a simple initial model 2. Repeat until model score ceases to improve Expansion: Search with node introduction (NI), and state introduction (SI) Each NI operation is followed by NR operations to compensate for the restriction on NI. (See Slide 17) Adjustment: Search with NR Simplification: Search with node deletion (ND), and state deletion (SD) EAST: Expansion, Adjustment, Simplification until Termination
Idea 3 Parameter value nheritance m: current model m: candidate model generated by applying a search operator on m The two models share many parameters m:(6,.82);m:(,A When evaluating m, inherit values of the shared parameters 0, from m, and estimate only the new parameters A2 2=arg max /2 log P(DIm, 01.n2) X5)(X6)(X7
Idea 3: Parameter Value Inheritance m : current model; m’ : candidate model generated by applying a search operator on m. The two models share many parameters ➢ m: ( θ1, θ2); m’: ( θ1 , λ2); When evaluating m’, inherit values of the shared parameters θ1 from m, and estimate only the new parameters λ2: λ* 2 = arg max λ2 log P(D|m’, θ1, λ2 )