Pattern recognition methods and hidden Markov models can be effective tools for online health monitoring of communications systems. Previous work has assumed that the states in the system model are exhaustive. This can be a significant drawback in real-world fault monitoring applications where it is difhcult if not impossible to model all the possible fault states of the system in advance. In this paper a method is described for extending the Markov monitoring approach to allow for unknown or novel states which can not be accounted for when the model is being designed, The method is described and evaluated on data from one of the Jet Propulsion Laboratory's Deep Space Network antennas. The experimental results indicate that the method is both practical and effective, allowing both discrimination between known states and detection of previously unknown fault conditions. Fault detection and isolation is often a complicated and lengthy process due to the fact that it can be difficult to establish the root cause of a problem in the communications chain. As an example, a problem with the radio receiver dropping carrier lock could be caused by a variety of factors such as problems with the spacecraft itself, external environmental influences such as weather, irregularities in the antenna pointing system, problems with the receiver hardware, incorrectly set tracking parameters, and so forth. Loss of a spacecraft signal during a planetary encounter may result in the irretrievable loss of science data. Hence, there is considerable motivation to be able to quickly detect, isolate, and repair a fault. The same scenario applies to many commercial and military communication systems: rapid detection of failures is essential as comnmnications equipment becomes more complex and various applications (such as medical imaging and electronic financial transactions) have come to rely on communications as an essential component of their day-to-day business. In this paper, the general problem of real-time monitoring of a dynamic system is examined, with particular emphasis on the problem of detecting anomalous states which have not been modelled a priori. There is an implicit assumption that the system being monitored is not amenable to standard linear modelling so that the standard linear literature [2, 3, world systems. monitored is in monitoring the systems approach to fault detection described in the control theory 4] is not applicable -this is frequently the case with complex realIt will help the reader to imagine that the particular system being fact a sub-system of an overall larger system: the primary purpose of "subsystem" is to quickly determine if it in particular is the cause of all the observed data up to time i, and y(t) is the observed data at time t. -Let 0 be a discrete random variable taking values in the set {wl, . . . . w~ }. Assume that the system at any time i is in one and only one of the m states, WI, , , , , Wm. For fault diagnosis applications WI is typically chosen to be the normal operating state of the system and the other states represent various possible fault conditions. The assumption that the states are mutually exclusive is equivalent to the "single-fault" assumption, namely that multiple faults do not occur simultaneously -this is a reasonable assumption in practice when fault conditions are relatively rare. The second assumption, that the set of fault states is exhaustive, is much more restrictive and rarely likely to be true in practice: we will return to this aspect of the problem later in the paper, but for the present we will assume that exhaustivity holds. Now consider the observable Y in relation to the states. We will assume that the conditional probability of Y given a particular state is stationary, i.e., For shorthand throughout the paper we will replace "fI(t) = Wi" by w: and "Y(t) = y" by y(i). Since the state-observable relation is not time-dependent, explicit reference -to time t in this context will be omitted, The observable ~ can be considered to be a probabilistic function of the underlying states, As an example, consider the case where the dynamic system being observed can be modelled in closed form, perhaps by a set of linear equations, In this case, the observable y could be a vector of residual prediction errors between the predicted -system outputs at time t and the actual system outputs at time i. Thus, y is a -characteristic indicator of whether the system is remaining with its normal state or has switched to another state (one which is not well approximated by the closed form system model). We will examine in more detail later specific examples of observable and underlying states. At this point we will assume that the prior probabilities of the states p(~i) are known and that either (a) the conditional probabilities of the observable given the states p(yl~i) are known, or equivalently, (b) that the conditional probabilities of the states given the observable p(~i [ y) are known. Since the states have been assumed -to be mutually exclusive and exhaustive, the equivalence of knowing either (a) or (b) follows from Bayes' rule: Section 2.3.2 will discuss how these conditional practice. Finally we will assume first-order Markov process the system being in state . I<i <m. distributions may be estimated in that the state variable O(t) is a stationary discrete-time with transition matrix A. Entry a ij is the probability of i at time i Riven that the system was in state i at time Q(t) need not necessarily be assumed to be a first-order Markov process: the algorithms and methodology described in the paper can be readily extended to higherorder and semi-Markov processes. What we have described so far is a first-order discrete-time hidden Markov model -a diagrammatic representation is shown in Figure 1  is just a normalizing constant to ensure that the state probability estimates at time t sum to 1. Note that these equations are usually written in terms of a variables in the speech recognition literature. In a similar manner, at time i, one can calculate the probability of state j at time t -k given only the data which has occurred between time tas: rf-~ = {lJ(t),lJ(t -1),..., g(t -k+ l)}. Analogous to the previous recursion, but now conditioning on after time t -k one has k and time t, defined data which occurred  Equations (2), (4), and (5) are the basic estimation equations for online monitoring. Given the above monitoring equations it remains to determine the Markov model structure and parameters in order to implement the method for a particular problem. The key point in the Markov monitoring approach (previously introduced in [6] and [7]) is that the transition probabilities are not estimated from the data (as in speech modeling), but rather are chosen a priori based on the long-term temporal characteristics of the system and prior knowledge concerning the system failure modes. Note that the use of this prior information is essential in applications of this nature in the sense that there is often no alternative practical method by which to estimate these probabilities. For example, in speech modelling one can use estimation algorithms (such as the Baum-Welch algorithm) to estimate the probabilities via maximum likelihood methods directly from data. In online monitoring however, sequences of data containing normal-fault transition information are not likely to be available. Hence, prior knowledge must be used to determine the probabilities in the matrix A. In particular, the mean time spent in the normal state WI of the model should be equal to the mean time between failure (MTBF) of the observed system. For a 5 first-order Markov system the expected length of time I spent in state q, given that it starts in state WI, is In practice the MTBF of a particular system is typically either available from databases of trouble reports or can be inferred system). Given all, the all terms ( Hence, the exact nature of the HMM matrix is highly dependent on the particular operational scenario under which the model is being used. A more detailed discussion on the design of HMM parameters is given in [7]. Earlier we showed that the problem of estimating the probability of any state at time t based on a particular sequence of observed data (either before, or after t, or both) can be expressed in recursive form. A central component in the recursion is the calculation of the instantaneous observable-state conditional probability, ~(y[~j), namely the probability of observing the data y supposing that the system is in state - Consider the problem of estimating p(y]wj) for a specific state ~~j. The density function can be either chosen directly in the form of an explicit parametric model (for example, a multi-variate Gaussian model) or could be estimated implicitly from data via non-parametric methods such as multi-variate kernel density estimation [8, 9]. In the parametric model case, the parameters of the model can in turn either be chosen based on prior knowledge of the system characteristics under fault and normal conditions, or can be estimated from data. The data-based estimation procedures (whether parameter fitting for a specific model or the entirely non-parametric approach) requires that observed data is available for state w j . This is usually not a problem for the normal state q. Indeed data can often be generated for common fault states which are easy to emulate in hardware -later we will describe results using this data-dependent approach. It is worth noting that the dimensionality of the observable variable Y can have a distinct effect on one's ability to estimate the functional form of the model ~(gluj). The larger the dimensionality the more parameters must be estimated (in the parametric case) and the sparser the data (in the non-parametric case), hence, the "curse of dimensionalityn may apply. One approach to alleviating this problem is to use Bayes' rule and work with the posterior or discriminative probabilities of the states given the observable. It is straightforward to show that the recursive mation equations derived earlier (see Equation (2)) can equally well be discriminative form: where 11{ is a normalization constant as before to ensure that the state probability estimates at time t sum to unity, and p(~j) is the prior probability of state j. This is equivalent to the previously derived recursion relation by virtue of Bayes' rule: In a manner exactly analogous to that of Equations (4) and (5), one can also derive equivalent recursion relationships for using all the observed data to time t, @~, to estimate the probability of a state at time i -k. The advantage of this discriminative formalism is that estimation of the discriminative probabilities tends to scale better (in terms of estimation) with dimensionality (of the observable) and is less sensitive to particular distributional assumptions about the observable, than the alternative approach of modelling ~(y[~i) directly. Can--didates for estimating such discriminative probabilities directly from data include logisitic discrimination [1 O] and feedforward neural network models [1 1]. In previous work [6, 7] we have described the application of the Markov monitoring approach to online failure detection in antenna pointing systems which are used to steer large 34 and 70 meter ground antennas of the DSN during tracking of various deep-space spacecraft. (-x)) ). The network weights were estimated ("trained") via a conjugate-gradient variant of the backpropagation algorithm to minimise the empirical log-likelihood [13, 14]. Under appropriate theoretical conditions it has been shown elsewhere [15, 16] that the outputs of such a trained network converge to the true a posterioti probabilities as the training sample size gets large. Hence, although 9 in practice one only has a finite training sample size, and the architecture of one's network model may be biased, it is reasonable to interpret the network outputs as estimates of the posterior probabilities of the states given the observable. Results with both the mixture and neural models (without any HMM component) are shown in Figures 3a and 3b respectively. The vertical axes represent various posterior probability estimates of the states ~(~i II), while the horizontal axis represents time in minutes, The system begins in the noisy tachometer fault state, switches to the failed tachometer state, switches back to the normal state, switches to the amplifier fault state, and finally returns to normal. Note that neither model is particularly accurate in tracking the states and that there is a tendency to switch around between states. This is a direct consequence of ignoring the temporal aspect of the problem, i.e., ignoring the fact that the fault and normal states do not occur randomly in time but tend to persist. It can also be seen in Figure 3a that the mixture model's probability estimates tend to be near either O or 1 indicating sharp decision boundaries and perhaps overfitting (the widths of the component Gaussian mixtures may be too small). The neural network model on the other hand provides smoother estimates. A simple HMM was designed to model temporal context. All states were chosen to be equally likely and the probability of changing to a different state was assigned as 0.01, resulting in a probability of remaining in the same state of 0,97 (this corresponds to an effective expected duration in any one state of 2 minutes for our simulated problem). Note that in a practical situation the transition probabilities would tend to be much closer to O or 1 in order to model realistic MTBF's, The depth of the backward recursion (k in equations (4) and (5)) was set to 5 time steps: empirically it was found that setting k any greater than this resulted in no change in the estimates. Thus there is a latency of 5 x 4 = 20 seconds before the systems produces its estimate of the state probabilities for time t. Figures 4a and 4b show the results obtained when this Markov transition matrix was used to correlate the estimates from Figures 3a and 3b , the mixture model and neural network state estimates, respectively. There is some improvement gained by introducing the HMM for the mixture model, for example, the number of false alarms (fault probabilities greater than 0.5 when the true state is normal) is somewhat reduced, However, overall the quality of the state probability estimates produced by the mixture model are poor enough that adding temporal context (in the form of the 10 HMM) does not significantly improve the overall quality of the model's estimates. For the neural-HMM combination (Figure 4b) , however, there is a dramatic improvement in performance. Apart from some mislabeling of the tachometer noise state, the model tracks the states almost perfectly. The lack of stability evident in Figure 3b (without the HMM) is completely removed, i.e., the introduction of appropriate temporal cxmtext removes any ambiguity about the identity of the states. Of the 4 responses plotted in Figures 3 and 4 , due to its combination of low false rate and accurate detection, the neural-HMM combination in Figure 4b is the only one which is accurate enough for actual operational use in DSN ground stations. Detecting Unknown States The assumption that there are m known mutually exclusive and exhaustive states (or "classes" ) of the system, o ] , ..., w~ bears further investigation. The "mutually exclusive" assumption is reasonable in many applications where multiple simultaneous failures are highly unlikely. However, the exhaustive assumption is somewhat unrealistic. In particular, for fault detection in a complex system composed of hundreds of thousands of components, there are a myriad of possible fault conditions which might occur. The probability of occurrence of any single condition is very small, nonetheless there is a significant probability that at least one of these conditions will occur over some finite time. As an example, for the antenna application, there are a few well-known faults (such as tachometer failures) which occur with regularity and can be assigned specific fault states in advance; however, it is not practical to assign states to all the other minor faults which might occur. Hence, the question must be asked as to whether or not a discrirninant classifier trained to distinguish data from m states, can identify data from a different, or novel state. The answer lies in a simple application of Bayes' rule. If the classifier is a pure cZiscriminant, i.e., it directly models the posterior probability p(tii[y), then it is -implicitly relying on the assumption of exhaustivity and cannot in principle detect novel data. A good example of this type of classifier is a feedforward neural network using sigmoidal activation functions. Essentially, if one gives such a trained network new data which is far away from the training data in the feature space, it will produce  To alleviate the fact that discriminative models may not detect novelty, but that generative models may have poor discriminative capabilities in many dimensions, we propose a hybrid classifier which uses both a generative and discriminative classifier in parallel. The model is based on the simple idea of adding an "m+ 1 th" state to the model to cover 'all other possible states" not accounted for by the known m states and modifying the probabilistic updating equations appropriately. Let the symbol w{l,,..,~} denote the event that the true system state is one of the known states, and let p (u{l,...,~}[y) be the posterior probability that the data is from the known state given the observed data y. Hence, one can estimate the true posterior -probability of individual known states as P(~ilY) = Pd("ilYt u{l,...,m} )P(u{l,m}l!J),!J), 1 S 2< ?n (8) --where pd(wi 1~, W{],...,m } ) is the posterior probability estimate of state z as provided by a discriminative model (such as the neural network described earlier). Thus, the posterior estimates of the hybrid classifier are conditioned on whether or not the data comes from one of the m known classes. The calculation of p(w{l ,...,~} 1~) can be obtained as follows. Assume for the moment that p(y[w~+l ), p(w~+l ), and p(ylw{l,...,~}) are all known. Thus we have by -Bayes' rule that P(@{l,...,rn}ly) = P(~l"{l,...,m}) P(~{l,m}),m}) P(~l"m+l)P(wm+l ) + P(!Jlw{l,...,m}) XT P("i) " and of course Since by definition p(w{l ,...,.,}) = 1 -p(~m+~), we must define a prior probability of being in an unknown state. This is based on the designer's prior belief of how often the system will be in this unknown state -a practical choice is that the system is at least as likely to be in an unknown failure state as any of the known failure states. The p(~lu{l,...,m}) term in Equation (9) is provided directly by the generative model, i.e., whereas the discriminative model provides direct estimates of p~(~i II, U{l,...,m}), the generative model provides estimates of the data given the states -hence, the notion of running a discriminative and generative model in parallel. The generative model need not necessarily use the full dimensionality of the input space, particularly if the dimensionality is large. A mixture model of the form P(!Jl"{l,...,m}) = ~ f(~lwi)P(w:) (lo) i=l is a natural choice, where in turn, the individual ~(yl~i) components in the mixture -could be chosen as unimodal parametric models (such as Gaussian), or mixture models (thus giving a hierarchical mixture model overall), or nonparametric kernel density estimates, The hierarchical mixture model provides a reasonable trade-off between model flexibility and complexity in practice, Finally, the density of the observable data given the unknown state, p(~lwm+l ), must be defined in Equation (9), This requires the use of non-informative 13ayesian priors for p(ylum+l) over a bounded space of feature values, i.e., the maximum en--tropy choice of priors which reflect the least amount of prior information. Typically this requires that we have some knowledge of upper and lower bounds on the possible feature values -with no prior knowledge on the nature of unknown faults a uniform density over this space is usually appropriate. Note that the stronger the bounds which can be placed on the features, t}]e narrower the prior density, and the 13 better the ability of the overall model to detect novelty. If we only have very weak prior information (very wide bounds), this will translate into a weaker criterion for accepting points which belong to the unknown category. The extension of the hybrid model to a HMM is straightforward, The number of states is now m + 1 instead of m, i.e., the 'unknown n state is explicitly modelled within the HMM. The necessary state-observable probabilities (as required for the HMM recursion) are calculated directly from Equations (8) and (9), i.e., the parallel generative/discriminative models are combined to provide estimates of both p(~il~(t)), 1 ~ i ~ m and p(w~+l Iy(i)) at each time instant. The transition proba--bilities between the known and transient states must be consistent with our choice of prior probability p(w~+l ), i.e., the relative likelihood of an unknown state. In addition, the self-transition probability of the unknown state reflects our prior belief concerning the typical duration of such states -in practice, multiple unknown states with different self-transition probabilities could be used to represent a range of possible conditions from short transient faults to longer-term "hard" failures. Experimental Results on Detecting Novel States To test the hybrid model the following experiment was conducted using the same data as described in Section 3. In the training phase of the model the training data for one of the known states was omitted entirely, i.e., the model was trained on 3 states instead of 4. Then, using the approach of Section 4, a hybrid model to detect unknown states was constructed in the following manner: q A discriminative classifier (the same feedforward neural network as described in Section 3) was trained using all 12 features to provide estimates of pd(~il~,~{l,.,.,m}), 1 S ~ S 3. q A generative model consisting of a hierarchical mixture model (Equation (10)) was fitted to the training data using only 3 features derived from the motor cur-14 rent signal; the two coefficients of a second-order autoregressive model (AR(2)), #l andq$2, and the standard deviation, a. Hence, y= (@l, #z, a). These features were chosen empirically on the basis of their being the most informative about changes in the system state -using all 12 features would not have been practical given that only 75 data points were available for the fault states. The individual mixture components were themselves a mixture of 3 Gaussian components with diagonal covariance matrices -the mixture weights and component parameters were estimated via the EM algorithm. q The prior probabilities of the 3 known states and the unknown state were set uniformly, i.e., to 0.25, q A 4-state HMM was designed; 3 known states plus 1 unknown state, all with equal prior probability and, as before, with probabilities of 0.01 of changing to any another state. k = 5 was again used as the backward recursion depth.  It will be assumed that the estimated coefficients are in fact stationary. Equation (11) thus provides bounds on the possible parameter values. A uniform density is specified over all such allowable values of #l and 42. Of course, this does not allow for the fact that in practice (and in particular for fault conditions) there is no guarantee that the estimated coefficients will obey these bounds. The following approach is adopted: if the estimated coefficients lie outside the bounds of the stationary region then the probability of the unknown state p(w~+l Iy) is set to 1. -The third parameter, the standard deviation of the voltage from the Hall effect sensor which measures motor current, is normally about 20mv under normal conditions. Based on experience from observing the motor current signal under a variety 15 of conditions it is estimated that under any fault condition the standard deviation should not exceed 1 volt. Hence, in the absence of any other prior information, a uniform density is placed on the standard deviation over this range O to 1 volt for a. This density is assumed independent of the AR(2) coefficient density, i e., the overall prior density is the product of the two. We conducted the experiment (of leaving a particular fault out of the training data set) twice; first the noisy tachometer fault was omitted, then the amplifier fault. Figure 5a shows the response of the discriminative model alone (the feedforward neural network probability estimates coupled to a 3-state HMM) to the test data which contains an 'unknown" fault, namely a noisy tachometer. The figure shows that the noisy tachometer fault is misclassified as a failed tachometer. Figure 5b shows the response when the hybrid model is run on the same data. Although there is some confusion between the unknown state and the failed tachometer state, the model clearly identifies that there is an unknown state present, i.e., the probability of an unknown state is usually close to 1 during the presence of the unknown noisy tachometer fault. Interestingly enough, the model also picks up a possible unknown transient which occurred during the simulation of the failed tachometer fault. In the second experiment, the amplifier fault was removed from the training data but was present in the test set. Figure 6a shows the response of the discriminative 3-state HMM (no explicit model for unknown). Whereas in the previous experiment the unknown fault condition was merely classified incorrectly as being a different fault, here the unknown fault is almost completely missed, i.e., it is largely misclassified as being normal. This is exactly the type of problem which can arise when using discriminative models when the exhaustivity assumption is not met, namely, novel states can go undetected simply because they happen to sit on the "normal" side of the estimated decision boundaries. Figure 6b shows the response of the hybrid model to the same data. Now, although the unknown fault is not detected in its entirety, it is partially detected in the unknown category. As before, some of the tachometer fault data is also classified as being of the unknown variety, perhaps indicating various transients in the data. Masson [25] , is to use only a generative model in the model and thus detect outliers via distance thresholds, e.g., the distance from the mean in a parametric model, or the distance from the nearest training set point in near-neighbour or kernel models. The disadvantage of threshold-based methods lies in the selection of the thresholds themselves; without some hypothesis for data from the unknown state there is no principled way to choose such thresholds. In contrast, the probabilistic model for detection of unknown states which we have proposed in this paper, while requiring significant prior knowledge on the part of the designer, is a more principled approach in that it makes quite explicit the various assumptions which surround the novelty detection issue. It forces the system designer to assign specific prior hypotheses to the prior density of the data conditioned on a novel event, Hence, the problem is framed explicitly in terms of comparing specific 17 # , hypotheses for known and unknown events. In this paper the Markov monitoring approach has been extended to allow for detection of system states which were unknown a pn"ori. This has significant impact for practical applications where novel events are far more likely than in a controlled laboratory environment. The proposed model was tested on data from a real-world fault detection application and clearly demonstrated its ability to detect previously unknown states -conversely, the model which assumed that unknown faults had a prior probability of zero either misclassified an unknown fault into another fault state or did not detect that any fault was present. Acknowledgements
Bayesian reasoning used by Smyth REF to monitor and diagnose the state of an antenna is applicable to the management of a system with a small number of possible states.
Markov Monitoring with Unknown States
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS
Computer Science