归纳逻辑程序设计的应用与发展

1、归纳逻辑程序设计的应用与发展机器学习试图利用计算机来模拟人类的学习行为，进而利用计算机的技术优势给人类的 生活带来便利。归纳逻辑程序设计（Inductive Logic Programming，简写为ILI是机器学习 和逻辑程序设计的交叉研究领域。它在子句逻辑的框架下，通过让计算机考察具体的事例， 然后学习出能够刻画这些事例特有属性的一般性规则。具体来说，计算机进行操作时，根据 背景知识在限定的归纳假设空间中不断地搜索，最后得出一个理论（也即满足某种语言偏向 的子句巢，使得所有的正例都能被理论覆盖，而负实例不被覆盖ILP作为机器学习的重要 方法，已经在生物信息学、自然语言处理、软件工程等应用领

2、域取得成功。一、归纳逻辑程序设计的研究现状近年来，ILP得到很大的发展，其应用领域也不断拓宽。一般说来，ILP最重要的应用领 域之一是生物信息学的ILP之所以能适用于生物信息学的任务，是因为它会将背景知识和 结构数据考虑在内，学习产生人类能理解的知识。在学习蛋白质结构的折叠的过程中，由于 对其结构的学习很重要，所以需要找到能够清晰描述其结构的语言。传统的属性方法无法描 述对象间的关系，因而也就无法合理地表示蛋白质分子的三维结构，ILP的一阶逻辑工具子 句逻辑是非常适合描述这种关系的语言，它在预测蛋白质结构信息和蛋白质次级结构生成中 发挥了很大作用。同时，在预测化合物诱变问题上，ILP也解决了传

3、统方法无法解决的结构 关系问题。机器学习一个非常独特的应用领域是自然语言处理，它的主要任务在于建立各种自然语 言处理系统，如文字自动识别系统、语音自动识别系统、机器翻译系统、自然语言信息检索 系统、自动索引系统等。在自然语言处理中，ILP的方法可以从文本中抽取复杂的关系数据， 这是ILP优于其他机器学习技术的特点之一ILP系统还常常为工程学、环境监控、软件分 析、模式学习和关系发现等领域的数据构造预测模型。虽然ILP与其他机器学习方法相比有 一定的优势，然而随着科学技术发展和需求的增加，ILP在应用中也面临许多挑战：首先，相比其他的机器学习系统来说，ILP系统对时间和空间有更高的要求，这使得I

4、LP 很难去处理大的数据集。因此，ILP应该努力寻求与随机搜索和并行处理技术等方法结合以 处理结构复杂的数据集。其次，隐马尔科夫模型、动态贝叶斯网络、双连词和三连词等技术都能充分表达任务中 的内在概率，而ILP系统很少有表达、处理概率的能力，这也是ILP的重大不足之一。最后，当背景知识和数据集用一阶逻辑清晰表达出来时，ILP可以运行良好。但是当数 据集是无法通过一阶逻辑清晰表达的图像、视频、音频时，ILP就无能为力。就这一问题来 说，ILP需要从约束逻辑程序设计中借鉴经验，学习处理特殊数据格式的技术。二、归纳逻辑程序设计的发展展望ILP用过程中所显现出来的不足之处，使得ILP必须与其他研究领域

5、的技术相结合，来 提高它解决问题的能力。为了使【LP更好地完成归纳学习任务，戴维培基提出了 ILP未来发 展的五个研究方向。.ILP和贝叶斯网络目前在人工智能中，贝叶斯网络(Bayesian network)是处理不确定信息和进行概率推理 的最有力工具，它在很大程度上取代了传统的基于规则的专家系统。人工智能的研究者已经 意识到概率的重要性，例如在医疗诊断中，几乎没有普遍真的医学规律存在，也很少有完全 正确的实验可被利用。取而代之的是，概率被用来刻画任务本身内在的不确定性。贝叶斯网 络被特别设计出来去表达一些可能的概率分布，并且尝试对这些概率分布进行推理。它已经 在医疗诊断、拼写纠错、故障诊断等

6、领域得到应用，也成为了国内外研究的新宠儿。虽然贝叶斯网络有如此良好的应用，然而它本质上是命题的:变量集是确定且有限的，并 且每个变量都有其确定的可能值域。这个事实限制了贝叶斯网络的应用。此外，当一个贝叶 斯网用一个图表表示时，图表能够刻画的唯一关系是概率、或然性之间的条件依赖关系，它 不能表达关系结构。要想使贝叶斯网络更好地为人类服务，必须试图去拓展贝叶斯网络的表 达力，并且试图用一个拓展的表达来进行归纳学习。实践证明，这个拓展的表达结果是复杂 的，还降低了一阶逻辑的表达力ILP研究者尝试学习添加概率的子句，来拓展贝叶斯网的 表达力，在一定程度上可以解决这一问题。目前，学者已经提出几种可供选择

7、的子句表达方 式，其中包括概率逻辑程序设计，随机逻辑程序设计和概率约束逻辑程序设计。库塞斯(Cusses) 着手研究随机逻辑程序设计的算法和应用，而恩格b和哈达维则研究贝叶斯网络的一阶表达。 一般说来，ILP和贝叶斯网络学习是正交的。ILP擅长处理关系域，而贝叶斯网络对概率处理 的很好。因此，设想一个能够具有贝叶斯网络学习和ILP-者优点的学习算法的存在和应用是 合理的，尝试将贝叶斯网络学习和ILP结合的领域也应该是一个有前途、有希望的研究领域。.ILP和随机搜索随着计算机技术的发展，人类收集数据、存储数据的能力有了很大提高，对这些数据施 以算法搜索处理，就能满足人类不同的需求。随机搜索是指在

8、目标位置基本服从均匀分布的 条件下，搜索轨迹随机且均匀散布在目标分布区域内的一种搜索方式。常用的随机搜索算法 主要包括模拟退火算法、进化策略、遗传算法。这些算法求解时搜索过程是非确定性的，算 法对约束函数及目标函数有限制，因而可以解决大规模复杂问题。大部分ILP算法搜索由假设而定的一个子句格。它们寻找这样一个子句即能够使子句覆 盖范围的函数达到最大化的子句。根据它们如何搜索这个子句格，这些ILP算法被分为(基于 最小一般泛化脚自底向上算法和(基于求精的自顶向下算法。算法又根据它们是否利用贪婪 搜索、定向搜索、接受搜索来进行进一步划分。在几乎所有算法中，以上这些搜索方法都是 确定性搜索。然而，对

9、于其他ILP之外的具有挑战性的逻辑或人工智能任务，随机搜索常常 胜过确定性搜索。1992年，考茨、塞尔曼、维斯克、米切尔以及其他学者对局部搜索算法诸 如LSAT, WSAT的可满足性问题的研究，已经证实了随机搜索更具优势。塞巴格(Saba咨和罗 维洛从事于随机匹配和定理证明，并且在诱变性研究上超越PROGOL程序，同时并没有牺牲预 测准确性和理解力。由此可以看出，随机搜索是ILP中一个有前途的研究方向。ILP可以尝 试与随机搜索算法结合，利用随机搜索可选择的形式去检测子句格，尝试解决不确定搜索问 题。.ILP和约束逻辑程序设计机器学习中广为人知的成功理论之一是约束逻辑程序设计。这个理论成功的原

10、因在于它 整合逻辑和特殊目的的推理者或约束解决者的能力。前面提到的在ILP中加入概率的方法也 可以理解为特殊目的推理者在贝叶斯网络片段形式中诉诸约束。关于约束问题，斯里尼瓦森 和卡马乔使用线性回归去构建一个约束，而克莱文和斯拉特利的工作是用朴素贝叶斯技术去 构造一个约束。值得注意的是，除了在演绎过程中所需要的约束解释器外，ILP还需要一个 像类似线性回归一样的约束构造函数。一般情况下，采用一个数据库的标准逻辑解释，这里 每一个关系是一个谓词，并且关系中每一元组是由那个谓词建立而来的一个基原子公式。现 在假设数据库中包含一些复杂数据的格式诸如影像，简单的逻辑相似性就不能够刻画一系列 影像的重要特

11、征，这时就需要基于特殊目的的影像处理技术。我们将ILP运用于处理电影（如 MPEG格沟或视频（如格沟数据时，首先需要构造特殊目的的约束解释器，再用ILP技术对其 进行处理。关于如何将约束加入到“？研究中，需要关注阿兰弗里希的工作。令人遗憾的是， 他的工作没有涉及如何确保归纳学习系统的效率，以及如何去设计约束解释器的正确类型。 这些问题正是留给我们去思考的，阿兰弗里希至少给我们提供了一种考虑问题的思路ILP确 实需要从约束逻辑程序设计中借鉴经验，学习处理特殊数据格式的技术，提高其处理问题和 解决问题的能力。.ILP和人类专家的交流在从远程通讯、分子生物学、制药学等领域的数据库中发现新知识的过程中

12、，如果一个 机器学习系统和人类专家能够以团队的形式合作，充分利用计算机的速度优势及人类专家的 知识和技术优势，那么在很大程度上会提高机器学习的效率和工作水平，促进新知识的发现。 ILP系统的三个特性使得它在知识发现中能够很自然地与人类专家进行合作:首先，ILP系统 能够利用可宣告的背景知识去构造假设，这就使得ILP和领域专家之间能够展开合作。其次， 基于特征的学习系统要求使用者从描述创造实例的特征开始，ILP系统允许结构实例根据组 成它的对象以及这些对象之间的关系一起自然地被描述。一个分子的二维结构可以将它的原 子作为对象，将原子之间的联系作为关系，这样直接表示出来。三维结构可以通过添加距离

13、关系而被表示。最后，ILP系统和命题逻辑学习者一样，都具有输出用户可以理解的规则的 能力，一些ILP系统甚至可以用英语返回规则。尽管ILP系统呈现了如此多的有用特性，它在知识发现中作为人类的合作者，仍然还有 许多缺点和不足。首先，大多数ILP系统在探试程序基础上返回单一理论，因此丢掉了对一 些领域专家来说有意义的子句。其次，ILP系统不能用人类合作者所使用的那种方式来回答 人类专家的问题。它们用简单的成批处理模式操作，采用一个数据库作为输入，并且在此基 础上返回一个假设。再次，ILP系统不会像人类合作者那样对输入的数据进行质疑。最后， 人类专家能够为假设提供知识丰富的辩护形式，例如将一个新的假

14、设与现有的信念联系起来， ILP系统做不到这一点，它仅仅能提供正确的判断。在知识发现和知识获取的人机合作中， 要克服ILP的不足，不仅需要逻辑和人工智能的技术，还需要对逻辑主体进行研究，只有二 者结合才能使机器与人类专家进行良好沟通。.ILP和并行处理技术面对今天复杂的科学计算、各式各样的图象处理以及大量的信号等问题，提高计算机的 运行速度和缩短程序的运行时间至关重要。ILP系统对时间和空间有很高的要求，这使得ILP 很难去处理大的数据集。并行处理技术的出现，为ILP处理大数据集提供了解决思路。并行 处理系统由多个处理单元组成，通过特定方法可以将一个任务分成若干个子任务，分别由各 处理单元完成

15、。目前并行处理技术最显著的是贝奥武夫簇群技术的普遍应用，以及个人计算 机、工作站、智能终端并行处理技术的使用。大卫斯基利康在大容量同步并行模型之下发展 了一个PROGOL的并行实施技术。艾伦韦德在贝奥武夫簇群技术基础上，再次进行自上而下的 ILP研究。并行处理技术的理想是在处理时间上的一个缩减，这里处理时间是处理程序所用数量的 一个线性函数，斜率接近于1。由于程序之间的管理自检和资源的竞争，这个理想很难达到。 一个好的并行策略，要求程序之间尽可能地相对独立，尽量使得程序之间拥有较少的交流或 资源共享。在测试数据时，在不同的处理器之间派发假设空间。更详细地说，对一个完备的 搜索，一个并行ILP方案能够产生一个户主用户模式，这里户主将不同分段的假设空间指派 给用户，然后用户用假设对数据进行测试。用户反馈给户主的所有假设在数据上达到一个预 先最小评估值。当用户完成自己的任务时，户主继续指派时空的新程序段，直到整个空间被 开发。在用户和户主交流过程中，要考虑每次交流产生数据的成本，还要考虑户主所花费的 时间和户主一用户交流的时间。在相对较大的论域中，完备性搜索期望用户和户主之间有尽 量少的假设交流。如果户主面对如此快速增长的假设空间片段，能够以这样一个方式将这些 片段与用户简洁地交流是可能的;那