For example, in generative adversarial network, we often hear that inference is easy because the conditional distribution of x given latent variable z is 'tractable'. Also, I read somewhere that Boltzmann machine and variational autoencoder is used where the posterior distribution is not tractable so some sort of approximation need to be applied. Could anyone tell me what 'tractable' means, in a rigorous definition? Or could anyone explain in any of the examples I gave above, what tractable exactly means in that context?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ This is relevant. $\endgroup$– GreenparkerCommented May 6, 2017 at 14:44
-
1$\begingroup$ It simply means that you are able to handle the relevant computations with the distribution. So, what is "tractable" expands with time! $\endgroup$– kjetil b halvorsen ♦Commented May 7, 2017 at 15:21
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
To my best memory, I've never come across a formal definition for this in a statistical text, but I think you can stitch one together from a few contextual readings. Start with Bayesian Data Analysis, p. 261:
Bayesian computation revolves around two steps: computation of the posterior distribution, $p(\theta|y)$, and computation of the posterior predictive distribution, $p(\hat y|y)$. So far we have considered examples where these could computed analytically in closed form[.]
The obstacle is generally the marginal likelihood, the denominator on the right-hand side of Bayes' rule, which could involve an integral that cannot be analytically expressed. For a more I think you'll find wiki's article on closed-form expression helpful for context (emphasis mine):
In mathematics, a closed-form expression is a mathematical expression that can be evaluated in a finite number of operations. It may contain constants, variables, certain "well-known" operations (e.g., + − × ÷), and functions (e.g., nth root, exponent, logarithm, trigonometric functions, and inverse hyperbolic functions), but usually no limit. The set of operations and functions admitted in a closed-form expression may vary with author and context.
Problems are said to be tractable if they can be solved in terms of a closed-form expression.
If you read on, you'll see a table of classes of expressions, and "Analytic expressions" includes several involved in the normalizing constants of exponential family distributions. E.g., the gamma function in the gamma distribution, and the Bessel function in the von-Mises Fisher.
Meaning, we're willing to admit at least these into our definition of "tractability." (There may be other distributions that involve the classes of operations classified as "analytic expressions"; I confess I'm not familiar.)
answered May 7, 2017 at 15:03
-
1$\begingroup$ This is a great answer, +1. For some indication of what "tractable" might have meant over a century ago, browse through the second half of Whittaker & Watson, A course of modern analysis. Gamma and Bessel functions are merely the tip of the iceberg. $\endgroup$– whuber ♦Commented Apr 19, 2018 at 16:15
-
1$\begingroup$ @whuber On Whittaker and Watson: G.N. Watson has a small place in the history of statistics as deriving a bound for kurtosis on behalf of Karl Pearson. E.T. Whittaker has a larger one as a parent of smoothing splines avant la lettre. $\endgroup$– Nick CoxCommented Apr 19, 2018 at 17:35
-
1$\begingroup$ @whuber Thank you much! This post received several up votes around the time of your comment, which I take as anecdotal evidence of a "Huber Bump." $\endgroup$ Commented Apr 28, 2018 at 11:22
$\begingroup$
$\endgroup$
In addition to Sean Easter's answer, I will try to shed some light from the perspective of computational cost.
First of all, let's define what tractable and intractable problems are (Reference: http://www.cs.ucc.ie/~dgb/courses/toc/handout29.pdf).
Tractable Problem: a problem that is solvable by a polynomial-time algorithm. The upper bound is polynomial.
Intractable Problem: a problem that cannot be solved by a polynomial-time algorithm. The lower bound is exponential.
From this perspective, a definition for tractable distribution is that it takes polynomial-time to calculate the probability of this distribution at any given point.
If a distribution is in a closed-form expression, the probability of this distribution can definitely be calculated in polynomial-time, which, in the world of academia, means the distribution is tractable. Intractable distributions take equal to or more than exponential-time, which usually means that with existing computational resources, we can never calculate the probability at a given point with relatively "short" time (any time longer than polynomial-time is long...).
$\begingroup$
$\endgroup$
2
A distribution is called tractable if any marginal probability induced by it can be computed in linear time
-
2$\begingroup$ Are you citing some reference or authority? This is an intriguing but surprising characterization, so some indication of where it comes from and its scope of applicability would be of interest. $\endgroup$– whuber ♦Commented Apr 19, 2018 at 16:12
-
2$\begingroup$ I found the source where I have it from "On Using Sum-Product Networks For Multi-Label Classification" by Julissa Villanueva Llerena and Denis Deratani Mauá $\endgroup$– malochoCommented Jan 3, 2019 at 19:05