|
|
|
|
|
We are thus freed from specifying the number of sides of the coin, and can write the probability function without its subscript t. In the sequel, we shall in fact refer to by pr. |
|
|
|
|
|
|
|
|
9.35 Definition (Pitt [149]) Let . |
|
|
|
|
|
|
|
|
(a) P ProbpTxtEx-identifies L (written: ) just in case for each text T for L . |
|
|
|
|
|
|
|
|
(b) ![0214-005.gif](0214-005.GIF) |
|
|
|
|
|
|
|
|
We now discuss some results about team and probabilistic identification of languages. In the context of functions, it is a simple consequence of the equivalence of team and probabilistic identification that if the success ratio of a team is greater than , then the team can be simulated by a single scientist without any loss in learning power. Such a cut-off ratio is referred to as the aggregation ratio of the team learning paradigm. It is also clear that in the context of functions the only success ratios of interest are of the form with k > 1. |
|
|
|
|
|
|
|
|
The story is different for language identification. First, the aggregation ratio for language identification turns out to be . Second, the notions of team and probabilistic identification fail to coincide in the language case. Probabilistic identification turns out to be strictly more powerful than team identification. Finally, the results for languages arc more difficult to obtain and only a partial picture is known. In what follows, we first present results for team identification of languages with success ratios . This is followed by the presentation of some results for success ratios of the form with k > 2. |
|
|
|
|
|
|
|
|
Team language identification with success ratio ![0214-011.gif](0214-011.GIF) |
|
|
|
|
|
|
|
|
We first consider when a team of scientists can be simulated by a single scientist without loss of learning ability. The next proposition below says that the collections of languages that can be identified by teams with success ratio greater than (that is, more than two-thirds of the members in the team are required to be successful) are the same as those collections of languages that can be identified by a single scientist. |
|
|
|
|
|
|
|
|
9.36 Proposition Suppose j and k are such that . Then . |
|
|
|
|
|
|
|
|
To facilitate the proof of the above proposition and other results in this chapter, we define the following technical notion. |
|
|
|
|