Machine learning filter: How can I make a smart flash card program?

October 18, 2009 3:39 PM

Machine learning filter: How can I make a smart flash card program?

I'm writing a flash card quiz program. It records the user's history as list of triples of the form:

(timestamp, question, correct)

Where "question" is a unique identifier for the question asked and "correct" is boolean---whether or not the user answered correctly.

I want to use this history to predict which question the user is most likely to answer incorrectly, so that my program can focus on questions the user is having trouble with. Specifically, for each question, I want a function that computes the probability that it will be answered correctly if asked at the current time.

Right now I'm using domain-specific heuristics to do this, but surely there's a more principled way. I suspect the time-series aspect of this problem sets it apart from the vaguely-remembered classification techniques I saw in AI class long ago. Something that can be efficiently updated with each new answer would be nice, but is not essential---the data set is small.

What kinds of AI tools can I bring to bear on this? What terms should I even be searching for?

posted by qxntpqbbbqxl to computers & internet (7 comments total)

I don't have an answer, but Anki does what you're trying to do. Perhaps you could poke around their development forums or ask someone directly involved. Good luck!
posted by spikeleemajortomdickandharryconnickjrmints at 3:50 PM on October 18

Read up on Spaced Repetition
posted by delmoi at 4:11 PM on October 18

SuperMemo is the king of this sort of thing; I believe there are free implementations that you could examine the workings of.
posted by dmd at 5:32 PM on October 18

Lets build this up piece by piece. First, lets ignore the temporal component and just focus on the prediction task: given a particular user and knowing his success/failure on some other questions, how do you predict whether the user will get a question right/wrong. IE,

P(User gets question right | user profile)

where the user profile is unobserved but built up based on the previous questions. Your methods of solving this problem really depend on the structure of your questions. For example, if you have lots of features about your questions (Q231 is a verb conjugation question, pretitite tense, '-ar' verb, etc) then you can, for each user, train up a classifier based on those features. Look up logistic regression or SVM as candidates. For logistic regression, you'll be training a classifier of the form

P(user gets the q right) = 1 / (1+exp (user-profile dot-product question-features))

Now, you can add an temporal element by training a classifier where more recent answers get weighted higher for the purposes of fitting a classifier (ie, you try to find a user-profile vector that best predicts past answers, but you care more about it getting the recent answer right than those from long ago). A more rigorous method would involve a temporal (dynamics) model of the user-profile; look up Hidden Markov Models and Kalman Filters for inspiration.

Alternatively, if you don't want to do prediction based on the structure of the questions, you'll need some other way of tying them together -- basically, of figuring out P(Q312 = right | user who got Q251=wrong, Q512=right). You can try to use collaborative-filtering techniques -- these are commonly used to figure out which products you want based on your past preferences and other users' behavior. You can use other people's ratings to induce some features on the questions (look up low rank matrix factorizaton in the context of collaborative filtering) and then use them as features for a logistic regression model.
posted by bsdfish at 5:57 PM on October 18

Mnemosyne uses an older supermemo algorithm (spaced repitition) and is open-source if you want to take a peek (coded in python). I'm planning on using the algorithm code later and I think it's pretty readable (hell python is almost pseudocode anyway).
posted by i_am_a_Jedi at 7:02 PM on October 18

Mnemosyne also provides an anonymized 860MB data set created from item-by-item records of remembering and forgetting.
posted by Maxwell_Smart at 8:17 PM on October 18

Spaced repetition appears to be sort of an inverse of my formulation (it concerns itself with how much time should elapse between repetitions to optimally reinforce memorized concepts, while I'm trying to predict which concepts are weakest). For those interested, here's SuperMemo's description of SM-11.

bsdfish's answer is much closer to my own thinking. I do have a directed graph of semantic dependence between questions.

Mnemosyne is very interesting. My program is already in Python, so maybe I'll steal its pretty GUI.
posted by qxntpqbbbqxl at 9:19 PM on October 18