Inductive inference from noisy examples: The rule-noise dilemma and the hybrid finite state filter

Recently, it has been shown that recurrent neural networks can be used as adaptive neural parsers. Given a set of positive and negative examples, picked up from a given language, adaptive neural parsers can effectively be trained to recognize its grammar. Many efforts have been focused on regular languages for which the continuous computation can be approximated by the set of transition rules of a finite state machine. In this paper we face the problem of inferring grammars from positive and negative examples that, however, may be corrupted by a noise that simply changes the membership of the strings. We propose using second-order recurrent networks and suggest a training algorithm, referred to as HFF (hybrid Finite state Filter), based on a parsimony principle that penalizes the development of complex rules.