Machine learning---Raymond J. Mooney
『機器學習』是一個新興且很有潛力的領域，它結合了統計、數學與資訊科學等學門。廣義來說，機器學習研究如何讓電腦具有學習的能力，從以往的經驗、資料中學習到知識，以增進電腦本身的效能，因此機器學習也可解釋為利用資料來建立一些模擬真實世界的模式（Model），利用這些模式來描述資料中的特徵（Patterns）以及關係（Relations）。這些模式有兩種用處，第一，瞭解資料的特徵與關係可以提供你做決策所需要的資訊。第二，資料的特徵可以幫助你做預測。
機器學習是一個重要的研究領域，在近幾年也有許多成功的應用。所發展的方法已被應用於消費者行為分析，聲音或影像識別，乃至於生物資訊等新興產業。
本章主要目的在介紹機器學習的基本概念、各種技術及演算法。如decision-tree、induction、Rule Induction、Instance-based、categorization等方法以及相關在自然語言處理上的應用，如：Part-of-speech tagging、Word-sense disambiguation、Information extraction、Anaphora resolution等。
一、學習分類：
機器學習定義為經學習過程後可以將一群data set(每一組data有n 個不同的features{f1,f2,…,fn}) 分類為m個不同的類別{c1,c2,….cm}中的某一類別。
舉例來說在不同句子中「interest」這個字可以有下列三種意思，如何判斷何時是何意呢?
根據此問題在句子中可以依下列方式選擇features：
訓練資料如下：
系統會加入許多的訓練資料(training data)透過學習後，得到將來判斷新資料的知識。
二、機器學習相關演算法：
1. decision-tree induction
決策樹的推導(Decision tree induction)是一種使用樹狀架構的方法來做分類，結點代表不同的feature，樹枝為feature的值，而樹葉則是不同的分類類別(class label)。
這種方式是先找一個最佳的特徵作為根節點，所有的資料以此根節點為判斷根據，進行分類，分類在每一個分支的資料再選出最佳的特徵作為根節點，再進行分類，形式一棵子樹，如此的過程一直重複，直到在一個分支內的所有資料都屬於同一個類別，推導過程才算結束，這個最終的分支就會形式樹葉，裡面記載著該樹葉內的資料所屬的類別，這樣就會形式一棵決策樹。
詳細的決策樹推導演算法如下：
樹的大小決定於分支的節點數，希望用最少的節點就可以分出結果，因此要如何才能選到最好的feature呢? 原則上希望使分支後的每ㄧ個節點，就所要預測的變數而言，同質性越高越好(homogeneous)，可利用Information theory 的entropy理論來定義評估標準，同質性高者包含較少資訊，因此entropy比較小。
若ㄧ個節點包含S種預測值，且每ㄧ種預測值在該節點中的出現頻率為則該節點的entropy為
ㄧ個好的feature應該使得其subset的entropy最小，因此一個好的分類結點應該有最大的information gain，其定義為：
(split 前該結點的entropy) –(split 後各子結點的entropy的總和平均)，因為希望split後子結點的entropy的總和平均越小越好，所以gain 越大越好。
2. Rule Induction
規則歸納法(Rule Induction)是一種由一連串的「如果 … (條件) … 則 … (結果) … 」(IF … … T h e n … … )之邏輯規則對資料進行細分的技術，在實際運用時如何界定規則為有效是最大的問題，通常需先將資料中發生數太少的項目先剔除，以避免產生無意義的邏輯規則。
利用規則法試圖找出較佳特徵值，將含有此特徵值的資料全部找出來並聚合、形成一個子集合，一直重複這個動作，直到子集合中每一個記錄都屬於同一個類別為止，即所謂的規則歸納法則。它和決策樹同樣是要從大量資料中，擷取人類所能理解的知識型態，提供決策者作為決策的依據。
詳細的規則歸納演算法如下：
：
3. Instance-based categorization
又可稱為case-based案例學習分類法，是將新資料依據與訓練資料(training examples)的相似度來歸類，依據sample之間的距離來計算相似度，將相似度高的歸類為同一類。距離的計算採用Euclidian distance，其定義為：
案例分類法其中一種為KNN(K nearest-neighbor) ，其演算法如下：
三、應用：
許多機器學習的演算法如今已廣泛的應用在電腦語言學的處理上，以下提出一些範例：
1. Part-of-speech tagging
在做句法分析時最重要的第一步動作為標記每一個字的詞性，得到詞性後才可建立句法樹。但相同的字可能會有多種不同的詞性因此如何正確標記可利用建立window size，取得要標記字前後的文字詞性當feature，再透過決策樹推導、規則歸納法，或案例學習法來判斷正確的詞性。
2. Word-sense disambiguation
當文字中某個字出現多種字義時電腦如何判斷它此時正確的意思呢？此時利用機器學習的方法，可以根據文字內容決定此岐意字的意思。因為句子內一起出現的其他字會形成該字義專有的集合，另外還可再加上此字前後字的POS形成特有的feature，累積多筆的training data後，字義的字彙集合就會變大，就可以利用instance-based 的方法來解決歧異性。
3. Information extraction
資訊擷取(Information extract)是一種在自然語言文件中裡找到相關特有字(a specified set of relevant items)的技術。資訊擷取系統需要顯著的具體領域的知識並且費時且難親手建造，所以這也是一個相當適合做機器學習的應用。近來許多人利用規則歸納法來學習資訊擷取中的重要pattern，如下圖就是一個完成規則歸納法所得到的資訊擷取規則，利用這個規則可以擷取出所需要的資訊。
4. Anaphora resolution
首語重複法的解析(Anaphora resolution)亦可稱為代名詞指代問題，指的是當句子中出現代名詞時，這個代名詞實際上所指的是什麼，如果文章中有多個代名詞，則哪些代名詞指的是同一個人或事呢？因此首語重複法的解析的解析可視為是一種將片語分類為指向同一個人事物或不同事物的方法。利用決策樹推導方式找出主詞並建立樹狀結構，由此結構解析主詞間的關係。
簡單來說決策樹就是利用分類的方法來做classification的動作,用一個或多個特徵(feature),並運用二分法,慢慢把複雜的資料分成好幾類,把資料純化(purify)。For example,一個班級可以先用性別分成男生女生,再運用身高、體重將學生分成性質相近的幾個組別。
each branch node represents a choice
between a number of alternatives
each leaf node represents a classification or
decision
而要怎樣做決策呢，我們運用entropy
做為純度的檢驗,如果entropy越大代表純度越低(分類不完全)。
並且我們運用gain來測試,
如果gain越高代表分類的特徵越佳,分類完的純度越大。
分隔線以上的文章轉自http://210.240.194.97/course/2005/TGBCL/poko/OHCL-20.htm
留言列表
