arXiv:1711.10331v1 [cs.LG] 25 Nov 2017

Complex Structure Leads to Overfitting:
A Structure Regularization Decoding Method for Natural
Language Processing
Xu Suna , Weiwei Suna,b , Shuming Maa , Xuancheng Rena , Yi Zhanga , Wenjie Lic ,
Houfeng Wanga
a MOE

Key Laboratory of Computational Linguistics, Peking University
of Computer Science and Technology, Peking University
c Department of Computing, The Hong Kong Polytechnic University
b Institute

Abstract
Recent systems on structured prediction focus on increasing the level of structural dependencies within the model. However, our study suggests that complex structures
entail high overfitting risks. To control the structure-based overfitting, we propose to
conduct structure regularization decoding (SR decoding). The decoding of the complex structure model is regularized by the additionally trained simple structure model.
We theoretically analyze the quantitative relations between the structural complexity
and the overfitting risk. The analysis shows that complex structure models are prone to
the structure-based overfitting. Empirical evaluations show that the proposed method
improves the performance of the complex structure models by reducing the structurebased overfitting. On the sequence labeling tasks, the proposed method substantially
improves the performance of the complex neural network models. The maximum F1
error rate reduction is 36.4% for the third-order model. The proposed method also
works for the parsing task. The maximum UAS improvement is 5.5% for the tri-sibling
model. The results are competitive with or better than the state-of-the-art results. 1
Keywords: Structural complexity regularization, Structured prediction, Overfitting
risk reduction, Linear structure, Tree structure, Deep Learning

1. Introduction
Structured prediction models are often used to solve the structure dependent problems in a wide range of application domains including natural language processing,
bioinformatics, speech recognition, and computer vision. To solve the structure dependent problems, many structured prediction methods have been developed. Among them

Email addresses: xusun@pku.edu.cn (Xu Sun), ws@pku.edu.cn (Weiwei Sun),
shumingma@pku.edu.cn (Shuming Ma), renxc@pku.edu.cn (Xuancheng Ren),
zhangyi16@pku.edu.cn (Yi Zhang), cswjli@comp.polyu.edu.hk (Wenjie Li), wanghf@pku.edu.cn
(Houfeng Wang)
1 This work is a substantial extension of a conference paper presented at NIPS 2014 [1].

Preprint submitted to Artificial Intelligence

November 29, 2017

the representative models are conditional random fields (CRFs), deep neural networks,
and structured perceptron models. In order to capture the structural information more
accurately, some recent studies emphasize on intensifying structural dependencies in
structured prediction by applying long range dependencies among tags, developing
long distance features or global features, and so on.
From the probabilistic perspective, complex structural dependencies may lead to
better modeling power. However, this is not the case for most of the structured prediction problems. It has been noticed that some recent work that tries to intensify the
structural dependencies does not really benefit as expected, especially for neural network models. For example, in sequence labeling tasks, a natural way to increase the
complexity of the structural dependencies is to make the model predict two or more
consecutive tags for a position. The new label for a word now becomes a concatenation of several consecutive tags. To correctly predict the new label, the model can be
forced to learn the complex structural dependencies involved in the transition of the
new label. Nonetheless, the experiments contradict the hypothesis. With the increasing
number of the tags to be predicted for a position, the performance of the model deteriorates. In the majority of the tasks we tested, the performance decreases substantially.
We show the results in Section 4.1.1.
We argue that over-emphasis on intensive structural dependencies could be misleading. Our study suggests that complex structures are actually harmful to model
accuracy. Indeed, while it is obvious that intensive structural dependencies can effectively incorporate the structural information, it is less obvious that intensive structural
dependencies have a drawback of increasing the generalization risk. Increasing the
generalization risk means that the trained models tend to overfit the training data. The
more complex the structures are, the more instable the training is. Thus, the training is
more likely to be affected by the noise in the data, which leads to overfitting. Formally,
our theoretical analysis reveals why and with what degree the structure complexity
lowers the generalization ability of the trained models. Since this type of overfitting
is caused by the structural complexity, it can hardly be solved by ordinary regularization methods, e.g., the weight regularization methods, such as L2 and L1 regularization
schemes, which are used only for controlling the weight complexity.
To deal with this problem, we propose a simple structural complexity regularization
solution based on structure regularization decoding. The proposed method trains both
the complex structure model and the simple structure model. In decoding, the simpler
structure model is used to regularize the complex structure model, deriving a model
with better generalization power.
We show both theoretically and empirically that the proposed method can reduce
the overfitting risk. In theory, the structural complexity has the effect of reducing the
empirical risk, but increasing the overfitting risk. By regularizing the complex structure
with the simple structure, a balance between the empirical risk and the overfitting risk
can be achieved. We apply the proposed method to multiple sequence labeling tasks,
and a parsing task. The formers involve linear-chain models, i.e., LSTM [2] models,
and the latter involves hierarchical models, i.e., structured perceptron [3] models. Experiments demonstrate that the proposed method can easily surpass the performance of
both the simple structure model and the complex structure model. Moreover, the results
are competitive with the state-of-the-art results or better than the state-of-the-arts.
2

To the best of our knowledge, this is the first theoretical effort on quantifying the
relation between the structural complexity and the generalization risk in structured prediction. This is also the first proposal on structural complexity regularization via regularizing the decoding of the complex structure model by the simple structure model.
The contributions of this work are two-fold:
• On the methodology side, we propose a general purpose structural complexity
regularization framework for structured prediction. We show both theoretically
and empirically that the proposed method can effectively reduce the overfitting
risk in structured prediction. The theory reveals the quantitative relation between
the structural complexity and the generalization risk. The theory shows that
the structure-based overfitting risk increases with the structural complexity. By
regularizing the structural complexity, the balance between the empirical risk
and the overfitting risk can be maintained. The proposed method regularizes the
decoding of the complex structure model by the simple structure model. Hence,
the structured-based overfitting can be alleviated.
• On the application side, we derive structure regularization decoding algorithms
for several important natural language processing tasks, including the sequence
labeling tasks, such as chunking and name entity recognition, and the parsing
task, i.e., joint empty category detection and dependency parsing. Experiments
demonstrate that our structure regularization decoding method can effectively
reduce the overfitting risk of the complex structure models. The performance
of the proposed method easily surpasses the performance of both the simple
structure model and the complex structure model. The results are competitive
with the state-of-the-arts or even better.
The structure of the paper is organized as the following. We first introduce the
proposed method in Section 2 (including its implementation on linear-chain models and
hierarchical models). Then, we give theoretical analysis of the problem in Section 3.
The experimental results are presented in Section 4. Finally, we summarize the related
work in Section 5, and draw our conclusions in Section 6.
2. Structure Regularization Decoding
Some recent work focuses on intensifying the structural dependencies. However,
the improvements fail to meet the expectations, and the results are even worse sometimes. Our theoretical study shows that the reason is that although the complex structure results in the low empirical risk, it causes the high structure-based overfitting risk.
The theoretical analysis is presented in Section 3.
According to the theoretical analysis, the key to reduce the overall overfitting risk is
to use a complexity-balanced structure. However, such kind of structure is hard to define in practice. Instead, we propose to conduct joint decoding of the complex structure
model and the simple structure model, which we call Structure Regularization Decoding (SR Decoding). In SR decoding, the simple structure model acts as a regularizer
that balances the structural complexity.

3

As the structures vary with the tasks, the implementation of structure regularization
decoding also varies. In the following, we first introduce the general framework, and
then show two specific algorithms for different structures. One is for the linear-chain
structure models on the sequence labeling tasks, and the other is for the hierarchical
structure models on the joint empty category detection and dependency parsing task.
2.1. General Structure Regularization Decoding
Before describing the method formally, we first define the input and the output of
the model. Suppose we are given a training example (xx, y ), where x ∈ Xn is the input
and y ∈ Yn is the output. Here, X stands for the feature space, and Y stands for the
tag space, which includes the possible substructures regarding to each input position.
In preprocessing, the raw text input is transformed into a sequence of corresponding
features, and the output structure is transformed into a sequence of input position related tags. The reason for such definition is that the output structure varies with tasks.
For simplicity and flexibility, we do not directly model the output structure. Instead,
we regard the output structure as a structural combination of the output tags of each
position, which is the input position related substructure.
Different modeling of the structured output, i.e., different output tag space, will lead
to different complexity of the model. For instance, in the sequence labeling tasks, Y
could be the space of unigram tags, and then y is a sequence of y i . Y could also be the
space of bigram tags. The bigram tag means the output regrading to the input feature
x i involves two consecutive tags, e.g. the tag at position i, and the tag at position i + 1.
Then, y is the combination of the bigram tags y i . This also requires proper handling
of the tags at overlapping positions. It is obvious that the structural complexity of the
bigram tag space is higher than that of the unigram tag space.
Point-wise classification is donated by g(xx, k, y), where g is the model that assigns
the scores to each possible output tag y at the position k. For simplicity, we denote
g(xx, k) = argmaxy∈Y g(xx, k, y), so that g : Xn × R 7→ Y. Given a point-wise cost
function c : Y × Y 7→ R, which scores the predicted output based on the gold standard
output, the model can be learned as:
g = argmin
g

|xx|
X X

c(g(xx, i), y i )

(xx,yy)∈S i=1

For the same structured prediction task, suppose we could learn two models g1 and
g2 of different structural complexity, where g1 : Xn × R 7→ Y is the simple structure
model, and g2 : Xn × R 7→ Z is the complex structure model. Given the corresponding point-wise cost function c1 and c2 , the proposed method first learns the models
separately:
g1 = argmin
g

g2 = argmin
g

|xx|
X X

c1 (g(xx, i), y i )

(xx,yy)∈S 1 i=1
|xx|
X X
(xx,zz)∈S 2 i=1

4

c2 (g(xx, i), z i )

Suppose there is a mapping T from Z to {y|y ∈ Y}, that is, the complex structure
can be decomposed into simple structures. In testing, prediction is done by structure
regularization decoding of the two models, based on the complex structure model:
z = argmax
z ∈Z|xx|

|xx|
X

(g2 (xx, i, z i ) +

X

g1 (xx, i, y))

(1)

y∈T (zzi )

i=1

In the decoding of the complex structure model, the simple structure model acts as a
regularizer that balances the structural complexity.
We try to keep the description of the method as straight-forward as possible without
loss of generality. However, we do make some assumptions. For example, the general
algorithm combines the scores of the complex model and the simple model at each
position by addition. However, the combination method should be adjusted to the task
and the simple structure model used. For example, if the model g is a probabilistic
model, multiplication should be used instead of the addition. Besides, the number of
the models is not limited in theory, as long as (1) is changed accordingly. Moreover,
if the joint training of the models is affordable, the models are not necessarily to be
trained independently. These examples are intended to demonstrate the flexibility of
the structure regularization decoding algorithms. The detailed implementation should
be considered with respect to the task and the model.
In what follows, we show how structure regularization decoding is implemented
on two typical structures in natural language processing, i.e. the sequence labeling
tasks, which involve linear-chain structures, and the dependency parsing task, which
involves hierarchical structures. We focus on the differences and the considerations
when deriving structure regularization decoding algorithms. It needs to be reminded
that the implementation of the structure regularization decoding method can be adapted
to more kinds of structures. The implementation is not limited to the structures or the
settings that we use.
2.2. SR Decoding for Sequence Labeling Tasks
We first describe the model, and then explain how the framework in Section 2.1 can
be implemented for the sequence labeling tasks.
Sequence labeling tasks involve linear-chain structures. For a sequence labeling
task, a reasonable model is to find a label sequence with the maximum probability conditioned on the sequence of observations, i.e. words. Given a sequence of observations
x = x1 , x2 , · · · , xT , and a sequence of labels, y = y1 , y2 , ..., yT , where T denotes the
sentence length, we want to estimate the joint probability of the labels conditioned on
the observations as follows:
p(yy|xx) = p(y1 , y2 , · · · , yT |x1 , x2 , · · · , xT )
If we model the preceding joint probability directly, the number of parameters that
need to be estimated is extremely large, which makes the problem intractable. Most
existing studies make Markov assumption to reduce the parameters. We also make
an order-n Markov assumption. Different from the typical existing work, we decompose the original joint probability into a few localized order-n joint probabilities. The
5

multiplication of these localized order-n joint probabilities is used to approximate the
original joint probability. Furthermore, we decompose each localized order-n joint
probability to the stacked probabilities from order-1 to order-n, such that we can efficiently combine the multi-order information.
By using different orders of the Markov assumptions, we can get different structural
complexity of the model. For example, if we use the Markov assumption of order-1,
we obtain the simplest model in terms of the structural complexity:
p(yy|xx) = p(y1 , y2 , · · · , yT |x1 , x2 , · · · , xT )
, p(y1 |xx)p(y2 |xx) · · · p(yT |xx)
=

T
Y

(p (yt |xx))

t=1

If we use the Markov assumption with order-2, we estimate the original joint probability as follows:
p(yy|xx) = p(y1 , y2 , · · · , yT |x1 , x2 , · · · , xT )
, p(y1 , y2 |xx)p(y2 , y3 |xx) · · · p(yT −1 , yT |xx)
=

T −1
Y

(p (yt , yt+1 |xx))

t=1

This formula models the bigram tags with respect to the input. The search space expands, and entails more complex structural dependencies. To learn such models, we
need to estimate the conditional probabilities. In order to make the problem tractable,
a feature mapping is often introduced to extract features from conditions, to avoid a
large parameter space.
In this paper, we use BLSTM to estimate the conditional probabilities, which has
the advantage that feature engineering is reduced to the minimum. Moreover, the conditional probabilities of higher order models can be converted to the joint probabilities
of the output labels conditioned on the input labels. When using neural networks,
learning of n-order models can be conducted by just extending the tag set from unigram labels to n-gram labels. In training, this only affects the computational cost of the
output layer, which is linear to the size of the tag set. The models can be trained very
efficiently with a affordable training cost. The strategy is showed in Figure 1.
To decode with structure regularization, we need to connect the models of different
complexity. Fortunately, the complex model can be decomposed into a simple model
and another complex model. Notice that:
p(yt , yt+1 |xx) = p(yt+1 |xx, yt )p(yt |xx)

6

𝑦

𝑦
SR decoding

decoding

BIO

B

BI

BLSTM

BLSTM

𝑥

𝑥

BIO

Figure 1: Illustration of SR-decoding on sequence labeling task (Left: third-order BLSTM. Right: thirdorder BLSTM with SR-decoding). BLSTM decodes with third-order tags directly, while SR-decoding jointly
decodes with first-order, second-order, and third-order tags.

The original joint probability can be rewritten as:
p(yy|xx) = p(y1 , y2 , · · · , yT |x1 , x2 , · · · , xT )
, (y1 , y2 |xx)p(y2 , y3 |xx) · · · p(yT −1 , yT |xx)
= p(y2 |xx, y1 )p(y1 |xx)p(y3 |xx, y2 )p(y2 |xx) · · · p(yT |xx, yT −1 )p(yT −1 |xx)
=

T −1
Y

(p (yt+1 |yt , x ) p (yt |xx))

t=1

In the preceding equation, the complex model is p(yt+1 |yt , x ). It predicts the next label based on the current label and the input. p(yt |xx) is the simplest model. In practice, we estimate p(yt+1 |yt , x ) also by BLSTMs, and the computation is the same with
p(yt , yt+1 |xx). The derivation can also be generalized to an order-n case, which consists
of the models predicting the length-1 to length-n label sequence for a position. Moreover, the equation explicitly shows a reasonable way of SR decoding, and how the
simple structure model can be used to regularize the complex structure model. Figure
1 illustrates the method.
However, considering the sequence of length T and an order-n model, decoding is
not scalable, as the computational complexity of the algorithm is O(nT ). To accelerate
SR decoding, we prune the tags of a position in the complex structure model by the topmost possible tags of the simplest structure model. For example, if the output tags of
the complex structure are bigram labels, i.e. Z = Y×Y, the available tags for a position
in the complex structure model are the combination of the most probable unigram tags
of the position, and the position before. In addition, the tag set of the complex model is
also pruned so that it only contains the tags appearing in the training set. The detailed
algorithm with pruning, which we name scalable multi-order decoding, is given in
Appendix B.
2.3. SR Decoding for Dependency Parsing
We first give a brief introduction to the task. Then, we introduce the model, and
finally we show the structure regularization decoding algorithm for this task.
7

root

But it ∅1 is n’t clear how long GM would be willing ∅2 to fight ... ∅3
Figure 2: An example of the dependency parsing analysis augmented with empty elements from PTB. The
dependency structure is according to Stanford Dependency. “∅” denotes an empty element. “∅1 ” indicates
an expletive construction; “∅2 ” indicates that the subject for fight, i.e. GM, is located in another place; “∅3 ”
indicates a wh-movement.

The task in question is the parsing task, specifically, joint empty category detection
and dependency parsing, which involves hierarchical structures. In many versions of
Transformational Generative Grammars, e.g., the Government and Binding [4] theory,
empty category is the key concept bridging S-Structure and D-Structure, due to its
possible contribution to trace movements. Following the linguistic insights, a traditional
dependency analysis can be augmented with empty elements, viz. covert elements [5].
Figure 2 shows an example of the dependency parsing analysis augmented with empty
elements. The new representations leverages hierarchical tree structures to encode not
only surface but also deep syntactic information. The goal of empty category detection
is to find out all empty elements, and the goal of dependency parsing thus includes
predicting not only the dependencies among normal words but also the dependencies
between a normal word and an empty element.
In this paper, we are concerned with how to employ the structural complexity regularization framework to improve the performance of empty category augmented dependency analysis, which is a complex structured prediction problem compared to the
regular dependency analysis.
A traditional dependency graph G = (V, A) is a directed graph, such that for sentence x = w1 , . . . , wn the following holds:
1. V = {0, 1, 2, . . . , n},
2. A ⊆ V × V.
The vertex set V consists of n + 1 nodes, each of which is represented by a single integer. Especially, 0 represents a virtual root node w0 , while all others corresponded to
words in x. The arc set A represents the unlabeled dependency relations of the particular analysis G. Specifically, an arc (i, j) ∈ A represents a dependency from head wi
to dependent w j . A dependency graph G is thus a set of unlabeled dependency relations between the root and the words of x. To represent an empty category augmented
dependency tree, we extend the vertex set and define a directed graph as usual.
To define a parsing model, we denote the index set of all possible dependencies
as I = {(i, j)|i ∈ {0, · · · , n}, j ∈ {1, · · · , n}, i , j}. A dependency parse can then be
represented as a vector
y = {y(i, j) : (i, j) ∈ I}
where y(i, j) = 1 if there is an arc (i, j) in the graph, and 0 otherwise. For a sentence x,

8

we define dependency parsing as a search for the highest-scoring analysis of x:
y∗ (x) = arg max Score(x, y)
y∈Y(x)

(2)

Here, Y(x) is the set of all trees compatible with x and Score(x, y) evaluates the event
that tree y is the analysis of sentence s. In brief, given a sentence x, we compute its
parse y∗ (x) by searching for the highest-scored dependency parse in the set of compatible trees Y(x). The scores are assigned by Score. In this paper, we evaluate structured
perceptron and define Score(x, y) as w> Φ(x, y) ,where Φ(x, y) is a feature-vector mapping and w is the corresponding parameter vector.
In general, performing a direct maximization over the set Y(x) is infeasible. The
common solution used in many parsing approaches is to introduce a part-wise factorization:
X
φ(x, p)
Φ(x, y) =
p∈Part(y)

Above, we have assumed that the dependency parse y can be factored into a set of
parts p, each of which represents a small substructure of y. For example, y might be
factored into the set of its component dependencies. A number of dynamic programming (DP) algorithms have been designed for first- [6], second- [7, 8], third- [9] and
fourth-order [10] factorization.
Parsing for joint empty category detection and dependency parsing can be defined
in a similar way. We use another index set I0 = {(i, j)|i, j ∈ {1, · · · , n + (n + 1)2 }},
where i > n indicates an empty node. Then a dependency parse with empty nodes can
be represented as a vector similar to y:
z = {z(i, j) : (i, j) ∈ I0 }.
Let Z(x) denote the set of all possible z for sentence x. We then define joint empty
category detection and dependency parsing as a search for the highest-scoring analysis
of x:
X
w> φ(x, z)
(3)
z∗ (x) = arg max
z∈Z(x)

p∈Part(z)

When the output of the factorization function, namely Part(x), is defined as the
collection of all sibling or tri-sibling dependencies, decoding for the above two optimization problems, namely (2) and (3), can be resolved in low-degree polynomial time
with respective to the number of words contained in x [7, 9, 11]. In particular, the
decoding algorithms proposed by Zhang et al. [11] are extensions of the algorithms
introduced respectively by McDonald and Pereira [7] and Koo and Collins [9].
To perform structure regularization decoding, we need to combine the two models.
In this problem, as the models are linear and do not involve probability, they can be
easily combined together. Assume that f : Y → R and g : Z → R assign scores to
parse trees without and with empty elements, respectively. In particular, the training
data for estimating f are sub-structures of the training data for estimating g. Therefore,
the training data for f can be viewed as the mini-samples of the training data for g.

9

A reasonable model to integrate f and g is to find the optimal parse by solving the
following optimization problem:
max.
s.t.

λ f (y) + (1 − λ)g(z)
y ∈ Y, z ∈ Z
y(i, j) = z(i, j), ∀(i, j) ∈ I

(4)

where λ is a weight for score combination.
In this paper, we employ dual decomposition to resolve the optimization problem
(4). We sketch the solution as follows.
The Lagrangian of (4) is
X
L(y, z; u) = f (y) + g(z) +
u(i, j)(y(i, j) − z(i, j))
(i, j)∈I

where u is the Lagrangian multiplier. Then the dual is
L(u)

=

max L(y, z; u)
X
X
= max( f (y) +
u(i, j)y(i, j)) + max(g(z) −
u(i, j)z(i, j))
y∈Y,z∈Z
y∈Y

z∈Z

(i, j)∈I

(i, j)∈I

We instead try to find the solution for
min L(u).
u

By using a subgradient method to calculate maxu L(u), we have another SR decoding
algorithm. Notice that, there is no need to train the simple model and the complex
model separately.
Algorithm 1 SR Decoding Algorithm for Dependency Parsing
u(0) ← 0
for k = 0 → K do
P
y ← arg maxy∈Y ( f (y) + i, j u(i, j)y(i, j))
P
z ← arg maxz∈Z (g(z) − i, j u(i, j)z(i, j))
if ∀(i, j) ∈ I, y(i, j) = z(i, j) then
return z
else
u(k+1) ← u(k) − α(k) (y − z)
end if
end for
return z
3. Theoretical Analysis: Structure Complexity vs. Overfitting Risk
We first describe the settings for the theoretical analysis, and give the necessary
definitions (Section 3.1). We then introduce the proposed method with the proper annotations for clearance of the analysis (Section 3.2). Finally, we give the theoretical
10

results on analyzing the generalization risk regarding to the structure complexity based
on stability (Section 3.3). The general idea behind the theoretical analysis is that the
overfitting risk increases with the complexity of the structure, because more complex
structures are less stable in training. If some examples are taken out of the training set,
the impact on the complex structure models is much severer compared to the simple
structure models. The detailed relations among the factors are shown by the analysis.
3.1. Problem Settings of Theoretical Analysis
In this section, we give the preliminary definitions necessary for the analysis, including the learning algorithm, the data, and the cost functions, and especially the definition of structural complexity. We also describe the properties and the assumptions
we make to facilitate the theoretical analysis.
A graph of observations (even with arbitrary structures) can be indexed and be denoted by an indexed sequence of observations O = {o1 , . . . , on }. We use the term sample to denote O = {o1 , . . . , on }. For example, in natural language processing, a sample
may correspond to a sentence of n words with dependencies of linear chain structures
(e.g., in part-of-speech tagging) or tree structures (e.g., in syntactic parsing). In signal
processing, a sample may correspond to a sequence of n signals with dependencies of
arbitrary structures. For simplicity in analysis, we assume all samples have n observations (thus n tags). In the analysis, we define structural complexity as the scope of the
structural dependency. For example, a dependency scope of two tags is considered less
complex than a dependency scope of three tags. In particular, the dependency scope
of n tags is considered the full dependency scope which is of the highest structural
complexity.
A sample is converted to an indexed sequence of feature vectors x = {xx(1) , . . . , x (n) },
where x (k) ∈ X is of the dimension d and corresponds to the local features extracted
from the position/index k. We can use an n × d matrix to represent x ∈ Xn . In other
words, we use X to denote the input space on a position, so that x is sampled from Xn .
Let Yn ⊂ Rn be structured output space, so that the structured output y are sampled
from Yn . Let Z = (Xn , Yn ) be a unified denotation of structured input and output
space. Let z = (xx, y ), which is sampled from Z, be a unified denotation of a (xx, y ) pair
in the training data.
Suppose a training set is
S = {zz1 = (xx1 , y 1 ), . . . , z m = (xxm , y m )},
with size m, and the samples are drawn i.i.d. from a distribution D which is unknown. A
learning algorithm is a function G : Zm 7→ F with the function space F ⊂ {Xn 7→ Yn },
i.e., G maps a training set S to a function GS : Xn 7→ Yn . We suppose G is symmetric
with respect to S , so that G is independent on the order of S .
Structural dependencies among tags are the major difference between structured
prediction and non-structured classification. For the latter case, a local classification
of g based on a position k can be expressed as g(xx(k−a) , . . . , x (k+a) ), where the term
{xx(k−a) , . . . , x (k+a) } represents a local window. However, for structured prediction, a
local classification on a position depends on the whole input x = {xx(1) , . . . , x (n) } rather
than a local window, due to the nature of structural dependencies among tags (e.g.,
11

graphical models like CRFs). Thus, in structured prediction a local classification on k
should be denoted as g(xx(1) , . . . , x (n) , k). To simplify the notation, we define
g(xx, k) , g(xx(1) , . . . , x (n) , k)
Given a training set S of size m, we define S \i as a modified training set, which
removes the i’th training sample:
S \i = {zz1 , . . . , z i−1 , z i+1 , . . . , z m },
and we define S i as another modified training set, which replaces the i’th training sample with a new sample ẑ i drawn from D:
S i = {zz1 , . . . , zi−1 , ẑi , zi+1 , . . . , zm },
We define the point-wise cost function c : Y × Y 7→ R+ as c[GS (xx, k), y (k) ], which
measures the cost on a position k by comparing GS (xx, k) and the gold-standard tag y (k) .
We introduce the point-wise loss as
`(GS , z , k) , c[GS (xx, k), y (k) ]
Then, we define the sample-wise cost function C : Yn × Yn 7→ R+ , which is the
cost function with respect to a whole sample. We introduce the sample-wise loss as
L(GS , z ) , C[GS (xx), y ] =

n
X

`(GS , z , k) =

k=1

n
X

c[GS (xx, k), y (k) ]

k=1

Given G and a training set S , what we are most interested in is the generalization
risk in structured prediction (i.e., the expected average loss) [12, 13]:
R(GS ) = Ez

h L(GS , z ) i
n

Unless specifically indicated in the context, the probabilities and expectations over
random variables, including Ez (.), ES (.), Pz (.), and PS (.), are based on the unknown
distribution D.
Since the distribution D is unknown, we have to estimate R(GS ) from S by using
the empirical risk:
m

Re (GS ) =

m

n

1 X
1 XX
L(GS , z i ) =
`(GS , z i , k)
mn i=1
mn i=1 k=1

In what follows, sometimes we will use the simplified notations, R and Re , to denote
R(GS ) and Re (GS ).
To state our theoretical results, we must describe several quantities and assumptions which are important in structured prediction. We follow some notations and assumptions on non-structured classification [14, 15]. We assume a simple real-valued
structured prediction scheme such that the class predicted on position k of x is the sign
12

of GS (xx, k) ∈ D. In practice, many popular structured prediction models have a realvalued cost function. Also, we assume the point-wise cost function cτ is convex and
τ-smooth such that ∀y1 , y2 ∈ D, ∀y∗ ∈ Y
|cτ (y1 , y∗ ) − cτ (y2 , y∗ )| ≤ τ|y1 − y2 |

(5)

While many structured learning models have convex objective function (e.g., CRFs),
some other models have non-convex objective function (e.g., deep neural networks).
It is well-known that the theoretical analysis on the non-convex cases are quite difficult. Our theoretical analysis is focused on the convex situations and hopefully it can
provide some insight for the more difficult non-convex cases. In fact, we will conduct
experiments on neural network models with non-convex objective functions, such as
LSTM. Experimental results demonstrate that the proposed structural complexity regularization method also works in the non-convex situations, in spite of the difficulty of
the theoretical analysis.
Then, τ-smooth versions of the loss and the cost function can be derived according
to their prior definitions:
Lτ (GS , z ) = Cτ [GS (xx), y ] =

n
X

`τ (GS , z , k) =

k=1

n
X

cτ [GS (xx, k), y (k) ]

k=1

Also, we use a value ρ to quantify the bound of |GS (xx, k)−GS \i (xx, k)| while changing
a single sample (with size n0 ≤ n) in the training set with respect to the structured input
x . This ρ-admissible assumption can be formulated as ∀k,
|GS (xx, k) − GS \i (xx, k)| ≤ ρ||GS − GS \i ||2 · ||xx||2

(6)

where ρ ∈ R+ is a value related to the design of algorithm G.
3.2. Structural Complexity Regularization
Base on the problem settings, we give definitions for the common weight regularization and the proposed structural complexity regularization. In the definition, the
proposed structural complexity regularization decomposes the dependency scope of the
training samples into smaller localized dependency scopes. The smaller localized dependency scopes form mini-samples for the learning algorithms. It is assumed that the
smaller localized dependency scopes are not overlapped. Hence, the analysis is for a
simplified version of structural complexity regularization. We are aware that in implementation, the constraint can be hard to guarantee. From an empirical side, structural
complexity works well without this constraint.
Most existing regularization techniques are proposed to regularize model weights/parameters,
e.g., a representative regularizer is the Gaussian regularizer or so called L2 regularizer.
We call such regularization techniques as weight regularization.
Definition 1 (Weight regularization). Let Nλ : F 7→ R+ be a weight regularization
function on F with regularization strength λ, the structured classification based objective function with general weight regularization is as follows:
Rλ (GS ) , Re (GS ) + Nλ (GS )
13

(7)

While weight regularization normalizes model weights, the proposed structural
complexity regularization method normalizes the structural complexity of the training samples. Our analysis is based on the different dependency scope (i.e., the scope of
the structural dependency), such that, for example, a tag depending on two tags in context is considered to have less structural complexity than a tag depending on four tags
in context. The structural complexity regularization is defined to make the dependency
scope smaller. To simplify the analysis, we suppose a baseline case that a sample z
has full dependency scope n, such that all tags in z have dependencies. Then, we introduce a factor α such that a sample z has localized dependency scope n/α. In this
case, α represents the reduction magnitude of the dependency scope. To simplify the
analysis without losing generality, we assume the localized dependency scopes do not
overlap with each other. Since the dependency scope is localized and non-overlapping,
we can split the original sample of the dependency scope n into α mini-samples of
the dependency scope of n/α. What we want to show is that, the learning with small
and non-overlapping dependency scope has less overfitting risk than the learning with
large dependency scope. Real-world tasks may have an overlapping dependency scope.
Hence, our theoretical analysis is for a simplified “essential” problem distilled from the
real-world tasks.
In what follows, we also directly call the dependency scope of a sample as the
structure complexity of the sample. Then, a simplified version of structural complexity regularization, specifically for our theoretical analysis, can be formally defined as
follows:
Definition 2 (Simplified structural complexity regularization for analysis). Let Nα :
F 7→ F be a structural complexity regularization function on F with regularization
strength α with 1 ≤ α ≤ n, the structured classification based objective function with
structural complexity regularization is as follows2 :
m

Rα (GS ) , Re [G Nα (S ) ] =

α

m

α

n/α

1 XXX
1 XX
L[GS 0 , z (i, j) ] =
`[GS 0 , z (i, j) , k] (8)
mn i=1 j=1
mn i=1 j=1 k=1

where Nα (zzi ) splits z i into α mini-samples {zz(i,1) , . . . , z (i,α) }, so that the mini-samples
have a dependency scope of n0 = n/α. Thus, we get
S 0 = {zz(1,1) , z(1,2) , . . . , z(1,α) , . . . , z(m,1) , z(m,2) , . . . , z(m,α) }
|
{z
}
|
{z
}
α

(9)

α

with mα mini-samples of expected structure complexity n/α. We can denote S 0 more
compactly as S 0 = {zz01 , z 02 , . . . , z 0mα } and Rα (GS ) can be simplified as
mα n/α

mα

Rα (GS ) ,

1 XX
1 X
L(GS 0 , z 0i ) =
`[GS 0 , z 0i , k]
mn i=1
mn i=1 k=1

(10)

2 The notation N is overloaded here. For clarity throughout, N with subscript λ refers to weight regularization function, and N with subscript α refers to structural complexity regularization function.

14

Note that, when the structural complexity regularization strength α = 1, we have
S 0 = S and Rα = Re .
Now, we have given a formal definition of structural complexity regularization,
by comparing it with the traditional weight regularization. Below, we show that the
structural complexity regularization can improve the stability of learned models, and
can finally reduce the overfitting risk of the learned models.
3.3. Stability of Structured Prediction
Because the generalization of a learning algorithm is positively correlated with the
stability of the learning algorithm [14], to analyze the generalization of the proposed
method, we instead examine the stability of the structured prediction. Here, stability
describes the extent to which the resulting learning function changes, when a sample
in the training set is removed. We prove that by decomposing the dependency scopes,
i.e, by regularizing the structural complexity, the stability of the learning algorithm can
be improved.
We first give the formal definitions of the stability with respect to the learning
algorithm, i.e., function stability.
Definition 3 (Function stability). A real-valued structured classification algorithm G
has “function value based stability” (“function stability” for short) ∆ if the following
holds: ∀zz = (xx, y ) ∈ Z, ∀S ∈ Zm , ∀i ∈ {1, . . . , m}, ∀k ∈ {1, . . . , n},
|GS (xx, k) − GS \i (xx, k)| ≤ ∆
The stability with respect to the cost function can be similarly defined.
Definition 4 (Loss stability). A structured classification algorithm G has “uniform
loss-based stability” (“loss stability” for short) ∆l if the following holds: ∀zz ∈ Z, ∀S ∈
Zm , ∀i ∈ {1, . . . , m}, ∀k ∈ {1, . . . , n},
|`(GS , z , k) − `(GS \i , z , k)| ≤ ∆l
G has “sample-wise uniform loss-based stability” (“sample loss stability” for short)
∆ s with respect to the loss function L if the following holds: ∀zz ∈ Z, ∀S ∈ Zm , ∀i ∈
{1, . . . , m},
|L(GS , z) − L(GS \i , z)| ≤ ∆ s
It is clear that the upper bounds of loss stability and function stability are linearly
correlated under the problem settings.
Lemma 5 (Loss stability vs. function stability). If a real-valued structured classification algorithm G has function stability ∆ with respect to loss function `τ , then G has
loss stability
∆l ≤ τ∆
and sample loss stability
∆ s ≤ nτ∆.

15

The proof is provided in Appendix A.
Here, we show that lower structural complexity has lower bound of stability, and
is more stable for the learning algorithm. The proposed method improves stability by
regularizing the structural complexity of training samples.
Theorem 6 (Stability vs. structural complexity regularization). With a training set
S of size m, let the learning algorithm G have the minimizer f based on commonly
used L2 weight regularization:
f = argmin Rα,λ (g) = argmin
g∈F

g∈F

mα

 1 X
λ
Lτ (g, z 0j ) + ||g||22
mn j=1
2

(11)

where α denotes the structural complexity regularization strength with 1 ≤ α ≤ n.
Also, we have
 1 X

λ
0
\i0
f \i = argmin Rα,λ
(g) = argmin
Lτ (g, z 0j ) + ||g||22
(12)
mn j,i0
2
g∈F
g∈F
where j , i0 means j ∈ {1, . . . , i0 − 1, i0 + 1, . . . , mα}.3 Assume Lτ is convex and
differentiable, and f (xx, k) is ρ-admissible. Let a local feature value is bounded by v
such that x (k,q) ≤ v for q ∈ {1, . . . , d}.4 Let ∆ denote the function stability of f compared
0
with f \i for ∀zz ∈ Z with |zz| = n. Then, ∆ is bounded by
∆≤

dτρ2 v2 n2
,
mλα2

(13)

and the corresponding loss stability is bounded by
∆l ≤

dτ2 ρ2 v2 n2
,
mλα2

and the corresponding sample loss stability is bounded by
∆s ≤

dτ2 ρ2 v2 n3
.
mλα2

The proof is given in Appendix A.
We can see that increasing the size of training set m results in linear improvement
of ∆, and increasing the strength of structural complexity regularization α results in
quadratic improvement of ∆.
0
The function stability ∆ is based on comparing f and f \i , i.e., the stability is based
on removing a mini-sample. Moreover, we can extend the analysis to the function
stability based on comparing f and f \i , i.e., the stability is based on removing a fullsize sample.
3 Note that, in some cases the notation i is ambiguous. For example, f \i can either denote the removing
of a sample in S or denote the removing of a mini-sample in S 0 . Thus, when the case is ambiguous, we use
different index symbols for S and S 0 , with i for indexing S and i0 for indexing S 0 , respectively.
4 Recall that d is the dimension of local feature vectors defined in Section 3.1.

16

Corollary 7 (Stability by removing a full sample). With a training set S of size m,
let the learning algorithm G have the minimizer f as defined before. Also, we have
f \i = argmin R\i
α,λ (g) = argmin
g∈F

g∈F

 1 X

λ
Lτ (g, z 0j ) + ||g||22
mn j<i
2

(14)

where j < i means j ∈ {1, . . . , (i − 1)α, iα + 1, . . . , mα}, i.e., all the mini-samples derived
from the sample z i are removed. Assume Lτ is convex and differentiable, and f (xx, k)
is ρ-admissible. Let a local feature value be bounded by v such that x (k,q) ≤ v for
q ∈ {1, . . . , d}. Let ∆¯ denote the function stability of f comparing with f \i for ∀zz ∈ Z
with |zz| = n. Then, ∆¯ is bounded by
dτρ2 v2 n2
= α sup(∆),
∆¯ ≤
mλα

(15)
0

where ∆ is the function stability of f comparing with f \i , and sup(∆) =
described in Eq. (13). Similarly, we have

dτρ2 v2 n2
,
mλα2

as

dτ2 ρ2 v2 n2
∆¯ l ≤
= α sup(∆l ),
mλα
and

dτ2 ρ2 v2 n3
= α sup(∆ s ).
∆¯ s ≤
mλα

The proof is presented in Appendix A.
In the case that a full sample is removed, increasing the strength of structural complexity regularization α results in linear improvement of ∆.
3.4. Reduction of Generalization Risk
In this section, we formally describe the relation between the generalization and
the stability, and summarize the relationship between the proposed method and the
generalization. Finally, we draw our conclusions from the theoretical analysis.
Now, we analyze the relationship between the generalization and the stability.
Theorem 8 (Generalization vs. stability). Let G be a real-valued structured classification algorithm with a point-wise loss function `τ such that ∀k, 0 ≤ `τ (GS , z , k) ≤ γ.
Let f , ∆, and ∆¯ be defined before. Let R( f ) be the generalization risk of f based on
the expected sample z ∈ Z with size n, as defined before. Let Re ( f ) be the empirical
risk of f based on S , as defined like before. Then, for any δ ∈ (0, 1), with probability
at least 1 − δ over the random draw of the training set S , the generalization risk R( f )
is bounded by
r

 ln δ−1
¯
¯
(16)
R( f ) ≤ Re ( f ) + 2τ∆ + (4m − 2)τ∆ + γ
2m

17

The proof is in Appendix A.
The upper bound of the generalization risk contains the loss stability, which is
rewritten as the function stability. We can see that better stability leads to lower bound
of the generalization risk.
By substituting the function stability with the formula we get from the structural
complexity regularization, we get the relation between the generalization and the structural complexity regularization.
Theorem 9 (Generalization vs. structural complexity regularization). Let the structured prediction objective function of G be penalized by structural complexity regularization with factor α ∈ [1, n] and L2 weight regularization with factor λ. The penalized
function has a minimizer f :
f = argmin Rα,λ (g) = argmin
g∈F

g∈F

mα

 1 X
λ
Lτ (g, z 0j ) + ||g||22
mn j=1
2

(17)

Assume the point-wise loss `τ is convex and differentiable, and is bounded by `τ ( f, z , k) ≤
γ. Assume f (xx, k) is ρ-admissible. Let a local feature value be bounded by v such that
x (k,q) ≤ v for q ∈ {1, . . . , d}. Then, for any δ ∈ (0, 1), with probability at least 1 − δ over
the random draw of the training set S , the generalization risk R( f ) is bounded by
r
 ln δ−1
2dτ2 ρ2 v2 n2  (4m − 2)dτ2 ρ2 v2 n2
R( f ) ≤ Re ( f ) +
+
+γ
(18)
mλα
mλα
2m
The proof is in Appendix A.

 q −1
2 2 2 2
2 2 2 2
ρ v n
ρ v n
ln δ
We call the term 2dτmλα
+ (4m−2)dτ
+γ
mλα
2m in (18) as the “overfit-bound”.
Reducing the overfit-bound is crucial for reducing the generalization risk bound. Most
importantly, we can see from the overfit-bound that the structural complexity regularization factor α always stays together with the weight regularization factor λ, working
together to reduce the overfit-bound. This indicates that the structural complexity regularization is as important as the weight regularization for reducing the generalization
risk for structured prediction.
Moreover, since τ, ρ, and v are typically small compared with other variables, especially m, (18) can be approximated as follows by ignoring the small terms:
√
 dn2 ln δ−1 
R( f ) ≤ Re ( f ) + O
(19)
√
λα m
First, (19) suggests that structure complexity n can increase the overfit-bound on a magnitude of O(n2 ), and applying weight regularization can reduce the overfit-bound by
O(λ). Importantly, applying structural complexity regularization further (over weight
regularization) can additionally reduce the overfit-bound by a magnitude of O(α). When
α = 1, which means “no structural complexity regularization”, we have the worst
overfit-bound. Also, (19) suggests that increasing the size of training set can reduce
the overfit-bound on a square root level.
Theorem 9 also indicates that too simple structures may overkill the overfit-bound
but with a dominating empirical risk, while too complex structures may overkill the
18

empirical risk but with a dominating overfit-bound. Thus, to achieve the best prediction
accuracy, a balanced complexity of structures should be used for training the model.
By regularizing the complex structure with the simple structure, a balance between
the empirical risk and the overfitting risk can be achieved. In the proposed method,
the model of the complex structure and the simple structure are both used in decoding.
In essence, the decoding is based on the complex model, for the purpose of keeping
the empirical risk down. The simple model is used to regularize the structure of the
output, which means the structural complexity of the complex model is compromised.
Therefore, the overfitting risk is reduced.
To summarize, the proposed method decomposes the dependency scopes, that is,
regularizes the structural complexity. It leads to better stability of the model, which
means the generalization risk is lower. Under the problem settings, increasing the
regularization strength α can bring linear reduction of the overfit-bound. However,
too simple structure may cause a dominating empirical risk. To achieve a balanced
structural complexity, we could regularize the complex structure model with the simple
structure model. The complex structure model has low empirical risk, while the simple
structure model has low structural risk. The proposed method takes the advantages
of both the simple structure model and the complex structure model. As a result, the
overall overfitting risk can be reduced.
4. Experiments
We conduct experiments on natural language processing tasks. We are concerned
with two types of structures: linear-chain structures, e.g. word sequences, and hierarchical structures, e.g. phrase-structure trees and dependency trees. The natural language processing tasks concerning linear-chain structures include (1) text chunking,
(2) English named entity recognition, and (3) Dutch named entity recognition. We also
conduct experiments on a natural language processing task that involves hierarchical
structures, i.e. (4) dependency parsing with empty category detection.
4.1. Experiments on Sequence Labeling Tasks
Text Chunking (Chunking): The chunking data is from the CoNLL-2000 shared
task [16]. The training set consists of 8,936 sentences, and the test set consists of 2,012
sentences. Since there is no development data provided, we randomly sampled 5%
of the training data as development set for tuning hyper-parameters. The evaluation
metric is F1-score.
English Named Entity Recognition (English-NER): The English NER data is
from the CoNLL-2003 shared task [17]. There are four types of entities to be recognized: PERSON, LOCATION, ORGANIZATION, and MISC. This data has 14,987
sentences for training, 3,466 sentences for development, and 3,684 sentences for testing. The evaluation metric is F1-score.
Dutch Named Entity Recognition (Dutch-NER): We use the D-NER dataset [18]
from the shared task of CoNLL-2002. The dataset contains four types of named entities: PERSON, LOCATION, ORGANIZATION, and MISC. It has 15,806 sentences
for training, 2,895 sentences for development, and 5,195 sentences for testing. The
evaluation metric is F1-score.
19

Test score
BLSTM order1
BLSTM order2
BLSTM order2 + SR
BLSTM order3
BLSTM order3 + SR

Chunking
93.97
93.24
94.81 (+1.57)
92.50
95.23 (+2.73)

English-NER
87.65
87.59
89.72 (+2.13)
87.16
90.59 (+3.43)

Dutch-NER
76.04
76.33
80.51 (+4.18)
76.57
81.62 (+5.05)

Table 1: Comparing SR decoding with the baseline BLSTM models. As we can see, when the order of the
model increases, the performance of BLSTM deteriorates most of the time. With SR decoding, the structural
complexity is controlled, so that the performance of the higher order model is substantially improved. It is
also interesting that the improvement is larger when the order is higher.
Chunking
96
91.0

F−score (%)

95

82.0

90.0

80.0

89.0

94

78.0
88.0

93

76.0

87.0

BLSTM
BLSTM+SR

92
1

2
Order

(a) Chunking

3

86.0

74.0

order-1
BLSTM

order-2

order-3

BLSTM-STAD

(b) English-NER

order-1
BLSTM

order-2

order-3

BLSTM-STAD

(c) Dutch-NER

Figure 3: Comparing SR decoding with baseline LSTM models. SR decoding can substantially improve the
performance of the complex structure model. Moreover, it is clear that SR decoding improves the order-3
models more than the order-2 models.

Since LSTM [19] is a popular implementation of recurrent neural networks, we
highlight experiment results on LSTM. In this work, we use the bi-directional LSTM
(BLSTM) as the implementation of LSTM, considering it has better accuracy in practice. For BLSTM, we set the dimension of input layer to 200 and the dimension of
hidden layer to 300 for all the tasks.
The experiments on BLSTM are based on the Adam learning method [20]. Since
we find the default hyper parameters work satisfactorily on those tasks, following
Kingma and Ba [20] we use the default hyper parameters as follows: β1 = 0.9, β2 =
0.99,  = 1 × 10−5 .
For the tasks with BLSTM, we find there is almost no difference by adding L2 regularization or not. Hence, we do not add L2 regularization for BLSTM. All weight
matrices, except for bias vectors and word embeddings, are diagonal matrices and randomly initialized by normal distribution.
We implement our code with the python package Tensorflow.
4.1.1. Results
First, we apply the proposed scalable multi-order decoding method on BLSTM
(BLSTM-SR). Table 1 compares the scores of BLSTM-SR and BLSTM on standard
test data. As we can see, when the order of the model is increased, the baseline model
worsens. The exception is the result of the Dutch-NER task. When the order of the

20

Model
Kudoh and Matsumoto [22]
Kudo and Matsumoto [23]
Sha and Pereira [24]
McDonald et al. [25]
Sun et al. [26]
Collobert et al. [27]
Sun [1]
Huang et al. [28]
This paper

F1
93.48
93.91
94.30
94.29
94.34
94.32
94.52
94.46
95.23

Table 2: Text Chunking: comparing with previous work. Shen and Sarkar [21] also achieve 95.23%, but
their result is based on noun phrase chunking. However, our result is based on all phrase chunking, which
has more tags to predict and is more difficult.

model is increased, the model is slightly improved. It demonstrates that, in practice,
although complex structure models have lower empirical risks, the structural risks are
more dominant.
The proposed method easily surpasses the baseline. For Chunking, the F1 error
rate reduction is 23.2% and 36.4% for the second-order model and the third-order
model, respectively. For English-NER, the proposed method reduces the F1 error rate
by 17.2% and 26.7% for the second-order model and the third-order model, respectively. For Dutch-NER, the F1 error rate reduction of 17.7% and 21.6% is achieved
respectively for the second-order model and the third-order model. It is clear that the
improvement is significant. We suppose the reason is that the proposed method can
combine both low-order and high order information. It helps to reduce the overfitting
risk. Thus, the F1 score is improved.
Moreover, the reduction is larger when the order is higher, i.e., the improvement
of order-3 models is better than that of order-2 models. This confirms the theoretical
results that higher structural complexity leads to higher structural risks. This also suggests the proposed method can alleviate the structural risks and keep the empirical risks
low. The phenomenon is better illustrated in Figure 3.
Table 2 shows the results on Chunking compared to previous work. We achieve the
state-of-the-art in all-phrase chunking. Shen and Sarkar [21] achieve the same score as
ours. However, they conduct experiments in noun phrase chunking (NP-chunking). All
phrase chunking contains much more tags than NP-chunking, which is more difficult.
SR decoding also achieves better results on English NER and Dutch NER than
existing methods. Huang et al. [28] employ a BLSTM-CRF model in the English
NER task and achieve F1 score of 90.10%. The score is lower than our best F1 score.
Chiu and Nichols [29] present a hybrid BLSTM with F1 score of 90.77%. The model
slightly outperforms our method, which may be due to the external CNNs they used to
extract word features. Gillick et al. [30] keep the best result of Dutch NER. However,
the model is trained on corpora of multilingual languages. Their model trained with
a single language gets 78.08% on F1 score and performs worse than ours. Nothman
et al. [18] reach 78.6% F1 with a semi-supervised approach in Dutch NER. Our model
21

English
Chinese

train
test
train
test

#{Sent}
38667
2336
8605
941

#{Overt}
909114
54242
193417
21797

#{Covert}
57342
3447
13518
1520

Table 3: Numbers of sentences, overt and covert elements in training and test sets.

still outperforms the method.
4.2. Experiments on Parsing
Joint Empty Category Detection and Dependency Parsing For joint empty category detection and dependency parsing, we conduct experiments on both English and
Chinese treebanks. In particular, English Penn TreeBank (PTB) [31] and Chinese TreeBank (CTB) [32] are used . Because PTB and CTB are phrase-structure treebanks, we
need to convert them into dependency annotations. To do so, we use the tool provided
by Stanford CoreNLP to process PTB, and the tool introduced by Xue and Yang [5]
to process CTB 5.0. We use gold-standard POS to derive features for disambiguation. To simplify our experiments, we preprocess the obtained dependency trees in the
following way.
1. We combine successive empty elements with identical head into one new empty
node that is still linked to the common head word.
2. Because the high-order algorithm is very expensive with respect to the computational cost, we only use relatively short sentence. Here we only keep the
sentences that are less than 64 tokens.
3. We focus on unlabeled parsing.
The statistics of the data after cleaning are shown in Table 3. We use the standard
training, validation, and test splits to facilitate comparisons. Accuracy is measured
with unlabeled attachment score for all overt words (UASo ): the percentage of the overt
words with the correct head. We are also concerned with the prediction accuracy for
empty elements. To evaluate performance on empty nodes, we consider the correctness
of empty edges. We report the percentage of the empty words in the right slot with
correct head. The i-th slot in the sentence means that the position immediately after the
i-th concrete word. So if we have a sentence with length n, we get n + 1 slots.
4.2.1. Results
Table 4 lists the accuracy of individual models coupled with different decoding
algorithms on the test sets. We focus on the prediction for overt words only. When
we take into account empty categories, more information is available. However, the
increased structural complexity affects the algorithms. From the table, we can see that
the complex sibling factorization works worse than the simple sibling factorization
in English, but works better in Chinese. The results of the tri-sibling factorization
are exactly the opposite. The complex tri-sibling factorization works better than the
22

Factorization
Sibling
Sibling (complex)
Tri-sibling
Tri-sibling (complex)

Empty Element
No
Yes
No
Yes

English
91.73
91.70
92.23
92.41

Chinese
89.16
89.20
90.00
89.82

Table 4: UASo of different individual models on test data. The upper and bottom blocks present results
obtained by sibling and tri-sibling models respectively. We cannot draw a conclusion whether the complex
structure models performs better or not, because the results vary with the structural complexity and the data.
This is expected, because structural complexity affects both the empirical risks and the structural risks. As
the data (English vs. Chinese) and the structure (Sibling vs. Tri-sibling) are different, the relations between
empirical risks and the structural risks are also different. Hence, the varied results.

Method
Sibling (complex)
Sibling (complex) + SR
Tri-sibling (complex)
Tri-sibling (complex) + SR

English
91.70
91.96 (+0.26)
92.41
92.71 (+0.30)

Chinese
89.20
89.53 (+0.33)
89.82
90.38 (+0.56)

Table 5: UASo of different SR decoding models on test data. As we can see, SR decoding consistently
improves the complex structure models. All improvements are statistically significant.

simple tri-sibling factorization in English, but works worse in Chinese. The results can
be explained by our theoretical analysis. While the structural complexity is positively
correlated with the overfitting risk, it is negatively correlated with the empirical risk. In
this task, although the overfitting risk is increased when using the complex structure,
the empirical risk is decreased more sometimes. Hence, the results vary both with the
structural complexity and the data.
Table 5 lists the accuracy of different SR decoding models on the test sets. We can
see that the SR decoding framework is effective to deal with the structure-based overfitting. This time, the accuracy of analysis for overt words is consistently improved.
For the second-order model, SR decoding reduces the error rate by 3.1% for English,
and by 3.0% for Chinese. For the third-order model, the error rate reduction of 4.0%
for English, and 5.5% for Chinese is achieved by the proposed method. Similar to the
sequence labeling tasks, the third-order model is improved more. We suppose the consistent improvements come from the ability of reducing the structural risk of the SR
decoding algorithm. Although in this task, the complex structure is sometimes helpful
to the accuracy of the parsing, the structural risk still increases. By regularizing the
structural complexity, further improvements can be achieved, on top of the decreased
empirical risk brought by the complex structure.
We use the Hypothesis Tests method [33] to evaluate the improvements. When the
p-value is set to 0.05, all improvements in Table 5 are statistically significant.
5. Related Work
The term structural regularization has been used in prior work for regularizing
structures of features. For (typically non-structured) classification problems, there
23

are considerable studies on structure-related regularization. Argyriou et al. [34] apply
spectral regularization for modeling feature structures in multi-task learning, where the
shared structure of the multiple tasks is summarized by a spectral function over the
tasks’ covariance matrix, and then is used to regularize the learning of each individual
task. Xue et al. [35] regularize feature structures for structural large margin binary classifiers, where data points belonging to the same class are clustered into subclasses so
that the features for the data points in the same subclass can be regularized. While those
methods focus on the regularization approaches, many recent studies focus on exploiting the structured sparsity. Structure sparsity is studied for a variety of non-structured
classification models [36, 37] and structured prediction scenarios [38, 39], via adopting
mixed norm regularization [40], Group Lasso [41], posterior regularization [42], and a
string of variations [43, 44, 45].
Compared with those pieces of prior work, the proposed method works on a substantially different basis. This is because the term structure in all of the aforementioned
work refers to structures of feature space, which is substantially different compared
with our proposal on regularizing tag structures (interactions among tags).
There are other related studies, including the studies of Sutton and McCallum [46]
and Samdani and Roth [47] on piecewise/decomposed training methods, and the study
of Tsuruoka et al. [48] on a “lookahead” learning method. They both try to reduce the
computational cost of the model by reducing the structure involved. Sutton and McCallum [46] try to simply the structural dependencies of the graphic probabilistic models,
so that the model can be efficiently trained. Samdani and Roth [47] try to simply the
output space in structured SVM by decomposing the structure into sub-structures, so
that the search space is reduced, and the training is tractable. Tsuruoka et al. [48] try to
train a localized structured perceptron, where the local output is searched by stepping
into the future instead of directly using the result of the classifier.
Our work differs from Sutton and McCallum [46], Samdani and Roth [47], Tsuruoka et al. [48], because our work is built on a regularization framework, with arguments and justifications on reducing generalization risk and for better accuracy, although it has the effect that the decoding space of the complex model is reduced by the
simple model. Also, the theoretical results can fit general graphical models, and the
detailed algorithm is quite different.
On generalization risk analysis, related studies include Tsuruoka et al. [49], Bousquet and Elisseeff [14], Shalev-Shwartz et al. [15] on non-structured classification and
Taskar et al. [12], London et al. [13, 50] on structured classification. This work targets
the theoretical analysis of the relations between the structural complexity of structured
classification problems and the generalization risk, which is a new perspective compared with those studies.
6. Conclusions
We propose a structural complexity regularization framework, called structure regularization decoding. In the proposed method, we train the complex structure model.
In addition, we also train the simple structure model. The simple structure model is
used to regularize the decoding of the complex structure model. The resulting model

24

embodies a balanced structural complexity, which reduces the structure-based overfitting risk. We derive the structure regularization decoding algorithms for linear-chain
models on sequence labeling tasks, and for hierarchical models on parsing tasks.
Our theoretical analysis shows that the proposed method can effectively reduce the
generalization risk, and the analysis is suitable for graphic models. In theory, higher
structural complexity leads to higher structure-based overfitting risk, but lower empirical risk. To achieve better performance, a balanced structural complexity should
be maintained. By regularizing the structural complexity, that is, decomposing the
structural dependencies but also keeping the original structural dependencies, structurebased overfitting risk can be alleviated and empirical risk can be kept low as well.
Experimental results demonstrate that the proposed method easily surpasses the
performance of the complex structure models. Especially, the proposed method is also
suitable for deep learning models. On the sequence labeling tasks, the proposed method
substantially improves the performance of the complex structure models, with the maximum F1 error rate reduction of 23.2% for the second-order models, and 36.4% for the
third-order models. On the parsing task, the maximum UAS improvement of 5.5% on
Chinese tri-sibling factorization is achieved by the proposed method. The results are
competitive with or even better than the state-of-the-art results.
Acknowledgments
This work was supported in part by National Natural Science Foundation of China
(No. 61300063), and Doctoral Fund of Ministry of Education of China (No. 20130001120004).
This work is a substantial extension of a conference paper presented at NIPS 2014 [1].
References
References
[1] X. Sun, Structure regularization for structured prediction, in: Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing
Systems 2014, Montreal, Quebec, Canada, pp. 2402–2410.
[2] S. Hochreiter, J. Schmidhuber, Long short-term memory, Neural Computation 9 (1997)
1735–1780.
[3] M. Collins, Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms, in: Proceedings of EMNLP’02, pp. 1–8.
[4] N. Chomsky, Lectures on Government and Binding, Foris Publications, Dordecht, 1981.
[5] N. Xue, Y. Yang, Dependency-based empty category detection via phrase structure trees,
in: Proceedings of the 2013 Conference of the North American Chapter of the Association
for Computational Linguistics: Human Language Technologies, Association for Computational Linguistics, Atlanta, Georgia, 2013, pp. 1051–1060.
[6] J. M. Eisner, Three new probabilistic models for dependency parsing: an exploration, in:
Proceedings of the 16th conference on Computational linguistics - Volume 1, Association
for Computational Linguistics, Stroudsburg, PA, USA, 1996, pp. 340–345.
[7] R. McDonald, F. Pereira, Online learning of approximate dependency parsing algorithms,
in: Proceedings of 11th Conference of the European Chapter of the Association for Computational Linguistics (EACL-2006)), volume 6, pp. 81–88.

25

[8] X. Carreras, Experiments with a higher-order projective dependency parser, in: J. Eisner (Ed.), EMNLP-CoNLL 2007, Proceedings of the 2007 Joint Conference on Empirical
Methods in Natural Language Processing and Computational Natural Language Learning,
ACL, Prague, Czech Republic, 2007, pp. 957–961.
[9] T. Koo, M. Collins, Efficient third-order dependency parsers, in: Proceedings of the
48th Annual Meeting of the Association for Computational Linguistics, Association for
Computational Linguistics, Uppsala, Sweden, 2010, pp. 1–11.
[10] X. Ma, H. Zhao, Fourth-order dependency parsing, in: Proceedings of COLING 2012:
Posters, The COLING 2012 Organizing Committee, Mumbai, India, 2012, pp. 785–796.
[11] X. Zhang, W. Sun, X. Wan, The covert helps parse the overt, in: Proceedings of the 21st
Conference on Computational Natural Language Learning (CoNLL 2017), Association for
Computational Linguistics, Vancouver, Canada, 2017, pp. 343–353.
[12] B. Taskar, C. Guestrin, D. Koller, Max-margin markov networks, in: S. Thrun, L. K.
Saul, B. Schölkopf (Eds.), Advances in Neural Information Processing Systems 16 [Neural
Information Processing Systems, NIPS 2003], MIT Press, Vancouver and Whistler, British
Columbia, Canada, 2003, pp. 25–32.
[13] B. London, B. Huang, B. Taskar, L. Getoor., Pac-bayes generalization bounds for randomized structured prediction, in: NIPS Workshop on Perturbation, Optimization and
Statistics.
[14] O. Bousquet, A. Elisseeff, Stability and generalization., Journal of Machine Learning
Research 2 (2002) 499–526.
[15] S. Shalev-Shwartz, O. Shamir, N. Srebro, K. Sridharan, Learnability and stability in the
general learning setting, in: COLT 2009 - The 22nd Conference on Learning Theory,
Montreal, Quebec, Canada, June 18-21, 2009.
[16] E. T. K. Sang, S. Buchholz, Introduction to the CoNLL-2000 shared task: Chunking, in:
Proceedings of CoNLL’00, pp. 127–132.
[17] E. F. Sang, F. D. Meulder, Introduction to the CoNLL-2003 Shared Task: LanguageIndependent Named Entity Recognition, in: Proceedings of CoNLL-2003, pp. 142–147.
[18] J. Nothman, N. Ringland, W. Radford, T. Murphy, J. R. Curran, Learning multilingual
named entity recognition from wikipedia, Artificial Intelligence 194 (2013) 151–175.
[19] J. Hammerton, Named entity recognition with long short-term memory, in: CoNLL, ACL,
2003, pp. 172–175.
[20] D. P. Kingma, J. Ba, Adam: A method for stochastic optimization, CoRR abs/1412.6980
(2014).
[21] H. Shen, A. Sarkar, Voting between multiple data representations for text chunking, in:
Advances in Artificial Intelligence, 18th Conference of the Canadian Society for Computational Studies of Intelligence, Canadian AI 2005, Victoria, Canada, May 9-11, 2005,
Proceedings, pp. 389–400.
[22] T. Kudoh, Y. Matsumoto, Use of support vector learning for chunk identification, in: Fourth
Conference on Computational Natural Language Learning, CoNLL 2000, and the Second
Learning Language in Logic Workshop, LLL 2000, Held in cooperation with ICGI-2000,
Lisbon, Portugal, September 13-14, 2000, pp. 142–144.
[23] T. Kudo, Y. Matsumoto, Chunking with support vector machines, in: Proceedings of
NAACL’01, pp. 1–8.
[24] F. Sha, F. Pereira, Shallow parsing with conditional random fields, in: NAACL ’03:
Proceedings of the 2003 Conference of the North American Chapter of the Association for
Computational Linguistics on Human Language Technology, pp. 134–141.
[25] R. T. McDonald, K. Crammer, F. Pereira, Flexible text segmentation with structured multilabel classification, in: HLT/EMNLP 2005, Human Language Technology Conference
and Conference on Empirical Methods in Natural Language Processing, Proceedings of

26

[26]

[27]

[28]
[29]
[30]
[31]
[32]
[33]

[34]

[35]

[36]
[37]

[38]

[39]
[40]
[41]
[42]
[43]

the Conference, 6-8 October 2005, Vancouver, British Columbia, Canada, The Association
for Computational Linguistics, 2005, pp. 987–994.
X. Sun, L. Morency, D. Okanohara, Y. Tsuruoka, J. Tsujii, Modeling latent-dynamic in
shallow parsing: A latent conditional model with imrpoved inference, in: COLING 2008,
22nd International Conference on Computational Linguistics, Proceedings of the Conference, 18-22 August 2008, Manchester, UK, pp. 841–848.
R. Collobert, J. Weston, L. Bottou, M. Karlen, K. Kavukcuoglu, P. P. Kuksa, Natural
language processing (almost) from scratch, Journal of Machine Learning Research 12
(2011) 2493–2537.
Z. Huang, W. Xu, K. Yu, Bidirectional lstm-crf models for sequence tagging, arXiv preprint
arXiv:1508.01991 (2015).
J. P. C. Chiu, E. Nichols, Named entity recognition with bidirectional lstm-cnns., TACL 4
(2016) 357–370.
D. Gillick, C. Brunk, O. Vinyals, A. Subramanya, Multilingual language processing from
bytes, CoRR abs/1512.00103 (2015).
N. Xue, F. Xia, F.-d. Chiou, M. Palmer, The penn Chinese treebank: Phrase structure
annotation of a large corpus, Natural Language Engineering 11 (2005) 207–238.
M. P. Marcus, M. A. Marcinkiewicz, B. Santorini, Building a large annotated corpus of
english: the penn treebank, Computational Linguistics 19 (1993) 313–330.
T. Berg-Kirkpatrick, D. Burkett, D. Klein, An empirical investigation of statistical significance in nlp, in: Proceedings of the 2012 Joint Conference on Empirical Methods in
Natural Language Processing and Computational Natural Language Learning, Association
for Computational Linguistics, Jeju Island, Korea, 2012, pp. 995–1005.
A. Argyriou, C. A. Micchelli, M. Pontil, Y. Ying, A spectral regularization framework for
multi-task structure learning, in: J. C. Platt, D. Koller, Y. Singer, S. T. Roweis (Eds.), Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia,
Canada, December 3-6, 2007, Curran Associates, Inc., 2007, pp. 25–32.
H. Xue, S. Chen, Q. Yang, Structural regularized support vector machine: A framework
for structural large margin classifier., IEEE Transactions on Neural Networks 22 (2011)
573–587.
C. A. Micchelli, J. Morales, M. Pontil, A family of penalty functions for structured sparsity., in: Proceedings of NIPS’10, Curran Associates, Inc., 2010, pp. 1612–1623.
J. C. Duchi, Y. Singer, Boosting with structural sparsity, in: A. P. Danyluk, L. Bottou,
M. L. Littman (Eds.), Proceedings of the 26th Annual International Conference on Machine
Learning, ICML 2009, Montreal, Quebec, Canada, June 14-18, 2009, volume 382 of ACM
International Conference Proceeding Series, ACM, 2009, pp. 297–304.
M. W. Schmidt, K. P. Murphy, Convex structure learning in log-linear models: Beyond
pairwise potentials., in: Proceedings of AISTATS’10, volume 9 of JMLR Proceedings, pp.
709–716.
A. F. T. Martins, N. A. Smith, M. A. T. Figueiredo, P. M. Q. Aguiar, Structured sparsity in
structured prediction., in: Proceedings of EMNLP’11, pp. 1500–1511.
A. Quattoni, X. Carreras, M. Collins, T. Darrell, An efficient projection for l1,infinity
regularization., in: Proceedings of ICML’09, p. 108.
M. Yuan, Y. Lin, Model selection and estimation in regression with grouped variables,
Journal of the Royal Statistical Society, Series B 68 (2006) 49–67.
J. Graça, K. Ganchev, B. Taskar, F. Pereira, Posterior vs parameter sparsity in latent variable
models, in: Proceedings of NIPS’09, pp. 664–672.
F. Bach, R. Jenatton, J. Mairal, G. Obozinski, Structured sparsity through convex optimization, CoRR abs/1109.2397 (2011).

27

[44] G. Obozinski, B. Taskar, M. I. Jordan, Joint covariate selection and joint subspace selection
for multiple classification problems., Statistics and Computing 20 (2010) 231–252.
[45] J. Huang, T. Zhang, D. N. Metaxas, Learning with structured sparsity., Journal of Machine
Learning Research 12 (2011) 3371–3412.
[46] C. A. Sutton, A. McCallum, Piecewise pseudolikelihood for efficient training of conditional
random fields., in: ICML’07, ACM, 2007, pp. 863–870.
[47] R. Samdani, D. Roth, Efficient decomposed learning for structured prediction, in: Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh,
Scotland, UK, June 26 - July 1, 2012, icml.cc / Omnipress, 2012.
[48] Y. Tsuruoka, Y. Miyao, J. Kazama, Learning with lookahead: Can history-based models
rival globally optimized models?, in: S. Goldwater, C. D. Manning (Eds.), Proceedings
of the Fifteenth Conference on Computational Natural Language Learning, CoNLL 2011,
Portland, Oregon, USA, June 23-24, 2011, ACL, 2011, pp. 238–246.
[49] Y. Tsuruoka, J. Tsujii, S. Ananiadou, Stochastic gradient descent training for l1-regularized
log-linear models with cumulative penalty, in: Proceedings of ACL’09, Suntec, Singapore,
pp. 477–485.
[50] B. London, B. Huang, B. Taskar, L. Getoor, Collective stability in structured prediction:
Generalization from one example, in: Proceedings of the 30th International Conference on
Machine Learning (ICML-13), pp. 828–836.
[51] X. Sun, W. Li, H. Wang, Q. Lu, Feature-frequency-adaptive on-line training for fast and
accurate natural language processing, Computational Linguistics 40 (2014) 563–586.
[52] H. Noji, Y. Miyao, M. Johnson, Using left-corner parsing to encode universal structural
constraints in grammar induction, in: Proceedings of the EMNLP’16, pp. 33–43.
[53] Y. Miyao, R. Sætre, K. Sagae, T. Matsuzaki, J. Tsujii, Task-oriented evaluation of syntactic
parsers and their representations, in: Proceedings of ACL’08, pp. 46–54.
[54] X. Sun, T. Matsuzaki, D. Okanohara, J. Tsujii, Latent variable perceptron algorithm for
structured classification, in: Proceedings of the 21st International Joint Conference on
Artificial Intelligence (IJCAI 2009), pp. 1236–1242.
[55] T. Matsuzaki, Y. Miyao, J. Tsujii, Probabilistic CFG with latent annotations, in: Proceedings of ACL’05, pp. 75–82.
[56] T. Matsuzaki, J. Tsujii, Comparative parser performance analysis across grammar frameworks through automatic tree conversion using synchronous grammars, in: Proceedings of
COLING’08, pp. 545–552.
[57] J. Nivre, J. Hall, J. Nilsson, A. Chanev, G. Eryigit, S. Kübler, S. Marinov, E. Marsi, Maltparser: A language-independent system for data-driven dependency parsing, Natural Language Engineering 13 (2007) 95–135.
[58] J. Nivre, Algorithms for deterministic incremental dependency parsing, Computational
Linguistics 34 (2008) 513–553.
[59] Y. Zhang, S. Clark, A tale of two parsers: Investigating and combining graph-based and
transition-based dependency parsing, in: Proceedings of EMNLP’08, pp. 562–571.
[60] Y. Zhang, S. Clark, Syntactic processing using the generalized perceptron and beam search,
Computational Linguistics 37 (2011) 105–151.
[61] O. Vinyals, L. Kaiser, T. Koo, S. Petrov, I. Sutskever, G. E. Hinton, Grammar as a foreign
language, in: NIPS’15, pp. 2773–2781.
[62] H. He, X. Sun, A unified model for cross-domain and semi-supervised named entity recognition in chinese social media, in: Proceedings of the Thirty-First AAAI Conference on
Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., pp. 3216–
3222.
[63] H. He, X. Sun, F-score driven max margin neural network for named entity recognition
in chinese social media, in: Proceedings of the 15th Conference of the European Chapter

28

of the Association for Computational Linguistics, EACL 2017, Valencia, Spain, April 3-7,
2017, Volume 2: Short Papers, pp. 713–718.
[64] X. Sun, Structure regularization for structured prediction: Theories and experiments,
CoRR abs/1411.6243 (2014).

Appendix A. Proof
Our analysis sometimes needs to use McDiarmid’s inequality.
Theorem 10 (McDiarmid, 1989). Let S = {q1 , . . . , qm } be independent random variables taking values in the space Qm . Moreover, let g : Qm 7→ R be a function of S that
satisfies ∀i, ∀S ∈ Qm , ∀q̂i ∈ Q,
|g(S ) − g(S i )| ≤ ci .
Then ∀ > 0,
 −2 2 
PS [g(S ) − ES [g(S )] ≥ ] ≤ exp Pm 2 .
i=1 ci
Lemma 11 (Symmetric learning). For any symmetric (i.e., order-free) learning algorithm G, ∀i ∈ {1, . . . , m}, we have
ES [R(GS ) − Re (GS )] =

1
ES ,ẑẑi [L(GS , ẑi ) − L(GS i , ẑi )]
n

Proof
m


1 
1X
ES [R(GS ) − Re (GS )] = ES Ez (L(GS , z)) −
L(GS , z j )
n
m j=1
m

=

 1X

1
ES L(GS , z j )
ES ,ẑẑi L(GS , ẑ i ) −
n
m j=1



1
ES ,ẑẑi L(GS , ẑ i ) − ES L(GS , z i )
n


1
= ES ,ẑẑi L(GS , ẑ i ) − ES i L(GS i , ẑ i )
n

1
= ES ,ẑẑi L(GS , ẑ i ) − L(GS i , ẑ i )
n
=

where the 3rd step is based on ES L(GS , z i ) = ES L(GS , z j ) for ∀zzi ∈ S and ∀zz j ∈ S ,
given that G is symmetric.
t
u

Appendix A.1. Proofs
Proof of Lemma 5

29

According to (5), we have ∀i, ∀S , ∀zz, ∀k
|`τ (GS , z, k) − `τ (GS \i , z, k)| = |cτ [GS (xx, k), y(k) ] − cτ [GS \i (xx, k), y(k) ]|
≤ τ|GS (xx, k) − GS \i (xx, k)|
≤ τ∆
This gives the bound of loss stability.
Also, we have ∀i, ∀S , ∀zz
|Lτ (GS , z) − Lτ (GS \i , z)| =
≤

n
X
k=1
n
X

cτ [GS (xx, k), y(k) ] −

n
X

cτ [GS \i (xx, k), y(k) ]

k=1

cτ [GS (xx, k), y (k) ] − cτ [GS \i (xx, k), y (k) ]

k=1
n
X

≤τ

|GS (xx, k) − GS \i (xx, k)|

k=1

≤ nτ∆
t
u

This derives the bound of sample loss stability.

Proof of Theorem 6
When a convex and differentiable function g has a minimum f in space F , its
Bregman divergence has the following property for ∀ f 0 ∈ F :
dg ( f 0 , f ) = g( f 0 ) − g( f )
With this property, we have
0

0

0

0

0

0

\i
\i
dRα,λ ( f \i , f ) + dR\i0 ( f, f \i ) = Rα,λ ( f \i ) − Rα,λ ( f ) + R\i
α,λ ( f ) − Rα,λ ( f )
α,λ
0

0
\i0
\i0 
= Rα,λ ( f \i ) − R\i
α,λ ( f ) − Rα,λ ( f ) − Rα,λ ( f )
1
1
0
Lτ ( f \i , z 0i0 ) −
Lτ ( f, z 0i0 )
=
mn
mn

30

(A.1)

Then, based on the property of Bregman divergence that dg+g0 = dg + dg0 , we have
0

0

0

0

dNλ ( f, f \i ) + dNλ ( f \i , f ) = d(R\i0 −R\iα 0 ) ( f, f \i ) + d(Rα,λ −Rα ) ( f \i , f )
α,λ

0

0

0

0

= dRα,λ ( f \i , f ) + dR\i0 ( f, f \i ) − dRα ( f \i , f ) − dR\iα 0 ( f, f \i )
α,λ

(based on non-negativity of Bregman divergence)
0

0

≤ dRα,λ ( f \i , f ) + dR\i0 ( f, f \i )
α,λ

(using (A.1))

1
0
=
Lτ ( f \i , z 0i0 ) − Lτ ( f, z 0i0 )
mn
n/α

1 X
0
`τ ( f \i , z 0i0 , k) − `τ ( f, z 0i0 , k)
=
mn k=1

(A.2)

n/α




1 X  \i0 0
cτ f (xxi0 , k), y 0i0 (k) − cτ f (xx0i0 , k), y 0i0 (k)
≤
mn k=1
n/α

≤

τ X \i0 0
f (xxi0 , k) − f (xx0i0 , k)
mn k=1

(using (6))
ρτ
0
|| f − f \i ||2 · ||xx0i0 ||2
≤
mα
Moreover, Nλ (g) =
gence satisfies:

λ
2
2 ||g||2

=

λ
2 hg, gi

is a convex function and its Bregman diver-


λ
hg, gi − hg0 , g0 i − h2g0 , g − g0 i
2
λ
= ||g − g0 ||22
2

dNλ (g, g0 ) =

(A.3)

Combining (A.2) and (A.3) gives
0

λ|| f − f \i ||22 ≤

ρτ
0
|| f − f \i ||2 · ||xx0i0 ||2
mα

(A.4)

which further gives

ρτ 0
||xx 0 ||2
(A.5)
mλα i
Given ρ-admissibility, we derive the bound of function stability ∆( f ) based on sample z with size n. We have ∀zz = (xx, y ), ∀k,
0

|| f − f \i ||2 ≤

0

0

| f (xx, k) − f \i (xx, k)| ≤ ρ|| f − f \i ||2 · ||xx||2
(using (A.5))
τρ2 0
≤
||xx 0 ||2 · ||xx||2
mλα i
31

(A.6)

With the feature dimension d and x (k,q) ≤ v for q ∈ {1, . . . , d} , we have
||xx||2 = ||

n
X

x (k) ||2

k=1

≤ ||hnv, . . . , nvi||2
| {z }

(A.7)

d

√
= dn2 v2
√
= nv d
√

Similarly, we have ||xx0i0 ||2 ≤ nvα d because x 0i0 is with the size n/α.
Inserting the bounds of ||xx||2 and ||xx0i0 ||2 into (A.6), it goes to
0

| f (xx, k) − f \i (xx, k)| ≤

dτρ2 v2 n2
mλα2

which gives (13). Further, using Lemma 5 derives the loss stability bound of
and the sample loss stability bound of

dτ2 ρ2 v2 n3
mλα2

on the minimizer f .

(A.8)
dτ2 ρ2 v2 n2
,
mλα2

t
u

Proof of Corollary 7
The proof is similar to the proof of Theorem 6. First, we have
\i
\i
dRα,λ ( f \i , f ) + dR\i ( f, f \i ) = Rα,λ ( f \i ) − Rα,λ ( f ) + R\i
α,λ ( f ) − Rα,λ ( f )
α,λ

\i
\i 
= Rα,λ ( f \i ) − R\i
α,λ ( f ) − Rα,λ ( f ) − Rα,λ ( f )
α
α
1 X
1 X
Lτ ( f \i , z (i, j) ) −
Lτ ( f, z (i, j) )
=
mn j=1
mn j=1

32

(A.9)

Then, we have
dNλ ( f, f \i ) + dNλ ( f \i , f ) = d(R\i

\i
α,λ −Rα )

( f, f \i ) + d(Rα,λ −Rα ) ( f \i , f )

= dRα,λ ( f \i , f ) + dR\i ( f, f \i ) − dRα ( f \i , f ) − dR\iα ( f, f \i )
α,λ

(based on non-negativity of Bregman divergence)
≤ dRα,λ ( f \i , f ) + dR\i ( f, f \i )
α,λ

(using (A.9))
α
α
1 X
1 X
=
Lτ ( f \i , z (i, j) ) −
Lτ ( f, z (i, j) )
mn j=1
mn j=1
=

!
n/α
n/α
α
X
1 X X
`τ ( f \i , z (i, j) , k) −
`τ ( f, z (i, j) , k)
mn j=1 k=1
k=1

≤

1 XX
`τ ( f \i , z (i, j) , k) − `τ ( f, z (i, j) , k)
mn j=1 k=1

≤

τ X X \i
f (xx(i, j) , k) − f (xx(i, j) , k)
mn j=1 k=1

α

n/α

α

n/α

(A.10)

(using (6), and define ||xx(i,max) ||2 = max ||xx(i, j) ||)2 )
ρτ
≤ || f − f \i ||2 · ||xx(i,max) ||2
m
This gives
λ|| f − f \i ||22 ≤

∀j

ρτ
|| f − f \i ||2 · ||xx(i,max) ||2
m

(A.11)

and thus

ρτ
||xx(i,max) ||2
(A.12)
mλ
Then, we derive the bound of function stability ∆( f ) based on sample z with size n,
and based on \i rather than \i0 . We have ∀zz = (xx, y ), ∀k,
|| f − f \i ||2 ≤

| f (xx, k) − f \i (xx, k)| ≤ ρ|| f − f \i ||2 · ||xx||2
(using (A.12))
τρ2
||xx(i,max) ||2 · ||xx||2
mλ
√
√
τρ2 nv d
≤
·
· nv d
mλ
α
dτρ2 v2 n2
=
mλα
(using (13))
≤

(A.13)

= α sup(∆)
t
u
33

Proof of Theorem 8
Let f \i be defined like before. Similar to the definition of f \i based on removing a
sample from S , we define f i based on replacing a sample from S . Let R( f )\i denote
[R( f )]\i = R\i ( f \i ).
First, we derive a bound for |R( f ) − R\i ( f )|:
1
|Ez Lτ ( f, z ) − Ez Lτ ( f \i , z )|
n
n
n
X
1 X
z
= |Ez
`τ ( f, , k) − Ez
`τ ( f \i , z, k)|
n
k=1
k=1

|R( f ) − R( f )\i | =

≤

n
n
X
1 X
`τ ( f \i , z , k)|
`τ ( f, z , k) −
Ez |
n
k=1
k=1

≤

1 X
Ez
|`τ ( f, z , k) − `τ ( f \i , z , k)|
n k=1

(A.14)

n

¯
(based on Lemma 5 and the definition of ∆)
¯
≤ τ∆
Then, we derive a bound for |R( f ) − R( f )i |:
|R( f ) − R( f )i | = |R( f ) − R( f )\i + R( f )\i − R( f )i |
≤ |R( f ) − R( f )\i | + |R( f )\i − R( f )i |
(based on (A.14))
≤ τ∆¯ + τ∆¯
= 2τ∆¯
Moreover, we derive a bound for |Re ( f ) − Re ( f )i |. Let ẑ i denote the full-size sample

34

(with size n and indexed by i) which replaces the sample z i , it goes to:
m

1 X
1
1 X
|Re ( f ) − Re ( f ) | =
Lτ ( f i , z j ) −
Lτ ( f, z j ) −
Lτ ( f i , ẑi )
mn j=1
mn j,i
mn
1 X
1
|Lτ ( f, z i ) − Lτ ( f i , ẑ i )|
≤
|Lτ ( f, z j ) − Lτ ( f i , z j )| +
mn j,i
mn
i

n

≤

1 X
1 X
|`τ ( f, z i , k) − `τ ( f i , ẑ i , k)|
|Lτ ( f, z j ) − Lτ ( f i , z j )| +
mn j,i
mn k=1

(based on 0 ≤ `τ (GS , z , k) ≤ γ)
γ
1 X
|Lτ ( f, z j ) − Lτ ( f i , z j )| +
≤
mn j,i
m
 γ
1 X
|Lτ ( f, z j ) − Lτ ( f \i , z j )| + |Lτ ( f \i , z j ) − Lτ ( f i , z j )| +
≤
mn j,i
m
(based on Lemma 5, and ∆( f i , f \i ) = ∆( f, f \i ) from the definition of stability)
 γ
1 X ¯
≤
nτ∆ + nτ∆¯ +
mn j,i
m
=

2(m − 1)τ∆¯ + γ
m
(A.15)

Based on the bounds of |R( f )−R( f )i | and |Re ( f )−Re ( f )i |, we show that R( f )−Re ( f )
¯
∆+γ
satisfies the conditions of McDiarmid Inequality (Theorem 10) with ci = (4m−2)τ
:
m
|[R( f ) − Re ( f )] − [R( f ) − Re ( f )]i | = |[R( f ) − R( f )i ] − [Re ( f ) − Re ( f )i ]|
≤ |R( f ) − R( f )i | + |Re ( f ) − Re ( f )i |
2(m − 1)τ∆¯ + γ
≤ 2τ∆¯ +
m
(4m − 2)τ∆¯ + γ
=
m

35

(A.16)

Also, following the proof of Lemma 11, we can get a bound for ES [R( f ) − Re ( f )]:
ES [R( f ) − Re ( f )] =
=

m

1 
1X
ES Ez (L( f, z )) −
L( f, z j )
n
m j=1
m
 1X

1
ES ,ẑẑi L( f, ẑ i ) −
ES L( f, z j )
n
m j=1



1
ES ,ẑẑi L( f, ẑ i ) − ES L( f, z i )
n


1
= ES ,ẑẑi L( f, ẑ i ) − ES i L( f i , ẑ i )
n
(A.17)

1
= ES ,ẑẑi L( f, ẑ i ) − L( f i , ẑ i )
n
1
≤ ES ,ẑẑi |L( f, ẑ i ) − L( f i , ẑ i )|
n
1
1
≤ ES ,ẑẑi |L( f, ẑ i ) − L( f \i , ẑ i )| + ES ,ẑẑi |L( f \i , ẑ i ) − L( f i , ẑ i )|
n
n
(based on Lemma 5 and the ∆¯ defined in (15))
≤ τ∆¯ + τ∆¯
=

= 2τ∆¯
Now, we can apply McDiarmid Inequality (Theorem 10):


 −2 2 
PS [R( f ) − Re ( f )] − ES [R( f ) − Re ( f )] ≥  ≤ exp Pm 2
i=1 ci

(A.18)

Based on (A.16) and (A.17), it goes to


PS R( f ) − Re ( f ) ≥ 2τ∆¯ +  ≤ exp
Let δ = exp



−2m 2
2
¯
(4m−2)τ∆+γ

−2m 2

(4m − 2)τ∆¯ + γ 2

!
(A.19)


, we have
r


 = (4m − 2)τ∆¯ + γ



ln δ−1
2m

(A.20)

Based on (A.19) and (A.20), there is a probability no more than δ such that
R( f ) − Re ( f ) ≥ 2τ∆¯ + 
r

ln δ−1
2m

r

ln δ−1
2m



= 2τ∆¯ + (4m − 2)τ∆¯ + γ
Then, there is a probability at least 1 − δ such that


R( f ) ≤ Re ( f ) + 2τ∆¯ + (4m − 2)τ∆¯ + γ
36

(A.21)

t
u

which gives (16).
Proof of Theorem 9
2 2 2
v n
According to (15), we have ∆¯ ≤ dτρmλα
.
Inserting this bound into (16) gives (18).

t
u

Appendix B. Scalable Decoding with Pruning in Sequence Labeling Tasks
Train time (overall)
BLSTM order1 + SR
BLSTM order2 + SR
BLSTM order3 + SR
Test time (overall)
BLSTM order1 + SR
BLSTM order2 + SR
BLSTM order3 + SR

Chunking
443.13
448.65
459.75
Chunking
10.71
13.64
44.81

English-NER
677.16
705.23
726.58
English-NER
10.08
13.13
20.43

Dutch-NER
484.74
511.08
520.85
Dutch-NER
15.89
26.60
28.66

Table B.6: Timing Results on varying the orders.

SR decoding is implemented by extending the Viterbi decoding algorithm, and
multi-order dependencies are jointly considered. Originally, we should consider all
possible transition states for every position, which means the search space is very large
because there are often too many high order tags. However, in the complete search
space, we may compute many tag-transitions that are almost impossible in the best
output tag sequence. Thus, it is crucial to adopt good pruning strategies to reduce
the search space in decoding to avoid the unnecessary computation of the impossible
state transitions. For scalability, we adopt two pruning techniques to greatly reduce the
search space.
First, we use low order information to prune the search space of high order information. There can be different implementations for this idea. In practice, we find a simple
pruning strategy already works well. We simply use order-1 probability to prune the
tag candidates at each position, such that only top-k candidates at each position are
used to generate the search space for higher order dependencies. In practice we find
top-5 pruning gives no loss on accuracy at all.
Second, we prune the search space according to training set, such that only the
tag dependencies appeared in the training data will be considered as probable tag dependencies in the decoding. We collect a dictionary of the tag dependencies from the
training set, and the first pruning technique is based on this dictionary.
With this implementation, our scalable multi-order decoding performs efficiently
on various real-world NLP tasks and keeps good scalability. The overall training time
and the overall test time on the tasks are shown in the Table B.6.5
5 The “overall” time of BLSTM-SR means that the time of all related orders are added together already.
For example, BLSTM-SR-order3’s overall time already includes the time of order-1 and order-2 models.

37

