Intrinsic complexity of partial learning

DOI10.1016/J.TCS.2018.12.022MaRDI QIDQ2419119zbMATH OpenOpenAlexWikidataFDO

Authors Sanjay Jain, Efim Kinber

Publication date 29 May 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.12.022

zbMATH Keywords

inductive inferenceintrinsic complexitypartial learning

Mathematics Subject Classification ID

Computational learning theory (68Q32) Formal languages and automata (68Q45)

Review text

The authors define intrinsic complexity of partial learning, based on reducibilities between learning problems. They observe a rich structure of incomplete degrees, reflecting different types of learning strategies, in terms of topological structures of the target language classes. They also present some examples of complete classes that illuminate the character of the strategies for partial learning of the hardest classes.

Recommendations

• Intrinsic complexity of partial learning
• On the intrinsic complexity of learning recursive functions
• Language learning from texts: Degrees of intrinsic complexity and their characterizations
• scientific article; zbMATH DE number 2051904
• An approach to intrinsic complexity of uniform learning

Cites work

• A Machine-Independent Theory of the Complexity of Recursive Functions
• A non-learnable class of E-pattern languages
• A survey on recent results on partial learning
• A theory of formal synthesis via inductive learning
• Combining models of approximation with partial learning
• Computability-theoretic learning complexity
• Confident and Consistent Partial Learning of Recursive Functions
• Finding patterns common to a set of strings
• scientific article; zbMATH DE number 3932417 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3806956 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Inductive inference of formal languages from positive data
• Intrinsic complexity of learning geometrical concepts from positive data
• Intrinsic complexity of partial learning
• Language identification in the limit
• Language learning from texts: Degrees of intrinsic complexity and their characterizations
• Learning languages from positive data and negative counterexamples
• Learning regular sets from queries and counterexamples
• On conservative learning of recursively enumerable languages
• On the intrinsic complexity of learning
• On the intrinsic complexity of learning recursive functions
• The intrinsic complexity of language identification
• The structure of intrinsic complexity of learning

Cited in

(11)

• On the value of partial information for learning from examples
• On the intrinsic complexity of learning recursive functions
• Language learning from texts: Degrees of intrinsic complexity and their characterizations
• On the intrinsic complexity of learning
• Intrinsic complexity of partial learning
• Measuring learning complexity with criteria epitomizers
• The structure of intrinsic complexity of learning
• scientific article; zbMATH DE number 2051904 (Why is no real title available?)
• Intrinsic complexity of uniform learning
• An approach to intrinsic complexity of uniform learning
• Partial observability and learnability

This page was built for publication: Intrinsic complexity of partial learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2419119)