# Privacy-Preserving Feature Selection with Fully Homomorphic Encryption
## 1 Introduction  
### Motivation  
This study proposes a secure feature selection protocol that works effectively as a preprocessor for traditional machine learning (ML). Let us consider a scenario where different data owners are interested in private ML model training (e.g., logistic regression [1], SVM [2, 3], and decision tree [4, 5]) on their combined data. There is a large advantage to securely training these ML models on distributed data due to competitive advantage or privacy regulations. Feature selection is the problem of finding a subset of relevant features for model training. Using well-chosen features can lead to more accurate models, as well as speedup during model training [6]. Consider a data set \(D\) associated with a feature set \(F\) and a class variable \(C\), where all feature values \(x(F_{i})\) (\(F_{i}\in F\)) and the corresponding class label \(x(C)\) are defined for each datum \(x\in D\). In Table 1, for example, we show a concrete example. Given a triple \((D,F,C)\), the feature selection problem is to find a minimal \(F^{\prime}\subseteq F\) that is relevant to the class \(C\). The relevance of \(F^{\prime}\) is evaluated, for example, by \(I(F^{\prime};C)\), which measures the mutual information between \(F^{\prime}\) and \(C\). On the other hand, \(F^{\prime}\) is minimal, if any proper subset of \(F^{\prime}\) is no longer consistent. To the best of our knowledge, the most common method for identifying favorable features is to choose features that show higher relevance in some statistical measures. Individual feature relevance can be estimated using statistical measures such as mutual information and Bayesian risk. For example, at the bottom row of Table 1, the mutual information score \(I(F_{1};C)\) of each feature \(F_{i}\) to class labels is described. We can see thatis more important than \(F_{5}\), because \(I(F_{1};C)>I(F_{5};C)\). \(F_{1}\) and \(F_{2}\) of Table 1 will be chosen to explain \(C\) based on the mutual information score. However, a closer examination of \(D\) reveals that \(F_{1}\) and \(F_{2}\) cannot uniquely determine \(C\). In fact, we find \(x_{2}\) and \(x_{5}\) with \(x_{2}(F_{1})=x_{5}(F_{1})\) and \(x_{2}(F_{2})=x_{5}(F_{2})\) but \(x_{2}(C)\
eq x_{5}(C)\). On the other hand, we can see that \(F_{4}\) and \(F_{5}\) uniquely determine \(C\) using the formula \(C=F_{4}\oplus F_{5}\) while \(I(F_{4};C)=I(F_{5};C)=0\). As a result, the traditional method based on individual feature relevance scores misses the correct answer. Thus, we concentrate on the concept of consistency: \(F^{\prime}\subseteq F\) is considered to be consistent if, for any \(x,y\in D\), \(x(F_{i})=y(F_{i})\) for all \(F_{i}\in F^{\prime}\) implies \(x(C)=y(C)\). In machine learning research, consistency-based feature selection has received a lot of attention [8; 9; 10; 11; 12]. CWC (Combination of Weakest Components) [8] is the simplest of such consistency-based feature selection algorithms, and even though CWC uses the most rigorous measure, it shows one of the best performances in terms of accuracy as well as computational speed compared to other methods [7]. Throughout the proposed secure protocol, none of the parties learns the values of the data as all computations are done over ciphertexts. Next, the parties train an ML model over the pre-processed data using existing privacy-preserving training protocols (e.g., logistic regression training [13] and decision tree [14]). Finally, they can disclose the trained model for common use. To design a secure protocol for feature selection, we focus on the framework of homomorphic encryption. Given a public key encryption scheme \(E\), let \(E[m]\) denote a ciphertext of integer \(m\); if \(E[m+n]\) can be computed from \(E[m]\) and \(E[n]\) without decrypting them, then \(E\) is said to be _additive_ homomorphic, and if \(E[mn]\) can also be computed, then \(E\) is said to be _fully_ homomorphic.