Learning Automata from Ordered Examples
Abstract
Connectionist learning models have had considerable empirical success, but it is hard to characterize exactly what they learn. The learning of finite-state languages (FSL) from example strings is a domain which has been extensively studied and might provide an opportunity to help understand connectionist learning. A major problem is that traditional FSl learning assumes the storage of all examples and thus violates connectionist principles. This paper presents a provably correct algorithm for inferring any minimum-state deterministic finite-state automata (FSA) from a complete ordered sample using limited total storage and without storing example strings. The algorithm is an iterative strategy that uses at each stage a current encoding of the data considered so far, and one single sample string. One of the crucial advantages of our algorithm is that the total amount of space, used in the course of learning, for encoding any finite prefix of the sample is polynomial in the size of the inferred minimum state deterministic FSA. The algorithm is also relatively efficient in time and has been implemented. More importantly, there is connectionist version of the algorithm that preserves these properties. The connectionist version requires much more structure than the usual models and has not yet been implemented. But is does significantly extend the scope of connectionist learning systems and helps relate them to other paradigms. We also show that no machine with finite working storage can identify iteratively the FSL from arbitrary presentations.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1988
- Accession Number
- ADA206851
Entities
People
- Jerome A. Feldman
- Sara Porat
Organizations
- University of Rochester