Cognitive psychology has studied how people encode, use, and learn concepts that describe categories, and how they represent, recognize, and acquire chunks for familiar patterns of elements. The literatures on these two topics are nearly disjoint, which poses a challenge for unified theories of cognition. In this paper, we review Cobweb, a computational account of categorization and concept formation, then propose an extended theory that incorporates chunks and their acquisition. The theory makes no commitments about modality, applying to any experience that decomposes into elements and relations among them. We also present \trellis/, an implementation of this theory, and illustrate its application to learning context-free grammars, which we adopt as a testbed because they involve both concept-like and chunk-like elements. In addition, we report experimental results on learning for three synthetic grammars that demonstrate the system's ability to represent syntactic knowledge, use it to parse and generate sentences, and learn compositional structures from sample parses. We conclude by discussing related work on concepts and chunks, along with directions for future research on the problem.
Figures & tables
Figure 1: Modules of Trellis and the flow of an experience through them. Parsing composes primitive elements into a partonomic tree, consulting the content and context taxonomies that make up long-term memory, while generation inverts the process. Section 3 defines the terms set in italics.
Figure 2: One primitive (“cat”, green) and one composite (“saw a dog”, amber) from a parse of “the cat saw a dog”. Each box header is the long-term memory identifier to which the instance was sorted. The composite’s content field points into the context hierarchy, keeping the two descriptions in complementary formats. Window width, distance weighting, and content-bag width are run-time values (Appendix B).
Figure 3: Leaf-level subtrees of the content (left) and context (right) hierarchies. Arrows show the cross-hierarchy link: a content leaf’s child fields name the context concepts that describe its children.
Figure 4: Trellis ’ two performance modules. (a) Parsing (1) forms candidate chunks over adjacent frontier elements; (2) sorts each through both taxonomies, admitting it iff some nonroot ancestor on the sort path has count above τparse , ranking the admitted candidates by sc+sx ; (3) commits the top-ranked one to the parse tree. (b) Generation (1) selects the next seed; (2) samples a fresh content leaf from a well-supported neighborhood above it; (3) resolves each of the sampled leaf’s two child references against the class the parent expects; (4) expands the seed with these results. The numeric values in a2 are for illustration only.
Figure 5: 1−omissionrate (parse, left of each pair) and 1−commissionrate (generation, right of each pair), across (a) the three grammars and (b) the three lexicon sizes (five data sets, ±1σ band).
Figure 6: Content (top) and context (bottom) taxonomies after training on the med grammar. Each node shows the distribution of syntactic classes among the elements sorted through it, with n the number of such elements. For content nodes the upper and lower bars give the left and right constituent, respectively. Red borders mark basic-level nodes, and the legend applies to both panels. The labels are only for inspection purposes and play no role in learning. Nodes become nearly pure well above the leaves, which is the generalization that lets one chunk cover many fillers.