转载

研究领域总结(二):稀疏——矩阵补全

I.定义

矩阵补全(Matrix Completion)是指如下一个问题: 有一个巨大的矩阵$X/in/mathbb{R}^{m/times n}$,然而人们只能观测到其中的部分元素。记观测到的矩阵为矩阵$M/in/mathbb{R}^{m/times n}$(没观测到的元素位置以$0$填充),则$P_/Omega(X)=P_/Omega(M)$,其中观测到的元素下标集合记为$/Omega$,$P_/Omega$表示投影到$/Omega$。

为了说明它的意义,这里举一个最常见的情形,即评分预测/推荐系统——协同过滤,如豆瓣之类的网站,会有很多用户(看作行)对很多电影(看作列)进行打分(矩阵元素的值),每个用户只会对很少的电影打分,这就导致我们的打分矩阵是一个部分观测到的矩阵,而往往我们想预测出来用户对没有打分的电影的评分,依次来推荐或挖掘等等。同时注意到行数和列数往往非常非常大(>百万级别),并且矩阵的稀疏度可能很高很高(<0.x%)。

显然这个问题是个不适定问题,想要补全整个矩阵,我们需要一些额外的约束,最常见的就是假设这个矩阵是低秩的,一方面这符合我们对自然界的观测,另一方面可以用“物以类聚,人以群分”的一致性来做直觉解释。考虑观测有噪声的情况,则整个问题可以形式化为:

/[ /min_{X}/|P_/Omega(X-M)/|_F^2 /quad s.t. rank(X)/leq k. /]

II.求解:化归到稀疏问题

rank是个很难搞的东西,而且把整个问题变成非凸的了。把$X$的奇异值表示成向量形式$/sigma$,那么根据SVD分解的性质,$rank(X)/leq k$等价于 $/|/sigma/|_0/leq k$。这样,就化归到了稀疏问题上来,可以用压缩感知、稀疏编码的思路来思考,只不过目标从向量拓展到了矩阵。

1.松弛到凸问题。

类似压缩感知,我们也可以把$/|/sigma/|_0$松弛到$/|/sigma/|_1$,这样就变成了凸问题。同时,松弛到$/|/sigma/|_1$即矩阵的Nuclear norm  /|X/|_*,问题化为:

/[ /min_{X}/|P_/Omega(X-M)/|_F^2 +/lambda /|X/|_* /]

关于这个问题,有很多解法,大部分都是从稀疏里变换过来的,如收缩算子、ADMM等等。

Candes证明了矩阵补全和压缩感知一样,在满足矩阵size和采样率(观测稀疏度)要求下,有exact recovery的bound(事实上,矩阵补全的坑就是Candes挖的)。有兴趣的可以读一下他的paper: E. J. Candès and B. Recht. Exact matrix completion via convex optimization.  Found. of Comput. Math. 9  717-772

2.非凸解法。

同样的,虽然松弛到凸问题有最优解,有bound guarantee,但是论起实际效果往往非凸的一些解法更准确更快速。这部分我做的比较多。主要两类:

    • 类似OMP,可以用贪心方法选基,每次选一个rank one的矩阵,然后更新系数,选k个即能保证矩阵秩小于等于k。注意到一个重要的区别是稀疏里有个字典,也即从一组冗余基里选,而矩阵补全没有这样一个字典,可以从无限个数的基里选,可以用top SVD 或者其它子目标问题求解得到。
    • 非凸惩罚项,比如MCP。

III.协同过滤、去噪

工业界的推荐系统最主要的两个思路就是基于内容和协同过滤两种。协同过滤更standard的是用矩阵分解来做(个人认为主要还是矩阵分解比补全出来的早,抢占了市场),矩阵分解根据一篇paper的定理(一时忘记出处了),其实是和Nuclear norm约束等价的。期待矩阵补全在实际中的更多应用。此外,矩阵补全也可以用来做图像去噪。

正文到此结束
Loading...