از الگوریتم‌ها تا نمرات Z: مدل‌سازی احتمالی و آماری در علوم کامپیوتر

The materials here form a textbook for a course in mathematical probability and statistics for computer science students. (It would work fine for general students too.) "Why is this text different from all other texts?" Computer science examples are used throughout, in areas such as: computer networks; data and text mining; computer security; remote sensing; computer performance evaluation; software engineering; data management; etc. The R statistical/data manipulation language is used throughout. Since this is a computer science audience, a greater sophistication in programming can be assumed. It is recommended that my R tutorials be used as a supplement: Chapter 1 of my book on R software development, The Art of R Programming, NSP, 2011 (http://heather.cs.ucdavis.edu/~matloff/R/NMRIntro.pdf) Part of a VERY rough and partial draft of that book (http://heather.cs.ucdavis.edu/~matloff/132/NSPpart.pdf). It is only about 50% complete, has various errors, and presents a number of topics differently from the final version, but should be useful in R work for this class. Throughout the units, mathematical theory and applications are interwoven, with a strong emphasis on modeling: What do probabilistic models really mean, in real-life terms? How does one choose a model? How do we assess the practical usefulness of models? For instance, the chapter on continuous random variables begins by explaining that such distributions do not actually exist in the real world, due to the discreteness of our measuring instruments. The continuous model is therefore just that--a model, and indeed a very useful model. There is actually an entire chapter on modeling, discussing the tradeoff between accuracy and simplicity of models. There is considerable discussion of the intuition involving probabilistic concepts, and the concepts themselves are defined through intuition. However, all models and so on are described precisely in terms of random variables and distributions. For topical coverage, see the book's detailed table of contents. The materials are continuously evolving, with new examples and topics being added. Prerequisites: The student must know calculus, basic matrix algebra, and have some minimal skill in programming. Time Waste Versus Empowerment......Page 27 ALOHA Network Example......Page 29 The Crucial Notion of a Repeatable Experiment......Page 31 Our Definitions......Page 32 Basic Probability Computations: ALOHA Network Example......Page 36 Bayes' Rule......Page 39 ALOHA in the Notebook Context......Page 40 Solution Strategies......Page 41 Example: Divisibility of Random Integers......Page 43 Example: A Simple Board Game......Page 44 Example: Bus Ridership......Page 45 Example: Rolling Dice......Page 47 Improving the Code......Page 48 Simulation of the ALOHA Example......Page 50 Back to the Board Game Example......Page 51 Which Is More Likely in Five Cards, One King or Two Hearts?......Page 52 ``Association Rules'' in Data Mining......Page 54 Multinomial Coefficients......Page 55 Example: Probability of Getting Four Aces in a Bridge Hand......Page 56 Discrete Random Variables......Page 61 Generality—Not Just for Discrete Random Variables......Page 62 Computation and Properties of Expected Value......Page 63 ``Mailing Tubes''......Page 68 Casinos, Insurance Companies and ``Sum Users,'' Compared to Others......Page 69 Definition......Page 70 Intuition Regarding the Size of Var(X)......Page 73 The Coefficient of Variation......Page 74 Covariance......Page 75 Indicator Random Variables, and Their Means and Variances......Page 76 A Combinatorial Example......Page 77 Expected Value, Etc. in the ALOHA Example......Page 79 Distributions......Page 80 Example: Watts-Strogatz Random Graph Model......Page 81 Parameteric Families of Functions......Page 82 The Case of Importance to Us: Parameteric Families of pmfs......Page 83 The Geometric Family of Distributions......Page 84 R Functions......Page 86 Example: a Parking Space Problem......Page 87 The Binomial Family of Distributions......Page 89 Example: Flipping Coins with Bonuses......Page 90 Example: Analysis of Social Networks......Page 91 The Negative Binomial Family of Distributions......Page 92 The Poisson Family of Distributions......Page 93 R Functions......Page 94 The Power Law Family of Distributions......Page 95 Example: a Coin Game......Page 96 Example: the ALOHA Example Again......Page 98 Example: the Bus Ridership Problem Again......Page 99 Multivariate Distributions......Page 100 Trick Coins, Tricky Example......Page 101 Intuition in Retrospect......Page 102 Why Not Just Do All Analysis by Simulation?......Page 103 Proof of Chebychev's Inequality......Page 104 Reconciliation of Math and Intuition (optional section)......Page 105 Example: Die Game......Page 111 Long-Run State Probabilities......Page 112 Example: 3-Heads-in-a-Row Game......Page 113 Example: ALOHA......Page 114 Example: Bus Ridership Problem......Page 116 An Inventory Model......Page 117 A Random Dart......Page 119 But Equation (5.2) Presents a Problem......Page 120 Motivation, Definition and Interpretation......Page 124 Properties of Densities......Page 127 A First Example......Page 128 Density and Properties......Page 129 Example: Modeling of Disk Performance......Page 130 Density and Properties......Page 131 Example: Network Intrusion......Page 133 Example: River Levels......Page 135 The Central Limit Theorem......Page 136 Example: Bug Counts......Page 137 Example: Coin Tosses......Page 138 Optional topic: Formal Statement of the CLT......Page 139 Density and Properties......Page 140 Example: Error in Pin Placement......Page 141 R Functions......Page 142 Example: Garage Parking Fees......Page 143 Connection to the Poisson Distribution Family......Page 144 Density and Properties......Page 146 Example: Network Buffer......Page 147 The Beta Family of Distributions......Page 148 Choosing a Model......Page 150 ``Hybrid'' Continuous/Discrete Distributions......Page 151 Stop and Review: Probability Structures......Page 155 Covariance......Page 159 Example: the Committee Example Again......Page 161 Correlation......Page 162 Sets of Independent Random Variables......Page 163 Covariance Is 0......Page 164 Example: Dice......Page 165 Example: Ratio of Independent Geometric Random Variables......Page 166 Matrix Formulations......Page 167 Covariance Matrices......Page 168 Example: (X,S) Dice Example Again......Page 169 Example: Dice Game......Page 170 Correlation Matrices......Page 173 Multivariate Probability Mass Functions......Page 177 Use of Multivariate Densities in Finding Probabilities and Expected Values......Page 180 Example: a Triangular Distribution......Page 181 Example: Train Rendezvouz......Page 184 Convolution......Page 185 Example: Ethernet......Page 186 Example: Analysis of Seek Time......Page 187 Example: Backup Battery......Page 188 Example: Minima of Independent Exponentially Distributed Random Variables......Page 189 Example: Computer Worm......Page 191 Example: Ethernet Again......Page 192 Parametric Families of Multivariate Distributions......Page 193 Probability Mass Function......Page 194 Example: Component Lifetimes......Page 195 Mean Vectors and Covariance Matrices in the Multinomial Family......Page 196 Densities......Page 199 Geometric Interpretation......Page 200 Properties of Multivariate Normal Distributions......Page 203 The Multivariate Central Limit Theorem......Page 204 Application: Data Mining......Page 205 Derivation and Intuition......Page 211 Example: ``Nonmemoryless'' Light Bulbs......Page 213 Holding-Time Distribution......Page 214 Intuitive Derivation......Page 215 Computation......Page 216 Example: Machine Repair......Page 217 Example: Migration in a Social Network......Page 218 Introduction to Confidence Intervals......Page 221 Random Samples......Page 222 The Sample Mean—a Random Variable......Page 223 Sample Means Are Approximately Normal–No Matter What the Population Distribution Is......Page 224 The Sample Variance—Another Random Variable......Page 225 The ``Margin of Error'' and Confidence Intervals......Page 226 Confidence Intervals for Means......Page 227 Example: Simulation Output......Page 228 A Weight Survey in Davis......Page 229 One More Point About Interpretation......Page 230 General Formation of Confidence Intervals from Approximately Normal Estimators......Page 231 Example: Standard Errors of Combined Estimators......Page 232 Derivation......Page 233 Simulation Example Again......Page 234 Interpretation......Page 235 Planning Ahead......Page 236 Independent Samples......Page 237 Dependent Samples......Page 239 Example: Machine Classification of Forest Covers......Page 241 And What About the Student-t Distribution?......Page 242 Example: Amazon Links......Page 243 Example: Master's Degrees in CS/EE......Page 244 One More Time: Why Do We Use Confidence Intervals?......Page 245 Introduction to Significance Tests......Page 249 The Basics......Page 250 General Testing Based on Normally Distributed Estimators......Page 251 The Notion of ``p-Values''......Page 252 Exact Tests......Page 253 Example: Improved Light Bulbs......Page 254 Example: Test Based on Range Data......Page 255 R Computation......Page 256 Example: Improved Light Bulbs......Page 257 History of Significance Testing, and Where We Are Today......Page 258 The Basic Fallacy......Page 259 What to Do Instead......Page 260 Decide on the Basis of ``the Preponderance of Evidence''......Page 261 Example: Assessing Your Candidate's Chances for Election......Page 262 Example: Guessing the Number of Raffle Tickets Sold......Page 265 Method of Moments......Page 266 Method of Maximum Likelihood......Page 267 Method of Moments......Page 268 R's mle() Function......Page 269 More Examples......Page 271 What About Confidence Intervals?......Page 273 Why Divide by n-1 in s2?......Page 274 Tradeoff Between Variance and Bias......Page 277 More on the Issue of Independence/Nonindependence of Samples......Page 278 Basic Ideas in Density Estimation......Page 281 Histograms......Page 282 Kernel-Based Density Estimation......Page 284 Bayesian Methods......Page 286 How It Works......Page 288 Empirical Bayes Methods......Page 289 Arguments Against Use of Subjective Priors......Page 290 What Would You Do? A Possible Resolution......Page 291 Simultaneous Inference Methods......Page 295 The Bonferonni Method......Page 296 Scheffe's Method......Page 297 Example......Page 298 Other Methods for Simultaneous Inference......Page 299 Introduction to Model Building......Page 301 Estimated Mean......Page 302 The Bias/Variance Tradeoff......Page 303 Implications......Page 305 The Chi-Square Goodness of Fit Test......Page 306 Kolmogorov-Smirnov Confidence Bands......Page 307 Bias Vs. Variance—Again......Page 308 Robustness......Page 309 Real Populations and Conceptual Populations......Page 310 The Goals: Prediction and Understanding......Page 313 Example Applications: Software Engineering, Networks, Text Mining......Page 314 Adjusting for Covariates......Page 315 Example: Marble Problem......Page 316 Estimating That Relationship from Sample Data......Page 317 Example: Baseball Data......Page 320 Multiple Regression: More Than One Predictor Variable......Page 322 Example: Baseball Data (cont'd.)......Page 323 Interaction Terms......Page 324 Meaning of ``Linear''......Page 325 Point Estimates and Matrix Formulation......Page 326 Approximate Confidence Intervals......Page 328 Example: Baseball Data (cont'd.)......Page 330 Example: Baseball Data (cont'd.)......Page 331 What Does It All Mean?—Effects of Adding Predictors......Page 333 Model Selection......Page 335 The Overfitting Problem in Regression......Page 336 Methods for Predictor Variable Selection......Page 337 What About the Assumptions?......Page 339 Regression Diagnostics......Page 340 Example: Prediction of Network RTT......Page 341 Example: OOP Study......Page 342 Slutsky's Theorem......Page 347 Why It's Valid to Substitute s for......Page 348 The Theorem......Page 349 Example: Square Root Transformation......Page 352 Example: Confidence Interval for 2......Page 353 Example: Confidence Interval for a Measurement of Prediction Ability......Page 356 Basic Methodology......Page 357 Computation in R......Page 358 General Applicability......Page 359 Why It Works......Page 360 Nonlinear Parametric Regression Models......Page 361 Classification = Regression......Page 362 Optimality of the Regression Function for 0-1-Valued Y (optional section)......Page 363 Logistic Regression: a Common Parametric Model for the Regression Function in Classification Problems......Page 364 The Logistic Model: Motivations......Page 365 Example: Forest Cover Data......Page 367 What If Y Doesn't Have a Marginal Distribution?......Page 368 Methods Based on Estimating mY;X(t)......Page 369 Nearest-Neighbor Methods......Page 370 Kernel-Based Methods......Page 372 The Naive Bayes Method......Page 373 Support Vector Machines (SVMs)......Page 374 CART......Page 375 Comparison of Methods......Page 377 Symmetric Relations Among Several Variables......Page 378 How to Calculate Them......Page 379 Log-Linear Models......Page 381 The Data......Page 382 The Models......Page 383 Parameter Estimation......Page 384 Simpson's (Non-)Paradox......Page 385 Basic Concepts......Page 389 A Cautionary Tale: the Bus Paradox......Page 391 Length-Biased Sampling......Page 392 Probability Mass Functions and Densities in Length-Biased Sampling......Page 393 Renewal Theory......Page 394 Intuitive Derivation of Residual Life for the Continuous Case......Page 395 Age Distribution......Page 396 Example: Disk File Model......Page 398 Example: Memory Paging Model......Page 399 Conditional Pmfs and Densities......Page 403 Conditional Expected Value As a Random Variable......Page 404 Famous Formula: Theorem of Total Expectation......Page 405 Example: Trapped Miner......Page 406 Example: Analysis of Hash Tables......Page 408 Simulation of Random Vectors......Page 410 Mixture Models......Page 411 Transform Methods......Page 413 Generating Functions......Page 414 Moment Generating Functions......Page 415 Sums of Independent Poisson Random Variables Are Poisson Distributed......Page 416 Random Number of Bits in Packets on One Link......Page 417 Other Uses of Transforms......Page 418 Vector Space Interpretations (for the mathematically adventurous only)......Page 419 Conditional Expectation As a Projection......Page 420 Proof of the Law of Total Expectation......Page 422 Example: Finite Random Walk......Page 427 Long-Run Distribution......Page 428 Derivation of the Balance Equations......Page 429 Solving the Balance Equations......Page 430 Periodic Chains......Page 431 Description......Page 432 Initial Analysis......Page 433 Going Beyond Finding......Page 434 The Model......Page 436 Going Beyond Finding......Page 438 Example: Slotted ALOHA......Page 439 Going Beyond Finding......Page 440 Simulation of Markov Chains......Page 442 Continuous-Time Markov Chains......Page 444 Continuous-Time Birth/Death Processes......Page 445 Some Mathematical Conditions......Page 446 Example: Random Walks......Page 447 Finding Hitting and Recurrence Times......Page 448 Example: Tree-Searching......Page 450 Introduction......Page 455 Steady-State Probabilities......Page 456 Distribution of Residence Time/Little's Rule......Page 457 M/M/c......Page 460 M/M/2 with Heterogeneous Servers......Page 461 Cell Communications Model......Page 463 Stationary Distribution......Page 464 Nonexponential Service Times......Page 465 Markov Property......Page 467 Reversible Markov Chains......Page 468 Making New Reversible Chains from Old Ones......Page 469 Example: Queues with a Common Waiting Area......Page 470 Closed-Form Expression for for Any Reversible Markov Chain......Page 471 Tandem Queues......Page 472 Jackson Networks......Page 473 Open Networks......Page 474 Closed Networks......Page 475 Terminology and Notation......Page 477 Matrix Addition and Multiplication......Page 478 Linear Independence......Page 479 Eigenvalues and Eigenvectors......Page 480 Correspondences......Page 483 First Sample Programming Session......Page 484 Second Sample Programming Session......Page 488 Third Sample Programming Session......Page 490 The Reduce() Function......Page 491 S3 Classes......Page 492 Handy Utilities......Page 493 Graphics......Page 495 Complex Numbers......Page 496 Installation and Use......Page 499 Basic Structures......Page 500 Example: Simple Line Graphs......Page 501 Example: Census Data......Page 503 What's Going on Inside......Page 510 For Further Information......Page 513