allenlu2007

A great WordPress.com site

NLP 中文分詞 – HanLP

Reference:

[1] Hankcs/pyhanlp, github, “Python interfaces for HanLP

[2] Hankcs/HanLP, github, “HanLP: Han Language Processing 

竹間智能 in 知乎, “有哪些比较好的中文分词方案?


前言

HanLP 不只是中文分詞。HanLP是一系列模型與算法組成的NLP工具包,由大快搜索主導並完全開源,目標是普及自然語言處理在生產環境中的應用。

HanLP提供下列功能:

 

原始的 HanLP 是 Jave implementation and Java API, pyhanlp 提供了 python API 更容易安裝和使用。

 

Install pyhanlp and HanLP

$ pip install pyhanlp

 

HanLP python API 相當容易使用。

中文分詞:HanLP.segment(‘text’)

關鍵詞提取:HanLP.extractKeyword(document)

自動摘要:HanLP.extractSummy(document)

 

# -*- coding:utf-8 -*-
from pyhanlp import*
print(HanLP.segment('你好,歡迎在Python中調用HanLP的API'))
for term in HanLP.segment('下雨天地面積水'):
    print('{}\t{}'.format(term.word, term.nature)) # 獲取單詞與詞性
testCases = [
    "商品和服務",
    "結婚的和尚未結婚的確實在干擾分詞啊",
    "買水果然後來世博園最後去世博會",
    "中國的首都是北京",
    "歡迎新老師生前來就餐",
    "工信處女幹事每月經過下屬科室都要親口交代24口交換機等技術性器件的安裝工作",
    "隨著頁遊興起到現在的頁游繁盛,依賴於存檔進行邏輯判斷的設計減少了,但這塊也不能完全忽略掉。"]
for sentence in testCases: print(HanLP.segment(sentence))
# 關鍵詞提取
document = "水利部水資源司司長陳明忠9月29日在國務院新聞辦舉行的新聞發佈會上透露," \
           "根據剛剛完成了水資源管理制度的考核,有部分省接近了紅線的指標," \
           "有部分省超過紅線的指標。對一些超過紅線的地方,陳明忠表示,對一些取用水項目進行區域的限批," \
           "嚴格地進行水資源論證和取水許可的批准。"
print(HanLP.extractKeyword(document, 2))
# 自動摘要
print(HanLP.extractSummary(document, 3))
# 依存句法分析
print(HanLP.parseDependency("徐先生還具體幫助他確定了把畫雄鷹、松鼠和麻雀作為主攻目標。"))

 

Advertisements

NLP 中文分詞 – 結巴

Reference:

[1] Fukuball, “如何使用 JIEBA 結巴中文分詞程式

[2] 竹間智能 in 知乎, “有哪些比较好的中文分词方案?


前言

中文自然語言處理的其中一個重要環節就是斷詞的處理。英文字詞基本相同,斷詞非常容易,直接用 space 就可以斷字或斷詞。中文斷詞在先天上就比較難處理,比如電腦要怎麼知道「全台大停電」要斷詞成「全台 / 大 / 停電」或是 「全/台大 / 停電」呢?如果是英文「Power outage all over Taiwan」,就可以直接用空白斷成「Power / outage / all / over / Taiwan」,可見中文斷詞是一個大問題。因為斷詞有歧義的可能如上,所以後面用分詞來替代斷詞。英文也會有姓名,專有名詞,複合名詞需要分詞,不過比起中文分詞還是相對容易。

 

分詞算法

是否有基於深度學習的中文分詞?Yes [2].

中文分詞根據實現原理和特點,主要分為以下2個類別:

1、基於詞典分詞算法

也稱字符串匹配分詞算法。該算法是按照一定的策略將待匹配的字符串和一個已建立好的“充分大的”詞典中的詞進行匹配,若找到某個詞條,則說明匹配成功,識別了該詞。常見的基於詞典的分詞算法分為以下幾種:正向最大匹配法、逆向最大匹配法雙向匹配分詞法等。

基於詞典的分詞算法是應用最廣泛、分詞速度最快的。很長一段時間內研究者都在對基於字符串匹配方法進行優化,比如最大長度設定、字符串存儲和查找方式以及對於詞表的組織結構,比如採用TRIE索引樹、Hash 索引等。

2、基於統計的機器學習算法

這類目前常用的是算法是HMM、CRF (Conditional Random Field)、SVM、深度學習等算法,比如 Stanford、Hanlp 分詞工具是基於 CRF 算法。以 CRF 為例,基本思路是對漢字進行標註訓練,不僅考慮了詞語出現的頻率,還考慮上下文,具備較好的學習能力,因此其對歧義詞和未登錄詞的識別都具有良好的效果。

JIEBA 中文分詞所使用的演算法是基於 TRIE TREE 結構去生成句子中中文字所有可能成詞的情況,然後使用動態規劃(DYNAMIC PROGRAMMING)算法來找出最大機率的路徑,這個路徑就是基於詞頻的最大分詞結果。對於辨識新詞(字典詞庫中不存在的詞)則使用了 HMM 模型及 VITERBI 算法來辨識出來。基本上這樣就可以完成具有分詞功能的程式了。

熟悉通訊理論的 Trellis Code Modulation (TCM), 或是語音識別理論者,對此應該不陌生。Jieba 基本是 statistics based machine learning 中文分詞。

Nianwen Xue在其論文《Combining Classifiers for Chinese Word Segmentation》中首次提出對每個字符進行標註,通過機器學習算法訓練分類器進行分詞,在論文《Chinese word segmentation as character tagging》中較為詳細地闡述了基於字標註的分詞法。

常見的分詞器都是使用機器學習算法和詞典相結合,一方面能夠提高分詞準確率,另一方面能夠改善領域適應性。

隨著深度學習的興起,也出現了基於神經網絡的分詞器,例如有人員嘗試使用雙向LSTM+CRF實現分詞器,其本質上是序列標註,所以有通用性,命名實體識別等都可以使用該模型,據報導其分詞器字符準確率可高達97.5%。算法框架的思路與論文《Neural Architectures for Named Entity Recognition》類似,利用該框架可以實現中文分詞,如下圖所示:

首先對語料進行字符嵌入,將得到的特徵輸入給雙向LSTM,然後加一個CRF就得到標註結果。

分詞器當前存在問題:

目前中文分詞難點主要有三個:

1、分詞標準:比如人名,在哈工大的標準中姓和名是分開的,但在Hanlp中是合在一起的。這需要根據不同的需求制定不同的分詞標準。

2、歧義:對同一個待切分字符串存在多個分詞結果。

歧義又分為組合型歧義、交集型歧義和真歧義三種類型。

1) 組合型歧義:分詞是有不同的粒度的,指某個詞條中的一部分也可以切分為一個獨立的詞條。比如“中華人民共和國”,粗粒度的分詞就是“中華人民共和國”,細粒度的分詞可能是“中華/人民/共和國”

2) 交集型歧義:在“鄭州天和服裝廠”中,“天和”是廠名,是一個專有詞,“和服”也是一個詞,它們共用了“和”字。

3) 真歧義:本身的語法和語義都沒有問題, 即便採用人工切分也會產生同樣的歧義,只有通過上下文的語義環境才能給出正確的切分結果。例如:對於句子“美國會通過對台售武法案”,既可以切分成“美國/會/通過對台售武法案”,又可以切分成“美/國會/通過對台售武法案”。

一般在搜索引擎中,構建索引時和查詢時會使用不同的分詞算法。常用的方案是,在索引的時候使用細粒度的分詞以保證召回,在查詢的時候使用粗粒度的分詞以保證精度。

3、新詞:也稱未被詞典收錄的詞,該問題的解決依賴於人們對分詞技術和漢語語言結構的進一步認識。

 

 

部分分詞工具供參考:

中研院有提供「中文斷詞系統」,但是非開源。

中科院計算所NLPIR ictclas.nlpir.org/nlpir

ansj 分詞器 github.com/NLPchina/ans

哈工大的LTP github.com/HIT-SCIR/ltp

清華大學THULAC github.com/thunlp/THULA

Stanford 分詞器 nlp.stanford.edu/softwa

Hanlp分詞器 github.com/hankcs/HanLP

Jieba 結巴分詞 github.com/yanyiwu/cppj

KCWS分詞器(字嵌入+Bi-LSTM+CRF) github.com/koth/kcws

ZPar github.com/frcchang/zpa

IKAnalyzer github.com/wks/ik-analy

以及部分分詞器的簡單說明:

哈工大的分詞器:主頁上給過調用接口,每秒請求的次數有限制。

清華大學THULAC:目前已經有Java、Python和C++版本,並且代碼開源。

Stanford 分詞器:作為眾多斯坦福自然語言處理中的一個包,目前版本3.7.0, Java實現的CRF算法。可以直接使用訓練好的模型,也提供訓練模型接口。

Hanlp分詞:求解的是最短路徑。優點:開源、有人維護、可以解答。原始模型用的訓練語料是人民日報的語料,當然如果你有足夠的語料也可以自己訓練。

Jieba 結巴分詞工具:基於前綴詞典實現高效的詞圖掃瞄,生成句子中漢字所有可能成詞情況所構成的有向無環圖 (DAG);採用了動態規劃查找最大概率路徑, 找出基於詞頻的最大切分組合;對於未登錄詞,採用了基於漢字成詞能力的 HMM 模型,使用了 Viterbi 算法。

Word Embedding+Bi-LSTM+CRF分詞器:本質上是序列標註,這個分詞器用人民日報的80萬語料,據說按照字符正確率評估標準能達到97.5%的準確率。

ZPar分詞器:新加坡科技設計大學開發的中文分詞器,包括分詞、詞性標註和Parser,支持多語言,據說效果是公開的分詞器中最好的,C++語言編寫。

 

公開的分詞數據集

測試數據集

1、SIGHAN Bakeoff 2005 MSR,560KB

sighan.cs.uchicago.edu/

2、SIGHAN Bakeoff 2005 PKU, 510KB

sighan.cs.uchicago.edu/

3、人民日報 2014, 65MB

pan.baidu.com/s/1hq3KKX

 

結巴 

近來 jieba 結巴這個 Python Based 的開源中文分詞程式非常流行。本文以 jieba 為主。

中文歌詞斷詞,使用預設詞庫

現在我們使用 回聲樂團 – 座右銘 的歌詞作為中文斷詞測試範例,歌詞我們先做成一個純文字檔,內容如下:

 

我沒有心 

我沒有真實的自我 

我只有消瘦的臉孔 

所謂軟弱 

所謂的順從一向是我的座右銘 

而我

沒有那海洋的寬闊

我只要熱情的撫摸

所謂空洞

所謂不安全感是我的墓誌銘

而你

是否和我一般怯懦

是否和我一般矯作

和我一般囉唆

而你

是否和我一般退縮

否和我一般肌迫

一般地困惑

我沒有力

我沒有滿腔的熱火

我只有滿肚的如果

所謂勇氣

所謂的認同感是我

隨便說說

而你

是否和我一般怯懦

是否和我一般矯作

是否對你來說

只是一場遊戲

雖然沒有把握

而你

是否和我一般退縮

是否和我一般肌迫

是否對你來說

只是逼不得已

雖然沒有藉口

 NewImage

Jieba 得到的分詞結果會是:

我 / 沒 / 有心 / 我 / 沒 / 有 / 真實 / 的 / 自我 / 我 / 只有 / 消瘦 / 的 / 臉孔 / 所謂 / 軟弱 / 所謂 / 的 / 順 / 從 / 一向 / 是 / 我 / 的 / 座 / 右銘 / 而 / 我 / 沒有 / 那 / 海洋 / 的 / 寬闊 / 我 / 只要 / 熱情 / 的 / 撫 / 摸 / 所謂 / 空洞 / / 所謂 / 不安全感 / 是 / 我 / 的 / 墓誌 / 銘 / 而 / 你 / 是否 / 和 / 我 / 一般 / 怯懦 / 是否 / 和 / 我 / 一般 / 矯作 / 和 / 我 / 一般 / 囉 / 唆 / 而 / 你 / 是否 / 和 / 我 / 一般 / 退縮 / 是否 / 和 / 我 / 一般 / 肌迫 / 一般 / 地 / 困惑 / 我 / 沒 / 有力 / 我 / 沒 / 有 / 滿腔 / 的 / 熱火 / 我 / 只有 / 滿肚 / 的 / 如果 / 所謂 / 勇氣 / 所謂 / 的 / 認 / 同感 / 是 / 我 / 隨便 / 說 / 說 / 而 / 你 / 是否 / 和 / 我 / 一般 / 怯懦 / 是否 / 和 / 我 / 一般 / 矯作 / 是否 / 對 / 你 / 來 / 說 / 只是 / 一場 / 遊戲 / 雖然 / 沒 / 有把握 / 而 / 你 / 是否 / 和 / 我 / 一般 / 退縮 / 是否 / 和 / 我 / 一般 / 肌迫 / 是否 / 對 / 你 / 來 / 說 / 只是 / 逼不得已 / 雖然 / 沒有 / 藉口

我們可以從結果看出分詞已經開始出了一些問題,比如「座右銘」被斷成了「座 / 右銘」「墓誌銘」被斷成了「墓誌 / 銘」,這應該就是因為預設詞庫是簡體中文所造成,因此繁體中文的分詞結果會比較差,還好 jieba 也提供了可以切換詞庫的功能,並提供了一個繁體中文詞庫,所以我們可以使用切換詞庫的功能來改善分詞結果。


使用繁體詞庫


jieba_cut_lyric_zh.py

 NewImage


我們在程式中多加一行 jieba.set_dictionary('dict.txt.big'),這樣就可以將分詞詞庫切換到 dic.txt.big 這個檔案。

得到的分詞結果會是:

我 / 沒有 / 心 / 我 / 沒有 / 真實 / 的 / 自我 / 我 / 只有 / 消瘦 / 的 / 臉孔 / 所謂 / 軟弱 / 所謂 / 的 / 順從 / 一向 / 是 / 我 / 的 / 座右銘 / 而 / 我 / 沒有 / 那 / 海洋 / 的 / 寬闊 / 我 / 只要 / 熱情 / 的 / 撫摸 / 所謂 / 空洞 / 所謂 / 不安全感 / 是 / 我 / 的 / 墓誌銘 / 而 / 你 / 是否 / 和 / 我 / 一般 / 怯懦 / 是否 / 和 / 我 / 一般 / 矯作 / 和 / 我 / 一般 / 囉唆 / 而 / 你 / 是否 / 和 / 我 / 一般 / 退縮 / 是否 / 和 / 我 / 一般 / 肌迫 / 一般 / 地 / 困惑 / 我 / 沒有 / 力 / 我 / 沒有 / 滿腔 / 的 / 熱火 / 我 / 只有 / 滿肚 / 的 / 如果 / 所謂 / 勇氣 / 所謂 / 的 / 認同感 / 是 / 我 / 隨便說說 / 而 / 你 / 是否 / 和 / 我 / 一般 / 怯懦 / 是否 / 和 / 我 / 一般 / 矯作 / 是否 / 對 / 你 / 來說 / 只是 / 一場 / 遊戲 / 雖然 / 沒有 / 把握 / 而 / 你 / 是否 / 和 / 我 / 一般 / 退縮 / 是否 / 和 / 我 / 一般 / 肌迫 / 是否 / 對 / 你 / 來說 / 只是 / 逼不得已 / 雖然 / 沒有 / 藉口 

我們可以看到「座右銘」成功斷成「座右銘」了!「墓誌銘」也成功斷成「墓誌銘」了!果然切換成繁體中文詞庫還是有用的!

 

大陸中科院的結果如下。除了分詞之外。還有詞性類別 (名詞,動詞,助詞,etc.)如下顏色。

NewImage

 

詞的分類

  • 實詞:名詞、動詞、形容詞、狀態詞、區別詞、數詞、量詞、代詞
  • 虛詞:副詞、介詞、連詞、助詞、擬聲詞、嘆詞。

 


CBOW and Skip-gram

Reference:

[1] T. Ganegedara, “Word2Vec (Part 1): NLP With Deep Learning with Tensorflow (Skip-gram)”, (Chinese)

[2] T. Ganegedara, “Word2Vec (Part 2): NLP With Deep Learning with Tensorflow (CBOW)”, (Chinese)

 

CBOW是什麼?

CBOW是什麼呢?它的全稱是 continuous bag-of-words ,中文是連續詞袋模型。它的框架可以說就是將skip-gram模型倒轉過來。在skip-gram模型中,是根據目標詞預測上下文。而CBOW模型,則是根據上下文預測目標詞。

 

為什麼要使用CBOW模型?

既然我們已經有了skip-gram模型,為什麼我們還要學習CBOW模型呢?原因就是CBOW模型的表現更加優秀。一部分的原因在於CBOW模型的 inputs 更加豐富。換句化說,假定如下句子:the dog barked at the mailman , 在skip-gram模型中,輸入輸出為 (input:'dog',output:'barked') ,而在CBOW模型中,將有以下輸入輸出:(input:['the','barked','at'],output:'dog') 。可以看出在CBOW中,只有當 [the, barked, at] 等詞準確地出現了,才會預測dog 出現,而不像skip-gram那樣,只能預測出dog 將出現在 barked 附近。

 

CBOW模型

CBOW的概念模型看起來就像倒過來的skip-gram模型一樣。儘管看起來如此,但是CBOW模型和skip-gram模型並不是對稱的。下面是模型的框架圖。


 

注意到,因為實現框架圖跟skip-gram的十分相似,所以沒有給出來。如何把這個概念模型如轉化成實現模型呢,我們要做的就是生成 (input, output) 的 batch。換句化說,對每一列每次處理處理 b 個(b – batch大小)詞(比如b x word[t-2],b x word[t-1]b x word[t+1],b x word[t+2])。

CBOW 背後的思想是,我們使用所有 input 詞的平均詞向量作為學習模型的輸入。

 

數據生成

現在,生成數據的函數需要做一些小小的修改來適應CBOW模型。下面是修改後的代碼:

  1. def generate_batch(batch_size, skip_window):  
  2.     # skip window is the amount of words we’re looking at from each side of a given word  
  3.     # creates a single batch  
  4.     global data_index  
  5.     assert skip_window%2==1  
  6.    
  7.     span = 2 * skip_window + 1 # [ skip_window target skip_window ]  
  8.    
  9.     batch = np.ndarray(shape=(batch_size,span-1), dtype=np.int32)  
  10.     labels = np.ndarray(shape=(batch_size, 1), dtype=np.int32)  
  11.     # e.g if skip_window = 2 then span = 5  
  12.     # span is the length of the whole frame we are considering for a single word (left + word + right)  
  13.     # skip_window is the length of one side  
  14.    
  15.     # queue which add and pop at the end  
  16.     buffer = collections.deque(maxlen=span)  
  17.    
  18.     #get words starting from index 0 to span  
  19.     for _ in range(span):  
  20.         buffer.append(data[data_index])  
  21.         data_index = (data_index + 1) % len(data)  
  22.    
  23.     # num_skips => # of times we select a random word within the span?  
  24.     # batch_size (8) and num_skips (2) (4 times)  
  25.     # batch_size (8) and num_skips (1) (8 times)  
  26.     for i in range(batch_size):  
  27.         target = skip_window  # target label at the center of the buffer  
  28.         target_to_avoid = [ skip_window ] # we only need to know the words around a given word, not the word itself  
  29.    
  30.         # do this num_skips (2 times)  
  31.         # do this (1 time)  
  32.    
  33.         # add selected target to avoid_list for next time  
  34.         col_idx = 0  
  35.         for j in range(span):  
  36.             if j==span//2:  
  37.                 continue  
  38.             # e.g. i=0, j=0 => 0; i=0,j=1 => 1; i=1,j=0 => 2  
  39.             batch[i,col_idx] = buffer[j] # [skip_window] => middle element  
  40.             col_idx += 1  
  41.         labels[i, 0] = buffer[target]  
  42.    
  43.         buffer.append(data[data_index])  
  44.         data_index = (data_index + 1) % len(data)  
  45.    
  46.     assert batch.shape[0]==batch_size and batch.shape[1]== span-1  

可以注意到,batch 的大小變為 (b x span-1),而修改前為(b x 1)。並且去除了num_skips.因為我們將使用 span 中所有的詞。直觀地說,batch 的索引(i,j)可以理解為文檔labels 中第 j 個詞的 i-skip_window 偏移量( i<skip_window 時)或 i-skip_window+1 個詞 (i>=skip_window 時)。舉個例子,假設 skip_window=1 , 輸入句子 the dog barked at the mailman,我們將會得到,

batch: [[‘the’,’barked’],[‘dog’,’at’],[‘barked’,’the’],[‘at’,’mailman’]]

labels: [‘dog’,’barked’,’at’,’the’]

或是以 text8 為例:anarchism originated as a term of abuse …

with num_skips = 2 and skip_window = 1:   

batch: [[‘anarchism’, ‘as’], [‘originated’, ‘a’], [‘as’, ‘term’], [‘a’, ‘of’], [‘term’, ‘abuse’], [‘of’, ‘first’], [‘abuse’, ‘used’], [‘first’, ‘against’]]   

labels: [‘originated’, ‘as’, ‘a’, ‘term’, ‘of’, ‘abuse’, ‘first’, ‘used’] 


訓練模型

同樣,訓練模型的階段也需要做一些調整。但是這也沒有很複雜,我們要做的就是把 data placholder 的大小做一些調整,並且為多個輸入寫

寫入正確的符號操作以得到其平均值。考慮到訓練過程比較重要,因此我將會把代碼分成幾個小片段,並且從中挑取重要的來講解。

 

變量初始化

首先我們要把 train_dataset 的 placeholder 改變為 (b x 2*skip_window)(記住,span-1 = 2*skip_window)。其它保持不變。

 

  1. if __name__ == ‘__main__’:  
  2.     batch_size = 128  
  3.     embedding_size = 128 # Dimension of the embedding vector.  
  4.     skip_window = 1 # How many words to consider left and right.  
  5.     num_skips = 2 # How many times to reuse an input to generate a label.  
  6.     valid_size = 16 # Random set of words to evaluate similarity on.  
  7.     valid_window = 100 # Only pick dev samples in the head of the distribution.  
  8.     # pick 16 samples from 100  
  9.     valid_examples = np.array(random.sample(range(valid_window), valid_size//2))  
  10.     valid_examples = np.append(valid_examples,random.sample(range(1000,1000+valid_window), valid_size//2))  
  11.     num_sampled = 64 # Number of negative examples to sample.  
  12.    
  13.     graph = tf.Graph()  
  14.    
  15.     with graph.as_default(), tf.device(‘/cpu:0’):  
  16.    
  17.         # Input data.  
  18.         train_dataset = tf.placeholder(tf.int32, shape=[batch_size,2*skip_window])  
  19.         train_labels = tf.placeholder(tf.int32, shape=[batch_size, 1])  
  20.         valid_dataset = tf.constant(valid_examples, dtype=tf.int32)  
  21.    
  22.         # Variables.  
  23.         # embedding, vector for each word in the vocabulary  
  24.         embeddings = tf.Variable(tf.random_uniform([vocabulary_size, embedding_size], –1.01.0))  
  25.         softmax_weights = tf.Variable(tf.truncated_normal([vocabulary_size, embedding_size],  
  26.                          stddev=1.0 / math.sqrt(embedding_size)))  
  27.         softmax_biases = tf.Variable(tf.zeros([vocabulary_size]))  

向量查找與求平均

這裡我們要做些大的變動。我們要重新編寫 embedding lookup 並且正確地求出它們的平均值。總來的來說,我們要查找 train_dataset (大小為 b x 2*skip_window) 的每一行,查找行中詞ID對應的向量。然後將這些向量保存在臨時變量( embedding_i )中,在把這些向量連接起來稱為復合向量(embeds)(大小為 2*skip_window x b x D),進而在 axis 0 上求得 reduce mean 。最終我們可以對 data 的每個 batch 生成 train_labels 中詞相應上下文的平均向量。

  1. # Model.  
  2. embeds = None  
  3. for i in range(2*skip_window):  
  4.     embedding_i = tf.nn.embedding_lookup(embeddings, train_dataset[:,i])  
  5.     print(’embedding %d shape: %s’%(i,embedding_i.get_shape().as_list()))  
  6.     emb_x,emb_y = embedding_i.get_shape().as_list()  
  7.     if embeds is None:  
  8.         embeds = tf.reshape(embedding_i,[emb_x,emb_y,1])  
  9.     else:  
  10.         embeds = tf.concat(2,[embeds,tf.reshape(embedding_i,[emb_x,emb_y,1])])  
  11.    
  12. assert embeds.get_shape().as_list()[2]==2*skip_window  
  13. print(“Concat embedding size: %s”%embeds.get_shape().as_list())  
  14. avg_embed =  tf.reduce_mean(embeds,2,keep_dims=False)  
  15. print(“Avg embedding size: %s”%avg_embed.get_shape().as_list())  

以下是另一個 implementation.  

NewImage

 

和 skip-gram 不同,skip-gram 是 (input, output) pair.  Input 是 one-hot.  

CBOW 是 ([batch], label) pair.  batch 是多個 words.  Input 不是 one-hot, 而是 multiple-hot.

 

Training 時 multiple-hot 的 embedding lookup 的平均值,經過 softmax 得到 label.  

問題是如何得到單字, e.g. “Paris”, 的 embedding?   


Loss 函數以及優化

現在相較於skip-gram模型,我們在CBOW模型的 sampled_softmax_loss 中使用了平均向量。代碼方面沒有很大的變動。

  1. loss = tf.reduce_mean(tf.nn.sampled_softmax_loss(softmax_weights, softmax_biases, avg_embed,  
  2.                        train_labels, num_sampled, vocabulary_size))  
  3. optimizer = tf.train.AdagradOptimizer(1.0).minimize(loss)  
  4.    
  5. # We use the cosine distance:  
  6. norm = tf.sqrt(tf.reduce_sum(tf.square(embeddings), 1, keep_dims=True))  
  7. normalized_embeddings = embeddings / norm  
  8. valid_embeddings = tf.nn.embedding_lookup(normalized_embeddings, valid_dataset)  
  9. similarity = tf.matmul(valid_embeddings, tf.transpose(normalized_embeddings))  

運行程序

最後我們要來讓tensorflow跑起來。

  1. with tf.Session(graph=graph) as session:  
  2.     tf.initialize_all_variables().run()  
  3.     print(‘Initialized’)  
  4.     average_loss = 0  
  5.     for step in range(num_steps):  
  6.         batch_data, batch_labels = generate_batch(batch_size, skip_window)  
  7.         feed_dict = {train_dataset : batch_data, train_labels : batch_labels}  
  8.         _, l = session.run([optimizer, loss], feed_dict=feed_dict)  
  9.         average_loss += l  
  10.         if step % 2000 == 0:  
  11.             if step > 0:  
  12.                 average_loss = average_loss / 2000  
  13.                 # The average loss is an estimate of the loss over the last 2000 batches.  
  14.             print(‘Average loss at step %d: %f’ % (step, average_loss))  
  15.             average_loss = 0  
  16.         # note that this is expensive (~20% slowdown if computed every 500 steps)  
  17.         if step % 10000 == 0:  
  18.             sim = similarity.eval()  
  19.             for i in range(valid_size):  
  20.                 valid_word = reverse_dictionary[valid_examples[i]]  
  21.                 top_k = 8 # number of nearest neighbors  
  22.                 nearest = (-sim[i, :]).argsort()[1:top_k+1]  
  23.                 log = ‘Nearest to %s:’ % valid_word  
  24.                 for k in range(top_k):  
  25.                     close_word = reverse_dictionary[nearest[k]]  
  26.                     log = ‘%s %s,’ % (log, close_word)  
  27.                 print(log)  
  28.     final_embeddings = normalized_embeddings.eval()  

 

最終我們得到的結果如下

  1. Average loss at step 1000002.422888  
  2. Nearest to he: she, it, they, there, who, eventually, neighbors, theses,  
  3. Nearest to is: was, has, became, remains, be, becomes, seems, cetacean,  
  4. Nearest to some: many, several, certain, most, any, all, both, these,  
  5. Nearest to only: settling, orchids, commutation, until, either, first, alcohols, rabba,  
  6. …  
  7. Nearest to i: we, you, ii, iii, iv, they, t, lm,  
  8. Nearest to bbc: news, corporation, coffers, inactivity, mprp, formatted, cara, pedestrian,  
  9. Nearest to cost: cakes, length, completion, poking, measure, enforcers, parody, figurative,  
  10. Nearest to proposed: introduced, discovered, foreground, suggested, dismissed, argued, ecuador, builder,  

 問題是 given words[t], what is the embedding?  

 

 

 

Word Embeddings and Sentence Embeddings 最近進展 (2018)

Reference:

[1] J. Fjellestad in Medium, “The Current Best of Universal Word Embeddings and Sentence Embeddings”. (Chinese)

[2] 黃頌, 機器之心, “fastText,智慧与美貌并重的文本分类及向量化工具

[3] fastText in Github

 


前文討論 word embeddings, 特別是 Mikolov 的 word2vec based on skip-gram or CBOW.

 詞語和句子的嵌入已經成為了任何基於深度學習的自然語言處理系統必備的組成部分。

 它們將詞語和句子編碼成稠密的定長向量,從而大大地提升通過神經網絡處理文本數據的能力。

當前主要的研究趨勢是追求一種通用的嵌入技術:在大型語料庫中預訓練的嵌入,它能夠被添加到各種各樣下游的任務模型中(情感分析、分類、翻譯等),從而通過引入一些從大型數據集中學習到的通用單詞或句子的表徵來自動地提升它們的性能。 

它是遷移學習的一種體現形式。Transfer learning has been recently shown to drastically increase the performance of NLP models on important tasks such as text classification.

儘管在相當長的一段時間內,對句子的無監督表示學習已經成為了一種行業規範。但在最近的幾個月裡,人們開始逐漸轉向監督學習和多任務學習,並且在 2017 年底/2018 年初提出了一些非常有趣的方案。

NewImage

 

最近 Word Embeddings 的進展

在過去的五年中,人們提出了大量可行的詞嵌入方法。目前最常用的模型是 word2vec 和 GloVe,它們都是基於分佈假設(在相同的上下文中出現的單詞往往具有相似的含義)的無監督學習方法。

儘管此後有一些研究(https://arxiv.org/abs/1805.04032)通過引入語義或者句法的監督信息來增強這些無監督方法,但是純粹的無監督學習方法在 2017 年到 2018 年得到了令人關注的提升,最著名的是「FastText」(word2vec 的一種拓展)以及「ELMo」(目前最先進的基於上下文的詞嵌入技術)。

FastText 由 Tomas Mikolov 的團隊提出,他曾在 2013 年提出了著名的 word2vec 框架,引發了通用詞嵌入技術的研究浪潮。

FastText 相對於原始的 word2vec 向量最主要的提升是它引入了 n 元字符(n-gram),這使得對沒有在訓練數據中出現的單詞(詞彙表外的單詞)計算單詞的表徵成為了可能。

FastText 向量的訓練速度非常快,並且可以在 GitHub 上獲取通過「Wikipedia」和「Common Crawl」數據集上預訓練好的版本。它們是非常棒的對比基線。

深度上下文單詞表徵(ELMo)在很大的程度上提高了目前最先進的詞嵌入模型的性能。它們由 Allen 人工智能研究所研發,並將在 6 月初的 NAACL 2018(https://arxiv.org/abs/1802.05365)中展示。

 

FastText

fastText的主要作者 Mikolov 2012年到2014年就職於Google,隨後跳到了Facebook至今。

他名揚天下的,主要是以下三篇重要論文: 

1.Efficient Estimation of WordRepresentation in Vector Space, 2013 —— 這篇是word2vec的開蒙之作;

2.Distributed Representations ofSentences and Documents, 2014 —— 這篇將詞向量的思想擴展到了段落和文檔上;

3.Enriching Word Vectors withSubword Information, 2016 —— 這篇和fastText相關,引入了詞內的n-gram信息,豐富了詞向量的語義。

fastText是FAIR(Facebook AIResearch) 在2016年推出的一款文本分類與向量化工具。它的官網(fasttext.cc)上是這樣介紹的:

fastText開源、免費、輕量級,適用於文本分類和文本向量化表示場景,運行於標準硬件環境。裁剪壓縮過的模型甚至可以輕鬆跑在移動設備上。

fastText最驚豔的地方在於,和最前沿深度神經網絡模型相比,它在分類精度等指標毫不遜色的情況下,把訓練和推斷速度降低了幾個數量級!按Facebook的報告,在普通多核CPU上,10億詞的文本訓練時間小於10分鐘,50萬句子分到31.2萬類別用時小於1分鐘。

下面這張圖可以清楚地看到這一點,深度模型天級的訓練時間被壓榨到了秒級!

我實際 download fastText [3] 的 c code and compile.  同時用 text8 做 input data 如下。大約 1 分鐘就產生 model.bin and model.vec.  比起 word2vec 的 skip-gram 快的多 (~20min).

$ ./fasttext skipgram -input text8 -output model 

text8來源於enwiki8,而enwiki8最早是用來做文本壓縮的。簡單說來,enwiki8是從wikipedia上扒下來的前100,000,000個字符;而text8就是把這些字符當中各種奇怪的符號啊,非英文字符啊全都去掉,再把大寫字符轉化成小寫字符,把數字轉化成對應的英語單詞之後,得到的。

所以text8中只包含27種字符:小寫的從a到z,以及空格符。如果把它打出來,讀起來就像是去掉了所有標點的wikipedia。Matt Mahoney有一個網頁很詳細地說明了這個文件是如何來的,也包含了對文本內容一些基本分析:About the Test Data

 
fastText能夠做到效果好,速度快,主要依靠兩個秘密武器:一是利用了詞內的n-gram信息(subword n-gram information),二是用到了階層化 Softmax (Hierarchical Softmax) 的訓練trick。我們分別介紹一下。
Refresh: skip-gram 的秘密武器是用 negative sampling 化簡 softmax. 

Subword n-gram information 

在fastText的工作之前,大部分的文本向量化的工作,都是以詞彙表中的獨立單詞作為基本單元來進行訓練學習的。這種想法非常自然,但也會帶來如下的問題:

· 低頻詞、罕見詞,由於在語料中本身出現的次數就少,得不到足夠的訓練,效果不佳;

· 未登錄詞,如果出現了一些在詞典中都沒有出現過的詞,或者帶有某些拼寫錯誤的詞,傳統模型更加無能為力。

 fastText引入了subword n-gram的概念來解決詞形變化(morphology)的問題。直觀上,它將一個單詞打散到字符級別,並且利用字符級別的n-gram信息來捕捉字符間的順序關係,希望能夠以此豐富單詞內部更細微的語義。我們知道,西方語言文字常常通過前綴、後綴、字根來構詞,漢語也有單字表義的傳統,所以這樣的做法聽起來還是有一定的道理。

舉個例子。對於一個單詞“google”,為了表達單詞前後邊界,我們加入<>兩個字符,即變形為“<google>”。假設我們希望抽取所有的tri-gram信息,可以得到如下集合:G = { <go, goo, oog,ogl, gle, le>}。在實踐中,我們往往會同時提取單詞的多種n-gram信息,如2/3/4/5-gram。這樣,原始的一個單詞google,就被一個字符級別的n-gram集合所表達。

在訓練過程中,每個n-gram都會對應訓練一個向量,而原來完整單詞的詞向量就由它對應的所有n-gram的向量求和得到。所有的單詞向量以及字符級別的n-gram向量會同時相加求平均作為訓練模型的輸入

從實驗效果來看,subword n-gram信息的加入,不但解決了低頻詞未登錄詞的表達的問題,而且對於最終任務精度一般會有幾個百分點的提升。唯一的問題就是由於需要估計的參數多,模型可能會比較膨脹。不過,Facebook也提供了幾點壓縮模型的建議:

· 採用hash-trick。由於n-gram原始的空間太大,可以用某種hash函數將其映射到固定大小的buckets中去,從而實現內存可控;

· 採用quantize命令,對生成的模型進行參數量化和壓縮;

· 減小最終向量的維度。

需要注意的是以上幾種方法都會以一定的精度損失為代價,尤其是維度的壓縮,具體可以實踐中再權衡。

 

Hierarchical Softmax

另一個效率優化的點是所謂的層次化Softmax。

Softmax大家都比較熟悉,它是邏輯回歸(logisticregression)在多分類任務上的推廣,是我們訓練的神經網絡中的最後一層。一般地,Softmax以隱藏層的輸出h為輸入,經過線性和指數變換後,再進行全局的歸一化處理,找到概率最大的輸出項。當詞彙數量V較大時(一般會到幾十萬量級),Softmax計算代價很大,是O(V)量級。 

層次化的Softmax的思想實質上是將一個全局多分類的問題,轉化成為了若幹個二元分類問題,從而將計算複雜度從O(V)降到O(logV)。

每個二元分類問題,由一個基本的邏輯回歸單元來實現。如下圖所示,從根結點開始,每個中間結點(標記成灰色)都是一個邏輯回歸單元,根據它的輸出來選擇下一步是向左走還是向右走。下圖示例中實際上走了一條“左-左-右”的路線,從而找到單詞w₂。而最終輸出單詞w₂的概率,等於中間若干邏輯回歸單元輸出概率的連乘積。

至此,我們還剩下兩個問題,一是如何構造每個邏輯回歸單元的輸入,另一個是如何建立這棵用於判斷的樹形結構。

邏輯回歸單元的參數

每個邏輯回歸單元中,sigmoid函數所需的輸入實際上由三項構成,如下公式所示:

記號說明如下:

1. ⟦x⟧是一個特殊的函數,如果下一步需要向左走其函數值定義為1,向右則取-1。在訓練時,我們知道最終輸出葉子結點,並且從根結點到葉子結點的每一步的路徑也是確定的。

2. v’ 是每個內部結點(邏輯回歸單元)對應的一個向量,這個向量可以在訓練過程中學習和更新。

3. h 是網絡中隱藏層的輸出。 

因此,我們以隱藏層的輸出、中間結點對應向量以及路逕取向函數為輸入,相乘後再經過sigmoid函數,得到每一步邏輯回歸的輸出值。 

霍夫曼樹的構造

Hierarchical Softmax採用的樹型結構實際上是一棵二叉霍夫曼樹。

霍夫曼樹是在解決通信編碼過程中引入的。在通信過程中,需要將字符信息編碼成為0/1二進制串。顯然,給出現頻繁的字符較短的編碼,出現較少的字符以較長的編碼,是最經濟的方案。通過一棵霍夫曼樹的構造,我們讓越頻繁的字符離根結點越近,使得最終的通信編碼最短。

霍夫曼樹的構造步驟如下:

在做Hierarchical Softmax之前,我們需要先利用所有詞彙(類別)及其頻次構建一棵霍夫曼樹。這樣,不同詞彙(類別)作為輸出時,所需要的判斷次數實際上是不同的。越頻繁出現的詞彙,離根結點越近,所需要的判斷次數也越少。從而使最終整體的判斷效率更高。

 fastText和傳統CBOW模型對比

假設你對word2vec的CBOW模型熟悉,小結一下CBOW和fastText的訓練過程有什麼不同。下面兩張圖分別對應CBOW和fastText的網絡結構圖。 

兩者的不同主要在如下幾個方面:

· 輸入層:CBOW的輸入是目標單詞的上下文並進行one-hot編碼,fastText的輸入是多個單詞embedding向量,並將單詞的字符級別的n-gram向量作為額外的特徵;

· 從輸入層到隱藏層,CBOW會將上下文單詞向量疊加起來並經過一次矩陣乘法(線性變化)並應用激活函數,而fastText省略了這一過程,直接將embedding過的向量特徵求和取平均;

· 輸出層,一般的CBOW模型會採用Softmax作為輸出,而fastText則採用了Hierarchical Softmax,大大降低了模型訓練時間;

· CBOW的輸出是目標詞彙,fastText的輸出是文檔對應的類標。

 

GCP – Running Jupyter Notebook in 15min

Reference

[1] A. Aankul in Medium, “Running Jupyter Notebook on Google Cloud Platform in 15 min

 

[1] 提供很仔細的的介紹 running Jupyter notebook on GCP.

 

Step1-3:Create VM with Ubuntu 16.04 LTS OS.  

另外一個方式是直接用 GCP 已經建好的 tensorflow VM, 見前文。有兩個差異:

[1] 有 2 GPU cores (Nvidia K80);  tensorflow VM 是 CPU only.

[1] 是用 Ubuntu 16.04 LTS; tensorflow VM 是 Debian ?  (basically same as Ubuntu 16.04).

 

Step4-5: Make external IP address as static and change firewall setting (for remote access VM)

 

Step6-7:Start VM and Install tensorflow, keras, jupyter 

如果用 tensorflow VM 已經 install tensorflow.  Do:

$ pip install keras 

$ pip install jupyter

 

以下是重點部份

Step8:Set up the VM server for Jupyter

Open up a SSH session for the VM.  Create a configuration file.

$ jupyter notebook —generate-config

Then edit the file:

~/.jupyter/jupyter_notebook_config.py  加上

c = get_config()
c.NotebookApp.ip = '*'
c.NotebookApp.open_browser = False
c.NotebookApp.port = <Port Number>

 <port number> 就是 step 5 設定 firewall 的 TCP port number.

 

Step9:Launching Jupyter Notebook

To run jupyter notebook, type the following command in VM.

jupyter-notebook --no-browser --port=<PORT-NUMBER>

再來使用 browser and type the following:

http://<External Static IP Address>:<Port Number>

<IP address> 是前面設定的 static IP address.  <Port number> 是 firewall 設定的 port number.

 

 

 

NLP 自然語言處理 – word2vec 工具箱基於 skip-gram and CBOW

Reference:

[1] 天雨粟 in 知乎,“理解 Word2Vec 之 Skip-Gram 模型”, translation of [3]

[2] 天雨粟 in 知乎,“基於TensorFlow實現Skip-Gram模型”, translation of [4]

[3] C. McCormick, “Word2Vec Tutorial – The Skip-Gram Model”  – Excellent tutorial

[4] T. Ganegedara, “Word2Vec: NLP with Deep Learning with Tensorflow (Skip-gram) 

[5] T. Ganegedara, “Word2Vec: NLP with Deep Learning with Tensorflow (CBOW)

[6] AI 研習社, “一文詳解 Word2vec 之 Skip-Gram 模型 (結構訓練實現)“

 

Tip: negative sampling 對於非常大的 classification problem (using softmax function) 可以大幅降低 computation!

 

Word2Vec 模型中,主要有 skip-gram 和 CBOW 兩種模型。圖示如下圖:

NewImage
 
w(t) 是中心詞。其他 w(t-1), w(t+1), etc. 是上下文。 
 
用神經網絡實現方式如下:(以 skip-gram 為例)
Input vector 是用 one-hot representation, 非常長但稀疏的 vector (~10,000 x 1).
Output vector 是上下文 probability distribution.  同樣是非常長的 vector (~10,000 x 1).
Hidden layer 是降維後的 dense feature vector, 一般是 50~300 dimensions (~300 x 1).
 
NewImage
 

Auto-encoder vs. Skip-gram

這讓我們想起 auto-encoder for MNIST image encoding.  
 
1. 同樣是降維 (encoder, 10,000×300) 之後再升維 (decoder, 300×10,000).
 
2. 同樣是取 encoder (10,000×300) 作為 word embedding vectors.  Skip-gram 因為 input vector 是 one-hot, [0, …, 1, …0],
通過 encoder matrix (10,000×300) 得到對應的 1×300 word embedding vector. 所以 10,000×300 matrix 就是 10,000 words 的 embedding vector. 
 
下圖左右兩張圖分別從不同角度代表了 input-hidden layer 的權重矩陣。左圖中每一列代表一個10000維的詞向量和隱層單個神經元連接的權重向量。從右邊的圖來看,每一行實際上代表了每個單詞的詞向量。
 
NewImage
 
 
3. 同樣 decoder 主要目的是還原到高維。根據 output data 定義 loss function, back-prop 收斂 encoder and decoder matrix.
 
這也是 auto-encoder 和 skip-gram 的“小小”差異:
 
(a) Auto-encoder 的 output data 就是 input data, 不需要額外的 label, 算是 unsupervised “feature” learning.   
Skip-gram 同樣是 input data 本身包含 output data (context, 上下文), 也算是 unsupervised “feature” learning.  
 
(b) Auto-encoder 的 loss function 是 L2-loss function.  即使 dimension 大,計算 L2 loss 也很容易。back-prop 也簡單。  
Skip-gram 的 loss function 是最關鍵的部分。理論上是 10,000 維的 softmax function training!  非常大的計算量!
 
Output Layer (輸出層)

經過神經網絡隱層的計算,ants這個詞會從一個1 x 10000的向量變成1 x 300的向量,再被輸入到輸出層。輸出層是一個softmax 分類器,它的每個結點將會輸出一個0-1之間的機率,這些所有輸出層神經元結點的概率之和為1。

下面是一個例子,訓練樣本為 (input word: “ants”, output word: “car”) 的計算示意圖。

NewImage

需要針對 10,000 個 outputs 都要計算,非常費時。在 back-prop 也要再算一次。

 

我們擁有10000個單詞的詞彙表,我們如果想嵌入300維的詞向量,那麼我們的輸入-隱層權重矩陣隱層-輸出層的權重矩陣都會有 10000 x 300 = 300萬個權重,在如此龐大的神經網絡中進行梯度下降是相當慢的。更糟糕的是,你需要大量的訓練數據來調整這些權重並且避免過擬合。百萬數量級的權重矩陣和億萬數量級的訓練樣本意味著訓練這個模型將會是個災難。 

常見的 image object detection and classification 只有幾十類,最多上百類的 softmax function.  10,000 dimension 的 softmax function 一般很少遇到。每一次 forward pass and back prop path 需要計算 10,000 output 以及對應的 partition function.  需要其他的方法加速。 Negative sampling 用來解決這個問題。


Word2Vec 的作者 Mikolov 在它的第二篇論文中強調了這些問題,下面是作者在第二篇論文中的三個創新,大幅降低計算量以及增加準確率 [6]:

1. 將常見的單詞組合(word pairs)或者詞組作為單個“words”來處理。增加準確率。

2. 對高頻次單詞進行抽樣來減少訓練樣本的個數同時避免高頻詞的 bias.

3.  拆解 10,000 維的 softmax 變成 one positive sample + a few negative samples weight update!  對優化目標採用“negative sampling”方法,這樣每個訓練樣本的訓練只會更新一小部分的模型權重,從而降低計算負擔。 

事實證明,對常用詞 subsampling (2) 並且對優化目標採用“negative sampling” (3), 不僅降低了訓練過程中的計算負擔,還提高了訓練的詞向量的質量。

Word Pairs and “Phrases”

論文的作者指出,一些單詞組合(或者詞組)的含義和拆開以後具有完全不同的意義。比如“Boston Globe”是一種報刊的名字,而單獨的“Boston”和“Globe”這樣單個的單詞卻表達不出這樣的含義。因此,在文章中只要出現“Boston Globe”,我們就應該把它作為一個單獨的詞來生成其詞向量,而不是將其拆開。同樣的例子還有“New York”,“United Stated”等。

在Google發佈的模型中,它本身的訓練樣本中有來自Google News數據集中的1000億的單詞,但是除了單個單詞以外,單詞組合(或詞組)又有3百萬之多。

如果你對模型的詞彙表感興趣,可以點擊:

http://t.cn/RoVde3h

你還可以直接瀏覽這個詞彙表:

http://t.cn/RoVdsZr

如果想瞭解這個模型如何進行文檔中的詞組抽取,可以看論文中“Learning Phrases”這一章,對應的代碼在 word2phrase.c ,相關鏈接如下。

論文鏈接:

http://t.cn/RMct1c7

代碼鏈接:

http://t.cn/R5auFLz

從中文角度來看就是 “字  (word)” 和 “詞 (word pairs or phrases)” 分別出來而且同等對待。例如 “花” 和 “花生“ 就是獨立的 vocalulary.  

英文這樣的 word paris or phrases 大約有幾千個 (3218 in Mikolov paper).  

中文當然更多詞。另外中文還要先解決斷句的問題。”我喜歡吃花生糖“ => ”我 喜歡 吃 花生 糖“.

英文有 space 幫忙解決斷句問題。中文斷句可以用 python jieba (結巴) package.


對高頻詞抽樣(subsample)

一言以蔽之,就是對高頻字/詞採取樣 (subsample) 方式避免影響準確率。

如果原始文本為“The quick brown fox jumps over the laze dog”,如果我使用大小為2的窗口,那麼我們可以得到圖中展示的那些訓練樣本。

一文詳解 Word2vec 之 Skip-Gram 模型(訓練篇)

但是對於“the”這種常用高頻單詞,這樣的處理方式會存在下面兩個問題:

  1. 當我們得到成對的單詞訓練樣本時,(“fox”, “the”) 這樣的訓練樣本並不會給我們提供關於“fox”更多的語義信息,因為“the”在每個單詞的上下文中幾乎都會出現。

  2. 由於在文本中“the”這樣的常用詞出現概率很大,因此我們將會有大量的(”the“,…)這樣的訓練樣本,而這些樣本數量遠遠超過了我們學習“the”這個詞向量所需的訓練樣本數。

Word2Vec通過“抽樣”模式來解決這種高頻詞問題。它的基本思想如下:對於我們在訓練原始文本中遇到的每一個單詞,它們都有一定概率被我們從文本中刪掉,而這個被刪除的概率與單詞的頻率有關。
如果我們設置窗口大小,並且從我們的文本中刪除所有的“the”,那麼會有下面的結果:

1. 由於我們刪除了文本中所有的“the”,那麼在我們的訓練樣本中,“the”這個詞永遠也不會出現在我們的上下文窗口中。

2. 當“the”作為input word時,我們的訓練樣本數至少會減少10個。

這句話應該這麼理解,假如我們的文本中僅出現了一個“the”,那麼當這個“the”作為input word時,我們設置span=10,此時會得到10個訓練樣本 (“the”, …) ,如果刪掉這個“the”,我們就會減少10個訓練樣本。實際中我們的文本中不止一個“the”,因此當“the”作為input word的時候,至少會減少10個訓練樣本。

上面提到的這兩個影響結果實際上就幫助我們解決了高頻詞帶來的問題。

抽樣率

word2vec的C語言代碼實現了一個計算在詞彙表中保留某個詞概率的公式。

ω是一個單詞,Z(ωi) 是 ωi 這個單詞在所有語料中出現的頻次。舉個栗子,如果單詞“peanut”在10億規模大小的語料中出現了1000次,那麼 Z(peanut) = 1000/1000000000 = 1e – 6

在代碼中還有一個參數叫“sample”,這個參數代表一個閾值,默認值為0.001(在gensim包中的Word2Vec類說明中,這個參數默認為0.001,文檔中對這個參數的解釋為“ threshold for configuring which higher-frequency words are randomly downsampled”)。這個值越小意味著這個單詞被保留下來的概率越小(即有越大的概率被我們刪除)。

P(ωi) 代表著保留某個單詞的概率:

一文詳解 Word2vec 之 Skip-Gram 模型(訓練篇)

一文詳解 Word2vec 之 Skip-Gram 模型(訓練篇)

圖中x軸代表著 Z(ωi) ,即單詞 ωi 在語料中出現頻率,y軸代表某個單詞被保留的概率。對於一個龐大的語料來說,單個單詞的出現頻率不會很大,即使是常用詞,也不可能特別大。

從這個圖中,我們可以看到,隨著單詞出現頻率的增高,它被採樣保留的概率越來越小,我們還可以看到一些有趣的結論:

● 當 Z(ωi) <= 0.0026 時,P(ωi) = 1.0 。當單詞在語料中出現的頻率小於 0.0026 時,它是 100% 被保留的,這意味著只有那些在語料中出現頻率超過 0.26% 的單詞才會被採樣。

● 當時 Z(ωi) = 0.00746 時,P(ωi) = 0.5,意味著這一部分的單詞有 50% 的概率被保留。

● 當 Z(ωi) = 1.0 時,P(ωi) = 0.033,意味著這部分單詞以 3.3% 的概率被保留。

如果你去看那篇論文的話,你會發現作者在論文中對函數公式的定義和在C語言代碼的實現上有一些差別,但我認為C語言代碼的公式實現是更權威的一個版本。


負採樣(negative sampling)

訓練一個神經網絡意味著要輸入訓練樣本並且不斷調整神經元的權重,從而不斷提高對目標的準確預測。每當神經網絡經過一個訓練樣本的訓練,它的權重就會進行一次調整。

正如我們上面所討論的,vocabulary的大小決定了我們的Skip-Gram神經網絡將會擁有大規模的權重矩陣,所有的這些權重需要通過我們數以億計的訓練樣本來進行調整,這是非常消耗計算資源的,並且實際中訓練起來會非常慢。

負採樣(negative sampling)解決了這個問題,它是用來提高訓練速度並且改善所得到詞向量的質量的一種方法。不同於原本每個訓練樣本更新所有的權重,負採樣每次讓一個訓練樣本僅僅更新一小部分的權重,這樣就會降低梯度下降過程中的計算量。

當我們用訓練樣本 ( input word: “fox”,output word: “quick”) 來訓練我們的神經網絡時,“ fox”和“quick”都是經過one-hot編碼的。如果我們的vocabulary大小為10000時,在輸出層,我們期望對應“quick”單詞的那個神經元結點輸出1,其餘9999個都應該輸出0。在這裡,這9999個我們期望輸出為0的神經元結點所對應的單詞我們稱為“negative” word。

當使用負採樣時,我們將隨機選擇一小部分的negative words(比如選5個negative words)來更新對應的權重。我們也會對我們的“positive” word進行權重更新(在我們上面的例子中,這個單詞指的是”quick“)。也就是 1 positive word + a few negative words 的 weight update.

在論文中,作者指出指出對於小規模數據集,選擇5-20個negative words會比較好,對於大規模數據集可以僅選擇2-5個negative words。

回憶一下我們的隱層-輸出層擁有300 x 10000的權重矩陣。如果使用了負採樣的方法我們僅僅去更新我們的positive word-“quick”的和我們選擇的其他5個negative words的結點對應的權重,共計6個輸出神經元,相當於每次只更新 300 x 6 = 1800 個權重。對於3百萬的權重來說,相當於只計算了0.06%的權重,這樣計算效率就大幅度提高。

如何選擇negative words

我們使用“一元模型分佈(unigram distribution)”來選擇“negative words”。
要注意的一點是,一個單詞被選作negative sample的概率跟它出現的頻次有關,出現頻次越高的單詞越容易被選作negative words。
在word2vec的C語言實現中,你可以看到對於這個概率的實現公式。每個單詞被選為“negative words”的概率計算公式與其出現的頻次有關。
代碼中的公式實現如下:

一文詳解 Word2vec 之 Skip-Gram 模型(訓練篇)

每個單詞被賦予一個權重,即 f(ωi), 它代表著單詞出現的頻次。

公式中開3/4的根號完全是基於經驗的,論文中提到這個公式的效果要比其它公式更加出色。你可以在google的搜索欄中輸入“plot y = x^(3/4) and y = x”,然後看到這兩幅圖(如下圖),仔細觀察x在[0,1]區間內時y的取值,x^(3/4) 有一小段弧形,取值在 y = x 函數之上。

一文詳解 Word2vec 之 Skip-Gram 模型(訓練篇)

負採樣的C語言實現非常的有趣。unigram table有一個包含了一億個元素的數組,這個數組是由詞彙表中每個單詞的索引號填充的,並且這個數組中有重複,也就是說有些單詞會出現多次。那麼每個單詞的索引在這個數組中出現的次數該如何決定呢,有公式,也就是說計算出的負採樣概率*1億=單詞在表中出現的次數

有了這張表以後,每次去我們進行負採樣時,只需要在0-1億範圍內生成一個隨機數,然後選擇表中索引號為這個隨機數的那個單詞作為我們的negative word即可。一個單詞的負採樣概率越大,那麼它在這個表中出現的次數就越多,它被選中的概率就越大。

到目前為止,Word2Vec中的Skip-Gram模型就講完了,對於裡面具體的數學公式推導細節這裡並沒有深入。這篇文章只是對於實現細節上的一些思想進行了闡述。

 

Word2vec Tensorflow 實現 (Python 3 OK; Python 2 有問題!) [1]

Data set: wiki (english)

Editor: jupyter notebook

https://github.com/vyomshm/Skip-gram-Word2vec


文章主要包括以下四個部分進行代碼構造:

– 數據預處理
– 訓練樣本構建
– 模型構建
– 模型驗證

1 數據預處理

數據預處理部分主要包括:

  • 替換文本中特殊符號並去除低頻詞
  • 對文本分詞
  • 構建語料
  • 單詞映射表

首先我們定義一個函數來完成前兩步,即對文本的清洗和分詞操作。

NewImage

上面的函數實現了替換標點及刪除低頻詞操作,返回分詞後的文本。 

下面讓我們來看看經過清洗後的數據:

NewImage

NewImage

我們還可以看一下文本和詞典的規模大小:

NewImage

整個文本中單詞大約為1660萬的規模,詞典大小為6萬左右,這個規模對於訓練好的詞向量其實是不夠的,但可以訓練出一個稍微還可以的模型。


 

2 訓練樣本建構

我們知道skip-gram中,訓練樣本的形式是(input word, output word),其中output word是input word的上下文。

為了減少模型噪音並加速訓練速度,我們在構造batch之前要對樣本進行採樣 (subsampling),剔除停用詞等噪音因素。

 

採樣 (subsampling)

 

在建模過程中,訓練文本中會出現很多“the”、“a”之類的常用詞(也叫停用詞),這些詞對於我們的訓練會帶來很多噪音。在上一篇Word2Vec中提過對樣本進行抽樣,剔除高頻的停用詞來減少模型的噪音,並加速訓練。

 

我們採用以下公式來計算每個單詞被刪除的概率大小:

 

一文詳解 Word2vec 之 Skip-Gram 模型(實現篇)

 

其中 f(wi) 代表單詞 w的出現頻次。t為一個閾值,一般介於1e-3到1e-5之間。

t 是閥值。 f(wi) = word_count / total_count 是很小的值。

prob_drop 是 drop probability, 原則上是 between 0~1.  

NewImage

以下是用 pycharm debugging 的結果。Subsampling 過後的 trained_words 大小從 16680599 刪成 4627182.  

NewImage


構造batch

我們先來分析一下skip-gram的樣本格式。skip-gram不同於CBOW,CBOW是基於上下文預測當前input word。而skip-gram則是基於一個input word來預測上下文,因此一個input word會對應多個上下文。我們來舉個例子 “The quick brown fox jumps over lazy dog”,如果我們固定skip_window=2的話,那麼fox的上下文就是[quick, brown, jumps, over],如果我們的batch_size=1的話,那麼實際上一個batch中有四個訓練樣本。

上面的分析轉換為代碼就是兩個步驟,第一個是找到每個input word的上下文,第二個就是基於上下文構建batch。

首先是找到input word的上下文單詞列表:

NewImage

R 是 random number bounded by window size.  Target_words 是 idx 前後 R 個 words.   

NewImage

 

我們定義了一個get_targets函數,接收一個單詞索引號,基於這個索引號去查找單詞表中對應的上下文(默認window_size=5)。請注意這裡有一個小trick,在實際選擇input word上下文時,使用的窗口大小是一個介於[1, window_size]區間的隨機數 (window size=10 in the above example)。這裡的目的是讓模型更多地去關注離input word更近詞。

 

我們有了上面的函數後,就能夠輕鬆地通過input word找到它的上下文單詞。有了這些單詞我們就可以構建我們的batch來進行訓練:

NewImage

注意上面的代碼對batch的處理。我們知道對於每個input word來說,有多個output word(上下文)。例如我們的輸入是“fox”,上下文是[quick, brown, jumps, over],那麼fox這一個batch中就有四個訓練樣本[fox, quick], [fox, brown], [fox, jumps], [fox, over]。

NewImage

如上例 (ii=0) x: [5233, 5233, 5233, 5233] and y: [27349, 741, 10571, 3133]  ~ x: [fox, fox, fox, fox]  and y: [quick, brown, jumps, over]  

如下例 (ii=1) 再加上更多的 (x,y).
NewImage
 
 

3 模型構建

數據預處理結束後,就需要來構建我們的模型。在模型中為了加速訓練並提高詞向量的質量,我們採用負採樣方式進行權重更新。

Input layer 到 hidden layer (encoder)

輸入層到隱層的權重矩陣作為嵌入層要給定其維度,一般embeding_size設置為50-300之間。

encoder weight matrix (vocal_size x embedding_size) or (16680599 x 200) 就是我們要找的 embedding!

NewImage

這麼大的 matrix 如果用矩陣乘法非常耗費計算資源。因為 input 是 one-hot, 可以直接用 table lookup 實現!!

Hidden layer 的 lookup 通過 TensorFlow 中的 embedding_lookup 實現(自己會處理 forward and backward prop),詳見:

http://t.cn/RofvbgF

Hidden Layer to Output Layer (decoder)

在skip-gram中,每個input word的多個上下文單詞實際上是共享一個權重矩陣,我們將每個(input word, output word)訓練樣本來作為我們的輸入。為了加速訓練並且提高詞向量的質量,我們採用negative sampling的方法來進行權重更新。Hidden layer to output layer (labels) 就是一個非常大的 softmax function!

NewImage

TensorFlow中的sampled_softmax_loss,由於進行了negative sampling,所以實際上我們會低估模型的訓練loss。詳見:http://t.cn/RofvS4t

請注意代碼中的softmax_w的維度是vocab_size x embedding_size!(16680599 x 200),這是因為TensorFlow中的sampled_softmax_loss中參數weights的size是[num_classes, dim]。

4 模型驗證

在上面的步驟中,我們已經將模型的框架搭建出來,下面就讓我們來訓練訓練一下模型。為了能夠更加直觀地觀察訓練每個階段的情況。我們來挑選幾個詞,看看在訓練過程中它們的相似詞是怎麼變化的。

一文詳解 Word2vec 之 Skip-Gram 模型(實現篇)

訓練模型:注意是 for x, y in batches, 所以是一個一個 word pair {fox, quick} training, 加上 negative sampling.

一文詳解 Word2vec 之 Skip-Gram 模型(實現篇)

在這裡注意一下,儘量不要經常去讓代碼打印驗證集相似的詞,因為這裡會多了一步計算步驟,就是計算相似度,會非常消耗計算資源,計算過程也很慢。所以代碼中我設置1000輪打印一次結果。

一文詳解 Word2vec 之 Skip-Gram 模型(實現篇)

從最後的訓練結果來看,模型還是學到了一些常見詞的語義,比如one等計數詞以及gold之類的金屬詞,animals中的相似詞也相對準確。

為了能夠更全面地觀察我們訓練結果,我們採用sklearn中的TSNE來對高維詞向量進行可視化。詳見:http://t.cn/Rofvr7D

一文詳解 Word2vec 之 Skip-Gram 模型(實現篇)

上面的圖中通過TSNE將高維的詞向量按照距離遠近顯示在二維坐標系中,該圖已經在git庫中,想看原圖的小夥伴去git看~

我們來看一下細節:

一文詳解 Word2vec 之 Skip-Gram 模型(實現篇)

上面是顯示了整張大圖的局部區域,可以看到效果還不錯。

關於提升效果的技巧:

  • 增大訓練樣本,語料庫越大,模型學習的可學習的信息會越多。

  • 增加window size,可以獲得更多的上下文信息。

  • 增加embedding size可以減少信息的維度損失,但也不宜過大,我一般常用的規模為50-300。

 

GCP Tensorflow

 

Google Cloud Platform (GCP) 有一些已經建好的 VM. 只要花 10 分鐘就可以 run tensorflow.

先選 Cloud Launcher -> Search -> “tensorflow”

NewImage

 

 

小本經營就選:Tensorflow CPU Production.  

NewImage

 

OS: Debian 9 (~Ubuntu 16.04).  Python 3.6;  Tensorflow 1.5

NewImage

 

建立一個 VM with tensorflow. 10G SSD.

NewImage

NewImage

 

NLP 自然語言處理 – Word Embedding/Vector 詞嵌入/詞向量

Reference

[1] Andrew Ng, Coursera, “Sequence Model”

[2] 知乎, “有誰可以解釋下word embedding?

[3] T. Mikolov, Efficient Estimation of Word Representations in Vector Space” (skip-gram)

[4] T. Mikolov, Distributed Representations of Words and Phrases and their Compositionality

[5] 李韶華,“詞嵌入原理

[6] Google tensorflow tutorial, “Vector Representations of Words

[7] Baroni, et al, “Don’t count, predict! A Systematic Comparison of Context-counting vs. Context-predicting semantic vectors


Word Embedding  

Embedding 就是數學上的 injective (單射函數)  f: X->Y 和 structure-preserving (保存結構?)。

Word embedding 可以視為從高維空間的稀疏 one-hot representation 嵌入到低維空間的 dense vector representation.

One-hot encoding 的問題:

-高維(幾萬-幾十萬),高度稀疏。

-看不出不同詞之間的相似性。

-難以做模糊匹配。

 

-Discrete, hard to implement gradient base optimization algorithm

 

 

詞映射到嵌入空間中的低維連續向量

-向量方向編碼語義

-Cosine 相似度衡量相似性

-向量長度反映詞的“語義選擇性”。愈長的向量愈少 neighborhood

-Continuous in vector space.  Easily integrate with gradient base algorithm.

NewImage

 

Word vector 的好處是可以用上向量計算。例如計算兩個 vectors 的相似度 (cosine)。 


一旦找到 word embedding, 就可以繼續之後的 NLP tasks, 例如 sentimental analysis, translation, etc.


第一步是如何處理高維到低維的 mapping?  之前常用的是 linear dimension reduction 的 PCA,

或是 nonlinear dimension reduction 的 autoencoder or MDS or t-SNE.  

不過以上的算法都是高維的 data 已經有 make sense 的結構。例如 MNIST 的影像。降維只是保存結構。

Word embedding 的 one-hot code book 並沒有特別的結構,基本是 random structure. 

因此 word embedding 同時要降維以及找出結構。怎麼做? 以及如何評估效能?


 

Word Embedding – Neighbour Word Distribution

我思故我在。字思(自私)不存在 🙂  字的意義有時是由上下文決定。

“[7] A long tradition in computational linguistics has shown that contextual information provides a good approximation to word meaning, since semantically similar words tend to have similar contextual distributions” 

“In concrete, distributional semantic models (DSMs) use vectors that keep track of the contexts (e.g., co-occurring words) in which target terms appear in a large corpus as proxies for meaning representations, and apply geometric techniques to these vectors to measure the similarity in meaning of the corresponding words”

DSM 分為兩種:Count model (refer to the traditional way since it initialize vectors with co-occurrence counts), and Predict(ive) model for the training based model.

Count model: e.g. DISSECT toolkit, based on Pointwise Mutual Information (PMI) and SVD.

Predict model: e.g. word2vec toolkit, based on skip-gram and CBOW (Continuous Bag of Word, Mikolov).

in a nutshell: Count-based methods compute the statistics of how often some word co-occurs with its neighbor words in a large text corpus, and then map these count-statistics down to a small, dense vector for each word.

Predictive models directly try to predict a word from its neighbors in terms of learned small, dense embedding vectors (considered parameters of the model).

[7] 的結論是 Don’t count, predict!  

 

Word embedding predict model 最主要的精髓是 explore neighbour word (probability) distribution.

這有點像 Google search engine 的 Page ranking 算法。連結 link 多的 website 的 page rank 比較高。


*中心詞:正在討論的詞

*鄰居詞:中心詞周圍 window 內出現的詞

*Window 的大小 c 由我們定義 

* Neighbour word distribution 是幾萬維/幾十萬維的離散分佈


相似词为什么映射到相似方向?

* 假设1: 相似词的邻居词分布类似 (出现很多词都一 样, 相同词的出现频率类似) •

* 倒推: 两个词的邻居词分布类似 => 两个词语义相近 •

* 假设2: 邻居词的分布间接反映了词的大部分语义 – 这种语义是粗糙的大略的, 不那么精确 •

* 诀窍: 映射时不考虑语义, 只考虑邻居词 •

* 词向量是邻居词分布的一个“缩影”(降维表示) •

* 猫, 狗邻居词分布类似 => v(“猫”)≈v(“狗”)


词嵌入向量长度反映了语义选择性

* 向量长度反映词的“语义选择性” •

* 越长的向量对邻居词越“挑剔” •

* “冷”和“低温”是同义词 •

– 用处广

– 邻居词多, 每个邻居词概率相对低些 •

低温

– 多用来描述天气

– 邻居词少, 每个邻居词概率相对高些 •

* |v(“低温”)|>|v(“冷”)| •

* 停用词 (the, a) 的向量最短


Word Embedding Method

Word embedding method 主要是 regression

– 參數:中心詞 wi 和 鄰居詞 wj 的向量

Fit objective:

– Conditional probability P(wj | wj)  –  word2vec   (discriminative model)

– Bigram probability P(wi, wj) – GloVe   (generative model?)



Word2vec Toolbox [6] 

[3-4] 提出 word2vec 的工具包,裡面包含幾種 word embedding 的方法。這些方法有兩個特點。
一個特點是速度快;另一個特點是 embedding vectors 具備 analogy 性質。
Analogy 性質類似於 “A-B=C-D” 這樣的結構。舉例說明:“北京-中國=巴黎-法國”。

 

Mikolov 認為具備這樣的性質,說明得到的 embedding vectors 性質非常好,能夠 model 到語義。

Word2vec 是一種 neural probabilistic language model (NPLM).  

一般的 NPLM training 是用 maximum likelihood (ML) principle to maximise the conditional probability of the next word wt (target) given the previous words h (history) using softmax function (maximum entropy principle) 

NewImage 

This yields a properly normalized probabilistic model for language modeling. However this is very expensive, because we need to compute and normalize each probability using the score for all other V V words w’w′ in the current context hhat every training step.

NewImage 

On the other hand, for feature learning in word2vec we do not need a full probabilistic model. The CBOW and skip-gram models are instead trained using a binary classification objective (logistic regression) to discriminate the real target words wtwt from kk imaginary (noise) words w~w~, in the same context. We illustrate this below for a CBOW model. For skip-gram the direction is simply inverted.

Mathematically, the objective (for each example) is to maximize

NewImage

where Qθ(D=1|w,h)Q(D=1 | w,h) is the binary logistic regression probability under the model of seeing the word ww in the context hh in the dataset DD, calculated in terms of the learned embedding vectors θθ. In practice we approximate the expectation by drawing kk contrastive words from the noise distribution (i.e. we compute a Monte Carlo average).

This objective is maximized when the model assigns high probabilities to the real words, and low probabilities to noise words. Technically, this is called Negative Sampling, and there is good mathematical motivation for using this loss function: The updates it proposes approximate the updates of the softmax function in the limit. But computationally it is especially appealing because computing the loss function now scales only with the number of noise words that we select (kk), and not all words in the vocabulary (VV). This makes it much faster to train. We will actually make use of the very similar noise-contrastive estimation (NCE) loss, for which TensorFlow has a handy helper function tf.nn.nce_loss().

其實我也不是很懂 negative sampling 的意義。還是看一個例子。

Skip-gram Model:

the quick brown fox jumped over the lazy dog

We first form a dataset of words and the contexts in which they appear. We could define ‘context’ in any way that makes sense.  

For now, let’s stick to the vanilla definition and define ‘context’ as the window of words to the left and to the right of a target word. Using a window size of 1, we then have the dataset

([the, brown], quick), ([quick, fox], brown), ([brown, jumped], fox), ...

of (context, target) pairs. Recall that skip-gram inverts contexts and targets, and tries to predict each context word from its target word, so the task becomes to predict ‘the’ and ‘brown’ from ‘quick’, ‘quick’ and ‘fox’ from ‘brown’, etc. Therefore our dataset becomes

 (quick, the), (quick, brown), (brown, quick), (brown, fox), …

of (input, output) pairs. The objective function is defined over the entire dataset, but we typically optimize this with stochastic gradient descent (SGD) using one example at a time (or a ‘minibatch’ of batch_size examples, where typically 16 <= batch_size <= 512). So let’s look at one step of this process.

Let’s imagine at training step t we observe the first training case above, where the goal is to predict the from quick. We select num_noise number of noisy (contrastive) examples by drawing from some noise distribution, typically the unigram distribution, P(w). For simplicity let’s say num_noise=1 and we select sheep as a noisy example. Next we compute the loss for this pair of observed and noisy examples, i.e. the objective at time step t becomes

 

JNEG(t)=log Qθ(D=1|the, quick)+log (Qθ(D=0|sheep, quick

 

)

The goal is to make an update to the embedding parameters θ to improve (in this case, maximize) this objective function. We do this by deriving the gradient of the loss with respect to the embedding parameters θ.

其實以上的說明我還是很迷惑。後來看到另一篇文章用 autoencoder 解釋覺得茅塞頓開。見下文。




貝葉斯定理和 naive Bayes 分類器

Reference 

[1] Wiki, “Maximum A Posteriori Estimation”

[2] T. Cover, “Element of Information Theory 2nd Edition, Solution to Problem” 

[3] cnblogs 壹讀, “樸素貝葉斯算法

[4] Wiki, “Naive Bayes classifier

[5] Stanford notes, “Text Classification and Naive Bayes

 

貝葉斯定理簡單說

1. Probability, 而且是 conditional probability.  P(x|y), given condition or evidence y, 求 P(x|y) 的機率。 

2. 連結 prior and posterior probably 的橋樑。 P(x|y) and P(y|x) 的關係。

P(x|y) = P(x, y) / P(y) = P(y|x) P(x)/P(y) = P(y|x) P(x) / Σ P(y|x) P(x)

 

數學公式是死的,例子是活的。我們看幾個例子。

 

1. Binary Asymmetric Source Plus Symmetric Channel (BSC)

NewImage

P(Y=0 | X=0) = P(Y=1 | X=1) = 1-p   (correct)

P(Y=1 | X=0) = P(Y=0 | X=1) = p    (error) 

我們要解 Given Y=0  (or Y =1),  P(X | Y)?

或是分類器只要解: P(X=0 | Y=0) 大於或小於 P(X=1 | Y=0)   (判斷為 X=0 or 1)

i.e. argmax_x P(X|Y)

 

直觀而言:假設 p~0,(同向 + 小雜訊): Y=0(1) =>  X=0(1),  

i.e.  P(Y=0 | X=0) > P(Y=0 | X=1)  ( 1-p > p) 取 X^=0 

P(Y=1 | X=0) < P(Y=1 | X=1)  ( p > 1-p) 取 X^=1

p~1 (反向 + 小雜訊):  Y=0(1) =>  X=1(0),  

i.e. P(Y=0 | X=0) < P(Y=0 | X=1)   (1-p < p) 取 X^=1

P(Y=1 | X=0) > P(Y=1 | X=1)  ( p > 1-p) 取 X^=0

這種直觀法稱為 Maximum Likelihood principle (ML)!!  意即用 P(Y|X) (likelihood) 代替 P(X|Y) (posterior).

i.e. argmax_x P(Y|X)

 

直觀上好像 ok, 但有例外嗎?Yes

極端的 case, 假設 P(X=0)=1 and P(X=1)=0.  就是 X 永遠只送 “0”.

同時 p = 0.1 (10% 0->1 or 1->0 error).   此時如果用 Y = X, 會有 10% error!

如果用 Y=0, 則是 0% error.   這代表 P(X) 扮演重要的角色。

數學而言:

P(X|Y) = P(Y|X) P(X)/P(Y)   因為是 given Y (0 or 1), 計算 P(X|Y), 所以 P(Y) 可視為常數。

Posterior = Likelihood * Prior / Evidence   (Post = LPrior/E)

P(X|Y) ~ P(Y|X) P(X)  when Y is given

argmax_x P(X|Y) = argmax_x P(Y|X) P(X)

這種方法稱為  Maximum A Posteriori principle (MAP)!!  是貝葉斯定理的簡單應用。


回到 BSC 問題:

P(X=0 | Y=0) ~ P(Y=0 | X=0)*P(X=0) = (1-p)*P(X=0) = (1-p)*s  

P(X=1 | Y=0) ~ P(Y=0 | X=1)*P(X=1) =  p*P(X=1)=p*(1-s)

同樣

P(X=0 | Y=1) ~ P(Y=1 | X=0)*P(X=0) = p*P(X=0) = p*s 

P(X=1 | Y=1) ~ P(Y=1 | X=1)*P(X=1) =  (1-p)*P(X=1)=(1-p)*(1-s)

where s=P(X=0)

 

如果 s=P(X=0)=0.5  也就是 source 是 uniform distribution,  ML estimation =  MAP estimation.

但如果 s=P(X=0)=1   ; X 永遠送 “0″   

ML (assuming p is small):

{P(Y=0 | X=0) = 1-p}  >  { P(Y=0 | X=1)=p }   =>  X^ = 0 

{P(Y=1 | X=0) = p}  <  { P(Y=1 | X=0)=1-p }   =>  X^ = 1

MAP:

{P(X=0 | Y=0) = 1-p}  >  { P(X=1 | Y=0)=0 }   =>  X^ = 0

{P(X=0 | Y=1) = p}  >  { P(X=1 | Y=0)=0 }  =>  X^ = 0

MAP 永遠解 “0”, 如我們預期。

 

2. HIV (Binary Asymmetric Source Plus Asymmetric Channel)

Problem Denoted blood is screened for AIDS. Suppose the test has 99% accuracy, and that one in ten thousand people in your age group are HIV positive. The test has a 5% false positive rating, as well. Suppose the test screens you as positive. What is the probability you have AIDS? Is it 99%?

這個問題有兩個角度。一個是從 performance metric 來看:

NewImage

以 HIV 為例:actual positive = 1;  actual negative = 10,000-1 = 9999

TP+FN=1    FP+TN=9999   positive rate (非 TPR) = 1/10000

HIV test FPR = FP/(FP+TN) = 0.05  =>  FP = 0.05 * (FP+TN) = 0.05 * 9999 = 499.95

TN = 9999 – 499.95 = 9499.05

Test accuracy = P(predict positive | actual positive) = recall = TP / (TP+FN) = 0.99   TP/1 = 0.99

=> TP = 0.99  =>  FN = 0.01

P(actual positive | predict positive) = TP/(TP+FP) = Precision = 0.99 / (0.99 + 499.95) = 1/501 = 0.198%!!

 

另一個角度是套用貝葉斯公式:

Prior:  P(X=1) = 1/10000 = 0.0001 or 0.01% or 100 ppm

Likelihood:  

Test accuracy = Recall = True positive rate = P(Y=1 | X=1) = 0.99  =>  P(Y=0 | X=1) = 0.01

False positive rate:  P(Y=1 | X=0) = 0.05  => P(Y=0 | X=0) = 0.95

Now to find:  P( X=1 | Y=1) or other posterior probability

Step1:   

P(X=1 | Y=1) ~  P(Y=1 | X=1) * P(X=1) = 0.99 * 0.0001 = 0.000099 or 99ppm

P(X=0 | Y=1) ~ P(Y=1 | X=0) * P(X=0) = 0.05* (1-100ppm) = 0.05

Step 2: normalize the probability

P(X=1 | Y=1) = 99 ppm / (0.05 + 99ppm) = 19.8e-4 = 0.0198% ~ 0.02%  !!

P(X=0 | Y=1) = 1-0.02% = 99.98%

 

總結來說: 

Prior:  P(X=1) = (TP+FN) / (TP+FN+FP+TN) = 100ppm

Likelihood 包含兩項:

Recall=True Positive Rate: P(Y=1 | X=1)=P(predicted positive |actual positive) = TP/(TP+FN)= 0.99

False positive Rate: P(Y=1 | X=0) = P( predicted positive | actual negative) = FP / (FP+TN) = FPR = 0.05

 

貝葉斯公式就是給 Prior, Likelihood (accuracy and false positive), 求 Posterior 也就是 Precision!

Posterior:  P(X=1 | Y=1) = P( actual positive | predicted positive) = TP / (TP+FP) = Precision

TP / (TP+FP) = {[TP/(TP+FN)]*[(TP+FN)/(all)]} / {  [TP/(TP+FN)]*[(TP+FN)/(all)] + [FP/(FP+TN)]*[(FP+TN)/(all)] }

Precision = Recall * P(X=1) /  { Recall * P(X=1) + FPR * P(X=0) }

 

 

什麼時候 Precision 會很差 =>  (1) Recall * P(X=1) << FPR * P(X=0)

(2) 貪婪法 Recall~1,  P(X=1) 需要很小,  P(X=0)~1 =>  P(X=1) << FPR  =>  Prior << FPR

 

什麼時候 Recall 會很差 =>  Recall * P(X=1) >> FPR * P(X=0)

保守法 Precision~1 => FPR * P(X=0) << Recall * P(X=1)  => FPR ~ 0 or P(X=0)~0 (Prior~1) or both

 

 

3. Binary Asymmetric Source Plus Asymmetric Channel 

1. assuming additive (Gaussian) noise

2. adjust the threshold

NewImage

NewImage

 

(Prior) True Positive   ——— 1-p1 (Recall) ————>  Predicted Positive

                        ———\                —— p2 (FPR)/

                                    — p1 ——\

(Prior) True Negative      ———  ——-  ———————> Predicted negative

 

Adjust the threshold can control the trade-off between p1 (Recall, FN) and p2 (FPR, FP).

The dot goes to predicted positive from two path:  True positive -> Recall (1-p1)  +  True negative -> FPR (p2)

Bayes formula :    (Posterior) Precision  = Prior * Recall / (Prior * Recall + (1-Prior) * FPR)

 

Likelihood:  Recall and FPR

Posterior:  Precision

如同 ML and MAP estimation 比較。

何時 Recall (likelihood) = Precision (posterior)? 

1. (Source) Prior is uniform/symmetric:  P(X=1)=P(X=0);  AND

2.  (Channel) is symmetric: p1=p2

Precision = Recall / (Recall + FPR) = (1-p1) / (1-p1 + p2)  = 1-p1 = Recall

 

何時 Recall (likelihood) and Precision (posterior) 有很大的差異? 

1. Source prior 非常 asymmetric (很大或很小); OR

2. Channel 非常 asymmetric (特別厭惡 false positive or false negative 而改變 decision threshold 造成 p1 and p2 差異很大) 

 

4. Binary Source Plus Multiple Channel Model -Naive Bayes

以上是假設一個 channel.  如果是兩個 channels 產生的 outputs:  

X -> Y1 (p11 and p12), and X-> Y2 (p21 and p22)

如何得到 MAP  argmax_x P(X | Y1, Y2)?

例如 HIV 的 screening 有兩種方法,Y1 and Y2.  直覺而言 posterior 應該比一個方法更好。

P(X | Y1, Y2) = P(X, Y1, Y2) / P(Y1, Y2)   同樣 P(Y1, Y2) 只是常數,可以最後在 normalize.

重點在 joint PDF P(X, Y1, Y2)  

Using chain rule:  P(X, Y1, Y2) = P(Y1, Y2, X) = P(Y1 | Y2, X) * P(Y2 | X) * P(X)

if P(Y1|Y2, X) = P(Y1|X) 所有 information 都在 X,  Y2 沒有多加任何新的 information

P(Y1,Y2,X)*P(X)=P(Y2,X)*P(Y1,X) => P(Y1,Y2,X)/P(X)=P(Y1,X)/P(X)*P(Y2,X)/P(X)=>P(Y1,Y2|X)=P(Y1|X)*P(Y2|X)

=> 兩個 channels P(Y1|X) and P(Y2|X) are conditionally independent ! 

Y1 and Y2 沒有獨立(因為都來自 X), 但是 channels, i.e. (p11, p12) and (p21, p22) 是獨立 noise source.  

 

Posterior ~ Likelihood * Prior / Evidence

Posterior: P(X | Y1, Y2) 

Likelihood:  P(Y1|X) * P(Y2|X)

Prior:   P(X)

Evidence = Z = Σ_YZ (Likelihood * Prior)

對於分類器而言,Z 只是常數不重要。

argmax_x P(X | Y1, Y2) = argmax_x P(X, Y1, Y2) = argmax_x P(Y1|X) * P(Y2|X) * P(X)  假設 conditionally independent

= argmax_x  log[ P(Y1|X) * P(Y2|X) * P(X)] = argmax_x { Σ log-Likelihood + log-Prior }

注意以上的公式可以推廣到 multiple channels!! 同樣假設 multiple channels 都互相條件獨立!!


從 information theory 來看,X ->  (Y1, Y2)  可以參考 [2] p. 187.

Y1 and Y2 are conditionally independent and conditionally identically distributed given X

P(X, Y1, Y2) = P(Y1|X)*P(Y2|X)*P(X)

I(X; Y1, Y2) = H(Y1, Y2)  – H(Y1, Y2 | X) = H(Y1, Y2) – H(Y1|X) – H(Y2|X)

= H(Y1) + H(Y2) – I(Y1; Y2) – H(Y1|X) – H(Y2|X) = I(X; Y1) + I(X; Y2) – I(Y1; Y2)

If Y1 and Y2 are independent;  I(Y1; Y2) = 0

However, Y1 and Y2 are NOT independent!!  所以 I(Y1; Y2) > 0!

The capacity of single look channel X -> Y1 is   C1 = max I(X; Y1) 

The capacity of the channel  X -> (Y1, Y2) is C’ = max I(X; Y1, Y2) = C1+C2 – I(Y1; Y2) < C1+C2

max{C1, C2}  <  C’  <  C1+C2     實務上 C’ 不可能大於 1-bit 因為 source H(X) ≤ 1-bit

 

回到原來問題。這種假設 channel are conditionally independent model 就是 naive Bayes model. 

可以從 binary 分類器直接推廣到 multiple class 分類器。

 

幾個應用例子:

EX1. 病人分類[3]:Count and Laplace Smoothing

某個醫院早上收了六個門診病人,如下表。

症狀 (Y1) 職業 (Y2) 疾病 (X)
打噴嚏 護士 感冒
打噴嚏 農夫 過敏
頭痛 建築工人 腦震盪
頭痛 建築工人 感冒
打噴嚏 教師 感冒
頭痛 教師 腦震盪

現在又來了第七個病人,是一個打噴嚏的建築工人。請問他患上感冒的機率有多大?

我們把 X 從二元分類器擴展到三元分類器。公式完全一樣。

現在又來了第七個病人,是一個打噴嚏的建築工人。請問他患上感冒的機率有多大?

P(感冒|打噴嚏,建築工人) = P(打噴嚏,建築工人|感冒) *P(感冒) / 
P(打噴嚏,建築工人)

 

假定 ”打噴嚏|感冒” 和 ”建築工人|感冒” 這兩個特徵是 conditionally independent

P(打噴嚏,建築工人|感冒) *P(感冒) / P(打噴嚏,建築工人)

P(打噴嚏|感冒) x P(建築工人|感冒) x P(感冒) P(打噴嚏,建築工人)


P(感冒|打噴嚏,建築工人) = 2/3 * 1/3 * 3/6 / Z = 1

P(腦震盪|打噴嚏,建築工人) = 0/2 * 1/2 * 2/6 / Z = 0

P(過敏|打噴嚏,建築工人) = 1/1 * 0/1 * 1/6 / Z = 0

因此 P(感冒|打噴嚏,建築工人) = 1  and Z = 2/3*1/3*3/6+0+0 = 2/3*1/3*1/2

注意此時 Z ≠ P(打噴嚏,建築工人) ≠ P(打噴嚏)*P(建築工人)

因為 conditionally independent 只是假設,事實不成立!

但實務上,Naive Bayes works well.  Z = Σ_x {P(打噴嚏|X) x P(建築工人|X) x P(X)}

另一個實務上的問題是 P(Yi|Xi) 有些為 0 (如上例 P(建築工人|過敏)=0 and P(打噴嚏|腦震盪)=0),

會讓結果兩極化如上例: P(X|Y1, Y2) = {1, 0, 0}!!

如果取 log-likelihood 為負無窮大,則會造成計算上的問題。

Laplace (+1) smoothing addresses this:

NewImage

 (這個公式 copy here.  Xj 是 feature; Yk 是 class, 剛好和上面的定義相反,請注意)


再計算上面的例子:

P(感冒|打噴嚏,建築工人) = 3/4 * 2/4 * 3/6 / Z = 0.1875/Z = 54%

P(腦震盪|打噴嚏,建築工人) = 1/3 * 2/3 * 2/6 / Z = 0.0741/Z = 21%

P(過敏|打噴嚏,建築工人) = 2/2 * 1/2 * 1/6 / Z = 0.08333/Z = 24%

Z = 0.345  似乎比較合理。


Naive Bayes in summary:

1.  P( features | class) are conditionally independent!

2.  Likelihood with Laplace smoothing (Yk is class; Xj is feature) 

NewImage

3.  Prior:  P(Xj) 不用 Laplace smoothing, 因為不會是 0 (如果為 0 代表不需要這個 class)

4.  Z 是計算 Z = Σ Likelihood*Prior 得到。 


EX2. 帳號分類[3]: 區間 likelihood 估計

 根據某社區網站的抽樣統計,該站10000個帳號中有89%為真實帳號:設為C01

C0 = 0.89

C1 = 0.11

 

接下來,就要用統計資料判斷一個帳號的真實性。假定某一個帳號有以下三個特徵:

F1: 日誌數量/註冊天數

F2: 好友數量/註冊天數

F3: 是否使用真實頭像(真實頭像為1,非真實頭像為0)

F1 = 0.1

F2 = 0.2

F3 = 0

請問該帳號是真實帳號還是虛假帳號?

雖然上面這些值可以從統計資料得到,但是這裡有一個問題:F1和F2是連續變量,不適宜按照某個特定值計算機率。

一個技巧是將連續值變為離散值,計算區間的機率。比如將F1分解成[0, 0.05]、(0.05, 0.2)、[0.2, +∞]三個區間,然後計算每個區間的機率。在我們這個例子中,F1等於0.1,落在第二個區間,所以計算的時候,就使用第二個區間的發生機率。

根據統計資料,可得:(此處沒有統計資料)

P(F1|C0) = 0.5, P(F1|C1) = 0.1

P(F2|C0) = 0.7, P(F2|C1) = 0.2

P(F3|C0) = 0.2, P(F3|C1) = 0.9

因此,

P(F1|C0) P(F2|C0) P(F3|C0) P(C0)

= 0.5 x 0.7 x 0.2 x 0.89

= 0.0623

P(F1|C1) P(F2|C1) P(F3|C1) P(C1)

= 0.1 x 0.2 x 0.9 x 0.11

= 0.00198

可以看到,雖然這個用戶沒有使用真實頭像,但是他是真實帳號的機率,比虛假帳號高出30多倍,因此判斷這個帳號為真。

 

 

5. Naive Bayes With Parameter Estimation and Event Models

Gaussian naive Bayes [5]

NewImage

注意此時用 conditional probability density 替代 conditional probability.  Probability density 可以大於 1 (density 只要大於 0 and area under distribution sum to 1 就 OK)

對於每一個 class 以及麼一個 feature 都有一個對應的 Gaussian, K*M Gaussian.  乍看之下需要很多的計算資源。

解決之道是用 log-likelihood 取代 likelihood.  不用做 exponential, 同時用加法代替乘法。不過還是要算 (log σk).


EX3. 性別分類 [5]:訓練數據如下:

NewImage

已知某人身高6英呎、體重130磅,腳掌8英吋,請問該人是男是女?

根據樸素貝葉斯分類器,計算下面這個式子的值。

P(身高|性別) x P(體重|性別) x P(腳掌|性別) x P(性別)

這裡的困難在於,由於身高、體重、腳掌都是連續變量,不能採用離散變量的方法計算機率。而且由於樣本太少,所以也無法分成區間計算。怎麼辦?

這時,可以假設男性和女性的身高、體重、腳掌都是正態分佈,通過樣本計算出均值和方差,也就是得到正態分佈的密度函數。有了密度函數,就可以把值代入,算出某一點的密度函數的值。

比如,男性的身高是均值5.855、方差0.035的正態分佈。所以,男性的身高為6英呎的機率的相對值等於1.5789(大於1並沒有關係,因為這裡是密度函數的值,只用來反映各個值的相對可能性)。

有了這些數據以後,就可以計算性別的分類了。

NewImage


Prior: P(male) = P(female) = 0.5

Likelihood distribution and density:  

NewImage

NewImage 

Gaussian naive Bayes 要用 log-likelihood 取代 likelihood 節省計算資源!

不用作 exponential, 並且用加法取代乘法。

 

Multinomial naive Bayes 

前面的例子都是 multiple channels/features with conditional independence.   

每一個 channel/feature 可以是 binary, discrete, or continuous scalar.  但不同的 feature 之間都是 conditionally independent.

Multinomial naive Bayes 則是一個 channel/feature, 但這一個 feature 是一個 vector.  


Source ->  

class1 : [p11, p12, p13, .. p1m]     e.g. special dice 1 的 probability for {1, 2, 3, 4, 5, 6}, sum to 1

class2:  [p21, p22, ..     …p2m]     e.g. special dice 2 的 probability for {1, 2, 3, 4, 5 ,6}, sum to 1

classK: [pk1, pk2, ..      …pkm]     e.g. special dice K 的 probability for {1, 2, 3, 4, 5 ,6}, sum to 1

 

E.g. Given a histogram of a rolling dice K times, {1, 2, 3, 4, 5, 6} occurrences  =>  [67, 90, 2, 18, 0, 40] 

或者給一個文件包含 K words, vector [n1, n2, …, nm]   K=n1+n2+…+nm

where n1, n2, .., nm is occurrence number based on a m-word dictionary.

BTW, [p11, p12, p13, .., p1m] 可以想成是 rolling dice.  互相是 conditionally independent (at the same class).  

這和 naive Bayes 是一樣的。 

另外 “bag of words” imply position does not matter. 

NewImage

 

有兩種角度:

(a) Assuming the vector feature follows a multinomial distribution, use ML classifier or MAP classifier.

如果是 maximum likelihood classifier, 就是找哪一個 class 的 multinomial distribution 最有可能產生 [n1, n2, .., nm].

如果是 MAP classifier, 就是再乘上 P(class) or prior probability!  

 

(b) Maximum entropy classifier (MaxEnt) with prior distribution. 

vector x,  vector product with w1, w2, …, wk.  Then max  {pi(c1)exp(x.w1), pi(c2)exp(x.w2), …}

其實等價 multinomial classification? 

 

問題:

1. 如何產生 [p11, p12, .., p1m], … [pk1, pk2, .., pkm]?  或是如何 training w1, w2, …wk?

2. 如何做 inference?

 

先回答如何做 inference.

NewImage

在 prior P(Ck) and log likelihood log Pki 已知情況下,計算 posterior probability 並取 maximum value 的 Ck.

 

上面的公式其實就是 cross-entropy loss.  Cross-entropy loss 最小的 Ck 就是 inference 的結果。

另一個 hint 是用 minimise cross-entropy loss 做 training using labeled vector x. 

 

如何產生 pki, 或是 wk = log pki?  

(a) 一是用 labeled vectors {x} 對 minimise cross-entropy loss 做 training.

(b) 另一個做法是把所有同一個 class 的 vector {x} 加在一起,normalise (with Laplace smoothing) 得到 pki.

NewImage

NewImage

(b) 是一個平均的算法。如果資料多,不失為一個好方法。 

 

Multinomial naive Bayes 和原來的 naive Bayes 其實大同小異。可以把原來的 naive Bayes with multiple features 看成

class1 : [p11, p12, p13, .. p1m]     e.g. class1 feature probability, NOT sum to 1 

class2:  [p21, p22, ..     …p2m]     e.g. class2 feature probability, NOT sum to 1

classK: [pk1, pk2, ..      …pkm]     e.g. class3 feature probability, NOT sum to 1

No multiple occurrence in original naive Bayes

Conditionally independence 則是一樣。 

 

EX4. 文件分類 [5]:

NewImage 

 

(K, N) (class, feature) 貝葉斯分類器

N features and K classes, given P(Ym|Xk), 求 argmax P(Xk|Ym) 

NewImage 

 

 

NewImage

Maximal Entropy Principle Statistics Mechanics

Reference:

[1] UCI, lecture notes, “Maxwell-Boltzmann, Fermi, and Bose Statistics

[2] J. Chou, Harvard BCMP201 lecture notes, “Entropy

[3] K. Hock, Liverpool PHYS393 notes, “Statistical Physics

[4] C. Yu, UCI PHY115A notes, “Maxwell-Boltzmann, Fermi, and Bose Statistics

[5] Wiki, “Partition function

[6] Anonymous, “Partition function (statistical mechanics)”   Excellent article

 

Maximum entropy principle = Minimum bias principle

所有滿足 constraints (e.g. energy constraint) 的 micro-state 都是 equally probable.

 

假設一個容積為V的盒子中有N個相同粒子的“氣體”。“氣體”是粒子不會相互影響。

=> 這點非常重要!粒子不會相互影響,代表我們可以 label 每一個粒子。也就是每個粒子是 “distinguishable”.

=> 以上說法不對。如果完全沒有相互作用,就無法達到熱平衡!應該是粒子有 weak interaction [3]. 

這是經典統計力學的前提和基礎。量子統計力學每一個粒子都是一個 “波函數”。當粒子處於非常接近,彼此的波函數疊合,有很強的 interaction,量子效應會讓 ”波函數“ 互相交換。粒子變為 “indistinguishable”.

(a) 非常接近:  粒子的平均距離接近 De Broglie wavelength, 強迫粒子交換作用。例子:He or 其他原子在極低溫所表現的超導現象;或是低溫比熱 (low temperature? high temperature phonon?);或是黑體輻射 (high temp?)

(b) ”波函數“ 交換作用:交換作用有兩種:對稱和反對稱:symmetrical (Boson) and anti-symmetrical (Fermion).  不論是 symmetrical or anti-symmetrical 都是 “indistinguishiable”

————————————————————————————

假設我們知道這種氣體中的單個粒子狀態 (想像一個骰子有六個狀態) 。我們想知道什麼是可能的整個系統的狀態。有 3 種可能的情況?哪一個是合適的,取決於我們是用 Maxwell-Boltzmann,Bose-Einstein, or Fermi-Dirac 統計。

我們來考慮一個非常簡單的情況,其中我們在盒子中有 2 個粒子,盒子有 2 個粒子態 (1 and 2) 對應單一粒子的狀態。我們可以有多少種不同的方式將這些粒子放入兩個狀態?

 

經典統計力學 follows Maxwell-Boltzmann distribution.  

This is sometimes called the classical case.

In this case the particles are distinguishable so let’s label them A and B.

Let’s call the 2 single particle states 1 and 2.

For Maxwell–Boltzmann statistics any number of particles can be in any state. So let’s enumerate the states of the system:

NewImage

We get a total of 4 states of the system as a whole. Half of the states have the particles bunched in the same state and half have them in separate states.

 

量子統計力學 follows Bose–Einstein Statistics (for Boson with integral spin):

This is a quantum mechanical case. This means that the particles are indistinguishable. Both particles are labelled A. Recall that bosons have integer spin: 0, 1, 2, etc. For Bose statistics any number of particles can be in one state. So let’s again enumerate the states of the system:

NewImage

We get a total of 3 states of the system as a whole. 2/3 of the states have the particles bunched in the same state and 1/3 of the states have them in separate states.

 

量子統計力學 follows Fermi-Dirac Statistics (for Fermion with half-integral spin):

This is another quantum mechanical case. Again the particles are indistinguishable. Both particles are labelled A. Recall that fermions have half–integer spin: 1/2, 3/2, etc. According to the Pauli exclusion principle, no more than one particle can be in any one single particle state. So let’s again enumerate the states of the system:

NewImage

We get a total of 1 state of the system as a whole. None of the states have the particles bunched up; the Pauli exclusion principle forbids that. 100% of the states have the particles in separate states.


經典統計力學: Maximum Entropy [2] => Boltzmann Distribution [3]

NewImage

 

Maximum Entropy = Minimum Bias

NewImage 

NewImage 

NewImage

NewImage

 

NewImage

ln Ω = NH  or  H = (ln Ω / N) 是一個很有趣的關係。

可以從 Ω (擲骰子 N 次的 possible outcomes) 出發,定義 (1) Shannon entropy 以及 (2) statistics physics entropy. 

 

Shannon information (entropy) 就是 log(possible outcome) 的平均,也就是 log(possible outcome)/N  (log base on 2)

舉例而言:擲 N 個硬幣,正面的機率是 p, possible outcomes = C(N, Np),  H ~ [log C(N, Np)] / N

* N = 100, Np = 0 or 100, H ~ log[C(100, 0)]/100 = 0 ~ 0-bit

* N=100, Np=10 or 90, H ~ log[C(100,10)]/100=0.44 ~ -0.9*log(0.9)-0.1*log(0.1)= 0.47-bit

* N = 100, Np = 50,  H ~ log[C(100, 50)]/100=96.34/100=0.96 ~ 1-bit  

* 另一個觀察是 N 個粒子的 total entropy proportional to particle number N.  因為 log(possible outcome) ~ N.

N 可以是空間上的粒子數目。或是時間上的 symbol 數目 (通訊 channel). 

 

Statistics physics entropy 就是 S = kb* ln(possible outcome) = kb * lnΩ = kb * N * H

主要的差異是 (1) log base on e; (2) Scale by kb (Boltzmann constant), 同時單位換成 Joule/Kelvin

 

Maximum Entropy => Boltzmann Distribution

[3] 的推導出 Boltzmann distribution 非常給力。[3] 的 t 相當於 [2] 的 Ω.  nj = N * pj

NewImage

NewImage

因為 ln t = ln Ω ~ S.  在熱平衡是 maximum entropy, 所以微分為 0.

 

可以加上其他 constraints 的微分為 0,得到 Boltzmann distribution 如下:

 NewImage

 NewImage

 NewImage

(40) 就是有名的 Boltzmann distribution!

 

NewImage

and 

NewImage

(48) links statistics mechanics and thermodynamics.

NewImage 

Boltzmann distribution 如下:(40) => p(εj) = nj / N = exp(-εj / kb*T) / Z

NewImage 

另一種表示法 [3] 是把 discrete energy level 變為 continuous energy band:

 NewImage

 

兩個 energy level distribution 例子:

1. Quantum harmonic oscillator (uniform energy level distribution)

NewImage

NewImage 

 

 

兩個粒子交互作用

如果兩個粒子物理上完全沒有相互作用。波函數就是兩個機率波相乘。

數學上就是兩個獨立的機率波。顯然這不是我們有興趣的例子。

NewImage 

再來考慮“弱交互作用”的情況。

NewImage

 

NewImage 

如果 ϵ 很小,兩個粒子看到的能階是分別能階的和。

假設兩個粒子都是 harmonic oscillator 有弱交互作用。

兩個粒子(或多個粒子)的能階和仍是 harmonic oscillator 的能階 (uniform energy level).

舉四個粒子為例:如果 total energy, U = 4ε constraint.   一共有 25 種 microstates.

NewImage

其中第一類分佈圖示如下:

NewImage 

根據上表的五類分佈,假設每一個 microstate 有同樣的機率。會得到以下的分佈。

NewImage

看起來像 exponential distribution, 也就是 Boltzmann distribution with uniform energy level.

粒子愈多,就會愈接近 exponential distribution. 

Boltzmann distribution:(40) => p(εj) = nj / N = exp(-εj / kb*T) / Z

nj = N/Z * exp(-j*ε)  where N = 4  and  Z = N/no = 4/1.71 = 2.34

NewImage 

 

再來考慮“強交互作用”的情況

“Indistinguishable” 粒子

NewImage

NewImage

NewImage

NewImage

 

Fermion 的一個特性是 Pauli exclusion principle (one particle at one state) 因為:

NewImage

 

gi 是 εi 的 degenerate number.  ni ≤ gi or the maximum value of ni is gi.

NewImage

By applying Maximum Entropy Principle (MEP) again!

NewImage

 

NewImage

NewImage 

NewImage 

如果 ni << gi  or ni / gi << 1  也就是 “low density” or “dilute” system, Fermi-Dirac distribution 趨近 Boltzmann distribution.

 NewImage

 

一般情況下(Fermi Energy or Chemical Potential): 

NewImage 

NewImage 

在極低溫時,比 Fermi energy 低的能階都塞滿 fermions, 比 Fermi energy 高的能階都是空的。

Fermi energy 基本上和 Boltzmann distribution 的 partition function Z 一樣。

不論 Boltzmann distribution 的 partition function Z, 或是 Fermi-Dirac distribution 的 Fermi energy, μ, 一樣。

都是非常有用的狠角色。從 Fermi energy 可以再定義 Fermi temperature, Tf.

 

NewImage

 NewImage

 

Boson (No limit on number of Boson at a given state)

 

NewImage 

NewImage 

NewImage 

By applying Maximum Entropy Principle (MEP) again!

 NewImage

NewImage

 

Maximum Entropy Principle 框架總結 

 

Maximum entropy principle = Minimum bias principle

所有滿足 constraints (e.g. energy constraint) 的 micro-states of N particles has equal probability

在 equal probability 前提下: Let  Ω is the number of micro-state of N particles

maximum entropy principle 就變成 maximum micro-state principle.  (如果有 micro-state meets the constraints and not counted => not equal probability!)     =>   dΩ = 0   (with respect to nj)

一個常用的 trick 是定義:

S = ln Ω  where S is entropy and Ω is the number of microstate

dS = dΩ / Ω = 0

所以

Maximum entropy: dS = 0  (given the following two differential constraints)

再加上兩個 constraints, 就完成了 MEP 的基本框架。

NewImage

 

接下來是 Ω 的差異: , indistinguishable particles (symmetry and anti-symmetry).

Boltzmann distribution (distinguishable N partciles):  Ω =

NewImage

Bose-Einstein distribution (indistinguishable N bosons): Ω = 

NewImage

Fermi-Dirac distribution ((indistinguishable N fermiions): Ω = 

NewImage

或是其他例如 three-level N particle Boltzmann distribution: Ω =

N! / (n0! n1! n2!)

 

是否能在 Ω 未知的情況下得到更多的信息? Yes

 

Start From Ω Then Get ni [3]

dS = d ln Ω = Σ ln{f(ni)} dni = 0   再加上面兩個 constraints (Lagrange multiplier)

ln f(ni) – α – β εi = 0    =>   f(ni) = exp(α + β εi)  =>  ni = g( exp(α+βεi) ) !!!

 

ni is the key!!  

Boltzmann distribution:  ni = N/ζ  exp(βεi)    β = -1/kT       Σ ni = N  =>   ζ = Σ exp(-εi/kT)  and α = – ln ζ   

Fermi distribution: ni = gi / ( exp(-α-βεi) + 1)    β = -1/kT     α = εf / kT    ni = gi / {exp((εi – εf)/kT)+1}

Bose distribution:  ni = gi / ( exp(-α-βεi) – 1)    β = -1/kT      ni = gi / {exp((εi – εf)/kT)-1}

 

Maximum entropy principle => mostly exponential family distribution

但不是所有 MEP 都是 exponential family.   Boltzmann, Bose, and Fermi are all MEP distribution!  But

Boltzmann distribution is q-exponential distribution (or softmax function)

Q: Bose and Fermi distribution are NOT exponential distribution? 

Q: Partition function Z can be used for Fermi and Bose distribution? 

 

Equal Probability Principle 

Start From Partition Function Z Then Get ni [4] and [6]

我們從另一個角度。就是從 partition function Z 出發。從 Z 再得到 ni.

這裡的 partition function Z 和之前不同 !!  是 sum over 所有的 micro-states R.

固定 ER, R 有很多的 micro-states.  Sum over R 的所有 micro-states.

下面 equation (4) 是神來之筆。Why is true?

(a) Equal probability principle,  P_R = exp(-β E_R) / Z for every microstate.

(b) The exponential comes from ?  Exponential family => from Maximum Entropy Principle!

 

 

NewImage 

公式 (5) 可以參考上面 4 個粒子的分佈計算。ns 代表不同 (energy) state 的平均粒子數, 就是上面的 ni.

最主要的結論就是 (7):   ni = -(d lnZ / dεi )/β   和之前 S = ln Ω  and  d lnΩ / dni = 0 相似。

一個問題是 Z 和 Ω 是否有直接關係?

Equation (17)  =>  Z = Σ (Ω * exp(-β (n1ε1+…)))  over n1, n2, …

ln Σ 是最大的問題。重點如何把 Σ 變成 π.  ln π = Σ ln.

 

NewImage 

Maxwell-Boltzmann distribution

Equation (12) 和上面的結果一致。

NewImage

NewImage

 

Bose-Einstein Distribution

NewImage

 NewImage

NewImage 

NewImage 

NewImage

 

Fermi-Dirac Distribution

NewImage 

NewImage

NewImage

NewImage

 

Grand Partition Function 

From [4]:

NewImage

NewImage

Equation (31) 只用於 Bose-Einstein distribution.  (31) 之前則是 general correct.

 

From [5]

NewImage

From [6]

NewImage

 

對比 Statistics Maximum Entropy / Exponential Family

ni / N = pi    =>  Σ pi = 1  

and Σ pi εi = U/N  or  E(ε) = U/N = μ   where ε is a random variable of values {εi}. 

S = -Σ pi ln pi   dS = -Σ ln pi – N

or exponential family.  Z partition function?

NewImage 

NewImage 

T(x) = [n1/N, n2/N, n3/N, …] = [x1, x2, x3, …],  η = -βN*[ε1, ε2, ε3, …]

A(η) = ln Σ exp(-β*(n1*ε1 + n2*ε2 + …))   ~  ln Z  (log – partition function)

 NewImage

這和 ni 平均值一樣,如下。

NewImage

 NewImage