What path(s) do high-performing students take through online educational materials? What social networks can foster or inhibit learning? Do users of online learning tools behave as the system designers expect? What diagnostic substructures are commonly found in studentproduced diagrams? Can we use prior student data to identify students' solution plan, if any? Can we use prior student data to provide meaningful hints in complex domains? Can we identify students who are particularly helpful based upon their social interactions?
Thus, graphs are simple in concept, general in structure, and have wide applications for Educational Data Mining (EDM).
Despite the importance of graphs to data mining and data
analysis there exists no strong community of researchers focused on
Graph-Based Educational Data Mining. Such a community is
important to foster useful interactions, share tools and techniques,
and to explore common problems.
2. GEDM 2014
This is the second workshop on Graph-Based Educational Data
Mining. The first was held in conjunction with EDM 2014 in
London [
The group discussion sections at that workshop focused on the
distinct uses of graph data. Some of the work presented focused
on student-produced graphs as solution representations (e.g. [
These differing uses motivate different analytical techniques and, as participants noted, change our underlying assumptions about the graph structures in important ways. 3. GEDM 2015 Our goal in this second workshop was to build upon this nascent community structure and to explore the following questions: 1. What common goals exist for graph analysis in EDM? 2. What shared resources such as tools and repositories are re
quired to support the community? 3. How do the structures of the graphs and the analytical methods change with the applications?
The papers that we include here fall into four broad categories: interaction, induction, assessment, and MOOCs.
Work by Poulovassilis et al. [
Lynch et al. by contrast, examined user-system interactions from existing model-based tutors to examine the impact of specific design decisions on student performance.
Price & Barnes [
The goal in much of this work is to identify rules that can be used to characterize good and poor interactions or good and poor graphs. Xue at al. sought address this challenge in part via the automatic induction of graph rules for student-produced diagrams [22]. In their ongoing work they are applying evolutionary computation to the induction of Augmented Graph Grammars, a graph-based formalism for rules about graphs.
The work described by Leo-John et al. [
And finally, Vigentini & Clayphan [20], and Brown et al. [
Graph Grammar Induction via Evolutionary Computation
Electrical Engineering
Department North Carolina State
University Raleigh, North Carolina,
U.S.A. lxue3@ncsu.edu
Computer Science
Department North Carolina State
University Raleigh, North Carolina,
U.S.A. cflynch@ncsu.edu Min Chi Computer Science
Department North Carolina State
University Raleigh, North Carolina,
U.S.A. mchi@ncsu.edu
Augmented Graph Grammars provide a robust formalism for representing and evaluating graph structures. With the advent of robust graph libraries such as AGG, it has become possible to use graph grammars to analyze realistic data. Prior studies have shown that graph rules can be used to evaluate student work and to identify empirically-valid substructures using hand-authored rules. In this paper we describe proposed work on the automatic induction of graph grammars for student data using evolutionary computation via the pyEC system.
Graph Grammars are logical rule representations for graph
structures. They can be designed to encode classes of
suitable graphs to recognize complex sub-features. They were
introduced by Rosenfeld and Pfaltz in 1969 as \Context-free
web grammars" [
In this paper we describe our ongoing work on the automatic induction of Augmented Graph Grammars via Evolutionary Computation (EC). Our long-term goal in this work is to develop automated techniques that can extract empiricallyvalid graph rules which can, in turn, be used to classify student-produced argument diagrams and to provide the basis for automated student guidance and evaluation. This will build upon our prior on the evaluation of a-priori rules for student arguments. We will begin with background material on Augmented Graph Grammars and discuss prior work on grammar induction. We will then present an overview of our planned work.
Classical graph grammars are designed to deal with xed
graphs that are composed from a nite set of static node and
arc types. Augmented graph grammars are an extension of
simple graph grammars that allow for complex node and arc
types, optional substructures, and complex rule expressions
[
Graph and relational data has grown increasingly prevalent
and graph analysis algorithms have been applied in a wide
range of domains from social network analysis [
A number of algorithms have been developed to discover
frequent subgraphs. These include the gSpan algorithm
developed by Yan and Han [
S a : c
b 8t:T pye = \claim00or\hypothesis009 <>> a:T ype = \Citation00 =>>
b:T ype = \Citation00
:>> c:T ype = \Comparison00 ;>>
algorithm [
The SUBDUE system takes a greedy-compression approach
to graph mining. SUBDUE searches for candidate
subgraphs that can best compress the input graphs by replacing
a candidate subgraph with a single vertex. Then nodes and
arcs are added to the vertices to form new candidate
subgraphs. The process is recursive and relies on the
MinimumDescription-Length (MDL) principle to evaluate the
candidates. SUBDUE has been applied successfully to extract
structure from visual programming [
While these methods are successful they have practical and theoretical limitations. Both classes of approaches are limited to static graphs composed from a nite alphabet of node and arc types. The frequent subgraph approaches are based upon iterative graph walks and can be computationally expensive and are limited to nding exact matches. They do not generalize beyond the exact graphs matched nor do they allow for recursive typing. SUBDUE, by contrast is a greedy algorithm that nds the single most descriptive grammar and does not allow for weighted matches.
For our present purposes, however, our goal is to identify multiple heirarchical classes of the type shown in Figure 2 that can: generalize beyond exact node and arc types; can draw on recursive rule productions; and can be weighted based upon the graph quality. Moreover our long-term goal with this work is to explore graph rule induction mechanisms that can be expanded to include textual rules and complex constraints. For that reason we have elected to apply evolutionary computation. This is a general-purpose machine learning mechanism that can be tunes to explore a range of possible induction mechanisms.
Evolutionary Computation (EC) is a general class of machine learning and optimization methods that are inspired by the process of Darwinian evolution through natural selection [23] such as Genetic Algorithms [24] or Genetic Programming [25]. EC algorithms begin with a population of randomly generated candidate solutions such as snippets of random code, strings representing a target function, or formal rules. Each of these solutions is ranked by a tness function that is used to evaluate the quality of the individuals. These functions can be de ned by absolute measures of success such as a suite of test cases, or by relative measures such as a competition between chess-playing systems. Once the individuals have been ranked a new generation of individuals is produced through a combination of crossover and mutation operations. Crossover operations combine two or more parents to produce one or more candidate children. In Genetic Algorithms where the candidate solutions are represented as strings this can be accomplished by splitting two parents at a given index and then exchanging the substrings to produce novel children. In Genetic Programming the parents exchange blocks of code, functions, or subtrees. Mutation operations alter randomly-selected parts of a candidate solution by swapping out one symbol or instruction for another, adding new sub-solutions, or deleting components. This process of ranking and regeneration will iterate until a target performance threshold is reached or a maximum number of generations has passed.
EC methods are highly general algorithms that can be readily adapted to novel domains by selecting an appropriate solution representation and modi cation operations. Thus, in contrast to more speci c methods such as SUBDUE, the EC algorithm allows us to tune the inductive bias of our search and to explore alternative ways of traversing the solution space. Therefore it is well suited to our present needs. This exibility is costly, however, as EC is far more computationally expensive than more specialized algorithms, and applications of EC can require a great deal of tuning for each use. In the subsections below we will describe the tness function and the operators that we will use in this work. For this work we will rely on pyEC a general purpose evolutionary computation engine that we have developed [26].
Our initial analysis will be based upon a corpus of expert
graded student produced argument diagrams and essays
previously described in [
For the purposes of our present experiments we will use a restricted solution representation that relies on a subset of the augmented graph grammar formalism exempli ed by the rule shown in Figure 2. This will include only element types and recursive productions. In future work we plan to support the induction of more complex rules de ned by multiple graph classes, novel productions, and expressions. However for the present study we will focus on the simple case of individual classes coupled with prede ned productions.
We plan to use the frequency correlation metric previously
employed in [
Our mutation operator will draw on the prede ned graph ontology to make atomic changes to an existing graph class. The change will be one of the following operations:
Change Arc Change an existing arc's type or orientation. Delete Node Delete a node and its associated arcs.
By design the crossover operation should, like genetic crossover, be conservative. Two very similar parents should produce similar o spring. Crossover operations should therefore preserve good building blocks and sub-solutions or introns through random behavior [25]. Arbitrary graph alignment and crossover is a challenging problem that risks causing unsustainable changes on each iteration. We therefore treat graph crossover as a matrix problem.
For each pair of parent classes we will de ne a pair of diagonal matricies of the type illustrated in Figure 3. The letter indicies on the top and right indicate nodes while the numerical indicies internally indicate arcs, and the ; symbol indicates that no arc is present. The matricies are generated in a canonical order based upon the order in which the nodes were added to the class. Thus on each iteration of the crossover process the corresponding elements will obtain the same index. As a consequence good subsolutions will obtain the same location and will tend to be preserved over time. Once a set of parent matricies has been generated we then generate two child matricies of the same size as the parents and then randomly select the node and arc members. In the example shown in gures 3 and 4 the parents have nodes fA,B,C,Dg and fE,F,Gg while the children have fE,B,G,Dg and fA,F,Cg. Thus we align the nodes in canonical order and, for each node pair, we ip a coin to decide where they are copied. If one parent is larger than the other than any additional nodes, in this case D, will be copied to the larger child. We then perform a comparable exchange process for the arcs. Each arc or potential arc is de ned uniquely in the matricies by its endpoints. We thus align the lists of arcs in a comparable manner and then decide randomly which arc, or empty arc, to copy. As with the nodes, extra arcs from the larger parent, in this case 3,5, and one ; are copied directly into the larger of the two children.
In this paper we presented a method for the induction of augmented graph grammars through evolutionary computation. We are presently applying this work to the automatic induction of empirically-valid rules for student-produced argument diagrams. This work will serve to extend our prior e orts on the use of augmented graph grammars for student 7 F 7 grading and feedback. This work represents an improvement over prior graph grammar induction algorithms which are limited to classical graph grammars and greedy extraction. This work also represents an extension for evolutionary computation by shifting it into a new domain. As part of this work we also plan to explore additional extensions to the standard evolutionary computation algorithm to address problems of over- tting such as 2 reduction.
E F A F
Communities of Performance & Communities of Preference Rebecca Brown North Carolina State
University
Raleigh, NC rabrown7@ncsu.edu
Michael Eagle North Carolina State University
Raleigh, NC mjeagle@ncsu.edu
Ryan Baker Teachers College, Columbia
University
New York, NY ryanshaunbaker@gmail.com
Collin Lynch North Carolina State
University
Raleigh, NC cflynch@ncsu.edu
Jennifer Albert North Carolina State
University
Raleigh, NC jennifer_albert@ncsu.edu
Yoav Bergner Educational Testing Service
Princeton, NJ ybergner@gmail.com
Yuan Wang Teachers College, Columbia
University
New York, NY elle.wang@columbia.edu
Tiffany Barnes North Carolina State
University
Raleigh, NC tmbarnes@ncsu.edu
Danielle McNamara Arizona State University
Phoenix, AZ dsmcnamara1@gmail.com The current generation of Massive Open Online Courses (MOOCs) operate under the assumption that good students will help poor students, thus alleviating the burden on instructors and Teaching Assistants (TAs) of having thousands of students to teach. In practice, this may not be the case. In this paper, we examine social network graphs drawn from forum interactions in a MOOC to identify natural student communities and characterize them based on student performance and stated preferences. We examine the community structure of the entire course, students only, and students minus low performers and hubs. The presence of these communities and the fact that they are homogeneous with respect to grade but not motivations has important implications for planning in MOOCs.
Keywords MOOC, social network, online forum, community detection 1. INTRODUCTION The current generation of Massive Open Online Courses (MOOCs) is designed to leverage student interactions to augment instructor guidance. The activity in courses on sites such as Coursera and edX is centered around user forums that, while curated and updated by instructors and TAs, are primarily constructed by students. When planning and building these courses, it is hoped that students will help one another through the course and that interacting with stronger students will help to improve the performance of weaker ones. It has not yet been shown, however, that this type of support occurs in practice.
Prior research on social networks has shown that social groups, even those that gather face-to-face, can fragment into disjoint sub-communities [37]. This small-group separation, if it takes place in an online course, can be considered negative or positive, depending on one's perspective. If poor students communicate only with similarly-floundering peers, then they run the risk of perpetuating misunderstandings and of missing insights discussed by better-performing peers and teaching staff. An instructor may wish to avoid this fragmentation to encourage poor students to connect with better ones.
These enduring subgroups may be beneficial, however, by
helping students to form enduring supportive relationships. Research
by Li et al. has shown that such enduring relationships can
enhance students' social commitment to a course [
Eckles and Stradley [
We have previously shown that students can form stable
communities and that those communities are homogeneous with
respect to performance [
In the remainder of this paper we will survey prior educational literature on community formation in traditional and online classrooms. We will then build upon our prior work by examining the impact of hub users. And we will look at the impact of user motivations on community formation.
RELATED WORK
2.1 MOOCs, Forums, & Student Performance
A survey of the literature on MOOCs shows the beginnings of a
research base generating an abundance of data that has not yet
been completely analyzed [
Stahl et al. [30] illustrates how through this online interaction
students collaborate to create knowledge. Thus students' forum
activity is good not only for the individual student posting
content or receiving answers, but for the class as a whole. Huang et
al. [
Huang et al. also found that these superposters did not suppress the activity of less-active users. Rienties et al. [25] examined the way in which user interaction in MOOCs is structured. They found that allowing students to self-select collaborators is more conducive to learning than randomly assigning partners. Further, Van Dijk et al. [31] found that simple peer instruction is significantly less effective in the absence of a group discussion step, pointing again to the importance of a class discussion forum.
More recently Rose et al. [27] examined students' evolving interactions in MOOCs using a Mixed-Membership Stochastic Block model which seeks to detect partially overlapping communities.
They found that the likelihood that students would drop out
of the course is strongly correlated with their community
membership. Students who actively participated in forums early in
the course were less likely to drop out later. Furthermore, they
found one forum sub-community that was much more prone
to dropout than the rest of the class, suggesting that MOOC
communities are made up of students who behave in similar
ways. This community can in turn reflect or impact a student's
level of motivation and their overall experience in a course much
like the \emotional contagion" model used in the Facebook mood
manipulation study by Kramer, Guillroy, and Hancock [
Yang et al. [36] also notes that unlike traditional courses
students can join MOOCs at different times and observed that
students who join a course early are more likely to be active
and connected in the forums, and less likely to drop out, than
those who join later. MOOCs also attract users with a range of
individual motivations. In a standard classroom setting students
are constrained by availability, convention, and goals. Few
students enroll in a traditional course without seeking to complete
it and to get formal credit for doing so. MOOCs by virtue of
their openness and flexibility attract a wide range of students
with unique personal motivations [
This social presence considers the nature and persistence of student interactions and the extent to which they reinforce students' behaviors. In their analysis, the authors sought to test whether network relationships, specifically students' centrality in their social graph, is related to their social performance as measured by the nature and type of their interactions. To that end, they examined a set of course logs taken from a series of online courses offered within a public university. They found that students' position within their social graph was positively correlated with the nature and type of their interactions, thus indicating that central players also engaged in more useful social interactions. They did not extend this work to groups, however, focusing solely on individual hub students.
Other authors have also examined the relationship between
network centrality, neighbor relationships, network density, and
student performance factors. Eckles and Stradley [
Fire et al. [
Online student interaction in blended courses has also been
linked to course performance. Dawson [
Dedicated question-and-answer forums are more structured than MOOC forums, with question and answer posts identified, but a similar approach might help identify which students in a MOOC ask or answer the most questions.
Choo et al. [
In the context of complex networks, a community structure is a
subgraph which is more densely connected internally than it is to
the rest of the network. We chose to apply the Girvan-Newman
edge-betweenness algorithm (GN) [
It then ranks the edges in the graph by their edge-betweenness
value and removes the highest ranking edge. To calculate
Edgebetweenness we identify the shortest path p(a;b) between each
pair of nodes a and b in the graph. The edge-betweenness
of an arc is defined as the number of shortest paths that it
participates in. This is one of the centrality measures explored
by Kovanovic et al. above [
Thus the algorithm operates by iteratively finding and removing
the highest-value communications channel between communities
until the graph is fully segmented. For this analysis, we used
the iGraph library [
The strength of a candidate community can be estimated by
modularity. The modularity score of a given subgraph is defined
as a ratio of its intra-connectedness (edges within the subgraph)
to the inter-connectedness with the rest of the graph minus the
fraction of such edges expected if they were distributed at
random [
All of the weekly assignments were structured as numeric input or multiple-choice questions. The assignments were graded automatically. In each assignment, students were asked to conduct analyses on a data set provided to them and answer questions about it. In order to receive a grade, students had to complete this assignment within two weeks of its release with up to three attempts for each assignment, and the best score out of the three attempts was counted. The course had a total enrollment of over 48,000, but a much smaller number actively participated. 13,314 students watched at least one video, 1,242 students watched all the videos, 1,380 students completed at least one assignment,and 778 made a post or comment in the weekly discussion sections. Of those with posts, 426 completed at least one class assignment. 638 students completed the online course and received a certificate (meaning that some students could earn a certificate without participating in forums at all).
In addition to the weekly assignments the students were sent a survey that was designed to assess their personal motivations for enrolling in the course. This survey consisted of 3 sets of questions: MOOC-specific motivational items; two PALS (Patterns of Adaptive Learning Survey) sub-scales [21], Academic Efficacy and Mastery-Goal Orientation; and an item focused on confidence in course completion. It was distributed to students through the course's E-mail messaging system to students who enrolled in the course prior to the official start date. Data on whether participants successfully completed the course was downloaded from the same course system after the course concluded. The survey received 2,792 responses; 38% of the participants were female and 62% of the participants were male. All of the respondents were over 18 years of age.
The MOOC-specific items consisted of 10 questions drawn from
previous MOOC research studies (cf. [
PALS scales have been widely used to investigate the relation
between a learning environment and a student's motivation (cf.
[
Respondents were also asked to self-rate their confidence on a scale of 1 to 10 as to whether they could complete the course according to the pace set by the course instructor. All three groups of items were domain-general. 4. METHODS For our analysis, we extracted a social network from the online forum associated with the course. We assigned a node to each student, instructor, or TA in the course who added to it. Nodes representing students were labeled with their final course grade out of 100 points. The Coursera forums operate as standard threaded forums. Course participants could start a new thread with an initial post, add a post to an existing thread, and add a comment or child element below an existing post. We added a directed edge from the author of each post or comment to the parent post and to all posts or comments that preceded it on the thread based upon their timestamp. We made a conscious decision to omit the textual content of the replies with the goal of isolating the impact of the structure alone.
We thus treat each reply or followup in the graph as an implicit
social connection and thus a possible relationship. Such implicit
social relationships have been explored in the context of
recommender systems to detect strong communities of researchers [
This is, by design, a permissive definition that is based upon the assumption that individuals generally add to a thread after viewing the prior content within it and that individual threads can be treated as group conversations with each reply being a conscious statement for everyone who has already spoken. The resulting network forms a multigraph with each edge representing a single implicit social interaction. We removed self loops from this graph as they indicate general forum activity but not any meaningful interaction with another person. We also removed vertices with a degree of 0, and collapsed the parallel edges to form a simple weighted graph for analysis.
In the analyses below we will focus on isolating student performance and assessing the impact of the faculty and hub students.
We will therefore consider four classes of graphs: ALL the complete graph; Student the graph with the instructor and TAs removed; NoHub the graph with the instructor and hub users removed; and Survey which includes only students who completed the motivation survey. We will also consider versions of the above graphs without students who obtained a score of 0, and without the isolated individuals who connect with at most one other person. As we will discuss below, a number of students received a zero grade in the course. Because this is an at-will course, however, we cannot readily determine why these scores were obtained.
They may reflect a lack of engagement with the course,
differential motivations for taking the course, a desire to see the course
materials without assignments, or genuinely poor performance.
4.1 Best-Friend Regression & Assortativity
Fire et al. [
To examine whether the same correlation existed in a massive online course in which students were less likely to know each other beforehand and there were no group assignments, we calculated each student's best friend in the same manner and performed a similar correlation.
The simple best friends analysis gives a straightforward mechanism for correlating individual students. However it is also worthwhile to ask about students who are one-step removed from their peers. Therefore we will also calculate the grade assortativity (rG) of the graphs. Assortativity describes the correlation of values between vertices and their neighbors [23]. The assortativity metric r ranges between -1 and 1, and is essentially the Pearson correlation between vertex and their neighbors [23].
A network with r = 1 would have each vertex only sharing edges with vertices of the same score. Likewise, if r = 1 vertices in the network would only share edges with vertices of different scores. Thus grade assortativity allows us to measure whether individuals are not just connected directly to individuals with similar scores but whether they correlate with individuals who are one step removed.
Several commonly studied classes of networks tend to have
patterns in their assortativity. Social networks tend to have high
assortativity, while biological and technological networks tend
to have negative values (dissortativity) [23]. In a homogeneous
course or one where students only form stratified communities
we would expect the assortativity to be very high while in a
heterogeneous class with no distinct communities we would expect
it to be quite low.
4.2 Community Detection
The process of community detection we employed is briefly
described here [
Homogeneity in this context would mean that students gathered and communicated primarily with equally-performing peers and thus that they did not consistently draw from better-performing classmates and help lower-performing ones or that the at-will communities served to homogenize performance, with the students in a given cluster evening out over time.
While algorithms such as GN are useful for finding clusters they
do not, in and of themselves, determine the right number of
communities. Rather, when given a target number they will seek
to identify the best possible set of communities. In some
implementations the algorithm can be applied to iteratively select the
maximum modularity value over a possible range. Determining
the correct number of communities to detect, however, is a
non-trivial task especially in large and densely connected graphs
where changes to smaller communities will have comparatively
small effects on the global modularity score. As a consequence
we cannot simply optimize for the best modularity score as we
would risk missing small but important communities [
Therefore, rather than select the clusterings based solely on
the highest modularity, we have opted to estimate the correct
number of clusters visually. To that end we plotted a series of
modularity curves over the set of graphs. For each graph G we
applied the GN algorithm iteratively to produce all clusters in
the range (2;jGN j). For each clustering, we then calculated the
global modularity score. We examined the resulting scores to
identify a crest where the modularity gain leveled off or began to
decrease thus indicating that future subdivisions added no
meaningful information or created schisms in existing high-quality
communities. This is a necessarily heuristic process that is
similar to the use of Scree plots in Exploratory Factor Analysis [
We define the number identified as the natural cluster number. 5. RESULTS AND DISCUSSION Before removing self-loops and collapsing the edges, the network contained 754 nodes and 49,896 edges. The final social network contained 754 nodes and 17,004 edges. 751 of the participants were students, with 1 instructor and 2 TAs. One individual was incorrectly labeled as a student when they were acting as the Chief Community TA. Since this person's posts clearly indicated that he or she was acting in a TA capacity with regard to the forums, we relabeled him/her as a TA. Of the 751 students 304 obtained a zero grade in the course leaving 447 nonzero students. 215 of the 751 students responded to the motivation survey.
There were a total of 55,179 registered users, so the set of 754 forum participants is a small fraction of the entire course audience. However, forum users are not necessarily those who will make an effort or succeed in the course. Forum users did not all participate in the course, and some students who participated in the course did not use the forums: 1,381 students in the course got a grade greater than 0, and 934 of those did not post or comment on the forums, while 304 of the 751 students who did participate in the forums received a grade of 0. Clearly students who go to the trouble of posting forum content are in some respect making an effort in the course beyond those who don't, but this does not necessarily correspond to course success. 5.1 Best-Friend Regression & Assortativity We followed Fire et al.'s methodology for identifying Best Friends in a weighted graph and calculated a simple linear regression over the pairs. This correlation did not include the instructor or TAs in the analysis. We calculated the correlation between the students' grades to their best friends' grades in the set using Spearman's Rank Correlation Coefficient ( ) [34]. The two variables were strongly correlated, (748)=0:44, p<0:001. However, the correlation was also affected by the dense clusters of students with 0 grades. After removing the 0 grade students we found an additional moderate correlation, (444)=0:29, p<0:001.
Thus the significant correlation between best-friend grade and grade holds over the transition from the traditional classroom to a MOOC. This suggests that students in a MOOC, excluding the many who drop out or do not submit assignments, behave similarly to those in a traditional classroom in this respect. These results are also consistent with our calculations for assortativity.
There we found a small assortative trend for the grades as shown in Table 1. These values reflect that a student was frequently communicating with students who in turn communicated with students at a similar performance level. This in turn supports our belief that homogeneous communities may be found. As Table 1 also illustrates, the zero-score students contribute substantially to the assortativity correlation as well with the correlation dropping by as much as a third when they were removed. 5.2 Community Structure The modularity curves for the graphs both with and without zero-score students are shown in Figures 1 and 2. We examined these plots to select the natural cluster numbers which are shown in Table 2. As the values illustrate the instructor, TAs, and hub students have a disproportionate impact on the graph structure. The largest hub student in our graph connects to 444 out of 447 students in the network. The graph with all users had lower modularity and required more clusters than the graphs with only students or only non-hubs (see Table 2), with the non-hub graph having the highest modularity. This suggests that non-hub students formed more isolated communities, while teaching staff and hubs communicated across these communities and connected them.
This largely consistent with the intent of the forums and the active role played by the instructor and TAs in monitoring and replying to all relevant posts in the forums. It is particularly interesting how closely the curves for the ALL and Student graphs mirror one another. This may indicate that the hub students are also those that followed the instructor and TAs closely, thus giving them isomorphic relationships, or it may indicate that they are more connected than even the instructors and thus came to bind the forums together on their own. This impact is further illustrated by the cluster plots shown in Figure 3. Here the absence of the hub students results in a noticeable thinning of the graph which in turn highlights the frequency of communication that can be attributed to this, comparatively small, group.
The difference between the full plots and those with zero values are also notable as the zero grade students were clearly a major factor in community formation. A direct examination of the user graph showed that many of the zero students were only connected to other zero students or were not connected at all.
This is also highlighted in Figure 3. In both graphs the bulk of the zero score students are clustered in a tight network of communities on the left-hand side. That super-community consists primarily of zero score students communicating with other zeroscore students, a structure we have nick-named the `deathball.' 5.3 Student Performance & Motivation As the color coding in Figure 3 illustrates, the students did cluster by performance. Table 3 shows the average grade and standard deviation for a small selection of the communities in the ALL reply network including zero-grades, hub students, and teaching staff. Several of the communities, particularly the larger ones, do show a blend of good and poor students, with a high standard deviation. However many if not most of the communities are more homogeneous with good and poor students sharing a community with similarly-performing peers.
These clusters have markedly lower standard deviation.
An examination of the grade distribution for each of the clusters showed that the scores within each cluster were non-normal.
Therefore we opted to apply the Kruskal-Wallis (KW) test to
assess the correlation between cluster membership and
perforYes
No
Yes
No
Yes
No
Yes
mance. The KW test is a nonparametric rank-based analogue
to the common Analysis of Variance [
We performed a similar KW analysis for the questions on the
motivation survey and for a binary variable indicating whether
or not the student completed the survey at all. For this analysis
we evaluated the clusters on all of the graphs. We found no
significant relationship between the community structure on
any of the graphs and the survey question results or the survey
completion variable. Thus while the clusters may be driven by
separate factors they are not reflected in the survey content.
6. CONCLUSIONS AND FUTURE WORK
Our goal in this paper was to expand upon our prior community
detection work with the goal of aligning that work with prior
research on peer impacts, notably the work of Fire et al. [
We also sought to examine the impact of hub students and student motivations on our prior results.
To that end we performed a novel community clustering analysis of student performance data and forum communications taken from a single well-structured MOOC. As part of this analysis we described a novel heuristic method for selecting natural numbers of clusters, and replicated the results of prior studies of both immediate neighbors and second-order assortativity.
Consistent with prior work, we found that students' grades were significantly correlated with their most closely associated peers in the new networks. We also found that this correlation extended out to their second-order neighborhood. This is consistent with our prior work showing that students form stable user communities that are homogeneous by performance. We found that those results were stable even if instructors, hub players, students with 0 scores, and students who did not fill out the survey were removed from consideration. This suggests that either the students are forming communities that are homogeneous or that the effect of those individual and network features on the communities and on performance is minimal.
Users
We also found that community membership was not a significant predictor of whether students would complete the motivation survey or of students' motivations. We were surprised by the fact that even when we focused solely on individuals who had completed the survey, the students did not connect by stated goals. This suggests to us that the students are more likely coalescing around the pragmatic needs of the class or conceptual challenges rather than on the winding paths that brought them there. One limitation of this work is that by relying on the forum data we were focused solely on the comparatively small proportion of enrolled students (6%) who actively participated in the forums. This group is, by definition a smaller set of more actively-involved participants.
In addition to addressing our primary questions this study also raised a number of open issues for further exploration. Firstly, this work focused solely on the final course structure, grades, and motivations. We have not yet addressed whether these communities are stable over time or how they might change as students drop in our out. Secondly, while we ruled out motivations as a basis for the community this work we were not able to identify what mechanisms do support the communities. And finally this study raises the question of generality and whether or not these results can be applied to MOOCs offered on different topics or whether the results apply to traditional and blended courses.
In subsequent studies we plan to examine both the evolution of the networks over time as well as additional demographic data with the goal of assessing both the stability of these networks and the role of other potential latent factors. We will also examine other potential clustering mechanisms that control for other user features such as frequency of involvement and thread structure. We also plan to examine other similar datasets to determine if these features transition across classes and class types. We believe that these results may change somewhat once students can coordinate face to face far more easily than online. 7. ACKNOWLEDGMENTS This work was supported by NSF grant #1418269: \Modeling Social Interaction & Performance in STEM Learning" Yoav Bergner, Ryan Baker, Danielle S. McNamara, & Tiffany Barnes Co-PIs.
Using the Hint Factory to Compare Model-Based Tutoring Systems
Collin Lynch North Carolina State
University 890 Oval Drive
Raleigh, NC 27695 cflynch@ncsu.edu
Min Chi North Carolina State
University 890 Oval Drive Raleigh, NC 27695 mchi@ncsu.edu
Thomas W. Price North Carolina State
University 890 Oval Drive
Raleigh, NC 27695 twprice@ncsu.edu
Tiffany Barnes North Carolina State
University 890 Oval Drive
Raleigh, NC 27695 tmbarnes@ncsu.edu ABSTRACT Model-based tutoring systems are driven by an abstract domain model and solver that is used for solution validation and student guidance. Such models are robust but costly to produce and are not always adaptive to speci c students' needs. Data-driven methods such as the Hint Factory are comparatively cheaper and can be used to generate individualized hints without a complete domain model. In this paper we explore the application of data-driven hint analysis of the type used in the Hint Factory to existing modelbased systems. We present an analysis of two probability tutors Andes and Pyrenees. The former allows for exible problem-solving while the latter sca olds students' solution path. We argue that the state-space analysis can be used to better understand students' problem-solving strategies and can be used to highlight the impact of di erent design decisions. We also demonstrate the potential for data-driven hint generation across systems. 1. INTRODUCTION Developers of model-based tutoring systems draw on domain experts to develop ideal models for student guidance.
Studies of such systems have traditionally been focused on their overall impact on students' performance and not on the students' user-system interaction. The Hint Factory, by contrast, takes a data-driven approach to extract advice based upon students' problem solving paths. In this paper we will apply the Hint Factory analytically to evaluate the impact of user interface changes and solution constraints between two closely-related tutoring systems for probability.
Model-based tutoring systems are based upon classical
expert systems, which represent relevant domain knowledge
via static rule bases or sets of constraints [
Data-driven hint generation methods such as those used in
Hint Factory [
Model-based systems such as Andes [
Data-driven methods for generating feedback, by contrast,
require much lower initial investment and can readily adapt
to individual student behaviors. Systems such as the Hint
Factory are designed to extract solutions from prior student
data, to evaluate the quality of those solutions, and to
compile solution-speci c hints [
We believe that both of these approaches have inherent advantages and are not necessarily mutually exclusive. Our goal in this paper is to explore what potential data-driven methods have to inform and augment model-based systems.
We argue that data-driven methods can be used to: (1) evaluate the di erences between closely-related systems; (2) assess the impact of speci c design decisions made in those systems for user behaviors; and (3) evaluate the potential application of data-driven hint generation across systems. To that end we will survey relevant prior work on model-based and data-driven tutoring. We will describe two closelyrelated tutoring systems and data collected from them. We will then present a series of analyses using state-based methods and discuss the conclusions that we drew from them.
BACKGROUND
2.1 Model-Based Tutoring
Model-based tutoring systems take a classical expert-systems
approach to tutoring. They are typically based upon a
strong domain model composed of declarative rules and facts
representing domain principles and problem-solving actions
coupled with an automatic problem solver. This knowledge
base is used to structure domain knowledge, de ne
individual problems, evaluate candidate solutions, and to provide
student guidance. Novices typically interact with the system
through problem solving with the system providing solution
validation, automatic feedback, pedagogical guidance, and
additional problem-solving tasks. The Sherlock 2 system, for
example, was designed to teach avionics technicians about
appropriate diagnostic procedures [
Andes [
The systems are designed to function as homework-helpers, with students logging into the system and being assigned or selecting one of a set of prede ned problems. Each problem is associated with a pre-compiled solution graph that de nes the set of possible solutions and problem-solving steps. The system uses a principle-driven automated problem solver to compile these graphs and to identify the complete solution paths. The solver is designed to implement the Target Variable Strategy (TVS), a backward-chaining problem solving strategy that proceeds from a goal variable (in this case the answer to the problem) via principle applications to the given information. The TVS was designed with the help of domain experts and guides solvers to de ne basic solution information (e.g. given variables) and then to proceed from the goal variable and use principles to de ne it in terms of the given variables.
Students working with Andes use a multi-modal user interface to write equations, de ne variables and engage in other atomic problem-solving steps. A screenshot of the Andes UI can be seen in Figure 1. Andes allows students to solve problems exibly, completing steps in any order so long as they are valid [20]. A step is considered to be valid if it matches one or more entries in the saved solution paths and all necessary prerequisites have been completed. Invalid steps are marked in red, but no other immediate feedback is given.
Andes does not force students to delete or x incorrect entries as they do not a ect the solution process. In addition to validating entries, the Andes system also uses the precompiled solution graphs to provide procedural guidance (next-step-help). When students request help, the system will map their work to the saved solution paths. It will then select the most complete solution and prompt them to work on the next available step.
One of the original goals of the Andes system was to develop a tutor that operated as an \intelligent worksheet." The system was designed to give students the freedom to solve problems in any order and to apply their preferred solution strategy. The system extends this freedom by allowing invalid steps in an otherwise valid solution and by allowing students to make additional correct steps that do not advance the solution state or are drawn from multiple solution paths. This was motivated in part by a desire to make the system work in many di erent educational contexts where instructors have their own preferred methods [20]. The designers of Andes also consciously chose only to provide advice upon demand when the students would be most willing to accept it. For the students however, particularly those with poor problem-solving skills, this passive guidance and comparative freedom can be problematic as it does not force them to adhere to a strategy.
This problem motivated the development of Pyrenees.
Pyrenees, like Andes acts as a homework helper and supports
students with on-demand procedural and remediation help. It
uses an isomorphic domain model with the same principles,
basic steps, problems, and solution paths. Unlike Andes,
however, Pyrenees forces students to applying the
targetvariable-strategy during problem solving. It also requires
them to repair incorrect entries immediately before moving
on. Students are guided through the solution process with
a menu-driven interface, shown in Figure 2. At each step,
the system asks students what they want to work on next
and permits them to make any valid step that is consistent
with the TVS. Chi and VanLehn [
This e ect was observed both in the original domain where it was taught (in their case probability) and it transferred to a new domain (physics), where students used Andes alone. 2.2 Data-Extraction and
Data-Driven Tutoring.
One of the longstanding goals of educational data-miners is to support the development of data-driven tutoring systems.
Such systems use past student data to structure pedagogical and domain knowledge, administer conceptual and pedagogical advice, or evaluate student performance and needs. A number of attempts have been made to address these goals.
One of the most successful data-driven systems is the Hint
Factory [
These hints are incorporated into existing tutoring systems
in the form of a lookup table that provides state-speci c
advice. When a user asks for help the tutor will match their
current state to an index state in the lookup table and will
prompt them to take the action that will lead them to the
highest value neighboring state. If their current state is not
found then the tutor will look for a known prior state or
will give up. The Hint Factory has been applied successfully
in a number of domains including logic proofs [
The primary goal of the Hint Factory is to leverage prior
data to provide optimal state-speci c advice. By calculating
advice on a per-state basis, the system is able to adapt to
students' speci c needs by taking into account both their
current state and the paths that they can take to reach the
goal. As a consequence the authors of the Hint Factory
argue that this advice is more likely to be in the students'
Zone of Proximal Development and thus more responsive to
their needs than a less-sensitive algorithm.
3. METHODS
In order to investigate the application of data-driven
methods to model-based tutoring systems, we collected data from
two studies conducted with Andes and Pyrenees in the
domain of probability. We then transformed these datasets
into interaction networks, consisting of states linked with
actions. We used this representation to perform a variety of
quantitative and qualitative analyses with the goal of
evaluating the di erences between the two systems and the
impact of the speci c design decisions that were made in each.
3.1 The Andes and Pyrenees Datasets
The Andes dataset was drawn from an experiment
conducted at the University of Pittsburgh [
Forty-four students completed the entire study. However for the purposes of the present analysis, we drew on all 66 students who completed at least one problem in AndesProbability. This is consistent with prior uses of the Hint Factory which draw from all students including those who did not complete the problem. The Pyrenees-Probability logs from this study were not used due to problems with the data format that prevented us from completing our analysis.
From this dataset we drew 394 problem attempts covering 11 problems. The average number of steps required to solve the problems was 17.6. For each problem we analyzed between 25 and 72 problem attempts, with an average of 35.8 attempts per problem. Some attempts were from the same student, with at most two successful attempts per student.
Over all problems, 81.7% of the attempts were successful, with the remainder being incomplete attempts.
The Pyrenees dataset was drawn from a study of 137 students conducted in the 200-level Discrete Mathematics course in the Department of Computer Science at North Carolina State University. This study used the same probability textbook and pre-training materials as those used in the Andes study. The students used Pyrenees as part of a homework assignment, in which they completed 12 problems using the tutoring system. One of these problems was not represented in the Andes dataset. We therefore excluded it from our analysis, leaving 11 shared problems.
Unlike the Andes students, however, the Pyrenees students
were not always required to solve every problem. In this
study the system was con gured to randomly select some
problems or problem steps to present as worked examples
rather than as steps to be completed. In order to ensure
that the results were equivalent we excluded the
problemlevel worked examples and any attempt with a step-level
worked example from our analysis. As a consequence, each
problem included a di erent subset of these students. For
each problem we analyzed between 83 and 102 problem
attempts, with an average of 90.8 attempts per problem. Some
attempts were from the same student, with at most one
successful attempt per student. Over all problems, 83.4% of
the attempts were successful.
3.2 State and Action Representations
In order to compare the data from both tutors, we
represented each problem as an interaction network, a
representation used originally in the Hint Factory [
A variable is a probabilistic expression, such as P (A [ B), that the student has identi ed as important to solving the problem, for which the probability is known or sought. An equation represents the application of a principle of probability, which relates the values of de ned variables, such as the Complement Theorem, P (A) + P (:A) = 1. Because such equations can be written in many algebraically equivalent ways, we represent each equation as a 2-tuple, consisting of the set of variables included in the equation (e.g. fP (A); P (:A)g) and the principle being applied (e.g. Complement Theorem). Because we only represent valid equations, this representation uniquely identi es any equation for a given problem. Because we used the same state representation for both tutors, we were able to compare states directly across tutors.
Additionally, we opted to ignore incorrect entries. Pyrenees prevents students from applying the principles of probability improperly and forces them to correct any mistakes made immediately therefore any errors in the student logs are immediately removed making the paths uninformative. Andes, by contrast, gives students free reign when writing equations and making other entries. This freedom resulted in syntactic errors and improper rule application errors arising in our dataset. The meaning of these invalid equations is inherently ambiguous and therefore di cult to incorporate into a state de nition. However such errors are immediately agged by the system and may be ignored by the student without consequence as they do not a ect the answer validity therefore they may be safely ignored as well.
An edge, or action, in our network represents the correct application of a rule or a correct variable de nition and leads to a transition from one state to another. For the present dataset and state representation, the possible actions were the de nition or deletion of variables or equations. Each of these actions was possible in both tutors. 4. ANALYSIS In order to develop a broader understanding of our datasets, we rst visualized the interaction network for each problem as a weighted, directed graph. We included attempts from both Andes and Pyrenees in the network, and weighted the edges and verticies by the frequency with which it appeared in the logs. We annotated each state and edge with the weight contributed by each tutor. Two examples of these graphs are given in Figure 3.
Throughout this section, we will use these graphs to address the points we outlined at the end of Section 1. We begin with a case study from one problem and will explore the student problem solving strategies using our graph representation. We will then compare the Andes and Pyrenees Systems with a variety of metrics based on this representation. We will relate our observations back to the design decisions of each system and identify evidence that may support or question these decisions. Finally, we will show how the analysis methods associated with data-driven hint generation can be used to validate some of these ndings. 4.1 Case Study: Problem Ex242 The graphical representation of a problem is very helpful for giving a high-level overview of a problem and performing qualitative analysis. Problem Ex242, shown in Figure 3, presents an interesting scenario for a number of reasons. The problem was the 10th in a series of 12 practice problems, and asked the following:
Events A, B and C are mutually exclusive and exhaustive events with p(A) = 0:2 and p(B) = 0:3. For an event D, we know p(DjA) = 0:04, p(DjB) = 0:03, and p(CjD) = 0:3. Determine p(BjD). \zones" of knowledge. For example, a partial graph with only concepts that belongs to a speci c topic, or concepts that are prerequisites of a speci c concept. Another interesting idea relates to recommendation of content: guide the student to questions that will connect the isolated parts of the knowledge graph or minimize the average path length of the graph. Along the same lines, the analysis of the graph shortest paths and overall connectivity can help in designing assessment items that better connect distant concepts.
Graph-based Modelling of Students’ Interaction Data from
Exploratory Learning Environments Alexandra Poulovassilis
London Knowledge Lab Birkbeck, Univ. of London ap@dcs.bbk.ac.uk
Sergio Gutierrez-Santos
London Knowledge Lab Birkbeck, Univ. of London sergut@dcs.bbk.ac.uk
Manolis Mavrikis
London Knowledge Lab UCL Institute of Education m.mavrikis@lkl.ac.uk ABSTRACT Students' interaction data from learning environments has an inherent temporal dimension, with successive events being related through the \next event" relationship. Exploratory learning environments (ELEs), in particular, can generate very large volumes of such data, making their interpretation a challenging task. Using two mathematical microworlds as exemplars, we illustrate how modelling students' eventbased interaction data as a graph can open up new querying and analysis opportunities. We demonstrate the possibilities that graph-based modelling can provide for querying and analysing the data, enabling investigation of student-system interactions and leading to the improvement of future versions of the ELEs under investigation.
Keywords
Exploratory Learning Environments, Interaction Data, Graph
Modelling
1. INTRODUCTION
Much recent research has focussed on Exploratory
Learning Environments (ELEs) which encourage students'
openended interaction within a knowledge domain, coupled with
intelligent techniques that aim to provide pedagogical
support to ensure students' productive interaction [
In this paper, we consider how modelling students'
eventbased interaction data as a graph makes possible
graphbased queries and analyses that can provide insights into
the ways that students are using the a ordances of the
system and the e ects of system interventions on students'
behaviour. Our case studies are two intelligent ELEs: the
MiGen system, that aims to foster 11-14 year old students'
learning of algebraic generalisation [
Both systems include intelligent components that provide
di erent levels of feedback to students, ranging from
unsolicited prompts and nudges, to low-interruption feedback
that students can choose to view if they wish. The aim
of this feedback is to balance students' freedom to explore
while at the same time providing su cient support to
ensure that learning is being achieved [
Teacher Assistance tools can subscribe to receive real-time
information relating to occurrences of indicators for each
student, and can present aspects of this information
visually to the teacher [
In this paper we explore how graph-based representation of
event-based interaction data arising from ELEs such as
MiGen and FractionsLab can aid in the querying and analysis
of such data, with the aim of exploring both the behaviours
of the students in undertaking the exploratory learning tasks
set and the e ectiveness of the intelligent support being
provided by the system to the students. Data relating to
learning environments has often been modelled as a graph
in previous work, for example in [
Previous work that is close to ours is the work on
interaction networks and hint generation [
ne-grained event-based interaction data arising from ELEs.
In our graphs, nodes are used to represent indicator occurrences (i.e. events, not problem states) and edges between such nodes represent the \next event" relationship. Also, rather than using the information derived from querying and analysing this data to automatically generate hints, our focus is on investigating how students are using the system and the e ects of the system's interventions in order to understand how students interact with the ELEs and improve their future versions. 2. GRAPH-BASED MODELLING Figure 1 illustrates our Graph Data Model for ELE interaction data. We see two classes of nodes: Event | representing indicator occurrences; and EventType | representing di erent indicator types. The instances of the Event class are occurrences of indicators that are detected or generated by the system as each student undertakes a task. We see that instances of Event have several attributes: dateTime: the date and time of the indicator occurrence; userID: the student it relates to; sessionID: the class session that the student was participating in at the time; taskID: the taskID that the student was working on; and constrID: the construction that the student was working on1. 1The model in Fig. 1 focusses on the interaction data. The full data relating to ELEs such as eXpresser and FractionsLab would also include classes relating to users, tasks, sessions and constructions; and attributes describing instances of these classes, such as a user's name and year-group, a task's name and description, a construction's content and description, and a session's description and duration.
Event dateTime taskID constrID userID sessionID occurrenceOf next
EventType eventID eventStatus eventCat There is a relationship `next' linking an instance of Event to the next Event that occurs for the same user, task and session. There is a relationship `occurrenceOf' linking each instance of Event to an instance of the EventType class.
The instances of the EventType class include: startTask,
endTask, numberCreated, numberUnlocked,
unlockedNumberChanged, buildingBlockMade, correctModelRuleCreated,
incorrectModelRuleCreated, interventionGenerated,
interventionShown, in the case of eXpresser (see [
We see that instances of the EventType class have several attributes, including: eventID: a unique numerical identi er for each type of indicator; eventStatus: this may be -1, 0 or 1, respectively stating that an occurrence of this type of indicator shows that the student is making negative, neutral or positive progress towards achieving the task goals; an additional status 2 is used for indicators relating to system interventions; eventCat: the category into which this indicator type falls; for example, startTask and endTask are taskrelated indicators; interventionGenerated and interventionShown are system-related ones; numberCreated, numberUnlocked, unlockedNumberChanged are numberrelated; and fractionCreated, fractionChanged, fractionReleased are fraction-related.
Figure 2 shows a fragment of MiGen interaction data conforming to this graph data model. Speci cally, it relates to the interactions of user 5 as he/she is working on task 2 during session 9. The user makes three constructions during this task (with constrIDs 1, 2 and 3). The start and end of the task are delimited by an occurrence of the startTask and endTask indicator type, respectively | events 23041 and 33154. We see that the two events following 23041 relate to an intervention being generated and being shown to the student (this is likely to be because the student was inactive for over a minute after starting the task); following which, the student creates a number | event 24115.
There are additional attributes relating to events, not shown here for simplicity, capturing values relating to the student's next next 23041 dateTime: 20150331091524 taskID:2 constrID:1 userID:5 sessionID:9 23921 dateTime: 20150331091637 taskID:2 constrID:1 userID:5 sessionID:9 23923 dateTime: 20150331091638 taskID:2 constrID:1 userID:5 sessionID:9 startTask eventID:0 eventStatus:0 eventCat:taskEv interventionGenerated eventID:6001 eventStatus:2 eventCat:systemEv occurrenceOf next interventionShown eventID:6002 eventStatus:2 eventCat:systemEv numberCreated eventID:1006 eventStatus:1 eventCat:numberEv occurrenceOf next ... next next 344712 dateTime: 20150215091741 taskID:56 constrID:4 userID:5 sessionID:1 344758 dateTime: 20150215091828 taskID:56 constrID:4 userID:5 sessionID:1 344759 dateTime: 20150215091828 taskID:56 constrID:4 userID:5 sessionID:1 occurrenceOf fractionChanged eventID:1002 eventStatus:1 eventCat:sfractionEv occurrenceOf constructions and information relating to the system's interventions. For example, for event 24115, the value of the number created, say 5; for event 23921, the feedback strategy used by the system to generate this intervention, say strategy 8; and for event 23923, the content of the message displayed to the user, say \How many green tiles do you need to make your pattern?" and whether this is a high-level interruption by the system or a low-level interruption that the student can choose to view or not. Such information can be captured through additional edges outgoing from an event instance to a literal-valued node: 24115 valu!e 5, 23921 strateg!y 8, 23932 messag!e \How many green tiles do you need to make your pattern?", 23932 lev!el \high". Since graph data models are semi-structured (and graph data therefore does not need to strictly conform to a single schema), this kind of heterogeneity in the data is readily accommodated.
Figure 3 similarly shows a fragment of FractionsLab interaction data, relating to the interactions of user 5 working on task 56 during session 1. The user makes one construction during this task. We see events relating to the student changing and `releasing' a fraction. Following which the system displays a message (in this case, it was a highinterruption message of encouragement \Great! Well Done").
We see from Figures 2 and 3 that the sub-graph induced by edges labelled `next' consists of a set of paths, one path for each task undertaken by a speci c user in a speci c session.
The entire graph is a DAG (directed acyclic graph): there are no cycles induced by the edges labelled `next' since each links an earlier indicator occurrence to a later one; while the instances of EventType and other literal-valued nodes can have only incoming edges. The entire graph is also a bipartite graph, with the two parts comprising (i) the instances of Event, and (ii) the instances of EventType and the literal-valued nodes.
As a nal observation, we note that Figures 1 { 3 adopt
a \property graph" notation (e.g. as used in the Neo4J
graph database, neo4j.com) in which nodes may have
attributes. In a \classical" graph data model, each attribute
of a node would be represented by an edge and its value by
a literal-valued node. So, for example, the information that
the taskID of event 23041 is 2 would be represented by an
edge 23041 taskI!D 2. The query examples in the next section
assume this \classical" graph representation.
3. GRAPH QUERIES AND ANALYSES
Because the sub-graph induced by edges labelled `next'
consists of a set of paths, the data readily lends itself to
exploration using conjunctive regular path (CRP) queries [
(X1; R1; Y1); : : : ; (Xn; Rn; Yn) where each Xi and Yi is a variable or a constant, each Zi is a variable that appears also in the right hand side of Q, and each Ri is a regular expression over the set of edge labels.
In this context, a regular expression, R, has the following syntax:
R := j a j j (R1:R2) j (R1jR2) j R j R+ where denotes the empty string, a denotes an edge label, denotes the disjunction of all edge labels, and the operators have their usual meaning. The answer to a CRP query on a graph G is obtained by nding for each 1 i n a binary relation ri over the scheme (Xi; Yi), where there is a tuple (x; y) in ri if and only if there is a path from x to y in G such that: x = Xi if Xi is a constant; y = Yi if Yi is a constant; and the concatenation of the edge labels in the path satis es the regular expression Ri. The answer is then given by forming the natural join of the binary relations r1; : : : ; rn and nally projecting on Z1; : : : ; Zm.
To illustrate, the following CRP query returns pairs of events x, y such that x is an intervention message shown to the user by the system and y indicates that the user's next action { in eXpresser { was to create a number (note, variables in queries are distinguished by an initial question mark): (?X,?Y) <- (?X,occurrenceOf,interventionShown), (?X,next,?Y), (?Y,occurrenceOf,numberCreated) The result would contain pairs such as (23923,24115) from Figure 2, demonstrating that there are indeed situations where an intervention message displayed by the MiGen system leads directly to the creation of a number by the student.
The following query returns pairs of events x, y such that that x is an intervention message shown to the user by the system and y is the user's next action; the type of y is also returned, through the variable ?Z: (?X,?Y,?Z) <- (?X,occurrenceOf,interventionShown), (?X,next,?Y), (?Y,occurrenceOf,?Z) The result would contain triples such as (23923,24115,numberCreated) from Figure 2 and (344760,344761,clickButton) from Figure 3, allowing researchers to see what types of events directly follow the display of an intervention message. This would allow the con rmation or contradiction of researchers' expectations regarding the immediate e ect of intervention messages on students' behaviours.
Focussing for the rest of this section on the data in Figure 2, the following query returns pairs of events x, y such that x is any type of event and y indicates that the user's next action was to unlock a number; the type of x is also returned, through the variable ?Z: (?X,?Y,?Z) <- (?X,occurrenceOf,?Z), (?X,next,?Y), (?Y,occurrenceOf,numberUnlocked) The result would allow researchers to see what types of events immediately precede the unlocking of a number (i.e. the creation of a variable). This would allow con rmation of researchers' expectations about the design of the MiGen system's intelligent support in guiding students towards generalising their models by changing a xed number to an `unlocked' one.
The following query returns pairs of events x, y such that that x is an intervention generated by the system and y is any subsequent event linked to x through a path comprising one or more `next' edges; the type of y is also returned, through the variable ?Z: (?X,?Y,?Z) <- (?X,occurrenceOf,interventionGenerated), (?X,constrID,?C), (?X,next+,?Y), (?Y,constrlID,?C), (?Y,occurrenceOf,?Z) The result would contain triples such as (23921, 23923, interventionShown), (23921, 24115, numberCreated), (23921, 24136, numberUnlocked), (23921, 24189, unlockedNumberChanged), relating to construction 1 made by user 5 during session 9 for task 2 (two more events | 24136 and 24189 | relating to construction 1 have been assumed here, in addition to 23923 amd 24115 shown in Figure 2, for illustrative purposes). The results would not contain (23921,33154,endTask), since event 33154 relates to construction 3.
To show more clearly the answers to the previous query in
the form of possible event paths, we can use extended regular
path (ERP) queries [
The use of the regular expressions next and next+ in the
previous queries matches precisely one edge labelled `next',
or any number of such edges (greater than or equal to 1),
respectively. However, for ner control and ranking of query
answers, it is possible to use approximate answering of CRP
and ERP queries (see [
For example, using the techniques described in [
We can modify the query to retain only pairs x, y that relate to the same construction: (?X,?P,?Y,?Z) <(?X,occurrenceOf,interventionGenerated), (?X,constrID,?C), APPROX(?X,next:?P,?Y), (?Y,constrID,?C), (?Y,occurrenceOf,?Z) would return rst exact answers, such as (23921, [next], 23923, interventionShown). The regular expression next in the conjunct APPROX(?X,next:?P,?Y) would then be automatically approximated to next.next, leading to answers such as (23921, [next, 23923, next], 24115, numberCreated) at an edit distance of 1 from the original query. Following this, the regular expression next.next would be automatically approximated to next.next.next, leading to answers such as (23921, [next, 23923, next, 24115, next], 24136, numberUnlocked) at distance 2. This incremental return of paths of increasing length can continue for as long as the user wishes, and allows researchers to examine increasingly longer-term effects of intervention messages on students' behaviours. It would also be possible for users to specify from the outset a minimum and maximum edit distance to be used in approximating and evaluating the query, for example to request paths encompassing between 2 and 4 edges labelled `next'.
Queries based on evaluating regular expressions over a
graphbased representation of interaction data, such as those above,
can aid in the exploration of students' behaviours as they are
undertaking tasks using ELEs and the e ectiveness of the
intelligent support being provided by the ELE. The query
processing techniques employed are based on incremental
query evaluation algorithms which run in polynomial time
with respect to the size of the database graph and the size
of the query and which return answers in order of increasing
edit distance [
The rst of these has rather `linear' data, similar to the interaction data discussed here, while the second has `bushier' connectivity. Query performance is generally better for the former than the latter, and the paper discusses several possible approaches towards query optimisation.
In addition to evaluating queries over the interaction data,
by representing the data in the form of a graph it is possible
to apply graph structure analyses such as the following:
path nding and clustering: this would be useful for
determining patterns of interest across a whole dataset,
or focussing on particular students, tasks or sessions
c.f. [
1002 3006
1010 3002 1015 1014 1011 1003 1004 1005 1006 1007 1008 1009 applied across a whole dataset, or focussing on particular students, tasks or sessions; nodes that have a high probability of being visited on a randomly chosen shortest path between two randomly chosen nodes have high betweenness centrality; determining this measure for pairs of event type nodes (ignoring the directionality of the `occurrenceOf' edges) would identify event types that play key mediating roles between other event types.
We have already undertaken some ad hoc analyses of interaction data arising from classroom sessions using ELEs.
For example, Figure 4 shows the normalised incoming transitions for a 1-hour classroom session involving 22 students using MiGen (in the diagram, s denotes the `startTask' and e the `endTask' event types). Event types with an adjacent circle show transitions where this type of event occurs repeatedly in succession. The thickness of each arrow or circle indicates the value of the transition probability: the thicker the line, the higher the probability. Red (light grey) is used for probabilities < 0:2 and black for probabilities
0:2. We can observe a black arrow 3007 ! 1005,
indicating transitions from events of type 3007 (detection by the
system that the student has made an implausible building
block for this task) to events of type 1005 (modi cation of a
rule by the student). Such an observation raises a
hypothesis for more detailed analysis or further student
observation, namely: \does the construction of an incorrect building
block lead students to self-correct their rules?". Developing
a better understanding of such complex interaction can lead
to improvement of the system. For this particular example,
we designed a new prompt that suggests to students to rst
consider the building block against the given task before
proceeding unnecessarily in correcting their rules. More
examples of such ad hoc analyses are given in [
We have explored the possibilities that evaluating regular path queries over this graph-based representation might provide for exploring the behaviours of students as they are working in the ELE and the e ectiveness of the intelligent support that it provides to them. We have also identi ed additional graph algorithms that may yield further insights about learners, tasks and signi cant indicators.
Planned worked includes transformation and uploading of
the interaction data sets gathered during trials and full
classroom sessions of the two systems into an industrial-strength
graph database such as Neo4J, following the graph model
presented in Section 2; followed by the design,
implementation and evaluation of meaningful queries, analyses and
visualisations over the graph data, building on the work
presented in Section 3. Equipped with an appropriate user
interface, educational researchers, designers or even
teachers with less technical expertise could in this way explore
the data from their perspective. This has the potential to
lead to an improved understanding of interaction in this
context and to feed back to the design of the ELEs. We
see this approach very much in the spirit of \polyglot
persistence" (i.e. using di erent data storage methods to
address di erent data manipulation problems), and hence
being used in conjunction with other EDM resources such as
DataShop [
Acknowledgments This work has been funded by the ESRC/EPSRC MiGen project, the EU FP7 projects iTalk2Learn (#318051) and M C Squared (#610467). We thank all the members of these projects for their help and insights.
Lorenzo Vigentini Learning & Teaching Unit
UNSW Australia, Lev 4 Mathews, Kensington 2065
+61 (2) 9385 6226 l.vigentini@unsw.edu.au ABSTRACT In this paper we present an analysis (in progress) of a dataset containing forum exchanges from three different MOOCs. The forum data is enhanced because together with the exchanges and the full text, we have a description of the design and pedagogical function of forums in these courses and a certain level of detail about the users, which includes achievement, completion, and in some instances more details such as: education; employment; age; and prior MOOC exposure.
Although a direct comparison between the datasets is not possible because the nature of the participants and the courses are different, what we hope to identify using graph-based techniques is a characterization of the patterns in the nature and development of communication between students and the impact of the ‘teacher presence’ in the forums. With the awareness of the differences, we hope to demonstrate that student engagement can be directed ‘bydesign’ in MOOCs: teacher presence should therefore be planned carefully in the design of large-scale courses.
Keywords
MOOCs, Discussion forums, graph-based EDM, pedagogy.
1. INTRODUCTION
In the past couple of years MOOCs (Massive Open Online
Courses) have become the center of much media hype as
disruptive and transformational [
In particular, P2P was designed emulating a traditional university course in a sequential manner. All content was released on a week-by-week basis dictating the pace of instruction. LTTO and INTSE, instead were designed to provide a certain level of flexibility for the students to elect their learning paths. All content was readily available at the start, however for LTTO, the delivery followed a week-on-week delivery focusing on the interaction with students and a selective attention to particular weekly topics (i.e. weekly feedback videos driven by the discussion forums as well as weekly announcements). Although announcements were used also in INTSE, the lack of weekly activities in the forums did not impose a strong pacing. In INTSE, the forums had only a tangential support value and were used mainly to respond to students’ queries and to clarify specific topics emerging from the quizzes. Table 1 provides an overview of the different courses.
This also shows that the forum activity in the various courses is a
very small portion of all actions emerging from the logs of activity
which has been reported in the literature [
The clickstream was further classified into: browsing; profile lookups; social interaction (looking at contributions); search; tagging; and threads. From the classification it became evident the clickstream did not record all events, such as when a post or comment was made, or when votes were applied. For these, specific database tables were used. In order to manage different data sets and sources, a standardized schema was built, allowing disparate sources to feed into, but exposing a common interface to conduct analysis over forum activities. This is shown in Figure 1. 3.2 An overview of forums activity There are very interesting trends which require more detailed examination (bottom of table 1). As expected, in LTTO the forum activity is larger than in the other courses and this is probably due to the fact that students were asked to submit post in forums following the learning activities. The proportion of active students in forum is 4x in magnitude compared to the other courses. Yet, if we look at the average amount of posts or comments, the patterns are not straightforward to interpret, as the level of engagement is similar across the courses with 3 to 5 posts per student and 1 to 3 comments (i.e. replies to existing posts), but with P2P showing a higher level of engagement than the other courses. One possible explanation is the different target group of the different courses with INTSE including a majority of professional engineers with postgraduate qualifications, P2P focusing on high school student and teachers, and LTTO targeting a broad base of teachers across different educational levels.
Target group Course length Forums Design mode Delivery mode Use of forums N in forum Tot posts Tot comments Registrants Active students1
INTSE Engineers 9 weeks 60%
LTTO Teachers at all levels 8 weeks 63%
P2P High school and teachers 8 weeks 47% Completing2 The type of activity is summarised in Figure 2. In the chart, the five categories refer to the following: View corresponds to listing forums, threads and viewing posts; Post is the writing of a post or start of a new thread; Comment is a reply to an existing post; Social refers to all actions engaging directly with other’s status (up-vote, down-vote and looking at profiles/reputation); Engage refers to the additional interaction with forums content (searching, tagging, ‘watching’ or subscribing to posts or threads).
The viewing behaviour is the most prominent for both the student and instructor groups and the figures are pretty much similar across the board. A two-way ANOVA (2x5, role by activity) on the percentage of distributions, shows that there is no significant difference between students and instructors, but there is an obvious difference between views and the other types of behaviour (F(4,29) = 1656.3, p < .01).
If we consider the engagement over the timeline and compare the type of activities carried out by students and instructors, Figure 3 (end of the paper) shows the patterns for the three courses. The most striking pattern is that there doesn’t seem to be an obvious one. For what concerns posts and views in all the three courses there is a sense of synchronicity between the two groups, however from this chart it is not possible to understand in more detail what are the connections between what students and teachers do.
Instructors’ comments are slightly offset, possibly as a reaction to
students’ posts. An interesting aspect is the amount of ‘social’
engagement in the P2P course that merits further analysis.
4. DIRECTIONS AND OPEN QUESTIONS
From this coarse analysis it is apparent that there seem to be
minimal behavioural differences in the way students and
instructors interact in the different courses, however more analysis
is required to tackle questions about the individual differences in
students’ and instructors’ patterns of interaction and their
interrelations. Furthermore little can be said about how the nature
of interactions drives the development of communication and
engagement. However a number of questions like the following
remain open and unanswered: how do discussions develop over
time? How teacher presence affects the development of
discussions? Is the number of forums affecting how students
engage with them (i.e. causing disorientation)?
4.1 The DM and graph-based approaches
A possible way to answer the questions about the types/patterns of
behaviours, the structure and development of networks and the
growth of groups/communities over time might be using data
mining and graph-based approaches. For example, [
Indicator Messages Threads Words Sentences Reads Time
Type Quantitative Quantitative Quantitative Quantitative Quantitative
Quantitative AvgScoreMsg
Qualitative Centrality Prestige
Social Social
Description Number of messages written by the student.
Number of new threads created by the student.
Number of words written by the student.
Number of sentences written by the student.
Number of messages read on the forum by the student.
Total time, in minutes, spent on forum by the student.
Average score on the instructor's evaluation of the student's messages.
Degree centrality of the student.
Degree prestige of the student.
An alternative method that can be explored is graph-based
approaches. For example, Bhattacharya et al. [
Kobayashi et al. [
Furthermore, Brown et al [22] have already shown the value of exploring the communities in discussion forums in MOOCs particularly for what concerns the homogeneity of performance but dissimilarity of motivations characterizing student hubs. 4.2 Discussion points The examples above provide evidence of the potential for using graph-based methods to obtain better insights into the process and content analysis for our dataset and to extend its applicability to MOOCs, however there are a number of contentious points to raise which will provide opportunities for discussion.
Firstly the number of students who are actively involved in discussion is a very small proportion of the active participants.
This means that the subset may not be representative at all. One could argue that these students are already engaged or desperately need help. Previous literature [21, 22, 23] focused on the ability to predict performance and on the peer effect which can emerge from the analysis of the graphs/social networks.
Secondly, one could question the value of the communities in xMOOCs: especially when courses are designed with an instructivits approach leading to mastery, by definition this is an individualistic perspective focused on the testing of one’s own skills/learning. Of course in cMOOCs -connectivists by designthe importance of the development of social support is essential.
This seems to be supported by Brown et al [22]: they were not able to uncover a direct relation between stated goals and motivations with the participation in forums, and attributed this to pragmatic needs. However, as the authors suggested earlier, the instructors might play a fundamental role in shaping the communities based on the value attributed to forums in their plans/design and the level of engagement/interaction. Considering the split between cMOOCs and xMOOCs again, interesting work might come out of the experiment conducted by Rose’ and colleagues in the DALMOOC in which automated agents were deployed to support students’ conversations. In Coursera the deployment of ‘community mentors’ will be an interesting space to explore, given that the importance of design seems to be removed from instructors in the ‘on-demand’ model.
Lastly, more research is needed in the time-based dimension of
development of forums in MOOCs. Questions like how students
bond and create stable relations, how they become authoritative
and what motivates them to contribute over time are all open
questions which the analysis of graphs over time might be able to
address.
5. REFERENCES
[
Are Transforming the Face of Higher Education. Retrieved
April 12, 2015 from
http://www.huffingtonpost.co.uk/dirkjan-van-den-berg/why-moocs-aretransforming_b_4116819.html
[
Like Courses: Two Successful and Distinct Course Formats for Massive Open Online Courses. European Journal of
Open, Distance and E-Learning (January 2012).
[
Game
Drew Hicks North Carolina State
University 911 Oval Drive
Raleigh, NC 27606 aghicks3@ncsu.edu
Yihuan Dong North Carolina State
University 911 Oval Drive
Raleigh, NC 27606 ydong2@ncsu.edu
Rui Zhi North Carolina State
University 911 Oval Drive Raleigh, NC 27606 rzhi@ncsu.edu Veronica Cateté North Carolina State
University 911 Oval Drive
Raleigh, NC 27606 vmcatete@ncsu.edu
Tiffany Barnes North Carolina State
University 911 Oval Drive
Raleigh, NC 27606 tmbarnes@ncsu.edu ABSTRACT In the eld of Intelligent Tutoring Systems, data-driven methods for providing hints and feedback are becoming increasingly popular. One such method, Hint Factory, builds an interaction network out of observed player traces. This data structure is used to select the most appropriate next step from any previously observed state, which can then be used to provide guidance to future players. However, this method has previously been employed in systems in which each action a player may take requires roughly similar e ort; that is, the \step cost" is constant no matter what action is taken.
We hope to apply similar methods to an interaction network built from player traces in our game, BOTS; However, each edge can represent a varied amount of e ort on the part of the student. Therefore, a di erent hint selection policy may be needed. In this paper, we discuss the problems with our current hint policy, assuming all edges are the same cost.
Then, we discuss potential alternative hint selection policies we have considered.
Keywords Hint Generation, Serious Games, Data Mining 1. INTRODUCTION Data-driven methods for providing hints and feedback are becoming increasingly popular, and are especially useful for environments with user- or procedurally-generated content.
One such method, Hint Factory, builds an interaction
network out of observed player traces. An Interaction Network
is a complex network of student-tutor interactions, used to
model student behavior in tutors, and provide insight into
problem-solving strategies and misconceptions. This data
structure can be used to provide hints, by treating the
Interaction Network similarly to a Markov Decision Process and
selecting the most appropriate next step from the requesting
user's current state. This method has successfully been
employed in systems in which each action a player may take is
of similar cost; for example in the Deep Thought logic tutor
each action is an application of a particular axiom. Applying
this method to an environment where actions are of di
erent costs, or outcomes are of varying value will require some
adaptations to be made. In this work, we discuss how we
will apply Hint Factory methods to an interaction network
built from player traces in a puzzle game, BOTS. In BOTS,
each \Action" is the set of changes made to the program
between each run. Therefore, using the current hint
selection policy would result in very high-level hints comprising
a great number of changes to the student's program. Since
this is undesirable, a di erent hint selection policy may be
needed.
2. DATA-DRIVEN HINTS AND FEEDBACK
In the ITS community, several methods have been proposed
for generating hints/feedback from previous observations of
users' solutions or behavior. Rivers et al propose a
datadriven method to generate hints automatically for novice
programmers based on Hint Factory[
Due to the existence of multiple ways to solve a programming problem, the size of the solution space is huge and thus it is impractical to use. A Canonicalizing model is used to reduce the size of the solution space. All states are transformed to canonicalized abstract syntax trees (ASTs). If the canonical form of two di erent states are identical, they can be combined together. After simplifying the solution space, hint generation is implemented. If the current state is incorrect and not in the solution space, the path construction algorithm will nd an optimal goal state in the solution space which is closest to current state. This algorithm uses change vectors to denote the change between current state and goal state. Once a better goal state is found during enumerating all possible changes, it returns the current combination of change vectors. Each change vector can be applied to current state and then form an intermediate state. The intermediate states are measured by desirability score, which represents the value of the state. And then the path construction algorithm generates optimal next states based on the rank of the desirability scores of all the intermediate states. Thus a new path can be formed and added to the solution space, and appropriate hints can be generated.
Jin et al propose linkage graph to generate hints for
programming courses[
rst generate linkage graphs with a set of correct solutions, as the sources for hint generation. They also compose the intermediate steps during program development into a large linkage graph, and assign a reward value to each state and the correct solution. Then, they apply value iteration to create a Markov Decision Process (MDP). When a student requires hint, tutor will generate a linkage graph for the partial program and try to nd the closest match in MDP. If a match is found in MDP, the tutor would generate hint with the next best state based on highest assigned value.
If a match is not found in current MDP, which means the student is taking a di erent approach from existing correct solutions, the tutor will try to modify those correct solutions to t student's program and then provide hints.
Hint Factory[
The action that leads to subsequent state with the highest
value is used to generate a hint sequence. A hint sequence
consists of four types of hints and are ordered from
general hint to detailed hint. Hint provider will then show hint
from top of the sequence to the student. Hint Factory has
been applied in logic tutors which helps students learn logic
proof. The result shows that the hint-generating function
could provide hints over 80% of the time.
3. BOTS
BOTS is a programming puzzle game designed to teach
fundamental ideas of programming and problem-solving to
novice computer users. The goal of the BOTS project is
to investigate how to best use community-authored content
within serious games and educational games. BOTS was
inspired by games like LightBot [
To program the robots, players will use simple graphical pseudo-code, allowing them to move the robot, repeat sets of commands using \for" or \while" loops, and re-use chunks of code using functions. Within each puzzle, players' scores depend on the number of commands used, with lower scores being preferable. In addition, each puzzle limits the maximum number of commands, as well as the number of times each command can be used. For example, in the tutorial levels, a user may only use the \Move Forward" instruction 10 times. Therefore, if a player wants to make the robot walk down a long hallway, it will be more e cient to use a loop to repeat a single \Move Forward" instruction, rather than to simply use several \Move Forward" instructions one after the other. These constraints are meant to encourage players to re-use code and optimize their solutions.
In addition to the guided tutorial mode, BOTS also
contains an extensive \Free Play" mode, with a wide selection
of puzzles created by other players. The game, in line with
the \Flow of Inspiration" principles outlined by Alexander
Repenning [
User-generated content supports replayability and a sense of a community for a serious game. We believe that usercreated puzzles could improve interest, encouraging students to return to the game to solidify their mastery of old skills and potentially helping them pick up new ones. 4. ANALYSIS 4.1 Dataset Data for the BOTS studies has come from a middle school computer science enrichment program called SPARCS. In this program, the students attend class on Saturday for 4 hours where computer science undergraduates teach them about computational thinking and programming. Students attend a total of 7 sessions, each on a di erent topic, ranging from security and encryption to game design. The students all attend the same magnet middle school. The demographics for this club are 74.2% male, 25.8% female, 36.7% African American, and 23.3% Hispanic. The student's grade distribution is 58% 6th grade, 36% 7th grade and 6% 8th grade.
From these sessions, we collected gameplay data for 20
tutorial puzzles as well as 13 user-created puzzles, With this
data, we created an Interaction Network in order to be able
to provide hints and feedback for future students [
Based on these types of states, we classi ed our hints based on the transitions they represented. 4.2.1
Subgoal Transition c e
Error b d f (start/intermediate) ! (intermediate/goal) These transitions occur when a student moves the robot to an intermediate state rather than directly to the goal. Since players run their programs to produce output, we speculate that these may represent subgoals such asmoving a box onto a speci c switch. After accomplishing that task, the user then appends to their program, moving towards a new objective, until they reach a goal state. Hint B in Figure 2 shows a hint generated from such a transition. 4.2.2 Correction Transition (error/mistake) ! (intermediate/goal) This transition occurs when a student makes and then corrects a mistake.
These are especially useful because we can o er hints based on the type of mistake. Hints D and E in Figure 2 show hints built from this type of transition; however, hint E shows a case where a student resolved the mistake in a suboptimal way. 4.2.3 Simple Solution Transition (start) ! (goal) This occurs when a student enters an entire, correct program, and solves the puzzle in one attempt. This makes such transitions not particularly useful for generating hints, other than showing a potential solution state of the puzzle. Hint F in Figure 2 shows this type of transition. 4.2.4 Rethinking Transition (intermediate) ! (intermediate/goal) This transition occurs when rather than appending to the program as in a subgoal transition, the user deletes part or all of their program, then moving towards a new goal. As a result, the rst state is unrelated to the next state the player reaches. O ering this state as a hint would likely not help guide a di erent user.
Hint A in Figure 2 shows an example of this. Finding and
recognizing these is an important direction for future work.
4.2.5 Error Transition
(start/intermediate) ! (mistake/error) This corresponds to
a program which walks the robot out of bounds, into an
object, or other similar errors. While we disregarded these
as hints, this type of transition may still be useful. In such
a case, the last legal output before the error could be a
valuable state. Hint C in Figure 2 is one such case.
4.3 Next Steps
While this approach was able to help us identify
interesting transitions, as well as signi cantly reduce the sparseness
of the Interaction Network by merging states with similar
output, we violate several assumptions of the Hint Factory
technique by using user compilation as an action.
Essentially, the cost of an action can vary widely. In the most
extreme examples, the best next state selected by Hint
Factory will simply be the goal state.
4.4 Current Hint Policy
Our current hint selection policy is the same as the one used
in the logic tutor Deep Thought with a few exceptions [
We combine all student solution paths into a single graph, mapping identical states to one another (comparing either the programs or the output). Then, we calculate a tness value for each node. We assign a large positive value (100) to each goal state, a low value for dead-end states (0) and a step cost for each step taken (1). Setting a non-zero cost on actions biases us towards shorter solutions. We then calculate tness values V (s) for each state s, where R(s) is the initial tness value for the state, is a discount factor, and P (s; s0) is the observed frequency with which users in state s go to state s0 next, via taking the action a. The equation for determining the tness value of a state is as follows:
V (s) := R(s) + max X Pa(s; s0)V (s0) a
(1) s0 However, in our current representation there is only one available action from any state: \run." Di erent players using this action will change their programs in di erent ways between runs, so it is not useful to aggregate across all the possible resulting states. Instead, we want to consider each resulting state on its own. As a result, we use a simpli ed version of the above, essentially considering each possible resulting state s0 as the de nite result of its own action:
V (s) := R(s) + maxP (s; s0)V (s0) s0 Since the action \run" can encompass many changes, selecting the s0 which maximizes the value may not always be the best choice for a hint. The di erence between s and s0 can be quite large, and this is usually the case when an expert user solves the problem in one try, forming an edge directly between the \start" state and \goal" state. These and other \short-circuits" make it di cult to assess which of the child nodes would be best to o er as a hint by simply using the calculated tness value.
Another problem which arises from this state representation is seen in Hints C and E above. These hints show states where a student traveled from a state to a worse state before ultimately solving the problem. Since we limit our search for hintable states to the immediate child states of s in s0, we are unable to escape from such a situation if the path containing the error is the best or only observable path to the goal. 4.5 Proposed Hint Policies One potential modi cation of the hint policy involves analyzing the programs/output on the nodes, using some distance metric (s; s0). This measurement would be used in addition to the state's independent tness value R(s) which takes into account distance from a goal, but is irrespective of the distance from any previous state. For example in the short-circuit example above, using \di erence in number of lines of code" as a distance metric we could take into account how far the \Goal" state is from the \Start" state, and potentially choose a nearer state as a hint. This also helps correct for small error-correction steps in player solutions; if the change between the current state and the target hint state is very small, we may want to consider hinting toward the next step instead, or a di erent solution path altogether.
V (s) := R(s) + max X a s0 (s; s0)P (s; s0)V (s0) One potential downside to this approach is that it requires somewhat more knowledge of the domain to be built into the model. If the distance metric used is inaccurate or awed, there may be cases where we choose a very suboptimal hint. using di erence in lines of code as our distance metric, the change between a state where a player is using no functions and a state where the user writes existing code into a function may be very small. Hints selected in these cases might guide students away from desired outcomes in our game.
Another problem we need to resolve with our current hint policy, as discussed above, is the case where the best or only path to a goal from a given state s has an error as a direct child s0. One method of resolving this could be, instead of o ering s0 as a hint, continuing to ask for nextstep hints from s0 until some s0 is a hintable, non-error state.
This solution requires no additional knowledge of the game domain, however it's possible that the hint produced will be very far from s, or that we may skip over important information about how to resolve the error or misconception that led the student into state s in the rst place.
Other modi cations to the hint selection policy may produce better results than these. We hope to look into as many possible modi cations as we can, seeing which modi cations produce the most suitable hints on our current dataset before settling on an implementation for the live version of the game. 5. ACKNOWLEDGMENTS Thanks to the additional developers who have worked on this project or helped with our outreach activities so far, including Aaron Quidley, Trevor Brennan, Irena Rindos, Vincent Bugica, Victoria Cooper, Dustin Culler, Shaun Pickford, Antoine Campbell, and Javier Olaya. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. 0900860 and Grant No. 1252376.
[
Johnson, and L. Lehmann. Program representation for
automatic hint generation for a data-driven novice
programming tutor. In Intelligent Tutoring Systems,
pages 304{309. Springer, 2012.
[
Generating hints for programming problems using
intermediate output.
[
Making university education more like middle school
computer club: facilitating the ow of inspiration. In
Proceedings of the 14th Western Canadian Conference
on Computing Education, pages 9{16. ACM, 2009.
[
The hint factory: Automatic generation of contextualized help for existing computer aided instruction. In Proceedings of the 9th International Conference on Intelligent Tutoring Systems Young
Researchers Track, pages 71{78, 2008.
[
Semantic Graphs for Mathematics Word Problems based on Mathematics Terminology Rogers Jeffrey Leo John
Center for Computational
Learning Systems Columbia University
New York, NY, USA rl2689@columbia.edu
Thomas S. McTavish
Center for Digital Data, Analytics & Adaptive Learning
Pearson
Austin, TX, USA tom.mctavish@pearson.com
Rebecca J. Passonneau
Center for Computational
Learning Systems Columbia University
New York, NY, USA becky@ccls.columbia.edu ABSTRACT 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. 1. INTRODUCTION Curricula are compiled learning objects, typically presented in sequential order and arranged hierarchically, as in a book's Table of Contents. Ideally, a domain model captures relationships between the learning objects and the knowledge components or skills they exercise. Unfortunately, domain models are not often granular enough for optimal learning experiences. For example, prerequisite relationships may be lacking, or the knowledge components associated with an exercise may be unknown. In such cases, assessments on those learning objects will be insu cient to enable appropriate redirection unless expert (i.e. teacher) intervention is explicitly given. Domain models remain coarse because using experts to enumerate and relate the knowledge components is costly.
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
[
We contrast these two di erent types of random walks and
nd somewhat similar results, which lends con dence to the
analysis. The bipartite graph walks, however, are more
sensitive to di erences in word frequency. Casting measures of
similarity as graphs and performing random walks on them
a ords more nuanced ways of relating objects, which can be
used to build more granular domain models for analysis of
prerequisites, instructional design, and adaptive learning.
2. RELATED WORK
Random walks over graphs have been used extensively to
measure text similarity. Applications include similarity of
web pages [
nd that the global results are very similar, which is good evidence for the general approach, and we nd di erences in detail that suggest further investigation could lead to customizable methods, depending on needs.
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. [
Extracted relations serve as a knowledge base against which to answer questions, and answering a question is treated as
nding a proof. A shallow approach to knowledge extraction
from a fourth grade science curriculum is taken in [
The fraction of damaged widgets for Machine B is YZ or (simpli ed fraction). Write each fraction as a decimal and a percent. Use pencil and paper. Select a small percent that would allow for a small number of damaged widgets. Find the number of widgets by which each machine exceeded the acceptable number of widgets.
Other work that addresses knowledge representation from
text includes ontology learning [
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. 3.2 Math Terminology 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 [
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. 3.4 Cosine Similarity Graph 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 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. 3.5 Bipartite exercise and word graph 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. minimum maximum mean median std. dev.
rwcos 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. 4. RESULTS 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. 4.1 Exercise-to-Exercise Similarity 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. 4.2 Comparison of the Graph Walks 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 10 4 10 3 max df 0.42 0.13 0.11 0.11 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. 5. CONCLUSION 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.