【机器学习】On the Identifiability of Nonlinear ICA： Sparsity and Beyond

前言

这篇综述概述了该研究论文中两个关键的稀疏性假设的具体内容，并详细阐述了这两个假设对非线性ICA模型识别能力的影响。具体信息可参考Reference部分。

什么是ICA(Independent component analysis)？

independent component analysis, colloquially referred to asICA, is a computational technique for separating a multivariate signal into additive components that are statistically independent from each other. It can be used to model a mixture of many samples X, where each sample can be represented as a combination of underlying sources S that are non-Gaussian and mutually independent.

关于ICA的深入解析, 建议访问Yifan Shen的博客: ICA简明攻略.

非线性独立成分分析

非线性独立成分分析（ICA）的目标在于基于观测数据恢复潜在的独立源信息。作为一种无监督学习的核心技术，在缺乏任何额外假设的情况下无法唯一确定这些潜在源信息。它通过建立观测向量x与潜在源s之间的可逆非线性关系f来进行建模，在这种关系下观测数据被表示为x = f(s)。然而由于问题本身的复杂性，在没有进一步约束或先验知识的情况下存在无限多种可能的分解方式。即使分离出的结果看似清晰但仍然无法完全还原原始的源信号。

现有的研究采用了辅助变量u（如类别标签、领域索引及时间戳等），并在给定u的情况下假设源数据满足条件独立性这一假设。如需进一步了解相关内容，请参考Hyvärinen教授的演讲视频：Hyvärinen的talk。

条件独立

P(A, B|C) = P(A|C) \cdot P(B|C)
一个很好的例子：
C指赖床，A指熬夜，B指迟到，P(A, B|C) = P(A|C) \cdot P(B|C)，赖床的发生使得熬夜想通过赖床来影响迟到的可能为零，即没有别的可能来影响迟到了，所以此时熬夜和迟到就是条件独立了。

结构稀疏(Structural Sparsity)假设

Theorem 1. Let the observed data be drawn from a nonlinear ICA model according to Eqs. (1) and (2). Suppose the subsequent conditions are satisfied.

i. Mixing function f is invertible and smooth. Its inverse is also smooth.

ii. For every integer i ranging from 1 to n and every element j in the set F_i,: there exists a collection {s^(ℓ)} indexed by ℓ from 1 to the cardinality of F_i,:) and a transformation T such that the span of the matrix J_f evaluated at s^(ℓ) for each ℓ forms the entire vector space R^n restricted to F_i,: and the transpose of J_f(s^(ℓ)) at position j,:) belongs to R^n restricted to the transformed set hat F_i,:.

iii. |\hat{\mathcal{F}}| \leq |\mathcal{F}|.

iv. (Structural Sparsity) For all k \in \{1, \ldots, n\}, there exists C_k such that

\bigcap_{i \in C_k} \mathcal{F}_{i, :} = \{k\}.

Then h := \hat{f}^{-1} \circ f is a composition of a component-wise invertible transformation and a permutation.

符号含义

1. {J_f(s)}即表示为对源矩阵求偏导的结果。
2. 在非线性ICA求解后得到的矩阵求偏导的过程中, 该雅可比矩阵\hat{J}_{f}(\hat{s})所对应的雅各比行列式具有特定性质。
3. 支撑集\mathcal{F}由雅各比矩阵{J_f(s)}中所有非零元素的位置组成。
4. 支撑集\hat{\mathcal{F}}则由对应雅可比矩阵中的非零元素位置构成。
5. 对某一行的所有非零元素索引进行选择。
6. s^{(l)}表示的是第l个源。
7. C_k

理论拆解：

1. 通过观测样本X推导出源S的过程属于一种逆运算。当函数f具有可逆性和光滑性时，则可以执行该运算并进行微分。
2. 源S的所有可能组合构成了一个充分大的实数空间。这一设定旨在避免ill-posed问题的发生。例如，在雅可比矩阵中的某个部分始终满足后续假设条件时，尽管这些条件成立但依然无法找到唯一解。
3. 预测得到的雅可比矩阵支持集的大小不超过真实雅可比矩阵支持集的大小。
4. 针对某一列C_k中的每个行i来说，在支持集合\mathcal{F}中提取所有行坐标为i的位置，并依次提取所有行的支持集，在列方向上求交集即可确保至少存在一列满足特定条件：该列包含目标索引k，并且其对应的支持集不仅与该列相交还保持唯一性。
   这样就能确保至少存在一列满足特定条件：该列包含目标索引k，并且其对应的支持集不仅与该列相交还保持唯一性。

证明

问题简化

该方法旨在通过引入置换映射h_map := \hat{f}^{-1} \circ f实现源域s上的逐元素可逆变换。等价地说：\hat{f} = f \circ h_map^{-1}(s)成立。假设D(s)表示一个对角矩阵，并且P表示一个排列变换矩阵。基于链式法则分析可知：

\begin{aligned} K^{\hat{s}}(\hat{s}) &= (n ∘ m^{−2})(mσ) \\ &= (n ∘ m^{−2})(Mσ) \\ &= (n ∘ m^{−2})(mσ) ⋅ Mσ \\ &= n(m(mσ)) ⋅ D(mσ) ⋅ M σ \\ &= n(g(mσ)) ⋅ D(m σ) ⋅ M σ \\ &= n(g(m σ)) ⋅ D(m σ) ⋅ M σ \end{aligned}

其中，g是一个元素可逆函数（可逆的逐元素函数）。

我们也期望通过实验数据来验证这一假设是否正确。为了进一步分析问题的本质特征，在此我们主要关注的是系统响应的最大幅值所对应的输入信号类型之间的关系。基于此设想，在后续分析中我们将集中精力探讨以下关键问题：即如何确定系统输出的最大幅值及其对应的时间点。

找源雅可比矩阵，预测雅可比矩阵，变换矩阵T之间的关系

定义 \mathcal{F} 为 J_f(s) 的支撑集，并定义 \hat{\mathcal{F}} 为 J_{\hat{f}}(\hat{s}) 的支撑集。令 \tau = \text{supp}(T(s)), 并令矩阵 T \in \mathbb{R}^{n \times n} 满足其非零元素位于其对角线上或与其附近的位置。由假设 ii 可知：

\text{span}\{J_f(s^{(\ell)})_i\}_{\ell=1}^{|\mathcal{F}_{i, ：}|} = \mathbb{R}^n_{\mathcal{F}_{i, ：}} \tag{4}

由于 \{J_f(s^{(\ell)})_i\}_{\ell=1}^{|\mathcal{F}_{i, ：}|} 形成了 \mathbb{R}^n_{\mathcal{F}_{i, ：}} 的一组基，对于任意 j_0 \in \mathcal{F}_{i, ：}，我们可以将热独向量 e_{j_0} \in \mathbb{R}^n_{\mathcal{F}_{i, ：}} 重写为：

e_{j_0} = \sum_{\ell \in \mathcal{F}_{i, ：}} \alpha_{\ell} J_f(s^{(\ell)})_{i, :}, \tag{5}

其中 \alpha_{\ell} 是对应的系数。则有：

对于任意给定的 j₀ 和 i，在实数域 ℝ^n 上定义线性变换 L_T 为 L_T(T) = E_j₀T = ∑{ℓ ∈ 𝔽_i,:} α_ℓ J_f(s^{(ℓ)}){i,:} · T ∈ ℝ^n 的行空间 𝔽̂_{i,:}, 其中 E_j₀ 表示第 j₀ 个标准基向量。

公式（6）中的"∈"符号源于假设ii，并明确指出（6）求和中的每一个元素都归于 \mathbb{R}^n_{\hat{\mathcal{F}}_{i,:}}这一空间。

\forall j \in \mathcal{F}_{i, ：}, \quad T_{j, ：} \in \mathbb{R}^n_{\hat{\mathcal{F}}_{i, ：}} \tag{7}

到这一步我们推出了T_{j, :} 是属于预测矩阵的支撑集的。

然后我们可以在支撑集之间建立如下关系：

\forall (i, j) \in \mathcal{F}, \{i\} \times \tau_{j, :} \subseteq \hat{\mathcal{F}}. \tag{8}

需要注意的是，在这里\times代表的是 combinations 。意思是横坐标{i}与\tau_{j, :}所代表的纵坐标结合起来。

基于假设 i, 矩阵 T(s) 成为一个可逆矩阵, 即表明其行列式的值为非零. 将该矩阵 T(s) 的行列式以 Leibniz 公式的形式展开.

\text{det}(T(s)) = \sum_{\sigma \in S_n} \{\text{sgn}(\sigma) \prod_{i=1}^n T(s)_{i,\sigma(i)}\} \neq 0. \tag{9}

其中 S_n 是 n排列的集合。

由于（9）不为0， 则存在至少一个求和元素是非零的，表示为：

该排列σ属于对称群Sn满足以下条件：对于所有i∈{1,…,n}有sgn(σ)⋅∏{i=1}^n T(s){i,σ(i)}≠0。（10）

（10）等价于：

\exists \sigma \in S_n, \forall i \in \{1, \ldots, n\}, T(s)_{i,\sigma(i)} \neq 0. \tag{11}

由此我们可以得到 \sigma(·) 在 T(s) 的支持集中，进而有：

\forall j \in \{1, \ldots, n\}, \sigma(j) \in T_{j, ：} \tag{12}

结合 (8)，可以得到：

\forall (i, j) \in \mathcal{F}, (i, \sigma(j)) \in \{i\} \times T_{j, :} \subseteq \hat{\mathcal{F}}. \tag{13}

表示

\sigma(\mathcal{F}) = \{(i, \sigma(j)) | (i, j) \in \mathcal{F}\}. \tag{14}

以上我们得到了\mathcal{F}, \hat{\mathcal{F}}, T 之间的变换关系。

反证法证明T(s) = D(s)P成立

假设 T(s) \neq D(s)P，那么：

\exists j_1 \neq j_2, \tau_{j_1, :} \cap \tau_{j_2, :} \neq \varnothing. \tag{15}

此外，考虑 j_3 \in \{1, \ldots, n\} 使得：

\sigma(j_3) \in \tau_{j_1, :} \cap \tau_{j_2, :}. \tag{16}

由于 j_{\text{A}} \neq j_{\text{B}} ，我们能够合理推断出 j_{\text{C}} \neq j_{\text{A}} 而无需牺牲普遍性（在矩阵规模较大的情况下，在这种情况下出现的概率极其微小——仅为 \frac{1}{n} ）。

根据假设 iv, 存在 j_1 \in C_{j_1} 使得：

\bigcap_{i \in C_{j_1}} \mathcal{F}_{i, :} = \{j_1\}. \tag{17}

由于：

j_3 \not\in \{j_1\} = \bigcap_{i \in C_{j_1}} \mathcal{F}_{i, :}, \tag{18}

那么一定存在 i_3 \in C_{j_1} 使得：

j_3 \not\in \mathcal{F}_{i_3, :} \tag{19}

因为 j_1 \in \mathcal{F}_{i_3, :}，我们有 (i_3, j_1) \in \mathcal{F}。然后根据公式 (8)，可以得到：

\{i_3\} \times \tau_{j_1, :} \subseteq \hat{\mathcal{F}}. \tag{20}

由\sigma(j_3) \in \tau_{j_1, ：} \cap \tau_{j_2, ：} 可以得到：

(i_3, \sigma(j_3)) \in \{i_3\} \times \tau_{j_1, ：}. \tag{21}

通过公式(20) 和 (21)，我们可以得到：

(i_3, \sigma(j_3)) \in \hat{\mathcal{F}}, \tag{22}

结合公式 (14) 可知 (i_3, j_3) \in \mathcal{F}，与等式 (19) 矛盾。

则可知假设T(s) \neq D(s)P不成立。

则T(s) = D(s)P，得证。

不完备情况下的结构稀疏假设

不完备指观测样本的数量远大于源的数量

Assume that the observed data are sampled from a linear ICA model as defined by Equations (1) and (3), which incorporates Gaussian sources. Notably, in this scenario, the number of observed variables (denoted as m) may exceed that of the underlying sources (n), i.e., m \geq n. Under these circumstances, several assumptions must hold.

The non-vanishing elements of the mixing matrix \mathbf{A} are subject to random selection from a distribution that exhibits absolute continuity concerning the Lebesgue measure.

ii. The estimated mixing matrix \hat{A} achieves the minimal L_0 norm in the estimation process.

iii. (Structural Sparsity) Let C be a subset of \{1,2,\ldots,n\} with cardinality greater than 1. Denote by A_C the submatrix of size m \times |C| extracted from matrix A by selecting the columns indexed by elements in set C. Specifically, for each element k in set C, the following condition applies:

该式表明集合\bigcup_{k' \in C}\text{supp}(A_{k'})与\text{overlap}(A_C)之间的差值大于\text{supp}(A_k)的大小。

Then \hat{A} = ADP with probability one, where D is a diagonal matrix and P is a column permutation matrix.

理论拆解：

1. 确保混合矩阵具有足够的复杂性，并非单一特定结构。
2. L0范数表明矩阵中非零元素的数量。
3. 支持集的并集中元素的数量减去行重叠子矩阵秩的结果大于每一列支持集大小之和。为了实现这一目标：每个来源对观测的影响应尽可能地小，并且相互作用应尽可能弱。图中所示例子：当k=1时且C={1,2,3}时的情况。其中A_C表示图示子矩阵，则|∪{k'∈C} supp(A{k'})|=7个元素；overlap(A_C)由蓝色虚线框定；overlap(A_C)秩为2；因此|∪{k'∈C} supp(A{k'})| - rank(overlap(A_C)) =5（黑点数量），这比|supp(A₁)|=4大。

证明

根据假设（ii），我们考虑以下组合优化问题：

\hat{U} := \arg \min_{U \in \mathbb{R}^{s \times s}, UU^T=I_s} \|AU\|_0,\tag{1}

其中 A 代表真实数据来源生成的真实混合矩阵。
\hat{U} 表示对应于优化问题解的旋转矩阵。
被定义为 \hat{A} = A\hat{U}。

用反证法，假设 \hat{A} \neq ADP，那么 \hat{U} \neq DP。
这意味着存在某个 j' \in \{1, \ldots, s\} 和它对应的行索引集合 \mathcal{I}_{j'} （|\mathcal{I}_{j'}| > 1），使得 \hat{U}_{i,j'} \neq 0 对所有 i \in \mathcal{I}_{j'}成立，并且 \hat{U}_{i,j'} = 0 对所有 i \notin \mathcal{I}_{j'}成立。
由于 \hat{U} 是可逆的并且具有完整的行秩，为了避免列之间的线性依赖，存在唯一对应于 j' 的行索引 i'。设：

\hat{U} := \begin{bmatrix} \hat{U}_1 & \ldots & \hat{U}_s \end{bmatrix},

我们可以得到：

\|\hat{A}_{j'}\|_0 = \|A\hat{U}_{j'}\|_0 = \left\| \sum_{i \in \mathcal{I}_{j'}} A_{i} \hat{U}_{i,j'} \right\|_0. \tag{2}

这里的 \|\cdot\|_0 表示 L_0 范数，即矩阵中非零元素的数量。

定义为：设由矩阵的列索引所组成的子矩阵记为I_j = A[\mathcal{I}_j, :]^T = [a^{(k)}_i]_{k=1}^{n_j}；值得注意的是，在这里每一列都是独立于其他列的信息载体，并且能够唯一地代表原始数据中的特定特征信息；基于假设（ii）和（iii）可知，在这种情况下我们的模型能够通过以下关系式来进行推导：

U_i,j' = \sum_{k=1}^{n_j} a^{(k)}_i v^{(k)}_j

其中满足条件的是因为集合I'_{j'}|大于1，并且对应的元素不等于零。

The norm of the sum \sum_{i \in I_j'} A_i U^{\wedge}_{i,j'} is greater than or equal to the cardinality of the union over I_j' of supports for each A_i, minus the rank of their overlapping, which in turn exceeds that of a single term's support, as shown in Equation (3).

其中一项\text{rank}(\text{overlap}(A_{\mathcal{I}_{j'}}))表示为能够通过该矩阵线性组合消除的最大行数。假设i排除了违反该公式的可能性。从而可以保证：例如，在 A 的两列具有相同的值和support。

其值大于支撑集模长等于 A_{i'} 的零范数等于 A_{i'} 与 \hat{U}_{i',j'} 乘积的零范数。\tag{4}

然后我们可以构造 \tilde{U} := \begin{bmatrix} \tilde{U}_1 & \ldots & \tilde{U}_s \end{bmatrix}。
首先，我们将 \tilde{U}_{i,j'} 设置为列 \tilde{U}_{j'} 中的唯一非零项。为了简便起见，我们可以将 \tilde{U}_{i,j'} 设为 1。对于其他 j \neq j' 并且 \hat{U}_{i,j} \neq 0的列 \tilde{U}_{j}，我们设 \tilde{U}_{i,j} = 1。因此：

\begin{align} & 当 \|A\hat{U_{j}} \|_0 超过 \|A\tilde{U}_{j}\|_0 时，则该条件满足； \\ & 当且仅当 j 等于 j' 时，则 \|A\hat{U}_{j}\|_0 相等于 \|A\tilde{U}_{j}\|_0 。 \\ & 标签为 (5)。 \\ \\ \\ \\ \\ \\ \\

由于假设 iii 包括了所有各列，在这种情况下，在式（4）中对任意j' ∈ {1,…,s}都成立。若存在多于一个\hat{U}的列为非零项，则对每个这样的列计算式（4）的结果。令目标列为J的所有索引；对于每个j ∈ J而言，则设定\hat{U}_{i,j}=1；其中$i_j是对应行中唯一的一个非零元素的位置；而对于不属于J但属于某行中对应位置有非零值的那些元素，则设定这些位置上的值为1；由此可得：

特别地，在集合J中的每一个指标j上，
\|A\hat{U}_j\|_0 > \|A\tilde{U}_j\|_0，
而对于每一个不属于J的指标j而言，
\|A\hat{U}_j\|_0 = \|A\tilde{U}_j\|_0。

正如前面所述，每一个列索引j都唯一地对应着一个行索引。\quad \tilde{U}是一个置换矩阵，并且满足\tilde{U}\tilde{U}^T=I_s。\quad 因此有：

\left\|A\hat{U}\right\|_0 > \left\|A\tilde{U}\right\|_0，\tag{7}

根据（1），\hat{U}理应是最小值；然而根据（7），若\hat{U}\neq DP则\hat{U}并非最小值此与定义矛盾因而可证得\hat{U}=DP即有\hat{A}=ADP成立

Reference

This research investigates the separable nature of nonlinear ICA models, highlighting how sparsity contributes to effective source separation.