×

On the necessity of Occam algorithms. (English) Zbl 0825.68544


MSC:

68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abe, N., Polynomial learnability of semilinear sets, (Proc. 1989 Workshop on Computational Learning Theory (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 25-40 · Zbl 0747.68039
[2] Angluin, D., Negative results for equivalence queries, Machine Learning, 5, 2, 121-150 (1990), (Special issue on computational learning theory.)
[3] Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M., Occam’s razor, Inform. Process. Lett., 24, 377-380 (1987) · Zbl 0653.68084
[4] Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M., Learnability and the Vapnik-Chervonenkis dimension, J. ACM, 36, 4, 929-965 (1989) · Zbl 0697.68079
[5] Ehrenfeucht, A.; Haussler, D.; Kearns, M.; Valiant, L. G., A general lower bound on the number of examples needed for learning, Inform. and Comput., 82, 247-261 (1989) · Zbl 0679.68158
[6] Fulk, M.; Case, J., Proc. 1990 Workshop on Computational Learning Theory (1990), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[7] Gill, J., Probabilistic Turing machines, SIAM J. Comput., 6, 4, 675-695 (1977) · Zbl 0366.02024
[8] Haussler, D., Learning conjunctive concepts in structural domains, Machine Learning, 4, 1, 7-40 (1989)
[9] to appear in Inform. and Comput.; to appear in Inform. and Comput.
[10] Haussler, D.; Pitt, L., Proc. 1988 Workshop on Computational Learning Theory (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[11] Kearns, M.; Li, M., Learning in the presence of malicious errors, (Proc. 20th Ann. ACM Symp. on Theory of Computing (1988), ACM: ACM New York), 267-280
[12] Kearns, M.; Valiant, L. G., Cryptographic limitations on learning Boolean formulae and finite automata, (Proc. 21st Ann. ACM Symp. on Theory of Computing (1989), ACM: ACM New York), 433-444
[13] William of Occam, Quodlibeta Septem; William of Occam, Quodlibeta Septem
[14] Pitt, L.; Valiant, L. G., Computational limitations on learning from examples, J. ACM, 35, 4, 965-984 (1988) · Zbl 0662.68086
[15] Pitt, L.; Warmuth, M. K., Prediction preserving reducibility, J. Comput. System Sci., 41, 430-467 (1990) · Zbl 0722.68094
[16] Pitt, L.; Warmuth, M. K., The minimum consistent DFA problem cannot be approximated within any polynomial, (Tech. Report UIUCDCS-R-89-1499 (1989), University of Illinois at Urbana-Champaign). (Tech. Report UIUCDCS-R-89-1499 (1989), University of Illinois at Urbana-Champaign), 21st annual ACM Symposium on Theory of Computing (1989), to appear in J. ACM · Zbl 0774.68084
[17] Rivest, R. L., Learning decision lists, Machine Learning, 2, 229-246 (1987)
[18] Rivest, R. L.; Haussler, D.; Warmuth, M. K., Proc. 1989 Workshop on Computational Learning Theory (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[19] Schapire, R., The strength of weak learnability, Machine Learning, 5, 2, 197-227 (1990), (Special issue on computational learning theory.)
[20] Sloan, R., Computational learning theory: New models and algorithms, (Tech. Report MIT/LCS/TR-448. Tech. Report MIT/LCS/TR-448, Ph.D. Thesis (1989), MIT)
[21] Valiant, L. G., A theory of the learnable, Comm. ACM, 27, 11, 1134-1142 (1984) · Zbl 0587.68077
[22] Warmuth, M. K., Towards representation independence in PAC-learning, (Proc. AII-89 Workshop on Analogical and Inductive Inference. Proc. AII-89 Workshop on Analogical and Inductive Inference, Lecture Notes in Artificial Intelligence, Vol. 397 (1989), Springer: Springer Heidelberg), 78-103
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.