[인공지능] 마르코프 체인

마르코프 체인

 

• 마르코프 성질을 가진 이산시간 확률과정
  • 마르코프 성질:
    • 과거와 현재 상태가 주어졌을 때의 미래 상태의조건부 확률 분포가 과거 상태와는 독립적으로 현재 상태에 의해서만 결정됨
    • 오늘의 상태는 어제의 상태에 의해서만 결정되고, 내일의 상태는 오늘의 상태에 의해서만 결정됨
  • 이산시간 확률과정:
    • 이산적인 (뚜렷이 구분되는) 시간의 변화에 따라 확률이 변화하는 과정
    • e.g., 아침 - 점심 - 저녁

 

마르코프 체인의 구성 요소

 

• 상태 집합
  • S = {1,2,...,m}
  • 주식: S = {상승, 하락}
  • 날씨: S = {해, 비, 흐림, 눈, ....}
• 상태 전이 확률 (조건부 확률)
  • 현재 상태 i에서 다음 상태 j로 변화할 확률
  • Pij = P(다음상태 = j | 현재상태 = i)

상태 전이 트리

 

+ 상태와 상태 전이 확률이 주어지면 상태 전이도로 나타낼 수도 있다.

상태전이도

 

상태 전이 확률의 성질

 

• 상태 전이 확률은 오로지 현재 상태에 의해 결정된다 (마르코프 성질).
  • P(내일 = 해|오늘 = 비, 어제 = 비, 그저께 = 해, ...) = P(내일 = 해|오늘 = 비)
• 상태 전이 확률은 0보다 큰 수이고, 현재 상태가 갗은 모든 전이 확률의 합은 1이다.

 

전이 확률 매트릭스

 

• 마르코프 체인의 전이확률은 매트릭스로 표시할 수 있다.

상태 전이도와 상태 전이 확률 매트릭스

 

2-step 전이 확률

 

• 내일 날씨는 오늘 날씨에 의해 확률적으로 결정된다. 날씨 전이도는 위와 같고, 오늘 날씨가 주어졌을 때, 모레 날씨 확률을 나타내는 날씨 전이도는 다음과 같다:
  • 이는 전이 확률 매트릭스의 곱을 통해서 쉽게 구할 수 있다.

2-step

 

n-step 전이 확률

 

• 마르코프 체인의 활용
  • 시스템이 마르코프 체인에 따라 상태 전이를 했을 때 n-step 뒤에 특정 상태에 머물 확률을 모델링 할 수 있다.
  • 날씨 모델의 n-step 전이 확률 (n → ∞)

n-step

 

• 해당 예제에서 n-step뒤의 상태는 초기 상태에 따라 확률이 다르다.
• 상태 1에서 시작하면 n-step뒤 무조건 상태 1에 도달하고, 상태 2에서 시작하면 2/3확률로 상태1이 도달하고 1/3확률로 상태 4에 도달한다.
• 또한 n이 무한대로 가까워지면 상태 2와 상태 3에는 도달할 확률은 0에 가까워진다.
• 이런 특성에 따라 각 상태들을 구분해야 한다.

 

상태의 구분

 

• Accessible
  • 특정 상태 i에서 상태 j로 이동할 수 있는 경로가 있다면, 상태 j는 상태 i에서 accessible하다.
• Recurrent
  • 상태 i에서 도달 (accessible)할 수 있는 모든 상태 j에 대해, 상태 j에서도 상태 i에 도달할 수 있다면 상태 i는 recurrent한 상태이다.
• Transient
  • Recurrent한 상태가 아니면 transient한 상태이다.

 

Recurrent class

 

• A(i)는 상태 i에서 accessible한 모든 상태들의 집합이다. 만약 상태 i가 recurrent 상태라면 A(i)는 recurrent class다.
• A(i)가 recurrent class일 때, A(i) 집합에 있는 모든 상태들은 서로 accessible하고, A(i)에 속해있는 상태에서는 A(i)에 속하지 않는 상태에 절대 accessible할 수 없다.

 

Recurrent class의 성질

 

• 최소 하나의 recurrent 상태가 존재한다.
• Recurrent 상태들은 recurrent class들로 구분할 수 있다.
• 만약 상태 j가 transient면, n-step Pij는 0에 수렴하고, 상태 j는 유한한 횟수 만큼만 방문된다.
• 만약 상태 j가 recurrent고 j∈A(i)면, n-step Pij는 0으로 수렴하지 않는다. 만약 초기 상태 j에서 시작하면 A(i) 집합에 있는 모든 상태는 무한 횟수 만큼 방문된다.
• n이 증가함에 따라 방문한 상태가 transient일 확률은 0으로 수렴한다. N이 증가함에 따라 방문한 상태가 recurrent일 확률은 1에 가까워진다.