0000000000178161

AUTHOR

Lance Fortnow

showing 2 related works from this author

Measure, category and learning theory

1995

Measure and category (or rather, their recursion theoretical counterparts) have been used in Theoretical Computer Science to make precise the intuitive notion “for most of the recursive sets.” We use the notions of effective measure and category to discuss the relative sizes of inferrible sets, and their complements. We find that inferrible sets become large rather quickly in the standard hierarchies of learnability. On the other hand, the complements of the learnable sets are all large.

Preference learningRecursionTheoretical computer scienceLearnabilitySample exclusion dimensionComputer scienceConcept learningAlgorithmic learning theoryMeasure (mathematics)Recursive tree
researchProduct

On the relative sizes of learnable sets

1998

Abstract Measure and category (or rather, their recursion-theoretical counterparts) have been used in theoretical computer science to make precise the intuitive notion “for most of the recursive sets”. We use the notions of effective measure and category to discuss the relative sizes of inferrible sets, and their complements. We find that inferable sets become large rather quickly in the standard hierarchies of learnability. On the other hand, the complements of the learnable sets are all large.

General Computer Science0102 computer and information sciencesMachine learningcomputer.software_genre01 natural sciencesMeasure (mathematics)Theoretical Computer ScienceTuring machinesymbols.namesake0101 mathematicsMathematicsBinary treeLearnabilitybusiness.industry010102 general mathematicsInductive inferenceCategoryInductive reasoningMeasureAbstract machine010201 computation theory & mathematicssymbolsArtificial intelligencebusinesscomputerComputer Science(all)Theoretical Computer Science
researchProduct