Introducción a las cadenas de Markov con ejemplos - Cadenas de Markov con Python

Introducción a las cadenas de Markov:

¿Te has preguntado alguna vez cómo clasifica Google las páginas web? Si ha investigado, debe saber que utiliza el algoritmo PageRank que se basa en la idea de las cadenas de Markov. Este artículo sobre Introducción a las cadenas de Markov lo ayudará a comprender la idea básica detrás de las cadenas de Markov y cómo se pueden modelar como una solución a problemas del mundo real.

Aquí hay una lista de temas que se cubrirán. en este blog:

1. ¿Qué es una cadena de Markov?
2. ¿Qué es la propiedad de Markov?
3. Comprensión de las cadenas de Markov con un ejemplo
4. ¿Qué es una matriz de transición?
5. Cadena de Markov en Python
6. Aplicaciones de la cadena de Markov

Para obtener un conocimiento profundo sobre ciencia de datos y aprendizaje automático con Python, puede inscribirse para de Edureka con soporte 24/7 y acceso de por vida.

¿Qué es una cadena de Markov?

Andrey Markov introdujo por primera vez las cadenas de Markov en el año 1906. Explicó las cadenas de Markov como:

Un proceso estocástico que contiene variables aleatorias, que pasa de un estado a otro dependiendo de ciertos supuestos y reglas probabilísticas definidas.

Estos aleatorios las variables pasan de un estado a otro, basándose en una propiedad matemática importante llamada Propiedad de Markov.

Esto nos lleva a la pregunta:

¿Qué es la propiedad de Markov?

La propiedad de Markov del tiempo discreto establece que la probabilidad calculada de que un proceso aleatorio pase al siguiente estado posible solo depende del estado actual y del tiempo y es independiente de la serie de estados que lo precedieron.

El hecho de que la siguiente acción / estado posible de un proceso aleatorio no dependa de la secuencia de estados anteriores, hace que las cadenas de Markov sean un proceso sin memoria que depende únicamente del estado / acción actual de una variable.

Derivemos esto matemáticamente:

Sea el proceso aleatorio, {Xm, m = 0,1,2, ⋯}.

Este proceso es una cadena de Markov solo si,

Cadena de Markov - Introducción a las cadenas de Markov - Edureka

para todos los m, j, i, i0, i1, ⋯ im & minus1

Para un número finito de estados, S = {0, 1, 2, ⋯, r}, esto se llama cadena de Markov finita.

P (Xm + 1 = j | Xm = i) aquí representa las probabilidades de transición para pasar de un estado a otro. Aquí, asumimos que las probabilidades de transición son independientes del tiempo.

Lo que significa que P (Xm + 1 = j | Xm = i) no depende del valor de 'm'. Por tanto, podemos resumir,

Fórmula de la cadena de Markov - Introducción a las cadenas de Markov - Edureka

Entonces esta ecuación representa la cadena de Markov.

Ahora entendamos qué son exactamente las cadenas de Markov con un ejemplo.

Ejemplo de cadena de Markov

Antes de darle un ejemplo, definamos qué es un modelo de Markov:

¿Qué es un modelo de Markov?

Un modelo de Markov es un modelo estocástico que modela variables aleatorias de tal manera que las variables siguen la propiedad de Markov.

Ahora comprendamos cómo funciona un modelo de Markov con un ejemplo simple.

Como se mencionó anteriormente, las cadenas de Markov se utilizan en aplicaciones de generación de texto y autocompletado. Para este ejemplo, veremos una oración de ejemplo (aleatoria) y veremos cómo se puede modelar mediante el uso de cadenas de Markov.

Ejemplo de cadena de Markov - Introducción a las cadenas de Markov - Edureka

La oración anterior es nuestro ejemplo, sé que no tiene mucho sentido (no es necesario), es una oración que contiene palabras al azar, en las que:

1. Llaves denotar las palabras únicas en la oración, es decir, 5 claves (uno, dos, granizo, feliz, edureka)

2. Tokens denota el número total de palabras, es decir, 8 fichas.

En el futuro, necesitamos comprender la frecuencia de aparición de estas palabras, el siguiente diagrama muestra cada palabra junto con un número que denota la frecuencia de esa palabra.

Claves y frecuencias - Introducción a las cadenas de Markov - Edureka

Entonces, la columna de la izquierda aquí denota las claves y la columna de la derecha denota las frecuencias.

De la tabla anterior, podemos concluir que la clave 'edureka' aparece 4 veces más que cualquier otra clave. Es importante inferir dicha información porque puede ayudarnos a predecir qué palabra podría aparecer en un momento determinado. Si tuviera que adivinar la siguiente palabra en la oración de ejemplo, iría con 'edureka' ya que tiene la mayor probabilidad de que ocurra.

Hablando de probabilidad, otra medida que debe tener en cuenta es distribuciones ponderadas.

En nuestro caso, la distribución ponderada para 'edureka' es 50% (4/8) porque su frecuencia es 4, de un total de 8 tokens. El resto de las claves (una, dos, granizo, feliz) todas tienen 1/8 de probabilidad de ocurrir (& asymp 13%).

Ahora que tenemos una comprensión de la distribución ponderada y una idea de cómo las palabras específicas ocurren con más frecuencia que otras, podemos continuar con la siguiente parte.

Comprensión de las cadenas de Markov - Introducción a las cadenas de Markov - Edureka

En la figura anterior, agregué dos palabras adicionales que denotan el comienzo y el final de la oración; comprenderá por qué hice esto en la sección siguiente.

Ahora asignemos también la frecuencia para estas teclas:

Teclas y frecuencias actualizadas - Introducción a las cadenas de Markov - Edureka

Ahora creemos un modelo de Markov. Como se mencionó anteriormente, un modelo de Markov se usa para modelar variables aleatorias en un estado particular de tal manera que los estados futuros de estas variables dependen únicamente de su estado actual y no de sus estados pasados.

Entonces, básicamente, en un modelo de Markov, para predecir el siguiente estado, solo debemos considerar el estado actual.

En el siguiente diagrama, puede ver cómo cada ficha de nuestra oración conduce a otra. Esto muestra que el estado futuro (siguiente token) se basa en el estado actual (token actual). Entonces esta es la regla más básica en el modelo de Markov.

El siguiente diagrama muestra que hay pares de tokens donde cada token del par conduce al otro del mismo par.

Pares de cadenas de Markov - Introducción a las cadenas de Markov - Edureka

En el siguiente diagrama, he creado una representación estructural que muestra cada clave con una matriz de los siguientes tokens posibles con los que puede emparejarse.

Una variedad de pares de cadenas de Markov - Introducción a las cadenas de Markov - Edureka

Para resumir este ejemplo, considere un escenario en el que tendrá que formar una oración utilizando la matriz de claves y tokens que vimos en el ejemplo anterior. Antes de pasar por este ejemplo, otro punto importante es que necesitamos especificar dos medidas iniciales:

1. Una distribución de probabilidad inicial (es decir, el estado de inicio en el momento = 0, (tecla 'Inicio'))

2. Una probabilidad de transición de saltar de un estado a otro (en este caso, la probabilidad de pasar de un token a otro)

Hemos definido la distribución ponderada al principio, así que tenemos las probabilidades y el estado inicial, ahora sigamos con el ejemplo.

• Entonces, para comenzar con el token inicial es [Inicio]

• A continuación, solo tenemos un token posible, es decir, [uno]

• Actualmente, la oración tiene solo una palabra, es decir, 'una'

• De este token, el siguiente token posible es [edureka]

• La oración se actualiza a 'una edureka'

• Desde [edureka] podemos pasar a cualquiera de las siguientes fichas [dos, granizo, feliz, fin]

• Hay un 25% de probabilidad de que se elija 'dos', lo que posiblemente resultaría en la formación de la oración original (un edureka dos edureka granizo edureka feliz edureka). Sin embargo, si se elige 'fin', el proceso se detiene y terminaremos generando una nueva oración, es decir, 'una edureka'.

Date una palmada en la espalda porque acabas de construir un modelo de Markov y ejecutar un caso de prueba a través de él. Para resumir el ejemplo anterior, básicamente usamos el estado actual (palabra actual) para determinar el estado siguiente (palabra siguiente). Y eso es exactamente lo que es un proceso de Markov.

Es un proceso estocástico en el que las variables aleatorias pasan de un estado a otro de tal manera que el estado futuro de una variable solo depende del estado presente.

Vayamos al siguiente paso y dibujemos el modelo de Markov para este ejemplo.

Diagrama de transición de estado - Introducción a las cadenas de Markov - Edureka

La figura anterior se conoce como Diagrama de transición de estado. Hablaremos más sobre esto en la siguiente sección, por ahora recuerde que este diagrama muestra las transiciones y la probabilidad de un estado a otro.

Observe que cada óvalo de la figura representa una tecla y las flechas están dirigidas hacia las posibles teclas que pueden seguirla. Además, los pesos en las flechas indican la probabilidad o distribución ponderada de transición desde / hacia los estados respectivos.

que es anaconda para python

Así que todo se trataba de cómo funciona el modelo de Markov. Ahora intentemos comprender algunas terminologías importantes del proceso de Markov.

¿Qué es una matriz de probabilidad de transición?

En la sección anterior discutimos el funcionamiento de un modelo de Markov con un ejemplo simple, ahora entendamos la terminología matemática en un proceso de Markov.

En un proceso de Markov, usamos una matriz para representar las probabilidades de transición de un estado a otro. Esta matriz se llama matriz de transición o de probabilidad. Generalmente se denota por P.

Matriz de transición - Introducción a las cadenas de Markov - Edureka

Tenga en cuenta que pij & ge0 y 'i' para todos los valores es,

Fórmula de la matriz de transición - Introducción a las cadenas de Markov - Edureka

Déjame explicarte esto. Suponiendo que nuestro estado actual es 'i', el próximo o próximo estado tiene que ser uno de los estados potenciales. Por lo tanto, tomando la suma de todos los valores de k, debemos obtener uno.

¿Qué es un diagrama de transición de estado?

Un modelo de Markov está representado por un diagrama de transición de estado. El diagrama muestra las transiciones entre los diferentes estados en una cadena de Markov. Entendamos la matriz de transición y la matriz de transición de estado con un ejemplo.

Ejemplo de matriz de transición

Considere una cadena de Markov con tres estados 1, 2 y 3 y las siguientes probabilidades:

Ejemplo de matriz de transición - Introducción a las cadenas de Markov - Edureka

Ejemplo de diagrama de transición de estado - Introducción a las cadenas de Markov - Edureka

El diagrama anterior representa el diagrama de transición de estado para la cadena de Markov. Aquí, 1, 2 y 3 son los tres estados posibles, y las flechas que apuntan de un estado a los otros estados representan las probabilidades de transición pij. Cuando, pij = 0, significa que no hay transición entre el estado 'i' y el estado 'j'.

Ahora que nosotros Conozca las matemáticas y la lógica detrás de las cadenas de Markov, ejecutemos una demostración simple y comprendamos dónde se pueden usar las cadenas de Markov

Cadena de Markov en Python

Para ejecutar esta demostración, usaré Python, por lo que si no conoce Python, puede consultar los siguientes blogs:

2. Cómo aprender Python 3 desde cero: una guía para principiantes

¡Ahora comencemos con la codificación!

Generador de texto en cadena de Markov

Planteamiento del problema: Aplicar la propiedad de Markov y crear un modelo de Markov que pueda generar simulaciones de texto mediante el estudio del conjunto de datos de voz de Donald Trump.

Descripción del conjunto de datos: El archivo de texto contiene una lista de discursos pronunciados por Donald Trump en 2016.

Lógica: Aplique la propiedad de Markov para generar el discurso de Donald Trump considerando cada palabra utilizada en el discurso y para cada palabra, cree un diccionario de palabras que se usarán a continuación.

Paso 1: importar los paquetes requeridos

importar numpy como np

Paso 2: leer el conjunto de datos

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display the data print (trump) SPEECH 1 ... Gracias eres demasiado. Eso es tan agradable. ¿No es un gran tipo? No recibe una prensa justa, no la recibe. Es que no es justo. Y tengo que decirles que estoy aquí, y muy fuertemente aquí, porque tengo un gran respeto por Steve King y también tengo un gran respeto por Citizens United, David y todos, y un gran resentimiento por el Tea Party. Además, también la gente de Iowa. Ellos tienen algo en comun. Personas trabajadoras....

Paso 3: divida el conjunto de datos en palabras individuales

corpus = trump.split () #Muestra el corpus print (corpus) 'poderoso', 'pero', 'no', 'poderoso', 'me gusta', 'nosotros', 'Irán', 'tiene', ' sembrado ',' terror ', ...

A continuación, cree una función que genere los diferentes pares de palabras en los discursos. Para ahorrar espacio, usaremos un objeto generador.

Paso 4: creación de pares de claves y palabras de seguimiento

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

A continuación, inicialicemos un diccionario vacío para almacenar los pares de palabras.

En caso de que la primera palabra del par ya sea una clave en el diccionario, simplemente agregue la siguiente palabra potencial a la lista de palabras que siguen a la palabra. Pero si la palabra no es una clave, cree una nueva entrada en el diccionario y asigne la clave igual a la primera palabra del par.

Paso 5: agregar el diccionario

word_dict = {} para word_1, word_2 en pares: si word_1 en word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

A continuación, elegimos al azar una palabra del corpus, que iniciará la cadena de Markov.

Paso 6: construye el modelo de Markov

# Elija aleatoriamente la primera palabra first_word = np.random.choice (corpus) # Elija la primera palabra como una palabra en mayúscula para que la palabra elegida no se tome entre una oración mientras first_word.islower (): #Inicie la cadena la cadena de palabras seleccionadas = [first_word] #Inicializar el número de palabras estimuladas n_words = 20

Después de la primera palabra, cada palabra en la cadena se muestra al azar de la lista de palabras que han seguido a esa palabra específica en los discursos en vivo de Trump. Esto se muestra en el siguiente fragmento de código:

para i en el rango (n_palabras): chain.append (np.random.choice (word_dict [cadena [-1]]))

Paso 7: predicciones

Finalmente, mostremos el texto estimulado.

#Join devuelve la cadena como una cadena print ('' .join (chain)) La cantidad de personas increíbles. Y Hillary Clinton, tiene nuestra gente y un gran trabajo. Y no derrotaremos a Obama

Así que este es el texto generado que obtuve al considerar el discurso de Trump. Puede que no tenga mucho sentido, pero es lo suficientemente bueno para hacerle comprender cómo se pueden utilizar las cadenas de Markov para generar textos automáticamente.

Ahora veamos algunas aplicaciones más de las cadenas de Markov y cómo se utilizan para resolver problemas del mundo real.

Aplicaciones de la cadena de Markov

A continuación, se muestra una lista de aplicaciones de las cadenas de Markov en el mundo real:

1. PageRank de Google: Se puede pensar en toda la web como un modelo de Markov, donde cada página web puede ser un estado y los enlaces o referencias entre estas páginas pueden considerarse como transiciones con probabilidades. Básicamente, independientemente de la página web en la que comience a navegar, la posibilidad de acceder a una determinada página web, por ejemplo, X es una probabilidad fija.

2. Predicción de palabras escritas: Se sabe que las cadenas de Markov se utilizan para predecir las próximas palabras. También se pueden utilizar para completar automáticamente y en sugerencias.

3. Subreddit Simulation: Seguramente te has encontrado con Reddit y has tenido una interacción en uno de sus hilos o subreddits. Reddit utiliza un simulador de subreddit que consume una gran cantidad de datos que contienen todos los comentarios y discusiones mantenidos en sus grupos. Al hacer uso de cadenas de Markov, el simulador produce probabilidades palabra a palabra para crear comentarios y temas.

4. Generador de texto: Las cadenas de Markov se utilizan con mayor frecuencia para generar textos ficticios o producir ensayos grandes y compilar discursos. También se utiliza en los generadores de nombres que ves en la web.

Ahora que sabe cómo resolver un problema del mundo real mediante el uso de cadenas de Markov, estoy seguro de que tiene curiosidad por saber más. A continuación, se muestra una lista de blogs que lo ayudarán a comenzar con otros conceptos estadísticos:

Con esto, llegamos al final de este blog de Introducción a las cadenas de Markov. Si tiene alguna consulta sobre este tema, deje un comentario a continuación y nos pondremos en contacto con usted.

Estén atentos para más blogs sobre las tecnologías de tendencia.

Si estás buscando formación estructurada online en Data Science, ¡edureka! tiene un curado especialmente programa que le ayuda a adquirir experiencia en estadísticas, ordenación de datos, análisis exploratorio de datos, algoritmos de aprendizaje automático como agrupación de K-medias, árboles de decisión, bosque aleatorio, bayes ingenuos. También aprenderá los conceptos de series temporales, minería de textos y una introducción al aprendizaje profundo. ¡Pronto comenzarán nuevos lotes para este curso!