Active Learning of Strict Partial Orders: A Case Study on
Concept Prerequisite Relations
Chen Liang1

Jianbo Ye1
1

Han Zhao2

Bart Pursel1

C. Lee Giles1

The Pennsylvania State University
2
Carnegie Mellon University{cul226, jxy198, bkp10, clg20}@psu.edu
han.zhao@cs.cmu.edu

ABSTRACT
Strict partial order is a mathematical structure commonly
seen in relational data. One obstacle to extracting such typeof relations at scale is the lack of large scale labels for building effective data-driven solutions. We develop an active
learning framework for mining such relations subject to astrict order. Our approach incorporates relational reasoning not only in finding new unlabeled pairs whose labels canbe deduced from an existing label set, but also in devising
new query strategies that consider the relational structureof labels. Our experiments on concept prerequisite relations
show our proposed framework can substantially improve theclassification performance with the same query budget compared to other baseline approaches.

1.

INTRODUCTION

Pool-based active learning is a learning framework where thelearning algorithm is allowed to access a set of unlabeled examples and ask for the labels of any of these examples [3].
Its goal is to learn a good classifier with significantly fewerlabels by actively directing the queries to the most “valuable” examples. In a typical setup of active learning, the label dependency among labeled or unlabeled examples is notconsidered. But data and knowledge in the real world areoften embodied with prior relational structures. Taking into
consideration those structures in building machine learning
solutions can be necessary and crucial. The goal of this paper is to investigate the query strategies in active learning ofa strict partial order, namely, when the ground-truth labelsof examples constitute an irreflexive and transitive relation.
In this paper, we develop efficient and effective algorithms
extending popular query strategies used in active learning
to work with such relational data. We study the following
problem in the active learning context:
Problem. Given a finite set V , a strict order on V is a
type of irreflexive and transitive (pairwise) relation. Such astrict order is represented by a subset G ⊆ V × V . Given an
unknown strict order G, an oracle W that returns W (u, v) =−1 + 2 · 1[(u, v) ∈ G] ∈ {−1, 1}, and a feature extractor
F : V × V 7→ Rd , find h : Rd 7→ {−1, 1} from a hypothesis
class H that predicts whether or not (u, v) ∈ G for each pair(u, v) ∈ V × V and u 6= v (using h(F(u, v))) by querying W
a finite number of (u, v) pairs from V × V .
Our main focus is to develop reasonable query strategies in
active learning of a strict order exploiting both the knowledge from (non-consistent) classifiers trained on a limited
number of labeled examples and the deductive structures
among pairwise relations. Our work also has a particularfocus on partial orders. If the strict order is total, a large
school called “learning to rank” has studied this topic [10],some of which are under the active learning setting [4]. Learning to rank relies on binary classifiers or probabilistic models
that are consistent with the rule of a total order. Such approaches are however limited in a sense to principally modeling a partial order: a classifier consistent with a total order
will always have a non-zero lower bound of error rate, if theground-truth is a partial order but not a total order.
In our active learning problem, incorporating the deductive
relations of a strict order in soliciting examples to be labeled is non-trivial and important. The challenges motivating us to pursue this direction can be explained in threefolds: First, any example whose label can be deterministically reasoned from a labeled set by using the properties ofstrict orders does not need further manual labeling or statistical prediction. Second, probabilistic inference of labels
based on the independence hypothesis, as is done in the conventional classifier training, is not proper any more because
the deductive relations make the labels of examples dependent on each other. Third, in order to quantify how valuable
an example is for querying, one has to combine uncertainty
and logic to build proper representations. Sound and efficient heuristics with empirical success are to be explored.
One related active learning work that deals with a similar setting to ours is [13], whereas equivalence relations are
considered instead. Particularly, they made several crude
approximations in order to expedite the expected error calculation to a computational tractable level. We approachthe design of query strategies from a different perspective
while keeping efficiency as one of our central concerns.
To empirically study the proposed active learning algorithm,
we apply it to concept prerequisite learning problem [15, 8],
where the goal is to predict whether a concept A is a pre-requisite of a concept B given the pair (A, B). Although
there have been some research efforts towards learning prerequisites [16, 15, 8, 17], the mathematical nature of theprerequisite relation as strict partial orders has not been
investigated. In addition, one obstacle for effective learningbased solutions to this problem is the lack of large scale
prerequisite labels. Liang et al. [9] applied standard active
learning to this problem without utilizing relation properties of prerequisites. Active learning methods tailored forstrict partial orders provide a good opportunity to tackle
the current challenges of concept prerequisite learning.
Our main contributions are summarized as follows: Fist, we
propose a new efficient reasoning module for monotonicallycalculating the deductive closure under the assumption ofa strict order. This computational module can be usefulfor general AI solutions that need fast reasoning in regard
to strict orders. Second, we apply our reasoning module
to extend two popular active learning approaches to handle
relational data and empirically achieve substantial improvements. This is the first attempt to design active learning
query strategies tailored for strict partial orders. Third, under the proposed framework, we solve the problem of concept prerequisite learning and our approach appears to be
successful on data from four educational domains, whereas
previous work have not exploited the relational structure of
prerequisites as strict partial orders in a principled way.

that a key difference between the traditional transitive closure and our definition of closure (Definition 3&4) is thatthe former only focuses on G but the latter requires calculation for both G and Gc . In the context of machine learning,
relations in G and Gc correspond to positive examples andnegative examples, respectively. Since both of these examples are crucial for training classifiers, existing algorithms
for calculating transitive closure such as the Warshall algorithm are not applicable. Thus we propose the following
theorem for monotonically computing the closure. Pleaserefer to supplemental material for the proofs.
Theorem 1. Let G be a strict order of V and WH a complete G-oracle on H ⊆ V × V . For any pair (a, b) ∈ V × V ,define the notation C(a,b) by(i) If (a, b) ∈ H, C(a,b) := H.
0(ii) If (a, b) ∈ Gc ∩ H c , C(a,b) := H ∪ N(a,b)
where0N(a,b):= {(d, c)|c ∈ AG∩H
∪ {b}, d ∈ DaG∩H ∪ {a}},b0and particularly N(a,b)⊆ Gc .

(iii) If (a, b) ∈ G∩H c , C(a,b) := H ∪N(a,b) ∪R(a,b) ∪S(a,b) ∪T(a,b) ∪ O(a,b) , whereN(a,b) := {(c, d) | c ∈ AG∩H
∪ {a}, d ∈ DbG∩H ∪ {b}},aR(a,b) := {(d, c) | (c, d) ∈ N(a,b) },S(a,b) := {(d, e) | c ∈ AG∩H
∪ {a}, d ∈ DbG∩H ∪ {b},a2. REASONING OF A STRICT ORDER
2.1 Preliminary(c, e) ∈ Gc ∩ H},
T(a,b) := {(e, c) | c ∈ AG∩H
∪ {a}, d ∈ DbG∩H ∪ {b},aDefinition 1 (Strict Order). Given a finite set V ,a subset G of V × V is called a strict order if and only if itsatisfies the two conditions: (i) if (a, b) ∈ G and (b, c) ∈ G,
then (a, c) ∈ G; (ii) if (a, b) ∈ G, then (b, a) 6∈ G.

O(a,b) :=2.2

Reasoning Module for Closure Calculation

With the definitions in the previous section, this section proposes a reasoning module that is designed to monotonicallycalculate the deductive closure for strict orders. Remark(c,d)∈S(a,b) ∪T(a,b)

00
N(c,d),

G∩(H∪N(a,b) )00
N(c,d):= {(f, e) | e ∈ Ad

Definition 2 (G-Oracle). For two subsets G, H ⊆V × V , a function denoted as WH (·, ·) : H 7→ {−1, 1} iscalled a G-oracle on H iff for any (u, v) ∈ H, WH (u, v) =−1 + 2 · 1[(u, v) ∈ G].
The G-oracle returns a label denoting whether a pair belongs
to G.
Definition 3 (Completeness of an Oracle). A Goracle of strict order WH is called complete if and only if
H satisfies: for any a, b, c ∈ V , (i) if (a, b) ∈ H ∩ G,(b, c) ∈ H ∩ G, then (a, c) ∈ H ∩ G; (ii) if (a, b) ∈ H ∩ G,(a, c) ∈ H ∩ Gc , then (b, c) ∈ H ∩ Gc ; (iii) if (b, c) ∈ H ∩ G,(a, c) ∈ H ∩ Gc , then (a, b) ∈ H ∩ Gc ; (iv) if (a, b) ∈ H ∩ G,
then (b, a) ∈ H ∩ Gc , where Gc is the complement of G.
WH is called complete if it is consistent under transitivity
when restricted on pairs from H.
Definition 4 (Closure). Given a strict order G, for
any H ⊆ V × V , its closure is defined to be the smallest set
H such that H ⊆ H and the G-oracle WH is complete.
Definition 5 (Descendant and Ancestor). Given astrict order G of V and a ∈ V , its ancestor subject to G isGAG
a := {b | (b, a) ∈ G} and its descendant is Da := {b |(a, b) ∈ G}.

(e, d) ∈ Gc ∩ H},[∪ {d},

G∩(H∪N(a,b) )f ∈ Dc∪ {c}}.

In particular, N(a,b) ⊆ G and R(a,b) ∪ S(a,b) ∪ T(a,b) ∪O(a,b) ⊆ Gc .
For any pair (x, y) ∈ V ×V , the closure of H 0 = H ∪{(x, y)}is C(x,y) .
Figure 1 provides an informal explanation of each necessary
condition (except for R(a,b) ) mentioned in the theorem. If(a, b) is a positive example, i.e. (a, b) ∈ G, then (i) N(a,b) is
a set of inferred positive examples by transitivity; (ii) R(a,b)
is a set of inferred negative examples by irreflexivity; (iii)S(a,b) and T(a,b) are sets of inferred negative examples bytransitivity; (iv) O(a,b) is a set of negative examples inferredfrom S(a,b) and T(a,b) . If (a, b) is a negative example, i.e.
0(a, b) ∈ Gc , then N(a,b)
is a set of negative examples inferredby transitivity.

3.

POOL-BASED ACTIVE LEARNING

The pool-based sampling [7] is a typical active learning scenario in which one maintains a labeled set Dl and an unlabeled set Du . In particular, we let Du ∪ Dl = D = {1, . . . , n}
and Du ∩ Dl = ∅. For i ∈ {1, . . . , n}, we use xi ∈ Rd todenote a feature vector representing the i-th instance, andyi ∈ {−1, +1} to denote its groundtruth class label. At eachround, one or more instances are selected from Du whose label(s) are then requested, and the labeled instance(s) are

g

h
e
?

a
c

(a)

g

h

g

h

g

h

f

e

f

e

f

e

f

b

a

b

a

b

a

b

d

c

(b)

d

c

(c)

d

c

(d)

d

Figure 1: Following the notations in Theorem 1: (a) Black lines are pairs in H, solid lines are pairs in G, anddashed lines are pairs in Gc . The pair (a, b) in the cyan color is the pair to be labeled or deduced. (b) If (a, b) ∈ G,{(a, b), (e, f ), (a, f ), (e, b)} ⊆ N(a,b) . (c) If (a, b) ∈ G, {(h, e), (h, a)} ⊆ T(a,b) and {(b, g), (f, g)} ⊆ S(a,b) . (d) If (a, b) ∈ Gc ,0{(a, b), (a, d), (c, b), (c, d)} ⊆ N(a,b). Likewise, if ∃(x, y) ∈ G, s.t.(a, b) ∈ S(x,y) ∪ T(x,y) , {(a, b), (a, d), (c, b)} ⊆ O(x,y) .
then moved to Dl . Typically instances are queried in a prioritized way such that one can obtain good classifiers trainedwith a substantially smaller set Dl . We focus on the poolbased sampling setting where queries are selected in serial,i.e., one at a time.

3.1

Query Strategies

The key component of active learning is the design of aneffective criterion for selecting the most “valuable” instanceto query, which is often referred to as query strategy. We
use s∗ to refer to the selected instance by the strategy. In
general, different strategies follow a greedy framework:s∗ = argmax
s∈Du

min
y∈{−1,1}f (s; y, Dl ),(1)where f (s; y, Dl ) ∈ R is a scoring function to measure therisks of choosing y as the label for xs ∈ Du given an existinglabeled set Dl .
We investigate two commonly used query strategies: uncertainty sampling [6] and query-by-committee [14]. We showthat under the binary classification setting, they can all bereformulated as Eq. (1).
Uncertainty Sampling selects the instance which it isleast certain how to label. We choose to study one popular uncertainty-based sampling variant, the least confident.
Subject to Eq. (1), the resulting approach is to letf (s; y, Dl ) = 1 − P∆(Dl ) (ys = y|xs ),(2)

where P∆(Dl ) (ys = y|xs ) is a conditional probability which isestimated from a probabilistic classification model ∆ trainedon {(xi , yi ) | ∀i ∈ Dl }.
Query-By-Committee maintains a committee of models trained on labeled data, C(Dl ) = {g (1) , ..., g (C) }. It
aims to reduce the size of version space. Specifically, it selects the unlabeled instance about which committee members disagree the most based on their predictions. Subject
to Eq. (1), the resulting approach is to let
XC
f (s; y, Dl ) =1[y 6= g (k) (xs )],(3)
k=1

where g (k) (xs ) ∈ {−1, 1} is the predicted label of xs using
the classifier g (k) .
Our paper will start from generalizing Eq. (1) and show that
it is possible to extend the two popular query strategies forconsidering relational data as a strict order.

4.

ACTIVE LEARNING OF A STRICT ORDER

Given G a strict order of V , consider a set of data D ⊆ V ×V ,where (a, a) 6∈ D, ∀a ∈ V . Similar to the pool-based active
learning, one needs to maintain a labeled set Dl and an
unlabeled set Du . We require that D ⊆ Dl ∪ Du and Dl ∩Du = ∅. Given a feature extractor F : V × V 7→ Rd , we canbuild a vector dataset {x(a,b) = F(a, b) ∈ Rd | (a, b) ∈ D}.
Let y(a,b) = −1 + 2 · 1[(a, b) ∈ G] ∈ {−1, 1} be the groundtruth label for each (a, b) ∈ V × V . Active learning aims toquery Q a subset from D under limited budget and construct
a label set Dl from Q, in order to train a good classifier hon Dl ∩ D such that it predicts accurately whether or not an
unlabeled pair (a, b) ∈ G by h(F(a, b)) ∈ {−1, 1}.
Active learning of strict orders differs from the traditional
active learning in two unique aspects: (i) By querying thelabel of a single unlabeled instance, one may obtain a setof labeled examples, with the help of strict orders’ properties; (ii) The relational information of strict orders could
also be utilized by query strategies. We will present our efforts towards incorporating the above two aspects into active
learning of a strict order.

4.1

Basic Relational Reasoning in Active Learning

A basic extension from standard active learning to one under
the strict order setting is to apply relational reasoning whenboth updating Dl and predicting labels. Algorithm 1 shows
the pseudocode for the pool-based active learning of a strict
order. When updating Dl with a new instance (a, b) ∈ Du
whose label y(a,b) is acquired from querying, one first calculates Dl0 , i.e., the closure of Dl ∪ {(a, b)}, using Theorem 1, and then sets Dl := Dl0 and Du := D\Dl0 respectively.
Therefore, it is possible to augment the labeled set Dl withmore than one pair at each stage even though only a single instance is queried. Furthermore, the following corollaryshows that given a fixed set of samples to be queried, theirquerying order does not affect the final labeled set Dl constructed.
Corollary 1.1. Given a list of pairs Q of size m whose
elements are from V ×V , let i1 , . . . , im and j1 , . . . , jm be twodifferent permutations of 1, . . . , m. Let I0 = ∅ and J0 = ∅,and Ik = Ik−1 ∪ {qik }, Jk = Jk−1 ∪ {qjk } for k = 1, . . . , m,where · is defined as the closure set under G. We have Im =Jm , which is the closure of {qi ∈ V × V | i = 1, . . . , m}.
Corollary 1.1 is a straightforward result from the uniquenessof closure, which is also verified by our experiments. The la-Algorithm 1 Pseudocode for pool-based active learning ofa strict order.
Input:
D ⊆V ×V% a data set
Initialize:
Dl ← {(as1 , bs1 ), (as2 , bs2 ), ..., (ask , bsk )} % initial labeled set with k seeds
Dl ← Dl % initial closure
Du ← D\Dl % initial unlabeled set
while Du 6= ∅ do
Select (a∗ , b∗ ) from Du % according to a query strategy
Query the label y(a∗ ,b∗ ) for the selected instance(a∗ , b∗ )Dl ← Dl ∪ {(a∗ , b∗ )}Du ← D\Dlend while

Table 1: Dataset statistics.
Domain# Concepts# Pairs# Prerequisites

120
89
153
224

826
1681
1962
2060

292
524
487
699

Data Mining
Geometry
Physics
Precalculus

by assuming y(a,b)=y. The modified scoring function reads:
F (S(y(a,b) = y), Dl ) =X
1 − P∆(Dl ∩D) (y(u,v) = ŷ(u,v) |x(u,v) ).

(6)(u,v)∈S(y(a,b) =y)

Query-by-Committee with Reasoning. Likewise, one also has
the extension for QBC, where {g (k) }C
k=1 is a committee ofclassifiers trained on bagging samples of Dl ∩ D,
F (S(y(a,b) = y), Dl ) =
X
XC
k=1

1(ŷ(u,v) 6= g (k) (x(u,v) )).

(7)(u,v)∈S(y(a,b) =y)

beled set Dl contains two kinds of pairs based on where theirlabels come from: The first kind of labels comes directlyfrom queries, and the second kind comes from the relational
reasoning as explained by Theorem 1. Such an approach has
a clear advantage over standard active learning at the samebudget of queries, because labels of part of the test pairs
can be inferred deterministically and as a result there will
be more labeled data for supervised training. In our setup ofactive learning, we train classifiers on D ∩ Dl and use themfor predicting the labels of remaining pairs that are not in
Dl .

4.2

Query Strategies with Relational Reasoning

The relational active learning framework as explained in theprevious section however does not consider incorporating relational reasoning in its query strategy. We further develop
a systematic approach on how to achieve this.
We start from the following formulation: at each stage, onechooses a pair (a∗ , b∗ ) to query based on(a∗ , b∗ ) = argmax

F (S(y(a,b) = y), Dl ),(4)

S(y(a,b) = y) = (Dl ∪ {(a, b)}\Dl ) ∩ D.

(5)

min

(a,b)∈Du y∈{−1,1}

5.

5.1

Uncertainty Sampling with Reasoning. With relational reasoning, one not only can reduce the uncertainty of the queried
pair (a, b) but also may reduce that of other pairs deduced

DatasetWe use the Wiki concept map dataset from [17] which iscollected from textbooks on different educational domains.
Each concept corresponds to an English Wiki article. For
each domain, the dataset consists of prerequisite pairs in theconcept map. Table 1 summarizes the statistics of the our
final processed dataset.

5.2

Features

For each concept pair (A, B), we calculate two types of features following the popular practice of information retrieval
and natural language processing: graph-based features andtext-based features. Please refer to Table 2 for detailed description. Note we trained a topic model [1] on the Wiki
corpus. We also trained a Word2Vec [12] model on the same
corpus with each concept treated as an individual token.

5.3
Again, F is the scoring function. S(y(a,b) = y) is the setof pairs in D whose labels, originally unknown (6∈ Dl ), cannow be inferred by assuming y(a,b) = y using Theorem 1.
For each (u, v) ∈ S(y(a,b) = y), its inferred label is denotedas ŷ(u,v) in the sequel. One can see that this formulation
is a generalization of Eq. (1). We now proceed to develop
extensions for the two query strategies to model the dependencies between pairs imposed by the rule of a strict order.
Following the same notations as previously described withthe only difference that the numbering index is replaced by
the pairwise index, we propose two query strategies tailored
to strict orders.

EXPERIMENTS

For evaluation, we apply the proposed active learning algorithms to concept prerequisite learning problem [8]. Given apair of concepts (A, B), we predict whether or not A is aprerequisite of B, which is a binary classification problem.
Here, cases where B is a prerequisite of A and where no
prerequisite relation exists are both considered negative.

Experiment Settings

We follow the typical evaluation protocol of pool-based active learning. We first randomly split a dataset into a training set D and a test set Dtest with a ratio of 2:1. Then
we randomly select 20 samples from the training set as theinitial query set Q and compute its closure Dl . Meanwhile,
we set Du = D\Dl . In each iteration, we pick an unlabeledinstance from Du to query for its label, update the label
set Dl , and re-train a classification model on the updated
Dl ∩ D. The re-trained classification model is then evaluated on Dtest . In all experiments, we use a random forests
classifier [2] with 200 trees as the classification model. We
use Area under the ROC curve (AUC) as the evaluation
metric. Taking into account the effects of randomness subject to different initializations, we continue the above experimental process for each method repeatedly with 300 preselected distinct random seeds. Their average scores andTable 2: Feature description. Top: graph-based features. Bottom: text-based features.
FeatureDescription

In/Out Degree
Common Neighbors# Links
Link Proportion

The in/out degree of A/B.
# common neighbors of A and B.
# times A/B links to B/A.
The proportion of pages that link to A/B also link to
B/A.
The Normalized Google Distance between A andB [18].
The Pointwise Mutual Information relatedness between the incoming links of A and B.
A metric to measure how differently A and B’s related
concepts refer to each other [8].
The difference between A and B’s hub/authority
scores. [5]

NGD
PMI
RefD
HITS
1st Sent
In Title
Title Jaccard
LengthMentionNP
Tf-idf Sim
Word2Vec Sim
LDA Entropy
LDA Cross Entropy

Whether A/B is in the first sentence of B/A.
Whether A appears in B’s title.
The Jaccard similarity between A and B’s titles.
# words of A/B’s content.
# times A/B are mentioned in the content of B/A.
# noun phrases in A/B’s content; # common nounphrases.
The cosine similarity between Tf-idf vectors for A and
B’s first paragraphs.
The cosine similarity between vectors of A and B
trained by Word2Vec.
The Shannon entropy of the LDA vector of A/B.
The cross entropy between the LDA vector of A/B
and B/A.

Table 3: Summary of compared query strategies.
MethodUse reasoning
when
updating Dl

Use reasoning to selectthe instanceto query

Use learning to selectthe instanceto queryRandomLC, QBC
Random-R
LC-R, QBC-R
CNT
LC-R+, QBC-R+

7
7
3
3
3
3

7
7
7
7
3
3

7
3
7
3
7
3

confidence intervals (α = 0.05) are reported. We compare
four query strategies: (i) Random: randomly select an instance to query; (ii) LC: least confident sampling, a widelyused uncertainty sampling variant. We use logistic regression to estimate posterior probabilities; (iii) QBC: queryby-committee algorithm. We apply query-by-bagging [11]and use a committee of three decision trees; (iv) CNT: asimple baseline query strategy designed to greedily select an
instance whose label can potentially infer the most number of unlabeled instances. Following the previous notations, the scoring function for CNT is F (S(y(a,b) = y), Dl ) =|S(y(a,b) = y)| , which is solely based on logical reasoning.
For experiments, we test each query strategy under threesettings: (i) Traditional active learning where no relational
information is considered. Query strategies under this setting are denoted as Random, LC, and QBC. (ii) Relational
active learning where relation reasoning is applied to updating Dl and predicting labels of Dtest . Query strategies under
this setting are denoted as Random-R, LC-R, and QBC-R.
(iii) Besides being applied to updating Dl , relational reasoning is also incorporated in the query strategies. Querystrategies under this setting are the baseline method CNT
and our proposed extensions of LC and QBC for strict partial orders, denoted as LC-R+ and QBC-R+, respectively.
Table 3 summarizes the query strategies studied in the experiments.

5.4

Experiment Results

Figure 2 shows the AUC results of different query strategies. For each case, we present the average values and 95%
C.I. of repeated 300 trials with different train/test splits. In
addition, Figure 3 compares the relations between the number of queries and the number of labeled instances acrossdifferent query strategies. Note that in the relational active learning setting querying a single unlabeled instancewill result in one or more labeled instances. According to
Figure 2 and Figure 3, we have the following observations:First, by comparing query strategies under the settings (ii)and (iii) with setting (i), we observe that incorporating relational reasoning into active learning substantially improves
the AUC performance of each query strategy. In addition,
we find the query order, which is supposed to be different foreach strategy, does not affect Dl at the end when D ⊆ Dl .
Thus, it partly verifies Corollary 1.1. Second, our proposed
LC-R+ and QBC-R+ significantly outperform other compared query strategies. Specifically, when comparing themwith LC-R and QBC-R, we see that incorporating relational
reasoning into directing the queries helps to train a betterclassifier. Figure 3 shows that LC-R+ and QBC-R+ leadto more labeled instances when using the same amount ofqueries than that of LC-R and QBC-R. This partly contributes to the performance gain. Third, LC-R+ and QBCR+ are more effective at both collecting a larger labeled
set and training better classifiers than the CNT baseline.
In addition, by comparing CNT with LC-R, QBC-R, andRandom-R, we observe that a larger size of the labeled set
does not always lead to a better performance. Such observations demonstrate the necessity of combining deterministic
relational reasoning and probabilistic machine learning indesigning query strategies.
In addition to effectiveness, we also conduct empirical studies on the runtime of the reasoning module and include theresults in the supplemental material.

6.

CONCLUSION

We propose an active learning framework tailored to relational data in the form of strict partial orders. An efficient reasoning module is proposed to extend two commonlyused query strategies – uncertainty sampling and query bycommittee. Experiments on concept prerequisite learningshow that incorporating relational reasoning in both selecting valuable examples to label and expanding the training set significantly improves standard active learning approaches. Future work could be to explore the following: (i)apply the reasoning module to extend other query strategies; (ii) active learning of strict partial orders from a noisy
oracle.

7.

REFERENCES[1] D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent Dirichlet
allocation. Journal of machine Learning research,3(Jan):993–1022, 2003.
[2] L. Breiman. Random forests. Machine learning, 45(1):5–32,
2001.
[3] D. A. Cohn, Z. Ghahramani, and M. I. Jordan. Active
learning with statistical models. Journal of Artificial
Intelligence Research, 4(1):129–145, 1996.
[4] P. Donmez and J. G. Carbonell. Optimizing estimated loss
reduction for active sampling in rank learning. In Proc.
ICML, pages 248–255. ACM, 2008.

98
96
94
92
90
88
86
84
82

RandomLC
Random-R
LC-R
CNT
LC-R+

80
75

20

40

60

80

RandomLC
Random-R
LC-R
CNT
LC-R+

94
92
90
88

100

# queries (% unlabeled data)

96

20

40

60

80

100

# queries (% unlabeled data)(a) Data Mining - LC(b) Geometry - LC

95

98

80
75

20

40

60

80

# queries (% unlabeled data)96

AUC (%)AUC (%)

RandomQBC
Random-R
QBC-R
CNT
QBC-R+

85

RandomQBC
Random-R
QBC-R
CNT
QBC-R+

94
92
90
88

100

(e) Data Mining - QBC

20

40

60

80

# queries (% unlabeled data)

20

40

60

80

99
98
97
96
95
94
93
92
91
90

100

# queries (% unlabeled data)(c) Physics - LC

100

90

RandomLC
Random-R
LC-R
CNT
LC-R+

100

98
96
94
92
90
88
86
84
82

AUC (%)

85

AUC (%)AUC (%)

90

AUC (%)98

AUC (%)

100(f) Geometry -QBC

20

40

60

80

20

40

60

80

100

# queries (% unlabeled data)(d) Precalculus - LC

RandomQBC
Random-R
QBC-R
CNT
QBC-R+# queries (% unlabeled data)

RandomLC
Random-R
LC-R
CNT
LC-R+

100

99
98
97
96
95
94
93
92
91
90

AUC (%)

95(g) Physics - QBC

RandomQBC
Random-R
QBC-R
CNT
QBC-R+

20

40

60

80

# queries (% unlabeled data)

100(h) Precalculus - QBC

Figure 2: Comparison of different query strategies’ AUC scores for concept prerequisite learning.

100
00

600
200
00

100 200 300 400 500 600# queries(a) Data Mining - LC

Random-R
QBC-R
CNT
QBC-R+

200
100
00

100 200 300 400 500 600# queries(e) Data Mining - QBC# labeled instances

1000# labeled instances

1200

500
300

200 400 600 800 1000 1200

# queries# queries(b) Geometry - LC

600
400

Random-R
LC-R
CNT
LC-R+

400

800
600
Random-R
QBC-R
CNT
QBC-R+

400
200
00

200 400 600 800 1000 1200

# queries(f) Geometry - QBC# labeled instances

Random-R
LC-R
CNT
LC-R+

200

800

1400
1200
1000
800
600
Random-R
400
LC-R
CNT
200
LC-R+
00 200 400 600 800 1000 1200 1400

# queries(c) Physics - LC(d) Precalculus - LC

1400
1200
1000
800
600
Random-R
400
QBC-R
CNT
200
QBC-R+
00 200 400 600 800 1000 1200 1400

1400
1200
1000
800
600
Random-R
400
QBC-R
CNT
200
QBC-R+
00 200 400 600 800 1000 1200 1400

# queries(g) Physics - QBC# labeled instances

300# labeled instances

400

1400
1200
1000
800
600
Random-R
400
LC-R
CNT
200
LC-R+
00 200 400 600 800 1000 1200 1400

# labeled instances

1000# labeled instances

1200

500

# labeled instances

600# queries(h) Precalculus - QBC

Figure 3: Comparison of relations between the number of queries and the number of labeled instances whenusing different query strategies.
[5] J. M. Kleinberg. Authoritative sources in a hyperlinked
environment. Journal of the ACM, 46(5):604–632, 1999.
[6] D. D. Lewis and J. Catlett. Heterogeneous uncertainty
sampling for supervised learning. In Proc. ICML, pages
148–156, 1994.
[7] D. D. Lewis and W. A. Gale. A sequential algorithm fortraining text classifiers. In Proc. SIGIR, pages 3–12, 1994.
[8] C. Liang, Z. Wu, W. Huang, and C. L. Giles. Measuring
prerequisite relations among concepts. In Proc. EMNLP,
pages 1668–1674, 2015.
[9] C. Liang, J. Ye, S. Wang, B. Pursel, and C. L. Giles.
Investigating active learning for concept prerequisite
learning. In Proc. EAAI, 2018.
[10] T.-Y. Liu. Learning to rank for information retrieval.
Foundations and Trends R in Information Retrieval,3(3):225–331, 2009.
[11] N. A. H. Mamitsuka. Query learning strategies using
boosting and bagging. In Proc. ICML, volume 1. Morgan
Kaufmann Pub, 1998.
[12] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, andJ. Dean. Distributed representations of words and phrases
and their compositionality. In Proc. NIPS, pages

3111–3119, 2013.
[13] S. Rendle and L. Schmidt-Thieme. Active learning ofequivalence relations by minimizing the expected loss using
constraint inference. In Proc. ICDM, pages 1001–1006.
IEEE, 2008.
[14] H. S. Seung, M. Opper, and H. Sompolinsky. Query bycommittee. In Proc. COLT, pages 287–294. ACM, 1992.
[15] P. P. Talukdar and W. W. Cohen. Crowdsourced
comprehension: predicting prerequisite structure in
Wikipedia. In Proc. BEA, pages 307–315. ACL, 2012.
[16] A. Vuong, T. Nixon, and B. Towle. A method for finding
prerequisites within a curriculum. In Proc. EDM, pages
211–216, 2011.
[17] S. Wang, A. Ororbia, Z. Wu, K. Williams, C. Liang,
B. Pursel, and C. L. Giles. Using prerequisites to extract
concept maps from textbooks. In Proc. CIKM, pages
317–326. ACM, 2016.
[18] I. Witten and D. Milne. An effective, low-cost measure ofsemantic relatedness obtained from Wikipedia links. In
Proceeding of AAAI Workshop on Wikipedia and Artificial
Intelligence: an Evolving Synergy, pages 25–30, 2008.