一个有趣的机器学习问题是如何从正的和负的例子集合推断一个布尔函数。这也被称为逻辑分析问题，是归纳推理的一个特例。当系统中没有随机或模糊行为，而人们感兴趣于以一组逻辑规则的形式提取潜在模式时，这个问题是必不可少的。当一个人对获得一组规则感兴趣时，这种知识提取是可取的，而这些规则反过来又能被领域专家容易理解。在许多领域，最终用户缺乏复杂的计算机和建模专业知识。因此，基于神经网络、统计或线性规划等技术的系统并不吸引他们。另一方面，当逻辑分析方法适用时，它可以产生最终用户已经知道的规则(从而增加他/她对该方法的信心)或导致新的发现。
在区分两个模式集的元素方面的最新进展可以是分为六个不同的类别。这些是Kamath等人的归纳推理的子句可满足性方法[1,2];生成小集合的一些改进的分支定界方法.Triantaphyllou等人[3]和Triantaphyllou [4]Boros等人对布尔函数分解的一些改进多项式时间和完备情况[5,6];Wolberg和Mangasarian的线性规划方法[7],Mangasarian等[8]，Mangasarian [9],Shavlik[10]、Fu [11], Goldman等[12]和Cohn等[13]提出了一些基于符号和连接主义(神经网络)机器学习相结合的基于知识的学习方法，最后是Hattori和Tori [14],Kurita [15]， Kamgar-Parsi和Kanal[16]提出的一些最近邻分类方法。从以上六种分类中，前三种可以被认为是逻辑分析方法。
更具体地说，当节点的加权输入超过其阈值时，该算法就会制定规则，并将每种情况转换为规则。然而，这些方法可能需要大量的规则来制定规则[10]。回想一下，重点是尽量减少规则的数量。Towell和Shavlik开发了一种方法，为每个节点产生可理解的规则，同时保持网络的准确性。然而，他们的方法只适用于基于知识的网络，因为它需要将这些权重聚为几个组。基于知识的连接主义通过对神经元权重进行聚类来提高搜索效率。
Fu[11]提出了一种从训练过的神经网络中提取规则的算法。该算法在规则空间中启发式搜索，区分与正、负权重相关的正、负属性。由于搜索过程是一层一层地进行的，因此算法的时间复杂度与网络深度成指数关系。
戈德曼和斯隆[12]研究了自我导向学习方法，在这种方法中，学习者选择训练例子来提供给学习机制。虽然在这类分类方法中，时间复杂度比其他学习机制要少一些，但本质上仍然保持指数复杂度，考察了两个相互关联的问题。在这两个问题中，给出的都是例子的集合。在第一个问题中，每个例子都是一个大小为n的向量(其中n是与当前应用程序相关的二进制属性或原子的数量)，定义在{1,0}空间中的布尔函数应该接受正的例子，而否定的例子应该被拒绝。在第二个问题中，在空格{1,0,*}n中定义了示例，其中' *'代表一个缺失的(例如:未知的)价值。由于例子中缺失的元素的存在，现在有些例子可能是不可分类的（专家不能确定这个例子是肯定的还是否定的)。因此，推断的布尔函数既不接受也不拒绝不可分类的例子。在上述设置中，重点是推断一个在CNF(合取范式)或DNF(析取范式)中的布尔函数，其析取(CNF情况)或连接(DNF情况)的数目非常小，理想最小。当考虑到每个CNE分离对应于单个逻辑规则时，这个方向的动机就变得明显起来。也就是说，到“如果-那么”类型的逻辑结构。
上述子句最小化问题是NP-complete [2]。在过去，第二作者和他的同事[3,4]已经开发了一些有效的(但仍然是指数时间复杂度)分支定界(Bamp;B)方法，可以推断出非常小的布尔函数(CNF或DNF形式)，介绍了两种可以在多项式时间内推断小尺寸布尔函数的随机启发式算法的发展。这两种启发式方法可用于解决前两种研究问题。
规则学习一直是机器学习的重要研究内容,国内外的学者在这一领域已取得了很多成果,主要代表有归纳逻辑程序设计(inductive logic programming)[17]和基于扩张矩阵(extension matrix)[18]的归纳算法等.归纳逻辑程序设计的方法可以产生一阶规则,但其通常比较低效,另外,它需要背景知识,因此在很多情况下难以应用.基于扩张矩阵的方法需要解决两个优化问题,即最小公式(minimum formula, MFL)问题和最小覆盖(minimum cover,MCV)问题.遗憾的是这两个问题都是NP难问题[18],因此,只能采用一些启发式策略以力图获得较好的解.目前一种常用的规则学习算法是C4.5 Rule[19],这一方法通过将C4.5决策树转化成规则,用于规则学习.也有学者将神经网络用于规则学习,例如张朝晖等人[20]在分类精度基本不变的前提下,将训练后的前馈神经网络利用遗传算法进行剪枝,再将其转换为含有若干棵树的森林结构,然后将每棵树看做一个分类器,利用决策树模拟每个分类器的分类过程,最后将决策树结构转化为若干条符号规则.还有一些学者致力于从神经网络中抽取可理解的符号规则[21～22 ],其目的是增强神经网络的可解释性,但其中的一些成果也可用于规则学习.由于将神经网络与规则学习相结合可以产生很好的效果[20],而神经网络集成作为一种新兴的神经计算方法,具有比单一神经网络系统更强的泛化能力,因此,如果将神经网络集成与规则学习相结合,将可望获得更好的效果.在这一思想的基础上提出了一种基于神经网络集成的规则学习算法.以神经网络集成作为规则学习的前端,首先利用其产生规则学习所用的数据集,在产生数据集时,采用能够较好地反映神经网络集成性能的数据生成方式,使得用于规则学习的示例能够受益于神经网络集成的强泛化能力,以最终获得较高的预测精度.
参考文献
1. A.P. Kamath, N. Karmarker, K.G. Ramakrishnan and M.G.C. Resende, A continuous approach to inductive inference, Math. Programming 57 (2), 215-238 (1992).
2. A.P. Kamath, N. Karmarker, K.G. Ramakrishnan and M.G.C. Resende, An interior point approach to Boolean vector function synthesis, In Proceedinas of the 36th MSCAS, 1-5. ,(1994).
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
