Numerous generalization bounds have been proposed in the literature as
potential explanations for the ability of neural networks to generalize in the
overparameterized setting. However, none of these bounds are tight. For
instance, in their paper ``Fantastic Generalization Measures and Where to Find
Them'', Jiang et al. (2020) examine more than a dozen generalization bounds,
and show empirically that none of them imply guarantees that can explain the
remarkable performance of neural networks. This raises the question of whether
tight generalization bounds are at all possible. We consider two types of
generalization bounds common in the literature: (1) bounds that depend on the
training set and the output of the learning algorithm. There are multiple
bounds of this type in the literature (e.g., norm-based and margin-based
bounds), but we prove mathematically that no such bound can be uniformly tight
in the overparameterized setting; (2) bounds that depend on the training set
and on the learning algorithm (e.g., stability bounds). For these bounds, we
show a trade-off between the algorithm's performance and the bound's tightness.
Namely, if the algorithm achieves good accuracy on certain distributions in the
overparameterized setting, then no generalization bound can be tight for it. We
conclude that generalization bounds in the overparameterized setting cannot be
tight without suitable assumptions on the population distribution.

神经网络在超参数化设置中的泛化界限无法达到紧致性，除非在总体分布上具备合适的假设。

奇妙的概括度量无处追寻

Fantastic Generalization Measures are Nowhere to be Found

Language modeling, a central task in natural language processing, involves
estimating a probability distribution over strings. In most cases, the
estimated distribution sums to 1 over all finite strings. However, in some
pathological cases, probability mass can ``leak'' onto the set of infinite
sequences. In order to characterize the notion of leakage more precisely, this
paper offers a measure-theoretic treatment of language modeling. We prove that
many popular language model families are in fact tight, meaning that they will
not leak in this sense. We also generalize characterizations of tightness
proposed in previous works.

这篇论文采用了度量理论的方法来对自然语言处理中的语言建模进行精确的描述，并证明了许多流行的语言模型家族本质上是紧密的，从而避免了概率可能会 “渗漏” 到无限序列集合中的问题。同时也推广了之前一些关于紧密性的特征描述。

一种与测度相关的紧凑语言模型特征化方法

A Measure-Theoretic Characterization of Tight Language Models

We present deterministic techniques for computing upper and lower bounds on
marginal probabilities in sigmoid and noisy-OR networks. These techniques
become useful when the size of the network (or clique size) precludes exact
computations. We illustrate the tightness of the bounds by numerical
experiments.

本研究介绍了用于计算 sigmoid 网络和 noisy-OR 网络边际概率的确定性技巧，这些技巧在网络规模（或点团大小）不足以进行精确计算时非常有用，并通过数值实验说明了这些边界的紧密性。

在难以处理的网络中计算似然的上下界

Computing Upper and Lower Bounds on Likelihoods in Intractable Networks

This note is about the relationship between two theories of negation as
failure -- one based on program completion, the other based on stable models,
or answer sets. Francois Fages showed that if a logic program satisfies a
certain syntactic condition, which is now called ``tightness,'' then its stable
models can be characterized as the models of its completion. We extend the
definition of tightness and Fages' theorem to programs with nested expressions
in the bodies of rules, and study tight logic programs containing the
definition of the transitive closure of a predicate.

本论文探讨否定作为失败的两种理论之间的关系：基于程序完成和基于稳定模型或答案集。研究表明，当一个逻辑程序满足一定的语法条件 (被称为 “紧密性”) 时，它的稳定模型可以被表征为其完成模型。本研究将 “紧密性” 的定义和 Fages 的定理扩展到规则体中包含嵌套表达式的程序，并研究包含谓词的传递闭包定义的紧致逻辑程序。