29:null 2a:["$","title",null,{"children":"Function Fitting Crash Course | Jhelum Chakravorty | Observable"}] 2f:T596,html``30:T658,keypresscontrol= { document.cells = document.getElementsByClassName("observablehq"); document.current=2; document.stopnumber = document.cells.length- 5 //keymap document.onkeyup = function(e) { console.log(e) ; if (e.which === 83){console.log('re -s- tart'); document.current=2 var elmnt = document.cells[document.current] elmnt.scrollIntoView(); } if (e.which === 32| e.which === 39| e.which === 40){console.log('space'); document.current+=1 if (document.current < (document.stopnumber)){ var elmnt=document.cells[document.current]; if (elmnt.innerHTML != '

'){ elmnt.scrollIntoView(); } else { document.stopnumber = document.current; } }else{document.current = document.stopnumber } } if (e.which === 38 | e.which === 37){console.log('back'); document.current-=1 if (document.current <2){document.current = 2} var elmnt = document.cells[document.current] elmnt.scrollIntoView(); } } }31:T8a4,slide = { function slide() { const container = document.createElement("div"); container.className = "slide"; container.appendChild(md.apply(this, arguments)); return container; } function end() { const container = document.createElement("div"); container.className = "end"; return container; } slide.end = end; function iframe(strings) { const container = document.createElement("div"); container.innerHTML="" container.className = "slide"; return container; } slide.iframe=iframe; function html(strings) { const container = document.createElement("div"); container.innerHTML = strings; container.className = "slide slide--html"; return container; } slide.html = html; function htmldark(strings) { const container = document.createElement("div"); container.innerHTML = strings; container.className = "slide slide--html dark"; return container; } slide.htmldark = htmldark; function code(strings) { const container = document.createElement("div"); const pre = container.appendChild(document.createElement("pre")); const code = pre.appendChild(document.createElement("code")); let string = strings[0] + "", i = 0, n = arguments.length; while (++i < n) string += arguments[i] + "" + strings[i]; code.textContent = string.trim(); container.className = "slide slide--code"; return container; } slide.code = code; slide.js = function() { const container = code.apply(this, arguments); const content = container.firstChild.firstChild; content.className = "js hljs javascript"; hl.highlightBlock(content); return container; }; slide.img = function(strings) { const img = new Image; let string = strings[0] + "", i = 0, n = arguments.length; while (++i < n) string += arguments[i] + "" + strings[i]; img.src = string.trim(); img.className = "slide slide--img"; return img; }; return slide; }32:T4ed,slide`### Bias-variance tradeoff * The number of variables is one measure of model complexity * More variables -> lower bias but higher variance

* *Ridge Regression*: You can also "regularize" the fit, using ${mtex_block`\hat{\beta} = \left(X^{T}X + \lambda I\right)^{-1}X^{T}y`} Larger ${mtex`\lambda`} reduce model complexity:

${mtex `\lambda \rightarrow 0`}, ${mtex `\hat \beta_{\text{ridge}} \rightarrow \hat \beta_{\text{OLS}}; \qquad`} ${mtex `\lambda \rightarrow \infty`}, ${mtex `\hat \beta_{\text{ridge}} \rightarrow 0`}

* *Bias-variance trade-off in ridge*:

${mtex `\scriptsize \text{Bias}(\hat \beta_{\text{ridge}}) = - \lambda (X^{T}X + \lambda I)^{-1} \beta`} ${mtex `\scriptsize \text{Variance}(\hat \beta_{\text{ridge}}) = \sigma^2 (X^{T}X + \lambda I)^{-1} X^{T}X (X^{T}X + \lambda I)^{-1}`}

* Choice of ${mtex `\lambda`}. - Minimizing information criteria: estimate the model with many different values for ${mtex `\lambda`} and choose the one that minimizes the Akaike or Bayesian Information Criterion (AIC, BIC)

[Interactive demo](http://www.r2d3.us/visual-intro-to-machine-learning-part-2/)

`33:[] 2d:{"id":"2a3e1e590ca63231","slug":"function-fitting-crash-course","title":"Function Fitting Crash Course","thumbnail":"3cb32efcaa9a5e0671149965c1d4180a26bed7b54b8449b3d799b2fabe762e9c","access_level":"public","create_time":"$D2020-08-06T14:30:52.570Z","update_time":"$D2020-09-17T15:29:41.375Z","view_time":null,"first_public_time":"$D2020-08-06T14:39:57.220Z","has_unpublished_edits":null,"fork":{"id":"ab4ac413b366e0ee","slug":"function-fitting-crash-course","title":"Function Fitting Crash Course","owner":{"id":"58c635fe0c6a930c","login":"krisrs1128","name":"Kris Sankaran"}},"stars":1,"starred":false,"owner":{"type":"team","id":"f2fc5ebdd7876938","login":"jhelum-ch","name":"Jhelum Chakravorty","avatar_url":"https://avatars-next.observableusercontent.com/e83434a00e17e1552b4c063369c1a25828f14baddcc06570dd0b3dcd14b13b9d","tier":"starter_2024"},"version":796,"publish_version":796,"role":null,"authored":false,"authors":[{"type":"individual","id":"d5380db8be1a36e9","login":"jhelum-ch","name":"Jhelum Chakravorty","avatar_url":"https://avatars-next.observableusercontent.com/e83434a00e17e1552b4c063369c1a25828f14baddcc06570dd0b3dcd14b13b9d","tier":null}],"members":[{"type":"individual","id":"d5380db8be1a36e9","login":"jhelum-ch","name":"Jhelum Chakravorty","avatar_url":"https://avatars-next.observableusercontent.com/e83434a00e17e1552b4c063369c1a25828f14baddcc06570dd0b3dcd14b13b9d","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":7,"collection":null,"type":"notebook","body":{"title":"Function Fitting Crash Course","cells":[{"id":0,"value":"md`# Function Fitting Crash Course\n## KNN, Linear Regression, and their Relatives\nIFT 6758, Fall 2020; \nReading: [ISLR](http://faculty.marshall.usc.edu/gareth-james/ISL/ISLR%20Seventh%20Printing.pdf) sections 3.2.1, 3.3.1, 3.3.2, 3.5, 4.3, 7.2, 8.1\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":779,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"slide`### Goals of function fitting\n\n* Deeply understand mechanics of k-nearest neighbors (KNN) and linear models\n* See how bias-variance tradeoff and curse of dimensionality manifest themselves in these models\n* Get a feeling for how versatile the ideas in KNN and linear models can be\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"slide`### Why KNN and Linear Models?\n\n* These models are the foundation for nonparametric and parametric learning algorithms, respectively\n* Understanding strengths and limitations here will help with in other contexts\n\n

\nLocally Weighted Linear Regression (loess or lowess)\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":725,"value":"slide`### Parametric vs. Nonparametric Models\n\n* Parametric: Have a fixed complexity, that remains constant even as the number of samples grows \n * (fixed # of parameters)\n* Nonparametric: Has a complexity that grows with the number of samples that arrive \n * (growing # of effective parameters)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"slide`# KNN`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"slide`### Algorithm (KNN Regression)\n\nSay that we have ${mtex`n`} samples ${mtex`\\left(x_i, y_i\\right)_{i = 1}^{n}`}. Estimate the data generating function ${mtex`f`} by\n\n${mtex_block`\n\\begin{aligned}\n\\hat{f}\\left(x\\right) &= \\frac{1}{K}\\sum_{i \\in N_{K}\\left(x\\right)} y_i\n\\end{aligned}\n`}\nwhere ${mtex`N_{K}`} is the set of ${mtex`K`} nearest-neighbors of ${mtex`x`} within the training set.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"slide`### KNN Regression Picture\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"slide`### KNN Regression Picture\n\n

\n\nIf you move ${mtex`x`} a little, the nearest points don't change, so the prediction is the same.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"slide`### KNN Regression Picture\n\n

\n\nOnce a new point enters the neighborhood, the average over the neighborhood changes.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":"slide`### KNN Regression Picture\n\n

\n\nYou can do this over a fine grid to make an estimate of ${mtex`f`}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"slide`### Bias-variance tradeoff\n\nThe model complexity is controlled by the size of the neighborhood.\n* Large ${mtex`K`} --> Lower variance, larger bias\n* Small ${mtex`K`} --> Higher variance, smaller bias\n\nLarger ${mtex`K`} learns smoother functions that might not match the true function's wiggliness. Smaller ${mtex`K`} will be larger variance, but can match complex functions when the sampling density is high enough.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":81,"value":"slide`### Curse of Dimensionality\n\n* In higher dimensions, ${mtex`n`} the density of samples gets lower and lower\n* The lack of close-by neighbors increases both the bias and the variance\n* You end up needing to look at almost the whole space to make a prediction. Means you average over points that are quite different in terms of ${mtex`x`}.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":85,"value":"slide`### Classification\n\n* The method extends to classification. The probability that a location ${mtex`x`} gets assigned to class ${mtex`j`} is approximated by\n\n${mtex_block`\n\\begin{aligned}\n\\hat{p}_{k}\\left(x\\right) &= \\frac{1}{K}\\sum_{i \\in N_{K}\\left(x\\right)} \\indic{y_i = j}\n\\end{aligned}`}\nLooking at the class with top probability, this is like taking local majority votes.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"slide`### Classification\n\n* The method extends to classification. The probability that a location ${mtex`x`} gets assigned to class ${mtex`j`} is approximated by\n\n

\n\nLooking at the class with top probability, this is like taking local majority votes.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":718,"value":"slide`### Discussion\n\n* What are the pros and cons of KNN in practice?\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":721,"value":"slide`### Possible Answers\n\n* Pros\n * Possible to fit arbitrarily complex functions\n * Can achieve range of model complexities\n * Easy to inspect predictions\n* Cons\n * Looking up nearest neighbor can be computationally expensive\n * Deteriorates when there are many variables\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"slide`# Linear Regression`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":103,"value":"slide`### Definition (one-dimension)\n\n* Function family --> ${mtex`f_\\beta\\left(x\\right) = \\beta x`} for some ${mtex`\\beta`}\n * One unit increase in ${mtex`x`} increases mean prediction by ${mtex`\\beta`}\n* Choose ${mtex`\\beta`} so that ${mtex`\\sum_{i} \\left(y_i - f_{\\beta}\\left(x_i\\right)\\right)^ 2`} is small\n* This minimizes the vertical distances between ${mtex`y`} and ${mtex`f`}\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":112,"value":"slide`### Derivation (one-dimension)\n\n* Can do this in closed form,\n${mtex_block`\n\\begin{aligned}\n\\frac{\\partial}{\\partial \\beta} &\\sum_{i}\\left(y_i - \\beta x_i\\right)^{2} = 0 \\\\\n\\iff &\\sum_{i}x_i \\left(y_i - \\beta x_i\\right) = 0 \\\\\n\\iff &\\beta = \\frac{\\sum_{i} x_i y_i}{\\sum_{i} x_i^2}\n\\end{aligned}\n`}\nInterpretation: Each unit increase in ${mtex`x`} leads to an increase by one unit variance in ${mtex`y`}, shrunken by a factor determined by the correlation (compare with ISLR eqn. 3.18).\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"slide`### Definition (Higher Dimensions)\n\n* Function family --> ${mtex`f_\\beta\\left(x\\right) = x^{T}\\beta`} for some ${mtex`\\beta \\in \\reals^{p}`}\n * One unit increase in ${mtex`x_j`} increases mean prediction by ${mtex`\\beta_j`}\n* Choose ${mtex`\\beta`} to minimize ${mtex`\\sum_i \\left(y_i - x_i^{T} \\beta\\right)^{2}`}\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"slide`### Derivation (Higher Dimensions)\n\nThis can again be done analytically (but don't worry if you haven't seen the calculus / linear algebra),\n\n${mtex_block`\n\\begin{aligned}\n\\frac{\\partial}{\\partial \\beta} &\\sum_{i}\\left(y_i - x_i^{T}\\beta\\right)^{2} = 0 \\\\\n\\iff &\\sum_{i}x_i \\left(y_i - x_i^{T}\\beta\\right) = 0 \\\\\n\\iff &\\beta = \\left(\\sum_{i} x_i x_i^{T}\\right)^{-1}\\sum_{i} x_i y_i \\\\\n&= \\left(X^{T}X\\right)^{-1}X^{T}y\n\\end{aligned}\n`}\nThis is a generalization of the previous story.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"slide`### Curse of dimensionality\n\n* It's possible to show ${mtex`\\Earg{\\left(y_i - f_{\\hat{\\beta}}\\left(x_i\\right)\\right)^2 \\vert x_i} \\approx\\frac{p\\sigma^2}{n}`}\n * assuming the true function is linear\n* In high dimensions, functions **could** get exponentially rough\n * KNN tries to do well in all cases, and suffers as a result\n * By betting against exponential roughness, regression does better\n

\n\nLinear regression deteriorates linearly with dimension.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":268,"value":"slide`### Logistic Regression\n\n* For binary classification, say the probability of class 1 is ${mtex`\np_{\\beta}\\left(x\\right) = \\sigma\\left(x^{T}\\beta\\right)`}, where \n${mtex`\\sigma\\left(z\\right) = \\frac{\\exp{z}}{1 + \\exp{z}}`} \n* The transformation keeps the probability between 0 and 1\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":295,"value":"slide`### Logistic Regression\n\n* We can make this resemble linear regression,\n${mtex_block`\n\\begin{aligned}\n \\log\\left(\\frac{p_{\\beta}\\left(x\\right)}{1 - p_{\\beta}\\left(x\\right)}\\right) &= \\sigma^{-1}\\left(p_{\\beta}\\left(x\\right)\\right) \\\\\n&= x^{T}\\beta\n\\end{aligned}\n`}\n* A 1 unit increase in ${mtex`x_j`} increases the \"logit\" by ${mtex`\\beta_j`}.\n * Equivalently, multiplies ${mtex`p_{\\beta}\\left(x\\right)`} by a factor of ${mtex`\\exp{\\beta_j}`}\n* This is a special case of using a *link function* in generalized linear models\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":309,"value":"slide`### Logistic Regression\n\n* Can no longer fit this using the least squares criterion\n* Instead, use maximum likelihood: Find ${mtex`\\beta`} so that ${mtex`p_{\\beta}\\left(x_{i}\\right)`} is large whenever ${mtex`y_i = 1`} and small otherwise\n* Formally, maximize ${mtex`\\prod_{i : y_i = 1} p_{\\beta}\\left(x_i\\right) \\prod_{i : y_i = 0}\\left(1 - p_{\\beta}\\left(x_i\\right)\\right)`} over all possible ${mtex`\\beta`}\n* Can't be done analytically, but derivatives can be found, so we can optimize\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":328,"value":"slide`# Variants`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":333,"value":"slide`### Decision Trees\n* The local averaging idea in KNN is powerful, but it got overwhelmed in high dimensions\n* Can we adapt it so that it only considers a few dimensions that really matter?\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":344,"value":"slide`### Decision Trees\n* The basic idea is,\n * Split the input space into nonoverlapping rectangles, ${mtex`R_1, R_2, \\dots, R_K`}\n * For a new ${mtex`x`} lying in region ${mtex`R_k`}, estimate the output by\n${mtex_block`\n\\begin{aligned}\n\\hat{f}\\left(x\\right) &= \\frac{1}{\\absarg{R_k}}\\sum_{i : x_i \\in R_k}y_i\n\\end{aligned}\n`}\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":365,"value":"slide` ### Finding ${mtex`R_k`}\n* The ${mtex`R_k`}'s replace KNN's local neighborhoods\n * Not all variables will be split, helping avoid curse of dimensionality\n* Do the splitting recursively, from the top down\n* Choose splitting variables and positions so that ${mtex`y_i`}'s are similar within regions and different across them\n\n

\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":456,"value":"slide` ### Finding ${mtex`R_k`}\n* The ${mtex`R_k`}'s replace KNN's local neighborhoods\n * Not all variables will be split, helping avoid curse of dimensionality\n* Do the splitting recursively, from the top down\n* Choose splitting variables and positions so that ${mtex`y_i`}'s are similar within regions and different across them\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":457,"value":"slide` ### Finding ${mtex`R_k`}\n* The ${mtex`R_k`}'s replace KNN's local neighborhoods\n * Not all variables will be split, helping avoid curse of dimensionality\n* Do the splitting recursively, from the top down\n* Choose splitting variables and positions so that ${mtex`y_i`}'s are similar within regions and different across them\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":459,"value":"slide` ### Finding ${mtex`R_k`}\n* The ${mtex`R_k`}'s replace KNN's local neighborhoods\n * Not all variables will be split, helping avoid curse of dimensionality\n* Do the splitting recursively, from the top down\n* Choose splitting variables and positions so that ${mtex`y_i`}'s are similar within regions and different across them\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":404,"value":"slide` ### Finding ${mtex`R_k`}\nDefine a candidate splits of ${mtex`R_k`} by the split point ${mtex`s`} and split dimension ${mtex`j`},\n\n* ${mtex`R_{1}\\left(s, j\\right) = \\{x \\in R_k \\vert x_{j} < s\\}`} \n* ${mtex`R_{2}\\left(s, j\\right) = \\{x \\in R_k\\vert x_{j} \\geq s\\}`}.\n\nThe lower this quantity, the better the split,\n${mtex_block`\n\\sum_{\\{i \\vert x_i \\in R_{1}\\left(s, j\\right)\\}}\\left(y_i - \\hat{y}_{R_1}\\right)^{2} +\n\\sum_{\\{i \\vert x_i \\in R_{2}\\left(s, j\\right)\\}}\\left(y_i - \\hat{y}_{R_2}\\right)^{2}\n`}\n\n

\n\nExample of a split that would have a good value.\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":586,"value":"slide` ### Finding ${mtex`R_k`}\nDefine a candidate splits of ${mtex`R_k`} by the split point ${mtex`s`} and split dimension ${mtex`j`},\n\n* ${mtex`R_{1}\\left(s, j\\right) = \\{x \\in R_k \\vert x_{j} < s\\}`} \n* ${mtex`R_{2}\\left(s, j\\right) = \\{x \\in R_k\\vert x_{j} \\geq s\\}`}.\n\nThe lower this quantity, the better the split,\n${mtex_block`\n\\sum_{\\{i \\vert x_i \\in R_{1}\\left(s, j\\right)\\}}\\left(y_i - \\hat{y}_{R_1}\\right)^{2} +\n\\sum_{\\{i \\vert x_i \\in R_{2}\\left(s, j\\right)\\}}\\left(y_i - \\hat{y}_{R_2}\\right)^{2}\n`}\n\n

\n\nExample of a split that would have a bad value.\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":435,"value":"slide`### Finding ${mtex`R_k`}\n\nAcross ${mtex`R_k`}, scan over ${mtex`j`} and ${mtex`s`},\n* Choose best of any split, according to the criterion above\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":469,"value":"slide`### Finding ${mtex`R_k`}\n\nAcross ${mtex`R_k`}, scan over ${mtex`j`} and ${mtex`s`},\n* Choose best of any split, according to the criterion above\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":384,"value":"slide`### ${mtex`R_k`} and Trees\n\n* The region splitting procedure can be interpreted as \"growing a tree\"\n* Each node in the tree corresponds to one rectangular subregion\n* Cutting an ${mtex`R_k`} along dimension ${mtex`j`} is like splitting a branch\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":481,"value":"slide`### \"Cautious\" optimism is necessary\n\n* Some splits don't appear useful until we proceed a few splits further down\n* This motivates \"overgrowing\" the tree, and then pruning away unecessary splits\n\n

\n\nNo one split point seems useful if you look at only one dimension. But if you see two, the choice becomes clear.\n\n* \"Overgrowing\" the tree: too many split can lead to overfitting.\n\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":698,"value":"slide`### Trees wrap-up\n\n* Both regression and classification\n* Performance can be substantially improved by ensembling; Boosting and Random Forests (not in this lecture)\n* Let's go through [this demo](http://www.r2d3.us/visual-intro-to-machine-learning-part-1/)\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":495,"value":"slide`## Linear Regression Tricks\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":706,"value":"slide` ### Overview\n* A few tricks can make linear regression more powerful\n * Interaction terms\n * Categorical predictors\n * Nonlinear basis\n * ${mtex`\\ell^{2}`} and ${mtex`\\ell^1`} regularization\n* We'll cover the first three\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":506,"value":"slide`### Interactions\n\nRecall the example of model families.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":523,"value":"slide`### Interactions\n\nConsider the regression,\n${mtex_block`\n\\begin{aligned}\n y &= \\beta_0 + \\beta_1 x_{1} + \\beta_2 x_{2} + \\beta_{3} x_{1}x_{2} \\\\\n &= \\beta_0 + \\beta_1 x_1 + \\left(\\beta_2 + \\beta_3 x_1\\right)x_2.\n\\end{aligned}\n`}\nNotice that the slope for ${mtex`x_2`} varies smoothly as a function of ${mtex`x_1`}. The same holds when you reverse the variables.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":650,"value":"slide`### Categorical predictors\n\n\n* Suppose a variable ${mtex`x`} takes on one of ${mtex`L`} levels\n * e.g. ${mtex`x \\in \\{\\text{Montreal, Toronto, Vancouver}\\}`}\n* You would like a different mean for each city,\n\n ${mtex`f\\left(x\\right) = \\beta_{0} + \\beta_{1}\\indic{x \\in \\text{Montreal}} + \\beta_{2}\\indic{x \\in \\text{Toronto}} + \\beta_{3}\\indic{x \\in \\text{Vancouver}}`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":662,"value":"slide`### Categorical predictors\n\n\n* Suppose a variable ${mtex`x`} takes on one of ${mtex`L`} levels\n * e.g. ${mtex`x \\in \\{\\text{Montreal, Toronto, Vancouver}\\}`}\n* Equivalently, you can set the intercept ${mtex`\\beta_0`} to be the Montreal mean, so that\n\n ${mtex`f\\left(x\\right) = \\beta_{0} + \\beta_{1}\\indic{x \\in \\text{Toronto}} + \\beta_{2}\\indic{x \\in \\text{Vancouver}}`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":665,"value":"slide`### Categorical predictors\n\n\n* Equivalently, you can set the intercept ${mtex`\\beta_0`} to be the Montreal mean, so that\n\n ${mtex`f\\left(x\\right) = \\beta_{0} + \\beta_{1}\\indic{x = \\text{Toronto}} + \\beta_{2}\\indic{x = \\text{Vancouver}}`}\n* This can be accomplished by,\n * encode ${mtex`x = \\left(0, 0\\right)`} for Montreal, ${mtex`\\left(1, 0\\right)`} for Toronto, and ${mtex`\\left(0, 1\\right)`} for Vancouver\n * write ${mtex`f\\left(x\\right) = \\beta_0 + x^{T}\\beta`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":537,"value":"slide`### Nonlinearities: Basis Functions\n\n* Usual (linear) model family: ${mtex`f\\left(x\\right) = x^{T}\\beta`}\n* Instead, could use ${mtex`f\\left(x\\right) = h\\left(x\\right)^{T}\\beta`},\n * e.g., ${mtex`h\\left(x\\right) = \\left(1, x_1, x_2, , x_1 x_2, x_1^{2}, x_{2}^{2}\\right)`}\n * Or, ${mtex`h\\left(x\\right) = \\left(\\sin\\left(x\\right), \\cos\\left(x\\right)\\right)`}\n* It's still linear in ${mtex`\\beta`}, so formulas from before still work (just replace ${mtex`x_i`} with ${mtex`h\\left(x_i\\right)`})\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":542,"value":"slide`### Nonlinearities: Local Basis\n\n* Polynomials are global, unbounded functions. It's safer to consider ${mtex`h\\left(x\\right)`} that are more local\n* E.g., piecewise constant\n\n${mtex`h\\left(x\\right) = \\left[\\indic{x < c_1}, \\indic{x \\in \\left[c_1, c_2\\right]}, \\dots, \\indic{x > c_k}\\right]`}\n***\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":624,"value":"slide`### Nonlinearities: Local Basis\n\n* Polynomials are global, unbounded functions. It's safer to consider ${mtex`h\\left(x\\right)`} that are more local\n* E.g., piecewise linear \n\n${mtex`h\\left(x\\right) = \\left[x, \\left(x - c_1\\right)_{+}, \\dots, \\left(x - c_k\\right)_{+}\\right]`}\n***\n\n\n\n $\"piecewise-linear-basis\"$ \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":544,"value":"slide`### Nonlinearities: Generalized Additive Models\n\n* In higher-dimensions, it's not obvious what the nonlinear basis should look like\n* 💡 Simple decomposition across dimensions, and use nonlinearities only within dimensions:\n\n${mtex_block`\n\\begin{aligned}\n\\hat{f}\\left(x\\right) &= \\sum_{j = 1}^{p} \\hat{f}_{j}\\left(x_j\\right),\n\\end{aligned}\n`}\nwhere each ${mtex`\\hat{f}_j`} is fit using nonlinear basis functions.\n* Can no longer directly use regression formulas (link, nonlinear features), but a slight (iterative) variant works.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":736,"value":"$30","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":738,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":741,"value":"hl = require(\"@observablehq/highlight.js@1.0.0/highlight.min.js\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"slide_style = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"function mtex() {\n return tex`\n\\def\\reals{\\mathbb{R}}\n\\def\\E{\\mathbb{E}} % Expectation symbol\n\\def\\Var{\\text{Var}} % Expectation symbol\n\\def\\P{\\mathbb{P}} % Expectation symbol\n\\def\\Earg#1{\\E\\left[{#1}\\right]}\n\\def\\Vararg#1{\\V\\left[{#1}\\right]}\n\\def\\Esubarg#1#2{\\E_{#1}\\left[{#2}\\right]}\n\\def\\Parg#1{\\P\\left[{#1}\\right]}\n\\def\\eps{\\epsilon}\n\\newcommand\\mbb[1]{\\mathbb{#1}}\n\\def\\indic#1{\\mbb{I}\\left({#1}\\right)} % Indicator function\n\\def\\Vararg#1{\\Var\\left[{#1}\\right]}\n\\def\\absarg#1{\\left|#1\\right|}\n\\renewcommand{\\exp}[1]{\\operatorname{exp}\\left(#1\\right)} % Exponential\n${String.raw.apply(String, arguments)}\n`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"function mtex_block() {\n return tex.block`\n\\def\\reals{\\mathbb{R}}\n\\def\\E{\\mathbb{E}} % Expectation symbol\n\\def\\Var{\\text{Var}} % Expectation symbol\n\\def\\P{\\mathbb{P}} % Expectation symbol\n\\def\\Earg#1{\\E\\left[{#1}\\right]}\n\\def\\Vararg#1{\\V\\left[{#1}\\right]}\n\\def\\Esubarg#1#2{\\E_{#1}\\left[{#2}\\right]}\n\\def\\Parg#1{\\P\\left[{#1}\\right]}\n\\def\\eps{\\epsilon}\n\\newcommand\\mbb[1]{\\mathbb{#1}}\n\\def\\indic#1{\\mbb{I}\\left({#1}\\right)} % Indicator function\n\\def\\Vararg#1{\\Var\\left[{#1}\\right]}\n\\def\\absarg#1{\\left|#1\\right|}\n\\renewcommand{\\exp}[1]{\\operatorname{exp}\\left(#1\\right)} % Exponential\n${String.raw.apply(String, arguments)}\n`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":693,"value":"slide`## Asides`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":259,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":499,"value":"slide`### Locally Linear Regression\n\n* Instead of taking averages within neighborhoods, can fit small linear regressions\n* A type of blend between KNN and linear regression\n\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 2e:"$2d:body"