The hidden permutation model and location-based activity recognition

Permutation modeling is challenging because of the combi-natorial nature of the problem. However, such modeling is often required in many real-world applications, including ac-tivity recognition where subactivities are often permuted and partially ordered. This paper introduces a novel Hidden Per-mutation Model (HPM) that can learn the partial ordering constraints in permuted state sequences. The HPM is parame-terized as an exponential family distribution and is flexible so that it can encode constraints via different feature functions. A chain-flipping Metropolis-Hastings Markov chain Monte Carlo (MCMC) is employed for inference to overcome the O(n!) complexity. Gradient-based maximum likelihood pa-rameter learning is presented for two cases when the permu-tation is known and when it is hidden. The HPM is evaluated using both simulated and real data from a location-based ac-tivity recognition domain. Experimental results indicate that the HPM performs far better than other baseline models, in-cluding the naive Bayes classifier, the HMM classifier, and Kirshner’s multinomial permutation model. Our presented HPM is generic and can potentially be utilized in any prob-lem where the modeling of permuted states from noisy data is needed