跳到主要內容

How About One-To-Many Function


本文探討數學語言三大基礎概念之一 (邏輯，集合，函數) 的函數 !!
並推廣函數觀念至"一對多"，並定義共同集(common set) 等概念與例子 

[回顧函數定義]
函數是一種對應，給定兩個集合 $X$ , $Y$
$ f : X \longrightarrow Y  $ ，稱 $X$ 為定義域(domain)，$Y$ 為對應域(codomain)
英文定義 :
$(E1)$ For each $x \in X$  there exists "unique" $y \in Y$ such that  $y = f(x)$
符號寫法:
$\forall x \in X \exists ! y \in Y , \text{ s.t } y = f(x)$
資工術語:
key-value ，資料結構裡面的 map data structure

注意: 這邊的 $y$ 是隨著 $x$ 值不同而可能不同($y$ is depend on $x$)，必須要跟下面的意思做區分:
$(E2)$ For all $x \in X$ , there exists "unique common" $y \in Y$ such that  $y = f(x)$，這代表對應到的 "y" 都是一模一樣的。
$(E1)$ 是函數的意思，$(E2)$ 是常數(Constant)函數的意思。

函數也可以想成一條條 if - then 構成(邏輯式展開)
--------------------------------------------------------------------
[Example: 如果令 $X= \{1,2,3\} , Y= \{4,5,6\}$]
$f(1) = 4$    代表  if $X=1$ then $Y=4$
$f(2) = 5$    代表  if $X=2$ then $Y=5$
$f(3) = 5$    代表  if $X=3$ then $Y=5$

而(E2)大概是長這樣
$f(1) = 4$    代表  if $X=1$ then $Y=4$
$f(2) = 4$    代表  if $X=2$ then $Y=4$
$f(3) = 4$    代表  if $X=3$ then $Y=4$
--------------------------------------------------------------------

[可以說的事]
可以定義函數的值域 $Range(f) := \{y\in Y : \exists x \in X \text{ s.t } f(x) = y\}$或寫成 $f(X) \text{ or } Image(f)$ ，很明顯，$f(X)\subseteq Y$
可以定義反映射 Preimage , 給定 $y \in f(X) , f^{-1}(y) := \{x\in X : f(x) = y \}    $

注意: 定義域裡面的每一個 $x$ 都要對應一個 $y$，不能一對無，可以多對一，即 $\forall y \in f(X) ,  |f^{-1}(y)| \geq 1$

注意: 函數$f$ 可以視為把定義域 $X$ 做切割成一塊塊互斥的集合(partitions) ，即 $$ \bigcup^{\text{disjoint}}_{y\in f(X)} f^{-1}(y)  = X$$ ，這在機率論"隨機變數"上是重要的概念!!


如果 $\forall y \in f(X) ,  |f^{-1}(y)| = 1$ 則我們稱函數為 1-1 函數 !!

如果 $f(X) = Y$ 則我們稱函數為 onto 函數 !!

如果一個函數 1-1 又 onto 則我們可以定義反函數，$f^{-1} : Y \rightarrow X$ ，$f^{-1}(y) = x$ ，而且 $f^{-1}(f(x)) = x $

函數我們有時候會簡記成 $y = y(x)$ (在微分方程領域常用) ，$y$ 代表值 ，$y(\cdot)$代表函數，不過簡記容易會有意義上混淆。

如果 $X$ 是一個有限集，我們有時候會寫成下標 $f_x = y$
例如: 實數矩陣 $A = (A_{ij})$  可看成 $ A : I \times J \rightarrow \mathbb{R}$
$I = \{1,2,3,....m\} , J = \{1,2,3,....n\}$

[簡單的假想實驗]
如果你有個黑板上可以畫 $xy$ 平面，畫一條條水平線(跟$x$軸平行)，垂直線(跟$y$軸平行)，隨便在畫一條曲線代表 $f$，如果每一條垂直線都跟曲線$f$ 恰有一交點則我們稱 $f$ 是一個 $x$ 的函數，而此時如果每一條水平線又跟曲線 $f$ 也是恰有一個交點，則我們稱此函數為 1-1 (one-one)

[推廣至一對多]
而在現實生活中，一對多的概念也是非常常見，所以筆者決定定義它
(p.s)在資工資料結構類似 Linked List 的概念或是 C++ 實作的結構 map<T,set<T>>，其中 T 是型別(datatype)，而數學上可以想成圖論(Graph Theory) 的 Directed Bipartite Graph
給定兩個集合 $X$ , $Y$ ，定義函數 $f : X \longrightarrow 2^{Y}$ ，其中 $2^{Y}:= \{S: S \subset Y\}$ 是 PowerSet of $Y$ ，也就是 $f(x)$ 是一個集合 !! ，我們把 $y = f(x)$ 寫成 $y \in f(x)$ !! (點對應到一個集合)，而如果 $\forall x\in X  \quad  |f(x)| = 1$ 就是傳統函數的概念。
而當 $|f(x)| = 1$ 時 $f(x) = \{ y \}$ (單一元素的集合，因為沒得選)，我們可以簡記寫成 $y = f(x)$
註: 是否要允許一對無， $f(x) = \emptyset$，視情況而決定
英文定義 :
For each $x \in X$  there exists  $y \in Y$ such that $y \in f(x)$
[可以說的事]
很自然的我們可以定義 Range $f$
$$f(X):= \bigcup_{x\in X}f(x) \subseteq Y $$
自然如果 $f(X) = Y$ 我們可以說是 $f$ 是 onto
也可以定義 Preimage ，給定 $y \in f(X) , f^{-1}(y) := \{x\in X : y\in f(x) \}$
我們可以定義一個集合 $ G := \{(x,y) :  x \in X ,  y \in f(x)  \} \subseteq X \times Y $
然後可發現 $G$ 也可以用 Preimage 定義，即 $G = \{(x,y) :  y \in f(X) ,  x \in f^{-1}(y)  \} $
代表 $G$ 集合可以有兩種方式描述 !!
-----------------------------------------------------------------
[Example1] 二重積分交換順序的例子  $X = [0,1]$，$Y = [0,1]$，考慮實數函數 $g(x,y)$，然後積分範圍 $G$ 為$x$軸(y=0)跟 $y = x $，$x=1$之間的三角形區域，則 $y \in f(x) = [0,x]$ ，$x\in f^{-1}(y) = [y,1]$ ，註 : $f(X) = Y$
根據微積分 Fubini 定理，我們可以寫成

$$\iint_{G} g(x,y) dA = \underbrace{\int^{1}_{0}\int^{x}_{0} g(x,y) dydx}_{x\in X , y\in f(x)} = \underbrace{\int^{1}_{0}\int^{1}_{y} g(x,y) dxdy}_{y\in Y , x\in f^{-1}(y)} $$
-------------------------------------------------------------------
[Example2]  程式碼掃上三角矩陣(upper triangular matrix)，考慮 $I = \{1,2,3,....n\}， J = \{1,2,3,.....n\}$ 的 $n \times n $ 矩陣 $A_{ij}$ ，則我們只需要印出  $i \leq j $ 的部分，而且 $f(i) = [i,n]_{\mathbb{N}}$，$ f^{-1}(j) = [1,j]_{\mathbb{N}}$ $f(I) = J$

為了更方便理解，寫成 $J_i = f(i)$，$I_j = f^{-1}(j)$
則掃矩陣我們可以用以下三種方式
++++++++++++++++++++++++++++++++++++
$(C1)$ 全掃型 $I \times J$
For  $i \in I$
$\qquad$ For $j \in J$
$\qquad$$\qquad$ if $(i\leq j)$ Print $A_{ij}$
$\qquad$ EndFor
EndFor
++++++++++++++++++++++++++++++++++++
$(C2)$ 先掃 $I$
For  $i \in I$
$\qquad$ For $j \in J_i$
$\qquad$$\qquad$ Print $A_{ij}$
$\qquad$ EndFor
EndFor
++++++++++++++++++++++++++++++++++++
$(C3)$ 先掃 $J$
For  $j \in J$
$\qquad$ For $i \in I_j$
$\qquad$$\qquad$ Print $A_{ij}$
$\qquad$ EndFor
EndFor
++++++++++++++++++++++++++++++++++++
其中 $(C2),(C3)$ 比 $(C1)$ 省了一半時間左右
註:則符號上可以記做 $G = I \times J_i = I_j \times  J$ (這是筆者的寫法)
註:也可以寫成這兩個等式  :
$\left\{\begin{array}{c} \bigcup_{i\in I} J_i  = J \\  \bigcup_{j\in J}I_j =I \\ \end{array}\right.$
-------------------------------------------------------------------
令 $S \subset X$  我們可以定義
[sub-image] $$ f(S) := \bigcup_{x\in S} f(x)$$
[common set]  $$Com(f) := \bigcap_{x\in X} f(x)  $$
[sub-common set] $$Com(f,S) := \bigcap_{x\in S} f(x)  $$

如果$Com(f) \neq \emptyset $，common set 是重要的集合，因為$y$ 與 $x$ 無關
英文定義是 $\forall y \in Com(f) , y \text{ is  constant respect to } x$

----------------------------------------------------------------------------------
[Example]  ${\displaystyle{\lim_{n \rightarrow \infty }g_n(t)} = g(t)} $ ,  $t \in \mathbb{R}$
逐點收斂(pointwise-convergence) and 均勻收斂(uniform convergence)
詳細定義可參考高等微積分(advanced calculus) 或是實分析(real analysis)相關領域
我們可以定義 $f : \mathbb{R}^{+}\times \mathbb{R} \longrightarrow 2^{\mathbb{N}}$
$$ N \in f(\epsilon,t) \Longleftrightarrow  \text{if } n > N \text{ then }  |g_n(t) - g(t)| < \epsilon $$
或是以下的定義
$$ f(\epsilon,t) := \{N \in \mathbb{N}:  n > N \Rightarrow |g_n(t) - g(t)| < \epsilon  \}$$
(D1) 則 pointwise convergence 代表 $$\forall (\epsilon,t) \in  \mathbb{R}^{+}\times \mathbb{R}  , f(\epsilon,t) \neq \emptyset$$
(D2) 則 uniform convergence 代表 $$\forall \epsilon \in  \mathbb{R}^{+}  , \bigcap_{t\in \mathbb{R}}f(\epsilon,t) \neq \emptyset$$
註: uniform convergence 即為 common set 的概念 !!
註: 相似的概念還有均勻連續(uniform continuity)
-----------------------------------------------------------------------------------

[小結]
定義一對多函數是筆者在大學時代自創研究的符號與概念，雖然數學上都有類似的概念，但正式的符號定義並不多見，希望能藉由集合的交集聯集來描述複雜的邏輯概念，能對讀者有另一個角度的了解，關於一對多函數"合成"，還有其他可以做的事或許日後會再寫一篇 !!

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











留言

張貼留言

這個網誌中的熱門文章

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