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

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

来源：评论

学校读者我要写书评

暂无评论

Efficient sampling and Counting of Graph Structures Related to Chordal Graphs

Efficient Sampling and Counting of Graph Structures Related ...

引用

作者： Sun, Wenbo Rochester Institute of Technology

学位级别：Ph.D., Doctor of Philosophy

Counting problems aim to count the number of solutions for a given input, for example, counting the number of variable assignments that satisfy a Boolean formula. sampling problems aim to produce a random object from a desired distribution, for example, producing a variable assignment drawn uniformly at random from all assignments that satisfy a Boolean formula. The problems of counting and sampling of graph structures on different types of graphs have been studied for decades for their great importance in areas like complexity theory and statistical physics. For many graph structures such as independent sets and acyclic orientations, it is widely believed that no exact or approximate (with an arbitrarily small error) polynomial-time algorithms on general graphs exist. Therefore, the research community studies various types of graphs, aiming either to design a polynomial-time counting or sampling algorithm for such inputs, or to prove a corresponding inapproximability result. Chordal graphs have been studied widely in both AI and theoretical computer science, but their study from the counting perspective has been relatively limited. Previous works showed that some graph structures can be counted in polynomial time on chordal graphs, when their counting on general graphs is provably computationally hard. The main objective of this thesis is to design and analyze counting and sampling algorithms for several well-known graph structures, including independent sets and different types of graph orientations, on chordal graphs. Our contributions can be described from two perspectives: evaluating the performances of some well-known sampling techniques, such as Markov chain Monte Carlo, on chordal graphs; and showing that the chordality does make those counting problems polynomial-time solvable.

关键词： Chordal graphs Boolean formula sampling algorithms Graph structures

来源：评论

学校读者我要写书评

暂无评论

Optimal mixing via tensorization for random independent sets on arbitrary trees

引用

COMBINATORICS PROBABILITY AND COMPUTING 2024年第2期34卷 259-275页

作者： Efthymiou, Charilaos Hayes, Thomas P. Stefankovic, Daniel Vigoda, Eric Univ Warwick Dept Comp Sci Coventry England Univ Buffalo Dept Comp Sci & Engn New York NY USA Univ Rochester Dept Comp Sci Rochester NY USA Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA USA

We study the mixing time of the single-site update Markov chain, known as the Glauber dynamics, forgenerating a random independent set of a tree. Our focus is obtaining optimal convergence results forarbitrary trees. We consider the more general problem of sampling from the Gibbs distribution in the hard-core model where independent sets are weighted by a parameter lambda>0;the special case lambda=1 corresponds to the uniform distribution over all independent sets. Previous work of Martinelli, Sinclair and Weitz(2004) obtained optimal mixing time bounds for the complete Delta-regular tree for all lambda. However, Restrepo,Stefankovic, Vera, Vigoda, and Yang (2014) showed that for sufficiently large lambda there are bounded-degreetrees where optimal mixing does not hold. Recent work of Eppstein and Frishberg (2022) proved a poly-nomial mixing time bound for the Glauber dynamics for arbitrary trees, and more generally for graphs ofbounded tree-width. We establish an optimal bound on the relaxation time (i.e., inverse spectral gap) ofO(n) for the Glauber dynamics for unweighted independent sets on arbitrary trees. We stress that our results hold for arbitrarytrees and there is no dependence on the maximum degree Delta. Interestingly, our results extend (far) beyondthe uniqueness threshold which is on the order lambda=O(1/Delta). Our proof approach is inspired by recent workon spectral independence. In fact, we prove that spectral independence holds with a constant independentof the maximum degree for any tree, but this does not imply mixing for general trees as the optimal mixingresults of Chen, Liu, and Vigoda (2021) only apply for bounded-degree graphs. We instead utilize thecombinatorial nature of independent sets to directly prove approximate tensorization of variance via anon-trivial inductive proof.

关键词： Markov Chain Monte Carlo mixing time independent sets hard-core model approximate counting algorithms sampling algorithms

来源：评论

学校读者我要写书评

暂无评论

Hybrid algorithms for approximate belief updating in Bayes nets

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 1997年第2-3期17卷 191-216页

作者： Santos, E Shimony, SE Williams, E BEN GURION UNIV NEGEV DEPT MATH & COMP SCIIL-84105 BEER SHEVAISRAEL USAF INST TECHNOLDEPT ELECT & COMP ENGNWRIGHT PATTERSON AFBOH 45433

Belief updating in Bayes nets, a well-known computationally hard problem, has recently been approximated by several deterministic algorithms and by various randomized approximation algorithms Deterministic algorithms usually provide probability bounds, but have an exponential runtime. Some randomized schemes have a polynomial runtime, but provide only probability estimates. Randomized algorithms that accumulate high-probability partial instantiations, resulting in probability bounds, are presented. Some of these algorithms are also sampling algorithms. Specifically, a variant of backward sampling, used both as a sampling algorithm and as a randomized enumeration algorithm, is introduced and evaluated An implicit assumption made in prior work, for both sampling and accumulation algorithms, that query nodes must be instantiated in all the samples, is relaxed Genetic algorithms can be used as an alternate search component for high-probability instantiations;several methods of applying them to belief updating are presented. (C) 1997 Elsevier Science Inc.

关键词： probabilistic reasoning Bayes networks belief updating approximation algorithms sampling algorithms genetic algorithms

来源：评论

学校读者我要写书评

暂无评论

Geometric inhomogeneous random graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 760卷 35-54页

作者： Bringmann, Karl Keusch, Ralph Lengler, Johannes Max Planck Inst Informat Saarbrucken Germany Swiss Fed Inst Technol Inst Theoret Comp Sci Zurich Switzerland

Real-world networks, like social networks or the internet infrastructure, have structural properties such as large clustering coefficients that can best be described in terms of an underlying geometry. This is why the focus of the literature on theoretical models for real-world networks shifted from classic models without geometry, such as Chung-Lu random graphs, to modern geometry-based models, such as hyperbolic random graphs. With this paper we contribute to the theoretical analysis of these modern, more realistic random graph models. Instead of studying directly hyperbolic random graphs, we use a generalization that we call geometric inhomogeneous random graphs (GIRGs). Since we ignore constant factors in the edge probabilities, GIRGs are technically simpler (specifically, we avoid hyperbolic cosines), while preserving the qualitative behavior of hyperbolic random graphs, and we suggest to replace hyperbolic random graphs by this new model in future theoretical studies. We prove the following fundamental structural and algorithmic results on GIRGs. (1) We provide a sampling algorithm that generates a random graph from our model in expected linear time, improving the best-known sampling algorithm for hyperbolic random graphs by a substantial factor O (root n). (2) We establish that GIRGs have clustering coefficients in Omega(1), (3) we prove that GIRGs have small separators, i.e., it suffices to delete a sublinear number of edges to break the giant component into two large pieces, and (4) we show how to compress GIRGs using an expected linear number of bits. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Real-world networks Random graph models Hyperbolic random graphs sampling algorithms Compression algorithms Clustering coefficient

来源：评论

学校读者我要写书评

暂无评论

The trichotomy of HAVING queries on a probabilistic database

引用

VLDB JOURNAL 2009年第5期18卷 1091-1116页

作者： Re, Christopher Suciu, Dan Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA

We study the evaluation of positive conjunctive queries with Boolean aggregate tests (similar to HAVING in SQL) on probabilistic databases. More precisely, we study conjunctive queries with predicate aggregates on probabilistic databases where the aggregation function is one of MIN, MAX, EXISTS, COUNT, SUM, AVG, or COUNT(DISTINCT) and the comparison function is one of =, not equal, >=, >, <=, or <. The complexity of evaluating a HAVING query depends on the aggregation function, alpha, and the comparison function, theta. In this paper, we establish a set of trichotomy results for conjunctive queries with HAVING predicates parametrized by (alpha, theta). For such queries (without self-joins), one of the following three statements is true: (1) the exact evaluation problem has P-time data complexity. In this case, we call the query safe. (2) The exact evaluation problem is #P-hard, but the approximate evaluation problem has (randomized) P-time data complexity. More precisely, there exists an FPTRAS for the query. In this case, we call the query apx-safe. (3) The exact evaluation problem is #P-hard, and the approximate evaluation problem is also hard. We call these queries hazardous. The precise definition of each class depends on the aggregate considered and the comparison function. Thus, we have queries that are (MAX, >=)-safe, (COUNT, <=)-apx- safe, (SUM, =)-h azardous, etc. Our trichotomy result is a significant extension of a previous dichotomy result for Boolean conjunctive queries into safe and not safe. For each of the three classes we present novel techniques. For safe queries, wedescribe an evaluation algorithm that uses random variables over semirings. For apx-safe queries, we describe an FPTRAS that relies on a novel algorithm for generating a random possible world satisfying a given condition. Finally, for hazardous queries we give novel proofs of hardness of approximation. The results for safe queries were previously announced (in Re, C., Suciu, D. Efficien

关键词： Probabilistic databases Query evaluation sampling algorithms Semirings Safe plans

来源：评论

学校读者我要写书评

暂无评论

A Configuration Deactivation Algorithm for Boosting Probabilistic Roadmap Planning of Robots

引用

International Journal of Automation and computing 2012年第2期9卷 155-164页

作者： Mika T. Rantanen Martti Juhola Computer Sciences School of Information Sciences University of Tampere

We present a method to improve the execution time used to build the roadmap in probabilistic roadmap planners. Our method intelligently deactivates some of the configurations during the learning phase and allows the planner to concentrate on those configurations that axe most likely going to be useful when building the roadmap. The method can be used with many of the existing sampling algorithms. We ran tests with four simulated robot problems typical in robotics literature. The sampling methods applied were purely random, using Halton numbers, Gaussian distribution, and bridge test technique. In our tests, the deactivation method clearly improved the execution times. Compared with pure random selections, the deactivation method also significantly decreased the size of the roadmap, which is a useful property to simplify roadmap planning tasks.

关键词： Probabilistic roadmaps motion planning collision avoidance sampling algorithms robotics.

来源：评论

学校读者我要写书评

暂无评论

Tiny families of functions with random properties: A quality-size trade-off for hashing

引用

RANDOM STRUCTURES & algorithms 1997年第4期11卷 315-343页

作者： Goldreich, O Wigderson, A HEBREW UNIV JERUSALEM INST COMP SCI JERUSALEM ISRAEL

We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family), and the quality (or error parameter) of the pseudorandom property it achieves. Unlike previous constructions, most notably universal hashing, the size of our families is essentially independent of the size of the domain on which the functions operate. The first construction is for the mixing property-mapping a proportional part of any subset of the domain to any other subset. The other two are for the extraction property-mapping any subset of the domain almost uniformly into a range smaller than it. The second and third constructions handle, respectively, the extreme situations when the range is very large or very small. We provide lower bounds showing that our constructions are nearly optimal, and mention some applications of the new constructions. (C) 1997 John Wiley & Sons, Inc.

关键词： randomness and computation randomness extractors sampling algorithms random-looking functions expander graphs Ramanujan graphs universal hashing small-biased probability spaces Lindsey's lemma

来源：评论

学校读者我要写书评

暂无评论

Is there an analog of Nesterov acceleration for gradient-based MCMC?

引用

BERNOULLI 2021年第3期27卷 1942-1992页

作者： Ma, Yi-An Chatterji, Niladri S. Cheng, Xiang Flammarion, Nicolas Bartlett, Peter L. Jordan, Michael, I Univ Calif San Diego Halicioglu Data Sci Inst San Diego CA 92093 USA Univ Calif Berkeley Dept Phys Berkeley CA 94720 USA Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Ecole Polytech Fed Lausanne Sch Comp & Commun Sci Lausanne Switzerland Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

We formulate gradient-based Markov chain Monte Carlo (MCMC) sampling as optimization on the space of probability measures, with Kullback-Leibler (KL) divergence as the objective functional. We show that an under-damped form of the Langevin algorithm performs accelerated gradient descent in this metric. To characterize the convergence of the algorithm, we construct a Lyapunov functional and exploit hypocoercivity of the underdamped Langevin algorithm. As an application, we show that accelerated rates can be obtained for a class of nonconvex functions with the Langevin algorithm.

关键词： Markov chain Monte Carlo Langevin Monte Carlo accelerated gradient descent sampling algorithms

来源：评论

学校读者我要写书评

暂无评论

A Bayesian approach to bandwidth selection for multivariate kernel density estimation

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 2006年第11期50卷 3009-3031页

作者： Zhang, Xibin King, Maxwell L. Hyndman, Rob J. Monash Univ Dept Econometr & Business Stat Clayton Vic 3800 Australia

Kernel density estimation for multivariate data is an important technique that has a wide range of applications. However, it has received significantly less attention than its univariate counter-part. The lower level of interest in multivariate kernel density estimation is mainly due to the increased difficulty in deriving an optimal data-driven bandwidth as the dimension of the data increases. We provide Markov chain Monte Carlo (MCMC) algorithms for estimating optimal bandwidth matrices for multivariate kernel density estimation. Our approach is based on treating the elements of the bandwidth matrix as parameters whose posterior density can be obtained through the likelihood cross-validation criterion. Numerical studies for bivariate data show that the MCMC algorithm generally performs better than the plug-in algorithm under the Kullback-Leibler information criterion, and is as good as the plug-in algorithm under the mean integrated squared error (MISE) criterion. Numerical studies for five-dimensional data show that our algorithm is superior to the normal reference rule. Our MCMC algorithm is the first data-driven bandwidth selector for multivariate kernel density estimation that is applicable to data of any dimension. (C) 2005 Elsevier B.V. All rights reserved.

关键词： cross-validation Kullback-Leibler information mean integrated squared errors sampling algorithms Monte Carlo kernel likelihood

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：