Simulação de modelos Markovianos utilizando a técnica Bootstrap
Resumo
Simulação é uma alternativa interessante para a solução de modelos Markovianos. No entanto, comparando-a com métodos analíticos e numéricos percebe-se uma falta de confiança na precisão dos resultados pela própria natureza da simulação que escolhe amostras de funcionamento através da geração de números pseudo-aleatórios. Este artigo propõe uma nova forma de simular modelos Markovianos pelo uso de uma técnica estatística baseada em Bootstrap para reduzir os efeitos de escolha de amostras. A eficácia da técnica proposta, chamada Simulação Bootstrap, é comparada aos resultados exatos obtidos pela solução numérica de um conjunto de exemplos descritos pelo formalismo de Redes de Autômatos Estocásticos.
Referências
Aczel, A. D. (1998). Probability 1: The Book That Proves There is Life in Outer Space. Harvest Books, Orlando, Florida.
Arnoldi, W. E. (1951). The principle of minimized iterations in the solution of the matrix eigenvalue problem. Quarterly of Applied Mathematics, 9:17–29.
Bauer, E. and Kohavi, R. (1999). An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants. Machine Learning, 36(1-2):105–139.
Bertolini, C., Brenner, L., Fernandes, P., Sales, A., and Zorzo, A. F. (2004). Structured StochasticModeling of Fault-Tolerant Systems. In 12th IEEE/ACM Internacional Symposium on Modelling, Analysis and Simulation on Computer and Telecommunication Systems (MASCOTS’04), pages 139–146, Volendam, The Netherlands. IEEE Press.
Brenner, L., Fernandes, P., Fourneau, J. M., and Plateau, B. (2009). Modelling Grid5000 point availability with SAN. Elect. Notes in Theoret. Computer Science (ENTCS), 232:165–178.
Brenner, L., Fernandes, P., Plateau, B., and Sbeity, I. (2007). PEPS2007 - Stochastic Automata Networks Software Tool. In Fourth Internat. Conf. on the Quantitative Evaluation of Systems (QEST’07), pages 163–164, Edinburgh, UK. IEEE Press.
Donatelli, S. (1993). Superposed stochastic automata: a class of stochastic Petri nets with parallel solution and distributed state space. Performance Evaluation, 18(1):21–36.
Dotti, F. L., Fernandes, P., Sales, A., and Santos, O. M. (2005). Modular Analytical Performance Models for Ad Hoc Wireless Networks. In 3rd International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt’05), pages 164–173, Trentino, Italy. IEEE Computer Society.
Efron, B. (1979). Bootstrap Methods: Another Look at the Jackknife. The Annals of Statistics, 7(1):1–26.
Fernandes, P., Plateau, B., and Stewart, W. J. (1998). Efficient descriptor-vector multiplication in Stochastic Automata Networks. Journal of the ACM, 45(3):381–414.
Häggström, O. (2002). Finite Markov Chains and Algorithmic Applications. Cambridge University Press. Based on lecture notes.
Hillston, J. (1996). A compositional approach to performance modelling. Cambridge University Press, New York, USA.
Manly, B. F. J. (1997). Randomization, Bootstrap and Monte Carlo Methods in Biology. Chapman & Hall/CRC, second edition.
Plateau, B. (1985). On the stochastic structure of parallelism and synchronization models for distributed algorithms. In Proc. of the 1985 ACM SIGMETRICS Conf. on Measurements and Modeling of Comp. Systems, pages 147–154, Austin, Texas. ACM Press.
Propp, J. G. and Wilson, D. B. (1996). Exact Sampling with Coupled Markov Chains and Applications to Statistical Mechanics. Random Structures and Algorithms, 9(1–2):223–252.
Ross, S. M. (2002). Simulation. Academic Press, Inc., Orlando, FL, USA.
Saad, Y. and Schultz, M. H. (1986). GMRES: A Generalized Minimal RESidual Algorithm for Solving Nonsymmetric Linear Systems. SIAM Journal on Scientific and Statistical Computing, 7(3):856–869.
Sales, A. and Plateau, B. (2009). Reachable state space generation for structured models which use functional transitions. In Proc. of the 6th Internat. Conf. on the Quantitative Evaluation of Systems (QEST’09), pages 269–278, Budapest, Hungary. IEEE Press.
Sayre, K. (1999). Improved techniques for software testing based on Markov chain usage models. PhD thesis, University of Tennessee, Knoxville, USA.
Shannon, R. E. (1998). Introduction to the art and science of simulation. In Proceedings of the 30th Conference on Winter Simulation (WSC’98), pages 7–14, Los Alamitos, CA, USA. IEEE Computer Society Press.
Stewart, W. J. (2009). Probability, Markov Chains, Queues, and Simulation. Princeton University Press, Princeton, NJ, USA.
Taschetto, D. (2010). Precisão de Simulações para Solução de Modelos Estocásticos. Master’s thesis, PUCRS-FACIN-PPGCC, Porto Alegre.
Arnoldi, W. E. (1951). The principle of minimized iterations in the solution of the matrix eigenvalue problem. Quarterly of Applied Mathematics, 9:17–29.
Bauer, E. and Kohavi, R. (1999). An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants. Machine Learning, 36(1-2):105–139.
Bertolini, C., Brenner, L., Fernandes, P., Sales, A., and Zorzo, A. F. (2004). Structured StochasticModeling of Fault-Tolerant Systems. In 12th IEEE/ACM Internacional Symposium on Modelling, Analysis and Simulation on Computer and Telecommunication Systems (MASCOTS’04), pages 139–146, Volendam, The Netherlands. IEEE Press.
Brenner, L., Fernandes, P., Fourneau, J. M., and Plateau, B. (2009). Modelling Grid5000 point availability with SAN. Elect. Notes in Theoret. Computer Science (ENTCS), 232:165–178.
Brenner, L., Fernandes, P., Plateau, B., and Sbeity, I. (2007). PEPS2007 - Stochastic Automata Networks Software Tool. In Fourth Internat. Conf. on the Quantitative Evaluation of Systems (QEST’07), pages 163–164, Edinburgh, UK. IEEE Press.
Donatelli, S. (1993). Superposed stochastic automata: a class of stochastic Petri nets with parallel solution and distributed state space. Performance Evaluation, 18(1):21–36.
Dotti, F. L., Fernandes, P., Sales, A., and Santos, O. M. (2005). Modular Analytical Performance Models for Ad Hoc Wireless Networks. In 3rd International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt’05), pages 164–173, Trentino, Italy. IEEE Computer Society.
Efron, B. (1979). Bootstrap Methods: Another Look at the Jackknife. The Annals of Statistics, 7(1):1–26.
Fernandes, P., Plateau, B., and Stewart, W. J. (1998). Efficient descriptor-vector multiplication in Stochastic Automata Networks. Journal of the ACM, 45(3):381–414.
Häggström, O. (2002). Finite Markov Chains and Algorithmic Applications. Cambridge University Press. Based on lecture notes.
Hillston, J. (1996). A compositional approach to performance modelling. Cambridge University Press, New York, USA.
Manly, B. F. J. (1997). Randomization, Bootstrap and Monte Carlo Methods in Biology. Chapman & Hall/CRC, second edition.
Plateau, B. (1985). On the stochastic structure of parallelism and synchronization models for distributed algorithms. In Proc. of the 1985 ACM SIGMETRICS Conf. on Measurements and Modeling of Comp. Systems, pages 147–154, Austin, Texas. ACM Press.
Propp, J. G. and Wilson, D. B. (1996). Exact Sampling with Coupled Markov Chains and Applications to Statistical Mechanics. Random Structures and Algorithms, 9(1–2):223–252.
Ross, S. M. (2002). Simulation. Academic Press, Inc., Orlando, FL, USA.
Saad, Y. and Schultz, M. H. (1986). GMRES: A Generalized Minimal RESidual Algorithm for Solving Nonsymmetric Linear Systems. SIAM Journal on Scientific and Statistical Computing, 7(3):856–869.
Sales, A. and Plateau, B. (2009). Reachable state space generation for structured models which use functional transitions. In Proc. of the 6th Internat. Conf. on the Quantitative Evaluation of Systems (QEST’09), pages 269–278, Budapest, Hungary. IEEE Press.
Sayre, K. (1999). Improved techniques for software testing based on Markov chain usage models. PhD thesis, University of Tennessee, Knoxville, USA.
Shannon, R. E. (1998). Introduction to the art and science of simulation. In Proceedings of the 30th Conference on Winter Simulation (WSC’98), pages 7–14, Los Alamitos, CA, USA. IEEE Computer Society Press.
Stewart, W. J. (2009). Probability, Markov Chains, Queues, and Simulation. Princeton University Press, Princeton, NJ, USA.
Taschetto, D. (2010). Precisão de Simulações para Solução de Modelos Estocásticos. Master’s thesis, PUCRS-FACIN-PPGCC, Porto Alegre.
Publicado
20/07/2010
Como Citar
TASCHETTO, Dione; FERNANDES, Paulo; WEBBER, Thais; SALES, Afonso.
Simulação de modelos Markovianos utilizando a técnica Bootstrap. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 9. , 2010, Belo Horizonte/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2010
.
p. 1915-1928.
ISSN 2595-6167.
