This must be the best explanation of importance sampling available online, or at least on YT. And this channel in general is such a gem. Can't wait for more of your content
One interesting use of importance sampling is in path tracing (similar to ray tracing) in computer graphics, since path tracing is a Monte-Carlo method for computing the rendering equation. You can use importance sampling to get a better (less noisy) image with the same number of samples by using a sampling distribution which provides more frequent samples where the contribution from the BRDF/BSDF is higher, essentially sampling fewer dim paths which don't contribute to the total lighting of a pixel.
Every single word you say it's the absolute minimum for bestly conveying and explaining the full meaning of the formulas. Congratulations, and thank you for being an excellent teacher
This is THE best explanation of importance sampling I have come across. I'm studying for a PhD in Astrophysics, I've been linked to so many textbooks and college courses that make it really confusing. This was so simple and has really helped me understand this and move on to further topics. Thank you so much!
Well I was trying to understand variational inference but with no luck. This gem helped to me. To be honest this is the best video on topic and this guy is a brilliant teacher. Please make more of this kind of videos.
Wow that's an awesome explanation. I'm taking a Monte Carlo STATS class right now and this was far more clear then my professor was about what is actually happening here. Great video!
You earned this sub. Fantastic quality! This is also the most intuitive explanation of a concept like this I've ever seen! I sometimes think other channels with similar topics either ramble a bit much or go too fast in parts and I get lost, but this is just the right amount of building the foundation slowly and confidently to arrive at the final idea. Keep going with these videos and you are sure to get algorithmed eventually 👍
Thank you very much! It's a work in progress too. I'm learning the rhythm and what does/doesn't need to be said. Things will get better and I'm sure it'll get recognized.
This is exceptionally well explained. Just one suggestion, when explaining remove yourself when going down the analytical steps and bring yourself back. Grabs attention instantly.
Excellent video! I find myself lost in graduate statistic books, since they often explain concepts like this based on a lot of other statistical concepts, that I do not always have a good understanding for. It certainly helped to broaden the perspective a bit. It is easy to find excellent recourses on the most common and hyped methods, but not important but often overlooked topics like this. Thanks!
Thank you that's a big point of the channel. All the basic topics get covered at a high quality level, but there's clearly a real appetite for a few steps beyond it.
Amazing visualization and lucid explanation ❤This was the kind of video that bring you joy of understanding, appreciate the beauty of math and people behind the original idea! Bring your favorite wine to watch this!
Nice video, thank you ! The last condition for "When is Important Sampling used" is a sufficient condition for the use of IS rather than a necessary condition in my opinion. In Reinforcement Learning we try to evaluate values (the f(x)) for a target policy (the p(x)) using a sampling policy (the q(x)). It is used because using p is not sample efficient as it only can be used with recently sampled data. Using q allows us to make use of the all data sampled since the beginning of the training. But we are not at all choosing q to be high where |pf| is.
!! It's wild you mentioned that. I actually made this vid as a pre-req to my RL sequence. Yes! The IS case I mentioned here is not the full story. I tried to allude to that a bit in the intro :)
Wow - this must have been a lot of work to do. A clear structure, so many details, theoretical knowledge as well as practical tips, astonishing/valuable graphics and super clear audio. Thank you!
Thank you very much for the great intuition on this technique ! I am using it to understand the SMC algorithm, where Importance Sampling is a key ingredient.
I think this is the kind of video that you have to look when you already have more or less idea of what the algorithm does, and then it helps you to summarize and understand better.
OMG, YOU SAVE MY excessive thoughts about how to handle the theoretical side in the practical side (in Particle filter - based SLAM algorithms for probabilistic mobile robotics systems) . Many thanks.
Fantastic video! I'm giving an internal lit review on quasi-adiabatic path integrals and this really helped me get some perspective on the core of the method! Super clear lecture and great use of visuals! Thank you so much!
Those topics are widely used in computer graphics but they are explained in such a convoluted way. For example I only understood what "unbiased" means with your explanation. You do have a tallent to explain things!
I stumbled upon your kelly criterion video some time ago and liked it. Now, properly looking at your channel, I'm blown away. Really high quality explanations (props to the usage of manim as well) of hard to understand ideas 👏👏👏
Oh yea, the quality is improving. Took me a long time but I think I'm getting the essentials. I'm also not using Manim.. maybe I should but I've always wanted to build something bespoke for this.
Great video! If I would like to add anything it would be maybe 2-3 questions in the end of the presented material to see if you did grasp the key points in the video (with answers in the description)! Thank you
I think the pace of this video is great, but I missed the motivation for this up until the very end. The why should generally come first: "why do I need this explanation?"
I think what I like the most about your videos is the reference book by your right, always showing up :) Do you have a complete list of your recommended/favorite books?
lol you noticed! Yea these textbooks are essential :) I think one day I'll put together a list of my favorites. I can tell you a few of them here: Machine Learning: A Probabilistic Perspective is definitely my number 1. There's actually a new edition available for pre-order on Kevin Murphy's site. Second would be The Elements of Statistical Learning, a classic. Then Deep Learning by Bengio et al. And, just because I'm reading it right now, I really love Reinforcement Learning by Sutton and Barto. It does a great job creating a unifying framework on a wide and rapidly evolving field.
You said: “The dimension of x is high ... This integral is impossible to calculate exactly ... A small set of samples have an outsize impact on the average.” This describes my doctoral dissertation problem in polymer chemistry. I wanted to determine average thermodynamic properties of a desirable variable like the end to end distance or radius of gyration (average distance of molecular units from center of mass) of a very long polymer molecule of, say, several thousand units. In thermodynamics this is the integral of [the end-to-end distance times exp(-U/kt)d(tau)] where U is energy, t is temperature, and k is Boltzmann’s constant, divided by the integral of (exp-U/kt)d(tau), also called the partition function. Tau is the volume element of the phase space for the molecule and represents all possible geometric conformations or shapes of the molecule. The conformation of the polymer is completely defined geometrically by listing the dihedral angles about successive backbone atoms from one end to the other (ignoring side chains for simplicity). Given such a list, you can generate all of the molecule’s coordinates in three dimensions, from which you can then calculate the energy of the molecule, U, using any number of standard chemical functions. Each of the dihedral angles can vary continuously from 0 to 2pi. The multi-dimensional “phase space” defined by tau is unwieldy because tiny changes in any dihedral angle can bring distant atoms together in energetically unpredictable ways and there is no analytical solution to the integral. In the 1950s Monte Carlo methods were used to generate coordinates for a single polymer molecule by using a random number generator to create a list of dihedral angles and then calculating (a) the end-to-end distance of the polymer whose angles corresponded to the list and (b) its energy. In a single computer “experiment” researchers could generate thousands of polymers and calculate the average end-to-end distance using the exponential function as the weighting function. In principle, this worked, but in practice, polymers with very high energies due to atomic overlaps and therefore very low weights dominated the outputs so the averages converged too slowly to be useful. In the 1960s Moti Lal, a chemist at Unilever Labs in the UK, became aware of Metropolis’s seminal paper from 1953 in the Journal of Chemical Physics that laid out the statistical ideas of importance sampling and applied them to the polymer problem. However, the available computing power (IBM 360/50) confined his polymers to 30 monomer units on a 2-dimensional spatial lattice. As a graduate student at NYU 1968 I had access to a Control Data Corp. CDC 6600 supercomputer at the Courant Institute and used the Metropolis-Lal method to generate more realistic polymers in 3 dimensions with free rotation about their backbone bonds (i.e., not restricted to an artificial lattice). Just as you pointed out, samples generated with this method tended to represent more “important” regions of polymer conformation space so it took fewer samples to get stable averages. This allowed me to also generate the numerical distributions of end-to-end distances of polymers of several hundred units and with sufficient accuracy to determine which of a number of theoretical analytic functions best described those distributions.
Thank you for the excellent tutorial! I have a little problem. What is the V_p[f(x)] called, which is not just variance, I assume? I want to search for the calculation method, however I don't know the keyword to search.
It is just variance, basically. It's the variance of the random variable defined by sampling x (according to the distribution p(x)) and plugging it into f(x). So you can do this way. Sample x's with p(x). plug them into f(x), giving many f(x)'s samples. Calculate the empirical variance of these samples. If you want to compute it exactly, then you do the p(x)f(x) integration to get the mean. And then you did integration for the variance. This answer your Q?
I'm finishing up part 6 on the RL series, which is a huge vid that's taking a long time (~30 min). BUT, after that I've committed to making short, more bite-sized videos (4-12 minutes). I can upload more frequently that way and it's less on the audience.
Thx again for the great content. I have two questions though. * At 10:04, how did our new function (p(x)/q(x))*f(x) perfectly fit to p(x)? * In variational encoders, the q(z) must be selected such that KL(q||p) must be minimum. But as far as I understood, it's another concept, right? Because in your example q is a very different distribution than p.
Hey Ali, thanks! To your questions: 1) It's not terribly surprising they are close. p(x) is a component (p(x)/q(x))*f(x). If you imagine another case (but just as arbitrary as what I was showing on screen), where f(x) = 1 for all x and q(x) is the uniform distribution.. then (p(x)/q(x))*f(x) and p(x) would be the same thing! 2) Yes q in the variational inference is a separate concept. There are connections, but the criteria for selecting q in this case vs that case are different, so you should think about the q's differently.
@@kafaayari Variational autoencoders are an algorithm which is a special case of variational EM , where both model parameters ( usually denoted by theta, the decoder ) and " variational " parameters (usually denoted by phi the encoder ) are learnt at the same time . For variational * inference *, where the theta are known , and one only has to "learn" the variational parameters , there is a deep connection with importance sampling . In fact , it is nothing more (or less) than a special case of *adaptive* importance sampling, where the adaptation metric is the KL divergence to some posterior distribution . Other adaptive IS methods are more sophisticated , as for example they always use *all* samples previously generated in the adaptation (in VI parlance, ) , and *not* just the ones from the latest iteration (as popular VI techniques do ) . These concepts are surprisingly not well understood in the VI literature (although they are more in the AIS literature) . I can recommend proceedings.mlr.press/v151/kviman22a/kviman22a.pdf for some recent work on these connections, but there is more. By the way @Mutual Information , nice video :)
