Probability and Statistics for Computer Science

1 Notation and conventions 9

1.0.1 Background Information........................................................................ 10

1.1 Acknowledgements................................................................................................. 11

I Describing Datasets

; 12

2 First Tools for Looking at Data 13

2.1 Datasets....................................................................................

................................... 13

2.2 What's Happening? - Plotting Data................................................................. 15

2.2.1 Bar< Charts.................................................................................................... 16

2.2.2 Histograms................................................................................................... 16

2.2.3 How to Make Histograms...................................................................... 17

2.2.4 Conditional Histograms.......................................................................... 19

2.3 Summarizing 1D Data.................................

........................................................... 19

2.3.1 The Mean...................................................................................................... 20

2.3.2 Standard Deviation................................................................................... 22

2.3.3 Computing Mean and Standard Deviation Online...................... 26

2.3.4 Variance......................................................................................................... 26

2.3.5 The Median.................................................................................................. 27

2.3.6 Interqu

artile Range.................................................................................. 29

2.3.7 Using Summaries Sensibly.................................................................... 30

2.4 Plots and Summaries............................................................................................. 31

2.4.1 Some Properties of Histograms.......................................................... 31

2.4.2 Standard Coordinates and Normal Data......................................... 34

2.4.3 Box Plots....................................................................................................... 38

2.5 Whose is bigger? Inves

tigating Australian Pizzas...................................... 39

2.6 You should.................................................................................................................. 43

2.6.1 remember these definitions:................................................................. 43

2.6.2 remember these terms............................................................................ 43

2.6.3 remember these facts:............................................................................. 43

2.6.4 be able to...................................................................................................... 43

3 Looking at Relationships

47

3.1 Plotting 2D Data...................................................................................................... 47

3.1.1

3.1.2 Series...............................

............................................................................... 51

3.1.3 Scatter Plots for Spatial Data.............................................................. 53

3.1.4 Exposing Relationships with Scatter Plots..................................... 54

3.2 Correlation.................................................................................................................. 57

3.2.1 The Correlation Coefficient................................................................... 60

3.2.2 Using Correlation to Predict................................................................ 64

3.2.3 Confusion caused by co

rrelation......................................................... 68

1

<3.3 Sterile Males in Wild Horse Herds.................................................................. 68

3.4 You should.................................................................................................................. 72

3.4.1 remember these definitions:................................................................. 72

3.4.2 remember these terms............................................................................ 72

3.4.3

remember these facts: . .

. . .

3.4.4

use these procedures: . . .

. . .

3.4.5

be able to: . . . . . . . . .

. . .

. . . . . . . . . . . . . . . . . 72

. . . . . . . . . . . . . . . . . 72

. . . . . . . . . . . . . . . . . 72

II Probability &

nbsp; 78

4 Basic ideas in probability 79

4.1 Experiments, Outcomes and Probability....................................................... 79

4.1.1 Outcomes and Probability...................................................................... 79

4.2 Events.................

.......................................................................................................... 81

4.2.1 Computing Event Probabilities by Counting Outcomes............. 83

4.2.2 The Probability of Events...................................................................... 87

4.2.3 Computing Probabilities by Reasoning about Sets...................... 89

4.3 Independence............................................................................................................ 92

4.3.1 Example: Airline Overbooking............................................................ 96

4.4 Conditional ...........................................

............. 99

4.4.1 Evaluating Conditional Probabilities.............................................. 100

4.4.2 Detecting Rare Events is Hard......................................................... 104

4.4.3 Conditional Probability and Various Forms of Independence . 106 4.4.4 The Prosecutor's Fallacy 108

4.4.5 Example: The Monty Hall Problem................................................ 110

4.5 Extra Worked Examples.................................................................................... 112

4.5.1 Outcomes and Probability........................................

........................... 112

4.5.2 Events.......................................................................................................... 114

4.5.3 Independence........................................................................................... 115

4.5.4 Conditional Probability......................................................................... 117

4.6 You should............................................................................................................... 121

4.6.1 remember these definitions:.............................................................. 121

4.6.2 remember these terms........

................................................................. 121

4.6.3 remember and use these facts.......................................................... 121

4.6.4 remember these points:....................................................................... 121

4.6.5 be able to.................................................................................................... 121

5 Random Variables and Expectations

128

5.1 Random Variables................................................................................................. 128

5.1.1 Joint and Conditional Probability for Random Variables . . . 131

5.1.2 Just a Little Continuous Probability............................................... 134

5.2 Expectations and Expected Values................................................................ 137

5.2.1 Expected Values...................................................................................... 138

5.2.2 Mean, Variance and Covariance....................................................... 141

5.2.3

Expectations and Statistics................................................................. 145

5.3 The Weak Law of Large Numbers................................................................ 145

5.3.1

IID Samples . . . . . . .

. .

. .

. . . .

. . . . .

. . .

. . . .

. 145

5.3.2

Two Inequalities . . . .

. .

. .

. . . .

. . . . .

. . .

. . . .<

. 146

5.3.3

Proving the Inequalities

. .

. .

. . . .

. . . . .

. . .

. . . .

. 147

5.3.4 The Weak Law of Large Numbers.................................................. 149

5.4 Using the Weak Law of Large Numbers 151

5.4.1 Should you accept a bet?..................................................................... 151

5.4.2 Odds, Expectations and Bookmaking - a Cultural Diversion 152 5.4.3 Ending a Game Early 154

5.4.4 Making a Decision with Decision Trees and

Expectations . . 154 5.4.5 Utility 156

5.5 You should................................................................................... 159

5.5.1 remember these definitions:.............................................................. 159

5.5.2 remember these terms......................................................................... 159

5.5.3 use and remember these facts.......................................................... 159

5.5.4 be able to.................................................................................................... 160

6 Useful Probability Distributions

; 167

6.1 Discrete Distributions 167

6.1.1 The Discrete Uniform Distribution................................................. 167

6.1.2 Bernoulli Random Variables..........................................................

..... 168

6.1.3 The Geometric Distribution................................................................ 168

6.1.4 The Binomial Probability Distribution........................................... 169

6.1.5 Multinomial probabilities..................................................................... 171

6.1.6 The Poisson Distribution..................................................................... 172

6.2 Continuous Distributions

; 174

6.2.1 The Continuous Uniform Distribution........................................... 174

6.2.2 The Beta Distribution........................................................................... 174

6.2.3 The Gamma Distribution..................................................................... 176

6.2.4 The Exponential Distribution............................................................ 176

6.3 The Normal Distribution ; 178

6.3.1 The Standard Normal Distribution................................................. 178

6.3.2 The Normal Distribution..................................................................... 179

6.3.3 Properties of The Normal Distribution......................................... 180

6.4 Approximating Binomials with Large N 182

6.4.1 Large N..............................................................

......................................... 183

6.4.2 Getting Normal<........................................................................................ 185

6.4.3 Using a Normal Approximation to the Binomial Distribution 187

6.5

You should . . . . . . . . . . . . .

. .

. . . .

. . . . .

. . .

. .

6.5.1 remember these definitions:

. .

. . . .

. . . . .

. . .

. .

6.5.2

remember these terms: .

. .

. .

. . . .

. . . . .

. . .

. .

6.5.3

remember these facts: .

. .

. .

. . . .

. . . . .

. . .

. .

6.5.4

remember these points:

. .

. .

.

. . .

. . . . .

. . .

. .<

. . . 188

. . . 188

. . . 188

. . . 188

. . . 188

III Inference

; 196

7 Samples and Populations 197

7.1 The Sample Mean................................................................................................. 197

7.1.1 The Sample Mean is an Estimate of the Population Mean . . 197

7.1.2 The Varianc

e of the Sample Mean.................................................. 198

7.1.3 When The Urn Model Works............................................................ 201

7.1.4 Distributions are Like Populations................................................. 202

7.2 Confidence Intervals............................................................................................ 203

7.2.1 Constructing Confidence Intervals.................................................. 203

7.2.2 Estimating the Variance of the Sample Mean............................ 204

7.2.3 The Probability Distribution of the Sample Mean..................... 206 &

lt;

7.2.4 Confidence Intervals for Population Means................................. 208

7.2.5 Standard Error Estimates from Simulation................................. 212

7.3 You should............................................................................................................... 216

7.3.1 remember these definitions:.............................................................. 216

7.3.2 remember these terms......................................................................... 216

7.3.3 remember these facts:........................................................................... 216

7.3.4 use these procedures............................................................................. 216

7.3.5 be able to.................................................................................................... 216

8 The Significance of Evidence 221

8.1 Significance..............................................................

................................................ 222

8.1.1 Evaluating Significance......................................................................... 223

8.1.2 P-values....................................................................................................... 225

8.2 Comparing the Mean of Two Populations.................................................. 230

8.2.1 Assuming Known Population Standard Deviations................... 231

8.2.2 Assuming Same, Unknown Population Standard Deviation . 233

8.2.3 Assuming Different, Unknown Population Stand

ard Deviation 235

8.3 Other Useful Tests of Significance................................................................. 237

8.3.1 F-tests and Standard Deviations...................................................... 237

8.3.2 2 Tests of Model Fit............................................................................ 239

8.4 Dangerous Behavior............................................................................................. 244

8.5 You should............................................................................................................... 246

8.5.1 remember these definitions:......................................

........................ 246

8.5.2 remember

8.5.3

remember these facts: . .

. . .

8.5.4

use these procedures: . . .

. . .

8.5.5

be able to: . . . . . . . . .

. . .

. . . . . . . . . . . . . . . . . 246

. . . . . . . . . . . . . . . . . 246

. . . . . . . . . . . . . . . . . 246

9 Experiments &nbs

p; 251

9.1 A Simple Experiment: The Effect of a Treatment.................................. 251

9.1.1 Randomized Balanced Experiments............................................... 252

9.1.2   Decomposing Error in Predictions.................................................. 253

9.1.3 Estimating the Noise Variance......................................................... 253

9.1.4 The ANOVA Table.................................................................................. 255

9.1.5 Unbalanced Experiments.................................................................... 257

9.1.6 Significant Differences.......................................................................... 259

9.2 Two Factor Experiments.................................................................................... 261

9.2.1 &n

bsp; Decomposing the Error........................................................................ 264

9.2.2 Interaction Between Effects................................................................ 265

9.2.3 The Effects of a Treatment................................................................. 266

9.2.4 Setting up an ANOVA Table.............................................................. 267

9.3 You should............................................................................................................... 272

9.3.1 remember these definitions:.............................................................. 272

9.3.2

remember these terms......................................................................... 272

9.3.3 remember these facts:........................................................................... 272

9.3.4 use these procedures............................................................................. 272

9.3.5 be able to.................................................................................................... 272

9.3.6 Two-Way Experiments.......................................................................... 274

10 Inferring Probability Models from Data &n

bsp; 275

10.1 Estimating Model Parameters with Maximum Likelihood.................. 275

10.1.1 The Maximum Likelihood Principle............................................... 277

10.1.2 Binomial, Geometric and Multinomial Distributions................ 278

10.1.3 Poisson and Normal Distributions................................................... 281

10.1.4 Confidence Intervals for Model Parameters................................ 286

10.1.5 Cautions about Maximum Likelihood............................................ 288

10.2 Incorporating Prio

rs with Bayesian Inference.......................................... 289

10.2.1 Conjugacy................................................................................................... 292

10.2.2 MAP Inference......................................................................................... 294

10.2.3 Cautions about Bayesian Inference................................................. 296

10.3 Bayesian Inference for Normal Distributions............................................ 296

10.3.1 Example: Measuring Depth of a Borehole................................... 296

10.3.2 Normal Prior and Normal Likelihood Yield Normal Posterior 297

10.3.3 Filtering....................................

.................................................................. 300

10.4 You should............................................................................................................... 303

10.4.1 remember these definitions:.............................................................. 303

10.4.2 remember these terms......................................................................... 303

10.4.3 remember these facts:........................................................................... 304

10.4.4 use these procedures............................................................................. 304

10.4.5 be able to.................................................................................................... 304

&

lt;

IV Tools 312

11 Extracting Important Relationships in High Dimensions 313

11.1 Summaries and Simple Plots........................................................................... 313

11.1.1 The Mean......................

............................................................................. 314

11.1.2 Stem Plots and Scatterplot Matrices.............................................. 315

11.1.3 Covariance.................................................................................................. 317

11.1.4 The Covariance Matrix......................................................................... 319

11.2 Using Mean and Covariance to Understand High Dimensional Data . 321

11.2.1 Mean and Covariance under Affine Transformations............... 322

11.2.2

. .

324

. .

325

. .

326

. .

327

. .

329

.

332

. .

334

. .

335

. .

335

. .

338

. .

339

. .

341

. .

<

345

. .

345

. .

345

. .

345

. .

345

. .

345

349

. .

349

. .

350

. .

350

. .

351

. .

351

. .

353

. .

355

. .

357

. .

358

. .

359

. .

<360

.< .

361

<

Eigenvectors and Diagonalization . . . . . . . . . . . . . .

11.2.3 Diagonalizing Covariance by Rotating Blobs . . . . . . . .

11.2.4 Approximating Blobs . . . . . . . . . . . . . . . . . . . .

11.2.5 Example: Transforming the Height-Weight Blob . . . . .

11.3 Principal Components Analysis . . . . . . . . . . . . . . . . . . .

11.3.1 Example: Representing Colors with Principal Components

11.3.2 Example: Representing Faces

with Principal Components

11.4 Multi-Dimensional Scaling . . . . . . . . . . . . . . . . . . . . . .

11.4.1 Choosing Low D Points using High D Distances . . . . . .

11.4.2 Factoring a Dot-Product Matrix . . . . . . . . . . . . . .

11.4.3 Example: Mapping with Multidimensional Scaling . . . .

11.5 Example: Understanding Height and Weight . . . . . . . . . . . 11.6 You should . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11.6.1 remember these definitions: . . . . . . . . . . . . . . . . .

11.6.2 remember these terms: . . . . . . . . . . . . . . . . . . . .

11.6.3 remember these facts: .&

nbsp; . . . . . . . . . . . . . . . . . . .

11.6.4 use these procedures: . . . . . . . . . . . . . . . . . . . . . 11.6.5 be able to: . . . . . . . . . . . . . . . . . . . . . . . . . . .

12 Learning to Classify

12.1 Classification: The Big Ideas . . . . . . . . . . . . . . . . . . . . 12.1.1 The Error Rate . . . . . . . . . . . . . . . . . . . . . . . . 12.1.2 Overfitting . . . . . . . . . . . . . . . . . . . . . . . . . . 12.1.3 Cross-Validation . . . . . . . . . . . . . . . . . . . . . . .

12.1.4 Is the Classifier Working Well? . . . . . . . . . . . . . . .

12.2 Classifying with Nearest Neighbors . . . . .

. . . . . . . . . . . .

12.3 Classifying with Naive Bayes . . . . . . . . . . . . . . . . . . . . 12.3.1 Missing Data . . . . . . . . . . . . . . . . . . . . . . . . .

12.4 The Support

12.4.1 Choosing a Classifier with the Hinge Loss . . . . . . . . .

12.4.2 Finding a Minimum: General Points . . . . . . . . . . . .

12.4.3 Finding a Minimum: Stochastic Gradient Descent . . . .

12.4.4 Example: Training an SVM with Stochastic Gradient Descent 363

12.4.5 Multi-Class Classification with SVMs..................

............................ 366

12.5 Classifying with Random Forests................................................................... 367

12.5.1 Building a Decision Tree..................................................................... 367

12.5.2 Choosing a Split with Information Gain........................................ 370

12.5.3 Forests......................................................................................................... 373

12.5.4 Building and Evaluating a Decision Forest.................................. 374

12.5.5 Classifying Data Items with a Decision Forest........................... 375

12.6 You should...................................................................

............................................ 378

12.6.1 remember these definitions:.............................................................. 378

12.6.2 remember these terms......................................................................... 378

12.6.3 remember these facts:........................................................................... 379

12.6.4 use these procedures............................................................................. 379

12.6.5 be able to.................................................................................................... 379

<

13.1 The Curse of Dimension........................................................................

............. 384

13.1.1 The Curse: Data isn't Where You Think it is............................. 384

13.1.2 Minor Banes of Dimension.................................................................. 386

13.2 The Multivariate Normal Distribution......................................................... 387

13.2.1 Affine Transformations and Gaussians.......................................... 387

13.2.2 Plotting a 2D Gaussian: Covariance Ellipses.............................. 388

13.3 Agglomerative and Divisive Clustering........................................................ 389

13.3.1 Clustering and Distance....................................................................... 391

13.4 &

nbsp; The K-Means Algorithm and Variants......................................................... 392

13.4.1 How to choose K...................................................................................... 395

13.4.2 Soft Assignment....................................................................................... 397

13.4.3 General Comments on K-Means....................................................... 400

13.4.4 K-Mediods.................................................................................................. 400

13.5 Application Example: Clustering Documents........................................... 401

13.5.1 A Topic Model......................................................................................

.... 402

13.6 Describing Repetition with Vector Quantization...................................... 403

13.6.1 Vector Quantization............................................................................... 404

13.6.2 Example: Groceries in Portugal....................................................... 406

13.6.3 Efficient Clustering and Hierarchical K Means.......................... 409

13.6.4 Example: Activity from Accelerometer Data............................... 409

13.7 You should............................................................................................................... 413

13.7.1 remember these definitions:.............................................................. 413

13.7.2 remember these terms......................................................................... 413

13.7.3 remember these facts:........................................................................... 413

13.7.4 use these procedures............................................................................. 413

14 Regression &nbs

p; 417

14.1.1 Regression to Make Predictions....................................................... 417

14.1.2 Regression to Spot Trends.................................................................. 419

14.1 Linear Regression and Least Squares.......................................................... 421

14.1.1 Linear Regression................................................................................... 421

14.1.2 Choosing beta.................................................................................................. 422

14.1.3 Solving the Least Squares Problem................................................ 423

14.1.4 &n

bsp; Residuals..................................................................................................... 424

14.1.5 R-squared.................................................................................................... 424

14.2 Producing Good Linear Regressions............................................................. 427

14.2.1 Transforming Variables........................................................................ 428

14.2.2 Problem Data Points have Significant Impact............................ 431

14.2.3 Functions of One Explanatory Variable........................................ 433

14.2.4 Regularizing Linear Regressions...................................................... 435

14.3 &nbs

p; Exploiting Your Neighbors

14.3.1 Using your Neighbors to Predict More than a Number............ 441

14.3.2 Example: Filling Large Holes with Whole Images.................... 441

14.4

You should . . . . . . . . . . . . .

. .

. . . .

. . . . .

. . .

14.4.1 remember these definitions:

. .

. . . .

. . .

. .

. . .

14.4.2 remember these terms: . . .

. .

. . . .

. . . . .

. . .

. . . . . 444

. . . . . 444

. . . . . 444

14.4.3 remember these facts:........................................................................... 444

14.4.4 remember these procedures:............................................................. 444

15 Markov Chains and Hidden Markov Models &n

bsp; 454

15.1 Markov Chains........................................................................................................ 454

15.1.1 Transition Probability Matrices........................................................ 457

15.1.2 Stationary Distributions....................................................................... 459

15.1.3 Example: Markov Chain Models of Text...................................... 462

15.2 Estimating Properties of Markov Chains.................................................... 465

15.2.1 Simulation....................................................

.............................................. 465

15.2.2 Simulation Results as Random Variables..................................... 467

15.2.3 Simulating Markov Chains.................................................................. 469

15.3 Example: Ranking the Web by Simulating a Markov Chain................ 472

15.4 Hidden Markov Models and Dynamic Programming............................. 473

15.4.1 Hidden Markov Models........................................................................ 474

15.4.2 Picturing Inference with a Trellis.................................................... 474

15.4.3 Dynamic Programming for HMM's: Formalities....................... 478

15.4.4 &nb

sp; Example: Simple Communication Errors..................................... 478

15.5 You should............................................................................................................... 481

15.5.1 remember these definitions:.............................................................. 481

15.5.2 remember these terms......................................................................... 481

15.5.3 remember these facts:........................................................................... 481

15.5.4 be able to.................................................................................................... 481

V Some Mathematical Background &nb

sp; 484

16 Resources 485

16.1 Useful

Material about Matrices....................................................................... 485

16.1.1 The Singular Value Decomposition................................................. 486

16.1.2 Approximating A Symmetric Matrix............................................... 487

16.2 Some Special Functions..................................................................................... 489

16.3 Finding Nearest Neighbors............................................................................... 490

16.4 Entropy and Information Gain........................................................................ 493