1 Normal distribution

11 Univariate

A random variable is said to have a normal distribution with mean and variance if its probability density function (pdf) is given by

where is the mean and is the variance of the distribution. More compactly, it can be written as

12 Uncorrelated multivariate

A random vector is said to have an uncorrelated multivariate normal distribution with mean and variances if the pdf of every random component of is given by

where is the mean and is the variance of the -th component. The uncorrelated multivariate normal distribution is a special case of the general multivariate normal. When components are uncorrelated, the covariance matrix is diagonal, which simplifies many calculations.

All components of are assumed to be independent, so the joint pdf of is the product of the pdfs of its components:

13 Covariance matrix

All variance parameters can be combined into a covariance matrix . The covariance matrix is a symmetric positive definite matrix that describes the covariance between the components of .

Here, the covariance matrix is diagonal (all off-diagonal elements are zero), because we assumed that the components of are uncorrelated, i.e., for all .

The pdf of the multivariate normal distribution can be written in terms of the covariance matrix:

For a sample , the variance is the average of the squared differences from the mean:

Given another sample , the co-variance between two samples is characterized by how much they vary together:

Both per sample variance and two samples covariance can be combined into a covariance matrix.

It will be shown below that this is equivalent to the covariance matrix for a sample of 2D vectors .

The covariance matrix above is a diagonal matrix, but in general, it’s a symmetric positive definite matrix that describes the covariance between the components of :

If we substitute the non-diagonal covariance matrix into the pdf, we get the general form of the multivariate normal distribution.

To characterize co-variance of multiple samples

all together, we combine them into one sample of -dimensional data:

The covariance between any two samples and is

Generally, for a sample of vectors :

which resembles the variance but in multiple dimensions.

Technically, each component of is the covariance between the corresponding components

The term is the generalized variance.

14 Mahalanobis distance

The distance between a point and the distribution can be measured using the Mahalanobis distance.

Quadratic form is a scalar function of a vector that can be expressed as a weighted sum of the squares of the components of :

These weights can be gathered into a matrix , and the quadratic form can be written as a matrix product:

The premise is that the covariance matrix captures the correlations between the components of . The Mahalanobis distance is a measure of how many standard deviations away a point is from the mean , taking into account the correlations between the components of .

We can define a quadratic form

The square root of this quadratic form is the Mahalanobis distance between a point and the distribution .

2 Multivariate Normal Distribution

21 General form

The probability density function of the multivariate normal distribution is given by:

where:

• is the random vector
• is the mean vector
• is the covariance matrix (symmetric positive definite)
• is the generalized variance
• is a quadratic form
• is the Mahalanobis distance between a point and the distribution

In compact notation, this is written as:

22 Uncorrelated components

When the components of the distribution are uncorrelated:

This has geometric implications - the axes of the probability density ellipsoid are parallel to the coordinate axes.

The covariance matrix simplifies to a diagonal matrix:

For uncorrelated components, the multivariate normal pdf can be expressed as a product of univariate normal pdfs:

This factorization enables simpler parameter estimation methods.

23 Decorrelation transformation

Decorrelation is a critical preprocessing step in many machine learning applications. It simplifies the data by removing linear dependencies between features.

For correlated components, we need to find a transformation that makes the components uncorrelated. When components of a multivariate normal distribution are correlated, the covariance matrix is not diagonal.

To decorrelate the components:

1. Apply spectral decomposition to the covariance matrix (a special case of SVD for symmetric matrices):

2. The quadratic form can be rewritten as:

3. Define the decorrelation transformation:

4. The transformed parameters are:

5. To transform parameters back to the original space:

For orthogonal (rotation) matrices:

3 Parameter Estimation for Normal Distribution

31 Maximum likelihood estimation

When a sample is generated from a Gaussian distribution, we can estimate its parameters using maximum likelihood estimation:

The MLE estimates are asymptotically unbiased and efficient, making them optimal for large samples. For smaller samples, however, the covariance estimate is biased.

32 Multicollinearity issues

Multicollinearity is a statistical phenomenon where two or more predictor variables in a model are highly correlated. This creates redundant information that doesn’t contribute uniquely to the model’s explanatory power.

When estimating parameters from data, multicollinearity can cause problems:

• The sample covariance matrix is constructed from rank-1 matrices, so
• If the number of features exceeds the sample size, will be singular ()
• A singular covariance matrix cannot be inverted, making it impossible to evaluate the density function

Solutions to multicollinearity include:

1. Reducing the number of features through feature selection methods (PCA, SFS, etc.)
2. Increasing the sample size
3. Adding regularization to the covariance matrix:

4. Assuming uncorrelated features (diagonal covariance matrix)

4 Non-parametric Density Estimation

41 Parametric vs non-parametric approaches

The choice between parametric and non-parametric methods involves a bias-variance tradeoff. Parametric methods generally have higher bias but lower variance, while non-parametric methods have lower bias but higher variance.

Parametric methods for density estimation assume a specific distribution shape (e.g., normal), which simplifies calculations and requires less data. However, they can be inaccurate if the actual data distribution differs significantly from the assumed form and are limited in capturing complex structures.

Non-parametric methods offer greater flexibility and can provide more accurate estimates for complex and multimodal distributions without assuming a specific form. However, they typically require larger data sets, are more computationally intensive, and their results are harder to interpret due to the lack of explicit parameters.

42 Empirical density estimator

The simplest non-parametric estimator for a probability density function is:

and for the cumulative distribution function:

where:

• is a pdf/pmf
• is a cdf
• is a point from the sample
• is a new point

43 Histogram density estimator

A more practical approach divides the feature space into bins:

and for the CDF:

where:

• is the partition into bins
• is the bin size
• is the specific bin containing
• iff allows ordering of bins
• is the number of bins for the th feature
• is the corresponding bin width

44 Window averaging

The choice of window width is critical in kernel density estimation and presents the classic bias-variance tradeoff.

Instead of bins, we can use a window function centered at each data point:

and for the CDF:

where:

• is the window width (radius)
• means all components are less or equal
• means componentwise addition
• is a kernel function

5 Kernel Density Estimation

51 Parzen-Rosenblatt window method

Kernel density estimation is often called the Parzen-Rosenblatt window method after its developers Emanuel Parzen and Murray Rosenblatt.

There are two main approaches for multivariate density estimation:

1. Product kernel approach (assumes local independence):

2. Multivariate kernel approach:

where:

• is a kernel function satisfying:

  • For all : (non-increasing)

52 Kernel functions

Several standard kernel functions are used in practice:

• Epanechnikov kernel:
• Quartic (biweight) kernel:
• Triangle kernel:
• Gaussian kernel:
• Uniform kernel:

The Epanechnikov kernel is theoretically optimal in terms of mean integrated squared error, but in practice, the choice of kernel usually has less impact than the bandwidth selection.

53 Bandwidth selection

The optimal bandwidth can be found by minimizing the cross-validation criterion:

where:

• is the window width (radius)
• is the estimated density function
• The notation indicates leave-one-out cross-validation

Cross-validation provides a data-driven approach to bandwidth selection, avoiding both oversmoothing and undersmoothing.

This approach:

1. Excludes each point from the training set
2. Estimates the density at that point using the remaining points
3. Minimizes the negative log-likelihood of these estimates

54 Relationship to other methods

The connection between these methods highlights the unified theoretical foundation underlying non-parametric approaches.

Kernel methods form a common framework that includes:

1. Density estimation:
2. Classification (Parzen window):
3. Regression (Nadaraya-Watson):

In these methods:

• is a distance function
• is a similarity function (larger distance means smaller similarity)

6 Mixture Models

61 Definition

Mixture models provide a flexible framework that can approximate any continuous distribution with arbitrary precision.

A mixture model combines multiple probability distributions:

where:

• indicates data generated by different distributions
• is the probability of being generated by the th distribution
• is the pdf/pmf of the th distribution

62 Parameter estimation

The log-likelihood function for a mixture model is:

where:

• are constraints
• is the pdf/pmf of the th distribution

Direct optimization is challenging because the logarithm of a sum doesn’t simplify easily. The EM algorithm provides an iterative solution.

63 Fixed point method

The fixed point method underlies many iterative algorithms in machine learning, including the EM algorithm.

Before introducing EM, it’s helpful to understand the fixed point iteration method:

This method converges if:

where is the fixed point such that .

7 Expectation-Maximization Algorithm

71 EM algorithm

The EM algorithm was formalized by Dempster, Laird, and Rubin in 1977, though similar approaches had been used earlier.

The EM algorithm iteratively optimizes parameters and for mixture components. Each iteration consists of two steps:

1. Expectation step (E-step): Calculate the posterior probability for each data point:

2. Maximization step (M-step): Update parameters: