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 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.     

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.     

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...     

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.     

Extracting representative motion flows for effective video retrieval

In this paper, we propose a novel motion-based video retrieval approach to find desired videos from video databases through trajectory matching. The main component of our approach is to extract representative motion features from the video, which could be broken down to the following three steps. First, we extract the motion vectors from each frame of videos and utilize Harris corner points to compensate the effect of the camera motion. Second, we find interesting motion flows from frames using sliding window mechanism and a clustering algorithm. Third, we merge the generated motion flows and select representative ones to capture the motion features of videos. Furthermore, we design a symbolic based trajectory matching method for effective video retrieval. The experimental results show that our algorithm is capable to effectively extract motion flows with high accuracy and outperforms existing approaches for video retrieval.     

一种基于图论的计算蛋白质数据库代表序列的算法

许多生物序列数据库中都含有大量的冗余序列,这些冗余序列通常不利于对数据库的统计分析和处理,而且它们要占用更多的计算机存储和处理资源.针对这个问题,本文中我们设计了一种去除蛋白质冗余序列的算法.该算法基于图论最大独立集的概念来生成非冗余序列集合,对目前存在的不少蛋白质去冗余程序所采用的由Hobohm和Sander最早设计的一种首先将序列分成若干簇然后取出代表序列的算法进行了改进,使得生成了更多的非冗余代表序列集合,避免了一些非冗余的序列也被去除.我们开发出了实现该算法的程序FastCluster,可以用来去除蛋白质数据库中的冗余序列.     

Verification of distributed programs using representative interleaving sequences

Summary We present a formal proof method for distributed programs. The semantics used to justify the proof method explicitly identifies equivalence classes of execution sequences which are equivalent up to permuting commutative operations. Each equivalence class is called an interleaving set or a run. The proof rules allow concluding the correctness of certain classes of properties for all execution sequences, even though such properties are demonstrated directly only for a subset of the sequences. The subset used must include a representative sequence from each interleaving set, and the proof rules, when applicable, guarantee that this is the case. By choosing a subset with appropriate sequences, simpler intermediate assertions can be used than in previous formal approaches. The method employs proof lattices, and is expressed using the temporal logic ISTL. Shmuel Katz received his B.A. in Mathematics and English Literature from U.C.L.A., and his M.Sc. and Ph.D. in Computer Science (1976) from the Weizmann Institute in Rechovot, Israel. From 1976 to 1981 he was at the IBM Israel Scientific Center. Presently, he is on the faculty of the Computer Science Department at the Technion in Haifa, Israel. In 1977–1978 he visited for a year at the University of California, Berkeley, and in 1984–1985 was at the University of Texas at Austin. He has been a consultant and visitor at the MCC Software Technology Program, and in 1988–1989 was a visiting scientist at the I.B.M. Watson Research Center. His research interests include the methodology of programming, specification methods, program verification and semantics, distributed programming, data structures, and programming languages. Doron Peled was born in 1962 in Haifa. He received his B.Sc. and M.Sc. in Computer Science from the Technion, Israel in 1984 and 1987, respectively. Between 1987 and 1991 he did his military service. He also completed his D.Sc. degree in the Technion during these years. Dr. Peled was with the Computer Science department at Warwick University in 1991–1992. He is currently a member of the technical staff with AT & T Bell Laboratories. His main research interests are specification and verification of programs, especially as related to partial order models, fault-tolerance and real-time. He is also interested in semantics and topology.This research was carried out while the second author was at the Department of Computer Science, The Technion, Haifa 32000, Israel     

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

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

A clustering method to identify representative financial ratios

When companies evaluate their performance, it is impractical to take all of their financial ratios into consideration. To evaluate the financial performance of a company, only a fraction of the available financial ratios are considered and selected as evaluation criteria. In general, financial ratios presented as sequences (or called financial ratio sequences), are first clustered and then a representative indicator is chosen from each cluster to serve as an evaluation criterion. To cluster financial ratios, we propose a clustering method in which the financial ratios of different companies with similar variations are partitioned into the same cluster. In other words, a fuzzy relation is proposed to represent the similarity between the financial ratios, and a cluster validation index is also provided to determine the number of clusters. Once the financial ratios are clustered, the representative indicator for each cluster will be identified.     

Detecting community structure in networks by representative energy

Network community has attractedmuch attention recently, but the accuracy and efficiency in finding a community structure is limited by the lower resolution of modularity. This paper presents a new method of detecting community based on representative energy. The method can divide the communities and find the representative of community simultaneously. The communities of network emerges during competing for the representative among nodes in network, thus we can sketch structure of the whole network. Without the optimizing by modularity, the community of network emerges with competing for representative among those nodes. To obtain the proximate relationships among nodes, we map the nodes into a spectral matrix. Then the top eigenvectors are weighted according to their contributions to find the representative node of a community. Experimental results show that the method is effective in detecting communities of networks.     

Top-K representative documents query over geo-textual data stream

The increasing popularity of location-based social networks encourages more and more users to share their experiences. It deeply impacts the decision of customers when shopping, traveling, and so on. This paper studies the problem of top-K valuable documents query over geo-textual data stream. Many researchers have studied this problem. However, they do not consider the reliability of documents, where some unreliable documents may mislead customers to make improper decisions. In addition, they lack the ability to prune documents with low representativeness. In order to increase user satisfaction in recommendation systems, we propose a novel framework named PDS. It first employs an efficiently machine learning technique named ELM to prune unreliable documents, and then uses a novel index named \(\mathcal {GH}\) to maintain documents. For one thing, this index maintains a group of pruning values to filter low quality documents. For another, it utilizes the unique property of sliding window to further enhance the PDS performance. Theoretical analysis and extensive experimental results demonstrate the effectiveness of the proposed algorithms.     

A representative model based algorithm for maximal contractions

In this paper,we propose a representative model based algorithm to calculate maximal contractions.For a formal theory Γ and a fact set Δ,the algorithm begins by accepting all models of refutation by facts of Γ with respect to Δ and filters these models to obtain the models of R-refutation.According to the completeness of R-calculus,the relevant maximal contraction is obtained simultaneously.In order to improve the efficiency,we divide the models into different classes according to the assignments of atomic propositions and only select relevant representative models to verify the satisfiability of each proposition.The algorithm is correct,and all maximal contractions of a given problem can be calculated by it.Users could make a selection according to their requirements.A benchmark algorithm is also provided.Experiments show that the algorithm has a good performance on normal revision problems.