Exploiting Feature Covariance in High-Dimensional Online Learning


Justin Ma, Alex Kulesza, Mark Dredze, Koby Crammer, Lawrence Saul, Fernando Pereira ;
Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 9:493-500, 2010.


Some online algorithms for linear classification model the uncertainty in their weights over the course of learning. Modeling the full covariance structure of the weights can provide a significant advantage for classification. However, for high-dimensional, large-scale data, even though there may be many second-order feature interactions, it is computationally infeasible to maintain this covariance structure. To extend second-order methods to high-dimensional data, we develop low-rank approximations of the covariance structure. We evaluate our approach on both synthetic and real-world data sets using the confidence-weighted online learning framework. We show improvements over diagonal covariance matrices for both low and high-dimensional data.

Related Material