How does SpaCy make its dependency tree? I discovered that SpaCy had the ability to make dependency trees. For instance given a question “To whom did the Virgin Mary allegedly appear in 1858 in Lourdes France?”

We can create its dependency tree with the following code :



I know that it is a set of edges $E$ which represents the relations of labeled dependencies of the particular analysis of $G$. More precisely, an edges $w_i, r, w_j \in E$ represents a relationship of dependence of head $w_i$ towards $w_j$ labeled with the type of relationship. A dependency graph $G$ is therefore a set of dependency relations between tokens in $S$. 

For instance we present the dependency graph that follows
 by the following graph:


$G = (V, E)$
$V = \{\mbox{It, is, a, replica, of, the, grotto, at, Lourdes, France, where, the, Virgin, Mary}\\ \mbox{reputedly, appeared, to, Saint, Bernadette ...}\}$
$E=\{\mbox{(is, NSUBJ, It), (is, ATTR, a replica), (a replica, PREP, of),...}\}$


But I was wondering how does $E$ was made with Spacy? How does the dependency tree method chose which node is the root and which aren't? 

I have heard from this French paper that, on the one hand that $E \subseteq V \times R \times V$ where $R = {r_1, ..., r_m}$ is a finite set of dependency possible names that we call dependency relationship. They can link two tokens in a sentence. A dependency name $r \in R$ is also called a labeled edge. For example, a relationship between a head verb and its subject can be noted with $r = SBJ$.

On the other hand it was an analysis problem of finding the dependency graph that has the highest score for an input sentence.

Yet I haven't seen where there is a child-children ordering creation.



The context is that I am using SpaCy dependency trees to get the root of sentences of a paragraph and match it with the root of a question.

For the question given above we have to find the answer in the following paragraph :


  Context — “Architecturally, the school has a Catholic character. Atop
  the Main Building\’s gold dome is a golden statue of the Virgin Mary.
  Immediately in front of the Main Building and facing it, is a copper
  statue of Christ with arms upraised with the legend “Venite Ad Me
  Omnes”. Next to the Main Building is the Basilica of the Sacred Heart.
  Immediately behind the basilica is the Grotto, a Marian place of
  prayer and reflection. It is a replica of the grotto at Lourdes,
  France where the Virgin Mary reputedly appeared to Saint Bernadette
  Soubirous in 1858. At the end of the main drive (and in a direct line
  that connects through 3 statues and the Gold Dome), is a simple,
  modern stone statue of Mary.”


The expected answer is  “Saint Bernadette Soubirous”. 
The sentence having the answer — is “It is a replica of the grotto at Lourdes, France where the Virgin Mary reputedly appeared to Saint Bernadette Soubirous in 1858”. Its dependency tree of the sentence containing the answer is :
Matthew Honnibal, who created Spacy, answered me :


  The full answer is rather complicated :). I've written a few blog
  posts over the years to make it more accessible. The best place to
  start is this blog post:
  
  https://explosion.ai/blog/parsing-english-in-python
  
  Since v2, we use a more complicated machine learning strategy,
  following the general architecture described here:
  https://explosion.ai/blog/deep-learning-formula-nlp . More specifics
  about the model architecture can be found in this description of the
  NER model: https://www.youtube.com/watch?v=sqDHBH9IjRU
  
  The transition system is mostly described by this paper:
  http://aclweb.org/anthology/D15-1162 , but with some modifications for
  sentence segmentation.


I already started with the first one which I didn't completly understand yet. I will update this post through my reading progress but leave the question open if a concise question comes to your mind.