Fast Learning from Distributed Datasets without Entity Matching

1 Introduction

Learning from massively distributed data collections and multiple information sources has become a pivotal problem, yet it faces critical challenges, among which is the fact that it relies on reconstructing consistent examples from diverse features distributed between different data handling peers. Exhaustive search to solve this problem is simply not scalable, nor communication efficient, and sometimes not even accurate [Estrada et al., 2010; Zhang et al., 2015].

-A key technical message of our paper is:

Entity resolution can be bypassed to carry out supervised learning almost as accurately as if its solution were known.

A main motivation of this work comes from the reported experience that combining features from different sources leads to better predictive power. For instance, insurance and banking data together can improve fraud detection; shopping records well complement medical history for estimating risk of disease [Tsui et al., 2003]; joining heterogeneous data helps prediction in genomics [Lanckriet et al., 2004; Yamanishi et al., 2004]; security agencies integrate various sources for terrorism intelligence [Sweeney, 2005; Christen, 2006; Sproull et al., 2015].

A typical data fusion framework relies however on a known map between entities [Bleiholder and Naumann, 2008], i.e. peers have partially different views of the same examples. Instead, we assume the datasets do not share a common ID, as shown in Figure 1; that is, for example, the case when data collection of was performed independently by each peer, or when sources were deliberately anonimized. Thus, we can think the data as vertically partitioned (VP). Entity resolution (ER), or entity matching [Christen, 2012], would be the traditional approach for reconciling entities with no shared ID 1 . It approximates a JOIN operation, assuming that some of the attributes are shared, e.g., age-band, gender, postcode (etc.), and hence can be used as "weak IDs". Most techniques for ER are based on similarity functions and thresholding: candidate entities are selected as matches when their similarity is above a threshold. Both components can be tuned on some ground truth matches and effectively enhanced with learning techniques [Bilenko and Mooney, 2003][Christen, 2012]. The various metrics of ER encompass lots of different parameters, including generality, accuracy, soundness, scalability, parallelizability [Rastogi et al., 2011]. The standard pipeline for learning with ER is depicted in Figure 2 (left): (1) entities are matched based on similarity and heuristics, (2) they are merged in one unique database and (3) a model is learnt on the joint data. Common issues in fusion, such as conflicts and heterogeneity [Bleiholder and Naumann, 2008], are not considered in this work.

From a high level view, ER integrates data as a pre-process for other tasks. When it comes to learning from ER'ed data, small changes in ER can have large impact on evaluating classifiers, even for simple classifiers as linear models. To see this, suppose we are in the toy example of Table 1. Here, all shared variables have the same values, so entity matching has two potential solutions (notice that one of the shared variables is class c). One, say ER1, is matching e1 with e01 and e2 with e02 . We denote the examples obtained by e11 ▷= ((1↪ -1↪ 1)↪ 1) and e22 ▷= ((-1↪ 1↪ 1)↪ 1) (an example is a pair (observation, class)). The other solution, say ER2, is matching e1 with e02 and e2 with e01 . We denote the examples obtained by e12 ▷= ((1↪ 1↪ 1)↪ 1) and e21 ▷= ((-1↪ -1↪ 1)↪ 1). Now, consider linear classifier ✓ = (1↪ 1↪ 1) 2 R3 ; the class it gives is the sign of its inner product with an observation, ✓(z) ▷= sign(✓>z). While ✓ classifies perfectly on ¶e11↪ e22♦ (zero error), it classifies no better than random on ¶e12↪ e21♦ (error 50%).

To cope with (VP) data, we use a recent trick for learning from private data [Nock et al., 2015]: examples are not necessary to learn an accurate linear classifier. We stress the fact that "accurate" refers to the quality of the class prediction from observations. The input of the algorithm consists of Rademacher observations, rados. A rado is just a sum, over a subset of examples, of the observations times their class. Surprisingly, we can learn with data in this form and, moreover, the output classifier does not need any post-processing since it is the same as if we were learning with examples.

1 This is clearly non trivial: if just two rows in each dataset have the same exact values for the shared features across the p peers, this yields 2p possible matchings for the two examples involved.

Contributions - Our contribution starts from noticing that many rados are invariant to the selection of different solutions for entity resolution. For example, consider again Table 1. Since all classes are positive, computing a rado is just summing observations. Let ⇡ij↪kl be the rado that sums those of examples eij and ekl. Then, surprisingly, regardless of the solution to ER, this rado is the same:

This, as we show, always holds in the (VP) setting: there exists a huge, i.e., of potential exponential size, set of rados that match the set that could be built knowing the true entity resolution. We give the algorithm that builds these rados. It is easily parallelizable and requires sublinear communication, i.e. the amount of information that transits is no larger-and may be much smaller - than the size of all peers' data.

These "ideal" rados are not just interesting per se: learning from them (Figure 2, right) is both efficient and accurate. We show that using them leads to approximating the classifier that would be optimal on the set of all (ideally ER'ed) examples. This involves three technical contributions:

• ÷ The first is an elementary proof that the minimisation of the Ridge regularized square loss [Hoerl and Kennard, 1970] on examples is equivalent to the minimisation of a regularized loss on rados, which we call the M-loss.
• ÷ We then give the closed-form solution for the classifier minimizing the M-loss. Surprisingly, it shows that the minimisation of the regularized M-loss, over the complete (possibly exponential-size) set of "ideal" rados can be done not just in polynomial time: it is in general faster than the minimization of the Ridge regularized square loss over examples.
• ÷ Finally, the optimal M-loss classifier learnt using only the set of "ideal" rados converges - as the number of shared features increases - to the minimizer of the Ridge regularized square loss over all ideally ER'ed examples. In other words, as the number of shared features (or their modalities) increases, we are guaranteed to converge to the best classifier learned over examples.

Last, but not least, while we focus on the two-classes setting, description features need not be boolean. There is in fact no restriction apart from the fact that shared features are treated as ordinal instead of plain real: if one feature had as many modalities as there are examples, then there would be no need to address ER. The rest of this paper is as follows. Section ∗2 provides preliminaries. ∗ 3 follows that shows how to learn from distributed data to minimise, indirectly, the Ridge regularized square loss over the ER'ed complete data. ∗ 4 introduces a more realistic learning setting, then used in the experimental analysis of ∗ 5. Finally, ∗ 6 discusses our approach and ∗ 7 concludes the paper.

2 Preliminaries

Learning setting We let [n] ▷= ¶1↪ 2↪ ▷ ▷ ▷ ↪ n♦ for n 2 N⇤; boldfaces like x indicate vectors, whose coordinates are denoted as xi. Notation 1¶▷♦ is the indicator function. We briefly recall the task of binary classification with linear models ✓ as learning a predictor for label (or class) y 2 ¶◦1♦, from a total (learning, training) sample S ▷= ¶(xi↪ yi)↪ i 2 [m]♦. Each example is an observation-label pair (xi↪ yi) 2 X ⇥ ¶◦1♦, with X ✓ Rd the feature space, and it is drawn i.i.d. from an unknown distribution. We also denote X ▷= ⇥dk=1Xk, the cartesian product of its component spaces. We reserve the word entity for a generic record in a dataset, the object of matching, and attributes or features to its fields.

Our setting departs from the standard setting in what follows. Instead of one total training sample, we have p (sub)samples, Sj of size mj, j 2 [p] for some p > 1. Each one is defined in its own feature space Xj ▷= ⇥dj k=1Xjk , where jk 2 [d]↪ 8k. To get a simple case of this framework, shown in Figure 1, one may see each Sj ▷= ¶(xji ↪ yj i )↪ i 2 [mj]♦ handled by a peer Pj . Throughout the paper, subscripts i will refer to an example or entity, while superscripts j to a peer. We rely on the following assumption:

• (A) The class and a subset of features J ✓ ¶Xk♦dk=1 are shared by all peers. Each other feature is exclusive to one peer.

Hence, there exists dim(J) + 1 columns that represent the same set of attributes among peers, and one of them is the class. Each of the dimensions of J is in all Xj s. This is a realistic assumption for the features in J: in the (VP) setting, which is a gold standard of database frameworks, the domain is vertically partitioned for the non-shared features, implying mj = m↪ 8j 2 [p]. In this case, there exists a (unknown) oneto-one mapping between the peers' rows. The shared label might be harder to justify, since it is the attribute we aim to predict. However, as argued in Section 6, if at least one peer has classes than all peers can get their labels as well without entity resolution, by the use of algorithms that learn with label proportions [Patrini et al., 2014; Quadrianto et al., 2009].

Rademacher observations In the standard classification model, a Rademacher observation (rado) is a simple linear transformation of the examples in sample S [Nock, 2015; Nock et al., 2015]. Now, let σ 2 ⌃m ▷= ¶-1↪ 1♦m. Then a rado is ⇡σ ▷= Pmi=1 1¶yi = σi♦ yi ·xi, where yi ·xi is termed an edge vector. One of the 2m rados, ⇡y = Pmi=1 yi · xi, (σ = y), is a sufficient statistic w.r.t. class y for a wide set of losses; see the mean operator [Patrini et al., 2014], [Patrini et al., 2016a]. In our distributed setting, we extend the definition as follows. We let s 2 J denote a signature, i.e. a vector of shared attributes, y 2 ¶◦1♦ and let j index peer Pj . A rado is then:

where projI(z) denotes the restriction of a vector z to I. In short, ⇡j(s↪y) sums edge vectors local to Pj whose examples match signature s and class y. Intuitively, we can conceptualize those rados and expressing statistics locally sufficient for the examples sharing the same signature s in the data of Pj . Let F(z) ✓ X be the set of features of z. We also define, for any F0 ◆ F(z), liftF0 (z) to be the vector z0 described using F0 such that projF(z)(z0 ) = z and projF0 ∩F(z)(z0 ) = 0. While projF(z) removes coordinates of z, liftF0(z) "completes" the coordinates of z with zeroes.

By analogy with entity resolution [Whang et al., 2009], we define block rados as rados, lifted to X, that are sums of edges matching a particular signature and class in all peers.

Definition 1 For any s 2 J, y 2 ¶-1↪ 1♦, let m(s↪y) be the number of examples matching signature (s↪ y). Then a basic block (BB) rado for (s↪ y) is

We need to subtract the second term to take into account that s has already been summed up m(s↪y) times by each peer. Let J⇤ ▷= ¶(s↪ y) 2 J ⇥ ¶-1↪ 1♦ : 9j 2 [p]↪ ⇡j(s↪y) 6= 0♦. This latter set, which can easily be computed from all peers, has cardinal m⇤ ▷= ♣J⇤♣  m, and even m⇤ ⌧ m when few features are shared. We let RB ▷= ¶⇡vi ↪ 8i 2 [m⇤]♦ denote the ordered set of each BB rado, each coordinate of v = (s↪ y) being in one-one correspondence with an element of J⇤. A superset of RB is interesting, that considers all sums of vectors fromRB:

We call R⇤ the set of block rados. Notice that we may have ♣R⇤♣ = ⌦(2Pj ♣Sj ♣ ). It is therefore intractable in general to explicitly compute R⇤. However, ♣RB♣ = O(Pj ♣Sj ♣) and to compute it, we just need the set of ⇡j(s↪y) , hence a communication complexity that can be much smaller than Pj ♣Sj ♣.

3 Building and learning fromBB rados

Why and how can we use rados to learn accurate classifiers? This first subsection does not concern the distributed setting. Instead, it summarizes and comments findings from [Nock et al., 2015], [Nock, 2015].

Example vs rado losses Learning ✓ on S is done by minimizing a loss function. Here, we consider the Ridge regularized square loss [Hoerl and Kennard, 1970] (Γ is sym. positive definite, SPD),

It is crucial to remark that this loss is described over the total sample S of examples (see the red rectangle in Figure 1). This is the loss we want to minimize, exactly or approximately. One reason we choose this loss is that in the standard classification framework, it admits a simple closed form solution:

where X ▷= [x1♣x2♣ · · · ♣xm], and so, XX> = Pi xix>i . Remark that ✓? ex involves ⇡y, one particular rado 2 . For any ⌃0m ✓ ⌃m ▷= ¶-1↪ 1♦m, we let RS↪⌃0m ▷= ¶⇡σ : ⇡σ 2 ⌃0m♦ denote the set of rados that can be crafted from ⌃0m using S.

Definition 2 The M-loss over RS↪⌃0m of classifier ✓ is:

where expectation and variance are computed with respect to the uniform sampling of σ in ⌃0m.

Eq. (5) resembles a Markowitz mean-variance criterion [Markowitz, 1952] -with no coefficient for the risk aversion. What this means is that a good classifier trained on rados should have large "return" and small "risk", where the risk is the variance of its predictions and the return is its inner product with the expected rado.

The next Theorem shows that what was known for the logistic loss in [Nock et al., 2015] also holds for the square loss: `sql(✓) (other dependences omitted) is equal to a strictly increasing function of `M(✓), described over rados, for any ✓. Hence, minimizing `sql(✓) over examples is equivalent to minimizing `M(✓) for the same classifier. The proof of the Theorem is interesting in itself as it simplifies the long derivation of the more general equivalence in [Nock, 2015].

Theorem 3 Let ⌃m ▷= ¶-1↪ 1♦m. Then, for any S, any Γ and any ✓, `sql(S↪ ✓; Γ) = 1 + (4◁m) · `M(RS↪⌃m ↪ ✓; Γ) with

Proof First, we remark that E⌃m [✓>⇡σ] = ✓>E⌃m [⇡σ] = (1◁2) · ✓>⇡y, since each example participates to half of the 2m rados. Letting ˜ v ▷= 2m+2 · V⌃m [✓>⇡σ], we also have

2 Notice here its sufficiency w.r.t. y, as labels do not appear anywhere else in the formula.

▷= Pσ2⌃m σiσi0 . Now, for any i 6= i0 , σiσi0 takes

and we get Theorem 3 by integrating Ridge regularization.

Hence, minimizing the Ridge regularized square loss over examples is equivalent to minimizing a regularized version of the M-loss, over the complete set of all rados. This set has exponential size. A possibility is to randomly subsample the set, along with proving good uniform convergence bounds for the M-loss - this can be done in the same way as for the logistic loss [Nock et al., 2015]. However, in the case of the square loss, greed pays twice: learning from all rados in R⇤ may be both cheap (computationally) and accurate.

Computation and optimality of R⇤ In our distributed context, we do not have access to all rados because we do not assume to known the entity matching function. Yet, we are going to show a first result which is, in a sense, stronger: R⇤ always belongs to RS↪⌃m . Therefore R⇤ -potentially exponential-size- gives us a set of rados that would have been built from S, had we known the perfect solution to entity matching. So, even without carrying out entity matching, we have access to a potentially huge set of "ideal" rados which we can use to learn ✓ via the minimization of `M(▷↪ ✓; Γ). Furthermore, there exists a simple algorithm to build RB.

Algorithm 1 summarizes the protocol. Each peer Pj crafts rados upon request of a particular signature and label; "CRAFT(s↪ y) " symbolizes a message sent, expecting ⇡j(s↪y) in return. Remark that the computation of each rado for each peer can easily be performed in parallel. We now show one of the main results of this paper: Algorithm 1 always provides the basis for the set R⇤ of the "ideal" rados.

Theorem 4 In setting (VP), for any p ≥ 2, any S, any J. Let RB be the output of Algorithm 1 and let R⇤ its superset by eq. (2). Then, R⇤ ✓ RS↪⌃m .

Algorithm 1 RADOCRAFT(P1 ↪ P2 ↪ ▷▷▷↪ Pp )

Input Peers P1 ↪ P2 ↪ ▷▷▷↪ Pp ; Step 1: Let RB ;; Step 2: for s 2 J, y 2 ¶◦1♦: 2.1: Let ⇡(s↪y) 0 2 Rd ; 2.2: for j 2 [p]: 2.2.1: ⇡(s↪y) ⇡(s↪y)+liftX(CRAFT(s↪ y) Pj ) 2.3: RB RB [ ¶⇡(s↪y)♦; Return RB;

Proof (sketch) The Theorem follows once three simple facts are established in the (VP) setting: (a) the true entity matching exists, (b) any BB rado for pair (s↪ y) would be obtained as a rado summing the contributions of all examples in S matching the corresponding signature s and class y, (c) we obtain RB ✓ RS↪⌃m , from which follows the Theorem's statement with eq. (2) and the fact that any sum of a subset of rados in RB would also be in RS↪⌃m since an example cannot match two distinct couples (signature, class).

Learning from all rados of R⇤ How do we minimize the regularized M-loss and, more importantly, which subset of rados from R⇤ shall we use? As already discussed, we choose "greediness" against randomization: instead of picking a (small) random subset of R⇤, we want to use them all because we know that all of them are "ideal" or close to being so via Theorems 4. Recall that ♣R⇤♣ may be of exponential size (in m, d, ♣J⇤♣, etc.). We now show that if we consider all of R⇤, the optimal ✓? rad of `M(R⇤↪ ✓; Γ) has an analytic expression which depends only on the rados of RB. In short, it is even faster to compute than ✓? ex from S in eq. (4), and can be directly computed from the output of Algorithm 1.

where B stacks in columns the rados of RB, and dimc(B) is the number of columns of B.

Proof The proof uses the following trick: consider any sample S0 such that its edge vectors match the basic block rados. Remark that XX> = Pi (yixi)(yixi)> in eq. (4) depends only on edge vectors, and so, since ⇡y = B1, the optimal square loss classifier on S0 is ✓? rad in eq. (9), which, through Theorem 3, is also the optimal classifier on `M(R⇤↪ ✓; Γ).

When m⇤ = m, each element of RB is in fact an example, and we retrieve eq. (4). One consequence of Theorem 5 is the following convergence property which we sketch: in the (VP) setting, for any " ≥ 0, there exists a minimal size for J⇤ such that ✓? rad will be "-close to ✓? ex , where the closeness can be measured by k✓? rad - ✓? ex k2 or ♣cos(✓? rad ↪ ✓? ex )♣. The statement of DRL (Distributed Rado-Learn) is given in Algorithm 2. In Step 1, "column(▷)" takes a set of vectors and put them in column in a matrix.

Algorithm 2 DRL(P1 ↪ P2 ↪ ▷▷▷↪ Pp ; Γ)

Input Peers P1 ↪ P2 ↪ ▷▷▷↪ Pp , SPD matrix Γ, γ > 0; Step 1: B Column(RADOCRAFT(P1 ↪ P2 ↪ ▷▷▷↪ Pp )); Step 2: ✓ (BB> +γ · Γ)-1 B1; Return ✓;

4 Amore realistic setting

What happens if we drop the assumption of data being vertically partitioned (VP)? Or equivalently, what if examples are not shared by all peers ? This is a much more realistic scenario. Since there is no shared ID- and the data may have been anonymized - we are not even in a situation where we can guarantee that a specific client of the bank is, or is not, a client of the insurance company. Thus, there may be significant unknown data "to reconstruct" the total sample S, but we do not know which specific examples have missing features. In this most general setting (G), it is possible to show that a very simple transformation of the rados, involving only the shared features, has in expectation the same properties so far described and for which Theorem 4 holds in expectation. Due to lack of space, details are left to a longer version of the paper [Patrini et al., 2016b]. However, in the next Section, we provide an experimental validation of our approach in both the settings.

5 Experiments

Algorithms We have evaluated the leverage that DRL provides compared to the peers, that would learn using only their local dataset. Each peer Pj estimates learns through a ten-folds stratified cross-validation (CV) minimization of `sql(Sj ↪ ✓; γ · Iddj ) (see eq. (4)), where γ is also locally optimized through a ten-folds CV in set G ▷= ¶▷01↪ 1▷0↪ 100▷0♦. DRL minimizes `M(R⇤↪ ✓; Γ) (solution in eq. (9)) where RB is built using RADOCRAFT, with the set of all peers as input.

We have carried out a very simple optimisation of the regularisation matrix of DRL as a diagonal matrix which weights differently the shared features, Γ ▷= Diag(liftX(projJ(1)))+ γ · Diag(liftX(projX∩J(1))), for γ 2 G. γ is optimized by a 10-folds CV on I⇤. CV is performed on rados as follows: first, RB is split in 10 folds, RB↪`, for ` = 1↪ 2↪ ▷▷▷↪ 10. Then, we repeat for ` = 1↪ 2↪ ▷▷▷↪ 10 (and then average) the following CV routine:

1. DRL is trained using RB∩RB↪`;
2. DRL's solution, ✓? rad , is evaluated on "test rados" by computing `M(RB↪`↪ ✓? rad ; Γ).

The expression of Γ for rados exploits the idea that the estimations related to a shared feature can be much more accurate than for another, non-shared feature.

Domain generation We ran experiments on a dozen UCI domains. Only two are fully detailed here, due to reason of space: they are ionosphere (m ⇥ d) = (351 ⇥ 33) and musk = (6598 ⇥ 166) - the others appears in [Patrini et al., 2016b]. For each domain, we have varied (i) the number of peers p, (ii) the number of shared features dim(J), and (iii)

the number b of numeric modalities ("bins") each shared feature was reduced to (it controls the size of I⇤). The training sample is split among peers, each keeping record of I and its own features (non-shared features are evenly partitioned among peers). Finally, for some ps 2 [0↪ 1], each peer Pj selects a proportion ps of its examples index and for each of them, another peer Pj 0 , chosen at random, gets the example as well (on its own set of features Xj 0 ). This policy implements (G). When ps = 0, this is setting (VP). We then run all algorithms for each value p↪ dim(J)↪ b↪ ps. As we shall see, b appears to have a relatively small influence compared to the other factors, so we mainly report results combining various values for p↪ dim(J) and ps, for the range of values of p↪ dim(J) specified in the corresponding Tables (3, 4), and for ps 2 ¶0▷0↪ 0▷2♦. We have chosen b = 4 for all domains, except when it is not possible (if for example all features are boolean), in which case we pick b = 2.

Metric We used two metrics. The first,

is the test error for DRL minus that of the optimal peer in hindsight (since we consider the peer's test error). when ∆ < 0, DRL beats all peers. For example, Table 3 (left) provides the results obtained on UCI domain ionisphere. We see that for almost all combinations of p and dim(J), DRL beats all peers. We give for each domain the smallest test error obtained for a peer among all runs for each domain: this is an indication of the room of improvement for DRL, and it also shows that in general, at least some (and in fact most) peers were always very significantly better than random guessing, a safe-check that DRL is not just beating unbiased coins.

To evaluate the statistical significance, we compute

q ▷= proportion of peers statistically beaten by DRL ▷

To compute the test, we use the powerful BenjaminiHochberg procedure on top of paired t-tests with q⇤ = p-val = 0▷05, [Benjamini and Hochberg, 1995]; q = 0▷8 surface helps see when DRL statistically beats all peers. For example, Table 3 (right) displays that DRL does not always statistically beat all peers when ∆ < 0, yet it manages to stastically beat all of them in a wide range of p↪ dim(J) values. Table 4 display that DRL tends to systematically beat all peers when p is sufficiently large.

Results To summarize our results, all domains display that there exists regimes (p↪ dim(J)) for which DRL improves on all peers, in some cases significantly. Sometimes, the improvement is sparse, but sometimes it is quite spectacular and in fact (almost) systematic. Drilling down into the results displays two patterns that seem to be quite general: the first is when the so-called Oracle, i.e. the learner that learns from the complete training fold before it is split among peers - and therefore knows the solution to entity matching -, has almost optimal error, but local peers are in fact very far from this optimum. This indicates that many features, properly combined, are necessary to attain the best performances. In

#bins per shared f.

Oracle

Table 2: Left: test error of DRL on domain ionosphere, as a function of the number of bins, aggregating all results varying p and dim(J); the green line denotes the average values. Right: scatterplot of the test error of DRL (y) vs. that of the Oracle (learning using the complete entity-resolved domain). Green in the dark grey area denote better performances of DRL; blue in the light grey area denote better performances of the Oracle (but not statistically better). Red in the white area denote statistically better performances of the Oracle (filled points: ps = 0▷2; empty points: ps = 0▷8).

such cases, DRL can manage to have performances close to the Oracle, and yields to a gap in classification compared to peers which can properly be huge - sometimes, DRL's test error is smaller than that of the best peer by more than 20% -. The second pattern is that for many domains, there is a threshold value for p beyond which DRL progressively improves on all peers (statistically). These two patterns seems to advocate that DRL may represent a very significant leverage of peer's data for moderately to massively distributed learning problems, when entity resolution is not available.

To analyze further our results, Table 2 (left) displays that binning indeed does not affect significantly DRL on average, which is also good news, since it means that there is no restriction on the shared features for DRL to perform well: shared features can be binary, or categorical with any number of modalities. Additionally, Table 2 (right) compares the performances of DRL with respect to those of the Oracle on a domain for which DRL obtains somehow "median" performances among all domains, sonar, (m⇥ d) = (208 ⇥ 60). The Oracle (10-folds CV from the total ER'ed S) is idealistic since in general we do not know the solution to ER, yet it gives clues on how close DRL may be from the "graal". Interestingly, DRL comes frequently under the statistical significance radar (↵ = 0▷05). In notable cases (more frequent as ps increases), DRL beats Oracle - but not significantly. Aside from theory, these are good news as DRL does not assume ER'ed data, and uses an amount of data which can be ⇠ p2 times smaller than Oracle.

6 Discussion and related work

We remark that our framework is not formally comparable with ER, since the two address different problems. On one hand, ER has a much broader applicability than the problem object of this paper; learning on distributed datasets is less general than ER: in fact, we show a solution that bypasses ER. On the other hand, learning-based ER [Bilenko and Mooney, 2003] as well as manifold alignment techniques [Lafon et al., 2006] are viable only knowing some ground truth matches - which are not required for working with rados. From another perspective, in concert with the open issues in [Getoor and Machanavajjhala, 2012], we study ER as component of a pipeline for classification, and highlight how matching is not necessary for the purpose of learning.

In spite of those considerations, we can still draw comparisons with methods that learn on top of data merged through ER (Table 5). In both settings, no ID is shared between datasets but some attributes must be so, in order to allow entities comparison for matching or for building rados. Obviously, entity matching does not require the labels to be one of those shared attributes, while this is a fundamental hypothesis of our approach. Although, it is not as restrictive as it might seem at first: if just one peer has labels, then all can obtain labels on their own data, via learning from label proportions [Quadrianto et al., 2009], [Patrini et al., 2014]: the label handling peer computes the label proportions per each block; the "bags" are defined by examples matching a particular signature. Proportions are then shared among all other peers, which can train a classifier with them so as to estimate a label for each observation.

To discuss time complexity, let us consider a simplified problem with only 2 peers in the (VP) scenario. In terms of complexity of fusion, if we assume that examples are uniformly distributed in the blocks, each block has size m◁m? . DRL builds each block rado in time O(m◁m? ), with total cost linear in m. ER takes O((m◁m? )2 ·Tsim) to match entities in each of the m? blocks, where Tsim is the cost of evaluation any similarity function; learning-based methods spend additional time for training; advanced blocking strategies can reduce the average complexity [Bilenko et al., 2006],[Whang et al., 2009], [Whang and Garcia-Molina, 2012].

Most literature on distributed learning is concerned with limiting communication and designing optimal strategies for merging models [Balcan et al., 2012], [Liu and Ihler, 2014]; beside that, previous works focus on horizontal split by observations, with few exceptions [Liu and Ihler, 2012]. In contrast, we exploit what is sufficient to merge about the data. The communication protocol is extremely simple. Once rados are crafted locally, they are sent to a central learner in one shot. By Theorem 5, only d-dimensional m? basic block rados are needed. Data is not accessed anymore and learning takes place centrally. Moreover, rados help with data compression, being m? ⇥ d, m? ⌧ m the problem size. With ER we learn from all entities, with a total size of m⇥ d.

Learning on data described by different feature sets is the topic of multiple view learning and co-training [Blum and Mitchell, 1998], [Sindhwani et al., 2005]. To the best of our knowledge, co-training with unknown matches has not been addressed before. [Brefeld et al., 2006] presents a multi-view distributed algorithm with co-regularization; although it requires matches for all unlabelled examples.

In settings with multiple data providers, privacy can be crucial. The peers have to trade off model enhancements and information leaks. A learner receives rados to train the model; this can be done by one of the peers, or by a third party - paralleling multi-party ER scenarios [Christen, 2006]. The only information sent through the channel consists of rados, while examples, with their individual sensitive features, are never shared. Hardness results on reconstruct-ability of examples have been proven, along with NP-HARD characterizations, and protection in the sense of differential privacy [Nock et al., 2015]. Regarding ER, since matching has the potential of de-anonimizing the entities, privacy is usually a very relevant issue to address [Christen, 2006]. However, solutions are not straightforward, as proven by the vast amount of research on the topic [Vatsalan et al., 2013].

Even assuming labelled examples, no (observation, label) pair is actually available for training, and thus the task can be seen as weakly supervised [Garcıa-Garcıa and Williamson, 2011], [Patrini et al., 2016a]. Although, a set of aggregate quantities turns out to be enough for the task. Theorem 3 expresses a form of sufficiency of the whole set of rados with regard to the square loss; the analogue property is known for logistic loss in [Nock et al., 2015]. One particular rado, (1◁m) · ⇡, mean operator, is formally proven a sufficient statistics for the class for a wide set of losses [Patrini et al., 2014], [Patrini et al., 2016a]. This work, along with predecessors, shows how the interplay between aggregate statistics and losses can lead to effective solutions to hard learning problems.

7 Conclusion

Entity matching addresses a very general but difficult problem, and in the comparatively restricted context of supervised learning from distributed datasets, it is possible to evade the pitfalls of entity matching with Rademacher observations. Rados have other advantages: they provide a cheap, easily parallelizable material which somehow "compresses" examples while allowing accurate learning. Moreover, they also offer readily available solution for guarantees private exchange of data in a distributed setting.

Acknowledgments

The authors are grateful for the contribution of Hugh DurrantWhyte in many stimulating discussions. NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Center of Excellence Program.