Learning coherent concepts

Ashutosh Garg, Dan Roth

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAlgorithmic Learning Theory - 12th International Conference, ALT 2001, Proceedings
EditorsNaoki Abe, Roni Khardon, Thomas Zeugmann
Number of pages16
ISBN (Print)3540428755, 9783540428756
StatePublished - 2001
Externally publishedYes
Event12th Annual Conference on Algorithmic Learning Theory, ALT 2001 - Washington, United States
Duration: Nov 25 2001Nov 28 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other12th Annual Conference on Algorithmic Learning Theory, ALT 2001
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Learning coherent concepts'. Together they form a unique fingerprint.

Cite this