本文是筆者在計算隨機過程，研究的時候發現的積分公式，很有趣，原理很簡單 !! [明顯的例子] 假如我要算二重定積分 $$ A = \int^{1}_{0}\int^{1}_{x} (x+y)dydx $$ 今天我不小心把符號寫反 $x$ 寫成 $y$ , $y$ 寫成 $x$  $$ A' = \int^{1}_{0}\int^{1}_{y} (y+x)dxdy $$ 但理論上答案是一樣的(你只是換了符號而已，題目本質不變)，所以 $A' =A$ 後來你發現加法有交換律 $(y+x) = (x+y)$ ，你會發現 $A'' = A'$  ，其中  $$ A'' = \int^{1}_{0}\int^{1}_{y} (x+y)dxdy $$ 然後你會發現 $\{(x,y) \in [0,1]^2 :   x\leq y    \} \cup \{(x,y) \in [0,1]^2 :   x\geq y    \} = [0,1]^2$ $$ 2A =  A'' + A =   \int^{1}_{0} \int^{1}_{0} (x+y)dydx $$ 所以我們有 $$A = \frac{1}{2!} \int^{1}_{0} \int^{1}_{0} (x+y)dydx  $$ 如果令 $f(x,y) := x+y = y+x = f(y,x)$ 我們發現 $f$ 是對稱函數!! ------------------------------------------------------------------------- [推廣] 所以如果 $f(\vec{x}):= f(x_1,x_2,x_3,....,x_n)$ 是一個在 $(x_1,x_2,....,x_n)$對稱的函數 [註: 對稱函數代表 $\forall \sigma \in S_n  \quad  f(\sigma(\vec{x})) = f(\vec{x}) $  (其中$S_n$為交換群( Permutation Group )) 考慮 定義域為 $$ \Omega := \{ \vec{x}\in [a,b]^{n} : x_1 \leq x_2 \leq x_3 \leq ..

日常生活中，我們常常拿到的資料是一筆筆的。假如有 $n$ 筆資料，$p$ 種屬性，$n \times p$ 矩陣 ------------------------------------------------------------------------- 例如 : $(5+1) \times 5$ 資料矩陣 其中第一行(column)為 id 代表第幾筆 !! 有5個給定屬性集依序為 (1)12羅馬字$S^{R} = \{ I ,II , III , .... XII \}$   (2)小寫英文字母  $\tau = \{a,b,c,d,e,f.....z\}$ (3)大寫字母  $\Gamma = \{A,B,C,D,E,....Z\}$ (4)比例值 $[0,1]$ (5)負數 $\mathbb{Z}^{-}$ $$\left[\begin{array}{c|cccc} 1&III &  c &  C &  0.1 & -9   \\ 2&IV &  a &  C &  0.2 &  -999 \\ 3&II &  a &  A &  0.5 &  -9999 \\ 4&III &  b &  A &  0.5 & -999\\ 5&IV &  c &  B &  0.7 & -99 \\ \end{array}\right]$$ 這時你會有一連串 Q & A ~~ (Q1) 當 負數為 -99 的資料哪幾筆?? (Q2) 這筆資料總共有哪些大寫英文字母?? (Q3) 當 大寫英文字母為 $A$   且比例值為 $0.5$其他屬性有哪些種 ?? .... 而你問的每個問題事實上都是一個收集的概念 !! 像 (Q1) 你會希望印出的是 $\{ 5 \}$ 或是  $(IV, c, B,0.7)$ 像 (Q2) 你會希望印出的是 $\{ A,B,C \}$ 像 (Q3) 你會希望印出的是 $ \{(II,a ,-9999),(III,b,-999)\}$ 當資料大的時候 $n , p $ 很大，你

本文為筆者自行設計圖論演算法解離散不確定決策過程，含動態規劃( Dynamic Programming ) 與 Bellman principle of optimality(Bellman Equation) 相關概念，分享其 Idea 框架！！ 給定有向圖 $G(N,A)$ ，其中 $N = D \cup R \cup T $，$D,R,T$為互斥的集合， 其中 $i,j \in N$ 代表 State 實作上可以想成 string representation 定義 Forward Set  of $i$ : $F_i$ $$ (i,j) \in A \Longleftrightarrow  j \in F_i $$ 其中: $d \in D$ 稱為 Decision Nodes  (決策點集) ，代表該情境決策當下           $r \in R$ 稱為  Random  Nodes  (隨機點集) ，代表不確定性的開端           $t \in T$ 稱為  Terminate Nodes (停止點集) ，代表得到報酬或離開 註: $\forall i \in T \quad F_{i} = \emptyset $ 定義機率函數(ArcCost) $p : R\times F_r \longrightarrow \mathbb{[0,1]}  \quad p_{ij} \text{ are given }$ 並滿足機率公設 定義累計報酬函數:  $g : N \longrightarrow  \mathbb{R}$ $$ g(i):= \left\{\begin{array}{lll} \displaystyle{\underset{j\in F_i}{\text{max }}g(j)}&,& \text{if }  i \in D \\ \displaystyle{\sum_{j\in F_i}p_{ij}g(j)} &,& \text{if }  i \in R \\ \text{Initial Value }&,& \text{if }  i \in T \\  \end{array} \right. $$ 定義選擇函數:  $s :

條件機率( Conditional Probability )的概念， Bayes Formula ，在日常生活中機率應該是最常使用的公式，由於多維的時候需要寫一長串公式，所以這邊自己嘗試定義推廣到抽象化的代數符號!! 令 $X,Y,Z$ 為連續隨機變數的集合，$f_X, f_Y,f_Z$ 為 joint pdf 1.Define: $$\left<\frac{X}{Y} \right> := \frac{f_{X\cup Y}}{f_Y}   $$ (p.s : 意思是給定 $Y$ 資訊下，測量$X$ 的機率密度 ，即 $X|Y$ 的分布) ------------------------------------------------------------------- [Ex: 二維的例子] $$X = \{x_1,x_2\}, Y=\{x_2\}  \Longrightarrow  \left<\frac{X}{Y} \right> = \frac{f(x_1,x_2)}{f(x_2)} $$ 其中分子為 joint $(x_1,x_2)$ , 分母為 marginal $x_2$ ------------------------------------------------------------------- 2.No Information : ($f_\emptyset = 1$) $$ \left< \frac{X}{\emptyset} \right>  := f_X$$ 3.Integration Formula : (if $Y\subset X$) $$ \left<\frac{Y}{Z} \right>= \int_{X\setminus Y}\left<\frac{X}{Z} \right> $$ -------------------------------------------------------------------- [Ex: 二維的例子] $X = \{x_1,x_2\}, Y=\{x_1\},Z=\emptyset$ $$\Longrightarrow  \left<\frac{Y}{Z} \right&

日常生活中，常常會有機智問答，如給定一個數列 $1,2,3,4,5,X$ ，請問下一項$X$是什麼，我們自然會回答 $6$ ，下一項是 $7$ ，事實上我們發現公式可以寫成 $a_k = k  \quad  k=1,2,3,...$ 我們可以定義正式一個問題如下: -------------------------------------------------------------------------- $(Q)$給定 $n$ 個整數，如何找到 $f$ 使得 $(C) : a_k = f(k) , k = 1,2,3,...n $ -------------------------------------------------------------------------- 而根據知識，我們可以找到無窮多個多項式 $f$ 可以滿足$(C)$，而恰好存在唯一一個 $n-1$ 次多項式(polynomial) 可以滿足$(C)$，這問題的連續版本在數值分析( Numerical Analysis )領域稱為 interpolation ，也就是給定 $ S \subset \mathbb{R}^2$，找到一個公式$f$ 使得 $ \forall (x,y) \in S \quad f (x) = y $ [註: 這跟統計上迴歸分析不同的是，interpolation 要完全 fit !!，但是如果存在$(x,y_1),(x,y_2) \in S$,$y_1 \neq y_2$，因為函數無法一對多，則無法使用 interpolation !!   ] 而問題$(Q)$ 在筆者讀高中的時候發現的一個公式，會找到一個最低項的多項式(如果只有紙跟筆的話)，分享給讀者~ 先定義差分數列 $ b_k = a_{k+1}- a_{k}$ ，$\{b_k\}^{n-1}_{k=1}$ 會比 $a_k$ 少一項，記做 $\{\Delta a_k\}^{n-1}_{k=1}$ ，每做一次差分會少一項。 我們持續做會得到很多差分數列，取它們的第一項，記做 $\vec{a} :=< a_1 , \Delta a_1 , ..... \Delta^{n-1} a_1 >$ 再來定義 $\vec{b}:= <C^{k-1}_0, C^{

日常生活中充滿著不確定性( Uncertainty )，隨機性( Randomness )。我們能輕易理解公平骰子每一面出現的機率值為$\frac{1}{6}$，而且可以利用排列組合( Combinatorics )的比例去計算複雜的狀況的機率值。但對於更複雜的隨機性(如隨著時間，空間連續變化的隨機性，大量的試驗，該如何計算，如何刻劃，我們就必須要學習 20世紀數學家發展嚴謹的測度論( Measure Theory )與機率論( Probability Theory )， Andrey Komogorov 機率公設模型後，才算是更清楚掌握瞭解機率的真正概念與正確使用數學描述不確定性!! 而其中核心概念是隨機變數( Random Variable )的引入，但因初學者往往會對隨機變數有種似懂非懂甚至誤解，所以本篇算是對於"隨機變數"的概念做澄清。 [預備知識] 需要理解 集合( Set )，函數( Function )，微積分( Calculus )符號 [註] 關於函數的介紹，也可以看 這篇 的前半部有詳細的回顧 !! 首先我們會定義一個抽象的集合 $\Omega$ ，稱之為樣本空間( sample space )，其元素 $\omega \in \Omega$，代表可能的情境(possible scenario)或是稱為基本事件(simple event)。當事情發生後，相當於從 $\Omega$ 選取一個 $\omega$ !! [Example] 丟一個骰子，可能會出現的結果 $\Omega = \{1,2,3,4,5,6\}$，則丟完以後只會出現其中一種 $\omega = 1 \text{ or }2\text{ or }3\text{ or }4\text{ or }5\text{ or }6$，而機率值假設分別為 $\frac{1}{6}$。但實際上我們可能感興趣更大的集合，例如: 出現偶數點的機率。回憶起你如何計算它，你必須先收集出 $E :=\{2,4,6\} \subset \Omega $ ，然後再分別計算基本事件的機率 $\frac{1}{6} + \frac{1}{6} + \frac{1}{6}  = \frac{1}{2} \quad (*)$ [可以做的事] 把基本事件寫成"單點&

在學習數理邏輯( Mathematical Logic )的時候，常常會聽到若 $P$ 則 $Q$，可能會被 "$\Longrightarrow$"(if .... then ...) 的意義搞得似懂非懂，就算懂了它的結果跟生活上的結合也是有種莫名陌生感，像筆者小時候會想成"因為 ... 所以 ..."，但這不是它的正確意義。而日常生活中集合論的交集，聯集或許是大家比較容易理解的。本文是用集合論的觀點去了解邏輯，方程組，數學規劃上的應用，並介紹布林代數( Boolean Algebra )跟邏輯的關係，提供另一個角度可能更容易理解數學 !! [輔助理解] 因為集合論可以在黑板上畫文氏圖( Venn Diagram )，詢問點是落在哪個圈圈裡面還外面，大家都能輕易理解認同，而產生共鳴的語言!! [假想實驗] 通常我們會先定義宇集，論域( universal set ) $U$，代表我們所感興趣的東西，事物，元素變數符號 $u$。$P$，$Q$在日常生活中可能是某個條件(condition)，性質(property)，限制(constraint)。而我們會依依檢驗 $U$裡面的元素 $u$ 是否滿足條件$P$，如果滿足就把它們收集起來，形成一個集合。 同理 $Q$ 也照做，所以我們會收集到兩個集合!! 白話來說，可以寫成 $S_P := \{ u \in U : u \text{ satisfies condition } P\}$ $S_Q := \{ u \in U : u \text{ satisfies condition } Q\}$ 註: 比較正式的寫法是可以分別把 $P$，$Q$對應到布林值( Boolean 或叫 Predicate 或叫 Indicator function ) $f_P$ , $f_Q$，$f_P,f_Q: U \longrightarrow \{0 , 1 \}$，$S_P := \{ u \in U : f_P(u) = 1  \}，S_Q :=\{ u \in U : f_Q(u) = 1 \}$ 虛擬碼大致上是 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Into Da

本文探討數學語言三大基礎概念之一 (邏輯，集合，函數) 的函數 !! 並推廣函數觀念至"一對多"，並定義共同集(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$    代表  

現實生活中，很很多資料，不管是文字跟數字，代表的意義也不同，但在實作運算上需要特別注意，本文先介紹一些常見的類型，值域型態 : 統計學 基本上有分成四種類型資料 ( level of measurement ) 1.名目尺度(Nominal) :   任意兩元素只能區分相同與不相同 例如 :       [1] $X_i = \{ \text{apple} , \text{bananas} \}$ [2] $X_i = \{ \text{mac} , \text{windows} , \text{linux} \}$ [3] $X_i = \{True = 1 , False = 0 \}$ 注意: 模糊理論( Fuzzy Theory ) 有對於 Boolean 集合論隸屬關係 $\in$ {0,1} 拓展到 [0,1] ，定義模糊的概念 注意: 資工方面，常常會把文字"string"資料轉數字"int" ，如:   Hash function 2. 順序尺度(Ordinal) :    任意兩元素可以區分不同，也可以有大小排序，但不能運算出其差距 例如 :     排名，偏好  $X_i = \{ 1 = 1st , 2 = 2nd , 3 = 3rd , 4 = 4th  \}$               3.等距尺度(Interval):      任意兩元素可以區分不同，也可以有大小排序，也可以計算其差距，但是沒有參考原點(理想點)，不能做乘除運算，不能探討倍數關係 例如:  攝氏溫標  85度C 的 2倍 $\neq$ 170度C 例如:  絕對時刻  碼表上的 3秒 兩倍未必是 6秒 (除非你從 0 秒開始算) 4.等比尺度(Ratio)  任意兩元素可以區分不同，也可以有大小排序，也可以計算其差距，可以做乘除運算 有參考原點 "0" 與單位長 "1 - 0"的概念，可以利用參考原點計算出變化 $\Delta$   例如:  計量  $X_i = \{ 1=1個，2=2個，3=3個，.... \}$         數學上常見可以分成(尤其在定義機率論值域的時候0) 1. Discr

經濟學重要的賽局理論( 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_{-i}) :=  \underset{x_i \in \Omega_i}{\text

在統計學裡， Maximum Likelihood Estimation (MLE) 是常見對於母體參數的估計，本文詳細介紹它數學的詳細大致長相，以及它是一個無約束最佳化問題(unconstrained optimization problem) ，所以可以用最佳化演算法去逼近 MLE [Notation] 母體未知參數為 $\theta = (\theta_1,\theta_2,...\theta_m) \in \Theta \subset \mathbb{R}^{m} $ 隨機向量為 $X = (X_1,X_2,....X_p)$ 給定向量為 $x = (x_1,x_2,...,x_p)$ 母體分布 (joint probability density function) $f = f(x,\theta) $ $$(1)\forall \theta \in \Theta, \int_{x\in \mathbb{R}^{p}} f(x,\theta) = 1 \qquad (2) \forall (x , \theta) \in \mathbb{R}^{p}\times \Theta \quad f(x,\theta) \in [0,1]$$ [樣本的聯合分配] 考慮獨立同分配 identical independent distributed (iid) 抽樣，$n$ 個樣本為 $\mathcal{D}=\{(X^k)\}^{n}_{k=1}$，$d = \{(x^k)\}^{n}_{k=1}$，其中 $X^{k} = (X^{k}_1,X^{k}_2,...X^{k}_p)$ $$\{(X^k)\}^{n}_{k=1} \sim  \prod^{n}_{k=1} f(x^{k},\theta)  =  \underbrace{f(x^{1},\theta) \cdot f(x^{2},\theta) ... \cdot  f(x^{k},\theta)}_{\text{number of variables } np + m} =(*)  $$ [ Likelihood Function ] 當樣本已知 $\mathcal{D} = d $ 給定，視 $\theta$ 為變數，則統計學術語稱$(*)$為 Likelihoo

當拿到一筆資料準備玩統計，往往會想要做線性迴歸( 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)\approx \left\{

這是一個關於"跨領域應用數學"的網誌，之所以取名為 Discover Forgotten Mathematics ，是因為要重新發現數學在各個工程，自然科學，社會科學扮演的角色。筆者在大學碩士博士班讀書生活約8年的時間，約4年學習純數學(Pure Mathematics)，2年學習應用數學(Applied Mathematics)，2年學習作業研究(Operation Research)，加上筆者喜歡雜學與自學，是一位數學探險家，目前重視社會科學的數學，而對於機率，統計，最佳化，演算法，數學規劃，方程類，都有極大的熱忱，於是想把視野廣度整合藉由此網誌分享給有興趣的人~~最後分享兩句話，一句話是應用數學大師 John von Neumann  的名言   " 若人們不相信數學簡單，只因他們未意識到生命之複雜 " ，而另一句是筆者的想法 : " 我們不能只學簡單的數學或恐懼困難的數學，或是獨自抽象化，而該學習把困難的數學變簡單，讓更多人能夠輕易理解與體會數學的確無所不在。 " Email : mathfunction@gmail.com by Plus & Minus 2017.08

複製以下這行在 html 模式，文章的開始，即可使用 latex 碼 :) <script type="text/x-mathjax-config">   MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}}); </script> <script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"> </script> 參考網址 :  http://holdenweb.blogspot.tw/2011/11/blogging-mathematics.html

在計算數學( Computational Mathematics )，數值分析( Numerical Analysis )領域裡，介紹在$\mathbb{R}^n$ 上解非線性方程組 (System of Nonlinear Equations) 學術上有名的牛頓法( Newton Method ) ，它也是很多最佳化演算法的核心概念 現實問題中，我們通常會想要找一組解 $x \in \mathbb{R}^{n}$上，使得 $f(x) = \vec{0}$， 其中 $f : \mathbb{R}^n \longrightarrow \mathbb{R}^{m}$， 詳細一點可以寫成一個有 $n$ 個未知數(unknowns) 跟 $m$ 個限制式(constraints)  $\text{Find } x = (x_1,x_2,...,x_n) \in \mathbb{R}^n \quad  \text{such that } \left\{\begin{array}{c}f_1(x_1,x_2,x_3,...,x_n)=0\\f_2(x_1,x_2,x_3,...,x_n)=0\\f_3(x_1,x_2,x_3,...,x_n)=0\\f_4(x_1,x_2,x_3,...,x_n)=0\\...\\f_m(x_1,x_2,x_3,...,x_n)=0\\\end{array}\right.$ 精確解我們記做 $x^{*}$ 1.如果 $f$ 是線性函數，即為我們熟知的線性聯立方程組 $Ax = b $ 或寫成 $\left(\forall i = 1,2,3,...m \quad f_{i}(x) = \sum^{n}_{j=1}a_{ij}x_j  = b_i \right)$ 線性系統可以用大家熟知高斯消去法( Gauss Elimination )，經過有限步驟得到精確解。 2.如果$f$ 是非線性但連續且可微，即   Jacobian Matrix $f$  存在，則我們可以用牛頓迭代法， [以下是虛擬碼 ( pseudo code )] +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ $\text{Given Initial G