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.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v9-ma10a, title = {Exploiting Feature Covariance in High-Dimensional Online Learning}, author = {Ma, Justin and Kulesza, Alex and Dredze, Mark and Crammer, Koby and Saul, Lawrence and Pereira, Fernando}, booktitle = {Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics}, pages = {493--500}, year = {2010}, editor = {Teh, Yee Whye and Titterington, Mike}, volume = {9}, series = {Proceedings of Machine Learning Research}, address = {Chia Laguna Resort, Sardinia, Italy}, month = {13--15 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v9/ma10a/ma10a.pdf}, url = {https://proceedings.mlr.press/v9/ma10a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Exploiting Feature Covariance in High-Dimensional Online Learning %A Justin Ma %A Alex Kulesza %A Mark Dredze %A Koby Crammer %A Lawrence Saul %A Fernando Pereira %B Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2010 %E Yee Whye Teh %E Mike Titterington %F pmlr-v9-ma10a %I PMLR %P 493--500 %U https://proceedings.mlr.press/v9/ma10a.html %V 9 %X 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.
RIS
TY - CPAPER TI - Exploiting Feature Covariance in High-Dimensional Online Learning AU - Justin Ma AU - Alex Kulesza AU - Mark Dredze AU - Koby Crammer AU - Lawrence Saul AU - Fernando Pereira BT - Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics DA - 2010/03/31 ED - Yee Whye Teh ED - Mike Titterington ID - pmlr-v9-ma10a PB - PMLR DP - Proceedings of Machine Learning Research VL - 9 SP - 493 EP - 500 L1 - http://proceedings.mlr.press/v9/ma10a/ma10a.pdf UR - https://proceedings.mlr.press/v9/ma10a.html AB - 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. ER -
APA
Ma, J., Kulesza, A., Dredze, M., Crammer, K., Saul, L. & Pereira, F.. (2010). Exploiting Feature Covariance in High-Dimensional Online Learning. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 9:493-500 Available from https://proceedings.mlr.press/v9/ma10a.html.

Related Material