Provable Variable Selection for Streaming Features

Jing Wang, Jie Shen, Ping Li
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:5171-5179, 2018.

Abstract

In large-scale machine learning applications and high-dimensional statistics, it is ubiquitous to address a considerable number of features among which many are redundant. As a remedy, online feature selection has attracted increasing attention in recent years. It sequentially reveals features and evaluates the importance of them. Though online feature selection has proven an elegant methodology, it is usually challenging to carry out a rigorous theoretical characterization. In this work, we propose a provable online feature selection algorithm that utilizes the online leverage score. The selected features are then fed to $k$-means clustering, making the clustering step memory and computationally efficient. We prove that with high probability, performing $k$-means clustering based on the selected feature space does not deviate far from the optimal clustering using the original data. The empirical results on real-world data sets demonstrate the effectiveness of our algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-wang18g, title = {Provable Variable Selection for Streaming Features}, author = {Wang, Jing and Shen, Jie and Li, Ping}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {5171--5179}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/wang18g/wang18g.pdf}, url = {https://proceedings.mlr.press/v80/wang18g.html}, abstract = {In large-scale machine learning applications and high-dimensional statistics, it is ubiquitous to address a considerable number of features among which many are redundant. As a remedy, online feature selection has attracted increasing attention in recent years. It sequentially reveals features and evaluates the importance of them. Though online feature selection has proven an elegant methodology, it is usually challenging to carry out a rigorous theoretical characterization. In this work, we propose a provable online feature selection algorithm that utilizes the online leverage score. The selected features are then fed to $k$-means clustering, making the clustering step memory and computationally efficient. We prove that with high probability, performing $k$-means clustering based on the selected feature space does not deviate far from the optimal clustering using the original data. The empirical results on real-world data sets demonstrate the effectiveness of our algorithm.} }
Endnote
%0 Conference Paper %T Provable Variable Selection for Streaming Features %A Jing Wang %A Jie Shen %A Ping Li %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-wang18g %I PMLR %P 5171--5179 %U https://proceedings.mlr.press/v80/wang18g.html %V 80 %X In large-scale machine learning applications and high-dimensional statistics, it is ubiquitous to address a considerable number of features among which many are redundant. As a remedy, online feature selection has attracted increasing attention in recent years. It sequentially reveals features and evaluates the importance of them. Though online feature selection has proven an elegant methodology, it is usually challenging to carry out a rigorous theoretical characterization. In this work, we propose a provable online feature selection algorithm that utilizes the online leverage score. The selected features are then fed to $k$-means clustering, making the clustering step memory and computationally efficient. We prove that with high probability, performing $k$-means clustering based on the selected feature space does not deviate far from the optimal clustering using the original data. The empirical results on real-world data sets demonstrate the effectiveness of our algorithm.
APA
Wang, J., Shen, J. & Li, P.. (2018). Provable Variable Selection for Streaming Features. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:5171-5179 Available from https://proceedings.mlr.press/v80/wang18g.html.

Related Material