2
$\begingroup$

I have a set of questions regarding how HMMs are used.

Context: there is a stream of real numbers or real number vectors (e.g. data from a phone accelerometer) and the goal is to detect that an action has just happened based on the data from this stream. Only one type of action is considered, i.e. the device is either performing the action or not. An example of an action could be "drawing" a circle in the air with the device while not performing the action is, for example, just carrying the device in the pocket. I'm aware that there are other ways to do this than HMMs but I'm asking this question also to understand HMMs more so for the sake of this question please suppose that using HMMs is required.

I see two ways of doing this

  • multiple HMMs (i.e. the speech recognition way) - two HMMs (one for the action and for a non-action), the action is detected if the action-model has higher probability of generating the observed sequence than the non-action model - this would also mean that the signal would have to be processed in a sliding window fashion, running the whole window through the HMMs to get the probabilities
  • single HMM with tracking state - a single HMM with states corresponding to the stages of the (non-)action and then the forward algorithm (updated with each new observation as they come in from the stream) is used to get the probabilities of the states and if the action-is-happening-right-now state (or action-just-ended state) has the highest probability, the action is detected

Which of these ways is used in practice or which of these makes the most sense? What are the requirements for training data for each of the above approaches (provided they both make sense in the first place).

Regarding the training...

  • The Baum-Welch training uses only the observations and the state model is fitted to the observations, i.e. there is no clear interpretation of what the states actually represent. Therefore it cannot be used for the single HMM approach, am I correct?
  • If I wanted to use the single-model approach (provided it makes sense at all) I would need to actually know the hidden states of the system for the training sequences, am I correct?
  • If it is possible to label the training sequence(s) with the state (or what I think is the state), i.e. an in-action state and not-in-action state, or even action-is-starting, in-action, action-is-ending and non-action states, how would I train the single HMM?

I'm a total newbie in HMMs so if the questions are weird or very basic, you know why. Thanks for any answers that help me shine light on these issues.

$\endgroup$
  • $\begingroup$ The context you provide isn't very clear to me, in terms of motivating why you would want to use an HMM. You say you have a stream of real-number values, but what are these values and what hidden state are you supposing they are manifest representations of? You say you want to "detect an action" from the signal, but then you talk about blinking lights and tapping your phone on a table, which doesn't make sense in the context of "detecting" anything. Perhaps if you were more clear about WHY you want to use an HMM and what data you have to work with, people could give clearer advice. $\endgroup$ – Ryan Simmons Jul 3 '18 at 13:02
  • $\begingroup$ That said, your description of "multiple HMMs" also isn't clear to me. Are you referring to multi-stream HMMs, or something else entirely? If you are referring to multi-stream HMMs, I don't think your description of the method is accurate, nor would it apply to your situation. From what you describe, you only have a SINGLE stream of observed information, whereas multistream HMM is trying to make inference based on MULTIPLE streams of observed information. It doesn't make sense to try to apply this to "action" vs. "non-action", since those are just complementary (non-independent) states. $\endgroup$ – Ryan Simmons Jul 3 '18 at 13:09
  • $\begingroup$ @RyanSimmons I have updated the Context section of the question. Regarding multiple HMMs - if I understood the basics of speech recognition with HMMs correctly, it works in such a way that the observation sequence (acoustic features in that case) is passed to all the HMMs and each of the HMMs is trained to recognize a speech unit (phone, word... depending on the application). The unit is then chosen based on the probabilities of generating the observation sequence that is computed from all the HMMs. Using this way in my case would be like there are just two words - an action and a non-action. $\endgroup$ – zegkljan Jul 3 '18 at 13:14
  • $\begingroup$ (1/2): Multistream HMMs have multiple output processes; i.e. multiple streams of OBSERVED variables. In speech recognition, this is represented by multiple modalities (acoustic features, phonetic features, syntactic features, and in some contexts things like facial expressions, etc.). The idea is that you are trying to extract information on some finite set of latent features based on information across these multiple observed modalities. This does not sound like your context, to me. (cont...) $\endgroup$ – Ryan Simmons Jul 3 '18 at 13:39
  • $\begingroup$ (2/2): You have a single stream of observed information, by which you are trying to infer information on a single latent feature (the occurrence of an action). It doesn't make sense to me, as the problem is described, to try and fit multiple HMMs to this structure. In fact, that model wouldn't be identified. Action and non-action are not independent states, since one is a complement of the other; they are only describable by a single parameter (the probability of an action, since 1 minus this probability is the probability of a non-action). $\endgroup$ – Ryan Simmons Jul 3 '18 at 13:41
1
+100
$\begingroup$

To answer each of the questions in your post:

  1. Which of these ways is used in practice or which of these makes the most sense?

As I have mentioned in the comments above, unless I am misunderstanding, your description of "multiple HMMs" is likely inaccurate, and certainly inappropriate for the problem as you describe it. It seems to me that when you say "multiple HMMs" you are referring to what are usually called "multi-stream HMMs". Multistream HMMs have multiple output processes; i.e. multiple streams of OBSERVED variables. In speech recognition, this is represented by multiple modalities (acoustic features, phonetic features, syntactic features, and in some contexts things like facial expressions, etc.). The idea is that you are trying to extract information on some finite set of latent features based on information across these multiple observed modalities. This does not sound like your context, to me.

You have a single stream of observed information, by which you are trying to infer information on a single latent feature (the occurrence of an action). It doesn't make sense to me, as the problem is described, to try and fit multiple HMMs to this structure. In fact, that model wouldn't be identified. Action and non-action are not independent states, since one is a complement of the other; they are only describable by a single parameter (the probability of an action, since 1 minus this probability is the probability of a non-action).

  1. The Baum-Welch training uses only the observations and the state model is fitted to the observations, i.e. there is no clear interpretation of what the states actually represent. Therefore it cannot be used for the single HMM approach, am I correct?

No. Baum-Welch is simply an estimation algorithm. It is in fact the default for any simple HMM. Interpretation of the states has nothing to do with what algorithm is used to estimate the parameters; interpretation should be based on substantive knowledge of your data, and you should use this to inform how you construct your model.

  1. If I wanted to use the single-model approach (provided it makes sense at all) I would need to actually know the hidden states of the system for the training sequences, am I correct?

If you actually knew the hidden states of your system, there would be no point in running a hidden Markov model! The entire point of an HMM is that you cannot observe the hidden states of the system, so you must make inference on them using some set of manifest variables which you can observe. If you can observe the hidden states, then you can just directly estimate the transition probabilities.

  1. If it is possible to label the training sequence(s) with the state (or what I think is the state), i.e. an in-action state and not-in-action state, or even action-is-starting, in-action, action-is-ending and non-action states, how would I train the single HMM?

This question is a little unclear to me. As I said above, if you actually knew the states, then you don't have a HMM anymore. Otherwise, it sounds a little bit like you are describing a supervised training, where you may have some set of data on which you have complete knowledge but on future sets of data you will no longer have this knowledge. But it is also possible (and, I would argue, more common) to use unsupervised training, where you don't have any such labels. There is also a literature on semi-supervised training, where you have incomplete labeling.

Regardless, it sounds to me like you should start with a more basic overview of how training works in the context of HMMs. This thread has a number of useful links to papers and worked examples.

$\endgroup$
  • $\begingroup$ "If you actually knew the hidden states of your system, there would be no point in running a hidden Markov model!" - I was talking about the training data only. I have some fixed amount of observation sequences for which I know the hidden states. However, the states of the "live system" are actually hidden and therefore I need to use an HMM. "But it is also possible (and, I would argue, more common) to use unsupervised training" - please elaborate. If unsupervised, how would I find out the label for the live data then? $\endgroup$ – zegkljan Jul 3 '18 at 14:14
  • $\begingroup$ Did you follow the link I provided? There are plenty of examples, there. You have to understand that training in and of itself is only about estimating parameters, which can be done with our without labels. In unsupervised training, you fit an HMM to your training data set to estimate the parameters; you can then validate or test this model using whatever other data you have, as in any other statistical model. Fundamentally, supervised training is no different, only you have more information to work with in order to estimate these model parameters. $\endgroup$ – Ryan Simmons Jul 3 '18 at 14:39
1
$\begingroup$

I will try to answer the questions separately below but would also refer you to a question I have asked on the subject some years ago, where - I believe - the setting is similar to what you describe. I will intentionally not repeat what is covered in that thread.

Which of these ways is used in practice or which of these makes the most sense? What are the requirements for training data for each of the above approaches (provided they both make sense in the first place).

In brief, for the event detection setting I have tried both the multiple HMM and single HMM approaches and did not get very far. Conceptually HMM's are more suited for settings where the states themselves are latent / hidden and you do not actually have intuition of what they may / may not represent; how many states there are etc. Put more succinctly, an HMM is an unsupervised learning algorithm with a temporal dimension.

In most cases it is just a Gaussian Mixture model with a state-transition component in the likelihood function. A very good reference on this is Pattern Recognition and Machine Learning by Chris Bishop, chapters 9 and 13.

The Baum-Welch training uses only the observations and the state model is fitted to the observations, i.e. there is no clear interpretation of what the states actually represent. Therefore it cannot be used for the single HMM approach, am I correct?

Baum-Welch is just the EM algorithm in this context, you use it to fit a single HMM, for multiple HMM's you would need to repeat the process. You can also try to fit a HMM (as you can any model) by using a stochastic optimisation process like MCMC, etc. In an HMM there is no clear representation of what the states represent not due to Baum-Welch but due to the unsupervised nature of the approach. In other words, you are just temporally clustering similar observations, taking also into account how they transition between themselves. Theoretically, there is no guarantee that the results of the clustering will align with your implicit labelling (event / no event). You can force it to do so by feature-engineering, but then you are trying to fit a solution to a problem it is not originally meant for IMHO.

If I wanted to use the single-model approach (provided it makes sense at all) I would need to actually know the hidden states of the system for the training sequences, am I correct?

If you knew the hidden states, they are not hidden. The very discussion of event/non-event resonates with supervised labelling. One commonly encountered issue in this context is the large imbalance in the number of event versus non-event observations. Events are usually rare occurrences (like in my question).

If it is possible to label the training sequence(s) with the state (or what I think is the state), i.e. an in-action state and not-in-action state, or even action-is-starting, in-action, action-is-ending and non-action states, how would I train the single HMM?

As mentioned above, form the moment you are talking about labelling, you would be better off, especially if your events are fixed lengths, by using a classifier with temporal features (e.g. going back x number of timesteps). Even more suitable are the weight sharing neural network algorithms like recurrent neural networks as you point out or convolutional neural networks (not just useful for image processing) with varying window/convolution sizes.

$\endgroup$
  • $\begingroup$ The actions (events) are not fixed lengths. I they were I could just make a classifier that would take a window from the signal as an input and spit out action/non-action as an output. $\endgroup$ – zegkljan Jul 3 '18 at 14:01
  • $\begingroup$ The recurrent architectures (GRU or LSTM) or conv nets with varying window sizes will likely take care of that for you. $\endgroup$ – Zhubarb Jul 3 '18 at 14:02
  • $\begingroup$ I'm also looking for something minimalistic so that it could run reasonably well on, say, arduino. HMMs seemed like the way to go but I have never actually used them before, hence my question. Thanks for the insights though. $\endgroup$ – zegkljan Jul 3 '18 at 14:05
  • $\begingroup$ HMM's are not minimlaistic by any means! They are (the simplest form of) dynamic bayesian networks. Notoriously difficult to fit. EM is not a robust process, not guaranteed to find the global optimum (unlike likelihood maximisation). $\endgroup$ – Zhubarb Jul 3 '18 at 14:06
  • $\begingroup$ I'm talking about using a finished trained model. The training is, of course, hard but that would be done offline, not on the device. The inference, however, is quite easy if the number of states is small. $\endgroup$ – zegkljan Jul 3 '18 at 14:17
0
$\begingroup$

People always mix up "state", "event" and "event boundary".

Philosophically, "event" means the sharp change of state. So an "event detection" would mean detecting some transition with low probability.

Cognitively, psychologically and also looking at LSTM and predictive coding theory, you have a relatively stable predictive model of the input. Within a chunk of "event" (with a different meaning here), your model doesn't change much. When your model can no longer predict the input, this chunk of "event" breaks and a new event and a new model comes up.

Whatever terms people use, you can see the isomorphic structure.

In your description, "event" seems to mean actually a specific state. It's unnecessary to create a lot of parameters if it is already enough to describe your problem.

diagram

so at each time point you have a hidden sate which can take value "Event" or "Non-event". Between adjacent hidden states a transition matrix $A$ parametrizes $P(H_{i+1}|H_i)$ with higher probability to stay in the same state and lower probability to change (the usual sense of "event").

Probability density distributions of signal under hidden state "Event" and "Non-event" are different. Which means $p(S_i|H_i=Event)\neq p(S_i|H_i=Nonevent)$. We call it $B$.

$\pi$ specifying the probability with which value $H_0$ takes.

You have all the $S_i$ observed. What left is to find the most likely sequence of $H_i$. It gives you the highest joint probability which you can get by applying chain rule.

Each $H_i$ corresponds to one time point, but it will form chunks given the way you specify $A$ (more likely to stay than change). Starting and ending of actions are essentially the first and last action hidden state in a row.

You can of course also call $p(S_i|H_i=Event)$ and $ p(S_i|H_i=Nonevent)$ two different models. Then I think your two ways mean the same thing.

$\endgroup$
  • $\begingroup$ You are right that "event" is not a good word. I edited my question to not use the word "event" but "action" instead as that is closer to what I'm trying to achieve. However, your answer does not actually answer almost any of my questions. I know how HMMs work but I don't know how to actually use them. The two ways are definitely not the same thing - in the multiple-models there are multiple separate HMMs and I look how well each of them describes the observations while in the single-model there is only one HMM and I look at the probable hidden state given the observations. $\endgroup$ – zegkljan Jul 3 '18 at 12:58
  • $\begingroup$ if you have two separate HMMs, what are the hidden states of each HMM? If each HMM has only one state that doesn't change, it's essentially a reduced version of 1 HMM - the temporal relation between hidden states is ignored. $\endgroup$ – Xiaoxiong Lin Jul 3 '18 at 13:25
  • $\begingroup$ I have never said that the two HMMs would have only one state. They would have some number of states chosen such that they would fit the training sequences well. I don't know what are the hidden states - if I understand Baum-Welch training correctly there is no representation of the states, they (the transition probabilities) are just arranged as to maximize the likelihood that the training data are explained by the model. But I'm asking about this (in a way) in my question too. $\endgroup$ – zegkljan Jul 3 '18 at 13:32
  • $\begingroup$ sorry I misread your question. I think Baum-Welch algorithm can also be used for the 1HMM case, it automatically gives hidden states, just maybe not being what you expected - "action/non-action". For the 2 HMM case, I still don't see how it's doable. you are still not capturing the transition between action/non-action, by only comparing which is more likely at each time point. Unless you wrap these 2 HMMs up into a larger HMM. Then it comes back to what I said in the answer, with each small HMM being a distribution generating mechanism for $p(S_i|H_i=Event)$ $\endgroup$ – Xiaoxiong Lin Jul 3 '18 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.