Systems and methods for tractable variational approximation for interference in decision-graph Bayesian networks
View Patent ↗The present invention leverages approximations of distributions to provide tractable variational approximations, based on at least one continuous variable, for inference utilization in Bayesian networks where local distributions are decision-graphs. These tractable approximations are employed in lieu of exact inferences that are normally NP-hard to solve. By utilizing Jensen's inequality applied to logarithmic distributions composed of a generalized sum including an introduced arbitrary conditional distribution, a means is acquired to resolve a tightly bound likelihood distribution. The means includes application of Mean-Field Theory, approximations of conditional probability distributions, and/or other means that allow for a tractable variational approximation to be achieved.
1. A computer-implemented system that facilitates deriving an inference in a Bayesian network comprising:
a component that accesses a decision-graph Bayesian network; and
an approximation component that determines a tractable variational approximation by selecting a bound that adjusts processing time through a bounding equation:
log
p
(
x
)
>
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
;
wherein x and h are sets of variables that form a full domain of the Bayesian network, h represents hidden or unobserved nodes in the decision-graph Bayesian network, x represents observed nodes in the decision-graph Bayesian network, p(x) represents a marginal probability for the decision-graph Bayesian network, p(x, h) represents joint probabilities for x and h, and q(h|x) is an arbitrary conditional distribution over h given x.
2. The system of claim 1 , the approximation component selects
q
(
h
❘
x
)
such
that
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
of the bounding equation is above a threshold.
3. The system of claim 1 , the approximation component selects
q
(
h
❘
x
)
such
that
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
of the bounding equation is maximum.
4. The system of claim 1 , the approximation component evaluates the arbitrary conditional distribution over h given x as a product of a set of q( h i |x) as given by:
q
(
h
❘
x
)
=
∏
i
q
(
h
i
❘
x
)
;
where each h i corresponds to a single variable in h and q(h|x) is greater than zero.
5. The system of claim 4 , the approximation component identifies a value of q(h|x) that yields
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
of the bounding equation being greater than a threshold.
6. The system of claim 4 , the approximation component determines q(h|x) that provides a maximum
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
of the bounding equation.
7. The system of claim 1 , the approximation component utilizes a conditional probability distribution, p(h|x), and an arbitrary conditional distribution, q(h|x), wherein x and h are sets of variables that form a full domain of the Bayesian network, h represents hidden or unobserved nodes, x represents observed nodes, and p(h|x) and q(h|x) are distributions over h given x, and q(h|x) being utilizes as an approximation for p(h|x) as given by:
p(h|x)∝q(h|x).
8. The system of claim 7 , the approximation component chooses q(h |x) such that
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
is above a threshold of a bounding equation:
log
p
(
x
)
≥
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
.
9. The system of claim 7 , the approximation component selects q(h|x) to obtain a maximum
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
of a bounding equation:
log
p
(
x
)
≥
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
.
10. The system of claim 7 , the approximation component determines the arbitrary conditional distribution, q(h|x), based at least in part upon a product of a set of q(h i |x) as given by:
q
(
h
❘
x
)
=
∏
i
q
(
h
i
❘
x
)
where each h i corresponds to a single variable in h and q(h|x) is greater than zero.
11. The system of claim 10 , the approximation component selects q(h |x) to provide a value greater than a threshold of
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
of a bounding equation:
log
p
(
x
)
≥
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
.
12. The system of claim 10 , the approximation component determines
q
(
h
❘
x
)
to
maximize
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
of a bounding equation:
log
p
(
x
)
≥
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
.
13. A computer readable medium having stored thereon computer executable components of the system of claim 1 .
14. A device employing the system of claim 1 comprising at least one selected from the group consisting of a computer, a server, and a handheld electronic device.
15. A computer implemented method for facilitating processing inference in a Bayesian network, comprising:
providing a decision-graph Bayesian network; and
utilizing at least one continuous variable to determine a tractable variational approximation by selecting a bound that modifies processing time.
16. The method of claim 15 , determining the tractable variational approximation including, at least in part, approximating log p(x) by utilizing a bounding equation:
log
p
(
x
)
≥
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
;
wherein x and h are sets of variables that form a full domain of the Bayesian network, h represents hidden or unobserved nodes in the decision-graph Bayesian network, x represents observed nodes in the decision-graph Bayesian network, p(x) represents marginal probability for the decision-graph Bayesian network, p(x, h) represents the joint probabilities for x and h, and q(h|x) is an arbitrary conditional distribution over h given x.
17. The method of claim 16 , further including:
determining a desired result for
∑
h
q
(
h
❘
x
)
log
[
p
(
x
,
h
)
q
(
h
❘
x
)
]
of the bounding equation, wherein the desired result comprising at least one selected from the group consisting of making
∑
h
q
(
h
|
x
)
log
[
p
(
x
,
h
)
q
(
h
|
x
)
]
closer to its maximum than its medial value; and making
∑
h
q
(
h
|
x
)
log
[
p
(
x
,
h
)
q
(
h
|
x
)
]
maximized.
18. The method of claim 16 , the approximation component evaluates the arbitrary conditional distribution over h given x as a product of a set of q( h i |x) as given by:
q
(
h
|
x
)
=
∏
i
q
(
h
i
|
x
)
;
where each h i corresponds to a single variable in h and the value of q(h|x) is greater than zero.
19. The method of claim 18 , further including: determining a desired result for
∑
h
q
(
h
|
x
)
log
[
p
(
x
,
h
)
q
(
h
|
x
)
]
of the bounding equation; wherein the desired result comprising at least one selected from the group consisting of making
∑
h
q
(
h
|
x
)
log
[
p
(
x
,
h
)
q
(
h
|
x
)
]
closer to its maximum value than to its medial value; and making
∑
h
q
(
h
|
x
)
log
[
p
(
x
,
h
)
q
(
h
|
x
)
]
maximized.
20. The method of claim 15 , determining the tractable variational approximation including, at least in part, utilizing a conditional probability distribution, p(h|x), and an arbitrary conditional distribution, q(h|x), wherein x and h are sets of variables that form a full domain of the Bayesian network, h represents hidden or unobserved nodes, x represents observed nodes, and wherein p(h|x) and q(h|x) are distributions over h given x, and q(h|x) being utilized as an approximation for p(h|x) as given by:
p(h|x)∝q(h|x).
21. The method of claim 20 , further including:
determining a desired parameter for utilization, at least in part, in ascertaining the approximation, wherein the parameter comprising at least one selected from the group consisting of obtaining a value of
∑
h
q
(
h
|
x
)
log
[
p
(
x
,
h
)
q
(
h
|
x
)
]
with closer proximity to its maximum than to its medial value, and obtaining a maximized
∑
h
q
(
h
|
x
)
log
[
p
(
x
,
h
)
q
(
h
|
x
)
]
of a bounding equation:
log
p
(
x
)
≥
∑
h
q
(
h
|
x
)
log
[
p
(
x
,
h
)
q
(
h
|
x
)
]
.
22. The system of claim 20 , the approximation component evaluates conditional distribution over h given x as a product of a set of q( h i |x) as given by:
q
(
h
|
x
)
=
∏
i
q
(
h
i
|
x
)
;
where each h i corresponds to a single variable in h and q(h|x) is greater than zero.
23. The method of claim 22 , further including:
determining a desired parameter for utilization, at least in part, in ascertaining the approximation, wherein the parameter comprising at least one selected from the group consisting of obtaining a value of
∑
h
q
(
h
|
x
)
log
[
p
(
x
,
h
)
q
(
h
|
x
)
]
with closer proximity to its maximum than its medial value, and obtaining a maximized
∑
h
q
(
h
|
x
)
log
[
p
(
x
,
h
)
q
(
h
|
x
)
]
of a bounding equation:
log
p
(
x
)
≥
∑
h
q
(
h
|
x
)
log
[
p
(
x
,
h
)
q
(
h
|
x
)
]
.
24. A device employing the method of claim 15 comprising at least one selected from the group consisting of a computer, a server, and a handheld electronic device.
25. A system for facilitating processing inference in a Bayesian network comprising:
means for approximating, utilizing at least one continuous variable, a tractable variational approximation based on a selectable bound that influences computational processing time.
26. The system of claim 25 , the means for approximating including employing, at least in part, approximating log p(x) by utilizing a bounding equation:
log
p
(
x
)
≥
∑
h
q
(
h
|
x
)
log
[
p
(
x
,
h
)
q
(
h
|
x
)
]
;
wherein x and h are sets of variables that form a full domain of the Bayesian network, h represents hidden or unobserved nodes in the decision-graph Bayesian network, x represents observed nodes in the decision-graph Bayesian network, p(x) represents marginal probability for the decision-graph Bayesian network, p(x, h) represents the joint probabilities for x and h, and q(h|x) is an arbitrary conditional distribution over h given x.
27. The system of claim 26 , the approximation component evaluates the arbitrary conditional distribution over h given x as a product of a set of q( h i |x) as given by:
q
(
h
|
x
)
=
∏
i
q
(
h
i
|
x
)
;
where each h i corresponds to a single variable in h and q(h|x) is a value greater than zero.
28. The method of claim 25 , the means for approximating including employing, at least in part, utilizing a conditional probability distribution, p(h|x), and an arbitrary conditional distribution, q(h|x), wherein x and h are sets of variables that form a full domain of the Bayesian network, h represents hidden or unobserved nodes, x represents observed nodes, and wherein p(h|x) and q(h|x) are distributions over h given x, and q(h|x) being utilized as an approximation for p(h|x) as given by:
p(h|x)∝q(h|x).
29. A data packet transmitted between two or more computer components that facilitates inferencing of decision-graph Bayesian networks, the data packet includes information relating to a system that determines, based on at least one continuous variable, a tractable variational approximation with a selectable bound that adjusts computational processing time.