\section{Electronic Submission}
\label{submission}

Submission to ICML 2017 will be entirely electronic, via a web site
(not email).  Information about the submission process and \LaTeX\ templates
are available on the conference web site at:
\begin{center}
\textbf{\texttt{http://icml.cc/2017/}}
\end{center}
Send questions about submission and electronic templates to
\texttt{icml2017pc@gmail.com}.

The guidelines below will be enforced for initial submissions and
camera-ready copies.  Here is a brief summary:
\begin{itemize}
\item Submissions must be in PDF.
\item The maximum paper length is \textbf{8 pages excluding references and acknowledgements, and 10 pages
  including references and acknowledgements} (pages 9 and 10 must contain only references and acknowledgements).
\item Do \textbf{not include author information or acknowledgements} in your initial
submission. 
\item Your paper should be in \textbf{10 point Times font}.
\item Make sure your PDF file only uses Type-1 fonts.
\item Place figure captions {\em under} the figure (and omit titles from inside
the graphic file itself).  Place table captions {\em over} the table.
\item References must include page numbers whenever possible and be as complete
as possible.  Place multiple citations in chronological order.  
\item Do not alter the style template; in particular, do not compress the paper
format by reducing the vertical spaces.
\item Keep your abstract brief and self-contained, one
   paragraph and roughly 4--6 sentences.  Gross violations will require correction at the camera-ready phase.
  Title should have content words capitalized.
  

\end{itemize}

\subsection{Submitting Papers}

{\bf Paper Deadline:} The deadline for paper submission to ICML 2017
is at \textbf{23:59 Universal Time (3:59 p.m.\ Pacific Standard Time) on February 24, 2017}.
If your full submission does not reach us by this time, it will 
not be considered for publication. There is no separate abstract submission.

{\bf Anonymous Submission:} To facilitate blind review, no identifying
author information should appear on the title page or in the paper
itself.  Section~\ref{author info} will explain the details of how to
format this.

{\bf Simultaneous Submission:} ICML will not accept any paper which,
at the time of submission, is under review for another conference or
has already been published. This policy also applies to papers that
overlap substantially in technical content with conference papers
under review or previously published. ICML submissions must not be
submitted to other conferences during ICML's review period. Authors
may submit to ICML substantially different versions of journal papers
that are currently under review by the journal, but not yet accepted
at the time of submission. Informal publications, such as technical
reports or papers in workshop proceedings which do not appear in
print, do not fall under these restrictions.

\medskip

To ensure our ability to print submissions, authors must provide their
manuscripts in \textbf{PDF} format.  Furthermore, please make sure
that files contain only Type-1 fonts (e.g.,~using the program {\tt
  pdffonts} in linux or using File/DocumentProperties/Fonts in
Acrobat).  Other fonts (like Type-3) might come from graphics files
imported into the document.

Authors using \textbf{Word} must convert their document to PDF.  Most
of the latest versions of Word have the facility to do this
automatically.  Submissions will not be accepted in Word format or any
format other than PDF. Really. We're not joking. Don't send Word.

Those who use \textbf{\LaTeX} to format their accepted papers need to pay close
attention to the typefaces used.  Specifically, when producing the PDF by first
converting the dvi output of \LaTeX\ to Postscript the default behavior is to
use non-scalable Type-3 PostScript bitmap fonts to represent the standard
\LaTeX\ fonts. The resulting document is difficult to read in electronic form;
the type appears fuzzy. To avoid this problem, dvips must be instructed to use
an alternative font map.  This can be achieved with the following two commands:

{\footnotesize
\begin{verbatim}
dvips -Ppdf -tletter -G0 -o paper.ps paper.dvi
ps2pdf paper.ps
\end{verbatim}}
Note that it is a zero following the ``-G''.  This tells dvips to use
the config.pdf file (and this file refers to a better font mapping).

A better alternative is to use the \textbf{pdflatex} program instead of
straight \LaTeX. This program avoids the Type-3 font problem, however you must
ensure that all of the fonts are embedded (use {\tt pdffonts}). If they are
not, you need to configure pdflatex to use a font map file that specifies that
the fonts be embedded. Also you should ensure that images are not downsampled
or otherwise compressed in a lossy way.

Note that the 2017 style files use the {\tt hyperref} package to
make clickable links in documents.  If this causes problems for you,
add {\tt nohyperref} as one of the options to the {\tt icml2017}
usepackage statement.

\subsection{Reacting to Reviews}

We will continue the ICML tradition in which the authors are given the
option of providing a short reaction to the initial reviews. These
reactions will be taken into account in the discussion among the
reviewers and area chairs.

\subsection{Submitting Final Camera-Ready Copy}

The final versions of papers accepted for publication should follow the
same format and naming convention as initial submissions, except of
course that the normal author information (names and affiliations)
should be given.  See Section~\ref{final author} for details of how to
format this.

The footnote, ``Preliminary work.  Under review by the International
Conference on Machine Learning (ICML).  Do not distribute.'' must be
modified to ``\textit{Proceedings of the
$\mathit{34}^{th}$ International Conference on Machine Learning},
Sydney, Australia, 2017.  JMLR: W\&CP. 
Copyright 2017 by the author(s).''

For those using the \textbf{\LaTeX} style file, simply change
$\mathtt{\backslash usepackage\{icml2017\}}$ to 

$$\mathtt{\backslash usepackage[accepted]\{icml2017\}}$$

\noindent
Authors using \textbf{Word} must edit the
footnote on the first page of the document themselves.

Camera-ready copies should have the title of the paper as running head
on each page except the first one.  The running title consists of a
single line centered above a horizontal rule which is $1$ point thick.
The running head should be centered, bold and in $9$ point type.  The
rule should be $10$ points above the main text.  For those using the
\textbf{\LaTeX} style file, the original title is automatically set as running
head using the {\tt fancyhdr} package which is included in the ICML
2017 style file package.  In case that the original title exceeds the
size restrictions, a shorter form can be supplied by using

\verb|\icmltitlerunning{...}|

just before $\mathtt{\backslash begin\{document\}}$.
Authors using \textbf{Word} must edit the header of the document themselves.

\section{Format of the Paper} 
 
All submissions must follow the same format to ensure the printer can
reproduce them without problems and to let readers more easily find
the information that they desire.

\subsection{Length and Dimensions}

Papers must not exceed eight (8) pages, including all figures, tables,
and appendices, but excluding references and acknowledgements. When references and acknowledgements are included,
the paper must not exceed ten (10) pages.
Acknowledgements should be limited to grants and people who contributed to the paper.
Any submission that exceeds 
this page limit or that diverges significantly from the format specified 
herein will be rejected without review.

The text of the paper should be formatted in two columns, with an
overall width of 6.75 inches, height of 9.0 inches, and 0.25 inches
between the columns. The left margin should be 0.75 inches and the top
margin 1.0 inch (2.54~cm). The right and bottom margins will depend on
whether you print on US letter or A4 paper, but all final versions
must be produced for US letter size.

The paper body should be set in 10~point type with a vertical spacing
of 11~points. Please use Times typeface throughout the text.

\subsection{Title}

The paper title should be set in 14~point bold type and centered
between two horizontal rules that are 1~point thick, with 1.0~inch
between the top rule and the top edge of the page. Capitalize the
first letter of content words and put the rest of the title in lower
case.

\subsection{Author Information for Submission}
\label{author info}

To facilitate blind review, author information must not appear.  If
you are using \LaTeX\/ and the \texttt{icml2017.sty} file, you may use
\verb+\icmlauthor{...}+ to specify authors.  The author information
will simply not be printed until {\tt accepted} is an argument to the
style file. Submissions that include the author information will not
be reviewed.

\subsubsection{Self-Citations}

If your are citing published papers for which you are an author, refer
to yourself in the third person. In particular, do not use phrases
that reveal your identity (e.g., ``in previous work \cite{langley00}, we 
have shown \ldots'').

Do not anonymize citations in the reference section by removing or
blacking out author names. The only exception are manuscripts that are
not yet published (e.g. under submission). If you choose to refer to
such unpublished manuscripts \cite{anonymous}, anonymized copies have 
to be submitted
as Supplementary Material via CMT. However, keep in mind that an ICML
paper should be self contained and should contain sufficient detail
for the reviewers to evaluate the work. In particular, reviewers are
not required to look a the Supplementary Material when writing their
review.

\subsubsection{Camera-Ready Author Information}
\label{final author}

If a paper is accepted, a final camera-ready copy must be prepared.
For camera-ready papers, author information should start 0.3~inches
below the bottom rule surrounding the title. The authors' names should
appear in 10~point bold type, electronic mail addresses in 10~point
small capitals, and physical addresses in ordinary 10~point type.
Each author's name should be flush left, whereas the email address
should be flush right on the same line. The author's physical address
should appear flush left on the ensuing line, on a single line if
possible. If successive authors have the same affiliation, then give
their physical address only once.

A sample file (in PDF) with author names is included in the ICML2017 
style file package.

\subsection{Abstract}

The paper abstract should begin in the left column, 0.4~inches below
the final address. The heading `Abstract' should be centered, bold,
and in 11~point type. The abstract body should use 10~point type, with
a vertical spacing of 11~points, and should be indented 0.25~inches
more than normal on left-hand and right-hand margins. Insert
0.4~inches of blank space after the body. Keep your abstract brief and 
self-contained,
limiting it to one paragraph and roughly 4--6 sentences.  Gross violations will require correction at the camera-ready phase.

\subsection{Partitioning the Text} 

You should organize your paper into sections and paragraphs to help
readers place a structure on the material and understand its
contributions.

\subsubsection{Sections and Subsections}

Section headings should be numbered, flush left, and set in 11~pt bold
type with the content words capitalized. Leave 0.25~inches of space
before the heading and 0.15~inches after the heading.

Similarly, subsection headings should be numbered, flush left, and set
in 10~pt bold type with the content words capitalized. Leave
0.2~inches of space before the heading and 0.13~inches afterward.

Finally, subsubsection headings should be numbered, flush left, and
set in 10~pt small caps with the content words capitalized. Leave
0.18~inches of space before the heading and 0.1~inches after the
heading. 

Please use no more than three levels of headings.

\subsubsection{Paragraphs and Footnotes}

Within each section or subsection, you should further partition the
paper into paragraphs. Do not indent the first line of a given
paragraph, but insert a blank line between succeeding ones.
 
You can use footnotes\footnote{For the sake of readability, footnotes
should be complete sentences.} to provide readers with additional
information about a topic without interrupting the flow of the paper. 
Indicate footnotes with a number in the text where the point is most
relevant. Place the footnote in 9~point type at the bottom of the
column in which it appears. Precede the first footnote in a column
with a horizontal rule of 0.8~inches.\footnote{Multiple footnotes can
appear in each column, in the same order as they appear in the text,
but spread them across columns and pages if possible.}

\begin{figure}[ht]
\vskip 0.2in
\begin{center}
\centerline{\includegraphics[width=\columnwidth]{icml_numpapers}}
\caption{Historical locations and number of accepted papers for International
  Machine Learning Conferences (ICML 1993 -- ICML 2008) and
  International Workshops on Machine Learning (ML 1988 -- ML
  1992). At the time this figure was produced, the number of
  accepted papers for ICML 2008 was unknown and instead estimated.}
\label{icml-historical}
\end{center}
\vskip -0.2in
\end{figure} 

\subsection{Figures}
 
You may want to include figures in the paper to help readers visualize
your approach and your results. Such artwork should be centered,
legible, and separated from the text. Lines should be dark and at
least 0.5~points thick for purposes of reproduction, and text should
not appear on a gray background.

Label all distinct components of each figure. If the figure takes the
form of a graph, then give a name for each axis and include a legend
that briefly describes each curve. Do not include a title inside the
figure; instead, the caption should serve this function.

Number figures sequentially, placing the figure number and caption
{\it after\/} the graphics, with at least 0.1~inches of space before
the caption and 0.1~inches after it, as in
Figure~\ref{icml-historical}.  The figure caption should be set in
9~point type and centered unless it runs two or more lines, in which
case it should be flush left.  You may float figures to the top or
bottom of a column, and you may set wide figures across both columns
(use the environment {\tt figure*} in \LaTeX), but always place
two-column figures at the top or bottom of the page.

\subsection{Algorithms}

If you are using \LaTeX, please use the ``algorithm'' and ``algorithmic'' 
environments to format pseudocode. These require 
the corresponding stylefiles, algorithm.sty and 
algorithmic.sty, which are supplied with this package. 
Algorithm~\ref{alg:example} shows an example. 

\begin{algorithm}[tb]
   \caption{Bubble Sort}
   \label{alg:example}
\begin{algorithmic}
   \STATE {\bfseries Input:} data $x_i$, size $m$
   \REPEAT
   \STATE Initialize $noChange = true$.
   \FOR{$i=1$ {\bfseries to} $m-1$}
   \IF{$x_i > x_{i+1}$} 
   \STATE Swap $x_i$ and $x_{i+1}$
   \STATE $noChange = false$
   \ENDIF
   \ENDFOR
   \UNTIL{$noChange$ is $true$}
\end{algorithmic}
\end{algorithm}
 
\subsection{Tables} 
 
You may also want to include tables that summarize material. Like 
figures, these should be centered, legible, and numbered consecutively. 
However, place the title {\it above\/} the table with at least 
0.1~inches of space before the title and the same after it, as in 
Table~\ref{sample-table}. The table title should be set in 9~point 
type and centered unless it runs two or more lines, in which case it
should be flush left.


\begin{table}[t]
\caption{Classification accuracies for naive Bayes and flexible 
Bayes on various data sets.}
\label{sample-table}
\vskip 0.15in
\begin{center}
\begin{small}
\begin{sc}
\begin{tabular}{lcccr}
\hline
\abovespace\belowspace
Data set & Naive & Flexible & Better? \\
\hline
\abovespace
Breast    & 95.9$\pm$ 0.2& 96.7$\pm$ 0.2& $\surd$ \\
Cleveland & 83.3$\pm$ 0.6& 80.0$\pm$ 0.6& $\times$\\
Glass2    & 61.9$\pm$ 1.4& 83.8$\pm$ 0.7& $\surd$ \\
Credit    & 74.8$\pm$ 0.5& 78.3$\pm$ 0.6&         \\
Horse     & 73.3$\pm$ 0.9& 69.7$\pm$ 1.0& $\times$\\
Meta      & 67.1$\pm$ 0.6& 76.5$\pm$ 0.5& $\surd$ \\
Pima      & 75.1$\pm$ 0.6& 73.9$\pm$ 0.5&         \\
\belowspace
Vehicle   & 44.9$\pm$ 0.6& 61.5$\pm$ 0.4& $\surd$ \\
\hline
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vskip -0.1in
\end{table}

Tables contain textual material that can be typeset, as contrasted 
with figures, which contain graphical material that must be drawn. 
Specify the contents of each row and column in the table's topmost
row. Again, you may float tables to a column's top or bottom, and set
wide tables across both columns, but place two-column tables at the
top or bottom of the page.
 
\subsection{Citations and References} 

Please use APA reference format regardless of your formatter
or word processor. If you rely on the \LaTeX\/ bibliographic 
facility, use {\tt natbib.sty} and {\tt icml2017.bst} 
included in the style-file package to obtain this format.

Citations within the text should include the authors' last names and
year. If the authors' names are included in the sentence, place only
the year in parentheses, for example when referencing Arthur Samuel's
pioneering work \yrcite{Samuel59}. Otherwise place the entire
reference in parentheses with the authors and year separated by a
comma \cite{Samuel59}. List multiple references separated by
semicolons \cite{kearns89,Samuel59,mitchell80}. Use the `et~al.'
construct only for citations with three or more authors or after
listing all authors to a publication in an earlier reference \cite{MachineLearningI}.

Authors should cite their own work in the third person
in the initial version of their paper submitted for blind review.
Please refer to Section~\ref{author info} for detailed instructions on how to
cite your own papers.

Use an unnumbered first-level section heading for the references, and 
use a hanging indent style, with the first line of the reference flush
against the left margin and subsequent lines indented by 10 points. 
The references at the end of this document give examples for journal
articles \cite{Samuel59}, conference publications \cite{langley00}, book chapters \cite{Newell81}, books \cite{DudaHart2nd}, edited volumes \cite{MachineLearningI}, 
technical reports \cite{mitchell80}, and dissertations \cite{kearns89}. 

Alphabetize references by the surnames of the first authors, with
single author entries preceding multiple author entries. Order
references for the same authors by year of publication, with the
earliest first. Make sure that each reference includes all relevant
information (e.g., page numbers).

\subsection{Software and Data}

We strongly encourage the publication of software and data with the
camera-ready version of the paper whenever appropriate.  This can be
done by including a URL in the camera-ready copy.  However, do not
include URLs that reveal your institution or identity in your
submission for review.  Instead, provide an anonymous URL or upload
the material as ``Supplementary Material'' into the CMT reviewing
system.  Note that reviewers are not required to look a this material
when writing their review.

\section*{Acknowledgements} 
 
\textbf{Do not} include acknowledgements in the initial version of
the paper submitted for blind review.

If a paper is accepted, the final camera-ready version can (and
probably should) include acknowledgements. In this case, please
place such acknowledgements in an unnumbered section at the
end of the paper. Typically, this will include thanks to reviewers
who gave useful comments, to colleagues who contributed to the ideas, 
and to funding agencies and corporate sponsors that provided financial 
support.  


\nocite{langley00}


\subsubsection{Data and Preprocessing and Baselines}
We consider the CoNLL 2005 shared task data~\citep{carreras2005introduction}, with standard data splits and official evaluation scripts. We apply similar preprocessing as~\citet{tackstrom2015efficient}. This includes part-of-speech tagging, dependency parsing, and using
the parse to generate candidate arguments. 

Our baseline is an arc-factored model for the conditional probability of the predicate-argument arc labels:
\begin{equation}
\mathbb{P}(\mathbf{r}|\mathbf{x},\mathbf{p},\mathbf{a}) = \Pi_i \mathbb{P}(\mathbf{r}_i |\mathbf{x},\mathbf{p},\mathbf{a}). \label{eq:arc-factored}
\end{equation}
where $\mathbb{P}(r_i |\mathbf{x},\mathbf{p},\mathbf{a})\propto \exp\big(g(\mathbf{r}_i, \mathbf{x},\mathbf{p},\mathbf{a}) \big)$. Here, each conditional distribution is given by a multiclass logistic regression model. See Appendix~\ref{app:srl-feat-arch} for details of the architecture and training procedure for our baseline.




When using the negative log of Eq.~\eqref{eq:arc-factored} as an energy in Eq.~\eqref{eq:srl-eb}, there are variety of methods for finding a near-optimal $\mathbf{r} \in \mathcal{Q}(\mathbf{x},\mathbf{p},\mathbf{a})$. First, we can employ simple heuristics for locally resolving constraint violation. The \textbf{Local + H} system uses Eq.~\eqref{eq:arc-factored} and these. We can instead use the AD$^3$ message passing algorithm~\citep{martins2011augmented} to solve the LP relaxation of this constrained problem. We use \textbf{Local + AD}$^3$ to refer to this system. Since the LP solution may not be integral, we post-process the AD$^3$ output using the same heuristics as \textbf{Local + H}. 


\subsubsection{SPEN Model}

The SPEN performs continuous optimization over the relaxed set $\mathbf{y}_i \in \Delta_A$ for each discrete label $\mathbf{r}_i$, where $A$ is the number of possible roles. The preprocessing generates sparse predicate-argument candidates, but we optimize over the complete bipartite graph between predicates and arguments to support vectorization. We have $\mathbf{y} \in \Delta_A^{n \times m}$, where $n$ and $m$ are the max number of predicates and arguments. Invalid arcs are constrained to the empty label.

We employ a pretrained version of Eq.~\eqref{eq:arc-factored} to provide the local energy term of a SPEN. This is augmented with global terms that couple the outputs together. See Appendix~\ref{sec:srl-arch} for details of the architecture we use. It has terms, for example, that apply a deep network to the feature representations of all of the arcs selected for a given predicate. 

As with~\citet{tackstrom2015efficient}, we seek to account for constraints $\mathcal{Q}(\mathbf{x},\mathbf{p},\mathbf{a})$ during both inference and learning, rather than only imposing them via post-processing. Therefore, we include additional energy terms that encode membership in $\mathcal{Q}(\mathbf{x},\mathbf{p},\mathbf{a})$ as twice-differentiable soft constraints that can be applied to $\mathbf{y}$. All of the constraints in $\mathcal{Q}(\mathbf{x},\mathbf{p},\mathbf{a})$ express that certain arcs cannot co-occur. For example, two arguments cannot attach to the same predicate if the arguments correspond to spans of tokens that overlap. Consider general binary variables $a$ and $b$ with corresponding relaxations $\bar{a},\bar{b} \in [0,1]$. We convert the constraint $\lnot (a \land b)$ into an energy function $\alpha\text{SoftPlus}(\bar{a} + \bar{b} - 1)$, where $\alpha$ is a learned parameter. 

We consider the \textbf{SPEN + H} and \textbf{SPEN + AD}$^3$ configurations, which employ heuristics or AD$^3$ to enforce the output constraints. Rather than applying these methods to the probabilities from Eq.~\eqref{eq:arc-factored}, we use the soft prediction output by energy minimization. 

\begin{table}
\begin{footnotesize}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
& Dev  & Test  & Test\\
Model & (WSJ) & (WSJ) & (Brown) \\
\hline
{\bf Local + H} & 78.0 & 79.7 & 69.7\\
\hline
{\bf Local + AD}$^3$ & 78.2 & 80.0 & 69.9\\
\hline
{\bf SPEN + H} & 79.0 & 80.7 & 69.3\\
\hline
{\bf SPEN + AD}$^3$ & \textbf{79.0} & \textbf{80.7} & 69.4\\
\hline
\hline
T{\"a}ckstr{\"o}m (Local) & 77.9 & 79.3 & 70.2\\
\hline
T{\"a}ckstr{\"o}m (Structured) & 78.6 & 79.9 & \textbf{71.3}\\
\hline
FitzGerald (Local) & 78.4 & 79.4 & 70.9\\
\hline
FitzGerald (Structured) & 78.3 & 79.4 & 71.2\\
\hline
\end{tabular}
\end{center}
\caption{SRL Results (F1)}
\label{table:srl}
\end{footnotesize}
\end{table}


\subsubsection{Results and Discussion}
Table~\ref{table:srl} contains results on the CoNLL 2005 WSJ dev and test sets and the Brown test set. We compare the \textbf{SPEN} and \textbf{Local} systems with the best non-ensemble systems of~\citet{tackstrom2015efficient} and~\citet{fitzgerald2015semantic}, which have similar overall setups as us for feature extraction and for the parametrization of the local energy terms. For these,  `Local' fits Eq.~\eqref{eq:arc-factored} without regard for the output constraints, whereas `Structured' explicitly considers them during training. Note that~\citet{zhou2015end} obtain slightly better performance with alternative RNN methods. We were unable to outputerform the \textbf{Local} systems using a \textbf{SPEN} system trained with an SSVM loss.

We select our SPEN configuration by maximizing performance of \textbf{SPEN + AD}$^3$ on the dev data. Our best system unrolls for 10 iterations, trains per-iteration learning rates, uses no momentum, and unrolls Eq.~\eqref{eq:logit}.  Overall, \textbf{SPEN + AD}$^3$ performs the best of all systems on the WSJ test data. We expect our diminished performance on the Brown test set is due to overfitting. The Brown set is not from the same source as the train, dev, and test WSJ data. SPENs are more susceptible to overfitting because the expressive global term introduces many parameters. 

Note that \textbf{SPEN + AD}$^3$ and \textbf{SPEN + H} performs identically, whereas \textbf{LOCAL + AD}$^3$ and \textbf{LOCAL + H} do not. This is because our learned global energy encourages constraint satisfaction during gradient-based optimization of $\mathbf{y}$. Using the method of~\citet{amos2016input} for restricting the energy to be convex wrt $\mathbf{y}$, we obtain 80.3 on the test set.





\section{Introduction}

In a variety of application domains, given an input $\mathbf{x}$ we seek to predict a structured output $\mathbf{y}$. For example, given a noisy image, we predict a clean version of it, or given a sentence we predict its semantic structure. Often, it is insufficient to employ a feed-forward predictor $\mathbf{y} = F(\mathbf{x})$, since this may have prohibitive sample complexity, fail to model global interactions among outputs, or fail to enforce hard output constraints. Instead, it can be advantageous to define the prediction function implicitly in terms of energy minimization~\citep{lecun2006tutorial}:
\begin{equation}
\mathbf{\hat{y}} = \argmin_\mathbf{y} E_{\mathbf{x}}(\mathbf{y}) \label{eq:spen}, 
\end{equation}
where $E_{\mathbf{x}}(\cdot)$ depends on $\mathbf{x}$ and learned parameters. 

This approach includes factor graphs~\citep{kschischang2001factor}, e.g., conditional random fields (CRFs)~\citep{lafferty2001conditional}, and many recurrent neural networks (Sec.~\ref{sec:fac-energy}).
Output constraints can be enforced using constrained optimization. Compared to feed-forward approaches, energy-based approaches often provide better opportunities to inject prior knowledge about likely outputs and often have more parsimonious models. On the other hand, energy-based prediction requires non-trivial search in the exponentially-large space of outputs, and search techniques often need to be designed on a case-by-case basis.

Structured prediction energy networks (SPENs)~\citep{belanger2016structured} help reduce these concerns. They can capture high-arity interactions among components of $\mathbf{y}$ that would lead to intractable factor graphs and provide a mechanism for automatic structure learning. This is accomplished by expressing the energy function in Eq.~\eqref{eq:spen} as a deep architecture and forming predictions by approximately optimizing $\mathbf{y}$ using gradient descent. 

While providing the expressivity and generality of deep networks, SPENs also maintain the useful semantics of energy functions: domain experts can design architectures to capture known properties of the data, energy functions can be combined additively, and we can perform constrained optimization over $\mathbf{y}$. Most importantly, SPENs provide for black-box interaction with the energy, via forward and back-propagation. This allows practitioners to explore a wide variety of models without the need to hand-design corresponding prediction methods. 

\citet{belanger2016structured} train SPENs using a structured SVM (SSVM) loss~\citep{koller2004max,tsochantaridis2004support} and achieve competitive performance on simple multi-label classification tasks. Unfortunately, we have found it difficult to extend their method to more complex domains. SSVMs are unreliable when \text{exact} energy minimization is intractable, as loss-augmented inference may fail to discover margin violations (Sec.~\ref{sec:learning-exact}). 

In response, we present end-to-end training of SPENs, where one directly back-propagates through a computation graph that unrolls gradient-based energy minimization. This does not assume that exact minimization is tractable, and instead directly optimizes the practical performance of a particular approximate minimization algorithm. End-to-end training for gradient-based prediction was introduced in~\citet{domke2012generic} and applied to deep energy models by~\citet{brakel2013training}. See Sec.~\ref{sec:unrolled} for details.

When applying end-to-end training to SPENs for problems with sophisticated output structure, we have encountered a variety of technical challenges. The core contribution of this paper is a set of general-purpose solutions for overcoming these.  Sec.~\ref{sec:simplex} alleviates the effect of vanishing gradients when training SPENs defined over the convex relaxation of discrete prediction problems. Sec.~\ref{sec:fast} trains energies such that gradient-based minimization is fast. Sec.~\ref{sec:eff-impl} reduces SPENs' computation and memory overhead. Finally, Sec.~\ref{sec:rec-archs} provides practical recommendations for specific architectures, parameter tying schemes, and pretraining methods that reduce overfitting and improve efficiency.

We demonstrate the effectiveness of our SPEN training methods on two diverse tasks. We first consider depth image denoising on the 7-Scenes dataset~\citep{newcombe2011kinectfusion}, where we employ deep convolutional networks as priors over images. This provides a significant performance improvement, from 36.3 to 40.4 PSNR, over the recent work of~\citep{wang2016proximal}, which unrolls more sophisticated optimization than us, but uses a simpler image prior.  After that, we apply SPENs to semantic role labeling (SRL) on the CoNLL-2005 dataset~\citep{carreras2005introduction}. The task is challenging for SPENs because the output is discrete, sparse, and subject to rigid non-local constraints. We show how to formulate SRL as a SPEN problem and demonstrate performance improvements over strong baselines that use deep features, but sufficiently simple energy functions that the constraints can be enforced using dynamic programming.

Despite substantial differences between the two applications, learning and prediction for all models is performed using the same gradient-based prediction and end-to-end learning code. This black-box interaction with the model provides many opportunities for further use of SPENs. 



\section{Structured Prediction Energy Networks}
A SPEN is defined as an instance of Eq.~\eqref{eq:spen} where the energy is given by a deep neural network that provides a subroutine for efficiently evaluating $\frac{d}{d \mathbf{y}} E_{\mathbf{x}}(\mathbf{y})$~\citep{belanger2016structured}. Differentiability necessitates that the energy is defined on continuous inputs. Going forward, $\mathbf{y}$ will always be continuous. Prediction is performed by gradient-based optimization with respect to $\mathbf{y}$. 

This section first motivates the SPENs employed in this paper, by contrasting them with alternative energy-based approaches to structured prediction. Then, we present two families of methods for training energy-based structured prediction models that have been explored in prior work. 



\subsection{Black-Box vs. Factorized Energy Functions}
\label{sec:fac-energy}
The definition of SPENs above is extremely general and includes many existing modeling techniques. However, both this paper and~\citet{belanger2016structured} depart from most prior work by employing monolithic energy functions that only provide forward and back-propagation. 

This contrasts with the two principal families of energy-based models in the literature, where the tractability of (approximate) energy minimization depends crucially on the factorization structure of the energy. 
First, \textit{factor graphs} decompose the energy into a sum of functions defined over small sets of subcomponents of $\mathbf{y}$~\citep{kschischang2001factor}.
This structure provides opportunities for energy minimization using message passing, MCMC, or combinatorial solvers. Second, \textit{autoregressive models}, such as recurrent neural networks (RNNs) assume an ordering on the components of $\mathbf{y}$ such that the energy for component $\mathbf{y}_i$ only depends on its predecessors. Approximate energy minimization can be performed using search in the space of prefixes of $\mathbf{y}$ using beam search or greedy search. See, for example,~\citet{sutskever2014sequence}.


By not relying on any such factorization when choosing learning and prediction algorithms for SPENs, we can consider much broader families of deep energy functions.  We do not specify the interaction structure in advance, but instead learn it automatically by fitting a deep network. This can capture sophisticated global interactions among components of $\mathbf{y}$ that are difficult to represent using a factorized energy. Of course, the downside of such SPENs is that they provide few guarantees, particularly when employing non-convex energies. Furthermore, for problems with hard constraints on outputs, the ability to do effective constrained optimization may have depended crucially on certain factorization structure. 

\subsection{Learning as Conditional Density Estimation}
One method for estimating the parameters of an energy-based model $E_{\mathbf{x}}(\mathbf{y})$ is to maximize the conditional likelihood of $\mathbf{y}$:
\begin{align}
\mathbb{P}(\mathbf{y} | \mathbf{x}) \propto \exp\left(-E_{\mathbf{x}}(\mathbf{y})\right).
\end{align}
Unfortunately, computing the likelihood requires the distribution's normalizing constant, which is intractable for black-box energies with no available factorization structure. In~\textit{contrastive backprop}, this is circumvented by performing contrastive divergence training, with Hamiltonian Monte Carlo sampling from the energy surface~\citep{mnih2005learning,hinton2006unsupervised,ngiam2011learning}. Recently,~\citet{zhai2016deep} trained energy-based density models for anomaly detection by exploiting the connections between denosing autoencoders, energy-based models, and score matching~\citep{vincent2011connection}. 


\subsection{Learning with Exact Energy Minimization}
\label{sec:learning-exact}
Let $\Delta(\hat{\mathbf{y}},\mathbf{y}^*)$ be a non-negative task-specific cost function for comparing $\hat{\mathbf{y}}$ and the ground truth $\mathbf{y}^*$.  ~\citet{belanger2016structured} employ a structured SVM (SSVM) loss ~\citep{koller2004max,tsochantaridis2004support}:
\begin{equation}
\sum_{\{\mathbf{x}_i,\mathbf{y}_i\}} \max_{\mathbf{y}} \left[\Delta(\mathbf{y},\mathbf{y}_i)- E_{\mathbf{x}_i}(\mathbf{y}) + E_{\mathbf{x}_i}(\mathbf{y}_i)\right]_+, \label{eq:ssvm}
\end{equation}
where $\left[\cdot\right]_+ = \max(0,\cdot)$. Each step of minimizing Eq.~\eqref{eq:ssvm} by subgradient descent requires \textit{loss-augmented inference}: 
\begin{equation}
\min_{\mathbf{y}} \left(-\Delta(\mathbf{y},\mathbf{y}_i) + E_{\mathbf{x}_i}(\mathbf{y})\right). \label{eq:loss-aug}
\end{equation}
For differentiable $\Delta(\mathbf{y},\mathbf{y}_i)$,  a local optimum of Eq.~\eqref{eq:loss-aug} can obtained using first-order methods.

Solving Eq.~\eqref{eq:loss-aug} probes the model for margin violations. If none exist, the gradient of the loss with respect to the parameters is zero. Therefore, SSVM performance does not degrade gracefully with optimization errors in the inner prediction problem, since inexact energy minimization may fail to discover margin violations that exist. Performance can be recovered if Eq.~\eqref{eq:loss-aug} returns a lower bound, eg. by solving an LP relaxation~\citep{finley2008training}. However, this is not possible in general. In Sec.~\ref{sec:denoise-results} we compare the image denoising performance of SSVM learning vs. this paper's end-to-end method. Overall, we have found SSVM learning to be unstable and difficult to tune for non-convex energies in applications more complex than the multi-label classification experiments of~\citet{belanger2016structured}.

The~\textit{implicit function theorem} offers an alternative framework for training energy-based predictors~\citep{foo2008efficient,samuel2009learning}. See~\citet{domke2012generic} for an overview. While a naive implementation requires inverting Hessians, one can solve the product of an inverse Hessian and a vector using conjugate gradients, which can leverage the techniques discussed in Sec.~\ref{sec:unrolled} as a subroutine. To perform reliably, the method unfortunately requires exact energy minimization and many conjugate gradient iterations. 

Overall, both of these learning algorithms only update the energy function in the neighborhoods of the ground truth and the predictions of the current model. On the other hand, it may be advantageous to shape the entire energy surface such that is exhibits certain properties, e.g., gradient descent converges quickly when initialized well (Sec.~\ref{sec:fast}). Therefore, these methods may be undesirable even for problems where exact energy minimization is tractable.

For non-convex $E_{\mathbf{x}}(\mathbf{y})$, gradient-based prediction will only find a local optimum. \citet{amos2016input} present \textit{input-convex neural networks} (ICNNs), which employ an easy-to-implement method for constraining the parameters of a SPEN such that the energy is convex with respect to $\mathbf{y}$, but perhaps non-convex with respect to the parameters. One simply uses convex, non-decreasing non-linearities and only non-negative parameters in any part of the computation graph downstream from $\mathbf{y}$. Here, prediction will return the global optimum, but convexity, especially when achieved this way, may impose a strong restriction on the expressivity of the energy. Their construction is a sufficient condition for achieving convexity, but there are convex energies that disobey this property.  Our experiments present results for instances of ICNNs. In general, non-convex SPENS perform better. 


\section{Learning with Unrolled Optimization}
\label{sec:unrolled}

The methods of Sec.~\ref{sec:learning-exact} are unreliable with non-convex energies because we cannot simply use the output of inexact energy minimization as a drop-in replacement for the exact minimizer. Instead, a collection of prior work has performed end-to-end learning of gradient-based predictors~\citep{gregor2010learning,domke2012generic,MacDuvAda2015hyper,andrychowicz2016learning,wang2016proximal,metz2016unrolled,greff2016highway}. Rather than reasoning about the energy minimum as an abstract quantity, the authors pose a specific gradient-based algorithm for approximate energy minimization and optimize its empirical performance using back-propagation. This is a form of~\textit{direct risk minimization}~\citep{tappen2007learning,stoyanov2011empirical,domke2013learning}. 

Consider simple gradient descent: 
\begin{equation}
\mathbf{y}_T = \mathbf{y}_0 - \sum_{t = 1}^T \eta_t \frac{d}{d \mathbf{y}} E_\mathbf{x}(\mathbf{y}_t). \label{eq:gd1}
\end{equation}
To learn the energy function end-to-end, we can back-propagate through the unrolled optimization Eq.~\eqref{eq:gd1} for fixed $T$. 
With this, it can be rendered API-equivalent to a feed-forward network that takes $\mathbf{x}$ as input and returns a prediction for $\mathbf{y}$, and can thus be trained using standard methods. Furthermore, certain hyperparameters, such as the learning rates $\eta_t$, are trainable~\citep{domke2012generic}. 

This backpropagation requires non-standard interaction with a neural-network library because Eq.~\eqref{eq:gd1} computes gradients in the forward pass, and thus it must compute second order terms in the backwards pass. We can save space and computation by avoiding instantiating Hessian terms and instead directly computing Hessian-vector products. These can be achieved three ways. First, the method of~\citet{pearlmutter1994fast} is exact, but requires non-trivial code modifications. Second, some libraries construct computation graphs for gradients that are themselves differentiable. Third, we can employ finite-differences~\citep{domke2012generic}. 

It is clear that Eq.~\eqref{eq:gd1} can be naturally extended to certain alternative optimization methods, such as gradient descent with momentum, or L-BFGS~\citep{liu1989limited,domke2012generic}. These require an additional state vector $\textbf{h}_t$ that is evolved along with $\textbf{y}_t$ across iterations. \citet{andrychowicz2016learning} unroll gradient-descent, but employ a learned non-linear RNN to perform per-coordinate updates to $\mathbf{y}$. End-to-end learning is also applicable to special-case energy minimization algorithms for graphical models, such as mean-field inference and belief propagation~\citep{domke2013learning,chen2014semantic,tompson2014joint,li2014,hershey2014deep,zheng2015conditional}.


\section{End-to-End Learning for SPENs}
\label{sec:e2e-in-practice}
We now present details for applying the methods of the previous section to SPENs. We first describe considerations for learning SPENs defined for the convex relaxation of discrete labeling problems. Then, we describe how to encourage our models to optimize quickly in practice. Finally, we present methods for improving the speed and memory overhead of SPEN implementations.

Our experiments unroll either Eq.~\eqref{eq:gd1} or an analogous version implementing gradient descent with momentum.   We compute Hessian-vector products using the finite-difference method of~\citep{domke2012generic}, which allows black-box interaction with the energy. 

We avoid the RNN-based approach of~\citet{andrychowicz2016learning} because it diminishes the semantics of the energy, as the interaction between the optimizer and gradients of the energy is complicated. In recent work,~\citet{2017arXiv170304363G} propose an alternative learning method that fits the energy function such that $E_\mathbf{x}(\cdot) \approx -\Delta(\cdot,\mathbf{y}^*)$, where $\Delta$ is defined as in Sec.~\ref{sec:learning-exact}. This is an interesting direction for future research, as it allows for non-differentiable $\Delta$. The advantage of end-to-end learning, however, is that it provides a energy function that is precisely tuned for a particular test-time energy minimization procedure. 


\subsection{End-to-End Learning for Discrete Problems}
\label{sec:simplex}

To apply SPENs to a discrete structured prediction problem, we relax to a constrained continuous problem, apply SPEN prediction, and then round to a discrete output. For example, for tagging each pixel of a $h \times w$ image with a binary label, we would relax from $\{0,1\}^{w \times h}$ to $[0,1]^{w \times h}$, and if the pixels can take on one of $D$ values, we would relax from $\mathbf{y} \in \{0,\ldots, D\}^{w \times h}$ to $\Delta_D^{w \times h}$, where $\Delta_D$ is the probability simplex on $D$ elements. 

While this rounding introduces poorly-understood sources of error, it has worked well for non-convex energy-based prediction in multi-label classification~\citep{belanger2016structured}, sequence tagging~\citep{vilnis2015bethe}, and translation \citep{DBLP:journals/corr/HoangHC17}.

Both $[0,1]^{w \times h}$ and $\Delta_D^{w \times h}$ are Cartesian products of probability simplices, and it is easy to adopt existing methods for projected gradient optimization over the simplex.

First, it is natural to apply Euclidean projected gradient descent. Over $[0,1]^{w \times h}$, we have:
\begin{equation}
\mathbf{y}_{t+1} = \text{Clip}_{0,1}\left[\mathbf{y}_t  - \eta_t \nabla E_{\mathbf{x}}(\mathbf{y}_t)\right],
\end{equation}
This is unusable for end-to-end learning, however, since back-propagation through the projection will yield 0 gradients whenever $\mathbf{y}_t  - \eta_t \nabla E_{\mathbf{x}}(\mathbf{y}_t) \notin [0,1]$. This is similarly problematic for projection onto $\Delta_D^{w \times h}$~\citep{duchi2008efficient}.

Alternatively, we can apply entropic mirror descent, ie. projected gradient with distance measured by KL divergence~\citep{beck2003mirror}. For $\mathbf{y} \in \Delta_D^{w \times h}$, we have:
\begin{equation}
\mathbf{y}_{t+1} = \text{SoftMax}\left(\log(\mathbf{y}_t)  - \eta_t \nabla E_{\mathbf{x}}(\mathbf{y}_t)\right) \label{eq:emd}
\end{equation}
This is suitable for end-to-end learning, but the updates are similar to an RNN with sigmoid non-linearities, which is vulnerable to vanishing gradients~\citep{bengio1994learning}. 

Instead, we have found it useful to avoid constrained optimization entirely, by optimizing un-normalized logits $\mathbf{l}_t$, with $\mathbf{y}_t = \text{SoftMax}(\mathbf{l}_t)$:
\begin{equation}
\mathbf{l}_{t+1} = \mathbf{l}_t - \eta_t\nabla E_{\mathbf{x}}\left(\text{SoftMax}(\mathbf{l}_t)\right). \label{eq:logit}
\end{equation}
Here, the updates to $\mathbf{l}_t$ are additive, and thus will be less susceptible to vanishing gradients~\citep{hochreiter1997long,srivastava2015training,he2016deep}. 

Finally,~\citet{amos2016input} present the \textit{bundle entropy method} for convex optimization with simplex constraints, along with a method for differentiating the output of the optimizer. End-to-end learning for Eq.~\eqref{eq:gd} can be performed using generic learning software, since the unrolled optimization obeys the API of a feed-forward predictor, but unfortunately this is not true for their method. Future work should consider their method, however, as it performs very rapid energy minimization. 



\subsection{Learning to Optimize Quickly}     
\label{sec:fast}

We next enumerate methods for learning a model such that gradient-based energy minimization converges to high-quality $\mathbf{y}$ quickly. When using such methods, we have found it important to maintain the same optimization configuration, such as $T$, at both train and test time. 

First, we can encourage rapid optimization by defining our loss function as a sum of losses on every iterate $\mathbf{y}_t$, rather than only on the final one. Let $\ell(\mathbf{y}_t,\mathbf{y}^*)$ be a differentiable loss between an iterate and the ground truth. We employ
\begin{equation}
L = \frac{1}{T}\sum_{t=1}^Tw_t\ell(\mathbf{y}_t,\mathbf{y}^*), \label{eq:avg-loss}
\end{equation}
where $w_t$ is a non-negative weight. This encourages the model to achieve high-quality predictions early. It has the additional benefit that it reduces vanishing gradients, since a learning signal is introduced at every timestep. Our experiments use $w_t = \frac{1}{T - t + 1}$. 

Second, for the simplex-constrained problems of Sec.~\ref{sec:simplex}, we smooth the energy with an entropy term $\sum_i H(\mathbf{y}_i)$. This introduces extra strong convexity, which helps improve convergence. It also strengthens the parallel between SPEN prediction and marginal inference in a Markov random field, where the inference objective is expected energy plus entropy~\citep[p.~385]{koller2009probabilistic}. 

Third, we can set $T$ to a small value. Of course, this guarantees that optimization converges quickly on the train data. Here, we lose the contract that Eq.~\eqref{eq:gd} is even performing energy minimization, since it hasn't converged, but this may be acceptable if predictions are accurate. For example, some experiments achieve good performance with $T = 3$.

In future work, it may be fruitful to directly penalize convergence criteria, such as $\lVert \mathbf{y}_{t} - \mathbf{y}_{t-1}\rVert$ and $ \lVert \frac{d}{d\mathbf{y}_t} E_\mathbf{x}(\mathbf{y}_t) \rVert$.



\subsection{Efficient Implementation}
\label{sec:eff-impl}
Since we can explicitly encourage our model to converge quickly, it is important to exploit fast convergence at train time. Eq.~\eqref{eq:gd} is unrolled for a fixed $T$. However, if optimization converges at $T_0 < T$, it suffices to start back-propagation at $T_0$, since the updates to $\mathbf{y}_t$ for $t > T_0$ are the identity. Therefore, we unroll for a fixed number of iterations $T$, but iterate only until convergence is detected.

To support back-propagation, a naive implementation of Eq.~\eqref{eq:gd} would require $T$ clones of the energy (with tied parameters). We reduce memory overhead by checkpointing the inputs and outputs of the energy, but discarding its internal state. This allows us to use a single copy of the energy, but requires recomputing forward evaluations at specific $\mathbf{y}_t$ during the backwards pass. To save additional memory, we could have reconstructed the $\mathbf{y}_t$ on-the-fly either by reversing the dynamics of the energy minimization method~\citep{domke2013learning,MacDuvAda2015hyper} or by performing a small amount of extra forward-propagation~\citep{rey2000exact,lewis2003debugging}.


\section{Recommended SPEN Architectures for End-to-End Learning}
\label{sec:rec-archs}
 To train SPENs end-to-end, we write Eq.~\eqref{eq:gd1} as:
\begin{equation}
\mathbf{y}_T = \text{Init}(F(\mathbf{x})) - \sum_{t = 1}^T \eta_t \frac{d}{d \mathbf{y}} E(\mathbf{y}_t \; ; \; F(\mathbf{x})). \label{eq:gd}
\end{equation}
Here, $\text{Init}(\cdot)$ is a differentiable procedure for predicting an initial iterate $\mathbf{y}_0$. 
Following~\citet{belanger2016structured}, we also employ $E_{\mathbf{x}}(\mathbf{y}) = E(\mathbf{y} \; ; \; F(x))$,  where the dependence of $E_{\mathbf{x}}(\mathbf{y})$ on $\mathbf{x}$ comes by way of a parametrized feature function $F(\mathbf{x})$. This is useful because test-time prediction can avoid back-propagation in $F(x)$. 

We have found it useful in practice to employ an energy that splits into global and local terms:
\begin{equation}
E(\mathbf{y} \; ;F(\mathbf{x}) ) = E^g(\mathbf{y} \; ;F(\mathbf{x}))  + \sum_i  E_i^l(\mathbf{y}_i \; ;F(\mathbf{x})).
\end{equation}
Here, $i$ indexes the components of $\mathbf{y}$ and $E^g(\mathbf{y} \; ;F(\mathbf{x}))$ is an arbitrary global energy function.  The modeling benefits of the local terms are similar to the benefits of using local factors in popular factor graph models. We also can use the local terms to provide an implementation of $\text{Init}(\cdot)$.

We pretrain $F(x)$ by training the feed-forward predictor $\text{Init}(F(x))$. We also stabilize learning by first clamping the local terms for a few epochs while updating $E^g(\mathbf{y} \; ;F(\mathbf{x}))$.

To back-propagate through Eq.~\eqref{eq:gd}, the energy function must be at least twice differentiable with respect to $\mathbf{y}$. Therefore, we can't use non-linearities with discontinuous gradients. Instead of ReLUs, we use a SoftPlus with a reasonably high temperature. Note that $F(\mathbf{x})$ and $\text{Init}(\cdot)$ can be arbitrary networks that are sub-differentiable with respect to their parameters.

\section{Experiments}
We evaluate SPENs on image denoising and semantic role labeling (SRL) tasks. Image denoising is an important benchmark for SPENs, since the task appears in many prior works employing end-to-end learning. SRL is useful for evaluating SPENs' suitability for challenging combinatorial problems, since the outputs are subject to rigid, non-local constraints.  For both, we provide controlled experiments that isolate the impact of various SPEN design decisions, such as the optimization method that is unrolled and the expressivity of the energy function.

 In these applications, we employ specific architectures based on our prior knowledge about the problem domain. This capability is crucial for introducing the necessary inductive bias to fbe able to fit SPENs on limited datasets. Overall, black-box prediction and learning methods for SPENs are useful because we can select architectures based on their suitability for the data, not whether they support model-specific algorithms. 




\subsection{Image Denoising}
\label{sec:denoising}


Let $\mathbf{x} \in [0,1]^{w \times h}$ be an observed grayscale image. We assume that it is a noisy realization of a latent clean image $\mathbf{y} \in [0,1]^{w \times h}$, which we estimate using MAP inference. Consider a Gaussian noise model with variance $\sigma^2$ and a prior $\mathbb{P}(\mathbf{y})$. The associated energy function is: 
\begin{equation}
\lVert \mathbf{y} - \mathbf{x} \rVert_2^2 - 2\sigma^{2}\log \mathbb{P}(\mathbf{y}). \label{eq:MAP}
\end{equation}
Here, the feature network is the identity. The first term is the local energy network and the second, which does not depend on $\mathbf{x}$, is the global energy network. 

There are three general families for the prior. First, it can be hard-coded. Second, it can be learned by approximate density estimation. Third, given a collection of $\{\mathbf{x},\mathbf{y}\}$ pairs, we can perform supervised learning, where the prior's parameters are discriminatively trained such that the output of a particular algorithm for minimizing Eq.~\eqref{eq:MAP} is high-quality. End-to-end learning has proven to be highly successful for the third approach~\citep{tappen2007learning,barbu2009training,schmidt2010generative,sun2011learning,domke2012generic,wang2016proximal}, and thus it is important to evaluate the methods of this paper on the task. 

\subsubsection{Image Priors}
Much of the existing work on end-to-end training for denoising considers some form of a field-of-experts (FOE) prior~\citep{roth2005fields}. We consider an $\ell_1$ version, which assigns high probability to images with sparse activations from $K$ learned filters:
\begin{equation}
\mathbb{P}(\mathbf{y}) \propto \exp\left(-\sum_k  \lVert(\mathbf{f}_k \ast \mathbf{y})  \rVert_1\right). \label{eq:foe}
\end{equation}
\citet{wang2016proximal} perform end-to-end learning for Eq.~\eqref{eq:foe}, by unrolling proximal gradient methods that analytically handle the non-differentiable $\ell_1$ term. 

This paper assumes we only have black-box interaction with the energy. In response, we alter Eq.~\eqref{eq:foe} such that it is twice differentiable, so that we can unroll generic first-order optimization methods. We approximate Eq.~\eqref{eq:foe} by leveraging a SoftPlus with temperature 25, replacing $|\cdot|$ by: 
\begin{equation}
\text{SoftAbs}(\mathbf{y}) = 0.5 \; \text{SoftPlus}(\mathbf{y}) + 0.5\;\text{SoftPlus}(-\mathbf{y}). \label{eq:softabs}
\end{equation}

The principal advantage of learning algorithms that are not hand-crafted to the problem structure is that they provide the opportunity to employ more expressive energies. In response, we also consider a deeper prior, given by:
\begin{equation}
\mathbb{P}(\mathbf{y}) \propto \exp\left(-\text{DNN}(\mathbf{y}) \right). \label{eq:dnn}
\end{equation}
Here, $\text{DNN}(\mathbf{y})$ is a general deep convolutional network that takes an image and returns a number. The architecture in our experiments consists of a $7 \times 7 \times 32$  convolution, a SoftPlus, another $7 \times 7 \times 32$ convolution, a SoftPlus, a $1 \times 1 \times 1$ convolution, and finally spatial average pooling. The method of~\citet{wang2016proximal} cannot handle this prior. 

\subsubsection{Experimental Setup}
We evaluate on the 7-Scenes dataset~\citep{newcombe2011kinectfusion}, where we seek to denoise depth measurements from a Kinect sensor. Our data processing and hyperparameters are designed to replicate the setup of~\citet{wang2016proximal}, who demonstrate state-of-the art results for energy-minimization-based denoising on the dataset. We train using random 96 $\times$ 128 crops from 200 images of the same scene and report PSNR (higher is better) for 5500 images from different scenes. We treat $\sigma^2$ as a trainable parameter and minimize the mean-squared-error of $\mathbf{y}$. 


\subsubsection{Results and Discussion}
\label{sec:denoise-results}
Example outputs are given in Figure~\ref{fig:denoise} and Table~\ref{table:denoise} compares PSNR. \textbf{BM3D} is a widely-used non-parametric method~\citep{dabov2007image}. FilterForest (\textbf{FF}) adaptively selects denoising filters for each location~\citep{ryan2014filter}. ProximalNet (\textbf{PN}) is the system of~\citet{wang2016proximal}. \textbf{FOE-20} is an attempt to replicate \textbf{PN} using end-to-end SPEN learning. We unroll 20 steps of gradient descent with momentum 0.75 and use the modification in Eq.~\eqref{eq:softabs}. Note it performs similarly to \textbf{PN}, which unrolls 5 iterations of sophisticated optimization. Note that we can obtain 37.0 PSNR using a feed-forward convnet with a similar architecture to our DeepPrior, but without spatial pooling.

The next set of results consider improved instances of the FOE model. First, \textbf{FOE-20+} is identical to \textbf{FOE-20}, except that it employs the average loss Eq.~\eqref{eq:avg-loss}, uses a momentum constant of 0.25, and treats the learning rates $\eta_t$ as trainable parameters. We find that this results in both better performance and faster convergence. Of course, we could achieve fast convergence by simply setting $T$ to be small. In response, we consider \textbf{FOE-3}. This only unrolls for $T = 3$ iterations and obtains superior performance. 

The final three results are with the DNN prior Eq.~\eqref{eq:dnn}. \textbf{DP-20} unrolls 20 steps of gradient descent with a momentum constant of 0.25. The gain in performance is substantial, especially considering that a PSNR of 30 can be obtained with elementary signal processing. Similar to \textbf{FOE-3} vs. \textbf{FOE-20+}, we experience a modest performance gain using \textbf{DP-3}, which only unrolls for 3 gradient steps but is otherwise identical. 

Finally, the \textbf{FOE-SSVM} and \textbf{DP-SSVM} configurations use SSVM training. We find that  \textbf{FOE-SSVM} performs competitively with the other FOE configurations. This is not surprising, since the FOE prior is convex. However, fitting the DeepPrior with an SSVM is inferior to using end-to-end learning.  The performance is very sensitive to the energy minimization hyperparameters. 

In these experiments, it is superior to only unroll for a few iterations for end-to-end learning. One possible reason is that a shallow unrolled architecture is easier to train. Truncated optimization with respect to $\mathbf{y}$ may also provide an interesting prior over outputs~\citep{duvenaud2016early}. It is also observed in~\citet{wang2014efficient} that better energy minimization for FOE models may not improve PSNR. Often unrolling for 20 iterations results in over-smoothed outputs.

We are unable achieve reasonable performance with an ICNN~\citep{amos2016input}, which restricts all of the parameters of the convolutions to be positive. Unfortunately, this hinders the ability of the filters in the prior to act as edge detectors or encourage local smoothness. Both of these are important for high-quality denoising. Note that the $\ell_1$ FOE is convex, even without the restrictive ICNN constraint. 




\begin{figure}[tb]
\centering
\begin{tabular}{cc}
  \includegraphics[width=0.4\columnwidth]{ims/final/FOE-BASIC/500-15_gt.jpg} &
  \includegraphics[width=0.4\columnwidth]{ims/final/FOE-BASIC/500-15_noisy.jpg} \\
{\small Ground Truth } & {\small Noisy Input}  \\
  \includegraphics[width=0.4\columnwidth]{ims/final/FOE-BASIC/500-15_pred.jpg} &
  \includegraphics[width=0.4\columnwidth]{ims/final/FOE-20-Better/500-15_pred.jpg} \\
{\small FOE-20 } & {\small FOE-20+}  \\
\includegraphics[width=0.4\columnwidth]{ims/final/DeepPrior-20/250-15_pred.jpg} & 
\includegraphics[width=0.4\columnwidth]{ims/final/DeepPrior-3/250-15_pred.jpg} \\
{\small DeepPrior-20 } & {\small DeepPrior-3}  \\
\end{tabular}
\caption{Example Denoising Outputs}
\label{fig:denoise}
\end{figure}



\begin{table}[tb!]
\begin{footnotesize}
\begin{center}
\begin{tabular}{|c|c|c|c| c |}
\hline
\textbf{BM3D} & \textbf{FF} & \textbf{PN} & \textbf{FOE-20} & \textbf{FOE-SSVM}\\
\hline
35.46 & 35.63 & 36.31 & 36.41 & 37.7\\
\hline
\hline
\textbf{FOE-20+} & \textbf{FOE-3} & \textbf{DP-20} & \textbf{DP-3}  & \textbf{DP-SSVM} \\
\hline
37.34 & 37.62 & 40.3 & \textbf{40.4}  & 38.7\\
\hline
\end{tabular}
\end{center}
\caption{Denoising Results (PSNR)}
\label{table:denoise}
\end{footnotesize}
\end{table}

\subsection{Semantic Role Labeling}
\input{experiment}



\section{Conclusion and Future Work}
SPENs are a flexible, expressive framework for structured prediction, but training them can be challenging. This paper provides a new end-to-end training method that enables high performance on considerably more complex tasks than those of~\citet{belanger2016structured}.  We unroll an approximate energy minimization algorithm into a differentiable computation graph that is trainable by gradient descent. The approach is user-friendly in practice because it returns not just an energy function but also a test-time prediction procedure that has been tailored for it. 

In the future, it may be useful to employ more sophisticated unrolled optimizers, perhaps where the optimizer's hyperparameters are a learned function of $\mathbf{x}$, and to perform iterative optimization in a learned feature space, rather than output space. Finally, we could model gradient-based prediction as a sequential decision making problem and train the energy using value-based reinforcement learning. 

\section*{Acknowledgments}
Many thanks to Justin Domke, Tim Vieiria, Luke Vilnis, and Shenlong Wang for helpful discussions. The first and third authors were supported in part by the Center for Intelligent Information Retrieval and in part by DARPA under agreement number FA8750-13-2-0020.  The second author was supported in part by DARPA under contract number FA8750-13-2-0005. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect those of the sponsor.

