Bumblebee

In the beginning of the semester I decided it was time for me to finally take guitar lessons. I had tried in the past to teach myself, but I couldn’t get past the beginner stage. So, when the opportunity arose to take guitar lessons through McGill’s mini courses I seized it and I was really looking forward to them. My instructor was Denis Chang, without a second-thought one of the most talented guitarists and gifted teachers I have ever seen. The man is the ideal teacher: he’s really experienced and knowledgeable, a master in his craft, supportive whenever you need him to be, extremely funny and quite the teaser. Besides, he has some of the coolest guitars I’ve seen. Going to his classes is a real joy. Lessons were held once a week for about two hours and initially there were around ten people registered for the course, but somehow he managed to give individual attention to each of us.

During the last three weeks, though, my coursework and the requirements of my research project didn’t allow much time for me to dedicate to my guitar. I had to skip my three last lessons, but I thought that most other students would attend. Today, which was the day of the last lesson, I decided to go meet Denis and tell him that he’s been a great teacher and he’s made me like the instrument much more. I discovered to my surprise (which is why I’m writing this post) that almost everyone in the class had been skipping the last lessons, just like me. I found Denis waiting for his students in the usual room where we practise (in the SSMU building) playing the piano and killing time. After feeling perplexed that I found none of my classmates there, I started feeling angry and disappointed. It was really depressing to see that one of the best teachers I’ve had was receiving this kind of treatment from his students — myself included, of course. He said that it’s OK, that it’s understandable because it’s the last week of classes and everyone is busy with course work, but that didn’t make me feel better at all. It didn’t seem fair to me that he wouldn’t receive an applause on the last lesson like all good teachers do.

I really like my coursework this semester, and my working hard for the moment is something that just feels right, because I’m doing it for myself and something that I enjoy doing. Yet, this was the first time since I’ve started at McGill that I’ve felt guilty about my efforts. I hope it’s the last. In the meantime, here’s what Denis can do:

My last computer vision assignment had a very cool component, so I thought I’d share it. We were supposed to implement Harris’ corner detector, which is a method for detecting corners in an image. By a “corner” we usually mean the point at which a pair of edges cross each other. For the purposes of this  method though, a corner is a pixel such that the intensities (of one of the RGB channels) within a small neighbourhood around it are significantly different than the intensities in the neighbourhood of a nearby pixel. A more detailed explanation of why the method works and how to implement it can be found here. These are the results of the algorithm, applied first to a simple image consisting of rectangles and then a real image (keep in mind that a threshold had to put on the number of corners marked on the image to avoid cluttering it):

Almost every Friday at 3pm there is a talk at McGill’s Computer Science department. Today was definitely one of the coolest ones: two members of the team that won the Netflix prize gave a talk on their machine learning techniques. Martin Chabbert and Martin Piotte, graduates of the Ecole Polytechnique de Montreal were members of BellKor Pragmatic Chaos that won the $1 million, 20 minutes before the deadline. Among the most interesting lessons in their fascinating talk, was the fact that at the end they had intelligently combined about 800 predictors using machine learning techniques and clever approximations. However, as they said, it was becoming evident towards the end of the competition that the only way to win, by hitting the mark of 10% improvement on Netflix’s movie recommendation algorithm, was to join forces with other teams, namely BellKor and BigChaos  — explains the weird team name. This meant sharing technical expertise, sharing predictors to be combined in ensemble classification, and of course sharing the money Here are the technical documents that explain how they did it: Pragmatic Theory, BigChaos, BellKor.

Yet another classification method used in machine learning. Here is the most accessible tutorial I found on this topic, by Tristan Fletcher at UCL. It might also be useful to see how you can use SVMs for regression (to predict continuous variables, instead of classes). This technical report, by Steve Gunn at U of Southampton, was the one that added the most intuition among the tutorials I found on SVMs, along with Geoff Hinton’s notes. And if you are interested in having a library that implements different SVMs then you might want to take a look at Shogun. It provides interfaces to Matlab, R, Octave and Python. It seems like a pretty neat library — at least from what I can see on its website.

Bagging and boosting are two methods introduced in machine learning that aim to combine different classifiers into one classifier that outperforms its components. AdaBoost seems to be the most widely used boosting algorithm, or at least the one profs seem to be more excited about. A very detailed description of how and why it works can be found here. However, I find Chris Bishop’s chapter 14 in Pattern Recognition and Machine Learning much more accessible if you haven’t seen this material before.

I have the feeling that the more algorithms I am introduced to in my machine learning class the less ways I know to solve problems, or at least, the less confident I am about which method is most appropriate. I guess that will come with time and experience, but still, I have to admit I have more respect now for statisticians.

Thankfully, Prof. Aaron Hertzmann’s notes for CSC411 at UofT are really helpful and accessible for people who visit the machine learning jungle for the first time. Maybe after some years I’ll become a machine learning Tarzan, but for the moment I have to watch out not to fall prey to next week’s ML midterm.

One of the lectures in my Machine Learning class briefly described the backpropagation algorithm used in neural networks. I wasn’t very satisfied with how the lecture notes described it, and there were many details I didn’t understand. Fortunately, this chapter from Raul Rojas’ Neural Networks: a Systematic Introduction does a much better and detailed job of describing the algorithm. Hope it helps!

That’s the title of a Facebook message that arrived at my inbox today. It was sent from the University of Toronto’s Student Union (UTSU) and it basically urged interested students to apply for a position for UofT’s student delegation that is going to attend the Copenhagen Climate Change Conference in December. The message included a link to UofT’s Environmental Resource Network which explained all the details about the application process. Extended application deadline:  October 5th (that is tomorrow!).

While I am not a UofT student any more, I couldn’t help but wonder how many students were notified of this opportunity in the beginning of September when they were choosing their courses. The convention takes place from December 5th to 18th, 2009,  which is exactly exam period for most north-american universities. If you read the application page, it mentions that students who wish to participate will probably have to ask their registrar’s office to defer their December exams and take them in February — a request that might or might not be satisfied.

This brings up some interesting questions: how many students are going to realistically be able to attend the conference and is the University willing to make it easier for them to attend? Will the university grant exam deferrals for this reason? As far as I know exam deferrals are granted for situations of medical (or other) emergencies, but I might be mistaken. What other support will this delegation need from the university?

And, since every time you ask for something you’d better have something to “bring to the table,” what role does the UofT delegation hope to play in the convention? Will they participate in peaceful demonstrations? Are they going to meet with delegations from other universities? Are they going to act as journalists, providing the latest news to the UofT community through blogging? Are they going to be given the opportunity to actually talk to any politicians? (I’m not referring to heads of states, of course, but perhaps to some of their representatives…) How many people does this delegation need to have in order to accomplish its goals?

I have no idea how things like this are organized, and how the voices of all these delegations are going to reach the ears of politicians, but I sincerely hope that they have some sort of an impact, and that everyone who’ll participate is going to be committed enough not to regard this trip solely as an opportunity for tourism. There are far better places to visit in December than Copenhagen.

PS: the Climate Thinkers Blog might be of interest.

What would happen if we took and pretended that we didn’t know where it’s origin was? One of the ramifications would be that points and vectors in that space would have to be considered different entities. When the origin is fixed and we know it any point in the space can be represented as the vector . This means that when we are working in an affine space (any point can be the origin), points are regarded as fixed locations in space and vectors are regarded as displacements without an origin — two different things.

Formally, an affine space consists of a vector space and a set of points such that:

• if then
• if and then

So, to specify an affine space we need a basis for (suppose it’s the image plane) and a point to act as the “unknown” origin. becomes the reference frame of the affine space. As usual, every vector in the affine space can be expressed as , while points are expressed as . In other words, vectors are of the form while points are of the form .

Does this remind you of anything? Yup, homogeneous coordinates. I believe this is why my lecture notes mentioned that “ is interpreted as a line (vector, horizon) when and as a point when .” It makes much more sense now then back when I first looked at that black magic of a sentence.

OK, so far so good. What really confuses me now, and confused some of my friends when they took the graphics course at UofT, is the question of why is it necessary to use affine spaces & homogeneous coordinates (and thus differentiate between points and vectors) in computer graphics? Why can’t we use our good old euclidean geometry? I believe the answer has to do with the types of transformations that euclidean geometry allows: only rigid-body transformations (i.e. identity, translations and rotations) are allowed and they preserve distances and angles.

Which classes of transformations are missing from that list and might be very useful in computer graphics? Linear transformations (e.g. scaling, reflection and shear), affine transformations (they preserve parallel lines) and projective transformations (artistic perspective). For instance, euclidean geometry says that two parallel lines never meet thus failing to describe perspective and the vanishing point on the horizon:

Projective geometry allows projective transformations such as the above. Euclidean geometry is a subset of affine and that in turn is a subset of projective, with respect to the classes of transformations each one includes. So, I presume that the answer to my question  is that in computer graphics people use projective geometry because it makes the end result much more realistic.

Some links to whet your appetite: #1, #2, #3, #4, #5, #6, #7

My first two lectures on computer graphics left me puzzled with some unanswered questions that have to do with basic projective geometry and its transformations. I’ll try to collect my thoughts and some links, and write them down primarily for the sake of summarizing to reduce my own confusion.

Basically, both in computer vision and in computer graphics the first geometric problem that we study is that of projecting points from a 3D scene to a 2D image plane (think of it as a photograph), using the pinhole camera model. The projection looks like this:

An important thing to notice on this picture is that any point that lies on one of the dotted lines will be projected to the same image location. This leads us to write for any nonzero , where is the euclidean coordinate system that we are accustomed to. This “equality” holds in the sense of equivalence classes, not in the sense of euclidean geometry.

Using a similar triangles argument we can prove that the pixel on the image is equal to . However, can also be viewed as part of the 3D scene like this provided that . The correspondence between image pixels and representatives of the equivalence classes of is one-to-one. The equivalence class corresponding to an image pixel is called the homogeneous coordinates of that pixel. Many of the articles that I found online assumed for the sake of simplicity and mentioned that the mapping is “just a trick” to be followed blindly because

What happens when ? In that case does not correspond to any point in the euclidean space, but to a unique point-at-infinity along the direction . The proof is in the first link.

Here are some of the links that might prove to be helpful for this topic: #1, #2