A Compression Based Classification Framework Using Symbolic Dynamics of Chaotic Maps

This paper introduces ChaosComp, a novel classification framework that leverages symbolic dynamics and chaotic maps to model class-specific transition probabilities, assigning labels based on the shortest compressed representation of test data to reinterpret classification through the lens of dynamical systems and information theory.

The Gist

Imagine you are trying to teach a computer how to tell the difference between two types of fruit, say Apples and Oranges.

Usually, machine learning works like a detective looking for clues: "If it's red and round, it's an apple. If it's orange and bumpy, it's an orange." It builds a complex rulebook based on the data it sees.

This paper proposes a completely different approach. Instead of building a rulebook, they treat the data like a secret code and ask a simple question: "Which fruit's secret language can I write down the shortest way?"

Here is how their method, called ChaosComp, works, explained through a story.

1. The Chaos Map (The Loom)

Imagine you have a magical loom (a machine for weaving). This loom is a "Chaotic Map." It takes a number, stretches it, cuts it, and rearranges it in a very specific, unpredictable way.

• If you feed it a number representing an Apple, the loom weaves a specific pattern.
• If you feed it a number representing an Orange, it weaves a different pattern.

The magic is that this loom is chaotic. Tiny changes in the starting number lead to wildly different patterns. But, if you know the exact rules of the loom, you can reverse the process.

2. Turning Data into a String of Beads (Symbolic Dynamics)

The researchers take their data (like the size, weight, and color of a fruit) and turn it into a simple string of beads: 0s and 1s.

• If a feature is "small," it's a 0.
• If it's "big," it's a 1.

So, an Apple might look like 0-1-0-1-1, and an Orange might look like 1-0-1-0-0.

3. Learning the "Language" of Each Class (Training)

During the training phase, the computer looks at all the Apples it has ever seen. It counts how often the bead patterns appear.

• "Oh, Apples usually have 0-1 together often, but 1-1 is rare."
• "Oranges love 1-0 but hate 0-0."

Based on these counts, the computer builds a custom loom for Apples and a different custom loom for Oranges. Each loom is tuned specifically to the "rhythm" of that fruit.

4. The Compression Test (The "Zip File" Trick)

Now, you bring in a mystery fruit. You turn it into a bead string.

• Step A: You try to feed this string into the Apple Loom. You run the loom backwards (like rewinding a tape). The loom tries to find the original starting number that would create this exact string.
  • If the string fits the Apple pattern perfectly, the loom finds a very specific, tiny starting number. This means the "Apple Loom" understands this data very well.
  • If the string is weird for an Apple, the loom gets confused, and the starting number becomes a huge, vague range.
• Step B: You do the same with the Orange Loom.

The Golden Rule: The paper uses a principle from information theory called Minimum Description Length.

• If the "Apple Loom" can explain the mystery fruit using a very tiny, precise starting number, it means the data is highly compressible for Apples. It's like saying, "I can describe this fruit in just 3 words because it fits my Apple dictionary perfectly."
• If the "Orange Loom" needs a huge, vague range to explain it, it's a bad fit. It's like trying to describe an Apple using an Orange dictionary; you need 100 words to explain why it doesn't fit.

The Winner: The fruit that results in the shortest description (the smallest "file size") wins. If the mystery fruit can be compressed into a tiny file using the Apple model, the computer says, "It's an Apple!"

Why is this cool?

• It's like a Zip file: Think of the computer not as a classifier, but as a file compressor. It asks, "Which class's dictionary allows me to zip this file down to the smallest size?"
• It handles chaos: Real-world data is messy and chaotic. This method embraces that chaos instead of fighting it. It uses the mathematical properties of "chaotic maps" (which are known to be incredibly efficient at encoding information) to do the work.
• No complex rules: It doesn't need to draw complex lines on a graph to separate classes. It just checks which "language" the data speaks most fluently.

The Results

The researchers tested this on real-world problems, like detecting breast cancer from medical scans or identifying different types of seeds.

• On the Breast Cancer dataset, their method was incredibly accurate (95%+), beating many traditional methods.
• It even solved tricky logic puzzles (like the XOR problem) that usually confuse simple machines, proving it can handle non-linear, messy data.

The Bottom Line

This paper suggests that learning is just compression. If a machine truly "understands" a category of data, it should be able to describe it using the fewest possible bits. By using chaotic maps as a tool to measure this "compressibility," they built a new kind of classifier that is simple, elegant, and surprisingly powerful.

Technical Summary

1. Problem Statement

The paper addresses the classification problem from a unique perspective: data compression and dynamical systems, rather than traditional function approximation or probabilistic inference.

• Core Challenge: How to classify data by modeling each class as a distinct dynamical system and determining which system can "compress" a test instance most efficiently.
• Theoretical Gap: While Minimum Description Length (MDL) principles suggest that the best model minimizes the total description length of the model and data, practical implementations often struggle with complex, non-linear data structures. This paper proposes using chaotic maps (specifically the Baker's map) to implement Shannon-optimal arithmetic coding for classification.

2. Methodology: The ChaosComp Framework

The proposed method, ChaosComp, operates on the principle that a class-specific chaotic map can generate a symbolic sequence from data. If the data belongs to that class, the map will compress the data efficiently (resulting in a short description length).

A. Preprocessing

1. Normalization: All features are scaled to the interval $[0, 1]$ using MinMax scaling.
2. Dimensionality Augmentation: If the number of features $k < 30$, a new feature (sum of squares of original features) is added to ensure stability during backward iteration.
3. Binarization: Continuous data is converted to binary symbols ($0$ or $1$) using a threshold hyperparameter.
4. Padding: If the feature count is not a multiple of the block length $n$, dummy symbols are appended to ensure complete block coverage.

B. Training Phase: Model Construction

For a dataset with $m$ classes:

1. Symbolic Sequence Generation: Training data is binarized and segmented into non-overlapping blocks of length $n$ (e.g., pairs for $n=2$).
2. Empirical Probability Estimation: For each class, the frequency of every possible $n$-length binary pattern (e.g., 00, 01, 10, 11 for $n=2$) is calculated.
3. Map Construction: A specific $n$-th Return Baker's Map is constructed for each class.
   • The unit interval $[0, 1)$ is partitioned into $2^n$ subintervals.
   • The width of each subinterval corresponds to the empirical probability of the associated symbolic pattern for that class.
   • The map is piecewise-linear and expanding, ensuring ergodicity and chaos.
4. Smoothing: Laplace smoothing is applied to prevent zero probabilities, which would break the backward iteration process.

C. Testing Phase: Classification via Backward Iteration

1. Symbolization: A test instance is binarized using the optimal threshold found during hyperparameter tuning.
2. Backward Iteration (Dynamical Reconstruction):
   • For each class model, the algorithm performs backward iteration on the symbolic sequence.
   • Starting from the final symbol, the algorithm iteratively maps the interval $[0, 1)$ backwards through the class-specific map.
   • This process reconstructs the initial interval $[L, U]$ that would generate the observed symbolic sequence under that specific class's dynamics.
3. Compression Metric: The length of the final interval, $\ell = U - L$, represents the probability of the sequence under that model. The compressed file size is calculated as:
   $$\text{Size} = \lceil -\log_2(U - L) \rceil$$
4. Decision Rule: The class yielding the shortest compressed file size (smallest interval length) is selected as the predicted label.
   • Tie-breaking: If multiple classes yield the same size, cosine similarity between the test sample's probability vector and the class's empirical probability vector is used.

3. Key Contributions

• Novel Classification Paradigm: Introduces a classification framework where the "learning" process is the construction of a class-specific chaotic dynamical system, and "inference" is the measurement of compression efficiency.
• Shannon-Optimal Coding via Chaos: Extends the theoretical proof that piecewise-linear chaotic maps (like the Baker's map) achieve Shannon entropy rates for source coding to the context of multi-class classification.
• Higher-Order Symbolic Dynamics: Generalizes the standard Baker's map to $n$-th return maps, allowing the model to capture higher-order sequential dependencies (e.g., pairwise or block correlations) rather than just single-symbol statistics.
• Non-Linearity Handling: Demonstrates the ability to solve non-linearly separable problems (like XOR, NAND, NOR) naturally through the non-linear dynamics of the chaotic maps, without explicit kernel transformations.

4. Experimental Results

The authors evaluated ChaosComp on synthetic and real-world datasets, comparing it against Logistic Regression, SVM, Decision Trees, k-NN, and Naive Bayes.

• Synthetic Data: Successfully solved the XOR problem and other logical gates with perfect accuracy, visualizing complex non-linear decision boundaries.
• Real-World Datasets:
  • Breast Cancer Wisconsin: Achieved a Macro F1-score of 0.9531, outperforming Decision Trees and matching SVM/Logistic Regression.
  • Seeds: Achieved 0.9475 F1-score, outperforming Decision Trees.
  • Wine: 0.9124 F1-score.
  • Banknote: 0.8976 F1-score.
  • Iris: 0.8469 F1-score (slightly lower than some traditional models, but competitive).
• Hyperparameters: The method requires only two hyperparameters: the threshold for binarization and the block length ($n$).

5. Significance and Limitations

Significance:

• Theoretical Insight: The work bridges Information Theory, Dynamical Systems, and Machine Learning. It posits that "learning" is equivalent to finding the dynamical system that minimizes the description length of the data.
• Interpretability: Unlike "black box" neural networks, the decision boundary is defined by the geometric properties of the chaotic maps and the compression efficiency, offering a physically interpretable model.
• Foundation for Future Research: It opens a new avenue for studying the relationship between the Lyapunov exponent (measure of chaos) and class separability.

Limitations:

• Numerical Stability: As the number of features increases, the interval length during backward iteration shrinks exponentially, leading to floating-point precision issues. The authors suggest renormalization techniques (common in arithmetic coding) as a future fix.
• Performance Ceiling: While competitive, the method does not consistently outperform state-of-the-art deep learning or kernel-based SVMs on all datasets, suggesting it is currently more of a theoretical proof-of-concept than a universal SOTA classifier.

Conclusion

ChaosComp offers a compelling alternative to traditional machine learning by reframing classification as a compression problem solved via chaotic dynamics. It demonstrates that chaotic maps can effectively model class-specific data structures and that the principle of Minimum Description Length can be practically implemented using symbolic dynamics. The research provides a foundational step toward understanding the interplay between chaos, entropy, and learnability.