Bumblebee

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!

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

This week was my first week of classes at McGill and my second in Montreal. Being a grad student is quite enjoyable at the moment: I have more freedom in my course selection than when I was an undergrad, I get to explore the topics I’m studying in a greater depth than before, and generally the whole feeling of starting at McGill as a new student is quite exciting. Living independently in Montreal has its perks: a very vibrant and creative European-like city with a large student population, plenty of interesting activities to engage in and lots of opportunities to learn French. For now, I want to write about something other than Montreal, though, which I am sure is going to come up frequently in future posts.

My coursework for this semester, which I hope I have chosen so that it is neither too easy nor extremely time-demanding looks like this:

• Computer vision. While there is no required textbook, I think I am going to consult a couple of recommended ones, namely Introductory Techniques for 3D Computer Vision and Computer Vision: A Modern Approach

• Computer graphics. There is no required textbook in this course either. The OpenGL Programming Guide is a recommended one, and I suspect it’s going to be quite necessary for our assignments, but I think I should also consult Fundamentals of Computer Graphics and some online articles and tutorials because I feel that the lecture notes leave me with many questions.

• Machine learning. Pattern Recognition and Machine Learning is a classic and so seems to be Reinforcement Learning: An Introduction. This course has about seven assignments and a big final project that will include a report and an in-class presentation.

Needless to say that all of these courses require careful preparation and equal attention. I should also keep in mind that I’ll have to start reading a couple of papers each week to familiarize myself with the work that is being done at the Mobile Robotics Lab. I’m still not sure whether I should spend the rest of the time learning French or experimenting with something I haven’t tried before — I’ll just have to see how the following couple of weeks will be.

One of the few things I didn’t like at UofT’s computer science department was the lack of robotics courses in the undergraduate curriculum. This becomes all the more puzzling if you take into consideration the fact that UofT excels in teaching and researching artificial intelligence: computer vision, check, machine learning, double check, cognitive robotics, check, multi-agent systems, also check. It seems to me that the only thing missing is a couple of professors whose primary focus would be to create the necessary hardware that would provide a testbed for all those research efforts. Until that hardware becomes a reality though, some friends of mine and I thought that it would be a good idea to try out participating in RoboCup’s Simulation League.

RoboCup is a robotics competition whose aim is to promote artificial intelligence by creating robots, either actual moving hardware or just software-simulated agents, that will play soccer against each other. It’s (ambitious) goal is that by the year 2050 a team of humanoid robots will be able to beat the World Cup champions in soccer (say Brazil for instance), proving that the field of artificial intelligence has advanced to the point where machines can beat humans in an activity that requires elaborate motor skills, team strategy, and coordination. Personally, I find the fact that humans are striving to build machines that will beat them in a popular sport quite scary (and pointless) — I think Garry Kasparov won’t disagree. Nonetheless, until (and if) that happens, I believe that it is absolutely worthwhile to participate in RoboCup, simply because one can learn so much by the the engineering and artificial intelligence challenges involved in that effort.

Long story short, we convinced one of our professors, Steve Engels to supervise a fourth-year course whose topic would be the creation of a team for RoboCup’s Simulation League. About fifteen students were interested in taking this (summer) course, some of them for credit and others as volunteers. The students were split into four teams, each of which competes against the others every week. This way provides a way to set a benchmark by which to compare the progress of different teams. We used the official RoboCup soccer simulator and its incredibly detailed and helpful documentation. Fortunately, despite of the lack of previous experience of everyone who is involved, the course is going pretty well. See for example what one of the teams has been up to:

The bulletin board for the course is here and, admittedly, it doesn’t do the course much justice but I’ll do my best to make it a bit more informative. A lot of emails went back and forth discussing documentation, the pluses and minuses of available libraries for C++, Java and Python as well as other issues. Those notes will be very helpful for future teams who are considering the possibility of participating in the competition, so I’ll make sure to include them in the above board. As for the future of the course at UofT, it seems that it has attracted enough interest from students, so it will be continued, at least for another semester in a different format. Greg is working on it.

I decided to take CSC401, a course on statistical Natural Language Processing, this term at UofT, after listening to a lot of friends who were saying how fun this course is. I’ve heard things like this many times before: “Oh, you absolutely have to take that course on the ‘Evolution of Ancient Navajo Characters to Modern Navajo Characters‘, it is wicked!” and the result was a course that made watching  grass grow exciting by comparison. So, I took my friends’ (and profs’) suggestions with a grain of salt.

I am glad to say that everyone was right. This is probably one of the best courses I have ever taken in CS, even though I am not going to specialize in it. First of all, it deals with the one thing that Computer Scientists understand best of all: text. Of course, I have to admit that using Python in our assignments makes our tasks very approachable, because we can just think of them from a high-level perspective, instead of worrying about how to tokenize the text, use regular expressions, split strings, store data etc. These things would take a lot of time and effort in C, or in Java for that matter. Second, the assignments are empirical by nature, meaning that there is no right answer you can obtain by a formula, nor an algorithm that will solve your problems optimally. For instance, how can you detect sentence boundaries? “By a period” you say? You obviously haven’t been to St. James, and haven’t walked on Yonge St. See, you are dealing with many parameters that cannot possibly fit in your head, with many exceptions to the rules, and trial-and-error is the only approach that will make you choose some value over others. Apparently, this is how you develop experience in this field.

Speaking of our assignments, our first one is to train a decision tree from 500 articles, each 2000 words long, taken from the Brown corpus. The tree will classify unseen documents from the same corpus according to their literary genre (e.g. is it sci-fi, adventure, reportage, romance, humour?) It’s really cool, or at least it is much cooler than the  “Evolution of Ancient Navajo Characters to Modern Navajo Characters.” So, spread the word and tell your friends about CSC401. It/PRP ’s/VBZ worth/JJ it/PRP ./, even though POS-tagging is not perfect.

I am still alive; alive and feeling well. “When humans make plans, God laughs,” is a saying that can describe very well my life since September. After finishing an extremely satisfying summer, working with my friends and profs at the Department of Computer Science at UofT, I thought…no wait…I was sure that I was going to regain my focus to my classes. In a way, I was expecting that my third year here at UofT would simply be an improvement in terms of my academic efficiency over my previous couple of years. “Yes,” I thought, “this year I will be so focused that I’ll be able to manage my homework, get involved in extracurricular activities and go out to have fun with my friends,” assuming that nothing extremely unusual will happen to me.

Thankfully, I was wrong. I met a lot of new friends, most of them Albanians, who welcomed me to their group. Meeting other people from Albania is always fun, because there are so few of us and yet we have spread in almost every corner of the world (although, I still haven’t heard of any Albanians living in the Arctic, but who knows) . Our language and common background unites us immediately, even if our families are not related, and even our hometowns are far apart.

A s far as courses are concerned, I have realized that the more high-level Math courses I take, the less they relate to any aspect of Computer Science and the less they seem helpful to anything I do outside the classroom, even if it is technical. Take Group Theory for example: we study groups (sets together with an addition-like operation), rings (sets together with an addition and a multiplication-like operation) and fields (sets together with basic operations, just like the ones you’ve been almost unconsciously using since grade 1). Of course, the material is not that easy because otherwise I wouldn’t be complaining about it. There are literally hundreds of theorems that you have to be familiar with, few of which are applicable to a wide collection of problems. Unfortunately, there are few standard methods that you can use to solve problems, as opposed to first-year Calculus, where you had a “standard” arsenal of techniques that could solve 90% of your problems — I mean math ones. In Group Theory it seems to me so far, after 1.5 semesters in this year-long course, I haven’t used the same technique in more than one problem — it’s fascinating, the complete opposite of what I think of the material.

And then of course, there is Real Analysis. I frequently think that the very reason I decided to study Math together with CS was Analysis. But taking this course is really testing my will. We have been studying convergence of sequences of functions and then measurability and Lebesgue integration. Again, I have to admit: this material is extremely interesting, but there is an asterisk at the end of that phrase saying “if you want to be a mathematician,” written in tiny font.

That’s what the people who design programs of study that combine a major in X with Math have got wrong, in my opinion. Including these courses in programs of study for non-mathematicians does indeed guarantee that their preparation in math is solid, but it does not attempt at all to teach math skills that might be somewhat applicable to discipline X. For instance, if Johnny is doing a double specialist in Comp Sci and Math then why not teach Johnny material that might help him in his main course of study, say Combinatorics or Graph Theory or Linear Programming & Network Flows, or Discrete Math, or Number Theory or something that will be more than just another course to him. Because when Johnny decided to include math in his studies, I’m sure he didn’t do it just for the “coolness” of it, or just because math is “generally interesting and useful.” No! It has to be interesting and useful to Johnny, by supplementing his studies in CS with a more theoretical preparation.

So, after three years the time to decide which rabbit to chase finally came, and I chose Comp Sci, simply because at this point, even a Hello World program seems more creative and practical and constructive than studying material whose homework requirements outweigh its benefits by miles. Don’t worry though, I haven’t become soft and whiny yet; I can still handle hard times. The fact that I haven’t changed my program of studies and I am still trying proves that. Nevertheless, the requirements of these courses are starting to become scary –maybe it’s time to hug my mom. Yes, that will fix everything, for sure.