Directed Models: Limitations
nAcyclicity
constraint limits expressive power:
nTwo objects
linked to by a student probably not both professors
nAllow arbitrary
patterns over sets of objects & links
nAcyclicity
forces modeling of all potential links:
nNetwork
size O(N2)
nInference
is quadratic
nGenerative training:
nTrain to fit all of data, not to maximize accuracy
nInfluence
flows over existing links, exploiting link graph sparsity
nNetwork
size O(N)
nAllow discriminative training:
nMax P (labels | observations)
Solution:
Undirected Models
[Lafferty, McCallum, Pereira]