5
$\begingroup$

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:

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).

example tree

(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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Apr 12 '16 at 12:36
  • $\begingroup$ 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 $\endgroup$ – vzn Apr 12 '16 at 15:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Maarten Apr 12 '16 at 15:08
  • $\begingroup$ @vzn Makes sense applying this to semantic indexing. Do you have an example of a project that implements this? $\endgroup$ – Maarten Apr 12 '16 at 15:14
  • $\begingroup$ 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. $\endgroup$ – vzn Apr 12 '16 at 15:17
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.