ALT 2011

Earlier this month, I traveled to Finland, where I attended ALT 2011 and presented a paper on learning sparse parity functions in the presence of noise. 

a picture I took in Helsinki

COLT (Conference on Learning Theory) and ALT (Algorithmic Learning Theory) are the two main learning theory conferences.  Though COLT is both the larger and better known of the two, it seems that ALT is growing stronger with every passing year, and this year was no exception.  Not only was the program good, but Sébastien Bubeck gave a timely tutorial on bandits, which deservedly got their own session this year. (I, unfortunately, arrived too late to see the tutorial, but I read the nice slides afterwards.)

I wouldn't be the first to note that the other thing that differentiates ALT from its big brother is that ALT seems to have a broader definition of learning theory, and the conference is therefore more diverse in its topics than a typical COLT.  This has clear benefits, but it also means that there are entire sessions where I am pretty lost.  Of course, as I've previously noted, not feeling like you have to following everything could also be a benefit when you're attending a conference.

I want to mention one paper I particularly enjoyed, especially because of the model, which illustrates the importance of unlabeled data in the agnostic setting:

"Learning a Classifier when the Labeling is Known" by Shai Ben-David and Shalev Ben-David.  This paper works in an agnostic learning model where the learner already knows the labeling function, but wants to find a good succinct representation (i.e. proper learning).  How good a particular representation is depends on the distribution the data is coming from, and this is what the algorithm needs to learn by seeing examples.  It turns out that this, more generous, model is subject to essentially the same sample complexity lower bound as the common agnostic PAC model.

Happenings on CSTheory Q&A

In addition to machine learning, one of my main research interests is theoretical computer science.  Following the success of MathOverflow and other Q&A sites, cstheory.stackexchange.com ("cstheory" for short) was born about a year ago, and I've been an active participant since its inception.  In the last year, we've worked hard to make cstheory a valuable resource and to promote it.  I'd say the efforts paid off -- the site is doing quite well, with over 5000 members.

Moreover, cstheory recently added a blog (Aaron Sterling and Joe Fitzsimons are editors), whose posts are on topics related to theoretical computer science and to the site itself.  In one of the first posts, Suresh Venkatasubramanian, a site moderator and one of the people most responsible for its success, wrote a nice summary of cstheory's first year.

I've also volunteered to occasionally blog about the learning theory side of things.  My first entry, on learning regular languages, was just posted.  It touches on many interesting issues learning theorists regularly encounter. Enjoy!

Reyzin-Srivastava Trees

When I was a grad student at Yale, Ravi Kannan taught a great sequence of graduate theory courses on approximation algorithms, randomized algorithms, and streaming algorithms, and I was lucky enough to get to take all three.  The first one, approximation algorithms, Ravi taught during my first semester in grad school.  We were allowed to collaborate on assignments, and I discussed many of them with my friend Nikhil Srivastava.

I remember a problem on one of the first assignments was particularly tricky.  The question was about s-t cuts in a graph.  The hard part about this problem was that to solve it, it seemed we needed to efficiently keep track of all pairs minimum s-t cuts.  We started discussing the problem in the afternoon, and though it took us a while, by about 5am we had designed a data structure to do just that.  We realized you can maintain all the cuts in just one tree.  It was perfect.  We jokingly called the data structure the Reyzin-Srivastava tree.

I spent the remainder of the night writing up the assignment, describing this thing in detail, proud of our cleverness.  About a week later, we got the graded assignments back.  Mine had one note on it, next to that particular question of course.  It said "Next time, just reference Gomory-Hu trees when you need to use them."

I learned a couple lessons from this.  The first is that I should remember to do the required reading before starting the assignment (we used Vijay Vazirani's approximation algorithms textbook, which really is worth reading).  Had I done the reading, I would have learned about Gomory-Hu trees and realized the question asked us to trivially apply them to some problem, instead of reinventing them.   The second, and perhaps, more important lesson was that I had a shot at doing research, at inventing something new.  Yes, these trees had been invented decades before, and yes, we'd been exposed to more data structures than Gomory and Hu had been in 1961.  But somehow knowing that we figured out something on our own that wasn't trivial really helped our confidence as first year grad students, and as I've written before, confidence is quite important for research.

Nikhil and I went on to do some real research together, producing two joint papers the following year.  Actually, both of those papers also began as classwork, for Dana Angluin's machine learning class.  But that's a story better left for another post.

On ICML 2011

I've heard from some people that they liked my summary of NIPS 2010, so I'm posting my thoughts on ICML 2011, where I went a couple weeks ago.  ICML is one of the two main yearly conferences in machine learning, so there are always interesting new results to see, and this year saw a record of over 700 attendees.  Unfortunately, I didn't get to attend the tutorials or the workshops, so my post is about the main conference.  The conference took place in Bellevue, a city near Seattle, Washington.

Bellevue downtown at night, from Wikipedia

Invited Talks

One of the main highlights of ICML 2011 were the invited talks.  Usually, I like one invited talk or so, but this time all of them were great.   I've heard a number of people remark that the organizers did a great job of choosing the speakers.  I should also note that the videos of all the talks, invited and not, will soon appear on TechTalks, and I recommend you watch the invited talks especially.

The first talk was by Chris Bishop, of the Microsoft Research (MSR) Cambridge, UK lab, who talked about applied machine learning coming of age.  He addressed a variety of topics, perhaps a bit loosely tied together, but the real highlight of his talk was the first half-hour, where he addressed the technology behind Kinect.  Apparently, much of the technology behind it was developed at MSR (this should be good for research funding at Microsoft, as Kinect was a huge commercial success), and he went into some depth about both the machine learning and hardware challenges in building Kinect. For example, machine learning was used for the body tracking system in Kinect, but with some interesting twists, e.g. 1) the body tracking problem isn't treated as a tracking problem at all: each individual frame is independently classified, 2) lots of the training data is synthetic.  On the hardware end, I learned that Kinect could track you just fine in the dark.  To find out more, you should watch the entire talk.

Kinect sensor, image from Wikipedia

The second invited talk was by a mathematical biologist, Martin Nowak, who talked about the evolutionary dynamics of competition and cooperation.  He talked about all sorts of interesting things.  What stuck with me the most were some results he presented on the repeated prisoner's dilemma.  In the famous classic prisoner's dilemma, each of two prisoners must independently decide whether to cooperate or defect (see figure below for a possible payoff matrix).  The dominant strategy for both prisoners is to defect, but if both prisoners cooperate they are better off than both defecting, hence the dilemma.  In the real world, we often play variants of this game, but over and over again.  The repeated prisoners dilemma setting captures this aspect of repeated play, and a while ago, Robert Axelrod held a famous repeated prisoners dilemma tournament where he showed tit-for-tat was a really good strategy: basically, to cooperate at first and then, on each future round, to do what your opponent did on the previous one.  I have a lot more to say on this topic, but I'll skip to Martin's talk.  Martin presented some interesting results where he showed us that if noise is introduced into this repeated game (like in real life), and one runs an evolutionary tournament that starts with random strategies, first tit-for-tat will evolve.  But then, tit-for-tat will be taken over by a more forgiving versions tit-for-tat, which will subsequently be dominated by completely cooperative strategies, which will be exploited by completely defecting strategies, which will then be taken over by tit-for-tats again.  And this cycle repeats!  Martin pessimistically suggested this this cycle is inevitable in the real world as well.  Of course, his talk had a lot more, so if you want to know the details of this and more, I recommend you watch it!

possible prisoner's dilemma payoff matrix, image from "beyond intractability"

Then, Hatmut Neven, of Google talked about the machine learning behind "Google Goggles," the reverse-image search where you take a picture of an object, send it to Google as a query, and Google will hopefully return some relevant results.  I hadn't thought much about this reverse-search problem, so a lot of the talk was interesting to me on a basic level.  For example, if you send a picture of a fancy chair, it's useless for Google to tell you it's a chair, you're probably looking to know what type of chair it is so you can buy it -- this makes the problem very hard.  But it doesn't mean Hatmut and his team haven't made a scary amount of progress: Hatmut says that Google can, given a picture of an arbitrary person who has about a dozen photos of them in Google's databases (i.e. online), correctly classify them in the top ten results.  Google hasn't activated this feature for privacy reasons, but if (or when?) Google does, this means that you could pretty much see someone on the street, take a picture of them, and find out who they are (and they don't even have to be a famous actress).  Hatmut thinks that in 10 years, we'll be able to carry a camera with us, which will, without any special querying, know more about the world around us than we do -- it will know what species of trees are around us, the origin of the name of the street we are on, the history of the author of the book we're reading, etc. Exciting stuff.  Finally, Hatmut talked about how quantum computing might help with all this, and he gave a much more positive endorsement of D-Wave than I'd read elsewhere.

D-Wave's 128-bit chip, image from Wikipedia

The last talk was by David Ferrucci about the IBM Watson system that beat the top two humans on Jeopardy (see my post on Watson).  He talked about the immense challenge of building Watson, the collaboration among many different types of researchers, the scientific problems involved, and the various problems his team had to overcome.  The task of building Watson was so monumental that many (non computer scientist) people couldn't get their heads around it.  David described an incident when he went on a radio show to talk about Watson and was asked by the radio host "So, you're going to give the computer all the questions and answers, and when a question is asked, the computer will pull up the right answer?"  David said, surely rolling his eyes, "No. We don't know any of the answers in advance, let alone the questions."  Then the radio show host responded "I don't understand. How are you going to do it then?" "Exactly!" said David.  I trust I'm not spoiling anything if I tell you machine learning was a big part of the solution.

Watson's avatar, image from Wikipedia

Neural Networks 

John Langford (who hosted my postdoc at Yahoo! Research) already blogged that neural networks were making a comeback, so to speak, at ICML 2011.  In addition to the sheer number of "deep learning" papers, lots of people excitedly talked about what great things they could train their neural nets to do.  I would add to John's post, after talking to Bill and Ilya, that another reason this area is becoming "hot" is that we finally have the computing power to train neural networks for real-world problems, something that was previously much more difficult.

I must admit that I don't know enough about neural networks, and the reason is that it's not easy to see how the fit into the larger world from a learning theory perspective.  For example, we know that a single-layer neural network cannot learn even the XOR function, that recurrent neural nets can simulate Turing Machines, and that certain classes of neural nets are not properly PAC learnable.  But from what I can see, the theory of neural nets is of a very different flavor than, say, the theory of decision trees.  If someone who knows these connections better wrote up a survey, I'm sure I'm not the only one who would be grateful. (Even better, maybe such a survey exists and I'm not aware of it.)

Papers I Liked

Given that ICML has 4 or 5 parallel tracks, I didn't get to see even 20% of the talks, but I tried to catch what I could at the poster sessions.  Here are a few non neural-networks (for the neural networks ones, see John's post) papers I liked, besides my own, of course.

"On the Necessity of Irrelevant Variables" by David Helmbold and Phil Long.  The main gist of this paper is that irrelevant variables don't hurt a predictor nearly as much as relevant variables help.  So if you're trying to do feature selection and aren't sure whether to add a feature or not, add it.

"Clustering Partially Observed Graphs via Covex Optimization" by Ali Jalali, Yudong Chen, Sujay Sanghavi, and Huan Xu.  Here, they do correlation clustering with partial observations, which is NP-Hard, so instead of the usual approach of making an approximation algorithm, they give an algorithm which succeeds of the data satisfies certain properties.  They're not the first to do this type of analysis, but I rather liked their type of data-dependent assumption.

"Optimal Distributed Online Prediction" by Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao.  This paper considers online prediction, but in a distributed model, where one can get speedups, possibly at some cost in the regret.  They derive optimal regret bounds for convex losses and i.i.d. examples, and show that for many parameter settings,  you can actually get the same asymptotic regret as without parallelizing.

"Doubly Robust Policy Evaluation and Learning" by Miroslav Dudik, John Langford, and Lihong Li.  I'm a bit biased about this paper because I was at Yahoo! when they were woking on it. They basically show a technique for evaluating a new bandit policy on historical data, where you can get an unbiased evaluation as long as you have either a good model of rewards or a good model of the past policy. Hence, doubly robust.

Overall

ICML 2011 was great.  I'm looking forward to ICML 2012! One extra bonus is that ICML 2012 will be co-located in Edinburgh with COLT 2012, the main learning theory conference.

Update (7/26/11): Videos of all the talks from ICML 2011 have now been posted here.

If you're interested in machine learning, you should follow John Langford's blog, hunch.net.  Also, John will co-chair ICML 2012.

Three Tweets

It is well-known that it's not always easy to explain scientific ideas to the public.  Scientists are often blamed for being bad communicators, but I don't think that's fair.  Most people simply aren't interested enough to read detailed explanations of science (or of anything for that matter).  And scientists are hesitant to give oversimplified explanations because, among other reasons, oversimplified explanations are by definition not correct.  The problem surely exists in all sorts of disciplines, but is probably exacerbated in the sciences/math, where one often needs years of postgraduate study to truly grasp what's going on.

Sometimes, though, it doesn't hurt to give simplified explanations of complicated phenomena.  Our universe is a cool and interesting place, and making some of what we've learned accessible to more people isn't a bad idea.  Maybe it will make more people excited about science and help with funding in the long run.  It's also fun to try to explain what you're doing to others, even if it's on a high level.

Unfortunately, there's still temptation for scientists to go into too much detail.  We can't help ourselves but to bore everyone around us.  This is where twitter comes to the rescue.  Its 140 character limit forces us to be concise, so if we're going to talk about science at all, we have to choose our words carefully.  So, when Sean Carroll, a physicist at CalTech, entertained a request to explain M-theory on twitter, and attempted to do it using only 3 tweets, he opened a floodgate of other scientists trying to explain the major ideas in their fields in just 3 tweets.  Check out the #3tweets hashtag, and you'll see all sorts of interesting things posted.

Sticking to three tweets strikes a balance between a blog post (which won't get a large readership) and just 1 tweet (in which one cannot explain anything).  And if you have followers who are reading your twitter stream, they won't be able to avoid reading some science.

I, too, got tempted and did my own three tweets on the Church-Turing thesis (to be read bottom-up):

If you have a twitter account (and if you don't, get one), try explaining something about what you do, whether it's science or not, in just three tweets (and don't forget to use the #3tweets hashtag).  It's harder than it seems.

Sean Carroll also blogged about this.

Paperless Problems

While listening to an academic talk at a conference, I like to read the corresponding paper being presented.  I follow along by taking notes right in the paper proceedings and marking things that will be of interest to me later.  Then on the flight home, I leisurely browse through the proceedings, looking at my notes.

Apparently, I am also one of only a few people to do this because conferences, almost uniformly, have been getting rid of paper proceedings.  Instead, we get the proceedings on CD or USB stick, or the proceedings are put online, and we are (in theory) supposed to follow along on our laptops or to print the papers interesting to us in advance of the talks.

Unfortunately, this never really worked for me.  My laptop 1) doesn't have enough battery life to last the entire conference* 2) does not allow me to take notes on the paper 3) is too distracting to be used effectively.  These problems are solvable in theory, but it seems in theory only. I could (and sometimes do) fight for the occasional outlet. Technically, there's software that will let me write on pdfs, but it never works properly, and I'm no good at "writing" with my mouse. And I could try to not get distracted on my laptop, but it's a losing battle.  

For all our technical sophistication, we can't yet beat the simplicity of paper.  It's easy to write on and even has great battery life and resolution! But the solution of printing interesting papers in advance is no good because I don't know which papers are interesting to me until I actually go to the talk -- I think of talks as advertisements for papers.  If a talk is good, I'll read the paper afterwards.  If a talk is boring, I probably won't, unless I need to directly for research.

So, desperate for a solution, I got a Kindle so that I could load the papers in advance and read them during the conference.  The latest Kindle even advertised the ability to mark up pdf documents.  However, I quickly discovered that this was no solution at all.  The Kindle interface is so awful, that I managed to do none of these things. The only thing one can realistically do with a Kindle is read novels, preloaded in Amazon's format.  Actually the Kindle did improve my conference travel experience in that I no longer have to lug around books to read for fun.  Unfortunately, my original problem remains.

Now, I do realize that printing costs money, uses paper, and produces big proceedings that are no fun to lug around.  For big conferences like NIPS, I agree that printing all the papers would probably be too much.  And I'm confident that technology will be good enough in a couple years that this will no longer be a problem, making this inconvenience only temporary.  Perhaps going paperless is even the right solution at this time, though I tend to think we abandoned paper too early.

But I don't understand what everyone does in the meantime.  I've never seen anyone follow a paper on a laptop screen, nor have I ever witnessed anyone actually printing papers in advance of talks.  So what should I do?  Should I get an iPad -- will it solve any of my problems?  Is there something everyone is doing that I'm missing?  I don't want to have to bring up the old paper/electronic proceedings debate at the next business meeting!**

* My new laptop's battery might just last long enough, but the other issues remain with using a laptop.

** Okay, I'm bluffing.

Elementary, My Dear Watson?

As many of you know, this week IBM's computer system, Watson, is competing on Jeopardy against its two strongest performers, Ken Jennings and Brad Rutter. At the time of this post, their first match has finished, and Watson is ahead by a large margin.  Watson's lead is so great that it would be quite surprising if Ken or Brad were to catch up.  Given I do machine learning research (though I'd more call the Jeopardy task AI than ML), I couldn't resist posting about this match.

Ever since witnessing humanity's line fall when Deep Blue defeated Kasparov over a decade ago, we humans have become accustomed to computers outperforming us at various tasks.  Computers were first built precisely to do computations quicker and more accurately than we could hope to.  And even though winning at chess takes a lot more than brute-force computing power (if a computer really tried to calculate all possible chess move sequences, it would take more than the current age of the universe for it to finish), chess seems like one of those activities that computers should be good at.  Actually, the best humans can still easily defeat the best computer systems at Go, but few of us will be surprised when, in a couple years, this ceases to be the case.

Jeopardy is another thing all-together.  One might at first ask what possible hope is there of beating a computer at trivia.  Watson can download pretty much the entire internet into its memory (and has), but the problem is what to do with all this information.  And equally difficult is understanding the Jeopardy questions (or "answers" as they call them) in the first place.  Yesterday, Watson had a lot of trouble with the "name the decade" category precisely because it didn't know the answer had to be a decade.  Or in naming the murderer of Snape and others, Watson couldn't properly rank Voldemort over Harry Potter because, even though it had the entire book in its memory, it had no idea of the concept of murder -- only of word associations, and Harry and murder appear rather frequently together (you-know-who's fault).**

So the difficult part for Watson is exactly the easy part for humans (and vice versa).  Watson can easily store the name of every general, country, and battle, but has a lot more difficulty trying to figure out what is being asked.  Sure there are keywords like "he" or "this date," but when there's any ambiguity, it's quite a challenge.  And even if Watson figures out the answer is a date, it still does massive lookups, searches for correlations, runs machine learning algorithms, etc.  At any point, something can go wrong because Watson doesn't "understand" the way we do.  (Interestingly enough, as Louis von Ahn observes on twitter, the final Jeopardy question about city airport names was pretty hard to answer even for us humans using a search engine, though it wasn't so hard for Ken or Brad, but no human would answer Toronto for "U.S. cities").  Ken and Brad need no help interpreting the questions, but to them, remembering the ridiculous amount of information is the hard part.

That being said, the IBM team has done a great job with Watson.  Watson's performance this far already heralds other incredibly useful applications, which are not so unlike the Star Trek TNG computer systems -- only they'll come much before the 24th century.  Don't get me wrong; there's still quite a bit to go.  Real-life speech doesn't come in the form of nicely-formatted Jeopardy riddles (typed to Watson, who still doesn't have speech recognition), but this demonstration shows we've passed a major hurdle.

Finally, I should say that even though I believe that these technological changes are ultimately for the better, I am rooting for Ken and Brad*.  Once Watson can beat us, there's no going back.  In 10 more years, your typical personal computer, in whatever phone/laptop/terminal/watch shape it is, will run circles around Watson.

Yet, whatever discomfort I have will probably soon go away, and I'll become accustomed to computers being better than we are at yet another thing.  I'll take comfort in my personal better-than-Watson computer.  I'll enjoy the efficiency this brings.  I'll celebrate of the new scientific and medical breakthroughs we'll make using the help of (and closer interaction with) ever more powerful computers.  I'll, for one, eventually welcome our trivia overlords.

Update (2/16/11): Watson won today, as expected. And Daniel Reeves has some interesting ideas on how to change the rules of the game.

*I also felt that the game was a bit rigged against Ken and Brad -- the computer can always buzz in faster, so Ken and Brad have to compete for who wins the more human questions.  Were the game 1 on 1, it would have been a lot closer.  And if it were two Watsons vs just Ken or Brad, I'm sure the humans would win.

**Showing, once more that humans are decidedly more human, as we can easily tell the difference between Harry and Voldemort.

The image is of IBM's Watson Avatar and taken from Wikipedia.  It is posted for commentary under "fair use."

Academic Resolutions

I don't normally make New Year's resolutions, and I don't plan on making any explicitly this year, but the coming of a new year feels like a good time to reflect on what we can do better.

So in the spirit of the tradition, I'll list some things many of us researchers (especially computer scientists) could work on in the coming year.

• Finish writing papers at least a week before the (conference) deadline. That way, you can spend the last week improving the writing and rechecking the results.
• Write up results immediately.  This will make writing papers much easier, and you can make sure your work is correct before moving on to the next thing.
• Do reviewing in advance. We often have months to do our reviews, but often end up leaving them for the last week.  Even just reading a paper long before a review is due lets the ideas sink in a lot better.
• Make journal versions (especially of conference papers that don't include full proofs). Until you've given a complete proof, people are justified in questioning your theorems.
• Read more. It never hurts.
• Enjoy work but also leave time to enjoy life.

Feel free, of course, to add to the list in the comments.

And have a happy New Year!

If you are serious about making resolutions and following through on them, check out beeminder. They seem to have good ideas on how to make your future self behave.

My Thoughts on NIPS 2010

This year, I attended my first NIPS conference -- NIPS stands for "Neural Information Processing Systems," but it has become one of the main venues for machine learning research in general. I've attended lots of machine learning conferences before, but somehow never managed to go to NIPS. This year, I had run out of excuses.

NIPS is broader than ICML, the other general machine learning conference, and it is certainly much broader than COLT and ALT, the learning theory conferences. I thought this would be a bad thing, as I expected that I wouldn't understand many of the talks and posters, but it turned out to have been one of my favorite (if not my favorite) conference experiences.

First, because most people at NIPS are in the position of not being familiar with everything, there wasn't the expectation that I would immediately know the model or the problem being tackled when I talked to someone. This strangely made things more, not less, accessible. Also, because lots of topics were outside my areas of research interests, I didn't feel internal pressure to attend many of the talks, and it allowed me to relax and have more time to talk to other researchers. And because NIPS draws a huge attendance, I got to reconnect with many people I hadn't seen for a while, and I had a chance to meet people whom I know only through their research or through correspondence.

On top of all that, within my areas of research, there were quite a few really good contributions, and I wanted to point out some of the papers that I found especially interesting. This is, of course, a list biased not only toward my interests, but also toward the papers whose presentations I happened to catch.

• A Theory of Multiclass Boosting by I. Mukherjee, R.E. Schapire. This paper characterizes necessary and sufficient conditions for multiclass boosting and gives a new multiclass algorithm not based on reductions to the binary case. A nice an elegant paper, it won one of the best student paper awards.
• Online Learning: Random Averages, Combinatorial Parameters, and Learnability by A. Rakhlin, K. Sridharan, A. Tewari. Building on the work of [BPS '09], this paper extends various notions of complexity to the online setting (Radamacher complexity, covering numbers, fat shattering dimension) and proves general online learnability guarantees based on these notions. This is similar in flavor to already known general offline guarantees.
• Trading off Mistakes and Don’t-Know Predictions by A. Sayedi, M. Zadimoghaddam, A. Blum. This paper analyzes a model where the learner is allowed a limited number of prediction mistakes, but is also allowed to answer "I don't know," generalizing the KWIK model [LLW '08]. They prove some nice trade-offs, and there seem to be many potential interesting extensions.
  
• Learning from Logged Implicit Exploration Data by A. Strehl, J. Langford, L. Li, S. Kakade. This paper discusses how to analyze the performance of a new contextual bandit algorithm by running it on previously recorded data. It's pretty intuitive that this should be possible, and this paper goes through the math carefully. This is a problem confronted by many content-serving companies, and I imagine this analysis will be quite useful.
  

Additionally, I also enjoyed David Parkes's talk on the interactions between machine learning and mechanism design -- this seems to be a very interesting area of research.

Finally, I also attended the NIPS workshops, which were rumored to be quite good, and they certainly lived up to their expectations. I especially enjoyed the workshop on Computational Social Science and Wisdom of the Crowds -- I decided to attend a workshop in an area about which I know very little, and all the talks were really good. In fact, from Yiling Chen's and Jake Abernathy's talks, I even learned about connections between prediction markets and online learning, so this workshop ended up being more closely related to my research than I expected.

Clearly, I've been missing out by not having attended the previous NIPS meetings. I'm planning to make up for it in future years.

To Boldly Research

In science, at least in computer science, in order for your research to have impact, you roughly have to do one of two things.

1. Solve a known open problem that people care about.
2. Solve a problem you made up and convince others that it’s interesting / important / impactful.

Often, a paper will do a combination of the two. Of course these aren’t the only ways to have impact – you might find a shorter proof of a known theorem, find a connection between fields others haven’t, etc. But discovering something interesting that nobody else has is a common theme.

So research requires some confidence, if not arrogance, to attempt. Successful researchers clearly need to find this confidence, and it’s not something that comes immediately. So I thought it might be helpful, especially to beginning graduate students (assuming any are reading), for me to spell out why I think succeeding in research is not as hopeless as it might first seem.

Lots of people think in the following chain, especially regarding solving known open problems: 1) Famous researcher X attempted this problem and didn’t get anywhere. 2) They’re clearly better / more experienced than I am. 3) Hence, I won’t be able to solve it.

The worst part of thinking this way is that it’s self-fulfilling – if you never make a serious attempt at a problem believing you can solve it, you probably never will. The second worst part is that this reasoning is flawed.

Lets assume that experienced researcher X attempted (but failed to solve) the problem you’re working on; it doesn’t mean that you can’t. There are a couple reasons for this.

1. Famous researcher X is probably working on lots of problems and doesn’t have nearly as much time to devote to your problem as you do. By seriously applying yourself, you might succeed where X hasn’t.
2. The process of doing research is partly random. You might just have an idea that X hadn’t.
3. Some advances may have come out since X seriously attempted your problem. The average graduate student can solve lots of problems Gauss couldn’t solve, and it’s because science has made progress since then. This type of reasoning holds true on much smaller time scales.

There are also things you can do to increase the chances of being successful, or at least I’ve found that these things have helped me.

1. Work on a problem that you’re actually excited about. This will make it much easier to put in the work needed to be successful. If research feels more like work than fun, then you might be doing it wrong.
2. Find a problem that you think you have a chance in tackling. You should be able to feel in your gut if the problem “feels right.” Many problems are indeed too hard to attempt for beginning researchers.
3. Don’t forget you have access to experienced person Y (your advisor) who might give you some insight that experienced person X didn’t have.

Of course I am also still a relatively young researcher, and getting research confidence is an ongoing process -- I still find working on hard open problems (rightfully) daunting. But if you can fool yourself into thinking you can succeed, even where others have failed, you might just turn out to be right.

A Study in Purple

Yahoo! Research has a lab in New York city, right near Times Square. It is where I spent last year as as a "computing innovation fellow," and as promised, I want to blog about my experience.

Yahoo!'s New York lab isn't large. It has about 15 scientists, whose research spans several areas of computer science — machine learning, algorithms, economics and computation, storage systems, and computational social science. Most of the scientists are permanent researchers, but there also are a few postdocs. The lab often had talks, visitors, and interns to keep the atmosphere lively and interesting.

I mainly worked with John Langford on machine learning problems in computational advertising. A particular problem most search engines need to solve is what advertisements to show to their users, given some contextual information like a user's IP address, shared browser settings, and search query. The goal is to show users ads that they are likely to click, in order for the user to have a good experience and for the search engine to make a profit. However, how to do that is not clear because whenever an ad is shown, no explicit information is received about how well a different ad would have performed in the same situation. Effective algorithms need to balance exploiting strategies they have already learned to be good and exploring new strategies, possibly at some cost. In my time at Yahoo! we made good progress in understanding what sort of guarantees are possible for this problem, which is called the "contextual bandit problem" in the machine learning literature.

It was quite exciting to get to work on real-world internet scale machine learning problems, and have the results of my work have practical consequences. I was also very lucky to have a chance to work with John, who, in addition to being one of the foremost experts on this problem (and in machine learning in general), was a kind and patient host, from whom I learned a lot. I also got to work with Rob Schapire (my undergraduate mentor and collaborator thereafter), who was visiting the lab on his sabbatical from Princeton.

Overall, I was impressed by the flexibility scientists at Yahoo! have in choosing their problems, in having significant time to do research, and in having access to large amounts of real-world data at scales available at only a few other places. We computer scientists are quite lucky to have industrial research jobs as a serious option for research careers.

Now, I have started on a new adventure as a postdoc at Georgia Tech's Algorithms and Randomness Center. I have never been at such a big and "happening" department, and I am excited to get to work with many great researchers on interesting and important problems.

Secret Numbers

I recently moved from New York to Atlanta to take a postdoc at Georgia Tech's Algorithms and Randomness Center. Georgia Tech is a great place to do computer science research, and I am excited to have started working there. I hope to soon blog about ARC and also about my time at Yahoo! Research, but not in this post -- this post is about something I have to do every time I move or get a new job: give lots of people my "secret" numbers.

In 1936, when the Social Security Administration arose from the New Deal, Social Security Numbers (SSNs) were assigned to people to keep track of their accounts. By 1986, the government started using these numbers for tax purposes. And today, Social Security Numbers have basically become national identification numbers.

It's a number we're supposed to keep secret because with it, others can steal our identity and unearth our private information. It is also a number that we're supposed to put in clear-text on tax forms, car purchases, credit card papers, job materials, apartment applications, college applications, doctor's visits, pet adoption forms, appliance rental paperwork, etc. Soon, I feel like I'll need to give my SSN to train conductors and clerks at the supermarket. Yes, I know I'm technically allowed not to give out my SSN number, but this may leave a potential employer or apartment landlord unhappy with me. Being left out of a job or house is possibly worse than giving an nth person my SSN.

Unfortunately Social Security Numbers are not the only examples of this sort of thing. The same problem arises with credit card numbers, routing and account numbers on checks, and even numbers on college id cards. I only pick on the Social Security system because it's the most glaring example of this phenomenon, and possibly the most serious.

The most frustrating thing about this situation is that there is no need for our system to work this way. For example, we could use public key cryptography, where each person has a public and private key (with the public key verifiable by the government) -- people could sign whatever forms they needed to with their private  keys without compromising their integrity. Or if that's too hard, we could have the government generate one-time-use checkable identification numbers that we could give out to untrusted sources. Or we could have two sets of numbers: one that we use for taxes/credit and another that's not secret, but checkable in some database. Or we could do away with this whole national ID thing all-together. I'm sure there are many better solutions.

But that's not how bureaucracy works, and sometimes the short-term cost of switching systems is too high for politicians to do anything about it, even if switching would be better in the longer term. For now, I just have to hope that the dozens of people I shared my secrets with this last week won't abuse our broken system.

This document has some more information about the security of your SSN number.

An Awful Waste of Space?

It's been 50 years since Frank Drake (of the famous Drake equation) started project Ozma -- humanity's first search for signals from alien intelligent life. I thought it might be fun to post on this topic, even though I have absolutely no expertise in it.

In 1950, ten years prior to project Ozma, Enrico Fermi posed a question that might have inspired Drake: if intelligent aliens exist, why haven't we found them (or they us) yet? This question is actually worth thinking about, for the following reasons:

1. Earth is probably not the only planet in the entire universe on which intelligent life evolved. It's likely that (the building blocks of) life can form in many diverse conditions. There's probably even more evidence for these claims now than there was in 1950.
2. Once there's life, evolution should take care of producing intelligent life (at least in some cases).
3. Intelligent life would probably start explore the universe and expand at, perhaps, an exponential rate (hey, the universe is pretty big).
4. So much intelligent life, going all about the universe, you'd think they would have run into us by now! (Or at least sent us some messages)

But of course, despite looking, we haven't yet found anything.  So, why not?

Here's a list of all the (remotely plausible) reasons I can think of, from least to most likely. I realize the events are not all mutually exclusive.

• [very unlikely] Intelligent life is all over the place. But once aliens invent true virtual reality or something else that really floats their boat (and they always do), they have no good reason to go exploring the universe.
• [very unlikely] Intelligent life is everywhere, and different aliens often run into each other. However, whenever this occurs, the more advanced aliens wipe out the less advanced ones. By the anthropic principle, we'll have to wait to be the more advanced ones.
• [unlikely] Intelligent life has already found us on Earth but we don't know it. Either it is successfully hiding from us (more likely) or the government is successfully hiding its signals from us (much less likely).
• [unlikely] Intelligent life occasionally appears, but always (or usually) manages to wipe itself out with the weapons it invents before getting the chance to meet us humans.
• [possible] We are alone and very special. Intelligent life, has not appeared anywhere else. The reason we are even around to ask this question is the anthropic principle, God's will, or plain old extreme luck.
• [reasonable chance] There is life all over the universe, but either it doesn't expand exponentially or the distances are just too great to cover, both for both intelligent beings and their signals.
• [reasonable chance (most likely)] There are intelligent beings emitting signals that reach us from afar, but using methods (or languages) we haven't though of. Eventually, we'll figure it out and our world will change forever.

I'm sure I missed something, so I welcome your comments.

The image of the Very Large Array at Socorro, New Mexico, United States is under a Creative Commons Attribution-Share Alike 2.0 Generic license. Its author is here.

After writing this post, I have found a similar list on Wikipedia's article on the Fermi Paradox.

Pay it Backward

I just finished writing peer reviews for an academic conference. The peer review system is the established method of quality control for scientific publications. When work is submitted for publication to an academic journal, experts judge it for correctness, importance, clarity, etc. It is then published or rejected. In computer science, conference publications, which are at least as important as journal publications, also go through the review process.

The question for this post is: how much peer reviewing ought one (researcher) do?

One easy answer is that you can't do more than you're asked to do. So if you're not being asked to review papers, no need to feel guilty! But when can you start to feel like you're doing too much reviewing? How much is the ideal amount?

The average paper gets reviewed by about 4 people, so it's not hard to compute what your "fair share" of reviewing should be. For each paper you submit, whether it is ultimately accepted or not, add to a running total: 4 divided by the number of coauthors on the paper. This sum, perhaps rounded up and say taken yearly, would be your fair share.

But just like taxes are progressive, so is reviewing load. We cannot expect a someone submitting his first paper to review 4 papers in payment. This person isn't yet known in the community and won't be asked to peer review, and either way he wouldn't yet be considered an "expert" in the field. To make up for this, more senior people have to do more reviewing -- it's only fair. Every established scientist had to submit her first paper without having "payed" for it upfront.

Only the situation is even more lopsided. Scientists need to make up for more than the reviewing burden they've placed on others when they were getting started. Research is very bottom heavy; for instance lots of graduate students leave research right after (or even before) finishing their Ph.D.s. These graduate students (at least in computer science) usually submit some publications, but don't review nearly their "fair share." So those who remain in research need to compensate, and they should -- research is their game.

Of course we have to take into account that very senior people do other forms of service that the rest of the researchers benefit from like chairing conferences, editing journals, and serving on committees. This should perhaps reduce their reviewing load.

My feeling is that in computer science a good time for the amount of reviewing you do to become as large as the amount of reviewing you ask of others is when you're a post-doc. You've stayed past graduate school, and you've become an expert in something -- time to pay your dues.

This year I've done at least as much reviewing as I've "used," but that's how it should be. It's not always the most pleasant work, but I realize it needs to be done. And if I'm lucky enough to stay in research, I expect my reviewing load to continue to increase.

Not the worst price to pay for having a job you love.

Staying Connected

When I visited Japan three years ago, I was stunned to see how many people poked at their phones as they rode the trains or walked along the streets. I had heard a lot about Japan's high-tech industry, and I thought this strange phenomenon was a local quirk limited to Japan, whose society is known for its attachment to technology.

In this respect, Japan was just ahead of the curve. Now, three years later, Manhattan is no different. During my daily commute, I spend considerable effort avoiding bumping into the many people staring down at their plams. I am even occasionally guilty iWalking myself. Whenever we're bored, our phones offer an easy escape to another world of email, tweets, and blogs.

Of course, I realize I'm not pointing out anything new -- countless articles are written on this subject, many coming to different conclusions about what the new phenomena of information at our fingertips, constant connectivity, and faster computing mean for our society: we're getting stupider, we're becoming smarter, the singularity is near, etc. One of the more fun conclusions from this trend is that the reason we haven't met any aliens is because they're busy playing computer games.

I don't know where this technological progress will lead. Information technology allows science to advance at a faster and faster rate, forming a positive feedback loop. Being constantly connected is addictive, and I imagine as technology improves, this trend will get stronger and stronger. I see myriad benefits, but also some downsides. As we spend our minutes checking email and tweets, we leave fewer hours for things that are immediately less fun but ultimately more fulfilling -- like reading a long novel or even simply thinking deeply without interruption.

I got thinking about all this during my recent trip to Israel, where I didn't have the constant connectivity I am now used to. I had no iPhone reception, the internet connection in my hotel was spotty, and I even used physical maps to navigate while driving. And even though it was a bit frustrating, in many ways it was nice to be off the proverbial digital leash.

While I think that technology, including information technology, is a big net plus for society, there's also some real danger of us ending up like those imagined aliens. I don't know if we have any power to change the course this arrow is taking, but I want to stay connected to the real world, even as I inevitably become more connected to the virtual one.

So while I'm happy you're reading this post, maybe it's time for a walk -- without your phone.

Fruitful Fractions

In my first week of college, John Conway gave a lecture on one of his beautiful inventions, fourteen fruitful fractions, to attract freshmen to become math majors. This post is about these fractions.

Here are the 14 fractions, in order: 17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55/1

Here's what you do with them. Start with the number 2, and keep multiplying your number by the first fraction on this list that produces an integer. (Note this is always possible because the last "fraction" is just 55.) Every time you see a power of 2 produced by this procedure, write down the exponent.

For example, if you start with the number 2, you get the sequence: 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, 225, 12375, 10875, 28875, 25375, 67375, 79625, 14875, 13650, 2550, 2340, 1980, 1740, 4620, 4060, 10780, 12740, 2380, 2184, 408, 152, 92, 380, 230, 950, 575, 2375, 9625, 11375, 2125, 1950, 1650, 1450, 3850, 4550, 850, 780, 660, 580, 1540, 1820, 340, 312, 264, 232, 616, 728, 136, 8, 60, ..., 928, 2464, 2912, 544, 32, ...

I've underlined the first three powers of two that appear on the list: 4, 8, 32. Their corresponding exponents (of two) are 2, 3, 5. If you keep going, these exponents generate the prime numbers, and I really mean all the prime numbers, and only the prime numbers, in order! This looks very much like magic.

There has been a long history of research into finding a formula for efficiently generating prime numbers -- this is beyond the scope of this post. But the fourteen fruitful fractions, fun as they are, in some sense aren't as exciting as one might hope. The problem with these fractions is that it takes a huge number of multiplications to get each additional prime, and it gets worse and worse the further you go. Suffice it to say, this is not an efficient method.

But isn't it surprising that such a list exists at all? Yes and no. Mathematicians found this surprising, and it is indeed very surprising until you look at it from the point of view of computer science. You see, this procedure is a prime-generating algorithm, and these fractions and the list they create correspond to a Turing machine (properly programmed for this task), with states, memory, and all. To a computer scientist, that this happens is very natural, and it has to do with the Church-Turing thesis.

Maybe these fractions could be better used to entice freshmen into computer science?

These fractions make an appearance in Conway's Book of Numbers.

Shorter fruitful sequences have since been found, but as far as I understand, finding the shortest such sequence remains open!

The Legacy of Martin Gardner

You may have heard that Martin Gardner passed away a couple days ago at the age of 95. Martin Gardner was perhaps the most famous creator of recreational mathematics. His books, columns, and articles made math fun and accessible to many.

Martin Gardner
photo from the Oberwolfach Photo Collection 

Martin Gardner was best known for his Mathematical Games column in Scientific American from 1956 to 1981. He stopped writing the column before I was even born, but others carried on his legacy. In the 1980s Douglas Hofstadter (the famous author of GEB) took over with with his Metamagical Themas column, and afterwards Ian Stewart (a professional mathematician) continued the tradition with Mathematical Recreations.

Ian Stewart's wonderful column ran from 1990 to 2001, when I was just the right age to become hooked -- I probably read every one of Ian Stewart's articles after 1995. When I got to college, some of my friends pointed me to the earlier columns of Martin Gardner, and I quickly became a fan. It was not hard to me to see why Ron Graham said of him, "Martin has turned thousands of children into mathematicians and thousands of mathematicians into children." I'm sure that I owe some of my love for puzzles to Martin Gardner's legacy, and I was very sad to hear of his passing.

It would only be appropriate to end this post with a puzzle. Martin Gardner really liked this one and named it the "Impossible Puzzle."

Let x and y be two different integers. Both x and y are greater than 1, and their sum is at most 100. Sally is given only their sum, and Paul is given only their product. Sally and Paul are honest and all this is commonly known to both of them.

The following conversation now takes place:

• Paul: I do not know the two numbers.
• Sally: I knew that already.
• Paul: Now I know the two numbers.
• Sally: Now I know them also.

What are these numbers?

No cheating! I will update this post with the solution in a couple days.

A good memorial and an obituary of Martin Gardner.

The writer of the current Scientific American puzzle column, Puzzling Adventures, is Dennis Shasha.

Update (5/30/10): The answer is that the two numbers are 4 and 13. I might have written up a solution if good ones (including Martin Gardner's) didn't appear here.

Fenno's Phenomenon

As November congressional elections approach and analysts fill the airways, I am reminded of a phenomenon called Fenno's Paradox. It goes like this: why is it that voters are usually dissatisfied with congress but keep re-electing their representatives at high rates?

I first heard of Fenno's Paradox as an undergraduate taking an elective course on congressional power. The professor tried to tackle the paradox by looking at the advantages of incumbency, the role of money in elections, the irrationality of voters, etc. But I never understood why this is a paradox at all.

Consider the following situation. Say each voter wants all federal spending to go to his or her own state and votes for representatives who feel the same. Each representative fights to bring all spending to his or her state, and this results in a compromise that the money is split among the states. The voters in every state are furious at the end result, and they blame congress for wasting their money. But all appreciate their respective representatives' valiant efforts.

This may even be not so far from what really happens. I haven't studied this carefully, but most people seem to be against protectionism and special deals, except when these deals favor their own states. Representatives (without national ambitions) are only answerable to their own constituents, so they have incentive to keep pushing for these deals, and in the end everyone is disgusted with congress.

The problem is that whenever I mention this to political scientists, they aren't convinced but don't really tell me why. And clearly I'm not the first person who thought of this "resolution." Perhaps in the social sciences coming up with a non-paradoxical interpretation doesn't resolve a paradox, or a paradox may just mean a seemingly contradictory statement.

Admittedly, I haven't read the literature on this phenomenon, so am I missing something? Perhaps the real resolution to this paradox is that in the future I should stick to posting only on things I know anything about.

Lessons from Future Past

After reading Isaac Asimov's 1950 novel Pebble in the Sky, I started thinking about what visions of the future people had around 50 years ago. While reading the book, I was particularly struck by a mundane passage where one character (Arbin) waits for his turn at the newspaper. This passage wouldn't have been jarring to me had the book's setting not been thousands of years in Earth's future, where spaceships routinely traversed the galaxy. Asimov (at least in this book) imagined people passing a newspaper around in an age of interstellar travel. This reminded me of Captain Kirk signing notepads brought to him by his crew or Princess Leia hiding messages in droids. Just send an email!

But who can blame people for imagining the future this way? The 50s and 60s followed an exciting time in physics -- in the preceding half-century, we had gone from searching for the ever-unfindable aether to discovering relativity and quantum mechanics, inventing televisions and the atomic bomb, and much more. Fusion power providing unlimited free energy was supposed to be just around the corner. Meanwhile, computer science was still in its early stages -- we sent a man to the moon still doing some calculations with slide rules. What happened in the next half a century blindsided everyone.

To be fair, physics has made its own remarkable advances since then (in ways people imagined) -- in everything from incredible materials to new and interesting theoretical developments. But in the last half-century, the real action was in computing. Some visionaries did foresee the rise of computers. But instant and universal access to information? Secure virtual payments? Zettabyte scales? Nobody saw that coming! People envisioned a Golden Age for spaceships and jetpacks, yet got one in computing first.

That some of our predictions would turn out wrong is of course expected, but I still can't help wonder what the next 50 years will bring. There's a near consensus that these advances will continue, that we'll spend more and more time online and computers will do more and more for us. And it's hard for me not to believe that this will help Golden Ages in other fields -- in medicine, now that we can quickly sequence genomes, run studies at unprecedented scales, and take advantage of nanotechnology; in math, as computers become more useful and we collaborate in new ways to solve open problems; even social sciences, as researchers get data they couldn't have dreamed of. Perhaps computers will even start to develop dreams of their own.

And while I think continued breakthroughs in computer science await (How can I not? I'm a computer scientist!), it's useful to remember that our predictions have never been perfect. Who knows where the next exciting advance will actually lie -- it might even be fusion reactors.

Caveat Surfer

A recent article got me thinking about laws and the internet. A couple days ago, the Latvian police apprehended a researcher at the University of Latvia who they claim hacked into government systems and obtained tax documents of various officials. Apparently, there was a security flaw that allowed anyone to access Latvian tax records by basically visiting the proper url. So this alleged "hacker" probably wrote a simple shell script to get 7.5 million tax documents and sent them to a journalist. He now faces a possible 10 years in jail for essentially executing an illegal command.

Now, we don't really know what he did, and I have little knowledge of Latvian law, but it got me thinking about what I'd ideally like the law to be. On one extreme, we have people who write viruses and purposely cause lots of damage; on the other extreme are people who steal wifi from the local coffee shop (even they can get arrested).

This Latvian story falls somewhere in between -- unlike the wifi "thief," the Latvian hacker probably should have known what he was doing could get him into trouble, but do we really want to live in a society where you can be sent to jail for visiting a website? It seems one problem is that visiting a website can include everything from buffer overflow attacks to illegal currency transfers. But this incident feels more like the Latvian government put sensitive information online and then decided to arrest anyone who accessed it.

I guess it's unavoidable that laws about the digital world, even more so than laws about face-to-face interactions, will have seemingly arbitrary lines between what's legal and what's not. But there should be some burden on people and governments to reasonably protect their own data -- and freedom for all of us to poke around a little.

Reddit has some interesting comments on this story.

For a blog on these types of issues by people who have thought about them more than I, visit Freedom to Tinker.