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

Harnessing the strengths of anytime algorithms for constant data streams

DATA MINING AND KNOWLEDGE DISCOVERY 2009年第2期19卷 245-260页

作者： Kranen, Philipp Seidl, Thomas Rhein Westfal TH Aachen Data Management & Data Explorat Grp D-52056 Aachen Germany

anytime algorithms have been proposed for many different applications, e.g., in data mining. Their strengths are the ability to first provide a result after a very short initialization and second to improve their result with additional time. Therefore, anytime algorithms have so far been used when the available processing time varies, e.g., on varying data streams. In this paper we propose to employ anytime algorithms on constant data streams, i.e., for tasks with constant time allowance. We introduce two approaches that harness the strengths of anytime algorithms on constant data streams and thereby improve the over all quality of the result with respect to the corresponding budget algorithm. We derive formulas for the expected performance gain and demonstrate the effectiveness of our novel approaches using existing anytime algorithms on benchmark data sets.

关键词： anytime algorithms Stream data mining Classification confidence

来源：评论

学校读者我要写书评

暂无评论

An efficient hybrid search algorithm for job shop scheduling with operators

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2013年第17期51卷 5221-5237页

作者： Mencia, Carlos Sierra, Maria R. Varela, Ramiro Univ Oviedo Dept Comp Gijon Spain

We confront the job shop scheduling problem with human operators and total flow time minimisation. To solve this problem we propose a hybrid search algorithm that interleaves best-first and depth-first search. The efficiency of this algorithm relies on the proper combination of diversification and intensification capabilities of best-first and depth-first searches, respectively, as well as two admissible heuristics and some global pruning rules designed from problem domain knowledge. We conducted an experimental study on a benchmark set with small-, medium- and large-size instances. The results of this study show that the algorithm is efficient thanks to the combination of all its components and that it compares favorably with an outstanding constraint programming solver specialised in scheduling problems.

关键词： job shop scheduling with operators total flow time best-first search depth-first search hybrid search algorithms anytime algorithms global pruning rules

来源：评论

学校读者我要写书评

暂无评论

Incremental Beam search

引用

INFORMATION PROCESSING LETTERS 2013年第22-24期113卷 888-893页

作者： Vadlamudi, S. G. Aine, Sandip Chakrabarti, P. P. Indian Inst Technol Dept Comp Sci & Engn Kharagpur 721302 W Bengal India Indraprastha Inst Informat Technol New Delhi 110020 DL India

Beam search is a heuristic search algorithm that explores a state-space graph by expanding w most promising nodes at each level (depth) of the graph, where w is called the beam-width which is taken as input from the user. The quality of the solution produced by beam search does not always monotonically improve with the increase in beam-width making it difficult to choose an appropriate beam-width for effective use. We present an algorithm called Incremental Beam Search (IncB) which guarantees monotonicity, and is also anytime in nature. Experimental results on the sliding-tile puzzle, the traveling salesman, and the single-machine scheduling problems show that IncB significantly outperforms basic monotonic methods such as iterative widening beam search as well as some of the state-of-the-art anytime heuristic search algorithms in terms of the quality of the solution produced at the end as well as the anytime performance. (C) 2013 Elsevier B.V. All rights reserved.

关键词： algorithms Beam search Monotonicity Heuristic search anytime algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

An anytime assignment algorithm: From local task swapping to global optimality

引用

AUTONOMOUS ROBOTS 2013年第4期35卷 271-286页

作者： Liu, Lantao Shell, Dylan A. Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

The assignment problem arises in multi-robot task-allocation scenarios. Inspired by existing techniques that employ task exchanges between robots, this paper introduces an algorithm for solving the assignment problem that has several appealing features for online, distributed robotics applications. The method may start with any initial matching and incrementally improve the current solution to reach the global optimum, producing valid assignments at any intermediate point. It is an any-time algorithm with a performance profile that is attractive: quality improves linearly with stages (or time). Additionally, the algorithm is comparatively straightforward to implement and is efficient both theoretically (complexity of is better than many widely used solvers) and practically (comparable to the fastest implementation, for up to hundreds of robots/tasks). The algorithm generalizes "swap" primitives used by existing task exchange methods already used in the robotics community but, uniquely, is able to obtain global optimality via communication with only a subset of robots during each stage. We present a centralized version of the algorithm and two decentralized variants that trade between computational and communication complexity. The centralized version turns out to be a computational improvement and reinterpretation of the little-known method of Balinski-Gomory proposed half a century ago. Thus, deeper understanding of the relationship between approximate swap-based techniques-developed by roboticists-and combinatorial optimization techniques, e.g., the Hungarian and Auction algorithms-developed by operations researchers but used extensively by roboticists-is uncovered.

关键词： Multi-robot task allocation Decentralized assignment anytime algorithms Task swapping

来源：评论

学校读者我要写书评

暂无评论

Nonprobabilistic anytime algorithm for high-quality trajectories in high-dimensional spaces

引用

ROBOTICA 2012年第02期30卷 289-303页

作者： Vazquez, Andres S. Adan, Antonio Univ Castilla La Mancha Escuela Super Informat E-13071 Ciudad Real Spain

This paper proposes a feasible variation of approximate grid-based path-planning methods, which have been replaced with probabilistic methods nowadays, due mainly to their impracticality in high-dimensional spaces. Our aim is to demonstrate that, with an incremental exploration of the CSpace by means of Interpolated walk primitives and ANY-Time algorithms, we can generate online high-quality solutions that can be compared with probabilistic methods and can even improve some aspects, such as the completeness. Computational time, path smoothness, path clearance, and path distance are the qualifiers used to evaluate the path planner. These quality factors are critical in robotics. In fact, in both mobile and industrial robots, the computational time is a primary requirement to work online, the clearance gives security to the movements of the robot, and the smoothness can prolong the life of the mechanical components. Our method has been compared to probabilistic path planners, with the feasibility and benefits of our algorithm being proved in terms of the quality factors aforementioned.

关键词： Path planning anytime algorithms

来源：评论

学校读者我要写书评

暂无评论

anytime learning of anycost classifiers

引用

MACHINE LEARNING 2011年第3期82卷 445-473页

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

The classification of new cases using a predictive model incurs two types of costs-testing costs and misclassification costs. Recent research efforts have resulted in several novel algorithms that attempt to produce learners that simultaneously minimize both types. In many real life scenarios, however, we cannot afford to conduct all the tests required by the predictive model. For example, a medical center might have a fixed predetermined budget for diagnosing each patient. For cost bounded classification, decision trees are considered attractive as they measure only the tests along a single path. In this work we present an anytime framework for producing decision-tree based classifiers that can make accurate decisions within a strict bound on testing costs. These bounds can be known to the learner, known to the classifier but not to the learner, or not predetermined. Extensive experiments with a variety of datasets show that our proposed framework produces trees with lower misclassification costs along a wide range of testing cost bounds.

关键词： Decision trees Cost-sensitive learning Resource-bounded reasoning anytime algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Improving the anytime behavior of two-phase local search

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2011年第2期61卷 125-154页

作者： Dubois-Lacoste, Jeremie Lopez-Ibanez, Manuel Stutzle, Thomas Univ Libre Bruxelles IRIDIA Brussels Belgium

algorithms based on the two-phase local search (TPLS) framework are a powerful method to efficiently tackle multi-objective combinatorial optimization problems. TPLS algorithms solve a sequence of scalarizations, that is, weighted sum aggregations, of the multi-objective problem. Each successive scalarization uses a different weight from a predefined sequence of weights. TPLS requires defining the stopping criterion (the number of weights) a priori, and it does not produce satisfactory results if stopped before completion. Therefore, TPLS has poor "anytime" behavior. This article examines variants of TPLS that improve its "anytime" behavior by adaptively generating the sequence of weights while solving the problem. The aim is to fill the "largest gap" in the current approximation to the Pareto front. The results presented here show that the best adaptive TPLS variants are superior to the "classical" TPLS strategies in terms of anytime behavior, matching, and often surpassing, them in terms of final quality, even if the latter run until completion.

关键词： Multi-objective anytime algorithms Two-phase local search

来源：评论

学校读者我要写书评

暂无评论

Document Recognition Without Strong Models

Document Recognition Without Strong Models

引用

11th International Conference on Document Analysis and Recognition (ICDAR)

作者： Baird, Henry S. Lehigh Univ Comp Sci & Engn Dept Bethlehem PA 18015 USA

ISBN: (纸本)9780769545202

Can a high-performance document image recognition system be built without detailed knowledge of the application? Having benefited from the statistical machine-learning revolution of the last twenty years, our architectures rely less on hand-crafted special-case rules and more on models trained on labeled-sample data sets. But urgent questions remain. When we can't collect (and label) enough real training data, does it help to complement them with data synthesized using generative models? Is it ever completely safe to rely on synthetic data? If we can't manage to train (or craft) a single complete, near-perfect, application-specific "strong" model to drive recognition, can we make progress by combining several imperfect or incomplete "weak" models? Can recognition that is carried out jointly over weak models perform optimally while still running fast? Can a recognizer automatically pick a strong model of its input? Must we always pre-train models for every kind ("style") of input expected, or can a recognizer adapt to unknown styles? Can weak models adapt autonomously, growing stronger and so driving accuracy higher, without any human intervention? Can one model "criticize"-and then proceed to correct-other models, even while it is being criticized and corrected in turn by them? After twenty-five years of research on these questions we have partial answers, many in the affirmative: in addition to promising laboratory demonstrations, we can take pride in successful applications. I'll illustrate the evolution of the state of the art with concrete examples, and point out open problems.

关键词： Rule-based recognition model-driven recognition learning models synthetically generated data strong versus weak models joint recognition style-conscious recognition adaptive recognition anytime algorithms whole-book recognition

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：