April 1st 2008, 15.00 hrs

Sander Evers

Abstract:

In sensor data processing, a simple and popular probabilistic model to relate a sequence of observations to an underlying sequence of hidden states is the Hidden Markov Model (HMM). In its basic form, the HMM defines one hidden state and one observation per time granule. This is too restrictive for our Bluetooth localization scenario, where we want observations to range over arbitrary time intervals. We define a variant of the HMM in which this is the case, and derive the associated (forward-backward) inference algorithm. Its complexity is exponential in the interval length, but if we restrict the sensor model to a Noisy-OR variant, we can modify the algorithm so that it is only exponential in the number of simultaneous `positive' readings. A perhaps larger contribution than the algorithms themselves are the systematic way in which we derive them. For this, we introduce a so-called `sum-factor' diagram which visualizes their structure and efficiency.