Distance metrics for universal pattern processing tasks

This Application claims priority to the Provisional Application No.: 60/911,333, which is referred to by filed on Apr. 12, 2007, and incorporated herein by reference.

1. Field of the Invention

The present invention relates to universal pattern processing tasks.

2. Description of the Related Art

Universal pattern processing tasks include at least any process that involves pattern recognition tasks (e.g speech or image recognition), segmentation (e.g. audio segmentation), identification (e.g. speaker), verification (e.g. speaker), search, translation, text-to-speech, information retrieval, audio-retrieval, image retrieval, language processing tasks, summarization, simplification etc.

In general, in universal pattern processing tasks such as classification, segmentation, translation, search etc., the best model is identified as follows. Let F(Y,λ) be some score (e.g. likelihood score) function that characterizes a model λ given data Y. Then the “best” model could be found by the following rule:

{tilde over (λ)}=argmax λεΘ F ( Y, λ)   (1)

where Θ is a family of models.

That is, the quality of the model was measured by how well the model fit the data. A likelihood score is calculated between the model and the data, and if the likelihood score is high, then the model fits the data well. To have a function such as matching maximum likelihood to match a model to data, the function and data must be trained. The likelihood score measured how well the data fit the model.

This method in most cases does not give perfect processing recognition accuracy. Thus, a need exists for additional methods to improve pattern processing in various tasks.

The universal distance pattern processing technique in this invention can be described generally as follows.

The technique of the present invention was developed with training a model on test data. Different models for decoding are available, such that if one model is correct, others are incorrect. The present inventors have found that a model for correct decoding is changed less than other models when trained on test data.

That is, the present invention applies data to a set of models, and measures the change of model before and after the data is applied. By identifying which model is changed the least by the data, the present invention does not measure how well the data fits a model, but instead indicates which of several models is the best fit to the data.

Assume that there have been identified several models λεΘ as models that may represent some data Y, and one needs to identify which model best characterizes the data Y. We can update or train each of the models λεΘ using data Y. During such updating or training, each of the models λεΘ changes in response to the input data Y. In general, the model that best fits the data will change the least. Therefore, determining which model changed least when the models were exposed to the data can identify a best fitting model.

More specifically, define T (Y, λ) as a ratio of a model change in some metrics when a model λ was exposed to data Y. Then the “best” model can be defined by the following rule:

{tilde over (λ)}=argmin λεΘ T ( Y, λ)   (2)

where Θ is a family of models.

Incidentally, implementation of this concept is described herein as used on Hidden Markov Models (HMM), but it can also be applied to various other different kinds of models.

In a first exemplary aspect of the present invention, described herein is a universal pattern processing system that receives input data and produces output patterns that are best associated with this data. The system transforms models using the input data, and then associates output patterns with original models that are changed least during this transformation process.

The foregoing and other purposes, aspects and advantages will be better understood from the following detailed description of an exemplary embodiment of the invention with reference to the drawings, in which:

FIG. 1 shows basic operation of a universal pattern distance decoder embodying the present invention;

FIG. 2 shows operation of a pattern distance decoder of the present invention;

FIG. 3 shows operation of a models transformator of the present invention;

FIG. 4 shows operation of a models comparator of the present invention;

FIG. 5 shows distance computation in the present invention;

FIG. 6 shows a flow chart of an embodiment of the claimed method;

FIG. 7 illustrates an exemplary hardware/information handling system 700 for incorporating the present invention therein; and

FIG. 8 illustrates a signal bearing medium 800 (e.g., storage medium) for storing steps of a program of a method according to the present invention.

Distance HMM Metrics

In this section is described a method for computing Extended Baum-Welch Transformations (EBW) distance T for Hidden Markov Models (HMM). In general, the EBW distance T (Y, λ) between data Y and a model λ can be used to find the “best” model by the following rule:

{tilde over (λ)}=argmin λεΘ T ( Y ,λ)   (3)

where Θ is a family of models.

In order to apply this distance to some HMM M with continuous Gaussian parameters, one can choose the best path S=s 1 , . . . s n in this HMM model. The likelihood of this HMM becomes the product

Q = ∏ i = 1 n ⁢ q i ( 4 )

where each q i is a mixture of Gaussian components

∑ k = 1 r ⁡ ( i ) ⁢ w ik ⁢ N ( y i , μ ik , ∑ ik )

(or some Gaussian components

q i =w ik N ( y i ,μ ik(i) ,Σ ik(i) )  (5)

if the best state path is taken along Gaussian components in mixtures).

Applying distance T to HMM consists of the following steps:

1) Application of T to likelihood score for the best HMMpath by using the multiplicative property of T that allows to represent T (F 1 *F 2 ) as T(F 1 )F 2 +F 1 *T(F 2 ). Using this property, we represent T(Q)/Q as ΣT(Q i )/Q i for the likelihood score of the best path. Such representation is attractive because this expression is smaller if T(Q i ) is smaller and Q i is bigger. Note that the definition of T in this representation depends on the function Q i and on EBW transformation of μ and Σ. This transformation depends on Q.

2) Computing the full likelihood score (for all HMM paths) by extending forward-backward algorithm to T.

To understand further, first review the following definitions. EBW transformations can be described as follows: Let F(Z)=F(Z ij ), i=1, . . . n, j=1, . . . m be some function in variables Z=(Z ij ), and differentiable at Z=zεR nm . Let

c ij = c ⁡ ( F ) ij = c ⁡ ( F , z ) ij = z ij ⁢ δ δ ⁢ ⁢ z ij ⁢ F ⁡ ( z )

(we can drop z and/or F in c(F,z) ij if it is clear from the context).

I. Gaussian Mixture Densities:

μ ^ j = μ j ⁡ ( F , α ) = ∑ i ∈ I ⁢ c ⁡ ( F , z ) ij ⁢ y i ⁢ α + μ j ∑ i ∈ I ⁢ c ⁡ ( F , z ) ij ⁢ α + 1 ( 6 ) σ ^ j 2 - σ j ⁡ ( F , α ) ⁢ 2 = ∑ i ∈ I ⁢ c ⁡ ( F , z ) ij ⁢ y i 2 ⁢ α + ( μ j 2 + σ j 2 ) ∑ i ∈ I ⁢ c ⁡ ( F , z ) ij ⁢ α + 1 - μ ^ j 2 ⁢ ⁢ where ( 7 ) z = { z ij } = { 1 ( 2 ⁢ π ) 1 / 2 ⁢ σ j ⁢ ⅇ - ( y i - μ j ) 2 / 2 ⁢ σ j 2 } ( 8 )

and y i is a sample of training data.

II. Multidemensional Multivariate Gaussian Mixture Densities:

μ ^ j = μ j ⁡ ( F , α ) = ∑ i ∈ I ⁢ c ⁡ ( F , z ) ij ⁢ y i ⁢ α + μ j ∑ i ∈ I ⁢ c ⁡ ( F , z ) ij ⁢ α + 1 ( 9 ) ∑ ^ j ⁢ ⁢ = ∑ j ⁢ ⁢ ( F , α ) = ∑ i ∈ I ⁢ c ⁡ ( F , z ) ij ⁢ y i ⁢ y i T ⁢ α + ( μ j ⁢ μ j T + ∑ j ) ∑ i ∈ I ⁢ c ⁡ ( F , z ) ij ⁢ α + 1 - μ ^ j ⁢ μ ^ j T ( 10 ) where z = { z ij } = { z ⁡ ( F , α ) ij } = {  Σ j  - 1 / 2 ( 2 ⁢ π ) d / 2 ⁢ ⅇ - 1 / 2 ⁢ ( y i - μ j ) T ⁢ ∑ j - 1 ⁢ ( y i - μ j ) } ( 11 ) z ^ = { z ^ i , j } = z ⁡ ( F , α ) ij } = {  Σ ^ j  - 1 / 2 ( 2 ⁢ π ) d / 2 ⁢ ⅇ - 1 / 2 ⁢ ( y i - μ ^ j ) T ⁢ Σ ^ j - 1 ⁡ ( y i - μ ^ j ) } ( 12 )

and y i T =(y i1 , . . . y in ) is a sample of training data.

The Distance Definition

Consider one model

λ={μ,Σ}  (13)

and

{tilde over (λ)}=λ( F ,α)={μ( F, α), Σ( F ,α)}  (14)

Let Y=Y 1 n ={y 1 , . . . y n } be a sample of test data. For each frame y t define

p ( y t ⁢  λ ) =  Σ  - 1 / 2 ( 2 ⁢ π ) d / 2 ⁢ ⅇ - 1 / 2 ⁢ ( y t - μ ) T ⁢ ∑ i - 1 ⁢ ( y t - μ ) = z t ( 15 )

Let G({Z t })be a function that is differentiable at {z t }. For example, G is a log-likelihood function:

G ⁡ ( { z t } ) = log ⁢ ⁢ p ( y 1 n ⁢  λ ) = ∑ t = 1 m ⁢ c t ⁢ log ⁢ ⁢ p ( y t ⁢  λ ) = G ⁡ ( { z t , t = 1 , … ⁢ ⁢ n } ) ( 16 )

Using EBW transformations (9) and (10) λ→{tilde over (λ)}=λ( F ,ε), {z t }→{{circumflex over (z)} t }={z t (F,ε)} we get an initial part of the Taylor series

G ({ z t ( F, ε)})= G ({ z t })+ T (λ, F,G )ε+ o (ε)   (17)

We write T (F, G), if λ is clear from the context. We set T(λ,F,G)=T(λ,F) (or T(F)) if F=G. For F=G the distance T in the above formula was computed in D. Kanevsky, “Extended Baum Transformations for General Functions, II”, tech. Rep. RC23645(W0506-120), Human Language technologies, IBM, 2005. It was shown there that it is always non-negative.

Model Tying

In the likelihood expression for the best HMM path (4) some different q i can be represented by the same set of models M i ={μ ik(i) ,Σ ik(i) } from a mixture (5) for different subscript i. Let us introduce a map L of subscripts iε[1, . . . N] of M i on a set S such that L(i)=L(j)εS for any i, jε[1, . . . N] iff Mi=My. Then the product (4) can be represented as

Q = ∏ s ∈ S ⁢ Q s ( 18 ) where ⁢ ⁢

⁢ Q s = ∏ { i ∈ [ 1 ⁢ … ⁢ ⁢ N ] ⁢  L ⁡ ( i ) = s } ⁢ Q i ( 19 )

Let split a data Y=y 1 , . . . y T into subsets of frames

Y s = { y i ⁢  L ⁡ ( i ) = s } ( 20 ) Then ⁢ ⁢

⁢ T ⁡ ( Q ) = Q ⁢ ∑ { s ∈ S } ⁢ T ⁡ ( Q , Q s ) / Q s ( 21 )

where T(Q, Q s ) is associated with a subset of frames Ys. This tying may allow to increase a number of frames associated with each model in a distance expression for T.

Some Details on EBW-Distance for HMM

Let {right arrow over (S)} n ={s(1), . . . s(n)} be a sequence a path in some HMM, i.e. a sequence of n states. Let Y 1 n ={y 1 , . . . y n } be an observed vector.

EBW State Distances

Let p(y t |s t )=Σ k w k N(y t |s(t))=Σ k w k z t k =p({z t k }) be a Gaussian mixture. Define an EBW distance associated with a state s(t) and a frame y t as T(y t |s(t))=T(p({z t k }). Define normalized EBW distance associated with a state s(t) and a frame y t as (Normalized State Distance)

NST ( y t |s ( t ); α)= T ( p ({z t k })/ p ({z t k } a   (22)

where α is some positive number. For every path {right arrow over (S)} n and a vector Y 1 n one can define its quality as sum of normalized state distances along this path:

The smaller NST(Y 1 n |{right arrow over (S)} n ;α) is, the better the data Y 1 n is explained by this HMM path {right arrow over (S)} n . For all paths in HMM {right arrow over (S)} r n and a vector Y 1 n one can define HMM quality as sum of normalized state distances along all these paths:

The less NST(Y 1 n ;α) is, the better the data Y 1 n is explained by this HMM. The computations in (23 and 24) can be done by suitable modification of Viterby and forward-backward algorithms.

EBW State Distance Probability

We can associate with each HMM state distance a probability density as follows.

f ( y t |s ( t ))= D*e −T(y t s(t))   (25)

With this probability distribution associated with HMM states one can apply standard HMM technique, where D is a normalized number (to turn f( ) into probability density).

Turning now to FIG. 1 , Block 100 denotes any kind of data input: text data, signals (e.g. audio, video, media, biometrics), binary data (e.g. compiled code) etc. Block 101 represents a universal pattern distance decoder (e.g. speech recognizer for audio media, image recognizer for video media, identification for biometric media etc.). The pattern distance decoder 101 will be described in a different figure. Block 103 denotes output from 101 —some patterns that are associated with data 101 via Block 101 (for example, segments for segmentizer, classes for classifier, decoded words for speech recognition, translation for machine translation, biometrics for speaker identification, search queries for a searching engine etc.).

Turning now to FIG. 2 , this figure describes in more detail the universal pattern distance decoder 101 . Block 202 denotes original models that were trained on some training data prior to pattern recognition process (for example, Gaussian models that were trained on audio data before a decoding on a test data). Block 203 denotes test data (e.g. audio) that should be processed for some pattern recognition tasks using models from 202 . Block 203 transforms models from 201 using test data from 203 (for example, trains Gaussian models on test data 203 using Extended-Baum-Welch transformation (9, 10) that were described in the Summary). The outputs of 203 are transformed models 204 (that were adapted to test data 202 ). These transformed models are fed to Block 205 Transformed vs. Original Models Comparator, which compares transformed models 203 to original models 201 using metrics (as described in FIG. 3 ). After 205 identifies transformed model that points to the best original models it labels best original models (e.g. choose the best decoding words in a speech recognition process, or the best matching speaker in the speaker identification process).

FIG. 3 provides explanations to 200 (Models Transformator). The block 300 (updater of model parameters) updates original models 201 using controlling 301 parameters for training process (one example of such controlling parameters (α) could be found in (9, 10)). They control how much (and how fast) models are updated while they are exposed to data Y.

For example, the following are examples of processes that could be used to update models:

Supervised Training Unsupervised Training Maximum likelihood training Maximum entropy training Baum-Welch update Expended Baum-Welch update Bayes network Mutual Information Training

There can be several iterations in such updating process. The block 303 breaks update iterations using some criteria (e.g. a default number of iterations that were defined on training data). The output of this updating process is transformed models 203 .

FIG. 4 provides explanations to 204 (Models Comparator). Block 400 is a score producer. Given test data, it produces scores 401 for original models 201 and scores 402 transformed models 203 using some metrics (for example, F(Y, λ) for original models λ and F(Y, λ) for transformed models {tilde over (λ)} where F(Y, λ) is some score function (3) that characterizes a model λ given data Y). In Block 403 (Computation of Distance between original and transformed model scores), these scores 401 and 402 are used to compute a ratio with which transformed models are changed when they were exposed data. Different metrics could be used to measure this change. Details of such metrics are described in FIG. 5 .

FIG. 5 provides explanations to 403 (Distant Computation). Block 500 provides control parameters (the same as 301 ) that are used to update models. For example, by varying a in (9, 10), one can get a parametric curve. Tangents hyperplanes to such control parameters manifold can characterize flatness of manifolds (e.g. tangents to a parametric curve represented by ( 9 , 10 ) measure flatness of this curve). The flatness of parametric manifold usually represent the quality of models (the flatter the manifold, the better data is explained by the model). Block 502 provides metrics to represent quality of models (it chooses models that provide minimal changes to associated structures). These metrics can be represented as slopes (difference) for scores of transformed and original models, as tangent (slopes) to parametric curves or used Vector support machine to separate tangent hyperplanes to control parametric manifolds that represent different classes.

FIG. 6 is a flow chart of the invention. Block 600 —the universal pattern processing system gets test data and in Block 601 the pattern processing system gets a set of models representing different events (e.g. classes, words, speakers etc.). Then the pattern processing system chooses criteria for training on test data (e.g. maximum likelihood, or maximum entropy, maximum mutual information) and also values for control parameters that control training. In Block 603 the pattern processing system updates each model in 601 using data from 601 . In Block 604 the pattern processing system measures change in each updated model in comparison with original models. In Block 605 the pattern processing system chooses the event whose associated model changed least as the decoding result of this pattern process.

Exemplary Hardware Implementation

FIG. 7 illustrates a typical hardware configuration of an information handling/computer system in accordance with the invention and which preferably has at least one processor or central processing unit (CPU) 711 .

The CPUs 711 are interconnected via a system bus 712 to a random access memory (RAM) 714 , read-only memory (ROM) 716 , input/output (I/O) adapter 718 (for connecting peripheral devices such as disk units 721 and tape drives 740 to the bus 712 ), user interface adapter 722 (for connecting a keyboard 724 , mouse 726 , speaker 728 , microphone 732 , and/or other user interface device to the bus 712 ), a communication adapter 734 for connecting an information handling system to a data processing network, the Internet, an Intranet, a personal area network (PAN), etc., and a display adapter 736 for connecting the bus 712 to a display device 738 and/or printer 739 (e.g., a digital printer or the like).

In addition to the hardware/software environment described above, a different aspect of the invention includes a computer-implemented method for performing the above method. As an example, this method may be implemented in the particular environment discussed above.

Such a method may be implemented, for example, by operating a computer, as embodied by a digital data processing apparatus, to execute a sequence of machine-readable instructions. These instructions may reside in various types of signal-bearing media.

Thus, this aspect of the present invention is directed to a programmed product, comprising signal-bearing media tangibly embodying a program of machine-readable instructions executable by a digital data processor incorporating both of CPU's identified as element 710 in FIG. 7 and hardware above, to perform the method of the invention. In addition, CPU 710 may exemplarily provide means for processing input means receiving and processing input data and a set of models, each model in the set of models representing a different event. CPU 710 may exemplarily universal pattern decoder means including transforming means, the decoder transforming models using the input data and associating output patterns with original models that are changed least during the transforming, the universal pattern decoder means being configured to select criteria for training the set of models and selecting control parameters, which control how fast and to what degree a model is transformed while the model is exposed to the input data as well as output means outputting best associated patterns chosen by the universal pattern decoder. Additionally, CPU 710 may provide a processor including a change determination unit configured to apply the input data to the set of models to transform the set of models, and configured to determine which of said models is changed least during the transforming.

This signal-bearing media may include, for example, a RAM contained within the CPU 711 , as represented by the fast-access storage for example. Alternatively, the instructions may be contained in another signal-bearing media, such as a magnetic data storage diskette 800 ( FIG. 8 ), directly or indirectly accessible by the CPU 711 .

Whether contained in the diskette 800 , the computer/CPU 711 , or elsewhere, the instructions may be stored on a variety of machine-readable data storage media, such as DASD storage (e.g., a conventional “hard drive” or a RAID array), magnetic tape, electronic read-only memory (e.g., ROM, EPROM, or EEPROM), an optical storage device (e.g. CD-ROM, WORM, DVD, digital optical tape, etc.), paper “punch” cards, or other suitable signal-bearing media including transmission media such as digital and analog and communication links and wireless. In an illustrative embodiment of the invention, the machine-readable instructions may comprise software object code.