Processing math: 0%
跳到主要內容

Discovery Of Set Notations & Multidimensional Array Operations

本篇為筆者使用集合論符號，方便抽象推廣化到多維陣列。
======================================
[符號提醒]
由於有些符號有點抽象，為了方便讀者了解，小寫大多為"元素"，大寫大多為"集合"
\prod 代表集合的 Catesian Product , \sum 代表連加，| \cdot | 代表集合元素個數(Cardinality)，符號幾乎不會混用，並注意字母粗體的差別!!


[定義論域]
首先定義下標符號集合 i \in I , 而且給定多維離散結構有限集合 \mathcal{R}_{I}  \subseteq U_{I}
其中 U_{I} 為給定 |I|維座標宇集 u_{I} \in U_{I} = \prod_{i\in I}U_i , 正式定義如下
======================================
[定義整體離散結構]
\mathcal{R}_{I} := \left\{ u_I = \underbrace{(u_i)_{i\in I}}_{|I|\text{dim - tuple}} \in U_{I} \left| u_i \in U_i  , \forall i \in I ,  u_{I} \text{ satisfies something ...} \right. \right \}

[ex1]
關於 \mathcal{R}_{I} 與 depend sets 的例子可以參考這篇
https://discoverforgottenmath.blogspot.tw/2017/08/framework-of-creating-depend-sets-given.html

可以簡記 u_{I} \in \mathcal{R}_{I}
對於每個 i \in I，可以把 u_{I} 寫成 (u_{i},u_{I-\{i\}} ) ,
也可以簡記為 u_{I} = (u_{i},u_{-i} )  (賽局理論表示法)
======================================
[收集出一維結構]
對於每一個維度我們還可以定義  u_i \in \mathcal{R}_{i} := \left\{ u_i \in U_i | \exists u_i \text{ s.t } (u_i , u_{-i}) = u_I \in \mathcal{R}_{I}   \right\}

於是我們有    \mathcal{R}_{I} \subset \underbrace{\prod_{i\in I} \mathcal{R}_{i}}_{\text{利用 $\mathcal{R}_{i}$ 構造出新的小宇集}} \subset U_{I}
======================================
[收集出部分結構]
我們還可以推廣成集合版本 (類似線性規劃 simplex algorithm  basic , non-basic variables 的概念)
令 A,B \subset I ，把 u_{I} = (u_{A},u_{-A}) ，其中 \mathcal{R}_{A} := \{u_{A}  \in U_{A}| \exists u_{A} \text{ s.t }  (u_{A},u_{-A}) \in \mathcal{R}_{I}  \}

同理 :
\mathcal{R}_{B} := \{u_{B}  \in U_{B}| \exists u_{B} \text{ s.t }  (u_{B},u_{-B}) \in \mathcal{R}_{I}  \}

根據之前筆者的 Depend Set 定義 :

  \mathcal{R}_{A|B}(u_B) := \left\{ \overbrace{u_{A} \in \mathcal{R}_{A}}^{\text{collect indexes in }A} | \exists u_A \text{ s.t }  u_{I} =  (u_{A},u_{-A}) = (\underbrace{u_{B}}_{\text{ given } u_B \in \mathcal{R}_{B}},u_{-B}) \in \mathcal{R}_{I}    \right\}(u_{B})


註 : \forall u_B \in \mathcal{R}_{B} , \mathcal{R}_{A|B}(u_B) \subseteq  \mathcal{R}_{A} 為 |A| 維空間
======================================
[分解出整體離散結構]
而且 \mathcal{R}_{I} 可以有 |I|! 種分解方式(層狀結構)

定義 1-1 排列函數 \sigma : \{1,2,...,|I-1|,|I|\} \underset{\text{1-1} }{\longrightarrow} I,即 \sigma_{k}\in I  ,  k \in \mathbb{Z}

而定義以下 Nested Sets
A_0 = \emptyset , A_{1} = \{\sigma_{1}\} , A_{2} =\{\sigma_{1},\sigma_{2} \} ,.....A_{|I|} = I
======================================
則給定 \sigma \in \Sigma^{|I|}(Permutation) 下 ，我們可以了解  \mathcal{R}_{I} 的長相
\mathcal{R}_{I} :=  \underbrace{\prod^{|I|}_{k=1}\mathcal{R}_{\{\sigma_{k}\}|A_{k-1}}(u_{A_{k-1}})}_{\text{given  $\sigma$ }}   

註:  \mathcal{R}_{\{\sigma_1\}|A_0}(u_{A_0}) = \mathcal{R}_{\{\sigma_1\}|\emptyset}(u_{\emptyset}) = \mathcal{R}_{\sigma_1}   

==============================================================
[定義多維陣列]
一樣考慮  A \subset I ，我們可以定義多維|A|維陣列

  X_A : \mathcal{R}_{A} \longrightarrow  \mathbb{R} \quad X_A(u_A) \in \mathbb{R}

如果類比我們熟悉的矩陣寫法，可以寫成
  X_A = \left[  X_A(u_A) \right]_{u_A \in \mathcal{R}_A}

其中若 |A| = 0 (A = \emptyset)即為我們熟知的 value
             |A| = 1 即為我們熟知的 sparse vector
             |A| = 2 即為我們熟知的 sparse matrix
             |A| > 2 即為我們熟知的 sparse tensor (sparse multidimensional array )
==============================================================
[多維 Summation 關係]
給定互斥集合 A , B  \in I , 定義

  X_A(u_A)  := \sum_{u_B \in \mathcal{R}_{B|A}(u_A)} X_{A \cup B} (u_A,u_B)

抽象一點可以寫成
X_{A} := \sum_{B|A} X_{A\cup B} 
===========================================================
程式虛擬碼或許比較好理解可以寫成
For u_A \in \mathcal{R}_{A}
       X_{A}(u_A) \leftarrow 0
       For u_B \in \mathcal{R}_{B|A}(u_A)
             X_{A}(u_A) \leftarrow X_{A}(u_A)  + X_{A \cup B} (u_A,u_B)
       EndFor
EndFor
===========================================================
根據 Depend Set 拆解可以寫成  (given \sigma \in \Sigma^{|B|})

X_A(u_A)  :=  \underbrace{\sum_{u_{b_1}}\sum_{u_{b_2}}...\sum_{u_{b_{|B|}}}}_{\displaystyle{\mathcal{R}_{B}=\prod^{|B|}_{k=1} \mathcal{R}_{\{b_k\}|B_{k-1}}(u_{B_{k-1}})}}X_{A\cup B}(u_A, \underbrace{u_{b_1},...,u_{b_{|B|}}}_{u_{B}}) 

其中   B:= \{b_1,.....b_{|B|} \} , B_k :=\{b_1,...,b_k \} , u_{b_k} \in \mathcal{R}_{\{b_k\}|B_{k-1}}(u_{B_{k-1}})

[ex2]
關於 Summation 的現實概念可參考
https://discoverforgottenmath.blogspot.tw/2017/12/set-notation-in-real-life.html


以下是筆者自行定義的運算，還不確定是否跟 tensor 運算類似 !!
[*抽象乘法*]
考慮 A , B \subset I ，但 A\cap B \neq \emptyset， 兩個不同維度多維陣列 X_{A}，Y_{B}，定義域分別為 \mathcal{R}_{A}, \mathcal{R}_{B}
[Remark :  |A\cup B| = |A\setminus B| +  |A\cap B|  +  |B\setminus A|    ]
則定義廣義矩陣乘法 :
[XY]_{A\cup B \setminus A\cap B}(\color{blue}{u_{A\setminus B}},\color{green}{u_{B\setminus A}} ) := \sum_{\color{red}{u_{A\cap B}} \in \mathcal{R}_{A\cap B | A\cup B \setminus A\cap B }} X_{A}(\color{blue}{u_{A\setminus B}},\color{red}{u_{A\cap B}}) \cdot Y_{B}(\color{red}{u_{A\cap B}},\color{green}{u_{B\setminus A}})


以下舉例子套用上面的理論 !!
[二維的例子]   Sparse Matrix 乘法
令兩個矩陣  \mathbf{A} =\left(a_{\bf ij}\right) = m \times n \text{ matrix } , \mathbf{B} =\left(b_{\bf jk}\right) = n \times r \text{ matrix }
很明顯我們可以定義  I := \{ \bf{i,j,k}\}  , u_I = ({\bf{i,j,k}}) \in  U_I = [1,m]_{\mathbb{Z}} \times [1,n]_{\mathbb{Z}} \times [1,r]_{\mathbb{Z}}

註: 我們把 u_i 記做 i 符號本身

根據稀疏矩陣，不存 0 ，我們可以定義 \bar{\mathcal{R}}_{A}:= \{ ({\bf{i,j}}) | a_{\bf ij} \neq 0 \} ,\bar{\mathcal{R}_{B}}:= \{ ({\bf{j,k}}) | b_{\bf jk} \neq 0   \} 

則我們可以構造出 \mathcal{R}_{I} := \{ ({\bf{i,j,k}}) |   {\bf (i,j)} \in \bar{\mathcal{R}_{A}} , {\bf(j,k)} \in \bar{\mathcal{R}_{B}}  \text{ both exists and share same ${\bf j}$ }  \}

注意 : 仔細思考會發現  \mathcal{R}_{A}   \neq\bar{\mathcal{R}}_{A} 事實上是 \mathcal{R}_{A}   \subset \bar{\mathcal{R}}_{A}

套用集合符號
A =  \{{\bf i,j}\} , B = \{{\bf j,k}\} ,A\cap B = \{{\bf j}\} ,A\setminus B = \{{\bf i}\} ,B\setminus A = \{{\bf k}\}


而且
\mathcal{R}_{A\cap B} = \left\{{\bf j} \in [1,n]_{\mathbb{Z}}| \exists {\bf j} \text{ s.t } ({\bf{i,j,k}})\in \mathcal{R}_{I} \right\}


所以矩陣乘法為 \mathbf{A}\mathbf{B}({\bf i} , {\bf k}) = \sum_{j \in \mathcal{R}_{A\cap B}}  \mathbf{A}({\bf i,j}) \cdot \mathbf{B}({\bf j,k})  \quad  \forall  ({\bf i,k}) \in \mathcal{R}_{A\cup B \setminus A\cap B}

筆者這邊是推廣它的概念最後變成上面的

[XY]_{A\cup B \setminus A\cap B}(\color{blue}{u_{A\setminus B}},\color{green}{u_{B\setminus A}} ) := \sum_{\color{red}{u_{A\cap B}} \in \mathcal{R}_{A\cap B | A\cup B \setminus A\cap B }} X_{A}(\color{blue}{u_{A\setminus B}},\color{red}{u_{A\cap B}}) \cdot Y_{B}(\color{red}{u_{A\cap B}},\color{green}{u_{B\setminus A}})

[小結]
筆者嘗試把熟悉的數學運算，方程式，推廣到多維複雜的離散結構，並清楚使用集合論描述其概念，目前也還在研究當中 ~

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









留言

張貼留言

這個網誌中的熱門文章

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...
張貼留言
閱讀完整內容

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...
張貼留言
閱讀完整內容

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)\...
張貼留言
閱讀完整內容