# US 2005/0231401 A1 · Method and system for the compression of probability tables

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2005/0231401 A1
- Document ID: US20050231401A1
- Status: Published application
- Kind: A1
- Application number: 10/818,567
- Filed: 2004-04-06
- Published: 2005-10-20
- Earliest claimed: 2004-04-06
- Assignees: International Business Machines Corporation
- Inventors: Michael Perrone; Eugene Ratzlaff; Jianying Hu
- Web page: https://patentgrep.com/patent/US20050231401A1

## CPC

- H04N 1/4177: {encoding document change data, e.g. form drop out data}
- G06F 18/2321: using statistics or function optimisation, e.g. modelling of probability density functions
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present invention relates to a method, computer program product and system for the compression of a probability table and the reconstruction of one or more probability elements using the compressed data and method. After determining a probability table that is to be compressed, the probability table is compressed using a first probability table compression method, wherein the probability table compression method creates a first compressed probability table. The first compressed probability table contains a plurality of probability elements. Further, the probability table is compressed using a second probability table compression method, wherein the probability table compression method creates a second compressed probability table. The second compressed probability table containing a plurality of probability elements. A first probability element reconstructed using the first compressed probability table is thereafter merged with a second probability element reconstructed using the second compressed probability table in order to produce a merged probability element.

## Claims

### Claim 1

A method of implementing a computer for the compression of probability tables and the recovery of selected probability elements through the use of compressed probability tables, comprising the steps of:
determining a probability table that is to be compressed, wherein the probability table contains a plurality of probability elements;
compressing the probability table using a first probability table compression method, wherein the probability table compression method creates a first compressed probability table, the first compressed probability table containing a plurality of probability elements;
compressing the probability table using a second probability table compression method, wherein the probability table compression method creates a second compressed probability table, the second compressed probability table containing a plurality of probability elements; and
merging a first probability element with a second probability element in order to produce a merged probability element.

### Claim 2 (depends on 1)

The method of claim 1, further comprising the use of a discrepancy table to conditionally replace the merged probability elements based on the absolute difference between the merged probability element and a corresponding probability element being larger than a variable threshold.

### Claim 3 (depends on 2)

The method of claim 2, wherein the probability elements in the compressed tables and the discrepancy table are quantized to a pre-specified degree.

### Claim 4 (depends on 3)

The method of claim 3, wherein the quantized probability element and a probability look-up table element address of the quantized probability element are stored within a discrepancy table element.

### Claim 5 (depends on 4)

The method of claim 4, wherein the probability table is compressed using a mixture model probability table compression method.

### Claim 6 (depends on 4)

The method of claim 4, wherein the probability table is compressed using a distributional clustering probability table compression method.

### Claim 7

A method for the compression of a probability table using distributional clustering, comprising the steps of:
determining a probability table that is to be compressed, wherein the probability table contains a plurality of probability elements;
evaluating the probability elements of the probability table in order to determine related probability elements of the probability table that can be replaced with a compressed probability element;
generating a compressed probability table, the compressed probability table containing probability elements that are compressed, wherein the probability table elements that have been determined to have related values are represented by a single compressed probability element; and
creating an index for the compressed probability table that maps the index for each probability element of the probability table to a new index for the corresponding compressed probability element of the compressed probability table, wherein the indices of similar probability elements will map to the index of a single compressed probability element.

### Claim 8 (depends on 7)

The method of claim 7, wherein the step of evaluating the probability elements further comprises the step of sorting the probability elements into a list that is ordered by decreasing mutual information with a class variable.

### Claim 9 (depends on 8)

The method of claim 8, wherein the step of evaluating the probability elements further comprises the step of initializing M+1 clusters as singletons with a top M+1 probability element on the list.

### Claim 10 (depends on 9)

The method of claim 9, wherein the step of generating an estimated probability element value comprises the step of merging two clusters with a minimum distance in accordance with Df(Ei,Ej)=P(Ei)·D(P(C|Ei)∥P(C|EivEj))+P(Ej)·D(P(C|Ej)∥P(C|EivEj)), the next probability element on the list is added as a singleton cluster and the merging of two clusters with a minimum distance is repeated until the last probability element on the list has been processed.

### Claim 11 (depends on 10)

The method of claim 10, further comprising the step of computing the within-cluster distance between each estimated probability element and its cluster center using the equation Df(Ei,Ej)=P(Ei)·D(P(C|Ei)∥P(C|EivEj))+P(Ej)·D(P(C|Ej)∥P(C\EivEj)).

### Claim 12 (depends on 11)

The method of claim 11, further comprising the step of sorting the estimated probability elements in an order of decreasing within-cluster distance.

### Claim 13 (depends on 12)

The method of claim 12, further comprising the step of computing the distance for each estimated probability element Df(Tk, Ek), to all cluster centers in order to find the cluster Ej with the minimum distance to the estimated probability element, wherein if j is not equal to i then the probability element Tk is moved to cluster Ej.

### Claim 14 (depends on 13)

The method of claim 13, wherein the step of generating an estimated probability table further comprises the step of quantizing the estimated probability element values into an integer of a predetermined size.

### Claim 15

A method for the compression of a probability table using mixture model probability table compression, comprising the steps of:
determining a joint probability table that is to be compressed, wherein the joint probability table contains a plurality of probability elements;
generating a first compressed probability table, the first compressed probability table containing compressed probability mixture elements;
generating a second compressed probability table, the second probability table containing compressed probability mixture coefficients;
optimizing the compressed first and second probability tables in order to generate a compressed mixture model of the joint probability table, wherein the compressed mixture model contains compressed mixture model elements; and
quantizing the compressed mixture model elements of the compressed mixture model into integers of a predetermined size.

### Claim 16 (depends on 15)

The method of claim 15, wherein the steps of generating a first and second compressed probability table to compress a joint probability table represented by P(X1,N), the first and second compressed probability tables are calculated according to
P
⁡
(
X
1
,
N
)
=
∑
l
=
1
M
⁢
P
⁡
(
X
k
+
1
,
N
|
μ
l
)
⁢
P
⁡
(
μ
l
,
X
1
,
k
)
,
wherein P(Xk+1,N|μl) represents a probability mixture and P(μl,X1,k) represents a probability mixture coefficient.

### Claim 17 (depends on 16)

The method of claim 16, wherein the compressed first and second probability tables are optimized according to
P
t
⁡
(
μ
l
❘
X
1
,
N
)
=
P
t
⁡
(
μ
l
❘
X
1
,
k
)
⁢
P
t
⁡
(
X
k
+
1
,
N
❘
μ
l
)
∑
j
⁢
P
t
⁡
(
μ
j
❘
X
1
,
k
)
⁢
P
t
⁡
(
X
k
+
1
,
N
❘
μ
j
)
.

### Claim 18

A computer program product that includes a computer readable medium useable by a processor, the medium having stored thereon a sequence of instructions which, when executed by the processor, causes the processor to compress a probability tables through the use of compressed probability tables, wherein the computer program product executes the steps of:
determining a probability table that is to be compressed, wherein the probability table contains a plurality of probability elements;
compressing the probability table using a first probability table compression method, wherein the probability table compression method creates a first compressed probability table, the first compressed probability table containing a plurality of probability elements;
compressing the probability table using a second probability table compression method, wherein the probability table compression method creates a second compressed probability table, the second compressed probability table containing a plurality of probability elements; and
merging a first probability element with a second probability element in order to produce a merged probability element.

### Claim 19 (depends on 18)

The computer program product of claim 18, further comprising the step of using a discrepancy table to conditionally replace the merged probability elements based on the absolute difference between the merged probability element and a corresponding probability element being larger than a variable threshold.

### Claim 20 (depends on 19)

The computer program product of claim 19, wherein the probability elements in the compressed tables and the discrepancy table are quantized to a pre-specified degree.

### Claim 21 (depends on 20)

The computer program product of claim 20, wherein the quantized probability element and a probability look-up table element address of the quantized probability element are stored within a discrepancy element table.

### Claim 22 (depends on 21)

The computer program product of claim 21, wherein the probability table is compressed using a mixture model probability table compression method.

### Claim 23 (depends on 21)

The computer program product of claim 21, wherein the probability table is compressed using a distributional clustering probability table compression method.

### Claim 24

A computer program product that includes a computer readable medium useable by a processor, the medium having stored thereon a sequence of instructions which, when executed by the processor, causes the processor to compress a probability table through the use of distributional clustering, wherein the computer program product executes the steps of:
determining a probability table that is to be compressed, wherein the probability table contains a plurality of probability elements;
evaluating the probability elements of the probability table in order to determine related probability elements of the probability table that can be replaced with a compressed probability element;
generating a compressed probability table, the compressed probability table containing probability elements that are compressed, wherein the probability table elements that have been determined to have related values are represented by a single compressed probability element; and
creating an index for the compressed probability table that maps the index for each probability element of the probability table to a new index for the corresponding compressed probability element of the compressed probability table, wherein the indices of similar probability elements will map to the index of a single compressed probability element.

### Claim 25 (depends on 24)

The computer program product of claim 24, wherein the step of evaluating the probability elements further comprises the step of sorting the probability elements into a list that is ordered by decreasing mutual information with a class variable.

### Claim 26 (depends on 25)

The computer program product of claim 25, wherein the step of evaluating the probability elements further comprises the step of initializing M+1 clusters as singletons with a top M+1 probability element on the list.

### Claim 27 (depends on 26)

The computer program product of claim 26, wherein the step of generating an estimated probability element value comprises the step of merging two clusters with a minimum distance in accordance with Df(Ei,Ej)=P(Ei)·D(P(C|Ei)∥P(C|EivEj))+P(Ej)·D(P(C|Ej)∥P(C|EivEj)), the next probability element on the list is added as a singleton cluster and the merging of two clusters with a minimum distance is repeated until the last probability element on the list has been processed.

### Claim 28 (depends on 27)

The computer program product of claim 27, further comprising the step of computing the within-cluster distance between each estimated probability element and its cluster center using the equation Df(Ei,Ej)=P(Ei)·D(P(C|Ei)∥P(C|EivEj))+P(Ej)·D(P(C|Ej)∥P(C\EivEj)).

### Claim 29 (depends on 28)

The computer program product of claim 28, further comprising the step of sorting the estimated probability elements in an order of decreasing within-cluster distance.

### Claim 30 (depends on 29)

The computer program product of claim 29, further comprising the step of computing the distance for each estimated probability element Df(Tk, Ek), to all cluster centers in order to find the cluster Ej with the minimum distance to the estimated probability element, wherein if j is not equal to i then the probability element Tk is moved to cluster Ej.

### Claim 31 (depends on 30)

The computer program product of claim 30, wherein the step of generating an estimated probability table further comprises the step of quantizing the estimated probability element values into an integer of a predetermined size.

### Claim 32

A computer program product that includes a computer readable medium useable by a processor, the medium having stored thereon a sequence of instructions which, when executed by the processor, causes the processor to compress a probability table using a mixture model, wherein the computer program product executes the steps of:
determining a joint probability table that is to be compressed, wherein the joint probability table contains a plurality of probability elements;
generating a first compressed probability table, the first compressed probability table containing compressed probability mixture elements;
generating a second compressed probability table, the second probability table containing compressed probability mixture coefficients;
optimizing the compressed first and second probability tables in order to generate a compressed mixture model of the joint probability table, wherein the compressed mixture model contains compressed mixture model elements; and
quantizing the compressed mixture model elements of the compressed mixture model into integers of a predetermined size.

### Claim 33 (depends on 32)

The computer program product of claim 32, wherein the steps of generating a first and second compressed probability table to compress a joint probability table represented by P(X1,N), the first and second compressed probability tables are calculated according to
P
⁡
(
X
1
,
N
)
=
∑
l
=
1
M
⁢
P
⁡
(
X
k
+
1
,
N
❘
μ
l
)
⁢
P
⁡
(
μ
l
,
X
1
,
k
)
,
wherein P(Xk+1,N|μl) represents a probability mixture and P(μl,X1,k) represents a probability mixture coefficient.

### Claim 34 (depends on 33)

The computer program product of claim 33, wherein the compressed first and second probability tables are optimized according to
P
t
⁡
(
μ
l
❘
X
1
,
N
)
=
P
t
⁡
(
μ
l
❘
X
1
,
k
)
⁢
P
t
⁡
(
X
k
+
1
,
N
❘
μ
l
)
∑
j
⁢
P
t
⁡
(
μ
j
❘
X
1
,
k
)
⁢
P
t
⁡
(
X
k
+
1
,
N
❘
μ
j
)
.

### Claim 35

A computer system for the compression of probability tables through the use of compressed probability tables, the system comprising:
a means for determining a probability table that is to be compressed, wherein the probability table contains a plurality of probability elements;
a means for compressing the probability table using a first probability table compression method, wherein the probability table compression method creates a first compressed probability table, the first compressed probability table containing a plurality of probability elements;
a means for compressing the probability table using a second probability table compression method, wherein the probability table compression method creates a second compressed probability table, the second compressed probability table containing a plurality of probability elements; and
a means for merging a first probability element with a second probability element in order to produce a merged probability element.

### Claim 36

A method of implementing a computer for the recovery of selected probability elements through the use of compressed probability tables, comprising the steps of:
determining if a probability look-up table element address is located within a discrepancy table,
returning the corresponding probability element if the probability look-up table element address is located in the discrepancy table;
retrieving a compressed probability element, which has been compressed using a first compression method that corresponds with the probability look-up table element address if the probability look-up table element address is not located in the discrepancy table;
retrieving a compressed probability element, which has been compressed using a second compression method, that corresponds with the probability look-up table element address if the probability look-up table element address is not located in the discrepancy table; and
merging the retrieved compressed probability elements in order to produce a merged probability element.

### Claim 37 (depends on 36)

The method of claim 36, wherein the step of retrieving a compressed probability element comprises retrieving at least two probability elements that have been compressed using differing compressions.

### Claim 38

A computer program product that includes a computer readable medium useable by a processor, the medium having stored thereon a sequence of instructions which, when executed by the processor, causes the computer to recover selected probability elements through the use of compressed probability tables, wherein the computer program product executes the steps of:
determining if a probability look-up table element address is located within a discrepancy table,
returning a corresponding probability element if the probability look-up table element address is located in the discrepancy table;
retrieving a compressed probability element, which has been compressed using a first compression method that corresponds with the probability look-up table element address if the probability look-up table element address is not located in the discrepancy table;
retrieving a compressed probability element, which has been compressed using a second compression method, that corresponds with the probability look-up table element address if the probability look-up table element address is not located in the discrepancy table; and
merging the retrieved compressed probability elements in order to produce a merged probability element.

### Claim 39 (depends on 38)

The computer program product of claim 38, wherein the step of retrieving a compressed probability element comprises retrieving at least two probability elements that have been compressed using differing compressions.

### Claim 40

A computer system for the recovery of selected probability elements through the use of compressed probability tables, the system comprising:
a means to determine if a probability look-up table element address is located within a discrepancy table,
a means to retrieve a corresponding probability element if the probability look-up table element address is located in the discrepancy table;
a means to retrieve a compressed probability element, which has been compressed using a first compression method that corresponds with the probability look-up table element address if the probability look-up table element address is not located in the discrepancy table;
a means to retrieve a compressed probability element, which has been compressed using a second compression method, that corresponds with the probability look-up table element address if the probability look-up table element address is not located in the discrepancy table; and
a means to merge the retrieved compressed probability elements in order to produce a merged probability element.
