Timezone: »
Representing distributions over permutations can be a daunting task due to the fact that the number of permutations of n objects scales factorially in n. One recent way that has been used to reduce storage complexity has been to exploit probabilistic independence, but as we argue, full independence assumptions impose strong sparsity constraints on distributions and are unsuitable for modeling rankings. We identify a novel class of independence structures, called riffled independence, which encompasses a more expressive family of distributions while retaining many of the properties necessary for performing efficient inference and reducing sample complexity. In riffled independence, one draws two permutations independently, then performs the riffle shuffle, common in card games, to combine the two permutations to form a single permutation. In ranking, riffled independence corresponds to ranking disjoint sets of objects independently, then interleaving those rankings. We provide a formal introduction and present algorithms for using riffled independence within Fourier-theoretic frameworks which have been explored by a number of recent papers.
Author Information
Jonathan Huang (google.com)
Carlos Guestrin (Apple & University of Washington)
Related Events (a corresponding poster, oral, or spotlight)
-
2009 Spotlight: Riffled Independence for Ranked Data »
Wed. Dec 9th 01:22 -- 01:23 AM Room
More from the Same Authors
-
2021 : Feedforward Omnimatte »
Sharon Zhang · Jonathan Huang · Vivek Rathod -
2018 Poster: Learning to Optimize Tensor Programs »
Tianqi Chen · Lianmin Zheng · Eddie Yan · Ziheng Jiang · Thierry Moreau · Luis Ceze · Carlos Guestrin · Arvind Krishnamurthy -
2018 Spotlight: Learning to Optimize Tensor Programs »
Tianqi Chen · Lianmin Zheng · Eddie Yan · Ziheng Jiang · Thierry Moreau · Luis Ceze · Carlos Guestrin · Arvind Krishnamurthy -
2018 Poster: Training Deep Models Faster with Robust, Approximate Importance Sampling »
Tyler Johnson · Carlos Guestrin -
2016 : Invited talk, Carlos Guestrin »
Carlos Guestrin -
2016 Poster: Unified Methods for Exploiting Piecewise Linear Structure in Convex Optimization »
Tyler Johnson · Carlos Guestrin -
2015 Poster: Deep Knowledge Tracing »
Chris Piech · Jonathan Bassen · Jonathan Huang · Surya Ganguli · Mehran Sahami · Leonidas Guibas · Jascha Sohl-Dickstein -
2014 Poster: Divide-and-Conquer Learning by Anchoring a Conical Hull »
Tianyi Zhou · Jeffrey A Bilmes · Carlos Guestrin -
2013 Workshop: Data Driven Education »
Jonathan Huang · Sumit Basu · Kalyan Veeramachaneni -
2013 Demonstration: Codewebs: a Pedagogical Search Engine for Code Submissions to a MOOC »
Jonathan Huang · Chris Piech · Andy Nguyen · Leonidas Guibas -
2012 Poster: Probabilistic Event Cascades for Alzheimer's disease »
Jonathan Huang · Daniel C Alexander -
2012 Demonstration: GraphLab: A Framework For Machine Learning in the Cloud »
Yucheng Low · Haijie Gu · Carlos Guestrin -
2011 Workshop: Big Learning: Algorithms, Systems, and Tools for Learning at Scale »
Joseph E Gonzalez · Sameer Singh · Graham Taylor · James Bergstra · Alice Zheng · Misha Bilenko · Yucheng Low · Yoshua Bengio · Michael Franklin · Carlos Guestrin · Andrew McCallum · Alexander Smola · Michael Jordan · Sugato Basu -
2011 Poster: Linear Submodular Bandits and their Application to Diversified Retrieval »
Yisong Yue · Carlos Guestrin -
2010 Poster: Evidence-Specific Structures for Rich Tractable CRFs »
Anton Chechetka · Carlos Guestrin -
2010 Poster: Inference with Multivariate Heavy-Tails in Linear Models »
Danny Bickson · Carlos Guestrin -
2009 Workshop: Learning with Orderings »
Tiberio Caetano · Carlos Guestrin · Jonathan Huang · Risi Kondor · Guy Lebanon · Marina Meila -
2009 Workshop: Large-Scale Machine Learning: Parallelism and Massive Datasets »
Alexander Gray · Arthur Gretton · Alexander Smola · Joseph E Gonzalez · Carlos Guestrin -
2007 Oral: Efficient Inference forDistributions on Permutations »
Jonathan Huang · Carlos Guestrin · Leonidas Guibas -
2007 Poster: Efficient Inference forDistributions on Permutations »
Jonathan Huang · Carlos Guestrin · Leonidas Guibas -
2007 Spotlight: Selecting Observations against Adversarial Objectives »
Andreas Krause · H. Brendan McMahan · Carlos Guestrin · Anupam Gupta -
2007 Poster: Selecting Observations against Adversarial Objectives »
Andreas Krause · H. Brendan McMahan · Carlos Guestrin · Anupam Gupta -
2007 Poster: Efficient Principled Learning of Thin Junction Trees »
Anton Chechetka · Carlos Guestrin -
2006 Poster: Distributed Inference in Dynamical Systems »
Stanislav Funiak · Carlos Guestrin · Mark A Paskin · Rahul Sukthankar