5.4.2 Monotonic Learning
Definition
5.10
Monotonic Learning (\(\mathrm{Mon}\mathbf{Ex}\))
A learner monotonically \(\mathbf{Ex}\)-identifies \(L\) if it \(\mathbf{Ex}\)-identifies \(L\) and, whenever it changes its hypothesis from \(e\) to \(e'\), the new hypothesis is at least as inclusive on the data seen so far: \(W_e \cap \{ t_0, \ldots , t_n\} \subseteq W_{e'} \cap \{ t_0, \ldots , t_n\} \). Once a datum is correctly classified, that classification is never retracted.
Monotonic learning strengthens \(\mathbf{Ex}\) by adding a constraint. The class of \(\mathrm{Mon}\mathbf{Ex}\)-identifiable families is a strict subset of \(\mathbf{Ex}\)-identifiable families. In the graph, \(\textsf{\small monotonic\_ learning} \xrightarrow {\texttt{\small restricts}} \textsf{\small ex\_ learning}\).