Fast Sequential Monte Carlo Methods for Counting and Optimization E-Book

Reuven Y. Rubinstein

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley Series in Probability and Statistics
• Sprache: Englisch

Seitenzahl: 259

Veröffentlichungsjahr: 2013

Beschreibung

A comprehensive account of the theory and application of Monte Carlo methods Based on years of research in efficient Monte Carlo methods for estimation of rare-event probabilities, counting problems, and combinatorial optimization, Fast Sequential Monte Carlo Methods for Counting and Optimization is a complete illustration of fast sequential Monte Carlo techniques. The book provides an accessible overview of current work in the field of Monte Carlo methods, specifically sequential Monte Carlo techniques, for solving abstract counting and optimization problems. Written by authorities in the field, the book places emphasis on cross-entropy, minimum cross-entropy, splitting, and stochastic enumeration. Focusing on the concepts and application of Monte Carlo techniques, Fast Sequential Monte Carlo Methods for Counting and Optimization includes: * Detailed algorithms needed to practice solving real-world problems * Numerous examples with Monte Carlo method produced solutions within the 1-2% limit of relative error * A new generic sequential importance sampling algorithm alongside extensive numerical results * An appendix focused on review material to provide additional background information Fast Sequential Monte Carlo Methods for Counting and Optimization is an excellent resource for engineers, computer scientists, mathematicians, statisticians, and readers interested in efficient simulation techniques. The book is also useful for upper-undergraduate and graduate-level courses on Monte Carlo methods.

Leseprobe

Table of Contents

Series

Copyright

Dedication

Chapter 1: Introduction to Monte Carlo Methods

Chapter 2: Cross-Entropy Method

2.1 Introduction

2.2 Estimation of Rare-Event Probabilities

2.3 Cross-Entropy Method forOptimization

2.4 Continuous Optimization

2.5 Noisy Optimization

Chapter 3: Minimum Cross-Entropy Method

3.1 Introduction

3.2 Classic MinxEnt Method

3.3 Rare Events and MinxEnt

3.4 Indicator MinxEnt Method

3.5 IME Method for Combinatorial Optimization

Chapter 4: Splitting Method for Counting and Optimization

4.1 Background

4.2 Quick Glance at the Splitting Method

4.3 Splitting Algorithm with Fixed Levels

4.4 Adaptive Splitting Algorithm

4.5 Sampling Uniformly on Discrete Regions

4.6 Splitting Algorithm for Combinatorial Optimization

4.7 Enhanced Splitting Method for Counting

4.8 Application of Splitting to Reliability Models

4.9 Numerical Results with the Splitting Algorithms

4.10 Appendix: Gibbs Sampler

Chapter 5: Stochastic Enumeration Method

5.1 Introduction

5.2 OSLA Method and Its Extensions

5.3 SE Method

5.4 Applications of SE

5.5 Numerical Results

Appendix A: Additional Topics

A.1 Combinatorial Problems

A.2 Information

A.3 Efficiency of Estimators

Bibliography

Abbreviations and Acronyms

List of Symbols

Index

Series

Cover Design: Michael Rutkowski

Cover Image: © Eastnine Inc./Getty Images

Copyright © 2014 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.

Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Rubinstein, Reuven Y.

Fast sequential Monte Carlo methods for counting and optimization/Reuven Rubinstein, Faculty of Industrial Engineering and Management, Technion, Israel Institute of Technology, Haifa, Israel, Ad Ridder, Department of Econometrics and Operations Research, Vrije University, Amsterdam, Netherlands, Radislav Vaisman, Faculty of Industrial Engineering and Management, Technion, Israel Institute of Technology, Haifa, Israel.

pages cm

Includes bibliographical references and index.

ISBN 978-1-118-61226-2 (cloth)–Monte Carlo method. 2. Mathematical optimization. I. Ridder, Ad, 1955- II. Vaisman,Radislav. III. Title.

T57.64.R83 2013

518′.282–dc23

2013011113

In Memoriam

Reuven Y. Rubinstein (1938–2012):

Reuven Rubinstein died in December 2012, when this book was at its final stage of drafting. Reuven was an inspiration to many simulation researchers and practitioners, and was always a stimulating colleague to work with. His co-authors would like to dedicate this book to him, and to show appreciation for all the contributions he made up until the last moments of his life.

Reuven was born in Kaunas, Lithuania, in 1938. His family was exiled to the Syberian Gulag in 1941, but he managed to earn a Master's degree from Kaunas Polytechnic Institute in 1960. In 1969, Reuven obtained his PhD degree in Operational Research from Riga Polytechnical Institute. In 1973, Reuven and his family immigrated to Israel and he immediately joined the Faculty of Industrial Engineering and Management at Technion, Israel Institute of Technology. In 1978, Reuven obtained the Associate Professor rank and in 1992 he was awarded a Full Professor at Technion.

Reuven published eight books and more than one-hundred scientific papers. During his sabbatical years he was a visiting professor at many universities and research centers around the world, among them University of Illinois at Urbana-Champaign, Harvard University, Stanford University, IBM Research Center, Bell Laboratories, NJ, NEC, and the Institute of Statistical Mathematics, Japan. He was a member of several societies, including the Operations Research Society of Israel (ORSIS) and the Institute for Operations Research and Management Science (INFORMS).

A highly respected researcher in simulation algorithms, Reuven is best known for founding the score function method in simulation and the cross-entropy method for combinatorial optimization, which generated an entire new scientific community. His research was recognized with several prestigious awards, including the 2010 Lifetime Professional Achievement Award from INFORMS Simulation Society, and the 2011 Lifetime Achievement Award from ORSIS.

He will be remembered with respect and affection by everyone who loved him for his friendliness, his creative talents, and his animated spirit.

Preface

This book presents an introduction to fast sequential Monte Carlo (SMC) methods for counting and optimization. It is based mainly on the research work of Reuven Rubinstein and his collaborators, performed over the last ten years, on efficient Monte Carlo methods for estimation of rare-event probabilities, counting problems, and combinatorial optimization. Particular emphasis is placed on cross-entropy, minimum cross-entropy, splitting, and stochastic enumeration methods.

Our aim was to write a book on the SMC methods for a broad audience of engineers, computer scientists, mathematicians, statisticians, and, in general, anyone, theorist or practitioner, interested in efficient simulation and, in particular, efficient combinatorial optimization and counting. Our intention was to show how the SMC methods work in applications, while at the same time accentuating the unifying and novel mathematical ideas behind the SMC methods. We hope that the book stimulates further research at a postgraduate level.

The emphasis in this book is on concepts rather than on mathematical completeness. We assume that the reader has some basic mathematical background, such as a basic undergraduate course in probability and statistics. We have deliberately tried to avoid the formal “definition—lemma—theorem—proof” style of many mathematics books. Instead, we embed most definitions in the text and introduce and explain various concepts via examples and experiments.

Most of the combinatorial optimization and counting case studies in this book are benchmark problems taken from the World Wide Web. In all examples tested so far, the relative error of SMC was within the limits of 1–2% of the best-known solution. In some instances, SMC produced even more accurate solutions. The book covers the following topics:

Chapter 1 introduces the concepts of Monte Carlo methods for estimation and randomized algorithms to solve deterministic optimization and counting problems.

Chapter 2 deals with the cross-entropy method, which is able to approximate quite accurately the solutions to difficult estimation and optimization problems such as integer programming, continuous multiextremal optimization, noisy optimization problems such as optimal buffer allocation, optimal policy search, clustering, signal detection, DNA sequence alignment, network reliability optimization, and neural and reinforcement learning. Recently, the cross-entropy method has been used as a main engine for playing games such as Tetris, Go, and backgammon. For more references, see http://www.cemethod.org.

Chapter 3 presents the minimum cross-entropy method, also known as the MinxEnt method. Similar to the cross-entropy method, MinxEnt is able to deliver accurate solutions for difficult estimation and optimization problems. The main idea of MinxEnt is to associate with each original optimization problem an auxiliary single-constrained convex optimization program in terms of probability density functions. The beauty is that this auxiliary program has a closed-form solution, which becomes the optimal zero-variance solution, provided the “temperature” parameter is set to minus infinity. In addition, the associated probability density function based on the product of marginals obtained from the joint optimal zero variance probability density function coincides with the parametric probability density function of the cross-entropy method. Thus, we obtain a strong connection of the cross-entropy method with MinxEnt, providing solid mathematical foundations.

Chapter 4 introduces the splitting method for counting, combinatorial optimization, and rare-event estimation. Similar to the classic randomized algorithms, splitting algorithms use a sequential sampling plan to decompose a “difficult” problem into a sequence of “easy” ones. It presents, in fact, a combination of Markov chain Monte Carlo, like the Gibbs sampler, with a specially designed cloning mechanism. The latter runs in parallel multiple Markov chains by making sure that all of them run in steady-state at each iteration. This chapter contains the following elements:

It combines splitting with the classic capture–recapture method in order to obtain low-variance estimators for counting in complex sets, such as counting the number of satisfiability assignments.

It shows that the splitting algorithm can be efficiently used for estimating the reliability of complex static networks.

It demonstrates numerically that the splitting algorithm can be efficiently used for generating uniform samples on discrete sets. We provide valid statistical tests supporting the uniformity of generated samples.

It presents supportive numerical results, while solving quite general counting problems, such as counting the number of true assignments in a satisfiability problem, counting the number of feasible colorings in a graph, calculating the permanent, Hamiltonian cycles, 0-1 tables, and volume of a polytope, as well as solving integer and combinatorial optimization, like the traveling salesman, knapsack, and set-covering problems.

Chapter 5 presents a new generic sequential importance sampling algorithm, called stochastic enumeration for counting #P-complete problems, such as the number of satisfiability assignments, number of trajectories in a general network, and number of perfect matching in a graph. For this purpose, it employs a decision-making algorithm, also called an oracle. The crucial differences between stochastic enumeration and the other generic methods that we present in this book (i.e., cross-entropy, MinxEnt, and splitting) are:

The former is sequential in nature (it is based on sequential importance sampling), whereas the latter are not (they sample simultaneously in the entire -dimensional space).

The former is based on decision-making oracles to solve #P-complete problems, whereas the latter are not. As a result, it is typically faster than the others.

We also present extensive numerical results with stochastic enumeration and show that it outperforms some of its well-known counterparts, in particular, the splitting method. Our explanation for that relies again on the fact that it uses sequential sampling and an oracle.

Appendix A provides auxiliary material. In particular, it covers some basic combinatorial and counting problems and supplies a background to the cross-entropy method. Finally, the efficiency of Monte Carlo estimators is discussed.

We thank all colleagues and friends who provided us with comments, corrections, and suggestions for improvements. We are grateful to the many undergraduate and graduate students at the Technion who helped make this book possible, and whose valuable ideas and experiments where extremely encouraging and motivating. We are especially indebted to Dirk Kroese, who worked through the entire manuscript and provided us a thorough review and feedback.

Ad Ridder

Radislav Vaisman

Amsterdam and Haifa

September 2013

Chapter 1

Introduction to Monte Carlo Methods

Monte Carlo methods present a class of computational algorithms that rely on repeated random sampling to approximate some unknown quantities. They are best suited for calculation using a computer program, and they are typically used when the exact results with a deterministic algorithm are not available.

The Monte Carlo method was developed in the 1940s by John von Neumann, Stanislaw Ulam, and Nicholas Metropolis while they were working on the Manhattan Project at the Los Alamos National Laboratory. It was named after the Monte Carlo Casino, a famous casino where Ulam's uncle often gambled away his money.

We mainly deal in this book with two well-known Monte Carlo methods, called importance sampling and splitting, and in particular with their applications to combinatorial optimization, counting, and estimation of probabilities of rare events.

Importance sampling is a well-known variance reduction technique in stochastic simulation studies. The idea behind importance sampling is that certain values of the input random variables have a greater impact on the output parameters than others. If these “important” values are sampled more frequently, the variance of the output estimator can be reduced. However, such direct use of importance sampling distributions will result in a biased estimator. To eliminate the bias, the simulation outputs must be modified (weighted) by using a likelihood ratio factor, also called the Radon Nikodym derivative [108]. The fundamental issue in implementing importance sampling is the choice of the importance sampling distribution.

In the case of counting problems, it is well known that a straightforward application of importance sampling typically yields poor approximations of the quantity of interest. In particular, Gogate and Dechter [56] [57] show that poorly chosen importance sampling in graphical models such as satisfiability models generates many useless zero-weight samples, which are often rejected, yielding an inefficient sampling process. To address this problem, which is called the problem of losing trajectories, these authors propose a clever sample search method, which is integrated into the importance sampling framework.

With regard to probability problems, a wide range of applications of importance sampling have been reported successfully in the literature over the last decades.Siegmund [115] was the first to argue that, using an exponential change of measure, asymptotically efficient importance sampling schemes can be built for estimating gambler's ruin probabilities. His analysis is related to the theory of large deviations, which has since become an important tool for the design of efficient Monte Carlo experiments. Importance sampling is now a subject of almost any standard book on Monte Carlo simulation (see, for example, [3] [108]). We shall use importance sampling widely in this book, especially in connection to rare-event estimation.

The splitting method dates back to Kahn and Harris [62] and Rosenbluth and Rosenbluth [97]. The main idea is to partition the state-space of a system into a series of nested subsets and to consider the rare event as the intersection of a nested sequence of events. When a given subset is entered by a sample trajectory during the simulation, numerous random retrials are generated, with the initial state for each retrial being the state of the system at the entry point. By doing so, the system trajectory is split into a number of new subtrajectories, hence the name “splitting”. Since then, hundreds of papers have been written on this topic, both from a theoretical and a practical point of view. Applications of the splitting method arise in particle transmission (Kahn and Harris [62]), queueing systems (Garvels [48], Garvels and Kroese [49], Garvels et al. [50]), and reliability (L'Ecuyer et al. [76]). The method has been given new impetus by the RESTART (Repetitive Simulation Trials After Reaching Thresholds) method in the sequence of papers by Villén-Altimirano and Villén-Altimirano [122–124]. A fundamental theory of the splitting method was developed by Melas [85], Glasserman et al. [54] [55], and Dean and Dupuis [38] [39]. Recent developments include the adaptive selection of the splitting levels in Cérou and Guyader [24], the use of splitting in reliability networks [73] [109], quasi-Monte Carlo estimators in L'Ecuyer et al. [77], and the connection between splitting for Markovian processes and interacting particle methods based on the Feynman-Kac model in Del Moral [89].

Let us introduce the notion of a randomized algorithm. A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic to solve a deterministic problem such as a combinatorial optimization problem. As a result, the algorithm's output will be a random variable representing either the running time, its output, or both. In general, introducing randomness may result in an algorithm that is far simpler, more elegant, and sometimes even more efficient than the deterministic counterpart.

Example 1.1 Checking Matrix Multiplication

Suppose we are given three matrices , and and we want to check whether .

A trivial deterministic algorithm would be to run a standard multiplication algorithm and compare each entry of with . Simple matrix multiplication requires operations. A more sophisticated algorithm [88] takes only operations. Using randomization, however, we need only operations, with an extremely small probability of error [88].

The randomized procedure is as follows:

Pick a random -dimensional vector .

Multiply both sides of by , that is, obtain and .

If , then declare , otherwise, .

This algorithm runs in operations because matrix multiplication is associative, so can be computed as , thus requiring only three matrix-vector multiplications for the algorithm.

For more examples and foundations on randomized algorithms, see the monographs [88] [90].

We shall consider not only randomized algorithms but also random structures. The latter comprises random graphs (such as Erdös-Rényi graphs), random Boolean formulas, and so on. Random structures are of interest both as a means of understanding the behavior of algorithms on typical inputs and as a mathematical framework in which one can investigate various probabilistic techniques to analyze randomized algorithms.

This book deals with Monte Carlo methods and their associated randomized algorithms for solving combinatorial optimization and counting problems. In particular, we consider combinatorial problems that can be modeled by integer linear constraints. To clarify, denote by the set of feasible solutions of a combinatorial problem, which is assumed to be a subset of an -dimensional integer vector space and which is given by the following linear constraints:

1.1

Here, is a given matrix and is a given -dimensional vector. Most often we require the variables to be nonnegative integers and, in particular, binary integers.

In this book, we describe in detail various problems, algorithms, and mathematical aspects that are associated with (1.1) and its relation to decision making, counting, and optimization. Below is a short list of problems associated with (1.1):

1.Decision making: Is nonempty?

2.Optimization: Solve for a given objective (performance) function .

3.Counting: Calculate the cardinality of .

It turns out that, typically, it is hard to solve any of the above three problems and, in particular, the counting one, which is the hardest one. However, we would like to point out that there are problems for which decision making is easy (polynomial time) but counting is hard [90]. As an example, finding a feasible path (and also the shortest path) between two fixed nodes in a network is easy, whereas counting the total number of paths between the two nodes is difficult. Some other examples of hard counting and easy decision-making problems include:

How many different variable assignments will satisfy a given satisfiability formula in disjunctive normal form?

How many different variable assignments will satisfy a given 2-satisfiability formula (constraints on pairs of variables)?

How many perfect matchings are there for a given bipartite graph?

In Chapter 5, we follow the saying “counting is hard, but decision making is easy” and employ relevant decision-making algorithms, also called oracles, to derive fast Monte Carlo algorithms for counting.

Below is a detailed list of interesting hard counting problems.

The Hamiltonian cycle problem.

How many Hamiltonian cycles does a graph have? That is, how many tours contains a graph in which every node is visited exactly once (except for the beginning/end node)?

The permanent problem.

Calculate the permanent of a matrix , or equivalently, the number of perfect matchings in a bipartite balanced graph with as its biadjacency matrix.

The self-avoiding walk problem.

How many self-avoiding random walks of length exist, when we are allowed to move at each grid point in any neighboring direction with equal probability?

The connectivity problem.

Given two different nodes in a directed or undirected graph, say and , how many paths exist from to that do not traverse the same edge more than once?

The satisfiability problem.

Let be a collection of all sets of Boolean variables . Thus, has cardinality . Let be a set of Boolean disjunctive clauses. Examples of such clauses are , , etc. How many (if any) satisfying truth assignments for exist, that is, how many ways are there to set the variables either true or false so that all clauses are true?

The

-

coloring problem.

Given distinct colors, in how many different ways can one color the nodes (or the edges) of a graph, so that each two adjacent nodes (edges, respectively) in the graph have different colors?

The spanning tree problem.

How many unlabeled spanning trees has a graph ? Note that this counting problem is easy for labeled graphs.

The isomorphism problem.

How many isomorphisms exist between two given graphs and ? In other words, in an isomorphism problem one needs to find all mappings between the nodes of and such that is an edge of if and only if is an edge of .

The clique problem.

How many cliques of fixed size exist in a graph ? Recall that a clique is a complete subgraph of .

The decision versions of these problems are all examples of NP-complete problems. Clearly, counting all feasible solutions, denoted by #P, is an even harder problem.

Generally, the complexity class #P consists of the counting problems associated with the decision problems in NP. Completeness is defined similarly to the decision problems: a problem is #P-complete if it is in #P, and if every #P problem can be reduced to it in polynomial counting reduction. Hence, the counting problems that we presented above are all #P-complete. For more details we refer the reader to the classic monograph by Papadimitrou and Stieglitz [92].

Chapter 2

Cross-Entropy Method

2.1 Introduction

The cross-entropy (CE) method is a powerful technique for solving difficult estimation and optimization problems, based on Kullback-Leibler (or cross-entropy) minimization [15]. It was pioneered by Rubinstein in 1999 [100] as an adaptive importance sampling procedure for the estimation of rare-event probabilities. Subsequent work in [101] [102] has shown that many optimization problems can be translated into a rare-event estimation problem. As a result, the CE method can be utilized as randomized algorithms for optimization. The gist of the idea is that the probability of locating an optimal or near-optimal solution using naive random search is a rare event probability. The cross-entropy method can be used to gradually change the sampling distribution of the random search so that the rare event is more likely to occur. For this purpose, using the cross-entropy or Kullback-Leibler divergence as a measure of closeness between two sampling distributions, the method estimates a sequence of parametric sampling distributions that converges to a distribution with probability mass concentrated in a region of near-optimal solutions.

To date, the CE method has been successfully applied to optimization and estimation problems. The former includes mixed-integer nonlinear programming [69], continuous optimal control problems [111] [112], continuous multiextremal optimization [71], multidimensional independent component analysis [116], optimal policy search [19], clustering [11] [17, 72], signal detection [80], DNA sequence alignment [67] [93], fiber design [27], noisy optimization problems such as optimal buffer allocation [2], resource allocation in stochastic systems [31], network reliability optimization [70], vehicle routing optimization with stochastic demands [29], power system combinatorial optimization problems [45], and neural and reinforcement learning [81] [86, 118] [128]. CE has even been used as a main engine for playing games such as Tetris, Go, and backgammon [26].