Comparison of identification criteria for machine inductive inference

DOI10.1016/0304-3975(83)90061-0zbMath0524.03025MaRDI QIDQ585192

Publication date: 1983

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

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90061-0

zbMATH Keywords

identification; philosophy of science; inductive inference; recursive function theory; anomalies in programs; inherent relative computational complexity; tradeoff results

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03D20: Recursive functions and relations, subrecursive hierarchies

03D10: Turing machines and related notions

Related Items

Costs of general purpose learning, On the learnability of recursively enumerable languages from good examples, Synthesizing noise-tolerant language learners, Hierarchies of probabilistic and team FIN-learning, Synthesizing learners tolerating computable noisy data, Robust learning is rich, Learning algebraic structures from text, Predictive learning models for concept drift, Closedness properties in ex-identification, Infinitary self-reference in learning theory, Spatial/kinematic domain and lattice computers, The power of probabilism in Popperian FINite learning, Machine learning of higher-order programs, On an open problem in classification of languages, Generalization versus classification, Parsimony hierarchies for inductive inference, Explanatory and creative alternatives to the MDL principle, Vacillatory and BC learning on noisy data, Hypothesis spaces for learning, Learning all subfunctions of a function, Classes with easily learnable subclasses, On the classification of recursive languages, Anomalous learning helps succinctness, Training digraphs, On a question about learning nearly minimal programs, Towards a mathematical theory of machine discovery from facts, Resource restricted computability theoretic learning: Illustrative topics and problems, One-sided error probabilistic inductive inference and reliable frequency identification, On the inference of approximate programs, Training sequences, Learning via finitely many queries, The complexity of finding SUBSEQ\((A)\), An approach to intrinsic complexity of uniform learning, Learning recursive functions: A survey, Learning and extending sublanguages, Non-U-shaped vacillatory and team learning, Learning languages from positive data and negative counterexamples, Inferring answers to queries, Taming teams with mind changes, Probability and plurality for aggregations of learning machines, Synthesizing inductive expertise, On the power of recursive optimizers, Saving the phenomena: Requirements that inductive inference machines not contradict known data, On the relative sizes of learnable sets, The independence of control structures in abstract programming systems, Learning in the presence of partial explanations, Aggregating inductive expertise on partial recursive functions, Inductive reasoning and Kolmogorov complexity, On the power of inductive inference from good examples, A note on batch and incremental learnability, On the inductive inference of recursive real-valued functions, Approximation methods in inductive inference, Learning via queries and oracles, The logic of reliable and efficient inquiry, Maximal machine learnable classes, Extremes in the degrees of inferability, On the danger of half-truths, Is Gold-Putnam diagonalization complete?, Learning in the presence of inaccurate information, On aggregating teams of learning machines, Learning recursive functions from approximations, Learning-theoretic perspectives of acceptable numberings, Kolmogorov numberings and minimal identification, Probabilistic language learning under monotonicity constraints, On the intrinsic complexity of learning recursive functions, Identification of function distinguishable languages., Learning how to separate., Separation of uniform learning classes., Learning by switching type of information., Robust learning aided by context, Learning languages and functions by erasing, Structural measures for games and process control in the branch learning model, Ordinal mind change complexity of language identification, Mind change complexity of learning logic programs, Avoiding coding tricks by hyperrobust learning, Language learning from texts: Degrees of intrinsic complexity and their characterizations, Inductive inference with additional information., Increasing the power of uniform inductive learners, Trade-off among parameters affecting inductive inference, Automata techniques for query inference machines, Learning classes of approximations to non-recursive functions., The synthesis of language learners., Incremental concept learning for bounded data mining., Robust behaviorally correct learning., Learning to win process-control games watching game-masters, Learning by the process of elimination, On learning of functions refutably., Intrinsic complexity of learning geometrical concepts from positive data, Trees and learning, Robust learning -- rich and poor, Generalized notions of mind change complexity, Counting extensional differences in BC-learning, Recursion theoretic models of learning: Some results and intuitions, Generality's price: Inescapable deficiencies in machine-learned programs, Invertible classes, Iterative learning from positive data and negative counterexamples, Learning multiple languages in groups, Learning languages from positive data and a limited number of short counterexamples, Learning languages from positive data and a finite number of queries, Variations on U-shaped learning, Inductive inference of approximations for recursive concepts, On the Amount of Nonconstructivity in Learning Recursive Functions, Robust separations in inductive inference, Dynamic Modeling in Inductive Inference, Prediction of Recursive Real-Valued Functions from Finite Examples, Hypothesis Spaces for Learning, Learning correction grammars, Learning via queries in [+, <], Unnamed Item

Cites Work