'transition probability table'에 해당되는 글 1건

  1. 2016.04.16 [선형대수] 마아코프 과정 (Markov Process), 대각화(diagonalization) 적용하여 계산하기 (2)

 지난 포스팅에서는 대각행렬(diagonal matrix), 행렬의 대각화(diagonalization), 그리고 고유값(eigenvalue)과 고유벡터(eigenvector)를 이용 (eigenvalue-eigenvector decompositon)하여 n차 정방행렬의 p제곱을 구하는 방법을 소개하겠습니다.

 

 이번 포스팅에서는 지난번에 소개했었던 내용을 마아코프 과정 (Markov Process)에 어떻게 적용할 수 있는지에 대해서 설명해보렵니다.

 

 먼저, 마아코프 과정(Markov Process)가 무엇인지부터 알아보겠습니다. 

 

 아래의 사진은 확률론으로 유명한 러시아의 수학자 Andrei Andreyevich Markov 입니다.  Markov Process, Markov Chain 은 이 이론을 발표했던 수학자 이름을 딴 것이예요.

 

        * 사진출처 : http://www.slideshare.net/butest/hidden-markov-models-with-applications-to-speech-recognition

 

 

 불확실한 상황 하에서 의사결정을 하려면 '확률'에 기초해서 분석을 해야 합니다.  어떤 사건이 발생할 확률값이 시간에 따라 변화해 가는 과정을 확률적 과정(Stochastic Process)라고 하며, 확률적 과정 중에서 한 가지 특별한 경우가 마아코프 과정 (Markov Process) 입니다.

 

 "어떤 상태가 일정한 시간 간격으로 변하고, 다음 상태는 현재 상태에만 의존하여 확률적으로 변하는 경우, 이 상태의 변화를 마아코프 과정(Markov Process)이라 부른다.  마아코프 과정에서는 현재 상태에 따라서만 다음 상태가 결정되며, 현재 상태에 이르기까지의 과정은 전혀 고려할 필요가 없다.

 

 어떤 실제 현상이 마아코프 과정을 따르는 경우, 충분한 시간이 지난 후에 어떤 상태가 되는지를 파악하는 것이 중요한 경우가 많다"

 

 - 출처 : 박부성 지음, '8일간의 선형대수학', 경문사

 

 마아코프 과정에서 연속적인 시간 변화를 고려하지 않고 이산적인 경우만 고려한 경우를 마아코프 연쇄 (Markov Chain) 이라고 합니다. 마아코프 연쇄는 각 시행의 결과가 여러개의 미리 정해진 결과 중의 하나가 되며, 각 시행의 결과는 과거의 역사와는 무관하며 오직 바로 직전 시행의 결과에만 영향을 받는 특징(Markov Property)을 가지고 있습니다.

 

 예를 들어서 설명을 해보겠습니다.

 

 맥주 회사의 마케터라면 시장 내 주요 브랜드 간에 시장점유율이 장기간 후에 (즉, 충분한 시간이 지난 후에) 어떻게 변화할지 궁금하겠지요?  이를 확률적으로 분석해 보기 위해서 캬아쓰 맥주와 하아뜨 맥주를 구매하는 고객들의 구매 행태를 장기간에 걸쳐서 관측하여 아래와 같은 데이터를 힘들게 구했습니다.

 

 

(1) 이번 주에 캬아쓰 맥주를 구매한 고객 중 90%가 다음 주에도 캬아쓰 맥주를 구매하고, 나머지 10%는 하아뜨 맥주로 갈아탄다.

 

(2) 이번 주에 하아뜨 맥주를 구매한 고객 중 80%가 다음 주에도 여전히 하아뜨 맥주를 구매하고, 나머지 20%는 캬아쓰 맥주로 갈아타더라.

 

 

 하아뜨 맥주회사의 '처음해' 신입사원이  '깐깐해' 과장으로부터 중장기 마케팅 전략 수립을 위해 "하아뜨 맥주와 캬아쓰 맥주의 장기적인 시장점유율"을 분석해오라는 지시를 받았습니다.  점쟁이도 아닌데 어케 장기 시장점유율을 알 수 있냐고 투덜대거나 무기력하게 멍때리지 마시기 바랍니다.  우리에게는 마아코프 과정(Markov Process)으로 장기 시장점유율을 추정해 볼 수 있는 데이터가 있으니깐요.

 

 위의 예에서 고객이 구매한 맥주 브랜드는 이 고객의 상태(state)를 나타내며(이번달에 캬아쓰 샀다, 아니면 하아뜨 샀다...), 맥주 구매는 일정한 시간 간격을 두고 변하고(주마다 구매, 불금 퇴근 길에 6팩~룰루랄라~), 다음 주의 상태(state)는 현재 주의 상태(이번 달에 무슨 브랜드 맥주를 샀는가)에만 영향을 받는 확률 과정을 따르고 있습니다. 다음주의 상태를 알기 위해 저번주, 저저번주, 저저저번주에 무슨 맥주 샀는지 알 필요가 없습니다.  네, 마아코프 과정Markov Process) 되겠습니다.

 

 - 상태 (state) 1 : 캬아쓰 맥주 구매

 - 상태 (state) 2 : 하아뜨 맥주 구매

 

라고 했을 때, (장기간에 걸쳐서 관찰 조사해서 얻은, 혹은 매주 맥주를 마시는 필자의 경험과 통찰로 부터 얻은?) 이번주 구매한 맥주 브랜드에서 다음주 구매한 맥주 브랜드로의 변화 확률을 표로 정리하면 아래와 같습니다.  아래와 같은 표를 전이확률표(transition probability table) 이라고 합니다. 

 

                             다음 주

 이번 주

캬아쓰 맥주

하아뜨 맥주 

 계

캬아쓰 맥주

0.9

0.1

 1.0

하아뜨 맥주

0.2

0.8

 1.0

 

 

맥주 애호가 '알프랜'이라는 고객이 이번주에 '캬아쓰' 맥주를 구매했다고 칩시다. 그러면 '알프랜' 고객이 다음주에 '캬아쓰' 맥주와 '하아뜨' 맥주를 구매할 확률은 위의 전이확률표(transition probability table)을 가지고 계산할 수 있습니다.

 

 

 

 

 

위에서 계산한 방법을 전이확률행렬(transition probability matrix)를 가지고 아래처럼 계산 표기를 간편하게 나타낼 수 있습니다.

 

 

 

 

 

2주 후(n=2) 의 전이확률값은 아래와 같이 계산할 수 있습니다.  마아코프 과정을 따르므로 2주 후의 확률은 직전 주의 확률에만 의존하며, 그 이전의 과거는 무시합니다.  단기기억만 가지고 계산을 해도 되니 얼마나 편하고 좋습니까!

 

 

 

 

n 시간 이후의 상태확률값 계산은 아래와 같이 일반화할 수 있습니다.

 

 

 

 

 

그러면 3주 후, 4주 후, 5주 후, ..., 12주 후, ..., n -> ∞ 로 일정 주기마다 시간이 꼬박꼬박 가게 되면 장기간 후에는 아래 처럼 확률값이 수렴을 하게 됩니다.

 

 

 

 

위의 계산 결과를 보면 처음에 무슨 맥주('캬아쓰' or '하아뜨')를 구매했었느냐에 따라서 n 의 초반에는 차이가 많이 납니다. (가령, 처음에 '캬아쓰'를 샀으면 그 다음주에 캬아쓰를 살 확률은 0.9, 하지만 처음에 '하아뜨'를 샀다면 다음주에 '캬아쓰'를 살 확률은 0.2).  하지만 n이 점차 커짐에 따라서 처음에 무슨  맥주를 구매했느냐에 상관없이 점점 캬아쓰 맥주 구매 확률은 0.669로 수렴, 하아뜨 맥주 구매 확률은 0.331로 수렴함을 알 수 있습니다.  이 값을 안정상태의 확률값 (steady-state probability) 이라고 합니다. 충분히 시간이 지난 후에 장기적으로 시장 점유율이 어떤 상태가 되는지를 예측해볼 수 있게 된 것입니다.  자, 이쯤되면 '처음해' 신입사원이 '깐깐해' 과장을 좀 놀래켜줄 수 있겠지요? ^^

 

 

 

지금까지 마아코프 과정(Markov Process)의 개념과 계산 과정을 설명드렸는데요, 이게 선형대수랑 무슨 관계라는 거지? 대각화(diagonalization)로 무엇을 한다는 것인지? 에 대해서 이제부터 설명을 드리겠습니다.  지난번 포스팅에서 다루었던 선형대수의 대각화 성질을 이용하면 계산을 매우 간편하게 할 수 있습니다.

 위에서 제시했던 식의 끝부분을 한번 더 써보면 아래와 같은데요, 아래 식의 오른쪽의 2차 정방행렬의 p제곱 부분을 주목해보세요.

 

 

고유값, 고유벡터가 존재하는 정방행렬의 p제곱 구하는 방법은 이전 포스팅에서 소개했었습니다. 그걸 이번 마아코프 과정 맥주 장기 시장점유율의 안정상태확률 구하는 문제에 한번 적용해보겠습니다.

 

(1) 고유값(eigenvalue) 구하기

 

 

 

 

 

(2) 고유벡터(eigenvector) 구하기

 

위에서 고유값을 먼저 구한 다음에, λ=1에 대응하는 고유벡터 V1은 아래와 같이 구합니다.

 

 

 

고유값 λ=0.7 에 대응하는 고유벡터 V2는 아래와 같이 구합니다.

 

 

상태전이확률 행렬 A = (0.9  0.2,   0.1  0.8)^T 의

고유값 λ1=1, 이에 대응하는 고유벡터 V1 = (1  1),

고유값 λ2=0.7, 이에 대응하는 고유벡터 V2 = (-1  2)

를 구했습니다.  따라서 상태전이확률 행렬 A는 아래와 같이 대각화(diagonalization)이 가능합니다.

 

 

 

 

(3) 첫 구매가 '캬아쓰' 맥주였을 때, 2주 후(n=2) 시간이 지난 후의 '캬아스 구매 확률', '하아뜨 구매 확률' 구하기

 

 

위에 계산한것을 보면 고유값, 고유벡터를 가지고 대각화해서 계산하는 것의 장점을 잘 모르겠지요?  도리어 고유값, 고유벡터 구하느라 더 난리치는거 아닌가 싶기도 하구요. 차라리 고유값, 고유벡터의 대각화를 사용안하고 그냥 저 위에서 마아코프 과정의 정의에 따라서 계산한 것이 더 간편하게 느껴지기까지 하지 않나요?

 

그러면 이번엔 2주 후(n=2)가 아니라 100주 후(n=100)의 상태확률의 변화를 계산해보는 경우는 어떨까요?  저 위에서 소개했던 방법으로 100번 반복 계산하려면 손 좀 아프겠지요?  계산 중간에 실수할 수도 있겠구요.  이걸 고유값, 고유벡터를 가지고 대각화하여 n차 제곱하는 성질을 이용하면 매우 간편하게 계산을 할 수가 있습니다.  아래에 n=100 일 때의 계산 방법 소개합니다.

 

 

(4) 첫 구매가 '캬아쓰' 맥주였을 때, 100주 후(n=100) 시간이 지난 후의 '캬아스 구매 확률', '하아뜨 구매 확률' 구하기

 

 

저~어기 위에서 처음에 계산했던 것 n -> ∞ 일 때의 상태확률 계산값이 '캬아스 0.669', '하아뜨 0.331'로 수렴했었는데요, 바로 위에서 고유값과 고유벡터의 대각화 성질을 이용해서 계산한 값도 정확히 일치하지요?

 

 

다음번 포스팅에서는 SVD(Singular Value Decomposition)에 대해서 알아보겠습니다.  이번 포스팅에서 이용한 고유값-고유벡터 분해(eigenvalue-eigenvector decomposition)이 정방행렬에 대해서만 적용이 가능한데 반해 특이값 분해 (SVD)는 m*n 행렬에 적용가능해 활용성이 매우 높은 방법이므로 기대해주세요.

 

이번 포스팅이 도움이 되었다면 아래의 '공감 ♡ 꾸욱~' 눌러주세요. ^^

 

 

Posted by R Friend R_Friend

댓글을 달아 주세요

  1. @@ 2018.07.19 17:14  댓글주소  수정/삭제  댓글쓰기

    X2 = X0 * A^2 를 행렬식 계산할때

    (1 0) 이 어떻게 나온 건지 궁금합니다... y값이 없어서 그런건가요?

    • R Friend R_Friend 2018.07.23 22:49 신고  댓글주소  수정/삭제

      제일 처음에 (즉, state 0) 구매한 맥주가 카스 1, 하이트 0 이었으므로 (1, 0)으로 기입한 것입니다. 만약 첫주에 하이트를 구매(즉, 카스 0, 하이트 1) 했던거면 (0, 1) 이 되는거구요.