本篇以隨筆平易近人的方式，寫一些如何降低演算法"計算量"的一些核心抽象概念。
[利用分配律尋找完全多分圖]
相信大家都知道加法(+) ，乘法(\times) 分配律的概念，複習一下
(A+B)\times (C+D) =A \times C + B \times C + A \times D + B \times D
左式推廣我們可以寫成
\underbrace{(A_1+A_2+....+A_{L_1})}_{\text{第一組}}\times \underbrace{(B_1+B_2+....+B_{L_2})}_{\text{第二組}} \times ... \times \underbrace{( ... )}_{\text{第 $m$ 組}}
每一組 有L_{i} 個元素，總共有 L 個元素(字母)
而且每一組有 L_{i} -1 個加法，總共就有 \displaystyle{\sum^{m}_{i=1}(L_i - 1) = L - m } \text{ 個加法}
由於每一組中間穿叉乘法，有 m-1 個乘法。我們分別把加法，乘法個數記做 ~ \otimes , \oplus，所以左式總共的運算數為
\text{左式運算量 = } (m-1) \cdot \otimes + (L-m) \cdot \oplus
右式完全展開，非常多項，要完整寫出來並非容易的事，但是我們知道它應該是長這樣
(\text{第一組連乘}) + (\text{第二組連乘} ) + (\text{第三組連乘} ) + ........
至於究竟有幾組連乘呢 ??
答案是 \displaystyle{ \prod^{m}_{i=1}L_i } 組，而每一組中間穿叉 L_i -1 乘法
右式總運算量為
\text{右式運算量 = } (L-m)\cdot \otimes + \displaystyle{ \prod^{m}_{i=1}L_i } \cdot \oplus
如果符號間加法 + 運算時間 \leq 乘法符號間 \times 運算的時間
幾乎可說明右式運算量遠大於左式運算量，因為\displaystyle{ \sum^{m}_{i=1}L_i \leq \prod^{m}_{i=1}L_i }
如果把字母符號想成 n \times n 矩陣加法與乘法運算，
則 \oplus = O(n^2) (2層 for 迴圈)
則 \otimes = O(n^3) (3層 for 迴圈)
就會感覺出明顯差異了 !!
現實發展演算法當中，我們大多都會遇到像右式連加的情況，而我們的目標是要去找"完全子圖" (Complete Subbipartite graphs) ，竟量把右式越縮越短，已達到降低計算量的目的。
舉例來說:
給定 AC + BC + DA + BD + AB + B^2
我們可以定義集合 V = \{ A,B,C,D \} E = \{(A,C) , (B,C) , (D,A) , (B,D) , (A,B) , (B,C) , (B,B) \}
E \subset V^2
因為乘法加換律，邊沒有方向性， (D,A) = (A,D) 則式子可以想成一個無向圖(但可能有重邊)
可以把邊的集等價寫成 E' = \{ \color{red}{(A,C)} , (B,C) , \color{red}{(A,D)} , \color{red}{(B,D)} , (A,B) , \color{red}{(B,C)} , (B,B) \}
你會發現\color{red}{\text{紅色}}部分可以寫成 Cartesian Product \underbrace{\color{red}{\{A,B\} \times \{C,D\}}}_{\text{complete bipartite}} \subset E'
則一定可以把 complete bipartite 寫成像左式那樣子。
即 \underbrace{\color{red}{\{A,B\} \times \{C,D\}}}_{\text{complete bipartite}} 等價於 (A+B) \times (C+D)，
於是我們可以把式子化簡成 AC + BC + DA + BD + AB + B^2 = (A+B) \times (C+D) + AB +B^2 你還可以持續化簡下去 !!
所以如何算得更快相當於如何有效率把知道的邊塗成紅色囉 !!
(應用1)
矩陣快速乘法有名的 Strassen algorithm O(n^{2.8})，也是有用到分配律+"線性組合"的精神，而且連矩陣(字母)本身的 size 也有考慮到 !!
(應用2)
多項式的效率計算 Horner's Method
計算時間要滿足以下式才叫做優化 !!
\text{Detect Bipartite Subgraphs} + \text{Compute Reduced Form} \leq \text{Compute Original Form}
[尋找遞迴式的重要]
先複習一下 n個數加總
S_n = \sum_{i=1}^{n}{X_i}
會發現如果要計算 S_n 以上式必須要知道 X_1,.....X_n 的值，還要做 n-1 次運算，多記憶 n 個數。抽象來說可以寫成
\left\{\begin{array}{l} S_1 = Need(X_1) \\ S_2 = Need(X_1,X_2) \\ ... \\ S_n = Need(X_1,X_2,....X_n) \end{array}\right.
註 : 有名的線性方程組，高斯消去法事實上也是把 Ax =b 化簡成如上的三角系統，詳細可以查詢關鍵字 (Back Substitution)
但如果寫成遞迴式 S_i = S_{i-1} + {X_i} \quad i = 2 , 3 , .... , 其中 S_1 = X_1
則我們可以把系統寫成以下這樣，不僅可以降低運算量，而且只要存 1-2 個數，不用記得以前的量
\begin{array}{l} S_i = NeedRecursive(X_i,S_{i-1}) \end{array}
註:如果把 S_i 想成 State Space，抽象來說類似 Markov Chain 的概念(S_{i} 的值只跟上一個S_{i-1}有關係) !!
這也是我們熟知的加總演算法:
###############################
S \leftarrow 0
For i = 1 to n
\quad S \leftarrow (S + X_i )
EndFor
###############################
研究經驗: 日常生活大多問題為不同維度的加總量，
例如 : 平均每天餐廳總共來了 n 個人的機率為 p_n 付的錢分別為 X_1,.....X_n
聯合機率密度函數(joint pdf)為 f_{n}(x_1,x_2,....x_n)
則要計算每天平均期望收益 (Random Sum) 為
\sum_{n \in [1,\infty) }p_{n} \underbrace{\left\{ \underbrace{\iiint}_{n\text{重積分}}\left[\sum^{n}_{i=1}x_i\right] \cdot f_{n}(x_1,x_2,...,x_n)\underbrace{\left(\prod^{n}_{i=1}dx_i \right)}_{\text{積分尾巴}} \right\}}_{ n \text{維量}}
可以把這個n重積分量寫成類似上面的記號
\sum_{n \in [1,\infty) }p_{n} Need(x_1,x_2,...x_n)
會發現 n重積分在數值運算上非常昂貴，尋找 NeedRecursive(x_i , S_{i-1}) 即 f_i(x_1,....x_i) 與 f_{i-1}(x_1,...,x_{i-1})) 的遞迴關係是非常重要的，即 f_{i}= NeedRecursive(x_i,f_{i-1})，電腦計算上才會真正有效率與實現 !!
[尋找變換與反變換，homomorphism]
工程學上著名的變換 Fourier / Laplace Transform ，例如卷積運算
\mathcal{F}(f \ast g) (x) := \mathcal{F}\left\{\int_{\tau \in \mathbb{R}} f(\tau) g(x-\tau)\right\} = \mathcal{F}(f )(x) \cdot \mathcal{F}(g)(x)
我們可以寫成 (f \ast g) = \mathcal{F}^{-1}(\mathcal{F}(f ) \cdot \mathcal{F}(g) )
你會發現卷積計算很昂貴，但是你可以透過已知的變換到代數運算系統(乘法)
註: Fourier / Laplace 類似把微積分(昂貴的運算)變成代數運算(便宜的運算) !! 計算完之後再做反轉換回來 !!
這背後抽象的邏輯即為同態 homomorphism 。
假如給一個運算序列 \{x_1,x_2,....,x_n \} ，以及初始值 s_0 ，定義二元運算子 \ast
則n次運算過程類似遞迴式有 s_i = s_{i-1} \ast x_{i} \quad i=1,2,...n
但今天我找到一個很便宜的轉換 \mathrm{T} ，以及反轉換 \mathrm{T}^{-1} ，甚至找到另一個運算子 + 使得滿足同態 homomorphism
T(y \ast z) = T(y) + T(z)
則要求得 s_n 可以有昂貴的運算 [ n次 \ast 計算 ]
或是便宜的運算 [ n+1 次 T 轉換 + n 次 " + " 運算 + 1 次 T^{-1} 轉換 ]
如下式:
\overbrace{ \left\{.[(s_0 \ast x_1) \ast x_2 ] .... \right\} \ast x_n }^{\text{昂貴的運算}} = s_n = T^{-1} \overbrace{\left( \left\{ ...[\left(T(s_0) + T(x_1)\right) + T(x_2) ] .... \right\} + T(x_n) \right)}^{\text{便宜的運算}}
現實類比 :
例如: 旅行台灣到美國， \ast 運算相當於坐"船" ， + 運算相當於坐"飛機"，如何起飛與降落，相當於找 T , T^{-1}
[小結]
由於經典優化的演算法很多，但是都尚未提到一些叫直覺的概念，本文列舉一些筆者覺得很重要又好解釋的，當然還有一些經典的優化概念，如平行運算與排程(scheduling)，二分法 binary search ， bisection method 。 Heap 資料結構計算 max , min 。尋找子結構相似原理運用在快速傅立葉轉換(FFT)等等，日後再分享給讀者 !!
[利用分配律尋找完全多分圖]
相信大家都知道加法(+) ，乘法(\times) 分配律的概念，複習一下
(A+B)\times (C+D) =A \times C + B \times C + A \times D + B \times D
左式推廣我們可以寫成
\underbrace{(A_1+A_2+....+A_{L_1})}_{\text{第一組}}\times \underbrace{(B_1+B_2+....+B_{L_2})}_{\text{第二組}} \times ... \times \underbrace{( ... )}_{\text{第 $m$ 組}}
每一組 有L_{i} 個元素，總共有 L 個元素(字母)
而且每一組有 L_{i} -1 個加法，總共就有 \displaystyle{\sum^{m}_{i=1}(L_i - 1) = L - m } \text{ 個加法}
由於每一組中間穿叉乘法，有 m-1 個乘法。我們分別把加法，乘法個數記做 ~ \otimes , \oplus，所以左式總共的運算數為
\text{左式運算量 = } (m-1) \cdot \otimes + (L-m) \cdot \oplus
右式完全展開，非常多項，要完整寫出來並非容易的事，但是我們知道它應該是長這樣
(\text{第一組連乘}) + (\text{第二組連乘} ) + (\text{第三組連乘} ) + ........
至於究竟有幾組連乘呢 ??
答案是 \displaystyle{ \prod^{m}_{i=1}L_i } 組，而每一組中間穿叉 L_i -1 乘法
右式總運算量為
\text{右式運算量 = } (L-m)\cdot \otimes + \displaystyle{ \prod^{m}_{i=1}L_i } \cdot \oplus
如果符號間加法 + 運算時間 \leq 乘法符號間 \times 運算的時間
幾乎可說明右式運算量遠大於左式運算量，因為\displaystyle{ \sum^{m}_{i=1}L_i \leq \prod^{m}_{i=1}L_i }
如果把字母符號想成 n \times n 矩陣加法與乘法運算，
則 \oplus = O(n^2) (2層 for 迴圈)
則 \otimes = O(n^3) (3層 for 迴圈)
就會感覺出明顯差異了 !!
現實發展演算法當中，我們大多都會遇到像右式連加的情況，而我們的目標是要去找"完全子圖" (Complete Subbipartite graphs) ，竟量把右式越縮越短，已達到降低計算量的目的。
舉例來說:
給定 AC + BC + DA + BD + AB + B^2
我們可以定義集合 V = \{ A,B,C,D \} E = \{(A,C) , (B,C) , (D,A) , (B,D) , (A,B) , (B,C) , (B,B) \}
E \subset V^2
因為乘法加換律，邊沒有方向性， (D,A) = (A,D) 則式子可以想成一個無向圖(但可能有重邊)
可以把邊的集等價寫成 E' = \{ \color{red}{(A,C)} , (B,C) , \color{red}{(A,D)} , \color{red}{(B,D)} , (A,B) , \color{red}{(B,C)} , (B,B) \}
你會發現\color{red}{\text{紅色}}部分可以寫成 Cartesian Product \underbrace{\color{red}{\{A,B\} \times \{C,D\}}}_{\text{complete bipartite}} \subset E'
則一定可以把 complete bipartite 寫成像左式那樣子。
即 \underbrace{\color{red}{\{A,B\} \times \{C,D\}}}_{\text{complete bipartite}} 等價於 (A+B) \times (C+D)，
於是我們可以把式子化簡成 AC + BC + DA + BD + AB + B^2 = (A+B) \times (C+D) + AB +B^2 你還可以持續化簡下去 !!
所以如何算得更快相當於如何有效率把知道的邊塗成紅色囉 !!
(應用1)
矩陣快速乘法有名的 Strassen algorithm O(n^{2.8})，也是有用到分配律+"線性組合"的精神，而且連矩陣(字母)本身的 size 也有考慮到 !!
(應用2)
多項式的效率計算 Horner's Method
計算時間要滿足以下式才叫做優化 !!
\text{Detect Bipartite Subgraphs} + \text{Compute Reduced Form} \leq \text{Compute Original Form}
[尋找遞迴式的重要]
先複習一下 n個數加總
S_n = \sum_{i=1}^{n}{X_i}
會發現如果要計算 S_n 以上式必須要知道 X_1,.....X_n 的值，還要做 n-1 次運算，多記憶 n 個數。抽象來說可以寫成
\left\{\begin{array}{l} S_1 = Need(X_1) \\ S_2 = Need(X_1,X_2) \\ ... \\ S_n = Need(X_1,X_2,....X_n) \end{array}\right.
註 : 有名的線性方程組，高斯消去法事實上也是把 Ax =b 化簡成如上的三角系統，詳細可以查詢關鍵字 (Back Substitution)
但如果寫成遞迴式 S_i = S_{i-1} + {X_i} \quad i = 2 , 3 , .... , 其中 S_1 = X_1
則我們可以把系統寫成以下這樣，不僅可以降低運算量，而且只要存 1-2 個數，不用記得以前的量
\begin{array}{l} S_i = NeedRecursive(X_i,S_{i-1}) \end{array}
註:如果把 S_i 想成 State Space，抽象來說類似 Markov Chain 的概念(S_{i} 的值只跟上一個S_{i-1}有關係) !!
這也是我們熟知的加總演算法:
###############################
S \leftarrow 0
For i = 1 to n
\quad S \leftarrow (S + X_i )
EndFor
###############################
研究經驗: 日常生活大多問題為不同維度的加總量，
例如 : 平均每天餐廳總共來了 n 個人的機率為 p_n 付的錢分別為 X_1,.....X_n
聯合機率密度函數(joint pdf)為 f_{n}(x_1,x_2,....x_n)
則要計算每天平均期望收益 (Random Sum) 為
\sum_{n \in [1,\infty) }p_{n} \underbrace{\left\{ \underbrace{\iiint}_{n\text{重積分}}\left[\sum^{n}_{i=1}x_i\right] \cdot f_{n}(x_1,x_2,...,x_n)\underbrace{\left(\prod^{n}_{i=1}dx_i \right)}_{\text{積分尾巴}} \right\}}_{ n \text{維量}}
可以把這個n重積分量寫成類似上面的記號
\sum_{n \in [1,\infty) }p_{n} Need(x_1,x_2,...x_n)
會發現 n重積分在數值運算上非常昂貴，尋找 NeedRecursive(x_i , S_{i-1}) 即 f_i(x_1,....x_i) 與 f_{i-1}(x_1,...,x_{i-1})) 的遞迴關係是非常重要的，即 f_{i}= NeedRecursive(x_i,f_{i-1})，電腦計算上才會真正有效率與實現 !!
[尋找變換與反變換，homomorphism]
工程學上著名的變換 Fourier / Laplace Transform ，例如卷積運算
\mathcal{F}(f \ast g) (x) := \mathcal{F}\left\{\int_{\tau \in \mathbb{R}} f(\tau) g(x-\tau)\right\} = \mathcal{F}(f )(x) \cdot \mathcal{F}(g)(x)
我們可以寫成 (f \ast g) = \mathcal{F}^{-1}(\mathcal{F}(f ) \cdot \mathcal{F}(g) )
你會發現卷積計算很昂貴，但是你可以透過已知的變換到代數運算系統(乘法)
註: Fourier / Laplace 類似把微積分(昂貴的運算)變成代數運算(便宜的運算) !! 計算完之後再做反轉換回來 !!
這背後抽象的邏輯即為同態 homomorphism 。
假如給一個運算序列 \{x_1,x_2,....,x_n \} ，以及初始值 s_0 ，定義二元運算子 \ast
則n次運算過程類似遞迴式有 s_i = s_{i-1} \ast x_{i} \quad i=1,2,...n
但今天我找到一個很便宜的轉換 \mathrm{T} ，以及反轉換 \mathrm{T}^{-1} ，甚至找到另一個運算子 + 使得滿足同態 homomorphism
T(y \ast z) = T(y) + T(z)
則要求得 s_n 可以有昂貴的運算 [ n次 \ast 計算 ]
或是便宜的運算 [ n+1 次 T 轉換 + n 次 " + " 運算 + 1 次 T^{-1} 轉換 ]
如下式:
\overbrace{ \left\{.[(s_0 \ast x_1) \ast x_2 ] .... \right\} \ast x_n }^{\text{昂貴的運算}} = s_n = T^{-1} \overbrace{\left( \left\{ ...[\left(T(s_0) + T(x_1)\right) + T(x_2) ] .... \right\} + T(x_n) \right)}^{\text{便宜的運算}}
現實類比 :
例如: 旅行台灣到美國， \ast 運算相當於坐"船" ， + 運算相當於坐"飛機"，如何起飛與降落，相當於找 T , T^{-1}
[小結]
由於經典優化的演算法很多，但是都尚未提到一些叫直覺的概念，本文列舉一些筆者覺得很重要又好解釋的，當然還有一些經典的優化概念，如平行運算與排程(scheduling)，二分法 binary search ， bisection method 。 Heap 資料結構計算 max , min 。尋找子結構相似原理運用在快速傅立葉轉換(FFT)等等，日後再分享給讀者 !!
[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~]
by Plus & Minus 2018.01
留言
張貼留言