Equivalence of models for polynomial learnability. (English) Zbl 0743.68115
Summary: We consider several variants of Valiant’s learnability model that have appeared in the literature. We give conditions under which these models are equivalent in terms of the polynomially learnable concept classes they define. These equivalences allow comparisons of most of the existing theorems in Valiant-style learnability and show that several simplifying assumptions on polynomial learning algorithms can be made without loss of generality. We also give a useful reduction of learning problems to the problem of finding consistent hypotheses, and give comparisons and equivalences between Valiant’s model and the prediction learning models of Haussler, Littlestone, and Warmuth (in “29th Annual IEEE Symposium on Foundations of Computer Science”, 1988).
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
machine learning; polynomial learnability; Valiant’s learnability model; equivalences; consistent hypotheses; prediction learningReferences:
| [1] | Aho, V. A.; Hopcroft, J. E.; Ullman, J. D., (The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Menlo Park) · Zbl 0326.68005 |
| [2] | Angluin, D., Queries and concept learning, Machine Learning, 2, 319-342 (1987) · Zbl 1470.68050 |
| [3] | Angluin, D.; Valiant, L. D., Fast probabilistic algortihms for Hamiltonian circuits and matchings, J. Comput. System Sci., 18, 155-193 (1979) · Zbl 0437.05040 |
| [4] | Benedek, G.; Itai, A., Learnability by fixed distributions, (Proceedings, 1st Workshop on Computational Learning Theory. Proceedings, 1st Workshop on Computational Learning Theory, Theoretical Computer Science (1988), MIT: MIT Cambridge, MA), 80-90, to appear |
| [5] | Benedek, G.; Itai, A., Nonuniform learnability, (Proceedings, 15th International Colloquium on Automata Languages and Programming (1988)), 82-92 · Zbl 0649.68080 |
| [6] | Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M. K., Occam’s razor, Inform. Process. Lett., 24, 377-380 (1987) · Zbl 0653.68084 |
| [7] | Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M. K., Learnability and the Vapnik-Chervonenkis dimension, J. Assoc. Comput. Mach., 36, 4, 929-965 (1989) · Zbl 0697.68079 |
| [8] | Board, R. A.; Pitt, L., On the Necessity of Occam Algorithms, (Proceedings, 22nd Annual ACM Symposium on Theory of Computing. Proceedings, 22nd Annual ACM Symposium on Theory of Computing, Baltimore, Maryland. Proceedings, 22nd Annual ACM Symposium on Theory of Computing. Proceedings, 22nd Annual ACM Symposium on Theory of Computing, Baltimore, Maryland, Theoretical Computer Science (1990)), 54-63, to appear |
| [9] | Garey, M.; Johnson, D., (Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco) · Zbl 0411.68039 |
| [10] | Haussler, D.; Littlestone, N.; Warmuth, M. K., Predicting {0, 1}-functions on randomly drawn points, (29th Annual IEEE Symposium on Foundations of Computer Science. 29th Annual IEEE Symposium on Foundations of Computer Science, White Plains, New York (1988)), 100-109 · Zbl 0938.68785 |
| [11] | Haussler, D. and Welzl, E.Discrete Comput. Geom.2; Haussler, D. and Welzl, E.Discrete Comput. Geom.2 · Zbl 0619.68056 |
| [12] | Kearns, M.; Li, M.; Pitt, L.; Valiant, L., Recent results on Boolean concept learning, (Proceedings, 4th International Workshop on Machine Learning. Proceedings, 4th International Workshop on Machine Learning, Irvine, California (1987)), 337-352 |
| [13] | Linial, N.; Mansour, Y.; Rivest, R., Results on learnability and the Vapnik-Chervonenkis dimension, (Proceedings, 29th IEEE Symposium on Foundations of Computer Science. Proceedings, 29th IEEE Symposium on Foundations of Computer Science, White Plains, New York (1988)), 120-129 |
| [14] | Natarajan, B. K., On learning boolean functions, (Proceedings, 19th Annual ACM Symposium on Theory of Computation (1987)), 296-304 |
| [15] | Natarajan, B. K., Learning Functions from Examplex, (Technical Report CMU-RI-TR-87-19 (1987), Carnegie Mellon University) · Zbl 0747.68056 |
| [16] | Natarajan, B. K., On learning sets and functions, Machine Learning, 4, 2 (1989) · Zbl 0747.68056 |
| [17] | Pitt, L.; Valiant, L. G., Computational limitations on learning from examples, J. Assoc. Comput. Mach., 35, 4, 965-984 (1988) · Zbl 0662.68086 |
| [18] | Pitt, L.; Warmuth, M. K., Prediction preserving reducibility, J. Comput. System Sci., 41, 3, 430-467 (1990) · Zbl 0722.68094 |
| [19] | Rivest, R., Learning decision-lists, Machine Learning, 2, 3, 229-246 (1987) |
| [20] | Sauer, N., On the density of families of sets, J. Combin. Theory Ser. A, 13, 145-147 (1972) · Zbl 0248.05005 |
| [21] | Schapire, R. F., The strength of weak learnability, Machine Learning, 5, 2, 197-227 (1990) |
| [22] | Valiant, L. G., A theory of the learnable, Comm. ACM, 27, 11, 1134-1142 (1984) · Zbl 0587.68077 |
| [23] | Valiant, L. G., Learning disjunctions of conjunctions, (Proceedings, 9th IJCAI, Los Angeles, California, Vol. 1 (1985)), 560-566 |
| [24] | Vapnik, V. N., (Estimation of Dependences Based on Empirical Data (1982), Springer-Verlag: Springer-Verlag New York) · Zbl 0499.62005 |
| [25] | Vapnik, V. N.; Chervonenkis, A. Ya., On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16, 2, 264-280 (1971) · Zbl 0247.60005 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
