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

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 1

引用

丛书名： Lecture Notes in computer science

1000年

作者： Irit Dinur Klaus Jansen Joseph Naor José Rolim

来源：评论

学校读者我要写书评

暂无评论

Active learning with distributional estimates

Active learning with distributional estimates

引用

28th Conference on Uncertainty in Artificial Intelligence, UAI 2012

作者： Röder, Jens Nadler, Boaz Kunzmann, Kevin Hamprecht, Fred A. CR/AEM Robert Bosch GmbH Hildesheim Germany Department of Computer Science and Applied Math Weizmann Institute of Science Rehovot Israel University of Heidelberg Heidelberg Germany

ISBN: (纸本)9780974903989

Active Learning (AL) is increasingly important in a broad range of applications. Two main AL principles to obtain accurate classification with few labeled data are refinement of the current decision boundary and exploration of poorly sampled regions. In this paper we derive a novel AL scheme that balances these two principles in a natural way. In contrast to many AL strategies, which are based on an estimated class conditional probability p(y|x), a key component of our approach is to view this quantity as a random variable, hence explicitly considering the uncertainty in its estimated value. Our main contribution is a novel mathematical framework for uncertainty-based AL, and a corresponding AL scheme, where the uncertainty in p(y|x) is modeled by a second-order distribution. On the practical side, we show how to approximate such secondorder distributions for kernel density classification. Finally, we find that over a large number of UCI, USPS and Caltech- 4 datasets, our AL scheme achieves significantly better learning curves than popular AL methods such as uncertainty sampling and error reduction sampling, when all use the same kernel density classifier.

关键词： Uncertainty analysis

来源：评论

学校读者我要写书评

暂无评论

Computation of the normal forms for general M-DOF systems using multiple time scales. Part II: Non-autonomous systems

引用

Communications in Nonlinear science and Numerical Simulation 2006年第1期11卷 45-81页

作者： Zhu, Songhui Yu, Pei Department of Applied Mathematics Faculty of Sciences The University of Western Ontario London Ont. N6A 5B7 Canada Department of Math./Computer Science Benedict College Columbia SC 29204 United States

A perturbation technique has been developed in Part I to consider the computation of the normal forms for general multiple-degree-of-freedom autonomous systems. In this paper, the perturbation approach is extended to study general non-autonomous systems and is focused on systems with external forcing. With the aid of multiple time scales, efficient recursive algorithms are developed for systematically computing the normal forms. General solutions are obtained for solving ordered perturbation equations. In particular, the following cases are considered in detail: the non-resonance, internal resonances (including general resonance, resonant case involving 1:1 primary resonance, and combination of resonant case with non-resonance), and external resonances (including general resonance, and combination of internal resonance and external resonance). User-friendly Maple programs have been coded which can be "automatically" executed on various computer systems. Examples are given to demonstrate the computational efficiency of the method and the convenience of using computer algebra systems. © 2004 Elsevier B.V. All rights reserved.

关键词： Degrees of freedom (mechanics)

来源：评论

学校读者我要写书评

暂无评论

Approximating equilibria in sequential auctions with incomplete information and multi-unit demand

Approximating equilibria in sequential auctions with incompl...

引用

26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012

作者： Greenwald, Amy Li, Jiacui Sodomka, Eric Department of Computer Science Brown University Providence RI 02912 United States Department of Applied Math/Economics Brown University Providence RI 02912 United States

ISBN: (纸本)9781627480031

In many large economic markets, goods are sold through sequential auctions. Examples include eBay, online ad auctions, wireless spectrum auctions, and the Dutch flower auctions. In this paper, we combine methods from game theory and decision theory to search for approximate equilibria in sequential auction domains, in which bidders do not know their opponents' values for goods, bidders only partially observe the actions of their opponents', and bidders demand multiple goods. We restrict attention to two-phased strategies: first predict (i.e., learn);second, optimize. We use best-reply dynamics [4] for prediction (i.e., to predict other bidders' strategies), and then assuming fixed other-bidder strategies, we estimate and solve the ensuing Markov decision processes (MDP) [18] for optimization. We exploit auction properties to represent the MDP in a more compact state space, and we use Monte Carlo simulation to make estimating the MDP tractable. We show how equilibria found using our search procedure compare to known equilibria for simpler auction domains, and we approximate an equilibrium for a more complex auction domain where analytical solutions are unknown.

关键词： Markov processes

来源：评论

学校读者我要写书评

暂无评论

Shortest Path to a Segment and Quickest Visibility Queries 31

Shortest Path to a Segment and Quickest Visibility Queries

引用

31st International Symposium on Computational Geometry, SoCG 2015

作者： Arkin, Esther M. Efrat, Alon Knauer, Christian Mitchell, Joseph S.B. Polishchuk, Valentin Rote, Günter Schlipf, Lena Talvitie, Topi Department of Applied Math and Statistics Stony Brook University United States Department of Computer Science University of Arizona United States Institute of Computer Science Universität Bayreuth Germany Communications and Transport Systems ITN Linköping University Sweden Institute of Computer Science Freie Universität Berlin Germany Department of Computer Science University of Helsinki Finland

ISBN: (纸本)9783939897835

We show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortest-path-to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a different generalization of shortest-path-to-a-point queries, which may be of independent interest: to report efficiently a shortest path from s to a query segment in the domain.

关键词： Visibility

来源：评论

学校读者我要写书评

暂无评论

On the complexity of verifying concurrent transition systems 8th

On the complexity of verifying concurrent transition systems

引用

Proceedings of the 1997 8th International Conference on Concurrency Theory, CONCUR

作者： Harel, David Kupferman, Orna Vardi, Moshe Y. Department of Applied Math. and Computer Science The Weizmann Institute Rehovot 76100 Israel EECS Department UC Berkeley Berkeley 94720-1770 CA United States Rice University Department of Computer Science Houston 77251-1892 TX United States

ISBN: (纸本)3540631410

In implementation verification, we check that an implementation is correct with respect to a specification by checking whether the behaviors of a transition system that models the program's implementation correlate with the behaviors of a transition system that models its specification. In this paper, we investigate the effect of concurrency on the complexity of implementation verification. We consider trace-based and tree-based approaches to the verification of concurrent transition systems, with and without fairness. Our results show that in almost all cases the complexity of the problem is exponentially harder than that of the sequential case. Thus, as in the model-checking verification methodology, the state-explosion problem cannot be avoided.

关键词： Specifications

来源：评论

学校读者我要写书评

暂无评论

Natural Image Denoising: Optimality and Inherent Bounds

Natural Image Denoising: Optimality and Inherent Bounds

引用

IEEE Conference on computer Vision and Pattern Recognition

作者： Anat Levin Boaz Nadler Department of Computer Science and Applied Math The Weizmann Institute of Science

ISBN: (纸本)9781457703942

The goal of natural image denoising is to estimate a clean version of a given noisy image, utilizing prior knowledge on the statistics of natural images. The problem has been studied intensively with considerable progress made in recent years. However, it seems that image denoising algorithms are starting to converge and recent algorithms improve over previous ones by only fractional dB values. It is thus important to understand how much more can we still improve natural image denoising algorithms and what are the inherent limits imposed by the actual statistics of the data. The challenge in evaluating such limits is that constructing proper models of natural image statistics is a long standing and yet unsolved problem. To overcome the absence of accurate image priors, this paper takes a non parametric approach and represents the distribution of natural images using a huge set of 10~(10) patches. We then derive a simple statistical measure which provides a lower bound on the optimal Bayesian minimum mean square error (MMSE). This imposes a limit on the best possible results of denoising algorithms which utilize a fixed support around a denoised pixel and a generic natural image prior. Our findings suggest that for small windows, state of the art denoising algorithms are approaching optimality and cannot be further improved beyond ～ 0.1dB values.

关键词： image denoising Noisy Image fixed pivot DATA(STATISTICS) images optimality Mean square error Converge Prior Learning Noise reduction

来源：评论

学校读者我要写书评

暂无评论

Adjacency Sketches in Adversarial Environments

arXiv

引用

arXiv 2023年

作者： Naor, Moni Pekel, Eugene Department of Computer Science and Applied Math Weizmann Institute of Science

An adjacency sketching or implicit labeling scheme for a family F of graphs is a method that defines for any n vertex G ∈ F an assignment of labels to each vertex in G, so that the labels of two vertices tell you whether or not they are adjacent. The goal is to come up with labeling schemes that use as few bits as possible to represent the labels. By using randomness when assigning labels, it is sometimes possible to produce adjacency sketches with much smaller label sizes, but this comes at the cost of introducing some probability of error. Both deterministic and randomized labeling schemes have been extensively studied, as they have applications for distributed data structures and deeper connections to universal graphs and communication complexity. The main question of interest is which graph families have schemes using short labels, usually O(log n) in the deterministic case or constant for randomized sketches. In this work we consider the resilience of probabilistic adjacency sketches against an adversary making adaptive queries to the labels. This differs from the previously analyzed probabilistic setting which is "one shot". We show that in the adaptive adversarial case the size of the labels is tightly related to the maximal degree of the graphs in F . This results in a stronger characterization compared to what is known in the non-adversarial setting. In more detail, we construct sketches that fail with probability Ε for graphs with maximal degree d using 2d log(1/Ε) bit labels and show that this is roughly the best that can be done for any specific graph of maximal degree d, e.g. a d-ary *** Codes 68W20, 68W40, 68Q87 Copyright © 2023, The Authors. All rights reserved.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

The Grad of a Graph and Classes with Bounded Expansion

引用

Electronic Notes in Discrete mathematics 2005年 22卷 101-106页

作者： Nešetřil, Jaroslav Ossona de Mendez, Patrice Department of Applied Mathematics Institute of Theoretical Computer Science Charles University Praha Czech Republic Centre d'Analyse Mathématiques Sociales - CNRS UMR 8557 Paris France

We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇_r (G). We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings and homomorphism dualities. © 2005 Elsevier B.V. All rights reserved.

关键词： Bounded expansion Coloring Constrained orientation Homomorphism Restricted duality Transitive fraternal augmentation Tree-depth

来源：评论

学校读者我要写书评

暂无评论

Fraternal Augmentations of graphs, Coloration and Minors

引用

Electronic Notes in Discrete mathematics 2007年 28卷 223-230页

We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇_r (G). We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings, a linear time algorithm to check subgraph isomorphism for a fixed pattern and homomorphism dualities. © 2007 Elsevier B.V. All rights reserved.

关键词： Bounded expansion Coloring Graph Algorithm Homomorphism Ramsey number Restricted duality Subgraph Isomorphism Transitive fraternal augmentation Tree-depth

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：