\section{Introduction}
\label{sec:intro}
Deeper and larger neural networks have led to significant improvement in accuracy in various tasks, but they are also more computationally expensive and unfit for resource-constrained scenarios such as online serving. An interesting and viable solution to this problem is knowledge distillation (KD) \citep{Bucilua:2006:MC:1150402.1150464,NIPS2014_5484,44873}, which can be used to transfer the knowledge of a large model (the teacher) to a smaller model (the student). 
In the field of natural language processing (NLP), for example, KD has been successfully applied to compress massive pretrained language models such as BERT \citep{devlin-etal-2019-bert} and XLM-R \citep{conneau-etal-2020-unsupervised} into much smaller and faster models without significant loss in accuracy \citep{tang2019distilling,sanh2019distilbert,tsai-etal-2019-small,mukherjee-hassan-awadallah-2020-xtremedistil}.

A typical approach to KD is letting the student mimic the teacher model's output probability distributions on the training data by using the cross-entropy objective.
For structured prediction problems, however, the output space is exponentially large, making the cross-entropy objective intractable to compute and optimize directly.
Take sequence labeling for example. If the size of the label set is $L$, then there are $L^n$ possible label sequences for a sentence of $n$ words and it is infeasible to compute the cross-entropy by enumerating the label sequences. 
Previous approaches to structural KD either choose to perform KD on local decisions or substructures instead of on the full output structure, or resort to Top-K approximation of the objective \citep{kim-rush-2016-sequence,kuncoro-etal-2016-distilling,wang-etal-2020-structure}.

In this paper, we derive a factorized form of the structural KD objective based on the fact that almost all the structured prediction models factorize the scoring function of the output structure into scores of substructures. If the student's substructure space is polynomial in size and the teacher's marginal distributions over these substructures can be tractably estimated, then we can tractably compute and optimize the factorized form of the structural KD objective. As will be shown in the paper, many widely used structured prediction models satisfy the assumptions and hence are amenable to tractable KD. In particular, we show the feasibility and empirical effectiveness of structural KD with different combinations of teacher and student models, including those with incompatible factorization forms. 
We apply this technique to structural KD between sequence labeling and dependency parsing models under four different scenarios


\begin{enumerate} [leftmargin=*]
    \item The teacher and student share the same factorization form of the output structure scoring function.
    \item The student factorization produces more fine-grained substructures than the teacher factorization.
    \item The teacher factorization produces more fine-grained substructures than the student factorization.
    \item The factorization forms from the teacher and the student are incompatible.
\end{enumerate}

In all the cases, we empirically show that our structural KD approaches can improve the student models. In the few cases where previous KD approaches are applicable, we show our approaches outperform these previous approaches.
With unlabeled data, our approaches can further improve student models' performance. 
In a zero-shot cross-lingual transfer case, we show that with sufficient unlabeled data, student models trained by our approaches can even outperform the teacher models.

















\section{Background}

\subsection{Structured Prediction}
\label{sec:str_pred}
Structured prediction aims to predict a structured output such as a sequence, a tree or a graph. In this paper, we focus on structured prediction problems with a discrete output space, which include most of the structured prediction tasks in NLP (e.g., chunking, named entity recognition, and dependency parsing) and many structured prediction tasks in computer vision (e.g., image segmentation). We further assume that the scoring function of the output structure can be factorized into scores of a polynomial number of substructures. Consequently, we can calculate the conditional probability of the output structure ${\bm{y}}$ given an input ${\bm{x}}$ as follows:
\begin{align}
P({\bm{y}}|{\bm{x}}) & = \frac{\exp{(\text{Score}({\bm{y}},{\bm{x}})})}{\sum_{{\bm{y}}^{\prime} \in {\mathbb{Y}}({\bm{x}})} \exp{(\text{Score}({\bm{y}}^{\prime},{\bm{x}})})}\nonumber \\
            & = \frac{\prod_{{\bm{u}} \in {\bm{y}}}\exp{(\text{Score}({\bm{u}},{\bm{x}})})}{\mathcal{Z}({\bm{x}})} 
\label{eq:2.1}
\end{align}
where ${\mathbb{Y}}({\bm{x}})$ represents all possible output structures given the input ${\bm{x}}$, $\text{Score}({\bm{y}},{\bm{x}})$ is the scoring function that evaluates the quality of the output ${\bm{y}}$, $\mathcal{Z}({\bm{x}})$ is the partition function, 
and ${\bm{u}} \in {\bm{y}}$ denotes that ${\bm{u}}$ is a substructure of ${\bm{y}}$. We define the substructure space
${\mathbb{U}}({\bm{x}}) = \bigcup_{{\bm{y}}\in{\mathbb{Y}}({\bm{x}})}\{{\bm{u}}|{\bm{u}}\in{\bm{y}} \} $as the set of substructures of  all possible output structures given input ${\bm{x}}$.

Take sequence labeling for example. Given a sentence ${\bm{x}}$ , the output space ${\mathbb{Y}}({\bm{x}})$ contains all possible label sequences of ${\bm{x}}$. In linear-chain CRF, a popular model for sequence labeling, the scoring function $\text{Score}({\bm{y}},{\bm{x}})$ is computed by summing up all the transition scores
and emission scores 
where $i$ ranges over all the positions in sentence ${\bm{x}}$, and the substructure space ${\mathbb{U}}({\bm{x}})$ contains all possible position-specific labels $\{y_i\}$ and label pairs $\{(y_{i-1},y_i)\}$.
    
    






\subsection{Knowledge Distillation}


\label{sec:kd}
Knowledge distillation is a technique that trains a small student model by encouraging it to imitate the output probability distribution of a large teacher model. The typical KD objective function is the cross-entropy between the output distributions predicted by the teacher model and the student model:
\begin{align}
\mathcal{L}_{\text{KD}} 
 = -\sum_{{\bm{y}} \in {\mathbb{Y}}({\bm{x}})} P_t({\bm{y}}|{\bm{x}})\log P_s({\bm{y}}|{\bm{x}}) \label{eq:kd}
\end{align}
where $P_t$ and $P_s$ are the teacher's and the student's distributions respectively.

During training, the student jointly learns from the gold targets and the distributions predicted by the teacher by optimizing the following objective function:
\begin{align}
    \mathcal{L}_{\text{student}} = \lambda \mathcal{L}_\text{KD} + (1-\lambda) \mathcal{L}_\text{target} \nonumber
\end{align}
where $\lambda$ is an interpolation coefficient between the target loss $\mathcal{L}_\text{target}$ and the structural KD loss $\mathcal{L}_\text{KD}$. Following \citet{clark-etal-2019-bam,wang-etal-2020-structure}, one may apply teacher annealing in training by decreasing $\lambda$ linearly from 1 to 0. 
Because KD does not require gold labels, unlabeled data can also be used in the KD loss. 











\section{Structural Knowledge Distillation}
\label{sec:model}
When performing knowledge distillation on structured prediction, a major challenge is that the structured output space is exponential in size, leading to intractable computation of the KD objective in Eq. \ref{eq:kd}.
However, if the scoring function of the student model can be factorized into scores of substructures (Eq. \ref{eq:2.1}), then we can derive the following factorized form of the structural KD objective.
\begin{align}
&\mathcal{L}_{\text{KD}} 
= -\sum_{{\bm{y}} \in {\mathbb{Y}}({\bm{x}})} P_t({\bm{y}}|{\bm{x}}){\log} P_s({\bm{y}}|{\bm{x}}) \nonumber \\
& {=} {-}\smashoperator{\sum_{{\bm{y}} \in {\mathbb{Y}}({\bm{x}})}} P_t({\bm{y}}|{\bm{x}}) \sum_{{\bm{u}} \in {\bm{y}}} \text{Score}_s({\bm{u}},{\bm{x}}) {+} {\log} \mathcal{Z}_s({\bm{x}}) \nonumber\\
&{=} {-} \smashoperator{\sum_{{\bm{y}} \in {\mathbb{Y}}({\bm{x}})}} P_t({\bm{y}}|{\bm{x}}) \smashoperator{\sum_{{\bm{u}} \in {\mathbb{U}}_s({\bm{x}})}}  \bm{1}_{{\bm{u}} \in {\bm{y}}} \text{Score}_s({\bm{u}},{\bm{x}}) {+} {\log} \mathcal{Z}_s({\bm{x}}) \nonumber \\
& {=} {-}\smashoperator{\ssum_{\substack{{\bm{u}} \in {\mathbb{U}}_s({\bm{x}}), {\bm{y}} \in {\mathbb{Y}}({\bm{x}})}}} P_t({\bm{y}}|{\bm{x}})  \bm{1}_{{\bm{u}} \in {\bm{y}}} \text{Score}_s({\bm{u}},{\bm{x}})  {+} {\log} \mathcal{Z}_s({\bm{x}}) \nonumber \\
& {=} {-}\smashoperator{\sum_{{\bm{u}} \in {\mathbb{U}}_s({\bm{x}})}}P_t({\bm{u}}|{\bm{x}}) \text{Score}_s({\bm{u}},{\bm{x}}){+}{\log} \mathcal{Z}_s({\bm{x}})
\label{eq:kl}
\end{align}
where $\bm{1}_\mathrm{condition}$ is 1 if the condition is true and 0 otherwise. From Eq. \ref{eq:kl}, we see that if 
${\mathbb{U}}_s({\bm{x}})$ is polynomial in size and $P_t({\bm{u}}|{\bm{x}})$ can be tractably estimated, then the structural KD objective can be tractably computed and optimized.
In the rest of this section, we will show that this is indeed the case for some of the most widely used models in sequence labeling and dependency parsing, two representative structured prediction tasks in NLP. Based on the difference in score factorization between the teacher and student models, we divide our discussion into four scenarios.





\subsection{Teacher and Student Share the Same Factorization Form}


\paragraph{Case 1a: Linear-Chain CRF $\Rightarrow$ Linear-Chain CRF}
In this case, both the teacher and the student are linear-chain CRF models. 
An example application is to compress a state-of-the-art CRF model for named entity recognition (NER) that is based on large pretrained contextualized embeddings to a smaller CRF model with static embeddings that is more suitable for fast online serving.


For a CRF student model described in section \ref{sec:str_pred}, if we absorb the emission score $\text{S}_\text{e}(y_i,{\bm{x}})$ into the transition score $\text{S}_\text{t}((y_{i-1},y_i),{\bm{x}})$ at each position $i$, then the substructure space ${\mathbb{U}}_s({\bm{x}})$ contains every two adjacent labels $\{(y_{i-1},y_i)\}$ for $i{=}1,\ldots,n$, with $n$ being the sequence length, and the substructure score is defined as $\text{Score}((y_{i-1},y_i),{\bm{x}})= \text{S}_\text{t}((y_{i-1},y_i),{\bm{x}})+\text{S}_\text{e}(y_i,{\bm{x}})$. The substructure marginal $P_t((y_{i-1}, y_i)|{\bm{x}})$ of the teacher model can be computed by:
\begin{align}
   
     P_t((y_{i-1}, y_i)|{\bm{x}}) &\propto \alpha(y_{i-1}) \times \beta(y_i)\nonumber\\
     &\times \exp(\text{Score}((y_{i-1},y_i),{\bm{x}}))
     \label{eq:crf2crf}
\end{align}
where $\alpha(y_{i-1})$ and $\beta(y_i)$ are forward and backward scores that can be tractably calculated using the classical forward-backward algorithm. 




Comparing with the Posterior KD and Top-K KD of linear-chain CRFs proposed by \citet{wang-etal-2020-structure}, our approach calculates and optimizes the KD objective exactly, while their two KD approaches perform KD either heuristically or approximately. At the formulation level, our approach is based on the marginal distributions of two adjacent labels, while the Posterior KD is based on the marginal distributions of a single label.



\paragraph{Case 1b: Graph-based Dependency Parsing $\Rightarrow$ Dependency Parsing as Sequence Labeling}
In this case, we use the biaffine parser proposed by \citet{dozat-etal-2017-stanfords} as the teacher and the sequence labeling approach proposed by \citet{strzyz-etal-2019-viable} as the student for the dependency parsing task. 
The biaffine parser is one of the state-of-the-art models, while the sequence labeling parser provides a good speed-accuracy tradeoff. There is a big gap in accuracy between the two models and therefore KD can be used to improve the accuracy of the sequence labeling parser. 

Here we follow the head-selection formulation of dependency parsing without the tree constraint. The dependency parse tree ${\bm{y}}$ is represented by $\langle y_1, \ldots, y_n \rangle$, where $n$ is the sentence length and $y_i=(h_i,l_i)$ denotes the dependency head of the $i$-th token of the input sentence, with $h_i$ being the index of the head token and $l_i$ being the dependency label.
The biaffine parser predicts the dependency head for each token independently. It models separately the probability distribution of the head index $P_t(h_i|{\bm{x}})$ and the probability distribution of the label $P_t( l_i |{\bm{x}})$. 
The sequence labeling parser is a MaxEnt model that also predicts the head of each token independently. 
It computes $\text{Score}((h_i, l_i), {\bm{x}})$ for each token and applies a softmax function to produce the distribution $P_s((h_i,l_i)|{\bm{x}})$.

Therefore, these two models share the same factorization in which each substructure is a dependency arc specified by $y_i$. ${\mathbb{U}}_s({\bm{x}})$ thus contains all possible dependency arcs among tokens of the input sentence ${\bm{x}}$. The substructure marginal predicted by the teacher can be easily derived as:
\begin{equation}
    P_t((h_i,l_i)|{\bm{x}}) = P_t(h_i|{\bm{x}}) \times P_t(l_i|{\bm{x}}) 
    \label{eq:dp2sl}
\end{equation}
Note that in this case, the sequence labeling parser uses a MaxEnt decoder, which is locally normalized for each substructure. Therefore, the structural KD objective in Eq. \ref{eq:kl} can be reduced to the following form without the need for calculating the student partition function $\mathcal{Z}_s({\bm{x}})$.
\begin{align}
    \mathcal{L}_{\text{KD}} 
   
   
    &= -\sum_{{\bm{u}} \in {\mathbb{U}}_s({\bm{x}})}P_t({\bm{u}}|{\bm{x}}) \times \text{log} P_s({\bm{u}}|{\bm{x}}) 
\end{align}
In all the cases except \textbf{Case 1a} and \textbf{Case 3}, 
the student model is locally normalized and hence we can follow this form of objective.


\subsection{Student Factorization Produces More Fine-grained Substructures than Teacher Factorization}

\paragraph{Case 2a: Linear-Chain CRF $\Rightarrow$ MaxEnt}
\label{subsubsec:crf2soft}
In this case, we use a linear-chain CRF model as the teacher and a MaxEnt model as the student. Previous work \citep{yang-etal-2018-design,wang-etal-2020-structure} shows that a linear-chain CRF decoder often leads to better performance than a MaxEnt decoder for many sequence labeling tasks. Still, the simplicity and efficiency of the MaxEnt model is desirable. Therefore, it makes sense to perform KD from a linear-chain CRF to a MaxEnt model.
 
As mentioned in \textbf{Case 1a}, the substructures of a linear-chain CRF model are consecutive labels $\{(y_{i-1},y_i)\}$. In contrast, a MaxEnt model predicts the label probability distribution $P_s(y_i|{\bm{x}})$ of each token independently and 
hence the substructure space ${\mathbb{U}}_s({\bm{x}})$ consists of every individual label $\{y_i\}$.
To calculate the substructure marginal of the teacher $P_t(y_i|{\bm{x}})$, we can again utilize the forward-backward algorithm:
\begin{align}
    P_t(y_i|{\bm{x}}) \propto \alpha(y_i) \times \beta(y_i) 
\end{align}
where $\alpha(y_{i})$ and $\beta(y_i)$ are forward and backward scores.




\paragraph{Case 2b: Second-Order Dependency Parsing $\Rightarrow$ Dependency Parsing as Sequence Labeling}

The biaffine parser is a first-order dependency parser, which scores each dependency arc in a parse tree independently. A second-order dependency parser scores pairs of dependency arcs with a shared token. The substructures of second-order parsing are therefore all the dependency arc pairs with a shared token.
It has been found that second-order extensions of the biaffine parser often have higher parsing accuracy \citep{wang-etal-2019-second,zhang-etal-2020-efficient,wang-etal-2020-enhanced,wang-tu-2020-second}.
Therefore, we may take a second-order dependency parser as the teacher to improve a sequence labeling parser.

Here we consider the second-order dependency parser of \citet{wang-tu-2020-second}. It employs mean field variational inference to estimate the probabilities of arc existence $P_t(h_i|{\bm{x}})$ and uses a first-order biaffine model to estimate the probabilities of arc labels $P_t(l_i|{\bm{x}})$. 
Therefore, the substructure marginal can be calculated in the same way as Eq. \ref{eq:dp2sl}.








\subsection{Teacher Factorization Produces More Fine-grained Substructures than Student Factorization}
\label{subsec:soft2crf}
\paragraph{Case 3: MaxEnt $\Rightarrow$ Linear-Chain CRF}
Here we consider KD in the opposite direction of \textbf{Case 2a}. An example application is zero-shot cross-lingual NER. 
Previous work \citep{pires-etal-2019-multilingual,wu-dredze-2019-beto} has shown that multilingual BERT (M-BERT) has strong zero-shot cross-lingual transferability in NER tasks. Many such models employ a MaxEnt decoder. 
In scenarios requiring fast speed and low computation cost, however, we may want to distill knowledge from such models to a model with much cheaper static monolingual embeddings while compensating the performance loss with a linear-chain CRF decoder.

As described in \textbf{Case 1a}, the substructures of a linear-chain CRF model are consecutive labels $\{(y_{i-1},y_i)\}$. Because of the label independence and local normalization in the MaxEnt model, the substructure marginal of the MaxEnt teacher is calculated by:
\begin{align}
    P_t((y_{i-1}, y_i)|{\bm{x}}) = P_t(y_{i-1}|{\bm{x}})P_t(y_i|{\bm{x}}) 
    \label{max2crf}
\end{align}






\subsection{Factorization Forms From Teacher and Student are Incompatible}
\paragraph{Case 4: NER as Parsing $\Rightarrow$ MaxEnt}
Very recently, \citet{yu-etal-2020-named} propose to solve the NER task as graph-based dependency parsing and achieve state-of-the-art performance. They represent each named entity with a dependency arc from the first token to the last token of the named entity, and represent the entity type with the arc label. However, for the flat NER task (i.e., there is no overlapping between entity spans), the time complexity of this method is higher than commonly used sequence labeling NER methods. In this case, we take a parsing-based NER model as our teacher and a MaxEnt model with the BIOES label scheme as our student.

The two models adopt very different representations of NER output structures. The parsing-based teacher model represents an NER output of a sentence with a set of labeled dependency arcs and defines its score as the sum of arc scores. The MaxEnt model represents an NER output of a sentence with a sequence of BIOES labels and defines its score as the sum of token-wise label scores. Therefore, the factorization forms of these two models are incompatible.

Computing the substructure marginal of the teacher $P_t(y_i|{\bm{x}})$, where $y_i \in \{B_l, I_l, E_l, S_l, O | l \in L\}$ and $L$ is the set of entity types, is much more complicated than in the previous cases. Take $y_i = B_l$ for example. $P_t(y_i = B_l |{\bm{x}})$ represents the probability of the $i$-th word being the beginning of a multi-word entity of type `$l$’. In the parsing-based teacher model, this probability is proportional to the summation of exponentiated scores of all the output structures that contain a dependency arc of label `$l$’ with the $i$-th word as its head and with its length larger than 1. It is intractable to compute such marginal probabilities by enumerating all the output structures, but
we can tractably compute them using dynamic programming. See supplementary material for a detailed description of our dynamic programming method.















\section{Experiments}
\label{sec:exp}
We evaluate our approaches described in Section \ref{sec:model} on NER (\textbf {Case 1a, 2a, 3, 4}) and dependency parsing (\textbf{Case 1b, 2b}). 

\subsection{Settings}
\label{sec:set}
\paragraph{Datasets} We use CoNLL 2002/2003 datasets \citep{tjong-kim-sang-2002-introduction,tjong-kim-sang-de-meulder-2003-introduction} for {\bf Case 1a}, \textbf{2a} and \textbf{4}, and use WikiAnn datasets \citep{pan-etal-2017-cross} for  {\bf Case 1a}, \textbf{2a}, \textbf{3}, and \textbf{4}. The CoNLL datasets contain the corpora of four Indo-European languages. We use the same four languages from the WikiAnn datasets. For cross-lingual transfer in \textbf{Case 3}, we use the four Indo-European languages as the source for the teacher model and additionally select four languages from different language families as the target for the student models.\footnote{The four languages from the CoNLL datasets are Dutch, English, German and Spanish and the four target languages for \textbf{Case 3} are Basque, Hebrew, Persian and Tamil. We use ISO 639-1 language codes (\url{https://en.wikipedia.org/wiki/List_of_ISO_639-1_codes}) to represent each language.} 

We use the standard training/development/test split for the CoNLL datasets. For WikiAnn, we follow the sampling of \citet{wang-etal-2020-structure} with 12000 sentences for English and 5000 sentences for each of the other languages. We split the datasets by 3:1:1 for training/development/test. For \textbf{Case 1b} and \textbf{2b}, we use Penn Treebank (PTB) 3.0 and follow the same pre-processing pipeline as in \citet{ma-etal-2018-stack}. 
For unlabeled data, we sample sentences that belong to the same languages of the labeled data from the WikiAnn datasets for {\bf Case 1a}, \textbf{2a} and {\bf 4} and we sample sentences from the target languages of WikiAnn datasets for \textbf{Case 3}. We use the BLLIP corpus\footnote{Brown Laboratory for Linguistic Information Processing (BLLIP) 1987-89 WSJ Corpus Release 1. } as the unlabeled data for \textbf{Case 1b} and \textbf{2b}.

\paragraph{Models}

For the student models in all the cases, we use fastText \citep{bojanowski2017enriching} word embeddings and character embeddings as the word representation. For {\bf Case 1a}, \textbf{2a} and {\bf 4}, we concatenate the multilingual BERT, Flair \citep{akbik-etal-2018-contextual}, fastText embeddings and character embeddings \citep{santos2014learning} as the word representations for stronger monolingual teacher models \cite{wang-etal-2020-more}. For {\bf Case 3}, we use M-BERT embeddings for the teacher. Also for \textbf{Case 3}, we fine-tune the teacher model on the training set of the four Indo-European languages from the WikiAnn dataset and train student models on the four additional languages. For the teacher models in {\bf Case 1b} and {\bf 2b}, we simply use the same embeddings as the student because there is already huge performance gap between the teacher and student in these settings and hence we do not need strong embeddings for the teacher to demonstrate the utility of KD.

\paragraph{Baselines} 
We compare our Structural KD (\textit{Struct. KD}) with training without KD (\textit{w/o KD}) as well as existing KD approaches.
In \textbf{Case 1a}, the \textit{Pos. KD} baseline is the Posterior KD approach for linear-chain CRFs proposed by \citet{wang-etal-2020-structure}. They also propose \textit{Top-K KD} but have shown that it is inferior to \textit{Pos. KD}. For experiments using unlabeled data in all the cases, in addition to labeled data, we use the teacher's prediction on the unlabeled data as pseudo labeled data to train the student models. This can be seen as the \textit{Top-1 KD} method\footnote{We do not predict pseudo labels for the labeled data, because we find that the teacher models' predictions on the labeled training data have approximately 100\% accuracy in most of the cases. }. 
In Case \textbf{2a} and \textbf{3}, where we perform KD between CRF and MaxEnt models, we run a reference baseline that replaces the CRF teacher or student model with a MaxEnt model and performs token-level KD (\textit{Token KD}) of MaxEnt models that optimizes the cross entropy between the teacher and student label distributions at each position.








\begin{table}[t]
\small
\centering
\setlength\tabcolsep{1pt}
\begin{tabular}{l|cc|c|cc|c|cc}
\hlineB{4}

Case     & \multicolumn{2}{c|}{\textbf{1a}} & \textbf{1b} & \multicolumn{2}{c|}{\textbf{2a}} & \textbf{2b} & \multicolumn{2}{c}{\textbf{4}} \\

Labeled      & CoN            & Wiki            & PTB              & CoN            & Wiki            & PTB              & CoN           & Wiki           \\ \hline\hline
Teacher      & 89.15            & 88.52              & 95.96            & 89.15            & 88.52              & 96.04            & 88.57           & 88.38             \\
\hline
w/o KD        & 84.70            & 83.31              & 89.85            & 83.87            & 80.86              & 89.85            & 83.87           & 80.86             \\
Pos. KD & 85.27            & 83.73              & -                & -                & -                  & -                & -               & -                 \\
Struct. KD    & \textbf{85.35}   & \textbf{84.12}     & \textbf{91.83}   & \textbf{84.50}   & \textbf{82.23}     & \textbf{91.78}   & \textbf{84.28}  & \textbf{81.45}    \\ 
\hlineB{4}
\end{tabular}
\caption{Averaged F1 scores for NER and labeled attachment scores (LAS) for dependency parsing on labeled datasets. CoN: CoNLL datasets.}
\label{tab:labeled}
\end{table}

\begin{table}[t]
\small
\centering
\setlength\tabcolsep{1.5pt}
\begin{tabular}{l|c|c|c|c|c|c}
\hlineB{4}
Case       & \textbf{1a} & \textbf{1b} & \textbf{2a} & \textbf{2b} & \textbf{3} & \textbf{4} \\ 
Labeled+Unlabeled        & Wiki           & PTB           & Wiki           & PTB            & Wiki U          & Wiki          \\ 
\hline\hline
Teacher        & 88.52            & 95.96            & 88.52            & 96.04            & 56.01           & 88.38           \\
\hline
Top-1       & 84.19            & 90.03            & 82.40             & 90.03            & 41.11           & 82.10            \\
Pos. KD + Top-1   & 84.91            & -                & -                & -                & -               & -               \\
Struct. KD + Top-1 & \textbf{85.24}   & \textbf{91.98}   & \textbf{85.24}   & \textbf{91.94}   & \textbf{45.28}  & \textbf{82.44}  \\ \hlineB{4}
\end{tabular}
\caption{Average F1 score of NER and labeled attachment scores (LAS) for dependency parsing with both labeled and unlabeled data. Wiki U means that the training data of this case contains only the unlabeled data. }
\label{tab:unlabel}
\end{table}



\paragraph{Training}
For MaxEnt and linear-chain CRF models, we use the same hyper-parameters as in \citet{akbik-etal-2018-contextual}. For dependency parsing, we use the same hyper-parameters as in \citet{wang-tu-2020-second} for teacher models and \citet{strzyz-etal-2019-viable} for student models. For M-BERT fine-tuning in {\bf Case 3}, we mix the training data of the four source datasets and train the teacher model with the AdamW optimizer \citep{loshchilov2018decoupled} with a learning rate of $5{\times} 10^{-5}$ for 10 epochs. We tune the KD temperature in $\{1,2,3,4,5\}$ and the loss interpolation annealing rate in $\{0.5,1.0,1.5\}$. 
For all experiments, we train the models for 5 runs with a fixed random seed for each run.






\subsection{Results}
\label{sec:results}


\begin{table}[t]
\small
\centering
\setlength\tabcolsep{2pt}
\begin{tabular}{l||ccc|c}
\hlineB{4}
                 & \multicolumn{3}{c|}{\textbf{Case 2a}}                    & \textbf{Case 3}         \\
                 & CoNLL         & WikiAnn        & Wiki+U         & Wiki U         \\ \hline\hline
MaxEnt Teacher & 88.65         & 87.41          & 87.41          & 56.01          \\
CRF Teacher      & 89.15         & 88.52          & 88.52          & -            \\
\hline
Token. KD        & 84.25         & 82.09          & 83.07          & 38.42          \\
Struct. KD       & \textbf{84.50} & \textbf{82.23} & \textbf{83.34} & \textbf{45.28} \\ \hlineB{4}
\end{tabular}
\caption{Comparing with reference baselines on NER task. Wiki+U means the training data comprises labeled and unlabeled WikiAnn data and Wiki U means that the training data of this case contains only the unlabeled data.}
\label{tab:baseline_ref}
\end{table}



Table \ref{tab:labeled} shows the experimental results with labeled data only and \ref{tab:unlabel} shows the experimental results with additional 3000 unlabeled sentences.
The results show that our structural KD approaches outperform the baselines in all the cases. Table \ref{tab:baseline_ref} compares \textit{Struct. KD} with \textit{Token KD}, the reference baseline based on MaxEnt models.
For \textbf{Case 2a}, which involves a MaxEnt student, \textit{Struct. KD} with a CRF teacher achieves better results than \textit{Token KD} with a MaxEnt teacher. For \textbf{Case 3}, which involves a MaxEnt teacher, \textit{Struct. KD} with a CRF student achieves better results than \textit{Token KD} with a MaxEnt student. 
These results are to be expected because \textit{Struct. KD} makes it possible to apply exact knowledge distillation with a more capable teacher or student. 
In all the experiments, we run Almost Stochastic Dominance proposed by \citet{dror-etal-2019-deep} with a significance level of $0.05$ and find that the advantages of our structural KD approaches are significant. Please refer to Appendix for more detailed results.




\begin{table}[t]
\setlength\tabcolsep{5pt}
\centering
\small
\begin{tabular}{l||cccc|c}
\hlineB{4}
&	 de    	 &   en &	  es    	 & nl    &	  Avg.  \\
\hline					
\multicolumn{6}{c}{\textbf{Case 1a}}\\					
\hline					
w/o KD$^\dagger$         &      	82.16&	90.13&	88.06&	89.11&	 87.36\\
Top-WK KD$^\dagger$  &    	82.15&	90.52&	88.64&	89.24&	   87.64\\
Pos. KD$^\dagger$  &            	82.22&	90.68&	88.57&	89.41&	 87.72\\
Pos.+Top-WK$^\dagger$ &	 \textbf{82.31} &	90.53	&88.66&	89.58&	 87.77\\
Struct. KD& 	82.28&	 \textbf{90.86}& 	 \textbf{88.67}& 	 \textbf{90.07}& 	 \textbf{87.97} \\
\hline
\multicolumn{6}{c}{\textbf{Case 2a}}\\
\hline
w/o KD$^\dagger$ &	 \textbf{81.40}  &	90.08 &	87.72 &	88.99	 & 87.05 \\
Token KD$^\dagger$  &	81.30 &	90.02 &	88.24 &	88.87 &	 87.11 \\
Struct. KD  &	81.27 &	 \textbf{90.25}  &	 \textbf{88.64}  &	 \textbf{89.14}  &	 \textbf{87.32}\\
\hlineB{4}
\end{tabular}
\caption{A comparison of KD approaches for multilingual NER. $\dagger$: Results are from \citet{wang-etal-2020-structure}.}
\label{tab:ner}
\end{table}

\subsection{Multilingual NER Experiments}
There is a recent increase of interest in training multilingual NER models \citep{tsai-etal-2019-small,mukherjee-hassan-awadallah-2020-xtremedistil} because of the strong generalizability of M-BERT on multiple languages. Existing work explored knowledge distillation approaches to train fast and effective multilingual NER models with the help of monolingual teachers \citep{wang-etal-2020-structure}. To show the effectiveness of structural KD in the multilingual NER setting, we compare our approaches with those reported by \citet{wang-etal-2020-structure}.
Specifically, the monolingual teachers are always CRF models, and the multilingual student is either a CRF model (\textbf{Case 1a}) or a MaxEnt model (\textbf{Case 2a}). \citet{wang-etal-2020-structure} report results of the \textit{Top-WK KD} (a weighted version of \textit{Top-K KD}) and \textit{Pos. KD} approaches for \textbf{Case 1a} and the reference baseline \textit{Token KD} (with a MaxEnt teacher) for \textbf{Case 2a}. We follow their experimental settings when running our approach.


The experimental results in Table \ref{tab:ner} show the effectiveness of \textit{Struct. KD} in both cases. 
In \textbf{Case 1a}, our approach is stronger than both \textit{Top-WK KD} and \textit{Pos. KD} as well as the mixture of the two approaches on average.
In \textbf{Case 2a}, \textit{Struct. KD}
not only outperforms \textit{Token KD}, but also makes the MaxEnt student competitive with the CRF student without KD (87.32 vs. 87.36). 









\begin{filecontents}{zs_maxent2crf.dat}
unlabel	MaxEnt	CRF	MaxEnt->MaxEnt	Structural Teacher baseline
3	37.0515	41.1075	38.417	45.2785 56.01 37.0515
10	44.0215	48.457	45.8685	51.678 56.01 37.0515
30	53.794	57.2435	54.827	59.2375 56.01 37.0515
\end{filecontents}

\begin{filecontents}{graph2seq_parsing.dat}
unlabel	Baseline	Structural Teacher baseline
0	89.854	91.828 94.24 89.854
3	90.028	91.976 94.24 89.854
10	90.622	92.236 94.24 89.854
30	91.44	92.632 94.24 89.854
50	91.9925	92.996 94.24 89.854
100	92.61	93.282 94.24 89.854
\end{filecontents}

\begin{filecontents}{crf2crf.dat}
unlabel	crf	posterior	structural teacher baseline
0	83.31	83.7275	84.1225 88.5225 83.31
3	84.185	85.005	85.2075 88.5225 83.31
10	84.9	85.4525	85.6625 88.5225 83.31
30	86.24	86.5075	86.64 88.5225 83.31
\end{filecontents}

\begin{figure*}[!ht]
\centering
\begin{tikzpicture}
   
   
    \node at (-4.7,-0.65) {(a) Case 1a};
    \node at (0.7,-0.65) {(b) Case 1b};
    \node at (5.9,-0.65) {(c) Case 3};
   
    \begin{axis}[
        xshift=-7cm,
       
        name=ner,
       
        width=0.38\textwidth,
        height=0.25\textwidth,
       
       
       
        legend columns=2, 
        legend pos=north west,
        legend style={font=\tiny,yshift=-0.3cm},
        tick label style={font=\small},
       
       
        xtick={0,3,10,30},
        ylabel style={yshift=-0.5cm},
        ]
        \addplot[red,mark=square] table[x=unlabel,y=crf] {crf2crf.dat};
        \addplot[black,mark=*] table[x=unlabel,y=posterior] {crf2crf.dat};
        \addplot[blue,mark=square*] table[x=unlabel,y=structural] {crf2crf.dat};
        \addplot[black,dashed,line width=0.4mm] table[x=unlabel,y=teacher] {crf2crf.dat};
        \addplot[black,dotted,line width=0.4mm] table[x=unlabel,y=baseline] {crf2crf.dat};
        \legend{Top-1 KD, Pos. KD, Struct. KD}
    \end{axis}
    \begin{axis}[
        xshift=5.3cm,
       
        at={(ner.south west)},
        name=zeroshot,
       
        width=0.38\textwidth,
        height=0.25\textwidth,
       
       
       
        legend columns=1, 
        legend pos=south east,
        legend style={font=\tiny,yshift=0.3cm},
        tick label style={font=\small},
       
       
         xtick={0,10,30,50,100},
       
        ylabel style={yshift=-0.5cm},
        ]
        \addplot[red,mark=square] table[x=unlabel,y=Baseline] {graph2seq_parsing.dat};
        \addplot[blue,mark=square*] table[x=unlabel,y=Structural] {graph2seq_parsing.dat};
        \addplot[black,dashed,line width=0.4mm] table[x=unlabel,y=Teacher] {graph2seq_parsing.dat};
        \addplot[black,dotted,line width=0.4mm] table[x=unlabel,y=baseline] {graph2seq_parsing.dat};
        \legend{Top-1 KD, Struct. KD}
    \end{axis}
    \begin{axis}[
       
        at={(zeroshot.south west)},
        xshift=5.3cm,
       
        width=0.38\textwidth,
        height=0.25\textwidth,
       
       
       
        legend columns=1, 
        legend pos=south east,
        legend style={font=\tiny},
        tick label style={font=\small},
       
        xtick={0, 3,10,30},
        ylabel style={yshift=-0.5cm},
        ]
       
        \addplot[red,mark=square] table[x=unlabel,y=CRF] {zs_maxent2crf.dat};
        \addplot[black,mark=*] table[x=unlabel,y=MaxEnt->MaxEnt] {zs_maxent2crf.dat};
        \addplot[blue,mark=square*] table[x=unlabel,y=Structural] {zs_maxent2crf.dat};
        \addplot[black,dashed,line width=0.4mm] table[x=unlabel,y=Teacher] {zs_maxent2crf.dat};
       
        \legend{Top-1 KD, Token KD, Struct. KD}
       
    \end{axis}
\end{tikzpicture}
\caption{The accuracy of structural KD and the baselines on different amounts of unlabeled data in three cases. The x-axis represents the amount of unlabeled data in thousand and the y-axis represents the accuracy. The dashed lines are the accuracy of the teacher models. The dotted lines are the accuracy of the baseline models without any knowledge from the teachers.}
\label{fig:performance_curve}
\end{figure*}


\section{Analysis}
\subsection{Amount of Unlabeled Data}

We compare our approaches with the baselines with different amounts of unlabeled data for \textbf{Case 1a}, \textbf{1b} and \textbf{3}, which are cases that apply in-domain unlabeled data for NER and dependency parsing, and cross-lingual unlabeled data for NER. We experiment with more unlabeled data for \textbf{Case 1b} than for the other two cases because the labeled training data of PTB is more than $10$ times larger than the labeled NER training data in \textbf{Case 1a} and \textbf{3}. Results are shown in Figure \ref{fig:performance_curve}. 
The experimental results show that our approaches consistently outperform the baselines, though the performance gaps between them become smaller when the amount of unlabeled data increases. Comparing the performance of the students with the teachers, we can see that in \textbf{Case 1a} and \textbf{1b}, the gap between the teacher and the student remains large even with the largest amount of unlabeled data. This is unsurprising considering the difference in model capacity between the teacher and the student. In \textbf{Case 3}, however, we find that when using 30,000 unlabeled sentences, the CRF student models can even outperform the MaxEnt teacher model, which shows the effectiveness of CRF models on NER. 










\subsection{Temperature in Structural Knowledge Distillation}
A frequently used KD technique is dividing the logits of probability distributions of both the teacher and the student by a temperature in the KD objective \citep{44873}. Using a higher temperature produces softer probability distributions and often results in higher KD accuracy. In structural KD, there are two approaches to applying the temperature to the teacher model, either globally to the logit of $P_t({\bm{y}}|{\bm{x}})$ (i.e., $\text{Score}_t({\bm{y}},{\bm{x}})$) of the full structure ${\bm{y}}$, or locally to the logit of $P_t({\bm{u}}|{\bm{x}})$ of each student substructure ${\bm{u}}$. 
We empirically compare these two approaches in \textbf{Case 1a} with the same setting as in Section \ref{sec:set}. Table \ref{tab:temperature} shows that the local approach results in better accuracy for all the languages. Therefore, we use the local approach by default in all the experiments.


\begin{table}[!t]

\small
\centering
\begin{tabular}{l||cccc|c}
\hlineB{4}
 & de    & en    & es    & nl    & Avg.   \\
\hline\hline
CRF    & 75.37 & 91.21 & 86.55 & 85.67 & 84.70 \\
Global      & 75.67 & 91.11 & 86.72 & 85.92 & 84.85 \\
Local       & \textbf{76.61} & \textbf{91.41} & \textbf{87.20} & \textbf{86.19} & \textbf{85.35}\\
\hlineB{4}
\end{tabular}
\captionof{table}{Comparison of the global and local temperature application approaches on CoNLL NER.}
\label{tab:temperature}
\end{table}
\begin{table}[!t]
\small \centering
\begin{tabular}{l||cc}
\hlineB{4}
                  & CoNLL   & WikiAnn \\
\hline\hline
CRF                & \textbf{89.15}  & \textbf{88.52} \\
CRF-Mrg.      & 89.08 & 88.41 \\
NER-Par.           & 88.57   & 88.38 \\
NER-Par.-Mrg. & 87.40   & 86.82 \\
MaxEnt            & 88.65 & 87.41  \\
\hlineB{4}
\end{tabular}
\captionof{table}{Averaged F1 score of teachers and it's marginal distributions. -Mrg.: Marginal distribution, NER-Par.: NER as parsing \citep{yu-etal-2020-named}.}
\label{tab:teachers}
\end{table}

\subsection{Comparison of Teachers}
In \textbf{Case 2a} and \textbf{Case 4}, we use the same MaxEnt student model but different types of teacher models. Our structural KD approaches in both cases compute the marginal distribution $P_t(y_i|{\bm{x}})$ of the teacher at each position $i$ following the substructures of the MaxEnt student, which is then used to train the student substructure scores. We can evaluate the quality of the marginal distributions by taking their modes as label predictions and evaluating their accuracy.
In Table \ref{tab:teachers}, we compare the accuracy of the CRF teacher and its marginal distributions from \textbf{Case 2a}, the NER-as-parsing teacher and its marginal distributions from \textbf{Case 4}, and the MaxEnt teacher which is the KD baseline in \textbf{Case 2a}.
First, we observe that for both CRF and NER-as-parsing, predicting labels from the marginal distributions leads to lower accuracy. This is to be expected because such predictions do not take into account correlations between adjacent labels. While predictions from marginal distributions of the CRF teacher still outperform MaxEnt, those of the NER-as-parsing teacher clearly underperform MaxEnt. This provides an explanation as to why \textit{Struct. KD} in \textbf{Case 4} has equal or even lower accuracy than the \textit{Token KD} baseline in \textbf{Case 2a} in Table \ref{tab:baseline_ref}.











\section{Related Work}

\subsection{Structured Prediction}

In this paper, we use sequence labeling and dependency parsing as two example structured prediction tasks.
In sequence labeling, a lot of work applied the linear-chain CRF and achieved state-of-the-art performance in various tasks \citep{ma-hovy-2016-end,akbik-etal-2018-contextual,liu-etal-2019-gcdt,yu-etal-2020-named,wei-etal-2020-dont,wang2020automated,wang2021improving}. Meanwhile, a lot of other work used the MaxEnt layer instead of the CRF for sequence labeling \citep{devlin-etal-2019-bert,conneau-etal-2020-unsupervised,wang-etal-2020-ain} because MaxEnt makes it easier to fine-tune pretrained contextual embeddings in training. Another advantage of MaxEnt in comparison with CRF is its speed. \citet{yang-etal-2018-design} showed that models equipped with the CRF are about two times slower than models with the MaxEnt layer in sequence labeling.
In dependency parsing, recent work shows that second-order CRF parsers achieve significantly higher accuracy than first-order parsers \citep{wang-etal-2019-second,zhang-etal-2020-efficient}. However, the inference speed of second-order parsers is much slower. \citet{zhang-etal-2020-efficient} showed that second-order parsing is four times slower than the simple head-selection first-order approach \citep{dozat2016deep}. 
Such speed-accuracy tradeoff as seen in sequence labeling and dependency parsing also occurs in many other structured prediction tasks. This makes KD an interesting and very useful technique that can be used to circumvent this tradeoff to some extent.



\subsection{Knowledge Distillation in Structured Prediction}
KD has been applied in many structured prediction tasks in the fields of NLP, speech recognition and computer vision, with applications such as neural machine translation \citep{kim-rush-2016-sequence,tan2018multilingual},  sequence labeling \citep{tu-gimpel-2019-benchmarking,wang-etal-2020-structure}, 
connectionist temporal classification \citep{Huang2018}, 
image semantic segmentation \citep{liu2019structured} and so on.
In KD for structured prediction tasks, how to handle the exponential number of structured outputs is a main challenge. To address this difficult problem, recent work resorts to approximation of the KD objective. \citet{kim-rush-2016-sequence} proposed sequence-level distillation through predicting K-best sequences of the teacher in neural machine translation. \citet{kuncoro-etal-2016-distilling} proposed to use multiple greedy parsers as teachers and generate the probability distribution at each position through voting. Very recently, \citet{wang-etal-2020-structure} proposed structure-level knowledge distillation for linear-chain CRF models in multilingual sequence labeling. During the distillation process, teacher models predict the Top-K label sequences as the global structure information or the posterior label distribution at each position as the local structural information, which is then used to train the student. Besides approximate approaches, an alternative way is using models that make local decisions and performing KD on these local decisions. \citet{anderson-gomez-rodriguez-2020-distilling} formulated dependency parsing as a head-selection problem and distilled the distribution of the head node at each position. \citet{tsai-etal-2019-small} proposed MiniBERT through distilling the output distributions of M-BERT models of the MaxEnt classifier. Besides the output distribution, \citet{mukherjee-hassan-awadallah-2020-xtremedistil} further distilled the hidden representations of teachers.







\section{Conclusion}
In this paper, we propose structural knowledge distillation, which transfers knowledge between structured prediction models. We derive a factorized form of the structural KD objective and make it tractable to compute and optimize for many typical choices of teacher and student models. We apply our approach to four KD scenarios with six cases for sequence labeling and dependency parsing. Empirical results show that our approach outperforms baselines without KD as well as previous KD approaches. With sufficient unlabeled data, our approach can even boost the students to outperform the teachers in zero-shot cross-lingual transfer. 

\subsubsection*{Acknowledgments}
This work was supported by the National Natural Science Foundation of China (61976139) and by Alibaba Group through Alibaba Innovative Research Program. 



