# Online Streaming Feature Selection via Conditional Independence
## 2 Related Work  
Feature selection is a simple, interpretable and especially necessary technique for handling high dimensional data [1; 3; 23; 24; 25; 26]. From the label perspective that illustrates whether label information is involved in the selection phase, feature selection includes supervised, unsupervised, and semi-supervisedmethods [3]. From the selection strategy perspective that describes how the features are selected, it includes wrapper methods, filter methods, and embedded methods [2; 3]. O_SFSF_ is one of the most important branches of feature selection [27]. The number of features changes over time, and it requires real time processing, rather than waiting for all features to arrive. The representative works include _Grafting_[28], _Alpha-investing_[18], _OSFS_[6], _OGFS_[29] and _SAOLA_[19]. _Grafting_[28] is an embedded feature selection approach that can discard various irrelevant and redundant features. The grafting algorithm is based on an L1 regularized formulation. It can handle streaming features but requires that the feature size be known so that it can obtain the value of the regularization parameter \(\lambda\)[6]. _Alpha-investing_[18] can handle feature sets with infinite sizes. However, it only evaluates each feature once instead of considering the redundancy of selected features. As a result, the prediction accuracy is low and unstable [5]. _OSFS_[6] uses the G\({}^{2}\) test to denote conditional independence or dependence and then identifies irrelevant and redundant features. _OSFS_ can remove irrelevant and redundant features from streaming features. Therefore, it can select fewer features and obtain higher prediction accuracy than _Grafting_ and _Alpha-investing_ when the volume of redundant features is high. It is adaptive, enabling it to deal with extremely high dimensionality feature sets. Therefore, it guarantees that strongly relevant features and non-redundant features can be selected as the features stream one at a time as well as the removal of features that do not belong to its _Marko blanket_. However, with an increasing number of selected features with weak relevance, the running time grows exponentially [6]. _OGFS_[29] uses group structure information as a type of prior knowledge to select features. It produces improved feature subsets using two stages: intra-group feature selection and inter-group feature selection. However, _OGFS_ needs to choose a small number of positive parameters in advance, which is relatively difficult without prior information [5]. _SAOLA_[19] can handle feature spaces with extremely high dimensionality using the online pairwise comparison strategy. _SALOA_ filters out redundant features using the \(k\)-greedy search strategy, but it cannot obtain an optimal value at the same time for the relevance threshold [5]. Causal feature selection has recently been proposed as an emerging filtering approach that is successful in feature selection. In particular, the discovery of _Markov blankets_ from Bayesian networks for feature selection has attracted much attention. _[PERSON]_ and _[PERSON]_ bridged the gap between the concepts of feature relevance in feature selection and _Markov blanket_ in a Bayesian network used for classification [30]. The algorithms include the Grow-Shrink (_GS_) [20], the Iterative Associative _Markov Blanket_ (_IAMB_) [31], _HITON_MB_[32], the max-min _Markov blanket_ (_MMMB_) [33], the target information equivalence (_TIE_*) [34], and the selection via group alpha-investing (SGAI) [22]. _TIE_* algorithm can mine all Markov blankets under nonfaithful conditions. However, _TIE_* mines multiple Markov blankets for causal discovery without missing causative variables and is not yet customized for feature selection [22; 34]. _SGAI_ perform Markov blanket feature selection with representative sets for classification under the nonfaithful condition, and outperforms the state-of-the-art Markov blanket feature selectors [22].