Unsupervised Learning: Difference between revisions
(58 intermediate revisions by the same user not shown) | |||
Line 8: | Line 8: | ||
Here we wish to cluster them to minimize the distance to the mean of their cluster.<br> | Here we wish to cluster them to minimize the distance to the mean of their cluster.<br> | ||
In our formulation we have k clusters.<br> | In our formulation we have k clusters.<br> | ||
The mean of each cluster <math>\mu_i</math> is called the centroid. | The mean of each cluster <math>\mu_i</math> is called the centroid.<br> | ||
====Optimization==== | ====Optimization==== | ||
Let <math>\mathbf{\mu}</math> denote the centroids and let <math>\mathbf{z}</math> denote the cluster labels for our data.<br> | Let <math>\mathbf{\mu}</math> denote the centroids and let <math>\mathbf{z}</math> denote the cluster labels for our data.<br> | ||
Line 18: | Line 18: | ||
If we fix <math>\mathbf{z}</math> then we need to minimize <math>L(\mu, \mathbf{z})</math> wrt <math>\mu</math>.<br> | If we fix <math>\mathbf{z}</math> then we need to minimize <math>L(\mu, \mathbf{z})</math> wrt <math>\mu</math>.<br> | ||
Taking the gradient and setting it to 0 we get:<br> | Taking the gradient and setting it to 0 we get:<br> | ||
<math> | <math display="block"> | ||
\begin{ | \begin{aligned} | ||
\ | \nabla_{\mu} L(\mu, \mathbf{z}) &= \nabla_{\mu} \sum_{i} \Vert x^{(i)} - \mu_{z^{(i)}} \Vert ^2\\ | ||
&= \ | &= \nabla_{\mu} \sum_{j=1}^{k} \sum_{i\mid z(i)=j} \Vert x^{(i)} - \mu_{z^{(i)}} \Vert ^2\\ | ||
&= \ | &= \nabla_{\mu} \sum_{j=1}^{k} \sum_{i\mid z(i)=j} \Vert x^{(i)} - \mu_{j} \Vert ^2\\ | ||
&= \sum_{j=1}^{k} \sum_{i\mid z(i)=j} \nabla_{\mu} \Vert x^{(i)} - \mu_{j} \Vert ^2\\ | |||
&= \sum_{j=1}{k} \sum_{i\mid z(i)=j} \ | &= -\sum_{j=1}^{k} \sum_{i\mid z(i)=j} 2(x^{(i)} - \mu_{j}) = 0\\ | ||
&= \sum_{j=1}{k} \sum_{i\mid z(i)=j} 2(x^{(i)} - \mu_{j})\\ | \implies \mu_{j} &= (\sum_{i\mid z(i)=j} x^{(i)})/(\sum_{i\mid z(i)=j} 1) \quad \forall j | ||
\implies \mu_{j} &= (\sum_{i\mid z(i)=j} x^(i))/(\sum_{i\mid z(i)=j} 1) \quad \forall j | \end{aligned} | ||
\end{ | |||
</math> | </math> | ||
;Notes | |||
This procedure will yield us a sequence of parameters and losses.<br> | |||
<math> \mu^{0}, z^{0}, \mu^1, z^1, ...</math><br> | |||
<math> L(0) \geq L(1) \geq L(2) \geq ...</math><br> | |||
* Since the loss is monotone decreasing and bounded below, it will converge by the monotone convergence theorem. | |||
* However, this does not imply that the parameters <math>\mathbf{\mu}</math> and <math>\mathbf{z}</math> will converge. | |||
====Algorithm==== | ====Algorithm==== | ||
# Randomly initialize labels <math>\mathbf{z}</math>. | |||
# Then calculate the centroids <math>\mathbf{\mu}</math>. | |||
# Then update the labels for each example to the closest centroid. | |||
# Update the centroids by taking the mean of every point in the cluster. | |||
# Repeat steps 3 and 4 | |||
===Soft K-means=== | ===Soft K-means=== | ||
We will develop a model for how our data is generated | We will develop a model for how our data is generated.<br> | ||
We will then find probabilities for each element being from a cluster (ala Bayesian paradigm).<br> | |||
Given <math>k</math> clusters, the probability of a point being from cluster k is <math>\phi_k = P(z^{(i)} = k)</math><br> | Given <math>k</math> clusters, the probability of a point being from cluster k is <math>\phi_k = P(z^{(i)} = k)</math><br> | ||
We will assume each cluster is from a normal distribution <math>N(\mu_j, \sigma_j)</math> | |||
====EM Algorithm==== | |||
Expectation Maximization<br> | |||
The key idea is to introduce intermediate coefficients to apply Jensen's inequality.<br> | |||
=====Maximum Likelihood===== | |||
Let <math>\theta_j = [\phi_j, \mu_j, \sigma_j]</math> denote our parameters.<br> | |||
The likelihood is <math>L(\theta) = \Pi_{i=1}^{m} P(x^{(i)}; \theta)</math> where <math>P</math> is our pdf/pmf.<br> | |||
Then the log-likelihood is <math>l(\theta) = \sum_{i=1}^{m} \log P(x^{(i)}; \theta) = \sum_{i=1}^{m} \log \sum_{j=1}^{k}P(x^{(i)}, z^{(i)}=j; \theta)</math><br> | |||
By introducing an extra variable <math>Q^{(i)}_{(j)}</math> we'll be able to apply Jensen's inequality to the concave log function.<br> | |||
Assume <math>Q^{(i)}{(j)}</math> is a probability mass function.<br> | |||
<math display="block"> | |||
\begin{align*} | |||
l(\theta) &= \sum_{i=1}^{m} \log \sum_{j=1}^{k}P(x^{(i)}, z^{(i)}=j; \theta)\\ | |||
&=\sum_{i=1}^{m} \log \sum_{j=1}^{k} \frac{Q^{(i)}_{(j)}}{Q^{(i)}_{(j)}} P(x^{(i)}, z^{(i)}=j; \theta)\\ | |||
&\geq \sum_{i=1}^{m} \sum_{j=1}^{k} Q^{(i)}_{(j)} \log(\frac{P(x^{(i)}, z^{(i)}=j; \theta) | |||
}{Q^{(i)}_{(j)}})\\ | |||
\implies \log\left[E_{Q}\left(\frac{P(x^{(i)}, q^{(i)}; \theta)}{Q^{(i)}_{(j)}}\right)\right] &\geq E_{Q} \left[ \log \left(\frac{P(x^{(i)}, q^{(i)}; \theta)}{Q^{(i)}(j)} \right)\right] | |||
\end{align*} | |||
</math><br> | |||
Let <math>J(\theta, Q) = \sum_{i=1}^{m} \sum_{j=1}^{k} Q^{(i)}_{(j)} \log \left( \frac{P(x^{(i)}, z^{(i)}=j;\theta)}{Q^{(i)}(j)} \right)</math><br> | |||
The EM algorithm is an iterative algorithm which alternates between an E-Step and an M-Step. | |||
=====E-Step===== | |||
We will fix <math>\theta</math> and maximize J wrt <math>Q</math>.<br> | |||
Jensen's inequality holds with equality iff either the function is linear or if the random variable is degenerate.<br> | |||
We will assume <math>\frac{P(x^{(i)}, z^{(i)}=j; \theta) | |||
}{Q^{(i)}_{(j)}}</math> is a constant.<br> | |||
This implies <math>Q^{(i)}(j) = c * P(x^{(i)}, z^{(i)} = j ; \theta)</math>.<br> | |||
Since Q is a pmf, we have <math>Q^{(i)}(j) = \frac{1}{P(x^{(i)})} * P(x^{(i)}, z^{(i)} = j ; \theta) = P(z^{(i)} ; x^{(i)}, \theta)</math><br> | |||
Q is updated with <math>Q^{(i)}(j) = \frac{P(z^{(i)}=j)P(x^{(i)}|z^{(i)}=j)}{P(x^{(i)})}</math> | |||
{{hidden | Maximization w.r.t Q | | |||
<math>J(\theta, Q) = \sum_{i=1}^{m} \sum_{j=1}^{k} Q^{(i)}_{(j)} \log \left( \frac{P(x^{(i)}, z^{(i)}=j;\theta)}{Q^{(i)}(j)} \right)</math><br> | |||
We are assuming that Q is a pmf so <math>\sum_j Q = 1 </math><br> | |||
Our lagrangian is:<br> | |||
<math> | |||
\max_{Q} \min_{\beta} \left[ \sum_{i=1}^{m} \sum_{j=1}^{k} Q^{(i)}_{(j)} \log \left( \frac{P(x^{(i)}, z^{(i)}=j;\theta)}{Q^{(i)}(j)} \right) +\beta (\sum_j Q^{(i)}_{(j)} - 1)\right] | |||
</math> | |||
We can maximize each <math>Q^{(i)}</math> independently.<br> | |||
Taking the derivative wrt Q we get:<br> | |||
<math display="block"> | |||
\begin{aligned} | |||
\frac{\partial}{\partial Q^{(i)}_{(j)}} \sum_{j=1}^{k} Q^{(i)}_{(j)} \log \left( \frac{P(x^{(i)}, z^{(i)}=j;\theta)}{Q^{(i)}(j)} \right) +\beta (\sum_j Q^{(i)}_{(j)} - 1) | |||
&= \log(\frac{P(x^{(i)}, z^{(i)}=j;\theta)}{Q}) - Q \frac{Q}{P(x^{(i)}, z^{(i)}=j;\theta)} (P(x^{(i)}, z^{(i)}=j;\theta))(Q^{-2}) + \beta\\ | |||
&= \log(\frac{P(x^{(i)}, z^{(i)}=j;\theta)}{Q}) - 1 + \beta \\ | |||
&= 0\\ | |||
\implies Q^{(i)}_{(j)} &= (\frac{1}{exp(1-\beta)})P(x^{(i)}, z^{(i)}=j;\theta) | |||
\end{aligned} | |||
</math><br> | |||
Since Q is a pmf, we know it sums to 1 so we get the same result replacing <math>(\frac{1}{exp(1-\beta)})</math> with <math>P(x^{(i)}</math> | |||
}} | |||
=====M-Step===== | |||
We will fix <math>Q</math> and maximize J wrt <math>\theta</math> | |||
<math>J(\theta, Q) = \sum_{i=1}^{m} \sum_{j=1}^{m} Q^{(i)}_{(j)} \log \left( \frac{P(x^{(i)}, z^{(i)}=j;\theta)}{Q^{(i)}(j)} \right)</math><br> | |||
Assume <math>\Sigma_j = I</math> for simplicity.<br> | |||
Then: | |||
<math display="block"> | |||
\begin{aligned} | |||
J(\theta, Q) &= \sum_{i=1}^{m} \sum_{j=1}^{m} Q^{(i)}_{(j)} \log \left( \frac{P(x^{(i)}, z^{(i)}=j;\theta)}{Q^{(i)}(j)} \right)\\ | |||
&= \sum_{i=1}^{m} \sum_{j=1}^{m} Q^{(i)}_{(j)} \log ( P(x^{(i)}, z^{(i)}=j;\theta)) + C_1 \\ | |||
&= \sum_{i=1}^{m} \sum_{j=1}^{m} Q^{(i)}_{(j)} \log ( P(x^{(i)} \mid z^{(i)}=j) P(z^{(i)}=j)) + C_1\\ | |||
&= \sum_{i=1}^{m} \sum_{j=1}^{m} Q^{(i)}_{(j)} \log ( P(x^{(i)} \mid z^{(i)}=j)) - Q^{(i)}_{(j)} \log( P(z^{(i)}=j)) + C_1\\ | |||
&= \sum_{i=1}^{m}\left[ \sum_{j=1}^{m} Q^{(i)}_{(j)} \log ( (2\pi)^{-n/2}exp(-\Vert x^{(i)} + \mu_j \Vert^2 / 2)) - Q^{(i)}_{(j)} \log( \phi_j) \right]+ C_1 \\ | |||
&= \sum_{i=1}^{m}\left[ \sum_{j=1}^{m} Q^{(i)}_{(j)} -\Vert x^{(i)} - \mu_j \Vert^2 / 2) + Q^{(i)}_{(j)} \log( \phi_j) \right]+ C_2 | |||
\end{aligned} | |||
</math><br> | |||
Maximizing wrt <math>\mu</math>, we get <math>\mu_j^* = (\sum_{i} Q^{(i)}_{(i)}x^{(i)}) / (\sum_{i}Q^{(i)}_{(j)})</math>.<br> | |||
Maximizing wrt <math>\phi</math> we get <math>\phi_j^* = \frac{1}{m} \sum_{i=1}^{m}Q^{(i)}_{(j)}</math><br> | |||
{{hidden | Maximization wrt phi| | |||
We want to maximize <math>Q^{(i)}_{(j)} \log( \phi_j)</math> subject to the condition <math>\sum \phi_j = 1</math> since <math>\phi_j = P(z^{(i)}=j)</math> is a pmf.<br> | |||
The lagrangian for this is <math>\max_{\phi_1,...,\phi_k} \min_{\beta} \left[ \sum_{i=1}^{m} \sum_{j=1}^{k}Q^{(i)}_{(j)} \log( \phi_j) + \beta(\sum_{j=1}^{k}\phi_j - 1) \right]</math><br> | |||
This can be rewritten as <math>\max_{\phi_1,...,\phi_k} \min_{\beta} \sum_{j=1}^{k}\left[\log( \phi_j) \sum_{i=1}^{m} Q^{(i)}_{(j)} + \beta(\phi_j - 1/k) \right]</math><br> | |||
The dual of this problem is <math> \min_{\beta} \max_{\phi_1,...,\phi_k} \sum_{j=1}^{k} \left[\log( \phi_j) \sum_{i=1}^{m} Q^{(i)}_{(j)} + \beta(\phi_j - 1/k) \right]</math><br> | |||
Taking the gradient w.r.t <math>\phi</math>, we get <math>\frac{1}{\phi_j}\sum_{i}Q^{(i)}_{(j)} + \beta = 0 \implies \phi_j = \frac{-1}{\beta}(\sum_{i}Q^{(i)}_{(j)})</math><br> | |||
Plugging this into our dual problem we get:<br> | |||
<math> \min_{\beta} \sum_{j=1}^{k} \left[\log(\frac{-1}{\beta}(\sum_{i}Q^{(i)}_{(j)})) \sum_{i=1}^{m} Q^{(i)}_{(j)} + \beta(\frac{-1}{\beta}(\sum_{i}Q^{(i)}_{(j)}) - 1/k) \right]</math><br> | |||
<math>= \min_{\beta} \sum_{j=1}^{k} \left[\log(\frac{-1}{\beta}(\sum_{i}Q^{(i)}_{(j)})) \sum_{i=1}^{m} Q^{(i)}_{(j)} -(\sum_{i}Q^{(i)}_{(j)}) - (\beta/k) \right]</math><br> | |||
Taking the derivative with respect to <math>\beta</math>, we get:<br> | |||
<math display="block"> | |||
\begin{aligned} | |||
\sum_{j=1}^{k} [(\frac{1}{(-1/\beta)(\sum Q)})(-\sum Q)(-\beta^{-2})(\sum Q) - \frac{1}{k}] | |||
&= \sum_{j=1}^{k} [ (\beta)(-\beta^{-2})(\sum Q) - \frac{1}{k}] \\ | |||
&= \sum_{j=1}^{k} [\frac{-1}{\beta}(\sum_{i=1}^{m} Q) - \frac{1}{k}]\\ | |||
&= [\sum_{i=1}^{m} \frac{-1}{\beta} \sum_{j=1}^{k}P(z^{(i)} = j | x^{(i)}) - \sum_{j=1}^{k}\frac{1}{k}]\\ | |||
&= [\frac{-1}{\beta}\sum_{i=1}^{m}1 - 1]\\ | |||
&= \frac{-m}{\beta} - 1 = 0\\ | |||
\implies \beta &= -m | |||
\end{aligned} | |||
</math><br> | |||
Plugging in <math>\beta = -m</math> into our equation for <math>\phi_j</math> we get <math>\phi_j = \frac{1}{m}\sum_{i=1}^{m}Q^{(i)}_{(j)}</math> | |||
}} | |||
===Mean-Shift=== | |||
===DBSCAN=== | |||
==Generative Models== | |||
Goal: Generate realistic but fake samples. | |||
Applications: Denoising, impainting | |||
===VAEs=== | |||
Variational Auto-Encoders<br> | |||
[https://arxiv.org/abs/1606.05908 Tutorial]<br> | |||
====KL Divergence==== | |||
* [[Wikipedia:Kullback–Leibler divergence]]<br> | |||
* Kullback–Leibler divergence<br> | |||
* <math>KL(P \Vert Q) =E_{P}\left[ \log(\frac{P(X)}{Q(X)}) \right]</math> | |||
; Notes | |||
* KL is always >= 0 | |||
* KL is not symmetric | |||
* Jensen-Shannon Divergence | |||
** <math>JSD(P \Vert Q) = \frac{1}{2}KL(P \Vert Q) + \frac{1}{2}KL(Q \Vert P)</math> | |||
** This is symmetric | |||
====Model==== | |||
Our model for how the data is generated is as follows: | |||
* Generate latent variables <math>z^{(1)},...,z^{(m)} \in \mathbb{R}^r</math> iid where dimension r is less than n. | |||
** We assume <math>Z^{(i)} \sim N(\mathbf{0},\mathbf{I})</math> | |||
* Generate <math>x^{(i)}</math> where <math>X^{(i)} \vert Z^{(i)} \sim N(g_{\theta}(z), \sigma^2 \mathbf{I})</math> | |||
** For some function <math>g_{\theta_1}</math> parameterized by <math>\theta_1</math> | |||
====Variational Bound==== | |||
The variational bound is: | |||
* <math>\log P(x^{(i)}) \geq E_{Z \sim Q_i}[\log P(X^{(i)} \vert Z)] - KL(Q_i(z) \Vert P(z))</math> | |||
{{hidden | Derivation | | |||
We know from Baye's rule that <math>P(z|X) = \frac{P(X|z)P(z)}{P(X)}</math>.<br> | |||
Plugging this into the equation for <math>KL(Q_i(z) \Vert P(z|X))</math> yields our inequality.<br> | |||
<math display="block"> | |||
\begin{aligned} | |||
KL(Q_i(z) \Vert P(z|X)) &= E_{Q} \left[ \log(\frac{Q_i(z)}{P(z|X)}) \right]\\ | |||
&=E_Q(\log(\frac{Q_i(z) P(X^{(i)})}{P(X|z)P(z)})\\ | |||
&=E_Q(\log(\frac{Q_i(z)}{P(z)})) + \log(P(x^{(i)})) - E_Q(\log(P(X|z))\\ | |||
&=KL(Q_i(z) \Vert P(z)) + \log(P(x^{(i)}) - E_Q(\log(P(X|z)) | |||
\end{aligned} | |||
</math> | |||
Rearranging terms we get:<br> | |||
<math>\log P(x^{(i)}) - KL(Q_i(z) \Vert P(z|X)) = E_Q(\log(P(X|z)) - KL(Q_i(z) \Vert P(z))</math><br> | |||
Since the KL divergence is greater than or equal to 0, our variational bound follows. | |||
}} | |||
===GANs=== | |||
{{main | Generative adversarial network}} | |||
====Wasserstein GAN==== | |||
[https://arxiv.org/abs/1701.07875 Paper]<br> | |||
The main idea is to ensure the that discriminator is lipschitz continuous and to limit the lipschitz constant (i.e. the derivative) of the discriminator.<br> | |||
If the correct answer is 1.0 and the generator produces 1.0001, we don't want the discriminator to give us a very high loss.<br> | |||
;Earth mover's distance | |||
{{main | wikipedia:earth mover's distance}} | |||
The minimum cost of converting one pile of dirt to another.<br> | |||
Where cost is the cost of moving (amount * distance)<br> | |||
Given a set <math>P</math> with m clusters and a set <math>Q</math> with n clusters:<br> | |||
... | |||
<math>EMD(P, Q) = \frac{\sum_{i=1}^{m}\sum_{j=1}^{n}f_{i,j}d_{i,j}}{\sum_{i=1}^{m}\sum_{j=1}^{n}f_{i,j}}</math><br> | |||
;Notes | |||
* Also known as Wasserstein metric | |||
==Dimension Reduction== | |||
Goal: Reduce the dimension of a dataset.<br> | |||
If each example <math>x \in \mathbb{R}^n</math>, we want to reduce each example to be in <math>\mathbb{R}^k</math> where <math>k < n</math> | |||
===PCA=== | |||
Principal Component Analysis<br> | |||
Preprocessing: Subtract the sample mean from each example so that the new sample mean is 0.<br> | |||
Goal: Find a vector <math>v_1</math> such that the projection <math>v_1 \cdot x</math> has maximum variance.<br> | |||
Result: These principal components are the eigenvectors of <math>X^TX</math>.<br> | |||
Idea: Maximize the variance of the projections.<br> | |||
<math>\max \frac{1}{m}\sum (v_1 \cdot x^{(i)})^2</math><br> | |||
Note that <math>\sum (v_1 \cdot x^{(i)})^2 = \sum v_1^T x^{(i)} (x^{(i)})^T v_1 = v_1^T (\sum x^{(i)} (x^{(i)})^T) v_1</math>.<br> | |||
<!-- | |||
Thus our lagrangian is <math>\max_{\alpha} v_1^T (\sum x^{(i)} (x^{(i)})^T) v_1 + \alpha(\Vert v_1 \Vert^2 - 1)</math><br> | |||
Taking the gradient of this we get:<br> | |||
<math>\nabla_{v_1} (v_1^T (\sum x^{(i)} (x^{(i)})^T) v_1) + \alpha(\Vert v_1 \Vert^2 - 1)</math><br> | |||
<math>= 2(\sum x^{(i)} (x^{(i)})^T) v_1 + 2\alpha v_1</math> | |||
--> | |||
===Kernel PCA=== | |||
{{main | Wikipedia: Kernel principal component analysis}} | |||
===Autoencoder=== | |||
You have a encoder and a decoder which are both neural networks. | |||
==Resources== | |||
;Clustering | |||
* [https://towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68 TowardsDataScience: top 5 clustering algos] | |||
* [https://machinelearningmastery.com/clustering-algorithms-with-python/ MachineLearningMastery: Clustering Algorithms] |