[Solved]: What was going on before PAC learning

Problem Detail: 

I am investigating PAC learning (computational learning theory) as a beginner with no previous knowledge of machine learning / AI. I am investigating the model mainly from a historical point of view.

For this, the most important things are of course the results based on the model. There are enough papers out there that document these results. But I also want to write something about what was going on before PAC learning, as to sketch the historical context up to where Valiant came with the notion of the PAC model.

No papers/surveys I've found so far document this, and as someone with no real knowledge of machine learning, it is hard to find this out. I am therefore asking this soft question here, because I believe there are enough experts that can help me with this. References are highly appreciated.

When I can research and study what was going on before PAC, I might get a better appreciation as to why the academic world is so enthusiastic about the PAC model, which is also something interest to document in my historical work!

Asked By : codd

Answered By : Thomas Klimpel

References are highly appreciated.

An author is expected to address the question of the context and relevance of his results at the begin of his publication. I just skimmed over the introduction of "L. Valiant. A theory of the learnable. Communications of the ACM, 27, 1984." again, and found out that Valiant indeed well covered your question.

The original paper by Valiant is both freely available and not too difficult to read. (Except section 7, which only proves that the author can also tackle challenging mathematical problems, but doesn't contribute much to the real content of the paper.) Reading at least its introduction will be more rewarding than reading my overly long answer to this question, so I suggest to really try it.

---

The rest of this answer tries to cite some passages from the introduction which should indicate whether reading this introduction might answer the question about the historical context. Note however that an author has the natural prerogative to be biased with respect to such questions.

... such a system would, at least, be a very good start. First, when one examines the most famous examples of systems that embody preprogrammed knowledge, namely, expert systems such as DENDRAL and MYCIN, essentially no logical notation beyond the propositional calculus is used.

This is interesting information for the context, because propositional calculus is significantly weaker than predicative calculus or the various systems of type theory sometimes used today. (Strange enough though, Prolog (1972) and ML (1973) were among others intended as meta-languages for "such" expert systems, and seem to go beyond simple propositional logic as far as I can see. Also, the relational model (1969) for database management is claimed to be based on predicate logic.)

Perhaps the main technical discovery contained in the paper is that with this probabilistic notion of learning highly convergent learning is possible for whole classes of Boolean functions. This appears to distinguish this approach from more traditional ones where learning is seen as a process of "inducing" some general rule from information that is insufficient for a reliable deduction to be made.

I fully agree here. It is important to be able to explain how your solution is able to solve a given problem, and in which sense it is a solution. Otherwise, you just end up with "no-free lunch" theorems which don't allow you to distinguish a buggy implementation of a dubious heuristic from a correct implementation of an appropriate heuristic.

In summary, this paper attempts to explore the limits of what is learnable as allowed by algorithmic complexity. The results are distinguishable from the diverse body of previous work on learning because they attempt to reconcile the three properties ((1)-(3)) mentioned earlier. Closest in rigor to our approach is the inductive inference literature [...]. There is a large body of work on pattern recognition and classification, using statistical and other tools [...]. Learning, in various less formal senses, has been studied widely as a branch of artificial intelligence.

The properties ((1)-(3)) were that (1) "the machines can provably learn whole characterizable classes of concepts" which are (2) "appropriate and nontrivial for general-purpose knowledge" and (3) "the computational process requires only a feasible (i.e., polynomial) number of steps".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11937

3.2K people like this

 Download Related Notes/Documents