summaries: This paper studies FL under local differential privacy constraints. They identify two major concerns in designing practical privacy-preserving FL algorithms: communication efficiency and highdimensional compatibility, and develop a gradient-based learning algorithm sqSGD that addresses both concerns. They improve the base algorithm in two ways: First, apply a gradient subsampling strategy that offers simultaneously better training performance and smaller communication costs. Secondly, utilize randomized rotation as a preprocessing step to reduce quantization error.

summaries: This paper studies a low communication algorithm for multivariate mean estimation in the federated learning setting with differentially private communication. The algorithm uses quantization and dimension subsampling (only reporting some coordinates of the vector) to lower communication and randomized rotation (essentially applying a random orthogonal matrix) to reduce quantization error. They then apply this algorithm to ERM, using it as a subroutine in SGD. They experimentally explore the behavior of their algorithm on a number of benchmark datasets. They consider how the performance changes as they vary epsilon, the discretization parameter and the number of epochs (in SGD).

summaries: The paper proposed a differentially private training algorithm for federated learning. The target is to achieve communication reduction while keeping differential privacy during training. The proposed algorithm adds a few new components to SGD, including a privacy mechanism, a random rotation to reduce quantization error, a gradient coordinate selection mechanism to reduce communication/computation. Experiments with high \epsilon local differentially privacy guarantees are conducted. The proposed algorithm outperforms a baseline algorithm.

abstractText: Federated learning (FL) is a technique that trains machine learning models from decentralized data sources. We study FL under local differential privacy constraints, which provides strong protection against sensitive data disclosures via obfuscating the data before leaving the client. We identify two major concerns in designing practical privacy-preserving FL algorithms: communication efficiency and highdimensional compatibility. We then develop a gradient-based learning algorithm called sqSGD (selective quantized stochastic gradient descent) that addresses both concerns. The proposed algorithm is based on a novel privacy-preserving quantization scheme that uses a constant number of bits per dimension per client. Then we improve the base algorithm in two ways: first, we apply a gradient subsampling strategy that offers simultaneously better training performance and smaller communication costs under a fixed privacy budget. Secondly, we utilize randomized rotation as a preprocessing step to reduce quantization error. We also initialize a discussion about the role of quantization and perturbation in FL algorithm design with privacy and communication constraints. Finally, the practicality of the proposed framework is demonstrated on benchmark datasets. Experiment results show that sqSGD successfully learns large models like LeNet and ResNet with local privacy constraints. In addition, with fixed privacy and communication level, the performance of sqSGD significantly dominates that of baseline algorithms.

authors:
Martin Abadi
Andy Chu
Ian Goodfellow
H. Brendan McMahan
Ilya Mironov
Kunal Talwar
Li Zhang

title: Deep learning with differential privacy

venue: In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS

authors:
Naman Agarwal
Ananda Theertha Suresh
Felix Xinnan X Yu
Sanjiv Kumar
Brendan McMahan

title: cpsgd: Communication-efficient and differentially-private distributed sgd

venue: In Advances in Neural Information Processing Systems,

authors:
Alham Fikri Aji
Kenneth Heafield

title: Sparse communication for distributed gradient descent

venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,

authors:
Dan Alistarh
Demjan Grubic
Jerry Li
Ryota Tomioka
Milan Vojnovic

title: Qsgd: Communicationefficient sgd via gradient quantization and encoding

venue: Advances in Neural Information Processing Systems

authors:
Abhishek Bhowmick
John Duchi
Julien Freudiger
Gaurav Kapoor
Ryan Rogers

title: Protection against reconstruction and its applications in private federated learning

venue: arXiv preprint arXiv:1812.00984,

authors:
Chia-Yu Chen
Jungwook Choi
Daniel Brand
Ankur Agrawal
Wei Zhang
Kailash Gopalakrishnan

title: Adacomp : Adaptive residual gradient compression for data-parallel distributed training, 2017

authors:
Gregory Cohen
Saeed Afshar
Jonathan Tapson
André van Schaik

title: Emnist: an extension of mnist to handwritten letters, 2017

authors:
Zeyu Ding
Yuxin Wang
Danfeng Zhang
Daniel Kifer

title: Free gap information from the differentially private sparse vector and noisy max mechanisms, 2019

authors:
John C Duchi
Michael I Jordan
Martin J Wainwright

title: Minimax optimal procedures for locally private estimation

venue: Journal of the American Statistical Association,

authors:
Cynthia Dwork
Aaron Roth

title: The algorithmic foundations of differential privacy

venue: Foundations and Trends in Theoretical Computer Science,

authors:
Venkata Gandikota
Daniel Kane
Raj Kumar Maity
Arya Mazumdar

title: vqsgd: Vector quantized stochastic gradient descent, 2019

authors:
Andrew Hard
Kanishka Rao
Rajiv Mathews
Swaroop Ramaswamy
Françoise Beaufays
Sean Augenstein
Hubert Eichner
Chloé Kiddon
Daniel Ramage

title: Federated learning for mobile keyboard prediction, 2019

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

title: Hadamard matrices and their applications

venue: Princeton university press,

authors:
Shiva Prasad Kasiviswanathan
Homin K Lee
Kobbi Nissim
Sofya Raskhodnikova
Adam Smith

title: What can we learn privately

venue: SIAM Journal on Computing,

authors:
Jakub Konečnỳ
H Brendan McMahan
Felix X Yu
Peter Richtárik
Ananda Theertha Suresh
Dave Bacon

venue: arXiv preprint arXiv:1610.05492,

authors:
Jakub Konečný
H. Brendan McMahan
Felix X. Yu
Peter Richtárik
Ananda Theertha Suresh
Dave Bacon

title: Federated learning: Strategies for improving communication efficiency, 2016

authors:
Y. Lecun
L. Bottou
Y. Bengio
P. Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
D. Leroy
A. Coucke
T. Lavril
T. Gisselbrecht
J. Dureau

title: Federated learning for keyword spotting

venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),

authors:
Yujun Lin
Song Han
Huizi Mao
Yu Wang
Bill Dally

title: Deep gradient compression: Reducing the communication bandwidth for distributed training

venue: In International Conference on Learning Representations,

authors:
Ruixuan Liu
Yang Cao
Masatoshi Yoshikawa
Hong Chen

title: Fedsel: Federated sgd under local differential privacy with top-k dimension selection, 2020

authors:
Lingjuan Lyu
Han Yu
Qiang Yang

title: Threats to federated learning: A survey

venue: arXiv preprint arXiv:2003.02133,

authors:
H. Brendan McMahan
Daniel Ramage
Kunal Talwar
Li Zhang

title: Learning differentially private recurrent language models

authors:
Luca Melis
Congzheng Song
Emiliano De Cristofaro
Vitaly Shmatikov

title: Inference attacks against collaborative learning

venue: arXiv preprint arXiv:1805.04049,

authors:
Feng Niu
Benjamin Recht
Christopher Re
Stephen J. Wright

title: Hogwild! a lock-free approach to parallelizing stochastic gradient descent

venue: In Proceedings of the 24th International Conference on Neural Information Processing Systems,

authors:
Ananda Theertha Suresh
X Yu Felix
Sanjiv Kumar
H Brendan McMahan

title: Distributed mean estimation with limited communication

venue: In International Conference on Machine Learning,

authors:
Ning Wang
Xiaokui Xiao
Yin Yang
Jun Zhao
Siu Cheung Hui
Hyejin Shin
Junbum Shin
Ge Yu

title: Collecting and analyzing multidimensional data with local differential privacy

venue: IEEE 35th International Conference on Data Engineering (ICDE),

authors:
K. Wei
J. Li
M. Ding
C. Ma
H.H. Yang
F. Farokhi
S. Jin
T.Q.S. Quek
H. Vincent Poor

title: Federated learning with differential privacy: Algorithms and performance analysis

venue: IEEE Transactions on Information Forensics and Security,

authors:
Wei Wen
Cong Xu
Feng Yan
Chunpeng Wu
Yandan Wang
Yiran Chen
Hai Li

title: Terngrad: Ternary gradients to reduce communication in distributed deep learning

authors:
Han Xiao
Kashif Rasul
Roland Vollgraf

title: Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017

heading: 1 INTRODUCTION

heading: 1.1 BACKGROUND

text:
Federated learning (FL) Kairouz et al. (2019); Konečnỳ et al. (2016) is a rapidly evolving application of distributed optimization to large-scale learning or estimation scenarios where multiple entities. called clients, collaborate in solving a machine learning problem, under the coordination of a central server. Each client’s raw data is stored locally and not exchanged or transferred. To achieve the learning objective, the server collects minimal information from the clients for immediate aggregation. FL is particularly suitable for mobile and edge device applications since the (sensitive) individual data never directly leave the device and has seen deployments in industries (?Hard et al., 2019; Leroy et al., 2019). While FL offers significant practical privacy improvements over centralizing all the training data, it lacks a formal privacy guarantee. As discussed in Melis et al. (2018), even if only model updates (i.e. gradient updates) are transmitted, it is easy to compromise the privacy of individual clients.
Differential privacy (DP) (Dwork et al., 2014) is the state-of-the-art approach to address information disclosure. Differentially private algorithms fuse participation of any individual via injecting algorithm-specific random noise. In FL setting, DP is suitable for protecting against external adversaries, i.e. a malicious analyst that tries to infer individual data via observing final or intermediate model results. However, DP paradigms typically assume a trusted curator, which corresponds to the server in the FL setting. This assumption is often not satisfied in practical cases, under which users that act as clients may not trust the service provider that acts as the server. Local differential privacy (LDP) (Kasiviswanathan et al., 2011; Dwork et al., 2014) provides privacy protection on the individual level via applying randomized mechanisms that obfuscate the data before leaving the
client, and is a more natural privacy model for distributed learning scenarios like FL, allowing easier compliance with regulatory strictures (Bhowmick et al., 2018).

heading: 1.2 METHODOLOGY

text:
We will be focusing on distributed learning procedures that aim to solve an empirical risk minimization problem in a decentralized fashion:
min θ∈Θ
L(θ), L(θ) = 1
N M∑ m=1 Lm(θ) (1)
where M denotes the number of clients. Let Yi denotes training data that belongs to the m-th client consisting Nm data points, and N = ∑M m=1Nm. The term Lm(θ) = ∑ y∈Ym `(θ, y) stands for locally aggregated loss evaluated at parameter θ, where ` : Θ × Y 7→ R+ is the loss function depending on the problem context and we use Θ and Y to describe parameter and data domain respectively. We will seek to optimize (1) via gradient-based methods. In what follows we will use [n], n ∈ N+ to denote the set {1, 2, . . . , n}. At round t, the procedure iterates as:
1. Server distribute the current value θt among a subset S of clients.
2. For each client s ∈ S, a local update is computed ∆s = g(θt, Ys) and transmitted to the server.
3. The server aggregates all {∆s}s∈Ss to obtain a global update ∆ and updates the parameter as θt+1 = θt + ∆.
We distinguish 2 practical scenarios as cross-silo FL and cross-device FL (Kairouz et al., 2019). In cross-silo FL, M is relatively small (i.e. M ≤ 100 ) and usually each client has a moderate or large amount of data (i.e. minmNm 1). As a consequence, all the clients participate in the learning process (i.e. S = [M ]). In each iteration a client computes locally a negative stochastic gradient g(θt, Ys) = − 1R ∑ y∈Rs ∇`(θt, y) of Ls(θt)/Ns, based on a uniform random subsample Rs ⊂ Ys of size R. In cross-device FL S is a uniformly random subset of [M ], and g(θt, Ys) = − 1Ns ∑ y∈Ys ∇`(θt, y) is the average negative gradient over Ys evaluated at θt. In this paper we will be focusing on the FedSgd aggregation rule corresponding to a stochastic gradient step with learning rate η, i.e., ∆ = η ∑ s∈S Ns N g(θt, Ys). Generally speaking, there are two sources of data that need privacy protection: the parameter θt and the updates {∆s}s∈S . In this paper we will develop algorithms for protecting {∆s}s∈S against inference attack or reconstruction attack, which will be defined later. Note that the protection of θts could be done via applying standard central DP techniques as in Bhowmick et al. (2018). To begin our discussion on suitably defined privacy models, we first review the local model of privacy.
Local differential privacy Kasiviswanathan et al. (2011) we say a randomized algorithm A that maps the private data X ∈ X to some value Z = A(X) ∈ Z is -locally differentially private, if the induced conditional probability measure P (·|X = x) satisfies that for any x, x′ ∈ X and any Z ∈ Z:
e− ≤ P (Z|X = x) P (Z|X = x′) ≤ e (2)
In the FL setting, the private data X is typically not the raw data Y but the gradient of the loss function ` evaluated at Y . Hereafter we will assume the private data to be a d dimensional euclidean vector, while d could be very large (i.e. to the order of millions). LDP is a very strong privacy protection model that protects individual data against inference attacks that aims at inferring the membership of arbitrary data from the data universe. According to the discussion in Bhowmick et al. (2018), allowing adversaries with such strength may be overly pessimistic: to conduct an effective inference attack the adversary shall come up with "the true data" and only use the privatized output to verify his/her belief about the membership. If the prior information is reasonably constrained for the adversary, we may adopt a weaker, but still elegant type of privacy protection paradigm that protects against reconstruction attacks. Heuristically, reconstruction attack aims at recovering individual data with respect to a well-defined criterion, given a prior over the data domain that is not too concentrated. Formally, we adopt the definition in Bhowmick et al. (2018):
Reconstruction attack Bhowmick et al. (2018) Let π be a prior distribution over the data domain Y that encodes the adversary’s prior belief. We describe the generation process of privatized user data as Y → X → Z = A(X) for some (privacy-protecting) mechanism A. Additionally let f : Y 7→ Rk be the target of reconstruction (i.e., the adversary wants to evaluate the value f(Y )) and Lrec : Rk × Rk 7→ R+ be the reconstruction loss serving as the criterion. Then an estimator ζ : X 7→ Rk provides an (α, p, f)-reconstruction breach for the loss Lrec if there exists some z ∈ Z such that:
P (Lrec(f(X), ζ(z))|A(X) = z) > p (3)
The existence of a reconstruction breach provides an attack that effectively breaks the privatized algorithm for some output z. Hence to provide protection against reconstruction attacks, we need the following to hold:
sup ζ sup z∈Z
P (Lrec(f(X), ζ(z))|A(X) = z) ≤ p (4)
When (4) holds, the mechanism A is said to be (α, p, f)-protected against reconstruction for the loss Lrec. In (Bhowmick et al., 2018, Lemma 2.2), the authors relates LDP mechanisms with protection against reconstruction attacks, and the result for several scenarios suggest that using LDP mechanisms with large may still provide decent protection against reconstruction. As a consequence, we identify two sorts of threats used in this paper:
Inference attacks by powerful adversaries this is the standard setup in LDP scenarios under which the adversary can observe the final learned model, as well as the information about potential participants except for the precise membership list. For such cases, only low LDP mechanisms provide sufficient protection against inference attacks. Reconstruction attacks by curious onlookers in this relaxed scenario we assume the adversary is able to observe all model updates and individual communications to conduct reconstruction attacks that target the evaluation of some function f over private individual data. But knowledge about individual data is restricted some prior distribution πf . For such cases, we will discover mechanisms that are based upon LDP algorithms with large but provides decent protection against reconstruction.
Moreover, we assume the adversaries to be semi-honest (Lyu et al., 2020), i.e. they are curious about individual data but follow the FL protocol correctly.
In the seminal work (Duchi et al., 2018), the authors developed minimax optimal LDP mean estimators under i.i.d generative constraints. Bhowmick et al. (2018) used separate mechanisms to privatize both the direction and the scale of the individual gradients, and was shown to achieve comparable performance with respect to non-private counterparts using high s. Despite the effectiveness of the LDP approach, the communication cost 1 is prohibitive. For models involving deep neural architectures, the number of parameters explodes to the order of millions. For each round, each client transmit O(dδ) bits to the server, where δ is the minimum number of bits to represent a real number with desired precision. The resulting communication cost is usually not affordable for mobile scenarios. In fact, the primary bottleneck for FL is usually communication, especially for deep neural architectures (Kairouz et al., 2019). It is thus of significant importance to reduce the communication cost to a reasonable level. We identify two main challenges in building practical privacy-preserving FL algorithms:
Communication Efficiency The algorithm shall be communication efficient, measured in terms of bits transferred per client in a single round. High-dimensional compatibility It was shown in Duchi et al. (2018) that upon estimating a ddimensional vector, the locally private constraint incurs a multiplicative penalty of O(d/ 2) in terms of minimax `2 risk. This linear dependence on the dimension of gradients may result in overly noisy gradient estimates that destroy the learning process. Hence the algorithm shall be able to handle models with high-dimensional inputs with tolerable performance degradation.
1In general, there are two sources of communication cost in a distributed learning scenario that requires sequential interactions between the server and the clients: downlink cost that happens during clients downloading the updated model from the central server, and uplink cost that happens when clients sending their updates to the server. In was previously noted in Konečnỳ et al. (2016) that uplink cost usually dominates downlink costs in FL settings. Hence in the scope of this work, we will refer to communication cost as uplink communication cost.
Summary of contributions In this paper, we propose a practical solution to locally private FL setting that addresses the above concerns which we term selective quantized stochastic gradient descent (sqSGD). Our contributions are summarized as follows:
1. We propose a novel algorithm for locally private multivariate mean estimation. The proposed algorithm stochastically quantizes each dimension of each sample to K equally spaced levels and serves as the base algorithm for our gradient-based learning framework.
2. We make several improvements to the basic algorithm under the gradient-based learning scenario. Specifically, we attribute the estimation error of the base algorithm to perturbation error caused by privacy constraints, and quantization error. Then we utilize a gradient subsampling strategy to simultaneously reduce communication cost and improve private estimation utility. We also apply randomized rotation to reduce quantization error.
3. We verify the performance of sqSGD on benchmark datasets using standard neural architectures like LeNet (Lecun et al., 1998) and ResNet (He et al., 2016), and make systematic studies on the impact of both communication and privacy constraints. Specifically, under the same privacy and communication constraints, our model outperforms baseline algorithms that do not involve quantization by a significant margin.

heading: 2 RELATED WORK

text:
Communication-efficient FL Since its introduction in (Konečný et al., 2016), communication efficiency has been one of the central topics of FL (Konečnỳ et al., 2016; Kairouz et al., 2019). Konečnỳ et al. (2016) described two kinds of general approaches for improving communication efficiency: structured updates like randomized masking, and sketched updates like quantization methods. The design of sqSGD could be viewed as a combination of the aforementioned approaches.
Privacy-preserving FL As optimization via stochastic gradient methods remains the most representative task in federated learning, most privacy-preserving FL approaches are based on private SGD type algorithms like Abadi et al. (2016). McMahan et al. (2018) used a slightly tweaked central DP model to train large language models. Wei et al. (2020) derived federated aggregation schemes under the central DP model and discussed convergence properties. Bhowmick et al. (2018) justified using large privacy budgets in LDP settings, while still provide reasonable privacy guarantees against reconstruction attacks. However, most of the previous works on privacy-preserving FL did not address communication efficiency problems.
Gradient sparsification and quantization Gradient dropping methods threshold gradients based on either fixed single threshold (Aji & Heafield, 2017) or adaptively chosen thresholds (Chen et al., 2017) are reported to greatly reduce communication overhead. DGC (Lin et al., 2018) adopted more elegant refinements like accumulation correction and factor masking to achieve even higher compression ratios. FedSel (Liu et al., 2020) performed privatized gradient sparsification via adopting randomized response techniques to select the most significant gradient dimension. Gradient quantization methods like QSGD (Alistarh et al., 2017) or TernGrad (Wen et al., 2017) are able to achieve little performance degradation on large neural architectures using less than 4 quantization bits. Privatized versions of quantized SGD are recently proposed, cpSGD (Agarwal et al., 2018) adopts the central DP model and vqSGD (Gandikota et al., 2019) allows local DP model.

heading: 3 OUR MODEL

heading: 3.1 BASE MECHANISM

text:
As a starting point, we base our communication efficient mean estimation algorithm on the stochastic k-level quantization(Suresh et al., 2017) scheme: We assume a uniform upper bound U on the `∞ norm of any individual gradients over the whole course of the FL process. The quantization procedure is described as follows: Let K ≥ 2 be the desired quantization level. We quantize the gradient to a sequence of points −U = B1 < B2 < . . . , < BK−1 < BK = U , where
Bk = −U + 2(k − 1)U K − 1
(5)
The case for K = 2 corresponds to using only the endpoints {−U,U} for quantization. We will denote the quantization range as B = {Bk}Kk=1. For each dimension j ∈ [d] of the individual gradient Xj , we first locate Xj to one of the K bins via finding a k∗ such that Xj ∈ [Bk∗ , Bk∗+1) and round Xj to the boundary of the bin as:
X̂j =
{ Bk∗+1 with probability k∗(Xj−Bk∗ ) 2U
Bk∗ otherwise (6)
Note that X̂j is an unbiased estimator of Xj . The quantization scheme reduces the communication cost to d log2K bits per round per client.
Next we privatize X̂j by constructing a locally private unbiased estimator of X̂j (where we fix the randomness of the quantization step), thereby obtaining a locally private estimator of X with its value resides in Bd. To describe the privatization scheme we introduce some new notations: for ∀v1, v2 ∈ Bd, define M(v1, v2) = #{j : vj1 = v j 2} − #{j : v j 1 6= v j 2} where #C stands for the number of elements in the set C. For a given positive integer κ ∈ {0, . . . , d − 1}, let S(v;Bd) := {u :M(u, v) > κ} and S(v;Bd) := {u :M(u, v) ≤ κ}. The privatization procedure, which we termed PrivQuantK,∞, is summarized in Algorithm1. To state the privacy guarantee of PrivQuantK,∞, we identify two setups which corresponds to protection against inference and reconstruction attacks. The later case requires additional specifications for the priors and evaluation function held by the adversary, which we state as follows: we assume the evaluation function f to be a map from Y to a compact set C ⊂ Rr. For any absolutely continuous prior π on Y , we use πf to denote the induced prior on f . Let π0 be the uniform prior over C, we will be focusing on priors that belong to the following set:
Pf (ρ0) = { π : sup
y∈C log
dπf (y) dπ0(y) ≤ ρ0
} (7)
where ρ0 is a non-negative number. The set Pf (ρ0) characterize prior beliefs that are "not much more certain than uniformly random guessing" over all possible outcomes that belong to the image of the evaluation function. We state the theorem under the orthogonal reconstruction attack that uses the evaluation function fA(x) = Ax/ ‖x‖2 with A ∈ Rr×d an orthonormal matrix, i.e., AAT = Ir, and the reconstruction criterion is chosen as the `2 error Lrec(x, x′) = ‖x/ ‖x‖2 − x′/ ‖x′‖2‖ 2 2 . Theorem 1. For any K ≥ 2, Consider PrivQuantK,∞ as a mechanism parameterized by (κ, p). Let τ := dd+κ+12 e, and let (κ, p) be chosen such that the following relation holds:
p 1− p × ∑τ−1 `=0 ( d ` ) (K − 1)(d−`)∑d
`=τ ( d ` ) (K − 1)(d−`) ≤ e (8)
then Z is an unbiased estimator of X , i.e. E(Z) = X , with randomness jointly over the quantization step and sampling step. Moreover, we have the following privacy guarantees:
Inference attack protection PrivQuantK,∞(·, κ, p) is -locally differentially private.
Reconstruction attack protection with k ≥ 4 and a ∈ [0, 1], PrivQuantK,∞(·, κ, p) is ( √ 2− 2a, ω(a), fA)-protected against reconstruction for
ω(a) = √ 8 exp ( − (r − 1)a 2
2
) exp( + ρ0) (9)
The proof will be deferred to appendix A.1. Theorem 1 implies that, if the adversary aims at reconstructing a non-vanishing fraction of the private data with r = O(d), for small a that allows coarse reconstruction, we only need and ρ0 to be of smaller order than d to ensure that any reconstruction attack will not succeed with reasonable probability. Note for K = 2 levels and U = 1, algorithm 1 reduces to algorithm PrivUnit∞ in (Bhowmick et al., 2018).
We may view the estimation error of Z (measured in terms of `2 risk) as coming from two parties: one from the quantization step, and the other from the privatization step. In the following sections we will take closer looks at the two sources of error, and develop corresponding improvements. Indeed as verified by our empirical study (see section 4), certain improvements are necessary to achieve high-dimensional compatibility.
Algorithm 1 Private K-quantized `∞ Ball PrivQuantK,∞
Require: X ∈ [−U,U ]d, κ ∈ {0, · · · , d− 1}, p ≥ 12 , τ = d d+κ+1 2 e. 1: Quantize each coordinate of X to B using (6) to obtain X̂ ∈ Bd. 2: Sample a random vector V as follows: with probability p, V is sampled uniformly at random
from S(X̂;Bd); otherwise with probability 1 − p, V is sampled uniformly at random from S(X̂;Bd).
3: Calculate normalizing factor
m = p ( d−1 τ−1 ) (K − 1)d−τ∑d
`=τ ( d ` ) (K − 1)d−l
− (1− p) ( d−1 τ−1 ) (K − 1)d−τ∑τ−1
`=0 ( d ` ) (K − 1)d−l
return Z = 1m · V

heading: 3.2 IMPROVING PRIVATIZATION UTILITY VIA SELECTIVE GRADIENT UPDATE

text:
PrivQuantK,∞ provides an unbiased estimator of individual gradients, but the considerable amount of noise injected would hurt the training process. This defect is amplified in deep learning scenarios: empirically, Lin et al. (2018) observed that for many representative deep architectures, most of the gradient dimensions are nearly sparse. Hence privatizing the whole gradient vector would result in a high privatization error that is even orders of magnitude higher than the norm of the gradient itself.
The (almost) sparse structure of the gradients suggests a modification to the estimation scheme via privatizing and transmitting only a fraction of the gradient dimensions, which could be regarded as significantly reducing variance at the cost of a small amount of bias. Such techniques are closely related to gradient compression that sends a few most significant gradient dimensions (Lin et al., 2018). Typically, gradient compression techniques require selecting top-k gradients measured in absolute magnitude (Lin et al., 2018; Aji & Heafield, 2017). A straightforward extension to the local private setting would be to perform private selection methods like exponential mechanism (Dwork et al., 2014) or noisy top-k (Ding et al., 2019), for which we need to allocate a certain fraction of privacy budget. However, these solutions are either computationally expensive or "too noisy" for picking high dimensional gradients that are almost sparse. We defer a more detailed discussion to appendix A.2.
Motivated by algorithm designs in distributed learning like random masking (Konečnỳ et al., 2016) and Hogwild! (Niu et al., 2011), we utilize a simple strategy, gradient subsampling, by randomly sample d̃ = brdc dimensions, where r is the sampling proportion of gradient dimensions. To further improve training efficiency, we applied local accumulation techniques like momentum correction and factor masking similar to (Lin et al., 2018). It is worth noting that low sampling ratio do not necessarily improves model performance as the overall bias of the sparse approximation would become significant when only a few dimensions are selected. A more detailed study of this aspect is provided in appendix A.3.

heading: 3.3 IMPROVING QUANTIZATION PERFORMANCE VIA RANDOMIZED ROTATION

text:
As shown in (Agarwal et al., 2018; Suresh et al., 2017), for a d-dimensional vectorX , the quantization error scales with ( maxj∈[d]X j −minj∈[d]Xj )2
. To reduce quantization error, an effective way is to preprocess the data via randomized rotation, so as to make maxj∈[d]Xj − minj∈[d]Xj small in expectation. Note that we only need to rotate the fraction of gradient that are selected to get transmitted.
To perform randomized rotation we need to assume public randomness between the server and the clients, under which we generate an orthogonal random matrix R ∈ Rd̃×d̃ and apply the linear transform to the individual gradients X̃ = RX on the client side, and apply inverse transform on the server side Z̃ = R−1Z. We adopt the method in (Agarwal et al., 2018; Suresh et al., 2017) to generate R that support fast matrix multiplication with O(d log d) time and O(1) space. Specifically, we generate R = 1
d̃ HA where A is a random diagonal matrix with i.i.d. Rademacher entries (i.e.
P(Aii = 1) = P(Aii = −1) = 0.5,∀i ∈ [d̃]), and H is a Walsh-Hadamard matrix (Horadam, 2012), defined recursively by the formula:
H(21) = [ 1 1 1 −1 ] , H(2m) = [ H(2m−1) H(2m−1) H(2m−1) −H(2m−1) ] , (10)
The randomized rotation operation is performed before quantization and privatization, therefore we project the vector X to an `2 ball of radius U before rotation. This would ensure the vector obtained after rotation has `∞ norm bounded by U as well.
The final selective SGD updating process is summarized in algorithm 2. The randomized rotation and sparsification strategy have no effect on privacy level, hence the local update within a single round is -LDP. At the same time, communication cost was further reduced from O(d log2K) bits to O(d̃ log2K) bits per client.
Algorithm 2 sqSGD: Selective Quantized SGD with local privacy guarantee
Require: Training data {Yi}Mi=1, gradient norm bound U , privacy budge , sampling ratio r ∈ (0, 1), local correction factor α, β, learning rate η, batch size B.
1: Find a (κ , p ) pair that satisfies relation (8) 2: Calculate the corresponding normalizing constant m as in algorithm 1 3: Set d̃ = 2blog2(rd)c, and using public randomness to generate a random matrix R ∈ Rd̃×d̃,
according to the construction in (10) 4: Initialize model parameter θ0 and local residuals resi,0 = 0,∀i = 1, . . . , N 5: for t = 0, . . . , T − 1 do 6: Sample a batch of indices St ∈ [N ] with size B 7: for s ∈ S do 8: //* Client Side Update *// 9: Select a uniformly random subset of [d] with cardinality d̃, denoted as Ds,
10: also let DCs denote [d]\D. 11: Calculate local (stochastic) gradient with respect to client data Xs,t = g(Ys,t, θt) 12: Clip the local gradient to the `2 ball with radius U 13: Accumulate and Apply rotation X̃s,t = R (resi,t[Ds] + βXs,t[Ds]) 14: Rotate and update local residual ress,t+1[DCs ] = ress,t[DCs ] + αXs,t[DCs ] 15: and ress,t+1[Ds] = 0 16: Calculate Zs,t = PrivQuantK,∞(X̃s,t, κ , p ) 17: Upload (Zs,t/m ,Ds) to the server 18: //* Server Side Update *// 19: Gradient update step θt+1 = θt −R−1 ηB ∑ s∈S Z dense s,t , where Z dense s,t is the d− dimensional 20: zero vector with indices in Ds replaced by Zs,t. return θT

heading: 4 EXPERIMENTS

text:
In this section, we apply sqSGD to simulated FL environments, constructed via standard datasets MNIST (Lecun et al., 1998), EMNSIT (Cohen et al., 2017), and Fashion MNIST (Xiao et al., 2017) which we abbreviate as FMNIST hereafter. All three datasets are of equal (training) sample size, therefore we randomly partition each dataset into 10 equally sized blocks to simulate a cross-silo FL environment consisting of a central server and 10 clients.
We train on MNIST and EMNIST datasets using the LeNet-5 architecture (Lecun et al., 1998) (119, 850 parameters). We also train a larger network under the ResNet-110 architecture (1, 722, 224 parameters) on the FMNIST dataset. Since the main goal of the empirical study is not to achieve state-of-the-art performance, we adopt the following common strategies without further tuning across all experiments: in each round, we randomly sample a single batch with batch size 32 for each client and compute a single gradient update step. Without gradient subsampling, this would be equivalent to a stochastic gradient descent update over the entire data with a batch size of 320. The training duration is measured via number of epochs (1 epoch = 188 rounds). We use the same configuration
of learning rate η = 0.001 and local correction factors α = 1.0, β = 1.0 across all experiments. We set the `2 norm bound of the gradients U = 10 as it works reasonably well. Note that we could use a more elegant distributed private estimation of the `2 norm bound via sending privatized magnitude evaluated at different points of the parameter space, i.e. via mechanisms like ScalarDP in Bhowmick et al. (2018). Finally, for a given privacy budget , we use the following method to determine the value of (κ , p ): We set κ to be the largest integer such that the value of the left hand side of (8) is smaller than or equal to e0.9 , and p = e 0.1
1+e0.1 .
Choice of privacy budget across all the experiments we align the choice = O( √ d) with respect to the additional risk factor O(d/ 2) in private mean estimation (in comparison to non-private case). As the models used in our experiments are all of high dimension, the choice of high-epsilon will basically provide little protection against inference attacks. However, with respect to reconstruction attack specified in section 1.2 and the protection level (4), such choice still provide reasonable protection against reconstruction attacks if the adversary’s goal is to evaluate more than O( √ d) of the entries in the private data.
Impact of communication constraints We evaluate the performance of trained models using the test set accuracy. The privacy budget is chosen as = 400 for LeNet models and = 2000 for ResNet models. Sampling ratio is fixed at r = 0.5%. We vary the quantization level in the range {2, 8, 32} which corresponds to using {1, 3, 5} bits per client per dimension. The results are plotted in figure 1. The results indicate that a while 1-bit sqSGD is efficient in terms of communication cost, the quantization error results in significant degradation in model performance, both in the final accuracy after model convergence, and in the speed of convergence. A reasonable quantization level (i.e. larger than 3 bits) yields competitive performance.
Impact of privacy constraints Next we investigate the performance loss due to privacy constraints. We fix the sampling rate at r = 0.5% and quantization level at K = 16. For LeNet-5 architecture, we select from the set {200, 300, 400}, for ResNet-110 architecture, we select from the set {1000, 2000, 3000}. The results are plotted in figure 2. The results imply that with limited communication, we need high privacy budgets to ensure successful training on large models.
Baseline comparisons We compare sqSGD against two baselines:
Piecewise mechanism (PM) (Wang et al., 2019) PM is designed for mean estimation under local privacy model that improves accuracy upon the PrivUnit∞ algorithm in Bhowmick et al. (2018)
κ = 0. Although PM communicates real values, the multi-dimensional version of PM (Wang et al., 2019, Algorithm 4) samples a fraction of coordinates for perturbation hence we may view PM practically as a limited-communication mean estimation algorithm. For large d settings, we choose reasonably large values such that PM communicates raw perturbed gradients in b /2.5c dimensions. vqSGD Gandikota et al. (2019) vqSGD uses an communication-optimal distributed mean estimation algorithm that adopts vector quantization strategies. The per client communication cost of vqSGD is O(log d) for mean estimation task. The algorithm has trivial extensions to locally private settings using randomized response strategies (Gandikota et al., 2019). As discussed by the authors, for distributed optimization settings with high dimensional models. Variance reduction techniques are necessary, specifically one data point is communicated b times and server uses the average of b quantized gradients for aggregation. This makes the communication cost O(b log d). Note that in private settings this results in a caveat that privacy protection level is degraded under composition. In our experiments we will ignore this caveat and use variance reduction so that the communication of vqSGD matches that of sqSGD and PM.
We compare the three approaches across all tasks mentioned above under the same privacy budget. For sqSGD we use K = 16 for LeNet architectures and K = 128 for ResNet architectures, and we adjust the sampling ratio in sqSGD such that communication costs remain equal among all methods. The comparisons are presented in figure 3. Figure 3 shows that sqSGD consistently outperforms PM by a significant margin across all tasks under various privacy levels. vqSGD obtains comparable performance with sqSGD in relatively smaller models and high-privacy regime (Note that vqSGD approaches offer much worse privacy protections in this setting), but breaks down when models get larger. Overall, in high-dimensional settings, sqSGD provides much better optimization performance.
Additional experiments We present an experimental study on the effect of gradient subsampling in appendix A.3, and another study on the trade-off between quantization and subsampling in A.4. The results of additional experiments further justify the choice of sampling ratios and quantization levels in the above comparisons.

heading: 5 CONCLUSION

text: We studied privacy-preserving federated learning under the local differential privacy model. To achieve both communication efficiency and high-dimensional compatibility, we proposed a gradientbased learning framework sqSGD that is based on a novel private multivariate mean estimation scheme with controllable quantization levels. We applied gradient subsampling and randomized rotation to reduce estimation error of the base mechanism that exploits the specific structure of federated learning with large modern neural architectures. Finally, our designed algorithm was shown on standard datasets to be capable of training large models with random initializations, surpassing baseline algorithms by a significant margin.

heading: A APPENDIX

text:
A.1 PROOFS
Proof of theorem 1. Let u ∈ Bd and U ∼ Unif(Bd). The vector V ∈ Bd sampled as in algorithm 1, has p.m.f.
p(v | u) ∝ {
1/P(M(U, u) > κ) ifM(v, u) > κ 1/P(M(U, u) < κ) ifM(v, u) ≤ κ.
The event that M(U, u) = κ when d+κ+12 ∈ Z implies that U and u match in exactly d+κ+1 2 coordinates; the number of such matches is (
d (d+κ+1)/2
) . Computing the binomial sum, we have
P(M(U, u) > κ) = 1 Kd d∑ `=d d+κ+12 e ( d ` ) (K − 1)(d−`)
P(M(U, u) ≤ κ) = 1 Kd d d+κ+12 e−1∑ `=0 ( d ` ) (K − 1)(d−`)
(11)
Now we show unbiasedness via showing E[V | u = u] = m · u. We have
E[V | u = u] = pE[U | M(U, u) > κ] + (1− p)E[U | M(U, u) ≤ κ]
By rotational symmetry, it suffices to show:
E[V 1 | u = u] = pE[U1 | M(U, u) > κ]︸ ︷︷ ︸ Υ1 +(1− p)E[U1 | M(U, u) ≤ κ]︸ ︷︷ ︸ Υ2
For Υ1, we have:
Υ1 = 1
KdP(M(U, u) > κ) × d∑ `=τ u1(d ` ) (K − 1)d−` − ∑ w∈B\u1 w ( d ` ) (K − 1)d−`−1  = u1 KdP(M(U, u) > κ) × ( d− 1 τ − 1 ) (K − 1)(d−τ)
Where in the second equality we used the fact that ∑ w∈B w = 0. Similar calculations yield:
Υ2 = − u1 KdP(M(U, u) ≤ κ) × ( d− 1 τ − 1 ) (K − 1)(d−τ)
Combining the preceding display with (11), we have:
E[V 1 | u = u] = ( p ( d−1 τ−1 ) (K − 1)d−τ∑d
`=τ ( d ` ) (K − 1)d−l
− (1− p) ( d−1 dτ−1 ) (K − 1)d−τ∑τ−1
`=0 ( d ` ) (K − 1)d−l
) × u1
= mu1
Next we show privacy guarantee.
LDP guarantee As P(M(U, u) > κ) is decreasing in κ for any u, u′ ∈ Bd and v ∈ Bd we have
p(v | u) p(v | u′) ≤ p 1− p · P(M(U, u ′) ≤ κ) P(M(U, u) > κ) = p 1− p × ∑τ−1 `=0 ( d ` ) (K − 1)(d−`)∑d
`=τ ( d ` ) (K − 1)(d−`)
The result follows by relation (8)
Reconstruction protection guarantee the result follows by Bhowmick et al. (2018, Proposition 1) and the LDP guarantee.
A.2 ON THE PRACTICALITY OF PRIVACY-PRESERVING SELECTION METHODS
Performing top-k selection with local privacy constraints could be done via two approaches. The first take is iteratively running the exponential mechanism (Dwork et al., 2014) for k times, each time selecting a single index with gumble noise. The bottleneck of this take is that it requires sampling from a high dimensional distribution for k times, which is computationally heavy. Note that the privatization step is carried out on the client side device, which is usually assumed to be of limited computational power in FL settings (Kairouz et al., 2019), thus using iterative exponential mechanism is not practical for FL scenarios. The second take is the noisy top-k algorithm (Ding et al., 2019), which generalizes the report noisy max mechanism in Dwork et al. (2014). The algorithm requires adding Laplacian noise of scale 2Uk/ to each dimension of the gradient vector. In practice, k is typically chosen at the order of hundreds. Since most of the gradients are very small in magnitude,to ensure reasonable noise requires a high budget to allocate for the selection step. This would significantly affect the overall privacy level.
A.3 EXPERIMENTS ON THE EFFECT OF GRADIENT SUBSAMPLING
In this experiment, we investigate the effect of subsampling under the setup of training a ResNet110 model on the FMNIST dataset. We fix the privacy level at = 2000 and quantization level at K = 16. We vary the subsampling ratio from the set {1, 5, 10, 50} × 10−3. The results are plotted in figure 4. It could be seen from the plot that using a high sampling ratio severely hurts the training performance, while also incurs more communication. It is thus necessary to perform subsampling. However, using a very low subsampling ratio also causes training failure. This phenomenon will be further explored in the next experiment.
A.4 EXPERIMENTS ON THE TRADE-OFF BETWEEN QUANTIZATION AND SAMPLING
In this experiment, we study the trade-off between quantization and sampling under the setup of training a LeNet-5 model on the MNIST dataset. We fix the privacy level at = 400, and fix the total communication cost per client, measured using the product r log2K. We vary the quantization level in the range {2, 8, 32, 128} which corresponds to using {1, 3, 5, 7} bits per client per dimension, and the sampling rate are adjusted accordingly. The results are shown in figure 5. The results suggest that increasing the quantization level may not monotonically increase training performance. This is mainly due to the random subsample scheme of sqSGD, under which the structure of gradients is not fully explored.


summaries: This submission works on the neural machine translation problem. The authors extend the previous works on leveraging language statistics or prior knowledge (SMT model or whatever) in LSTM based NMT models in self-attention based NMT models, Transformer model. The authors propose two alternatives to incorporate prior knowledge, which are the word frequency information for the monolingual data and the prior translation lexicon information for the bilingual data. These resources are integrated into the hidden representations from the self-attention computations and then the two output hidden representations are gated together for upper computations. The experiments are conducted on two typical NMT datasets: WMT14 En->De and WMT17 Zh->En, the results show that the proposed method can improve the NMT model performances.

summaries: This paper proposes a method to introduce **prior knowledge** into Transformer-based sentence encoders, here in the context of neural machine translation (NMT). More concretely, the prior knowledge is represented in the form of a matrix $\boldsymbol{M}$, where each row denotes a vector of prior knowledge associated with each word $x_i$. The prior knowledge matrix $\boldsymbol{M}$ is then represented as a (key, value) pair that can be attended by the query matrix $\boldsymbol{Q}$ (the same query matrix as used in the main NMT component) using a standard Transformer self-attention mechanism. This procedure results in a prior knowledge representation matrix $\boldsymbol{PK}$, which is then combined with the standard Transformer encoder output using a simple gating mechanism.

summaries: This paper presents a method for introducing prior knowledge into Transformer models. More specifically, the authors propose to use an additional self-attention block to incorporate prior knowledge about the word frequency and translation lexicon and use a gating mechanism to combine its output with that of the standard sefl-attention block. Experiments are conducted using English-to-German and Chinese-to-English translation datasets, and the results show the effectiveness of the proposed approach.

abstractText: Self-attention networks (SANs) have shown promising empirical results in various natural language processing tasks. Typically, it gradually learning language knowledge on the whole training dataset in parallel and stacked ways, thereby modeling language representation. In this paper, we propose a simple and general representation method to consider prior knowledge related to language representation from the beginning of training. Also, the proposed method allows SANs to leverage prior knowledge in a universal way compatible with neural networks. Furthermore, we apply it to one prior word frequency knowledge for the monolingual data and other prior translation lexicon knowledge for the bilingual data, respectively, thereby enhancing the language representation. Experimental results on WMT14 English-to-German and WMT17 Chinese-toEnglish translation tasks demonstrate the effectiveness and universality of the proposed method over a strong Transformer-based baseline.

authors:
Tamer Alkhouli
Gabriel Bretschner
Hermann Ney

title: On the alignment problem in multi-head attention-based neural machine translation

venue: In Proceedings of the Third Conference on Machine Translation: Research Papers,

authors:
Philip Arthur
Graham Neubig
Satoshi Nakamura

title: Incorporating discrete translation lexicons into neural machine translation

venue: In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing,

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

title: Neural machine translation by jointly learning to align and translate

venue: In Proceedings of the 3rd International Conference on Learning Representations,

authors:
Peter F. Brown
Stephen A. Della Pietra
Vincent J. Della Pietra
Robert L. Mercer

title: The mathematics of statistical machine translation: Parameter estimation

venue: Computational Linguistics,

authors:
Kehai Chen
Rui Wang
Masao Utiyama
Eiichiro Sumita

title: Content word aware neural machine translation

venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics,

title: Hierarchical phrase-based translation

authors:
Michael Collins
Philipp Koehn
Ivona Kučerová

title: Clause restructuring for statistical machine translation

venue: In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05),

authors:
Chris Dyer
Victor Chahuneau
Noah A. Smith

title: A simple, fast, and effective reparameterization of IBM model 2

venue: In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,

authors:
Sarthak Garg
Stephan Peitz
Udhyakumar Nallasamy
Matthias Paulik

title: Jointly learning to align and translate with transformer models

venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing,

authors:
Jonas Gehring
Michael Auli
David Grangier
Yann Dauphin

title: A convolutional encoder model for neural machine translation

venue: In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics,

authors:
Jiatao Gu
Zhengdong Lu
Hang Li
Victor O.K. Li

title: Incorporating copying mechanism in sequence-to-sequence learning. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)

authors:
Shilin He
Zhaopeng Tu
Xing Wang
Longyue Wang
Michael Lyu
Shuming Shi

title: Towards understanding neural machine translation with word importance

venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),

authors:
Wei He
Zhongjun He
Hua Wu
Haifeng Wang

title: Improved neural machine translation with smt features

venue: In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence,

authors:
Sathish Reddy Indurthi
Insoo Chung
Sangha Kim

title: Look harder: A neural machine translation model with hard attention

venue: In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics,

authors:
Sébastien Jean
Kyunghyun Cho
Roland Memisevic
Yoshua Bengio

title: On using very large target vocabulary for neural machine translation

venue: In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing,

authors:
Philipp Koehn
Franz J. Och
Daniel Marcu

title: Statistical phrase-based translation

venue: In Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics,

authors:
Zuchao Li
Rui Wang
Kehai Chen
Masso Utiyama
Eiichiro Sumita
Zhuosheng Zhang
Hai Zhao

title: Data-dependent gaussian prior objective for language generation

authors:
Xuebo Liu
Derek F. Wong
Yang Liu
Lidia S. Chao
Tong Xiao
Jingbo Zhu

title: Shared-private bilingual word embeddings for neural machine translation

authors:
Yang Liu
Qun Liu
Shouxun Lin

title: Tree-to-string alignment template for statistical machine translation

venue: In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics,

authors:
Yang Liu
Yun Huang
Qun Liu
Shouxun Lin

title: Forest-to-string statistical translation rules

venue: In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics,

authors:
Thang Luong
Ilya Sutskever
Quoc Le
Oriol Vinyals
Wojciech Zaremba

title: Addressing the rare word problem in neural machine translation

authors:
Haitao Mi
Zhiguo Wang
Abe Ittycheriah

title: Vocabulary manipulation for neural machine translation

authors:
Jan Niehues
Eunah Cho
Thanh-Le Ha
Alex Waibel

title: Pre-translation for neural machine translation

venue: In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers,

authors:
Myle Ott
Sergey Edunov
Alexei Baevski
Angela Fan
Sam Gross
Nathan Ng
David Grangier
Michael Auli

title: fairseq: A fast, extensible toolkit for sequence modeling

venue: In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations),

authors:
Rico Sennrich
Barry Haddow
Alexandra Birch

title: Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)

authors:
Hendra Setiawan
Min-Yen Kan
Haizhou Li

title: Ordering phrases with function words

authors:
Hendra Setiawan
Min-Yen Kan
Haizhou Li
Philip Resnik

title: Topological ordering of function words in hierarchical phrase-based translation

venue: In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP,

authors:
Ilya Sutskever
Oriol Vinyals
Quoc V Le

title: Sequence to sequence learning with neural networks

venue: Advances in Neural Information Processing Systems

authors:
Zhaopeng Tu
Zhengdong Lu
Yang Liu
Xiaohua Liu
Hang Li

title: Modeling coverage for neural machine translation

venue: In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics,

authors:
Zhaopeng Tu
Yang Liu
Zhengdong Lu
Xiaohua Liu
Hang Li

title: Context gates for neural machine translation

venue: Transactions of the Association for Computational Linguistics,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Ł ukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
X. Wang
Z. Tu
M. Zhang

title: Incorporating statistical machine translation word knowledge into neural machine translation

venue: IEEE/ACM Transactions on Audio, Speech, and Language Processing,

authors:
Xing Wang
Zhengdong Lu
Zhaopeng Tu
Hang Li
Deyi Xiong
Min Zhang

title: Neural machine translation advised by statistical machine translation

venue: In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence,

authors:
Xing Wang
Zhaopeng Tu
Deyi Xiong
Min Zhang

title: Translating phrases in neural machine translation

venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,

authors:
Yiren Wang
Yingce Xia
Fei Tian
Fei Gao
Tao Qin
Cheng Xiang Zhai
Tie-Yan Liu

title: Neural machine translation with soft prototype

authors:
Davy Weissenbacher
Graciela Gonzalez-Hernandez (eds

title: Proceedings of the Fourth Social Media Mining for Health Applications (#SMM4H) Workshop & Shared Task, Florence, Italy, August 2019

authors:
Rongxiang Weng
Shujian Huang
Zaixiang Zheng
Xinyu Dai
Jiajun Chen

title: Neural machine translation with word predictions

authors:
Joern Wuebker
Spence Green
John DeNero
Saša Hasan
Minh-Thang Luong

title: Models and inference for prefix-constrained machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)

authors:
Jian Yang
Shuming Ma
Dongdong Zhang
Zhoujun Li
Ming Zhou

title: Improving neural machine translation with soft template prediction

authors:
Jingyi Zhang
Hai Zhao

title: Improving function word alignment with frequency and syntactic information

venue: In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence,

authors:
Yang Zhao
Yining Wang
Jiajun Zhang
Chengqing Zong

title: Phrase table as recommendation memory for neural machine translation

venue: In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence,

authors:
Long Zhou
Wenpeng Hu
Jiajun Zhang
Chengqing Zong

title: Neural system combination for machine translation

heading: 1 INTRODUCTION

text:
Self-attention networks (SANs) have attracted increasing attention in the natural language processing community. Instead of using complex recurrent or convolutional neural networks (Sutskever et al., 2014; Bahdanau et al., 2015), SANs first use the positional encoding mechanism Gehring et al. (2017) to encode order dependencies in the language. The learned positional embedding is then added to corresponding word embedding to obtain an input representation, based on which SANs perform (multi-head) and stack (multi-layer) self-attentive functions (Vaswani et al., 2017) in parallel to learn language representation. The SAN-based models are iteratively optimized to model language knowledge on the whole training dataset, which has achieved state-of-the-art performance in many natural language processing tasks pairs (Barrault et al., 2019; Oepen et al., 2019; Weissenbacher & Gonzalez-Hernandez, 2019; Demner-Fushman et al., 2019).
Despite the success, SANs gradually model language knowledge on the batch-level datasets and does not consider the prior knowledge on the whole dataset from the beginning of training, which may decrease its language representation capability. For example, the SAN-based neural machine translation (NMT) model often mistranslate into words that seem to be natural in the target language sentence, but do not reflect the original meaning of the source language sentence (Arthur et al., 2016; Wang et al., 2017a). As a result, the NMT model produces fluent yet sometimes inadequate translations (Tu et al., 2016; 2017). To address this issue, recent studies explored the prior knowledge which has the stringer ability to model the fluency of translation in traditional SMT (Koehn et al., 2003; Liu et al., 2006; Chiang, 2007; Liu et al., 2007). Take the prior translation lexicon knowledge as an example, Arthur et al. (2016) directly biased or interpolated the bilingual lexicon translation distribution with the output of the softmax layer of NMT to improve the translations of infrequency words. An auxiliary classifier (Zhao et al., 2018; Wang et al., 2018) were employed to integrate the SMT recommendations with NMT generations to generate the faithful translation. In addition, the phrase translation rules was as the recommendation memory to make better predictions in NMT (Wang et al., 2017b; Zhao et al., 2018). Although these studies successfully improved the issue of inadequate translations in NMT, they tended to focus on exploring the prior translation lexicon knowledge by using their specific methods. In other words, these unique methods make it difficult to explore other prior knowledge in a universal way and to determine which of the prior knowledge and the unique method this improvement comes from. Meanwhile, these studies directly
utilized the probability distribution of the prior knowledge and lacked the neural network’s ability to semantically generalize, while will further hinder the language representation ability of SANs.
In this paper, we propose a simple and general representation method to introduce the prior knowledge into SANs. In particular, we package the prior knowledge related with one source sentence to a continuous space matrix, which allows SANs to utilize the prior knowledge from the beginning of training, thereby better performing language representation in a universal way compatible with neural networks. To maintain the simplicity and flexibility of the SANs, we use the prior knowledge representation in parallel and stacked ways to learn the representation of the input sentence. Furthermore, we use the proposed method to explore one prior word frequency knowledge for the monolingual data and other prior translation lexicon knowledge for the bilingual data, respectively. Empirical results on two widely used translation data sets, including WMT14 English→German and WMT17 Chinese→English, to verify the effectiveness and universality of the proposed method over a strong Transformer-based baseline.

heading: 2 SELF-ATTENTION NETWORKS

text:
The self-attention networks (SANs) (Vaswani et al., 2017) is composed of a stack of N identical layers, each of which includes two sub-layers. Formally, given a input sentence with the length J , X={x1, x2, · · · , xJ}, the positional encoding mechanism (Gehring et al., 2017) is used to compute a positional embedding of each word based on its position index. The positional embedding is then added to the corresponding word embedding as an combined embedding, thereby gaining a sequence of input representation H0={v1, v2, · · · , vJ}. Moreover, the stacked SANs is organized as follows:
Hn = LN(SelfAttn(Qn−1,Kn−1,Vn−1) + Hn−1), Hn = LN(FFNn(Hn) + Hn), (1)
where SelfAttn(·), LN(·), and FFNn(·) are self-attention module, layer normalization (Ba et al., 2016), and feed-forward network for the n-th identical layer, respectively. Qn−1, Kn−1, and Vn−1 are query, key, and value matrices that are transformed from the (n-1)-th layer Hn−1. For example, Q0, K0, and V0 are packed from the H0 learned by the positional encoding mechanism (Gehring et al., 2017). In particular, SelfAttn(·) is applied on the {Qn−1, Kn−1, Vn−1} of the n-1 layer:
SelfAttn(Qn−1,Kn−1,Vn−1) = softmax(Qn−1Kn−1>/ √ dmodel)Vn−1, (2)
where dmodel is the dimension size of the query and key vectors. As a result, the output of the N -th layer HN is the representation of the input sentence. Moreover, the self-attention mechanism can be further refined as multi-head self-attention to jointly attend to the information from different representation sub-spaces at different positions.

heading: 3 PRIOR KNOWLEDGE REPRESENTATION

text:
In this section, we propose a simple and general representation method to encode the prior knowledge, which allows SANs to model the prior knowledge in a manner compatible with neural networks. Given a input sentence X={x1, x2, · · · , xJ} with the length J , we represent the associated prior knowledge as a matrix M:
M =  m11 m21 · · · mK1 m12 m22 · · · mK2 ... ... . . . ...
m1J m2J · · · mKJ  , (3) where each row denotes the prior knowledge related with word xj and each element mtj is a fixed size vector. Also, M is packed into a key and value matrix pair {K, V} for the prior knowledge. The prior {K, V} and the current Q are the input to the self-attention mechanism (see Eq.(2)) to learn a prior knowledge representation PK for the input sentence X:
PK = LN(SelfAtt(Q,K,V) + H), (4)
where Q is transformed from the current sentence representation H, for example, the n-th layer output Hn of the stacked SANs in Eq.(1). Finally, PK is the expected prior knowledge representation (PKR). Later, we will apply the proposed method to one prior word frequency knowledge for the monolingual data and other prior translation lexicon knowledge for the bilingual data, respectively, thereby enhancing the language representation.

heading: 3.1 WORD FREQUENCY BASED PRIOR KNOWLEDGE REPRESENTATION

text:
Recent studies have shown the effectiveness of the prior word frequency information for improving the translations of content words (Arthur et al., 2016; Wang et al., 2018; He et al., 2019; Chen et al., 2020). Intuitively, these content words generally have more meanings and lower word frequency than function words in one sentence. To capture the prior knowledge, we use word frequency information to enhance the importance of content words in the sentence representation. Inspired by the previous studies (Setiawan et al., 2007; 2009; Zhang & Zhao, 2013; Chen et al., 2020), we use the frequency of each word w on the monolingual corpus F to distinguish content words and function words in the input sentence. To this end, let the B most frequent words in the monolingual corpus denote the function words while the remaining words are regarded as content words for the input sentence. In other words, let the prior word frequency knowledge of each word denote a binary mask:
fj = { 0, xj ∈ B 1, xj /∈ B
(5)
Furthermore, the prior word frequency knowledge of the input sentence is a diagonal matrix according to Eq.(3):
MF =  f1 0 · · · 0 0 f2 · · · 0 ... ... . . .
... 0 0 · · · fJ  . (6) Finally, we use MF to mask the representation of function words in H, and thereby gain key and value matrices {KF , VF } to learn a prior word frequency based PKR PKF for the input sentence:
PKF = LN(SelfAtt(Q,KF ,VF ) + H), (7) where Q is transformed from the current sentence representation H, for example, Hn in Eq.(1).

heading: 3.2 BILINGUAL TRANSLATION LEXICON BASED PRIOR KNOWLEDGE REPRESENTATION

text:
We apply the proposed PKR method into the prior bilingual translation lexicons in SMT (Brown et al., 1993). Discretely, each source word xj has multiple associated target translation options retrieved from the bilingual translation lexicon table. For simplicity, we select the top L target translation options as the prior translation knowledge of word xj are remained according to their lexicon translation probabilities and the entry corresponds to the target word. Formally, all retrieved lists for the input sentence X are constructed as a J×K×dmodel prior translation knowledge matrix MT according to Eq.(3):
MT =  t11 t21 · · · tL1 t12 t22 · · · tL2 ... ... . . .
... t1J t2J · · · tLJ  . (8) where each row corresponds to the retrieved list of the word xj , and the entry corresponds to the embedding of the target word. In particular, when the number of the associated target words for one source word xj is less than L, we use the embedding of a special placeholder “/” to fill the j-th row in MT up to L. Also, the MT is packed into a key and value matrix pair {KT , VT }. {Q, KT , and VT } are the input to Eq.(4) to learn a prior translation knowledge representation PKT for the source sentence: PKT = LN(SelfAtt(Q,KT ,VT ) + H), (9) where Q is transformed from the current sentence representation H, for example, Hn in Eq.(1).
4 SANS WITH PRIOR KNOWLEDGE REPRESENTATION
Intuitively, the prior knowledge assists SANs to enhance the language representation in the SAN-based models of NLP tasks. In other words, the prior knowledge plays an auxiliary role during the processing of learning language representation. Therefore, we compute a gate scalar gn ∈ [0, 1] to weight the expected importance of the prior knowledge representation PK at the n-th layer:
gn = Sigmoid(Ung H n + Wng PK), (10)
where the Sigmoid is an active function, and Wng∈Rdmodel×1 and Ung∈Rdmodel×1 are model parameters. We then fuse Hn and PK through the gate scalar gn to learn the sentence representation at the nth layer:
Hn = Hn + gn · PK. (11) Also, the new stacked SAN is formally denoted as the modified version of Eq.(1):
Hn = LN(SelfAttn(Qn−1,Kn−1,Vn−1) +Hn−1), PKn = LN(SelfAttn(Qn,K,V) + Hn), gn = Sigmoid(Ung H n + Wng PK n), Hn = Hn + gn · PKn, Hn = LN(FFNn(Hn) +Hn),
(12)
where H0 is the initialized sentence representation H0 as in the Section 2. As a result, there is a more effective sentence representation HN for the input sentence. Later, HN will be fed into the Decoder of the SAN-based model to model NLP tasks, for example, machine translation task.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENT SETUP

text:
In this paper, we selected the machine translation task to evaluate the effectiveness of the proposed method, that is, two widely-used datasets: The WMT14 En-De includes 4.43 million bilingual sentence pairs, and the newstest2013 and newstest2014 datasets were used as the validation set and test set, respectively; The WMT17 Zh-En includes 22 million bilingual sentence pairs, and the newsdev2017 and newstest2017 datasets were used as the validation set and the test set, respectively. In the experiment, we first used the fast align toolkit Dyer et al. (2013) to obtain word alignments from the source language to the target language. We then learned bilingual translation lexicon table between each word pair from the bilingual parallel training data with word alignments.
The byte pair encoding algorithm (Sennrich et al., 2016) was adopted, and the vocabulary size was set to 40K. For the Transformer base NMT, the dimension of all input and output layers was set to 512, the dimension of the inner feedforward neural network layer was set to 2048, and the total heads of all multi-head modules were set to 8 in both the encoder and decoder layers. In each training batch, there was a set of sentence pairs containing approximately 4096×8 source tokens and 4096×8 target tokens. During training, the value of label smoothing was set to 0.1, and the attention dropout and residual dropout were p = 0.1. The learning rate was varied under a warm-up strategy with warmup steps of 8,000. For evaluating the test sets, we used a beam size of 4 for decoding, and evaluated tokenized case-sensitive BLEU with the averaged model of the last 5 checkpoints for Transformer base model and 20 checkpoints for Transformer big model saved with an interval of 2,000 training steps. Following the training of 300,000 batches, the model with the highest BLEU score for the validation set was selected to evaluate the test sets. For the other setting not mentioned,
we followed the setting in Vaswani et al. (2017). All models were trained on eight V100 GPUs and evaluated on a single V100 GPU. The multi-bleu.perl script was used as the evaluation metric for the three translation tasks, and signtest (Collins et al., 2005) was used as the statistical significance test. We implemented the proposed NMT models on the fairseq toolkit (Ott et al., 2019).

heading: 5.2 BASELINE SYSTEMS

text:
Trans.base/big: a vanilla Transformer-based base/big models (Vaswani et al., 2017). Both Trans.base and Trans.big models differ at the hidden size (512 vs. 1024), filter size (2048 vs. 4096), and the number of attention heads (8 vs. 16).
+Shared-private: It proposes shared-private bilingual word embeddings (Liu et al., 2019), which give a closer relationship between the source and target embeddings in the Transformer-based NMT.
+SoftPrototype: Each word in the input sequence is mapped into a distribution over the target vocabulary, and the weighted average of target word embeddings is treated as an “expected” word representation in the prototype R for the Transformer-based NMT model. It allows the Decoder to have indirect access to both past and future information (Wang et al., 2019).
+D2GPo: A kind of data-dependent Gaussian prior objective is proposed to build two probability distributions for the Transformer-based NMT, the first of which is from the detailed model training prediction and the second of which is from a ground-truth word-wise distribution (Li et al., 2020).
+BCWAContLoss: It used word frequency information to learn a sequence of content words for the source and target sentences. A content word-aware Transformer-based NMT model was designed to learn an additional content word-aware source representation and to utilize target content words to compute an additional loss during the training (Chen et al., 2020).
+Soft Template: It used extracted templates from tree structures as soft target templates to guide the translation procedure. We incorporate the prior template information into the encoderdecoder framework to jointly utilize the templates and source text to enhance the Transformer-based NMT (Yang et al., 2020).

heading: 5.3 TRANSLATION RESULTS

text:
Main Results: Table 1 showed the main results of WMT14 En-De and WMT17 Zh-En translation tasks. The BLEU scores of re-implemented Trans.base/big models were better than that of the original Trans.base/big models (Vaswani et al., 2017), which makes the evaluation convincing. As seen, our models (i.e., +PKF and +PKT ) and the comparison methods (+SoftPrototype, +Shared-private, +D2GPo, BCWAContLoss, and +Soft Template) were superior to the baseline Trans.base/big models. This indicates that introducing the prior knowledge consistently improved translation performance, demonstrating the effectiveness of the proposed prior knowledge representation approach.
Evaluating Prior Knowledge: Based on the proposed prior knowledge representation approach, the prior word frequency knowledge (+PKF ) and the prior translation lexicon knowledge (+PKT ) gained the improvement of BLEU scores on the Trans.base/big models. This indicates that the proposed approach provided a universal setting to better verify the effectiveness of two prior knowledge compare to the comparison models (i.e., +SoftPrototype, +Shared-private, +D2GPo, BCWAContLoss, and +Soft Template) with their specific methods. Furthermore, BLEU scores of +PKT were higher than that of +PKF , that is, two types of prior knowledge have different improvements. The difference means that the improvement comes more from the prior knowledge itself rather than the method.
Comparison with Previous Works: Trans.base +PKF was superior to +Shared-privat and +D2GPo while it was slightly inferior to Trans.base +BCWAContLoss. PKF only focused on exploring the importance of source content words while BCWAContLoss captured the importance of source and target content words. In comparison, Trans.big +PKF was slightly superior to Trans.base +BCWAContLoss. The reason may be that the proposed approach can make full use of the prior word frequency knowledge on the Trans.big setting. +PKT outperformed +SoftPrototype, +Sharedprivate and +D2GPo and +BCWAContLoss on the Trans.base/big settings while it was slightly inferior to +Soft Template on the Trans.big seting. The reason may be that +Soft Template encoded the syntax constraint in addition to the prior translation knowledge.
Model Parameters and Training Speed: Take the En-De translation task as an example in Table 1, Trans.base +PKF and +PKT models contained approximately 1.5% additional parameters while both they decreased 8.3%/12.1% the training speeds, compared to the baseline Trans.base model. Meanwhile, Trans.base +PKT model achieved a comparable performance compared to the baseline Trans.big model which has many more parameters. This indicates that the improvement is indeed from prior knowledge rather than more parameters.
5.4 MODEL CONVERGENCE
In this section, we tried to verify whether the introduction of prior knowledge has an impact on the training process. Specifically, for Trans.base, +PKF , and +PKT models, we observed their BLEU scores on the En-De valid set every five epoch intervals as shown in Figure 2. As seen, the learning curves of +PKF and +PKT are that of Trans.base, confirming the effectiveness of the prior translation lexicons and word frequency knowledge. Also, BLEU scores of +PKF and +PKT had been improving from the 5-th Epoch to the 55-th and 45-th Epochs, respectively. Thus, +PKF and +PKT reached the highest BLEU scores at the 55-th and 45-th Epochs. This means that +PKT converged faster than +PKF during
the training. This may be that the target language knowledge is advanced to the Encoder of NMT to learn a more effective representation of the source sentence.

heading: 5.5 PROBING EXPERIMENT

text:
Following the word prediction experiment in (Weng et al., 2017)’s work, we also did a similar probing experiment here to evaluate the source representation learned by the proposed SANs with PKF and PKT . In detail, for each sentence in the test set, we use the final source representation to make a prediction about the
possible source words. Given the set of top C words in the target vocabulary and the set of words in all the references as R, and the precision of the word prediction: Precision = |C ∩ R|/|C| × 100. We then trained a bag-of-words predictor by maximizing P (ybow|H
N ), where ybow is an unordered set containing all target words in the output sentence. In addition to the structure of SANs with PKF and PKT , the predictor included an additional feed-forward network layer which maps the final source sentence to the target word embedding matrix. Then, we compare the precision of target words in the top-N words which are chosen through the predicted probabilities. As shown in Table 2, +PKF and +PKT gained higher precision in all conditions, especially +PKT was higher than +PKF , which was consistent with the analysis that +PKT allows the target language knowledge to be advanced to the Encoder compare to +PKF . This shows that the proposed method can obtain more information about the target language sentence and partial answers to why the proposed NMT models could improve generation quality.
5.6 EVALUATING HYPER-PARAMETERS IN PKT AND PKF
The left sub-figure of Figure 3 showed the results of Trans.base model (black dotted line) and +PKT model with different hyper-parameter K for learning prior translation knowledge representation (colorful line) on the En-De and Zh-En test sets. When K is one of (0, 5, 10, 15, 20, 30), the result of Trans.base+PKT outperformed the Trans.base on the two test sets. Furthermore, Trans.base+PKT reached the point of highest BLEU score in K=10, K=15, and K=10 on the En-De and Zh-En test sets, respectively. Finally, we trained the proposed NMT models in the two translation tasks (See Table 1) according to this optimized hyper-parameter K.
Furthermore, we masked the function words in the source sentence according to a list of the B function words, thereby gaining the MF in Eq.(6). The right sub-figure of Figure 3 showed the results of Trans.base+PKF with the different number of the top B function words on the En-De and Zh-En test sets. Trans.base+PKF obtained the highest BLEU scores on both test sets over the Trans.base on modeling B = 256. The trained +PKF was as shown in Table 1.

heading: 5.7 TRANSLATING DIFFERENT LENGTH SENTENCES

text: To further evaluate our method, we showed the translation performance of source sentences with different sentence lengths. Specifically, we divided each test set into six groups according to the length of the source sentence, for example, “40” indicates that the length of sentences is between 30 and 40. Figure 4 shows the results of Trans.base, +PKF , and +PKT models on the two translation tasks. As seen, +PKF and +PKT were superior to the baseline Trans.base in almost every length group on the two tasks, confirming the effectiveness of our method. Also, BLEU scores of all models decreased when the length was greater than thirty over the Zh-En task. BLEU scores of all models decreased when the length was greater than forty over the En-De task. The reason may be more diverse vocabulary in Chinese than English and German. Thus, a target word was mapped to more source words in the prior translation lexicons, that is, increasing the ambiguity of the target word.

heading: 6 RELATED WORK

text: There were a variety of methods to combine the advantages of both the dominant NMT and traditional SMT models. Typically, the prior knowledge was used to enhance the NMT, for example, discrete dictionary (Luong et al., 2015; Jean et al., 2015; Arthur et al., 2016; Gu et al., 2016), the limitation of vocabulary (Mi et al., 2016; He et al., 2016; Indurthi et al., 2019), translation of certain terminology (Alkhouli et al., 2018), and translations and interpretable alignments (Garg et al., 2019). Wang et al. (2017a) combined NMT posteriors with SMT word recommendations through linear interpolation implemented by a gating function. Niehues et al. (2016) utilized the SMT model to pre-translate the inputs into target translations and employed the target pre-translations as input sequences in NMT. The combination of NMT and SMT had been also introduced in interactive machine translation to improve the system’s suggestion quality (Wuebker et al., 2016). Zhou et al. (2017) presented a neural system combination framework to directly combine NMT and SMT outputs. Different from the direct combination of SMT (Wang et al., 2017a; Wuebker et al., 2016; Niehues et al., 2016; Zhou et al., 2017), the proposed method allows the prior knowledge to be introduced into NMT in a universal neural way. Meanwhile, the prior knowledge representation enables the NMT to semantically generalize the prior knowledge instead of directly combining the probability distribution of the prior translation knowledge.

heading: 7 CONCLUSION

text: This article explored a universal representation method to introduce the prior knowledge into the Transformer-based NMT in a universal way. In particular, the proposed method can represent the prior knowledge as a continuous space matrix to semantically generalize instead of directly combining the probability distribution of the prior translation knowledge, thereby enhancing the representation of the input sentence. Experimental results verified the effectiveness of our method on the two wildly used translation tasks. In the future, we will adopt the proposed method to other natural language processing tasks and explore more effective prior knowledge.

heading: A BILINGUAL TRANSLATION LEXICONS IN SMT

text:
The goal of machine translation is to translate a source sentence X =xJ1 into a target sentence Y =y I 1 , where xj and yi belong to the source vocabulary Vx, and the target vocabulary Vy , respectively. In the traditional SMT systems, bilingual lexical translation rules are generally learned directly from the large-scale bilingual parallel data in an unsupervised fashion using the IBM models (Brown et al., 1993; Koehn et al., 2003). These models can be used to estimate the word alignments a and lexical translation probabilities p(a)(y|x) between the words of the two language through the expectation maximization algorithm. First, in the expectation step, the algorithm estimates the expected count c(x, y). In the maximization step, lexical translation probabilities are calculated by dividing the expected count by all possible counts:
p(l,a)(y|x) = c(x, y)/ ∑ ŷ c(x, ŷ). (13)
As a result, there is a list table in which each source word is linked to a set of possible target candidate translations, called bilingual lexicon translation table T = {x, y, p(a)(y|x)} from source language to target language.