--- title: "Maximum A Posteriori Path Estimation with Input Trace Perturbation: Algorithms and Application to Credible Rating of Human Routines" authors: - "Daniel H. Wilson" - "Matthai Philipose" doi: "" url: "https://ijcai.org/proceedings/2005/149" pdf: "https://ijcai.org/proceedings/2005/0149.pdf" venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence" year: 2005 pages: "895-900" track: "" keywords: --- # Maximum A Posteriori Path Estimation with Input Trace Perturbation: Algorithms and Application to Credible Rating of Human Routines Daniel H. Wilson, Matthai Philipose *Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence*, pages 895-900. ## Abstract Rating how well a routine activity is performed can be valuable in a variety of domains. Making the rating inexpensive and credible is a key aspect of the problem. We formalize the problem as MAP estimation in HMMs where the incoming trace needs repair. We present polynomial time algorithms for computing minimal repairs with maximal likelihood for HMMs, Hidden Semi-Markov Models (HSMMs) and a form of HMMs constrained with a fragment of the temporal logic LTL. We present some results to show the promise of our approach. ## Full text ## 1 Introduction Rating how well a person performs a routine activity is a broadly useful capability with many applications: professors train medical students by rating their execution of established procedures, caregivers assess the well-being of their wards by rating how well they are able to perform activities of daily living, and managers and workflow experts identify poorly performed procedures that cause bottlenecks in a system. Although rating routine activity is certainly useful, as conventionally done it is also very expensive - each activity performance requires a dedicated human observer (often an expert). Many situations where gauging the performance of routine activities could be helpful are therefore either not rated at all, or rated in a cursory manner. Clearly, an opportunity exists for automated techniques to reduce the cost of rating. In this paper, we explore methods for automatically rating performances of routine activities. The basic classification task of rating, going from observations to scores, is amenable to a variety of standard approaches. Rating becomes challenging, however, if we wish to make it both incrementally inexpensive and credible. We define an incrementally inexpensive rater to be a rater in which the extra cost of rating a new activity is relatively low. The main determinant of cost is whether rating a new activity requires a custom classifier to be developed from scratch, or whether a generic classifier of some kind can be easily customized to the task. A credible rater is one that is both relevant and transparent. By relevant, we mean that the classification model for a particular rating task should reflect constraints on activity performance that are important to those ## Matthai Philipose Intel Research 6th Floor 1100 NE 45th Street Seattle WA 98115 matthai@cs.washington.edu using the rating. For example, a professor grading anesthesiology students performing an intubation may want to indicate what her notion of good performance is. By transparency, we mean that the system should be able to justify why it has assigned a particular rating. Ideally, the justification should be constructive, in that it should suggest how a low-rated performance may be altered to obtain a high-rated one. Our techniques for rating activity routines are designed to satisfy the above requirements. To lower incremental cost, we choose a representation that is easily learned: all activities to be rated in our system are modeled by variants of Hidden Markov Models (HMMs). We intend that these models, especially given simple prior information, can be learned easily from training examples. More crucially, we formulate the justification for a rating relative to this model generically as the set of edits required on the trace generated by the rated activities; we therefore do not require special identification and modeling of errors and their causes. A fundamental weakness of these models is that they are first order, preventing them from capturing certain important correlations. We augment the Markov models with an intuitive constraint formalism (a small fragment of the temporal logic LTL [1]) that allows raters to explicitly state relevant constraints. Given these relevant and easy-to-construct models, we formulate rating as the likelihood of (possibly edited) observation sequences. The core of this paper consists of efficient algorithms to compute maximum likelihood paths of minimally edited versions of incoming observations with respect to various representations for activities, including HMMs, HSMMs and temporally constrained HMMs. The algorithms use the dynamic programming technique used to great effect by the wellknown Viterbi algorithm. A preliminary evaluation shows the promise of our techniques. ## 2 Overview In this section, we describe how we expect our system to be used, and we sketch how our system supports this usage model. In this paper, our goal is to develop a system that rates how well an elder performs day-to-day activities. Such a system is of great interest to the eldercare industry. In theory, caregivers will assess the elders' well-being by consulting ratings summaries and credible explanations of performance deficits. For example, the system may recognize that an elder is no longer able to prepare their daily bowl of soup, and report why (e.g., can't reach cabinet or difficulty holding spoon). To end-users, our system represents activities as a set of steps. Each step has a duration and a set of observed actions performed, and is succeeded by other steps. For instance, the activity "making soup" for a particular elder may have the following steps: "preheat water," "open can," "mix and boil ingredients," "serve," and "clean up." The step "open can," may have an average duration of 45 seconds and contain the following actions: "use utensil drawer," "use can opener," "use can," and "use pantry door." For concreteness, we will assume in what follows that we are using RFID-based [4] sensors that will directly sense the action of using particular objects. Therefore, all of our actions are of the form "use X" where X is some object. Inherently, our system requires that actions are observable by sensors. Given an activity trace (i.e., a trace of actions that constitutes a particular execution of an activity), our system provides a rating (e.g., pass or fail). If the grade is a fail, the system provides an alternate sequence of actions as close to the original as possible that would have elicited a pass grade (essentially a constructive justification of the grade). In more detail, use of the system proceeds as follows: - Learning the model A human demonstrator performs the routine in an exemplary fashion. The system collects traces Y1, . . . , Yn of the routine. Each trace Yi is a sequence of time-stamped observations yi1, . . . , yimi of the demonstrator's actions. The traces are used to learn a dynamic stochastic model (either an HMM or an HSMM) with parameters λ. The hidden states s1, . . . , sN of the model correspond to the "activity steps" above, and are labelled l1, . . . , lN with the names of the step. - Adding global constraints Typically, the first-order model learned in the previous step cannot capture important higher-order correlations. For instance, in a successful soup-making routine, the stove, if it is used, should eventually be turned off after it is turned on. The turning on would happen in the "preheat water" step, but the turning off may not happen until the end of the "serve" step. The human rater explicitly adds a set C of constraints on the sequence of hidden states or observations that specify these required higher-order correlations. In this case, a possible constraint would be of the form use("stove control knob") E use("stove control knob"), read as "a use of a stove control knob should eventually succeeded by a use of a stove control knob". - Learning rating thresholds A human rater rates each trace Yi with a rating ri ∈ {pass, fail}. Let the constrained MAP likelihood of trace Y given λ and C, ˆlY = CMAP(M, Y, C), be the likelihood of the path ˆ SY with maximum a posteriori (MAP) likelihood given λ and Y that satisfies C. We perform a simple thresholding computation to calculate the likelihood threshold L such that, given the classification function R(l) = if l < L then fail else pass, R(ˆlYi ) = ri for as many of the Yi as possible. Intuitively, L separates the passes from the fails. Generating a rating and justification Given the constrained model (λ, C) and threshold L, the automated rater is ready for use. The person to be rated generates a trace Y = y1, . . . , ym to be rated automatically. The rater finds the constrained MAP likelihood ˆlY and path ˆ SY = (ˆ s1, y1), . . . , (ˆ sm, ym) for Y , and assigns it the rating r = R(ˆlY ). If r = fail, the rater attempts to produce a repaired trace trace Y ′ = y′1 , . . . , y′m such that the edit distance between Y and Y ′ is as small as possible, and ˆlY ′ > L. In other words, Y ′ is the closest trace to T that passes. The rater offers r as the rating for the activity and, if appropriate, δˆ SY , ˆ SY ′ , the set of edits needed to transform ˆ SY into ˆ SY ′ , as the justification for the rating. As described above, our rating system employs two key non-standard pieces of machinery. 1. A method to compute the repaired observation trace T ′ , that is a minimum edit distance from a given trace T whose likelihood is above a pre-specified threshold L. 2. A method to compute the constrained MAP likelihood function CMAP(M, T, C). ## 3 Trace Repair for HiddenMarkovModels A Hidden Markov Model (HMM) λ = (A,B, π) is a commonly used stochastic model for dynamic systems [5]. We formally pose the trace repair problem as a variation of estimating the most likely state sequence given a sequence of observations (classically solved via the Viterbi algorithm). An HMM is defined as follows. Let QA = {q1, . . . , qN} be the states of the process being modeled, and OB = {o1, . . . , oM} the observation signals possibly generated by the process. We use meta-variables st and yt to denote the states and observations respectively at time t. Aij is the probability p(st+1 = qj|st = qi) of transitioning from state qi at time t to qj at time t + 1 for any t; Bij is the probability p(yt = oj|st = qi) of generating observation oj when in state qi (we write Biyt for Bij such that yt = oj). The initial state distribution πi = p(s0 = qi). ## 3.1 The RepairedMAP Path Estimation Problem We now formulate the problem of MAP path estimation given an observation sequence if we are allowed to first make a limited number of edits or "repairs" to the sequence. We begin by formalizing the notion of an edit. We then state the repaired MAP path estimation problem and present a variation of the Viterbi algorithm to solve it. Let Y N be the set of length-N strings of observations over some finite alphabet Y . Then ek,N = ((b1, s1), ...(bN, sN)) is a length-N k-edit vector on Y N , with bi boolean, si strings over Y , and k = ∑1≤i≤N (bi + |si|). For instance, ˆ y1 = "cat" is a string in Y 3 ; e4,3 1 = ((false, "BB"), (false, ""), (true, "R")) is an edit vector on Y 3 . Applying an edit vector e to string ˆ yn = y1 . . . yn, written e(ˆ y) results in a new string ˆ y′ obtained as follows. For 1 ≤ i ≤ n, let if e.bi is true, then replace yi with ˆ y′i , else replace yi with yie.si (e.si appended to yi). For example, e4,3 1 (ˆ y1) = "cBBaR". A string ˆ y′ is a k-edit of another ˆ y if there exists edit vector ek,N such that ˆ y′ = ek,N (ˆ y). Figure 1: Trellis for k-Edit Viterbi on HMMs ![Image](https://ijcai.org/proceedings/2005/fulltext/149/image_000000_ed14df8c15d225f5113accd4378bf46769fd1c7e457c625393a24363cb366ceb.png) We are now ready to specify the problem of MAP estimation with repairs: Definition 1. (Repaired MAP Path Estimation Problem (RMAP)) Given observation sequence ˆ yT , HMM λ = (A,B, π) and edit distance K find observation sequence ˆ y′T ′ = ˙y1 . . . ˙yT ′ that is a K-edit of ˆ yT and path ˆ sT ′ = ˙s1, . . . , ˙sT ′ maximizing p(ˆ sT ′ , ˆ y′T ′) over all T ′ , ˆ sT ′ and ˆ y′T ′ . Before discussing our solution, we define string ˆ y′ as the (k,a)-edit of string ˆ yn if ˆ y′ = ek,n (ˆ y) for some ek,n , |ek,n .sn| ≤ a, and additionally, ek,n .bn if a = 0 and |ek,n .sn| > 0 if a > 0. The (k, a)-edit of a string requires its last character to be either preserved or replaced by at least one character, with at most a characters added. Edits compose as follows (dνn = n - ν ; a′ = 1 if a ̸= 0, 0 otherwise; (ν, α)<k(n, a) if ν < n and α ≤ k, or if ν = n and α < a): Lemma 1. (Edit Composition) Let Y kaˆ y n be the set of all (k, a)-edits of the n-prefix of string ˆ y over Y . Then Y kaˆ y n = {ˆ y′ y|y ∈ Y, ˆ y′ ∈ Y καˆ y ν , (ν, α)<k(n, a), κ+dνn +a′ = k}. Table 1 specifies an algorithm (the k-Edit Viterbi (KEV) algorithm) to solve RMAP. KEV iterates over the T original observations in the incoming observation string. For each original observation, it iterates over possibilities for the K added observations at that position, for a total of TK + T iterations. At each iteration t corresponding to original obervation [t] = t div (K + 1) + 1 and added observation #t = t mod (K+1), KEV computes the likelihood δtik of the most likely path ending in state i given an observation string that is a (k,#t)-edit of y1 . . . y[t] over all such edit vectors; KEV also records as ψtik the penultimate state and edit in this path. Following the chain of ψtik's back to the start state iteration gives the MAP repaired path. The trellis of figure 1 illustrates KEV. Columns of the trellis represent edits considered for inclusion into the final string. Large circles represent original observations and small ones represent adds. For technical reasons (to allow skipping the first original observation), we add a distinguished start state q0 with new start probabilities π′0 = 1, A0i = πi and Ai0 = 0 and add a column (t = 0) processed in the initialization step. To allow skipping the last original observation with Initialization: t = 0, k = 1 . . . K, 1 ≤ i ≤ N Iteration: 1 ≤ t ≤ TK+T, k = at, at+1, . . . , K Termination: t = TM = TK + T + 1 Backtracking: (t, i, k) = ψTMiMK; while t > 0, Table 1: The k-Edit Viterbi Algorithm for HMMs no adds, we add a column (t = TM = TK + T + 1). Rows represent possible hidden states. The end result of the algorithm is a forward path (shown in light grey in figure 1) through the trellis that, unlike in the conventional Viterbi algorithm, may jump between nodes in non-adjacent time slices. If the path jumps over the slice for an original observation yi (where i is the position of the observation in the input string ˆ y), we conclude that yi was deleted from ˆ y, otherwise not. Further, if the path passes through a sequence of added nodes with no intervening original node such that yi is the first original observation to the left of the sequence, and the observations at these nodes are yi1 , . . . , yin , we conclude that the string yi1 . . . yin was added at the i'th spot in the incoming string. The forward path is the required solution ˆ sT ′ , and the string of observations along the path is the edited string ˆ yT ′ . The algorithm uses three intermediate variables, at, dtτ and yit. Variable at = 1 if #t ̸= 0 and 0 otherwise; dτt = [t] - [τ], represents the number of deletes skipping original observations between τ and t; yit is the observation considered when processing state i at slice t. Note that we only process original observations at time slices 1,K + 1, 2K + 1, .... In all other "added" slices, we need to propose the observed value to be added. A simple but inefficient approach would be to consider for each state, k-value and iteration t, every possible observable o ∈ OB as a candidate. In fact, we can consider a single observation instead of all |OB|. The key insight is that, when processing state i in an added slice, it is sufficient to consider adding as observable the most likely observable in that state. Let SN and YN be the sets of all length-N sequences of states and observables. Let ˙yi = argmax 1≤j≤M Bij. Let ˆ sq be the result of appending state q to sequence ˆ s, and similarly for ˆ yy. Then, for all qi ∈ QA: This follows from the fact that max yi p(ˆ sqi, ˆ yyi) = max yi πs1Bs1y1 (∏1≤i≤N,siqj ∈ˆ sN AijBjyj )(AsNiBiyi ) = πs1 . . . AsNi max yi Biyi = πs1 . . .AsNi ˙yi. Given this identity for the optimal observable to be added in state qi, we set yit to ˙yi if t is an "added" timeslice, and to y[t] otherwise. We are now ready to establish the soundness of the KEV algorithm. Let Sin be the set of length-n sequence of states ending in state qi. Let Y tik n be the set of length-n strings of observables that are (k,#t)-edits of y1 . . . y[t]. Proof sketch. Proof is by induction on t. We focus on the inductive case for δ. For ψ, replace "max" with "argmax". Given sn, sn+1 is independent of ˆ sn-1 , ˆ yn : Similarly, for yn+1 given sn+1: Substituting for Aji and Biyit above, and using p(A,B) = p(A|B)p(B) twice, we have, with (κ + at + dτt) = k: Lemma 2 ensures that maximizing over ˆ yyit maximizes over all strings ˆ yy. By lemma 1 maximizing over all ˆ yy with ˆ y ∈ Y τjκ n maximizes over ˆ y ∈ Y tik n+1 . Finally, ∀1≤j≤N,ˆ s∈Sjnqi ˆ s = ∀1≤i≤N,ˆ s∈Sin+1 ˆ s. Modifying the previous equation to reflect these insights: The soundness of KEV follows in a straightforward way from the above lemma. Further, given that the trellis has O(TKN) nodes, that at each node we compute O(K) δ and ψ values, and we consult O(NK) preceding data values to do so, the complexity of KEV as a whole is O(TN 2K3 ). ## 4 Trace Repair for HSMMs A Hidden Semi-Markov Model (HSMM) [3] λ = (A,B,D, π) is identical to an HMM except for the duration distribution D. Where an HMM generates a single observation according to B on each visit to a state s, the HSMM generates l independent observations from B on each visit, where l is drawn according to Dsl = p(l|s). The added flexibility is useful when modeling human activities, since the duration of stay in a state is restricted to be geometric (and therefore biased to small values) in HMMs. In what follows, we assume that D is over a finite set (of size |D|) of durations, where the longest duration is L steps. The RMAP problem is: given HSMM (A, B, D, π), observations ˆ yT and limit K, find argmax t,ˆ s∈QtA,ˆ y∈OtB , ˆ y k-edit of ˆ yT p(ˆ s, ˆ y). Init., Term., Bactracking: See table 1. Iteration: 1 ≤ t ≤ TK+T, k = at, at+1, . . . , t Table 2: The k-Edit Viterbi Algorithm for HSMMs Table 2 specifies a variant of KEV to solve the problem, and figure 2 shows a trellis for this algorithm. The trellis is identical to that used by KEV (we represent k added nodes with a single small circle), only its use is different. We focus on how δtik is calculated. At each timestep t, state i and edit distance k, as with KEV, we iterate over previous timesteps, states and edit distances τ, j and κ. However, this time instead of discarding the observations in the intervening timesteps, we seek their sub-sequence yκkτti. We assume that step t only ends a stay in state qi that begins immediately after the stay in qj that ended in step τ. If eτt is the number of edits in yκkτti (added nodes included + original nodes ignored), we require κ + at + eτt = k. The problem of maximizing the likelihood of the path ending at (i, t) then reduces to the problem of finding yκkτti maximizing p(yκkτti)Di|yκkτti|. We find this maximum by iterating through durations l in Di; for each l, we iterate through predecessors (τ, j, κ) of (t, i), finding a sequence yκkτti of length l with the highest probability; we keep a running tally of the maximum p(yκkτti)Dil. Finding yκkτti reduces to identifying NA added nodes (to include in yκkτti) and NO original nodes (to ignore), such that NA + NO = k - κ - at (to satisfy the k-edit criterion), and NA + (([t] - [τ]) - NO) = l (to satisfy the duration constraint). The two equations fix NA and NO. Since all the added nodes have the same probability ˙yi = p(ˆ oi|qi), it doesn't matter which particular NA we pick. On the other hand, we pick the NO original nodes with lowest probability of observation for exclusion; this can be done by sorting the original nodes in O(T log T) time offline, with O(L) access during execution. Once the sequence of nodes is picked to get yκkτti, we simply multiply their observation and transition probabilties together to get p(yκkτti), a process that takes l operations, since |yκkτti| = l = O(L). Given O(TNK) trellis nodes, computing O(K) δ and ψ values at each node, consulting O(|D|NK) preceding values for each value, and spending O(L) for each preceding value considered, the entire algorithm takes O(TN 2 |D|LK3 ) steps. Note that in the (fairly) common case that D and L are unbounded, this running time becomes O(T 3N 2K3 ). Figure 2: Trellis for KEV on HSMMs ![Image](https://ijcai.org/proceedings/2005/fulltext/149/image_000001_dec15e9fb83b686dba185d5e5b5241ea8eebb8df4158ffd241e7ef1503dd111b.png) ## 5 Trace Repair for Constrained HMMs We define a temporally constrained HMM (TCHMM) as λ = (A,B, C, π), where C is a temporal constraint of the form φ1Eφ2E . . . Eφ|C|. The φi are propositional boolean formulas over state labels l and observations y: φ ::= state(l)|obs(y)|φ ∧ φ|¬φ. Path suffix si . . . sT and observations yi . . . yT satisfy the constraint suffix Cj = φj . . . φW if for any k ≥ j, φj(sk, yk) implies that (sk+1 . . . sT , yk+1 . . . yT ) satisfy Cj+1, written (sk+1 . . . sT , yk+1 . . . yT ) ⊢ Cj. Intuitively if one formula in the constraint sequence is true w.r.t. the head of the state/observation sequences, then the formulas that follow must also eventually be true in their specified order later in the sequences. The constraint (state(COOK) ∧ obs(oil))E(state(WASH)∧obs(soap)) could, for instance capture the constraint that if oil is used in the cooking step of making dinner, soap should be used in the eventual required washing step. The RMAP problem may now be reformulated as given TCHMM with constraints C, observations ˆ yT and limit K, find SY = argmax t,ˆ s∈QtA,ˆ y∈OtB , ˆ y k-edit of ˆ yT φ(ˆ s, ˆ y) such that SY ⊢ C. Our solution for RMAP estimation is restricted to formulas of the form φ ::= state(l)|φ∧φ|¬φ (we disallow dependences on observables). A small modification to the KEV algorithm enables polynomial time solution of this problem. We use the same trellis as in KEV. For each timestep t, state i and edit distance k, we also now maintain an additional |C|-vector. An element δtikm with 0 ≤ m < |C| represents the likelihood of the MAP path ending at state i in time slice t with (k,#t) edits that still requires constraint suffix Cm+1 to be satisfied (except δtik0, which has no outstanding constraints to be satisfied). This likelihood can be computed compositionally from δτjκµ, with τ < t and (κ, µ) pointwise ≤ (k,m) in O(TN 2k3 |C|2P) steps, where formulas φi can be evaluated in O(P) steps (where P is the size of the formulas). Even MAP estimation (without trace perturbation) for TCHMM's has apparently neither been formulated nor solved previously, although it is potentially quite powerful. For instance, the constrained inference work of Culotta et. al. [2] is a special case of TCHMM k-edit MAP estimation (with k = 0, and C = state(q0)Estate(qi)). MAP estimation is a special case of RMAP estimation with k = 0. Our variant of KEV above therefore performs MAP estimation. Interestingly with k = 0, we can allow the more general version of formulas φ and still retain the fast running time. It is open how general C can be while remaining tractable. For instance, our constraints can be viewed as a fragment of Linear Temporal Logic (LTL) [1]. It is interesting to consider larger fragments as candidates. ## 6 Evaluation How does model choice affect advice? The k-edit Viterbi algorithm dispenses advice based on the parameters of its activity models. The credibility of this advice will suffer from any differences between these models and the reality they represent. In order to illustrate this point, we conducted two experiments over three different activity models. The two experiments compare a regular HMM and a time-sensitive HSMM, and a regular HSMM with an HSMM that has temporal logic constraints, respectively. First, we compare the output of HMMs versus HSMMs on three activity traces from different activity models (see the top row of Figure 3). Each activity trace was intentionally made incorrect: for making tea, the preparation step was hurried; for making a sandwich, not enough ingredients were collected; and for grooming, brushing teeth and combing hair were performed too rapidly. In the top row of Figure 3, we plotted the maximum likelihood values at each step of the activity traces (where a "step" is considered to be a state transition). HMMs fail to detect any problem, exhibiting high likelihood. However, HSMM likelihoods plummet, due to sensitivity to the amount of time spent in each state. The KEDIT trace correctly adds the proper number of observations to each state, resulting in a high likelihood. Second, we compare the output of HSMMs with and without temporal logic constraints (TLCs) (see the bottom row of Figure 3). Again, we intentionally chose incorrect sequences for the three activities: for making tea, the stove is turned on but never turned off; for preparing a sandwich, the refrigerator door is opened and never closed; and for grooming, the sink water is turned on and never turned back off. In the top row of Figure 3, we plotted the maximum likelhood values at each step of the activity traces. Regular HSMMs fail to detect any problem, reporting high likelihood. HSMMs with TLCs report low likelihood, because they are only allowed to consider state-transitions which satisfy all constraints. In these traces, constraints are broken and alternate, low-likelihood, paths must be considered. The KEDIT trace correctly adds the necessary steps (i.e., turn off stove, shut refrigerator, and turn off sink), resulting in high likelihood. How does the rating change as k increases? The k-edits Viterbi algorithm provides advice for up to K edits. Ideally, we desire a trace that is above the likelihood threshold with the minimum number of edits. One method is to incrementally increase k until the threshold is exceeded. For this reason, we are interested in how the likelihood changes as k increases. In this experiment we ran k-edits Viterbi for HSMMs on an empty trace of the "making tea" activity. In Figure 4 we plotted the overall likelihood of each trace as the number of possible edits was increased. The dashed line is a threshold showing the likelihood of an acceptable "good" trace. Obviously, the original empty sequence had low likelihood. As k was increased from one to three, the algorithm was forced to assemble partially complete activity traces which had even lower overall likelihood. When k = 4 the algorithm formed a complete trace and met the threshold. As k increased further, the algorithm tweaked the sequence for a slightly higher likelihood. The most likely possible path was reached at k = 6. Afterwards, we see an "odd-even" effect as the algorithm is forced to add new (less likely) observations, and then opportunistically delete other observations. For k ≥ 9, the likelihood drops as the algorithm performs too many modifications to the trace and is unable to reach the optimal solution. How intuitive is the advice? We now examine the advice dispensed by k-edits Viterbi in several scenarios. We ran the algorithm on activity traces that had the following problems: restarted the activity, got two steps out of order, performed a step too quickly, and missed or sped through several nonconsecutive steps. All traces are from the "making tea" activity and likelihoods are reported using the optimal number of edits (i.e., k value). Figure 3: One activity per column; top row compares HMMs to HSMMs, bottom to TCHMMs ![Image](https://ijcai.org/proceedings/2005/fulltext/149/image_000002_2d53357556e2dc7f7ad2dc1ff78156e9d8f159cb327a9a8271275a9fc946ac32.png) The beginning steps of the next trace were performed twice (i.e., a "start" and a "restart"). The algorithm finds the maximum likelihood solution by deleting extra observations. However, the algorithm did not delete the entire start or restart, but decided to "pick and choose" among the two, keeping the best observations of both. In contrast, our intuition would be to advise the user to keep either the start or the restart. Similarly, in a trace in which two steps were performed out of order, the algorithm deletes one of the misordered steps and inserts new steps in the correct position. We found this to be less intuitive than simply telling the user to switch the two steps to the correct order. In the next trace, one step was performed too quickly: the "preparation step" only generated one observation, when it should have generated at least two. The algorithm suggested new observations that corrected the amount of time is spent in the state. However, the algorithm will always suggest the most likely observation from the state, because this maximizes the overall likelihood. At first glance, we found this suggestion strategy to be non-intuitive (although mathematically optimal), however, it became a non-issue for models in which observations were spread across multiple states. In the last trace several non-contiguous steps were missed entirely or performed too quickly. As k increased, the algorithm first chose to insert states that had been missed entirely, and then to add more observations to states that had been visited too briefly. In other words, the algorithm advises the user to at least visit each step of the activity before it advises how to perfect each step. This "top-down" approach fits with our intuition of how advice should be given. Figure 4: The likelihood of KEDIT traces as k increases. ![Image](https://ijcai.org/proceedings/2005/fulltext/149/image_000003_db9836b00d270f84bd21526d7e0cceffec022fcd7341a9cfabef32ee4338ac1b.png) ## 7 Conclusions In this paper, we describe the credible activity rating problem. We introduced the k-edits Viterbi algorithm and showed that given model parameters and an activity trace it can provide optimally repaired traces with from zero to k edits. We improved the algorithm by incorporating high-level temporal logic constraints. Finally, we evaluated the strengths and limitations of the algorithm on data from three activity models. ## References 1. E.M. Clarke, O. Grumberg, and D. A. Peled. Model Checking. MIT Press, Boston, 2000. 2. A. Culotta and A. McCallum. Confidence estimation for infor- mation extraction. In Proc. of Human Lang. Tech. Conf. (HLT- NAACL), 2004. 3. M. Ostendorf, V. V. Digalakis, and O. A. Kimball. From hmms to segment models: A unified view of stochastic modeling for speech recognition. IEEE Trans. Speech Audio Process, 4(5):360-378, 1996. 4. M. Philipose, K.P. Fishkin, M. Perkowitz, D.J. Patterson, H. Kautz, and D. Hahnel. Inferring activities from interactions with objects. IEEE Pervasive Computing Magazine, 3(4):50- 57, 2004. 5. L.R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257-286, 1989.