Distance measure for probability distribution function of mixture type

• US 6,993,452 B2
• Filed: 05/04/2001
• Issued: 01/31/2006
• Est. Priority Date: 05/04/2000
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Liu, Zhu, Huang, Qian
• Primary Examiner(s): Wachsman, Hal
• Assistant Examiner(s): Desta, Elias
• Application Number:
  US09/849,737
• Publication Number:
  US 20020069032A1
• Time in Patent Office: 1,733 Days
• Field of Search: 702/69, 702/110, 702/111, 702/124, 702/126, 702/158, 702179-181, 702/183, 702/189, 702/FOR.103, 702/104, 702/134, 702/139, 702/155, 702/170, 702/171, 706/12, 706/14, 706/15, 706 19- 21, 703/2, 703/5, 704200-201, 704/226, 704/231, 704/233, 704/240, 704/245, 704254-256, 704/500
• US Class Current: 702/179
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

In accordance with our invention, for two mixture-type probability distribution functions (PDF'"'"'s), G, H, $G\left(x\right)=\sum _{i=1}^N{\mu }_i{g}_i\left(x\right),H\left(x\right)=\sum _{k=1}^K{\gamma }_k{h}_k\left(x\right),$
where G is a mixture of N component PDF'"'"'s g_i (x), H is a mixture of K component PDF'"'"'s h_k (x), μ_i and γ_k are corresponding weights that satisfy $\sum _{i=1}^N{\mu }_i=1\mathrm{and}\sum _{k=1}^K{\gamma }_k=1;$
we define their distance, D_M(G, H), as $D_M\left(G,H\right)=\underset{w=\left[{\omega }_{\mathrm{ik}}\right]}{\min }\sum _{i=1}^N\sum _{k=1}^K{\omega }_{\mathrm{ik}}d\left(g_i,h_k\right)$
where d(g_I, h_k is the element distance between component PDF'"'"'s g_i and h_k and w satisfie
ω_ik≧0, 1≦i≦N, 1≦k≦K;
and $\sum _{k=1}^K{\omega }_{\mathrm{ik}}={\mu }_i,1\le i\le N,\sum _{i=1}^N{\omega }_{\mathrm{ik}}={\gamma }_k,1\le k\le K.$
The application of this definition of distance to various sets of real world data is demonstrated.

Claims

1. A method executed in a computer of computing a distance measure between first mixture type probability distribution functions, $G$

(x)=∑

i=1N⁢

μ

i⁢

gi⁡

(x),

pertaining to a set data collected from a first source, and a second mixture type probability distribution function $H<br><br>\left(x\right)=\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\gamma <br><br>}}_k<br><br>h_k<br><br>\left(x\right),$

pertaining to another set of collected data, the improvement characterized by;

said distance measure being $D_M<br><br>\left(G,H\right)=\underset{w=\left[{\mathrm{\omega <br><br>}}_{\mathrm{ik}}\right]}{\min }<br><br>\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}<br><br>d<br><br>\left(g_i,h_k\right),$

where d(g_i, h_k) is a function of the distance between component g_i of the first probability distribution function and component h_k of the second probability distribution function where $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\mu <br><br>}}_i=1<br><br><br><br>\mathrm{and}<br><br><br><br>\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\gamma <br><br>}}_k=1,$

ω

_ik≧

0 for 1≦

i≦

N, and for 1 ≦

k≦

K, and $\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}={\mathrm{\mu <br><br>}}_i,1\le <br><br>i\le <br><br>N,\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}={\mathrm{\gamma <br><br>}}_k,1\le <br><br>k\le <br><br>K,$

and

making a determination, based on said computed overall distance as to whether said another set of collected data pertains to said source.

2. The method according to claim 1 wherein at least one of said first and second mixture probability distribution functions includes a Gaussian Mixture Model.

3. The method according to claim 1 wherein the element distance between the first and second probability distance functions is a Kullback Leibler Distance.

4. The method of claim 1 wherein the first and second probability distribution functions are Gaussian mixture models derived from audio segments.

5. A computer program embedded in a storage medium for computing a distance measure between first and second mixture type probability distribution functions, $G$

(x)=∑

i=1N⁢

μ

i⁢

gi⁡

(x),

pertaining to a set data collected from a first source, and $H<br><br>\left(x\right)=\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\gamma <br><br>}}_k<br><br>h_k<br><br>\left(x\right),$

pertaining to another set of collected data, the improvement comprising a software module of said computer program that evaluates said distance measure in accordance with equation;

$D_M<br><br>\left(G,H\right)=\underset{w=\left[{\mathrm{\omega <br><br>}}_{\mathrm{ik}}\right]}{\min }<br><br>\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}<br><br>d<br><br>\left(g_i,h_k\right),$

where d(g_i, h_k) is a function of distance between a component, g_i, of the first probability distribution function and a component, h_k, of the second probability distribution function where $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\mu <br><br>}}_i=1<br><br><br><br>\mathrm{and}<br><br><br><br>\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\gamma <br><br>}}_k=1,$

ω

_ik≧

0, 1≦

i≦

N, 1≦

k≦

K,

there exists some value of i for which ω

_ik>

0 for at least two values of k, and $\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}={\mathrm{\mu <br><br>}}_i,1\le <br><br>i\le <br><br>N,\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}={\mathrm{\gamma <br><br>}}_k,1\le <br><br>k\le <br><br>K,$

and

making a determination, based on said computed overall distance as to whether said another set of collected data pertains to said source.

6. The computer program according to claim 5 wherein at least one of said first and second mixture probability distribution functions includes a Gaussian Mixture Model.

7. The computer program according to claim 5 wherein the element distance between the first and second probability distance functions includes Kullback Leibler Distance.

8. The computer program of claim 5 wherein the first and second probability distribution functions are Gaussian mixture models derived from audio segments.

9. A computer system for computing a distance measure between first and second mixture type probability distribution functions, $G$

(x)=∑

i=1N⁢

μ

i⁢

gi⁡

(x),and⁢

⁢

H⁡

(x)=∑

k=1K⁢

γ

k⁢

hk⁡

(x),

pertaining to audio data comprising;

memory for storing said audio data;

a processing module for deriving one of said mixture type probability distribution functions from said audio data; and

a processing module for evaluating said distance measure in accordance with $D_M<br><br>\left(G,H\right)=\underset{w=\left[{\mathrm{\omega <br><br>}}_{\mathrm{ik}}\right]}{\min }<br><br>\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}<br><br>d<br><br>\left(g_i,h_k\right),$

where d(g_i, h_k) is a function of the distance between a component, g_i, of the first probability distribution function and a component, h_k, of the second probability distribution function,

where $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\mu <br><br>}}_i=1<br><br><br><br>\mathrm{and}<br><br><br><br>\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\gamma <br><br>}}_k=1,$

and

ω

_ik≧

0, 1≦

i≦

N, 1≦

k≦

K,

and there exists some value of i for which ω

_ik>

0 for at least two values of k, and $\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}={\mathrm{\mu <br><br>}}_i,1\le <br><br>i\le <br><br>N,\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}={\mathrm{\gamma <br><br>}}_k,1\le <br><br>k\le <br><br>K.$

10. The computer system according to claim 9 wherein at least one of said first and second mixture probability distribution functions includes a Gaussian Mixture Model.

11. The computer system according to claim 9 wherein the element distance between the first and second probability distance functions includes Kullback Leibler Distance.

12. The computer system of claim 9 wherein the first and second probability distribution functions are Gaussian mixture models derived from audio segments.

13. A method executed in a computer for computing a distance measure between a mixture type probability distribution function $G$

(x)=∑

i=1N⁣

μ

i⁢

gi⁢

(x),

pertaining to a set data collected from a first source, where μ

, is a weight imposed on component g_i(x), and a mixture type probability distribution function $H<br><br>\left(x\right)=\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\gamma <br><br>}}_k<br><br>h_k<br><br>\left(x\right),$

pertaining to another set of collected data, where γ

_k is a weight imposed on component h_k comprising the steps of;

computing an element distance, d(g_i, h_k), between each g_i and each h_k where 1≦

i≦

N,1≦

k≦

K,

computing an overall distance, denoted by D_M(G, H), between the mixture probability distribution function G, and the mixture probability distribution function H, based on a weighted sum of the all element distances, $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}<br><br>d<br><br>\left(g_i,h_k\right),$

wherein weights ω

_i,k imposed on the element distances d(g_i, h_k), are chosen so that the overall distance D_M(G, H) is minimized, subject to

ω

_ik>

0 for at least two values of k for each value of i, $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}={\mathrm{\gamma <br><br>}}_k,1\le <br><br>k\le <br><br>K,\mathrm{and}$$\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}={\mathrm{\mu <br><br>}}_i,1\le <br><br>i\le <br><br>N,$

and

making a determination, based on said computed overall distance as to whether said another set of collected data pertains to said source.

14. The method according to claim 13 wherein at least one of said first and second mixture probability distribution functions includes a Gaussian Mixture Model.

15. The method according to claim 13 wherein the element distance between the first and second probability distance functions includes Kullback Leibler Distance.

16. The method of claim 13 wherein the first and second probability distribution functions are Gaussian mixture models derived from audio segments.

17. A method executed in a computer for content-based searching of stored data that pertains to a physical attribute of a system comprising the steps of:

acquiring a collection of physical attributes data; and

transforming said collection of physical attributes data into a signal tat is outputted by said computer;

where said transforming is effected by;

identifying collections in said stored data;

developing a probability distribution function for each of said identified collections;

developing a probability distribution function for the acquired collection;

developing a distance measure between the developed probability distribution function of said acquired collection and developed probability distribution functions for said identified collections;

applying a threshold to the developed distance measure to discover those of said identified segments with a distance measure below said preselected threshold value, where said distance is directly computed according to a measure that guarantees to satisfy the non-negativeness, symmetry, and triangular inequality properties of a distance measure; and

developing said output signal based on step of applying

where said distance measure between a first probability function, $G<br><br>\left(x\right)=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\mu <br><br>}}_i<br><br>g_i<br><br>\left(x\right),$

and a second probability function, $H<br><br>\left(x\right)=\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\gamma <br><br>}}_k<br><br>h_k<br><br>\left(x\right),$

is $D_M<br><br>\left(G,H\right)=\underset{w=\left[{\mathrm{\omega <br><br>}}_{\mathrm{ik}}\right]}{\min }<br><br>\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}<br><br>d<br><br>\left(g_i,h_k\right),$

where

d(g_i, h_k) is a function of the distance between a component, g_i, of the first probability distribution function and a component h_k, of the second probability distribution function, $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\mu <br><br>}}_i=1<br><br><br><br>\mathrm{and}<br><br><br><br>\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\gamma <br><br>}}_k=1,$

ω

_ik≧

0, 1≦

i≦

N, 1≦

k≦

K, $\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}={\mathrm{\mu <br><br>}}_i,1\le <br><br>i\le <br><br>N,\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}={\mathrm{\gamma <br><br>}}_k,1\le <br><br>k\le <br><br>K,$

and

there exists some value of i for which ω

_ik>

0 for at least two values of k.

18. A method executed in a computer comprising the steps of:

identifying speaker segments in provided audio-visual data based on speech contained in said data;

developing a probability distribution function for each of said segments from data points within each of said segments; and

developing distance measures among said probability distribution functions, where each of said measures is obtained through a one-pass evaluation of a function that guarantees to satisfy the non-negativeness, symmetry, and triangular inequality properties of a distance measure

where said distance measure between a first probability function, $G<br><br>\left(x\right)=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\mu <br><br>}}_i<br><br>g_i<br><br>\left(x\right),$

 

and a second probability function, $H<br><br>\left(x\right)=\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\gamma <br><br>}}_k<br><br>h_k<br><br>\left(x\right),$

 

is $D_M<br><br>\left(G,H\right)=\underset{w=\left[{\mathrm{\omega <br><br>}}_{\mathrm{ik}}\right]}{\min }<br><br>\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}<br><br>d<br><br>\left(g_i,h_k\right),$

 

where

d(g_i, h_k) is a function of the distance between a component, g_i, of the first probability distribution function and a component, h_k, of the second probability distribution function, $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\mu <br><br>}}_i=1<br><br><br><br>\mathrm{and}<br><br><br><br>\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\gamma <br><br>}}_k=1,$

ω

_ik≧

0, 1≦

i≦

N, 1≦

k≦

K, $\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}={\mathrm{\mu <br><br>}}_i,1\le <br><br>i\le <br><br>N,\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\omega <br><br>}}_{\mathrm{ik}}={\mathrm{\gamma <br><br>}}_k,1\le <br><br>k\le <br><br>K,$

and

there exists some value of i for which ω

_ik>

0 for at least two values of k.