Mark Chang's Blog

Machine Learning, Deep Learning and Python

Log-Linear Model

1. Introduction

在機器學習中有一種用於分類的演算法, 叫作 Logistic Regression , 可以把東西分成兩類

而在自然語言處理的應用, 常常需要處理多類別的分類問題, 像是 Part of speech Tagging 就是把一個字詞分類到名詞, 動詞, 形容詞, 之類的問題

如果二元分類的 Logistic Regression , 推廣到多種類別分類, 就可以處理這種分類問題

首先, 把二元分類的 Logistic Regression 公式, 稍做調整, 如下

針對多類別的 Logistic Regression , 叫作 Multinomial logistic regression , 如果總共有 的類別, 每個類別的 label 為 , 則公式如下

在自然語言處理中, 由於 feature value , 也就是 , 通常不是數字, 例如 前面幾個字的 Tag 之類的, 這時就要用 feature function 把 feature value 轉成數字

所謂的 feature function , 就像是一個檢查器, 去檢查 input data 是否滿足某個 feature , 滿足的話則輸出 1 , 不滿足者輸出 0 , 以下為一個feature function 的例子

其中 , 是前一個字的 Tag , 而 為這個字的類別, 如果這個字的類別是 , 且前一個字的 Tag 為 , 則 , 若不滿足這些條件, 則

加入 feature function 以後 , 原本的 變為 , Multinomial logistic regression 的公式變為這樣, 也就是所謂的 Log-Linear Model

再來, 要怎麼訓練這個 Model 呢？

Training 是一個求最佳解的過程, 要找到一組 Weight 可以使得 為最大值, 公式為

由於有時 feature function 的數量會太多, 容易導致 Overfitting , 為了避免此現象, 所以會減掉 以進行 Regularization

另外, 由於此最佳化後產生的結果, 會有最大的 Entropy , 故 Log-Linear Model 又稱為 Maxmum Entropy Model , 在此做不推導, 欲知詳情請看 Berger et al. (1996). A maximum entropy approach to natural language processing.

2. Example

舉個例子, 如何用 feature function 算出 Tagging 的機率值

假設現在要對以下句子進行 Part of Speech Tagging , 現在已經進行到了 race 這個字

總共用了以下六種 feature function

現在要求 race 這個字的 Tag 是 NN 還是 VB , 代入以上六個 feature function , 得出結

果於下表

其中 是 feature function 算出來的值, 是 weight , 這個值通常是針對 Training Data 做最佳化得出來的值, weight 越大則表示 feature 所占的比重越重

接著把 的值帶入公式

算出結果 , 所以 race 的 Tag 為 VB

3. Implementation

接著來實作用 Log-Linear Mode 進行 Part of Speech Tagging

這次要用 python nltk 的 MaxentClassifier 來實作

首先, 開一個新的檔案 loglinear.py 貼上以下程式碼

loglinear.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

import nltk
import operator

class LogLinearTagger(nltk.TaggerI):

    def __init__(self,training_corpus):
        self.classifier = None
        self.training_corpus = training_corpus

    def train(self):
        self.classifier = nltk.MaxentClassifier.train(
                    reduce(operator.add,
                        map(lambda tagged_sent :
                            self.sent_to_feature(tagged_sent)
                            ,self.training_corpus)),algorithm='megam' )

    def sent_to_feature(self,tagged_sent):
        return  map(lambda (i, elem) :
                        apply( lambda token , tag :
                             (self.extract_features(token, i, tag), elem[1])
                            ,zip(*tagged_sent))
                        ,enumerate(tagged_sent))

    def tag_sentence(self, sentence_tag):
        if self.classifier == None:
            self.train()
        return apply (lambda sentence :
                    zip(sentence,
                    reduce(lambda x,y:
                        apply(operator.add,
                            [x,[self.classifier.classify(self.extract_features(sentence, y[0], x))]])
                        , enumerate(sentence), []))
                    ,[map(operator.itemgetter(0),sentence_tag)])

    def evaluate(self,test_sents):
        return apply(lambda result_list :
                    sum(result_list)/float(len(result_list))
                    , [reduce(operator.add,
                        map(lambda line:
                            map(lambda tag : int(tag[0] == tag[1])
                                , zip(map(operator.itemgetter(1),line),
                                      map(operator.itemgetter(1),self.tag_sentence(line))))
                           ,test_sents))])

    def extract_features(self, sentence, i, history):
        features = {}
        features["this-word"] =  sentence[i]
        if i == 0:
            features["prev-tag"] = "<START>"
        else:
            features["prev-tag"] = history[i-1]
        return features

其中, extract_features 是用於把 input sentence 的 feature 取出來, 例如這次用到的 feature 有目前這個字是什麼 "this-word" ,和前一個字的 Tag 是什麼 "prev-tag"

取出 feature 後 , MaxentClassifier 會自動根據這些 feature 產生 feature function

接下來到 python 的 interactive mode 載入檔案

1

>>> from loglinear import LogLinearTagger

這次要用 brown corpus 的 category , news 的前 100 句來當作 Tranining Data ,第 100~200 句當作 Test Data , 先輸入以下程式碼

1
2
3
4

>>> from nltk.corpus import brown
>>> brown_tagged_sents = brown.tagged_sents(categories='news')
>>> train_sents = brown_tagged_sents[:100]
>>> test_sents = brown_tagged_sents[100:200]

接著用 Training Data 建立一個 LogLinearTagger 的 class

1

>>> classifier = LogLinearTagger(train_sents)

在開始訓練之前, 我們先挑其中的一句, 看一下格式, 是已經 Tag 好的句子 , 我們以 train_sents[31] 為例

1
2
3

>>> train_sents[31]
[('His', 'PP$'), ('petition', 'NN'), ('charged', 'VBD'), ('mental', 'JJ'), \
('cruelty', 'NN'), ('.', '.')]

看一下這句可以產生出哪些 Feature

1
2
3
4
5
6
7
8
9

>>> for x in classifier.sent_to_feature(train_sents[31]):
...     print x
...
({'prev-tag': '<START>', 'this-word': 'His'}, 'PP$')
({'prev-tag': 'PP$', 'this-word': 'petition'}, 'NN')
({'prev-tag': 'NN', 'this-word': 'charged'}, 'VBD')
({'prev-tag': 'VBD', 'this-word': 'mental'}, 'JJ')
({'prev-tag': 'JJ', 'this-word': 'cruelty'}, 'NN')
({'prev-tag': 'NN', 'this-word': '.'}, '.')

例如第一個字, 'His' , 它的 feature 有 'prev-tag': '<START>' 和 'this-word': 'His' , Tag 的結果為

'PP$' , 由於第一個字前面已經沒有字了, 也沒有 Tag 了, 所以我們用 <START> 來表示

再來就是要訓練 classifier, 執行 classifier.train() 就可以開始訓練, 但要花一點時間

1
2
3
4
5
6
7
8
9
10

>>> classifier.train()
Scanning file...2268 train, 0 dev, 0 test, reading...done
optimizing with lambda = 0
it 1   dw 5.348e-01 pp 4.19728e+00 er 0.79850
it 2   dw 3.179e+00 pp 3.32097e+00 er 0.82760
it 3   dw 1.037e+00 pp 2.92326e+00 er 0.67549
it 4   dw 9.602e-01 pp 2.72106e+00 er 0.63933
it 5   dw 1.345e+00 pp 2.41257e+00 er 0.54012
it 6   dw 1.378e+00 pp 2.16177e+00 er 0.46429
......

如果出現以下錯誤訊息, 表示你沒安裝 megan

1
2
3
4
5
6
7
8
9
10

raise LookupError('\n\n%s\n%s\n%s' % (div, msg, div))
LookupError:

===========================================================================
NLTK was unable to find the megam file!
Use software specific configuration paramaters or set the MEGAM environment variable.

  For more information, on megam, see:
<http://www.cs.utah.edu/~hal/megam/>
===========================================================================

請到 http://www.umiacs.umd.edu/~hal/megam/version0_91/ 下載 megan

如果你是 linux 的使用者, 可直接下載執行檔, 放到 /home/xxxxxx/bin/ 資料夾 ( 若你是使用 Mac 或 Window$ , 則需要下載 source code 自行編譯

或者你可以把 loglinear.py 中的 MaxentClassifier 的 ` algorithm=’megam’ ` 去掉 , 變成這樣

loglinear.py
1
2
3
4
5

    self.classifier = nltk.MaxentClassifier.train(
                reduce(operator.add,
                    map(lambda tagged_sent :
                        self.sent_to_feature(tagged_sent)
                        ,self.training_corpus)) )

但這會導致訓練速度變得很慢

訓練好之後, 可以用 Test Data 看看結果如何 , 先挑一句, 以 test_sents[10] 為例

1
2
3
4

>>> test_sents[10]
[('``', '``'), ('You', 'PPSS'), ('take', 'VB'), ('out', 'RP'), ('of', 'IN'), \
('circulation', 'NN'), ('many', 'AP'), ('millions', 'NNS'), ('of', 'IN'), \
('dollars', 'NNS'), ("''", "''"), ('.', '.')]

把這個句子放到訓練好的 classifier , 用它來 Tag , 比較一下跟原本的 tag 有何不同 

1
2
3
4

>>> classifier.tag_sentence(test_sents[10])
[('``', '``'), ('You', 'VB'), ('take', 'VB'), ('out', 'RP'), ('of', 'IN'), \
('circulation', 'JJ'), ('many', 'AP'), ('millions', 'NNS'), ('of', 'IN'), \
('dollars', 'JJ'), ("''", "''"), ('.', '.')]

先用肉眼觀察, 我們發現 classifier 所得出的 Tag 有些和原本的一樣, 有些不一樣, 表示 classifier 有些字 Tag 錯了

可以用程式來算準確率, 用 classifier.evaluate , 但注意的是, input argument 不是 sentence , 而是 list of sentence , 所以 input argument 要用 [test_sents[10]] , 如下

1
2

>>> classifier.evaluate([test_sents[10]])
0.75

算出來後準確度是 0.75 , 也就是說有 75% 的 Tag 是正確的

再來把所有的 Test Data 都做 Evaluation 看看

1
2

>>> classifier.evaluate(test_sents)
0.6910327241818954

得的準確率約為 69.1%

這樣的準確率不是很理想, 原因是因為 100 句的 Training Data 實在是太少了

有興趣者可以試試看, 取 2000 句的 Training Data , 準確度應該會大幅提昇, 但是要花很久的時間訓練

3. Furtuer Reading

本文參考至這本教科書

Speech and Language Processing

以及台大資工系 陳信希教授的 自然語言處理 課程講義

Comments