基于贝叶斯估计的概念语义相似度算法

传统的基于语义距离的概念语义相似度算法不能兼顾客观统计数据,基于信息量的相似度算法又难以获得权威统计样本,针对这些不足,该文提出一种基于贝叶斯估计的概念语义相似度算法。该算法首先假定概念出现概率是符合Beta分布的随机变量,然后基于语义距离的相似度算法计算先验参数,并根据统计样本计算该先验分布下基于最小风险的贝叶斯估计后验参数。随后利用基于信息量的语义相似度算法,便可获得主观经验与客观事实相结合的概念语义相似度。结合WordNet的实验分析表明,该算法与人为主观经验之间具有最大的相关系数。     

融合多重实例关系的无监督跨模态哈希检索

大多数跨模态哈希检索方法仅使用余弦相似度进行特征匹配,计算方式过于单一,没有考虑到实例的关系对于性能的影响.为此,提出一种基于多重实例关系图推理的方法,通过构造相似度矩阵,建立全局和局部的实例关系图,充分挖掘实例之间的细粒度关系.在多重实例关系图的基础上进行相似度推理,首先分别进行图像模态和文本模态关系图内部的推理,然后将模态内的关系映射到实例图中进行推理,最后执行实例图内部的推理.此外,为了适应图像和文本两种模态的特点,使用分步训练策略训练神经网络.在MIRFlickr和NUS-WIDE数据集上实验表明,提出的方法在mAP指标上具有很明显的优势,在Top-k-Precision曲线上也获得良好的效果.这也说明所提方法对实例关系进行深入挖掘,从而显著地提升检索性能.     

Supporting sketch-based retrieval from a library of reusable behaviours

Building the behaviour for non-player characters in a game is a complex collaborative task among AI designers and programmers. In this paper we present a visual authoring tool for game designers that supports behaviour reuse. We describe a visual editor, capable of storing, indexing, retrieving and reusing behaviours previously designed by AI programmers. One of the most notable features of our editor is its capability for sketch-based retrieval: searching in a repository for behaviours that are similar to the one the user is drawing, and making suggestions about how to complete it. As this process relies on graph behaviour comparison, in this paper, we describe different algorithms for graph comparison, and demonstrate, through empirical evaluation in a particular test domain, that we can provide structure-based similarity for graphs that preserves behaviour similarity and can be computed at reasonable cost.     

基于数据集分割的云工作流模型库并行检索方法

在由多个行业云服务平台组成的集成服务平台中,随着行业云服务平台加盟数及各平台下租户数量的不断增多,其底层的云工作流模型库的规模也必将不断增大.当云工作流模型库的规模超大时,需要一种效率更高的并行检索方法去满足云工作流模型库高效检索的需求.鉴于此,文章将采用均匀划分法或自动聚类法对大规模云工作流模型库进行合理的子集划分,并结合前期工作中已改进的基于图结构的流程检索算法,提出基于数据集分割的大规模云工作流模型库并行检索方法.该方法主要包括4种流程并行检索算法：基于均匀划分模型集的静态并行检索算法、基于均匀划分模型集的动态并行检索算法、基于自动聚类模型集的静态并行检索算法及基于自动聚类模型集的动态并行检索算法.最后,在模拟生成的大规模流程集及真实的云工作流模型库中对这4种并行检索算法的检索效率进行实验评估.     

Reasoning about pictures and similarity retrieval for image information systems based on SK-set knowledge representation

Spatial reasoning and similarity retrieval are two important functions of any image information system. Good spatial knowledge representation for images is necessary to adequately support these two functions. In this paper, we propose a new spatial knowledge representation, called the SK-set based on morphological skeleton theories. Spatial reasoning algorithms which achieve more accurate results by directly analysing skeletons are described. SK-set facilitates browsing and progressive visualization. We also define four new types of similarity measures and propose a similarity retrieval algorithm for performing image retrieval. Moreover, using SK-set as a spatial knowledge representation will reduce the storage space required by an image database significantly.     

基于UML的构件检索

基于构件的软件开发（CBD）是当前大型软件系统开发方法的主流,而CBD的基础是构件库及其检索方法。目前主要采用从领域梃型中获得特定领域知识辅助用户进行构件检索,但缺乏较好的领域模型表示方法。本文对使用UML表示领域模型进行了研究,提出了一个利用UML和领域词典中的领域知识辅助用户刻画领域、扩充和求精初始查询、形成用户的构件需求并指导构件库检索,通过行为相似性确定构件的构件检索方法。该方法增强了用户对领域知识的了解,在检索过程中充分考虑了与构件相关的领域知识、检索上下文以及用户的意图,可对结果集进行有效筛选评优,极大地提高了查全率、查准率及用户的满意度。为了验证该方法的可行性和有效性,设计并实现了一个高效的构件检索环境。     

Generalized median graph computation by means of graph embedding in vector spaces

The median graph has been presented as a useful tool to represent a set of graphs. Nevertheless its computation is very complex and the existing algorithms are restricted to use limited amount of data. In this paper we propose a new approach for the computation of the median graph based on graph embedding. Graphs are embedded into a vector space and the median is computed in the vector domain. We have designed a procedure based on the weighted mean of a pair of graphs to go from the vector domain back to the graph domain in order to obtain a final approximation of the median graph. Experiments on three different databases containing large graphs show that we succeed to compute good approximations of the median graph. We have also applied the median graph to perform some basic classification tasks achieving reasonable good results. These experiments on real data open the door to the application of the median graph to a number of more complex machine learning algorithms where a representative of a set of graphs is needed.     

基于触发序列集合的过程模型行为相似性算法

过程模型的相似性计算是业务过程管理中不可缺少的任务,广泛应用于组织合并、用户需求变更、模型仓库管理等多个场景.对基于主变迁序列的相似性度量方法 PTS进行研究,并提出了改进方案.通过定义完整触发序列表示模型行为,基于A*算法结合剪枝策略实现触发序列集合间的映射,进而完成模型相似性计算.实验结果表明:该方法较主流的基于模型行为相似性算法,计算合理性有很大提升.     

A new approach to applicable memory-based reasoning

To appropriately utilize the rapidly growing amount of data and information is a big challenge for people and organizations. Standard information retrieval methods, using sequential processing combined with syntax-based indexing and access methods, have not been able to adequately handle this problem. We are currently investigating a different approach, based on a combination of massive parallel processing with case-based (memory-based) reasoning methods. Given the problems of purely syntax-based retrieval methods, we suggest ways of incorporating general domain knowledge into memory-based reasoning. Our approach is related to the properties of the parallel processing microchip MS160, particularly targeted at fast information retrieval from very large data sets. Within this framework different memory-based methods are studied, differing in the type and representation of cases, and in the way that the retrieval methods are supported by explicit general domain knowledge. Cases can be explicitly stored information retrieval episodes, virtually stored abstractions linked to document records, or merely the document records themselves. General domain knowledge can be a multi-relational semantic network, a set of term dependencies and relevances, or compiled into a global similarity metric. This paper presents the general framework, discusses the core issues involved, and describes three different methods illustrated by examples from the domain of medical diagnosis.     

并行任务图的优化调度算法

科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对Fork-Join类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。     

A workflow net similarity measure based on transition adjacency relations

Many activities in business process management, such as process retrieval, process mining, and process integration, need to determine the similarity or the distance between two processes. Although several approaches have recently been proposed to measure the similarity between business processes, neither the definitions of the similarity notion between processes nor the measure methods have gained wide recognition. In this paper, we define the similarity and the distance based on firing sequences in the context of workflow nets (WF-nets) as the unified reference concepts. However, to many WF-nets, either the number of full firing sequences or the length of a single firing sequence is infinite. Since transition adjacency relations (TARs) can be seen as the genes of the firing sequences which describe transition orders appearing in all possible firing sequences, we propose a practical similarity definition based on the TAR sets of two processes. It is formally shown that the corresponding distance measure between processes is a metric. An algorithm using model reduction techniques for the efficient computation of the measure is also presented. Experimental results involving comparison of different measures on artificial processes and evaluations on clustering real-life processes validate our approach.     

An abstract model of service discovery and binding

We propose a formal operational semantics for service discovery and binding. This semantics is based on a graph-based representation of the configuration of global computers typed by business activities. Business activities execute distributed workflows that can trigger, at run time, the discovery, ranking and selection of services to which they bind, thus reconfiguring the workflows that they execute. Discovery, ranking and selection are based on compliance with required business and interaction protocols and optimisation of quality-of-service constraints. Binding and reconfiguration are captured as algebraic operations on configuration graphs. We also discuss the methodological implications that this model framework has on software engineering using a typical travel-booking scenario. To the best of our knowledge, our approach is the first to provide a clear separation between service computation and discovery/instantiation/binding, and to offer a formal framework that is independent of the SOA middleware components that act as service registries or brokers, and the protocols through which bindings and invocations are performed.     

基于二分图的装配体检索研究

基于事例推理是解决DFA和装配工艺规划问题的有效方法,装配体检索是应用此方法的关键步骤．对装配体中的联结关系进行表达和分类,提出联结关系定量的比较方法,基于二分图理论建立了装配体之间的相似计算模型,给出了装配体检索过程和计算实例．     

基于行为特征的语义工作流修正算法

工作流修正是工作流重用的重要任务.目前在基于工作流的可重用片段——stream的语义工作流修正中,当工作流stream库中不存在与检索语义工作流中的工作流stream结构相似的stream时,无法修正检索工作流.针对这种情况,提出了一种改进方案——基于stream行为特征修正语义工作流.使用任务紧邻关系集表达stream的行为特征.对于检索语义工作流中的每个与变更请求不一致的stream,使用锚集合数据索引和stream匹配规则对工作流stream库过滤得到候选匹配stream集;之后基于stream的行为相似性和变更请求对候选stream集进行验证,得到与变更请求一致程度最高和足够相似的匹配stream;然后更新变更请求,使用每个检索到的匹配stream替换原stream以逐步修正检索语义工作流中的缺陷;最后得到修正语义工作流.实验结果表明,与现有的基于工作流stream的修正算法相比,本文的算法得到了整体质量更好的修正语义工作流集,其适应性更好.该修正算法能为业务过程管理人员为适应新业务需求的工作流建模提供较好质量的修正语义工作流供参考,对提高工作流重用的效率和质量有较大帮助.     

Influence-based model decomposition for reasoning about spatially distributed physical systems

Many important science and engineering applications, such as regulating the temperature distribution over a semiconductor wafer and controlling the noise from a photocopy machine, require interpreting distributed data and designing decentralized controllers for spatially distributed systems. Developing effective computational techniques for representing and reasoning about these systems, which are usually modeled with partial differential equations (PDEs), is one of the major challenge problems for qualitative and spatial reasoning research.

This paper introduces a novel approach to decentralized control design, influence-based model decomposition, and applies it in the context of thermal regulation. Influence-based model decomposition uses a decentralized model, called an influence graph, as a key data abstraction representing influences of controls on distributed physical fields. It serves as the basis for novel algorithms for control placement and parameter design for distributed systems with large numbers of coupled variables. These algorithms exploit physical knowledge of locality, linear superposability, and continuity, encapsulated in influence graphs representing dependencies of field nodes on control nodes. The control placement design algorithms utilize influence graphs to decompose a problem domain so as to decouple the resulting regions. The decentralized control parameter optimization algorithms utilize influence graphs to efficiently evaluate thermal fields and to explicitly trade off computation, communication, and control quality. By leveraging the physical knowledge encapsulated in influence graphs, these control design algorithms are more efficient than standard techniques, and produce designs explainable in terms of problem structures.     

Spatial reasoning and similarity retrieval for image database systems based on RS-strings

In this paper, we propose a rotation-invariant spatial knowledge representation called RS-string. Then we present the string generation algorithm to automatically generate RS-strings for segmented pictures. We also propose the spatial reasoning and similarity retrieval algorithms based on RS-strings. The similarity retrieval algorithm is much more flexible than all previous 2D string representations because our approach can consider every possible view of a query picture. Thus the system does not require the user to provide a query picture which must have the same orientation as that of a database picture. Finally, we provide several examples to demonstrate the capabilities of spatial reasoning and similarity retrieval based on the RS-string representation.     

Efficient model-checking of weighted CTL with upper-bound constraints

We present a symbolic extension of dependency graphs by Liu and Smolka in to model-check weighted Kripke structures against the computation tree logic with upper-bound weight constraints. Our extension introduces a new type of edges into dependency graphs and lifts the computation of fixed-points from boolean domain to nonnegative integers to cope with the weights. We present both global and local algorithms for the fixed-point computation on symbolic dependency graphs and argue for the advantages of our approach compared to the direct encoding of the model-checking problem into dependency graphs. We implement all algorithms in a publicly available tool and evaluate them on several experiments. The principal conclusion is that our local algorithm is the most efficient one with an order of magnitude improvement for model checking problems with a high number of “witnesses”.     

基于领域本体的软构件检索

为了提高刻面分类检索软构件的查准率,结合领域本体,提出了支持自然语言检索的软构件检索过程模型.该模型抽象了领域知识,形成领域本体库,用于匹配用户检索使用的自然语言,提供领域内一致认可的检索术语.该术语然后与软构件描述库中的软构件描述术语进行匹配,进而从软构件库中检索软构件.软构件描述库采用了刻面分类方法.ATS软构件检索实验结果表明,较之于传统的刻面分类方法,该检索策略既提高了检索精度,又增强了检索的灵活性.     

基于领域本体的概念语义相似度计算研究

通过对领域本体参照下传统概念的3种语义相似度的计算模型研究,针对这3种计算模型的优缺点和领域本体所特有的性质,提出了一种改进的基于领域本体的概念语义相似度计算模型.实验结果表明,该计算模型通过定量的分析利用本体构词所描述的概念、特性之间的相似度,可以指导基于领域知识本体的语义查询中概念集扩充和查询结果排序,为概念之间的语义关系提供一种有效的量化.     

基于语义检索的构件库系统体系结构

语义检索是解决目前构件查准率和查全率不高的最好方法之一。该文研究了基于语义检索的构件库技术,能在构件入库时完成基于本体的构件语义描述,在检索时复用领域本体,实现构件隐含语义推理和匹配,检索出传统算法难以检索到的构件,为设计实现具体面向语义检索的构件库系统提供了一个参考模型。