DISCRETE PROBABILITY DISTRIBUTIONS
CONTENTS 1 PROBABILITY AND STATISTICS: AN INTRODUCTION 1 1 INTRODUCTION THE INTERPLAY BETWEEN PROBABILITY, STATISTICS, AND MACHINE LEARNING CHAPTER ORGANIZATION 1 2 REPRESENTING DATA NUMERIC MULTIDIMENSIONAL DATA CATEGORICAL AND MIXED ATTRIBUTE DATA 1 3 SUMMARIZING AND VISUALIZING DATA 1 4 THE BASICS OF PROBABILITY AND PROBABILITY DISTRIBUTIONS POPULATIONS VERSUS SAMPLES MODELING POPULATIONS WITH SAMPLES HANDING DEPENDENCE IN DATA SAMPLES 1 5 HYPOTHESIS TESTING 1 6 BASIC PROBLEMS IN MACHINE LEARNING CLUSTERING CLASSI?CATION AND REGRESSION MODELING OUTLIER DETECTION 1 7 SUMMARY 1 8 FURTHER READING 1 9 EXERCISES 2 SUMMARIZING AND VISUALIZING DATA 2 1 INTRODUCTION 2 2 SUMMARIZING DATA UNIVARIATE SUMMARIZATION MULTIVARIATE SUMMARIZATION 2 3 DATA VISUALIZATION UNIVARIATE VISUALIZATION MULTIVARIATE VISUALIZATION 2 4 APPLICATIONS TO DATA PREPROCESSING UNIVARIATE PREPROCESSING METHODS WHITENING: A MULTIVARIATE PREPROCESSING METHOD 2 5 SUMMARY 2 6 FURTHER READING 2 7 EXERCISES 3 PROBABILITY BASICS AND RANDOM VARIABLES 3 1 INTRODUCTION 3 2 SAMPLE SPACES AND EVENTS 3 3 THE COUNTING APPROACH TO PROBABILITIES 3 4 SET-WISE VIEW OF EVENTS 3 5 CONDITIONAL PROBABILITIES AND INDEPENDENCE 3 6 THE BAYES RULE THE OBSERVABILITY PERSPECTIVE: POSTERIORS VERSUS LIKELIHOODS 3 7 THE BASICS OF PROBABILITY DISTRIBUTIONS CLOSED-FORM VIEW OF PROBABILITY DISTRIBUTIONS CONTINUOUS DISTRIBUTIONS MULTIVARIATE PROBABILITY DISTRIBUTIONS 3 8 DISTRIBUTION INDEPENDENCE AND CONDITIONALS INDEPENDENCE OF DISTRIBUTIONS CONDITIONAL DISTRIBUTIONS EXAMPLE: A SIMPLE 1-DIMENSIONAL KNOWLEDGE-BASED BAYES CLASSI?ER 3 9 SUMMARIZING DISTRIBUTIONS EXPECTATION AND VARIANCE DISTRIBUTION COVARIANCE USEFUL MULTIVARIATE PROPERTIES UNDER INDEPENDENCE 3 10 COMPOUND DISTRIBUTIONS 3 10 1 TOTAL PROBABILITY RULE IN CONTINUOUS HYPOTHESIS SPACES 3 10 2 BAYES RULE IN CONTINUOUS HYPOTHESIS SPACES 3 11 FUNCTIONS OF RANDOM VARIABLES (*) 3 11 1 DISTRIBUTION OF THE FUNCTION OF A SINGLE RANDOM VARIABLE 3 11 2 DISTRIBUTION OF THE SUM OF RANDOM VARIABLES 3 11 3 GEOMETRIC DERIVATION OF DISTRIBUTIONS OF FUNCTIONS 3 12 SUMMARY 3 13 FURTHER READING 3 14 EXERCISES 4 PROBABILITY DISTRIBUTIONS 4 1 INTRODUCTION 4 2 THE UNIFORM DISTRIBUTION 4 3 THE BERNOULLI DISTRIBUTION 4 4 THE CATEGORICAL DISTRIBUTION 4 5 THE GEOMETRIC DISTRIBUTION 4 6 THE BINOMIAL DISTRIBUTION 4 7 THE MULTINOMIAL DISTRIBUTION 4 8 THE EXPONENTIAL DISTRIBUTION 4 9 THE POISSON DISTRIBUTION 4 10 THE NORMAL DISTRIBUTION 4 10 1 MULTIVARIATE NORMAL DISTRIBUTION: INDEPENDENT ATTRIBUTES 4 10 2 MULTIVARIATE NORMAL DISTRIBUTION: DEPENDENT ATTRIBUTES 4 11 THE STUDENT’S T-DISTRIBUTION 4 12 THE ?2-DISTRIBUTION 4 12 1 APPLICATION: MAHALANOBIS METHOD FOR OUTLIER DETECTION 4 13 MIXTURE DISTRIBUTIONS: THE REALISTIC VIEW 4 13 1 WHY MIXTURES ARE UBIQUITOUS: A MOTIVATING EXAMPLE 4 13 2 THE BASIC GENERATIVE PROCESS OF A MIXTURE MODEL 4 13 3 SOME USEFUL RESULTS FOR PREDICTION 4 13 4 THE CONDITIONAL INDEPENDENCE ASSUMPTION 4 14 MOMENTS OF RANDOM VARIABLES (*) 4 14 1 CENTRAL AND STANDARDIZED MOMENTS 4 14 2 MOMENT GENERATING FUNCTIONS 4 15 SUMMARY 4 16 FURTHER READING 4 17 EXERCISES 5 HYPOTHESIS TESTING AND CON?DENCE INTERVALS 5 1 INTRODUCTION 5 2 THE CENTRAL LIMIT THEOREM 5 3 SAMPLING DISTRIBUTION AND STANDARD ERROR 5 4 THE BASICS OF HYPOTHESIS TESTING CON?DENCE INTERVALS WHEN POPULATION STANDARD DEVIATIONS ARE NOT AVAILABLE THE ONE-TAILED HYPOTHESIS TEST 5 5 HYPOTHESIS TESTS FOR DI?ERENCES IN MEANS UNEQUAL VARIANCE T-TEST EQUAL VARIANCE T-TEST PAIRED T-TEST 5 6 ?2-HYPOTHESIS TESTS STANDARD DEVIATION HYPOTHESIS TEST ?2-GOODNESS-OF-FIT TEST INDEPENDENCE TESTS 5 7 ANALYSIS OF VARIANCE (ANOVA) 5 8 MACHINE LEARNING APPLICATIONS OF HYPOTHESIS TESTING EVALUATING THE PERFORMANCE OF A SINGLE CLASSI?ER COMPARING TWO CLASSI?ERS ?2-STATISTIC FOR FEATURE SELECTION IN TEXT FISHER DISCRIMINANT INDEX FOR FEATURE SELECTION FISHER DISCRIMINANT INDEX FOR CLASSI?CATION (*) 5 9 SUMMARY 5 10 FURTHER READING 5 11 EXERCISES 6 RECONSTRUCTING PROBABILITY DISTRIBUTIONS FROM DATA 6 1 INTRODUCTION 6 2 MAXIMUM LIKELIHOOD ESTIMATION COMPARING LIKELIHOODS WITH POSTERIORS 6 3 RECONSTRUCTING COMMON DISTRIBUTIONS FROM DATA THE UNIFORM DISTRIBUTION THE BERNOULLI DISTRIBUTION THE GEOMETRIC DISTRIBUTION THE BINOMIAL DISTRIBUTION THE MULTINOMIAL DISTRIBUTION THE EXPONENTIAL DISTRIBUTION THE POISSON DISTRIBUTION THE NORMAL DISTRIBUTION MULTIVARIATE DISTRIBUTIONS WITH DIMENSION INDEPENDENCE 6 3 10 GAUSSIAN DISTRIBUTION WITH DIMENSION DEPENDENCE 6 4 MIXTURE OF DISTRIBUTIONS: THE EM ALGORITHM 6 5 KERNEL DENSITY ESTIMATION 6 6 REDUCING RECONSTRUCTION VARIANCE VARIANCE IN MAXIMUM LIKELIHOOD ESTIMATION PRIOR BELIEFS WITH MAXIMUM A POSTERIORI (MAP) ESTIMATION KERNEL DENSITY ESTIMATION: ROLE OF BANDWIDTH 6 7 THE BIAS-VARIANCE TRADE-O? 6 8 POPULAR DISTRIBUTIONS USED AS CONJUGATE PRIORS (*) GAMMA DISTRIBUTION BETA DISTRIBUTION DIRICHLET DISTRIBUTION 6 9 SUMMARY 6 10 FURTHER READING 6 11 EXERCISES 7 REGRESSION 7 1 INTRODUCTION 7 2 THE BASICS OF REGRESSION INTERPRETING THE COE?CIENTS FEATURE ENGINEERING TRICK FOR DROPPING BIAS REGRESSION: A CENTRAL PROBLEM IN STATISTICS AND LINEAR ALGEBRA 7 3 TWO PERSPECTIVES ON LINEAR REGRESSION THE LINEAR ALGEBRA PERSPECTIVE THE PROBABILISTIC PERSPECTIVE 7 4 SOLUTIONS TO LINEAR REGRESSION CLOSED-FORM SOLUTION TO SQUARED-LOSS REGRESSION THE CASE OF ONE NON-TRIVIAL PREDICTOR VARIABLE SOLUTION WITH GRADIENT DESCENT FOR SQUARED LOSS GRADIENT DESCENT FOR L1-LOSS REGRESSION 7 5 HANDLING CATEGORICAL PREDICTORS 7 6 OVER?TTING AND REGULARIZATION CLOSED-FORM SOLUTION FOR REGULARIZED FORMULATION SOLUTION BASED ON GRADIENT DESCENT LASSO REGULARIZATION 7 7 A PROBABILISTIC VIEW OF REGULARIZATION 7 8 EVALUATING LINEAR REGRESSION EVALUATING IN-SAMPLE PROPERTIES OF REGRESSION OUT-OF-SAMPLE EVALUATION 7 9 NONLINEAR REGRESSION INTERPRETABLE FEATURE ENGINEERING EXPLICIT FEATURE ENGINEERING WITH SIMILARITY MATRICES IMPLICIT FEATURE ENGINEERING WITH SIMILARITY MATRICES 7 10 SUMMARY 7 11 FURTHER READING 7 12 EXERCISES 8 CLASSI?CATION: A PROBABILISTIC VIEW 8 1 INTRODUCTION 8 2 GENERATIVE PROBABILISTIC MODELS CONTINUOUS NUMERIC DATA: THE GAUSSIAN DISTRIBUTION BINARY DATA: THE BERNOULLI DISTRIBUTION SPARSE NUMERIC DATA: THE MULTINOMIAL DISTRIBUTION PLATE DIAGRAMS FOR GENERATIVE PROCESSES 8 3 LOSS-BASED FORMULATIONS: A PROBABILISTIC VIEW LEAST-SQUARES CLASSI?CATION LOGISTIC REGRESSION MULTINOMIAL LOGISTIC REGRESSION 8 4 BEYOND CLASSI?CATION: ORDERED LOGIT MODEL MAXIMUM LIKELIHOOD ESTIMATION FOR ORDERED LOGIT 8 5 SUMMARY 8 6 FURTHER READING 8 7 EXERCISES 9 UNSUPERVISED LEARNING: A PROBABILISTIC VIEW 9 1 INTRODUCTION 9 2 MIXTURE MODELS FOR CLUSTERING 9 3 MATRIX FACTORIZATION THE SQUARED LOSS MODEL PROBABILISTIC LATENT SEMANTIC ANALYSIS LOGISTIC MATRIX FACTORIZATION GRADIENT DESCENT STEPS FOR LOGISTIC MATRIX FACTORIZATION 9 4 OUTLIER DETECTION THE MAHALANOBIS METHOD: A PROBABILISTIC VIEW OF WHITENING MIXTURE MODELS IN OUTLIER DETECTION MATRIX FACTORIZATION FOR OUTLIER DETECTION 9 5 SUMMARY 9 6 FURTHER READING 9 7 EXERCISES 10 DISCRETE STATE MARKOV PROCESSES 10 1 INTRODUCTION 10 1 1 CHAPTER ORGANIZATION 10 2 MARKOV CHAINS 10 2 1 STEADY-STATE BEHAVIOR OF MARKOV CHAINS 10 2 2 TRANSIENT BEHAVIOR OF MARKOV CHAINS 10 2 3 PERIODIC MARKOV CHAINS 10 2 4 ERGODICITY 10 2 5 DI?ERENT CASES OF ERGODICITY AND NON-ERGODICITY 10 2 6 PROPERTIES AND APPLICATIONS OF NON-ERGODIC MARKOV CHAINS 10 2 7 PROBABILITIES OF ABSORBING OUTCOMES 10 2 8 THE VIEW FROM MATRIX ALGEBRA (*) 10 3 MACHINE LEARNING APPLICATIONS OF MARKOV CHAINS 10 3 1 PAGERANK 10 3 2 APPLICATION TO VERTEX CLASSI?CATION 10 4 MARKOV CHAINS TO GENERATIVE MODELS 10 5 HIDDEN MARKOV MODELS 10 5 1 FORMAL DE?NITION AND TECHNIQUES FOR HMMS 10 5 2 EVALUATION: COMPUTING THE FIT PROBABILITY FOR OBSERVED SEQUENCE 10 5 3 EXPLANATION: DETERMINING THE MOST LIKELY STATE SEQUENCE FOR OB- SERVED SEQUENCE 10 5 4 TRAINING: BAUM-WELCH ALGORITHM 10 6 APPLICATIONS OF HIDDEN MARKOV MODELS 10 6 1 MIXTURE OF HMMS FOR CLUSTERING 10 6 2 OUTLIER DETECTION 10 6 3 CLASSI?CATION 10 7 SUMMARY 10 8 FURTHER READING 10 9 EXERCISES 11 PROBABILISTIC INEQUALITIES AND APPROXIMATIONS 11 1 INTRODUCTION 11 1 1 CHAPTER ORGANIZATION 11 2 JENSEN’S INEQUALITY 11 3 MARKOV AND CHEBYCHEV INEQUALITIES 11 4 APPROXIMATIONS FOR SUMS OF RANDOM VARIABLES 11 4 1 THE CHERNO? BOUND 11 4 2 THE NORMAL APPROXIMATION TO THE BINOMIAL DISTRIBUTION 11 4 3 THE POISSON APPROXIMATION TO THE BINOMIAL DISTRIBUTION 11 4 4 THE HOE?DING INEQUALITY 11 5 TAIL INEQUALITIES VERSUS APPROXIMATION ESTIMATES 11 6 SUMMARY 11 7 FURTHER READING 11 8 EXERCISES REFERENCES