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

Es posible que hayas escuchado 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 continuar con la programación, ya sea para una carrera o simplemente un pasatiempo. ¡Excelente! Pero tal vez estés empezando a sentirte abrumado. No muy bien. Aquí hay ayuda para facilitar su viaje. , probablemente no sabes qué son, cómo funcionan y por qué son tan importantes.

La noción de una cadena de Markov es un “bajo el capó” concepto, lo que significa que realmente no necesita saber cuáles son para beneficiarse de ellos. Sin embargo, ciertamente puede beneficiarse al comprender cómo funcionan. Son simples pero útiles de muchas maneras..

Así que aquí hay un curso intensivo: todo lo que necesita saber sobre las cadenas de Markov se condensó 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 Los 8 mejores sitios para cursos universitarios gratuitos en línea Los 8 mejores sitios para cursos universitarios gratuitos en línea Interesado en acceder a nivel universitario gratuito Estos son algunos de los mejores sitios para tomar cursos en línea gratuitos.).

Cadenas de Markov 101

Digamos que quieres predecir cómo será el clima mañana. Una verdadera predicción: del tipo realizado por meteorólogos expertos. - implicaría cientos, o incluso miles, de diferentes variables que cambian constantemente. Los sistemas meteorológicos son increíblemente complejos e imposibles de modelar, al menos para legos como tú y yo. Pero podemos simplificar el problema usando estimaciones de probabilidad.

Imagine que tiene acceso a treinta años de datos meteorológicos. Empiezas desde el principio, observando que el día 1 fue soleado. Sigan, notando que el Día 2 también estuvo soleado, pero el Día 3 estuvo nublado, luego el Día 4 estuvo lluvioso, lo que llevó a una tormenta eléctrica el Día 5, seguido de cielos soleados y despejados el Día 6.

Idealmente, sería más granular, optando por un análisis hora por hora en lugar de un análisis diario, pero este es solo un ejemplo para ilustrar el concepto, así que tengan paciencia conmigo!

Usted hace esto durante todo el conjunto de datos de 30 años (que sería apenas de 11,000 días) y calcula las probabilidades de cómo será el clima de mañana en función del clima de hoy. Por ejemplo, si hoy hace sol, 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 estará nublado.
• Una probabilidad del 20 por ciento de que mañana lloverá.

Ahora repita esto para cada condición climática posible. Si hoy está nublado, ¿cuáles son las posibilidades de que mañana esté 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 el clima del día siguiente y el día siguiente..

Estados transitorios

Esta es la esencia de una cadena de Markov.. Tiene estados individuales (en este caso, condiciones climáticas) donde cada estado puede pasar a otros estados (por ejemplo, los días soleados pueden pasar 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. Por lo tanto, un Markov “cadena”.

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

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

Con la explicación fuera del camino, exploremos algunas de las aplicaciones del mundo real donde resultan ú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 has participado en juegos de mesa, juegos MMORPG o incluso en la escritura de ficción? Es posible que haya agonizado por la denominación de sus personajes (al menos en un momento u otro), y cuando parece que no puede pensar en un nombre que le gusta, probablemente recurrió a un generador de nombres en línea Crear un nuevo alias con el Los mejores generadores de nombres en línea [Web extraña y maravillosa] Cree un nuevo alias con los mejores generadores de nombres en línea [Web extraña y maravillosa] Su nombre es aburrido. Afortunadamente, puedes conectarte en línea y elegir un nuevo alias usando uno de los innumerables generadores de nombres disponibles en Internetz. .

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

Todo lo que necesita es una colección de letras donde cada letra tiene una lista de posibles cartas de seguimiento con probabilidades. Entonces, por ejemplo, la carta “METRO” tiene un 60 por ciento de posibilidades de conducir a la carta “UNA” y una probabilidad del 40 por ciento de conducir a la carta “yo”. Haga esto para 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 comienzas en el sistema.

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

Crédito de la imagen: 345Kai a través de Wikimedia

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

Cuanto mayor sea “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, entonces 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 es así??

Mecanografía la predicción de palabras

Los teléfonos móviles han tenido mecanografía predictiva durante décadas, pero ¿puedes adivinar cómo se hacen esas predicciones? Si está utilizando Android (opciones de teclado alternativas ¿Cuál es el mejor teclado alternativo para Android? ¿Cuál es el mejor teclado alternativo para Android? Echamos un vistazo a algunos de los mejores teclados en Play Store y los ponemos a prueba). o iOS (opciones de teclado alternativas 9 teclados iOS alternativos para que escribir sea más fácil o más divertido) 9 teclados iOS alternativos para hacer que escribir sea más fácil o más divertido Cuando Apple finalmente dejó de actuar como un padre sobreprotector e introdujo teclados de terceros, todos usaron teclado- loco), hay una buena posibilidad de que su aplicación de elección use cadenas de Markov.

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

Esa es también la razón por la cual las aplicaciones de teclado a menudo presentan tres o más opciones, generalmente en el orden de más probable a menos probable. No puede saber con certeza lo que quería escribir a continuación, pero es correcto la mayoría de las veces.

Subreddit Simulation

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

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

Una capa interesante de este experimento es que los comentarios y los títulos están clasificados 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 inquietante, 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 geniales para las cadenas de Markov? ¿Tienes alguna pregunta que aún necesite respuesta? Háganos saber en un comentario abajo!