COMPUTATIONAL CAPABILITIES OF LOCAL-FEEDBACK RECURRENT NETWORKS ACTING AS FINITE-STATE MACHINES

In this paper we explore the expressive power of recurrent networks wi th local feedback connections for symbolic data streams, We rely on th e analysis of the maximal set of strings that can be shattered by the concept class associated to these networks (i.e., strings that can be arbitrarily classified as positive or negative), and find that their e xpressive power is inherently limited, since there are sets of strings that cannot be shattered, regardless of the number of hidden units. A lthough the analysis holds for networks with hard threshold units, we claim that the incremental computational capabilities gained when usin g sigmoidal units are severely paid in terms of robustness of the corr esponding representation.