How Khan Academy is using machine learning to assess student mastery • Hacker News Board

Re: How Khan Academy is using machine learning to assess student mastery

#31

Post by equark » Thu, Nov 03, 2011, 4:14 AM UTC

xenophanes wrote: post #26

ced wrote: post #21

Earlier quoted context omitted.

It doesn't sound terribly Bayesian to me. From one of his pages: However, the significance calculation makes a critical assumption that you have probably violated without even realizing it: that the sample size was fixed in advance. If instead of deciding ahead of time, “this experiment will collect exactly 1,000 observations,” you say, “we’ll run it until we see a significant difference,” all the reported significan…

Changing stopping rules after seeing the data creates bias/distortions. One does have to set the rules in advance, that's not a mistake. Consider a data set consisting of a single license plate number. (This example is from Richard Feynman.) If you set the rules in retrospect, you can go "Wow, what were the odds my one license plate would be XJKDL-2342-KE? One in a million?" But that's wrong. On the other hand if you…

Changing stopping rules is perfectly fine in a Bayesian setup. It's the likelihood principle. This is one of the central differences that arises when you condition on the data (Bayesian) rather than the parameter (frequentist).

Re: How Khan Academy is using machine learning to assess student mastery

#32

Post by ced » Thu, Nov 03, 2011, 4:16 AM UTC

xenophanes wrote: post #30

ced wrote: post #29

Earlier quoted context omitted.

Thank you for your comments - there's a lot of issues about this problem that I'm not entirely comfortable with. With that said, I'm not sure that I see the connection between what you're arguing and the significance problem in the original. What do you think of the example with the two doctors? http://lesswrong.com/lw/mt/beautiful_probability/ Changing stopping rules after seeing the data creates bias/distortions We…

Oh, I see what you mean about fixed . It's hard to generalize about all data-dependent stopping rules. I do think the one that says "If I get one conclusion, stop. If I get the other, keep trying," has got to be a bad idea! It prevents you from possibly finishing an experiment that concludes you're wrong. The possibility of not terminating seems especially problematic. But if the rule was more like "Roll 10 dice. If…

It's getting too late for me to think about statistics :) A few points:

Similarly, imagine a study of coins which had a stopping rule to stop whenever you have at least 60% heads. You'll always be able to get that result and conclude the coin is biased, even if all coins used are fair.

This is not true. Because of the law of large numbers, the probability of ever reaching the 60% decreases with time.

I do think the one that says "If I get one conclusion, stop. If I get the other, keep trying," has got to be a bad idea!

I understand what you're talking about. I see the potential for a problem. But my understanding is that Bayesian statistics isn't subject to that.

Proper Bayesian result reporting doesn't say "We believe that the coin is biased". We would rather say "The probability that this coin is biased is 60%, subject to our assumptions and model".

My feeling is that this statement is true:

If the model and assumptions are correct, then the Bayesian outcome will be true regardless of the stopping rule.

In this case: 60% of coins for which the Bayesian analyst proclaims P(biased)=0.6 WILL be biased (barring sampling variations). The stopping rule doesn't matter.

I'll try and figure out a solid explanation by tomorrow.

Re: How Khan Academy is using machine learning to assess student mastery

#33

Post by equark » Thu, Nov 03, 2011, 4:28 AM UTC

xenophanes wrote: post #30

ced wrote: post #29

Earlier quoted context omitted.

Thank you for your comments - there's a lot of issues about this problem that I'm not entirely comfortable with. With that said, I'm not sure that I see the connection between what you're arguing and the significance problem in the original. What do you think of the example with the two doctors? http://lesswrong.com/lw/mt/beautiful_probability/ Changing stopping rules after seeing the data creates bias/distortions We…

Oh, I see what you mean about fixed . It's hard to generalize about all data-dependent stopping rules. I do think the one that says "If I get one conclusion, stop. If I get the other, keep trying," has got to be a bad idea! It prevents you from possibly finishing an experiment that concludes you're wrong. The possibility of not terminating seems especially problematic. But if the rule was more like "Roll 10 dice. If…

You're stuck in frequentist thinking. "Bias" is a property of repeated sampling -- the expectation over repeated samples. But we just have one! The relevant question is what is your best guess for p, the probability the coin will be heads.

Under a uniform prior [0, 1] the posterior mean is the empirical mean. How you sample is of no consequence. The likelihood/posterior f(p|#heads, #tails) is p^(#heads)(1-p)^(#tails) regardless of how you sample. Differentiate with respect to p and you get p*=heads/total.

It is rather amusing that most statistics professors are happy to have taught their students that the sampling procedures matter while at he same time crushing the natural intuition that your decisions should be based on the data you observe not on what might have happened in a world that doesn't exist.

http://books.google.com/books?id=6oQ4s8Pq9pYC&lpg=PA18&#...

Re: How Khan Academy is using machine learning to assess student mastery

#34

Post by xenophanes » Thu, Nov 03, 2011, 5:14 AM UTC

equark wrote: post #33

xenophanes wrote: post #30

Earlier quoted context omitted.

Oh, I see what you mean about fixed . It's hard to generalize about all data-dependent stopping rules. I do think the one that says "If I get one conclusion, stop. If I get the other, keep trying," has got to be a bad idea! It prevents you from possibly finishing an experiment that concludes you're wrong. The possibility of not terminating seems especially problematic. But if the rule was more like "Roll 10 dice. If…

You're stuck in frequentist thinking. "Bias" is a property of repeated sampling -- the expectation over repeated samples. But we just have one! The relevant question is what is your best guess for p, the probability the coin will be heads. Under a uniform prior [0, 1] the posterior mean is the empirical mean. How you sample is of no consequence. The likelihood/posterior f(p|#heads, #tails) is p^(#heads)(1-p)^(#tails)…

Consider an infinite string of coin flips. Now consider a subset selected by a stopping rule to meet a particular criterion. And a different subset chosen with an N=100 criterion. The first stopping rule creates a bias: you have a non-random sample chosen to meet that criterion. The second stopping rule doesn't do that, it gets what we call a "random sample".

If someone then takes your dataset and assumes it's a random sample -- e.g. just the same as the N=100 doctor trial -- he's wrong. It's not, it's something else, and that something else is less useful.

You say "how you sample is of no consequence". But suppose your sampling method selectively throws out some data that it doesn't like. That is of consequence, right? So sampling methods do matter. Now consider a method which implicitly throws out data because some sample collections are never completed. That matters too.

Re: How Khan Academy is using machine learning to assess student mastery

#35

Post by xenophanes » Thu, Nov 03, 2011, 5:20 AM UTC

ced wrote: post #32

xenophanes wrote: post #30

Earlier quoted context omitted.

Oh, I see what you mean about fixed . It's hard to generalize about all data-dependent stopping rules. I do think the one that says "If I get one conclusion, stop. If I get the other, keep trying," has got to be a bad idea! It prevents you from possibly finishing an experiment that concludes you're wrong. The possibility of not terminating seems especially problematic. But if the rule was more like "Roll 10 dice. If…

It's getting too late for me to think about statistics :) A few points: Similarly, imagine a study of coins which had a stopping rule to stop whenever you have at least 60% heads. You'll always be able to get that result and conclude the coin is biased, even if all coins used are fair. This is not true. Because of the law of large numbers, the probability of ever reaching the 60% decreases with time. I do think the o…

FYI I edited my post to mention the issue about the coins (your first point) shortly after submitting it. I'm guessing you read the non-edited version.

> Proper Bayesian result reporting doesn't say "We believe that the coin is biased". We would rather say "The probability that this coin is biased is 60%, subject to our assumptions and model".

I'm not really sure what you're getting at here. None of the coins are biased, by premise, so they shouldn't be concluding either thing.

If you throw in "if our model and assumptions are right" then you can shift the blame (if they assumed their stopping rule was OK, or came up with a model that says it's OK). But I'm not sure how that substantively helps.

Will check back tomorrow for further comments from you.

Re: How Khan Academy is using machine learning to assess student mastery

#36

Post by Eliezer » Thu, Nov 03, 2011, 8:20 AM UTC

ced wrote: post #21

Eliezer wrote: post #19

Earlier quoted context omitted.

(Reads links.) I've been going around telling people for a while that A/B testing is non-Bayesian but I didn't realize there was an off-the-shelf solution! You need to pimp your wares more often.

It doesn't sound terribly Bayesian to me. From one of his pages: However, the significance calculation makes a critical assumption that you have probably violated without even realizing it: that the sample size was fixed in advance. If instead of deciding ahead of time, “this experiment will collect exactly 1,000 observations,” you say, “we’ll run it until we see a significant difference,” all the reported significan…

Ced, the part about the significance calculation is a problem with the A/B test, not a problem with the Bayesian bandit version.

The post you're looking for is http://lesswrong.com/lw/1gc/frequentist_statistics_are_frequ...

Re: How Khan Academy is using machine learning to assess student mastery

#37

Post by currere » Thu, Nov 03, 2011, 10:25 AM UTC

Another ingenious approach is taken by chesstempo.com, a chess training site. Just as in chess itself the ratings of players are determined by pairwise comparisons (games between players), they pair players up against problems. If they solve the problem, the rating of the problem goes down, the rating of the player goes up. Players are given problems close to their ratings, which keeps everyone happy. I believe they use Glicko to track uncertainty in the rating.

Chapter 22 of David Barber's "Bayesian Reasoning and Machine Learning" (he makes it available online) does a nice (perhaps brief) job of explaining the progression through the Rasch model, the Bradley-Terry-Luce model and Elo.

As an aside, the way they chesstempo generate the exercises is also cute. The tactical chess problems are positions taken from high level (human) games fed into a chess engine which identifies blunderous moves where there is a single distinctly best way to respond. The challenge is to find that best move. Because they are taken from real games, they have the appearance and feel of real positions, which is important; many people believe pattern recognition is an important part of chess mastery. Apparently they've built up nearly 40000 such tactical exercises.

Re: How Khan Academy is using machine learning to assess student mastery

#38

Post by currere » Thu, Nov 03, 2011, 11:01 AM UTC

currere wrote: post #37

Another ingenious approach is taken by chesstempo.com, a chess training site. Just as in chess itself the ratings of players are determined by pairwise comparisons (games between players), they pair players up against problems. If they solve the problem, the rating of the problem goes down, the rating of the player goes up. Players are given problems close to their ratings, which keeps everyone happy. I believe they…

How awful, I just saw [ja27 17 hours ago]. I've even managed to describe it in almost exactly the same way..

Re: How Khan Academy is using machine learning to assess student mastery

#39

Post by eru » Thu, Nov 03, 2011, 1:14 PM UTC

brendano wrote: post #17

webspiderus wrote: post #11

Earlier quoted context omitted.

this is literally the first thing taught in both of the machine learning classes I've taken from Prof. Ng at Stanford, so maybe it's the application of logistic regression more than the estimation technique itself that makes machine learning?

There used to be an earlier era of machine learning that wasn't as statistical. Ng, and most other current ML researchers, now heavily draw on mainstream statistics. It really does make sense to do logistic regression as the foundation for later stuff. The terminology confusions, I think, stems from the earlier era of ML research.

What did the earlier era use?

Re: How Khan Academy is using machine learning to assess student mastery

#40

Post by lliiffee » Thu, Nov 03, 2011, 1:25 PM UTC

eru wrote: post #39

brendano wrote: post #17

Earlier quoted context omitted.

There used to be an earlier era of machine learning that wasn't as statistical. Ng, and most other current ML researchers, now heavily draw on mainstream statistics. It really does make sense to do logistic regression as the foundation for later stuff. The terminology confusions, I think, stems from the earlier era of ML research.

What did the earlier era use?

In a case like this, perhaps a perceptron?