科学研究行业小结(二):稀少引流矩阵补全

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. pletion via convex optimization. Found. of Comput. Math., 9 717-772

2.非凸解法。

一样的,尽管松驰到凸难题有最佳解,有bound guarantee,可是论起具体实际效果通常非凸的一些解法更准确迅速速。这一部分我做的较为多。关键两大类:


相近OMP,能够用贪婪方式选基,每一次选一个rank one的引流矩阵,随后升级系数,选k个即能确保引流矩阵秩低于相当于k。留意到一个关键的差别是稀少里有一个字典,也即从一组数据冗余基里选,而引流矩阵补全沒有那样一个字典,能够从无尽数量的基里选,能够用top SVD 或是其他子总体目标难题求出获得。 非凸处罚项,例如MCP。
III.协作过虑、去噪

工业生产界的强烈推荐系统软件最关键的2个构思便是根据內容合谐同过虑二种。协作过虑更standard的是用引流矩阵溶解来做(本人觉得关键還是引流矩阵溶解比补全出去的早,占领了销售市场),引流矩阵溶解依据一篇paper的定理(一时忘掉出處了),实际上是和Nuclear norm管束等额的的。希望引流矩阵补全在具体中的大量运用。另外,引流矩阵补全还可以用于做图象去噪。



扫描二维码分享到微信