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

26th IEEE International Workshop on Machine Learning for Signal Processing (MLSP)

作者： Su, Guolong Wei, Dennis Varshney, Kush R. Malioutov, Dmitry M. MIT 77 Massachusetts Ave Cambridge MA 02139 USA IBM Thomas J Watson Res Ctr Yorktown Hts NY USA

ISBN: (纸本)9781509007462

This paper develops a novel optimization framework for learning accurate and sparse two-level Boolean rules for classification, both in Conjunctive Normal Form (CNF, i.e. AND-of-ORs) and in Disjunctive Normal Form (DNF, i.e. OR-of-ANDs). In contrast to opaque models (e.g. neural networks), sparse two-level Boolean rules gain the crucial benefit of interpretability, which is necessary in a wide range of applications such as law and medicine and is attracting considerable attention in machine learning. This paper introduces two principled objective functions to trade off classification accuracy and sparsity, where 0-1 error and Hamming loss are used to characterize accuracy. We propose efficient procedures to optimize these objectives based on linear programming (LP) relaxation, block coordinate descent, and alternating minimization. We also describe a new approach to rounding any fractional values in the optimal solutions of LP relaxations. Experiments show that our new algorithms based on the Hamming loss objective provide excellent tradeoffs between accuracy and sparsity with improvements over state-of-the-art methods.

关键词： Sparse Boolean Classifier linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Rounding-based Moves for Semi-Metric Labeling

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2016年 17卷 1-42页

作者： Kumar, M. Pawan Dokania, Puneet K. Univ Oxford Dept Engn Sci Parks Rd Oxford OX1 3PJ England Cent Supelec Ctr Visual Comp F-92295 Chatenay Malabry France

Semi-metric labeling is a special case of energy minimization for pairwise Markov random fields. The energy function consists of arbitrary unary potentials, and pairwise potentials that are proportional to a given semi-metric distance function over the label set. Popular methods for solving semi-metric labeling include (i) move-making algorithms, which iteratively solve a minimum st-cut problem;and (ii) the linear programming (LP) relaxation based approach. In order to convert the fractional solution of the LP relaxation to an integer solution, several randomized rounding procedures have been developed in the literature. We consider a large class of parallel rounding procedures, and design move-making algorithms that closely mimic them. We prove that the multiplicative bound of a move-making algorithm exactly matches the approximation factor of the corresponding rounding procedure for any arbitrary distance function. Our analysis includes all known results for move-making algorithms as special cases.

关键词： semi-metric labeling move-making algorithms linear programming relaxation multiplicative bounds

来源：评论

学校读者我要写书评

暂无评论

Robust Optimization of Sums of Piecewise linear Functions with Application to Inventory Problems

引用

OPERATIONS RESEARCH 2016年第2期64卷 474-494页

作者： Ardestani-Jaafari, Amir Delage, Erick HEC Montreal Dept Decis Sci Montreal PQ H3T 2A7 Canada

Robust optimization is a methodology that has gained a lot of attention in the recent years. This is mainly due to the simplicity of the modeling process and ease of resolution even for large scale models. Unfortunately, the second property is usually lost when the cost function that needs to be "robustified" is not concave (or linear) with respect to the perturbing parameters. In this paper we study robust optimization of sums of piecewise linear functions over polyhedral uncertainty set. Given that these problems are known to be intractable, we propose a new scheme for constructing conservative approximations based on the relaxation of an embedded mixed-integer linear program and relate this scheme to methods that are based on exploiting affine decision rules. Our new scheme gives rise to two tractable models that, respectively, take the shape of a linear program and a semidefinite program, with the latter having the potential to provide solutions of better quality than the former at the price of heavier computations. We present conditions under which our approximation models are exact. In particular, we are able to propose the first exact reformulations for a robust (and distributionally robust) multi-item newsvendor problem with budgeted uncertainty set and a reformulation for robust multiperiod inventory problems that is exact whether the uncertainty region reduces to a L-1-norm ball or to a box. An extensive set of empirical results will illustrate the quality of the approximate solutions that are obtained using these two models on randomly generated instances of the latter problem.

关键词： optimization piecewise linear linear programming relaxation semidefinite program tractable approximations newsvendor problem inventory problem

来源：评论

学校读者我要写书评

暂无评论

Universality of the Local Marginal Polytope

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2015年第4期37卷 898-904页

作者： Prusa, Daniel Werner, Tomas Czech Tech Univ Dept Cybernet Prague 12135 Czech Republic

We show that solving the LP relaxation of the min-sum labeling problem (also known as MAP inference problem in graphical models, discrete energy minimization, or valued constraint satisfaction) is not easier than solving any linear program. Precisely, every polytope is linear-time representable by a local marginal polytope and every LP can be reduced in linear time to a linear optimization (allowing infinite costs) over a local marginal polytope. The reduction can be done (though with a higher time complexity) even if the local marginal polytope is restricted to have a planar structure.

关键词： Graphical model Markov random field discrete energy minimization valued constraint satisfaction linear programming relaxation local marginal polytope

来源：评论

学校读者我要写书评

暂无评论

Marginal Consistency: Upper-Bounding Partition Functions over Commutative Semirings

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2015年第7期37卷 1455-1468页

作者： Werner, Tomas Czech Tech Univ Dept Cybernet Prague 12135 Czech Republic

Many inference tasks in pattern recognition and artificial intelligence lead to partition functions in which addition and multiplication are abstract binary operations forming a commutative semiring. By generalizing max-sum diffusion (one of convergent message passing algorithms for approximate MAP inference in graphical models), we propose an iterative algorithm to upper bound such partition functions over commutative semirings. The iteration of the algorithm is remarkably simple: change any two factors of the partition function such that their product remains the same and their overlapping marginals become equal. In many commutative semirings, repeating this iteration for different pairs of factors converges to a fixed point when the overlapping marginals of every pair of factors coincide. We call this state marginal consistency. During that, an upper bound on the partition function monotonically decreases. This abstract algorithm unifies several existing algorithms, including max-sum diffusion and basic costraint propagation (or local consistency) algorithms in constraint programming. We further construct a hierarchy of marginal consistencies of increasingly higher levels and show than any such level can be enforced by adding identity factors of higher arity (order). Finally, we discuss instances of the framework for several semirings, including the distributive lattice and the max-sum and sum-product semirings.

关键词： Partition function commutative semiring graphical model Markov random field linear programming relaxation message passing max-sum diffusion soft constraint satisfaction local consistency constraint propagation

来源：评论

学校读者我要写书评

暂无评论

How Hard Is the LP relaxation of the Potts Min-Sum Labeling Problem? 10

How Hard Is the LP Relaxation of the Potts Min-Sum Labeling ...

引用

10th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR)

作者： Prusa, Daniel Werner, Tomas Czech Tech Univ Fac Elect Engn Prague 12135 2 Czech Republic

ISBN: (纸本)9783319146126;9783319146119

An important subclass of the min-sum labeling problem (also known as discrete energy minimization or valued constraint satisfaction) is the pairwise min-sum problem with arbitrary unary costs and attractive Potts pairwise costs (also known as the uniform metric labeling problem). In analogy with our recent result, we show that solving the LP relaxation of the Potts min-sum problem is not significantly easier than that of the general min-sum problem and thus, in turn, the general linear program. This suggests that trying to find an efficient algorithm to solve the LP relaxation of the Potts min-sum problem has a fundamental limitation. Our constructions apply also to integral solutions, yielding novel reductions of the (non-relaxed) general min-sum problem to the Potts min-sum problem.

关键词： Markov random field discrete energy minimization valued constraint satisfaction linear programming relaxation uniform metric labeling problem Potts model

来源：评论

学校读者我要写书评

暂无评论

LP relaxation-based solution algorithms for the multi-mode project scheduling with a non-renewable resource

引用

EUROPEAN JOURNAL OF INDUSTRIAL ENGINEERING 2015年第4期9卷 450-469页

作者： Azizoglu, Meral Cetinkaya, Ferda Can Pamir, Selin Kirbiyik Middle E Tech Univ Dept Ind Engn TR-06800 Ankara Turkey Cankaya Univ Fac Engn Dept Ind Engn TR-06810 Ankara Turkey Genel Energy Next Level Is Merkezi Eskisehir Yolu TR-06500 Ankara Turkey

In this study, we consider a multi-mode resource allocation problem with a single non-renewable resource. We assume the resource is released at defined time points and at defined quantities. We also assume that the activity costs are charged once they are completed. Our aim is to minimise the project completion time. We formulate the problem as a pure integer programming model and show that it is strongly NP-hard. We find lower bounds by pure and mixed integer linear programming relaxations of the model and develop three heuristic procedures based on those relaxations. The results of our computational study have revealed the satisfactory performances of our lower bounds and heuristic procedures.

关键词： project scheduling multi-modes non-renewable resource integer programming linear programming relaxation heuristics

来源：评论

学校读者我要写书评

暂无评论

Rounding-based moves for semi-metric labeling

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2016年第1期17卷

作者： Kevin Murphy Bernhard Schölkopf M. Pawan Kumar Puneet K. Dokania Google MPI for Intelligent Systems Department of Engineering Science University of Oxford United Kingdom Center for Visual Computing CentraleSupelec Châtenay-Malabry France

Semi-metric labeling is a special case of energy minimization for pairwise Markov random fields. The energy function consists of arbitrary unary potentials, and pairwise potentials that are proportional to a given semi-metric distance function over the label set. Popular methods for solving semi-metric labeling include (i) move-making algorithms, which iteratively solve a minimum st-cut problem; and (ii) the linear programming (LP) relaxation based approach. In order to convert the fractional solution of the LP relaxation to an integer solution, several randomized rounding procedures have been developed in the literature. We consider a large class of parallel rounding procedures, and design move-making algorithms that closely mimic them. We prove that the multiplicative bound of a move-making algorithm exactly matches the approximation factor of the corresponding rounding procedure for any arbitrary distance function. Our analysis includes all known results for move-making algorithms as special cases.

关键词： linear programming relaxation move-making algorithms multiplicative bounds semi-metric labeling

来源：评论

学校读者我要写书评

暂无评论

Handelman's hierarchy for the maximum stable set problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2014年第3期60卷 393-423页

作者： Laurent, Monique Sun, Zhao CWI NL-1090 GB Amsterdam Netherlands Tilburg Univ NL-5000 LE Tilburg Netherlands

The maximum stable set problem is a well-known NP-hard problem in combinatorial optimization, which can be formulated as the maximization of a quadratic square-free polynomial over the (Boolean) hypercube. We investigate a hierarchy of linear programming relaxations for this problem, based on a result of Handelman showing that a positive polynomial over a polytope with non-empty interior can be represented as conic combination of products of the linear constraints defining the polytope. We relate the rank of Handelman's hierarchy with structural properties of graphs. In particular we show a relation to fractional clique covers which we use to upper bound the Handelman rank for perfect graphs and determine its exact value in the vertex-transitive case. Moreover we show two upper bounds on the Handelman rank in terms of the (fractional) stability number of the graph and compute the Handelman rank for several classes of graphs including odd cycles and wheels and their complements. We also point out links to several other linear and semidefinite programming hierarchies.

关键词： Polynomial optimization Combinatorial optimization Handelman hierarchy linear programming relaxation The maximum stable set problem

来源：评论

学校读者我要写书评

暂无评论

Bicriteria Multiresource Generalized Assignment Problem

引用

NAVAL RESEARCH LOGISTICS 2014年第8期61卷 621-636页

作者： Karsu, Ozlem Azizoglu, Meral Bilkent Univ Dept Ind Engn TR-06800 Ankara Turkey Middle E Tech Univ Dept Ind Engn TR-06531 Ankara Turkey

In this study, we consider a bicriteria multiresource generalized assignment problem. Our criteria are the total assignment load and maximum assignment load over all agents. We aim to generate all nondominated objective vectors and the corresponding efficient solutions. We propose several lower and upper bounds and use them in our optimization and heuristic algorithms. The computational results have shown the satisfactory behaviors of our approaches. (c) 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 621-636, 2014

关键词： generalized assignment problem linear programming relaxation branch and bound heuristics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：