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

Ranking by Norm is an evaluation method used to assess learned prerequisite chains. It ranks all topics by increasing norm, which is defined as the distance between a concept $$u$$ and the origin of the Poincaré vector space. The method then evaluates performance by verifying how many annotated prerequisite relationships are satisfied or included within 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. https://arxiv.org/abs/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

- 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

Improved Concept Embeddings for Learning Prerequisite Chains: Model parameters

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, \text{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.

Learn Before

Related

Learn After