python - udacity - tensorflow

¿Aplicar el aprendizaje automático a un juego de adivinanzas?

Question

Tengo un problema con un juego que estoy haciendo. Creo que conozco la solución (o qué solución aplicar) pero no estoy seguro de cómo encajan todas las ''piezas''.

Cómo funciona el juego:

( ¿Cómo abordar el algoritmo del número de adivinanzas (con un giro)? )

los usuarios recibirán elementos con un valor (los valores cambian todos los días y el programa conoce el cambio en el precio). Por ejemplo

Apple = 1
Pears = 2
Oranges = 3

Luego tendrán la oportunidad de elegir cualquier combo que quieran (es decir, 100 manzanas, 20 peras y 1 naranja). El único resultado que obtiene la computadora es el valor total (en este ejemplo, actualmente es $ 143). La computadora intentará adivinar lo que tienen. Que obviamente no podrá obtener correctamente el primer turno.

 Value quantity(day1) value(day1)
Apple 1 100 100
Pears 2 20 40
Orange 3 1 3
Total 121 143

El siguiente turno el usuario puede modificar sus números pero no más del 5% de la cantidad total (o algún otro porcentaje que podamos elegir. Usaré un 5%, por ejemplo). Los precios de la fruta pueden cambiar (al azar) por lo que el valor total puede cambiar en función de eso también (por simplicidad, no estoy cambiando los precios de la fruta en este ejemplo). Usando el ejemplo anterior, en el día 2 del juego, el usuario devuelve un valor de $ 152 y $ 164 en el día 3. Aquí hay un ejemplo.

quantity(day2) %change(day2) value(day2) quantity(day3) %change(day3) value(day3)
104 104 106 106
21 42 23 46
2 6 4 12
127 4.96% 152 133 4.72% 164

* (Espero que las tablas se muestren bien, tuve que espaciarlas manualmente, así que espero que no solo lo haga en mi pantalla, si no funciona, házmelo saber e intentaré subir una captura de pantalla).

Estoy tratando de ver si puedo averiguar cuáles son las cantidades en el tiempo (suponiendo que el usuario tenga la paciencia para seguir ingresando números). Sé que en este momento mi única restricción es que el valor total no puede ser más del 5%, por lo que no puedo tener una precisión del 5% en este momento para que el usuario lo ingrese para siempre.

Lo que he hecho hasta ahora

Tomé todos los valores de la fruta y el valor total de la canasta de frutas que me dieron y creé una gran tabla con todas las posibilidades. Una vez que tengo una lista de todas las posibilidades, utilicé la teoría de grafos y los nodos creados para cada posible solución. Luego creo bordes (enlaces) entre los nodos de cada día (por ejemplo, día1 a día2) si está dentro del 5% de cambio. Luego elimino todos los nodos que no tienen bordes (enlaces a otros nodos) y, a medida que el usuario sigue reproduciendo, también elimino rutas completas cuando la ruta se convierte en un callejón sin salida. Esto es genial porque reduce las opciones, pero ahora estoy estancado porque quiero reducir aún más estas opciones. Me han dicho que este es un problema oculto de Markov pero una versión más complicada porque los estados están cambiando (como se puede ver más arriba, se están agregando nuevos nodos cada turno y se están eliminando los antiguos / no probables).

** si ayuda, recibí una respuesta increíble (con código de muestra) sobre una implementación python del modelo baum-welch (se usa para entrenar los datos) aquí: Ejemplo de implementación de Baum-Welch **

Lo que creo que debe hacerse (esto podría ser incorrecto):

Ahora que reduje los resultados, básicamente estoy tratando de permitir que el programa intente predecir la base de resultados restringida basada en la correcta. Pensé que esto no era posible, pero varias personas sugieren que esto se puede resolver con un modelo de markov oculto. Creo que puedo ejecutar varias iteraciones sobre los datos (usando un modelo de Baum-Welch) hasta que las probabilidades se estabilicen (y deberían mejorar con más turnos por parte del usuario). La forma en que los modelos ocultos de Markov pueden verificar la ortografía o la escritura a mano y mejorar a medida que cometen errores (en este caso, los errores son elegir una canasta que se elimina en el siguiente turno como improbable).

Dos preguntas:

1. ¿Cómo averiguo la matriz de transición y emisión si todos los estados son al principio iguales? Por ejemplo, como todos los estados son igualmente probables, se debe usar algo para dedicar la probabilidad de que los estados cambien. Estaba pensando en utilizar el gráfico que hice para ponderar los nodos con el mayor número de aristas como parte del cálculo de los estados de transición / emisión. ¿Tiene sentido o hay un mejor enfoque?

2. ¿Cómo puedo hacer un seguimiento de todos los cambios en los estados? A medida que se agregan nuevas cestas y se eliminan las antiguas, se produce un problema de seguimiento de las cestas. Pensé que un Modelo de markov oculto Dirichlet Proceso (hdp-hmm) sería lo que necesitaba pero no estoy seguro de cómo aplicarlo.

(Lo siento si me parece un poco frustrado ... es un poco difícil saber que un problema se puede resolver, pero no es capaz de captar conceptualmente lo que se debe hacer).

Como siempre, gracias por su tiempo y cualquier consejo / sugerencia sería muy apreciado.

Answer 1

Como ha dicho, este problema se puede describir con un HMM. Usted está esencialmente interesado en mantener una distribución sobre estados latentes u ocultos, que serían las cantidades verdaderas en cada punto de tiempo. Sin embargo, parece que estás confundiendo el problema de aprender los parámetros para un HMM opuesto a simplemente hacer inferencia en un HMM conocido. Tienes el último problema pero propones emplear una solución (Baum-Welch) diseñada para hacer lo primero. Es decir, ya tienes el modelo, solo tienes que usarlo.

Curiosamente, si se codifica un HMM discreto para su problema, se obtiene un algoritmo muy similar al que se describe en la solución de teoría de grafos. La gran diferencia es que su solución está rastreando lo que es posible, mientras que un algoritmo de inferencia correcto, como el algoritmo Virterbi , rastreará lo que es probable . La diferencia es clara cuando hay superposición en el rango del 5% en un dominio, es decir, cuando múltiples estados posibles podrían pasar al mismo estado. Su algoritmo podría agregar 2 aristas a un punto, pero dudo que cuando calcule al día siguiente tenga un efecto (debería contar dos veces, esencialmente).

De todos modos, podrías usar el algortihm de Viterbi, si solo estás interesado en la mejor suposición en el último día, te daré una breve idea de cómo puedes simplemente modificar tu solución de teoría de grafos. En lugar de mantener los bordes entre los estados, mantenga una fracción que represente la probabilidad de que el estado sea el correcto (esta distribución a veces se denomina estado de creencia). En cada nuevo día, propague su estado de creencia incrementando cada segmento según la probabilidad de que sea padre (en lugar de agregar una ventaja agregando un número de coma flotante). También debe asegurarse de que su estado de creencia esté debidamente normalizado (sumas a 1), así que divida por su suma después de cada actualización. Después de eso, puede ponderar cada estado según su observación, pero como no tiene una observación ruidosa, puede ir y establecer todos los estados imposibles a cero y luego volver a normalizar. Ahora tiene una distribución sobre cantidades subyacentes condicionadas a sus observaciones.

Me estoy saltando una gran cantidad de detalles estadísticos aquí, solo para darle la idea.

Editar (re: preguntas): la respuesta a su pregunta realmente depende de lo que desee, si solo desea la distribución para el día más reciente, entonces puede salirse con la suya con un algoritmo de una sola pasada como el que describí. Sin embargo, si desea tener la distribución correcta de las cantidades en cada día, también tendrá que hacer un pase hacia atrás. Por lo tanto, el algoritmo acertadamente llamado forward-backward . Tengo la sensación de que, dado que estás buscando retroceder un paso y eliminar los bordes, probablemente quieras la distribución para todos los días (a diferencia de lo que originalmente asumí). Por supuesto, notó que hay información que se puede usar para que el "futuro pueda informar el pasado", por así decirlo, y esta es exactamente la razón por la que también debe hacer el pase hacia atrás, no es realmente complicado. ejecutar exactamente el mismo algoritmo comenzando al final de la cadena. Para obtener una buena visión general, consulte el tutorial de 6 piezas de Christopher Bishop en videolectures.net.

Como mencionaste agregar / eliminar bordes, déjame aclarar el algoritmo que describí anteriormente, ten en cuenta que esto es para un único pase hacia adelante. Deje que haya un total de N posibles permutaciones de cantidades, por lo que tendrá un estado de creencia que es un vector escaso N elementos largos (llamado v_0). El primer paso que recibe es una observación de la suma, y ​​rellena el vector al establecer todos los valores posibles para que tengan la probabilidad 1.0, luego se re-normalizan. El siguiente paso crea un nuevo vector disperso (v_1) de todos los 0, itera sobre todas las entradas distintas de cero en v_0 e incrementa (por la probabilidad en v_0) todas las entradas en v_1 que están dentro del 5%. Luego, ponga a cero todas las entradas en v_1 que no sean posibles de acuerdo con la nueva observación, luego vuelva a normalizar v_1 y deseche v_0. repita para siempre, v_1 ​​siempre será la distribución correcta de posibilidades.

Por cierto, las cosas pueden ser mucho más complejas que esto, si tiene observaciones ruidosas o estados muy grandes o estados continuos. Por esta razón, es bastante difícil leer parte de la literatura sobre inferencia estadística; es bastante general.