scientific article; zbMATH DE number 193511
Te monograph attempts to give a mathematical model of learning. The author describes his contribution to developing of the model as study of the identification problem, i.e., the problem of identifying an item from a known class using positive and negative examples. In the first part of the book the following definitions are introduced. An identification problem is a 4-tuple ((D,\(\geq),\epsilon,h,GE?)\), where D, the semantics, is a set of objects partially ordered by \(\geq\), \(\epsilon\), the syntax, or rule space, is a recursively enumerable set of expressions representing objects in D, h is a mapping of \(\epsilon\) onto D, GE? is an oracle for the partial order \(\geq\), \(e_ 1,e_ 2\in \epsilon\), \[ GE?(e_ 1,e_ 2)=\{yes\quad if\quad h(e_ i)\geq h(e_ 2),\quad =no\quad otherwise. \] A training example is a signed expression (s,e), where \(s\in \{+.-\}\) and \(e\in \epsilon\), such that \(d_ 0\geq h(e)\) if s is \(+\) and \(d_ 0\ngeq h(e)\) if s is -. An instance of the identification problem is a pair \((d_ 0,Ex)\), where \(d_ 0\in D\) is a target element to be identified and Ex is an oracle that returns training examples of \(d_ 0\). Ex determines how the indifferent teacher presents information about the target \(d_ 0\). The goal of an identification problem is to construct a learner that, for any instance finds an expression \(e_ 0\) such that \(h(e_ 0)=d_ 0.\) Chapter 2 describes refinement relations, used in generalizing and specializing. Chapter 3 introduces another kind of refinements. Chapters 4 and 5 constitute the second part of the book. Stochastic identification in the limit, probably approximately correct identification, as defined by \textit{L. G. Valiant} in 1984, and identification from noisy examples are studied there.
- Algorithms for learning regular expressions from positive data
- Some deterministic models of concept identification
- Schema induction for logic program synthesis
- Learning in parallel
- The description identification problem
- General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
- Specification and simulation of statistical query algorithms for efficiency and noise tolerance
- Learning with unreliable boundary queries
- Learning with restricted focus of attention
- Sample size lower bounds in PAC learning by Algorithmic Complexity Theory
- PAC-learning a decision tree with pruning
- Learning Boolean concepts in the presence of many irrelevant features
- On the connections between statistical disclosure control for microdata and some artificial intelligence tools
- Improved lower bounds for learning from noisy examples: An information-theoretic approach
- Hypothesis finding based on upward refinement of residue hypotheses.
- Can PAC learning algorithms tolerate random attribute noise?
- Learning fallible deterministic finite automata
- The lattice structure and refinement operators for the hypothesis space bounded by a bottom clause
- PAC-learning in the presence of one-sided classification~noise
- Noise modelling and evaluating learning from examples
- Exact Learning of Discretized Geometric Concepts
- Comparing the power of probabilistic learning and oracle identification under monotonicity constraints
- Learning from Multiple Sources of Inaccurate Data
- scientific article; zbMATH DE number 2080445 (Why is no real title available?)
- An approach to one-bit compressed sensing based on probably approximately correct learning theory
- On the role of search for learning from examples
- scientific article; zbMATH DE number 1875403 (Why is no real title available?)
- Learning concepts and their unions from positive data with refinement operators
- Costs of general purpose learning
- On approximately identifying concept classes in the limit
- Learning Boolean functions in AC^0on attribute and classification noise -- estimating an upper bound on attribute and classification noise
- Four types of noise in data for PAC learning
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4040311)
