K\"orner introduced the notion of graph entropy in 1973 as the minimal code rate of a natural coding problem where not all pairs of letters can be distinguished in the alphabet. Later it turned out that it can be expressed as the solution of a minimization problem over the so-called vertex-packing polytope. In this paper we generalize this notion to graphons. We show that the analogous minimization problem provides an upper bound for graphon entropy. We also give a lower bound in the shape of a maximization problem. The main result of the paper is that for most graphons these two bounds actually coincide and hence precisely determine the entropy in question. Furthermore, graphon entropy has a nice connection to the fractional chromatic number and the fractional clique number (defined for graphons by Hladk\'y and Rocha).


翻译:K\ “ orner ” 于1973年引入了图解 entropy 概念, 认为它是自然编码问题的最低编码率, 而在字母中并非所有的字母都可区分。 后来发现它可以被表现为在所谓的顶端包装聚点上最小化问题的解决方案。 在本文中, 我们将这个概念概括为图形。 我们显示相似的最小化问题为图解 entropy 提供了上界。 我们还给出了一个更低的线条, 其形状是最大化问题。 纸张的主要结果是, 对于大多数的图解来说, 这两条线实际上吻合, 从而精确地决定了所涉及的酶 。 此外, 石墨 entropy 与分数和分数( Hladk\'y 和 Rocha 所定义的图形) 有着良好的联系 。

0
下载
关闭预览

相关内容

自然语言处理顶会NAACL2022最佳论文出炉!
专知会员服务
43+阅读 · 2022年6月30日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
79+阅读 · 2020年7月26日
专知会员服务
162+阅读 · 2020年1月16日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
154+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
177+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
94+阅读 · 2019年10月10日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium7
中国图象图形学学会CSIG
0+阅读 · 2021年11月15日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2022年10月18日
Arxiv
0+阅读 · 2022年10月17日
Arxiv
0+阅读 · 2022年10月17日
Arxiv
27+阅读 · 2020年6月19日
Arxiv
14+阅读 · 2019年9月11日
Arxiv
17+阅读 · 2019年3月28日
VIP会员
相关VIP内容
自然语言处理顶会NAACL2022最佳论文出炉!
专知会员服务
43+阅读 · 2022年6月30日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
79+阅读 · 2020年7月26日
专知会员服务
162+阅读 · 2020年1月16日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
154+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
177+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
94+阅读 · 2019年10月10日
相关资讯
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium7
中国图象图形学学会CSIG
0+阅读 · 2021年11月15日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
相关基金
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员