¿Es viable utilizar un HMM para evaluar qué tan bien se utiliza un catálogo?

Question

Yo estaba interesado en la evaluación de un catálogo que los estudiantes estarían utilizando para observar cómo está siendo utilizado de manera probabilística.

El catálogo trabaja por la elección de las células en una secuencia temporal, así por ejemplo:

• El estudiante A tiene: ($ t_1 $, $ Cell_3 $), ($ t_2 $, $ $ Cell_4)
• El estudiante B tiene: $ (t_1, Cell_5), (t_2, Cell_3), (t_3, Cell_7) $.

Supongamos que las células de la tabla son estados de un Hidden Markov Model, por lo que la transición entre los estados tendrían mapa en el mundo real a un estudiante que va de una célula dada a otro.

Si se asume que el catálogo no es más que una guía, que se espera que tenga un cierto tipo de fenómenos que se producen en un artefacto determinado. Considere este artefacto a ser único, digamos, por ejemplo, un programa.

¿Qué ocurre con este programa es una lista finita de observaciones, por lo tanto, para una célula dada tenemos una lista finita de observaciones para seguir la sugerencia mencionada en esa celda. En un HMM esto sería entonces la probabilidad asociada a un estado de generar una observación dada en este artefacto.

Por último, tenga en cuenta el catálogo de estructurarse de manera que en un principio se espera que la probabilidad para iniciar en una célula dada es igual. El catálogo no sugiere ningún punto de partida.

• Pregunta 1 :? ¿Es la correspondencia entre el catálogo y la adecuada HMM

• Pregunta 2 : Suponiendo que la pregunta 1 es válido. Consideremos ahora que formamos a la HMM utilizando como entradas $ (t_1, Cell_1), (t_2, Cell_3), ... (t_n, Cell_n) $ para los estudiantes. Habría entrenado el HMM, le preguntó una vez para generar la transición entre los estados que lo más probable es que los rendimientos consecuencia cuál es la forma más utilizada por las personas que utilizan el catálogo para un determinado experimento $ \ epsilon $?

Answer 1

Ad Question 1: Assuming that your assumptions on how the catalogue is used -- that is the choice of the next cell only depends on the current (or constantly many preceeding) cell(s), not the (full) history -- then yes, you can use a Markov Chain to model it.

However, you do not seem to need the "Hidden" part; this is only useful if you have (probabilistic) output in the states which you observe. In contrast, you want to observe the students' cell states directly.

Imagine you can not observe which cells students are in but only how much they like the current cell; this could be implemented by notorious "Was this useful to you?" buttons; in general, assume every students gives feedback from $\{1, \dots, k\}$ in every cell but you do not know which cell they are in. Then you can use a HMM to estimate their cell sequence given their feedback sequence.

Ad Question 2: Let me illustrate the use continuing above train of thought. For $n=k=3$, we have the following Markov chain:

^[source]

$p_{i,j}$ is the probability to transition from state $i$ to state $j$; note that $p_{i,0}=0$ for all $i$ and those edges have been left out¹. Let $p_{i,\bot}$ the probability of terminating in state $i$ (we leave out another dummy state for clarity). $q_{i,l}$ is the probability to emit $l$ when entering (or, equivalently, leaving) state $i$; this models our feedback. Of course, we require $\sum_j p_{i,j} + p_{i,\bot} = \sum_l q_{i,l} = 1$ for all $i$.

Note that the state sequence $0,1,2$ has probability $p_{0,1} \cdot p_{1,2}$ -- that is a central property of Markov chains. The output sequence $1,2$, on the other hand, has probability $q_{0,1}\cdot p_{0,1}\cdot q_{1,2} + q_{0,1}\cdot p_{0,2}\cdot q_{2,2} + q_{0,1}\cdot p_{0,3}\cdot q_{3,2}$.

In a real world scenario, we would have to train our Markov chain. Let us assume we have some sequences of both state and output²:

$\qquad \begin{align} &(0,1), (1,1), (2,1), (3,1) \\ &(0,2), (1,3), (3,1) \\ &(0,1), (3,3), (1,2) \end{align}$

Now we just count how often each transition and output happened and set our probabilities to the relative frequencies³:

^[source]

Now you can do the interesting stuff. Ignoring the output, you can determine the path with highest probability, you can determine the output sequence with highest probability but most importantly, and here the hidden part comes into play, you can find the most likely state sequence given an output sequence with Viterbi algorithm.

Bottom line: yes, you can use Markov chains resp. hidden Markov models (depending on your needs) to model your scenario. Wether the fundamental assumption -- the probability for the next cell only depends on the current cell -- makes sense is another question entirely.

---

1. We need a starting state, but we can make it a dummy by never going back. We can ignore its output or introduce a dummy output that is only and always emitted in state $0$.
2. If we have only output sequences, we can use the forward-backward algorithm.
3. Due to our low number of observations, we have a number of impossible transitions/emissions. Usually you assume that everything is possible and has just not been observed due to low probability. We can compensate for this by adding $1$ to all counts; this way, all sequences have probability $\gt 0$.