Sparse coding

An ordinary least square regression does not apply regularization on the parameters we try to estimate. Often we regularize the optimization problem. This practice is know as shrinkage in statistics. The classic regularizer is the squared $l_2$ norm of the parameters to estimate. This results in the familiar ridge regression problem.

Lasso stands for "Least Absolute Shrinkage and Selection Operator." It replaces the 2-norm in ridge regression with a 1-norm. Lasso is often used in sparse coding because it provides a sparse solution in the sense that many parameters are zero for large enough regularization factor.

References:
http://pages.cs.wisc.edu/~jerryzhu/cs731/regression.pdf

DFS in action

Solution to level 13 robotMaze in Untrusted: http://alex.nisnevich.com/untrusted/

	/*
	* robotMaze.js
	*
	* The blue key is inside a labyrinth, and extracting
	* it will not be easy.
	*
	* It's a good thing that you're a AI expert, or
	* we would have to leave empty-handed.
	*/
	function startLevel(map) {
	// Hint: you can press R or 5 to "rest" and not move the
	// player, while the robot moves around.
	map.getRandomInt = function(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
	}
	map.placePlayer(map.getWidth()-1, map.getHeight()-1);
	var player = map.getPlayer();
	map.defineObject('robot', {
	'type': 'dynamic',
	'symbol': 'R',
	'color': 'gray',
	'onCollision': function (player, me) {
	me.giveItemTo(player, 'blueKey');
	},
	'behavior': function (me) {
	if (map.path) {
	if (map.path.length > 0) {
	var dir = map.path[map.path.length - 1];
	me.move(dir);
	map.path.pop();
	} else {
	me.move('down');
	}
	} else {
	var parent = new Array(10);
	for (var i = 0; i < 10; i++) {
	parent[i] = new Array(map.getWidth());
	}
	parent[me.getY()][me.getX()] = [[-1, -1], ''];
	var endX = map.getWidth() - 2;
	var endY = 7;
	var dfs = function (x, y) {
	if (x == endX && y == endY)
	return;
	var moves = map.getAdjacentEmptyCells(x, y);
	for (var i = 0; i < moves.length; i++) {
	var nextx = moves[i][0][0];
	var nexty = moves[i][0][1];
	if (!parent[nexty][nextx]) {
	parent[nexty][nextx] = [[x, y], moves[i][1]];
	dfs(nextx, nexty);
	}
	}
	}
	dfs(me.getX(), me.getY());
	var x = endX;
	var y = endY;
	map.path = [];
	while (parent[y][x][1] != '') {
	map.path.push(parent[y][x][1]);
	var xy = parent[y][x][0];
	y = xy[1];
	x = xy[0]
	}
	}
	}
	});
	map.defineObject('barrier', {
	'symbol': '░',
	'color': 'purple',
	'impassable': true,
	'passableFor': ['robot']
	});
	map.placeObject(0, map.getHeight() - 1, 'exit');
	map.placeObject(1, 1, 'robot');
	map.placeObject(map.getWidth() - 2, 8, 'blueKey');
	map.placeObject(map.getWidth() - 2, 9, 'barrier');
	var autoGeneratedMaze = new ROT.Map.DividedMaze(map.getWidth(), 10);
	autoGeneratedMaze.create( function (x, y, mapValue) {
	// don't write maze over robot or barrier
	if ((x == 1 && y == 1) || (x == map.getWidth() - 2 && y >= 8)) {
	return 0;
	} else if (mapValue === 1) { //0 is empty space 1 is wall
	map.placeObject(x,y, 'block');
	} else {
	map.placeObject(x,y,'empty');
	}
	});
	}
	function validateLevel(map) {
	map.validateExactlyXManyObjects(1, 'exit');
	map.validateExactlyXManyObjects(1, 'robot');
	map.validateAtMostXObjects(1, 'blueKey');
	}
	function onExit(map) {
	if (!map.getPlayer().hasItem('blueKey')) {
	map.writeStatus("We need to get that key!");
	return false;
	} else {
	return true;
	}
	}

view raw untrusted-lvl13-solution.js hosted with ❤ by GitHub