# Coercing a list of nodes into the most probable tree

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.

• Depends on $f$, I guess. The problem reminds me of parsing words w.r.t. stochastic context-free grammars; in that case, $f$ is a measure of likelihood/probability. – Raphael Apr 12 '16 at 12:36
• its roughly/ essentially a text-based machine learning problem. have seen similar application with eg LSA/ LSI. think this could possibly be better described. try Computer Science Chat for further discussion – vzn Apr 12 '16 at 15:07
• Indeed it looks like creating a parse tree for a stochastic CFG. If the feature space is fixed and limited, I guess one could generate every possible production rule and assign it a probability. – Maarten Apr 12 '16 at 15:08
• @vzn Makes sense applying this to semantic indexing. Do you have an example of a project that implements this? – Maarten Apr 12 '16 at 15:14
• participated in a project vaguely like this many years ago at an edu dotcom but results were unpublished (and imho somewhat inconclusive). if you provide more detail in Computer Science Chat may be able to find relevant/ more specific refs. the problem seems to be somewhat related to the area of "autosummarization" because the section headers are summaries of the sections. the code will potentially work better if it has access to the full sections and the headers and not headers alone. the problem is that headers may not contain enough info such that even humans would have trouble with the problem. – vzn Apr 12 '16 at 15:17