# Online Streaming Feature Selection via Conditional Independence
## 3 Framework for Streaming Features Filtering
### Notations, Definitions, and Formalizations
#### 3.1.2 Definitions  
**Definition 1** (Conditional Independence).: _In a variable set \(S\), two random variables \(x\), \(y\in S\) are conditionally independent given a set of variables \(S_{i}\subseteq S\setminus\{x,y\}\) with respect to a probability distribution \(P\), iff there exists an assignment of \(x\) and \(y\), s.t. \(P(x|y,S_{i})=P(x|S_{i})\), denoted as \(x\bot y|S_{i}\)._  
Conditional independence is a generalization of the traditional notion of statistical independence. If two variables \(x\) and \(y\) are **independent**, then the joint distribution is the product of the marginal: \(P(x)=P(x)\)\(P(y)\), _denoted as \(x\bot y\)_. If they are dependent given some conditioning set, \(S_{i}\), then we can write \(P(x,y|S_{i})=P(x|S_{i})\)\(P(y|S_{i})\). Conditional independence is a key concept in Bayesian networks because of the factorizations of the allowed joint probability distribution [36].  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Mathematical Meanings** \\ \hline \(X_{i}\) & the data set at time \(t_{i}\), denoted as \(X_{i}=[x_{1},x_{2},...,x_{n}]^{T}\in R^{n\times i}\) \\ \(S\) & the set of feature space under the streaming features \\ \(f\) & a feature, \(f\in S\) \\ \(t_{i}\) & a time point of the \(i\)th arriving feature \\ \(f_{i}\) & the \(i\)th arriving feature at time \(t_{i}\) \\ \(CFS\) & candidate feature set at current time \\ \(C\) & class attribute (target variable) \\ \(P(x)\) & event probability of feature \(x\) \\ \(P(.1.)\) & conditional probability \\ \(\rho\) & a threshold \\ \(\alpha\) & significance levels of 0.05 or 0.01 in statistics \\ \(MB(C)\) & _Markov blanket_ of \(C\) \\ \(a\perp b\) & \(a\) is independent of \(b\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Notation Mathematical meanings.  
To characterize conditional independence, according to the elements size of \(S_{i}\) in **Definition 1**, we can divide **conditional independence** into three disjoint categories, namely **null-conditional independence** (\(|S_{i}|=0\)), **single-conditional independence** (\(|S_{i}|=1\)), and **multi-conditional independence** (\(|S_{i}|>1\)).  
Definition 2 (Markov blanket): In a variable set \(S\), the Markov blanket of a class attribute, \(C\), denoted as MB(C), is a minimal set of features. The MB(C) makes \(\forall s\in S/\left(MB(C)\cup\{C\}\right)\), s.t. \(s\bot C|MB(C)\).  
The _Markov blanket_ of a node, \(C\), denoted \(MB(C)\), is the set of parents, children, and children's parents of \(C\). Using the _Markov blanket_ for feature selection can eliminate conditionally independent features without increasing our distance from the desired distribution. The _Markov blanket_ criterion only removes attributes that are unnecessary: attributes that are irrelevant to the target variable and attributes that are redundant given other attributes [20].  
Definition 3 (Strong relevance [6]): A feature \(x\) is strongly relevant to the class attribute, \(C\), iff \(\forall S_{i}\subseteq S-\{x\}\), s.t. \(P(x|S_{i},C)\).  
Definition 4 (Weak relevance [6]): A feature \(x\) is weakly relevant to the class attribute, \(C\), iff \(\exists S_{i}\subseteq S-\{x\}\), s.t. \(P(x|S_{i},C)\).  
Definition 5 (Redundant features [6]): A feature \(x\) is redundant to the class attribute, \(C\), iff it is weakly relevant to \(C\) and has a Markov blanket, MB(x), that is a subset of the Markov blanket of MB(C).  
Definition 6 (Irrelevance [6]): A feature \(x\) is irrelevant to a class attribute, \(C\), iff it is \(\forall S_{i}\subseteq S-\{x\}\), s.t.\(P(S_{i}|x,C)\)\(=P(S_{i}|C)\).