Measuring Statistical Dependence with Hilbert-Schmidt Norms

Authors: Arthur Gretton, Olivier Bousquet, Alex Smola, Bernhard Schölkopf
Published: 2005
Venue: ALT
Link: Springer

Summary

This foundational paper introduces the Hilbert-Schmidt Independence Criterion (HSIC), a kernel-based measure of statistical dependence. HSIC measures the distance between the joint distribution and the product of marginals in a reproducing kernel Hilbert space.

Key Contributions

1. HSIC Definition

The Hilbert-Schmidt Independence Criterion between random variables $X$ and $Y$: $\text{HSIC}(P_{XY}, \mathcal{F}, \mathcal{G}) = \|\mathcal{C}_{XY}\|_{HS}^2$

where $\mathcal{C}_{XY}$ is the cross-covariance operator in RKHS.

2. Cross-Covariance Operator

For RKHS $\mathcal{F}$ with kernel $K$ and $\mathcal{G}$ with kernel $L$: $\mathcal{C}_{XY} = \mathbb{E}_{XY}[\phi(X) \otimes \psi(Y)] - \mathbb{E}_X[\phi(X)] \otimes \mathbb{E}_Y[\psi(Y)]$

where $\phi$ and $\psi$ are feature maps.

3. Equivalent Formulation

HSIC can be written in terms of kernels: $\text{HSIC} = \mathbb{E}[K(X,X')L(Y,Y')] + \mathbb{E}[K(X,X')]\mathbb{E}[L(Y,Y')] - 2\mathbb{E}[K(X,X')L(Y,Y'')]$

where $(X,Y), (X',Y'), (X'',Y'')$ are independent copies.

4. Independence Characterization

Theorem: If kernels $K$ and $L$ are characteristic: $\text{HSIC}(P_{XY}) = 0 \iff X \perp\!\!\!\perp Y$

Mathematical Framework

Tensor Product Space

Consider the tensor product RKHS $\mathcal{F} \otimes \mathcal{G}$ with kernel: $K \otimes L((x,y), (x',y')) = K(x,x') L(y,y')$

Mean Embedding

The joint embedding: $\mu_{XY} = \mathbb{E}[\phi(X) \otimes \psi(Y)]$

The product of marginal embeddings: $\mu_X \otimes \mu_Y = \mathbb{E}[\phi(X)] \otimes \mathbb{E}[\psi(Y)]$

HSIC as Distance

$\text{HSIC} = \|\mu_{XY} - \mu_X \otimes \mu_Y\|_{\mathcal{F} \otimes \mathcal{G}}^2$

Empirical Estimation

Biased Estimator

Given samples $\{(x_i, y_i)\}_{i=1}^n$: $\widehat{\text{HSIC}}_b = \frac{1}{n^2}\text{Tr}(KHLH)$

where $H = I - \frac{1}{n}\mathbf{1}\mathbf{1}^T$ is the centering matrix.

Unbiased Estimator

$\widehat{\text{HSIC}}_u = \frac{1}{n(n-3)}\left[\text{Tr}(\tilde{K}\tilde{L}) + \frac{\mathbf{1}^T\tilde{K}\mathbf{1}\cdot\mathbf{1}^T\tilde{L}\mathbf{1}}{(n-1)(n-2)} - \frac{2}{n-2}\mathbf{1}^T\tilde{K}\tilde{L}\mathbf{1}\right]$

where $\tilde{K}$ and $\tilde{L}$ have zero diagonal.

Algorithm

import numpy as np

def hsic_biased(K, L):
    """
    Compute biased HSIC estimator.
    
    Parameters:
    -----------
    K : kernel matrix for X (n, n)
    L : kernel matrix for Y (n, n)
    
    Returns:
    --------
    hsic : HSIC value
    """
    n = K.shape[0]
    H = np.eye(n) - np.ones((n, n)) / n
    return np.trace(K @ H @ L @ H) / n**2

def hsic_unbiased(K, L):
    """
    Compute unbiased HSIC estimator.
    """
    n = K.shape[0]
    
    # Zero out diagonals
    K_tilde = K - np.diag(np.diag(K))
    L_tilde = L - np.diag(np.diag(L))
    
    # Compute terms
    term1 = np.trace(K_tilde @ L_tilde)
    term2 = K_tilde.sum() * L_tilde.sum() / ((n-1) * (n-2))
    term3 = 2 * (K_tilde @ L_tilde).sum() / (n-2)
    
    return (term1 + term2 - term3) / (n * (n-3))

def hsic_independence_test(X, Y, kernel_x, kernel_y, n_permutations=1000, alpha=0.05):
    """
    Permutation test for independence using HSIC.
    """
    K = kernel_x(X, X)
    L = kernel_y(Y, Y)
    
    # Observed HSIC
    observed = hsic_unbiased(K, L)
    
    # Permutation null distribution
    null_values = []
    for _ in range(n_permutations):
        perm = np.random.permutation(len(Y))
        L_perm = L[np.ix_(perm, perm)]
        null_values.append(hsic_unbiased(K, L_perm))
    
    # p-value
    p_value = np.mean(np.array(null_values) >= observed)
    
    return {
        'statistic': observed,
        'p_value': p_value,
        'reject': p_value < alpha
    }

Statistical Properties

Asymptotic Distribution

Under $H_0: X \perp\!\!\!\perp Y$: $n \cdot \widehat{\text{HSIC}} \xrightarrow{d} \sum_{i=1}^\infty \lambda_i z_i^2$

where $z_i \sim \mathcal{N}(0,1)$ and $\lambda_i$ are eigenvalues.

Consistency

Under $H_1: X \not\perp\!\!\!\perp Y$: $\widehat{\text{HSIC}} \xrightarrow{p} \text{HSIC}(P_{XY}) > 0$

Convergence Rate

$|\widehat{\text{HSIC}} - \text{HSIC}| = O_p(n^{-1/2})$

Applications

1. Feature Selection: Select features with high HSIC to target
2. Independence Testing: Non-parametric test for dependence
3. Kernel Selection: Choose kernel that maximizes HSIC
4. ICA: Independent component analysis via HSIC minimization
5. Causal Discovery: Test conditional independence

Comparison with Other Measures

Measure	Nonlinear	Distribution-free	Consistent
Pearson $r$	✗	✗	✗
Spearman $\rho$	Monotonic	✓	✗
Mutual Info	✓	✗	✓
HSIC	✓	✓	✓

Citation

@inproceedings{gretton2005measuring,
  title={Measuring statistical dependence with Hilbert-Schmidt norms},
  author={Gretton, Arthur and Bousquet, Olivier and Smola, Alex and 
          Sch{\"o}lkopf, Bernhard},
  booktitle={Algorithmic Learning Theory},
  pages={63--77},
  year={2005}
}

Further Reading

• Gretton, A., et al. (2012). A kernel two-sample test
• Fukumizu, K., et al. (2007). Kernel measures of conditional dependence
• Zhang, K., et al. (2011). Kernel-based conditional independence test