Top

Published in:

2022 | OriginalPaper | Chapter

Moment-Based Invariants for Probabilistic Loops with Non-polynomial Assignments

Authors : Andrey Kofnov, Marcel Moosbrugger, Miroslav Stankovič, Ezio Bartocci, Efstathia Bura

Published in: Quantitative Evaluation of Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present a method to automatically approximate moment-based invariants of probabilistic programs with non-polynomial updates of continuous state variables to accommodate more complex dynamics. Our approach leverages polynomial chaos expansion to approximate non-linear functional updates as sums of orthogonal polynomials. We exploit this result to automatically estimate state-variable moments of all orders in Prob-solvable loops with non-polynomial updates. We showcase the accuracy of our estimation approach in several examples, such as the turning vehicle model and the Taylor rule in monetary policy.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter Distribution Estimation for Probabilistic Loops

Available only for authorised users

\(\varOmega \) is dropped from the notation as the sample space is not important in our formulation.

Conditions that ascertain this are given in Theorem 3.4 of [8].

Generalized PCE typically entails using orthogonal basis polynomials specific to the distribution of the basic variables, according to the Askey scheme of [32, 33]. We opted for the most general procedure that can be used for any basic variable distribution.

We provide further details about PCE computation in Appendix 2 and 3.

It was proposed by the American economist John B. Taylor as a technique to stabilize economic activity by setting an interest rate [29].

https://data.worldbank.org/indicator/NY.GDP.MKTP.KD.ZG?locations=US.

Atkeson, A., Ohanian, L.E.: Are Phillips curves useful for forecasting inflation? Q. Rev. 25(Win), 2–11 (2001). https://ideas.repec.org/a/fip/fedmqr/y2001iwinp2-11nv.25no.1.html

Bartocci, E., Kovács, L., Stankovič, M.: Automatic generation of moment-based invariants for prob-solvable loops. In: Chen, Y.-F., Cheng, C.-H., Esparza, J. (eds.) ATVA 2019. LNCS, vol. 11781, pp. 255–276. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-31784-3_15CrossRefMATH

Bartocci, E., Kovács, L., Stankovič, M.: Mora - automatic generation of moment-based invariants. In: TACAS 2020. LNCS, vol. 12078, pp. 492–498. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45190-5_28CrossRef

Bouissou, O., Goubault, E., Putot, S., Chakarov, A., Sankaranarayanan, S.: Uncertainty propagation using probabilistic affine forms and concentration of measure inequalities. In: Chechik, M., Raskin, J.-F. (eds.) TACAS 2016. LNCS, vol. 9636, pp. 225–243. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49674-9_13CrossRefMATH

Chen, X., Ábrahám, E., Sankaranarayanan, S.: Taylor model flowpipe construction for non-linear hybrid systems. In: Proceedings of RTSS 2012: the 33rd IEEE Real-Time Systems Symposium, pp. 183–192. IEEE Computer Society (2012). https://doi.org/10.1109/RTSS.2012.70

Chorin, A.J.: Gaussian fields and random flow. J. Fluid Mech. 63(1), 21–32 (1974). https://doi.org/10.1017/S0022112074000991MathSciNetCrossRefMATH

Denamiel, C., Huan, X., Šepić, J., Vilibić, I.: Uncertainty propagation using polynomial chaos expansions for extreme sea level hazard assessment: the case of the eastern adriatic meteotsunamis. J. Phys. Oceanogr. 50(4), 1005–1021 (2020). https://doi.org/10.1175/JPO-D-19-0147.1CrossRef

Ernst, O.G., Mugler, A., Starkloff, H.J., Ullmann, E.: On the convergence of generalized polynomial chaos expansions. ESAIM: M2AN 46(2), 317–339 (2012). https://doi.org/10.1051/m2an/2011045

Foo, J., Yosibash, Z., Karniadakis, G.E.: Stochastic simulation of riser-sections with uncertain measured pressure loads and/or uncertain material properties. Comput. Methods Appl. Mech. Eng. 196, 4250–4271 (2007). https://doi.org/10.1016/j.cma.2007.04.005CrossRefMATH

10.

Formaggia, L., et al.: Global sensitivity analysis through polynomial chaos expansion of a basin-scale geochemical compaction model. Comput. Geosci. 17, 25–42 (2013). https://doi.org/10.1007/s10596-012-9311-5MathSciNetCrossRefMATH

11.

Ghanem, R., Dham, S.: Stochastic finite element analysis for multiphase flow in heterogeneous porous media. Transp. Porous Medias 32, 239–262 (1998). https://doi.org/10.1023/A:1006514109327MathSciNetCrossRef

12.

Ghanem, R.: Probabilistic characterization of transport in heterogeneous media. Comput. Methods Appl. Mech. Eng. 158, 199–220 (1998). https://doi.org/10.1016/s0045-7825(97)00250-8CrossRefMATH

13.

Ghanem, R.G., Spanos, P.D.: Stochastic Finite Elements: A Spectral Approach. Springer, New York (1991). https://doi.org/10.1007/978-1-4612-3094-6CrossRefMATH

14.

Giraldi, L., Le Maître, O.P., Mandli, K.T., Dawson, C.N., Hoteit, I., Knio, O.M.: Bayesian inference of earthquake parameters from buoy data using a polynomial chaos-based surrogate. Comput. Geosci. 21(4), 683–699 (2017). https://doi.org/10.1007/s10596-017-9646-zMathSciNetCrossRefMATH

15.

Hien, T.D., Kleiber, M.: Stochastic finite element modelling in linear transient heat transfer. Comput. Methods Appl. Mech. Eng. 144(1), 111–124 (1997). https://doi.org/10.1016/S0045-7825(96)01168-1CrossRefMATH

16.

Hou, T.Y., Luo, W., Rozovskii, B., Zhou, H.M.: Wiener chaos expansions and numerical solutions of randomly forced equations of fluid mechanics. J. Comput. Phys. 216, 687–706 (2006). https://doi.org/10.1016/j.jcp.2006.01.008MathSciNetCrossRefMATH

17.

Jasour, A., Wang, A., Williams, B.C.: Moment-based exact uncertainty propagation through nonlinear stochastic autonomous systems. CoRR abs/2101.12490 (2021). https://arxiv.org/abs/2101.12490

18.

Knio, O.M., Maître, O.P.L.: Uncertainty propagation in CFD using polynomial chaos decomposition. Fluid Dyn. Res. 38(9), 616–640 (2006). https://doi.org/10.1016/j.fluiddyn.2005.12.003

19.

Makino, K., Berz, M.: Taylor models and other validated functional inclusion methods. Int. J. Pure Appl. Math. 6, 239–316 (2003)MathSciNetMATH

20.

Meecham, W.C., Jeng, D.T.: Use of the Wiener-Hermite expansion for nearly normal turbulence. J. Fluid Mech. 32(2), 225–249 (1968). https://doi.org/10.1017/S0022112068000698CrossRefMATH

21.

Moosbrugger, M., Stankovič, M., Bartocci, E., Kovács, L.: This is the Moment for Probabilistic Loops. arXiv (2022). https://doi.org/10.48550/arXiv.2204.07185

22.

Mühlpfordt, T., Findeisen, R., Hagenmeyer, V., Faulwasser, T.: Comments on truncation errors for polynomial chaos expansions. IEEE Control Syst. Lett. 2(1), 169–174 (2018). https://doi.org/10.1109/LCSYS.2017.2778138MathSciNetCrossRef

23.

Neher, M., Jackson, K.R., Nedialkov, N.S.: On taylor model based integration of ODEs. SIAM J. Numer. Anal. 45, 236–262 (2007). https://doi.org/10.1137/050638448MathSciNetCrossRefMATH

24.

Sankaranarayanan, S.: Quantitative analysis of programs with probabilities and concentration of measure inequalities. Found. Probab. Program. 259 (2020). https://doi.org/10.1017/9781108770750.009

25.

Sankaranarayanan, S., Chou, Y., Goubault, E., Putot, S.: Reasoning about uncertainties in discrete-time dynamical systems using polynomial forms. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M.F., Lin, H. (eds.) Advances in Neural Information Processing Systems, vol. 33, pp. 17502–17513. Curran Associates, Inc. (2020). https://proceedings.neurips.cc/paper/2020/file/ca886eb9edb61a42256192745c72cd79-Paper.pdf

26.

Son, J., Du, Y.: Probabilistic surrogate models for uncertainty analysis: dimension reduction-based polynomial chaos expansion. Int. J. Numer. Meth. Eng. 121(6), 1198–1217 (2020). https://doi.org/10.1002/nme.6262MathSciNetCrossRef

27.

Stanković, B.: Taylor expansion for generalized functions. J. Math. Anal. Appl. 203, 31–37 (1996). https://doi.org/10.1006/jmaa.1996.0365MathSciNetCrossRefMATH

28.

Steinhardt, J., Tedrake, R.: Finite-time regional verification of stochastic non-linear systems. Int. J. Robot. Res. 31(7), 901–923 (2012). https://doi.org/10.1177/0278364912444146CrossRef

29.

Taylor, J.B.: Discretion versus policy rules in practice. In: Carnegie-Rochester Conference Series on Public Policy, vol. 39, no. 1, pp. 195–214 (1993). https://ideas.repec.org/a/eee/crcspp/v39y1993ip195-214.html

30.

Triebel, H.: Taylor expansions of distributions. In: The Structure of Functions. Birkhäuser Basel (2001). https://doi.org/10.1007/978-3-0348-8257-6_8

31.

Wan, X., Karniadakis, G.E.: An adaptive multi-element generalized polynomial chaos method for stochastic differential equations. J. Comput. Phys. 209, 617–642 (2005). https://doi.org/10.1016/j.jcp.2005.03.023MathSciNetCrossRefMATH

32.

Xiu, D.: Numerical Methods for Stochastic Computations: A Spectral Method Approach. Princeton University Press, Princeton (2010). http://www.jstor.org/stable/j.ctv7h0skv

33.

Xiu, D., Karniadakis, G.E.: The Wiener-Askey polynomial chaos for stochastic differential equations. SIAM J. Sci. Comput. 24(2), 619–644 (2002). https://doi.org/10.1137/S1064827501387826MathSciNetCrossRefMATH

Title: Moment-Based Invariants for Probabilistic Loops with Non-polynomial Assignments
Authors: Andrey Kofnov
Marcel Moosbrugger
Miroslav Stankovič
Ezio Bartocci
Efstathia Bura
Publisher: Springer International Publishing
Book: Quantitative Evaluation of Systems
Print ISBN: 978-3-031-16335-7

Electronic ISBN: 978-3-031-16336-4

Copyright Year: 2022
DOI: https://doi.org/10.1007/978-3-031-16336-4_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"