Algorithmic Exam Generation

Omer Geiger, Shaul MarkovitchIJCAI 2015

Abstract

Traditional exam composition often relies on manual expert tagging of question difficulty, creating a significant bottleneck in educational assessment. This paper presents MOEG (Model-based Exam Generation), a framework that algorithmically derives question properties by analyzing procedural solution steps. By simulating student performance across a pool of questions, MOEG optimizes exam composition to maximize the correlation between grade-based rankings and true student proficiency. Experimental results in middle-school algebra demonstrate that MOEG significantly outperforms existing baseline methods in ranking accuracy and efficiency.

Introduction

Creating an effective exam is a complex balancing act. Educators strive to design assessments that accurately distinguish between students of varying proficiency levels. However, existing "testsheet composition" systems typically treat questions as "black boxes," requiring human experts to manually assign numeric features like difficulty or estimated solving time. This manual process is time-consuming and prone to subjectivity.

The MOEG framework addresses this challenge by removing the human from the loop. Instead of relying on manual tags, the system understands the inherent difficulty of a question based on the specific cognitive abilities it tests. The primary goal is to ensure that the resulting grades provide a ranking that closely matches the "true" knowledge-based ordering of students.

The MOEG Framework

The MOEG framework is built upon three core pillars:

  1. Student Modeling: Students are represented using a "binary overlay model," where proficiency is defined as a set of mastered discrete abilities (e.g., "can distribute a negative sign").
  2. Disjunctive Action Landmarks: For procedural domains like mathematics, the system treats each question as a search graph of possible solution steps. It algorithmically identifies "action landmarks"—combinations of abilities sufficient to solve the problem. A student is modeled as "passing" a question if their mastered abilities satisfy at least one valid solution path.
  3. Optimization Algorithm: The system employs a three-phase search to compose the exam:
  4. Addition: Iteratively selecting questions that maximize the exam's utility.
  5. Swapping: Replacing questions to escape local optima.
  6. Weight Adjustment: Fine-tuning the point values assigned to questions to better differentiate between students with similar skill sets.

The "Utility" of an exam is quantified using Kendall’s $\tau$, measuring the correlation between the simulated grade-based ranking and the ideal target ranking.

Experimental Evaluation

The framework was evaluated using a dataset focused on middle-school algebra (linear equations).

  • Question Pool: A custom generator created 160 unique algebra problems by applying "complicating" operations to simple solutions.
  • Ability Set: 18 specific algebraic abilities were defined, such as term unification and moving terms across equals signs.
  • Student Population: A population of 1,000 students with varying ability distributions was simulated to test ranking accuracy.

Results and Discussion

MOEG demonstrated clear superiority over several baseline methods, including "Uniform Generate & Test" (random selection), "Weighted Generate & Test" (biased toward informative questions), and a "Diversifier" (focused on syntactic variety).

Figure 1: Performance comparison of MOEG against baseline methods over time.

As shown in Figure 1, MOEG reaches higher correlation levels (Kendall Tau) significantly faster than the baselines. The system's ability to recognize questions as logical intersections of skills, rather than just feature sets, allows it to select more informative questions. Furthermore, the inclusion of weight adjustment proved critical; by non-uniformly weighting questions, the system could better distinguish between students with overlapping but distinct skill sets.

The efficiency of the framework is also noteworthy. MOEG can achieve high ranking accuracy with relatively short exams.

Figure 3: Impact of exam length on the correlation between grades and true student ranking.

Figure 3 illustrates that while accuracy generally increases with exam length, MOEG reaches a high plateau quickly. In comparative tests, a 6-question exam generated by MOEG was found to be more accurate than a 10-question exam produced by competing methods.

Conclusion and Future Work

MOEG represents a significant step toward automated, high-quality assessment design in procedural domains. By modeling the logic of problem-solving, the system reduces the need for manual expert intervention.

However, current limitations include the assumption of independence between abilities, which are often hierarchical in practice. Future research could utilize Bayesian Networks to model these dependencies. Additionally, while highly effective for procedural subjects like math or chemistry, extending this logic-based approach to "softer" subjects like literature remains a challenge. Finally, automating the initial definition of the "ability set" from educational materials would further enhance the system's autonomy.

Summary updated

BibTeX
@inproceedings{geiger2015algorithmic,
  author = {Omer Geiger and Shaul Markovitch},
  title = {{Algorithmic Exam Generation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure