We present a graph-based approach to discover and extend semantic relationships found in a mathematics curriculum to more general network structures that can illuminate relationships within the instructional material. Using words representative of a secondary level mathematics curriculum we identi ed in separate work, we constructed two similarity networks of word problems in a mathematics textbook, and used analogous random walks over the two networks to discover patterns. The two graph walks provide similar global views of problem similarity within and across chapters, but are a ected di erently by number of math words in a problem and math word frequency.
As a means to automatically discover relationships among
learning objects and to reveal their knowledge components,
we demonstrate the use of direct similarity metrics and
random graph walks to relate exercises in a mathematics
curriculum. We rst apply a standard cosine similarity measure
between pairs of exercises, based on bag-of-word vectors
consisting of math terms that we identi ed in separate work
[
Random walks over graphs have been used extensively to
measure text similarity. Applications include similarity of
web pages [
An initiative where elementary science and math tests are a
driver for arti cial intelligence has led to work on knowledge
extraction from textbooks. Berant et al. [
Other work that addresses knowledge representation from
text includes ontology learning [
We used 1800 exercises from 17 chapters of a Grade 7 mathematics curriculum. Most are word problems, as illustrated in Figure 1. They can incorporate images, tables, and graphs, but for our analysis, we use only the text. The vocabulary of the resulting text consists of 3,500 distinct words. We construct graphs where math exercises are the nodes, or in a bipartite graph, math exercises are the left side nodes and words are the right side nodes. Our initial focus is on exercise similarity due to similarity of the math skills that exercises tap into, and we use mathematics terminology as an indirect proxy of skills a problem draws upon.
The text of the word problems includes ordinary language expressions unrelated to the mathematics curriculum, such as the nouns machines, widgets shown in problem in Figure 1, or the verbs produces, damaged. For our purposes, mathematics terminology consists of words that expresses concepts that are needed for the mathematical competence the curriculum addresses. To identify these terms, we developed annotation guidelines for human annotators who label words in their contexts of use, and assessed the reliability of annotation by these guidelines. Words can be used in the math texts sometimes in a math sense and sometimes in a non-math sense. Annotators were instructed to label terms based on the most frequent usage.
Using a chance-adjusted agreement coe cient in [
A random walk on a graph starts at a given node and steps with random probability to a neighboring node. The same random decision process is employed at this and every subsequent node until a termination criterion is met. Each time a node is visited, it is counted. Open random walks require that the start node and end nodes di er. Traversal methods may employ a bias to navigate toward or away from certain neighbors through edge weights or other graph attributes. In a graph, G = (V; E) with nodes V and edges E, a random walk that begins at vx and ends at vy can be denoted as (vx; :::; vy). By performing several random walks, the fraction of times the node vy is visited converges to the probability of target vy being visited given the start node vx, which can be expressed as P (vyjvx) under the conditions of the walk. In the case of a random walk length of 1, P (vyjvx) will simply measure the probability of vy being selected as an adjacent node to vx.
Math exercises are represented as bag-of-words vectors with boolean values to indicate whether a given math term is present. Cosine similarity quanti es the angle between the two vectors, and is given by the dot product of two vectors. cos(t; e) =
te ktkkek
Pn = pPn i=1 tieii=1 (ei)2 i=1 (ti)2pPn (1) Similarity values of 1 indicate that both the vectors are the same whereas a value of zero indicates orthogonality between the two vectors. Pairwise cosine similarities for all 1800 exercises were computed, yielding a cosine similarity matrix Mcos. The matrix corresponds to a graph where non-zero cosine similarities are edge weights between exercises. In a graph walk, the probability that a node vy will be reached in one step from a node vx is given by the product of the degree centrality of vx and the normalized edge weight (vx; vy). With each exercise as a starting node, we performed 100,000 random walks on the cosine-similarity graph, stepping with proportional probability to all outgoing cosine similarity weights. To measure 2nd degrees of separation, with each walk we made two steps.
For two math vectors considered as the sets A and B, cosine similarity can be conceptualized in terms of the intersection set C = A [ B and set di erences A n B and B n A. Cosine similarity is high when jCj A n B and jCj B n A. The degree of a node a ects the probability of traversing any edge from that node. The two factors that a ect degree centrality of a start node are the document frequencies of its math words, and the total number of math words. Here, document frequency (df) is the normalized number of exercises a word occurs in. A high df math word in a problem increase its degree centrality because there will be more problems it can share words with, resulting in non-zero cosine values and therefore edges. The number of math words in a problem also increases its degree centrality.
The set of exercises Ve are the left-side nodes and the math words Vw are the right-side nodes in the undirected bipartite graph G = (Ve; Vw; E), where an edge exists between vex and vwi if exercise x contains the math word i.
We performed open random walks on this graph to measure similarity between nodes. To measure the similarity of exercises, we walk in even steps { a step to a connected word followed by a step back to one of the exercises that shares that word. The degrees of separation between vertices on the same side of the graph (e.g. exercise-to-exercise) will be l=2 where l is the length of the walk. In this paper, we explored rst and second degrees of separation so our bipartite graphs had a walk length of 4. Because exercise nodes are connected via word nodes, we interpret the fraction of node visits as a similarity measure between the source node and any node visited. We performed 100,000 random walks from each node. Exercise-to-exercise similarity can be visualzed as square matrices with source nodes in the rows and target nodes in the columns. To factor out the times a source may have been selected as one of the targets, we set the diagonal of the matrix to zero. We then normalized across the rows so that we could interpret the distribution across the row as a probability distribution to all other nodes for that source node.
We compare the three measures of similarity between exercises: 1) cosine similarity, 2) random walks using cosine similarity as edge weights, and 3) random walks along a bipartite graph of exercises and words.
We describe exercise-to-exercise similarity with square matrices where each exercise is represented as a row-column. A number of features of the measures are embedded in Figure 2, which shows heatmaps of color values for pairs of exercises in chapter 6 for each matrix. We nd that within chapters and especially within sections of those chapters, there is a high degree of similarity between exercises regardless of the measure. This demonstrates that words within sections and chapters share a common vocabulary. We can see that Mcos has more extreme values than Mcosrw; as explained below, it has both more zero cosine values, and more very high values. This is most likely because Mcosrw, from doing the walk, picks up exercises that are another degree of separation away. When the row of the matrix is normalized to capture the distribution of the source node, the otherwise high values from Mcos are tempered in the Mcosrw matrix. This shift to a large number of lower scores is shown in the bottom panel of Figure 3. Mbp and Mcosrw are very similar, but Mbp generally has a wider dynamic range.
Table 1 provides summary statistics for cosine similarity and the two random walks for all pairs of problems (N=3,250,809). The cosine matrix is very sparse, as shown by the median value of 0. Of the two random walk similarities, rwcos has a lower standard deviation around the mean, but otherwise the two random walks produce similar distributions. The similarity values given by cosine and the cosine random walk will increasingly di er the more that the start problem has relatively higher degree centrality due either to more words or higher frequency of words in exercises (df). For reference, the word that occurs most frequently, number, has a df of 0.42, and the second most frequent occurs in only 15% of the exercises. Fifty eight nodes have no edges (0 degree), the most frequent number of edges is 170, and the maximum is 1,706. Table 2 gives the summary statistics for df, number of math words, and degree centrality. Inspection of the data shows that for pairs of problems in the two chapters for our case study, if the cosine similarity between a pair is high ( 0.75), the similarity values for rwcos tend to go down as the number of shared word increases from 3 to between 5 and 7. For the rwbp, the opposite trend occurs, where the similarity goes up as the number of words increases. This di erence helps account for an observed divergence in the two graph walks for sections 5 and 6 of Chapter 6.
Table 3 illustrates two pairs of problems from section 5 that have high cosine similarities, and relatively higher rwbp similarities (greater than the rw means of 0.0055) and relatively lower rwcos (lower than the rw means). The reverse pattern is seen for two pairs of problems from section 6 that have high cosine similarities. These problems have higher than average rwcos and lower than average rwbp. What di erentiates the two pairs of problems is that the section 5 problems have a relatively large number of words in common: 14 for the rst pair, 12 for the second pair. In both pairs, some of the words have relatively high document frequency. As discussed above, these two properties increase the degree centrality of the start node of a step in the rwcos graph, and thus lower the probability of hitting each of the start node's one-degree neighbors. This e ect propagates along the two steps of the walk. For the rwbp graph, however, as the number of shared math words for a pair of problems increases, the number of paths from one to the other also increases, thus raising the probability of the traversal. This e ect also propagates through a two-step walk. In contrast to the section 5 problems, the two section 6 problems have relatively fewer words in common: 3 for both pairs.
For problem pairs where the cosine similarity is between 0.40 and 0.60, the mean similarity from rwbp is 30% higher than for rwcos for when the number of math words in common is 3 (0.0033 vs. 0.0043), 80% higher when the number of math words in common is 6 (0.0024 versus 0.0045), and three as high when the number of math words in common is 9 (0.0023 versus 0.0068). For problems pairs where the minimum maximum mean median std. dev.
df cosine similarity is less than 0.20, the two walks produce very similar results. The average similarity values for the bipartite walk are about 20% higher, and the maximum values are higher, but the two walks produce similar means, independent of the lengths of the common word vectors, or the total number of math words.
Since we normalized the matrices across rows, which are the source nodes, di erences between the bipartite matrix, Mbp, and the cosine matrices implied that the degree of the target node had a greater impact on the variability in the bipartite matrix. To measure the impact of the edge degree on the target nodes, we considered the column sum for those targets that had 1 edge, those that had 2, etc. up to 20 edges. The results are summarized in Figure 4. As can be seen, the column sum varies linearly by the number of target edges in the bipartite matrix, whereas the cosine matrices do not. We found the cubed root of the column sum in Mbp approaches the distribution of column sums of the cosine matrices, which is provided in Figure 4.
Visualization of the three similarity matrices shows they reveal the same overall patterns, thus each is con rmed by the others. However, the bipartite walk was the most sensitive to word frequency across exercises, and the number of words in problems. With our goal of automatically discovering knowledge components and identifying their relationships, the random walk that stepped in proportion to its cosine similarity performed best. It was able to discover second-degree relationships that seem reasonable as we explore by eye those matches. Future work will test these relationships with student performance data. We should nd, for example, that if two exercises are conceptually similar, then student outcomes should also be similar and learning curves should reveal shared knowledge components. In this respect, such automatically constructed knowledge graphs can create more re ned domain models that intelligent tutoring systems and robust assessments can be built upon.