54,326
edits
1988 QueriesandConceptLearning: Difference between revisions
Jump to navigation
Jump to search
→1.2 Exact and probabilistic identification
| Line 66: | Line 66: | ||
==== 1.2 Exact and probabilistic identification ==== | ==== 1.2 Exact and probabilistic identification ==== | ||
The abstract examples we consider include sets of strings generated by grammars or recognized by automata and sets of truth | The abstract examples we consider include sets of strings generated by grammars or recognized by automata and sets of truth-value assignments that satisfy certain classes of propositional formulas. We consider two criteria of successful identification, exact and probabilistic. | ||
<P> | <P> | ||
An identification method exactly identifies a set | An identification method exactly identifies a set <math>L_*</math> with access to certain types of queries if it always halts and outputs an index <math>i</math> such that <math>L_i = L_*</math> Note that this is not a limiting criterion of identification — the identification method is allowed one guess, and that guess must be exactly right. In contrast, Valiant (1984) has introduced a criterion of probabilistic identification, and here we give a definition suitable for this paper. There is some probability distribution <math>D</math> on the universal set <math>U</math>. The probability of element <math>x</math> with respect to <math>D</math> is denoted <math>Pr(z)</math>. There is a sampling oracle EX( ), which has no input. Whenever EX( ) is called, it draws an element <math>x \in U</math> according to the distribution <math>D</math> and returns the element <math>x</math>, together with an indication of whether or not at is in the target set <math>L_*</math>. | ||
<P> | <P> | ||
Successful identification is parameterized with respect to two positive quantities, the accuracy parameter c and the confidence parameter 6. We define a notion of the difference between two sets L and L' with respect to the probability distribution as | Successful identification is parameterized with respect to two positive quantities, the accuracy parameter c and the confidence parameter 6. We define a notion of the difference between two sets <math>L</math> and <math>L'</math> with respect to the probability distribution as | ||
<P> | <P> | ||
<div style="text-align:center"><math> | <div style="text-align:center"><math> d(L,L')=\sum_{x\in L\oplus L'} Pr(x) </math></div> | ||
<P> | <P> | ||
The probability of getting an element in one but not the other of the two sets L and L’ in one call to EX( ) is precisely d(L, L’). | The probability of getting an element in one but not the other of the two sets L and L’ in one call to EX( ) is precisely d(L, L’). | ||
| Line 78: | Line 78: | ||
An identification method is said to probably approximately correctly identify L if it always halts and outputs an index 2' such that | An identification method is said to probably approximately correctly identify L if it always halts and outputs an index 2' such that | ||
<P> | <P> | ||
<div style="text-align:center"><math> | <div style="text-align:center"><math> ... </math></div> | ||
<P> | <P> | ||
That is‘ with high probability (quantified by 6) there is not too much difference (quantified by 6) between the conjectured set and the target set. | That is‘ with high probability (quantified by 6) there is not too much difference (quantified by 6) between the conjectured set and the target set. | ||