Lowe On ML

Derek Lowe: "Will It Learn? Can It Learn?" (Via H.R.)

[C]ould you have a dataset that really does have a rule in it that could theoretically be discovered, but you are luckless enough to have picked an ML algorithm that is incapable of finding such a rule? How general is learnability?

A recent paper came up with a surprising answer to that question. (Update: here’s Ash/Wavefunction with a post on this as well). The authors have a particular learning model (“estimating the maximum”, or EMX) and investigate its behavior with data produced by several different underlying “rule” functions. And they show – as in no escape, mathematically prove – that there are functions for which it is absolutely impossible to know whether they are learnable by the EMX algorithm or not. Not just difficult to know, not computationally hard until someone comes up with a better way to evaluate the problem, none of that: the question of learnability in those cases is formally undecidable.

The mathematically inclined will be wondering if I mean that term the way it sounds like, and the answer is, yep, Kurt Gödel rides again.