PaperlayerView exact revision on arXiv

Source-linked AI summary

Complexity Induction: Compositional Generalization via Structured Label Distortion

Aleksandr Abramov

arXiv:2608.21464v1cs.CVcs.AIcs.LG

TL;DR

The paper asks whether structured complication of training signals can induce compositional generalization without explicit attribute decomposition or architectural changes. It introduces complexity induction through similarity-based mixed labels and expanded false-label training, finding that both support prediction of unseen combinations while operating on different levels of representation and classification.

  • Problem

    The paper examines whether structured distortion can induce compositional generalization in classifiers trained on flat labels when some color-shape combinations are absent.

  • Method

    The authors train a standard CNN on synthetic colored shapes using Jaccard-like class-name similarity to construct mixed labels and an expanded dataset with structurally motivated false labels.

  • Results

    Both distortion methods support prediction of unseen combinations: mixed labels activate a partially factorized embedding, while expanded training improves embedding factorization; random false labels degrade it.

  • Takeaways & Limitations

    Structured complication of training signals can produce compositional generalization and influence both learned representation organization and classifier interpretation.

  • Takeaways & Limitations

    The evidence is limited to synthetic geometric data, a small class space, and one CNN architecture, so transfer to natural images and larger scales remains open.

Abstract

from arXiv · show

We demonstrate that structured distortion of training data - which we term complexity induction - can induce compositional generalization in a standard CNN classifier without architectural modification. Using synthetic images of colored geometric shapes, we encode classes as flat string labels (e.g., "red-circle") with no explicit attribute decomposition, and exclude certain color-shape combinations from training entirely. We apply two distortion methods derived from Jaccard string similarity between class names: mixed labels (soft target distributions encoding inter-class overlap) and expanded dataset (false training samples with structurally motivated incorrect labels). Both methods induce the ability to predict unseen class combinations, and act at different levels: mixed labels activate the classifier for unseen combinations by exploiting the CNN's natural embedding structure, while expanded training improves the embedding factorization itself. A control with random (unstructured) false labels confirms that the effect depends on the structure of the distortion, not on noise per se. These results suggest that structured complication of training signals can influence both the internal organization of learned representations and their compositional interpretation - a principle that may underlie the role of natural language in cognitive development.

I. INTRODUCTION

The paper asks whether structured distortion of training signals can induce compositional generalization in a standard classifier, even when training classes are flat labels and some combinations are held out. It tests this with synthetic colored shapes, two string-similarity-based distortions, and deliberately excluded color-shape pairs.

  • Motivation: Structured distortion is tested as a way to make a standard classifier predict color-shape combinations absent from training.The study challenges the premise that training signals should guide models only toward correct mappings.
  • Experimental setup: The experiment uses synthetic geometric images with color and form, providing control over object properties.
  • Experimental setup: Classes are monolithic labels such as “red-circle,” with no architectural or data-level indication that they contain attributes.
  • Experimental setup: Certain color-shape pairs are excluded from training entirely and reserved for evaluation as holdout combinations.
  • Distortion methods: Mixed labels encode overlap between class names, while expanded datasets add false copies with structurally motivated incorrect labels.

II. RELATED WORK

The paper distinguishes its approach from methods that explicitly decompose classes, use externally sourced relationships, or mitigate label noise. Instead, it uses structured distortion on flat labels to investigate internally induced compositional separation.

  • Compositional zero-shot learning: Unlike compositional zero-shot methods, this approach does not explicitly decompose classes into attribute pairs.
  • Compositional zero-shot learning: The method investigates whether structured label mixing alone can induce internal attribute separation without architectural or data-level decomposition.
  • Label smoothing: Its soft targets derive from class-name string similarity rather than external semantic or structural knowledge.
  • Noisy labels and latent generalization: A linear probe on frozen features can recover compositional generalization that the original classifier fails to express.
  • Noisy labels and latent generalization: Unlike noisy-label research, the paper treats structured label distortion as a productive mechanism rather than corruption to mitigate.

E. Data Augmentation with False Samples

The expanded-dataset method deliberately violates label-preservation assumptions by adding false samples whose incorrect labels are generated from structured similarity among flat class names.

  • False-sample augmentation: Expanded datasets add false copies of training images with incorrect but structurally motivated class assignments.
  • False-sample augmentation: The two proposed distortions share one class-name similarity function, with mixed labels modifying targets and expanded datasets adding false samples.
  • Label structure: Each class combines color and shape, with names such as red-circle and blue-triangle formed by concatenating the two properties.
  • Label structure: These class names are treated as atomic labels, so compositional structure exists only in the strings rather than in the classifier’s representation of the class space.
  • Similarity function: The similarity function measures shared component character lengths syntactically, independently of perceptual or semantic similarity.

C. Mixed Labels

Mixed-label training replaces one-hot targets with normalized soft distributions whose non-true-class values reflect class-name similarity, then optimizes the same soft cross-entropy framework.

  • Target construction: Mixed training constructs a soft target vector for each sample from its true class and similarities to other class names.
  • Target construction: The true class retains value 1.0, while other classes receive non-zero values proportional to their name similarity with the true class.
  • Optimization: Mixed labels are normalized and used with a soft cross-entropy loss.
  • Optimization: The loss encourages probability mass to follow the mixed target distribution and encode relationships derived from the similarity function.
  • Optimization: With one-hot targets, the soft loss is equivalent to standard cross-entropy, so standard and mixed training use the same loss function.

D. Expanded Dataset

The expanded dataset method adds false copies of training images with structurally motivated incorrect labels, with assignment probabilities determined by class-name similarity. Training retains the original correctly labeled images and excludes holdout classes from false assignments.

  • D. Expanded Dataset: For each training image of class j, false copies receive candidate class i assignments with probability β · S(cj, ci).β controls the proportion of false entries, and only candidates with positive similarity are considered.
  • D. Expanded Dataset: False copies use standard one-hot labels for their assigned classes, while holdout classes are excluded from false assignments.
  • D. Expanded Dataset: The expanded dataset combines original correctly labeled images with structurally motivated incorrect copies of those same images.An image of a red circle may also appear with the label “red-triangle,” modeling associations from shared linguistic fragments.
  • D. Expanded Dataset: Synthetic 64×64 RGB images contain one geometric shape whose color and form define the class, with randomized visual parameters and added noise.
  • D. Expanded Dataset: The 3 shapes × 4 colors produce K = 12 combinations, with two held out entirely and the remaining 10 split into training and validation sets.The holdout configurations are Holdout A (red-circle + yellow-triangle) and Holdout B (green-circle + blue-triangle).

C. Model Architecture

The model uses a CNN to produce a 64-dimensional embedding followed by a single linear classifier over K classes. This constrained architecture makes the embedding’s factorization and holdout separability directly inspectable.

  • C. Model Architecture: The CNN feature extractor produces a 64-dimensional embedding that the linear classifier maps to K classes.
  • C. Model Architecture: The CNN comprises four convolutional blocks, with the final 4 × 4 convolution reducing spatial dimensions to 1 × 1 and producing the embedding.
  • C. Model Architecture: A single 64 → K linear layer without hidden nonlinearities requires classes to be linearly separable in the embedding space.Correct holdout prediction therefore indicates that unseen classes occupy separable regions despite having no training samples.
  • C. Model Architecture: Training runs for 50 epochs with Adam at learning rate 10^-3 and ReduceLROnPlateau scheduling, selecting the checkpoint with lowest training loss.
  • C. Model Architecture: Each configuration is repeated 50–100 times with fresh initialization, and holdout performance is reported as per-class accuracy with 95% binomial confidence intervals.

V. MIXED TRAINING RESULTS

Standard one-hot training fits seen combinations but produces no holdout predictions, whereas mixed-label training yields non-zero compositional generalization. The effect is unstable across runs and asymmetric across holdout configurations.

  • V. MIXED TRAINING RESULTS: 0% holdout accuracy occurs across all standard one-hot runs and both holdout configurations despite greater than 99% accuracy on the 10 training combinations.
  • V. MIXED TRAINING RESULTS: Mixed-label training reaches average per-class accuracies of 70.8% for red-circle and 56.7% for yellow-triangle in Holdout A.Both holdout classes are predicted with non-trivial accuracy in most of 80 independent runs.
  • V. MIXED TRAINING RESULTS: Holdout accuracy varies from below 0.1 to above 0.9 across runs, showing that non-zero generalization is robust while its magnitude depends on initialization.
  • V. MIXED TRAINING RESULTS: Holdout B is asymmetric: green-circle averages 41.9% accuracy, whereas blue-triangle averages 0.2% and is almost never predicted correctly.The same architecture and mixed-training method therefore performs unevenly across unseen classes.
  • V. MIXED TRAINING RESULTS: The results motivate testing whether compositional generalization originates in the embedding representation or in the classifier mapping embeddings to classes.

VI. LOCATING THE EFFECT: PROBE EXPERIMENT

A probe experiment freezes a CNN trained with standard labels and retrains only a fresh linear classifier with mixed labels. The resulting holdout performance shows that standard training already creates partial embedding factorization, while mixed labels activate it.

  • VI. LOCATING THE EFFECT: PROBE EXPERIMENT: If the frozen embedding is factorized, a newly trained linear classifier should recover unseen classes from linearly separable embedding regions.
  • VI. LOCATING THE EFFECT: PROBE EXPERIMENT: The probe freezes the standard-trained CNN, re-initializes its 64 → K classifier, and trains only that classifier on mixed labels.The full model first achieves greater than 99% validation accuracy and 0% holdout accuracy under standard training.
  • VI. LOCATING THE EFFECT: PROBE EXPERIMENT: The probe averages 0.773 accuracy on Holdout A and 0.412 on Holdout B, comparable to full mixed training.Holdout A accuracies are 70.7% and 83.8%; Holdout B accuracies are 74.3% and 10.4% for the named classes.
  • VI. LOCATING THE EFFECT: PROBE EXPERIMENT: These probe results indicate that standard training already produces a partially factorized embedding, so mixed labels are not required to create that factorization.
  • VI. LOCATING THE EFFECT: PROBE EXPERIMENT: Persistent poor prediction of blue-triangle indicates that the asymmetry originates in embedding structure rather than whether mixed labels train the full model or only the classifier.

A. Expanded Probe Design

The expanded-probe experiment compares structured and random false-label training against a standard probe across two holdout configurations. Structured expansion improves holdout behavior and produces more distributed embeddings, whereas random expansion generally degrades performance.

  • Probe conditions: The comparison evaluates standard, structured-expanded, and random-expanded probes across Holdout A and Holdout B.The probes differ in Phase 1 training, while the classifier-probe comparison is conducted across both holdout configurations.
  • Results: 37.6%: blue-triangle accuracy improves from 10.4% with the standard probe after structured expansion.The structured expanded dataset yields particularly notable gains on this previously problematic class.
  • Control: Random expansion performs worse than the standard probe on most metrics, indicating that unstructured noise degrades rather than enhances embedding factorization.Random expansion uses the same number of false entries but assigns classes uniformly at random.
  • Results: Structured expansion shifts the Holdout B accuracy distributions rightward for both classes, including blue-triangle.This comparison is reported for green-circle and blue-triangle.
  • Embedding visualization: The expanded model produces more systematic spatial separation in t-SNE embeddings, with holdout classes positioned between related training classes.The expanded representation is more spatially distributed rather than collapsing holdout classes onto a single neighboring cluster.

VIII. DISCUSSION

Complexity induction operates through two mechanisms: mixed labels exploit a partially factorized embedding, while expanded training improves embedding organization through structured false labels. Together, these findings motivate a parallel with how language may connect perceptual structure to compositional categories, while the demonstration remains limited in scope.

  • Mechanisms: Mixed labels act on the classifier by exploiting a partially factorized embedding already produced by standard CNN training.They assign non-zero weights to regions corresponding to unseen combinations without restructuring the embedding.
  • Mechanisms: Expanded training acts on the embedding by using structured false labels to produce more distributed, linearly separable representations.The expanded model places holdout classes between related training classes, whereas random false labels degrade factorization.
  • Mechanisms: Random distortion degrades rather than enhances embedding factorization, indicating that the effect depends on structured distortion rather than noise alone.
  • Language and cognition: The authors suggest that language could both strengthen perceptual feature separation and connect it to a combinatorial category system.This proposed parallel links expanded training with embedding factorization and mixed labels with classifier activation for unseen combinations.
  • Scope and directions: The demonstration uses one simple CNN, synthetic geometric data, and surface-level string similarity, leaving richer language structure and broader architectures for future study.Suggested extensions include developmental schedules for distortion and nested levels of structure.

IX. LIMITATIONS

The findings are constrained by the synthetic, small-scale setting, limited architectural coverage, run-to-run variability, and simplified connection to natural language.

  • The effect has only been demonstrated on synthetic images of simple geometric shapes, so transfer to richer natural images remains open.
  • The class space is small (K = 12), and behavior at larger scales requires further exploration.
  • Only one CNN architecture was tested, while model capacity and architecture may affect susceptibility to complexity induction.The linear classifier constraint may limit generality, since deeper classifiers might compensate for poor embedding factorization.
  • Holdout accuracy varies substantially across runs and is often asymmetric, with quantitative outcomes depending on initialization and holdout combination.
  • The natural-language connection is a motivating analogy based on a highly simplified Jaccard model that does not capture language's full interaction with perception and learning.
Loading 2608.21464v1…