In the world of machine learning, the "features" you feed into a model are often more important than the model itself. For sequential data like text or DNA, we often rely on $n$-grams (sequences of $n$ characters). But which $n$-grams should we choose? If we take all of them, we face a "feature explosion"; if we take too few, we miss the signal.
A paper from ICLR 2016 titled "Data Representation and Compression Using Linear-Programming Approximations" introduces Dracula, a framework that uses the logic of data compression to perform unsupervised feature selection. By treating feature discovery as a "deep" compression problem, the authors provide a mathematically rigorous and interpretable alternative to traditional deep learning.
TL;DR
Dracula is a framework that learns a hierarchical dictionary of $n$-grams by losslessly compressing a corpus and then recursively compressing the dictionary itself. Unlike traditional deep neural networks, Dracula is formulated as a linear program, making its feature selection process stable, predictable, and grounded in convex analysis.
What Problem Does This Paper Address?
The authors tackle the challenge of unsupervised feature selection for sequential data.
Standard approaches usually fall into two camps:
- Heuristic/Redundant: Using all $n$-grams up to a certain length, which creates massive, noisy feature sets.
- Black-Box Deep Learning: Using autoencoders or RNNs, which are powerful but non-convex, hard to interpret, and difficult to tune.
There is a third way: Compression. The Minimum Description Length (MDL) principle suggests that the best way to represent data is the one that compresses it the most. However, classic compressors like LZ-77 are "online"—they depend on the order of documents. The authors wanted a method that is order-invariant and hierarchical, finding "deep" structures where long patterns are built from shorter, reusable ones.
Methods
Dracula (an extension of Compressive Feature Learning or CFL) works by solving an optimization problem: find the smallest dictionary and set of pointers that can perfectly reconstruct the data.
- Recursive Dictionary Compression: While CFL stores its dictionary in "plaintext," Dracula is "deep" because it compresses the dictionary using its own elements. This allows it to represent massive repetitions (like a string of $2^n$ characters) with exponential efficiency.
- Linear Programming (LP) Formulation: The core of Dracula is a Binary Linear Program (BLP). Because BLPs are NP-hard, the authors relax it into a standard Linear Program. This is a "departure from traditional deep learners" because LPs are convex and can be analyzed using well-understood tools like KKT conditions.
- Dictionary Diffusion: This is a clever way to use the discovered hierarchy. If the model finds a long $n$-gram like "representation," the "diffusion" process propagates the counts of that word down to its constituents ("repre," "sent," "ation"). This acts as a graph-based regularizer, helping the model focus on the most informative level of the hierarchy.
- The Solution Path: The authors prove that as you vary the "cost" of adding new words to the dictionary, the solution moves predictably across the faces of a high-dimensional polyhedron.
Key Insights and Ideas
- Structure is Regularization: The dictionary isn't just a flat list; it forms a Directed Acyclic Graph (DAG). The authors show that this DAG structure can be used to regularize learning, effectively "smoothing" the features across the hierarchy so that related $n$-grams share statistical strength.
- Convexity as a Feature: Because Dracula is an LP, it doesn't get stuck in local minima like a neural network. Its "learning" is essentially a walk on a polyhedron, making the resulting features much more stable and reproducible.
- Exponential Savings: By allowing the dictionary to refer to itself, Dracula can find much more compact representations than "shallow" compression methods, which is particularly useful for data with long-range repetitions (like genomic data).
Key Results
The authors evaluated Dracula across three distinct domains:
- Biology (Protein Data): Tested on 131 protein sequences labeled by kingdom and phylum. In bacteria identification, Dracula’s "Top" features achieved 91.2% accuracy (at SVD rank 10), significantly outperforming the "All $n$-grams" baseline of 77.7%.
- Stylometry (Reuters 50/50): A dataset of 2,000 sentences from 10 different authors, used to test if Dracula can identify an author's "fingerprint." Dracula consistently outperformed both the "All $n$-grams" approach and the older CFL method, proving especially effective at identifying authors even with small sample sizes.
- Sentiment Analysis (Pang & Lee): Tested on 10,662 movie review sentences labeled as positive or negative. The "Flat" features (derived via dictionary diffusion) achieved 78.8% accuracy, matching state-of-the-art bigram models. This suggests that Dracula successfully "distills" the most important $n$-grams for classification.
Limitations and Future Work
- Computational Scale: While LPs are "easier" to solve optimally than non-convex problems, general-purpose solvers (like Gurobi) still struggle with massive datasets. The authors note that specialized algorithms (like min-cost flow solvers) are needed to scale Dracula to something as large as the full human genome.
- Hyperparameter Tuning: While the "solution path" is predictable, choosing the right costs ($\tau, \lambda, \alpha$) for dictionary membership still requires some manual effort or cross-validation.
- Future Directions: The authors suggest exploring more complex "equivalence classes" in suffix trees to further tighten the LP relaxation and speed up the solver.
Summary updated