Math for AI 106

Acknowledgement: This post is based mainly on Dr. Vinh-Dinh Nguyen’s presentation and slides and partly on on TA, STA, and peers’ responses from the course AIO2025 offered by AI VIETNAM.

Relevance: The audience of this lecture were those who have read Math for AI 105 or been familiar with probability and statistics. Note that only basic probability material is introduced here; we’ll pick up specific concepts when in need.

In today’s post, we’ll delve into some more descriptive statistics. We’ll also discuss some applications in AI including template matching.

Measure of Central Tendency

We previously talked about measure of central tendency in general and only briefly mentioned population and sample. We’ll discuss more in detail to distinguish the two concepts.

Population vs Sample: Mean, Variance, and Standard Deviation

Why not $n$?
The sample variance calculated by dividing by $n$ is often referred to as the biased/naive sample variance. These name refer to a major problem it causes.

The problem is that we would consistently underestimate the variance around the population mean. This happens because, on average across all possible samples drawn from the population, the naive sample variance is smaller than the population variance. That is, there is a disparity between the two

1. Let’s first understand what each side of this equality means.
   • The right-hand side is simply the population variance.
   \[\frac{1}{N} \sum (x_k - \mu)^2 = \sigma^2\]
   • The left-hand side is the expected value of all possible naive sample variances, particularly the mean in this case. We have the left-hand side can be rewritten as
   \[E \left( \frac{1}{n} \sum_{k=1}^{n} (x_k - \bar{x})^2 \right) = E(\tilde{s}^2).\]

   Here, we are not just comparing a single sample’s naive variance. Instead, we want to analyze the relation between the naive sample variance and the entire population variance overall, that is, from a global point of view. Our goal is to drag the sample variance to be close to the population variance as much as possible.

2. Before working out the detail, let’t see how this idea might work in the case of a single sample’s naive variance and why we need the average.

   • Claim: \(\sum_{i=1}^{n} (x_k - \bar{x})^2 < \sum_{i=1}^{N} (x_k - \mu)^2 \text{ for any } \bar{x}\).

   • Proof: According the claim, we want to minimize the sum of squared deviations. The common method is to figure out the absolute minimum, in particular local minimum in this case.

     Consider $f(a) = \sum_{k=1}^{n} (x_k - z)^2$. Differentiating the function, we have

     \[\begin{align*} \frac{df}{dz} = \frac{d}{dz} \sum_{k=1}^{n} (x_k - z)^2 = -2 \sum_{k=1}^{n} (x_k - z). \end{align*}\]

     The local minimum of the function is at

     \[\begin{align*} &-2 \sum_{k=1}^{n} (x_k - z) = 0 \Rightarrow \sum_{k=1}^{n} (x_k - z) = 0 \\ &\Rightarrow \sum_{k=1}^{n} x_k = \sum_{k=1}^{n} z = nz \Rightarrow z = \frac{\sum_{k=1}^{n} x_k}{n} = \bar{x}. \end{align*}\]

     This proves our claim, which suggests there might be a bias if we divide by $n$. So the denominator cannot be $n$.

     The graphs below display the idea using different sample sizes. As the sample size increases to the population size, the sample mean will get closer to the population mean.

We cannot conclude the claim for the variance since the denominators are different. However, we know that the denominator of the naive sample variance should be smaller. It can be $n - 1$, $n - 2$, $n - 3$, and so on.

Why not $n - 2$, $n - 3$, and so on?

1. Note: This is a proof of our main claim. You can read the next part if you think it may be pedantic.

   Since we want to compare with the population variance, we want to involve $\mu$ in the left side of \eqref{naive-inequality-problem}.

   \[\begin{align} (x_k - \bar{x})^2 &= ((x_k - \mu) - (\bar{x} - \mu))^2 \nonumber \\ &= (x_k - \mu)^2 - 2(x_k - \mu)(\bar{x} - \mu) + (\bar{x} - \mu)^2. \label{bar_x-to-mu} \end{align}\]

   Using \eqref{bar_x-to-mu}, we have

   \[\begin{align} \sum (x_k - \bar{x})^2 &= \sum (x_k - \mu)^2 - \sum 2(x_k - \mu)(\bar{x} - \mu) + \sum (\bar{x} - \mu)^2 \nonumber \\ &= \sum (x_k - \mu)^2 - 2(\bar{x} - \mu) \sum (x_k - \mu) + n (\bar{x} - \mu)^2. \label{sum-bar_x-to-mu} \end{align}\]

   We know that

   \[\begin{align} \label{x_k-mu} \sum (x_k - \mu) = \sum x_k - \sum \mu = n \bar{x} - n \mu = n (\bar{x} - \mu) \end{align}\]

   Substitute \eqref{x_k-mu} into \eqref{sum-bar_x-to-mu}. We have

   \[\begin{align} \sum (x_k - \bar{x})^2 &= \sum (x_k - \mu)^2 - 2(\bar{x} - \mu) n (\bar{x} - \mu) + n (\bar{x} - \mu)^2 \nonumber \\ &= \sum (x_k - \mu)^2 - 2n (\bar{x} - \mu)^2 + n (\bar{x} - \mu)^2 \nonumber \\ &= \sum (x_k - \mu)^2 - n (\bar{x} - \mu)^2. \label{result-bar_x-to-mu} \end{align}\]

   Substituting \eqref{result-bar_x-to-mu} into the left side of \eqref{naive-inequality-problem}, we have

   \[\begin{align} E \left( \frac{1}{n} \sum (x_k - \bar{x})^2 \right) &= E \left(\frac{1}{n} \left[\sum (x_k - \mu)^2 - n (\bar{x} - \mu)^2 \right] \right) \nonumber \\ &= E \left(\frac{1}{n} \left[\sum (x_k - \mu)^2 \right] \right) - E \left(\frac{1}{n} n (\bar{x} - \mu)^2 \right) \nonumber \\ &= \frac{1}{n} \sum [E ((x_k - \mu)^2)] - E ((\bar{x} - \mu)^2) \nonumber \\ &= \frac{1}{n} n [E ((x_k - \mu)^2)] - E ((\bar{x} - \mu)^2) \nonumber \\ &= [E ((x_k - \mu)^2)] - E ((\bar{x} - \mu)^2) \label{expectation-naive-sample-variance} \end{align}\]

   Assume all the samples are independent and identically distributed—having the same variance $\sigma^2$. By definition of the general variance and linear combination rule, we have

   \[\begin{align} \label{same-variance} E ((x_k - \mu)^2) = var(x_k) = \sigma^2 \end{align}\]

   and

   \[\begin{align} E ((\bar{x} - \mu)^2) &= var(\bar{X}) = var \left(\frac{1}{n} \sum x_k \right) = \frac{1}{n^2} \sum var (x_k) \nonumber \\ &= \frac{1}{n^2} \sum \sigma^2 = \frac{1}{n^2} n \sigma^2 = \frac{\sigma^2}{n}. \label{variance-of-sample-mean} \end{align}\]

   Replacing \eqref{same-variance} and \eqref{variance-of-sample-mean} into \eqref{expectation-naive-sample-variance}, we have

   \[\begin{align} \label{result-expectation-naive-sample-variance} E(\tilde{s}^2) = E ((\bar{x} - \mu)^2) = \sigma^2 - \frac{\sigma^2}{n} = \frac{n - 1}{n} \sigma^2. \end{align}\]

   Thus, \eqref{result-expectation-naive-sample-variance} indicates that $\tilde{s}^2$ gives an estimate $\frac{n - 1}{n} \sigma^2$ of the population variance $\sigma^2$. This estimation contributes to the bias or difference by a factor of $\frac{n - 1}{n}$ between the two variances claimed in \eqref{naive-inequality-problem}.

2. To correct this bias, we need to eliminate that exact factor by multiplying by its reciprocal. The result after correction is called (unbiased) sample variance, denoted $s^2$ as in the formula.

   \[s^2 = \frac{n}{n - 1} \tilde{s}^2 = \frac{n}{n - 1} \left( \frac{1}{n} \sum_{k=1}^{n} (x_k - \bar{x})^2 \right) = \frac{1}{n - 1} \sum_{k=1}^{n} (x_k - \bar{x})^2\]

Degrees of Freedom

In statistics, the degrees of freedom specify the number of independent variables used in the calculation of statstic—any quantity computed from values in a sample. In laymen terms, it is the number of information pieces required to know the rest of a sample which is not free to vary.

Think about $y = a_1x_1 + \cdots a_nx_n$. This equation involves $n$ independent variables, say $x_1, \cdots, x_n$, since the value of $y$ depends on them and can be inferred knowing their values. So the degree of freedom is n.

Let’s say if you toss a coin, there are two possible outcomes: head and tail. If you say it is not a tail, then it must be a head. This means head can be derived from the information on tail—if tail is independent, head is not. So there is 1 degree of freedom. The same goes for doing this experiment many times.

Another example is that if we know the sample mean and all values but one in a sample of size $n$. The unknown is completely determined by the $n - 1$ known values because the mean must stay fixed. So the sample has $n - 1$ degrees of freedom. This is another reason why the unbiased estimator of variance divides by $n - 1$ as the constraints are all we need to control the sample space.

Measure of Variability

Covariance

In the previous post, we talked about variance, which shows how dispersed the data values are from the center (mean). That’s an individual measurement.

If we want to understand the relationship between more than one single set of data, we need covariance. Covariance measures the linear relationship of two random variables, that is, how they change together.

DEOMONSTRAION

Even though covariance have quite a few disadvantages, it is a major computational stepping stone for the development of advanced statistical methods like correlation coefficient or principal component analysis.

Correlation

Correlation measures the strength and direction of a linear relationship between two variables. Basically, it describes how two variables are linked or associated with each other. Correlation does not mean one variable causes the other; there could be a third variable influencing both of them and thus this co-relationship.

Correlation can be expressed by either a scatter plot or a correlation coefficient. The table below shows characteristics of Pearson’s correlation coefficient. We’ll talk more about it in the next part as well.

DEOMONSTRAION

Correlation vs Regression
Consider $y = ax + b$. In this equation, $x$ is an independent variable while $y$ is dependent, that is, $y$ is affected/determined by $x$. This idea describe regression of two variables. Formally, regression describes a functional relationship between two variables—how one is dependent of the other. With such a property, we can use it to estimate the unknowns and make predictions based on assumptions.

• Correlation may imply regression since we can model a regression line but it might not be a good one.
• Regression can indicate correlation since regression how much one variable depends on the other.

Correlation vs Causation
Causation indicates the cause and effect relationship between two variables.

• Correlation does not imply causation.
• Causation may imply correlation since that one variable causes the other means we can expect some correlation. Due to various factors, the correlation might not be clear.

The figure below illustrates a high correlation between icecream sales and swimming activity throughout the year. But it is wrong to conclude the sales is the reason for swimming activity or vice versa.

In practice, it can sometimes be unethical to force researches on causality, so researchers tend to use correlation to conclude if there is a relationship between events. Take smoking and lung cancer or domestic violence and mental illness for example.

Regression vs Causation

• Regression does not imply causation.
• Causation only implies regression if the relationship is linear and quantifiable.

Correlation Coefficient

Some common correlation coefficients are Pearson’s r, Spearman’s rho, Point-biserial, Cramer’s V (Cramer’s $\varphi$), and Kendall’s tau. We’ll only go over Pearson’r in this post.

Earlier, we noted that Pearson’s r is insensitive to scaled data. This mathematically means

as

and

Computers often represent correlation as a 2-by-2 matrix.

Practice Exercises

Exercise 1: Use a package in NumPy to compute the covariance between sets of data in the picture.

Exercise 2: Prove the three equations that show Pearson'r is sensitive to scaled data.
Exercise 3: Write a function to compute Pearson's r in four ways (expected value, data points, NumPy package, and Scipy package) and test it with X = [7, 18, 29, 2, 10, 9, 9] and Y = [1, 6, 12, 8, 6, 21, 10].
Exercise 4: For exercise 3, what is noteworthy about the results using pacakges?
Exercise 5: What can you say if two random variables have correlation being 1?
Hints: Property of correlation coefficient.

Applications in AI

Traffic Sign Matching

In Math for AI 102, we discussed some image matching applications. We can use two following concepts to check which images in a given set are most similar.

• absolute difference / distance
• cosine similarity

In addition, we can apply the correlation concept to handle the same situation. It is not only insensitive to scaled data in \eqref{corr-coeff-scale-invariant} like cosine similarity but invariant to brightness shift in \eqref{corr-coeff-brightness-shift-invariant} as well. This linear change insusceptibility in \eqref{corr-coeff-linear-change-invariant} facilitates correlation coefficient to perform well on the same images of different brightness.

DEOMONSTRAION

Image Processing: Template Matching

Template matching is a technique used to find a portion of an image that matches a template image.

We can use all three concepts to resolve this kind of problem. But we know absolute difference and cosine similarity both have more shortcomings compared to correlation coefficient which we’ll use here.

1. It’s recommended to work with grayscale version of images.
2. Since we already have a template, we can consider it as a sliding window to run all over the input image.
3. At each step, we can compute and store the correlation coefficient between the template and the checking portion in a correlation map.
4. The highest value give our matching.
5. Take the coordinates of the matching portion to highlight it on the original image.

We can also visualize the correlation map by representing it with colors.

# template matching

import cv2
import numpy as np
from matplotlib import pyplot as plt

# Load image and convert to grayscale
image = cv2.imread('image.png',1)
gray  = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)

template = cv2.imread('template.png',0)
w, h = template.shape[::-1]

# Apply template Matching
corr_map = cv2.matchTemplate(gray, template, cv2.TM_CCOEFF_NORMED)
min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(corr_map) 

# take minimum
top_left = max_loc
bottom_right = (top_left[0] + w, top_left[1] + h)

# draw a bounding box on the input image
cv2.rectangle(image, top_left, bottom_right, (0, 255, 0), 2)

# save corr map in grayscale
corr_map = (corr_map+1.0)*127.5
corr_map = corr_map.astype('uint8') 
cv2.imwrite('corr_map_grayscale.png', corr_map)

# applyColorMap
corr_map = cv2.applyColorMap(corr_map, cv2.COLORMAP_JET)

# save results
cv2.imwrite('corr_map_color.png', corr_map)
cv2.imwrite('result.png', image)

FAQ

Here are some good questions asked during class. The answers to these questions came from either some admin, TA, STA, or members of AIO2025.