Abstract Florencio
In \cite{Disco,datauni} `discovery procedures' for Classical Categorial Grammars were defined that accept a sequence of structures (i.e. analyzed strings) as input and yield a set of grammars. In \cite{Kanazawa} it was shown that some of the classes based on these procedures are learnable (in the sense of identification in the limit) from structures, and some functions were defined that learn these classes under certain restrictions on their behaviour.Two variants were studied, one that is conservative and one that is set-driven. This paper answers the (open) question whether the set-driven version is conservative.
Let $\varphi_{\mathrm{VG}_{k}}$ be a learning function that only updates its hypothesis if current data is not consistent with the previous hypothesis, and when updating chooses a grammar from $H = \mathrm{VG}_{k}(D)$ that generates a structure language that is minimal with respect to $H$. This is a construction that is guaranteed to be conservative: it ignores input that fits into the current hypothesis. I have shown that the set-driven learning function $\varphi^{\flat}_{\mathrm{VG}_k}$ is not conservative by defining an input-sample that fulfills sufficient conditions mentioned in a foot note on page 102 of \cite{Kanazawa}.
This sample has been verified using Kanazawa's Prolog implementation of the $k$- valued grammar algorithm.
Last modified $Date: 2001/10/04 13:39:45 $ by Parlevink Webmaster