# Machine learning with trinomial features

I have 100,000 students who have each answered some multiple choice questions. Given their performance I want to work out what the chances are of a particular student answering the next question correctly.

• not each student has answered every question
• the probability of getting a question correct by chance changes with each question

Can I turn this into a machine learning problem using past questions as features? If so, how should I code them up? From what I know of other ML systems (e.g. bag of words) people generally use 1 to show presence of a word and 0 to denote its absence. But in this case I would need 1 to show they got the question right, -1 if they got it wrong and 0 if they didn't answer it. Or can I just use 1 for correct, 0 for incorrect and then omit the feature if the student never answered that question?

Which algorithms are best suited for this kind of problem? I've been reading a bit about Latent Trait/ Latent Class analysis and Item Response Theory but unsure how to implement them. Using Python/Octave/Matlab.

The representation of the dataset in Zhubarb's answer below is correct btw. To make my question clearer, imagine i have been given a new question today, to which nobody knows the answer. I can see that 20 people have answered it and I can look through their exam history where i know which questions they got right and which they got wrong. I want to find out who the smartest person is so that I know who to copy but everyone has answered different questions and different numbers of questions (e.g. person 1 may have answered 20 and got 18 correct whereas person 2 has answered 12 and gotten them all correct. Person 3 has 5/5 correct but they were all quite easy questions, whereas person 4 only got 3/4 but the ones they got right were tricky).

• When a student doesn't answer a question, is it the case that he decides not to answer it? Or just some question were not presented to some students for technical reasons? – user31264 Nov 25 '13 at 22:42
• They weren't presented with them. – user2590701 Nov 25 '13 at 23:17
• Then you should put missing values instead of 0's in Zhubarb's approach. I'll elaborate on this in my answer. – user31264 Nov 25 '13 at 23:44
• Great! I look forward to it! – user2590701 Nov 26 '13 at 9:47
• This reminds me of the weighted majority algorithm. I don't know how to account for missing data in it, though; I wasn't able to find one in quick searching. – Dougal Apr 27 '15 at 5:52

As far as I understand, this is the structure of your data, where you have a closed set (size=n) of questions:

      Q1  Q2 ... Qn
S1    0   1      -1
S2    1   0       0
...  ...      ...
Sn   -1   1      -1


In that case, you may want to use a collaborative filter. Here is a light-weight introductory article. The underlying assumption of the collaborative filtering approach is that if a person A has the same opinion as a person B on an issue (answer questions / indicate preferences), A is more likely to have B's opinion on a different issue x than to have the opinion on x of a person chosen randomly.

This necessitates the definition of a similarity measure. You can define these between Questions (Q) or Students (S). The commonly used ones are cosine similarity or Pearson correlation. Here is a comprehensive list.

As long as you don't have hundreds of millions of observations, (hence performance is not an issue), coding this in whatever language should not be a big issue.

• Thank you for this. Two questions come to mind: 1. will this approach still hold when the data is relatively sparse? I have > 100 questions and the most anyone has answered is ~40, with many people only answering ~10 or fewer. 2. How will this approach help me to rank the students? I can see that it'd let me group people, but how do I decide who, out of everyone, is most likely to get the next question right? As if I were wanting to cheat on a test and I wanted to know who to trust when I myself don't know the answer. – user2590701 Nov 25 '13 at 23:17
• Yes, this should work with sparse data sets but I would do some more research on it. You would have to know what the next question is before predicting who is most likely to get the next question right. If you do not know what the next question, I guess you can just choose whoever has answered the most questions correctly up to that point. – Zhubarb Nov 26 '13 at 8:23
• But how do I make that choice? How do I choose between someone who got 6/6 correct and someone else who got 8/9? – user2590701 Nov 26 '13 at 9:44
• Hmm, that is a different story. The thing that would make the most sense is to use a Bayesian prior like this: andrewgelman.com/2007/03/21/bayesian_sortin – Zhubarb Nov 26 '13 at 9:59