论文标题
关于推理框架的相对渐近表达性
On the relative asymptotic expressivity of inference frameworks
论文作者
论文摘要
我们考虑具有真实价值的逻辑在单位间隔$ [0,1] $中。这种逻辑用于定义查询并定义概率分布。在这种情况下，几乎确定公式的等效性的概念被推广到渐近等效性的概念。我们证明了关于公式的渐近等效性的两个新结果，其中每个结果都具有融合定律为必然。这些结果以及几个较旧的结果可以作为有关推理框架的相对渐近表达性的结果。一个推进框架$ \ mathbf {f} $是一类对$（\ mathbb {p}，l）$，其中$ \ mathbb {p} =（\ mathbb {p} _n：n = 1，2，2，2，2，2，2，3，3，\ ldots） $ \ Mathbf {w} _n $的所有$σ$ - 带有域$ \ {1，\ ldots，n \} $的结构（其中$σ$是一阶签名），而$ l $是单位间隔$ [0，1] $的真相值的逻辑。一个推理框架$ \ mathbf {f}'$至少与推理框架$ \ mathbf {f} $同样表现力，如果对于每个$（\ m athbb {p}，l），l）\ in \ mathbf {f} $ \ mathbb {p} $是渐近的总变化，等同于$ \ mathbb {p}'$，并且每个$φ（\ bar {x}）\ in L $中有$φ'（\ bar {x}）\ in L'$ in l'$ in l'o相对于$ \ mathbb {p} $，$φ（\ bar {x}）$。这种关系是预订。此外，如果$ \ mathbf {f} $至少与$ \ mathbf {f}'$一样表达，那么我们说$ \ mathbf {f} $和$ \ mathbf {f}'$异常表达同样表达。我们的第三个贡献是将本文的新结果和以前的几个结果系统化，以便对许多推理系统进行预订，这些推理系统在机器学习和人工智能的背景下是相关的。
We consider logics with truth values in the unit interval $[0,1]$. Such logics are used to define queries and to define probability distributions. In this context the notion of almost sure equivalence of formulas is generalized to the notion of asymptotic equivalence. We prove two new results about the asymptotic equivalence of formulas where each result has a convergence law as a corollary. These results as well as several older results can be formulated as results about the relative asymptotic expressivity of inference frameworks. An inference framework $\mathbf{F}$ is a class of pairs $(\mathbb{P}, L)$, where $\mathbb{P} = (\mathbb{P}_n : n = 1, 2, 3, \ldots)$, $\mathbb{P}_n$ are probability distributions on the set $\mathbf{W}_n$ of all $σ$-structures with domain $\{1, \ldots, n\}$ (where $σ$ is a first-order signature) and $L$ is a logic with truth values in the unit interval $[0, 1]$. An inference framework $\mathbf{F}'$ is asymptotically at least as expressive as an inference framework $\mathbf{F}$ if for every $(\mathbb{P}, L) \in \mathbf{F}$ there is $(\mathbb{P}', L') \in \mathbf{F}'$ such that $\mathbb{P}$ is asymptotically total variation equivalent to $\mathbb{P}'$ and for every $φ(\bar{x}) \in L$ there is $φ'(\bar{x}) \in L'$ such that $φ'(\bar{x})$ is asymptotically equivalent to $φ(\bar{x})$ with respect to $\mathbb{P}$. This relation is a preorder. If, in addition, $\mathbf{F}$ is at least as expressive as $\mathbf{F}'$ then we say that $\mathbf{F}$ and $\mathbf{F}'$ are asymptotically equally expressive. Our third contribution is to systematize the new results of this paper and several previous results in order to get a preorder on a number of inference systems that are of relevance in the context of machine learning and artificial intelligence.
