No label defined (Q4040311)

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.