Optimal Copula Transport for Clustering Multivariate Time Series
Gautier Marti, Frank Nielsen, Philippe Donnat
cs.LG, stat.ML
2015-09-28
Empirical copulas plus EMD measure intra/inter MTS dependence; TDC stays near power 1 on noisy quadratic and step patterns until noise 30-40, while Pearson sits at 0.
The object to cluster is a cube: N series, each with d channels, each observed T times. CDS term structures, EEG, gait sensors on a horse all look like this. Dependence lives at two scales. Intra-dependence is how the d channels of one series move together, and that is enough to separate walk from gallop. Inter-dependence is how the N series move together, and that is the trajectory problem.
Off-the-shelf coefficients are a poor fit. Some are not multivariate. The Randomized Dependence Coefficient (RDC) of Lopez-Paz et al. jumps from sample to sample and can report strong dependence on independent variables. Equitable scores such as MIC try to catch every pattern, so a desk that only cares about co-movement and anti-co-movement has no way to ignore the rest. The Hirschfeld–Gebelein–Rényi maximum correlation hits 1 too often. This 2016 five-page note from Hellebore Capital and École Polytechnique was written for noisy CDS term-structure clustering: a multivariate dependence number that is robust, deterministic, and aimed at a pattern the user names.
Turn each series into an empirical copula, then move mass between copulas with optimal transport.
A copula transform pushes every margin onto Uniform[0,1]; the joint of those uniforms is the dependence. Sklar's theorem says the split is unique when margins are continuous. In practice this is ranking: the empirical copula coordinate of observation t on channel i is its rank divided by T, at cost O(DT log T). A textbook check: if X is uniform on [0,1] and Y = ln(X), Pearson correlation is about 0.84 on the raw pair and 1 after the copula transform. Strictly increasing maps disappear.
The intra-dependence distance bins the two empirical copulas, stores each bin as a (center, mass) signature, and computes Earth Mover's Distance, the discrete Wasserstein-1. A small bin shift only raises the distance a little. A bin-by-bin score such as KL blows up. The bill is an assignment of n Dirac masses, Hungarian in O(n³). Figure 2 shows three real CDS bivariate copulas. All three are diagonal and positive, yet EMD(C1, C2) is smaller than EMD(C1, C3). Correlation is high in every pair; the shapes are not the same.
Between two series the paper defines TDC, the Target Dependencies Coefficient using Transport to Dependence Copulas. Stack X and Y into 2d dimensions, form the empirical copula Ĉ, and place it on the path from the independence copula Cind to a user-chosen set of target copulas {Ci}:
TDC = EMD(Cind, Ĉ) / (EMD(Cind, Ĉ) + mini EMD(Ĉ, Ci))
TDC is 0 at independence, 1 on a named target, and a relative nearness in between. Figure 3 uses perfect dependence and perfect anti-dependence as targets. Positively correlated Gaussians land closer to the upper-right diagonal. A side product: which target lit up.
The only quantitative experiment is Figure 4. It reuses R code from Simon and Tibshirani and from the RDC paper, and scans noise levels 0 to 100 on linear, quadratic, wedge, circular, step, and bimodal "function plus noise" patterns. The y-axis is power: how often the estimator separates a dependent sample from an independent one. Baselines are Pearson, distance correlation, MIC, ACE, and RDC.
On the linear panel every method starts near 1; TDC decays slowest. On quadratic, circular, and step patterns, where Pearson correlation is near 0, the open circles sit on the floor while TDC (dark-blue crosses) stays near 1 until noise around 30 to 40. On the step panel TDC is almost flat at the top across the whole noise range, and Pearson is flat at the bottom. The paper says TDC "achieves the best results on the benchmark datasets" and, in the same paragraph, that the experiment is biased in its favor: the target copulas already contain the pattern being sought. The other coefficients do not get that hint.
There is no clustering-accuracy table on the intra side. Figure 2 shows that EMD can tell apart copulas with similar correlation and different shape. It does not report the two distances, and it does not report ARI or NMI.
For term structures, EEG, or multi-sensor motion, this is a distance that asks "which dependence do you care about?" before it clusters. Empirical copulas strip the margins. EMD is less brittle to histogram misalignment than KL. TDC also says whether the active target is co-movement or anti-co-movement. By 2016 the paper already points at Cuturi's Sinkhorn distance as a faster EMD.
It is not a production clustering stack. The five pages define the distances. The CDS clustering case is deferred to a company tech post and is not in the paper.
The authors flag two scaling issues. Nonparametric density estimates hit the curse of dimensionality. Hungarian EMD is O(n³), and the bin count of a high-d histogram grows fast. They leave parametric copulas and optimal transport on statistical manifolds as later work.
The larger problem is the experiment. TDC's selling point is that the user names the target. Scoring a coefficient that already knows the answer against MIC and RDC, which do not, is a constructed win. Figure 4 does not report sample size, number of repeats, or significance. The promised application is clustering noisy CDS term structures; the reader gets three qualitative copula plots and no stability, no cluster count, no comparison to a Pearson-matrix clustering. RDC is called unstable. TDC's own finite-sample variance is not measured.