逻辑程序设计的研究现状与展望

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

　　一、归纳逻辑程序设计的研究现状
　　
　　近年来，ILP得到很大的发展，其应用领域也不断拓宽。

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

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

　　首先，相比其他的机器学习系统来说，ILP系统对时间和空间有更高的要求，这使得ILP很难去处理大的数据集。因此，ILP应该努力寻求与随机搜索和并行处理技术等方法结合以处理结构复杂的数据集。

　　其次，隐马尔科夫模型、动态贝叶斯网络、双连词和三连词等技术都能充分表达任务中的内在概率，而ILP系统很少有表达、处理概率的能力，这也是ILP的重大不足之一。

　　最后，当背景知识和数据集用一阶逻辑清晰表达出来时，ILP可以运行良好。但是当数据集是无法通过一阶逻辑清晰表达的图像、视频、音频时，ILP就无能为力。就这一问题来说，ILP需要从约束逻辑程序设计中借鉴经验，学习处理特殊数据格式的技术。

　　二、归纳逻辑程序设计的发展展望
　　
　　ILP应用过程中所显现出来的不足之处，使得ILP必须与其他研究领域的技术相结合，来提高它解决问题的能力。为了使ILP更好地完成归纳学习任务，戴维·培基 （DavidPage） 提出了ILP未来发展的五个研究方向。

　　1.ILP和贝叶斯网络
　　目前在人工智能中，贝叶斯网络 （Bayesian network）是处理不确定信息和进行概率推理的最有力工具，它在很大程度上取代了传统的基于规则的专家系统。人工智能的研究者已经意识到概率的重要性，例如在医疗诊断中，几乎没有普遍真的医学规律存在，也很少有完全正确的实验可被利用。取而代之的是，概率被用来刻画任务本身内在的不确定性。贝叶斯网络被特别设计出来去表达一些可能的概率分布，并且尝试对这些概率分布进行推理。它已经在医疗诊断、拼写纠错、故障诊断等领域得到应用，也成为了国内外研究的新宠儿。

　　虽然贝叶斯网络有如此良好的应用，然而它本质上是命题的：变量集是确定且有限的，并且每个变量都有其确定的可能值域。这个事实限制了贝叶斯网络的应用。此外，当一个贝叶斯网用一个图表表示时，图表能够刻画的唯一关系是概率、或然性之间的条件依赖关系，它不能表达关系结构。

　　要想使贝叶斯网络更好地为人类服务，必须试图去拓展贝叶斯网络的表达力，并且试图用一个拓展的表达来进行归纳学习。实践证明，这个拓展的表达结果是复杂的，还降低了一阶逻辑的表达力。ILP研究者尝试学习添加概率的子句，来拓展贝叶斯网的表达力，在一定程度上可以解决这一问题。

　　目前，学者已经提出几种可供选择的子句表达方式，其中包括概率逻辑程序设计，随机逻辑程序设计和概率约束逻辑程序设计。库塞斯 （Cussens） 着手研究随机逻辑程序设计的算法和应用，而恩格 （Ngo） 和哈达维 （Haddawy） 则研究贝叶斯网络的一阶表达。一般说来，ILP和贝叶斯网络学习是正交的。ILP擅长处理关系域，而贝叶斯网络对概率处理的很好。因此，设想一个能够具有贝叶斯网络学习和ILP二者优点的学习算法的存在和应用是合理的，尝试将贝叶斯网络学习和ILP结合的领域也应该是一个有前途、有希望的研究领域。

　　2.ILP和随机搜索
　　随着计算机技术的发展，人类收集数据、存储数据的能力有了很大提高，对这些数据施以算法搜索处理，就能满足人类不同的需求。随机搜索 （Stochastic search） 是指在目标位置基本服从均匀分布的条件下，搜索轨迹随机且均匀散布在目标分布区域内的一种搜索方式。常用的随机搜索算法主要包括模拟退火算法、进化策略、遗传算法。这些算法求解时搜索过程是非确定性的，算法对约束函数及目标函数有限制，因而可以解决大规模复杂问题。

　　大部分ILP算法搜索由假设而定的一个子句格。它们寻找这样一个子句---即能够使子句覆盖范围的函数达到最大化的子句。根据它们如何搜索这个子句格，这些ILP算法被分为 （基于最小一般泛化的） 自底向上算法和 （基于求精的） 自顶向下算法。算法又根据它们是否利用贪婪搜索、定向搜索、接受搜索来进行进一步划分。在几乎所有算法中，以上这些搜索方法都是确定性搜索。然而，对于其他ILP之外的具有挑战性的逻辑或人工智能任务，随机搜索常常胜过确定性搜索。1992年，考茨 （Kautz）、塞尔曼 （Selman）、维斯克 （Levesque）、米切尔 （Mitchel）l 以及其他学者对局部搜索算法诸如GSAT、WSAT的可满足性问题的研究，已经证实了随机搜索更具优势。塞巴格 （Sebag） 和罗维洛（Rouveiro）l 从事于随机匹配和定理证明，并且在诱变性研究上超越PROGOL程序，同时并没有牺牲预测准确性和理解力。由此可以看出，随机搜索是ILP中一个有前途的研究方向。ILP可以尝试与随机搜索算法结合，利用随机搜索可选择的形式去检测子句格，尝试解决不确定搜索问题。

　　3.ILP和约束逻辑程序设计
　　机器学习中广为人知的成功理论之一是约束逻辑程序设计。这个理论成功的原因在于它整合逻辑和特殊目的的推理者或约束解决者的能力。前面提到的在ILP中加入概率的方法也可以理解为特殊目的推理者在贝叶斯网络片段形式中诉诸约束。关于约束问题，斯里尼瓦森 （Srinivasan） 和卡马乔 （Camacho） 使用线性回归去构建一个约束，而克莱文（Craven） 和斯拉特利 （Slattery） 的工作是用朴素贝叶斯技术去构造一个约束。值得注意的是，除了在演绎过程中所需要的约束解释器外，ILP还需要一个像类似线性回归一样的“约束构造函数”.一般情况下，采用一个数据库的标准逻辑解释，这里每一个关系是一个谓词，并且关系中每一元组是由那个谓词建立而来的一个基原子公式。现在假设数据库中包含一些复杂数据的格式诸如影像，简单的逻辑相似性就不能够刻画一系列影像的重要特征，这时就需要基于特殊目的的影像处理技术。我们将ILP运用于处理电影 （如MPEG格式） 或视频 （如MIDI格式） 数据时，首先需要构造特殊目的的约束解释器，再用ILP技术对其进行处理。关于如何将约束加入到ILP研究中，需要关注阿兰·弗里希 （AlanFrisch） 的工作。令人遗憾的是，他的工作没有涉及如何确保归纳学习系统的效率，以及如何去设计约束解释器的正确类型。这些问题正是留给我们去思考的，阿兰·弗里希至少给我们提供了一种考虑问题的思路。ILP确实需要从约束逻辑程序设计中借鉴经验，学习处理特殊数据格式的技术，提高其处理问题和解决问题的能力。

　　4.ILP和人类专家的交流
　　在从远程通讯、分子生物学、制药学等领域的数据库中发现新知识的过程中，如果一个机器学习系统和人类专家能够以团队的形式合作，充分利用计算机的速度优势及人类专家的知识和技术优势，那么在很大程度上会提高机器学习的效率和工作水平，促进新知识的发现。ILP系统的三个特性使得它在知识发现中能够很自然地与人类专家进行合作：首先，ILP系统能够利用可宣告的背景知识去构造假设，这就使得ILP和领域专家之间能够展开合作。其次，基于特征的学习系统要求使用者从描述创造实例的特征开始，ILP系统允许结构实例根据组成它的对象以及这些对象之间的关系一起自然地被描述。一个分子的二维结构可以将它的原子作为对象，将原子之间的联系作为关系，这样直接表示出来。三维结构可以通过添加距离关系而被表示。最后，ILP系统和命题逻辑学习者一样，都具有输出用户可以理解的规则的能力，一些ILP系统甚至可以用英语返回规则。

　　尽管ILP系统呈现了如此多的有用特性，它在知识发现中作为人类的合作者，仍然还有许多缺点和不足。首先，大多数ILP系统在探试程序基础上返回单一理论，因此丢掉了对一些领域专家来说有意义的子句。其次，ILP系统不能用人类合作者所使用的那种方式来回答人类专家的问题。它们用简单的成批处理模式操作，采用一个数据库作为输入，并且在此基础上返回一个假设。再次，ILP系统不会像人类合作者那样对输入的数据进行质疑。最后，人类专家能够为假设提供知识丰富的辩护形式，例如将一个新的假设与现有的信念联系起来，ILP系统做不到这一点，它仅仅能提供正确的判断。在知识发现和知识获取的人机合作中，要克服ILP的不足，不仅需要逻辑和人工智能的技术，还需要对逻辑主体进行研究，只有二者结合才能使机器与人类专家进行良好沟通。

　　5.ILP和并行处理技术
　　面对今天复杂的科学计算、各式各样的图象处理以及大量的信号等问题，提高计算机的运行速度和缩短程序的运行时间至关重要。ILP系统对时间和空间有很高的要求，这使得ILP很难去处理大的数据集。并行处理技术的出现，为ILP处理大数据集提供了解决思路。并行处理系统由多个处理单元组成，通过特定方法可以将一个任务分成若干个子任务，分别由各处理单元完成。目前并行处理技术最显着的是“贝奥武夫簇群技术” （Beowut clusters） 的普遍应用，以及个人计算机、工作站、智能终端并行处理技术的使用。大卫·斯基利康 （David Skillicorn） 在大容量同步并行模型之下发展了一个PROGOL的并行实施技术。艾伦·韦德 （Alanwild） 在贝奥武夫簇群技术基础上，再次进行自上而下的ILP研究。

　　并行处理技术的理想是在处理时间上的一个缩减，这里处理时间是处理程序所用数量的一个线性函数，斜率接近于1.由于程序之间的管理自检和资源的竞争，这个理想很难达到。一个好的并行策略，要求程序之间尽可能地相对独立，尽量使得程序之间拥有较少的交流或资源共享。在测试数据时，在不同的处理器之间派发假设空间。更详细地说，对一个完备的搜索，一个并行ILP方案能够产生一个户主-用户模式，这里户主将不同分段的假设空间指派给用户，然后用户用假设对数据进行测试。用户反馈给户主的所有假设在数据上达到一个预先最小评估值。当用户完成自己的任务时，户主继续指派时空的新程序段，直到整个空间被开发。

　　在用户和户主交流过程中，要考虑每次交流产生数据的成本，还要考虑户主所花费的时间和户主-用户交流的时间。

　　在相对较大的论域中，完备性搜索期望用户和户主之间有尽量少的假设交流。如果户主面对如此快速增长的假设空间片段，能够以这样一个方式将这些片段与用户简洁地交流是可能的；那么整体开销将是低的，处理时间也会缩减，这样也就接近理想的并行处理模式。

　　三、结语
　　
　　人类有对宇宙本源、生命本质、自我本体的好奇，对“机器如何模拟人类思维进行学习和思考”这一问题的探讨，给机器学习添加了自然科学色彩。本文总结了归纳逻辑程序设计的发展现状，对目前ILP发展过程存在的问题进行了详细地阐述。虽然ILP已经在软件工程、计算机网络、生物信息学等众多领域发挥作用，然而应用领域的迫切需求使得ILP仍需与贝叶斯网络、随机搜索、并行处理等技术结合，进一步推动科技的发展，进而为人类的生活带来便利。

　　参考文献：

　　[1] Shan-Hwei,Nienhuys-Cheng,Ronald de Wolf.Foundations of Inductive Logic Programming [M] .SpringerPress,1997.
　　[2] S.Muggleton.Inductive Logic Programming [M] .Academic Press,1992.
　　[3] David Page.ILP:Just Do It [M] .Berlin Heidelberg,2000:3-18.
　　[4] J.Jaffar,M.J.Maher.Constraint Logic Programming [J] .Journal of Logic Programming,1994.
　　[5] Ivan B,Ross K.Applications of Inductive LogicProgramming [J] .SIGART Bulletin,1995.