On acceptance rates and flagship conferences

There's been a lot of back and forth on ways of increasing attendance at STOC, and in our wonderful theory way, all of this has happened in a universe unencumbered by the presentation of actual data.

I thought I'd dig up statistics on what exactly goes on at a number of major conferences in different areas in computer science. My idea was to take some of the major areas in the field, identify their flagship conference (or one of two as the case may be), and compile statistics on acceptance rates, attendance, and general conference activities.

The areas I considered (with main conference in parentheses) were

• databases (SIGMOD)
• machine learning (ICML)
• operating systems (SOSP)
• networking (SIGCOMM)
• architecture (ISCA)
• graphics (SIGGRAPH)

and the results I got were interesting (all data that I compiled can be found in this spreadsheet: feel free to add other areas, or update numbers, as you see fit). Where I could, I tried to get a sense of attendance/acceptance rates from either asking people or looking at published numbers for recent years: the ACM DL has acceptance rates for many of the above. Information on conference activities were taken from the most recent year I could get data for (usually 2010 or 2009). The main points:

1. All of the listed conferences had attendance in the 500-600 range (except ISCA with average attendance of 400, and SIGGRAPH with 2000+ in the research side). So they are definitely conferences with attendance that STOC would like to mimic. 
2. Acceptance rates varied, but most were below 20% (ICML being the exception at 25%). STOC is at 28% or so
3. Number of papers accepted varied widely (23 for SOSP, 150 for ICML). I find this particularly interesting: it would seem that attendance correlates more with the perception of being 'flagship' than the actual number of papers accepted.
4. Most conferences had long lists of colocated workshops. The smallest number was SIGCOMM last year with 5, and others had many more. STOC had none.
5. Tutorials were variable: some places had many (SIGGRAPH had 27) and some had none. STOC had 3.
6. With the exception of ISCA last year, all the conferences had significant poster sessions, either consisting of all papers accepted, or as a separate track with many posters. STOC had none.
7. The conferences all had other activities: demos, industrial tracks, works in progress or other such things (ISCA being the exception). STOC had none. 
8. Durations varied between 4 and 6 days (including the initial day). Most had 5. STOC is 4.

To me, there are two things that stand out from this.

1. The number of papers accepted does not appear to make a difference to the attendance. SOSP happens once every two years, and accepts 23-25 papers, and gets 500 attendees !! ICML gets a similar number of attendees with 150 papers accepted each year. 
2. There are a TON of activities at these conferences. Indeed, I think ICALP and ESA match them in terms of level of activity, but certainly not STOC. I've been a proponent of satellite events around a conference to increase attendance, and the STOC/EC/CCC colocation does seem to have helped. I'm also intrigued by the idea of colocating SoCG with STOC. 

You may draw your own conclusions...

p.s for the legions of readers who will start protesting that these communities are much larger than the theory community, I will merely point out that almost no one in this discussion thinks that the theory community is 300 strong: the question is more about getting the rather large theory community to show up in force for STOC.

Update:  Michael Mitzenmacher has a post up listing specific logistical issues that come up with expanding the set of activities at a conference. He points out that if we decide to go to multiple satellite events (whether as separate events or whatever), we'll have to adjust to a much greater degree of organizational commitment up front, as well no small amount of 'attitude adjustment'. For anyone who's ever attended a business meeting, this is a scary thought :)

The Shape of Shape Analysis Research, Part III

(a brief series on shape analysis: for earlier episodes, click here)

Shape matching research in computational geometry is fundamentally distance-based. In other words, we start with a distance function, and then design algorithms to compute it, or minimize it under transformations, or approximate it, and so on.

There's an important problem with this point of view. While computing the distance between two shapes is an important tool in shape analysis, it's not the only problem. Other equally important problems include:

• Finding a shape similar to a query shape
• Matching pieces of shapes together
• Organizing shapes into groups (i.e clustering)

And so the problem with the distance-based viewpoint is that all you get at the end is an abstract metric space. You can compute d(x,y) in an appropriate amount of time (maybe), but you lack all the additional structure needed to solve these other problems efficiently. With our modern knowledge of metric embeddings, it's always possible to ask if these distances can be embedded in a more tractable space, but it turns out for measures of interest (Hausdorff, Frechet, earthmover), this cannot be done without incurring huge errors.

The idea of shape spaces turns this process around. Rather than starting with the distance, and trying to find a space to embed it in, shape-space based methods start with a mapping that takes a shape to a single point in a (usually curved) space, and use an induced metric (usually some kind of geodesic) as the distance.

By at least one unsourced account, this view of shape dates back to Riemann, but the modern formulation of this approach started with David Kendall, in the 70s. His idea was extremely elegant.

Consider a collection of closed simply connected regions of the plane (the shapes), each shape described by k points on its boundary. Each of these points can be described by the two coordinates (x,y), which we will write as the complex number x+iy. By a shifting transformation,  we can ensure that the centroid of each shape lies at the origin. This loses one (complex) degree of freedom, yielding a k-1 dimensional complex vector.

Next, consider what it means to rotate the shape around the origin. In the complex plane, this corresponds to multiplying by the complex number z = exp(i theta). Doing the appropriate projective transformation, this means that we can identify a shape with a single point in k-2 dimensional complex projective space.
The distance between two shapes is now defined as the geodesic distance between two points in this space.

There are a few important points to note here:

1. Each shape of k points is mapped to a single point in a k-2 dimensional space.
2. All shapes are assumed to have the same number of points, which correspond across shapes. 
3. The space is constructed by quotienting the original representation (the k-dimensional complex vector) by the special orthogonal group.

This last point is particularly crucial: the invariance under transformations is folded directly into the representation, rather than being something to "solve" via minimization.

The general program outlined by Kendall (map shapes to points on a manifold quotiented by a suitable set of transformations) has led to many other constructions, among the more notable being Bookstein's shape space and the Michor-Mumford representation for planar closed curves invariant under diffeomorphisms (which bears a strong resemblance to a summed variant of the Frechet distance). These methods have (for reasons unknown to me) taken up residence primarily in the computer vision community.

A Critique.

There is much to like about the shape space approach to shape analysis. Fundamentally, by embedding shapes in a space with structure, it gives us both a distance measure and a geometry to play with, and this is invaluable. However, there are serious limitations to the ideas developed thus far.

• Computation: It's all very well to come up with a mathematically elegant formulation of a distance as a geodesic, but it's a lot harder to actually compute these distances. In practice, researchers often resort to heuristics with no guarantees beyond local convergence. To me, this is like building a beautiful mansion in a pit of mud: it's hard to get in and out with a lot of dirt and pain. 
• Scalability: the mathematical complexity also makes it harder to do scalable computations on shapes.
• Global vs local features: I'll have more to say about this later, but these approaches (generally speaking) construct a global signature for a shape, which limits one's ability to do partial matching. 
• Correspondences: The Kendall method at least requires explicit correspondences between points in each shape. Finding correspondences is one of the most annoying parts of shape analysis (and affect most methods for comparing shapes). 

Next: We examine the problem of hearing shape, or how the Laplacian starts to figure in. 

Rebooting how we publish in CS.

Dan Wallach has a thought-provoking proposal on how to reboot the CS publication process from the ground up. Read the entire proposal here.

Here's an edited version of a response I sent to him (short version: I like it !)

I think the time is ripe for this: it seems that people are getting more and more used to using the arxiv/iacr/eccc for tech reports and DBLP as a de facto list of papers, and even regularly subscribing to arxiv rss feeds to see what's new. bibref management systems like Mendeley/citeulike would also really benefit from this.


While (like others) I'm concerned about facilitating ranking schemes too much (I personally think the h-index is an abomination, but that's a different discussion), I think that even if the only outcome of this was to have a centralized single repository for CS publications, that in itself would be a major benefit.

I'm less sure about attention/reputation mechanisms though. It's clear that one of the challenges for researchers today is the 'eyeballs problem': how to get attention to your work amidst the sea of publications. While one might argue that Google and page-rank have done a good job of this, i think that over time it's become more and more top heavy, with a few locations acquiring sticky reputation and sucking in attention, and while this might be ok for general news, it's not so for research, where more often than not, good ideas can come from less "well known" sources.

I don't think CSPub causes any additional problems in this regard - but it would seem like much more thought is needed to design *transparent* ranking schemes. While google can do what they want with their ranking scheme, and keep it as a trade secret, a public service such as CSPub should try to keep ranking methods as transparent as possible. (hack-proof ranking methods ? I know there's research on this !)

It's over !!

Yes, by far the most stress-filled SoCG I've attended is now over. I'm hoping we didn't traumatize the attendees too badly.

I apologize for the lack of posts during the conference - I just didn't have enough time to compose intelligent thoughts about the talks that I actually did manage to attend, and even Bernard's metamorphosis into Steve Jobs (at least in talk style) went unremarked upon :).

There were lots of great talks though, and hopefully as I get more time, I'll be able to mention some of them.

The Shape of Shape Analysis Research: Part II

(a brief series on shape analysis: for earlier episodes, click here)

Shape analysis in the geometry community follows a fairly standard pattern. It goes something like this:

1. Fix class of shapes (points or curves, usually)
2. Define distance between two shapes
3. Minimize distance under transformations (rotations, translations, sometimes scaling)
4. Approximate distance if necessary
5. Study distance for special classes of shapes.

There are many distances that have been studied in this manner for point sets, including the bottleneck matching distance, the Hausdorff distance, the RMS matching distance and the earthmover distance. For curves, the list is much shorter. The Frechet distance is pretty much the only game in town, with a brief cameo by its first cousin, the dynamic time warping distance.

This process has brought forth a number of interesting ideas and tools - among them

• free space decompositions and equivalence classes of regions with respect to combinatorial structure in the solution (so you can enumerate solution types)
• how to approximate spaces of transformations via carefully chosen grids in order to get provable approximations for distance estimation
• connections between geometric matching and string matching via different kinds of hashing tricks.

I'd go as far as to argue that these tools are more important than the measures themselves, because of their applicability. 

But while shape matching is a rich area of research within CompGeom, it's less clear what influence this research has had in the larger shape analysis environment. Some of the obstacles (some self-inflicted, some not) are:

Definitions involving 'max' terms.
Combinatorially, it's easier to define distance measures where the distance is governed by a max over some quantity (usually a max distance over pairs of points). It's easier to define the space of possible solutions, and make the requisite combinatorial arguments. But such measures are highly non-robust, since any one 'outlier' can cause the distance measure to report a large distance.

This problem is usually fixed by introducing 'outlier-sensitive' variants of the measure under consideration, which leaves some combinatorial structure intact (at a price), or by replacing 'max' measures by 'sum' measures, which can often be inelegant, and usually destroys most of the algorithmic tools developed for the original case.

Reliance on the 'expensive exact, cheap approximate' framework.
This might require some explanation. Most of the above shape matching measures can be computed for two fixed shapes relatively easily. But if you have to compute them under transformation groups, things get hairy really quickly. Running times in the realm of n^7 or n^8 for point sets in three dimensions are not unusual.

What's worse though is the kind of impracticality involved in these algorithms (yes I know, n^7 doesn't need further beating, but still...). They usually involve finding intersections of surfaces defined by medium-to-high-degree polynomials, and then walking through the arrangements thus defined.

There's no way on God's green earth that anyone in their right mind will implement these algorithms, so we usually apply the standard bait-and-switch: "if you love these expensive exact methods, you're REALLY going to like our fast and tasty approximations !!". There have been some really creative tools designed to solve shape matching problems approximately, but what they often do is hide high complexity in terms involving the error epsilon, while looking well behaved in n.

It's difficult to overstate the depth and beauty that approximation methods bring to the field of computational geometry as a whole, and you should read Sariel's soon-to-be-book on this topic to learn more. But in the narrow realm of shape analysis, this two-step 'expensive exact, sort-of-cheap-approximation' has the following problems:

• Designing exact algorithms with humungous running times only confuses the people you might want to have use your algorithms. They'll just turn around and use some other measure. Coming along afterwards and saying, "but wait, we can APPROXIMATE IT" doesn't help, because no one's vested enough in the measure to even care at this point.
• Hiding expensive dependencies in the error term is problematic. Theoretically, it's a sound form of analysis - isolating the dependency from the dominant 'input size' term. But practically speaking, a bound that's cubic in 1/epsilon is not a whole lot better than a bound that's (say) quadratic in n, for reasonable values of epsilon. Which is to say, they're both terrible. You can of course protest that in practice things will work a lot better (and they often do!), but again, you've lost your audience, who wasn't really vested in the distance measure in the first place !

Missing the forest for the trees. 
This is an odd kind of objection to level at theoretical research. But here's the problem as I see it. If your focus is the primitive 'compute distance between two shapes', then you use that as the platform and layer on things like 'minimize under transformations; find near neighbors', and so on.

The problem is that this approach focuses on the 'tree' (the distance measure) while in my mind missing the 'forest': namely, the larger set of problems of shape analysis, of which computing the distance measure is but one. I'll develop this idea as I talk about other approaches to shape analysis - the point I want to make is that you have to view the particular distance measure between shapes in the context of  a large set of possible applications. A  measure that looks nice and
clean and well founded on its own may be less well suited for the rigors of supporting a class of analysis problems than a different measure that's maybe less elegant, but more flexible when seen in context.


A coda. 
I was discussing some of the issues here with someone, and I think a clarification is important here.

I'm not saying that people can or cannot work on studying whatever distance measures they want. There are all kinds of interesting geometric puzzles that have cropped up while studying shape matching (subquadratic algorithm for the Frechet distance?).

But when we look at the CompGeom shape matching literature through the lens of "Is this a way of designing the theoretical foundations of the larger shape analysis research program", then the above objections become more relevant.

In the next installment, I'll switch over to the line of shape analysis research that originated with David Kendall and others, and present a similar critique of that body of work.

Active learning modules for grad algorithms ?

Active learning (the pedagogy, not the area of machine learning) is all the rage in undergraduate education. My understanding of it (limited, btw) is that it involves much more active engagement with the students, and much less lecturing. This meshes nicely with new trends in teaching, since so much information is available on the web, and so the traditional 'stand at blackboard and scribble for an hour' model seems a little out of date.

My question here is: has anyone tried active engagement modules for topics in graduate algorithms ?  (which means topics like randomization, network flows, and a fast review of basic algorithmic primitives, with an emphasis on proof techniques). I've experimented with group activities for NP-hardness reductions (team students up in groups and have them pick problems out of a hat to prove NP-hard) with mixed results.

My class size is in the 40s-50s range, and has a mix of beginning grads and advanced undergrads, divided up into people taking it as a requirement, people taking it out of curiosity and those taking it to help ace their google/m$ interviews (no I'm not making this up - I did a poll)

Why double blind review occasionally annoys me.

1. Submit a paper to a conference that expects blind submissions
2. Resist the urge to place the paper on the arxiv, because of said blind submission policy, and the misguided belief that placing the paper online will violate the spirit of said policy
3. Watch as a stream of papers on conference topic magically appear on the arxiv.

bibtex style question

I have a BibTeX style hacking question, and am hoping the community at large can help me out.

Here's the problem: I have a set of names of authors. I wish to make two bibtex style files, such that

• In style file 1 (S1) any paper including someone in this set of authors will be rendered normally
• In style file 2 (S2) any paper including someone in this set of authors will be rendered with the author name underlined. 

My current hack was to do the following. I created two versions of a 'names.bib' file. In both files, the names are stored as @strings, and in the second version, the strings are encoded as underlined i.e using \underline{name}.

In my master bib file, the names are entered merely as the string value, so if I stored a name as

@string{me = "Suresh Venkat"}  or @string{me = "\underline{Suresh Venkat}"}

I merely enter the author name as

author = {..other names... # me # .. other names}

While this works, the problem is that bibtex doesn't know (obviously) that the string 'me' needs to be formatted as a name, and so I get ugliness like

"Author, A., Author, B., Suresh Venkat and Author, C. " 

in the final bbl instead of

"Author, A., Author, B., Venkat, S. and Author, C. "

 Now I didn't expect my solution to work, but I don't know what will. Any ideas ?

A (minor) conundrum when citing related work

Suppose you're writing a paper in which the three key prior results are A, B, C. Let's say that C is the most recent of the three, and discusses A and B. But C completely misrepresents the work of A and B, to the extent that it starts to undermine the very premise of C !

Now you have to discuss these prior papers: what do you do ? The conservative approach is to ignore the issue, and merely discuss A, B, and C correctly. If it starts sounding like C doesn't make any sense in the light of the correct rendering of A and B, then that's too bad.

But suppose it really bothers you that C got away with this ? Is it appropriate to mention C's misinterpretation (as politely as possible) or is it not worth it ? Would your answer be different if the paper were for a conference or for a journal ? Would the identity of the authors of C matter ? Should you just suck it up and take the high road ?

Avner Magen

As has been announced by Lance and Mihai, Avner Magen just died in a climbing accident in Alaska (there's a memorial blog set up in his name).

I didn't know Avner personally, but I've "met" him through a few of his papers. Among the many things he did were some very nice early results in the theory of metric embeddings. With Nati Linial and Michael Saks, he showed how to embed trees into Euclidean metrics with low (O(log log n)) distortion. And in a later result, he showed how to do JL-style embeddings that preserved not only distances, but also higher order volumes (improvements here)

This last result has been of particular interest in some of the work I've been doing of late - we've been interested in arc-length preserving embeddings that relate to volume preservation, and I've also had a student looking at some near neighbor problems for higher dimensional objects.

It's very sad to read such recent works and know that the person who wrote them is no more. My condolences to his family and friends.

Summer Seminars

Jared Saia at UNM and Machinations is working through Wilf's generatingfunctionology over the summer with his students. He says,

During the summer theory seminar for my research group, I like to cover a topic that is mathematically challenging, but not something that any of us would normally learn about in the course of our day-to-day research

This is a great idea ! Usually, during the semester, I'm in market-driven mode, choosing topics that are more accessible, and are likely to draw a larger audience. But summer is a good time for harder material since you have smaller self-selected group and they're motivated.

Last summer I ran a "why can't we solve P vs NP" seminar with three students - we went through the standard obstacles, and along the way learnt a fair amount of complexity theory - it was a lot of fun. This summer we're doing lattice theory - I have selfish reasons for choosing this topic (some of my recent work needs it), and it's a very accessible (and relevant!) area, while still being nontrivial enough to get students to think.

We considered a number of other topics as well before settling on this one - we might even return to some of them later. They were, in no particular order.

• algorithmic game theory (from this book)
• concentration inequalities for random variables]
• quantum computing (possibly from these notes)
• complexity theory fundamentals (almost surely from Luca Trevisan's ongoing class)
• geometric flip theory (mulmuley's work on P vs NP). I suspect we'd go with this paper and these videos (and the associated reading material)
• A complexity series: the unique games conjecture, quantum computations as shortest paths and classical and quantum lower bounds + QIP=PSPACE) 
• Fourier methods for boolean function analysis
• Geometric Approximations (full book) 

Especially for a summer seminar, it's important to have material that's generally available for free, since students might not want to purchase a book for a topic that's off the beaten track. 

ICS 2011

Bernard highlights the 2nd incarnation of ICS, to be held again in Beijing between Jan 7-9, 2011.

What's newsworthy is the shifted submission deadline. Last year, the ICS submit-accept cycle was highly compressed, to make sure it didn't clash with either SODA or STOC. This year, it's in direct conflict with SODA (submission deadline Aug 2), which should make things interesting for the SODA submission levels.

Since the conference is still in some flux (I don't know where it will be next year), it's probably too soon to comment on the timing/deadlines, but I wonder whether it will continue to be a good idea to have SODA and ICS be in direct conflict.

Loading Image

Click anywhere to cancel

Image is Unavailable

SoCG 2010 Room block rate

Hi all
  this is a reminder that SoCG 2010 room block rates at both the Cliff Lodge and the Inn at Snowbird will expire on May 23, so make sure to make your reservations on time. 

If only they had given me an igNobel ...

Via Jeff Erickson (though I'm pretty sure I shouldn't be thanking him for this), my absurd research: http://bit.ly/d2CGJH

Although my wife is more impressed with this than
with any of my other papers ...

Choosing the number of clusters III: Phase Transitions

(this is part of an occasional series of essays on clustering: for all posts in this topic, click here)

We've seen two generic methods for determining the number of clusters in a data set thus far: the elbow method, and the ROC-curve/diminishing returns method. Now I want to talk about a more "dynamic" approach to identifying the number of clusters in a data set.

These ideas center around a 'simulated annealing' view of the clustering process. Imagine, if you will, a set of highly excited atoms all bouncing around in a state in which all are indistinguishable. If you now start cooling the atoms, they will start falling into local energy traps over time. If the cooling is done on the right schedule, the atoms will find a minimum energy configuration at each temperature, all the way down to absolute zero, where each atom is in its "own state", so to speak.

What does this have to do with clustering ?

The setup works something like this. Imagine a "soft" clustering assignment of points to clusters (where each point assigns a fraction of its membership to each cluster). We can write down the distortion D associated with this clustering by computing the weighted distance of each point from the various cluster centers. We'd also like the clustering to be more or less deterministic, so we can introduce a penalty team for the level of disorder in the clustering (usually captured by the conditional entropy H associated with the assignments of points to clusters).

Now we want to minimize the distortion subject to some constraint on the entropy, so in good old Lagrangian form, we write down a function of the form

F = D - TH

where T is a Lagrange parameter and F is the overall function to be minimized.

But here's the kicker. You can think of F as the free energy of a statistical ensemble, where D represents its energy, and H represents its entropy, and T is the "temperature" of the system. The T=0 limit captures the idea that distortion is all that matters, and so each point is assigned a cluster of its own. The "T large" limit prioritizes the entropy over the distortion, encouraging us to place all points in a single cluster.

So the annealing process corresponds to minimizing F while decreasing T steadily. It turns out, using magic from the realm of statistical physics, that for any temperature T, the probability of assigning point x to cluster y is proportional to exp(-d(x,y)/T), and as T decreases, the probability of assigning a point to any cluster except the very nearest one decreases dramatically.

All of this is very fascinating, and provides a "smooth landscape" in which to understand how points get assigned to (soft) clusters. Much of the work I'm exploring right now is in trying to understand the space of soft clusterings of data. But that's a digression.

What's really interesting is that if you look at the evolution of the probabilistic assignments, you start seeing phase transitions. As T starts off high, all the points are in the same cluster. At a specific temperature T, a phase transition occurs, and the data starts splitting (based on the assignments) into more than one cluster.

How can you tell when this happens ? Here's a very elegant technique, first proposed by Kenneth Rose in his work on deterministic annealing. In the high-T regime, where every point is in the same cluster, the cluster center location can be computed by solving a simple convex optimization. As the process evolves, the positive definite matrix defining the optimization starts losing its positive definiteness, till some point when one of its eigenvalues goes to zero. This point can be computed analytically, and yields a specific temperature value at which the first clusters start to emerge.

Kenneth Rose has some nice examples illustrating this behaviour. As time goes one, more and more phase transitions start to appear, as more and more clusters start to emerge. What you end up with is a hierarchy of clusterings that end with the trivial clustering where all data lie in separate clusters.

This idea has been developed further with the information bottleneck method, which replaces both the distortion and entropy terms by terms involving the mutual information of the assignments. The free energy paradigm works the same way, although now the phase transition points can't be computed analytically (I'll have more to say about the information bottleneck method)

What's entirely weird is that the phase transitions still happen (and I want to stress this point), data sets will split up into different numbers of clusters at the same transition point ! We wrote a paper a few years ago that proposes a particular "temperature" to look for phase transitions in, and lo and behold, we were able to recover the "correct" number of clusters from planted data sets by watching the data split at this point. I'm still not sure why this happens, but it was quite interesting, and yielded one way of identifying "natural clusters" in the data.


Phase transitions and the like are the coin of the realm in bifurcation theory. While a proper understanding of this area is well beyond my skill level, there has been recent work on trying to analyze the information bottleneck from a bifurcation theory perspective, specifically by trying to isolate and classify the different kinds of critical points that emerge in a bifurcation diagram of the clusters as the temperature changes. Albert Parker of the University of Montana wrote a Ph.D thesis on this topic, and I'd love to understand his work better.

Coming up next: Clustering as compression - the information bottleneck and kolmogorov complexity.

The Shape of Shape Analysis Research: Part I

Shape analysis is a topic that is almost a killer app for computational geometry. Where the word 'almost' comes in is an interesting story about the tension between computational power and mathematical elegance.

Shape analysis is defined by the generic problem:

Given two (or more) shapes, determine whether they are similar.

Simple, no ? I don't need to list the applications for this problem. Or maybe I should: computer vision, computational biology, graphics, imaging, statistics, computer-aided design, and so many more.

It would not be an exaggeration to say that in many ways, shape analysis is as fundamental a problem as clustering. It's a problem that people have been studying for a very long time (I heard a rumor that Riemann once speculated on the manifold structure of shapes). Especially in the realm of biology, shape analysis is not merely a way to organize biological structures like proteins: it's a critical part of thinking about their very function.

Like any problem of such richness and depth, shape analysis has spawned its own ecology of concepts. You have the distances, the transformation groups, the problem frameworks, the feature representations, the algorithms, and the databases. You now even have the large data sets of very large shapes, and this brings nontrivial computational issues to the forefront.

Shape analysis (or shape matching) has been a core part of the computational geometry problem base for a long time. I've seen papers on point pattern matching from the late 70s. There's been a steady stream of work all through the past 30 years, introducing new concepts, distances and algorithm design principles.

In parallel, and mostly within the computer vision community, there have been other efforts, focused mainly on designing more and more elegant distance measures. Computer graphics got in on the action more recently as well, with a focus on different kinds of  measures and problems.

What I think is unfortunate (and this is entirely my own opinion) is that there's a strong disconnect between the developments happening in the computational geometry community, and the parallel efforts in the more 'applied' communities.

I'm not merely talking about lack of awareness of results and ideas. I believe there are fundamentally different ways in which people go about attacking the problems of shape analysis, and I think all sides could benefit greatly from understanding the strengths of the others.

Specifically, I think that within our community, we've focused for far too long on measures that are easy to define and relatively easy to compute (while not being trivial to work with). On the more 'math/vision' side, researchers have focused much more on measures that have the 'right' kind of mathematical structures, but have bailed miserably on computational aspects.

Over the next post or two, I want to develop this argument further, and hopefully end with a set of problems that I think are worthy of study both from their intrinsic appeal and the unsolved computational issues they present.

Stay tuned....

p.s The clustering series will also continue shortly. Oh do I love summer :)

Loading Image

Click anywhere to cancel

Image is Unavailable

SoCG 2010: Come one, come all :)

There's about a month left to go for SoCG, and I just returned from a walk through at Snowbird. Surprisingly, it was still snowing - the ski season has wound down though. Most of the snow will disappear by early June - we're seeing the last confused weather oscillations right now before the steady increase in temperature.

We went up there to check out the layout of the room(s) for the conference - the main conference room is nice and large, and the parallel session room is pretty big as well, there'll be wireless access throughout (with a code), and there's a coffee place right next to the rooms. There are nice balconies all around, and of course you can wander around outside as well.

Registrations have been trickling in, a little slower than my (increasingly) gray hair would like. If you haven't yet registered, consider this a gentle reminder :). It helps to have accurate numbers when estimating food quantities and number of proceedings etc.

See you all in a month !

Hirsch Conjecture disproved

Via polybot, Gil Kalai posts that Francisco Santos has disproved the Hirsch Conjecture. This is big news.

The conjecture:

the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d.

The result:

I will describe the construction of a 43-dimensional polytope with 86 facets and diameter bigger than 43. The proof is based on a generalization of the d-step theorem of Klee and Walkup.

The proof will be presented at the 100 Years in Seattle (The mathematics of Klee and Grunbaum) conference in end-July, this year. 

Future-proofing research

Every now and then, we get called upon to project our work into the future. Usually, it's in a grant proposal (especially in a CAREER proposal). Sometimes it might be part of strategic planning at a faculty retreat. It even shows up in solicitations for position papers at various venues (for example this recent one that was circulating on a faculty list). It definitely comes up at faculty interviews, although I usually view it as a hazing ritual or the equivalent of "Nice weather we're having, aren't we?"

I understand the short-term imperative for such things: it's good to know that there are timelines in which your work has some kind of measurable impact, and even better to know that there's more than one (BPP vs NP, anyone?).

But I get the sense (and maybe I'm just off base here) that this kind of future prediction business is more common in non-theoryCS areas. My archetypical story for what happens if you ask theoreticians about future directions is Jeff Erickson's hilarious tale about his interview at MIT.

Of course the most famous example of future projection is in mathematics ! So maybe my premise is doomed ? But somehow I don't think so. I don't think mathematicians since Hilbert go around proposing future directions for entire areas (although there might be general consensus on key open problems), and I think theoryCS has absorbed much of this ethos (although I don't think that's true in theoretical physics).

I ask because I always feel awkward when asked questions like "where is going in the next X years ?" or even worse, "where SHOULD be going in the next X years". Maybe the more reasonable question is "where's all the activity and ferment happening right now". 

Loading Image

Click anywhere to cancel

Image is Unavailable

Loading Image

Click anywhere to cancel

Image is Unavailable

Ranking departments topologically rather than totally.

The US news rankings came out a while back (Jon Katz had two posts on this). As usual, this will prompt a round of either back-slapping or back-stabbing, depending on whether your department ranking went up or down (ours didn't change at all, which could also be a bad thing).

What I'd like to propose is a completely different way of doing rankings.

It's generally accepted that the place where rankings make the most difference is in graduate admissions, and there's a secondary effect in faculty hiring (since faculty want to get good students to work with). The general belief is that students will tiebreak between universities based on ranking, in the absence of more contextual information.

But it's also insanely silly to obsess about the relative rankings of (say) the top 5 schools, or to exult in your movement from 53 to 47 in the rankings. What I believe is generally true is that there are rough strata (antichains in a partial order, if you will) in which departments are generally of equivalent rank. Spending time and energy trying to optimize within such a statum is a useless waste (which doesn't mean that people don't LOVE to do it, because any activity is positive activity, right ? ... right ? ....)

What we do keep track of, and is interesting, is which universities our admits reject us for, or accept us in place of. If I'm not Stanford or MIT, but students are rejecting me only to go there, then I'm not happy, but I feel minor relief that at least they're not rejecting me for the University of Obscurity in Scarceville, Podunkistan.

But of course we know what this is ! it's a topological order ! So I propose the following tiering scheme:

A department is at tier k if "all" departments it is rejected for are at tier k-1 or less. 

Note 1: We have to define "all" carefully - there's always someone who's (say) following a boyfriend or girlfriend, or really wants to live in some town, etc etc. My preferred definition of "all" would be "at least 80%" or some large figure like that.

Note 2: If in fact people did select universities based on the "current" ranking scheme, this order would reflect that. Of course I don't believe this will happen

Note 3: This might even allow for more fine grained analysis based on subject area. Depending on the areas of the admitted students, one could create stratified orders by area.

Note 4: No I have no clue how to get this data, but many departments informally maintain this information (I know we try to get this info when we can), and it's not like the current approach is dripping with rigor anyway.

Note 5: If you're an administrator, you'll hate this when you're trying to move to a higher level, and you'll love it when you actuall make the move. The problem with the lack of granularity might annoy some people though.

Metrics on distributions defined over metric spaces

Now that's a title to make your head spin !

Semester is over, which means I hope to get back into blogging form again, picking up my clustering series where it left off, and also starting some new rants on problems in shape matching (which more and more to me look like problems in clustering).

But for today, just a little something to ponder. The following situation often occurs in data analysis. You have some data that inhabits a metric space - usually Euclidean space, but that doesn't really matter. You also have distributions over the data, by which I mean some kind of weight vector with one "component" for each data point, and components summing to one. The goal now is to compare these weight vectors in a way that takes into account the structure of the space.

The standard construction that one uses here is the earthmover distance, also known as the Wasserstein distance, or the Monge-Kantorovich distance, or the Mallows distance, or the transportation metric (you pick your favorite one). It's very intuitive (which is probably why it's been invented so many times) and works like this. Imagine piles of earth at each data point, with each pile having mass equalling the weight at that point. We have a "starting configuration" consisting of the first weight vector, and an "ending configuration" consisting of the second weight vector. The goal is to figure out how to "transport" the earth with minimum effort (effort = weight X distance moved) so that the first configuration becomes the second. Formally, this amounts to a generalized matching problem that can be solved via the Hungarian algorithm. The earthmover distance is very popular in computer vision (see the Wikipedia article for details)

Another metric over distributions of the kind above is the Levy-Prokhorov metric, which for two distributions u and v is defined as the smallest e such that on any neighborhood A, the measure of u is within e of the measure of v on A inflated by e (i.e by constructing a ball of size e around A), and vice versa. I haven't seen this metric used much in practice, and it seems hard to compute.

Another approach that I realized recently uses a method that thus far has been used only in shape analysis. I've been working with a shape matching measure called the current distance of late (more on this in another post - it's a fascinating measure). Roughly speaking, it works like this. It starts with a "shape" defined anyway you like (clouds of points, a curve, a surface, whatever), and a similarity function (a positive definite kernel actually) defined on this space. It then allows you to compare these shapes by using the kernel to create a "global signature" that lifts each shape to a point in a Hilbert space, where the induced distance captures the shape distance.

It also works with weighted point sets, which is the relevant point here. Suppose I give you a space with distance defined indirectly via a kernel similarity function (rather than via a distance function). The current distance then gives me a way of comparing distributions over this shape just like the above measures, and the kicker is that this approach is WAY more efficient then any of the above methods, taking near-linear time instead of needing the rather expensive Hungarian algorithm. Moreover, the current distance has a built-in isometric embedding into a Hilbert space, something the earthmover distance cannot have.

If you're curious for more details, wait for my post on the current distance - in the mean time, there are two papers we've written (one online, the other you should email me for) that explore the theory and practice behind the current distance. I'm curious now as to whether the current distance can be used an efficient replacement for the earthmover distance in applications that rely on the EMD, but don't have a natural relationship to shape analysis.

p.s Shape matching in particular, and data analysis in general, is a rich source of ever more exotic metric spaces. I've been working with a number of these, especially in non-Euclidean spaces, and there are lots of interesting algorithms questions here.

SoCG 2010 Early Registration Deadine

SoCG 2010 Early Registration deadline coming up tomorrow night. Make sure you register so you don't pay the full price. Also make sure to lock down your hotel reservations.

SoCG 2010 News

There's been a flurry of activity on the SoCG 2010 front, and while I've been running around getting things done, I haven't been diligent enough about announcing the activity here. 

1. The registration site is up and running, as has been noted. The deadline for early registration is May 2, so hurry up and get those registrations in ! The earlier you register, the easier it is for us to do our planning for conference activities.
2. You can (and should) reserve your hotel rooms at the same time. We have a group block rate at both the Cliff Lodge and the Lodge, (students can share rooms at the latter) and the block will expire in the middle of May. Snowbird is up in the mountains, and so if you plan on reserving a hotel room elsewhere, you'l need to arrange to get yourself up the mountain - not hard, but something to plan for. 
3. MADALGO is running a second installment of the very successful MASSIVE workshop on massive data algorithmics. This will be held on June 17, the day after SoCG ends, and so make sure to reserve an extended hotel stay if you plan on staying over. The group block applies through MASSIVE. Moreover, the deadline for submissions is Apr 14, so get those papers ready !
4. We've arranged a group discount rate for shuttles to and from the airport to Snowbird. If you click on the Travel section of the conference website, the last link will take you to a PDF form that you can use to reserve the discounted shuttle ($29 each way). Make sure to mention the group name (SoCG 2010) and group number (6922) if you call in a reservation.
5. The final program is available on the website. Some unusual elements worth noting: 
• There's a long break for a hike on Tuesday. The plan (and hope) is to make our way up the mountain for some spectacular views of the valley. 
• The conference ends relatively early on Wednesday (4pm) if you want to make a quick dash home. But of course you won't, because you'll be staying for MASSIVE !
6. If you need a letter of invitation for visa processing, send me an email with your full name and address, and title(s) of the papers/videos you'll be presenting. I can generate the letters pretty quickly, but I do need this information.