| Yoshinao Shiraki Chief Researcher Information Science Research Laboratory NTT Basic Research Laboratories |
|
| Yoshinao Shiraki Chief Researcher Information Science Research Laboratory NTT Basic Research Laboratories |
1 Introduction
Let's consider a phenomenon where the signals and the positions (states) change over time like speech and gestures. Here, we call it pattern recognition to find a certain similar pattern in such a phenomenon and find out the "meaning" of the "collected patterns." I would like to discuss in this paper the benefits of Dynamic Programming (DP: Dynamic Programming [DP, Sakoe]) in pattern recognition. Especially, we would like to proceed the discussion comparing DP with the Hidden Markov Model (HMM [HMM1]).
HMM was formulated at practical level in 1983 [HMM2] and serve as an important basic technology in speech recognition. Main feature of HMM is to consider a phenomenon (feature signal) as "something which moves among several states." HMM divides a phenomenon into "several states" and indicates the meaning of signals by "transitions among states." For instance, speech signals are expressed as a phonetic symbol sequence by corresponding one "sound" to a "transition among three states" using phonetic symbols (considering the continuity of phonemes to the preceding and following). Then, the recognition is carried out based on the occurrence probability of the phonetic symbol sequence. As such, HMM performs pattern recognition based on the probability of the state transition to determine if two phenomena are similar. Using the probability as a recognition criteria is another object to eliminate fluctuations in "patterns considered the same." The reason why HMM works well in speech recognition is considered because patterns (speech signals) and "phonetic symbols" (language) are closely related in speech, so it is easy to correspond (label) speech signals to "transitions among three states (viz., phonetic symbols)."
However, it is not easy for general signals to correspond other than speech (such as gesture motion images) to "states easy to find meaning." Since HMM has quite a few parameters, its estimation requires a vast amount of labelled data. "States," one of HMM's prominent features, may be considered as intermediates linking signals and symbols. Such intermediates worked well for speech. Conversely, whenever it is difficult to correspond signals to "states," pattern recognition is difficult as well. Thus, HMM requires a sufficiently great amount of labelled data well corresponded to "states" to give its full ability. In other words, HMM can be referred to as "heavy" (i.e., "heavy").
In contrast, DP works well as pattern recognition when given "the distance between phenomena" to consider two phenomena as "the same pattern." In doing so, DP eliminates fluctuations in "patterns considered the same" through time-scale warping. For instance, similarly uttered speech has different length. To consider two utterances as "the same pattern," a time-scale parameter should be given to DP. Fortunately, it is often relatively easy to set (estimate) a time scale parameter. Furthermore, DP does not require matching with "states" like HMM. That is, DP is "light-weight" (i.e., "light-weight"). With this, DP can be widely applied and easy to install into many kinds of pattern recognition problems.
2 DP vs. HMM: From the Standpoint of Applicability and Ease of Design
Therefore, let's compare the "weights" of HMM and DP from the standpoint of applicability perspective. Actual research examples shall be offered. First, I'd like to sketch a basic framework for pattern recognition.
2.1 Framework for Pattern Recognition
In general, pattern recognition consists of three steps:
1. Feature extraction step representing objects to be recognized appropriately;
2. Modeling step based on extracted features (parameter estimation controlling models);
3. Recognition step based on models (using predetermined "similarities" as criteria)
DP and HMM are involved in the second and third steps. These two steps are to eliminate or normalize fluctuations in objects both in time and space domain. This means that by ignoring time scale and slight offset in signals, two objects are considered as "the same pattern."
2.2 Relationship between Selection of Object Features and "Weights" of Recognition Models
Let's consider a case when there are several candidates for the features of objects and features should be selected with high recognition performance. In such cases, it is important to "focus on" good features quickly. For this, it is often desirable that models are "light-weight." In pattern recognition, it is often the case that features are not determined at the initial stage of research, and the selection of good features and the selection of models are often undertaken at the same time. In such situations where models may change, DPs light footwork as a model (i.e., short turnaround) is a big advantage.
2.3 Number of Model Parameters and Recognition Performances
While HMM has many parameters, DP has few parameters. In general, the number of model parameters and recognition performances are in a positive correlation. In other words, the more parameters, the higher recognition performance. But it requires that sufficient data be prepared for estimating parameters. In fact, when a sufficient amount of labelled data can be prepared, HMM shows superior performance to DP. This is roughly because HMM contains DP as a model, theoretically. Yet, in practice, to estimate parameters for HMM requires over 1000 times as much data as DP. For instance, while DP requires only one matching datum for recognition, HMM requires several thousand of data (mainly to learn deviation in state distribution).
2.4 Ease of Pattern Recognition and System Flexibility: Reference Pattern
It is a basic expected function for pattern recognition to find "a similar pattern." As an example, let's consider a case where "object to be searched = this pattern" is specified such as "Find objects similar to this pattern." This "object to be searched" is called "reference pattern" and the range in which a similar pattern is search is often called "input."
If this "object to be searched = reference pattern" is predetermined, it becomes a relatively easy pattern recognition problem. This is because the object to be searched is explicitly expressed as a "reference pattern," the "range" of length in time and signals are restricted. However, that "reference pattern" is predetermined poses restrictions on objects to be recognized, thus resulting in low flexibility of recognition systems.
On the contrary, in general cases where "reference pattern" is not predetermined, recognition systems may have high flexibility. However, this makes pattern recognition difficult because it has to create "reference pattern" at any point of time with any section length, while comparing with "input" (searching for match) at the same time.
As described in Section 1, HMM has a "state" as its basic unit. Because each "state" usually has a certain length in time, strong restriction in time is posed on patterns HMM can handle. Therefore, it is difficult in principle for HMM to deal with "reference patterns" with arbitrary length in time. On the other hand, DP can deal with this problem. Though, to make it a practical algorithm, many ideas such as reduction of computation time should be put into it.
2.5 Applicability and Ease of Design
The above-mentioned "light weight" of DP is due to its ability of easily incorporating heuristics with regard to fluctuations in objects to be recognized. In contrast, HMM automatically acquires (or learns) fluctuations in objects by using a statistical method. In short, DP is more advantageous over HMM when many design policies such as selection of features and heuristics for fluctuations are not determined. On the contrary, HMM has generally higher recognition performance when design policies are determined and sufficient learning data (for estimating parameters) can be prepared. In pattern recognition on a whole, design policies are not determined in many cases, which means that DP is more applicable.
2.6 Extension and Enhancement of DP by RWC Research Groups
Let's look at examples of actual problems to which DP is applied by RWC groups, considering the above descriptions on [RWC1, RWC2]. Here, the basic requirements for pattern searching are:
1. It should be applicable to signals without segmentation or recognition (labelling).
2. It should not exclude input outside a task.
3. It should be able to process input signals over time (so-called frame-wise).
4. The amount of similarity computation should be little and the amount of memory involved in computing should also be little.
In real environment, Requirements 1 and 2 correspond that there should be no restriction posed on utterances. Requirement 3 corresponds that speakers do not need to worry about the start and the end of utterances. Requirement 4 corresponds that it should process in real time. Requirements 1 and 2 mean that the goal is to build a flexible recognition system. They are quite natural in dealing with real environment. As described in Section 1, HMM can not satisfy Requirement 1, in principle, and requires drastic modification of the learning method for Requirement 3.
I to tackled Requirements 1, 2, and 3 with RIFCDP (Reference Interval Free Continuous DP) method, which is an extended DP. RIFCDP is designed so that pattern recognition is possible even if two time sequences of "reference pattern" and input have arbitrary section length and timing. This design makes it possible to handle general cases where "reference pattern" is not given, as described in 2.4. This means that RIFCDP suggests one of the very flexible recognition models in pattern recognition under real environment.
Nishimura, in addition, succeeded in reducing the amount of computation and memory to 1/16 and 1/50, respectively, of the conventional RIFCDP while preserving search ability. This was accomplished by introducing an exponential attenuation function into distance computing. By applying it to gesture motion images, the usefulness of this method was also verified.
We think RWC research groups, one can deduce, have truly gained insight into the essence of DP and steadily accumulated fruitful results both in theory and demonstration.
3 Summary
Thus far, DP and HMM have been compared as general theories of pattern recognition. The comparison was focused on "light-weightedness," namely applicability and ease of design. Such a perspective is often overlooked.
In light of all of this, HMM ought to justly be reconsidered, as it is only powerful under clear conditions, and the benefits of DP to be appreciated.
References
[DP]
Bellman, R., and R. Kalaba, Dynamic Programming and Modern Control
Theory. Academic Press, 1965.
[HMM1]
Jelinek, F. 'Continuous speech recognition by statistical methods,'
Proc. IEEE. 64, No.4, pp.532-556, 1976.
[HMM2]
Levinson, S.E., L.R.Rabiner et al. 'An introduction to the
application of the theory of probabilistic functions of a Markov process to
automatic speech recognition,' Bell Syst. J. 62, 4, pp.1035-1074, 1983.
[Sakoe]
Sakoe, Hiroaki, and Narumi Chiba, 'Continuous Speech Recognition
Based On Normalization In Time Using Dynamic Programming,' Journal of the
Acoustical Society of Japan. 27, 9, pp.483-490, 1971.
[RWC1]
Ito, Yoshiaki, Jiro Kiyama, et al. 'Reference Interval-Free
Continuous DP (RIFCDP) For Arbitrary Section Spotting Of Standard Patterns,'
Transactions of IEICE. D-II, Vol.J79-D-II, No.9, pp.1474-1483, 1996.
[RWC2],BR> Nishimura, Takuichi, Kiyoshi Furukawa, et al. 'On RIFCDP With Weight Attenuation For Time Sequence Pattern Searching,' Transactions of IEICE. D-II, 1998.