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

2nd Symposium on Inverse Problems, Design and Optimization

作者： Fox, Colin Univ Otago Dept Phys Dunedin New Zealand

Inferential solutions to inverse problems provide substantial advantages over deterministic methods, such as: quantitative estimates with posterior (data-dependent) error estimates, predictive densities, model comparison and direct support for optimal decisions. The ability to include arbitrary forward maps, and hence use high-level representations of the unknowns, allows structure-preserving model reduction and also allows 'classification' to be performed within the 'imaging' step. Since inferential methods make (provably) optimal use of data, the ability to reduce data to a minimal set gives cost savings in applications where collecting data is expensive. The price of these advantages is presently the relatively high computational cost of sampling algorithms for computing estimates. Hence the most significant advances are in computational methods for sample-based inference in inverse problems. In this article we review the inferential formulation of inverse problems, some reasons why it is necessary to take on the extra machinery of inferential solutions, the 'basement level' methods for computing inferential solutions, and summarize some recent advances in computational methods for inferential solutions to inverse problems.

关键词： inverse problems Bayesian inference Metropolis Hastings sampling algorithms computational cost

来源：评论

学校读者我要写书评

暂无评论

Algorithmic Pirogov-Sinai Theory 2019

Algorithmic Pirogov-Sinai Theory

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Helmuth, Tyler Perkins, Will Regts, Guus Univ Bristol Bristol Avon England Univ Illinois Chicago IL USA Univ Amsterdam Amsterdam Netherlands

ISBN: (纸本)9781450367059

We develop an efficient algorithmic approach for approximate counting and sampling in the low-temperature regime of a broad class of statistical physics models on finite subsets of the lattice Z(d) and on the torus (Z/nZ)(d). Our approach is based on combining contour representations from Pirogov-Sinai theory with Barvinok's approach to approximate counting using truncated Taylor series. Some consequences of our main results include an FPTAS for approximating the partition function of the hard-core model at sufficiently high fugacity on subsets of Z(d) with appropriate boundary conditions and an efficient sampling algorithm for the ferromagnetic Potts model on the discrete torus (Z/nZ)(d) at sufficiently low temperature.

关键词： Approximate counting algorithms Potts model Hard-core model statistical physics sampling algorithms Pirogov-Sinai theory

来源：评论

学校读者我要写书评

暂无评论

A Markov chain Monte Carlo approach to stereovision 7th

引用

7th European Conference on Computer Vision (ECCV 2002)

作者： Sénégas, J Ecole Mines Ctr Geostat F-77305 Fontainebleau France Istar F-06905 Sophia Antipolis France

ISBN: (纸本)3540437460

We propose Markov chain Monte Carlo sampling methods to address uncertainty estimation in disparity computation. We consider this problem at a postprocessing stage, i.e. once the disparity map has been computed, and suppose that the only information available is the stereoscopic pair. The method, which consists of sampling from the posterior distribution given the stereoscopic pair, allows the prediction of large errors which occur with low probability, and accounts for spatial correlations. The model we use is oriented towards an application to mid-resolution stereo systems, but we give insights on how it can be extended. Moreover, we propose a new sampling algorithm relying on Markov chain theory and the use of importance sampling to speed up the computation. The efficiency of the algorithm is demonstrated, and we illustrate our method with the computation of confidence intervals and-probability maps of large errors, which may be applied to optimize a trajectory in a three dimensional environment.

关键词： stereoscopic vision digital terrain models disparity uncertainty estimation sampling algorithms Bayesian computation inverse problems

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Sublinear algorithms for Gap Edit Distance 60

Sublinear Algorithms for Gap Edit Distance

引用

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

来源：评论

学校读者我要写书评

暂无评论

A Depth-dependent Derandomized sampling Algorithm for Lattice Decoding

A Depth-dependent Derandomized Sampling Algorithm for Lattic...

引用

2015 International Conference on Automation,Mechanical and Electrical Engineering(AMEE 2015)

作者： X.S.Chen Y.H.Sun R.Z.Yang Y.H.Zhang College of Electronic Information and Control Engineering Beijing University of Technology

Although lattice reduction aided decoding improves performance, it has a performance gap to maximum-likelihood(ML) decoding increasing with the lattice dimension. In view of this, efficient suboptimal decoding algorithms that can narrow the gap are desirable. The derandomized sampling(DS) algorithm recently proposed adopts a threshold-constant probability pruning strategy to generate the candidate lattice points, which can achieve the near optimal performance. In this paper, the existing DS algorithm is generalized by taking the information of search layer into account to introduce the depth-dependent probability threshold pruning strategy, and then the depth-dependent derandomized sampling(DDDS) decoding algorithm is proposed based on it. It is shown that the proposed DDDS algorithm can achieve a more flexible trade-off between performance and complexity by adjusting the pruning threshold.

关键词： multiple-input multiple-output(MIMO) system lattice decoding lattice reduction sampling algorithms

来源：评论

学校读者我要写书评

暂无评论

Bayesian Nonparametric Hidden Semi-Markov Models

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2013年第1期14卷 673-701页

作者： Johnson, Matthew J. Willsky, Alan S. MIT Informat & Decis Syst Lab Dept EECS Cambridge MA 02139 USA

There is much interest in the Hierarchical Dirichlet Process Hidden Markov Model (HDP-HMM) as a natural Bayesian nonparametric extension of the ubiquitous Hidden Markov Model for learning from sequential and time-series data. However, in many settings the HDP-HMM's strict Markovian constraints are undesirable, particularly if we wish to learn or encode non-geometric state durations. We can extend the HDP-HMM to capture such structure by drawing upon explicit-duration semi-Markov modeling, which has been developed mainly in the parametric non-Bayesian setting, to allow construction of highly interpretable models that admit natural prior information on state durations. In this paper we introduce the explicit-duration Hierarchical Dirichlet Process Hidden semi-Markov Model (HDP-HSMM) and develop sampling algorithms for efficient posterior inference. The methods we introduce also provide new methods for sampling inference in the finite Bayesian HSMM. Our modular Gibbs sampling methods can be embedded in samplers for larger hierarchical Bayesian models, adding semi-Markov chain modeling as another tool in the Bayesian inference toolbox. We demonstrate the utility of the HDP-HSMM and our inference methods on both synthetic and real experiments.

关键词： Bayesian nonparametrics time series semi-Markov sampling algorithms Hierarchical Dirichlet Process Hidden Markov Model

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：