TL;DR
This paper introduces "Dracula," a novel framework for unsupervised feature selection from sequential data like text. Dracula learns a "deep" dictionary of n-grams by recursively compressing its own dictionary, offering more efficient representations than previous methods. This approach, formulated as a linear program, demonstrates improved performance on various classification tasks.
What Problem Does This Paper Address?
Traditional machine learning often relies on good feature representations to highlight salient data properties. For sequential data like text, feature extraction can be challenging. While methods like Compressive Feature Learning (CFL) use n-grams to compress data, they are limited to "shallow" dictionaries. This paper addresses the need for more sophisticated, hierarchical feature representations that can capture deeper structures within sequential data, leading to better compression and more effective learning.
Methods
The core of Dracula is a framework that learns a dictionary of n-grams to compress a corpus and then recursively compresses its own dictionary. This is achieved by formulating the problem as a binary linear program (BLP), which can be relaxed to a standard linear program (LP). This LP formulation offers significant structural advantages, allowing for well-behaved solution paths and parameter control over dictionary depth and diversity. The authors also propose a "dictionary diffusion" process to incorporate the learned dictionary structure into feature representations, creating a hierarchical feature matrix.
Datasets
The paper evaluates Dracula on three datasets:
- Protein Data: 131 protein sequences labeled with kingdom and phylum.
- Stylometry Data: 100 sentences per author from the Reuters dataset, with words replaced by part-of-speech tags.
- Sentiment Prediction Data: 10,662 movie review sentences labeled as positive or negative.
Key Insights and Ideas
- Deep Compression: Dracula's recursive dictionary compression allows for hierarchical feature learning, going beyond the "shallow" dictionaries of prior methods like CFL. This is analogous to "deep" learning architectures.
- LP Formulation: Formulating the problem as a linear program (or its binary relaxation) provides significant structural advantages, enabling analysis of solution paths and parameter control, unlike non-convex deep learning methods.
- Dictionary Diffusion: Incorporating the learned dictionary structure into features (via diffusion) allows for richer representations that capture relationships between n-grams, leading to improved performance, especially for tasks where lower-order features are important.
- Predictable Solution Paths: The LP formulation guarantees that as cost parameters vary, the optimal solutions transition predictably through faces of the constraint polyhedron, avoiding abrupt "jumps" in solutions.
Key Results
- Protein Data: Dracula's "Top" features (using principal components of the learned dictionary) showed improved classification accuracy compared to CFL and "All" features (traditional bag-of-n-grams) on bacteria identification tasks.
- Stylometry Data: Dracula's features, particularly with higher-order n-grams, demonstrated better author identification accuracy than traditional methods.
- Sentiment Prediction: Dracula's "Flat" features (after dictionary diffusion) achieved competitive accuracy with bigrams on sentiment classification, outperforming traditional methods when using longer n-grams, suggesting its ability to perform effective feature selection.
Limitations and Future Work
- Scalability: The current LP formulation is computationally inefficient for large-scale datasets, and dedicated algorithms leveraging problem structure are needed for practical application.
- Characterizing Face Lattice: Analytically characterizing Dracula's face lattice remains an open problem.
- Extensions: The authors suggest exploring algorithms that exploit Dracula's problem structure for scalability and investigating its application to large datasets like the human genome. They also note that the optimal binary solutions found by Gurobi warrant further investigation.
Summary updated