On the intrinsic complexity of learning

DOI10.1006/inco.1995.1158zbMath1096.68635OpenAlexW2067748079MaRDI QIDQ2508338

Rūsiņš Freivalds, Carl H. Smith, E. B. Kinber

Publication date: 10 October 2006

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1995.1158

Mathematics Subject Classification ID

Computational learning theory (68Q32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items

On learning of functions refutably. ⋮ Intrinsic complexity of learning geometrical concepts from positive data ⋮ How rich is the structure of the intrinsic complexity of learning ⋮ Learning languages in a union ⋮ An approach to intrinsic complexity of uniform learning ⋮ Computability-theoretic learning complexity ⋮ Mind change speed-up for learning languages from positive data ⋮ Learning secrets interactively. Dynamic modeling in inductive inference ⋮ Intrinsic complexity of partial learning ⋮ On the intrinsic complexity of learning recursive functions ⋮ Dynamic Modeling in Inductive Inference ⋮ Learning recursive functions: A survey ⋮ Quantum inductive inference by finite automata ⋮ Explanatory and creative alternatives to the MDL principle ⋮ Mind change efficient learning ⋮ Iterative learning of simple external contextual languages ⋮ The functions of finite support: a canonical learning problem ⋮ Control structures in hypothesis spaces: The influence on learning ⋮ Aspects of complexity of probabilistic learning under monotonicity constraints ⋮ Intrinsic Complexity of Partial Learning ⋮ Induction by enumeration ⋮ Language learning from texts: Degrees of intrinsic complexity and their characterizations