31:T574,svg = { const svg = d3.select(DOM.svg(width, height)) const nx = 100 const ny = 100 const lerp = (t, a, b) => (1.0 - t) * a + t * b function get_f_values(nx, ny) { const grid = new Array(nx * ny) for (let i = 0; i < nx; i++) { for (let j = 0; j < ny; j++) { const x = lerp(parseFloat(i) / nx, -2, 2) const y = lerp(parseFloat(j) / ny, -2, 2) grid[i + j * nx] = fn(x, y) } } return grid } const fValues = get_f_values(nx, ny) const fMin = d3.min(fValues) const fMax = d3.max(fValues) const contour_step = (fMax - fMin) / 10 const domain_f = [fMin, fMax] const thresholds = d3.range(domain_f[0], domain_f[1], contour_step) const color_scale = d3.scaleLinear() .domain(d3.extent(thresholds)) .interpolate(function() { return d3.interpolateYlGnBu; }) const contours = d3.contours() .size([nx, ny]) .thresholds(thresholds) svg.append("g") .on("mousedown", mousedown) .selectAll("path") .data(contours(fValues)) .enter().append("path") .attr("d", d3.geoPath(d3.geoIdentity().scale(height / nx))) .attr("fill", function(d) { return color_scale(d.value); }) .attr("stroke", "none") for (let method of Object.keys(colors)) { svg.append("g").attr("id", method) } return svg }32:[] 2f:{"title":"Gradient Methods","cells":[{"id":0,"value":"# Gradient Methods","pinned":false,"hidden":false,"mode":"md"},{"id":690,"value":"Enter a function and click on the plot.","pinned":false,"hidden":false,"mode":"md"},{"id":448,"value":"viewof expr = Inputs.text({label: tex`f(x,y)=`, value: \"x^2 + 2 * y^2\", submit: true})","pinned":false,"hidden":false,"mode":"ojs"},{"id":267,"value":"svg.node()","pinned":false,"hidden":false,"mode":"ojs"},{"id":479,"value":"viewof methods = Inputs.checkbox([\"Newton\", \"Gradient\", \"CG\", \"Momentum\", \"Nesterov\", \"RMSProp\", \"Adam\"], {value: [\"Newton\", \"Gradient\", \"CG\", \"Momentum\", \"Nesterov\", \"RMSProp\", \"Adam\"], label: html`Methods`, format: x => html`${x}`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":488,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":389,"value":"mutable start = [2, 1]","pinned":false,"hidden":false,"mode":"ojs"},{"id":86,"value":"descent = async function (fn, start, method, maxiter, callback) {\n let [x, y] = start\n \n while (true) {\n let [dx, dy] = fn.d(x, y)\n \n const norm = Math.sqrt(dx**2 + dy**2)\n \n if (norm < 1e-8) break\n\n [x, y] = method.step(fn, x, y)\n\n callback(x, y)\n\n await sleep(100)\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":437,"value":"class NewtonRaphson {\n constructor () {\n }\n \n step (fn, x, y) {\n const [dx, dy] = fn.d(x, y)\n const [dxx, dxy, dyy] = fn.dd(x, y)\n \n const det = dxx * dyy - dxy**2\n \n const vx = (dyy * dx - dxy * dy) / det\n const vy = (dxx * dy - dxy * dx) / det\n \n return [x - vx,\n y - vy]\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":105,"value":"class Gradient {\n constructor (alpha) {\n this.alpha = alpha\n }\n \n step (fn, x, y) {\n const [dx, dy] = fn.d(x, y)\n return [x - this.alpha * dx,\n y - this.alpha * dy]\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":509,"value":"class ConjugateGradient {\n constructor (fn, x, y) {\n let [gx, gy] = fn.d(x, y)\n\n this.gx = gx\n this.gy = gy\n this.dx = -gx\n this.dy = -gy\n }\n \n step (fn, x, y) {\n const [gx_, gy_] = fn.d(x, y)\n \n const beta = Math.max(0, (gx_ * (gx_ - this.gx) + gy_ * (gy_ - this.gy)) / (this.gx * this.gx + this.gy * this.gy))\n\n const dx_ = -gx_ + beta * this.dx;\n const dy_ = -gy_ + beta * this.dy;\n\n [this.gx, this.gy, this.dx, this.dy] = [gx_, gy_, dx_, dy_]\n\n return lineSearch(fn, x, y, dx_, dy_)\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":123,"value":"class Momentum {\n constructor (alpha, beta) {\n this.alpha = alpha\n this.beta = beta\n this.vx = 0\n this.vy = 0\n }\n \n step (fn, x, y) {\n const [dx, dy] = fn.d(x, y)\n this.vx = this.beta * this.vx - this.alpha * dx\n this.vy = this.beta * this.vy - this.alpha * dy\n return [x + this.vx,\n y + this.vy]\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":158,"value":"class NesterovMomentum {\n constructor (alpha, beta) {\n this.alpha = alpha\n this.beta = beta\n this.vx = 0\n this.vy = 0\n }\n \n step (fn, x, y) {\n const [dx, dy] = fn.d(x + this.beta * this.vx, y + this.beta * this.vy)\n this.vx = this.beta * this.vx - this.alpha * dx\n this.vy = this.beta * this.vy - this.alpha * dy\n return [x + this.vx,\n y + this.vy]\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":732,"value":"class RMSProp {\n constructor (alpha, gamma, epsilon) {\n this.alpha = alpha\n this.gamma = gamma\n this.epsilon = epsilon\n this.sx = 0\n this.sy = 0\n }\n \n step (fn, x, y) {\n const [gx, gy] = fn.d(x, y)\n this.sx = this.gamma * this.sx + (1 - this.gamma) * (gx * gx)\n this.sy = this.gamma * this.sy + (1 - this.gamma) * (gy * gy)\n x = x - this.alpha * gx / (Math.sqrt(this.sx) + this.epsilon)\n y = y - this.alpha * gy / (Math.sqrt(this.sy) + this.epsilon)\n return [x, y]\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":696,"value":"class Adam {\n constructor (alpha, gamma_v, gamma_s, epsilon) {\n this.alpha = alpha\n this.gamma_v = gamma_v\n this.gamma_s = gamma_s\n this.epsilon = epsilon\n this.k = 0\n this.vx = 0\n this.vy = 0\n this.sx = 0\n this.sy = 0\n }\n\n step (fn, x, y) {\n const [gx, gy] = fn.d(x, y)\n \n this.vx = this.gamma_v * this.vx + (1 - this.gamma_v) * gx\n this.vy = this.gamma_v * this.vy + (1 - this.gamma_v) * gy\n \n this.sx = this.gamma_s * this.sx + (1 - this.gamma_s) * gx * gx\n this.sy = this.gamma_s * this.sy + (1 - this.gamma_s) * gy * gy\n \n this.k += 1\n \n const vx_hat = this.vx / (1 - this.gamma_v**this.k)\n const vy_hat = this.vy / (1 - this.gamma_v**this.k)\n \n const sx_hat = this.sx / (1 - this.gamma_s**this.k)\n const sy_hat = this.sy / (1 - this.gamma_s**this.k)\n \n x = x - this.alpha * vx_hat / (Math.sqrt(sx_hat) + this.epsilon)\n y = y - this.alpha * vy_hat / (Math.sqrt(sy_hat) + this.epsilon)\n\n return [x, y]\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":219,"value":"class HyperGradient {\n constructor (mu, alpha) {\n this.mu = mu\n this.alpha = alpha\n this.dxPrev = 0\n this.dyPrev = 0 \n }\n \n step (fn, x, y) {\n const [dx, dy] = fn.d(x, y)\n this.alpha = this.alpha + this.mu * (dx * this.dxPrev + dy * this.dyPrev)\n this.dxPrev = dx\n this.dyPrev = dy\n return [x - this.alpha * dx,\n y - this.alpha * dy] \n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":196,"value":"class HyperNesterovMomentum {\n constructor (mu, alpha, beta) {\n this.mu = mu\n this.alpha = alpha\n this.beta = beta\n this.vx = 0\n this.vy = 0\n this.dxPrev = 0\n this.dyPrev = 0\n }\n \n step (fn, x, y) {\n const [dx, dy] = fn.d(x, y)\n this.alpha = this.alpha + this.mu * (dx * (this.dxPrev + this.beta * this.vx) +\n dy * (this.dyPrev + this.beta * this.vy))\n \n this.vx = this.beta * this.vx + dx\n this.vy = this.beta * this.vy + dy\n \n this.dxPrev = dx\n this.dyPrev = dy\n \n return [x - this.alpha * (dx + this.beta * this.vx),\n y - this.alpha * (dy + this.beta * this.vy)] \n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":444,"value":"{\n const group = svg.select(\"#Newton\")\n \n group.selectAll(\"path\").remove()\n\n const path = group.append(\"path\")\n .attr(\"visibility\", methods.includes(\"Newton\") ? \"visible\" : \"hidden\")\n .attr(\"stroke\", \"orange\")\n .attr(\"stroke-width\", 0.5)\n .attr(\"fill\", \"none\")\n .attr(\"d\", `M${scaleX(start[0])},${scaleY(start[1])}`)\n \n descent(fn, start, new NewtonRaphson(), 1000, (x, y) => {\n path.attr(\"d\", path.attr(\"d\") + `L${scaleX(x)},${scaleY(y)}`)\n })\n\n return \"Newton\"\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":111,"value":"{\n const group = svg.select(\"#Gradient\")\n \n group.selectAll(\"path\").remove()\n \n const path = group.append('path')\n .attr(\"stroke\", \"red\")\n .attr(\"stroke-width\", 0.5)\n .attr(\"fill\", \"none\")\n .attr(\"d\", `M${scaleX(start[0])},${scaleY(start[1])}`)\n \n descent(fn, start, new Gradient(0.01), 1000, (x, y) => {\n path.attr(\"d\", path.attr(\"d\") + `L${scaleX(x)},${scaleY(y)}`)\n })\n\n return \"Gradient\"\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":520,"value":"{\n const group = svg.select(\"#CG\")\n \n group.selectAll(\"path\").remove()\n\n const path = group.append(\"path\")\n .attr(\"stroke\", \"purple\")\n .attr(\"stroke-width\", 0.5)\n .attr(\"fill\", \"none\")\n .attr(\"d\", `M${scaleX(start[0])},${scaleY(start[1])}`)\n \n descent(fn, start, new ConjugateGradient(fn, start[0], start[1]), 1000, (x, y) => {\n path.attr(\"d\", path.attr(\"d\") + `L${scaleX(x)},${scaleY(y)}`)\n })\n\n return \"Conjugate-Gradient\"\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":121,"value":"{\n const group = svg.select(\"#Momentum\")\n \n group.selectAll(\"path\").remove()\n\n const path = group.append(\"path\")\n .attr(\"stroke\", \"green\")\n .attr(\"stroke-width\", 0.5)\n .attr(\"fill\", \"none\")\n .attr(\"d\", `M${scaleX(start[0])},${scaleY(start[1])}`)\n \n descent(fn, start, new Momentum(0.01, 0.95), 1000, (x, y) => {\n path.attr(\"d\", path.attr(\"d\") + `L${scaleX(x)},${scaleY(y)}`)\n })\n\n return \"Momentum\"\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":360,"value":"{\n const group = svg.select(\"#Nesterov\")\n \n group.selectAll(\"path\").remove()\n\n const path = group.append(\"path\")\n .attr(\"stroke\", \"blue\")\n .attr(\"stroke-width\", 0.5)\n .attr(\"fill\", \"none\")\n .attr(\"d\", `M${scaleX(start[0])},${scaleY(start[1])}`)\n \n descent(fn, start, new NesterovMomentum(0.01, 0.95), 1000, (x, y) => {\n path.attr(\"d\", path.attr(\"d\") + `L${scaleX(x)},${scaleY(y)}`)\n })\n \n return \"Nesterov-Momentum\"\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":740,"value":"{\n const group = svg.select(\"#RMSProp\")\n \n group.selectAll(\"path\").remove()\n\n const path = group.append(\"path\")\n .attr(\"stroke\", colors[\"RMSProp\"])\n .attr(\"stroke-width\", 0.5)\n .attr(\"fill\", \"none\")\n .attr(\"d\", `M${scaleX(start[0])},${scaleY(start[1])}`)\n \n descent(fn, start, new RMSProp(0.2, 0.9, 1e-8), 1000, (x, y) => {\n path.attr(\"d\", path.attr(\"d\") + `L${scaleX(x)},${scaleY(y)}`)\n })\n \n return \"Adam\"\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":706,"value":"{\n const group = svg.select(\"#Adam\")\n \n group.selectAll(\"path\").remove()\n\n const path = group.append(\"path\")\n .attr(\"stroke\", colors[\"Adam\"])\n .attr(\"stroke-width\", 0.5)\n .attr(\"fill\", \"none\")\n .attr(\"d\", `M${scaleX(start[0])},${scaleY(start[1])}`)\n \n descent(fn, start, new Adam(0.2, 0.9, 0.999, 1e-8), 1000, (x, y) => {\n path.attr(\"d\", path.attr(\"d\") + `L${scaleX(x)},${scaleY(y)}`)\n })\n \n return \"Adam\"\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":669,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":612,"value":"bracketMinimum = function (f, x=0, s=1e-2, k=2.0) {\n let a = x\n let ya = f(x)\n let b = a + s\n let yb = f(a + s)\n\n if (yb > ya) {\n [a, b] = [b, a]\n [ya, yb] = [yb, ya]\n s = -s\n }\n\n while (true) {\n let c = b + s\n let yc = f(b + s)\n\n if (yc > yb) {\n return a < c ? [a, c] : [c, a]\n }\n a = b\n ya = yb\n b = c\n yb = yc\n s *= k\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":616,"value":"minimizeGoldenRatio = function (f, a, b, n=100) {\n let phi = (1 + Math.sqrt(5)) / 2\n let rho = phi - 1\n let d = rho * b + (1 - rho) * a\n let yd = f(d)\n \n for (let i = 0; i < n; i++) {\n let c = rho * a + (1-rho) *b\n let yc = f(c)\n if (yc < yd) {\n [b, d, yd] = [d, c, yc]\n } else {\n [a, b] = [b, c]\n }\n }\n \n return a < b ? [a, b] : [b, a]\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":604,"value":"lineSearch = function (fn, x, y, dx, dy) {\n const objective = alpha => fn(x + alpha * dx, y + alpha * dy)\n const [a, b] = bracketMinimum(objective)\n const [alpha, _] = minimizeGoldenRatio(objective, a, b)\n return [x + alpha * dx, y + alpha * dy]\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":674,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":722,"value":"colors = ({\n \"Newton\": \"orange\",\n \"Gradient\": \"red\",\n \"CG\": \"purple\",\n \"Momentum\": \"green\",\n \"Nesterov\": \"blue\",\n \"RMSProp\": \"olive\",\n \"Adam\": \"fuchsia\",\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":67,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":264,"value":"height = 600","pinned":false,"hidden":false,"mode":"ojs"},{"id":258,"value":"scaleX = d3.scaleLinear().domain([-2, 2]).range([0, height])","pinned":false,"hidden":false,"mode":"ojs"},{"id":261,"value":"scaleY = d3.scaleLinear().domain([-2, 2]).range([0, height])","pinned":false,"hidden":false,"mode":"ojs"},{"id":386,"value":"mousedown = function (event) {\n const [x, y] = d3.pointer(event)\n mutable start = [scaleX.invert(x), scaleY.invert(y)]\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":291,"value":"sleep = function (ms) {\n return new Promise(resolve => setTimeout(resolve, ms));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":492,"value":"{\n svg.select(\"#Newton\").attr(\"visibility\", methods.includes(\"Newton\") ? \"visible\" : \"hidden\")\n svg.select(\"#Gradient\").attr(\"visibility\", methods.includes(\"Gradient\") ? \"visible\" : \"hidden\")\n svg.select(\"#CG\").attr(\"visibility\", methods.includes(\"CG\") ? \"visible\" : \"hidden\")\n svg.select(\"#Momentum\").attr(\"visibility\", methods.includes(\"Momentum\") ? \"visible\" : \"hidden\")\n svg.select(\"#Nesterov\").attr(\"visibility\", methods.includes(\"Nesterov\") ? \"visible\" : \"hidden\")\n\n return \"Visibility\"\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":63,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":14,"value":"fn = {\n const node = math.parse(expr)\n const code = node.compile()\n const fn = (x, y) => node.evaluate({x, y})\n fn.d = (x, y) => [dx(x, y), dy(x, y)]\n fn.dd = (x, y) => [dxx(x, y), dxy(x, y), dyy(x, y)]\n return fn\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":27,"value":"dx = {\n const node = math.derivative(expr, \"x\")\n const code = node.compile()\n return (x, y) => node.evaluate({x, y})\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":34,"value":"dy = {\n const node = math.derivative(expr, \"y\")\n const code = node.compile()\n return (x, y) => node.evaluate({x, y})\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":176,"value":"dxx = {\n const node = math.derivative(math.derivative(expr, \"x\"), \"x\")\n const code = node.compile()\n return (x, y) => node.evaluate({x, y})\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":179,"value":"dxy = {\n const node = math.derivative(math.derivative(expr, \"x\"), \"y\")\n const code = node.compile()\n return (x, y) => node.evaluate({x, y})\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":181,"value":"dyy = {\n const node = math.derivative(math.derivative(expr, \"y\"), \"y\")\n const code = node.compile()\n return (x, y) => node.evaluate({x, y})\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":59,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":3,"value":"d3 = require(\"d3@6\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"math = require(\"mathjs@9\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}