Structural EM in Practice

In theory:

• E-Step: compute expected counts for all candidate structures

• M-Step: choose structure that maximizes expected score

Problem: there are (exponentially) many structures

• We cannot computed expected counts for all of them in advance

Solution:

• M-Step: search over network structures (e.g., hill-climbing)

• E-Step: on-demand, for each structure G examined by M-Step, compute expected counts

• Use smart caching schemes to minimize overall computations

Previous slide

Next slide

Back to first slide

View graphic version