Neural Machine Translation via Binary Code Prediction
In this paper, we propose a new method for calculating the output layer in neural machine translation systems. The method is based on predicting a binary code for each word, and can reduce computation time/memory requirements of the output layer to be logarithmic in vocabulary size in the best case. In addition, we also introduce two advanced approaches to improve robustness of the proposed model: using error-correcting codes and combining softmax and binary codes. Experiments show the proposed model achieves translation accuracies that approach the softmax, while reducing memory usage on the order of 1/10 to 1/1000, and also improving decoding speed on CPUs by x5 to x20.
1 Introduction
When handling broad or open domains, machine translation 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 model (Bahdanau et al., 2014; Luong et al., 2015) shown in Figure 1. In these models, 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 of computation to predict each of the candidate word probabilities.
Because this is a significant problem for neural language and translation models, there are a number of methods proposed to resolve this problem, which we detail in Section 2.2. However, none of these previous methods simultaneously satisfies the following desiderata, all of which, we argue, are desirable for practical use in NMT systems:
Memory efficiency: The method should not require large memory to store the parameters and calculated vectors to maintain scalability in resource-constrained environments.
Time efficiency: The method should be able to train the parameters efficiently, and possible to perform decoding efficiently with choosing the candidate words from the full probability distribution. In particular, the method should be performed fast on general CPUs to suppress physical costs of computational resources for actual production systems.
Compatibility with parallel computation: It should 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 pre-
2
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
dicting a softmax over the entire output vocabulary, 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 least n bits long, and thus the amount of computation and 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 found that it alone was not enough to achieve competitive accuracy with real NMT models. Thus we make two 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 to the 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 find that 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
Most of current NMT models use one-hot representations to represent the words in the output vocabulary – each word w is represented by a unique sparse 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 the target language. NMT models optimize network parameters by treating the one-hot representation eid(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 expu− uid(w), (2)
v := expu/ sum expu, (3)
u := Whuh+ βu, (4)
where sumx represents the sum of all elements in x, xi represents the i-th element of x, Whu ∈
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 clearly requires time/space computation in proportion to O(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 tens of thousands (Sutskever et al., 2014).
2.2 Prior Work on Suppressing Complexity of NMT Models
Several previous works have proposed methods to reduce 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 the parameters, 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 word clusters. This method make the conversion matrix of 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 and Teh, 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.
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 for longer sequences, and thus are not a direct solution to problems of computational efficiency.
3 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
3
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
Figure 2: Designs of output layers.
bit arrays that correspond to each word. Let b(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 in whole array. For convenience, we introduce some constraints on b. First, a wordw is mapped to only one bit array b(w). Second, all unique words can be discriminated by b, i.e., all bit arrays satisfy that:
id(w) 6= id(w′)⇒ b(w) 6= b(w′). (5)
Third, multiple bit arrays can be mapped to the same word as described in Section 3.5. By considering second constraint, we can also constrain B ≥ dlog2 V e, because b should have at least V unique representations to distinguish each word. The output layer of the network independently predicts B probability values q := [q1(h), q2(h), · · · , qB(h)] ∈ [0, 1]B using the current hidden values h by logistic regressions:
q(h) = σ(Whqh+ βq), (6) σ(x) := 1/(1 + exp(−x)), (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,” the joint probability of generating word w can be represented as:
Pr(w|h) := B∏ i=1 ( biqi + b̄iq̄i ) , (8)
Algorithm 1 Mapping words to bit arrays. Require: w ∈ V Ensure: b ∈ {0, 1}B = Bit array representing w
x :=  0, if w = UNK 1, if w = BOS 2, if w = EOS 2 + rank(w), otherwise bi := bx/2i−1c mod 2 b← [b1, b2, · · · , bB ]
where x̄ := 1 − x. We can easily obtain the maximum-probability bit array from q by simply assuming bi = 1 if qi ≥ 1/2, and bi = 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 that w = 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 to choose 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.1 Here, V is the set of V target words including 3 extra markers: UNK, BOS (begin-of-sentence), and EOS (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 one of the minimal mapping methods (i.e., satisfying B = dlog2 V e), and generated bit arrays have the characteristics 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).
3.2 Loss Functions
For learning correct binary representations, we can use any loss function that satisfies a constraint that:
LB(q, b) { = 0, if q = b, ≥ 0, otherwise. (9)
For example, the squared-distance:
LB(q, b) := B∑ i=1 (qi − bi)2, (10)
1Other methods examined included random codes, Huffman codes (Huffman, 1952) and Brown clustering (Brown et al., 1992) with zero-padding to adjust code lengths, and some original allocation methods based on the word2vec embeddings (Mikolov et al., 2013).
4
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
or the cross-entropy:
LB(q, b) := − B∑ i=1 ( bi log qi + b̄i log q̄i ) , (11)
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 Efficiency of the Binary Code Prediction
The computational complexity for the parameters Whq and βq is O(HB). This is equal to 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 chose V = 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 can be interpreted as the hierarchical softmax with two strong constraints for guaranteeing independence between all bits: all nodes in the same level of the hierarchy share their parameters, and all levels of the hierarchy are predicted independently of each other. By these constraints, all bits in b can be calculated in parallel. This is particularly important because it makes the model conducive to being calculated on GPGPUs.
However, the binary code prediction model also introduces problems of robustness due to these strong 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.
3.4 Hybrid Softmax/Binary Model
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 rare words. To alleviate this problem, we introduce a hybrid model using both softmax prediction and binary 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 rare words. 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 is separated into two equations according to the frequency of words:
Pr(w|h) := { v′id(w), if id(w) < N,
v′N · π(w,h), otherwise, (12)
v′ := expu′/ sum expu′, (13) u′ := Whu′h+ βu′ , (14)
π(w,h) := B∏ i=1 ( biqi + b̄iq̄i ) , (15)
where Whu′ ∈ RN×H and βu′ ∈ 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 hybrid model using both softmax and binary code losses:
L := { lH(id(w)), if id(w) < N, lH(N) + lB, otherwise, (16) lH(i) := λHLH(v ′, i), (17)
lB := λBLB(q, b), (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 than the original binary code modelO(H log V ). However,N can be chosen asN V because the softmax prediction is only required for a few frequent words. 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 frequent words 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 soft-
5
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
Figure 3: Example of the classification problem using redundant bit array mapping.
Figure 4: Training and generation processes with error-correcting code.
max, because the actual size of the output layer is still 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 of each 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 this idea works when discriminating 2 words using 3 bits. In this case, the actual words are obtained by 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 the ability 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 determined
by the design of error-correcting codes. Errorcorrecting codes have been examined in some previous work on multi-class classification tasks, and have 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) with error-correction, unlike previous studies focused on solving comparatively small tasks (#classes < 100). And this study also tries to solve a generation task unlike previous studies. As shown in the experiments, we found that this approach is highly effective in these tasks.
Figure 4 (a) and (b) illustrate the training and generation processes for the model with errorcorrecting codes. In the training, we first convert the original bit arrays b(w) to a center bit array b′ in the space of error-correcting code: b′(b) := [b′1(b), b ′ 2(b), · · · , b′B′(b)] ∈ {0, 1}B ′ , where B′(B) ≥ B is the number of bits in the error-correcting code. The NMT model learns its parameters based on the loss between predicted probabilities q and b′. Note that typical errorcorrecting codes satisfy O(B′/B) = O(1), and this 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)], and uses 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 is clear that these bits represent exactly the same information as each other. In this case, all bits can be 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 positions of the resulting bit arrays so that errors in bits are
6
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
Algorithm 2 Encoding into a convolutional code. Require: b ∈ {0, 1}B Ensure: b′ ∈ {0, 1}2(B+6) = Redundant bit array
x[t] := { bt, if 1 ≤ t ≤ B 0, otherwise y1t := x[t− 6 .. t] · [1001111] mod 2 y2t := x[t− 6 .. t] · [1101101] mod 2 b′ ← [y11 , y21 , y12 , y22 , · · · , y1B+6, y2B+6]
Algorithm 3 Decoding from a convolutional code. Require: q ∈ (0, 1)2(B+6) Ensure: q̃ ∈ {0, 1}B = Restored original bit array g(q, b) := b log q + (1− b) log(1− q)
φ0[s | s ∈ {0, 1}6]← {
0, if s = [000000] −∞, otherwise
for t = 1→ B + 6 do for 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′(x) := g(q2t−1, o1(x)) + g(q2t, o2(x)) φ′(x) := φt−1[s
prev(x)] + g′(x) x̂← arg maxx∈{0,1} φ′(x) rt[s
cur]← sprev(x̂) φt[s
cur]← φ′(x̂) end for
end for s′ ← [000000] for t = B → 1 do
s′ ← rt+6[s′] q̃t ← s′1
end for q̃ ← [q̃1, q̃2, · · · , q̃B ]
not highly correlated with each-other. In addition, it is desirable that the decoding method of the applied error-correcting code can directly utilize the probabilities 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 set of bit-wise convolutions between original bits and weight 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.2 Where x[i .. j] :=
2We also examined many configurations of convolutional codes which have different robustness and computation costs, and finally chose this one.
[xi, · · · , xj ] and x · y := ∑
i xiyi. 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 the decoding method described in Algorithm 3, where x ◦ 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 we are simply performing calculation of Equation (6). Algorithm 2 increases the number of bits from B intoB′ = 2(B+6), but does not restrict the actual value of B.
4 Experiments
4.1 Experimental Settings
We examined the performance of the proposed methods on two English-Japanese bidirectional translation tasks which have different translation difficulties: ASPEC (Nakazawa et al., 2016) and BTEC (Takezawa, 1999). Table 1 describes details of two corpora. To prepare inputs for training, we used 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) and trained/tested on 1 GPU (GeForce GTX TITAN X). Each test is also performed on CPUs to compare its processing time. We used the concat local attention model proposed in Luong et al. (2015) constructed using a 1-layer LSTM (input/forget/output gates and non-peepholes) (Gers et al., 2000) encoder/decoder with 30% dropout (Srivastava et al., 2014) for the input/output vectors of the LSTMs. Only output layers and loss functions are replaced, and other network architectures are identical for the conventional/proposed models. We used the Adam optimizer (Kingma and Ba, 2014) with fixed hyper-parameters α = 0.001, β1 = 0.9β2 = 0.999, ε = 10
−8, and minibatches with 64 sentences sorted according to their sequence lengths. For evaluating the quality of each model, we calculated BLEU (Papineni et al., 2002) every 1000 mini-batches. Table 2 lists all
7
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
Table 1: Details of the corpus.
Name ASPEC BTEC
Languages En↔ Ja
#sentences Train 2.00 M 465. k Dev 1,790 510 Test 1,812 508 Vocabulary size V 65536 25000
Table 2: Evaluated models.
Name Summary Softmax Softmax prediction (Figure 2(a)) Binary Figure 2(b) w/ raw bit array Hybrid-N Figure 2(c) w/ softmax size N Binary-EC Binary w/ error-correction Hybrid-N-EC Hybrid-N w/ error-correction
models we examined in experiments.
4.2 Results and Discussion
Table 3 shows the BLEU on the test set, number of bits B (or B′) for the binary code, actual size of the output layer #out, number of parameters in the output layer #W,β, as well as the ratio of #W,β or amount of whole parameters compared with Softmax, and averaged processing time at training (per mini-batch on GPUs) and test (per sentence on GPUs/CPUs), respectively. Figure 5(a) and 5(b) shows training curves up to 180,000 epochs about some English→Japanese settings. To relax instabilities of translation qualities while training (as shown in Figure 5(a) and 5(b)), each BLEU in Table 3 is calculated by averaging actual test BLEU of 5 consecutive results 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 compared with 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 to a practically negligible level. Note that most of remaining 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 to access them for input words, and do not need them to always be in the physical memory. It might be
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 than other models for all tasks. This is expected, as described in Section 3, because using raw bit arrays causes many one-off estimation errors at the output layer due to the lack of robustness of the output 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 fact that it suppress the number of parameters by about 1/10. These results show that introducing redundancy to target bit arrays is more effective than incremental 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 behav-
8
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
Table 3: Comparison of BLEU, size of output layers, number of parameters and processing time.
Corpus Method BLEU % B #out #W,β
Ratio of #params Time (En→Ja) [ms] EnJa JaEn #W,β All Train Test: GPU / CPU
ASPEC Softmax 31.13 21.14 — 65536 33.6 M 1/1 1 1026. 121.6 / 2539. Binary 13.78 6.953 16 16 8.21 k 1/4.10 k 0.698 711.2 73.08 / 122.3 Hybrid-512 22.81 13.95 16 528 271. k 1/124. 0.700 843.6 81.28 / 127.5 Hybrid-2048 27.73 16.92 16 2064 1.06 M 1/31.8 0.707 837.1 82.28 / 159.3 Binary-EC 25.95 18.02 44 44 22.6 k 1/1.49 k 0.698 712.0 78.75 / 164.0 Hybrid-512-EC 29.07 18.66 44 556 285. k 1/118. 0.700 850.3 80.30 / 180.2 Hybrid-2048-EC 30.05 19.66 44 2092 1.07 M 1/31.4 0.707 851.6 77.83 / 201.3
BTEC Softmax 47.72 45.22 — 25000 12.8 M 1/1 1 325.0 34.35 / 323.3 Binary 31.83 31.90 15 15 7.70 k 1/1.67 k 0.738 250.7 27.98 / 54.62 Hybrid-512 44.23 43.50 15 527 270. k 1/47.4 0.743 300.7 28.83 / 66.13 Hybrid-2048 46.13 45.76 15 2063 1.06 M 1/12.1 0.759 307.7 28.25 / 67.40 Binary-EC 44.48 41.21 42 42 21.5 k 1/595. 0.738 255.6 28.02 / 69.76 Hybrid-512-EC 47.20 46.52 42 554 284. k 1/45.1 0.744 307.8 28.44 / 56.98 Hybrid-2048-EC 48.17 46.58 42 2090 1.07 M 1/12.0 0.760 311.0 28.47 / 69.44
Figure 6: BLEU changes in the Hybrid-N methods according to the softmax size (En→Ja).
ior clearly demonstrates that these two methods are orthogonal, and combining them together can be 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.
Proposed methods also improve actual computation time in both training and test. In particular, proposed methods can be performed significantly faster than Softmax at testing on CPUs by x5 to x20, which are directly affected by the complexity of output layers. In addition, we can also see that applying error-correcting code is also efficient at the point of 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 and
raw 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, which is still improving at N = 2048. We presume that the 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 Conclusion
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 proposed model 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.
9
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
- Strengths: This paper has high originality, proposing a fundamentally different way of predicting words from a vocabulary that is more efficient than a softmax layer and has comparable performance on NMT. If successful, the approach could be impactful because it speeds up prediction.  This paper is nice to read with great diagrams. it's very clearly presented -- I like cross-referencing the models with the diagrams in Table 2. Including loss curves is appreciated.  - Weaknesses: Though it may not be possible in the time remaining, it would be good to see a comparison (i.e. BLEU scores) with previous related work like hierarchical softmax and differentiated softmax.  The paper is lacking a linguistic perspective on the proposed method. Compared to a softmax layer and hierarchical differentiated softmax, is binary code prediction a natural way to predict words? Is it more or less similar to how a human might retrieve words from memory? Is there a theoretical reason to believe that binary code based approaches should be more or less suited to the task than softmax layers?  Though the paper promises faster training speeds in the introduction, Table 3 shows only modest (less than x2) speedups for training. Presumably this is because much of the training iteration time is consumed by other parts of the network. It would be useful to see the time needed for the output layer computation only.  - General Discussion: It would be nice if the survey of prior work in 2.2 explicitly related those methods to the desiderata in the introduction (i.e. specify which they satisfy).  Some kind of analysis of the qualitative strengths and weaknesses of the binary code prediction would be welcome -- what kind of mistakes does the system make, and how does this compare to standard softmax and or hierarchical and differentiated softmax?  LOW LEVEL COMMENTS  Equation 5: what's the difference between id(w) = id(w') and w = w' ?  335: consider defining GPGPU  Table 3: Highlight the best BLEU scores in bold  Equation 15: remind the reader that q is defined in equation 6 and b is a function of w. I was confused by this at first because w and h appear on the LHS but don't appear on the right, and I didn't know what b and q were.