[mathematical basis of machine learning] (I) linear algebra (Part 1 +)

【 The mathematical basis of machine learning 】（ One ） linear algebra (Linear Algebra)（ On ）

2 linear algebra (Linear Algebra)（ On +）

2.3 The solution of linear equations

Earlier, we introduced the general form of equations , namely ：
$$\begin{array}{rl}{a}_{11}{x}_1+\cdots +a_{1n}{x}_n& =b_1\\ & ⋮\\ a_{m1}{x}_1+\cdots +a_{mn}{x}_n& =b_m\end{array}$$

among $a_{ij}\in \mathbb{R}$,$b_i\in \mathbb{R}$ Is a known constant ,$x_j$ Is an unknown quantity ,$i=1,\dots ,m,j=1,\dots ,n$. up to now , We see that matrix can be used as a concise method to express linear equations , In this way, we can write the linear equations as $\mathbf{A}\mathbf{x}=\mathbf{b}$. Besides , We also define the basic matrix operations , Such as matrix addition and multiplication . below , We will focus on the solution of linear equations , An algorithm for finding the inverse of matrix is provided .

2.3.1 Special solution and general solution

Before discussing how to solve linear equations , Let's start with an example . Consider the system of equations

$$\left[\begin{array}{cccc}1& 0& 8& -4\\ 0& 1& 2& 12\end{array}\right]\left[\begin{array}{l}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right]=\left[\begin{array}{c}42\\ 8\end{array}\right](2.38)$$

This system of equations has two equations and four unknowns . therefore , Generally speaking , We can get an infinite number of solutions . The form of this system of equations is a minimalist form , The first two columns consist of a 0 And a 1 form .

Our goal is to find scalars $x_1,\dots ,x_4$, bring ${\sum }_{i=1}^4{x}_i{\mathbf{c}}_i=\mathbf{b}$, among ${\mathbf{c}}_i$ Is the first... Of the matrix $i$ Column ,$b$ Is the of the system of equations (2.38) The right side of the . For this system of equations , This can be done by taking the... In the first column 42 Times and the second column 8 Times the solution ：

$$\mathbf{b}=\left[\begin{array}{c}42\\ 8\end{array}\right]=42\left[\begin{array}{l}1\\ 0\end{array}\right]+8\left[\begin{array}{l}0\\ 1\end{array}\right]$$

therefore , One solution of the system of equations is $[42,8,0,0{]}^{\top }$, This solution is called Special solution (particular solution or special solution).

However , This is not the only solution to this system of linear equations . To get other solutions , We need to creatively use the columns of the matrix to Extraordinary ( non-trivial) Generate vectors in the same way $0$： The special solution is multiplied by the matrix of the system of equations , Then add... On both sides of the equation at the same time $0$ Does not affect the equation .

We use the first two columns （ Their form is very simple ） Represents the third column
$$\left[\begin{array}{l}8\\ 2\end{array}\right]=8\left[\begin{array}{l}1\\ 0\end{array}\right]+2\left[\begin{array}{l}0\\ 1\end{array}\right]$$

Then there are $0=8{\mathbf{c}}_1+2{\mathbf{c}}_2-1{\mathbf{c}}_3+0{\mathbf{c}}_4$, Get the solution ：$\left(x_1,x_2,x_3,x_4\right)=(8,2,-1,0)$. in fact , This solution is arbitrary ${\lambda }_1\in \mathbb{R}$ Scaling will produce $0$ vector , namely ：
$$\left[\begin{array}{llll}1& 0& 8& -4\\ 0& 1& 2& 12\end{array}\right]\left({\lambda }_1\left[\begin{array}{c}8\\ 2\\ -1\\ 0\end{array}\right]\right)={\lambda }_1\left(8c_1+2c_2-c_3\right)=0$$

similarly , We use the first two columns to represent the fourth column of the matrix in the system of equations , For any ${\lambda }_2\in \mathbb{R}$ Generate another set $0$ An extraordinary version of
$$\left[\begin{array}{llll}1& 0& 8& -4\\ 0& 1& 2& 12\end{array}\right]\left({\lambda }_2\left[\begin{array}{c}-4\\ 12\\ 0\\ -1\end{array}\right]\right)={\lambda }_2\left(-4{\mathbf{c}}_1+12{\mathbf{c}}_2-{\mathbf{c}}_4\right)=0$$

Liberate all together , All solutions of the equations are obtained , be called general solution (general solution), Expressed in the form of a set as ：
$$\left\{x\in {\mathbb{R}}^4:x=\left[\begin{array}{c}42\\ 8\\ 0\\ 0\end{array}\right]+{\lambda }_1\left[\begin{array}{c}8\\ 2\\ -1\\ 0\end{array}\right]+{\lambda }_2\left[\begin{array}{c}-4\\ 12\\ 0\\ -1\end{array}\right],{\lambda }_1,{\lambda }_2\in \mathbb{R}\right\}$$

remarks ：
The general solution of linear equations includes the following three steps ：

• (1) find $Ax=b$ Special solution of .
• (2) find $Ax=0$ All the solutions of .
• (3) Combine steps (1) and (2) Get the general solution .
• Note that neither the general solution nor the special solution is unique .

The linear equations in the above example are easy to solve , Because the matrix in the system of equations has a particularly simple form , This enables us to obtain the special solution and general solution through the surrogate test . However , The general equations will not be in this simple form .

Fortunately, , There is a constructive algorithm that can convert any system of linear equations into this particularly simple form ： Gauss elimination ( Gaussian elimination). The key of Gauss elimination method is the elementary transformation of linear equations , Convert the equations into a simple form . then , We can use the above three steps to solve the linear equations .

2.3.2 Elementary transformation

The key to solving linear equations is Elementary transformation (elementary transformations), It can keep the solution set unchanged , Transform the equations into simpler forms ：

• （1） Two equations （ The row of the matrix representing the system of equations ） In exchange for
• （2） equation ( That's ok ) Multiply by a constant $\lambda \in \mathbb{R}\backslash \{0\}$
• （3） Two equations ( That's ok ) The addition of

remarks ：（1）、（2）、（3） Can be combined .

example 2.6
about $a\in \mathbb{R}$, Find all solutions of the following equations ：
$$\begin{array}{rrrrrrrrccc}-2x_1& +& 4x_2& -& 2x_3& -& x_4& +& 4x_5& =& -3\\ 4x_1& -& 8x_2& +& 3x_3& -& 3x_4& +& x_5& =& 2\\ x_1& -& 2x_2& +& x_3& -& x_4& +& x_5& =& 0\\ x_1& -& 2x_2& & & -& 3x_4& +& 4x_5& =& a\end{array}$$

We first convert this system of equations into a compact matrix representation $\mathbf{A}\mathbf{x}=\mathbf{b}$. We no longer explicitly mention variables $\mathbf{x}$, It's about building Augmented matrix (augmented matrix)（ In the form of $[\mathbf{A}\mid \mathbf{b}]$）

We use vertical lines to separate the left and right sides of the equations .
$$\left[\begin{array}{rrrrrr}-2& 4& -2& -1& 4& -3\\ 4& -8& 3& -3& 1& 2\\ 1& -2& 1& -1& 1& 0\\ 1& -2& 0& -3& 4& a\end{array}\right]\begin{array}{l}\text{Swap with }{R}_3\\ \\ \text{Swap with }{R}_1\\ \end{array}$$

Swap the first line $R_1$ And the third line $R_3$ obtain ：

$$\left[\begin{array}{rrrrrr}1& -2& 1& -1& 1& 0\\ 4& -8& 3& -3& 1& 2\\ -2& 4& -2& -1& 4& -3\\ 1& -2& 0& -3& 4& a\end{array}\right]\begin{array}{l}\\ -4R_1\\ +2R_1\\ -R_1\end{array}$$

We use the transformation specified in the above formula （ for example , The above formula includes 2 Line minus four times 1 That's ok ） after , We get
$$\left[\begin{array}{rrrrrr}1& -2& 1& -1& 1& 0\\ 0& 0& -1& 1& -3& 2\\ 0& 0& 0& -3& 6& -3\\ 0& 0& -1& -2& 3& a\end{array}\right]$$
We use it $⇝$ To represent the elementary transformation of the augmented matrix .

$$\left[\begin{array}{rrrrrr}1& -2& 1& -1& 1& 0\\ 0& 0& -1& 1& -3& 2\\ 0& 0& 0& -3& 6& -3\\ 0& 0& -1& -2& 3& a\end{array}\right]\begin{array}{l}\\ \\ \\ -R_2-R_3\end{array}$$

$$⇝\left[\begin{array}{rrrrrr}1& -2& 1& -1& 1& 0\\ 0& 0& -1& 1& -3& 2\\ 0& 0& 0& -3& 6& -3\\ 0& 0& 0& 0& 0& a+1\end{array}\right]\begin{array}{l}\cdot (-1)\\ \cdot (-\frac{1}{3})\end{array}$$
$$⇝\left[\begin{array}{rrrrrr}1& -2& 1& -1& 1& 0\\ 0& 0& 1& -1& 3& -2\\ 0& 0& 0& 1& -2& 1\\ 0& 0& 0& 0& 0& a+1\end{array}\right]$$

This （ Augmentation ） The matrix now becomes a simple form —— Line ladder form （row-echelon form,REF）. Reduce this compact representation to an explicit representation , We get
$$\begin{array}{rrrrrrccccc}{x}_1& -& 2x_2& +& x_3& -& x_4& +& x_5& =& 0\\ & & & & x_3& -& x_4& +& 3x_5& =& -2\\ & & & & & & x_4& -& 2x_5& =& 1\\ & & & & & & & & 0& =& a+1\end{array}$$

Only when the $a=-1$ The equations have a solution . A special solution is ：
$$\left[\begin{array}{l}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right]=\left[\begin{array}{c}2\\ 0\\ -1\\ 1\\ 0\end{array}\right]$$

general solution ：
$$\left\{x\in {\mathbb{R}}^5:x=\left[\begin{array}{c}2\\ 0\\ -1\\ 1\\ 0\end{array}\right]+{\lambda }_1\left[\begin{array}{l}2\\ 1\\ 0\\ 0\\ 0\end{array}\right]+{\lambda }_2\left[\begin{array}{c}2\\ 0\\ -1\\ 2\\ 1\end{array}\right],{\lambda }_1,{\lambda }_2\in \mathbb{R}\right\}$$

below , We will introduce in detail a constructive method to obtain the special and general solutions of linear equations .

remarks ： Principal element and ladder structure

Yes Leading coefficient （leading coefficient, The first non-zero number from the left ） be called Principal component (Pivots ), And always strictly to the right of the principal element of the upper row . therefore , Any row ladder (row-echelon form) All equations have “ ladder (staircase)” structure .

Definition 2.6( Row ladder )

A matrix is Row ladder (row-echelon form) The matrix needs to meet ：

• All rows containing only zeros are at the bottom of the matrix ; Accordingly , All rows containing at least one non-zero element are at the top of rows containing only zero .
• Just look at non-zero lines , The first non-zero number from the left （ Also known as principal element or leading coefficient ） Always strictly to the right of the row principal above it .

remarks ： Basic and free variables

The variable corresponding to the principal element of the row ladder type is called Basic variables (basic variables), Other variables are called Free variable (free variables).

for example , about
$$\begin{array}{rrrrrrccccc}{x}_1& -& 2x_2& +& x_3& -& x_4& +& x_5& =& 0\\ & & & & x_3& -& x_4& +& 3x_5& =& -2\\ & & & & & & x_4& -& 2x_5& =& 1\\ & & & & & & & & 0& =& a+1\end{array}$$
$x_1,x_3,x_4$ Is the basic variable ,$x_2,x_5$ It's a free variable .

remarks ：( Seeking special solution )

When we need to determine a particular solution , The row ladder is convenient for us to solve . To do this , We use the principal component column to represent the right side of the system of equations , namely $\mathbf{b}={\sum }_{i=1}^P{\lambda }_i{\mathbf{p}}_i$, among ${\mathbf{p}}_i,i=1,\dots ,P$ The column of the primary element , That is, the main element column .

${\lambda }_i$ It's easy to be sure , We can Start with the rightmost primary column , One to the left Once certain .

In the previous example , We're trying to find ${\lambda }_1,{\lambda }_2,{\lambda }_3$, bring ：
$${\lambda }_1\left[\begin{array}{l}1\\ 0\\ 0\\ 0\end{array}\right]+{\lambda }_2\left[\begin{array}{l}1\\ 1\\ 0\\ 0\end{array}\right]+{\lambda }_3\left[\begin{array}{c}-1\\ -1\\ 1\\ 0\end{array}\right]=\left[\begin{array}{c}0\\ -2\\ 1\\ 0\end{array}\right]$$

From here , We find relatively intuitively ${\lambda }_3=1,{\lambda }_2=-1,{\lambda }_1=2$. For non principal Columns , We implicitly set its coefficient to 0. therefore , We get the special solution as ：$[2,0,-1,1,0{]}^{\top }$

remarks ： The simplest step

A system of equations is The simplest step (Reduced Row Echelon Form, Also known as row-reduced echelon form or row canonical form) Need to meet ：

• It's a row ladder
• Each principal element is 1
• The principal element is the only non-zero item in its column .

The simplest step of the line will be in the next 2.3.3 Section plays an important role , Because it allows us to directly determine the general solution of linear equations

remarks ： Gauss elimination

Gauss elimination (Gaussian elimination) It is an algorithm that transforms a system of linear equations into a row simplest ladder type through elementary transformation .

example 2.7 The simplest step

There are the following lines of the simplest ladder matrix ( bold 1 The main element )：
$$\mathbf{A}=\left[\begin{array}{ccccc}1& 3& 0& 0& 3\\ 0& 0& 1& 0& 9\\ 0& 0& 0& 1& -4\end{array}\right](2.49)$$

seek $\mathbf{A}\mathbf{x}=0$ The key to the solution of is the non principal element column , We need to express it as the of the primary column （ linear ） Combine ; The simplest ladder makes this relatively simple . We use the sum of multiples of the principal column on the left to represent the non principal column ：

The second column is the... Of the first column 3 times （ We can ignore the primary column to the right of the second column ）. therefore , In order to get $0$, We need to subtract the second column from three times the first column .

Now? , Let's look at the second non principal column —— The fifth column .

The fifth column can be composed of... Of the first principal column 3 times 、 Of the second principal column 9 times And the third principal column −4 times Express . We need to use the index of the primary column , And convert the fifth column to the... Of the first column 3 times 、 Second column （ Non principal column ） Of 0 times 、 The third column ( The second non principal column ) Of 9 Times and the fourth column -4 times （ That is, the third principal element column ） The sum of the , Then subtract the fifth column to get $0$. Last , You can solve this homogeneous system of equations .

All in all ,$\mathbf{A}\mathbf{x}=0,\mathbf{x}\in {\mathbb{R}}^5$ All solutions of are given by
$$\left\{\mathbf{x}\in {\mathbb{R}}^5:\mathbf{x}={\lambda }_1\left[\begin{array}{c}3\\ -1\\ 0\\ 0\\ 0\end{array}\right]+{\lambda }_2\left[\begin{array}{c}3\\ 0\\ 9\\ -4\\ -1\end{array}\right],{\lambda }_1,{\lambda }_2\in \mathbb{R}\right\}(2.50)$$

2.3.3 Minus-1 skill

below , We will introduce a practical technique to solve homogeneous linear equations $\mathbf{A}\mathbf{x}=0$ Solution $\mathbf{x}$, among $\mathbf{A}\in {\mathbb{R}}^{k\times n},\mathbf{x}\in {\mathbb{R}}^n$

First , We assume that $\mathbf{A}$ yes The simplest step , And there are no rows that contain only zeros , namely ：
$$\mathbf{A}=\left[\begin{array}{ccccccccccccccc}0& \cdots & 0& 1& \ast & \cdots & \ast & 0& \ast & \cdots & \ast & 0& \ast & \cdots & \ast \\ ⋮& & ⋮& 0& 0& \cdots & 0& 1& \ast & \cdots & \ast & ⋮& ⋮& & ⋮\\ ⋮& & ⋮& ⋮& ⋮& & ⋮& 0& ⋮& & ⋮& ⋮& ⋮& & ⋮\\ ⋮& & ⋮& ⋮& ⋮& & ⋮& ⋮& ⋮& & ⋮& 0& ⋮& & ⋮\\ 0& \cdots & 0& 0& 0& \cdots & 0& 0& 0& \cdots & 0& 1& \ast & \cdots & \ast \end{array}\right]$$

among $\ast$ Is a random real number ,$\mathbf{A}$ The first non-zero item of each line must be 1, All other items in the corresponding column must be 0.

Columns with principal elements $j_1,\dots ,j_k$（ Mark it in bold ） Is the standard unit vector $e_1,\dots ,e_k\in {\mathbb{R}}^k$. We add $n-k$ Expand the matrix to $n\times n$- matrix $\tilde{\mathbf{A}}$, The form of the line added by the extension is ：

$$\left[\begin{array}{lllllll}0& \cdots & 0& -1& 0& \cdots & 0\end{array}\right](2.52)$$

So the augmented matrix $\tilde{\mathbf{A}}$ The diagonal of contains 1 or -1. then , contain −1 The column as the principal element is a system of homogeneous equations $\mathbf{A}\mathbf{x}=0$ Solution . More precisely , These columns make up $\mathbf{A}\mathbf{x}=0$ Basis of solution space , We also call it kernel or zero space ( see 2.7.3 section ).

example 8 (Minus-1 Trick)
about (2.49) This simplest step (REF) matrix ：
$$\mathbf{A}=\left[\begin{array}{ccccc}1& 3& 0& 0& 3\\ 0& 0& 1& 0& 9\\ 0& 0& 0& 1& -4\end{array}\right]$$

Now let's add... Where the principal element is missing on the diagonal (2.52) Lines of form , Expand this matrix into a 5 × 5 Matrix
$$\tilde{\mathbf{A}}=\left[\begin{array}{ccccc}1& 3& 0& 0& 3\\ 0& -1& 0& 0& 0\\ 0& 0& 1& 0& 9\\ 0& 0& 0& 1& -4\\ 0& 0& 0& 0& -1\end{array}\right]$$

We can take $\tilde{\mathbf{A}}$ It contains... On the diagonal -1 Columns of , Get... Immediately $\mathbf{A}\mathbf{x}=0$ Solution ：
$$\left\{\begin{array}{l}x\in {\mathbb{R}}^5:\mathbf{x}={\lambda }_1\left[\begin{array}{c}3\\ -1\\ 0\\ 0\\ 0\end{array}\right]+{\lambda }_2\left[\begin{array}{c}3\\ 0\\ 9\\ -4\\ -1\end{array}\right],{\lambda }_1,{\lambda }_2\in \mathbb{R}\}\end{array}\right\}$$

And example 2.7 Same result for .

Seeking inverse

For calculation $\mathbf{A}\in {\mathbb{R}}^{n\times n}$ The inverse of ${\mathbf{A}}^{-1}$, We need to find satisfaction $\mathbf{A}\mathbf{X}={\mathbf{I}}_n$ Matrix $\mathbf{X}$.$\mathbf{X}={\mathbf{A}}^{-1}$. We can write it as a set of linear equations $\mathbf{A}\mathbf{X}={\mathbf{I}}_n$ And solve $\mathbf{X}=\left[{\mathbf{x}}_1|\cdots |{\mathbf{x}}_n\right]$. We use augmented matrix representation to represent this set of linear equations , And make the following transformation ：
$$\left[\mathbf{A}\mid {\mathbf{I}}_n\right]⇝\cdots ⇝\left[{\mathbf{I}}_n\mid {\mathbf{A}}^{-1}\right]$$

It means , If we simplify the augmented system of equations into a row simplest ladder , We can read the inverse of the matrix on the right-hand side of the equations . therefore , Determining the inverse matrix of a matrix is equivalent to solving a system of linear equations .

example 2.9 Use Gauss elimination method to find the inverse matrix

seek
$$\mathbf{A}=\left[\begin{array}{llll}1& 0& 2& 0\\ 1& 1& 0& 0\\ 1& 2& 0& 1\\ 1& 1& 1& 1\end{array}\right]$$
The inverse of .

Let's write the augmented matrix

$$\left[\begin{array}{cccccccc}1& 0& 2& 0& 1& 0& 0& 0\\ 1& 1& 0& 0& 0& 1& 0& 0\\ 1& 2& 0& 1& 0& 0& 1& 0\\ 1& 1& 1& 1& 0& 0& 0& 1\end{array}\right]$$
The Gauss elimination method is used to transform it into the simplest step ：
$$\left[\begin{array}{cccccccc}1& 0& 0& 0& -1& 2& -2& 2\\ 0& 1& 0& 0& 1& -1& 2& -2\\ 0& 0& 1& 0& 1& -1& 1& -1\\ 0& 0& 0& 1& -1& 0& -1& 2\end{array}\right]$$

such , The required inverse matrix is given on the right ：
$${\mathbf{A}}^{-1}=\left[\begin{array}{cccc}-1& 2& -2& 2\\ 1& -1& 2& -2\\ 1& -1& 1& -1\\ -1& 0& -1& 2\end{array}\right]$$

We can perform multiplication $\mathbf{A}{\mathbf{A}}^{-1}$ Is it equal to ${\mathbf{I}}_4$ To test .

2.3.4 Algorithm for solving linear equations

In the following , We will briefly discuss $\mathbf{A}\mathbf{x}=\mathbf{b}$ The solution method of linear equations in form . Here we assume that there is a solution . If there is no solution , We need to resort to approximate solutions , Such as linear regression in Chapter 9 , There is no introduction here .

If we can determine the inverse ${\mathbf{A}}^{-1}$, that $\mathbf{A}\mathbf{x}=\mathbf{b}$ The solution of is expressed as $\mathbf{x}={\mathbf{A}}^{-1}\mathbf{b}$. However , Only when $\mathbf{A}$ When it is a square matrix and reversible , That's how it works , But it's not usually the case . however , Under appropriate assumptions （ namely $\mathbf{A}$ Need to have linearly independent columns ）, We can use the following transformations ：
$$\mathbf{A}\mathbf{x}=\mathbf{b}*{\mathbf{A}}^{\top }\mathbf{A}\mathbf{x}={\mathbf{A}}^{\top }\mathbf{b}*\mathbf{x}={\left({\mathbf{A}}^{\top }\mathbf{A}\right)}^{-1}{\mathbf{A}}^{\top }\mathbf{b}$$

That is to use Moore-Penrose Pseudo inverse (Moore-Penrose pseudo-inverse)${\left({\mathbf{A}}^{\top }\mathbf{A}\right)}^{-1}{\mathbf{A}}^{\top }$ To make sure $\mathbf{A}\mathbf{x}=\mathbf{b}$ Of Moore-Penrose Pseudo inverse solution ${\left({\mathbf{A}}^{\top }\mathbf{A}\right)}^{-1}{\mathbf{A}}^{\top }\mathbf{b}$, This also corresponds to the solution of the minimum norm least squares method .

The disadvantage of this method is that it needs to sum the product of the matrix ${\mathbf{A}}^{\top }\mathbf{A}$ Do a lot of calculations . Besides , For reasons of numerical accuracy , It is generally not recommended to calculate inverse or pseudo inverse . therefore , In the following , We will briefly discuss other methods for solving linear equations .

Gauss elimination method is used to calculate determinant 、 Check whether the vector set is linearly independent 、 Calculate the inverse of the matrix , Calculate the rank of the matrix , And determining the basis of vector space . Gauss elimination method is an intuitive and constructive method to solve a system of linear equations with thousands of variables . However , For a system of equations with millions of variables , This is impractical , Because the amount of computation required increases according to the cubic of the number of simultaneous equations .

In practice , Many linear equations are solved by Steady iterative method (stationary iterative methods) Indirectly solved , Such as Richardson Method 、Jacobi Method 、Gauß-Seidel Method and successive over relaxation method , or Krylov Subspace method , Such as conjugate gradient 、 Generalized minimum residual or biconjugate gradient .

set up ${\mathbf{x}}_{\ast }$ yes $\mathbf{A}\mathbf{x}=\mathbf{b}$ Solution . The key idea of these iterative methods is to establish the following forms of iteration
$${\mathbf{x}}^{(k+1)}=\mathbf{C}{\mathbf{x}}^{(k)}+\mathbf{d}$$

By looking for the right $\mathbf{C}$ and $\mathbf{d}$, Reduce the residual in each iteration $\Vert {\mathbf{x}}^{(k+1)}-{\mathbf{x}}_{\ast }\Vert$ Until it converges to ${\mathbf{x}}_{\ast }$. We will be in 3.1 Section introduces norm $\Vert \cdot \Vert$, It allows us to calculate the similarity between vectors .