Google Summer of Code Acceptance

A few days ago, I was delighted, and somewhat relieved to find out that my proposal to the Google Summer of Code 2011 program was accepted. Since 2005, each summer, Google funds undergraduates, masters and PhD students from all over the world to develop open source software. To apply, one needs to find an open source organization of his/her interest, find a suitable problem, and submit a proposal detailing the project to Google.

You can see my proposal here.

Apache Software Foundation is a well known body in the field of open source. As a matter of fact, the Apache Web Server was one of the first adopters of the Open Source Software license in late 90's. Since then, ASF has spawned a number of sub projects, and Mahout is one of them.

Apache Mahout is a highly scalable machine learning library written in Java. Mahout's aim is to provide users with easy to use data mining and machine learning tools capable of handling extremely large data sets, with a commercially friendly license. Anyone can download and use the library for free and use it for business, academic research or educational purposes.

I have proposed to extend one of Mahout's existing programs, called the Baum-Welch Hidden Markov Model Trainer (BW) so that it can be simultaneously run on any number of computers connected to each other on a network. This is important because the program in its current state can only handle as much data as can be fit on one computer. The trainer performs best when it is give a lot of data. One of the ways to handle a large data set is to divide it into smaller pieces, distribute the splits to a bunch of machines and have each machine run the same program on its share of data.

The BW trainer has a lot of applications in places where we have to predict something by looking at data which may not present the complete picture of the underlying process. For example, handwriting recognition. Here, the challenge is that people may scribble "A" in almost infinite ways and one has to develop a program which can predict that the letter was indeed A, by accounting for all the variability in human handwriting. Similarly in speech recognition, the BW is used to predict what the speaker said which can be then be printed, emailed or stored. One can extend these simple applications to more exotic cases, for instance finding out the parts-of-speech of a sentence and using that information to translate from one language to another. BW is also extremely widely used to analyze DNA and protein sequences to discover genes.

One must feed the BW some initial data using which it "learns" the nature of the problem, and then one can apply the "learned" model to predict. The prediction accuracy of BW improves if it is given more data to train, hence my motivation to improve the existing Mahout's code which as of now can only handle limited data.

The challenge for me was to find out a way to "break" the sequential nature of the BW and show that it could be made to run in parallel. I was not too concerned with the programming aspect of the project which although being non-trivial, presents less of a problem because I code for a living each day at UMass. However, investigating whether a sequential algorithm invented in 1950's could be made to fit on a particular parallel computation scheme (Map Reduce) was much more challenging because of its fundamental, mathematical nature. I wanted to be absolutely sure that the algorithm could indeed be made parallel before proposing the project. Since I had started early, around mid February, I had some time to think and research about the problem more. It took me almost one and half months of brainstorming to figure it out. During this process, I read a lot of research papers on machine learning, probability, statistics and parallel computation. At the end of it all, I was pretty confident of the feasibility of the project and knew that the BW could be made to handle data in chunks and still arrive at the same result. The final proof came just a few days before I formally proposed the project when I discovered this excellent book which contained a technique similar to what I was thinking.

Soon after I submitted the project proposal, I was interviewed telephonically by Grant Ingersoll which went great. I will be mentored by Grant for the project who incidentally, is an alum of the Amherst College.

So excited, I'm all set for a Summer of Code!

Of gym rats and fit men

I'm not being sexist, I could have easily called this post 'Of gym rats and fit women'. This would certainly be true, because I see extremely fit women everyday at my local CrossFit where highly motivated students, policemen, firefighters and general people train, sweat and redefine exercise intensity. However, Of Mice and Men is too good of a work for me to not connect with my title.

If you don't already know, CrossFit is a training philosophy aimed at making you fitter. Now devising a scheme to fit everyone's fitness needs is a pretty ambitious goal because clearly one training regime would not work for everyone, you would think. In a way this is true, but also untrue and I'll explain why. If you are not a highly specialized athlete, then in all likelihood, you would not want to narrow down to a training regime which only improves a few areas of your fitness. Let's say you are a powerlifter, and your only interest is in lifting as much weight as you can in 3 lifts (bench press, deadlift, squat). Obviously, the overall fitness goals for you would lay much more emphasis on increasing the absolute, raw strength rather than reducing the 100m sprint time. Similarly for the 100m sprinter, the amount of weight lifted in the 3 powerlifts is of a lesser concern (if any).

Let's look at it in a different way. Although academics and fitness are two entirely different things, I'll try to draw an analogy. In a typical undergraduate degree, the emphasis is largely on generalization- you're expected to know most of the fundamentals and obtain skills in a variety of areas. Armed with a solid foundation of the undergrad degree, you could pursue a Masters, Phd and a Post Doctorate, aiming for more and more specialization. CrossFit is more akin to the undergrad degree in fitness from a top ranked school. Very rigorous, very demanding but immensely rewarding. The fruits of this degree could be used just as is, or to specialize further in different sports. Just as no undergrad program will promise a high degree of specialization, CrossFit deliberately avoids converting someone into either a runner, strength athlete or a gymnast. However, it tries to achieve a combination of all the aforementioned abilities, and this works for 99.99% of the general population barring a few highly specialized athletes who train differently. However, the net result is fantastic. The training program is so rigorous that it has the potential to permanently transform you from a couch potato to a person with high degree of strength, explosiveness and endurance (Are these not the basic qualities of an 'Athlete'?)

The definition of fitness is itself very vague. In societies where protein deficiency is not an issue, a big beefy muscular individual could be considered very fit (I could be wrong here). However, in third world nations a totally different stereotype exists. I remember very vividly while growing up in India how doing a split was the fastest way to earn peer recognition. Another sure shot way was to be able to finish 20 pull ups. Clearly, there is no universally accepted definition of fitness. One can find a super strong powerlifter unable to perform the split, and one can find a champion splitter unable to put even 100 pounds over his head. So how can one reach a good definition of fitness?

I battled with this for a long time myself, much before I began CrossFitting. I knew instinctively that bodybuilders with big muscles were not the fittest, but I really struggled to rank Olympic weightlifters, sprinters, marathon runners, gymnasts, boxers, karate/MMA fighters, swimmers in their order of fitness. Turns out, this is almost an impossible thing to do. If you look at my list again, all of the mentioned activities are sport specific. Sure, a gymnast can fly though the air, rotate 3 times before landing on one foot and propelling to do the same thing 5 times again, but can he/she outrun a high school level 100m sprinter? Does this mean that the gymnast is less fit than the sprinter or does this mean that the gymnast is better at controlling his/her body than the sprinter? As it turns out in the same vein, comparing a weightlifter to a swimmer is like comparing apples to oranges. Both have their purposes, their challenges and their fitness needs, but they are different.

A good definition for fitness can still be achieved by combining the major sports and finding the basic skills required in each of them. This would effectively form the curriculum of our 'undergraduate program of fitness'. This is precisely what CrossFit has done - it combines aspects of gymnastics, olympic weightlifting and sprinting to create constantly changing workouts. The creator of CrossFit, Greg Glassman defines fitness as a combination of 10 sub skills - cardiovascular/respiratory endurance, stamina, strength, flexibility, power, speed, agility, balance, coordination, and accuracy. To avoid narrowing down to any one aspect of fitness, the workouts are constantly changed. This has the added benefit that training is fun, unexpected and yields quick results. There are other very interesting aspects of this training program as well, most of them rooted in solid human physiology research. For instance, research has proved that high intensity training for a short time can outweigh endurance gains achieved through long duration moderate intensity training. Most of the workouts are thus designed for 20 minutes or lesser duration.

The results? I joined CrossFit in Jan 2010, I have lost 20 lbs and around 4" in the waist. I feel a lot faster, more agile and stronger. I could not do a single a pull up on the first day, but now I can do 10 advanced kipping style pull ups. My numbers in core lifts have increased. I can deadlift 310 lbs, squat 270lbs and press 110 lbs. I'm on the way to learning better form in the highly technical Snatch and Clean and Jerk Olympic lifts and also shaving off numbers from sprint rows and 400m runs. These results are after the fact that I had been doing strength training on and off for 3 years, and have some background in sports (Cricket and Field Hockey), clearly precluding the lightning fast results which beginners usually achieve when put on a strength program.

In short, I feel fitter.

I must warn though, if you're aspiring to be on the next season of the Jersey Shore, then CrossFit is not for you. Traditional gyms with high volume, low intensity, sacroplasmic hypertrophy oriented workouts, fueled with steroids around a bunch of vane buffoons are your best bet.

Oh, and throw in a Nautilus as well.

Chess Fundamentals

I've been reading this book and it has helped to improve my understanding of chess considerably:




I consider myself at an advanced beginner stage where I understand some tactics, and I'm yet to refine strategic play. While looking for new books on chess, I felt that most of them did not answer the fundamental question of 'why this move was made and not that'. It is easy to get lost in the jargon (hypermodern, Reiti opening, Najdorf defense and so on) but it helps at least initially to focus on a few basic principles and get a book which can show you their application. John Nunn is a British grandmaster and he analyzes grandmaster level games in this book. It is very up to date, and reflects the advancements made in chess theory during the last century.

Highly recommended for someone who is looking to advance his chess strategy.

Good stuff in Windows 7

I had a sort of 'wow' moment yesterday at work regarding Windows 7.

Yes.

I should be honest, the fancy user interface and other 'look and feel' embellishments of Operating Systems seldom interest me. I'm not saying that they are unimpressive or easy to accomplish, but just that I'm more easily seduced by innovations in core technology or functional aspects of the program. For instance, I disabled Aero on Vista and similarly, the fancy Compiz on Ubuntu. It is fun to play around for a little bit, but really, I don't need rotating workspace-cubes when all I'm doing is entering C or C#/ASP.NET in an editor.

So Windows 7 was pretty to look at when it arrived at work. It was fast, but is not every new system fast? My coworker and I were playing around with a Logitech webcam yesterday and we decided to hook it up to the Win 7 box. As usual, the NT Kernel recognized the USB webcam as a Human Interface Device. I assumed it would proceed and ask me about the driver disk, but to my pleasant surprise, it went online and downloaded automatically not just the driver, but also the utility software. Best of all, it worked! I was able to use Skype, indulge in narcissistic facial gestures, and admire myself on the screen.

I personally have a bad feeling when NT based OSes search the web to find 'solutions'. How many times has Windows tried to match the file's extension with a program by going online when it does not understand the launching application for an unknown file extension? How many times has it failed to deliver anything useful out of the process?

However, with the Logitech webcam, it all came together just fine.

My boss later said that his Win 7 box did the same thing when he hooked up his new Canon digital camera.

I must say I'm pretty impressed by this feat, and I will not cringe when Win 7 goes online to find solutions.

A super long palindrome

Originally written on July 19, 2009

----------
I came across an interesting programming problem to generate Palindromes while reading a book on the good old C programming language.

If you don't already know, a palindrome is a phrase/word/sentence which reads the same backwards and forwards. Eg:

"A man, a plan, a canal - Panama" (Ignore the case and punctuation etc, focus on the letters).

The above palindrome is a classic, it shows the effort in building the Panama canal. Jim Saxe, a Computer Science grad student at CMU in 1983 extended this to the following:

"A man, a plan, a cat, a canal -Panama?"

Bragging by putting it up on his system for others to see it, he was soon parodied by someone from Yale:

"A tool, a fool, a pool—loopaloofaloota!"

Nonetheless, someone else soon extended the Jim's palindrome to:

"A man, a plan, a cat, a ham, a yak, a yam, a hat, a canal—Panama!"

This started a race to discover longer palindromes, which made sense to the ear. (It is pretty easy to come up with a program to generate meaningless palindromes)

Dan Hoey who had then recently graduated from CMU saw the palindrome obsession and tried to develop an ingenious program in C to generate one. His idea was to successively add letters on either side of the middle of the original Panama palindrome, the left image a reverse of the right one. In his resulting program, a finite state machine successively evaluated partial palindromes and added them to the original sentence. He used a small word list containing only nouns so that the resulting palindrome made some sense.

The program generated the following:

A man, a plan, a caret, a ban, a myriad, a sum, a lac, a liar, a hoop, a pint, a catalpa, a gas, an oil, a bird, a yell, a vat, a caw, a pax, a wag, a tax, a nay, a ram, a cap, a yam, a gay, a tsar, a wall, a car, a luger, a ward, a bin, a woman, a vassal, a wolf, a tuna, a nit, a pall, a fret, a watt, a bay, a daub, a tan, a cab, a datum, a gall, a hat, a fag, a zap, a say, a jaw, a lay, a wet, a gallop, a tug, a trot, a trap, a tram, a torr, a caper, a top, a tonk, a toll, a ball, a fair, a sax, a minim, a tenor, a bass, a passer, a capital, a rut, an amen, a ted, a cabal, a tang, a sun, an ass, a maw, a sag, a jam, a dam, a sub, a salt, an axon, a sail, an ad, a wadi, a radian, a room, a rood, a rip, a tad, a pariah, a revel, a reel, a reed, a pool, a plug, a pin, a peek, a parabola, a dog, a pat, a cud, a nu, a fan, a pal, a rum, a nod, an eta, a lag, an eel, a batik, a mug, a mot, a nap, a maxim, a mood, a leek, a grub, a gob, a gel, a drab, a citadel, a total, a cedar, a tap, a gag, a rat, a manor, a bar, a gal, a cola, a pap, a yaw, a tab, a raj, a gab, a nag, a pagan, a bag, a jar, a bat, a way, a papa, a local, a gar, a baron, a mat, a rag, a gap, a tar, a decal, a tot, a led, a tic, a bard, a leg, a bog, a burg, a keel, a doom, a mix, a map, an atom, a gum, a kit, a baleen, a gala, a ten, a don, a mural, a pan, a faun, a ducat, a pagoda, a lob, a rap, a keep, a nip, a gulp, a loop, a deer, a leer, a lever, a hair, a pad, a tapir, a door, a moor, an aid, a raid, a wad, an alias, an ox, an atlas, a bus, a madam, a jag, a saw, a mass, an anus, a gnat, a lab, a cadet, an em, a natural, a tip, a caress, a pass, a baronet, a minimax, a sari, a fall, a ballot, a knot, a pot, a rep, a carrot, a mart, a part, a tort, a gut, a poll, a gateway, a law, a jay, a sap, a zag, a fat, a hall, a gamut, a dab, a can, a tabu, a day, a batt, a waterfall, a patina, a nut, a flow, a lass, a van, a mow, a nib, a draw, a regular, a call, a war, a stay, a gam, a yap, a cam, a ray, an ax, a tag, a wax, a paw, a cat, a valley, a drib, a lion, a saga, a plat, a catnip, a pooh, a rail, a calamus, a dairyman, a bater, a canal—Panama.

The challenge given by the book is to use a real online noun list containing far more nouns and come up with a 10,000 word long palindrome.

Simple?

A geeky Christmas afternoon, and the perfect woman.

Originally written on Dec 25, 2008

----------

What does an international grad student in Electrical and Computer Engineering do on a Christmas afternoon in Amherst ? Explore Youtube.com, and waste the precious interweb's bandwidth.
Youtube.com is a hungry data-beast, it consumes and grows on flash videos, much like a caterpillar feeding on plants and insects. It is so huge, that it uses as much traffic as the web had in the year 2000. But not without a good reason - Youtube is democratic, fast, legal for the most part so RIAA can keep it in their pants, and devoid of porn.
Youtube made me feel more democratic. Searching for alternatives to the software tyrant of our days - Microsoft, I quickly navigated to Google labs - where the next generation cutting edge software is featured, all of it free, and some of it open for code inspection. That is where I found this geeky blog:

http://www.codinghorror.com/blog/

This gentleman ordered a pair of bare-bone computer servers, as his Christmas present. The servers are inoperable in their packaged state, and his endeavor is to make them functional by mounting hard drives and more memory. How could I not bookmark this page ? He wrote something about Uncanny Valley, which I was not aware of.
Uncanny Valley is in relation to a paradox : humans disdain technology as it creates more life like products. It is creepy to think of a robot resembling your previous crush, although it will be indeed a marvel of technology. The robot shown here on Youtube can play a Violin, although does not (and I hope not) look like your ex:



I appreciated the hot Japanese actroids , and was thinking of asking one out and buying them some system memory as a gift:



However, the Uncanny Valley syndrome quickly stirred up my senses when I found this:



Much like the Internet-mail-order wives, you can purchase this 'perfect woman' actroid from their website. Although lacking in sophistication than other robots (Asimo), the idea cracked me up - and angered me a little bit later. I hate chauvinism: Male, Female, Hindu, White - anything. And these folks are spearheading a campaign, marketing brilliant technological innovations by catering to the lowest psyche of males. I am waiting for the day when feminist groups can release their version of the perfect man actroid, which will be as distasteful as the perfect woman developed by these loonies.

2001: A Space Odyssey

Originally written on March 28, 2008

-----------

I recently saw 2001: A Space Odyssey for the third time on Netflix.com, and it left me more awed, more inspired and more perplexed by the cinematic genius of Stanley Kubrick. It is surprising how Kubrick can make excellent movies in diverse genres such as comedy (Dr Strangelove), relationships (Eyes Wide Shut), war (A Full Metal Jacket), infatuation (Lolita), horror (The Shining) and the all encompassing masterpiece `A Clockwork Orange'. 2001 can be dubbed as a science fiction/suspense movie. This motion picture creates a breathtaking imagery of space by using special effects and classical music. There are few dialogues and they do complete justice to the grand topics of human evolution, artificial intelligence and space exploration which this movie tries to address within its span of 148 minutes. After you finish it, you may find yourself guessing what happened and possibly engaging with your friends in `one of those' conversations about its meaning. Whatever you reason, your hypotheses will be debatable at best. The answers lie inside Arthur C Clarke's novel by the same name. Arthur Clarke assisted Kubrick with the screenplay.
This film was made in 1968 and was extremely ahead of its time, and holds its ground even today. The graphics used to create the colossal inter planetary spacecraft are very good and the sets do not appear lame. The music compliments the scenes at all times. The distinct opening theme composed by Richard Strauss has become a favorite of our times and can be commonly heard elsewhere. Kubrick uses music very smartly and does not swamp the viewer in long sequences which would have added little to the whole experience. For instance, the scenes where astronauts are engaging in EVA are devoid of any background score and you can only hear the breathing, taking you right inside the space suit.
I do not want to spoil the movie for people who have not watched it yet, but 2001 raises very pertinent philosophical questions about AI and the possibility of computer consciousness. We have seen a lot of movies of late in which some damned robot decides to overthrow humans ensuing some lame ass drama. HAL 9000 computer from 2001 however presents itself to be a less fancy but a very credible system which goes awry. The treatment of this serious issue is non glamorous and very straightforward.
If you have not seen it yet, please watch it. Although it will appeal more computer sc/ engineering majors, I think everyone who has a penchant for movies should be able to enjoy it.

Here is the trailer on Youtube: