Lossless compression with probabilistic circuits

Patent metadata

Field	Value
Publication number	US-12456231-B2
Application number	US-202318141130-A
Country	US
Kind code	B2
Filing date	Apr 28, 2023
Priority date	Apr 29, 2022
Publication date	Oct 28, 2025
Grant date	Oct 28, 2025

Abstract

Devices, methods, and systems for lossless compression utilizing probabilistic circuits (PCs) are provided. In one embodiments, a method for lossless compression using PCs is provided, the method comprising: receiving image data comprising a plurality of pixels, wherein each of the plurality of pixels is represented by a variable; sequentially compressing the variables one-by-one using conditional probabilities, wherein the conditional probabilities are computed by: calculating at least one marginal; initially setting to 1 a probability p(n) for every PC unit n; defining an eval i for a set of PC units n that need to be evaluated in an i th iteration; and for i=1 to a dataset D, evaluating PC units n in eval i using a bottom-up process and computing a target probability; and generating a bitstream using a streaming code for the compressed variables using the conditional probabilities.

First claim

What is claimed is:

1 . A method for lossless compression using probabilistic circuits (PCs), the method comprising:
receiving image data comprising a plurality of pixels, wherein each of the plurality of pixels is represented by a variable; sequentially compressing the variables one-by-one using conditional probabilities, wherein the conditional probabilities are computed by:
calculating at least one marginal;
initially setting to 1 a probability p(n) for every PC unit n;
defining an eval i for a set of PC units n that need to be evaluated in an i th iteration; and
for i=1 to a dataset D, evaluating PC units n in eval i using a bottom-up process and computing a target probability; and
generating a bitstream using a streaming code for the compressed variables using the conditional probabilities.

2 . The method of claim 1 , wherein sequentially compressing the variable one-by-one using the conditional probabilities comprises encoding a next variable by defining a left and right side cumulative probabilities of the next variable given one or more already encoded variables.

3 . The method of claim 2 , wherein the left and right side cumulative probabilities are defined using a 2D conditional probability that is a quotient of two marginals.

4 . The method of claim 1 , wherein calculating the at least one marginal comprises:
inputting a PC p having a variable instantiation x; outputting a marginal F(x)={p(x 1 , . . . , x 1 )} i=1 D , wherein D is the dataset.

5 . The method of claim 4 , wherein each of D terms in F(x) is computed one-by-one.

6 . The method of claim 5 , wherein each iteration on average re-evaluates only log(D)/D of the PC p.

7 . The method of claim 1 , wherein the evaluating the PC units in eval i is performed in a feedforward process to compute the target probability.

8 . The method of claim 1 , wherein at iteration i, a set of PC units eval i is selected that guarantees correctness of a target marginal, and contains a minimum number of PC units.

9 . The method of claim 8 , wherein the guarantee of correctness of the target marginal, and containing the minimum number of PC units is achieved by recognizing types of PC units that can be eliminated for evaluation.

10 . The method of claim 9 , wherein a root node's probability is equivalently computed using a weighted mixture of probabilities of PC units in eval i .

11 . A non-transitory computer readable storage medium storing a program comprising instructions that, when executed by at least one processor of a computing device, cause the at least one processor to perform operations including:
receiving image data comprising a plurality of pixels, wherein each of the plurality of pixels is represented by a variable; sequentially compressing the variables one-by-one using conditional probabilities, wherein the conditional probabilities are computed by:
calculating at least one marginal;
initially setting to 1 a probability p(n) for every PC unit n;
defining an eval i for a set of PC units n that need to be evaluated in an i th iteration; and
for i=1 to a dataset D, evaluating PC units n in eval i using a bottom-up process and computing a target probability; and
generating a bitstream using a streaming code for the compressed variables using the conditional probabilities.

12 . The non-transitory computer readable storage medium of claim 11 , wherein sequentially compressing the variable one-by-one using the conditional probabilities comprises encoding a next variable by defining a left and right side cumulative probabilities of the next variable given one or more already encoded variables.

13 . The non-transitory computer readable storage medium of claim 12 , wherein the left and right side cumulative probabilities are defined using a 2D conditional probability that is a quotient of two marginals.

14 . The non-transitory computer readable storage medium of claim 11 , wherein calculating the at least one marginal comprises:
inputting a PC p having a variable instantiation x; and outputting a marginal F(x)={p(x 1 , . . . , x i )} i=1 D , wherein D is the dataset.

15 . The non-transitory computer readable storage medium of claim 14 , wherein each of D terms in F(x) is computed one-by-one.

16 . The non-transitory computer readable storage medium of claim 15 , wherein each iteration on average re-evaluates only log(D)/D of the PC p.

17 . The non-transitory computer readable storage medium of claim 11 , wherein the evaluating the PC units in eval i is performed in a feedforward process to compute the target probability.

18 . The non-transitory computer readable storage medium of claim 11 , wherein at iteration i, a set of PC units eval i is selected that guarantees correctness of a target marginal, and contains a minimum number of PC units.

19 . The non-transitory computer readable storage medium of claim 18 , wherein the guarantee of correctness of the target marginal, and containing the minimum number of PC units is achieved by recognizing types of PC units that can be eliminated for evaluation.

20 . The non-transitory computer readable storage medium of claim 19 , wherein a root node's probability is equivalently computed using a weighted mixture of probabilities of PC units in eval i .

Assignees

• Univ California

Inventors

• Mandt Stephan
• Liu Anji
• Van Den Broeck Guy

Classifications

• H04N19/13

  Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC] · CPC title

• G06T9/005

  Statistical coding, e.g. Huffman, run length coding · CPC title

• H04N19/192

  the adaptation method, adaptation tool or adaptation type being iterative or recursive · CPC title

• H04N19/134

  characterised by the element, parameter or criterion affecting or controlling the adaptive coding · CPC title

• H04N19/182

  the unit being a pixel · CPC title