我们研究了（深）神经网络的可及性问题的复杂性：它是否计算出有效输入的有效输出？最近有人声称，对于一般神经网络的问题，该问题是通用神经网络的NP算法，并且在线性不等式的结合给出的输入/输出维度上的规格是NP的。我们概括了证明并修复原始上和下限证明中的一些缺陷。在总体结果的激励下，我们表明NP硬度已经适用于限制的简单规格和神经网络。允许仅一个隐藏层和一个单个的输出维度以及仅一个负，零和一个正重或偏置的神经网络，足以确保NP硬度。此外，我们为有关神经网络验证的这一研究方向进行了详尽的讨论和可能的扩展。

我们调查（深）神经网络的可达性问题的复杂性：它是否计算了一些有效输入的有效输出？最近声称问题是NP-Complete，用于一般神经网络和联合输入/输出规范。我们修复了原始上限和下限的缺陷。然后，我们表明NP-HATDINGS已经持有限制的简单规范和具有一层的神经网络，以及针对发生参数的最小要求的神经网络。

图神经网络（GNN）通常用于两个任务：（整个）图分类和节点分类。我们正式引入了两个任务的普遍提出的决策问题，对应于以下模式：给定GNN，有效输入的某些规范以及有效输出的某些规范，请确定是否有有效的输入满足输出规范。然后，我们证明了图形分类器验证通常是不可决定的，这意味着不能有算法肯定可以保证没有任何类型的错误分类。此外，我们表明，一旦我们限制了所考虑的图的程度，在节点分类案例中的验证就可以决定。此外，我们根据考虑的GNN模型和规格讨论这些结果可能的更改。

鉴于神经网络，训练数据和阈值，已知它是NP-HARD，用于找到神经网络的权重，使得总误差低于阈值。我们精确地确定了这种基本问题的算法复杂性，通过表示它是$ \存在\ mathbb r $ -complete。这意味着问题是等同的，达到多项式时间减少，以决定多项式方程和具有整数系数的不等式和真实未知的不平等是否具有解决方案。如果广泛预期，$ \存在\ MathBB r $严格大于NP，我们的工作意味着培训神经网络的问题甚至不是在NP中。通常使用反向化的一些变异培训神经网络。本文的结果提供了一种解释，为什么常用的技术常用于NP完全问题的大实例似乎不用于此任务。这种技术的示例是SAT求解器，IP求解器，本地搜索，动态编程，命名几个一般的。

We consider the algorithmic problem of finding the optimal weights and biases for a two-layer fully connected neural network to fit a given set of data points. This problem is known as empirical risk minimization in the machine learning community. We show that the problem is $\exists\mathbb{R}$-complete. This complexity class can be defined as the set of algorithmic problems that are polynomial-time equivalent to finding real roots of a polynomial with integer coefficients. Furthermore, we show that arbitrary algebraic numbers are required as weights to be able to train some instances to optimality, even if all data points are rational. Our results hold even if the following restrictions are all added simultaneously. $\bullet$ There are exactly two output neurons. $\bullet$ There are exactly two input neurons. $\bullet$ The data has only 13 different labels. $\bullet$ The number of hidden neurons is a constant fraction of the number of data points. $\bullet$ The target training error is zero. $\bullet$ The ReLU activation function is used. This shows that even very simple networks are difficult to train. The result explains why typical methods for $\mathsf{NP}$-complete problems, like mixed-integer programming or SAT-solving, cannot train neural networks to global optimality, unless $\mathsf{NP}=\exists\mathbb{R}$. We strengthen a recent result by Abrahamsen, Kleist and Miltzow [NeurIPS 2021].

我们有助于更好地理解由具有Relu激活和给定架构的神经网络表示的功能。使用来自混合整数优化，多面体理论和热带几何的技术，我们为普遍近似定理提供了数学逆向，这表明单个隐藏层足以用于学习任务。特别是，我们调查完全可增值功能是否完全可以通过添加更多层（没有限制大小）来严格增加。由于它为神经假设类别代表的函数类提供给算法和统计方面，这个问题对算法和统计方面具有潜在的影响。然而，据我们所知，这个问题尚未在神经网络文学中调查。我们还在这些神经假设类别中代表功能所需的神经网络的大小上存在上限。

Deep neural networks have emerged as a widely used and effective means for tackling complex, real-world problems. However, a major obstacle in applying them to safety-critical systems is the great difficulty in providing formal guarantees about their behavior. We present a novel, scalable, and efficient technique for verifying properties of deep neural networks (or providing counter-examples). The technique is based on the simplex method, extended to handle the non-convex Rectified Linear Unit (ReLU ) activation function, which is a crucial ingredient in many modern neural networks. The verification procedure tackles neural networks as a whole, without making any simplifying assumptions. We evaluated our technique on a prototype deep neural network implementation of the next-generation airborne collision avoidance system for unmanned aircraft (ACAS Xu). Results show that our technique can successfully prove properties of networks that are an order of magnitude larger than the largest networks verified using existing methods.

我们回答以下问题，哪些结合性查询以多种方式上的许多正和负面示例以及如何有效地构建此类示例的特征。结果，我们为一类连接的查询获得了一种新的有效的精确学习算法。我们的贡献的核心是两种新的多项式时间算法，用于在有限结构的同态晶格中构建前沿。我们还讨论了模式映射和描述逻辑概念的独特特征性和可学习性的影响。

Two approaches to AI, neural networks and symbolic systems, have been proven very successful for an array of AI problems. However, neither has been able to achieve the general reasoning ability required for human-like intelligence. It has been argued that this is due to inherent weaknesses in each approach. Luckily, these weaknesses appear to be complementary, with symbolic systems being adept at the kinds of things neural networks have trouble with and vice-versa. The field of neural-symbolic AI attempts to exploit this asymmetry by combining neural networks and symbolic AI into integrated systems. Often this has been done by encoding symbolic knowledge into neural networks. Unfortunately, although many different methods for this have been proposed, there is no common definition of an encoding to compare them. We seek to rectify this problem by introducing a semantic framework for neural-symbolic AI, which is then shown to be general enough to account for a large family of neural-symbolic systems. We provide a number of examples and proofs of the application of the framework to the neural encoding of various forms of knowledge representation and neural network. These, at first sight disparate approaches, are all shown to fall within the framework's formal definition of what we call semantic encoding for neural-symbolic AI.

本文研究了人工神经网络（NNS）与整流线性单元的表现力。为了将它们作为实际计算的模型，我们介绍了最大仿射算术计划的概念，并显示了它们与NNS之间的等效性有关自然复杂度措施。然后我们使用此结果表明，使用多项式NNS可以解决两个基本组合优化问题，这相当于非常特殊的强多项式时间算法。首先，我们显示，对于带有N $节点的任何无向图形，有一个NN大小$ \ Mathcal {O}（n ^ 3）$，它将边缘权重用为输入，计算最小生成树的值图表。其次，我们显示，对于任何带有$ N $节点和$ M $弧的任何定向图，都有一个尺寸$ \ mathcal {o}（m ^ 2n ^ 2）$，它将电弧容量作为输入和计算最大流量。这些结果尤其尤其暗示，相应的参数优化问题的解决方案可以在多项式空间中编码所有边缘权重或电弧容量的方法，并在多项式时间中进行评估，并且由NN提供这种编码。

连续约束满意度问题（CCSP）是一个约束满意度问题（CSP），其间隔域$ u \ subset \ mathbb {r} $。我们进行了一项系统的研究，以对CCSP进行分类，这些CCSP已完成现实的存在理论，即ER完整。为了定义该类别，我们首先考虑ETR问题，该问题也代表了真实的存在理论。在此问题的情况下，我们给出了$ \ compant x_1，\ ldots，x_n \ in \ mathbb {r}的某个句子：\ phi（x_1，\ ldots，x_n）$，其中$ \ phi $ is由符号$ \ {0、1， +，\ cdot，\ geq，>，\ wedge，\ vee，\ neg \} $组成的符号符号的公式正确。 。现在，ER是所有问题的家族，这些家族允许多项式时间降低到ETR。众所周知，np $ \ subseteq $ er $ \ subseteq $ pspace。我们将注意力限制在CCSP上，并具有附加限制（$ x + y = z $）和其他一些轻度的技术状况。以前，已经显示出乘法约束（$ x \ cdot y = z $），平方约束（$ x^2 = y $）或反转约束（$ x \ cdot y = 1 $）足以建立ER-完整性。如下所示，我们以最大的平等约束来扩展这一点。我们表明，CCSP（具有附加限制和其他轻度技术状况）具有任何一个表现良好的弯曲平等约束（$ f（x，y）= 0 $）的CCSP是ER的曲线限制（$ F（x，y）= 0 $）。我们将结果进一步扩展到不平等约束。我们表明，任何行为良好的凸出弯曲且行为良好的凹陷弯曲的不平等约束（$ f（x，y）\ geq 0 $ and $ g（x，x，y）\ geq 0 $）暗示着班级的ER完整性这种CCSP。

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

单调功能和数据集在各种应用中都会出现。我们研究单调数据集的插值问题：输入是带有$ n $点的单调数据集，目标是找到一个大小和深度有效的单调神经网络，具有非负参数和阈值单元，可以插入数据放。我们表明，单调数据集无法通过深度$ 2 $的单调网络插值。另一方面，我们证明，对于每个单调数据集，在$ \ mathbb {r}^d $中$ n $点，存在一个插值的单调网络，该网络的深度为$ 4 $ $ 4 $和size $ o（nd）$。我们的插值结果意味着，每个单调功能超过$ [0,1]^d $可以通过DEPTH-4单调网络任意地近似，从而改善了先前最著名的深度构建$ d+1 $。最后，基于布尔电路复杂性的结果，我们表明，当近似单调函数时，具有正参数的电感偏差会导致神经元数量的超顺式爆炸。

突出非克劳兰（NC）公式的富有表现性比基于氏子型公式的指数更丰富。然而，氏菌效率优于非克劳尿的效率。实际上，后者的一个主要弱点是，虽然喇叭子宫公式以及喇叭算法，对于高效率至关重要，但是已经提出了非符号形式的喇叭状公式。为了克服这种弱点，我们通过将喇叭图案充分提升到NC形式，定义HOLE非字母（HORN-NC）公式的混合类$ \ MATHBB {H_ {NC}}。争论$ \ MATHBB {H_ {NC}} $以及未来的Horn-NC算法，应随着喇叭类的股份效率增加，增加非信用效率。其次，我们：（i）给出$ \ mathbb的紧凑，归纳定义{h_ {nc}} $; （ii）证明了句法$ \ mathbb {h_ {nc}} $ suppups over class，但语义上两个类都是等效的，并且（iii）表征属于$ \ mathbb {h_ {nc}} $的非锁友公式。第三，我们定义了非字词单元分辨率计算，$ ur_ {nc} $，并证明它检查多项式时间$ \ mathbb {h_ {nc}} $的可靠性。这一事实是我们的知识，使$ \ mathbb {h_ {nc}} $中的nc推理中的第一个特征多项式类。最后，我们证明了$ \ mathbb {h_ {nc}} $线性识别，也是严格的是法官和比喇叭类呈指数富裕。我们在NC自动推理中讨论了这一点，例如，可靠性解决，定理证明，逻辑编程等可以直接受益于$ \ mathbb {h_ {nc} $和$ ur_ {nc} $，它作为其被证明属性的副产物，$ \ mathbb { H_ {NC}} $ as作为分析喇叭函数和含义系统的新替代方案。

We present an approach for the verification of feed-forward neural networks in which all nodes have a piece-wise linear activation function. Such networks are often used in deep learning and have been shown to be hard to verify for modern satisfiability modulo theory (SMT) and integer linear programming (ILP) solvers.The starting point of our approach is the addition of a global linear approximation of the overall network behavior to the verification problem that helps with SMT-like reasoning over the network behavior. We present a specialized verification algorithm that employs this approximation in a search process in which it infers additional node phases for the non-linear nodes in the network from partial node phase assignments, similar to unit propagation in classical SAT solving. We also show how to infer additional conflict clauses and safe node fixtures from the results of the analysis steps performed during the search. The resulting approach is evaluated on collision avoidance and handwritten digit recognition case studies.

大多数-AT是确定联合正常形式（CNF）中输入$ N $的最低价公式的问题至少为2 ^ {n-1} $令人满意的作业。在对概率规划和推论复杂性的各种AI社区中，广泛研究了多数饱和问题。虽然大多数饱满为期40多年来，但自然变体的复杂性保持开放：大多数 - $ k $ SAT，其中输入CNF公式仅限于最多$ k $的子句宽度。我们证明，每辆$ k $，大多数 - $ k $ sat是在p的。事实上，对于任何正整数$ k $和ratic $ \ rho \ in（0,1）$ in（0,1）$与有界分比者，我们给出了算法这可以确定给定的$ k $ -cnf是否至少有$ \ rho \ cdot 2 ^ n $令人满意的分配，在确定性线性时间（而先前的最着名的算法在指数时间中运行）。我们的算法对计算复杂性和推理的复杂性具有有趣的积极影响，显着降低了相关问题的已知复杂性，例如E-Maj-$ K $ Sat和Maj-Maj- $ K $ Sat。在我们的方法中，通过提取在$ k $ -cnf的相应设置系统中发现的向日葵，可以通过提取向日葵来解决阈值计数问题的有效方法。我们还表明，大多数 - $ k $ sat的易腐烂性有些脆弱。对于密切相关的gtmajority-sat问题（我们询问给定公式是否超过2 ^ {n-1} $满足分配），这已知是pp-cleanting的，我们表明gtmajority-$ k $ sat在p for $ k \ le 3 $，但为$ k \ geq 4 $完成np-cleante。这些结果是违反直觉的，因为这些问题的“自然”分类将是PP完整性，因为GTMAJority的复杂性存在显着差异 - $ k $ SAT和MOSTION- $ K $ SAT为所有$ k \ ge 4 $。

在概念学习，数据库查询的反向工程，生成参考表达式以及知识图中的实体比较之类的应用中，找到以标记数据项形式分开的逻辑公式，该公式分开以标记数据项形式给出的正面和负面示例。在本文中，我们研究了存在本体论的数据的分离公式的存在。对于本体语言和分离语言，我们都专注于一阶逻辑及其以下重要片段：描述逻辑$ \ Mathcal {alci} $，受保护的片段，两变量的片段和受保护的否定片段。为了分离，我们还考虑（工会）连接性查询。我们考虑了几种可分离性，这些可分离性在负面示例的治疗中有所不同，以及他们是否承认使用其他辅助符号来实现分离。我们的主要结果是（所有变体）可分离性，不同语言的分离能力的比较以及确定可分离性的计算复杂性的研究。

最近已经提出了几个查询和分数来解释对ML模型的个人预测。鉴于ML型号的灵活，可靠和易于应用的可解释性方法，我们预见了需要开发声明语言以自然地指定不同的解释性查询。我们以原则的方式通过源于逻辑，称为箔，允许表达许多简单但重要的解释性查询，并且可以作为更具表现力解释性语言的核心来实现这一语言。我们研究箔片查询的两类ML模型的计算复杂性经常被视为容易解释：决策树和OBDD。由于ML模型的可能输入的数量是尺寸的指数，因此箔评估问题的易易性是精细的，但是可以通过限制模型的结构或正在评估的箔片段来实现。我们还以高级声明语言包装的箔片的原型实施，并执行实验，表明可以在实践中使用这种语言。

We study the expressibility and learnability of convex optimization solution functions and their multi-layer architectural extension. The main results are: \emph{(1)} the class of solution functions of linear programming (LP) and quadratic programming (QP) is a universal approximant for the $C^k$ smooth model class or some restricted Sobolev space, and we characterize the rate-distortion, \emph{(2)} the approximation power is investigated through a viewpoint of regression error, where information about the target function is provided in terms of data observations, \emph{(3)} compositionality in the form of a deep architecture with optimization as a layer is shown to reconstruct some basic functions used in numerical analysis without error, which implies that \emph{(4)} a substantial reduction in rate-distortion can be achieved with a universal network architecture, and \emph{(5)} we discuss the statistical bounds of empirical covering numbers for LP/QP, as well as a generic optimization problem (possibly nonconvex) by exploiting tame geometry. Our results provide the \emph{first rigorous analysis of the approximation and learning-theoretic properties of solution functions} with implications for algorithmic design and performance guarantees.

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