Predict a tree structure out of nodes with different features

Question

The Problem

Suppose we have a representation of a document's text layout as in the image below:

Here, each rectangle represents a chunk of text (one word, an expression or even part of a sentence).

Each rectangle has a set of features and connections to adjacent rectangles (the image doesn't show all connections, but they are present):

• top/bot/lft/rgh sibling
• top/bot/lft/rgh distance to sibling (in case of sibling presence)
• margins alignment (for rectangles aligned in columns)
• font size (continuous variable type)
• font type (categorical)
• all_caps (binary)
• and some other

What I would like to achieve is to train an algorithm (ML? DNN? Graphs? something other?) that would structure these rectangles, would create a tree structure out of these individual nodes. For instance the above example would be structured as follows:

          ROOT
 __________|___
|          |   |
2          10  12
|_         |   |_________
| |        |   |         |
3 9        11  14        20...
|________      |__       |__
| | | | |      |  |      |  |
4 5 6 7 8      13 15...  19 21...
                            |  \
                            22 23...

My results so far

I spend some time (~8h already) searching for a solution, but couldn't find anything applicable to this case. I'm relatively new to ML and don't have much experience, however I think it can be solved using a supervised learning algorithm by feeding a training set consisting of documents with all these nodes with their features and annotated trees that should be generated as a result out of these nodes.

Some ideas I found while searching that might help (probably one of these is the solution, but I need some guidance on how to adjust in properly):

1. Using some sort of DNN. It would figure out the relationship between distances and other features of the nodes from the training set so that it would be able to predict a structure given only the nodes and their features. I didn't work with DNN and I don't know how to make it generate the structure instead of categorize which digit is shown in the image (I did some basic tutorials)
2. Creating/Training a PCFG (Probabilistic Context Free Grammar). This approach seems to be valid, as it used in generating parsed trees in NLP (those that structure a sentence in form of a tree) and I found some resources on it, however I don't understand how to use all the features that are available on my nodes in learning such a grammar? Also, I don't see how this approach could make use of the positioning data in 2D space and the distances between siblings, as it is one of the key features in structuring the nodes.
3. Probably some Graph or Tree related algorithms would solve my problem, but I don't know how to formulate the query that would help me find the solution.

A very similar question was asked on Computer Science SE site, but there are no answers and the OP doesn't respond.

I would really appreciate if you would provide a solution, or even a hint in what direction to move in order to solve this problem.

Answer 1

Don't use machine-learning for this - you probably don't have millions of training examples.

Instead, what you are looking for is a simple depth-first search.

Begin at the root, then define a priority list, e.g. below-left, below, below-right, in which order to proceed. Don't visit nodes twice, but when first visiting them mark them as seen, and add them to your tree instead.

Alternatively, define a priority pattern of how to define the parent node. Construct a tree based on this single "best parent" relationship,, but make sure you don't create cycles.