28:null 29:["$","title",null,{"children":"The Bootstrap | Kris Sankaran | Observable"}] 2e:[] 2c:{"id":"e0a3544d80cc2ba8","slug":"the-bootstrap","title":"The Bootstrap","thumbnail":"aef7c8b1b530c8f0686f4b75292f525957a87946e13108e31d5c87fc149df0e6","access_level":"public","create_time":"$D2019-09-30T19:09:08.684Z","update_time":"$D2019-10-01T13:23:50.237Z","view_time":null,"first_public_time":"$D2019-09-30T21:32:01.841Z","has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"58c635fe0c6a930c","login":"krisrs1128","name":"Kris Sankaran","avatar_url":"https://avatars-next.observableusercontent.com/384a4d4ac6e6ad0ce3c5b1bc69c03d2c693a0b2859424bd8395dfef0e462967e","tier":"starter_2024"},"version":421,"publish_version":421,"role":null,"authored":false,"authors":[{"type":"individual","id":"544fdf34bf62b87c","login":"krisrs1128","name":"Kris Sankaran","avatar_url":"https://avatars-next.observableusercontent.com/384a4d4ac6e6ad0ce3c5b1bc69c03d2c693a0b2859424bd8395dfef0e462967e","tier":null}],"members":[{"type":"individual","id":"544fdf34bf62b87c","login":"krisrs1128","name":"Kris Sankaran","avatar_url":"https://avatars-next.observableusercontent.com/384a4d4ac6e6ad0ce3c5b1bc69c03d2c693a0b2859424bd8395dfef0e462967e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":6,"collection":null,"type":"notebook","body":{"title":"The Bootstrap","cells":[{"id":0,"value":"md`# The Bootstrap\n\nIFT6758, Fall 2019\n\nReading: [ISLR](http://faculty.marshall.usc.edu/gareth-james/ISL/ISLR%20Seventh%20Printing.pdf) 5.2 - 5.3\n\nOptional reading: [CASI]() Chapter 1\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"slide`### Computation for Inference\n\n* Increased computation has revolutionized our ability to fit functions to data\n* It has also profoundly influenced inference\n* The bootstrap is one important reflection of this\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"slide`### Algorithms vs. Inference\n\n* Algorithms help you construct useful reductions of data (for knowledge or decision making).\n* Inference helps you gauge how reliable your reductions are\n\n\"It is a surprising, and crucial, aspect of statistical theory that the same data that supplies an estimate can also be used to assess it's accuracy.\"\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"slide`### Example: Sample Mean\n\nThere is a closed-form formula for the standard error of the sample mean. Suppose ${mtex`x_i \\stackrel{i.i.d.}{\\sim} F`}, a distribution with variance ${mtex`\\sigma^2`}. Then,\n\n${mtex_block`\n\\begin{aligned}\n\\Vararg{\\bar{x}} \n&= \\Vararg{\\frac{1}{n}\\sum_{i = 1}^{n}x_i} \\\\\n&= \\frac{1}{n^2}\\sum_{i = 1}^{n}\\Vararg{x_i} \\\\\n&= \\frac{1}{n^2}n\\sigma^{2} \\\\\n&= \\frac{\\sigma^{2}}{n}\n\n\\end{aligned}`}\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"slide`### Estimated Standard Error\n\nTherefore, if we had a way of estimating ${mtex`\\sigma^2`}, then we can estimate the standard error of the mean by plugging this estimate in.\n\n${mtex_block`\n\\Var\\left[\\bar{x}\\right] \\approx \\frac{\\hat{\\sigma}^2}{n}\n`}\n\nThis would us a way of understanding to what degree we can trust our estimate of the mean, computed entirely from the raw data.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":95,"value":"slide`### Estimated Standard Error\n\nOf course, if ${mtex`x_i \\stackrel{i.i.d.}{\\sim} F`}, then a reasonable estimate for ${mtex`\\sigma^2`} is\n\n${mtex_block`\n\\hat{\\sigma}^2 := \\frac{1}{n} \\sum_{i = 1}^{n} \\left(x_i - \\bar{x}\\right)^2\n`}\n\nSo in summary, to estimate the variance of the mean, we\n1. Compute an estimate of ${mtex`\\sigma^2`}\n2. Plug that the true expression for ${mtex`\\Vararg{\\bar{x}}`}\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":84,"value":"slide`### Abstraction\n\nThis is a more abstract way of describing this process.\n\n1. Define a statistic ${mtex`\\hat{\\theta}\\left(x_1, \\dots, x_n\\right)`} of the data\n2. Do math to get an expression for ${mtex`\\Vararg{\\hat{\\theta}}`}\n3. Replace unknowns in the expression with estimates, and argue that the result is ${mtex`\\approx \\Vararg{\\hat{\\theta}}`}. \n * If you want to be precise, you could call this new estimator ${mtex`\\widehat{\\Var}\\left[\\hat{\\theta}\\right]`}\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"slide` ### Goals\n\nIn a lot of cases, step (2) is intractable.\n\n* ${mtex`\\hat{\\theta}`} is a more complex function of the ${mtex`x_i`}\n - Ratio between eigenvalues in your PCA\n - Derived statistics, like ${mtex`\\log\\mu`} or ${mtex`\\frac{\\alpha}{\\beta}`} in some model\n* You ran some iterative algorithm to compute ${mtex`\\hat{\\theta}`}\n - Robust regression\n - Random forests\n\n**We'd like a recipe that works even then, and which doesn't have to be rederived for every single problem.**\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":129,"value":"slide`### Example: Portfolio Optimization\n\n* Two assets that you can invest in, ${mtex`X`} and ${mtex`Y`}.\n* Distribute ${mtex`\\alpha`} fraction of funds to ${mtex`X`}, and the rest to ${mtex`Y`}, i.e., invest\n${mtex_block`\\alpha X + \\left(1 - \\alpha\\right)Y`}\n* The best strategy (in the sense of minimizing variance) can be shown to be\n${mtex_block`\n\\begin{aligned}\n\\alpha &= \\frac{\\sigma^2_Y - \\sigma_{XY}}{\\sigma^2_X + \\sigma^2_Y - 2\\sigma_{XY}}\n\\end{aligned}\n`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":138,"value":"slide`### Example: Portfolio Optimization\n\n* ${mtex`\\alpha`} is unknown in practice, so we estimate it,\n${mtex_block`\n\\hat{\\alpha}\\left(x_1, \\dots, x_n, y_1, \\dots, y_n\\right) = \\frac{\\hat{\\sigma}^2_Y - \\hat{\\sigma}_{XY}}{\\hat{\\sigma}^2_X + \\hat{\\sigma}^2_Y - 2\\hat{\\sigma}_{XY}}\n`}\n* Now we want to know, how variable is this estimator?\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":143,"value":"slide`### A Thought Experiment\n\n* Suppose you had a window into parallel universes\n* How much does the estimator change across different samples?\n\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"slide`### Thought Experiment\n\nIf you simulate 1000 datasets in this way, you can get a different ${mtex`\\hat{\\alpha}_r`}, for ${mtex`r = 1, 2, \\dots, 1000`}. From the book's example,\n\n${mtex_block`\n\\bar{\\alpha} = \\frac{1}{1000}\\sum_{r = 1}^{1000} \\hat{\\alpha}_r = 0.5996\n`}\nwhich (unsurprisingly) is very close to the underlying 0.6.\n\nTo get a sense of the variability across datasets, we can use\n${mtex_block`\n\\widehat{\\Var}\\left[\\hat{\\alpha}\\right] = \\frac{1}{999}\\sum_{r = 1}^{1000}\\left(\\hat{\\alpha}_r - \\bar{\\alpha}\\right)^2 \\approx 0.083^2,\n`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":163,"value":"slide`### Bootstrap Idea\n\n* In our simulation, we were able to sample as many new datasets ${mtex`F`} as we wanted. In reality, we see only one.\n* But we can simulate as many datasets from the empirical distribution ${mtex`\\hat{F}`} as we want\n* It turns out that if you use ${mtex`\\hat{F}`} in place of ${mtex`F`}, the approach from the thought experiment *still works*\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":330,"value":"slide`### Sampling from ${mtex`F`}\n\nIn our ideal simulation world, we're able to generate many datasets from ${mtex`F`} and see how our estimator ${mtex`\\hat{\\theta}`} changes.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":336,"value":"slide`### Sampling from ${mtex`F`}\n\nIn our ideal simulation world, we're able to generate many datasets from ${mtex`F`} and see how our estimator ${mtex`\\hat{\\theta}`} changes.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":338,"value":"slide`### Sampling from ${mtex`F`}\n\n\nThe properties of the final sampling distribution for ${mtex`\\hat{\\theta}`} can be used to guide inference.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":346,"value":"slide`### Sampling from ${mtex`\\hat{F}`} \n\nIn reality, we can't just generate new datasets. We *can* draw samples from the empirical distribution, however.\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":355,"value":"slide`### Sampling from ${mtex`\\hat{F}`} \n\nIn reality, we can't just generate new datasets. We *can* draw samples from the empirical distribution, however.\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":357,"value":"slide`### Sampling from ${mtex`\\hat{F}`} \n\nIn reality, we can't just generate new datasets. We *can* draw samples from the empirical distribution, however.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":215,"value":"slide`### Bootstrap vs. Simulation Estimates\n\n* The left are estimates ${mtex`\\hat{\\alpha}_r`} when you simulate from ${mtex`F`} (impossible in practice), while the right are when you simulate from ${mtex`\\hat{F}`} (possible in practice).\n* The estimated variances are very similar\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":175,"value":"slide`### The Bootstrap\n\n* Input: A statistic ${mtex`\\hat{\\theta}`}, number of desired simulations ${mtex`B`}\n* For ${mtex`b = 1, \\dots, B`},\n * Simulate ${mtex`x_1^{b}, \\dots, x_n^b \\stackrel{i.i.d.}{\\sim} \\hat{F}`}\n * Compute ${mtex`\\hat{\\theta}^b := \\hat{\\theta}\\left(x_1^b, \\dots, x_n^b\\right)`}\n* Estimate the variance of the original ${mtex`\\hat{\\theta}`} by looking at the variance in the simulation output,\n${mtex_block`\n\\Var\\left[\\hat{\\theta}\\left(x_1, \\dots, x_n\\right)\\right] \\approx \\frac{1}{B - 1}\\sum_{b = 1}^{B}\\left(\\hat{\\theta}^b - \\bar{\\theta}\\right)^2,\n`}\nwhere ${mtex`\\bar{\\theta}`} is the average of all the ${mtex`\\hat{\\theta}^b`}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":226,"value":"slide`### Plug-in Principle\n\nThe original estimator is constructed according to\n${mtex_block`\nF \\xrightarrow{sample} x_{1}, \\dots, x_{n} \\xrightarrow{estimate} \\hat{\\theta}\\left(x_1, \\dots, x_n\\right)\n`}\nThis is only done once, so you can't estimate the standard error from it alone.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":244,"value":"slide`### Plug-In Principle\n\nIf we plug in ${mtex`\\hat{F}`} for ${mtex`F`}, we get\n${mtex_block`\n\\hat{F} \\xrightarrow{resample} x_{1}^b, \\dots, x_{n}^b \\xrightarrow{estimate} \\hat{\\theta}\\left(x_1^b, \\dots, x_n^b\\right) := \\hat{\\theta}^b\n`}\n\nThis can be done as much as we want, so we can estimate the variance across ${mtex`\\hat{\\theta}^b`}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":259,"value":"slide`### The Resampling Perspective\n\n* Draws from ${mtex`\\hat{F}`}: up or downweight original samples.\n * Some ${mtex`x_i`} may not be included, other might be included multiple times\n * View this as points on the simplex (space of weights that sum to ${mtex`n`})\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":276,"value":"slide`### The Resampling Perspective\n\n* The bootstrap measures the sensitivity of ${mtex`\\hat{\\theta}`} to different weightings of the original points\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":281,"value":"slide`### Bootstrap Confidence Intervals\n\n* A lot of times, we use estimates of the variance to build confidence intervals\n* If ${mtex`\\hat{\\theta}`} is approximately normal, it can be shown that\n\n ${mtex_block`\n\\hat{\\theta} \\pm 1.96 \\sqrt{\\Var\\left(\\hat{\\theta}\\right)}\n`}\n is a valid confidence interval\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":289,"value":"slide`### Approach 1\n\nTherefore, if we can use the bootstrap to estimate the variance, we can directly use it to make a confidence interval\n\n\n ${mtex_block`\n\\hat{\\theta} \\pm 1.96 \\sqrt{\\widehat{\\Var}\\left(\\hat{\\theta}\\right)}\n`}\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":296,"value":"slide`### Approach 2\n\n* What if ${mtex`\\hat{\\theta}`} isn't approximately normal?\n* In classical stats, you'd need new theory to find an alternative confidence interval\n* However, the bootstrap gives us access to something close to the distribution of ${mtex`\\hat{\\theta}`}\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":308,"value":"slide`### Approach 2\n\n* Main idea is to directly use quantiles of the simulated ${mtex`\\hat{\\theta}^b`}\n* No longer requires normality (or even symmetry)\n* However, requires more simulation samples, since quantiles are harder to estimate than variances\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":376,"value":"slide`### Approach 2\n\n* Main idea is to directly use quantiles of the simulated ${mtex`\\hat{\\theta}^b`}\n* No longer requires normality (or even symmetry)\n* However, requires more simulation samples, since quantiles are harder to estimate than variances\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":384,"value":"slide`### Extra Examples: Difference in Means\n\n* Suppose we want to test the difference in means between two groups.\n* We can define a reference distribution using the bootstrap\n* Idea is to sample repeatedly from ${mtex`\\hat{F}_1`} and ${mtex`\\hat{F}_2`}, and look at the distribution in the difference in means\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":396,"value":"slide`### Extra Examples: Difference in Means\n\n* Suppose we want to test the difference in means between two groups.\n* We can define a reference distribution using the bootstrap\n* Idea is to sample repeatedly from ${mtex`\\hat{F}_1`} and ${mtex`\\hat{F}_2`}, and look at the distribution in the difference in means\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":386,"value":"slide`### Extra Examples: Regression\n\n* You can bootstrap regression models as well\n* Fit the regression many times, across resampled versions of the data\n* Works for variants of regression with no analytical s.e. formula\n\n

\n\nExample robust regression bootstrap from [Bootstrapping Regression Models](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=2ahUKEwi8oJKQjPrkAhXNVN8KHUf1DaUQFjAAegQIABAC&url=http%3A%2F%2Fstatweb.stanford.edu%2F~owen%2Fcourses%2F305-1314%2FFoxOnBootingRegInR.pdf&usg=AOvVaw0Rn0cjZPcEqxnTE8LdGs1U)\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":388,"value":"slide`### Extra Examples: Regression\n\nIt can even be applied to nonparametric regression models, e.g., lowess regressions,\n\n

\n\nand even [Random Forests](https://arxiv.org/abs/1311.4555).\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"import {slide} from \"@mbostock/slide\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"slide_style = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"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":16,"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"}],"files":"$W2e","stdlib":"1","titling":"auto"}} 2d:"$2c:body"