Learning with Orderings

NIPS 2009 Workshop,
Hilton Whistler Resort: Diamond Head,
Saturday, December 12, 2009

Organizers: Tiberio Caetano, NICTA
Carlos Guestrin, CMU
Jonathan Huang, CMU
Guy Lebanon, Georgia Tech
Risi Kondor, Caltech
Marina Meila, UW
Contact: jch1@cs.cmu.edu

Motivation and Goals

Permutations and partial orders as input and output data are ubiquitous. Examples include:

A general and effective way to handle ordered sets of items is to assign each item a score computed from its features. Scoring effectively maps the items onto the real line or another Euclidean space, where standard learning algorithms and other operations apply. While this approach has often worked, we believe that much can be gained by directly building statistical models and learning algorithms on the discrete combinatorial spaces themselves. It is to forward this direction of research that we propose this workshop.

We propose to accomplish:

Related NIPS workshop: Advances in Ranking

There is a related workshop at NIPS this year titled Advances in Ranking; we encourage all participants of our workshop to attend this workshop as well (which takes place the previous day). The Advances in Ranking workshop hopes to bring together a broad spectrum of researchers from the statistical, mathematical, CS and machine learning disciplines, to facilitate interaction and fruitful exchange between the groups on a wide variety of ranking problems. The Learning with Orderings workshop approaches the problem of ranking and learning permutations by constructing statistical models and algorithms on the underlying combinatorial spaces.

Please note that submissions should be directed to only one workshop; dual submissions between the two workshops are not allowed. If a submission cannot be accommodated by one workshop, it may be forwarded to the other workshop for consideration; please indicate if you would like us to consider this. Details of the submission process can be found here.

Call for abstracts

The workshop will include a combined poster/demo session. We invite participants to submit 2-page extended abstracts (NIPS format) to LearningWithOrderings@gmail.com describing the technical content of proposed posters and computer demos. The submission deadline is November 9. The review process will be coordinated with the "Advances in Ranking" workshop. Please do not submit the same work to both workshops.

Our Target Audience


This one day workshop will have 9 invited talks from experts in the field (including a keynote lecture), as well as a poster/demonstration at the end. Each talk will be 20 minutes long with 5 minutes for questions and discussion. The keynote is 45 minutes long with 5 minutes. The day is split into two sessions (one in the morning, one in the afternoon) and there will be a coffee break in each session during which we encourage participants to engage in further discussion.

Learning with Orderings Workshop Schedule
Time Duration Title/Abstract (and Slides) Speaker
7:30 - 7:55 25 Min. Ranking in the algebra of the symmetric group [abstract] Risi Kondor (Caltech)
7:55 - 8:20 25 Min. Stable Identification of Cliques with Restricted Sensing [abstract] [slides] Xiaoye Jiang (Stanford)
8:20 - 8:45 25 Min. Clustering ranked preference data using sociodemographic covariates [abstract] [slides] Brendan Murphy (UCD)
8:45 - 9:10 25 Min. Dirichlet Process Mixtures of Generalized Mallows Models [abstract] [slides] Marina Meila (UW)
9:10 - 9:30 20 Min.

Coffee Break

9:30 - 9:55 25 Min. Discovering and exploiting riffled independence relations in ranked data [abstract] [slides] Jonathan Huang (CMU)
9:55 - 10:45 50 Min. Projection Pursuit for Discrete Data [abstract] Persi Diaconis (Stanford)

- Ski Break -

3:30 - 3:35 25 Min. Visualizing Spatial Proximity of Search Algorithms [abstract] [slides] Guy Lebanon (Georgia Tech)
3:55 - 4:20 25 Min. Content Modeling Using Latent Permutations [abstract] Harr Chen (MIT)
4:20 - 4:45 25 Min. Learning permutations with exponential weights [abstract] Manfred Warmuth (UCSC)
4:45 - 5:10 25 Min. Exact Inference in Graphical Models: is There More to it? [abstract] [slides] Tiberio Caetano (NICTA)
5:10 - 5:30 20 Min.

Coffee Break

5:30 - 5:55 25 Min. 5 minute poster spotlights
5:55 - 6:30 35 Min. Posters/Demonstration session [abstracts]

Contributed poster abstracts

Workshop Funding


  1. Aggregation of partial rankings, p-rakings and top-m lists,
    Nir Ailon,
    Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms,
    New Orleans, Louisiana 2007.
  2. Learning Graph Matching,
    Tiberio S. Caetano, Julian J. McAuley, Li Cheng, Quoc V. Le, Alex J. Smola,
    IEEE Transactions on Pattern Analysis and Machine Intelligence
    Volume 31, No. 6, pp 1048-1058, 2009.
  3. Betting on permutations,
    Yiling Chen, Lance Fortnow, Evdokia Nikolova, David Pennock,
    Proceedings of the 8th ACM conference on Electronic commerce,
    San Diego, Califonia, 2007.
  4. Group representations in probability and statistics,
    Persi Diaconis,
    Institute of Mathematical Statistics, 1988.
  5. A Latent Space Model for Rank Data,
    Claire Gormley, Brendan Murphy,
    In International Conference on Machine Learning (ICML 2006),
    Pittsburgh, Pennsylvania, 2006.
  6. Bayesian inference for Plackett-Luce ranking model,
    John Guiver, Edward Snelson,
    In International Conference on Machine Learning (ICML 2009),
    Montreal, Canada, 2009.
  7. Learning permutations with exponential weights,
    David Helmbold, Manfred Warmuth,
    In the 20th annual Conference on Learning Theory (COLT 2007),
    San Diego, California, June 2007.
  8. Riffled Independence for Ranked Data,
    Jonathan Huang, Carlos Guestrin
    In Advances in Neural Information Processing Systems (NIPS 2009),
    Vancouver, Canada, December 2009.
  9. Fourier Theoretic Probabilistic Inference over Permutations ,
    Jonathan Huang, Carlos Guestrin, Leonidas Guibas.
    Journal of Machine Learning (JMLR), Volume 10
    pp. 997-1070, May 2009.
  10. Exploiting Probabilistic Independence for Permutations ,
    Jonathan Huang, Carlos Guestrin, Xiaoye Jiang, Leonidas Guibas,
    In Artificial Intelligence and Statistics (AISTATS 2009)
    Clearwater Beach, Florida USA, April 2009.
  11. Efficient Inference for Distributions on Permutations ,
    Jonathan Huang, Carlos Guestrin, Leonidas Guibas,
    In Advances in Neural Information Processing Systems (NIPS 2007),
    Vancouver, Canada, December 2007.
  12. Inferring Rankings Under Constrained Sensing,
    Srikanth Jagabathula, Devavrat Shah,
    In Advances in Neural Information Processing Systems (NIPS 2008),
    Vancouver, Canada, December 2008.
  13. Multi-Object Tracking with Representations of the Symmetric Group,
    Risi Kondor, Andrew Howard, Tony Jebara,
    In Artificial Intelligence and Statistics (AISTATS 2007)
    San Juan, Puerto Rico, April 2007.
  14. The skew spectrum of graphs,
    Risi Kondor, Karsten Borgwardt,
    In International Conference on Machine Learning (ICML 2008)
    Helsinki, Finland, June 2008.
  15. The graphlet spectrum,
    Risi Kondor, Nino Shervashidze, Karsten Borgwardt,
    In International Conference on Machine Learning (ICML 2009)
    Montreal, Canada, June 2009.
  16. Snob: a C++ library for fast Fourier transforms on the symmetric group,
    Risi Kondor,
  17. Cranking: Combining Rankings using Conditional Models on Permutations,
    Guy Lebanon, John Lafferty,
    In International Conference on Machine Learning (ICML 2002),
    Sydney, Australia, July 2002.
  18. Non-parametric Modeling of Partially Ranked Data,
    Guy Lebanon, Yi Mao,
    Journal of Machine Learning Research
    Volume 9(Oct):2401-2429, 2008.
  19. Estimation and clustering with infinite rankings,
    Marina Meila, Le Bao,
    Proceedings of the 24-th Conference on Uncertainty in Artificial Intelligence (UAI 2008),
    Helsinki, Finland, 2008.
  20. Consensus ranking under the exponential model,
    Marina Meila, Kapil Phadnis, Arthur Patterson, Jeff Bilmes,
    UW Statistics Department Technical Report 515
    April 1, 2007
  21. Exponential Family Graph Matching and Ranking,
    James Petterson, Tiberio Caetano, Julian McAuley, Jin Yu,
    In Advances in Neural Information Processing Systems (NIPS 2009),
    Vancouver, Canada, December 2009.