Learning from a Substructural Perspective

In: Proceedings of CoNLL-2000 and LLL-2000, pages 176-183, Lisbon, Portugal, 2000. Learning from a Substructural Perspective Pieter Adriaans and Erik de Haas Syllogic, P.O. Box 2729, 3800GG Amersfoort, The Netherlands, and University of Amsterdam, Fac. of Mathematics, Computer Science, Physics and Astronomy, Plantage Muidergracht 24, 1018TV Amsterdam, The Netherlands pieter, adriaans@ps.net, erik@propersolution.nl Abstract In this paper we study learning from a logical perspective. We show that there is a strong re- lationship between a learning strategy, its for- mal learning framework and its logical represen- tational theory. This relationship enables one to translate learnability results from one theory to another. Moreover if we go from a classi- cal logic theory to a substructural logic theory, we can transform learnability results of logical concepts to results for string languages. In this paper we will demonstrate such a translation by transforming the Valiant learnability result for boolean concepts to a learnability :result for a class of string pattern languages. 1 Introduction There is a strong relation between a learn- ing strategy, its formal learning framework and its representational theory. Such a representa- tional theory typically is (equivalent to) a logic. As an example for this strong relationship as- sume that the implication A ~ B is a given fact, and you observe A; then you can deduce B, which means that you can learn B from A based on the underlying representational the- ory. The learning strategy is very tightly con- nected to its underlying logic. Continuing the above example, suppose you observe -~B. In a representational theory based on classical logic you may deduce ~A given the fact A ~ B. In intuitionistic logic however, this deduction is not valid. This example shows that the char- acter of the representational theory is essential for your learning strategy, in terms of what can be learned from the facts and examples. In the science of the representational theo- ries, i.e. logic, it is a common approach to connect different representational theories, and transform results of one representational theory to results in an other representational theory. Interesting is now whether we can transform learnability results of learning strategies within one representational theory to others. Observe that to get from a first order calculus to a string calculus one needs to eliminate structural rules from the calculus. Imagine now that we do the same transformation to the learning strategies, we would come up with a learning strategy for the substructural string calculus starting from a learning strategy for the full first order calculus. The observation that learning categorial grammars translates to the task of learning derivations in a substructural logic theory moti- vates a research program that investigates learn- ing strategies from a logical point of view (Adri- aans and de Haas, 1999). Many domains for learning tasks can be embedded in a formal learning framework based on a logical repre- sentational theory. In Adriaans and de Haas (1999) we presented two examples of substruc- tural logics, that were suitable representational theories for different learning …

Content truncated to 500 words