3 ms·

Does anyone have the experience with speed of convergence for some advanced models? And, defining sequence models in these probabilistic programming languages?

Does anyone have the experience with speed of convergence for some advanced models? And, defining sequence models in these probabilistic programming languages? Seems most (if not all) probabilistic programming languages use sampling as a general algorithm for training models. So, I guess it would be a hard job to express something like HMMs or CRFs that would fit into the framework (I guess one can easily train HMMs/CRFs with a fixed length of a sequence, but not undefined length).

nextos 11y ago
You can easily encode any generative sequence model in e.g. Church (Scheme-based), Anglican (Clojure-based) or PyMC (Python-based). These are Turing-complete, so they can model any sampleable (computable) distribution. See http://forestdb.org/ http://forestdb.org/ for some examples. E.g. an infinite HMM. I have no experience with Stan. There was some controversy on whether it is Turing-complete, but I cannot elaborate on that. The obvious disadvantage of using a language that is too expressive for something as simple as an HMM is that you loose the nice performance guarantees given by all specialized algorithms such as Viterbi. Theoretically, they can achieve good efficiency by performing program transformations (e.g. with abstract interpretation). But in practice, we are still a bit far from that. A nice trick is to implement your generative model in something very efficient (e.g. Probabilisitic C or something GPU-based). You can then forget the burden of having to encode your own sampling procedure, but at the same time inference might be tractable.
- mjn 11y ago
  There's some research on automatically deriving efficient algorithms for classes of distributions, e.g. getting a specialized EM-like algorithm for anything where EM-like algorithms are applicable: http://machinelearning.wustl.edu/mlpapers/paper_files/AA24.pdf http://machinelearning.wustl.edu/mlpapers/paper_files/AA24.p... But obviously that doesn't cover classes as big as "anything expressible in Church", so there's a pretty big gap. It's possible that languages like Church could use techniques like that as part of an optimizing compiler that recognizes specializable patterns, the way regular compilers do loop transformations and auto-vectorization and such. But, like auto-vectorization, not that easy to do.
  - nextos 11y ago
    Sure, I mentioned abstract interpretation, but as you say all optimizing compiler techniques might be applicable.
chmullig 11y ago
In my experience, Stan performance is decent with many models, particularly if all relevant operations are vectorized and the data sets are "reasonable." However it's easy to accidentally walk off a cliff, and write a model that takes days to fit. Additionally the real time output is a little lackluster, so it's hard to know how you're doing until it finishes (I hear they're working on that for ShinyStan). I haven't done any HMMs or CRFs with Stan, but don't see why you couldn't do them. Passing in the data likely requires some tricks with arrays and indexing, but it's totally doable. Probably unlikely that you'd beat standard, custom algorithms, but if your HMM was part of a larger model, it might make sense.
- jrnold 11y ago
  Admittedly Stan doesn't work for all problems, but where I've seen a lot of issues in "bad" performance by Stan is when people try to fit models that are unidentified or weakly identified. Unlike some other algorithms which will give back the wrong answer quickly with the user none the wiser, Stan's HMC will try to do what the model says - sample over the whole unidentified space, and it takes a while to sample R^n. What I've seen in Stan's mailing list is that in practice a lot of people have been fitting poorly identified models without realizing it.
dustintran 11y ago
Most all probabilistic programming languages in fact treat every model as equivalent to an HMM. So certainly inference on them can be done.

nextos 11y ago

You can easily encode any generative sequence model in e.g. Church (Scheme-based), Anglican (Clojure-based) or PyMC (Python-based). These are Turing-complete, so they can model any sampleable (computable) distribution. See http://forestdb.org/ http://forestdb.org/ for some examples. E.g. an infinite HMM. I have no experience with Stan. There was some controversy on whether it is Turing-complete, but I cannot elaborate on that. The obvious disadvantage of using a language that is too expressive for something as simple as an HMM is that you loose the nice performance guarantees given by all specialized algorithms such as Viterbi. Theoretically, they can achieve good efficiency by performing program transformations (e.g. with abstract interpretation). But in practice, we are still a bit far from that. A nice trick is to implement your generative model in something very efficient (e.g. Probabilisitic C or something GPU-based). You can then forget the burden of having to encode your own sampling procedure, but at the same time inference might be tractable.

mjn 11y ago
There's some research on automatically deriving efficient algorithms for classes of distributions, e.g. getting a specialized EM-like algorithm for anything where EM-like algorithms are applicable: http://machinelearning.wustl.edu/mlpapers/paper_files/AA24.pdf http://machinelearning.wustl.edu/mlpapers/paper_files/AA24.p... But obviously that doesn't cover classes as big as "anything expressible in Church", so there's a pretty big gap. It's possible that languages like Church could use techniques like that as part of an optimizing compiler that recognizes specializable patterns, the way regular compilers do loop transformations and auto-vectorization and such. But, like auto-vectorization, not that easy to do.
- nextos 11y ago
  Sure, I mentioned abstract interpretation, but as you say all optimizing compiler techniques might be applicable.

chmullig 11y ago

In my experience, Stan performance is decent with many models, particularly if all relevant operations are vectorized and the data sets are "reasonable." However it's easy to accidentally walk off a cliff, and write a model that takes days to fit. Additionally the real time output is a little lackluster, so it's hard to know how you're doing until it finishes (I hear they're working on that for ShinyStan). I haven't done any HMMs or CRFs with Stan, but don't see why you couldn't do them. Passing in the data likely requires some tricks with arrays and indexing, but it's totally doable. Probably unlikely that you'd beat standard, custom algorithms, but if your HMM was part of a larger model, it might make sense.

jrnold 11y ago
Admittedly Stan doesn't work for all problems, but where I've seen a lot of issues in "bad" performance by Stan is when people try to fit models that are unidentified or weakly identified. Unlike some other algorithms which will give back the wrong answer quickly with the user none the wiser, Stan's HMC will try to do what the model says - sample over the whole unidentified space, and it takes a while to sample R^n. What I've seen in Stan's mailing list is that in practice a lot of people have been fitting poorly identified models without realizing it.

dustintran 11y ago

Most all probabilistic programming languages in fact treat every model as equivalent to an HMM. So certainly inference on them can be done.