lidsblog

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.

Spring

The start of the spring semester provides me with a stark reminder that I've been here for 1 full year. I had better work harder on my research. I, unlike most graduate students in EECS, started graduate school in the Spring. My first semester here was really tough (rough) and my second slightly better. Hopefully, this Spring will be smooth-sailing. There are several key events that I'm looking forward to this semester.

1. I got a reminder in the mail that I'll be taking my RQE later in the semester. I know this isn't great fun and frankly I don't feel terribly well prepared at this point. More updates on this shortly.
2. I'll be visiting my alma mater, Cambridge University for two reasons. Firstly, in preparation for my summer internship, I'm going over to Microsoft Research to speak my mentor and other scientists. Also, because it's been 7 years since my matriculation, I'm entitled to receive my MA degree.
3. I'll be going to ICASSP. This is the largest signal processing conference. It should be good fun, meeting and talking to people. When I was an undergraduate, I used to travel Europe and Africa for fun. Now, I hardly have time to travel for fun and the traveling I do is mainly to present the stuff at conferences. I haven't forgotten about Kilimanjaro though. Next IAP perhaps.

Kush Varshney has given everyone a nice summary of the LIDS Student Conference so I'll not try to repeat that. My wife and I had a fantastic dinner at the MIT Faculty Club last night. I have been rather ill this past week so I couldn't enjoy the dessert as much as I had wanted to though. My temperature reached 102F, which made me very down. :(

I'm getting better with the news that Manchester United and Chelsea both dropped points during this round of matches. My team, Arsenal, has done well to keep up with United but in football, anything can happen. In particular, with the resumption of the Champions League, Arsenal's resources will be stretched. Being 2 points clear at the top of the table at the start of February is something I didn't expect of Arsenal at the start of the season. I seriously thought they would struggle but Adebayor has exceeded all expectations.

Ok more updates during the spring. I should stop rambling and start keeping up with the literature.

Vincent

LIDS Student Conference: Day 2

Yesterday was the second day of the 13th Annual LIDS Student Conference, organized as always by the students of the laboratory.  Day 2 featured two invited speakers, thirteen student talks, a panel discussion on academia-industry interactions, and the conference banquet.  All of the abstracts can be found on the conference website; photos and videos will make their way there eventually.

A list of today's student speakers along with descriptions of their talks, as delightful as descriptions from Day 1:

• Noah Stein - players with polynomial preferences
• Marco Pavone - strategies for successful servicing
• Amir Ali Ahmadi - loosening Lyapunov
• Sertac Karaman - Talos' trials and tribulations
• Melanie Rudoy - making more money than Markowitz
• Nicholas Matsakis - duplicate detection in databases
• Raluca Ada Popa - ensuring elections
• Lav Varshney - modulating mud: messaging and material transport
• Sheng Jing - dealings with diversity and distortion
• Emmanuel Abbe - divergence-optimized decoding for DMCs
• Jay-Kumar Sundararajan - queueing in coded communication networks
• Vincent Tan - arboreal adventures
• Barış Nakiboğlu - errors, erasures, exponents

LIDS Student Conference: Day 1

Today was the first day of the 13th Annual LIDS Student Conference, organized as always by the students of the laboratory.  The organizing commitee is being chaired by Jerome and Sertac this year.  So far we have had talks by two invited speakers and fifteen student talks.  All of the abstracts can be found on the conference website; photos and videos will make their way there eventually. 

A list of today's student speakers along with delightful descriptions of their talks:

• Robert Panish - egomotion, epipolar constraints, extended Kalman filter, and estimating depth
• Paul Njoroge - competition between connected commercial backbones with congestion
• Amit Bhatia - quick, contemporaneous convergence of craft
• Roberto Naldi - UAVs or UFOs?
• Theophane Weber - decentralized decisions and decaying dependence with distance
• Emanuele Garone - control with corrupted communications
• Michael Rinehart - conditions on controllers for a class of continuous-time switched systems
• Jelani Nelson - estimating empirical entropy efficiently
• Srikanth Jagabathula - sportsmanlike scheduling
• Ilan Lobel - aprendizagem das ações dos amigos
• Alexander Olshevsky - algorithms for averaging among agents
• Jinwoo Shin - mitigating mixing times in Markov chains
• Urs Niesen - characterization of cooperative communication
• Victor Preciado - probabilistic properties of plexuses
• Sankara Narayanan Vaideeswaran - simulations of splitting into subsets

Day 2 will feature fourteen more student talks, two more invited speakers, and the always popular panel discussion. 

Carpal Tunnel Syndrome

First turning on the TV at the Hilton hotel in Houston, something most unexpected came on: a commercial advertising the Brown Procedure, an endoscopic treatment for carpal tunnel syndrome. 

I was in Houston on a junket visiting Shell International Exploration and Production's Bellaire Technology Center with Biz, Dahua, Dmitry, Hyun, Jin, Venkat, and Vincent alongside.  Back in the day when Bell Labs was Bell Labs, the Bellaire facility was the Bell Labs of the oil industry.  The mission that the eight of us chose to accept was learning how teams of geologists and geophysicists interpret data, primarily seismic data, to find reservoirs of hydrocarbons from which it might be profitable to extract oil and natural gas. 

Dahua summarizes his experience here.  Interestingly, since my eyes are now looking for it, I keep seeing articles about this stuff, e.g. these two articles in the December SIAM News and this article in the January IEEE Spectrum. 

There are no pools or rivers or streams of oil in the earth's crust.  Oil exists in the pore spaces of rocks such as sandstone.  The presence or absence of three things make or break a prospect: source, reservoir, and trap.  Source means that over geologic time, organic material transformed into oil through heat and pressure.  Oil is less dense than rock, so it tends to move towards the surface if possible.  Reservoir is a layer of the crust with pore space, a good example being a layer of sandstone.  Trap is a geometric arrangement such that the reservoir is surrounded on all sides except the bottom by impermeable layers such as those made of shale.  Trap geometries are often the result of faulting, i.e. the cracking and pushing up of some regions leaving other regions below. 

In some parts of the world, like under the Gulf of Mexico, the crust contains massive bodies of salt.  The salt behaves like toothpaste, getting squeezed and pinched by the weight of the surrounding rock.  Importantly, salt is also impermeable to oil. 

To image the crust, seismic data is collected.  A large amplitude acoustic pulse or chirp signal is input into the ground and the reflections are recorded.  Reflections occur from interfaces between different rock types such as sandstone-shale boundaries.  Reflections from the same spatial location are recorded many times because a single record has extremely poor signal to noise ratio.  The data that is collected for a spatial location is in time, not depth.  It must be migrated from time to depth taking the speed of sound in the materials below into account, an ill-posed and challenging problem.

With a seismic volume either in time or depth, the interpreter's laborious job is to pick out faults, salt bodies, and continuous layers of reservoir rock.  Then the task is to understand the depositional environments, geology, etc., identify prospects, and finally decide whether the risk to drill them is worth it.  (It costs somewhere around one hundred million dollars to drill an exploratory 'wildcat' well.) 

Shell has developed some automatic pickers that we got to play around with that somewhat reduce the laborious, repetitive nature of picking faults and events.  However, the tools are far from perfect.  Interpreters are still subject to much repetitive strain injury such as carpal tunnel syndrome.  Now that we have seen the procedure that interpreters go through and what open problems exist, we can contribute to the development of interpretation tools for geologists and geophysicists so that they can focus their time on the higher level, understanding-based tasks of interpretation rather than on the lower level, repetitive tasks. 

An eventual goal is to put Dr. Brown out of business and develop a full object recognition system, but that is a long way off.