Learning implicitly in reasoning in PAC-Semantics
Learning implicitly in reasoning in PAC-Semantics
复制标题
PAC-Semantics 中隐式推理学习
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Brendan Juba
中科院分区：
文献类型：
--
作者：
Brendan Juba
我们考虑基于背景知识回答关于命题逻辑公式的查询的问题，所述背景知识部分地被显式地表示为其他公式，并且部分地被表示为独立地从固定的概率分布中提取的部分模糊的示例，其中查询相对于比通常更弱的语义被回答-PAC-Semantics，Valiant（2000）提出的一个新的概念--它是用例子的分布来定义的。我们描述了一个相当普遍的，有效的减少到有限版本的证明系统的决策问题（例如，有界空间树状分解、有界次数多项式演算等）从相应版本的推理问题，其中一些背景知识没有明确给出的公式，只能从例子中学习。至关重要的是，我们没有生成从示例中提取的知识的显式表示，因此背景知识的“学习”只是隐式完成的。因此，这种方法可以利用公式作为背景知识，这些知识在分布上并不完全有效-本质上是不可知学习的模拟。
We consider the problem of answering queries about formulas of propositional logic based on background knowledge partially represented explicitly as other formulas, and partially represented as partially obscured examples independently drawn from a fixed probability distribution, where the queries are answered with respect to a weaker semantics than usual -- PAC-Semantics, introduced by Valiant (2000) -- that is defined using the distribution of examples. We describe a fairly general, efficient reduction to limited versions of the decision problem for a proof system (e.g., bounded space treelike resolution, bounded degree polynomial calculus, etc.) from corresponding versions of the reasoning problem where some of the background knowledge is not explicitly given as formulas, only learnable from the examples. Crucially, we do not generate an explicit representation of the knowledge extracted from the examples, and so the "learning" of the background knowledge is only done implicitly. As a consequence, this approach can utilize formulas as background knowledge that are not perfectly valid over the distribution---essentially the analogue of agnostic learning here.