|
|
|
|
|
(b) M is always defined on just in case M is always defined on each . |
|
|
|
|
|
|
|
|
(c) M is always defined just in case M is always defined on each . |
|
|
|
|
|
|
|
|
Clearly ''M is always defined" is the same as "M is total." As discussed in the introduction, we may distinguish the global and the class versions of this strategy. The collections of languages identifiable by the two versions are recorded in the next definition. |
|
|
|
|
|
|
|
|
a) . |
|
|
|
|
|
|
|
|
(b) . |
|
|
|
|
|
|
|
|
As might be expected from Proposition 4.15, requiring that scientists always be defined is not restrictive. The following proposition is simply a restatement of Proposition 4.15. |
|
|
|
|
|
|
|
|
5.3 Proposition [TxtEx]all-def = [TxtEx]class-all-def = TxtEx. |
|
|
|
|
|
|
|
|
It will simplify the formulation of definitions and results in this chapter to limit attention to scientists that are defined on all inputs. We thus enter the following convention. |
|
|
|
|
|
|
|
|
Convention: Just for Chapter 5, the term "scientist" applies only to total functions from SEQ to N (in the language identification paradigm), or to total functions from SEG to N (in the function identification paradigm). |
|
|
|
|
|
|
|
|
Our next strategy captures a natural constraint on hypothesis selection, namely, that each conjecture made by a learner be consistent with the the data seen thus far. |
|
|
|
|
|
|
|
|
5.4 Definition (Angluin [6]) |
|
|
|
|
|
|
|
|
(a) M is said to be consistent on L just in case, for every s with , we have . |
|
|
|
|
|
|
|
|
(b) M is consistent on just in case M is consistent on each . |
|
|
|
|
|
|
|
|
(c) M is consistent just in case M is consistent on each . |
|
|
|
|
|
|
|
|
We first consider the global version of consistency. |
|
|
|
|
|
|
|
|
5.5 Definition . |
|
|
|
|