跳到主要內容

Some Special Set On Path-Arc Structure

本文是記錄一些使用集合論語言,表達路徑(Path)/線段(Undirected Arc) 組成的關係:
令所有的路徑集為 $p \in P$,所有的線段集 $a \in A$

路徑是由許多線段(無方向性)所組成的,自然存在對應關係 $E \subseteq P\times A$,可使用圖論二分圖描述 $G(P\cup A,E)$
可以定義相依集:$$P_{a}:=\{p\in P : (p,a)\in E \},A_{p}:= \{a\in A :(p,a) \in E \}$$ 
並且滿足以下自然對偶邏輯(Natural Dual Correspondence)
$$ \bigwedge_{(p,a)\in P\times A} \left( p \in P_a  \Longleftrightarrow a \in A_{p}  \right)   $$
如果$X_a$為線段長,則很明顯路徑長可寫為 $$\bigwedge_{p \in P}\left( X_{p}:= X(A_p) = \sum_{a\in A_p} X_{a} \right)$$

路徑長公式可以寫成線性系統 $$ X_{P} := M_{P\times A} X_{A} $$
(其中$X_P$,$X_{A}$ 為向量,$M_{P\times A}$ 為 $0-1$ adjacency sparse  matrix)
由線性系統可以求出反矩陣,而導出 $X_{A}= M^{-1}_{P\times A}X_{P} $)

定義 $p$ 損壞必定影響的路徑集
$$ \bigwedge_{p\in P}\left( P^{\cap}_{p}:= \bigcap_{a\in A_{p}} P_{a} \right) $$
代表只要路徑 $p$ 斷了,則所有路徑 $p' \in P^{\cap}_{p}$ 也必定會斷,($p$是$p'$的一部分)  $$ \bigwedge_{p \in P}\bigwedge_{p' \in P^{\cap}_{p}} \left(A_{p} \subseteq A_{p'}\right)$$

定義 $p$ 損壞可能影響的路徑集

$$ \bigwedge_{p \in P} \left( P^{\cup}_{p}:= \bigcup_{a\in A_{p}}P_{a} \right) $$

也就是兩路徑有部分的線段共同組成 $$  \bigwedge_{p \in P}\bigwedge_{p' \in P^{\cup}_{p}}\left(A_{p} \cap A_{p'} \neq \emptyset\right) $$


定義完全跟 $p$ 無關的路徑集(與 $p$ 獨立) 

$$\bigwedge_{p \in P} \left(P^{\times}_{p}:= P\setminus P^{\cup}_{p}\right) $$
也就是兩路徑沒有共同線段組成
$$  \bigwedge_{p \in P}\bigwedge_{p' \in P^{\times}_{p}}\left(A_{p} \cap A_{p'} = \emptyset\right) $$

給定一些路徑集 $P' \subset P$ ,可以定義必定會經過的線段集
$$A^{kernel}(P'):=\bigcap_{p \in P'} A_{p}   $$


系統核心線段可寫成 
$$ A^{kernel} :=\bigcap_{p \in P}A_{p} $$


[小結]
這些集合口語上很難表達,而本文利用相依集交集聯集來描述,方便讀者能夠正確計算出集合!!

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

留言

這個網誌中的熱門文章

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...

Expected Ratio of n trials & Probability Generating Function

本文介紹如何利用機率母函數(Probability Generating Function) 推導  $\color{red}{獨立n 局期望比例(投資報酬率)的解析式}$,相關概念與延伸問題 [機率情境] 現實生活中,往往是有付出($Paid$) 可能會有回報($Gain$)。 設樣本元/空間記做 $\omega \in \Omega$,$|\Omega|<\infty$,單局發生機率為 $p_{\omega}$ 此時會有產生成對樣本 $(Gain(\omega),Paid(\omega))$。 代表有 $\color{red}{p_{\omega}}$ 機率,你會先付出$\color{blue}{Paid(\omega)} \neq 0$ 元,而最後會回收 $\color{blue}{Gain(\omega)}$ 元 ,當局淨收入為 $Gain(\omega)-Paid(\omega)$,單局投資報酬率為 $\frac{Gain(\omega)}{Paid(\omega)}$ 而單局期望投資報酬率為 $$\sum_{\omega \in \Omega} p_{\omega}\left(\frac{Gain(\omega)}{Paid(\omega)}\right) =:  E\left[\frac{X_i}{Y_i}\right]$$ 其中 $(X_i, Y_i)$ 為隨機變數序對 : (回收值,付出值) $$(X_i,Y_i) \overset{iid}{\in} \bigg\{(Gain(\omega),Paid(\omega))  \bigg\}_{p_{\Omega}=(p_{\omega})}$$ [$n$局期望比例(投資報酬率)] 然而往往會參與 $n$ 局,投資報酬率(隨機變數)為 $ \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}^{n}Y_i} $ ,目標是如何計算出 $E\left[ \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}^{n}Y_i}\right]$  ??,很明顯即使每局是獨立同分布,一般情況下,$$E\left[ \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}...

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)\...