Abstract
This paper develops a theory for learning scenarios where multiple learners co-exist but there are mutual coherency constraints on their outcomes. This is natural in cognitive learning situations, where “natural” constraints are imposed on the outcomes of classifiers so that a valid sentence, image or any other domain representation is produced. We formalize these learning situations, after a model suggested in [11] and study generalization abilities of learning algorithms under these conditions in several frameworks. We show that the mere existence of coherency constraints, even without the learner’s awareness of them, deems the learning problem easier than predicted by general theories and explains the ability to generalize well from a fairly small number of examples. In particular, it is shown that within this model one can develop an understanding to several realistic learning situations such as highly biased training sets and low dimensional data that is embedded in high dimensional instance spaces.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Amsterdam. Some philosophical problems with formal learning theory. In National Conference on Artificial Intelligence, pages 580–584, 1988.
R. I. Arriaga and S. Vempala. An algorithmic theory of learning: Robust concepts and random projection. In Proc. of the 40th Foundations of Computer Science, 1999.
G. Benedek and A. Itai. Learnability with respect to fixed distributions. Theoret. Comput. Sci., 86(2):377–389, 1991.
A. Blum and T. Mitchell. Combining labeled and unlabeled data with co-training. In Proc. of the Annual ACM Workshop on Computational Learning Theory, pages 92–100, 1998.
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Occam’s razor. Information Processing Letters, 24:377–380, April 1987.
C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20:273–297, 1995.
H. Druker, R. Schapire, and P. Simard. Improving performance in neural networks using a boosting algorithm. In Neural Information Processing Systems 5, pages 42–49. Morgan Kaufmann, 1993.
A. Garg, S. Har-Peled, and D. Roth. Generalization bounds for linear learning algorithms. Technical Report UIUCDCS-R-2001-2232, University of Illinois at Urbana Champaign, June 2001.
A. R. Golding and D. Roth. A Winnow based approach to context-sensitive spelling correction. Machine Learning, 34(1–3):107–130, 1999. Special Issue on Machine Learning and Natural Language.
D. A. McAllester. Some PAC-Bayesian theorems. Machine Learning, 37(3):355–363, 1999.
D. Roth and D. Zelenko. Towards a theory of coherent concepts. In National Conference on Artificial Intelligence, pages 639–644, 2000.
L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, November 1984.
V. Vapnik, E. Levin, and Y. Le Cun. Measuring the VC-dimension of a learning machine. Neural Computation, 6(5):851–876, 1994.
V. N. Vapnik. Statistical Learning Theory. John-Wiley and Sons Inc., New York, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Garg, A., Roth, D. (2001). Learning Coherent Concepts. In: Abe, N., Khardon, R., Zeugmann, T. (eds) Algorithmic Learning Theory. ALT 2001. Lecture Notes in Computer Science(), vol 2225. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45583-3_12
Download citation
DOI: https://doi.org/10.1007/3-540-45583-3_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42875-6
Online ISBN: 978-3-540-45583-7
eBook Packages: Springer Book Archive