조건부 확률부터 마르코프까지 - 4) 마르코프 체인

2021.12.20 - [Python과 확률] - 조건부 확률부터 마르코프까지 - 3) 나이브 베이즈 분류 (근데 간단한)

조건부 확률부터 마르코프까지 - 3) 나이브 베이즈 분류 (근데 간단한)

요놈과 함께보시면 더욱 재밌습니다.

 

아 하루에 알고리즘코테 2개, 딥러닝 코테준비 1개를 하려고 했는데, 도저히 마르코프 체인에서 납득이 안되서,

계속 파보고, 지인들에게 물어보는 시간들을 가지느라 드디어 아티클을 쓰게 되었다. 이번 글은 할말이 많아서 길어질지도 모르겠다.

 

마르코프 체인은 증명까지 이야기하면 정말 긴데, 한마디로 설명하면,

과거로부터 이어져오는 어떤 서순이 있는 경우, 미래의 상태는 현재의 상태에만 의거하여 확률이 결정된다.

라는 점이다.

이에 대한 증명은, 조건부확률과 확률적 서순에 대한 Chapman - Kolmogorov Equatuin 정리로 증명 가능한데, 하기 아티클들을 참고하면 도움이 많이 될 것 같다.

뭐 사실 무지성으로 이해하자면, 전이행렬을 만들어놓고, 그것에 대한 타임 T만큼의 제곱을 해주면 된다는 얘기로, 시간이 무한이 흐르면서 제곱이 되다보면 결국 어떤 안정한(Stational) 상태에 들어가게 된다는 이야기들이 나온다.

https://analysisbugs.tistory.com/95?category=837870 

[응용통계] 8. 마코프 체인 (Markov Chains) (2)

https://www.youtube.com/watch?v=CnMq_ld3KkE 

 

일단 재밌는 점은,

1.

베이즈 정리, 나이브 베이즈 분류도 조건부 확률에 의거한다는 점이고, (A였을 가정하에 B일 확률)

마르코프 체인도, 조건부 확률에 의거한다는 점이다. (현재 A였을때 바로 다음 미래에 B일 확률)

 

2.

베이지안도 네트워크, 즉 그래프가 존재하며,

마르코프 체인도, 그래프가 존재한다.

즉, 두개의 그래프를 2차원 행렬로 표시할 수 있다.

 

3.

원리만 따지고보면, 둘이 분명 다른데, 실생활 문제에서 이거 베이즈쓸래? 마르코프 쓸래? 하면 순간...고민된다....!

마치 내가 알고리즘 코테 풀때 어떤문제는 DP여도 BFS로 풀 수 있을 것 같은데....하는 고민이 드는 것과 비슷하다.

 

이거 혹시 헷깔려본 사람 없는가?

아티클을 한글로 찾아본다면, 베이즈는 베이즈, 마르코프는 마르코프만 설명되어있으며,

둘이 뭐가 다르긴 다른건지? 비슷하긴 한건지? 똑같이 조건부 확률 써놓고는, 차이점이 무엇인지?

심지어 댓글을 달아도 모르는 사람들이 무성하다. (아 저는 하나는 알고 하나는 잘 몰라서.... 하는 반응들)

예시,

https://www.youtube.com/watch?v=KueAHu7iFNE 

외에 블로그들에도 몇개 달아봤는데, 대부분 다 모르쇠였다...ㅠㅠ

 

https://www.researchgate.net/post/Difference_between_Bayesian_Network_and_Markov_model

기어이 외국 아티클, 외국 유투브도 찾아보고, 댓글도 달아봤지만, 뾰족한 수는 없었고, 서울대 박사를 취득하신 통계학 형님에게 여쭤봐서 그나마 구도정도만 잡아볼 수 있었다. (정말 감사합니다 형님)

 

일단 내가 헷깔린 부분들부터 차근차근 나아가보자.

베이지안 네트워크도 결국엔 A였을때 B다.

마르코프 네트워크도 현재 A였을때 미래의 B다.

날씨를 예로 들어보자.

맑은 뒤 비올 확률

이거 딱 봐도 베이즈도 가능하지만, 마르코프도 가능해보인다.

키가 180이었을때 남자일 확률

이거는 딱 봐도 베이즈로는 가능해보이지만, 마르코프로는 불가능해보인다.

 

서술형 문제를 당도했을때, 우리는 베이즈로 접근하는 것이 옳은가? 마르코프로 접근하는 것이 옳은가?

또한, 이전에 베이즈 정리를 하면서 느껴봤겠지만, 확률 조합의 곱으로 조건부 확률을 구했다.

마르코프도 계산식을 조금만 톺아보면, 결국 확률들에 대한 상태와의 곱의 연쇄이다.

 

마르코프에서 이야기하는 현재의 상태는, 베이지안에서 얘기되는 prior와 다른가...?

 

막연하게 파이썬의 pomegranate 라던가, scikit-learn이라던가 쓸때는 이거를 왜 고민 안해봤지? 싶을정도로 생각하고 써본적이 없었는거 같다. (매우 부끄러운 사실)

또한, MCMC, HMM정도나 다루다보니, 그 이전의 문제 해결 방식은 접근조차 잘 해보려고 하지 않았다.

이런 개인적인 수치스러움도 있다보니, 더 정확하게 알고싶은 고집들도 생겼고, 그래서 파보느냐고 시간이 오래걸렸다.

 

일단 결론부터 이야기하자면, 몇가지 사례 혹은 개인적 납득으로 스스로 점철된 부분들이 있고, 그정도 이해로 넘어갈 만한 사유라고 생각된다.

1. 마르코프 네트워크라고 하더라도, 비순환 형식이라면, 베이즈 정리로 계산되는 조건부 확률과 결과가 똑같다.

이 사실은, 반례가 충분히 있을 수 있다. 내가 손으로 몇개 풀어보고 일단 점철되었다.

그냥 노오력을 좀 했다는 이야기.

일반화 하기위해 날씨 예제를 들어보면, 맑음이 또 맑음이 되는 어떤 그런 단순 순환구조 조차 없는 경우, 결국 마르코프를 구하기위한 전이행렬과, 베이즈 정리로 귀결되는 확률결과는 동일하다.

 

2. 마르코프로 구하기 위한 값은 통상 N X N 정방행렬로 전이행렬이 구성되어야 하며, 베이즈 정리로 구할 수 있는 확률의 값은 행렬의 shape이 규격화 되진 않는다.

해당 부분도 내가 마르코프 네트워크를 전이행렬로 구성하다보니 느껴진 한계다. 마르코프는 비방향성 그래프로, 전이행렬을 구하기 위해서는 엣지가 연결되지 않더라도, 각 노드들에 관계는 전부 표현 가능해야 한다.

하지만 베이즈는, 엣지가 완전 연결되는 형태가 아니더라도, 구할 수 있다. (키와 몸무게 등으로 여자, 남자를 가리는 문제를 예제로 풀어보면, 정방이 아니어도 된다.)

 

3. 하지만 조건부 확률을 이용하는 개념은 똑같으므로, 문제에서 다각도로 바라볼 필요가 있다.

이 부분이 서울대 박사 형님이 말씀해주신 부분으로, 내 관념을 많이 바꿔놓았다. 그 분이 실무에서 데이터를 보다보면, 베이즈로 풀 수도 있고, 마르코프로도 풀 수 있는 경우가 많다고 하셨다.

이럴 때는 실무자인 나의 입장에서, 두개를 전부 잘 이해해서, 빠르게 확률을 구해보고, 더 신뢰도 높은 값을 구해주는 자세가 중요하므로, 베이즈니 마르코프니 편가르지말고, 두개를 명확하게 이해하고 실무에 적용할 수 있는 역량을 키우라는 말씀이었다. (다만 두개의 부분은 학파의 관점이 있으니, 관심있다면 찾아보는게 좋다고 하셨다.)

 

3가지 관점을 전부 놓고 봤을때 내 결론은 이렇다.

1) 일단 어떤 문제에 무엇을 적용하는 것이 더 좋다는 마인드는 버려야겠다. 내가 구할 수 있는 상황을 전부 가져다놓고, 확률의 연산규칙에 따라 구할 수 있는 가장 좋은 안을 선택하는 것이 바람직하다.

2) 다만 전이확률 행렬을 정방으로 구할 수 있는지, 그렇지 않은 상황인지는 고려해서, 문제를 빠르게 해석하는 능력은 필요하겠다. (마르코프가 안될 상황인데, 고집부리고 있지 말자는 이야기.)

3) MRF(마르코프 랜덤 필드) 내용을 좀 보다보면, 약간 베이지안 네트워크는 마르코프 랜덤 필드에 포함되는 관계인 것도 같다. (정확히는 아닌 것 같기도.)

https://ko.wikipedia.org/wiki/%EB%A7%88%EB%A5%B4%EC%BD%94%ED%94%84_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC

마르코프 네트워크 - 위키백과, 우리 모두의 백과사전

https://www.youtube.com/watch?v=iBQkZdPHlCs 

위에 유투브가 도움이 많이 될 수 있다.

 

일단 그래서 내 내면에서 발생하는, 베이즈 계열과 마르코프 계열에 대한 마찰은 좀 일단락이 되었고, 실제로 마르코프 체인을 써서 할 수 있는 예제가 무엇일지 생각해보았다.

 

어찌보면 여태까지 고생한 부분들이, 내가 마르코프를 잘 이해하지 못해서, 베이지안과 제대로 적용해서 비교해볼 생각도 못해봤다는 느낌이 들어서, 그러면 내가 여태 본 아티클들은 잘 본걸까? 이런 생각이 들었고, 내가 본 아티클들을 크롤링해서, 이거로 마르코프 체인으로, '마르코프'라는 단어를 던졌을때 다음 단어는 무엇을 예측해서 문장이 생성되는지 궁금해졌다.

 

결국 마르코프와 베이즈 정리의 적용을 규정짓는 것은 얼마나 전이행렬을 수려하게 구성하느냐의 차이라고 생각이 들었고, 그 부분을 집중해서 소스를 구현하다보니, 구현하는데 크게 어려움은 없었다.

https://github.com/YooSungHyun/probability/blob/main/markov_sentense_pred_sample.ipynb

GitHub - YooSungHyun/probability: Independent, Markov Property, Chain, HMM and BEYOND!🚀

일단은 내가 초심자라고 생각되어, 숫자나 영어, 특수문자는 전부 뺐고, 다만 '.' 문자열만 문장의 최종으로 규정하기 위해 살려줬다. sample.txt에는 내가 여태껏 즐겨찾기 해놓은 게시물들의 크롤링 문자열들이 담겨있다.

블로그가 원체 자유분방하니 okt의 normalize를 써서 간단하게 정규화 하였다.

sample.txt는 블로그 저작권 문제가 있을 수 있어, 공개하지 않겠다.

# mecab과 konlpy는 설치 되어있어야 합니다.
# 이후에 numpy도 필요하긴 해요.
# 행렬곱이나 전치, list로 할라니 성능도 안나고 문제네요...
from konlpy.tag import Mecab, Okt

with open("sample.txt", "rt", encoding='utf-8') as f:
    text_list = f.readlines()

def clean_text(text):
    cleaned_text = re.sub('[a-zA-z0-9]','',text)
    cleaned_text = re.sub('[\{\}\[\]\/?,;:|\‘’)*~`!^\-_+<>@\#$%&\\\=\(\'\"\♥\♡\ㅋ\ㅠ\ㅜ\ㄱ\ㅎ\ㄲ\ㅡ]','',cleaned_text)
    return cleaned_text

# 일단 영어나 숫자, 특수문자는 빼고 생각해봅시다 우리.
text_list = list(map(lambda x :Okt().normalize(clean_text(x)).replace('  ',' ').replace('\n',''), text_list))

 

형태소 처리기를 선언하고, vocab dict를 만들기 위한 counter를 사용한 작업을 실시한다.

참고로 내장함수만 사용하기 때문에, pandas 같은 좋은 라이브러리를 쓰지 못해서, sorted를 통해, 추후에 append로 발생할 수 있는 index 꼬임을 방지하고자 한다. (vocab의 index가 text2vec 과 같은 기능으로 사용하기 위함.)

# 형태소는 제가 제일 좋아하는 mecab으로!
mecab = Mecab()
morphs_list = list(map(lambda x:mecab.morphs(x), text_list))

# vocab dict을 만들건데, 일단은 count도 중요할까 싶어서 이렇게 짜봤습니다.
import collections
morphs_dict = collections.Counter()
for doc in morphs_list:
    morphs_dict.update(doc)
morphs_dict = dict(sorted(morphs_dict.items()))
vocab_list = list(morphs_dict.keys())

 

현재 상황만이 미래의 영향을 미치므로, 현재 글자 바로 다음 글자까지만 dict로 유지하며, 확률값을 구해야 할 것이므로, counter를 사용해서 다음 글자 등장에 대한 횟수를 구한다.

(이런 부분들에서 내가 모든 vocab dict를 선언해놓고 사용하는게 아니라, 추후에 N X N 정방을 만들어주기 위해 vocab dict를 count 0으로 추가하는 상황에서 sort가 깨지게 된다.)

# 마르코프 = 현재 상태만이 미래에 영향을 미친다!
markov_dict = collections.defaultdict(list)
for i in range(len(morphs_list)):
    for j in range(len(morphs_list[i])-1):
        markov_dict[morphs_list[i][j]].append(morphs_list[i][j+1]) 

# 확률을 구하기 위한 일단 숫자셈
for key in markov_dict:
    markov_counter = collections.Counter()
    markov_counter.update(markov_dict[key])
    markov_dict[key]=dict(markov_counter)

 

추후에 transition을 만들기 위해 정방을 구하려고, vocab만큼의 child dict을 만들게 하며, dict에 append되므로, vocab_list와 index가 서로 맞지 않게되어, 추후에 list()에서 값을 찾을 수 없게 되므로 전부 sort하여 맞춰준다.

(참고로 transition은 대상 X 타겟 의 N X N 정방행렬이 되므로, 부모가 될 dict의 key도 전부 sort해야한다.)

이부분은 수려하게 짤 수 있을 것도 같은데, 그냥 일단 무지성으로 짰다.

# transition 배열을 나중에 만들기 위해, 없는 vocab에 대해서 0으로 채우고
# transition이 pandas 형태가 아니기 때문에, vocab_list와 1:1 index mapping을 위해서 동일하게 정렬을 해줍니다.
# transition은 dict X dict 정방 형태이므로, key도 value도 전부 order 해줘야 예외가 안생깁니다.
for vocab in vocab_list:
    for markov in markov_dict.keys():
        try:
            markov_dict[markov][vocab] = markov_dict[markov][vocab]
        except KeyError:
            markov_dict[markov][vocab]=0
markov_dict = dict(sorted(markov_dict.items()))
for markov in markov_dict.keys():
    markov_dict[markov] = dict(sorted(markov_dict[markov].items()))

 

transition 정방행렬을 실제로 구하는 부분.

해당 transition을 구하고 꼭 len을 쳐서 N X N이 생성됐음을 확인해봐야한다.

데이터 전처리 등에서 뭔가 잘못되면, key가 제대로 인식 안되서, 빠지는 애들 있을 수도 있다.

# 현재 상태와 곱해서 뭔가 다음에 나올 문자열에 대한 확률을 보고 싶을 수도 있으니까 한번 transition도 만들고
# 현재 상태도 곱해봅시다!
transition = list()
for i in markov_dict.keys():
    transition.append(list(map(lambda x:x/sum(markov_dict[i].values()), markov_dict[i].values())))

 

random을 이용해서 등장한 적이 있는 애들 위주로 다음 문장을 찾아나가며, 결국에 '.'에 당도하면 문장 완성이 종료된다.

만약에 매핑을 잘못하지 않고서야, 혹은 데이터 전처리를 잘못하지 않고서야. 모든 문장은 '.'으로 끝나므로, 여기서 무한루프가 걸린다면 뭔가 잘못한 것이다.

또한, 그래도 자존심은 있어서, weights를 사용해서 그나마 있는 확률들 중에 높은애들을 우선해서 뽑아서, 그나마 문장스럽게 만들어보고자 했다. 해당 기능은 내장함수에 3.6.9버전인가 그 이후에 생겼다고 한다. (이전에는 numpy 썼어야했음...ㅋㅋ)

# 문장은 '.'로 끝난다고 생각하고, 그냥 랜덤으로 선택하면서 문장을 만들어보자
# 뭐 다만 그나마 랜덤으로 선택할때, 좀 많이 나올만한 애들로 선택해볼까?
def make_sentence(input_text):
    import random
    next_text = input_text
    whole_word = input_text
    while next_text!='.':
        random_list = list()
        random_weight = list()
        for i, val in markov_dict[next_text].items():
            if val>0:
                random_list.append(i)
                random_weight.append(val)
        next_text = random.choices(random_list, weights=random_weight)[0]
        whole_word = whole_word + ' ' + next_text
    return whole_word

 

자, 이제 어케 나올까!?

# 결과는?
for _ in range(20):
    print(make_sentence('마르코프'))

마르코프 체인 은 대충 저 위 섹션 에서 관사 상태 만 마르코프 체인 에서 웹 페이지 간 에 적절 한 링크 들 이 다 .

마르코프 체인 입니다 .

마르코프 체인 을 마코프 프로세스 분석 관점 에서 문장 의 홈페이지 이렇게 총 개 의 고객 군 이 고 .

마르코프 체인 도 표현 할 수 있 다 .

마르코프 사슬 을 사용 하 게 된다 .

마르코프 체인 로 변이 확률 값 은 얼마 일 의 합 은 얼마 이런 열 이 모형 은 보다 더 많이 알려진 것 은 어디 있 는 그만큼 줄어들 었 다 .

마르코프 성질 을 거쳐서 생성 되 어 있 는 억 명 의 페이지랭크 는 메모리 리스 프로세스 마코프 프로세스 로 나 의 일과 를 그래프 를 사 마신 인구 가 된다 .

마르코프 체인 을 의미 한다 .

마르코프 체인 를 좀 더 인터넷 으로 수행 되 지만 이러 한 예제 무작위 단어 이전 일정 부분 진행 할 확률 이 온다면 내일 도 관련 이 된다 .

마르코프 체인 위 예 가 된다 .

마르코프 체인 을 수학 스럽 게 되 는 모르 고 종료 상태 에서 다른 상태 에서 관사 상태 로 전환 되 지 않 고 펩시 콜라 인구 중 하나 둘 중 하나 만 만족 할 확률 은 어느 지점 에서 본 키 및 프로세스 로 의 다이어그램 하 게 모델링 할 수 있 는 상태 를 들 도 포 아송 분포 라고 가정 하 는 두 가지 고 펩시 콜라 와 현재 몇 단어 와 펩시 콜라 인구 가 오로지 회 에서 의 기본 적 으로 랜덤 하 에서 가 다음 과 같 다 .

마르코프 체인 에서 가장 권위 있 고 이 되 지만 포 아송 과정 .

마르코프 체인 은 마르코프 모형 에 코카 콜라 를 예측 하 는 다음 과 모델링 하 고 딥 러닝 카테고리 에 넣 어야 할지 와 같 습니다 .

마르코프 사슬 을 예측 하 는 사건 의 일과 를 사 마신 인구 는 였 고 있 었 냐 하 고 주요 단어 를 사 마신다 .

마르코프 성질 을 던집니다 .

마르코프 모형 이 내릴 확률 은 고민 이 올 수 있 고 베르누이 실험 이 기 때문 에 위 에서 키 는 글자 들 이 한 용어 를 확인 하 는 것 입니다 .

마르코프 체인 을 가지 고 딥 러닝 의 조건 이 라고 부르 고 세 개 의 날씨 도 사용 됩니다 .

마르코프 체인 예시 – 구글 페이지 에 코카 콜라 를 자동 완성 응용 프로그램 에 있 는 관사 상태 는 동전 던지 간 에 어떤 관계 가 될 수 있 는 동사 전치사 상태 가 흐릴 확률 은 시간 이 기 전 에 의존 한다는 것 이 로 억 천만 명 이 더 하 면 동전 던지 기 도 합니다 .

마르코프 체인 입니다 별로 이해 가 마르코프 체인 과 모델링 하 면 각 타원 은 음성 인식 과 같이 나타낼 수 도 있 다고 할 수 있 다고 할 수 있 는 으로 가능 한 확률 값 만 의존 한다는 것 이 아래 와 같이 나타낼 수 있 을 발휘 하 기 의 상태 로 나타내 면 모두 나타내 보 자 .

마르코프 체인 으로 수행 되 기 전 세계 에서 독립 적 으로 이 됩니다 .

 

나름 내가 봤던 문장들에서 뽑아서 나오며, 아티클 몇개 안넣었는데도 그런데로 문장처럼 나오긴 나온다..ㅋㅋ

 

이후는 transition에서 행렬곱을 통해, 특정 상태(x)를 주어주고, 확률이 어떻게 나오는지 볼 수 있다.

transition을 전치하는 이유는, 내가 row, col을 내가 생각한것과 반대로 구성해서, 아래와 같이 해야 '마르코프' 다음 값이 나온다.

# 이쯤되면 전이확률 행렬은 어떤 값이 나올지, 누구나 알 수 있을듯.
import numpy as np
x_list = np.array([0 for _ in range(len(transition[0]))])
x_list[vocab_list.index('마르코프')]=1
np_transition = np.array(transition)

# 중요한 사실은 기준을 row로 잡았느냐, col 로 잡느냐 이다.
# 어케 잡느냐에 따라서, 과거/미래 값이 나오게 되니까...!
x_list_t = x_list.reshape(-1,1)
temp = np_transition.transpose()
next_p = np.matmul(temp,x_list_t)

# 뭐가 나왔을까...!?
for i,val in enumerate(next_p.flatten()):
    if val>0:
        print(list(morphs_dict.keys())[i],val)

전이행렬까지 구성할 수 있으면 이제 각 단어의 등장확률을 현재 상태로 주어놓고, 다음에 어떤 값이 나올지 확률적 예측을 진행해볼 수 있으며, 이 과정의 방법으로 새로운 문장을 만드는 것도 가능하다...!!

 

일단 stational 상태나, 발산 등 대각행렬, 미적분에 관련된 내용들은 시간이 된다면 추후에 다룰까 싶다. 일단은 HMM까지 치고나가는게 중요하다는 판단이다. 그래도 연속형 나이브베이즈 분류기 만드는 것에 포함해서 꼭 잊지 않고 다루도록 하겠다.

 

마르코프 체인. 간단하다면 간단한데, 베이즈 분류와 섞여서 고민을 좀 많이했고, 상당히 흥미로웠다.

베이지안과 마르코프. 아래와 같은 역사도 알아놓으면 재밌을 것 같고, 타인에게 설명이 진심이 담기기 위해서는 알아두면 좋은 정보인 것 같긴하다.

https://www.youtube.com/watch?v=GX4Ld2O530w 

 

ETC. 도움 많이 된 아티클 (외에도 엄청 찾아봤는데, 보고 넘어가서 기억안남 ㅠㅠ)

https://twlab.tistory.com/53

[Linear Algebra] Lecture 24 마코브 행렬(Markov Matrix)

https://www.youtube.com/watch?v=RWkHJnFj5rY