本篇以隨筆平易近人的方式，寫一些如何降低演算法"計算量"的一些核心抽象概念。
[利用分配律尋找完全多分圖]
相信大家都知道加法$(+)$ ，乘法$(\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
留言
張貼留言