Browse Prior Art Database

Adaptive Model for Nonstationary Sources

IP.com Disclosure Number: IPCOM000060441D
Original Publication Date: 1986-Apr-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Mohiuddin, K: AUTHOR [+3]

Abstract

In contrast to the prior art, an information source is regarded as varying continuously along a string. This means that the various symbol counts should be updated so as to forget the counts of the remote past. There are two basic ways of doing this. One is based upon collecting the counts over a fixed-sized "window" stretching into the past, while the other, discussed here, uses the notion of forgetting factor. It is given by (Image Omitted) where ni(sx g) and n(s g) are updated according to (Image Omitted) where g is a constant which is smaller than one (g<1), referred to as the "forgetting factor". From these equations, the intuitive role of g is seen: since the recent occurrences are weighted more relative to the remote occurrences, it follows that the smaller g is, the faster the forgetting process.

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

Page 1 of 2

Adaptive Model for Nonstationary Sources

In contrast to the prior art, an information source is regarded as varying continuously along a string. This means that the various symbol counts should be updated so as to forget the counts of the remote past. There are two basic ways of doing this. One is based upon collecting the counts over a fixed-sized "window" stretching into the past, while the other, discussed here, uses the notion of forgetting factor. It is given by

(Image Omitted)

where ni(sx g) and n(s g) are updated according to

(Image Omitted)

where g is a constant which is smaller than one (g<1), referred to as the "forgetting factor". From these equations, the intuitive role of g is seen: since the recent occurrences are weighted more relative to the remote occurrences, it follows that the smaller g is, the faster the forgetting process. To see this more quantitatively, notice that a recursive expression for the total count n(s) can also be written in the following explicit form:

(Image Omitted)

where n(s) denotes the length of the string s. As the length of the so-far processed string grows, that is, as n(s) T B, it follows from (2) that

(Image Omitted)

That is, a forgetting factor of g is roughly equivalent to having a virtual window of size

(Image Omitted)

over the so-far processed string. With this interpretation, the probability that the next symbol will be equal to i, given by (1), is simply the ratio between the number of occurrences of the symbol i over this virtual window to the length of the virtual window. It follows from the above discussion that the forgetting factor algorithm (1) is essentially equivalent to a "sliding window" algorithm of length

(Image Omitted)

However, the complexity and storage requirements of the two algorithms differ drastically; unlike in the forgetting factor algorithm, where the storage requirement is limited to the counts ni(s g) (i = 1,...,K) and n(s g), the sliding window scheme requires the storage of all the symbols over the window in a sequential order. In applications such as image compression, this difference is serious enough to make the sliding window algorithm unattractive. When string statistics change rapidly along the string, the forgetting factor g should be made small, and, conversely, when the statistics tend to remain unchanged, g should be made near one. This, then, leads to the idea of selecting g automatically, i.e.,

1

Page 2 of 2

adaptively, so as to match it to the currently prevailing string statistics. Given the so-far observed string s,...