extfieldsofstudy:
Computer Science
Mathematics

text:
Flexible Cache-Aided Networks with Backhauling

Caching at the edge is a promising technique to cope with the increasing data demand in wireless networks. This paper analyzes the performance of cellular networks consisting of a tier macro-cell wireless backhaul nodes overlaid with a tier of cache-aided small cells. We consider both static and dynamic association policies for content delivery to the user terminals and analyze their performance. In particular, we derive closed-form expressions for the area spectral efficiency and the energy efficiency, which are used to optimize relevant design parameters such as the density of cache-aided small cells and the storage size. By means of this approach, we are able to draw useful design insights for the deployment of highly performing cache-aided tiered networks.

I. INTRODUCTION
A tremendous increase in smartphone usage during the last decade resulted in a 4000-fold mobile data traffic explosion in cellular networks [1]. In this setting, mobile operators constantly look for innovative solutions to satisfy performance indicators such as higher spectral and energy efficiency, improved coverage, and lower end-to-end delays: this calls for the development of innovative techniques at both device and network level in the coming years [2]. Caching at the edge is regarded as one of the most promising approaches to cope with the increasing data demand [3]. This is particularly true for heterogeneous and tiered network layouts, for which the extent of the performance gains brought by caching has been extensively assessed in terms of several performance metrics of practical relevance. For instance, [4] and [5] focus on optimal probabilistic caching policies for enhanced content delivery, [6] studies the impact of caching on the coverage and on the delay experienced by the user terminals (UTs), and [7] jointly considers caching, routing, and channel assignment strategies for collaborative small cells (SCs).
Along similar lines, this work analyzes the system performance of cache-aided tiered networks comprised of a tier of macro-cell backhaul (BH) nodes overlaid with a tier of non-cooperative SCs [8]. Each SC in the considered network has (limited) storage capabilities and pre-fetches popular files before the downlink transmission to its associated UTs. In this context, and differently from what has been previously proposed in the literature, our goal is to optimize relevant performance metrics for network planners and operators, and draw design guidelines for the deployment of highly performing cache-aided tiered networks. Using consolidated random spatial models to characterize the location of SCs, BHs and UTs [9], we investigate the area spectral efficiency (ASE) gains brought by caching popular files in the considered network using tools from stochastic geometry. To increase the generality and relevance of our study, we examine both static and dynamic association policies for content delivery to the UTs. In particular, in the static case, UTs can only be associated with SCs, regardless of the occurrence of cache hit/miss events at the latter; conversely, in the dynamic case, UTs are associated with SCs in case of cache hit and with wireless BHs otherwise.
The first contribution of this paper is the derivation of closed-form expressions and bounds for the ASE and the energy efficiency (EE) with the aforementioned UT association policies. Such expressions are subsequently used to optimize crucial design parameters such as SC density and storage size. Our findings highlight that the impact of caching on the ASE is minor as compared to that of the SC density, i.e., densifying the network is always more convenient than expanding the storage size at the SCs. Conversely, we show that increasing the storage size rather than the SC density is more effective in terms of EE of the network. In practice, the choice of investing on additional SCs or on more storage strongly depends on the goal of the network operator. Finally, it is worth observing that the performance of the considered network heavily hinges on the adopted UT association policy: a dynamic policy is always preferable whenever the network can support the larger complexity necessary for its effective implementation.

II. SYSTEM MODEL A. Network Model
Let us consider a set of mobile UTs in a two-tier ultradense network, where the lower tier comprises a set of noncooperative SCs ensuring network coverage and the upper tier consists in a set of BHs connected to the internet. In our model, each SC is associated with only one UT and one BH. We assume that the spatial distribution of the network nodes follows the stationary, independently marked Poisson point We use Φ SC {x} to denote the PPP of the SCs with spatial density λ (measured in SCs/m 2 ), with isotropic marks Φ UT u(Φ SC ) = {u(x)} x∈ΦSC and Φ BH b(Φ SC ) = {b(x)} x∈ΦSC representing the UTs and the BHs, respectively; evidently, Φ UT and Φ BH are dependent on Φ SC and have the same spatial density λ. In this setting, the employment of PPPs allows to capture the randomness of practical ultra-dense network deployments and, at the same time, obtain precise and tractable expressions for the system-level performance metrics [9]- [11]. Let r yz y−z denote the distance between nodes y, z ∈ Φ: the distances of the UTs and the BHs from their associated SCs are assumed fixed and are denoted by R UT r xu(x) and R BH r b(x)x , ∀x ∈ Φ SC , respectively, with R BH > R UT .

B. Caching Model and UT Association
Let F {f i } F i=1 be a F -sized subset of all the files available in the internet, entirely accessible by each BH. Without loss of generality, and for simplicity in the notation, we assume that all F files have identical lengths. In the following, we refer to F as file catalog. Each UT requests files from F with probability denoted by P {p 1 , p 2 , . . . , p F }, with F i=1 p i = 1, which hinges on the files popularity over the whole network.
To offload the overlaying BH infrastructure, each noncooperative SC x is equipped with a storage unit ∆ x of size S ≤ F (measured in files/SC). Suppose that, at a given time we have a cache miss event. In this regard, we use / ∆ x to denote a cache miss event at x. Accordingly, we introduce the indicator function where its logical complement is denoted by 1 ∆x .
The effectiveness of the adopted cache-aided approach depends on the probability that any file requested by a given UT is cached at its serving SC, which is referred to as cache hit probability and is denoted by P hit . This quantity typically depends on the adopted caching policy, content placement, and distribution of the UT requests. Further details on these aspects are unnecessary for the scope of our work and we refer to [3] and references therein for further details. Now, let R = T B ∈ R be the time-frequency resource used by the network for delivering one file from the BH tier to the UTs, with T ∈ R (resp. B ∈ R) defined as the amount of necessary time (resp. frequency) resources to perform this operation. Two UT association policies are considered in this work, i.e., static and dynamic. When the static UT association is adopted, operations in the two tiers occur on orthogonal resources. In this case, the UTs can only be served by their associated SCs, and the BH-to-SC/SC-to-UT links occupy two R 2 -sized resources: for instance, each link may use the entirety of B for half of the time (i.e., T 2 ) or the entirety of T for half of the bandwidth (i.e., B 2 ). Conversely, under dynamic UT association, operations in the two tiers occur on the same resource. In this case, the UTs are served by either the SCs or the BHs depending on the availability of the requested file at the SCs, and the SC-to-UT/BH-to-UT links occupy a R-sized resource. In practice, the second approach leads to a more efficient use of the time-frequency resource at the cost of more sophisticated inter-tier coordination and possibly  signaling. For notational simplicity, in the rest of the paper we differentiate between static and dynamic UT association by means of the super-indices S and D, respectively. The adopted UT association policy has a strong impact on the network response to a cache hit/miss event when UT u(x) requests file f i . In particular: 1) Static: If a cache hit occurs, then SC x transmits f i to u(x). Conversely, if a cache miss occurs, first x retrieves f i from its associated BH b(x), then transmits it to UT u(x). In both cases, an R 2 -sized resource is used by the SC-to-UT link due to the static UT association; 2) Dynamic: If a cache hit occurs, then x transmits f i to u(x). Conversely, if a cache miss occurs, u(x) can bypass x and connect directly to b(x) to download f i . In both cases, the whole resource R is used by either the SC-to-UT or the BH-to-UT link. A graphical representation of these operations, and their impact on the network resource usage, is provided in Figure 1.

C. Channel Model
In this work, all nodes have a single transmit/receive antenna. In addition, we assume that the SCs and the BHs transmit with powers ρ SC and ρ BH (measured in W), respectively. The propagation through the wireless channel combines pathloss attenuation and small-scale fading. For the former, we adopt the standard power-law pathloss model and define the pathloss function (y, z) r −α yz between nodes y, z ∈ Φ, with pathloss exponent α > 2. For the latter, we use h yz to denote the channel power fading gain between nodes y, z ∈ Φ: all channels are assumed to be subject to Rayleigh fading and, hence, h yz ∼ exp(1). 1 The signal-to-interference-plus-noise ratio (SINR) at SC x reads as where I x is the overall interference power at SC x and σ 2 is the additive noise power. Likewise, the SINR at UT u(x) reads as where I u(x) is the overall interference power at u(x).
respectively. On the other hand, in case of dynamic UT association, we are only interested in the interference at the UT and we thus have III. PERFORMANCE ANALYSIS The system performance is closely related to the probability of the UTs successfully receiving the requested content, which is termed as success probability. This depends on two factors, i.e., the cache hit probability (cf. Section II-B) and the SINRs of the file transmissions (cf. Section II-C). Thus, in the following, we derive the success probability using both the considered UT association policies.
Our analysis focuses on a randomly chosen SC x, and its marks u(x) and b(x), referred to as typical SC, typical UT and typical BH, respectively: due to Slivnyak's theorem and to the stationarity of Φ, these nodes are representative of the whole network [9]. For a given SINR threshold θ, we assume that a file is successfully received by the typical UT if SINR x > θ∧SINR u(x) > θ and SINR u(x) > θ for static and dynamic UT association, respectively. The success probability is formalized in the following theorem, where we use the notation Theorem 1. For static UT association, the success probability is given by are the Laplace transforms of the interference terms I u(x) in (4)-(5), respectively. For dynamic UT association, the success probability is given by with Ω(R UT , R BH , φ) R 2 UT +R 2 BH +2R UT R BH cos φ α 2 and where L (D) is the Laplace transform of the interference term I (D) u(x) in (6). Proof: See Appendix I.
Since a closed-form expression for the success probability P (D) suc (θ) in (11) is not available, we provide a useful lower bound in the following corollary.
Corollary 1. For dynamic UT association, the success probability can be lower-bounded as Proof: The lower bound is obtained by considering the worst-case distance between BH and UT, i.e., R BH + R UT (cf. [9]).
The expressions above can be used to obtain other useful performance metrics. In this paper, we focus on the achievable ASE (measured in bps/Hz/m 2 ), which is readily obtained as for static and dynamic UT association, respectively. At this stage, it is worth observing that, in practice, the distances R UT and R BH depend on the SC density λ. Thus, in the following we set R UT = βUT 2 √ λ and R BH = βBH 2 √ λ , with β BH > β UT ; observe that 1 2 √ λ represents the average distance between nodes in a PPP with spatial density λ. Figure 2 illustrates the achievable ASEs as defined in (14)-(15) against the cache hit probability P hit , with λ = 10 −2 SCs/m 2 , α = 4, θ = 1, σ 2 = 0 (i.e., interference limited case), ρ SC = 0.5 W, ρ BH = 1 W, β SC = 0.5, and β BH = 1 (the same parameters will be used in Section IV-A). The beneficial impact of caching is evident: as compared with the cache-free setup (which corresponds to P hit = 0), the achievable ASE with P hit = 0.25 (resp. P hit = 0.5) is increased by 188% (resp. 264%) for dynamic UT association and by 158% (resp. 218%) for static UT association. Furthermore, we observe that the dynamic UT association always outperforms the static UT association. Lastly, the lower bound on (15), derived using Corollary 1, is increasingly tight as P hit grows large.

IV. CACHE-AIDED SC NETWORK DEPLOYMENT
In this section, we look at possible design problems of interest to network operators and we aim at providing simple design guidelines for the deployment of cache-aided SC networks. As design parameters, we focus on the SC density λ ∈ [λ (min) , λ (max) ] and the storage size S ∈ [0, S (max) ], with S (max) ≤ F : therefore, we make the dependence on these parameters explicit in our performance metrics. For instance, the minimum SC density λ (min) can be chosen to ensure an interference-limited system performance (i.e., the background noise becomes negligible), whereas the maximum SC density λ (max) can be due to spatial limitations; similarly, the maximum storage size S (max) may arise from practical constraints regarding space or power consumption at the SCs. In our analysis, we consider the simplest case of uniform files popularity, i.e., p i = 1 F , i = 1, . . . , F , with P hit (S) = S F , where we have made the dependence of the cache hit probability on S explicit. Note that, for the more realistic case of decreasing files popularity, i.e., p 1 > p 2 > . . . > p F , expanding the storage will have an increasingly less significant impact on the system performance.

A. Deployment Cost
Suppose that a network operator has a fixed monetary budget per m 2 c (measured in $/m 2 ) to deploy a cache-aided SC network. Let p λ denote the SC price (measured in $/SC) and let p S denote the storage price (measured in $/file). The following simple question naturally arises in this context: is it better to invest in deploying SCs or storage? The answer hinges on the choice of the performance metric and can be found by means of an appropriate optimization. For instance, to maximize the achievable ASE in (14)-(15), the answer is given by the solution of the following optimization problem: (P1) Alternatively, the system performance can be measured in terms of its EE. Before formalizing the corresponding problem, some definitions are in order. Let be the total energy consumed to provide a content to a UT (measured in J), where E hit is the energy needed by the SC to retrieve a cached file from its storage unit and transmit it to the UT in case of cache hit, and E miss is the energy needed by the BH to retrieve a non-cached file from the internet and transmit it to the UT in case of cache miss (via the SC for static UT association and directly for dynamic UT association). Moreover, we define the area energy consumption (measured in J/m 2 ) as AEC(λ, S) λE tot (S) and the EE (measured in bit/J) as Hence, the corresponding optimization problem is given by: Using the same parameters as in Section III, we additionally set F = 10 7 files, λ (min) = 10 −4 SCs/m 2 , λ (max) = 10 −2 SCs/m 2 , S (max) = 5 × 10 6 files/SC, p λ = 250 $/SC, p λ = 0.005 $/file, E hit = 1 J, and E miss = 10 J. Assuming p λ λ + p S λ S = c, which excludes the trivial solution {λ , S } = {λ (max) , S (max) }, Figure 3 illustrates the feasible solution set of the considered problems with c = {1, 2.5, 5} $/m 2 . Figures 4 and 5 plot the achievable ASE and the EE, respectively, against the SC density λ, where each value of λ yields a value of S (and thus of P hit ) according to the constraint on the monetary budget (cf. Figure 3). The achievable ASE in Figure 4 is monotonically increasing in λ: this means that, to maximize the network ASE, one should invest in deploying more SCs (even if that means S = 0), whereas S should be increased only if there is remaining budget. Therefore, the solution of problem (P1) is given by On the contrary, the EE in Figure 5 is monotonically decreasing in λ: this means that, to maximize the network EE, one should invest in expanding the storage as much as possible (even if that means λ = λ (min) ), whereas λ should be increased only if there is remaining budget. Hence, the solution of problem (P2) reads as (19) In practice, increasing the SCs caching capabilities seems to be very useful for increasing the EE. Conversely, the impact of additional storage on the ASE is minor if the operator disposes of additional resources to increase the SC density. These results suggest that the answer to the question initially posed in this section, i.e., the choice of investing on additional SCs or on more storage, is not unique but strongly hinges on the ultimate goal of the network operator. Finally, we observe that a dynamic UT association policy is always preferable in terms of network performance whenever the larger complexity necessary to implement it can be afforded.

V. CONCLUSIONS
In this work, we study the performance of a tiered network where a tier of macro-cell wireless backhaul nodes is overlaid with a tier of cache-aided SCs. To frame a more realistic scenario, we consider both static and dynamic UT association policies. Building on random spatial models and using tools from stochastic geometry, we derive closed-form expressions and bounds for the achievable ASE for both UT association policies. Then, we study suitable optimization problems to identify deployment strategies for maximizing the ASE and EE of the network. Our findings show that the ASE is maximized by first increasing the SC density and then the storage size at the SCs, whereas an opposite approach should be adopted for maximizing the EE.


text:
Latency Analysis of Coded Computation Schemes over Wireless Networks

Large-scale distributed computing systems face two major bottlenecks that limit their scalability: straggler delay caused by the variability of computation times at different worker nodes and communication bottlenecks caused by shuffling data across many nodes in the network. Recently, it has been shown that codes can provide significant gains in overcoming these bottlenecks. In particular, optimal coding schemes for minimizing latency in distributed computation of linear functions and mitigating the effect of stragglers was proposed for a wired network, where the workers can simultaneously transmit messages to a master node without interference. In this paper, we focus on the problem of coded computation over a wireless master-worker setup with straggling workers, where only one worker can transmit the result of its local computation back to the master at a time. We consider 3 asymptotic regimes (determined by how the communication and computation times are scaled with the number of workers) and precisely characterize the total run-time of the distributed algorithm and optimum coding strategy in each regime. In particular, for the regime of practical interest where the computation and communication times of the distributed computing algorithm are comparable, we show that the total run-time approaches a simple lower bound that decouples computation and communication, and demonstrate that coded schemes are $\Theta(\log(n))$ times faster than uncoded schemes.

I. INTRODUCTION
Modern large-scale computing systems are driven by scaling out computations across many small machines. While current distributed computing systems are mainly based on cloud computation with abundance of computational resources, there has been increasing interest in distributed computation over wireless networks where the computational nodes are mobile or wireless devices [2], [3]. In a recent report by Google research, "Federated Learning" is proposed that enables mobile phones to collaboratively learn a shared prediction model while keeping all the training data on device, decoupling the ability to do machine learning from the need to store the data in the cloud [4]. Further, wireless distributed computing enables many emerging mobile applications such as voice recognition, image processing, and virtual reality to get carried out without putting extra burden to the cloud. It can further improve the quality of service and latency of such applications.
Distributed computing systems encounter two major bottlenecks that limit their scalability: (i) Straggler delay bottleneck which is due to the latency in waiting for the slowest nodes to finish their computation tasks; (ii) Communication bottleneck which is due to the need in shuffling massive amounts of data over many nodes in the distributed algorithm. The traditional approach for mitigating these bottlenecks is to introduce computation redundancy in the form of task replicas. For example, replicating the straggling task on another available node is a common approach to mitigate the effect of stragglers [5]. However, recent results have proposed the use of "coding schemes" in introducing clever computational redundancy to deal with both stragglers and communication bottlenecks.

A. Related Works on Coded Computation
The use of codes for minimizing latency in distributed computation of linear functions was introduced in [1]. The key idea is to use erasure codes to inject redundancy such that the minimum latency is achieved by trading off the number of stragglers that the algorithm is robust to with redundancy factor in computation. In [6], the authors consider coded computation over heterogeneous clusters, and proposed an asymptotically optimal coded algorithm for distributed matrix-vector multiplication. The use of product codes and polynomial codes for high-dimensional matrix multiplication over homogeneous clusters is proposed in [7] and [8], respectively. In a related work [9], the authors propose the use of redundant short dot products to speed up distributed computation of linear transforms. Coded computing of the convolution of two long vectors distributedly in the presence of stragglers is proposed in [10]. Coded computation of nonlinear functions over multicore setups is studied in [11]. In [12], the authors propose coding schemes for mitigating stragglers in distributed batch gradient computation. The idea of coded computation is utilized in [13] for solving linear inverse problems in a parallelized implementation affected by stragglers.
The use of codes for minimizing bandwidth in distributed computation was introduced in [14], [15], and for coded data shuffling in distributed machine learning algorithms in [1]. In [16], the authors propose a scalable framework for minimizing the communication bandwidth in wireless distributed computing without considering stragglers delay. A unified coded framework for (wired) distributed computing with straggling servers is proposed in [17], by introducing a tradeoff between latency of computation and load of communication for some linear computation tasks. In a related word to coded data shuffling, [18] studies the information theoretic limits of data shuffling in distributed learning. A pliate index coding approach is proposed in [19] for data shuffling.

B. Main Contribution
All of the coded computation schemes for minimizing stragglers delay that have been proposed in the literature are for wired networks, where the results of computations of the workers can be received simultaneously by the master node, and there exists no interference between their channels. In this paper, we consider the problem of distributedly computing a linear computation task over a wireless master-worker setup with straggling workers, where only one worker can transmit the result of its local computation back to the master at a time. This interference model is motivated by classical results in wireless networks such as [20], and can be generalized to the case where the dependency of the workers can be described by defining subsets that can be activated simultaneously. To characterize the total run-time of a distributed computing task, we consider two variables for the computation time of each worker and for the communication time of each locally computed result from the workers to the master. This separation of computation and communication time is also performed in [11]. We propose optimal coding schemes for different regimes for speeding up distributed matrix-vector multiplication in wireless networks with straggling servers. Matrix-vector multiplication is a crucial computation in many distributed machine learning algorithms such as logistic regression, reinforcement learning and gradient descent based algorithms. Wireless implementations of such algorithms can play a fundamental role in speeding up mobile data analytics and emerging mobile applications.
We now explain the main contribution of this paper. In the original coded computation paper [1], an optimal MDS code is proposed to minimize the latency of total computation run-time by robustifying the distributed algorithm to a few stragglers. Using an (n, k)−MDS code, it is easy to show that this total computation run-time is the k-th order statistics of n i.i.d. random variables, assuming that the computation time of each worker is independent and identically distributed (i.i.d.); thus, one can optimize the rate of the code to find the best trade-off between computation redundancy and robustness to stragglers. In a wireless network, the total run-time is not simply determined by the k-th order statistics of n i.i.d. random variables; instead, the system has memory as the state of the computation is determined by the number of computations that are completed and the number of local computed results that are transmitted back to the master node. While exact characterization of the total run-time and optimal coding strategy seems to be intractable for arbitrary system parameters, in this paper we consider 3 asymptotic regimes (determined by how the communication and computation times are scaled with the number of workers) and precisely characterize the total run-time of the distributed algorithm and optimum coding strategy in each regime. In particular, for the regime of practical interest where the computation and communication times of the distributed computing algorithm are comparable, we show that the total run-time approaches a simple lower bound that decouples computation and communication, and demonstrate that coded schemes are Θ(log(n)) times faster than uncoded schemes.

C. Notation
In this paper, we use bold face small and capital letters for vectors and matrices respectively, capital letters for random variables, and lower cases for constants. For i ∈ N, we denote by [i] the set {1, 2, · · · , i}. For non-negative functions f and g, we denote f (n) = O(g(n)) if there exists n 0 ∈ N and c > 0 such that f (n) ≤ cg(n) for n ≥ n 0 ; f (n) = o(g(n)) if f (n)/g(n) → 0 as n → ∞. Moreover, f (n) = ω(g(n)) if and only if g(n) = o(f (n)) and f (n) = Θ(g(n)) if and only if f (n) = O(g(n)) and g(n) = O(f (n)).

II. PROBLEM STATEMENT
Consider a master-worker system consisting of a master node and n computing worker nodes. The goal is to compute the matrix-vector multiplication y = Ax distributedly across the worker nodes, where A ∈ R r×m and x ∈ R m . Every worker has access to the vector x = (x 1 , · · · , x m ) , where each x i can be represented by d bits, i.e., . Thus, there are overall r = Θ(n) inner product computations required to be carried out by the worker nodes. The master node assigns computing the matrix-vector multiplication y i = A i x to worker i for i ∈ [n] where A i 's are functions of A. Due to memory and computation capability constraint on local computing nodes, matrices A i 's are usually much smaller in size than the original matrix A. Each worker performs its partial computation and sends the result back to the master node. The master node aggregates the partial computations y i 's and retrieves y from a recoverable set of local computations.
Computation time of each worker node for one inner product is modeled as a shifted-exponential random variable with parameters (a, µ), i.e. for t ≥ a, where T i denotes the computation latency of worker node i ∈ [n] for computing an inner product of two vectors of length m. This computation time model is motivated by the distribution model proposed by authors in [21] for latency in querying data files from cloud storage systems. For the sake of notation simplicity, we denote such a random variable by T i ∼ a + exp(µ). Workers can communicate with the master node via wireless links with the same rate. We consider a MAC layer model where only one worker can transmit data to the master node at a time. Thus, every worker that finishes its computation, waits till the channel becomes idle and initiates the transmission, and priority is given to nodes that have earlier computation completion times. In other words, communications are carried out in the same order that their corresponding computations are executed. Let t 1-cmm denote the communication time for the result of a single inner product. Furthermore, we assume the communication phase of every worker node is without preemption, i.e. a worker node transmits its result in one round of communication. Since only one worker is able to transmit results to the master node at a time, one needs to reexamine the total execution time (latency) of the distributed computation, T tot , which is defined as the total time of computation and communication to carry out the complete multiplication. As we will see, precisely characterizing the total run-time T tot is intractable for arbitrary set of problem parameters and requires combinatorial analysis. Instead, we provide asymptotic characterizations of the total latency for three different regimes. We consider coded and uncoded scenarios for a system of one master and n workers and evaluate the total execution time for each scenario.

III. MAIN RESULTS: WIRELESS CODED COMPUTATION
In this section, we investigate the total execution time of coded computation schemes over wireless networks in different regimes of parameters. We first illustrate the key idea of coded computation through a simple example. Example 1. Consider a computation system consisting of one master node and n = 4 worker nodes as depicted in Figure  1. To robustify the computation to stragglers, we carry out a (4, 2)-MDS coded computation as follows. The master node divides the large matrix A to two submatrices A 1 and A 2 of the same size: Then, the local computations assigned to each worker node is as follows (3) Clearly, results of any k = 2 workers (e.g. workers 2 and 3 in Figure 1) compose a recoverable set to retrieve Therefore, the master node only waits for the two fastest workers and recovers the result then.
There are totally r inner products to be computed via n nodes distributedly. We employ an (n, k)−MDS code to perform the computation task, i.e. the computation result of any k worker nodes forms a decodable set of inner products. Therefore, every node is assigned r/k inner products to be computed. Each assigned vector to the worker nodes is a random linear combination of the rows of the matrix A, thus the master node assigns r/k random linear combinations of the rows of A to each worker. More precisely, the computation matrix assigned to worker i is A i = S i A where S i ∈ R r/k×r is the coding matrix for worker i. To establish a random linear code, the entries of S i are i.i.d. N (0, 1). Worker i computes y i = A i x and sends back the result to the master node. Upon receiving r inner products, the master node can retrieve the computation y = Ax with probability 1. The master node aggregates the results in the form z = S (r) Ax, where S (r) ∈ R r×r is the aggregated coding matrices which is full-rank with probability 1. Therefore, the master node can recover y = Ax = S −1 (r) z. Similarly, one can construct an MDS code to ensure any k out of n responses of the workers suffice for recovering y.
Since each worker node computes r/k inner products, adopting the computation time model in [1], the random variable denoting the computation time for worker node i can be represented as a constant shift t 0 = ar/k added to an exponential term T i with rate µk/r, i.e.
for t ≥ t 0 and i ∈ [n], where T i 's are i.i.d. (see figure 2). 1 We denote the ordered sequence of computation times by where t 0 + T (i) denotes the i-th smallest computation time (i-th order statistic), i.e. T (1) ≤ T (2) ≤ · · · ≤ T (n) . Moreover, we define the differences in computation times (differential times) as follows for i = 2, · · · , n. Let α = r µk . Differential times are exponential and mutually independent random variables with the following distribution: D i ∼ exp( 1 α (n − i + 1)). Furthermore, communication time for each worker is t cmm = r k t 1-cmm that is a constant term. The master node needs to wait for the results of the fastest k worker nodes. Trivial lower and upper bounds on the total execution time can be derived as follows where H i = 1 + 1 2 + · · · + 1 i (see Lemma 1). One can easily find lower and upper bounds on the total expected run-time as follows: Clearly, if the channel is idle at the time of the completion of k-th computation, one finds that the total run-time is the left-hand side of (8) which implies the lower bound. Further, if one considers a (higher-latency) protocol where all the communications are performed after the k-th computation, the upper bound will be derived.
To illustrate the challenge of exactly characterizing the total run-time, we provide a simple example describing the dynamics of the problem. Example 2. Assume a = 1 µ = 1 second, n = 5, k = 3, r = 5, and t cmm = 0.2 seconds. From a random realization, we get T (1) = 0.1138, T (2) = 0.2725, T (3) = 0.6458, T (4) = 0.7033, and T (5) = 5.5538 all in seconds. Figure 2 depicts the time digram of the experiment. Thus, one observes that the communication of the second result cannot be carried out at t 0 + T (2) since the channel is busy. However, the channel is idle at t 0 + T (3) . Thus, the overall run-time is the same as the lower bound in (8). For the (n, k)−MDS coded computation, k is the design parameter and is picked in the order of n: k = Θ(n). Thus, α = Θ(1). In the following lemma, we show that as j gets large, the random variable T (j) is well-concentrated around its expected value.
Proof. We can write where D i ∼ exp(α −1 (n − i + 1)) for i = 1, . . . , n, and they are independent. Therefore, the expected value of T (j) can be written as Harmonic series H n = 1 + 1 2 + · · · + 1 n can be approximated as H n = log n + γ + O( 1 n ) where γ ≈ 0.72156649 is the Euler-Mascheroni constant. Moreover, for j = Θ(n), we may write the variance of T (j) as By Chebyshev's inequality, for = Θ( log n n ).
This lemma indicates that for large enough j, we can approximate T (j) by its expected value, i.e. with probability approaching 1, we have T (j) = α log( n n−j ) ± o(1).
Proof. We can write the expected value of T (j) as Following the same argument in the proof of Lemma 1, the variance of T (j) for j = o(n) can be evaluated as By Chebyshev's inequality, (1), with probability 1−o(1). As discussed before, characterizing the exact execution time for arbitrary parameters seems to be intractable for arbitrary parameters. Instead, we consider three asymptotic regimes and evaluate the overall run-time in the following.

A. Regime I
In this regime, at a high level the total communication time is negligible compared to computation time. More precisely, we consider the regime where In this regime, the communication time for each worker node is small enough such that almost all of the results can be communicated during the computation phase. Thus, the problem gets reduced to the wired coded computation problem in [1] as n gets large. The following theorem precisely states this fact. Theorem 1. With high probability, k transmissions are completed by time t 0 + T (k) + t cmm .
Proof. Let Q ≤ k denote the greatest random index for which the channel is idle at time t 0 + T (Q) . First, assume that Q = o(n) with probability 1 − o(1). Given the realization Q = q = o(n), by Lemma 2, with high probability, T (q) = o(1).
(16) Therefore, T (k) = T (q) + (k − q)t cmm = o(1), which is in contradiction to Lemma 1, since T (k) = Θ(1). Secondly, assume that Q = q = Θ(n) < k with probability 1 − o(1). From Lemma 1 we can write On the other hand, since the channel is not idle in the interval that is a contradiction. Thus, Q = q = k with probability 1 − o(1). This implies that all the k − 1 computations are transmitted by time t 0 +T (k) with high probability. The last transmission would occur right after the corresponding computation is finished. Therefore, the lower bound t 0 + T (k) + t cmm in (8) is achieved and T RI coded = t 0 + T (k) + t cmm with probability 1 − o(1), where T RI coded denotes the run-time corresponding to the (n, k)−MDS coded scheme performing in regime I.
The following theorem states that the computation times are small enough such that most of the communications have to occur after the last computation is finished. Proof. Let Q ≤ k denote the random variable denoting the greatest index for which the channel is idle at time t 0 + T (q) . First, assume that Q = Θ(n) with probability 1 − o(1). Given the realization Q = q = Θ(n), by Lemma 1, with high probability, On the other hand, all the q − 1 communications are finished by time T (q) . Therefore, which is in contradiction to (17). Hence, Q = o(n) with probability 1 − o(1), and given that Q = q = o(n) the number of transmissions completed by time t 0 + T (k) can be written as Therefore, T RII coded ≥ t 0 + T (k) + (k − o(n))t cmm with probability 1 − o(1), where T RII coded denotes the run-time corresponding to the (n, k)−MDS coded scheme performing in regime II.

C. Regime III
The third regime is the regime of interest where communication and computation times are comparable, i.e. t 1-cmm = Θ( 1 n ). Without loss of generality, we assume that t 1-cmm = k rn and therefore t cmm = 1 n . We now define a new variable p as follows. Let p be the smallest integer such that that is Thus, for j < p, we have and for j > p, Moreover, From definition of the index p, it is easy to check that p = Θ(n).
To illustrate this definition, let us first discuss a naive approximation of the differential times as follows. We approximate the differential times with deterministic variables equal to their expected values, i.e.
This assumption implies that the inter-arrival times are increasing and therefore the first p − 1 computations are pipe-lined or the channel does not become idle in the first p − 1 transmissions (see figure 3), i.e. Proof. We define Q as the largest index less than p for which the channel is busy from t 0 + T (Q) to t 0 + T (p) , and q as its realization. We consider the following two possible regimes for Q.
• Case 2: Q = q = Θ(n). Using Lemma 1, we have T (q) = α log( n n−q ) ± o(1) and T (p) = α log( n n−p ) ± o(1) with probability 1 − o(1). Therefore, with probability 1 − o(1), where (28)  Proof. First, we note that by Lemma 1, T (p) and T (k) are well concentrated around their expected values. Thus, together with (25), with probability 1 − o(1). Now in contrary, suppose that the number of communications from t 0 + T (p) to t 0 + T (k) is smaller than β(k − p) for some constant β < 1 with a positive Θ(1) probability. Now let T (j) be the last time that the channel is idle in this period. Consider the following three cases: • Case 1: If j = p, then we reach a contradiction since n(T (k) − T (p) ) ≥ k − p − o(n) with high probability. • Case 2: If p < j < γk for some γ < 1, then n(T (k) − T (j) ) ≥ k − j − o(n) with probability 1 − o(1) and also j − p communications have been done by time t 0 + T (j) since the channel was idle, which implies a contradiction. • Case 3: If j = k − o(n), since the channel was idle at that time, at least j − p = k − p − o(n) communications have already been completed by t 0 + T (k) that is a contradiction. Therefore, the claim is concluded.
Putting Lemmas 3 and 4 together, we conclude that at least k − o(n) transmissions are completed by time t 0 + T (k) with probability approaching 1. That is, T RIII coded ≤ t 0 + T (k) + o(n)t cmm with probability 1 − o(1), where T RIII coded denotes the run-time corresponding to the (n, k)−MDS coded scheme performing in regime III. Theorem 3. The expected total run-time for an (n, k)−MDS coded scheme performing in Regime III is Proof. From the lower bound in (8), E[T RIII coded ] ≥ t 0 + α(H n − H n−k ) + o(1). Moreover, we proved that T RIII coded ≤ t 0 + T (k) + o(n)t cmm with probability 1 − o(1). Further, we have the upper bound T RIII coded ≤ t 0 + T (k) + kt cmm in (8). Thus we can write Therefore, E[T RIII coded ] = t 0 + α(H n − H n−k ) + o(1). According to Theorem 3, the lower bound in (8) is achieved within a o(1) additive factor for regime III. Note that one can optimize the rate of the code and find the best k to minimize the expected total run-time numerically similar to [1]. Moreover, note that for k = Θ(n), we have In the next section, we will evaluate the total run-time for the uncoded scheme and compare it with the one corresponding to the coded scenario.

IV. UNCODED COMPUTATION OVER WIRELESS NETWORKS
In the uncoded scheme, the workload (total r inner products) is evenly distributed among n workers. Thus, each node computes r/n inner products. The master node has to wait for all the workers to finish their computations and send the results back to the master node. The following theorem compares the total run-time corresponding to coded and uncoded schemes and demonstrates how much gain one achieves by employing the proper coding strategy. Theorem 4. In Regimes I and III, coded computation is Θ(log n) times faster than uncoded computation, i.e.
Proof. In the uncoded scenario, the master node needs to wait for the result of all the n computations. Therefore, with probability 1, ar n + T (n) + 1 n ≤ T uncoded ≤ ar n + T (n) + 1, which concludes E[T uncoded ] = Θ(H n ) = Θ(log n).

V. CONCLUSION AND FUTURE WORK
We considered the problem of coded computation over a wireless network with master-worker setup and straggling workers. In this network, only one worker can transmit message to the master node at a time. We proposed the use of optimal MDS-coded schemes to minimize the total run-time of the distributed computation algorithm. In particular, while the exact characterization of total run-time is not tractable, we considered 3 asymptotic regimes (determined by how the communication and computation times are scaled with the number of workers) and precisely characterized the total run-time of the distributed algorithm and the optimum coding strategy in each regime. We further showed that coded schemes are Θ(log(n)) times faster than uncoded schemes in the regime of practical interest.
The interference model in this paper is not the most general model in wireless networks. It would be interesting to consider the case where the dependency of workers is characterized by their subsets that can be activated simultaneously. In this case, since the symmetry of workers will be broken, clearly one needs to assign different workload to different workers, which makes finding the optimal coding strategy and characterizing the total run-time more challenging. Another interesting direction is to generalize the problem to heterogeneous setup where each worker node has different computation capability.


text:
An Improved Training Procedure for Neural Autoregressive Data Completion

Neural autoregressive models are explicit density estimators that achieve state-of-the-art likelihoods for generative modeling. The D-dimensional data distribution is factorized into an autoregressive product of one-dimensional conditional distributions according to the chain rule. Data completion is a more involved task than data generation: the model must infer missing variables for any partially observed input vector. Previous work introduced an order-agnostic training procedure for data completion with autoregressive models. Missing variables in any partially observed input vector can be imputed efficiently by choosing an ordering where observed dimensions precede unobserved ones and by computing the autoregressive product in this order. In this paper, we provide evidence that the order-agnostic (OA) training procedure is suboptimal for data completion. We propose an alternative procedure (OA++) that reaches better performance in fewer computations. It can handle all data completion queries while training fewer one-dimensional conditional distributions than the OA procedure. In addition, these one-dimensional conditional distributions are trained proportionally to their expected usage at inference time, reducing overfitting. Finally, our OA++ procedure can exploit prior knowledge about the distribution of inference completion queries, as opposed to OA. We support these claims with quantitative experiments on standard datasets used to evaluate autoregressive generative models.

Introduction
Neural autoregressive models are explicit density estimators that achieve state-of-the-art likelihoods for generative modeling [3,4,5,7]. The D-dimensional data distribution p(x) is factorized into an autoregressive product of one-dimensional conditional distributions according to the chain rule. Each conditional distribution is parametrized by a shared neural network.
Data completion is a more involved task than data generation: the model must infer missing variables for any partially observed input vector. Previous work [5] introduced an order-agnostic training procedure for data completion with autoregressive models. It maximizes the average likelihood of the model over all D! orderings of the data dimensions. As a result, all possible one-dimensional conditionals p(x o d |x o1 , ..., x o d−1 ) are trained, for any d ∈ {1..D} and any ordering o of {1...n}. Thus, missing variables in any partially observed input vector can be imputed efficiently by choosing an ordering where observed dimensions precede unobserved ones and by computing the autoregressive product in this order. This training procedure can be made efficient: [6] estimates the order-agnostic loss with an unbiased estimator that reuses most computations.
In this paper, we provide evidence that the order-agnostic (OA) training procedure is suboptimal for data completion. We propose an alternative procedure (OA++) that reaches better performance in fewer computations. It can handle all data completion queries while training fewer one-dimensional conditional distributions than the OA procedure. In addition, these one-dimensional conditional distributions are trained proportionally to their expected usage at inference time, reducing overfitting. Finally, our OA++ procedure can exploit prior knowledge about the distribution of inference completion queries, as opposed to OA. We support these claims with quantitative experiments on standard datasets used to evaluate autoregressive generative models.
2 Improving the order-agnostic loss for data completion The OA procedure trains autoregressive models for data completion by optimizing the loss I OA (θ) in Equation 1. In practice, the exact loss has too many terms to be computationally tractable. It is estimated by sampling a training vector x uniformly at random, a number d ∈ {1..D} and a set o <d of conditioned variables uniformly at random, and by computing I OA (θ) as in Equation 2. The sum in I OA (θ) is computed over all possible choices of o d , and the neural network computations involved in p(x o d |x o<d ; θ, o d ) can be reused across the terms of the sum.
31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA.
In this section, we present and motivate step-by-step the modifications we propose to the OA procedure (Equation 1), leading to the OA++ procedure (Equation 5).

Equal use of 1D conditional distributions at training and inference
Ideally, the usage of each 1D conditional distribution at inference time should be proportional to its usage at training time. Otherwise, some 1D conditional distributions frequently used at inference time might be under-trained (undermining performance), and some 1D conditional distributions rarely used at inference time might be over-trained (undermining efficiency). For d ∈ {1..D}, we refer to 1D conditional distributions with d − 1 conditioned variables, p(x o d |x o<d ; θ), as 1D conditional distributions of size d.
Result: Under the OA procedure, at any training iteration, each 1D conditional distribution of size d has a fixed probability of being trained.
Proof : At any training iteration, exactly one 1D conditional distribution of size d is trained. It is chosen uniformly at random among the D d−1 (D − d + 1) 1D conditional distributions of size d. Result: Under the OA procedure, each 1D conditional distribution of size d has probability of being involved in any generation query.
Proof : Exactly one 1D conditional distribution of size d is involved in any generation query, as each of the D variables must be sampled in sequence. There are D d−1 (D − d + 1) such distributions. The OA procedure chooses a variable ordering uniformly at random. Thus, any 1D conditional distribution of size d has an equal probability of being used in any generation query.
Therefore, under the OA procedure, the expected usage of any 1D conditional distribution at inference time is proportional to its expected usage at training time for generation queries. We are interested in data completion queries, however. In a completion query, the values of some variables are known, and thus conditional distributions for those variables do not need to be computed. This changes the expected usage patterns for each size d of conditional distribution. Using the OA procedure leads to a discrepancy between the usage of 1D conditional distributions during training and inference. Further, if we know something in advance about the distribution of inference queries (e.g. which variables will be known, or how many will be known), the OA procedure has no way to exploit such prior knowledge.
The OA++ procedure we propose does not suffer from these limitations. It assumes that inference queries follow a distribution D, and it trains all 1D conditional distributions proportionally to their expected usage during inference under this distribution. If we have prior knowledge about the expected structure of inference queries, this can be encoded in D. If we have no such prior knowledge, then OA++ sets D to be a uniform distribution over inference queries, i.e. the set of observed variables in a completion query is drawn uniformly at random.

Training fewer 1D conditional distributions
The OA procedure maximizes the average log-likelihood of the model over all orderings: in Equation  1, the ordering o is treated as a uniform random variable over its D! values. Consequently, all 1D conditional distributions are trained. However, these conditional distributions will not all be used. To handle any given query, the model must either fix an order of the unobserved variables, or use an ensemble of K > 1 orderings of the unobserved variables as in [5]. In most settings, K << D!, thus far fewer 1D conditionals will be used than were trained. Since the parameters of all conditionals are determined by a single shared neural network, the model is wasting its representational capacity on 1D conditionals that will not be used at inference time.  Table 1: Average negative log-likelihood of NADE models on 2 test sets of inference queries. In each cell, the left metric corresponds to uniform random queries, the right metric corresponds to random queries of size D/2 known in advance The OA++ procedure we propose instead trains at most K The OA++ loss I OA++ (θ) for data completion is expressed as in Equation 5. D is the distribution of inference queries if we have prior knowledge of it; otherwise D is the uniform random distribution of completion queries. K is the maximum number of inference queries that we expect to average by ensembling at inference time. For a given completion query obs ∈ D, the D − |obs| data dimensions of x missing are reordered according to ordering o.
Unbiased Estimator The OA++ loss in 5 has a large number of terms. It can be estimated by sampling a training example x uniformly at random, a completion query obs ∼ D, a number d ∈ {1..D − |obs|}, and by computing I OA++ (θ) as in Equation 6.
It is possible to provide an unbiased estimator of the loss, that consists of a sum with computations shared among its different terms, like in Equation 2. However, under the assumption K << D!, the sum would likely consist of a single term, effectively reducing to Equation 6.
Unifying data generation and data completion By choosing K = 1, OA++ reduces to the original training procedure for NADEs introduced in [2]. By choosing K = D!, OA++ reduces to the order-agnostic training procedure for data generation introduced in [6]. In other words, OA++ unifies the training procedures of data generation and data completion under a single framework.

Results
In order to compare OA and OA++, we train the same autoregressive model (two-layer NADE) with both procedures. We conduct experiments on eight multivariate binary datasets commonly used by previous works on autoregressive models [1,2,5]. Table 1 reports the performance of all models on 2 test sets of inference queries: one consists of uniform random completion queries; the other consists of completion queries of size D/2 picked at random. On the second test set, models were provided prior knowledge of the distribution of inference queries. Results are computed for K = 1 (no ensemble learning). The comparison of OA and OA++ for K > 1 is left as future work.
Performance at convergence OA++ outperforms OA on all experiments and does especially well when given prior knowledge about the distribution of inference queries.
Speed of convergence OA++ converges in fewer computations than OA. OA++ also does not suffer from overfitting, while OA sometimes does. Figure 1 reports the evolution of the training and validation log-likelihoods with the number of computations, for some experiments.


The Microsoft 2017 Conversational Speech Recognition System

We describe the 2017 version of Microsoft's conversational speech recognition system, in which we update our 2016 system with recent developments in neural-network-based acoustic and language modeling to further advance the state of the art on the Switchboard speech recognition task. The system adds a CNN-BLSTM acoustic model to the set of model architectures we combined previously, and includes character-based and dialog session aware LSTM language models in rescoring. For system combination we adopt a two-stage approach, whereby subsets of acoustic models are first combined at the senone/frame level, followed by a word-level voting via confusion networks. We also added a confusion network rescoring step after system combination. The resulting system yields a 5.1\% word error rate on the 2000 Switchboard evaluation set.

INTRODUCTION
We have witnessed steady progress in the improvement of automatic speech recognition (ASR) systems for conversational speech, a genre that was once considered among the hardest in the speech recognition community due to its unconstrained nature and intrinsic variability [1]. The combination of deep networks and efficient training methods with older neural modeling concepts [2,3,4,5,6,7,8] have produced steady advances in both acoustic modeling [9,10,11,12,13,14,15] and language modeling [16,17,18,19]. These systems typically use deep convolutional neural network (CNN) architectures in acoustic modeling, and multi-layered recurrent networks with gated memory (long-short-term memory, LSTM [8]) models for both acoustic and language modeling, driving the word error rate on the benchmark Switchboard corpus [20] down from its mid-2000s plateau of around 15% to well below 10%. We can attribute this progress to the neural models' ability to learn regularities over a wide acoustic context in both time and frequency dimensions, and, in the case of language models, to condition on unlimited histories and learn representations of functional word similarity [21,22].
Given these developments, we carried out an experiment last year, to measure the accuracy of a state-of-the-art con-versational speech recognition system against that of professional transcribers. We were trying to answer the question whether machines had effectively caught up with humans in this, originally very challenging, speech recognition task. To measure human error on this task, we submitted the Switchboard evaluation data to our standard conversational speech transcription vendor pipeline (who was left blind to the experiment), postprocessed the output to remove text normalization discrepancies, and then applied the NIST scoring protocol. The resulting human word error was 5.9%, not statistically different from the 5.8% error rate achieved by our ASR system [23]. In a follow-up study [24], we found that qualitatively, too, the human and machine transcriptions were remarkably similar: the same short function words account for most of the errors, the same speakers tend to be easy or hard to transcribe, and it is difficult for human subjects to tell whether an errorful transcript was produced by a human or ASR. Meanwhile, another research group carried out their own measurement of human transcription error [25], while multiple groups reported further improvements in ASR performance [25,26]. The IBM/Appen human transcription study employed a more involved transcription process with more listening passes, a pool of transcribers, and access to the conversational context of each utterance, yielding a human error rate of 5.1%. Together with a prior study by LDC [27], we can conclude that human performance, unsurprisingly, falls within a range depending on the level of effort expended.
In this paper we describe a new iteration in the development of our system, pushing well past the 5.9% benchmark we measured previously. The overall gain comes from a combination of smaller improvements in all components of the recognition system. We added an additional acoustic model architecture, a CNN-BLSTM, to our system. Language modeling was improved with an additional utterance-level LSTM based on characters instead of words, as well as a dialog session-based LSTM that uses the entire preceding conversation as history. Our system combination approach was refined by combining predictions from multiple acoustic models at both the senone/frame and word levels. Finally, we added an LM rescoring step after confusion network creation, bringing us to an overall error rate of 5.1%, thus surpassing the human accuracy level we had measured previously. The remainder of the paper describes each of these enhancements in turn, followed by overall results.

Convolutional neural nets
We used two types of CNN model architectures: ResNet and LACE (VGG, a third architecture used in our previous system, was dropped). The residual-network (ResNet) architecture [28] is a standard CNN with added highway connections [29], i.e., a linear transform of each layer's input to the layer's output [29,30]. We apply batch normalization [31] before computing rectified linear unit (ReLU) activations.
The LACE (layer-wise context expansion with attention) model is a modified CNN architecture [32]. LACE, first proposed in [32] and depicted in Figure 1, is a variant of timedelay neural network (TDNN) [4] in which each higher layer is a weighted sum of nonlinear transformations of a window of lower layer frames. Lower layers focus on extracting simple local patterns while higher layers extract complex patterns that cover broader contexts. Since not all frames in a window carry the same importance, a learned attention mask is applied, shown as the "element-wise matrix product" in Figure 1. The LACE model thus differs from the earlier TDNN models [4,33] in this attention masking, as well as the ResNet-like linear pass-through connections. As shown in the diagram, the model is composed of four blocks, each with the same architecture. Each block starts with a convolution layer with stride two, which sub-samples the input and increases the number of channels. This layer is followed by four ReLU convolution layers with jump-links similar to those used in ResNet. As for ResNet, batch normalization [31] is used between layers.

Bidirectional LSTM
For our LSTM-based acoustic models we use a bidirectional architecture (BLSTM) [34] without frame-skipping [11]. The core model structure is the LSTM defined in [10]. We found that using networks with more than six layers did not improve the word error rate on the development set, and chose 512 hidden units, per direction, per layer; this gave a reasonable trade-off between training time and final model accuracy.
BLSTM performance was significantly enhanced using a spatial smoothing technique, first described in [23]. Briefly, a two-dimensional topology is imposed on each layer, and activation patterns in which neighboring units are correlated are rewarded.

CNN-BLSTM
A new addition to our system this year is a CNN-BLSTM model inspired by [35]. Unlike the original BLSTM model, we included the context of each time point as an input feature in the model. The context windows was [−3, 3], so the input feature has size 40x7xt, with zero-padding in the frequency dimension, but not in the time dimension. We first apply three convolutional layers on the features at time t, and then apply six BLSTM layers to the resulting time sequence, similar to structure of our pure BLSTM model. Table 1 compares the layer structure and parameters of the two pure CNN architectures, as well as the CNN-BLSTM.

Senone set diversity
One standard element of state-of-the-art ASR systems is the combination of multiple acoustic models. Assuming these models are diverse, i.e., make errors that are not perfectly correlated, an averaging or voting combination of these models should reduce error. In the past we have relied mainly on different model architectures to produce diverse acoustic models. However, results in [23] for multiple BLSTM models showed that diversity can also be achieved using different sets of senones (clustered subphonetic units). Therefore, we have now adopted a variety of senone sets for all model architectures. Senone sets differ by clustering detail (9k versus 27k senones), as well as two slightly different phone sets and corresponding dictionaries. The standard version is based on the CMU dictionary and phone set (without stress, but including a schwa phone). An alternate dictionary adds specialized vowel and nasal phones used exclusively for filled pauses and backchannel words, inspired by [36]. Combined with set sizes, this gives us a total of four distinct senone sets.

Speaker adaptation
Speaker adaptive modeling in our system is based on conditioning the network on an i-vector [37] characterization of each speaker [38,39]. A 100-dimensional i-vector is generated for each conversation side (channel A or B of the audio file, i.e., all the speech coming from the same speaker). For the BLSTM systems, the conversation-side i-vector v s is appended to each frame of input. For convolutional networks, this approach is inappropriate because we do not expect to see spatially contiguous patterns in the input. Instead, for the CNNs, we add a learnable weight matrix W l to each layer, and add W l v s to the activation of the layer before the nonlinearity. Thus, in the CNN, the i-vector essentially serves as an speaker-dependent bias to each layer.
For results showing the effectiveness of i-vector adaptation on our models, see [40].

Sequence training
All our models are sequence-trained using maximum mutual information (MMI) as the discriminative objective function. Based on the approaches of [41] and [42], the denominator graph is a full trigram LM over phones and senones. The forward-backward computations are cast as matrix operations, and can therefore be carried out efficiently on GPUs without requiring a lattice approximation of the search space. For details of our implementation and empirical evaluation relative to cross-entropy trained models, see [40].

Frame-level model combination
In our new system we added frame-level combination of senone posteriors from multiple acoustic models. Such a combination of neural acoustic models is effectively just another, albeit more complex, neural model. Frame-level model combination is constrained by the fact that the underlying senone sets must be identical. Table 2 shows the error rates achieved by various senone set, model architectures, and frame-level combination of multiple architectures. The results are based on N-gram language models, and all combinations are equal-weighted.

Vocabulary size
In the past we had used a relatively small vocabulary of 30,500 words drawn only from in-domain (Switchboard and Fisher corpus) training data. While this yields an out-ofvocabulary (OOV) rate well below 1%, our error rates have reached levels where even small absolute reductions in OOVs could potentially have a significant impact on overall accuracy. We supplemented the in-domain vocabulary with the most frequent words in the out-of-domain sources also used for language model training: the LDC Broadcast News corpus and the UW Conversational Web corpus. Boosting the vocabulary size to 165k reduced the OOV rate (excluding word fragments) on the eval2002 devset from 0.29% to 0.06%. Devset error rate (using the 9k-senones BLSTM+ResNet+LACE acoustic models, see Table 2) dropped from 9.90% to 9.78%.

LSTM-LM rescoring
For each acoustic model our system decodes with a slightly pruned 4-gram LM and generates lattices. These are then rescored with the full 4-gram LM to generate 500-best lists. The N-best lists in turn are then rescored with LSTM-LMs. Following promising results by other researchers [43,19], we had already adopted LSTM-LMs in our previous system, with a few enhancements [23]: • Interpolation of models based on one-hot word encodings (with embedding layer) and another model using letter-trigram word encoding (without extra embedding layer).
• Log-linear combination of forward-and backwardrunning models.
• Pretraining on the large out-of-domain UW Web corpus (without learning rate adjustment), followed by final training on in-domain data only, with learning rate adjustment schedule.
• Improved convergence through a variation of selfstabilization [44], in which each output vector x of nonlinearities are scaled by 1 4 ln(1 + e 4β ), where a β is a scalar that is learned for each output. This has a similar effect as the scale of the well-known batch normalization technique [31], but can be used in recurrent loops.
• Data-driven learning of the penalty to assign to words that occur in the decoder LM but not in the LSTM-LM vocabulary. The latter consists of all words occurring twice or more in the in-domain data (38k words).
Also, for word-encoded LSTM-LMs, we use the approach from [45] to tie the input embedding and output embedding together. In our updated system, we add the following additional utterance-scoped LSTM-LM variants: All LSTM-LMs with word-level input use three 1000dimensional hidden layers. The word embedding layer for the word-based is also of size 1000, and the letter-trigram encoding has size 7190 (the number of unique trigrams). The character-level LSTM-LM uses two 1000-dimensional hidden layers, on top of a 300-dimensional embedding layer. As before, we build forward and backward running versions of these models, and combine them additively in the log-probability space, using equal weights. Unlike before, we combine the different LSTM-architectures via log-linear combination in the rescoring stage, rather than via linear interpolation at the word level. The new approach is more convenient when the relative weighting of a large number of models needs to be optimized, and the optimization happens jointly with the other knowledge sources, such as the acoustic and pronunciation model scores. Table 3 shows perplexities of the various LSTM language models on dev and test sets. The forward and backward versions have very similar perplexities, justifying tying their weights in the eventual score weighting. There are differences between the various input encodings, but they are small, on the order of 2-4% relative.

Dialog session-based modeling
The task at hand is not just to recognize isolated utterances but entire conversations. We are already exploiting global conversation-level consistency via speaker adaptation, by extracting i-vector from all the speech on one side of the conversation, as described earlier. It stands to reason that the language model could also benefit from information beyond the current utterance, in two ways: first conversations exhibit global coherence, especially in terms of conversation topic, and especially since Switchboard conversations are nominally on a pre-defined topic. Lexical entrainment [46], the tendency of conversants to adopt the same words and phrases, could also be exploited for language modeling. There is a large body of work on adaptation of language models to topics and otherwise [47], and recurrent neural network model extensions have been proposed to condition on global context [17]. A second set of conversation-level phenomena operate beyond the utterance, but more locally. Linguistic conversation analysis has long noted that utterance types come in adjacency pairs [48], with preferences for certain pairs over others (like a statement followed by agreement versus disagreement). Therefore, words in an utterance should be more predicable based on the previous utterance, as well as information about whether a speaker change occurred, and this has been proposed as useful information in language models [49]. We can also include in the history information on whether utterances overlap, since overlap is partially predicted by the words spoken [50]. This type of conditioning information  In order to capture both global and local context for modeling the current utterance, we train session-based LSTM-LMs. We serialize the utterances in a conversation based on their onset times (using the waveform cut points as approximate utterance onset and end times). We then string the words from both speakers together to predict the following word at each position, as depicted in Figure 2. Optionally, extra bits in the input are used to encode whether a speaker change occurred, or whether the current utterance overlaps in time with the previous one. When evaluating the session-based LMs on speech test data, we use the 1-best hypotheses from the Nbest generation step (which uses only an N-gram LM) as a stand-in for the conversation history. Table 4 shows the effect of session-level modeling and of these optional elements on the model perplexity. There is a large perplexity reduction of 21% by conditioning on the previous word context, with smaller incremental reductions from adding speaker change and overlap information. The table also compares the word error rate with the full sessionbased model to the baseline, within-utterance LSTM-LM. As shown in the last row of the table, some of the perplexity gain over the baseline is negated by the use of 1-best recognition output for the conversation history. However, the perplexity degrades by only 7-8% relative due to the noisy history.
For inclusion in the overall system, we built letter-trigram and word-based versions of the session-based LSTM (in both directions).
Both session-based LM scores are added to the utterancebased LSTM-LMs described earlier for log-linear combination.

Data
The data sets used for system training are unchanged [23]; they consist of the public and shared data sets used in the DARPA research community. Acoustic training used the English CTS (Switchboard and Fisher) corpora. Language model training, in addition, used the English CallHome transcripts, the BBN Switchboard-2 transcripts, the LDC Hub4 (Broadcast News) corpus, and the UW conversational web corpus [51]. Evaluation is carried out on the NIST 2000 CTS test set Switchboard portion. The Switchboard-1 and Switchboard-2 portions of the NIST 2002 CTS test set were used for tuning and development.

Model training
All neural networks in the final system were trained with the Microsoft Cognitive Toolkit, or CNTK [52,53] on a Linuxbased multi-GPU server farm. CNTK allows for flexible model definition, while at the same time scaling very efficiently across multiple GPUs and multiple servers. The resulting fast experimental turnaround using the full 2000-hour corpus was critical for our work.
Training the acoustic models in this paper on a single GPU would take many weeks or even months. CNTK made training times feasible by parallelizing the stochastic gradient descent (SGD) training with a 1-bit SGD parallelization technique [54]. This data-parallel method distributes minibatches over multiple worker nodes, and then aggregates the subgradients. While the necessary communication time would otherwise be prohibitive, the 1-bit SGD method eliminates the bottleneck by combining 1-bit quantization of gradients and automatic minibatch-size scaling, as described in more detail in [23].
We use the CNTK "FsAdaGrad" learning algorithm, which is an implementation of Adam [55]. A typical learning rate is 3 × 10 −6 , and learning rates are automatically adjusted with a decrease factor of 0.7. Momentum is set at a constant value of 2500 throughout model training. For individual acoustic models, we find that training converges after 1.5 to 2 passes over the 2000-hour training set. We do not use dropout or gradient noise in our model training, only the aforementioned spatial smoothing technique for BLSTM model training.

Confusion network combination
After rescoring all system outputs with all language models, we combine all scores log-linearly and normalize to estimate utterance-level posterior probabilities. All N-best outputs for the same utterance are then concatenated and merged into a single word confusion network (CN), using the SRILM nbestrover tool [56,36].

System Selection
Unlike in our previous system, we do not apply estimated, system-level weights to the posterior probabilities estimated from the N-best hypotheses. All systems have equal weight upon combination. This simplification allows us to perform a brute-force search over all possible subsets of systems, picking the ones that give the lowest word error on the development set. We started with 9 of our best individual systems, and eliminated two, leaving a combination of 7 systems,

Confusion network rescoring and backchannel modeling
As a final processing step, we generate new N-best lists from the confusion networks resulting from system combination. Following [57], these are once more rescored using the Ngram LM, but also with a subset of the utterance-level LSTM-LMs, and one additional knowledge source. The word log posteriors from the confusion network take the place of the acoustic model scores in this final rescoring step.
The additional knowledge source at this stage was motivated by our analysis of differences between machine versus human transcription errors [24]. We found that the major machine-specific error pattern is a misrecognition of filled pauses ('uh', 'um') as backchannel acknowledgments ('uhhuh', 'mhm'). In order to allow the system learn a correction for this problem, we provide the number of backchannel tokens in a hypotheses as a pseudo-score and allow the score weight optimization to find a penalty for it. (Indeed, a negative weight is learned for the backchannel count.) Table 5 compares the individual systems that were selected for combination, before and after rescoring with LSTM-LMs, and then shows the progression of results in the final processing stages, starting with the LM-rescored individual systems, the system combination, and the CN rescoring. The collection of LSTM-LMs (which includes the sessionbased LMs) gives a very consistent 22 to 25% relative error reduction on individual systems, compared to the N-gram LM. The system combination reduces error by 4% relative over the best individual systems, and the CN rescoring improves another 2-3% relative.

CONCLUSIONS AND FUTURE WORK
We have described the latest iteration of our conversational speech recognition system. The acoustic model was enhanced by adding a CNN-BLSTM system, and the more systematic use of a variety of senone sets, to benefit later system combination. We also switched to combining different model architectures first at the senone/frame level, resulting in several acoustic combined systems that are then fed into the confusion-network-based combination at the word level. The language model was updated with larger vocabulary (lowering the OOV rate by about 0.2% absolute), additional LSTM-LM variants for rescoring, and most importantly, session-level LSTM-LM that can model global and local coherence between utterances, as well as dialog phenomena. The session-level model gives over 20% relative perplexity reduction. Finally, we introduce a confusion network rescoring step with special treatment for backchannels (based on a prior error analysis), that gives a small additional gain after systems are combined. Overall, we have reduced error rate for the Switchboard tasks by 12% relative, from 5.8% for the 2016 system, to now 5.1%. We note that this level of error is on par with the multi-transcriber error rate previously reported on the same task. Future work we plan from here includes a more thorough evaluation, including on the CallHome genre of speech. We also want to gain a better understanding of the linguistic phenomena captured by the session-level language model, and reexamine the differences between human transcriber and machine errors.