跳到主要內容

Efficient Counting Number Of Paths



本文介紹比較有效率計算路徑個數的演算法，以及一些數學概念的整合

[符號定義]
考慮點集 $k \in K = \{1,2,.....|K|\}$ (stages) ，以及每個 stage $k$ 的可能值 $x_k$ 與其空間集 $X_{k}$ (state space)  也就是
$$ \bigwedge_{k \in K}\bigg( x_k \in X_{k} \bigg)$$

另外我們把 $K$ 集定義有序陣列的概念(list,array) !!  $K^{<} := [1,2,3,4,....|K|] , K^{>} := [|K|,....,2,1]$

而現實生活中有許多分類的層狀結構，數學上可寫成
$$ \bigwedge_{k \in K^{<}}\bigg(x_k\in \color{red}{X_{k}(x_{k-1})} \bigg)$$

其中 $\color{red}{X_{k}(x_{k-1})} \subseteq X_{k}$ 為 DependSet 的概念，代表給定 $x_{k-1}$ 下，$X_{k}$ 的可能值，這些 $\color{red}{X_{k}(x_{k-1})}$ 是已經被定義的，而且 $X_{1}(\underset{=\emptyset}{x_0}) \equiv X_{1}$
註: 每個 $X_{k}$ 只跟上一層 $x_{k-1}$ 值有關，而與前幾個值 $x_{k-2},x_{k-3}, ...$ 無關，
即類似馬可夫鍊(Markov Chain)相依，而非路徑相依 (Path-dependent)
==================================
舉例: 生物分類的界門綱目科屬種的概念
可以想成 $X_1 = $ 界 ，$X_2(x_1) = $ 門 ，$X_3(x_2) =  $  綱 ....
==================================
[問題定義]
定義
$$\mathcal{R} :=  X_{1} \times X_{2}(x_1) \times X_3(x_2) .... \times X_{|K|}(x_{|K|-1})   \subseteq  \prod_{ k\in K^{<}} X_{k} $$

今天我們要計算 $\mathcal{R}$ 的個數，即 $|\mathcal{R}|$ ，直覺的概念是窮舉法(Brute & Force) ~ 先選定 $x_1 \in X_1$ ，再選定 $x_2 \in X_2(x_1)$ .... 最後選完 $x_{k} \in X_{k}(x_{k-1})$ ，我們把 $x_{K} = (x_1,x_2,....x_{|K|}) $相當於一條路徑，列入 +1 計算，這可利用深度搜尋演算法(DFS)達到，但是當 $|\mathcal{R}|$ 很大的時候就要數很久，甚至數不完，計算效率應該跟 $|\mathcal{R}|$ 一樣多，計算複雜度可寫為 $$\text{complexity } = O\left(\prod_{k \in K} |X_{k}| \right)$$
但事實上在大多數情況下存在簡單易懂，更快的算法 :D

[遞迴公式推導]
如果仔細把 $|\mathcal{R}|$ 寫開會得到

$$ |\mathcal{R}| =   \sum_{x_K \in \mathcal{R}} 1 = \sum_{x_1\in X_1} \sum_{x_2 \in X_2(x_1)} \sum_{x_3 \in X_3(x_2)} ....\sum_{x_{|K|-1} \in X_{|K|-1}(x_{|K|-2})}\sum_{x_{|K|} \in X_{|K|}(x_{|K|-1})} 1  $$
注意: 請區分符號定義
$X_k$ (state space of stage $k$)
$x_k$(state value of stage $k$)
$x_{K}$ (vector of state values of  all stages $k \in K$)

這時候會發現以下遞迴式跟上面的等價 !!
$$  \bigwedge_{k \in K^{>}} \left[\bigwedge_{x_{k-1} \in X_{k-1}} \bigg( S_{x_{k-1}} :=  \sum_{x_k \in X_{k}(x_{k-1})} S_{x_k} \bigg)  \right]$$
其中 $$\bigwedge_{x_{|K|} \in X_{|K|}} \bigg( S_{x_{|K|}} = 1 \bigg) , S_{x_{0}} \equiv |\mathcal{R}|$$
註: 可以定義 $X_{0} := \{x_0\}$ 為單一虛擬點，彙整所有來自 $X_{1}$的邊 !!

而且會發現遞迴式的本質就是排列組合裡的"加法原理"，而且總共只需要$|K|$次兩層 for 迴圈，外圈掃過 $x_{k-1} \in X_{k-1}$，內圈掃過 $x_{k} \in X_{k}(x_{k-1})$做相加，計算複雜度約為
$$\text{complexity} = O\left(\sum_{k \in K^{<}} |X_{k-1}|\cdot |X_{k}|\right)$$
效率快很多，原因在於有些值已經算好不必每次都鑽到最深層 !! 不過需要多紀錄一些算好的數字，正所謂空間換取時間 !!!
[計算複雜度方程式比較]
如果令 $|K| = 4 $，$a = |X_1|$ , $b = |X_2|$ , $c = |X_3|$ , $d = |X_4|$
則窮舉法類似 $abcd$ ，而優化法類似 $ab+bc+cd$ ，所以在 $a,b,c,d$ 很小的時候不易察覺其差異，甚至可能窮舉法比優化法快，窮舉法需要 "路徑個數"的計算，優化法只需要"邊的個數"計算 !!

[矩陣向量乘法本質]
如果仔細看遞迴式某部分 ~

$$\bigwedge_{x_{k-1} \in X_{k-1}} \bigg( S_{x_{k-1}} :=  \sum_{x_k \in X_{k}(x_{k-1})} S_{x_k} \bigg)$$

改寫成
$$\bigwedge_{x_{k-1} \in X_{k-1}} \bigg( S_{x_{k-1}} :=  \sum_{x_k \in X_{k}} \underbrace{\color{blue}{[x_k \in X_{k}(x_{k-1})]}}_{\text{Iverson bracket}} \cdot S_{x_k} \bigg)  $$

今把 $(S_{x_{k-1}})_{x_{k-1} \in X_{k-1}}$，$(S_{x_k})_{x_k \in X_k}$ 想成向量們，$\color{blue}{[x_k \in X_{k}(x_{k-1})]}$ 想成 0-1 $|X_{k-1}| \times |X_{k}|$ 鄰接矩陣(adjacency matrix) $A_k := [a_{x_{k-1},x_{k}}] =  \color{blue}{[x_k \in X_{k}(x_{k-1})]}$
則我們把原問題可以寫成矩陣的連乘 :D
$$|\mathcal{R}| =  A_{1}  A_{2} ... A_{|K|} \vec{1}$$

[小結]
"算數"/"計數"是數學的初衷，而遞迴的概念，讓我們能夠有更快計算出答案的可能 !! 而且事實上這些遞迴式的精神不僅使用在計算路徑個數，也可使用在機率計算如 Chapman-Kolmogorov equation 與微積分Chain Rule 梯度更新(gradient update) 如:  backpropagation ，詳細日後再寫一篇 !!


[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~] 
by Plus & Minus 2018.07

留言

張貼留言

這個網誌中的熱門文章

Nash Equilibrium & Best Responce Function (BRF) In Continuous Strategies

經濟學重要的賽局理論( Game Theory )領域，用數學描述人與人之間的理性互動，最重要的就是尋找奈許均衡( Nash equilibrium )， 本篇介紹其數學規劃與非線性方程組!!  假設有 $p$ 名玩家(player $i$)，$i=1,2,3,4,5,....p$ ， 正在玩一場遊戲(Game)~~，完全不合作，各自獨立作決策 每個人有決策向量 $x_i \in \Omega_i \subseteq R^{n_i}$ (有$n_i$個決策變數)  定義長向量: $\underbrace{x =  (x_1,x_2,x_3,....x_p)}_{\# \text{ of } \sum^{p}_{i=1}n_i \text{ variables }} \in  \prod^{p}_{i=1} \Omega_i = \Omega $ 對於每個 player $i$ ，長向量可以寫成 $x = (x_i , x_{-i})$ ，$x_{-i}$ 代表其他人(不是 player $i$) 能做的決策向量。 所有人各自作決策後，每個人都會個自的存在報酬效用函數 $f_i (x)  \in \mathbb{R} $ (報酬函數皆為公開已知資訊) 假設每位玩家是理性人(會極大化自己效用) 即 $$\forall i = 1,2,3,4....p \qquad  \underset{x_i \in \Omega_i}{\text{max }}f_i(x)  $$ [註: 如果為合作可視為多目標規劃問題( multiobjective )，即 $x_1,x_2,...x_p$ 可以由領導人一起決定] [註: 如果為合作而且把效用加總，即目標式變成 $\sum_{i=1}^{p} f_i(x)$ ，可能對集體效益有更大的幫助，但是如何分配效益給 ( player $i$ )會是個議題，可以查關鍵字 fair optimization ] 我們可以定義每個 player i 的 Best Response Function (BRF) or Best Reponce Set $S_i(x_{-i}) \subset \Omega_i$ $$  S_i(x...
張貼留言
閱讀完整內容

Linear Regression By Using Linear Programming

當拿到一筆資料準備玩統計，往往會想要做線性迴歸( Linear Regression )，找出一個模型( mathematical model )來解釋變數間的關係，一般都是使用平方距離，但是如果我們採用絕對值距離呢?? 而剛好在工業工程( Industrial Engineering )，作業研究( Operation Research ) 領域，發展成熟的線性規劃( Linear Programming ) 恰好可以來解決，是一個跨領域的應用 !! 已經存在有許多商業或open source 軟體，如: Gurobi ， Cplex ， Xpress ， Mosek ， SCIP  可以輕易求解大型的線性規劃問題。而不僅如此也可以利用整數規劃( Integer Programming )來做特徵選擇 ( Feature Selection )，甚至可以偵測離群值( Detect Outlier ) !! 本文只介紹最小絕對值和，關於 Feature Selection , Detect Outlier 可以參考 Mixed-Integer Linear Programming Robust Regression with Feature Selection , Oleksii Omelchenko , 2010 的論文。 [Data Fitting Problem] 給定$n$筆實數型訓練資料 (training data) $\{(x^{k},y^{k})\}^{n}_{k=1} = \mathcal{D} , x^{k} =(x^{k}_1,x^{k}_2, ... , x^{k}_{p})\in \mathbb{R}^{p}$ , $y^{k} \in \mathbb{R}$ ， 我們目標是想要找到一個函數 $f_{\mathcal{D}} : \mathbb{R}^p \rightarrow \mathbb{R}$ 使得  $\forall x \in \mathbb{R}^{p} , f_{\mathcal{D}}(x) \approx y$ ， 精確來說: $$ \text{Find } f_{\mathcal{D}} \text{ such that } f_{\mathcal{D}}(x)\...
張貼留言
閱讀完整內容

Lattice & Multinomial Theorem

本文介紹格子點(Lattice) 幾何意義與多項式定理(Mutinomial Theorem) 的關係，並可協助我們理解計算一些機率問題。 [符號定義] 非負整數 / 非負實數:  $\mathbb{Z}_{\geq 0} := \{0,1,2,3,4,......\}  \subseteq [0,\infty) =: \mathbb{R}_{\geq 0}$ 離散機率向量:  $$p_{I} := (p_{i})_{i \in I} \text{ s.t } \sum_{i\in I}p_i =1 ，|I|<\infty  $$ 發生事件 $i \in I$ 的累積次數向量: $$ k_{I} := (k_i)_{i \in I} \in \mathbb{Z}^{|I|}_{\geq 0} $$ $\mathbb{Z}^{|I|}_{\geq 0}$ 就是 $|I|$ 維格子點 !! [格子點情境] 出發點定義為 $k^{start}_{I}:= \overbrace{(0,0...,0)}^{|I|}$，今發生一次 $p_{I}$ 分布隨機互斥事件，等價於"點的移動"(state transition)，數學定義如下: $$  \text{Event } i  \text{ happens }  \Longleftrightarrow  \overbrace{(\color{red}{k_i},k_{-i})}^{k^{old}_{I}}  \underset{\text{with probability }p_{i}}{\longrightarrow}   \overbrace{(\color{red}{k_i+1},k_{-i})}^{ k^{new}_{I}}    $$ PS1: 其中  $k_{-i} := (k_{i'})_{i' \in I-\{i\}}$ PS2: 不管怎麼走都在第一象限，也就是只能往右，往上，往高.... 當發生 $n$ 次獨立同分布 $p_{I}$ (iid) 的事件後，所有可能點位置在以下的集合上 $$  S_{n}(\col...
張貼留言
閱讀完整內容