Learning What’s Easy: Fully Differentiable Neural Easy-First Taggers
Julia Kreutzer∗
André F. T. Martins
Computational Linguistics
UnbabelHeidelberg University, Germany& Instituto de Telecomunicações
kreutzer@cl.uni-heidelberg.de
Lisbon, Portugal
andre.martins@unbabel.com

Abstract
We introduce a novel neural easy-first decoder that learns to solve sequence tagging tasks in a flexible order. In contrast to previous easy-first decoders, ourmodels are end-to-end differentiable. The
decoder iteratively updates a “sketch” ofthe predictions over the sequence. At its
core is an attention mechanism that controls which parts of the input are strategically the best to process next. We present
a new constrained softmax transformationthat ensures the same cumulative attention
to every word, and show how to efficiently
evaluate and backpropagate over it. Ourmodels compare favourably to BILSTM
taggers on three sequence tagging tasks.

1

Introduction

In the last years, neural models have led to major advances in several structured NLP problems,
including sequence tagging (Plank et al., 2016;
Lample et al., 2016), sequence-to-sequence prediction (Sutskever et al., 2014), and sequence-totree (Dyer et al., 2015). Part of the success comesfrom clever architectures such as (bidirectional)
long-short term memories (BILSTMs; Hochreiterand Schmidhuber (1997); Graves et al. (2005))
and attention mechanisms (Bahdanau et al., 2015),
which are able to select the pieces of context relevant for prediction.
A noticeable aspect about many of the systems
above is that they typically decode from left toright, greedily or with a narrow beam. While
this is computationally convenient and reminiscent of the way humans process spoken language,
the combination of unidirectional decoding and∗This research was partially carried out during an internship at Unbabel.

greediness leads to error propagation and suboptimal classification performance. This can partly be
mitigated by globally normalized models (Andoret al., 2016) and imitation learning (Daumé et al.,2009; Ross et al., 2011; Bengio et al., 2015), however these techniques still have a left-to-right bias.
Easy-first decoders (Tsuruoka and Tsujii,
2005; Goldberg and Elhadad, 2010, §2) are an interesting alternative: instead of a fixed decoding
order, these methods schedule their own actions
by prefering “easier” decisions over more difficult ones. A disadvantage is that these models
are harder to learn, due to the factorial number oforderings leading to correct predictions. Usually,
gradients are not backpropagated over this combinatorial latent space (Kiperwasser and Goldberg,2016), or a separate model is used to determine
the easiest next move (Clark and Manning, 2016).
In this paper, we develop novel, fully differentiable, neural easy-first sequence taggers (§3).
Instead of taking discrete actions, our decoders use
an attention mechanism to decide (in a soft manner) which word to focus on for the next tagging
decision. Our models are able to learn their own
sense of “easiness”: the words receiving focus
may not be the ones the model is most confident
about, but the best to avoid error propagation in thelong run. To make sure that all words receive thesame cumulative attention, we further contributewith a new constrained softmax transformation(§4). This transformation extends the softmax bypermitting upper bound constraints on the amountof probability a word can receive. We show how
to evaluate this transformation and backpropagate
its gradients.
We run experiments in three sequence tagging
tasks: multilingual part-of-speech (POS) tagging,
named entity recognition (NER), and word-level
quality estimation (§5). We complement our findings with a visual analysis of the attention distribu-

Algorithm 1 Easy-First Sequence Tagging
Input: input sequence x1:L
Output: tagged sequence yb1:L
1: initialize B = S = ∅2: while B 6= {1, . . . , L} do
3:for each non-covered position i ∈/ B do4:
compute scores f (i, yi ; x1:L , S), ∀yi
5:
end for6:(j, ybj ) = argmaxi,yi f (i, yi ; x1:L , S)
7:
S ← S ∪ {(j, ybj )}, B ← B ∪ {j}8: end whiletions produced by the decoder, to help understandwhat tagging decisions the model finds the easiest.

2

Easy-First Decoders

The idea behind easy-first decoding is to perform“easier” and less risky decisions before committing to more difficult ones (Tsuruoka and Tsujii, 2005; Goldberg and Elhadad, 2010; Ma et al.,2013). Alg. 1 shows the overall procedure for asequence tagging problem (the idea carries out toother structured problems). Let x1:L be an input
sequence (e.g. words in a sentence) and y1:L be
the corresponding tag sequence (e.g. their POStags). The algorithm assigns tags one position iat the time, maintaining a set B of covered positions. It also maintains a set S of pairs (i, ybi ),storing the tags that have already been predicted atthose positions. We can regard this set as a sketchof the output sequence, built incrementally while
the algorithm is executed. At each time step, themodel computes a score f (i, yi ; x1:L , S) for eachposition i ∈/ B and each candidate tag yi , taking
into account the current “sketch” S, which provides useful contextual information. The “easiest”
position and the corresponding tag are then jointly
obtained by maximizing this score (line 6). The algorithm terminates when all positions are covered.
Previous work has trained easy-first systems
with variants of the perceptron algorithm (Goldberg and Elhadad, 2010; Ma et al., 2013) or witha gradient-based method (Kiperwasser and Goldberg, 2016)—but without backpropagating information about the best ordering chosen by the algorithm (only tag mistakes). In fact, doing so directly
would be hard, since the space of possible orderings is combinatorial—the argmax in line 6 is notcontinuous, let alone differentiable. In the next
section, we introduce a fully differentiable easyfirst system that sidesteps this problem by working
with a “continuous” space of actions.

Figure 1: A neural easy-first system applied toa POS tagging problem. Given the current input/sketch representation, an attention mechanism
decides where to focus (see bar plot) and is used
to generate the next sketch. Right: A sequence ofsketches (Sn )N
n=1 generated along the way.

3

Neural Easy-First Sequence Taggers

Let ∆L−1 := {α ∈ RL | 1> α = 1, α ≥ 0} be
the probability simplex. Our neural easy-first decoders depart from Alg. 1 in the following key
points:• Instead of picking the position with the largest
score at each step (line 6 in Alg. 1), we computea (continuous) attention distribution α ∈ ∆L−1
over word positions.
• Instead of a set of covered positions B, we maintain a (continuous) cumulative attention vector β ∈ RL (ideally in [0, 1]L ) over the L positions in the sequence.
• The sketch set S is replaced by a sketch matrix S ∈ RDs ×L , whose columns are Ds dimensional vector representations of the output
labels to be predicted.
The high-level procedure is shown in Figure 1. We
describe two models that implement this procedure: a single-state model and a full-state model.
They differ in the way they update the sketch matrix: the single-state model applies a rank-one update, while the full-state model does a full update.
3.1

Single-State Model (NEF-S)PK

Let concat(x1 , . . . , xK ) ∈ R k=1 Dk be the concatenation of the vectors xk ∈ RDk . We use theshorthand affine(x) := Wx+b to denote an affine
transformation of x, where W is a weight matrix
and b is a bias vector.
Alg. 2 shows the overall procedure. We startby encoding the input sequence x1:L as a matrix

Algorithm 2 Neural Easy-First Sequence Tagging
Input: input sequence x1:L , sketch steps N
Output: tagged sequence yb1:L
1: initialize β 0 = 0 and s0i = 0, ∀i ∈ [L]
2: encode sequence as [h1 , . . . , hL ]3: for n = 1, 2, . . . , N do
4:
for each position i ∈ [L] don5:compute cn
i and zi (Eqs. 1–2)
6:
end for7:
compute attention αn = ρ(z n ; β n−1 )8:for each position i ∈ [L] donn9:refine sketch sn
i from αi and ci , via Eq. 4 (singlestate) or Eq. 7 (full-state)10:
end for11:
β n = β n−1 + αn
12: end for
13: for each position i ∈ [L] do
14:pi = softmax(affine(concat(hi , sN
i )))
15:
predict ybi = argmaxyi pi (yi )16: end for

H = [h1 , . . . , hL ] ∈ RDh ×L (line 2). Our model
is completely agnostic about this encoding step. In
our experiments, we compute H by composing alookup embedding layer with a BILSTM (Hochreiter and Schmidhuber, 1997; Graves et al., 2005),
as this strategy was successful in similar structured
prediction tasks. However, other choices are possible, for example using convolutional layers.
As stated above, our algorithm maintains a cumulative attention vector β ∈ RL and a sketch
matrix S ∈ RDs ×L , both with all entries initialized to zero. It then performs N sketching steps,
which progressively refine this sketch matrix, producing versions S1 , . . . , SN . At the nth step, thefollowing operations are performed:
Input-Sketch Contextual Representation. For
each word i ∈ [L], we compute a state cni summarizing the surrounding local information aboutother words and sketches. We use a simple vector
concatenation over a w-wide context window:n−1
cni = concat(hi−w , . . . , hi+w , sn−1
i−w , . . . , si+w ),
(1)
n−1 .
where we denote by sn−1
thejthcolumnofSj
The intuition is that the current sketches provide valuable information about the neighboringwords’ predictions that can influence the prediction for the ith word. In the vanilla easy-first algorithm, this was assumed in the score computation(line 4 of Alg. 1).

(2015). We first compute a score for each wordi ∈ [L] based on its contextual representation,
zin = v > tanh(affine(cni )),where v ∈ RDz is a model parameter. Then, weaggregate these scores in a vector z n ∈ RL andapply a transformation ρ to map them to a probability distribution αn ∈ ∆L−1 (optionally taking
into account the past cumulative attention β n−1 ):αn = ρ(z n ; β n−1 ).

(3)The “standard” choice for ρ is the softmax transformation. However, in this work, we consider
other possible transformations (to be described in§4). After this, the cumulative attention is updated
via β n = β n−1 + αn .
Sketch Generation. Now that we have a distribution αn ∈ ∆L−1 over word positions, it remains
to generate a sketch for those words. We first compute a single-state vectorof the enPL representationnnntire sentence c̄ =i=1 αi ci as the weighted
average of the word states defined in Eq. 1. Then,
we update each column of the sketch matrix as:1
sni = sin−1 +αin ·tanh(affine(c̄n )), ∀i ∈ [L]. (4)The intuition for this update is the following: inthe extreme case where the attention distribution ispeaked on a single word (say, the kth word, αn =ek ), we obtain c̄n = cnk and the sketch update only
affects that word, i.e., n−1
si + tanh(affine(cnk )) if i = k
sni =
sin−1
if i 6= k.
(5)This is similar to the sketch update in the originaleasy-first algorithm (line 7 in Alg. 1).
The three operations above are repeated N
times (or “sketch steps”). The standard choice is
N = L (one step per word), which mimics thevanilla easy-first algorithm. However, it is possible to have fewer steps (or more, if we want the decoder to be able to “self-correct”). After completing the N sketch steps, we obtain the final sketchNmatrix SN = [sN
1 , . . . , sL ]. Then, we compute a
tag probability for every word as follows:2
pi = softmax(affine(concat(hi , sNi ))).
1

Attention Mechanism. We then use an attention
mechanism to decide what is the “best” word to
focus on next. This is done in a similar way as thefeedforward attention proposed by Bahdanau et al.

(2)

(6)

Note that this is a rank-one update, as it can be written
in matrix notation as Sn = Sn−1 + tanh(affine(c̄n )) · αn> .
2We found the concatenation with hi in Eq. 6 beneficial to transfer input information directly to the output layer,
avoiding the need of flowing this information through thesketches.

In §5, we compare this to a BILSTM tagger, which
predicts according to pi = softmax(affine(hi )).
3.2

Full-State Model (NEF-F)

The full-state model differs from the single-statemodel in §3.1 by computing a full matrix for every sketch step, instead of a single vector. Namely,
instead of Eq. 4, it does the following sketch update for every word i ∈ [L]:sni = sn−1
+ αin · tanh(affine(cni )).
i(7)Note that the only difference is in replacing thesingle vector c̄n by the word-specific vector cni .
As a result, this is no longer a rank-one updateof the sketch matrix, but a full update. In the extreme case where the attention is peaked on a single word, the sketch update reduces to the same
form as in the single-state model (Eq. 5). However, the full-state model is generally more flexible
and allows processing words in parallel, since itallows different sketch updates for multiple words
receiving attention, instead of trying to force thosewords to receive the same update. We will see inthe experiments (§5) that this flexibility can be important in practice.
3.3

Computational Complexity

For both models, assuming that the ρ(z; β) transformation in Eq. 3 takes O(L) time to compute,the total runtime of Alg. 2 is O((N +K)L) (where
K is the number of tags), which becomes O(L2 ) if
K ≤ N = L. This is so because the input-sketch
representation, the attention mechanism, and thesketch generation step all have O(L) complexity,
and the final softmax layer requires O(KL) operations. This is the same runtime of the vanillaeasy-first algorithm, though the latter can be reduced to O(KLlogL) with caching and a heap, if
the scores in line 4 depend only on local sketches(Goldberg and Elhadad, 2010). By comparison, astandard BILSTM tagger has runtime O(KL).

4Constrained Softmax Attention

An important part of our models is their attention
component (line 7 in Alg. 2). To keep the “easyfirst” intuition, we would like the transformation ρin Eq. 3 to have a couple of properties:
1. Sparsity: being able to generate sparse distributions αn (ideally, peaked on a single word).

2. Evenness: over iterations, spreading attention
evenly over the words. Ideally, the cumulative
attention should satisfy β n ∈ [0, 1]L for everyn ∈ [N ] and β N = 1.
The standard choice for attention mechanisms isthe softmax transformation, αn = softmax(z n ).
However, the softmax does not satisfy either ofthe properties above. For the first requirement,
we could incorporate a “temperature” parameterin the softmax to push for more peaked distributions. However, this does not guarantee sparsity(only “hard attention” in the limit) and we foundit numerically unstable when plugged in Alg. 2.
For the second one, we could add a penalty before
the softmax transformation, αn = softmax(z n −λβ n−1 ), where λ ≥ 0 is a tunable hyperparameter. This strategy was found effective to prevent aword to receive too much attention, but it made themodel less accurate.
An alternative is the sparsemax transformation(Martins and Astudillo, 2016):
sparsemax(z) = argmin kα − zk2 .

(8)α∈∆L−1The sparsemax maintains most of the appealing
properties of the softmax (efficiency to evaluate
and backpropagate), and it is able to generate truly
sparse distributions. However, it still does not satisfy the “evenness” property.
Instead, we propose a novel constrained softmax transformation that satisfies both requirements. It resembles the standard softmax, but it
allows imposing hard constraints on the maximal
probability assigned to each word. Let us startby writing the (standard) softmax in the following
variational form (Amari and Nagaoka, 2001):
softmax(z) =argmin KL(αk softmax(z))α∈∆L−1=

argmin −H(α) − z > α,(9)α∈∆L−1

where KL and H denote the Kullback-Leibler divergence and the entropy, respectively. Based on
this observation, we define the constrained softmax transformation as follows:
csoftmax(z; u) =argmin −H(α) − z > αα∈∆L−1s.t. α ≤ u,(10)

where u ∈ RL is a vector of upper bounds. Note
that, if u ≥ 1, all constraints are loose and thisAlgorithm 3 Constrained Softmax Forward

Algorithm 4 Constrained Softmax Backprop

Input: z, u
Output: α = csoftmax(z; u)P
1: initialize s := 0, A := [L], Z := K
i=1 exp(zi )2: sort qi1 ≥ . . . ≥ qiL , where qi = exp(zi )/ui , ∀i ∈ [L]
3: for k = 1 to L do
4:
αik := exp(zik )(1 − s)/Z5:if αik > uik then6:
Z := Z − exp(zik )7:
αik := uik , s := s + uik , A := A \ {ik }8:
end if
9: end for

Input: z, u, dα (and cached α, A, s from Alg. 3)
Output: dz,
P du
1: m := i∈A αi dαi /(1 − s)2: for i ∈ [L] do
3:
if i ∈ A then4:dzi := αi (dαi − m), dui := 0
5:
else
6:
dzi := 0, dui := dαi − m
7:
end if
8: end for5
reduces to the standard softmax; on the contrary,
if u ∈ ∆L−1 , they are tight and we must have
α = u due to the normalization constraint. Thus,
we propose the following for Eq. 3:
αn = csoftmax(z n ; 1 − β n−1 ).
n

We evaluate our neural easy-first models in three
sequence tagging tasks: POS tagging, NER, andword quality estimation.
5.1

(11)

n−1

The constraints guarantee
β =β+ αn ≤ 1.
PN
N
>
>
n
Since 1 β = n=1 1 α = N , they also ensure that β N = 1, hence the “evenness” property is fully satisfied. Intuitively, each word getsa credit of one unit of attention that is consumed
during the execution of the algorithm. When thiscredit expires, all subsequent attention weights forthat word will be zero.
The next proposition shows how to evaluate theconstrained softmax and compute its gradients.
Proposition 1 Let α = csoftmax(z; u), and define the set A = {i ∈ [L] | αi < ui } of the constraints in Eq. 10 that are met strictly. Then:• Forward propagation. The solution of Eq. 10
can be written in closed form=
P as αi
exp(zi )i∈Amin{exp(zi )/Z, ui }, where Z = 1−P ui .
i∈A/

• Gradient backpropagation. Let L(θ) be a loss
function, dα = ∇α L(θ) be the output gradient,and dz = ∇z L(θ) and du = ∇u L(θ) be theinput gradients. Then, we have:dzi = 1(i ∈ A)αi (dαi − m)(12)

dui = 1(i ∈/ A)(dαi − m),

(13)

P
P
where m = ( i∈A αi dαi )/(1 − i∈A/ ui ).
Proof: See App. A (supplementary material).
Algs. 3–4 turn the results in Prop. 1 into concrete procedures for evaluating csoftmax and forbackpropagating its gradient. Their runtimes arerespectively O(LlogL) and O(L).

Experiments

Part-of-Speech Tagging

We ran POS tagging experiments in 12 languages
from the Universal Dependencies project v1.4
(Nivre et al., 2016), using the standard splits. The
datasets contain 17 universal tags.3
We implemented Alg. 2 in DyNet (Neubig et al.,2017), which we extended with the constrained
softmax operator (Algs. 3–4).4 We used 64dimensional word embeddings, initialized withpre-trained Polyglot vectors (Al-Rfou et al., 2013).
Apart from the words, we embedded prefix andsuffix character n-grams with n ≤ 4. We set
the affix embedding size to 50 and summed allthese embeddings; in the end, we obtained a 164dimensional representation for each word (words,
prefixes, and suffixes). We then fed these embeddings into a BILSTM (with 50 hidden units
in each direction) to obtain the encoder states[h1 , . . . , hL ] ∈ R100×L . The other hyperparameters were set as follows: we used a context size
w = 2, set the pre-attention size Dz and the sketch
size Ds to 50, and applied dropout with a probability of 0.2 after the embedding and BILSTM layers and before the final softmax output layer.5 We
ran 20 epochs of Adagrad to minimize the crossentropy loss, with a stepsize of 0.1, and gradient3
Our choice of languages covers 8 families: Romance(French, Portuguese, Spanish), Germanic (English, German),Slavic (Czech, Russian), Semitic (Arabic), Indo-Iranian(Hindi), Austronesian (Indonesian), Sino-Tibetan (Chinese),and Japonic (Japanese). For all languages, we used thedatasets that have the canonical language name, except for
Russian, where we used the (much larger) SynTagRus corpus. We prefered large datasets over small ones, to reducethe impact of overfitting in our analysis.
4
The code is available at https://github.com/
Unbabel/neural-easy-first.
5
These hyperparameters were tuned in the English development set, and kept fixed across languages.

Ara.

Chi.

Cze.

Ind.

Jap.

Por.

Rus.

Spa.

Avg.

Gillick et al. (2016)
Plank et al. (2016)†

–
98.91

–
–

98.44 94.00 95.17 92.34–
91.03
98.24 95.16 96.11 93.38 97.10 93.41

–
–

–
97.90

–
–

95.26
95.74

–
–

Linear (TurboTagger)
BILSTM
Vanilla Easy-First

95.18 91.38 98.07 94.43 96.48 91.92 95.98 93.12 89.35 96.63 97.32 95.44
95.60 92.73 98.46 94.94 96.37 92.97 96.80 93.79 92.72 97.01 97.83 95.27
95.62 92.78 98.50 94.78 96.35 92.91 96.81 93.68 92.68 97.12 97.93 95.31

94.88
95.39
95.42

NEF-S, csoftmax
NEF-F, softmax
NEF-F, sparsemax
NEF-F, csoftmax

95.63
95.61
95.14
95.53

95.42
95.43
93.88
95.47

†

92.87
92.92
92.86
92.99

98.50
98.47
97.75
98.53

Eng.

94.91
95.15
93.97
95.01

Fre.

96.41
96.52
91.79
96.70

Ger.

92.86
92.96
90.27
92.93

Hin.

96.79
96.75
89.40
96.98

93.65
93.67
93.48
93.81

92.93
92.57
92.61
92.72

96.57
97.12
95.27
97.04

97.91
97.92
96.32
97.94

95.42
95.41
95.36
95.42

Table 1: POS tagging accuracies. The average in the rightmost column is over the words of each treebank.
† Note that Gillick et al. (2016) and Plank et al. (2016) are not strictly comparable, since they use older
versions of the treebanks (UD1.1 and UD1.2, respectively).

Figure 2: Attention visualization for English POS tagging. From the left: constrained softmax, softmax,
sparsemax, vanilla. Rows correspond to attention vectors (high values in yellow, low ones in dark blue).
clipping of 5 (DyNet’s default). We excluded fromthe training set sentences longer than 50 words.
Table 1 compares several variants of our neural
easy-first system—the single-state model (NEFS), the full-state model (NEF-F), and the latterwith softmax, sparsemax, and csoftmax attention.
We used as many sketch steps as the number ofwords, N = L. As baselines, we used:• A feature-based linear model (TurboTagger,
Martins et al. (2013)).
• A BILSTM tagger identical to our system, but
without sketch steps (N = 0).
• A vanilla easy-first tagger (Alg. 1), using the argument of the softmax in Eq. 6 as the scoring
function. This uses the same sketch representations as the neural easy-first systems, but replaces the attention mechanism by “hard” attention placed on the highest scored word.
For comparison, we also show the accuracies reported by Gillick et al. (2016) for their byte-tospan system (trained separately on each language)
and by Plank et al. (2016) for their state-of-the-art
multi-task BILSTM tagger (these results are notfully comparable though, due to different treebank
versions).
Among the neural easy-first systems, we observe that NEF-F with csoftmax attention generally outperforms the others, but the differences arevery slight (excluding the sparsemax attention system, which performed substancially worse). Thissystem wins over the linear system for all languages but Spanish, and over the BILSTM baseline for 9 out of 12 languages (loses in Arabic andGerman, and ties in Japanese). Note, however, thatthe differences are small (95.47% against 95.39%,
averaged across treebanks). We conjecture that
this is due to the fact that the BILSTM already captures most of the relevant context in its encoder.
Our NEF-F system with csoftmax also wins overthe vanilla easy-first system for 10 out of 12 languages (arguably due to its ability to backpropagate the gradients through the soft attention mechanism), but the difference in the average score isagain small (95.47% against 95.42%).
Figure 2 depicts some patterns learned by the
NEF-F model with various attention types. With
the csoftmax, the model learns to move left andright, and the main verb “thought” is the mostprominent candidate for the easiest decision. In
fact, in 57% of the test sentences, the model focuses first on a verb. The “raindrop” appearance of the plot is due to the evenness propertyof csoftmax, which causes the attention over aword to increase gradually until the cumulative
attention is exhausted. This constrasts with thesoftmax attention (less diverse and non-sparse)
and the sparsemax (sparse, but not even). We show
for comparison the (hard) decisions made by thevanilla easy-first decoder.
5.2

Named Entity Recognition

Next, we applied our model to NER. We used theofficial datasets from the CoNLL 2002-3 sharedtasks (Tjong Kim Sang, 2002; Tjong Kim Sangand De Meulder, 2003), which tag names, locations, and organizations using a BIO scheme, andcover four languages (Dutch, English, German,
and Spanish). We made two experiments: one
using the exact same BILSTM and NEF models
with a standard softmax output layer, as in §5.1
(which does not guarantee valid segmentations),
and another one replacing the output softmax layer
by a sequential CRF layer, which requires learning O(K 2 ) additional parameters for pairs of consecutive tags (Huang et al., 2015; Lample et al.,2016). We used the same hyperparameters as in
the POS tagging experiments, except the dropout
probability, which was set to 0.3 (tuned on thevalidation set). For English, we used pre-trained
300-dimensional GloVe-840B embeddings (Pennington et al., 2014); for Spanish and German, weused the 64-dimensional word embeddings from
Lample et al. (2016); for Dutch we used the aforementioned Polyglot vectors. All embeddings are
fine-tuned during training. Since many words are
not entities, and those receive a default “outside”
tag, we expect that fewer sketch steps are necessary to achieve top performance.
Table 2 shows the results, which confirm thishypothesis. We compare the same BILSTM
baseline to our NEF-S and NEF-F models withcsoftmax attention (with and without the CRF output layer), varying the maximum number of sketch
steps. We also compare against the byte-to-spanmodel of Gillick et al. (2016) and the state-of-theart character-based LSTM-CRF system of Lample
et al. (2016).6 We can see that, for all languages,
6

The current state of the art on these datasets (Gillick
et al., 2016; Lample et al., 2016; Ma and Hovy, 2016) isachieved by more sophisticated systems with more param-

Dut.

Eng.

Ger.

Spa.

Gillick et al. (2016)
Lample et al. (2016)

78.08
81.74

84.57
90.94

72.08
78.76

81.83
85.75

BILSTM

76.56

85.74

70.05

77.00

NEF-S, N = 5
NEF-F, N = 5
NEF-F, N = 10
NEF-F, N = L

77.37
77.96
77.52
78.46

86.40
86.11
87.11
86.36

72.27
72.60
72.96
72.35

75.80
79.22
78.99
78.87

BILSTM-CRF

79.00

86.96

72.98

80.44

NEF-CRF-S, N = 5
NEF-CRF-F, N = 5
NEF-CRF-F, N = 10
NEF-CRF-F, N = L

78.89
80.03
79.86
80.29

88.33
88.01
87.51
87.58

72.37
73.45
73.63
74.75

80.21
81.00
80.35
80.71

Table 2: F1 scores for NER, computed by the
CoNLL 2002 evaluation script.
the NEF-CRF-F model with 5 steps is consistently
better than the BILSTM-CRF and, with the exception of English, the NEF-CRF-S model. The same
holds for the BILSTM and NEF-F models without
the CRF output layer. With the exception of German, increasing the number of steps did not makea big difference.
Figure 3 shows the attention distributions overthe sketch steps for an English sentence, for fullstate models trained with N ∈ {5, L}. The modelwith L sketch steps learned that it is easiest to focus on the beginning of a named entity, and thento move to the right to identify the full span. The
model with only 5 sketch steps learns to go straightto the point, placing most attention on the entity
words and ignoring most of the O -tokens.
5.3

Word-Level Quality Estimation

Finally, we evaluate our model’s performance on
word-level translation quality estimation. The
goal is to evaluate a translation system’s quality without access to reference translations (Blatz
et al., 2004; Specia et al., 2013). Given a sentencepair (a source sentence and its machine translated
sentence in a target language), a word-level system classifies each target word as OK or BAD. We
used the official English-German dataset from theWMT16 shared task (Bojar et al., 2016).
This task differs from the previous ones inwhich its input is a sentence pair and not a single
eters, mixing character and word-based models, sharing amodel across languages, or combining CRFs with convolutional and recurrent layers. We used simpler models in our
experiments since our goal is to assess how much the neural
easy-first systems can bring in addition to a BILSTM system,
rather than building a state-of-the-art system.

BILSTM
39.71

NEF-S
N =5 N =L

NEF-F
N =5 N =L

40.91

41.18

40.99

40.84

Table 3: F1 -MULT scores (product of F1 for OK
and BAD words) for word-level quality estimation,
computed by the official shared task script.

Figure 4: Example for word-level quality estimation. The source sentence is “To open the Actions
panel, from the main menu, choose Window > Actions.” BAD words are red (bold font), OK words
are green.
Figure 3: Attention visualization for English NER,
for 5 (top) and L (bottom) sketch steps. Words
tagged as B -* are marked in light blue, those with
I -* tags, in bold red, and with O -* tags, in green.

sentence. We replaced the affix embeddings by
the concatenation of the 64-dimensional embeddings of the target words with those of the aligned
source words (we used the alignments provided in
the shared task), yielding 128-dimensional representations. We used the same hyperparameters as
in the POS tagging task, except the dropout probability, set to 0.1. We followed prior work (Kreutzer
et al., 2015) and upweighted the BAD words in theloss function to make the model more pessimistic;
we used a weight of 5 (tuned in the validation set).
Table 3 shows the results. We see that all our
NEF-S and NEF-F models outperform the BILSTM, and that the NEF-F model with 5 sketch
steps achieved the best results.7
Figure 4 illustrates the attention over the target words for 5
sketches. We observe that the attention focusesearly in the areas predicted BAD and moves left
and right within these areas, not wasting attention
on the OK part of the sentence. This block-wise fo7

Our best system would rank third in the shared task, outof 13 submissions. The winner system, which achieved 49.52
F1 -MULT, was considerably more complex than ours, using
an ensemble of three neural networks with a linear system(Martins et al., 2016).

cus makes sense for quality estimation, since often
complete phrases are BAD.
5.4

Ablation Study

To better understand our proposed model, we carried out an ablation study for NER on the English
dataset. The following alternate configurations
were tried and compared against the NEF-CRF-F
model with csoftmax attention and 5 sketch steps:• A NEF-CRF-F model for which the final concatenation in Eq. 6 was removed, being replacedby pi = softmax(affine(sNi )). The goal was
to see if the sketches retain enough information
about the input to make a final prediction without requiring the states hi .
• A model for which the attention mechanism applied at each sketch step was replaced by a uniform distribution over the input words.
• A vanilla easy-first system (Alg. 1). Since thissystem can only focus on one word at the time
(unlike the models with soft attention), we tried
both N = 5 and N = L sketch steps.
• A left-to-right and right-to-left model, which replaces the attention mechanism by one of thesetwo prescribed orders.
Table 4 shows the results. As expected, the neural
easy-first system was the best performing one, although the difference with respect to the ablated

NEF-CRF-F, N = 5

88.01

NEF-CRF-F w/out concat, N = 5
Uniform Attention, N = 5
Vanilla EF + CRF, N = 5
Vanilla EF + CRF, N = L
Left-to-right + CRF, N = L
Right-to-left + CRF, N = L

87.47
87.46
87.17
87.46
87.57
87.53

Table 4: Ablation experiments. Reported are F1
scores for NER in the English test set.
systems is relatively small. Removing the concatenation in Eq. 6 is harmful, which suggests that
there is information about the input not retainedin the sketches. The uniform attention performs
surprisingly well, and so do the left-to-right andright-to-left models, but they are still about half apoint behind. The vanilla easy-first system has theworst performance with N = 5. This is due to thefact that the vanilla model is uncapable of processing words “in parallel” in the same sketch step, a
disadvantage with respect to the neural easy-firstmodels, which have this capability due to their soft
attention mechanisms (see the top image in Fig. 3).

6

Related Work

Vanilla easy-first decoders have been used in
POS tagging (Tsuruoka and Tsujii, 2005; Maet al., 2013), dependency parsing (Goldberg
and Elhadad, 2010), and coreference resolution(Stoyanov and Eisner, 2012), being related tocyclic dependency networks and guided learning(Toutanova et al., 2003; Shen et al., 2007). Morerecent works compute scores with a neural network (Socher et al., 2011; Clark and Manning,
2016; Kiperwasser and Goldberg, 2016), but they
still operate in a discrete space to pick the easiest actions (the non-differentiable argmax in line 6of Alg. 1). Generalizing this idea to “continuous”
operations is at the very core of our paper, allowing gradients to be fully backpropagated. In a different context, building differentiable computation
structures has also been addressed by Graves et al.
(2014); Grefenstette et al. (2015).
An important contribution of our paper is theconstrained softmax transformation. Others haveproposed alternatives to softmax attention, including the sparsemax (Martins and Astudillo, 2016)
and multi-focal attention (Globerson et al., 2016).
The latter computes a KL projection onto a budget polytope to focus on multiple words. Our constrained softmax also corresponds to a KL projec-tion, but (i) it involves box constraints instead ofa budget, (ii) it is normalized to 1, and (iii) we
also backpropagate the gradient over the constraint
variables. It also achieves sparsity (see the “raindrop” plots in Figures 2–4), and is suitable for sequentially computing attention distributions when
diversity is desired (e.g. soft 1-to-1 alignments).
Recently, Chorowski and Jaitly (2016) developed
an heuristic with a threshold on the total attention
as a “coverage criterion” (see their Eq. 11), however their heuristic is non-differentiable.
Our sketch generation step is similar in spirit to
the “deep recurrent attentive writer” (DRAW, Gregor et al. (2015)) which generates images by iteratively refining sketches with a recurrent neural network (RNN). However, our goal is very different:
instead of generating images, we generate vectorsthat lead to a final sequence tagging prediction.
Finally, the visualization provided in Figures 2–
4 brings up the question how to understand andrationalize predictions by neural network systems,
addressed by Lei et al. (2016). Their model, however, uses a form of stochastic attention and it does
not perform any iterative refinement like ours.

7

Conclusions

We introduced novel fully-differentiable easy-firsttaggers that learn to make predictions over sequences in an order that is adapted to the task at
hand. The decoder iteratively updates a sketchof the predictions by interacting with an attention
mechanism. To spread attention evenly through allwords, we introduced a new constrained softmax
transformation, along with an algorithm to backpropagate its gradients. Our neural-easy first decoder consistently outperformed a BILSTM on a
range of sequence tagging tasks.
A natural direction for future work is to go beyond sequence tagging (which we regard as a simple first step) toward other NLP structured prediction problems, such as sequence-to-sequence prediction. This requires replacing the sketch matrix
in Alg. 2 by a dynamic memory structure.

Acknowledgments
We thank the Unbabel research team and the reviewers for their comments. This work was supported by the Fundação para a Ciência e Tecnologia through contracts UID/EEA/50008/2013,
PTDC/EEI-SII/7092/2014 (LearnBig), and CMUPERI/TIC/0046/2014 (GoLocal).

References
Rami Al-Rfou, Bryan Perozzi, and Steven Skiena.
2013.
Polyglot: Distributed word representations for multilingual nlp.
arXiv preprint
arXiv:1307.1662.
S. Amari and H. Nagaoka. 2001. Methods of Information Geometry. Oxford University Press.
Daniel Andor, Chris Alberti, David Weiss, Aliaksei
Severyn, Alessandro Presta, Kuzman Ganchev, SlavPetrov, and Michael Collins. 2016. Globally normalized transition-based neural networks. In Proc.
of the Annual Meeting of the Association for Computational Linguistics, pages 2442–2452.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015. Neural Machine Translation by Jointly
Learning to Align and Translate. In International
Conference on Learning Representations.
Samy Bengio, Oriol Vinyals, Navdeep Jaitly, andNoam Shazeer. 2015. Scheduled sampling for sequence prediction with recurrent neural networks.
In Advances in Neural Information Processing Systems, pages 1171–1179.
John Blatz, Erin Fitzgerald, George Foster, Simona
Gandrabur, Cyril Goutte, Alex Kulesza, Alberto
Sanchis, and Nicola Ueffing. 2004. Confidence estimation for machine translation. In Proc. of the International Conference on Computational Linguistics,
page 315.

Association for Computational Linguistics, pages
334–343, Beijing, China. Association for Computational Linguistics.
Dan Gillick, Cliff Brunk, Oriol Vinyals, and Amarnag
Subramanya. 2016. Multilingual language processing from bytes. In Proc. of the Annual Meeting of
the North-American Chapter of the Association for
Computational Linguistics.
Amir Globerson, Nevena Lazic, Soumen Chakrabarti,
Amarnag Subramanya, Michael Ringgaard, and Fernando Pereira. 2016. Collective entity resolution
with multi-focal attention. In Proc. of the Annual
Meeting of the Association for Computational Linguistics.
Y. Goldberg and M. Elhadad. 2010. An efficient algorithm for easy-first non-directional dependency
parsing. In Proc. of Annual Conference of the North
American Chapter of the Association for Computational Linguistics, pages 742–750.
Alex Graves, Santiago Fernández, and Jürgen Schmidhuber. 2005. Bidirectional lstm networks for improved phoneme classification and recognition. In
International Conference on Artificial Neural Networks, pages 799–804. Springer.
Alex Graves, Greg Wayne, and Ivo Danihelka.
2014. Neural Turing Machines. arXiv preprint
arXiv:1410.5401.

Ondřej Bojar, Rajen Chatterjee, Christian Federmann,
Yvette Graham, Barry Haddow, Matthias Huck,
Antonio Jimeno Yepes, Philipp Koehn, Varvara
Logacheva, Christof Monz, Matteo Negri, Aurelie Neveol, Mariana Neves, Martin Popel, Matt
Post, Raphael Rubino, Carolina Scarton, Lucia Specia, Marco Turchi, Karin Verspoor, and Marcos
Zampieri. 2016. Findings of the 2016 conferenceon machine translation. In Proceedings of the First
Conference on Machine Translation, pages 131–
198.

Edward Grefenstette, Karl Moritz Hermann, Mustafa
Suleyman, and Phil Blunsom. 2015. Learning toTransduce with Unbounded Memory. In Advancesin Neural Information Processing Systems, pages
1819–1827.

Jan Chorowski and Navdeep Jaitly. 2016. Towards
better decoding and language model integrationin sequence to sequence models. arXiv preprint
arXiv:1612.02695.

Sepp Hochreiter and Jürgen Schmidhuber. 1997.
Long short-term memory. Neural computation,
9(8):1735–1780.

Kevin Clark and Christopher D Manning. 2016. Improving coreference resolution by learning entitylevel distributed representations. In Proc. of the Annual Meeting of the Association for Computational
Linguistics.
H. Daumé, J. Langford, and D. Marcu. 2009. Searchbased structured prediction. Machine learning,
75(3):297–325.
Chris Dyer, Miguel Ballesteros, Wang Ling, Austin
Matthews, and Noah A. Smith. 2015. Transitionbased dependency parsing with stack long shortterm memory. In Proc. of the Annual Meeting of the

Karol Gregor, Ivo Danihelka, Alex Graves, Danilo
Rezende, and Daan Wierstra. 2015. Draw: A recurrent neural network for image generation. In Proc.
of the International Conference on Machine Learning, pages 1462–1471.

Zhiheng Huang, Wei Xu, and Kai Yu. 2015. Bidirectional lstm-crf models for sequence tagging. arXiv
preprint arXiv:1508.01991.
Eliyahu Kiperwasser and Yoav Goldberg. 2016. Easyfirst dependency parsing with hierarchical tree lstms.
arXiv preprint arXiv:1603.00375.
Julia Kreutzer, Shigehiko Schamoni, and Stefan Riezler. 2015.
Quality estimation from scratch(quetch): Deep learning for word-level translation
quality estimation. In Proceedings of the TenthWorkshop on Statistical Machine Translation, pages
316–322.

Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016.
Neural architectures for named entity recognition.
In Proc. of the Annual Meeting of the NorthAmerican Chapter of the Association for Computational Linguistics.
Tao Lei, Regina Barzilay, and Tommi Jaakkola. 2016.
Rationalizing neural predictions. In Proc. of Empirical Methods for Natural Language Processing.
Ji Ma, Tong Xiao, and Nan Yang. 2013. Easy-first pos
tagging and dependency parsing with beam search.
In In Proceedings of the 51st Annual Meeting of the
Association for Computational Linguistics (Volume
2: Short Papers.
Xuezhe Ma and Eduard Hovy. 2016. End-to-end sequence labeling via bi-directional lstm-cnns-crf. In
Proc. of the Annual Meeting of the Association for
Computational Linguistics.
André F. T Martins, Miguel B. Almeida, and Noah A.
Smith. 2013. Turning on the turbo: Fast third-ordernon-projective turbo parsers. In Proc. of the Annual
Meeting of the Association for Computational Linguistics.
André F. T. Martins and Ramón Astudillo. 2016. From
Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification. In Proc. of theInternational Conference on Machine Learning.
André F. T. Martins, Ramón Astudillo, Chris Hokamp,
and Fábio Kepler. 2016. Unbabel’s participation in
the wmt16 word-level translation quality estimation
shared task. In Proceedings of the First Conference
on Machine Translation.
Graham Neubig, Chris Dyer, Yoav Goldberg, Austin
Matthews, Waleed Ammar, Antonios Anastasopoulos, Miguel Ballesteros, David Chiang, Daniel
Clothiaux, Trevor Cohn, et al. 2017. Dynet: The
dynamic neural network toolkit. arXiv preprint
arXiv:1701.03980.
Joakim Nivre, Željko Agić, Lars Ahrenberg, Maria Jesus Aranzabe, Masayuki Asahara, Aitziber Atutxa,
Miguel Ballesteros, John Bauer, Kepa Bengoetxea, Yevgeni Berzak, Riyaz Ahmad Bhat, Eckhard Bick, Carl Börstell, Cristina Bosco, Gosse
Bouma, Sam Bowman, Gülşen Cebirolu Eryiit,
Giuseppe G. A. Celano, Fabricio Chalub, ÇarÇöltekin, Miriam Connor, Elizabeth Davidson,
Marie-Catherine de Marneffe, Arantza Diaz deIlarraza, Kaja Dobrovoljc, Timothy Dozat, Kira
Droganova, Puneet Dwivedi, Marhaba Eli, Tomaž
Erjavec, Richárd Farkas, Jennifer Foster, Claudia
Freitas, Katarı́na Gajdošová, Daniel Galbraith, Marcos Garcia, Moa Gärdenfors, Sebastian Garza, Filip
Ginter, Iakes Goenaga, Koldo Gojenola, MemduhGökrmak, Yoav Goldberg, Xavier Gómez Guinovart, Berta Gonzáles Saavedra, Matias Grioni, Normunds Grūzītis, Bruno Guillaume, Jan Hajič, Linh
Hà M, Dag Haug, Barbora Hladká, Radu Ion,

Elena Irimia, Anders Johannsen, Fredrik Jørgensen,
Hüner Kaşkara, Hiroshi Kanayama, Jenna Kanerva,
Boris Katz, Jessica Kenney, Natalia Kotsyba, Simon Krek, Veronika Laippala, Lucia Lam, Phng
Lê Hng, Alessandro Lenci, Nikola Ljubešić, Olga
Lyashevskaya, Teresa Lynn, Aibek Makazhanov,Christopher Manning, Cătălina Mărănduc, David
Mareček, Héctor Martı́nez Alonso, André Martins,
Jan Mašek, Yuji Matsumoto, Ryan McDonald, Anna
Missilä, Verginica Mititelu, Yusuke Miyao, Simonetta Montemagni, Keiko Sophie Mori, Shunsuke
Mori, Bohdan Moskalevskyi, Kadri Muischnek,
Nina Mustafina, Kaili Müürisep, Lng Nguyn Th,
Huyn Nguyn Th Minh, Vitaly Nikolaev, Hanna
Nurmi, Petya Osenova, Robert Östling, Lilja Øvrelid, Valeria Paiva, Elena Pascual, Marco Passarotti,
Cenel-Augusto Perez, Slav Petrov, Jussi Piitulainen,
Barbara Plank, Martin Popel, Lauma Pretkalnia,
Prokopis Prokopidis, Tiina Puolakainen, Sampo
Pyysalo, Alexandre Rademaker, Loganathan Ramasamy, Livy Real, Laura Rituma, Rudolf Rosa,
Shadi Saleh, Baiba Saulīte, Sebastian Schuster,Wolfgang Seeker, Mojgan Seraji, Lena Shakurova,
Mo Shen, Natalia Silveira, Maria Simi, Radu
Simionescu, Katalin Simkó, Mária Šimková, Kiril
Simov, Aaron Smith, Carolyn Spadine, Alane Suhr,
Umut Sulubacak, Zsolt Szántó, Takaaki Tanaka,
Reut Tsarfaty, Francis Tyers, Sumire Uematsu,
Larraitz Uria, Gertjan van Noord, Viktor Varga,
Veronika Vincze, Lars Wallin, Jing Xian Wang,
Jonathan North Washington, Mats Wirén, ZdeněkŽabokrtský, Amir Zeldes, Daniel Zeman, andHanzhi Zhu. 2016. Universal dependencies 1.4.
LINDAT/CLARIN digital library at the Institute ofFormal and Applied Linguistics, Charles University
in Prague.
Jeffrey Pennington, Richard Socher, and Christopher D
Manning. 2014. Glove: Global Vectors for Word
Representation.
Proceedings of the Empiricial
Methods in Natural Language Processing (EMNLP
2014), 12:1532–1543.
Barbara Plank, Anders Søgaard, and Yoav Goldberg.
2016. Multilingual part-of-speech tagging withbidirectional long short-term memory models andauxiliary loss. In Proc. of the Annual Meeting of
the Association for Computational Linguistics (shortpapers).
Stéphane Ross, Geoffrey J Gordon, and Drew Bagnell.
2011. A reduction of imitation learning and structured prediction to no-regret online learning. In AISTATS, volume 1, page 6.
Libin Shen, Giorgio Satta, and Aravind Joshi. 2007.
Guided learning for bidirectional sequence classification. In ACL, volume 7, pages 760–767.
Richard Socher, Cliff C Lin, Chris Manning, and Andrew Y Ng. 2011. Parsing natural scenes and natural language with recursive neural networks. In Proceedings of the 28th international conference on machine learning (ICML-11), pages 129–136.

Lucia Specia, Kashif Shah, Jose G.C. de Souza, andTrevor Cohn. 2013. QuEst - a translation quality
estimation framework. In Proc. of the Annual Meeting of the Association for Computational Linguistics: System Demonstrations, pages 79–84.
Veselin Stoyanov and Jason Eisner. 2012. Easy-first
coreference resolution. In COLING, pages 2519–
2534.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014.
Sequence to sequence learning with neural networks. In Advances in Neural Information Processing Systems, pages 3104–3112.
E. F. Tjong Kim Sang and F. De Meulder. 2003. Introduction to the CoNLL-2003 shared task: Languageindependent named entity recognition. In Proc.
of International Conference on Natural Language
Learning.
E.F. Tjong Kim Sang. 2002. Introduction to the
CoNLL-2002 shared task: Language-independent
named entity recognition. In Proc. of International
Conference on Natural Language Learning.
Kristina Toutanova, Dan Klein, Christopher D Manning, and Yoram Singer. 2003. Feature-rich part-ofspeech tagging with a cyclic dependency network.
In Proceedings of the 2003 Conference of the North
American Chapter of the Association for Computational Linguistics on Human Language TechnologyVolume 1, pages 173–180. Association for Computational Linguistics.
Yoshimasa Tsuruoka and Jun’ichi Tsujii. 2005. Bidirectional inference with the easiest-first strategy for
tagging sequence data. In Proceedings of the conference on human language technology and empiricalmethods in natural language processing, pages 467–
474. Association for Computational Linguistics.

A

Proof of Proposition 1

We provide here a detailed proof of Proposition 1.
A.1

Forward Propagation

The optimization problem is−H(α) − z > α
 >
1 α=1
s.t.
0 ≤ α ≤ u.

csoftmax(z, u) = argmin

The Lagrangian function is:L(α, λ, µ, ν) = −H(α) − z > α + λ(1> α − 1)−µ> α + ν > (α − u).

(14)

To obtain the solution, we invoke the Karush-Kuhn-Tucker conditions. From the stationarity condition,
we have 0 = log(α) + 1 − z + λ1 − µ + ν, which due to the primal feasibility condition implies thatthe solution is of the form:
α = exp(z + µ − ν)/Z,(15)
where Z is a normalization constant. From the complementarity slackness condition, we have that 0 <αi < ui implies that µi = νi = 0 and therefore αi = exp(zi )/Z. On the other hand, νi > 0 implies
αi = ui . Hence the solution can be written as αi = min{exp(zi )/Z, ui }, where Z is determined suchthat the distribution normalizes:P
exp(zi )P
Z = i∈A,(16)
1 − i∈A/ ui
with A = {i ∈ [L] | αi < ui }.
A.2

Gradient Backpropagation

We now turn to the problem of backpropagating the gradients through the constrained softmax transfor∂αiimation. For that, we need to compute its Jacobian matrix, i.e., the derivatives ∂α∂zj and ∂uj for i, j ∈ [L].
Let us first express α as(
exp(zi )(1−s)
P, i∈Aj∈A exp(zj )
αi =
(17)
ui ,
i∈
/ A,
P
/ A). To compute thewhere s = j ∈A
/ uj . Note that we have ∂s/∂zj = 0, ∀j, and ∂s/∂uj = 1(j ∈entries of the Jacobian matrix, we need to consider several cases.
Case 1: i ∈ A. In this case, the evaluation of Eq. 17 goes through the first branch. Let us first computethe derivative with respect to uj . Two things can happen: if j ∈ A, then s does not depend on uj , hence∂αi/ A, we have
∂uj = 0. Else, if j ∈∂s−exp(zi ) ∂u∂αi
j=P
= −αi /(1 − s).
∂uj
exp(z
)
k
k∈A

Now let us compute the derivative with respect to zj . Three things can happen: if j ∈ A and i 6= j, we
have
∂αi
∂zj

−exp(zi )exp(zj )(1 − s)2Pk∈A exp(zk )= −αi αj /(1 − s).

=

(18)

If j ∈ A and i = j, we have
∂αi∂zi

= (1 − s) ×P
exp(zi ) k∈A exp(zk ) − exp(zi )22
Pk∈A exp(zk )= αi − αi2 /(1 − s).

(19)iFinally, if j ∈/ A, we have ∂α∂zj = 0.

Case 2: i ∈/ A. In this case, the evaluation of Eq. 17 goes through the second branch, which means∂αithat ∂zj = 0, always. Let us now compute the derivative with respect to uj . This derivative is always∂αizero unless i = j, in which case ∂u= 1.
j

To sum up, we have:
∂αi
=
∂zj
and



αα

i j
1(i = j)αi − 1−s, if i, j ∈ A
0,otherwise,αi, if i ∈ A, j ∈/A − 1−s∂αi=
1,if i, j ∈/ A, i = j∂uj0,otherwise.

(20)

(21)

Therefore, we obtain:
dzj

=

X ∂αi
i

∂zj

dαi

P


αj i∈A αi dαi= 1(j ∈ A) αj dαj −1−s= 1(j ∈ A)αj (dαj − m),

(22)

and
duj

=

X ∂αi
i

∂uj

dαi


P

= 1(j ∈/ A) dαj −= 1(j ∈/ A)(dαj − m),P

where m =i∈A αi dαi

1−s.

i∈A αi dαi



1−s
(23)