示例学习的最大复合问题及算法

本文证明了示例学习中的最大复合问题是ＮＰ难题，给出了求解最大复问题的近似算法，并将此示例学习算法应用于手写数学识别。实验证明，基于最大复合的学习算法和ＡＱ１５相比，速度快，得到的公式少、匹配精度高。     

基于示例选择的目标跟踪改进算法

多示例学习是一种处理包分类问题的新型学习模式,传统基于多示例学习的目标跟踪算法在自适应获取正包时受到无益或有害示例的干扰,不能很好地提取目标的鉴别性特征.为此,设计基于核密度估计的示例选择方法,剔除训练集中的无益示例或有害示例,提高多示例学习算法的有效性,并在此基础上提出一种基于示例选择的目标跟踪改进算法,针对负示例占多数的情况建立核密度估计函数来精简正包中的示例,使用精简后的样本数据进行训练学习,最终实现对目标的实时跟踪.实验结果表明,该算法在光照变化、目标部分遮挡及形体变化等情形下都具有较好的稳健性.     

一种基于多示例学习的图像检索方法

由于多示例学习能够有效处理图像的歧义性,因此被应用于基于内容的图像检索(CBIR).本文提出一种基于多示例学习的CBIR方法.该方法将图像作为多示例包,使用基于自组织特征映射网络聚类的方法分割图像,并将由颜色和纹理特征描述的图像区域作为包中示例.根据用户选择的实例图像生成正包和反包,使用多示例学习算法进行学习,实现图像检索和相关反馈.实验结果表明这种方法与已有方法检索效果相当,但检索效率更高.     

基于多示例学习的高分辨率遥感影像面向对象分类

多示例学习以示例组成的包作为训练样本,学习的目的是预测新包的类型。从分类角度上,处理问题的策略类似于以均质对象为基本处理单元的面向对象影像分类。针对两者之间理论和方法相似性,将多样性密度多示例学习算法与面向对象方法相结合用于高分辨率遥感图像分类。以图像分割方法获取均值对象作为示例,利用多样性密度算法对样本包进行学习获取最大多样性密度示例,最后根据相似性最大准则对单示例包或是经聚类算法得到的新包进行类别标记,以获取最终分类结果。通过与SVM分类器的比较,发现多样性密度算法的平均分类精度都在70%以上,最高可达96%左右,且对小样本问题学习能力更强,结果表明多示例学习在遥感图像分类中有着广泛应用前景。     

敏感视频判别性特征投影识别算法

网络的快速发展在给人们生活带来很多便利的同时,也存在着令人反感的敏感内容,如恐怖暴力视频等,这些内容严重影响着青少年的身心健康.因此,一种有效的敏感视频识别算法成为网络过滤技术中不可或缺的组成部分.近年来,多示例学习被引入到恐怖暴力类敏感视频识别中,并取得了令人瞩目的效果.由于该类视频中存在着很多冗余信息及部分非恐怖暴力帧的干扰,不可避免地影响了敏感视频的识别效果.因此提出了一种基于判别性特征投影的多示例学习算法,提出了一种基于自表示字典学习的示例选择框架,将示例作为字典,学习示例之间的最优表达关系,找到具有代表性的示例,并向代表示例进行投影构造了更具判别性的示例包特征.通过在恐怖暴力视频库以及VSD2014数据集上与现有多示例检测算法在准确率、召回率以及F_1指标的对比,验证了该算法在恐怖暴力视频识别中的有效性.     

Fretcit-kNN算法性能分析

1引言 上世纪90年代中期,多示例学习这个概念在Dietterich等人[1]对药物活性预测问题的研究中被首先提出.凭借其独特的性质和广泛的应用前景,多示例学习被认为是和监督学习、非监督学习、强化学习并列的一种学习框架[2].和监督学习相比,多示例学习中的训练集不再是由若干示例组成,取而代之的是一组带有概念标记的包(bag),每一个包是若干没有概念标记的示例集合.如果一个包中至少存在一个正例,则该包被标记为正包;如果一个包不含有任何正例,则该包为反包.学习系统通过对已经标定类别的包进行学习来建立模型,希望尽可能正确地预测不曾遇到过的包的概念标记.     

弱监督多示例子概念学习的遥感场景分类

遥感场景分类是近年来计算机视觉和表示学习领域的热门研究课题,其主要工作是基于学习到的特征信息自动分类图像场景.传统上场景分类方法忽略了场景中多个子概念的学习,进而影响到场景语义识别.为了解决上述问题,文中提出一种弱监督多示例子概念学习(Weakly Supervised Multi-Instance Sub-concept Learning)的遥感场景分类方法.首先,基于弱监督定位网络从逐类响应图中预测峰值坐标,以定位感兴趣的示例区域;其次,将峰值坐标信息回溯到卷积层,自动截取多个示例特征组成示例袋作为多示例聚合网络的输入.然后,在多示例聚合网络上嵌入一个子概念层,迭代学习子概念与示例之间的匹配分数,再将所有的示例进行聚合生成示例袋概率分数;最后,组合两个损失函数,联合训练整个网络,得到富于判别的分类模型.在AID、NWPU-RESISC45和CIFAR10/100数据集上进行了分类实验,结果表明,所提方法有效提高了遥感场景分类性能.     

融合包空间和示例空间特征的多示例学习

多示例学习中,包空间特征描述包容易忽略包中的局部信息,示例空间特征描述包容易忽略包的整体结构信息.针对上述问题,提出融合包空间特征和示例空间特征的多示例学习方法.首先建立图模型表达包中示例之间的关系,将图模型转化为关联矩阵以构建包空间特征;其次筛选出正包中与正包的类别的相关性比较强的示例和负包中与正包的类别的相关性比较弱的示例,将示例特征分别作为正包和负包的示例空间特征;最后用Gaussian RBF核将包空间和示例空间特征映射到相同的特征空间,采用基于权重的特征融合方法进行特征融合.在多示例的基准数据集、公开的图像数据集和文本数据集上进行实验的结果表明,该方法提高了分类效果.     

基于多部位多示例学习的人体检测

基于部位的检测方法能处理多姿态及部分遮挡的人体检测,多示例学习能有效处理图像的多义性,被广泛应用于图像检索与场景理解中.文中提出一种基于多示例学习的多部位人体检测方法.首先,根据人体生理结构将图像分割成若干区域,每个区域包含多个示例,利用AdaBoost多示例学习算法来训练部位检测器.然后利用各部位检测器对训练样本进行测试得到其响应值,从而将训练样本转化为部位响应值组成的特征向量.再用SVM方法对这些向量进行学习,得到最终的部位组合分类器.在INRIA数据集上的实验结果表明该方法能改进单示例学习的检测性能,同时评价3种不同的部位划分及其对检测性能的影响.     

基于全局和局部标签相关性的MIMLSVM改进算法

多示例多标记学习是用多个示例来表示一个对象,同时该对象与多个类别标记相关联的新型机器学习框架.设计多示例多标记算法的一种方法是使用退化策略将其转化为多示例学习或者是多标记学习,最后退化为传统监督学习,然后使用某种算法进行训练和建模,但是在退化过程中会有信息丢失,从而影响到分类准确率.MIMLSVM算法是以多标记学习为桥梁,将多示例多标记学习问题退化为传统监督学习问题求解,但是该算法在退化过程中没有考虑标记之间的相关信息,本文利用一种既考虑到全局相关性又考虑到局部相关性的多标记算法GLOCAL来对MIMLSVM进行改进,实验结果显示,改进的算法取得了良好的分类效果.     

Toward effective knoledge acquisition with first-order logic induction

Knowledge acquisition with machine learning techniques is a fundamental requirement for knowledge discovery from databases and data mining systems. Two techniques in particular — inductive learning and theory revision — have been used toward this end. A method that combines both approaches to effectively acquire theories (regularity) from a set of training examples is presented. Inductive learning is used to acquire new regularity from the training examples; and theory revision is used to improve an initial theory. In addition, a theory preference criterion that is a combination of the MDL-based heuristic and the Laplace estimate has been successfully employed in the selection of the promising theory. The resulting algorithm developed by integrating inductive learning and theory revision and using the criterion has the ability to deal with complex problems, obtaining useful theories in terms of its predictive accuracy.     

Some extensions of radial basis functions and their applications in artificial intelligence

Radial Basis Functions have recently found interesting applications in Artificial Intelligence, and in particular in the problem of learning to perform a particular task from a set of examples. However, in many practical cases the Radial Basis Functions method cannot be applied in a straight-forward manner, because it does not take into account some features that are typical of the problem of learning from examples. In this paper, we show some extensions of the standard theory, introduced in order to deal with a large number of examples and with problems in which different variables play very different roles. We present some examples and also point out some open problems.     

Learning rules from incomplete training examples by rough sets

Machine learning can extract desired knowledge from existing training examples and ease the development bottleneck in building expert systems. Most learning approaches derive rules from complete data sets. If some attribute values are unknown in a data set, it is called incomplete. Learning from incomplete data sets is usually more difficult than learning from complete data sets. In the past, the rough-set theory was widely used in dealing with data classification problems. In this paper, we deal with the problem of producing a set of certain and possible rules from incomplete data sets based on rough sets. A new learning algorithm is proposed, which can simultaneously derive rules from incomplete data sets and estimate the missing values in the learning process. Unknown values are first assumed to be any possible values and are gradually refined according to the incomplete lower and upper approximations derived from the given training examples. The examples and the approximations then interact on each other to derive certain and possible rules and to estimate appropriate unknown values. The rules derived can then serve as knowledge concerning the incomplete data set.     

结构化学习的噪声可学习性分析及其应用

噪声可学习性理论指出,有监督学习方法的性能会受到训练样本标记噪声的严重影响.然而,已有相关理论研究仅针对二类分类问题.致力于探究结构化学习问题受噪声影响的规律性.首先,注意到在结构化学习问题中,标注数据的噪声会在训练过程中被放大,使得训练过程中标记样本的噪声率高于标记样本的错误率.传统的噪声可学习性理论并未考虑结构化学习中的这一现象,从而低估了问题的复杂性.从结构化学习问题的噪声放大现象出发,提出了新的结构化学习问题的噪声可学习性理论.在此基础上,提出了有效训练数据规模的概念,这一指标可用于在实践中描述噪声学习问题的数据质量,并进一步分析了实际应用中的结构化学习模型在高噪声环境下向低阶模型回退的情况.实验结果证明了该理论的正确性及其在跨语言映射和协同训练方法中的应用价值和指导意义.     

主动学习的多标签图像在线分类

目的在多标签有监督学习框架中,构建具有较强泛化性能的分类器需要大量已标注训练样本,而实际应用中已标注样本少且获取代价十分昂贵。针对多标签图像分类中已标注样本数量不足和分类器再学习效率低的问题,提出一种结合主动学习的多标签图像在线分类算法。方法基于min-max理论,采用查询最具代表性和最具信息量的样本挑选策略主动地选择待标注样本,且基于KKT(Karush-Kuhn-Tucker)条件在线地更新多标签图像分类器。结果在4个公开的数据集上,采用4种多标签分类评价指标对本文算法进行评估。实验结果表明,本文采用的样本挑选方法比随机挑选样本方法和基于间隔的采样方法均占据明显优势;当分类器达到相同或相近的分类准确度时,利用本文的样本挑选策略选择的待标注样本数目要明显少于采用随机挑选样本方法和基于间隔的采样方法所需查询的样本数。结论本文算法一方面可以减少获取已标注样本所需的人工标注代价;另一方面也避免了传统的分类器重新训练时利用所有数据所产生的学习效率低下的问题,达到了当新数据到来时可实时更新分类器的目的。     

THE DISCIPLE–RKF LEARNING AND REASONING AGENT

Over the years we have developed the Disciple theory, methodology, and family of tools for building knowledge-based agents. This approach consists of developing an agent shell that can be taught directly by a subject matter expert in a way that resembles how the expert would teach a human apprentice when solving problems in cooperation. This paper presents the most recent version of the Disciple approach and its implementation in the Disciple–RKF (rapid knowledge formation) system. Disciple–RKF is based on mixed-initiative problem solving , where the expert solves the more creative parts of the problem and the agent solves the more routine ones, integrated teaching and learning , where the agent helps the expert to teach it, by asking relevant questions, and the expert helps the agent to learn, by providing examples, hints, and explanations, and multistrategy learning , where the agent integrates multiple learning strategies, such as learning from examples, learning from explanations, and learning by analogy, to learn from the expert how to solve problems. Disciple–RKF has been applied to build learning and reasoning agents for military center of gravity analysis, which are used in several courses at the US Army War College.     

From inductive inference to algorithmic learning theory

We present two phenomena which were discovered in pure recursion-theoretic inductive inference, namely inconsistent learning (learing strategies producing apparently “senseless” hypotheses can solve problems unsolvable by “reasonable” learning strategies) and learning from good examples (“much less” information can lead to much more learning power). Recently, it has been shown that these phenomena also hold in the world of polynomial-time algorithmic learning. Thus inductive inference can be understood and used as a source of potent ideas guiding both research and applications in algorithmic learning theory.     

Machine Learning on the Basis of Formal Concept Analysis

A model of machine learning from positive and negative examples (JSM-learning) is described in terms of Formal Concept Analysis (FCA). Graph-theoretical and lattice-theoretical interpretations of hypotheses and classifications resulting in the learning are proposed. Hypotheses and classifications are compared with other objects from domains of data analysis and artificial intelligence: implications in FCA, functional dependencies in the theory of relational data bases, abduction models, version spaces, and decision trees. Results about algorithmic complexity of various problems related to the generation of formal concepts, hypotheses, classifications, and implications.     

关于互信息准则在分类(包括拒识类别)问题中的应用

不同于传统的基于性能为评价指标的机器学习方法, 基于互信息评价准则的学习方法显示出了独到的优越性. 但是, 如何理解互信息概念在分类问题中的具体内涵与应用特点仍然是不明确的. 本文推导了归一化互信息与包括拒识类别分类矩阵的显式表达关系. 给出了归一化互信息在极值情况下的三个相关定理, 以及在二值分类情况下误差敏感度分析方程. 为互信息与传统分类性能指标作出了初步理论方面解释. 通过给出的若干简单实例, 讨论了互信息概念及评价准则在分类问题中的基本应用特点及相关问题.     

Complexity–Based Induction

A central problem in inductive logic programming is theory evaluation. Without some sort of preference criterion, any two theories that explain a set of examples are equally acceptable. This paper presents a scheme for evaluating alternative inductive theories based on an objective preference criterion. It strives to extract maximal redundancy from examples, transforming structure into randomness. A major strength of the method is its application to learning problems where negative examples of concepts are scarce or unavailable. A new measure called model complexity is introduced, and its use is illustrated and compared with a proof complexity measure on relational learning tasks. The complementarity of model and proof complexity parallels that of model and proof–theoretic semantics. Model complexity, where applicable, seems to be an appropriate measure for evaluating inductive logic theories.