Coercing a list of nodes into the most probable tree

Question

Suppose that we have an RTF document which contains sections and sub-sections. The sections and subsections all have headings that are visually marked up (e.g., bold and italic), but the document structure is not made explicit (i.e., we have a linear flow of text). From the section headings, we wish to automatically determine the most likely document structure.

For titles on the same sectioning level, we know that they probably have the same kind of markup, and they probably increment in numbering, but we don't know exactly what they should look like (e.g., bold/italic; arabic/roman; how deep subsectioning goes), and their relatedness may be fuzzy (the author might forget a number in a sequence, for instance 1. First section, Second section, 3. Third section).

To make things more explicit, we can assume assume that we have a features vector fs with a fixed number of features, that combines linearly into a fitness function f(fs) = w₁ f₁ + w₂ f₂ … wₙ fₙ, given a weight vector ws. The fitness function is arbitrary, this is just to make the problem explicit.

So from list G:

We wish to create a tree G' such that:

• G' maintains the preorder relations of G
• G' maximizes some fitness function f(G'), where f calculates how alike nodes are that are children of the same parent (same markup; incrementing numbering).

^{(root not displayed)}

---

My question: does this problem reduce to another well-known problem?

---

This problem reminds me of a lot of stuff I've seen before, from finding the best path through a DAG to hierarchical clustering, except nothing seems to hit the sweet spot in terms of describing or solving the problem. I guess it's closest to the problem of finding the minimum spanning tree, except calculating the spanning tree score is not as straighforward.

---

I have thought of my own solution, but I was surpirised that I could find no resources that deal with this problem exactly.

My solution would be a dynamic programming algorithm that attaches a score to each possible tree as a linear function. (Meaning we can cache subtrees without re-calculating everything.) We can learn the constants of our function using some expectation maximization algorithm based on existing document structures.

Answer 1

In the end, I ended up solving my particular problem using Stochastic Context Free Grammars.

There may be some additional cost incurred for production, or otherwise probability operations that you can't express in the CFG. The probabilistic Earley algorithm (Stolcke, 1995) allows us to intervene in the parsing process somewhat by producing callbacks on scannning a token (or predicting / completing).

I have arbitrarily chosen my rule probabilities, but you can train them using the inside-outside algorithm, although that will probably mess up the the soundness of any probability-tinkering callbacks.

---

Practically, this question lead me to create a Probabilistic Earley Parser for Javascript and for Java. These libraries only allow the user to multiply scan probability given a token at a position the sentence, but it is easy to add other callbacks with more information. Please create an issue in Github if you need this. Also, these libraries do not support training a grammar on a test set (inside-outside), because I did not have time to implement this.

For an exposition of my use case, consider the chapter in my master thesis Automatic Assignment of Section Structure to Texts of Dutch Court Judgments, Inferring a Section Hierarchy