CS229 Lesson 15 奇异值分解

课程视频地址: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)}​$相关的时间序列都是不正确的,但是如果有足够的数据,即使数据相关,算法的效果也不会受影响。但是,对于数据相关的问题,在使用随机梯度下降法的时候,如果以随机顺序访问数据,那么会加快收敛。

本文标题:CS229 Lesson 15 奇异值分解

文章作者:Doraemonzzz

发布时间:2019年01月08日 - 14:55:00

最后更新:2019年03月07日 - 17:50:25

原始链接:http://doraemonzzz.com/2019/01/08/CS229 Lesson 15 奇异值分解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。