l“Poly(size)” is great, but not if size is exponential!
Expressive language can capture structure, which can be exploited for faster inference
It is well-known that the
more expressive a representation language is, the harder it is to perform
inference in the language.Clearly,
the corollary is that we should use less expressive representations.So why am I trying to sell you a language
that combines relational logic on the one hand, probabilities on the
other?Well, complexity can often be
misleading.Polynomial in the size of
a representation is great, but not if the size is itself exponential.Specifically, many tasks are linear time in
an atomic representation --- we simply enumerate the worlds.But the number of worlds is huge. Thus,
more expressive languages are not necessarily harder.Furthermore, expressive languages often
contain structure that allows us to perform tasks much more efficiently.So, by picking the “right” type of
expressive power, we can often do inference much more efficiently.