고려대학교 산업공학과 정태수 교수님 강의 정리

Week4: 마르코브 과정

• Lecture

4-1. 마르코브 프로세스 개요

불확실성 모델링

• Markov decision process
  • 확률적 동적 계획법: 동적 계획법 + 마르코브 프로세스
• 확률 (Probability)
  • 주위에서 발생하는 여러 사건들 --> 근본적으로 불확실성 내포
  • 불확실성을 표현할 수 있는 수단
• 확률변수와 확률분포
  • 예시 (날씨 - 맑음, 흐림, 비)
    • X=1(맑음 0.6), 2(흐림, 0.2), 3(비, 0.2)
    • P(X=1)=0.6, P(X=2)=0.2, P(X=3)=0.2
    • 확률변수(X) 정의 후 다양한 분석
  • 시간에 따른 날씨의 시계열
    • 불확실성, 내일 날씨와 오늘 날씨의 상관 관계가 존재함
      --> 시간의 흐름에 따라 불확실성 변동
    • 맑음 > 흐림 > 흐림 > 비 > 비 > 맑음 ...., 맑음 > 맑음 > 흐림 > 비 > 맑음 ....
      --> 확률에 대한 수학적 모델링을 위한 확률 프로세스

시간에 따라 확률적으로 변화하는 프로세스 예시

전염병 분석

• 최근: ML등 데이터 기반 분석
• 예전: 수학적 모델링 접근

사스 주차 별 신규 확진자 수

• 신규 확진자가 시간의 흐름에 따라 변동
• 공통 패턴: 일정 부분 증가 후 감소
• 수학적 모델링을 통해 알고 싶은 점
  • 현재까지의 확진자 수 이력을 바탕으로 다음주에 추가 신규 확진자가 50건 이상 될 확률은?
  • 평균적으로 몇 주 후에 확산세가 진정될 것으로 예상되는가?
    

주가 분석

• 시시각각으로 변하는 주가
• 수학적 모델링을 통해 알고 싶은점: 주가가 패턴을 보이며 변동될 때, 주식은 어떻게 될까?

확률과정(Stochastic Process)

• 개념
  • 확률적으로 변화하는 프로세스를 모델링하기 위해 수학적으로 접근하는 방법
  • Random process, Stochastic process
• 정의
  • 불확실성을 가지고 변하는 일련의 과정
  • 시간에 따라 어떤 사건이 발생할 확률 값이 변화하는 과정
  • 시간이 진행함에 따라 상태가 확률적으로 변화하는 과정
• 정리
  • 불확실한 시스템 모델링: 확률과 확률변수
  • 각각의 어떤 시점을 하나의 확률변수로 정함
  • 시간에 따른 확률변수들의 집합 $\{X_t: t \in T\}$
  • 확률변수와 결합확률분포 정의 필요

추가 용어

• 시간공간(Time space)
  • 시스템의 상태를 관찰하는 시점들의 집합
• 상태와 상태공간
  • 상태(State): 확률변수들이 가지는 어떤 값 (시스템의 상태)
    • 예시: 주가, 날씨, 전염병 신규 확진자 수
  • 상태공간(State space): 확률과정 ${X_t:t \in T}$의 확률 변수 $X_t$가 가질 수 있는 모든 가능한 값들의 집합

확률과정 예시 - 동전던지기

• 게임 개요
  • 동전 하나를 던져서 앞면이 나오면 +1점, 뒷면 나오면 -1점
  • 기존 점수에 더한 것이 동전던지기 게임의 점수
  • 플레이어가 종료를 선언한 시점에서 게임 종료
  • 마지막 점수가 양수면 점수 당 천원 + 음수면 점수 당 천원 -
  • 점수는 0점부터 시작
• 확률과정
  • 확률 변수 $X_n$: n번째 동전을 던졌을 때까지의 누적점수
  • 상태공간 S={$\cdots, -2, -1, 0, 1, 2, \cdots$}
  • 시간공간 T={0,1,2, ....}
• 게임 과정
  • 앞면이 나오면 +1, 뒷면이 나오면 -1
  • 시간의 흐름에 따라 불확실성을 가지고 변동되는 프로세스
    

확률과정 4가지 분류

예측

• 확률과정을 통해 알고 싶은 것 --> 예측
• 확률과정 {$X_t: t \in T$}에 대해: $P(X_{k+1}|X_k,X_{k-1}, .., X_0)$?
  • 확률과정이 정의되기 위해서는 결합확률분포가 정의되어 있어야됨
  • 결합확률분포는 아래와 같이 조건부 확률의 곱으로 표현됨
  • 즉, 조건부확률은 확률과정의 결합확률분포를 결정하는 중요개념
    

Episode

• 확률과정의 실현된 값들의 sequence (= sample path)
• 확률과정의 실현치들을 모아놓은 것 (일종의 시계열 데이터 샘플)
  

정상과정(Stationary process)

• 시간 t에 따라 확률법칙이 변하지 않는 확률과정
• 시간 t가 변하더라도 상태확률이 변하지 않는 확률과정

마르코브 성질

확률과정을 통해 알고 싶은 것 --> 과거부터 현재까지 어떤 과정을 거쳤을 때, 다음 단계에서 확률변수가 가지는 특정 값이 될 확률 (=> 조건부 확률)

조건부 확률이 가장 단순한 경우

• $P(X_{k+1}|X_k,X_{k-1}, .., X_0)$ = $P(X_{k+1})$
  과거와 완전히 독립적인 경우
  --> 시간의 흐름과 관계가 없으므로 분석할 필요가 없음

조건부 확률이 두번째로 단순한 경우

• $P(X_{k+1}|X_k,X_{k-1}, .., X_0)$ = $P(X_{k+1}|X_k)$
  • $X_k$: 현재
  • $X_{k-1}, .., X_0$: 과거
• 현재만이 미래를 결정하는 지표
• 조건부 확률이 과거와 상관없이 현재로 미래 결정
  --> 복잡한 확률과정 모델 중 가장 단순한 형태

정리

• 미래는 현재로부터 정해지며, 과거는 영향을 주지 못한다 --> Markov Process
  
  

이산시간 마르코브 체인(Discrete-Time Markov Chain; DTMC)

• 정의: 마르코브 성질을 만족하는 확률 과정
  • chain: 상태공간에 속해 있는 어떤 값들이 셀 수 있는 값일 경우
  • Markov Chain: 확률변수가 셀 수 있는 값 중에 하나를 선택
    

• 상태전이확률: i상태에서 다음상태 j가 될 확률 기술
  • 단계별 정의 가능: 첫번째 단계의 i상태가 두번째 단계의 j가 될 확률은 단계별로 다를 수 있음 (일반적인 이산시간 마르코브 체인)
    

Time-homogeneous DTMC

• 확률이 시간에 독립적
  
  

4-2. 마르코브 프로세스 예시

• Markov Chain: 확률변수가 셀 수 있는 값들 중에 하나를 선택하는 경우

마르코브 체인 예시 1

• 마르코브 체인 정의

  • time space: 쥐가 한번 움직일 때 그것을 하나의 단계로 가정 --> 그 단계들의 모음

• 확률변수 정의

  • $X_n$: n번째 단계에서 쥐의 방 번호
  • $X_0=1$

• Sample path(episode) 예시
  

• 마르코브체인 증명

  • 전이확률 정의 가능 시 --> 마르코브체인이라고 할 수 있음
    
    
  • 3번방, 9번방은 종료지점으로 다른 방으로 갈 확률이 0임

• Markov Process: 과거 이력과 상관없이 Markov Property를 따르는 확률과정

마르코브 체인 예시 2(재고 관리)

• 상황
  
  
• 발주 규칙
  
  
• 가정
  • 주차별 수요에 대한 확률 분포 (수요발생확률을 관리자가 미리 알고 있음)
    • 금요일 발주 시 주말 중 도착 (월요일 판매)
    • 영업일: 월~금(토일 휴무)
      
      
  • 물건 품절 시
    • 온라인 쇼핑 예시: 일단 주문만 접수
    • 본 예시: 물건이 없으면 주문 접수 X

문제 정의

• $X_n$을 n번째 주 금요일 밤 재고 수준이라고 할 때, {$X_n:n\geq0$}은 마르코브 체인인가?

풀이 과정

마르코브 체인 예시 3

문제 정의

응용

임의 확률과정을 마르코브 체인으로 변환 시 문제점

벽돌깨기 게임

4-3. 마르코브 보상 프로세스

도입

• 예시: 마르코브 체인에 따라 확률적으로 움직이는 학생 (아래 상태전이 diagram 참조)
  
  
  • 다음에 무엇을 할 것인지 결정
    • 과거에 어떤 것을 했는지 상관 X
    • 현재 행동이 다음 행동을 결정 --> 내가 현재 무엇을 했는지가 중요함
  • 상태전이확률로 표시
    

Markov Reward Process

• 보상 개념 도입
  • 특정 상태에 제공하는 인센티브
  • 어떤 점수가 특정 상태에 있을 때 리워드 제공
    
    
• 구성요소

에피소드(Episode)

• 정의: 특정 상태로부터 시작하여 종료 상태까지 (상태,보상) sequence
  
  
• 에피소드별 보상이 다름
  

$G_t$ (Return)

• t번째 시각 이후의 (감가율이 반영된) 누적 보상
• 에피소드에서 방문했던 상태별로 얻은 보상의 합
  

예시

• SNS reward = -1임
  
  
• 어떤 상태가 더 좋고 나쁜지 평가할 수 있는 지표가 필요
• 어느 상태에서 시작해야 종료 상태까지 갈 때 보상이 최대가 될 것일까?

가치함수(value function) $v(s)$

• 특정 상태에서의 리턴의 기댓값
• 상태 s로 부터 시작하는 프로세스로부터 기대할 수 있는 누적보상의 평균
• 프로세스가 진행됨에 있어, 상태s가 보상측면에서 얼마나 좋은 상태인지 평가하기 위한 지표
  

가치함수 계산

• 재귀식을 활용
  
  
• 풀이 예시
  

정리

마르코브 프로세스

마르코브 보상 프로세스