Questimator: Generating Knowledge Assessments for Arbitrary Topics

1 Introduction

An increasing number of learners are opportunistic and selfdriven [Brandt et al., 2009; Sadowski et al., 2015; Cai et al., 2015]. Online learning opportunities such as MOOCs attract diverse students with a range of prior knowledge and experience [Kulkarni et al., 2015]. While online resources are a boon to self-directed learning, knowledge gaps cause learners to struggle with new material, lose motivation, and even avoid future subjects due to lowered self-perceived efficacy [Horwitz and Cope, 1986].

Assessments can help learners diagnose what they know, which may be particularly helpful in informal learning domains. Unfortunately informal learning domains are precisely those that often lack formal assessments. Relying on learners' self-diagnosis is tricky because they don't know what they don't know [Caputo and Dunning, 2005].

Traditionally, formative assessment of factual knowledge has relied on experts, such as teachers or textbook authors. However, what such expert resources provide in quality, they lack in breadth [Elwood and Klenowski, 2002]. Because creating formative assessments of factual knowledge is timeconsuming, such assessments are limited to a small set of common topics of interest. Furthermore, such assessments are often missing for new or esoteric topics.

This paper introduces Questimator (described in Section 3), which, to our knowledge, is the first system that automatically generates multiple-choice question (MCQ) quizzes for general topics from large networked corpora like Wikipedia, thus significantly extending the scope of automatically generated questions. For example, Figure 1 shows Questimator's automatically generated assessment for the topic of "Reinforcement learning".

A learner uses Questimator by inputting a topic they would like to learn about, e.g. "reinforcement learning" or "France". To generate a coherent quiz, we need questions covering different perspectives of that topic. Unfortunately, previous work (Section 2) mostly focused on single MCQ generation, and did not provide a principled quiz generation approach. We propose a method (contribution 1) to find topics that are related to the input topic (Section 3.1) and generate questions for those related topics. We utilize the Wikipedia page-topage linkage graph and word embedding in the process.

Generating a single multiple-choice question (Section 3.2) involves creating three pieces of output: (i) a question stem, (ii) a correct answer, and (iii) a set of distractors (usually, at least 3). A question stem (Section 3.3) is the part where the item to ask for is stated, for example "Reinforcement learning is ." The examinee then chooses from correct answer and distractors. We propose a novel method (contribution 2) to find distractors (Section 3.4), combining Wikipedia's categorical structure (treated as a bipartite graph between the set of categorical labels and the set of articles), word embedding and sentence embedding.

By strengthening related topic search and distractor generation with Wikipedia's graph structure and semantic embedding, Questimator advances question generation for general topics. Through Questimator, we demonstrate the feasibility of leveraging existing corpora of knowledge such as Wikipedia to create interactive testing materials.

2 RelatedWork

2.1 Automatic MCQGeneration

Questimator is most closely related to prior systems for generating textual multiple-choice questions, as creating questions for math or logic involves different techniques. Most prior methods for generating text-based questions start with an input article. The question and correct answer are derived from this article (often from a single sentence). And they mostly aimed at language learning [Hoshino and Nakagawa, 2005; Brown et al., 2005; Mitkov et al., 2006; Lin et al., 2007; Smith et al., 2010; Gates et al., 2011; Mostow and Jang, 2012] or a single subject/textbook [Wang et al., 2008; Agarwal and Mannem, 2011; Bhatia et al., 2013].

These prior approaches to generating MCQ quizzes are limited to using single document or a fixed ontology alone to generate questions and distractors. Generating questions from a single document often scopes questions too narrowly to assess a learners understanding of a general topic, which typically spans related documents. Related topic selection is addressed in Section 3.1.

Also, while previous approaches work well for language learning or single subject, they suffer from limited choices of distractors when directly applied to general topics. Some systems pick distractors (having same POS tag as the correct answer) within the same article/textbook, based on term frequency etc. [Hoshino and Nakagawa, 2005; Agarwal and Mannem, 2011]. Using terms from the article as distractors can be problematic, because good distractors might not be frequently mentioned in the article. For example, "Formula Two" is a good distractor for "Formula One", but does not have a high frequency in the Wikipedia article for "Formula One". Other systems use fixed ontologies or dictionaries, such as WordNet [Miller, 1995], to find synonyms or other related words to use as distractors [Mitkov et al., 2006; Gates et al., 2011].

Although WordNet has 117,000 synsets, it focuses more on a limited type of cognitive concepts, rather than general knowledge concepts. For example, it contains "baby", and groups it with "infant", but it does not contain "Baby", the Justin Bieber hit song. This limitation also applies to other ontologies and dictionaries. In comparison, there are more than 5,129,000 English Wikipedia articles (by April 2016) for a broad range, containing long-tail topics and contemporary topics. We use the abundant Wikipedia corpora along with its socially-annotated categorical information [Kittur et al., 2009] to select distractor topics. So Questimator can work across the wide range of domains. In additional it integrates semantic embeddings when generating distractors.

2.2 Crowdsourcing Question Generation

Crowdsourcing has recently been explored as a way to generate questions. Christoforaki and Ipeirotis [2015] ask crowdworkers to directly generate the questions by mining existing Q&A sites. For example, Stack Overflow can be used as a scalable source of coding questions. However this subjects to extra economical cost, human selection of topics and additional time delay. Another challenge with these approaches is verifying that the questions are of high quality. Although Wikipedia is crowdsourced, popular articles are quite accurate and complete, and so the questions generated by Questimator are in a sense crowdsourced from source material subject to Wikipedia's quality control.

Questimator is a new approach to multiple-choice question generation. Inspired by the recent trend to utilize large scale datasets, and enabled by the corresponding development in NLP, Questimator uses a connected set of documents rather than a single document to generate multiple choice questions for general topics.

3 Questimator System

Questimator is our system for automatically generating multiple choice questions from Wikipedia. To use Questimator, learners first enter a topic they would like to know about (Questimator matches the entered topic to one that appears in Wikipedia). Questimator then returns a set of multiple choice questions automatically generated fromWikipedia chosen to assess the learner's knowledge of the provided topic (Figure 1 shows the first two questions generated for the topic "Reinforcement learning"). The number of questions to return is configurable (10 by default). To do this, Questimator:

1. generates a list of topics related to the input topic,
2. generates questions for each of the topics by
3. (a) generating question stems,
4. (b) generating and ranking distractors for each question stem.

3.1 Stage 1: Related topic identification

Related topics for questions can be drawn from prerequisites and subtopics. Given an input (main) topic X0, to generate candidate related topics Xi(i = 1↪ ▷ ▷ ▷ ↪ n), Questimator leverages both the Wikipedia document for the main topic, and the larger Wikipedia structure to generate and rank related topics.

To rank a candidate related topic T , Questimator uses three measures of similarity:

• ÷ Term frequency of T in the article of X0

• ÷ backlink overlap between T and X0

We will elaborate on each of the three features in the following. Questimator combines these measures to produce a single relatedness metric. And Questimator then ranks topics based on that, and chooses the top n(n ≥ 9) items as related topics to generate questions for the quiz.

• ÷ embedded semantic similarity between T and X0

Wikilink term frequency

Important concepts are likely to be repeatedly mentioned in the main article of X0, and so term frequency can be an important feature for identifying important subtopics. We extract all the links to other Wikipedia topics in the main article (called pagelinks or wikilinks), and count the term frequencies (TFX0 (T)) of the wikilinks. We take simple correferences into account, like abbreviations used in the article etc.

The term frequencies alone do not always identify good related topics. For example, "(software) agent" are mentioned many times in the article for "Reinforcement learning", but it is not an important related concept. Neither is "Real number" for "Invertible matrix".

Backlink Overlap

The topics that co-occur with the main topic frequently are likely to be related. Similar backlinks, i.e. articles of which topics mention the topic, may imply topic relation. We find the backlinks of the candidate topics and the main topic, and compute the cosine similarity between their "bag-ofbacklinks" vectors using the following formula:

, where ♣ · ♣ is the cardinality of the set, X0 is the main topic, T is any candidate topic. This allows us to identify topics that are overlooked in the main article that can not be identified by term frequency. For example, "Convolutional neural network" for "Deep learning", and "Affine transformation" for "Rigid transformation".

Embedded semantic similarity of topics

We used a Word2Vec [Mikolov et al., 2013] model trained on Wikipedia articles with topics (article titles) treated as independent entities. This produces a vector representation for each title and word. We then measure the similarity between topics T and X0 by their vectors' cosine similarity, simword2vec(T↪X0) = vec(T)·vec(X0) kvec(T)k2·kvec(X0)k2 . Adding this feature to the relatedness measure, we might pick out "Backpropagation" for "Artificial neural network", which does not have either high term frequency or backlink overlap, but is semantically related, as an important optimization method for neural networks.

Combine and Rank Relatedness

We combine the above three quantities, to produce a single scalar used for ranking. We normalize each of the three features independently by ˜ f = f-mean(f) pvar(f) . Then they are truncated to [-1↪ 1], so a single feature would not play a too significant role in some edge cases. We sum the three features to

create a combined relatedness measure,

are "Markov decision processes", "Software agent", "Dynamic programming", "Temporal difference learning", "Supervised learning", "Machine learning", "Optimal control theory", "Gradient descent" and "Q-learning".

3.2 Stage 2: Single question generation

Given a topic Xi(i = 0↪ ▷ ▷ ▷ ↪ n) as input, Questimator generates a single MCQ as following:

• ÷ Question stem and correct answer are generated first from the same sentence, and
• ÷ distractors are generated separately from articles of similar topics.

3.3 Stage 2(a): Question stem generation

Questimator generates questions directly testing on concept explanation are frequently used in expert assessments, by asking about the verbal phrases after the topic noun phrases in the main clause. Questimator generates gap-fill questions, as the stems. To generate a question stem for a given topic, Questimator retrieves the Wikipedia article of the topic, and

• ÷ finds a set of sentences that each contain the stemmed tokens of the topic, and process them by their order in the article,
• ÷ parses a sentence into a PCFG syntax tree, and uses TGrep [Rohde, 2004] to match the syntax tree with certain syntactic phrase patterns,
• ÷ if matched, substitutes the matched phrase with a blank to generate the question stem, and uses the matched phrase as the correct answer.

Then Questimator processes the sentences by their order in the article, as the first few sentences where the main topic is mentioned usually contain an explanation of that topic. Note the second step is similar to Heilman and Smith [2010].

Additional types of question stem can be generated by simply inserting more TGrep patterns into Questimator. As a byproduct of limiting the question stem types, we avoid the problem of choosing the proper question type.

3.4 Stage 2(b): Distractor Generation

Different from previous approaches, we propose to generate distractors utilizing the Wikipedia categorical information, and word/sentence embedding methods. To generate distractors, Questimator

• ÷ finds topics in the same categories as the main topic,
• ÷ ranks them by their Word2Vec semantic similarities with the main topic, and picks the top few topics,
• ÷ extracts one distractor phrase for each by matching patterns on syntax tree (same as extracting the correct answer in Section 3.3),
• ÷ uses skip-thought vectors [Kiros et al., 2015] to find distractor phrases most similar to the right answer phrase.

Pre-Extraction: Distractor Topic Selection

Unlike searching for related topics as question topics (Section 3.1), the criterion of similarity for selecting distractor topics is different. For example, "Camera Matrix" is a very related topic for "Camera Calibration", by our former criteria for relatedness. But as a distractor, examinees can easily tell a matrix's definition from a calibration process. Luckily, semantic information in the definition phrase reveals this difference, so sentence embedding can help. In general, topics at the same level of the category hierarchy are preferred. For example, "Supervised learning" and "Unsupervised learning", "Formula One" and "Formula Two". So categorical structure is more informative than linkage graph for this purpose.

Questimator first finds topics sharing at least one category with the question topic to construct a candidate pool. The category information is from Wikipedia's socially annotated (noisy) category hierarchy. Then Questimator ranks the distractor topic candidates by their Word2Vec similarity (same as in Section 3.1) with the question topic, and selects the top ones. For nd (nd = 3 by default) distractors, Questimator intermediately select m·nd distractor topics (m = 3 by default) to generate the distractor phrases.

Post-Extraction: Distractor Phrase Ranking

After we have mnd distractor phrases, we aim to pick the ones most difficult to distinguish from the correct answers. Questimator applies skip-thought vectors [Kiros et al., 2015] to measure the similarity between the distractors and the correct answer. Like Word2Vec generating vectors for words, skip-thought generates vectors for sentences, with semantically similar sentences having similar vectors.

Questimator throws away phrases containing the stemmed tokens of the main topic string, because there is a high probability that this will reveal itself as a wrong answer. We match the distractors' tenses with the correct answer. This prevents the examinees from identifying them as wrong answers by tense mismatch.

3.5 Questimator MCQExample

Finally distractors together with the question stem and the correct answer are delivered as a whole MCQ. The following is an example of a whole MCQ (correct answer in italic): A recurrent neural network (RNN) is .

• ÷ a class of artificial neural network where connections between units form a directed cycle
• ÷ an artificial neural network where connections between the units do not form a directed cycle
• ÷ a parallel computing paradigm similar to neural networks, with the difference that communication is allowed between neighbouring units only
• ÷ a type of artificial neural network in which an electrically adjustable resistance material is used to emulate the function of a neural synapse

One of our goals in developing Questimator is for it to generate MCQ quizzes at scale for topics that do not have quizzes available online. We maintain an updated corpus of quizzes generated from the most popular Wikipedia articles at https: //crowdtutor.info. For many topics, such as "Wonders of the World" and "Oasis (band)", no other existing quizzes are readily available. For topics like the ongoing "Syrian Civil War", expert-generated quizzes, even if available, are likely out-of-date. Finally, for some topics, such as "Fascism" and "Constructivism", we found that Questimator generated questions similar to those on existing quizzes.

4 Evaluation

The goal of Questimator is to generate good MCQ quizzes for knowledge evaluation for arbitrary topics.

To preliminarily evaluate Questimator questions' quality, we asked 4 TAs to inspect 258 Questimator questions (each question has one labeler), with most of questions in their areas of expertise. 78% were labeled useful for assessment. Problems with the others included multiple correct answers (36%), irrelevant question topic(22%), obvious answer (21%), all wrong answers (20%) and typos (11%). This kind of labeling has been used in previous work (Section 2). While it gives an idea how effective Questimator is at generating reasonable questions, it does not assess the actual ability of questions to discriminate between different levels of knowledge.

To enhance ecological validity, Questimator assesses actual student performance and compares this to expertgenerated quizzes. Note that experimental comparisons with previous work are too difficult to run due to the lack of shared resources. We focused on two key measures:

1. the correlation between a student's performance on a set of Questimator-generated questions, and the same student's performance on a set of human expert generated questions (Section 4.2), and
2. the discriminatory power of individual Questimatorgenerated questions, in terms of their ability to distinguish between students' with varying topic knowledge states (Section 4.3).

Our motivation for the first objective is that, we would like Questimator to automatically construct a quiz that provides a measure of student knowledge that is similar to an assessment constructed by expert teachers. If Questimator can provide assessments such that a student performance on said assessments correlates highly with the same student's performance on an expert-constructed assessment, that provides encouraging evidence that Questimator is able to capture signals that provide important insight into a student's knowledge.

The second objective stems from wanting a deeper understanding of the quality of the individual questions generated by Questimator. We would like to better quantify how effective different automatically-constructed items are at assessing student knowledge, and how these compare to expertgenerated questions. This could also have interesting implications for future work which may generate many questions and then subsample.

4.1 Experimental Setup

Our evaluation was a within-subjects experiment with participants drawn from Amazon Mechanical Turk. In this setup, each learner sees a quiz on a particular topic that is composed of both expert and Questimator generated questions.

Choosing topics We evaluated Questimator on 10 diverse topics. We chose topics for evaluation based on three criteria. First, we chose topics of broad interest because our participants were drawn from Mechanical Turk, which excluded topics like "Reinforcement Learning" that we thought few workers would know about. Second, we chose topics for which we could find existing online quizzes in order to compare to human expert-generated assessments. Finally, we chose topics that naturally lent themselves to textual questions and answers because Questimator does not yet handle mathematical symbols, images, or video. With these criteria, we chose ten topics across ten disciplines: customer satisfaction (marketing), earthquake (earth science), developmental psychology (psychology), cell (biology), market structure (economics), Vietnam War (history), metaphysics (philosophy), stroke (medicine), waste management (environmental science), elasticity (physics). Quizzes were drawn from MOOCs (Coursera/edX), US university/school board websites, and textbooks by major publishers (e.g., McGraw Hill). We identified two expert-generated quizzes for two topics (VietnamWar and earthquake), and one for the other topics.

Creating quizzes To generate a quiz for a topic, we combined 10 questions from an expert quiz 1 with the 10 Questimator questions. For two topics for which we had two expert quizzes, we generated a quiz which comprised 20 expert questions only, as sampled from both quizzes.

Selecting questions Expert-generated quizzes varied in their length from 10 to 60 questions. To eliminate testing differences across topics, we randomly sampled 10 questions from each expert quiz, after removing questions that relied on numerical calculations and True-False questions wherever possible (if removing these questions resulted in fewer than 10 questions, we retained them). One of the two expertgenerated quiz on the "Vietnam war" was drawn from a textbook chapter on the "Vietnam Era", and questions on domestic issues like the Civil Rights Movement were removed before sampling. For each topic, we also generated 10 questions on Questimator.

Participants Participants were recruited from Mechanical Turk. In all, 833 workers participated. All participants were paid $1 as base for their participation. In addition, they could earn up to $4 as bonuses based on their test scores.

Experimental procedure Participants were shown one question at a time. To reduce ordering effects, question order was randomized across participants. To reduce responseorder biases, the order of answer choices was also randomized. Each question was also augmented with a textbox that asked participants to explain their reasoning (at least 15 characters), a technique that has been previously shown to encourage honest effort [Kittur et al., 2008]. Finally, to discourage participants from using the Internet to search for answers, we monitored the web browser blur event and warned subjects that they would not be allowed to submit an answer if they left the window. Subjects spent an average of 58 seconds on each question. The average length of textbox comments was 66 characters, much longer than the required 15. We received between 78 and 82 completed quizzes for each topic.

4.2 Objective 1: Correlation with Expert Quizzes

We computed a score for both the expert- and Questimatorgenerated questions for each participant. Each question was weighted equally. The median Pearson correlation between Questimator and expert quiz scores was 0▷28 (Table 1).

Of course, even expert-generated quizzes may not correlate highly: two experts may focus on different subtopics within a general topics, or prioritize different forms of knowledge. Therefore, we also evaluated how well scores on two expert quizzes correlate for two topics. The Pearson correlation of the two scores for expert quizzes was 0▷430 for "Earthquake" (vs 0▷370 for the Questimator-expert) and 0▷460 for "Vietnam War" (vs 0▷275 for the Questimator-expert).

1 If two expert quizes were available, we selected one at random

Scores on Questimator quizzes correlate with expert quizzes to a lower but similar degree as to the two expert quizzes gathered for each category. We believe this means our quiz covers a subset of the whole topic space (also partially covered by expert quiz differently) using reasonable questions. Taken together, it suggests that Questimator scores generally correlate quite well with expert quiz scores.

4.3 Objective 2: Question Discriminative Power

To analyze the discriminative power of questions, we used a very popular approach from psychometrics, Item Response Theory (IRT) [Fox, 2010] which is used to evaluate test items (questions) and analyze test takers. We fit a two-stage IRT model to analyze questions from a quiz under investigation (Questimator quiz) against a reference quiz (expert quiz) when they are mixed together for testing.

The IRT model we use is the unidimensional dichotomous model. For a student i with ability ✓i 2 R, the probability of success on the jth question item is

where ✓i is the student ability, ↵j and βj are question parameters. ✓i is a scalar, implying single knowledge ability for the related term affects students' performance on the quiz. Naturally ↵j is also unidimensional.↵j is the question discriminative parameter, and βj is question difficulty. We selected this simple version of an IRT model to alleviate over-fitting. It can also be easily visualized and interpreted. For the IRT curve of an item (in our case, as question), ↵ specifies the curve steepness (larger ↵, steeper curve) and β shifts the curve horizontally (larger β, more to the right). We want a steeper curve (in the extreme case, a step function), so there is less randomness in the score given a student's ability.

More specifically, we considered a Bayesian IRT model with a prior of ✓i ⇠ N(0↪ 1), ↵ ⇠ N(θ↵ = 1↪ δ2↵), β ⇠ N(θβ = 0↪ δ2β ). θ↵ is set to be larger than 0 as we would suppose the questions have some positive discrimination effect. θ↵, θβ, δ↵ and δβ can be set to reflect prior knowledge of the question items. We use MCMC to perform Bayesian inference and estimate the parameters of the model [Fox, 2010].

We fit two IRT models for each topic (i.e., each quiz mixture). We first fit one IRT model with the expert questions. We then treat the estimated student's ability ˆ ✓i↪exps as the true underlying student abilities of the tested topic. We fix ✓i = ˆ ✓i↪exps and fit another IRT model with Questimator questions, estimating only ↵ and β for the Questimator questions (Figure 3).

For "Customer satisfaction" (Pearson correlation across overall expert-Questimator question sets: 0▷465), all of the questions have positive discrimination (↵ > 0), and a fair amount have relatively large ↵s ( steep sigmoid curve). On the other hand, for "Elasticity (physics)" (correlation: 0▷083), the questions have lower discriminative power (smaller ↵s). Few have negative discrimination coefficients (↵ < 0).

Table 1 shows the average ↵ parameters values across the questions for each topic, both for the existing online quizzes and our Questimator-generated quizzes. These results suggest that for many topics Questimator is identifying questions that have positive discriminative power. In the future, it would be interesting to use this approach to automatically refine generated questions or question generation techniques.

5 Conclusion

This paper has introduced Questimator, a system for generating formative, fact-recall questions on arbitrary topics. Our results show that our automatically generated questions are comparable to existing online quizzes on a variety of topics, and that we can generate quizzes for many topics for which no quiz currently exists. Future work will explore (i) improving the quality and the breadth of automatically created assessments, (ii) integrating it into systems for learning through testing, and (iii) utilizing additional corpora.

6 Acknowledgement

The work was supported by a CMU ProSEED grant and a Google focused research award. We also gratefully acknowledge the assistance and/or helpful feedback of our reviewers and participants fromMTurk.