TRADING SPACES - COMPUTATION, REPRESENTATION, AND THE LIMITS OF UNINFORMED LEARNING

Some regularities enjoy only an attenuated existence in a body of trai ning data. These are regularities whose statistical visibility depends on some systematic recoding of the data. The space of possible recodi ngs is, however, infinitely large - its is the space of applicable Tur ing machines. As a result, mappings that pivot on such attenuated regu larities cannot, in general, be found by brute-force search. The class of problems that present such mappings we call the class of ''type-2 problems''. Type-1 problems, by contrast, present tractable problems o f search insofar as the relevant regularities can be found by sampling the input data as originally coded. Type-2 problems, we suggest, pres ent neither rare nor pathological cases. They are rife in biologically realistic setting sand in domains ranging from simple animat (simulat ed animal or autonomous robot) behaviors to language acquisition. Not only are such problems rife - they are standardly solved! This present s a puzzle. How, given the statistical intractability of these type-2 cases, does nature turn the trick? One answer, which we do not pursue, is to suppose that evolution gifts us with exactly the right set of r ecoding biases so as to reduce specific type-2 problems to (tractable) type-1 mappings. Such a heavy-duty nativism is not doubt sometimes pl ausible. But we believe there are other, more general mechanisms also at work. Such mechanisms provide general (not task-specific) strategie s for managing problems of type-2 complexity. Several such mechanisms are investigated. At the heart of each is a fundamental poly - namely, the maximal exploitation of states of representation already achieved by prior, simpler (type-1) learning so as to reduce the amount of sub sequent computational search. Such exploitation both characterizes and helps make unitary sense of a diverse range of mechanisms. These incl ude simple incremental learning (Elman 1993), modular connectionism (J acobs et al. 1991), and the developmental hypothesis of ''representati onal redescription'' (Karmiloff-Smith 1979; 1992). In addition, the mo st distinctive features of human cognition - language and culture - ma y themselves be viewed as adaptations enabling this representation/com putation trade-off to be pursued on an even grander scale.