Explained Visually
Victor Powell
tekstin suomentanut Lewis Lehe
Markovin ketjut, jotka on nimetty Andrey Markovin mukaan, ovat matemaattisia systeemejä, jotka hyppäävät yhdestä ”tilasta” (tilanteesta tai arvojen määrästä) toiseen. Jos esimerkiksi tekisit Markovin ketjumallin vauvan käyttäytymisestä, voisit sisällyttää tiloiksi ”leikkimisen”, ”syömisen”, ”nukkumisen” ja ”itkemisen”, jotka yhdessä muiden käyttäytymistapojen kanssa voisivat muodostaa ”tilaavaruuden”: luettelon kaikista mahdollisista tiloista. Lisäksi tila-avaruuden lisäksi Markovin ketju kertoo todennäköisyyden hypätä tai ”siirtyä” yhdestä tilasta mihin tahansa toiseen tilaan – esim, todennäköisyys sille, että parhaillaan leikkivä vauva nukahtaa seuraavan viiden minuutin aikana itkemättä ensin.
Alla on esitetty yksinkertainen, kahden tilan Markovin ketju.
nopeus
Tila-avaruudessamme on kaksi tilaa (A ja B), joten mahdollisia siirtymiä on neljä (ei kaksi, koska tila voi siirtyä takaisin itseensä). Jos olemme tilassa ’A’, voimme siirtyä tilaan ’B’ tai pysyä tilassa ’A’. Jos olemme tilassa ’B’, voimme siirtyä tilaan ’A’ tai pysyä tilassa ’B’. Tässä kahden tilan kaaviossa todennäköisyys siirtyä mistä tahansa tilasta mihin tahansa toiseen tilaan on 0,5.
Vaikka todelliset mallintajat eivät aina piirrä Markovin ketjukaavioita. Sen sijaan he käyttävät ”siirtymämatriisia” siirtymätodennäköisyyksien laskemiseen. Jokainen tila tilaavaruudessa on mukana kerran rivinä ja kerran sarakkeena, ja jokainen matriisin solu kertoo todennäköisyyden siirtyä rivin tilasta sarakkeen tilaan. Matriisissa solut tekevät siis samaa työtä kuin nuolet kaaviossa.
A B
Jos tilaavaruuteen lisätään yksi tila, lisätään yksi rivi ja yksi sarake, jolloin jokaiseen olemassa olevaan sarakkeeseen ja riviin lisätään yksi solu. Tämä tarkoittaa, että solujen määrä kasvaa neliöllisesti, kun lisäämme tiloja Markovin ketjuumme. Näin ollen siirtymämatriisi tulee aika nopeasti tarpeeseen, ellet halua piirtää viidakkovoimistelun Markovin ketjukaaviota.
Yksi Markovin ketjujen käyttötapa on sisällyttää reaalimaailman ilmiöitä tietokonesimulaatioihin. Voimme esimerkiksi haluta tarkistaa, kuinka usein uusi pato tulee ylivuotamaan, mikä riippuu peräkkäisten sadepäivien määrästä. Tämän mallin rakentamiseksi lähdemme liikkeelle seuraavasta sateisten (R) ja aurinkoisten (S) päivien kaavasta:
Yksi tapa simuloida tätä säätä olisi vain sanoa: ”Puolet päivistä on sateisia. Siksi simulaatiossamme jokaisena päivänä on viidenkymmenen prosentin mahdollisuus sateeseen.” Tämä sääntö tuottaisi simulaatiossa seuraavan sekvenssin:
Huomasitko, että yllä oleva sekvenssi ei näytä aivan alkuperäiseltä? Toinen sekvenssi näyttää hyppivän ympäriinsä, kun taas ensimmäinen (todelliset tiedot) näyttää olevan ”tahmea”. Todellisessa datassa, jos on aurinkoista (S) yhtenä päivänä, niin myös seuraava päivä on paljon todennäköisemmin aurinkoinen.
Voidaan minic tätä ”tahmeutta” kahden tilan Markovin ketjulla. Kun Markovin ketju on tilassa ”R”, sillä on 0,9 todennäköisyys pysyä paikallaan ja 0,1 todennäköisyys lähteä tilaan ”S”. Vastaavasti tilassa ”S” on 0,9 todennäköisyys pysyä paikallaan ja 0,1 mahdollisuus siirtyä tilaan ”R”.
Metereologien, ekologien, tietojenkäsittelytieteilijöiden, finanssi-insinöörien ja muiden sellaisten ihmisten käsissä, jotka joutuvat mallintamaan isoja ilmiöitä, Markovin ketjuista voi tulla varsin suuria ja tehokkaita. Esimerkiksi algoritmi, jota Google käyttää hakutulosten järjestyksen määrittämiseen ja jota kutsutaan PageRankiksi, on eräänlainen Markovin ketju.
Yllä olemme lisänneet Markovin ketjujen ”leikkikentän”, jossa voit tehdä omia Markovin ketjujasi pelleilemällä siirtymämatriisin kanssa. Tässä on muutama esimerkkinä: ex1, ex2, ex3 tai luo yksi satunnaisesti. Siirtymämatriisiteksti muuttuu punaiseksi, jos annettu matriisi ei ole kelvollinen siirtymämatriisi. Siirtymämatriisin rivien yhteismäärän on oltava 1. Rivejä on myös oltava yhtä monta kuin sarakkeita.
Voit käyttää myös koko ruudun versiota osoitteessa setosa.io/markov
.