feng's Blog

Happy coding

对SVD唯一性的理解

 

这篇文章主要讨论一下对Singular value decomposition的理解。
 
SVD告诉我们,对于任何一个$m\times n$的矩阵$A$,都存在这样的一个分解:
\[A=U\Sigma V'\]
其中$U$是$m\times m$的酉矩阵,也就是$UU^* = I$;$V$是一个$n\times n$的酉矩阵;$\Sigma$是一个$m\times n$的矩阵,非对角上的元素都是0,对角线上的元素都是非负的实数,不管$A$是实数矩阵,还是酉空间中的矩阵,或者说有虚数元素。
 
定理告诉了我们总是存在一个这样的分解的,但并不是说这样的分解是唯一的。比如说有一个permutation matrix,$J$。permutation matrix就是把单位矩阵的行进行重排列,或者列进行重排列。比如说把单位矩阵的第一行和第二行进行交换,第四行和第九行进行交换,交换后的矩阵就是一个permutaion matrix。一个矩阵$A$,左乘一个$J$,相当于对$A$的相应行进行行交换。右乘的话,相当于列交换。两个$J$相乘为一个单位矩阵,相当于对单位矩阵交换了两行之后,再交换一次,不变。
 
回到正题,任何一个$J$拿到了之后,我们有下面的式子成立
\[A=(UJ_m)(J_m\Sigma J_n)(VJ_n)'\]
$UJ_m$依然是一个酉矩阵,$VJ_n$也依然是一个酉矩阵。这里$J$的小角标表示$J$的大小,是$m\times m$的还是$n\times n$的。如果说$m\ge n$,并且$J_n$是$J_m$左上角的,$J_m$右下角是一个单位阵,右上角和左下角都是0矩阵的话,那么$J_m\Sigma J_n$依然也是一个对角阵。之前对$J_m$和$J_n$的描述,相当于是说,如果$J_m$使得$\Sigma$的第$i$行和第$j$行交换的话,那么$J_n$应该使得$\Sigma$的第$i$列和第$j$列进行交换。从而使得$J_m\Sigma J_n$依然是一个非对角线上元素都是0的矩阵,相当于是将$\Sigma$的对角线上的元素进行了一个重新排列。这是事实告诉我们,SVD的分解是不唯一的。
 
接下来再考虑一点,如果说$\Sigma$唯一确定之后,这个$U$和$V$是否能够唯一确定的呢?我们再引入一个矩阵,用$K_m$表示,是一个$m\times m$的对角方阵,对角线上的元素具有$e^{i\phi}$的形式,其中$\phi$可是互相不相同。根据定义,我们有$K_mK_m^* = I$。那么
\[A=UK_m K_m^*\Sigma K_n(VK_n)^*\]
其中$U K_m$和$VK_n$分别仍然是酉阵,如果说$K_m$的对角线上第$i$个元素和$K_n$对角线上第$i$个元素相同的话,那么$K_m^*\Sigma K_n = \Sigma$。也就是说,如果$U$的第$i$列乘以$e^{i\phi}$,并且$V$的第$i$列也乘以$e^{i\phi}$,那么结论依然成立。
 
然后,我们继续疑问:如果$\Sigma$给定,并且允许$U$和$V$差一个$e^{i\phi}$的话,那么$U$和$V$是否能够唯一确定?
这一种情况,比较麻烦。如果说$\sigma_i$都是non-degenerate的话,那么是唯一确定的。否则的话,依然不能够唯一确定。
 
对degenerate的定义是这样子的。如果$\sigma_i$是degenerate的,那么它有两个互相独立的singular vector。
在这里补充一下,singular value就是$\sigma_i$,而$\mathbf{u}_i$和$\mathbf{v}_i$分别是singular vector,其中要求$i<=\min{m, n}$。并且有下面的式子成立
\[A\mathbf{v}_i = \sigma \mathbf{u}_i\]
并且
\[A^*\mathbf{u}_i = \sigma \mathbf{v}_i\]
 
如果说$\sigma_i$都是不一样的,那么所有的$\sigma_i$都是non-degenerate的,也就是说这个时候,$U$和$V$都是唯一确定的,在一定意义下。如果说$A$是一个实数矩阵,$U$和$V$可以也是实数的,这样的话,对于其唯一确定的理解是,差一个符号。
 
这里对于degenerate的讨论比较少,以后有时间补上。

learning rate adaptation and stopping criterion

最近读了一篇文章,关于Binary Multidimensional Scaling的。原文见下面的链接:

http://tedlab.mit.edu/~dr/Papers/bmds.jou.pdf

其中4.4部分讲到了关于learning rate的设置的一个经验方法,觉得讲得很好。以下谈谈自己的理解。

------------------------------------------------------------------

处理的问题,是一个无约束的优化问题。也就是说,我们希望去找到一个\(\mathbf{x}\)能够最小化\(f(\mathbf{x})\)。这里的\(\mathbf{x}\)是一个向量,如果是\(1\times1\),就是一个标量。如果我们处理的未知数是一个矩阵,那么把这个矩阵中得未知数排成一列之后,也是一个未知的向量。

 

接下来考虑如何得到这样的\(\mathbf{x}\)。其中一个经常用到的方法是梯度下降法。也就是这样的一种迭代算法

\[\mathbf{x}_{t + 1} = \mathbf{x}_t - s  \nabla{f(\mathbf{x}_t)}\]

这里的\(\mathbf{x}_t\)指的是第\(t\)次迭代时,\(\mathbf{x}\)的值。$s$是步长,$\nabla{f(\mathbf{x}_t)}$是函数在$\mathbf{x}_t$的梯度值。在梯度的相反方向上,可以期望能够找到一个新的$\mathbf{x}_{t + 1}$使得目标函数值,尽可能的小。这里的问题来了,

如何确定这个步长$s$?

 

对这个问题的研究很多。这里我们只讨论一种经验性的简单做法。首先令$s = \alpha {\|\mathbf{x}_t\|}/{\|\nabla{f(\mathbf{x}_t)}\|}$。这是因为一般情况下,我们很难确定这个梯度值的取值范围。比如说$\mathbf{x}$的取值范围是在0到1之间,而它的梯度值有可能是在100左右的位置,也可能是在0.01左右的样子。那么这是时候,直接确定$s$,比较困难。在这个时候,我们在$\nabla{f(\mathbf{x}_t)}$前面乘以一个标量${\|\mathbf{x}_t\|}/{\|\nabla{f(\mathbf{x}_t)}\|}$,起到了一个矫正的作用。我们就可以确定,如果当前的$\mathbf{x}_t$是1,那么这个矫正之后梯度方向的模也是1。接下来就考虑$\alpha$应该如何确定。

 

总的来说,是首先给定一个初始值$\alpha = 0.2$。然后根据情况,对这个$\alpha$做一定的修改。

初始值$0.2$是文章中的原话,在最近做的一个项目中,用的是$0.1$,实验进行的很好。

接下来,我们定义,或者说在实验的过程中,维护两个变量。一个是progress,一个事instability。其中progress的定义为

\[progress = \frac{S_{t} - S_{t + 1}}{|S_{t}|}\]

其中$S_{t}=f(\mathbf{x}_t)$。可以看到,如果progress小于0的话,代表$S_{t + 1}$比$S_{t}$小,目标函数值减小了,正是我们所期望的事情。如果很不幸的,progress大于0的话,说明了函数值没有减小,反而变大。这个时候,我们就需要减小一个步长$\alpha$了。按照文章中的参数,$\alpha$变为原来的0.75。根据新的$\alpha$,可以算出来新的$\mathbf{x}_{t + 1}$,从而可以得到新的$S_{t + 1}$。如果比$S_{t}$变小了,也就是这个时候progress小于0了,就进入下一个循环。否则的话,继续减小$\alpha$,直到progress小于0,或者达到了循环停止的条件。

另一个参数是instability,其定义如下

 \[instability = I_{t + 1} = 0.5 (I_{t} + \frac{|P_{t - 1} - P_{t}|}{|P_{t - 1}|})|\]

可以想象,如果我们的目标函数值能够稳定的下降的话,那么$P_{t}$将会是一个常数,代表了目标函数值下降的程度。这个时候instability就会趋近于0。也就是说,instability越小,越是我们希望的事情。它的初值设置成10,同时,我们约定,每一次$\alpha$发生变动的时候,$I_{t}$都被重置成10。接下来,在考虑,如果这个instability比较大的话,说明不是很稳定,也就是说,目标函数值下降的时快时慢,有可能函数的曲线就是这样子的,很凹凸不平。也有可能是在最优值附近,在最优值附近不停地摆动。但不管怎么说,目标函数值是下降到的,所以尽管instability很大,我们依然不去做任何事情。唯一需要做的是这样的一种情况,instability很小,说明很稳定,但是呢,progress也很小。也就是说我们的目标函数值减小的速度很慢,就像蚂蚁一样。这是情况,说明了步长$\alpha$比较小,我们需要增大这个数值。具体来说,在$progress < 0.02$并且$instability<0.2$的时候,将$\alpha$乘以1.2。

 

循环停止的条件,在这里的设置是progress小于0.01,在连续的10个循环过程中。

写在前面的话

计划,这个博客写一些技术相关的博客。领域主要限定在机器学习和计算机视觉,也会有一些跟编程有关的内容。

 

以读后感,原创为主。督促自己多读书,读好书。不断进取。