发帖
雷达卡
摘要翻译：
在置换上表示分布可能是一项艰巨的任务，因为$n$objects的置换数以$n$为单位按因式分解。最近用来降低存储复杂性的一种方法是利用概率独立性，但正如我们所认为的，完全独立性假设对分布施加了很强的稀疏约束，不适用于建模排名。我们确定了一种新的独立结构，称为\emph{riffled独立性}，它包含了一个更有表现力的分布族，同时保留了执行有效推理和降低样本复杂性所必需的许多性质。在riffled独立中，一个人独立地绘制两个排列，然后执行\emph{riffle shuffle}，这是纸牌游戏中常见的，将两个排列组合成一个排列。在排序的上下文中，riffled独立性对应于独立地对不相交的对象集进行排序，然后交织这些排序。在这篇文章中，我们给出了一个关于Riffried独立性的正式介绍，并给出了在Fourier理论框架内使用Riffried独立性的算法，这些算法已经在最近的一些论文中得到了探索。此外，我们还提出了一种自动的方法来发现与排序训练集无关的项目集。我们证明了我们的类聚类算法可以用来从真实的偏好排序数据集中发现有意义的潜在联盟，并学习基于riffled独立性的分层可分解模型的结构。
---
英文标题：
《Uncovering the Riffled Independence Structure of Rankings》
---
作者：
Jonathan Huang and Carlos Guestrin
---
最新提交年份：
2010
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Machine Learning 机器学习
分类描述：Papers on all aspects of machine learning research (supervised, unsupervised, reinforcement learning, bandit problems, and so on) including also robustness, explanation, fairness, and methodology. cs.LG is also an appropriate primary category for applications of machine learning methods.
关于机器学习研究的所有方面的论文（有监督的，无监督的，强化学习，强盗问题，等等），包括健壮性，解释性，公平性和方法论。对于机器学习方法的应用，CS.LG也是一个合适的主要类别。
--
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Statistics 统计学
二级分类：Applications 应用程序
分类描述：Biology, Education, Epidemiology, Engineering, Environmental Sciences, Medical, Physical Sciences, Quality Control, Social Sciences
生物学，教育学，流行病学，工程学，环境科学，医学，物理科学，质量控制，社会科学
--
一级分类：Statistics 统计学
二级分类：Machine Learning 机器学习
分类描述：Covers machine learning papers (supervised, unsupervised, semi-supervised learning, graphical models, reinforcement learning, bandits, high dimensional inference, etc.) with a statistical or theoretical grounding
覆盖机器学习论文（监督，无监督，半监督学习，图形模型，强化学习，强盗，高维推理等）与统计或理论基础
--
---
英文摘要：
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 \emph{riffled independence}, encompassing 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 \emph{riffle shuffle}, common in card games, to combine the two permutations to form a single permutation. Within the context of ranking, riffled independence corresponds to ranking disjoint sets of objects independently, then interleaving those rankings. In this paper, we provide a formal introduction to riffled independence and present algorithms for using riffled independence within Fourier-theoretic frameworks which have been explored by a number of recent papers. Additionally, we propose an automated method for discovering sets of items which are riffle independent from a training set of rankings. We show that our clustering-like algorithms can be used to discover meaningful latent coalitions from real preference ranking datasets and to learn the structure of hierarchically decomposable models based on riffled independence.
---
PDF链接：
https://arxiv.org/pdf/1006.1328
京公网安备 11010802022788号
