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

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

集成学习的泛化误差和AUC分解理论及其在权重优化中的应用1-15

摘要：集成学习是机器学习领域的一个重要分支,其通过整合多个学习器以获得比单个学习器更好的学习效果.多样性和间隔被认为是影响集成学习效果的两个关键因素.现有研究大多是对这两个因素的影响单独进行分析.该文的研究集中于泛化误差、AUC、多样性和间隔之间关系及其在基分类器的权重优化中的应用.该文首先在泛化误差分解理论的基础上,给出了AUC的分解定理.进一步地,该文讨论了泛化误差、AUC、多样性与间隔之间的关系,并指出常用的最大化间隔方法在降低经验误差的同时,也会降低基分类器之间的多样性,进而导致过拟合问题.基于这些理论结果,该文提出了两种新的基分类器的权重优化算法,通过求解一个二次优化问题,实现在准确性和多样性之间的最佳平衡.在35个公开数据集上的实验结果表明,该文所提出的算法在绝大多数情况下都优于现有常用的集成方法.

MN-HDRM:长短兴趣多神经网络混合动态推荐模型16-28

摘要：动态推荐系统通过学习动态变化的兴趣特征来考虑推荐系统中的动态因素,实现推荐任务随着时间变化而实时更新.该文提出一种携带历史元素的循环神经网络(Recurrent Neural Networks,简称RNN)推荐模型负责用户短期动态兴趣建模,而利用基于前馈神经网络(Feedforward Neural Networks,简称FNN)的推荐模型对用户长期兴趣建模.通过两种神经网络的融合,该文构建了一个兼顾用户短期动态兴趣和稳定长期兴趣的多神经网络混合动态推荐模型(Hybrid Dynamic Recommendation Model based on Multiple Neural Networks,简称MN-HDRM).实验结果表明相对于目前比较流行的多种动态推荐算法:TimeSVD++、基于HMM(Hidden Markov Model)的推荐模型、基于RNN(Recurrent Neural Networks)的推荐模型、基于LSTM(Long Short-Term Memory)的推荐模型和STG(Session-based Temporal Graph)推荐模型,MN-HDRM在精确率、召回率和平均倒数排名等多项评价指标上展现出更加优越的性能.

一种基于Shapelets的懒惰式时间序列分类算法29-43

摘要：近些年,时间序列分类问题研究受到了越来越多的关注.基于shapelets的时间序列分类技术是一种有效的方法.然而,其在提取最优shapelet的过程中要建立包含大量冗余元素的候选shapelets集合,一般所获得的shapelets只在平均意义上具有某种鉴别性;与此同时,普通模型往往忽略了待分类实例所具有的局部特征.为此,我们提出了一种依据待分类实例显著局部特征的懒惰式分类模型.这种模型为每个待分类实例构建各自的数据驱动的懒惰式shapelets分类模型,从而逐步缩小了与其分类相关的时间序列搜索空间,使得所获得的shapelets能够直接反映待分类实例的显著局部特征.实验结果表明该文提出的模型具有较高的准确率和更强的可解释性.

一种基于数据流分析的冗余变异体识别方法44-60

摘要：变异测试是一种基于故障的软件测试技术,广泛用来评估测试用例集的充分性与软件测试技术的有效性.尽管变异测试具有较强的故障检测能力,但由于数量庞大的变异体导致了计算开销大的问题,阻碍了变异测试在实践中的广泛应用.为了增强变异测试的实用性,该文从减少变异体数量和缩短变异测试执行时间的角度出发研究变异测试的优化技术,提出冗余变异体的概念和一种基于数据流分析的冗余变异体识别方法.采用11个C程序以经验研究的方式评估了所提冗余变异体识别方法的可行性与有效性.实验结果表明,该文提出的冗余变异体识别方法不仅可以识别出大量的冗余变异体,有效地减少了变异测试执行时间,还提供了一种评价变异算子质量的方法.该文提出的冗余变异体概念及其识别方法可以有效地提高变异测试的效率,并为资源受限的情况下如何选择变异算子进行变异测试提供了指导方针.

基于局部后悔的在线核选择61-72

摘要：在线核选择是在线核学习的关键问题.不同于离线核选择,在线核选择需要在保证亚线性收敛率的同时单趟(one-pass)地进行核选择和假设更新,并且现有在线核选择方法的时间复杂度至少是关于回合数平方的,计算效率较低.针对这些问题,该文提出了一种新的基于局部后悔的在线核选择方法.该方法具有亚线性的后悔界和关于回合数对数的时间复杂度.首先,定义了基于局部后悔的核选择准则(LRC),证明该准则是假设序列期望风险的上界.然后,应用相干性来度量新实例与缓冲区中实例的相关性,并结合蓄水池采样来设计缓冲区实例的添加和删除策略.最后,构造LRC的增量更新方法,并应用在线梯度下降方法来更新假设,实现具有亚线性后悔界的在线核选择和在线核学习的高效算法.实验结果表明,该文所提出的在线核选择方法在保证精度的同时可显著提高核选择的计算效率.

基于异构哈希网络的跨模态人脸检索方法73-84

摘要：该文提出一种基于异构哈希网络的跨模态人脸检索方法.异构哈希网络能够将位于不同空间的人脸图像和人脸视频映射到一个公共且有判别力的二值空间上,以获得有效的二值哈希表示.该网络包含图像分支、视频分支和哈希函数三个部分,首先图像和视频分支分别将人脸图像和人脸视频映射到一个公共空间,然后在公共空间中学习非线性哈希函数.网络的训练使用了三种损失函数:Fisher损失、softmax损失和三元排序损失(triplet ranking loss),其中的Fisher损失关注于公共空间的判别力,softmax损失强调公共空间上表达的可分性,三元排序损失旨在提升最终的检索性能.在多个人脸视频数据集上的跨模态人检索实验结果表明了所提出方法的有效性.

知识系统中全粒度粗糙集及概念漂移的研究85-97

摘要：概念漂移探测是数据流挖掘的一个研究重点,不确定性分析是粗糙集理论的研究核心之一.大数据、数据流中存在不确定变化和概念漂移现象,但是,除F-粗糙集外,几乎所有的粗糙集模型都是静态模型或半动态模型,专注于各种不确定性研究,难以处理不确定性变化,也难以探测概念漂移.结合量子计算、数据流、概念漂移和粗糙集、F-粗糙集的基本观点,以上、下近似为工具,定义了知识系统中的全粒度粗糙集和上、下近似概念漂移,上、下近似概念耦合等概念,探讨了全粒度粗糙集的性质,分析了知识系统内概念的全局变化.全粒度粗糙集继承了Pawlak粗糙集和F-粗糙集的基本思想,以上、下近似簇为工具表示了概念在知识系统内的各种可能变化.用嵌套哈斯图表示了概念不同情况下的同一性和差异性:同一层内的表示没有发生概念漂移,不同层内的表示发生了概念漂移.以正区域为工具,定义了决策表中的全粒度正区域和概念漂移、概念耦合等概念,探究了全粒度正区域的性质,分析了决策表内整体概念的全局变化.全粒度正区域表示了决策表中各种可能情况下的正区域,用嵌套哈斯图表示了正区域簇的同一性和差异性:同一层内没有发生相对于正区域的概念漂移,不同层内发生了相对于正区域的概念漂移.在全粒度粗糙集意义下,定义了全粒度绝对约简、全粒度值约简、全粒度Pawlak约简等属性约简,并探讨其性质.与大部分的属性约简不同(仅仅与并行约简和多粒度约简类似),全粒度属性约简要求概念的所有可能表示不发生概念漂移.进一步探讨了属性约简的优缺点,属性约简使得概念的表示变得单一,冗余属性的存在增加了概念表示的丰富性、多样性.在认识论方面,以粗糙集和粒计算为工具分析了人类认识世界的局部性与全局性,对人类认识世界的方式进行了进一步探�

基于联合概率矩阵分解的群推荐方法研究98-110

摘要：近年来随着互联网的快速发展,各种虚拟社区不断涌现,用户组成群共同活动的现象逐渐增多,人们开始逐渐关注面向群的推荐.已有的群推荐方法大多是在基于内存的协同过滤推荐方法上进行改进,或是认为组内成员相互独立,忽略了群内成员间的关联关系对群推荐结果的影响.为此,该文提出了一种基于联合概率矩阵分解的群推荐方法,更好地对群推荐问题进行建模.首先,利用用户加入的群的信息计算用户之间的相关性,其次,将用户相关性矩阵融入到概率矩阵分解过程中,得到个人预测评分,最后,利用面向群推荐问题中常用的合成策略对个人预测评分进行融合,得到群对项目的预测评分.进一步将该文提出的方法与现有常用的群推荐方法进行比较,在CiteULike数据集上进行实验,实验结果表明,该文所提出的方法在准确率、召回率等多种评价指标上都取得了更好的推荐结果.

手语计算30年:回顾与展望111-135

摘要：手语的自然语言处理是计算机学科中的一项重要任务.目前随着信息技术的飞速发展,以文本和语音为主要载体的传统语言计算的工作重点已从编码、输入方法和字音的研究逐渐转移到语法层面,并进入深度计算的阶段.然而手语信息处理却严重滞后,处于空白起步阶段.究其原因,主要是缺乏用于机器学习的具有一定规模的手语语料库资源,同时传统的语言计算技术也存在不足,这些都阻碍了手语机器翻译、手语问答系统、手语信息检索等信息处理的应用研究.该文首先阐述了手语计算与传统语言计算的本质差异在于空间建模,这种差异导致了前者核心任务是单信道与多信道转换,后者根本任务是消歧.从词法、句法、语义、语用、应用等层面对手语计算进行了回顾,重点介绍了手语机器翻译和分类词谓语计算,指出分类词谓语是手语计算的关键以及取得突破的切入点.从展望的角度,认为互联网时代体感设备的出现、认知神经科学的兴起、深度学习的进展等新技术为手语计算带来了新的机遇.将手语计算与传统语言计算进行比较,分析了手语计算的趋势和未来的研究方向,手语的认知计算是从手势的物理特征到语义表征的映射转换过程,其计算趋势是填补音韵特征、语义单元这样的中间步骤,避免直接从底层特征得到语义概念,关注在手语行为与语言特征的关系上进行机器学习,建立融合空间特征的统计学习模型.未来研究方向包括资源建设、文景转换、隐喻理解,其中文景转换有助于实现空间信息抽取,即物体的空间方向、位置等信息,结合知识库消除自然语言的模糊性,进而实现三维场景构建.指出手语计算正从萌芽期过渡到发展期,若取得重大突破,手语计算将扩展语言计算体系,推动人工智能的发展.

标签增强的中文看图造句136-148

摘要：图像数据飞速增多,而计算机与人对图像数据的理解间存在语义鸿沟.如何有效地理解、管理和组织图像数据是学术界和工业界面临的一个重大挑战.利用计算机自动生成能够描述图像内容的自然语言描述有助于弥合语义鸿沟,从而提升对图像数据的理解.现有工作致力于英文句子生成.与之不同的是,该文实现了一个面向中文的看图造句系统.通过大规模机器翻译克服了中文训练数据缺乏的问题,同时提出了结合中文标签自动预测,对深度模型预测句子进行重排序的增强方法,改善句子生成质量.在两个中文图像句子数据集Flickr8k-cn和Flickr30k-cn上的实验表明,该文提出的标签增强方法可以有效改善现有两种看图造句模型(Google模型和Attention模型)所生成句子的质量.标签增强使得Google模型在Flickr8k-cn测试集上的CIDEr指标从0.474提高到0.503,Flickr30k-cn测试集上的CIDEr指标从0.325提高到0.356.通过标签增强,Attention模型在这两个数据集上的CIDEr分别从0.510提高到0.536,从0.392提高到到0.411.

一种新的基于三维卷积共生梯度直方图和多示例学习的特殊视频检测算法149-163

摘要：已有的基于梯度方向直方图信息的视频内容检测算法侧重在二维的视频帧上提取特征,忽略了视频内容在时间维度上的相关性.提取局部梯度间潜在的共生关系特征可一定程度上提高算法的检测准确率;同时,对相邻特征池化可有效减少特征降维过程中的信息丢失.基于此,利用视频帧间结构信息通过卷积运算构建共生梯度直方图的三维结构,然后对相邻特征池化实现描述特征的有效降维,解决了忽略帧间信息影响识别准确率以及高维度特征难以训练的问题;将视频特征映射到多示例学习中的示例和包,非常容易地实现了对不同长度视频的检测.在公开测试数据集Hockey、Movie上进行测试,实验结果显示,Hockey数据集上算法的检测准确率高于现有最优算法3%,Movie数据集上的检测准确率高于现有最优算法0.5%,验证了新特征与算法的有效性.

语义耦合相关的判别式跨模态哈希学习算法164-175

摘要：基于哈希的跨模态检索以其存储消耗低、查询速度快等优点受到广泛的关注.跨模态哈希学习的核心问题是如何对不同模态数据进行有效地共享语义空间嵌入学习.大多数算法在对多模态数据进行共享空间嵌入的过程中忽略了特征表示的语义判别性,从而导致哈希码表示的类别区分性不强,降低了最近邻搜索的准确性和鲁棒性.该文提出了基于语义耦合相关的判别式跨模态哈希特征表示学习算法.算法在模型的优化目标函数设计上综合了线性判别分类器的思想和跨模态相关性最大化思路,通过引入线性分类器,使得各模态都能够分别学习到各自具有判别性的二进制哈希码.同时利用耦合哈希表示在嵌入语义空间中最大化不同模态之间的相关性,不仅克服了把多种数据投影到一个共同嵌入语义空间的缺陷,而且能够捕捉到不同模态之间的语义相关性.算法在Wiki、LabelMe以及NUS_WID三个基准数据集上与最近相关的算法进行了实验比较.实验结果表明该文提出的方法在检索精度和计算效率上有明显的优势.

轻量级的软件定义网络数据包转发验证176-189

摘要：软件定义网络(Software Defined Network,SDN)引入控制层与转发层分离简化了网络管理和功能部署,近年来得到了广泛的关注.然而,SDN无法检测由于网络攻击或者转发规则的错误实施导致的数据包被错误转发.例如,SDN中转发的数据包会被异常的规则或攻击者丢弃、篡改或注入虚假数据包.此外,由于处于数据层的SDN交换机仅提供了简化的数据转发功能,因此作者无法简单地部署传统IP网络中的数据转发验证方案.因此,作者需要提出一个适用于SDN的有效数据转发验证方案以确保数据包的正确转发.已有SDN转发验证的方案通常通过逐跳验证或者对比全部流的统计信息,这会带来巨大的计算和通信开销.文中基于OpenFlow协议提出了一个轻量级的SDN数据包转发验证方案LPV(Lightweight Packet Forwarding Verification).由于LPV利用SDN本身提供的Packet-in消息机制以及组表读取转发结点的流转发统计值,在检测转发异常行为以及定位异常行为结点的同时,避免了大量读取转发结点状态而引入的计算和通信开销.LPV利用流表规则对入口和出换机进行采样,将采样信息的消息验证码MAC(Message Authentication Code)值和相应的流统计信息上报给控制器.由此,控制器可以通过对比包的MAC值和统计信息来检测网络中的异常转发行为.与此同时,LPV可以通过分析收集的信息找出篡改或丢弃包的结点以定位异常行为的结点.通过基于随机化采样的转发验证机制,LPV有效降低控制器和交换机中引入的处理和通信开销.同时,随机化采样实现了交换机转发状态的一致性检测,任何攻击者都无法通过推断采样来绕过LPV的检测.作者在开源Floodlight控制器和ofsoftware13软件交换机中实现了LPV并在Mininet中进行了仿真实验,实验结果表明LPV能够检测及定位数据包篡改、流量劫持等转发异常行为,同时仅引入了大约10%的平均转发延迟�

一种基于模糊选项关系的关键属性提取方法190-202

摘要：模糊分析方法已广泛应用于医学实践包括对心理疾病的辅助诊断.属性约简方法在过滤冗余信息并提取关键信息时起到了重要作用,使整个临床决策过程更加准确和高效.这些方法抽取的有价值信息可以从新的视角揭示深层次医学知识.很多未经培训的参与者很难识别心理量表中选项间模糊的界线,即很难区分拥有相同意义但程度不同的选项.临床心理学自身的模糊性和心理测量数据的模糊性都将带来噪声.如果将心理测量数据中的属性看作信息系统的条件属性,利用降维算法可提取关键属性,从而简化对疑似患者的临床筛查过程.实际使用时,可对提取的关键属性或者拥有高权重的属性进行重点关注,从而迅速定位拥有异常关键属性的患者,对其优先处理.由此该文提出一种称为FOAD(Fuzzy-Option based Attribute Discriminant method)的基于模糊选项关系的关键属性提取方法,包括三个主要步骤:数据获取、模糊选项的选择与约简以及关键属性的排序与提取.每个参与者样本包含若干身体症状属性,为每个属性都选择一个程度选项.选择模糊选项时须同时考虑选择该选项的样本数量和选项的程度含义.而模糊选项约简算法作为整个方法的核心,可以将模糊选项合并到其他选项,以降低心理测量数据中选项的模糊度.实验中采用两个真实临床数据集验证FOAD算法的性能.首先使用各种属性提取算法对测试数据集进行处理,获取关键属性,然后将输出的关键属性作为条件属性,以诊断结论作为分类标签,利用逻辑回归方法对样本数据进行分类.实验结果表明:FOAD算法在不增加时间复杂度的前提下能将分类准确率普遍提高3.3%-14.1%.虽然选项约简操作造成部分信息的损失,但是合并模糊选项使选项分布更加清晰.FOAD作用下的LDA(Linear Discrimination Analysis)对各种参数敏感,尤其是对保留属性的个数.LDA

自编码神经网络理论及应用综述203-230

摘要：自编码器是深度学习中的一种非常重要的无监督学习方法,能够从大量无标签的数据中自动学习,得到蕴含在数据中的有效特征.因此,自编码方法近年来受到了广泛的关注,已成功应用于很多领域,例如数据分类、模式识别、异常检测、数据生成等.该文对传统自编码基础理论、自编码方法、改进技术以及应用领域进行了比较全面的综述.首先,该文介绍传统自编码基础理论与实现方法,分析自编码器的一般处理框架.然后,讨论现有各种改进的自编码器,分析这些方法的创新点、所要达成的目的和可能存在的问题.随后,该文介绍自编码器的实际应用领域,分析这些领域的代表性自编码算法,并详细地分析、比较和总结这些方法的特点.最后,总结现有方法存在的问题,并探讨了自编码器的将来发展趋势和可能挑战.