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

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

基于流形学习的多示例回归算法

多示例学习是一种新型机器学习框架，以往的研究主要集中在多示例分类上，最近多示例回归受到了国际机器学习界的关注．流形学习旨在获得非线性分布数据的内在结构，可以用于非线性降维．文中基于流形学习技术，提出了用于解决多示例同归问题的Mani MIL算法．该算法首先对训练包中的示例降维，利用降维结果出现坍缩的特性对多示例包进行预测．实验表明，Mani MIL算法比现有的多示例算法例如Citation-kNN等有更好的性能．     

多示例学习及其研究现状

较全面地介绍和分析了第4种机器学习框架的多示例学习(MIL)．首先通过数学表达式对多示例学习进行描述，概括了其主要性质；然后总结了目前主要的求解多示例学习问题的算法，剖析了这些算法的主要思想；最后对多示例学习的未来发展作了展望．     

关于“示例学习的最大复合问题及算法”一文的注记

针对"示例学习的最大复合问题及算法"一文(计算机学报,1997,20(2):139-144)中提出的FCV算法给出了一种优化改进。改进的主要思想是省略FCV算法中建立扩张矩阵,寻找公共路径这一步,直接从评价矩阵中记录选择子得到公式,从而生成规则。实验表明,优化后的算法在时间和空间性能上都有提高,其泛化能力明显高于FCV算法。     

多示例学习的示例层次覆盖算法

在多示例学习（Multi-instance learning,MIL）中,核心示例对于包类别的预测具有重要作用。若两个示例周围分布不同数量的同类示例,则这两个示例的代表程度不同。为了从包中选出最具有代表性的示例组成核心示例集,提高分类精度,本文提出多示例学习的示例层次覆盖算法（Multi-instance learning with instance_level covering algorithm,MILICA）。该算法首先利用最大Hausdorff距离和覆盖算法构建初始核心示例集,然后通过覆盖算法和反验证获得最终的核心示例集和各覆盖包含的示例数,最后使用相似函数将包转为单示例。在两类数据集和多类图像数据集上的实验证明,MILICA算法具有较好的分类性能。     

深度逆向强化学习研究综述

深度逆向强化学习是机器学习领域的一个新的研究热点,它针对深度强化学习的回报函数难以获取问题,提出了通过专家示例轨迹重构回报函数的方法。首先介绍了3类深度强化学习方法的经典算法;接着阐述了经典的逆向强化学习算法,包括基于学徒学习、最大边际规划、结构化分类和概率模型形式化的方法;然后对深度逆向强化学习的一些前沿方向进行了综述,包括基于最大边际法的深度逆向强化学习、基于深度Q网络的深度逆向强化学习和基于最大熵模型的深度逆向强化学习和示例轨迹非专家情况下的逆向强化学习方法等。最后总结了深度逆向强化学习在算法、理论和应用方面存在的问题和发展方向。     

通过评估示例中概念的重要性来解决多示例学习问题

在多示例学习问题中,训练数据集里面的每一个带标记的样本都是由多个示例组成的包,其最终目的是利用这一数据集去训练一个分类器,使得可以利用该分类器去预测还没有被标记的包。在以往的关于多示例学习问题的研究中,有的是通过修改现有的单示例学习算法来迎合多示例的需要,有的则是通过提出新的方法来挖掘示例与包之间的关系并利用挖掘的结果来解决问题。以改变包的表现形式为出发点,提出了一个解决多示例学习问题的算法——概念评估算法。该算法首先利用聚类算法将所有示例聚成d簇,每一个簇可以看作是包含在示例中的概念;然后利用原本用于文本检索的TF-IDF(Term Frequency-Inverse Document Frequency)算法来评估出每一个概念在每个包中的重要性;最后将包表示成一个d维向量——概念评估向量,其第i个位置表示第i个簇所代表的概念在某个包中的重要程度。经重新表示后,原有的多示例数据集已不再是"多示例",以至于一些现有的单示例学习算法能够用来高效地解决多示例学习问题。     

基于联合多样性密度的汉语方言辨识

为了解决汉语方言模型设计较为单一的问题,提高方言辨识的效率,提出了一种基于联合多样性密度的汉语方言辨识方法。多样性密度算法是多示例学习中的一种经典算法,联合多样性密度算法是对其的改进应用。该方法首先将方言进行预分类为多个小类,然后将各小类方言进行多示例包生成,并通过期望最大多样性密度算法进行多示例学习,得到的多个多样性密度点作为方言的多示例模型,最后提出平均最近距离算法进行模式分类。该方法在训练模型时得到的方言模型更为全面、完整,在模式分类时考虑了未知包中每个示例的影响,提高了辨识系统的效率。     

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

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

基于多示例学习的局部离群点改进算法

在多示例学习框架下,训练数据集由若干个包组成,包内含有多个用属性-值对形式表示的示例,系统对包内的多个示例进行学习。传统的基于多示例学习的局部离群点检测算法将多示例学习框架运用到数据集上,将多示例问题转化为单示例问题进行处理。但在示例包的转换过程中采用示例内部的特征长度所占比作为权重机制,并没有考察对结果影响较大的示例,分析原因或者动态调整其权重,从而对离群点检测的效果造成影响。针对这一问题,为了充分适应数据内部的分布特征,提出了一种基于多示例学习的局部离群点改进算法FWMIL-LOF。算法采用MIL（Multi-Instance Learning）框架,在示例包的转换过程中引入描述数据重要度的权重函数,通过定义惩罚策略对权重函数做相应调整,从而确定了不同特征属性的示例在所属包中的权重。在实际企业的实时采集监控系统中,通过仿真分析,并与其他经典局部离群点检测算法进行对比,验证了改进算法在离群点检测效果方面的提高。     

小容量网络上的最大流算法

最大流问题是一类经典的组合优化问题。描述了一种小容量网络,这种网络有强的实际应用背景,同时给出了专门解这种网络上最大流问题的算法。该算法比通用的算法快。它已经突破了最大流问题的O（mn)时间障碍,具有较强的理论意义,也为解决许多实际应用问题提供了更有效的算法。同时,由于判断一个网络是否为小容量网络非常简单,因此该算法也具有普遍意义。     

Minimizing the bicriteria of makespan and maximum tardiness with an upper bound on maximum tardiness

This paper studies the flowshop scheduling problem with a complex bicriteria objective function. A weighted sum of makespan and maximum tardiness subject to a maximum tardiness threshold value is to be optimized. This problem, with interesting potential applications in practice, has been sparsely studied in the literature. We propose global and local dominance relationships for the three-machine problem and a fast and effective genetic algorithm (GA) for the more general m$m$-machine case. The proposed GA incorporates a novel three-phase fitness assignment mechanism specially targeted at dealing with populations in which both feasible as well as infeasible solutions might coexist. Comprehensive computational and statistical experiments show that the proposed GA outperforms the two most effective existing heuristics by a considerable margin in all scenarios. Furthermore, the proposed GA is also faster and able to find more feasible solutions. It should be noted that when the weight assigned to maximum tardiness is zero, then the problem is reduced to minimizing makespan subject to a maximum tardiness threshold value. Heuristics for both problems have been provided in the literature recently but they have not been compared. Another contribution of this paper is to compare these recent heuristics with each other.     

网络最大流问题求解的符号ADD增广路径算法

本文通过对网络及网络最大流问题的符号代数判定图（ADD）描述,将网络中的结点和边用ADD隐式表示,并利用Gabow的容量变尺度算法的主要思想,将一般网络最大流问题化为一系列的单位容量网络最大流问题,结合Hachtel等的单位容量网络最大流问题的求解算法,给出了网络最大流问题求解的符号ADD增广路径算法,简称为符号ADD算法.与Dinic算法、Karzanov算法相比,本文算法的空间复杂度得到了改善.实验结果表明,本文算法是切实有效的,且可处理更大规模的问题.     

On Modularity Clustering

Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, particularly in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomerative approach.     

具有切换拓扑结构的非恒等节点复杂网络同步化判据

网络拓扑结构与节点动态在复杂网络的同步化过程中起着关键性的作用,针对具有切换拓扑结构与非恒等节点的同步化问题还没有非常有效的判据.本文研究了具有切换拓扑与非恒等节点的复杂网络同步化问题,针对非恒等节点不存在公共平衡解的情况,选取所有节点的平均状态作为同步化目标,并在此基础上建立起误差动态方程.基于所有外部耦合矩阵可以同时三角化的条件下,构建了低维系统的公共Lyapunov函数,提出了在误差向量范数有界意义下的复杂网络全局同步化判据,保证系统在任意切换策略下实现复杂网络的同步化.最后通过数值仿真验证了结果的有效性.     

Chain packing in graphs

This paper discusses the complexity of packingk-chains (simple paths of lengthk) into an undirected graph; the chains packed must be either vertex-disjoint or edge-disjoint. Linear-time algorithms are given for both problems when the graph is a tree, and for the edge-disjoint packing problem when the graph is general andk = 2. The vertex-disjoint packing problem for general graphs is shown to be NP-complete even when the graph has maximum degree three andk = 2. Similarly the edge-disjoint packing problem is NP-complete even when the graph has maximum degree four andk = 3.     

Primal-dual approximation algorithms for integral flow and multicut in trees

We study the maximum integral multicommodity flow problem and the minimum multicut problem restricted to trees. This restriction is quite rich and contains as special cases classical optimization problems such as matching and vertex cover for general graphs. It is shown that both the maximum integral multicommodity flow and the minimum multicut problem are NP-hard and MAX SNP-hard on trees, although the maximum integral flow can be computed in polynomial time if the edges have unit capacity. We present an efficient algorithm that computes a multicut and integral flow such that the weight of the multicut is at most twice the value of the flow. This gives a 2-approximation algorithm for minimum multicut and a 1/2-approximation algorithm for maximum integral multicommodity flow in trees.     

Chain packing in graphs

This paper discusses the complexity of packingk-chains (simple paths of lengthk) into an undirected graph; the chains packed must be either vertex-disjoint or edge-disjoint. Linear-time algorithms are given for both problems when the graph is a tree, and for the edge-disjoint packing problem when the graph is general andk = 2. The vertex-disjoint packing problem for general graphs is shown to be NP-complete even when the graph has maximum degree three andk = 2. Similarly the edge-disjoint packing problem is NP-complete even when the graph has maximum degree four andk = 3.This is a revised version of the technical report [15].     

On maximum induced matchings in bipartite graphs

The problem of finding a maximum induced matching is known to be NP-hard in general bipartite graphs. We strengthen this result by reducing the problem to some special classes of bipartite graphs such as bipartite graphs with maximum degree 3 or C₄-free bipartite graphs. On the other hand, we describe a new polynomially solvable case for the problem in bipartite graphs which deals with a generalization of bi-complement reducible graphs.     

On-line maximum-order induced hereditary subgraph problems

We first study the competitive ratio for the on‐line version of the problem of finding a maximum‐order induced subgraph satisfying some hereditary property, under the hypothesis that the input graph is revealed by clusters. Next, we focus ourselves on two of the most known instantiations of this problem: the maximum independent set and the maximum clique. Finally, we study a variant of the on‐line maximum‐weight induced hereditary subgraph problem. Our results can also be seen as general reductions, either from off‐line problems to the corresponding on‐line versions, or between on‐line problems. The concept of reduction was absent, until now, from the on‐line computation.