Processing math: 0%
跳到主要內容

Efficient Way From Events To Disjoint Events



本文說明機率論如何在給定機率事件(Events) 如何轉成互斥機率事件(Disjoint Events) 的一些方法

[機率論複習/符號定義]
令 \omega \in \Omega 為樣本點(sample)，樣本空間(sample space)。以及已經定義的(pre-defined)一些事件集 (Events) e \in E ，與每個事件 e 所對應的樣本點集 \omega \in \Omega_{e}
當隨機發生時，相當於從樣本空間 \Omega 根據機率分布 p_{\Omega} 而產出一個元素 \omega_{*} 
當 \omega_{*} \in \Omega_{e}  我們說事件 e 發生，反之沒發生，發生的機率為 p_{e}:=\sum_{\omega \in \Omega_{e}}p_{\omega}

註: 現實生活中，事件 e 的樣本集通常是 \{0,1\}^{n} 的子集, n 可能為"實驗次數"或是"黑箱個數"
\bigwedge_{e \in E} \left( \Omega_{e} \subseteq \{0,1\}^{n} \right)

[問題定義]
如何給定 \Omega_{E} :=  \{\Omega_{e}\}_{e \in E} 找到互斥事件集 E^{disjoint} 與其樣本集
\Omega_{E^{disjoint}}:= \{\Omega_{e} \}_{e \in E^{disjoint}} 而且   \bigwedge_{e \in E} \bigg( p_{e} \in Span \bigg\{ p_{e'}: e'\in E^{disjoint} \bigg\} \bigg)

[文氏圖交集想法]
很明顯有一個解 \Omega_{E^{disjoint}} =  \bigg\{\displaystyle{ \bigcap_{e \in S}\Omega_{e} \cap \bigcap_{e \in E\setminus S}\bar{\Omega}_{e } : S \subseteq E    }  \bigg\}，也就是把文氏圖切成 2^{|E|} 塊。但現實生活中，如果 |E| = 50，則要做 2^{50}-1次集合組合間交集運算，而且很多"塊"可能都是空集合，稀疏的(Sparse)，實作上可能不能直接這樣思考!!

[從樣本點角度出發]
可以先把 \bigg\{ \Omega_{e}: e \in E \bigg\} 做自然對偶對應 (Natural Dual Correspondence) (筆者自己的用詞) ，產生 \color{red}{\bigg\{ E_{\omega} :   \omega \in  \displaystyle{\bigcup_{e \in E}\Omega_{e}} \bigg\}} ，也就是 
  \bigwedge_{e\in E} \bigwedge_{\omega \in \Omega} \bigg(  \omega \in \Omega_{e} \Longleftrightarrow e \in  \color{red}{E_{\omega}}        \bigg)

計算複雜度只要 \displaystyle{O\left(\sum_{e\in E}|\Omega_{e}|\right)}
白話來說，我們把焦點從 \color{blue}{"事件 e  發生所需要的樣本點 \omega"} 轉移到 \color{green}{"樣本點 \omega 出現時，哪些事件  e  會發生"}
另外考慮 E_{\omega} 上的事件們 \left\{\begin{array}{c}e \in E_{\omega}  \Longrightarrow \omega \in \Omega_{e} \\ e' \in E_{\omega}  \Longrightarrow \omega \in \Omega_{e}\\  e'' \not\in E_{\omega}  \Longrightarrow \omega \not\in \Omega_{e''}    \\\end{array}\right. \Longrightarrow  \omega \in \Omega_{e}\cap \Omega_{e'} \cap \bar{\Omega}_{e''}
廣義來說 : \omega \in \left(\bigcap_{e \in E_{\omega}} \Omega_{e}\right) \cap \left( \bigcap_{e \in E\setminus E_{\omega}} \bar{\Omega}_{e} \right)
會發現恰好就是文氏圖，2^{|E|}裡"非空"的那一塊，於是我們可以定義集合的集合 \mathcal{C} := \{\underset{=c}{E_{\omega}}\} ，而且很明顯 \mathcal{C} 互斥，以及 \forall e \in E ,  p_{e} \in  Span \bigg\{  p_{c} : c \in \mathcal{C}  \bigg\}
其中 p_{c} := \sum_{\omega \in  \#} p_{\omega} ， \# := \bigg\{\omega' \in \Omega :  E_{\omega'} = \underset{= c}{E_{\omega}}   \bigg\}

[舉例]
假設隨機試驗為丟3次銅板，F為正面，T為反面，定義事件集 e \in E := \{ AM1T, AL1T , E1T,ALLT , ALLF , F1T, C2T \}
以及樣本點集 e : \Omega_{e}
AM1T = At-Most-1-T  : \{FFF,TFF,FTF,FFT\}
AL1T =  At-Least-1-T : \{TFF,FTF,FFT,TTF,FTT,TFT,TTT\}
E1T = Exact-1-T : \{TFF,FFT,FTF\}
ALLT = All-T : \{TTT\}
ALLF = All-F : \{FFF\}
FIT = First-is-T : \{TFF,TTF,TFT,TTT\}
C2T = Consecutive-2-T : \{ FTT,TTF\}

構造出 \omega : E_{\omega}

FTF : \color{red}{\{AL1T,AM1T,E1T\}}
TFF : \{AL1T,AM1T,FIT,E1T\}
FFT : \color{red}{\{AL1T,AM1T,E1T\}}
FFF : \{ALLF,AM1T\}
FTT : \{C2T,AL1T\}
TTF : \{C2T,AL1T,FIT\}
TTT :\{ALLT,AL1T,FIT\}
TFT :\{AL1T,FIT\}

構造出互斥事件群 !! c :  \Omega_{c}
\color{red}{\{AL1T,AM1T,E1T\}} : \{FTF,FFT\}
 \{AL1T,AM1T,FIT,E1T\} : \{TFF\}
 \{ALLF,AM1T\} :  \{FFF\}
\{C2T,AL1T\} : \{FTT\}
 \{C2T,AL1T,FIT\} : \{TTF\}
\{ALLT,AL1T,FIT\} : \{TTT\}
\{AL1T,FIT\} : \{TFT\}
其餘狀況 : \emptyset

[小結]
本文提供一個簡單的方法，從樣本點的對應出發，會比從事件間交集間還來的有效率。


[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~] 
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...
張貼留言
閱讀完整內容

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