Te voy a contar una historia. Una historia en la que se utiliza un Modelo de Markov Oculto (HMM) para atrapar a un ladrón incluso cuando no había testigos reales en la escena del crimen; te sorprenderá ver la aplicación heroica de HMM para unir astutamente dos secuencias de eventos aparentemente no relacionadas en esta búsqueda de la verdad .
La trama
George es el gerente del departamento de entrega de equipaje en el aeropuerto del aeropuerto de Barra (Escocia)
- ¿Cuál es la diferencia entre el problema del vendedor ambulante y el problema del árbol de expansión mínima?
- ¿Qué tan importante es el DS y Algo?
- Cómo analizar el código para encontrar la complejidad del algoritmo
- ¿Cuál es el mejor algoritmo de sustracción automática de fondo para una sola imagen?
- ¿Cómo lidiar con la gestión eficiente de versiones y la compresión de múltiples versiones para bases de datos científicas?
Gestionar este aeropuerto pequeño y poco visitado hubiera sido fácil si no fuera por las constantes peleas entre Bob y William, los que manejan el equipaje.
Bob y William siempre pelean por la carga de trabajo, que podría ser una maleta, una mochila o una bolsa.
Para resolver estas peleas de una vez por todas, George creó una lista de trabajo. “Este gallo de trabajo establecerá expectativas claras sobre la división del trabajo en el manejo del equipaje”, pensó.
Pero estaba equivocado, justo cuando quería sentarse y relajarse, una queja llega y cae en su regazo.
Falta un collar con diamantes en la maleta de una celebridad que aterrizó.
George sabe que este es el trabajo de Bob o William, pero ¿cómo podría atrapar al verdadero culpable?
“Esto es complicado” pensó, ya que ambos no confesarían y para empeorar las cosas, la grabación de CCTV se estableció solo en el área de reclamo de equipaje y no en el área de manejo de equipaje. Esto significa que no puede haber evidencia concluyente de quién tomó la maleta y la puso en el cinturón.
¿Cómo puede George culpar al culpable sin evidencia concluyente de quién cargó la maleta manipulada?
Ingenioso George aplica HMM
Discapacitado por la falta de evidencia concluyente, George recurre a la ciencia para explorar la posibilidad de encontrar una señal estadística que pueda apuntar con la aguja al principal sospechoso.
Lee sobre Hidden Markov Models (HMM).
El aprende que
” Una de las aplicaciones de HMM es predecir la secuencia de cambios de estado, en función de la secuencia de observaciones”.
Aprende que HMM puede usarse para modelar un sistema que
1. Tiene estados internos finitos que generan un conjunto de eventos externos (observaciones)
2. Los cambios de estado internos son invisibles (ocultos) para un espectador fuera del sistema
3) El estado actual siempre depende del estado anterior inmediato solamente (proceso de Markov)
Voila! George rápidamente correlacionó su situación con un modelo HMM. George calcula que si las imágenes de CCTV del área de reclamo de equipaje se pueden considerar como la secuencia de observación, podría llenar el modelo y usarlo para exponer la secuencia ‘oculta’ en la que Bob y William habrían operado.
Además, William reemplaza a Bob cuando Bob pide un cambio de mano y viceversa. Al confiar solo en la última llamada de cambio, ¡Bob y William aparentemente estaban siguiendo el Proceso de Markov!
George ahora está emocionado ante la perspectiva de resolver el caso. Él crea un mapeo del HMM al escenario real que se parece a esto …
Habiendo relacionado los componentes básicos de HMM con su desafío, primero necesita encontrar una forma de poblar el HMM.
Para llenar completamente el modelo, necesita
1. Probabilidades de inicio: ¿cuáles son las posibilidades de comenzar en un estado? O, en otras palabras, ¿quién tenía más probabilidades de haber abierto el piso?
2. Probabilidades de emisión: ¿cuáles son las posibilidades de que ocurra una observación en un estado? ¿Cuáles son las posibilidades de decir ‘una bolsa siendo cargada por Bob’?
3. Probabilidades de transición de estado: ¿con qué frecuencia cambian los estados? ¿Qué posibilidades hay de que William le pida a Bob que se haga cargo?
Si bien HMM es crucial para resolver el caso, su función es solo modelar la situación. Sin embargo, para resolver el caso, necesitaría usar el HMM que crearía con el ‘Algoritmo de Viterbi’.
Usando el algoritmo de Viterbi, George podría descubrir la secuencia más probable de cambios de estado que causaron las observaciones.
Entonces, una vez que haya poblado el modelo, planeó usar el algoritmo de Viterbi para obtener la secuencia oculta en la que Bob y William operaron a partir de la secuencia de observación.
George ahora planea extraer información de la lista de trabajo para completar el modelo.
1. Probabilidades de inicio: ¿cuáles son las posibilidades de comenzar en un estado?
2. Probabilidades de transición de estado: ¿con qué frecuencia cambian los estados?
3. Probabilidades de emisión: en cualquier estado, ¿cuáles son las posibilidades de cada observación?
George ahora tiene la información crucial, el HMM, para acercarlo al culpable.
George ahora crea una secuencia de observación a partir de las imágenes de CCTV.
Secuencia de observación: secuencia en la que se observaron las emisiones causadas por los estados
Armado con cada pieza del rompecabezas, George ahora usa la implementación HMM y Viterbi, para armar el rompecabezas.
Finalmente llega a conocer la secuencia probable en la que operaron Bob y William.
Bob (piso abierto)> Bob (bolsa)> Bob ( maleta *)> Williams (mochila)
* Bob es acusado del robo.
¡CASO RESUELTO!
Referencias
1. Modelo oculto de Markov
2. Algoritmo de Viterbi
