[Haskell-cafe] Help on syntactic sugar for combining lazy & strict monads?

Tue Aug 10 15:57:15 UTC 2021

Hi Olaf,

If you recall, I actually wrote to this list asking for help. Adam 
Scibior's response was quite helpful, but this conversation, as far as I 
can tell, has not provided any help, so I will regretfully have to stop 
replying at some point.  Unfortunately, I don't have enough time to 
respond to everything - my apologies!

I may be able to clarify some of the questions that you asked. But I 
doubt that I can actually satisfy all of your concerns.  So, perhaps 
these responses will mostly clarify our points of disagreement.

1. It seems like you are assuming that the semantics of a probabilistic 
program is determined by running it under a rejection sampling 
interpreter.  Such an interpreter would:

   (a) interpret statements like "x <- normal 0 1" by performing a 
(pseudo)random sample from the distribution

   (b) interpret statements like "2.0 `observed_from` normal z 1`" by 
first sampling from "normal z 1" and then rejecting the program run if 
the sample from "normal z 1" does not satisfy (2.0==).

That is a rejection sampler, and it would work if the observations did 
not have probability 0.  But it is only one kind of sampler.  There are 
other kinds of samplers, that you (maybe?) have not considered:

   * importance sampling: the paper that I recommended is using the 
observation statements to weight the samples by the probability DENSITY 
of the observations.  This is called "importance sampling" -- we 
generate sampling from one distribution, but reweight them to 
approximate a different distribution.

   * MCMC: my approach is based on MCMC, and so performs a random walk 
over the space of program traces.  In this case, running the program 
must compute the probability DENSITY of samples from the prior (like "x 
<- normal 0 1") as well as observations (like observing 2.0 from "normal 
z 1").

These three alternative interpreters are alternative ways of sampling 
from the posterior distribution.  However, none of these three 
interpreters constitutes the semantics of the probabilistic program.

I mentioned the Giry monad (which I am no expert on) because it gives 
semantics that is not based on any interpreter.  I do not think that the 
semantics of probabilistic programs should be given by an interpreter.  
Perhaps we disagree on this.

2. You wrote "If the observe_from statement is never demanded, then what 
semantics should it have?"

> run_lazy $ do
>    x <- normal 0 1
>    y <- normal x 1
>    z <- normal y 1
>    2.0 `observe_from` normal z 1
>    return y

The semantics that it should have seems fairly obvious?

This program leads to the following (un-normalized!) probability density 
on (x,y,z):

     Pr(x) * Pr(y|x) * Pr(z|y) * Pr(2.0|z) = normal_pdf(x,0,1) * 
normal_pdf(y,x,1) * normal_pdf(z,y,1) * normal_pdf(2.0,z,1)

Therefore, the program leads to both (i) a distribution on (x,y,z) and 
(ii) a distribution on the return value y.

I don't think this has anything to to with whether there is a result 
that is demanded, but perhaps we disagree on that.

3. You wrote "But conditioning usually is a function "Observation a -> 
Dist a -> Dist a" so you must use the result of the conditioning somehow."

I was initially very confused by this, because it sounded like you are 
saying that because people USUALLY do something, therefore I HAVE AN 
OBLIGATION to do something.  But, now I realize that you mean "IT MUST 
BE THE CASE that you use the result of the conditioning somehow".  It is 
indeed the case that the "observe_from" command affects the intepreter 
somehow.

I think this is pretty simple ... the `observe_from` statement has a 
side-effect.  For both (i) importance-sampling interpreters and (ii) 
MCMC interpreters, the side-effect is to weight the current trace by the 
probability (or probability density) of the observation.

However, like the "put" command in the state monad, the result "()" of 
the observation is not demanded.  So in that sense, I am not "using the 
result".  It is perhaps interesting that the lazy state monad does not 
have the problem that "put" commands are ignored.

4. You wrote "And isn't the principle of Monte Carlo to approximate the 
posterior by sampling from it?"

I am not really sure what this means.  Sometimes you can generate 
samples directly from the posterior, and sometimes you can't.  In most 
situations where you have observations, you CANNOT generate samples from 
the posterior.

For example, in MCMC, we talk about the distribution of the sampled 
points CONVERGING to the posterior.  If an MCMC chain has points X[t] 
for t = 0...\infty, there is no t where X[t] is distributed according to 
the posterior distribution.

5. You wrote "I claim that once you have typed everything, it becomes 
clear where the problem is."

That is an interesting claim.  I don't think that there is actually 
"problem" per se, so I am not were that typing everything can reveal 
where it is.  Also, this exact same issue comes up in the Practical 
Probabilistic Programming with Monads paper, and they have typed 
everything.  So, I guess I disbelieve this claim, until I see evidence 
to the contrary.

I guess we will see, after I finish programming the type system.

6. You wrote:

> I believe I understand the Giry monad well, and it is my measuring 
> stick for functional probabilistic programming. Even more well-suited 
> for programming ought to be the valuation monad, because that is a 
> monad on domains, the [*] semantic spaces of the lambda calculus. 
> Unfortunately, to my knowledge until now attempts were unsuccessful to 
> find a cartesian closed category of domains which is also closed under 
> this probabilistic powerdomain construction.
>
> [*] There are of course other semantics, domains being one option. 

Given your expertise in this area, I doubt that I can shed any light on 
this.  I presume that you have read 
https://arxiv.org/pdf/1811.04196.pdf, and similar papers.  This is 
getting pretty far afield from my original question.

7. You wrote:

>>
>> 2. The paper "Practical Probabilistic Programming with Monads" - 
>> https://doi.org/10.1145/2804302.2804317
>
> Wasn't that what you linked to in your original post? As said above, 
> measure spaces is the wrong target category, in my opinion. There is 
> too much non constructive stuff in there. See the work of Culbertson 
> and Sturtz, which is categorically nice but not very constructive.

The link was indeed in my original post, but it did not seem like you 
had read it, since you did not consider the possibility of probabilistic 
programs generating WEIGHTED samples.

Also, the idea that probabilistic programs should not yield measures 
seems weird.  Partly because I am not sure what your alternative is, and 
partly because everybody else seems to disagree with you.  For example, 
the following paper assumes measures:

https://link.springer.com/chapter/10.1007/978-3-030-72019-3_16

Again, this is getting pretty far away from my original question.

8. You wrote:

> Perhaps I am being too much of a point-free topologist here. Call me 
> pedantic. Or I don't understand sampling at all. To me, a point is an 
> idealised object, only open sets really exist and are observable. If 
> the space is discrete, points are open sets. But on the real line you 
> can not measure with infinite precision, so any observation must 
> contain an interval. That aligns very nicely with functional 
> programming, where only finite parts of infinite lazy structures are 
> ever observable, and these finite parts are the open sets in the 
> domain semantics. So please explain how observing 2.0 from a 
> continuous distribution is not nonsensical.

You haven't actually shown that observing 2.0 from a continuous 
distribution is nonsensical.  What you have done is stated that you 
don't like it, and that you would like people to represent observations 
as intervals instead of points.  However, its not my job to convince you 
that point observations make sense, so I think I'll just leave that 
where it is.

OK, that's enough for now.

-BenRI

On 7/22/21 2:15 AM, Olaf Klinke wrote:
>> However, a lazy interpreter causes problems when trying to introduce
>> *observation* statements (aka conditioning statements) into the monad
>> [3].  For example,
>>
>> run_lazy $ do
>>    x <- normal 0 1
>>    y <- normal x 1
>>    z <- normal y 1
>>    2.0 `observe_from` normal z 1
>>    return y
>>
>> In the above code fragment, y will be forced because it is returned, and
>> y will force x.  However, the "observe_from" statement will never be
>> forced, because it does not produce a result that is demanded.
>
> I'm very confused. If the observe_from statement is never demanded, 
> then what semantics should it have? What is the type of observe_from? 
> It seems it is
> a -> m a -> m ()
> for whatever monad m you are using. But conditioning usually is a 
> function
> Observation a -> Dist a -> Dist a
> so you must use the result of the conditioning somehow. And isn't the 
> principle of Monte Carlo to approximate the posterior by sampling from 
> it? I tend to agree with your suggestion that observations and 
> sampling can not be mixed (in the same do-notation) but the latter 
> have to be collected in a prior, then conditioned by an observation.
>
> What is the semantic connection between your sample and obsersvation 
> monad? What is the connection between both and the semantic 
> probability distributions? I claim that once you have typed 
> everything, it becomes clear where the problem is.
>
> Olaf
>
> P.S. It has always bugged me that probabilists use elements and events 
> interchangingly, while this can only be done on discrete spaces. So 
> above I would rather like to write
> (2.0==) `observe_from` (normal 0 1)
> which still is a non-sensical statement if (normal 0 1) is a 
> continuous distribution where each point set has probability zero.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20210810/9ac70e9d/attachment.html>