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

Particle swarm optimization for time series motif discovery

KNOWLEDGE-BASED SYSTEMS 2016年第Jan.15期92卷 127-137页

作者： Serra, Joan Lluis Arcos, Josep Telefon Res Pl Ernest Lluch & Martin 5 Barcelona 08019 Spain CSIC IIIA Campus UAB S-N Bellaterra 08193 Spain

Efficiently finding similar segments or motifs in time series data is a fundamental task that, due to the ubiquity of these data, is present in a wide range of domains and situations. Because of this, countless solutions have been devised but, to date, none of them seems to be fully satisfactory and flexible. In this article, we propose an innovative standpoint and present a solution coming from it: an anytime multimodal optimization algorithm for time series motif discovery based on particle swarms. By considering data from a variety of domains, we show that this solution is extremely competitive when compared to the state-of-the-art, obtaining comparable motifs in considerably less time using minimal memory. In addition, we show that it is robust to different implementation choices and see that it offers an unprecedented degree of flexibility with regard to the task. All these qualities make the presented solution stand out as one of the most prominent candidates for motif discovery in long time series streams. Besides, we believe the proposed standpoint can be exploited in further time series analysis and mining tasks, widening the scope of research and potentially yielding novel effective solutions. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Motifs Time series anytime algorithms Particle swarm optimization Multimodal optimization

来源：评论

学校读者我要写书评

暂无评论

Resource-bounded sensing and planning in autonomous systems

引用

AUTONOMOUS ROBOTS 1996年第1期3卷 31-48页

作者： Zilberstein, S Computer Science Department LGRC University of Massachusetts Amherst

This paper is concerned with the implications of limited computational resources and uncertainty on the design of autonomous systems. To address this problem, we redefine the principal role of sensor interpretation and planning processes. Following Agre and Chapman's plan-as-communication approach, sensing and planning are treated as computational processes that provide information to an execution architecture and thus improve the overall performance of the system. We argue that autonomous systems must be able to trade off the quality of this information with the computational resources required to produce it. anytime algorithms, whose quality of results improves gradually as computation time increases, provide useful performance components for time-critical sensing and planning in robotic systems. In our earlier work, we introduced a compilation scheme for optimal composition of anytime algorithms. This paper demonstrates the applicability of the compilation technique to the construction of autonomous systems. The result is a flexible approach to construct systems that can operate robustly in real-time by exploiting the tradeoff between time and quality in planning, sensing and plan execution.

关键词： real-time sensing and planning anytime algorithms deliberation scheduling meta-level reasoning uncertainty

来源：评论

学校读者我要写书评

暂无评论

The $-calculus process algebra for problem solving: A paradigmatic shift in handling hard computational problems

引用

THEORETICAL COMPUTER SCIENCE 2007年第2-3期383卷 200-243页

作者： Eberbach, Eugene Univ Massachusetts Dartmouth Dept Comp & Informat Sci N Dartmouth MA 02747 USA

The $-calculus is the extension of the pi-calculus, built around the central notion of cost and allowing infinity in its operators. We propose the $-calculus as a more complete model for problem solving to provide a support to handle intractability and undecidability. It goes beyond the Turing Machine model. We define the semantics of the $-calculus using a novel optimization method (the k Omega-optimization), which approximates a nonexisting universal search algorithm and allows the simulation of many other search methods. In particular, the notion of total optimality has been utilized to provide an automatic way to deal with intractability of problem solving by optimizing together the quality of solutions and search costs. The sufficient conditions needed for completeness, optimality and total optimality of problem solving search are defined. A very flexible classification scheme of problem solving methods into easy, hard and solvable in the limit classes has been proposed. In particular, the third class deals with non-recursive solutions of undecidable problems. The approach is illustrated by solutions of some intractable and undecidable problems. We also briefly overview two possible implementations of the $-calculus. (c) 2007 Elsevier B.V. All rights reserved.

关键词： problem solving process algebras anytime algorithms superTuring models of computation bounded rational agents $-calculus intractability undecidability completeness optimality search optimality total optimality

来源：评论

学校读者我要写书评

暂无评论

anytime Computation of Cautious Consequences in Answer Set Programming

引用

THEORY AND PRACTICE OF LOGIC PROGRAMMING 2014年第4-5期14卷 755-770页

作者： Alviano, Mario Dodaro, Carmine Ricca, Francesco Univ Calabria Dept Math & Comp Sci I-87036 Arcavacata Di Rende CS Italy

Query answering in Answer Set Programming (ASP) is usually solved by computing (a subset of) the cautious consequences of a logic program. This task is computationally very hard, and there are programs for which computing cautious consequences is not viable in reasonable time. However, current ASP solvers produce the (whole) set of cautious consequences only at the end of their computation. This paper reports on strategies for computing cautious consequences, also introducing anytime algorithms able to produce sound answers during the computation.

关键词： answer set programming query answering cautious reasoning anytime algorithms

来源：评论

学校读者我要写书评

暂无评论

Cut-and-solve: An iterative search strategy for combinatorial optimization problems

引用

ARTIFICIAL INTELLIGENCE 2006年第8-9期170卷 714-738页

作者： Climer, Sharlee Zhang, Weixiong Washington Univ Dept Comp Sci & Engn St Louis MO 63130 USA

Branch-and-bound and branch-and-cut use search trees to identify optimal solutions to combinatorial optimization problems. In this paper, we introduce an iterative search strategy which we refer to as cut-and-solve and prove optimality and termination for this method. This search is different from traditional tree search as there is no branching. At each node in the search path, a relaxed problem and a sparse problem are solved and a constraint is added to the relaxed problem. The sparse problems provide incumbent solutions. When the constraining of the relaxed problem becomes tight enough, its solution value becomes no better than the incumbent solution value. At this point, the incumbent solution is declared to be optimal. This strategy is easily adapted to be an anytime algorithm as an incumbent solution is found at the root node and continuously updated during the search. Cut-and-solve enjoys two favorable properties. Since there is no branching, there are no "wrong" subtrees in which the search may get lost. Furthermore, its memory requirement is negligible. For these reasons, it has potential for problems that are difficult to solve using depth-first or best-first search tree methods. In this paper, we demonstrate the cut-and-solve strategy by implementing a generic version of it for the Asymmetric Traveling Salesman Problem (ATSP). Our unoptimized implementation outperformed state-of-the-art solvers for five out of seven real-world problem classes of the ATSP. For four of these classes, cut-and-solve was able to solve larger (sometimes substantially larger) problems. Our code is available at our websites. (c) 2006 Published by Elsevier B.V.

关键词： search strategies branch-and-bound branch-and-cut anytime algorithms linear programming traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

Sequence-Based anytime Control

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2013年第2期58卷 377-390页

作者： Quevedo, Daniel E. Gupta, Vijay Univ Newcastle Sch Elect Engn & Comp Sci Callaghan NSW 2308 Australia Univ Notre Dame Dept Elect Engn Notre Dame IN 46556 USA

We present two related anytime algorithms for control of nonlinear systems when the processing resources available are time-varying. The basic idea is to calculate tentative control input sequences for as many time steps into the future as allowed by the available processing resources at every time step. This serves to compensate for the time steps when the processor is not available to perform any control calculations. Using a stochastic Lyapunov function-based approach, we analyze the stability of the resulting closed-loop system for the cases when the processor availability can be modeled as an independent and identically distributed sequence and via an underlying Markov chain. Numerical simulations indicate that the increase in performance due to the proposed algorithms can be significant.

关键词： anytime algorithms embedded control nonlinear control systems stability analysis stochastic systems

来源：评论

学校读者我要写书评

暂无评论

anytime learning of decision trees

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2007年第5期8卷 891-933页

作者： Esmeir, Saher Markovitch, Shaul Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

The majority of existing algorithms for learning decision trees are greedy-a tree is induced top-down, making locally optimal decisions at each node. In most cases, however, the constructed tree is not globally optimal. Even the few non-greedy learners cannot learn good trees when the concept is difficult. Furthermore, they require a fixed amount of time and are not able to generate a better tree if additional time is available. We introduce a framework for anytime induction of decision trees that overcomes these problems by trading computation speed for better tree quality. Our proposed family of algorithms employs a novel strategy for evaluating candidate splits. A biased sampling of the space of consistent trees rooted at an attribute is used to estimate the size of the minimal tree under that attribute, and an attribute with the smallest expected tree is selected. We present two types of anytime induction algorithms: a contract algorithm that determines the sample size on the basis of a pre-given allocation of time, and an interruptible algorithm that starts with a greedy tree and continuously improves subtrees by additional sampling. Experimental results indicate that, for several hard concepts, our proposed approach exhibits good anytime behavior and yields significantly better decision trees when more time is available.

关键词： anytime algorithms decision tree induction lookahead hard concepts resource-bounded reasoning

来源：评论

学校读者我要写书评

暂无评论

anytime graph matching

引用

PATTERN RECOGNITION LETTERS 2016年 84卷 215-224页

作者： Abu-Aisheh, Zeina Raveaux, Romain Ramel, Jean-Yves Univ Francois Rabelais Tours Lab Informat 64 Ave Jean Portalis F-37200 Tours France

In this paper, we propose and explain the use of anytime algorithms in graph matching (GM). GM methods have been involved in many pattern recognition problems. In such a context, GM methods are part of a more complex retrieval system that imposes time and memory constraints on such methods. anytime algorithms are well suited for use in such an uncertain environment. An anytime algorithm quickly provides the first solution to the problem, finds a list of improved solutions and eventually converges to the optimal solution instead of providing one and only one solution (i.e., the optimal solution). We describe how to convert a recent depth-first GM method into an anytime one. By constraining the solver, the algorithm creates an anytime heuristic search algorithm that allows a flexible trade-off between the search time and the solution quality. We analyze the properties of the resulting anytime algorithm and consider its performance in terms of the deviation of the provided solution from the optimal or the best one found by a state-of-the-art method. Experiments were carried out on seven different types of graph datasets. Moreover, the adopted algorithm was compared to four approximate error-tolerant GM methods. Results showed that the anytime GM can outperform suboptimal methods by only waiting for a small amount of supplementary time. This conclusion brings into question the usual evidence that claims that it is impossible to use optimal GM methods in real-world applications. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Graph matching anytime algorithms Pattern recognition Graph edit distance Performance evaluation metrics

来源：评论

学校读者我要写书评

暂无评论

Design and Stability Analysis for anytime Control via Stochastic Scheduling

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2011年第3期56卷 571-585页

作者： Greco, Luca Fontanelli, Daniele Bicchi, Antonio Univ Salerno DIIMA I-84084 Fisciano SA Italy LSS Supelec F-91192 Gif Sur Yvette France Univ Pisa Interdept Res Ctr E Piaggio I-56100 Pisa Italy Univ Trento Dept Informat Engn & Comp Sci DISI I-38100 Tn Trento Italy IIT Genoa Italy

In this paper, we consider the problem of designing controllers for linear plants to be implemented in embedded platforms under stringent real-time constraints. These include preemptive scheduling schemes, under which the execution time allowed for control software tasks is uncertain. In a conservative Hard Real-Time (HRT) design approach, only a control algorithm that (in the worst case) is executable within the minimum time slot guaranteed by the scheduler would be employed. In the spirit of modern Soft Real-Time (SRT) approaches, we consider here an "anytime control" design technique, based on a hierarchy of controllers for the same plant. Higher controllers in the hierarchy provide better closed-loop performance, while typically requiring longer execution time. Stochastic models of the scheduler and of algorithm execution times are used to infer probabilities that controllers of different complexity can be executed at different periods. We propose a strategy for choosing among executable controllers, maximizing the usage of higher controllers, which affords better exploitation of the computational platform than the HRT design while guaranteeing stability (in a suitable stochastic sense). Results on the robustness with respect to uncertainties affecting the scheduler model, and on bumpless transfer for tracking problems are also reported. Simulation results on the control of two prototypical mechanical systems show that performance is substantially enhanced by our anytime control technique w.r.t. worst case-based scheduling.

关键词： anytime algorithms embedded control stochastic scheduling switched systems

来源：评论

学校读者我要写书评

暂无评论

Algorithm portfolios

引用

ARTIFICIAL INTELLIGENCE 2001年第1-2期126卷 43-62页

作者： Gomes, CP Selman, B Cornell Univ Dept Comp Sci Ithaca NY 14853 USA

Stochastic algorithms are among the best methods for solving computationally hard search and reasoning problems. The run time of such procedures can vary significantly from instance to instance and, when using different random seeds, on the same instance. One can take advantage of such differences by combining several algorithms into a portfolio, and running them in parallel or interleaving them on a single processor. We provide an evaluation of the portfolio approach on distributions of hard combinatorial search problems. We show under what conditions the portfolio approach can have a dramatic computational advantage over the best traditional methods. In particular, we will see how, ina portfolio setting, it can be advantageous to use a more "risk-seeking" strategy with a high variance in run time, such as a randomized depth-first search approach in mixed integer programming versus the more traditional best-bound approach. We hope these insights will stimulate the development of novel randomized combinatorial search methods. (C) 2001 Published by Elsevier Science B.V.

关键词： algorithm portfolios randomized algorithms cost profiles anytime algorithms empirical evaluation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：