Node Introduction(NI) N involves a latent variable y and some of its neighbors It introduces a new node y to mediate Y and the neighbors The cardinality of y is set at y Example Y2 introduced to mediate Y1 and its neighbors X1 and X2 s The cardinality of Y2 is set at Y1 AAAl2014 Tutorial Nevin L Zhang HKUST
AAAI 2014 Tutorial Nevin L. Zhang HKUST 11 NI involves a latent variable Y and some of its neighbors It introduces a new node Y’ to mediate Y and the neighbors. The cardinality of Y’ is set at |Y| Example: Y2 introduced to mediate Y1 and its neighbors X1 and X2 The cardinality of Y2 is set at |Y1| Node Introduction (NI)
Node Relocation(NR) > NR involves a latent variable Y, a neighbor Z of Y, and another neighbor y of y that is also a latent variable s t relocates z from y to y Example s X3 is relocated from y1 to y2 X3 X6 X X6 AAAl2014 Tutorial Nevin L Zhang HKUST
AAAI 2014 Tutorial Nevin L. Zhang HKUST 12 NR involves a latent variable Y, a neighbor Z of Y, and another neighbor Y’ of Y that is also a latent variable. It relocates Z from Y to Y’. Example: X3 is relocated from Y1 to Y2 Node Relocation (NR)
Node deletion ND involves a latent variable Y, a neighbor yof y that is a latent variables It remove Y, and reconnects the other neighbors of y to y Example >y2 is removed w.r. t to y1 AAAl2014 Tutorial Nevin L Zhang HKUST
AAAI 2014 Tutorial Nevin L. Zhang HKUST 13 ND involves a latent variable Y, a neighbor Y’ of Y that is a latent variables. It remove Y, and reconnects the other neighbors of Y to Y’. Example: Y2 is removed w.r.t to Y1. Node Deletion
State Introduction/ Deletion State introduction(SI) Increase the number of states of a latent variable by 1 State deletion (SD) Reduce the number of states of a latent variable by 1 AAAl2014 Tutorial Nevin L Zhang HKUST 14
AAAI 2014 Tutorial Nevin L. Zhang HKUST 14 State introduction (SI) Increase the number of states of a latent variable by 1 State deletion (SD) Reduce the number of states of a latent variable by 1. State Introduction/Deletion
Single Hill Climbing (SHC) Start with an initial model (LCm) At each step Construct all possible candidate models using NI, ND, NR, SI and SD Evaluate them one by one Pick the best one Still inefficient Tested on data with no more than 12 variables Reason Too many candidate models Too expensive to run EM on all of them AAAl2014 Tutorial Nevin L Zhang HKUST 5
AAAI 2014 Tutorial Nevin L. Zhang HKUST 15 Single Hill Climbing (SHC) Start with an initial model (LCM) At each step: Construct all possible candidate models using NI, ND, NR, SI and SD Evaluate them one by one Pick the best one Still inefficient Tested on data with no more than 12 variables. Reason Too many candidate models Too expensive to run EM on all of them