Fast Learning from Distributed Datasets without Entity Matching

By Giorgio Patrini, Richard Nock, Stephen Hardy, Tibério S. Caetano. 2016

12 citations recorded by the source corpus.

Consider the following data fusion scenario: two datasets/peers contain the same real-world entities described using partially shared features, e.g. banking and insurance company records of the same customer base. Our goal is to learn a classifier in the cross product space of the two domains, in the hard case in which no shared ID is available -- e.g. due to anonymization. Traditionally, the problem is approached by first addressing entity matching and subsequently learning the classifier in a standard manner. We present an end-to-end solution which bypasses matching entities, based on the recently introduced concept of Rademacher observations (rados). Informally, we replace the minimisation of a loss over examples, which requires to solve entity resolution, by the equivalent minimisation of a (different) loss over rados. Among others, key properties we show are (i) a potentially huge subset of these rados does not require to perform entity matching, and (ii) the algorithm that provably minimizes the rado loss over these rados has time and space complexities smaller than the algorithm minimizing the equivalent example loss. Last, we relax a key assumption of the model, that the data is vertically partitioned among peers --- in this case, we would not even know the existence of a solution to entity resolution. In this more general setting, experiments validate the possibility of significantly beating even the optimal peer in hindsight.

Subfields: Computer Networks and Communications, Information Systems, Management Science and Operations Research, Federated & Distributed Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Information Systems

In Management Science and Operations Research

In Federated & Distributed Learning

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “Loss factorization tricks can be used in supervised learning to alleviate up to the vertical partition assumption itself, but the practical benefits depend on the distribution of data and the number of parties [320].”
Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption (2017, background): “…statistics for the class instead of examples [Nock et al., 2015, Nock, 2016, Patrini, 2016], many of which do not require entity resolution to be computed, but rather a weak form of entity resolution between groups of observations that share common subset of features [Patrini et al., 2016b].”
Entity Resolution and Federated Learning get a Federated Resolution (2018, background): “This is crucial because this pipeline is pivotal to federated learning: to our knowledge, there is only one exception to this pipeline [22].”
On Regularizing Rademacher Observation Losses (2016, background): “(10)”