课程视频地址：http://open.163.com/special/opencourse/machinelearning.html

课程主页：http://cs229.stanford.edu/

更具体的资料链接：https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版：https://github.com/Kivy-CN/Stanford-CS-229-CN

这一讲介绍了奇异值分解以及独立成分分析。

奇异值分解

这部分来自老师上课笔记，讲义中没有，首先介绍奇异值分解的定义：

奇异值分解的定义

设$A$是一个$m\times n$矩阵, 则存在$m$阶正交矩阵$U$和$n$阶正交矩阵$V$, 满足

其中$\text{r = rank A},D\in \mathbb R^{m\times n}$. 习惯上,设 $\sigma_1\ge\sigma_2\ge…\ge\sigma_r>0$，称$\sigma_1,…,\sigma_r$为奇异值(singular value). 称$U$和$V$的前$r$列向量为奇异向量(singular vector)。这个分解为奇异值分解, 简称SVD。

奇异值分解的证明以及性质可以参考以下两篇博客：

这里老师上课介绍的奇异值分解有所不同，形式如下：

设$A$是一个$m\times n$矩阵（$m\ge n$），那么

这里来解释下这种形式，首先按之前的分解可以得到

注意$n\ge r$，我们补充$\sigma_{r+1},…,\sigma_n=0$，那么

从而可以得到老师给出的形式。注意这里的条件为$m\ge n$，如果$m<n$，则$A^T$可以得到上述分解。

现在做好了准备工作，接下来介绍如何对PCA使用SVD。

使用SVD处理PCA

现在假设数据已经预处理完毕，那么

我们对$X$使用SVD分解，那么

所以从上述表达式不难看出$V$的列向量为$\Sigma$的特征向量，因此选择$k$个主成分只要选择$V$的前$k$列即可，老师说这种方法在数据量很大的时候效果很好。

Part XII 独立成分分析

我们下一个主题是独立成分分析（ICA）。和PCA相似，这个算法将找到一组新的基来表示数据，但是目的非常不同。

​ 作为一个启发的例子，考虑“鸡尾酒问题”。在这个问题中，$n$个人在聚会上同时说话，放在屋子中的麦克风记录的是$n$个人叠加的声音。假设我们在屋中有$n$个不同的麦克风，因为每个麦克风距离每个人的距离不同，它记录了说话者声音的不同组合。利用麦克风的记录，我们可以把$n$个人的原始声音区分开来吗？

​ 为了形式化这个问题，我们想象数据$s\in \mathbb R^n$是由$n$个独立的数据源生成的。我们观测到的是

其中$A$是一个未知的方阵，被称为混合矩阵。重复观测得到数据集$\{x^{(i)};i=1,…,m\}$，我们的目标是恢复产生我们数据$x^{(i)}=As^{(i)}$的原始数据$s^{(i)}$。

​ 在我们的鸡尾酒问题中， $s^{(i)}$是一个$n$维向量，$s^{(i)}_j$是第$j$个人在时刻$i$发出的声音。同样的，$x^{(i)}$也是一个$n$维向量，$x^{(i)}_j$是第$j$个麦克风在时刻$i$录制的声音。

​ 令$W=A^{-1}$为还原矩阵。我们的目标是找到$W$，所以给定麦克风的记录$x^{(i)}$，我们可以通过计算$s^{(i)}= Wx^{(i)}$还原原始数据。为了记号方便，我们令$w_i^T$表示$W$的第$i$行，所以

因此，$w_i \in \mathbb R^n$，第$j$个原始数据可以通过计算$s^{(i)}_j= w_j^T x^{(i)}$来还原。

1.ICA的模糊性

$W=A^{-1}$能恢复到什么程度呢？如果我们对原始数据和混合矩阵没有先验知识，不难看出$A$中有些固有的模糊性，只给定$x^{(i)}$，这些模糊性是不可能恢复的。

​ 特别地，令$P$为$n$阶置换矩阵。这意味着$P$的每行每列有且只有一个$1$。下面是几个置换矩阵的例子：

如果$z$是一个向量，那么$Pz$是另一个向量，它包含了$z$坐标的置换版本。只给定$x^{(i)}$，没有办法区分$W$和$PW$。特别地，原始数据的置换是有歧义的。幸运的是，在绝大多数应用中，这一点无关紧要。

​ 此外，没有办法恢复$w_i$的大小。例如，如果用$2A$代替$A$，每个$s^{(i)}$用$0.5s^{(i)}$代替，那么我们观察的结果$x^{(i)}=2A.(0.5)s^{(i)}$将和之前一样。更广泛的，如果$A$的某一列乘以$\alpha$，相应的原始数据乘以$1/\alpha$，那么给定$x^{(i)}$，我们无法发现发生了什么。因此，我们无法恢复数据“准确”的大小。但是，对于我们正在考虑的应用——包括鸡尾酒问题，这种歧义性也没有影响。特别地，将说话者的说话信号$s^{(i)}_j $缩放正数$\alpha$只影响说话者的声音大小。另外，改变符号也没有影响，$s^{(i)}_j $和$-s^{(i)}_j $麦克风在的声音相同。因此，如果通过一个算法得到的$w_i$缩放非零常数，相应恢复的原始数据$s_i =w_i^Tx$将缩放相同的常数；但是这通常没有影响。

​ 这些是ICA中仅有的模糊性来源吗？事实上，只要原始数据$s_i$不服从高斯分布，那么这就是仅有的模糊性来源。为了看出来自高斯分布的数据的困难之处，考虑$n=2$，$s\sim \mathcal N(0,I)$的例子。这里，$I$是一个$2\times 2$的单位矩阵。注意到标准正态分布$\mathcal N(0,I)$密度的等高线是圆心位于原点的圆，并且密度是旋转对称的。

​ 现在，假设我们观测到$x=As$，其中$A$是混合矩阵。那么$x$服从高斯分布，均值为$0$，协方差矩阵为$\mathbb E[xx^T]= \mathbb E[Ass^T A^T]= AA^T$。现在，令$R$是任意正交矩阵，所以$RR^T= R^TR =I$，然后令$A’=AR$。如果使用$A’$而不是$A$来作为混合矩阵，我们将观测到$x’= A’s$。$x’$任然服从高斯分布，均值为$0$，协方差为

因此，无论混合矩阵为$A$还是$A’$，我们观察到的数据都服从$ \mathcal N(0,AA^T)$。

​ 我们上述讨论都建立于多元标准正态分布是旋转对称的。尽管ICA对服从高斯分布的数据无能为力，但事实上，只要数据不服从高斯分布，给定足够的数据，就有可能恢复$n$个独立的原始数据。

2.密度和线性变换

​ 如果$s$是一个向量值分布，密度为$p_s$，$x=As$，其中$A$是一个可逆方阵，那么$x$的密度由下式给出

其中$W=A^{-1}$

3.ICA算法

我们现在开始推导ICA算法。假设每个原始数据$s_i $的分布由密度$p_s$给出，所以原始数据$s$的联合分布为

注意到在建模中让联合分布等于边际分布的乘积，我们可以得出原始数据是独立的假设。利用前一部分的公式，我们可以得到$x= As =W^{-1}s$的密度为

剩下只要确定每个独立数据源的密度$p_s$

​ 回忆一下，给定实值随机变量$z$，它的累计分布函数(cdf)$F$由

定义。此外，$z$的密度为$p_z(z)= F’(z)$

​ 因此，要确定$s_i$的密度，我们只要确定它的cdf。一个cdf必须是一个从$0$到$1$单调递增的函数。从之前的讨论中，我们不能选择cdf为高斯分布的cdf。取而代之的，我们将选择一个合理“默认”的函数，它从$0$缓慢增加到$1$，这个函数是sigmoid函数$g(s)=1/(1+e^{-s})$。因此$p_s(s)=g’(s)$。

​ 方阵$W$是我们模型的参数，给定训练集$\{x^{(i)};i=1,…,m\}$，对数似然函数如下

我们对上式关于$W$求最大值，首先对$\log |W|$关于$W$求梯度，注意到

所以

接着对$\sum_{j=1}^n \log g’(w_j^T x^{(i)})$关于$W$求梯度，因为$W$每一行为$w_j^T$，所以先关于$w_j$求梯度，注意到

所以

从而$\nabla_W\sum_{j=1}^n \log g’(w_j^T x^{(i)})$的第$j$行为

因此对于训练样本$x^{(i)}$，随机梯度下降法的更新规则为：

其中$\alpha$是学习率。

​ 在算法收敛后，我们通过计算$s^{(i)}= Wx^{(i)}$来恢复原始数据。

注记

当写下数据的似然函数时，我们隐藏的假设了数据$x^{(i)}$直接相互独立（这里的独立是对于不同的$i$；和$x^{(i)}$的每个坐标独立不同），所以训练集的似然函数为$\prod_{i}p(x^{(i)};W)$。这个假设对于演讲数据以及其他$x^{(i)}$相关的时间序列都是不正确的，但是如果有足够的数据，即使数据相关，算法的效果也不会受影响。但是，对于数据相关的问题，在使用随机梯度下降法的时候，如果以随机顺序访问数据，那么会加快收敛。