咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >The complexity of revising log... 收藏

The complexity of revising logic programs

修订逻辑节目鈽的复杂性

作     者:Greiner, R 

作者机构:Univ Alberta Dept Comp Sci Edmonton AB T6G 2H1 Canada 

出 版 物:《JOURNAL OF LOGIC PROGRAMMING》 (逻辑与代数程序设计杂志)

年 卷 期:1999年第40卷第2-3期

页      面:273-298页

核心收录:

学科分类:08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术(可授工学、理学学位)] 081202[工学-计算机软件与理论] 

主  题:theory revision inductive logic programming computational complexity and approximatability PAC-learning 

摘      要:A rule-based program will return a set of answers to each query. An impure program, which includes the Prolog cut ! and not(.) operators, can return different answers if its rules are re-ordered. There are also many reasoning systems that return only the first answer found for each query;these first answers, too, depend on the rule order, even in pure rule-based systems. A theory revision algorithm, seeking a revised rule-base whose expected accuracy, over the distribution of queries, is optimal, should therefore consider modifying the order of the rules. This paper first shows that a polynomial number of training labeled queries (each a query paired with its correct answer) provides the distribution information necessary to identify the optimal ordering. It then proves, however, that the task of determining which ordering is optimal, once given this distributional information, is intractable even in trivial situations;e.g., even if each query is an atomic literal, we are seeking only a perfect theory, and the rule base is propositional. We also prove that this task is not even approximable: Unless P = NP, no polynomial time algorithm can produce an ordering of an n-rule theory whose accuracy is within n(gamma) of optimal, for some gamma 0. We next prove similar hardness and non-approximatability, results for the related tasks of determining, in these impure contexts, (1) the optimal ordering of the antecedents;(2) the optimal set of new rules to add and (3) the optimal set of existing rules to delete. (C) 1999 Elsevier Science Inc. All rights reserved.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分