臺灣博碩士論文加值系統

The simulation of rare events in Monte Carlo is of practical importance across many disciplines including circuit simulation, finance, and meterology to name a few. To make inferences about the behavior of distributions in systems which have a likelihood of 1 in billions, simulation by traditional Monte Carlo becomes impractical. Intuitively, Monte Carlo samples which are likely (i.e. samples drawn from regions of higher probability density) have little influence on the tail distribution which is associated with rare events. This work provides a novel methodology to directly sample rare events in input multivariate random vector space as a means to efficiently learn about the distribution tail in the output space. In addition, the true form of the Monte Carlo simulation is modeled by first linear and then quadratic forms. A systematic procedure is developed which traces the flow from the linear or quadratic modeling to the computation of distribution statistics such as moments and quantiles directly from the modeling form itself. Next, a general moment calculation method is derived based on the distribution quantiles where no underlying linear or quadratic model is assumed. Finally, each of the proposed methods is grounded in practical circuit simulation examples. Overall, the thesis provides several new methods and approaches to tackle some challenging problems in Monte Carlo simulation, probability distribution modeling, and statistical analysis.

Abstract i
Acknowledgements iii
List of Figures xii
List of Tables xvi
List of Algorithms xviii
Chapter 1 Introduction 1
1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation and Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.1 Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.2 Statistical Blockade . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Chapter 2 Background : Random Variables and their Statistics 9
2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Random Variable Probability Distribution . . . . . . . . . . . . . . . 10
2.3 Expectations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.1 Univariate Expectation . . . . . . . . . . . . . . . . . . . . . . 12
2.3.2 Multivariate Expectation . . . . . . . . . . . . . . . . . . . . . 13
2.4 Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Order statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6 Expectation of Gaps between Order Statistics . . . . . . . . . . . . . 15
2.6.1 Standard Moments . . . . . . . . . . . . . . . . . . . . . . . . 16
2.6.2 L-Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.7 Sample Quantiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.8 Con dence Intervals for Binomial Proportions . . . . . . . . . . . . . 20
2.9 QQ Plots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.10 Error Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.11 Selected Probability Distributions . . . . . . . . . . . . . . . . . . . . 25
2.11.1 Normal distribution . . . . . . . . . . . . . . . . . . . . . . . . 26
2.11.2 Chi-squared distribution . . . . . . . . . . . . . . . . . . . . . 27
2.11.3 Beta distribution . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.11.4 Log-normal distribution . . . . . . . . . . . . . . . . . . . . . 29
2.11.5 Skew Normal distribution . . . . . . . . . . . . . . . . . . . . 30
2.11.6 Weibull distribution . . . . . . . . . . . . . . . . . . . . . . . 32
2.11.7 Student''s t distribution . . . . . . . . . . . . . . . . . . . . . . 33
Chapter 3 Monte Carlo Sampling Techniques 34
3.1 Monte Carlo Simulation . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2 Motivation for Rare Sample Simulation . . . . . . . . . . . . . . . . . 35
3.3 Linear Forms of Standard Normal Random Vectors . . . . . . . . . . 37
3.3.1 Empirical Veri cation . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Statistics of the Linear Form . . . . . . . . . . . . . . . . . . . . . . . 41
3.5 Monte Carlo Sampling for Machine Learning . . . . . . . . . . . . . . 41
3.5.1 Uniform Sampling in High Dimensions . . . . . . . . . . . . . 44
3.5.2 Hyperspherical Uniform Volumetric Sampling . . . . . . . . . 47
3.6 Rejection Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.7 Generating List of Random Numbers in Sorted Order . . . . . . . . . 53
3.8 Inverse Transform Sampling . . . . . . . . . . . . . . . . . . . . . . . 55
3.9 In-order Multivariate Sampling . . . . . . . . . . . . . . . . . . . . . 56
3.10 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.10.1 Correlated Sampling . . . . . . . . . . . . . . . . . . . . . . . 63
3.10.2 Hyperspherical Non-Uniform Random Sampling . . . . . . . . 65
3.10.3 Directional Sampling . . . . . . . . . . . . . . . . . . . . . . . 67
3.11 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Chapter 4 Quadratic Forms of the Multivariate Standard Normal 73
4.1 Quadratic Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2 Quadratic Modeling with Monomial Polynomials . . . . . . . . . . . . 74
4.3 Quadratic Modeling with Legendre Polynomials . . . . . . . . . . . . 75
4.4 Linearization via Eigenvector Decomposition . . . . . . . . . . . . . . 78
4.5 Raw Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.6 Central Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.7 Cumulants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.8 Quantiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.9 Toy Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.10 Quadratic Modeling Examples . . . . . . . . . . . . . . . . . . . . . . 86
4.10.1 Univariate Linear . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.10.2 Univariate Quadratic . . . . . . . . . . . . . . . . . . . . . . . 88
4.10.3 Multivariate Quartic . . . . . . . . . . . . . . . . . . . . . . . 89
4.10.4 Multivariate Exponential and Quadratic . . . . . . . . . . . . 90
4.10.5 Quadratic Modeling Example Observations . . . . . . . . . . . 91
4.11 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Chapter 5 Quantile-Based Moments 93
5.1 Computing Moments from Quantile Information . . . . . . . . . . . . 93
5.2 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Chapter 6 Applications 110
6.1 Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.2 Monotonicity Veri cation . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.3 In-Order Multivariate Sampling Experiments . . . . . . . . . . . . . . 116
6.4 Linear and Quadratic Modeling with Direct Model-Based Quantile
Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.5 Quantile-Based Moment Experiments . . . . . . . . . . . . . . . . . . 120
6.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
Chapter 7 Conclusions 125
7.1 Connections Between Our Proposed Methods . . . . . . . . . . . . . 125
7.2 Connections of Our Proposed Methods with Related Work . . . . . . 126
7.2.1 Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . 126
7.2.2 Statistical Blockade . . . . . . . . . . . . . . . . . . . . . . . . 127
7.3 Thesis Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.4 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Bibliography 131
Appendix A Integral of High Order Error Function 1
Appendix B Operational Ampli er Netlist Listing 4

[1] M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover, New York, 1964.
[2] J. Aitchison and J. A. Brown. The lognormal distribution with special reference to its uses in economics. University of Cambridge Department of Applied Ecnomics Monograph 5, page 176, 1957.
[3] A. Azzalini. A class of distributions which includes the normal ones. Scandinavian Journal of Statistics, pages 171-178, 1985.
[4] J. L. Bentley and J. B. Saxe. Generating sorted lists of random numbers. Transactions on Mathematical Software, 6(3):359-364, Sept. 1979.
[5] D. C. Brock and G. E. Moore. Understanding Moore''s law: four decades of innovation. Chemical Heritage Foundation, 2006.
[6] P.-L. Chen, C.-T. Tsai, Y.-N. Chen, K.-C. Chou, C.-L. Li, C.-H. Tsai, K.-W. Wu, Y.-C. Chou, C.-Y. Li, W.-S. Lin, S.-H. Yu, R.-B. Chiu, C.-Y. Lin, C.-C. Wang, P.-W. Wang, W.-L. Su, C.-H. Wu, T.-T. Kuo, T. G. McKenzie, Y.-H. Chang, C.-S. Ferng, C.-M. Ni, H.-T. Lin, C.-J. Lin, and S.-D. Lin. A linear ensemble of individual and blended models for music rating prediction. In Proceedings of KDD Cup 2011, pages 21-60, 2012.
[7] C. J. Clopper and E. S. Pearson. The use of con dence or ducial limits illustrated in the case of the binomial. Biometrika, 26(4):404-413, 1934.
[8] E. A. Cornish and R. A. Fisher. Moments and cumulants in the speci cation of distributions. Revue de l''Institut International de Statistique, pages 307-320, 1938.
[9] R. B. Davies. Numerical inversion of a characteristic function. Biometrika, 60(2):415-417, 1973.
[10] N. I. Fisher. Statistical Analysis of Circular Data. Cambridge University Press, 1995.
[11] J. H. Friedman. Random event generation with preferred frequency distributions. Journal of Computational Physics, (7):201, 1970.
[12] F. Galton. The most suitable proportion between the value of rst and second prizes. Biometrika, pages 385-399, 1902.
[13] J. W. L. Glaisher. On a class of de nite integrals. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 42(280):294-302, 1871.
[14] G. H. Golub and C. F. Van Loan. Matrix Computations, volume 3. JHU press, 2012.
[15] I. S. Gradshteyn and I. M. Ryzhik. Table of Integrals, Series, and Products. Academic Press, 2014.
[16] M. Hane, T. Ikezawa, and T. Ezaki. Atomistic 3d process/device simulation considering gate line-edge roughness and poly-si random crystal orientation effects [mosfets]. In IEEE International Electron Devices Meeting 2003, pages 9-15. IEEE, 2003.
[17] R. Harman and V. Lacko. On decompositional algorithms for uniform sampling from n-spheres and n-balls. Journal of Multivariate Analysis, 101(10):2297-2304, 2010.
[18] F. Hausdorff. Summationsmethoden und momentfolgen. i. Mathematische Zeitschrift, 9(1-2):74-109, 1921.
[19] A. Hazen. The storage to be provided in impounding reservoirs for municipal water supply. Transactions of the American Society of Civil Engineers, 77:1539-1669, 1914.
[20] G. A. Holton. Value-at-risk: Theory and Practice. 2nd edition. https://www.value-at-risk.net/, 2014.
[21] J. R. Hosking. L-moments: Analysis and estimation of distributions using linear combinations of order statistics. Journal of the Royal Statistical Society: Series B (Methodological), 52(1):105-124, 1990.
[22] J. R. M. Hosking, J. R. Wallis, and E. F. Wood. Estimation of the generalized extreme-value distribution by the method of probability-weighted moments. Technometrics, 27(3):251-261, 1985.
[23] R. J. Hyndman and Y. Fan. Sample quantiles in statistical packages. The American Statistician, 50(4):361-365, 1996.
[24] J.-P. Imhof. Computing the distribution of quadratic forms in normal variables. Biometrika, 48(3/4):419-426, 1961.
[25] ISO26262. Road Vehicles : Functional Safety Standard, International Standards Organization, Geneva, Switzerland. https://www.iso.org/standard/68383.html, 2018.
[26] N. Johnson, S. Kotz, and N. Balakrishnan. Continuous Univariate Distributions. Number v. 2 in Wiley series in Probability and Mathematical Statistics: Applied Probability and Statistics. Wiley & Sons, 1995.
[27] G. Kitagawa. Monte Carlo lter and smoother for non-gaussian nonlinear state space models. Journal of Computational and Graphical Statistics, 5(1):1-25, 1996.
[28] D. E. Knuth. The Art of Computer Programming, Volume 3: (2nd Edition) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998.
[29] C.-Y. Li, W.-L. Su, T. G. McKenzie, F.-C. Hsu, S.-D. Lin, J. Y.-j. Hsu, and P. B. Gibbons. Recommending missing sensor values. In 2015 IEEE International Conference on Big Data (Big Data), pages 381-390. IEEE, 2015.
[30] E. Limpert, W. A. Stahel, and M. Abbt. Log-normal distributions across the sciences: keys and clues: on the charms of statistics, and how mechanical models resembling gambling machines offer a link to a handy way to characterize log-normal distributions, which can provide deeper insight into variability and probability,normal or log-normal: that is the question. BioScience, 51(5):341-352, 2001.
[31] A. M. Mathai and S. B. Provost. Quadratic Forms in Random Variables: Theory and Applications. Dekker, 1992.
[32] T. G. McKenzie, C.-S. Ferng, Y.-N. Chen, C.-L. Li, C.-H. Tsai, K.-W. Wu, Y.-H. Chang, C.-Y. Li, W.-S. Lin, S.-H. Yu, et al. Novel models and ensemble techniques to discriminate favorite items from ones for personalized music recommendation. In Proceedings of the 2011 International Conference on KDD Cup 2011-Volume 18, pages 101-135. JMLR. org, 2011.
[33] S. Mittal. A survey of architectural techniques for managing process variation. ACM Computing Surveys (CSUR), 48(4):54, 2016.
[34] E. W. Montroll and M. F. Shlesinger. On 1/f noise and other distributions with long tails. Proceedings of the National Academy of Sciences, 79(10):3380-3383, 1982.
[35] G. E. Moore et al. Cramming more components onto integrated circuits. Electronics, 38(8), 1965.
[36] M. E. Muller. A note on a method for generating points uniformly on n-dimensional spheres. Communications of the ACM, 2(4):19-20, 1959.
[37] D. B. Owen. Tables for computing bivariate normal probabilities. The Annals of Mathematical Statistics, 27(4):1075-1090, 1956.
[38] K. Pearson. On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 50(302):157-175, 1900.
[39] K. Pearson. Note on Francis Galton s problem. Biometrika, 1(4):390-399, 1902.
[40] M. J. Pelgrom and A. C. Duinmaijer. Matching properties of mos transistors. In ESSCIRC''88: Fourteenth European Solid-State Circuits Conference, pages 327-330. IEEE, 1988.
[41] R. Y. Rubinstein and D. P. Kroese. Simulation and the Monte Carlo method, volume 10. John Wiley & Sons, 2016.
[42] J. A. Shohat and J. D. Tamarkin. The Problem of Moments. Number 1. American Mathematical Soc., 1943.
[43] A. Singhee and R. A. Rutenbar. Statistical blockade: a novel method for very fast monte carlo simulation of rare circuit events, and its application. In 2007 Design, Automation & Test in Europe Conference & Exhibition, pages 1-6. IEEE, 2007.
[44] M. Thulin et al. The cost of using exact con dence intervals for a binomial proportion. Electronic Journal of Statistics, 8(1):817-840, 2014.
[45] R. M. Vogel and N. M. Fennessey. L moment diagrams should replace product moment diagrams. Water Resources Research, 29(6):1745-1752, 1993.
[46] H.-F. Yu, H.-Y. Lo, H.-P. Hsieh, J.-K. Lou, T. G. McKenzie, J.-W. Chou, P.-H. Chung, C.-H. Ho, C.-F. Chang, Y.-H. Wei, J.-Y. Weng, E.-S. Yan, C.-W. Chang, T.-T. Kuo, Y.-C. Lo, P. T. Chang, C. Po, C.-Y. Want, Y.-H. Huang, C.-W. Hung, Y.-X. Ruan, Y.-S. Lin, S.-d. Lin, H.-T. Lin, and C.-J. Lin. Feature Engineering and Classi er Ensemble for KDD Cup 2010. Journal of Machine Learning Research, 1(16), 2010.