AI - Lecture 19

Fast Recap:

---

Recap: Mixture of Gaussian Components: $\underline{{\Theta }_i}=\underline{{\mu }_i}$ A GMM (Gaussian Mixture Model) is a mixture density having form:

$$p(\underline{x}|\underline{\Theta })=\sum _{j=1}^{c}P({\omega }_j)N(\underline{{\mu }_j},{\Sigma }_j)$$

With the following component densities:

$$p(\underline{x}|{\omega }_j,\underline{{\Theta }_j})=\frac{1}{(2\pi {)}^{\frac{d}{2}}\cdot |{\Sigma }_j{|}^{\frac{1}{2}}}\cdot \exp \left\{-\frac{1}{2}(\underline{x}-\underline{{\mu }_j}{)}^t\cdot {\Sigma }_j^{-1}\cdot (\underline{x}-\underline{{\mu }_j})\right\}$$

Whose gradient w.r.t. (whit respect to) parameters ${\Theta }_i$ is:

$${\nabla }_{\underline{{\mu }_j}}\log \left\{p(\underline{x}|{\omega }_j,{\mu }_j)\right\}={\Sigma }_j^{-1}(\underline{x}-\underline{{\mu }_j})$$

From the previous lecture we have seen that the condition to be respected is:

$$\sum _{k=1}^{n}P({\omega }_i|\underline{x_k},\underline{\hat{\Theta }})\cdot {\nabla }_{\underline{{\hat{\Theta }}_i}}\log \left\{p(\underline{x}|{\omega }_i,\underline{{\hat{\Theta }}_i})\right\}=0\forall i=1,\dots ,c$$

So we will have that, since $\underline{{\hat{\Theta }}_j}=\underline{{\hat{\mu }}_j}$:

$$\underline{{\hat{\mu }}_j}=\frac{{\sum }_{k=1}^{n}P({\omega }_j|\underline{x_k},\hat{\underline{\mu }})\underline{x_k}}{{\sum }_{k=1}^{n}P({\omega }_j|\underline{x_k},\hat{\underline{\mu }})}$$

But there is a problem:

$$\{\begin{array}{l}\underline{{\hat{\mu }}_j}=\frac{{\sum }_{k=1}^{n}P({\omega }_j|\underline{x_k},\hat{\underline{\mu }})\underline{x_k}}{{\sum }_{k=1}^{n}P({\omega }_j|\underline{x_k},\hat{\underline{\mu }})}\\ P({\omega }_j|\underline{x_k},\hat{\underline{\mu }})=\frac{p(\underline{x_k}|{\omega }_j,\hat{\underline{\mu }})P({\omega }_j)}{{\sum }_{i=1}^{c}p(\underline{x_k}|{\omega }_j,\hat{\underline{\mu }})P({\omega }_i)}\end{array}$$

The formulation is circular: to calculate $\underline{{\hat{\mu }}_j}$ we need to know $\underline{{\hat{\mu }}_j}$, we thus resort to the following iterative algorithm:

$$\{\begin{array}{l}\underline{\hat{\mu }}(0)=\text{inital "arbitrary" estimate}\\ \underline{\hat{\mu }}(t+1)=\frac{{\sum }_{k=1}^{n}P({\omega }_j|\underline{x_k},\hat{\underline{\mu }}(t))\underline{x_k}}{{\sum }_{k=1}^{n}P({\omega }_j|\underline{x_k},\hat{\underline{\mu }}(t))}\end{array}$$

And we iterate for $t=0$ up to $t=T$, where $T$ is decided arbitrarily.

Unsupervised Non-Parametric Estimation: Clustering Update equation for $\underline{{\hat{\mu }}_j}(t+1)$:

The $P({\omega }_i|\underline{x_k},\underline{\hat{\mu }}(t))$ formula just says that given:

• $c$ classes (${\omega }_j$) each with a vector of parameters, in this case just the evaluated mean ($\underline{{\hat{\mu }}_j}(t)$) The probability that $\underline{x_k}$ belong to class ${\omega }_j$ is $1$ if and only if the evaluated mean $\underline{{\hat{\mu }}_j}(t)$ is the closest to $\underline{x_k}$ according to the Euclidean distance, with respect to all other means ($\underline{{\hat{\mu }}_i}(t)$ for $i\ne j$) ⇒ So: $P({\omega }_i|\underline{x_k},\underline{\hat{\mu }}(t))$ is just $1$ or $0$, this simplifies the calculation.
  

k-Means Clustering Algorithm:

1. Fix initial arbitrary (~ex.: random) values: $\underline{{\hat{\mu }}_1}(0),\dots ,\underline{{\hat{\mu }}_c}(0)$.
2. Assign each $\underline{x_k}$ (for $k=1,\dots ,n$) to its closest mean $\underline{{\hat{\mu }}_j}(t)$.
3. Re-calculate $\underline{{\hat{\mu }}_j}(t)$ for $j=1,\dots ,c$ applying the previous equation for updating $\underline{{\hat{\mu }}_j}(t)$ (arithmetic mean of the pattern $\underline{x_k}$ in cluster ${\omega }_i$).
4. If $\exists j\in \{1,\dots ,c\}:\underline{{\hat{\mu }}_j}(t)\ne \underline{{\hat{\mu }}_j}(t-1)$ then iterate from point 2., this mean: If during the last iteration at least one value of $\underline{{\hat{\mu }}_j}$ changed, repeat.
   

The Problem of Data Description $\underline{\hat{\mu }}$ and $\underline{\hat{\Sigma }}$ are sufficient statistics (they are a complete description of our data) if and only if, our data $\underline{x}$ is drawn from a Gaussian Distribution.

Otherwise they would yield a wrong data description.

To solve this problem we can use a GMM (Gaussian Mixture Model), and relying an an unbounded number of Gaussian Distribution we can describe any continuous and limited PDF. This raises two problems:

1. Using an “unbounded” number of Gaussian PDFs brings complexity issues
2. Also if we mix too many Gaussian PDFs the problem overfits the training data and doesn’t generalize too well.

Alternatively we can use a non-parametric technique for estimating $p(\underline{x})$, for example the Parzen-Window or $k_n$-Nearest Neighbors, but we need to pay attention to the number of data used:

1. If $n=|\tau |$ is small (few data), then the estimate $p_n(\underline{x})$ is not reliable.
2. If $n=|\tau |$ is big, then $p_n(\underline{x})$ is over-complex, being memory-based, since $\tau$ must be kept in memory and involved in the calculations, this would not be a real data description.

⇒ ==Our best shot is to use Clustering algorithms.==

Similarity Measures Instead of defining $k$ (the number of cluster) at the beginning we can define $d_0$ the maximum distance for which an element can be considered inside a cluster. If in a single the “within-cluster distance” of 2 elements is further than $d_0$, then we create another cluster and re-separate the data.
Hierarchical Clustering: The Hierarchical Clustering has 2 families:

1. Top-Bottom: Divisive Clustering (we start with 1 big cluster and separate until we have at least $c$ or clusters)
2. Bottom-Up: Agglomerative Clustering, that we will see later (we start with no cluster and agglomerate data into new and previously created cluster until we at least have $c$ clusters)
   

Agglomerative Clustering algorithm:

Here is an example on how the algorithm works:

1. We start with creating a cluster with data $10$ and $13$ since they are the closest.
2. Then a new cluster with $7$ and $12$
3. We simultaneously agglomerate $14$ and $19$ into their own cluster, and add $4$ to the cluster containing $10$ and $13$
4. $\dots$
   

Between-Clusters Distance Measures: The most popular measures of distance between 2 clusters are:

The formula for obtaining these distances are reported here: ($X_i$ and $X_j$ are the two cluster we take into consideration)

Utility of Clustering Algorithms:

1. Finding the geometric/probabilistic properties of the data: (~ex.: center of mass and variance)
2. Describe the data in a concise fashion
3. Partitioning the data into $c$ sub-samples (useful for dived et conquer algorithms)
4. Finding good initialization (the centroids) for complex models such as: GMMs with Max Likelihood, RBFs, $\dots$
5. Discretization of continuous features (~ex.: We can use the centroids and the number of data in each cluster to create an histograms of the data).
6. Replacing original big data set with one single cluster of it, useful when working with complex algorithms like K-NN or Parzen-Window.

---

Original Files:

---

---

---