对于两个随机变量 $X$ 和 $Y$, 他们的独立性可以通过他们的联合分布 $P_{XY}$ 和边缘分布 $P_{X}P_{Y}$ 来判断. 但是在实际应用中, 我们往往只有样本, 而没有真实的分布. 这时候我们可以通过样本来估计他们的独立性. 一种常用的方法是 Hilbert-Schmidt independence criterion (HSIC).
Setup
设 $X = \{x_{1}, x_{2}, \ldots, x_{n}\}$ 和 $Y = \{y_{1}, y_{2}, \ldots, y_{n}\}$ 是两个样本集合, 其中 $x_{i} \in \mathcal{X}$, $y_{i} \in \mathcal{Y}$, $i = 1, 2, \ldots, n$. $f: \mathcal{X} \rightarrow \mathbb{R}$ 和 $g: \mathcal{Y} \rightarrow \mathbb{R}$ 是两个函数. 我们希望通过 $f$ 和 $g$ 来判断 $X$ 和 $Y$ 是否独立.
x,y 相互独立, 即 $p(x,y) = p(x)p(y)$ 的充要条件如下:
这个结论显然不难理解。有意思的是，等号右边是采样的形式，也就是说我们将这个指标转化为了采样的形式，避免了直接估算概率密度。
这样一来, 我们就有一个判断独立性的方法: 选取”足够多”的 $f, g$, 然后计算
如果 $L_{H} = 0$, 那么我们就可以认为 $X$ 和 $Y$ 是独立的.
HSIC
进一步推导 $(C[f,g])^2$:
接下来, 我们引入核函数 $k: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$, 我们知道核函数具有以下性质:
- 对称性: $k(x, y) = k(y, x)$;
- 正定性: $\displaystyle \iint k(x, y) f(x) f(y) \mathrm{d}x \mathrm{d}y \geq 0$.
- 核函数的所有特征函数 $\phi_{i}(x)$ 构成 $\mathcal{X}$ 上的一组正交基.
- Mercer 定理: 如果 $k$ 是一个连续核, 则 $k$ 可以表示为: $\displaystyle k(x, y) = \sum_{i=1}^{\infty} \lambda_{i} \phi_{i}(x) \phi_{i}(y)$
我们可以用核函数代替式 $\eqref{eq3}$ 中的 $f$ 和 $g$:
我们的目标是考察 $f$ 和 $g$ 的独立性, 注意到用 $L_{H} = \sum_{i,j} (C[\phi_{i}, \phi_{j}])^2$ 和
来描述独立性是等价的. 于是我们可以用核函数来描述独立性.
将 $\eqref{eq4}$ 展开:
矩阵形式
以线性核 $K_{X}(x_{1}, x_{2}) = x_{1}^{T}x_{2}$ 和 $K_{Y}(y_{1}, y_{2}) = y_{1}^{T}y_{2}$ 为例, $K_{X}$ 和 $K_{Y}$ 为 $n \times n$ 的矩阵.
式 $\eqref{eq5}$ 中第一项可以写成:
同理, 第二项和第三项也可以写成: $\displaystyle \frac{1}{n^{4}} tr (K_{X} \mathbb{1} K_{Y} \mathbb{1})$ 和 $\displaystyle \frac{2}{n^{3}} tr (K_{X} K_{Y} \mathbb{1})$. 故 $L_{H}$ 可以写成:
其中 $H = I - \frac{1}{n} \mathbb{1} \mathbb{1}^{T}$, $\mathbb{1}$ 是中心矩阵, 即
注意到, 式 $\eqref{eq6}$ 是一个有偏估计, 故改写为无偏估计, 即最终的 HSIC 为:
注:
- $X$ 和 $Y$ 独立 $\Leftrightarrow$ $HSIC = 0$.
- HSIC 相当于联合分布 $P_{XY}$ 和边缘分布 $P_{X}P_{Y}$ 之间的最大均值差异.
- 具有特定的核函数, HSIC 相当于距离协方差.