Maximum A Posteriori Path Estimation with Input Trace Perturbation: Algorithms and Application to Credible Rating of Human Routines

Daniel H. Wilson, Matthai PhiliposeIJCAI 2005

Introduction

Automated activity recognition has traditionally focused on identifying what an individual is doing. However, in many critical domains—such as medical training, elderly care, or industrial safety—the more vital question is how well the activity is being performed. This paper addresses the challenge of "credible" automated rating of human routines. A credible rater must be both relevant, reflecting the actual constraints of a task, and transparent, providing actionable feedback rather than just a numerical score.

The k-Edit Viterbi Algorithm

The authors propose a novel framework based on Maximum A Posteriori (MAP) path estimation with a significant twist: the system is permitted to "repair" the input data. The core of this approach is the $k$-Edit Viterbi (KEV) algorithm.

Trellis diagram of the k-Edit Viterbi (KEV) algorithm showing original and added observations for trace repair.

Unlike the standard Viterbi algorithm, which finds the most likely state sequence for a fixed set of observations, KEV searches for the most likely path given a trace that can be modified by up to $k$ edits (insertions, deletions, or replacements). These edits represent the "justification" for the rating. If a student skips a step in a medical procedure, the algorithm "inserts" the missing observation to complete the path, and the cost of this edit informs the final grade.

Enhancing Credibility with HSMMs and Logic

Standard Hidden Markov Models (HMMs) are often insufficient for rating human routines because they assume action durations follow a geometric distribution and cannot easily model long-term dependencies. To solve this, the authors integrated KEV with Hidden Semi-Markov Models (HSMMs), allowing for explicit duration modeling. This makes the system sensitive to routines performed too quickly or too slowly.

Furthermore, they augmented these models with Linear Temporal Logic (LTL) constraints. This allows human experts to define "global rules" (e.g., "if the refrigerator is opened, it must eventually be closed") without needing to retrain the underlying statistical model. This combination of data-driven learning and expert-defined logic ensures the rater remains grounded in the task's actual requirements.

Evaluation and Key Insights

The framework was evaluated using RFID-sensor data from common routines: making tea, preparing a sandwich, and grooming. By testing on "intentionally incorrect" traces—such as skipping steps or moving too fast—the authors demonstrated that the HSMM-KEV approach significantly outperforms standard HMMs in detecting performance deficits.

Likelihood vs. k-value showing the 'Odd-Even' effect and thresholding for routine rating.

A fascinating discovery during evaluation was the "Odd-Even" effect. As the edit budget $k$ increases beyond the optimal repair, the algorithm's likelihood can oscillate. This happens because the algorithm may be forced to add unnecessary observations and then "opportunistically" delete others to compensate. Despite this, the system successfully used a likelihood threshold to distinguish between "pass" and "fail" performances across different activities.

Conclusion

The most powerful aspect of this research is the concept of "edits as advice." The minimal repair required to make a trace likely serves as a constructive, transparent explanation for the user. While challenges remain regarding the computational complexity of large edit budgets and the occasional lack of intuition in suggested repairs, this work provides a robust foundation for building automated systems that can teach and monitor complex human behaviors with high credibility.

Summary updated

BibTeX
@inproceedings{wilson2005maximum,
  author = {Daniel H. Wilson and Matthai Philipose},
  title = {{Maximum A Posteriori Path Estimation with Input Trace Perturbation: Algorithms and Application to Credible Rating of Human Routines}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure