自然語言處理 Project

Polarity Analysis for Sentiment Classification

Stop Word List

This stopword list is probably the most widely used stopword list. It covers a wide number of stopwords without getting too aggressive and including too many words which a user might search upon. This wordlist contains only 11 words.

1
2
3
4
5
6
7
8
9
10
11
the
i
it
he
she
they
we
you
-
a
an

比起其他網路上的 stop word list 少了很多介系詞,原因是這樣的,例如 who, whom, where, ... 這些詞作為描述對象的主體,這些主體通常不可省略。例如在描述『演員很不錯,但是電影劇本很糟糕。』這段話時,根據實驗的幾種模型,如果忽略主體的存在,很容易造成描述的需求面向錯誤。必然地,無法將 movie, film 過濾掉,主體是相當重要的,即使他在單一詞的極性上不夠明確。

Parsing Sentence

首先,必須把所有縮寫單位展開,當然有可能把錯誤的 Bob's 展開成錯誤的意思,實驗上不構成多大的影響,但以下的操作會更明確地把潛在的 feature 更清楚地劃分,而不會挑到已經重複的。

1
2
3
4
5
6
7
8
`can't` = `can not`
`n't` = ` not`
`'re` = ` are`
`'m` = ` am`
`'s` = ` is`
`'ve` = ` have`
`'ll` = ` will`
... maybe more

再來,必須針對符號轉英詞,有可能是在描述電影名稱會用到 &,一律將其轉換成 and 會更有效。

1
`&` = ` and`

最後,語法上的變換統一。這可能會遭遇到描述『過去的版本很好,現在這個版本很糟。』也許規則應該對時間做點細部劃分。

1
2
3
`am, are, is, was, were` = `be`
`no` = `not`
`film` = `movie`

更多的口語描述,例如 uuuuuuuugggggggggglllllllllllyyyyyyy = ugly 的可能,特別針對 long duplicate word 特別處理,查看濃縮之後,是否會在字典中。狀聲詞 oh, wow, ah, ... 可能是一個極性指標,在此就不濾掉這幾個單詞。

當使用 stop word 過濾某一個句子時,剩餘的詞應該串在一起成為新的句子,而不以 stop word 分開成新的句子。

Filter N-grams Feature

在挑選 n-grams 時,根據給定的公式,從 800 正向評論、800 反向評論中,大約會得到 50M ~ 100M 不同的 n-grams。當我們篩選 n = 3 時,bad 將可能被儲存為 (bad, null, null)。挑選時,必須保障 high order n-grams 佔有一定的數量,大約落在 n-grams : (n+1)-grams = 7 : 3

評分時,額外增加 high order 的評分權重,以下是程式中使用的分配。

1
N-grams Bonus = {1, 1.02, 1.03, 1.04, 1.05, 1.06, 1.07};

這麼做確保實驗上有保留之前的優良,同時也增加新的元素進去。

當挑選 K-top feature 時,必須將正反兩方的 feature N-grams 分別佔有約 50%,並且去掉同時挑到的情況。

更多的策略,例如 (bad, too, null) 可以視為 (too, bad, null),使用 dag 的方式紀錄 N-grams。

How To Decide K-top

明顯地觀察到,K 越大時,Language Model 越穩定,平均效能穩定,但最好效能可能會下降,對於 Winnow algorithm 或者是 Passive-Aggressive algorithm 來說,feature vector 會非常大,造成在找到合適的參數會消耗更多的時間,並且難在有限的迭代次數中找到好的切平面。

當 K 很大時,部分的 n-grams 甚至只出現在某些的 training set 中,這造成訓練 Winnow, Passive-Aggressive 的結果並不好,過於分配無用的權重給只出現在 training set 的 feature。在實驗中,挑選 K = 30000 與 K = 50000 的差異並不大,挑選的比例約為 5% 以內。

Improve

LM Classifier

關於論文中提到的 LM filter,試圖去替除掉一些主觀句子,根據每一個句子進行閥值的評測,實驗中測試到非常低的值作為閥值才具有較好的可能性,由於太高、太低都會使得準確度下降,估計這個閥值的調整不具有普遍性。

而其他的 Classifier 並沒有做這類的主客觀篩選,也許可以藉由主客觀句子的判斷做一套分類器,說不定可以改善另外兩個分類器的語意判斷能力。

Combine Classifier

發現到 Winnow, Passive-Aggressive (PA) 都是以閥值作為判斷標準,因此當得到靠近閥值的數據下,判斷能力是相當脆弱。雖然 PA 在平均表現最好,大約落在 85% 附近,遠比 LM 和 Winnow 多了 5% ~ 10% 的準確度,如何加強?

將四個 Classifier 串在一起,並且用八個 attribute 作為一個 feature vector,接著訓練這一個感知機。這八個 attribute 分別是每一個 Classifier 的判斷強度。

1
(LM_POS, LM_NEG, WINNOW_POS, WINNOW_NEG, PA_POS, PA_NEG, SIMPLE_POS, SIMPLE_NEG)

其中由於 Language Model (LM) 的機率不好量化,因此單純採用 0/1 的方式表示。嘗試過取 log 發現仍然並不好。

  • LM_POS : if LM.classify(x) = POS, then LM_POS = 1. Otherwise LM_POS = 0
  • LM_NEG : if LM.classify(x) = NEG, then LM_NEG = 1. Otherwise LM_POS = 0
  • WINNOW_POS : if Winnow.classify(x) = POS, the WINNOW_POS = Winnow.strongClassify(x).
  • WINNOW_NEG : if Winnow.classify(x) = NEG, the WINNOW_NEG = Winnow.strongClassify(x).

strongClassify(x) 從 training data 中得到 h(x) 的出現的最大值,然後根據將判斷的函數大小得到,strongClassify(x) = h(x) / TRAINING_MAX_H_VALUE,之所以不直接使用 strongClassify(x) = h(x) 是因為很容易造成 overflow 或者是過度的調整判斷。在實驗結果後,將後者公式調整為前者所使用的。

當然可以訓練多台,並且串在一起,但是這種串法必須盡可能有所歧異性,並不是串越多越好,可以藉較少次的迭代次數、洗牌後的訓練序列來達到歧異性。PA 具有良好的適應性,在訓練集與測資集大小、差異不大時,效能仍然可以保持著線性關係,相當具有魯棒性。

在實驗觀察中可以明白感知器在越少 feature 下,可以在越少迭代次數中訓練完成,相對地適應能力就會隨差異嚴重波動,實驗中使用的幾個感知機模型,都能在 vector 得到後的幾秒內完成訓練,不用勞費 SVM 的數個小時。Language Model 則會因為 feature 越多,展現更加穩定的效能,即便如此,LM 在負面評論的辨識率仍然不高,這一點從論文中也可以看得出具有相同的現象。

藉此把 LM 對於負面評論辨識率很差的特性,才將其判斷與其他的感知機串在一起使用。這一類的串許多的分類器的算法,可以參照 Adaboost (Adaptive Boosting) 的想法。

N-grams Score

特別小心公式的計算,雖然有很多乘除法,可以使用 Math.log 降下來,防止 overflow 的可能,但同時也會造成嚴重的浮點數誤差。所以使用恰當的 double 運算即可,即使遇到 NaN 也沒有關係。

論文中提及的公式,額外增加變成

$\chi^{2}(t, c) = \frac{N \times (AD - CB)^{2} }{(A+C)\times (B + D) \times (A + B) \times (C + D)} \times Weight[t.getSize()] \times Score(t)$

其中,Weight[t.getSize()] 正如上述的 N-grams Bonus,當最大上為 n = 5 時,部分 unigram、bigram 仍然有用。而 Score(t) 則是取額外資料中的 AFINN-111.txt 單詞正反面的絕對值權重和,有可能正負兩個詞合併成 bigram 來描述更強烈的負面,因此必須取絕對值。

Vector

選擇 K-top feature n-grams 後,感知機的 Vector 如何放置權重仍然是個困難,從實驗中,單純拿 n-grams appear times 作為一個 attribute weight 效果並不好,於是嘗試拿 Math.log(n-grams appear times),但是效果並不好,有可能是浮點數誤差造成的差異並不大,而 Math.log 本身就很小,尤其是 n-grams appear times = 1 的時候會變成 0,額外加上一個基底 base 來補足也拿以取捨。

最後取用

$vector[i] = Score(ngrams(i)) + \sqrt{n-grams(i) \text{ appear times}}$

這部分仍然要做實驗,Score(ngrams(i)) 大約落在 1 ~ 10 之間。

Process

經過幾次的 cross validation 後,每一次會挑到不同的 feature n-grams,藉由交叉驗證得到不同的精準度 P,同時也將挑選的 n-grams 增加 P 的權重,在實驗中總共做了 5 次 cross validation,針對同一組 800 資料,進行 1 : 1 的劃分。原本預期挑選 40K 個不同的 n-grams 作為 feature,但是經過 5 次實驗,總共得到 50K 個不同的 n-grams,根據累加的 P 值進行由大排到小,挑選 1/5 的 n-grams 出來,最後挑了少於 10K 個做為 feature。

針對已知的 1600 筆資料進行 3 : 1 的劃分,先對數量較多的資料重訓練,隨後才將數量較少放在一起做第二次訓練。防止過度的訓練,導致感知器針對訓練集的已知資訊分配過多的權重,反而針對未知的元素不足以判斷。

extra data support

  • AFINN-111.txt
  • positive word list (ignore) 毫無幫助
  • negative word list (ignore) 毫無幫助
  • negation not (ignore) 目前發現只會更糟糕

程式撰寫

N-grams Storing

stringinteger 標記。

How to improve experiment

先用同一份資料訓練、測試,查看是否接近 P = R = 100%,接著放入未知的資料,找到挑選 feature n-grams 之間的差異。

列出幾個可能的差異後,從訓練的感知機中得到每一項的權重,由於是線性分類器,權重的大小即可作為是否具有特色,通常差距會達到 10 ~ 100 倍之間。即使從 N-grams score 得到較高的分數,從感知機中會發現到未必是較大的權重,有可能是某幾篇相關的電影所造成的一面倒。

Pseudocode

preprocess

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
gobal_record(n-grams, score)
for i = 0 to CROSS_VALIDATION_MAX
shuffle_order(training_data)
(ttraining, ttest) = split(training_data, 1 : 1)
Vectraining = n-grams_sieve(ttraining)
(LM, Winnow, PA) = training(Vectraining)
P = test(LM, Winnow, PA, Vectraining)
gobal_record.add(P, Vectraining)

sort gobal_record(n-grams, score) by descending order.
shuffle_order(training_data)

(ttraining, tretain) = split(training_data, 4 : 1)
N-gramsTable = gobel_record.sublist(K)
Vectraining = parsingInput(ttraining,, N-gramsTable)
Vecretain= parsingInput(tretain,, N-gramsTable)

(LM, Winnow, PA) = training(Vectraining)
(LM, Winnow, PA) = retraining(Vecretain)

simpleTest(testdata, LM, Winnow, PA)
onlineTest(testdata, LM, Winnow, PA)

online test

1
2
3
4
5
6
7
GROUP_SIZE = 50
groups = splitEach(testdata, GROUP_SIZE)
foreach(group : groups)
appear set = find(group, N-gramsTable)
(LM, Winnow, PA) = retrainingLimited(Vectraining, appear set)
foreach(data : group)
classify(LM, Winnow, PA, data)

fail online test idea

1
2
3
4
5
6
7
8
GROUP_SIZE = 10
groups = splitEach(testdata, GROUP_SIZE)
foreach(group : groups)
backtracking 210 possible solution
training & test
if (better performance)
record solution.
Work, but not helpful.

Support N-grams Sieve

  • AFINN-111.txt
    The file AFINN-111.txt contains a list of sentiment scores
  • Stop word list
    Small set, |S| < 20
  • Synonymous “Not” list
    unused
  • Abbreviation list
    Rule, |R| < 10
  • No CRF, No Parsing tree, No Subjective filter

To Do

增加兩個不在 top feature 中的 attribute,但是在 pos/neg word weight 中的 n-grams 所評分的結果。在量化這些 n-grams 的分數時,不管正反面的強度,一律取絕對值進行加總,有可能一個正面單詞跟一個負面單詞合併在一起來表示一個更強烈的正面或反面資訊。

Training Classifier with 5000 subjective and 5000 objective processed sentences.

實作判斷主觀、客觀的分類器。

http://www.cs.cornell.edu/People/pabo/movie-review-data/

Github

感謝。

Read More +

自然語言處理 論文研讀 2

著重目標

即使 Unigram 效果已經相當不錯,基於人類日常對話的模式,絕非單詞相依無關,藉由好幾個連詞表示出不同的意思是常有的事情,探討 n-grams (n > 3) 對於當前的語意分類器的強化、優化。

已知問題

當 n-grams (n > 3) 時,語意的模糊性質會提高,可能同時把正反兩面的詞放置在一起,如此一來這一組的利用價值並不高,在計算分類上會將精準度稀釋,同時對於記憶體的負荷也會增加 (必須記錄各種組合,例如化學元素與化合物的數量大小關係)。

接著 n-grams 通常是用在英文處理精準度比較好,因為 單詞分明 (藉由空白隔開),對於機器而言中文句子並不存在詞 (token),都是一堆字元 (character)。

研究顯示: 漢字順序並不一定影響閱讀

請看下述文字-研究顯示:漢字序順並不定一影閱響讀。

對於中文自然語言處理,斷詞的重要性、語意處理上有額外的研究領域,在這裡暫時不談論這些。也許可以談談看不考慮順序的 n-grams,型態從 tuple 變成 dag。

分類器

分類器分成線上訓練、離線訓練,就已知得到目前 SVM 仍然在實務上的效果是最好的,在這裡不談論 SVM,一部分原因是 SVM 太慢。

下面是在不同領域的分類器構思,線上訓練、線性調整。大多數的分類器都必須定義特徵,對於每一個要分辨的項目是否存有這一個特徵 (boolean),而在部分可允許模糊的模型,可以利用權重 (float) 表示特徵強弱。

類神經網路

Passive-Aggressive Algorithm

對於感知機的內容所知不多,每加入一筆結果,將劃分的依準疊加上預期的法向量,成為新的劃分依準線。大多依靠數學的微積分來完成,並非完全相信新加入的結果,因此會有一個計算的權重,來權衡影響的大小。

訓練流程:

$$\begin{align} & \text{INITIALIZE : } w_{1} = (0 ... 0) \text{ as parameters of the classifier} \\ & \text{For } t = 1, 2, ... \\ & \text{receive instance : } x_{t} \in R^{n} \\ & \text{predict : } \hat{y_{t}} = sign(w_{t}, x_{t}) \\ & \text{receive correct label : } y_{t} \in {-1, +1} \\ & \text{suffer loss : } l_{t} = max\left \{ 0, 1 - y_{t}(w_{t} \cdot x_{t}) \right \} \\ & \text{update-1: set : } \tau_{t} = \frac{l_{t}}{\left \| x_{t} \right \|^{2}} \\ & \text{update-2: update : } w_{t+1} = w_{t} + \tau_{t} y_{t} x_{t} \end{align}$$

自然語言

Language Modeling

就如上課內容所講的

$$\begin{align} P(s) = \prod_{i = 1}^{l} P(w_{i}|w_{1}^{i-1}) \end{align}$$

用 Good Turing 的方式去 smoothing 那些從未在模型中出現的詞語,它們是有機會的,絕非是機率 0。

機器學習

Winnow algorithm

設定一個閥值作為是否存在此分類的依據,隨後根據閥值調整相關數據的參數大小。

$h(x) = \sum_{w \in V}^{} f_{w}c_{w}(x)$ $f_{w}$ 是需要調整的參數$c_{w}(x)$ 為資料在每一個特徵的權重向量,運算內積值為$h(x)$

訓練流程:

$$\begin{align} & \text{Initialize all } f_{w} \text{ to 1.} \\ & \text{For each labeled revies x in the training set : } \\ & \text{Step 1. Calculate } h(x) \\ & \text{Step 2-1. If the revies is positive but Winnow predicts it as negative } \\ & h(x) < V \text{ , update the weight} f_{w} \text{ where } c_{w}(x) = 1 \text{ by } f'_{w} = f_{w} \times 2 \\ & \text{Step 2-2. If the revies is negative but Winnow predicts it as positive } \\ & h(x) > V \text{ , update the weight} f_{w} \text{ where } c_{w}(x) = 1 \text{ by } f'_{w} = f_{w} / 2 \\ \end{align}$$

簡單來說,當判斷錯誤時,將相關的 (它有的) 特徵係數權重調整,將其變大使得納入分類中、或者將其變小踢出分類中。

調和

為了加入 n-grams (n > 3) 的機制,必然要學習 忘記 無視 的才能,才能將垃圾訊息給捨去掉。同時也是降低記憶體的耗存的方法,這裡無法像人類有辦法根據時間將單詞組合抽象化,等到哪天 HTM 腦皮質學習算法 成功實作,相信在取捨上會更為流暢。

對於每一個特徵給予分數,保留前 K 好的特徵進行訓練,其餘特徵捨去,至於要保留的 K 大小將由實驗結果進行測試。

分數計算:

  • A:同一分類下,該屬性使用的資料筆數
  • B:在其他分類下,該屬性被使用的資料筆數
  • C:同一分類下,該屬性不使用的資料筆數
  • D:在其他分類下,該屬性不被使用的資料筆數
  • t:屬性
  • c:分類
$$\begin{align} x^{2}(t, c) = \frac{N \times (AD - CB)^{2} }{(A+C)\times (B + D) \times (A + B) \times (C + D)} \end{align}$$

結論

論文中提到,分別去了 50K、100K、200K 個分數高的 n-grams,又分別在 n = 3, 4, 5, 6 下進行測試,效果有那麼一點點地提升。

接著就是考驗我們期末 Project 要怎麼體現這篇論文的思路、擴充。

Read More +

自然語言處理 論文研讀 1

Introduction

語意分析涉及正反意見在文字語句中判定,因此必須使用多方視角看待問題與答案,這一點在之前,有人做過意見導向的資訊萃取、資訊摘要 (於文件、語句、片語)。語意分析通常分為三個階段, 校準 辨識 分類 所有已經讀取的文句。這篇論文探討文件分級 (document-level) 的分析,將會著重分析 特定類型的評論文件

第一個問題-極性分類 (polarity classification),對於目標決策正極性 (贊同) 或者是 負極性 (反對),最近也在擴大到中性文件的分類上,雖然研究成果相當多且廣,極性分類仍然是自然語言處理系統中重大的挑戰。

接著將會著重於語言學上的極性分類。在語言學中,建立一個高校的極性分類透過:

  • high order n-grams
  • 複合形容詞,例如 happy 被視為正,而 terrible 視為負面。
  • 詞彙的相依關係
  • 來自於中立文件中所描述的詞組

… 本文略

主要是極性分類,反映正反兩方兩種評論,為了增加精準度,其一種方法把單純闡述事實的評論去除、以及在中性評論用的用詞特別處理,接著對於形容詞與關聯名詞做統計,確保面向的評論對象是所需。

至於 n-gram 部分,有說明到 n 越大,將會造成模糊範圍增加,這樣一來其極性價值就會被削減,對於精準度是會掉的,只用 n = 2 好不好?他說他複合使用 n = 2 和 n = 3 將精準度提升,看到所謂顯著 2% 上升,似乎跟誤差無仿。

Read More +

自然語言處理 - HW02

編譯環境

Dev-C++ 5.6.3

作業內容

給予 5000 筆的亞馬遜書店評論,每一個評論都已經分類好,總共有五種類型的書評,分別為 book, dvd, health, music, 以及 toys_games

利用這 5000 筆分類好的書評寫一個分類器,接著讀入另外測試資料,測試資料每一個書評有既定分類,使用分類器判斷是否符合既定分類,分別計算對於每一種分類書評的準確度 (Accuracy) 和精準度 (Precision)。

  • 準確度:接近正確答案的機率,在這裡可以理解為分類出來的結果等於實際結果的機率。
  • 精準度:測試結果一致的機率,在這裡可以理解為分類出來的結果中,實際上是正確的機率。(是否集中於某個實際結果)

還有一個混用準確度和精準度的概念 f,假設準確度為 R,精準度為 P。

$F = \frac{1}{\alpha \frac{1}{P} + (1 - \alpha) \frac{1}{R}} = \frac{(\beta^{2} + 1) PR}{\beta^{2}P+R}$

所謂的 F1 定義為$\beta = 1, \alpha = 1/2$,最後得到$F = 2PR / (P+R)$

關於輸入輸出資料

  • gold_standard.xml : 黃金標準的 5000 筆評論
  • test_outcome.xml :原本認為是 測試用的反饋資料,用來檢測寫的分類器好不好。 後更正為助教的分類器跑出來的結果。

通常會拿到一大筆資料,經驗上 3/4 的資料會拿來訓練,剩下 1/4 會拿來檢測。也就是資料量於 3 : 1,至於一段資料怎麼切分有很多方式,可以擷取中間一段的 1/4 … 等都可以。

看一下 xml 格式

gold_standard.xml
1
2
3
4
5
6
7
8
<RDF rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
<Text category="music">Forget the fact that despite the grumbling
about today's "music" ...</Text>
<Text category="health">Printed all over the box are the words
"with infrared heat". ...</Text>
<Text category="music">I just finished seeing the movie and loved
the song at the end ...</Text>
...

看起來最多兩層,如果不用插件來解析 XML,遞迴處理寫一個 parser 應該不是問題。

於是就這麼蠻幹 XML parser 下去,仔細查閱一下給定的 XML,會發現文件中有 &amp;amp;&amp;amp;quot; 的確在 XML 的元素 content 不會出現 >, < … 等字元,就跟 HTML 的 character entities 一樣都需要被替換成特殊的顯示規格。但真沒有見過上述的那兩個格式,仔細檢查發現應該是對應 and 字串和 " 引號。解析完作 replace 動作。

回過頭來看這次所需要的公式:

$$P(c) = \frac{N_{c}}{N} \\ P(w|c) = \frac{count(w,c)+1}{count(c)+|V|} \\ P(c|s) = P(c) \prod P(w_{i}|c)$$

參數說明:

$P(c)$ 表示該分類佔有群體的機率,也就是在 5000 筆評論中,分類 c 佔有百分比$N_{c}$ 表示有多少筆評論屬於 c 分類$N$ 表示評論筆數,這裡已知$N = 5000$ $P(w|c)$ 單詞 w 在分類 c 的出現機率為何$count(w,c)$ 單詞 w 在分類 c 中出現的次數$count(c)$ 屬於 c 分類中字詞總數 (評論總共有多少字)$|V|$ 分類 c 中使用的單詞集合大小。
*$P(c|s)$ 評論句子 s 在分類 c 的機率為何。

隨後找$P(c|s)$ 機率值最大作為分類依準。

最後要找到分類是否正確,對於每一種分類 c 會得到表格

實際結果\分類結果 Classifier no Classifier yes
Truth no true negative(TN) false positive(FP)
Truth yes false negative(FN) true positive(TP)

準確度 R 意即:TP / (TP + FN)、精準度 P 意即:TP / (TP + FP)

對於 Micro-average 和 Macro-average 的計算,Micro 和 Macro 概念上我理解程式幾何平均和算數平均的概念,Micro 會把每個分類 c 的表單結果累加到一個表格,隨後按照一般分類算法計算準確和精準度,而 Macro 則是將每個分類算完的結果取算術平均。

代碼

傻傻地用分類器判斷與助教的決策比較的運行結果。

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
process gold_standard.xml ...
statistics model built ...
--------------------+----------
book | 1000
dvd | 1000
health | 1000
music | 1000
toys_games | 1000
--------------------+----------
process test_outcome.xml ...
testing test_outcome.xml ...
| AC\Assign| book| dvd| health| music|toys_games|
| book| 892| 29| 17| 9| 25|
| dvd| 22| 829| 16| 48| 41|
| health| 30| 19| 975| 46| 177|
| music| 5| 13| 12| 870| 28|
|toys_games| 10| 16| 43| 21| 807|
book
p :0.9301355579
r :0.9176954733
f :0.9238736406
dvd
p :0.9150110375
r :0.8671548117
f :0.8904403867
health
p :0.9172154280
r :0.7818765036
f :0.8441558442
music
p :0.8752515091
r :0.9375000000
f :0.9053069719
toys_games
p :0.7486085343
r :0.8996655518
f :0.8172151899
Micro-average
p :0.8746000000
r :0.8746000000
f :0.8746000000
Macro-average
p :0.8772444134
r :0.8807784681
f :0.8790078886

--------------------------------
Process exited after 6.545 seconds with return value 0

後來發現是公式理解錯誤

  • 真陽性 (TP, true positive)
    正確的肯定。又稱:命中 (hit)
  • 真陰性 (TN, true negative)
    正確的否定。又稱:正確拒絕 (correct rejection)
  • 偽陽性 (FP, false positive)
    錯誤的肯定,又稱:假警報 (false alarm),第一型錯誤
  • 偽陰性 (FN, false negative)
    錯誤的否定,又稱:未命中 (miss),第二型錯誤

準確度就是在正確答案中找誤判,而精準度就是在判斷正確下找錯誤。

後來實驗用 gold_standard.xml train 和 test,運行結果為

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
| AC\Assign|      book|       dvd|    health|     music|toys_games|
| book| 950| 7| 15| 3| 25|
| dvd| 7| 895| 33| 21| 44|
| health| 1| 0| 984| 1| 14|
| music| 1| 3| 15| 968| 13|
|toys_games| 0| 1| 16| 1| 982|
book
p :0.9906152242
r :0.9500000000
f :0.9698825932
dvd
p :0.9878587196
r :0.8950000000
f :0.9391395593
health
p :0.9256820320
r :0.9840000000
f :0.9539505574
music
p :0.9738430584
r :0.9680000000
f :0.9709127382
toys_games
p :0.9109461967
r :0.9820000000
f :0.9451395573
Micro-average
p :0.9558000000
r :0.9558000000
f :0.9558000000
Macro-average
p :0.9577890462
r :0.9558000000
f :0.9567934893

當然不能拿相同的 train 和 test data 來用,但是也明顯地發現,這個 model 仍然沒有辦法達到很高純度的結果,在部分比例中也只達到 90% 的精度。

那有沒有一種情況,我們將六種分類的共同交集字符給去除?這樣的效果會不會比較好呢?例如常用的 Ithinkit … 等,在 model 中直接無視這些常用字集的效果如何呢?

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
void custom() {
set<string> common;
int first_set = 1;
for (map<string, map<string, int> >::iterator it = categories.begin();
it != categories.end(); it++) {
map<string, int> &R = it->second;
set<string> s;
for (map<string, int>::iterator jt = R.begin();
jt != R.end(); jt++)
s.insert(jt->first);
if (first_set) common = s, first_set = 0;
else {
set<string> C;
set_intersection(common.begin(), common.end(), s.begin(), s.end(), inserter(C, C.begin()));
common = C;
}
}
for (map<string, map<string, int> >::iterator it = categories.begin();
it != categories.end(); it++) {
map<string, int> &R = it->second;
for (set<string>::iterator jt = common.begin();
jt != common.end(); jt++)
R.erase(*jt);
int cnt = 0;
for (map<string, int>::iterator jt = R.begin();
jt != R.end(); jt++)
cnt += jt->second;
count_category[it->first] = cnt;
}
}

上述代碼為將每一個分類的字集與共同交集,並且將共同交集從每個分類中移除,同時將記數重新統計。根據實驗結果,很多分類都直接噴掉,也許是專有名詞使用的量太少,雖然每個字集仍然有上千上萬不等,但是在分類效應上某些分類完全消失。效果差到不行,所以就直接無視吧。或者提供點意見吧。

回過頭來解一下關於作業內容,其實作業內容可以化簡為:

輸入只有一組測資,該組測資會有數行,每一行上會有兩個分類結果,第一個分類結果為標準答案,第二個分類結果為根據模型運算的結果。對於測資輸出每一個分類的準確度、精準度以及 f1 的數據結果。

兩個輸入檔案可以壓縮為

Input

1
2
3
4
5
6
7
5000
music music
book health
music music
toys_games book
music music
... here are more rows

很明顯地,第二個評論中,誤把 book 類型判斷成 health。

Output

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
| AC\Assign|      book|       dvd|    health|     music|toys_games|
| book| 907| 25| 48| 7| 13|
| dvd| 35| 873| 43| 24| 25|
| health| 10| 2| 932| 11| 45|
| music| 9| 46| 56| 865| 24|
|toys_games| 11| 10| 168| 21| 790|
book
p :0.9331275720
r :0.9070000000
f :0.9198782961
dvd
p :0.9131799163
r :0.8730000000
f :0.8926380368
health
p :0.7473937450
r :0.9320000000
f :0.8295505118
music
p :0.9321120690
r :0.8650000000
f :0.8973029046
toys_games
p :0.8807134894
r :0.7900000000
f :0.8328940432
Micro-average
p :0.8734000000
r :0.8734000000
f :0.8734000000
Macro-average
p :0.8813053583
r :0.8734000000
f :0.8773348714

--------------------------------
Process exited after 1.736 seconds with return value 0

答案算出來當然跟助教一下啊,知道什麼是 sample output 嗎?在 ACMer 的眼中,代表根據算法不同,答案也許會有誤差,或者是測資不同造成答案不同。而 sample output 通常告訴我們的是輸出格式與可能情況,而非測資的正確答案。

我就是很笨,無法理解這個世界。不知道那檔案是有序對應,看到 attribute 名稱 name 一樣,內容 content 不一樣就自動補完無法理解的英文部分,而沒有去看 tag 中 inner content 內容是相同的。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
#include <stdio.h>
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <assert.h>
#include <sstream>
#include <math.h>
#include <ctype.h>
#include <string>
#include <string.h>
#include <set>
#include <algorithm>
using namespace std;
class XMLParser {
public:
struct Node {
string tag_name, content;
map<string, string> attr;
vector<Node> child;
};
Node root;
XMLParser(string text = "") {
sin << text;
root = Node();
build(root, "");
}
void replaceAll(std::string& str, const std::string& from, const std::string& to) {
if(from.empty())
return;
size_t start_pos = 0;
while((start_pos = str.find(from, start_pos)) != std::string::npos) {
str.replace(start_pos, from.length(), to);
start_pos += to.length(); // In case 'to' contains 'from', like replacing 'x' with 'yx'
}
}
string html2text(string s) {
string ret(s);
replaceAll(ret, "&amp;amp;quot;", "\"");
replaceAll(ret, "&amp;amp;", "and");
return ret;
}
private:
stringstream sin;
void getTagContent(Node &u) {
char c, div;
while (sin.get(c)) {
if (c == '<') {
while (sin.get(c) && isspace(c));
u.tag_name = c;
while (sin.get(c) && c != '>' && !isspace(c))
u.tag_name += c;
if (c == '>') return;
while (true) {
while (sin.get(c) && isspace(c));
if (c == '>') return;
string a = "", b = "";
a += c;
while (sin.get(c) && !isspace(c) && c != '=')
a += c;
while (sin.get(c) && (isspace(c) || c == '"' || c == '\'')) div = c;
b += c;
while (sin.get(c) && !isspace(c) && c != div)
b += c;
u.attr[a] = b;
}
return;
}
}
}
int build(Node &u, string last) {
getTagContent(u);
if (u.tag_name == last)
return 0;
while (sin.peek() != EOF && sin.peek() != '<') {
char c;
sin.get(c);
u.content += c;
}
u.content = html2text(u.content);
while (sin.peek() != EOF) {
while (sin.peek() != EOF && isspace(sin.peek()))
sin.get();
if (sin.peek() == '<') {
u.child.push_back(Node());
if (!build(u.child[u.child.size() - 1], "/" + u.tag_name)) {
u.child.pop_back();
break;
}
}
}
return 1;
}
};
class StatsModel {
public:
map<string, map<string, int> > categories; // count(w, c)
map<string, int > commentCount; // N_{c}
map<string, int > count_category; // count(c)
map<string, map<string, int> > judgeTable;
int N, V;
int microtable[2][2]; // [truth 0:1][classifier 0:1]
StatsModel() {
N = V = 0;
memset(microtable, 0, sizeof(microtable));
}
vector<string> normalSentence(string content) {
vector<string> w;
stringstream sin(content);
string token;
while (sin >> token) {
token = igntrim(token);
token = str2lower(token);
if (token.length() > 0)
w.push_back(token);
}
return w;
}
void recordJudge(string truth, string classifier) {
judgeTable[truth][classifier]++;
for (map<string, int>::iterator it = commentCount.begin();
it != commentCount.end(); it++) {
int t = (it->first == truth);
int c = (it->first == classifier);
microtable[t][c]++;
}
}
string judgeComment(string category, string content) {
vector<string> w = normalSentence(content);
double Pc, P;
double maxPwc = - 1e+30;
string chooseClass = "";
for (map<string, int>::iterator it = commentCount.begin();
it != commentCount.end(); it++) {
Pc = (double)it->second / N;
P = log(Pc);
map<string, int> &R = categories[it->first];
int count_c = count_category[it->first], count_w_c;
for (int i = 0; i < w.size(); i++) {
count_w_c = 0;
if (R.find(w[i]) != R.end())
count_w_c = R[w[i]];
P += log((double) (count_w_c + 1)/ (count_c + R.size()));
}
if (P > maxPwc)
maxPwc = P, chooseClass = it->first;
}
recordJudge(category, chooseClass);
return chooseClass;
}
void addComment(string category, string content) {
commentCount[category]++, N++;
map<string, int> &S = categories[category];
vector<string> w = normalSentence(content);
for (int i = 0; i < w.size(); i++)
S[w[i]]++;
count_category[category] += w.size(), V += w.size();
}
string igntrim(string s) {
while (s.size() > 0) {
if (isspace(s[0]) || s[0] == '.' || s[0] == ','
|| s[0] == '!' || s[0] == '"' || s[0] == '\'')
s = s.substr(1);
else {
int t = s.length();
if (isspace(s[t-1]) || s[t-1] == '.' || s[t-1] == ','
|| s[t-1] == '!' || s[t-1] == '"')
s = s.substr(0, t-1);
else
return s;
}
}
return s;
}
string str2lower(string s) {
for (int i = 0; i < s.length(); i++)
s[i] = tolower(s[i]);
return s;
}
void custom() {
set<string> common;
int first_set = 1;
for (map<string, map<string, int> >::iterator it = categories.begin();
it != categories.end(); it++) {
map<string, int> &R = it->second;
set<string> s;
for (map<string, int>::iterator jt = R.begin();
jt != R.end(); jt++)
s.insert(jt->first);
if (first_set) common = s, first_set = 0;
else {
set<string> C;
set_intersection(common.begin(), common.end(), s.begin(), s.end(), inserter(C, C.begin()));
common = C;
}
}
for (map<string, map<string, int> >::iterator it = categories.begin();
it != categories.end(); it++) {
map<string, int> &R = it->second;
for (set<string>::iterator jt = common.begin();
jt != common.end(); jt++)
R.erase(*jt);
int cnt = 0;
for (map<string, int>::iterator jt = R.begin();
jt != R.end(); jt++)
cnt += jt->second;
// printf("%d -> %d\n", count_category[it->first], cnt);
count_category[it->first] = cnt;
}
// printf("%d\n", common.size());
}
void print() {
printf("%-20s+%10s\n", string(20, '-').c_str(), string(10, '-').c_str());
for (map<string, int>::iterator it = commentCount.begin();
it != commentCount.end(); it++) {
printf("%-20s|%10d\n", it->first.c_str(), it->second);
}
printf("%-20s+%10s\n", string(20, '-').c_str(), string(10, '-').c_str());
}
void report() {
// print <judge table>
printf("|%10s|", "AC\\Assign");
for (map<string, int>::iterator it = commentCount.begin();
it != commentCount.end(); it++)
printf("%10s|", it->first.c_str());
puts("");
for (map<string, int>::iterator it = commentCount.begin();
it != commentCount.end(); it++) {
printf("|%10s|", it->first.c_str());
for (map<string, int>::iterator jt = commentCount.begin();
jt != commentCount.end(); jt++) {
printf("%10d|", judgeTable[it->first][jt->first]);
}
puts("");
}
// homework format
// recall: fraction of docs in class i classified correctly
// precision: fraction of docs assigned class i that are actually about class i
const double beta = 1;
double micro_r = 0, micro_p = 0, macro_r = 0, macro_p = 0, f1;
for (map<string, int>::iterator it = commentCount.begin();
it != commentCount.end(); it++) {
double recall = 0, precision = 0, f1 = 0;
int sumr = 0, sump = 0;
for (map<string, int>::iterator jt = commentCount.begin();
jt != commentCount.end(); jt++) {
sumr += judgeTable[it->first][jt->first];
sump += judgeTable[jt->first][it->first];
}
recall = (double) judgeTable[it->first][it->first] / sumr;
precision = (double) judgeTable[it->first][it->first] / sump;
f1 = (beta * beta + 1) * precision * recall / (beta * beta * precision + recall);

macro_r += recall, macro_p += precision;

printf("%s\n", it->first.c_str());
printf("%9s :%.10lf\n", "p", precision);
printf("%9s :%.10lf\n", "r", recall);
printf("%9s :%.10lf\n", "f", f1);
}
// for (int i = 0; i < 2; i++, puts(""))
// for (int j = 0; j < 2; j++)
// printf("%5d ", microtable[i][j]);
// [truth 0:1][classifier 0:1] = { {TN, FP}, {FN, TP} }
micro_r = (double) microtable[1][1] / (microtable[1][1] + microtable[1][0]); // TP / (TP + FN)
micro_p = (double) microtable[1][1] / (microtable[1][1] + microtable[1][0]); // TP / (TP + FP)
f1 = (beta * beta + 1) * micro_p * micro_r / (beta * beta * micro_p + micro_r);
printf("%s\n", "Micro-average");
printf("%9s :%.10lf\n", "p", micro_p);
printf("%9s :%.10lf\n", "r", micro_r);
printf("%9s :%.10lf\n", "f", f1);

macro_r /= commentCount.size();
macro_p /= commentCount.size();
f1 = (beta * beta + 1) * macro_p * macro_r / (beta * beta * macro_p + macro_r);
printf("%s\n", "Macro-average");
printf("%9s :%.10lf\n", "p", macro_p);
printf("%9s :%.10lf\n", "r", macro_r);
printf("%9s :%.10lf\n", "f", f1);
}
};
int main() {
ifstream fin("gold_standard.xml");
string xml = "", line;
while (getline(fin, line))
xml += "\n" + line;
printf("process gold_standard.xml ...\n");

XMLParser xmlDoc(xml);
StatsModel statsModel;

printf("statistics model built ...\n");
for (int i = 0; i < xmlDoc.root.child.size(); i++) {
string a = xmlDoc.root.child[i].attr["category"],
b = xmlDoc.root.child[i].content;
statsModel.addComment(a, b);
}

statsModel.print();
// statsModel.custom();

ifstream tin("test_outcome.xml");

xml = "";
while (getline(tin, line))
xml += "\n" + line;
printf("process test_outcome.xml ...\n");

XMLParser testDoc(xml);

printf("testing test_outcome.xml ...\n");
for (int i = 0; i < testDoc.root.child.size(); i++) {
statsModel.recordJudge(xmlDoc.root.child[i].attr["category"], testDoc.root.child[i].attr["category"]);
}

statsModel.report();

return 0;
}
Read More +

自然語言處理 - HW01

編譯環境

Dev-C++ 5.6.3

Language model implementation

實作語言處理模型,要求讀入一連串的英文語句做為基底,接著詢問一句的正確性為多少,也就是這句話是正確拼讀的機率為何,算是一個可用的句子嗎?

$$P(w_{i}) = \frac{Count(w_{i})}{\sum_{j} Count(w_{j})} \\ P(w_{i}, w_{i+1}) = \frac{Count(w_{i}, w_{i+1})}{\sum_{j} Count(w_{j}, w_{j+1})} \\ P(w_{i+1}|w_{i}) = \frac{P(w_{i}, w_{i+1})}{P(w_{i})}$$

上述分別是一個單詞的機率,以及計算相鄰兩個單詞的機率,最後推估在這個單詞下,它們相鄰的機率。請查閱 貝氏定理

  • P(A)是A的先驗機率或邊緣機率。之所以稱為”先驗”是因為它不考慮任何B方面的因素。
  • P(A|B)是已知B發生後A的條件機率,也由於得自B的取值而被稱作A的後驗機率。
  • P(B|A)是已知A發生後B的條件機率,也由於得自A的取值而被稱作B的後驗機率。
  • P(B)是B的先驗機率或邊緣機率,也作標准化常量(normalizing constant).
$P(s) = P(w_{0}) \times P(w_{1}|w_{0}) \times ... \times P(w_{n-1}|w_{n-2})$

上述為一個句子的機率,一個句子可以表示成一個序列單詞,利用連乘積將機率算出。當句子越常時,很容易發現機率陡降的速度相當快,就算是數個字詞,機率大約也是在$10^{-3}$ 左右。因此這麼算下去,長句子的正確性就會大幅減少,但是在邏輯上,如果句子都是短短幾個單詞也是相當奇怪的,口語上也許是,文章判讀上就難說。至於要不要取$\sqrt[n]{x}$ 值得思考。

$$\begin{cases} Count^{*}(w_{i}) = (Count(w_{i})+1) \times \frac{N_{Count(w_{i})+1}}{N_{Count(w_{i})}} & \text{ if } Count(w_{i}) < k \\ Count^{*}(w_{i}) = Count(w_{i}) & \text{ if } Count(w_{i}) \geq k \end{cases} \\ \text{unigram } N_{0} = 80000$$

當我們去計算一個單詞的機率時,必須相對於其他單詞的出現機率,然而像介係詞、助詞等,出現次數是相對高出取多,必須取一個閥值,來忽略過高無用的機率,以免將其他的單詞的機率過低不均。

$$\begin{cases} Count^{*}(w_{i}, w_{i+1}) = (Count(w_{i}, w_{i+1})+1) \times \frac{N_{Count(w_{i}, w_{i+1})+1}}{N_{Count(w_{i}, w_{i+1})}} & \text{ if } Count(w_{i}, w_{i+1}) < k \\ Count^{*}(w_{i}, w_{i+1}) = Count(w_{i}, w_{i+1}) & \text{ if } Count(w_{i}, w_{i+1}) \geq k \end{cases} \\ \text{bigram } N_{0} = 80000 \times 80000$$

在計算相鄰兩個單詞的出現次數時,一樣會遇到這種情況。既然在計算次數上需要做 smoothing 的調整,在機率處理上也是一樣動作。

$$\begin{cases} P(w_{i}) = \frac{N_{1}}{N} & \text{ if } Count(w_{i}) = 0 \\ P(w_{i}) = \frac{Count^{*}(w_{i})}{N} & \text{ if } Count(w_{i}) < K \\ P(w_{i}) = \frac{Count(w_{i})}{N} & \text{ if } Count(w_{i}) \geq K \end{cases}$$ $$\begin{cases} P(w_{i}, w_{i+1}) = \frac{Count^{*}(w_{i}, w_{i+1})}{N} & \text{ if } Count(w_{i}, w_{i+1}) < K \\ P(w_{i}, w_{i+1}) = \frac{Count(w_{i}, w_{i+1})}{N} & \text{ if } Count(w_{i}, w_{i+1}) \geq K \end{cases}$$

在單詞出現次數很少時,就必須使用 smoothing,因為出現 1 次、2 次、3 次 … 的單詞次數,之間大小關係不保證嚴格遞增或遞減,

實作細節

  • 公式都已經給定,基本上麻煩就是在於資料紀錄而已,其他就照著流程跑。
  • 雖然沒有規定語言,以下代碼在 Dev-C++ 下編過,別問 VS 到底行不行。

原則上,讀檔案,建立模型可以在 1.4 秒內完成

1
2
3
4
5
6
processing dataset.txt ...
read file end. Start prepare language model ...
input a sentence in a line :

--------------------------------
Process exited after 1.493 seconds with return value 0

測試輸入

1
2
3
4
5
6
7
8
causes AIDS and is associated with AIDS cases primarily in West Africa
AIDS cases primarily in West Africa
AIDS cases primarily at West Africa
AIDS cases primarily AIDS West Africa
morris
West Africa
East Africa
Taiwan Africa

測式輸出

考量長句子的機率,採用 log 平均結果,輸出應該為負值。

1
2
3
4
5
6
7
8
-4.597715
-4.796396
-5.992288
-7.245960
-1.857392
-4.639120
-8.003706
-8.003706

原始版本,直接輸出 P(s),這裡採用科學記號表示法。

1
2
3
4
5
6
7
8
1.101764e-026
2.622182e-015
6.068425e-019
9.372080e-023
2.436068e-002
9.031667e-007
3.733396e-011
3.733396e-011

結語

有 STL library,代碼不用太長,跑得時間也不會太久。想到插手別學校的自然語言處理,玩了一下他們作業,把同學的代碼效率修得好一點,其實也不錯玩得,只是在公式計算上比較沒有,但是要求高效率的搜索結構,讀檔案進來後,依據什麼建表、該用什麼順序完成是很重要的。

切記,在寫這種程式時,發現跑的速度太久,一部分是因為使用太多的標準輸出,也就是用太多 printf()cout <<System.out.println() 之類的在進行流程監控。輸出的效率必須將檔案寫到螢幕顯示的 memory buffer,因此 context-switch 什麼,消耗時間太大,盡可能不要輸出,要不然就是按比例輸出,速度可以快個數百倍。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <stdio.h>
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <assert.h>
#include <sstream>
#include <math.h>
#include <ctype.h>
using namespace std;
#define DEBUG
class Model {
public:
map<string, int> Count;
map<pair<string, string>, int> Count2;
map<int, int> Ni;
map<int, int> Ni2;
int totalCountWord, totalCount2Word;
static const int K;
static const int V;
string str2lower(string s) {
for (int i = 0; i < s.length(); i++)
s[i] = tolower(s[i]);
return s;
}
void prepare() {
totalCountWord = totalCount2Word = 0;
for (map<string, int>::iterator it = Count.begin();
it != Count.end(); it++) {
Ni[it->second]++;
totalCountWord += it->second;
//#ifdef DEBUG
// if (it->second > 1000)
// printf("Count(%s) = %d\n", it->first.c_str(), it->second);
//#endif
}
for (map<pair<string, string>, int>::iterator it = Count2.begin();
it != Count2.end(); it++) {
Ni2[it->second]++;
totalCount2Word += it->second;
}
int smooth = 0x3f3f3f3f;
for (map<int, int>::iterator it = Ni.begin();
it != Ni.end(); it++) {
// smooth = min(smooth, it->second);
// it->second = smooth;
//#ifdef DEBUG
// printf("N(%d) = %d\n", it->first, it->second);
// getchar();
//#endif
}
}
double getN(int i) { // N_{Count(w)}
if (i == 0) return 80000;
map<int, int>::iterator it = Ni.lower_bound(i), jt;
if (it == Ni.begin()) return it == Ni.end() ? 1 : it->second;
jt = it, jt--;
double sx = jt->first, sy = jt->second, ex = it->first, ey = it->second;
return sy + (ey - sy) / (ex - sx) * (i - sx);
}
double getN2(int i) { // N_{Count(w_{i}, w_{i+1})}
if (i == 0) return 80000.0 * 80000.0;
map<int, int>::iterator it = Ni2.lower_bound(i), jt;
if (it == Ni2.begin()) return it == Ni2.end() ? 1 : it->second;
jt = it, jt--;
double sx = jt->first, sy = jt->second, ex = it->first, ey = it->second;
return sy + (ey - sy) / (ex - sx) * (i - sx);
}
double getCountStar(const string &w) { // Count^{*}(w_{i})
int n = Count[w];
if (n < K) {
return (double) (n + 1) * (getN(n + 1) / getN(n));
} else {
return n;
}
}
double getCountStar2(const string &w1, const string &w2) { // Count^{*}(w_{i}, w_{i+1})
int n = Count2[make_pair(w1, w2)];
if (n < K) {
return (double) (n + 1) * (getN2(n + 1) / getN2(n));
} else {
return n;
}
}
double getPofW1(const string &w) { // P(w_{i}) = \frac{Count(w_{i})}{\sum_{j} Count(w_{j})}
map<string, int>::iterator it = Count.find(w);
if (it == Count.end() || it->second == 0) { // Count(w_{i}) = 0
double Nu0 = V - Count.size();
return (double) getN(1) / Nu0 / totalCountWord; // \frac{N_{1}}{N}
} else if (it->second < K) { // 0 < Count(w_{i}) < K
return (double) getCountStar(w) / totalCountWord; // \frac{Count^{*}(w_{i})}{N}
} else { // Count(w_{i}) \geq K
return (double) it->second / totalCountWord; // \frac{Count(w_{i})}{N}
}
}
double getPofW2(const string &w1, const string &w2) { // P(w_{i}, w_{i+1})
map< pair<string, string>, int>::iterator it = Count2.find(make_pair(w1, w2));
if (it == Count2.end() || it->second == 0) {
double Nb0 = (double) V * V - Count2.size();
return (double) getN2(1) / Nb0 / totalCount2Word;
} else if (it->second < K) { // Count(w_{i}, w_{i+1}) < K
return (double) getCountStar2(w1, w2) / totalCount2Word; // \frac{Count^{*}(w_{i}, w_{i+1})}{N}
} else { // Count(w_{i}, w_{i+1}) \geq K
return (double) it->second / totalCount2Word; // \frac{Count(w_{i}, w_{i+1})}{N}
}
}
void parseStmt(vector<string> &stmt) {
for (int i = 0; i < stmt.size(); i++) {
stmt[i] = str2lower(stmt[i]);
Count[stmt[i]]++;
if (i)
Count2[make_pair(stmt[i-1], stmt[i])]++;
}
}
double getPs(string in) {
stringstream sin(in);
vector<string> stmt;
string token;
while (sin >> token)
stmt.push_back(str2lower(token));
// P(s) = P(w_{0}) \times P(w_{1}|w_{0}) \times ... \times P(w_{n-1}|w_{n-2})
double p = 1;
if (stmt.size() > 0)
p = getPofW1(stmt[0]);
for (int i = 1; i < stmt.size(); i++ ) {
p *= getPofW2(stmt[i-1], stmt[i]) / getPofW1(stmt[i-1]);
// printf("%lf\n", getPofW2(stmt[i-1], stmt[i]) / getPofW1(stmt[i-1]));
// cout << stmt[i-1] << " " << stmt[i] << endl;
// printf("%lf\n", getPofW2(stmt[i-1], stmt[i]));
}
return p;
}
} tool;
const int Model::K = 10, Model::V = 80000;
int main() {
ifstream fin("dataset.txt");
// freopen("tmp.txt", "w+t", stdout);
string token, line;
vector<string> stmt;
puts("processing dataset.txt ...");
while (getline(fin, line)) {
stringstream sin(line);
stmt.clear();
while (sin >> token) {
stmt.push_back(token);
}
tool.parseStmt(stmt);
}
puts("read file end. Start prepare language model ...");
tool.prepare();
puts("input a sentence in a line :");
while (getline(cin, line)) {
printf("P*('%s') : %.10e\n", line.c_str(), tool.getPs(line));
}
return 0;
}
/*
causes AIDS and is associated with AIDS cases primarily in West Africa
AIDS cases primarily in West Africa
AIDS cases primarily at West Africa
AIDS cases primarily AIDS West Africa
morris
IL-2 is a gene .
IL-2 is an gene .
*/


Read More +