Project 0: Octave Basics

Optimize your breakfast:
ditch Fruit Loops for Chex!

Introduction

In this project, you will write a function to compute Euclidean distances between sets of vectors. But before you get started, you need to check out your code onto whatever computer you want to use.

How to check out your code: The first thing you need to do is obtain your code from the server. We use subversion, which should be installed on your Mac OSX or Linux computer as svn. (If you have Windows you can use TortoiseSVN or install Linux in a Virtual Box.)
To check out your code with the following command line call:

svn checkout svn+ssh://YOURNETID@en-cs-cs4780.coecis.cornell.edu:/opt/cs4780/repos/YOURNETID

svn update

The code for this project (project0) consists of several text files, some of which you will need to read and understand in order to complete the assignment, and some of which you can ignore.

How to submit: You can commit your code with subversion, with the command line

svn commit -m "some meaningful comment"

Evaluation: Your code will be autograded for technical correctness. Please do not change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. However, the correctness of your implementation -- not the autograder's output -- will be the final judge of your score. If necessary, we will review and grade assignments individually to ensure that you receive due credit for your work.

Academic Dishonesty: We will be checking your code against other submissions in the class for logical redundancy. If you copy someone else's code and submit it with minor changes, we will know. These cheat detectors are quite hard to fool, so please don't try. We trust you all to submit your own work only; please don't let us down. If you do, we will pursue the strongest consequences available to us.

Getting Help: You are not alone! If you find yourself stuck on something, contact the course staff for help. Office hours, section, and the Piazza are there for your support; please use them. If you can't make our office hours, let us know and we will schedule more. We want these projects to be rewarding and instructional, not frustrating and demoralizing. But, we don't know when or how to help unless you ask.

Euclidean distances in Octave

Many machine learning algorithms access their input data primarily through pairwise distances. It is therefore important that we have a fast function that computes pairwise (Euclidean) distances of input vectors. Assume we have $n$ data vectors $\vec x_1,\dots,\vec x_n\in{\cal R}^d$ and $m$ vectors $\vec z_1,\dots,z_m\in{\cal R}^d$. And let us define two matrices $X=[\vec x_1,\dots,\vec x_n]\in{\cal R}^{d\times n}$, where the $i^{th}$ column is a vector $\vec x_i$ and similarly $Z=[\vec z_1,\dots,\vec z_m]$. Our distance function takes as input the two matrices $X$ and $Z$ and outputs a matrix $D\in{\cal R}^{n\times m}$, where

How not to program in Octave

A naive Octave implementation of such a distance function would look like this:

function D=l2distanceSlow(X,Z)
[d,n]=size(X); % dimension of X
[~,m]=size(Z); % dimension of Z
D=zeros(n,m); % allocate memory for the output matrix
 for i=1:n % loop over vectors in X
	for j=1:m % loop over vectors in Z
		D(i,j)=0.0; 
		for k=1:d % loop over dimensions
			D(i,j)=D(i,j)+(X(k,i)-Z(k,j))^2; % compute l2-distance between the ith and jth vector
		end;
		D(i,j)=sqrt(D(i,j)); % take square root
	end;
 end;

	X=rand(100,100);
	Z=rand(100,50);
	tic;D=l2distanceSlow(X,Z);toc 

What is the problem? Octave is an interpreted language with a lot of slow execution overhead. This means you have to pay dearly for every command you execute. In our example we have three nested loops and call the inner most line many many times. This means almost our entire running time is spent in execution overhead. As a general rule, you should avoid tight loops at all cost.

How to program in Octave

Although there is an execution overhead per line in Octave, matrix operations are extremely optimized and very fast. In order to become a successful Octave programmer, you need to free yourself from the "for-loop" thinking and start thinking in terms of matrix operations. Octave can be very fast, if almost all the time is spent in a few heavy duty matrix operations. In this assignment you will do this, and transform the function above into a few matrix operations without any loops at all.

The key to efficient programming in Octave and machine learning in general is to think about it in terms of mathematics, and not in terms of Loops.

(a) Show that the Gram matrix (aka inner-product matrix)

My Answer to (a): (Please edit the .html file and "svn commit".)

(b) Let us define two new matrices $S,R\in{\cal R}^{n\times m}$

My Answer to (b):

(c) Implement the function l2distance.m, which computes the Euclidean distance matrix $D$ without a single loop. Test the distance function again:

X=rand(100,100);
Z=rand(100,50);
tic;D=l2distance(X,Z);toc 

hw0tictoc

My Answer to (c):

Hints

Tests. To test your code you can run hw0tests, which runs several unit tests. As your project progresses, slowly but surely these tests should stop failing.

Timing: To evaluate how fast your final code is, run hw0tictoc.

Credits