【Machine Learning】Unsupervised Learning

Principle Component Analysis

• Dimension reductio: JL lemma $d=\Omega \left(\frac{\log n}{{ϵ}^2}\right)$ to remain the distance of $n$ data points.
• Goal of PCA
  • maximize variance: $\mathbb{E}[(v^{\top }x{)}^2]=v^{\top }X{X}^{\top }v$ for $|v|=1$
  • minimize reconstruction error: $\mathbb{E}[|x-(v^{\top }x)v{|}^2]$
• Find $v_i$ iteratively, project data points onto subspace expanded by $v_1,v_2,..,v_d$
• How to find $v$ ?
  • Eigen decomposition: $X{X}^{\top }=U\Sigma U^{\top }$
  • $v_1$ is the eigenvector of maximum eigenvalue.
  • Power method

Nearest Neighbor Classification

• KNN: K-nearest neighbor
• nearest neighbor search: Locality sensitive hashing algorithm(LSH)*
  • Randomized $c$-approximate $R$-near neighbor($(c,R)$-NN): A data structure that at least gives a $cR$ neighbor in some probability if $R$ neighbor exists.
  • A family $H$ is called $(R,cR,P_1,P_2)$-sensitive if for any $p,q\in {\mathbb{R}}^d$
    • if $|p-q|\le R$, then ${\mathrm{Pr}}_H[h(q)=h(p)]\ge P_1$
    • if $|p-q|\ge cR$, then ${\mathrm{Pr}}_H[h(q)=h(p)]\le P_1$
    • $P_1>P_2$
  • Algroithm based on LSH family:
    • Construct $g_i(x)=(h_{i,1}(x),h_{i,2}(x),...,h_{i,k}(x)),1\le i\le L$. All $h_{i,j}$ are iid from $H$.
    • Check the element in the bucket of $g_i(q)$, whether it’s $cR$-near neighbor of $q$. Until we check $2L+1$ times.
    • if $R$ neighbor exists, w.p. at least $\frac{1}{2}-\frac{1}{e}$ find $cR$-neighbor
    • $\rho =\frac{\log 1/P_1}{\log 1/P_2},k={\log }_{1/P_2}(n),L=n^{\rho }$
    • Proof

Metric Learning

• project $x_i$ into $f(x_i)$
• Hard version(compare label of its neighbor)- soft version
• Neighborhood Component Analysis(NCA)
  • $p_{i,j}\sim \exp (-\Vert f(x_i)-f(x_j){\Vert }^2)$
  • maximize ${\sum }_i{\sum }_{j\in C_i}{p}_{i,j}$
• LMNN: $L=\max (0,\Vert f(x)-f(x^{+}){\Vert }_2-\Vert f(x)-f(x^{-}){\Vert }_2+r)$
  • $x^{+},x^{-}$ are worst cases.
  • r is margin

Spectral Cluster

• K-means
• Spectral graph clustring
  • Graph laplacian: $L=D-A$, $A$ represents the similarity.
  • #zero eigenvalue = # connected component
  • Smallest $k$ eigenvectors gives a partition of $k$ clusters, do $k$-means on the row
  • Ratio cut can be transfered into finding the $k$ smallest eigenvectors, which is the same as graph laplacian.

SimCLR*

• Intelligence is positioning

• InfoNCE loss
  L ( q , p 1 , { p i } i = 2 N ) = − log ⁡ exp ⁡ ( − ∥ f ( q ) − f ( p 1 ) ∣ 2 / ( 2 τ ) ∑ i = 1 N exp ⁡ ( − ∥ f ( q ) − f ( p i ) ∣ 2 / ( 2 τ ) L(q,p_1,\{p_i\}_{i=2}^N)=-\log \frac{\exp(-\|f(q)-f(p_1)|^2/(2\tau)}{\sum_{i=1}^{N}\exp(-\|f(q)-f(p_{i})|^2/(2\tau)} L(q,p1​,{pi​}i=2N​)=−log∑i=1N​exp(−∥f(q)−f(pi​)∣2/(2τ)exp(−∥f(q)−f(p1​)∣2/(2τ)​

• Learn $Z=f(x)$: map original data points into a space that semantic similarity is captured naturally.

  • Reproducing kernel Hilbert space: $k(f(x_1),f(x_2))=⟨\varphi (f(x_1)),\varphi (f(x_2)){⟩}_H$. Inner product is a kernel function.
  • Usually, $K_{Z,i,j}=k(Z_i-Z_j)$, $k$ is gaussian.

• We have a similarity matrix $\pi$ about the dataset previously. ${\pi }_{i,j}$ is the similarity of data $i$ and $j$. We want the similarity matrix $K_Z$ of $f(x)$ is the same as that of $x$ which is given manually. Let $W_X\sim \pi ,W_Z\sim K_Z$, we want these two samples are the same.

• Minimize crossentropy loss: $H_{\pi }^k(Z)=-{\mathbb{E}}_{W_X\sim P(\cdot ;\pi )}[\log P(W_Z=W_X;K_Z)]$

  • Equivalent to InfoNCE loss: Only care about row $i$, infoNCE loss is $\log (W_{Z,i}=W_{X,i})$. The given pair $q,p_1$ are sampled from similarity matrix $\pi$, which corresponds to $W_X\sim P(\cdot ;\pi )$.
  • Equivalent to spectral clustering: equaivalent to $\arg {\min }_{Z}tr(Z^{\top }{L}^{\ast }Z)$

t-SNE

• data visualization: map data into low dimension space(2D)

• SNE: Same as NCA, want $q_{i,j}\sim \exp (-\Vert f(x_i)-f(x_j){\Vert }^2/(2{\sigma }^2))$ to be similar to $p_{i,j}\sim \exp (-\Vert x_i-x_j{\Vert }^2/(2{\sigma }_i^2))$

  • CrossEntropy loss $-p_{i,j}\cdot \log \frac{q_{i,j}}{p_{i,j}}$

• Crowding problem

• Solved by t-SNE: let $q_{i,j}\sim (1+\Vert y_j-y_i{\Vert }^2{)}^{-1}$(student t-distribution)

  • The power $-1$ is more heavy tail than Gaussian, then we can solve the crowding problem by shifting the distance.