Neural Machine Translation via Binary Code Prediction
Yusuke Oda†
Philip Arthur†
Graham Neubig‡†
Koichiro Yoshino†§
Satoshi Nakamura††
Nara Institute of Science and Technoloty, 8916-5 Takayama-cho, Ikoma, Nara 630-0192, Japan‡
Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213, USA§
Japan Science and Technology Agency, 4-1-8 Hon-machi, Kawaguchi, Saitama 332-0012, Japan{oda.yusuke.on9, philip.arthur.om0}@is.naist.jp, gneubig@cs.cmu.edu,{koichiro, s-nakamura}@is.naist.jp
Abstract
In this paper, we propose a new method
for calculating the output layer in neuralmachine translation systems. The method
is based on predicting a binary code foreach word and can reduce computationtime/memory requirements of the output
layer to be logarithmic in vocabulary sizein the best case. In addition, we also introduce two advanced approaches to improve
the robustness of the proposed model: using error-correcting codes and combining
softmax and binary codes. Experimentson two English ↔ Japanese bidirectionaltranslation tasks show proposed models
achieve BLEU scores that approach thesoftmax, while reducing memory usage tothe order of less than 1/10 and improving
decoding speed on CPUs by x5 to x10.

1Figure 1: Encoder-decoder-attention NMT modeland computation amount of the output layer.
Memory efficiency: The method should not require large memory to store the parametersand calculated vectors to maintain scalability
in resource-constrained environments.

Introduction

Time efficiency: The method should be able totrain the parameters efficiently, and possible
to perform decoding efficiently with choosing the candidate words from the full probability distribution. In particular, the methodshould be performed fast on general CPUs tosuppress physical costs of computational resources for actual production systems.

When handling broad or open domains, machinetranslation systems usually have to handle a large
vocabulary as their inputs and outputs. This is particularly a problem in neural machine translation(NMT) models (Sutskever et al., 2014), such as
the attention-based models (Bahdanau et al., 2014;
Luong et al., 2015) shown in Figure 1. In thesemodels, the output layer is required to generate a
specific word from an internal vector, and a large
vocabulary size tends to require a large amount ofcomputation to predict each of the candidate word
probabilities.
Because this is a significant problem for neurallanguage and translation models, there are a number of methods proposed to resolve this problem,
which we detail in Section 2.2. However, noneof these previous methods simultaneously satisfies
the following desiderata, all of which, we argue,
are desirable for practical use in NMT systems:

Compatibility with parallel computation: Itshould be easy for the method to be minibatched and optimized to run efficiently on
GPUs, which are essential for training large
NMT models.
In this paper, we propose a method that satisfies all of these conditions: requires significantly
less memory, fast, and is easy to implement minibatched on GPUs. The method works by not predicting a softmax over the entire output vocab850

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 850–860
Vancouver, Canada, July 30 - August 4, 2017. c 2017 Association for Computational Linguistics
https://doi.org/10.18653/v1/P17-1079

RV ×H and βu ∈ RV are trainable parameters and
H is the total size of hidden layers directly connected to the output layer.
According to Equation (4), this model clearlyrequires time/space computation in proportion toO(HV ), and the actual load of the computation of
the output layer is directly affected by the size of
vocabulary V , which is typically set around tensof thousands (Sutskever et al., 2014).

ulary, but instead by encoding each vocabulary
word as a vector of binary variables, then independently predicting the bits of this binary representation. In order to represent a vocabulary size of
2n , the binary representation need only be at leastn bits long, and thus the amount of computationand size of parameters required to select an output
word is only O(log V ) in the size of the vocabulary V , a great reduction from the standard linear
increase of O(V ) seen in the original softmax.
While this idea is simple and intuitive, we foundthat it alone was not enough to achieve competitive
accuracy with real NMT models. Thus we maketwo improvements: First, we propose a hybrid
model, where the high frequency words are predicted by a standard softmax, and low frequency
words are predicted by the proposed binary codes
separately. Second, we propose the use of convolutional error correcting codes with Viterbi decoding (Viterbi, 1967), which add redundancy tothe binary representation, and even in the face of
localized mistakes in the calculation of the representation, are able to recover the correct word.
In experiments on two translation tasks, we findthat the proposed hybrid method with error correction is able to achieve results that are competitive
with standard softmax-based models while reducing the output layer to a fraction of its original size.

2

Problem Description and Prior Work

2.1

Formulation and Standard Softmax

2.2

Several previous works have proposed methods toreduce computation in the output layer. The hierarchical softmax (Morin and Bengio, 2005) predicts each word based on binary decision and reduces computation time to O(H log V ). However,this method still requires O(HV ) space for theparameters, and requires calculation much more
complicated than the standard softmax, particularly at test time.
The differentiated softmax (Chen et al., 2016)
divides words into clusters, and predicts words using separate part of the hidden layer for each wordclusters. This method make the conversion matrixof the output layer sparser than a fully-connected
softmax, and can reduce time/space computation
amount by ignoring zero part of the matrix. However, this method restricts the usage of hidden
layer, and the size of the matrix is still in proportion to V .
Sampling-based approximations (Mnih andTeh, 2012; Mikolov et al., 2013) to the denominator of the softmax have also been proposed to reduce calculation at training. However, these methods are basically not able to be applied at test time,
still require heavy computation like the standard
softmax.
Vocabulary selection approaches (Mi et al.,2016; L’Hostis et al., 2016) can also reduce thevocabulary size at testing, but these methods abandon full search over the target space and thequality of picked vocabularies directly affects thetranslation quality.
Other methods using characters (Ling et al.,2015) or subwords (Sennrich et al., 2016; Chitnis
and DeNero, 2015) can be applied to suppress the
vocabulary size, but these methods also make forlonger sequences, and thus are not a direct solution
to problems of computational efficiency.

Most of current NMT models use one-hot representations to represent the words in the output vocabulary – each word w is represented by a uniquesparse vector eid(w) ∈ RV , in which only one element at the position corresponding to the word ID
id(w) ∈ {x ∈ N | 1 ≤ x ≤ V } is 1, while others are 0. V represents the vocabulary size of thetarget language. NMT models optimize network
parameters by treating the one-hot representationeid(w) as the true probability distribution, and minimizing the cross entropy between it and the softmax probability v:
LH (v, id(w)) := H(eid(w) , v),=(1)

log sum exp u − uid(w) , (2)v := exp u/ sum exp u,(3)u := Whu h + βu ,(4)Prior Work on Suppressing Complexity
of NMT Models

where sum x represents the sum of all elements
in x, xi represents the i-th element of x, Whu ∈851

current hidden values h by logistic regressions:q(h)=σ(Whq h + βq ),σ(x) := 1/(1 + exp(−x)),

(6)
(7)

where Whq ∈ RB×H and βq ∈ RB are trainable parameters. When we assume that each qi
is the probability that “the i-th bit becomes 1,” thejoint probability of generating word w can be represented as:
Pr(b(w)|q(h)) :=

B
Y
i=1

Binary Code Prediction Models

3.1

Representing Words using Bit Arrays

Figure 2(a) shows the conventional softmax prediction, and Figure 2(b) shows the binary code
prediction model proposed in this study. Unlike
the conventional softmax, the proposed method
predicts each output word indirectly using dense
bit arrays that correspond to each word. Letb(w) := [b1 (w), b2 (w), · · · , bB (w)] ∈ {0, 1}B be
the target bit array obtained for word w, where
each bi (w) ∈ {0, 1} is an independent binary
function given w, and B is the number of bits inwhole array. For convenience, we introduce someconstraints on b. First, a word w is mapped to only
one bit array b(w). Second, all unique words canbe discriminated by b, i.e., all bit arrays satisfy
that:1
id(w) 6= id(w0 ) ⇒ b(w) 6= b(w0 ).

(8)

where x̄ := 1 − x. We can easily obtain the
maximum-probability bit array from q by simply
assuming the i-th bit is 1 if qi ≥ 1/2, or 0 otherwise. However, this calculation may generate invalid bit arrays which do not correspond to actual
words according to the mapping between words
and bit arrays. For now, we simply assume thatw = UNK (unknown) when such bit arrays are obtained, and discuss alternatives later in Section 3.5.
The constraints described here are very general
requirements for bit arrays, which still allows us tochoose between a wide variety of mapping functions. However, designing the most appropriate
mapping method for NMT models is not a trivial problem. In this study, we use a simple mapping method described in Algorithm 1, which was
empirically effective in preliminary experiments.2
Here, V is the set of V target words including 3
extra markers: UNK, BOS (begin-of-sentence), andEOS (end-of-sentence), and rank(w) ∈ N>0 is
the rank of the word according to their frequencies in the training corpus. Algorithm 1 is oneof the minimal mapping methods (i.e., satisfying
B = dlog2 V e), and generated bit arrays have thecharacteristics that their higher bits roughly represents the frequency of corresponding words (e.g.,
if w is frequently appeared in the training corpus,
higher bits in b(w) tend to become 0).

Figure 2: Designs of output layers.

3bi qi + b̄i q̄i ,(5)Third, multiple bit arrays can be mapped to thesame word as described in Section 3.5. By
considering second constraint, we can also constrain B ≥ dlog2 V e, because b should haveat least V unique representations to distinguisheach word. The output layer of the network independently predicts B probability values q :=[q1 (h), q2 (h), · · · , qB (h)] ∈ [0, 1]B using the

3.2

Loss Functions

For learning correct binary representations, we canuse any loss functions that is (sub-)differentiable
and satisfies a constraint that:= L , if q = b,
LB (q, b)(9)≥ L , otherwise,2

Other methods examined included random codes, Huffman codes (Huffman, 1952) and Brown clustering (Brown
et al., 1992) with zero-padding to adjust code lengths, andsome original allocation methods based on the word2vec embeddings (Mikolov et al., 2013).

1

We designed this injective condition using the id(·) function to ignore task-specific sensitivities between different
word surfaces (e.g. cases, ligatures, etc.).

852

Algorithm 1 Mapping words to bit arrays.

strong constraints for guaranteeing independence
between all bits: all nodes in the same level of thehierarchy share their parameters, and all levels of
the hierarchy are predicted independently of eachother. By these constraints, all bits in b can becalculated in parallel. This is particularly important because it makes the model conducive to being calculated on parallel computation backends
such as GPUs.
However, the binary code prediction model also
introduces problems of robustness due to thesestrong constraints. As the experimental results
show, the simplest prediction model which directly maps words into bit arrays seriously decreases translation quality. In Sections 3.4 and 3.5,
we introduce two additional techniques to prevent
reductions of translation quality and improve robustness of the binary code prediction model.

Require: w ∈ V
Ensure:b ∈ {0, 1}B = Bit array representing w
0,
if w = UNK1,
if w = BOSx :=if w = EOS 2,
2 + rank(w), otherwise
bi := bx/2i−1 c mod 2b ← [b1 , b2 , · · · , bB ]where L is the minimum value of the loss function which typically does not affect the gradient descent methods. For example, the squareddistance:
LB (q, b) :=

B
X
i=1

(qi − bi )2 ,(10)

or the cross-entropy:
LB (q, b) := −

B
X
i=1


bi log qi + b̄i log q̄i , (11)3.4

According to the Zipf’s law (Zipf, 1949), the distribution of word appearances in an actual corpus is biased to a small subset of the vocabulary. As a result, the proposed model mostly
learns characteristics for frequent words and cannot obtain enough opportunities to learn for rarewords. To alleviate this problem, we introduce a
hybrid model using both softmax prediction andbinary code prediction as shown in Figure 2(c).
In this model, the output layer calculates a standard softmax for the N − 1 most frequent words
and an OTHER marker which indicates all rarewords. When the softmax layer predicts OTHER,
then the binary code layer is used to predict the
representation of rare words. In this case, the actual probability of generating a particular word canbe separated into two equations according to thefrequency of words:

are candidates for the loss function. We also
examined both loss functions in the preliminary
experiments, and in this paper, we only used
the squared-distance function (Equation (10)), because this function achieved higher translation accuracies than Equation (11).3
3.3

Hybrid Softmax/Binary Model

Efficiency of the Binary Code Prediction

The computational complexity for the parameters Whq and βq is O(HB). This is equalto O(H log V ) when using a minimal mapping
method like that shown in Algorithm 1, and is significantly smaller than O(HV ) when using standard softmax prediction. For example, if we choseV = 65536 = 216 and use Algorithm 1’s mapping
method, then B = 16 and total amount of computation in the output layer could be suppressed to
1/4096 of its original size.
On a different note, the binary code prediction
model proposed in this study shares some ideas
with the hierarchical softmax (Morin and Bengio,
2005) approach. Actually, when we used a binarytree based mapping function for b, our model canbe interpreted as the hierarchical softmax with two

Pr(w|h) ' 0vid(w) ,if id(w) < N,
(12)
0 · π(w, h), otherwise,vNv 0 := exp u0 / sum exp u0 ,0u:= Whu0 h + βu0 ,π(w, h) := Pr(b(w)|q(h)),

3
In terms of learning probabilistic models, we should remind that using Eq. (10) is an approximation of Eq. (11). The
output bit scores trained by Eq. (10) do not represent actual
word perplexities, and this characteristics imposes some practical problems when comparing multiple hypotheses (e.g.,reranking, beam search, etc.). We could ignore this problem
in this paper because we only evaluated the one-best resultsin experiments.

(13)
(14)
(15)

where Whu0 ∈ RN ×H and βu0 ∈ RN are trainable
parameters, and id(w) assumes that the value corresponds to the rank of frequency of each word.
We also define the loss function for the hybrid853

Figure 3: Example of the classification problem
using redundant bit array mapping.

Figure 4: Training and generation processes witherror-correcting code.

model using both softmax and binary code losses:lH (id(w)), if id(w) < N,
L :=
(16)
lH (N ) + lB , otherwise,lH (i) := λH LH (v 0 , i),lB := λB LB (q, b),estimating the nearest centroid bit array according to the Hamming distance between each centroid and the predicted bit array. This approach
can predict correct words as long as the predicted
bit arrays are in the set of neighbors for the correct centroid (gray regions in the Figure 3), i.e.,
up to a 1-bit error in the predicted bits can be corrected. This ability to be robust to errors is a central idea behind error-correcting codes (Shannon,
1948). In general, an error-correcting code has theability to correct up to b(d − 1)/2c bit errors when
all centroids differ d bits from each other (Golay,1949). d is known as the free distance determinedby the design of error-correcting codes. Errorcorrecting codes have been examined in some previous work on multi-class classification tasks, andhave reported advantages from the raw classification (Dietterich and Bakiri, 1995; Klautau et al.,
2003; Liu, 2006; Kouzani and Nasireding, 2009;
Kouzani, 2010; Ferng and Lin, 2011, 2013). In
this study, we applied an error-correcting algorithm to the bit array obtained from Algorithm 1
to improve robustness of the output layer in an
NMT system. A challenge in this study is trying a large classification (#classes > 10,000) witherror-correction, unlike previous studies focusedon solving comparatively small tasks (#classes <100). And this study also tries to solve a generation task unlike previous studies. As shown in theexperiments, we found that this approach is highly
effective in these tasks.
Figure 4 (a) and (b) illustrate the training andgeneration processes for the model with errorcorrecting codes. In the training, we first convert the original bit arrays b(w) to a center bit
array b0 in the space of error-correcting code:0b0 (b) := [b01 (b), b02 (b), · · · , b0B 0 (b)] ∈ {0, 1}B ,where B 0 (B) ≥ B is the number of bits in theerror-correcting code. The NMT model learns its

(17)

(18)

where λH and λB are hyper-parameters to determine strength of both softmax/binary code losses.
These also can be adjusted according to the training data, but in this study, we only used λH =λB = 1 for simplicity.
The computational complexity of the hybrid
model is O(H(N + log V )), which is larger thanthe original binary code model O(H log V ). However, N can be chosen as N  V because the softmax prediction is only required for a few frequentwords. As a result, we can control the actual computation for the hybrid model to be much smaller
than the standard softmax complexity O(HV ),The idea of separated prediction of frequentwords and rare words comes from the differentiated softmax (Chen et al., 2016) approach. However, our output layer can be configured as a fullyconnected network, unlike the differentiated softmax, because the actual size of the output layer isstill small after applying the hybrid model.
3.5

Applying Error-correcting Codes

The 2 methods proposed in previous sections impose constraints for all bits in q, and the value ofeach bit must be estimated correctly for the correct word to be chosen. As a result, these models
may generate incorrect words due to even a single bit error. This problem is the result of dense
mapping between words and bit arrays, and can
be avoided by creating redundancy in the bit array. Figure 3 shows a simple example of how thisidea works when discriminating 2 words using 3
bits. In this case, the actual words are obtained by854

Algorithm 2 Encoding into a convolutional code.
Require: b ∈ {0, 1}BEnsure: b0∈{0, 1}2(B+6)=
Redundant bit arraybt , if 1 ≤ t ≤ B
x[t] :=
0, otherwise1
yt := x[t − 6 .. t] · [1001111] mod 2
yt2 := x[t − 6 .. t] · [1101101] mod 2
12
b0 ← [y11 , y12 , y21 , y22 , · · · , yB+6
, yB+6]

Algorithm 3 Decoding from a convolutional code.
Require: q ∈ (0, 1)2(B+6)
Ensure: q̃ ∈ {0, 1}B = Restored bit arrayg(q, b) := b log q + (1 − b) log(1 − q)0,
if s = [000000]
φ0 [s | s ∈ {0, 1}6 ] ←−∞, otherwise
for t = 1 → B + 6 dofor scur ∈ {0, 1}6 do
sprev (x) := [x] ◦ scur [1 .. 5]o1 (x) := ([x] ◦ scur ) · [1001111] mod 2
o2 (x) := ([x] ◦ scur ) · [1101101] mod 2
g 0 (x) := g(q2t−1 , o1 (x)) + g(q2t , o2 (x))φ0 (x) := φt−1 [sprev (x)] + g 0 (x)x̂ ← arg maxx∈{0,1} φ0 (x)rt [scur ] ← sprev (x̂)φt [scur ] ← φ0 (x̂)
end forend fors0 ← [000000]
for t = B → 1 dos0 ← rt+6 [s0 ]q̃t ← s01
end forq̃ ← [q̃1 , q̃2 , · · · , q̃B ]parameters based on the loss between predictedprobabilities q and b0 . Note that typical errorcorrecting codes satisfy O(B 0 /B) = O(1), andthis characteristic efficiently suppresses the increase of actual computation cost in the output
layer due to the application of the error-correcting
code. In the generation of actual words, the decoding method of the error-correcting code converts
the redundant predicted bits q into a dense representation q̃ := [q̃1 (q), q̃2 (q), · · · , q̃B (q)], anduses q̃ as the bits to restore the word, as is done in
the method described in the previous sections.
It should be noted that the method for performing error correction directly affects the quality of
the whole NMT model. For example, the mapping shown in Figure 3 has only 3 bits and it isclear that these bits represent exactly the same information as each other. In this case, all bits canbe estimated using exactly the same parameters,
and we can not expect that we will benefit significantly from applying this redundant representation. Therefore, we need to choose an error correction method in which the characteristics of original bits should be distributed in various positionsof the resulting bit arrays so that errors in bits are
not highly correlated with each-other. In addition,
it is desirable that the decoding method of the applied error-correcting code can directly utilize theprobabilities of each bit, because q generated by
the network will be a continuous probabilities between zero and one.
In this study, we applied convolutional codes(Viterbi, 1967) to convert between original and redundant bits. Convolutional codes perform a setof bit-wise convolutions between original bits andweight bits (which are hyper-parameters). They
are well-suited to our setting here because they
distribute the information of original bits in different places in the resulting bits, work robustly
for random bit errors, and can be decoded using

bit probabilities directly.
Algorithm 2 describes the particular convolutional code that we applied in this study, with two
convolution weights [1001111] and [1101101] as
fixed hyper-parameters.4 P
Where x[i .. j] :=[xi , · · · , xj ] and x · y := i xi yi . On the other
hand, there are various algorithms to decode convolutional codes with the same format which are
based on different criteria. In this study, we use thedecoding method described in Algorithm 3, wherex ◦ y represents the concatenation of vectors x
and y. This method is based on the Viterbi algorithm (Viterbi, 1967) and estimates original bits
by directly using probability of redundant bits. Although Algorithm 3 looks complicated, this algorithm can be performed efficiently on CPUs at test
time, and is not necessary at training time when weare simply performing calculation of Equation (6).
Algorithm 2 increases the number of bits from B
into B 0 = 2(B +6), but does not restrict the actual
value of B.
4

We also examined many configurations of convolutional
codes which have different robustness and computation costs,
and finally chose this one.

855

Table 2: Evaluated methods.
Name
Summary
Softmax
Softmax prediction (Fig. 2(a))
BinaryFig. 2(b) w/ raw bit array
Hybrid-N
Fig. 2(c) w/ softmax size N
Binary-EC
Binary w/ error-correction
Hybrid-N-EC Hybrid-N w/ error-correction

Table 1: Details of the corpus.
Name
ASPEC BTEC
Languages
En ↔ Ja
Train 2.00 M 465. k#sentences Dev
1,790
510
Test
1,812
508
Vocabulary size V
65536 25000

4

Experiments

4.1

Experimental Settings

We examined the performance of the proposed
methods on two English-Japanese bidirectionaltranslation tasks which have different translationdifficulties: ASPEC (Nakazawa et al., 2016) and
BTEC (Takezawa, 1999). Table 1 describes detailsof two corpora. To prepare inputs for training, weused tokenizer.perl in Moses (Koehn et al.,2007) and KyTea (Neubig et al., 2011) for English/Japanese tokenizations respectively, applied
lowercase.perl from Moses, and replaced
out-of-vocabulary words such that rank(w) >V − 3 into the UNK marker.
We implemented each NMT model using C++
in the DyNet framework (Neubig et al., 2017) andtrained/tested on 1 GPU (GeForce GTX TITAN
X). Each test is also performed on CPUs to compare its processing time. We used a bidirectional
RNN-based encoder applied in Bahdanau et al.
(2014), unidirectional decoder with the same styleof (Luong et al., 2015), and the concat global
attention model also proposed in Luong et al.
(2015). Each recurrent unit is constructed using a
1-layer LSTM (input/forget/output gates and nonpeepholes) (Gers et al., 2000) with 30% dropout(Srivastava et al., 2014) for the input/output vectors of the LSTMs. All word embeddings, recurrent states and model-specific hidden states are designed with 512-dimentional vectors. Only output
layers and loss functions are replaced, and othernetwork architectures are identical for the conventional/proposed models. We used the Adam optimizer (Kingma and Ba, 2014) with fixed hyperparameters α = 0.001, β1 = 0.9 β2 = 0.999, ε =10−8 , and mini-batches with 64 sentences sorted
according to their sequence lengths. For evaluating the quality of each model, we calculatedcase-insensitive BLEU (Papineni et al., 2002) every 1000 mini-batches. Table 2 lists summaries ofall methods we examined in experiments.

(a) ASPEC (En → Ja)(b) BTEC (En → Ja)
Figure 5: Training curves over 180,000 epochs.

4.2

Results and Discussion

Table 3 shows the BLEU on the test set (bold anditalic faces indicate the best and second places ineach task), number of bits B (or B 0 ) for the binarycode, actual size of the output layer #out , numberof parameters in the output layer #W,β , as well as
the ratio of #W,β or amount of whole parameterscompared with Softmax, and averaged processing
time at training (per mini-batch on GPUs) andtest (per sentence on GPUs/CPUs), respectively.
Figure 5(a) and 5(b) shows training curves up
to 180,000 epochs about some English→Japanesesettings. To relax instabilities of translation qualities while training (as shown in Figure 5(a) and5(b)), each BLEU in Table 3 is calculated by averaging actual test BLEU of 5 consecutive results856

Table 3: Comparison of BLEU, size of output layers, number of parameters and processing time.
Corpus

ASPEC

BTEC

MethodSoftmax
BinaryHybrid-512
Hybrid-2048
Binary-EC
Hybrid-512-EC
Hybrid-2048-EC
Softmax
BinaryHybrid-512
Hybrid-2048
Binary-EC
Hybrid-512-EC
Hybrid-2048-EC

BLEU %
EnJa
JaEn
31.13 21.14
13.78 6.953
22.81 13.95
27.73 16.92
25.95 18.02
29.07 18.66
30.05 19.66
47.72 45.22
31.83 31.90
44.23 43.50
46.13 45.76
44.48 41.21
47.20 46.52
48.17 46.58

B

#out

#W,β

—
16
16
16
44
44
44
—
15
15
15
42
42
42

65536
16
528
2064
44
556
2092
25000
15
527
2063
42
554
2090

33.6 M
8.21 k271. k
1.06 M
22.6 k285. k
1.07 M12.8 M
7.70 k270. k
1.06 M
21.5 k284. k
1.07 M

Ratio of #params
#W,β
All
1/1
1
1/4.10 k 0.698
1/124.
0.700
1/31.80.707
1/1.49 k 0.698
1/118.
0.700
1/31.40.707
1/1
1
1/1.67 k 0.738
1/47.40.743
1/12.10.759
1/595.
0.738
1/45.10.744
1/12.00.760

Time (En→Ja) [ms]Train Test: GPU / CPU
1026.
121.6 / 2539.
711.2
73.08 / 122.3
843.6
81.28 / 127.5
837.1
82.28 / 159.3
712.0
78.75 / 164.0
850.3
80.30 / 180.2
851.6
77.83 / 201.3
325.0
34.35 / 323.3
250.7
27.98 / 54.62
300.7
28.83 / 66.13
307.7
28.25 / 67.40
255.6
28.02 / 69.76
307.8
28.44 / 56.98
311.0
28.47 / 69.44

possible to apply a similar binary representation
as that of output layers to the input layers as well,then express the word embedding by multiplying
this binary vector by a word embedding matrix.
This is one potential avenue of future work.
Taking a look at the BLEU for the simple Binary method, we can see that it is far lower thanother models for all tasks. This is expected, as
described in Section 3, because using raw bit arrays causes many one-off estimation errors at theoutput layer due to the lack of robustness of theoutput representation. In contrast, Hybrid-N and
Binary-EC models clearly improve BLEU from
Binary, and they approach that of Softmax. This
demonstrates that these two methods effectively
improve the robustness of binary code prediction
models. Especially, Binary-EC generally achieves
higher quality than Hybrid-512 despite the factthat it suppress the number of parameters by about
1/10. These results show that introducing redundancy to target bit arrays is more effective thanincremental prediction. In addition, the Hybrid-NEC model achieves the highest BLEU in all proposed methods, and in particular, comparative or
higher BLEU than Softmax in BTEC. This behavior clearly demonstrates that these two methods
are orthogonal, and combining them together canbe effective. We hypothesize that the lower quality of Softmax in BTEC is caused by an over-fitting
due to the large number of parameters required in
the softmax prediction.
The proposed methods also improve actual
computation time in both training and test. In particular on CPU, where the computation speed is
directly affected by the size of the output layer,
the proposed methods translate significantly fasterFigure 6: BLEU changes in the Hybrid-N methods
according to the softmax size (En→Ja).

around the epoch that has the highest dev BLEU.
First, we can see that each proposed method
largely suppresses the actual size of the output
layer from ten to one thousand times comparedwith the standard softmax. By looking at the total number of parameters, we can see that the
proposed models require only 70% of the actual
memory, and the proposed model reduces the total number of parameters for the output layers toa practically negligible level. Note that most ofremaining parameters are used for the embedding
lookup at the input layer in both encoder/decoder.
These still occupy O(EV ) memory, where E represents the size of each embedding layer and usually O(E/H) = O(1). These are not targets to be
reduced in this study because these values rarely
are accessed at test time because we only need toaccess them for input words, and do not need themto always be in the physical memory. It might be857

References

than Softmax by x5 to x20. In addition, we canalso see that applying error-correcting code is also
effictive with respect to the decoding speed.
Figure 6 shows the trade-off between the translation quality and the size of softmax layers in
the hybrid prediction model (Figure 2(c)) without error-correction. According to the model definition in Section 3.4, the softmax prediction andraw binary code prediction can be assumed to be
the upper/lower-bound of the hybrid prediction
model. The curves in Figure 6 move between Softmax and Binary models, and this behavior intuitively explains the characteristics of the hybrid
prediction. In addition, we can see that the BLEU
score in BTEC quickly improves, and saturates at
N = 1024 in contrast to the ASPEC model, whichis still improving at N = 2048. We presume thatthe shape of curves in Figure 6 is also affected by
the difficulty of the corpus, i.e., when we train the
hybrid model for easy datasets (e.g., BTEC is easier than ASPEC), it is enough to use a small softmax layer (e.g. N ≤ 1024).

5

Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014. Neural machine translation by jointly
learning to align and translate. arXiv preprint
arXiv:1409.0473 .
Peter F Brown, Peter V Desouza, Robert L Mercer,
Vincent J Della Pietra, and Jenifer C Lai. 1992.
Class-based n-gram models of natural language.
Computational linguistics 18(4):467–479.
Wenlin Chen, David Grangier, and Michael Auli. 2016.
Strategies for training large vocabulary neural language models. In Proceedings of the 54th Annual
Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for
Computational Linguistics, Berlin, Germany, pages
1975–1985. http://www.aclweb.org/anthology/P161186.
Rohan Chitnis and John DeNero. 2015. Variablelength word encodings for neural translation models.
In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing. Association for Computational
Linguistics, Lisbon, Portugal, pages 2088–2093.
http://aclweb.org/anthology/D15-1249.

Conclusion

Thomas G. Dietterich and Ghulum Bakiri. 1995.
Solving multiclass learning problems via errorcorrecting output codes. Journal of Artificial Intelligence Research 2:263–286.

In this study, we proposed neural machine translation models which indirectly predict output words
via binary codes, and two model improvements:a hybrid prediction model using both softmax
and binary codes, and introducing error-correcting
codes to introduce robustness of binary code prediction. Experiments show that the proposedmodel can achieve comparative translation qualities to standard softmax prediction, while significantly suppressing the amount of parameters in
the output layer, and improving calculation speeds
while training and especially testing.
One interesting avenue of future work is to automatically learn encodings and error correcting
codes that are well-suited for the type of binary
code prediction we are performing here. In Algorithms 2 and 3 we use convolutions that were
determined heuristically, and it is likely that learning these along with the model could result in improved accuracy or better compression capability.

Chun-Sung Ferng and Hsuan-Tien Lin. 2011. Multilabel classification with error-correcting codes.
Journal of Machine Learning Research 20:281–295.
Chun-Sung Ferng and Hsuan-Tien Lin. 2013. Multilabel classification using error-correcting codes of
hard or soft bits. IEEE transactions on neural networks and learning systems 24(11):1888–1900.
Felix A Gers, Jürgen Schmidhuber, and Fred Cummins.
2000. Learning to forget: Continual prediction with
LSTM. Neural computation 12(10):2451–2471.
Marcel J. E. Golay. 1949. Notes on digital coding. Proceedings of the Institute of Radio Engineers
37:657.
David A. Huffman. 1952. A method for the construction of minimum-redundancy codes. Proceedings ofthe Institute of Radio Engineers 40(9):1098–1101.
Diederik Kingma and Jimmy Ba. 2014. Adam: A
method for stochastic optimization. arXiv preprint
arXiv:1412.6980 .

Acknowledgments
Part of this work was supported by JSPS
KAKENHI Grant Numbers JP16H05873 andJP17H00747, and Grant-in-Aid for JSPS Fellows
Grant Number 15J10649.

Aldebaro Klautau, Nikola Jevtić, and Alon Orlitsky.
2003. On nearest-neighbor error-correcting output
codes with application to all-pairs multiclass support
vector machines. Journal of Machine Learning Research 4(April):1–15.

858

Proceedings of Tenth International Workshop on Artificial Intelligence and Statistics. volume 5, pages
246–252.

Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris
Callison-Burch, Marcello Federico, Nicola Bertoldi,
Brooke Cowan, Wade Shen, Christine Moran,
Richard Zens, Chris Dyer, Ondrej Bojar, Alexandra Constantin, and Evan Herbst. 2007. Moses:
Open source toolkit for statistical machine translation. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics
Companion Volume Proceedings of the Demo andPoster Sessions. Association for Computational Linguistics, Prague, Czech Republic, pages 177–180.
http://www.aclweb.org/anthology/P07-2045.

Toshiaki Nakazawa, Manabu Yaguchi, Kiyotaka Uchimoto, Masao Utiyama, Eiichiro Sumita, Sadao
Kurohashi, and Hitoshi Isahara. 2016. Aspec:
Asian scientific paper excerpt corpus. In Nicoletta Calzolari (Conference Chair), Khalid Choukri,
Thierry Declerck, Marko Grobelnik, Bente Maegaard, Joseph Mariani, Asuncion Moreno, Jan
Odijk, and Stelios Piperidis, editors, Proceedingsof the Ninth International Conference on Language
Resources and Evaluation (LREC 2016). European
Language Resources Association (ELRA), Portoro,
Slovenia, pages 2204–2208.

Abbas Z Kouzani. 2010. Multilabel classification using error correction codes. In International Symposium on Intelligence Computation and Applications.
Springer, pages 444–454.

Graham Neubig, Chris Dyer, Yoav Goldberg, Austin
Matthews, Waleed Ammar, Antonios Anastasopoulos, Miguel Ballesteros, David Chiang, Daniel
Clothiaux, Trevor Cohn, Kevin Duh, Manaal
Faruqui, Cynthia Gan, Dan Garrette, Yangfeng Ji,
Lingpeng Kong, Adhiguna Kuncoro, Gaurav Kumar, Chaitanya Malaviya, Paul Michel, Yusuke
Oda, Matthew Richardson, Naomi Saphra, Swabha
Swayamdipta, and Pengcheng Yin. 2017. Dynet:
The dynamic neural network toolkit. arXiv preprint
arXiv:1701.03980 .

Abbas Z Kouzani and Gulisong Nasireding. 2009.
Multilabel classification by bch code and random
forests. International journal of recent trends in engineering 2(1):113–116.
Gurvan L’Hostis, David Grangier, and Michael Auli.
2016. Vocabulary selection strategies for neural machine translation. arXiv preprint arXiv:1610.00072.
Wang Ling, Isabel Trancoso, Chris Dyer, and Alan W
Black. 2015. Character-based neural machine translation. arXiv preprint arXiv:1511.04586 .

Graham Neubig, Yosuke Nakata, and Shinsuke Mori.
2011. Pointwise prediction for robust, adaptablejapanese morphological analysis. In Proceedingsof the 49th Annual Meeting of the Association
for Computational Linguistics: Human Language
Technologies. Association for Computational Linguistics, Portland, Oregon, USA, pages 529–533.
http://www.aclweb.org/anthology/P11-2093.

Yang Liu. 2006. Using svm and error-correcting codes
for multiclass dialog act classification in meeting
corpus. In INTERSPEECH.
Thang Luong, Hieu Pham, and Christopher D. Manning. 2015. Effective approaches to attention-basedneural machine translation. In Proceedings of the2015 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, Lisbon, Portugal, pages 1412–
1421. http://aclweb.org/anthology/D15-1166.

Kishore Papineni, Salim Roukos, Todd Ward,and Wei-Jing Zhu. 2002.
Bleu: a method
for automatic evaluation of machine translation. In Proceedings of 40th Annual Meetingof the Association for Computational Linguistics. Association for Computational Linguistics,
Philadelphia, Pennsylvania, USA, pages 311–318.
https://doi.org/10.3115/1073083.1073135.

Haitao Mi, Zhiguo Wang, and Abe Ittycheriah. 2016.
Vocabulary manipulation for neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics(Volume 2: Short Papers). Association for Computational Linguistics, Berlin, Germany, pages 124–129.
http://anthology.aclweb.org/P16-2021.

Rico Sennrich, Barry Haddow, and Alexandra Birch.
2016. Neural machine translation of rare words withsubword units. In Proceedings of the 54th Annual
Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for
Computational Linguistics, Berlin, Germany, pages
1715–1725. http://www.aclweb.org/anthology/P161162.

Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing
systems. pages 3111–3119.

Claude E. Shannon. 1948. A mathematical theoryof communication. Bell System Technical Journal
27(3):379–423.

Andriy Mnih and Yee Whye Teh. 2012. A fast and simple algorithm for training neural probabilistic language models. In Proceedings of the 29th International Conference on Machine Learning.

Nitish Srivastava, Geoffrey E Hinton, Alex Krizhevsky,
Ilya Sutskever, and Ruslan Salakhutdinov. 2014.
Dropout: a simple way to prevent neural networks
from overfitting. Journal of Machine Learning Research 15(1):1929–1958.

Frederic Morin and Yoshua Bengio. 2005. Hierarchical probabilistic neural network language model. In

859

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.
Toshiyuki Takezawa. 1999.
Building a bilingual
travel conversation database for speech translation
research. In Proc. of the 2nd international workshop
on East-Asian resources and evaluation conferenceon language resources and evaluation. pages 17–20.
Andrew Viterbi. 1967. Error bounds for convolutional
codes and an asymptotically optimum decoding algorithm. IEEE transactions on Information Theory
13(2):260–269.
George. K. Zipf. 1949. Human behavior and the principle of least effort.. Addison-Wesley Press.

860