예제가있는 마르코프 체인 소개 – 파이썬을 사용한 마르코프 체인

Introduction To Markov Chains에 대한이 기사는 Markov chain의 기본 아이디어와 Python을 사용하여 모델링하는 방법을 이해하는 데 도움이됩니다.

마르코프 체인 소개 :

Google이 웹 페이지의 순위를 매기는 방법에 대해 궁금한 적이 있습니까? 연구를 마쳤다면 Markov 체인의 아이디어를 기반으로하는 PageRank 알고리즘을 사용한다는 것을 알아야합니다. Introduction To Markov Chains에 대한이 기사는 Markov 체인의 기본 아이디어와 실제 문제에 대한 솔루션으로 모델링 할 수있는 방법을 이해하는 데 도움이됩니다.

다룰 주제 목록은 다음과 같습니다. 이 블로그에서 :





  1. 마르코프 체인이란?
  2. 마르코프 재산이란 무엇입니까?
  3. 예를 들어 마르코프 사슬 이해하기
  4. 전환 매트릭스 란 무엇입니까?
  5. 파이썬의 마르코프 체인
  6. 마르코프 체인 애플리케이션

Python을 사용한 데이터 과학 및 기계 학습에 대한 심층적 인 지식을 얻으려면 실시간으로 등록 할 수 있습니다. 24/7 지원 및 평생 액세스를 제공하는 Edureka

마르코프 체인이란?

Andrey Markov는 1906 년에 처음으로 Markov 체인을 소개했습니다. 그는 Markov 체인을 다음과 같이 설명했습니다.



특정 가정과 명확한 확률 규칙에 따라 한 상태에서 다른 상태로 전환되는 확률 변수를 포함하는 확률 적 프로세스입니다.

이 무작위 변수는 다음과 같은 중요한 수학적 속성을 기반으로 한 상태에서 다른 상태로 전환됩니다. 마르코프 재산.

이것은 우리에게 질문을 던집니다.



마르코프 재산이란 무엇입니까?

Discrete Time Markov Property에 따르면 랜덤 프로세스가 다음 가능한 상태로 전환 될 확률이 계산 된 확률은 현재 상태 및 시간에만 의존하며 그 이전의 일련의 상태와 무관합니다.

무작위 프로세스의 다음 가능한 동작 / 상태가 이전 상태의 시퀀스에 의존하지 않는다는 사실은 Markov 체인을 변수의 현재 상태 / 동작에만 의존하는 메모리없는 프로세스로 렌더링합니다.

이것을 수학적으로 도출해 봅시다.

랜덤 과정을 {Xm, m = 0,1,2, ⋯}이라고합시다.

이 프로세스는 다음과 같은 경우에만 마르코프 체인입니다.

마르코프 체인 공식-마르코프 체인 소개-Edureka

마르코프 체인 – 마르코프 체인 소개 – Edureka

모든 m, j, i, i0, i1, ⋯ im & minus1

유한 수의 상태 (S = {0, 1, 2, ⋯, r})의 경우이를 유한 마르코프 체인이라고합니다.

여기서 P (Xm + 1 = j | Xm = i)는 한 상태에서 다른 상태로 전환 할 전환 확률을 나타냅니다. 여기서는 전환 확률이 시간과 무관하다고 가정합니다.

즉, P (Xm + 1 = j | Xm = i)는 'm'값에 의존하지 않습니다. 따라서 요약 할 수 있습니다.

마르코프 체인 공식 – 마르코프 체인 소개 – Edureka

그래서이 방정식은 마르코프 사슬.

이제 예를 들어 마르코프 사슬이 정확히 무엇인지 이해합시다.

마르코프 체인 예

예제를 제공하기 전에 Markov 모델이 무엇인지 정의 해 보겠습니다.

자바에서 프로그램을 닫는 방법

마르코프 모델이란?

Markov 모델은 변수가 Markov 속성을 따르는 방식으로 랜덤 변수를 모델링하는 확률 적 모델입니다.

이제 간단한 예를 들어 Markov Model이 어떻게 작동하는지 이해해 봅시다.

앞서 언급했듯이 Markov 체인은 텍스트 생성 및 자동 완성 응용 프로그램에 사용됩니다. 이 예에서는 예제 (무작위) 문장을 살펴보고 Markov 체인을 사용하여 어떻게 모델링 할 수 있는지 살펴 보겠습니다.

마르코프 체인의 예 – 마르코프 체인 소개 – Edureka

위의 문장은 우리의 예입니다.별로 말이되지 않는다는 것을 알고 있습니다 (그럴 필요는 없음). 임의의 단어를 포함하는 문장입니다. 여기서 :

  1. 문장에서 고유 한 단어를 나타냅니다. 즉, 5 개의 키 (하나, 둘, 우박, 행복, 에듀 레카)

  2. 토큰 총 단어 수, 즉 8 개의 토큰을 나타냅니다.

계속해서 이러한 단어의 발생 빈도를 이해해야합니다. 아래 다이어그램은 해당 단어의 빈도를 나타내는 숫자와 함께 각 단어를 보여줍니다.

키와 주파수 – Markov Chains 소개 – Edureka

여기서 왼쪽 열은 키를 나타내고 오른쪽 열은 주파수를 나타냅니다.

위의 표에서 'edureka'키가 다른 키보다 4 배 더 많이 나온다는 결론을 내릴 수 있습니다. 특정 시점에 어떤 단어가 나올지 예측하는 데 도움이 될 수 있으므로 그러한 정보를 추론하는 것이 중요합니다. 예문의 다음 단어를 추측하면 발생 확률이 가장 높은 'edureka'를 사용합니다.

확률에 대해 말하자면, 알아야 할 또 다른 척도는 가중 분포.

우리의 경우 'edureka'의 가중치 분포는 총 8 개 토큰 중 빈도가 4이므로 50 % (4/8)입니다. 나머지 키 (하나, 둘, 우박, 행복)는 모두 1/8 확률로 발생합니다 (& asymp 13 %).

가중치 분포를 이해하고 특정 단어가 다른 단어보다 더 자주 발생하는 방법에 대한 아이디어를 얻었으므로 다음 부분으로 넘어갈 수 있습니다.

마르코프 체인 이해 – 마르코프 체인 소개 – Edureka

위 그림에서 문장의 시작과 끝을 나타내는 두 개의 추가 단어를 추가했습니다. 아래 섹션에서이 작업을 수행 한 이유를 이해할 수 있습니다.

이제 이러한 키에 대한 빈도도 지정하겠습니다.

Java에서 이진 문자열을 10 진수로 변환하는 방법

업데이트 된 키 및 주파수 – Markov Chains 소개 – Edureka

이제 Markov 모델을 만들어 보겠습니다. 앞서 언급했듯이 Markov 모델은 이러한 변수의 미래 상태가 과거 상태가 아닌 현재 상태에만 의존하는 방식으로 특정 상태에서 랜덤 변수를 모델링하는 데 사용됩니다.

따라서 기본적으로 Markov 모델에서 다음 상태를 예측하려면 현재 상태 만 고려해야합니다.

아래 다이어그램에서 문장의 각 토큰이 다른 토큰으로 이어지는 방식을 볼 수 있습니다. 이것은 미래 상태 (다음 토큰)가 현재 상태 (현재 토큰)를 기반으로 함을 보여줍니다. 그래서 이것은 마르코프 모델에서 가장 기본적인 규칙입니다.

아래 다이어그램은 쌍의 각 토큰이 동일한 쌍의 다른 토큰으로 연결되는 토큰 쌍이 있음을 보여줍니다.

마르코프 체인 쌍 – 마르코프 체인 소개 – Edureka

아래 다이어그램에서는 페어링 할 수있는 다음 가능한 토큰 배열과 함께 각 키를 보여주는 구조적 표현을 만들었습니다.

마르코프 체인 쌍의 배열 – 마르코프 체인 소개 – Edureka

이 예를 요약하려면 위의 예에서 본 키 및 토큰 배열을 사용하여 문장을 구성해야하는 시나리오를 고려하십시오. 이 예제를 실행하기 전에 또 다른 중요한 점은 두 가지 초기 측정 값을 지정해야한다는 것입니다.

  1. 초기 확률 분포 (즉, 시간 = 0에서의 시작 상태, (‘시작’키))

  2. 한 상태에서 다른 상태로 점프 할 수있는 전환 확률 (이 경우 한 토큰에서 다른 상태로 전환 할 확률)

처음에 가중치 분포를 정의 했으므로 확률과 초기 상태가 있으므로 이제 예를 들어 보겠습니다.

  • 따라서 초기 토큰으로 시작하려면 [시작]

  • 다음으로 가능한 토큰은 하나뿐입니다.

  • 현재 문장에는 한 단어 만 있습니다.

  • 이 토큰에서 가능한 다음 토큰은 [edureka]입니다.

  • 문장이‘한 에듀 레카’로 업데이트됩니다.

  • [edureka]에서 다음 토큰 중 하나로 이동할 수 있습니다. [two, hail, happy, end]

  • 'two'가 선택 될 확률은 25 %입니다. 그러면 원래 문장이 형성 될 수 있습니다 (하나는 edureka 2는 edureka hail edureka happy edureka). 그러나 'end'를 선택하면 프로세스가 중지되고 결국 'one edureka'라는 새로운 문장이 생성됩니다.

Markov 모델을 빌드하고이를 통해 테스트 케이스를 실행했기 때문에 자신을 칭찬하십시오. 위의 예를 요약하기 위해 기본적으로 현재 상태 (현재 단어)를 사용하여 다음 상태 (다음 단어)를 결정했습니다. 이것이 바로 마르코프 과정입니다.

변수의 미래 상태가 현재 상태에만 의존하는 방식으로 랜덤 변수가 한 상태에서 다른 상태로 전환되는 확률 적 프로세스입니다.

다음 단계로 이동하여이 예제에 대한 Markov Model을 그려 보겠습니다.

상태 전환 다이어그램 – Markov Chains 소개 – Edureka

위의 그림은 상태 전이 다이어그램으로 알려져 있습니다. 아래 섹션에서 이에 대해 자세히 설명하겠습니다. 지금은이 다이어그램이 한 상태에서 다른 상태로의 전환과 확률을 보여 준다는 점을 기억하세요.

그림의 각 타원은 키를 나타내며 화살표는 그 뒤에 올 수있는 가능한 키를 향합니다. 또한 화살표의 가중치는 확률 또는 각 상태에서 /로 전이의 가중 분포.

이것이 Markov Model의 작동 방식에 관한 것입니다. 이제 Markov Process에서 몇 가지 중요한 용어를 이해해 보겠습니다.

전환 확률 매트릭스 란 무엇입니까?

위 섹션에서는 간단한 예를 통해 Markov Model의 작동에 대해 논의했습니다. 이제 Markov Process의 수학적 용어를 이해하겠습니다.

Markov Process에서 우리는 한 상태에서 다른 상태로의 전이 확률을 나타내는 행렬을 사용합니다. 이 행렬을 전환 또는 확률 행렬이라고합니다. 일반적으로 P로 표시됩니다.

전환 매트릭스 – Markov Chains 소개 – Edureka

모든 값에 대한 pij & ge0 및 'i'는 다음과 같습니다.

전환 매트릭스 공식 – Markov Chains 소개 – Edureka

설명하겠습니다. 현재 상태가 'i'라고 가정하면 다음 또는 다가오는 상태가 잠재적 상태 중 하나 여야합니다. 따라서 k의 모든 값을 합산하는 동안 하나를 얻어야합니다.

상태 전이 다이어그램이란?

Markov 모델은 State Transition Diagram으로 표현됩니다. 이 다이어그램은 마르코프 체인의 여러 상태 간의 전환을 보여줍니다. 예를 들어 전환 매트릭스와 상태 전환 매트릭스를 이해해 봅시다.

전환 매트릭스 예

세 가지 상태 1, 2 및 3과 다음 확률을 가진 Markov 체인을 고려하십시오.

전환 매트릭스 예 – Markov Chains 소개 – Edureka

상태 전이 다이어그램 예 – Markov Chains 소개 – Edureka

위의 다이어그램은 Markov 체인의 상태 전이 다이어그램을 나타냅니다. 여기서 1,2 및 3은 가능한 세 가지 상태이며 한 상태에서 다른 상태를 가리키는 화살표는 전환 확률 pij를 나타냅니다. pij = 0이면 상태 'i'와 상태 'j'사이에 전환이 없음을 의미합니다.

이제 우리 Markov 체인의 수학과 논리를 알고, 간단한 데모를 실행하고 Markov 체인을 사용할 수있는 위치를 이해하겠습니다.

파이썬의 마르코프 체인

이 데모를 실행하기 위해 저는 Python을 사용할 것이므로 Python을 모르는 경우 다음 블로그를 살펴볼 수 있습니다.

  1. 처음부터 Python 3를 배우는 방법 – 초보자 가이드

이제 코딩을 시작하겠습니다!

마르코프 체인 텍스트 생성기

문제 설명: Markov Property를 적용하고 Donald Trump 음성 데이터 세트를 연구하여 텍스트 시뮬레이션을 생성 할 수있는 Markov Model을 생성합니다.

데이터 세트 설명 : 텍스트 파일에는 2016 년 도널드 트럼프의 연설 목록이 포함되어 있습니다.

논리: Markov Property를 적용하여 연설에 사용 된 각 단어를 고려하여 Donald의 Trump의 연설을 생성하고 각 단어에 대해 다음에 사용할 단어의 사전을 만듭니다.

자바 코드 컴파일 방법

1 단계 : 필요한 패키지 가져 오기

numpy를 np로 가져 오기

2 단계 : 데이터 세트 읽기

trump = open ( 'C : //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () # 데이터 표시 print (trump) SPEECH 1 ... 감사합니다 너 정말. 너무 좋아요. 그는 훌륭한 사람이 아닙니다. 그는 공정한 언론을 얻지 못합니다. 공정하지 않습니다. 그리고 저는 여러분에게 제가 여기 있고 매우 강하게 여기에 있다고 말해야합니다. 저는 스티브 킹에 대해 큰 존경심을 갖고 있고 시민 연합, 데이비드 및 모든 사람에게도 마찬가지로 큰 존경심을 가지고 있으며 티 파티에 대해 엄청나게 존경하기 때문입니다. 또한 아이오와 사람들도 마찬가지입니다. 그들은 공통점이 있습니다. 열심히 일하는 사람들 ....

3 단계 : 데이터 세트를 개별 단어로 분할

corpus = trump.split () # 말뭉치 표시 print (corpus) 'powerful,', 'but', 'not', 'powerful', 'like', 'us.', 'Iran', 'has', ' 시드 ','테러 ', ...

다음으로, 연설에서 서로 다른 단어 쌍을 생성하는 함수를 만듭니다. 공간을 절약하기 위해 생성기 객체를 사용합니다.

4 단계 : 키 쌍과 후속 단어 만들기

def make_pairs (corpus) : for i in range (len (corpus)-1) : yield (corpus [i], corpus [i + 1]) pairs = make_pairs (corpus)

다음으로 빈 사전을 초기화하여 단어 쌍을 저장해 보겠습니다.

쌍의 첫 단어가 이미 사전의 키인 경우 단어 다음에 나오는 단어 목록에 다음 잠재적 단어를 추가하면됩니다. 그러나 단어가 키가 아닌 경우 사전에 새 항목을 만들고 쌍의 첫 번째 단어와 동일한 키를 할당합니다.

5 단계 : 사전 추가

word_dict = {} for word_1, word_2 in pair : if word_1 in word_dict.keys () : word_dict [word_1] .append (word_2) else : word_dict [word_1] = [word_2]

다음으로 말뭉치에서 무작위로 단어를 선택하여 Markov 체인을 시작합니다.

6 단계 : Markov 모델 구축

# 첫 번째 단어를 무작위로 선택 first_word = np.random.choice (corpus) # 선택한 단어가 문장 사이에서 가져 오지 않도록 첫 번째 단어를 대문자로 선택하는 동안 first_word.islower () : # 체인 시작 선택한 단어 체인 = [first_word] # 자극 된 단어 수 초기화 n_words = 20

첫 번째 단어 다음에, 체인의 각 단어는 트럼프의 라이브 연설에서 특정 단어를 따르는 단어 목록에서 무작위로 샘플링됩니다. 이는 아래 코드 스 니펫에 나와 있습니다.

범위 (n_words)에있는 i의 경우 : chain.append (np.random.choice (word_dict [chain [-1]]))

7 단계 : 예측

마지막으로 자극 된 텍스트를 표시하겠습니다.

#Join은 체인을 문자열로 반환합니다. print ( ''.join (chain)) 믿을 수없는 사람들의 수입니다. 그리고 Hillary Clinton은 우리 직원을 가지고 있으며 훌륭한 직업을 가지고 있습니다. 그리고 우리는 오바마를 이기지 않을 것입니다

그래서 이것은 트럼프의 연설을 고려하여 얻은 텍스트입니다. 별로 말이되지 않을 수도 있지만 Markov 체인을 사용하여 텍스트를 자동으로 생성하는 방법을 이해하는 것으로 충분합니다.

이제 더 많은 응용 프로그램을 살펴 보겠습니다. 마르코프 체인과 실제 문제를 해결하는 데 사용되는 방법.

마르코프 체인 애플리케이션

다음은 Markov 체인의 실제 응용 프로그램 목록입니다.

  1. Google PageRank : 전체 웹은 Markov 모델로 생각할 수 있습니다. 여기서 모든 웹 페이지는 상태가 될 수 있으며 이러한 페이지 간의 링크 또는 참조는 확률이있는 전환으로 간주 될 수 있습니다. 따라서 기본적으로 어떤 웹 페이지에서 서핑을 시작하는지에 관계없이 특정 웹 페이지에 도달 할 확률은 고정 된 확률입니다.

  2. 단어 예측 입력 : 마르코프 체인은 다가오는 단어를 예측하는 데 사용되는 것으로 알려져 있습니다. 자동 완성 및 제안에도 사용할 수 있습니다.

  3. Subreddit 시뮬레이션 : 확실히 당신은 Reddit을 만났고 그들의 스레드 또는 하위 레딧 중 하나에서 상호 작용했습니다. Reddit은 그룹 전체에서 개최되는 모든 댓글과 토론이 포함 된 엄청난 양의 데이터를 소비하는 subreddit 시뮬레이터를 사용합니다. Markov 체인을 사용함으로써 시뮬레이터는 단어 대 단어 확률을 생성하여 댓글과 주제를 생성합니다.

  4. 텍스트 생성기 : Markov 체인은 더미 텍스트를 생성하거나 큰 에세이를 생성하고 연설을 컴파일하는 데 가장 일반적으로 사용됩니다. 웹에서 볼 수있는 이름 생성기에서도 사용됩니다.

이제 Markov Chains를 사용하여 실제 문제를 해결하는 방법을 알았으므로 자세한 내용을 알고 싶으 실 것입니다. 다음은 다른 통계 개념을 시작하는 데 도움이되는 블로그 목록입니다.

이것으로 Markov Chains 소개 블로그를 마칩니다. 이 주제와 관련하여 질문이 있으시면 아래에 의견을 남겨 주시면 연락 드리겠습니다.

최신 기술에 대한 더 많은 블로그를 계속 지켜봐주십시오.

데이터 과학에서 온라인 구조화 된 교육을 찾고 있다면, edureka! 특별히 선별 된 통계, 데이터 랭 글링, 탐색 데이터 분석, K- 평균 클러스터링, 의사 결정 트리, 랜덤 포레스트, Naive Bayes와 같은 머신 러닝 알고리즘에 대한 전문 지식을 얻을 수 있도록 도와주는 프로그램입니다. 시계열, 텍스트 마이닝의 개념과 딥 러닝에 대한 소개도 배우게됩니다. 이 과정의 새로운 배치가 곧 시작됩니다 !!