Matrix properties and machine learning/data mining

Question

I'm doing some data analysis in a Statistical Pattern Recognition course using PRML. We analyzed a lot of matrix properties, like eigenvalues, column independence, positive semi-definite matrix, etc. When we are doing, for example, linear regression, we need to calculate some of those properties, and fit them into the equation.

So my question is, my question is about the intuition behind these matrix properties, and their implications in the ML/DM literature.

If anyone could answer, can you teach me what is the importance of eigenvalue, positive semi-definite matrix, and column independence for ML/DM. And possibly, other important matrix properties you think important in study the dataset, and why.

I'd be really appreciated if someone can answer this question.

Answer 1

The importance of a concept in mathematics depends on the circumstances of its application. Sometimes, its importance relies on the fact that it allows you to carry on with what you are doing.

For example, you usually need column independence (independent variables between predictors) because multiple regression will behave badly with highly correlated variables. Even worst, when some of your columns (or rows) are dependent, your matrix is not invertible. Why? Because matrix inversion A^-1 involves the determinant 1/|A|, which is 0 when columns or rows are linearly dependent.

Eigenvalues is a common occurrence in calculations related to maximization/minimization in machine learning. Let's say you are interested in principal component analysis. A very important idea there is dimensional reduction (you have a dataset with many variables and want to reduce the number of variables without losing too much explanatory power.) One solution is to project your data onto a lower dimensional space (e.g. taking your data with 50 variables and reducing them to 5 variables.) Turns out a good projection to use is one that includes as much variation as possible and maximization of this variation results in the eigenvalue equation S u = λ u.

In other cases, you explicitly include the eigenvalue equation of some quantity of interest because in doing so, you're changing the coordinate system in which you represent the variables. Take the case of a (multivariate) Gaussian distribution in which the argument of the exponent is given by Δ = (x-μ)^T Σ (x-μ). If you consider the eigenvalue equation of Σ, the exponent can be written as Δ = y_1^2 / λ_1 + y_2^2 / λ_2 (in two dimensions) This is the equation of an ellipse only if λ_1 and λ_2 are positive. Therefore, you obtain the following graphical interpretation (Bishop, PRML, p.81):

Positive semi-definite matrices are used as a matter of convenience. They are well-behaved and well-understood. For instance, their eigenvalues are non-negative, and if you remember the previous paragraph, the argument Δ required positive eigenvalues. By now, you can see why some concepts are very popular: You need them for your calculations or they need each other.

I can recommend a couple of books:

1. Linear Algebra: A Modern Introduction by David Poole
2. Understanding Complex Datasets: Data Mining with Matrix Decompositions by David Skillicorn.

The second recommendation is more specialized and requires a decent understanding of the basics, but it is of great help to understand matrix decompositions.

Answer 2

A few things where the knowledge of Linear Algebra might be helpful in the context of Machine Learning:

1. Dimensionality Reduction: There are lots of problems where PCA (a special case of an SVD) followed by a simple Machine Learning method applied on the reduced dataset produces much better results than a non parametric model on the full (non-reduced dataset). For an example see Bhat and Zaelit, 2012 where PCA followed by linear regression performs better than more involved non-parametric models. It also suggests reasons why dimensionality reduction performs better in these cases.
2. Visualizing data: Higher dimensional data is complicated to visualize and one often needs to be able to reduce the dimension of the dataset to view it. This comes very handy when one has to "view" the results of clustering on a higher dimensional dataset.
3. Numerical Accuracy: Eigenvalues are generally handy in order to understand condition numbers of matrices and hence be able to figure out if results of Linear regression or other methods that require to solve Ax=b would be numerically accurate. Positive Definiteness of a matrix might also be able to guarantee bounds on numerical accuracies.
4. Recommendations: Some methods like collaborative filtering use matrix factorization (SVD) tuned smartly to solve recommendation problems.
5. Regularization: Regularization is commonly used to reduce over-fitting in machine learning problems. Most of these regularization techniques like Lasso, Tikhonov etc. have both optimization and Linear Algebra at their heart.