Comparing Apples to Oranges:
Learning Similarity Functions for Data Produced by Different Distributions

Let $I$ denote the feature space of elements. We assume that elements come from $\gamma$ known “demographic” groups, where $\gamma \in N$, and each group $\ell \in \left[\gamma \right]$ is governed by an unknown distribution $D_{\ell }$ over $I$. We use $x\sim D_{\ell }$ to denote a randomly drawn $x$ from $D_{\ell }$. Further, we use $x\in D_{\ell }$ to denote that $x$ is an element in the support of $D_{\ell }$, and thus $x$ is a member of group $\ell$. Observe now that for a specific $x\in I$, we might have $x\in D_{\ell }$ and $x\in D_{{\ell }^{\prime }}$, for $\ell \ne {\ell }^{\prime }$. Hence, in our model group membership is important, and every time we are considering an element $x\in I$, we know which distribution produced $x$, i.e., which group $x$ belongs to.

For every group $\ell \in \left[\gamma \right]$ there is an intra-group similarity function $d_{\ell }:I^2\mapsto R_{\ge 0}$, such that for all $x,y\in D_{\ell }$ we have $d_{\ell }(x,y)$ representing the true similarity between $x,y$. In addition, the smaller $d_{\ell }(x,y)$ is, the more similar $x,y$. Note here that the function $d_{\ell }$ is only used to compare members of group $\ell$. Further, a common assumption for functions measuring similarity is that they are metric (Yona and Rothblum, 2018; Kim et al., 2018; Ilvento, 2019; Mukherjee et al., 2020; Wang et al., 2019); a function $d$ is metric if a) $d(x,y)=0$ implies $x=y$, b) $d(x,y)=d(y,x)$ and c) $d(x,y)\le d(x,z)+d(z,y)$ for all $x,y,z$ (triangle inequality). We also adopt the metric assumption for the function $d_{\ell }$. Finally, based on the earlier discussion regarding computing similarity between elements of the same group, we assume that $d_{\ell }$ is known and given as part of the instance.

Moreover, for any two groups $\ell$ and ${\ell }^{\prime }$ there exists an unknown across-groups similarity function ${\sigma }_{\ell ,{\ell }^{\prime }}:I^2\mapsto R_{\ge 0}$, such that for all $x\in D_{\ell }$ and $y\in D_{{\ell }^{\prime }}$, ${\sigma }_{\ell ,{\ell }^{\prime }}(x,y)$ represents the true similarity between $x,y$. Again, the smaller ${\sigma }_{\ell ,{\ell }^{\prime }}(x,y)$ is, the more similar the two elements, and for a meaningful use of ${\sigma }_{\ell ,{\ell }^{\prime }}$ we must make sure that $x$ is a member of group $\ell$ and $y$ a member of group ${\ell }^{\prime }$. Finally, in order to imitate the metric nature of a similarity function, we impose the following properties on ${\sigma }_{\ell ,{\ell }^{\prime }}$, which can be viewed as across-groups triangle inequalities:

1. Property $M_1$: ${\sigma }_{\ell ,{\ell }^{\prime }}(x,y)\le d_{\ell }(x,z)+{\sigma }_{\ell ,{\ell }^{\prime }}(z,y)$ for every $x,z\in D_{\ell }$ and $y\in D_{{\ell }^{\prime }}$.

2. Property $M_2$: ${\sigma }_{\ell ,{\ell }^{\prime }}(x,y)\le {\sigma }_{\ell ,{\ell }^{\prime }}(x,z)+d_{{\ell }^{\prime }}(z,y)$ for every $x\in D_{\ell }$ and $y,z\in D_{{\ell }^{\prime }}$.

Nonetheless, the collection of similarity values here does not axiomatically yield a valid metric space. This is due to the following. 1) If ${\sigma }_{\ell ,{\ell }^{\prime }}(x,y)=0$ for $x\in D_{\ell }$ and $y\in D_{{\ell }^{\prime }}$, then we do not necessarily have $x=y$. 2) It is not always the case that $d_{\ell }(x,y)\le {\sigma }_{\ell ,{\ell }^{\prime }}(x,z)+{\sigma }_{\ell ,{\ell }^{\prime }}(y,z)$ for $x,y\in D_{\ell }$, $z\in D_{{\ell }^{\prime }}$. 3) It is not always the case that ${\sigma }_{\ell ,{\ell }^{\prime }}(x,y)\le {\sigma }_{\ell ,{\ell }^{\prime \prime }}(x,z)+{\sigma }_{{\ell }^{\prime \prime },{\ell }^{\prime }}(z,y)$ for $x\in D_{\ell }$, $y\in D_{{\ell }^{\prime }}$, $z\in D_{{\ell }^{\prime \prime }}$.

However, not having the collection of similarity values necessarily produce a metric space is not a weakness of our model. On the contrary, we view this as one of its strongest aspects. For one thing, imposing a complete metric constraint on the case of intricate across-groups comparisons sounds unrealistic and very restrictive. Further, even though existing literature treats similarity functions as metric ones, the seminal work of Dwork et al. (2012) mentions that this should not always be the case. Hence, our model is more general than the current literature.

Goal of Our Problem: We want for any two groups $\ell ,{\ell }^{\prime }$ to compute a function $f_{\ell ,{\ell }^{\prime }}:I^2\mapsto R_{\ge 0}$, such that $f_{\ell ,{\ell }^{\prime }}(x,y)$ is our estimate of similarity for any $x\in D_{\ell }$ and $y\in D_{{\ell }^{\prime }}$. Specifically, we seek a PAC guarantee, where for any given accuracy and confidence parameters $ϵ,\delta \in (0,1)$ we have:

The subscript in the above probability corresponds to two independent random choices, one $x\sim D_{\ell }$ and one $y\sim D_{{\ell }^{\prime }}$.

As for tools to learn $f_{\ell ,{\ell }^{\prime }}$, we only require two things. At first, for each group $\ell$ we want a set $S_{\ell }$ of i.i.d. samples from $D_{\ell }$. Obviously, the total number of used samples should be polynomial in the input parameters, i.e., polynomial in $\gamma ,\frac{1}{ϵ}$ and $\frac{1}{\delta }$. Secondly, we require access to an expert oracle, which given any $x\in S_{\ell }$ and $y\in S_{{\ell }^{\prime }}$ for any $\ell$ and ${\ell }^{\prime }$, returns the true similarity value ${\sigma }_{\ell ,{\ell }^{\prime }}(x,y)$. We refer to a single invocation of the oracle as a query. Since there is a cost to collecting expert feedback, an additional objective in our problem is minimizing the number of oracle queries.

In Section 2 we present our theoretical results. We begin with a simple learning algorithm achieving the following.

For each group $\ell$, we use $p_{\ell }(ϵ,\delta )$ to denote the probability of sampling an $(ϵ,\delta )$-rare element of $D_{\ell }$. We define as $(ϵ,\delta )$-rare for $D_{\ell }$, an element $x\in D_{\ell }$ for which there is a less than $\delta$ chance of sampling $x^{\prime }\sim D_{\ell }$ with $d_{\ell }(x,x^{\prime })\le ϵ$. Formally, $x\in D_{\ell }$ is $(ϵ,\delta )$-rare iff ${Pr}_{x^{\prime }\sim D_{\ell }}\left[d_{\ell }\right(x,x^{\prime })\le ϵ]<\delta$, and $p_{\ell }(ϵ,\delta )={Pr}_{x\sim D_{\ell }}\left[x\text{is}\right(ϵ,\delta \left)\text{-rare for}{D}_{\ell }\right]$. Intuitively, a rare element should be interpreted as an “isolated” member of the group, in the sense that it is at most $\delta$-likely to encounter another element that is $ϵ$-similar to it.

Clearly, the error probability for $\ell$ and ${\ell }^{\prime }$ is $O\left(\delta \right)$ only when $p_{\ell }(ϵ,\delta ),p_{{\ell }^{\prime }}(ϵ,\delta )=O\left(\delta \right)$. We hypothesize that in realistic distributions each $p_{\ell }(ϵ,\delta )$ should indeed be fairly small, and this hypothesis is actually validated by our experiments. The reason we believe this hypothesis to be true, is that very frequently real data demonstrate high concentration around certain archetypal elements. Hence, this sort of distributional density does not leave room for isolated elements in the rest of the space. Nonetheless, we also provide a strong no free lunch result involving the values $p_{\ell }(ϵ,\delta )$, which shows that any practical algorithm necessarily depends on them. This result further implies that our algorithm’s error probabilities are almost optimal.

Moving on, we focus on minimizing the oracle queries. By carefully modifying the earlier simple algorithm, we obtain a new algorithm with the following guarantees:

Based on Theorem 3, the queries of the improved algorithm are at most $\gamma (\gamma -1)N$, which is exactly the number of queries in our earlier simple algorithm. However, the smaller the values $p_{\ell }(ϵ,\delta )$ are, the fewer queries in expectation. Our experimental results actually confirm that this algorithm always leads to a significant decrease in the used queries.

Our final theoretical result involves a lower bound on the number of queries required for learning.

Combining Theorems 3, 4 implies that when all $p_{\ell }(ϵ,\delta )$ are negligible, i.e., $p_{\ell }(ϵ,\delta )\to 0$, the expected queries of the Theorem 3 algorithm are asymptotically optimal.

Finally, Section 3 contains our experimental evaluation, where through a large suite of simulations on both real and synthetic data we validate our theoretical findings.

Metric learning is a very well-studied area (Bellet et al., 2013; Kulis, 2013; Moutafis et al., 2017; Suárez-Díaz et al., 2018). There is also an extensive amount of work on using human feedback for learning metrics in specific tasks, e.g., image similarity, low-dimensional embeddings (Frome et al., 2007; Jamieson and Nowak, 2011; Tamuz et al., 2011; van der Maaten and Weinberger, 2012; Wilber et al., 2014). However, since these works are either tied to specific applications or specific metrics, they are only distantly related to ours.

Our model is more closely related to the literature on trying to learn the similarity function from the fairness definition of Dwork et al. (2012). This concept of fairness requires treating similar individuals similarly. Thus, it needs access to a function that returns a non-negative value for any pair of individuals, and this value corresponds to how similar the individuals are. Specifically, the smaller the value the more similar the elements that are compared.

Even though the fairness definition of Dwork et al. (2012) is very elegant and intuitive, the main obstacle for adopting it in practice is the inability to easily compute or access the crucial similarity function. To our knowledge, the only papers that attempt to learn this similarity function using expert oracles like us, are Ilvento (2019); Mukherjee et al. (2020) and Wang et al. (2019). Ilvento (2019) addresses the scenario of learning a general metric function, and gives theoretical PAC guarantees. Mukherjee et al. (2020) give theoretical guarantees for learning similarity functions that are only of a specific Mahalanobis form. Wang et al. (2019) simply provide empirical results. The first difference between our model and these papers is that unlike us, they do not consider elements coming from multiple distributions. However, the most important difference is that these works only learn metric functions. In our case the collection of similarity values (from all $d_{\ell }$ and ${\sigma }_{\ell ,{\ell }^{\prime }}$) does not necessarily yield a complete metric space; see the discussion in Section 1.1. Hence, our problem learns more general functions.

Regarding the difficulty in computing similarity between members of different groups, we are only aware of a brief result by Dwork et al. (2012). In particular, given a metric $d$ over the whole feature space, they mention that $d$ can only be trusted for comparisons between elements of the same group, and not for across-groups comparisons. In order to achieve the latter for groups $\ell$ and ${\ell }^{\prime }$, they find a new similarity function $d^{\prime }$ that approximates $d$, while minimizing the Earthmover distance between the distributions $D_{\ell },D_{{\ell }^{\prime }}$. This is completely different from our work, since here we assume the existence of across-groups similarity values, which we eventually want to learn. On the other hand, the approach of Dwork et al. (2012) can be seen as an optimization problem, where the across-groups similarity values need to be computed in a way that minimizes some objective. Also, unlike our model, this optimization approach has a serious limitation, and that is requiring $D_{\ell },D_{{\ell }^{\prime }}$ to be explicitly known.

Finally, since similarity as distance can be quite difficult to compute in practice, there has been a line of research that defines similarity using simpler, yet less expressive structures. Examples include similarity lists Chakrabarti et al. (2022), similarity graphs Lahoti et al. (2019) and ordinal relationships Jung et al. (2019).

Given any confidence and accuracy parameters $\delta ,ϵ\in (0,1)$ respectively, our approach is summarized in the following. At first, for every group $\ell$ we need a set $S_{\ell }$ of samples that are chosen i.i.d. according to $D_{\ell }$, such that $|S_{\ell }|=\frac{1}{\delta }\log \frac{1}{{\delta }^2}$. Then, for every distinct $\ell$ and ${\ell }^{\prime }$, and for all $x\in S_{\ell }$ and $y\in S_{{\ell }^{\prime }}$, we ask the expert oracle for the true similarity value ${\sigma }_{\ell ,{\ell }^{\prime }}(x,y)$. The next observation follows trivially.

Suppose now that we need to compare any $x\in D_{\ell }$ and $y\in D_{{\ell }^{\prime }}$. Our high level idea is that the properties $M_1$ and $M_2$ of ${\sigma }_{\ell ,{\ell }^{\prime }}$ (see Section 1.1), will actually allow us to use the closest element to $x$ in $S_{\ell }$ and the closest element to $y$ in $S_{{\ell }^{\prime }}$ as proxies. Thus, let $\pi \left(x\right)={argmin}_{x^{\prime }\in S_{\ell }}{d}_{\ell }(x,x^{\prime })$ and $\pi \left(y\right)={argmin}_{y^{\prime }\in S_{{\ell }^{\prime }}}{d}_{{\ell }^{\prime }}(y,y^{\prime })$. The algorithm then sets

where ${\sigma }_{\ell ,{\ell }^{\prime }}\left(\pi \right(x),\pi (y\left)\right)$ is known from the earlier queries.

Before we proceed with the analysis of the algorithm, we need to recall some notation which was first introduced in Section 1.2. Consider any group $\ell$. An element $x\in D_{\ell }$ with ${Pr}_{x^{\prime }\sim D_{\ell }}\left[d_{\ell }\right(x,x^{\prime })\le ϵ]<\delta$ is called an $(ϵ,\delta )$-rare element of $D_{\ell }$, and also $p_{\ell }(ϵ,\delta )\text{coloneqq}{Pr}_{x\sim D_{\ell }}\left[x\text{is}\right(ϵ,\delta \left)\text{-rare for}{D}_{\ell }\right]$.

Observation 5 and Theorem 6 directly yield Theorem 1.

A potential criticism of the algorithm presented here, is that its error probabilities depend on $p_{\ell }(ϵ,\delta )$. However, Theorem 2 shows that such a dependence is unavoidable.

Here we modify the earlier algorithm in a way that improves the number of queries used. The high-level idea behind this improvement is the following. Given the sets of samples $S_{\ell }$, instead of asking the oracle for all possible similarity values ${\sigma }_{\ell ,{\ell }^{\prime }}(x,y)$ for every $\ell ,{\ell }^{\prime }$ and every $x\in S_{\ell }$ and $y\in S_{{\ell }^{\prime }}$, we would rather choose a set $R_{\ell }\subseteq S_{\ell }$ of representative elements for each group $\ell$. Then, we would ask the oracle for the values ${\sigma }_{\ell ,{\ell }^{\prime }}(x,y)$ for every $\ell ,{\ell }^{\prime }$, but this time only for every $x\in R_{\ell }$ and $y\in R_{{\ell }^{\prime }}$. The choice of the representatives is inspired by the $k$-center algorithm of Hochbaum and Shmoys (1985). Intuitively, the representatives $R_{\ell }$ of group $\ell$ will serve as similarity proxies for the elements of $S_{\ell }$, such that each $x\in S_{\ell }$ is assigned to a nearby $r_{\ell }\left(x\right)\in R_{\ell }$ via a mapping function $r_{\ell }:S_{\ell }\mapsto R_{\ell }$. Hence, if $d_{\ell }(x,r_{\ell }(x\left)\right)$ is small enough, $x$ and $r_{\ell }\left(x\right)$ are highly similar, and thus $r_{\ell }\left(x\right)$ acts as a good approximation of $x$. The full details for the construction of $R_{\ell }$ and $r_{\ell }$ are presented in Algorithm 1.

Suppose now that we need to compare some $x\in D_{\ell }$ and $y\in D_{{\ell }^{\prime }}$. Our approach will be almost identical to that of Section 2.1. Once again, let $\pi \left(x\right)={argmin}_{x^{\prime }\in S_{\ell }}{d}_{\ell }(x,x^{\prime })$ and $\pi \left(y\right)={argmin}_{y^{\prime }\in S_{{\ell }^{\prime }}}{d}_{{\ell }^{\prime }}(y,y^{\prime })$. However, unlike the simple algorithm of Section 2.1 that directly uses $\pi \left(x\right)$ and $\pi \left(y\right)$, the more intricate algorithm here will rather use their proxies $r_{\ell }\left(\pi \right(x\left)\right)$ and $r_{{\ell }^{\prime }}\left(\pi \right(y\left)\right)$. Our prediction will then be

where ${\sigma }_{\ell ,{\ell }^{\prime }}\left(r_{\ell }\right(\pi \left(x\right)),r_{{\ell }^{\prime }}(\pi \left(y\right)\left)\right)$ is known from the queries.