HMM 實際應用過程中，如何確定隱含狀態數量？

11-16

最近在學習HMM模型在用戶行為和狀態預測中的應用，在不確定狀態數目未知的情況下，用什麼方法能確定，希望能有大神解答啊，感激不盡！

最近為什麼總有人問不確定聚類個數的問題呢？如何確定聚類演算法中的類別個數？ - 楊超的回答
這裡還是一樣的，如果不知道聚類個數，常用方法是利用狄利克雷過程，在這裡，即使用HDP-HMM。
但是DP對不熟悉貝葉斯方法的同學而言比較難，HDP-HMM就更難了。HDP-HMM只是HDP的簡單擴展，在teh最初的HDP論文中一筆帶過，具體的模型和演算法，請參考e.b. fox的論文。我的碩士論文也對其有詳細的整合和翻譯，但是網上似乎找不到，我自己也沒留備份。
另外，在HDP論文之前，有篇論文叫infinite HMM，其作者也是HDP論文的作者之一，好像叫Beal，你也可以看看。

當然，要說明兩點
1.HDP-HMM效果未必好，因為模型複雜度太高，然後和原問題的真實物理情況又不一致。
有多少現象真是個markov過程呢？就算真是的，那你真的知道每個狀態上的觀察概率么？人類的行為就是一個有限狀態的混合高斯?

2.任何基於DP的模型，雖然看上去是不用指定聚類數，也自稱是Bayesian nonparametric,但它實際是有個alpha參數的，它只是把顯示指定聚類數換成了用一個alpha參數來估計。
稍微了解下DP即可知道，alpha是DP的一個scale參數，也是中國餐館過程中產生一個新cluster的概率，alpha越大，就傾向於最終的聚類數越多。所以，使用DP只是獲取了在概率觀點上可以解釋通的控制聚類數的方法(如果用非概率觀點，一樣可以在目標函數中增加一個關於聚類數的懲罰項達到控制聚類數的目的，但是懲罰函數的物理意義不好解釋)，並沒有真正解決設定聚類數的問題，這也是發DP的論文時評審都要問的，「你的alpha怎麼給的？」
不過，倒是可以搞一個Dev集，在上面調出alpha，但dev集，在我看來就等於supervised學習了。。

如果有同學疑問，為什麼HMM里的狀態我也稱為聚類數，說明你對聚類和混合模型，混合模型和HMM的關係還沒搞清。

希望你最終沒有因為我而走到DP的坑。如果你是新手，正在研究HMM，那麼重點應該是搞明白混合模型和離散狀態時序模型的關係，搞清楚EM演算法和概率模型中的鏈式推斷演算法，這些會讓你受益無窮。

==================分割線===============================================
以上說的是學術界的做法，也是我熟悉的東西，下面說的其他想法。
我認為，真的研究問題，應該從物理出發，去搞清事物的原理，一個任務，為和非要用黑盒的東西，去建模推斷然後得到知識呢。我覺得那位匿名用戶說的雖然看起來沒有什麼理論性，一點不登堂入室，但是真的很對！

直接知道
足夠的信息去估計

根據領域知識，去研究問題，不要總是想著統計學，不要總想著套用幾個現有的機器學習的模型。

確定隱含狀態的數量，其實就是找出最大邊緣似然值的模型，即

$K^*=argmax_k ({cal {D}} mid K)$

所以一個很自然的起點就是用BIC來暴力搜尋，雖然嚴格來講BIC只是一個近似方法。不放心的話再加個交叉驗證。這種暴力搜尋法算一類。

另一類方法就是MCMC推斷法。這類方法最常見的就是Dirichlet process混合模型，可以用來擬合Gibbs採樣。Beal和Teh的論文有詳述，答主@楊超比我更懂。還有一個很老的方法叫reversible jump MCMC，具體這是個啥我也不知道，但我知道這方法基本沒人用。

再有一類就是變分推斷法。具體的演算法不展開，簡單地說就是變分貝葉斯(Variational Bayes)和EM演算法結合，求取邊緣似然函數的變分下界，也就是 ${cal{L}}(K) leq { m{log}} , p({cal{D}} mid K)$ 。有了下界，我們就可以近似 $p(K mid {cal{D}})$ 了。

推斷法通常要比暴力搜尋法要快。道理也很簡單，推斷法可以在判斷出隱含狀態數量K的效果不夠好的時候就不再繼續求模型的後驗分布了，但暴力搜尋會一路走到黑。

正如幾位答主共同提到的那樣，在不了解研究對象也不懂模型原理的情況下直接用上述方法來得到一個K，那隻能是煉丹的巫術。根據領域知識預先就可以設定好隱含狀態數量，才是墜吼的。

比如我在之前的一個回答裡面提到過，在統計套利中，HMM用來校準價差的參數。我們通常假設價差是服從Ornstein–Uhlenbeck過程的，也就是假設價差是均值回歸的。但價差在真實狀態空間里是有可能不服從均值回歸的，那麼很自然地把隱含狀態暫且設置為兩個，一個代表均值回歸，一個代表非均值回歸，而後者可以粗略地當作隨機遊走。而價差在所謂的風險中性測度里是可以證明是隨機遊走的。這樣一來，兩個隱含狀態既有理論基礎，又有現實依據，所以我們就能夠確定隱含狀態的數量了。

再比如，我要研究信息對order book（粗略地說就是高頻的交易單薄）的影響。其實絕大多數時候，我們的交易都是由信息驅使的。我們可以有三種隱含狀態，一種是因為掌握了內幕信息而引發的交易，第二種是公開信息引發的交易。那麼既然金融市場的信息只有內幕和公開之分，何來的第三種隱含狀態？答案是：「其它」...也就是單純提供/釋放流動性，不存在信息驅動的交易。

所以確定隱含狀態有一個拇指法則，那就是你可知的，可描述的「有序態」，再加上一個你不可知的，不可描述的「混沌態」。如果你把HMM跑下來發現大部分時間都在「有序態」之間流轉，那說明你的狀態設置得還是合理的，但如果「混沌態」佔據了大部分時間，那你就先去面壁一天，然後再回來改模型吧。

不是大神，希望引來大神...
據目前我的體會，
1.要麼就是直接知道！
2.要麼就是有足夠的信息來估計出一個比較合理的範圍，然後選性能最好的估計值，木有其他辦法
.....
這也是為什麼現在很多benchmark 吵翻天的根本原因....

在hidden variable 非常多，問題非常複雜的時候，牽扯性能的就不僅僅是對hidden variable 的估計了
所以，用欠抽的描述來說 : it"s an art ...

BIC: http://www2.imm.dtu.dk/courses/02433/doc/ch6_slides.pdf

DIC: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.58.6208amp;rep=rep1amp;type=pdf

難道不是根據BIC 值一個一個試嗎？

一個個的試其實本來就沒有最佳的都是根據實際情況設定的

1.NBs
貝葉斯定理

一般來說，x已給出，P(x)也是一個定值（雖然不知道準確的數據，但因為是恆值，可以忽略），只需關注分子P(x|yi)P(yi)。P(yi)是類別yi的先驗概率，P(x|yi)是x對類別yi的條件概率。
貝葉斯定理說明了可以用先驗概率P(yi)來估算後驗概率P(x|yi)。

貝葉斯分類器
設x∈Ω是一個類別未知的數據樣本，Y為類別集合，若數據樣本x屬於一個特定的類別，那麼分類問題就是決定P(yi|x)，即在獲得數據樣本x時，確定x的最佳分類。所謂最佳分類，一種辦法是把它定義為在給定數據集中不同類別yi先驗概率的條件下最可能的分類。貝葉斯理論提供了計算這種可能性的一種直接方法。
舉一個簡單的例子:
yi 是一個包含了整數的數據集合yi=(1,1,1,2,2,5,...,86),每個yi中的數據數量不一定相同，一共有N個這樣的yi數據集合，最終組成了一個擁有整數集合的數組。把這個數組當成已經劃分好的不同類別。現在給出一個整數，比如1，問這個1屬於哪一個集合或者說由某個類別yi產生該整數的可能性是多少？！
利用以上的貝葉斯定理可知，給定整數1的條件下，問屬於yi類別，就等同於求解先驗概率P(yi)與P(x|yi)的概率乘積大小。P(yi)表示類別yi的分布概率，在這裡可以簡單地定義為"每個類別yi的數據量/總數據量"（這種定義是有意義的，某個類別包含數據量越大，那麼產生這個數據的可能性就越大）。另外，除了這個先驗概率P(yi)之外，還要考慮條件概率P(x|yi)。在這個例子中，不同的yi類別可能都包含了1這個整數，但是每個類別中1出現的概率不一樣。所以，最後1屬於yi類別的概率=類別yi發生的概率×1在類別yi中的出現概率。

貝葉斯網路(Bayesian Network)
貝葉斯網路是最基本的有向圖，是類條件概率的建模方法。貝葉斯網路包括兩部分：網路拓撲圖和概率表。貝葉斯拓撲圖的有向邊指定了樣本之間的關聯。

概率圖示意

每個節點的條件概率分布表示為：P(當前節點|它的父節點)。

聯合分布為：

舉例：

聯合分布為

2.MEM
最大熵模型主要是在已有的一些限制條件下估計未知的概率分布。最大熵的原理認為，從不完整的信息（例如有限數量的訓練數據）推導出的唯一合理的概率分布應該在滿足這些信息提供的約束條件下擁有最大熵值。求解這樣的分布是一個典型的約束優化問題。

概率圖示意

最大熵推導過程省略，直接給出最後的模型公式——指數形式

其中是歸一化因子

最大熵模型公式中的表示特徵函數；表示特徵函數的權重，可由訓練樣本估計得到，大的非負數值表示了優先選擇的特徵，大的負值對應不太可能發生的特徵。

3.HMM
狀態集合Y，觀察值集合X，兩個狀態轉移概率：從yi-1到yi的條件概率分布P(yi | yi-1)，狀態yi的輸出觀察值概率P(xi | yi-1)，初始概率P0(y)。
概率示意圖

狀態序列和觀察序列的聯合概率

4.MEMM
用一個分布P(yi | yi-1,xi)來替代HMM中的兩個條件概率分布，它表示從先前狀態yi-1，在觀察值xi下得到當前狀態的概率，即根據前一狀態和當前觀察預測當前狀態。每個這樣的分布函數都是一個服從最大熵的指數模型。

概率圖示意

狀態yi 的條件概率公式（每個i 的狀態輸出都服從最大熵的指數模型）

5.MRF
隨機場可以看成是一組隨機變數(y1, y2, …, yn)的集合（這組隨機變數對應同一個樣本空間）。當然，這些隨機變數之間可能有依賴關係，一般來說，也只有當這些變數之間有依賴關係的時候，我們將其單獨拿出來看成一個隨機場才有實際意義。
馬爾可夫隨機場是加了馬爾可夫性限制的隨機場，一個Markov隨機場對應一個無向圖。定義無向圖G=(V,E)，V為頂點/節點, E為邊，每一個節點對應一個隨機變數，節點之間的邊表示節點對應的隨機變數之間有概率依賴關係。

馬爾可夫性：對Markov隨機場中的任何一個隨機變數，給定場中其他所有變數下該變數的分布，等同於給定場中該變數的鄰居節點下該變數的分布。即：

其中表示與yi有邊相連的節點。

Markov隨機場的結構本質上反應了我們的先驗知識——哪些變數之間有依賴關係需要考慮，而哪些可以忽略。

馬爾可夫性可以看成是馬爾科夫隨機場的微觀屬性，而宏觀屬性就是聯合分布。假設MRF的變數集合為Y={y1, y2,…, yn}, CG有是所有團Yc的集合。

其中表示一個團(clique)Yc的勢能，以上公式也可以具體寫成

其中Z是歸一化因子，是對分子的所有ys = y1, y2,…, yn求和得到。T是個溫度常數（一般取1）。U(y1, y2,…, yn)一般稱為能量函數(energy function)，定義為在MRF上所有團勢(clique-potential)之和。

在MRF對應的圖中，每一個團(clique)對應一個函數，稱為團勢(clique-potential)。這個聯合概率形式又叫做Gibbs分布(Gibbs distribution)。
Hammersley-Clifford定理給出了Gibbs分布與MRF等價的條件：一個隨機場是關於鄰域系統的MRF，當且僅當這個隨機場是關於鄰域系統的Gibbs分布。關於鄰域系統δ(s)的MRFX與Gibbs分布等價形式表示為

在圖像處理中，對先驗模型的研究往往轉換為對能量函數的研究。C表示鄰域系統δ 所包含基團的集合，Vc(·)是定義在基團c上的勢函數(potential)，它只依賴於δ(s)，s∈c的值。δ={δ(s)|s∈S}是定義在S上的通用的鄰域系統的集合。
上式解決了求MRF中概率分布的難題，使對MRF的研究轉化為對勢函數Vc(x)的研究，使Gibbs分布與能量函數建立了等價關係，是研究鄰域系統 δ(s) MRF的一個重要里程碑。

6.CRF
如果給定的MRF中每個隨機變數下面還有觀察值，我們要確定的是給定觀察集合下MRF的分布，也就是條件分布，那麼這個MRF就稱為CRF(Conditional Random Field)。它的條件分布形式完全類似於MRF的分布形式，只不過多了一個觀察集合X=(x1, x2,…, xn)，即
條件隨機場可以看成是一個無向圖模型或馬爾可夫隨機場，它是一種用來標記和切分序列化數據的統計模型。

理論上，圖G的結構可以任意，但實際上，在構造模型時，CRFs採用了最簡單和最重要的一階鏈式結構。

一階鏈式CRF示意圖（不同於隱馬爾科夫鏈，條件隨機場中的xi 除了依賴於當前狀態，還可能與其他狀態有關）

令 X=(x1, x2,…, xn)表示觀察序列， Y=(y1, y2,…, yn)是有限狀態的集合。根據隨機場的基本理論，無向圖中關於頂點的標記條件概率

其中歸一化因子

以上的是狀態函數和轉移函數的統一表達形式。

幾種比較

條件隨機場和隱馬爾科夫鏈的關係和比較
條件隨機場是隱馬爾科夫鏈的一種擴展。

不同點：觀察值xi不單純地依賴於當前狀態yi，可能還與前後狀態有關；
相同點：條件隨機場保留了狀態序列的馬爾科夫鏈屬性——狀態序列中的某一個狀態只與之前的狀態有關，而與其他狀態無關。（比如句法分析中的句子成分）

MRF和CRF的關係和比較
條件隨機場和馬爾科夫隨機場很相似，但又說不同，很容易弄混淆。最通用角度來看，CRF本質上是給定了觀察值 (observations)集合的MRF。
在圖像處理中，MRF的密度概率 p(x=labels, y=image) 是一些隨機變數定義在團上的函數因子分解。而CRF是根據特徵產生的一個特殊MRF。因此一個MRF是由圖和參數（可以無數個）定義的，如果這些參數是輸入圖像的一個函數（比如特徵函數），則我們就擁有了一個CRF。
圖像去噪處理中，P(去噪像素|所有像素)是一個CRF，而P(所有像素)是一個MRF。

個人不是這方面的專家，但看了吳軍的《數學之美》，覺得可以用資訊理論的最大熵之類的方法來確定。