Math for ML - Linear dependence & Linear Equation

Continue with math for machine learning, this article will give a quick note on definition of linear dependence and demonstration with python.

math for machine learning

Linear Dependence

In the theory of vector spaces, a set of vectors is said to be linearly dependent if at least one of the vectors in the set can be defined as a linear combination of the others; if no vector in the set can be written in this way, then the vectors are said to be linearly independent.

Definition: The vectors in a subset $S={\vec v_1,\vec v_2,\dots,\vec v_k}$ of a vector space V are said to be ”linearly dependent”, if there exist scalars $a_1,a_2,\dots,a_k$ , not all zero, such that $a_1\vec v_1+a_2\vec v_2+\cdots+a_k\vec v_k= \vec 0$ , where $\vec 0$ denotes the zero vector.

$\vec v_1 = \{1, 2, 3\} \\ \vec v_2 = \{2, 3, 4\} \\ \vec v_3 = \{3, 5, 8\}$

The above vectors are not linear independent as $\vec { v_1} + \vec { v_2} - \vec {v_3} = \vec 0$

System of linear equation

Linear dependence has a strong relation to solution of linear equations. Since it is all about systems of linear equations, let’s start again with the set of equations:

$A_{1,1}x_1 + A_{1,2}x_2 + \cdots + A_{1,n}x_n = b_1 \\ A_{2,1}x_1 + A_{2,2}x_2 + \cdots + A_{2,n}x_n = b_2 \\ \cdots \\ A_{m,1}x_1 + A_{m,2}x_2 + \cdots + A_{m,n}x_n = b_n$

We know A and b as constant terms and need to find x.

Matrix equation

The system is equivalent to a matrix equation of the form

$A \times x= b$

Where A is a m x n matrix of coefficients, x and b is column vectors. The equation corresponds to:

$A= \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix},\quad \mathbf{x}= \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix},\quad \mathbf{b}= \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{bmatrix}$

Number of solutions

Three cases can represent the number of solutions of the system of equations Ax=b.

No solution
Exactly 1 solution
An infinite number of solutions

It is because we are dealing with linear systems: 2 lines can’t cross more than once as illustrated below

Linear dependence and number of solution

Solve systems of equations with `numpy`.

To find x:

$x = A^{-1} \times b$

So the solution exists if A is invertible ( $A^{-1}$ exists). To solve the standard linear system, we can use numpy.linalg.solve(A, b).

Example 1: Solve the system of equations (no solution)

$-3x_0 - x_1 = 9 \\ -3x_0 -x_1 = 7$

a = np.array([[-3,-1], [-3, -1]])
b = np.array([9,7])
x = np.linalg.solve(a, b)
print(x)
#LinAlgError: Singular matrix

Example 2: Solve the system of equations (one solution)

$3 x_0 + x_1 + x_2 = 9 \\ x_0 + 2 x_1 + 3x_2 = 8 \\ 2x_0 + 0.5 x_1 + 4x_2 = 7$

a = np.array([[3,1,1], [1,2,3], [2, 0.5,4]])
b = np.array([9,8,7])
x = np.linalg.solve(a, b)
print(x)
#[2.08333333 2.33333333 0.41666667]

Check that the solution is correct:

np.allclose(np.dot(a, x), b)
#True

Example 3: Solve the system of equations (infinite solutions)

$3x_0 + x_1 = 9 \\ 6x_0 + 2 * x_1 = 18$

import numpy as np
a = np.array([[3,1], [6,2]])
b = np.array([9,18])
x = np.linalg.solve(a, b)
print(x)
#LinAlgError: Singular matrix

This system has infinite solutions and matrix a is not invertible. Its rows are linear dependent.

Check linear dependency

Use Eigenvalue: If one eigenvalue of the matrix is zero, its corresponding eigenvector is linearly dependent. The eigenvalues are not necessarily ordered. A method would be:

matrix = np.array(
    [
        [0, 1 ,0 ,0],
        [0, 0, 1, 0],
        [0, 1, 1, 0],
        [1, 0, 0, 1]
    ])
w, v =  np.linalg.eig(matrix.T)
# The linearly dependent row vectors
print matrix[w == 0,:]

w: The eigenvalues, each repeated according to its multiplicity.
v: The normalized (unit “length”) eigenvectors, such that the column v[:,i] is the eigenvector corresponding to the eigenvalue w[i]

References:

[1] Marc P.D, A. Aldo, Cheng S.O, Math for machine learning, url: https://mml-book.github.io/book/mml-book.pdf
[2] Deep learning book series, url https://hadrienj.github.io/posts/Deep-Learning-Book-Series-2.4-Linear-Dependence-and-Span/
[3] Wikipedia, https://en.wikipedia.org/wiki/System_of_linear_equations

Math for ML – Linear dependence & Linear Equation

Linear Dependence

System of linear equation

Matrix equation

Number of solutions

Solve systems of equations with `numpy`.

Check linear dependency

References:

Add comment

Cancel reply

Linear Dependence

System of linear equation

Matrix equation

Number of solutions

Solve systems of equations with numpy.

Check linear dependency

References:

Add comment

Cancel reply

Read more

Categories

Solve systems of equations with `numpy`.