The KL Divergence : Data Science Basics

Key Takeaways

[Music] hey everyone welcome back today we're going to be talking about the KL Divergence which is a very very popularly used metric in data science in order to measure the difference between two distributions now I want to approach this video in a slightly different way and my ulterior motive for this video is actually developing a better way to learn math and statistics and data science and we'll be using the KL Divergence as our example in this case now just a brief intro I think the reason math and stats are difficult for many people is because there's this notion that here's a new formula you want to learn this formula is just in some sense correct or was just given to us and is the obvious right thing to do and now the onus is on us to understand what this formula is trying to say so many students will start from the formula for example we'll start from the definition of the CH Divergence in mathematical form and try to look at it and try our best to understand what's going on but I think that's destructive for a lot of different reasons firstly if you're looking at a formula and it looks rather complicated as the K Divergence formula kind of does if we didn't do it in this better way then you can get kind of disheartened and feel like there's no way I can understand this there's no way I can figure out what's going on and the other is that it's not really the way that math was developed in the real world I think one of the misconceptions is math was thought of as this gift from God but it's not it's a constru constuction of man every formula that you see is constructed by someone in the past was engineered for a certain purpose and so in this video we'll be treating math as more of a construction process of going from here's a problem that I want solved can you develop me a metric that's going to solve that problem instead of working the other way around which is I think the way it gets taught a lot so enough about that let's get into understanding the K Divergence so just like we said starting from the problem let's assume that you are a kindergarten teacher and so year after year you'll get new batches of kindergarten students and every year you ask them a question about what's your favorite fruit now let's say they have three choices they can either choose Apple they can choose banana what's a fruit that starts with C let's say Clementine so they can choose apple banana or Clementine and you pull all of your students in your kindergarten class year after year and you get the percentages and you draw them on these plots so let's just focus on two back-to-back years so here's year 1 and here's year two let's say in year 1 50% of the students liked apples 40% bananas and 10% Clementine and let's say in year two the distribution was still 50% liking apples but these two swapped so now 10% of the year 2 students liked bananas and 40% liked Clementine and the question is here's one distribution and here's the distribution for the students in the year after can you quantify give me a single number that's going to tell me how much changed from year 1 to year 2 how much different is the year 2 distribution relative to the year one distribution and now just phrasing it in that way before we even start getting into any math we already understand another constraint that whatever metric we come up with which eventually we'll call the K Divergence we understand another constraint it needs to satisfy remember what I said remember we said that we want to know how much the year 2 distribution is different relative to the year 1 distribution and therefore whatever metric we come up to needs to be asymmetric and why should that be the case well asymmetry means that if I switch the two things I'm talking about the answer should change there's no reason it should be the exact same and indeed if you ask the reverse question if you say how much different is the year 1 distribution relative to the year 2 distribution then you would expect those two numbers to be different because the basis or the reference point is different in each case currently we're talking about the reference point being year one but if you talked about the reference point being year two then that change could be different and if that still seems fuzzy or asymmetry seems like an undesirable property to you because we talk about symmetry so much in mathematics asymmetry can be just as important for a very simple example just think about percent changes when you measure the percent change let's say between salaries in Los Angeles versus Chicago well one of those has to be your basis point if you live in Los Angeles you might care about relative to where I live how much higher would the salary be if I moved to Chicago but if you lived in Chicago you would care about just the opposite question relative to where I live which is Chicago how much higher or lower would the salary be if I move to Los Angeles and therefore asymmetry can be just as desirable a property as symmetry in mathematics and today for the K Divergence we definitely care about the final metric being asymmetric which is something that we can check so now let's get into this construction process if you were asked to do this from scratch if you asked to come up with this metric how would we start here's one possible way to start and again key word in this video is the word possible we'll go through some possibilities of what we could do but if you came up with a different way to do it that could just be equally valid you'll get a different metric in the end but that doesn't mean it's wrong again this is a engineering constructive process so a possible first place to start would be all right I see an a a b and a c in each of these distributions so let me measure the quotient or ratio between the probabilities of a between the two years B between the two years and C between the two years so I've chosen this notation p and Q so let me label those so that we don't get too confused when you're talking about K Divergence Q is always what's called your reference distribution or the basis the distribution against which you want to compare change and for us that's year one so we're going to go ahead plot our marker and say that year 1 this is the Q distribution which would make year two the P distribution so when we talk about PA we're talking about what is the proportion of students in year 2 that liked apple and that's of course 50% QA would be the proportion of students in year one that liked Apple which is also 50% so when you divide them we get one so this one is telling us that from year to year there was no change in the proportion of students that liked Apple we can do the same thing for bananas and Clementine and we find that for bananas p over Q is 1 over4 which means that there's only a quarter of the students or fraction of the students who liked bananas in year 2 versus year 1 and C is equal to four which means four times as many students like clementines in year 2 as in year one so that's great that's a good first step and now in the interest of just keeping things simple in mathematics what if we just took the average of these three numbers because each of these represents in some sense a change between some element of each of our distributions so why don't we just take the average change so take one coming from a the 1/4 coming from the B the four coming from the C add them all up divide by three because there's three of them and here you go 1.75 that is my metric for now for telling you how different the two distributions are now this is absolutely the right thing to do in the sense that we should always go with the more simple explanation if there is one but let's look at an issue that we've caused by doing this very simple example here so the issue that we've caused is that averages so when you take the arithmetic mean of a set of numbers we know one thing about them is that they're skewed by large numbers for example if I ask you to take the average of 1 2 3 and 1 million that 1 million even though it's just one out of the four numbers is going to very significantly skew the average towards it and so going back to our last page and seeing what similar things going on here we see that this 1/4 and this four are in some sense opposite and equal forces we see that from here we went from 40 to 10 which is a division by four and from here we want 10 to 40 which is a multiplication by four so when we do our formula for K Divergence they should get treated in an opposite and equal way but when we take the average it's not this four being so much higher than the 1/4 has a lot more sway has a lot more pull which is going to drive this final metric up and therefore taking a simple average is probably the not right way to go instead let's see if we can do some simple transformation find some function f which we can apply to this four which we can apply to this 1/4 and which we can apply to the as well and that function needs to satisfy exactly that equal but opposite Force property where if we feed four into this function we should get whatever number y if we feed 1/4 into this function we should get the opposite number negative y so the key thing to notice here is that when I feed in four or 1/4 and those in this context represent something was four times bigger or something was 1/4 as much this should map to some number Y and the 1/4 should map to its negative counterpart which is negative y because their magnitudes are equal it's just their different directions in terms of this distributional difference problem now the question is all right that makes sense for what the function should be able to do but how do we figure out what the function itself should be here we're going to do a very simple exercise we're simply just going to map values of the function and we'll see what kind of function we know about could fit that bill so we said that if we feed four into this fun function so we four into the function we should get y so I put y up here so here's one point on the function if we feed 1/4 into the function so 1/4 would be right there then we should get- Y and two points is not a great way to go let's try to get a little bit more data here so it's this four and 1/4 are not special you can do this with any pair of reciprocal numbers so if I put two into this function I should get some number Z let's say let's just say Z would be down here if I feed 1/2 which is the reciprocal of two into this I should get Negative Z let's say that's right here and now we start getting an idea of what form this should be it's not a linear function it's got some curvature to it and if I feed let's do one more Point that's going to probably help us figure this out overall if I feed one into this function then I should get some number let's say w if I feed the reciprocal of one which is one then I should also get W so one kind of seems like a place where the thing I map to should be the negative of itself but the only number that fits that is zero therefore one should map to zero so now let's kind of Trace out what this guy looks like it seems like it's doing a little bit of this then a little bit of that this and that I'm sure most of you would agree fits the general shape of a log curve and therefore we can use log of x as our function f so instead of just doing p over Q instead of just doing p over Q as we're doing back here so we were just doing P's over Q's let's do a log transformation so log of p over Q instead in order to eliminate that averages are skewed by large numbers problem so so far where are we at with our metric we are looking at summing up over all of the x's in the distribution so that would be summing over apples and bananas and clementines the log of p over Q again Q is our reference distribution and P is the other distribution again to which we want to compute change from the reference and since we're still taking an average we divide all of that by n n being the number of items in this case three the apples bananas and Clementine so what if this was our metric is there any issue with that now one possible issue that someone could have with this metric is that actually we want this distributional difference metric to prioritize popular X values in our current distribution so what I mean by that let me go back to this page here so we're we're in year two at this point year 1 was last year so in year two 50% of our students care about apples only 10% care about bananas and 40% care about Clementine so if I were to ask you which fruits should you weigh more heavily when you consider this change from year 1 to year 2 one way to answer that is looking at well right now a whole 50% of my students like apples and therefore I want you to waight Apples more significantly when you're looking at the change of apples from year 1 to year 2 40% which is also rather High care about Clementine and so when you compute that change from year 1 to year two for Clementine's I want you to weigh Clementine's pretty heavily too now only 10% of my current students care about bananas so when you look at the change from year 1 to year 2 for bananas you don't need to worry too much about that change because it's not going to affect my current students or my current population too much anyway therefore you're okay to downweight that change if you're able to upweight the changes on apples and Clementine's respectively so if we look at the metric we have have right now the weight we're putting on each of these changes is 1/ n so I put the n on the outside of the sum but you can just as easily think of the 1/ N being inside and not out there in which case it's much easier to see it as a weight put on each of these changes so instead of a one over n let's make the weight we put on the change be actually the probability or the proportion of students that care about that fruit in the current distribution which is of course P of X so the only change I've made going from this possible formulation of the CH Divergence to this possible formulation of the CH Divergence is that I replace the equal waiting on each of these items we care about with a probabilistic waiting where we care about it as much as its frequency in the current distribution things that are very popular get a lot of priority things that are not popular right now even if they were popular in the past distribution or the reference distribution do not contribute as much to this K Divergence and this form where we SU for all of the things we care about apples bananas clementines whatever other fruits there would be we put a weight which is equal to the popularity in the current distribution and then we have this log p over Q term which tells you a measure of how much change actually happened from the reference distribution to the current distribution that is the accepted definition of the KL Divergence and you'll see the notation of KL Divergence often look like this KL here you have your current distribution P you put these two big vertical bars and then you have your reference distribution q and the way you think about this is that relative to Q so that's the thing on the right hand side of these double bars relative to Q how much is P different how much has P changed and now the big other thing remember we wanted our metric to be asymmetric did we satisfy that if we switched p and Q here then we would switch all the p's and q's in this formula down here it is indeed asymmetric because this P would become a q so all these probabilities would be different and this p over Q would become a q over p and so these numbers would be different as well and so I haven't formally proven it to you but you can see intuitively here that the K Divergence is as we wanted it is a asymmetric uh metric for calculating the difference between distributions so it matters whether P or Q is your reference distribution here and that's it folks uh the only other things I would say here is that this is the discrete form of the K Divergence if you have discrete categories as we did here um of course you could be working with continuous distributions same exact deal you know the drill the sum gets switched out for an integral you have a DX on the outside here but otherwise nothing changes and so firstly I do hope you understand the K Divergence here but more importantly I hope it wasn't as scary as if we started from this formula here on the very first page the very first thing that I showed you and then we tried our best to kind of understand why it look the way it does I truly appreciate mathematics more when it is a constructive process and so enough ranting there the last thing I want to talk about is applications to data science so the most popular application of the K Divergence to data science is trying to find an approximation to some observed distribution you find in the wild so let's say that we have some observed distribution and so it looks like this as observed data can be it's rather noisy so this purple distribution is the distribution of observed or sampled points we saw from the world we would like to model this observed distribution using some well-known distribution like the normal distribution or the gamma distribution or the Calia distribution whatever and so we might have a few candidates in this case we just have two so we have this blue distribution and we have this red distribution and Visually you don't even need the K Divergence to tell you the answer here visually you know that the red distribution is going to be a better fit to this observed data this observed purple distribution but the K Divergence can make that process robust and reproducible and quantifiable and so in the context of everything we've learned today our reference distributions would actually be these candidates so either this would be q1 a possible reference distribution or Q2 a possible reference distribution and the reason we call these our reference distributions is since we're saying assume this blue distribution is true how different is this observed distribution here so this would be p in our terminology here how different is that P from the Q and you're going to find they're they're pretty different they're not really that good of a fit now if you did the same exercise you calculated the K Divergence using this Q2 assume this red Q2 distribution is the true distribution from which my individuals in this purple distribution were sampled assuming that's true how different is this observed distribution from this reference uh red Q2 distribution and you're going to find it's a much better fit the K Divergence will be much lower in that case and so that I think by and far is the biggest application of the K Divergence in data science so really hoping you learned about about the KO Divergence in this video but as we were saying before more importantly hope you kind of learned what it feels like to invent a piece of mathematics for yourself so if you like this video please please like And subscribe any comments are always welcome below thanks for watching and I'll see you next time