Source-linked AI summary
Towards a universal language of concepts: A survey
Aishni Parab
TL;DR
The paper asks what representation can capture the structure of concepts while supporting learning and generalization from sparse data. It surveys computational concept-learning models that represent concepts with programs, concluding that programs are a strong candidate, though their representation remains difficult to separate from the algorithms used to learn them.
Problem
A universal concept representation must support learning and generalization from few examples while capturing the structure and nature of concepts.
Source: §2 · p. 2Method
Results
Programs are a strong candidate for universal concept representation, with concepts represented as instances of a concept or as interacting entities that can be combined.
Source: §7 · p. 9Takeaways & Limitations
Combining instance-based and interacting-program representations may leverage their individual strengths, while combinatory logic is a proposed direction for representing concepts across domains.
Source: §6.3 · p. 8, §7 · p. 9In practice, combinatory-logic models restrict search to specific domains, leaving unclear whether the representation can be disentangled from its learning algorithm.
Source: §6.2 · p. 8
Abstract
from arXiv · showhide
Humans can learn and generalize novel concepts from sparse data because they express knowledge in rich structural formats. In this paper, we propose that programs are a strong candidate for universal representation of concepts. We review computational models of concept learning that use programs as their concept representation and evaluate their contribution toward a universal representational language.
Author’s note
This work was completed as a 2022 capstone project for the M.S. in Computer Science at the University of California, Los Angeles.
Author’s note
- The work was completed as a 2022 UCLA M.S. in Computer Science capstone project.UCLA is the University of California, Los Angeles.Source: Author’s note · p. 1
1 Introduction
The introduction asks how people represent flexible, compositional concepts and reason about them despite limited cognitive resources. It presents the paper’s evaluation of programs as a candidate representation and reviews computational concept-learning models that use them.
1 Introduction
- Concepts must support flexible transformations and composition, as illustrated by imagining a cow with pink zebra stripes or plans with nested subgoals.Planning examples require reasoning over simple and complex concepts despite limits on working memory and speed.Source: §1 · p. 1
- The paper evaluates the representational demands of concepts and argues that programs are a feasible universal representation.It reviews computational models of concept learning that use programs as their concept representation.Source: §1 · p. 1
- A representation for sophisticated concept manipulation must be readily conceived, stored, retrieved, processed, and updated.These capacities frame the introduction’s account of what a mental representation should support.Source: §1 · p. 1
2 Needed properties of a concept representation
The section argues that a universal concept representation must capture both the structure of concepts and the demands of learning and generalization from sparse examples. It proposes programs as a candidate scaffold for those requirements.
2 Needed properties of a concept representation
- Infants can learn concepts from sparse examples and generalize them, motivating representations that support learning beyond observed instances.The section notes word learning from one example and higher-order generalizations in infants.Source: §2 · p. 2
- Inductive bias constrains the learner’s search space, but a universal representation must capture concepts themselves as well as support rapid learning and generalization.The passage contrasts domain-specific structures with a structural bias broad enough to represent concepts universally.Source: §2 · p. 2
- Concepts combine modular parts and relations, can be abstracted and updated over time, and carry causal and probabilistic properties.The addition example illustrates updating a concept from natural numbers to real numbers.Source: §2 · p. 2
- The section presents programs as structured scaffolding for meeting these representational demands.It proposes defining programs and assessing how they satisfy the demands described above.Source: §2 · p. 2
3 What structural form does a program representation take?
The section describes programs as formal-language sequences whose syntax and semantics can encode operations and other structures. It introduces grammars as a way to specify program forms and priors as a way to favor simpler expressions.
3 What structural form does a program representation take?
- Programs order symbols according to a formal language to express executable instructions, as in the addition function example.The example’s function returns the sum of its two input variables.Source: §3 · pp. 2–3
- A grammar specifies program syntax through tokens, non-terminals, a start symbol, and production rules.The Python function-definition grammar gives rules that can express any Python function definition.Source: §3 · p. 3
- Probabilistic context-free grammars assign distributions over derivations, with priors often favoring shorter, simpler productions.The passage relates this choice to Occam’s razor and minimum description length.Source: §3 · p. 3
- Programs can encode other structured representations, including graphs, suggesting they can subsume alternative structural formats.The passage illustrates this with a graph represented through an adjacency list.Source: §3 · p. 3
- C and Python grammars can express semantically analogous function definitions while retaining language-specific syntactic differences.The C grammar example is attributed to Ritchie et al. [1988].Source: §3 · p. 3
4 What makes programs a good candidate for a universal representation?
Programs meet the section’s representational demands through modularity, abstraction, state change, causality, and uncertainty.
4 What makes programs a good candidate for a universal representation?
- Program modules can be separated, recombined, and grouped to represent concepts at different scales.For example, helper functions can implement a larger function, and member functions can be grouped in a class such as Dog.Source: §4 · p. 4
- Programs support abstraction by grouping expressions into named modules that can be accessed without restating their internal concepts.The paper lists variables, functions, classes, files, and libraries as possible modules.Source: §4 · p. 4
- Overwriting a variable changes program state, paralleling how learned concepts can become more specific or broad.Source: §4 · p. 4
- A function encodes how inputs influence outputs, giving programs a way to model causal structures within and between concepts.Source: §4 · p. 4
- Multiple valid expressions and probabilistic programs allow concepts to have alternative representations and generate varied instances or interpretations.Source: §4 · p. 4
5 Is representation enough for universality?
The section distinguishes program representations from the algorithms that learn them, while noting unresolved questions about priors, learning scope, and efficiency.
5 Is representation enough for universality?
- It remains unclear whether program representation can be separated from algorithms for efficient concept learning under limited cognitive resources.The paper frames learning as running a program forward to generate instances and inferring or synthesizing a program from examples.Source: §5 · p. 4
- If concepts use program representations as inductive bias, the choice of priors and primitives remains an open question.Source: §5 · p. 4
- Computability results establish polynomial-time learning for a class of CNF concepts, but do not explain how concepts beyond that class are learned as humans broadly do.The paper also notes uncertainty over whether human learners begin with intuitive knowledge or a clean slate.Source: §5 · p. 4
- Prior work has proposed efficient searches over program spaces, and the paper next compares program formats and their contributions to universal representation.Source: §5 · p. 5
6 Various ways concepts have been represented as a program in computational models of concept learning
The survey groups program-based concept models into instance sets and interdependent programs, then weighs their strengths and limitations as candidates for a universal representation.
6.1 Concept as a set of all its program instances
- Grammar rules define instance-set concepts and constrain learners to semantically consistent hypotheses and syntactically valid instances.The rules distinguish categories through object features or relations.Source: §6.1 · p. 5
- Logical-rule models use Bayesian inference over grammatically generated hypotheses to predict a rule explaining a concept.The surveyed Rational Rules model restricts concepts to logical connectives, quantifiers, and feature or comparison predicates.Source: §6.1 · p. 5
- For number concepts, a context-sensitive PRCG uses prefix-base-suffix rules and predicate networks to represent compositional and relational structure.The grammar uses number, successor, and predecessor predicates, with relations such as more and less.Source: §6.1 · pp. 5–6, Figure 1 · p. 6
- Probabilistic programs can generate both concept types and examples; Bayesian Program Learning achieved human-level accuracy and outperformed common deep models on Omniglot.The survey also describes variable-bound rules for abstract visual patterns such as ABA and Ring.Source: §6.1 · pp. 6–7, Figure 2 · p. 7
- Domain-specific languages can make hypothesis spaces more tractable, but their restricted primitives and semantics reduce genericity across domains.The surveyed visual systems are tied to their respective domains, unlike the broad, few-example flexibility attributed to humans.Source: §6.1 · p. 7
6.2 Concept as a set of interdependent programs
- Interdependent concepts can be represented with variable-free combinatory logic, where concepts are composed from combinators and gain meaning in context.The paper describes S and K as sufficient to express a wide range of concepts, including a possible representation of logical OR.Source: §6.2 · pp. 7–8
- Combinatory logic is universal in principle, but its large search space leads researchers to restrict evaluation to specific domains, leaving representation and algorithmic use entangled.Piantadosi’s S&K representations are recomputed for each domain, while Liang et al.’s multitask tasks share primitives but may leave some concepts with private primitives.Source: §6.2 · p. 8
6.3 What is the overarching gap?
- Instance-set and interdependent-program views have complementary strengths, but combining them and disentangling representation from algorithmic efficiency remain future directions.The proposed direction includes probabilistic programs based on combinatory logic for learning concepts across multiple domains.Source: §6.3 · p. 8
7 Conclusion
Programs are a strong candidate for universal concept representation, with instances and interacting entities as two approaches whose strengths can ultimately be combined.
7 Conclusion
- Programs are a strong candidate for universal concept representation, expressed either as instances of a concept or as interacting concept entities.The conclusion argues that the two forms can be combined to leverage their individual strengths.Source: §7 · p. 9