We consider a sequence $\mathbf{T} = (\mathcal{T}_n : n \in \mathbb{N}^+)$ of trees $\mathcal{T}_n$ where, for some $\Delta \in \mathbb{N}^+$ every $\mathcal{T}_n$ has height at most $\Delta$ and as $n \to \infty$ the minimal number of children of a nonleaf tends to infinity. We can view every tree as a (first-order) $\tau$-structure where $\tau$ is a signature with one binary relation symbol. For a fixed (arbitrary) finite and relational signature $\sigma \supseteq \tau$ we consider the set $\mathbf{W}_n$ of expansions of $\mathcal{T}_n$ to $\sigma$ and a probability distribution $\mathbb{P}_n$ on $\mathbf{W}_n$ which is determined by a (parametrized/lifted) Probabilistic Graphical Model (PGM) $\mathbb{G}$ which can use the information given by $\mathcal{T}_n$. The kind of PGM that we consider uses formulas of a many-valued logic that we call $PLA^*$ with truth values in the unit interval $[0, 1]$. We also use $PLA^*$ to express queries, or events, on $\mathbf{W}_n$. With this setup we prove that, under some assumptions on $\mathbf{T}$, $\mathbb{G}$, and a (possibly quite complex) formula $\varphi(x_1, \ldots, x_k)$ of $PLA^*$, as $n \to \infty$, if $a_1, \ldots, a_k$ are vertices of the tree $\mathcal{T}_n$ then the value of $\varphi(a_1, \ldots, a_k)$ will, with high probability, be almost the same as the value of $\psi(a_1, \ldots, a_k)$, where $\psi(x_1, \ldots, x_k)$ is a ``simple'' formula the value of which can always be computed quickly (without reference to $n$), and $\psi$ itself can be found by using only the information that defines $\mathbf{T}$, $\mathbb{G}$ and $\varphi$. A corollary of this, subject to the same conditions, is a probabilistic convergence law for $PLA^*$-formulas.


翻译:暂无翻译

0
下载
关闭预览

相关内容

概率图模型是图灵奖获得者Pearl开发出来的用图来表示变量概率依赖关系的理论。概率图模型理论分为概率图模型表示理论,概率图模型推理理论和概率图模型学习理论。
【干货书】线性代数概论:计算、应用和理论,435页pdf
专知会员服务
58+阅读 · 2023年1月30日
【2022新书】数据科学的实用线性代数,328页pdf
专知会员服务
135+阅读 · 2022年9月17日
专知会员服务
15+阅读 · 2021年10月4日
专知会员服务
49+阅读 · 2021年6月2日
【ACL2020】多模态信息抽取,365页ppt
专知会员服务
143+阅读 · 2020年7月6日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【ICML2020】图神经网络谱聚类
专知
10+阅读 · 2020年7月7日
【NeurIPS2019】图变换网络:Graph Transformer Network
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
基于Lattice LSTM的命名实体识别
微信AI
47+阅读 · 2018年10月19日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Arxiv
0+阅读 · 10月29日
Arxiv
0+阅读 · 10月22日
VIP会员
相关资讯
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【ICML2020】图神经网络谱聚类
专知
10+阅读 · 2020年7月7日
【NeurIPS2019】图变换网络:Graph Transformer Network
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
基于Lattice LSTM的命名实体识别
微信AI
47+阅读 · 2018年10月19日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
相关基金
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员