28:null 29:["$","title",null,{"children":"KNN Bias Variance | Kris Sankaran | Observable"}] 2e:T7b7,chart = { const svg = d3.select(DOM.svg(width, f1.height)); svg.selectAll("g") .data(["background", "series", "samples", "fit", "histogram", "x0", "fx0"]).enter() .append("g") .attr("id", (d) => d); svg.select("#background") .append("rect") .attrs({ "width": width, "height": f1.height, "fill": "white" }) .on("mousemove", function() { f1.mouse_fun(svg, this) }) var scales = f1.generate_scales(f1.x); svg.select("#x0") .append("rect") .attrs({ "x": scales.x(x0) - 5/2, "y": 0, "height": f1.height, "width": 5, "fill": "#9C4420", "fill-opacity": 0.2 }) svg.select("#fx0") .append("rect") .attrs({ "x": 0, "y": scales.y(f1.key_f(f1.f)[x0]) - 5 / 2, "height": 5, "width": width, "fill": "#9C4420", "fill-opacity": 0.2 }) svg.select("#series") .selectAll("circle") .data(f1.f).enter() .append("circle") .attrs({ "cx": (d) => scales.x(d.x), "cy": (d) => scales.y(d.y), "fill": "#d3d3d3", "r": 5 }) svg.select("#samples") .selectAll("circle") .data(f1.samples).enter() .append("circle") .attrs({ "cx": (d) => scales.x(d.x), "cy": (d) => scales.y(d.y), "fill": "#7BACA0", "r": 5 }) svg.select("#fit") .selectAll("circle") .data(f1.fit).enter() .append("circle") .attrs({ "cx": (d) => scales.x(d.x), "cy": (d) => scales.y(d.y), "fill": "#D9C16A", "r": 5 }) svg.select("#histogram") .selectAll("rect") .data(f1.histo).enter() .append("rect") .attrs({ "x": 0, "y": (d) => scales.y(d.x1), "height": (d) => scales.y(d.x0) - scales.y(d.x1), "width": (d) => history.length == 0? 0 : 200 * d.length / history.length, "fill-opacity": 0.5 }) while(true) { f1.click_fun(svg); yield Promises.delay(delay, svg.node()) } }2f:Tec8,f1 = { var height = width / 2, samples = sample_data(key_f(f), N), scales = generate_scales(), fit = knn_fit(samples, f, K), history = [], hist_fun = d3.histogram().value((d) => d).domain(scales.y.domain()).thresholds(scales.y.ticks(50)), histo = hist_fun(history); function generate_scales() { return { "x": d3.scaleLinear().domain([0, 1]).range([0, width]), "y": d3.scaleLinear().domain([-1.2, 1.2]).range([height, 0]), } } function sample_data(f, n) { var samples = []; for (var i = 0; i < n; i++) { var u = Math.round(Math.random() * 100) / 100 var y = f[u] + jstat.normal.sample(0, sigma) samples.push({ "x": u, "y": y }) } return samples } function key_f(f) { var result = {}; for (var i = 0; i < f.length; i++) { result[f[i].x] = f[i].y } return result; } function knn_fit(samples, f, K) { var result = []; for (var i = 0; i < f.length; i++) { var N = neighbors(f[i].x, samples, K) result.push({ "x": f[i].x, "y": d3.mean(N.map((d) => d.y)) }) } return result; } function neighbors(x, samples, K) { var result = []; for (var i = 0; i < samples.length; i++) { var dist = Math.abs(samples[i].x - x); if (result.length < K) { result.push({"x": samples[i].x, "y": samples[i].y, "dist": dist}); } else { var dists = result.map((d) => d.dist); var max_ix = d3.maxIndex(dists); if (dist < dists[max_ix]) { result.splice(max_ix, 1); result.push({"x": samples[i].x, "y": samples[i].y, "dist": dist}); } } } return result } function update_series(pos) { if (pos[0] <= 0 || pos[0] >= width || pos[1] > height || pos[1] < 0) return; console.log(pos) history = []; var closest_ix = Math.round(scales.x.invert(n * (pos[0]))) / n for (var i = 0; i < f.length; i++) { var dist = Math.abs(f[i].x - closest_ix); if (dist <= 0.05) { f[i].y = scales.y.invert((0.05 - dist) / 0.05 * pos[1] + dist / 0.05 * scales.y(f[i].y)); } } } function redraw_series(svg, scales, x) { svg.select("#series") .selectAll("circle") .data(f) .attrs({ "cy": (d) => scales.y(d.y), }); svg.select("#samples") .selectAll("circle") .data(samples) .attrs({ "cx": (d) => scales.x(d.x), "cy": (d) => scales.y(d.y), }); svg.select("#fit") .selectAll("circle") .data(fit) .attrs({ "cx": (d) => scales.x(d.x), "cy": (d) => scales.y(d.y) }) svg.select("#histogram") .selectAll("rect") .data(histo) .attrs({ "x": 0, "width": (d) => history.length == 0? 0 : 200 * d.length / history.length }) svg.select("#fx0").select("rect") .attrs({ "y": scales.y(key_f(f)[x0]) - 5/2, }) } function click_fun(svg) { samples = sample_data(key_f(f), N); fit = knn_fit(samples, f, K); history.push(key_f(fit)[x0]); histo = hist_fun(history) redraw_series(svg, scales, f); } function mouse_fun(svg, d) { var div = d3.select(d); d3.select(window) .on("mousemove", mousemove); function mousemove(event) { var pos = d3.pointer(event); pos[1] = pos[1] - 200 update_series(pos); redraw_series(svg, scales, f); } } return { "initialize_f": initialize_f, "generate_scales": generate_scales, "f": f, "samples": samples, "fit": fit, "height": height, "click_fun": click_fun, "mouse_fun": mouse_fun, "histo": histo, "key_f": key_f } }30:[] 2c:{"id":"a3cf0e9e1129d243","slug":"knn-bias-variance","title":"KNN Bias Variance","thumbnail":"a0d40c9f9e10ead547b7c0bc615ae2baec06e0a7fb33854379098611b18633e3","access_level":"public","create_time":"$D2019-09-11T21:51:28.130Z","update_time":"$D2022-09-27T19:11:32.626Z","view_time":null,"first_public_time":"$D2019-09-12T00:27:33.887Z","has_unpublished_edits":null,"fork":{"id":"dcd0dadcfa21ed76","slug":"time-warping","title":"Time Warping","owner":{"id":"58c635fe0c6a930c","login":"krisrs1128","name":"Kris Sankaran"}},"stars":0,"starred":false,"owner":{"type":"team","id":"58c635fe0c6a930c","login":"krisrs1128","name":"Kris Sankaran","avatar_url":"https://avatars-next.observableusercontent.com/384a4d4ac6e6ad0ce3c5b1bc69c03d2c693a0b2859424bd8395dfef0e462967e","tier":"starter_2024"},"version":622,"publish_version":null,"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":4,"collection":null,"type":"notebook","body":{"title":"KNN Bias Variance","cells":[{"id":231,"value":"md`# KNN Bias Variance`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":235,"value":"md`The grey points are the true data generating function. The green points are different samples from that function. The yellow points are the knn fit. The histogram gives the knn prediction at the position around the vertical red bar. The correct value is the horizontal red bar. Mouseover the figure to change the underlying function.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":558,"value":"$2e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":387,"value":"viewof N = slider({min: 5, max: 100, step: 1, value: 10, title: \"number of samples\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":390,"value":"viewof K = slider({min: 1, max: 50, step: 1, value: 5, title: \"Number of Neighbors\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":401,"value":"viewof x0 = slider({title: \"Evaluation Point\", min: 0.01, max:0.99, value: 0.7})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":581,"value":"viewof sigma = slider({title: \"Noise Standard Deviation\", min: 0.01, max: 1, value: 0.3})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":493,"value":"viewof delay = slider({min: 10, max: 1000, step: 20, value: 1000, title: \"frame delay\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":532,"value":"n = 100","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":528,"value":"f = initialize_f(n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":535,"value":"function initialize_f(n) {\n var x = [];\n for (var i = 1; i < n; i++) {\n x.push({\"x\": i / n, \"y\": .5 * Math.sin(2 * Math.PI * i / n)});\n }\n return x;\n} ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"d3 = require.alias({\n 'd3-selection': 'd3',\n 'd3-transition': 'd3',\n \"d3-scale\": 'd3', \n \"d3-array\": 'd3', \n \"d3-axis\": 'd3',\n \"d3-drag\": 'd3',\n \"d3-brush\": 'd3',\n \"d3-shape\": 'd3', \n \"d3-fetch\": 'd3',\n \"d3-scale-chromatic\": 'd3'\n})('d3', 'd3-selection-multi@1')\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":485,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":566,"value":"jstat = require(\"jstat\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W30","stdlib":"1","titling":"auto"}} 2d:"$2c:body"