stan for discrete parameters

[Andrew Gelman]

Hi all.
Here's a thought: What if we throw the "stan for discrete parameters" problem out into the world? We could write a short document with our ideas (various possible approaches and the pluses and minuses of them) and then maybe someone will go out and solve it. Or we could try to recruit a Ph.D. student, Columbia or Harvard stat or Princeton CS. What do you think?
A

[Michael Betancourt]

It seems like the right scope, and there's definitely interest from the community.

> --
> You received this message because you are subscribed to the Google Groups "stan development mailing list" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to stan-dev+u...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Nigel/essence]

It is certainly an interest in my area, plus a closely related issue of multi modal problems. They are not at all trivial!

At present I am using DREAM-type techniques to do these, in combination with NUTS for the continuous variables.

[Bob Carpenter]

On 3/17/13 10:48 AM, Nigel/essence wrote:
> On Sunday, 17 March 2013 00:17:52 UTC, Andrew Gelman wrote:
>> Hi all.
>>
>> Here's a thought: What if we throw the "stan for discrete parameters" problem out into the world?

So much for "what if" :-) But hey, I'm all for throwing
everything out into the world, which is why Stan's open
source and our dev group's out in the open.

One reason we haven't done this is just time.

Also, we're already a bit overwhelmed trying to sort out
all the responses to helping us with Python.

This isn't like a bunch of independent research projects,
because all the code that goes into and around Stan needs
to be fairly tightly integrated. For instance, anyone dealing with discrete
parameters in any deeper way than option (1) below is going to be down in the
guts of our parser, code generator, and sampler interface, and so has to be
sure not to mess up anything that's there that already works.

Writing a new continuous sampler, like Yuanjun did, only
involves half the battle -- he needed to use all the interfaces
we have, but only really had tight integration with one class.
That is, new continuous samplers can be added pretty modularly
at this point.

Writing some new functions, like Peter's doing, is more isolated
still. There's nothing to integrate with other than to use
some of our libraries. He's working on Metropolis now, which is
ramping up to the next level of integration.

If we really want to start recruting more developers,
we're going to need to figure out some process to manage
the design and integration of the various parts. It's
a qualitatively different game when there are more than two or
three people working on a project and the various pieces can't
be made wholly modular.

Now, to get on the actual answer...

>> We could write a short document with our ideas (various possible approaches and the pluses and minuses of them) and
>> then maybe someone will go out and solve it. Or we could try to recruit a Ph.D. student, Columbia
>> or Harvard stat or Princeton CS. What do you think?

I can summarize pretty quickly with the same info as is
on our TO-DO list:

1. We use the entire log probability function to compute the
conditional probability of a discrete parameter up to a proportion, then
use:

a. (adaptive) slice sampling for count (unbounded) parameters

b. Gibbs (exact discrete) for categorical (bounded) parameters

PROS: very easy to implement
models look exactly as now, but allow discrete parmaeters

CONS: very very inefficient

2. Same as 1, but we try to find a less computationally
intensive way to compute the log conditional probability up to
a proportion

-- Andrew thinks there may be some way to calculate which parts
of the code need to be executed

PROS: models look like now
CONS: we can't figure out how to do it (remember that
Stan is Turing complete as a language)

An extreme approach would be to restrict to BUGS-like directed
graphical models so we can calculate the Markov blanket

-- Andrew thinks there may also be some way to annotate which
parts of the code need to be executed for each conditional

PROS: ??
CONS: we can't figure out how to do it;
users have to learn annotation language;
makes regular models uglier

3. Same as 1, but we introduce a new block to define the discrete
conditional probabilities

-- PROS: easy to implement;
very efficient
-- CONS: user has to write discrete model twice;
user has to caclulate Markov blanket, which if they get
wrong, leads to an inconsistent model

We can mitigate the consistency issue somewhat by imposing checks
of values up to a proportion, but only for finitely many inputs

4. Hope someone else is more clever than we are.

> It is certainly an interest in my area, plus a closely related issue of multi modal problems. They are not at all trivial!
>
> At present I am using DREAM-type techniques to do these, in combination with NUTS for the continuous variables.

Is there a paper on how to do ensemble methods like DREAM
for discrete parameters somewhere?

- Bob

[Ben Goodrich]

On Sunday, March 17, 2013 4:11:14 PM UTC-4, Bob Carpenter wrote:

If we really want to start recruting more developers,
we're going to need to figure out some process to manage
the design and integration of the various parts.  It's
a qualitatively different game when there are more than two or
three people working on a project and the various pieces can't
be made wholly modular.

Git was designed for Linux kernel development and is used by many projects with hundreds of developers and gigabytes of source code. So, I think we can handle it. The problem as I see it is that we have not fully abandoned cvs / svn workflows. If someone has an idea for how to do something, they should make a branch, implement the idea, and submit a pull request. And it won't get pulled until we are sure it doesn't break what already works.

Ben

[Bob Carpenter]

I'm one of the main culprits in SVN-ishness. :-(
I want to be a better person.

But what I'm talking about is not managing workflow
in git, but in managing the design and growth of Stan.

If somebody wants to add new special functions or
a distribution or even a new sampler,
it's pretty easy to manage. But working on the discrete
samplers requires a much deeper integration down to the
guts of Stan.

How does Linux track who's doing what and plan out
what needs to be done and who's doing it? I've only
personally worked deeply on one project with 20 or 30
developers (the speech recognizer/dialogue system when
I was at SpeechWorks). For that, we had the APIs for
the submodules pretty well scoped out so we could
work modularly without stomping on each others' toes
too much.

I've committed code to much bigger projects
by patching little modules -- that's also easy to manage.
But I've never undertaken an API design in that context.

- Bob

[Nigel/essence]

On Sunday, 17 March 2013 00:17:52 UTC, Andrew Gelman wrote:

DREAMZ is designed for multi modal situations. I can't possibly comment on whether it is a true markov chain or not, but hey, when you are in the dark, you welcome any light there is. A search on Dreamz (rather than Dream) will find a paper.

In a way, discrete is easier than multi modal - you know how far apart the modes are. So if you have a rich enough chain, you should be able to explore all possible discrete cases.

I think multi modal is hard enough for optimization, and is simply a dream (sic) for MCMC.

To put it into context, I am right now (i.e. I am currently running tests on my client's cluster) using it with 60 continuous modifiers and 10 discrete modfifiers, with the discrete taking integer values 1 to 5.

The DREAMZ danger is collapsing onto a single mode/discrete values.

I never looked at tempering schemes, apart from my initial studies, as they were simply too inefficient for me.

[Andrew Gelman]

Nigel:
That's all fine, but what I'm looking for to start is something simpler, as right now we can't fit discrete models in Stan _at all_. I'd like to get something that's general and robust, then we'd have a platform where we could move on to do more.
A

[Bob Carpenter]

Andrew -- don't you also want something that's not too slow?
If we do the really dumb naive thing, we'll be crushed by
JAGS on discrete models speed-wise. If you really think it's
a good idea, option 1 (use the whole log prob function) wouldn't be
that hard to implement.

Nigel -- thanks for the pointer. I'll check it out.
We're not trying to deal with multimodality -- we know it's
basically impossible (intractable in the computational sense)
for most multimodal models of interest.

- Bob

[Andrew Gelman]

Bob
Yes, I want something that's not too slow. I agree that there's no point in implementing the dumb naive thing. Based on our most recent conversation on the topic, I think the basic slice sampler with duplicate coding is a good way to start.
A

[Ben Goodrich]

On Sunday, March 17, 2013 4:49:12 PM UTC-4, Bob Carpenter wrote:

How does Linux track who's doing what and plan out
what needs to be done and who's doing it?  I've only
personally worked deeply on one project with 20 or 30
developers (the speech recognizer/dialogue system when
I was at SpeechWorks).  For that, we had the APIs for
the submodules pretty well scoped out so we could
work modularly without stomping on each others' toes
too much.

There isn't much of a top-down plan, more of a bottom-up thing where individuals or companies want to add something. There are a few dozen submaintainers of various parts of the Linux kernel, and they need to ack any patches that affect what they submaintain. But most importantly, stuff just doesn't get merged into the master branch until the anticipated and unanticipated problems have been worked out. In other words, the master branch is pretty much just for merges of well-tested code.

Ben