计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2019年第03期杂志 文档列表

深度卷积神经网络的发展及其在计算机视觉领域的应用453-482

摘要：作为类脑计算领域的一个重要研究成果,深度卷积神经网络已经广泛应用到计算机视觉、自然语言处理、信息检索、语音识别、语义理解等多个领域,在工业界和学术界掀起了神经网络研究的浪潮,促进了人工智能的发展.卷积神经网络直接以原始数据作为输入,从大量训练数据中自动学习特征的表示.卷积神经网络具有局部连接、权值共享和池化操作等特性,可以有效降低网络复杂度,减少训练参数的数目,使模型对平移、扭曲、缩放具有一定程度的不变性.目前,深度卷积神经网络主要是通过增加网络的层数,使用更大规模的训练数据集,以及改进现有神经网络的网络结构或训练学习算法等方法,来模拟人脑复杂的层次化认知规律,拉近与人脑视觉系统的差距,使机器获得“抽象概念”的能力.深度卷积神经网络在图像分类、目标检测、人脸识别、行人再识别等多个计算机视觉任务中都取得了巨大成功.该文首先回顾了卷积神经网络的发展历史,简单介绍了M-P神经元模型、Hubel-Wiesel模型、神经认知机、用于手写识别的LeNet以及用于ImageNet图像分类比赛的深度卷积神经网络.然后详细分析了深度卷积神经网络的工作原理,介绍了卷积层、采样层、全连接层的数学表示及各自发挥的作用.接着该文重点从以下三个方面介绍卷积神经网络的代表性成果,并通过实例展示各种技术方法对图像分类精度的提升效果.从增加网络层数方面,讨论并分析了AlexNet、ZF-Net、VGG、GoogLeNet和ResNet等经典卷积神经网络的结构;从增加数据集规模方面,介绍了人工增加标注样本的难点以及使用数据扩增技术对神经网络性能提升的作用;从改进训练方法方面,介绍了包括L2正则化、Dropout、DropConnect、Maxout等常用的正则化技术,Sigmoid函数、tanh函数以及ReLU函数、LReLU函数、PReLU函数等常用的神经元激

基于ReliefF剪枝的多标记分类算法483-496

摘要：多标记分类问题需要为每个实例分配多个标记.常见的多标记分类方法主要分为算法转换法和问题转换法两类.合理利用标记间的依赖关系是提升多标记分类性能的关键.在该文中,作者从不同的问题转化方法的角度,将标记间依赖关系的利用方法分为标记分组法和属性空间扩展法两种.作者发现,对于属性空间扩展法,普遍存在的难题在于如何对标记间的依赖关系进行准确度量,并选择合适的标记集合加入到属性空间中.在此基础上,作者提出了一种基于ReliefF剪枝的多标记分类算法(ReliefF based Stacking,RFS).算法从属性选择的角度,利用ReliefF方法对标记间的依赖关系进行度量,进而选择依赖关系较强的标记加入到原始属性空间中.在9个多标记基准数据集上的实验结果显示,RFS算法相较于当下流行的多标记分类算法具有较为明显的优势.

融合关联矩阵自学习和显式秩约束的数据表示分簇算法497-512

摘要：复杂异构分布的高维数据在大数据时代随处可见,高效地挖掘其子空间结构并进行准确的分簇是机器视觉和模式识别领域的研究热点.低秩表示算法(Low-Rank Representation,LRR)因其优越的低维子空间挖掘能力而备受关注,其性能很大程度上取决于关联矩阵的构建,常见的方法都是通过原始输入数据或表示系数直接一次成形.然而,这些方法都采用独立的步骤进行表示系数计算以及关联矩阵学习,无法保证总体算法的最优性.针对该问题,该文提出一种新的LRR型数据表示分簇法(Data Representation Clustering,DRC)应用于实际子空间分割问题.首先,为实现模型的快速求解,DRC保留了基本数据表示框架中的光滑正则项并剔除了非负性、稀疏性等复杂约束;其次,将相似度矩阵的自适应学习策略添加至统一的数据表示框架,联合原始输入数据和表示系数确保目标关联矩阵在无噪环境下具备明确的对角分布结构.最后,对关联矩阵对应的Laplacian矩阵添加一种新的秩约束,在含噪环境下引导相似度连接结构与簇目标数的一致性.采用交替更新法对模型进行求解,保证目标函数单变量优化的全局最优性以及整体收敛性.人工合成数据和8个公开数据集的实验结果表明,DRC算法在分簇精度、归一化互信息、参数敏感性等指标上都具有优秀的性能.

大图中全部极大团的并行挖掘算法研究513-531

摘要：该文的目的在于优化现有的大图数据中全部极大团挖掘算法.在生物网络、社会网络及web分析中,找出图中的全部极大团是一个重要的应用.随着图数据规模的增大,传统的极大团挖掘算法因无法满足性能要求而被并行处理方式取代.但是,在现有的并行处理方法中,需要过滤大量的重复极大团和检测非极大团,降低了算法的性能.论文在分析了现有的极大团并行算法后,提出了新的大图中全部极大团挖掘算法.首先,使用顶点的偏序关系消除了冗余极大团以及非极大团的产生;第二,根据两个极大团之间至少存在一对无边的顶点的特征,提出了多颜色顶点涂色分片算法,将大图的顶点分为全色和半色两个集合;第三,证明了涂色分片算法是NP完全问题以及有一个多项式时间的2近似算法,并给出了近似算法;第四,基于多色顶点分片实现了一个并行的全部极大团挖掘算法,该算法只对全色顶点与它的邻接顶点组成重叠子图进行极大团挖掘;最后,对算法的性能以及加速比特性进行了评价,得出该算法能够处理百万个节点的大图并且性能比现有的算法有较大提高的实验结果.

一种采用模型学习和经验回放加速的正则化自然行动器评判器算法532-553

摘要：行动器评判器(Actor Critic,简称AC)算法是强化学习连续动作领域的一类重要算法,其采用独立的结构表示策略,但更新策略时需要大量样本导致样本效率不高.为了解决该问题,提出了基于模型学习和经验回放加速的正则化自然AC算法(Regularized Natural AC with Model Learning and Experience Replay,简称RNAC-ML-ER).RNAC-ML-ER将Agent与环境在线交互产生的样本用于学习系统动态性对应的线性模型和填充经验回放存储器.将线性模型产生的模拟样本和经验回放存储器中存储的样本作为在线样本的补充,实现值函数、优势函数和策略的更新.为了提高更新的效率,在每个时间步,仅当模型的预测误差未超过阈值时才利用该模型进行规划,同时根据TD-error从大到小的顺序对经验回放存储器中的样本进行回放.为了降低策略梯度估计的方差,引入优势函数参数向量对优势函数进行线性近似,在优势函数的目标函数中加入2-范数进行正则化,并通过优势函数参数向量来对策略梯度更新,以促进优势函数和策略的收敛.在指定的两个假设成立的条件下,通过理论分析证明了所提算法RNAC-ML-ER的收敛性.在4个强化学习的经典问题即平衡杆、小车上山、倒立摆和体操机器人中对RNACML-ER算法进行实验,结果表明所提算法能在大幅提高样本效率和学习速率的同时保持较高的稳定性.

基于索引树的带通配符序列模式挖掘算法554-565

摘要：随着有序时间序列数据的出现,序列模式挖掘成为数据挖掘领域的一个分支.其中带通配符的序列模式挖掘又是该领域中一个重要的研究问题,同时随着数据规模越来越大,算法的挖掘效率尤为重要.现有算法多采用树型结构来实现数据的压缩表示,树的结构和模式匹配方法对挖掘效率有决定性的影响.该文首先设计一个新的树结构索引树I-Tree(Index-Tree)来维护原始序列数据以及序列模式和模式索引信息;然后在索引树的基础上,提出一个新的带通配符的序列模式挖掘算法ITM(Index-Tree based sequential pattern Mining).算法ITM主要用4个策略提高算法的挖掘效率:(1)将原始序列中相同项压缩到一个节点上,该节点只记录项在原始序列中的索引;(2)采用迭代的方式,长度k+1的序列模式是用长度k(k>0)的候选序列模式产生;(3)采用前缀树的结构,逐层将k+1的候选序列模式压缩到索引树上,叶子节点上记录序列模式最后一项的索引;(4)整个挖掘过程,只用一棵索引树.算法ITM通过采用以上索引树压缩原始序列数据以及存储候选序列模式,有效地缩小搜索空间,从而算法效率得到显著提升.另一种提高挖掘效率的思路,是在挖掘过程中允许有小部分的模式丢失,来换取挖掘效率的大幅度提升,即所谓的近似模式挖掘.该文也给出了一个近似序列模式挖掘算法AITM(Approximate Index-Tree based sequential pattern Mining),该近似算法通过估计超序列模式的支持数,将非候选节点提前删掉,减少索引树上的节点个数,从而提高算法的时空效率;但是也因为估计的支持数可能会小于实际值,从而丢失了部分频繁的序列模式.该文实验中,提出的两个算法分别与算法MGCS、MAPB和MAPD进行了对比实验,采用3个典型数据序列进行测试,并设计了3组实验:(1)不同的最小支持度对算法的效率影响;(2)算法的扩展性;(3)通配符长度对算法效率�

模板驱动的神经机器翻译566-581

摘要：由于神经机器翻译模型简单、通用和有效,神经机器翻译模型已成为目前最受关注的机器翻译模型.在神经机器翻译模型中,通过引入词汇翻译表和短语翻译表可以提高翻译质量.然而,对于已经存在的人工整理的翻译模板或者启发式算法生成的翻译模板,目前已有的神经机器翻译框架不存在有效的方法对这些翻译模板进行建模.该文研究的主要内容是将翻译模板内嵌到端到端的神经机器翻译模型中.为此,我们提出了模板驱动的神经机器翻译模型,该模型通过使用额外的模板编码器对翻译模板进行端到端建模,通过使用知识门阀和注意力门阀动态地控制解码过程中不同来源的知识对当前解码词汇的贡献度的大小.知识门阀的主要作用是对源语言句子和翻译模板的信息进行有效的表示,从而更好地对解码器进行初始化.注意力门阀是一个基于时序的门阀,可以动态地控制当前翻译词汇接收源语言句子或者翻译模板信息的多少.最终实验结果表明,该文提出的方法对模板进行了有效的建模,20%词汇标准模板在汉英和英汉翻译任务上的翻译正确率分别高达93.6%和95.1%.与基线翻译系统相比,在汉英和英汉翻译任务上使用含有20%词汇的标准模板时,翻译性能可以增长4.2~7.2个BLEU值.当翻译模板中的真实词汇增加时,翻译质量得到进一步提升.

面向大图的可达性查询处理算法582-595

摘要：图的可达性查询处理是生物信息领域的热点问题之一,用于测定蛋白质交互网络中任意两个蛋白质分子间是否存在交互作用.针对已有在可达查询比例增大时在线搜索算法效率下降明显及性能不稳定的问题,提出优化的OPT-R算法.首先,提出最优生成树的概念,使得采用最优生成树的OPT-R算法可以在常量时间回答更多的可达查询;同时提出基于栈的互逆拓扑顺序,使得OPT-R可以在常量时间回答更多的不可达查询.作者还提出相应的最优生成树及互逆拓扑顺序生成算法,并通过实验对基于20个不同规模的真实数据集从不同角度对算法的高效性进行了验证.

面向不均衡医学数据集的疾病预测模型研究596-609

摘要：基于临床表现的疾病预测模型是临床决策支持系统(Clinical Decision Support System,CDSS)的一个重要研究内容.现有临床决策支持系统往往将临床病例作为训练数据集,以临床表现的描述文字为特征,采用统计机器学习方法构建疾病预测模型.然而,在医疗领域往往存在着样本数据集不均衡的问题,导致模型的预测效果降低.欠采样技术是目前解决样本不均衡问题的常用手段.其主要采用一定的方法从多数类样本中抽取部分样本,与少数类样本组成平衡数据集后再构建模型.现有的欠采样方法往往可以显著提高模型对少数类样本的召回率,然而其通常也会造成模型准确率的降低,从而限制了预测模型的整体提升效果.为此,该文提出了一种新的基于迭代提升欠采样的集成分类方法(Under-Sampling with Iteratively Boosting,USIB),该方法迭代地从多数类样本中进行欠抽样,构建多组弱分类器,并采用加权组合方式将这些弱分类器构成一个强分类器,从而提升样本不平衡条件下单种疾病预测效果.另外,医学病例样本数据集通常是多类别、多标签的,为此,该文将多个单种疾病的预测模型进行组合构成一个多标签疾病预测模型,以满足临床意义上的多病种以及并发症的诊断.为了进一步提升多标签预测模型的效果,该文设计了一种基于标签最大互信息生成树的标签选择方法(Labels Selection method based on Maximum Mutual Information Spanning Tree,LS-MMIST),该方法根据原始数据集的分布构建标签之间的最大互信息生成树,在每一次的样本预测阶段,借助树中疾病标签之间的关系确定最终的预测标签集合.实验方面,该文首先选择三种公开的不均衡二分类数据集和我们私有的四种稀有疾病的数据集,对该文提出的迭代提升欠采样方法进行性能评估.其次,分别对比了该文提出的多标签预测模型与现有的多标签预测技术在

同步有界偏序自动机610-623

摘要：所有状态都能被同一个字转换到同一状态(完全确定有限状态)的自动机称为同步自动机.同步自动机在许多方面都有着广泛的应用,如重启装置的设计、系统测试、编码、工业自动化、机器人技术以及生物计算等.同步自动机研究的最基本的问题是自动机的同步性问题,同步性问题主要包括同步性检测和同步字查找.最短同步字问题是同步自动机研究的核心课题,关于这个问题,?erny提出了如下猜想:所有n-状态同步自动机的最短同步字长度的上确界为(n-1)~2.现有研究结果表明,对于某些特殊类型的自动机?erny猜想是成立的,例如循环自动机、欧拉自动机等.然而,对于一般的同步自动机?erny猜想尚未得到证实或否定.由于任何自动机都能看作偏序自动机,因而?erny猜想成立的充分必要条件是它对所有偏序自动机都成立.单演自动机和广义单演自动机等偏序自动机都已被证实满足?erny猜想.作为偏序自动机的另一类特殊情形,该文定义了有界偏序自动机,运用组合分析方法证明了n-状态有界偏序自动机最短同步字的长度为n-1.作为主要结果的推论,得出n-状态格序自动机的最短同步字的长度也是n-1.这就意味着有界偏序自动机(特别是格序自动机)满足?erny猜想.进一步地,该文设计了有界偏序自动机的同步性检测及同步字查找算法.最后,该文还对单演自动机、广义单演自动机和有界偏序自动机的关系进行了讨论,得出以下结论:广义单演自动机和有界偏序自动机同为单演自动机的真推广,且它们的表达能力不相容.

连续型演化算法首达时间分析的平均增益模型624-635

摘要：连续型演化算法(Evolutionary Algorithms,EAs)的计算时间分析(Runtime analysis)是演化计算理论研究中的难点和热点问题,相较于离散型演化算法,有关前者的理论结果相对较少,数学基础较为薄弱.该文引入鞅论和停时理论,建立了平均增益模型,以估算连续型演化算法的平均首达时间(Expected First Hitting Time,EFHT)上界.平均增益模型建立在一个非负随机过程的基础上,不依赖于算法具体的实现形式.论文介绍了如何应用该模型进行连续型演化算法的计算时间分析.作为案例分析,研究分析了:(1)带自适应步长的非精英(1,λ)ES(Evolution Strategy)求解球函数问题的平均首达时间,得到了3维情形下的时间上界的闭合表达式,并讨论了确保算法收敛条件下步长与子代种群规模λ之间的关系;(2)(1+λ)ES求解2维倾斜平面问题的平均首达时间,得到了上界的闭合表达式.数值实验的结果表明实际的平均首达时间与理论计算的上界吻合.理论分析和实验结果表明平均增益模型有助于获得连续型演化算法平均首达时间紧致的上界,为连续型演化算法的计算时间分析提供了一种新的有效方法.

基于多重门限机制的异步深度强化学习636-653

摘要：近年来,深度强化学习已经成为人工智能领域一个新的研究热点.深度强化学习在如Atari 2600游戏等高维度大状态空间任务中取得了令人瞩目的成功,但仍存在训练时间太长等问题.虽然异步深度强化学习通过利用多线程技术大幅度减少了深度强化学习模型所需的训练时间,但是,基于循环神经网络的异步深度强化学习算法依然需要大量训练时间,原因在于具有记忆能力的循环神经网络无法利用并行化计算加速模型训练过程.为了加速异步深度强化学习模型的训练过程,并且使得网络模型具有记忆能力,该文提出了一种基于多重门限机制的异步优势行动者-评论家算法.该模型主要有三个特点:一是通过使用多重门限机制使前馈神经网络具有记忆能力,使Agent能够通过记忆不同时间步的状态信息做出更优的决策;二是通过利用并行计算进一步加速Agent的训练过程,减少模型所需的训练时间;三是通过采用一种新的跳跃连接方式实现数据向更深的网络层传递,增强模型识别状态特征的能力,从而提升深度强化学习算法的稳定性和学习效果.该文通过Atari 2600游戏平台上的部分战略型游戏以及稀疏奖赏环境型游戏来评估新模型的性能.实验结果表明,与传统的异步深度强化学习算法相比,新模型能够以较少的时间代价来获得更优的学习效果.

从文本中构建领域本体技术综述654-676

摘要：本体是一种重要的知识库,其包含的丰富的语义信息可以为问答系统、信息检索、语义Web、信息抽取等领域的研究及相关应用提供重要的支持.因而,如何快速有效地构建本体具有非常重要的研究价值.研究者们分别从不同角度提出了大量有效地进行本体构建的方法.一般来讲,这些本体构建方法可以分为手工构建的方法和采用自动、半自动技术构建的方法.手工本体的方法往往需要本体专家参与到构建的整个过程,存在着构建成本高、效率低下、主观性强、移植不便等缺点,因而,此类方法正逐步被大量基于自动、半自动技术的本体构建方法所代替.自动、半自动构建的方法不需要(或仅需少量)人工参与,可以很方便地使用其它研究领域(如机器学习、自然语言处理等)的最新研究成果,也可以方便地使用不同数据源进行本体构建.其中,文本数据源具有数据量大、获取方便的优点.因而,越来越多的研究者开始关注如何有效地使用文本资源进行本体构建.该文全面分析了以文本为数据源,采用自动、半自动技术进行本体构建的国内外最新研究成果.该文首先介绍了当前一些具有代表性的关于以文本为数据源进行本体构建的技术综述文章.在这一部分内容中,该文重点关注了各个综述文章针对本体构建技术研究所得出的结论.接着,该文从“全局”与“局部”两个角度对本体构建方法进行了详细的介绍.在“全局”角度介绍中,该文根据本体构建过程中用到的主导技术,将本体构建方法分为统计主导的方法和语言分析主导的方法两类,分别对各类方法进行了详细的介绍,并分析了各类方法的优缺点.在“局部”角度介绍中,该文把本体构建过程分为以下子任务:术语抽取、概念抽取、关系(包括层次关系和非层次关系)抽取、本体形成.分别从每个任务所使用的技术,从“任务-