lidsblog

Your Folly, My Jolly

First of all, props to John Downer for the title of this post. 

Energy is starting to become a key area of focus at MIT.  Within LIDS, there were several energy-related seminars this academic year.  Two weeks ago, the Secretary of Energy, Steven Chu gave a talk and said that a major increase in basic research is necessary in the United States in order to provide the new energy technologies needed to avert catastrophic climate change. 

Unfortunately, I was not able to attend because it coincided with a talk by Al Hero on a topic very close to my research: linear dimensionality reduction.  Prof. Hero discussed dimensionality reduction when models of statistical structure underlying the data are applicable, for example a graphical model that generates data.  He also focused on distributed implementations.  In some of my work, I have looked at linear dimensionality reduction for margin-based classification, including with distributed implementation.  I will be presenting that work this summer at the Fusion conference. 

The fusion in this case is information fusion, not the type of fusion that "has the potential to meet future worldwide energy needs in a safe, sustainable manner without carbon dioxide emissions."

I am doing an internship this summer at Lawrence Livermore National Laboratory, in the Systems and Decision Sciences section.  The National Ignition Facility, a device to create a fusion reaction, is being dedicated on Friday at the lab.  Some people think its a folly, but for me its a jolly.  I'll get to hear Secretary Chu after all. 

Spring 2009

I recently returned from SPARS09, a small workshop dedicated to sparse approximation and compressed sensing. It was held in St Malo, France. I presented a paper on model selection and nonnegative matrix factorization.

My research this year has primarily been focused on rates of convergence for learning tree structured graphical models. This work, co-authored with A. Anandkumar, L. Tong and my advisor Alan Willsky, has been accepted to ISIT 2009 and the longer version has been posted on arXiv.

I'll be interning at Microsoft Research again this summer. It should be interesting because I can do machine learning on real data.

I took a class on measure theory and functional analysis this semester. I think both subjects are absolutely fascinating. The next thing I would like to learn is Geometry on Manifolds.

Vincent

Atlantis

The ocean is deep.

Last week, there was some halchal regarding the purported discovery of the lost city of Atlantis by users of Google Earth, which has recently added bathymetry data.  Here is Google's write-up about it.  (By the way, that write-up also describes the Loihi Seamount, which is a Hawaiian 'almost' island.) 

So what was this so-called discovery?  It was an artifact of the estimated depth.  High quality ocean depth data can be collected by boats using echosounding, but this data acquisition is only local to where the boat is, and it is expensive to cover large areas.  Lower quality data can be collected using remote sensing satellites.  The artifact was that in the places there were boat measurements, a lower depth was estimated than in places that there weren't boat measurements. 

An estimation procedure ought to assimilate the various data available and perhaps also incorporate a prior model so as not to leave artifacts that people might think are Atlantis.  As described in the related paper, it is not an easy problem.  However, perhaps benefits could be gained by utilizing methods such as those described in this and this. 

Speaking of measuring the ocean and boats, after a talk by Marco Duarte a couple of weeks ago, my officemate Matt Johnson was saying how it would be a great demonstration of the power of compressed sensing (CS) if you made a version of the game Battleship in which one player could take CS measurements and exploit structured sparsity, while the other player played normally.  The CS player would win, either every time or with overwhelming probability --- I'm not sure exactly which.  

An interesting statement in the Atlantis write-up is: "If there really are little green men hiding somewhere, the ocean's not a bad place to do it. Mars, Venus, the moon, and even some asteroids are mapped at far higher resolution than our own oceans (the global map of Mars is about 250 times as accurate as the global map of our own ocean)."  It is easier to figure out relief above water than underwater, but the opposite is true for figuring out what is in the crust.  Doing large seismological surveys under the ocean with boats is easier than doing it on land with heavy trucks, as I've come to learn from Richard Sears, who sits two doors down from my office. 

The ocean is deep and the crust is thick. 

Thanks

The organizers would like to thank everyone for making the LIDS Student Conference a resounding success.

LIDS Student Conference 2009

**The Fourteenth Annual LIDS Student Conference**

8:30am-5:00pm, Thursday and Friday, January 29-30, 2009

Stata Center, 32-155, MIT

Sponsored by Draper Laboratory

The 14th Annual LIDS Student Conference is be to held on January 29 and 30, 2009, on Student Street in the Stata Center. The conference promises to be a stimulating two days of student presentations, an intriguing panel discussion, and lectures by our eminent guests:

-- Andrew Barron, Yale

-- Christos Cassandras, BU

-- Vincent Poor, Princeton

-- Steve Shreve, CMU

Student presentations will be in the areas of signals and estimation, optimization and control systems, information and coding theory, communications and networks, and graphical models. Abstracts of both student presentations and invited talks are available at the conference website at http://lidsconf.mit.edu/

We hope to see you at the student conference.

Sincerely,

LIDS Student Conference Committee

Recent Books

One of the many books I read over the summer. This is definitely worth a read, an introduction to the prime number theorem and the Riemann hypothesis. Accessible to anyone who is interested in math and prime numbers.

This is a harder book on the Riemann hypothesis. It's way more technical. I found the du Sautoy book more entertaining.

This is a book on the origins of algebra by the same author as "Prime Obsession".

One of 7 Millennium problems, the Poincare conjecture, was solved by Perelman. This book describes the problem and its solution to laymen.

A powerful book by the President-Elect on his values, his view on politics, the world and his family. The chapter on his family was, by far, my favorite one. 

Consistency

Last Friday before a sumptuous Thanksgiving-themed LIDS lunch, a seminar was presented by Xu Huan of McGill University.  Mr. Xu's talk was entitled "Miracle of Regularization," and was joint work with his advisor Shie Mannor, formerly a LIDS post-doc, and Constantine Caramanis, formerly a LIDS student and author of some very nice expository articles.  Part of the work was recently featured on An Ergodic Walk, the blog of Anand Sarwate. 

The supervised learning problem with regularization is studied from the viewpoint of robust optimization.  Xu first motivated why regularization is needed in supervised learning from finite training data by appealing to properties of ill-posed problems stated by Hadamard, in particular that a unique solution does not exist and that the solution does not depend continuously on the data.  Other motivations for regularization in supervised learning come from the structural risk minimization principle. 

I first learned about robust optimization in a lecture by Melvyn Sim tele-delivered from Singapore for the class 6.255.  When data is uncertain but known to belong to an uncertainty set, the basic idea of robust optimization is to optimize the objective function with respect to the worst-case point in the uncertainty set, i.e. doing a min-max or a max-min optimization. 

In typical supervised classification formulations, a decision function is to be found that minimizes an empirical risk of training data, often with a margin-based loss function, plus a regularization term, often a norm in the space of decision functions, weighted by a non-negative scalar c.  Xu, Caramanis, and Mannor show how this regularization formulation arises when a robust optimization problem with uncertainty around training examples is solved.  They also discuss what the uncertainty set corresponding to standard regularization terms is, and what c means in terms of the uncertainty set. 

The training data is generally assumed to be independent samples from a joint distribution of features and class labels.  (This joint distribution is unknown.)  A classifier is said to be consistent if in the limit as the size of the training set goes to infinity, it converges in probability to the optimal classifier that minimizes probability of error if the joint distribution were known.  Several recent papers, including those by Lin; Steinwart; and Bartlett, Jordan, and McAuliffe, discuss the properties of the margin-based loss function in the empirical risk and of the regularization term needed for a classifier to be consistent.  Xu et al. show consistency of classifiers using the robust optimization perspective they develop. 

Munther Dahleh made several remarks/questions at the end of the talk, including asking about connections to robust estimation studied twenty years ago.  Interestingly, when Mike Jordan was visiting LIDS a few weeks ago, he also discussed classifier consistency in his SSG talk, which was based on joint work with XuanLong Nguyen and former LIDS student Martin Wainwright.  That work links valid margin-based loss functions and Ali-Silvey distances. 

Spread the Wealth Around

Barack Obama to Joe "The Plumber" Wurzelbacher: I think when you spread the wealth around, it’s good for everybody.

I was out of the country last week and as always, was glad to hear the words "welcome home" from the immigration officer upon my return.  I came back to America, but apparently not to "real" America.  I participated in the IEEE International Workshop on Machine Learning for Signal Processing (MLSP), which was held in Mexico this year.  At the conference banquet, I sat between J. J. Remus of Duke University and Sergios Theodoridis of the University of Athens.  Remus, who is originally from Wasilla, Alaska (for certain a part of "real" America), had a poster on distance-weighted nearest neighbor classification.  Theodoridis gave a plenary talk and a regular oral presentation on using a sequence of projections onto convex sets in reproducing kernel Hilbert spaces to find feasible, but not necessarily optimized, solutions to problems such as finding classifiers. 

A paper on sparsity measures, which relates to the quotation at the top of this post, was presented by Niall Hurley and Scott Rickard.  Rickard had proposed six desiderata for sparsity measures in 2004, of which four were originally proposed by economists in the early part of the last century in the context of wealth inequity.  In the MLSP work, it is shown that among fifteen sparsity measures, including the popular ℓ₀ and ℓ₁, the Gini index alone satisfies the six desiderata.  Considering a vector of coefficient absolute values, where a large valued coefficient is analogous to a rich person, the six desiderata are:

1. Robin Hood.  Stealing from the rich and giving to the poor decreases sparsity.
2. Scaling.  Multiplying the wealth distribution by a constant does not change sparsity.
3. Rising Tide.  Adding a constant to each coefficient decreases sparsity.
4. Cloning.  If there is a twin population with identical wealth distribution, the sparsity in one population is the same as in the combination of the two.
5. Bill Gates.  As one individual becomes infinitely wealthy, the wealth distribution becomes as sparse as possible.
6. Babies.  Adding individuals with zero wealth increases sparsity.

According to the analogy, a sparse signal representation is clearly not an Obama signal representation.  I think I'll put in a request to change the title of a journal paper of mine to Palin Representation in Structured Dictionaries. 

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.