Machine Learning: Deterministic and Stochastic?

by allenlu2007

 

之前在看 machine learning 時,常常會有一些疑惑。Machine learning 的問題是 deterministic 還是 stochastic?

一方面在處理 supervised learning 的 classification 或是 regression 問題時,大多先定義 error function, 同時 minimize error 而得到對應的 weight.  可以想像 weights 是在 parameter space 之中,找最佳的 weight 就是一個 optimization 問題。

NewImage

其實 regression 問題也可以說是 curve fitting 問題。Curve 可以是 linear or nonlinear curves. 

NewImage

從 input data 的角度來看 machine learning,像是 stochastic (隨機) 的問題。不過不是 signal to noise (類似通訊) 類的隨機。

因為大部份 machine learning 的 input data (word, speech, image, object) 都不是 noise dominant, 而是 variation 所造成。(想像每個人的 speech 都有 variation).  其實這包含了兩個部份: (1) 求同存異: 就是找到特徵 (feature) 而忽略不同人的差異。這是一般 machine learning 的重點。如 speech recognition 可以辨識不同人說相同的話。 (2) 求同求異: 就是 ID (identification) 問題。以上例 speech recognition 來說,不但能辨識話,還能分辨是男女,或是特定人的聲音。 

In summary, input data 看來像是 stochastic 是由 sample 差異造成。而不是 noise.  這些差異在某一些情況可以提供了更多的 information (feature, structure, etc.).  不像 noise 大多是 information-less.

但從 parameter space 來看 machine learning, 像是 deterministic 的問題。

從上圖 (curve fitting) 而言,就是 minimize error, 找 optimal parameter (weight).  可參考上上圖。就是標準的 optimization 的問題。Optimization 一般的認知是 deterministic 問題。

 

In summary, supervised learning 問題的核心是 parameter estimation -> 也就是 optimization 問題

如 linear regression 的 a and b,  kernel or SVM 的 kernel;  neural network 的 weight functions!!!  一但 parameter learning finished (or on-line training), 就可以用 estimated parameter 來做 testing!!

Parameter estimation 可以是 deterministic (cost/error minimization) 或是 stochastic (probability maximization)

整體來說就是 optimization 問題 (minimization 或是 maximization)

Deterministic->cost/error minimization =>OPTIMIZATION<= maximum likelihood estimation (MLE)<-joint or conditional PDF<-Stochastic

 

* 不論是 cost/error function minimization 或是 PDF maximization 都是 Optimization 問題!  所以 stochastic approach 和 deterministic approach 就數學而言是一樣。

* 如果是 Gaussian distribution 加上 MLE (maximum likelihood estimation) and IID,  就從 stochastic 問題變成  mean square error minimization 問題 (見前文)。

 

4. 前文有其他的 PDF optimization, 如 MAP, or MAVE?   但更 general (and powerful?) 就是 Bayesian estimation 包含 prior distribution!

 

So Why Stochastic/Probabilistic?  Why Not Just Deterministic Optimization??

一般人對於 deterministic optimization 會更直覺也更容易理解(如拋物線找最小值)。反而對 stochastic/probabilistic/random 的觀念缺乏直覺。如果 machine learning 的問題 (e.g. classification or regression) 都可以用 deterministic optimization (至少數學上) 解決。為什麼需要導入 stochastic 的觀念?

**  Deterministic optimization 的最大問題就是暗示存在且找唯一最佳解 (min or max).  ~~~~~~  這是考試教育的通病?

很多 machine learning 的問題本質上並不存在唯一最佳解,如 canner diagnose, speech recognition, image recognition, object detection.  如果目光是要找到唯一最佳解,常常吃力不討好。例如 salesman traveling 問題。如果要找最佳解,是 NP 問題。如果要找接近 optimal solution (或者根本沒有 golden optimal solution), 則容易解的多。如果可以容忍有 randomness (就是可以有錯,但機率小), 可以有更好效率的算法或工具。例如用 SGD (stochastic gradient descent) 而非 GD (gradient descent). 或是 MCMC.  

GD 很大的問題是要有全部的 samples 才能計算。如果 sample 增加又要重算,費時費力。SGD 則可以 sample update, 非常有效率。唯一的缺點是 final settling 包含 random jitter.  但多數情況下 good enough.

 

** Probabilistic modeling 可以處理更 general 以及複雜的問題 

Probabilistic modeling 不只是有更多的算法和工具。而是觀念上的改變!

Deterministic optimization 需要定義 cost function, 基本上需要一個明確的 function, kernel, filter, etc.  才能做 optimization.

很多 machine learning 的問題並不一定有明確的公式,只知道有 correlation.  甚至不一定明確知道因果關係 (i.e. who is input, who is output).   例如 random Markov field 或 Ising model 相關問題(?).   如果用 probabilistic model 不一定需要明確因果或公式,只要是否有 correlation 就可。

另外 probabilistic modeling 可以很容易加入 prior information (Bayesian).  或是 explore factorization (factor graph, based on conditional probability).  

不需要 linear state space model 只要有 conditional or joint PDF dependence –> factor graph.  並不用 specific Gaussian pdf or linear space model.  當然解一些實際的問題還是需要一些 model (e.g. Kalman filter).  但很多時候可以靠 data or simulation (MCMC) 來得到 PDF information.

** Probabilistic modeling 可以回答更細的問題,不只是 yes or no (classification), 或是 one value (regression)

Probabilisitc modeling 可以回答 probability, confidence interval, of the estimation. 

 

University of Toronto CSC2515 Note “Optimization

Use probabilistic model 解釋 optimal weight (w) depending on ML, MAP, or Bayesian criterions.

Regression / Classification and Probability

NewImage

以下 slide shows: probabilistics model 的 maximum likelihood 等效於 minimum mean square error. (assuming Gaussian and IID).

NewImage 

 

如果有 prior information, 則變成 regulated minimum mean square error.

NewImage

 

更 general 的方式是 Bayesian 如下。

NewImage

 

以下是 MLE 的推論。

NewImage

 

再來就是 GD (ignore).   限制就是如下:

NewImage

再來則是 conjugate gradient 和 2nd order method (Newton method and others). 

Advertisements