工業局生醫電子

2017年1月4日 星期三

馬可夫鏈 (Markov Chain)




1) Random Variable X

2) Random Process (Stochastic Process) {X(t), t>=0} , 是一個Random Variable 的集合, (t可以是discrete time or continuous time)

3) Markov Process, 也是 Random Process,此Random Process {Xi,i=0,1,2....}是在描述狀態轉移的過程 (所有你會有一群狀態序列Chain), 但此系統的行為是chain中的節點,只和相鄰的節點有關,即你下一個狀態是什麼只取決你上一個狀態有關,而和先前的狀態無關 (此行為是是Markov property, 即Memory-less)



a discrete-time  Markov Process-->  Markov chain(DTMC)
a continuous-time Markov process--> Markov chain (CTMC)


4) Renewal process : is a counting process in which the inter-arrival times are an iid random sequence
  
     在講時間,事件發生的間隔時間為一個隨機變數Ti , 若Ti 彼'此為iid 則此counting process為renewal process。 (只看時間,不看狀態)


 
5) Markov Renewal Process

將 Markov process 再加上時間, 則狀態轉換和時間產生了關係。 Markov Renewal Process 共包含了2個隨機變數 {Xi,Ti},狀態是一個隨機變數,時間也是一個隨機變數。也許我們想關心,在這個狀態待多久後會跳到下一個狀態。


Consider a state space  Consider a set of random variables , where  are the jump times and  are the associated states in the Markov chain (see Figure). Let the inter-arrival time, . Then the sequence  is called a Markov renewal process if




6) Semi-Markov process 

  1. If we define a new stochastic process  for , then the process  is called a semi-Markov processNote the main difference between an MRP and a semi-Markov process is that the former is defined as a two-tuple of states and times, whereas the latter is the actual random process that evolves over time and any realisation of the process has a defined state for any given time. The entire process is not Markovian, i.e., memoryless, as happens in a continuous time Markov chain/process (CTMC). Instead the process is Markovian only at the specified jump instants. This is the rationale behind the name, Semi-Markov.[1][2][3] (See also: hidden semi-Markov model.)

    Semi-Markov process 和Markov process的差異是,

    會進入到某一個狀態 Xn ,只會發生在特定的時間區間,而不是發生在所有的時間點,因此,Semi-Markov Process 其Markovian 特性 (即memory-less的特性), 只會在特定時間而已 ,而非任意時間區間) 。即在Xn狀態只有和上一個狀態有關。而會落在上一個狀態其時間點也是特定的。

(defined in the above bullet point) where all the holding times are exponentially distributed is called a CTMC
Ergodic

random process is ergodic if its time average is the same as its average over the probability space, 

在某一段時間的平均, X/Ti 和 整個時間的平均 X /T 是相同, 則稱為ergodic







Markov Model  ( 所有狀能已知)

馬可夫模型是一連串事件(狀態)接續發生的機率
馬可夫鏈英語:Markov chain),又稱離散時間馬可夫鏈(discrete-time Markov chain,縮寫為DTMC[1]),因俄國數學家安德烈·馬可夫(俄語:Андрей Андреевич Марков)得名,為狀態空間中經過從一個狀態到另一個狀態的轉換的隨機過程

A Markov chain is a stochastic process with the Markov property. The term "Markov chain" refers to the sequence of random variables such a process moves through, with the Markov property"memorylessness"). defining serial dependence only between adjacent periods (as in a "chain").

It can thus be used for describing systems that follow a chain of linked events, where what happens next depends only on the current state of the system.




 已定義所有的狀態, 並有定義好從狀態 i 到各個狀態 j 的機率, 若共有N個狀態, 這就有一個矩陣描述每一個狀態彼此間的轉移的機率, ,這就狀態轉移機率矩陣 (State Transition probability matrix)

存在在一個狀態序列

常問的問題:


  1. 我們也許想知道, 原本在S0 狀態,經過T步後, 會落在那一個狀態? ( 這會需要知道 Pij : 狀態i 到 j 的機率)
  2. S0-->S1-->S2, 一開始在S0走2步後, 出現在S2的機率為何? 




Relation to other stochastic processes[edit]




  1. A semi-Markov process (defined in the above bullet point) where all the holding times are exponentially distributed is called a CTMC. In other words, if the inter-arrival times are exponentially distributed and if the waiting time in a state and the next state reached are independent, we have a CTMC.
  2. The sequence  in the MRP is a discrete-time Markov chain. In other words, if the time variables are ignored in the MRP equation, we end up with a DTMC.
  3. If the sequence of s are independent and identically distributed, and if their distribution does not depend on the state , then the process is a renewal process. So, if the states are ignored and we have a chain of iid times, then we have a renewal process.
     事件發生的時間和狀態都無關(不論狀態是過去,現在或未來的狀態)


Hidden Markov Model  (存在未知狀態)


也許某些情況,我們無法或根本無法完整定義所有事件(狀態)的轉移機率矩陣 ,

圖來源: http://www.csie.ntnu.edu.tw/~u91029/HiddenMarkovModel.html#1


存在一個Hidden State ,不知道內部會怎麼選的機制, 而僅知道 S1,S2,S3狀態

在這個例子裡,有兩個事件的序列:一個是我觀察得到的;另一個是我看不到的,也就是對我來說是隱藏的,就是Hidden State。由於我知悉這兩個馬可夫鏈之間的關係,所以我便可以由其中一個馬可夫鏈的狀態,去預測另一個馬可夫鏈的狀態。而「隱馬可夫模型」,便是描述這樣的兩個序列的關係的統計模型。

HMM讓我們可以利用「看得到的」連 續現象去探究、預測另一個「看不到的」連續現象。



隱藏馬可夫模型的特色就是:我們只看到了觀察序列(果),但是我們看不到狀態序列(因);我們只看到了依序噴出的 T 個值,但是我們看不到一路走過的是哪 T 個狀態。

References:





1 則留言 :

  1. Thanks for sharing, nice post!

    Tìm hiểu loại siro vitamin tổng hợp cho bé tốt nhất hiện nay là gì hay trẻ 1 tuổi biếng ăn phải làm sao và để tìm giải pháp trẻ biếng ăn nên cho uống thuốc gì và mẹ nên bổ sung loại vitamin và khoáng chất giúp trẻ phát triển như thế nào và loại thuốc bổ dành cho trẻ biếng ăn tốt nhất hiện nay là gì hay địa chỉ bán máy đưa võng giá rẻ uy tín nhất hiện nay cũng như lựa chọn máy đưa võng nào tốt nhất hiện nay.

    回覆刪除