Metrics and other distance functions

qif.metric

A metric is represented as a function d(a, b) returning a number; any Python function can be used. The functions of this module construct common metrics, and combine existing ones into new ones. Metrics can be defined on secrets (indices \(0,\ldots,n{-}1\)), on numbers, on qif.point, or on distributions. Some of the constructed functions are not strictly metrics (for instance they are not symmetric), but are still useful as distances.

Functions

euclidean(type: TypeLike = def_type) → Metric[Any, Any]

The Euclidean metric \(|a - b|\) on numbers (double, rat) or secrets (uint), or the Euclidean distance between two points (point), depending on type.

euclidean_chain(type: TypeLike = def_type) → Callable[[Any, Any], bool]

The “chainable” predicate of euclidean() for the given type: chain(a, b) is true if there is a chain \(a = e_1, \ldots, e_k = b\) of intermediate elements with \(d(a,b) = \sum_i d(e_i, e_{i+1})\). For secrets (uint) this holds for all \(a, b\) with \(|a - b| \neq 1\); for other types it is always false. Used by qif.mechanism.d_privacy.min_loss_given_d() to skip redundant constraints.

discrete(type: TypeLike = def_type) → Metric[Any, Any]

The discrete metric: \(0\) if \(a = b\), \(1\) otherwise.

mult_reals(type: TypeLike = def_type) → Metric[float, float]

The metric \(|\ln a - \ln b|\) on positive numbers.

scale(d: Metric[T, R], coeff: R) → Metric[T, R]

The metric \(\mathrm{coeff} \cdot d\). Distances equal to \(0\) stay \(0\) even when coeff is infinite.

min(d1: Metric[T, R], d2: Metric[T, R]) → Metric[T, R]

The pointwise minimum \(\min(d_1(a,b), d_2(a,b))\) (not necessarily a metric).

max(d1: Metric[T, R], d2: Metric[T, R]) → Metric[T, R]

The pointwise maximum \(\max(d_1(a,b), d_2(a,b))\).

mirror(d: Metric[T, R]) → Metric[T, R]

The distance \(d(b,a)\), with the arguments swapped (useful for non-symmetric distances).

threshold(d: Metric[T, R], thres: R) → Metric[T, R]

The distance \(\min(d(a,b), \mathrm{thres})\).

threshold_inf(d: Metric[T, R], thres: R) → Metric[T, R]

The distance \(d(a,b)\) if it is at most thres, infinity otherwise.

from_distance_matrix(M: ndarray) → Metric[int, float]

The distance on secrets given by a matrix: \(d(i,j) = M_{i,j}\).

to_distance_matrix(d: Metric[int, R], n_rows: int, n_cols: int = 0) → ndarray

The n_rows \(\times\) n_cols matrix \(M_{i,j} = d(i,j)\) of a distance on secrets (n_cols = 0 means n_cols = n_rows). Applied to a gain function \(g(w,x)\), it gives the gain matrix.

l1() → Metric[ndarray, float]

The \(\ell_1\) metric \(\sum_i |a_i - b_i|\) on vectors.

l2() → Metric[ndarray, float]

The Euclidean (\(\ell_2\)) metric \(\sqrt{\sum_i (a_i - b_i)^2}\) on vectors.

total_variation() → Metric[ndarray, float]

The total variation distance \(\frac12 \sum_x |a_x - b_x|\) between distributions, equal to the largest difference \(|a(Z) - b(Z)|\) in the probability of an event \(Z\).

mult_total_variation() → Metric[ndarray, float]

The multiplicative distance \(\max_x |\ln a_x - \ln b_x|\) between distributions (infinity if their supports differ), equal to the largest \(|\ln (a(Z)/b(Z))|\) for an event \(Z\). A channel \(C\) satisfies \(d\)-privacy iff the multiplicative distance between rows \(C_{x,-}, C_{x',-}\) is at most \(d(x,x')\) (see d-privacy).

convex_separation_quasi() → Metric[ndarray, float]

The quasiconvex separation \(q(a,b) = \max_{x \in \lceil a\rceil} (1 - b_x / a_x)\), where \(\lceil a\rceil\) is the support of \(a\) (a non-symmetric distance). The additive capacity for a fixed prior \(\pi\) over one-bounded gain functions is the expected value of \(q(\sigma, \pi)\) over the posteriors \(\sigma\) of \([\pi\triangleright C]\) (see qif.measure.g_vuln.add_capacity()).

convex_separation() → Metric[ndarray, float]

The symmetric version \(\max(q(a,b), q(b,a))\) of convex_separation_quasi().

kantorovich(d: Metric[int, float]) → Metric[ndarray, float]

The Kantorovich lifting of a metric d on secrets to a metric on distributions: the minimum cost of transforming \(a\) into \(b\) by moving probability mass, where moving a unit of mass from \(i\) to \(j\) costs \(d(i,j)\). Equivalently, the maximum of \(|\sum_x a_x f(x) - \sum_x b_x f(x)|\) over all functions \(f\) with \(|f(x) - f(x')| \le d(x,x')\). Computed with the FastEMD algorithm for double (which requires d to be a metric), and by linear programming otherwise.

mult_kantorovich(d: Metric[int, float]) → Metric[ndarray, float]

The multiplicative variant of the Kantorovich lifting [CGPX14]: the maximum of \(|\ln \sum_x a_x f(x) - \ln \sum_x b_x f(x)|\) over all functions \(f\) with values in \([0,1]\) and \(|\ln f(x) - \ln f(x')| \le d(x,x')\). Computed by linear programming (via the dual form).

References

[CGPX14]

K. Chatzikokolakis, D. Gebler, C. Palamidessi, L. Xu. Generalized bisimulation metrics. CONCUR 2014.