Confusion related to semisupervised learning in random walk

Question

I am trying to understand the semi supervised learning in random walk. Lets say I have 10 classes and I have some labelled and unlabelled points. Now, I need to find the labels for the unlabelled points using semi supervised learning in random walk.

I can define the transition matrix P for the nodes/elements such that every entry $P_{ij}$ gives the probability of moving from node i to j. Now its given that I can propagate the labels. If P is transition matrix, I can have P resetted to

P = $$P_{ll} P_{lu}$$ $$P_{ul} P_{uu}$$

and if Y represents a matrix of probability distributions over the label set, then I can use the following iterative algorithm to get the labels for the unlabelled points. Let say $Y_l$ be the set of labelled points given and $Y_u$ be the set of unlabelled points for which we have to find the labels. Lets says there are ten labelled points given for the 10 labels and I have to find the labels for the remaining 100 points lets say, then there is this iterative algorithm

$Y^{0} \leftarrow Y$

$t \leftarrow 1$

repeat

$Y^{t} \leftarrow PY^{t-1}$

$Y_{l}^{t} \leftarrow Y_{l}$

until convergence to $Y^\inf$

$\tilde{Y} \leftarrow Y^{inf}$

I didn't get how to initialize this Y vector at the beginning. Lets say I have 110 points given. I have label 1.2.3...10 for the ten points, then how am I going to initialize this Y matrix and in the end when I get $\tilde{Y}$ how will I know which class it belongs to. I mean I will just have some values. How am I going to know which class the unlabelled points from $\tilde{Y}$ belong to. If it had been binary I would have known, because if the value was greater than 0.5, I would have said it belongs to class 1 otherwise 0. But what in the case when I have ten labels.

Answer 1

Consider you have $n$ data points (or examples) of which $l$ are labeled and $u$ are unlabeled with $l \ll n$ and $ n = l + u $. Also, assume you have $m$ classes. Let us assign an $m$-dimensional label vector $\mathbf{y}_i \in [1, 0]^m$ with data point $i$. You can interpret the $j$th element of $\mathbf{y}_i$ as the probability of point $i$ belonging to class $j$. For labeled examples, you can set $y_{ij} = 1.0$ if $j$ is the label and $0$ otherwise. For unlabeled examples, in theory, it really does not matter what you initialize. Let $\mathbf{Y} \in [0, 1]^{n\times m}$ represent label vectors for the entire dataset (labeled and unlabeled). Further, let's use a superscript notation $\mathbf{Y}^{(k)}$ to denote this label matrix for iteration $k$.

We can start with $\mathbf{Y}^{(0)}$ as described above. The power-iteration method will let us calculate the value of this label matrix at iteration $t+1$ from its value at iteration $t$ as follows:

$\mathbf{Y}^{(t+1)} = \mathbf{P}\mathbf{Y}^{(t)}$

Let $\hat{\mathbf{Y}}$ be the value of this label matrix after convergence or, as is the practice, after a finite number of iterations. The $i$th row of this matrix represents the learnt label vector for example $i$, also known as the label posterior. The MAP label assignment for example $i$ would be:

$\hat{k} = \arg\max_{\displaystyle k} \hat{\mathbf{Y}}_{ik}$.