最大熵學習法 (Maximum Entropy) 在機器翻譯上的用途

機率統計

教學錄影

數學符號

數學基礎

排列組合

機率統計簡介

機率

機率公理

隨機變數

連續測度

單一分布

條件機率

聯合分布

貝氏定理

動差生成函數

特徵函數

機率法則匯總

離散分布

二項分布

多項分布

負二項分布

幾何分布

超幾何分布

布瓦松分布

連續分布

均勻分布

常態分布

Gamma 分布

指數分布

卡方分布

柯西分布

Weibull 分布

T 分布

F 分布

Beta 分布

多維分布

統計

抽樣

敘述統計

推論統計

中央極限定理

估計方法

單組樣本估計

兩組樣本估計

檢定方法

單組樣本檢定

兩組樣本檢定

平均値的推論

變異數的推論

無母數推論

迴歸分析

變異數分析

實驗設計

因子實驗

品質管制

時間序列

數據分類

統計定理匯總

統計情況分類

計算統計

蒙地卡羅法

最大似然法則

假說與學習

EM 算法

簡單貝氏分類

貝氏網路

隨機過程

馬可夫鏈

蒙地卡羅馬可夫

資源

範例

投影片

教學錄影

練習題

考題解答

訊息

相關網站

參考文獻

最新修改

簡體版

English

簡介

最大熵法則 (Maximum Entropy) 在自然語言與機器翻譯領域上相當有用,舉例而言,在統計式機器翻譯領域,最大熵法則就常被用在雙語語句的詞彙對齊問題上,並且有許多人以該法則實作出自動對齊軟體,而且效果不錯。

舉例而言,英文詞彙 fly 翻譯成中文時可能有『飛行、搭機、蒼蠅』等三種可能譯文,假如沒有其他種譯法,那我們就可以假設

P(飛行 | fly) + (P(搭機 | fly) + P(蒼蠅 | fly) = 1

但是,滿足這個條件的機率分布有很多,像是平均分布 (各 1/3),或者極端分布 P(飛行 | fly) = 1, 其餘為 0 等等,這些各式各樣的可能分布稱為一個機率模型 (Model)。

但是,什麼樣的分布最好呢?通常,在沒有任何進一步訊息的情況下,我們會傾向於使用平均分布。但是,如果有進一步的訊息,例如 加上限制條件 P(飛行 | fly) + (P(搭機 | fly) = 4/5。那麼,我們會傾向於使用哪種分布呢?

在資訊理論當中,當一個詞彙 w 的出現機率為 P(w) 時,其資訊量定義為如下公式。

(1)
\begin{equation} h(w) = - p_w log(p_w) \end{equation}

對於一個語言的所有詞彙集合 (詞集) 而言,整個詞集平均的詞彙編碼長度,稱為該詞集的『熵』或亂度,定義為如下公式。

(2)
\begin{align} H(W) = - \sum_{w \in W} p_w log(p_w) \end{align}

在數學符號的使用上,我們通常使用大寫代表整個隨機變數 (像是 W) 或整體函數 (像是 H),小寫代表一個案例 (像是 w) 或案例的函數 (像是 h)。

從觀察樣本到機率模型

針對英漢機器翻譯 (Machine Translation) 領域而言,假如訓練語料庫為一個很長的 (英文, 中文) 配對 $(x_1, y_1) (x_2, y_2) ... (x_N, y_N)$ 的雙語對齊語料庫。那麼,我們就可以統計配對 (x,y) 的出現機率 $\tilde{p}(x,y)$,其算法如下。

(3)
\begin{align} \tilde{p}(x,y) = \frac{n(x, y)}{N} \end{align}

其中的 n(x,y) 代表 (x,y) 配對出現的次數。

假如我們現在加入一個限制函數 f(x,y) 代表雙連詞 (bigram) 模型,如果 y 緊跟在 x 之後出現則為 1 ,否則為 0,其函數定義如下。

f(x,y) = 1 if y follow x
         0 otherwise

那麼,f 函數在 P(X,Y) 分布下的期望值將可由下列公式定義之。

(4)
\begin{align} \tilde{p}(f) \equiv \sum_{x,y} \tilde{p}(x,y) f(x,y) \end{align}

像 f 這樣的函數稱為特徵函數 (feature function,簡稱 feature)。

當我們取得一些統計上較為堅實的樣本,像是詞彙的出現率統計 $\tlide{P}(X)$ 時,我們可以假設真實的分布也應該與樣本一致,於是可以用下列算式取代 4

(5)
\begin{align} p(f) \equiv \sum_{x,y} \tilde{p}(x) p(y|x) f(x,y) \end{align}
(6)
\begin{align} p(f) \equiv \tilde{p}(f) \end{align}

條件式 6 稱為一種限制 (Constraint),這種限制要求我們只考慮符合這個條件的機率模型。於是我們可以將 4, [eref eq5]], 6 合併起來,形成下列等式。

(7)
\begin{align} \sum_{x,y} \tilde{p}(x,y) f(x,y) = \sum_{x,y} \tilde{p}(x) p(y|x) f(x,y) \end{align}

也就是我們要求找出的機率模型必須與訓練樣本一致,此時我們可以將

$\tlide{P}(x,y)$ 時 (像是雙語對齊語料庫),

我們的目標是希望建立一個統計模型,讓這個模型產生整個機率分布 P(X,Y) 的機會最大,

當沒有進一步的訊息時,我們傾向於使用平均分布,也就是讓

熵的距離公式

(8)
\begin{equation} d(X,Y) = H(X,Y) - I(X;Y) = H(X|Y) + H(Y|X) = 2 H(X,Y) - H(X) - H(Y) \end{equation}

目標

最佳化目標:找出 p 以最大化下列算式

(9)
\begin{eqnarray} && argmax \quad { d(X,Y) } \\ & \rightarrow & argmax \quad { H(X|Y) + H(Y|X)} \\ & \rightarrow & argmax \quad { 2 H(X,Y) - H(X) - H(Y) } \end{eqnarray}

最大距離原則 = 最大條件熵原則 = 最大聯合熵原則 (保持系統的最大亂度)

參考文獻

  1. Maximum Entropy Modeling — http://homepages.inf.ed.ac.uk/lzhang10/maxent.html

軟體程式

  1. YASMET — training of conditional maximum entropy models, Yet Another Small MaxEnt Toolkit. Believe it or not, this implementation is written in only 132 lines of C++ code and still has feature selection and gaussian smoothing. You need GCC 2.9x to compile the source.
  2. maxent.sf.net — Great java maxent implementation with GIS training algorithm. Part of OpenNlp project.
  3. Amis — A maximum entropy estimator for feature forests. A maximum entropy estimator with GIS, IIS and L-BFGS algorithms.
  4. maxent — Another Maximum Entropy Modeling Package with Ruby binding, GIS, Gaussian Prior smoothing and XML data format.
  5. Predictive Modeling Toolkit
  6. Robert Malouf's [Maximum Entropy Parameter Estimation software], now available as [Toolkit for Advanced Discriminative Modeling on sourceforge.net], has GIS, IIS, L-BFGS and Gradient Descent training methods and parallel computation ability through PETSc. You may want to read his paper first.
  7. MEGA Model Optimization Package — A recently appeared ME implementation by Hal Daumé III. The software features CG and LM-BFGS Optimization and is written in OCaml. Although I no longer use OCaml, I'd say that's a great language, and is worth learning.
  8. Text Modeller — A python implementation of a joint Maximum Entropy model (aka. Whole Sentence Language Model) with sampling based training. Now seems to be part of scipy.
  9. Stanford Classifer is another open source implementation of Maximum Entropy Model in java, suitable for NLP tagging and parsing tasks.
  10. NLTK includes a maxent classifier written entirely in Python. IIS and GIS training methods available. Suitable for text categorization and related NLP tasks.
  11. Here is another small maxent package in C++ with a BSD-like license, written by Dekang Lin.
  12. SharpEntropy, a C# port of the java maxent package (http://maxent.sf.net) mentioned above.
  13. Maxent software for species habitat modeling by Robert E. Schapire et al. Registration needed for downloading.
  14. Maxent implementation in C++ with Python binding, GIS, L-BFGS and Gaussian Prior Smoothing

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License