Thompson Sampling : Data Science Concepts

[Music] hey everyone welcome back so today we're going to be continuing our talk about both multi-arm bandit and bayesian stats with a method that's kind of at the intersection of that called thompson sampling so we'll start with the exact same setup as the multi-arm bandit video you're this crazy professor and you've come to lecture in a small town for a couple of years now the small town only has two restaurants r1 and r2 and you're going to go to one of them each and every night and the big problem for you since you have never been to them before there's no reviews online is trying to figure out whether or not you like one restaurant more than the other and so you get a certain level of satisfaction by visiting each restaurant and let's say that restaurant one the amount of satisfaction you get on any given night is normally distributed with mean five and standard deviation one so on average you're going to get five units of satisfaction by going to restaurant one but there's a standard deviation of one so you can get less or more than that restaurant 2 is also a normal distribution with standard deviation 1 but the mean here is 6. so if you knew this information if you came to the restaurant and you just somehow knew this distributions you would definitely just go to restaurant 2 every single night because it's going to give you a higher average satisfaction same exact standard deviation but obviously you don't so the big struggle is how do we design a good method that's going to be able to allow us to visit restaurants and form some kind of good foundation about which one is giving us a higher average satisfaction than the other obviously you need a couple of trips to each one you can't just do like one trip to each because of these standard deviations that could give you the wrong answer at the end of the day so we want some kind of method that balances exploration and exploitation so we talked about this a bunch in our multi-armed bandit but the exploration piece is you want to try every single restaurant in the real world there's going to be like hundreds of restaurants in your city right so you want to do this balance between trying all of them a little bit to get a feel for if you like it or not but also making sure that you're spending your time going to the ones that you know you already like so this is kind of a trade-off thompson sampling has a very elegant solution to it now i want to make sure to make it known that these mu eyes are unknown in this video so i don't know that the average of the restaurant one is five units and i don't know that the average of restaurant two is six units but for the purposes of this video the sigma i which are one are known so for whatever reason i know that the standard deviations that i'm getting from these two restaurants are one we can talk about what if you don't know that which is the real world assumption that we would really have but let's say we know that for this video so thompson sampling being a bayesian method as you might expect starts with priors so given that we have not visited either restaurant even one time we are going to establish some kind of prior beliefs on the average satisfaction we get from each restaurant and we're going to initialize both of these restaurants priors to the same thing so we're going to say for both of these restaurants the average satisfaction mu 1 and mu 2 that i get is going to be normally distributed with mean 0 and standard deviation 100 so obviously this normal distribution is very very wide has a huge standard deviation and for that reason we call this a flat prior or uninformative prior invasion statistics which is just any prior where you're putting about equal weight on many many many possible outcomes so you can see although this is a normal distribution and it is shaped like a bell curve in this area in the vicinity of zero it's almost a flat line so there's pretty much equal weight in all these things and why would we do this in bayesian stats this is to incorporate this knowledge this assumption that i honestly have no idea what the averages should be for these two restaurants i just got to town right now so i'm going to put as little much bias as possible into my prior and that's where we use a flat prior so this is an example of a flat prior here now believe it or not we actually have the prior and the likelihoods so the priors we just talked about the likelihoods we actually talked about before so the prior is answering the question about what is the distribution of this parameter before i even observe anything and then the likelihood is saying if you fix some value of that parameter then what is the distribution of the satisfaction i would get by visiting that restaurant and so we know both of these are normal distributions for example the first one is saying if mu 1 is equal to 5 then the satisfaction i get from a visit to that restaurant is going to be normally distributed with that mean 5 and as we said standard deviation 1. so we have our likelihoods here we have our prior here you know what's coming up we have to derive a posterior and it turns out in this situation since we have a lot of normal distributions around the posterior is also normal now this is one of those hand wavy parts of the video where i'm not going to prove to you that this is the posterior distribution if this is our setup but i will link a article below that basically talks about basically a table of if this is your prior and this is your likelihood then this is your posterior you can just look up your current situation in that table so take it for granted here that our posterior which again is going to be probability of a certain mu given s1 s2 all the way to sn so what are these these guys are visits to a restaurant so it's saying you visited this restaurant end times on n different nights and the satisfaction you got from the first knight is s1 then s2 then s3 all the way to sn so basically it's saying i visited end times and this is the satisfactions that i got given that data give me a distribution for the average satisfaction level from that restaurant and so this is going to be normally distributed with mu p mean mu p and standard deviation sigma p and these are the formulas here again that just comes from that table i was talking about so sigma p squared is going to be 1 over 100 squared 100 comes directly from that being the standard deviation of our prior plus n which is the number of visits you've made to the restaurant so far to the power of negative 1. so it's really just 1 over this inside part and then mu p the mean of the posterior distribution is going to be sigma p squared so basically the same quantity above times the sum of all of these visits to the restaurant now you know on this channel i don't feel great when i just throw formulas at you and this does seem like one of those places so let's remedy that by talking about the intuition behind this form so let's say i haven't visited either restaurant not even once so i've just arrived in town today think about what these formulas are going to be n is going to be 0 so 1 over 100 squared to the power of negative 1 that's just going to give us 100 squared and that's the variance so the standard deviation is going to be 100 of the posterior the mean is going to be 0 because the sum of my satisfactions is zero i haven't even visited once so currently on my first day in the city not even a visited restaurant even once i have a mean zero and a standard deviation 100 normal distribution which is the same thing as my prior so it's kind of this comfortable thing where my prior is my posterior when i don't have any evidence which is a very cool thing now let's think about what happens if i make one visit to one of the restaurants so now this n is equal to one and now this one over 100 squared just vanishes in proportion because now you have one plus something extremely small so this is basically just one and one to the power of negative one is just one so your standard deviation of your posterior is now one so it's gotten a lot tighter it's gone from a standard deviation of 100 to a standard deviation of one almost one after just one visit to a restaurant and what what happens to the mean here so the standard deviation squared we said was one so we kind of ignore that and your mean just becomes the sum of all your visits so far and since you've only had one visit the mean of your posterior is just that visit to the restaurant so after one visit to a restaurant your average of the posterior distribution is the value of that visit and the standard deviation is one now let's round out the story by talking about let's say you visited a restaurant many many times like a hundred times then n is equal to 100 this is still insignificant so now sigma p squared is going to be 1 over 100 and mu p is going to be the sum of those hundred visits divided by 100 which is just the empirical average of all those visits so you see that this posterior distribution encodes a lot of very intuitive things as you visit the restaurant many many many times the average of the posterior distribution is going to go to the average of your visits literally just taking the average of your visits and the standard deviation is going to get smaller and smaller and smaller and smaller the more visits you make because the standard deviation basically is just going to be 1 over n and so basically that's saying the more you visit a restaurant the more sure you become about the average of all the visits from that restaurant so now that we've spent some time talking about that let's go on to step two so step one was the main math the main understanding the rest is just a process here so now what we do is we sample from the posteriors so let's backtrack we're back to the day one where we haven't visited the restaurants even one time we're going to sample from this posterior the first posterior and the second posterior which currently are normal distributions with mean 0 and standard deviation 100 so that's going to give us some like huge values in either direction let's say that this one gives us 20 and the second one gives us negative 12. then we're going to visit the restaurant with the higher expected value so let's let's drill down on this a little bit so basically by sampling from this posterior and getting 20 we're saying that our current assumption about the average value we're gonna get from restaurant one is twenty the reason it's so far away from the truth is because again we're just dealing with our priors right now and the average satisfaction from visiting restaurant 2 is going to be negative 12. and so we're going to go to the restaurant that's giving us the higher average satisfaction which is going to be restaurant 1. so let's say we visit restaurant 1. now maybe for some of you alarm bells are going off because you're saying wait restaurant 1 is not the answer restaurant two has a higher mean so we're making a big mistake but we'll see how thompson sampling self-corrects so we go ahead and visit restaurant one and let's say we get a satisfaction of five which is well within the realm of what it could actually be that's the actual mean so then what we do is we update the posterior for the restaurant that we just visited and that update rule we talked about all of that just now so we go ahead and plug that into these formulas for restaurant one and we see that the new posterior for restaurant one is going to be mean five and standard deviation one and the other posterior for restaurant two is unchanged because we haven't visited yet so we're still stuck with the prior so let's draw a picture of what they look like at this moment so we have this picture here this blue very very large blue line is r2 which is the same one that we were looking at here and this much narrower distribution is r1 and then we just repeat the process now we sample from the posteriors again and let's think about why have we not totally messed this up why do we still have a chance for restaurant 2 to become the winner at the end of this process because restaurant 2 still has a massive standard deviation so all the restaurant 1 currently has a higher mean because restaurant 2 still has that massive standard deviation we encoded in the prior we still have a very solid chance of sampling from restaurant 2 next it's not like we're sure fire going to sample from restaurant one so let's say we do that let's say by random chance we sample from restaurant two and we get a satisfaction of six which again is well within the balance of what it could be it's the actual average and now what do the posteriors look like so we go through the same update steps and the posteriors now look very close to a normal five one and a normal sixth one and now we see we've self-corrected that issue with picking restaurant one by accident and now we have restaurant two actually ahead of restaurant one and now we're very very likely to actually pick restaurant two on the next step and that's just gonna continue to reinforce continue to reinforce because what happens as we keep picking restaurant two remember the variance is gonna be one over n so it's going to get tighter and tighter and tighter and tighter so that at the end of the day we have found that restaurant two was the correct restaurant to go to i think this is crazy i think it takes a little bit of time to understand but once you kind of grasp that thompson sampling is this really like cohesive technique that just deals with these distributions and self-corrects and by the way this is for two restaurants but you can have like hundreds to thousands of restaurants and we'll see that in the code when we have that video but you'll see this process kind of play out where the winning distribution kind of emerges its way to the top even if you make a few mistakes in the beginning and now let me just finish this video by talking about one of the drawbacks of thomson sampling so thompson sampling once it's kind of locked in on what the winning distribution is it's going to pretty much just pick that every single time going forward so you miss out on a lot of exploration in thompson sampling unless you kind of modify the algorithm you can do like epsilon greedy kind of thing where you say on 10 of the days i'm actually not going to go with the thompson estimate i'm just going to pick a random restaurant if you do pure thompson sampling like we have here then all the other distributions are going to get sampled a little bit until the winning distribution appears on top but after that their distributions are kind of just going to be stuck where they're at we'll see all that in the code but um hopefully this explained thompson sampling in a nutshell hopefully you thought it was interesting like and subscribe for more videos just like this and i'll see you next

Channel: ritvikmath

Views: 5,069

Keywords:

Id: Zgwfw3bzSmQ

Length: 13min 16sec (796 seconds)

Published: Wed Jul 07 2021