Efficient programmable learning to search
Kai-Wei Chang
University of Illinois
\href{mailto:Kai-Wei Chang <kw@kwchang.net>
% We improve ``learning to search'' approaches to structured prediction in two ways. First, we show that the search space can be defined by an arbitrary imperative program, reducing the number of lines of code required to develop new structured prediction tasks by orders of magnitude. Second, we make structured prediction orders of magnitude faster through various algorithmic improvements. We demonstrate the feasibility of our approach on three structured prediction tasks: two variants of sequence labeling and entity-relation resolution. In all cases we obtain accuracies at least as high as alternative approaches, at drastically reduced execution and programming time.
learning_to_search-arxiv.tex
\documentclass[oneside,english]{article}
\usepackage{nips14submit_e,times,amsfonts}

\title{Efficient programmable learning to search}
\author{
Kai-Wei Chang\\
University of Illinois\\
\href{mailto:Kai-Wei Chang <kw@kwchang.net>}{\nolinkurl{kw@kwchang.net}}
\And
Hal Daum\'e III\\
University of Maryland\\
\href{mailto:Hal Daumé III <me@hal3.name>}{\nolinkurl{me@hal3.name}}
\AND
John Langford\\
Microsoft Research\\
\href{mailto:John Langford <jcl@microsoft.com>}{\nolinkurl{jcl@microsoft.com}}
\And
Stephane Ross\\
Google\\
\href{mailto:Stephane Ross <stephaneross@google.com>}{\nolinkurl{stephaneross@google.com}}
}

\input{preamble}


% adjust the following to edit space around subsections & sections
\newcommand\sectionprelude    {  \vspace{-0.0em} }
\newcommand\sectionpostlude   {  \vspace{-0.0em} }
\newcommand\subsectionprelude {  \vspace{-0.0em} }
\newcommand\subsectionpostlude{  \vspace{-0.0em} }

\hypersetup{pdftitle={Efficient programmable learning to search},
            pdfauthor={Kai-Wei Chang, Hal Daume III, John Langford and Stephane Ross}}

\nipsfinalcopy
\begin{document}

\maketitle

\begin{abstract}%
  We improve ``learning to search'' approaches to structured
  prediction in two ways.  First, we show that the search space can be
  defined by an arbitrary imperative program, reducing the number of
  lines of code required to develop new structured prediction tasks by
  orders of magnitude.  Second, we make structured prediction orders
  of magnitude faster through various algorithmic improvements.
  We demonstrate the feasibility of our approach on three structured prediction tasks:
  two variants of sequence labeling and entity-relation resolution.
  In all cases we obtain accuracies at least as high as alternative approaches,
  at drastically reduced execution and programming time.
\end{abstract}

\section{Introduction}

\label{sec:intro}

In structured prediction problems, the goal is creating a good set of
joint predictions. As an example, consider recognizing a handwritten
word where each character might be recognized in turn to understand
the word. Here, it is commonly observed that exposing information
from related predictions (i.e. adjacent letters) aids individual
predictions. Furthermore, optimizing a joint loss function can
improve the gracefulness of error recovery. 

Despite these advantages, it is
empirically common to build independent predictors in settings where
structured prediction naturally applies. Why? Because independent
predictors are much simpler to implement, and are easier and faster to train. Our primary goal is
to make structured prediction algorithms as
easy and fast as possible to both program and compute.

We present a new programming abstraction that radically reduces the complexity of
programming and the running time of our solution.
\begin{enumerate}
\item We enable structured prediction as a \emph{library} which has a function
\predict\ returning individual predictions. The \predict\ interface is
the minimal complexity approach to producing a structured prediction.
Surprisingly, this single library interface is sufficient for both
testing \emph{and training}, when augmented to include label ``advice'' from a training
set and an arbitrary user-provided loss function and a reference decision. This means that a developer need only code desired \emph{test time behavior} and
gets training with minor additional decoration.

\item Although the \predict\ interface is the same as the interface for an
  online learning algorithm, the structured prediction setting commonly differs in two critical ways. First, the
  loss may not be simple 0/1 loss over subproblems. For optimization of a joint loss, we
  add a \loss\ function which allows the declaration of an \emph{arbitrary} loss for the
  joint set of predictions. The second difference is that past predictions
  are commonly used as features for other predictions. This can be
  handled either implicitly or explicitly, but the algorithm is
  guaranteed to work either way.
\end{enumerate}
Here \predict\ and \loss\ enable a concise specification of structured
prediction problems.

Basic sequence labeling as shown in algorithm \ref{alg:sequential}
is the easiest possible structured prediction problem, so it forms a
good use case. The algorithm takes as input a sequence of examples
(consider features of handwritten digits in words), and predicts the
meaning of each element in turn. This is a specific case of sequential decision making, in which the $i$th prediction may depend on previous predictions. In this example, we make use of the library's support for implicit feature-based dependence on previous predictions.

\newalgorithm{sequential}%
  {\FUN{Sequential\_RUN}(\VAR{examples})}%
  {
    \SETST{{output}}{[]}
    \FOR{{\VAR{n}} = \CON{1} to \FUN{len}(\VAR{examples})}
      \SETST{ref}{\VAR{examples}{[}\VAR{n}{]}\texttt{.}{true\_label}}
      \STATE{\VAR{output}[\VAR{n}] $\leftarrow$ \FUN{predict}(\texttt{\footnotesize input=}\VAR{examples}{[}{i}{]}, \texttt{\footnotesize ref=}\VAR{ref}, \texttt{\footnotesize tag=}\VAR{n}, \texttt{\footnotesize condition=}[1:\VAR{n}-1])}
    \ENDFOR
    \STATE \FUN{loss}(\# \VAR{output}[\VAR{n}] $\neq$ \VAR{examples}[\VAR{n}]\texttt{.}true\_label)
    \STATE \textbf{return} \VAR{output}
  }


The use of this function for decoding is clear, but how can the
\predict\ interface be effective?  There are two challenges to
overcome in creating a viable system.
\begin{enumerate}
\item Given the available information, are there well-founded
  structured prediction algorithms? For Conditional Random
  Fields~\cite{lafferty01crf} and structured SVMs
  \cite{taskar03mmmn,tsochantaridis04svmiso}, the answer is ``no'',
  because we have not specified the conditional independence structure
  of the system of predicted variables. Instead, we use a system that
  implements search-based structured prediction methods such as
  Searn~\cite{daume09searn}, DAgger~\cite{ross11dagger}, AggreVaTe~\cite{ross14aggrevate} or LOLS~\cite{chang15lols}. These have
  formal correctness guarantees which differ qualitatively from the
  conditional log loss guarantees of CRFs. For example, given a low
  regret cost-sensitive classification algorithm, Searn guarantees
  competition according to \loss\ with an oracle policy and local
  optimality w.r.t. one-step deviations from the learned policy.  We
  discuss how these work below.
\item A sequential program has only one execution stack, which is used
  by the decoding algorithm above. This conflicts because the learning
  algorithm would naturally also use the stack. We refactor the learning
  algorithm into a state machine which runs before the \FUN{Run}
  function is called and after the various library calls are made.  In
  essence, \FUN{Run} is invoked many times with different
  example sequences and different versions of \predict\ so as to find
  a version of \predict\ with a small \loss.
\end{enumerate}
Given this high level design, the remaining challenge is
computational.  How do we efficiently and effectively find a
\predict\ which achieves a small \loss? 

\section{Learning to Search}

Learning to search~\cite{collins04incremental,daume09searn,ross11dagger,ross14aggrevate} is a family of approaches that solve structured
prediction tasks.
This family includes a number of specific algorithms including
the incremental structured perceptron \cite{collins04incremental,huang12structured}, \textsc{Searn} \cite{daume09searn},
\textsc{DAgger} \cite{ross11dagger},
\textsc{AggreVaTe} \cite{ross14aggrevate},
and others \cite{daume05laso,xu07beam,xu07planning,ratliff07boosting,syed11reduction,doppa12oss,doppa14hcsearch}.
Learning to search approaches 
solve structured prediction problems by 
(1) decomposing the production of the structured
output in terms of an explicit search space (states, actions, etc.);
and (2) learning hypotheses that control a policy that takes actions in
this search space.

More formally, structured prediction aims to induce a function $f$
such that for any $x \in \mathcal{X}$ (the input space), $f$ produces an
output $f(x) = y \in \mathcal{Y}(x)$ in a (possibly input-dependent) space
$\mathcal{Y}(x)$. A problem is structured if such $y$s can be decomposed into
smaller pieces, but that those pieces are tied together by features,
by a loss function or just by statistical dependence (given
$f,x$). There is a task-specific loss function $\ell : \mathcal{Y} \times \mathcal{Y}
\rightarrow \mathbb{R}^{\geq0}$, where $\ell(y,\hat y)$ tells us how bad it is to predict
$\hat y$ when the true output is $y$. 
In the learning to search framework, the joint variable $\hat y$
is produced incrementally by traversing some search space.
The goal of the learning
task is to construct some hypothesis $h \in \mathcal{H}$ (typically represented as a scoring
function or classifier) that can be used to construct a policy $\pi_h$
that makes decisions in this search space.

A discrete search space is defined by states $s\in S$ and a mapping
$A:S\rightarrow2^{S}$ defining the set of valid next states. One of
the states is a unique start state $S$ while some of the others are
end states $e\in E$. Each end state corresponds to some output variable $y_e$
and for $s \in E$, we will abuse notation and write $\ell(s)$ to mean $\ell(y,y_s)$, where $y$ will be clear from context.
\footnote{\citet{doppa14hcsearch} discuss several approaches for
  defining a search space.  The theoretical properties of our approach
  do not depend on which search space definition is used.} We are interested in algorithms
which learn a transition function $f:X_{s}\rightarrow S$ that uses
the features of an input state ($x_s$) to choose a next state so as to
minimize the loss $\ell$ on a heldout test set.  Canonical algorithms to solve this problem
are Searn~\cite{daume09searn}, DAgger~\cite{ross11dagger} and LOLS~\cite{chang15lols},
which we review next. In this discussion, it may be useful to refer to Figure~\ref{fig:searchspace} which depicts
an abstract search space over which learning is to take place.

\begin{figure}[t]
\centering
\noindent\begin{tabular}{|@{}p{0.45\linewidth}|p{0.5\linewidth}|}
\hline
\includegraphics[width=\linewidth]{searchspace} & \vspace{-2in}
The system begins at the start state $S$ and chooses the middle among three actions by the \textbsf{rollin} policy twice. At state $R$ it considers both the chosen action (middle) and both one-step deviations from that action (top and bottom). Each of these deviations is completed using the \textbsf{rollout} policy until an end state is reached, at which point the loss is collected. Here, we learn that deviating to the top action (instead of middle) at state $R$ decreases the loss by $0.2$.\\
\hline
\end{tabular}
\caption{A search space implicitly defined by an imperative program.}
\label{fig:searchspace}
\end{figure}

Learning to search algorithms use some reference transition function $f^{*}$ which is defined on
the training set, but not on the heldout test set.
For instance, LOLS~\cite{chang15lols} operates in an online fashion;
it learns a sequence of transition functions $f_{0},f_{1},....,f_{n}$,
trained on progressively more data.
On each structured example $(x_i,y_i) \in \mathcal{X} \times \mathcal{Y}$, LOLS constructs a
search space. LOLS runs the currently learned model $f_{i-1}$ in this
search space to generate a ``rollin'' trajectory, pictured in blue along the center of Figure~\ref{fig:searchspace}.
It then picks a random position in that trajectory (denoted by \textsf{R} in the Figure)
and considers \emph{all} possible actions that could be taken at that state. In this example, there are three, including
the one actually taken by $f_{i-1}$. These are called ``one-step deviations.''
For each possible action, LOLS tries taking that action, and then rolling out\footnote{When the reference $f^*$ is known to be optimal, LOLS can use $f^*$ to complete the rollout; if not, it uses a stochastic mixture of $f^*$ and $f_{i-1}$.}
until an end state is reached. At each of these end states $e$, a loss $\ell(y_i,y_e)$ can be measured
and any differences in loss can be credit-assigned to the particular choice of the one-step deviation.
Based on this loss vector, LOLS creates a cost-sensitive classification example, where each action
is a possible class, and the cost of each class is the differential loss of that deviation's rollout
versus the lowest cost rollout.
The underlying online cost-sensitive classifier is then updated to yield $f_i$.

DAgger differs from LOLS by avoiding rollouts. Instead, it assumes that a loss function is defined at every state, and a classifier is trained simply to minimize the immediate loss. It also uses a batch underlying classifier rather than an online underlying classifier. Searn differs from LOLS by learning a sequence of policies which are stochastically interpolated, rather than essentially mixing datasets; it also assumes a batch classifier. AggreVaTe is most similar to LOLS, but always rolls out with the reference policy, which can lead to inconsistent learning when the reference policy is not optimal~\cite{chang15lols}.

%DAgger differs from Searn in two computationally helpful ways: it
%mixes datasets rather than policies and uses a loss function $l'$
%defined on all states, so rollouts are not required.  When a loss is
%only defined for end states, a DAgger style algorithm can operate with
%rollouts.

The rollout versions of the previous algorithms require $\cO(t^{2} k n
p)$ where $t$ is the average end state depth (i.e. sequence length),
$k=|m(s)|$ is the number of next states (i.e. branching factor), $n$ is the number of distinct
searches (i.e. sequences), and $p$ is the number of data passes.
Three computational tricks: online learning \cite{collins02perceptron,crfsgd},
memoization, and rollout collapse allow the computational complexity
to be reduced to $\cO(tkn)$, similar to independent prediction.  For
example, we can train a part-of-speech tagger $1000$ times faster than
\system{CRF++}\ \cite{crf++} which is unsurprising since Viterbi
decoding in a CRF is $\cO(tk^2)$. Surprisingly we can do it with $6$ lines of ``user code,'' versus almost $1000$. Our speed matches that of independent classifiers, with a significant lift in performance by using structured features. See~\ref{sec:experiments} for more details.

Most importantly, we show that learning to search can be implemented with the library
interface in section \ref{sec:equiv}. This provides a radical
reduction in the coding complexity of solving new structured
prediction problems as discussed. We also radically reduce the
computational complexity as discussed next in section \ref{sec:comp},
then conduct experiments in section \ref{sec:experiments}.


\section{System Equivalences}
\label{sec:equiv}

Here we show the equivalence of a class of programs and search spaces.
The practical implication of this equivalence is that instead of specifying
a search space (which can be unnatural and awkward), we can specify a program, which can radically reduce
the programming complexity of structured prediction.

Search spaces are defined in the introduction, so we must first define
the set of programs that we consider. Terminal Discrete Oracle Loss
Reporting (TDOLR) programs:
\begin{enumerate}
\item Always terminate.
\item Takes as input any relevant feature information $X$.
\item Make zero or more calls to an oracle $O:X'\rightarrow Y$ which provides
a discrete outcome.
\item Report a loss $L$ on termination.
\end{enumerate}
To show equivalence, we prove a theorem. This theorem holds for the
case where the number of choices is fixed in a search space (and,
hence, $m(s)$ is implicitly defined). 
\begin{theorem}
For every TDOLR program there exist an equivalent search space and
for every search space there exists an equivalent TDOLR program.\end{theorem}

The practical implication of this theorem is that instead of
speicfying search spaces, we can specify a TDOLR program (such as
algorithm \ref{alg:sequential}), and apply any learning to search
algorithm such as Searn, DAgger, or variants thereof.

\begin{proof}
A search space is defined by $(A,E,S,l)$. We show there is a TDOLR
program which can simulate the search space in algorithm \ref{alg:TDOLR}.
This algorithm does a straightforward execution of the search space,
followed by reporting of the loss on termination. This completes the
second claim. 

For the first claim, we need to define, $(A,E,S,l)$ given a TDOLR
program such that the search space can simulate the TDOLR program.
At any point in the execution of TDOLR, we define an equivalent state
$s=(O(X_{1}),...,O(X_{n}))$ where $n$ is the number of calls to
the oracle. We define $a$ as the sequence of zero length, and we
define $E$ as the set of states after which TDOLR terminates. For
each $s\in E$ we define $l(s)$ as the loss reported on termination.
This search space manifestly outputs the same loss as the TDOLR program. 

\newalgorithm{TDOLR}%
  {\FUN{TDOLR}(\VAR{X})}%
  {
    \SETST{\VAR{s}}{\VAR{a}}
    \WHILE{\VAR{s} $\not\in$ \VAR{E}}
      \STATE Compute \VAR{$X_s$} from \VAR{X} and \VAR{s}
      \SETST{s}{\FUN{O}(\VAR{$X_s$})}
    \ENDWHILE
    \RETURN{\FUN{Loss}(\VAR{s})}
  }
\end{proof}

\section{Imperative Structured Prediction} \label{sec:comp}

\newalgorithm{learning}%
  {\FUN{Learn}(\VAR{X}, \FUN{f})}
  {
    \SETST{T}{\CON{0}} \label{learn:initbegin}
    \SETST{ex} [] 
    \SETST{cache} [] 
    %\SETST{loss}{\CON{0}}
    \STATE define \FUN{Predict}(\VAR{x}, \VAR{y}) := \{ \VAR{T}\texttt{++} ; \VAR{ex}[\VAR{T}-1] $\leftarrow$ \VAR{x}; \VAR{cache}[\VAR{T}-1] $\leftarrow$ \FUN{f}(\VAR{x}, \VAR{y}, \textsf{\footnotesize rollin}) ;  \myreturn \VAR{cache}[\VAR{T}-1]  \}
    \STATE define \FUN{Loss}(\VAR{l}) := \textsf{\footnotesize no-op} %\{ \VAR{loss} \texttt{+=} \VAR{l} \}
    \STATE \FUN{Run}(X) \label{learn:initend}
    \FOR{\VAR{$t_0$} $=\CON{1}$ \TO \VAR{T}} \label{learn:loopt}
      \SETST{losses}{$\langle$\CON{0}, \CON{0}, \dots, \CON{0}$\rangle$}
      \SETST{t}{\CON{0}}
      \FOR{\VAR{$a_0$} $=\CON{1}$ \TO \FUN{A}(\VAR{ex}[\VAR{$t_0$}])} \label{learn:loopa}
        \STATE Define \FUN{Predict}(\VAR{x}, \VAR{y}) := \{
            \VAR{t}\texttt{++} ; 
            \myreturn
            $\brack{ 
              \textnormal{\VAR{cache}$[$\VAR{t}-1$]$} & \textnormal{if } t < t_0 \\
              \textnormal{\VAR{$a_0$}} & \textnormal{if } t = t_0 \\ 
              \textnormal{\FUN{f}(\VAR{x},\VAR{y},\textsf{\footnotesize rollout})} & \textnormal{if } t > t_0
            }$ \}
        \STATE Define \FUN{Loss}(\VAR{val}) := \{ \VAR{losses}[\VAR{$a_0$}] \texttt{+=} \VAR{val} \} \label{learn:loss}
        \STATE \FUN{Run}(X) \label{learn:rerun}
      \ENDFOR
      \STATE Online update with cost-sensitive example (\VAR{ex}[\VAR{$t_0$}], \VAR{losses}) \label{learn:example}
    \ENDFOR
  }

The full learning algorithm (for a single structured input, \VAR{X}) is depicted in Algorithm~\ref{alg:learning}. 
The ugliness of this algorithm is due to the fact that standard computational systems have a single stack. We have elected to give \FUN{Run} control of this stack to ease the implementation of structured prediction tasks. The consequence of this is that the learning algorithm does not have access to the machine stack, and therefore must be implemented as a state machine.

In lines~\ref{learn:initbegin}--\ref{learn:initend}, a \emph{rollin} pass of \FUN{Run} is executed.  \FUN{Run} can generally be any TDOLR program as discussed in appendix \ref{sec:equiv}, with a specific example being algorithm \ref{alg:sequential}. In this pass, predictions are made according to the current policy, \FUN{$f$}, flagged as rollin (this is to enable support of arbitrary rollin and rollout policies). Furthermore, the examples (feature vectors) encountered during prediction are stored in \VAR{ex}, indexed by their position in the sequence (\VAR{T}), and the rollin predictions are cached in the variable \VAR{cache}.

The algorithm then initiates one-step deviations from this rollin trajectory. For every time step, (line~\ref{learn:loopt}), we generate a \emph{single} cost-sensitive classification example; its features are \VAR{ex}[\VAR{$t_0$}], and there are \FUN{m}(\VAR{ex}[\VAR{$t_0$}]) possible labels (=actions). For each action (line~\ref{learn:loopa}), we compute the \emph{cost} of that action. To do so, we execute \FUN{Run} again (line~\ref{learn:rerun}) with a ``tweaked'' \FUN{Predict} that at a particular time-step (\VAR{$t_0$}) simply returns the perturbed action \VAR{$a_0$}. At previous timesteps it returns the cached predictions. At future timesteps it calls \FUN{f}, flagged as a rollout example.\footnote{For concreteness, for LOLS, the rollin policy would be the current classifier and the rollout policy would be a stochastic interpolation of that classifier and the oracle \VAR{y}.} The \FUN{Loss} function simply accumulates the loss for the query action. Finally, a cost-sensitive classification is generated (line~\ref{learn:example}) and fed into an online learning algorithm.  

When the learning-to-search algorithm is Searn, this implies a
straightforward update of the next policy.  The situation with online
DAgger is more subtle---in essence a dependence on the reference
policy must be preserved for many updates to achieve good performance.
We do this using policy interpolation (as in Searn) between the
reference policy and learned policy.  

Without any speed enhancements, each execution of \FUN{Run} takes $\cO(t)$ time, and we execute it $tk+1$ times, yielding an overall complexity of $\cO(kt^2)$ per structured example.
For comparison, structured SVMs or CRFs with first order Markov dependencies run in $\cO(k^2t)$ time.

To improve this running time, we make use of memoization. This reduces the overall runtime to $\cO(kt)$, when paths collapse frequently (this is tested empirically in Section~\ref{sec:pathcollapse}). This optimization take advantage of the fact that most predictions only depend on a small subset of previous predictions, not all of them. In particular, if the $i$th prediction only depends on the $i-1$st prediction, then there are at \emph{most} $tk$ unique predictions ever made.\footnote{We use \emph{tied randomness}~\cite{ng00pegasus} to ensure that for any time step, the same policy is called.} This is what enables dynamic programming for sequences (the Viterbi algorithm). We capitalize on this observation in a more generic way: memoization.

\subsection{Optimization 1: Memoization}

For many structured prediction tasks, the primary computational cost is prediction: namely, calling the underlying classifier. In order to avoid repredictions, we can cache previous predictions. The challenge is understanding how to know when two predictions are going to be identical, faster than actually computing the prediction. Since we rely on a highly optimized base predictor, this computation must be done almost instantaneously.

In order to accomplish this, the user must decorate their calls to the \FUN{Predict} function with \emph{tags}. In the case of graphical models, one can think of a tag as the ``name'' of a particular variable in the graphical model. For a sequence labeling problem, the tag for a given position might just be its index.

When calling \FUN{Predict}, the user specifies both the tag of the
current prediction, and the tag of \emph{all previous predictions} on
which the current prediction depends. This roughly means: when the
features \VAR{x} are computed, which previous predictions are being
used in construction of those features. The semantics of this dependence
is that the user is guaranteeing that \emph{if} the predictions for all the tags in the dependent variables are the
same, \emph{then} the prediction for the current example will also be the
same.

Under this assumption, we can store a cache that maps triples of $\langle$tag, condition tags, condition predictions$\rangle$ to $\langle$current prediciton$\rangle$. In all cases we've looked at, the added overhead of maintaining this datastructure (as a hash table) is tiny in comparison to making repeated predictions on the same features.

One subtle issue arizes with respect to correctness. In line~\ref{learn:example}, the learned policy changes. For policy mixing algorithms (like Searn), this is fine and correctness is guaranteed. However, for data mixing algorithms (like DAgger), this potentially changes \FUN{$f_i$}, implying the memoized predictions may no longer be up-to-date so the recorded cache may no longer be accurate. Thus, for DAgger-like algorithms, this optimization is okay \emph{if} the policy does not change much. We evaluate this empirically  Section~\ref{sec:pathcollapse}.

\subsection{Optimization 2: Forced Path Collapse}

The second optimization we can use is a heuristic that only makes rollout predictions for a constant number of steps (e.g., 2 or 4). The intuition is that optimizing against a truly long term reward might be difficult, in particular if features are not available at the current time \VAR{$t_0$} that enables the underlying learner to distinguish between the outcome of decisions far in the future. The specific optimization is to stop rollouts after some fixed number of rollout steps (essentially: to just return a constant action).

This intuitive reasoning is correct, except for accumulating \loss. If \loss\ is only declared at the end of \FUN{Run}, then we must execute $T-t_0$ time steps making (possibly memoized) predictions.
However, for many problems, it is possible to declare loss \emph{early} as with Hamming loss (= number of incorrect predictions). There is no need to wait until the end of the sequence to declare a per-sequence loss: one can declare it after every prediction, and have the total loss accumulate (hence the ``\texttt{+=}'' on line~\ref{learn:loss}). We generalize this notion slightly to that of a history-independent loss:

\begin{definition}[History-independent loss]
A loss function is \emph{history-independent at state $s_0$} if, for \emph{any} final state $e$ reachable from $s_0$, and for any sequence $s_0 s_1 s_2 \dots s_i = e$: it holds that $\FUN{Loss}(e) = A(s_0) + B(s_1 s_2 \dots s_i)$, where $B$ does not depend on any state before $s_1$.
\end{definition}

For example, Hamming loss is history-independent: $A(s_0)$ corresponds to Hamming loss up to and including $s_0$ and $B(s_1 \dots s_i)$ is the Hamming loss after $s_0$.\footnote{Any loss function that decomposes over structure, as required by structured SVMs, is guaranteed to also be history-independent; the reverse is not true. Furthermore, when structured SVMs are run with a non-decomposible loss function, their runtime becomes exponential in $t$. When our approach is used with a loss function that's not history-independent, our runtime increases by a factor of $t$.}
When the loss function being optimized is history-independent, we allow \loss\ to be declared \emph{early}, allowing this additional optimization.

\subsection{Overall Complexity}

Suppose that the cost of calling the policy is $d$.\footnote{Because the policy is a multiclass classifier, $d$ might hide a factor of $k$ or $\log k$.} Then the complexity of the unoptimized learning function is $\cO(t^2kd)$. By adding the memoization optimizations only, and assuming paths collapse after a constant number of steps, this drops to $\cO(t^2k + t k d)$. (The first term is from retrieving memoized predictions, the second from executing the policy a constant number of times for each perturbed sequence.)  Adding the forced path collapse heuristic in addition to the memoization, the complexity drops further to $\cO(tkd)$.
In comparison, a first order CRF or structured SVM for sequence labeling has a complexity of $\cO(tk^2f)$, where $f$ is the number of features and $d \approx fk$ or $\approx f\log k$ depending on the underlying classifier used.

\section{Experimental Results}
\label{sec:experiments}

\begin{figure}
\begin{tabular}{|l|l|}
\hline
\textbf{POS} &
\begin{tabular}{c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c}
\wordtag{NNP} & \wordtag{NNP} & \wordtag{,} & \wordtag{CD} & \wordtag{NNS} & \wordtag{JJ} & \wordtag{,} & \wordtag{MD} & \wordtag{VB} & \wordtag{DT} & \wordtag{NN} & \wordtag{IN} & \wordtag{DT} & \wordtag{JJ} & \wordtag{NN} & \\
Pierre & Vinken & , & 61 & years & old & , & will & join & the & board & as & a & nonexecutive & director & \dots
\end{tabular} \\
\hline
\textbf{NER} 
&
\overbracetxt{Germany}{LOC} 's rep to the \overbracetxt{European Union}{ORG} 's committee \overbracetxt{Werner Zwingmann}{PER} said \dots \\
\hline
\textbf{NER+RE} &
	\rlap{\overbracetxt{\overbracetxt{Bob}{PER} 's wife, \overbracetxt{Alice}{PER}}{Spouse\_of}}\overbracetxt{Bob}{PER} 's wife, \overbracetxt{\overbracetxt{Alice}{PER}, is a native of \overbracetxt{Chicago}{LOC}}{Born\_in}.\\ 
\hline
\end{tabular}
\caption{Example inputs (below, black) and desired outputs (above, blue) for 
part of speech tagging task, named entity recognition task, and 
entity-relation recognition task. }
\label{fig:examples}
\end{figure}


We conduct experiments based on two variants of the sequence labeling problem 
(Algorithm~\ref{alg:sequential}), and an entity-relation recognition task. The first is a pure sequence labeling 
problem: Part of Speech tagging based on data from the Wall Street Journal 
portion of the Penn Treebank. The second is a sequence \emph{chunking} 
problem: named entity recognition using data from the CoNLL 2003 dataset.
The final one is an entity-relation extraction task, we consider jointly assigning
types to name entities in a sentence and recognizing relations between 
them~\cite{RothYi07}. 
See Figure~\ref{fig:examples} for example inputs and outputs for these tasks.% 
Basic statistics about the data sets used are in Table~\ref{tab:datasets}.

We use the following freely available systems/algorithms as points of comparison:
\begin{description}
\item[\system{CRF++}] The popular \system{CRF++}\ toolkit \cite{crf++} for conditional random fields \cite{lafferty01crf}, which implements both L-BFGS optimization for CRFs \cite{nash91bfgs,malouf02opt} as well as ``structured MIRA'' \cite{crammer03mira,mcdonald04margin}.
\item[\system{CRF SGD}] A stochastic gradient descent conditional random field package \cite{crfsgd}.
\item[\system{Structured Perceptron}] An implementation of the structured perceptron~\cite{collins02perceptron} due to \cite{chang13svm}.
\item[\system{Structured SVM}] The cutting-plane implementation \cite{joachims09cuttingplane} of the structured SVMs \cite{tsochantaridis04svmiso} for ``HMM'' problems.
\item[\system{Structured SVM (DEMI-DCD)}] A multicore algorithm for optimizing structured SVMs called DEcoupled Model-update and Inference with Dual Coordinate Descent.
\item[\system{VW Search}] Our approach is implemented in the Vowpal Wabbit \cite{langford07vw} toolkit on top of a cost-sensitive classifier \cite{beygelzimer05reductions} that reduces to regression trained with an online rule incorporating AdaGrad \cite{duchi2011adaptive}, per-feature normalized updates \cite{normalized}, and importance invariant updates \cite{invariant}.
\item[\system{VW Classification}] An \emph{unstructured} baseline that predicts each label independently, using one-against-all multiclass classification \cite{beygelzimer05reductions}.
\end{description}
These approaches vary both objective function (CRF, MIRA, structured SVM, learning to search) and optimization approach (L-BFGS, cutting plane, stochastic gradient descent, AdaGrad). All implementations are in C/C++, except for the structured perceptron and DEMI-DCD (Java).

\subsection{Methodology}

Comparing different systems is challenging because one wishes to hold constant as many variables as possible. In particular, we want to control for both \textbf{features} and \textbf{hyperparameters}. In general, if a methodological decision cannot be made ``fairly,'' we made it in favor of competing approaches.

To control for \textbf{features}, for the two sequential tagging tasks (POS 
and NER), we use the built-in \emph{feature template} approach of 
\system{CRF++}\ (duplicated in \system{CRF SGD}) to generate features. The 
other approaches (\system{Structured SVM}, \system{VW Search}\ and \system{VW 
Classification}) all use the features generated (offline) by \system{CRF++}. 
For each task, we tested six feature templates and picked the one with best 
development performance using \system{CRF++}. The templates included 
neighboring words and, in the case of NER, neighboring POS tags. 
\emph{However,} because \system{VW Search}\ is also able to generate features 
from its own templates, we also provide results for \textbf{\system{VW Search\ 
(own fts)}} in which it uses its own, internal, feature template generation, 
which were tuned to maximize it's heldout performance on the most 
time-consuming run (4 passes) and include neighboring words (and POS tags, for 
NER) and word prefixes/suffixes.\footnote{The exact templates used are 
provided in the supplementary materials.} In all cases we use \emph{first 
order Markov dependencies,} which lessens the speed advantage of search based 
structured prediction.

\subsection{Entity-Relation Prediction}

In the entity-relation task (NER+RE), we use features based 
on unigrams, bigrams and trigrams from the mixture of target words, and 
part-of-speech tags for the entity classifier.   For the relation classifier, we 
use some additional patterns extracted from the words between the two target 
phrases. Detailed feature templates can be found in \cite{RothYi07}. Besides 
features, we also consider constraints that ensure the entity-type 
assignments and relation-type assignments are compatible with each other. 
For example, the first argument of the {work\_for} relation need to be tagged 
as person, and the second argument has to be an organization. For methods using 

\subsection{Dependency Parsing} \label{sec:dep}

In parallel research, we used the framework described in this paper to build a state-of-the-art dependency parser~\cite{chang15dependency}. The primary advantages of our parser over alternative approaches is a combination of correctness
and simplicity.

Our implementation requires only $\sim$300 lines of C++ code, when built on top of the imperative learning to search compiler described in this paper. This compares favorably to alternatives such as the Stanford Neural Network parser ($3k$ lines) ~\cite{danqi14nndep}, the RedShift parser ($2k$ lines)\footnote{Available at
\url{https://github.com/syllog1sm/redshift}}, the dynamic orcale parser ($4k$ lines)~\cite{goldberg13oracles} and Malt Parser ($10k$ lines)~\cite{hall06dependency} (all of these line counts attempt to exclude the underlying learning components).

Evaluated on English, our parser achieves a labeled accuracy of $91.1\%$ in comparison to $90.8$ for the dyanmic oracle parser, $89.1$ for the Stanford neural network parser, and $90.8$ for the RedShift parser. On Chinese, we achieve $86.4$ in comparison to $85.1$ (dynamic oracle) and $82.7$ (Stanford). Averaged across ten languages, our accuracy is $81.3$ (versus $80.3$ dynamic oracle and $75.3$ Stanford).


\subsection{Hyperparameters}

To control for \textbf{hyperparameters}, we first separated each system's hyperparameters into two sets: (1) those that affect termination condition and (2) those that otherwise affect model performance. When available, we tune hyperparameters for (a) learning rate and (b) regularization strength\footnote{Precise details of hyperparameters tuned and their ranges is in the supplementary materials.}. Additionally, we vary the termination conditions to sweep across different amounts of time spent training. For each termination condition, we can compute results using either the \textbf{default hyperparameters} or the \textbf{tuned hyperparameters} that achieved best performance on heldout data. We report both conditions to give a sense of how sensitive each approach is to the setting of hyperparameters (the amount of hyperparameter tuning directly affects effective training time).

One final confounding issue is that of \textbf{parallelization}. Of the baseline approaches, only \system{CRF++}\ supports parallelization via multiple threads at training time. In our reported results, \system{CRF++}'s time is the total CPU time (i.e., effectively using only one thread). Experimentally, we found that wall clock time could be decreased by a factor of $1.8$ by using $2$ threads, a factor of $3$ using $4$ threads, and a (plateaued) factor of $4$ using $8$ threads. This should be kept in mind when interpreting results. DEMI-DCD (for structured SVMs) also \emph{must} use multiple threads. To be as fair as possible, we used $2$ threads. Likewise, it can be sped up more using more threads \cite{chang13svm}. VW (Search and Classification) can also easily be parallelized using AllReduce \cite{agarwal11allreduce}. We do not conduct experiments with this option here because none of our training times warranted parallelization (a few minutes to train, max).

\subsection{Task Specifics}

\newalgorithm{entrel}%
  {\FUN{Entity\_Relation\_RUN}(\VAR{sent})}%
  {
    \SETST{\VAR{output}}{\FUN{Initialize\_structrue}()}
    \SETST{\VAR{K}}{\FUN{Number\_of\_entities}(\VAR{sent})}
    \FOR{{\VAR{n}} = \CON{1} to \VAR{K}}
      \SETST{ref}{\VAR{sent\texttt{.}entity\_type}[\VAR{n}]}
      \SETST{\VAR{output}\texttt{.}entity\_type[n]}{\FUN{predict}(\texttt{\footnotesize input=}\VAR{sent}.entity[i], \texttt{\footnotesize ref=}\VAR{ref}, \texttt{\footnotesize tag=}\VAR{n}}
 \STATE \FUN{loss}(\VAR{output}\texttt{.}entity\_type[n] $\neq$ \VAR{sent}\texttt{.}entity\_type[n]\texttt{.}true\_label)
    \ENDFOR
    \FOR{{\VAR{n}} = \CON{1} to \VAR{K}-1}
    \FOR{{\VAR{m}} = \CON{n+1} to \VAR{K})}
      \SETST{ref}{\VAR{sent}\texttt{.}relation\_type[\VAR{n},\VAR{m}]\texttt{.}{true\_label}}
      \SETST{valid\_relations}{\FUN{Find\_valid\_relations}(\VAR{output}\texttt{.}entity\_type[\VAR{n}], \VAR{output}\texttt{.}entity\_type[\VAR{m}])}
      \SETST{\VAR{output\texttt{.}relation\_type}}{\FUN{predict}(\texttt{\footnotesize input=}\VAR{sent}.relation[n,m], \texttt{\footnotesize ref=}\VAR{ref}, \texttt{\footnotesize tag=}\VAR{K*(n+1)+m}, \texttt{\footnotesize valid\_labels=}\VAR{valid\_relations}, \texttt{\footnotesize condition=}[\VAR{n},\VAR{m}])}
 \STATE \FUN{loss}(\VAR{output}\texttt{.}relation\_type[n,m] $\neq$ \VAR{sent}\texttt{.}entity\_type[n,m]\texttt{.}true\_label )
\ENDFOR
\ENDFOR
    \STATE \textbf{return} \VAR{output}
  }



Part of speech tagging for English is based on the Penn Treebank tagset that includes $45$ discrete labels for different parts of speech. The overall accuracy reported is Hamming accuracy (number of tokens tagged correctly). This is a \emph{pure} sequence labeling task. We use $912k$ tokens (words) of training data and approximately $50k$ tokens of heldout data and test data. The \system{CRF++}\ templates generate $630k$ unique features for the training data; additional statistics are in Table~\ref{tab:datasets}.
\begin{table}
\begin{tabular}{|l|rrrrr|rr|rr|}
\hline
&
\multicolumn{5}{c|}{\textbf{Training}} &
\multicolumn{2}{c|}{\textbf{Heldout}} &
\multicolumn{2}{c|}{\textbf{Test}} \\
      & Sents &  Toks  & Labels & Features & Unique Fts & Sents & Toks & Sents & Toks \\
\hline
\textbf{POS} &  38k &  912k & 45 & 13,685k &  629k &  5.5k  &     132k  &    5.5k  &      130k \\
\textbf{NER} &  15k &  205k &  7 &  8,592k &  347k &  3.5k  &      52k  &    3.6k  &       47k \\
\hline
\end{tabular}
\caption{Basic statistics about the data sets used for part of speech (POS) tagging and named entity recognition (NER).}
\label{tab:datasets}
\vspace{-1em}
\end{table}

Named entity recognition for English is based on the CoNLL 2003 dataset that includes four entity types: Person, Organization, Location and Miscellaneous. We report accuracy as macro-averaged F-measure over the correct identification and labeling of these entity spans (the standard evaluation metric). In order to cast this \emph{chunking} task as a sequence labeling task, we use the standard Begin-In-Out (BIO) encoding, though some results suggest other encodings may be preferable \cite{ratinov09design} (we tried BILOU and our accuracies decreased).
 The example sentence from Figure~\ref{fig:examples} in this encoding is:
\begin{center}
\begin{tabular}{c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c}
\overbracetxt{Germany}{LOC} & 's & rep & to & the & \overbracetxt{European Union}{ORG} & 's & committee & \overbracetxt{Werner Zwingmann}{PER} & said & \dots \\
\wordtag{B-LOC} & \wordtag{O} & \wordtag{O} & \wordtag{O} & \wordtag{O} & \wordtag{~~~B-ORG~~~~~~~I-ORG} & \wordtag{O} & \wordtag{O} & \wordtag{B-PER~~~~~~~~~~I-PER~~~~~} & \wordtag{O} &
\end{tabular}
\end{center}
In our system, the only change made to the sequence labeling algorithm (Algorithm~\ref{alg:sequential}) is that \wordtag{\small I-$x$} may only follow \wordtag{\small B-$x$} or \wordtag{\small I-$x$}. We still optimize Hamming loss because macro-averaged F measure does not decompose over individual sentences.

The entity-relation extraction data is from \cite{RothYi07}\footnote{Available at \url{http://cogcomp.cs.illinois.edu/page/resource_view/43}}.
It includes four entity types (Person, Organization, Location, and Others) and six relation types (located in, work for, organization based in, live in, kill, and none).
We report the micro-averaged F1 scores of entity type and relation type, separately. 
Because there is no relation between most pairs of entities, we exclude the ``none'' relation when evaluating the F1 score of relation type.
We consider a simple search space that first assigns a type tag to each entity in the sentence and then recognizes the relation between them. 
Constraints are incorporated into the search space such that the assignments for entity and relation types do not conflict.  
Algorithm \ref{alg:entrel} depicts the procedure.
In the algorithm, \VAR{sent}.entity\_type[n].true\_label is the gold label of the $n$th entity, and \VAR{sent}.relation\_type[n, m].true\_label represents the relation between the $n$th and the $m$th entities. The function \FUN{Find\_valid\_relation} returns a set of valid relation types.

When there are constraints, it is unclear how to compute the partition function efficiently in the CRF model. Therefore, we exclude \system{CRF++} and \system{CRF  SGD} in the comparison. For \system{Structured Perceptron} and \system{Structured SVM}, we follow \citet{RothYi07} to formulate the inference problems as integer linear programming problems (ILPs) and solve them using Gurobi\footnote{\url{http://www.gurobi.com/}}, a commercial ILP solver.


\subsection{Efficiency versus Accuracy}

\begin{figure}
\begin{tabular}{cc}
\hspace{-1.5em}\includegraphics[width=0.5\textwidth,clip=true,trim=24 5 58 27]{figs/POS0.pdf}&
\includegraphics[width=0.5\textwidth,clip=true,trim=24 5 58 27]{figs/NER0.pdf}
\end{tabular}
\caption{Training time versus evaluation accuracy for part of speech tagging (left) and named entity recognition (right). X-axis is in log scale. Different points correspond to different termination criteria for training. Both figures use hyperparameters that were tuned (for accuracy) on the heldout data. (Note: lines are curved due to log scale x-axis.)}
\label{fig:results-tuned}
\end{figure}

\begin{figure}
\begin{tabular}{cc}
\hspace{-1.5em}\includegraphics[width=0.5\textwidth,clip=true,trim=24 5 58 27]{figs/EREnt1.pdf}&
\includegraphics[width=0.5\textwidth,clip=true,trim=24 5 58 27]{figs/ERRel1.pdf}
\end{tabular}
\caption{Training time versus F1 score of the entity type (left) and the 
relation type (right) for the NER+RE task. X-axis is in log scale. Different points correspond to different termination criteria for training.
\emph{Default} hyperparameters are used.}
\label{fig:results-er}
\end{figure}

In Figure~\ref{fig:results-tuned}, we show trade-offs between training time (x-axis, log scaled) and prediction accuracy (y-axis) for the six systems described previously for the two sequential tagging tasks. The left figure is for part of speech tagging (912k training tokens) and the right figure is for named entity recognition (205k training tokens).


In Figure~\ref{fig:results-tuned}, we show trade-offs between training time (x-axis, log scaled) and prediction accuracy (y-axis) for the six systems described previously for the two sequential tagging tasks. The left figure is for part of speech tagging (912k training tokens) and the right figure is for named entity recognition (205k training tokens).

For POS tagging, the independent classifier is by far the fastest (trains in less than one minute) but its performance peaks at $95\%$ accuracy. Three other approaches are in roughly the same time/accuracy tradeoff: \system{VW Search}, \system{VW Search (own fts)} and \system{Structured Perceptron}. All three can achieve very good prediction accuracies in just a few minutes of training. \system{CRF SGD} takes about twice as long. \system{DEMI-DCD} eventually achieves the same accuracy, but it takes a half hour. \system{CRF++} is not competitive (taking over five hours to even do as well as \system{VW Classification}). \system{Structured SVM} (cutting plane implementation) looks promising, but runs out of memory before achieving competitive performance (likely due to too many constraints).

For NER the story is a bit different. The independent classifiers are quite fast (a few seconds to train) but are far from being competitive\footnote{When evaluating F measure for a system that may produce incoherent tag sequences, like ``\wordtag{O} \wordtag{I-LOC}'' we replace any malpositioned \wordtag{I-$x$} with \wordtag{B-$x$}; of all heuristics we tried, this worked best.}. Here, the two variants of \system{VW Search} totally dominate.\footnote{We verified the prediction performance with great care here---it is the first time we have observed learning to search approaches significantly exceeding the prediction performance of other structured prediction techniques when the feature information available is precisely the same.}. In this case, \system{Structured Perceptron}, which did quite well on POS tagging, is no longer competitive and is essentially dominated by \system{CRF SGD} (in the sense that it is faster for the same accuracy). The only system coming close to \system{VW Search}'s performance is \system{DEMI-DCD}, although it's performance flattens out after a few minutes.\footnote{We also tried giving \system{\scriptsize CRF SGD} the features computed by \system{VW Search (own fts)} on both POS and NER. On POS, its accuracy improved to 96.5---on par with \system{VW Search (own fts)}---with essentially the same speed. On NER it's performance decreased. For both tasks, clearly features matter. But which features matter \emph{is} a function of the approach being taken.}

\begin{figure}
\begin{tabular}{cc}
\hspace{-1.5em}\includegraphics[width=0.5\textwidth,clip=true,trim=24 5 58 27]{figs/POS1.pdf}&
\includegraphics[width=0.5\textwidth,clip=true,trim=24 5 58 27]{figs/NER1.pdf}
\end{tabular}
\caption{Training time versus evaluation accuracy for POS tagging (left) and NER (right). X-axis is in log scale. Different points correspond to different termination criteria for training. Both figures use \emph{default} hyperparameters.}
\label{fig:results-default}
\end{figure}

To achieve the results in Figure~\ref{fig:results-tuned} required fairly extensive hyperparameter tuning (on the order of $50$ to $100$ different runs for each system). To see the effects of hyperparameter tuning, we also ran each system with the built-in hyperparameter options.\footnote{The only exceptions is \system{\scriptsize Structured SVM}s, which do not have a default $C$ value (we used $C=128$ because that setting won most often across all experiments).} The trends in the runs with default hyperparameters (Figure~\ref{fig:results-default}) show similar behavior to those with tuned, though some of the competing approaches suffer significantly in prediction performance. \system{Structured Perceptron} has no hyperparameters.

State of the art results on Named Entity recognition are in the $92-94\%$ F1 range on the development data and the $89-90\%$ F1 range on the test data~\cite{ratinov09design}. To achieve these results, one must use a large number of external resources, such as Brown clusters, Gazeteers and distributed representations learned on large external corpora. We repeated experiments with more hyperparameter tuning using these external resources and found the best combination was to use Gazeteers and Brown cluster (word embeddings consistently hurt performance). These were turned on using command line flags and lead to a development performance of $93.2$ and test performance of $89.6$, putting our results well within state of the art on this dataset.

For NER+RE tasks, all the learning approaches achieve similar performance in predicting entity types. However, the joint learning approaches outperform the independent classifier approach by around 6\% in F1 score. The main reason is that predicting the entity type is easier than predicting the relation type.
The joint learning approaches incorporates the entity-type information  when predicting relation type, resulting in better performance. For the training speed, 
%comparisons between  \system{VW Search} and other approaches that formulate the inference as ILP, \system{VW Search} is much more efficient.
\system{VW Search} is much more efficient than other approaches that formulate the inference as an ILP, because a greedy search is relatively faster than solving an ILP.
Surprisingly, the performance of \system{VW Search} is competitive and even higher than other joint learning approaches.

\section{Test-time Prediction Performance} \label{sec:testtimeapp}

\begin{figure}
\includegraphics[width=0.9\textwidth]{figs/tokens_per_second.pdf}
\caption{Comparison of test-time efficiency of the different approaches.
We report the results in thousands of entities per second (for NER+RE) or in thousands of tokens per second (for POS and NER). 
For NER, this ranges from 5k tokens/sec (\system{DEMI-DCD}) to over a quarter million tokens/sec. These numbers include feature computation time only for the two CRF approaches.}
\label{fig:results-testtime}
\end{figure}


In addition to training time, one might care about test time behavior.
On NER, prediction times varied from $5.3k$ tokens/second (\system{DEMI-DCD} and \system{Structured Perceptron} to around $20k$ (\system{CRF SGD} and \system{Structured SVM}) to $100k$ (\system{CRF++}) to $220k$ (\system{VW (own fts)}) and $285k$ (\system{VW}). Although \system{CRF SGD} and \system{Structured Perceptron} fared well in terms of training time, their test-time behavior is suboptimal.
When looking at POS tagging, the effect of the $\cO(k^2)$ dependence on the size of the label set further increased the (relative) advantage of \system{VW Search} over the alternatives. 
Regard the NER-RE task, the \system{VW Search} is faster than other approaches by orders of magnitude. It is again due to the overhead of solving ILP problems in structured SVM and structured Perceptron.

Figure~\ref{fig:results-testtime} shows the speed at which the different systems can make predictions on raw text. \system{Structured SVM}s and friends (\system{DEMI-DCD} and \system{Structured Perceptron}) are by far the slowest (NER: $14k$ tokens per second), followed closely by \system{CRF SGD}\ (NER: $24k$ t/s). This is disappointing because \system{CRF SGD}\ performed very well in terms of training efficiency. \system{CRF++}\ achieves respectable test-time efficiency (NER: almost $100k$ t/s).\footnote{This suggests gains are possible by combining \system{\scriptsize CRF++}'s ``decoder'' and I/O system with \system{\scriptsize CRF SGD}'s optimizer.} \system{VW Search}\ using \system{CRF++}'s features is the fastest (NER: $285k$ t/s) but, like \system{Structured SVM}, this is a bit misleading because it requires feature computation from \system{CRF++}\ to be run as a preprocessor. A fairer comparison is \system{VW Search\ (own fts)}, which runs on (nearly) raw text and achieves a speed of $218k$ t/s for NER.


One thing that is particularly obvious comparing the prediction speed for \system{VW Search} against the other three approaches is the effect of the size of the label space. When the number of labels increases from $9$ (NER) to $45$ (POS), the speed of \system{VW Search} is about halved. For the others, it is cut down by as much as a factor of $8$. This is a direct complexity argument. Prediction time for \system{VW Search} is $\cO(tkf)$ versus $\cO(tk^2f)$ for all other approaches.

Overall, we found our approach to achieve comparable or higher accuracy in as little or less time, both with tuned hyperparameters and default hyperparameters. The closest competitor for POS tagging was the \system{Structured Perceptron} (but that did poorly on NER); the closest competitor for NER was \system{CRF SGD} (but that was several times slower on POS tagging).


\subsection{Empirical evaluation of optimizations}
\label{sec:pathcollapse}


In Section~\ref{sec:comp}, we discussed two approaches for computational improvements. First, memoization: avoid re-predicting on the same input multiple times (which is fully general). Second, path collapse: to stop rollouts at a particular point in time.

The effect of the different optimizations depends greatly on the underlying learning to search algorithm. For example, DAgger does not do rollouts at all, so no efficiency is gained by either of the optimizations for DAgger. (Though, nicely, training speed is only degraded by about 0.5\% when caching is turned on, demonstrating that it's overhead is negligible.) In particular, the only algorithms that are affected are LOLS (with mixed rollouts) and Searn.


\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
& \multicolumn{2}{c|}{\textbf{             NER}} & \multicolumn{2}{c|}{\textbf{  POS}} \\ \hline
                                 &   LOLS(mix)    &       Searn    &     LOLS(mix)     &      Searn \\ \hline
\textbf{No Opts               }  &   96s          &       123s     &     3739s         &      4255s \\ 
\textbf{Memoization           }  &   75s          &       85s      &     1142s         &      1215s \\
\textbf{Collapse@4+Memoization}  &   71s          &       75s      &     1059s         &      1104s \\ 
\textbf{Collapse@2+Memoization}  &   69s          &       71s      &     1038s         &      1074s \\ \hline
\end{tabular}
\end{center}

The above results show the effect of these optimizations on the \emph{best} NER and POS systems we trained without using external resources. In this table, we can see that memoization alone reduces overall training runtime by about $25\%$ on NER and about $70\%$ on POS, essentially because the overhead for the classifier on POS tagging is so much higher (45 labels versus 9). When rollouts are terminated early, the speed increases are much more modest, essentially because memoization is already accounting for much of these gains. In all cases the final performance of the predictors is within statistical significance of eachother (p-value of 0.95, paired sign test), \emph{except} for Collapse@2+Memoization on NER, where the performance decrease is only insignificant at the 0.90 level.

\section{Relation to Probabilistic Programming} \label{sec:pprog}

Probabilistic programming~\cite{gordon14probprog} has been an active area of research for the past decade or more. While our approach bears a family resemblace to the idea of probabilistic programming, it differs in two key ways. First, we have not designed a new programming language. Instead we have a three-function library. This is advantageous because it makes adoption easier. Moreover, our library is in C/C++, which makes integration into existing code bases (relatively) easy. Second, the abstract we focus on is that of \emph{prediction}. In contrast, the typical abstraction for probabilistic programming is \emph{distributions}. We believe that prediction is a more natural abstraction for a lay programmer to think about than probability distributions.

The closest work to ours is Factorie~\cite{mccallum09factorie}. Factorie is a domain specific language embedded in Scala, and is essentially an embedded language for writing factor graphs. It compiles them into Scala, which in turn produces JVM code that can be run reasonably efficiently. Nonetheless, as far as we are aware, Factorie-based implementations of simple tasks like sequence labeling are still less efficient than systems like \system{CRF SGD}. Factorie, more than other probabilistic programming languages we are aware of, acts more like a library than a language; though it's abstraction is still distributions (more precisely: factor graphs).
Another approach which takes the approach of formulating a library is Infer.NET, from \citet{minkainfer}. Infer.NET is a library for constructing probabilistic graphical models in a .NET programming framework. It supports approximate inference methods for things like variational inference and message passing.

In the same spirit as Factorie of having a concise programmic method of specifying factors in a Markov network are: Markov Logic Networks (MNLs) due to~\citet{richardson2006markov} and Probabilistic Soft Logic (PSL) due to~\citet{kimmig2012short}. Although neither of these was derived specifically from the perspective of formulating factors in a conditional random field (or hinge-loss Markov network), that is the net result. Neither of these is an embedded language: one must write declarative code and provide data in an appropriate format, which makes it somewhat difficult to use in complex systems. BLOG~\cite{milch2007blog} falls in the same category, though with a very different focus. Similarly, Dyna~\cite{eisner2005compiling} is a related declarative language for specifying probabilistic dynamic programs which can be compiled into C++ (and then used as library code inside another C++ program). All of these example have picked particular aspects of the probabilistic modeling framework to focus on.

Beyond these examples, there are several approaches that essentially ``reinvent'' an existing programming language to support probabilistic reasoning at the first order level. IBAL~\cite{pfeffer2001ibal} derives from O'Caml; Church~\cite{goodman2008church} derives from LISP. IBAL uses a (highly optimized) form of variable elimination for inference that takes strong advantage of the structure of the program; Church uses MCMC techniques, coupled with a different type of structural reasoning to improve efficiency.

It is worth noting that most of these approaches have a different goal than we have. Our goal is to build a framework that allows a developer to solve a quite general, but still specific type of problem: learning to solve sequencial decision-making problems (``learning to search''). The goal of (most) probabilistic programming languages is to provide a flexible framework for specifying graphical models and performing inference in those models. While these two goals are similar, they are different enough that the minimalistic library approach we have provided is likely to be insufficient for general graphical model inference.

\section{Discussion}

We have shown a new abstraction for a structured prediction library
which achieves better accuracies than many widely used
specialized software toolkits that are specialized to sequence labeling.\footnote{It is worth noting that better accuracies \emph{have} been reported in the literature for these two tasks, even without using external data sources (e.g., unlabeled data or gazetteers). For instance, guided learning \cite{shen07guided} achieves an accuracy of 97.33\% on POS tagging and \citet{ratinov09design} achieves an F-score of 85.57\% on NER.}
Moreover, it achieves this with runtimes up to two orders of magnitude faster than
competing approaches. Moreover, we achieve this with minimal
programming effort on the part of the developer who must implement
\FUN{Run}. Our sequence labeling implementation is $6$ lines of code;
compared to: \system{CRF SGD} at $1068$ \textsc{loc}, \system{CRF++}
at $777$ \textsc{loc} and \system{Structured SVM} at 876
\textsc{loc}.\footnote{All \textsc{loc} computations \emph{exclude}
  lines of code for ``base learning'' algorithms and ``optimizer''
  implementations: this is a measure of how much code has gone in to
  implementing the specific structured prediction task (in this case:
  sequence labeling). The code complexity for alternatives come from
  implementing dynamic programming; or for SVMs from the requirement
  for finding maximally violated constraints.}  Somewhat surprisingly,
this is all possible through a very simple (three function) library
interface which does \emph{not} require the development of an entirely
new programming language. This is highly advantageous as it allows
very easy adoption. Moreover, since our library functions in a
reduction stack, as base classifiers and reductions for cost-sensitive
classification improve, so does structured prediction performance.

\section*{Acknowledgments}

%Many thanks for Kai-Wei Chang for providing the DEMI-DCD and his patient support in helping us run those experiments and the structured perceptron experiments. 
Thanks to Martin Popel for helpful comments on an earlier version of this paper.


\bibliographystyle{plainnat}
\bibliography{bibfile}

\newpage
\appendix

\section{Example TDOLR programs}

In this section, we a few other TDOLR programs which illustrate the
ease and flexibility of programming. 

Algorithm~\ref{alg:sdetect} is for a sequential \emph{detection} task
where the goal is to detect whether or not a sequence contains some
rare element.  This illustrates outputs of lengths other than the
number of examples, explicit loss functions.

\newalgorithm{sdetect}%
  {\FUN{Sequential\_Detection\_RUN}(\VAR{examples}, \VAR{false\_negative\_loss})}%
  {
    \STATE Let \VAR{max\_value} = 1
    \FOR{\VAR{$i$} $=\CON{1}$ \TO \FUN{len}(\VAR{examples})}
      \SETST{max\_value}{\FUN{max}(\VAR{max\_value}, \VAR{examples}{[}\VAR{i}{]}\texttt{.}\VAR{label})}
    \ENDFOR

    \STATE Let \VAR{max\_prediction} = 1

    \FOR{\VAR{$i$} $=\CON{1}$ \TO \FUN{len}(\VAR{examples})}
      \SETST{max\_prediction}{\FUN{max}(\VAR{max\_prediction}, \FUN{predict}(\VAR{examples}{[}\VAR{i}{]}, \VAR{examples}{[}\VAR{i}{]}\texttt{.}\VAR{label}))} \COMMENT{maintain max}
    \ENDFOR

    \IF{\VAR{max\_label} > \VAR{max\_prediction}} 
       \STATE \FUN{loss}(\VAR{false\_negative\_loss}) \COMMENT{The loss is asymmetric}
    \ELSE 
       \IF{\VAR{max\_label} < \VAR{max\_prediction}}
           \STATE \FUN{loss}(1)
       \ELSE
           \STATE \FUN{loss}(0)
       \ENDIF
    \ENDIF

    \IF{\VAR{output}\texttt{.}\VAR{good}}
        \STATE \VAR{output} \texttt{<<} \VAR{max\_prediction}\COMMENT{if we should generate output, append our prediction}
    \ENDIF
  }


In Algorithm~\ref{alg:depparsing}, we show an implementation of a shift-reduce depedency parser for natural language, described in more detail in~\cite{chang15dependency}. We discuss each subcomponent below.   
\begin{itemize}
\item \textsc{GetValidAction} returns valid actions that can be taken by the current configuration.
\item \textsc{GetFeat} extracts features based on the current configuration.   
%The features depend on the top few words in the stack and leftmost few words in the buffer
%as well as their associated part-of-speech tags.
A detailed list of our features is in the supplementary material.
%Features are generated dynamically because configuration changes during parsing.
\item \textsc{GetGoldAction} implements the dynamic oracle described in \cite{goldberg13oracles}. 
The dynamic oracle returns the optimal action in any state that leads to a reachable end state with the minimal loss.
\item \textsc{Predict} is a library call implemented in the L2S system.  
Given training samples,  L2S can learn the policy automatically.
In the test phase, it returns a predicted action leading to an end state with small structured loss.
\item \textsc{Trans} implements the hybrid-arc transition system described above.
%Based on the predicted action and labels, it updates the parser's configuration, and move the agent to the next state.
\item \textsc{Loss} %function is used to measure the distance between the predicted output and the gold annotation. Here, 
returns the number of words whose parents are wrong. It has no effect in the test phase.
\end{itemize}


\newalgorithm{depparsing}%
  {\FUN{RunParser}(\VAR{sentence})}%
  {
  \SETST{{stack $S$}}{\{\bf Root\}}
    \SETST{{buffer $B$}}{[words in sentence]}
    \SETST{{arcs $A$}}{$\emptyset$}
	\WHILE{{ $B\neq \emptyset$ or $|S| > 1$}}
	  \SETST{ValidActs}{\FUN{GetValidActions}($S, B$)}
	  \SETST{features}{\FUN{GetFeat}($S, B, A$)}
	  \SETST{ref}{\FUN{GetGoldAction}($S, B$)}
	  \SETST{action}{\FUN{predict}({features, ref, ValidActs})}
	  \SETST{$S, B, A$}{\FUN{Trans}($S, B , A$, action)}
%	  \SETST{arcLabel}{$\emptyset$}
%	  \IF{action $\in$ \{ReduceLeft, ReduceRight\}}
%		  \SETST{arcLabel}{\FUN{predict}({features, arc.goldLabel, ValidLabels})}
%	  \ENDIF
%	  \SETST{arcs, stack, head}{\FUN{Trans}(stack, head, arcs, action, arcLabel)}
    \ENDWHILE
    \STATE \FUN{loss}($A[w]$ $\neq$ $A^*[w]$, $\forall w \in$ sentence)
    \STATE \textbf{return} output
  }

As mentioned in the section~\ref{sec:dep}, this parser achieves state of the art accuracy across ten language from the CoNLL-X challenge, and requires only $300$ lines of readable C++ code.


\section{Hardware Used}

All timing results were obtained on the same machine with the
following configuration. Nothing else was run on this machine
concurrently:

\begin{verbatim}  
%   2 * Intel(R) Core(TM)2 Duo CPU E8500 @ 3.16GHz
  6144 KB cache
  8 GB RAM, 4 GB Swap
  Red Hat Enterprise Linux Workstation release 6.5 (Santiago)
  Linux 2.6.32-431.17.1.el6.x86_64 #1 SMP
    from Fri Apr 11 17:27:00 EDT 2014 x86_64 x86_64 x86_64 GNU/Linux
\end{verbatim}  


\section{Software Used}

The precise software versions used for comparison are:

\begin{itemize}
\item  Vowpal Wabbit version 7.10,
    commit 72994d3f1c5cdb33d842bac7bea146679c84ad98

\item
  CRF++ version 0.58

\item
  crfsgd version 2.0

\item
  svm\_hmm\_learn version 3.10, 14.08.08\\
    includes SVM-struct V3.10 for learning complex outputs, 14.08.08\\
    includes SVM-light V6.20 quadratic optimizer, 14.08.08

\item Illinois-SL version 0.2.2
\end{itemize}

\section{Hyperparameters Tuned}

The hyperparameters tuned and the values we considered for each system are:

\paragraph{CRF++}
\begin{tiny}
\begin{verbatim}
%     termination parameters:
      number of passes (--max_iter)     { 2, 4, 8, 16, 32, 64, 128 }
      termination criteria (--eta)      0.000000000001 (to prevent termination)

    tuned hyperparameters (default is *):
      learning algorithm (--algorithm)  { CRF*, MIRA }
      cost parameter (--cost)           { 0.0625, 0.125, 0.25, 0.5, 1*, 2, 4, 8, 16 }
\end{verbatim}
\end{tiny}

\paragraph{CRF SGD}
\begin{tiny}
\begin{verbatim}
%     termination parameters:
      number of passes (-r)             { 1, 2, 4, 8, 16, 32, 64, 128 }

    tuned hyperparameters (default is *):
      regularization parameter (-c)     { 0.0625, 0.125, 0.25, 0.5, 1*, 2, 4, 8, 16 }
      learning rate (-s)                { auto*, 0.1, 0.2, 0.5, 1, 2, 5 }
\end{verbatim}
\end{tiny}


\paragraph{Structured SVM}
\begin{tiny}
\begin{verbatim}
%     termination parameters:
      epsilon tolerance (-e)            { 4, 2, 1, 0.5, 0.1, 0.05, 0.01, 0.005, 0.001 }

    tuned hyperparameters (default is *):
      regularization parameter (-c)     { 0.0625, 0.125, 0.25, 0.5, 1*, 2, 4, 8, 16 }
\end{verbatim}
\end{tiny}


\paragraph{Structured Perceptron}
\begin{tiny}
\begin{verbatim}
%     termination parameters:
      number of passes (MAX_NUM_ITER)   { 1, 2, 4, 8, 16, 32, 64, 128 }

    tuned hyperparameters (default is *):
      NONE
\end{verbatim}
\end{tiny}


\paragraph{Structured SVM (DEMI-DCD)}
\begin{tiny}
\begin{verbatim}
%     termination parameters:
      number of passes (MAX_NUM_ITER)   { 1, 2, 4, 8, 16, 32, 64, 128 }

    tuned hyperparameters (default is *):
      regularization (C_FOR_STRUCTURE)  { 0.01, 0.05, 0.1*, 0.5, 1.0 }
\end{verbatim}
\end{tiny}


\paragraph{VW Search}
\begin{tiny}
\begin{verbatim}
    termination parameters:
      number of passes (--passes)       { 0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1, 2, 4 }
      (note: a number of passes < 1 means that we perform one full pass, but 
       _subsample_ the training positions for each sequence at the given rate)

    tuned hyperparameters (default is *):
      base classifier                   { csoaa*}
      interpolation rate                10^{-10, -9, -8, -7, -6 }
\end{verbatim}
\end{tiny}


\paragraph{VW Classifier}
\begin{tiny}
\begin{verbatim}
    termination parameters:
      number of passes (--passes)       { 1, 2, 4 }

    tuned hyperparameters (default is *):
      learning rate (-l)                { 0.25, 0.5*, 1.0 }
\end{verbatim}
\end{tiny}


\section{Templates Used}

For part of speech tagging (CRF++):

\begin{verbatim}
    U00:%x[-2,0]
    U01:%x[-1,0]
    U02:%x[0,0]
    U03:%x[1,0]
    U04:%x[2,0]
\end{verbatim}


For named entity recognition (CRF++):

\begin{verbatim}
    U00:%x[-2,0]
    U01:%x[-1,0]
    U02:%x[0,0]
    U03:%x[1,0]
    U04:%x[2,0]
    
    U10:%x[-2,1]
    U11:%x[-1,1]
    U12:%x[0,1]
    U13:%x[1,1]
    U14:%x[2,1]
    
    U15:%x[-2,1]/%x[-1,1]
    U16:%x[-1,1]/%x[0,1]
    U17:%x[0,1]/%x[1,1]
    U18:%x[1,1]/%x[2,1] 
\end{verbatim}

    (where words are in position 0 and POS is in 1)


For VW Search (own fts) on POS Tagging:

\begin{verbatim}
  --search_neighbor_features -1:w,1:w
  --affix -2w,+2w
\end{verbatim}

  (where words are in namespace "w")


For VW Search (own fts) on NER:

\begin{verbatim}
  --search_neighbor_features -2:w,-1:w,1:w,2:w,-1:p,1:p
  --affix -1w
\end{verbatim}

  (where words are in namespace "w" and POS is in "p")


\end{document}

preamble.tex
\usepackage{hyperref}
\usepackage{url}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{float}
\usepackage{amsthm}
\usepackage{multirow}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amsthm}
\usepackage{natbib}

\definecolor{mydarkblue}{rgb}{0,0.08,0.45}
\hypersetup{ %
  pdftitle={},
  pdfauthor={Anonymous Submission},
  pdfsubject={},
  pdfkeywords={},
  pdfborder=0 0 0,
  pdfpagemode=UseNone,
  colorlinks=true,
  linkcolor=mydarkblue,
  citecolor=mydarkblue,
  filecolor=mydarkblue,
  urlcolor=mydarkblue,
  pdfview=FitH}


\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}

\algsetup{linenosize=\tiny,
          linenodelimiter=:
          }

\renewcommand{\cite}[1]{\citep{#1}}

\definecolor{darkgrey}{rgb}{0.2,0.2,0.2}
\definecolor{grey}{rgb}{0.9,0.9,0.9}
\definecolor{darkblue}{rgb}{0.0,0.0,0.5}
\definecolor{darkpurple}{rgb}{0.4,0.0,0.4}
\definecolor{darkred}{rgb}{0.5,0.0,0.0}
\definecolor{darkorange}{rgb}{0.6,0.4,0.1}
\definecolor{darkgreen}{rgb}{0.0,0.5,0.0}
\definecolor{darkergreen}{rgb}{0.0,0.4,0.0}
\definecolor{lightblue}{rgb}{0.8,0.8,1.0}
\definecolor{lightgreen}{rgb}{0.8,1.0,0.8}
\definecolor{lightred}{rgb}{1.0,0.8,0.8}
\definecolor{lightyellow}{rgb}{1.0,1.0,0.8}
\definecolor{lightorange}{rgb}{1.0,0.9,0.8}
\definecolor{lightgrey}{rgb}{0.96,0.97,0.98}


\newcommand{\wordtag}[1]{\textsf{\scriptsize{\textcolor{darkblue}{#1}}}}
\newcommand{\overbracetxt}[2]{$\textcolor{darkblue}{\overbrace{\textnormal{\textcolor{black}{#1}}}^{\textsf{#2}}}$}

\newcommand{\algorithmicfont}{\normalfont\sffamily\footnotesize}
\newcommand{\algorithmiccolor}{darkergreen}

\newcommand{\GOTO}[1]{\STATE
  \textcolor{\algorithmiccolor}{\algorithmicfont goto~} {\large #1}}

\renewcommand{\algorithmicif}{\textcolor{\algorithmiccolor}{\algorithmicfont if}}
\renewcommand{\algorithmicrequire}{\textcolor{\algorithmiccolor}{\algorithmicfont Require:}}
\renewcommand{\algorithmicensure}{\textcolor{\algorithmiccolor}{\algorithmicfont Ensure:}}
\renewcommand{\algorithmicend}{\textcolor{\algorithmiccolor}{\algorithmicfont end}}
\renewcommand{\algorithmicif}{\textcolor{\algorithmiccolor}{\algorithmicfont if}}
\renewcommand{\algorithmicthen}{\textcolor{\algorithmiccolor}{\algorithmicfont then}}
\renewcommand{\algorithmicelse}{\textcolor{\algorithmiccolor}{\algorithmicfont else}}
\renewcommand{\algorithmicelsif}{\algorithmicelse\ \algorithmicif}
\renewcommand{\algorithmicendif}{\algorithmicend\ \algorithmicif}
\renewcommand{\algorithmicfor}{\textcolor{\algorithmiccolor}{\algorithmicfont for}}
\renewcommand{\algorithmicforall}{\textcolor{\algorithmiccolor}{\algorithmicfont for all}}
\renewcommand{\algorithmicdo}{\textcolor{\algorithmiccolor}{\algorithmicfont do}}
\renewcommand{\algorithmicto}{\textcolor{\algorithmiccolor}{\algorithmicfont to}}
\renewcommand{\algorithmicendfor}{\algorithmicend\ \algorithmicfor}
\renewcommand{\algorithmicwhile}{\textcolor{\algorithmiccolor}{\algorithmicfont while}}
\renewcommand{\algorithmicendwhile}{\algorithmicend\ \algorithmicwhile}
\renewcommand{\algorithmicloop}{\textcolor{\algorithmiccolor}{\algorithmicfont loop}}
\renewcommand{\algorithmicendloop}{\algorithmicend\ \algorithmicloop}
\renewcommand{\algorithmicrepeat}{\textcolor{\algorithmiccolor}{\algorithmicfont repeat}}
\renewcommand{\algorithmicuntil}{\textcolor{\algorithmiccolor}{\algorithmicfont until}}
\renewcommand{\algorithmicprint}{\textcolor{\algorithmiccolor}{\algorithmicfont print}}
\renewcommand{\algorithmicreturn}{\textcolor{\algorithmiccolor}{\algorithmicfont return}}
\renewcommand{\algorithmictrue}{\textcolor{\algorithmiccolor}{\algorithmicfont true}}
\renewcommand{\algorithmicfalse}{\textcolor{\algorithmiccolor}{\algorithmicfont false}}
\renewcommand{\algorithmicand}{\textcolor{\algorithmiccolor}{\algorithmicfont and}}
\renewcommand{\algorithmicor}{\textcolor{\algorithmiccolor}{\algorithmicfont or}}

\renewcommand{\algorithmiccomment}[1]{\hfill\textcolor{darkred}{\normalfont\sffamily// #1}}

\newcommand{\VAR}[1]{\textcolor{darkblue}{\textit{#1}}}
\newcommand{\CON}[1]{\textcolor{darkgrey}{\textit{#1}}}
\newcommand{\FUN}[1]{\textcolor{darkpurple}{\textsc{#1}}}
\newcommand{\STR}[1]{\textcolor{darkergreen}{\textsc{#1}}}
\newcommand{\VARm}[1]{\textcolor{darkblue}{\ensuremath #1}}
\newcommand{\FUNm}[1]{\textcolor{blue}{\ensuremath #1}}

\newcommand{\SETST}[1]{\STATE \VAR{#1} $\leftarrow$ }
\newcommand{\SAMPLE}[1]{\STATE \VAR{#1} $\sim$ }

\newcommand{\feat}[1]{\textsc{\textcolor{darkpurple}{#1}}}

\floatname{algorithm}{\textcolor{\algorithmiccolor}{\algorithmicfont Algorithm}}

\newcommand{\newalgorithm}[3]{%
  \begin{algorithm}[t]
    \caption{#2}
    \begin{small}
      \begin{algorithmic}[1]
        #3
      \end{algorithmic}
    \end{small}
    \label{alg:#1}
  \end{algorithm}}


\newcommand{\predict}{\FUN{predict}(...)}
\newcommand{\loss}{\FUN{loss}(...)}

\usepackage{babel}
\providecommand{\theoremname}{Theorem}

\renewcommand{\brack}[1]{\left\{\begin{array}{ll}#1\end{array}\right.}
\newcommand{\myreturn}{\textcolor{\algorithmiccolor}{\algorithmicfont return~~}}
\newcommand{\cO}{\mathcal{O}}

\newcommand{\system}[1]{\textsf{\footnotesize #1}}
\newcommand{\pmstring}[1]{\textcolor{gray}{\scriptsize$\pm #1$}}

\makeatletter
\let\origsection\section
\let\origsubsection\subsection
\renewcommand\section{\@ifstar{\starsection}{\nostarsection}}
\renewcommand\subsection{\@ifstar{\starsubsection}{\nostarsubsection}}
\newcommand\nostarsection[1]{\sectionprelude\origsection{#1}\sectionpostlude}
\newcommand\starsection[1]  {\sectionprelude\origsection*{#1}\sectionpostlude}
\newcommand\nostarsubsection[1]{\subsectionprelude\origsubsection{#1}\subsectionpostlude}
\newcommand\starsubsection[1]  {\subsectionprelude\origsubsection*{#1}\subsectionpostlude}
\makeatother

\newcommand{\textbsf}[1]{{\bf \textsf{\small #1}}}
