Machine Learning Notes 1

1) Machine learning (ML) related definitions

Definition A (Athur Samuel, 1959): Machine learning is the field of study which gives computers the ability to learn without being explicitly programmed.

Definition B (Tom Mitchell, 1998): Well-posed machine learning problem: A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.

2) Types of ML algorithms

In general any ML algorithm can be classified into one of the following two categories

• Supervised learning (the "right answers" are given in the initial data set; i.e. the data set is labeled)
• Regression: trying to predict the values of some quantity which we view as a continuous function
• Classification: trying to predict the values of some quantity whose possible values form a small finite discrete set (that set could be e.g. {Yes, No}; {0,1,2,3}; {Cat, Dog, Other}; etc.); trying to classify a set of data points into a small finite number of classes
• Unsupervised learning (the "right answers" are not given in the initial data set; i.e. the data set is unlabeled); in unsupervised learning the task is to automatically find some structure in the unlabeled data set that is given
• Clustering: a data set is given, the task is to break it down into several separate clusters (i.e. into several separate disjoint data sets). Examples: 1) Google news (news articles from various sources are grouped together if they are about the same story); 2) Market segmentation: find market segments/clusters in a dataset which contains data about all customers of a given company.
• Non-clustering: 
• Independent component analysis (used in signal processing). Example: separating different voices (or say different audio tracks) out of one (or a few) given chaotic audio recordings (see e.g. (1) cocktail party effect, (2) cocktail party problem and algorithm). The so-called "cocktail party algorithm" allows you to find structure in a chaotic environment (identifying individual voices and music from a mesh of sounds at a cocktail party).
• Anomaly detection (detect unusual data points in a given dataset). Anomaly detection (also referred to as outlier detection and sometimes as novelty detection) is generally understood to be the identification of rare items, events or observations which deviate significantly from the majority of the data and do not conform to a well defined notion of normal behavior (Source: Wikipedia). 
• Dimensionality reduction (compress data points using fewer numbers). Dimensionality reduction, or dimension reduction, is the transformation of data from a higher-dimensional space into a lower-dimensional space so that the lower-dimensional representation retains some meaningful properties of the original data, ideally close to its intrinsic dimension (Source: Wikipedia).

3) GNU Octave

This is a powerful framework for quick prototyping of solutions/algorithms for ML problems (see here: GNU Octave)

NumPy operators and their corresponding NumPy universal functions (ufuncs)

NumPy operators and their corresponding NumPy universal functions (ufuncs)

This table was compiled from the 3 tables shown on pages 53, 72, 75 of the book Python Data Science Handbook by Jake VanderPlas. I put it here just for my own reference.

Arithmetic Operator	Equivalent ufunc	Description
+	np.add	Addition (e.g., 1 + 1 = 2)
-	np.subtract	Subtraction (e.g., 3 - 2 = 1)
-	np.negative	Unary negation (e.g., -2)
*	np.multiply	Multiplication (e.g., 2 * 3 = 6)
/	np.divide	Division (e.g., 3 / 2 = 1.5)
//	np.floor_divide	Floor division (e.g., 3 // 2 = 1)
**	np.power	Exponentiation (e.g., 2 ** 3 = 8)
%	np.mod	Modulus/remainder (e.g., 9 % 4 = 1)
Comparison Operator	Equivalent ufunc
==	np.equal
!=	np.not_equal
<	np.less
<=	np.less_equal
>	np.greater
>=	np.greater_equal
Logical Operator	Equivalent ufunc	See also
&	np.bitwise_and	np.logical_and
|	np.bitwise_or	np.logical_or
^	np.bitwise_xor	np.logical_xor
~	np.bitwise_not	np.logical_not

NumPy rules of broadcasting

These rules are listed in the book Python Data Science Handbook by Jake VanderPlas (see page 65).

Broadcasting in NumPy is simply a set of rules for applying binary universal functions (like addition, subtraction, multiplication, etc.) on NumPy arrays of different sizes.

Here are the NumPy broadcasting rules. 

• Rule 1: If the two arrays differ in their number of dimensions, the shape of the
one with fewer dimensions is padded with ones on its leading (left) side.

• Rule 2: If the shape of the two arrays does not match in any dimension, the array
with shape equal to 1 in that dimension is stretched to match the other shape.

• Rule 3: If in any dimension the sizes disagree and neither is equal to 1, an error is
raised.

Inverse of a matrix

All matrices we talk about here are $n \times n$ square matrices over a numeric field.  

In linear algebra the definition of the concept invertible matrix is usually given this way. 

Def.: A matrix is said to be invertible if there exists a matrix B such that $AB=BA=I$ where I is the identity matrix. In this case B is called the inverse matrix of A.

But I somehow don't like this definition, it seems too strong to me since it implies B is both left inverse (meaning $BA=I$) and right inverse (meaning $AB=I$) of the matrix A.

So let us try to introduce this concept in a somewhat different way.

Def.1: A matrix is said to be left invertible if there exists a matrix B such that $BA=I$ where I is the identity matrix. In this case B is called left inverse matrix of A.

Def.2: A matrix is said to be right invertible if there exists a matrix B such that $AB=I$ where I is the identity matrix. In this case B is called right inverse matrix of A.

We still don't know if left/right inverses of a matrix A exist and under what conditions. We also don't know if they are unique (in case they exist). 

Now we will prove a few statements to clarify all this. 

Th1: If a matrix A is left (or right) invertible then $\det (A) \ne 0$  

Proof: We know that $\det (XY) = \det(X) \cdot \det(Y)$ 

If A is left invertible then there exists a matrix B such that $BA = I$. But then $1 = \det(I) = \det(BA) = \det(B) \cdot \det(A)$ And now it follows that $\det(A) \ne 0$  

If A is right invertible then there exists a matrix B such that $AB = I$. But then $1 = \det(I) = \det(AB) = \det(A) \cdot \det(B)$ And now again it follows that $\det(A) \ne 0$  

Th2: If $\det(A) \ne 0$ then A is left and right invertible. 

Proof: The proof here is done by construction. If $A=(a_{ij})$, we construct the matrix $S=(A_{ji})$ which is the matrix formed by the cofactors of $A$ transposed. Then one easily shows (using previous theory from linear algebra) that the matrix $T = \frac{1}{\det(A)} \cdot S$ satisfies both $TA=I$ and $AT=I$ 

So far we proved that a matrix A is left/right invertible if and only if $\det(A) \ne 0$ In the case when $\det(A) \ne 0$, we also showed how one left inverse and one right inverse can be constructed i.e. we showed existence of the left/right inverses (the matrix T is both left and right inverse of A). 

This construction of $T$ (from $A$) is important so we will keep denoting this so-constructed matrix as $T$ for the rest of this post. 

Th3: For each matrix $A$ with $\det(A) \ne 0$ there is a unique left inverse and a unique right inverse and they are both equal to the above constructed matrix $T$.  

Proof: Let's assume that $BA=CA=I$ for some matrices $B,C$ - left inverses of $A$. 

Then $T=IT=(BA)T=B(AT)=BI = B$  

And also $T=IT=(CA)T=C(AT)=CI = C$  

OK, so it follows that $B=C$ (and both B and C are equal to that special matrix T). This proves the uniqueness of the left inverse. 

Note that to prove the uniqueness of the left inverse we used the existence of the right inverse T of A. 

The uniqueness of the right inverse is proved in the same way.  

Let's assume that $AB'=AC'=I$ for some matrices $B',C'$ - right inverses of $A$. 

Then $T=TI=T(AB')=(TA)B'=IB' = B'$  

Also  $T=TI=T(AC')=(TA)C'=IC' = C'$  

So it follows that $B'=C'$ (and both B' and C' are equal to that special matrix T). This proves the uniqueness of the right inverse. 

Note that to prove the uniqueness of the right inverse we used the existence of the left inverse T of A. 

We are done. Now we have everything introduced in a clear way. We proved that A is left/right invertible if and only if its determinant is non-zero. And we proved that in that case (when the determinant is non-zero) the left/right inverses exists (T), and also that they are unique and coincide (both are equal to T). 

Elementary row/column operations on matrices

The elementary row/column operations on matrices are:

1) Multiplying the $i$-th row (column) by a number $\lambda \ne 0$.

$R_i := \lambda \cdot R_i$

2) Adding the $j$-th row/column multiplied by a number $\lambda$ to the $i$-th row/column.

$R_i := R_i + \lambda \cdot R_j$

3) Exchanging the rows/columns $i$ and $j$.

$R = R_i$

$R_i = R_j$

$R_j = R$

The interesting thing is that for square matrices each of these operations can be accomplished by matrix multiplication.

Let us define: 

• $E$ - the identity matrix of order $n \times n$.
• $E_{ij}$ - the square matrix of order $n \times n$ which has an element $1$ at position $(i, j)$ and zeroes at all other positions.
• $A$ - any square matrix of order $n \times n$.

Then one can show that:

(1) Multiplying the i-th row/column of A by the number $\lambda \ne 0$ is accomplished by left/right multiplying A with the matrix $A_i(\lambda) = E + (\lambda-1)E_{ii}$

(2A) Adding the $j$-th row multiplied by a number $\lambda$ to the $i$-th row is accomplished by left multiplying A with the matrix $B_{ij}(\lambda) = E + \lambda E_{ij}$

(2B) Adding the $j$-th column multiplied by a number $\lambda$ to the $i$-th column is accomplished by right multiplying A with the matrix $B_{ji}(\lambda) = E + \lambda E_{ji}$

(3) Exchanging the rows/columns $i$ and $j$ is accomplished by left/right multiplying A with the matrix $C_{ij} = E - E_{ii} - E_{jj} + E_{ij} + E_{ji}$

The matrices $A_i(\lambda), B_{ij}(\lambda), C_{ij}$ are usually called matrices of the elementary transformations.

Rank of a system of vectors

Let $V\ $ be a vector space and let

$$b_1, b_2, \dots, b_n \tag{1}$$ be a system (multiset) of vectors from $V$

(multiset because the vectors $b_i$ are not required to be distinct).

Definition: 

a) We will say that the system $(1)$ has rank $r \in \mathbb{N}$ if there exist $r$ linearly independent vectors from $(1)$, and every other vector from $(1)$ can be represented as a linear combination of these $r$ vectors. 

b) We will say that the system $(1)$ has rank $0$ if $b_i = 0$ (the zero vector) for every $i=1,2,\dots, n$.

The rank of the system of vectors $(1)$ is denoted by $r(b_1, b_2, \dots, b_n)$.

Proposition 1: The rank of the system $(1)$ is equal to the maximal number of linearly independent vectors in the system $(1)$

Proposition 2: $r(b_1, b_2, \dots, b_n) = \dim\ \textbf{span}(b_1, b_2, \dots, b_n)$

Proposition 3: If $r(b_1, b_2, \dots, b_n)=r$ and $b$ is a vector, then $\ r(b_1, b_2, \dots, b_n, b) = r\ $ or $\ r(b_1, b_2, \dots, b_n, b) = r + 1\ $

More specifically: 

A) $r(b_1, b_2, \dots, b_n, b) = r(b_1, b_2, \dots, b_n)$ 

if and only if $b$ is a linear combination of the vectors $b_i$

B) $r(b_1, b_2, \dots, b_n, b) = r(b_1, b_2, \dots, b_n) + 1$ 

if and only if $b$ is not a linear combination of the vectors $b_i$

Algebra Notes 3

3.1) Permutations

Every ordering of the first n natural numbers $1,2,\dots,n$ is called a permutation.

There are $n!$ permutations of the first n natural numbers.

3.2) Inversions

If we have the permutation $i_1, i_2, \dots i_n$ (of the first n natural numbers) then the numbers $i_k$ and $i_s$ are said to form an inversion if $k \lt s$ but $i_k > i_s$

In other words, an inversion in a permutation is a pair of numbers such that the larger number appears to the left of the smaller one in the permutation. The inversion number of a permutation is the total number of inversions. The inversion number of the permutation $i_1, i_2, \dots i_n$ is denoted by $[i_1, i_2, \dots ,i_n]$.

3.3) Parity of a permutation

Odd permutations - the inversion number is odd

Even permutations - the inversion number is even

3.4) Sign of a permutation

The sign of a permutation $i_1, i_2, \dots i_n$ is defined as $(-1)^{[i_1, i_2, \dots ,i_n]}$, where $[i_1, i_2, \dots ,i_n]$ is the inversion number of the permutation. It is obvious that the sign is $+1$ for even permutations and $-1$ for odd permutations.

3.5) Transposition

We say that we have applied a transposition if in a permutation P we swap the order of any two elements and the other elements we leave in place. When we do this, we get (from P) a new permutation R.

Lemma 1: The permutations P and R are of different parity.

Lemma 2: When $n \ge 2$, the number of the even permutations is equal to the number of the odd permutations.

3.6) Determinant

The concepts introduced here are important building blocks for introducing the concept of determinant (of a square matrix). The concept of determinant is usually defined using the Leibniz formula for determinants

Algebra Notes 2

2.1) Systems of linear equations

$a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1$

$a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2$

$\dots$

$a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m$

This is a system of m linear equations with n unknowns. 

a) The matrix of this system is defined as follows

$$A = \begin{bmatrix}a_{11}&a_{12}&...&a_{1n}\\a_{21}&a_{22}&...&a_{2n}\\...&...&...&...\\a_{m1}&a_{m2}&...&a_{mn}\end{bmatrix}$$

На български: матрица на системата

b) The augmented matrix of this system is defined as follows

$$B = \begin{bmatrix}a_{11}&a_{12}&...&a_{1n}&b_1\\a_{21}&a_{22}&...&a_{2n}&b_2\\...&...&...&...&...\\a_{m1}&a_{m2}&...&a_{mn}&b_m\end{bmatrix}$$

На български: разширена матрица на системата

2.2) Types of systems of linear equations

a) Independent system: has exactly one solution

b) Inconsistent system: has no solutions

c) Consistent system: has at least one solution

d) Dependent system: has infinitely many solutions

a) Определена система: има точно едно решение

b) Несъвместима система: няма решения

c) Съвместима систeмa: има поне едно решение

d) Неопределена система: има безбройно много решения

2.3) Elementary transformations applied to a system of linear equations

a) swapping two rows

b) multiplying a row of the system with a non-zero number

$R := \lambda R$, where $\lambda \neq 0$ 

c) adding to a row another row (multiplied by a number)

$R_2 := R_2 + \lambda R_1$

Note: If we apply (to a given system of linear equations) a finite number of elementary transformations, the resulting system is equivalent to the original system.

2.4) Gaussian elimination - a general method for solving systems of linear equations

Gaussian elimination