BKT-POMDP: Fast Action Selection for User Skill Modelling over Tasks with Multiple Skills

Nicole Salomons, Emir Akdere, Brian ScassellatiIJCAI 2021 · DOI

TL;DR

This paper introduces BKT-POMDP, a novel system that efficiently models a user's mastery of multiple skills simultaneously, even when individual tasks test several skills at once. By adapting Partially Observable Markov Decision Processes (POMDPs) with Bayesian Knowledge Tracing (BKT), BKT-POMDP intelligently selects tasks to maximize learning and skill estimation, outperforming traditional methods in both simulated and real-world experiments.

What Problem Does This Paper Address?

Intelligent Tutoring Systems (ITS) aim to personalize education by modeling a student's knowledge. A key challenge is accurately assessing a student's proficiency across various skills. Traditional ITS often assume a one-to-one mapping between a task and a single skill, which is unrealistic. Many real-world tasks, like solving a math problem or assembling a circuit, require the application of multiple skills concurrently. Existing methods struggle to efficiently select tasks that provide the most information about a student's mastery of these multiple, often interdependent, skills. This leads to slower learning and less accurate skill models. The paper addresses this by proposing a method that can handle multi-skill tasks and actively select the best task to maximize the information gained about the user's skill state.

Methods

The core of the proposed system, BKT-POMDP, combines two established techniques:

  • Bayesian Knowledge Tracing (BKT): This is used to model the probability of a user mastering a skill. BKT updates a user's skill mastery probability based on whether they answer a question correctly or incorrectly, considering factors like guessing and slipping.
  • Partially Observable Markov Decision Process (POMDP): POMDPs are a framework for decision-making in situations where the true state of the world is not fully known. BKT-POMDP adapts POMDPs to the context of skill modeling. Instead of dealing with an exponential number of possible "true skill states," BKT-POMDP operates on a "belief state" – a vector representing the probability of mastering each skill.

The novelty lies in how these are integrated:

  • Action Selection: BKT-POMDP selects tasks (actions) that are expected to minimize the uncertainty in the user's skill belief state. This is achieved by maximizing the "information gain" from the observation of the user's performance on the task.
  • Reward Function: The reward is defined not by the current state, but by the increase in certainty about the user's skill state from one time-step to the next, measured using Kullback-Leibler Divergence (KLD).
  • Belief Update: When a task is completed, BKT is used to update the belief state for each skill independently. The system accounts for observations (correct, incorrect, or skill not tested) and uses BKT's probability of guessing and slipping.

The system can also be extended to account for learning during the interaction by modifying the reward function to encourage skill acquisition.

Datasets

The paper evaluates BKT-POMDP using three experimental setups:

  1. Simulation: Simulated users, skills, and tasks were generated. This allowed for extensive testing and comparison against an "optimal" policy that has perfect knowledge of the user's true skill state.
  2. Real-world Task (Electronic Circuits): Participants completed tasks involving building electronic circuits using "Snap Circuits." This provided a more realistic evaluation of the system's ability to model skills in a complex, multi-skill domain.
  3. Learning Simulation: A simulated environment was used to evaluate the system's ability to promote learning, not just skill estimation.

No new benchmarks were introduced; rather, existing concepts and simulated environments were leveraged.

Key Insights and Ideas

  • Multi-skill tasks are the norm, not the exception: The paper convincingly argues that assuming one-to-one skill-task mapping is a significant limitation in current ITS.
  • Information gain is key for efficient learning: By actively selecting tasks that maximize the reduction in uncertainty about the user's skills, BKT-POMDP learns faster than random or heuristic approaches.
  • POMDPs can be made tractable for skill modeling: By shifting from state-space to belief-space, the computational complexity is significantly reduced, making online decision-making feasible.
  • Flexibility for different goals: The framework's ability to adapt its reward function to either maximize skill estimation or promote learning highlights its versatility.

Key Results

  • Simulation Experiment: BKT-POMDP performed almost as well as the optimal policy in estimating user skill states, significantly outperforming Random and Hand-Crafted policies in terms of speed and accuracy.
  • Electronic Circuit Experiment: BKT-POMDP again showed strong performance, closely following the optimal policy and significantly outperforming baseline policies in modeling user skills in a real-world, multi-skill task.
  • Learning Simulation Experiment: When adapted for learning, BKT-POMDP effectively selected tasks that led to faster mastery of skills compared to baseline policies.

Limitations and Future Work

  • Skill Independence Assumption: The current BKT-POMDP formulation assumes skills are independent. While the paper notes this can be relaxed, it would increase computational complexity. Future work could explore more sophisticated models for skill interdependence.
  • Computational Cost: While more tractable than traditional POMDPs, the system's performance might still be a concern for very large numbers of skills or complex task structures.
  • Generalizability: While tested on circuits, further validation across diverse domains would be beneficial.
  • Learning during interaction: The paper acknowledges that the initial model assumes no learning during the interaction, but then presents an extension. Further research could explore more nuanced models of learning that interact with skill estimation.

Summary updated

BibTeX
@inproceedings{salomons2021bkt,
  author = {Nicole Salomons and Emir Akdere and Brian Scassellati},
  title = {{BKT-POMDP: Fast Action Selection for User Skill Modelling over Tasks with Multiple Skills}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/583},
}
Figure