Tree_example.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# Let’s use a simple example data to demonstrate how XGBoost algorithm works\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "bc0903359dff077a"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### A) on a regression problem.\n",
    "\n",
    "Let’s use a simple example data to demonstrate how XGBoost algorithm works on a regression problem.\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "6f0b0feaca667696"
  },
  {
   "cell_type": "raw",
   "source": [
    "X\t|\tY   \n",
    "==========\n",
    "5\t|\t1   \n",
    "8\t|\t2   \n",
    "15\t|\t8   \n",
    "20\t|\t4       \n",
    "-9 \t|   0   "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "c2577e007babce64"
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### Step 1. Set an initial prediction\n",
    "Let’s set the initial prediction (F0(x)) to be 3. In other words, regardless of the value of X, the predicted Y will be 3 - mean value.\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "4744bcf8199fa154"
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "outputs": [
    {
     "data": {
      "text/plain": "3.0"
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [5,8,15,20,-9]\n",
    "y = [1,2,8,4,0]\n",
    "pred_0 = sum(y) / len(y)\n",
    "pred_0"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:01.869285500Z",
     "start_time": "2023-12-01T18:58:01.812436500Z"
    }
   },
   "id": "c2061c203d833af"
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (999749795.py, line 2)",
     "output_type": "error",
     "traceback": [
      "\u001B[1;36m  Cell \u001B[1;32mIn[18], line 2\u001B[1;36m\u001B[0m\n\u001B[1;33m    ============================\u001B[0m\n\u001B[1;37m    ^\u001B[0m\n\u001B[1;31mSyntaxError\u001B[0m\u001B[1;31m:\u001B[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "X\t|\tY   |\tPred_0(mean)\n",
    "============================\n",
    "5\t|\t1   |\t3\n",
    "8\t|\t2   |\t3\n",
    "15\t|\t8   |\t3\n",
    "20\t|\t4   |\t3\n",
    "-9 \t|   0   |\t3"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:08.202567800Z",
     "start_time": "2023-12-01T18:58:08.170655700Z"
    }
   },
   "id": "e0d6d52f657fd0b"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Step 2. Calculate the residuals\n",
    "In this step we calculate the difference between the actual value (Y) and the predicted value (F0(x)).\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "22634783a4658d8a"
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "outputs": [
    {
     "data": {
      "text/plain": "[-2.0, -1.0, 5.0, 1.0, -3.0]"
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res_0 = []\n",
    "for i in range(len(y)):\n",
    "    res_0.append(y[i] - pred_0)\n",
    "res_0"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:09.920968700Z",
     "start_time": "2023-12-01T18:58:09.827219Z"
    }
   },
   "id": "c44aec44377a580a"
  },
  {
   "cell_type": "raw",
   "source": [
    "X\t|\tY   |Pred_0 |res_0 \n",
    "============================\n",
    "5\t|\t1   |\t3   | -2\n",
    "8\t|\t2   |\t3   | -1\n",
    "15\t|\t8   |\t3   |  5\n",
    "20\t|\t4   |\t3   |  1\n",
    "-9 \t|   0   |\t3   | -3"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "fcfa35ad44273d0c"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Step 3. Train model on the residuals\n",
    "\n",
    "Here, we build one or more tree-based models that are trained on [X, res].\n",
    "\n",
    "The following shows how a tree model is constructed."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "ec8b20a7cec723fe"
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### A) Generate split candidates ####\n",
    "\n",
    "In this step we find one or more split candidates. The formula is with N rows we would have N - 1 split candidates.\n",
    "\n",
    "With our dataset example, here’s the result."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "dfc44ee82b95b50d"
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid character '—' (U+2014) (975836391.py, line 10)",
     "output_type": "error",
     "traceback": [
      "\u001B[1;36m  Cell \u001B[1;32mIn[21], line 10\u001B[1;36m\u001B[0m\n\u001B[1;33m    ————————————————————————————————————————————————————————————————————————> threshold = (-9 + 5) / 2 = -2\u001B[0m\n\u001B[1;37m    ^\u001B[0m\n\u001B[1;31mSyntaxError\u001B[0m\u001B[1;31m:\u001B[0m invalid character '—' (U+2014)\n"
     ]
    }
   ],
   "source": [
    "Raw NBConvert\n",
    "\n",
    "\n",
    "===== Candidate Split 1 =====\n",
    "\n",
    "X\t|\tY   |Pred_0 |res_0 \n",
    "\n",
    "============================\n",
    "-9 \t|   0   |\t3   | -3\n",
    "————————————————————————————————————————————————————————————————————————> threshold = (-9 + 5) / 2 = -2\n",
    "5\t|\t1   |\t3   | -2\n",
    "8\t|\t2   |\t3   | -1\n",
    "15\t|\t8   |\t3   |  5\n",
    "20\t|\t4   |\t3   |  1\n",
    "\n",
    "\n",
    "===== Candidate Split 2 =====\n",
    "X\t|\tY   |Pred_0 |res_0 \n",
    "============================\n",
    "-9 \t|   0   |\t3   | -3\n",
    "5\t|\t1   |\t3   | -2\n",
    "————————————————————————————————————————————————————————————————————————> threshold = (5 + 8) / 2 = 6.5\n",
    "8\t|\t2   |\t3   | -1\n",
    "15\t|\t8   |\t3   |  5\n",
    "20\t|\t4   |\t3   |  1\n",
    "\n",
    "===== Candidate Split 3 =====\n",
    "\n",
    "X\t|\tY   |Pred_0 |res_0 \n",
    "============================\n",
    "-9 \t|   0   |\t3   | -3\n",
    "5\t|\t1   |\t3   | -2\n",
    "8\t|\t2   |\t3   | -1\n",
    "————————————————————————————————————————————————————————————————————————> threshold = (8 + 15) / 2 = 11.5\n",
    "15\t|\t8   |\t3   |  5\n",
    "20\t|\t4   |\t3   |  1\n",
    "\n",
    "===== Candidate Split 4 =====\n",
    "\n",
    "X\t|\tY   |Pred_0 |res_0 \n",
    "============================\n",
    "-9 \t|   0   |\t3   | -3\n",
    "5\t|\t1   |\t3   | -2\n",
    "8\t|\t2   |\t3   | -1\n",
    "15\t|\t8   |\t3   |  5\n",
    "————————————————————————————————————————————————————————————————————————> threshold = (15 + 20) / 2 = 22.5\n",
    "20\t|\t4   |\t3   |  1\n",
    "\n",
    "\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:30.647956400Z",
     "start_time": "2023-12-01T18:58:30.528276800Z"
    }
   },
   "id": "c849636145851e44"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The threshold will be used to create two child nodes. \n",
    "\n",
    "Here’s the complete parent-child nodes for each candidate."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "ce56379bedfb4e0"
  },
  {
   "cell_type": "markdown",
   "source": [
    "===== Candidate Split 1 =====\n",
    "\n",
    "Parent node -> X < -2\n",
    "Left child node, res_0 -> [-3]\n",
    "Right child node, res_0 -> [-2, -1, 5, 1]\n",
    "\n",
    "===== Candidate Split 2 =====\n",
    "\n",
    "Parent node -> X < 6.5\n",
    "Left child node -> [-3, -2]\n",
    "Right child node -> [-1, 5, 1]\n",
    "\n",
    "===== Candidate Split 3 =====\n",
    "\n",
    "Parent node -> X < 11.5\n",
    "Left child node -> [-3, -2, -1]\n",
    "Right child node -> [5, 1]\n",
    "\n",
    "===== Candidate Split 4 =====\n",
    "\n",
    "Parent node -> X < 22.5\n",
    "Left child node -> [-3, -2, -1, 5]\n",
    "Right child node -> [1]\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "e97164fc624a8e4e"
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### B) Select the split\n",
    "From step (A) we generate one or more split candidates. The question is how to select the best one?\n",
    "\n",
    "In XGBoost, we select the best split by leveraging what are called as Similarity Score and Gain. Gain is calculated for the parent node, while Similarity Score is calculated for the child nodes. We select a candidate with the maximum Gain.\n",
    "\n",
    "Here are the formulas."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "cd998964dd514ed5"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Gain = Left_similarity_score + Right_similarity_score - Root_similarity_score\n",
    "\n",
    "Similarity_score = SUM(residual_i)**2 / {SUM(prev_proba_i x (1 - prev_proba_i)) + lambda}\n",
    "\n",
    "But in this case we will consider all possible trees with depth = 2\n",
    "\n",
    "we have \n",
    "lamda = 1\n",
    "gamma = 5\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "c53b2818b86b5e0b"
  },
  {
   "cell_type": "markdown",
   "source": [
    "\n",
    "\n",
    "===== Candidate Split 1 =====\n",
    "\n",
    "Parent node -> X < -2\n",
    "Left child node, res_0 -> [-3]\n",
    "Right child node, res_0 -> [-2, -1, 5, 1]\n",
    "\n",
    "SS_root = (-3 -2 - 1 + 5 + 1)**2 / (5 + 1) = 0\n",
    "SS_left = (-3)**2 / (1 + 1)= 9/2 = 4.5\n",
    "SS_right = (-2 - 1 + 5 + 1)**2 / (4 + 1)= 9/5 = 1.8\n",
    "Gain = 4.5 + 1.8 - 0 - 5 = 0.3 > 0 => SPLITTING\n",
    "\n",
    "    ___SPLIT1.1___\n",
    "    \n",
    "    left - nothing to split - 1 element\n",
    "    right:\n",
    "        ___SPLIT1.11___\n",
    "        \n",
    "        Parent node -> X < 6.5\n",
    "        Left child node -> [-2]\n",
    "        Right child node -> [-1, 5, 1] \n",
    "        \n",
    "        SS_root = (-2 - 1 + 5 + 1)**2 / (4 + 1)= 9/5 = 1.8\n",
    "        SS_left = (-2)**2 / (1 + 1)= 4/2 = 2\n",
    "        SS_right = (- 1 + 5 + 1)**2 / (3 + 1)= 25/4 = 6.25\n",
    "        Gain = 2 + 6.25 - 1.8 - 5 = 1.45 > 0 => SPLITTING\n",
    "        \n",
    "        ___SPLIT1.12___\n",
    "\n",
    "        Parent node -> X < 11.5\n",
    "        Left child node -> [-2, -1]\n",
    "        Right child node -> [5, 1]\n",
    "        \n",
    "        SS_root = (-2 - 1 + 5 + 1)**2 / (4 + 1)= 9/5 = 1.8\n",
    "        SS_left = (-2 - 1)**2 / (2 + 1)= 9/3 = 3\n",
    "        SS_right = (5 + 1)**2 / (2 + 1)= 36/3 = 12\n",
    "        Gain = 3 + 12 - 1.8 - 5 = 8.2 > 0 => SPLITTING\n",
    "        \n",
    "        ___SPLIT1.13___\n",
    "\n",
    "        Parent node -> X < 22.5\n",
    "        Left child node -> [-2, -1, 5]\n",
    "        Right child node -> [1]\n",
    "        \n",
    "        SS_root = (-2 - 1 + 5 + 1)**2 / (4 + 1)= 9/5 = 1.8\n",
    "        SS_left = (-2 - 1 + 5)**2 / (2 + 1)= 4/3 = 1.3\n",
    "        SS_right = ( 1)**2 / (1 + 1)= 1/2 = 0.5\n",
    "        Gain = 1.3 + 0.5 - 1.8 - 5 = -5 < 0 => NO SPLITTING        \n",
    "        \n",
    "\n",
    "===== Candidate Split 2 =====\n",
    "\n",
    "Parent node -> X < 6.5\n",
    "Left child node -> [-3, -2]\n",
    "Right child node -> [-1, 5, 1]\n",
    "\n",
    "SS_root = (-3 -2 - 1 + 5 + 1)**2 / (5 + 1) = 0\n",
    "SS_left = (-3 - 2)**2 / (2 + 1)= 25/3 = 8.3\n",
    "SS_right = (- 1 + 5 + 1)**2 / (3 + 1)= 25/4 = 6.25\n",
    "Gain = 8.3 + 6.25 - 0 - 5 = 9.58 > 0 => SPLITTING\n",
    "\n",
    "    ___SPLIT2.1___\n",
    "    \n",
    "    left:\n",
    "        ___SPLIT2.11___\n",
    "        \n",
    "        Parent node -> X < -2\n",
    "        Left child node, res_0 -> [-3]\n",
    "        Right child node, res_0 -> [-2]\n",
    "        \n",
    "        SS_root = (-3 - 2)**2 / (2 + 1)= 25/3 = 8.3\n",
    "        SS_left = (-3)**2 / (1 + 1)= 9/2 = 4.5\n",
    "        SS_right = (-2)**2 / (1 + 1)= 24/2 = 12\n",
    "        Gain = 4.5 + 12 - 8.3 - 5 = 3.2 > 0 => SPLITTING\n",
    "     \n",
    "\n",
    "    right:\n",
    "        ___SPLIT2.12___\n",
    "\n",
    "        Parent node -> X < 11.5\n",
    "        Left child node -> [-1]\n",
    "        Right child node -> [5, 1]\n",
    "        \n",
    "        SS_root = (- 1 + 5 + 1)**2 / (3 + 1)= 25/4 = 6.25\n",
    "        SS_left = (- 1)**2 / (1 + 1)= 1/2 = 0.5\n",
    "        SS_right = (5 + 1)**2 / (2 + 1)= 36/3 = 12\n",
    "        Gain = 0.5 + 12 - 6.25 - 5 = 1.25 > 0 => SPLITTING\n",
    "        \n",
    "        ___SPLIT1.13___\n",
    "\n",
    "        Parent node -> X < 22.5\n",
    "        Left child node -> [-1, 5]\n",
    "        Right child node -> [1]\n",
    "        \n",
    "        SS_root = (- 1 + 5 + 1)**2 / (3 + 1)= 25/4 = 6.25\n",
    "        SS_left = (- 1 + 5)**2 / (2 + 1)= 16/3 = 5.3\n",
    "        SS_right = ( 1)**2 / (1 + 1)= 1/2 = 0.5\n",
    "        Gain = 5.3 + 0.5 - 6.25 - 5 = -5.45 < 0 => NO SPLITTING \n",
    "\n",
    "===== Candidate Split 3 =====\n",
    "\n",
    "Parent node -> X < 11.5\n",
    "Left child node -> [-3, -2, -1]\n",
    "Right child node -> [5, 1]\n",
    "\n",
    "SS_root = (-3 -2 - 1 + 5 + 1)**2 / (5 + 1) = 0\n",
    "SS_left = (-3 - 2 - 1)**2 / (3 + 1)= 36/4 = 9\n",
    "SS_right = (5 + 1)**2 / (2 + 1)= 36/3 = 12\n",
    "Gain = 9 + 12 - 0 - 5 = 16 > 0 => SPLITTING\n",
    "\n",
    "    ___SPLIT3.1___\n",
    "    \n",
    "    left:\n",
    "        ___SPLIT3.11___\n",
    "        \n",
    "        Parent node -> X < -2\n",
    "        Left child node, res_0 -> [-3]\n",
    "        Right child node, res_0 -> [-2, -1]\n",
    "        \n",
    "        SS_root = (-3 - 2 - 1)**2 / (3 + 1)= 36/4 = 9\n",
    "        SS_left = (-3)**2 / (1 + 1)= 9/2 = 4.5\n",
    "        SS_right = (-2 - 1)**2 / (2 + 1)= 9/3 = 3\n",
    "        Gain = 4.5 + 3 - 9 - 5 = -5.5 <0 => NO SPLITTING\n",
    "        \n",
    "        ___SPLIT3.12___\n",
    "        \n",
    "        Parent node -> X < 6.5\n",
    "        Left child node, res_0 -> [-3, -2]\n",
    "        Right child node, res_0 -> [-1]\n",
    "        \n",
    "        SS_root = (-3 - 2 - 1)**2 / (3 + 1)= 36/4 = 9\n",
    "        SS_left = (-3 - 2)**2 / (2 + 1)= 25/3 = 8.3\n",
    "        SS_right = (- 1)**2 / (1 + 1)= 1/2 = 0.5\n",
    "        Gain = 8.3 + 0.5 - 9 - 5 = -5.2 <0 => NO SPLITTING\n",
    "        \n",
    "\n",
    "    right:\n",
    "        ___SPLIT3.13___\n",
    "\n",
    "        Parent node -> X < 22.5\n",
    "        Left child node -> [5]\n",
    "        Right child node -> [1]\n",
    "        \n",
    "        SS_root = (5 + 1)**2 / (2 + 1)= 36/3 = 12\n",
    "        SS_left = (5)**2 / (1 + 1)= 25/2 = 12.5\n",
    "        SS_right = (1)**2 / (1 + 1)= 1/2 = 0.5\n",
    "        Gain = 12.5 + 0.5 - 12 - 5 = -6 < 0 => NO SPLITTING \n",
    "    \n",
    "        \n",
    "\n",
    "===== Candidate Split 4 =====\n",
    "\n",
    "Parent node -> X < 22.5\n",
    "Left child node -> [-3, -2, -1, 5]\n",
    "Right child node -> [1]\n",
    "\n",
    "SS_root = (-3 -2 - 1 + 5 + 1)**2 / (5 + 1) = 0\n",
    "SS_left = (-3 - 2 - 1 + 5)**2 / (4 + 1)= 1/5 = 0.20\n",
    "SS_right = (1)**2 / (1 + 1)= 1/2 = 0.5\n",
    "Gain = 0.20 + 0.5 - 0 - 5 = -4.3 < 0 => NO SPLITTING"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "ff1bae12216cc388"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Let's take one of the possible trees and take a look on the model\n",
    "    "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "e7f0f7b51ae64faf"
  },
  {
   "cell_type": "markdown",
   "source": [
    "\n",
    "===== Candidate Split 2 =====\n",
    "\n",
    "Parent node -> X < 6.5\n",
    "Left child node -> [-3, -2]\n",
    "Right child node -> [-1, 5, 1]\n",
    "\n",
    "    ___SPLIT2.1___\n",
    "    \n",
    "    left:\n",
    "        ___SPLIT2.11___       \n",
    "        Parent node -> X < -2\n",
    "        Left child node, res_0 -> [-3]\n",
    "        Right child node, res_0 -> [-2]\n",
    "\n",
    "    right:\n",
    "        ___SPLIT2.12___\n",
    "        Parent node -> X < 11.5\n",
    "        Left child node -> [-1]\n",
    "        Right child node -> [5, 1]\n",
    "\n",
    "\n",
    "        \n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "4e1c98a3ba8b4eaa"
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### c) Calculate Output Values\n",
    "Output Values is calculated for all leaves of the decision tree.\n",
    "\n",
    "The formula is given by the following:"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "80aff5acaff6c93e"
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "closing parenthesis ']' does not match opening parenthesis '(' (1725511801.py, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001B[1;36m  Cell \u001B[1;32mIn[22], line 1\u001B[1;36m\u001B[0m\n\u001B[1;33m    Output Value = SUM(residual_i) / [SUM(n + lambda]\u001B[0m\n\u001B[1;37m                                                    ^\u001B[0m\n\u001B[1;31mSyntaxError\u001B[0m\u001B[1;31m:\u001B[0m closing parenthesis ']' does not match opening parenthesis '('\n"
     ]
    }
   ],
   "source": [
    "Output Value = SUM(residual_i) / [SUM(n + lambda]"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:42.296372600Z",
     "start_time": "2023-12-01T18:58:42.257472300Z"
    }
   },
   "id": "a36b56bec69dd6fe"
  },
  {
   "cell_type": "markdown",
   "source": [
    "\n",
    "===== Candidate Split 2 =====\n",
    "\n",
    "Parent node -> X < 6.5\n",
    "Left child node -> [-3, -2]\n",
    "Output  = (-3 - 2) / (2 + 1)= -5/3 = -1.6\n",
    "\n",
    "Right child node -> [-1, 5, 1]\n",
    "Output = (-1 + 5 -1) / (3 + 1)= 5/3 = 1.6\n",
    "\n",
    "    ___SPLIT2.1___\n",
    "    \n",
    "    left:\n",
    "        ___SPLIT2.11___\n",
    "        \n",
    "        Parent node -> X < -2\n",
    "        Left child node, res_0 -> [-3]\n",
    "        Output = (-3) / (1 + 1)= -3/2 = -1.5\n",
    "        \n",
    "        Right child node, res_0 -> [-2]\n",
    "        Output = (-2) / (1 + 1)= -2/2 = -1\n",
    "      \n",
    "     \n",
    "    right:\n",
    "        ___SPLIT2.12___\n",
    "\n",
    "        Parent node -> X < 11.5\n",
    "        Left child node -> [-1]\n",
    "        Output = (-1) / (1 + 1)= -1/2 = -0.5\n",
    "        \n",
    "        Right child node -> [5, 1]\n",
    "        Output = (5 + 1) / (2 + 1)= 6/3 = 2\n",
    "\n",
    "        "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "13922358f0eeb4c9"
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### d) Predict the new values using our chosen DT"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "3de8a99273ef69a1"
  },
  {
   "cell_type": "markdown",
   "source": [
    "pred_1 = pred_0 + learning_rate * (DT_0(x))\n",
    "Where: \n",
    "        pred_0 = 3 \n",
    "        learning_rate = 0.1"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "68df3bae985cebda"
  },
  {
   "cell_type": "raw",
   "source": [
    "X\t|\tY   |Pred_0 |res_0 |output |Pred_1 \n",
    "===========================================\n",
    "-9 \t|   0   |\t3   | -3   | -1.5  | 3 - (0.1 * 1.5) = 2.85   \n",
    "5\t|\t1   |\t3   | -2   | -1    | 3 - (0.1 * 1)   = 2.9\n",
    "8\t|\t2   |\t3   | -1   | -0.5  | 3 - (0.1 * 0.5) = 2.95\n",
    "15\t|\t8   |\t3   |  5   | 2     | 3 - (0.1 * 2)   = 2.8\n",
    "20\t|\t4   |\t3   |  1   | 2     | 3 - (0.1 * 2)   = 2.8\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "c053875e55a6a673"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### B) on a classification problem.\n",
    "\n",
    "Let’s use a simple example data to demonstrate how XGBoost algorithm works on a regression problem."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "e3b2771830461199"
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (2444926364.py, line 2)",
     "output_type": "error",
     "traceback": [
      "\u001B[1;36m  Cell \u001B[1;32mIn[23], line 2\u001B[1;36m\u001B[0m\n\u001B[1;33m    ==========\u001B[0m\n\u001B[1;37m    ^\u001B[0m\n\u001B[1;31mSyntaxError\u001B[0m\u001B[1;31m:\u001B[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "X\t|\tY\n",
    "==========\n",
    "-7\t|\t0\n",
    "5\t|\t0\n",
    "6\t|\t1\n",
    "8\t|\t1\n",
    "9 \t|   1 "
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:45.904507400Z",
     "start_time": "2023-12-01T18:58:45.873590Z"
    }
   },
   "id": "16bc6676852699f0"
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "outputs": [],
   "source": [
    "x = [-7, 5, 6, 8, 9]\n",
    "y = [0, 0, 1, 1, 1]"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:46.142871500Z",
     "start_time": "2023-12-01T18:58:46.090011400Z"
    }
   },
   "id": "928bd0e0da0f16e7"
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### Step 1. Set an initial prediction\n",
    "Let’s set the initial prediction (F0(x)) to be 0.6. In other words, regardless of the value of X, the predicted Y will be 3 - mean value.\n",
    "\n",
    "F(0)(mean) = (0 + 0 + 1 + 1 + 1)/ 5 = 0.6\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "d92053e4d3af33b5"
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (1740534946.py, line 2)",
     "output_type": "error",
     "traceback": [
      "\u001B[1;36m  Cell \u001B[1;32mIn[25], line 2\u001B[1;36m\u001B[0m\n\u001B[1;33m    ============================\u001B[0m\n\u001B[1;37m    ^\u001B[0m\n\u001B[1;31mSyntaxError\u001B[0m\u001B[1;31m:\u001B[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "X\t|\tY   |\tPred_0(mean)\n",
    "============================\n",
    "-7\t|\t0   |\t0.6\n",
    "5\t|\t0   |\t0.6\n",
    "6\t|\t1   |\t0.6\n",
    "8\t|\t1   |\t0.6\n",
    "9 \t|   1   |\t0.6"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:50.008841600Z",
     "start_time": "2023-12-01T18:58:49.904122500Z"
    }
   },
   "id": "dfc9ff29ccd158ba"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Step 2. Calculate the residuals and odds\n",
    "In this step we calculate the difference between the actual value (Y) and the predicted value (F0(x)).\n",
    "\n",
    "Also we will calculate odds according to next formula:\n",
    "    odds = p/(1-p)\n",
    "    \n",
    "And then we will calculate logarithm of odds\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "11a3d593e90e9a16"
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "outputs": [
    {
     "data": {
      "text/plain": "[-0.6, -0.6, 0.4, 0.4, 0.4]"
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res_0 = []\n",
    "pred_0 = 0.6\n",
    "for i in range(len(y)):\n",
    "    res_0.append(y[i] - pred_0)\n",
    "res_0"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:50.284106300Z",
     "start_time": "2023-12-01T18:58:50.251196200Z"
    }
   },
   "id": "fb38cc8e6b15b781"
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (3697008290.py, line 2)",
     "output_type": "error",
     "traceback": [
      "\u001B[1;36m  Cell \u001B[1;32mIn[27], line 2\u001B[1;36m\u001B[0m\n\u001B[1;33m    ========================================================\u001B[0m\n\u001B[1;37m    ^\u001B[0m\n\u001B[1;31mSyntaxError\u001B[0m\u001B[1;31m:\u001B[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "X\t|\tY   |\tPred_0(mean) |res_0 |odds_0 |log(odds_0)\n",
    "========================================================\n",
    "-7\t|\t0   |\t    0.6      |-0.6  | 1.5   | 0.405\n",
    "5\t|\t0   |\t    0.6      |-0.6  | 1.5   | 0.405\n",
    "6\t|\t1   |\t    0.6      | 0.4  | 1.5   | 0.405\n",
    "8\t|\t1   |\t    0.6      | 0.4  | 1.5   | 0.405\n",
    "9 \t|   1   |\t    0.6      | 0.4  | 1.5   | 0.405"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:50.459638200Z",
     "start_time": "2023-12-01T18:58:50.413759200Z"
    }
   },
   "id": "35efbc79453fc689"
  },
  {
   "cell_type": "markdown",
   "source": [],
   "metadata": {
    "collapsed": false
   },
   "id": "11ee5fe3f2e986bb"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Step 3. Train model on the residuals\n",
    "\n",
    "Here, we build one or more tree-based models that are trained on [X, res].\n",
    "\n",
    "The following shows how a tree model is constructed."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "46813820651ebf41"
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### A) Generate split candidates ####\n",
    "In this step we find one or more split candidates. The formula is with N rows we would have N - 1 split candidates.\n",
    "With our dataset example, here’s the result."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "df6b1fecc46a051e"
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid character '—' (U+2014) (263720272.py, line 8)",
     "output_type": "error",
     "traceback": [
      "\u001B[1;36m  Cell \u001B[1;32mIn[28], line 8\u001B[1;36m\u001B[0m\n\u001B[1;33m    ———————————————————————————————————————————————————————————————————————— > threshold = (-7 + 5) / 2 = 1\u001B[0m\n\u001B[1;37m    ^\u001B[0m\n\u001B[1;31mSyntaxError\u001B[0m\u001B[1;31m:\u001B[0m invalid character '—' (U+2014)\n"
     ]
    }
   ],
   "source": [
    "Raw NBConvert\n",
    "\n",
    "== == = Candidate Split 1 == == =\n",
    "\n",
    "X\t|\tY   |\tPred_0(mean) |res_0\n",
    "===================================\n",
    "-7\t|\t0   |\t    0.6      |-0.6\n",
    "———————————————————————————————————————————————————————————————————————— > threshold = (-7 + 5) / 2 = 1\n",
    "5\t|\t0   |\t    0.6      |-0.6\n",
    "6\t|\t1   |\t    0.6      | 0.4\n",
    "8\t|\t1   |\t    0.6      | 0.4\n",
    "9 \t|   1   |\t    0.6      | 0.4\n",
    "\n",
    "== == = Candidate Split 2 == == =\n",
    "\n",
    "X\t|\tY   |\tPred_0(mean) |res_0\n",
    "===================================\n",
    "-7\t|\t0   |\t    0.6      |-0.6\n",
    "5\t|\t0   |\t    0.6      |-0.6\n",
    "———————————————————————————————————————————————————————————————————————— > threshold = (5 + 6) / 2 = 5.5\n",
    "6\t|\t1   |\t    0.6      | 0.4\n",
    "8\t|\t1   |\t    0.6      | 0.4\n",
    "9 \t|   1   |\t    0.6      | 0.4\n",
    "\n",
    "\n",
    "== == = Candidate Split 3 == == =\n",
    "\n",
    "X\t|\tY   |\tPred_0(mean) |res_0\n",
    "===================================\n",
    "-7\t|\t0   |\t    0.6      |-0.6\n",
    "5\t|\t0   |\t    0.6      |-0.6\n",
    "6\t|\t1   |\t    0.6      | 0.4\n",
    "———————————————————————————————————————————————————————————————————————— > threshold = (6 + 8) / 2 = 7\n",
    "8\t|\t1   |\t    0.6      | 0.4\n",
    "9 \t|   1   |\t    0.6      | 0.4\n",
    "\n",
    "\n",
    "== == = Candidate Split 4 == == =\n",
    "\n",
    "X\t|\tY   |\tPred_0(mean) |res_0\n",
    "===================================\n",
    "-7\t|\t0   |\t    0.6      |-0.6\n",
    "5\t|\t0   |\t    0.6      |-0.6\n",
    "6\t|\t1   |\t    0.6      | 0.4\n",
    "8\t|\t1   |\t    0.6      | 0.4\n",
    "———————————————————————————————————————————————————————————————————————— > threshold = (8 + 9) / 2 = 8.5\n",
    "9 \t|   1   |\t    0.6      | 0.4\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:51.659369200Z",
     "start_time": "2023-12-01T18:58:51.582575200Z"
    }
   },
   "id": "20824486ad14930a"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The threshold will be used to create two child nodes.\n",
    "\n",
    "Here’s the complete parent-child nodes for each candidate."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "f801ee6c214e8341"
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (119867641.py, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001B[1;36m  Cell \u001B[1;32mIn[29], line 1\u001B[1;36m\u001B[0m\n\u001B[1;33m    ===== Candidate Split 1 =====\u001B[0m\n\u001B[1;37m    ^\u001B[0m\n\u001B[1;31mSyntaxError\u001B[0m\u001B[1;31m:\u001B[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "===== Candidate Split 1 =====\n",
    "\n",
    "Parent node -> X < 1\n",
    "Left child node, res_0 -> [-0.6]\n",
    "Right child node, res_0 -> [-0.6, 0.4, 0.4, 0.4]\n",
    "\n",
    "===== Candidate Split 2 =====\n",
    "\n",
    "Parent node -> X < 5.5\n",
    "Left child node -> [-0.6, -0.6]\n",
    "Right child node -> [0.4, 0.4, 0.4]\n",
    "\n",
    "===== Candidate Split 3 =====\n",
    "\n",
    "Parent node -> X < 7\n",
    "Left child node -> [-0.6, -0.6, 0.4]\n",
    "Right child node -> [0.4, 0.4]\n",
    "\n",
    "===== Candidate Split 4 =====\n",
    "\n",
    "Parent node -> X < 8.5\n",
    "Left child node -> [-0.6, -0.6, 0.4, 0.4]\n",
    "Right child node -> [0.4]\n"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:52.245848300Z",
     "start_time": "2023-12-01T18:58:52.220886100Z"
    }
   },
   "id": "f05a05d72e73a5fd"
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### B) Select the split\n",
    "From step (A) we generate one or more split candidates. \n",
    "\n",
    "In XGBoost, we select the best split by leveraging what are called as Similarity Score and Gain. Gain is calculated for the parent node, while Similarity Score is calculated for the child nodes. We select a candidate with the maximum Gain.\n",
    "\n",
    "Here are the formulas."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "9ca25c5f966bbd3b"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Gain = Left_similarity_score + Right_similarity_score - Root_similarity_score\n",
    "\n",
    "Similarity_score = SUM(residual_i)**2 / {SUM(prev_proba_i x (1 - prev_proba_i)) + lambda}\n",
    "\n",
    "For our example we  will take 1 random tree with depth = 2\n",
    "\n",
    "we have \n",
    "lamda = 1\n",
    "gamma = 0.2\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "c0355822268e6d17"
  },
  {
   "cell_type": "markdown",
   "source": [
    "== == = Candidate Split 2 == == =\n",
    "\n",
    "Parent node -> X < 5.5\n",
    "Left child node -> [-0.6, -0.6]\n",
    "Right child node -> [0.4, 0.4, 0.4]\n",
    "\n",
    "SS_root = (-0.6 - 0.6 + 0.4 + 0.4 + 0.4)**2 / (0.6*0.4 + 0.6*0.4 + 0.4*0.6 + 0.4*0.6 + 0.4*0.6  + 1) = 0\n",
    "SS_left = (-0.6 - 0.6)**2 / (2*(0.6*0.4) + 1)= 1.44/1.48 = 0.97\n",
    "SS_right = (0.4 + 0.4 + 0.4)**2 / (3*(0.6*0.4) + 1)= 1.44/1.72 = 0.83\n",
    "Gain = 0.97 + 0.83 - 0 - 0.2 = 1.6 > 0 => SPLITTING\n",
    "\n",
    "    ___SPLIT2.1___\n",
    "    \n",
    "    left:\n",
    "    ___SPLIT2.11___\n",
    "    \n",
    "    Parent node -> X < 1\n",
    "    Left child node, res_0 -> [-0.6]\n",
    "    Right child node, res_0 -> [-0.6]\n",
    "    \n",
    "    SS_root = (-0.6 - 0.6)**2 / (2*(0.6*0.4) + 1)= 1.44/1.48 = 0.97\n",
    "    SS_left = (-0.6)**2 / ((0.6*0.4) + 1)= 0.36/1.24 = 0.29\n",
    "    SS_right = (-0.6)**2 / ((0.6*0.4) + 1)= 0.36/1.24 = 0.29\n",
    "    Gain = 0.29 + 0.29 - 0.97 - 0.2  = -0.59 < 0 => NO SPLITTING\n",
    "\n",
    "    right:\n",
    "    ___SPLIT2.12___\n",
    "    \n",
    "    Parent node -> X < 7\n",
    "    Left child node -> [0.4]\n",
    "    Right child node -> [0.4, 0.4]\n",
    "    \n",
    "    SS_root = (0.4 + 0.4 + 0.4)**2 / (3*(0.6*0.4) + 1)= 1.44/1.72 = 0.83\n",
    "    SS_left = (0.4)**2 / ((0.6*0.4) + 1)= 0.16/1.24 = 0.12\n",
    "    SS_right = (0.4 + 0.4)**2 / (2*(0.6*0.4) + 1)= 0.64/1.48 = 0.43\n",
    "    Gain = 0.12 + 0.43 - 0.83 - 0.2  = -0.48 < 0 => NO SPLITTING\n",
    "    \n",
    "    right:\n",
    "    ___SPLIT2.13___\n",
    "    \n",
    "    Parent node -> X < 8.5\n",
    "    Left child node -> [0.4, 0.4]\n",
    "    Right child node -> [0.4]\n",
    "    \n",
    "    calculations symmetrical to ___SPLIT2.12___\n",
    "    \n",
    "    SS_root = (0.4 + 0.4 + 0.4)**2 / (3*(0.6*0.4) + 1)= 1.44/1.72 = 0.83\n",
    "    SS_left = (0.4)**2 / ((0.6*0.4) + 1)= 0.16/1.24 = 0.12\n",
    "    SS_right = (0.4 + 0.4)**2 / (2*(0.6*0.4) + 1)= 0.64/1.48 = 0.43\n",
    "    Gain = 0.12 + 0.43 - 0.83 - 0.2  = -0.48 < 0 => NO SPLITTING\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "b54882a61a5ccb2e"
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### c) Calculate Output Values\n",
    "Output Values is calculated for all leaves of the decision tree.\n",
    "\n",
    "The formula is given by the following:\n",
    "Output Value = SUM(residual_i) / [SUM(prev_proba_i x (1 - prev_proba_i)) + lambda]\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "ad0f841acd2999cc"
  },
  {
   "cell_type": "markdown",
   "source": [
    "== == = Candidate Split 2 == == =\n",
    "\n",
    "Parent node -> X < 5.5\n",
    "Left child node -> [-0.6, -0.6]\n",
    "Right child node -> [0.4, 0.4, 0.4]\n",
    "\n",
    "Output_left = (-0.6 - 0.6) / (2*(0.6*0.4) + 1)= -1.2/1.48 = -0.81\n",
    "Output_right = (0.4 + 0.4 + 0.4) / (3*(0.6*0.4) + 1)= 1.2/1.72 = 0.69\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "1fe41d012fa5f406"
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### d) Predict the new values using our chosen DT\n",
    "\n",
    "To predict the new values, we use the following formula.\n",
    "\n",
    "log(odds)_F1(x) = log(odds)_F0(x) + learning_rate * (DT_0(x))\n",
    "\n",
    "F1(x) is retrieved by computing e^log(odds)_F1(x) / [1 + e^log(odds)_F1(x)]\n",
    "\n",
    "Let’s apply this step to our dataset. Assume that learning_rate is set to 0.1."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "bf9a211c7db310c0"
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (9164966.py, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001B[1;36m  Cell \u001B[1;32mIn[30], line 1\u001B[1;36m\u001B[0m\n\u001B[1;33m    log(odds)_F1(-7) = 0.405 + 0.1*(-0.81) = - 0.324\u001B[0m\n\u001B[1;37m             ^\u001B[0m\n\u001B[1;31mSyntaxError\u001B[0m\u001B[1;31m:\u001B[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "log(odds)_F1(-7) = 0.405 + 0.1*(-0.81) = - 0.324\n",
    "log(odds)_F1(5) = 0.405 + 0.1*(-0.81) = - 0.324\n",
    "log(odds)_F1(6) = 0.405 + 0.1*(0.69) = 0.474\n",
    "log(odds)_F1(8) = 0.405 + 0.1*(0.69) = 0.474\n",
    "log(odds)_F1(9) = 0.405 + 0.1*(0.69) = 0.474\n",
    "\n",
    "F1(-7) = exp**(- 0.324)/ (1 + exp**(- 0.324) = 0.419\n",
    "F1(5) = exp**(0.474)/ (1 + exp**(0.474) = 0.616\n",
    "F1(6) = exp**(0.474)/ (1 + exp**(0.474) = 0.616\n",
    "F1(8) = exp**(0.474)/ (1 + exp**(0.474) = 0.616\n",
    "F1(9) = exp**(0.474)/ (1 + exp**(0.474) = 0.616"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:57.526863Z",
     "start_time": "2023-12-01T18:58:57.501877800Z"
    }
   },
   "id": "14d6d5915bb510bc"
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (872557540.py, line 2)",
     "output_type": "error",
     "traceback": [
      "\u001B[1;36m  Cell \u001B[1;32mIn[31], line 2\u001B[1;36m\u001B[0m\n\u001B[1;33m    ======================================================================\u001B[0m\n\u001B[1;37m    ^\u001B[0m\n\u001B[1;31mSyntaxError\u001B[0m\u001B[1;31m:\u001B[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "X\t|\tY   |\tPred_0(mean) |res_0 |odds_0 |log(odds_0)|Pred_1\n",
    "======================================================================\n",
    "-7\t|\t0   |\t    0.6      |-0.6  | 1.5   | 0.405     | 0.419\n",
    "5\t|\t0   |\t    0.6      |-0.6  | 1.5   | 0.405     | 0.419\n",
    "6\t|\t1   |\t    0.6      | 0.4  | 1.5   | 0.405     | 0.616\n",
    "8\t|\t1   |\t    0.6      | 0.4  | 1.5   | 0.405     | 0.616\n",
    "9 \t|   1   |\t    0.6      | 0.4  | 1.5   | 0.405     | 0.616"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-01T18:58:58.010566200Z",
     "start_time": "2023-12-01T18:58:57.865956400Z"
    }
   },
   "id": "9a520eea438f7fea"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### CatBoost\n",
    "\n",
    "#### 1. Initialization of Initial Prediction\n",
    "\n",
    "First, we need to initialize the initial prediction. In CatBoost, like in other gradient boosting algorithms, this is usually the mean value of the target variable.\n",
    "\n",
    "\\[\n",
    "F^{(0)}_{mean} = \\frac{\\sum Y}{N} = \\frac{1 + 2 + 8 + 4 + 0}{5} = \\frac{15}{5} = 3\n",
    "\\]\n",
    "\n",
    "| X    | Y    | Pred_0(mean) |\n",
    "| ---- | ---- | ------------ |\n",
    "| 5    | 1    | 3            |\n",
    "| 8    | 2    | 3            |\n",
    "| 15   | 8    | 3            |\n",
    "| 20   | 4    | 3            |\n",
    "| -9   | 0    | 3            |\n",
    "\n",
    "#### 2. Calculation of Residuals and Odds\n",
    "\n",
    "Next, we calculate the residuals and odds. Residuals are the difference between the actual target value and the predicted value at the previous step. Odds are calculated using the following formula:\n",
    "\n",
    "\\[\n",
    "odds = \\frac{p}{1 - p}\n",
    "\\]\n",
    "\n",
    "And then we calculate the logarithm of odds.\n",
    "\n",
    "| X    | Y    | Pred_0(mean) | Residuals | Odds_0 | Log(Odds_0) |\n",
    "| ---- | ---- | ------------ | --------- | ------ | ----------- |\n",
    "| 5    | 1    | 3            | -2        | 0.333  | -1.099      |\n",
    "| 8    | 2    | 3            | -1        | 0.5    | -0.693      |\n",
    "| 15   | 8    | 3            | 5         | 5      | 1.609       |\n",
    "| 20   | 4    | 3            | 1         | 0.667  | -0.405      |\n",
    "| -9   | 0    | 3            | -3        | 0.25   | -1.386      |\n",
    "\n",
    "#### 3. Training the Model on Residuals\n",
    "\n",
    "Now, we train the gradient boosting model on the residuals. CatBoost automatically solves the optimization problem and finds the optimal splits.\n",
    "\n",
    "#### 4. Calculation of Output Values\n",
    "\n",
    "Output Values are calculated for all leaves of the decision tree. The formula for calculating the Output Value is:\n",
    "\n",
    "\\[\n",
    "Output Value = \\frac{\\sum residual_i}{\\sum prev\\_proba_i \\cdot (1 - prev\\_proba_i) + \\lambda}\n",
    "\\]\n",
    "\n",
    "where \\( \\lambda \\) is the regularization coefficient.\n",
    "\n",
    "#### 5. Predicting New Values using the Chosen CatBoost Model\n",
    "\n",
    "Predicting new values is done using the formula:\n",
    "\n",
    "\\[\n",
    "\\log(odds)_{F1(x)} = \\log(odds)_{F0(x)} + learning\\_rate \\cdot DT_0(x)\n",
    "\\]\n",
    "\n",
    "where:\n",
    "\n",
    "- \\( F0(x) \\) is the prediction at the previous step,\n",
    "- \\( DT_0(x) \\) is the prediction of the model at the current step,\n",
    "- \\( learning\\_rate \\) is the learning rate.\n",
    "\n",
    "### LightGBM\n",
    "\n",
    "#### 1. Initialization of Initial Prediction\n",
    "\n",
    "Similar to CatBoost, the initial prediction in LightGBM is initialized with the mean value of the target variable.\n",
    "\n",
    "\\[\n",
    "F^{(0)}_{mean} = 3\n",
    "\\]\n",
    "\n",
    "| X    | Y    | Pred_0(mean) |\n",
    "| ---- | ---- | ------------ |\n",
    "| 5    | 1    | 3            |\n",
    "| 8    | 2    | 3            |\n",
    "| 15   | 8    | 3            |\n",
    "| 20   | 4    | 3            |\n",
    "| -9   | 0    | 3            |\n",
    "\n",
    "#### 2. Calculation of Residuals and Odds\n",
    "\n",
    "The calculation of residuals and odds is the same as for CatBoost.\n",
    "\n",
    "| X    | Y    | Pred_0(mean) | Residuals | Odds_0 | Log(Odds_0) |\n",
    "| ---- | ---- | ------------ | --------- | ------ | ----------- |\n",
    "| 5    | 1    | 3            | -2        | 0.333  | -1.099      |\n",
    "| 8    | 2    | 3            | -1        | 0.5    | -0.693      |\n",
    "| 15   | 8    | 3            | 5         | 5      | 1.609       |\n",
    "| 20   | 4    | 3            | 1         | 0.667  | -0.405      |\n",
    "| -9   | 0    | 3            | -3        | 0.25   | -1.386      |\n",
    "\n",
    "#### 3. Training the Model on Residuals\n",
    "\n",
    "Similar to CatBoost, we train the gradient boosting model on the residuals.\n",
    "\n",
    "#### 4. Calculation of Output Values\n",
    "\n",
    "Similar to CatBoost, we calculate Output Values for all leaves of the decision tree.\n",
    "\n",
    "#### 5. Predicting New Values using the Chosen LightGBM Model\n",
    "\n",
    "Predicting new values is also done using the formula:\n",
    "\n",
    "\\[\n",
    "\\log(odds)_{F1(x)} = \\log(odds)_{F0(x)} + learning\\_rate \\cdot DT_0(x)\n",
    "\\]\n",
    "\n",
    "where \\( F0(x) \\) is the prediction at the previous step, \\( DT_0(x) \\) is the prediction of the model at the current step, and \\( learning\\_rate \\) is the learning rate.\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "8c5cb53b433146d"
  },
  {
   "cell_type": "raw",
   "source": [],
   "metadata": {
    "collapsed": false
   },
   "id": "7b1c53f7c1c8affe"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}