The Maths Behind XGBoost | Machine Learning | CampusX — Transcript
Full transcript
- 0:00Hi guys, my name is Nitesh and welcome
- 0:02to my YouTube channel. In this video,
- 0:05we are going to cover the in-depth
- 0:07mathematics of XGBoost. So if you have
- 0:09been following all the videos, I have
- 0:11already posted three videos on XGBoost.
- 0:14In the first video, I covered the
- 0:15introduction. In the second video, I
- 0:17showed how XGBoost is applied to
- 0:19regression. I demonstrated that. And in
- 0:22the third video, we covered how XGBoost
- 0:24is applied to classification problems.
- 0:27But in all three videos, I hadn't
- 0:29discussed any math at all. So that is
- 0:31exactly what we will cover in this
- 0:33video. In this video, we will go very
- 0:36deep and understand the entire
- 0:37mathematical formulation from scratch.
- 0:40We will try to understand where all the
- 0:43formulas came from. Let me tell you why
- 0:45you should watch this video. XGBoost is
- 0:49undoubtedly the most powerful algorithm
- 0:51in the machine learning space today.
- 0:54Take any problem involving tabular data
- 0:56, and most likely, you will be using
- 0:58XGBoost there. So, if you are going to
- 1:01become a data scientist or let's say
- 1:04you are a data scientist, you should
- 1:06have a very clear picture of XGBoost's
- 1:09mathematics. This video will provide
- 1:12you with exactly that. In a very
- 1:14in-depth, detailed, step-by-step
- 1:17approach, we will refer to the research
- 1:21paper to cover all the mathematics. No
- 1:25doubt, the video is a bit long. But
- 1:27that is because I made a conscious
- 1:29decision not to skip anything and to
- 1:32show you everything by writing and
- 1:35deriving it. So this is just for the
- 1:38hardcore data science fans. So now, I
- 1:41won't bore you any further. Let's start
- 1:43the video. So you must have understood
- 1:46that in this video, we are going to
- 1:48cover the detailed mathematics of
- 1:49XGBoost. But before starting the video,
- 1:52I want to tell you exactly what we are
- 1:54going to study in the mathematics
- 1:55section. If you have followed all the
- 1:58previous XGBoost videos, you would know
- 2:00that we have already posted three
- 2:02videos on this channel. In the first
- 2:05video, we did a detailed introduction
- 2:09to the XGBoost algorithm. In video
- 2:13number two, we focused specifically on
- 2:16regression and how XGBoost solves a
- 2:18regression problem. Then in video
- 2:22number three, we discussed how XGBoost
- 2:25works on classification problems. So,
- 2:30if you have watched both these videos,
- 2:33you might remember that the common
- 2:36thing in both regression and
- 2:38classification problems was that we
- 2:41used to build a decision tree that was
- 2:44slightly different from regular
- 2:46decision trees. Right? In XGBoost, your
- 2:50decision tree is different from a
- 2:52normal decision tree. In two aspects,
- 2:55the first aspect is that in a normal
- 2:59decision tree, when you construct a
- 3:02node, you calculate quantities like
- 3:06entropy and Gini index. But in XGBoost
- 3:10trees, instead of using these two, you
- 3:13calculate a completely different
- 3:15quantity, which we call the similarity
- 3:18score. Right? And if you focus here,
- 3:23you will find the formula to calculate
- 3:26the similarity score for regression and
- 3:29to calculate the similarity score for
- 3:32classification. Right? So, I introduced
- 3:36both these formulas in those two videos
- 3:39. I did not give you any mathematical
- 3:42background, and I told you that just
- 3:43trust me, this is the formula we have
- 3:45to use. But in today's video, we will
- 3:48go into great detail to understand
- 3:50where these two formulas came from. The
- 3:54second point of difference between an
- 3:56XGBoost tree and a normal decision tree
- 3:59is that the method to calculate the
- 4:02decision tree output is different; the
- 4:04normal one and the XGBoost one have
- 4:07different formulas for calculating the
- 4:10leaf node output. And again, if you
- 4:13focus here, this is the formula to
- 4:16calculate the output value for any leaf
- 4:18node in the case of regression. And
- 4:22this is the formula to calculate the
- 4:24output of any leaf node in the case of
- 4:26classification. And again, I introduced
- 4:29both these formulas in those two videos
- 4:31. And once again, I did not tell you
- 4:33where they came from. So, in today's
- 4:36video, we will look behind these as
- 4:38well and try to understand how these
- 4:40two formulas came into existence. Right
- 4:43? So, in short, in today's video, we
- 4:47are going to do a deep dive into the
- 4:50mathematics of XGBoost, and our goal
- 4:53will be to understand where these four
- 4:57formulas came from. I will give you the
- 5:01answer to every "why." And trust me, if
- 5:03you understand this video well, you
- 5:06will have such foundational knowledge
- 5:08of XGBoost that you will be able to
- 5:11apply XGBoost to any problem very
- 5:13effectively in the future. Right? Also,
- 5:16before starting the video, I want to
- 5:18give one more disclaimer. So when I was
- 5:22researching for this video, I noticed
- 5:24that there isn't much content available
- 5:26on the internet. In a few places,
- 5:29people have explained how the
- 5:31mathematics of XGBoost works. But I
- 5:33noticed some mistakes in them. So that
- 5:37is why for this video, I have
- 5:39specifically used the research paper of
- 5:41XGBoost. So whatever mathematics I
- 5:45explain to you in this entire video is
- 5:47basically in these two pages. Page
- 5:50number two and page number three. Okay?
- 5:53So things will be factually correct and
- 5:56the good part is that you will be able
- 5:58to go back and read this XGBoost paper
- 6:01too. Okay? So with that, I guess I gave
- 6:03you a clear plan of attack. Now let's
- 6:05start the video. Also, one more thing,
- 6:09if you are feeling a bit scared that
- 6:11this video about mathematics will be
- 6:13very difficult, then I have a
- 6:15suggestion for you to study a few
- 6:18things before watching this video.
- 6:21After that, this video will seem easy
- 6:22to you. What do you need to study?
- 6:26First of all, the two videos I uploaded
- 6:29before this on XGBoost, the regression
- 6:31video and the classification video. You
- 6:36must watch these videos, only then will
- 6:38you understand things. Apart from this,
- 6:41you should have some idea about
- 6:43gradient boosting. Because XGBoost is
- 6:47just optimizations over gradient
- 6:50boosting. So if you know gradient
- 6:52boosting, it will become much easier to
- 6:54understand. And obviously, you should
- 6:57know the basic concepts of decision
- 7:00trees. How a tree is built, how the
- 7:02output value is calculated? You should
- 7:05know all of this. If your foundation is
- 7:07clear to this extent, trust me, you
- 7:09won't have much trouble understanding
- 7:11this video. So guys, at the very
- 7:15beginning, I want to give you a short
- 7:17quick revision of how boosting models
- 7:20like XGBoost or gradient boosting work.
- 7:24Although I have told you this multiple
- 7:26times. But let's have a quick revision
- 7:28once. So as you know that boosting
- 7:32models like gradient boosting or
- 7:35XGBoost or for that matter, other
- 7:37boosting algorithms you will study
- 7:40later, they are all additive models.
- 7:44Additive models mean that in a
- 7:46stage-wise fashion, one after the other
- 7:52you keep adding models to your existing
- 7:55ensemble. So in stage one, you have
- 7:58this model M1. Okay? It made some
- 8:02mistakes on your data. You train this
- 8:06model M2 on those mistakes and then you
- 8:09combine these two to make a prediction.
- 8:15Then the combination of these two will
- 8:17also make some mistakes. So, you
- 8:19propagate that error towards the third
- 8:22model. The third model trains, and then
- 8:25you combine these into an ensemble to
- 8:27make a prediction, and in this way, you
- 8:30can add as many models as you want. I
- 8:34guess you are aware of this. All right?
- 8:36So, here, to explain this point a bit
- 8:39better, I am taking an example. Like,
- 8:43suppose you have this data of students
- 8:45where you have CGPA and IQ as input,
- 8:47and this is your output, which is the
- 8:49value of their package. So, what did we
- 8:53do? We applied XGBoost on this. And we
- 8:59already decided that we will build two
- 9:02models. The first and the second. Now,
- 9:06generally, the first model is a base
- 9:09model. And in the case of regression,
- 9:14this could be the mean of the output
- 9:18column. So, we basically took the mean
- 9:22of all three. This is your first model.
- 9:24This, this is your m1. All right? Now,
- 9:27obviously, M1 will make some mistakes.
- 9:29You are saying for this student too,
- 9:31the package should be 14.5. For this
- 9:33one too, you are saying it should be
- 9:3514.5. And for this one too, you are
- 9:37saying it must be 14.5. So, obviously,
- 9:39there are errors, there are mistakes.
- 9:41So, now what will you do? You will take
- 9:45your input and this difference, these
- 9:49mistakes, this error, you will take
- 9:53them and use this data to train M2 in
- 9:57stage two, which is nothing but a
- 10:01decision tree. All right? Now, for a
- 10:06moment, assume that this is the
- 10:07decision tree you built. All right? If
- 10:09CGPA is less than six, then this
- 10:11happens; if IQ is less than 100, then
- 10:13this happens. All right? And you have
- 10:17trained this. All right? Now the
- 10:21question is, if tomorrow a new student
- 10:25comes, suppose their CGPA is nine and
- 10:29their IQ is 100 or 102, then how will
- 10:33we calculate their output? How will we
- 10:37calculate y-hat to find out what their
- 10:39package will be? It is very simple. We
- 10:42will send this input data into this
- 10:45combination of m1 + m2. So, what output
- 10:49will m1 give? 14.5 plus what output
- 10:53will m2 give? Since it is a decision
- 10:55tree. You will ask it a question. Is
- 10:58CGPA less than six? No, it is nine. All
- 11:04right? So, if you consider this as yes
- 11:09and this as no, then you will directly
- 11:13add 2.1 and say that 16.6 should be the
- 11:18package. So, this is how you find out
- 11:23predictions in the case of boosting.
- 11:28All right? So, if you talk in a
- 11:31strictly mathematical sense, all these
- 11:34models are nothing but mathematical
- 11:37functions; if you think about it, I can
- 11:40actually write this one as f1x or f1xi,
- 11:43we will calculate it for each data
- 11:46point, and we can call this f2xi. Even
- 11:50though this is a decision tree, it is
- 11:52still a function; you give it some
- 11:53input. It gives you some output. Now,
- 11:56to calculate that output, it is using
- 11:58if-else statements. But that doesn't
- 11:59matter, it is still a function. So, if
- 12:02you have a lot of such functions, then
- 12:04this last one will become fn xi. So, in
- 12:09short, what I mean to say is that the
- 12:11output calculated in boosting can be
- 12:13written in a compact mathematical form.
- 12:17If you have n models, like there are
- 12:22two here. Suppose we had n models, then
- 12:25we would write this entire expression
- 12:26like this. f1 xi + f2 xi + dot dot dot
- 12:33+ fn xi, or we could write it as sum
- 12:40from i = 1 to n fi xi; this is the
- 12:49formula for the output of a boosting
- 12:53algorithm like XGBoost. I hope you have
- 13:01understood. Now guys, we have
- 13:04understood that you can explain the
- 13:07output of a boosting model in terms of
- 13:11the sum of functions. But one thing
- 13:15that isn't clear is how the output
- 13:18values of these leaf nodes of this
- 13:21decision tree, these three leaf nodes,
- 13:24were calculated. Now, if you have
- 13:32watched the previous two videos, I told
- 13:35you there that if you talk about
- 13:37regression, since this is a regression
- 13:39problem. So, if you talk about
- 13:43regression, then the formula to
- 13:45calculate the output of the decision
- 13:48tree in the case of regression is Sum
- 13:55of residuals divided by number of
- 14:02residuals plus lambda. Okay? For
- 14:06example, suppose you have to calculate
- 14:08the output of this particular leaf node
- 14:10. Then first of all, you will find out
- 14:12which of these data points will fall
- 14:13into this particular leaf node. Okay?
- 14:24You can see that only this data point
- 14:25will fall here. Right? Because less
- 14:32than CGPA 5 is only in this row. So
- 14:33here, what you will do is you will
- 14:35write down the residual or error
- 14:36corresponding to this point, divided by
- 14:37the number of residuals, which is one.
- 14:40Plus whatever your lambda value is, you
- 14:45will put it in, and that will be your
- 14:50output value. Similarly, what will you
- 14:55do for this one? Similarly, you will do
- 14:58the same for this one as well. For this
- 15:01node as well, you will find out which
- 15:04points fall into this node. Like right
- 15:09now, I can see this particular point.
- 15:12So for this too, you will apply the
- 15:14same formula. And similarly for this
- 15:16one also. But in this video, we need to
- 15:19understand where this formula came from
- 15:22. What is the origin story of this
- 15:25formula? That is what we will try to
- 15:29understand. Moving forward, given an
- 15:32XGBoost tree, how do you find the leaf
- 15:36weights? By the way, the output of a
- 15:41leaf node is also called a leaf weight.
- 15:46So we are trying to figure out how this
- 15:49formula came to be. Okay? Now, how is
- 15:53this formula derived? I will first
- 15:56explain the thought process behind it.
- 15:58Okay? Based on the discussion so far,
- 16:03you have understood that in our overall
- 16:06combined model, where we have two
- 16:08models, m1 and m2, their combined
- 16:11output, which we will call yi-hat, will
- 16:14be m 1's output plus m 2's output.
- 16:17Right? And I told you a while ago that
- 16:20we can mathematically write this in
- 16:22terms of functions. So let's say we are
- 16:25calling m1 f1 (xi) + m2, which is this
- 16:28decision tree. We are calling this f2.
- 16:32(xi). Okay? Now we know that the output
- 16:36of f1 (xi) is always 14.5. We need to
- 16:40find the output of f2 (xi). Okay? The
- 16:44interesting thing is that we have to
- 16:47calculate three output values. Okay?
- 16:49You have to remember that f2 (xi)
- 16:52doesn't have a single output value.
- 16:55There will be three different output
- 16:56values. One for this leaf node, one for
- 16:59this leaf node, and one for this leaf
- 17:01node. So we need to calculate all three
- 17:03. So basically, if this decision tree
- 17:06had five leaf nodes, we would have to
- 17:08find five values for this f2 (xi). Okay
- 17:12? Anyway. Now we have the formula for
- 17:18yi-hat. Okay? We need to find out what
- 17:30the value of f2 (xi) will be. Okay? So
- 17:34let's try to think once about what the
- 17:38value should be. If you have studied
- 17:42machine learning enough and read about
- 17:45the algorithms, you should always know
- 17:49that the only job of your algorithm's
- 17:52prediction is to get closer to reality.
- 17:56And what is reality? yi, which is the
- 17:59actual package of the kids in your data
- 18:01. You will always want to do one thing.
- 18:05You will want to reduce the gap between
- 18:09yi and yi-hat. Right? So basically, we
- 18:15need a value in f2 xi such that for
- 18:20every data point, the difference
- 18:24between these two quantities is reduced
- 18:30. Okay? Now, that is why it is very
- 18:36important that you first write down the
- 18:39relationship between yi and yi hat. And
- 18:46I guess even a beginner knows what we
- 18:49call the relationship between yi and yi
- 18:53hat? Loss function. A loss function is
- 19:00a mathematical function that
- 19:03establishes a relationship between yi
- 19:07and yi hat, and our goal in machine
- 19:11learning is to minimize this loss
- 19:14function. Like in the case of
- 19:19regression, we studied a very famous
- 19:21loss function. Mean Squared Error,
- 19:24whose formula is this. I hope you
- 19:41remember this from linear regression.
- 19:44So now, if we need to find this value,
- 19:49then we need to find a value that will
- 19:56minimize the loss function. I think
- 19:58you've understood this much. Now, the
- 20:01only question that arises is, what is
- 20:04the loss function in the case of
- 20:07XGBoost? What is the loss function? If
- 20:10we get the loss function, then in the
- 20:14process of minimizing that loss
- 20:17function, I will find this f2 xi. Okay?
- 20:21So first, I will show you the loss
- 20:24function used in Gradient Boosting, and
- 20:29then after that, I will show you the
- 20:32XGBoost loss function. So Gradient
- 20:36Boosting is one algorithm which is very
- 20:39, very flexible. I told you while
- 20:45teaching Gradient Boosting that
- 20:47Gradient Boosting is so flexible that
- 20:50it accepts any type of loss function,
- 20:52provided it is differentiable. Meaning,
- 20:56you should be able to differentiate
- 20:57that loss function. Because
- 20:58differentiating is necessary since you
- 21:00will perform optimization. So for that,
- 21:03you need a differentiable loss function
- 21:04. One such differentiable loss function
- 21:07is Mean Squared Error, which I just
- 21:09showed you. So if you talk about
- 21:11Gradient Boosting, then there isn't
- 21:13actually any specific loss function in
- 21:15Gradient Boosting. In Gradient Boosting
- 21:17, the loss function is often
- 21:19represented in this way. That's it. If
- 21:23you see this written, then this is the
- 21:25Gradient Boosting loss function. Now,
- 21:27you can put any mathematical function
- 21:29into this. You can also put Mean
- 21:32Squared Error. You can also put Log
- 21:34Loss. You can also put any other loss
- 21:36function. It just needs to be
- 21:38differentiable. But the XGBoost loss
- 21:42function looks a bit different,
- 21:44slightly different. And as I told you
- 21:50in the first video of XGBoost, the loss
- 21:54function of XGBoost has a
- 21:56regularization parameter by default.
- 22:05Right? So now, I will show you what the
- 22:09XGBoost loss function looks like. Now,
- 22:12if you go to the original XGBoost paper
- 22:16, you will see this. And this is the
- 22:21loss function of XGBoost. Right? So
- 22:24first, I will write it down. Then I
- 22:27will explain to you what this loss
- 22:28function indicates. So in our case,
- 22:31since there are two models m1 + m2,
- 22:34here m1 is a base model and m2 is a
- 22:38decision tree. So our loss function
- 22:45will be σ i = 1 to n for all data
- 22:51points l yi yi hat plus this omega term
- 22:58on f2 xi Right, now it is explained
- 23:07here what this omega of f is. Right? By
- 23:11the way, this term is only applicable
- 23:15to your last decision tree. So, it is
- 23:19actually made of two terms. Right? So
- 23:22it is actually gamma times T + 1/2
- 23:29lambda times w². Right? Let me explain
- 23:36all these things to you once. So here,
- 23:39this T is the number of leaf nodes in
- 23:46your decision tree. Like in our case,
- 23:49one, two, three, these are our number
- 23:53of leaf nodes. So here, the value of t
- 23:56will be three. And what is this W? This
- 24:00W is the weight or output of these
- 24:03leaves. Like this is W1. This is W2.
- 24:07This is W3. Right? And this gamma is a
- 24:12regularization parameter, and this
- 24:16lambda is also a regularization
- 24:19parameter. Right? Basically, you want
- 24:23to penalize your tree for having too
- 24:27many leaf nodes and having very high
- 24:30output values. That's the whole idea
- 24:33behind this entire loss function. Right
- 24:37? You can compare it side-by-side with
- 24:40gradient boosting. In gradient boosting
- 24:42, this loss function would just be this
- 24:44. That's it. This term would not be
- 24:53there. So, the biggest difference you
- 24:57can see so far in XGBoost is this. That
- 25:01this loss function is different. It
- 25:04comes with a built-in regularization
- 25:06parameter. Right? So, now if I tell you
- 25:12what W1, W2, and W3 should be? Then in
- 25:20very simple words, we need values for
- 25:23W1, W2, and W3 that will minimize this
- 25:27loss function. And that's the whole
- 25:32idea. And now we have entered the
- 25:34domain of optimization, which is a
- 25:37somewhat familiar territory. You have
- 25:39studied this in gradient descent and
- 25:41also in linear regression. And in many
- 25:44other algorithms, you have explored how
- 25:46to find values for specific parameters
- 25:49by minimizing the loss function. Okay?
- 25:52So, moving forward, we are going to
- 25:55apply all this same mathematics. Before
- 25:57moving ahead, I would like to clarify
- 26:00one thing. Until now, what I was doing
- 26:04was calling this thing a loss function.
- 26:09Okay? I was calling this complex term a
- 26:11loss function. But actually, you don't
- 26:14call it a loss function. You actually
- 26:17call it an objective function. This is
- 26:22called an objective function. Because
- 26:26this is a sum of two things. First,
- 26:29your loss function, And second, your
- 26:35regularization term. Okay? So, going
- 26:40forward, we will call it an objective
- 26:42function. Wherever you read about it,
- 26:43it will be called an objective function
- 26:45. I might accidentally call it a loss
- 26:47function again. But you understand the
- 26:49sentiment. Okay? Now, I want you to get
- 26:53comfortable with this objective
- 26:56function. It is very, very important
- 26:59that you get a bit comfortable with
- 27:01what is written on the screen right now
- 27:03. So, what am I going to do? I will
- 27:06show you this objective function
- 27:08through two or three different examples
- 27:10. Okay? So, let's assume we are
- 27:14building three or four different models
- 27:18. Suppose we have a dataset. Any
- 27:23dataset, and we performed boosting on
- 27:26it using XGBoost. Now you know what you
- 27:30do in boosting. You keep adding models
- 27:33one after another in a stage-wise
- 27:34fashion. One model in the first stage,
- 27:37two models in the second stage, three
- 27:40models in the third, and so on. Now,
- 27:43assume that when you first applied
- 27:46XGBoost on it, you decided that, no, I
- 27:50will use only one model. So there will
- 27:54be only one model. So, I want to show
- 27:58you what this objective function would
- 28:00look like if there were only a single
- 28:02model. By the way, you know that the
- 28:05first model in XGBoost is not a
- 28:07decision tree. It is simply the mean.
- 28:10This is just a constant. So let's
- 28:13assume we have a single model. This is
- 28:16m1; mathematically, we can call it f1
- 28:20xi. So, for this, our objective
- 28:24function becomes sigma i = 1 to n for
- 28:28all the data points. Loss function is
- 28:33yi. yi hat, that's it; this term does
- 28:39not come because what is this term?
- 28:42This term is this thing. Right? What is
- 28:48T in this? Number of leaf nodes. And
- 28:51what is W? Leaf weights. Now think
- 28:54about it yourself. If you have just one
- 28:56model and it is only a mean model. This
- 28:59is not even a decision tree, so you
- 29:02wouldn't write this for that. I hope
- 29:05you are understanding the point. Now
- 29:07let's take a second case. The second
- 29:10case is that this time we are taking
- 29:13two models. We are taking two models.
- 29:17This is m1, which is again mean, and we
- 29:21are taking m2, which is a decision tree
- 29:25. Okay? And mathematically we are
- 29:28writing this as f1. xi and we are
- 29:32representing this as f2 xi. How will
- 29:36our objective function look in this
- 29:39case? Our objective function will look
- 29:41like this. yi, by the way, we can write
- 29:49yi hat as this. Right? So what am I
- 29:58doing? Here, rather than writing yi hat
- 30:03, I am writing f1 xi + f2 xi, okay? +
- 30:09omega of f2 xi. Why only f2xi? Because
- 30:16only f2xi is a decision tree. Okay,
- 30:21anyway, this is stage two. This is
- 30:25stage two, this was stage one. So since
- 30:31this new model has been added and since
- 30:34this is a decision tree, your
- 30:36regularization term will only apply to
- 30:39F2. It will not apply to F1. Okay?
- 30:43Let's take one more iteration. Let's
- 30:46add one more model. So we are moving on
- 30:49to stage three. In stage three, we have
- 30:52three models. This is the first one.
- 30:55This is the second one. This is the
- 30:57third one. So this is model one. This
- 31:00is model two. This is model three. This
- 31:03is again just a mean. This is a
- 31:06decision tree. This is also a decision
- 31:10tree. Okay? Mathematically, we are
- 31:14calling it f1xi, f2xi, f3xi, and now I
- 31:21would like you to imagine what the
- 31:24objective function will be. The
- 31:28objective function will be this. yi f1
- 31:38xi + f2 xi + f3 xi + f3 xi, why did I
- 31:52add only f3xi? Because the
- 31:56regularization up to here has already
- 32:01been handled in this step. Okay? Now,
- 32:05since this new decision tree has been
- 32:07added. That is why we are applying
- 32:11regularization on it. Okay? I hope
- 32:14things are clear up to here. One last
- 32:19example, we are at stage T. We don't
- 32:26know how many iterations have passed.
- 32:27How many models we have added. We don't
- 32:29know. We just know that now we have T
- 32:31models. T could be 100, or it could be
- 32:341000. We don't know anything. So now we
- 32:37have T models. We have T models. This
- 32:45is M1, this is M2, this is MT. This is
- 32:50mean, this is decision tree. In between
- 32:54are all decision trees, and this is
- 32:56also a decision tree. Let's call this
- 33:00one f1 xi, f2 xi, ft xi, and now I
- 33:03would like you to think, what would be
- 33:08the objective function? So, the
- 33:12objective function will be from i = 1
- 33:14to n. By the way, we can do one more
- 33:18thing. We can introduce a notation.
- 33:21Here, we can write one to represent
- 33:23this is the objective function of stage
- 33:24one. Here, we can write the objective
- 33:27function of stage two. Here, we can
- 33:30write the objective function of stage
- 33:32three. And similarly, we can write the
- 33:34objective function of stage t. So here
- 33:38we will have yi, f1 (xi) + f2 (xi) +
- 33:50dot dot dot + ft (xi). The very last
- 33:57plus, you always focus on your last
- 34:00decision tree, so here we will have (ft
- 34:03) xi. This will be the loss function,
- 34:07or I am sorry, this will be the
- 34:09objective function at stage t. Right.
- 34:13Now I am going to do one thing; I am
- 34:17going to simplify this entire term a
- 34:21bit. How? Pay attention, so I would
- 34:24rewrite it as yi, yi hat till stage t-1
- 34:38+ ft (xi) + ft. Basically, what I did
- 34:48is that I took (f1xi) + f2xi dot dot
- 34:55dot f (t-1) xi, replaced this whole
- 35:03thing with this term. yi hat till stage
- 35:08t-1 And we can write it like this,
- 35:13right? If we were at the t-1 stage, its
- 35:16yi hat would be this value, wouldn't it
- 35:19? So basically, I simplified it and I
- 35:23can say that, "At any stage t, the
- 35:32objective function of XGBoost can be
- 35:36written as sigma i = 1 to n (for all
- 35:40the data points): l (yi, yi hat till t-
- 35:511 stage +) ft (xi) + omega of ft (xi)"
- 35:56and I did all this hard work only
- 36:01because I want to show you that in this
- 36:06research paper, they have also written
- 36:12the t-th stage objective function
- 36:17exactly the way we have written it. You
- 36:22can see, now what do we need to do? We
- 36:26need to find such an output value for
- 36:28this fxi, which is the last decision
- 36:37tree, that will minimize this entire
- 36:44objective function. That is the goal.
- 36:46We have to find such a value of ftxi or
- 36:49this decision tree or the output of
- 36:53this leaf so that this entire objective
- 36:56function is minimized. This is our goal
- 36:59at this point of time. So, we have
- 37:02established our objective function and
- 37:04we have also established our goal. We
- 37:08basically need a value for ftxi that
- 37:11will minimize this entire objective
- 37:14function. So essentially, we have
- 37:19turned this whole problem into an
- 37:21optimization problem. And the good part
- 37:25is that we are already very comfortable
- 37:28with solving such optimization problems
- 37:31. Right? My question to you would be,
- 37:36have you ever solved an optimization
- 37:38problem like this? Where you need the
- 37:42values of parameters that minimize a
- 37:44loss function or an objective function.
- 37:47The answer should be yes. I mean, if
- 37:52you have studied linear regression,
- 37:54then if you remember, we used to have
- 37:57an objective function or a loss
- 37:58function there. Which was this. And,
- 38:10the actual loss function there, which I
- 38:13have written in a general form right
- 38:15now, was mean squared error, which you
- 38:18could also write as: (yi-yi hat)
- 38:20squared. Okay, now for a moment, assume
- 38:25that you are applying linear regression
- 38:28on this data. You have an input column
- 38:32called experience and you have to
- 38:34calculate salary, so this is your input
- 38:37and this is your output. Okay? So, What
- 38:43was yi here? What was yi hat? Like, yi
- 38:46is this. yi hat used to be m times
- 38:52experience of the ith candidate + b,
- 38:57right? So in a way, I was able to write
- 39:01this loss function like this too. yi-I
- 39:09can also call experience i as xi here.
- 39:12Because this is the input. Right? And
- 39:18if you remember, our task used to be
- 39:21that we needed such values of m and b
- 39:24for which this loss is minimum. This is
- 39:30like basic linear regression. Okay? And
- 39:34then what did we do? We used to plot a
- 39:37graph. Where one axis had m, one axis
- 39:41had b, and the vertical axis had our
- 39:44loss value. Okay? We used to try
- 39:47different values of m and b and plot
- 39:50the loss. Now, since this is a
- 39:54quadratic equation type. So, if you
- 39:57remember, this used to be our loss
- 39:59function. Here, this is the cost or
- 40:03loss. On this axis, you have m. On this
- 40:06axis, you have b. Okay? As soon as we
- 40:09find out that there is such a lovely
- 40:11parabolic shape. And now we have to
- 40:14find such values of M and B for which
- 40:17the loss is minimum. We know it will
- 40:21always be at the point where the loss
- 40:25with respect to both, the slope and the
- 40:30intercept, is zero. So what did we used
- 40:34to do? We used to differentiate our
- 40:37loss function. Once with respect to m,
- 40:41and by setting it to zero, we would
- 40:43find the value of m. And once by
- 40:45differentiating with b, we would find
- 40:48the value of b. And basically, we would
- 40:51get such a value of m and b. That would
- 40:54minimize this loss. And this is where
- 40:57we used techniques like gradient
- 40:59descent. Right? So in short, I just
- 41:03want to tell you that we have solved
- 41:05this kind of optimization problem
- 41:08before. But what if I tell you that
- 41:13this particular optimization problem is
- 41:19a tough nut to crack or is very
- 41:21difficult to solve. So would you agree?
- 41:26Let me give you my argument as to why I
- 41:30think optimizing this is...In this way,
- 41:34the method I just explained, in the
- 41:37linear regression case, our 'l' is this
- 41:41. In linear regression, m and b were
- 41:45our parameters, which are these here.
- 41:48Right? But the job is the same. But why
- 41:52am I saying that optimizing this is
- 41:54much more difficult? The reason is that
- 42:00if you understand, what is yi-hat in
- 42:04both places? In the case of linear
- 42:07regression, yi-hat is a very simple
- 42:09thing. It is mx + b, okay? If you try
- 42:16to draw it, if this is your experience
- 42:19and this is your salary, and if this is
- 42:24your data, then your 'yi-hat' is
- 42:27basically this line, it's a simple
- 42:30curve. But if you talk about our
- 42:35decision tree thing, then here what is
- 42:41'yi-hat'? First of all, 'yi-hat' is
- 42:46yi-hat at time t-1 + ft xi, you can see
- 42:51that. This entire term is our yi-hat,
- 42:55right? Now, if you talk about this term
- 43:00, it is a constant, but if you talk
- 43:02about this term, it is a decision tree,
- 43:05okay? So this means that if we had the
- 43:11same data, experience here, salary here
- 43:15, and these were our data points, then
- 43:19the 'yi-hat' curve would look something
- 43:23like this. It would look something like
- 43:27this. I am not sure if I will be able
- 43:32to draw this or not. Basically, if you
- 43:38have studied decision trees for
- 43:41regression, you would know that in this
- 43:44way the entire regression happens. In
- 43:51the case of suppose this was the data.
- 43:58Then in this case, it would look
- 44:01something like this. Something like
- 44:07this. What I am trying to tell you is
- 44:10that unlike the linear regression case,
- 44:12this won't be a simple line. In our
- 44:16case, it would be a zigzag curve, a
- 44:20curve like this. Okay? Why? Because the
- 44:25output of decision trees is actually
- 44:28like this. Okay? Okay? If I can show
- 44:32you, so I would just search for a
- 44:36decision tree regression graph just to
- 44:41show you, because I am not able to draw
- 44:45it correctly. So yeah, this is what I
- 44:49wanted to show you. You can see, if
- 44:52this were linear regression here. I
- 44:54will just cut this diagram and I will
- 44:57just show you what I am trying to say.
- 45:03Where did it go? Here it is. So if this
- 45:07were normal linear regression, a line
- 45:10would be drawn like this. Right? But
- 45:14since this is a decision tree or a set
- 45:17of decision trees. Then its graph will
- 45:21look like this. Like this. And it will
- 45:25look like this because if you have
- 45:27watched my decision tree class, then I
- 45:30had mentioned there that its output is
- 45:32piecewise constant. Meaning, in this
- 45:35area, it is a constant value. Then at
- 45:38the very next moment, it is this value.
- 45:40At the previous moment, it was that
- 45:42value. There are sudden jumps. There
- 45:44are sudden jumps. Okay? So because our
- 45:48yi hat is such a weird curve. Because
- 45:55of that, when we try to plot the graph
- 45:58of loss with yi hat, we will not get
- 46:01such a smooth parabolic curve. There is
- 46:05a good chance that we might get a curve
- 46:07like this. It is perhaps a parabola,
- 46:11but with many irregularities; imagine
- 46:15this in 3D. Okay? So because the
- 46:19parabola is formed in this way.
- 46:25Optimizing this will not be easy. Why?
- 46:28Because at many points this curve is
- 46:35not even differentiable. So basically,
- 46:39you cannot even apply this partial
- 46:44differentiation. You cannot even reach
- 46:46this point because you are unable to
- 46:48find the slope with respect to fxi. So
- 46:54let me summarize my entire argument
- 46:56once. What did I say we have to do? We
- 47:01need to find the ft xi that minimizes
- 47:04this entire equation, this entire
- 47:06objective function. So basically, this
- 47:10is an optimization problem. But we
- 47:13learned that in an optimization problem
- 47:16, what you do is differentiate your
- 47:19objective function with respect to the
- 47:22parameters involved and then equate it
- 47:26to zero to find the value. But for this
- 47:30, it is necessary that your
- 47:32optimization—I am sorry—your
- 47:34objective function must be
- 47:36differentiable. But since our y-i hat
- 47:41involves a decision tree. Because of
- 47:47this decision tree, the loss curve that
- 47:50is formed is actually
- 47:52non-differentiable at many points.
- 47:57Because of that, you cannot find this
- 47:59slope, and hence you cannot find a
- 48:02value of f (xi) that will minimize this
- 48:05entire thing. This is my argument. I
- 48:07hope I was able to explain it. So, what
- 48:11is the solution? The solution is, what
- 48:16if I could smooth out this curve—this
- 48:21zigzag, weird curve? Could approximate
- 48:26it? I mean, what if I could replace
- 48:32this complex equation with some other
- 48:39equation that might look like this. It
- 48:47is not necessary. It could be a bit
- 48:49higher or a bit lower. But it should be
- 48:52close. Okay? And at the same time, it
- 48:56should be smooth and differentiable.
- 49:00The important thing is that we can
- 49:03differentiate it with respect to f (xi)
- 49:07. This is very important, then our work
- 49:10can be done. So basically, what we need
- 49:15to do is somehow approximate this part
- 49:20of the objective function because,
- 49:23right now, this is not useful. So, this
- 49:28was a bit of a complex part of this
- 49:31entire explanation, but I think I was
- 49:33able to roughly explain what the
- 49:36problem is. And now, I will tell you
- 49:38the solution. The solution is that we
- 49:41will approximate our non-differentiable
- 49:44curve using a beautiful mathematical
- 49:47technique called Taylor series. I am
- 49:52sure you must have studied it in
- 49:54engineering math, but perhaps didn't
- 49:57pay much attention then, but guess what
- 49:59? It is going to help us with this
- 50:03problem now. So guys, let's quickly try
- 50:05to understand the Taylor series. So
- 50:08that when I apply it later, you have
- 50:11some idea. So, what is the Taylor
- 50:14series? Let me first define it for you
- 50:17in one line. So, the Taylor series is a
- 50:21very, very powerful approximation
- 50:24technique. That is the simplest
- 50:28definition. So, what does the Taylor
- 50:31series say? That you bring any complex
- 50:35function. Okay? Bring any complex
- 50:38mathematical function. And the Taylor
- 50:41series can approximate it using a
- 50:48polynomial. Right? Suppose you have
- 50:53some very complex function. Let's say
- 50:57for now, e to the power x, you can
- 51:00approximate it very easily using a
- 51:03polynomial. For instance, let's assume
- 51:08this is a polynomial. Okay? So, this is
- 51:14what the basic definition says: you
- 51:17input a complex function, and you can
- 51:20approximate it using simple polynomials
- 51:23. Okay? This is the main idea behind a
- 51:27Taylor approximation or Taylor series.
- 51:31The only caveat here is that if you
- 51:34want a very accurate, highly accurate
- 51:38approximation, then the polynomial you
- 51:43create will need many polynomial terms.
- 51:47Like x raised to the power 3, to the
- 51:50power 4, to the power 5, and so on. The
- 51:54more polynomial terms you keep adding,
- 51:56the more accurate your approximation
- 51:59will become. It will become more
- 52:01accurate. Okay? So that was the "what"?
- 52:05Now I will tell you the "how"—exactly
- 52:08how the Taylor series works. We won't
- 52:12go too deep because this isn't a video
- 52:14specifically about the Taylor series.
- 52:16So, I have added a video in the
- 52:19description. From 3Blue1Brown. It is a
- 52:21very beautiful video on the Taylor
- 52:23series. If you watch it once, your
- 52:25understanding will be well-developed.
- 52:27But still, I will explain to you a
- 52:29little bit about exactly how the Taylor
- 52:31series works. Okay? So, the Taylor
- 52:35series uses derivatives to convert any
- 52:39complex function into a polynomial. It
- 52:47uses first-order derivatives,
- 52:48second-order derivatives, third, fourth
- 52:50, and higher-order derivatives to
- 52:52approximate a complex function. Okay?
- 52:55So, if I tell you the formula—what is
- 52:58the Taylor series formula? The Taylor
- 53:01series formula for a function (f (x))
- 53:05around a point 'a' can be written as: f
- 53:14(x) is approximately equal to f (a) + f
- 53:18'(a) divided by 1!(x-a) + f''(a)/2!(x-a
- 53:37) ² + f'''(a)/3!(x-a) ³ and in this
- 53:49way, you can add as many polynomial
- 53:52terms as you want. So you can see, to
- 53:56approximate this function around point
- 53:58'a', I am using the derivatives. This
- 54:02is the first-order derivative. This is
- 54:03the second order, this is the third
- 54:05order. The more derivatives you keep
- 54:07adding, the more accurate approximation
- 54:09you will get. Okay? So, I will try to
- 54:12explain this whole thing to you through
- 54:15an example. Let's assume our function
- 54:19is e raised to the power x, and we want
- 54:22to approximate this function around the
- 54:26point a = 0. Okay? So, according to
- 54:29this formula, what will the
- 54:31approximation be? I will work that out
- 54:33for you. First, I will focus on this
- 54:35term. What will f of a be? So f of a
- 54:39will basically be e raised to the power
- 54:42of a instead of x, and the value of a
- 54:43is zero. That means it will be one.
- 54:47Okay? Now we will focus on this term.
- 54:51So this term is f '(a)/1!*(x-a). By the
- 54:57way, here f'(a) means the derivative of
- 55:02f (x). Okay? So you know that the
- 55:06differentiation of e to the power x is
- 55:08just e to the power x. So going by that
- 55:12logic, it will be e to the power x, and
- 55:15instead of x, we will put a, and the 1!
- 55:19becomes 1 here, and x-a comes here as
- 55:22it is. We will put zero in place of a.
- 55:25So it will simply become x. Okay? So,
- 55:32for this term, we got x. Now let's
- 55:35focus on this term. f ''(a)/2!(x-a) ²;
- 55:43the double derivative will be the same.
- 55:46So here we will get e to the power a/2!
- 55:52(x-a) ²; e to the power 0*x²; so we
- 55:58get x²/2! here. So it will be two.
- 56:03Then I will show you by calculating. f
- 56:08This term will basically be (x-a) ³/3!
- 56:15This will again be 1/6*x³; so this
- 56:24becomes x³/6. So basically, if I want
- 56:29to approximate e to the power x using
- 56:33Taylor series, this is what comes. And
- 56:45I can extend this as much as I want.
- 56:47Okay? So now I will show you how to
- 56:51visualize this. So I have Desmos open
- 56:55here. First, I will show you what e
- 56:59raised to the power x looks like. It's
- 57:02very famous. You must already know. Now
- 57:05I will show you y = by adding 1 + x. So
- 57:14basically, I have used only these terms
- 57:17for now. Okay? And you can see that the
- 57:22approximation is already accurate for x
- 57:27= 0 or a = 0. At least at this point,
- 57:31the blue curve and the red curve are
- 57:33the same thing. Okay? But notice, as I
- 57:37keep adding higher-degree terms, like
- 57:40adding x²/2, you will notice that a
- 57:48bit around zero, on both sides, the
- 57:52approximation is becoming more accurate
- 57:55. Notice, I am adding the x³ term.
- 58:05Divided by 6, and you can see that you
- 58:08can now see the approximation over a
- 58:10larger area. So basically, the more
- 58:14terms you keep adding to this
- 58:17polynomial, the more your approximation
- 58:20accuracy will improve for a wider range
- 58:23of x. Right? If you add a lot of terms,
- 58:27it will start to perfectly approximate
- 58:29this red curve. And that is the beauty
- 58:32of Taylor series. Right? So that is
- 58:35what we have to do now. We need to
- 58:37apply Taylor series to our objective
- 58:41function, which is not particularly
- 58:46usable at this point, and make it
- 58:50usable. So guys, now that we understand
- 58:53what Taylor series is and how it works.
- 58:57Now we will apply the Taylor series to
- 58:59our objective function and approximate
- 59:01and simplify this complex objective
- 59:03function of ours. Right? We are just
- 59:07going to do one thing: we will simplify
- 59:10only up to the second-degree polynomial
- 59:13. Basically, we will take this term,
- 59:15this term, and this term. We won't take
- 59:17the terms beyond that. Third derivative
- 59:19, fourth derivative. We don't need to
- 59:21take them. Our work will get done.
- 59:23Right? Now, the biggest challenge in
- 59:27applying Taylor series approximation to
- 59:30such complex equations is to identify
- 59:34what x will be and what a will be. So,
- 59:38first of all, I would like to give this
- 59:40clarification. Look, in our case, x
- 59:43will be this entire term. Oh, one more
- 59:46thing, we are only going to apply
- 59:49Taylor series to this much part. We
- 59:52won't apply it to the rest. Right? So
- 59:55here, if you notice, then our x is this
- 59:58entire thing. Because this is the very
- 1:00:00thing that will vary. Basically, the
- 1:00:03prediction up to the t-th iteration. So
- 1:00:08you can write it down here first: yi
- 1:00:13hat t-1 + ft. xi, this becomes our x.
- 1:00:20Now the question arises: what will a be
- 1:00:22? A is the point of change where the
- 1:00:25modification starts to occur. So
- 1:00:27basically, this T-1 iteration is the
- 1:00:30point after which the change is
- 1:00:32happening. We are adding this decision
- 1:00:34tree. Now, it can have any output. So
- 1:00:37we will take a as yi hat t-1, okay? The
- 1:00:42change is about to happen after this.
- 1:00:44Right? Now, what will we do? We will
- 1:00:46calculate all these terms one by one
- 1:00:50and approximate this equation. So first
- 1:00:53of all, we need to calculate f (a), so
- 1:00:56to calculate f (a), what will we have
- 1:00:58to do? First, we have to write f (x)
- 1:01:01and then wherever there is x, we will
- 1:01:03substitute it with a. We will replace x
- 1:01:07. So, first, let me write down f (x)
- 1:01:09for you. So f (x) is this entire term
- 1:01:12of ours. I am writing this as it is. i
- 1:01:16= 1 to n, yi-yi hat (t-1) + (ft) xi;
- 1:01:29okay, this is my entire x. Now I just
- 1:01:33have to do one thing, I have to replace
- 1:01:36this entire x with a. So what I will do
- 1:01:38is, I will just erase and I will
- 1:01:43rewrite and this becomes our f (a); we
- 1:01:46have found our first term. Now, we need
- 1:01:49to find the second term similarly. What
- 1:01:52do we need to do for the second term?
- 1:01:54We need to find f '(a). Okay? Basically
- 1:01:58, we need to do df/dx. And then, after
- 1:02:02replacing x, let's assume for a moment
- 1:02:05that f (x) is x². So, what would df/dx
- 1:02:09be? 2x So then, what would f'(a) be? 2a
- 1:02:18, replaced x with a. So, if I want to
- 1:02:22write it simply, then f '(a) x-a; let's
- 1:02:27focus on f'(a) first. This will become
- 1:02:32our sigma i = 1 to n del L yi yi hat,
- 1:02:42here too t-1 will come. Because you
- 1:02:45have to put a in place of x. Divided by
- 1:02:48del y t-1, okay. Now let's talk about
- 1:02:55x-a, it's simple. You subtract this
- 1:02:58from that. What is left? ft xi and
- 1:03:04similarly we now need to find f ''(a)/2
- 1:03:10*(x-a) ². So, this is also simple.
- 1:03:14Here we will have i = 1 to n. This will
- 1:03:21remain the same thing, just
- 1:03:23double-differentiated, square of ft
- 1:03:30squared. And we have approximated this.
- 1:03:33Now I will just place these three here,
- 1:03:36so this whole equation will now be
- 1:03:39formed. I am bringing all three
- 1:03:42summations out. And first of all, L
- 1:03:47will come (yi, yi hat t-1 iteration),
- 1:03:56plus now this term, this big
- 1:04:00differentiation here, we call this the
- 1:04:05gradient. This is called the gradient.
- 1:04:09Okay? And we will denote this by gi. So
- 1:04:15what we can do is we can write gi. Oh,
- 1:04:20I forgot one more thing here. A half
- 1:04:23will also come outside here because
- 1:04:24this is also two, right. So here it
- 1:04:27became gi. And then came our ft xi plus
- 1:04:35. Now this term, the double
- 1:04:38differentiation of the loss function,
- 1:04:42we call it the Hessian. You might have
- 1:04:46heard of it, and you will denote it by
- 1:04:49hi, so here will come 1/2 hi ft² xi
- 1:04:57and then lastly, this term will also
- 1:05:02come, plus ft I am sorry, here will
- 1:05:09come omega of ft xi and this is our
- 1:05:15simplified objective function, guys. So
- 1:05:18, I have written this final equation a
- 1:05:21bit more clearly here. Right? I guess,
- 1:05:25first of all, you can appreciate that
- 1:05:28we have given that complex equation a
- 1:05:32polynomial form, and now our objective
- 1:05:35function is represented very well in
- 1:05:38terms of x. Also, at this point, I
- 1:05:41would like to show you the research
- 1:05:43paper. And you can see that we have
- 1:05:46achieved this step exactly. Absolutely
- 1:05:49line by line. Here is our first term.
- 1:05:52Here is our second gradient term, and
- 1:05:55here is our third Hessian term. This is
- 1:05:58exactly what we have achieved here. Now
- 1:06:01, if we want, we can simplify this a
- 1:06:04little bit. How? I will tell you. Look,
- 1:06:08what is our goal? What did we set out
- 1:06:10to do? We need a value for f (t, xi)
- 1:06:14for which this entire equation is
- 1:06:17minimized. Okay? So, our plan was to
- 1:06:21differentiate this whole thing with
- 1:06:25respect to f (t, xi) and then set it to
- 1:06:28zero. Right? I mean, the plan was
- 1:06:31something like this, or we will apply
- 1:06:33some form of optimization. So, we have
- 1:06:36to differentiate. That is clear. So,
- 1:06:39notice one thing. If I look here, there
- 1:06:45are a total of four terms. This is the
- 1:06:47first term. This is the second term,
- 1:06:50this is the third term, and this is the
- 1:06:52fourth term. In this, this, and this, f
- 1:06:55(t, xi) is present. Meaning,
- 1:06:58differentiating will be useful. But f (
- 1:07:00t, xi) is not present in this one. So,
- 1:07:03when I differentiate it with respect to
- 1:07:05f (t, xi), this term will automatically
- 1:07:07become zero later on. So, what I can do
- 1:07:11is, I can perform a simplification and
- 1:07:14I can write my objective function as
- 1:07:16this. Just a sum of gradients and
- 1:07:25Hessian. And exactly this is written
- 1:07:29here in the next equation. Look, these
- 1:07:32people have done the same thing. They
- 1:07:34have also removed this term. Because
- 1:07:37this is a constant term. It does not
- 1:07:39contain f (t, xi). So, by
- 1:07:41differentiating it further, you won't
- 1:07:43get anything from it. So, it was just a
- 1:07:46smart move to remove that. And now we
- 1:07:48are here. Now, perhaps you might also
- 1:07:51notice that this term of ours has been
- 1:07:54sitting quietly for a long time. So,
- 1:07:57now what will we do? We will expand
- 1:07:59this too. Okay? And we know how to
- 1:08:03expand. I told you when I taught you
- 1:08:06the XGBoost loss function that this
- 1:08:08term is kind of your regularization
- 1:08:11term and you can break it down into
- 1:08:13these two components. Okay? Here, this
- 1:08:17t is the decision tree that you must
- 1:08:20have applied at the t-th step, which is
- 1:08:22the last model you added. So, this t
- 1:08:27indicates how many leaf nodes there are
- 1:08:30. So you can see there are three leaf
- 1:08:32nodes in this one. And this lambda
- 1:08:36times W squared basically means that
- 1:08:40the output of these three leaf nodes
- 1:08:43can be called W1, W2, and W3. So we can
- 1:08:48write it by breaking it down as 1/2
- 1:08:52times lambda W1 squared + W2 squared +
- 1:08:57W3 squared, okay? One term for each
- 1:09:01leaf node. Okay? So that is what we are
- 1:09:04going to do. We are going to expand
- 1:09:09this. Okay? For a moment, let's assume
- 1:09:13that the tree we added at the end has t
- 1:09:17leaf nodes. Okay? So how will this
- 1:09:22entire equation break down? This whole
- 1:09:26equation will become. i = 1 to n. We
- 1:09:30will write this term as it is. gi ft xi
- 1:09:36+ 1/2 hi ft squared xi plus here you
- 1:09:42will have gamma times t + 1/2 lambda
- 1:09:48inside, since there are t leaf nodes,
- 1:09:55we will write it as w 1² + w 2² + w
- 1:10:013² dot dot dot + wt² because there
- 1:10:07are t nodes. Now obviously this is not
- 1:10:10the compact form. So to write this in
- 1:10:13compact form, what we can do is we can
- 1:10:15use a summation. So we can write it
- 1:10:17this way. We can call it i or j.
- 1:10:21Because we have already used i. j = 1
- 1:10:25to T of WJ squared. Okay? This became
- 1:10:32our somewhat more simplified objective
- 1:10:34function. So now guys, we have brought
- 1:10:37this objective function up to this
- 1:10:39point, but there is a big problem here.
- 1:10:42Understand the problem. There are three
- 1:10:45terms here. This is the first term,
- 1:10:47this is the second term, and this is
- 1:10:49the third term. Now, two of these terms
- 1:10:52have a summation. In this term and in
- 1:10:54this term. But the problem is that
- 1:10:57these two summations are different.
- 1:10:59Here you have a summation over i which
- 1:11:02goes from 1 to n. Basically the number
- 1:11:05of rows. And here you have another
- 1:11:10summation over j which goes from 1 to t
- 1:11:13. Where t is what? t is your number of
- 1:11:17leaf nodes in the last model that was
- 1:11:21added. For instance, if there are two
- 1:11:24leaf nodes, then the value of t will be
- 1:11:26two and the value of j will be one for
- 1:11:27the first time. The second time, it
- 1:11:29will be two. So now, the problem is
- 1:11:32that if we go to optimize this, there
- 1:11:34will be a problem. So we have to
- 1:11:38simplify this further and bring them
- 1:11:40into a common summation. So I am going
- 1:11:43to do a smart manipulation here. First,
- 1:11:48I will show you that manipulation and
- 1:11:50then I will explain how it happened.
- 1:11:53But trust me, after that manipulation
- 1:11:56is done, things will drastically
- 1:11:58improve. Then it will become very easy
- 1:12:00to optimize this. So let me write it
- 1:12:03down first. So I would write it this
- 1:12:05way. Summation of j = 1 to t Bracket
- 1:12:16summation i belongs to ij gi wj plus
- 1:12:27summation i belongs to ij 1/2 comes
- 1:12:35outside h wj sq plus gamma plus plus
- 1:12:471/2 lambda I am sorry j = 1 to t wj²
- 1:12:57This is the transformation. Now I will
- 1:13:00be very honest with you. When I was
- 1:13:02reading this XGBoost paper and I saw
- 1:13:04this step and this transformation, for
- 1:13:07a while I didn't even understand how
- 1:13:09this happened. How are we able to write
- 1:13:13it this way? But trust me, it's very
- 1:13:15logical. I will explain it to you one
- 1:13:17by one. First of all, understand a
- 1:13:19small change. The first change is that
- 1:13:24I have started calling ft (xi) as wj. I
- 1:13:29guess you might be able to notice this.
- 1:13:32This is the first change. Right? This
- 1:13:38is the first change. I will write it
- 1:13:42here that wj is nothing but ft (xi)
- 1:13:48right? The second change is that I have
- 1:13:54broken i = 1 to N into two summations.
- 1:14:01First j = 1 to t and inside that, i
- 1:14:05belongs to ij. You just need to
- 1:14:10understand these two things. If you
- 1:14:13understand these two things, you will
- 1:14:15understand this transformation. Alright
- 1:14:18guys, then I will explain to you how we
- 1:14:20took this transformation. Right? First,
- 1:14:24I will explain how we gave the form of
- 1:14:28summation i = 1 to n to j = 1 to t and
- 1:14:32inside that, i belongs to ij. Right? To
- 1:14:37understand this, I have taken a small
- 1:14:39example. Suppose this is your data. It
- 1:14:42has an input column. You can call it xi
- 1:14:45. And this is your output column. You
- 1:14:47can call it yi. And this is our t-th
- 1:14:50step decision tree. It's a very simple
- 1:14:53decision tree. Where it's just asking
- 1:14:55if the CGPA is less than seven. If it's
- 1:14:57less, the package will be five, and if
- 1:15:00it's more than seven, the package will
- 1:15:02be 10. Simple. Okay? Since this is a
- 1:15:05leaf output, we are calling it W1. And
- 1:15:08this is also a leaf output, so we are
- 1:15:10calling it W2. Okay? Now understand,
- 1:15:13look at this setup. Focus on this. Just
- 1:15:17focus on this part. If I were to tell
- 1:15:22you to expand this term for this
- 1:15:24particular dataset where you have four
- 1:15:27rows. Expand this term. Then how would
- 1:15:31you write it expanded? You would write
- 1:15:33G1 FT X1 + 1/2 H1 FT² X1 would be for
- 1:15:47the first row. Okay? Here, wherever
- 1:15:50there is X1, you would put 7.1. Okay?
- 1:15:54Even here in X1, you would put 7.1.
- 1:15:57Plus, now what would you do for the
- 1:15:59second row? For the second row, you
- 1:16:02would write G2 f2 x2 + 1/2 h2 f t² x2,
- 1:16:09here wherever there is x2, you would
- 1:16:15put 8.2. You would write the same for
- 1:16:18the fourth term: g4 ft x4 + 1/2 h4 ft²
- 1:16:33x4. I guess you can understand, I have
- 1:16:36expanded it for all four terms. If you
- 1:16:38divide it here, there are four terms in
- 1:16:42total, one for each row. Okay, now I
- 1:16:47will explain what this is saying here.
- 1:16:51So first of all, think about how many
- 1:16:53times this outer summation will open?
- 1:16:56This outer summation will open twice,
- 1:17:00why? Because in our decision tree,
- 1:17:02there are two leaf nodes. This is one,
- 1:17:04this is two. So this outer node will
- 1:17:08run twice. Now let's talk about the
- 1:17:11inner node and what it means. i belongs
- 1:17:14to IJ. What is IJ? So IJ is the
- 1:17:19instance set of leaf J. That is what I
- 1:17:26mean. Watch carefully. It's a very
- 1:17:28small thing. This is row one. This is
- 1:17:30row two. This is row three. This is row
- 1:17:33four. Okay? Now I am putting these rows
- 1:17:36into this decision tree. CGPA less than
- 1:17:397.1 Less than seven. So where will this
- 1:17:45first row fall? Into this leaf. It's
- 1:17:508.2. Where will it fall? Right here.
- 1:17:54It's 6.5. Where will it fall? 3 and 9.1
- 1:17:59. Where will it fall? Four. So that
- 1:18:03means based on this data, we can say
- 1:18:07that for this leaf, leaf node one, its
- 1:18:10instance set contains only one row,
- 1:18:13this one. Whereas if you talk about
- 1:18:18this leaf, its instance set will
- 1:18:20contain three rows. One, two, and four.
- 1:18:24Okay? So now look, I am expanding it. I
- 1:18:27am starting the value of J from one.
- 1:18:31Started the value of J at one. This
- 1:18:33means we are talking about this leaf
- 1:18:35node. Now what do we need to do? For
- 1:18:37whatever row is inside this leaf node,
- 1:18:41we have to write this equation. Okay?
- 1:18:45So that will be g 3, for a moment I
- 1:18:52will just call wj as ft xi. I will
- 1:18:56explain how both are equal a little
- 1:18:57later. But for now, I am calling it ft
- 1:19:02x3. Plus 1/2 h3 ft x3. That's it. Now
- 1:19:15Since there was only one in this, the
- 1:19:17work of the first leaf node is finished
- 1:19:19. Now we will move to J = 2, which is
- 1:19:22this leaf node. Now it has three rows.
- 1:19:25Which is the first row? The one with
- 1:19:26one. So for that, it will be G1 FT X1 +
- 1:19:341/2 H1 FT X1 Okay? It will be squared.
- 1:19:42Here also it will be squared. Then the
- 1:19:46second row will come, g2 ft x2 + 1/2 h2
- 1:19:57ft² x2, and lastly the fourth term
- 1:20:03will come, g4t x4 + 1/2 h4 ft² x4. Now
- 1:20:16you compare this one and compare this.
- 1:20:20You would find that both are the same.
- 1:20:23The order is different, but they are
- 1:20:25the same thing. Right? So it means that
- 1:20:29when we have written the equation in
- 1:20:31this form, we are writing all these
- 1:20:33rows one by one in this form. But when
- 1:20:39we bring it into this form, what are we
- 1:20:41doing? We are asking the tree which
- 1:20:43rows ended up in your first leaf node.
- 1:20:46For them, I did the same thing. Then
- 1:20:50for the rows in the second leaf node, I
- 1:20:52did the same thing. So basically, I am
- 1:20:55still traversing over all the rows. I
- 1:20:57have just segregated them according to
- 1:21:00the tree. So if we were talking about
- 1:21:02the first 100 children before. Here too
- 1:21:04, we are talking about the same 100
- 1:21:05children. Only the order has changed.
- 1:21:08Because you are expanding according to
- 1:21:10the decision tree's processing. So I
- 1:21:14really hope you understood this first
- 1:21:17similarity, how we smartly broke down i
- 1:21:20= 1 to n into this. Okay? Now, just one
- 1:21:25thing remains to be understood, why I
- 1:21:28have called F (t, xi) as Wj. Look here,
- 1:21:35I guess you can understand this very
- 1:21:38easily too. Think about it, when you
- 1:21:42are talking about the third row, when
- 1:21:44you talk about the third row, the third
- 1:21:47row has entered this leaf, right? So,
- 1:21:51for that, what will ft (t, x3) be?
- 1:21:55First of all, what was ft? ft was the
- 1:21:57output of our decision tree. Now think
- 1:22:01for yourself, for x3, as in the third
- 1:22:03row, what output will our decision tree
- 1:22:06give? W1 It will give W1 as the output,
- 1:22:12right? So, I can actually write it like
- 1:22:15this too. Right? Similarly, if you talk
- 1:22:25about this one. This is the first row.
- 1:22:27So, for the first row, what will our
- 1:22:30decision tree output? W2, so I can
- 1:22:33write this as G1 W2 as well. I guess
- 1:22:46you are understanding. This WJ is
- 1:22:50basically the output of the tree for a
- 1:22:53particular leaf node. If I know that
- 1:22:57leaf node, I can directly write it in
- 1:22:59its place, right? That is why I
- 1:23:02performed this transformation. And now
- 1:23:04we are at a stage where we have a
- 1:23:09proper objective function. In a
- 1:23:13completely simplified form. I will
- 1:23:14write it down one more time. The more I
- 1:23:17write it, the more familiar it will
- 1:23:20feel to you. Here we have gi wj + 1/2 i
- 1:23:32belongs to ij hi wj squared plus gamma
- 1:23:42t + 1/2 lambda j = 1 to t wj squared
- 1:23:50and now we can actually simplify this
- 1:23:55entire thing. So, simplifying this now
- 1:23:59is simple algebra. You can see that
- 1:24:02this term, this term, and this term,
- 1:24:06all three are summed from j = 1 to t.
- 1:24:11So, what can we do? We can write the
- 1:24:14loss or objective function in this way.
- 1:24:18Summation j = 1 to t, here we will have
- 1:24:25i belongs to ij gi wj squared plus 1/2
- 1:24:36i belongs to ij hi wj squared and 1/2
- 1:24:47lambda wj squared + gamma t. Now, you
- 1:24:56can take some things common in these,
- 1:25:00like you can write it as I am writing
- 1:25:09it again, summation i belongs to ij gi
- 1:25:13wj squared plus we took half as common,
- 1:25:18and after taking half out, what remains
- 1:25:24here is i belongs to ij hi plus here
- 1:25:29remains lambda, and we also took wj
- 1:25:35squared as common + gamma t. And now we
- 1:25:41are at the position where we can now
- 1:25:45differentiate this term with respect to
- 1:25:48WJ, okay? So, this is for all the terms
- 1:25:55for all the leaves in your decision
- 1:25:57tree, but we actually need to do it for
- 1:26:00just one leaf, and from that, we will
- 1:26:03get the answer for the other leaves too
- 1:26:05. So, basically, we don't need this
- 1:26:08outer summation. We would just take
- 1:26:12this, this, and this. This will also
- 1:26:16become zero. Because when you
- 1:26:18differentiate this with respect to Wj,
- 1:26:20since there is no Wj here, it will
- 1:26:22become zero. Only this term and this
- 1:26:25term will remain, so as soon as we
- 1:26:29differentiate with respect to Wj, first
- 1:26:34of all, okay, one thing I have been
- 1:26:36doing wrong. There won't be a square
- 1:26:38here. My bad, there won't be a square
- 1:26:40here either. First of all, when you
- 1:26:44differentiate this, you will get the
- 1:26:47sum of i belonging to Ij of gi. Right?
- 1:26:53Plus, when you differentiate this, it
- 1:26:56will become 2 times Wj. This two will
- 1:26:58come out to the front. So 2/2 will
- 1:27:01become 1. So you will just be left with
- 1:27:04here, sum of i belonging to Ij of Hi +
- 1:27:11lambda*Wj, and now you have to set this
- 1:27:15equal to 0 and find the value of Wj,
- 1:27:20and the value of Wj will be-lambda*sum
- 1:27:24of i belonging to Ij of gi, divided by
- 1:27:33sum of i belonging to Ij of Hi + lambda
- 1:27:38, and this is the output value for all
- 1:27:45the leaves. If you are talking about
- 1:27:50leaf one, if you want to find w1, then
- 1:27:53you just have to calculate the gradient
- 1:27:57for all those rows that are falling
- 1:28:00into this leaf. If you want to
- 1:28:03calculate W2, then you have to
- 1:28:05calculate the gradient of all those
- 1:28:07rows that are falling into this leaf
- 1:28:10node. And that's it. Now our only job
- 1:28:13is to find out what Gi is and what hi
- 1:28:16is. And we will get our formula to
- 1:28:21calculate the output that we set out to
- 1:28:25find. So guys, we are this close to
- 1:28:29calculating the exact value of Wj, just
- 1:28:32two missing pieces left. We need this
- 1:28:36value of G and we need this value of H.
- 1:28:38G means gradient, and H means Hessian.
- 1:28:46Right? So let me remind you once where
- 1:28:48these came from. When we were applying
- 1:28:52the Taylor series to our objective
- 1:28:54function, we got these derivatives and
- 1:28:56this double derivative there. We called
- 1:29:00the derivative the gradient and the
- 1:29:01double derivative the Hessian. So now
- 1:29:04we have to calculate these values. The
- 1:29:09problem is that your gradient, which
- 1:29:13you are also writing like this: y i hat
- 1:29:20t minus 1, Del y-hat t-1 and whatever
- 1:29:26your Hessian is (well, Del will be used
- 1:29:30here too), whatever your Hessian is,
- 1:29:34which is the double derivative. Let me
- 1:29:41write it down first, then I'll explain
- 1:29:43what I'm trying to say. So, the problem
- 1:29:47with this gradient and Hessian is that
- 1:29:50they actually depend on the loss
- 1:29:52function. This means you will have to
- 1:29:55derive separate gradients and Hessians
- 1:29:58for regression and separate ones for
- 1:30:00classification. So, what do we do first
- 1:30:03? Let's focus on regression because the
- 1:30:05loss function is a bit simpler here.
- 1:30:07One more thing I would like to clarify.
- 1:30:11Don't be intimidated by this t-1. It
- 1:30:15simply means that you are adding models
- 1:30:19one by one, and you are currently at
- 1:30:23the t-th iteration. But the loss you
- 1:30:28are calculating is at the t-1 step. You
- 1:30:31are calculating the loss at this step.
- 1:30:33That's it. Nothing more. Okay? So it's
- 1:30:36nothing special. It's basically the
- 1:30:38same thing. So, if you talk about
- 1:30:43regression, then in regression, your
- 1:30:46loss function is Mean Squared Error,
- 1:30:50and you can also write it as: sigma of
- 1:30:54i = 1 to n (yi-yi-hat) squared. Okay,
- 1:31:00now whether you write yi-hat here or
- 1:31:03add t-1, it doesn't matter, it's the
- 1:31:05same thing. You have to differentiate
- 1:31:09this. You have to find out this value.
- 1:31:13So, what will this value be? It's very
- 1:31:16simple. If you differentiate, you will
- 1:31:20basically get sigma i = 1, this two
- 1:31:23will come here and cancel out, and you
- 1:31:27will get yi-yi-hat, and this minus sign
- 1:31:30will come out after differentiation.
- 1:31:35Okay? This is basic differentiation. So
- 1:31:37you can write it like this too. i = 1
- 1:31:40to n yi-hat-yi Okay? And this is your
- 1:31:50gi. Okay? Also, the yi-hat here is the
- 1:31:55yi-hat of the previous step. You have
- 1:31:59to remember this because it is t-1. The
- 1:32:02significance of this t-1 is that the
- 1:32:04yi-hat is from the previous step. So if
- 1:32:06I place this here, what will this whole
- 1:32:10thing become? This whole thing will
- 1:32:13become minus sigma of i instead of gi.
- 1:32:23Now we will not use this summation.
- 1:32:27Because we are already using this
- 1:32:29summation. We are not talking about all
- 1:32:31the rows. We are only talking about the
- 1:32:34rows that fell into the current leaf.
- 1:32:36So the next term will remain the same.
- 1:32:37So here we will get yi hat minus yi.
- 1:32:44Now, if you want, you can take this
- 1:32:46minus inside. So actually, you can
- 1:32:49write it by flipping it. You can write
- 1:32:53it by reversing it. Then it will return
- 1:32:57to yi minus yi hat. And just remember,
- 1:33:00this will be t-1, the y-hat from the
- 1:33:02previous step. Okay? Now think for
- 1:33:05yourself, in a way, what are you doing?
- 1:33:07You are calculating the residual for
- 1:33:13every point. That is exactly what you
- 1:33:16are doing, right? Just think about it,
- 1:33:18suppose you have this data-CGPA, IQ,
- 1:33:22and the package received. How did you
- 1:33:26start? You used to start. Suppose you
- 1:33:28have this data. Eight, 80, package
- 1:33:30received is eight; nine, 90, package
- 1:33:32received is nine, for example. Okay? So
- 1:33:35how did you start? You used to build
- 1:33:37the first model. So what was the
- 1:33:38prediction of the first model? Which is
- 1:33:40the mean. So here we get pred one. So
- 1:33:43this became 8.5, and this also became
- 1:33:468.5. Okay? So this is your yi and this
- 1:33:51is your yi hat. For step one. Okay? Now
- 1:33:56, as soon as you started adding the
- 1:34:00second model, this column became your t
- 1:34:04-1. Okay? So now for this, what do you
- 1:34:08need to do? To calculate the gradient,
- 1:34:11you just need to subtract this column
- 1:34:13from this column. Calculate 8 minus 8.5
- 1:34:16. Calculate 9 minus 8.5. Okay? So in a
- 1:34:20way, basically, whatever your residual
- 1:34:22was from the previous step, that is
- 1:34:23what came here. So I can actually do
- 1:34:26what with this? I can replace this with
- 1:34:30the sum of residuals. Don't you think
- 1:34:36this whole expression above can just be
- 1:34:39replaced with the sum of residuals?
- 1:34:42Okay? Now let's talk about the Hessian.
- 1:34:45So in the case of the Hessian, what do
- 1:34:47you have to do? Differentiate this
- 1:34:49thing twice. When we differentiated it
- 1:34:53once with respect to yi hat, what did
- 1:34:56we get? We got—let's forget the
- 1:34:59summation for a moment. Okay? Ignore
- 1:35:01the summation because there is a
- 1:35:03summation from i equals 1 to n. Here is
- 1:35:05another summation. So ignore that. You
- 1:35:08got this yi hat minus yi. Okay? Now you
- 1:35:15have to differentiate it again, with
- 1:35:18respect to yi hat. You have to
- 1:35:21differentiate one more time, so what
- 1:35:22will you get? You will get one, right?
- 1:35:27This means down here we will have σ (i
- 1:35:32belonging to ij) one + lambda. Now, how
- 1:35:37many times will this one occur? As many
- 1:35:40as the number of points falling into
- 1:35:44your leaf, so basically this becomes
- 1:35:49number of residuals + lambda. So, in
- 1:35:53simple terms, if you go to calculate wj
- 1:35:58for a regression problem with mean
- 1:36:02squared error, your formula is sum of
- 1:36:07residuals divided by number of
- 1:36:11residuals + lambda, okay, that are
- 1:36:17falling into that leaf. Okay? And if
- 1:36:22you go back to the very beginning, to
- 1:36:25the plan of attack, notice this right
- 1:36:28here. This is exactly what we just
- 1:36:30derived. Sum of residuals/number of
- 1:36:36residuals + lambda; we have solved the
- 1:36:38regression problem. Now, only the
- 1:36:41classification problem remains. Now
- 1:36:43let's talk about the classification
- 1:36:46scenario. Here, if you want to
- 1:36:48calculate the gradient and hessian,
- 1:36:51your loss function is log loss. Okay?
- 1:36:57You will have to differentiate and
- 1:36:59double-differentiate the log loss to
- 1:37:00find out g and h. The good part is that
- 1:37:04we have already done this in gradient
- 1:37:07boosting. So, I won't show it again
- 1:37:11here because it will take a lot of time
- 1:37:13. But I will show you where I have
- 1:37:15taught this to you. So, if you go to
- 1:37:17your course dashboard, you'll find
- 1:37:20gradient boosting taught in week 36.
- 1:37:22The math formulation for gradient
- 1:37:24boosting classification is there. If
- 1:37:27you watch from 37 minutes onwards, I
- 1:37:29have derived everything to show what
- 1:37:31comes from single differentiation. And
- 1:37:34then I have also explained what comes
- 1:37:36from double differentiation. Here, you
- 1:37:41will find, like, I'll have to scroll a
- 1:37:43bit to figure out where it is. But yeah
- 1:37:46, both things have been derived. In
- 1:37:49fact, you can also see it in the notes
- 1:37:51that have been provided to you. Anyway,
- 1:37:55let me show it to you. Yeah, so when
- 1:38:01you differentiate once, here is your
- 1:38:06output. It's basically yi-pi; pi is the
- 1:38:11probability for the previous time step,
- 1:38:14okay? You can call this a residual
- 1:38:17itself. And if you double-differentiate
- 1:38:21, you get this: pi*(1-pi). Here, pi is
- 1:38:25again the probability in the previous
- 1:38:28time step. Okay? So Basically, when you
- 1:38:33calculate wj for the classification
- 1:38:37scenario, it's the same here as well.
- 1:38:40The sum of residuals will still be on
- 1:38:43top. There will just be one change in
- 1:38:45the denominator. Here comes PI 1-PI +
- 1:38:50lambda i belongs to I. What is PI here?
- 1:38:58The predicted probability from the
- 1:39:02previous time step or iteration, you
- 1:39:07can say. Okay? So this is the output
- 1:39:11and this is what we saw when we
- 1:39:13discussed the plan of attack. You can
- 1:39:16see. At the top is the sum of residuals
- 1:39:19, and this has come at the bottom. Okay
- 1:39:22? And this is what we calculated here
- 1:39:25as well. And you can see, I hope you
- 1:39:27have understood up to this point. So
- 1:39:31guys, if we go back to where we started
- 1:39:33, we wanted to learn to derive four
- 1:39:35formulas in this video. We have learned
- 1:39:39to derive two of those formulas from
- 1:39:41scratch. The one to calculate the
- 1:39:44output value. Now only two formulas are
- 1:39:46left, and that is the formula to find
- 1:39:48the similarity score. Where did this
- 1:39:50come from? We will learn that now. So
- 1:39:53if we look at our progress so far, we
- 1:39:57had an objective function. Okay? Whose
- 1:40:02equation is on the screen, and we
- 1:40:04calculated the values of wj that
- 1:40:07minimize it, and that wj turned out to
- 1:40:10be this. Then, when I put the values of
- 1:40:14G and H into this wj, I got the output
- 1:40:17value exactly for both regression and
- 1:40:20classification. But what if I do one
- 1:40:25thing, take this wj and replace it here
- 1:40:29, what will I get? Think about it. I
- 1:40:34will get the minimum loss. That comes
- 1:40:40from using this parameter value. Right?
- 1:40:45Currently, what is this wj? This is the
- 1:40:48value of wj. That will minimize this
- 1:40:53loss. But how much will that loss be?
- 1:40:57What will be its minimum value? We want
- 1:40:59to find that out. So that is why we
- 1:41:02will replace them inside wj. So what
- 1:41:06will happen by replacing? I am
- 1:41:07continuing here. Why is it called that?
- 1:41:11This minimum loss that comes, why is it
- 1:41:13called that? First, let me derive the
- 1:41:17expression for you. Then I will tell
- 1:41:20you what its significance is. So there
- 1:41:23is nothing special. We will basically
- 1:41:26use simple mathematical algebra to
- 1:41:30manipulate it. Otherwise, there is
- 1:41:32nothing special. Here comes GI. This wj
- 1:41:35we are...filling in here. Here comes
- 1:41:50plus 1/2. i belongs to ij. hi + lambda,
- 1:42:01here it is squared, so here will come i
- 1:42:05belongs to ij gi squared divided by the
- 1:42:10square of the bottom quantity as well.
- 1:42:15i belongs to ij hi + lambda squared.
- 1:42:21Okay? And...We will close this and here
- 1:42:28am t will come. Now you will notice
- 1:42:33that this quantity will cancel out this
- 1:42:36quantity once because there is a square
- 1:42:39there, and by doing that we get this.
- 1:42:43We will get J. By the way, it should be
- 1:42:47J here. I am sorry. Because there are
- 1:42:49such long expressions and I have to
- 1:42:51teach simultaneously. So, some small
- 1:42:53mistakes might be happening. I am sure
- 1:42:55there must be some mistakes earlier too
- 1:42:57that I might not have noticed. So
- 1:42:59please write in the comments so that if
- 1:43:02anyone gets confused in the future, if
- 1:43:05they go through the comments, at least
- 1:43:08they will understand. So, one thing you
- 1:43:14might be seeing is that both terms have
- 1:43:16become the same. This one and this one,
- 1:43:21there is a -1 in front of this. There
- 1:43:24is a +1/2 in front of this. So, if we
- 1:43:28want, we can write it like this. This
- 1:43:31would become -1/2 + t. Now, if I want,
- 1:43:39I can bring this -1/2 outside. So, this
- 1:43:44will come as -1/2, j = 1 to t In the
- 1:43:54numerator, there will be Σ (i belongs
- 1:43:57to Ij) gi², divided by (i belongs to
- 1:44:05Ij) hi + λ + gamma. This is the
- 1:44:10minimum loss value. This is the minimum
- 1:44:16loss value, and it indicates what the
- 1:44:20minimum loss will be from the last
- 1:44:24model you are adding, the last tree you
- 1:44:29are adding. Okay? Exactly this same
- 1:44:33value you will also find in the
- 1:44:35research paper. You can see I am
- 1:44:37talking about this value. We had
- 1:44:40already calculated wj. When we filled
- 1:44:44it back, -1/2 Σ gi²/hi + λ + t, we
- 1:44:49got exactly this. And look what is
- 1:44:53written here. This equation can be used
- 1:44:56as a scoring function to measure the
- 1:44:58quality of a tree structure q. Whatever
- 1:45:03tree you have built at iteration t, the
- 1:45:07most recent one you are adding, you can
- 1:45:10use this equation to measure the
- 1:45:13quality of that tree. This score is
- 1:45:16like the impurity score for evaluating
- 1:45:19decision trees, except that it is
- 1:45:21derived for a wider range of objective
- 1:45:23functions. Okay? So we can use this
- 1:45:28quantity to replace Gini impurity or
- 1:45:33entropy. Because this also tells us
- 1:45:37what the quality of the tree we have
- 1:45:40built is. Now guys, in this similarity
- 1:45:43score that you derived, you can also
- 1:45:46fill in the values of G and H. Okay? If
- 1:45:49you talk about regression. We found out
- 1:45:51just a while ago that G comes out to be
- 1:45:54. Sum of residuals. Okay? G is actually
- 1:46:05not the sum of residuals. Uh, because
- 1:46:08of this summation, sum comes in. But
- 1:46:11yeah, g is basically your residual. And
- 1:46:14h is one, right? And when you do the
- 1:46:20summation over that, it becomes n. Okay
- 1:46:22? Similarly for classification, your g
- 1:46:27will again be the residual that gets
- 1:46:30summed, and h becomes pi*(1-pi); I told
- 1:46:34you this as well. As soon as you put
- 1:46:38both these things into this formula,
- 1:46:41again you will get this. This formula
- 1:46:45for regression, this formula for
- 1:46:47classification. Here we haven't used
- 1:46:49the regularization term. But you can do
- 1:46:52it too. So guys, the similarity score
- 1:46:55is out. Now I will tell you how we use
- 1:46:59this similarity score to do tree
- 1:47:01building. So for a while, assume that
- 1:47:06you have already added t-1 models. You
- 1:47:11have added t-1 models. And now you are
- 1:47:15going to add the t-th model. At time
- 1:47:19step t, okay? And this is a decision
- 1:47:22tree. So how do you build this decision
- 1:47:27tree? It's very simple. You start with
- 1:47:31a single leaf node first. Okay? You
- 1:47:38will have to watch the old video. And
- 1:47:40there you try out all the feature
- 1:47:42values to find out that feature split.
- 1:47:45Okay? After that, for this single leaf
- 1:47:49node, you calculate this quantity. Okay
- 1:47:53? See how, for this single leaf node,
- 1:47:57you can call this quantity qp, as
- 1:48:03parent. Okay? And this will be -1/2,
- 1:48:08think for yourself, what will the value
- 1:48:12of t be here? The value of t here will
- 1:48:15be one. Why? Because we have only one
- 1:48:17leaf node. So basically, there is no
- 1:48:19need to use the summation. We can write
- 1:48:22it here without using the summation, as
- 1:48:25i belongs to Ip. Ip means parent. All
- 1:48:29those rows that are falling into this
- 1:48:31leaf node. Okay? Here, it will be Gi
- 1:48:38squared, i belongs to Ip Hi + λ + Okay
- 1:48:52? So this is our similarity score for
- 1:48:55this leaf node. Now what will happen?
- 1:48:59We will split this leaf node. So after
- 1:49:03splitting, we will get this decision
- 1:49:05tree where this is the structure. Now
- 1:49:08we will have two leaf nodes. Okay? One
- 1:49:13is this and the second one is this. Now
- 1:49:16obviously, if we have done splitting
- 1:49:19and created new nodes, we would want to
- 1:49:23do that because we want to reduce this
- 1:49:26loss further. Right? So now what will
- 1:49:30we do? We will calculate this overall
- 1:49:34loss for this tree structure. Okay? So,
- 1:49:38pay attention to what happens here. We
- 1:49:42will write I am calling this qc for
- 1:49:49child; here it will be -1/2, and this
- 1:49:52inner loop will run twice because the
- 1:49:54value of t is two. There are two leaf
- 1:49:57nodes, this one and this one. So, I am
- 1:50:00expanding it. The first time, we will
- 1:50:04talk about this node. The second time,
- 1:50:07we will talk about this node. So, for
- 1:50:10the left node, our equation will be i
- 1:50:14belonging to I_left, gi squared, all
- 1:50:18those rows that fall into this node. σ
- 1:50:24i belonging to IL hi + λ + gamma t.
- 1:50:33Also, one more thing, here the value of
- 1:50:37this t will be one. So, you can
- 1:50:41actually remove it for the parent. And
- 1:50:46what will happen here? Here, this
- 1:50:52lambda has come. Plus Plus, we will
- 1:51:00write this expression once more. So,
- 1:51:04this would be I belonging to IR GI, now
- 1:51:11we are creating it for this node.
- 1:51:14Divided by σ i belonging to ir +
- 1:51:20lambda + here too there is gamma t. But
- 1:51:25now, instead of t, two will come here.
- 1:51:27Because there are two leaf nodes. So we
- 1:51:29can write it as 2 gamma. Okay? So now I
- 1:51:36have the loss of this parent, and the
- 1:51:43cumulative loss of this child. Now I
- 1:51:49need to find out how much the loss was
- 1:51:52reduced. How much did the loss reduce
- 1:51:54after making this split? So, what will
- 1:51:57I do? I will try to calculate this
- 1:51:59quantity. Parent minus child. Okay? I
- 1:52:06will subtract this from that. And you
- 1:52:10would see that you get. I don't want to
- 1:52:14write the whole thing again. So I will
- 1:52:17just copy this much. And I will paste
- 1:52:27it here. Okay? In fact, this will come
- 1:52:35later. The thing above will come first.
- 1:52:38So, I will quickly erase copy paste.
- 1:52:56Okay? Now, I am keeping this entire
- 1:53:01thing like this between them. Between
- 1:53:05these two, this subtraction will come.
- 1:53:07Okay? So, what will happen with this?
- 1:53:10Let's summarize it once. This minus
- 1:53:13will also make this one negative. So,
- 1:53:16because of that, when you add these two
- 1:53:19, you will get-gamma. Okay? And if you
- 1:53:24talk about these three, they will look
- 1:53:27like this -1/2. I am trying to write
- 1:53:31quickly because all these expressions
- 1:53:33are very lengthy. So it takes a lot of
- 1:53:36time. lambda, this minus minus will
- 1:53:48become + 1/2. Here, it will now become
- 1:54:08plus half. Okay? All of this comes
- 1:54:29together and becomes gamma. Now you can
- 1:54:33see if you rearrange this a bit and
- 1:54:35pull the half out. If you pull the half
- 1:54:39out, you can rearrange and write it
- 1:54:41like this. σi belonging to IL, this
- 1:54:48term GI squared σi belonging to IL hi
- 1:54:55+ lambda plus σi belonging to IR GI²,
- 1:55:05this term divided by i belonging to IR
- 1:55:09hi + lambda minus this term i belonging
- 1:55:16to IR gi squared (i belonging to not r,
- 1:55:25it will be p for parent) hi + lambda
- 1:55:31minus gamma; and This is the difference
- 1:55:39that you are, difference in loss that
- 1:55:42you are getting when you are actually
- 1:55:46doing this split. By doing this split,
- 1:55:50you are getting this much of a gain.
- 1:55:52This is the difference. Okay? And this
- 1:55:55is what you do if you remember, we used
- 1:55:57to do exactly this. We used to make a
- 1:55:59split. We used to calculate the
- 1:56:03similarity score for the parent and
- 1:56:05both children and subtract the child
- 1:56:07ones. Okay? Okay? There, I just didn't
- 1:56:11take this half and didn't consider this
- 1:56:13gamma. Because we were not talking
- 1:56:15about regularization. But this internal
- 1:56:17formula is what we had used. Now if you
- 1:56:24talk about it, you can see this is the
- 1:56:26split criteria. The half came out. The
- 1:56:30IL part plus the IR part minus the
- 1:56:34normal I part minus gamma. Okay? So
- 1:56:38this is the loss reduction after the
- 1:56:41split. I hope you are understanding.
- 1:56:44Okay? So with that, we have understood
- 1:56:48this entire mathematics from scratch.
- 1:56:52We now have justification for
- 1:56:54everything we have done so far. So how
- 1:56:56did you find this video? I know it was
- 1:56:58a very long video and you must be tired
- 1:57:01from studying for sure, and it is
- 1:57:02possible that you might have doubts in
- 1:57:04some places. But trust me, this video
- 1:57:07is created in such a way that if you go
- 1:57:09back and watch it again, and make your
- 1:57:11own notes, then things will stick in
- 1:57:13your mind and you will be able to
- 1:57:15retain it. Okay? So a lot of hard work
- 1:57:17went into making this video. So please,
- 1:57:20if you liked it, do like it, and if you
- 1:57:22haven't subscribed to this channel,
- 1:57:23please do subscribe. See you in the
- 1:57:25next video. Bye.
About this transcript
This page contains the full transcript of The Maths Behind XGBoost | Machine Learning | CampusX by CampusX, generated from the public captions YouTube serves with the video. The transcript has 13,892 words across 1,911 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.
What you can do with it
Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to choose a caption track available on the video.
Free YouTube transcript tool
YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, caption language selection, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.