Consistency of the MDL Score

MDL Score is consistent

• As M ?? the “true” structure G* maximizes the score (almost surely)

• For sufficiently large M, the maximal scoring structures are equivalent to G*

Proof (outline):

• Suppose G implies an independence statement not in G*, then

  as M ??, l(G:D) ? l(G*:D) - eM (e depends on G)
  
  so MDL(G*:D) - MDL(G:D) ? eM - (dim(G*)-dim(G))/2 log M

• Now suppose G* implies an independence statement not in G, then

  as M ??, l(G:D) ? l(G*:D)
  
  so MDL(G:D) - MDL(G*:D) ? (dim(G)-dim(G*))/2 log M

Previous slide

Next slide

Back to first slide

View graphic version