跳到主要內容

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

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

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