新編528自然語(yǔ)言中的重要技術(shù)課件

1、 分類(lèi)IRLAB大綱自然語(yǔ)言中的重要技術(shù)決策樹(shù)最大熵模型K近鄰自然語(yǔ)言中的分類(lèi)問(wèn)題分類(lèi)的一般過(guò)程訓(xùn)練集數(shù)學(xué)模型訓(xùn)練過(guò)程測(cè)試集評(píng)價(jià)精確率，宏平均，微平均本課介紹的幾種方法決策樹(shù)最大熵模型K近鄰決策樹(shù)簡(jiǎn)介決策樹(shù)表示法決策樹(shù)學(xué)習(xí)的適用問(wèn)題基本的決策樹(shù)學(xué)習(xí)算法決策樹(shù)學(xué)習(xí)中的假想空間搜索決策樹(shù)學(xué)習(xí)的常見(jiàn)問(wèn)題簡(jiǎn)介決策樹(shù)方法的起源是概念學(xué)習(xí)系統(tǒng)CLS，然后發(fā)展到ID3方法而為高潮，最后又演化為能處理連續(xù)屬性的C4.5。有名的決策樹(shù)方法還有CART和Assistant。是應(yīng)用最廣的歸納推理算法之一一種逼近離散值目標(biāo)函數(shù)的方法對(duì)噪聲數(shù)據(jù)有很好的健壯性且能學(xué)習(xí)析取表達(dá)式?jīng)Q策樹(shù)的表示法決策樹(shù)通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到

2、某個(gè)葉子節(jié)點(diǎn)來(lái)分類(lèi)實(shí)例，葉子節(jié)點(diǎn)即為實(shí)例所屬的分類(lèi)。樹(shù)上的每一個(gè)節(jié)點(diǎn)說(shuō)明了對(duì)實(shí)例的某個(gè)屬性的測(cè)試，并且該節(jié)點(diǎn)的每一個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值圖表達(dá)式?jīng)Q策樹(shù)學(xué)習(xí)的適用問(wèn)題實(shí)例是由屬性-值對(duì)表示的目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例屬性選擇構(gòu)造好的決策樹(shù)的關(guān)鍵在于如何選擇好的邏輯判斷或?qū)傩?。?duì)于同樣一組例子，可以有很多決策樹(shù)能符合這組例子。人們研究出，一般情況下或具有較大概率地說(shuō)，樹(shù)越小則樹(shù)的預(yù)測(cè)能力越強(qiáng)。要構(gòu)造盡可能小的決策樹(shù)，關(guān)鍵在于選擇恰當(dāng)?shù)倪壿嬇袛嗷驅(qū)傩?。由于?gòu)造最小的樹(shù)是NP-難問(wèn)題，因此只能采取用啟發(fā)式策略選擇好的邏輯判

3、斷或?qū)傩浴?用熵度量樣例的均一性（純度）熵的定義舉例用信息增益度量期望熵最低舉例ID3算法創(chuàng)建樹(shù)的Root結(jié)點(diǎn)如果Examples都為正，那么返回label=+中的單結(jié)點(diǎn)Root如果Examples都為反，那么返回lable=-單結(jié)點(diǎn)樹(shù)Root如果Attributes為空，那么返回單節(jié)點(diǎn)樹(shù)Root，lable=Examples中最普遍的目標(biāo)屬性值否則開(kāi)始AAttributes中分類(lèi)能力最好的屬性Root的決策屬性A對(duì)于每個(gè)可能值 在Root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試A=vi令Example-vi為Examples中滿(mǎn)足A屬性值為vi的子集如果Examples-vi為空在這個(gè)新分支下加一個(gè)葉子結(jié)點(diǎn)

4、，節(jié)點(diǎn)的lable=Examples中最普遍的 目標(biāo)屬性值否則在這個(gè)新分支下加一個(gè)子樹(shù)ID3(example-vi,target-attribute,attributes-|A|結(jié)束返回 RootC4.5C4.5是對(duì)ID3的改進(jìn)算法對(duì)連續(xù)值的處理對(duì)未知特征值的處理對(duì)決策樹(shù)進(jìn)行剪枝規(guī)則的派生決策樹(shù)學(xué)習(xí)中的假設(shè)空間搜索假設(shè)空間ID3算法中的假設(shè)空間包含所有的決策樹(shù)當(dāng)遍歷決策樹(shù)空間時(shí)，ID3僅維護(hù)單一的當(dāng)前假設(shè)?；镜腎D3算法在搜索中不進(jìn)行回溯ID3算法在搜索的每一步都使用當(dāng)前的所有訓(xùn)練樣例決策樹(shù)學(xué)習(xí)的常見(jiàn)問(wèn)題(1)避免過(guò)度擬合數(shù)據(jù)基本的決策樹(shù)構(gòu)造算法沒(méi)有考慮噪聲，生成的決策樹(shù)完全與訓(xùn)練例子擬合。

5、有噪聲情況下，完全擬合將導(dǎo)致過(guò)分?jǐn)M合（overfitting），即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很好的預(yù)測(cè)性能。 解決方法剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹(shù)得到簡(jiǎn)化而變得更容易理解。向前剪枝（forward pruning）向后剪枝（backward pruning） 理論上講，向后剪枝好于向前剪枝，但計(jì)算復(fù)雜度大。剪枝過(guò)程中一般要涉及一些統(tǒng)計(jì)參數(shù)或閾值，如停機(jī)閾值；有人提出了一種和統(tǒng)計(jì)參數(shù)無(wú)關(guān)的基于最小描述長(zhǎng)（MDL）的有效剪枝法 決策樹(shù)學(xué)習(xí)的常見(jiàn)問(wèn)題（2）合并連續(xù)值屬性屬性選擇的其他度量標(biāo)準(zhǔn)信息增益比（gain ratio）、Gini-index、距離度量（distance meas

6、ure）等。不同的度量有不同的效果，特別是對(duì)于多值屬性。決策樹(shù)學(xué)習(xí)的常見(jiàn)問(wèn)題（3）處理缺少屬性值的訓(xùn)練樣例處理不同代價(jià)的屬性決策樹(shù)的優(yōu)點(diǎn)可以生成可以理解的規(guī)則；計(jì)算量相對(duì)來(lái)說(shuō)不是很大；可以處理連續(xù)和離散字段；決策樹(shù)可以清晰的顯示哪些字段比較重要不足之處對(duì)連續(xù)性的字段比較難預(yù)測(cè)當(dāng)類(lèi)別太多時(shí)，錯(cuò)誤可能會(huì)增加的比較快一般的算法分類(lèi)的時(shí)候，只是根據(jù)一個(gè)屬性來(lái)分類(lèi)。不是全局最優(yōu)。舉例：利用決策樹(shù)進(jìn)行文本分類(lèi)最大熵模型熵定量的描述事物的不確定性設(shè)隨機(jī)變量 ，它有A1，A2，An共n個(gè)可能的結(jié)局，每個(gè)結(jié)局出現(xiàn)的機(jī)率分別為p1,p2 ，.，pn，則 的不確定程度，即信息熵為: 熵越大，越不確定熵等于0，變量是

7、確定的最大熵思想最大熵思想由來(lái)已久，Occam在他著名的Occam剃刀理論中即體現(xiàn)了這種思想，對(duì)最大熵理論的系統(tǒng)論述出現(xiàn)在上世紀(jì)50年代中期，由E.T. Jaynes提出，其原理的基本思想是：我們從全部相容的分布預(yù)測(cè)中挑選這樣的預(yù)測(cè)，它是在某些約束條件下（通常是給定的某些隨機(jī)變量的分布）使信息熵達(dá)到極大值。這是因?yàn)樾畔㈧厝〉脴O大值時(shí)對(duì)應(yīng)的一組概率分布出現(xiàn)的概率占絕對(duì)優(yōu)勢(shì)。 在自然語(yǔ)言中的應(yīng)用S.Pietra、V.Pietra等人提出了一種基于最大熵原理的單詞聚類(lèi)方法，首次將最大熵理論應(yīng)用于自然語(yǔ)言處理。A.L.Berger、S.Pietra、V.Pietra等人比較詳細(xì)地介紹了最大熵的理論框架

8、，并介紹了其在基于統(tǒng)計(jì)的機(jī)器翻譯領(lǐng)域的一些應(yīng)用。S.Abney在統(tǒng)計(jì)屬性-值文法(Attribute-value Grammars)中使用最大熵進(jìn)行參數(shù)估計(jì)。李涓子、黃昌寧改進(jìn)了最大熵的特征選擇策略，并將其應(yīng)用于漢語(yǔ)的詞義消歧，取得了較好的效果A.Borthwick研究了基于最大熵的名實(shí)體(Named Entity)的識(shí)別 最大熵模型已知訓(xùn)練樣本集(x1,y1),(x2,y2),(xN,yN),其中x為輸入，y為輸出 指x出現(xiàn)的情況下，y的經(jīng)驗(yàn)概率，也就是y在樣本集中的概率。指x出現(xiàn)的情況下，y的實(shí)際概率。隨機(jī)事件的不確定性可以用條件熵來(lái)衡量：特征指x與y之間存在的某種特定關(guān)系，可以用一個(gè)輸出

9、為0或1的特征函數(shù)表示。 最大熵模型特征的經(jīng)驗(yàn)概率為所有滿(mǎn)足特征要求的(x,y)的驗(yàn)概率之和,即：特征的期望概率,也就是特征在我們所學(xué)習(xí)的隨機(jī)事件中的真實(shí)分布為： 最大熵模型選定的特征的重要性可通過(guò)下式體現(xiàn)：上 式表示，特征f的經(jīng)驗(yàn)概率與期望概率一致，當(dāng)樣本足夠多時(shí)，可信度高的特征的經(jīng)驗(yàn)概率與期望概率是一致的 約束集根據(jù)隨機(jī)事件的情況，約束等式可以有多組，約束等式的集合叫約束集，可表示為 最大熵模型最大熵模型，是滿(mǎn)足約束集條件的所有模型中熵最大的模型，即： 其中p為滿(mǎn)足約束集C條件的某一統(tǒng)計(jì)模型。因?yàn)榧s束集中的每一個(gè)特征的分布是最大似然估計(jì)，所以約束集中元素越多，統(tǒng)計(jì)模型從訓(xùn)練樣本中學(xué)得的越多

10、，其做出的預(yù)測(cè)也越依賴(lài)于樣本集。選擇特征較多時(shí)，滿(mǎn)足約束集要求的統(tǒng)計(jì)模型個(gè)數(shù)較少，當(dāng)把樣本中的所有(x,y)都作為特征時(shí)，模型唯一，為用極大似然估計(jì)求p(y|x)所建立的模型。 最大熵模型求解 最大熵模型求解問(wèn)題，實(shí)質(zhì)是一個(gè)約束條件下求極值的問(wèn)題。此類(lèi)問(wèn)題通常用拉格朗日乘子法確定。其中：求導(dǎo)后變換得 其中最大值可通過(guò)求 沒(méi)有解析解，Danroch 和Rateliff于1972年提出了一個(gè)稱(chēng)為GIS(Generalized Iterative Scaling Algorithm)算法133。D.Pietra等改進(jìn)了原有的最大熵模型求解算法，降低了求解算法的約束條件，提出了IIS(Improved

11、 Iterative Scaling Algorithm)算法，增加了算法的適用性，IIS算法是目前最大熵參數(shù)求解中的常用算法。 IIS算法IIS算法如下： 輸入：約束集， x，y的經(jīng)驗(yàn)概率分布 輸出：1、 初始令，2、 for i=1 to n 循環(huán)a) 令 為下面方程的解其中， 由(3-3)對(duì)f的定義可知在本文中為某一實(shí)例(x,y)包含的特征數(shù)量。b) c) 重復(fù) a)至 收斂3、 算法結(jié)束這里求解使用牛頓迭代法 迭代算法1 初始令 i=0, ai=023當(dāng) , i+, 循環(huán)至2，4算法結(jié)束, 為方程解， = 。最大熵統(tǒng)計(jì)模型的優(yōu)點(diǎn) 最大熵統(tǒng)計(jì)模型獲得的是所有滿(mǎn)足約束條件的模型中信息熵極大的模型。 其次最大熵統(tǒng)計(jì)模型可以靈活地設(shè)置約束條件。通過(guò)約束條件的多少可以調(diào)節(jié)模型對(duì)未知數(shù)據(jù)的適應(yīng)度和對(duì)已知數(shù)據(jù)的擬合程度。 另外最大熵模型還自然地解決了統(tǒng)計(jì)模型中參數(shù)平滑的問(wèn)題。 K近鄰（KNN）最近鄰分類(lèi)規(guī)則 對(duì)于測(cè)試樣本點(diǎn)x