Brief Introduction of Label Propagation Algorithm

bebound@gmail.com (KK) — Sun, 16 Jul 2017 21:45:00 +0800

As I said before, I’m working on a text classification project. I use doc2vec to convert text into vectors, then I use LPA to classify the vectors.

LPA is a simple, effective semi-supervised algorithm. It can use the density of unlabeled data to find a hyperplane to split the data.

Here are the main stop of the algorithm:

Let $ (x_1,y1)…(x_l,y_l)$ be labeled data, $Y_L = \{y_1…y_l\} $ are the class labels. Let $(x_{l+1},y_{l+u})$ be unlabeled data where $Y_U = \{y_{l+1}…y_{l+u}\}$ are unobserved, usually $l \ll u$. Let $X=\{x_1…x_{l+u}\}$ where $x_i\in R^D$. The problem is to estimate $Y_U$ for $X$ and $Y_L$.
Calculate the similarity of the data points. The most simple metric is Euclidean distance. Use a parameter $\sigma$ to control the weights.

\[w_{ij}= exp(-\frac{d^2_{ij}}{\sigma^2})=exp(-\frac{\sum^D_{d=1}{(x^d_i-x^d_j})^2}{\sigma^2})\]

Label Propagation on KK's Blog (fromkk)