A note on the use of probabilities by mechanical learners

Eric Martin, Daniel Osherson

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


We raise the following problem: in a probabilistic context, is it always fruitful for a machine to compute probabilities? The question is made precise in a paradigm of the limit-identification kind, where a learner must discover almost surely whether an infinite sequence of heads and tails belongs to an effective subset S of the Cantor space. In this context, a successful strategy for an ineffective learner is to compute, at each stage, the conditional probability that he is faced with an element of 5, given the data received so far. We show that an effective learner should not proceed this way in all circumstances. Indeed, even if he gets art optimal description of a set S, and even if some machine can always compute the conditional probability for S given any data, an effective learner optimizes his inductive competence only if he does not compute the relevant probabilities. We conclude that the advice "compute probabilities whenever you can" should sometimes be received with caution in the context of machine learning.

Original languageEnglish (US)
Title of host publicationComputational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings
EditorsPaul Vitanyi
PublisherSpringer Verlag
Number of pages11
ISBN (Print)9783540591191
StatePublished - 1995
Event2nd European Conference on Computational Learning Theory, EuroCOLT 1995 - Barcelona, Spain
Duration: Mar 13 1995Mar 15 1995

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


Other2nd European Conference on Computational Learning Theory, EuroCOLT 1995

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A note on the use of probabilities by mechanical learners'. Together they form a unique fingerprint.

Cite this