lidsblog

Innovation

After acquiring some knowledge that you didn't have before, it is amazing how you can see new things within something you have seen many times before. 

For example, during my first semester at MIT, I was reading the book chapter "Regularization in Image Restoration and Reconstruction" by Clem Karl, when it hit me that the cameraman image was taken at MIT.  I had seen that image several times before, but before coming to MIT, I hadn't paid attention to the background.

Something similar happened last week.  I talked with Nir Sochen, who was visiting LIDS last Monday and Tuesday, about his and his colleagues' work on curve evolution on manifolds.  Then on Wednesday, Biz gave a talk about open surfaces, something which I had heard about from him several times.  This time, however, it hit me that his work is essentially curve evolution on manifolds.  A shape is to be found that minimizes some functional with the shape as its argument.  Curve evolution is basically gradient descent minimization starting from some initial shape.  When the shape is restricted to lie on a manifold, then the problem becomes curve evolution on a manifold. 

In my meeting with Dr. Sochen, I also told him about the work I will be presenting in a couple of weeks at the IEEE Workshop on Machine Learning for Signal Processing in Cancun.  The basic idea is to take a level set/curve evolution formulation usually applied in image segmentation and to apply it in supervised classification problems of machine learning. 

The topic he discussed in the LIDS Seminar was not related to curve evolution, but to designing overcomplete dictionaries.  For discrete-time signals of length p, a very large dictionary of order p³ atoms is constructed.  The mutual coherence of the dictionary is low: on the order of p^-1/2.  (See slide 16 of this for a definition of mutual coherence.) The atoms of the dictionary are related to the eigenvectors of the harmonic oscillator.  Two versions of the paper that give the details have appeared recently; they may be found here and here. 

Engagement

The opening ceremonies were "frickin' amazing."  Lopez Lomong bore the flag for the USA.  It is quite a story of how he ended up less than a marathon's distance from my birthplace.  (The excellent film God Grew Tired of Us which I saw at Kendall Cinema recounts similar stories.)  His participation was symbolic of the engagement with China that President Bush talked about in this interview. 

Costas: The Opening Ceremonies were glorious. There's much to admire about China's people, China's culture, and its present accomplishments. But this remains an authoritarian state --

Bush: That's true.

Costas: -- with an abysmal human rights record. In the long run, is China's rise irreconcilable with America's interests?

Bush: No. In the long run, America better remain engaged with China, and understand that we can have a cooperative and constructive, yet candid relationship. It's really important for future Presidents to understand the relationship between China and the region, and it's important to make sure that America is engaged with China -- even though we may have some disagreements.

Bush echoes the sentiments expressed by President Lehman in an excellent speech I had the pleasure of hearing at Schoellkopf Field in 2004.  (A quotation from the speech forms the tagline of Krish's blog.)

Lehman: But Ice-9 contamination arguments of this form revolve around other, more limited forms of contact, forms that do not endorse or enable the underlying activity. They take the simple form, “Don’t have anything to do with X because X is bad and if you engage X you will elevate X and debase yourself, X’s name will be legitimated, and yours will be sullied.”

Lehman: My primary message this morning is that you should be very wary of Ice-9 contamination arguments and the sense of despair that is implicitly associated with them. Let me stipulate that there is a special satisfaction one can derive from using them as a reason to withdraw from contact with the world. It is the satisfaction that follows from feeling a certain kind of moral superiority. But I would argue that this satisfaction carries a very heavy price. Yielding to Ice-9 contamination arguments will often, perhaps usually, lead us to miss opportunities to accomplish genuine good in the world through serious engagement.

What does all of this have to do with LIDS?  Working on mathematics and theory, the hazard is to view application and the details of applications as something to be avoided.  From Servo Loops to Fiber Nets written on the fiftieth anniversary of the laboratory by Bob and Sanjoy discusses how LIDS has engaged with various applications through its history.

Gallager and Mitter: Its mathematical foundations lie in complex function theory and harmonic analysis.  Its creativity lies in the discovery of the hidden conceptual structures behind engineering problems and in crystallizing them through the introduction of appropriate mathematical structures.  But the interaction between theoretical and conceptual ideas, engineering synthesis and technological development in the field of systems, communication and control is more complex.  It is in fact a highly complicated feedback process.  Conceptual developments in engineering are incomplete until they lead to a new algorithm, new apparatus or machine.  These in turn require new conceptual ideas for their full utilization. 

Pictures

Just a fleeting glimpse of a picture of Mr. Strong on the shirt of a character in the Mary Poppins—Sound of Music—Mighty Ducks-esque film Thoda Pyaar Thoda Magic has the power to take you back to when you were little and Papa was reading to you.  Through books and especially picture books, you can go anywhere. 

Alan's wife Susanna Natti, when she is not illustrating esoteric talks such as this, illustrates children’s books.  I don't know if it is because of this, or just because of the power of picture books, Alan always refers to the story The Sky is Falling when describing loopy belief propagation.  "Chicken Little told Henny Penny, who told Ducky Lucky, who told Goosey Lucy, who told Chicken Little, who said 'I knew I was right.'"  One advantage of graphical models is the ability to visualize complicated probability distributions as well as algorithms on those distributions.

Another favorite of Alan's is to refer to the Hawaiian islands and 'almost' islands when describing level set methods and curve evolution.  The picture gives your mind much more than equations do.  Lav has argued that in scientific works such as those of information theory, the text and the pictures/diagrams cannot be taken apart (see his class project for details). 

I opened my SSG talk last year with a slide featuring Elmer, Granny, Sylvester, Penelope, and Pepe to go over the fact that objects can be clustered based on a variety of features, e.g. human/animal, color/black-and-white, and coappearance in stories.   For the purposes of the work I was presenting, however, the features that mattered were the prior probabilities of hypotheses for a detection task — perhaps the prior probability of an 'aerosol release.'  The previous year, my early slides included an anatomical diagram by Leonardo and a cartoon, both related to the topic I was presenting.   

In Jason's opinion, technical talks, especially when given at MIT, should be as rich in technical content as a technical report.  They shouldn't be Powerpoint engineered and they should, quoting Dmitry, deliver the "full fury of science."  I agree with those sentiments, but also feel that different media have different requirements.  I don't think that including cartoonish pictures in talks necessarily diminishes their technical depth if the necessary equations, derivations, etc. are also included. 

I'm not sure if I'll put any cartoon-type graphic elements into the slides for my SSG talk this year, but I still have a couple of months to think about it.

The Tunnel

I have passed the technical qualifying exam and research qualifying exam, been in residence for at least four semesters, taken courses and written a master's thesis, satisfied the teaching requirement, and completed the minor program.  I will be turning in my doctoral thesis proposal this week, which is the last of the requirements other than the actual thesis and defense.  My doctoral committee will consist of Alan, John Fisher, Polina Golland, and Josh Tenenbaum.  The road towards graduation in terms of these hurdles is pretty straightforward, but looking at things at that scale misses the tortuosity of the path at the end. 

For no particular reason, I have been following the progress of the tennis player Somdev Dev Varman over the last several weeks.  He turned professional after his college career concluded with back-to-back NCAA championships.  Related in some manner to the royal family of Tripura, Dev Varman went out and won tournaments in Rochester, NY and Pittsburgh, PA on the Futures circuit, won an exhibition tournament in New City, NY, and qualified for and won the tournament in Lexington, KY on the Challenger circuit.  As a professional he has won twenty matches and lost none.  His world ranking has jumped from 797 to 661 to 565 to 345.  This week he is playing another Challenger-level tournament and will very soon be playing full ATP tour level tournaments. 

As discussed by Bill Simmons and James Blake, the ranking system is very definitive and players know exactly what they need to do.  (Doing so is not easy and requires a lot of hard work.)  Many non-research-related careers don't per se have rankings, but the path is about finding the light at the end of the tunnel; it is not about finding the tunnel, as it is with research.  With the thesis proposal now written, I think I have found the tunnel and am now looking for the light at the end of it.

The other Cambridge

So I have managed to get through three semesters at MIT. Three rather traumatic and difficult semesters. This Spring has been tough. I expected it to have gone more smoothly but it turned out to be very challenging indeed. Let's recap what happened.

On the research front, I was a little disappointed because a paper of mine got rejected. But I guess it's something we have to deal with. We have somehow repackaged it and submitted it elsewhere. I managed, somehow, to pass my RQE though. That was probably the greatest achievement of the Spring, since I was not very confident. The two members in my committee were very nice -- no tricky questions were asked, only questions that helped clarify their understanding of my work.

I signed up for 2 classes (Information Theory and Analaysis) and listened to Statistical Learning Theory. All of them were great classes. I have always wanted to learn Information Theory properly. Unfortunately, even until more than halfway through the semester, I didn't get the big picture. I couldn't tell the difference between source and channel coding (an unforgivably sin given I'm in LIDS! But credit me for being honest) until Mukul Agrawal of LIDS enlightened me. Analysis was taught by an expert teacher, Prof. Sig Helgason. Before taking the class, I was a little apprehensive; I didn't know whether I could take the rigor of math. But I can say that I enjoyed the experience of dealing with simple theorems and proofs. It made me feel bright. I have even decided to do Math as a minor and I'll start with Topology or Differential Geometry next semester. Out of all the classes I have ever taken, Statistical Learning Theory by Prof. Tomaso Poggio is by far the class that covered the most topics. I enjoyed all the lectures by the invited guests and of course the teaching staff. Many of the topics were related to my research, e.g. the lectures on manifold learning given by Prof. Partha Niyogi and regularized least squares by Prof. Ryan Rifkin.

I received a bit of good news lately. My paper on "Estimating Signals with Finite Rate of Innovation from Noisy Samples: A Stochastic Algorithm" with Prof. Vivek Goyal has been accepted to the IEEE Transactions on Signal Processing. This work can be found on arXiv but since that version, we have made some rather substantial changes so keep a lookout for it if you're interested in signals with finite rate of innovation. This work was borne out of my class project for 6.342: Wavelets, Approximation and Compression last spring.

I'm now in the other Cambridge, in UK. I am interning at Microsoft Research Cambridge with John Winn and Chris Bishop. More details to come later... Needless to say, I'm so happy to be back at my second home, Cambridge, a place I met my wife and where I spent three wonderful years of my life. There's nothing quite like roaming the quaint streets of Cambridge and seeing the punts along the narrow river Cam. I also attended a formal hall yesterday. Here's a picture.

It's time for a bit of reflection given that I have spent a substantial amount of time at MIT. I have truly enjoyed interacting with the people in LIDS and elsewhere. In particular, Pat Kreidl has given me many words of encouragement, when I often feel that I'm not good enough for MIT, often when I feel stupid. My office mates, including Michael Chen, Jin and Venkat provide me with the avenue to talk about half-cooked ideas and I thank the rest of SSG for putting up with some of my many idiosyncracies, including my heavy footsteps. I have also enjoyed talking with members of Prof. Mitter's group, including Peter Jones and Mukul Agrawal, who gave me the big picture behind Information Theory. On the academic front, I can say that I'm pretty pleased, though there were some disappointments (as mentioned above). I enjoy my research, though it's often like a love-hate relationship. Classes, what can I say? I have endless zest for learning! There are still so many I want to take. For example, how can I leave MIT without knowing what a measure is?

I'll stop here now. I promise to update this blog more frequently.

Vincent

Purpose

Walking home from the Stochastic Systems Symposium, which I played a role in organizing, I encountered two shirtless guys riding their bikes down the middle of the street yelling that the Celtics had advanced to the NBA Finals.  Who knows why they were doing this a night late? 

Let me not be tardy like those shirtless guys on bicycles and write about an emerging paradigm.  Learning of complicated models from training examples has often been a generative pursuit, that is the goal is to learn a model from which one can generate new examples that are like the training examples.  One piece of work of this type is: Describing Visual Scenes Using Transformed Objects and Parts by Sudderth, Torralba, Freeman, and Willsky.  The key word in the title is describing.  The goal is to model or describe visual scenes, but part of the evaluation looks at classification tasks.  If the goal or purpose of the learning is in fact the classification task, then it makes sense to include classification in the objective function, making things more discriminative. 

In both Supervised Topic Models by Blei and McAuliffe in the most recent NIPS and Conditionally Trained Latent Dirichlet Allocation for Text Modeling and Categorization by Lacoste-Julien, Sha, and Jordan presented a couple of months ago at the Learning Workshop in Snowbird, models very much like those of Sudderth et alii are learned with the purpose of classification in mind.  Undirected graphical models are learned for the purpose of classification (hypothesis testing) in Learning Graphical Models for Hypothesis Testing by Sanghavi, Tan, and Willsky presented at the most recent SSP Workshop.  Overcomplete dictionaries are learned for the same purpose in Discriminative Learned Dictionaries for Local Image Analysis by Mairal, Bach, Ponce, Sapiro, and Zisserman to appear at CVPR later this month.

The purpose of classification (hypothesis testing) is also central to work I have done with my brother and fellow LIDS student Lav.  In Quantization of Prior Probabilities for Hypothesis Testing by Varshney and Varshney, which was recently accepted by the IEEE Transactions on Signal Processing and is available from arXiv, we are doing quantization (k-means clustering) with classification performance as the objective.  I encourage you to read the article and see how it is related to NBA referees and racial discrimination.  I'm biased, but I think it is quite interesting. 

I would write more about it, but Game 1 is about to start.  Beat L.A.!

Information Theory, Music, and Life

According to this video (3:41) forwarded to me by Vivek Goyal, Claude E. Shannon, the father of information theory, was a lifelong lover of Dixieland music. 

Being at LIDS for more than three and a half years, I have picked up some knowledge of information theory.  In 1999 and 2000, I played the tuba in The F-M Land Band, a Dixieland band, alongside a bunch of friends from high school: Jason Smucny (clarinet), Steve Keller (saxophone), James Ahern (trumpet), John Downer (trumpet), Paul Arras (trombone), and Dave Chalenski (drums). 

Why do I mention these things?  LIDS alumni gave talks this week about information theory and music. 

Anant Sahai gave a talk entitled Fundamental Bounds for Physical-Layer Power Consumption: "Waterslide Curves" and the Price of Certainty.  Diana Dabby gave a talk entitled Creating Musical Variation. 

The main point of Sahai's talk was that, along with probability of error, the energy per bit required to encode and decode should be the critical parameter in a digital communication system.  He analyzed various decoders, including iterative, message-passing decoders in terms of energy consumed per bit, assuming that certain operations use a certain amount of energy.  The main point of Dabby's talk was that chaos theory can be used to generate variations of musical pieces.  Given a piece of music and a recurrence plot of a chaotic system, a new piece of music can be created by substituting tones in the original piece according the the recurrence plot, but keeping the rhythm, dynamics, and everything else the same. 

When introducing musical variation, she brought up Schoenberg, to whom a large section was devoted in Digital Mantras, a book mentioned in an earlier post.

Dabby mentioned that her ideas could potentially be applied to other types of sequences involving context, such as dance.  Now that I have thought about it more, I would ask: how about the genome?  Variation and recurrence plots show up in genomics as well.  Just as some of her technique-produced variations do not sound pleasing, some genetic variations are unfit to survive.  Mutation and natural selection might result in the evolution of life, but where does the original life come from?  The original musical piece to which the chaotic variation was applied sprang from the creativity of a composer, but it is not clear what the analog is for life, or for that matter, what is life?

According to Schrödinger and others, the characteristic of life is that life reduces entropy.  Thermodynamic entropy and information entropy have a long history of being the same and being different.  Sahai's research makes energy the common currency for communication systems.  Decoding a received message involves a computation which uses energy.  The energy usage might be necessary due to Landauer's principle (which I was introduced to by Lav, and which he was introduced to by Sanjoy, I believe).   

With all this talk of information theory, music, and life, I am starting to venture into Two Famous Papers territory.  A jolt of the Land Band's renditions of Sidewalks of New York and When The Saints Go Marching In might bring me back to "exciting and important problems."

England and ICASSP

I was in England during Spring break to receive my MA degree. Unlike other degrees awarded by Cambridge University, the MA degree is conferred to anyone who's graduated with a BA degree successfully, no less than six years from the end of our first term of residence. This means that if you live long enough, you'll be conferred the degree approximately 3-4 years after your first degree(s). Which was nice for me as this provided me with an excuse to head back to Cambridge to visit my former classmates who were all very successful in their own right. Unlike me, most of them have sensibly decided to get on with life with a proper job, mostly in investment banking and finance. I also managed to meet up with people from the machine learning group at Microsoft Research Cambridge and got a better idea of the scope of my project this summer.

After less than a day to get over 5 hrs of jetlag, I headed further west to Vegas together with some members of LIDS and SSG. ICASSP is a huge conference with emphasis on signal processing and speech. A subset of the talks and posters were very impressive but what I got out of the conference was the chance to meet and talk with people, graduate students as well as professors. I was nervous before my talk but I guess it's natural. I wasn't terribly happy with the way I handled the questions at the end and I hope to do better for my RQE in 3 weeks time. I will have one more practice run at the upcoming North East Student Colloquium on Artificial Intelligence (NESCAI) to be held in Cornell at  the start of May. I'm looking forward to this conference. Some of the talks sound interesting and high quality. After the ICASSP, SSG students took the opportunity to venture to the Grand Canyon. Just in case you've read the previous post by Kush Varshney and are interested to find out who the biggest (and speediest) loser at Vegas was, it's none other than the current blogger. I know I've been a letdown but I'm not a bad poker player. Serdar Balci can attest to that. I was just unlucky to to screwed by the Queen on the river! But Vegas was great fun. We did everything there was to do. Away from the tables I was lucky - When we passed by the Bellagio fountain one night, the waters were dancing to the tune of "Time to Say Goodbye" by Sarah Brightman and Andrea Bocelli. I listen to this tune, on youtube, whenever I'm stressed.  I encourage you to do so too.   

Alright, as mentioned, I will be taking my RQE in 3 weeks. I should really start panicking and work hard to understand all the nitty-gritty details about my research. But before that, I have one term paper for Information Theory 6.441 and two more midterms (6.441 and 18.100B) to work on. In addition, I have some research to write up before my internship at Microsoft. So it should be an interesting end to the semester.

Vincent

Convex Optimization

Why can't things be like they used to be?  Pan Am and TWA?  Flying without quart-sized, clear, plastic, zip-top bags?  Boarding economy class from the back of the aircraft to the front?  As Pablo mentioned in the last lecture of 6.255, the newfangled zone boarding is the solution to an optimization problem to minimize boarding time.  I don't agree with the model used to describe the constraints and particularly the costs, but I don't doubt that zone boarding is the optimal feasible solution for the given model. 

I had the pleasure (or hassle) of zone boarding four times recently on the way to and on the way back from Las Vegas.  I wasn't there to emulate 21, or to lose a hundred dollars in ten minutes, but to attend the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP). 

The students of LIDS were there in force.  Myung Jin Choi & Venkat Chandrasekaran had a paper Maximum Entropy Relaxation for Multiscale Graphical Model Selection.  Dmitry Malioutov had a paper Compressed Sensing with Sequential Observations.  Mesrob Ohannessian had a paper A Turbo-Style Algorithm for Lexical Baseforms Estimation. Xiaomeng (Shirley) Shi had a paper Joint Base-Calling of Two DNA Sequences with Factor Graphs.  Vincent Tan had a paper Learning Max-Weight Discriminative Forests.  Lav Varshney & I had a paper Minimum Mean Bayes Risk Error Quantization of Prior Probabilities.

Aside from the Elvis impersonators and mimes, one interesting thing at the conference was a panel on convex optimization theory and practice in signal processing.  The main lesson that was imparted was that people working on signal processing applications really need to learn and use modern techniques of convex optimization, as well as collaborate with optimization theorists starting at the initial stages of problem formulation.  (One example I can point to where convex optimization theory has been used is Jason Johnson's Lagrangian relaxation work.) 

LIDS is uniquely positioned in this regard because we have both signal processors and optimizers within one lab.  Some members of LIDS are aeronautical engineers; now if we also had overhead bin designers, we could finally make aircraft boarding hassle-free. 

Jury Duty

A few days after coming back from Houston, I had the pleasure of going up to Lowell, MA for jury duty. 

While biding my time in the courthouse, it occurred to me that jury duty is much like reviewing.  (Other people have, of course, made the same observation.)  The review process is subject to much debate, e.g. these two blog entries.  One difference for me is that I hope to never be on the other side in criminal proceedings, but I have and will continue to be on the other side in peer review. 

What was the probability of my getting called to jury duty in Lowell, not being empanelled, getting released before lunchtime, stopping at the Burlington Mall for lunch but first walking into Sears to buy pants at the same time the principal chair of the trumpet section in my high school's wind ensemble during my freshman year is walking out of Sears, and remembering his name (Larry Chien) ten seconds later?  There are many considerations in reporting probabilities of coincidental events after the fact, as discussed here recently in the context of primary elections in the city of my birth. 

The juror's task in a criminal trial is to decide whether the defendant is guilty beyond a reasonable doubt based on the evidence presented.  He or she is supposed to not have prior biases, but is supposed to use intelligence.  Are not priors a critical part of intelligence?  I am not a philosopher and do not pretend to have any insight about this topic.  Some quotations loosely related to the topic from things I have read recently:

The most important qualifications of a juror are fairness and impartiality. The juror must be led by intelligence, not by emotions, must put aside all bias and prejudice, must decide the facts and apply the law impartially.

It is a striking theorem of Bayesian analysis that, if the DM's prior distribution of the parameter p is sufficiently 'open minded', then, if the true value of p is p* (say), then the sequence of the DM's posterior distributions of p will become more and more concentrated in the neighborhood of p*.  In other words, the DM will asymptotically learn the true value of the parameter p.  By 'open minded' I mean, roughly speaking, that the DM does not rule out as impossible any value of the parameter between zero and one.  Technical Note: More precisely, 'open minded' means that the support of the prior is the entire unit interval.

It was with a sense of bewilderment and confusion that I left Benares.  Yet I was captivated by it all, and from that moment to this India has been to me the land of enduring and ever-increasing fascination, nor has a day passed without my learning something new and strange about the working of the Indian mentality.  How to express the thing is difficult, but I may put it thus.  As opposed to the Western mind, the Indian mind does not seem to be conditioned by facts.  Take the most highly educated Indian graduate of Oxford or Cambridge, a man versed in the arts, sciences or philosophy.  He will not think it incompatible with his learning to go on believing what he had been taught as a boy.  He has absorbed a new knowledge but it has not displaced the old.  Also, there seems to be a fusion in the Indian mind between myth and history, as though both were of a piece.  Of Indian thinking as I encountered it at the end of the nineteenth century, the most consistent thing was inconsistency.  Yet Indians in general are highly intelligent.  Their lawyers are among the best, and their linguists and teachers compare favourably with those of any other people.

The trouble is that this traditional picture of the relation between deduction and induction conflates two quite different things, a theory of reasoning and a theory of what follows from what.

1. Office of Jury Commissioner, Commonwealth of Massachusetts (1998). The Trial Juror's Handbook, Sixth Edition.
2. Roy Radner (2005). Costly and Bounded Rationality in Individual and Team Decision-making.  In: Understanding Industrial and Corporate Change. Oxford University Press.
3. Sam Higginbottom (1949). Sam Higginbottom: Farmer, p. 53. New York: Charles Scribner's Sons.
4. Gilbert Harman and Sanjeev Kulkarni (2007). Reliable Reasoning: Induction and Statistical Learning Theory, p. 5. MIT Press.