知识图谱构建技术综述

谷歌知识图谱技术近年来引起了广泛关注,由于公开披露的技术资料较少,使人一时难以看清该技术的内涵和价值.从知识图谱的定义和技术架构出发,对构建知识图谱涉及的关键技术进行了自底向上的全面解析.1)对知识图谱的定义和内涵进行了说明,并给出了构建知识图谱的技术框架,按照输入的知识素材的抽象程度将其划分为3个层次：信息抽取层、知识融合层和知识加工层;2)分别对每个层次涉及的关键技术的研究现状进行分类说明,逐步揭示知识图谱技术的奥秘,及其与相关学科领域的关系;3)对知识图谱构建技术当前面临的重大挑战和关键问题进行了总结.     

多智能体系构架下的属性图分布式聚类算法

近年来属性图聚类受到了广泛关注,其目的是将属性图中的节点划分到若干簇中,使得每一个集群都有紧密的簇内结构和均匀的属性值。现有的理论主要是假设属性图中的节点或对象是为了协助优化某个给定的方程,而忽略了它们在现实生活中本身的属性。同时,一些开放性问题尚未得到有效解决,如异构信息集成、计算成本高等。为此,把属性图聚类问题理解为自身节点代理的集群形成博弈。为了有效地整合拓扑结构和属性信息,提出了基于紧密性和均匀性约束的节点代理策略选择。进一步证明了博弈过程将会收敛到弱帕累托纳什均衡。在实证方面,设计了一个分布式和异构的多智能体系统,给出了一个快速的分布式学习算法。该算法的主要特点是结果分区的重叠率可以由一个事先给定的阈值控制。最后,在现实社交网络上进行了模拟实验,并与目前先进方法进行比较,结果证实了所提算法的有效性。     

基于刚性图的多智能体编队控制研究

对多智能体编队执行结点扩展、集结、分离等操作后,保持编队队形稳定的问题进行研究。利用代数图论为研究工具,介绍了刚性图和最小刚性图的概念,基于刚性图理论对多智能体编队操作进行形式化描述和数学建模,重点研究了结点增减、编队集结、分离等操作下编队刚性保持的条件,并给出保持编队刚性的理论证明。采用编队控制的形式化建模方法,可对进一步深入编队队形控制算法以及控制器的设计等问题提供编队操作的形式化表达,具有一定的借鉴意义。     

Exploration Strategies for Model-based Learning in Multi-agent Systems: Exploration Strategies

An agent that interacts with other agents in multi-agent systems can benefit significantly from adapting to the others. When performing active learning, every agent's action affects the interaction process in two ways: The effect on the expected reward according to the current knowledge held by the agent, and the effect on the acquired knowledge, and hence, on future rewards expected to be received. The agent must therefore make a tradeoff between the wish to exploit its current knowledge, and the wish to explore other alternatives, to improve its knowledge for better decisions in the future. The goal of this work is to develop exploration strategies for a model-based learning agent to handle its encounters with other agents in a common environment. We first show how to incorporate exploration methods usually used in reinforcement learning into model-based learning. We then demonstrate the risk involved in exploration—an exploratory action taken by the agent can yield a better model of the other agent but also carries the risk of putting the agent into a much worse position.We present the lookahead-based exploration strategy that evaluates actions according to their expected utility, their expected contribution to the acquired knowledge, and the risk they carry. Instead of holding one model, the agent maintains a mixed opponent model, a belief distribution over a set of models that reflects its uncertainty about the opponent's strategy. Every action is evaluated according to its long run contribution to the expected utility and to the knowledge regarding the opponent's strategy. Risky actions are more likely to be detected by considering their expected outcome according to the alternative models of the opponent's behavior. We present an efficient algorithm that returns an almost optimal exploration plan against the mixed model and provide a proof of its correctness and an analysis of its complexity.We report experimental results in the Iterated Prisoner's Dilemma domain, comparing the capabilities of the different exploration strategies. The experiments demonstrate the superiority of lookahead-based exploration over other exploration methods.     

知识图谱构建技术综述

知识图谱在医疗、金融、农业等领域得到快速发展与广泛应用,其可以高效整合海量数据的有效信息,为实现语义智能化搜索以及知识互联打下基础。随着深度学习的发展,传统基于规则和模板的知识图谱构建技术已经逐渐被深度学习所替代。梳理知识抽取、知识融合、知识推理3类知识图谱构建技术的发展历程,重点分析基于卷积神经网络、循环神经网络等深度学习的知识图谱构建方法,并归纳现有方法的优劣性与发展思路。此外,深度学习虽然在自然语言处理、计算机视觉等领域取得了较大成果,但自身存在依赖大规模样本、缺乏推理性与可解释性等缺陷,限制了其进一步发展。为此,对知识图谱应用于深度学习以改善深度学习自身缺陷的相关方法进行整理,分析深度学习的可解释性、指导性以及因果推理性,归纳知识图谱的优势以及发展的必要性。在此基础上,对知识图谱构建技术以及知识图谱应用于深度学习所面临的困难和挑战进行梳理和分析,并对该领域的发展前景加以展望。     

有向图中基于扰动观测器的线性多智能体系统一致性

在有向图中,针对多智能体系统中智能体动力学存在扰动的情形,研究了系统的一致性问题.每个智能体的动力学模型为存在未知外部扰动的一般线性系统.在有向图是强连通的条件下,通过设计一种基于扰动观测器的分布式算法,实现了存在未知扰动的线性多智能体系统的一致性.最后通过仿真验证所提算法的有效性.     

Graph Decomposition for Memoryless Periodic Exploration

We consider a general framework in which a memoryless robot periodically explores all the nodes of a connected anonymous graph by following local information available at each vertex. For each vertex?v, the endpoints of all edges adjacent to v are assigned unique labels within the range?1 to?deg?(v) (the degree of?v). The generic exploration strategy is implemented using a right-hand-rule transition function: after entering vertex v via the edge labeled?i, the robot proceeds with its exploration, leaving via the edge having label [i mod deg?(v)]+1 at v. A lot of attention has been given to the problem of labeling the graph so as to achieve a periodic exploration having the minimum possible length?π. It has recently been proved (Czyzowicz et?al., Proc.?SIROCCO’09, 2009) that $\pi\leq4\frac{1}{3}n$ holds for all graphs of n vertices. Herein, we provide a new labeling scheme which leads to shorter exploration cycles, improving the general bound to π≤4n?2. This main result is shown to be tight with respect to the class of labellings admitting certain connectivity properties. The labeling scheme is based on a new graph decomposition which may be of independent interest.     

图概要技术研究进展

图的概要化,简称图概要,旨在寻找一组简洁的超图或稀疏图,阐明原始图的主要结构信息或变化趋势.当前图概要的研究大多结合原始图的应用领域和背景,使用不同的概要技术构建一个特定的概要图,解决目前大图面临的信息过载、查询优化、空间压缩、影响分析、社交网络可视化等问题.对现有的图概要技术进行了汇总,以概要主要目的作为分类标准划分为基于空间压缩的图概要、基于查询优化的图概要、基于模式可视化的图概要和基于影响分析的图概要四大类,针对部分属性图和无属性图概要算法在真实数据集上进行了相关实验,并从压缩率、信息保持率、信息熵和时间进行对比分析.点明图概要的发展趋势,并指出图概要面临的挑战和可深入探索的研究方向,结合热门的深度学习技术提出了部分有价值的的宏观想法用以解决当前挑战.     

Efficient Relational Techniques for Processing Graph Queries

Graphs are widely used for modeling complicated data such as social networks, chemical compounds, protein interactions and semantic web. To effectively understand and utilize any collection of graphs, a graph database that efficiently supports elementary querying mechanisms is crucially required. For example, Subgraph and Supergraph queries are important types of graph queries which have many applications in practice. A primary challenge in computing the answers of graph queries is that pair-wise comparisons of graphs are usually hard problems. Relational database management systems (RDBMSs) have repeatedly been shown to be able to efficiently host different types of data such as complex objects and XML data. RDBMSs derive much of their performance from sophisticated optimizer components which make use of physical properties that are specific to the relational model such as sortedness, proper join ordering and powerful indexing mechanisms. In this article, we study the problem of indexing and querying graph databases using the relational infrastructure. We present a purely relational framework for processing graph queries. This framework relies on building a layer of graph features knowledge which capture metadata and summary features of the underlying graph database. We describe different querying mechanisms which make use of the layer of graph features knowledge to achieve scalable performance for processing graph queries. Finally, we conduct an extensive set of experiments on real and synthetic datasets to demonstrate the efficiency and the scalability of our techniques.     

基于时间序列的多Agent工作流模型关键技术

针对实际工作中如何将固定的工作流程转化为计算机能够执行和管理的自动化控制问题,提出建立基于时间序列的多Agent工作流模型的方法。通过将任务流程转变成按时间排列的优化序列,开辟进程池,采用多进程同步或异步推进的方式执行,解决工作流分支和聚合引起的同步失调和死锁等问题;结合多Agent进行建模,利用智能Agent单元对进程池进行管理,实现工作流的全程可控;提供基于时间戳的数据并发处理方法,解决数据更新不及时的问题。实际应用表明,该方法实现了对工作流的有效控制,达到了预期目的。     

Piecemeal Graph Exploration by a Mobile Robot

We study how a mobile robot can learn an unknown environment in a piecemeal manner. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every so often to its starting position (for refueling, say). The environment is modeled as an arbitrary, undirected graph, which is initially unknown to the robot. We assume that the robot can distinguish vertices and edges that it has already explored. We present a surprisingly efficient algorithm for piecemeal learning an unknown undirected graph G=(V, E) in which the robot explores every vertex and edge in the graph by traversing at most O(E+V^1+o(1)) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most O(E+V²) edges. We also give an application of piecemeal learning to the problem of searching a graph for a “treasure.”     

Techniques for Edge Stratification of Complex Graph Drawings

We propose an approach that allows a user (e.g., an analyst) to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on stratifying the drawing into layers with desired properties; to this aim, heuristics are presented. The produced layers can be explored and combined by the user to gradually acquire details. We present a user study to test the effectiveness of our approach. Furthermore, we performed an experimental analysis on popular force-directed graph drawing algorithms, in order to evaluate what is the algorithm that produces the smallest number of layers and if there is any correlation between the number of crossings and the number of layers of a graph layout. The proposed approach is useful to explore graph layouts, as confirmed by the presented user study. Furthermore, interesting considerations arise from the experimental evaluation, in particular, our results suggest that the number of layers of a graph layout may represent a reliable measure of its visual complexity. The algorithms presented in this paper can be effectively applied to graph layouts with a few hundreds of edges and vertices. For larger drawings that contain lots of crossings, the time complexity of our algorithms grows quadratically in the number of edges and more efficient techniques need to be devised. The proposed approach takes as input a layout produced by any graph drawing algorithm, therefore it can be applied in a variety of application domains. Several research directions can be explored to extend our framework and to devise new visualization paradigms to effectively present stratified drawings.     

面向知识图谱的信息抽取技术综述

互联网时代, 数据呈爆发式的增长, 怎样从这些数据中抽取出有用的信息, 已是人工智能研究中的一个核心问题. 知识图谱作为解决这一问题的重要方法, 已成为人工智能技术发展的核心推动力. 信息抽取是知识图谱构建过程中的首要环节, 它实现了从海量的数据中抽取出结构化实体以及实体之间的关系. 本文探讨知识图谱中信息抽取的发展趋势, 对实体抽取、关系抽取和事件抽取及其关键技术进行了综述, 分析和讨论了当前存在的问题、挑战以及未来发展的方向.     

事件知识图谱构建技术与应用综述

知识图谱以图结构表示丰富灵活的语义,描述客观世界的事物及其关系,在应用领域得到了广泛的关注。事件知识图谱聚焦动态事件及其间的顺承、时序和因果关系,并以结构化的图形式表示,对海量数据更高效地管理。尤其是对动态事件信息和事件逻辑关系的挖掘,对认识客观世界发展规律,助力领域多种智能应用有着重要的意义。本文系统阐述事件知识图谱的构建技术,包括事件知识表示、事件知识抽取、事件关系抽取,并介绍事件知识图谱在领域的典型应用,最后介绍现阶段的挑战与研究展望。     

图聚集技术的现状与挑战

图聚集技术旨在获取能够涵盖原图大部分信息的简洁超图,用于提炼概要信息、解决存储消耗和社交隐私保护等问题.对当前的图聚集技术进行研究,综述了现有图聚集技术中的分组方法并对其进行分类,将分组标准划分为基于属性一致性、基于邻接分组一致性、基于关联强度一致性、基于邻接顶点一致性和基于零重建误差这5类;在高层次上将各分组标准概括为基于属性、基于结构和同时基于属性和结构的图聚集.较为全面地总结和分析了当前图聚集技术的研究现状和进展,并探讨了未来研究的方向.     

Generalizing the TT-transform

The TT-transform is a method of dividing a primary time series into a set of secondary, time-localized time series, through use of a translatable, scalable Gaussian window. These secondary time series resemble ordinary windowed time series, except that higher frequencies are more strongly concentrated around the midpoint of the Gaussian, as compared with lower frequencies. In this paper the TT-transform is generalized to accommodate arbitrary scalable windows. The generalized TT-transform can be useful in resolving the times of event initiations when used jointly with a related time–frequency distribution, the generalized S-transform.     

Generalizing Version Spaces

Although a landmark work, version spaces have proven fundamentally limited by being constrained to only consider candidate classifiers that are strictly consistent with data. This work generalizes version spaces to partially overcome this limitation. The main insight underlying this work is to base learning on version-space intersection, rather than the traditional candidate-elimination algorithm. The resulting learning algorithm, incremental version-space merging (IVSM), allows version spaces to contain arbitrary sets of classifiers, however generated, as long as they can be represented by boundary sets. This extends version spaces by increasing the range of information that can be used in learning; in particular, this paper describes how three examples of very different types of information—ambiguous data, inconsistent data, and background domain theories as traditionally used by explanation-based learning—can each be used by the new version-space approach.     

面向知识图谱约束问答的强化学习推理技术

知识图谱问答任务通过问题分析与知识图谱推理,将问题的精准答案返回给用户,现已被广泛应用于智能搜索、个性化推荐等智慧信息服务中.考虑到关系监督学习方法人工标注的高昂代价,学者们开始采用强化学习等弱监督学习方法设计知识图谱问答模型.然而,面对带有约束的复杂问题,现有方法面临两大挑战:(1)多跳长路径推理导致奖励稀疏与延迟;(2)难以处理约束问题推理路径分支.针对上述挑战,设计了融合约束信息的奖励函数,能够解决弱监督学习面临的奖励稀疏与延迟问题;设计了基于强化学习的约束路径推理模型COPAR,提出了基于注意力机制的动作选择策略与基于约束的实体选择策略,能够依据问题约束信息选择关系及实体,缩减推理搜索空间,解决了推理路径分支问题.此外,提出了歧义约束处理策略,有效解决了推理路径歧义问题.采用知识图谱问答基准数据集对COPAR的性能进行了验证和对比.实验结果表明:与现有先进方法相比,在多跳数据集上性能相对提升了2%-7%,在约束数据集上性能均优于对比模型,准确率提升7.8%以上.     

医学知识图谱构建技术与研究进展

医学知识图谱是实现智慧医疗的基石,有望带来更高效精准的医疗服务。然而,现有知识图谱构建技术在医学领域中普遍存在效率低,限制多,拓展性差等问题。针对医疗数据跨语种,专业性强,结构复杂等特点,对构建医学知识图谱的关键技术进行了自底向上的全面解析,涵盖了医学知识表示、抽取、融合和推理以及质量评估五部分内容。此外,还介绍了医学知识图谱在信息检索、知识问答、智能诊断等医疗服务中的应用现状。最后,结合当前医学知识图谱构建技术面临的重大挑战和关键问题,对其发展前景进行了展望。     

Generalizing rational degree elevation

A generalization of the well-known degree elevation algorithms for Bézier curves is presented. This generalized degree elevation extends the expressive power of rational polynomials. In particular, it allows a given curve to be represented equivalently by a family of control point and weight distributions, without affecting its parameterization. Some control over the control point distribution is demonstrated. The effects of reparameterization in conjunction with degree elevation are also explored, and techniques for detecting degeneracy in the presence of reparameterization are described.