发帖
雷达卡
摘要翻译：
虽然已知的概率网络灵敏度分析和参数整定算法的运行时间与网络规模成指数关系，但这些问题的精确计算复杂度尚未确定。在本文中，我们研究了调谐问题的几个变体，并证明了这些问题一般是NPPP-完全的。我们进一步证明，对于一些受限变体，问题仍然是NP-完全或PP-完全的。这些复杂性的结果提供了一个洞察力，即灵敏度分析和调谐方面的最新成果是否可以推广到更普遍、更实用的方法。
---
英文标题：
《The Computational Complexity of Sensitivity Analysis and Parameter
Tuning》
---
作者：
Johan Kwisthout, Linda C. van der Gaag
---
最新提交年份：
2012
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
While known algorithms for sensitivity analysis and parameter tuning in probabilistic networks have a running time that is exponential in the size of the network, the exact computational complexity of these problems has not been established as yet. In this paper we study several variants of the tuning problem and show that these problems are NPPP-complete in general. We further show that the problems remain NP-complete or PP-complete, for a number of restricted variants. These complexity results provide insight in whether or not recent achievements in sensitivity analysis and tuning can be extended to more general, practicable methods.
---
PDF链接：
https://arxiv.org/pdf/1206.3265
京公网安备 11010802022788号
