|
|
|
|
|
Team Language Identification for Success Ratios ![0217-001.gif](0217-001.GIF) |
|
|
|
|
|
|
|
|
We first discuss results for success ratio . In the context of functions, the following result immediately follows from Proposition 9.33. |
|
|
|
|
|
|
|
|
9.41 Corollary (Pitt [149], Pitt and Smith [151]) For all j > 0, . |
|
|
|
|
|
|
|
|
This result says that the collections of functions that can be identified by a team with success ratio 1/2 are the same as those collections of functions that can be identified by a team employing two scientists and requiring at least one to be successful. Consequently, . In other words, there is nothing to be gained by introducing redundancy into a team learning functions. |
|
|
|
|
|
|
|
|
Surprisingly, in the context of language identification, Proposition 9.42 below implies that for success ratio there is something to be gained by introducing redundancy. As a consequence of this result, a direct analog of Pitt's connection for function inference does not lift to language learning. |
|
|
|
|
|
|
|
|
A proof of this result can be obtained by a somewhat complex version of the proof of Proposition 9.40. We direct the reader to Jain and Sharma [92] for the details. |
|
|
|
|
|
|
|
|
9.42 Theorem . |
|
|
|
|
|
|
|
|
Even more surprising is the next proposition, which implies that the collections of languages that can be identified by teams employing six scientists and requiring at least three to be successful are exactly the same as those collections of languages that can be identified by teams employing two scientists and requiring at least one to be successful! |
|
|
|
|
|
|
|
|
9.43 Proposition For all j, . |
|
|
|
|
|
|
|
|
Proof: Let j be as given in the hypothesis of the proposition. Suppose a team consisting of scientists M1, M2, . . . , M4j+2 . We describe two scientists, and , that . |
|
|
|
|
|
|
|
|
Let cony be as defined in the proof of Proposition 9.36. Let , , . . ., be a permutation of 1, 2, . . . , 4j + 2 such that, for each r = 1, . . . , 4j + 1, |
|
|
|
|
|
|
|
|
For each r and s , define |
|
|
|
|