Jakie są łańcuchy Markowa? 5 zastosowań Nifty Real World

Być może słyszałeś ten termin “Łańcuch Markowa” wcześniej, ale jeśli nie wziąłeś udziału w kilku zajęciach z teorii prawdopodobieństwa lub algorytmów informatycznych Jak nauczyć się programowania bez stresu Jak nauczyć się programowania bez stresu Być może zdecydowałeś się kontynuować programowanie, czy to w karierze, czy po prostu hobby. Świetny! Ale może zaczynasz czuć się przytłoczony. Nie za dobrze. Oto pomoc w ułatwieniu podróży. , prawdopodobnie nie wiesz, czym one są, jak działają i dlaczego są tak ważne.

Pojęcie łańcucha Markowa to “pod maską” koncepcja, co oznacza, że ​​tak naprawdę nie musisz wiedzieć, jakie są, aby z nich skorzystać. Jednak na pewno możesz skorzystać ze zrozumienia, jak działają. Są proste, ale przydatne na wiele sposobów.

Oto kurs awaryjny - wszystko, co musisz wiedzieć o łańcuchach Markowa skondensowane w jednym, strawnym artykule. Jeśli chcesz zagłębić się jeszcze głębiej, wypróbuj bezpłatny kurs teorii informacji na Khan Academy (i rozważ także inne strony z kursami online. 8 najlepszych stron z darmowymi kursami szkół wyższych w Internecie 8 najlepszych stron z darmowymi kursami szkół wyższych online Zainteresowany dostępem do bezpłatnego poziomu uczelni kursy? Oto niektóre z najlepszych stron, na których można wziąć udział w bezpłatnych kursach online.).

Łańcuchy Markowa 101

Powiedzmy, że chcesz przewidzieć, jaka będzie jutro pogoda. Prawdziwa prognoza - taka, jaką wykonują eksperci meteorologowie. 7 najlepszych darmowych aplikacji pogodowych dla Androida. 7 najlepszych darmowych aplikacji pogodowych dla Androida. Te bezpłatne aplikacje pogodowe pomogą Ci zachować kontrolę nad pogodą na urządzeniu z Androidem. - obejmowałyby setki, a nawet tysiące różnych zmiennych, które ciągle się zmieniają. Systemy pogodowe są niezwykle złożone i niemożliwe do modelowania, przynajmniej dla laików takich jak ty i ja. Ale możemy uprościć problem, używając oszacowań prawdopodobieństwa.

Wyobraź sobie, że masz dostęp do trzydziestoletnich danych pogodowych. Zaczynasz od początku, zauważając, że Dzień 1 był słoneczny. Kontynuujesz, zauważając, że Dzień 2 był również słoneczny, ale Dzień 3 był pochmurny, następnie Dzień 4 był deszczowy, co doprowadziło do burzy w Dniu 5, a następnie słonecznego i czystego nieba w Dniu 6.

Idealnie byłoby, gdybyś był bardziej szczegółowy, wybierając analizę z godziny na godzinę zamiast analizy z dnia na dzień, ale to tylko przykład ilustrujący tę koncepcję, więc trzymaj się mnie!

Robisz to na podstawie całego 30-letniego zestawu danych (który byłby krótszy niż 11 000 dni) i obliczasz prawdopodobieństwa, jaka będzie jutrzejsza pogoda na podstawie dzisiejszej pogody. Na przykład, jeśli dzisiaj jest słonecznie, to:

• 50 procent szans, że jutro znów będzie słonecznie.
• 30 procent szans, że jutro będzie pochmurno.
• 20 procent szans, że jutro będzie padać.

Teraz powtórz to dla wszystkich możliwych warunków pogodowych. Jeśli dzisiaj jest pochmurno, jakie są szanse, że jutro będzie słonecznie, deszczowo, mglisto, burze, gradobicie, tornada itp.? Wkrótce masz cały system prawdopodobieństw, których możesz użyć, aby przewidzieć nie tylko pogodę na jutro, ale także pogodę na następny dzień i na następny dzień.

Stany przejściowe

To jest istota łańcucha Markowa. Masz poszczególne stany (w tym przypadku warunki pogodowe), w których każdy stan może przejść do innych stanów (np. Dni słoneczne mogą przejść w dni pochmurne), a te przejścia są oparte na prawdopodobieństwach. Jeśli chcesz przewidzieć, jaka będzie pogoda w ciągu jednego tygodnia, możesz zbadać różne prawdopodobieństwa w ciągu najbliższych siedmiu dni i zobaczyć, które są najbardziej prawdopodobne. Tak więc Markov “łańcuch”.

Kim jest Markov? Był rosyjskim matematykiem, który wpadł na pomysł, że jedno państwo prowadzi bezpośrednio do innego w oparciu o pewne prawdopodobieństwo, w którym żadne inne czynniki nie wpływają na szansę przejściową. Zasadniczo wynalazł łańcuch Markowa, stąd nazwa.

Jak łańcuchy Markowa są używane w prawdziwym świecie

Wyjaśniając to na marginesie, przyjrzyjmy się niektórym aplikacjom ze świata rzeczywistego, w których się przydają. Możesz być zaskoczony, gdy przez cały czas korzystasz z łańcuchów Markowa, nie wiedząc o tym!

Generowanie nazw

Czy kiedykolwiek brałeś udział w grach stołowych, grach MMORPG, a nawet pisaniu fikcji? Być może cierpiałeś z powodu nazewnictwa swoich postaci (przynajmniej w tym czy innym momencie) - a kiedy po prostu nie mogłeś pomyśleć o nazwie, którą lubisz, prawdopodobnie uciekłeś się do internetowego generatora nazw Utwórz nowy alias z Najlepsze generatory nazw online [Weird & Wonderful Web] Stwórz nowy alias z najlepszymi generatorami nazw online [Weird & Wonderful Web] Twoje imię jest nudne. Na szczęście możesz przejść do trybu online i wybrać nowy alias, korzystając z jednego z niezliczonych generatorów nazw dostępnych w Interneciez. .

Czy zastanawiałeś się kiedyś, jak działały te generatory nazw? Jak się okazuje, wiele z nich używa łańcuchów Markowa, co czyni je jednym z najczęściej używanych rozwiązań. (Istnieją inne algorytmy, które są równie skuteczne, oczywiście!)

Wszystko, czego potrzebujesz, to zbiór listów, w których każda litera zawiera listę potencjalnych liter uzupełniających z prawdopodobieństwem. Na przykład list “M.” ma 60 procent szans na doprowadzenie do listu “ZA” i 40 procent szans na doprowadzenie do listu “ja”. Zrób to dla całej masy innych liter, a następnie uruchom algorytm. Bum, masz imię, które ma sens! (W każdym razie przez większość czasu.)

Google PageRank

Jednym z interesujących implikacji teorii łańcucha Markowa jest to, że wraz ze wzrostem długości łańcucha (tzn. Wzrostem liczby przejść stanu) prawdopodobieństwo, że wylądujesz w określonym stanie, zbiega się z ustaloną liczbą, a prawdopodobieństwo to jest niezależne od tego, gdzie zaczynasz w systemie.

Jest to niezwykle interesujące, gdy myślisz o całej sieci jako systemie Markowa, w którym każda strona jest stanem, a łącza między stronami są przejściami z prawdopodobieństwem. To twierdzenie w zasadzie to mówi bez względu na to, na której stronie zaczynasz, szansa na wylądowanie na określonej stronie X jest stałym prawdopodobieństwem, zakładając, że “długi czas” surfowania.

Źródło zdjęcia: 345Kai za pośrednictwem Wikimedia

I to jest podstawa tego, jak Google klasyfikuje strony internetowe. Rzeczywiście, algorytm PageRank jest zmodyfikowaną (czytaj: bardziej zaawansowaną) formą algorytmu łańcucha Markowa.

Im wyższy “ustalone prawdopodobieństwo” po wejściu na określoną stronę, tym wyższy PageRank. Wynika to z faktu, że wyższe ustalone prawdopodobieństwo oznacza, że ​​strona zawiera wiele linków przychodzących z innych stron - a Google zakłada, że ​​jeśli strona ma wiele linków przychodzących, to musi być cenna. Im więcej linków przychodzących, tym bardziej jest cenny.

Jest to oczywiście bardziej skomplikowane, ale ma sens. Dlaczego witryna taka jak About.com ma wyższy priorytet na stronach wyników wyszukiwania? Ponieważ okazuje się, że użytkownicy często tam docierają, przeglądając sieć. Ciekawe, prawda??

Wpisywanie słów

Telefony komórkowe już od dziesięcioleci mają typowanie predykcyjne, ale czy potrafisz zgadnąć, jak te prognozy są tworzone? Niezależnie od tego, czy korzystasz z Androida (alternatywne opcje klawiatury Co to jest najlepsza alternatywna klawiatura dla Androida? Co to jest najlepsza alternatywna klawiatura dla Androida? Przyjrzymy się niektórym z najlepszych klawiatur w Sklepie Play i przetestujemy je.) lub iOS (alternatywne opcje klawiatury 9 alternatywnych klawiatur iOS, aby ułatwić pisanie lub więcej zabawy 9 alternatywnych klawiatur iOS, aby ułatwić pisanie lub więcej zabawy Gdy Apple wreszcie przestało zachowywać się jak nadopiekuńczy rodzic i wprowadziło klawiatury innych firm, wszyscy poszli na klawiaturę) szalone.), istnieje duża szansa, że ​​twoja wybrana aplikacja korzysta z łańcuchów Markowa.

Dlatego aplikacje klawiatury pytają, czy mogą gromadzić dane dotyczące twoich nawyków pisania. Na przykład w Klawiaturze Google istnieje ustawienie o nazwie Udostępnij fragmenty to prosi “udostępniaj fragmenty tego, co i jak piszesz w aplikacjach Google, aby ulepszyć klawiaturę Google”. Zasadniczo twoje słowa są analizowane i uwzględniane w prawdopodobieństwie łańcucha Markowa w aplikacji.

Dlatego aplikacje klawiatury często zawierają trzy lub więcej opcji, zwykle w kolejności od najbardziej prawdopodobnej do najmniej prawdopodobnej. Nie może wiedzieć na pewno, co chciałeś wpisać dalej, ale jest poprawne częściej niż nie.

Subreddit Simulation

Jeśli nigdy nie korzystałeś z Reddit, zachęcamy do zapoznania się z tym fascynującym eksperymentem o nazwie / r / SubredditSimulator.

Mówiąc najprościej, Subreddit Simulator przejmuje ogromną część WSZYSTKICH komentarzy i tytułów poczynionych w licznych społecznościach Reddit, a następnie analizuje skład każdego zdania słowo po słowie. Korzystając z tych danych, generuje prawdopodobieństwa od słowa do słowa - a następnie wykorzystuje te prawdopodobieństwa do generowania tytułów i komentarzy od zera.

Jedną interesującą warstwą tego eksperymentu jest to, że komentarze i tytuły są kategoryzowane przez społeczność, z której pochodzą dane, więc rodzaje komentarzy i tytułów generowanych przez zestaw danych / r / food są bardzo różne od komentarzy i tytułów generowanych przez / r / zbiór danych piłkarskich.

Najśmieszniejsze - a może najbardziej niepokojące - jest to, że generowane komentarze i tytuły często są nie do odróżnienia od tych, które napisali prawdziwi ludzie. To absolutnie fascynujące.

Czy znasz jakieś inne fajne zastosowania dla łańcuchów Markowa? Masz pytania, na które wciąż musisz odpowiedzieć? Daj nam znać w komentarzu poniżej!