jonahwilliams · June 3, 2015 00:33
diff --git a/index.html b/index.html
 <!DOCTYPE html>
 <meta charset="utf-8">
 <head>
 <script src="http://d3js.org/d3.v3.min.js"></script>
 <script src="SMO.js"></script>
 <style>
 .axis {
  font: 10px sans-serif;
 }
 path { 
    stroke: steelblue;
    stroke-width: 2;
    fill: none;
 }

 .axis path,
 .axis line {
  fill: none;
  stroke: #000;
  shape-rendering: crispEdges;
 }
 </style>
 </head>
 <body>
 <script>
 var margin = {top: 80, right: 180, bottom: 80, left: 180},
    width = 960 - margin.left - margin.right,
    height = 500 - margin.top - margin.bottom;

 var svg = d3.select("body").append("svg")
 	.attr("width", width + margin.left + margin.right)
    .attr("height", height + margin.top + margin.bottom)
 	.append("g")
    .attr("transform", "translate(" + margin.left + "," + margin.top + ")");

 var y = d3.scale.linear()
 		.domain([0, 10])
 		.range([height, 0]);

 var x = d3.scale.linear()
 		.domain([0, 10])
 		.range([0, width])

 var xAxis = d3.svg.axis()
 	.scale(x)
    .orient("bottom");

 var yAxis = d3.svg.axis()
 	.scale(y)
    .orient("left");

 var line = d3.svg.line()
 	.x(function(d) { return x(d.x); })
 	.y(function(d) { return y(d.y); });

 svg.append("g")
 	.attr("class", "x axis")
 	.attr("transform", "translate(0," + height + ")")
 	.call(xAxis)

 svg.append("g")
 	.attr("class", "y axis")
 	.call(yAxis);


 d3.json("PerceptronClassifier.json", function(error, data){

 	dots = svg.selectAll(".dot")
 		.data(data)
 		.enter().append("circle")
 		.attr("class", "dot")
 		.attr("r", 5.5)
 		.attr("cx", function(d){
 			return x(+d.x);
 		})
 		.attr("cy", function(d){
 			return y(+d.y)
 		})
 		.style("fill", function(d){
 			if (d.c == 1){
 				return "#377eb8";
 			}
 			else {
 				return "#e41a1c";
 			}
 		})
 		.style("stroke-width", 2);

 	var X = [],
 		Y = [];

 	for (var i = data.length - 1; i >= 0; i--) {
 		X[i] = [+data[i].x, +data[i].y];
 		Y[i] = +data[i].c;
 	};

 	V = SMO(X, Y, 1, 0.000001, 30, -1);
 	var w = V.w[0],
 		b = V.b;

 	var decision = [];
 	for (var i = 0; i < 1000; i++){
 		decision[i] = {'x' : i / 100, 'y': (-w[0] / w[1]) * (i / 100) - (b / w[1])};
 	}

 	var pg = [];
 	for (var i = 0; i < 1000; i++){
 	 	pg[i] = {'x' : i / 100, 'y': (-w[0] / w[1]) * (i / 100) - ((1 + b) / w[1])};
 	}

 	var ng = [];
 	for (var i = 0; i < 1000; i++){
 		ng[i] = {'x' : i / 100, 'y': (-w[0] / w[1]) * (i / 100) - ((-1 + b) / w[1])};
 	}

 	svg.append("path")
 		.datum(decision)
 		.attr("class", "line")
 		.attr("d", line);
 		
 	svg.append("path")
 		.datum(pg)
 		.attr("class", "line")
 		.attr("d", line)
 		.style("stroke-dasharray", "10,10");

 	svg.append("path")
 		.datum(ng)
 		.attr("class", "line")
 		.attr("d", line)
 		.style("stroke-dasharray", "10,10");

 });
 </script>
 </body>
diff --git a/PerceptronClassifier.json b/PerceptronClassifier.json
 [{"x":1.3918159586,"y":2.3137462987,"c":-1},{"x":2.7553492977,"y":3.8358933062,"c":-1},{"x":1.3068825052,"y":1.562141254,"c":-1},{"x":2.8944226465,"y":2.5841533943,"c":-1},{"x":3.7024428812,"y":2.7501198675,"c":-1},{"x":3.5026863304,"y":4.1441852379,"c":-1},{"x":1.2875267989,"y":1.6449839313,"c":-1},{"x":1.5512224368,"y":3.479681808,"c":-1},{"x":2.4134867529,"y":4.2236237896,"c":-1},{"x":3.6559341255,"y":1.9783436371,"c":-1},{"x":6.9659900849,"y":5.3009901301,"c":1.0},{"x":9.0119210614,"y":7.702946096,"c":1.0},{"x":5.950966712,"y":7.2311001543,"c":1.0},{"x":5.979236673,"y":7.7339372771,"c":1.0},{"x":5.955605886,"y":6.8574976596,"c":1.0},{"x":7.8664572356,"y":6.3242365141,"c":1.0},{"x":5.2714950518,"y":6.744864841,"c":1.0},{"x":7.0457948624,"y":8.2216029477,"c":1.0},{"x":8.3580121873,"y":7.1820232618,"c":1.0},{"x":9.6273291291,"y":7.0579781464,"c":1.0}]
diff --git a/SMO.js b/SMO.js
 function SMO(X, y, C, tolerance, max_passes, gamma){
 	//Performs the SMO algorithm to determine Lagrange Multipliers for a SVM

 	var n = X.length, //Size of Data
 		a = [],          //Lagrange Multipliers
 		E = [],			 //Expected Values
 		b = 0.0,	     //Threshold
 		passes = 0,		 //Current Passes
 		num_changed_alphas = 0;     

 	//initialize lagrange multipliers
 	for (var i = n - 1; i >= 0; i--) {
 		a[i] = 0.0;
 		E[i] = 0.0;
 	};

 	while (passes < max_passes) {
 		num_changed_alphas = 0;

 		//Calculate Ei = f(x_i) - y_i
 		for (var i = n - 1; i >= 0; i--) {
 			
 			E[i] = b - y[i];
 			for (var j = n - 1; j >= 0; j--) {
 				E[i] += (y[j] * a[j] * RBF(X[i], X[j], gamma));
 			};



 			if ((y[i] * E[i] < -tolerance && a[i] < C) || (y[i] * E[i] > tolerance && a[i] > 0)){
 				//Select j != i Randomly

 				do {
 					j = Math.floor(Math.random() * n);
 				}
 				while(j == i);

 				//Calculate Ej = f(x_j) - y_j
 				E[j] = b - y[j];
 				for (var k = n - 1; k >= 0; k--) {
 					E[j] += (y[k] * a[k] *
 					        RBF(X[j], X[k], gamma)) ;
 				};
 	
 				var alpha_old_i = a[i],
 					alpha_old_j = a[j];

 				//Compute L and H by 10 or 11
 				if (y[i] != y[j]){
 					var L = Math.max(0, a[j] - a[i]);
 					var H = Math.min(C, C + a[j] - a[i]);
 				}
 				else {
 					var L = Math.max(0, a[i] + a[j] - C);
 					var H = Math.min(C, a[j] + a[i]);
 				}

 				if(L == H){
 					continue;
 				}

 				//Compute nen by 14
 				var nen = 2 * RBF(X[i], X[j], gamma) -
 				        RBF(X[i], X[i], gamma) -
 				        RBF(X[j], X[j], gamma);

 				if (nen >= 0){
 					continue;
 				}

 				//Compute and clip new value for aj using 12 and 15
 				a[j] = a[j] - ((y[j] * (E[i] - E[j])) / nen);

 				//Clip aj to fall in range
 				if (a[j] > H){
 					a[j] = H;
 				}
 				else if (a[j] < L){
 					a[j] = L;
 				}

 				//Check Change
 				if (Math.abs(a[j] - alpha_old_j) < 10e-5){
 					continue;
 				}
 				//Compute value for ai using 16
 				a[i] = a[i] + (y[i] * y[j] * (alpha_old_j - a[j]));


 				//Compute b1 and b2 with 17 and 18
 				var b1 = b - E[i] - y[i] * (a[i] - alpha_old_i) *
 				        RBF(X[i], X[i], gamma) - y[j] *
 				        (a[j] - alpha_old_j) * RBF(X[i], X[j], gamma);

 				var b2 = b - E[j] - y[i] * (a[i] - alpha_old_i) *
 				        RBF(X[i], X[j], gamma) - y[j] *
 				        (a[j] - alpha_old_j) * RBF(X[j], X[j], gamma);

 				//Compute b by 19
 				if ((a[i] > 0) && (a[i] < C)){
 					b = b1;
 				}
 				else if ((a[j] > 0) && (a[j] < C)){
 					b = b2;
 				}
 				else {
 					b = (b1 + b2) / 2;
 				}
 				num_changed_alphas += 1;
 			};
 		};
 		if (num_changed_alphas == 0){
 			passes += 1;
 		}
 		else {
 			passes = 0;
 		}
 	};

 	var w = [[]];
 	for (var i = X[0].length - 1; i >= 0; i--) {
 		w[0][i] = 0; 	
 	};
 	for (var i = n - 1; i >= 0; i--) {
 		for (var j = X[0].length - 1; j >= 0; j--) {
 			w[0][j] += a[i] * X[i][j] * y[i];
 		};
 	};
 	return {'w' : w, 'b' : b};
 }

 function RBF(a, b, gamma){
 	var d = 0.0;

 	for (var i = a.length - 1; i >= 0; i--) {
 		d += a[i] * b[i]
 	};
 	return d;
 }
	<!DOCTYPE html>
	<meta charset="utf-8">
	<head>
	<script src="http://d3js.org/d3.v3.min.js"></script>
	<script src="SMO.js"></script>
	<style>
	.axis {
	font: 10px sans-serif;
	}
	path {
	stroke: steelblue;
	stroke-width: 2;
	fill: none;
	}

	.axis path,
	.axis line {
	fill: none;
	stroke: #000;
	shape-rendering: crispEdges;
	}
	</style>
	</head>
	<body>
	<script>
	var margin = {top: 80, right: 180, bottom: 80, left: 180},
	width = 960 - margin.left - margin.right,
	height = 500 - margin.top - margin.bottom;

	var svg = d3.select("body").append("svg")
	.attr("width", width + margin.left + margin.right)
	.attr("height", height + margin.top + margin.bottom)
	.append("g")
	.attr("transform", "translate(" + margin.left + "," + margin.top + ")");

	var y = d3.scale.linear()
	.domain([0, 10])
	.range([height, 0]);

	var x = d3.scale.linear()
	.domain([0, 10])
	.range([0, width])

	var xAxis = d3.svg.axis()
	.scale(x)
	.orient("bottom");

	var yAxis = d3.svg.axis()
	.scale(y)
	.orient("left");

	var line = d3.svg.line()
	.x(function(d) { return x(d.x); })
	.y(function(d) { return y(d.y); });

	svg.append("g")
	.attr("class", "x axis")
	.attr("transform", "translate(0," + height + ")")
	.call(xAxis)

	svg.append("g")
	.attr("class", "y axis")
	.call(yAxis);


	d3.json("PerceptronClassifier.json", function(error, data){

	dots = svg.selectAll(".dot")
	.data(data)
	.enter().append("circle")
	.attr("class", "dot")
	.attr("r", 5.5)
	.attr("cx", function(d){
	return x(+d.x);
	})
	.attr("cy", function(d){
	return y(+d.y)
	})
	.style("fill", function(d){
	if (d.c == 1){
	return "#377eb8";
	}
	else {
	return "#e41a1c";
	}
	})
	.style("stroke-width", 2);

	var X = [],
	Y = [];

	for (var i = data.length - 1; i >= 0; i--) {
	X[i] = [+data[i].x, +data[i].y];
	Y[i] = +data[i].c;
	};

	V = SMO(X, Y, 1, 0.000001, 30, -1);
	var w = V.w[0],
	b = V.b;

	var decision = [];
	for (var i = 0; i < 1000; i++){
	decision[i] = {'x' : i / 100, 'y': (-w[0] / w[1]) * (i / 100) - (b / w[1])};
	}

	var pg = [];
	for (var i = 0; i < 1000; i++){
	pg[i] = {'x' : i / 100, 'y': (-w[0] / w[1]) * (i / 100) - ((1 + b) / w[1])};
	}

	var ng = [];
	for (var i = 0; i < 1000; i++){
	ng[i] = {'x' : i / 100, 'y': (-w[0] / w[1]) * (i / 100) - ((-1 + b) / w[1])};
	}

	svg.append("path")
	.datum(decision)
	.attr("class", "line")
	.attr("d", line);

	svg.append("path")
	.datum(pg)
	.attr("class", "line")
	.attr("d", line)
	.style("stroke-dasharray", "10,10");

	svg.append("path")
	.datum(ng)
	.attr("class", "line")
	.attr("d", line)
	.style("stroke-dasharray", "10,10");

	});
	</script>
	</body>
	function SMO(X, y, C, tolerance, max_passes, gamma){
	//Performs the SMO algorithm to determine Lagrange Multipliers for a SVM

	var n = X.length, //Size of Data
	a = [], //Lagrange Multipliers
	E = [], //Expected Values
	b = 0.0, //Threshold
	passes = 0, //Current Passes
	num_changed_alphas = 0;

	//initialize lagrange multipliers
	for (var i = n - 1; i >= 0; i--) {
	a[i] = 0.0;
	E[i] = 0.0;
	};

	while (passes < max_passes) {
	num_changed_alphas = 0;

	//Calculate Ei = f(x_i) - y_i
	for (var i = n - 1; i >= 0; i--) {

	E[i] = b - y[i];
	for (var j = n - 1; j >= 0; j--) {
	E[i] += (y[j] * a[j] * RBF(X[i], X[j], gamma));
	};



	if ((y[i] * E[i] < -tolerance && a[i] < C) \|\| (y[i] * E[i] > tolerance && a[i] > 0)){
	//Select j != i Randomly

	do {
	j = Math.floor(Math.random() * n);
	}
	while(j == i);

	//Calculate Ej = f(x_j) - y_j
	E[j] = b - y[j];
	for (var k = n - 1; k >= 0; k--) {
	E[j] += (y[k] * a[k] *
	RBF(X[j], X[k], gamma)) ;
	};

	var alpha_old_i = a[i],
	alpha_old_j = a[j];

	//Compute L and H by 10 or 11
	if (y[i] != y[j]){
	var L = Math.max(0, a[j] - a[i]);
	var H = Math.min(C, C + a[j] - a[i]);
	}
	else {
	var L = Math.max(0, a[i] + a[j] - C);
	var H = Math.min(C, a[j] + a[i]);
	}

	if(L == H){
	continue;
	}

	//Compute nen by 14
	var nen = 2 * RBF(X[i], X[j], gamma) -
	RBF(X[i], X[i], gamma) -
	RBF(X[j], X[j], gamma);

	if (nen >= 0){
	continue;
	}

	//Compute and clip new value for aj using 12 and 15
	a[j] = a[j] - ((y[j] * (E[i] - E[j])) / nen);

	//Clip aj to fall in range
	if (a[j] > H){
	a[j] = H;
	}
	else if (a[j] < L){
	a[j] = L;
	}

	//Check Change
	if (Math.abs(a[j] - alpha_old_j) < 10e-5){
	continue;
	}
	//Compute value for ai using 16
	a[i] = a[i] + (y[i] * y[j] * (alpha_old_j - a[j]));


	//Compute b1 and b2 with 17 and 18
	var b1 = b - E[i] - y[i] * (a[i] - alpha_old_i) *
	RBF(X[i], X[i], gamma) - y[j] *
	(a[j] - alpha_old_j) * RBF(X[i], X[j], gamma);

	var b2 = b - E[j] - y[i] * (a[i] - alpha_old_i) *
	RBF(X[i], X[j], gamma) - y[j] *
	(a[j] - alpha_old_j) * RBF(X[j], X[j], gamma);

	//Compute b by 19
	if ((a[i] > 0) && (a[i] < C)){
	b = b1;
	}
	else if ((a[j] > 0) && (a[j] < C)){
	b = b2;
	}
	else {
	b = (b1 + b2) / 2;
	}
	num_changed_alphas += 1;
	};
	};
	if (num_changed_alphas == 0){
	passes += 1;
	}
	else {
	passes = 0;
	}
	};

	var w = [[]];
	for (var i = X[0].length - 1; i >= 0; i--) {
	w[0][i] = 0;
	};
	for (var i = n - 1; i >= 0; i--) {
	for (var j = X[0].length - 1; j >= 0; j--) {
	w[0][j] += a[i] * X[i][j] * y[i];
	};
	};
	return {'w' : w, 'b' : b};
	}

	function RBF(a, b, gamma){
	var d = 0.0;

	for (var i = a.length - 1; i >= 0; i--) {
	d += a[i] * b[i]
	};
	return d;
	}