The Mean Rank is the mean difference between the annotated ranks of the children of a node and the ranks of the same children obtained from the embedding (label vs. result). The lower the Mean Rank, the more correctly the embedding can determine what topics have a certain topic as their prerequisite.

Improved Concept Embeddings for Learning Prerequisite Chains: Mean Rank

For a single node/concept $u$ in the co-occurrence graph $G$, the Average Precision (AP) is calculated in two steps.
1. Constructed a list $labels = \{l_1, l_2, ..., l_n\}$, where $l_i = 1$ if $i$ is a child of $u$ and 0 otherwise, and calculated a list $distances = −\{d_1, d_2, ..., d_n\}$, where $d_i$ is the distance between $u$ and $i$. 
2. The AP algorithm considers every possible distance threshold to classify the nodes as children of $u$ in the graph $G$ , and for each threshold $j$ returns the recall $R_j$ and the precision $P_j$ . Sorted $R_j$ and calculated
$$AP = \sum_{i=1}^n (R_i − R_{i−1})P_i$$
The Mean Average Precision (mAP) is
$$mAP= \frac{1}{|G|}\sum_{u∈G} AP_u$$

A higher mAP means a more efficient embedding when reconstructing the prerequisite relationships of the annotated graph.

Improved Concept Embeddings for Learning Prerequisite Chains: mAP

This evaluation method is to rank all the topics by increasing norm, defined as the distance between a concept $u$ and the origin of the Poincaré vector space, and verify how many annotated prerequisite relationships are satisfied/included in this rank.

Improved Concept Embeddings for Learning Prerequisite Chains: Ranking by Norm

University of Michigan - Ann Arbor

- Poincaré embeddings (Nickel and Kiela, 2017) is a method that better fit for data with latent hierarchies than other embedding models using the Euclidean vector space.
- Dhingra et al. (2018) introduced a method to obtain Poincaré word embeddings from natural language text.
- This paper combines the two methods above to obtain prerequisite relations between concepts from two datasets in the domain of Natural Language Processing. 

Improved Concept Embeddings for Learning Prerequisite Chains: Methods

Nickel, M., & Kiela, D. (2017). Poincaré embeddings for learning hierarchical representations. In Advances in neural information processing systems (pp. 6338-6347).

References for Poincaré embeddings

Dhingra, B., Shallue, C. J., Norouzi, M., Dai, A. M., & Dahl, G. E. (2018). Embedding text in hyperbolic spaces. arXiv preprint arXiv:1806.04313.

Reference for generating Poincaré embeddings from natural-language text corpora

Löffel, E. P. (2019). Improved Concept Embeddings for Learning Prerequisite Chains

Paper: https://pdfs.semanticscholar.org/6073/0900a80fcee29e9059fd293a1fa38742abf3.pdf

Github: https://github.com/eloffel/improved_embeddings

Improved Concept Embeddings for Learning Prerequisite Chains: Reference

Improved Concept Embeddings for Learning Prerequisite Chains: Datasets

- The embedding models using the Euclidean vector space are unable to capture hierarchical relationships, which is not optimized for embedding structures like graphs and trees. Nickel and Kiela (2017) proposed a model that embeds concepts into a hyperbolic space, which can be thought of as a continuous version of trees structure and therefore provides a better fit to embed data with latent hierarchies.
- Poincaré ball model represents the entire hyperbolic space within the border of an n-dimensional sphere. This model, referred to as Poincaré Embeddings, generates the embeddings having as its input a weighted directed graph $G = \{(b, a)\}$, in which each node represents a concept and a directed edge between a and b means that a is a hypernym of b, in other words, b is a prerequisite concept of a. 

Improved Concept Embeddings for Learning Prerequisite Chains: Poincaré embeddings

To generate Poincaré embeddings from a natural language text corpus, the author converted the text to a list of directed edges in the format $u,v,weight$, where $v$ is a hypernym of $u$, as input to the Poincaré embeddings algorithm, using the method described by Dhingra et al. (2018).  They constructed a co-occurrence graph $G = \{(u, v)\}$ that includes all pairs of words that occur within a fixed window of each other. Each edge $(u, v)$ in the graph has a weight $w = f^c$, where $f$ is the frequency of the co-occurrence pairs in the corpus and $c$ is a downsampling constant. 

Improved Concept Embeddings for Learning Prerequisite Chains: Generating Poincaré embeddings from natural-language text corpora

- Learning rate = 0.2
- Number of negative examples = 80 
- Number of epochs = 100
- Epochs of burn-in = 10 
- Number of dimensions = 2, 3, 5, 10, 50, 100

Learn Before

Related

Learn After