Chapter 09 - Additive Models, Trees, and Related Methods.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 9 - Additive Models, Trees, and Related Methods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Section 9.1 - Generalized Additive Models\n",
    "* Traditional linear model often fail to account for the non-linearity of real life effects.\n",
    "    * Traditional linear model\n",
    "        * $E(Y|X_1, X_2, \\dots, X_p) = \\alpha + \\beta_1X_1 + \\beta_2X_2 + \\dots  + \\beta_pX_p$.\n",
    "    * Generalized additive model\n",
    "        * $E(Y|X_1, X_2, \\dots, X_p) = \\alpha + f_1(X_1) + f_2(X_2) + \\dots  + f_p(X_p)$.\n",
    "    * where $\\beta$ is a constant and $f$ is some smooth function.\n",
    "    \n",
    "    \n",
    "* Additivity/interprebility is retained but the model is now more flexible.\n",
    "* Typically, we relate the conditional mean to the predictors via a link function:\n",
    "    * $g[u(X)] = \\alpha + f_1(X_1) + f_2(X_2) + \\dots  + f_p(X_p)$.\n",
    "    * Classical link functions are\n",
    "        * $g(\\mu) = \\mu$ - identity link\n",
    "        * $g(\\mu) = logit(\\mu)$ - probit link for modeling binomial probabilities.\n",
    "        * $g(\\mu) = log(\\mu)$ - for log-linear or log-additive models for Poisson count data.\n",
    "    * All three of these arise from exponential family sampling models, which also include gamma and negative-binomial distributions. These families generate the well-known class of generalized linear models. These can be extended in the same way to generalized additive models.\n",
    "\n",
    "\n",
    "* $f_j$ are estimated using an algorithm whose basic building block is a scatterplot smoother. For example, a cubic smoothing spline with knots at each of the unique values of $x_ij$. Continually cycle $j=1,2,\\dots,p,1,2,\\dots,p,\\dots$ until the spline approximations $\\hat{f}_j$ change less than a prescribed threshold. This same algorithm can be generalized to use other smoother operators such as kernel methods.\n",
    "\n",
    "* $f_j$ can reveal possible non-linearities in the effect of $X_j$, but need not necessarily be non-linear.\n",
    "\n",
    "* Additive models can be fit with a scatterplot smoother (e.g. smoothing spline). It can be shown that a cubic smoothing spline minimizes a penalized RSS criteria. \n",
    "\n",
    "* The iterative method for finding the solution is known as \"backfitting\". \n",
    "\n",
    "* Additive models provide a useful extension of linear models, making them more flexible while still retaining much of their interpretability.\n",
    "\n",
    "* Backfitting fits all predictors, which is not feasible or desirable for large number of variables. Regularized versions have been researched recently.  This is a limitation of additive models for large scale data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Section 9.2 - Tree-Based Methods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Background__\n",
    "* Tree based methods partition the feature space into a set of rectangles, then fit a simple model (e.g. constant) in each one.\n",
    "* The regions are created through recursive binary partitioning where each region has a split point $X_j <= s$.\n",
    "* The optimal $X_j$ and $s$ to use for splitting is determined by some objective criteria.\n",
    "* This recursive process is terminated by applying some stopping rule.\n",
    "* For regression trees, the prediction is the average of the observed variable in the last partition (the leaves).\n",
    "* A feature space is fully described by a single tree -- this makes the model interpretable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Regression Trees**\n",
    "* Suppose we model our response as a constant in each region, and seek to minimize the SSE criteria. The best \"constant\" to choose in each region is simply the average of the observed response.  \n",
    "* Finding the best binary partition in is generally computationally infeasible, so we use a greedy algorithm.\n",
    "* At each level of the binary tree, we seek to minimize the sum of the SSE in each resulting binary region.  We can do this by scanning through the inputs to find the best $(j, s)$ pair. This process is repeated until a stopping criteria is met.\n",
    "* A large tree might overfit the data, while a small tree might not capture the important structure.\n",
    "* Strategies for controlling complexity:\n",
    "    * Split tree only if decrease in SSE exceeds some threshold -- short sighted because a worthless split might lead to a good split later on.\n",
    "    * Stop splitting process only when some minimum node size is reached, then prune using cost-complexity pruning. Ths is preferred.\n",
    "* Cost complexity pruning seeks to find the best sub-tree to minimize some objective criteria. This criteria has a tuning parameter to balance the trade-off between tree size and goodness of fit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Classification Trees**\n",
    "* If the target is a classification outcome, the only changes needed pertain to the splitting criteria.\n",
    "* The squared error node impurity measure is not suitable for classification.\n",
    "* We classify the observations in node $m$ to the majority class in node $m$.\n",
    "* Different measure of impurity include. For 2 classes, suppose $p$ is the proportion in the second class in the region.\n",
    "    * Misclassfication error = $1-max(p, 1-p)$ (not differentiable)\n",
    "    * Gini index = $2p(1-p)$ (differentiable)\n",
    "    * Cross-entropy or deviance = $-plogp-(1-p)log(1-p)$ (differentiable)\n",
    "* Because misclassifaction error is not differentiable, it does not lend itself well to optimization.\n",
    "* Gini & cross-entropy are more sensitive to changes in node probabilities."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Categorical Predictors**\n",
    "* The partitioning algorithm tends to favor categorical predictors with many levels q; the number of partitions grows exponentially in q, and the more choices we have, the more likely we can find a good one for the data at hand. This can lead to severe overfitting if q is large, and such variables should be avoided."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Missing Data**\n",
    "* Better to replace \"null\" with a \"missing\" category for categorical data.\n",
    "* Best procedure is to define surrogate variables: At each split decision we create multiple splitting rules and rank them based on effectiveness. We choose the best rule such that we do not have missing data for applying that rule.\n",
    "\n",
    "**Binary Splits**\n",
    "* It is natural to wonder why we use only binary splits -- multi-way splits cause too much data fragmentation too quickly.\n",
    "\n",
    "**Linear Combination Splits**\n",
    "* It is also possible to split on optimized linear combination of variables instead of a constant in 1 variable. However, this can hurt interpretability.\n",
    "\n",
    "**Limitations**\n",
    "* Trees are high variance which can be problematic. A small change in data can create a much different series of splits. Bagging (tree averaging) can help with this.\n",
    "\n",
    "* Prediction surface is not smooth and they also have difficulty capturing additive structure. The MARS procedure can help alleviate these problems."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Spam Example**\n",
    "* Sensitivity: probability of predicting disease given true state is disease.\n",
    "* Specificity: probability of predicting non-disease given true state is non- disease.\n",
    "* The receiver operating characteristic curve (ROC) is a commonly used summary for assessing the tradeoff between sensitivity and specificity. \n",
    "* The area under the ROC curve, used above, is sometimes called the c-statistic. Interestingly, it can be shown that the area under the ROC curve is equivalent to the Mann-Whitney U statistic (or Wilcoxon rank-sum test), for the median difference between the prediction scores in the two groups (Hanley and McNeil, 1982)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.3 - PRIM: Bump Hunting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Tree-based methods (for regression) partition the feature space into box- shaped regions, to try to make the response averages in each box as different as possible. The splitting rules defining the boxes are related to each through a binary tree, facilitating their interpretation.\n",
    "* The patient rule induction method (PRIM) also finds boxes in the feature space, but seeks boxes in which the response average is high. Hence it looks for maxima in the target function, an exercise known as bump hunting. (If minima rather than maxima are desired, one simply works with the negative response values.)\n",
    "\n",
    "**Algorithm 9.3 Patient Rule Induction Method**\n",
    "1. Start with all of the training data, and a maximal box containing all\n",
    "of the data.\n",
    "2. Consider shrinking the box by compressing one face, so as to peel off the proportion α of observations having either the highest values of a predictor $X_j$, or the lowest. Choose the peeling that produces the highest response mean in the remaining box. (Typically α = 0.05 or 0.10.)\n",
    "3. Repeat step 2 until some minimal number of observations (say 10) remain in the box.\n",
    "4. Expand the box along any face, as long as the resulting box mean increases.\n",
    "5. Steps 1–4 give a sequence of boxes, with different numbers of observations in each box. Use cross-validation to choose a member of the sequence. Call the box $B_1$.\n",
    "6. Remove the data in box $B_1$ from the dataset and repeat steps 2–5 to obtain a second box, and continue to get as many boxes as desired."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.4 - MARS: Multivariate Adaptive Regression Splines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* MARS is an adaptive procedure for regression, and is well suited for high-dimensional problems. \n",
    "* It can be viewed as a generalization of stepwise linear regression or a modification of the CART method to improve the latter’s performance in the regression setting.\n",
    "* A reflected pair linear basis function is defined for each input point ($2Np$ basis functions for input space $\\mathbb{R}^p$).\n",
    "* Model building strategy is like forward stepwise regression, but instead of using the original inputs, we can use the basis functions and their products. Each input is restricted to appear at most once in a product.\n",
    "* After the forward-pass, we usually have an overfit model, so a backwards deletion process is applied. The term whose removal causes the smallest increase in residual squared error is removed. Continue until we reach a specific number of terms ($\\lambda$). We can select optimal $\\lambda$ using a cross-validation procedure.\n",
    "* Restrictions can be put in place to disallow more than 2 or 3 pairwise products when computing the additive basis term.\n",
    "\n",
    "**Connection to CART**\n",
    "* Take MARS and replace piecewise linear basis functions by step functions $I(x-t > 0)$ and $I(x-t < 0)$.\n",
    "* When a model term is involved in a multiplication by a candidate term, it gets replaced by the interaction, and hence is not available for further interactions.\n",
    "* These 2 modifications, the MARS forward procedure is the same as CART."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.5 - Hierarchical Mixtures of Experts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The hierarchical mixtures of experts (HME) procedure can be viewed as a variant of tree-based methods. The main difference is that the tree splits are not hard decisions but rather soft probabilistic ones. At each node an observation goes left or right with probabilities depending on its input values. \n",
    "* In an HME, a linear (or logistic regression) model is fit in each terminal node, instead of a constant as in CART.\n",
    "* Terminal nodes are called \"experts\" while non-terminal nodes are called \"gating networks.\"\n",
    "* By using soft splits rather than hard decision rules, it can capture situations where the transition from low to high response is gradual.\n",
    "* A limitation is that there are no methods for finding a good/optimal tree topology for HME."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.6 - Missing Data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Data may not be missing \"at random\", meaning the missing data has distorted the observed data. Data are missing at random if the mechanism resulting in its omission is independent of its unobserved value.\n",
    "* For example, if a patient's measurement was not taken because the doctor felt he was too sick, this observation is not missing at random.\n",
    "* Data imputation (such as mean) can be dangerous in situations where data is not missing at random.\n",
    "* If the features have at least some moderate degree of dependence, one can do better (than computing mean/median) by estimating a predictive model for each feature given the other features and then imputing each missing value by its prediction from the model."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.7 - Computation Considerations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Given N observations and p predictors:\n",
    "    * Additive fitting requires $mp$ application of a one dimensional smoother where $m$ is the number of cycles of the backfitting algorithm (usually less than 20).\n",
    "    * Trees require $pNlogN$ operations for an initial sort of each predictor and between $pNlogN$ and $N^2p$ operations for the split computations.\n",
    "    * MARS requires $Nm^2 + pmN$ operations to add basis functions to a model with $m$ terms already present.  So an $M$ term model requires $NM^3 + pM^2N$ operations.\n",
    "    * HME requires $Np^2$ for regressions and $Np^2K^2$ for a $K$-class logistic regression. They are considered costly to fit for sizable data because the EM algorithm takes a long time to converge.\n",
    "    "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}