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. 

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. 

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. 

Large-Scale and Decentralized

Germans seem to like engineering-related TV commercials.  For example, when I was at École Centrale in 2006, Christian Wachinger, a German student who was also visiting, was quite amused by this Volkswagen commercial that "unpimp[ed] ze auto."  Also, there is an IBM commercial that has been airing recently in the US featuring buzzword bingo.  It seems that this commercial has been out in Germany for a few months and become popular; the German version can be seen here. 

The ivory tower is not an impenetrable defense from buzzwords.  My officemate Pat was recently quipping that one of us should propose to work on small-scale centralized algorithms, the thing to do now being large-scale, decentralized or distributed algorithms. 

Large-scale distributed algorithms are often defined on or described via graphs. 

Some of the students in SSG, nicknamed graphniks by Alan, spend some of their time looking at inference in large-scale graphical models via efficient message-passing algorithms.  Inference is the problem of estimating unobserved nodes X from observed nodes Y in a graphical model by computing marginal conditional densities (X_i|Y), or statistics of those marginal conditional densities such as mean and variance.  Belief propagation, an algorithm for inference is inherently distributed as the procedure involves passing messages -- functions computed locally at nodes, details of which are not described here -- along edges of the graphical model in an iterative fashion.

Part of Devavrat Shah's research agenda is also message-passing algorithms, in particular to solve problems such as matching, independent set, and scheduling.  Message-passing algorithms are used in the decoding of low-density parity-check codes, which were developed by Bob Gallager. 

On Tuesday, Lieven Vandenberghe gave a talk entitled, "Chordal sparsity in normal graphical models and semidefinite programming" at the LIDS colloquium.  He described interior point matrix optimization methods that make use of the junction tree, where the matrix in question is an adjacency matrix of a graph.  On Thursday, Éva Tardos gave a talk on games in networks during a CSAIL colloquium.  She first discussed congestion games in which agents do not cooperate and make their own choices in a decentralized manner.  Then she discussed buying and selling games on trade networks in which there is a little bit of cooperation or collusion.  One of her main points was that algorithmic game theory needs to start dealing more with cooperation.  Oh snap! German engineering in da house, ya!  What?  Oh.  Belgian and Hungarian engineering in da house, ya!

Letter of Intent

The letter of intent is an interesting concept, isn't it?

With the national letter of intent early signing period for collegiate athletics such as basketball recently concluding, I was reminded of something I wrote for a fellowship application in response to the question, "What are the considerations involved in your choice of graduate school?" and I thought it would be interesting to revisit four years later.

First, what I wrote four years ago:
I am approaching my choice of graduate school in much the same way a high school basketball recruit would choose a college. If I were a basketball player, I would choose to join the national champion Syracuse University Orangemen because of many factors. The program has a rich heritage, but is also highly regarded today. The facilities are of high quality and unparalleled in the nation. My peers would be diverse, talented, and likable. The coaching staff (the faculty) has a good mix of ageless hall-of-famers, and up and coming younger members. There is a certain stability in the teaching philosophy, but also innovation to keep up with the times. There is freedom for students to pursue their interests within general guidelines and have fun doing it. The coaching instills confidence to follow instincts rather than always looking to the bench for instruction. There is marked improvement in individual ability from the first day to the last, and good placement afterwards. There is also a commitment to community involvement.

Now, the revisiting:

• Rich heritage - check
• Highly regarded today - check
• Facilities - unparalleled: yes; high quality: debatable
• Peers - check
• Faculty - double check
• Teaching - stability: I think so; innovation: yes
• Freedom - I would say so
• Instilling confidence - I have enough confidence to post blog entries as a representative of the lab for the world's consumption without running them by faculty members, so that's something
• Improvement - I would not have been able to make any sense of the Heine-Borel theorem, but now I can.  I had no idea what the simplex algorithm was, but now I do.  I can understand and summarize complicated concepts much better than I could.  And so on.
• Placement - graduates seem to be doing well for themselves
• Community involvement - getting there, but room for improvement

Good overall.

On another note, although there is no signed letter of intent, Srikanth Jagabathula and Vincent Tan will be joining the roster of the LIDS-Blog very soon, so be on the lookout for their posts.

Orange Alert

Last week, Ayres Fan, a fellow student in the Stochastic Systems Group, who is close to finishing, was suggesting that I should write about my beloved Syracuse Orange in this space.  I was completely disillusioned after the first three weeks of the football season, but that changed on Saturday.  Let me not write about the alert sounded by the Orange to the college football world, but a different orange alert. 

This past week was career week at MIT and a lot of representatives from companies were in town.  One Course 6 undergrad, in order to stand out at the career fair, fashioned some LED-laden bling.  My officemate Emily, in fact, complimented this student on her piece of flair at the fair.  On Friday, we heard that she had been arrested at gunpoint at the airport as a suspected terrorist. 

Note to self: 'flying while brown' is already an issue for me, so I shouldn't compound things by carrying conspicuous electronics -- I should really hide any electronic items I have on my person. 

So how do intelligence analysts investigate whether someone is a terrorist or not? 

Also on Friday, I was invited by my friend Zennard Sun to a dinner and demo hosted by Palantir at the upscale Nine Zero Hotel in Boston.  Palantir is a fairly new company that is developing very powerful software platforms for analysts, both in the intelligence community and the financial industry.  The intelligence platform is a way to deal with data about links among people and to analyze whether a group of people forms a clique, whether two people are really the same person, how money flowed from leaders out to operatives and then whether this resulted in coordinated travel, etc.  Some screen shots are available here, but my verbal description and the screen shots do not do the product justice.  It was really, really impressive, and apparently completely unlike anything currently deployed. 

Palantir incorporates some aspects of machine learning into their product, but their goal is not to have one button that will do everything -- they want to use human capabilities as well.  One thing I have been discussing with Alan recently is the idea of machine learning for a purpose, possibly an unspecified or underspecified purpose at that.  The usual modus operandi in machine learning is maximum likelihood -- finding the most likely explanation given a model.  In discussions Alan has had with people like military commanders, what he has observed is that commanders do want the most likely explanation, but also the most dangerous explanation and the most unusual or weirdest explanation. 

Some recent work by Sujay Sanghavi and Vincent Tan looks at doing machine learning for a purpose, where the purpose is hypothesis testing.  They learn graphical models from data to minimize hypothesis testing decision error.  What do you do when the cost or utility function to optimize is not given a priori?  That is an interesting line of inquiry that I may look at in the years to come. 

I wonder whether Ayres will encounter Palantir's financial platform Hedgehog in the years to come after he starts his job at Goldman Sachs. 

Professor Servetto

The information theory community lost one of its own under tragic circumstances.

"a man of great intelligence, intense conviction, boundless energy, great personal warmth with 'an enthusiasm for research, information theory, teaching and ideas.'"

"The first time I walked into his office was just after someone had brought him a freshly baked chocolate chip cookie. Without a second thought, he immediately split the cookie and handed me half. I still remember seeing one of the melted chips stretch between the two halves of the cookie and thinking hat a generous thing to do."

I will always remember him as the bearded professor who attended lectures of an introductory probability class the semester I was taking it, just to get a different perspective on a subject he knew backwards and forwards.

I was not his advisee.  I was never in his class.  We had barely interacted.  Yet, he took an interest in me.  When I was deciding on graduate schools, we met in his office on the third floor of Rhodes Hall.  He listened to my interests and what I had thought of my visits to the various schools.  He gave me two names, Bresler and Willsky, saying that these two would be good fits.  Prescience.

There are some people with whom even a fleeting relationship means a great deal.  Professor Servetto was one of those people. 

Eyes on the Prize

Dear Takeru,

I'm in a 10der mood to-day
& feel poetic 2;
4 fun I'll just — off a line
& send it off 2 U.

I'm sorry you've been 6 O long;
Don't B disconsol8;
But bear your ills with 42de,
& they won't seem so gr8.

Hope your jaw-thritis clears up before tomorrow.

Sincerely,
Kush

---

New York City in the period 1900-1920 was a different world than today.  However, many things that one may have expected to have fallen by the wayside, have in fact persisted.  The poem above, published in 1906 by the New York publisher Charles Scribner's Sons within a collection of whimsies, seems slightly anachronistic, but is readily understood by today's practitioners of SMS language. 

The hot dog eating contest started at Coney Island in 1916 has not only persisted, but has become the Super Bowl of the competitive eating circuit.  The successor to an international technical organization founded in 1912 New York is currently the largest in the world and counts many LIDS students and faculty as members and fellows. 

The Orteig Prize, first offered in 1919 by a New York hotelier for a non-stop trans-Atlantic flight, was a conscious inspiration for the Ansari X Prize and the X Prize Foundation.  It seems amazing to me that groups of technologists spend much more than the value of a prize in claiming it.  I don't know if the challenge problem/prize paradigm is working or not, but there seem to be more and more of them, including on the machine learning side of things e.g. the DARPA Grand Challenge and upcoming Urban Challenge, the Netflix Prize, and the Spock Challenge. 

One prize out there in which LIDS could potentially play a role is the Archon Genomics X Prize.  Are there any "grand challenges" in LIDS areas of interest that should be supported with large prizes?  Is this paradigm effective?  Share your thoughts.  Leave comments.