# Privacy-Preserving Feature Selection with Fully Homomorphic Encryption
## 2 Preliminaries
### CWC Algorithm over Plaintext  
We generally assume that the dataset \(D\) associated with \(F\) and \(C\) contains no errors, i.e., if \(x(F_{i})=y(F_{i})\) for all \(i\), \(x(C)=y(C)\). When \(D\) contains such errors, they are removed beforehand and \(D\) contains not more than one \(x\in D\) with the same feature values. In Algorithm 1, we describe the original algorithm for finding a minimal consistent feature for two-class data. Given \(D\) with \(F_{i}\) and \(C=\{0,1\}\), a datum \(x\in D\) of \(x(C)=1\) is referred to as a positive datum and \(y\in D\) of \(y(C)=0\) is referred to as a negative datum. Let \(n\) represent the number of positive data and \(m=|D|-n\). We consider two-dimensional bit array \(\mathbf{B}_{i}[1..n][1..m]\) such that, for any \(1\leq p\leq n\) and \(1\leq q\leq m\), \(\mathbf{B}_{i}[p][q]=0\) if \(x_{p}(F_{i})=y_{q}(F_{i})\) and \(\mathbf{B}_{i}[p][q]=1\) otherwise, where \(x_{p}\) is the \(p\)-th positive datum (\(1\leq p\leq n\)) and \(y_{q}\) is the \(q\)-th negative datum (\(1\leq q\leq m\)). \(\mathbf{B}_{i}[p][q]=0\) means that \(F_{i}\) is not consistent with the pair \((x_{p},y_{q})\) because \(x_{p}(F_{i})=y_{q}(F_{i})\) despite \(x_{p}(C)\
eq y_{q}(C)\). Recall that \(F_{i}\) is said to be consistent only if \(x(F_{i})=y(F_{i})\) implies \(x(C)=y(C)\) for any \(x,y\in D\). As a result, \(||\mathbf{B}_{i}||\) is defined to be the number of \(1\)s in \(\mathbf{B}_{i}\). For a subset \(F^{\prime}\subseteq F_{i}\), \(F^{\prime}\) is said to be consistent, if for any \(p\in[1,n]\) and \(q\in[1,m]\), there exists \(i\) such that \(F_{i}\in F^{\prime}\) and \(\mathbf{B}_{i}[p][q]=1\) hold. CWC uses this to remove irrelevant features from \(F\) in order to build a minimal consistent feature set. We note that finding the smallest consistent feature set is clearly NP-hard. There is a simple reduction from the minimum set cover to this problem as follows: given \(S_{1},\ldots,S_{k}\subseteq S\) (\(|S|=n\)) with the intention that \(S_{i}\) is regarded as \(\mathbf{B}_{i}\) in CWC, covering any element of \(S\) corresponds to the condition that for any \(j\in\{1,\ldots,n\}\), there exists at least one \(i\) such that \(\mathbf{B}_{i}[j]=1\). Since the point of \(\mathbf{B}_{i}\) is that it contains information, for every pair of data across different classes, whether \(F_{i}\) is consistent with the pair or not, it can be easily extended to multi-class data that have more than two classes. Although we focus on two-class data for the sake of simplicity, for multi-class data, the \(mn\)-factors in the complexities are replaced with the number of pairs of data across different classes, which is upper bounded by \(|D|(|D|-1)/2\). Moreover, in extending to multi-class data, it is convenient to consider \(\mathbf{B}_{i}\) as an appropriately serialized one-dimensional bit string because there is no way to represent it as a dense two-dimensional bit array. Hence, in what follows, we treat \(\mathbf{B}_{i}\) as a bit string. ```
1:Input: A dataset \(D\) associated with features \(F=\{F_{1},\ldots,F_{k}\}\) and class \(C=\{0,1\}\). 2:Output: A minimal consistent subset \(S\subseteq F\). 3:Sort \(F_{1},\ldots,F_{k}\) in the incremental order of \(||\mathbf{B}_{i}||\). 4:Let \(\pi\) be the sorted indices of \(\{1,\ldots,k\}\). 5:for\(i=1,\ldots,k\)do
6:if\(F\setminus\{F_{\pi[i]}\}\) is consistent then
7: update \(F\gets F\setminus\{F_{\pi[i]}\}\)
8:endif
9:endfor
```  
**Algorithm 1** The algorithm CWC for plaintext  
Table 3 shows an example of \(D\), and Table 4 shows the corresponding \(\mathbf{B}_{i}\). Consider the behavior of CWC in this case. All \(\mathbf{B}_{i}\) (\(1\leq i\leq 4\)) are computed as preprocessing. Then, the features are sorted by the order \(||\mathbf{B}_{2}||=5\leq||\mathbf{B}_{4}||=5\leq||\mathbf{B}_{3}||=6\leq|| \mathbf{B}_{1}||=8\) and \(\pi=(2,4,3,1)\). By the consistency order \(\pi\), CWC checks whether \(F_{\pi[i]}\) can be removed from the current \(F\).