本篇為筆者使用集合論符號，方便抽象推廣化到多維陣列。
======================================
[符號提醒]
由於有些符號有點抽象，為了方便讀者了解，小寫大多為"元素"，大寫大多為"集合"
$\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}})$$
[小結]
筆者嘗試把熟悉的數學運算，方程式，推廣到多維複雜的離散結構，並清楚使用集合論描述其概念，目前也還在研究當中 ~
======================================
[符號提醒]
由於有些符號有點抽象，為了方便讀者了解，小寫大多為"元素"，大寫大多為"集合"
$\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
留言
張貼留言