機器學習文本分類Improved Iterative Scaling算法以及JAVA實作

IIS算法數學理論

背景

IIS算法主要用來計算參數估計的maximum-likelihood。 這篇文章主要是解讀Adam Berger的算法( IIS Algorithm)。首先這裡采用的是機率模型。

其中

參數解釋：

：表示再輸入文檔是x的情況下，輸出label為y的機率。(在Adam的文章中這個是表示language modeling的一個句子機率問題，但是這裡用于文本分類)。y就是你的模型中會包含有多少個的label，然後去判斷你輸入的文檔屬于每個label的機率，當然機率最大的就會判斷哪一個。

：這個其實就是我們用IIS算法訓練出來的權重，i的範圍就是1到n，n就是你的所有training dataset 裡面的feature總數。

：就是feature function了。我這裡feature function的定義就是，如果在一篇文章裡 word[i] 屬于 document x并且 word[i] 也屬于label y就為1，否則為0.

：是用在标準化的，使得機率在0到1之間。

：這個是表示

 .

Improved Iterative Scaling算法

Maximum-likelihood

首先我們構造基于對數的log-likelihood.

這裡的

 表示<x,y> pair出現在dataset中的機率，一般都是

.。 然後具體的推導不在這裡詳細詳述，推導可以看adam上的論文，我這裡直接把結果給出來。因為要求最大的可能性，是以我們需要求這個公式的最大值，就是說對這個公式就導，求導的話，因為

有n個值，是以就要求n次偏導數。進而求到每一個的

.

因為這個式子優化還是比較麻煩，是以Adam文章中采用辦法就是一點一點的疊代。原理就是如果我們能夠找到一個

使得下面的式子成立就可以了。

而且又有

是以隻需要上式右邊的式子大于0即可，可以看到現在要求的變量變成了

。 然後論文最後，再繼續優化上式，得到一個式子可以單獨的求取

，如下：

其實就是表示在<x,y>這個pair中的所有的feature，在文本分類模型中，就是總共有多少種feature(注意不是多少個.)

因為這裡可能每一個的

都會不一樣，是以可能需要用牛頓疊代求解的方法去求解

。但是，其實有兩篇文章(忘了什麼名字了)都證明隻需要取最大的

來代替就可以了，就是說我們希望計算的友善。

是以我們這裡選擇：

 針對所有的x 和y.

最後可以得到

的表達式：

IIS算法流程

第一步，随便選擇

，一般初始化每一個都是0.

第二步，不斷執行一下的操作收斂為止，一般很快。

-----求解

， 用上面最後推導出來的式子

-----Set 

算法的實作和模型訓練測試

這裡因為代碼太長不可能完全放出來，是以打算講解一部分的核心代碼然後把完整代碼和資料都放到出來大家下載下傳好了。

首先是feature function的定義。

/**
 * feature function
 * wordInLabel[c] is a map, to denote that if this word is also in this label.
 * Note: a word can belongs to many labels.
 * allFeature List has contained all the words in training dataset
 * @param i: denote the word[i] in document d
 * @param d: doc[d], the number of this document
 * @param c: the label of this document
 * @return
*/
private int featureFun(int i,int d,int c){
        
        if(doc[d].getDoc().containsKey(allFeature.get(i)) && wordInLabel[c].containsKey(allFeature.get(i)))
            return 1;
        else return 0;
}
           

doc 是我定義的一個document的結構，這個結構裡面包含一個 map<word,value>容器的document, key是單詞，value是這個單詞在這個document中出現的次數。這個結構另外一個成員就是label. 就是這篇document的label.主要是用在訓練過程中，測試過程不需要。

接下來直接上訓練階段的核心代碼，就是不停疊代求解

然後更新

的過程。

/**
     * Train the data.
     * getExponentialProb(x,y) function is used to calculate p(y|x)
     * lamda[] is the final weight coefficients we can get.
     * @param times: the iteration time, depends on your choice
     */
    private void trainData(int times){
        lambda = new double[allFeature.size()];
        double[] delta = new double[allFeature.size()];
        for(int t=0;t
                  

上面的 this.NUMERTOR[I]是因為我們仔細看上一部分求的

，顯然分子和

是沒有關系的，是以我已經預處理在另外一個方法中計算存儲起來，這個也是空間換時間的一個概念。 在測試階段，我通過預測每個label的機率然後進行比較，得到機率最大的那個label. 先給出測試的代碼，然後最後給出結果。

/**
     * Get the error rate, remember run the startUp function first
     * Get the error rate of our model.
     */
    public void testModel(){
        int ein = 0;
        for(int d=0;d
       
           

測試資料采用的是 Reuter21578的資料，用了其中的4種類型，acq, coffee, fuel and housing. Best:：就是這個算法中預測出來的最好的，就是機率最大的。True：就是真正測試中的結果。

coefficient vector size:1728
acq[0.3559] coffee[0.3012] fuel[0.2457] housing[0.0972]     Best:acq   True:acq
acq[0.2893] coffee[0.2815] fuel[0.2438] housing[0.1853]     Best:acq   True:acq
acq[0.2704] coffee[0.2562] fuel[0.2565] housing[0.2170]     Best:acq   True:acq
acq[0.3340] coffee[0.2252] fuel[0.2659] housing[0.1749]     Best:acq   True:acq
acq[0.2990] coffee[0.2590] fuel[0.2466] housing[0.1955]     Best:acq   True:acq
acq[0.2904] coffee[0.2416] fuel[0.2544] housing[0.2136]     Best:acq   True:acq
acq[0.2978] coffee[0.2767] fuel[0.2406] housing[0.1848]     Best:acq   True:acq
acq[0.3844] coffee[0.2638] fuel[0.2282] housing[0.1236]     Best:acq   True:acq
acq[0.2855] coffee[0.3156] fuel[0.2547] housing[0.1442]     Best:coffee   True:coffee
acq[0.2486] coffee[0.2780] fuel[0.2744] housing[0.1989]     Best:coffee   True:coffee
acq[0.2407] coffee[0.2871] fuel[0.2596] housing[0.2126]     Best:coffee   True:coffee
acq[0.2788] coffee[0.2859] fuel[0.2580] housing[0.1773]     Best:coffee   True:coffee
acq[0.2518] coffee[0.2501] fuel[0.2518] housing[0.2464]     Best:acq   True:coffee
acq[0.2850] coffee[0.2646] fuel[0.2532] housing[0.1972]     Best:acq   True:coffee
acq[0.2348] coffee[0.2692] fuel[0.2735] housing[0.2224]     Best:fuel   True:coffee
acq[0.2382] coffee[0.2678] fuel[0.2727] housing[0.2214]     Best:fuel   True:coffee
acq[0.2548] coffee[0.2632] fuel[0.2859] housing[0.1962]     Best:fuel   True:fuel
acq[0.2733] coffee[0.2613] fuel[0.2541] housing[0.2113]     Best:acq   True:fuel
acq[0.2844] coffee[0.2530] fuel[0.2727] housing[0.1899]     Best:acq   True:fuel
acq[0.2421] coffee[0.2345] fuel[0.3366] housing[0.1867]     Best:fuel   True:fuel
acq[0.2579] coffee[0.2519] fuel[0.3093] housing[0.1809]     Best:fuel   True:fuel
acq[0.2435] coffee[0.2466] fuel[0.3049] housing[0.2050]     Best:fuel   True:fuel
acq[0.2871] coffee[0.3343] fuel[0.2452] housing[0.1334]     Best:coffee   True:fuel
acq[0.2738] coffee[0.2191] fuel[0.3157] housing[0.1914]     Best:fuel   True:fuel
acq[0.2450] coffee[0.2397] fuel[0.2450] housing[0.2702]     Best:housing   True:housing
acq[0.2202] coffee[0.2054] fuel[0.2335] housing[0.3409]     Best:housing   True:housing
acq[0.2350] coffee[0.2372] fuel[0.2393] housing[0.2885]     Best:housing   True:housing
acq[0.2340] coffee[0.2361] fuel[0.2382] housing[0.2917]     Best:housing   True:housing
acq[0.3156] coffee[0.2897] fuel[0.2219] housing[0.1728]     Best:acq   True:housing
acq[0.2340] coffee[0.2238] fuel[0.2475] housing[0.2947]     Best:housing   True:housing
acq[0.2431] coffee[0.2383] fuel[0.2481] housing[0.2706]     Best:housing   True:housing
acq[0.2525] coffee[0.2460] fuel[0.2737] housing[0.2278]     Best:fuel   True:housing
error rate is:0.28125
accuracy: 71.75%
           

其實做了另外一個實驗發現用binary classification 的結果更好，就是首先預測 acq- not acq coffee - not coffee fuel - not fuel housing -not housing. 然後最後在combine 這四個結果，得到的準确率會更高。

最後其實我也把IIS模型和 maxent裡面已經實作了的GIS模型對比了，發現GIS的收斂的确比IIS慢一點，但是GIS的疊代速度更快。我覺得可能是我的算法寫的不好，比較慢。有興趣的可以嘗試用用OPENNLP 的maxent 包。

代碼和資料下載下傳

因為我貌似沒有找到上傳附件的地方，是以我放到百度雲上讓大家下載下傳吧，下面是連接配接。 http://pan.baidu.com/s/1bnf7BZL 謝謝您的閱讀，希望有問題可以一起讨論。