UA MATH567 高維統(tǒng)計(jì)專(zhuān)題2 Low-rank矩陣及其估計(jì)1 Low-rank Matrix簡(jiǎn)介

例 在推薦系統(tǒng)中，Netflix data是非常經(jīng)典的數(shù)據(jù)集?？紤]它的電影評(píng)分?jǐn)?shù)據(jù)，用矩陣的每一行表示每一個(gè)用戶(hù)（假設(shè)有$d_1$個(gè)用戶(hù)），每一列表示每一部電影（假設(shè)有$d_2$部電影），矩陣的第$i$行第$j$列表示第$i$個(gè)用戶(hù)對(duì)第$j$部電影的評(píng)分，記這個(gè)矩陣為$Y$。目前世界上大概兩三百萬(wàn)部電影，即使每個(gè)用戶(hù)每天給24部評(píng)分一年365天無(wú)休也要三百多年才能評(píng)完分，所以這個(gè)矩陣中有巨多missing data。但是根據(jù)這些評(píng)分?jǐn)?shù)據(jù)，我們想估計(jì)用戶(hù)對(duì)每部電影的真實(shí)評(píng)分，也就是要估計(jì)一個(gè)矩陣$\Theta \in {\mathbb{R}}^{d_1\times d_2}$。在評(píng)分的時(shí)候，口味相同的用戶(hù)對(duì)不同電影的評(píng)分傾向于一致，而同一個(gè)用戶(hù)對(duì)相似電影的評(píng)分也會(huì)比較類(lèi)似，所以我們大致可以認(rèn)為$\Theta$行列之間可能會(huì)有很強(qiáng)的線(xiàn)性相關(guān)性，因此$\Theta$的秩應(yīng)該比較低。于是我們可以把$\Theta$的估計(jì)用下面的模型表示：
$$\begin{gathered} \underset{\Theta }{\min }rank(\Theta ) \\ s.t.P_{\Omega }(\Theta )=Y \end{gathered}$$

其中$$P_{\Omega }:{\mathbb{R}}^{d_1\times d_2}\to \Omega =\{(i,j):Y_{ij}isnotmissing\}$$

翻譯一下，這個(gè)優(yōu)化想要最小化$\Theta$的秩，同時(shí)要保證在評(píng)分?jǐn)?shù)據(jù)沒(méi)有缺失的時(shí)候，$\Theta$與用戶(hù)評(píng)分相等，所以這個(gè)模型實(shí)際上是在嘗試補(bǔ)全用戶(hù)評(píng)分中缺失的那些數(shù)據(jù)，這也是它被稱(chēng)為matrix completion的原因。

---

Matrix Completion

我們先嘗試對(duì)這個(gè)模型做一點(diǎn)一般性的分析，用0-1矩陣$E_{ij}$表示$\Omega$中的每個(gè)元素，$E_{ij}\in {\mathbb{R}}^{d_1\times d_2}$，除了第$i$行第$j$列為1外其他元素均為0，則
$$Y_{ij}=?E_{ij},\Theta ?$$

其中$?A,B?$表示兩個(gè)矩陣的“內(nèi)積”：
$$?A,B?=\sum _{i,j}{A}_{ij}{B}_{ij}=tr(A^{T}B)=tr(B^{T}A)$$

這樣做的好處是可以把約束$P_{\Omega }(\Theta )=Y$改寫(xiě)為
$$Y=?E_{ij},\Theta ?,(i,j)\in \Omega$$

在noisy setting下可以假設(shè)$Y_{ij}=?E_{ij},\Theta ?+w_{ij}$，其中$w_{ij}$是一個(gè)噪聲，這個(gè)形式非常像我們熟悉的回歸問(wèn)題，$Y_{ij}$是observation，$E_{ij}$是design matrix，$w_{ij}$是noise。

現(xiàn)在我們考慮matrix completion的一般框架：
$$Y_i=?X_i,\Theta ?+w_i,i=1,?,n$$

其中$X_i,\Theta \in {\mathbb{R}}^{d_1\times d_2}$，引入線(xiàn)性映射$\mathcal{X}:{\mathbb{R}}^{d_1\times d_2}\to {\mathbb{R}}^n$
$$\mathcal{X}(\Theta {)}_i=?X_i,\Theta ?$$

則$\mathcal{X}$是一個(gè)三階張量，
$$Y_i=\mathcal{X}(\Theta )+w_i$$

把這個(gè)模型類(lèi)比為線(xiàn)性回歸，那么$\mathcal{X}$就是design tensor，$\Theta$是系數(shù)，只是我們的目標(biāo)函數(shù)并不是最小二乘損失，而是系數(shù)的秩：
$$\begin{gathered} \min rank(\Theta ) \\ s.t.y=\mathcal{X}(\Theta ) \end{gathered}$$

把這個(gè)優(yōu)化的等式約束放松為用$L_2$-norm表示的不等式約束，那么我們的優(yōu)化模型就變成了
$$\begin{gathered} \min rank(\Theta ) \\ s.t.{\Vert y?\mathcal{X}(\Theta )\Vert }_2^2\le R^2 \end{gathered}$$

這個(gè)不等式約束對(duì)模型造成的效果和最小二乘損失沒(méi)有區(qū)別，因此我們可以把這個(gè)模型看成是一種Penalized Least Square，penalty是$rank(\Theta )$。在多數(shù)情況下，這個(gè)優(yōu)化是NP-hard問(wèn)題，只有在特定條件下，它才能在Polynomial time內(nèi)完成。

---

Singular Value Decomposition (SVD)
$X\in {\mathbb{R}}^{m\times n},r=rank(X)$，則compact version的奇異值分解為
$$X=U\Sigma V^T=\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T$$

其中$U\in {\mathbb{R}}^{m\times r},V\in {\mathbb{R}}^{n\times r}$滿(mǎn)足
$$U^{T}U=V^{T}V=I$$

并且
$$\Sigma =diag({\sigma }_1,?,{\sigma }_r),\underset{singularvalues}{{\sigma }_1\ge ?\ge {\sigma }_r}>0$$

complete version（不妨假設(shè)$m>n$）的奇異值分解為
$$X=U\Sigma V^T$$

其中$U\in {\mathbb{R}}^{m\times m},V\in {\mathbb{R}}^{n\times m}$滿(mǎn)足
$$U^{T}U=V^{T}V=I$$

并且$\Sigma \in {\mathbb{R}}^{m\times n}$，前$n$個(gè)主對(duì)角元是奇異值，其余部分都是0；記
$$\sigma (X)=({\sigma }_1(X),?,{\sigma }_n(X)),\underset{singularvalues}{{\sigma }_1\ge ?\ge {\sigma }_n}\ge 0$$

則
$$rank(X)={\Vert \sigma (X)\Vert }_0=\#\{i:{\sigma }_i>0\}$$

這個(gè)結(jié)果可以說(shuō)明rank-minimization與$L_0$-minimization之間存在某種等價(jià)性。

定理
Best Low-rank Approximation
$$\begin{gathered} \underset{X}{\min }{\Vert X?Y\Vert }_F \\ s.t.rank(X)\le r \end{gathered}$$

的解為${\sum }_{i=1}^r{\sigma }_i{u}_i{v}_i^T$，其中$Y={\sum }_{i=1}^n{\sigma }_i{u}_i{v}_i^T$。其中Frobenius范數(shù)可以替換為其他orthogonal-invariant norm（即對(duì)某個(gè)矩陣而言與正交矩陣相乘后取范數(shù)與原矩陣直接取范數(shù)相等），approximation error為
$${\Vert \sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T?Y\Vert }_F=\sum _{i=r+1}^n{\sigma }_i^2$$

這個(gè)定理對(duì)其他形式的Best Low-rank Approximation也成立，比如
$$\begin{gathered} \min rank(X) \\ s.t.\Vert X?Y\Vert \le ? \end{gathered}$$

的解為為${\sum }_{i=1}^r{\sigma }_i{u}_i{v}_i^T$，其中
$$r=\inf \{r:\sum _{i=r+1}^n{\sigma }_i^2\le ?\}$$

---

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的UA MATH567 高维统计专题2 Low-rank矩阵及其估计1 Matrix Completion简介的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。