In the paper Semi-supervised learning by mixed label propagation Wei Tong and Rong Jin define

$S$ as the similarity(adjacency) matrix
$D = \operatorname{diag}(D_1, D_2, \ldots, D_n)$ where $D_i = \sum_{j=1}^nS_{i,j}$
class assignment $\textbf{y} = (y_1, y_2, \ldots, y_n)$

Given the class labels of $n_l$ examples, $\widehat{y}_l = (\widehat{y}_1, \widehat{y}_2,\ldots,\widehat{y}_{nl})$, the optimal class assignment y is found by minimizing the energy function


where $E(S, \textbf{y}) = \sum_{i, j=1}^n S_{ij}(y_i - y_j)^2 = \textbf{y}^TL \textbf{y}, L = D - S$. How to find $y_u$? I have tried the following.

\begin{align} E(S, \textbf{y}) & = \begin{bmatrix} y_l & y_u \end{bmatrix} \begin{bmatrix} L^{l, l} & L^{l, u}\\ L^{u, l} & L^{u, u}\\ \end{bmatrix} \begin{bmatrix} y_l \\ y_u \end{bmatrix} \\[6pt] & = \begin{bmatrix} y_l & y_u \end{bmatrix} \begin{bmatrix} L^{l, l}y_l + L^{l, u}y_u\\ L^{u, l}y_l + L^{u, u}y_u\\ \end{bmatrix} \\[6pt] & = y_l^TL^{l, l}y_l + y_l^TL^{l, u}y_u + y_u^TL^{u, l}y_l + y_u^TL^{u, u}y_u \end{align}

when I take the derivative w.r.t $y_u$ I don't understand how to differentiate $y_u^TL^{u, l}y_l$. Following this method,

$$(y_u + h)^TL^{u, l}y_l - y_u^TL^{u, l}y_l = h^TL^{u, l}y_l$$

Now, how to divide by $h$.

Also if this is not the correct way, how to find $y_u$ then?


1 Answer 1


Thanks to this answer.
As $L$ is symmetric, \begin{align} \frac{d (E(S, \textbf{y}))}{d y_u} = 0 + y_l^TL^{l,u} + (L^{u,l}y_l)^T + y_u^TL^{u, u} + (L^{u, u}y_u)^T = 0 \\ 2 y_l^T L^{L, u} + 2y_u^T L^{u, u} = 0 \\ y_u = -(L^{u,u})^{-1}L^{u,l}y_l \end{align}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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