虛擬實境 建模 SVD 筆記

contents

  1. 1. SVD
  2. 2. Map-Reduce

由於在選讀論文時,和上課都遇到相關問題,但一直對這 SVD 的實際感觸沒很深,了解數學計算,卻不知道特性一直很困惑我。在這裡收集一下曾經學過的內容,當初在線性代數時沒有學到這一塊,至於 $LU$ 分解有沒有上到過,我自己也深感困惑,不過看一下網路資源勉強還能理解。

至於 SVD 則在線性代數非常重要,在許多領域時常會遇到,如巨量資料 (massive data)?機器學習?影像處理?就我所知理解看看吧!

SVD

定義從一般式

$$A_{m, n} = U_{m, m} \Sigma_{m, r} V_{n, r}^T$$

得到縮減過後的相似矩陣

$$A_{m, n} \cong U_{m, r} \Sigma_{r, r} V_{n, r}^T$$

給定 $A$ 矩陣,要變成三個矩陣相乘,可以壓縮儲存空間,一般來說都是拿來得到近似的 $A$ 矩陣,藉由刪除過小的 eigenvalue 來完成,eigenvalue 就是所謂的矩陣特徵值。

在學線性代數時,沒有仔細想過 eigenvalue 的意義所在,每一個 eigenvalue 也會對應一個 eigenvector,這些 eigenvalue 大小對應的分佈的相關性大小,而 eigenvector 則表示新的轉換軸的方向。類似最小平方法得到的結果。

但在巨量資料課程中我們可以知道一件事情,若是稀疏矩陣 $A$,經過 SVD 運作後,得到 $U, V$ 矩陣都是稠密的,因此空間儲存反而划不來,因此會有另外一種解法 CUR,可以上網搜尋 massive data mining coursera 在 這裏 可以知道關於 CUR 的資訊。

從課程中的例子來看,假設在電影評論系統中,則 A 矩陣表示電影對人的喜好度,則 SVD 相當於如下描述 (假想,單純的矩陣概念)

  • $A(i, j)$ 電影編號 i 對用戶 j 的好感度
  • $U(i, j)$ 電影編號 i 對電影屬性 j 的成分程度
  • $\Sigma(i, j)$ 電影屬性 i 跟電影屬性 j 的之間重要性。
  • $V(i, j)$ 表示用戶 i 對電影屬性 j 的偏愛程度。

也就是說有一些電影屬性不是很重要,可以移除掉,這樣的表示法得到一個近似的矩陣 $A$

在巨量資料中一個有趣的運用,可以用在購物推薦系統中,來達到預測相關性,跟某人對其他產品的喜好程度或者是需求性,但是在處理之前會遇到矩陣過大,但又非常稀疏,為了解決紀錄問題,就有奇奇怪怪的 Dimensionality Reduction 來完成,SVD 就是其中一種方法。

其他應用部分,將不重要的特徵值消除,來求得哪些元素是需要的,看到有一篇 文章 在做 PCA 主成份分析。

$$\begin{align} & A_{m, n} V_{n, r} = U_{m, r} \Sigma_{r, r} V_{n, r}^T V_{n, r} \\ & \because V_{n, r}^T V_{n, r} = I \\ & \therefore A_{m, n} V_{n, r} = U_{m, r} \Sigma_{r, r} \\ \end{align}$$

如此一來就可以知道要保留哪幾個主要資訊。

在虛擬實境論文中也是有這樣的處理,做的是 CT 建模,將模型的每個頂點,要計算 QEM (最小二次誤差) 的重要性,可以將其表示成一個矩陣,利用 SVD 方式得到,來決策要保留前 k 個重要性的節點,再將其他節點移除,來讓新得到節點盡可能地可以貼近真實模型。

之所以會這麼做,是要利用內插法來強迫得到邊緣偵測,但這樣會造成很多新頂點,為了要把過多頂點消除,使用 QEM 作為評價方法,利用 SVD 來完成大規模刪除的操作。

Map-Reduce

都明白 SVD 是一個很繁複的做法,有一個 $O(N^3)$ 的算法來求得所有 eigenvalue,若要用一般電腦跑,光是得到一個大矩陣所有 eigenvalue 複雜度相當高,其複雜程度沒有細讀過。有一種迭代的方法,類似馬可夫過程,每一次迭代可以逼近一個 eigenvalue,為了得到 n 個 eigenvalue,想必要迭代非常多次。運用 Map-Reduce 分散到很多台群落電腦加快矩陣乘法,這種方法的複雜度是可以期待的。

詳細操作 請參考

eigenvalue $\lambda$ 滿足

$Av = \lambda v$

現在開始迭代 $v$ 讓其等式趨近於穩定

$A x_{i} = \lambda x_{i+1}$

初始化$x_{i} = (1, 1, ..., 1, 1)$ ,其中$|x_{i}| = 1$ 藉由長度為 1 的向量,來求得$\lambda$,之所以要對 $x$ 進行正規化,其一就是要求出$\lambda$,另一個原因是要看何時穩定,當$|x_{i} - x_{i+1}|$ 差距夠小時,則表示進入穩定狀態。

那就可以得到矩陣 $A$ 的其中一個 eigenvalue,為了求得另外一組解,得到新的$A^* = A - \lambda x x^T$,再對$A^*$ 找到 eigenvalue,不斷地迭代下去。