本文介紹筆者自己定義的名詞 : Merge Encoding ，或許有別的學術名詞 !! 數學概念簡單易懂，用途方便理解集合論，機率論，壓縮紀錄大量的元素等等 :)
在數學上，我們習慣會用 $\{0,1\} = \{ False , True \}$，而且日常生活經驗常構造出高維度子集合
$$ s \in S \subseteq \{0,1\}^{n} $$
====================================================
例如 : $n = 3$ 長相大概像這樣 $$ s \equiv (s_1,s_2,s_3) \in S = \{(0,0,1), (1,0,1),.....\} \subseteq \{0,1\}^3$$
====================================================
很明顯 $|S| \leq 2^{n}$，而且 $$\bigwedge_{s \in S}\bigg(\sum_{k=1}^{n} s_k \in [0,n]_{\mathbb{Z}} \bigg)$$
可以把 $n$ 想成物件的集合個數 $|K|$ ，$K$ 為物件集，則 $S$ 相當於選取哪些物件可能的組合，類似背包問題(knapsack problem)的概念。
=====================================================
例如: $(0,1,1)$ 代表選第2個與第3個物件
=====================================================
今想要表達一個物件 $k \in K$ 在集合$S$是可有可無的概念，也就是 $$(s_{k},s_{-k}) , (\bar{s_k},s_{-k}) \in S$$
其中
$$\bar{s_k} = \left\{ \begin{array}{ccc} 1 & \text{if } & s_k = 0 \\ 0 & \text{if } & s_k =1 \\ \end{array} \right. \quad , \quad s_{-k} \equiv \underbrace{(s_{k'})_{k' \in K-\{k\}}}_{\text{向量}} $$
於是可以使用新的數字 $2$ 來表達此概念 :) $2 \equiv \{0,1\}$
定義 MergeEncoding , $$(s_{k},s_{-k}) \text{ or } (\bar{s_{k}},s_{-k}) \equiv (2,s_{-k})$$
====================================================
例如 : $S = \{ (0,1,\color{red}{1}), (0,1,\color{red}{0})\} \equiv \{ (0,1,\color{red}{\{0,1\}})\} \equiv \{ (0,1,{\color{red}2}) \}$
====================================================
所以任何 $S \subseteq \{0,1\}^{|K|} $ ，都存在 $S' \subset \{0,1,2 \}^{|K|}$
注意: Merge Encoding 不是函數，$S' \in MergeEncoding(S)$，但是 preimage 是一個函數 !! $InverseMergeEncoding(S') = S$
白話來說 : 給一個 $S$ 可能有很多種 $S'$ 的表示，給一個 $S'$ 只會有唯一的 $S$ !!
====================================================
例子[*]:
$$ S = \{ (1,0,0) , (1,1,0) , (0,1,1) , (1,1,1) \} \equiv \underbrace{\{ (1,0,0) , (1,1,2) , (0,1,1) \}}_{S'_1} \equiv \underbrace{\{ (1,2,0) ,(2,1,1) \}}_{S'_2} $$
====================================================
有了 Merge Encoding 以後，就可以拿來跟代數意義，集合論/機率論結合
[*] 代數意義: 英文大寫 $ = 1$ ，英文小寫 $ = 0$
$$Abc + ABc + aBC + ABC = Abc + AB(C+c) +aBC = A(B+b)c + (A+a) BC $$
就是分配律啦 ~~ ，項數越少，計算量就越少，如何給定 $S$ 快速找到元素最少的 Merge Encoding $S^{*} := \underset{S' \in MergeEncoding(S)}{\text{argmin } |S'| }$ 是重要的問題 !!
集合論 :
給定一些集合 $\Omega_k$，定義 $$ \bigwedge_{k \in K} \bigg( s_k = 1 \Longleftrightarrow \omega \in \Omega_k \bigg) $$
於是 $\Omega_{k} \equiv (\overbrace{1}^{s_k},\overbrace{2,...,2}^{s_{-k}})$
==========================================================
例如 : $|K| = 2$
$\Omega_{1} \cap \Omega_{2} \equiv (1,1)$
$\Omega_1 \setminus \Omega_2 \equiv \Omega_{1} \cap \bar{\Omega_{2}} \equiv (1,0)$
$\Omega_2 \setminus \Omega_1 \equiv \bar{\Omega_{1}} \cap \Omega_{2} \equiv (0,1)$
$\Omega_{1} \equiv (1,2)$
$\Omega_{2} \equiv (2,1)$
$\Omega_{1} \cup \Omega_{2} \equiv \{(1,1),(1,0),(0,1) \} $
全空間 $\equiv \{ (2,2)\}$
==========================================================
機率論:
$P(\Omega_{1} \cap \Omega_{2}) \equiv p_{11}$
$P(\Omega_1 \setminus \Omega_2) \equiv P(\Omega_{1} \cap \bar{\Omega_{2}}) = p_{10}$
$P(\Omega_2 \setminus \Omega_1) \equiv P(\bar{\Omega_{1}} \cap \Omega_{2}) = p_{01}$
$P(\Omega_{1}) = p_{12} = p_{10} + p_{11}$
$P(\Omega_{2}) = p_{21} = p_{01} + p_{11}$
$P(\Omega_{1} \cup \Omega_{2}) = p_{10} + p_{11} + p_{01} = p_{12} + p_{01} = p_{21} + p_{10} = p_{22} - p_{00} $
$P(全空間) = p_{22} =1$
[檢驗 $S' \equiv S$]
有個必要條件
也就是把 $2$ 全部展開後的元素個數要跟 $|S|$ 相等
$$ S' \in MergeEncoding(S) \Longrightarrow \sum_{s' \in S'} 2^{\#} = |S| $$
其中 : $$\# := \sum_{k \in K}\color{blue}{\underbrace{[s'_k = 2]}_{\text{Iverson Bracket}}} = 2\text{的個數}$$
例如: 例子[*] 分別為 $1+1+1+1 = 1+2+1 = 2+2 = 4$
[小記]
由於筆者對於數字 $2 \equiv \{0,1\}$ 比較敏感，有了 Merge Encoding，就更能理解$|K|$維度文氏圖，排容原理(inclusion-exclusion principle)的計算，而非透過集合符號 !! 記得口訣 : 看到 $2$ 就可以展開 $0$ 跟 $1$ !!
在數學上，我們習慣會用 $\{0,1\} = \{ False , True \}$，而且日常生活經驗常構造出高維度子集合
$$ s \in S \subseteq \{0,1\}^{n} $$
====================================================
例如 : $n = 3$ 長相大概像這樣 $$ s \equiv (s_1,s_2,s_3) \in S = \{(0,0,1), (1,0,1),.....\} \subseteq \{0,1\}^3$$
====================================================
很明顯 $|S| \leq 2^{n}$，而且 $$\bigwedge_{s \in S}\bigg(\sum_{k=1}^{n} s_k \in [0,n]_{\mathbb{Z}} \bigg)$$
可以把 $n$ 想成物件的集合個數 $|K|$ ，$K$ 為物件集，則 $S$ 相當於選取哪些物件可能的組合，類似背包問題(knapsack problem)的概念。
=====================================================
例如: $(0,1,1)$ 代表選第2個與第3個物件
=====================================================
今想要表達一個物件 $k \in K$ 在集合$S$是可有可無的概念，也就是 $$(s_{k},s_{-k}) , (\bar{s_k},s_{-k}) \in S$$
其中
$$\bar{s_k} = \left\{ \begin{array}{ccc} 1 & \text{if } & s_k = 0 \\ 0 & \text{if } & s_k =1 \\ \end{array} \right. \quad , \quad s_{-k} \equiv \underbrace{(s_{k'})_{k' \in K-\{k\}}}_{\text{向量}} $$
於是可以使用新的數字 $2$ 來表達此概念 :) $2 \equiv \{0,1\}$
定義 MergeEncoding , $$(s_{k},s_{-k}) \text{ or } (\bar{s_{k}},s_{-k}) \equiv (2,s_{-k})$$
====================================================
例如 : $S = \{ (0,1,\color{red}{1}), (0,1,\color{red}{0})\} \equiv \{ (0,1,\color{red}{\{0,1\}})\} \equiv \{ (0,1,{\color{red}2}) \}$
====================================================
所以任何 $S \subseteq \{0,1\}^{|K|} $ ，都存在 $S' \subset \{0,1,2 \}^{|K|}$
注意: Merge Encoding 不是函數，$S' \in MergeEncoding(S)$，但是 preimage 是一個函數 !! $InverseMergeEncoding(S') = S$
白話來說 : 給一個 $S$ 可能有很多種 $S'$ 的表示，給一個 $S'$ 只會有唯一的 $S$ !!
====================================================
例子[*]:
$$ S = \{ (1,0,0) , (1,1,0) , (0,1,1) , (1,1,1) \} \equiv \underbrace{\{ (1,0,0) , (1,1,2) , (0,1,1) \}}_{S'_1} \equiv \underbrace{\{ (1,2,0) ,(2,1,1) \}}_{S'_2} $$
====================================================
有了 Merge Encoding 以後，就可以拿來跟代數意義，集合論/機率論結合
[*] 代數意義: 英文大寫 $ = 1$ ，英文小寫 $ = 0$
$$Abc + ABc + aBC + ABC = Abc + AB(C+c) +aBC = A(B+b)c + (A+a) BC $$
就是分配律啦 ~~ ，項數越少，計算量就越少，如何給定 $S$ 快速找到元素最少的 Merge Encoding $S^{*} := \underset{S' \in MergeEncoding(S)}{\text{argmin } |S'| }$ 是重要的問題 !!
集合論 :
給定一些集合 $\Omega_k$，定義 $$ \bigwedge_{k \in K} \bigg( s_k = 1 \Longleftrightarrow \omega \in \Omega_k \bigg) $$
於是 $\Omega_{k} \equiv (\overbrace{1}^{s_k},\overbrace{2,...,2}^{s_{-k}})$
==========================================================
例如 : $|K| = 2$
$\Omega_{1} \cap \Omega_{2} \equiv (1,1)$
$\Omega_1 \setminus \Omega_2 \equiv \Omega_{1} \cap \bar{\Omega_{2}} \equiv (1,0)$
$\Omega_2 \setminus \Omega_1 \equiv \bar{\Omega_{1}} \cap \Omega_{2} \equiv (0,1)$
$\Omega_{1} \equiv (1,2)$
$\Omega_{2} \equiv (2,1)$
$\Omega_{1} \cup \Omega_{2} \equiv \{(1,1),(1,0),(0,1) \} $
全空間 $\equiv \{ (2,2)\}$
==========================================================
機率論:
$P(\Omega_{1} \cap \Omega_{2}) \equiv p_{11}$
$P(\Omega_1 \setminus \Omega_2) \equiv P(\Omega_{1} \cap \bar{\Omega_{2}}) = p_{10}$
$P(\Omega_2 \setminus \Omega_1) \equiv P(\bar{\Omega_{1}} \cap \Omega_{2}) = p_{01}$
$P(\Omega_{1}) = p_{12} = p_{10} + p_{11}$
$P(\Omega_{2}) = p_{21} = p_{01} + p_{11}$
$P(\Omega_{1} \cup \Omega_{2}) = p_{10} + p_{11} + p_{01} = p_{12} + p_{01} = p_{21} + p_{10} = p_{22} - p_{00} $
$P(全空間) = p_{22} =1$
[檢驗 $S' \equiv S$]
有個必要條件
也就是把 $2$ 全部展開後的元素個數要跟 $|S|$ 相等
$$ S' \in MergeEncoding(S) \Longrightarrow \sum_{s' \in S'} 2^{\#} = |S| $$
其中 : $$\# := \sum_{k \in K}\color{blue}{\underbrace{[s'_k = 2]}_{\text{Iverson Bracket}}} = 2\text{的個數}$$
例如: 例子[*] 分別為 $1+1+1+1 = 1+2+1 = 2+2 = 4$
[小記]
由於筆者對於數字 $2 \equiv \{0,1\}$ 比較敏感，有了 Merge Encoding，就更能理解$|K|$維度文氏圖，排容原理(inclusion-exclusion principle)的計算，而非透過集合符號 !! 記得口訣 : 看到 $2$ 就可以展開 $0$ 跟 $1$ !!
[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~]
by Plus & Minus 2018.07
留言
張貼留言