feature selection

---
Provable Variable Selection for Streaming Features. ICML'18.
---

Background. In many machin learning tasks, the samples are fixed and feature can be generated dynamically, for example the features of patients.

The goal of online feature selectionis to make a decision on whether to keep the new fature in real time. For example, the features of patient are collected over time, e.g. history information on day \(t_1\), the lab Testing results on day \(t_2\) as shown in the following figure. The task of online feature selection is to select the most important features (in red rectangle) at each time step, and discard the remaining features.

Problem setup. Suppose that there are \(n\) samples,

• Each \(a_i\) being the feature arrives at \(i\)th time step.
• Algorithm makes the yes / no decision on whether to keep the feature \(a_i\).
• Update the data matrix \(A\in R^{n\times s_i}\), \(s_i\) is the number of selected features so far.

Contributions. This work is a simple feature selection algorithm

• High dimensional regime \(n\ll d\).
• Memory cost \(O(n^2 log n)\).
• Time efficiency \(O(n^3)\).
• Theoretical guarantee for \(k\)-means clustering.

Related works.

---
Online Group Feature Selection. IJCAI'13.
Online Feature Selection with Group Structure Analysis. TKDE'15.
---