Selection Algorithms

The TutorShop Learning Management System, which was built to deploy CTAT tutors on the web, groups individual tutor instances, or "problems" (a problem is a pairing of a student interface and a model, either a behavior graph or a cognitive model), into problem sets at runtime. Each problem set has a selection algorithm that determines which of its problems will be shown to the student and in what sequence.

TutorShop has a number of built-in problem selection algorithms an author could choose from. Besides that it also allows authors to implement their own custom selection algorithms and link them to the system in one of several ways, as described below and further detailed in Interface to Custom Problem Selectors.

One factor that plays into the built-in problem selection algorithms is the number of times each problem has already been run, in case problem repeating is allowed. All built-in algorithms have a preference for selecting problems that have been run fewer times.

The built-in algorithms can be classified into 3 main groups: simple ordering algorithms, mastery algorithms, and custom algorithms.

Simple Ordering Selection Algorithms

These algorithms are based on the order of the problems in the problem set. They only choose among problems in the problem set that have not been attempted yet, or among problems that have been attempted the fewest times.

The algorithms are:

• Sequential Order: choose the first problem from the subset mentioned above.
• Random Order: choose a problem randomly from the subset mentioned above.

Mastery Selection Algorithms

These algorithms aim to select the problem that could advance the student furthest toward mastery. Mastery is hard-coded to 0.95 probability. The algorithms compute a score for each problem, which is a weighted average of the missing skill probabilities. Where a missing skill probability is the difference between the mastery level (0.95) and the current skill p-known, and the weights are given by the number of opportunities for each skill. Problems exercising skills that have already been mastered are not considered.

The computed score is further adjusted by dividing it by the number of times the problem has already been attempted plus 1 (to avoid division by zero). This gives a preference to problems that have been attempted fewer times.

The algorithms are:

• Sequential Mastery Learning - Harder First: choose the first problem from the subset of problems with the highest score,
• Sequential Mastery Learning - Easier First: choose the first problem from the subset of problems with the lowest score.
• Random Mastery Learning - Harder First: choose a problem randomly from the subset of problems with the highest score.
• Random Mastery Learning - Easier First: choose a problem randomly from the subset of problems with the lowest score.

Custom Selection Algorithms

TutorShop also provides a way for authors to customize the problem selection, by replacing the built-in ones with their own. This could be implemented either as a script running in the browser or on the same server, or an internet service running on any other server.

Tutorshop defines an API for communicating with the custom problem selection service. TutorShop sends a POST request with the student model and some data about the problems to choose from in JSON format, and the service is expected to return a JSON object containing the next problem choice using whatever strategy it implements, together with an updated dynamic student model.

The 3 types of available custom problem selection algorithms are:

• Local Selection: the custom selection algorithm is implemented as a javascript program running either in the browser or on the server. If the problem set is run with a local sequencer, the sequencer executes the script in the browser when a problem needs to be selected. If the problem set is run with the usual TutorShop sequencer, the script is executed within a sandbox on the server.

  In this case the algorithm parameters are:

  • Selection Command: the javascript function that implements the selection algorithm, which is executed when a problem needs to be selected. The function is called with the JSON parameters defined by the API as arguments, and it is expected to return a JSON object containing the information defined by the API.
  • Selection Script: the script file that implements the selection algorithm, which is loaded either by the browser or by the TutorShop server when a problem needs to be selected. The script file must define the Selection Command function.

• External Selection: the custom selection algorithm is implemented as a script running on the same server as TutorShop. The script is executed on the server when a problem needs to be selected. The script can be written in any language, and is expected to be preinstalled on the server. The command can be a binary command, or a shell command that runs a script file.

  In this case the algorithm parameters are:

  • Selection Command: the shell command that executes the script implementing the selection algorithm, which is executed when a problem needs to be selected. The command is run with the JSON parameters defined by the API given on the standard input, and it is expected to return a JSON object containing the information defined by the API on the standard output.

• Remote Selection: the custom selection algorithm is implemented as an internet service running on any server. The service is called by the TutorShop server when a problem needs to be selected, and needs to be able to respond to standard HTTP requests.

  In this case the algorithm parameters are:

  • Selection Command: the URL of the internet service implementing the selection algorithm, which is called when a problem needs to be selected. The service receives a POST request with the information defined by the API in JSON format, and it is expected to return a JSON object containing the information defined by the API as a response.

For details about the TutorShop API to custom problem selectors see Interface to Custom Problem Selectors.