Permutations and partial orders as input and output data are ubiquitous. Examples include:
Preference elicitation
Social choice and voting theory
Ranking and search.
Tracking and identity management
Structure learning for Bayesian networks
Multi-way classification and other categorization tasks
Natural language processing
Graph matching
... and many others!
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:
Compact representations:
What parametrizations for permutations and partial orders
exist and what are their respective advantages? What are `good'
parametrizations for subclasses of partial orders that are common
in practice (e.g posets of bounded height, ratings, top-t orderings)?
Algorithms:
Poset classes are rich classes (superexponential) which do not
naturally admit low dimensional embeddings. Most estimation algorithms
over the space of permutation have theoretically exponential or larger
running times; other classes of algorithms are polynomial, but of high
degree (see e.g. group theoretical algorithms). What structure can
one impose on posets in order to achieve compact representations that
can be learned efficiently? What are the most effective approximate
and heuristic algorithms?
Learning theory for discrete parameters:
Statistical models on permutations and posets have both continuous
and discrete parameters, like the central permutation in consensus
ranking. How can one formulate and obtain standard theoretical
guarantees of learnability: like generalization bounds, consistency,
confidence intervals in such combined discrete-continuous spaces?
Dissemination:
Inform the larger NIPS audience on the progress and possibilities
in learning with orderings: what data can be advantageously modeled as
posets? What algorithmic solutions exist? What software implementations
are available?
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
NIPS community
Mathematicians, statisticians, combinatorialists
Application people in computer vision, natural language processing, etc...
Schedule
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
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.
Spectral Analysis for Partially Ranked Data
[abstract]
Dan Rockmore (Dartmouth)
8:20 - 8:45
25 Min.
Clustering ranked preference data using sociodemographic covariates
[abstract]
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.
Betting on permutations,
Yiling Chen, Lance Fortnow, Evdokia Nikolova, David Pennock,
Proceedings of the 8th ACM conference on Electronic commerce,
San Diego, Califonia, 2007.
A Latent Space Model for Rank Data,
Claire Gormley, Brendan Murphy,
In International Conference on Machine Learning (ICML 2006),
Pittsburgh, Pennsylvania, 2006.
Riffled Independence for Ranked Data,
Jonathan Huang, Carlos Guestrin
In Advances in Neural Information Processing Systems (NIPS 2009),
Vancouver, Canada, December 2009.
Inferring Rankings Under Constrained Sensing,
Srikanth Jagabathula, Devavrat Shah,
In Advances in Neural Information Processing Systems (NIPS 2008),
Vancouver, Canada, December 2008.
The skew spectrum of graphs,
Risi Kondor, Karsten Borgwardt,
In International Conference on Machine Learning (ICML 2008)
Helsinki, Finland, June 2008.
The graphlet spectrum,
Risi Kondor, Nino Shervashidze, Karsten Borgwardt,
In International Conference on Machine Learning (ICML 2009)
Montreal, Canada, June 2009.
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.
