Wprowadzenie do łańcuchów Markowa z przykładami - łańcuchy Markowa z Pythonem

Wprowadzenie do łańcuchów Markowa:

Czy zastanawiałeś się kiedyś, jak Google ocenia strony internetowe? Jeśli przeprowadziłeś już swoje badania, musisz wiedzieć, że używa algorytmu PageRank, który jest oparty na idei łańcuchów Markowa. Ten artykuł na temat Wprowadzenie do łańcuchów Markowa pomoże ci zrozumieć podstawową ideę stojącą za łańcuchami Markowa i to, jak można je modelować jako rozwiązanie rzeczywistych problemów.

Oto lista tematów, które zostaną omówione na tym blogu:

1. Co to jest łańcuch Markowa?
2. Co to jest własność Markowa?
3. Zrozumienie łańcuchów Markowa na przykładzie
4. Co to jest macierz przejścia?
5. Łańcuch Markowa w Pythonie
6. Aplikacje łańcucha Markowa

Aby uzyskać dogłębną wiedzę na temat nauki o danych i uczenia maszynowego przy użyciu języka Python, możesz zarejestrować się na żywo by Edureka z całodobowym wsparciem i dożywotnim dostępem.

Co to jest łańcuch Markowa?

Andrey Markov po raz pierwszy wprowadził łańcuchy Markowa w roku 1906. Wyjaśnił łańcuchy Markowa jako:

Proces stochastyczny zawierający zmienne losowe, przechodzący z jednego stanu do drugiego w zależności od pewnych założeń i określonych reguł probabilistycznych.

Te losowe zmienne przechodzą z jednego do drugiego stanu na podstawie ważnej właściwości matematycznej zwanej Własność Markowa.

To prowadzi nas do pytania:

Co to jest własność Markowa?

Właściwość Markowa dla czasu dyskretnego stwierdza, że ​​obliczone prawdopodobieństwo przejścia procesu losowego do następnego możliwego stanu zależy tylko od aktualnego stanu i czasu oraz jest niezależne od serii stanów, które go poprzedzały.

Fakt, że następna możliwa akcja / stan procesu losowego nie zależy od sekwencji wcześniejszych stanów, sprawia, że ​​łańcuchy Markowa są procesem pozbawionym pamięci, który zależy wyłącznie od bieżącego stanu / działania zmiennej.

Wyprowadźmy to matematycznie:

Niech losowym procesem będzie {Xm, m = 0,1,2, ⋯}.

Ten proces jest łańcuchem Markowa tylko wtedy, gdy

Łańcuch Markowa - Wprowadzenie do łańcuchów Markowa - Edureka

dla wszystkich m, j, i, i0, i1, ⋯ im & minus1

Dla skończonej liczby stanów, S = {0, 1, 2, ⋯, r}, nazywa się to skończonym łańcuchem Markowa.

P (Xm + 1 = j | Xm = i) tutaj reprezentuje prawdopodobieństwo przejścia z jednego stanu do drugiego. Tutaj zakładamy, że prawdopodobieństwa przejścia są niezależne od czasu.

Co oznacza, że ​​P (Xm + 1 = j | Xm = i) nie zależy od wartości „m”. Dlatego możemy podsumować,

Formuła łańcucha Markowa - Wprowadzenie do łańcuchów Markowa - Edureka

Więc to równanie reprezentuje łańcuch Markowa.

Teraz zrozummy, czym dokładnie są łańcuchy Markowa na przykładzie.

Przykład łańcucha Markowa

Zanim podam przykład, zdefiniujmy, czym jest model Markowa:

Co to jest model Markowa?

Model Markowa to model stochastyczny, który modeluje zmienne losowe w taki sposób, że zmienne są zgodne z własnością Markowa.

Przyjrzyjmy się teraz, jak działa model Markowa na prostym przykładzie.

Jak wspomniano wcześniej, łańcuchy Markowa są używane w aplikacjach do generowania tekstu i automatycznego uzupełniania. W tym przykładzie przyjrzymy się przykładowemu (losowemu) zdaniu i zobaczymy, jak można je modelować za pomocą łańcuchów Markowa.

Przykład łańcucha Markowa - Wprowadzenie do łańcuchów Markowa - Edureka

Powyższe zdanie jest naszym przykładem, wiem, że nie ma większego sensu (nie musi), jest to zdanie zawierające przypadkowe słowa, w których:

1. Klucze oznaczają niepowtarzalne słowa w zdaniu, tj. 5 kluczy (jeden, dwa, hail, happy, edureka)

2. Tokeny oznaczają całkowitą liczbę słów, czyli 8 żetonów.

Idąc dalej, musimy zrozumieć częstotliwość występowania tych słów, poniższy diagram pokazuje każde słowo wraz z liczbą określającą częstotliwość tego słowa.

Klucze i częstotliwości - wprowadzenie do łańcuchów Markowa - Edureka

Zatem lewa kolumna oznacza klawisze, a prawa kolumna - częstotliwości.

Z powyższej tabeli możemy wywnioskować, że klucz „edureka” pojawia się 4x więcej niż jakikolwiek inny klawisz. Wnioskowanie z takich informacji jest ważne, ponieważ może nam pomóc przewidzieć, jakie słowo może się pojawić w określonym momencie. Gdybym miał odgadnąć następne słowo w przykładowym zdaniu, wybrałbym „edureka”, ponieważ ma ono największe prawdopodobieństwo wystąpienia.

Mówiąc o prawdopodobieństwie, inną miarą, o której musisz wiedzieć, jest dystrybucje ważone.

W naszym przypadku ważona dystrybucja dla „edureki” wynosi 50% (4/8), ponieważ jej częstotliwość wynosi 4 z całkowitej liczby 8 tokenów. Pozostałe klucze (jeden, dwa, grad, szczęśliwy) mają 1/8 szansy na wystąpienie (i asymp 13%).

Teraz, gdy rozumiemy rozkład ważony i wiemy, jak określone słowa występują częściej niż inne, możemy przejść do następnej części.

Zrozumienie łańcuchów Markowa - Wprowadzenie do łańcuchów Markowa - Edureka

Na powyższym rysunku dodałem dwa dodatkowe słowa, które oznaczają początek i koniec zdania, zrozumiesz, dlaczego to zrobiłem w poniższej sekcji.

Teraz przypiszmy częstotliwość również tym klawiszom:

Zaktualizowane klucze i częstotliwości - wprowadzenie do łańcuchów Markowa - Edureka

Teraz stwórzmy model Markowa. Jak wspomniano wcześniej, model Markowa służy do modelowania zmiennych losowych w określonym stanie w taki sposób, że przyszłe stany tych zmiennych zależą wyłącznie od ich aktualnego stanu, a nie od ich przeszłych stanów.

Zatem zasadniczo w modelu Markowa, aby przewidzieć następny stan, musimy wziąć pod uwagę tylko stan bieżący.

Na poniższym diagramie możesz zobaczyć, jak każdy token w naszym zdaniu prowadzi do kolejnego. To pokazuje, że przyszły stan (następny token) jest oparty na obecnym stanie (obecny token). Jest to więc najbardziej podstawowa zasada w Modelu Markowa.

Poniższy diagram pokazuje, że istnieją pary żetonów, w których każdy żeton w parze prowadzi do drugiego w tej samej parze.

Pary łańcuchów Markowa - Wprowadzenie do łańcuchów Markowa - Edureka

Na poniższym diagramie utworzyłem reprezentację strukturalną, która pokazuje każdy klucz z tablicą kolejnych możliwych tokenów, z którymi może się połączyć.

Szereg par łańcuchów Markowa - Wprowadzenie do łańcuchów Markowa - Edureka

Podsumowując ten przykład, rozważ scenariusz, w którym będziesz musiał utworzyć zdanie, używając tablicy kluczy i tokenów, które widzieliśmy w powyższym przykładzie. Zanim przejdziemy przez ten przykład, kolejną ważną kwestią jest to, że musimy określić dwie początkowe miary:

1. Początkowy rozkład prawdopodobieństwa (tj. Stan początkowy w czasie = 0, (klawisz „Start”))

2. Prawdopodobieństwo przejścia z jednego stanu do drugiego (w tym przypadku prawdopodobieństwo przejścia z jednego tokena do drugiego)

Rozkład ważony zdefiniowaliśmy na samym początku, więc mamy prawdopodobieństwa i stan początkowy, przejdźmy teraz do przykładu.

• Na początek początkowy token to [Start]

• Następnie mamy tylko jeden możliwy token, tj. [Jeden]

• Obecnie zdanie ma tylko jedno słowo, tj. „Jeden”

• Z tego tokena następny możliwy token to [edureka]

• Zdanie zmieniono na „jedna edureka”

• Z [edureka] możemy przejść do jednego z następujących tokenów [two, hail, happy, end]

• Istnieje 25% szans na wybranie „dwóch”, co może skutkować utworzeniem pierwotnego zdania (jedna edureka dwie edureka hail edureka happy edureka). Jeśli jednak wybierzesz „koniec”, to proces się zatrzyma i skończymy na wygenerowaniu nowego zdania, czyli „jednej edureki”.

Poklep się po plecach, ponieważ po prostu tworzysz model Markowa i przeprowadzasz przez niego przypadek testowy. Podsumowując powyższy przykład, w zasadzie użyliśmy obecnego stanu (obecne słowo) do określenia następnego stanu (następnego słowa). I tym właśnie jest proces Markowa.

Jest to proces stochastyczny, w którym zmienne losowe przechodzą z jednego stanu do drugiego w taki sposób, że przyszły stan zmiennej zależy tylko od stanu obecnego.

Przejdźmy do następnego kroku i narysujmy model Markowa dla tego przykładu.

Diagram przejścia stanów - wprowadzenie do łańcuchów Markowa - Edureka

Powyższy rysunek jest znany jako diagram zmian stanów. Porozmawiamy o tym więcej w poniższej sekcji, na razie pamiętaj tylko, że ten diagram przedstawia przejścia i prawdopodobieństwo z jednego stanu do drugiego.

Zauważ, że każdy owal na rysunku przedstawia klucz, a strzałki są skierowane w stronę możliwych klawiszy, które mogą za nim podążać. Również wagi na strzałkach oznaczają prawdopodobieństwo lub ważony rozkład przejścia z / do odpowiednich stanów.

A więc chodziło tylko o to, jak działa model Markowa. Spróbujmy teraz zrozumieć kilka ważnych terminologii w procesie Markowa.

Co to jest macierz prawdopodobieństwa przejścia?

W powyższej sekcji omówiliśmy działanie modelu Markowa na prostym przykładzie, teraz przyjrzyjmy się terminologii matematycznej w procesie Markowa.

W procesie Markowa używamy macierzy do reprezentowania prawdopodobieństw przejścia z jednego stanu do drugiego. Ta macierz nazywa się macierzą przejścia lub prawdopodobieństwa. Zwykle jest oznaczany przez P.

Macierz przejścia - wprowadzenie do łańcuchów Markowa - Edureka

Uwaga, pij & ge0 i „i” dla wszystkich wartości to:

Formuła macierzy przejścia - Wprowadzenie do łańcuchów Markowa - Edureka

Pozwól mi to wyjaśnić. Zakładając, że nasz obecny stan to „i”, następny lub nadchodzący stan musi być jednym z potencjalnych stanów. Dlatego sumując wszystkie wartości k, musimy otrzymać jeden.

Co to jest diagram przejścia między stanami?

Model Markowa jest reprezentowany przez Diagram Przejścia Stanowego. Diagram pokazuje przejścia między różnymi stanami w łańcuchu Markowa. Rozumiemy macierz przejść i macierz przejść stanów na przykładzie.

Przykład macierzy przejścia

Rozważmy łańcuch Markowa z trzema stanami 1, 2 i 3 oraz z następującymi prawdopodobieństwami:

Przykład macierzy przejścia - wprowadzenie do łańcuchów Markowa - Edureka

Przykład diagramu przejścia stanów - wprowadzenie do łańcuchów Markowa - Edureka

Powyższy diagram przedstawia diagram przejścia stanów dla łańcucha Markowa. Tutaj 1,2 i 3 to trzy możliwe stany, a strzałki wskazujące z jednego stanu do drugiego reprezentują prawdopodobieństwo przejścia pij. Gdy pij = 0, oznacza to, że nie ma przejścia między stanem „i” a stanem „j”.

Teraz, gdy my znać matematykę i logikę stojącą za łańcuchami Markowa, uruchommy proste demo i zrozummy, gdzie można użyć łańcuchów Markowa.

Łańcuch Markowa w Pythonie

Aby uruchomić tę demonstrację, będę używać Pythona, więc jeśli nie znasz Pythona, możesz przejrzeć następujące blogi:

2. Jak uczyć się Pythona 3 od podstaw - przewodnik dla początkujących

A teraz zacznijmy od kodowania!

Generator tekstu łańcucha Markowa

Oświadczenie dotyczące problemu: Aby zastosować właściwość Markowa i utworzyć model Markowa, który może generować symulacje tekstu, analizując zestaw danych mowy Donalda Trumpa.

Opis zbioru danych: Plik tekstowy zawiera listę wystąpień Donalda Trumpa w 2016 roku.

Logika: Zastosuj właściwość Markov, aby wygenerować przemówienie Donalda Trumpa, biorąc pod uwagę każde słowo użyte w mowie i dla każdego słowa utwórz słownik słów, które zostaną użyte jako następne.

Krok 1: Zaimportuj wymagane pakiety

importuj numpy jako np

Krok 2: Przeczytaj zestaw danych

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display the data print (atut) SPEECH 1 ... Dziękuję tak bardzo. To takie miłe. Czy on nie jest świetnym facetem. Nie dostaje uczciwej prasy, nie dostaje tego. To po prostu nie jest sprawiedliwe. Muszę wam powiedzieć, że jestem tutaj i bardzo mocno tutaj, ponieważ mam wielki szacunek dla Steve'a Kinga i mam również wielki szacunek dla Citizens United, Davida i wszystkich, a także ogromną korzyść dla Tea Party. Również mieszkańcy Iowa. Coś ich łączy. Ciężko pracujący ludzie....

Krok 3: Podziel zestaw danych na pojedyncze słowa

corpus = trump.split () #Wyświetl wydruk korpusu (korpus) 'potężny', 'ale', 'nie', 'potężny', 'jak', 'nas', 'Iran', 'ma', ' zasiane ',' terror ', ...

Następnie utwórz funkcję, która generuje różne pary słów w przemówieniach. Aby zaoszczędzić miejsce, użyjemy obiektu generatora.

Krok 4: Tworzenie par kluczy i kolejnych słów

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

Następnie zainicjujmy pusty słownik, aby przechowywać pary słów.

W przypadku, gdy pierwsze słowo w parze jest już kluczem w słowniku, po prostu dodaj następne potencjalne słowo do listy słów występujących po tym słowie. Ale jeśli słowo nie jest kluczem, utwórz nowy wpis w słowniku i przypisz klucz równy pierwszemu słowu w parze.

Krok 5: Dołączanie słownika

word_dict = {} dla słowa_1, słowo_2 parami: jeśli słowo_1 w słowie_dykt.keys (): słowo_dykt [słowo_1] .append (słowo_2) else: słowo_dykt [słowo_1] = [słowo_2]

Następnie losowo wybieramy słowo z korpusu, które rozpocznie łańcuch Markowa.

Krok 6: Zbuduj model Markowa

# losowo wybierz pierwsze słowo first_word = np.random.choice (corpus) # Wybierz pierwsze słowo jako słowo pisane wielką literą, aby wybrane słowo nie zostało wzięte spomiędzy zdania, podczas gdy first_word.islower (): # Rozpocznij łańcuch od łańcuch wybranych słów = [pierwsze_słowie] # Zainicjuj liczbę stymulowanych słów n_words = 20

Po pierwszym słowie każde słowo w łańcuchu jest losowo próbkowane z listy słów, które nastąpiły po tym konkretnym słowie w przemówieniach Trumpa na żywo. Jest to pokazane w poniższym fragmencie kodu:

co ma związek w java

for i in range (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Krok 7: Prognozy

Na koniec wyświetlmy stymulowany tekst.

#Join zwraca łańcuch jako ciąg znaków print (`` .join (łańcuch)) Liczba niesamowitych ludzi. Hillary Clinton ma swoich ludzi i świetną pracę. I nie pokonamy Obamy

Więc to jest tekst wygenerowany, biorąc pod uwagę przemówienie Trumpa. To może nie mieć większego sensu, ale wystarczy, abyś zrozumiał, jak łańcuchy Markowa mogą być używane do automatycznego generowania tekstów.

Spójrzmy teraz na więcej aplikacji łańcuchów Markowa i tego, jak są wykorzystywane do rozwiązywania problemów w świecie rzeczywistym.

Aplikacje łańcucha Markowa

Oto lista rzeczywistych zastosowań łańcuchów Markowa:

1. Google PageRank: Cała sieć może być traktowana jako model Markowa, w którym każda strona internetowa może być stanem, a linki lub odniesienia między tymi stronami można traktować jako przejścia z prawdopodobieństwem. Zasadniczo więc, niezależnie od tego, na której stronie zaczniesz surfować, szansa dotarcia do określonej strony internetowej, powiedzmy, X jest stałym prawdopodobieństwem.

2. Przewidywanie słów na klawiaturze: Wiadomo, że łańcuchy Markowa są używane do przewidywania nadchodzących słów. Można ich również używać w autouzupełnianiu i sugestiach.

3. Symulacja Subreddit: Z pewnością natknąłeś się na Reddita i miałeś interakcję na jednym z ich wątków lub subredditów. Reddit używa symulatora subreddita, który zużywa ogromną ilość danych zawierających wszystkie komentarze i dyskusje prowadzone w ich grupach. Korzystając z łańcuchów Markowa, symulator generuje prawdopodobieństwa słowo w słowo, aby tworzyć komentarze i tematy.

4. Generator tekstu: Łańcuchy Markowa są najczęściej używane do generowania fikcyjnych tekstów lub tworzenia dużych esejów i kompilowania przemówień. Jest również używany w generatorach nazw, które widzisz w Internecie.

Teraz, gdy wiesz, jak rozwiązać rzeczywisty problem za pomocą łańcuchów Markowa, jestem pewien, że chcesz dowiedzieć się więcej. Oto lista blogów, które pomogą Ci zacząć z innymi pojęciami statystycznymi:

W ten sposób dochodzimy do końca bloga Wprowadzenie do łańcuchów Markowa. Jeśli masz jakieś pytania dotyczące tego tematu, zostaw komentarz poniżej, a my skontaktujemy się z Tobą.

Wkrótce pojawi się więcej blogów na temat popularnych technologii.

Jeśli szukasz ustrukturyzowanego szkolenia online z zakresu Data Science, edureka! ma specjalnie wyselekcjonowany program, który pomaga zdobyć wiedzę w zakresie statystyki, Wrangling danych, eksploracyjnej analizy danych, algorytmów uczenia maszynowego, takich jak klastry K-średnich, drzewa decyzyjne, losowy las, naiwne Bayes. Poznasz koncepcje szeregów czasowych, eksplorację tekstu, a także wprowadzenie do głębokiego uczenia się. Wkrótce zaczną się nowe partie tego kursu !!