¿Qué son las cadenas de Markov? 5 ingeniosos usos del mundo real

Puede que hayas oído el término “Cadena de markov” antes, pero a menos que haya tomado algunas clases sobre teoría de la probabilidad o algoritmos informáticos Cómo aprender a programar sin todo el estrés Cómo aprender a programar sin todo el estrés Tal vez haya decidido dedicarse a la programación, ya sea para una carrera o simplemente como un pasatiempo. ¡Genial! Pero tal vez estás empezando a sentirte abrumado. No muy bien. Aquí hay ayuda para facilitar su viaje. Lea más, probablemente no sepa qué son, cómo funcionan y por qué son tan importantes..

La noción de una cadena de Markov es una “bajo el capó” concepto, lo que significa que no es necesario saber qué son para poder beneficiarse de ellos. Sin embargo, ciertamente puede beneficiarse de entender cómo funcionan. Son simples pero útiles de muchas maneras..

Así que aquí hay un curso intensivo: todo lo que necesita saber acerca de las cadenas de Markov condensadas en un solo artículo digerible. Si desea profundizar aún más, pruebe el curso gratuito de teoría de la información en Khan Academy (y considere también otros sitios de cursos en línea 8 sitios web impresionantes para tomar cursos universitarios gratuitos en línea 8 sitios web impresionantes para tomar cursos universitarios gratuitos en línea Leer más).

Cadenas de Markov 101

Digamos que quieres predecir cómo será el clima mañana. Una verdadera predicción: el tipo realizado por expertos meteorólogos Las 7 mejores aplicaciones meteorológicas gratuitas para Android Las 7 mejores aplicaciones meteorológicas gratuitas para Android Estas aplicaciones meteorológicas gratuitas lo ayudarán a mantenerse al tanto del clima con su dispositivo Android. Leer más: implicaría cientos, o incluso miles, de variables diferentes que cambian constantemente. Los sistemas meteorológicos son increíblemente complejos e imposibles de modelar, al menos para los laicos como tú y yo. Pero podemos simplificar el problema usando estimaciones de probabilidad.

Imagina que tienes acceso a treinta años de datos meteorológicos. Empiezas por el principio, notando que el día 1 fue soleado. Continúa, observando que el Día 2 también fue soleado, pero el Día 3 estaba nublado, luego el Día 4 fue lluvioso, lo que provocó una tormenta eléctrica en el Día 5, seguido de cielos despejados y soleados en el Día 6.

Lo ideal sería que fueras más granular, optando por un análisis de hora por hora en lugar de un análisis de día por día, pero esto es solo un ejemplo para ilustrar el concepto, así que ten paciencia.!

Usted hace esto a lo largo de todo el conjunto de datos de 30 años (que sería aproximadamente 11,000 días) y calcula las probabilidades de cómo será el clima de mañana según el clima de hoy. Por ejemplo, si hoy está soleado, entonces:

• Una probabilidad del 50 por ciento de que mañana vuelva a estar soleado..
• Una probabilidad del 30 por ciento de que mañana esté nublado..
• Un 20 por ciento de posibilidades de que mañana sea lluvioso..

Ahora repita esto para todas las condiciones climáticas posibles. Si hoy está nublado, ¿cuáles son las posibilidades de que mañana sea soleado, lluvioso, con niebla, tormentas eléctricas, granizadas, tornados, etc.? Muy pronto, tiene un sistema completo de probabilidades que puede usar para predecir no solo el clima de mañana, sino también el clima del día siguiente y el día siguiente..

Estados de transicion

Esta es la esencia de una cadena de Markov.. Tiene estados individuales (en este caso, condiciones climáticas) donde cada estado puede hacer la transición a otros estados (por ejemplo, los días soleados pueden hacer la transición a días nublados) y esas transiciones se basan en probabilidades. Si desea predecir cómo será el clima en una semana, puede explorar las diversas probabilidades en los próximos siete días y ver cuáles son las más probables. Así, un Markov “cadena”.

¿Quién es Markov? Era un matemático ruso que se le ocurrió la idea completa de que un estado conducía directamente a otro estado basado en una cierta probabilidad, donde ningún otro factor influye en la posibilidad de transición. Básicamente, él inventó la cadena de Markov, de ahí el nombre.

Cómo se utilizan las cadenas de Markov en el mundo real

Con la explicación fuera del camino, exploremos algunas de las aplicaciones del mundo real en las que son útiles. Es posible que se sorprenda al descubrir que ha estado utilizando las cadenas de Markov todo este tiempo sin saberlo.!

Generación de nombres

¿Alguna vez ha participado en juegos de mesa, juegos de MMORPG o incluso escritura de ficción? Es posible que haya agonizado por la denominación de sus personajes (al menos en un punto u otro), y cuando parece que no puede pensar en un nombre que le guste, es probable que haya recurrido a un generador de nombres en línea. Los mejores generadores de nombres en línea [Extraña y maravillosa web] Crea un nuevo alias con los mejores generadores de nombres en línea [Extraña y maravillosa web] Tu nombre es aburrido. Afortunadamente, puede conectarse y elegir un nuevo alias utilizando uno de los innumerables generadores de nombres disponibles en Internetz. Lee mas .

¿Alguna vez te has preguntado cómo funcionaban esos generadores de nombres? Como resultado, muchos de ellos usan cadenas de Markov, lo que la convierte en una de las soluciones más utilizadas. (¡Hay otros algoritmos que son igual de efectivos, por supuesto!)

Todo lo que necesita es una colección de cartas donde cada letra tiene una lista de posibles cartas de seguimiento con probabilidades. Así, por ejemplo, la letra. “METRO” Tiene un 60 por ciento de posibilidades de llegar a la carta. “UNA” y un 40 por ciento de probabilidad de llevar a la carta “yo”. Haga esto por un montón de otras letras, luego ejecute el algoritmo. Boom, tienes un nombre que tiene sentido! (La mayor parte del tiempo, de cualquier manera.)

Google PageRank

Una de las implicaciones interesantes de la teoría de la cadena de Markov es que a medida que aumenta la longitud de la cadena (es decir, aumenta el número de transiciones de estado), la probabilidad de aterrizar en un determinado estado converge en un número fijo, y esta probabilidad es independiente de dónde empiezas en el sistema.

Esto es extremadamente interesante cuando piensa en toda la red mundial como un sistema de Markov en el que cada página web es un estado y los enlaces entre páginas web son transiciones con probabilidades. Este teorema básicamente dice que independientemente de la página web en la que comience, su probabilidad de llegar a una determinada página web X es una probabilidad fija, suponiendo un “largo tiempo” de surf.

Y esta es la base de cómo Google clasifica las páginas web. De hecho, el algoritmo PageRank es una forma modificada (leída: más avanzada) del algoritmo de cadena de Markov..

Cuanto mayor sea el “probabilidad fija” de llegar a una determinada página web, mayor es su PageRank. Esto se debe a que una probabilidad fija más alta implica que la página web tiene muchos enlaces entrantes de otras páginas web, y Google asume que si una página web tiene muchos enlaces entrantes, debe ser valiosa. Cuantos más enlaces entrantes, más valioso es.

Es más complicado que eso, por supuesto, pero tiene sentido. ¿Por qué un sitio como About.com obtiene mayor prioridad en las páginas de resultados de búsqueda? Porque resulta que los usuarios tienden a llegar allí mientras navegan por la web. Interesante no lo es?

Escribiendo predicción de palabras

Los teléfonos móviles han tenido una tipificación predictiva desde hace décadas, pero ¿puedes adivinar cómo se hacen esas predicciones? Ya sea que estés usando Android (opciones de teclado alternativo ¿Cuál es el mejor teclado alternativo para Android? ¿Cuál es el mejor teclado alternativo para Android? Miramos algunos de los mejores teclados en Play Store y los ponemos a prueba. Lee Más) o iOS (opciones de teclado alternativas 9 Teclados iOS alternativos para hacer que su escritura sea más fácil o más divertida) 9 Teclados iOS alternativos para hacer que su escritura sea más fácil o más divertida Cuando Apple finalmente dejó de actuar como un padre sobreprotector e introdujo teclados de terceros locos por el teclado. Más información), es muy probable que su aplicación de elección use cadenas de Markov.

Es por esto que las aplicaciones de teclado le preguntan si pueden recopilar datos sobre sus hábitos de escritura. Por ejemplo, en el teclado de Google, hay una configuración llamada Compartir fragmentos que pide a “comparte fragmentos de qué y cómo escribes en las aplicaciones de Google para mejorar el teclado de Google”. En esencia, sus palabras se analizan e incorporan a las probabilidades de la cadena Markov de la aplicación..

Es también por eso que las aplicaciones de teclado a menudo presentan tres o más opciones, generalmente en el orden de más probable a menos probable. No se puede saber con seguridad qué fue lo que quisiste escribir a continuación, pero es correcto la mayoría de las veces.

Simulación Subreddit

Si nunca ha usado Reddit, le recomendamos que al menos revise este experimento fascinante llamado / r / SubredditSimulator.

En pocas palabras, Subreddit Simulator toma una gran parte de TODOS los comentarios y títulos hechos en las numerosas comunidades de Reddit, luego analiza la composición palabra por palabra de cada oración. Usando estos datos, genera probabilidades palabra por palabra, luego utiliza esas probabilidades para generar títulos y comentarios desde cero..

Una capa interesante de este experimento es que los comentarios y títulos se clasifican por la comunidad de la que provienen los datos, por lo que los tipos de comentarios y títulos generados por el conjunto de datos de / r / food son muy diferentes de los comentarios y títulos generados por / r / conjunto de datos de fútbol.

Y la parte más divertida, o quizás la más perturbadora, de todo esto es que los comentarios y títulos generados con frecuencia pueden ser indistinguibles de los hechos por personas reales. Es absolutamente fascinante.

¿Conoces otros usos interesantes para las cadenas de Markov? ¿Tienes alguna pregunta que todavía necesites responder? Háganos saber en un comentario abajo.!

Explorar más sobre: ​​Algoritmos.