\documentclass{article}
\usepackage{palatino}
\usepackage{geometry}
\geometry{top=1in,bottom=1in,left=1in,right=1in}

\usepackage{graphicx}
\DeclareGraphicsExtensions{.eps}


\usepackage{algorithm}
\usepackage{algorithmic}



\newcommand{\argmax}{\operatornamewithlimits{argmax}} 
\newcommand{\argmin}{\operatornamewithlimits{argmin}}


\usepackage{amsfonts}
\usepackage{amsmath}

\begin{document}

\title{Perceptron for Part-Of-Speech (POS) Tagging}
\author{Yuncheng Li}
\maketitle

\section{POS Tagging}
POS Tagging is a standard NLP procedure to give a tag for each word in a sentence. For example, ``Time/NN flies/VBZ like/IN an/DT arrow/NN'', in which words are accompanied with a POS tag. See the textbook for a full list of the
standard set of tags and their meanings.

%\begin{figure}[!h]
%    \begin{center}
%        \includegraphics[width=1\textwidth]{tags.eps}
%    \end{center}
%    \caption{POS tags and their meanings. (Snipped from JM book)}
%    \label{fig:pos-tags}
%\end{figure}

Features can be extracted for POS tagging, given a word sequence (sentence) and a tagging candidate (tag sequence), denoted by $X_{1\ldots N}$ and $Y_{1\ldots N}$ respectively. The feature extraction procedure can be denoted by a function mapping $\Phi:(X, Y, i) \mapsto \{0, 1\}^I$, in which $i$ denotes the word position and $I$ denotes the size of the feature set. This is better explained by example. Define the indicator function as Equ. (\ref{equ:indicator}).
\begin{equation}
    \mathbb{I}(\mathit{expr}) = \left\{
        \begin{array}[h]{ll}
            1 & \text{if }\mathit{expr} \text{ is True }\\
            0 & \text{if }\mathit{expr} \text{ is False }
    \end{array}
    \right.
    \label{equ:indicator}
\end{equation}

An example of unary feature bin is $\Phi_{100}(X, Y, i) =
\mathbb{I}(X_i = time \wedge Y_i = \text{\textit{NN}})$ and an
example of pairwise feature bin is $\Phi_{200}(X, Y, i) =
\mathbb{I}(Y_i = \text{\textit{NN}} \wedge Y_{i+1} =
\text{\textit{VBZ}})$. Note that $\Phi_{100}$ depends on $X$,
while $\Phi_{200}$ doesn't, which are all about design. Also note
that $\mathit{100}$ and $\mathit{200}$ here are just random
numbers for notation.  The size of feature set
$I$ depends on vocabulary size and the set of tags set, denoted
by $T$.

For example, let the word sequence $X = (time, flies, like, an, arrow)$ and the tagging candidate $Y = (\text{\textit{NN}}, \text{\textit{VBZ}}, \text{\textit{IN}}, \text{\textit{DT}}, \text{\textit{NN}})$. It is easily seen that $\Phi_{100}(X, Y, 1) = 0$, $\Phi_{100}(X, Y, 2) = 0$, $\Phi_{200}(X, Y, 1) = 1$ and $\Phi_{200}(X, Y, 2) = 1$.

\section{Viterbi Decoder}
Given a set of weights and a word sequence, we define a objective function, a.k.a. score, as a weighed sum of features, as in Equation (\ref{equ:score}). Viterbi Decoder is used to find the tagging sequence that achieves highest score. Note that the set of weights can be set manually or learned from examples, and one way of learning from examples is explained in the next section.
\begin{equation}
    F(X, Y)_{1\ldots N} = \sum_{j = 1}^{I} w_j \sum_{i = 1}^{N} \Phi_j(X, Y, i)
    \label{equ:score}
\end{equation}

It's easy to show that $F(X, Y)_{1\ldots N}$ in Equation (\ref{equ:score}) can be decomposed as Equation (\ref{equ:sub-viterbi}), which is the key equation to do dynamic programming, a.k.a. Viterbi Decoding in this context.
\begin{equation}
    F_{1\ldots N} = F_{1\ldots (N - 1)} + \sum_{j = 1}^I w_j \Phi_j(X, Y, N)
    \label{equ:sub-viterbi}
\end{equation}

Based on Equation (\ref{equ:sub-viterbi}), the dynamic
programming algorithm to maximize $F_{1\ldots N}$ can be derived
as Algorithm (\ref{algo:viterbi}). Note that $\Phi_j(X, Y, i)$
depends only on $X_i, Y_i = t \text{ and } Y_{i - 1} =
t'$, because we are considering pairwise chain features. 
In general, the same dynamic programming algorithm can be
used for any features that can be written as functions of 
$X_{1\ldots N}, Y_i = t \text{ and } Y_{i - 1} =
t'$
%It's trivial to extend this algorithm to n-gram. 
Also note that the
table entry $\delta(i, t)$ denotes $F_{1\dots i}$ with tag at
position $i$ set to $t$. After computing $\delta$ with Algorithm
(\ref{algo:viterbi}), it's trivial to get the optimal sequence
$Y_{1\ldots N}$ from $\delta$.


\begin{algorithm}[H]

    \begin{algorithmic}[1]
    %\begin{algorithmic}
        \REQUIRE $w_{1\ldots I}$, $X_{1\ldots N}$
    \STATE allocate a table $\delta$ with size $|T| * N$

        \FOR{$i=1$ to $N$} %\COMMENT{For each word position}
        \FOR{$t \in T$} %\COMMENT{For each tag candidate at position $i$}
            \STATE $\delta(i, t) \leftarrow -\infty$

            \FOR{$t' \in T$} %\COMMENT{For each tag candidate at position $i - 1$}
            \STATE $\delta(i, t) \leftarrow max\left\{ \delta(i, t), \delta(i - 1, t') + \sum_{j = 1}^I w_j \Phi_j(X, Y, i)\right\}$
            \ENDFOR
        \ENDFOR
        \ENDFOR

        \RETURN $\delta$

    \end{algorithmic}
 \caption{ Viterbi Decoding }
 \label{algo:viterbi}
\end{algorithm}

\section{Perceptron for POS Tagging}
With a learning algorithm, we will be able to train feature weights, which is required by Viterbi decoding. Perceptron algorithm is one way to do so.

\subsection{Perceptron Background}
Perceptron algorithm is originally used for training a binary classifier. Given data points $i = 1\dots S$, associated with features $f^i \in R^D$ and a binary label $y^i \in \{-1, +1\}$, perceptron algorithm tries to find solution for the optimization problem, $\argmax_{w, b} (\sum_i \mathbb{I}(y^i = t^i))$, in which $t^i = \mathrm{sign}(w ^T f^i + b)$ is the predicted label. People usually remove the bias term $b$, by extending the feature $f^i$ with a constant column, and we denote $\hat{f}^i = (f^i, 1)$ and $\hat{w} = (w, b)$, so that $t^i$ becomes $\mathrm{sign}(\hat{w}^T \hat{f}^i)$. By iteratively adjusting feature weights for wrong decision points, perceptron algorithm, shown in Algorithm \ref{algo:perceptron}, guarantees to converge to an $w$ that achieves perfect separation, if the data is linearly separable.

\begin{algorithm}
    \caption{ Perceptron Algorithm for Binary Classifier}
    \label{algo:perceptron}

\begin{algorithmic}

    \REQUIRE Features $f^{1\dots S} \in R^D$ and binary labels $y^{1\dots S}$
    \STATE make extended feature matrix $\hat{f} \leftarrow (f, 1)$
    \STATE initialize $(\hat w) \leftarrow \mathbf{0}$

    \REPEAT
    \FOR{$i = 1\dots S$}

    \STATE $t^i = \mathrm{sign}(\hat{w} ^T \hat{f}^i)$
    \IF{$t^i \neq y^i$}
        \STATE $\hat{w} \leftarrow \hat{w} + y^i \hat{f}^i$
    \ENDIF

    \RETURN $\hat{w}$

    \ENDFOR
    \UNTIL{Convergence or maximum number of iteration}

\end{algorithmic}

\end{algorithm}

There are some fundamental problems to use Algorithm \ref{algo:perceptron} for POS tagging. Suppose that for all data instances $i = 1\dots S$, length of the word sequences are fixed to $N$, then the number of all possible tagging sequence is $T^N$, which means naively, we need to construct a $T^N$-class classifier. To extend binary classifiers, such as the one shown above, to multiple class classifiers, people usually construct multiple one-vs-all binary classifiers. Basically, we'll need $C$ binary classifiers for $C$-class classifiers. Therefore, it's not tractable to use the binary perceptron algorithm directly in POS tagging problem. An implication for this problem is that we will need exponentially large number of data instances to achieve decent error bound.

\subsection{ Perceptron Algorithm for POS tagging }

Combining the optimization problem for binary perceptron and the one in the Viterbi decoding, we will get a unified one, $\argmax_{w} \sum_i \mathbb{I}(Y^s = V^s)$, in which $V^s = \argmax_Y(\sum_{j = 1}^{I} w_j \sum_{i = 1}^{N_s} \Phi_j(X, Y, i))$ is the predicted label. Bear in mind that $V_i$ can be efficiently carried out by the Viterbi Decoder explained above. By iteratively adjusting weights for wrong decoded sequences, the perceptron algorithm, shown in Algorithm \ref{algo:perp-pos}, guarantees to converge to an $w$ that achieve perfect separation, if the data is linearly separable.

\begin{algorithm}
    \caption{ Perceptron Algorithm for POS Tagging}
    \label{algo:perp-pos}

\begin{algorithmic}

    \REQUIRE Word sequences $X^{1\dots S}$
    \REQUIRE POS tagging $Y^{1\dots S}$
    \REQUIRE the feature extraction function $\Phi$

    \STATE initialize $w \leftarrow \mathbf{0}$

    \REPEAT
    \FOR{$s = 1\dots S$}

    \STATE $V^s = \argmax_Y(\sum_{j = 1}^{I} w_j \sum_{i = 1}^{N_s} \Phi_j(X^s, Y, i))$ \COMMENT{Using Viterbi Decoder}
    \IF{$V^s \neq Y^s$}
        \STATE $f(X^s, Y^s) \leftarrow \sum_{i = 1}^{N_s} \Phi(X^s, Y^s, i)$
        \STATE $f(X^s, V^s) \leftarrow \sum_{i = 1}^{N_s} \Phi(X^s, V^s, i)$

        \STATE $\hat{w} \leftarrow \hat{w} + f(X^s, Y^s) - f(X^s, V^s)$
    \ENDIF


    \ENDFOR
    \UNTIL{Convergence or maximum number of iteration}

\end{algorithmic}

\end{algorithm}

\subsection{Interpretation}
The essence of perceptron algorithm, both for binary classifier and POS tagging, is to adjust weights when there is error. The way to adjust weights is to make sure the new weights will be better than the old ones, in terms of correcting prediction locally.

Take the perceptron for POS tagging as an example. When $V^s \neq Y^s$, the adjusting will make sure $F_{1\dots N_s}(X, V^s)$ will be decreased and $F_{1\dots N_s}(X, Y^s)$ will be increased, so that there are more chances that viterbi decoding on new weights will yield $Y^s$ with more changes. By calculating gradients for the score $F_{1\dots N}$, as defined in Equation \ref{equ:score}, it's easy to show that the updating rules in \ref{algo:perp-pos} indeed achieves the goal to decrease $F_{1\dots N_s}(X, V^s)$ and increase $F_{1\dots N_s}(X, V^s)$. Actually, $\nabla_w F_{1\dots N_s}(X, V^s) = f(X^s, V^s)$ and $\nabla_w F_{1\dots N_s}(X, Y^s) = f(X^s, Y^s)$.


\end{document}
