Glophy Zone Backup

機率在提昇計算速度之應用 PDF 列印 E-mail
作者 曾正男   
2012/12/13, 週四

在大資料的計算中所面臨的問題第一個是要能算,第二個是要準,再來是要快。若三個條件需要同時要求時在計算上就有其挑戰性。最容易出現大資料的環境就是網頁服務,這裡的資料除了量大之外,變數新增與淘汰的速度也快。若需要即時的網頁服務,那背後需要承載的計算量就非常可觀。許多傳統的方法在應用到大資料計算時,並不是像許多人認知的把dimension 放大即可,計算量會隨著尺度呈高次成長的方法幾乎都不適用。因此我們常須要透過機率方法的介入,來降低計算的時間。

舉個簡單的例子:若我們要檢查兩個矩陣A, B 的乘積是否等於另外兩個C, D 矩陣的乘積,一個很簡單的方式就是把A, B 矩陣的乘積和C, D  矩陣的乘積都算出來,然後把得到的兩個新矩陣,做元素上的一一比對,若其中一個位址的元素不同,那麼這兩個矩陣就不相同。這看似簡單的問題在矩陣的大小特別設計之後就會有計算效率的問題值得討論。例如,A, C 的大小若是\(m\times r\) ,B, D 的大小是\( r\times n \) ,並且 \(m,n >> r \), 那麼AB 與 CD 會是一個low rank 的大矩陣。倘若m = 100000, n = 50000, r = 3,那AB 與CD 就是一個 \(100000\times 500000\) 但是rank 只有3 的大矩陣。要乘開這個大矩陣,在許多電腦上就是辦不到的事。

或許我們不需要真的把矩陣乘開並且放置在記憶體中,然後再對對應元素一一比對。我們可以給定 \( (i,j) \) 位置,然後計算A 的第i 列與B 的第j 行是否等於C 的第i 列與D 的第j 行的乘積,並檢查是否相等。這樣我們就避開不能算的問題,當所有的\( (i,j) \) 數對都算過一遍之後,我們就可以確認AB 是否等於CD。這雖然是很暴力的方法,卻在有限時間內可以計算的。因為現在的計算機運算速度都很快,所以我們把加法、乘法以及比對都當作一個計算計算量的單元。這樣要確認AB 是否等於CD ,以上述方法我們比較一個\( (i,j) \) 位置需要3 個乘法,兩個加法,一個比對,總計六個計算。加總每一個元素的位置總共需要3000000000000的計算量。 

有一個簡單的機率方法可以讓我們大幅降低比對的計算量。若我們隨機選取一個長度是50000的向量x ,然後計算A(Bx) 是否等於C(Dx) ,若結果相同,我們便稱AB = CD。這樣計算量就會降低到1599994,這個數字是原來計算量的 \( 5.3*10^{-7}\)倍。為甚麼只用到一個隨機的x 就可以決定AB 是否等於CD 呢?

其實我們用到的是檢查AB-CD 的null space 是否等於整個定義域的觀念。想想看在三度空間中,我們隨便給兩個隨機向量,這兩個向量會平行的機率是多少?答案是0。又給定一個三度空間中的平面,然後再隨機給一個三度空間中的向量,這個向量會落在這個平面的機率是多少?也是0。那麼在n 維空間中給定一個n-1 維的平面,然後隨機給一個向量,問此向量落在此平面的機率是多少?答案當然還是0。當我們隨機給一個x 結果A(Bx)就等於C(Dx) 了,這表示隨便給一個x ,x 都會落在AB-CD 的null space 中。這代表的是AB-CD 的null space 的維度絕對和x 定義域的維度相同,若少一個維度以上,那麼x 落在null space 的機率就是0 。反之,AB-CD 的null space 若是整個定義域,那麼AB 當然等於CD 。這就是利用機率方法配合線性代數的觀念達到降低計算量的一個範例。

最後更新 ( 2014/03/08, 週六 )
 
下一個 >