Browse Prior Art Database

# Fast Algorithm for Computing the Optimal Linear Combination of Probability Distributions

IP.com Disclosure Number: IPCOM000062214D
Original Publication Date: 1986-Oct-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 1 page(s) / 12K

IBM

## Related People

Bahl, LR: AUTHOR [+5]

## Abstract

The present invention relates to an algorithm which, given distributions P(.) and Q(.) and a sample output X, is directed to computing the optimal linear combination gP(.) + (1-g)Q(.) that maximizes Pr (X). The algorithm is applicable to speech recognition. Let P(.) and Q(.) be two probability distributions over some alphabet A. Then Rg(.) = gP(.) + (1-g)Q(.),0

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 62% of the total text.

Page 1 of 1

Fast Algorithm for Computing the Optimal Linear Combination of Probability Distributions

The present invention relates to an algorithm which, given distributions P(.) and Q(.) and a sample output X, is directed to computing the optimal linear combination gP(.) + (1-g)Q(.) that maximizes Pr (X). The algorithm is applicable to speech recognition. Let P(.) and Q(.) be two probability distributions over some alphabet A. Then Rg(.) = gP(.) + (1-g)Q(.),0<g<1 is a linear combination of P and Q parameterized by the weighting value g. Let X = x1x2 ...xN be a sequence with xieA i=1,2,...N. Let

(Image Omitted)

be the probability of the sequence X being generated by Rg(.). Given P(.), Q(.) and X, the optimal value of g,i.e., the value of g that maximizes Prg (X), is sought. P(xi) is represented as Pi and Q(xi) as Qi . Then considering Prg (X) as a function if g for the given X,

(Image Omitted)

S(g) is a polynomial of degree N in terms of g. All of the roots of S(g) are real and occur outside the interval 0<g<1. Therefore, S(g) can have at most one local maximum in the interval 0<g<1. The derivative of S(g) is:

(Image Omitted)

Since S(g) is positive in the region 0<g<1, the sign of S'(g) is the same as the sign of T(g), where

(Image Omitted)

The present algorithm is based on evaluating the function T(g). Two cases are considered in which the maximum occurs at a boundary point g=0 or g=1. Case 1: S(g) is maximum at g=0 . <=> i) T(0) = 0 or ii) T(0) < 0 and T(1) < 0 Case 2: S(g...