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

60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Goldenberg, Elazar Krauthgamer, Robert Saha, Barna Acad Coll Tel Aviv Yaffo Tel Aviv Israel Weizmann Inst Sci Rehovot Israel Univ Calif Berkeley Berkeley CA 94720 USA

ISBN: (纸本)9781728149523

The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. A simple dynamic programming computes the edit distance between two strings of length n in O(n(2)) time, and a more sophisticated algorithm runs in time O(n + t(2)) when the edit distance is t [Landau, Myers and Schmidt, SICOMP 1998]. In pursuit of obtaining faster running time, the last couple of decades have seen a flurry of research on approximating edit distance, including polylogarithmic approximation in near-linear time [Andoni, Krauthgamer and Onak, FOCS 2010], and a constant-factor approximation in subquadratic time [Chakrabarty, Das, Goldenberg, Koucky and Saks, FOCS 2018]. We study sublinear-time algorithms for small edit distance, which was investigated extensively because of its numerous applications. Our main result is an algorithm for distinguishing whether the edit distance is at most t or at least t(2) (the quadratic gap problem) in time (O) over tilde (n/t + t(3)). This time bound is sublinear roughly for all tin [omega(1), o(n(1/3))], which was not known before. The best previous algorithms solve this problem in sublinear time only for t = omega(n(1/3)) [Andoni and Onak, STOC 2009]. Our algorithm is based on a new approach that adaptively switches between uniform sampling and reading contiguous blocks of the input strings. In contrast, all previous algorithms choose which coordinates to query non-adaptively. Moreover, it can be extended to solve the t vs t(2-epsilon) gap problem in time (O) over tilde (n/t(1-epsilon) + t(3)).

关键词： edit distance sequence alignment sublinear-time algorithms sampling algorithms

来源：评论

学校读者我要写书评

暂无评论

On Local Distributed sampling and Counting 18

On Local Distributed Sampling and Counting

引用

37th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Feng, Weiming Yin, Yitong Nanjing Univ State Key Lab Novel Software Technol Nanjing Jiangsu Peoples R China

ISBN: (纸本)9781450357951

In classic distributed graph problems, each instance on a graph specifies a space of feasible solutions (e.g. all proper (Delta + 1)-list-colorings of the graph), and the task of distributed algorithm is to construct a feasible solution using local information. We study distributed sampling and counting problems, in which each instance specifies a joint distribution of feasible solutions. The task of distributed algorithm is to sample from this joint distribution, or to locally measure the volume of the probability space via the marginal probabilities. The latter task is also known as inference, which is a local counterpart of counting. For self-reducible classes of instances, the following equivalences are established in the LOCAL model up to polylogarithmic factors: For all joint distributions, approximate inference and approximate sampling are computationally equivalent. For all joint distributions defined by local constraints, exact sampling is reducible to either one of the above tasks. If further, sequentially constructing a feasible solution is trivial locally, then all above tasks are easy if and only if the joint distribution exhibits strong spatial mixing. Combining with the state of the arts of strong spatial mixing, we obtain efficient sampling algorithms in the LOCAL model for various important sampling problems, including: an O(root Delta log(3) n)-round algorithm for exact sampling matchings in graphs with maximum degree Delta, and an O(log(3) n)-round algorithm for sampling according to the hardcore model (weighted independent sets) in the uniqueness regime, which along with the Omega(diam) lower bound in [3] for sampling according to the hardcore model in the non-uniqueness regime, gives the first computational phase transition for distributed sampling.

关键词： distributed graph algorithms local computation sampling algorithms Gibbs distribution strong spatial mixing

来源：评论

学校读者我要写书评

暂无评论

A Classification of Product sampling for Software Product Lines 18

A Classification of Product Sampling for Software Product Li...

引用

22nd International Systems and Software Product Line Conference (SPLC)

作者： Varshosaz, Mahsa Al-Hajjaji, Mustafa Thum, Thomas Runge, Tobias Mousavi, Mohammad Reza Schaefer, Ina Halmstad Univ Halmstad Sweden Pure Syst GmbH Magdeburg Germany TU Braunschweig Braunschweig Germany Univ Leicester Leicester Leics England

ISBN: (纸本)9781450364645

The analysis of software product lines is challenging due to the potentially large number of products, which grow exponentially in terms of the number of features. Product sampling is a technique used to avoid exhaustive testing, which is often infeasible. In this paper, we propose a classification for product sampling techniques and classify the existing literature accordingly. We distinguish the important characteristics of such approaches based on the information used for sampling, the kind of algorithm, and the achieved coverage criteria. Furthermore, we give an overview on existing tools and evaluations of product sampling techniques. We share our insights on the state-of-the-art of product sampling and discuss potential future work.

关键词： sampling algorithms Software Product Lines Testing Feature Interaction Domain Models

来源：评论

学校读者我要写书评

暂无评论

Using a Many-Objective Optimization Algorithm to Select sampling Approaches for Imbalanced Datasets

Using a Many-Objective Optimization Algorithm to Select Samp...

引用

IEEE Congress on Evolutionary Computation (IEEE CEC) as part of the IEEE World Congress on Computational Intelligence (IEEE WCCI)

作者： Miranda, Pericles B. C. Morais, Romero F. A. B. Silva, Ricardo M. A. Univ Fed Rural Pernambuco Dept Comp Recife PE Brazil Univ Fed Pernambuco Ctr Informat Recife PE Brazil

ISBN: (纸本)9781509060177

Imbalanced datasets are pervasive and comprise many real-world applications, such as medical diagnosis and software fault detection. As common classifiers assume a balanced distribution of examples in the data, learning from imbalanced datasets presents its own challenges. sampling techniques play an essential role in aiding classifiers which learn from imbalanced datasets, as these techniques return a more balanced version of the imbalanced dataset. Given the current number of sampling techniques available, selecting a technique together with a set of values for its hyper-parameters is a time-consuming task. In this work, we treat the mentioned problem as a many-objective optimization problem. An evolutionary algorithm was applied to select sampling algorithms and their parameters to imbalanced datasets considering multiple performance criteria. In the experiments, we compared the proposed method against the brute-force, the default (all sampling algorithms with their default hyper-parameters' values), and the random approaches. The experiments revealed that the proposal reached results comparable to those achieved by the brute-force approach, overcame the techniques with their default parameters most of the time, and surpassed the random search approach in the majority of the problems.

关键词： Imbalanced Datasets sampling algorithms Many-Objective Optimization

来源：评论

学校读者我要写书评

暂无评论

The simulated tempering method in the infinite switch limit with adaptive weight learning

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2019年第1期2019卷 013207-013207页

作者： Martinsson, Anton Lu, Jianfeng Leimkuhler, Benedict Vanden-Eijnden, Eric Univ Edinburgh Sch Math James Clerk Maxwell Bldg Edinburgh EH9 3FD Midlothian Scotland Univ Edinburgh Maxwell Inst James Clerk Maxwell Bldg Edinburgh EH9 3FD Midlothian Scotland Duke Univ Dept Math Durham NC 27708 USA Duke Univ Dept Phys Durham NC 27708 USA Duke Univ Dept Chem Durham NC 27708 USA New York Univ Courant Inst Math Sci 251 Mercer St New York NY 10012 USA

We investigate the theoretical foundations of the simulated tempering (ST) method and use our findings to design an efficient accelerated sampling algorithm. Employing a large deviation argument first used for replica exchange molecular dynamics (Plattner et al 2011 J. Chem. Phys. 135 134111), we demonstrate that the most efficient approach to simulated tempering is to vary the temperature infinitely rapidly. In this limit, we can replace the equations of motion for the temperature and physical variables by averaged equations for the latter alone, with the forces rescaled according to a position-dependent function defined in terms of temperature weights. The averaged equations are similar to those used in Gao's integrated-over-temperature method, except that we show that it is better to use a continuous rather than a discrete set of temperatures. We give a theoretical argument for the choice of the temperature weights as the reciprocal partition function, thereby relating simulated tempering to Wang-Landau sampling. Finally, we describe a self-consistent algorithm for simultaneously sampling the canonical ensemble and learning the weights during simulation. This infinite switch simulated tempering (ISST) algorithm is tested on three examples of increasing complexity: a system of harmonic oscillators;a continuous variant of the Curie-Weiss model, where ISST is shown to perform better than standard ST and to accurately capture the second-order phase transition observed in this model;and alanine-12 in vacuum, where ISST also compares favorably with standard ST in its ability to calculate the free energy profiles of the root mean square deviation (RMSD) and radius of gyration of the molecule in the 300-500 K temperature range.

关键词： sampling algorithms mixing stochastic processes large deviation molecular dynamics

来源：评论

学校读者我要写书评

暂无评论

Markov chains and emergent behavior for problems from discrete geometry

Markov chains and emergent behavior for problems from discre...

引用

作者： Cannon, Sarah Georgia Institute of Technology

学位级别：博士

The problem of generating random samples from large, complex sets is widespread across the sciences, where such samples provide one way to begin to learn about the sets' typical properties. However, when the samples generated are unexpectedly correlated or drawn from the wrong distribution, this can produce misleading conclusions. One way to generate random samples is with Markov chains, which are widely used but often applied without careful analysis of their mixing time, how long they must run for until they are guaranteed to produce good samples. We present new mixing time bounds for two sampling problems from discrete geometry: dyadic tilings, combinatorial structures with applications in machine learning and harmonic analysis, and 3-colorings on a grid, an instance of the celebrated antiferromagnetic Potts model from statistical physics. Both of these results required the development of new techniques. In addition, we use Markov chains in a novel way to address research questions in programmable matter. Here, a main goal is to understand how simple computational elements can collectively accomplish complicated system-level goals. In an abstracted setting, we show that groups of particles executing our simple processes, based on Markov chains, can accomplish various tasks. This includes compression, a behavior exhibited by natural distributed systems such as fire ants and honey bees, and shortcut bridging, where the particles build bridges that optimize the same global trade-off as certain bridge-building ant colonies. Throughout, a key ingredient is the interplay between global properties of Markov chains, including but not limited to mixing time, and their dependence on local moves, or Markov chain transitions that change only a small part of the configuration. We call the global behavior that arises out of these local moves and their probabilities emergent behavior. In addition to understanding the relationship between local moves and mixing times in order to

关键词： Markov chains sampling algorithms Randomized algorithms Discrete geometry Dyadic tilings Programmable matter Self-organization

来源：评论

学校读者我要写书评

暂无评论

Computing return times or return periods with rare event algorithms

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2018年第4期2018卷 043213-043213页

作者： Lestang, Thibault Ragone, Francesco Brehier, Charles-Edouard Herbert, Corentin Bouchet, Freddy Univ Claude Bernard Univ Lyon ENS Lyon CNRSLab Phys F-69342 Lyon France Univ Claude Bernard Univ Lyon Ecole Cent Lyon CNRSLab Mecan Fluides & Acoust F-69134 Ecully France Univ Milano Bicocca Dept Earth & Environm Sci Milan Italy Univ Claude Bernard Lyon 1 Univ Lyon CNRS UMR 5208 Inst Camille Jordan 43 Blvd 11 Novembre 1918 F-69622 Villeurbanne France

The average time between two occurrences of the same event, referred to as its return time (or return period), is a useful statistical concept for practical applications. For instance insurances or public agencies may be interested by the return time of a 10 m flood of the Seine river in Paris. However, due to their scarcity, reliably estimating return times for rare events is very dificult using either observational data or direct numerical simulations. For rare events, an estimator for return times can be built from the extrema of the observable on trajectory blocks. Here, we show that this estimator can be improved to remain accurate for return times of the order of the block size. More importantly, we show that this approach can be generalised to estimate return times from numerical algorithms specifically designed to sample rare events. So far those algorithms often compute probabilities, rather than return times. The approach we propose provides a computationally extremely efficient way to estimate numerically the return times of rare events for a dynamical system, gaining several orders of magnitude of computational costs. We illustrate the method on two kinds of observables, instantaneous and time-averaged, using two different rare event algorithms, for a simple stochastic process, the Ornstein-Uhlenbeck process. As an example of realistic applications to complex systems, we finally discuss extreme values of the drag on an object in a turbulent flow.

关键词： classical Monte Carlo simulations large deviations in non-equilibrium systems sampling algorithms mixing extreme value

来源：评论

学校读者我要写书评

暂无评论

Flexible Backbone Methods for Predicting and Designing Peptide Specificity

Flexible Backbone Methods for Predicting and Designing Pepti...

引用

作者： Noah Ollikainen

Protein–protein interactions play critical roles in essentially every cellular process. These interactions are often mediated by protein interaction domains that enable proteins to recognize their interaction partners, often by binding to short peptide motifs. For example, PDZ domains, which are among the most common protein interaction domains in the human proteome, recognize specific linear peptide sequences that are often at the C-terminus of other proteins. Determining the set of peptide sequences that a protein interaction domain binds, or it’s “peptide specificity,” is crucial for understanding its cellular function, and predicting how mutations impact peptide specificity is important for elucidating the mechanisms underlying human diseases. Moreover, engineering novel cellular functions for synthetic biology applications, such as the biosynthesis of biofuels or drugs, requires the design of protein interaction specificity to avoid crosstalk with native metabolic and signaling pathways. The ability to accurately predict and design protein–peptide interaction specificity is therefore critical for understanding and engineering biological function. One approach that has recently been employed toward accomplishing this goal is computational protein design. This chapter provides an overview of recent methodological advances in computational protein design and highlights examples of how these advances can enable increased accuracy in predicting and designing peptide specificity. less

关键词： Protein design Protein interactions Conformational ensembles sampling algorithms Backbone flexibility Specificity prediction Designing specificity

来源：评论

学校读者我要写书评

暂无评论

RRS: Rapidly-Exploring Random Snakes a New Method for Mobile Robot Path Planning 13th

RRS: Rapidly-Exploring Random Snakes a New Method for Mobile...

引用

13th International Conference on Intelligent Autonomous Systems (IAS)

作者： Baizid, K. Chellali, R. Luza, R. Vitezslav, B. Arrichiello, F. Univ Cassino & Southern Lazio Via G Di Biasio 43 I-03043 Cassino FR Italy Fdn Inst Italiano Technol IIT Via Morego 30 Genoa Italy Univ Technol Brno BUT Brno Czech Republic

ISBN: (纸本)9783319083384;9783319083377

Recently, sampling-based path planning algorithms have been implemented in many practical robotics tasks. However, little improvements have been dedicated to the returned solution (quality) and sampling process. The aim of this paper is to introduce a new technique that improves the classical rapidly-exploring random trees (RRT) algorithm. First, the sampling step is modified in order to increase the number of possible solutions in the free space. Second, within the possible solutions, we apply an optimization scheme that gives the best solution in term of safety and shortness. The proposed solution, namely, rapidly-exploring random snakes (RRS) is a combination of a modified deformable Active Contours Model (called Snakes) and the RRT. The RRS takes the advantage of both RRT and deformable Snakes contours, respectively, in: rapidly searching new candidate nodes in the free space and circumnavigating obstacles by calculating a safe sub-path in the free space toward the new node created by the RRT. In comparison to the classical RRT, the proposed algorithm increases the probability of completeness, accelerates the convergence and generates a much safer and shorter open-loop solution, hence, increasing considerably the efficiency of the classical RRT. The proposed approach has been validated via numerical simulations and experimental results with a mobile robot.

关键词： Path planning Active counter model sampling algorithms Snake

来源：评论

学校读者我要写书评

暂无评论

Extension of the constant exchange probability method to multi-dimensional replica exchange Monte Carlo applied to the tri-critical spin-1 Blume-Capel model

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2016年第12期2016卷 123207-123207页

作者： Kimura, Kenji Higuchi, Saburo Ryukoku Univ Dept Appl Math & Informat Otsu Shiga 5202194 Japan

In replica exchange Monte Carlo (REM), tuning of the temperature set and the exchange scheduling are crucial in improving the accuracy and reducing calculation time. In multi-dimensional simulated tempering, the first order phase transition is accessible. Therefore it is important to study the tuning of parameter set and the scheduling of exchanges in the parallel counterpart, the multi-dimensional REM. We extend Hukushima's constant exchange probability method to multi-dimensional REM for the parameter set. We further propose a combined method to use this set and the Bittner-Nussbaumer-Janke's PT tau algorithm for scheduling. We test the proposed method in the two-dimensional spin-1 Blume-Capel model and find that it works efficiently, including the vicinity of the first order phase transition.

关键词： classical Monte Carlo simulations sampling algorithms mixing classical phase transitions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：