Introducció a les cadenes Markov:
Us heu preguntat mai com Google classifica les pàgines web? Si heu fet la vostra investigació, heu de saber que utilitza l’algorisme PageRank que es basa en la idea de les cadenes de Markov. Aquest article sobre Introducció a les cadenes Markov us ajudarà a entendre la idea bàsica que hi ha darrere de les cadenes Markov i com es poden modelar com a solució a problemes del món real.
Aquí teniu una llista de temes que es tractaran en aquest bloc:
- Què és una cadena de Markov?
- Què és la propietat Markov?
- Comprendre les cadenes de Markov amb un exemple
- Què és una matriu de transició?
- Cadena Markov a Python
- Aplicacions de la cadena Markov
Per obtenir coneixements en profunditat sobre ciència de dades i aprenentatge automàtic mitjançant Python, podeu inscriure-us a la sessió en directe per Edureka amb assistència les 24 hores del dia, els 7 dies de la setmana i accés permanent.
Què és una cadena de Markov?
Andrey Markov va introduir per primera vegada les cadenes Markov l'any 1906. Va explicar les cadenes Markov com:
Un procés estocàstic que conté variables aleatòries, que transiten d’un estat a un altre en funció de certs supòsits i regles probabilístiques definides.
Aquests aleatoris variables de transició d'un estat a l'altre, basades en una important propietat matemàtica anomenada Propietat de Markov.
Això ens porta a la pregunta:
Què és la propietat Markov?
La propietat Markov de temps discret afirma que la probabilitat calculada d’un procés aleatori que passi al següent estat possible només depèn de l’estat i el temps actuals i és independent de la sèrie d’estats que l’han precedit.
El fet que la següent possible acció / estat d'un procés aleatori no depengui de la seqüència d'estats anteriors, fa que les cadenes de Markov siguin un procés sense memòria que només depèn de l'estat / acció actual d'una variable.
Derivem això matemàticament:
Sigui el procés aleatori {Xm, m = 0,1,2, ⋯}.
Aquest procés és una cadena de Markov només si,
Cadena Markov - Introducció a les cadenes Markov - Edureka
per a tots els m, j, i, i0, i1, ⋯ im & min1
Per a un nombre finit d'estats, S = {0, 1, 2, ⋯, r}, això s'anomena cadena finita de Markov.
P (Xm + 1 = j | Xm = i) aquí representa les probabilitats de transició a la transició d’un estat a l’altre. En aquest cas, suposem que les probabilitats de transició són independents del temps.
El que significa que P (Xm + 1 = j | Xm = i) no depèn del valor de ‘m’. Per tant, podem resumir,
Fórmula de la cadena Markov - Introducció a les cadenes Markov - Edureka
Per tant, aquesta equació representa la cadena Markov.
Ara entenem què són exactament les cadenes Markov amb un exemple.
Exemple de la cadena Markov
Abans de donar-vos un exemple, definim què és un model Markov:
Què és un model Markov?
Un model de Markov és un model estocàstic que modela variables aleatòries de manera que les variables segueixin la propietat de Markov.
Ara entenem com funciona un model Markov amb un exemple senzill.
Com es va esmentar anteriorment, les cadenes Markov s’utilitzen en aplicacions de generació de text i autocompletar. Per a aquest exemple, veurem una frase (aleatòria) d’exemple i veurem com es pot modelar utilitzant cadenes de Markov.
Exemple de la cadena Markov - Introducció a les cadenes Markov - Edureka
La frase anterior és el nostre exemple, sé que no té gaire sentit (no cal), és una frase que conté paraules aleatòries, en què:
Claus indica les paraules úniques de la frase, és a dir, 5 tecles (una, dues, calamarsa, feliç, edureka)
Fitxes indica el nombre total de paraules, és a dir, 8 fitxes.
Per avançar, hem d’entendre la freqüència d’aparició d’aquestes paraules; el diagrama següent mostra cada paraula juntament amb un número que denota la freqüència d’aquesta paraula.
Claus i freqüències - Introducció a les cadenes Markov - Edureka
Per tant, la columna esquerra aquí indica les tecles i la columna dreta indica les freqüències.
A la taula anterior, podem concloure que la tecla 'edureka' surt quatre vegades més que qualsevol altra tecla. És important inferir aquesta informació perquè ens pot ajudar a predir quina paraula pot aparèixer en un moment concret del temps. Si suposés una suposició sobre la següent paraula de la frase d’exemple, aniria amb ‘edureka’, ja que té la probabilitat més alta d’aparició.
Parlant de probabilitat, cal tenir en compte una altra mesura distribucions ponderades.
En el nostre cas, la distribució ponderada per a ‘edureka’ és del 50% (4/8) perquè la seva freqüència és de 4, del total de 8 fitxes. La resta de tecles (una, dues, calamarsa, feliç) tenen una probabilitat 1/8 de produir-se (& asymp 13%).
Ara que tenim una comprensió de la distribució ponderada i una idea de com les paraules específiques es produeixen amb més freqüència que altres, podem continuar amb la següent part.
Comprensió de les cadenes Markov - Introducció a les cadenes Markov - Edureka
A la figura anterior, he afegit dues paraules addicionals que denoten l’inici i el final de la frase; entendreu per què ho he fet a la secció següent.
Ara assignem també la freqüència d’aquestes claus:
Claus i freqüències actualitzades - Introducció a les cadenes Markov - Edureka
Ara creem un model Markov. Com s'ha esmentat anteriorment, un model de Markov s'utilitza per modelar variables aleatòries en un estat concret de manera que els estats futurs d'aquestes variables depenguin únicament del seu estat actual i no dels seus estats passats.
Així, bàsicament, en un model de Markov, per predir el següent estat, només hem de considerar l’estat actual.
Al diagrama següent, podeu veure com cada testimoni de la nostra frase condueix a un altre. Això mostra que l’estat futur (testimoni següent) es basa en l’estat actual (testimoni actual). Per tant, aquesta és la regla més bàsica del model Markov.
El diagrama següent mostra que hi ha parells de fitxes on cada fitxa del parell condueix a l’altra del mateix parell.
Parelles de cadenes Markov - Introducció a les cadenes Markov - Edureka
Al diagrama següent, he creat una representació estructural que mostra cada clau amb un conjunt de següents fitxes possibles amb què es pot emparellar.
com establir classpath a Java
Una sèrie de parells de cadenes Markov - Introducció a les cadenes Markov - Edureka
Per resumir aquest exemple, tingueu en compte un escenari en què haureu de formar una frase utilitzant la matriu de claus i fitxes que hem vist a l'exemple anterior. Abans d’executar aquest exemple, un altre punt important és que hem d’especificar dues mesures inicials:
Una distribució de probabilitat inicial (és a dir, l’estat d’inici al moment = 0, (tecla ‘Inici’))
Una probabilitat de transició de saltar d’un estat a un altre (en aquest cas, la probabilitat de passar d’un testimoni a l’altre)
Hem definit la distribució ponderada al principi, de manera que tenim les probabilitats i l’estat inicial; ara anem a seguir amb l’exemple.
Per tant, per començar amb el testimoni inicial és [Inici]
A continuació, només tenim un testimoni possible, és a dir, [un]
Actualment, la frase només té una paraula, és a dir, 'una'
A partir d’aquest testimoni, el següent testimoni possible és [edureka]
La frase s’actualitza a ‘one edureka’
Des de [edureka] podem passar a qualsevol de les fitxes següents [dues, gran, feliç, final]
Hi ha un 25% de probabilitats que es triïn 'dos', cosa que possiblement donaria lloc a la formació de la frase original (un edureka dos edureka hail edureka happy edureka). Tanmateix, si es selecciona 'final', el procés s'atura i acabarem generant una nova frase, és a dir, 'una edureka'.
Feu-vos un copet a la part posterior perquè acabeu de construir un model Markov i heu realitzat un cas de prova. Per resumir l'exemple anterior, bàsicament hem utilitzat l'estat actual (paraula actual) per determinar l'estat següent (paraula següent). I això és exactament el que és un procés de Markov.
És un procés estocàstic en el qual les variables aleatòries transiten d’un estat a l’altre de manera que l’estat futur d’una variable només depengui de l’estat actual.
Passem al següent pas i traiem el model Markov per a aquest exemple.
Diagrama de transició estatal - Introducció a les cadenes de Markov - Edureka
La figura anterior es coneix com a diagrama de transició estatal. En parlarem més a la secció següent, de moment només recordeu que aquest diagrama mostra les transicions i la probabilitat d’un estat a un altre.
Fixeu-vos que cada oval de la figura representa una clau i les fletxes estan dirigides cap a les possibles tecles que la poden seguir. A més, els pesos de les fletxes denoten el probabilitat o la distribució ponderada de la transició des de / cap als estats respectius.
Així doncs, es tractava de com funciona el model Markov. Ara intentem comprendre algunes terminologies importants del procés de Markov.
Què és una matriu de probabilitat de transició?
A la secció anterior es va parlar del funcionament d’un model de Markov amb un exemple senzill; ara entenem les terminologies matemàtiques d’un procés de Markov.
En un procés de Markov, fem servir una matriu per representar les probabilitats de transició d’un estat a un altre. Aquesta matriu s’anomena matriu de transició o de probabilitat. Se sol denotar per P.
Matriu de transició - Introducció a les cadenes Markov - Edureka
Nota, pij & ge0 i 'i' per a tots els valors és,
Fórmula de matriu de transició - Introducció a les cadenes Markov - Edureka
Deixeu-me explicar-ho. Suposant que el nostre estat actual és ‘i’, l’estat següent o pròxim ha de ser un dels estats potencials. Per tant, mentre prenem la suma de tots els valors de k, n’hem d’obtenir un.
Què és un diagrama de transició estatal?
Un model de Markov està representat per un diagrama de transició estatal. El diagrama mostra les transicions entre els diferents estats d’una cadena de Markov. Entenem la matriu de transició i la matriu de transició d’estats amb un exemple.
Exemple de matriu de transició
Penseu en una cadena de Markov amb tres estats 1, 2 i 3 i les probabilitats següents:
Exemple de matriu de transició - Introducció a les cadenes de Markov - Edureka
Exemple de diagrama de transició d'estat - Introducció a les cadenes de Markov - Edureka
El diagrama anterior representa el diagrama de transició d'estats de la cadena Markov. Aquí, 1,2 i 3 són els tres estats possibles, i les fletxes que apunten d’un estat a l’altre representen les probabilitats de transició pij. Quan, pij = 0, vol dir que no hi ha transició entre l’estat ‘i’ i l’estat ‘j’.
Ara que nosaltres coneixeu les matemàtiques i la lògica que hi ha darrere de les cadenes de Markov, fem una demostració senzilla i entenem on es poden utilitzar les cadenes de Markov.
Cadena Markov a Python
Per executar aquesta demostració, faré servir Python, de manera que, si no coneixeu Python, podeu consultar els següents blocs:
Ara comencem a codificar!
Generador de text de la cadena Markov
Plantejament del problema: Per aplicar la propietat Markov i crear un model Markov que pugui generar simulacions de text mitjançant l'estudi del conjunt de dades de veu de Donald Trump.
Descripció del conjunt de dades: El fitxer de text conté una llista de discursos pronunciats per Donald Trump el 2016.
java com utilitzar tostring
Lògica: Apliqueu Markov Property per generar el discurs de Donald’s Trump tenint en compte cada paraula que s’utilitza i, per a cada paraula, creeu un diccionari de paraules que s’utilitzen a continuació.
Pas 1: importeu els paquets necessaris
importa numpy com a np
Pas 2: llegiu el conjunt de dades
trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', coding = 'utf8'). read () #display the data print (trump) SPEECH 1 ... Gràcies tu tant. És molt agradable. No és un gran noi? No aconsegueix una premsa justa, no ho aconsegueix. Simplement no és just. I us he de dir que sóc aquí, i molt fort, perquè tinc un gran respecte per Steve King i un gran respecte per Citizens United, David i tothom, i un enorme resecte per la festa del te. A més, també la gent d'Iowa. Tenen alguna cosa en comú. Gent treballadora ....Pas 3: dividiu el conjunt de dades en paraules individuals
corpus = trump.split () #Display the corpus print (corpus) 'powerful,', 'but', 'not', 'powerful', 'like', 'us.', 'Iran', 'has', ' sembrat ',' terror ', ...
A continuació, creeu una funció que generi els diferents parells de paraules dels discursos. Per estalviar espai, utilitzarem un objecte generador.
Pas 4: crear parells de tecles i les paraules de seguiment
def make_pairs (corpus): per a l'interval (len (corpus) - 1): rendiment (corpus [i], corpus [i + 1]) pairs = make_pairs (corpus)
A continuació, inicialitzem un diccionari buit per emmagatzemar els parells de paraules.
En cas que la primera paraula del parell ja sigui una clau del diccionari, només cal afegir la següent paraula potencial a la llista de paraules que segueixen la paraula. Però si la paraula no és una clau, creeu una entrada nova al diccionari i assigneu la clau igual a la primera paraula del parell.
Pas 5: afegir el diccionari
word_dict = {} per a word_1, word_2 per parelles: si word_1 a word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]A continuació, escollim a l'atzar una paraula del corpus que iniciarà la cadena Markov.
Pas 6: Creeu el model Markov
#escolliu la primera paraula aleatòriament first_word = np.random.choice (corpus) # Seleccioneu la primera paraula com a paraula en majúscula de manera que la paraula escollida no es prengui entre una frase mentre first_word.islower (): #Inicieu la cadena de la cadena de paraules escollida = [first_word] # Inicialitza el nombre de paraules estimulades n_words = 20
Després de la primera paraula, cada paraula de la cadena es mostra aleatòriament de la llista de paraules que han seguit aquesta paraula específica en els discursos en directe de Trump. Això es mostra al fragment de codi següent:
per a l'interval (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))
Pas 7: prediccions
Finalment, mostrem el text estimulat.
#Join retorna la cadena com una impressió de cadena ('.join (chain)) El nombre de persones increïbles. I Hillary Clinton, té la nostra gent, i un treball tan fantàstic. I no guanyarem a ObamaPer tant, aquest és el text generat que vaig obtenir tenint en compte el discurs de Trump. Pot ser que no tingui molt de sentit, però és prou bo per fer-vos entendre com es poden utilitzar les cadenes Markov per generar automàticament textos.
Vegem ara algunes aplicacions més de les cadenes de Markov i de com s’utilitzen per resoldre problemes del món real.
Aplicacions de la cadena Markov
Aquí teniu una llista d’aplicacions del món real de les cadenes de Markov:
Google PageRank: Es pot considerar que tot el web és un model de Markov, on cada pàgina web pot ser un estat i els enllaços o referències entre aquestes pàgines es poden considerar transicions amb probabilitats. Per tant, bàsicament, independentment de la pàgina web en què comenceu a navegar, la probabilitat d’arribar a una pàgina web determinada, per exemple, és una probabilitat fixa.
Escriptura de predicció de paraules: Se sap que les cadenes de Markov s’utilitzen per predir les properes paraules. També es poden fer servir per completar automàticament i suggeriments.
Subreddit Simulation: Segur que us heu trobat amb Reddit i heu tingut una interacció en algun dels seus fils o subredits. Reddit utilitza un simulador de subredit que consumeix una gran quantitat de dades que contenen tots els comentaris i discussions realitzats entre els seus grups. En fer ús de les cadenes de Markov, el simulador produeix probabilitats de paraules a paraules, per crear comentaris i temes.
Generador de text: Les cadenes de Markov s’utilitzen amb més freqüència per generar textos ficticis o produir grans assajos i compilar discursos. També s’utilitza als generadors de noms que veieu al web.
Ara que ja sabeu resoldre un problema del món real mitjançant les cadenes Markov, estic segur que teniu curiositat per obtenir més informació. Aquí teniu una llista de blocs que us ajudaran a començar amb altres conceptes estadístics:
Amb això, arribem al final d’aquest blog Introducció a les cadenes Markov. Si teniu cap pregunta sobre aquest tema, deixeu un comentari a continuació i us respondrem.
Estigueu atents a més blogs sobre les tendències tecnològiques.
Si esteu buscant formació estructurada en línia en ciències de dades, edureka! compta amb un dispositiu especialment curat programa que us ajuda a obtenir experiència en estadístiques, disputes de dades, anàlisi de dades exploratòries, algorismes d'aprenentatge automàtic com K-Means Clustering, arbres de decisió, Random Forest, Naive Bayes. També aprendreu els conceptes de sèries temporals, mineria de text i una introducció a l’aprenentatge profund. Ben aviat començaran les noves lots d’aquest curs !!