# Unsupervised machine learning

Here we collect material(videos, articles, pdfs) regarding the unsupervised machine learning course. We follow the outline of the slides.

## Sources and Material

Slides:
1. https://ml.jku.at/teaching/ss2018/ss_vl_mlut/MLun_part1.pdf
2. https://ml.jku.at/teaching/ss2018/ss_vl_mlut/MLun_part2.pdf
3. http://www.bioinf.at/teaching/ss2018/ss_vl_mlut/MLun_part3.pdf

Lecture Notes:
https://moodle.jku.at/jku/pluginfile.php/5435221/mod_resource/content/0/ML_unsupervised.pdf

Generally there are two very good playlists for the unsupervised course, both intersect also supervised learning but it's probably not bad to repeat some stuff there.

Standford course for machine learning
https://www.youtube.com/watch?v=jGwO_UgTS7I&list=PLoROMvodv4rMiGQp3WXShtMGgzqpfVfbU

Bloomberg foundation for machine learning
https://bloomberg.github.io/foml/#lectures

I find these two courses to be very packed with good examples and material.

## Content of the lecture

1. Introduction
2. Basic Terms and Concepts
3. Principal Component Analysis (PCA)
4. Independent Component Analysis (ICA)
6. Factor Analysis
7. Scaling and Projection Methods
8. Clustering
9. Biclustering
10. Hidden Markov Models
11. Boltzmann Machines

## Introduction
---

## Basic Terms and Concepts
---

### Unsupervised Learning in Bioinformatics
e.g. clustering of microarray data: use unsupervised methods to visualize dependencies and clusters with PCA for example

### Unsupervised Learning Categories
Categories:
* generative framework: density estimation, hidden Markov models; main objectives: maximum likelihood or maximum a posteriori
* recoding or descriptive framework: projection methods, PCA, ICA; main objectives: maximal variance, orthogonality, independence, maximum entropy
* Projection Methods: project the data into a space with desired properties
* PCA = Principal Component Analysis: projection to a low dimensional space under maximal information conservation
* ICA = Independent Component Analysis: projection into a space with statistically independent components (factorial code)
* often characteristics of a factorial distribution are optimized: maximal entropy (given variance) or cummulants
* or prototype distributions should be matched: product of special super-Gaussians
* Projection Pursuit: components are maximally non-Gaussian

Generative Models: simulate the world and produce the same data
* data generation process is probabilistic: underlying distribution
* generative model tries to approximate this distribution
* loss function: distance between the model output distribution and the distribution of the data generation process
* examples: factor analysis, latent variable models, Boltzmann machines, hidden Markov models

### Quality of Parameter Estimation

Generative Models estimate the true parameter given a parameterized model class; the data is generated from a model of this class --> task is to find this model
* model class known
* task: estimate actual/true parameters
* training data: {x} = {x^1^, x^2^, ...., x^l^} --> X (matrix of training data)
* true parameter vector: w
* estimate of w: w^(w-hat)



* loss: difference between true and estimated parameter
* evaluate estimator: expected loss

### Maximum Likelihood Estimator
* ML is one of the major objectives in unsupervised learning
* ML is asymptotically efficient and unbiased
* ML does everything right and this efficiently (if enough data is available)


* MLE is invariant under parameter change
* MLE is asymptotically unbiased and efficient --> asymptotically optimal
* MLE is asymptotically consistent (for large training sets the estimator w-hat approaches the true value)

### Expectation Maximization

* likelihood can be optimized by gradient descent methods
* likelihood cannot be computed analytically:
* hidden states, many-to-one output mapping, non-linearities
* **u** = hidden variables, latent variables, unobserved variables
* likelihood is determined by all **u** mapped to x

* Expectation Maximization (EM) algorithm: joint probability p(x, u; w) is easier to compute than likelihood --> estimate p(u|x;w) by Q(u|x)


**General Idea of EM Algorithm/K-means Clustering:**

**Start**: we have given datapoints and we want to partition the data set into k clusters
**Goal**: find assignment of data points to clusters as well as a set of vectors {μk} such that the sum of the squares of the distances of each data point to its closest vector μk is a minimum

**Example**: k = 2
1. We choose 2 random initial values for our μk.
2. assign each datapoint to its nearest μk --> 2 clusters are formed
3. calculate the new means of the clusters = new μk
4. reassign each datapoint to the nearest μk
5. calculate new means of the clusters = new μk
6. ....

**E step** = re-assign data points to clusters
**M step** = re-compute the cluster mean
repeat both steps until nothing changes --> convergence


* EM increases the lower bound in both steps:


* EM algorithm is used in hidden Markov models, mixture of Gaussians, factor analysis and independent component analysis

**Videos:**

https://www.youtube.com/embed/lMShR1vjbUo
https://www.youtube.com/embed/rVfZHWTwXSA
https://www.youtube.com/embed/JNlEIEwe-Cg <--- extrem gutes video
https://brilliant.org/wiki/gaussian-mixture-model/ <--- guter artikel
https://www.youtube.com/embed/REypj2sy_5U

### Maximum Entropy

* maximal entropy given a class of distributions
* minimal prior assumptions
* physical systems converge to maximal entropy configurations
* most likely observed solution
* connection: statistical mechanics and information theory
* principle of maximum entropy: first expounded by E.T. Jaynes in 1957


* examples: normal distribution (given mean and std), uniform distribution (supported in the interval [a, b]), exponential distribution (given mean in [0, inf])

* not all classes of distributions contain a maximum entropy distribution: arbitrarily large entropy (distributions with mean), entropies of a class are bounded from above but not attained (distributions with mean zero, second moment one, third moment one)

* Maximum Entropy Solution


## Principal Component Analysis (PCA)
---

### The Method
There are two commonly used definitons of PCA that lead to the same algorithm.

**For Variance Maximization:**
Starting point we have centered data usually high dimensional. Sometimes the data is correlated, so we have to find the direction of the largest variance (i.e. 1st principal component), then orthogonal to that the direction of the 2nd largest variance and so on.

**Minimum error formulation:**
Can be defined as the linear projection that minimizes the average projection cost, defined as the mean squared distance between the data points.

### Variance Maximization
1. Shift the data such that it is centered (mean=0 for every dim) $\frac{1}{N}\sum_{i=1}^{N}x_i$ and write it in the matrix $X$
2. Compute the symmetric and positive definite covariance matrix $C=\frac{1}{N}X^TX$
3. Then the variance of the projected data is given by $u^TCu$ such that $u$ is a unit vector$(u^Tu=1)$
4. Now we maximize the projected variance with respect to $u$. This has to be a constrained maximization to prevent $\lVert u \rVert \to \infty$. The appropriate constraint comes from $\lVert u \rVert = 1$ and to enforce this constraint we use a Lagrange multiplier. <br/>  <br/>This says that $u$ must be an eigenvector of $C$.Then we left multiply by $u^T$ to make use of $u^Tu=1$ and see that the variance is given by $u^TCu=\lambda$ and so we see that the eigenvalue $\lambda$ is the variance along the direction of $u$ which is our first principal component.
5. We can define additional principal components in an incremental fashion by choosing each new direction which maximizes the projected variance amongst all possible directions orthogonal to those already considered(adding new constraints to our Lagrangian)
6. To summarize PCA involves evaluating $X$ and the covariance matrix $C$ of the data set and then finding $M$ eigenvectors of $C$ corresponding to to the $M$ eigenvalues.
7. PCA defines a new space for the data, where each dimension explains less of the original variance than the last.The amount of variance explained can be seen from the eigenvectors.The amount of "explained variance" by principal component j is $v_j=\frac{\lambda_j}{\sum_{k=1}^{d}\lambda_k}$

### Uniqueness
In short PCA is unique.
The longer answer is, PCA is unique up to signs, if the eigenvalues of the covariance matrix are different from each other.

### Properties of PCA
PCA is often used to visualize data. (i.e. to downproject data to a small number of dimensions and plot it)
In machine learning PCA is often used to reduce dimensionality
* often drastically reduces amount of data -> faster algorithms, less memory needed
* often performs better, since less overfitting
* destroys sparseness
* no guarantees, you may throw away important information
* The projections onto PCs have zero mean
* The projection of the data on the first principal component (PC) has maximal variance of all possible one-dimensional projections. That means $u$ maximizes
* The projections onto PCs are mutually uncorrelated, that is, they are orthogonal to each other.
* The sample variance of the $k$-th projection is equal to the $k$-th eigenvalue of the sample covariance matrix $C$
* PCs are ranked decreasingly according to their eigenvalues which are the variances in the PC direction
* The first $l$ PCs minimize the mean-squared error

### Examples
E.g. can be found in Hochreiter's skript page 47-60 contains various examples.

*Example: Showing how much "explained variance" the first few PC's contain, or rather retain*

### Kernel Principal Component Analysis
PCA is a linear method but data is often not linearly separable. So the idea is to map data into a higher dimensional space where it becomes linearly separable and apply PCA there.
*Showing the mapping onto a higher dimensional plane*

Before looking at the formulas for KPCA below i recommend to watch these two short videos on Kernel PCA, because they explain the fundamentals.
[Kernel PCA by Reema Harnekar(volume is quite low)](https://www.youtube.com/watch?v=0zjfA1PO6DI)
[Caltech (8.6 David Thompson (Part 6): Nonlinear Dimensionality Reduction: KPCA)](https://www.youtube.com/watch?v=HbDHohXPLnU)


## Independent Component Analysis (ICA)
---

**videos**

quick video introduction to the problem:

https://www.youtube.com/watch?v=2WY7wCghSVI
https://www.youtube.com/watch?v=wIlrddNbXDo
https://www.youtube.com/watch?v=e4woe8GRjEI
https://www.youtube.com/watch?v=SjM2Qm7N9CU

longer and more detailed video:

https://www.youtube.com/watch?v=YQA9lLdLig8

good slides for basic understanding:

https://wwwf.imperial.ac.uk/~nsjones/TalkSlides/HyvarinenSlides.pdf

good article for better understanding:

http://arnauddelorme.com/ica_for_dummies/

concrete practical example with brain scans (long tutorial series):

https://www.youtube.com/playlist?list=PLXc9qfVbMMN2uDadxZ_OEsHjzcRtlLNxc

### Basics and Intution
Independent component analysis (ICA) goes beyond PCA, which decorrelated the components, by requiring statistically independent components.

ICA decomposes a multivariate observation into additive components, where the components are non-Gaussian and statistically independent from each other. ICA differs from PCA in four major issues:
* ICA does not maximize the variance,
* ICA does not enforce orthogonal projection or demixing matrices,
* ICA aims at statistically independent components,
* ICA components are not ranked.

Independent component analysis attempts to decompose a multivariate signal into independent non-Gaussian signals. As an example, sound is usually a signal that is composed of the numerical addition, at each time t, of signals from several sources. The question then is whether it is possible to separate these contributing sources from the observed total signal. When the statistical independence assumption is correct, blind ICA separation of a mixed signal gives very good results.

ICA assumes that the observations x are generated by mixing the sources y, where both x and y are m-dimensional vectors: $x = U y$
U is seen as the mixing matrix

The goal is to find a matrix W which de-mixes x with
$y = W x$ with W being the de-mixing matrix $W = U^{-1}$

### Identifiability and Uniqueness
ICA is not unique. It is only unique up to scaling and

### Measuring Independence
ICA finds the independent components (also called factors, latent variables or sources) by maximizing the statistical independence of the estimated components. We may choose one of many ways to define a proxy for independence, and this choice governs the form of the ICA algorithm. The two broadest definitions of independence for ICA are

* Minimization of mutual information
* Maximization of non-Gaussianity

**Mutual Information**
The basic idea is based on entropy. Entropy of a factorial code is larger than the entropy of the joint distribution.
The difference I is called mutual information:
$I(y_1,...,y_l) = \sum_{j=1}^l H(y_j) - H(y)$ H denotes the entropy.

**Non-Gaussianity**
Is based on the Central Limit Theorem: The distribution of a sum of a large number of independent random variables tends toward a Gaussian distribution.
* Signal is more Gaussian than sources since it is a linear combination of them.
* Signal becomes least Gaussian when equal to one of the sources

Gaussianity is measured using “Cumulants”

## Factor Analysis
---

**videos**

https://www.youtube.com/watch?v=WV_jcaDBZ2I
https://www.youtube.com/watch?v=TeIx7dRedkg
https://www.youtube.com/watch?v=yWUKzEIeVWU
https://www.youtube.com/watch?v=mIx-qlI4mJo
https://www.youtube.com/watch?v=Vl7mtAmveYQ
https://www.youtube.com/watch?v=PgqiBezoAUA
https://www.youtube.com/watch?v=9j-c9fOIHmM
https://www.youtube.com/watch?v=yj7Q0EM5VMA
https://www.youtube.com/watch?v=G16c2ZODcg8

from the Standford video series

https://www.youtube.com/watch?v=tw6cmL5STuY

## Scaling and Projection Methods
---

## Clustering
---

## Biclustering
---

---