检索结果-内蒙古大学图书馆

作者： Wu, Wei University of Washington

学位级别：Ph.D.

Lexical semantics studies the meaning of words, which is a useful tool for computer-based automatic natural language processing (NLP). This thesis explores graph-based algorithms to learn and apply distributional lexical semantics in NLP applications. One theory of lexical semanticists holds that semantic relations among words can be extracted from their textual context in natural languages. based on this theory, we propose using graphs to represent natural language text according to the contextual relations of words in higher-level language units (e.g. sentences, definitions or documents). In these graphs, words and/or higher-level language units are represented with nodes, and edges are added between them according to their textual context to indicate their observed relatedness in a dictionary or a collection of documents. We explore two types of graph representations: the word-word graph which is used for modeling the semantic relations among words, and the instance-word bipartite graph which uses words as a medium to study the relatedness among higher-level language units. In this way, we can embed the semantic relations among words and optionally higher-level language units into the graph structure. We design algorithms to propagate semantic information through the graphs in order to recover the unobserved relatedness among words or higher-level language units, which is used in designing unsupervised, semi-supervised or active learning algorithms to reduce human supervision in NLP applications for harvesting or analyzing text data resources. Specifically, we design graph-based algorithms either for quantitatively assessing lexical semantic similarity, or for developing representativeness and diversity criteria for selecting a characteristic subset of terms, which is useful for problems such as keyword summarization and query design for active learning. In particular, we focus on designing graph-based algorithms to apply lexical semantics in three NLP applicatio

关键词： graph-based algorithms Lexical Semantics NLP Semantic Similarity Sentiment Classification Twitter Electrical engineering

来源：评论

学校读者我要写书评

暂无评论

Comparing graph-based algorithms to Generate Test Cases from Finite State Machines

引用

JOURNAL OF ELECTRONIC TESTING-THEORY AND APPLICATIONS 2019年第6期35卷 867-885页

作者： Mariano, Matheus Monteiro de Souza, Erica Ferreira Endo, Andre Takeshi Vijaykumar, Nandamudi Lankalapalli Natl Inst Space Res Lab Comp & Appl Math INPE Av Astronautas1-758 Jardim Granja BR-12227010 Sao Jose Dos Campos SP Brazil Fed Univ Technol Dept Comp UTFPR Av Alberto Carazzai 1640 BR-86300000 Cornelio Procopio PR Brazil Univ Fed Sao Paulo ICT Inst Sci & Technol Av Cesare Monsueto Giulio Lattes 1201 Sao Jose Dos Campos Brazil Natl Inst Space Res LABAC Av Astronautas 1758 Sao Jose Dos Campos Brazil

Model-based Testing (MBT) is a well-known technique that employs formal models to represent reactive systems' behavior and generates test cases. Such systems have been specified and verified using mostly Finite State Machines (FSMs). There is a plethora of test generation algorithms in the literature;most of them are based on graphs once an FSM can be formally defined as a graph. Nevertheless, there is a lack of studies on analyzing cost and efficiency of FSM-based test generation algorithms. This study compares graph-based algorithms adopted to generate test cases from FSM models. In particular, we compare the Chinese Postman Problem (CPP) and H-Switch Cover (HSC) algorithms with the well-known Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms in the context of covering all-transitions and all-transition-pairs criteria in an FSM. First, a systematic literature mapping was conducted to summarize the methods that have been adopted in MBT, considering FSMs. Second, the main methods found were implemented and analyzed on randomly-generated FSMs, as well as real-world models that represent embedded systems of space applications. To make comparisons, we considered analyses in terms of cost (time), efficiency (mutant analysis) and characteristics of the generated test suites (number of test cases, average length of test cases, largest and smallest test cases, standard deviation and distribution of test cases). In general, CPP presented the best results in terms of number of test cases and test suite size. In addition, CPP also presented low distribution of average length compared to other algorithms.

关键词： Software testing Model based testing Finite state machine graph-based algorithms

来源：评论

学校读者我要写书评

暂无评论

Assessing two graph-based algorithms in a model-based testing platform for Java applications 15

Assessing two graph-based algorithms in a model-based testin...

引用

15th Iberian Conference on Information Systems and Technologies (CISTI)

作者： Villalobos-Arias, Leonardo Quesada-Lopez, Christian Martinez, Alexandra Jenkins, Marcelo Univ Costa Rica Escuela Ciencias Comp & Informat San Jose Costa Rica

ISBN: (纸本)9789895465903

Model-based testing (MBT) is an approach for automatically generating test cases from a model of the system under test. Existing MBT tools support the automation of this process at varying degrees. One such tool is MBT4J, a research platform that extends ModelJUnit, offering a high level of automation. We extended MBT4J with two graph-based algorithms: the Chinese Postman Problem (CPP) and Breadth-First Search (BFS). The purpose of this study is to evaluate the efficacy of these two new algorithms added to MBT4J by comparing them to previous algorithms implemented in the platform. A case study was conducted using two open-source Java applications from public repositories, and twenty-one different configurations. The CPP tester performed similarly to previous testers in terms of time and coverage, and in addition, it resulted in a greater percentage of failed test cases in one application. The BFS tester was able to generate a greater amount of test cases when using fewer resources. We thus recommend using these algorithms for generating test cases for systems with complex models.

关键词： model-based testing MBT4J graph-based algorithms Java applications case study

来源：评论

学校读者我要写书评

暂无评论

Distinguishing Social Ties in Recommender Systems by graph-based algorithms

Distinguishing Social Ties in Recommender Systems by Graph-B...

引用

14th International Conference on Web Information Systems Engineering (WISE)

作者： Wei, Xiaochi Huang, Heyan Xin, Xin Yang, Xianxiang Beijing Inst Technol Sch Comp Sci & Technol Beijing 100081 Peoples R China

ISBN: (纸本)9783642412301;9783642412295

Incorporating the social network information into recommender systems has been demonstrated as an effective approach in improving the recommendation performance. When predicting ratings for an active user, his/her taste is influenced by the ones of his/her friends. Intuitively, different friends have different influential power to the active user. Most existing social recommendation algorithms, however, fail to consider such differences, and unfairly treat them equally. The problem is that the friends with less influential power might mislead the rating predictions, and finally impair the recommendation performance. Some previous work has tried to differentiate the influential power by local similarity calculations, but it has not provided a systematic solution and it has ignored the propagation of the influence among the social network. To solve the above limitations, in this paper, we investigate the issue of distinguishing different users' influence power in recommendation systematically. We propose to employ three graph-based algorithms (including PageRank, HITS, and heat diffusion) to distinguish and propagate the influence among the friends of an active user, and then integrate them into the factorization-based social recommendation framework. Through experimental verification in the Epinions dataset, we demonstrate that the proposed approaches consistently outperform previous social recommendation algorithms significantly.

关键词： Recommender Systems Social Network Collaborative Filtering graph-based algorithms

来源：评论

学校读者我要写书评

暂无评论

graph-based algorithms for phase-type distributions

引用

STATISTICS AND COMPUTING 2022年第6期32卷 103-103页

作者： Roikjer, Tobias Hobolth, Asger Munch, Kasper Aarhus Univ Bioinformat Res Ctr Universitetsbyen 813 Bldg 1872 DK-8000 Aarhus Denmark Aarhus Univ Dept Math Ny Munkegade 118 Bldg 1530 DK-8000 Aarhus Denmark

Phase-type distributions model the time until absorption in continuous or discrete-time Markov chains on a finite state space. The multivariate phase-type distributions have diverse and important applications by modeling rewards accumulated at visited states. However, even moderately sized state spaces make the traditional matrix-based equations computationally infeasible. State spaces of phase-type distributions are often large but sparse, with only a few transitions from a state. This sparseness makes a graph-based representation of the phase-type distribution more natural and efficient than the traditional matrix-based representation. In this paper, we develop graph-based algorithms for analyzing phase-type distributions. In addition to algorithms for state space construction, reward transformation, and moments calculation, we give algorithms for the marginal distribution functions of multivariate phase-type distributions and for the state probability vector of the underlying Markov chains of both time-homogeneous and time-inhomogeneous phase-type distributions. The algorithms are available as a numerically stable and memory-efficient open source software package written in C named ptdalgorithms. This library exposes all methods in the programming languages C and R. We compare the running time of ptdalgorithms to the fastest tools using a traditional matrix-based formulation. This comparison includes the computation of the probability distribution, which is usually computed by exponentiation of the sub-intensity or sub-transition matrix. We also compare time spent calculating the moments of (multivariate) phase-type distributions usually defined by inversion of the same matrices. The numerical results of our graph-based and traditional matrix-based methods are identical, and our graph-based algorithms are often orders of magnitudes faster. Finally, we demonstrate with a classic problem from population genetics how ptdalgorithms serves as a much faster, simpler, a

关键词： Phase-type distributions Computational statistics Moments Distribution graph-based algorithms

来源：评论

学校读者我要写书评

暂无评论

Analyzing graph-based algorithms employed to generate test cases from finite state machines 20

Analyzing graph-based algorithms employed to generate test c...

引用

20th IEEE Latin American Test Symposium (LATS)

作者： Mariano, Matheus Monteiro Souza, Erica F. Endo, Andre T. Vijaykumar, Nandamudi L. Natl Inst Space Res INPE Lab Comp & Appl Math Sao Jose Dos Campos SP Brazil Fed Technol Univ UTFPR Dept Comp Cornelio Procopio PR Brazil

ISBN: (纸本)9781728117560

Context: Model-based Testing (MBT) is a technique that employs formal models to represent reactive systems' behavior and generates test cases. Such systems are mostly specified and verified using Finite State Machines (FSMs). There is a plethora of test generation algorithms in the literature. Most of them are graph-based once an FSM can be formally defined as a graph. Nevertheless, there is a lack of studies on analyzing cost and efficiency of FSM-based test generation algorithms. Objective: This study aims to compare graph-based algorithms employed to generate test cases from FSM models. In particular, we compare the Chinese Postman Problem (CPP) and H-Switch Cover (HSC) algorithms with the well-known depth-first and breadth-first searches algorithms in the context of covering all-transitions and all-transition-pairs criteria in an FSM. Method: First, a systematic literature mapping was conducted to summarize the algorithms that have been adopted in MBT, considering FSM. The main algorithms found were implemented and analyzed in different experiments. Results: CPP presented better results with the FSMs used in terms of number of test cases and test suite size. In addition, CPP also presented low distribution of average length compared to other algorithms.

关键词： Software Testing Model based Testing Finite State Machine graph-based algorithms

来源：评论

学校读者我要写书评

暂无评论

graph-based evolutionary algorithms

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2006年第5期10卷 550-567页

作者： Bryden, Kenneth Mark Ashlock, Daniel A. Corns, Steven Willson, Stephen J. Iowa State Univ Dept Engn Mech Ames IA 50011 USA Univ Guelph Dept Math & Stat Guelph ON N1G 2R4 Canada Iowa State Univ Dept Math Ames IA 50011 USA

Evolutionary algorithms use crossover to combine information from pairs of solutions and use selection to retain the best solutions. Ideally, crossover takes distinct good features from each of the two structures involved. This process creates a conflict: progress results from crossing over structures with different features, but crossover produces new structures that are like their parents and so reduces the diversity on which it depends. As evolution continues, the algorithm searches a smaller and smaller portion of the search space. Mutation can help maintain diversity but is not a panacea for diversity loss. This paper explores evolutionary-algorithms that use combinatorial graphs to limit possible crossover partners. These graphs limit the speed and mariner in which information can spread giving competing solutions time to mature. This use of graphs is a computationally inexpensive method of picking a global level of tradeoff between exploration and exploitation. The results of using 26 graphs with a diverse collection of graphical properties are presented. The test problems used are: one-max, the De Jong functions, the Griewangk function in three to seven dimensions, the self-avoiding random walk problem in 9, 12, 16, 20, 25, 30, and 36 dimensions, the plus-one-recall-store (PORS) problem with n = 15, 16, and 17, location of length-six one-error-correcting DNA barcodes, and solving a simple differential equation semi-symbolically. The choice of combinatorial graph has a significant effect on the time-to-solution. In the cases studied, the optimal choice of graph improved solution time as much as 63-fold with typical impact being in the range of 15% to 100% variation. The graph yielding superior performance is found to be problem dependent. In general, the optimal graph diameter increases and the optimal average degree decreases with the complexity and difficulty of the fitness landscape. The use of diverse graphs as population structures for a collection of pr

关键词： evolutionary algorithm graph-based algorithms population structure test suite

来源：评论

学校读者我要写书评

暂无评论

graph based algorithms to efficiently map VLSI circuits with simple cells

Graph based algorithms to efficiently map VLSI circuits with...

引用

作者： Matos, Jody Maick Araujo de

This thesis introduces a set of graph-based algorithms for efficiently mapping VLSI circuits using simple cells. The proposed algorithms are concerned to, first, effectively minimize the number of logic elements implementing the synthesized circuit. Then, we focus a significant effort on minimizing the number of inverters in between these logic elements. Finally, this logic representation is mapped into a circuit comprised of only two-input NANDs and NORS, along with the inverters. Two-input XORs and XNORs can also be optionally considered. As we also consider sequential circuits in this work, flip-flops are taken into account as well. Additionally, with high-effort optimization on the number of logic elements, the generated circuits may contain some cells with unfeasible fanout for current technology nodes. In order to fix these occurrences, we propose an area-oriented, level-aware algorithm for fanout limitation. The proposed algorithms were applied over a set of benchmark circuits and the obtained results have shown the usefulness of the method. We show that efficient implementations in terms of inverter count, transistor count, area, power and delay can be generated from circuits with a reduced number of both simple cells and inverters, combined with XOR/XNOR-based optimizations. The proposed buffering algorithm can handle all unfeasible fanout occurrences, while (i) optimizing the number of added inverters; and (ii) assigning cells to the inverter tree based on their level criticality. When comparing with academic and commercial approaches, we are able to simultaneously reduce the average number of inverters, transistors, area, power dissipation and delay up to 48%, 5%, 5%, 5%, and 53%, respectively. As the adoption of a limited set of simple standard cells have been showing benefits for a variety of modern VLSI circuits constraints, such as layout regularity, routability constraints, and/or ultra low power constraints, the proposed methods can be of special i

关键词： graph-based algorithms Microeletrônica Vlsi Simple cells Síntese lógica Standard cell library Technology mapping Logic synthesis Tese

来源：评论

学校读者我要写书评

暂无评论

OClustR: A new graph-based algorithm for overlapping clustering

引用

NEUROCOMPUTING 2013年 121卷 234-247页

作者： Perez-Suarez, Airel Martinez-Trinidad, Jose F. Carrasco-Ochoa, Jesus A. Medina-Pagola, Jose E. Inst Nacl Astrofis Opt & Electr Puebla 72840 Mexico Ctr Aplicac Tecnol Avanzada Havana 12200 Cuba

Clustering is a Data Mining technique, which has been widely used in many practical applications. From these applications, there are some, like social network analysis, topic detection and tracking, information retrieval, categorization of digital libraries, among others, where objects may belong to more than one cluster;however, most clustering algorithms build disjoint clusters. In this work, we introduce OClustR, a new graph-based clustering algorithm for building overlapping clusters. The proposed algorithm introduces a new graph-covering strategy and a new filtering strategy, which together allow to build overlapping clusterings more accurately than those built by previous algorithms. The experimental evaluation, conducted over several standard collections, showed that our proposed algorithm builds less clusters than those built by the previous related algorithms. Additionally, OClustR builds clusters with overlapping closer to the real overlapping in the collections than the overlapping generated by other clustering algorithms. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Data mining Overlapping clustering graph-based algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal ice routing of a ship with icebreaker assistance

引用

APPLIED OCEAN RESEARCH 2019年 86卷 177-187页

作者： Topaj, A. G. Tarovik, O. V. Bakharev, A. A. Kondratenko, A. A. Kylov State Res Ctr 44 Moskovskoe Shosse St Petersburg 196158 Russia

Offshore development and growing prospects of commercial shipping in the Arctic pose the challenge of optimal ship routing in ice. Route selection in spatially distributed ice conditions significantly affects the voyage time and determines the efficiency of shipping. Most of the applied methods of ice routing solve the problem of a single vessel route selection without considering icebreaker support. At the same time, the real practice of ice navigation is closely connected with icebreaker assistance. It allows reducing the voyage time and fuel consumption, while having additional costs for icebreaker services. Such opposite trends set an optimization task that has not been studied in detail before. In this article, we presented the formulation of a Single Vessel and Icebreaker Assisted Ice Routing optimization problem in non-stationary ice conditions. We considered the icebreaker assistance as an integral part of the overall route optimization problem, and used the economic criterion to optimize both ship route and amount of icebreaker involvement. The article contains the adapted mathematical formulations of classical graph-based and wave-based routing problems in order to consider icebreaker assistance. To prove the practical applicability of these formulations, we developed special subject-oriented research software and implemented there both graph-based (Dijkstra, A*) and the wave-based ice routing methods. Using this developments, we conducted several case studies and made the analysis of strengthens and weaknesses of the alternative routing methods in case of ice operation. The results of the study may serve an additional step to the practical implementation of ice routing technologies and planning of icebreaker resources.

关键词： Ship routing Ice navigation Path finding graph-based algorithms Wave-based methods Icebreaker assistance

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：