任何涉及一组随机变量的概率模型的主要用途是在其上运行推理和采样查询。经典概率模型中的推理查询是通过计算作为输入的事件的边际或条件概率的计算。当概率模型是顺序的时，涉及复杂语法的更复杂的边际推理查询可能会在计算语言学和NLP等领域中引起人们的关注。在这项工作中，我们解决了在隐藏的马尔可夫模型（HMMS）中计算无上下文语法（CFG）的可能性的问题。我们提供了一种动态算法，用于确切计算无上下文的语法类别的可能性。我们表明问题是NP-HARD，即使输入CFG的歧义性程度小于或等于2。然后我们提出了一种完全多项式随机近似方案（FPRAS）算法，以近似案例的可能性多项式结合的模棱两可的CFG。

Probabilistic context-free grammars have a long-term record of use as generative models in machine learning and symbolic regression. When used for symbolic regression, they generate algebraic expressions. We define the latter as equivalence classes of strings derived by grammar and address the problem of calculating the probability of deriving a given expression with a given grammar. We show that the problem is undecidable in general. We then present specific grammars for generating linear, polynomial, and rational expressions, where algorithms for calculating the probability of a given expression exist. For those grammars, we design algorithms for calculating the exact probability and efficient approximation with arbitrary precision.

识别概率上下文无语法的问题有两个方面：第一个是确定语法的拓扑（语法规则），第二个是估计每个规则的概率权重。考虑到一般来说，尤其是学习无上下文语法的硬度结果，尤其是概率语法，大多数文献都集中在第二个问题上。在这项工作中，我们解决了第一个问题。我们将注意力限制在结构上明确的无上下文语法（SUWCFG）上，并为\提供了一种查询学习算法，用于\结构上明确的概率无上下文语法（SUPCFG）。我们表明，可以使用\ emph {Co-Linear多重树自动机}（CMTA）表示SUWCFG，并提供一种学习CMTA的多项式学习算法。我们表明，学到的CMTA可以转换为概率语法，从而提供了一种完整的算法，用于学习结构明确的概率上下文无语法（语法拓扑和概率权重），并使用结构化的成员资格查询和结构化的等价Queries。这项工作的摘要版本在AAAI 21上发布。

我们考虑测定点过程（DPP）的产物，该点过程，其概率质量与多矩阵的主要成本的产物成比例，作为DPP的天然有希望的推广。我们研究计算其归一化常量的计算复杂性，这是最重要的概率推理任务。我们的复杂性 - 理论结果（差不多）排除了该任务的有效算法的存在，除非输入矩阵被迫具有有利的结构。特别是，我们证明了以下内容：（1）计算$ \ sum_s \ det（{\ bf a} _ {s，s，s}）^ p $完全针对每个（固定）阳性甚至整数$ p $ up-hard和Mod $ _3 $ p-hard，它给Kulesza和Taskar提出的打开问题给出了否定答案。 （2）$ \ sum_s \ det（{\ bf a} _ {s，s}）\ det（{\ bf b} _ {s，s}）\ det（{\ bf c} _ {s，s} ）$ IS难以在2 ^ {o（| i | i | ^ {1- \ epsilon}）} $或$ 2 ^ {o（n ^ {1 / epsilon}）} $的任何一个$ \ epsilon> 0 $，其中$ | i | $是输入大小，$ n $是输入矩阵的顺序。这种结果比Gillenwater导出的两个矩阵的#P硬度强。 （3）有$ k ^ {o（k）} n ^ {o（1）} $ - 计算$ \ sum_s \ det的时间算法（{\ bf a} _ {s，s}）\ det（ {\ bf b} _ {s，s}）$，其中$ k $是$ \ bf a $和$ \ bf b $的最大等级，或者由$ \ bf a $的非零表项形成的图表的树宽和$ \ bf b $。据说这种参数化算法是固定参数的易解。这些结果可以扩展到固定尺寸的情况。此外，我们介绍了两个固定参数批量算法的应用程序给定矩阵$ \ bf a $ treewidth $ w $：（4）我们可以计算$ 2 ^ {\ frac {n} {2p-1} $ - 近似值到$ \ sum_s \ det（{\ bf a} _ {s，s}）^ p $ for任何分数$ p> 1 $以$ w ^ {o（wp）} n ^ {o（1）} $时间。 （5）我们可以在$ w ^ {o（w \ sqrt n）} n ^ {

酒吧 - 希利尔的结构是正式语言理论的经典结果。它通过构造表明，无上下文语言与普通语言之间的相交本身是无上下文的。但是，其原始配方（Bar-Hillel等人，1961年）都不是其加权扩展（Nederhof和Satta，2003年）都无法使用$ \ epsilon $ -Arcs处理自动机。在此简短的说明中，我们将Bar-Hillel结构概括为即使自动机包含$ \ epsilon $ -Arcs，也可以正确计算交叉路口。我们进一步证明，我们的广义结构导致语法编码输入自动机和语法的结构，同时保留原始结构的渐近尺寸。

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.

我们建立了量子算法设计与电路下限之间的第一一般连接。具体来说，让$ \ mathfrak {c} $是一类多项式大小概念，假设$ \ mathfrak {c} $可以在统一分布下的成员查询，错误$ 1/2 - \ gamma $通过时间$ t $量子算法。我们证明如果$ \ gamma ^ 2 \ cdot t \ ll 2 ^ n / n $，则$ \ mathsf {bqe} \ nsubseteq \ mathfrak {c} $，其中$ \ mathsf {bqe} = \ mathsf {bque} [2 ^ {o（n）}] $是$ \ mathsf {bqp} $的指数时间模拟。在$ \ gamma $和$ t $中，此结果是最佳的，因为它不难学习（经典）时间$ t = 2 ^ n $（没有错误） ，或在Quantum Time $ t = \ mathsf {poly}（n）$以傅立叶采样为单位为1/2美元（2 ^ { - n / 2}）$。换句话说，即使对这些通用学习算法的边际改善也会导致复杂性理论的主要后果。我们的证明在学习理论，伪随机性和计算复杂性的几个作品上构建，并且至关重要地，在非凡的经典学习算法与由Oliveira和Santhanam建立的电路下限之间的联系（CCC 2017）。扩展他们对量子学习算法的方法，结果产生了重大挑战。为此，我们展示了伪随机发电机如何以通用方式意味着学习到较低的连接，构建针对均匀量子计算的第一个条件伪随机发生器，并扩展了Impagliazzo，JaiSwal的本地列表解码算法。 ，Kabanets和Wigderson（Sicomp 2010）通过微妙的分析到量子电路。我们认为，这些贡献是独立的兴趣，可能会发现其他申请。

形状约束语言（SHACL）是通过验证图表上的某些形状来验证RDF数据的最新W3C推荐语言。先前的工作主要集中在验证问题上，并且仅针对SHACL的简化版本研究了对设计和优化目的至关重要的可满足性和遏制的标准决策问题。此外，SHACL规范不能定义递归定义的约束的语义，这导致文献中提出了几种替代性递归语义。尚未研究这些不同语义与重要决策问题之间的相互作用。在本文中，我们通过向新的一阶语言（称为SCL）的翻译提供了对SHACL的不同特征的全面研究，该语言精确地捕获了SHACL的语义。我们还提出了MSCL，这是SCL的二阶扩展，它使我们能够在单个形式的逻辑框架中定义SHACL的主要递归语义。在这种语言中，我们还提供了对过滤器约束的有效处理，这些滤镜经常在相关文献中被忽略。使用此逻辑，我们为不同的SHACL片段的可满足性和遏制决策问题提供了（联合）可决定性和复杂性结果的详细图。值得注意的是，我们证明这两个问题对于完整的语言都是不可避免的，但是即使面对递归，我们也提供了有趣的功能的可决定性组合。

我们证明，可以通过恒定的深度统一阈值电路模拟输入长度中具有对数精度的变压器神经网络（以及使用输入长度中的线性空间计算的FeedForward子网络）。因此，此类变压器仅在$ \ mathsf {tc}^0 $中识别形式语言，这是由常数深度，多大小阈值电路定义的语言类。这证明了NLP中的实际主张与计算复杂性理论中的理论猜想之间的联系：“注意就是您需要的一切”（Vaswani等，2017），即，只有在所有有效地计算的情况下，变形金刚都能够进行所有有效的计算可以使用日志空间来解决问题，即$ \ mathsf l = \ mathsf p $。我们还构建了一个可以在任何输入上评估任何恒定深度阈值电路的变压器，证明变形金刚可以遵循$ \ Mathsf {tc}^0 $中表示的说明。

在本文中，我们在不同研究领域使用的三种模型之间存在联系：来自正式语言和语言学的加权有限自动机〜（WFA），机器学习中使用的经常性神经网络，以及张量网络，包括一组高处的优化技术量子物理学和数值分析中使用的顺序张量。我们首先介绍WFA与张力列车分解，特定形式的张量网络之间的内在关系。该关系允许我们展示由WFA计算的函数的Hankel矩阵的新型低级结构，并设计利用这种结构的有效光谱学习算法来扩展到非常大的Hankel矩阵。我们将解开基本连接在WFA和第二阶逆转神经网络之间〜（2-RNN）：在离散符号的序列的情况下，具有线性激活功能的WFA和2-RNN是表现性的。利用该等效结果与加权自动机的经典频谱学习算法相结合，我们介绍了在连续输入向量序列上定义的线性2-RNN的第一可提供学习算法。本算法依赖于Hankel Tensor的低等级子块，可以从中可以从中恢复线性2-RNN的参数。在综合性和现实世界数据的仿真研究中评估了所提出的学习算法的性能。

语法推断是计算学习理论中的一个经典问题，也是自然语言处理中更广泛影响的话题。我们将语法视为计算模型，并提出了一种新型的神经方法，以从正面和负面实例中诱导常规语法。我们的模型是完全可以解释的，其中间结果可直接解释为部分分析，并且可以在提供足够的数据时将其用于学习任意的常规语法。我们的方法始终在各种复杂性测试中获得高召回和精确得分。我们使详细的结果和代码随时可用。

在本文中，我们提出了一个基于树张量网状状态的密度估计框架。所提出的方法包括使用Chow-Liu算法确定树拓扑，并获得线性系统通过草图技术定义张量 - 网络组件的线性系统。开发了草图功能的新颖选择，以考虑包含循环的图形模型。提供样品复杂性保证，并通过数值实验进一步证实。

该注释有三个目的：（i）我们提供了一个独立的说明，表明在可能的（PAC）模型中，连接性查询无法有效地学习，从而明确注意这一概念阶级缺乏这一概念的事实，多项式大小的拟合属性，在许多计算学习理论文献中被默认假设的属性；（ii）我们建立了强大的负PAC可学习性结果，该结果适用于许多限制类别的连接性查询（CQ），包括针对广泛的“无循环”概念的无孔CQ；（iii）我们证明CQ可以通过会员查询有效地学习PAC。

Motivated by alignment of correlated sparse random graphs, we introduce a hypothesis testing problem of deciding whether or not two random trees are correlated. We obtain sufficient conditions under which this testing is impossible or feasible. We propose MPAlign, a message-passing algorithm for graph alignment inspired by the tree correlation detection problem. We prove MPAlign to succeed in polynomial time at partial alignment whenever tree detection is feasible. As a result our analysis of tree detection reveals new ranges of parameters for which partial alignment of sparse random graphs is feasible in polynomial time. We then conjecture that graph alignment is not feasible in polynomial time when the associated tree detection problem is impossible. If true, this conjecture together with our sufficient conditions on tree detection impossibility would imply the existence of a hard phase for graph alignment, i.e. a parameter range where alignment cannot be done in polynomial time even though it is known to be feasible in non-polynomial time.

我们介绍了神经堆栈体系结构，包括一个可区分的参数化堆栈操作员，该堆栈操作员近似堆栈推送和弹出操作，以选择明确表示堆栈的参数选择。我们证明了这种堆栈体系结构的稳定性：在任意许多堆栈操作之后，神经堆栈的状态仍然与离散堆栈的状态非常相似。使用神经堆栈和复发性神经网络，我们引入了神经网络下降自动机（NNPDA），并证明具有有限/有界神经元的NNPDA可以模拟任何PDA。此外，我们扩展了建筑，并提出了新的建筑神经状态图灵机（NNTM）。我们证明，具有有界神经元的可区分NNTM可以实时模拟图灵机（TM）。就像神经堆栈一样，这些架构也很稳定。最后，我们扩展了构造，以表明可区分的NNTM等同于通用图灵机（UTM），并且只能使用\ textbf {七个有限/有限的精度}神经元模拟任何TM。这项工作为有界精度RNN的计算能力提供了新的理论界限，并随着内存增强。

当前深度学习方法的许多应用程序的警告是需要大规模数据。Kolmogorov复杂性结果提出的一种改进是将最小描述长度原理与计算通用模型应用。我们研究了这种方法原则上可以带来的样品效率的潜在提高。我们使用多项式时间图灵机代表计算上的通用模型和布尔电路，以表示作用于有限精确数字的人工神经网络（ANN）。我们的分析解散了我们的问题与计算复杂性结果之间的直接联系。我们在使用图灵机而不是ANN应用的MDL之间的样品效率上提供了下限和上限。我们的界限取决于要学习的布尔函数的输入的位尺寸。此外，我们重点介绍了电路复杂性的经典开放问题与这些问题的紧密关系之间的密切关系。

我们研究了用$ q $ modes $ a \ in \ mathbb {r}^{n \ times \ ldots \ times n} $的近似给定张量的问题。图$ g =（v，e）$，其中$ | v | = q $，以及张张量的集合$ \ {u_v \ mid v \ in v \} $，以$ g $指定的方式收缩以获取张量$ t $。对于$ u_v $的每种模式，对应于$ v $的边缘事件，尺寸为$ k $，我们希望找到$ u_v $，以便最小化$ t $和$ a $之间的frobenius norm距离。这概括了许多众所周知的张量网络分解，例如张量列，张量环，塔克和PEPS分解。我们大约是二进制树网络$ t'$带有$ o（q）$核的大约$ a $，因此该网络的每个边缘上的尺寸最多是$ \ widetilde {o}（k^{o（dt） } \ cdot q/\ varepsilon）$，其中$ d $是$ g $的最大度，$ t $是其树宽，因此$ \ | a -t'-t'\ | _f^2 \ leq（1 + \ Varepsilon）\ | a -t \ | _f^2 $。我们算法的运行时间为$ o（q \ cdot \ text {nnz}（a）） + n \ cdot \ text {poly}（k^{dt} q/\ varepsilon）$，其中$ \ text {nnz }（a）$是$ a $的非零条目的数量。我们的算法基于一种可能具有独立感兴趣的张量分解的新维度降低技术。我们还开发了固定参数可处理的$（1 + \ varepsilon）$ - 用于张量火车和塔克分解的近似算法，改善了歌曲的运行时间，Woodruff和Zhong（Soda，2019），并避免使用通用多项式系统求解器。我们表明，我们的算法对$ 1/\ varepsilon $具有几乎最佳的依赖性，假设没有$ O（1）$ - 近似算法的$ 2 \至4 $ norm，并且运行时间比蛮力更好。最后，我们通过可靠的损失函数和固定参数可拖动CP分解给出了塔克分解的其他结果。

我们根据描述逻辑ALC和ALCI介绍并研究了本体论介导的查询的几个近似概念。我们的近似值有两种：我们可以（1）用一种以易访问的本体语言为例，例如ELI或某些TGD，以及（2）用可拖动类的一个替换数据库，例如其treewidth的数据库，由常数界定。我们确定所得近似值的计算复杂性和相对完整性。（几乎）所有这些都将数据复杂性从Conp-Complete降低到Ptime，在某些情况下甚至是固定参数可拖动和线性时间。虽然种类（1）的近似也降低了综合复杂性，但这种近似（2）往往并非如此。在某些情况下，联合复杂性甚至会增加。

计算Wassersein BaryCenters（A.K.A.最佳运输重构）是由于数据科学的许多应用，最近引起了相当大的关注的几何问题。虽然存在任何固定维度的多项式时间算法，但所有已知的运行时间都在维度中呈指数级。这是一个开放的问题，无论是这种指数依赖性是否可改进到多项式依赖性。本文证明，除非P = NP，答案是否定的。这揭示了Wassersein的BaryCenter计算的“维度诅咒”，其不会发生最佳运输计算。此外，我们对计算Wassersein的硬度结果延伸到近似计算，看似简单的问题案例，以及在其他最佳运输指标中平均概率分布。

由于机器学习，统计和科学的应用，多边缘最佳运输（MOT）引起了极大的兴趣。但是，在大多数应用中，MOT的成功受到缺乏有效算法的严重限制。实际上，MOT一般需要在边际K及其支撑大小n的数量中指数时间n。本文开发了一个关于“结构”在poly（n，k）时间中可溶解的一般理论。我们开发了一个统一的算法框架，用于通过表征不同算法所需的“结构”来解决poly（n，k）时间中的MOT，这是根据双重可行性甲骨文的简单变体所需的。该框架有几个好处。首先，它使我们能够证明当前是最流行的MOT算法的Sinkhorn算法比其他算法要在poly（n，k）时间中求解MOT所需的结构更严格。其次，我们的框架使得为给定的MOT问题开发poly（n，k）时间算法变得更加简单。特别是（大约）解决双重可行性Oracle是必要和足够的 - 这更适合标准算法技术。我们通过为三个通用类成本结构类别的poly（n，k）时间算法开发poly（n，k）时间算法来说明这种易用性：（1）图形结构； （2）设定优化结构； （3）低阶和稀疏结构。对于结构（1），我们恢复了Sindhorn具有poly（n，k）运行时的已知结果；此外，我们为计算精确且稀疏的解决方案提供了第一个poly（n，k）时间算法。对于结构（2） - （3），我们给出了第一个poly（n，k）时间算法，甚至用于近似计算。这三个结构一起涵盖了许多MOT的当前应用。