YouTube2Text

The Maths Behind XGBoost | Machine Learning | CampusX — Transcript

by CampusX · 13,892 words · 1,911 segments · language en · Watch on YouTube

Full transcript

  1. 0:00Hi guys, my name is Nitesh and welcome
  2. 0:02to my YouTube channel. In this video,
  3. 0:05we are going to cover the in-depth
  4. 0:07mathematics of XGBoost. So if you have
  5. 0:09been following all the videos, I have
  6. 0:11already posted three videos on XGBoost.
  7. 0:14In the first video, I covered the
  8. 0:15introduction. In the second video, I
  9. 0:17showed how XGBoost is applied to
  10. 0:19regression. I demonstrated that. And in
  11. 0:22the third video, we covered how XGBoost
  12. 0:24is applied to classification problems.
  13. 0:27But in all three videos, I hadn't
  14. 0:29discussed any math at all. So that is
  15. 0:31exactly what we will cover in this
  16. 0:33video. In this video, we will go very
  17. 0:36deep and understand the entire
  18. 0:37mathematical formulation from scratch.
  19. 0:40We will try to understand where all the
  20. 0:43formulas came from. Let me tell you why
  21. 0:45you should watch this video. XGBoost is
  22. 0:49undoubtedly the most powerful algorithm
  23. 0:51in the machine learning space today.
  24. 0:54Take any problem involving tabular data
  25. 0:56, and most likely, you will be using
  26. 0:58XGBoost there. So, if you are going to
  27. 1:01become a data scientist or let's say
  28. 1:04you are a data scientist, you should
  29. 1:06have a very clear picture of XGBoost's
  30. 1:09mathematics. This video will provide
  31. 1:12you with exactly that. In a very
  32. 1:14in-depth, detailed, step-by-step
  33. 1:17approach, we will refer to the research
  34. 1:21paper to cover all the mathematics. No
  35. 1:25doubt, the video is a bit long. But
  36. 1:27that is because I made a conscious
  37. 1:29decision not to skip anything and to
  38. 1:32show you everything by writing and
  39. 1:35deriving it. So this is just for the
  40. 1:38hardcore data science fans. So now, I
  41. 1:41won't bore you any further. Let's start
  42. 1:43the video. So you must have understood
  43. 1:46that in this video, we are going to
  44. 1:48cover the detailed mathematics of
  45. 1:49XGBoost. But before starting the video,
  46. 1:52I want to tell you exactly what we are
  47. 1:54going to study in the mathematics
  48. 1:55section. If you have followed all the
  49. 1:58previous XGBoost videos, you would know
  50. 2:00that we have already posted three
  51. 2:02videos on this channel. In the first
  52. 2:05video, we did a detailed introduction
  53. 2:09to the XGBoost algorithm. In video
  54. 2:13number two, we focused specifically on
  55. 2:16regression and how XGBoost solves a
  56. 2:18regression problem. Then in video
  57. 2:22number three, we discussed how XGBoost
  58. 2:25works on classification problems. So,
  59. 2:30if you have watched both these videos,
  60. 2:33you might remember that the common
  61. 2:36thing in both regression and
  62. 2:38classification problems was that we
  63. 2:41used to build a decision tree that was
  64. 2:44slightly different from regular
  65. 2:46decision trees. Right? In XGBoost, your
  66. 2:50decision tree is different from a
  67. 2:52normal decision tree. In two aspects,
  68. 2:55the first aspect is that in a normal
  69. 2:59decision tree, when you construct a
  70. 3:02node, you calculate quantities like
  71. 3:06entropy and Gini index. But in XGBoost
  72. 3:10trees, instead of using these two, you
  73. 3:13calculate a completely different
  74. 3:15quantity, which we call the similarity
  75. 3:18score. Right? And if you focus here,
  76. 3:23you will find the formula to calculate
  77. 3:26the similarity score for regression and
  78. 3:29to calculate the similarity score for
  79. 3:32classification. Right? So, I introduced
  80. 3:36both these formulas in those two videos
  81. 3:39. I did not give you any mathematical
  82. 3:42background, and I told you that just
  83. 3:43trust me, this is the formula we have
  84. 3:45to use. But in today's video, we will
  85. 3:48go into great detail to understand
  86. 3:50where these two formulas came from. The
  87. 3:54second point of difference between an
  88. 3:56XGBoost tree and a normal decision tree
  89. 3:59is that the method to calculate the
  90. 4:02decision tree output is different; the
  91. 4:04normal one and the XGBoost one have
  92. 4:07different formulas for calculating the
  93. 4:10leaf node output. And again, if you
  94. 4:13focus here, this is the formula to
  95. 4:16calculate the output value for any leaf
  96. 4:18node in the case of regression. And
  97. 4:22this is the formula to calculate the
  98. 4:24output of any leaf node in the case of
  99. 4:26classification. And again, I introduced
  100. 4:29both these formulas in those two videos
  101. 4:31. And once again, I did not tell you
  102. 4:33where they came from. So, in today's
  103. 4:36video, we will look behind these as
  104. 4:38well and try to understand how these
  105. 4:40two formulas came into existence. Right
  106. 4:43? So, in short, in today's video, we
  107. 4:47are going to do a deep dive into the
  108. 4:50mathematics of XGBoost, and our goal
  109. 4:53will be to understand where these four
  110. 4:57formulas came from. I will give you the
  111. 5:01answer to every "why." And trust me, if
  112. 5:03you understand this video well, you
  113. 5:06will have such foundational knowledge
  114. 5:08of XGBoost that you will be able to
  115. 5:11apply XGBoost to any problem very
  116. 5:13effectively in the future. Right? Also,
  117. 5:16before starting the video, I want to
  118. 5:18give one more disclaimer. So when I was
  119. 5:22researching for this video, I noticed
  120. 5:24that there isn't much content available
  121. 5:26on the internet. In a few places,
  122. 5:29people have explained how the
  123. 5:31mathematics of XGBoost works. But I
  124. 5:33noticed some mistakes in them. So that
  125. 5:37is why for this video, I have
  126. 5:39specifically used the research paper of
  127. 5:41XGBoost. So whatever mathematics I
  128. 5:45explain to you in this entire video is
  129. 5:47basically in these two pages. Page
  130. 5:50number two and page number three. Okay?
  131. 5:53So things will be factually correct and
  132. 5:56the good part is that you will be able
  133. 5:58to go back and read this XGBoost paper
  134. 6:01too. Okay? So with that, I guess I gave
  135. 6:03you a clear plan of attack. Now let's
  136. 6:05start the video. Also, one more thing,
  137. 6:09if you are feeling a bit scared that
  138. 6:11this video about mathematics will be
  139. 6:13very difficult, then I have a
  140. 6:15suggestion for you to study a few
  141. 6:18things before watching this video.
  142. 6:21After that, this video will seem easy
  143. 6:22to you. What do you need to study?
  144. 6:26First of all, the two videos I uploaded
  145. 6:29before this on XGBoost, the regression
  146. 6:31video and the classification video. You
  147. 6:36must watch these videos, only then will
  148. 6:38you understand things. Apart from this,
  149. 6:41you should have some idea about
  150. 6:43gradient boosting. Because XGBoost is
  151. 6:47just optimizations over gradient
  152. 6:50boosting. So if you know gradient
  153. 6:52boosting, it will become much easier to
  154. 6:54understand. And obviously, you should
  155. 6:57know the basic concepts of decision
  156. 7:00trees. How a tree is built, how the
  157. 7:02output value is calculated? You should
  158. 7:05know all of this. If your foundation is
  159. 7:07clear to this extent, trust me, you
  160. 7:09won't have much trouble understanding
  161. 7:11this video. So guys, at the very
  162. 7:15beginning, I want to give you a short
  163. 7:17quick revision of how boosting models
  164. 7:20like XGBoost or gradient boosting work.
  165. 7:24Although I have told you this multiple
  166. 7:26times. But let's have a quick revision
  167. 7:28once. So as you know that boosting
  168. 7:32models like gradient boosting or
  169. 7:35XGBoost or for that matter, other
  170. 7:37boosting algorithms you will study
  171. 7:40later, they are all additive models.
  172. 7:44Additive models mean that in a
  173. 7:46stage-wise fashion, one after the other
  174. 7:52you keep adding models to your existing
  175. 7:55ensemble. So in stage one, you have
  176. 7:58this model M1. Okay? It made some
  177. 8:02mistakes on your data. You train this
  178. 8:06model M2 on those mistakes and then you
  179. 8:09combine these two to make a prediction.
  180. 8:15Then the combination of these two will
  181. 8:17also make some mistakes. So, you
  182. 8:19propagate that error towards the third
  183. 8:22model. The third model trains, and then
  184. 8:25you combine these into an ensemble to
  185. 8:27make a prediction, and in this way, you
  186. 8:30can add as many models as you want. I
  187. 8:34guess you are aware of this. All right?
  188. 8:36So, here, to explain this point a bit
  189. 8:39better, I am taking an example. Like,
  190. 8:43suppose you have this data of students
  191. 8:45where you have CGPA and IQ as input,
  192. 8:47and this is your output, which is the
  193. 8:49value of their package. So, what did we
  194. 8:53do? We applied XGBoost on this. And we
  195. 8:59already decided that we will build two
  196. 9:02models. The first and the second. Now,
  197. 9:06generally, the first model is a base
  198. 9:09model. And in the case of regression,
  199. 9:14this could be the mean of the output
  200. 9:18column. So, we basically took the mean
  201. 9:22of all three. This is your first model.
  202. 9:24This, this is your m1. All right? Now,
  203. 9:27obviously, M1 will make some mistakes.
  204. 9:29You are saying for this student too,
  205. 9:31the package should be 14.5. For this
  206. 9:33one too, you are saying it should be
  207. 9:3514.5. And for this one too, you are
  208. 9:37saying it must be 14.5. So, obviously,
  209. 9:39there are errors, there are mistakes.
  210. 9:41So, now what will you do? You will take
  211. 9:45your input and this difference, these
  212. 9:49mistakes, this error, you will take
  213. 9:53them and use this data to train M2 in
  214. 9:57stage two, which is nothing but a
  215. 10:01decision tree. All right? Now, for a
  216. 10:06moment, assume that this is the
  217. 10:07decision tree you built. All right? If
  218. 10:09CGPA is less than six, then this
  219. 10:11happens; if IQ is less than 100, then
  220. 10:13this happens. All right? And you have
  221. 10:17trained this. All right? Now the
  222. 10:21question is, if tomorrow a new student
  223. 10:25comes, suppose their CGPA is nine and
  224. 10:29their IQ is 100 or 102, then how will
  225. 10:33we calculate their output? How will we
  226. 10:37calculate y-hat to find out what their
  227. 10:39package will be? It is very simple. We
  228. 10:42will send this input data into this
  229. 10:45combination of m1 + m2. So, what output
  230. 10:49will m1 give? 14.5 plus what output
  231. 10:53will m2 give? Since it is a decision
  232. 10:55tree. You will ask it a question. Is
  233. 10:58CGPA less than six? No, it is nine. All
  234. 11:04right? So, if you consider this as yes
  235. 11:09and this as no, then you will directly
  236. 11:13add 2.1 and say that 16.6 should be the
  237. 11:18package. So, this is how you find out
  238. 11:23predictions in the case of boosting.
  239. 11:28All right? So, if you talk in a
  240. 11:31strictly mathematical sense, all these
  241. 11:34models are nothing but mathematical
  242. 11:37functions; if you think about it, I can
  243. 11:40actually write this one as f1x or f1xi,
  244. 11:43we will calculate it for each data
  245. 11:46point, and we can call this f2xi. Even
  246. 11:50though this is a decision tree, it is
  247. 11:52still a function; you give it some
  248. 11:53input. It gives you some output. Now,
  249. 11:56to calculate that output, it is using
  250. 11:58if-else statements. But that doesn't
  251. 11:59matter, it is still a function. So, if
  252. 12:02you have a lot of such functions, then
  253. 12:04this last one will become fn xi. So, in
  254. 12:09short, what I mean to say is that the
  255. 12:11output calculated in boosting can be
  256. 12:13written in a compact mathematical form.
  257. 12:17If you have n models, like there are
  258. 12:22two here. Suppose we had n models, then
  259. 12:25we would write this entire expression
  260. 12:26like this. f1 xi + f2 xi + dot dot dot
  261. 12:33+ fn xi, or we could write it as sum
  262. 12:40from i = 1 to n fi xi; this is the
  263. 12:49formula for the output of a boosting
  264. 12:53algorithm like XGBoost. I hope you have
  265. 13:01understood. Now guys, we have
  266. 13:04understood that you can explain the
  267. 13:07output of a boosting model in terms of
  268. 13:11the sum of functions. But one thing
  269. 13:15that isn't clear is how the output
  270. 13:18values of these leaf nodes of this
  271. 13:21decision tree, these three leaf nodes,
  272. 13:24were calculated. Now, if you have
  273. 13:32watched the previous two videos, I told
  274. 13:35you there that if you talk about
  275. 13:37regression, since this is a regression
  276. 13:39problem. So, if you talk about
  277. 13:43regression, then the formula to
  278. 13:45calculate the output of the decision
  279. 13:48tree in the case of regression is Sum
  280. 13:55of residuals divided by number of
  281. 14:02residuals plus lambda. Okay? For
  282. 14:06example, suppose you have to calculate
  283. 14:08the output of this particular leaf node
  284. 14:10. Then first of all, you will find out
  285. 14:12which of these data points will fall
  286. 14:13into this particular leaf node. Okay?
  287. 14:24You can see that only this data point
  288. 14:25will fall here. Right? Because less
  289. 14:32than CGPA 5 is only in this row. So
  290. 14:33here, what you will do is you will
  291. 14:35write down the residual or error
  292. 14:36corresponding to this point, divided by
  293. 14:37the number of residuals, which is one.
  294. 14:40Plus whatever your lambda value is, you
  295. 14:45will put it in, and that will be your
  296. 14:50output value. Similarly, what will you
  297. 14:55do for this one? Similarly, you will do
  298. 14:58the same for this one as well. For this
  299. 15:01node as well, you will find out which
  300. 15:04points fall into this node. Like right
  301. 15:09now, I can see this particular point.
  302. 15:12So for this too, you will apply the
  303. 15:14same formula. And similarly for this
  304. 15:16one also. But in this video, we need to
  305. 15:19understand where this formula came from
  306. 15:22. What is the origin story of this
  307. 15:25formula? That is what we will try to
  308. 15:29understand. Moving forward, given an
  309. 15:32XGBoost tree, how do you find the leaf
  310. 15:36weights? By the way, the output of a
  311. 15:41leaf node is also called a leaf weight.
  312. 15:46So we are trying to figure out how this
  313. 15:49formula came to be. Okay? Now, how is
  314. 15:53this formula derived? I will first
  315. 15:56explain the thought process behind it.
  316. 15:58Okay? Based on the discussion so far,
  317. 16:03you have understood that in our overall
  318. 16:06combined model, where we have two
  319. 16:08models, m1 and m2, their combined
  320. 16:11output, which we will call yi-hat, will
  321. 16:14be m 1's output plus m 2's output.
  322. 16:17Right? And I told you a while ago that
  323. 16:20we can mathematically write this in
  324. 16:22terms of functions. So let's say we are
  325. 16:25calling m1 f1 (xi) + m2, which is this
  326. 16:28decision tree. We are calling this f2.
  327. 16:32(xi). Okay? Now we know that the output
  328. 16:36of f1 (xi) is always 14.5. We need to
  329. 16:40find the output of f2 (xi). Okay? The
  330. 16:44interesting thing is that we have to
  331. 16:47calculate three output values. Okay?
  332. 16:49You have to remember that f2 (xi)
  333. 16:52doesn't have a single output value.
  334. 16:55There will be three different output
  335. 16:56values. One for this leaf node, one for
  336. 16:59this leaf node, and one for this leaf
  337. 17:01node. So we need to calculate all three
  338. 17:03. So basically, if this decision tree
  339. 17:06had five leaf nodes, we would have to
  340. 17:08find five values for this f2 (xi). Okay
  341. 17:12? Anyway. Now we have the formula for
  342. 17:18yi-hat. Okay? We need to find out what
  343. 17:30the value of f2 (xi) will be. Okay? So
  344. 17:34let's try to think once about what the
  345. 17:38value should be. If you have studied
  346. 17:42machine learning enough and read about
  347. 17:45the algorithms, you should always know
  348. 17:49that the only job of your algorithm's
  349. 17:52prediction is to get closer to reality.
  350. 17:56And what is reality? yi, which is the
  351. 17:59actual package of the kids in your data
  352. 18:01. You will always want to do one thing.
  353. 18:05You will want to reduce the gap between
  354. 18:09yi and yi-hat. Right? So basically, we
  355. 18:15need a value in f2 xi such that for
  356. 18:20every data point, the difference
  357. 18:24between these two quantities is reduced
  358. 18:30. Okay? Now, that is why it is very
  359. 18:36important that you first write down the
  360. 18:39relationship between yi and yi hat. And
  361. 18:46I guess even a beginner knows what we
  362. 18:49call the relationship between yi and yi
  363. 18:53hat? Loss function. A loss function is
  364. 19:00a mathematical function that
  365. 19:03establishes a relationship between yi
  366. 19:07and yi hat, and our goal in machine
  367. 19:11learning is to minimize this loss
  368. 19:14function. Like in the case of
  369. 19:19regression, we studied a very famous
  370. 19:21loss function. Mean Squared Error,
  371. 19:24whose formula is this. I hope you
  372. 19:41remember this from linear regression.
  373. 19:44So now, if we need to find this value,
  374. 19:49then we need to find a value that will
  375. 19:56minimize the loss function. I think
  376. 19:58you've understood this much. Now, the
  377. 20:01only question that arises is, what is
  378. 20:04the loss function in the case of
  379. 20:07XGBoost? What is the loss function? If
  380. 20:10we get the loss function, then in the
  381. 20:14process of minimizing that loss
  382. 20:17function, I will find this f2 xi. Okay?
  383. 20:21So first, I will show you the loss
  384. 20:24function used in Gradient Boosting, and
  385. 20:29then after that, I will show you the
  386. 20:32XGBoost loss function. So Gradient
  387. 20:36Boosting is one algorithm which is very
  388. 20:39, very flexible. I told you while
  389. 20:45teaching Gradient Boosting that
  390. 20:47Gradient Boosting is so flexible that
  391. 20:50it accepts any type of loss function,
  392. 20:52provided it is differentiable. Meaning,
  393. 20:56you should be able to differentiate
  394. 20:57that loss function. Because
  395. 20:58differentiating is necessary since you
  396. 21:00will perform optimization. So for that,
  397. 21:03you need a differentiable loss function
  398. 21:04. One such differentiable loss function
  399. 21:07is Mean Squared Error, which I just
  400. 21:09showed you. So if you talk about
  401. 21:11Gradient Boosting, then there isn't
  402. 21:13actually any specific loss function in
  403. 21:15Gradient Boosting. In Gradient Boosting
  404. 21:17, the loss function is often
  405. 21:19represented in this way. That's it. If
  406. 21:23you see this written, then this is the
  407. 21:25Gradient Boosting loss function. Now,
  408. 21:27you can put any mathematical function
  409. 21:29into this. You can also put Mean
  410. 21:32Squared Error. You can also put Log
  411. 21:34Loss. You can also put any other loss
  412. 21:36function. It just needs to be
  413. 21:38differentiable. But the XGBoost loss
  414. 21:42function looks a bit different,
  415. 21:44slightly different. And as I told you
  416. 21:50in the first video of XGBoost, the loss
  417. 21:54function of XGBoost has a
  418. 21:56regularization parameter by default.
  419. 22:05Right? So now, I will show you what the
  420. 22:09XGBoost loss function looks like. Now,
  421. 22:12if you go to the original XGBoost paper
  422. 22:16, you will see this. And this is the
  423. 22:21loss function of XGBoost. Right? So
  424. 22:24first, I will write it down. Then I
  425. 22:27will explain to you what this loss
  426. 22:28function indicates. So in our case,
  427. 22:31since there are two models m1 + m2,
  428. 22:34here m1 is a base model and m2 is a
  429. 22:38decision tree. So our loss function
  430. 22:45will be σ i = 1 to n for all data
  431. 22:51points l yi yi hat plus this omega term
  432. 22:58on f2 xi Right, now it is explained
  433. 23:07here what this omega of f is. Right? By
  434. 23:11the way, this term is only applicable
  435. 23:15to your last decision tree. So, it is
  436. 23:19actually made of two terms. Right? So
  437. 23:22it is actually gamma times T + 1/2
  438. 23:29lambda times w². Right? Let me explain
  439. 23:36all these things to you once. So here,
  440. 23:39this T is the number of leaf nodes in
  441. 23:46your decision tree. Like in our case,
  442. 23:49one, two, three, these are our number
  443. 23:53of leaf nodes. So here, the value of t
  444. 23:56will be three. And what is this W? This
  445. 24:00W is the weight or output of these
  446. 24:03leaves. Like this is W1. This is W2.
  447. 24:07This is W3. Right? And this gamma is a
  448. 24:12regularization parameter, and this
  449. 24:16lambda is also a regularization
  450. 24:19parameter. Right? Basically, you want
  451. 24:23to penalize your tree for having too
  452. 24:27many leaf nodes and having very high
  453. 24:30output values. That's the whole idea
  454. 24:33behind this entire loss function. Right
  455. 24:37? You can compare it side-by-side with
  456. 24:40gradient boosting. In gradient boosting
  457. 24:42, this loss function would just be this
  458. 24:44. That's it. This term would not be
  459. 24:53there. So, the biggest difference you
  460. 24:57can see so far in XGBoost is this. That
  461. 25:01this loss function is different. It
  462. 25:04comes with a built-in regularization
  463. 25:06parameter. Right? So, now if I tell you
  464. 25:12what W1, W2, and W3 should be? Then in
  465. 25:20very simple words, we need values for
  466. 25:23W1, W2, and W3 that will minimize this
  467. 25:27loss function. And that's the whole
  468. 25:32idea. And now we have entered the
  469. 25:34domain of optimization, which is a
  470. 25:37somewhat familiar territory. You have
  471. 25:39studied this in gradient descent and
  472. 25:41also in linear regression. And in many
  473. 25:44other algorithms, you have explored how
  474. 25:46to find values for specific parameters
  475. 25:49by minimizing the loss function. Okay?
  476. 25:52So, moving forward, we are going to
  477. 25:55apply all this same mathematics. Before
  478. 25:57moving ahead, I would like to clarify
  479. 26:00one thing. Until now, what I was doing
  480. 26:04was calling this thing a loss function.
  481. 26:09Okay? I was calling this complex term a
  482. 26:11loss function. But actually, you don't
  483. 26:14call it a loss function. You actually
  484. 26:17call it an objective function. This is
  485. 26:22called an objective function. Because
  486. 26:26this is a sum of two things. First,
  487. 26:29your loss function, And second, your
  488. 26:35regularization term. Okay? So, going
  489. 26:40forward, we will call it an objective
  490. 26:42function. Wherever you read about it,
  491. 26:43it will be called an objective function
  492. 26:45. I might accidentally call it a loss
  493. 26:47function again. But you understand the
  494. 26:49sentiment. Okay? Now, I want you to get
  495. 26:53comfortable with this objective
  496. 26:56function. It is very, very important
  497. 26:59that you get a bit comfortable with
  498. 27:01what is written on the screen right now
  499. 27:03. So, what am I going to do? I will
  500. 27:06show you this objective function
  501. 27:08through two or three different examples
  502. 27:10. Okay? So, let's assume we are
  503. 27:14building three or four different models
  504. 27:18. Suppose we have a dataset. Any
  505. 27:23dataset, and we performed boosting on
  506. 27:26it using XGBoost. Now you know what you
  507. 27:30do in boosting. You keep adding models
  508. 27:33one after another in a stage-wise
  509. 27:34fashion. One model in the first stage,
  510. 27:37two models in the second stage, three
  511. 27:40models in the third, and so on. Now,
  512. 27:43assume that when you first applied
  513. 27:46XGBoost on it, you decided that, no, I
  514. 27:50will use only one model. So there will
  515. 27:54be only one model. So, I want to show
  516. 27:58you what this objective function would
  517. 28:00look like if there were only a single
  518. 28:02model. By the way, you know that the
  519. 28:05first model in XGBoost is not a
  520. 28:07decision tree. It is simply the mean.
  521. 28:10This is just a constant. So let's
  522. 28:13assume we have a single model. This is
  523. 28:16m1; mathematically, we can call it f1
  524. 28:20xi. So, for this, our objective
  525. 28:24function becomes sigma i = 1 to n for
  526. 28:28all the data points. Loss function is
  527. 28:33yi. yi hat, that's it; this term does
  528. 28:39not come because what is this term?
  529. 28:42This term is this thing. Right? What is
  530. 28:48T in this? Number of leaf nodes. And
  531. 28:51what is W? Leaf weights. Now think
  532. 28:54about it yourself. If you have just one
  533. 28:56model and it is only a mean model. This
  534. 28:59is not even a decision tree, so you
  535. 29:02wouldn't write this for that. I hope
  536. 29:05you are understanding the point. Now
  537. 29:07let's take a second case. The second
  538. 29:10case is that this time we are taking
  539. 29:13two models. We are taking two models.
  540. 29:17This is m1, which is again mean, and we
  541. 29:21are taking m2, which is a decision tree
  542. 29:25. Okay? And mathematically we are
  543. 29:28writing this as f1. xi and we are
  544. 29:32representing this as f2 xi. How will
  545. 29:36our objective function look in this
  546. 29:39case? Our objective function will look
  547. 29:41like this. yi, by the way, we can write
  548. 29:49yi hat as this. Right? So what am I
  549. 29:58doing? Here, rather than writing yi hat
  550. 30:03, I am writing f1 xi + f2 xi, okay? +
  551. 30:09omega of f2 xi. Why only f2xi? Because
  552. 30:16only f2xi is a decision tree. Okay,
  553. 30:21anyway, this is stage two. This is
  554. 30:25stage two, this was stage one. So since
  555. 30:31this new model has been added and since
  556. 30:34this is a decision tree, your
  557. 30:36regularization term will only apply to
  558. 30:39F2. It will not apply to F1. Okay?
  559. 30:43Let's take one more iteration. Let's
  560. 30:46add one more model. So we are moving on
  561. 30:49to stage three. In stage three, we have
  562. 30:52three models. This is the first one.
  563. 30:55This is the second one. This is the
  564. 30:57third one. So this is model one. This
  565. 31:00is model two. This is model three. This
  566. 31:03is again just a mean. This is a
  567. 31:06decision tree. This is also a decision
  568. 31:10tree. Okay? Mathematically, we are
  569. 31:14calling it f1xi, f2xi, f3xi, and now I
  570. 31:21would like you to imagine what the
  571. 31:24objective function will be. The
  572. 31:28objective function will be this. yi f1
  573. 31:38xi + f2 xi + f3 xi + f3 xi, why did I
  574. 31:52add only f3xi? Because the
  575. 31:56regularization up to here has already
  576. 32:01been handled in this step. Okay? Now,
  577. 32:05since this new decision tree has been
  578. 32:07added. That is why we are applying
  579. 32:11regularization on it. Okay? I hope
  580. 32:14things are clear up to here. One last
  581. 32:19example, we are at stage T. We don't
  582. 32:26know how many iterations have passed.
  583. 32:27How many models we have added. We don't
  584. 32:29know. We just know that now we have T
  585. 32:31models. T could be 100, or it could be
  586. 32:341000. We don't know anything. So now we
  587. 32:37have T models. We have T models. This
  588. 32:45is M1, this is M2, this is MT. This is
  589. 32:50mean, this is decision tree. In between
  590. 32:54are all decision trees, and this is
  591. 32:56also a decision tree. Let's call this
  592. 33:00one f1 xi, f2 xi, ft xi, and now I
  593. 33:03would like you to think, what would be
  594. 33:08the objective function? So, the
  595. 33:12objective function will be from i = 1
  596. 33:14to n. By the way, we can do one more
  597. 33:18thing. We can introduce a notation.
  598. 33:21Here, we can write one to represent
  599. 33:23this is the objective function of stage
  600. 33:24one. Here, we can write the objective
  601. 33:27function of stage two. Here, we can
  602. 33:30write the objective function of stage
  603. 33:32three. And similarly, we can write the
  604. 33:34objective function of stage t. So here
  605. 33:38we will have yi, f1 (xi) + f2 (xi) +
  606. 33:50dot dot dot + ft (xi). The very last
  607. 33:57plus, you always focus on your last
  608. 34:00decision tree, so here we will have (ft
  609. 34:03) xi. This will be the loss function,
  610. 34:07or I am sorry, this will be the
  611. 34:09objective function at stage t. Right.
  612. 34:13Now I am going to do one thing; I am
  613. 34:17going to simplify this entire term a
  614. 34:21bit. How? Pay attention, so I would
  615. 34:24rewrite it as yi, yi hat till stage t-1
  616. 34:38+ ft (xi) + ft. Basically, what I did
  617. 34:48is that I took (f1xi) + f2xi dot dot
  618. 34:55dot f (t-1) xi, replaced this whole
  619. 35:03thing with this term. yi hat till stage
  620. 35:08t-1 And we can write it like this,
  621. 35:13right? If we were at the t-1 stage, its
  622. 35:16yi hat would be this value, wouldn't it
  623. 35:19? So basically, I simplified it and I
  624. 35:23can say that, "At any stage t, the
  625. 35:32objective function of XGBoost can be
  626. 35:36written as sigma i = 1 to n (for all
  627. 35:40the data points): l (yi, yi hat till t-
  628. 35:511 stage +) ft (xi) + omega of ft (xi)"
  629. 35:56and I did all this hard work only
  630. 36:01because I want to show you that in this
  631. 36:06research paper, they have also written
  632. 36:12the t-th stage objective function
  633. 36:17exactly the way we have written it. You
  634. 36:22can see, now what do we need to do? We
  635. 36:26need to find such an output value for
  636. 36:28this fxi, which is the last decision
  637. 36:37tree, that will minimize this entire
  638. 36:44objective function. That is the goal.
  639. 36:46We have to find such a value of ftxi or
  640. 36:49this decision tree or the output of
  641. 36:53this leaf so that this entire objective
  642. 36:56function is minimized. This is our goal
  643. 36:59at this point of time. So, we have
  644. 37:02established our objective function and
  645. 37:04we have also established our goal. We
  646. 37:08basically need a value for ftxi that
  647. 37:11will minimize this entire objective
  648. 37:14function. So essentially, we have
  649. 37:19turned this whole problem into an
  650. 37:21optimization problem. And the good part
  651. 37:25is that we are already very comfortable
  652. 37:28with solving such optimization problems
  653. 37:31. Right? My question to you would be,
  654. 37:36have you ever solved an optimization
  655. 37:38problem like this? Where you need the
  656. 37:42values of parameters that minimize a
  657. 37:44loss function or an objective function.
  658. 37:47The answer should be yes. I mean, if
  659. 37:52you have studied linear regression,
  660. 37:54then if you remember, we used to have
  661. 37:57an objective function or a loss
  662. 37:58function there. Which was this. And,
  663. 38:10the actual loss function there, which I
  664. 38:13have written in a general form right
  665. 38:15now, was mean squared error, which you
  666. 38:18could also write as: (yi-yi hat)
  667. 38:20squared. Okay, now for a moment, assume
  668. 38:25that you are applying linear regression
  669. 38:28on this data. You have an input column
  670. 38:32called experience and you have to
  671. 38:34calculate salary, so this is your input
  672. 38:37and this is your output. Okay? So, What
  673. 38:43was yi here? What was yi hat? Like, yi
  674. 38:46is this. yi hat used to be m times
  675. 38:52experience of the ith candidate + b,
  676. 38:57right? So in a way, I was able to write
  677. 39:01this loss function like this too. yi-I
  678. 39:09can also call experience i as xi here.
  679. 39:12Because this is the input. Right? And
  680. 39:18if you remember, our task used to be
  681. 39:21that we needed such values of m and b
  682. 39:24for which this loss is minimum. This is
  683. 39:30like basic linear regression. Okay? And
  684. 39:34then what did we do? We used to plot a
  685. 39:37graph. Where one axis had m, one axis
  686. 39:41had b, and the vertical axis had our
  687. 39:44loss value. Okay? We used to try
  688. 39:47different values of m and b and plot
  689. 39:50the loss. Now, since this is a
  690. 39:54quadratic equation type. So, if you
  691. 39:57remember, this used to be our loss
  692. 39:59function. Here, this is the cost or
  693. 40:03loss. On this axis, you have m. On this
  694. 40:06axis, you have b. Okay? As soon as we
  695. 40:09find out that there is such a lovely
  696. 40:11parabolic shape. And now we have to
  697. 40:14find such values of M and B for which
  698. 40:17the loss is minimum. We know it will
  699. 40:21always be at the point where the loss
  700. 40:25with respect to both, the slope and the
  701. 40:30intercept, is zero. So what did we used
  702. 40:34to do? We used to differentiate our
  703. 40:37loss function. Once with respect to m,
  704. 40:41and by setting it to zero, we would
  705. 40:43find the value of m. And once by
  706. 40:45differentiating with b, we would find
  707. 40:48the value of b. And basically, we would
  708. 40:51get such a value of m and b. That would
  709. 40:54minimize this loss. And this is where
  710. 40:57we used techniques like gradient
  711. 40:59descent. Right? So in short, I just
  712. 41:03want to tell you that we have solved
  713. 41:05this kind of optimization problem
  714. 41:08before. But what if I tell you that
  715. 41:13this particular optimization problem is
  716. 41:19a tough nut to crack or is very
  717. 41:21difficult to solve. So would you agree?
  718. 41:26Let me give you my argument as to why I
  719. 41:30think optimizing this is...In this way,
  720. 41:34the method I just explained, in the
  721. 41:37linear regression case, our 'l' is this
  722. 41:41. In linear regression, m and b were
  723. 41:45our parameters, which are these here.
  724. 41:48Right? But the job is the same. But why
  725. 41:52am I saying that optimizing this is
  726. 41:54much more difficult? The reason is that
  727. 42:00if you understand, what is yi-hat in
  728. 42:04both places? In the case of linear
  729. 42:07regression, yi-hat is a very simple
  730. 42:09thing. It is mx + b, okay? If you try
  731. 42:16to draw it, if this is your experience
  732. 42:19and this is your salary, and if this is
  733. 42:24your data, then your 'yi-hat' is
  734. 42:27basically this line, it's a simple
  735. 42:30curve. But if you talk about our
  736. 42:35decision tree thing, then here what is
  737. 42:41'yi-hat'? First of all, 'yi-hat' is
  738. 42:46yi-hat at time t-1 + ft xi, you can see
  739. 42:51that. This entire term is our yi-hat,
  740. 42:55right? Now, if you talk about this term
  741. 43:00, it is a constant, but if you talk
  742. 43:02about this term, it is a decision tree,
  743. 43:05okay? So this means that if we had the
  744. 43:11same data, experience here, salary here
  745. 43:15, and these were our data points, then
  746. 43:19the 'yi-hat' curve would look something
  747. 43:23like this. It would look something like
  748. 43:27this. I am not sure if I will be able
  749. 43:32to draw this or not. Basically, if you
  750. 43:38have studied decision trees for
  751. 43:41regression, you would know that in this
  752. 43:44way the entire regression happens. In
  753. 43:51the case of suppose this was the data.
  754. 43:58Then in this case, it would look
  755. 44:01something like this. Something like
  756. 44:07this. What I am trying to tell you is
  757. 44:10that unlike the linear regression case,
  758. 44:12this won't be a simple line. In our
  759. 44:16case, it would be a zigzag curve, a
  760. 44:20curve like this. Okay? Why? Because the
  761. 44:25output of decision trees is actually
  762. 44:28like this. Okay? Okay? If I can show
  763. 44:32you, so I would just search for a
  764. 44:36decision tree regression graph just to
  765. 44:41show you, because I am not able to draw
  766. 44:45it correctly. So yeah, this is what I
  767. 44:49wanted to show you. You can see, if
  768. 44:52this were linear regression here. I
  769. 44:54will just cut this diagram and I will
  770. 44:57just show you what I am trying to say.
  771. 45:03Where did it go? Here it is. So if this
  772. 45:07were normal linear regression, a line
  773. 45:10would be drawn like this. Right? But
  774. 45:14since this is a decision tree or a set
  775. 45:17of decision trees. Then its graph will
  776. 45:21look like this. Like this. And it will
  777. 45:25look like this because if you have
  778. 45:27watched my decision tree class, then I
  779. 45:30had mentioned there that its output is
  780. 45:32piecewise constant. Meaning, in this
  781. 45:35area, it is a constant value. Then at
  782. 45:38the very next moment, it is this value.
  783. 45:40At the previous moment, it was that
  784. 45:42value. There are sudden jumps. There
  785. 45:44are sudden jumps. Okay? So because our
  786. 45:48yi hat is such a weird curve. Because
  787. 45:55of that, when we try to plot the graph
  788. 45:58of loss with yi hat, we will not get
  789. 46:01such a smooth parabolic curve. There is
  790. 46:05a good chance that we might get a curve
  791. 46:07like this. It is perhaps a parabola,
  792. 46:11but with many irregularities; imagine
  793. 46:15this in 3D. Okay? So because the
  794. 46:19parabola is formed in this way.
  795. 46:25Optimizing this will not be easy. Why?
  796. 46:28Because at many points this curve is
  797. 46:35not even differentiable. So basically,
  798. 46:39you cannot even apply this partial
  799. 46:44differentiation. You cannot even reach
  800. 46:46this point because you are unable to
  801. 46:48find the slope with respect to fxi. So
  802. 46:54let me summarize my entire argument
  803. 46:56once. What did I say we have to do? We
  804. 47:01need to find the ft xi that minimizes
  805. 47:04this entire equation, this entire
  806. 47:06objective function. So basically, this
  807. 47:10is an optimization problem. But we
  808. 47:13learned that in an optimization problem
  809. 47:16, what you do is differentiate your
  810. 47:19objective function with respect to the
  811. 47:22parameters involved and then equate it
  812. 47:26to zero to find the value. But for this
  813. 47:30, it is necessary that your
  814. 47:32optimization—I am sorry—your
  815. 47:34objective function must be
  816. 47:36differentiable. But since our y-i hat
  817. 47:41involves a decision tree. Because of
  818. 47:47this decision tree, the loss curve that
  819. 47:50is formed is actually
  820. 47:52non-differentiable at many points.
  821. 47:57Because of that, you cannot find this
  822. 47:59slope, and hence you cannot find a
  823. 48:02value of f (xi) that will minimize this
  824. 48:05entire thing. This is my argument. I
  825. 48:07hope I was able to explain it. So, what
  826. 48:11is the solution? The solution is, what
  827. 48:16if I could smooth out this curve—this
  828. 48:21zigzag, weird curve? Could approximate
  829. 48:26it? I mean, what if I could replace
  830. 48:32this complex equation with some other
  831. 48:39equation that might look like this. It
  832. 48:47is not necessary. It could be a bit
  833. 48:49higher or a bit lower. But it should be
  834. 48:52close. Okay? And at the same time, it
  835. 48:56should be smooth and differentiable.
  836. 49:00The important thing is that we can
  837. 49:03differentiate it with respect to f (xi)
  838. 49:07. This is very important, then our work
  839. 49:10can be done. So basically, what we need
  840. 49:15to do is somehow approximate this part
  841. 49:20of the objective function because,
  842. 49:23right now, this is not useful. So, this
  843. 49:28was a bit of a complex part of this
  844. 49:31entire explanation, but I think I was
  845. 49:33able to roughly explain what the
  846. 49:36problem is. And now, I will tell you
  847. 49:38the solution. The solution is that we
  848. 49:41will approximate our non-differentiable
  849. 49:44curve using a beautiful mathematical
  850. 49:47technique called Taylor series. I am
  851. 49:52sure you must have studied it in
  852. 49:54engineering math, but perhaps didn't
  853. 49:57pay much attention then, but guess what
  854. 49:59? It is going to help us with this
  855. 50:03problem now. So guys, let's quickly try
  856. 50:05to understand the Taylor series. So
  857. 50:08that when I apply it later, you have
  858. 50:11some idea. So, what is the Taylor
  859. 50:14series? Let me first define it for you
  860. 50:17in one line. So, the Taylor series is a
  861. 50:21very, very powerful approximation
  862. 50:24technique. That is the simplest
  863. 50:28definition. So, what does the Taylor
  864. 50:31series say? That you bring any complex
  865. 50:35function. Okay? Bring any complex
  866. 50:38mathematical function. And the Taylor
  867. 50:41series can approximate it using a
  868. 50:48polynomial. Right? Suppose you have
  869. 50:53some very complex function. Let's say
  870. 50:57for now, e to the power x, you can
  871. 51:00approximate it very easily using a
  872. 51:03polynomial. For instance, let's assume
  873. 51:08this is a polynomial. Okay? So, this is
  874. 51:14what the basic definition says: you
  875. 51:17input a complex function, and you can
  876. 51:20approximate it using simple polynomials
  877. 51:23. Okay? This is the main idea behind a
  878. 51:27Taylor approximation or Taylor series.
  879. 51:31The only caveat here is that if you
  880. 51:34want a very accurate, highly accurate
  881. 51:38approximation, then the polynomial you
  882. 51:43create will need many polynomial terms.
  883. 51:47Like x raised to the power 3, to the
  884. 51:50power 4, to the power 5, and so on. The
  885. 51:54more polynomial terms you keep adding,
  886. 51:56the more accurate your approximation
  887. 51:59will become. It will become more
  888. 52:01accurate. Okay? So that was the "what"?
  889. 52:05Now I will tell you the "how"—exactly
  890. 52:08how the Taylor series works. We won't
  891. 52:12go too deep because this isn't a video
  892. 52:14specifically about the Taylor series.
  893. 52:16So, I have added a video in the
  894. 52:19description. From 3Blue1Brown. It is a
  895. 52:21very beautiful video on the Taylor
  896. 52:23series. If you watch it once, your
  897. 52:25understanding will be well-developed.
  898. 52:27But still, I will explain to you a
  899. 52:29little bit about exactly how the Taylor
  900. 52:31series works. Okay? So, the Taylor
  901. 52:35series uses derivatives to convert any
  902. 52:39complex function into a polynomial. It
  903. 52:47uses first-order derivatives,
  904. 52:48second-order derivatives, third, fourth
  905. 52:50, and higher-order derivatives to
  906. 52:52approximate a complex function. Okay?
  907. 52:55So, if I tell you the formula—what is
  908. 52:58the Taylor series formula? The Taylor
  909. 53:01series formula for a function (f (x))
  910. 53:05around a point 'a' can be written as: f
  911. 53:14(x) is approximately equal to f (a) + f
  912. 53:18'(a) divided by 1!(x-a) + f''(a)/2!(x-a
  913. 53:37) ² + f'''(a)/3!(x-a) ³ and in this
  914. 53:49way, you can add as many polynomial
  915. 53:52terms as you want. So you can see, to
  916. 53:56approximate this function around point
  917. 53:58'a', I am using the derivatives. This
  918. 54:02is the first-order derivative. This is
  919. 54:03the second order, this is the third
  920. 54:05order. The more derivatives you keep
  921. 54:07adding, the more accurate approximation
  922. 54:09you will get. Okay? So, I will try to
  923. 54:12explain this whole thing to you through
  924. 54:15an example. Let's assume our function
  925. 54:19is e raised to the power x, and we want
  926. 54:22to approximate this function around the
  927. 54:26point a = 0. Okay? So, according to
  928. 54:29this formula, what will the
  929. 54:31approximation be? I will work that out
  930. 54:33for you. First, I will focus on this
  931. 54:35term. What will f of a be? So f of a
  932. 54:39will basically be e raised to the power
  933. 54:42of a instead of x, and the value of a
  934. 54:43is zero. That means it will be one.
  935. 54:47Okay? Now we will focus on this term.
  936. 54:51So this term is f '(a)/1!*(x-a). By the
  937. 54:57way, here f'(a) means the derivative of
  938. 55:02f (x). Okay? So you know that the
  939. 55:06differentiation of e to the power x is
  940. 55:08just e to the power x. So going by that
  941. 55:12logic, it will be e to the power x, and
  942. 55:15instead of x, we will put a, and the 1!
  943. 55:19becomes 1 here, and x-a comes here as
  944. 55:22it is. We will put zero in place of a.
  945. 55:25So it will simply become x. Okay? So,
  946. 55:32for this term, we got x. Now let's
  947. 55:35focus on this term. f ''(a)/2!(x-a) ²;
  948. 55:43the double derivative will be the same.
  949. 55:46So here we will get e to the power a/2!
  950. 55:52(x-a) ²; e to the power 0*x²; so we
  951. 55:58get x²/2! here. So it will be two.
  952. 56:03Then I will show you by calculating. f
  953. 56:08This term will basically be (x-a) ³/3!
  954. 56:15This will again be 1/6*x³; so this
  955. 56:24becomes x³/6. So basically, if I want
  956. 56:29to approximate e to the power x using
  957. 56:33Taylor series, this is what comes. And
  958. 56:45I can extend this as much as I want.
  959. 56:47Okay? So now I will show you how to
  960. 56:51visualize this. So I have Desmos open
  961. 56:55here. First, I will show you what e
  962. 56:59raised to the power x looks like. It's
  963. 57:02very famous. You must already know. Now
  964. 57:05I will show you y = by adding 1 + x. So
  965. 57:14basically, I have used only these terms
  966. 57:17for now. Okay? And you can see that the
  967. 57:22approximation is already accurate for x
  968. 57:27= 0 or a = 0. At least at this point,
  969. 57:31the blue curve and the red curve are
  970. 57:33the same thing. Okay? But notice, as I
  971. 57:37keep adding higher-degree terms, like
  972. 57:40adding x²/2, you will notice that a
  973. 57:48bit around zero, on both sides, the
  974. 57:52approximation is becoming more accurate
  975. 57:55. Notice, I am adding the x³ term.
  976. 58:05Divided by 6, and you can see that you
  977. 58:08can now see the approximation over a
  978. 58:10larger area. So basically, the more
  979. 58:14terms you keep adding to this
  980. 58:17polynomial, the more your approximation
  981. 58:20accuracy will improve for a wider range
  982. 58:23of x. Right? If you add a lot of terms,
  983. 58:27it will start to perfectly approximate
  984. 58:29this red curve. And that is the beauty
  985. 58:32of Taylor series. Right? So that is
  986. 58:35what we have to do now. We need to
  987. 58:37apply Taylor series to our objective
  988. 58:41function, which is not particularly
  989. 58:46usable at this point, and make it
  990. 58:50usable. So guys, now that we understand
  991. 58:53what Taylor series is and how it works.
  992. 58:57Now we will apply the Taylor series to
  993. 58:59our objective function and approximate
  994. 59:01and simplify this complex objective
  995. 59:03function of ours. Right? We are just
  996. 59:07going to do one thing: we will simplify
  997. 59:10only up to the second-degree polynomial
  998. 59:13. Basically, we will take this term,
  999. 59:15this term, and this term. We won't take
  1000. 59:17the terms beyond that. Third derivative
  1001. 59:19, fourth derivative. We don't need to
  1002. 59:21take them. Our work will get done.
  1003. 59:23Right? Now, the biggest challenge in
  1004. 59:27applying Taylor series approximation to
  1005. 59:30such complex equations is to identify
  1006. 59:34what x will be and what a will be. So,
  1007. 59:38first of all, I would like to give this
  1008. 59:40clarification. Look, in our case, x
  1009. 59:43will be this entire term. Oh, one more
  1010. 59:46thing, we are only going to apply
  1011. 59:49Taylor series to this much part. We
  1012. 59:52won't apply it to the rest. Right? So
  1013. 59:55here, if you notice, then our x is this
  1014. 59:58entire thing. Because this is the very
  1015. 1:00:00thing that will vary. Basically, the
  1016. 1:00:03prediction up to the t-th iteration. So
  1017. 1:00:08you can write it down here first: yi
  1018. 1:00:13hat t-1 + ft. xi, this becomes our x.
  1019. 1:00:20Now the question arises: what will a be
  1020. 1:00:22? A is the point of change where the
  1021. 1:00:25modification starts to occur. So
  1022. 1:00:27basically, this T-1 iteration is the
  1023. 1:00:30point after which the change is
  1024. 1:00:32happening. We are adding this decision
  1025. 1:00:34tree. Now, it can have any output. So
  1026. 1:00:37we will take a as yi hat t-1, okay? The
  1027. 1:00:42change is about to happen after this.
  1028. 1:00:44Right? Now, what will we do? We will
  1029. 1:00:46calculate all these terms one by one
  1030. 1:00:50and approximate this equation. So first
  1031. 1:00:53of all, we need to calculate f (a), so
  1032. 1:00:56to calculate f (a), what will we have
  1033. 1:00:58to do? First, we have to write f (x)
  1034. 1:01:01and then wherever there is x, we will
  1035. 1:01:03substitute it with a. We will replace x
  1036. 1:01:07. So, first, let me write down f (x)
  1037. 1:01:09for you. So f (x) is this entire term
  1038. 1:01:12of ours. I am writing this as it is. i
  1039. 1:01:16= 1 to n, yi-yi hat (t-1) + (ft) xi;
  1040. 1:01:29okay, this is my entire x. Now I just
  1041. 1:01:33have to do one thing, I have to replace
  1042. 1:01:36this entire x with a. So what I will do
  1043. 1:01:38is, I will just erase and I will
  1044. 1:01:43rewrite and this becomes our f (a); we
  1045. 1:01:46have found our first term. Now, we need
  1046. 1:01:49to find the second term similarly. What
  1047. 1:01:52do we need to do for the second term?
  1048. 1:01:54We need to find f '(a). Okay? Basically
  1049. 1:01:58, we need to do df/dx. And then, after
  1050. 1:02:02replacing x, let's assume for a moment
  1051. 1:02:05that f (x) is x². So, what would df/dx
  1052. 1:02:09be? 2x So then, what would f'(a) be? 2a
  1053. 1:02:18, replaced x with a. So, if I want to
  1054. 1:02:22write it simply, then f '(a) x-a; let's
  1055. 1:02:27focus on f'(a) first. This will become
  1056. 1:02:32our sigma i = 1 to n del L yi yi hat,
  1057. 1:02:42here too t-1 will come. Because you
  1058. 1:02:45have to put a in place of x. Divided by
  1059. 1:02:48del y t-1, okay. Now let's talk about
  1060. 1:02:55x-a, it's simple. You subtract this
  1061. 1:02:58from that. What is left? ft xi and
  1062. 1:03:04similarly we now need to find f ''(a)/2
  1063. 1:03:10*(x-a) ². So, this is also simple.
  1064. 1:03:14Here we will have i = 1 to n. This will
  1065. 1:03:21remain the same thing, just
  1066. 1:03:23double-differentiated, square of ft
  1067. 1:03:30squared. And we have approximated this.
  1068. 1:03:33Now I will just place these three here,
  1069. 1:03:36so this whole equation will now be
  1070. 1:03:39formed. I am bringing all three
  1071. 1:03:42summations out. And first of all, L
  1072. 1:03:47will come (yi, yi hat t-1 iteration),
  1073. 1:03:56plus now this term, this big
  1074. 1:04:00differentiation here, we call this the
  1075. 1:04:05gradient. This is called the gradient.
  1076. 1:04:09Okay? And we will denote this by gi. So
  1077. 1:04:15what we can do is we can write gi. Oh,
  1078. 1:04:20I forgot one more thing here. A half
  1079. 1:04:23will also come outside here because
  1080. 1:04:24this is also two, right. So here it
  1081. 1:04:27became gi. And then came our ft xi plus
  1082. 1:04:35. Now this term, the double
  1083. 1:04:38differentiation of the loss function,
  1084. 1:04:42we call it the Hessian. You might have
  1085. 1:04:46heard of it, and you will denote it by
  1086. 1:04:49hi, so here will come 1/2 hi ft² xi
  1087. 1:04:57and then lastly, this term will also
  1088. 1:05:02come, plus ft I am sorry, here will
  1089. 1:05:09come omega of ft xi and this is our
  1090. 1:05:15simplified objective function, guys. So
  1091. 1:05:18, I have written this final equation a
  1092. 1:05:21bit more clearly here. Right? I guess,
  1093. 1:05:25first of all, you can appreciate that
  1094. 1:05:28we have given that complex equation a
  1095. 1:05:32polynomial form, and now our objective
  1096. 1:05:35function is represented very well in
  1097. 1:05:38terms of x. Also, at this point, I
  1098. 1:05:41would like to show you the research
  1099. 1:05:43paper. And you can see that we have
  1100. 1:05:46achieved this step exactly. Absolutely
  1101. 1:05:49line by line. Here is our first term.
  1102. 1:05:52Here is our second gradient term, and
  1103. 1:05:55here is our third Hessian term. This is
  1104. 1:05:58exactly what we have achieved here. Now
  1105. 1:06:01, if we want, we can simplify this a
  1106. 1:06:04little bit. How? I will tell you. Look,
  1107. 1:06:08what is our goal? What did we set out
  1108. 1:06:10to do? We need a value for f (t, xi)
  1109. 1:06:14for which this entire equation is
  1110. 1:06:17minimized. Okay? So, our plan was to
  1111. 1:06:21differentiate this whole thing with
  1112. 1:06:25respect to f (t, xi) and then set it to
  1113. 1:06:28zero. Right? I mean, the plan was
  1114. 1:06:31something like this, or we will apply
  1115. 1:06:33some form of optimization. So, we have
  1116. 1:06:36to differentiate. That is clear. So,
  1117. 1:06:39notice one thing. If I look here, there
  1118. 1:06:45are a total of four terms. This is the
  1119. 1:06:47first term. This is the second term,
  1120. 1:06:50this is the third term, and this is the
  1121. 1:06:52fourth term. In this, this, and this, f
  1122. 1:06:55(t, xi) is present. Meaning,
  1123. 1:06:58differentiating will be useful. But f (
  1124. 1:07:00t, xi) is not present in this one. So,
  1125. 1:07:03when I differentiate it with respect to
  1126. 1:07:05f (t, xi), this term will automatically
  1127. 1:07:07become zero later on. So, what I can do
  1128. 1:07:11is, I can perform a simplification and
  1129. 1:07:14I can write my objective function as
  1130. 1:07:16this. Just a sum of gradients and
  1131. 1:07:25Hessian. And exactly this is written
  1132. 1:07:29here in the next equation. Look, these
  1133. 1:07:32people have done the same thing. They
  1134. 1:07:34have also removed this term. Because
  1135. 1:07:37this is a constant term. It does not
  1136. 1:07:39contain f (t, xi). So, by
  1137. 1:07:41differentiating it further, you won't
  1138. 1:07:43get anything from it. So, it was just a
  1139. 1:07:46smart move to remove that. And now we
  1140. 1:07:48are here. Now, perhaps you might also
  1141. 1:07:51notice that this term of ours has been
  1142. 1:07:54sitting quietly for a long time. So,
  1143. 1:07:57now what will we do? We will expand
  1144. 1:07:59this too. Okay? And we know how to
  1145. 1:08:03expand. I told you when I taught you
  1146. 1:08:06the XGBoost loss function that this
  1147. 1:08:08term is kind of your regularization
  1148. 1:08:11term and you can break it down into
  1149. 1:08:13these two components. Okay? Here, this
  1150. 1:08:17t is the decision tree that you must
  1151. 1:08:20have applied at the t-th step, which is
  1152. 1:08:22the last model you added. So, this t
  1153. 1:08:27indicates how many leaf nodes there are
  1154. 1:08:30. So you can see there are three leaf
  1155. 1:08:32nodes in this one. And this lambda
  1156. 1:08:36times W squared basically means that
  1157. 1:08:40the output of these three leaf nodes
  1158. 1:08:43can be called W1, W2, and W3. So we can
  1159. 1:08:48write it by breaking it down as 1/2
  1160. 1:08:52times lambda W1 squared + W2 squared +
  1161. 1:08:57W3 squared, okay? One term for each
  1162. 1:09:01leaf node. Okay? So that is what we are
  1163. 1:09:04going to do. We are going to expand
  1164. 1:09:09this. Okay? For a moment, let's assume
  1165. 1:09:13that the tree we added at the end has t
  1166. 1:09:17leaf nodes. Okay? So how will this
  1167. 1:09:22entire equation break down? This whole
  1168. 1:09:26equation will become. i = 1 to n. We
  1169. 1:09:30will write this term as it is. gi ft xi
  1170. 1:09:36+ 1/2 hi ft squared xi plus here you
  1171. 1:09:42will have gamma times t + 1/2 lambda
  1172. 1:09:48inside, since there are t leaf nodes,
  1173. 1:09:55we will write it as w 1² + w 2² + w
  1174. 1:10:013² dot dot dot + wt² because there
  1175. 1:10:07are t nodes. Now obviously this is not
  1176. 1:10:10the compact form. So to write this in
  1177. 1:10:13compact form, what we can do is we can
  1178. 1:10:15use a summation. So we can write it
  1179. 1:10:17this way. We can call it i or j.
  1180. 1:10:21Because we have already used i. j = 1
  1181. 1:10:25to T of WJ squared. Okay? This became
  1182. 1:10:32our somewhat more simplified objective
  1183. 1:10:34function. So now guys, we have brought
  1184. 1:10:37this objective function up to this
  1185. 1:10:39point, but there is a big problem here.
  1186. 1:10:42Understand the problem. There are three
  1187. 1:10:45terms here. This is the first term,
  1188. 1:10:47this is the second term, and this is
  1189. 1:10:49the third term. Now, two of these terms
  1190. 1:10:52have a summation. In this term and in
  1191. 1:10:54this term. But the problem is that
  1192. 1:10:57these two summations are different.
  1193. 1:10:59Here you have a summation over i which
  1194. 1:11:02goes from 1 to n. Basically the number
  1195. 1:11:05of rows. And here you have another
  1196. 1:11:10summation over j which goes from 1 to t
  1197. 1:11:13. Where t is what? t is your number of
  1198. 1:11:17leaf nodes in the last model that was
  1199. 1:11:21added. For instance, if there are two
  1200. 1:11:24leaf nodes, then the value of t will be
  1201. 1:11:26two and the value of j will be one for
  1202. 1:11:27the first time. The second time, it
  1203. 1:11:29will be two. So now, the problem is
  1204. 1:11:32that if we go to optimize this, there
  1205. 1:11:34will be a problem. So we have to
  1206. 1:11:38simplify this further and bring them
  1207. 1:11:40into a common summation. So I am going
  1208. 1:11:43to do a smart manipulation here. First,
  1209. 1:11:48I will show you that manipulation and
  1210. 1:11:50then I will explain how it happened.
  1211. 1:11:53But trust me, after that manipulation
  1212. 1:11:56is done, things will drastically
  1213. 1:11:58improve. Then it will become very easy
  1214. 1:12:00to optimize this. So let me write it
  1215. 1:12:03down first. So I would write it this
  1216. 1:12:05way. Summation of j = 1 to t Bracket
  1217. 1:12:16summation i belongs to ij gi wj plus
  1218. 1:12:27summation i belongs to ij 1/2 comes
  1219. 1:12:35outside h wj sq plus gamma plus plus
  1220. 1:12:471/2 lambda I am sorry j = 1 to t wj²
  1221. 1:12:57This is the transformation. Now I will
  1222. 1:13:00be very honest with you. When I was
  1223. 1:13:02reading this XGBoost paper and I saw
  1224. 1:13:04this step and this transformation, for
  1225. 1:13:07a while I didn't even understand how
  1226. 1:13:09this happened. How are we able to write
  1227. 1:13:13it this way? But trust me, it's very
  1228. 1:13:15logical. I will explain it to you one
  1229. 1:13:17by one. First of all, understand a
  1230. 1:13:19small change. The first change is that
  1231. 1:13:24I have started calling ft (xi) as wj. I
  1232. 1:13:29guess you might be able to notice this.
  1233. 1:13:32This is the first change. Right? This
  1234. 1:13:38is the first change. I will write it
  1235. 1:13:42here that wj is nothing but ft (xi)
  1236. 1:13:48right? The second change is that I have
  1237. 1:13:54broken i = 1 to N into two summations.
  1238. 1:14:01First j = 1 to t and inside that, i
  1239. 1:14:05belongs to ij. You just need to
  1240. 1:14:10understand these two things. If you
  1241. 1:14:13understand these two things, you will
  1242. 1:14:15understand this transformation. Alright
  1243. 1:14:18guys, then I will explain to you how we
  1244. 1:14:20took this transformation. Right? First,
  1245. 1:14:24I will explain how we gave the form of
  1246. 1:14:28summation i = 1 to n to j = 1 to t and
  1247. 1:14:32inside that, i belongs to ij. Right? To
  1248. 1:14:37understand this, I have taken a small
  1249. 1:14:39example. Suppose this is your data. It
  1250. 1:14:42has an input column. You can call it xi
  1251. 1:14:45. And this is your output column. You
  1252. 1:14:47can call it yi. And this is our t-th
  1253. 1:14:50step decision tree. It's a very simple
  1254. 1:14:53decision tree. Where it's just asking
  1255. 1:14:55if the CGPA is less than seven. If it's
  1256. 1:14:57less, the package will be five, and if
  1257. 1:15:00it's more than seven, the package will
  1258. 1:15:02be 10. Simple. Okay? Since this is a
  1259. 1:15:05leaf output, we are calling it W1. And
  1260. 1:15:08this is also a leaf output, so we are
  1261. 1:15:10calling it W2. Okay? Now understand,
  1262. 1:15:13look at this setup. Focus on this. Just
  1263. 1:15:17focus on this part. If I were to tell
  1264. 1:15:22you to expand this term for this
  1265. 1:15:24particular dataset where you have four
  1266. 1:15:27rows. Expand this term. Then how would
  1267. 1:15:31you write it expanded? You would write
  1268. 1:15:33G1 FT X1 + 1/2 H1 FT² X1 would be for
  1269. 1:15:47the first row. Okay? Here, wherever
  1270. 1:15:50there is X1, you would put 7.1. Okay?
  1271. 1:15:54Even here in X1, you would put 7.1.
  1272. 1:15:57Plus, now what would you do for the
  1273. 1:15:59second row? For the second row, you
  1274. 1:16:02would write G2 f2 x2 + 1/2 h2 f t² x2,
  1275. 1:16:09here wherever there is x2, you would
  1276. 1:16:15put 8.2. You would write the same for
  1277. 1:16:18the fourth term: g4 ft x4 + 1/2 h4 ft²
  1278. 1:16:33x4. I guess you can understand, I have
  1279. 1:16:36expanded it for all four terms. If you
  1280. 1:16:38divide it here, there are four terms in
  1281. 1:16:42total, one for each row. Okay, now I
  1282. 1:16:47will explain what this is saying here.
  1283. 1:16:51So first of all, think about how many
  1284. 1:16:53times this outer summation will open?
  1285. 1:16:56This outer summation will open twice,
  1286. 1:17:00why? Because in our decision tree,
  1287. 1:17:02there are two leaf nodes. This is one,
  1288. 1:17:04this is two. So this outer node will
  1289. 1:17:08run twice. Now let's talk about the
  1290. 1:17:11inner node and what it means. i belongs
  1291. 1:17:14to IJ. What is IJ? So IJ is the
  1292. 1:17:19instance set of leaf J. That is what I
  1293. 1:17:26mean. Watch carefully. It's a very
  1294. 1:17:28small thing. This is row one. This is
  1295. 1:17:30row two. This is row three. This is row
  1296. 1:17:33four. Okay? Now I am putting these rows
  1297. 1:17:36into this decision tree. CGPA less than
  1298. 1:17:397.1 Less than seven. So where will this
  1299. 1:17:45first row fall? Into this leaf. It's
  1300. 1:17:508.2. Where will it fall? Right here.
  1301. 1:17:54It's 6.5. Where will it fall? 3 and 9.1
  1302. 1:17:59. Where will it fall? Four. So that
  1303. 1:18:03means based on this data, we can say
  1304. 1:18:07that for this leaf, leaf node one, its
  1305. 1:18:10instance set contains only one row,
  1306. 1:18:13this one. Whereas if you talk about
  1307. 1:18:18this leaf, its instance set will
  1308. 1:18:20contain three rows. One, two, and four.
  1309. 1:18:24Okay? So now look, I am expanding it. I
  1310. 1:18:27am starting the value of J from one.
  1311. 1:18:31Started the value of J at one. This
  1312. 1:18:33means we are talking about this leaf
  1313. 1:18:35node. Now what do we need to do? For
  1314. 1:18:37whatever row is inside this leaf node,
  1315. 1:18:41we have to write this equation. Okay?
  1316. 1:18:45So that will be g 3, for a moment I
  1317. 1:18:52will just call wj as ft xi. I will
  1318. 1:18:56explain how both are equal a little
  1319. 1:18:57later. But for now, I am calling it ft
  1320. 1:19:02x3. Plus 1/2 h3 ft x3. That's it. Now
  1321. 1:19:15Since there was only one in this, the
  1322. 1:19:17work of the first leaf node is finished
  1323. 1:19:19. Now we will move to J = 2, which is
  1324. 1:19:22this leaf node. Now it has three rows.
  1325. 1:19:25Which is the first row? The one with
  1326. 1:19:26one. So for that, it will be G1 FT X1 +
  1327. 1:19:341/2 H1 FT X1 Okay? It will be squared.
  1328. 1:19:42Here also it will be squared. Then the
  1329. 1:19:46second row will come, g2 ft x2 + 1/2 h2
  1330. 1:19:57ft² x2, and lastly the fourth term
  1331. 1:20:03will come, g4t x4 + 1/2 h4 ft² x4. Now
  1332. 1:20:16you compare this one and compare this.
  1333. 1:20:20You would find that both are the same.
  1334. 1:20:23The order is different, but they are
  1335. 1:20:25the same thing. Right? So it means that
  1336. 1:20:29when we have written the equation in
  1337. 1:20:31this form, we are writing all these
  1338. 1:20:33rows one by one in this form. But when
  1339. 1:20:39we bring it into this form, what are we
  1340. 1:20:41doing? We are asking the tree which
  1341. 1:20:43rows ended up in your first leaf node.
  1342. 1:20:46For them, I did the same thing. Then
  1343. 1:20:50for the rows in the second leaf node, I
  1344. 1:20:52did the same thing. So basically, I am
  1345. 1:20:55still traversing over all the rows. I
  1346. 1:20:57have just segregated them according to
  1347. 1:21:00the tree. So if we were talking about
  1348. 1:21:02the first 100 children before. Here too
  1349. 1:21:04, we are talking about the same 100
  1350. 1:21:05children. Only the order has changed.
  1351. 1:21:08Because you are expanding according to
  1352. 1:21:10the decision tree's processing. So I
  1353. 1:21:14really hope you understood this first
  1354. 1:21:17similarity, how we smartly broke down i
  1355. 1:21:20= 1 to n into this. Okay? Now, just one
  1356. 1:21:25thing remains to be understood, why I
  1357. 1:21:28have called F (t, xi) as Wj. Look here,
  1358. 1:21:35I guess you can understand this very
  1359. 1:21:38easily too. Think about it, when you
  1360. 1:21:42are talking about the third row, when
  1361. 1:21:44you talk about the third row, the third
  1362. 1:21:47row has entered this leaf, right? So,
  1363. 1:21:51for that, what will ft (t, x3) be?
  1364. 1:21:55First of all, what was ft? ft was the
  1365. 1:21:57output of our decision tree. Now think
  1366. 1:22:01for yourself, for x3, as in the third
  1367. 1:22:03row, what output will our decision tree
  1368. 1:22:06give? W1 It will give W1 as the output,
  1369. 1:22:12right? So, I can actually write it like
  1370. 1:22:15this too. Right? Similarly, if you talk
  1371. 1:22:25about this one. This is the first row.
  1372. 1:22:27So, for the first row, what will our
  1373. 1:22:30decision tree output? W2, so I can
  1374. 1:22:33write this as G1 W2 as well. I guess
  1375. 1:22:46you are understanding. This WJ is
  1376. 1:22:50basically the output of the tree for a
  1377. 1:22:53particular leaf node. If I know that
  1378. 1:22:57leaf node, I can directly write it in
  1379. 1:22:59its place, right? That is why I
  1380. 1:23:02performed this transformation. And now
  1381. 1:23:04we are at a stage where we have a
  1382. 1:23:09proper objective function. In a
  1383. 1:23:13completely simplified form. I will
  1384. 1:23:14write it down one more time. The more I
  1385. 1:23:17write it, the more familiar it will
  1386. 1:23:20feel to you. Here we have gi wj + 1/2 i
  1387. 1:23:32belongs to ij hi wj squared plus gamma
  1388. 1:23:42t + 1/2 lambda j = 1 to t wj squared
  1389. 1:23:50and now we can actually simplify this
  1390. 1:23:55entire thing. So, simplifying this now
  1391. 1:23:59is simple algebra. You can see that
  1392. 1:24:02this term, this term, and this term,
  1393. 1:24:06all three are summed from j = 1 to t.
  1394. 1:24:11So, what can we do? We can write the
  1395. 1:24:14loss or objective function in this way.
  1396. 1:24:18Summation j = 1 to t, here we will have
  1397. 1:24:25i belongs to ij gi wj squared plus 1/2
  1398. 1:24:36i belongs to ij hi wj squared and 1/2
  1399. 1:24:47lambda wj squared + gamma t. Now, you
  1400. 1:24:56can take some things common in these,
  1401. 1:25:00like you can write it as I am writing
  1402. 1:25:09it again, summation i belongs to ij gi
  1403. 1:25:13wj squared plus we took half as common,
  1404. 1:25:18and after taking half out, what remains
  1405. 1:25:24here is i belongs to ij hi plus here
  1406. 1:25:29remains lambda, and we also took wj
  1407. 1:25:35squared as common + gamma t. And now we
  1408. 1:25:41are at the position where we can now
  1409. 1:25:45differentiate this term with respect to
  1410. 1:25:48WJ, okay? So, this is for all the terms
  1411. 1:25:55for all the leaves in your decision
  1412. 1:25:57tree, but we actually need to do it for
  1413. 1:26:00just one leaf, and from that, we will
  1414. 1:26:03get the answer for the other leaves too
  1415. 1:26:05. So, basically, we don't need this
  1416. 1:26:08outer summation. We would just take
  1417. 1:26:12this, this, and this. This will also
  1418. 1:26:16become zero. Because when you
  1419. 1:26:18differentiate this with respect to Wj,
  1420. 1:26:20since there is no Wj here, it will
  1421. 1:26:22become zero. Only this term and this
  1422. 1:26:25term will remain, so as soon as we
  1423. 1:26:29differentiate with respect to Wj, first
  1424. 1:26:34of all, okay, one thing I have been
  1425. 1:26:36doing wrong. There won't be a square
  1426. 1:26:38here. My bad, there won't be a square
  1427. 1:26:40here either. First of all, when you
  1428. 1:26:44differentiate this, you will get the
  1429. 1:26:47sum of i belonging to Ij of gi. Right?
  1430. 1:26:53Plus, when you differentiate this, it
  1431. 1:26:56will become 2 times Wj. This two will
  1432. 1:26:58come out to the front. So 2/2 will
  1433. 1:27:01become 1. So you will just be left with
  1434. 1:27:04here, sum of i belonging to Ij of Hi +
  1435. 1:27:11lambda*Wj, and now you have to set this
  1436. 1:27:15equal to 0 and find the value of Wj,
  1437. 1:27:20and the value of Wj will be-lambda*sum
  1438. 1:27:24of i belonging to Ij of gi, divided by
  1439. 1:27:33sum of i belonging to Ij of Hi + lambda
  1440. 1:27:38, and this is the output value for all
  1441. 1:27:45the leaves. If you are talking about
  1442. 1:27:50leaf one, if you want to find w1, then
  1443. 1:27:53you just have to calculate the gradient
  1444. 1:27:57for all those rows that are falling
  1445. 1:28:00into this leaf. If you want to
  1446. 1:28:03calculate W2, then you have to
  1447. 1:28:05calculate the gradient of all those
  1448. 1:28:07rows that are falling into this leaf
  1449. 1:28:10node. And that's it. Now our only job
  1450. 1:28:13is to find out what Gi is and what hi
  1451. 1:28:16is. And we will get our formula to
  1452. 1:28:21calculate the output that we set out to
  1453. 1:28:25find. So guys, we are this close to
  1454. 1:28:29calculating the exact value of Wj, just
  1455. 1:28:32two missing pieces left. We need this
  1456. 1:28:36value of G and we need this value of H.
  1457. 1:28:38G means gradient, and H means Hessian.
  1458. 1:28:46Right? So let me remind you once where
  1459. 1:28:48these came from. When we were applying
  1460. 1:28:52the Taylor series to our objective
  1461. 1:28:54function, we got these derivatives and
  1462. 1:28:56this double derivative there. We called
  1463. 1:29:00the derivative the gradient and the
  1464. 1:29:01double derivative the Hessian. So now
  1465. 1:29:04we have to calculate these values. The
  1466. 1:29:09problem is that your gradient, which
  1467. 1:29:13you are also writing like this: y i hat
  1468. 1:29:20t minus 1, Del y-hat t-1 and whatever
  1469. 1:29:26your Hessian is (well, Del will be used
  1470. 1:29:30here too), whatever your Hessian is,
  1471. 1:29:34which is the double derivative. Let me
  1472. 1:29:41write it down first, then I'll explain
  1473. 1:29:43what I'm trying to say. So, the problem
  1474. 1:29:47with this gradient and Hessian is that
  1475. 1:29:50they actually depend on the loss
  1476. 1:29:52function. This means you will have to
  1477. 1:29:55derive separate gradients and Hessians
  1478. 1:29:58for regression and separate ones for
  1479. 1:30:00classification. So, what do we do first
  1480. 1:30:03? Let's focus on regression because the
  1481. 1:30:05loss function is a bit simpler here.
  1482. 1:30:07One more thing I would like to clarify.
  1483. 1:30:11Don't be intimidated by this t-1. It
  1484. 1:30:15simply means that you are adding models
  1485. 1:30:19one by one, and you are currently at
  1486. 1:30:23the t-th iteration. But the loss you
  1487. 1:30:28are calculating is at the t-1 step. You
  1488. 1:30:31are calculating the loss at this step.
  1489. 1:30:33That's it. Nothing more. Okay? So it's
  1490. 1:30:36nothing special. It's basically the
  1491. 1:30:38same thing. So, if you talk about
  1492. 1:30:43regression, then in regression, your
  1493. 1:30:46loss function is Mean Squared Error,
  1494. 1:30:50and you can also write it as: sigma of
  1495. 1:30:54i = 1 to n (yi-yi-hat) squared. Okay,
  1496. 1:31:00now whether you write yi-hat here or
  1497. 1:31:03add t-1, it doesn't matter, it's the
  1498. 1:31:05same thing. You have to differentiate
  1499. 1:31:09this. You have to find out this value.
  1500. 1:31:13So, what will this value be? It's very
  1501. 1:31:16simple. If you differentiate, you will
  1502. 1:31:20basically get sigma i = 1, this two
  1503. 1:31:23will come here and cancel out, and you
  1504. 1:31:27will get yi-yi-hat, and this minus sign
  1505. 1:31:30will come out after differentiation.
  1506. 1:31:35Okay? This is basic differentiation. So
  1507. 1:31:37you can write it like this too. i = 1
  1508. 1:31:40to n yi-hat-yi Okay? And this is your
  1509. 1:31:50gi. Okay? Also, the yi-hat here is the
  1510. 1:31:55yi-hat of the previous step. You have
  1511. 1:31:59to remember this because it is t-1. The
  1512. 1:32:02significance of this t-1 is that the
  1513. 1:32:04yi-hat is from the previous step. So if
  1514. 1:32:06I place this here, what will this whole
  1515. 1:32:10thing become? This whole thing will
  1516. 1:32:13become minus sigma of i instead of gi.
  1517. 1:32:23Now we will not use this summation.
  1518. 1:32:27Because we are already using this
  1519. 1:32:29summation. We are not talking about all
  1520. 1:32:31the rows. We are only talking about the
  1521. 1:32:34rows that fell into the current leaf.
  1522. 1:32:36So the next term will remain the same.
  1523. 1:32:37So here we will get yi hat minus yi.
  1524. 1:32:44Now, if you want, you can take this
  1525. 1:32:46minus inside. So actually, you can
  1526. 1:32:49write it by flipping it. You can write
  1527. 1:32:53it by reversing it. Then it will return
  1528. 1:32:57to yi minus yi hat. And just remember,
  1529. 1:33:00this will be t-1, the y-hat from the
  1530. 1:33:02previous step. Okay? Now think for
  1531. 1:33:05yourself, in a way, what are you doing?
  1532. 1:33:07You are calculating the residual for
  1533. 1:33:13every point. That is exactly what you
  1534. 1:33:16are doing, right? Just think about it,
  1535. 1:33:18suppose you have this data-CGPA, IQ,
  1536. 1:33:22and the package received. How did you
  1537. 1:33:26start? You used to start. Suppose you
  1538. 1:33:28have this data. Eight, 80, package
  1539. 1:33:30received is eight; nine, 90, package
  1540. 1:33:32received is nine, for example. Okay? So
  1541. 1:33:35how did you start? You used to build
  1542. 1:33:37the first model. So what was the
  1543. 1:33:38prediction of the first model? Which is
  1544. 1:33:40the mean. So here we get pred one. So
  1545. 1:33:43this became 8.5, and this also became
  1546. 1:33:468.5. Okay? So this is your yi and this
  1547. 1:33:51is your yi hat. For step one. Okay? Now
  1548. 1:33:56, as soon as you started adding the
  1549. 1:34:00second model, this column became your t
  1550. 1:34:04-1. Okay? So now for this, what do you
  1551. 1:34:08need to do? To calculate the gradient,
  1552. 1:34:11you just need to subtract this column
  1553. 1:34:13from this column. Calculate 8 minus 8.5
  1554. 1:34:16. Calculate 9 minus 8.5. Okay? So in a
  1555. 1:34:20way, basically, whatever your residual
  1556. 1:34:22was from the previous step, that is
  1557. 1:34:23what came here. So I can actually do
  1558. 1:34:26what with this? I can replace this with
  1559. 1:34:30the sum of residuals. Don't you think
  1560. 1:34:36this whole expression above can just be
  1561. 1:34:39replaced with the sum of residuals?
  1562. 1:34:42Okay? Now let's talk about the Hessian.
  1563. 1:34:45So in the case of the Hessian, what do
  1564. 1:34:47you have to do? Differentiate this
  1565. 1:34:49thing twice. When we differentiated it
  1566. 1:34:53once with respect to yi hat, what did
  1567. 1:34:56we get? We got—let's forget the
  1568. 1:34:59summation for a moment. Okay? Ignore
  1569. 1:35:01the summation because there is a
  1570. 1:35:03summation from i equals 1 to n. Here is
  1571. 1:35:05another summation. So ignore that. You
  1572. 1:35:08got this yi hat minus yi. Okay? Now you
  1573. 1:35:15have to differentiate it again, with
  1574. 1:35:18respect to yi hat. You have to
  1575. 1:35:21differentiate one more time, so what
  1576. 1:35:22will you get? You will get one, right?
  1577. 1:35:27This means down here we will have σ (i
  1578. 1:35:32belonging to ij) one + lambda. Now, how
  1579. 1:35:37many times will this one occur? As many
  1580. 1:35:40as the number of points falling into
  1581. 1:35:44your leaf, so basically this becomes
  1582. 1:35:49number of residuals + lambda. So, in
  1583. 1:35:53simple terms, if you go to calculate wj
  1584. 1:35:58for a regression problem with mean
  1585. 1:36:02squared error, your formula is sum of
  1586. 1:36:07residuals divided by number of
  1587. 1:36:11residuals + lambda, okay, that are
  1588. 1:36:17falling into that leaf. Okay? And if
  1589. 1:36:22you go back to the very beginning, to
  1590. 1:36:25the plan of attack, notice this right
  1591. 1:36:28here. This is exactly what we just
  1592. 1:36:30derived. Sum of residuals/number of
  1593. 1:36:36residuals + lambda; we have solved the
  1594. 1:36:38regression problem. Now, only the
  1595. 1:36:41classification problem remains. Now
  1596. 1:36:43let's talk about the classification
  1597. 1:36:46scenario. Here, if you want to
  1598. 1:36:48calculate the gradient and hessian,
  1599. 1:36:51your loss function is log loss. Okay?
  1600. 1:36:57You will have to differentiate and
  1601. 1:36:59double-differentiate the log loss to
  1602. 1:37:00find out g and h. The good part is that
  1603. 1:37:04we have already done this in gradient
  1604. 1:37:07boosting. So, I won't show it again
  1605. 1:37:11here because it will take a lot of time
  1606. 1:37:13. But I will show you where I have
  1607. 1:37:15taught this to you. So, if you go to
  1608. 1:37:17your course dashboard, you'll find
  1609. 1:37:20gradient boosting taught in week 36.
  1610. 1:37:22The math formulation for gradient
  1611. 1:37:24boosting classification is there. If
  1612. 1:37:27you watch from 37 minutes onwards, I
  1613. 1:37:29have derived everything to show what
  1614. 1:37:31comes from single differentiation. And
  1615. 1:37:34then I have also explained what comes
  1616. 1:37:36from double differentiation. Here, you
  1617. 1:37:41will find, like, I'll have to scroll a
  1618. 1:37:43bit to figure out where it is. But yeah
  1619. 1:37:46, both things have been derived. In
  1620. 1:37:49fact, you can also see it in the notes
  1621. 1:37:51that have been provided to you. Anyway,
  1622. 1:37:55let me show it to you. Yeah, so when
  1623. 1:38:01you differentiate once, here is your
  1624. 1:38:06output. It's basically yi-pi; pi is the
  1625. 1:38:11probability for the previous time step,
  1626. 1:38:14okay? You can call this a residual
  1627. 1:38:17itself. And if you double-differentiate
  1628. 1:38:21, you get this: pi*(1-pi). Here, pi is
  1629. 1:38:25again the probability in the previous
  1630. 1:38:28time step. Okay? So Basically, when you
  1631. 1:38:33calculate wj for the classification
  1632. 1:38:37scenario, it's the same here as well.
  1633. 1:38:40The sum of residuals will still be on
  1634. 1:38:43top. There will just be one change in
  1635. 1:38:45the denominator. Here comes PI 1-PI +
  1636. 1:38:50lambda i belongs to I. What is PI here?
  1637. 1:38:58The predicted probability from the
  1638. 1:39:02previous time step or iteration, you
  1639. 1:39:07can say. Okay? So this is the output
  1640. 1:39:11and this is what we saw when we
  1641. 1:39:13discussed the plan of attack. You can
  1642. 1:39:16see. At the top is the sum of residuals
  1643. 1:39:19, and this has come at the bottom. Okay
  1644. 1:39:22? And this is what we calculated here
  1645. 1:39:25as well. And you can see, I hope you
  1646. 1:39:27have understood up to this point. So
  1647. 1:39:31guys, if we go back to where we started
  1648. 1:39:33, we wanted to learn to derive four
  1649. 1:39:35formulas in this video. We have learned
  1650. 1:39:39to derive two of those formulas from
  1651. 1:39:41scratch. The one to calculate the
  1652. 1:39:44output value. Now only two formulas are
  1653. 1:39:46left, and that is the formula to find
  1654. 1:39:48the similarity score. Where did this
  1655. 1:39:50come from? We will learn that now. So
  1656. 1:39:53if we look at our progress so far, we
  1657. 1:39:57had an objective function. Okay? Whose
  1658. 1:40:02equation is on the screen, and we
  1659. 1:40:04calculated the values of wj that
  1660. 1:40:07minimize it, and that wj turned out to
  1661. 1:40:10be this. Then, when I put the values of
  1662. 1:40:14G and H into this wj, I got the output
  1663. 1:40:17value exactly for both regression and
  1664. 1:40:20classification. But what if I do one
  1665. 1:40:25thing, take this wj and replace it here
  1666. 1:40:29, what will I get? Think about it. I
  1667. 1:40:34will get the minimum loss. That comes
  1668. 1:40:40from using this parameter value. Right?
  1669. 1:40:45Currently, what is this wj? This is the
  1670. 1:40:48value of wj. That will minimize this
  1671. 1:40:53loss. But how much will that loss be?
  1672. 1:40:57What will be its minimum value? We want
  1673. 1:40:59to find that out. So that is why we
  1674. 1:41:02will replace them inside wj. So what
  1675. 1:41:06will happen by replacing? I am
  1676. 1:41:07continuing here. Why is it called that?
  1677. 1:41:11This minimum loss that comes, why is it
  1678. 1:41:13called that? First, let me derive the
  1679. 1:41:17expression for you. Then I will tell
  1680. 1:41:20you what its significance is. So there
  1681. 1:41:23is nothing special. We will basically
  1682. 1:41:26use simple mathematical algebra to
  1683. 1:41:30manipulate it. Otherwise, there is
  1684. 1:41:32nothing special. Here comes GI. This wj
  1685. 1:41:35we are...filling in here. Here comes
  1686. 1:41:50plus 1/2. i belongs to ij. hi + lambda,
  1687. 1:42:01here it is squared, so here will come i
  1688. 1:42:05belongs to ij gi squared divided by the
  1689. 1:42:10square of the bottom quantity as well.
  1690. 1:42:15i belongs to ij hi + lambda squared.
  1691. 1:42:21Okay? And...We will close this and here
  1692. 1:42:28am t will come. Now you will notice
  1693. 1:42:33that this quantity will cancel out this
  1694. 1:42:36quantity once because there is a square
  1695. 1:42:39there, and by doing that we get this.
  1696. 1:42:43We will get J. By the way, it should be
  1697. 1:42:47J here. I am sorry. Because there are
  1698. 1:42:49such long expressions and I have to
  1699. 1:42:51teach simultaneously. So, some small
  1700. 1:42:53mistakes might be happening. I am sure
  1701. 1:42:55there must be some mistakes earlier too
  1702. 1:42:57that I might not have noticed. So
  1703. 1:42:59please write in the comments so that if
  1704. 1:43:02anyone gets confused in the future, if
  1705. 1:43:05they go through the comments, at least
  1706. 1:43:08they will understand. So, one thing you
  1707. 1:43:14might be seeing is that both terms have
  1708. 1:43:16become the same. This one and this one,
  1709. 1:43:21there is a -1 in front of this. There
  1710. 1:43:24is a +1/2 in front of this. So, if we
  1711. 1:43:28want, we can write it like this. This
  1712. 1:43:31would become -1/2 + t. Now, if I want,
  1713. 1:43:39I can bring this -1/2 outside. So, this
  1714. 1:43:44will come as -1/2, j = 1 to t In the
  1715. 1:43:54numerator, there will be Σ (i belongs
  1716. 1:43:57to Ij) gi², divided by (i belongs to
  1717. 1:44:05Ij) hi + λ + gamma. This is the
  1718. 1:44:10minimum loss value. This is the minimum
  1719. 1:44:16loss value, and it indicates what the
  1720. 1:44:20minimum loss will be from the last
  1721. 1:44:24model you are adding, the last tree you
  1722. 1:44:29are adding. Okay? Exactly this same
  1723. 1:44:33value you will also find in the
  1724. 1:44:35research paper. You can see I am
  1725. 1:44:37talking about this value. We had
  1726. 1:44:40already calculated wj. When we filled
  1727. 1:44:44it back, -1/2 Σ gi²/hi + λ + t, we
  1728. 1:44:49got exactly this. And look what is
  1729. 1:44:53written here. This equation can be used
  1730. 1:44:56as a scoring function to measure the
  1731. 1:44:58quality of a tree structure q. Whatever
  1732. 1:45:03tree you have built at iteration t, the
  1733. 1:45:07most recent one you are adding, you can
  1734. 1:45:10use this equation to measure the
  1735. 1:45:13quality of that tree. This score is
  1736. 1:45:16like the impurity score for evaluating
  1737. 1:45:19decision trees, except that it is
  1738. 1:45:21derived for a wider range of objective
  1739. 1:45:23functions. Okay? So we can use this
  1740. 1:45:28quantity to replace Gini impurity or
  1741. 1:45:33entropy. Because this also tells us
  1742. 1:45:37what the quality of the tree we have
  1743. 1:45:40built is. Now guys, in this similarity
  1744. 1:45:43score that you derived, you can also
  1745. 1:45:46fill in the values of G and H. Okay? If
  1746. 1:45:49you talk about regression. We found out
  1747. 1:45:51just a while ago that G comes out to be
  1748. 1:45:54. Sum of residuals. Okay? G is actually
  1749. 1:46:05not the sum of residuals. Uh, because
  1750. 1:46:08of this summation, sum comes in. But
  1751. 1:46:11yeah, g is basically your residual. And
  1752. 1:46:14h is one, right? And when you do the
  1753. 1:46:20summation over that, it becomes n. Okay
  1754. 1:46:22? Similarly for classification, your g
  1755. 1:46:27will again be the residual that gets
  1756. 1:46:30summed, and h becomes pi*(1-pi); I told
  1757. 1:46:34you this as well. As soon as you put
  1758. 1:46:38both these things into this formula,
  1759. 1:46:41again you will get this. This formula
  1760. 1:46:45for regression, this formula for
  1761. 1:46:47classification. Here we haven't used
  1762. 1:46:49the regularization term. But you can do
  1763. 1:46:52it too. So guys, the similarity score
  1764. 1:46:55is out. Now I will tell you how we use
  1765. 1:46:59this similarity score to do tree
  1766. 1:47:01building. So for a while, assume that
  1767. 1:47:06you have already added t-1 models. You
  1768. 1:47:11have added t-1 models. And now you are
  1769. 1:47:15going to add the t-th model. At time
  1770. 1:47:19step t, okay? And this is a decision
  1771. 1:47:22tree. So how do you build this decision
  1772. 1:47:27tree? It's very simple. You start with
  1773. 1:47:31a single leaf node first. Okay? You
  1774. 1:47:38will have to watch the old video. And
  1775. 1:47:40there you try out all the feature
  1776. 1:47:42values to find out that feature split.
  1777. 1:47:45Okay? After that, for this single leaf
  1778. 1:47:49node, you calculate this quantity. Okay
  1779. 1:47:53? See how, for this single leaf node,
  1780. 1:47:57you can call this quantity qp, as
  1781. 1:48:03parent. Okay? And this will be -1/2,
  1782. 1:48:08think for yourself, what will the value
  1783. 1:48:12of t be here? The value of t here will
  1784. 1:48:15be one. Why? Because we have only one
  1785. 1:48:17leaf node. So basically, there is no
  1786. 1:48:19need to use the summation. We can write
  1787. 1:48:22it here without using the summation, as
  1788. 1:48:25i belongs to Ip. Ip means parent. All
  1789. 1:48:29those rows that are falling into this
  1790. 1:48:31leaf node. Okay? Here, it will be Gi
  1791. 1:48:38squared, i belongs to Ip Hi + λ + Okay
  1792. 1:48:52? So this is our similarity score for
  1793. 1:48:55this leaf node. Now what will happen?
  1794. 1:48:59We will split this leaf node. So after
  1795. 1:49:03splitting, we will get this decision
  1796. 1:49:05tree where this is the structure. Now
  1797. 1:49:08we will have two leaf nodes. Okay? One
  1798. 1:49:13is this and the second one is this. Now
  1799. 1:49:16obviously, if we have done splitting
  1800. 1:49:19and created new nodes, we would want to
  1801. 1:49:23do that because we want to reduce this
  1802. 1:49:26loss further. Right? So now what will
  1803. 1:49:30we do? We will calculate this overall
  1804. 1:49:34loss for this tree structure. Okay? So,
  1805. 1:49:38pay attention to what happens here. We
  1806. 1:49:42will write I am calling this qc for
  1807. 1:49:49child; here it will be -1/2, and this
  1808. 1:49:52inner loop will run twice because the
  1809. 1:49:54value of t is two. There are two leaf
  1810. 1:49:57nodes, this one and this one. So, I am
  1811. 1:50:00expanding it. The first time, we will
  1812. 1:50:04talk about this node. The second time,
  1813. 1:50:07we will talk about this node. So, for
  1814. 1:50:10the left node, our equation will be i
  1815. 1:50:14belonging to I_left, gi squared, all
  1816. 1:50:18those rows that fall into this node. σ
  1817. 1:50:24i belonging to IL hi + λ + gamma t.
  1818. 1:50:33Also, one more thing, here the value of
  1819. 1:50:37this t will be one. So, you can
  1820. 1:50:41actually remove it for the parent. And
  1821. 1:50:46what will happen here? Here, this
  1822. 1:50:52lambda has come. Plus Plus, we will
  1823. 1:51:00write this expression once more. So,
  1824. 1:51:04this would be I belonging to IR GI, now
  1825. 1:51:11we are creating it for this node.
  1826. 1:51:14Divided by σ i belonging to ir +
  1827. 1:51:20lambda + here too there is gamma t. But
  1828. 1:51:25now, instead of t, two will come here.
  1829. 1:51:27Because there are two leaf nodes. So we
  1830. 1:51:29can write it as 2 gamma. Okay? So now I
  1831. 1:51:36have the loss of this parent, and the
  1832. 1:51:43cumulative loss of this child. Now I
  1833. 1:51:49need to find out how much the loss was
  1834. 1:51:52reduced. How much did the loss reduce
  1835. 1:51:54after making this split? So, what will
  1836. 1:51:57I do? I will try to calculate this
  1837. 1:51:59quantity. Parent minus child. Okay? I
  1838. 1:52:06will subtract this from that. And you
  1839. 1:52:10would see that you get. I don't want to
  1840. 1:52:14write the whole thing again. So I will
  1841. 1:52:17just copy this much. And I will paste
  1842. 1:52:27it here. Okay? In fact, this will come
  1843. 1:52:35later. The thing above will come first.
  1844. 1:52:38So, I will quickly erase copy paste.
  1845. 1:52:56Okay? Now, I am keeping this entire
  1846. 1:53:01thing like this between them. Between
  1847. 1:53:05these two, this subtraction will come.
  1848. 1:53:07Okay? So, what will happen with this?
  1849. 1:53:10Let's summarize it once. This minus
  1850. 1:53:13will also make this one negative. So,
  1851. 1:53:16because of that, when you add these two
  1852. 1:53:19, you will get-gamma. Okay? And if you
  1853. 1:53:24talk about these three, they will look
  1854. 1:53:27like this -1/2. I am trying to write
  1855. 1:53:31quickly because all these expressions
  1856. 1:53:33are very lengthy. So it takes a lot of
  1857. 1:53:36time. lambda, this minus minus will
  1858. 1:53:48become + 1/2. Here, it will now become
  1859. 1:54:08plus half. Okay? All of this comes
  1860. 1:54:29together and becomes gamma. Now you can
  1861. 1:54:33see if you rearrange this a bit and
  1862. 1:54:35pull the half out. If you pull the half
  1863. 1:54:39out, you can rearrange and write it
  1864. 1:54:41like this. σi belonging to IL, this
  1865. 1:54:48term GI squared σi belonging to IL hi
  1866. 1:54:55+ lambda plus σi belonging to IR GI²,
  1867. 1:55:05this term divided by i belonging to IR
  1868. 1:55:09hi + lambda minus this term i belonging
  1869. 1:55:16to IR gi squared (i belonging to not r,
  1870. 1:55:25it will be p for parent) hi + lambda
  1871. 1:55:31minus gamma; and This is the difference
  1872. 1:55:39that you are, difference in loss that
  1873. 1:55:42you are getting when you are actually
  1874. 1:55:46doing this split. By doing this split,
  1875. 1:55:50you are getting this much of a gain.
  1876. 1:55:52This is the difference. Okay? And this
  1877. 1:55:55is what you do if you remember, we used
  1878. 1:55:57to do exactly this. We used to make a
  1879. 1:55:59split. We used to calculate the
  1880. 1:56:03similarity score for the parent and
  1881. 1:56:05both children and subtract the child
  1882. 1:56:07ones. Okay? Okay? There, I just didn't
  1883. 1:56:11take this half and didn't consider this
  1884. 1:56:13gamma. Because we were not talking
  1885. 1:56:15about regularization. But this internal
  1886. 1:56:17formula is what we had used. Now if you
  1887. 1:56:24talk about it, you can see this is the
  1888. 1:56:26split criteria. The half came out. The
  1889. 1:56:30IL part plus the IR part minus the
  1890. 1:56:34normal I part minus gamma. Okay? So
  1891. 1:56:38this is the loss reduction after the
  1892. 1:56:41split. I hope you are understanding.
  1893. 1:56:44Okay? So with that, we have understood
  1894. 1:56:48this entire mathematics from scratch.
  1895. 1:56:52We now have justification for
  1896. 1:56:54everything we have done so far. So how
  1897. 1:56:56did you find this video? I know it was
  1898. 1:56:58a very long video and you must be tired
  1899. 1:57:01from studying for sure, and it is
  1900. 1:57:02possible that you might have doubts in
  1901. 1:57:04some places. But trust me, this video
  1902. 1:57:07is created in such a way that if you go
  1903. 1:57:09back and watch it again, and make your
  1904. 1:57:11own notes, then things will stick in
  1905. 1:57:13your mind and you will be able to
  1906. 1:57:15retain it. Okay? So a lot of hard work
  1907. 1:57:17went into making this video. So please,
  1908. 1:57:20if you liked it, do like it, and if you
  1909. 1:57:22haven't subscribed to this channel,
  1910. 1:57:23please do subscribe. See you in the
  1911. 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.