Abstract
Kotaro Kitagawa, Kumiko Tanaka-Ishii. Proceedings of 5th International Joint Conference on Natural Language Processing.
2011.
Introduction
In modern Natural Language Processing (NLP), models often contend with millions of features. While high dimensionality allows for rich information capture, it also introduces noise and redundancy. Standard L1-regularization (Lasso) is a popular tool for feature selection, pushing many weights to zero. However, Lasso treats features as independent entities, failing to account for correlations. For instance, the word "economic" and its stem "econom" are highly correlated; Lasso might select both or pick one arbitrarily, potentially ignoring other diverse evidence.
Methodology: Relational Lasso
The authors propose Relational Lasso, an extension of the classic Lasso optimization that incorporates known or automatically discovered relationships between features. The objective function is modified with a per-feature penalty parameter, $\alpha_i$:
$$w^* = \arg \min_{w} L(w) + \lambda \sum_{i} \alpha_i |w_i|$$
The innovation lies in the dynamic determination of $\alpha_i$ based on a relation $R$.
Defining Relations
While $R$ can incorporate any prior knowledge, the study highlights inclusion relations. A feature $q$ "includes" $p$ if $p$ is always present whenever $q$ is (e.g., a word always implies its stem).
The Algorithm
Relational Lasso uses an iterative process. As the model identifies important features based on the gradient of the loss function, it increases the penalty ($\alpha$) for all related features in $R$. This mechanism discourages the selection of redundant features, forcing the model to seek diverse evidence across the feature space.
Experimental Setup
The method was evaluated on three NLP tasks:
- Text Classification: 20 Newsgroups (20NG) dataset.
- Sentiment Analysis: Movie Review dataset v2.0.
- Dependency Parsing: Penn Treebank (WSJ).
Experiments compared "Standard" (Std) feature sets against "Standard + Additional" (Std+Add) sets, which include more complex and potentially redundant features like stems or bigrams.
Results and Discussion
Relational Lasso consistently outperformed conventional and Adaptive Lasso across all tasks, particularly when the feature space was expanded.
As shown in the figure above, Relational Lasso maintains higher performance even as the number of non-zero features grows. The comprehensive results are summarized in the table below:
Key findings include:
- 20 Newsgroups: Relational Lasso achieved a Micro-F1 of 81.81%, significantly higher than Adaptive Lasso (77.16%).
- Sentiment Analysis: It reached 86.45% accuracy. Notably, conventional Lasso's performance dropped when additional features were added, whereas Relational Lasso improved.
- Parsing: Relational Lasso achieved the highest word accuracy at 89.23%.
Conclusion
Relational Lasso effectively addresses feature redundancy by penalizing correlated features during optimization. By leveraging structural knowledge—often extracted automatically—the method achieves superior classification performance in high-dimensional settings without significant computational overhead. Future work may explore more complex semantic relations, such as those found in WordNet.
Summary updated