Learning Global Models Based on Distributed Data Abstractions
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 1645-1645.
© 2005 International Joint Conferences on Artificial Intelligence
Abstract
Due to the increasing demand of massive and distributed data analysis, achieving highly accurate global data analysis results with local data privacy preserved becomes an increasingly important research issue. In this paper, we propose to adopt a model-based method (Gaussian mixture model) for local data abstraction and aggregate the local model parameters for learning global models. To support global model learning based on solely local GMM parameters instead of virtual data generated from the aggregated local model, a novel EM-like algorithm is derived. Experiments have been performed using synthetic datasets and the proposed method was demonstrated to be able to achieve the global model accuracy comparable to that of using the data regeneration approach at a much lower computational cost.
- [Bishop, 1995] C. M. Bishop. Neural Networks for Pattern Recognition. Oxford University Press, 1995.
- [Kargupta et al., 2000] H. Kargupta, B. Park, D. Hersh- berger, and E. Johnson. Collective Data Mining: A New Perspective Towards Distributed Data Mining. In Ad- vances in Distributed and Parallel Knowledge Discovery. MIT/AAAI Press, 2000.
- [Merugu and Ghosh, 2003] S. Merugu and J. Ghosh. Privacy-preserving Distributed Clustering using Gen- erative Models. In Proceedings of IEEE International Conference on Data Mining, 2003.
- [Zhang et al., 2004] Xiaofeng Zhang, C.M. Lam, and William K. Cheung. Mining local data sources for learn- ing global cluster models via local model exchange. The IEEE Intelligent Informatics Bulletin, 4(2), 2004.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Most machine learning and data mining algorithms work with a rather basic assumption that all the data can first be pooled together in a centralized data repository. Recently, there exist a growing number of cases that the data have to be physically distributed due to some practical constraints, such as privacy concerns. The need to tackle them calls for the recent research interest in distributed data mining.
A common methodology for distributed data mining is to first perform local data analysis and then combine the results to form a global one [Kargupta et al., 2000]. One major limitation is that local analysis may result in loss of information for global pattern discovery. In [Zhang et al., 2004], a model parameter exchange approach was proposed to improve the global model accuracy, which however is not a generic methodology which can easily be generalized to different types of global models. An alternative is to adopt a flexible enough model for local data abstraction and have the subsequent analysis based on the local model parameters, which is what we adopt in this paper.
As inspired by [Merugu and Ghosh, 2003], Gaussian mixture model (GMM) [Bishop, 1995] is chosen for the local data abstraction. Via different parameter settings, GMM can interpolate a set of data with more detailed information as well as a rough ensemble illustration. Thus, by sharing only local model parameters for global analysis, the degree of data privacy preservation and the bandwidth requirement in a distributed environment can readily be controlled. In this paper, an EM-like algorithm is proposed for learning a global GMM directly from the aggregated version of the local abstractions.
2 ProblemFormulation
2.1 Local Data Abstraction
Let ti ∈ ℜ d denote an observed data instance, θl denote the parameters of the l th local model (GMM) as the abstraction of the l th source. The probability density function of the l th local model plocal(ti|θl) with Kl components is given as,
L sets of local GMMs' parameters {θ1, θ2, ..., θL} obtained by performing local model-based density estimation (e.g., the EM algorithm) are sent to a global server to learn a global data model.
2.2 Learning Global Model Parameters
We start the derivation of our learning algorithm by considering first the conventional setting of the Expectation Maximization (EM) algorithm. Let Rik denote the estimated indicator for the k th component of the global model generating the i th data instance.
Assume Rlk is now a new indicator for the l th local component 1 with its underlying data to be generated by the k th global component and Rik denotes the average estimate of the probability that data instances from the l th local component are generated by the k th global component. By approximating Rik as
where Nl denotes the number of data from the l th source, the new M-steps become
1 Note that we abuse the index "l" to refer to one local component of the aggregated local model.
KL-divergence is adopted to compute Rlk (E-step), resulting in
where D(P||Q) denotes the KL-divergence between the two probabilistic models P and Q, which can be derived as
3 Experiments
Experiments have been performed using synthetic data sets for performance evaluation. Four data sets (as ground truth) were generated using known mixture models with 4, 5, 6 and 7 components, respectively. The data instances were then randomly partitioned as four sources and local GMMs were learned via the conventional EM algorithm for each source. Two global models were trained, one using the proposed method and one using the conventional data regeneration approach. As shown in the Table 1, the proposed method can achieve a speedup factor ranging from 1.5 to 257 with highly comparable model accuracy.
| time/speedup | log-like./diff. | mean/diff. | KL | ||
|---|---|---|---|---|---|
| g4 | 2: | 0.09s/1.5 | -1470.2/+2 | 3.7/-0.03 | 0.43 |
| 3: | 0.22s/1.8 | -1169.4/-70.9 | 1.0/-0.03 | 0.12 | |
| g5 | 2: | 1.33s/33 | -1850.6/-17 | 3.2/-0.02 | 0.21 |
| 3: | 8.11s/162 | -1898.5/-67 | 4.1/+0.04 | 1.31 | |
| 4: | 10.3s/257 | -1788.4/+1 | 3.3/+0.02 | 3.66 |
The proposed approach has also been applied to a more sizeable dataset generated using a GMM with 100 components. Global models with different number of components were learned and their corresponding KL-divergence values when compared with the true model are shown in Figure 1 (a). The divergence value decreased rapidly when the number of components increased from 1 to 10 and then started to saturate. One could determine the optimal number of global components by setting a threshold on the KL-divergence value as cut-off. Figure 1 (b) shows the result with 10 global components identified.
4 Conclusion and Future Plan
In this paper, we proposed a novel EM-like algorithm for learning a global model directly from the aggregated local model parameters with promising experimental results on synthetic datasets. Currently, we are extending the obtained results to learn more sophisticated global models. Furthermore, we are investigating how active negotiation between the global mediator and the local data sources for compromising individual local data sources' privacy levels can be adopted to improve the global model accuracy.


Figure 1: Experimental results with a sizeable dataset.
Acknowledgement
This work has been partially supported by RGC Central Allocation Group Research Grant (HKBU 2/03/C).
@inproceedings{ijcai2005p275,
title = {Learning Global Models Based on Distributed Data Abstractions},
author = {Zhang, Xiaofeng and Cheung, William K.},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Leslie Pack Kaelbling and Alessandro Saffiotti},
pages = {1645--1645},
year = {2005},
url = {https://ijcai.org/proceedings/2005/275},
}
TY - CPAPER TI - Learning Global Models Based on Distributed Data Abstractions AU - Zhang, Xiaofeng AU - Cheung, William K. T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 1645 EP - 1645 UR - https://ijcai.org/proceedings/2005/275 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: