Three-valued abstraction for probabilistic systems

This paper proposes a novel abstraction technique for fully probabilistic systems. The models of our study are classical discrete-time and continuous-time Markov chains (DTMCs and CTMCs, for short). A DTMC is a Kripke structure in which each transition is equipped with a discrete probability; in a CTMC, in addition, state residence times are governed by negative exponential distributions. Our abstraction technique fits within the realm of three-valued abstraction methods that have been used successfully for traditional model checking. The key ingredients of our technique are a partitioning of the state space combined with an abstraction of transition probabilities by intervals. It is shown that this provides a conservative abstraction for both negative and affirmative verification results for a three-valued semantics of PCTL (Probabilistic Computation Tree Logic). In the continuous-time setting, the key idea is to apply abstraction on uniform CTMCs which are readily obtained from general CTMCs. In a similar way as for the discrete case, this is shown to yield a conservative abstraction for a three-valued semantics of CSL (Continuous Stochastic Logic). Abstract CTMCs can be verified by computing time-bounded reachability probabilities in continuous-time MDPs.     

Three-valued diagnosable systems: Diagnosability,optimal design and fault identification algorithm

A three-valued model for computer system diagnosis is proposed in this paper. A subsystem is regurded as composed of two components, a task processor and a communication processor. Accordingly, subsystem faults are classified as type 1 or type 1/2 faults, representing subsystem faults with communication processors being faulty or those with communication processors being fault-free, The concepts of virtual tests andt ¹ /t ^1/2 fault diagnosis are introduced. Andt ¹ /t ^1/2 fault diagnosis with centralized control and that with distributed control are studied respectively. The problems addressed here include diagnosability, optimal design and fault identification algorithm. The results show clearly thatt ¹ /t ^1/2 fault diagnosis can afford to identify significantly more faults thant-fault diagnosis under the same structural constraint.     

Three-valued completion for abductive logic programs

In this paper, we propose a three-valued completion semantics for abductive logic programs, which solves some problems associated with the Console et al. two-valued completion semantics. The semantics is a generalization of Kunen's completion semantics for general logic programs, which is known to correspond very well to a class of effective proof procedures for general logic programs. Secondly, we propose a proof procedure for abductive logic programs, which is a generalization of a proof procedure for general logic programs based on constructive negation. This proof procedure is sound and complete with respect to the proposed semantics. By generalizing a number of results on general logic programs to the class of abductive logic programs, we present further evidence for the idea that limited forms of abduction can be added quite naturally to general logic programs.     

Analyzing time-dimension communication characterizations for representative scientific applications on supercomputer systems

Exascale computing is one of the major challenges of this decade, and several studies have shown that communications are becoming one of the bottlenecks for scaling parallel applications. The analysis on the characteristics of communications can effectively aid to improve the performance of scientific applications. In this paper, we focus on the statistical regularity in time-dimension communication characteristics for representative scientific applications on supercomputer systems, and then prove that the distribution of communication-event intervals has a power-law decay, which is common in scientific interests and human activities. We verify the distribution of communication-event intervals has really a power-lawdecay on the Tianhe-2 supercomputer, and also on the other six parallel systems with three different network topologies and two routing policies. In order to do a quantitative study on the power-law distribution, we exploit two groups of statistics: bursty vs. memory and periodicity vs. dispersion. Our results indicate that the communication events show a “strong-bursty and weak-memory” characteristic and the communication event intervals show the periodicity and the dispersion. Finally, our research provides an insight into the relationship between communication optimizations and time-dimension communication characteristics.     

三值量子基本门及其对量子Fourier变换的电路实现

理论上可以把量子基本门组合在一起来实现任何量子电路和构建可伸缩的量子计算机。但由于构建量子线路的量子基本门数量庞大,要正确控制这些量子门十分困难。因此,如何减少构建量子线路的基本门数量是一个非常重要和非常有意义的课题。提出采用三值量子态系统构建量子计算机,并给出了一组三值量子基本门的功能定义、算子矩阵和量子线路图。定义的基本门主要包括三值量子非门、三值控制非门、三值Hadamard门、三值量子交换门和三值控制CR_k门等。通过把量子Fourier变换推广到三值量子态,成功运用部分三值量子基本门构建出能实现量子Fourier变换的量子线路。通过定量分析发现,三值量子Fourier变换的线路复杂度比二值情况降低了至少50%,表明三值量子基本门在降低量子计算线路复杂度方面具有巨大优势。     

Identifying representative users in matrix factorization-based recommender systems: application to solving the content-less new item cold-start problem

Matrix factorization has proven to be one of the most accurate recommendation approaches. However, it faces one major shortcoming: the latent features that result from the factorization are not directly interpretable. Providing interpretation for these features is important not only to help explain the recommendations presented to users, but also to understand the underlying relations between the users and the items. This paper consists of 2 contributions. First, we propose to automatically interpret features as users, referred to as representative users. This interpretation relies on the study of the matrices that result from the factorization and on their link with the original rating matrix. Such an interpretation is not only performed automatically, as it does not require any human expertise, but it also helps to explain the recommendations. The second proposition of this paper is to exploit this interpretation to alleviate the content-less new item cold-start problem. The experiments conducted on several benchmark datasets confirm that the features discovered by a Non-Negative Matrix Factorization can be interpreted as users and that representative users are a reliable source of information that allows to accurately estimate ratings on new items. They are thus a promising way to solve the new item cold-start problem.     

Towards capturing representative AS-level Internet topologies

Recent studies on AS-level Internet connectivity have attracted considerable attention. These studies have exclusively relied on BGP data from the Oregon route-views [University of Oregon Route Views Project, http://www.routeviews.org] to derive some unexpected and intriguing results. The Oregon route-views data sets reflect AS peering relationships, as reported by BGP, seen from a handful of vantage points in the global Internet. The possibility that these data sets may provide only a very sketchy picture of the complete inter-AS connectivity of the Internet has received little scrutiny. By augmenting the Oregon route-views data with BGP summary information from a large number of Internet Looking Glass sites and with routing policy information from Internet Routing Registry (IRR) databases, we find that (1) a significant number of existing AS peering relationships remain hidden from most BGP routing tables, (2) the AS peering relationships with tier-1 ASs are in general more easily observed than those with non-tier-1 ASs, and (3) there are at least about 40% more AS peering relationships in the Internet than commonly-used BGP-derived AS maps reveal (but only about 4% more ASs). These findings point out the need for continuously questioning the applicability and completeness of data sets at hand when establishing the generality of any particular Internet-specific observation and for assessing its (in)sensitivity to deficiencies in the measurements.     

An optimal representative set selection method

The optimal representative set selection problem is defined thus: given a set of test requirements and a test suite that satisfies all test requirements, find a subset of the test suite containing a minimum number of test cases that still satisfies all test requirements. Existing methods for solving the representative set selection problem do not guarantee that obtained representative sets are optimal (i.e. minimal). The enhanced zero–one optimal path set selection method [C.G. Chung, J.G. Lee, An enhanced zero–one optimal path set selection method, Journal of Systems and Software, 39(2) (1997) 145–164] solves the so-called optimal path set selection problem, and can be adapted to solve the optimal representative set selection problem by considering paths as test cases and components to be covered (e.g. branches) as test requirements.     

Selective clustering for representative paintings selection

Multimedia Tools and Applications - Selective classification (or rejection based classification) has been proved useful in many applications. In this paper we describe a selective clustering...     

基于代表点的快速聚类算法

针对传统的层次聚类算法每次迭代只将距离最小的那对类簇合并,容易受离群点影响,偏向于发现凸状或球状簇等缺点,受CURE算法启发,采用簇中固定数量代表点来代表簇对象进行距离的计算,并结合90_10规则,提出了一种改进的层次聚类算法REPBFC（REpresentative Points Based Fast Clustering）,实验表明该算法是有效的。     

Comparing representative selection strategies for dissimilarity representations

Many of the computational intelligence techniques currently used do not scale well in data type or computational performance, so selecting the right dimensionality reduction technique for the data is essential. By employing a dimensionality reduction technique called representative dissimilarity to create an embedded space, large spaces of complex patterns can be simplified to a fixed‐dimensional Euclidean space of points. The only current suggestions as to how the representatives should be selected are principal component analysis, projection pursuit, and factor analysis. Several alternative representative strategies are proposed and empirically evaluated on a set of term vectors constructed from HTML documents. The results indicate that using a representative dissimilarity representation with at least 50 representatives can achieve a significant increase in classification speed, with a minimal sacrifice in accuracy, and when the representatives are selected randomly, the time required to create the embedded space is significantly reduced, also with a small penalty in accuracy. © 2006 Wiley Periodicals, Inc. Int J Int Syst 21: 1093–1109, 2006.     

群体智能典型算法研究综述

群体智能是指无智能的或具有简单智能的个体通过协作表现出群体智能行为的特性,它在没有集中控制且不提供全局模型的前提下,为寻找复杂的分布式问题求解方案提供了基础。群体智能潜在的并行性和分布式特征使之成为计算机领域一个重要的研究方向。在介绍群体智能模型的基础上,分别对基于该模型的蚁群优化算法和粒子群优化算法这两类代表性算法进行较为详尽的归纳阐述并进行比较,最后就目前应用最为广泛的蚁群算法对群体智能的发展趋势进行展望。     

Finding representative landmarks of data on manifolds

Data-driven non-parametric models, such as manifold learning algorithms, are promising data analysis tools. However, to fit an off-training-set data point in a learned model, one must first “locate” the point in the training set. This query has a time cost proportional to the problem size, which limits the model's scalability. In this paper, we address the problem of selecting a subset of data points as the landmarks helping locate the novel points on the data manifolds. We propose a new category of landmarks defined with the following property: the way the landmarks represent the data in the ambient Euclidean space should resemble the way they represent the data on the manifold. Given the data points and the subset of landmarks, we provide procedures to test whether the proposed property presents for the choice of landmarks. If the data points are organized with a neighbourhood graph, as it is often conducted in practice, we interpret the proposed property in terms of the graph topology. We also discuss the extent to which the topology is preserved for landmark set passing our test procedure. Another contribution of this work is to develop an optimization based scheme to adjust an existing landmark set, which can improve the reliability for representing the manifold data. Experiments on the synthetic data and the natural data have been done. The results support the proposed properties and algorithms.     

一种基于代表点的增量聚类算法

针对现有的增量聚类算法对参数敏感度较高、时空复杂度较高等问题,提出了一种基于代表点的增量聚类算法。首先采用代表点聚类算法对静态的数据库进行聚类;然后根据新增加的节点与已存的代表点之间的关系,判断是否将其添加到已存的代表点所属的类簇中,或是提升为新的代表点;最后,再次采用代表点聚类算法对其进行聚类。实验结果证明,该算法对参数的敏感性低、效率高、占用空间小。     

分布式环境下的Skyline代表点查询

为了克服Skyline查询的不足即结果集大小无法控制,提出了Skyline代表点查询,返回k个可描述全局Skyline轮廓的Skyline代表点。研究了分布式环境下的Skyline代表点查询,提出了Naive算法和FDRA。Naive算法首先转移每个子节点上满足条件的两个局部代表点,再通过比较传来的局部代表点间的评价函数值大小决定子节点是否需要传送余下的局部点,以实现剪枝非代表点;与之相比,FDRA的改进在于过滤元组的选择,运用反馈方法,将每次动态更新最大评价函数值的点作为过滤元组,大大降低了计算代价,中心服务器每次只发送过滤元组到分布节点,这样可以尽早且最大限度地剪枝不可能成为代表的Skyline点。提出的算法降低了服务器间的通信开销,返回了正确的结果集,实验论证了算法的有效性与高效性。