An Online Learning Algorithm for Bilinear Models

Yuanbin Wu, Shiliang SunICML 2015 · OpenReview

In the world of supervised learning, linear models are the bread and butter of classification. Traditionally, we pack features into a long vector and learn a corresponding weight vector. But what if your features naturally resemble a matrix? This paper introduces an efficient way to learn these "bilinear" models on the fly, bridging the gap between expressiveness and computational efficiency.

The Challenge of Bilinear Models

Standard linear models treat features as flat vectors. However, in fields like computer vision or natural language processing (NLP), features often possess a latent structure that is better represented as a matrix. For example, in sequential labeling tasks like part-of-speech tagging, a feature might depend simultaneously on the "current label" and the "previous label."

While one could flatten these interactions into a massive vector, a bilinear model ($W = \alpha\beta^\top$) captures them more naturally. The catch is that imposing a rank constraint—specifically rank-1—makes the optimization problem non-convex. Traditional methods often rely on Singular Value Decomposition (SVD) at each step, which is computationally crushing for large-scale, real-time (online) learning.

Proposed Methodology

The authors bridge the gap between the structural advantages of bilinear models and the speed of online learning through two main innovations:

  1. Online Mirror Descent with Power Iteration: Instead of performing a full SVD at every step to find the best rank-1 approximation, the algorithm uses Power Iteration. To make this fast enough for online updates, they employ a "warm start" strategy: the singular vectors from the previous time step serve as the starting point for the current one.
  2. Theoretical Regret Analysis: Because the rank-1 constraint is non-convex, standard regret bounds for online convex optimization do not apply. The authors derive a new second-order approximation of the squared spectral norm. This allows them to prove a regret bound, demonstrating that the algorithm's performance stays close to the best possible fixed model over time.
  3. Feature Decomposition: They demonstrate how standard feature templates in NLP can be decomposed into two "views" (e.g., current state and previous state), naturally fitting the $W = \alpha\beta^\top$ structure.

Experimental Insights

The researchers evaluated their algorithm on two classic sequential labeling tasks: Chinese Word Segmentation (CWS) using the SIGHAN Backoff dataset, and Text Chunking using the CoNLL Shared Task 2000 dataset.

  • Parameter Efficiency: By enforcing a rank-1 constraint, the model significantly reduces the number of parameters. In the CWS task, the bilinear model used only 50% of the parameters required by a standard linear model while maintaining competitive performance.
  • The "Warm Start" Advantage: The power iteration converges extremely quickly (often in just 4 iterations) because the singular vectors of the model do not change drastically between consecutive online updates.
  • Prior Knowledge as a Regularizer: The rank-1 constraint acts as a form of structural regularization. The authors found that their method (denoted as "bol") was particularly effective when training data was scarce, outperforming the standard structured perceptron.

Key Results

The proposed online bilinear algorithm ("bol") proved to be both highly accurate and exceptionally fast compared to traditional batch learners like Conditional Random Fields (CRFs).

Performance and training time comparison across datasets
  • Accuracy: The algorithm achieved F1 scores competitive with state-of-the-art batch learners. For instance, on the pku dataset, it reached a 94.6 F1 score, outperforming crf2 (93.3) and crf1 (92.5).
  • Training Speed: The online bilinear algorithm was significantly faster than CRFs. On the tested datasets, it was roughly 4x faster than the L2-regularized CRF (crf2) and nearly as fast as the simple structured perceptron (sp).
Convergence comparison of the proposed algorithm against baselines
  • Convergence: The model converges much faster than CRFs in terms of iterations, making it highly suitable for applications where models need to be updated frequently with streaming data.

Limitations and Future Directions

While highly effective, the approach has a few limitations:

  • Rank-1 Limitation: This paper focuses specifically on the rank-1 case. While efficient, more complex tasks might require a higher rank (rank-$k$) to capture all necessary feature interactions.
  • Spectral Gap Dependency: The theoretical regret bound and the convergence of the power iteration depend on the gap between the first and second singular values ($\sigma_1$ and $\sigma_2$). If these values are too close, the algorithm might struggle to converge quickly.

Future work could extend the algorithm to handle rank-$k$ models ($k > 1$), which would require more sophisticated methods to efficiently compute the gradient of the Ky Fan $k$-norm.

Summary updated

Abstract

We investigate the bilinear model, which is a matrix form linear model with the rank 1 constraint. A new online learning algorithm is proposed to train the model parameters. Our algorithm runs in t...
BibTeX
@inproceedings{wu2015online,
  author = {Yuanbin Wu and Shiliang Sun},
  title = {{An Online Learning Algorithm for Bilinear Models}},
  booktitle = {International Conference on Machine Learning},
  year = {2015},
  url = {https://openreview.net/forum?id=rJEhgoZdWr},
}
Figure