ICA 简明攻略

独立成分分析 Independent Component Analysis

正如任何能在其他地方看到的 ICA 教程一样，我们首先用鸡尾酒会问题来介绍独立成分分析这一概念。

假设在一个鸡尾酒会上，有 个人在说话，同时有 个麦克风在录音。我们记录每个人说话的真实信号为随机变量 ；每个麦克风录下的混合信号为随机变量 。我们假设 和 之间满足某种线性关系：

$$X = AS$$

通过 ICA 算法，我们可以在仅知道可观测信号 (observed signals) 的情况下，恢复出 (source) 的估计值 。换言之，可以在仅有麦克风接收到的混合信号数据的情况下，分离出每个人说话的真实信号的一个估计。

Identifiability

从直觉上讲，想从混合信号 中分离出 的真实值无疑是天方夜谭，因为 和 都是未知的，不同的 在不同的 的作用下可能生成同样的 ，在这种情况下，我们无法区分出哪个 才是真实值。

因此在 ICA 中，我们只能得到一个相对更弱的结论。我们定义 Componentwise Identifiability 如下：

考虑一个源 和生成混合信号的过程 ，以及一个估计值 和其生成过程 。Componentwise Identifiability 即表示，当真实过程和估计过程得到的观测信号分布相同时，则估计的生成过程 至多是真实生成过程 经过一个排列变换 和一个 component-wise 的可逆变换 之后的结果，即：

$$p_{g}(X)=p_{\hat{g}}(X)\quad \Longrightarrow \quad \hat{g}=g \circ \pi \circ T$$

同时我们还能得到如下等价推论：

当 Componentwise Identifiability 成立时，若前件满足，则估计值 至多是真实值 经过一个排列变换和一个 component-wise 的可逆变换之后的结果。

证明如下：

$$\begin{aligned} \hat{S} & = \hat{g}^{-1}(X) \\ & = (\hat{g}^{-1}\circ g)(S) \\ & = (T^{-1} \circ \pi^{-1} \circ g^{-1}\circ g )(S) \\ & = (T^{-1} \circ \pi^{-1})(S) \end{aligned}$$

Linear ICA

定理：对于未知的独立非高斯源信号 和已知混合信号 ，假设他们满足未知线性关系 ，如果存在矩阵 使得

$$X = \hat{A}\hat{S}$$

其中 均可逆， 且 各分量独立，则生成过程是 Componentwise Identifiable 的，且 可以从 通过排列变换 和 component-wise 线性变换 得到。

以下给出证明：

考虑从真实生成过程 中得到的分布 和从估计生成过程 中得的分布 ，由于此时都是从 出发，因此 Componentwise Identifiablilty 前件恒成立，即

$$p_A(X) = p_{\hat{A}}(X)$$

根据等价推论，要证明 identifibility，即要证

$$\hat{S} = (T\circ \pi)(S)$$

其中 和 分别为 component-wise 可逆线性变换和排列变换。

方便起见，我们令 ，即

$$\hat{S} = \hat{A}^{-1}X = \hat{A}^{-1}AS = BS$$

由概率分布变换公式，有

$$P(\hat{S}) = \frac{P(S)}{|B|}$$

取对数，有

$$\log P(\hat{S}) = \log P(S)- \log |B|$$

由于 各分量之间独立，有

$$\sum_{i=1}^d \log P(\hat{s}_i) = \sum_{i=1}^d \log P(s_i) - \log |B|$$

两边同时对任意不同下标的 求偏导

$$\sum_{i=1}^d \frac{\partial^2 \log P(\hat{s}_i)}{\partial \hat{s}_j\partial\hat{s}_k} = \sum_{i=1}^d \frac{\partial^2 \log P(s_i)}{\partial \hat{s}_j\partial\hat{s}_k} - \frac{\partial^2 \log |B|}{\partial \hat{s}_j\partial\hat{s}_k}$$

上式第一项分子没有关于 的交叉项，第三项分子是常数，因此在计算二阶导时均为 0。因此上式改写为

$$\sum_{i=1}^d \frac{\partial^2 \log P(s_i)}{\partial \hat{s}_j\partial\hat{s}_k} = 0$$

使用链式法则展开，有

$$\sum_{i=1}^d \frac{\partial^2 \log P(s_i)}{\partial s_i\partial s_i}\frac{\partial s_i}{\partial \hat{s}_j}\frac{\partial s_i}{\partial \hat{s}_k} + \sum_{i=1}^d \frac{\partial \log P(s_i)}{\partial s_i}\frac{\partial^2 s_i}{\partial \hat{s}_j\partial \hat{s}_k} = 0$$

又因为 ，则 ，即关于 的线性组合，计算二阶导时总为 0。因此上式简化为

$$\sum_{i=1}^d \frac{\partial^2 \log P(s_i)}{\partial s_i\partial s_i}\frac{\partial s_i}{\partial \hat{s}_j}\frac{\partial s_i}{\partial \hat{s}_k} = 0$$

同时，由 ，可得 。方便起见，简记 ，则有

$$\sum_{i=1}^d \phi''(s_i)B^{-1}_{(i,j)}B^{-1}_{(i,k)} = 0$$

当 非高斯时， 为随 变化而变化的函数。由于 独立，各个 都可以独立变化，要使得上式恒成立，则对任意的 总有

$$B^{-1}_{(i,j)}B^{-1}_{(i,k)}=0$$

因此 每行至多有一个非零元素。

又因为 可逆，从而其每行每列有且仅有一个非 0 元素。因此 必定是一个置换矩阵和一个对角矩阵的乘积，其逆矩阵 同样也是一个置换矩阵和一个对角矩阵的乘积。

于是我们得到了

$$\hat{S} = (T\circ \pi)(S)$$

Identifiability 得证。

Nonlinear ICA

定理：对于未知的独立非高斯源信号 和已知混合信号 ，假设他们满足未知非线性关系 ，如果存在函数 使得

$$X = \hat{g}(\hat{S})$$

其中 均可逆， 且 各分量独立。若存在 个域 ，且满足 个差分方程 线性无关，其中

$$w(S,u_p) = \left[ \frac{\partial^2 \log P(s_i|u_p)}{\partial s_i\partial s_i}, \cdots, \frac{\partial^2 \log P(s_i|u_p)}{\partial s_i\partial s_i}, \frac{\partial \log P(s_i|u_p)}{\partial s_i}, \cdots, \frac{\partial \log P(s_i|u_p)}{\partial s_i} \right]$$

则生成过程是 Component-wise Identifiable 的，且 可以从 通过排列变换 和 component-wise 非线性变换 得到。

以下给出证明：

考虑从真实生成过程 中得到的分布 和从估计生成过程 中得的分布 ，由于此时都是从 出发，因此 Componentwise Identifiablilty 前件恒成立，即

$$p_g(X|u) = p_{\hat{g}}(X|u)\quad \forall u$$

根据等价推论，要证明 identifibility，即要证

$$\hat{S} = (T\circ \pi)(S)$$

其中 和 分别为 component-wise 可逆非线性变换和排列变换。

方便起见，我们令 ，即

$$\hat{S} = \hat{g}^{-1}(X) = (\hat{g}^{-1}\circ g)(S) = h(S)$$

由概率分布变换公式，有

$$P(\hat{S}|u) = \frac{P(S|u)}{|J_h|}$$

取对数，有

$$\log P(\hat{S}|u) = \log P(S|u)- \log |J_h|$$

由于 各分量之间独立，有

$$\sum_{i=1}^d \log P(\hat{s}|u) = \sum_{i=1}^d \log P(s_i|u) - \log |J_h|$$

两边同时对任意不同下标的 求偏导

$$\sum_{i=1}^d \frac{\partial^2 \log P(\hat{s}_i|u)}{\partial \hat{s}_j\partial\hat{s}_k} = \sum_{i=1}^d \frac{\partial^2 \log P(s_i|u)}{\partial \hat{s}_j\partial\hat{s}_k} - \frac{\partial^2 \log |J_h|}{\partial \hat{s}_j\partial\hat{s}_k}$$

上式第一项分子没有关于 的交叉项，因此在计算二阶导时均为 0。因此上式改写为

$$\sum_{i=1}^d \frac{\partial^2 \log P(s_i|u)}{\partial \hat{s}_j\partial\hat{s}_k} - \frac{\partial^2 \log |J_h|}{\partial \hat{s}_j\partial\hat{s}_k} = 0$$

使用链式法则展开，有

$$\sum_{i=1}^d \frac{\partial^2 \log P(s_i|u)}{\partial s_i\partial s_i}\frac{\partial s_i}{\partial \hat{s}_j}\frac{\partial s_i}{\partial \hat{s}_k} + \sum_{i=1}^d \frac{\partial \log P(s_i|u)}{\partial s_i}\frac{\partial^2 s_i}{\partial \hat{s}_j\partial \hat{s}_k} - \frac{\partial^2 \log |J_h|}{\partial \hat{s}_j\partial\hat{s}_k} = 0$$

不同于 Linear ICA，在 nonlinear 情形下，Jacobi 行列式 求二阶导并不为 0。因此我们构造

$$w(S,u_p) = \left[ \frac{\partial^2 \log P(s_i|u_p)}{\partial s_i\partial s_i}, \cdots, \frac{\partial^2 \log P(s_i|u_p)}{\partial s_i\partial s_i}, \frac{\partial \log P(s_i|u_p)}{\partial s_i}, \cdots, \frac{\partial \log P(s_i|u_p)}{\partial s_i} \right]$$

对于任意 ，与 进行差分消去 Jacobian 项，得到差分方差组

$$\begin{aligned} &\sum_{i=1}^d \left(\frac{\partial^2 \log P(s_i|u_p)}{\partial s_i\partial s_i}-\frac{\partial^2 \log P(s_i|u_0)}{\partial s_i\partial s_i}\right)\frac{\partial s_i}{\partial \hat{s}_j}\frac{\partial s_i}{\partial \hat{s}_k} \\ +& \sum_{i=1}^d \left(\frac{\partial \log P(s_i|u_p)}{\partial s_i}-\frac{\partial \log P(s_i|u_0)}{\partial s_i}\right)\frac{\partial^2 s_i}{\partial \hat{s}_j\partial \hat{s}_k} \\ =& 0 \end{aligned}$$

于是我们有差分矩阵

$$A = \begin{bmatrix} w(S, u_1) - w(S, u_0) \\ w(S, u_2) - w(S, u_0) \\ \vdots \\ w(S, u_{2d}) - w(S, u_0) \\ \end{bmatrix}$$

及目标向量

$$B = \begin{bmatrix} \frac{\partial s_1}{\partial \hat{s}_j}\frac{\partial s_1}{\partial \hat{s}_k} \\ \vdots \\ \frac{\partial s_d}{\partial \hat{s}_j}\frac{\partial s_d}{\partial \hat{s}_k} \\ \frac{\partial^2 s_1}{\partial \hat{s}_j\partial \hat{s}_k} \\ \vdots \\ \frac{\partial^2 s_d}{\partial \hat{s}_j\partial \hat{s}_k} \end{bmatrix}$$

则差分方程组可以改写为矩阵形式

$$AB = 0$$

当 线性无关时， 可逆。当 非高斯时， 为随 变化而变化的矩阵。由于 独立，各个 都可以独立变化，要使得上式恒成立，要使得上式恒成立，则对任意的 总有

$$\frac{\partial s_i}{\partial \hat{s}_j}\frac{\partial s_i}{\partial \hat{s}_k} = 0$$

因此任意 都只能是最多关于一个 的非线性函数。

又因为 可逆，每个 也得是关于至少一个 的函数，从而可以得到 是一个排列变换和一个 element-wise 非线性变换的组合。

于是我们得到了

$$\hat{S} = (T\circ \pi)(S)$$

Identifiability 得证。

Reference

本文证明主要来自 Partial Identifiability for Domain Adaptation.