Learning boolean functions in an infinite attribute space
Tóm tắt
This paper presents a theoretical model for learning Boolean functions in domains having a large, potentially infinite number of attributes. The model allows an algorithm to employ a rich vocabulary to describe the objects it encounters in the world without necessarily incurring time and space penalties so long as eachindividual object is relatively simple. We show that many of the basic Boolean functions learnable in standard theoretical models, such as conjunctions, disjunctions,K-CNF, andK-DNF, are still learnable in the new model, though by algorithms no longer quite so trivial as before. The new model forces algorithms for such classes to act in a manner that appears more natural for many learning scenarios.
Tài liệu tham khảo
Angluin, D. (1986).Learning regular sets from queries and counter-examples (Technical Report YALEU/DCS/TR-464). New Haven, CT: Yale University, Department of Computer Science.
Angluin, D. (1988). Queries and concept learning.Machine Learning, 2, 319–342.
Angluin, D., Hellerstein, L., & Karpinski, M. (1989).Learning read-once formulas with queries (Technical Report UCB/CSD 89/528). Berkeley, CA: University of California, Berkeley, Computer Science Division.
Blum, A. (1990). Learning boolean functions in an infinite attribute space.Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (pp. 64–72). Baltimore, MD.
Blum, A., Hellerstein, L., & Littlestone, N. (1991). Learning in the presence of finitely or infinitely many irrelevant attributes.Proceedings of the Fourth Annual Workshop on Computational Learning Theory. Santa Cruz, CA: Morgan Kaufmann.
Kearns, M. (1989).The computational complexity of machine learning. PhD thesis, Harvard University Center for Research in Computing Technology. (Technical Report TR-13-89). Also published by MIT Press as an ACM Distinguished Dissertation.
Kearns, M., Li, M., Pitt, L., & Valiant, L. (1987). Recent results on boolean concept learning.Proceedings of the Fourth International Workshop on Machine Learning pp. 337–352). Irvine, CA: University of California, Irvine.
Littlestone, N. (1987). Learning when irrelevant attributes abound: A new linear-threshold algorithm.Machine Learning, 2, 285–318.
Littlestone, N. (1989).Mistake bounds and logarithmic linear-threshold learning algorithms. PhD thesis, University of California, Santa Cruz.
Rivest, R.L. (1987). Learning decision lists.Machine Learning, 2, 229–246.
Valiant, L.G. (1984). A theory of the learnable.Communications of the ACM, 27, 1134–1142.