We consider determinantal point processes (DPPs) constrained by spanning trees. Given a graph $G=(V,E)$ and a positive semi-definite matrix $\mathbf{A}$ indexed by $E$, a spanning-tree DPP defines a distribution such that we draw $S\subseteq E$ with probability proportional to $\det(\mathbf{A}_S)$ only if $S$ induces a spanning tree. We prove $\sharp\textsf{P}$-hardness of computing the normalizing constant for spanning-tree DPPs and provide an approximation-preserving reduction from the mixed discriminant, for which FPRAS is not known. We show similar results for DPPs constrained by forests.


翻译:我们考虑的是受横贯树木制约的决定性点过程。 如果用一个图形$G=(V,E) 和正的半限定基质基体$\mathbf{A}美元以美元指数计算, 横贯树木的DPP定义了一种分配方式,只有用美元来诱导横贯树木的树,我们才能以美元来比照(\mathbf{A ⁇ S) 的概率来提取$S\subseteq E$。 我们证明, 美元是计算横贯树木的 DPPs 正常化常数的硬性, 并且提供了混合的色彩的近似保存减值, 而FPRAS并不知道这一点。 我们对受森林制约的DPPs 显示类似的结果 。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
127+阅读 · 2020年11月20日
【ICML2020】多视角对比图表示学习,Contrastive Multi-View GRL
专知会员服务
80+阅读 · 2020年6月11日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
111+阅读 · 2020年6月10日
【斯坦福大学】Gradient Surgery for Multi-Task Learning
专知会员服务
47+阅读 · 2020年1月23日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
trape 一种识别工具
黑白之道
4+阅读 · 2019年5月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年4月15日
VIP会员
相关VIP内容
【干货书】机器学习速查手册,135页pdf
专知会员服务
127+阅读 · 2020年11月20日
【ICML2020】多视角对比图表示学习,Contrastive Multi-View GRL
专知会员服务
80+阅读 · 2020年6月11日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
111+阅读 · 2020年6月10日
【斯坦福大学】Gradient Surgery for Multi-Task Learning
专知会员服务
47+阅读 · 2020年1月23日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
trape 一种识别工具
黑白之道
4+阅读 · 2019年5月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员