\documentclass[12pt,fullpage]{article}

\usepackage{graphicx}
\newcommand{\yy}[1]{\textit{TODO: {#1}}}
\newcommand{\vek}[1]{\textbf{{#1}}}
\newcommand{\trm}[1]{\textit{{#1}}}
\newcommand{\rwr}{\textit{{RWR}}}
\newcommand{\vrwr}{\textbf{{RWR}}}

\begin{document} 

\title{Semi-Supervised Learning: Lecture Notes}
\author{William W. Cohen}

\maketitle

\section{What is Semi-Supervised Learning?}

\begin{figure}
\centerline{\includegraphics[width=0.4\textwidth]{./figs/Slide1.png}~\includegraphics[width=0.4\textwidth]{./figs/Slide2.png}~\includegraphics[width=0.4\textwidth]{./figs/Slide3.png}}
\caption{\small Cartoon suggesting why unlabeled examples might be
  helpful in learning.  (A) If there are few labeled examples,
  learning a classifier is unconstrained---many different classifiers
  separate the data equally well. (B) If unlabeled examples are added,
  then the choice of classifier may become more obvious; for instance,
  if we assume that the labeled examples are drawn from two
  well-separated clusters, learning becomes nearly as constrained as
  in supervised learning with many examples (C).} \label{fig:cartoon}
\end{figure}

In \trm{supervised learning}, a learner is given a dataset of $m$ labeled
examples 
\[ \{ (\vek{x}^1,y^1), \ldots, (\vek{x}^m,y^m) \} 
\] 
and constructs a function $f$ which predicts a label $y$ for an unseen
test example $\vek{x}$, i.e., $\hat{y}=f(\vek{x})$.  In
\trm{semi-supervised learning} (SSL) the learner has an additional
input: a set of $n$ unlabeled examples $\{ \vek{x}^{m+1}, \ldots,
\vek{x}^{m+n} \}$.  Figure~\ref{fig:cartoon} suggests how this can be
helpful.

\begin{figure}
\centerline{\includegraphics[width=0.5\textwidth]{./figs/Slide4.png}~\includegraphics[width=0.5\textwidth]{./figs/Slide5.png}}
\caption{\small Graphs based on similarity edges (A) and coupling
  edges (B).} \label{fig:edge-types}
\end{figure}

There are several different paradigms for SSL
\cite{zhu2009introduction}.  Here I will focus on \trm{graph-based
  SSL} \cite{subramanya2014graph}. Here the examples (both labeled and
unlabeled) are organized in a graph.  I will assume $W$ is a matrix
such that $W[i,j]$ is the weight of the edge between $\vek{x}_i$ and
$\vek{x}_j$, and weights are always positive.  This graph can be
constructed in many ways, but usually it is sparse (i.e., most edges
have weight zero).  Here are some common cases.
\begin{itemize}
\item \trm{Similarity edges:} All nodes in the graph are examples, and
  $W[i,j]$ measures similarity between examples $i$ and $j$.
  Figure~\ref{fig:edge-types}(A) shows an example of this, where the
  examples are images of digits, taken from \cite{zhu2003semi}.  Note
  that some of the nodes in the graph have labels, and some do not.
\item \trm{Network edges:} All nodes in the graph are examples,
  $W[i,j]$ indicates that some relationship holds between the 
  examples. For instance, the examples are web sites, and
  $W[i,j]=1$ if there is a hyperlink from from site $i$ to site $j$.
\item \trm{Coupling-node edges:} The graph is a bipartite graph, and
  some nodes are examples, and the other nodes correspond to sets of
  example.  As an example, in \cite{talukdar2010experiments}
  text-mining was performed on a large corpus, looking for phrases
  like ``songwriters such as Bob Dylan'' or ``singers such as Billy
  Joel''.  This was used to create a graph with nodes of two types:
  categories (``songwriters'', ``singers'', \ldots) and examples
  (``Bob Dylan'', ``Billy Joel'', \ldots).  Edges connect a category
  nodes to member of that category, with weights derived from
  frequency in the corpus.  Figure~\ref{fig:edge-types}(B) shows an
  example of this from \cite{talukdar2010experiments}.
\end{itemize}

Note that only some of the nodes in the graph are labeled. The
initially-labeled nodes are sometimes called ``seeds''.  Graph-based
SSL is often called \trm{label propagation} (LP), with the intuition
that labels ``propagate'' from the seeds through the graph along the
edges, thus associating labels with initially-unlabeled nodes.  Label
propagation is generally a ``soft'' iterative process, where in each
iteration, some real-number scores, each representing confidence in a
particular label at a particular node, are propagated through the
graph.

\section{MultiRank Walk: A Sample LP Algorithm}

\begin{figure}
\centerline{\includegraphics[width=0.8\textwidth]{./why-mrw.png}}
\caption{\small Some sample graphs to motivate a particular graph
  propagation scheme} \label{fig:why-mrw}
\end{figure}

Let us first look at this problem intuitively, and ask: when does it
make sense that a label from $\vek{x}_i$ should be ``propagated''
(transferred) to a connected node $\vek{x}_j$?  More interestingly,
when should labels be propagated over a path consisting of multiple
edges? 

Figure~\ref{fig:why-mrw} shows three subgraphs, each of which contains
two seeds with red and green labels, and a starred node which is
connected to both red and green seeds.  However, in each case, we
argue it is more plausible to associate the starred node with the
green label.
\begin{itemize}
\item In subgraph (A), the path to the green seed is shorter than the
  path to the red seed.
\item In subgraph (B), every path to a seed is of length two, but
  there are more paths to the greed seed than to the red seed.  Put
  another way, define ${\cal N}(i)$ to be the set of nodes that are
  neighbors of $i$, and suppose that shared neighbors of two graph
  nodes indicate similarity, such as shared words of two documents
  indicate similarity.  The starred node has three common neighbors
  with the green seed, and only one common neighbor with the red one.
\item In subgraph (C), there is exactly one length-two path to each of
  the seeds, and the starred node has exactly one common neighbor with
  each seed. But there is an important difference: the common neighbor
  with the red node is a common neighbor for many pairs of nodes.
  Again treating common neighbors as analogous to words, this would be
  like two documents sharing a common word (like ``the'') rather than
  a rare one (like ``aardvark'').  This suggests that the starred node
  should ultimately receive the green label, not the red label, after
  propagation.
\end{itemize}

We now ask: is there any simple algorithmic definition of graph
similarity that is consistent with these intuitions? It turns out
there is: they are all consistent with random-walk-with-reset (RWR)
distance, also known as personalized PageRank.  

Let's start by defining the following random process, parameterized by
a set of seed nodes $S$ and a reset probability $c$:
\begin{enumerate}
\item Draw node $V_0$ uniformly at random from $S$ (notice $V_0$ is a
  random variable here)
\item For $t=0,\ldots,T$:
  \begin{enumerate}
  \item with probability $c$, draw node $V_{t+1}$ uniformly at random from $S$;
  \item otherwise, draw\footnote{Hence we are assuming here that every
    node has some outlinks.  Sometimes this is enforced by having
    every node link to itself.} node $V_{t+1}$ from the neighbors of
    $V_t$, weighted by the weight of the edge from $V_{t}$ to
    $V_{t+1}$.
  \end{enumerate}
\end{enumerate}
This is the same as the random surfer model used in PageRank, except
that the ``teleport'' steps always jump to a seed.  Ignore for a
minute the parameter $c$, and define
\[ \rwr_{S}(j) \equiv \lim_{T \rightarrow \infty} \Pr(V_T = j)
\]
Finally the vector $\vrwr_{S}$ is the vector of these values over all
nodes, i.e.
\[ \vrwr_{S} = \langle \rwr_{S}(1),\rwr_{S}(2),\ldots,\rwr_{S}(m+n) \rangle
\]
where the nodes of the graph are named with integers $1,\ldots,m+n$.

One way to approximate $\vrwr_S$ is let $\vek{s}$ be a row vector which
is uniform over the seeds $S$, and let $W'$ be a column-normalized version
of $W$: i.e., 
\[ W'[i,j] = \frac{W[i,j]}{\sum_k W[i,k]}
\]
Let $\vek{v}^0 = \vek{s}$, and then repeatedly do this
update:
\[
 \vek{v}^{t+1} = c\vek{s} + (1-c) \vek{v}^t W'
\]
If $\vek{s}$ was uniform over the whole graph (not just the nodes in
$S$) then this would be exactly the update used to compute ordinary
PageRank.  In practice this converges quickly: the effect of long
paths on $\rwr_{S}$ is small because the probability of not doing a
reset in $n$ steps is $(1-c)^n$, which shrinks exponentially.  As
discussed in class, this update operation can also be done using
map-reduce for very large graphs.

Now let's look go back to Figure~\ref{fig:why-mrw} and consider two
seeds sets, $G$ and $R$ (for green and red) which contain just one
node each. Let $i^*$ be the index of the starred node, and also
suppose that each edge is bidirectional, so our random walks don't hit
any ``dead ends'', and that the edge weights are all equal.  We can
see that propagating labels using RWR satisfies the intuitions
discussed above:
\begin{itemize}
\item In subgraph (A), $\rwr_{G}[i^*] > \rwr_{R}[i^*]$ because $\rwr$
  is dominated by the number of short random walks, and the path from
  $i^*$ to the green seed is shorter than the path to the red seed.
\item In subgraph (B), $\rwr_{G}[i^*] > \rwr_{R}[i^*]$ because $\rwr$
  is dominated by the short random walks, and there are \textit{more}
  short paths to the green seed.
\item In subgraph (C), $\rwr_{G}[i^*] > \rwr_{R}[i^*]$ because a
  random walk from the red seed needs to go through a high-fanout
  ``hub'' node, and the probability of moving toward the starred node
  from this hub is low.
\end{itemize}

This suggests that we can use $\rwr_{G}[i]$ (respectively
$\rwr_{R}[i]$) a measure of how much the the green (respectively red)
label should be propagated to $i$.  So we have now motivated the
following simple LP method.
\begin{enumerate}
\item For classes $y_1,\ldots,y_K$:
  \begin{enumerate}
  \item Let $S_k$ be the seeds for class $y_k$
  \item Compute \( \vrwr_{S_k} \)
  \end{enumerate}
\item For each unlabeled graph node $j$:
  \begin{itemize}
  \item Predict the class $y_k$ where \( k = argmax_{k'} ~ \vrwr_{S_k'}[j] \)
  \end{itemize}
\end{enumerate}

This approach is called the \textit{MultiRank Walk} (MRW) algorithm,
and it works reasonably well in a wide range of
settings \cite{lin2010semi}.

Note that in MRW, nodes don't need to have any features (although
features of the examples $\vek{x}_i$ might have been used in creating
the graph initially---e.g., in the graph might include similarity
edges computed where similarity was computed using features.)  This is
also true for the other LP methods we'll discuss here.


\section{Graph-based SSL as optimization}

For MRW, we took an existing propagation method (based on PageRank)
and argued that it was an intuitively reasonable way to propagate
labels.  Some LP schemes also arise as solutions to certain simple
ptimization criterion.

Remember in our notation, the first $m$ examples are labeled and
examples $m+1 \ldots m+n$ are unlabeled. For a binary classification
task, let us use $y=+1$ for a positive examples and $y=-1$ for a
negative example.  Labeling the unlabeled examples (softly) simply
means that we will assign a real-number ``soft'' prediction
$\hat{y}_i$ every label.  One plausible goal would be to make these
predictions consistent with the labeled examples, also try to minimize
degree to which connected nodes are given different labels---i.e., to
minimize the following loss on the unlabeled examples:
\begin{equation} \label{eq:smooth}
  Loss = \sum_{i>m,j>m} W[i,j](\hat{y}_i - \hat{y}_j)^2
\end{equation}
This loss expresses a sort of ``smoothness'' constraint on our labels:
the predicted labels for nodes connected by an edge should be similar.

I will now assume that $W[i,j]=W[j,i]$---which makes sense if a weight
indictes similarity of two nodes.  With a little algebra, we can write
the smoothness penalty $L$ in matrix form.  To simplify I'll write
$w_{ij}$ for $W[i,j]$, define $d_i = \sum_j w_{i,j}$, and let $D$ be a
diagonal matrix where $D_{i,i}=d_i$.  I will also ignore the
complicated indexing $i>m,j>m$ below.  Then
\begin{eqnarray*}
 Loss & = & \sum_{i,j} w_{i,j}(\hat{y}_i - \hat{y}_j)^2 \\
   & = & \sum_{i,j} w_{i,j}\hat{y}_i^2 + \sum_{i,j} w_{i,j}\hat{y}_j^2 - 2\sum_{i,j} w_{i,j}\hat{y}_i\hat{y}_j \\
   & = & \sum_i (\sum_j w_{i,j}) \hat{y}_i^2 + \sum_j (\sum_i w_{i,j}) \hat{y}_j^2 - 2\sum_{i,j} w_{i,j}\hat{y}_i\hat{y}_j \\
   & = & \sum_i d_i \hat{y}_i^2 + \sum_j d_j \hat{y}_j^2 - 2\sum_{i,j} w_{i,j}\hat{y}_i\hat{y}_j \\
   & = & 2 \sum_i d_i \hat{y}_i^2  - 2\sum_{i,j} w_{i,j}\hat{y}_i\hat{y}_j \\
   & = & 2 (\sum_i d_i \hat{y}_i^2  - \sum_{i,j} w_{i,j}\hat{y}_i\hat{y}_j) \\
   & = & 2 (\hat{\vek{y}}^T D \hat{\vek{y}} - \hat{\vek{y}}^T W \hat{\vek{y}}) \\
   & = & 2 \hat{\vek{y}}^T (D - W) \hat{\vek{y}}
\end{eqnarray*}
We'll go ahead and drop the factor of 2, which doesn't make a
difference since at the end we want to just minimize subject to a
constraint, and let $S$ be another diagonal matrix which tells where
the seeds are: i.e., $S_{i,i}=1$ for $i\leq m$ and $S_{i,i}=0$
otherwise.  Then the final optimization problem is
\begin{equation} \label{eq:hf}
 \mbox{minimize~} \hat{\vek{y}}^T (D - W) \hat{\vek{y}} \mbox{~subject to the constraint~} S\hat{\vek{y}}=S{\vek{y}}
\end{equation}

(A side note: $\hat{\vek{y}}^T (D - W) \hat{\vek{y}}$ is often written
as $\hat{\vek{y}}^T L \hat{\vek{y}}$ where the matrix $L=(D-W)$ is
called the ``graph Laplacian''.  I'm going to avoid this notation for
now so we don't confuse this $L$ with a loss function.)

There is a simple iterative algorithm to solve Eq~\ref{eq:hf}.  
\begin{enumerate}
\item Let $\hat{\vek{y}}^0$ be any label assignment consistent with
  the seed labels.
\item For $t=0,\ldots,T$:
  \begin{enumerate}
    \item For every unlabeled node $i>m$, let $\hat{y}^{t+1}_i = \frac{1}{d_i} \sum_{j} w_{i,j} \hat{y}^t_j$
    \item For every labeled node $i\leq m$, let $\hat{y}^{t+1}_i = y_i$ (where $y_i$ is the seed label for example $i$).
   \end{enumerate}
\end{enumerate}

This algorithm is very simple and natural: in each iteration, you
simply replace each node's value with the weighted average of its
neighbor's values (while keeping the seed nodes unchanged).  This
method has been invented at least three times with different
motivations, and has many names.
\begin{itemize}
\item Zhu, Gharamani and Lafferty \cite{zhu2003semi} motivate it as an
  optimization problem (as we did above).  They called the method
  \trm{Gaussian harmonic fields} (GHF), because after you converge, in
  iteration $T$, it should be true that
\[ \hat{y}^{T}_i = \frac{1}{d_i} \sum_{j} w_{i,j} \hat{y}^T_j
\]
or in other words, each prediction $\hat{y}^{T}_i$ is the weighted
average of the predictions for its neighbors. This is called the
``harmonic property''.  Not everyone liked that name, and other
researchers have cited \cite{zhu2003semi} and called the method
``harmonic fields'' (HF) or ``ZGL-LP''.
\item Around the same time, Mackassy and Provost
  \cite{macskassy2003simple} presented results with the same method,
  which they called the \trm{relational neighbor} algorithm (RN) and
  later used the even catchier name \trm{weighted-vote relational
    neighbor} algorithm (wvRN) \cite{macskassy2007classification}
\item Earlier, Nigam and Ghani \cite{nigam2000understanding} presented
  a variant of co-training called co-EM which is algorithmically the
  same (although the presentation assumes a coupling-node graph).
\end{itemize}


\section{Other optimization criteria}

There are many variations of this optimization-based algorithm.  For
instance, Eq~\ref{eq:hf} can be extended to multilabel tasks by
introducing $K$ different label vectors
$\hat{\vek{y}}_1,\ldots,\hat{\vek{y}}_K$ and solving this optimization problem:
\[
 \mbox{minimize~} \sum_{k=1}^K \hat{\vek{y}_k} (D - W) \hat{\vek{y}_k} 
    \mbox{~subject to the constraint~} \forall k, S\hat{\vek{y}_k}= \vek{y}_k
\]
You can relax the hard constraint that the predictions match the seeds
precisely. For instance you can simply minimize the loss
\begin{eqnarray}
 Loss_2 & =  & \mu_1 \sum_{i=1}^m (\hat{y}_i - y_i)^2 + \mu_2 \hat{\vek{y}}^T (D - W) \hat{\vek{y}} \nonumber \\
        & =  & \mu_1 (\hat{\vek{y}} - \vek{y})^T S (\hat{\vek{y}} - \vek{y}) + \mu_2 \hat{\vek{y}}^T (D - W) \hat{\vek{y}} \label{eq:soft-constraint}
\end{eqnarray}
Here $\mu$ is a parameter that determines how to trade off the
``smoothness'' part of the loss with the soft constraint on matching
seeds.

Eq~\ref{eq:hf} doesn't make any distinction between high-fanout
``hub'' nodes and other nodes.  One approach to making such a
distinction is to modify the smoothness penalty of Eq~\ref{eq:smooth} to
\begin{equation} \label{eq:hub}
  Loss_3 = \sum_{m+1}^n \sum_{i,j} w_{i,j}\left( \frac{\hat{y}_i}{f(d_i)} - \frac{\hat{y}_j}{f(d_j)} \right)^2
\end{equation}
where $f(d)$ is some appropriate way of scaling down the impact of
high-degree nodes based on their degree: for instance, $f(d)=\sqrt{d}$
is used in the \trm{local and global consistency} algorithm
\cite{zhou2004learning}.  This formula downweights label disagreements
that involve one or more high-degree node.

Another approach to handling ``hubs'' is to introduce vector of biases $\vek{r}_k$ that
pushes each node toward a particular class, and trade closeness to the
bias vectors off against the usual smoothness criterion.  
\[
  Loss_4 = \sum_{k=1}^K \mu_1 \hat{\vek{y}_k}^T (D - W) \hat{\vek{y}_k}  +  \mu_2 (\hat{\vek{y}_k} - \vek{r}_k)
\]
These bias vectors can be used to push the labels of certain unlabeled
nodes towards a special ``unknown'' or ``dummy'' label.  If one uses
$\vek{r}$ to push high-degree nodes toward a dummy label, then an
effect similar Eq~\ref{eq:hub} is obtained.  In
\cite{talukdar2010experiments} this loss function is combined with the
agreement constraint of Eq~\ref{eq:soft-constraint} to get the
following loss
\[
  Loss_4 =  \mu_1 (\hat{\vek{y}} - \vek{y})^T S (\hat{\vek{y}} - \vek{y}) + \mu_2 \hat{\vek{y}}^T (D - W) \hat{\vek{y}}
       + \mu_3 (\hat{\vek{y}_k} - \vek{r}_k)
\]
All of these optimization criterion have iterative update schemes similar to the ones shown above.

\bibliography{graph-ssl}
\bibliographystyle{plain}

\end{document} 
