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

FPGA implementation of a stochastic neural network for monotonic pseudo-boolean optimization

NEURAL NETWORKS 2008年第6期21卷 872-879页

作者： Grossi, Giuliano Pedersini, Federico Univ Milan Dipartimento Sci Informaz I-20135 Milan Italy

In this paper a FPGA implementation of a novel neural stochastic model for solving constrained NP-hard problems is proposed and developed. The model exploits pseudo-boolean functions both to express the constraints and to define the cost function, interpreted as energy of a neural network. A wide variety of NP-hard problems falls in the class of problems that can be solved by this model, particularly those having a quadratic pseudo-boolean penalty function. The proposed hardware implementation provides high computation speed by exploiting parallelism, as the neuron update and the constraint violation check can be performed in parallel over the whole network. The neural system has been tested on random and benchmark graphs, showing good performance with respect to the same heuristic for the same problems. Furthermore, the computational speed of the FPGA implementation has been measured and compared to software implementation. The developed architecture featured dramatically faster computation, with respect to the software implementation, even adopting a low-cost FPGA chip. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： stochastic model FPGA optimization pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

On Sugeno integral as an aggregation function

引用

FUZZY SETS AND SYSTEMS 2000年第3期114卷 347-365页

作者： Marichal, JL Univ Liege FEGSS Dept Management B-4000 Liege Belgium

The Sugeno integral, for a given fuzzy measure, is studied under the viewpoint of aggregation. In particular, we give some equivalent expressions of it. We also give an axiomatic characterization of the class of all the Sugeno integrals. Some particular subclasses, such as the weighted maximum and minimum functions are investigated as well. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： fuzzy measures Sugeno integral aggregation functions multicriteria decision making pseudo-boolean functions max-min algebra ordinal scales

来源：评论

学校读者我要写书评

暂无评论

On the computational power of max-min propagation neural networks

引用

NEURAL PROCESSING LETTERS 2004年第1期19卷 11-23页

作者： Estévez, PA Okabe, Y Univ Chile Dept Elect Engn Santiago 6513027 Chile Univ Tokyo Grad Sch Engn Bunkyo Ku Tokyo 1138656 Japan

We investigate the computational power of max-min propagation (MMP) neural networks, composed of neurons with maximum (Max) or minimum (Min) activation functions, applied over the weighted sums of inputs. The main results presented are that a single-layer MMP network can represent exactly any pseudo-boolean function F: {0;1}(n) --> [0;1], and that two-layer MMP neural networks are universal approximators. In addition, it is shown that several well-known fuzzy min-max (FMM) neural networks, such as Simpson's FMM, are representable by MMP neural networks.

关键词： computational power max-min propagation neural networks pseudo-boolean functions universal approximation

来源：评论

学校读者我要写书评

暂无评论

Factored edge-valued binary decision diagrams

引用

FORMAL METHODS IN SYSTEM DESIGN 1997年第2-3期10卷 243-270页

作者： Tafertshofer, P Pedram, M TECH UNIV MUNICH INST ELECT DESIGN AUTOMAT D-8000 MUNICH GERMANY UNIV SO CALIF DEPT ELECT ENGN SYST LOS ANGELES CA 90089 USA

Factored Edge-Valued Binary Decision Diagrams form an extension to Edge-Valued Binary Decision Diagrams. By associating both an additive and a multiplicative weight with the edges, FEVBDDs can be used to represent a wider range of functions concisely. As a result, the computational complexity for certain operations can be significantly reduced compared to EVBDDs. Additionally, the introduction of multiplicative edge weights allows us to directly represent the so-called complement edges which are used in OBDDs, thus providing a one to one mapping of all OBDDs to FEVBDDs. Applications such as integer linear programming and logic verification that have been proposed for EVBDDs also benefit from the extension. We also present a complete matrix package based on FEVBDDs and apply the package to the problem of solving the Chapman-Kolmogorov equations.

关键词： Ordered Binary Decision Diagrams pseudo-boolean functions affine property logic verification integer linear programming matrix operations

来源：评论

学校读者我要写书评

暂无评论

Quadratic reformulations of nonlinear binary optimization problems

引用

MATHEMATICAL PROGRAMMING 2017年第1-2期162卷 115-144页

作者： Anthony, Martin Boros, Endre Crama, Yves Gruber, Aritanan London Sch Econ & Polit Sci Dept Math London England Rutgers State Univ MSIS Dept New Brunswick NJ USA Rutgers State Univ RUTCOR New Brunswick NJ USA Univ Liege HEC Management Sch QuantOM Liege Belgium Univ Sao Paulo Inst Math & Stat Sao Paulo Brazil

Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case. Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision, various techniques have been recently developed to reduce the general case to the quadratic one, at the cost of increasing the number of variables by introducing additional auxiliary variables. In this paper we initiate a systematic study of these quadratization approaches. We provide tight lower and upper bounds on the number of auxiliary variables needed in the worst-case for general objective functions, for bounded-degree functions, and for a restricted class of quadratizations. Our upper bounds are constructive, thus yielding new quadratization procedures. Finally, we completely characterize all "minimal" quadratizations of negative monomials.

关键词： Nonlinear binary optimization Quadratic binary optimization pseudo-boolean functions Reformulation methods

来源：评论

学校读者我要写书评

暂无评论

Prior specification for binary Markov mesh models

引用

STATISTICS AND COMPUTING 2019年第2期29卷 367-389页

作者： Luo, Xin Tjelmeland, Hakon Norwegian Univ Sci & Technol Dept Math Sci Trondheim Norway

We propose prior distributions for all parts of the specification of a Markov mesh model. In the formulation, we define priors for the sequential neighborhood, for the parametric form of the conditional distributions and for the parameter values. By simulating from the resulting posterior distribution when conditioning on an observed scene, we thereby obtain an automatic model selection procedure for Markov mesh models. To sample from such a posterior distribution, we construct a reversible jump Markov chain Monte Carlo algorithm (RJMCMC). We demonstrate the usefulness of our prior formulation and the limitations of our RJMCMC algorithm in two examples.

关键词： Markov mesh model Prior construction pseudo-boolean functions Reversible jump MCMC Sequential neighborhood

来源：评论

学校读者我要写书评

暂无评论

Approximate computations for binary Markov random fields and their use in Bayesian models

引用

STATISTICS AND COMPUTING 2017年第5期27卷 1271-1292页

作者： Austad, Haakon Michael Tjelmeland, Hakon Norwegian Univ Sci & Technol Dept Math Sci N-7491 Trondheim Norway If P&C Oslo Norway

Discrete Markov random fields form a natural class of models to represent images and spatial datasets. The use of such models is, however, hampered by a computationally intractable normalising constant. This makes parameter estimation and a fully Bayesian treatment of discrete Markov random fields difficult. We apply approximation theory for pseudo-boolean functions to binary Markov random fields and construct approximations and upper and lower bounds for the associated computationally intractable normalising constant. As a by-product of this process we also get a partially ordered Markov model approximation of the binary Markov random field. We present numerical examples with both the pairwise interaction Ising model and with higher-order interaction models, showing the quality of our approximations and bounds. We also present simulation examples and one real data example demonstrating how the approximations and bounds can be applied for parameter estimation and to handle a fully Bayesian model computationally.

关键词： Approximate inference Bayesian analysis Discrete Markov random fields Image analysis pseudo-boolean functions Spatial data Variable elimination algorithm

来源：评论

学校读者我要写书评

暂无评论

RECOGNITION PROBLEMS FOR SPECIAL CLASSES OF POLYNOMIALS IN 0-1 VARIABLES

引用

MATHEMATICAL PROGRAMMING 1989年第2期44卷 139-155页

作者： CRAMA, Y 1.Capaciteitsgroep Kwantitatieve Economie Rijksuniversiteit Limburg Postbus 616 6200 MD Maastricht The Netherlands

This paper investigates the complexity of various recognition problems for pseudo-boolean functions (i.e., real-valued functions defined on the unit hypercubeB n = {0, 1} n ), when such functions are represented as ... 详细信息

This paper investigates the complexity of various recognition problems for pseudo-boolean functions (i.e., real-valued functions defined on the unit hypercubeB ⁿ = {0, 1}ⁿ), when such functions are represented as multilinear polynomials in their variables. Determining whether a pseudo-boolean function (a) is monotonic, or (b) is supermodular, or (c) is threshold, or (d) has a unique local maximum in each face ofB ⁿ, or (e) has a unique local maximum inB ⁿ, is shown to be NP-hard. A polynomial-time recognition algorithm is presented for unimodular functions, previously introduced by Hansen and Simeone as a class of functions whose maximization overB ⁿ is reducible to a network minimum cut problem.

关键词： Nonlinear 0–1 optimization pseudo-boolean functions monotonicity supermodularity local extrema unimodularity NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Formal verification using edge-valued binary decision diagrams

引用

IEEE TRANSACTIONS ON COMPUTERS 1996年第2期45卷 247-255页

作者： Lai, YT Pedram, M Vrudhula, SBK UNIV SO CALIF DEPT ELECT ENGN SYST LOS ANGELES CA 90089 USA UNIV ARIZONA DEPT ELECT & COMP ENGN TUCSON AZ 85721 USA

In this paper we present a new data structure called Edge-Valued Binary-Decision Diagrams (EVBDD). An EVBDD is a directed acyclic graph, that provides a canonical and compact representation of functions that involve both boolean and integer quantities. In general, EVBDDS provide a more versatile and powerful representation that Ordinary Binary Decision Diagrams. We first describe the structure and properties of EVBDDS, and present a general algorithm for performing a variety of binary operations. Next, we describe an important extension of EVBDDS, called Structural EVBDDS, and show how they can be used for hierarchical verification.

关键词： binary decision diagrams boolean functions pseudo-boolean functions verification

来源：评论

学校读者我要写书评

暂无评论

On anonymous and weighted voting systems

引用

THEORY AND DECISION 2021年第4期91卷 477-491页

作者： Freixas, Josep Pons, Montserrat Univ Politecn Cataluna Dept Math EPSEM Campus ManresaAv Bases Manresa 61-73 Manresa 08242 Spain

Many bodies around the world make their decisions through voting systems in which voters have several options and the collective result also has several options. Many of these voting systems are anonymous, i.e., all voters have an identical role in voting. Anonymous simple voting games, a binary vote for voters and a binary collective decision, can be represented by an easy weighted game, i.e., by means of a quota and an identical weight for the voters. Widely used voting systems of this type are the majority and the unanimity decision rules. In this article, we analyze the case in which voters have two or more voting options and the collective result of the vote has also two or more options. We prove that anonymity implies being representable through a weighted game if and only if the voting options for voters are binary. As a consequence of this result, several significant enumerations are obtained.

关键词： Decision-making Multichoice games Anonymous decision systems Weighted decision systems pseudo-boolean functions Enumerations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：