Browse Prior Art Database

Design And Construction of an Idiot-System for Determining One Sequence From Another

IP.com Disclosure Number: IPCOM000100145D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 3 page(s) / 101K

Publishing Venue

IBM

Related People

Bahl, LR: AUTHOR [+5]

Abstract

This document is concerned with the problem of determining an unknown sequence Y from a given sequence X. One prominent approach to this problem is to estimate the probability Pr(Y ¯ X) and to search for the sequence Y' which maximizes it. That is, Y' = argmax Pr(Y ¯ X). Let the sequence Y be of length N, then y N Pr(Y ¯ X) = F Pr(yi ¯ y1i-1 , X). (1) i=1

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Design And Construction of an Idiot-System for Determining One Sequence From Another

       This document is concerned with the problem of
determining an unknown sequence Y from a given sequence X.  One
prominent approach to this problem is to estimate the probability
Pr(Y ¯ X) and to search for the sequence Y' which maximizes it.  That
is, Y' = argmax Pr(Y ¯ X).  Let the sequence Y be of length N,
then             y
                   N
      Pr(Y ¯ X) =  F  Pr(yi ¯ y1i-1 , X). (1)
                  i=1

      The conditional probabilities on the right hand side can be
estimated via an idiot-system, and maximizing Y' may be achieved via
a stack search [*].  If yi is strongly associated with y1i-1, then
the above approach may produce unsatisfactory results.  Because of
the association, the idiot-system may include few or no questions
about X.  Since the total number of questions in an idiot system is
limited by the amount of training data, it may be more efficient to
direct those questions to the preceding y's rather than to X.  If X
is ignored by the idiot-system, then Pr(Y ¯ X) will be independent of
X, and the same Y' will always be obtained, regardless of X.  The
following inventions describe two different solutions to this
problem.

      METHOD 1:  Bayes decomposition.  By Bayes' rule, the sequence
Y' which maximizes Pr(Y ¯ X) satisfies
      Y' = argmax Pr(X ¯ Y).Pr(Y).
              y
Observe that
               N
      Pr(Y) =  F  Pr(yi ¯ y1i-1)
              i=1
                   N
      Pr(X ¯ Y) =  F  Pr(xi ¯ x1i-1 , Y).
                  i=1
Hence,
                    N
      Y' = argmax   F  Pr(xi ¯ x1i-1 , Y).Pr(yi ¯ y1i-1). (2)
              y    i=1

      The conditional probabilities in (2) may both be estimated via
separate idiot-systems, and the optimal sequence Y' may be determined
via a stack search as before.

      Note that the idiot-system for Pr(xi ¯ x1i-1 , Y) explicitly
recognizes the role of X and cannot ignore it. At the same time, the
presumed high autocorrelation in the sequence Y is not discarded; it
is exploited by the idiot-system for Pr(yi ¯ y1i-1) in obtaining an
estimate of the prior probability of Y.

      Because the search for Y' proceeds from y1 to yN in sequence,
it may be convenient in practice to make the approximation
 Pr(xi ¯ x1i-1 , Y) = Pr(xi ¯ x1i-1 ,y1i-1)
so as to remove the dependence in (2) of xi on the as yet unknown
elements yi+1 to yN .  If nece...