29:null 2a:["$","title",null,{"children":"Cross Validation and Model Selection | Jhelum Chakravorty | Observable"}] 2f:T4d0,slide`### Detection of bias and variance from training and validation error * Variance occurs since different validation sets give different estimates * Bias occurs when training on subset leads to worse expected performance (remember learning curves)

**Regime # 1 (High variance)** *Symptoms* * Training error is much lower than test error * Training error is lower than acceptable threshold ${mtex `\epsilon`} * Test error is above ${mtex `\epsilon`} *Remedies* * Add more training data * Reduce model complexity -- complex models are prone to high variance * Bagging (will be covered later in the course) **Regime # 2 (High bias)** *Symptoms* * Training error is higher than ${mtex `\epsilon`} *Remedies* * Use more complex model (e.g. non-linear instead of linear) * Add features * Boosting (will be covered later in the course) Instead of using one validation set, one could have few alternative methods of getting more robust valiadation (less randomness). We will talk about: * Leave-One-Out Cross Validation [LOOCV] * K-Fold Cross Validation. `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:[] 2d:{"id":"2c11a0fe880dcd64","slug":"cross-validation-and-model-selection","title":"Cross Validation and Model Selection","thumbnail":"1074e719c9095680c6713cde7b77b495a8ffffc106f2d5f76070baf08af72264","access_level":"public","create_time":"$D2020-08-12T13:52:04.266Z","update_time":"$D2020-09-24T16:27:26.836Z","view_time":null,"first_public_time":"$D2020-08-12T13:52:55.287Z","has_unpublished_edits":null,"fork":{"id":"8011aa53029d4e95","slug":"cross-validation-and-model-selection","title":"Cross Validation and Model Selection","owner":{"id":"58c635fe0c6a930c","login":"krisrs1128","name":"Kris Sankaran"}},"stars":0,"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":341,"publish_version":341,"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":2,"collection":null,"type":"notebook","body":{"title":"Cross Validation and Model Selection","cells":[{"id":0,"value":"md`\n# Cross Validation and Model Selection\n\nIFT6758, Fall 2020\n\nReading: [ISLR](http://faculty.marshall.usc.edu/gareth-james/ISL/ISLR%20Seventh%20Printing.pdf) section 5.1 and [PDS](https://tanthiamhuat.files.wordpress.com/2018/04/pythondatasciencehandbook.pdf) pg. 359 - 375`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":307,"value":"slide.html`

Cross Validation and Model Selection

`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"slide`### Daily Choices for Data Scientists\n\nKnowing how to fit models is not enough, if you want to solve a real-world problem.\n\n* How should you select between model families?\n* Which parameters are best within a model family?\n* Should you be trying to improve the data?\n - More samples? Richer features?\n - Fewer missing data, outliers, ...\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"slide`### Transitioning to Inference\n\n* Inference: ML algorithms in action. Apply live data into the (learned) model to get output\n\n* To get a meaningful inference, we need to be more introspective, trying to understand properties of our algorithms\n\n* The heart of inference: Being critical of the processes people use to learn from data\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"slide`### Recall: Bias-Variance Tradeoff\n\n* Ultimately, you want your model to perform well on out-of-sample data\n* If you only evaluate on in-sample data, you will underestimate the out-of-sample error\n\n

\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":48,"value":"slide`### Validation Sets\n\n* To approximate the out-of-sample error, we can use a validation set.\n* Randomly divide your sample into two pieces, one to train and another to validate\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"slide`### Validation Sets\n\nIf you run this over models with different degrees of complexity, you can see the bias-variance tradeoff.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":234,"value":"slide`### Validation Sets\n\nIf you run this over models with different degrees of complexity, you can see the bias-variance tradeoff.\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"slide`### Complexity Regimes\n\nEven if you only evaluate the train / validation error for a model of a given complexity, you get useful information.\n\n* Training ${mtex`\\ll`} validation error ${mtex`\\rightarrow`} Model is overfit\n* Training ${mtex`\\approx`} validation error ${mtex`\\rightarrow`} Model is underfit (or OK)\n\nCommon heuristic: Overfit the data first, then regularize.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"slide`### Learning Curves\n\n* As you gather more data, how much better do your models get?\n\n* *Model score*: this can guide the decision to collect more data.\n\n - training score and the validation score are both low, the estimator will be **underfitting**\n - training score is high and the validation score is low, the estimator will be **overfitting**\n - Okay otherwise.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":79,"value":"slide`### Learning Curves\n\n* Models of different complexities have different learning curves\n* Larger models don't saturate as quickly. They are,\n - worse than small models on small datasets\n - better than small models on large datasets\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"slide`### Evaluation and Randomness\n\n* We are only _estimating_ out-of-sample error\n* These estimates might be good or bad\n - Have randomness from choice of validation set\n - Have randomness from dataset collection\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":246,"value":"slide`### Evaluation and Randomness\n\n* We are only _estimating_ out-of-sample error\n* These estimates might be good or bad\n - Have randomness from choice of validation set\n - Have randomness from dataset collection\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"slide`### LOOCV\n\n1. Fit your model without sample ${mtex`\\left(x_i, y_i\\right)`}. Call the fit ${mtex`\\hat{f}_{-i}`}.\n2. Compute holdout ${mtex`\\widehat{MSE}_{i} := \\left(y_{i} - \\hat{f}_{-i}\\left(x_i\\right)\\right)^{2}`}\n3. Estimate the out-of-sample error by averaging this over all possible holdouts coming from (1) and (2),\n${mtex_block`\n\\widehat{MSE} = \\frac{1}{n}\\sum_{i = 1}^{n} \\widehat{MSE}_{i}\n`}\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":252,"value":"slide`### LOOCV\n\n1. Fit your model without sample ${mtex`\\left(x_i, y_i\\right)`}. Call the fit ${mtex`\\hat{f}_{-i}`}.\n2. Compute holdout ${mtex`\\widehat{MSE}_{i} := \\left(y_{i} - \\hat{f}_{-i}\\left(x_i\\right)\\right)^{2}`}\n3. Estimate the out-of-sample error by averaging this over all possible holdouts coming from (1) and (2),\n${mtex_block`\n\\widehat{MSE} = \\frac{1}{n}\\sum_{i = 1}^{n} \\widehat{MSE}_{i}\n`}\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"slide`### LOOCV\n\nAdvantages\n * Lower bias. We use almost all the training data, so we don't underestimate performance.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"slide`### LOOCV\n\nDisdvantages\n * High computational complexity (except linear regression)\n * The trained models are correlated \n - The ${mtex`\\widehat{MSE}_i`} are correlated\n - The average of correlated variables has larger variance than the average of independent ones\n - The out-of-sample estimate has higher variance\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"slide`### K-Fold CV\n\n\n1. Randomly partition samples into one of ${mtex`K`} folds, ${mtex`\\{S_{1}, \\dots, S_{K}\\}`}.\n1. Fit your model without fold ${mtex`S_{k}`}. Call the fit ${mtex`\\hat{f}_{-k}`}.\n2. Compute holdout ${mtex`\\widehat{MSE}_{k} := \\sum_{i \\in S_{k}} \\left(y_{i} - \\hat{f}_{-k}\\left(x_i\\right)\\right)^{2}`}\n3. Estimate the out-of-sample error by averaging over folds,\n${mtex_block`\n\\widehat{MSE} = \\frac{1}{K}\\sum_{k = 1}^{K} \\widehat{MSE}_{k}\n`}\n\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":151,"value":"slide`### K-Fold CV\n\nAdvantages\n* More computationally tractable\n* Learns less correlated models\n - The estimates ${mtex`\\widehat{MSE}_k`} are less correlated\n - The estimate ${mtex`\\widehat{MSE}`} has lower variance\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":263,"value":"slide`### K-Fold CV\n\nDisadvantages\n* We don't train using the full training set: high bias \n - Model on full dataset is actually better than estimated (overestimating error)\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":276,"value":"slide`### Estimation Quality: LOOCV and K-Fold\n\n* The blue curves are known out-of-sample MSE's from a simulation experiment\n* Black and orange are LOOCV and K-Fold estimates, respectively\n* Note: Even when estimates of out-of-sample MSE is poor, the estimate of the minimum might be good\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":174,"value":"slide`### Hyperparameter Search\n\n* We will often have many parameters to tune simultaneously\n - Model parameters: Polynomial degree, # trees, ...\n - Training parameters: Learning rate, subsampling, ...\n - Preprocessing: Normalization, outlier removal, ...\n* No single \"model complexity\" parameter\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":187,"value":"slide`### Search Options\n\n* Manual search\n* Grid search\n* Random search\n* Combinations of these\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":192,"value":"slide`### Manual Search\n\n* Reasonable strategy: use *coordinate descent* - change one hyper-parameter at a time, make it better from where it was until now. \n* Focus more on certain parameters (fine tune the updates). Guide your choice of parameters by which regime (over vs. underfitting) you are in\n* Advantage: Uses bias-variance tradeoff information\n* Disadvantage: Tedious, not fully reproducible\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":198,"value":"slide`### Grid Search\n\n* Compute out-of-sample error on all combinations of parameters\n* Advantage: Automatic, easy to implement\n* Disadvantage: Exponentially many parameter configurations; might take long to identify relevant parameters\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":203,"value":"slide`### Random Search\n\n* Compute out-of-sample error on random samples of parameters\n* Advantage: Automatic, easy to implement. Relevant parameters become clear quickly.\n* Disadvantage: Still suffers when there are many parameters.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":217,"value":"slide` ### Combinations\n\n* Can fix a few parameters manually, and use random search for others\n* Can use [\"multi-resolution\"](https://arxiv.org/abs/1206.5533) search. Automatically search over predefined grids, but manually set the grids to more promising regions.\n - Start with a broad range for each hyper-parameter. Manually update (using coarse tuning, large changes at every step). \n - Once you found few best configurations, start fine tuning them more locally with smaller changes around the nominal value. \n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":299,"value":"slide.end('Let us stop here')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":283,"value":"$30","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":292,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"slide_style = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":288,"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":310,"value":"import {mtex} from \"@krisrs1128/function-fitting\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":313,"value":"import {mtex_block} from \"@krisrs1128/function-fitting\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}} 2e:"$2d:body"