2020
Akyildiz, O. D.; Crisan, Dan; Miguez, Joaquín
Parallel sequential Monte Carlo for stochastic gradient-free nonconvex optimization Artículo de revista
En: Statistics and Computing, 2020.
Enlaces | BibTeX | Etiquetas: Gradient-free optimization, Nonconvex optimization, Sampling, Sequential Monte Carlo, Stochastic optimization
@article{JMiguez20c,
title = {Parallel sequential Monte Carlo for stochastic gradient-free nonconvex optimization},
author = {O. D. Akyildiz and Dan Crisan and Joaqu\'{i}n Miguez},
doi = {https://doi.org/10.1007/s11222-020-09964-4},
year = {2020},
date = {2020-07-29},
journal = {Statistics and Computing},
keywords = {Gradient-free optimization, Nonconvex optimization, Sampling, Sequential Monte Carlo, Stochastic optimization},
pubstate = {published},
tppubtype = {article}
}
2014
Crisan, Dan; Miguez, Joaquin
Particle-Kernel Estimation of the Filter Density in State-Space Models Artículo de revista
En: Bernoulli, vol. (to appear, 2014.
Resumen | Enlaces | BibTeX | Etiquetas: density estimation, Markov systems., Models, Sequential Monte Carlo, state-space, stochastic filtering
@article{Crisan2014bb,
title = {Particle-Kernel Estimation of the Filter Density in State-Space Models},
author = {Dan Crisan and Joaquin Miguez},
url = {http://www.tsc.uc3m.es/~jmiguez/papers/P43_2014_Particle-Kernel Estimation of the Filter Density in State-Space Models.pdf
http://www.bernoulli-society.org/index.php/publications/bernoulli-journal/bernoulli-journal-papers},
year = {2014},
date = {2014-01-01},
journal = {Bernoulli},
volume = {(to appear},
abstract = {Sequential Monte Carlo (SMC) methods, also known as particle filters, are simulation-based recursive algorithms for the approximation of the a posteriori probability measures generated by state-space dynamical models. At any given time t, a SMC method produces a set of samples over the state space of the system of interest (often termed “particles”) that is used to build a discrete and random approximation of the posterior probability distribution of the state variables, conditional on a sequence of available observations. One potential application of the methodology is the estimation of the densities associated to the sequence of a posteriori distributions. While practitioners have rather freely applied such density approximations in the past, the issue has received less attention from a theoretical perspective. In this paper, we address the problem of constructing kernel-based estimates of the posterior probability density function and its derivatives, and obtain asymptotic convergence results for the estimation errors. In particular, we find convergence rates for the approximation errors that hold uniformly on the state space and guarantee that the error vanishes almost surely as the number of particles in the filter grows. Based on this uniform convergence result, we first show how to build continuous measures that converge almost surely (with known rate) toward the posterior measure and then address a few applications. The latter include maximum a posteriori estimation of the system state using the approximate derivatives of the posterior density and the approximation of functionals of it, e.g., Shannon’s entropy.},
keywords = {density estimation, Markov systems., Models, Sequential Monte Carlo, state-space, stochastic filtering},
pubstate = {published},
tppubtype = {article}
}
Sequential Monte Carlo (SMC) methods, also known as particle filters, are simulation-based recursive algorithms for the approximation of the a posteriori probability measures generated by state-space dynamical models. At any given time t, a SMC method produces a set of samples over the state space of the system of interest (often termed “particles”) that is used to build a discrete and random approximation of the posterior probability distribution of the state variables, conditional on a sequence of available observations. One potential application of the methodology is the estimation of the densities associated to the sequence of a posteriori distributions. While practitioners have rather freely applied such density approximations in the past, the issue has received less attention from a theoretical perspective. In this paper, we address the problem of constructing kernel-based estimates of the posterior probability density function and its derivatives, and obtain asymptotic convergence results for the estimation errors. In particular, we find convergence rates for the approximation errors that hold uniformly on the state space and guarantee that the error vanishes almost surely as the number of particles in the filter grows. Based on this uniform convergence result, we first show how to build continuous measures that converge almost surely (with known rate) toward the posterior measure and then address a few applications. The latter include maximum a posteriori estimation of the system state using the approximate derivatives of the posterior density and the approximation of functionals of it, e.g., Shannon’s entropy.
2012
Achutegui, Katrin; Miguez, Joaquin; Rodas, Javier; Escudero, Carlos J
A Multi-Model Sequential Monte Carlo Methodology for Indoor Tracking: Algorithms and Experimental Results Artículo de revista
En: Signal Processing, vol. 92, no 11, pp. 2594–2613, 2012.
Resumen | Enlaces | BibTeX | Etiquetas: Data fusion, Indoor positioning, Indoor tracking, Interacting multiple models, Sequential Monte Carlo, Switching observation models
@article{Achutegui2012,
title = {A Multi-Model Sequential Monte Carlo Methodology for Indoor Tracking: Algorithms and Experimental Results},
author = {Katrin Achutegui and Joaquin Miguez and Javier Rodas and Carlos J Escudero},
url = {http://www.tsc.uc3m.es/~jmiguez/papers/P32_2012_ Multi-Model Sequential Monte Carlo Methodology for Indoor Tracking- Algorithms and Experimental Results.pdf
http://www.sciencedirect.com/science/article/pii/S0165168412001077},
year = {2012},
date = {2012-01-01},
journal = {Signal Processing},
volume = {92},
number = {11},
pages = {2594--2613},
abstract = {In this paper we address the problem of indoor tracking using received signal strength (RSS) as a position-dependent data measurement. Since RSS is highly influenced by multipath propagation, it turns out very hard to adequately model the correspondence between the received power and the transmitter-to-receiver distance. Although various models have been proposed in the literature, they often require the use of very large collections of data in order to fit them and display great sensitivity to changes in the radio propagation environment. In this work we advocate the use of switching multiple models that account for different classes of target dynamics and propagation environments and propose a flexible probabilistic switching scheme. The resulting state-space structure is termed a generalized switching multiple model (GSMM) system. Within this framework, we investigate two types of models for the RSS data: polynomial models and classical logarithmic path-loss representation. The first model is more accurate however it demands an offline model fitting step. The second one is less precise but it can be fitted in an online procedure. We have designed two tracking algorithms built around a Rao-Blackwellized particle filter, tailored to the GSMM structure and assessed its performances both with synthetic and experimental measurements.},
keywords = {Data fusion, Indoor positioning, Indoor tracking, Interacting multiple models, Sequential Monte Carlo, Switching observation models},
pubstate = {published},
tppubtype = {article}
}
In this paper we address the problem of indoor tracking using received signal strength (RSS) as a position-dependent data measurement. Since RSS is highly influenced by multipath propagation, it turns out very hard to adequately model the correspondence between the received power and the transmitter-to-receiver distance. Although various models have been proposed in the literature, they often require the use of very large collections of data in order to fit them and display great sensitivity to changes in the radio propagation environment. In this work we advocate the use of switching multiple models that account for different classes of target dynamics and propagation environments and propose a flexible probabilistic switching scheme. The resulting state-space structure is termed a generalized switching multiple model (GSMM) system. Within this framework, we investigate two types of models for the RSS data: polynomial models and classical logarithmic path-loss representation. The first model is more accurate however it demands an offline model fitting step. The second one is less precise but it can be fitted in an online procedure. We have designed two tracking algorithms built around a Rao-Blackwellized particle filter, tailored to the GSMM structure and assessed its performances both with synthetic and experimental measurements.
2011
Maiz, Cristina S; Miguez, Joaquin
On the Optimization of Transportation Routes with Multiple Destinations in Random Networks Proceedings Article
En: 2011 IEEE Statistical Signal Processing Workshop (SSP), pp. 349–352, IEEE, Nice, 2011, ISBN: 978-1-4577-0569-4.
Resumen | Enlaces | BibTeX | Etiquetas: Approximation algorithms, communication networks, Estimation, graph theory, Histograms, intelligent transportation, Monte Carlo algorithm, Monte Carlo methods, multiple destinations, optimisation, Optimization, random networks, route optimization, routing, Sequential Monte Carlo, Signal processing algorithms, stochastic graph, Stochastic processes, telecommunication network routing, time-varying graph, transportation routes
@inproceedings{Maiz2011,
title = {On the Optimization of Transportation Routes with Multiple Destinations in Random Networks},
author = {Cristina S Maiz and Joaquin Miguez},
url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5967701},
isbn = {978-1-4577-0569-4},
year = {2011},
date = {2011-01-01},
booktitle = {2011 IEEE Statistical Signal Processing Workshop (SSP)},
pages = {349--352},
publisher = {IEEE},
address = {Nice},
abstract = {Various practical problems in transportation research and routing in communication networks can be reduced to the computation of the best path that traverses a certain graph and visits a set of D specified destination nodes. Simple versions of this problem have received attention in the literature. Optimal solutions exist for the cases in which (a) D \>; 1 and the graph is deterministic or (b) D = 1 and the graph is stochastic (and possibly time-dependent). Here, we address the general problem in which both D \>; 1 and the costs of the edges in the graph are stochastic and time-varying. We tackle this complex global optimization problem by first converting it into an equivalent estimation problem and then computing a numerical solution using a sequential Monte Carlo algorithm. The advantage of the proposed technique over some standard methods (devised for graphs with time-invariant statistics) is illustrated by way of computer simulations.},
keywords = {Approximation algorithms, communication networks, Estimation, graph theory, Histograms, intelligent transportation, Monte Carlo algorithm, Monte Carlo methods, multiple destinations, optimisation, Optimization, random networks, route optimization, routing, Sequential Monte Carlo, Signal processing algorithms, stochastic graph, Stochastic processes, telecommunication network routing, time-varying graph, transportation routes},
pubstate = {published},
tppubtype = {inproceedings}
}
Various practical problems in transportation research and routing in communication networks can be reduced to the computation of the best path that traverses a certain graph and visits a set of D specified destination nodes. Simple versions of this problem have received attention in the literature. Optimal solutions exist for the cases in which (a) D >; 1 and the graph is deterministic or (b) D = 1 and the graph is stochastic (and possibly time-dependent). Here, we address the general problem in which both D >; 1 and the costs of the edges in the graph are stochastic and time-varying. We tackle this complex global optimization problem by first converting it into an equivalent estimation problem and then computing a numerical solution using a sequential Monte Carlo algorithm. The advantage of the proposed technique over some standard methods (devised for graphs with time-invariant statistics) is illustrated by way of computer simulations.
Miguez, Joaquin; Crisan, Dan; Djuric, Petar M
On the Convergence of Two Sequential Monte Carlo Methods for Maximum a Posteriori Sequence Estimation and Stochastic Global Optimization Artículo de revista
En: Statistics and Computing, vol. 23, no 1, pp. 91–107, 2011, ISSN: 0960-3174.
Resumen | Enlaces | BibTeX | Etiquetas: Global optimization, MAP sequence estimation, Sequential Monte Carlo, State space models
@article{Miguez2011,
title = {On the Convergence of Two Sequential Monte Carlo Methods for Maximum a Posteriori Sequence Estimation and Stochastic Global Optimization},
author = {Joaquin Miguez and Dan Crisan and Petar M Djuric},
url = {http://www.researchgate.net/publication/225447686_On_the_convergence_of_two_sequential_Monte_Carlo_methods_for_maximum_a_posteriori_sequence_estimation_and_stochastic_global_optimization},
issn = {0960-3174},
year = {2011},
date = {2011-01-01},
journal = {Statistics and Computing},
volume = {23},
number = {1},
pages = {91--107},
abstract = {This paper addresses the problem of maximum a posteriori (MAP) sequence estimation in general state-space models. We consider two algorithms based on the sequential Monte Carlo (SMC) methodology (also known as particle filtering). We prove that they produce approximations of the MAP estimator and that they converge almost surely. We also derive a lower bound for the number of particles that are needed to achieve a given approximation accuracy. In the last part of the paper, we investigate the application of particle filtering and MAP estimation to the global optimization of a class of (possibly non-convex and possibly non-differentiable) cost functions. In particular, we show how to convert the cost-minimization problem into one of MAP sequence estimation for a state-space model that is “matched” to the cost of interest. We provide examples that illustrate the application of the methodology as well as numerical results.},
keywords = {Global optimization, MAP sequence estimation, Sequential Monte Carlo, State space models},
pubstate = {published},
tppubtype = {article}
}
This paper addresses the problem of maximum a posteriori (MAP) sequence estimation in general state-space models. We consider two algorithms based on the sequential Monte Carlo (SMC) methodology (also known as particle filtering). We prove that they produce approximations of the MAP estimator and that they converge almost surely. We also derive a lower bound for the number of particles that are needed to achieve a given approximation accuracy. In the last part of the paper, we investigate the application of particle filtering and MAP estimation to the global optimization of a class of (possibly non-convex and possibly non-differentiable) cost functions. In particular, we show how to convert the cost-minimization problem into one of MAP sequence estimation for a state-space model that is “matched” to the cost of interest. We provide examples that illustrate the application of the methodology as well as numerical results.
2010
Zoubir, A; Viberg, M; Yang, B; Miguez, Joaquin
Analysis of a Sequential Monte Carlo Method for Optimization in Dynamical Systems Artículo de revista
En: Signal Processing, vol. 90, no 5, pp. 1609–1622, 2010.
Resumen | Enlaces | BibTeX | Etiquetas: Dynamic optimization, Nonlinear dynamics, Nonlinear tracking, Sequential Monte Carlo, Stochastic optimization
@article{Zoubir2010,
title = {Analysis of a Sequential Monte Carlo Method for Optimization in Dynamical Systems},
author = {A Zoubir and M Viberg and B Yang and Joaquin Miguez},
url = {http://www.sciencedirect.com/science/article/pii/S0165168409004708},
year = {2010},
date = {2010-01-01},
journal = {Signal Processing},
volume = {90},
number = {5},
pages = {1609--1622},
abstract = {We investigate a recently proposed sequential Monte Carlo methodology for recursively tracking the minima of a cost function that evolves with time. These methods, subsequently referred to as sequential Monte Carlo minimization (SMCM) procedures, have an algorithmic structure similar to particle filters: they involve the generation of random paths in the space of the signal of interest (SoI), the stochastic selection of the fittest paths and the ranking of the survivors according to their cost. In this paper, we propose an extension of the original SMCM methodology (that makes it applicable to a broader class of cost functions) and introduce an asymptotic-convergence analysis. Our analytical results are based on simple induction arguments and show how the SoI-estimates computed by a SMCM algorithm converge, in probability, to a sequence of minimizers of the cost function. We illustrate these results by means of two computer simulation examples.},
keywords = {Dynamic optimization, Nonlinear dynamics, Nonlinear tracking, Sequential Monte Carlo, Stochastic optimization},
pubstate = {published},
tppubtype = {article}
}
We investigate a recently proposed sequential Monte Carlo methodology for recursively tracking the minima of a cost function that evolves with time. These methods, subsequently referred to as sequential Monte Carlo minimization (SMCM) procedures, have an algorithmic structure similar to particle filters: they involve the generation of random paths in the space of the signal of interest (SoI), the stochastic selection of the fittest paths and the ranking of the survivors according to their cost. In this paper, we propose an extension of the original SMCM methodology (that makes it applicable to a broader class of cost functions) and introduce an asymptotic-convergence analysis. Our analytical results are based on simple induction arguments and show how the SoI-estimates computed by a SMCM algorithm converge, in probability, to a sequence of minimizers of the cost function. We illustrate these results by means of two computer simulation examples.