Online Feature Selection: A Limited-Memory Substitution Algorithm and Its Asynchronous Parallel Variation
Haichuan Yang*, University of Rochester; Ryohei Fujimaki, NEC Laboratories America; Yukitaka Kusumura, NEC lab; Ji Liu, University of Rochester
Abstract
This paper considers the feature selection scenario where only a few features are accessible at any time point. For example, features are generated sequentially and visible one by one. Therefore, one has to make an online decision to identify key features after all features are only scanned once or twice. The optimization based approach is a powerful tool for the online feature selection.
However, most existing optimization based algorithms explicitly or implicitly adopt L1 norm regularization to identify important features, and suffer two main disadvantages: 1) the penalty term for L1 norm term is hard to choose; and 2) the memory usage is hard to control or predict. To overcome these two drawbacks, this paper proposes a limited-memory and model parameter free online feature selection algorithm, namely online substitution (OS) algorithm. To improve the selection efficiency, an asynchronous parallel extension for OS (Asy-OS) is proposed. Convergence guarantees are pro-vided for both algorithms. Empirical study suggests that the performance of OS and Asy-OS is comparable to the bench-mark algorithm Grafting, but requires much less memory cost and can be easily extended to the parallel implementation.
Filed under: Frequent Pattern Mining | Deep Learning | Dimensionality Reduction