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

Anuncio

Es posible que haya escuchado el término "cadena de Markov" antes, pero a menos que haya tomado algunas clases sobre teoría de probabilidad o algoritmos informáticos Cómo aprender a programar sin todo el estrésQuizás hayas decidido dedicarte a la programación, ya sea para una carrera o simplemente como un pasatiempo. ¡Excelente! Pero tal vez estés empezando a sentirte abrumado. No muy bien. Aquí hay ayuda para facilitar su viaje. Lee mas , probablemente no sepa qué son, cómo funcionan y por qué son tan importantes.

La noción de una cadena de Markov es un concepto "bajo el capó", lo que significa que realmente no necesita saber cuáles son para beneficiarse de ellas. 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 quieres profundizar aún más, prueba el curso gratuito de teoría de la información

en Khan Academy (y considere otros sitios de cursos en línea también Los 8 mejores sitios para cursos universitarios gratuitos en línea¿Interesado en acceder a cursos gratuitos de nivel universitario? Estos son algunos de los mejores sitios para tomar cursos en línea gratuitos. Lee mas ).

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 Las 7 mejores aplicaciones meteorológicas gratuitas para AndroidEstas aplicaciones meteorológicas gratuitas lo ayudarán a estar al tanto del clima con su dispositivo Android. Lee mas - 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 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. Continúa, observando 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!

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 otro 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, una "cadena" de Markov.

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 el nombre de sus personajes (al menos en un momento u otro), y cuando parece que no puede pensar en un nombre que le guste, probablemente recurrido a un generador de nombres en línea Cree un nuevo alias con los mejores generadores de nombres en línea [Web extraña y maravillosa]Tu nombre es aburrido. Afortunadamente, puede conectarse a Internet 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, 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 letra "M" tiene una probabilidad del 60 por ciento de conducir a la letra "A" y una probabilidad del 40 por ciento de conducir a la letra "I". 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, el número de transiciones de estado aumenta), la probabilidad de que aterrices en un determinado estado converge en un número fijo, y esta probabilidad es independiente de donde comienzas el sistema.

Esto es extremadamente interesante cuando piensas 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 un "largo tiempo" de navegación.

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 la cadena de Markov.

Cuanto mayor sea la "probabilidad fija" de llegar a una determinada página web, mayor será 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 valioso. 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? Ya sea que estés usando Android (opciones de teclado alternativas ¿Cuál es el mejor teclado alternativo para Android?Echamos un vistazo a algunos de los mejores teclados de Play Store y los ponemos a prueba. Lee mas ) o iOS (opciones de teclado alternativas Las 10 mejores aplicaciones de teclado para iPhone: elegantes fuentes, temas, GIF y más¿Cansado del teclado predeterminado del iPhone? Estas aplicaciones alternativas de teclado para iPhone ofrecen GIF, temas, búsqueda y más. Lee mas ), existe una buena posibilidad de que la aplicación que elija use cadenas de Markov.

Es por eso 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 "compartir 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.

Simulación Subreddit

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 los datos de / r / soccer conjunto.

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 a continuación!