MACHINE LEARNING METHODS FOR BUILDING EDUCATIONAL APPLICATIONS: CONCEPT PREREQUISITE LEARNING AND AUTOMATIC DISTRACTOR GENERATION

Abstract

The increasing amount of education-related data provides a valuable research opportunity for developing data-driven machine learning methods for building educational applications. This dissertation investigates machine learning solutions for two educational applications: concept prerequisite learning and automatic distractor generation.

A prerequisite relation describes a fundamental directed relation among concepts in knowledge structures. The first part of this dissertation focuses on the concept prerequisite learning problem, the study of machine learning methods for automatic concept prerequisite discovery. Specifically, this dissertation explores the use of Wikipedia – the largest free online encyclopedia – for concept prerequisite learning and presents the following studies towards automatically measuring concept prerequisite relations. First, a simple but effective link-based feature, RefD, is proposed for measuring prerequisite relations among concepts. Second, how concept prerequisite relations can be recovered from university course dependencies is explored. Third, active learning of concept prerequisite learning is studied to deal with the lack of large-scale concept prerequisite labels. The dissertation explores the mathematical nature of prerequisite relation being a strict partial order and proposes an active learning framework tailored for such relation. The proposed approach incorporates relational reasoning not only in finding new unlabeled pairs whose labels can be deduced from an existing label set, but also in devising new query strategies that consider the relational structure of labels.

Multiple choice questions (MCQs) are widely used to assess students’ knowledge and skills. Among all methods for creating good MCQs, finding reasonable distractors is crucial and usually the most time-consuming. The second part of this dissertation investigates automatic distractor generation (DG). In contrast with previous similarity-based methods, this dissertation presents two studies on machine learning methods for DG. The first study proposes a generative model learned from training generative adversarial nets to create useful distractors for automatically creating fill-in-the-blank questions. The second work investigates how ranking models can be used to select useful distractors for MCQs. The proposed models can learn to select distractors that resemble those in actual exam questions.

Finally, the dissertation introduces BBookX, a computer-facilitated bookcreation system. Using information retrieval techniques, BBookX is designed to facilitate the online book-creation process by searching OERs. BBookX is an actual educational application where the proposed methods for concept prerequisite learning and automatic distractor generation could be applied.

 

Chapter 1 |

Introduction

1.1 Background

There have been many computer-based learning systems from which a large amount of education-related usage data can be gathered. Examples include Learning Management Systems, Intelligent Tutoring Systems (ITS) [32] , and recently developed Massive Open Online Courses (MOOCs). Their usage data provides a valuable opportunity for developing data-driven machine learning methods for building educational applications, which has gained increasing attention from computer science subfields data mining and natural language processing (NLP).

In the field of educational data mining (EDM), researchers have investigated learning methods for applications such as (i) student modeling [154] , which includes performance prediction [126] , engagement modeling [136] , undesirable student behavior detection [57,104] , student profiling and grouping [58] , etc., (ii) planning and scheduling [66] , and (iii) automatic concept map construction [83] . With a special focus on utilizing text information, the NLP community has been working oneducational applicationsincluding automated written response scoring/evaluation [135] , tools for second and foreign language learners [153] , automatic test question generation [118] , educational dialog systems [98] , automatic grammatical error correction [120] , plagiarism detection [43] , etc. The use of machine learning for building educational applications is still at an early stage, compared to the extensive research on general machine learning. Note the major venues for such studies have a relatively short history, with about 10 years for the EDM conference^[1] and 15 years for the NLP BEA workshop^[2] .

This dissertation research seeks to develop machine learning methods for two educational applications: concept prerequisite learning and automatic distractor generation. Before introducing the two tasks, we begin by defining the following general terms that will be frequently used throughout this dissertation.

Definition 1 _(Concept). A concept is defined as a general idea of something. To be concrete, each concept in this dissertation corresponds to a Wikipedia entity/title. For example, “Machine learning”, “Data mining”, “Natural language processing” are all concepts.

Definition 2 (Prerequisite of a Concept). A prerequisite of a concept C is a concept that is necessary to learn before one can proceed to understand C. For example, “Linear algebra” is a prerequisite of “Deep learning”.

Definition 3 (Distractor). A distractor is an alternative answer used to sidetrack students from the correct answer. Distractors are usually a part of multiple choice questions. For example, “ADP” could be a distractor for the question, “A compound which is found in all living cells and play a key role in energy transformations is ___,” of which “ATP” is the correct answer.

1.2 Concept Prerequisite Learning

A prerequisite relation describes a fundamental directed connection among concepts in knowledge structures. Following the learning order that is consistent with the underlying prerequisite relationship is crucial to successful and effective teaching and learning processes. For the example shown in Figure 1.1, learning the concept “Hidden Markov Model” requires first understanding prerequisites such as “posterior probability” and “maximum likelihood”. Identifying prerequisite concepts is crucial for a variety of other educational applications such as curriculum planning [5] and intelligent tutoring systems [7] . It can be especially useful for online learning where students face a large amount of educational resources. For example, prerequisite information can be extremely helpful for students in MOOCs, who are typically faced with hundreds of course choices. Because each university creates its own

Probability

distribution

Conditional probability

distribution

Bayes’

theorem

Likelihood

function

Posterior

probability

Maximum

likelihood

Bayesian

network

Naïve Bayes

classifier

Hidden

Markov model

Figure 1.1. Concept prerequisite relations. “A → B” represents that the concept A is a prerequisite of the concept B.

MOOCs and puts them on different MOOC platforms, there are usually no readily identifiable prerequisite relations among courses from different universities or across different platforms. In addition, manually organizing prerequisites from thousands of MOOCs would be too time-consuming. This challenge motivates the need for automatic prerequisite relation discovery methods.

The first part of this dissertation focuses on solving the concept prerequisite learning problem [151] , the study of machine learning methods for automatic concept prerequisite discovery. Specifically, the dissertation focused on the concept prerequisite learning problem defined as follows:

Definition 4 (Concept Prerequisite Learning Problem.). Given a pair of concepts (A, B), predict whether A is a prerequisite of B.

Concept prerequisite learning is is a binary classification problem. Here, cases where B is a prerequisite of A and where no prerequisite relation exists are both considered negative.

A possible solution for developing scalable methods for automatic prerequisite discovery is to develop or integrate approaches that automatically infer such prerequisites from the increasing amount of digital educational data. Available data sources include knowledge bases, student assessment data, text books, course materials, etc. This dissertation explores the use of Wikipedia – the largest free online encyclopedia – for concept prerequisite learning and presents three studies towards automatically measuring concept prerequisite relations, which are summarized as follows.

1.2.1 RefD: A Link-based Feature for Measuring Concept Prerequisite Relations

As a semantic relation, concept prerequisite relation has not been well studied in computational linguistics. The dissertation proposes a simple link-based feature, namely reference distance (RefD) [90] , that effectively models the relation by measuring how differently two concepts refer to each other. Evaluations on two datasets that include seven domains show that a Wikipedia-based RefD implementation outperforms existing supervised learning-based methods.

1.2.2 Learning Concept Prerequisites from University Course Dependencies

Besides using knowledge bases such as Wikipedia, this dissertation also investigates how to recover concept prerequisite relations from course dependencies [94] . An optimization-based framework is proposed to address the problem. The first real dataset for empirically studying this problem is created, which consists of the listings of computer science courses from 11 U.S. universities and their concept pairs with prerequisite labels. Experiment results on a synthetic dataset and the real course dataset both show that the proposed method outperforms existing baselines.

1.2.3           Active Learning for Concept Prerequisite Learning

A major obstacle to extracting concept prerequisite relations at scale is the lack of large-scale labels to enable effective data-driven solutions. This dissertation presents the first study [93] to investigate the applicability of active learning to concept prerequisite learning. We propose a novel set of features tailored for prerequisite classification and compare the effectiveness of four widely used query strategies. Experimental results for domains including data mining, geometry, physics, and precalculus show that active learning can be used to reduce the amount of training data required. Given the proposed features, the query-by-committee strategy outperforms other compared query strategies.

Mathematically, a prerequisite relation is a type of strict partial order, a mathematical structure commonly seen in relational data. As a follow-up work for the abovementioned study, this dissertation proposes an active learning framework [95] for mining such relations subject to a strict order. The proposed approach incorporates relational reasoning not only in finding new unlabeled pairs whose labels can be deduced from an existing label set, but also in devising new query strategies that consider the relational structure of labels. Experiments on concept prerequisite relations show the proposed framework can substantially improve the classification performance with the same query budget compared to other baseline approaches.

1.3 Automatic Distractor Generation for Multiple Choice

Questions

Multiple choice questions (MCQs) are widely used as an assessment of students’ knowledge and skills. An MCQ consists of three elements: (i) stem, the question sentence; (ii) key, the correct answer; and (iii) distractors, alternative answers used to sidetrack students from the correct answer. See Figure 1.2 for examples of MCQs. Among all methods for creating good MCQs, finding reasonable distractors is crucial and usually the most time-consuming. The second part of this dissertation investigates automatic distractor generation (DG), i.e., generating distractors given

the stem and the key to the question. DG is a crucial step for multiple choice question generation (MCQG) because one of its main challenges is the generation of “good” distractors which can distinguish knowledgeable test takers from less knowledgeable ones, in the sense that the question becomes more effective at testing a student’s knowledge.

Most existing methods for DG are based on semantic similarities [2,54,80] .

Distractors are selected from a ranked list based on a weighted combination of

1. What is the least dangerous radioactive decay?
   • Beta decay (b) Alpha decay (c) Zeta decay (d) Gamma decay
2. If extension in spring is proportional to load applied then material obeys ___.
   • Gravitational law (b) Newton’s law (c) Hooke’s law (d) Charles’s law

Figure 1.2. Examples of multiple choice questions. The correct answers are written in bold text. Note the second MCQ is also a fill-in-the-blank question.

different similarity metrics, where the weights are determined by heuristics. In contrast with previous similarity-based methods, this dissertation presents two studies on machine learning methods for DG, which are summarized below.

1.3.1           Distractor Generation with Generative Adversarial Nets

We propose a generative model learned from training generative adversarial nets

(GANs) to create useful distractors for automatically creating fill-in-the-blank questions [92] . Our method utilizes only context information and does not use the correct answer, which is completely different from previous ontology-based or similarity-based approaches. Trained on the Wikipedia corpus, the proposed model can predict Wiki entities as distractors. Our method is evaluated on two biology question datasets collected from Wikipedia and actual college-level exams. Experimental results show that our context-based method achieves comparable performance to a frequently used word2vec-based method for the Wiki dataset. In addition, we propose a second-stage learner to combine the strengths of the two methods, which further improves the performance on both datasets, with 51.7% and 48.4% of generated distractors being acceptable.

1.3.2          Learning to Rank for Distractor Generation

We investigate how machine learning models, specifically ranking models, can be used to select useful distractors for MCQs [91] . Our proposed models can learn to select distractors that resemble those in actual exam questions, which is different from most existing unsupervised ontology-based and similarity-based methods. We empirically study feature-based and neural net based (NN-based) ranking models with experiments on the recently released SciQ dataset and our MCQL dataset. Experimental results show that feature-based ensemble learning methods (random forest and LambdaMART) outperform both the NN-based method and unsupervised baselines. These two datasets can serve as benchmarks for distractor generation.

1.4 Summary of Research Contributions

To summarize, the goal of this dissertation is to design machine learning methods tailored for two educational applications: concept prerequisite learning and automatic distractor generation for multiple choice questions. The main research contributions include:

• A simple but effective link-based feature for measuring concept prerequisite relations. [90]
• A novel optimization-based method to learn concept-level prerequisite relations from course dependencies. [94]
• The first study of active learning for the concept prerequisite learning problem. [93]
• The first attempt to design active learning query strategies tailored for strict partial orders. The proposed methods are applied to concept prerequisite learning and appear to be successful on data from educational domains. [95] • The first application of GANs to automatic distractor generation. [92]
• Supervised learning to rank methods for automatic distractor generation. [91]

1.5 Structure of the Dissertation

This dissertation presents the research described above. Specifically, Chapter 2 introduces a simple but effective link-based feature, RefD, for measuring concept prerequisite relation, and Chapter 3 proposes an optimization framework to learn concept prerequisites from university course dependencies. Chapter 4, then, investigates active learning for concept prerequisite learning. Chapter 5 explores the mathematical nature of prerequisite relation being a strict partial order and proposes an active learning framework tailored for such relation. The focus shifts to distractor generation in Chapter 6, which presents two studies on supervised learning methods for automatic distractor generation, and Chapter 7, which introduces BBookX, an educational application where the proposed methods for distractor generation and concept prerequisite learning would potentially be useful. Lastly, Chapter 8 concludes the dissertation and discusses possible future work.

[1] The International Conference on Educational Data Mining

[2] The Workshop on Innovative Use of NLP for Building Educational Applications

MACHINE LEARNING METHODS FOR BUILDING EDUCATIONAL APPLICATIONS: CONCEPT PREREQUISITE LEARNING AND AUTOMATIC DISTRACTOR GENERATION

Sharing is caring!