Draft:Distributed Machine Learning

Distributed Machine Learning (DML) deals with the problem of analyzing data in a distributed environment by paying attention to issues like computation, communication, storage, and human factors. Like many other fields of computing, DML focuses on algorithms and systems that scale up along these dimensions. DML algorithms showed up in many different fields under different names. Distributed Data Mining ^{[1] [2] [3]} , Meta Learning ^[4] , High Performance Data Mining ^[5] , Privacy Preserving Distributed Data Mining ^{[6] [7] [8]} , Federated Machine Learning ^[9] , and Multi-Agent Learning^[10] are some examples. The benefits of parallel/distributed computing in machine learning have been acknowledged in many different fields, including Neural Networks ^[11] , Parallel Genetic Algorithms ^{[12] [13] [14]} , Multi-Agent systems ^[15] , and Data Fusion, among others.

DML algorithms vary depending on the nature of the data models supported by the different distributed sites. For example, all the data sites can have the same set of features but with different data tuples. Traditionally, this is called the Homogeneous data model. On the other hand, the features observed at different sites can be different, possibly with some overlaps. The latter scenario is called the Heterogeneous data model. A wide range of DML algorithms have been developed for learning from both homogeneous^{[16] [17]} and heterogeneous data ^{[18] [19]} . Various DML algorithms also exist for semi-structured and unstructured data ^[20] .

DML algorithms can also be classified based on how they perform computational operations. For example, we can distribute the computation of the machine learning tasks among different nodes/processors ^[21] . Depending upon the architecture, we may consider computing a single instruction with multiple data (SIMD) items simultaneously on different processors. On the other hand, we may compute multiple instructions with multiple data (MIMD) items in parallel. We may also design a DML architecture where different nodes are highly interdependent and often work in a synchronized manner (tightly coupled). On the other hand, nodes may be loosely coupled --- work fairly independently by exchanging messages, often asynchronously.

Network topology also plays an important role in the design of DML algorithms. One may create an overlay network topology for designing how different nodes are going to communicate with each other. For example, we may select a client-server type topology where the client nodes communicate only with the server. On the other hand, we may use a peer-to-peer topology where there is no single server and every node communicates only with a small number of nodes (the neighbors). Often, local and asynchronous algorithms are used for such P2P DML applications ^[22] .

Principal Component Analysis (PCA) is frequently used for creating a low-dimensional representation of the data by constructing features that capture the maximally varying directions in the data. PCA is often used for clustering, classification, and predictive model building.

PCA from distributed homogeneous data is relatively straightforward in most cases. Since the covariance matrix is additively decomposable, one can simply compute the covariance matrix at each of the local participating sites and send those matrices to the central site. The central site can construct the global covariance matrix by adding the local covariance matrices with appropriate weights. This can be followed by a regular PCA of the global covariance matrix. The global eigenvectors can be broadcast to the local sites, and they can be subsequently used for projecting the local data for clustering and other related applications.

PCA from distributed heterogeneous data is a relatively more challenging problem. The Collective Principal Component Analysis (CPCA) algorithm ^{[23] [24]} offers one way to perform distributed PCA from heterogeneous sites. The main steps of the CPCA algorithm are given below:

• Perform local PCA at each site; select dominant eigenvectors and project the data along them.
• Send a sample of the projected data along with the (dominant) eigenvectors.
• Combine the projected data from all the sites.
• Perform PCA on the global data set, identify the dominant eigenvectors, and transform them back to the original space.

To compute exact Principal Components (PCs), in principle, we need to reconstruct the original data from all projected local samples. However, since the PCA is invariant under a linear transformation, the global PCs are computed directly from projected samples.

A wide range of distributed clustering algorithms have been reported in the DML literature. They can be grouped based on the type of data model supported by the distributed nodes.

Forman and Zhang^[25] proposed a center-based distributed clustering algorithm from Homogeneous data sites that only requires the exchange of sufficient statistics, which is essentially an extension of their earlier parallel clustering work^[26] . The Recursive Agglomeration of Clustering Hierarchies by Encircling Tactic (RACHET)^[27] is also based on the exchange of sufficient statistics. It collects local dendrograms that are merged into a global dendrogram. Each local dendrogram contains descriptive statistics about the local cluster centroid that are sufficient for the global aggregation. Both approaches iterate until the sufficient statistics converge or the desired quality is achieved.

Parthasarathy and Ogihara^[28] note that finding a suitable distance metric is an important problem in clustering, including distributed clustering. They define one such metric based on association rules.

The PADMA system^[29] is yet another distributed clustering-based system for document analysis from homogeneous data sites. Distributed clustering in PADMA is aided by relevance feedback-based supervised learning techniques. Additional work on parallel and distributed clustering is reported elsewhere^{[30] [31]} .

McClean and her colleagues^[32] consider the clustering of heterogeneous distributed databases. They particularly focus on clustering heterogeneous data cubes comprised of attributes from different domains. They utilize Euclidean distance and Kullback-Leiber information divergence to measure differences between aggregates.

Clustering heterogeneous, distributed data sets constitutes an important class of problems. Kargupta, et. al.^[33] proposed a distributed clustering algorithm based on CPCA. This technique first applies a given off-the-shelf clustering algorithm to the local Principal Components (PCs). Then the global PCs are obtained from an appropriate data subset (projected) that is the union of all representative points from local clusters. Each site projects local data on the global PCs and again obtains new clusters, which are subsequently combined at the central site. A collective approach toward hierarchical clustering is proposed elsewhere^[34] .

An ensemble-based approach to combining multiple clustering is proposed by Strehl and Ghosh^[35] . Given different clustering (possibly different number of clusters in each clustering), they propose a framework to construct an ensemble of clusters in a way to maximize the shared information between original clusters. In order to quantify the shared information, they use a mutual information-based approach. Mutual information essentially denotes that how two clusters are similar in terms of distributions of shared objects.

A distributed clustering algorithm for analyzing click-stream data is reported elsewhere^[36] . This algorithm works by generating local clusterings and then combining them by analyzing the local cluster descriptions. A cluster is represented using a set of transaction IDs. The combining phase uses duplicate cluster removal and a technique for generating maximal large itemsets (where items correspond to the transaction IDs) to define the new global clusters.

Just like unsupervised DML algorithms, their supervised counterparts can also be grouped based on the distributed data models they are designed to work with.

Many of the DML algorithms for distributed supervised learning from homogeneous data sites are related to ensemble learning techniques^{[37] [38] [39] [40]} . The ensemble approach produces multiple models (base predictors) and combines the outputs of the base modules in order to enhance accuracy. Different models can be generated at different sites and ultimately aggregated using ensemble strategies. Several ensemble-based techniques have been reported in the literature.

Fan et al.^[41] discussed an AdaBoost-based ensemble approach from this perspective. Breiman^[42] considered Arcing as a way to aggregate multiple blocks of data, especially in on-line setting. An experimental investigation of Stacking^[43] for combining multiple models was reported elsewhere^[44] . The meta-learning framework^{[45] [46]} offers another possible approach to learn classifiers from homogeneous, distributed data. In this approach, supervised learning techniques are first used to learn classifiers at local data sites; then meta-level classifiers are constructed by either learning from a data set generated using the locally learned concepts or combining local classifiers using ensemble techniques. The meta-level learning may be applied recursively, producing a hierarchy of meta-classifiers. Meta learning follows three main steps:

• Generate base classifiers at each site using a classifier learning algorithm.
• Collect the base classifiers at a central site. Produce meta-level data from a separate validation set and predictions generated by the base classifier on it.
• Generate the final classifier (meta-classifier) from meta-level data. Learning at the meta-level can work in many different ways. For example, we may generate a new dataset using the locally learned classifiers. We may also move some of the original training data from the local sites, blend it with the data artificially generated by the local classifiers, and then run a learning algorithm to learn the meta-level classifiers. We may also decide the output of the meta-classifier by counting votes cast by different base models. A meta-learning-type technique known as knowledge probing is reported in^[47] . A Java-based distributed system for meta-learning is reported elsewhere^{[48] [49]} . Meta-learning illustrates two characteristics of DML algorithms — parallelism and reduced communication. All base classifiers are generated in parallel and collected at the central location along with the validation set.

Homogeneous DML algorithms usually do not work well for learning from heterogeneous distributed data. In the heterogeneous case, each local site observes only a subset of features. Therefore, a DML algorithm must be able to learn a model using different features observed at different sites without downloading all the data to a single location. Ensemble-based approaches described in the previous subsection usually generate high-variance local models^[50] and fail to detect the interaction between features observed at different sites. This makes the problem fundamentally challenging.

In some applications, heterogeneous DML may not require detecting interactions between features from different sites. In other words, the underlying problem may be node-wise decomposable. This scenario is relatively easy to handle. An ensemble-based approach to learn distributed classifiers is likely to work well for this case. Even if the application does not involve distributed data, vertical partitioning of data for decomposing the learning problem into smaller sub-problems using a data parallel approach can speed up the process^[51] . However, the assumption of node-wise decomposability is not necessarily correct in every application. In the general case, heterogeneous DML may require building classifiers using non-linearly interacting features from different sites.

The WoRLD system^[52] also works by making some assumptions about the class of DML problems. It works by collecting first order statistics from the data. It considers the problem of concept learning from heterogeneous sites by developing an "activation spreading" approach. This approach first computes the cardinal distribution of the feature values in the individual data sets. Next, this distribution information is propagated across different sites. Features with strong correlations with the concept space are identified based on the first order statistics of the cardinal distribution. Since the technique is based on the first order statistical approximation of the underlying distribution, it may not be appropriate for machine learning problems where concept learning requires higher order statistics.

There exist a few DML algorithms that use an ensemble of classifiers for mining heterogeneous data sites. However, these techniques use special-purpose aggregation algorithms in order to handle some of the issues discussed earlier in this section. The aggregation technique proposed in^[53] uses an order statistics-based approach for combining high variance local models generated from heterogeneous sites. The technique works by ordering the predictions of different classifiers and using them in an appropriate manner. Their work developed several methods, including the selection of an appropriate order statistic as the classifier and taking a linear combination of some of the order statistics ("spread" and "trimmed mean" classifiers). It also analyzes the error of such a classifier in various situations. Although these techniques are more robust than other ensemble-based models, they do not explicitly consider interactions across multiple sites.

Park and his colleagues^[54] developed a technique to learn decision trees from heterogeneous, distributed sites. The approach can be classified as an ensemble-based approach. However, they also proposed a Fourier spectrum-based technique to aggregate the ensemble of decision trees. They note that any pattern involving features from different sites cannot be captured by the simple aggregation of local classifiers generated using only the local features. In order to detect such patterns, they first identify a subset of data that none of the local classifiers can classify with high confidence. This subset of the data is merged at the central site, and another classifier (central classifier) is constructed from it. When a combination of local classifiers cannot classify a new observation with a high confidence, the central classifier is used instead. This approach exhibits a better performance than a simple aggregation of local models. However, its performance is sensitive to the confidence threshold.

Kargupta and his colleagues considered a Collective framework to address data analysis in heterogeneous DML environments and proposed the CDM^[55] framework. CDM can be deployed for learning classifiers and predictive models from distributed data. Instead of combining incomplete local models, it seeks to find globally meaningful pieces of information from each local site. In other words, it obtains local building blocks that directly constitute the global model. Given a set of labeled training data, CDM learns a function that approximates it. The foundation of CDM is based on the observation that any function can be represented in a distributed fashion using an appropriate set of basis functions. When the basis functions are orthonormal, the local analysis produces correct and useful results that can be directly used as a component of the global model without any loss of accuracy. The main steps of CDM can be summarized as follows:

• Generate approximate orthonormal basis coefficients at each local site.
• Move an appropriately chosen sample of the data sets from each site to a single site and generate the approximate basis coefficients corresponding to non-linear cross terms.
• Combine the local models, transform the model into the user described canonical representation, and output the model.

Here non-linear terms represent a set of coefficients (or patterns) that cannot be determined at a local site. In essence, the performance of a CDM model depends on the quality of estimated cross-terms. Typically, CDM requires an exchange of a small sample that is often negligible compared to the entire data.

The CDM approach was originally explored using two important classes of function induction problems — learning decision trees and multivariate regressors. Fourier and Wavelet-based representations of functions have been proposed elsewhere^[56] for constructing decision trees and multivariate regressors, respectively. The Fourier spectrum-based approach works by estimating the Fourier Coefficients (FCs) from the data. It estimates the local FCs from the local data and FCs involving features from different data sites using a selected small subset of data collected at the central site. It has been shown elsewhere^{[57] [58]} that one can easily compute the Fourier spectrum of a decision tree and vice versa. This observation can be exploited to construct decision trees from the estimated FCs. However, fast estimation of FCs from data is a non-trivial job. Estimation techniques usually work well when the data is uniformly distributed. This problem is addressed by the development of a resampling-based technique^[59] for the estimation of the Fourier spectrum.

The collective multivariate regression ^[60] chooses a wavelet basis to represent local data. For each feature in data, wavelet transformation is applied, and significant coefficients are collected at the central site. Then the regression is performed directly on the wavelet coefficients. This approach has a significant advantage in communication reduction since a set of wavelet coefficients usually represents raw data in a highly compressed format.

Choen et al.^[61] developed an algorithm for distributed asynchronous deep neural network training using a single momentum buffer to mitigate gradient staleness. This approach tries to improve the scalability, stability, and speed of training large neural networks in a distributed environment.

The field of high-performance parallel and distributed computing is also closely related to DML in many ways. High-performance parallel computing environments are widely used for scaling up machine learning from very large data sets. There exists a large volume of high-performance machine learning and data mining literature^{[62] [63] [64] [65] [66] [67] [68] [69]} .

Algorithms for machine learning over P2P networks can be grouped in the following main areas: (1) heuristics-based, (2) broadcast-based, (3) gossip-based, and (4) local algorithms.

The P2P k-Means algorithm by Bandyopadhyay et al.^[70] is an example of the heuristics-based approach. In this category of algorithms, usually a peer learns a model based on its own data and the data collected from its neighbors. Often, these algorithms do not come with accuracy guarantees.

Sharfman et al.^[71] reported broadcast-based algorithms for P2P systems. Since these algorithms rely on broadcasts-based communication, the communication cost usually increases fast as the number of nodes increases.

Gossip algorithms rely on the properties of random samples to provide probabilistic guarantees on the accuracy of the results. Researchers have proposed various algorithms for computing data aggregates, such as the average, sum, and max on P2P networks using gossip-based techniques. Kempe et al.^[72] and Boyd et al.^[73] present such primitives. In gossip protocols, a peer exchanges data or statistics with a random peer. However, they can still be quite costly.

Local distributed algorithms have been proposed for data analysis in P2P networks. Local algorithms rely upon data-dependent conditions (local rules) in order to stop propagating messages. This means that if the data distribution does not change, the communication overhead is relatively low. On the other hand, the local rules are violated when the distribution changes. Local algorithms were first introduced in the context of graph theory by Afek et al.^[74] and Linial^[75] . Local algorithms have been developed for several data analysis problems: association rule mining^[76] , outlier detection^[77] , meta-classification^[78] , Eigen-monitoring^[79] , Decision Tree induction^[80] , Top-k Inner Product monitoring^[81] over P2P networks.

Privacy is an important issue in many applications. A growing body of literature on privacy-sensitive DML is emerging. These algorithms can be divided into different groups based on the model of privacy they adopt. One approach adopts a distributed framework with various supported models of privacy. On the other hand, there exist some approaches that add randomized perturbations to the data in such a way that the individual data values are distorted while still preserving the underlying distribution properties at a macroscopic level. The following part of this section briefly discusses these two approaches.

The distributed approach supports the computation of machine learning models and extraction of "patterns" at a given node by exchanging only the minimal necessary information among the participating nodes without transmitting the raw data. The field of DML^[82] offers several distributed algorithms that are sensitive to privacy. For example, the meta-learning-based JAM system^[83] was designed for analyzing multi-party distributed sensitive data, such as financial fraud detection. The Fourier spectrum-based approach to represent and construct decision trees^{[84] [85]} , the Collective hierarchical clustering^[86] are examples of additional distributed machine learning algorithms that may have applications in privacy-preserving learning from distributed data. Several additional distributed techniques to analyze multi-party data have been reported. A privacy-preserving technique to construct decision trees^[87] proposed elsewhere^[88] , a multi-party secured computation framework^[89] , association rule mining from homogeneous^[90] and heterogeneous^[91] distributed data sets are some examples. There also exists a collection of useful secure multi-party computation primitives (e.g., secure sum computation^[92] , secure scalar product computation) that can be used for developing distributed privacy-preserving machine learning algorithms.

There is also a somewhat different approach, and the algorithms that belong to this group work by first perturbing the data using randomized techniques. The perturbed data is then used to extract the patterns and models. The randomized value distortion technique for learning decision trees and association rule learning^[93] are examples of this approach. Additional work on randomized masking of data can be found elsewhere^[94] . However, Kargupta^[95] showed that simple additive noise may not be suitable for privacy protection.

A restricted form of DML that primarily seems to focus on iterative deep learning from distributed data. More information about Federated Machine Learning can be found elsewhere^[96] .

• Draft articles on computing
• Draft articles on mathematics
• AfC submissions on science, mathematics and engineering
• Pending AfC submissions
• AfC pending submissions by age/12 days ago
• AfC submissions by date/22 November 2025