sampling spanning trees

Question

We know from Ryan McDonald's spanning tree work that we can think of dependency parsing as setting up edge potentials in a fully connected graph (modulo some cornercase-need to handle roots), and then running a maximum spanning tree algorithm to find the most likely parse for a sentence. What if, instead of desiring a most-likely parse, we want to generate samples from the corresponding distribution? Is there an obvious way to do this?

I suspect that there is, because we know how to do it for constituent trees generated by a PCFG. Perhaps it's obvious and I'm just not seeing it in the dependency case...

Answer 1

Hey Hal,

Certainly for the projective case one can use this trick to convert an arc-factored model to a CFG and then, you should be able to run standard PCFG sampling techniques. This Wallach et al. paper also might help you. For the non-projective case it is going to be trickier, since the top down step of the Johnson et al. paper assumes projectivity. I do think there is something that can be done here (via the matrix-tree theorem, or something similar). This paper might be a good starting point.

Answer 2

I read the paper a while ago so am not sure on the details, but these guys Multilingual Dependency Parsing using Global Features, (Nakagawa 2007) used gibbs sampling for non-projective dependency parsing.

Answer 3

This paper might solve your problem:

 @article{propp1998get,
   title={{How to get a perfectly random sample from a generic Markov chain and 
              generate a random spanning tree of a directed graph}},
   author={Propp, J.G. and Wilson, D.B.},
   journal={Journal of Algorithms},
   volume={27},
   number={2},
   pages={170--217},
   issn={0196-6774},
   year={1998},
   publisher={Academic Press}
 }

sampling spanning trees

Subscription:

Related questions