Q: Can we say that all of machine learning is, essentially, only about finding good estimations of programs? If not, is there any example of a machine learning problem that is not about finding estimations of programs?

Examples of programs could be simple decision problem solvers, such as binary classification, regression, clustering, or more complicated programs such as those that generate special sequences of output (e.g. instructions for a self-drive automotive, human text, audio signals, etc).

Some definitions in case it helps clarifying the context.

A program is defined here as follows:

A computer program is a collection of instructions that performs a specific task when executed by a computer. A computer requires programs to function, and typically executes the program's instructions in a central processing unit.

Machine learning is defined here as follows:

Machine learning is a subfield of computer science that evolved from the study of pattern recognition and computational learning theory in artificial intelligence. In 1959, Arthur Samuel defined machine learning as a "Field of study that gives computers the ability to learn without being explicitly programmed". Machine learning explores the study and construction of algorithms that can learn from and make predictions on data. Such algorithms operate by building a model from example inputs in order to make data-driven predictions or decisions, rather than following strictly static program instructions.


closed as unclear what you're asking by whuber Sep 12 '16 at 14:24

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ This question is confusing to me because I'm not familiar with exactly what "estimation of programs" means, and from your examples, it's not clear what is not a program. $\endgroup$ – Cliff AB Sep 11 '16 at 16:14
  • $\begingroup$ Estimating programs means finding a program that is closest possible to the true program that you ideally want to identify. Usually you estimate such programs by only analyzing the previous outputs of the true program. And yes, I too think that everything is a program. So I guess the answer to this question is a yes? $\endgroup$ – caveman Sep 11 '16 at 18:00
  • 3
    $\begingroup$ If your question is "Is machine learning only about estimating something?", then it seems safe to say "yes". If your question is "Is machine learning only about estimating something based only analyzing previous results of that something?", one could say the answer is "no", with Bayesian methods being a counter example: you are estimating something using both observations and expert knowledge. But I'm not sure if that's exactly what you're after. $\endgroup$ – Cliff AB Sep 11 '16 at 18:09
  • $\begingroup$ I am after a bigger question. It's all coming as multiple specific questions instead of a single big question. I also agree about everything you said in your comment. $\endgroup$ – caveman Sep 11 '16 at 18:15
  • 1
    $\begingroup$ "Anything that computes things" is pretty vague. I think this is going to end up being an exercise in definitions. You come up w/ a definition that makes the answer trivially no, or a different definition that makes the answer trivially yes. $\endgroup$ – gung Sep 15 '16 at 12:24

The paper On the Learnability of the Uncomputable showes that machine learning is not estimating programs in a very surprising direction. It shows how to pac learn the halting problem. The halting problem is not computable, and therefore there is no program that can compute it.

The way to learn it is simple - take a large enough sample of programs that halt. Compute a threshold high enough so most programs halt before it. When having to classify a new sample run it until the threshold and see if it halts.

I think that this paper shouldn't be interpreted as showing that we can learn what we cannot compute. Instead, in alerts on the problem in the PAC framework. We assume that if we have samples, we can learn. In the case of the halting problem, we cannot get such samples (in general). Without extra knowledge we won't know which of the programs will eventually halt so we can run time until they end.

In the other direction, formal treatment of machine learning usually assume that the concept belong to some hypothesis set of a mathematical nature. Usually most concept discussed belong to much simpler hypothesis classes than programs. The reason to that is that we have negative results about the learnability for already when the concept is less complex than a program. For examples see "Cryptographic limitations on learning boolean formulae and finite automata"

  • $\begingroup$ But PAC learning aims to find an estimation of a solver that solves the halting problem. However, it will never be able to find a solver for it (it will always have errors). I don't think that there is any claim that a program cannot estimate the solver of the halting problem, and as far as I know PAC learning is about finding estimators (not actual solvers). Just to make sure I read correctly: are you saying that estimators of solvers of the halting problems are not programs? $\endgroup$ – caveman Sep 13 '16 at 14:58
  • 1
    $\begingroup$ There is no program that can solve the halting problem. However, this paper shows how one can estimate this inexistent solver. The key point here is that PAC learning assumes that you will have a dataset of labeled sample. Hence the claim is "Given labeled samples for halting programs, one can estimate the inexistent halting problem problem". The next step should be - since we know that one cannot solve the halting problem (in general), then one cannot build a dataset on halting problem (in general). $\endgroup$ – DaL Sep 14 '16 at 6:08
  • $\begingroup$ The in general is for estimating the halting problem on arbitrary cases. Of course that one can find many samples of program that stop/don't stop. $\endgroup$ – DaL Sep 14 '16 at 6:09
  • $\begingroup$ I see how that is evidence that enough dataset cannot be found, but I cannot see how that is evidence that the resultant classification model is not a program. $\endgroup$ – caveman Sep 14 '16 at 14:26
  • $\begingroup$ Oh, I understand. The resultant model is indeed a program. The concept that the model tries to learn cannot be implemented in a program. $\endgroup$ – DaL Sep 15 '16 at 5:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.