基于信息熵的POMDP模型觀測

鐘可立 王小捷

中圖分類號：TN91； TN919.8 文獻標志碼：A 文章編號：1009-6868 （2015） 05-0050-006

摘要：部分可觀測馬爾可夫決策過程（POMDP）廣泛應用于建模決策任務。模型中的觀測矩陣主要用來建模環境的不確定性，通常很難從訓練數據中直接獲取，需要引入額外的信息進行估計。通過引入信息熵來修正模型中的觀測矩陣，修正后的觀測矩陣更能反映環境的不確定性。模擬環境下的實驗表明，引入信息熵進行修正估計的觀測矩陣有效提高了POMDP模型的性能，而在基于POMDP模型的對話系統中，修正的估計提高了系統的決策準確度。

關鍵詞：部分可觀測馬爾可夫決策過程；不確定性；意圖識別；觀測矩陣；信息熵

Abstract： Partially Observable Markov Decision Process （POMDP） is a decision model used extensively for decision tasks. The observation matrix of the model is a channel that reflects the uncertainty of surroundings， which is hard to do directly from the corpus. Extra information needs to be introduced for estimation of the observation matrix and better reflection of surroundings. The concept of information entropy is introduced to modify the observation matrix in the model by which the modified observation matrix can reflect the uncertainty of the situation more precisely. Simulated experiment and real situation show that introducing information entropy to modify the observation matrix improves performance of the POMDP model together with the decision-making accuracy in a dialogue system based on POMDP.

Key words： partially observable markov decision process； uncertainty； intention identification； observation matrix； information entropy

人機對話是語言信息處理中的一個重要應用任務，對話管理是對話系統中的核心組成部分，決定了對話系統的質量，為此出現了很多關于對話管理模型的研究。

已有的對話管理技術[1]主要包括：基于自動機的方法[2-3]，基于框架的方法[4-5]，基于信息狀態的方法[6]，基于概率模型的方法[7-8]。基于自動機的方法雖然易于設計，但是不靈活，不自然，難以應付復雜的任務。基于框架的方法實現的復雜度較低，但是對話比較機械，人機交互的自然度較低。基于信息狀態的方法比較靈活，能豐富的表達對話的狀態，把對話過程看作是一列規則的變化，但是需要人工的定義規則與策略。概率方法主要基于馬爾可夫決策過程（MDP）與部分可觀測馬爾可夫決策過程（POMDP）模型。與前3種方法相比，基于POMDP的方法不需要人工定義策略，而是通過數據學習策略，POMDP將客觀世界的動態特性用狀態轉移來描述，在狀態不完全可觀測的情況下，系統通過與環境交互，進行決策，管理對話過程。

雖然基于POMDP模型的對話管理具有更大的靈活性，可用于狀態不完全可觀測的情況，但是模型需要統計狀態轉移矩陣，在訓練過程比較依賴于數據；需要定義回報函數，目前沒有很好的估計方法；需要估計觀測概率矩陣，一般情況下是很難從數據中直接估計。這些問題會給基于POMDP模型的對話管理帶來困難。

基于POMDP模型的對話管理是根據當前的信念狀態分布來選擇動作，因此信念狀態的估計會直接影響到系統決策性能，而觀測函數的估計也會直接影響到信念狀態的估計。在對話系統中，POMDP模型的觀測函數一般是建模從用戶對話意圖到系統狀態的映射，但是，用戶對話意圖本身并不是直接可獲得的，它是由用戶的語言輸入來體現的。一方面，用戶對話意圖十分豐富，且同一對話意圖可以用幾乎是無限種不同的語言輸入來表現，另一方面，對一個確定的語言輸入的意圖識別也會存在不確定性，更不用說語言輸入本身的識別也可能存在不確定性。因此，很難直接從訓練數據直接獲得，而需要另外的技術來進行估計。對觀測函數專門研究的文獻不多。文獻[9]簡單地把語音識別錯誤率引入到觀測函數的估計中，主要建模語音輸入識別錯誤的影響，但并不考慮對識別結果進行用戶意圖識別時的錯誤。這種估計方法也沒有把訓練數據的信息考慮到里面，性能較差。文獻[10]結合連續信息與離散信息并應用到貝葉斯網路里面，觀測的集合大小有4種，即觀測是離散的，連續信息指的是觀測的概率，但需要相關閾值確定離散信息，閾值的確定給計算POMDP的回報值帶來困難。文獻[7]對觀測函數進行擴展，在原來的基礎上加入置信度（Confidence）分數，用置信度來衡量該觀測包含的信息量和對策略規劃的重要程度，但是此方法的參數h很難估計，由于是直接引入置信度，因此很難在現有的工具訓練模型。

觀測函數是描述內部狀態與外部環境之間的聯系。對話管理的一個關鍵性的問題是部分可觀測帶來的不確定性[11-12]，而信息的不確性可以使用信息熵來衡量，因此為了使觀測函數更能反映環境的不確定信息和其所包含的信息量，本文引入信息熵來修正觀測概率。

1 POMDP模型及觀測函數

的估計

一個POMDP模型可以用一個六元組[]來描述，其含義如下：

*[S]：系統的狀態集合

*[A]：系統的動作集合

*[T（s′，a，s）]：系統的狀態轉移函數，描述的是當系統在狀態s下執行動作a可能轉移到[s′]的概率

*[R（s，a）]：系統的報酬函數，描述的是當在狀態s下執行動作a時，系統獲得的立即回報值

*[Z]：系統的觀測集合

*[O（s′，a，o）]：系統的觀測函數，其中[o∈Z]

POMDP問題結構如圖1所示。每個時刻，系統會處于一個隱狀態s，系統會根據當前的信念分布b，選擇一個動作a，得到一個立即回報r，然后轉移到下一個隱狀態[s′]，[s′]依賴于s、a。此時系統會得到新的觀測[o′]，[o′]依賴于[s′]、a，然后根據動作a，新的觀測[o′]，更新當前的信念分布，繼續選擇動作。其中關于[o′]的觀測概率，可用于確定轉移到[s′]狀態的置信度。

在POMDP中，觀測函數一般情況下是很難直接從數據中估計得到，需要額外的信息去加強對觀測函數的估計，反映環境的不確定性。

文獻[9]在研究基于語音輸入的人機對話系統建模時，把語音識別錯誤率引入到觀測矩陣的估計中，而語音識別結果到意圖的映射是一對一的。雖然這里是針對語言識別錯誤，假設輸入為文本，不存在語音識別錯誤時，這里的語音識別錯誤也可以看成是意圖識別的錯誤，因此，相同的模型可以建模文本輸入時存在意圖識別錯誤的情形。因此，后文中我們會替換使用語音識別和意圖識別，其反映的都是類似的觀測中的不確定性，可以類似進行建模。設[perr]為語音識別錯誤率，如果用戶的意圖與系統觀測到的用戶意圖或行為一致的話，認為觀測概率為1-[perr]；否則觀測概率[perr|Au|-1]，其中[Au]為觀測集合的個數。這種方法把語音識別的整體錯誤率信息引入到觀測函數里面，但是卻沒有反映當前對話的信息。

文獻[7]和文獻[13]對文獻[9]觀測函數進行擴展，在原來的基礎上加入置信度分數，反映當前對話的信息。在每個觀測概率前乘以相應的觀測置信度分數。這種方法把觀測o分成兩部分，一部分是離散的觀測值，代表語音識別或意圖識別的假設；一部分是連續分數，衡量該假設的置信度。由于直接在觀測函數里面加入連續性的分數，目前訓練工具基本都是要求觀測部分是離散的，因此無法在現有的工具上直接訓練。

2 改進的觀測函數估計方法

在文獻[14]中，每一個語音輸入只有一個識別結果，即只使用識別率最高或分數最高的結果，相當于使用1-best識別結果。

但是，語音識別通常并不完美，采用1-best顯然沒有采用n-Best（n>1）得到的信息豐富。直接利用1-best結果作為觀測已經一定程度損失了語音信息。例如：假設一個語音輸入的標準識別結果是“我要購買從北京到廣州的機票”，其1-best結果為“我要購買東京到廣州的機票”。如果還有2rd-best的結果“我要購買從北京到廣西的機票”以及3rd-best的結果“我要購買從北京到杭州的機票”，甚至N-best的結果...其中N-best列表中的第一個地點很有可能出現“北京”的次數多于其他的地點，采用語音識別的N-best結果可以使觀測的結果更能反映真實的狀態，使信念分布提供更具體的信息。

本文關注輸入為文本的人機對話系統管理。如上所述，對于文本輸入的對話，語言輸入假設是正確的，那么需要考慮的是意圖識別的錯誤。在采用POMDP建模時，需要基于文本輸入估計對話意圖作為真正的觀測。一般，對每輪對話中用戶的輸入進行一次意圖識別，對于一段語言輸入判斷其言語意圖，可以用分類器（意圖識別器）來進行識別，本文在實驗中會選擇采用兩種不同的意圖分類器進行考查，無論哪種分類器，均可以得到N-best識別結果。隨后的問題就是，如何有效利用這些N-best信息。

本文提出利用N-best信息，計算其信息熵，引入到觀測函數中，用于修正觀測矩陣的值，使觀測函數包含環境不確定性的信息，更加客觀的描述環境。

為每個觀測得到的是一個N-best列表（由意圖識別器獲得），N-best列表記錄的最可能的N個用戶意圖假設，N-best列表中同時還記錄了意圖識別器為每個用戶意圖分配的概率，例如：

[o=[

本節基于對話系統對修正后的觀測函數對POMDP模型的性能進行定量分析。實驗分別在模擬和實際的對話系統中進行。

模擬系統實驗是在給定一組策略下，經過多輪決策，估計總的期望回報。使用基于SARSOP 算法的Approximate POMDP Planning工具包，模擬決策次數是1 000次。

真實系統實驗是在一個以機器人教學為目的的對話系統下進行的，通過接收實際的人類語言輸入，POMDP模型采用修正后的觀測函數（其他參數不變）進行決策，產生相應的應對句子。

實驗采用的對話系統結構如圖2所示，UserState為用戶的狀態即意圖，Obs為系統的觀測部分，由于需要計算Obs的信息熵，因此該觀測值不是1-best，而是N-best，Action是對話系統的動作，Reward是系統得到的長期累計回報值，并不是當前得到的立即回報值。

系統根據用戶的意圖來選擇動作，達到學習，回答，詢問的結果。在該系統的設計中，使用156個對話作為訓練語料，建模一個基于POMDP的對話系統，需要完成7部分工作。

（1）狀態

在POMDP模型框架之上構建的對話系統，模型中的信念狀態包含當前狀態的信息和歷史信息，允許系統不直接知道確定的狀態，根據信念狀態分布做出決策，所以可以把用戶的意圖直接作為狀態變量。用戶意圖總共分4種類型：對話開始/結束狀態；教學意圖，教學形狀、類別、顏色、名稱、部位；查詢意圖，查詢名稱、顏色、形狀、部位；其他意圖。

（2）動作

動作是對話系統根據當前信念狀態分布信息采取的操作，用于與用戶交互。對話系統的動作可以分為5類：對話開始/結束；回答，回答形狀、類別、顏色、名稱、部位；提問，提問名稱、顏色、形狀、部位；學習，學習形狀、類別、顏色、名稱、部位；其他。

（3）觀測

這個系統的觀測是用戶說話意圖的表現，主要是用于描述在系統的角度下用戶意圖的表現，所以把觀測狀態集合定義為和狀態集合一樣。

（4）狀態轉移函數

系統是根據當前的信念狀態得出動作，從而影響用戶的下一步的狀態，由于把用戶狀態定義為用戶意圖，即會影響用戶意圖。不同的動作選擇會對用戶意圖的改變有著不同的影響。狀態轉移函數用于記錄當前意圖下，執行動作后，下一個出現某意圖的可能性。

（5）觀察函數

一般情況下觀測函數是很難直接從訓練語料直接統計出來，也是POMDP模型最復雜，最有挑戰性的部分。不同的狀態、動作會導致不同的觀察出現。觀測函數的性能也是直接影響信念狀態的更新，從而影響對話系統的決策。為了方便計算，該系統認為系統的觀測只跟當前的意圖相關，與前一個動作無關，即[p（o|s′u，a）=p（o|s′u）]。

（6）回報函數

回報函數是用于描述在當前意圖的情況下執行某動作后得到的回報。回報函數的定義雖然比較簡單，但是卻不能很好的定義回報函數。目前一般都是按照系統的實際用途人工定義回報函數。系統根據用戶意圖采取正確的動作就可以得到正的回報，執行錯誤的動作就會得到負的回報。比如，如果當前用戶意圖是Teach類別的話，系統采取Rlearn動作，就會得到+200的回報，采取Rquery類別的動作就會得到+150回報，否則會得到-200回報；如果當前意圖是End，用戶采取的動作是Rend，代表對話結束，可以給出+1000的回報。

（7）Belief初始值

如果沒有對話的開始狀態，一般情況下是每個狀態的Belief值定義為一樣，效果比較好。

根據這7部分的定義，搭建一個基于POMDP模型的對話系統，這個模型總共有12種狀態，9種動作，12種觀測，折扣因子為0.9，因為引入開始/結束狀態，初始狀態的信念值只有Start的值為1，其他狀態的值為0。

為了加快POMDP模型的速度，訓練時沒有采用精確求解算法，而是采用SARSOP近似算法。

為了更全面的考察上文提出的修正觀測概率方法在基于POMDP的對話系統的效果，設計了兩個實驗。

3.2 模擬環境實驗

意圖識別模塊使用條件隨機場（CRF）和支持向量機（SVM）兩種分類器來估計觀測概率，同時為了體現加入修正方法后，系統的健壯性，在估計狀態轉移時同時使用4種不同的平滑方法（不使用平滑（Origin），最大熵，最大使然，Good-turing）估計狀態轉移概率。模擬次數是1 000次。

表1的意圖識別分類器都是使用CRF，而表1的第二列實驗的POMDP模型中的觀測概率是沒有經過修正的，第三列的觀測概率是經過修正的。從表1可以看出，經過修正后的系統回報值比沒有經過修正的系統回報值要大，最高提高了2.5%，最低提高了2%。

表2的意圖識別分類器都是使用SVM，而第二列實驗的POMDP模型中的觀測概率是沒有經過修正的，第三列的觀測概率是經過修正的。從表2可以看出，經過修正后的系統回報值比沒有經過修正的系統回報值要大，最高提高了35%，最低提高了3.4%。

主要結論是：修正帶來了性能提高，且不論是CRF還是SVM，都能提高。主要原因是觀測函數是反映環境的不確定性與意圖識別的錯誤信息的一個渠道，因此加入信息熵的概率來修正觀測概率在理論上也有所支持。

3.3 真實對話實驗

上一組實驗是直接經過POMDP模型仿真模擬得出的結果，下面這一組實驗是放在真實對話中測試經過修正觀測概率后給對話系統帶來的影響。

表3、表4中的每個實驗都包含3個測試樣本集，第一個樣本集的對話輪數是212，第二個樣本集的對話輪數是87，第三個樣本集的對話輪數是100。分別對比表3和表4，可知對觀測概率經過修正后，在真實對話中，該對話系統的決策準確度比沒有使用修正的觀測矩陣的系統是要高的，對系統的決策性能有所提高。

通過實驗一與實驗二兩組實驗可知，使用CRF分類進行意圖識別得到的期望回報整體上會比使用SVM方法的要大，主要是因為本文使用的基于SVM分類器的意圖識別模塊的識別錯誤率perr為0.17，而基于CRF分類的意圖識別錯誤率perr為0.05，也就是說意圖識別錯誤率的大小會直接影響到模型的性能大小。

使用SVM作為意圖識別模塊的對話系統經過修改觀測概率方法后，系統決策性能的提升幅度比使用CRF的要大，主要是因為本文使用的基于SVM分類器的意圖識別模塊的識別錯誤率比基于CRF分類的意圖識別錯誤率要大，也就是說CRF的意圖識別率已經很高，修正前與修正后的概率變化不大，而SVM的意圖識別錯誤率比CRF的大，修正的觀測概率給對話系統帶來比較大的影響。如果從信息熵的角度來看的話，經過計算，使用CRF的意圖識別的系統得到的觀測平均信息熵是0.3168，而是用SVM的意圖識別的系統得到的觀測平均信息熵是1.0557。平均信息熵越高，不確定性越大，越需要修正觀測矩陣，可提升的性能也越大。平均信息熵越低，代表觀測比較可靠，越不需修正，甚至可以直接相信觀測，同樣可提升的性能也不大。

因此在意圖識別錯誤率比較高的情況是有必要對觀測概率進行合理的修正，以達到提高對話系統的決策性能的效果。

3.4 實驗總結

意圖識別模塊的性能很明顯對模型的期望回報有著很大的影響，模型的期望回報是反應該模型的性能重要指標，系統是通過意圖識別的結果對具有不確定性的環境的進行估計，根據不完全可觀測的結果，進行決策，執行動作，得到回報獎賞，進而與環境交互。因此意圖識別的性能和對環境的估計準確程度與對話系統的性能有著密切關系。通過實驗與分析可知，在意圖識別錯誤率一定的情況下，在觀測函數估計中引入對環境不確定性的信息，通過信息熵描述環境的不確定性，提高系統對環境的估計與判斷，使系統在不完全可觀測的情況下，提高決策的準確度與模型的期望回報。

4 結論

在本文中，把描述環境不確定性的信息熵加入到觀測函數里，修正觀測概率。以一個簡單的機器人教學系統為例子實現具體的POMDP模型，并通過兩個實驗考察觀測概率經過修正后與修正前的性能差異，驗證使用修正后的觀測概率的系統得到較好的效果。

作為使用POMDP模型來搭建對話系統這個方向的初步工作，本文的結果說明對話的決策性能受很多方面影響。可以通過很多方面提高對話決策性能，回報函數反映執行某動作得到的立即回報，也是與環境交互的結果之一，因此今后可以把回報函數的信息加入到觀測函數里面，增強觀測函數對環境的描述。