A little update on what I’ve been learning about lately.
Metropolis-Hastings is an algorithm for sampling random values out of a probability distribution. Effectively, for a function f(x) you wish to simulate where the curve is higher it is more probable that a random number will be chosen from there. Uniform sampling of the range would mean that all x values on the graph have an even probability of being chosen, this could be simulated by saying f(x) = 1.
However, if the function f(x) represents a curve then the number of samples in high energy (probability) regions needs to be more dense. This can be seen in the simulations of f(x) = sqrt(x-1) and f(x) = sin(1/x) below.
Metropolis-Hastings is best suited to problems where Direct Sampling and other more efficient solutions are not available. Because it only relies on the availability of a computable function f(x) and a proposal density Q(x|x*) M-H can correctly sample unusual probability distributions that would else-wise be difficult or impossible to compute. This can be seen below in the simulations of the sine function f(x) = sin(x) + 1.5.
Matlab code for Metropolis-Hastings Monte Carlo Integration (for generating samples)
Below is the Matlab code used to generate the above graph. By modifying the function f(x), the sample count N, the proposal distribution and it’s variance qV, and the upper and lower truncation bounds LB & HB any PDF can be simulated.
Work continues and it’s going well! Over the last week I have been teaching myself Bayesian Statistics which allows you to think about probability in terms of degrees of belief. It is also predicated on the concept of parameters, or prior known data, allowing you to update the probability of something happening in the future. This allows for convergent solutions on unknown probabilities which useful in graphics in terms of being able to fully sample arbitrary probability distributions.
After a minor crisis that I am horribly unprepared to start my PhD in October I thought I’d try to delve back into the world of graphics with something simple (ha). I decided to try and extend my Java Path Tracer to support a rendering mode for Bi-Directional Path Tracing. Something which I now realize is easier said than done. Ideally if I had had the time I would have introduced Bi-Directional Path Tracing (BDPT) to my dissertation project last year; however, I simply never had the time to wrap my head around all the mathematics so I left it out.
The image above was rendered at 640 x 480 but I have downsampled the image here to 320 x 240 to make up for the fact I was only able to render 100 samples before my computer BSOD’d. That’s right, because if you can make a Java program cause a BSOD then you know something is terribly amiss. My theory is that it’s simply too much recursion for the JVM. Even though I am running the 64bit version with an increased memory quota the stack for function calls is still (annoyingly) a memory limited 32bit stack. And seeing as this is just a toy project I am working on whenever I start to panic about next year it doesn’t seem worth spending the time to convert the whole thing to an iterative renderer from a recursive one.
Program
