機器學習 -- 簡介

機器學習

簡介

歷史

輸入

特徵

分群

最佳化

鄰近搜尋法

疊代搜尋法

案例比對法

函數分割法

模糊分群法

神經網路法

機率統計法

分群

分類

規則學習

語法規則學習

劇本規則學習

推理規則學習

網路關係學習

物件知識學習

貝氏法則與疊代

類別學習

最近 K 鄰居法

核心機

支持向量機

EM 學習法

程式實作

訊息

相關網站

參考文獻

最新修改

簡體版

English

前言

讓電腦具有學習能力,是資訊科學界長久以來的夢想,這個夢想不斷的吸引許多資訊科學研究者的目光,並促使他們發展出各式各樣的機器學習法。

然而,機器學習一詞也引起許多非理性的幻想,這些幻想也誤導了許多研究者,並讓他們產生了一些不科學的想法。

在本書中,我們將儘可能的讓機器學習一詞朝向科學化的領域邁進,並且將許多直覺性的想法落實為數學描述與程式,讓機器學習不再是神秘而變幻莫測的想法,而是明確而實際的算式與程式。

機器學習函數

根據筆者的觀察與研究,大致上可將機器學習化簡為下列更明確的想法。

機器學習程式 = 輸入 + (特徵函數 * 分群優化) + 輸出

機器學習的程式,仍然是一種普通的程式,其目的是為了將某些輸入值轉換為輸出值,因此沒有不可知的神秘之處。

因此,一個機器學習的程式,仍然是一個函數,我們可以將該函數寫成一個數學算式如下。

(y1, y2, …, ym) = f(x1, x2, …., xn)

舉例而言,一個機器翻譯系統,乃是將一串的來源文字 s1,s2,….,sn,轉換成一串的輸出文字 t1, t2, …, tm,因此可以寫成如下公式。

(t1, t2, …, tm) = MT(s1, s2, …., sn)

而一個光學數字辨識系統,乃是將一整張影像 p[1,1], p[1,2], …p[2,1],…., p[w, h] 作為輸入,然後輸出該影像所代表的數字符號 (0..9),因此可以寫成下列公式。

c = OCR(p[1..w, 1..h])

線性函數的學習

最簡單的一種機器學習程式,其輸出是輸入的線性組合,因此函數 f 可以寫成如下的程式。

(1)
\begin{equation} y_i = f(x_{i,1}, x_{i,2}, ..., x_{i,n}) = c_0+c_1*x_{i,1}+...+c_n*x_{i,n} \end{equation}

這種函數基本上是一個線性函數,因此只要訓練樣本足夠 (超過 n 組),就能用線性代數的方法解決。

舉例而言,假如我們已知 n 組樣本與輸出,如下列的算式所示。

(2)
\begin{eqnarray} y_1 &=& c_0 + c_1*x_{1,1} + ...+ c_n * x_{1,n} \\ y_2 &=& c_0 + c_1*x_{2,1} + ...+ c_n * x_{2,n} \\ ... &=& ...\\ y_k &=& c_0 + c_1*x_{k,1} + ...+ c_n * x_{k,n} \end{eqnarray}

上述算式可以用矩陣的方式表示,如下所示。

(3)
\begin{align} \left\{ \begin{array}{c} y_1 \\ y_2 \\ ... \\ y_k \end{array} \right\} = \left[ \begin{array}{cccc} 1 & x_{1,1} & ... & x_{1,n} \\ 1 & x_{2,1} & ... & x_{2,n} \\ ... & ... & ... & ... \\ 1 & x_{k,1} & ... & x_{k,n} \end{array} \right] \left\{ \begin{array}{c} c_0 \\ c_1 \\ ... \\ c_n \end{array} \right\} \end{align}

只要 k>n,而且學習的對象嚴格的符合公式 (1),那麼就可以用線性方程式的求解方法,像是高斯消去法等方式,求出 c0, c1, …, cn 的值。

甚至,我們也可以用簡單的搜尋法,像是爬山演算法,對 c0, c1, …, cn 等參數進行微調,然後尋找下列公式的最小值,以便找出 c0, c1, …, cn 的組合。

(4)
\begin{align} \arg \max_{c0,...,cn} \sum_{i=1}^k (y_i-f(x_i))^2 \end{align}

因此這是一種簡單的學習問題。

然而,在現實的世界中的現象,通常無法完全符合公式 (1),原因大致有兩個,第一個是現實生活的現象通常並非線性函數可以描述的,即使可以用線性函數描述,也通常有某種雜訊存在,這種雜訊就是無法符合公式 (1) 的第二個原因。

分群問題

即使上述的線性參數學習法並沒有很大的實用價值,但是卻有很好的理論價值,只要我們能夠對上述方法進行擴充即可。舉例而言,學習問題所要找的,通常是能夠將輸入問題,根據輸出分成很多目標群的方法,這種分群問題可以用數學式描述如下。

c = f(x1, …, xn)

其中的 c 可能為 {c1, c2, …, ck} 等 k 個可能的群體代號之一,於是我們只要能找出一些分割函數,這些分割函數能將 x1, …, xn 分割為 k 個區域,讓這 k 個區域盡可能符合輸出的類別即可。

使用球形的分割函數是一種可能的分割方法,像是 K-means,K-Nearest-Neighbor 等方法,都屬於球形分割的範例。

有時,分割的邊界會難以明確劃分,而是模糊或逐漸減弱的,此時若引入機率或模糊理論,就能讓這種分割更有彈性,像是貝氏分類 (Naive Bayes Classifier) 、模糊分類 (Fuzzy C-means) 與類神經網路等方法,就引入強弱函數以處理這種漸進現象。

如果我們的分割函數是線性的,那相當於找出一些 n 維空間中的分割平面,這些分割平面可以將輸入分為 k 群。但是,線性函數無法分割出像球形這樣的區域,因此並不是一個好的分割方法。為了克服這樣的問題,我們可以將輸入進行轉換,轉換到以 $[x_1, ..., x_n] * [x_1, ..., x_n]$ 為基底的二次領域中,也就是用 $x_1^2, x_2^2, ..., x_n^2, x_1x_2, x_1,x_3, ....,x_2 x_1, ..., x_2 x_{n-1}x_{n}$ 等所有的二次組合做為基底,然後用線性的方式進行組合,如此就能創造出 n 維空間中的球狀分割區域,這種方法就是支持性向量機 (Support Vector Machine) 所採用的模式。

最佳化

但是,如何知道某個分割函數比另一個分割函數更好呢?此時我們需要某種目標函數。只要目標函數確定了,那麼我們就可以利用最佳化方法找出最好或相對較好的分割函數,這些分割函數通常由某些參數所決定。

舉例而言,對於確定性的模型而言,我們可以假設分割函數是一個球體,如此只要找出分割球的中心位置與半徑 (c1, r1), (c2, r2), …, (ck, rk) 等,就可以將整個空間分割成許多群。於是,分群問題就變成了一種參數尋找問題,也就是搜尋最佳化的問題了。

對於機率模型而言,我們可以假設每個分割函數都是一個常態分布,只是期望值 c 與變異數 v 尚未確定而已,如此只要找出 (c1, v1), (c2, v2), …, (ck, vk) 這些參數,這些分割函數就確定下來了。

特徵抽取

舉例而言,如果我們將輸入參數 x1, …, xn 進行加值處理,加入一些特徵函數 f1(x1,…,xn), …, fk(x1,…, xn) ,只要這些函數可以很好的抓住問題的特性,就能透過簡單的線性分割,將樣本點分群。

然而,在許多問題上,這些特徵抽取函數乃是未知的,我們必須學習這些特徵抽取函數,將要能做出上述的智慧型函數,通常必須對輸入進行某些特徵抽取,這些特徵抽取動作仍然是一群由輸入所衍生出來的函數,可以寫成 f1(x1, x2, …, xn), f2(x1, x2, …, xn), …, fk(x1, …, xn)。

然而,這些特徵函數往往是經由某些訓練後所得到的,所謂的學習,也就存在於這些特徵函數的建構過程上。

然後,我們通常會將這些特徵函數

分群優化

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License