Over-parametrization was a crucial ingredient for recent developments in inference and machine-learning fields. However a good theory explaining this success is still lacking. In this paper we study a very simple case of mismatched over-parametrized algorithm applied to one of the most studied inference problem: the planted clique problem. We analyze a Monte Carlo (MC) algorithm in the same class of the famous Jerrum algorithm. We show how this MC algorithm is in general suboptimal for the recovery of the planted clique. We show however how to enhance its performances by adding a (mismatched) parameter: the temperature; we numerically find that this over-parametrized version of the algorithm can reach the supposed algorithmic threshold for the planted clique problem.


翻译:超平衡化是最近推论和机器学习领域发展的关键要素。 但是仍然缺乏解释这一成功的良好理论。 在本文中,我们研究了一个非常简单的不匹配的超平衡算法案例,该案例适用于研究最多的推论问题之一:种植的碎块问题。我们在著名的Jerrum算法的同一类中分析了蒙特卡洛(MC)算法。我们展示了这种MC算法一般对于恢复所栽种的碎块来说如何不最理想。然而,我们展示了如何通过添加一个(分离的)参数来提高它的性能:温度;我们从数字上发现,这种过于平衡的算法版本可以达到所栽种的碎块问题的假定算法阈值。

0
下载
关闭预览

相关内容

【ACML2020】张量网络机器学习:最近的进展和前沿,109页ppt
专知会员服务
54+阅读 · 2020年12月15日
因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
76+阅读 · 2019年10月10日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
蒙特卡罗方法(Monte Carlo Methods)
数据挖掘入门与实战
6+阅读 · 2018年4月22日
论文浅尝 | Hike: A Hybrid Human-Machine Method for Entity Alignment
机器学习研究会
6+阅读 · 2018年1月6日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【TED】同情心的进化论
英语演讲视频每日一推
3+阅读 · 2017年8月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年8月3日
Optimization for deep learning: theory and algorithms
Arxiv
102+阅读 · 2019年12月19日
Techniques for Automated Machine Learning
Arxiv
4+阅读 · 2019年7月21日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关资讯
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
蒙特卡罗方法(Monte Carlo Methods)
数据挖掘入门与实战
6+阅读 · 2018年4月22日
论文浅尝 | Hike: A Hybrid Human-Machine Method for Entity Alignment
机器学习研究会
6+阅读 · 2018年1月6日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【TED】同情心的进化论
英语演讲视频每日一推
3+阅读 · 2017年8月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员