Distributed Collaborative Feature Selection Based on Intermediate Representation

1 Introduction

The dimensionality of data is often very high in many realworld applications [Jain and Zongker, 1997], making great challenges such as the curse of dimensionality, high computation and storage cost. There are mainly two distinct ways for dimensionality reduction to tackle these difficulties: feature extraction and feature selection. Feature extraction provides data transformation to form a low dimensional space, while feature selection aims to extract the amount of important features to represent the original data [Guyon and Elisseeff, 1997; Imakura et al., 2019]. In the applications that need to retain the original representations of data variables, e.g, learning the risk factors of cancer, feature selection is preferred.

The feature selection methods can be classified into three main types: filter [He et al., 2006], wrapper [Maldonado and Weber, 2009], and embedded methods [Hou et al., 2011;

Nie et al., 2010; Ye et al., 2016b]. The filter methods are usually computationally simple, but ignore the interactions among features, which may lead to undesired classification result. The wrapper methods detect the possible interactions among features by searching the feature subsets in a learning model, which provide better results than the filter methods [Saeys et al., 2008]. However, the wrapper methods are usually computationally expensive. The embedded methods consider the interactions among features while having lower computational complexity than the wrapper methods, which incorporate feature selection as a part of data training process to search for the optimal subset of features [Ye et al., 2016a].

Similar to most machine learning techniques, in the general setting of feature selection, a large number of data should be available to train a model for good generalization ability. However, in some applications, the data is distributed in multiple parties. The data in one party may be lack of some useful information to learn the most discriminative features. Thus, sharing data with multiple parties for collaborative feature selection can help to learn more useful information and solve the problem of information deficiency in one party. For example, consider learning the risk factors of cancer in the hospital. The risk factors learned in one hospital are limited to the data it holds. If several hospitals share their data for collaborate feature selection, a wealth of information contained in the shared data could mutually benefit all hospitals to learn the most important risk factors.

However, data sharing may be difficult in some organizations due to the limitations such as privacy requirement. Thus, an emerging challenge for feature selection is how to learn the data from multiple parties without revealing their original data. Although the current researches mainly focus on classification or clustering for privacy-aware distributed data setting [Chaudhuri et al., 2011], some studies have been devoted to feature selection by considering the privacy preserving. Due to the simplicity of filter methods, most researchers consider privacy-aware feature selection based on the filter methods. Banerjee and Chakravarty [Banerjee and Chakravarty, 2011] propose a distributed filter based feature selection method by using the virtual dimension reduction technique with a secure sum protocol, which allows privacy-aware feature selection for multiple parties. Yang and Li [Yang and Li, 2014] design a private filter based feature selection method by adding noise as output perturbation according to the sensitivity analysis, but in centralized architecture. Sheikhalishahi and Martinelli [Sheikhalishahi and Fabio, 2017] consider the trade-off between feature utility and privacy score to remove the irrelevant features, and collaborative data classification is performed on the data with the remaining features from multiple parties. Including the filter methods, wrapper based feature selection methods also have been proposed by combining with the anonymization techniques [Jafer et al., 2014]. However, these methods are in centralized architecture and have heavy computational cost.

In this paper, we propose a novel distributed method for embedded feature selection, which allows collaborative feature selection for multiple parties without revealing their original data. Existing studies have addressed privacy preserving for the filter and wrapper feature selection methods, to the best of our knowledge, there is no existing study addresses privacy preserving for the embedded feature selection methods. The contributions of the proposed method are summarized as follows.

• Different from the above related works, the proposed method does not rely on any security protocols. The proposed method performs collaborative feature selection based on the intermediate representations. Instead of the original data, each party shares the intermediate representations for feature learning.
• Embedded feature selection is performed in each party by learning the intermediate representations frommultiple parties, which can solve the information deficiency in the local party.
• The proposed method is flexible and extendable, since many embedded feature selection methods can be incorporated to perform distributed collaborative feature selection with privacy preserving.
• Experimental results show that the proposed method can help a single party to select the important features and improve the classification result through collaborative feature selection.

2 RelatedMethods

2.1 Embedded Feature Selection

We introduce a framework of unsupervised embedded feature selection methods [Hou et al., 2011] and incorporate it for collaborative feature selection, while the supervised case also can be incorporated in our method. Consider that n original data X = [x1, ..., xn] ∈ Rm×n are embedded in a low dimensional space by a transformation matrix W ∈ Rm×q , where m and q are the dimensionalities of the original and embedded data. Let Y = [y1, ..., yn] ∈ Rq×n denote the embedded data matrix of X, where yi is corresponding to xi. By preserving the local data structure of X in Y , the objective function is formulated as

where α and β are two balanced parameters; the term ‖W‖2,1 is calculated as ‖W‖2,1 = ∑ni=1 √∑mj=1 w2 i,j , which is to ensure that W is sparse in rows; tr(Y T LY ) is a promoting regularization term to preserve the local data structure in Y .

Many methods can be used to preserve the local data structure, such as LPP [He and Niyogi, 2004] and LLE [Roweis and Saul, 2000]. We use LPP to preserve the data similarity of X in Y .

where sij is the pairwise similarity between xi and xj . Based on the k-nearest neighbor graph, sij is calculated as

Let L = D - S be the Laplacian matrix, where S is the similarity matrix with sij as its entries, D is the n×n diagonal matrix with Dii = ∑nj=1 sij on the diagonal. Then, equation (2) can be equivalently expressed as

The optimization problem in equation (1) is solved by updating Y and W alternatively until the objective function converges [Hou et al., 2011]. Let wi denote the ith row of W. wi corresponds to the weight of the ith feature, thus, the sparsity constraint on rows makes W suitable for feature selection. The feature weights are ranked according to ‖wi‖2 in descending order and the top rank features are selected.

2.2 Intermediate Representation

Intermediate representation has been proposed as an effective method for collaborative classification [Imakura and Sakurai, 2019]. Consider g parties and let Xi be the original data in party i. Party i calculates the intermediate representation of Xi as ˜Xi = BiXi ∈ Rp×n by a transformation matrix Bi ∈ Rp×m. Xi, Bi and ˜Xi are not revealed to other parties. To perform collaborative classification, ˜Xi (i = 1, .., g) from multiple parties are transformed to the same low dimensional space, where ̂Xi = Mi ˜Xi ∈ Rq×n , and Mi ∈ Rq×p is the transformation matrix in party i which satisfies

That is, for an original data X, after the two transformations by MiBi and MjBj in parties i and j, the same data properties are retained, i.e., the two transformations of X tend to the same data point in the low dimensional space. Thus, classification can be performed on ̂Xi (i = 1, .., g) in the low dimensional space.

Without sharing Bi, to find Mi that satisfies equation (5), some sharable data called anchor data are introduced. The anchor data can be the public data or dummy data constructed based on the training data. Let Xa = [xa1 , ..., xar ] ∈ Rm×r denote the anchor data and ˜Xa i = BiXa is the intermediate representation of Xa in party i. ˜Xa i (i = 1, .., g) are shared to calculate Mi. Set the target Z a ∈ Rq×r that satisfies Z a ≈ ̂Xa i (i = 1, .., g). Z a can be solved by

Directly solving equation (6) is difficult. An alternative way is to solve its minimal perturbation problem based on the singular value decomposition (SVD)[Ito and Murota, 2016]. Let

be SVD of the matrix combing ˜Xa i . Then, Z a can be set as

Based on equation (6), Mi can be computed by solving minMi ‖Z a -Mi ˜Xa i ‖2F , that is

3 Distributed Collaborative Feature Selection

In this section, we propose a distributed method for collaborative feature selection. We first show the steps and formulations of the proposed method and then provide an effective algorithm to solve the problem.

3.1 Steps and Formulations

In the embedded feature selection, the original data X is transformed to the low dimensional data Y by a transformation matrix W. Y is obtained by preserving the local data structure of X and the learned transformation matrix W is used to rank the features. If X is lack of some useful information, W can not learn the most discriminative features. In the proposed method, we consider the collaborative feature selection from multiple parties to solve the information deficiency in one party, meanwhile we consider privacy preserving that each party does not reveal the original data.

Inspired by [Imakura and Sakurai, 2019], we consider transforming the original data from multiple parties by two transformation matrices (e.g., Bi and Mi in party i) to the same low dimensional space, where the condition of equation (5) is satisfied. This can be realized by the following steps.

1) Set the anchor data Xa ∈ Rm×r and share them for all parties.

1. Apply LPP [He and Niyogi, 2004] to calculate the transformation matrix Bi based on Xi in party i. The intermediate representations of Xi and Xa are calculated as ˜Xi = BiXi and ˜Xa i = BiXa , respectively.
2. The intermediate representations of the anchor data from multiple parties, i.e., ˜Xa 1 , ..., ˜Xa g , are shared to calculate the transformed low dimensional data Z a , as shown in equation (8). The transformation matrix Mi can be calculated as equation (9).
3. The transformations of the original data from multiple parties in the same low dimensional space can be calculated as Zi =Mi ˜Xi =MiBiXi (i = 1, .., g).

Different from [Imakura and Sakurai, 2019] that aims to perform classification on Zi (i = 1, .., g) from multiple parties, for the purpose of feature selection, we consider learning the transformation matrix MiBi to rank the features in each party. Since Bi is distributed in each party without sharing, in each party we consider updating Bi to minimize the following objective function for feature selection.

where α and β are two balanced parameters. Note that the Bi in step 2) can be seen as the initialization to generate the initial Zi in step 4). After Bi being updated, Zi can be updated based on ˜Xa i = BiXa according to equations (7) and (8). Let Wi = (MiBi)T , equation (10) can be rewritten as

The term ‖Wi‖2,1 is to ensure that Wi is sparse in rows and the feature weights in party i are learned based on Wi.

Note that L in the term tr(W T i XiLXT i Wi) is calculated as that introduced in Section 2.1. We replace Y by W T i Xi since the low dimensional data Zi is not a variable in the objective function, while Zi can be updated based on Bi. Zi is calculated based on ˜Xa i (i = 1, .., g), which are the intermediate representation of the anchor data from multiple parties. Thus, some properties of the original data from multiple parties can be preserved by the transform to Zi. In addition, we also consider preserving the local data structure of Xi by adding the term tr(W T i XiLXT i Wi). In contrast to our method, the local feature selection in equation (1) only considers preserving the local data structure of Xi.

3.2 Solutions

We show the process of how to solve the objective function in equation (11).

where Hi ∈ Rm×m is a diagonal matrix with the ith diagonal element as

wi is the ith row of W. By setting ∂Θ(Wi) ∂Wi = 0, we have

Since Wi = (MiBi)T , we obtain

After Bi being updated, the intermediate representations ˜Xa i = BiXa can be updated. Mi can be updated based on ˜Xa i . Thus, Zi can be updated. Then, Bi can be updated again. We consider alternatively updating Wi and Zi to optimize the objective function. Algorithm 1 shows the procedure of collaborative feature selection distributed in party i. Algorithm 1 will stop when the objective function tends to a constant or the change is very small.

Algorithm 1 Distributed collaborative feature selection

Input: Original data matrix Xi; Anchor data matrixXa Parameter: Balance parameters α, β; Neighborhood size k; Dimensionalities of embedding p, q; Selected feature number

dOutput: d selected features

• 1: Set t = 0 and Calculate L;
• 2: Initialize Bt i by LPP; Calculate ( ˜Xa i )t = Bt i Xa ;
• 3: Collect ( ˜Xa 1 )t , ..., ( ˜Xa g )t from multipler parties; Calculate (Z a )t as in equation (8); Calculate M t i as in equation (9);
• 4: Calculate Z t i =M t i Bt i Xi;
• 5: Initialize Ht = Im ;
• 6: repeat
• 7: Calculate W t i as in equation (14);
• 8: Calculate Bt+1 i = (M t i )-1 (W t i )T ;
• 9: Calculate ( ˜Xa i )t+1 = Bt+1 i Xa ;
• 10: Collect ( ˜Xa 1 )t+1 , ..., ( ˜Xa g )t+1 from other parties;
• 11: Calculate (Z a )t+1 as in equation (8);
• 12: Calculate M t+1 i as equation (9);
• 13: Calculate Z t+1 i =M t+1 i Bt+1 i Xi
• 14: Calculate Ht+1 i according to equation (13);
• 15: t = t + 1;
• 16: until convergence
• 17: Sort each feature according to ‖wi‖2 in descending order and select the top d ranked ones.

4 Discussions

4.1 Convergence Analysis

We solve the proposed method in an alternative way. Then, we show its converge behavior. From steps 8 and 13 in Algorithm 1, Z t+1 i is calculated based on W t i . For the sake of convenience, we denote Z t i = f(W t-1 i ). Denote Θ(W t i ) = ‖f(W t-1 i ) - (W t i )T Xi‖2F + α‖W t i ‖2,1 + βtr((W t i )T XiLXT i W t i ). We can show that the objective function in equation (11) will monotonically decrease in each iteration if Θ(W t+1 i ) ≤ Θ(W t i ).

Firstly, when f(W t-1 i ) is fixed, we can prove that

We omit the detailed proof process of equation (16). A similar proof process can be found in [Hou et al., 2011]. On the other hand, since ‖f(W t i ) - (W t+1 i )T Xi‖2F ≤ ‖f(W t-1 i ) -

(W t+1

i )T Xi‖2F , the following inequality holds.

From the inequalities (16) and (17), we have Θ(W t+1 i ) ≤ Θ(W t i ). The objective function has lower bounds, such as zero, thus the above iteration will converge. Empirical results show that the convergence is fast and only several iterations (less than 10 iterations in the experiments) are needed to converge.

4.2 Relations with Other Methods

Firstly, considering the privacy preserving and distributed collaboration, the proposed method is related to the methods in [Banerjee and Chakravarty, 2011] and [Sheikhalishahi and Fabio, 2017]. Both the two methods apply secure sum protocol [Sheikh et al., 2010] to obtain the sum of the data from multiple parties, and both the two methods focus on filter feature selection. The proposed method introduces a set of anchor data and each party shares the intermediate representations of the anchor data for collaborative feature selection without revealing their original data. Moreover, the proposed method focuses on embedded feature selection.

Secondly, the proposed method has a close relationship with the general embedded feature selection methods, such as the methods in [Hou et al., 2011; Cai et al., 2010; Ye and Sakurai, 2018]. The embedded feature selection methods consider local data structure preserving to find an embedded low dimensional data. In addition to preserving the local data structure, the proposed method utilizes the intermediate representations of the anchor data from multiple parties to find the low dimensional data. Furthermore, the proposed method can achieve privacy preserving and distributed collaboration.

Note that for privacy preserving, the proposed method only shares the intermediate representations of the anchor data from multiple parties. In the case that without privacy requirement while the data from multiple parties are difficult to collect for centralized analysis due to the huge data size, the proposed method is also applicable. A part of the original data collected from multiple parties can be used as the anchor data, and the process of feature selection is distributed in each party based on the shared intermediate representations of the anchor data.

4.3 Privacy Analysis

The proposed method does not use privacy-preserving techniques like cryptography or differential privacy that have a strong guarantee for privacy. Since differential privacy is considered to be too strong for some applications, some weakened versions of privacy have been proposed [Hall et al., 2012]. Similarly, in our method, the term "privacy is preserved" can be defined as the case when the original data in each party cannot be (approximately) obtained by others. Here, we do not consider the privacy of the statistical datasets. According to the proposed method, the original data Xi in party i can be approximated only if one can obtain both the intermediate representation of Xi and the transformation matrix Bi. However, the intermediate representation of Xi and the transformation matrix Bi are not revealed to other parties. As shown in our algorithm, the intermediate representation of Xi is only distributed in party i, thus, the original dataset Xi cannot be (approximately) obtained by others. We will consider further analyzing the privacy in a more formal way for our method in future work.

5 Experimental Results

In this section, the proposed method is evaluated on several datasets. A dataset is divided into some parts. The data in one part is referred to as the data in one party. The proposed method is performed in each party for distributed collaborative feature selection. We apply k Nearest Neighbors (NN) classifier (k = 1) to test the performance of the proposed method. In each party, feature selection is performed on the training data to learn the features. The training data with the selected features are used to train the classifier and the test data with the selected features are used to test the result. Two widely used evaluation metrics, i.e., accuracy (ACC) and normalized mutual information (NMI) [Strehl and Ghosh, 2002], are used to evaluate the classification results.

We compare the proposed method, i.e., distributed collaborative feature selection (DCFS), with local feature selection (LFS) in each party using the method in Section 2.1. We also compare the case of collecting all data from each party for feature selection (AFS), and the baseline case using all the features (i.e., without feature selection) for classification. In the experiments, we generate 500 anchor data based on the original data in each party. The features of the anchor data are generated as random values between the maximum and minimum values of the corresponding features in the training data. Since the anchor data in each party is generated based on its original data, the anchor data gathered from all parties are related to the original data in all parties. The number of selected features is ranged from 1 to 300. α and β are tuned over {10-3 , 10-2 , 10-1 1, 101 , 102 , 103 }. The neighborhood size is set as k = 5. Dimensionalities of embedding are set as p = 10 and q = 5. We report the best result of all the methods by using different parameters. All experiments are performed using MATLAB2018a on Mac OS X 10.13.6 (18C54) with core i7 CPU and 16GB ram.

5.1 Handwritten Digit Data

We first use the handwritten digit data (i.e., MNIST) [LeCun et al., 1998] to generate two datasets for performance evaluation. MNIST consists of 5000 samples with 784 features. The two generated datasets are denoted as MNIST-d1 and MNIST-d2, respectively. MNIST-d1 contains the digitals 0, 1, 2, 3 and is divided into two parts. Party 1 consists of 270 samples of 1 and 10 samples of 0, 2, 3, respectively. Party 2 consists of 30 samples of 1 and 90 samples of 0, 2, 3, respectively. MNIST-d2 contains the digitals 4, 5, 6, 7, 8, 9 and is divided into six parts. Each part consists of about 90% of one digital and 10% of other digitals, e.g., party 1 consists of 275 samples of 4 and 5 samples of 5, 6, 7, 8, 9, respectively. We use five test data to test the performance of feature selection in MNIST-d1 and MNIST-d2, respectively. Each test data has 600 samples and all classes are equal in size. The mean results with standard deviation are reported.

Figure 1 shows some of the testing digitals with the selected features by using LFS and DCFS, respectively. We can see that, compared with LFS, the features selected by DCFS can better capture the data structure to represent the original data. In Figures 1 (b) and (d), the digital 0 is difficult to be recognized. In Figure 1 (g), 4 and 5 are difficult to be recognized.

(a) MNIST-d1

(b) MNIST-d2

The classification results in each party on MNIST-d1 and MNIST-d2 are shown in Table 1. In each party, the best and the second best results are highlighted in bold-face type and underlined, respectively. For MNIST-d2, we show the results in three parties and the average result of the other three parties. We can see that feature selection can improve the results of classification. Collecting all data for centralized analysis obtain the best results in most cases. LFS performs worse than baseline in some parties due to the lack of information. The proposed method solves the information deficiency in the local party, thus performs better than LFS and also baseline on most parties.

5.2 Gene Expression Data

We use four gene expression datasets for performance evaluation. The datasets are Colon, TOX-171, Lung, and Lymphoma, which are downloaded from http://featureselection.asu.edu/datasets.php. We summarize the properties of the datasets in Table 2. Colon and TOX-171 are randomly divided into two parts with equal size, while Lung and Lymphoma are randomly divided into three parts with roughly equal size. For each dataset, 80% and 20% of the data are set as the training and test data in each party, We perform data divisions five times on each dataset and report the mean results with standard deviation.

The classification results on the four gene expression datasets are shown in Table 3. The performance improvements by the three feature selection methods on gene expression datasets are more significant than that on MNIST. The proposed method performances better than local feature selection in each party. In party 1 on TOX-171, NMI of DCFS is better than AFS. That is because AFS focuses on preserving the local data structure in multiple parties. The proposed method can be seen as a trade-off between preserving the local data structure in a single party and in multiple parties. In some case, the trade-off can obtain better result.

Figure 2 shows the classification results on colon by varying the number of selected features. It is clear that DCFS performs better than LFS in terms of both ACC and NMI.

The classification results on Colon with different α and β are shown in Figure 3. As seen from Figure 3, when two parameters are changed within a certain range, the performance also changes within a certain range. The performance

(b) TOX-171

(a) ACC

(b) NMI

Figure 3: Classification results on Colon vs. parameters α and β

in terms of ACC is more stable than that in terms of NMI.

6 Conclusion

In this paper, we proposed a novel distributed method for collaborative feature selection method by considering privacy preserving. The proposed method learns the intermediate representations of the anchor data from multiple parties. Embedded feature selection is performed in each party based on the intermediate representations, which can solve the information deficiency in the local party. We derive an effective algorithm to solve the optimization problem and present the convergence analysis. Experimental results show that the proposed method can improve the performance of feature selection in the local party. In the future work, we will use some statistical methods and investigate the practical techniques to improve the setting of anchor data for higher performance. We also consider to extend the proposed method for the supervised case and accelerate the algorithm.

Acknowledgments

The authors would like to thank the anonymous reviewers for their helpful and constructive comments. The present study is supported in part by the Japan Science and Technology Agency (JST), ACT-I (No. JPMJPR16U6), the New Energy and Industrial Technology Development Organization (NEDO) and the Japan Society for the Promotion of Science (JSPS), Grants-in-Aid for Scientific Research (Nos. 17K12690, 18H03250).