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$


$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.


1 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.