Comparison of identification criteria for machine inductive inference

DOI10.1016/0304-3975(83)90061-0zbMath0524.03025OpenAlexW2018722248MaRDI 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

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)

Related Items

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 ⋮ Generality's price: Inescapable deficiencies in machine-learned programs ⋮ Counting extensional differences in BC-learning ⋮ The complexity of finding SUBSEQ\((A)\) ⋮ On the danger of half-truths ⋮ Is Gold-Putnam diagonalization complete? ⋮ Learning in the presence of inaccurate information ⋮ Effectivity questions for Kleene's recursion theorem ⋮ Invertible classes ⋮ Probability and plurality for aggregations of learning machines ⋮ Synthesizing inductive expertise ⋮ Strongly non-U-shaped language learning results by general techniques ⋮ Enlarging learnable classes ⋮ An approach to intrinsic complexity of uniform learning ⋮ On aggregating teams of learning machines ⋮ On the power of recursive optimizers ⋮ Learning recursive functions from approximations ⋮ Saving the phenomena: Requirements that inductive inference machines not contradict known data ⋮ Learning pattern languages over groups ⋮ Learning all subfunctions of a function ⋮ Classes with easily learnable subclasses ⋮ On the classification of recursive languages ⋮ Learning-theoretic perspectives of acceptable numberings ⋮ Recursion theoretic models of learning: Some results and intuitions ⋮ On the relative sizes of learnable sets ⋮ Mind change speed-up for learning languages from positive data ⋮ Learning and classifying ⋮ Kolmogorov numberings and minimal identification ⋮ Probabilistic language learning under monotonicity constraints ⋮ Learning secrets interactively. Dynamic modeling in inductive inference ⋮ On the intrinsic complexity of learning recursive functions ⋮ Identification of function distinguishable languages. ⋮ The independence of control structures in abstract programming systems ⋮ Absolutely no free lunches! ⋮ Optimal language learning from positive data ⋮ Learning families of algebraic structures from informant ⋮ Learning how to separate. ⋮ Separation of uniform learning classes. ⋮ Learning recursive functions: A survey ⋮ Learning and extending sublanguages ⋮ Confident and consistent partial learning of recursive functions ⋮ Learning by switching type of information. ⋮ Non-U-shaped vacillatory and team learning ⋮ Learning languages from positive data and negative counterexamples ⋮ Inferring answers to queries ⋮ Taming teams with mind changes ⋮ Learnability and positive equivalence relations ⋮ Learning in the presence of partial explanations ⋮ Anomalous learning helps succinctness ⋮ Aggregating inductive expertise on partial recursive functions ⋮ Iterative learning from positive data and negative counterexamples ⋮ Learning multiple languages in groups ⋮ Training digraphs ⋮ On a question about learning nearly minimal programs ⋮ Towards a mathematical theory of machine discovery from facts ⋮ Learning languages from positive data and a limited number of short counterexamples ⋮ Inductive reasoning and Kolmogorov complexity ⋮ Algorithmic identification of probabilities is hard ⋮ Realism, rhetoric, and reliability ⋮ On the power of inductive inference from good examples ⋮ Theory choice, theory change, and inductive truth-conduciveness ⋮ Causal learning with Occam's razor ⋮ Learning languages from positive data and a finite number of queries ⋮ Hypothesis spaces for learning ⋮ Variations on U-shaped learning ⋮ Increasing the power of uniform inductive learners ⋮ Resource restricted computability theoretic learning: Illustrative topics and problems ⋮ A note on batch and incremental learnability ⋮ Trade-off among parameters affecting inductive inference ⋮ 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 ⋮ 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 ⋮ Automata techniques for query inference machines ⋮ Maximal machine learnable classes ⋮ 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 ⋮ Inductive inference of approximations for recursive concepts ⋮ One-sided error probabilistic inductive inference and reliable frequency identification ⋮ On the inference of approximate programs ⋮ On the interplay between inductive inference of recursive functions, complexity theory and recursive numberings ⋮ Mind change complexity of learning logic programs ⋮ Avoiding coding tricks by hyperrobust learning ⋮ Language learning from texts: Degrees of intrinsic complexity and their characterizations ⋮ Extremes in the degrees of inferability ⋮ Training sequences ⋮ Learning via finitely many queries ⋮ Inductive inference with additional information. ⋮ On an open problem in classification of languages ⋮ Learning Families of Closed Sets in Matroids ⋮ Memory limited inductive inference machines ⋮ Effectivity Questions for Kleene’s Recursion Theorem ⋮ On the Influence of Technology on Learning Processes ⋮ Parsimony hierarchies for inductive inference ⋮ Infinitary self-reference in learning theory ⋮ Spatial/kinematic domain and lattice computers ⋮ The power of probabilism in Popperian FINite learning ⋮ Learning via queries in [+, <] ⋮ Generalization versus classification ⋮ Machine learning of higher-order programs ⋮ Computability-theoretic learning complexity ⋮ Learning from Positive Data and Negative Counterexamples: A Survey ⋮ Machine induction without revolutionary paradigm shifts ⋮ Simulating teams with many conjectures ⋮ On unstable and unoptimal prediction ⋮ Gold-Style Learning Theory ⋮ Learning Theory and Epistemology ⋮ Dynamic Modeling in Inductive Inference ⋮ On the Amount of Nonconstructivity in Learning Recursive Functions ⋮ Robust separations in inductive inference ⋮ Measure, category and learning theory ⋮ Explanatory and creative alternatives to the MDL principle ⋮ 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 ⋮ Vacillatory and BC learning on noisy data ⋮ Learnability and positive equivalence relations ⋮ Learners based on transducers ⋮ Learning algebraic structures from text ⋮ Predictive learning models for concept drift ⋮ Closedness properties in ex-identification ⋮ Partial learning of recursively enumerable languages ⋮ Prediction of Recursive Real-Valued Functions from Finite Examples ⋮ Hypothesis Spaces for Learning ⋮ Unnamed Item ⋮ Learning correction grammars ⋮ Random Subgroups of Rationals ⋮ Learning Pattern Languages over Groups ⋮ Combining Models of Approximation with Partial Learning

Cites Work