viewof viz = {
var width = 960,
height = 500,
nx = parseInt(width / 5),
ny = parseInt(height / 5),
h = 1e-7,
drawing_time = 30;
var svg = d3.select(DOM.svg(width, height));
var domain_x = [-1.5, 1.5],
domain_y = [-1, 3],
domain_f = [0,15],
contour_step = 0.5;
var scale_x = d3.scaleLinear()
.domain([0, width])
.range(domain_x);
var scale_y = d3.scaleLinear()
.domain([0, height])
.range(domain_y);
var thresholds = d3.range(domain_f[0], domain_f[1], contour_step);
var color_scale = d3.scaleLinear()
.domain(d3.extent(thresholds))
.interpolate(function() { return d3.interpolateYlGnBu; });
var function_g = svg.append("g").on("mousedown", mousedown),
gradient_path_g = svg.append("g"),
menu_g = svg.append("g");
function f(x, y) {
return Math.pow(1 - x, 2) + 2 * Math.pow(y - x * x, 2);
}
function grad_f(x, y) {
var grad_x = (f(x + h, y) - f(x, y)) / h,
grad_y = (f(x, y + h) - f(x, y)) / h;
return [grad_x, grad_y];
}
function sec_grad_f(x, y) {
var sec_grad_xx = (((f(x + h + h, y) - f(x + h, y)) / h) - ((f(x + h, y) - f(x, y)) / h)) / h
var sec_grad_xy = (((f(x + h, y + h) - f(x, y + h)) / h) - ((f(x + h, y) - f(x, y)) / h)) / h
var sec_grad_yx = (((f(x + h, y + h) - f(x + h, y)) / h) - ((f(x, y + h) - f(x, y)) / h)) / h
var sec_grad_yy = (((f(x, y + h + h) - f(x, y + h)) / h) - ((f(x, y + h) - f(x, y)) / h)) / h
return [[sec_grad_xx, sec_grad_xy], [sec_grad_yx, sec_grad_yy]];
}
function inverse(x) {
var a, b, c, d;
a = x[0][0];
b = x[0][1];
c = x[1][0];
d = x[1][1];
var coef = 1 / (a * d - b * c);
return [[coef * d, -coef * b], [-coef * c, coef * a]]
}
function get_f_values(nx, ny) {
var grid = new Array(nx * ny);
for (var i = 0; i < nx; i++) {
for (var j = 0; j < ny; j++) {
var x = scale_x( parseFloat(i) / nx * width ),
y = scale_y( parseFloat(j) / ny * height );
grid[i + j * nx] = f(x, y);
}
}
return grid;
}
function backtrack(x,y,alpha,beta,delta){
var t=1;
var gradient=grad_f(x,y);
var left_val=f(x-delta[0]*t,y-delta[1]*t);
var right_val=f(x,y)-alpha*t*(gradient[0]*delta[0]+gradient[1]*delta[1]);
while(left_val>right_val){
t=beta*t;
left_val=f(x-delta[0]*t,y-delta[1]*t);
right_val=f(x,y)-alpha*t*(gradient[0]*delta[0]+gradient[1]*delta[1]);
}
console.log(t)
return t
}
var contours = d3.contours()
.size([nx, ny])
.thresholds(thresholds);
var f_values = get_f_values(nx, ny);
function_g.selectAll("path")
.data(contours(f_values))
.enter().append("path")
.attr("d", d3.geoPath(d3.geoIdentity().scale(width / nx)))
.attr("fill", function(d) { return color_scale(d.value); })
.attr("stroke", "none");
var draw_bool = {"SGD": true, "Newton": true,"SGD_BLS":true,"Newton_BLS":true};
var buttons = ["SGD", "Newton","SGD_BLS","Newton_BLS"];
menu_g.append("rect")
.attr("x", 0)
.attr("y", height - 40)
.attr("width", width)
.attr("height", 40)
.attr("fill", "white")
.attr("opacity", 0.2);
menu_g.selectAll("circle")
.data(buttons)
.enter()
.append("circle")
.attr("cx", function(d,i) { return width/4 * (i + 0.25);} )
.attr("cy", height - 20)
.attr("r", 10)
.attr("stroke-width", 0.5)
.attr("stroke", "black")
.attr("class", function(d) { return d;})
.attr("fill-opacity", 0.5)
.attr("stroke-opacity", 1)
.on("mousedown", button_press);
menu_g.selectAll("text")
.data(buttons)
.enter()
.append("text")
.attr("x", function(d,i) { return width/4 * (i + 0.25) + 18;} )
.attr("y", height - 14)
.text(function(d) { return d; })
.attr("text-anchor", "start")
.attr("font-family", "Helvetica Neue")
.attr("font-size", 15)
.attr("font-weight", 200)
.attr("fill", "white")
.attr("fill-opacity", 0.8);
function button_press() {
var type = d3.select(this).attr("class")
if (draw_bool[type]) {
d3.select(this).attr("fill-opacity", 0);
draw_bool[type] = false;
} else {
d3.select(this).attr("fill-opacity", 0.5)
draw_bool[type] = true;
}
}
function get_sgd_path(x0, y0, learning_rate, num_steps) {
var sgd_history = [{"x": scale_x.invert(x0), "y": scale_y.invert(y0)}];
var x1, y1, gradient;
for (var i = 0; i < num_steps; i++) {
gradient = grad_f(x0, y0);
x1 = x0 - learning_rate * gradient[0]
y1 = y0 - learning_rate * gradient[1]
sgd_history.push({"x" : scale_x.invert(x1), "y" : scale_y.invert(y1)})
x0 = x1
y0 = y1
}
return sgd_history;
}
function get_newton_path(x0, y0, learning_rate, num_steps) {
var newton_history = [{"x": scale_x.invert(x0), "y": scale_y.invert(y0)}];
var x1, y1, gradient, sec_gradient, inverse_secgrad;
for (var i = 0; i < num_steps; i++) {
gradient = grad_f(x0, y0)
sec_gradient = sec_grad_f(x0, y0)
inverse_secgrad = inverse(sec_gradient)
x1 = x0 - learning_rate * (inverse_secgrad[0][0] * gradient[0] + inverse_secgrad[0][1] * gradient[1])
y1 = y0 - learning_rate * (inverse_secgrad[1][0] * gradient[0] + inverse_secgrad[1][1] * gradient[1])
newton_history.push({"x": scale_x.invert(x1), "y": scale_y.invert(y1)})
x0 = x1
y0 = y1
}
return newton_history;
}
function get_sgd_bls_path(x0, y0, alpha, beta, num_steps) {
var sgd_history = [{"x": scale_x.invert(x0), "y": scale_y.invert(y0)}];
var x1, y1, gradient,t;
for (var i = 0; i < num_steps; i++) {
gradient = grad_f(x0, y0);
t=backtrack(x0,y0,alpha,beta,gradient)
x1 = x0 - t * gradient[0]
y1 = y0 - t * gradient[1]
sgd_history.push({"x" : scale_x.invert(x1), "y" : scale_y.invert(y1)})
x0 = x1
y0 = y1
}
return sgd_history;
}
function get_newton_bls_path(x0, y0, alpha, beta, num_steps) {
var newton_history = [{"x": scale_x.invert(x0), "y": scale_y.invert(y0)}];
var x1, y1, gradient, sec_gradient, inverse_secgrad,delta,t;
for (var i = 0; i < num_steps; i++) {
gradient = grad_f(x0, y0)
sec_gradient = sec_grad_f(x0, y0)
inverse_secgrad = inverse(sec_gradient)
delta=[inverse_secgrad[0][0] * gradient[0]+inverse_secgrad[0][1] *gradient[1],inverse_secgrad[1][0] * gradient[0]+inverse_secgrad[1][1] * gradient[1]]
t=backtrack(x0,y0,alpha,beta,delta)
x1 = x0 - t*delta[0]
y1 = y0 - t*delta[1]
newton_history.push({"x": scale_x.invert(x1), "y": scale_y.invert(y1)})
x0 = x1
y0 = y1
}
return newton_history;
}
var line_function = d3.line()
.x(function(d) { return d.x; })
.y(function(d) { return d.y; });
function draw_path(path_data, type) {
var gradient_path = gradient_path_g.selectAll(type)
.data(path_data)
.enter()
.append("path")
.attr("d", line_function(path_data.slice(0,1)))
.attr("class", type)
.attr("stroke-width", 3)
.attr("fill", "none")
.attr("stroke-opacity", 0.5)
.transition()
.duration(drawing_time)
.delay(function(d,i) { return drawing_time * i; })
.attr("d", function(d,i) { return line_function(path_data.slice(0,i+1));})
.remove();
gradient_path_g.append("path")
.attr("d", line_function(path_data))
.attr("class", type)
.attr("stroke-width", 3)
.attr("fill", "none")
.attr("stroke-opacity", 0.5)
.attr("stroke-opacity", 0)
.transition()
.duration(path_data.length * drawing_time)
.attr("stroke-opacity", 0.5);
}
function mousedown() {
var point = d3.mouse(this);
minimize(scale_x(point[0]), scale_y(point[1]));
}
function minimize(x0,y0) {
gradient_path_g.selectAll("path").remove();
if (draw_bool.SGD) {
var sgd_data = get_sgd_path(x0, y0, 3e-2, 500);
draw_path(sgd_data, "sgd");
}
if (draw_bool.Newton) {
var new_data = get_newton_path(x0, y0, 1e-1, 200);
draw_path(new_data, "new");
}
if (draw_bool.SGD_BLS) {
var sgd_bls_data = get_sgd_bls_path(x0, y0, 0.25, 0.5, 300);
draw_path(sgd_bls_data, "sgd_bls");
}
if (draw_bool.Newton_BLS) {
var new_bls_data = get_newton_bls_path(x0, y0, 0.25, 0.5, 500);
draw_path(new_bls_data, "new_bls");
}
}
return svg.node();
}