Personalized Mathematical Word Problem Generation

1 Introduction

Word problems are notoriously difficult for children and adults alike [Verschaffel, 1994]. This phenomenon is not always related to mathematical understanding; in fact, many people find word problems much more difficult than the corresponding symbolic representations. Children have been reported to perform up to 30% worse on word problems than on corresponding algebraic equations [Carpenter et al., 1980]. Multiple studies have conjectured that this is caused by language understanding, conceptual knowledge, discourse comprehension, and other aspects required to build a mental representation of a word problem [Cummins et al., 1988; Schumacher and Fuchs, 2012].

Moreover, many students find word problems artificial and irrelevant to their lives [Ensign, 1996]. This perception is known to be altered by introducing individual interest in a

AdamM. Smith

University of Washington amsmith@cs.washington.edu

Zoran Popovi´c

University of Washington zoran@cs.washington.edu

context of a word problem [Renninger et al., 2002]. Many researchers have found that personalizing word problems raises understanding and engagement in a problem solving process, which, in turn, increases children's performance [DavisDorsey et al., 1991; Hart, 1996]. However, personalizing a progression of word problems is impractical in a textbook, and would place unreasonable burden on teachers, who would need to maintain awareness of each student's interests.

According to observations above, an ideal pedagogy might involve an individually crafted progression of unique word problems that form a personalized plot. Educational scaffolding of such a progression should be able to vary multiple aspects of a word problem individually. Such aspects should include but are not limited to: concepts of a mathematical model, plot complexity, discourse structure, and language richness. Moreover, problem personalization should rely on the students' own preferences, and ideally should generate word problems automatically according to their requirements.

In this work, we present a system for automatic personalized word problem generation from general specifications. In our system, word problem generation is defined as a constrained synthesis of labeled logical graphs that represent abstract plots. The constraints are given by a tutor and a student independently as a set of mathematical and narrative requirements. Our system has the following properties:

• It is automatic: a mathematical model, a plot, and a discourse of a word problem are generated automatically from general specifications.
• It is personalized: students can set preferences for a problem's setting, characters, and their relationships.
• It is sensible: we enforce coherence in a synthesized plot using a novel technique called discourse tropes.
• It is fit for scaffolding: varying requirements to different layers of a word problem enables a tutor to scaffold a unique educational progression.

Synthesis of logical graphs is implemented with answer-set programming (ASP), a logic programming paradigm, wellsuited for exploration of a huge space of possible models under declarative constraints [Gebser et al., 2012]. The technical novelty of this approach lies in (a) application of ASP to a novel domain, and (b) using a relatively underexplored saturation technique [Eiter et al., 2009] to solve the universally quantified problem of graph generation with discourse tropes.

The system also includes a natural language generation (NLG) module for generating a textual representation of a synthesized logical graph. It is built according to the classic guidelines of NLG systems [Reiter and Dale, 1997]. To reduce the impact of poor language clarity on problem complexity, the system includes an algorithm for unambiguous and non-repetitive reference resolution in problem text.

This paper makes the following contributions:

• We define the problem of personalized word problem generation from tutor and student requirements (§3.1).
• We formulate plot generation of a word problem as constrained synthesis of labeled graphs in ASP (§4).
• We build a system of discourse tropes, designed to enforce semantic coherence in a synthesized plot. We formulate the problem of graph synthesis with discourse tropes as an NP NP problem, and present its encoding in ASP using the saturation technique (§4.4).
• We present a method for translating abstract problem plots into unambiguous textual representations (§5).
• We report an evaluation of generated problems by comparing human judgements with textbook problems (§6). Our problems have slightly more artificial language, but they are generally comprehensible, and as solvable as the textbook problems.

2 RelatedWork

Problem generation

Automatic problem generation for various educational domains has been studied since the mid-1960s [Wexler, 1968]. Recently it has gained new interest with novel approaches in problem generation for natural deduction [Ahmed et al., 2013], algebraic proof problems [Singh et al., 2012], procedural problems [Andersen et al., 2013], embedded systems [Sadigh et al., 2012], etc. All of them apply a similar technique: they first generalize an existing problem into a template, and then explore a space of solutions that fit this template. However, the specific approaches vary. Ahmed et al. build templates automatically, Andersen et al. and Singh et al. do it semi-automatically, and Sadigh et al. write templates manually. Our system builds templates automatically w.r.t. the set of requirements, provided by tutors and students.

The underlying search space for possible problem models is usually explored with logical reasoning and exhaustive search, as opposed to combinatorial model space exploration in our approach. Andersen et al. [2013] use a state-of-the-art code coverage toolkit that is built on a SMT-based constraint solver. In this way, their approach is similar to our usage of ASP solvers for space exploration. However, the specific application of solvers to a new subject domain often requires significant technical insight, such as the usage of disjunctive ASP for enforcing narrative constraints for our domain.

In the word problem domain, the most common automation approach is a database of worksheets with templates, prepared in advance. This approach has proved itself valuable for assessment, but its personalization level is insufficient for engaging education. Deane and Sheehan [2003] built one of the rare projects that performs automatic word problem generation. They focus on natural language generation using Frame Semantics [Fillmore, 1976] with the standard NLG architecture introduced by Reiter and Dale [1997], and explore distance/speed word problems as an example domain. Our work builds upon the same architecture for NLG, but it also includes automatic generation of the word problem logic.

Declarative content generation using ASP

A number of systems have explored procedural content generation (PCG) via declarative specification of desired properties and constraints. Tutenel et al. [2009] describe a rulebased interior generation system for building design systems. Brain and Schanda [2009] present a declarative Warzone 2100 map generator. Smith et al. [2012] generate levels for an educational puzzle game. Many of such projects use ASP as a paradigm for declarative specification of content constraints, and rely on state-of-the-art ASP solvers for combinatorial model space exploration [Smith and Mateas, 2011].

Our system also uses ASP for automatic generation of a word problem. However, it also pushes the approach further, using a saturation technique for automatic verification of a universally quantified property. Smith et al. [2013] productively applied this technique in puzzle generation where they used universally quantified constraints to require key concepts across all possible puzzle solutions.

3 Overview

This section defines the problem of personalized mathematical word problem generation and gives a general overview of our solution at a high level. We describe our implementation in details in §4 and §5. Throughout the paper, we use the following simple addition problem as our running example:

Example 1. Knight Alice has 30 chalices. Dragon Elliot has 9 chalices. Alice slays the dragon, and takes his chalices. How many chalices does she have now?

3.1 ProblemDefinition

The word problem generation procedure takes as input a set of requirements R to the problem and produces as output a textual representation of the problem. Out of many requirements that a progression designer would want to include in the set R, we study two requirement classes that define pedagogical and narrative constraints on the generated problem: tutor requirements RT and student requirements RS.

Tutor requirements provide pedagogical constraints on the problem's mathematical model. They vary from general constraints ("Should include multiplication") to equation patterns like "x = ?+6 × ?", where "?" stands for any subexpression. One might imagine more complex requirements like constraining any solution to include certain steps [Smith et al., 2013].

Student requirements provide personalized narrative constraints on the problem plot according to the student's literary preferences. Student requirements can be of three kinds:

• Setting requirements - define the literary setting of the problem plot, e.g. "Science Fiction," "Fantasy."
• Character requirements - define characters to be included in the plot, along with their names and genders.

• Relationship requirements - define narrative relationships between the characters, e.g. "Amanda and Billy are friends." The word problem plot should explicitly showcase these relationships, and should not include any plot elements that logically contradict these relationships.

The output of the system is a textual representation of the word problem. Its plot and mathematical model should satisfy all the requirements in R.

3.2 Architecture

Figure 1 shows the architecture of our solution to the word problem generation problem. The process consists of two phases: logic generation and natural language generation.

Logic generation

The first phase constructs a logical representation of a word problem plot, given the requirements R. It builds the mathematical and the narrative layers of a word problem. The result is a logical graph of actors, actions, and entities.

The system starts with equation generation (§4.2). It builds a mathematical model of the problem (an abstract equation E), taking into account tutor requirements RT .

Given a specific equation E, the system generates a problem plot (§4.3, §4.4). This involves finding setting-dependent interpretations for every variable in the equation E, according to the setting in the student requirements RS. Plot actors and actions, generated from the ontology according to the rest of the requirements RS, complete the logical graph of the word problem. At this step the generator also gives concrete values to any constants present in the equation E according to the constraints of their setting-dependent logical types.

Natural language generation

The NLG phase takes a generated logical graph, and realizes it into a concrete textual representation (§5). First, it makes use of primitive sentence templates that form a placeholder for the word problem text. The language produced by such templates is unnatural: it is repetitive, every entity is referenced identically every time it appears, and every sentence describes exactly one action. Thus, the rest of the NLG phase is a post-processing of the template-generated text to make the generated language more natural, before passing it to the surface realizer to produce technically valid English.

At the sentence ordering step, the sentences produced by templates are ordered into a linear narrative according to temporal and causal relationships between the sentences.

At the reference resolution step, every entity reference in the text is realized into its textual representation. Elements of representations include pronouns, articles, type determiners (knight, dragon), etc. We present a reference resolution algorithm that finds the shortest unambiguous non-repetitive representation for every reference, given its discourse context.

4 Logic Generation

We use ASP to implement the logic generation phase of the process. ASP is a logic programming paradigm where programs declaratively describe a set of models, called answer sets. In this section, we describe our usage of ASP for word problem generation. We start with a general description of ASP, and then proceed to explanation of logic generation.

4.1 Answer-set programming

In ASP [Gebser et al., 2012], programs are composed of facts and rules in a first-order logic representation (syntactically similar to Prolog). After propositionalization of this program (called grounding), answer set solvers search the space of truth assignments associated with each logical statement. Each satisfying solution, called an answer set, is a set of selfconsistent statements identifying a different possible world.

Conventionally, a program in ASP consists of three parts that correspond to three different types of rules. The "Generate" part consists of choice rules. They allow the solver to guess facts that might be true. The "Define" part consists of deductive rules. They allow the solver to deduce new facts from the established ones. The "Test" part consists of integrity constraints. They forbid solutions that have certain properties. These three parts together define a general formulation of a problem, called a general problem encoding. It is later combined with a specific problem instance (a set of facts that describe input data), and passed to the solver.

4.2 Equation generation

In this section, we describe the equation generation phase in ASP. It takes tutor requirements RT as a problem instance, and generates an equation E that satisfies constraints in RT .

Example 2. The set of requirements R for our running example in ASP syntax. Line 2 shows a tutor requirement.

1 require_setting(fantasy). 2 require_math(plus(any, any)). % "? + ?" subexpression 3 require_character(cAlice, ("Alice", female)). 4 require_character(cElliot, ("Elliot", male)). 5 require_relationship(adversary, cAlice, cElliot).

The ASP formulation of equation generation follows the conventional approach, described in §4.1. The key idea is to encode an equation E as an expression tree. The encoding first guesses a tree shape (of given maximal size) and an assignment of mathematical operators to internal binary nodes. Then it deduces whether every mathematical requirement in RT is covered by some subexpression of the guessed tree. Finally, it forbids the solutions that do not cover all of the requirements in RT or do not represent a valid equation.

Example 3. One of many possible answer sets that represent our running example is shown below, along with its graphical representation as an expression tree. The tree has five nodes, labeled 1 through 5. The subtree that covers a tutor requirement plus(any, any) from Example 2 is highlighted.

=1

4.3 Plot generation

Given an equation E, the following phase of logic generation synthesizes a word problem plot that models E. A plot is described with an ontology that consists of types, relations, and discourse tropes. A logical graph of a word problem instance consists of entities that are annotated with ontology types, facts that are annotated with ontology relations, and connectives that are annotated with discourse tropes. We first give a formal definition of entities and facts in a logical graph, and describe their meaning. We defer the discussion of discourse tropes and connectives to §4.4.

Definition 1. A logical graph G is a tuple 〈E, F, C〉 where:

• E is a set of entities. Every entity e ∈ E has a corresponding ontology type τ, denoted e: τ. Types form a hierarchy tree: every type τ except for the root has a parent type par(τ). We write τ ≼ τ ′ to denote that τ is a subtype of τ ′ .
• F is a set of facts. Every fact f ∈ F has a corresponding ontology relation R = relation(f). Every relation R has a set of named arguments args(R). For a fact f ∈ F in a logical graph G, every argument a ∈ args(relation(f)) is associated with an entity e ∈ E. We denote this as f = R(a1 = e1, . . . , an = en) or simply f = R(e1, . . . , en).

Facts are required to type-check w.r.t. their associated relations. Each relation argument (aj : τ) ∈ args(R) is annotated with its required ancestor type τ. The corresponding entities ej : τ ′ in the fact instances of this relation should have τ ′ ≼ τ .

• C is a set of temporal (T) and causal (C) connectives. A connective c ∈ C is a tuple 〈t, f1, f2〉, where tag t ∈ {T, C}.

Example 4. In our example, G consists of the following sets:

E = {k1, d1, ck, cd, cu} where: k1 : TKnight d1 : TDragon ck, cd, cu : TChalice F = {ownsk, ownsd, ownsu, slays, acq, total, unk} where: ownsk = Owns(owner = k1, item = ck) ownsd = Owns(owner = d1, item = cd) slays = Slays(slayer = k1, victim = d1) acq = Acquires(receiver = k1, item = cd) total = TotalCount(total = cu, count1 = ck, count2 = cd) ownsu = Owns(owner = k1, item = cu) unk = Unknown(unknown = cu) C = {〈T, ownsk, slays〉, 〈T, ownsd, slays〉, 〈C, slays, acq〉}

Some of the relations R in the ontology are annotated with their corresponding mathematical operations. We say that a logical graph G models an equation E, if its subgraph generated by such operations is isomorphic to the expression tree of E. For example, the relation TotalCount represents an operation total = count1 + count2 over its arguments. This operation is isomorphic to E, hence G models E.

We describe the ontology with ASP facts like:

% Type TWarrior with par(TWarrior) = TPerson belongs to a fantasy setting. type(setting(fantasy), t_warrior, t_person). % Slays(slayer : TWarrior, victim: TMonster) belongs to a fantasy setting. relation(setting(fantasy), p_slays(t_warrior, t_monster)). % Arguments slayer and victim in Slays relation can only be adversaries in RS. only_relationship(p_slays, adversary(1, 2)). %TotalCount(total : TCountable, count1: TCountable, count2: TCountable) relation(setting(common), p_total_count(t_countable, t_countable, t_countable)). math_skeleton(p_total_count, eq(1, plus(2, 3))).

We say that G fits a set of student requirements RS, if (a) every type and relation in G are either setting-neutral, or belong to a setting from RS, (b) every character in RS corresponds to a distinct entity e ∈ E, and (c) facts f ∈ F that include character entities as arguments do not violate relationship requirements fromRS semantically.

The goal of plot generation phase is: given an equation E, student requirements RS, and an ontology, generate any logical graph G from types, relations, and tropes in the ontology, such that it models the equation E, and fits the requirements RS. In ASP, we solve this problem using a generalization of equation generation technique from §4.2, sketched below. We first guess the graph topology, then deduce whether it typechecks w.r.t. the ontology, and whether it models the equation E, and then forbid graphs that do not fit the requirements RS.

% Guess a single type for each entity. 1 { entity_type(E, T): concrete_type(T) } 1 :- entity(E). instanceof(E, T1) :- entity_type(E, T), subtype(T, T1). % Guess a relation and an assignment of typed arguments for each fact. 1 { fact_relation(F, R): relation(R) } 1 :- fact(F). 1 { fact_argument(F, K, E): instanceof(E,T) } 1 :- fact_relation(F, R), K = 1..@arity(R), argument_type(R, K, T). % Deduce whether a logical graph models an equation. models(Eq, F) :- fact_relation(F, R), math_skeleton(R, S), shape_matches(Eq, F, S). shape_matches(Eq, F, S) :- . . . %Deduce inductively from arguments. % Forbid solutions that do not model the required equation. :- equation(Eq), #count { F: matches(Eq, F) } == 0.

The main part of the deduction is the inductive verification that the graph topology, guessed in the first section of our ASP program, models the equation E. For that, the encoding recursively follows the argument edges in E and in the mathematical operations of ontology relations in parallel. This process is denoted by the predicate shape matches(Eq, F, S) above. Here Eq denotes the equation E, F denotes the current fact f under verification, and S denotes the skeleton of the mathematical operation against which f is being matched. Our encoding implements shape matches as follows:

1. For each numbered placeholder k in the skeleton S, recursively follow the paths from the root of S and the root of E in parallel, arriving at the equation argument node nk ∈ E. Fail if the paths in S and E are not isomorphic.
2. Map each equation argument nk to the kth plot argument ek of the fact f = R(e1, . . . , en) under verification.
3. Fail if the deduced mapping between E and E is noninjective or is not a function, succeed otherwise.

Example 5. Matching the skeleton eq(1, plus(2, 3)) of the relation TotalCount against the nodes of equation E from Example 3, we obtain the following corresponding equation nodes: n1 = 3, n2 = 4, n3 = 5. They are respectively mapped to the arguments of the fact "total": n1 → cu, n2 → ck, n3 → cd. This mapping is functional and injective, hence the logical graph G from Example 4 models the equation E.

Multiple integrity constraints forbid insensible logical graphs (not shown in the snippet above). They require the graph to be connected, to include an entity for every character in RS, to comply with character relationships, to have a single "unknown" value (that the students recover by solving the problem), to use types and relations only from the required setting or from common life, etc.

4.4 Discourse tropes

Relying on the ontology type system is sufficient for generating plausible logical situations, but insufficient for generating engaging plots. Word problems are primarily short stories, and every short story needs a developed narrative. This aspect is even more important for our setting of personalized word problems, where the story is centered around student-defined characters and their relationships.

An ASP solver, when presented with an encoding above, generates any logical graph G that fits the requirements, models the equation, and is logically sound w.r.t. the ontology type system. However, requiring G to represent a coherent narrative is a more challenging problem. Consider the logical graph in Example 4. One might ask, why did the solver not choose any subset of F instead? Or why did the solver not add a fact slays′ = Slays(slayer = d1, victim = k1)? In both of these situations, the resulting graph would still be logically sound, but it would either lack plot-driving details, or include unnecessary statements. To forbid such answer sets, we describe such narrative constraints in discourse tropes.

Definition 2. A discourse trope D is a constraint on a logical graph G of form ∀⃗x ⊂ E [Φ(⃗x) ⇒ ∃⃗y ⊂ E : Ψ(⃗x, ⃗y)]. Here Φ,Ψ are quantifier-free formulas that make use of ontology relations as logical predicates. ⃗x, ⃗y are groups of distinct entities in G that participate in the constraints Φ, Ψ.

A subgraph of G generated by facts corresponding to predicates in Φ, Ψ and their arguments is called an instance of D if both D and Φ(⃗x) hold on this subgraph.

Example 6. A fantasy trope "A warrior slays a monster only if the monster has some treasures" is described logically as:

D = ∀ w, m ∈ E [Slays(w, m) ⇒ ∃ t ∈ E : Owns(m, t)]

In Example 4 a subgraph {slays, ownsd} is an instance of D. The snippet below shows D in our ontology syntax:

discourse( forall(m, w), premise(p_slays(w, m)), exists(t), conclusion(p_owns(m, t)), temporal(p_owns(m, t), p_slays(w, m)) ).

The syntax describes arbitrary first-order logical formulas of the form above with predicates forall, exists, and, etc. Distinctly named variables are assumed to match distinct entities. Expressions premise and conclusion represent constraints Φ and Ψ, respectively. The last argument of discourse predicate instructs a solver to generate connectives C between some pairs of facts when they belong to an instance of this trope in G. These connectives are later used by the NLG phase to order problem sentences (§5).

Our plot generator takes the ontology discourse tropes into account by requiring every fact in the generated logical graph G to either be mathematical or belong to an instance of some discourse trope. Thus, any solution that does not represent a coherent literary narrative will be forbidden by the solver.

Saturation technique

Verifying a discourse trope on a logical graph is non-trivial. ASP is well-suited for solving search problems with existentially quantified goal conditions, which lie in the complexity class NP. However, the problem of plot generation with discourse tropes has a ∃∀∃ structure. Here the first quantifier represents a search for a graph G that satisfies both the problem encoding and the set of tropes in the ontology. The last two quantifiers represent validation of G w.r.t. D according to Definition 2. A na¨ıve encoding of such a problem in ASP would cause an exponential blowup in grounding time.

In our setting, the innermost ∃ quantifier is expanded during grounding using skolemization [Benedetti, 2005]. It causes only a polynomial blowup in grounding time, because every trope in our ontology has at most 3 existentially quantified variables ⃗y. After that, we are left with a 2QBF problem, which lies in the complexity class NP NP . In order to express a 2QBF problem in ASP without an exponential blowup, we leverage an extension of classic ASP with a special fourth rule type in a relatively underexplored saturation technique.

Disjunctive rules, not supported by many ASP solvers, include disjunction in rule heads, allowing the solver to deduce any of the facts in the head, given the body. The solution is then chosen according to subset minimality semantics: no answer set is emitted as a solution if any of its subsets is also a valid solution [Gebser et al., 2013].

Consider for simplicity the problem of searching for a graph G, constrained with a single trope ∀⃗xΦ(⃗x). In the snippet below, we briefly demonstrate the saturation technique for this problem (see [Eiter et al., 2009] for a detailed overview):

1 % Example discourse trope: ∀a, b ∈ E : Owns(a, b) ∧ Acquires(a, b) 2 discourse(forall(a,b), premise(owns(a,b), acquires(a,b))). 3 % Assign each formal variable V ∈ {"a", "b"} to some entity e ∈ E. 4 bind(V, E): entity(E) :- var(V). 5 sat(Xs, F) :- . . . %Deduced if Φ(⃗x) holds under the current assignment ⃗x. 6 valid :- discourse(Xs, F), sat(Xs, F). 7 bind(V, E) :- valid, var(V), entity(E). 8 :- not valid.

We want to enforce the property ∀⃗x Φ(⃗x). For that, we nondeterministically choose an assignment of formal variables ⃗x to a subset of entities, using a disjunctive rule in line 4. If the assignment is a valid counterexample to Φ(⃗x), valid will not be deduced, and the integrity constraint in line 8 will eliminate this answer set. On the other hand, if the assignment is not a counterexample, line 7 will saturate the answer set, including every possible bind(V, E) fact into it. According to subset minimality semantics, a valid answer set is emitted only if all of its subsets are not valid. However, for a saturated answer set, every other answer set is its subset. Thus, the solver will emit a solution only after a thorough check of all other variable assignments, which is equivalent to enforcing a ∀⃗xΦ(⃗x) property.

5 Natural Language Generation

After generating a logical graph of a problem, our system realizes it into a textual representation. First, it approximates the text with sentences produced using primitive templates, and then it orders sentences produced by templates, resolves entity references unambiguously and non-repetitively, and realizes the result into valid English.

Primitive Templates

Figure 2 shows an example of a primitive template. It matches a subset of facts in F, and produces a syntactic tree of a sentence, where some NP (noun phrase) subtrees are replaced does with entities they describe. As a result, we obtain a first approximation to the word problem text - an unordered bag of sentences S with somewhat unnatural, repetitive language.

Figure 2: A primitive template that matches 2 facts from F.

Sentence ordering

The key idea in turning the sentences S into a linear narrative is leveraging connectives C that were added to G from discourse tropes during plot generation. Each connective c ∈ C specifies a temporal or causal relationship between two facts f1, f2 ∈ F. Consequently, corresponding sentences s1, s2 ∈ S that describe f1, f2 should follow the same ordering in a narrative. The set C thus defines a partial ordering on S. Any total ordering of sentences in S that satisfies this partial ordering constitutes a valid narrative.

Example 7. After this phase, the template-generated problem text of our running example turns into the following text. The subtrees are marked with corresponding entities from E.

"[Knight Alice]k1 has [30 chalices]ck . [Dragon Elliot]d1 has [9 chalices]cd . [Knight Alice]k1 slays [Dragon Elliot]d1 , and takes [9 chalices]cd . How many [chalices]cu does [knight Alice]k1 have?"

Reference resolution

At the reference resolution step, we convert every entitymarked text node into some textual representation for this entity. Our method is inspired by classic NLG guidelines [Krahmer and Van Deemter, 2012], and is based on type attributes.

Every type τ has a set of named attributes. We divide them disjointly into implicit and explicit, denoted imp(τ) and exp(τ). Every textual reference to e: τ implicitly or explicitly mentions all attributes in imp(τ) to the reader. For example, gender is an implicit attribute for sentient entities: once e is introduced, every reference to it preserves the memory of its gender to the reader. Names, types, and quantities can be mentioned only explicitly, and hence belong to exp(τ).

Given a reference to an entity e : τ , a subset of its attributes A ⊂ exp(τ ), and its discourse context, we can generate a textual representation of e that mentions exactly the attributes in A∪ imp(τ) to the reader. The representation also depends on some contextual properties, e.g. whether e is a subject or an object in the sentence, or whether e is a definite reference (i.e. has it been introduced before). For example, A = ∅ represents a pronoun only if the reference is definite.

The key idea of our reference resolution algorithm is to choose the smallest set of attributes for every reference that makes it unambiguous w.r.t. the preceding discourse. For every reference to e: τ after its introduction, the algorithm enumerates the subsets of exp(τ), and chooses the smallest one that does not share at least one attribute value with other entities in the preceding discourse. To avoid repetition, we often choose a second or third unambiguous representation instead.

Example 8. Consider a reference to cd on the third line of Example 7. The algorithm first checks A = ∅, which corresponds to the pronoun representation "them." However, it is ambiguous because imp(cd) = {plural}, and the value of this attribute is equal to the value of the same attribute of a previously processed reference to ck. In several iterations, the algorithm finds an unambiguous subset A = {owner, type}, corresponding to the representation "[d1]'s chalices."

6 Evaluation

In this work, we chose not to evaluate the personalization aspect of our system, since a complete study of its pedagogical value on the students is beyond the scope of this paper. Instead, we evaluate our generation techniques by assessing the content of the produced word problems w.r.t. its language comprehensibility and its mathematical applicability.

User Study

We prepared an ontology of 100-200 types, relations, and tropes in three literary settings: "Fantasy," "Science Fiction," "School of Wizardry." This one-time initial setup of the system took about 1-2 person-months. From it, we randomly generated 25 problems in the domains of age, counting, and trading, with the solutions requiring 2-4 primitive arithmetic operations. We sampled the problems with sufficient linguistic variability to evaluate the overall text quality. Although the ASP solving has exponential complexity, every problem was generated in less than 60 s, which is a feasible time limit for realistic problems within our range of interests.

We selected 25 textbook problems from the Singapore Math curriculum [Publications, 2009] with the equivalent distribution of complexity (solution lengths), and conducted two studies using Mechanical Turk. Study A assessed language aspects of the problems. It asked the subjects 4 questions (shown in Figure 3) on a forced-choice Likert scale. Study B assessed mathematical applicability of the problems. It asked the subjects to solve a given problem, and measured solving time and correctness. For both studies, each problem was presented to 20 different native English speakers (1000 total).

Our experimental hypotheses were: (a) the generated problems should be rated equally or slightly less comprehensible than the textbook problems (by the nature of our problems being artificial), (b) the language of our problems should remain generally comprehensible with possible slight oddities (with a mean > 3 on the forced-choice Likert scale converted to 1-4), and (c) problems should remain solvable with no statistical difference from the textbook problems.

Figure 3 presents the results of the studies A and B on the aggregated dataset of 50 problems. The hypotheses (a) and (b) were confirmed: the judges rated the textbook problems significantly better than our problems across all 4 questions with moderate effect sizes (for the most general Q1 we had χ2 = 193.52, p < 0.001, V = 0.44), but our problems were generally comprehensible with occasional oddities (mean rating ranged from 3.36 to 3.50). The original results invalidated hypothesis (c): participants correctly solved textbook problems significantly more often than the generated problems (χ2 = 9.474, p < 0.005, V = 0.01). However, since a Cramer's V effect size of 0.01 is considered very small, we conjectured that the result was driven by a handful of problems with poor nondeterministic choices during the NLG phase (§5). To validate this hypothesis, we excluded outlier problems from the analysis (those with a mean answer < 3 to any Study A question). As Figure 3 shows, there were only 4 outliers out of 25 generated problems. A new analysis of the resulting filtered dataset found no statistically significant difference in solving performance (χ2 = 2.439, n.s.). The participants solved textbook problems correctly 78% of the time, compared to 73% of the time for generated problems. There was also no statistically significant difference in the solving times for generated (mean = 232 s, SD = 367.2) and textbook (mean = 220 s, SD = 378.7) problems (t(918) = 0.473, n.s.). The mean Q1-4 rating of non-outlier generated problems was 3.45-3.65, as compared to 3.90-3.92 for textbook problems.

Study B also exposed two generated problems with clear language but mostly incorrect solutions (g18 and g23). This happened because of incomplete semantics of the participating ontology relations (e.g. an intermediate result assuming less than 24 hours/day). One way to resolve it is a richer ontology with commonsense background knowledge such as Cyc [Lenat, 1995], which is an important area of future work.

Examples

Figure 4 demonstrates how various problem requirements correspond to different aspects of word problem complexity. It shows a series of generated word problems, where each step changes one requirement at a time, thereby producing a different problem with respect to a single complexity aspect. The aspects are, in order: character relationships, mathematical model, literary setting, unknown value. We highlighted entity references in each sentence to demonstrate how our reference resolution impacts language clarity. This aspect, together with sentence ordering in the last two steps, demonstrates variation in linguistic complexity of word problems.

7 Conclusions and FutureWork

In this work, we defined and explored the problem of personalized mathematical word problem generation. We presented a system that focuses on synthesis of single word problems from general specifications, provided by a tutor and a student independently. Our usage of constrained logic programming and our coherence enforcement with universally quantified discourse tropes allows a tutor to define the word problem structure in the form of its abstract concepts. Word problems, as a domain with multiple independent layers of complexity, also entail a personalized approach, where students express personal preferences to the generated content. In that case, the student's engagement often overcomes the impact of semantic and linguistic problem complexity on their performance.

Automatic problem generation under individually tailored conceptual constraints could be a valuable tool for instructional scaffolding in any educational domain. Since problem generation through synthesis of labeled logical graphs is a domain-independent idea, it allows a wide spectrum of applications. For instance, replacing mathematical constraints with logical implications enables generation of language comprehension problems, notoriously confusing in elementary school. Augmenting an ontology with background knowledge enables problem generation in physics or programming. Problem generation in such domains is not only beneficial for education or assessment, but also valuable for data-driven research on the individual aspects of problem complexity. This work takes an important step towards realizing the vision of providing personalized pedagogy to support the needs of teachers and the interests of students simultaneously.

8 Acknowledgments

This work was supported by the Office of Naval Research grant N00014-12-C-0158, the Bill and Melinda Gates Foundation grant OPP1031488, the Hewlett Foundation grant 2012-8161, Adobe, and Microsoft. We also thank Roy Szeto and Robert Duisberg for helpful discussions, and the anonymous reviewers for their feedback.