[K-MOOC] Introductory Mathematics for Artificial Intelligence
Translated by
Sang-Gu LEE with Youngju NIELSEN, Yoonmee HAM
from the original Korean text written by
Sang-Gu LEE with Jae Hwa LEE, Yoonmee HAM, Kyung-Eun PARK
Part Ⅱ. AI and Matrix
5. Orthogonal Projection and Least Squares Problem
The least-squares method is the most intuitive way to obtain the best fit curve representing the data patterns.
Let's find out how we can get the best possible solution using the method of least squares (curve fitting).
5.1 Least Squares Problem
5.2 The meaning of the least squares problem
5.3 Orthogonal projection and least squares solution
5.4 Curve fitting
5.1 Least Squares Problem
Consider 4 points in the 
-plane (2-dimensional data).
We can see the left graph with 
and 
in the below figure. We can make the relationship between 
and 
by drawing a straight line. It is quite intuitive.
The least-squares method can be used to find out a straight line that best represents the given data. The straight line obtained is called
<the least-squares line> or <the best fit line>.
[Figure 1]
Let's consider the simplest case of solving the best possible straight line 
to describe the given data 
. It is finding the linear function
that best fits 
. The ideal situation is to find the 
-intercept 
and slope 
that satisfies 
for all data 
.
We can find out the solution using a system of linear equations in matrix form with two unknowns 
and 
as following.
|
Data |
|
Linear function |
System of linear equations |
Matrix Form |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
||
|
|
|
|
[Table 1]
When we have only two data points, then it will be easy to find 
and 
for 
. If we have more than two data points,
this modeling requires us to use a linear system of equations. We usually use a larger number of data to find the best possible curve fitting.
As a result, we end up with a larger number of equations than the number of unknowns. In this case, we do not expect 
to have a (unique) solution 
.
So, we try to find an approximate 
that minimizes the distance between 
and 
,
.
We will try to obtain a straight line with the least error even though it does not pass all four points. Mathematically, it means 
.
This problem is called <least squares problem> and 
is called the optimal solution (or the least square solution) 
even though
might not satisfy 
.
5.2 Meaning of the least-squares problem
Let 
be the value obtained by inputting 
into 
from each data point 
. There exists an error for some 
when 
and 
are not the same.
If 
and 
are the same for all 
, then the line 
has a unique solution. Since there are cases where 
and 
are not the same,
in other words, 
is not all zero, we will try to find 
, and 
that minimize the error. Adding all the squared errors for all the given data
gives the following error function 
.
The error 
is eventually equal to the square of the distance between 
and 
. It is easy to see how a norm and an inner product are related to errors.
Solving the least-squares problem is solving a problem of finding 
that minimizes the error function 
. The optimal solution to this problem is
the least-squares solution 
. To find the least-squares solution, we need the concept of <projection>.
5.3 Projection and least-squares solution https://youtu.be/xGZPBT4Q4t4
To understand the least-squares problem, we need to know about a projection. Let's consider the problem of finding 
satisfying the following.
where 
is a real number
In other words, this is the problem of finding 
that minimizes the distance between the vector 
and the straight line containing 
where 
is the scalar.
[Figure 2]
We can see that
represents a distance between 
and 
as shown in [Figure 2]. Intuitively, the shortest distance can be obtained
when 
and 
. Such 
is a solution for 
and the vector 
is called the projection of 
onto 
.
Since 
, this 
can be obtained as follows:
Find the projection of 
onto 
, for 
, 
.
We can solve the least-squares problem 
in [Table 1], similar to the problem of determining 
that minimizes the difference
between the projection (of 
onto 
) and the vector 
. For this purpose, let 
,
be the first and second column vector of 
, respectively.
Then, we have 
.
Hence, the least-squares problem is related to the column space of column vectors of 
. The least-square problem can be interpreted as
a problem of finding a projection.
The plane 
in [Figure 3] is a set of images given by 
. As shown in this figure, it can be understood as
'the problem of obtaining 
and 
that gives the minimal distance between the plane containing 
and 
and the vector 
.'
[Figure 3]
As shown in [Figure 3], 
is the length of the marked real line for the values of 
and 
. It is easy to see that the vector
with the shortest distance from 
to 
can be obtained by 
when 
and 
.
Such 
and 
give the solution for 
. The conditions 
and 
imply
that 
and give 
.
☞ Note If 
for a data set 
, then 
is always invertible (Vandermonde determinant) and 
can be found easily. https://steemit.com/kr-math/@beoped/vandermonde-determinant
Find a least-squares solution of 
in [Table 1].
Solution. For 
, 
, 
in [Table 1], the least-squares solution of 
is 
that 
.
[Fig. 4]
Answer. The least square line 
where 
. ■
We will study a ‘process of finding a least-squares curve(line)’ called the ‘linear regression’ in the statistics section later.
5.4 Finding a suitable curve for data (Curve Fitting)
Consider 4 points in the 
-plane (2-dimensional data).
Just like we did in section 5.3, we can also find the best fit curve (a quadratic approximation of 
) to describe data 
.
Since all 4 points of data should satisfy the quadratic equation 
, they can be expressed in a matrix form as follows.
[Fig. 5]
|
data |
|
quadratic function |
system of linear equations |
matrix representation |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
||
|
|
|
|
[Table 3]
Simply, we only need to find a vector 
for 
that 
. To obtain this quadratic function for a data set,
we will have a system of equations with no unique solution. So we will have a least-squares problem 
to solve.
The following function 
represents an error for this problem.
We can find 
.
So the least-squares curve is 
. ■
Similarly, we now can find cubic and higher approximations for any given 
-points.
|
◩ Open Problem 14 |
Discuss the conditions for the existence of the inverse matrix of 
and find a least-squares solution for the given 6-points in 
to make the curve of 
.
Lab
- Least squares problem: http://matrix.skku.ac.kr/2020-math4AI/LSS/
- Projection:https://www.geogebra.org/m/ewP9ybUP
Copyright @ 2021 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
