summaries: In this work the authors prove several claims regarding the inductive bias of gradient descent and gradient flow trained on deep linear networks with linearly separable data. They show that asymptotically gradient descent minimizes the risk, each weight matrix converges to its rank one approximation and the top singular vectors of two adjacent weight matrices align. Furthermore, for the logistic and exponential loss the induced linear predictor converges to the max margin solution.

summaries: This paper studies the properties of applying gradient flow and gradient descent to deep linear networks on linearly separable data. For strictly decreasing loss like the logistic loss, this paper shows 1) the loss goes to 0, 2) for every layer the normalized weight matrix converges to a rank-1 matrix 3) these rank-1 matrices are aligned. For the logistic loss, this paper further shows the linear function is the maximum margin solution.

abstractText: This paper establishes risk convergence and asymptotic weight matrix alignment — a form of implicit regularization — of gradient flow and gradient descent when applied to deep linear networks on linearly separable data. In more detail, for gradient flow applied to strictly decreasing loss functions (with similar results for gradient descent with particular decreasing step sizes): (i) the risk converges to 0; (ii) the normalized ith weight matrix asymptotically equals its rank-1 approximation uiv i ; (iii) these rank-1 matrices are aligned across layers, meaning |v> i+1ui| → 1. In the case of the logistic loss (binary cross entropy), more can be said: the linear function induced by the network — the product of its weight matrices — converges to the same direction as the maximum margin solution. This last property was identified in prior work, but only under assumptions on gradient descent which here are implied by the alignment phenomenon.

authors:
Sanjeev Arora
Nadav Cohen
Elad Hazan

title: On the optimization of deep networks: Implicit acceleration by overparameterization

venue: arXiv preprint arXiv:1802.06509,

authors:
Peter Bartlett
Dylan Foster
Matus Telgarsky

title: Spectrally-normalized margin bounds for neural networks

authors:
Simon S Du
Wei Hu
Jason D Lee

title: Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced

venue: arXiv preprint arXiv:1806.00900,

authors:
Suriya Gunasekar
Jason Lee
Daniel Soudry
Nathan Srebro

title: Implicit bias of gradient descent on linear convolutional networks

venue: arXiv preprint arXiv:1806.00468,

authors:
Ziwei Ji
Matus Telgarsky

title: Risk and parameter convergence of logistic regression

venue: arXiv preprint arXiv:1803.07300,

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffery Hinton

title: Imagenet classification with deep convolutional neural networks

venue: In NIPS,

authors:
Thomas Laurent
James von Brecht

title: Deep linear neural networks with arbitrary loss: All local minima are global

venue: arXiv preprint arXiv:1712.01473,

authors:
Jason D Lee
Max Simchowitz
Michael I Jordan
Benjamin Recht

title: Gradient descent converges to minimizers

venue: arXiv preprint arXiv:1602.04915,

authors:
Haihao Lu
Kenji Kawaguchi

title: Depth creates no bad local minima

venue: arXiv preprint arXiv:1702.08580,

authors:
Andrew M Saxe
James L McClelland
Surya Ganguli

title: Exact solutions to the nonlinear dynamics of learning in deep linear neural networks

venue: arXiv preprint arXiv:1312.6120,

authors:
Daniel Soudry
Elad Hoffer
Nathan Srebro

title: The implicit bias of gradient descent on separable data

venue: arXiv preprint arXiv:1710.10345v3,

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization

authors:
Yi Zhou
Yingbin Liang

title: Critical points of linear neural networks: Analytical forms and landscape properties

heading: 1 INTRODUCTION

text:
Efforts to explain the effectiveness of gradient descent in deep learning have uncovered an exciting possibility: it not only finds solutions with low error, but also biases the search for low complexity solutions which generalize well (Zhang et al., 2017; Bartlett et al., 2017; Soudry et al., 2017; Gunasekar et al., 2018).
This paper analyzes the implicit regularization of gradient descent and gradient flow on deep linear networks and linearly separable data. For strictly decreasing losses, the optimum is at infinity, and we establish various alignment phenomena:
• For each weight matrix Wi, the corresponding normalized weight matrix Wi/‖Wi‖F asymptotically equals its rank-1 approximation uiv>i , where the Frobenius norm ‖Wi‖F satisfies ‖Wi‖F → ∞. In other words, ‖Wi‖2/‖Wi‖F → 1, and asymptotically only the rank-1 approximation of Wi contributes to the final predictor, a form of implicit regularization. • Adjacent rank-1 weight matrix approximations are aligned: |v>i+1ui| → 1. • For the logistic loss, the first right singular vector v1 ofW1 is aligned with the data, meaning v1 converges to the unique maximum margin predictor ū defined by the data. Moreover, the linear predictor induced by the network, wprod := WL · · ·W1, is also aligned with the data, meaning wprod/‖wprod‖→ ū.
Simultaneously, this work proves that the risk is globally optimized: it asymptotes to 0. Alignment and risk convergence are proved simultaneously; the phenomena are coupled within the proofs.
Since the layers align, they can be viewed as a minimum norm solution: they do not “waste norm” on components which are killed off when the layers are multiplied together. Said another way, given data ((xi, yi))ni=1, the normalized matrices (W1/‖W1‖F , . . . ,WL/‖WL‖F ) asymptotically solve a maximum margin problem which demands all weight matrices be small, not merely their product:
max WL∈R1×dL−1 ‖WL‖F =1 · · · max W1∈Rd1×d0 ‖W1‖F =1 min i yi(WL · · ·W1)xi.
The paper is organized as follows. This introduction continues with related work, notation, and assumptions in Sections 1.1 and 1.2. The analysis of gradient flow is in Section 2, and gradient descent is analyzed in Section 3. The paper closes with future directions in Section 4; a particular highlight is a preliminary experiment on CIFAR-10 which establishes empirically that a form of the alignment phenomenon occurs on the standard nonlinear network AlexNet.

heading: 1.1 RELATED WORK

text:
On the implicit regularization of gradient descent, Soudry et al. (2017) show that for linear predictors and linearly separable data, the gradient descent iterates converge to the same direction as the maximum margin solution. Ji & Telgarsky (2018) further characterize such an implicit bias for general nonseparable data. Gunasekar et al. (2018) consider gradient descent on fully connected linear networks and linear convolutional networks. In particular, for the exponential loss, assuming the risk is minimized to 0 and the gradients converge in direction, they show that the whole network converges in direction to the maximum margin solution. These two assumptions are on the gradient descent process itself, and specifically the second one might be hard to interpret and justify. Compared with Gunasekar et al. (2018), this paper proves that the risk converges to 0 and the weight matrices align; moreover the proof here proves the properties simultaneously, rather than assuming one and deriving the other. Lastly, Arora et al. (2018) show for deep linear networks (and later Du et al. (2018) for ReLU networks) that gradient flow does not change the difference between squared Frobenius norms of any two layers. We use a few of these tools in our proofs; please see Sections 2 and 3 for details.
For a smooth (nonconvex) function, Lee et al. (2016) show that any strict saddle can be avoided almost surely with small step sizes. If there are only countably many saddle points and they are all strict, and if gradient descent iterates converge, then this implies (almost surely) they converge to a local minimum. In the present work, since there is no finite local minimum, gradient descent will go to infinity and never converge, and thus these results of Lee et al. (2016) do not show that the risk converges to 0.
There has been a rich literature on linear networks. Saxe et al. (2013) analyze the learning dynamics of deep linear networks, showing that they exhibit some learning patterns similar to nonlinear networks, such as a long plateau followed by a rapid risk drop. Arora et al. (2018) show that depth can help accelerate optimization. On the landscape properties of deep linear networks, Lu & Kawaguchi (2017); Laurent & von Brecht (2017) show that under various structural assumptions, all local optima are global. Zhou & Liang (2018) give a necessary and sufficient characterization of critical points for deep linear networks.

heading: 1.2 NOTATION, SETTING, AND ASSUMPTIONS

text:
Consider a data set {(xi, yi)}ni=1, where xi ∈ Rd, ‖xi‖ ≤ 1, and yi ∈ {−1,+1}. The data set is assumed to be linearly separable, i.e., there exists a unit vector uwhich correctly classifies every data point: for any 1 ≤ i ≤ n, yi〈u, xi〉 > 0. Furthermore, let γ := max‖u‖=1 min1≤i≤n yi〈u, xi〉 > 0 denote the maximum margin, and ū := arg max‖u‖=1 min1≤i≤n yi〈u, xi〉 denote the maximum margin solution (the solution to the hard-margin SVM).
A linear network of depth L is parameterized by weight matrices WL, . . . ,W1, where Wk ∈ Rdk×dk−1 , d0 = d, and dL = 1. Let W = (WL, . . . ,W1) denote all parameters of the network. The (empirical) risk induced by the network is given by
R(W ) = R (WL, . . . ,W1) = 1
n n∑ i=1 ` (yiWL · · ·W1xi) = 1 n n∑ i=1 ` ( 〈wprod, zi〉 ) ,
where wprod := (WL · · ·W1)>, and zi := yixi. The loss ` is assumed to be continuously differentiable, unbounded, and strictly decreasing to 0. Examples include the exponential loss `exp(x) = e−x and the logistic loss `log(x) = ln ( 1 + e−x ) .
Assumption 1. `′ < 0 is continuous, limx→−∞ `(x) =∞ and limx→∞ `(x) = 0.
This paper considers gradient flow and gradient descent, where gradient flow { W (t) ∣∣t ≥ 0, t ∈ R} can be interpreted as gradient descent with infinitesimal step sizes. It starts from some W (0) at
t = 0, and proceeds as dW (t)
dt = −∇R
( W (t) ) .
By contrast, gradient descent { W (t) ∣∣t ≥ 0, t ∈ Z} is a discrete-time process given by W (t+ 1) = W (t)− ηt∇R ( W (t) ) ,
where ηt is the step size at time t.
We assume that the initialization of the network is not a critical point and induces a risk no larger than the risk of the trivial linear predictor 0. Assumption 2. The initialization W (0) satisfies∇R ( W (0) ) 6= 0 andR ( W (0) ) ≤ R(0) = `(0).
It is natural to require that the initialization is not a critical point, since otherwise gradient flow/descent will never make a progress. The requirement R ( W (0) ) ≤ R(0) can be easily satisfied, for example, by making W1(0) = 0 and WL(0) · · ·W2(0) 6= 0. On the other hand, if R ( W (0) ) > R(0), gradient flow/descent may never minimize the risk to 0. Proofs of those claims are given in Appendix A.

heading: 2 RESULTS FOR GRADIENT FLOW

text: In this section, we consider gradient flow. Although impractical when compared with gradient descent, gradient flow can simplify the analysis and highlight proof ideas. For convenience, we usually useW ,Wk, andwprod, but they all change with (the continuous time) t. Only proof sketches are given here; detailed proofs are deferred to Appendix B.

heading: 2.1 RISK CONVERGENCE

text:
One key property of gradient flow is that it never increases the risk:
dR(W ) dt =
〈 ∇R(W ), dW
dt
〉 = −‖∇R(W )‖2 = − L∑ k=1 ∥∥∥∥ ∂R∂Wk ∥∥∥∥2 F ≤ 0. (1)
We now state the main result: under Assumptions 1 and 2, gradient flow minimizes the risk, Wk and wprod all go to infinity, and the alignment phenomenon occurs. Theorem 1. Under Assumptions 1 and 2, gradient flow iterates satisfy the following properties:
• limt→∞R(W ) = 0.
• For any 1 ≤ k ≤ L, limt→∞ ‖Wk‖F =∞.
• For any 1 ≤ k ≤ L, letting (uk, vk) denote the first left and right singular vectors of Wk,
lim t→∞ ∥∥∥∥ Wk‖Wk‖F − ukv>k ∥∥∥∥ F = 0.
Moreover, for any 1 ≤ k < L, limt→∞ ∣∣〈vk+1, uk〉∣∣ = 1. As a result,
lim t→∞ ∣∣∣∣∣∣ 〈 wprod∏L k=1 ‖Wk‖F , v1 〉∣∣∣∣∣∣ = 1, and thus limt→∞ ‖wprod‖ =∞.
Theorem 1 is proved using two lemmas, which may be of independent interest. To show the ideas, let us first introduce a little more notation. Recall that R(W ) denotes the empirical risk induced by the deep linear network W . Abusing the notation a little, for any linear predictor w ∈ Rd, we also useR(w) to denote the risk induced by w. With this notation,R(W ) = R(wprod), while
∇R(wprod) = 1
n n∑ i=1 `′ ( 〈wprod, zi〉 ) zi = 1 n n∑ i=1 `′ (WL · · ·W1zi) zi
is in Rd and different from∇R(W ), which has ∑L k=1 dkdk−1 entries, as given below:
∂R ∂Wk = W>k+1 · · ·W>L ∇R(wprod)>W>1 · · ·W>k−1.
Furthermore, for any R > 0, let
B(R) = { W ∣∣∣∣ max1≤k≤L ‖Wk‖F ≤ R } .
The first lemma shows that for any R > 0, the time spent by gradient flow in B(R) is finite. Lemma 1. Under Assumption 1 and 2, for any R > 0, there exists a constant (R) > 0, such that for any t ≥ 1 and any W ∈ B(R), ‖∂R/∂W1‖F ≥ (R). As a result, gradient flow spends a finite amount of time in B(R) for any R > 0, and max1≤k≤L ‖Wk‖F is unbounded.
Here is the proof sketch. If ‖Wk‖F are bounded, then ‖∇R(wprod)‖ will be lower bounded by a positive constant, therefore if ‖∂R/∂W1‖F = ‖WL · · ·W2‖‖∇R(wprod)‖ can be arbitrarily small, then ‖WL · · ·W2‖ and ‖wprod‖ can also be arbitrarily small, and thusR(W ) can be arbitrarily close toR(0). This cannot happen after t = 1, otherwise it will contradict Assumption 2 and eq. (1). To proceed, we need the following properties of linear networks from prior work (Arora et al., 2018; Du et al., 2018). For any time t ≥ 0 and any 1 ≤ k < L, W>k+1(t)Wk+1(t)−W>k+1(0)Wk+1(0) = Wk(t)W>k (t)−Wk(0)W>k (0). (2) To see this, just notice that
W>k+1 ∂R
∂Wk+1 = W>k+1 · · ·W>L ∇R(wprod)>W>1 · · ·W>k = ∂R ∂Wk W>k .
Taking the trace on both sides of eq. (2), we have∥∥Wk+1(t)∥∥2F −∥∥Wk+1(0)∥∥2F =∥∥Wk(t)∥∥2F −∥∥Wk(0)∥∥2F . (3) In other words, the difference between the squares of Frobenius norms of any two layers remains a constant. Together with Lemma 1, it implies that all ‖Wk‖F are unbounded. However, even if ‖Wk‖F are large, it does not follow necessarily that ‖wprod‖ is also large. Lemma 2 shows that this is indeed true: for gradient flow, as ‖Wk‖F get larger, adjacent layers also get more aligned to each other, which ensures that their product also has a large norm.
For 1 ≤ k ≤ L, let σk, uk, and vk denote the first singular value (the 2-norm), the first left singular vector, and the first right singular vector of Wk, respectively. Furthermore, define
D := ( max
1≤k≤L ‖Wk(0)‖2F
) − ‖WL(0)‖2F + L−1∑ k=1 ∥∥∥Wk(0)W>k (0)−W>k+1(0)Wk+1(0)∥∥∥ 2 ,
which depends only on the initialization. If for any 1 ≤ k < L,Wk(0)W>k (0) = W>k+1(0)Wk+1(0), then D = 0. Lemma 2. The gradient flow iterates satisfy the following properties:
• For any 1 ≤ k ≤ L, ‖Wk‖2F − ‖Wk‖22 ≤ D. • For any 1 ≤ k < L, 〈vk+1, uk〉2 ≥ 1− ( D+‖Wk+1(0)‖22+‖Wk(0)‖ 2 2 ) /‖Wk+1‖22.
• Suppose max1≤k≤L ‖Wk‖F →∞, then ∣∣∣〈wprod/∏Lk=1 ‖Wk‖F , v1〉∣∣∣→ 1.
The proof is based on eq. (2) and eq. (3). If Wk(0)W>k (0) = W > k+1(0)Wk+1(0), then eq. (2) gives that Wk+1 and Wk have the same singular values, and Wk+1’s right singular vectors and Wk’s left singular vectors are the same. If it is true for any two adjacent layers, since WL is a row vector, all layers have rank 1. With general initialization, we have similar results when ‖Wk‖F is large enough so that the initialization is negligible. Careful calculations give the exact results in Lemma 2.
An interesting point is that the implicit regularization result in Lemma 2 helps establish risk convergence in Theorem 1. Specifically, by Lemma 2, if all layers have large norms, ‖WL · · ·W2‖ will be large. If the risk is not minimized to 0, ‖∇R(wprod)‖ will be lower bounded by a positive constant, and thus ‖∂R/∂W1‖F = ‖WL · · ·W2‖‖∇R(wprod)‖ will be large. Invoking eq. (1), Lemma 1 and eq. (3) gives a contradiction. Since the risk has no finite optimum, ‖Wk‖F →∞.

heading: 2.2 CONVERGENCE TO THE MAXIMUM MARGIN SOLUTION

text:
Here we focus on the exponential loss `exp(x) = e−x and the logistic loss `log(x) = ln(1 + e−x). In addition to risk convergence, these two losses also enable gradient descent to find the maximum margin solution.
To get such a strong convergence, we need one more assumption on the data set. Recall that γ = max‖u‖=1 min1≤i≤n〈u, zi〉 > 0 denotes the maximum margin, and ū denotes the unique maximum margin predictor which attains this margin γ. Those data points zi for which 〈ū, zi〉 = γ are called support vectors. Assumption 3. The support vectors span the whole space Rd.
Assumption 3 appears in prior work Soudry et al. (2017), and can be satisfied in many cases: for example, it is almost surely true if the number of support vectors is larger than or equal to d and the data set is sampled from some density w.r.t. the Lebesgue measure. It can also be relaxed to the situation that the support vectors and the whole data set span the same space; in this case∇R(wprod) will never leave this space, and we can always restrict our attention to this space.
With Assumption 3, we can state the main theorem. Theorem 2. Under Assumptions 2 and 3, for almost all data and for losses `exp and `log, then limt→∞ ∣∣〈v1, ū〉∣∣ = 1, where v1 is the first right singular vector of W1. As a result, limt→∞ wprod/ ∏L k=1 ‖Wk‖F = ū.
Before summarizing the proof, we can simplify both theorems into the following minimum norm property mentioned in the introduction. Corollary 1. Under Assumptions 2 and 3, for almost all data and for losses `exp and `log,
min i yi ( WL ‖WL‖F · · · W1 ‖W1‖F ) xi −−−→ t→∞ max
AL∈R1×dL−1 ‖AL‖F =1 · · · max A1∈Rd1×d0 ‖A1‖F =1 min i yi (AL · · ·A1)xi.
Theorem 2 relies on two structural lemmas. The first one is based on a similar almost-all argument due to Soudry et al. (2017, Lemma 12). Let S ⊂ {1, . . . , n} denote the set of indices of support vectors. Lemma 3. Under Assumption 3, if the data set is sampled from some density w.r.t. the Lebesgue measure, then with probability 1,
α := min |ξ|=1,ξ⊥ū max i∈S 〈ξ, zi〉 > 0.
Let ū⊥ denote the orthogonal complement of span(ū), and let Π⊥ denote the projection onto ū⊥. We prove that if ‖Π⊥w‖ is large enough, gradient flow starting fromw will tend to decrease ‖Π⊥w‖. Lemma 4. Under Assumption 3, for almost all data, `exp and `log, and any w ∈ Rd, if 〈w, ū〉 ≥ 0 and ‖Π⊥w‖ is larger than 1+ln(n)/α for `exp or 2n/eα for `log, then 〈Π⊥w,∇R(w)〉 ≥ 0.
With Lemma 3 and Lemma 4 in hand, we can prove Theorem 2. Let Π⊥W1 denote the projection of rows of W1 onto ū⊥. Notice that
Π⊥wprod = ( WL . . .W2(Π⊥W1) )> and
d‖Π⊥W1‖2F dt = −2〈Π⊥wprod,∇R(wprod)〉.
If ‖Π⊥W1‖F is large compared with ‖W1‖F , since layers become aligned, ‖Π⊥wprod‖ will also be large, and then Lemma 4 implies that ‖Π⊥W1‖F will not increase. At the same time, ‖W1‖F →∞, and thus for large enough t, ‖Π⊥W1‖F must be very small compared with ‖W1‖F . Many details need to be handled to make this intuition exact; the proof is given in Appendix B.

heading: 3 RESULTS FOR GRADIENT DESCENT

text:
One key property of gradient flow which is used in the previous proofs is that it never increases the risk, which is not necessarily true for gradient descent. However, for smooth losses (i.e, with
Lipschitz continuous derivatives), we can design some decaying step sizes, with which gradient descent never increases the risk, and basically the same results hold as in the gradient flow case. Deferred proofs are given in Appendix C.
We make the following additional assumption on the loss, which is satisfied by the logistic loss `log. Assumption 4. `′ is β-Lipschitz (i.e, ` is β-smooth), and |`′| ≤ G (i.e., ` is G-Lipschitz).
Under Assumption 4, the risk is also a smooth function of W , if all layers are bounded. Lemma 5. Suppose ` is β-smooth. If R ≥ 1, then β(R) = 2L2R2L−2(β + G), and R(W ) is a β(R)-smooth function on the set B(R) = { W ∣∣‖Wk‖F ≤ R, 1 ≤ k ≤ L}.
Smoothness ensures that for any W,V ∈ B(R), R(W ) − R(V ) ≤ 〈∇R(V ),W − V 〉 + β(R)‖W−V ‖2/2 (see Bubeck et al. (2015) Lemma 3.4). In particular, if we choose some R and set a constant step size ηt = 1/β(R), then as long as W (t+ 1) and W (t) are both in B(R),
R ( W (t+ 1) ) −R ( W (t) ) ≤ 〈 ∇R ( W (t) ) ,−ηt∇R ( W (t) )〉 + β(R)η2t
2 ∥∥∥∇R (W (t))∥∥∥2 = − 1
2β(R) ∥∥∥∇R (W (t))∥∥∥2 = −ηt 2 ∥∥∥∇R (W (t))∥∥∥2 . (4) In other words, the risk does not increase at this step. However, similar to gradient flow, the gradient descent iterate will eventually escape B(R), which may increase the risk. Lemma 6. Under Assumption 1, 2 and 4, suppose gradient descent is run with a constant step size 1/β(R). Then there exists a time t whenW (t) 6∈ B(R), in other words, max1≤k≤L ‖Wk(t)‖F > R.
Fortunately, this issue can be handled by adaptively increasing R and correspondingly decreasing the step sizes, formalized in the following assumption. Assumption 5. The step size ηt = min{1/β(Rt), 1}, where Rt satisfies W (t) ∈ B(Rt− 1), and if W (t+ 1) ∈ B(Rt − 1), Rt+1 = Rt.
Assumption 5 can be satisfied by a line search, which ensures that the gradient descent update is not too aggressive and the boundary R is increased properly.
With the additional Assumptions 4 and 5, exactly the same theorems can be proved for gradient descent. We restate them briefly here. Theorem 3. Under Assumption 1, 2, 4, and 5, gradient descent satisfies
• limt→∞R ( W (t) ) = 0.
• For any 1 ≤ k ≤ L, limt→∞ ‖Wk(t)‖F =∞. • limt→∞ ∣∣∣〈wprod(t)/∏Lk=1 ‖Wk(t)‖F , v1(t)〉∣∣∣ = 1, where v1(t) is the first right singular vector
of W1(t). Theorem 4. Under Assumptions 2, 3 and 5, for the logistic loss `log and almost all data, limt→∞ ∣∣〈v1(t), ū〉∣∣ = 1, and limt→∞ wprod(t)/∏Lk=1 ‖Wk(t)‖F = ū. Corollary 2. Under Assumptions 2, 3 and 5, for the logistic loss `log and almost all data,
min i yi ( WL ‖WL‖F · · · W1 ‖W1‖F ) xi −−−→ t→∞ max
AL∈R1×dL−1 ‖AL‖F =1 · · · max A1∈Rd1×d0 ‖A1‖F =1 min i yi (AL · · ·A1)xi.
Proofs of Theorem 3 and 4 are given in Appendix C, and are basically the same as the gradient flow proofs. The key difference is that an error of ∑∞ t=0 η 2 t ‖∇R(W (t))‖2 will be introduced in many parts of the proof. However, it is bounded in light of eq. (4): ∞∑ t=0 η2t ∥∥∥∇R (W (t))∥∥∥2 ≤ ∞∑ t=0 ηt
∥∥∥∇R (W (t))∥∥∥2 ≤ 2R (W (0)) . Since all weight matrices go to infinity, such a bounded error does not matter asymptotically, and thus proofs still go through.

heading: 4 SUMMARY AND FUTURE DIRECTIONS

text:
This paper rigorously proves that, for deep linear networks on linearly separable data, gradient flow and gradient descent minimize the risk to 0, align adjacent weight matrices, and align the first right singular vector of the first layer to the maximum margin solution determined by the data. There are many potential future directions; a few are as follows.
Convergence rates and practical step sizes. This paper only proves asymptotic convergence, moreover for adaptive step sizes depending on the current weight matrix norms. A refined analysis with rates for practical step sizes (e.g., constant step sizes) would allow the algorithm to be compared to other methods which also globally optimize this objective, would suggest ways to improve step sizes and initialization, and ideally even exhibit a sensitivity to the network architecture and suggest how it could be improved.
Nonseparable data and nonlinear networks. Real-world data is generally not linearly separable, but nonlinear deep networks can reliably decrease the risk to 0, even with random labels (Zhang et al., 2017). This seems to suggest that a nonlinear notion of separability is at play; is there some way to adapt the present analysis?
The present analysis is crucially tied to the alignment of weight matrices: alignment and risk are analyzed simultaneously. Motivated by this, consider a preliminary experiment, presented in Figure 3, where stochastic gradient descent was used to minimize the risk of a standard AlexNet on CIFAR-10 (Krizhevsky et al., 2012; Krizhevsky & Hinton, 2009).
Even though there are ReLUs, max-pooling layers, and convolutional layers, the alignment phenomenon is occurring in a reduced form on the dense layers (the last three layers of the network). Specifically, despite these weight matrices having shape (1024, 4096), (4096, 4096), and (4096, 10) the key alignment ratios ‖Wi‖2/‖Wi‖F are much larger than their respective lower bounds (1024−1/2, 4096−1/2, 10−1/2). Two initializations were tried: default PyTorch initialization, and a Gaussian initialization forcing all initial Frobenius norms to be just 4, which is suggested by the norm preservation property in the analysis and removes noise in the weights.

heading: ACKNOWLEDGEMENTS

text: The authors are grateful for support from the NSF under grant IIS-1750051. This grant allowed them to focus on research, and when combined with an NVIDIA GPU grant, led to the creation of their beloved GPU machine DUTCHCRUNCH.

heading: A REGARDING ASSUMPTION 2

text:
Suppose W1(0) = 0 while WL(0) · · ·W2(0) 6= 0. First of all, WL(0) · · ·W1(0) = 0 and thus R ( W (0) ) = R(0). Moreover,〈
∇R ( wprod(0) ) , ū 〉 = 1
n n∑ i=1 `′(0)〈zi, ū〉 ≤ `′(0)γ < 0,
which implies∇R ( wprod(0) ) 6= 0 and ∂R/∂W1 = ( WL(0) · · ·W2(0) )>∇R (wprod(0))> 6= 0. On the other hand, if R ( W (0) ) > R(0), gradient flow/descent may never minimize the risk to 0. For example, suppose the network has two layers, and both the input and output have dimension 1; the network just computes the dot product of two vectors w1 and w2. Consider minimizing R(w1, w2) = exp ( −〈w1, w2〉 ) . If w1(0) = −w2(0) 6= 0, then R ( w1(0), w2(0) ) =
exp ( ‖w1‖2 ) > exp(0). It is easy to verify that for any t, w1(t) = −w2(t), andR ( w1(t), w2(t) ) ≥ exp(0) > 0.

heading: B OMITTED PROOFS FROM SECTION 2

text:
Proof of Lemma 1. Fix an arbitrary R > 0. If the claim is not true, then for any > 0, there exists some t ≥ 1 such that ‖Wk‖F ≤ R for all k while ∥∥∂R/∂W1∥∥2F ≤ 2, which means∥∥∥∥ ∂R∂W1 ∥∥∥∥2 F = ∥∥∥W>2 · · ·W>L ∇R(wprod)>∥∥∥2 F =‖WL · · ·W2‖2
∥∥∇R(wprod)∥∥2 ≤ 2. Since ‖wprod‖ ≤ RL, we have
〈∇R(wprod), ū〉 = 1
n n∑ i=1 `′ ( 〈wprod, zi〉 ) 〈zi, ū〉 ≤ 1 n n∑ i=1 `′ ( 〈wprod, zi〉 ) γ ≤ −Mγ,
where −M = max−RL≤x≤RL `′(x). Since `′ is continuous and the domain is bounded, the maximum is attained and negative, and thus M > 0. Therefore ∥∥∇R(wprod)∥∥ ≥ Mγ, and thus ‖WL · · ·W2‖ ≤ /Mγ. Since ‖W1‖F ≤ R, we further have ‖wprod‖ ≤ R/Mγ. In other words, after t = 1,
∥∥wprod∥∥ may be arbitrarily small, which implies R (wprod) can be arbitrarily close to R (0). On the other hand, by Assumption 2, dR(W )/ dt = −‖∇R(W )‖2 < 0 at t = 0. This implies that R ( W (1) ) < R ( W (0) ) , and for any t ≥ 1,R ( W (t) ) ≤ R ( W (1) ) < R ( W (0) ) ≤ R(0), which is a contradiction.
Since the risk is always positive, we have
R ( W (0) ) ≥ ∫ ∞ t=0 L∑ k=1 ∥∥∥∥ ∂R∂Wk ∥∥∥∥2 F dt
≥ ∫ ∞ t=0 ∥∥∥∥ ∂R∂W1 ∥∥∥∥2 F dt
≥ ∫ ∞ t=0 ∥∥∥∥ ∂R∂W1 ∥∥∥∥2 F 1 [ max 1≤k≤L ‖Wk‖F ≤ R ] dt
≥ ∫ ∞ t=1 ∥∥∥∥ ∂R∂W1 ∥∥∥∥2 F 1 [ max 1≤k≤L ‖Wk‖F ≤ R ] dt
≥ (R)2 ∫ ∞ t=1 1 [ max 1≤k≤L ‖Wk‖F ≤ R ] dt,
which implies gradient flow only spends a finite amount of time in { W ∣∣max1≤k≤L ‖Wk‖F ≤ R}. This directly implies that max1≤k≤L ‖Wk‖F is unbounded.
Proof of Lemma 2. The first claim is true for k = L since WL is a row vector. For any 1 ≤ k < L, recall that Arora et al. (2018); Du et al. (2018) give the following relation:
W>k+1(t)Wk+1(t)−W>k+1(0)Wk+1(0) = Wk(t)W>k (t)−Wk(0)W>k (0). (5)
Let Ak,k+1 = Wk(0)W>k (0)−W>k+1(0)Wk+1(0). By eq. (5) and the definition of singular vectors and singular values, we have
σ2k ≥ v>k+1WkW>k vk+1 = v>k+1W > k+1Wk+1vk+1 + v > k+1Ak,k+1vk+1
= σ2k+1 + v > k+1Ak,k+1vk+1 ≥ σ2k+1 − ‖Ak,k+1‖2. (6)
Moreover, by taking the trace on both sides of eq. (5), we have ‖Wk‖2F = tr ( WkW > k ) = tr ( W>k+1Wk+1 ) + tr ( Wk(0)W > k (0) ) − tr ( W>k+1(0)Wk+1(0) ) = ‖Wk+1‖2F + ‖Wk(0)‖2F − ‖Wk+1(0)‖2F . (7)
Summing eq. (6) and eq. (7) from k to L− 1, we get
‖Wk‖2F − ‖Wk‖22 ≤ ‖Wk(0)‖2F − ‖WL(0)‖2F + L−1∑ k′=k ‖Ak′,k′+1‖2 ≤ D. (8)
Next we prove that singular vectors get aligned. Consider u>kW > k+1Wk+1uk. On one hand, similar to eq. (6), we can get that
u>kW > k+1Wk+1uk = u > kWkW > k uk − u>kWk(0)W>k (0)uk + u>kW>k+1(0)Wk+1(0)uk
≥ u>kWkW>k uk − u>kWk(0)W>k (0)uk ≥ σ2k − ‖Wk(0)‖22. (9)
On the other hand, it follows from the definition of singular vectors and eq. (8) that
u>kW > k+1Wk+1uk = 〈uk, vk+1〉2σ2k+1 + u>k ( W>k+1Wk+1 − vk+1σ2k+1v>k+1 ) uk
≤ 〈uk, vk+1〉2σ2k+1 + ‖Wk+1‖2F − ‖Wk+1‖22 ≤ 〈uk, vk+1〉2σ2k+1 +D. (10)
Combining eq. (9) and eq. (10), we get
σ2k ≤ 〈uk, vk+1〉2σ2k+1 +D + ‖Wk(0)‖22. (11)
Similar to eq. (9), we can get
σ2k ≥ v>k+1WkW>k vk+1 ≥ σ2k+1 − ‖Wk+1(0)‖22.
Therefore σ2k σ2k+1 ≥ 1− ‖Wk+1(0)‖ 2 2 σ2k+1 . (12)
Combining eq. (11) and eq. (12), we finally get
〈uk, vk+1〉2 ≥ 1− D + ‖Wk(0)‖22 + ‖Wk+1(0)‖22
σ2k+1 .
Regarding the last claim, first recall that since the difference between the squares of Frobenius norms of any two layers is a constant, max1≤k≤L ‖Wk‖F → ∞ implies ‖Wk‖F → ∞ for any k. We further have the following.
• Since ‖Wk‖2F − ‖Wk‖22 ≤ D, ‖Wk‖2 →∞ for any k, and Wk/‖Wk‖F → ukv>k .
• Since ‖Wk‖2 →∞, |〈uk, vk+1〉| → 1.
As a result, ∣∣∣∣∣∣ 〈 wprod∏L k=1 ‖Wk‖F , v1 〉∣∣∣∣∣∣ = ∣∣∣∣∣∣ 〈 L∏ k=1 Wk ‖Wk‖F , v1 〉∣∣∣∣∣∣ → ∣∣∣∣∣∣ 〈 L∏ k=1 uiv > i , v1
〉∣∣∣∣∣∣ → 1.
Proof of Theorem 1. Suppose for some > 0, R (W ) ≥ for any t. Then there exists some 1 ≤ j ≤ n such that ` ( 〈wprod, zj〉 ) ≥ , and thus 〈wprod, zj〉 ≤ `−1( ). On the other hand,
since R(W ) ≤ R(0) = `(0), ` ( 〈wprod, zj〉 ) ≤ n`(0), and thus 〈wprod, zj〉 ≥ `−1 ( n`(0) ) . Let −M = max`−1(n`(0))≤x≤`−1( /n) ` ′(x) < 0, we have for any t,
〈∇R(wprod), ū〉 = 1
n n∑ i=1 `′ ( 〈wprod, zi〉 ) 〈zi, ū〉
≤ 1 n n∑ i=1 `′ ( 〈wprod, zi〉 ) γ
≤ 1 n `′ ( 〈wprod, zj〉 ) γ ≤ −Mγ n < 0,
and thus ‖∇R(wprod)‖ ≥Mγ/n. Similar to the proof of Lemma 2, we can show that if ‖Wk‖F →∞,∣∣∣∣∣∣ 〈 (WL · · ·W2)> ‖Wk‖F · · · ‖W2‖F , v2
〉∣∣∣∣∣∣→ 1. In other words, there exists some C > 0, such that when min1≤k≤L ‖Wk‖F > C, ‖WL · · ·W2‖ ≥ ‖Wk‖F · · · ‖W2‖F /2 > CL/2.
Lemma 1 shows that gradient flow spends a finite amount of time in { W ∣∣max1≤k≤L ‖Wk‖F ≤ R} for any R > 0. Since the difference between the squares of Frobenius norms of any two layers is a constant, gradient flow also spends a finite amount of time in { W ∣∣min1≤k≤L ‖Wk‖F ≤ C}. Now we have
R ( W (0) ) ≥ ∫ ∞ t=0 L∑ k=1 ∥∥∥∥ ∂R∂Wk ∥∥∥∥2 F dt
≥ ∫ ∞ t=0 ∥∥∥∥ ∂R∂W1 ∥∥∥∥2 F dt
= ∫ ∞ t=0 ‖WL · · ·W2‖2‖∇R(wprod)‖2 dt
≥ ∫ ∞ t=0 ‖WL · · ·W2‖2‖∇R(wprod)‖21 [ W ∣∣∣∣ min1≤k≤L ‖Wk‖F > C ] dt
≥ ( Mγ
n
)2( CL
2 )2 ∫ ∞ t=0 1 [ W ∣∣∣∣ min1≤k≤L ‖Wk‖F > C ] dt
=∞,
which is a contradiction. ThereforeR( )→ 0. This further implies ‖Wk‖F →∞, sinceR(W ) has no finite optimum. Finally, invoking Lemma 2 proves the final claim of Theorem 1.
Proof of Lemma 3. Soudry et al. (2017) Lemma 12 proves that, with probability 1, there are at most d support vectors, and moreover, the i-th support vector zi has a positive dual variable αi, such that∑ i∈S αizi = ū.
Suppose there exists some ξ ⊥ ū, such that maxi∈S〈ξ, zi〉 ≤ 0. Since∑ i∈S αi〈ξ, zi〉 = 〈 ξ, ∑ i∈S αizi 〉 = 〈ξ, ū〉 = 0,
we actually have 〈ξ, zi〉 = 0 for all i ∈ S. This is impossible under Assumption 3, since the support vectors span the whole space.
Proof of Lemma 4. For the sake of presentation, we leave out the subscript in zi and denote a data point by z generally. For any data point z and predictor w, let z⊥ and w⊥ denote their projection onto ū⊥. Let z′ ∈ arg maxi∈S〈−w⊥, z〉, and thus 〈−w⊥, z′〉 ≥ α‖w⊥‖. For `exp, we have
〈w⊥,∇R(w)〉 = ∑ z 1 n [ − exp ( −〈w, z〉 )] 〈w⊥, z⊥〉
= ∑ z 1 n [ exp ( 〈−w, z〉 )] 〈−w⊥, z⊥〉
≥ 1 n
exp ( 〈−w, z′〉 ) 〈−w⊥, z′⊥〉+ ∑ 〈z⊥,w⊥〉≥0 1 n exp ( 〈−w, z〉 ) 〈−w⊥, z⊥〉. (13)
The first part can be lower bounded as below (recall that 〈−w⊥, z′⊥〉 = 〈−w⊥, z′〉 ≥ α‖w⊥‖)
1 n exp
( 〈−w, z′〉 ) 〈−w⊥, z′⊥〉 = 1
n exp
( 〈−w, γū〉 ) exp ( 〈−w⊥, z′⊥〉 ) 〈−w⊥, z′⊥〉
≥ 1 n
exp ( −〈w, γū〉 ) exp ( α‖w⊥‖ ) α‖w⊥‖. (14)
To bound the second part, first notice that since we assume 〈w, ū〉 ≥ 0, for any z,
〈w, z − γū〉 = 〈w, z⊥〉+ 〈w, z − γū− z⊥〉 ≥ 〈w, z⊥〉 = 〈w⊥, z⊥〉. (15)
The reason is that every data point has margin at least γ, and thus z−γū−z⊥ = cū for some c ≥ 0. Using eq. (15), we can bound the second part of eq. (13).∑
〈z⊥,w⊥〉≥0
1 n exp
( 〈−w, z〉 ) 〈−w⊥, z⊥〉
= ∑
〈z⊥,w⊥〉≥0
1 n exp
( 〈−w, γū〉 ) exp ( 〈−w, z − γū〉 ) 〈−w⊥, z⊥〉
≥ ∑
〈z⊥,w⊥〉≥0
1 n exp
( 〈−w, γū〉 ) exp ( 〈−w⊥, z⊥ ) 〈−w⊥, z⊥〉
≥ ∑
〈z⊥,w⊥〉≥0
1 n exp
( 〈−w, γū〉 )( −1 e )
≥ exp ( 〈−w, γū〉 )( −1 e ) . (16)
On the third line eq. (15) is applied. The fourth line applies the property that f(x) = −xe−x ≥ −1/e when x ≥ 0.
Combining eq. (13), eq. (14) and eq. (16), we get
〈w⊥,∇R(w)〉 ≥ exp ( 〈−w, γū〉 )( 1 n exp ( α‖w⊥‖ ) α‖w⊥‖ − 1 e ) .

heading: As long as ‖w⊥‖ ≥ (1 + ln(n))/α, 〈w⊥,∇R(w)〉 ≥ 0.

text:
For `log, similar to eq. (13), we have
〈w⊥,∇R(w)〉 ≥ 1
n
exp ( 〈−w, z′〉 ) 1 + exp ( 〈−w, z′〉 ) 〈−w⊥, z′⊥〉+ ∑ 〈z⊥,w⊥〉≥0 1 n exp ( 〈−w, z〉 ) 1 + exp ( 〈−w, z〉
) 〈−w⊥, z⊥〉 ≥ 1 n exp ( 〈−w, z′〉 ) 1 + exp ( 〈−w, z′〉 ) 〈−w⊥, z′⊥〉+ ∑ 〈z⊥,w⊥〉≥0 1 n exp ( 〈−w, z〉 ) 〈−w⊥, z⊥〉.
(17)
The second part of eq. (17) can be bounded again by eq. (16). To bound the first part of eq. (17), first notice that (recall 〈w, ū〉 ≥ 0)
exp ( 〈−w, z′〉 ) = exp ( 〈−w, γū〉 ) exp ( 〈−w⊥, z′⊥〉 ) ≤ exp ( 〈−w⊥, z′⊥〉 ) . (18)
Using eq. (18), and recall that 〈−w⊥, z′⊥〉 = 〈−w⊥, z′〉 ≥ α‖w⊥‖ ≥ 0, we can bound the first part of eq. (17) as below.
1
n
exp ( 〈−w, z′〉 ) 1 + exp ( 〈−w, z′〉 ) 〈−w⊥, z′⊥〉 = 1n exp (〈−w, γū〉) exp ( 〈−w⊥, z′⊥〉 ) 1 + exp ( 〈−w, z′〉
) 〈−w⊥, z′⊥〉 ≥ 1 n exp ( 〈−w, γū〉 ) exp (〈−w⊥, z′⊥〉) 1 + exp ( 〈−w⊥, z′⊥〉
) 〈−w⊥, z′⊥〉 ≥ 1
2n exp
( 〈−w, γū〉 ) 〈−w⊥, z′⊥〉
≥ 1 2n
exp ( 〈−w, γū〉 ) α‖w⊥‖. (19)
Combining eq. (17), eq. (19) and eq. (16), we get
〈w⊥,∇R(w)〉 ≥ exp ( 〈−w, γū〉 )( 1 2n α‖w⊥‖ − 1 e ) .

heading: As long as ‖w⊥‖ ≥ 2n/eα, 〈w⊥,∇R(w)〉 ≥ 0.

text:
Proof of Theorem 2. Recall that
dW1 dt = − ∂R ∂W1 = −W>2 · · ·W>L ∇R(wprod)>,
and thus d‖W1‖2F
dt =
〈 W1,
dW1 dt
〉 = −2〈wprod,∇R(wprod)〉. (20)
Let Πū denote the projection onto span(ū), and let Π⊥ denote the projection onto ū⊥. Also let ΠūW1 and Π⊥W1 denote the projection of rows of W1 onto span(ū) and ū⊥, respectively. Notice that
Πūwprod = ( WL · · ·W2(ΠūW1) )> , and Π⊥wprod = ( WL · · ·W2(Π⊥W1) )> .
We further have d‖Π⊥W1‖2F
dt = −2〈Π⊥wprod,∇R(wprod)〉. (21)
Let W1 = u1σ1v>1 + S. We have ‖S‖2 ≤ σ1,2 ≤ √ σ21,2 ≤ √ ‖W1‖2F − ‖W1‖22 ≤ √ D, where σ1,2 is the second singular value of W1 and D is the constant introduced in Lemma 2. Then
Π⊥W1 = u1σ1 (Π⊥v1) > + Π⊥S,
and ‖Π⊥W1‖F ≤ ∥∥∥u1σ1 (Π⊥v1)>∥∥∥
F + ‖Π⊥S‖F = σ1‖Π⊥v1‖+ ‖Π⊥S‖F ≤ σ1‖Π⊥v1‖+
√ dD.
It follows that
‖Π⊥v1‖ ≥ ‖Π⊥W1‖F σ1 − √ dD σ1 ≥ ‖Π⊥W1‖F ‖W1‖F − √ dD ‖W1‖2 . (22)
Fix an arbitrary > 0. By Theorem 1, we can find some t0 large enough such that for any t ≥ t0:
1. √ dD/‖W1‖2 ≤ /3.
2. ‖wprod/‖WL‖F ···‖W1‖F − v1‖ ≤ /3, or ‖wprod/‖WL‖F ···‖W1‖F + v1‖ ≤ /3.
3. ‖WL‖F · · · ‖W1‖F ≥ 3K/ , where K is the threshold given in Lemma 4, i.e., 1+ln(n)/α for `exp, 2n/eα for `log.
4. R(W ) ≤ `(0)/n, which implies 〈wprod, zi〉 ≥ 0 for all 1 ≤ i ≤ n. By Lemma 3, there always exists a support vector z for which 〈Π⊥wprod, z〉 ≤ 0, and therefore 〈wprod, ū〉 ≥ 0.
Suppose for some t ≥ t0, ‖Π⊥W1‖F /‖W1‖F ≥ . By eq. (22) and bullet 1 above, ‖Π⊥v1‖ ≥ 2 /3. Bullet 2 above then gives ‖Π⊥wprod/‖WL‖F ···‖W1‖F‖ ≥ /3, which together with bullet 3 above implies ‖Π⊥wprod‖ ≥ K. Since also 〈wprod, ū〉 ≥ 0, we can apply Lemma 4 and get that 〈Π⊥wprod,∇R(wprod)〉 ≥ 0. In light of eq. (21), d‖Π⊥W1‖2F / dt ≤ 0.
On the other hand, since after t ≥ t0, 〈wprod, zi〉 ≥ 0, we have d‖W1‖2F / dt ≥ 0 by eq. (20). Therefore ‖Π⊥W1‖F /‖W1‖F will not increase, and since ‖W1‖F → ∞, it will eventually drop below , and will never exceed again. Therefore,
lim sup t→∞ ‖Π⊥W1‖F ‖W1‖F ≤ .
Since is arbitrary, we have
lim sup t→∞ ‖Π⊥W1‖F ‖W1‖F = 0,
and thus limt→∞ ∣∣〈v1, ū〉∣∣ = 1. An application of Theorem 1 gives the other part of Theorem 2.
Proof of Corollary 1. By Theorem 2,
min i yi ( WL ‖WL‖F · · · W1 ‖W1‖F ) xi −→ min i yiū >xi.
Next, pick arbitrary unit vectors ai ∈ Rdi , and note
max A1∈Rd1×d0 ‖A1‖F =1 · · · max AL∈R1×dL−1 ‖AL‖F =1 min i yi (AL · · ·A1)xi ≥ min i yi
( (1a>L−1)(aL−1a > L−2) · · · (a2a>1 )(a1ū>) ) xi
= min i yiū >xi.
On the other hand, if matrices (AL, . . . , A1) are feasible, then
‖AL · · ·A1‖2 ≤ ‖AL‖2 · · · ‖A2‖2‖A1‖F ≤ ‖AL‖F · · · ‖A1‖F ≤ 1, whereby
min i yi(AL · · ·A1)xi ≤ ‖AL · · ·A1‖2 min i yi ( AL · · ·A1 ‖AL · · ·A1‖2 ) xi
≤ 1 · max ‖w‖2=1 min i yiw >xi = min i yiū >xi.

heading: C OMITTED PROOFS FROM SECTION 3

text:
Proof of Lemma 5. GivenW,V ∈ B(R), we need to show that ‖∇R(W )−∇R(V )‖ ≤ β(R)‖W− V ‖ for some β(R). Consider k = 1 first. Let w = (WL · · ·W1)>, and v = (VL · · ·V1)>. Since |`′| ≤ G, ‖∇R(w)‖, ‖∇R(v)‖ ≤ G. We have∥∥∥∥ ∂R∂W1 − ∂R∂V1
∥∥∥∥ =∥∥∥W>2 · · ·W>L ∇R(w)− V >2 · · ·V >L ∇R(v)∥∥∥ ≤ ∥∥∥W>2 · · ·W>L ∇R(w)− V >2 W>3 · · ·W>L ∇R(w)∥∥∥ + ∥∥∥V >2 W>3 · · ·W>L ∇R(w)− V >2 · · ·V >L ∇R(v)∥∥∥
≤ RL−2G‖W2 − V2‖ + ∥∥∥V >2 W>3 · · ·W>L ∇R(w)− V >2 · · ·V >L ∇R(v)∥∥∥
≤ RL−2G‖W − V ‖ + ∥∥∥V >2 W>3 · · ·W>L ∇R(w)− V >2 · · ·V >L ∇R(v)∥∥∥ . (23)
Proceeding in this way, we can get∥∥∥∥ ∂R∂W1 − ∂R∂V1 ∥∥∥∥ ≤ (L− 1)RL−2G‖W − V ‖+RL−1‖∇R(w)−∇R(v)‖. (24) Since ‖zi‖ ≤ 1, `′ is β-Lipschitz, we have ‖∇R(w)−∇R(v)‖ ≤ β‖w − v‖ ≤ βLRL−1‖W − V ‖, (25)
where the last inequality follows from a similar one-by-one replacement procedure as in eq. (23). Combining eq. (24) and eq. (25), we get for R ≥ 1,∥∥∥∥ ∂R∂W1 − ∂R∂V1 ∥∥∥∥ ≤ ((L− 1)RL−2G+ βLR2L−2) ‖W − V ‖ ≤ 2LR2L−2(β +G)‖W − V ‖. The same procedure can be done for other layers, and together
‖∇R(W )−∇R(V )‖ ≤ 2L2R2L−2(β +G)‖W − V ‖.
Proof of Lemma 6. Recall that if W (t),W (t+ 1) ∈ B(R) and ηt = 1/β(R),
R ( W (t+ 1) ) −R ( W (t) ) ≤ 〈∇R ( W (t) ) ,−ηt∇R ( W (t) ) 〉+ β(R)η 2 t
2 ∥∥∥∇R (W (t))∥∥∥2 = − 1
2β(R) ∥∥∥∇R (W (t))∥∥∥2 = −ηt
2 ∥∥∥∇R (W (t))∥∥∥2 . (26) Suppose W (t) ∈ B(R) for all t. By Assumption 2 and eq. (26),
R ( W (1) ) ≤ R ( W (0) ) − 1
2β(R) ∥∥∥∇R (W (0))∥∥∥2 < R (W (0)) . By eq. (26), gradient descent never increases the risk, and thus for all t ≥ 1, R ( W (t) ) ≤
R ( W (1) ) < R ( W (0) ) . In exactly the same way as in the proof of Lemma 1, one can show that there exists some constant (R) > 0, so that ‖∂R/∂W1(t)‖F ≥ (R) for all t. Invoking eq. (26) again, we will get
R ( W (0) ) ≥ ∞∑ t=0 1 2β(R) (R)2 =∞,
which is a contradiction. Therefore W (t) must go out of B(R) at some time.
Next we prove Theorem 3 and 4. The proofs depend on several lemmas which are similar to the gradient flow ones. The following Lemma 7 is similar to Lemma 1. Lemma 7. Under Assumption 1, 2, 4, and 5, gradient descent ensures that
• max1≤k≤L ‖Wk(t)‖F is unbounded. • ∑∞ t=0 ηt =∞.
• For any R > 0, ∑ t:W (t)∈B(R) ηt <∞.
Proof. By Assumption 5, we always have thatW (t) ∈ B(Rt). Since β(Rt) = 2L2R2L−2t (β+G) ≥ RL−1t G, we have for any 1 ≤ k ≤ L,
‖Wk(t+ 1)‖F ≤ ‖Wk(t)‖F + ηt ∥∥∥∥ ∂R∂Wk(t) ∥∥∥∥ F
≤ ‖Wk(t)‖F + 1
β(Rt) ∥∥∥∥ ∂R∂Wk(t) ∥∥∥∥ F
≤ ‖Wk(t)‖F + 1
β(Rt) RL−1t G
≤ ‖Wk(t)‖F + 1. (27) Moreover, Lemma 6 shows that Rt → ∞. Since Rt+1 = Rt as long as W (t + 1) ∈ B(Rt − 1), max1≤k≤L ‖Wk(t)‖F is unbounded. It then follows that for any t, by Cauchy-Schwarz,t−1∑
τ=0
ητ t−1∑ τ=0 ητ ∥∥∥∇R (W (τ))∥∥∥2  ≥ t−1∑ τ=0 ητ ∥∥∥∇R (W (τ))∥∥∥ 2 →∞.
since by eq. (26), t−1∑ τ=0 ητ ∥∥∥∇R (W (τ))∥∥∥2 ≤ 2R (W (0))− 2R (W (t)) ≤ 2R (W (0)) , we have ∑∞ t=0 ηt =∞.
Since under Assumptions 4 and 5 gradient descent never increases the risk, it can be shown in exactly the same as in the proof of Lemma 1 that, for W (t) ∈ B(R), ‖∂R/∂W1(t)‖F ≥ (R) for some constant (R) > 0. Invoking eq. (26) again, we get that ∑ t:W (t)∈B(R) ηt <∞.
The next lemma is an analogy to Lemma 2. Lemma 8. Under Assumption 1 and 4, the gradient descent iterates satisfy the following properties:
• For any 1 ≤ k ≤ L, ‖Wk‖2F − ‖Wk‖22 ≤ D + 2R ( W (0) ) .
• For any 1 ≤ k < L, 〈vk+1, uk〉2 ≥ 1− D+3R(W (0))+‖Wk+1(0)‖22+‖Wk(0)‖22/‖Wk+1‖22. • Suppose max1≤k≤L ‖Wk‖F →∞, then ∣∣∣〈wprod/∏Lk=1 ‖Wk‖F , v1〉∣∣∣→ 1.
Proof. Recall that for any W ,
W>k+1 ∂R
∂Wk+1 = W>k+1 · · ·W>L ∇R(wprod)>W>1 · · ·W>k = ∂R ∂Wk W>k . (28)
For gradient descent iterates, summing eq. (28) from 0 to t− 1, we get
W>k+1(t)Wk+1(t)−W>k+1(0)Wk+1(0) + t−1∑ τ=0 η2τ ( ∂R ∂Wk+1(τ) )>( ∂R ∂Wk+1(τ) )
= Wk(t)W > k (t)−Wk(0)W>k (0) + t−1∑ τ=0 η2τ ( ∂R ∂Wk(τ) )( ∂R ∂Wk(τ) )> . (29)
For any 1 ≤ k ≤ L and any t, let
Pk(t) = t−1∑ τ=0 η2τ ( ∂R ∂Wk(τ) )( ∂R ∂Wk(τ) )> ,
and
Qk(t) = t−1∑ τ=0 η2τ ( ∂R ∂Wk(τ) )>( ∂R ∂Wk(τ) ) .
We have ‖Pk(t)‖2 = ‖Qk(t)‖2 ≤ tr ( Qk(t) ) = tr ( Pk(t) ) . Moreover, invoking eq. (26),
L∑ k=1 tr ( Pk(t) ) = L∑ k=1 t−1∑ τ=0 η2τ ∥∥∥∥ ∂R∂Wk(τ) ∥∥∥∥2 F
= t−1∑ τ=0 η2τ ∥∥∥∇R (W (τ))∥∥∥2 ≤
t−1∑ τ=0 ητ ∥∥∥∇R (W (τ))∥∥∥2 ≤ 2R ( W (0) ) − 2R ( W (t)
) ≤ 2R ( W (0) ) . (30)
Still let σk(t), uk(t) and vk(t) denote the first singular value, left singular vector and right singular vector of Wk(t). We can then proceed basically in the same way as in the proof of Lemma 2. For example, eq. (6) becomes
σ2k(t) ≥ σ2k+1(t)− ‖Ak,k+1(t)‖2 − ‖Pk(t)‖2 ≥ σ2k+1(t)− ‖Ak,k+1(t)‖2 − tr ( Pk(t) ) , (31)
while eq. (7) becomes ‖Wk(t)‖2F = ‖Wk+1(t)‖2F + ‖Wk(0)‖2F − ‖Wk+1(0)‖2F − tr ( Pk(t) ) + tr ( Qk+1(t) ) . (32)
Summing eq. (31) and eq. (32) from k to L− 1, and invoke eq. (30), we get
‖Wk(t)‖2F − ‖Wk(t)‖22 ≤ D − tr ( Pk(t) ) + tr ( QL(t) ) + L−1∑ k′=k tr ( Pk′(t) ) ≤ D + 2R ( W (0) ) .
To prove singular vectors get aligned, we can still proceed in nearly the same way as in the proof of Lemma 2. eq. (9) becomes
u>kW > k+1Wk+1uk ≥ σ2k − ‖Wk(0)‖22 − ‖Qk+1(t)‖2, (33)
while eq. (10) becomes
u>kW > k+1Wk+1uk ≤ 〈uk, vk+1〉2σ2k+1 +D + 2R
( W (0) ) . (34)
Combining eq. (33) and eq. (34) σ2k ≤ 〈uk, vk+1〉2σ2k+1 +D + 2R ( W (0) ) + ‖Qk+1(t)‖2 + ‖Wk(0)‖22. (35)
Similar to eq. (33), we can get
σ2k ≥ v>k+1WkW>k vk+1 ≥ σ2k+1 − ‖Wk+1(0)‖22 − ‖Pk(t)‖2, and thus eq. (12) becomes
σ2k σ2k+1 ≥ 1− ‖Wk+1(0)‖ 2 2 + ‖Pk(t)‖2 σ2k+1 . (36)
Combining eq. (35) and eq. (36), we get
〈uk, vk+1〉2 ≥ 1− D + ‖Wk(0)‖22 + ‖Wk+1(0)‖22 + 3R
( W (0) ) σ2k+1 .
The final claim of Lemma 8 can be proved in exactly the same way as Lemma 2.
Proof of Theorem 3. Summing eq. (32), we know that for any two different layers j > k, ‖Wk(t)‖2F − ‖Wj(t)‖2F = ‖Wk(0)‖2F − ‖Wj(0)‖2F − tr ( Pk(t) ) + tr ( Qj(t) ) . Recall eq. (30), we know that∣∣∣∣(‖Wk(t)‖2F − ‖Wj(t)‖2F)− (‖Wk(0)‖2F − ‖Wj(0)‖2F)∣∣∣∣ ≤ 2R (W (0)) . (37) In other words, the difference between the squares of Frobenius norms of any two layers is still bounded.
The proof then goes in the same way as the proof of Theorem 1. Suppose the risk is always above > 0. Then there exists some c( ) > 0 such that ‖∇R(wprod)‖ ≥ c( ). By Lemma 8, there exists some C such that if min1≤k≤L ‖Wk(t)‖F > C, ‖WL(t) · · ·W2(t)‖ ≥ CL/2. By eq. (37) and Lemma 7, ∑ t:‖Wk(t)‖F≤C for some k ηt is finite. On the other hand, by Lemma 7, ∑∞ i=0 ηt =∞, and
thus ∑ t:‖Wk(t)‖F>C for all k ηt =∞. Therefore we have, by invoking eq. (26),
2R ( W (0) ) ≥ ∞∑ t=0 ηt ∥∥∥R (W (t))∥∥∥2 ≥ ∞∑ t=0 ηt ∥∥∥∥ ∂R∂W1(t) ∥∥∥∥2
≥ c( )C L
2 ∑ t:‖Wk(t)‖F>C for all k ηt
=∞, which is a contradiction. Therefore R ( W (t) ) → 0, and since it has no finite optimum, ‖Wk‖F → ∞. The other results follow from Lemma 7.
Proof of Theorem 4. Recall that
∂R ∂W1 = W>2 · · ·W>L ∇R(wprod),
and thus ‖W1(t+ 1)‖2F = ‖W1(t)‖2F − 2ηt 〈 W1(t),
∂R ∂W1(t)
〉 + η2t ∥∥∥∥ ∂R∂W1(t) ∥∥∥∥2 F
= ‖W1(t)‖2F − 2ηt 〈 wprod(t),∇R ( wprod(t) )〉 + η2t ∥∥∥∥ ∂R∂W1(t) ∥∥∥∥2 F .

heading: If 〈wprod, zi〉 ≥ 0 for all i, then ‖W1(t+ 1)‖F ≥ ‖W1(t)‖F .

text:
Also recall that Π⊥W1(t) denote the projection of rows of W1(t) onto ū⊥, the orthogonal complement of span(ū). We have
‖Π⊥W1(t+ 1)‖2F ≤ ‖Π⊥W1(t)‖2F − 2ηt 〈 Π⊥W1(t), ∂R
∂W1(t)
〉 + η2t ∥∥∥∥ ∂R∂W1(t) ∥∥∥∥2 F
= ‖Π⊥W1(t)‖2F − 2ηt 〈 Π⊥wprod(t),∇R ( wprod(t) )〉 + η2t ∥∥∥∥ ∂R∂W1(t) ∥∥∥∥2 F .
(38)
Invoking eq. (26) again gives
η2t ∥∥∥∥ ∂R∂W1(t) ∥∥∥∥2 F ≤ ηt ∥∥∥∇R (W (t))∥∥∥2 ≤ 2(R (W (t))−R (W (t+ 1))) . (39)
The proof then goes in almost the same way as the proof of Theorem 2. For any > 0, we can find some large enough time t0, such that for any t ≥ t0,
1. ‖Π⊥W1(t)‖F /‖W1(t)‖F ≥ implies that 〈 Π⊥wprod(t),∇R ( wprod(t) )〉 ≥ 0.
2. 〈wprod(t), zi〉 ≥ 0 for all i, and thus ‖W1(t+ 1)‖F ≥ ‖W1(t)‖F . 3. ‖W1(t)‖F ≥ 1+ √ 2R(W (0))/ .
Suppose at some time t1 ≥ t0, ‖Π⊥W1(t1)‖F /‖W1(t1)‖F ≥ . As long as this still holds, in light of bullet (1) above, eq. (38) and eq. (39), ‖Π⊥W1‖2F will increase by at most 2R ( W (t1) ) ≤
2R ( W (0) ) . On the other hand, ‖W1‖F → ∞, and thus there exists some t2 > t1 such that ‖Π⊥W1(t2)‖F /‖W1(t2)‖F < . Let t3 denote the smallest time after t2 such that ‖Π⊥W1(t3)‖F /‖W1(t3)‖F ≥ (if it exists). Recall that ‖W1(t+ 1)‖F ≤ ‖W1(t)‖F + 1 for any t ≥ 0, and ‖W1(t+ 1)‖F ≥ ‖W1(t)‖F for any t ≥ t0, we have
‖Π⊥W1(t3)‖F ‖W1(t3)‖F ≤ ‖Π⊥W1(t3)‖F ‖W1(t3 − 1)‖F ≤ ‖Π⊥W1(t3 − 1)‖F + 1 ‖W1(t3 − 1)‖F < + 1 ‖W1(t3 − 1)‖F .
After t3, ‖Π⊥W1‖2F will increase by at most 2R ( W (0) ) , and thus ‖Π⊥W1‖F will increase by at
most √ 2R ( W (0) ) . Therefore, for any t4 ≥ t3, as long as ‖Π⊥W1(t4)‖F /‖W1(t4)‖F ≥ , we
have
‖Π⊥W1(t4)‖F ‖W1(t4)‖F ≤ ‖Π⊥W1(t4)‖F ‖W1(t3)‖F
≤ ‖Π⊥W1(t3)‖F +
√ 2R ( W (0) ) ‖W1(t3)‖F
≤ + 1 ‖W1(t3 − 1)‖F +
√ 2R ( W (0) ) ‖W1(t3)‖F ≤ 2 ,
since ‖W1(t)‖F ≥ 1+ √ 2R(W (0))/ after t0. In other words,
lim sup t→∞ ‖Π⊥W1‖F ‖W1‖F ≤ 2 .
Since is arbitrary, we have
lim sup t→∞ ‖Π⊥W1‖F ‖W1‖F = 0,
and thus limt→∞ ∣∣〈v1, ū〉∣∣ = 1.
Proof of Corollary 2. The proof is analogous to that of Corollary 1, except using Theorem 4 in place of Theorem 2.

title: GRADIENT DESCENT ALIGNS THE LAYERS OF DEEP LINEAR NETWORKS


summaries: This paper proposes an extension to hredGAN, which is an adversarial framework for multi-turn dialogue model, to simultaneously learns a set of attribute embeddings that represents the persona of each speaker and generate persona-based responses. The generator of the proposed system phredGAN is conditioned on both the history utterances and the speakers’ persona by concatenating the utterance encoding with attribute embeddings. For discriminator, the authors explore two versions: 1) phredGAN_a takes attributes as inputs; 2) phredGAN_d adds a dual discriminator that predicts the attribute(s) for each utterance.

summaries: This paper uses the idea from 'A Persona-Based Neural Conversation Model' by Li et al and incrementally applies it to the 'Multi-turn Dialogue Response Generation in an Adversarial Learning Framework' work-in-progress by Olabiyi et al. The paper by Olabiyi uses the idea of adversarial training to the HRED work by Xing et al (Hierarchical Recurrent Attention Network for Response Generation). The paper shows very promising results for controlling the response generation based on input attributes with adversarial training. Compared to the persona based model, this work seems to outperform that model significantly as reported in Table 1 (in terms of Perplexity/Bleu). It would have been great to see the quantitative comparison in terms of other metrics (if the authors could try to reproduce their results). There are other interesting ways to incorporate attribute information into the dialogue model such as reported in the work of Lee et al (SCALABLE SENTIMENT FOR SEQUENCE-TO-SEQUENCE CHATBOT RESPONSE WITH PERFORMANCE ANALYSIS) - since this paper is primarily about personalization of responses - a comparison to some of the methods used in Lee's work would have been very relevant and made the paper much more convincing in terms of core contributions. The model and architecture is pretty convincing but the paper lacks more in-depth analysis, comparison and evaluation of the model.

abstractText: In this paper, we extend the persona-based sequence-to-sequence (Seq2Seq) neural network conversation model to a multi-turn dialogue scenario by modifying the state-of-the-art hredGAN architecture to simultaneously capture utterance attributes such as speaker identity, dialogue topic, speaker sentiments and so on. The proposed system, phredGAN has a persona-based HRED generator (PHRED) and a conditional discriminator. We also explore two approaches to accomplish the conditional discriminator: (1) phredGANa, a system that passes the attribute representation as an additional input into a traditional adversarial discriminator, and (2) phredGANd, a dual discriminator system which in addition to the adversarial discriminator, collaboratively predicts the attribute(s) that generated the input utterance. To demonstrate the superior performance of phredGAN over the persona SeqSeq model, we experiment with two conversational datasets, the Ubuntu Dialogue Corpus (UDC) and TV series transcripts from the Big Bang Theory and Friends. Performance comparison is made with respect to a variety of quantitative measures as well as crowd-sourced human evaluation. We also explore the trade-offs from using either variant of phredGAN on datasets with many but weak attribute modalities (such as with Big Bang Theory and Friends) and ones with few but strong attribute modalities (customer-agent interactions in Ubuntu dataset).

authors:
D. Bahdanau
K. Cho
Y. Bengio

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

venue: In Proceedings of International Conference of Learning Representation

title: Movie-dic: A movie dialogue corpus for research and development

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

authors:
X. Glorot
Y. Bengio

title: Understanding the difficulty of training deep feedforward neural networks

venue: In International conference on artificial intelligence and statistics,

authors:
S. Jean
K. Cho
R. Memisevic
Y. Bengio

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

venue: In arXiv preprint arXiv:1412.2007,

authors:
J. Li
M. Galley
C. Brockett
J. Gao
B. Dolan

title: A diversity-promoting objective function for neural conversation models

venue: In Proceedings of NAACL-HLT,

authors:
J. Li
M. Galley
C. Brockett
G. Spithourakis
J. Gao
B. Dolan

title: A persona-based neural conversation model

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

title: Rouge: a package for automatic evaluation of summaries

venue: In Proceedings of the Workshop on Text Summarization Branches Out,

authors:
H. Nguyen
D. Morales
T. Chin

title: A neural chatbot with personality

venue: In Stanford NLP Course website:

authors:
O. Olabiyi
A. Salimov
A. Khazane
E. Mueller

title: Multi-turn dialogue response generation in an adversarial learning framework

venue: In arXiv preprint arXiv:1805.11752,

authors:
K. Papineni
S. Roukos
T. Ward
W. Zhu

title: Bleu: A method for automatic evalution of machine translation

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

authors:
I. Serban
A. Sordoni
Y. Bengio
A. Courville
J. Pineau

title: Building end-to-end dialogue systems using generative hierarchical neural network models

venue: In Proceedings of The Thirtieth AAAI Conference on Artificial Intelligence (AAAI 2016),

authors:
I.V. Serban
T. Klinger
G. Tesauro
K. Talamadupula
B. Zhou
Y. Bengio
A. Courville

title: Multiresolution recurrent neural networks: An application to dialogue response generation

venue: In Proceedings of The Thirty-first AAAI Conference on Artificial Intelligence (AAAI 2017),

authors:
I.V. Serban
A. Sordoni
R. Lowe
L. Charlin
J. Pineau
A. Courville
Y. Bengio

title: A hierarchical latent variable encoder-decoder model for generating dialogue

authors:
I. Sutskever
O. Vinyals
Q. Le

title: Sequence to sequence learning with neural networks

venue: In Proceedings of Advances in Neural Information Processing Systems (NIPS),

authors:
O. Vinyals
Q. Le

title: A neural conversational model

venue: In Proceedings of ICML Deep Learning Workshop,

authors:
C. Xing
W. Wu
Y. Wu
M. Zhou
Y. Huang
W. Ma

title: Hierarchical recurrent attention network for response generation

venue: In arXiv preprint arXiv:1701.07149,

authors:
S. Zhang
E. Dinan
J. Urbanek
A. Szlam
D. Kiela
J. Weston

title: Personalizing dialogue agents: I have a dog, do you have pets too

venue: In arXiv preprint arXiv:1801.07243v3,

title: toN − 1 do Update the context state. hi = cRNN(eRNN(E(Xi)),hi−1, Ci) Compute the generator output similar to Eq

venue: PθG

heading: 1 INTRODUCTION

text:
Recent advances in machine learning especially with deep neural networks has lead to tremendous progress in natural language processing and dialogue modeling research (Sutskever et al., 2014; Vinyals & Le, 2015; Serban et al., 2016). Nevertheless, developing a good conversation model capable of fluent interaction between a human and a machine is still in its infancy stage. Most existing work relies on limited dialogue history to produce response with the assumption that the model parameters will capture all the modalities within a dataset. However, this is not true as dialogue corpora tend to be strongly multi-modal and practical neural network models find it difficult to disambiguate characteristics such as speaker personality, location and sub-topic in the data.
Most work in this domain has primarily focused on optimizing dialogue consistency. For example, Serban et al. (Serban et al., 2016; 2017b;a) and Xing et al. (2017) introduced a Hierarchical Recurrent Encoder-Decoder (HRED) network architecture that combines a series of recurrent neural networks to capture long-term context state within a dialogue. However, the HRED system suffers from lack of diversity and does not have any guarantee on the generator output since the output conditional probability is not calibrated. Olabiyi et al. (2018) tackles these problems by training a modified HRED generator alongside an adversarial discriminator in order to increase diversity and provide a strong and calibrated guarantee to the generator’s output. While the hredGAN system improves upon response quality, it does not capture speaker and other attributes modality within a dataset and fails to generate persona specific responses in datasets with multiple modalities.
On the other hand, there has been some recent work on introducing persona into dialogue models. For example, Li et al. (2016b) integrates attribute embeddings into a single turn (Seq2Seq) generative dialogue model. In this work, Li et al. consider persona models one with Speaker-only representation and the other with Speaker and Addressee representations (Speaker-Addressee model), both of which capture certain speaker identity and interactions. Nguyen et al. (2018) continue along the
same line of thought by considering a Seq2Seq dialogue model with Responder-only representation. In both of these cases, the attribute representation is learned during the system training. Zhang et al. (2018) proposed a slightly different approach. Here, the attributes are a set of sentences describing the profile of the speaker. In this case, the attributes representation is not learned. The system however learns how to attend to different parts of the attributes during training. Still, the above persona-based models have limited dialogue history (single turn); suffer from exposure bias worsening the trade-off between personalization and conversation quality and cannot generate multiple responses given a dialogue context. This is evident in the relatively short and generic responses produced by these systems, even though they generally capture the persona of the speaker.
In order to overcome these limitations, we propose two variants of an adversarially trained persona conversational generative system, phredGAN , namely phredGANa and phredGANd. Both systems aim to maintain the response quality of hredGAN and still capture speaker and other attribute modalities within the conversation. In fact, both systems use the same generator architecture (PHRED generator), i.e., an hredGAN generator (Olabiyi et al., 2018) with additional utterance attribute representation at its encoder and decoder inputs as depicted in Figure 1. Conditioning on external attributes can be seen as another input modality as is the utterance into the underlying system. The attribute representation is an embedding that is learned together with the rest of model parameters similar to Li et al. (2016b). Injecting attributes into a multi-turn dialogue system allows the model to generate responses conditioned on particular attribute(s) across conversation turns. Since the attributes are discrete, it also allows for exploring different what-if scenarios of model responses. The difference between the two systems is in the discriminator architecture based on how the attribute is treated.
We train and sample both variants of phredGAN similar to the procedure for hredGAN (Olabiyi et al., 2018). To demonstrate model capability, we train on a customer service related data such as the Ubuntu Dialogue Corpus (UDC) that is strongly bimodal between question poser and answerer, and transcripts from a multi-modal TV series The Big Bang Theory and Friends with quantitative and qualitative analysis. We examine the trade-offs between using either system in bi-modal or multi-modal datasets, and demonstrate system superiority over state-of-the-art persona conversational models in terms of dialogue response quality and quantitatively with perplexity, BLEU, ROUGE and distinct n-gram scores.

heading: 2 MODEL ARCHITECTURE

text:
In this section, we briefly introduce the state-of-the-art hredGAN model and subsequently show how we derive the two persona versions by combining it with the distributed representation of the dialogue speaker and utterance attributes, or with an attribute discrimination layer at the end of the model pipeline.
2.1 hredGAN : ADVERSARIAL LEARNING FRAMEWORK
Problem Formulation: The hredGAN (Olabiyi et al., 2018) formulates multi-turn dialogue response generation as: given a dialogue history of sequence of utterances, Xi = ( X1, X2, · · · , Xi ) ,
where each utterance Xi = ( X1i , X 2 i , · · · , X Mi i ) contains a variable-length sequence of Mi word tokens such that Xij ∈ V for vocabulary V , the dialogue model produces an output Yi = ( Y 1i , Y 2 i , · · · , Y Ti i ) , where Ti is the number of generated tokens. The framework uses conditional GAN structure to learn a mapping from an observed dialogue history to a sequence of output tokens. The generator, G, is trained to produce sequences that cannot be distinguished from the ground truth by an adversarially trained discriminator, D akin to a two-player min-max optimization problem. The generator is also trained to minimize the cross-entropy loss LMLE(G) between the ground truthXi+1, and the generator output Yi. The following objective summarizes both goals:
G∗, D∗ = argmin G max D
( λGLcGAN (G,D) + λMLMLE(G) ) . (1)
where λG and λM are training hyperparamters andLcGAN (G,D) andLMLE(G) are defined in Eqs. (5) and (7) of Olabiyi et al. (2018) respectively. Please note that the generator G and discriminator D share the same encoder and embedding representation of the word tokens.
2.2 phredGAN : PERSONA ADVERSARIAL LEARNING FRAMEWORK
The proposed architecture of phredGAN is very similar to that of hredGAN (Olabiyi et al., 2018). The only difference is that the dialogue history is now Xi = ( (X1, C1), (X2, C2), · · · , (Xi, Ci) ) where Ci is additional input that represents the speaker and/or utterance attributes. Please note that Ci can either be a sequence of tokens or single token such that Cij ∈ V c for vocabulary V c. Also, at the ith turn, Ci and Ci+1 are the source/input attribute and target/output attribute to the generator respectively. The embedding for attribute tokens is also learned similar to that of word tokens.
Both versions of phredGAN shares the same generator architecture (PHRED) but different discriminators. Below is the highlight of how they are derived from the hredGAN architecture.
Encoder: The context RNN, cRNN takes the source attribute Ci as an additional input by concatenating its representation with the output of eRNN as in Figure 1. If the attribute Ci is a sequence of tokens, then an attention (using the output of eRNN ) over the source attribute representations is concatenated with the output of eRNN . This output is used by the generator to create a context state for a turn i.
Generator: The generator decoder RNN, dRNN takes the target attribute Ci+1 as an additional input as in Fig. 1. If the attribute Ci+1 is a sequence of tokens, then an attention (using the output of dRNN ) over the attribute representations is concatenated with the rest of the decoder inputs. This forces the generator to draw a connection between the generated responses and the utterance attributes such as speaker identity.
Noise Injection: As in Olabiyi et al. (2018), we also explore different noise injection methods.
Objective: For phredGAN , the optimization objective in eq. (1) can be updated as:
G∗, D∗adv, D ∗ att = argmin
G ( max Dadv λGadvLadvcGAN (G,Dadv) (2)
+min Datt
λGattLattc (G,Datt) + λMLMLE(G) ) .
where LadvcGAN (G,Dadv) and Lattc (G,Datt) are the traditional adversarial and attribute prediction loss respectively and dependent on the architectural variation. It is worth to point out that while the former is adversarial, the later is collaborative in nature. The MLE loss is common and can be expressed as:
LMLE(G) = EXi+1 [−log PG ( Xi+1|Xi, Ci+1, Zi ) ]. (3)
where Zi the noise sample and depends on the choice of either utterance-level or word-level noise input into the generator (Olabiyi et al., 2018).
2.3 phredGANa: ATTRIBUTES AS A DISCRIMINATOR INPUT
phredGANa shares the same discriminator architecture as the hredGAN but with additional input, Ci+1. Since it does not use attribute prediction, λGatt = 0.
The adversarial loss, LadvcGAN (G,D) can then be expressed as:
LadvcGAN (G,Dadv) = EXi,Ci+1,Xi+1 [logDadv(Xi, Ci+1, Xi+1)] (4) + EXi,Ci+1,Zi [1− logDadv(Xi, Ci+1, G(Xi, Ci+1, Zi))]
The addition of speaker or utterance attributes allows the dialogue model to exhibit personality traits given consistent responses across style, gender, location, and so on.
2.4 phredGANd: ATTRIBUTES AS A DISCRIMINATOR TARGET
phredGANd does not take the attribute representation at its input but rather use the attributes as the target of an additional discriminator Datt. The adversarial and the attribute prediction losses can be respectively expressed as:
LadvcGAN (G,Dadv) = EXi,Xi+1 [logDadv(Xi, Xi+1)] (5) + EXi,Zi [1− logDadv(Xi, G(Xi, Ci+1, Zi))]
Lattc (G,Datt) = ECi+1 [− logDatt(Ci+1|Xi, Xi+1)] (6) + ECi+1 [− logDatt(Ci+1|Xi, G(Xi, Ci+1, Zi))]
Attribute Discriminator: In addition to the existing word-level adversarial discriminator Dadv from hredGAN , we add an attribute discriminator, Datt, that discriminates on an utterance level to capture attribute modalities since attributes are assigned at utterance level. The discriminator uses a unidirectional RNN (DattRNN ) that maps the input utterance to the particular attribute(s) that generated it. The attributes can be seen as hidden states that inform or shape the generator outputs. The attribute discriminator can be expressed as:
Datt(Ci+1|Xi, χ) = DattRNN (hi, E(χ)) (7) where E(.) is the word embedding lookup (Olabiyi et al., 2018), χ = Xi+1 for groundtruth and χ = Yi for the generator output.

heading: 3 MODEL TRAINING AND INFERENCE

heading: 3.1 MODEL TRAINING

text:
We train both the generator and the discriminator (with shared encoder) of both variants of phredGAN using the training procedure in Algorithm 1 (Olabiyi et al., 2018). For both variants, λGadv = λM = 1, and for phredGANa and phredGANd, λGatt = 0 and λGatt = 1 respectively. Since the encoder, word embedding and attribute embedding are shared, we are able to train the system end-to-end with back-propagation.
Encoder: The encoder RNN, eRNN , is bidirectional while cRRN is unidirectional. All RNN units are 3-layer GRU cell with hidden state size of 512. We use word vocabulary size, V = 50, 000 with word embedding size of 512. The number of attributes, V c is dataset dependent but we use an attribute embedding size of 512. In this study, we only use one attribute per utterance so that is no need to use attention to combine the attribute embeddings.
Generator: The generator decoder RNN, dRNN is also a 3-layer GRU cell with hidden state size of 512. The aRNN outputs are connected to the dRNN input using an additive attention mechanism (Bahdanau et al., 2015).
Adversarial Discriminator: The word-level discriminator RNN, DRNN is a bidirectional RNN, each 3-layer GRU cell with hidden state size of 512. The output of both the forward and the backward cells for each word are concatenated and passed to a fully-connected layer with binary output. The output is the probability that the word is from the ground truth given the past and future words of the sequence, and in the case of phredGANa, the responding speaker’s embedding.
Attribute Discriminator: The attribute discriminator RNN,DattRNN is a unidirectional RNN with a 3-layer GRU cell, each of hidden state size 512. A softmax layer is then applied to project the final hidden state to a prespecified number of attributes, Vc. The output is the probability distribution over the attributes.
Others: All parameters are initialized with Xavier uniform random initialization (Glorot & Bengio, 2010). Due to the large word vocabulary size, we use sampled softmax loss (Jean et al., 2015) for MLE loss to expedite the training process. However, we use full softmax for model evaluation. For both systems, parameters updates are conditioned on the word-level discriminator accuracy performance as in Olabiyi et al. (2018) with accDthadv = 0.99 and accGth = 0.75. The model is trained end-to-end using the stochastic gradient descent algorithm. Finally, the model is implemented, trained, and evaluated using the TensorFlow deep learning framework.

heading: 3.2 MODEL INFERENCE

text:
We use an inference strategy similar to the approach in Olabiyi et al. (2018).
For the modified noise sample, we perform a linear search for αwith sample size L = 1 based on the average word-level discriminator loss, −logDadv(G(.)) (Olabiyi et al., 2018) using trained models run in autoregressive mode to reflect performance in actual deployment. The optimum α value is then used for all inferences and evaluations. During inference, we condition the dialogue response generation on the encoder outputs, noise samples, word embedding and the attribute embedding of the intended responder. With multiple noise samples, L = 64, we rank the generator outputs by the discriminator which is also conditioned on encoder outputs, and the intended responder’s attribute embedding. The final response is the response ranked highest by the discriminator. For phredGANd, we average the confidences produced by Dadv and Datt.

heading: 4 EXPERIMENTS AND RESULTS

text: In this section, we explore the performance of PHRED, phredGANa and phredGANd on two conversational datasets and compare its performance to non-adversarial persona Seq2seq models Li et al. (2016b) as well as to the adversarial hredGAN (Olabiyi et al., 2018) with no explicit persona.

heading: 4.1 DATASETS

text:
TV Series Transcripts dataset (Serban et al., 2016). We train all models on transcripts from the two popular TV drama series, Big Bang Theory and Friends. Following a similar preprocessing setup in Li et al. (2016b), we collect utterances from the top 12 speakers from both series to construct a corpus of 5,008 lines of multi-turn dialogue. We split the corpus into training, development, and test set with a 94%, 3%, and 3% proportions, respectively, and pair each set with a corresponding attribute file that maps speaker IDs to utterances in the combined dataset.
Due to the small size of the combined transcripts dataset, we first train our model on the larger Movie Triplets Corpus (MTC) by Banchs (2012) which consists of 240,000 dialogue triples. We pre-train
our model on this dataset to initialize our model parameters to avoid overfitting on a relatively small persona TV series dataset. After pre-training on MTC, we reinitialize the attribute embeddings in the generator from a uniform distribution following a Xavier initialization (Glorot & Bengio, 2010) for training on the combined person TV series dataset.
Ubuntu Dialogue Corpus (UDC) dataset (Serban et al., 2017b). We train our model on 1.85 million conversations of multi-turn dialogue from the Ubuntu community hub, with an average of 5 utterances per conversation. We assign two types of speaker IDs to utterances in this dataset: questioner and helper. We follow a similar training, development, and test split as the UDC dataset in Olabiyi et al. (2018), with 90%, 5%, and 5% proportions, respectively, and pair each set with a corresponding attribute file that maps speaker IDs to utterances in the combined dataset
While the overwhelming majority of utterances in UDC follow two speaker types, the dataset does include utterances that do not classify under either a questioner or helper speaker type. In order to remain consistent, we assume that there are only two speaker types within this dataset and that the first utterance of every dialogue is from a questioner. This simplifying assumption does introduce a degree of noise into each persona model’s ability to construct attribute embeddings. However, our experiment results demonstrate that both phredGANa and phredGANd is still able to differentiate between the larger two speaker types in the dataset.

heading: 4.2 EVALUATION METRICS

text: We use similar evaluation metrics as in Olabiyi et al. (2018) including perplexity, BLEU (Papineni et al., 2002), ROUGE (Lin, 2014), distinct n-gram (Li et al., 2016a) and normalized average sequence length (NASL) scores. For human evaluation, we follow a similar setup as Li et al. (2016a), employing crowd-sourced judges to evaluate a random selection of 200 samples. We present both the multi-turn context and the generated responses from the models to 3 judges and asked them to rank the general response quality in terms of relevance, informativeness, and persona. For N models, the model with the lowest quality is assigned a score 0 and the highest is assigned a score N-1. Ties are not allowed. The scores are normalized between 0 and 1 and averaged over the total number of samples and judges.

heading: 4.3 BASELINE

text:
We compare the non-adversarial persona HRED model, PHRED with the adversarially trained ones, i.e. hredGAN , phredGANa and phredGANd, to demonstrate the impact of adversarial training. Please note that no noise was added to the PHRED model.
We also compare the persona models to Li et al.’s work (Li et al., 2016b) which uses a Seq2Seq framework in conjunction with learnable persona embeddings. Their work explores two persona models in order to incorporate vector representations of speaker interaction and speaker attributes into the decoder of their Seq2Seq model i.e., Speaker model (SM) and Speaker-Addressee model (SAM). All reported results are based on our implementation of their models in Li et al. (2016b).

heading: 4.4 HYPERPARAMETER SEARCH

text:
For both phredGANa and phredGANd, we determine the noise injection method and the optimum noise variance α that allows for the best performance on both datasets. We find that phredGANd performs optimally with word-level noise injection on both Ubuntu and TV transcripts, while phredGANa performs the best with utterance-level noise injection on TV transcripts and word-level injection on UDC. For all phredGAN models, we perform a linear search for optimal noise variance values between 1 and 30 at an increment of 1, with a sample size of L = 1. For phredGANd, we obtain an optimal α of 4 and 6 for the UDC and TV Transcripts respectively. For phredGANa,
we obtain an optimal value of 2 and 5 for the combined TV series dataset and the much larger UDC respectively.

heading: 4.5 RESULTS

text: We will now present our assessment of performance comparisons of phredGAN against the baselines, PHRED, hredGAN and Li et al.’s persona Seq2Seq models.

heading: 4.6 QUANTITATIVE ANALYSIS

text:
We first report the performance on TV series transcripts in table 1. The performance of both SM and SAM models in Li et al. (2016b) compared to the hredGAN shows a strong baseline and indicates that the effect of persona is more important than that of multi-turn and adversarial training for datasets with weak multiple persona. However, once the persona information is added to the hredGAN , the resulting phredGAN shows a significant improvement over the SM and SAM baselines with phredGANa performing best. We also observe that PHRED performs worse than the baseline S(A)M models on a number of metrics but we attribute this to the effect of persona on a limited dataset that results into less informative responses. This behavior was also reported in Li et al. (2016b) where the persona models produce less informative responses than the non-personal Seq2seq models but it seems to be even worse in multi-turn context. However, unlike the SpeakerAddressee and PHRED models that suffer from lower response quality due to persona conditioning, we note that conditioning the generator and discriminator of phredGAN on speaker embeddings does not compromise the systems ability to produce diverse responses. This problem might have been alleviated by the adversarial training that encourages the generator model to produce longer, more informative, and diverse responses that have high persona relevance even with a limited dataset.
We also compare the models performances on the UDC. The evaluation result is summarized in table 2. While the deleterious effect of persona conditioning on response diversity is still worse with PHRED than with S(A)M models, we note that hredGAN performs much better than the S(A)M models. This is because, the external persona only provides just a little more information than is already available from the UDC utterances. We also note an improvement of phredGAN variants over the hredGAN in a variety of evaluation metrics including perplexity, ROUGE with the exception of distinct n-grams. This is expected as phredGAN should be generally less diverse than hredGAN since the number of distinct data distribution modes is more for phredGAN dataset due to the persona attributes. However, this leads to better response quality with persona, something not achievable with hredGAN . Also, the much better ROUGE(F1) score indicates that phredGAN is able to strike a better balance between diversity and precision while still capturing the characteristics of the speaker attribute modality in the UDC dataset. Within the phredGAN variants, phredGANd seems to perform better. This is not surprising as speaker classification is much easier on UDC than on TV series. The attribute discriminator, Datt is able to provide more informative feedback on UDC than on TV series where it is more difficult to accurately predict the speaker. Therefore, we recommend phredGANa for datasets with weak attribute distinction and phredGANd for strong attribute distinction.

heading: 4.7 QUALITATIVE ANALYSIS

text:
In addition to the quantitative analysis above, we report the results of the human evaluation in the last column of tables 1 and 2 for the TV Series and UDC datasets respectively. The human evaluation scores largely agrees with the automatic evaluations on the TV Series with phredGANa clearly giving the best performance. However, on the UDC, both hredGAN and phredGANd performs similarly which indicates that there is a trade off between diversity and persona by each model. We believe this is due to the strong persona information that already exists in the UDC utterances.
An additional qualitative assessment of these results are in Table 3 with responses from several characters in the TV series dataset and the two characters in UDC.
We see that for TV drama series, phredGAN responses are comparatively more informative than that of the Speaker-Addressee model of Li et al. (2016b). For example, all the characters in the TV series respond the same to the dialogue context. Similar behavior is reported in Li et al. (2016b) where for the Speaker-Addressee model, nearly all the characters in the TV series respond with
“Of course I love you.” to the dialogue context, “Do you love me?” despite the fact that some of the responders sometimes have unfriendly relationship with the addressee. Many of the novel situations explored by phredGAN are unachievable with the Speaker-Addressee model due to lack of informative responses. For example, by conditioning as Sheldon from The Big Bang Theory and asking “Do you like me?”, our model responds with annoyance if conditioned as Penny (“No, you don’t understand. You’re an idiot”), brevity with Leonard (“Yes?”) and sarcasm with Raj (“Well , you know , we could be a little more than my friend’s friends.”) The wide range of responses indicate our model’s ability to construct distinct attribute embeddings for each character even from a limited dataset. The other interesting responses in table 3 indicate phredGAN ’s ability to infer not only the context of the conversation but important character information about the addressee.
We also see similar results with our model’s output on UDC in table 4. We demonstrate that by conditioning as either a helper or questioner from the UDC dataset, phredGAN models are able to respond differently to input utterances as well as stay close to the context of the conversation.

heading: 5 CONCLUSION AND FUTURE WORK

text:
In this paper, we improve upon state-of-the-art persona-based response generation models by exploring two persona conversational models: phredGANa which passes the attribute representation as an additional input into a traditional adversarial discriminator, and phredGANd a dual discriminator system which in addition to the adversarial discriminator from hredGAN , collaboratively predicts the attribute(s) that are intrinsic to the input utterance. Both systems demonstrate quantitative improvements upon state-of-the-art persona conversational systems such as the work from Li et al. (2016b) with respect to both quantitative automatic and qualitative human measures.
Our analysis also demonstrates how both variants of phredGAN perform differently on datasets with weak and strong modality. One of our future direction is to take advantage of phredGANd’s ability to predict utterance attribute such as speaker identity from just the utterance. We believe its performance can be improved even with weak modality by further conditioning adversarial updates on both the attribute and adversarial discriminator accuracies. Overall, this paper demonstrates clear benefits from adversarial training of persona generative dialogue system and leaves the door open for more interesting work to be accomplished in this domain.

heading: 6 RESULTS - DISCRIMINATOR

text:
After training both phredGAN models on the TV series and UDC datasets, we ran inference on some example dialogue contexts. The responses and their discriminator scores from phredGANs are listed in Tables 6, and 7. The tables shows that phredGAN (i) can handle multi-turn dialogue context with utterances and corresponding persona attributes; (ii) generates responses conditioned on a persona attribute; (iii) generates multiple responses per dialogue context and score their human likelihood by the discriminator; and (iv) in case of phredGANd, can predict the attribute such as speaker identity that might have produced the utterance. We observe that the discriminator score(s) is/are generally reasonable with longer, more informative and more persona-related responses receiving higher scores. It worth to note that this behavior, although similar to the behavior of a human judge is learned without supervision. More so, we observe that phredGAN responses retain contextual consistency sometimes referencing background information that is inherent in the conversation between two speakers. For example, in the second sample of the TV series in Table 6, phredGANa generator, conditioned on Leonard refers to Sheldon by name who is the second interlocutor. Also, in the third sample, phredGANa, conditioned on Raj refers to Penny when responding to Leonard who happens to be Penny’s boy friend. We see similar persona-based response generation for the UDC dataset with distinct communication style between the asker and the helper. For example, in Table 7, when the asker could not hear some music, phredGANd, conditioned on helper suggested the asker might not be using the right driver. For the purpose of completion, we also show some samples from PHRED generator on both UDC and TV series dataset in Table 5.
Context 0 Sheldon NA NA NA Did I? Well, that cant be right. No ones ever done that before. Except me,because I just did it. Sheldon and his brain, yeah. Response 0 Leonard 0.7028 Rachel 0.3805 You ’ re really good . Response 1 Leonard 0.5998 Rachel 0.3805 You know , I can ’ t believe you can ’ to do that . Response 2 Leonard 0.4384 Rachel 0.3805 You ’ re right .
Context 0 Leonard NA NA NA Shes gotten really hooked on Age of Conan, shes playing non-stop. Response 0 Raj 0.6707 Rachel 0.2867 You know , I , I just want to be friends with you . Response 1 Raj 0.6451 Rachel 0.2867 You ’ want on to do that ? Response 2 Raj 0.4138 Rachel 0.2867 You okay ?
UDC Context 0 asker NA NA NA all i need some quick amarok help. i cant hear my music Context 1 helper NA NA NA is amarok muted? Context 2 asker NA NA NA no Response 0 helper 0.4489 helper 0.8582 ok , so you ’ re not using the right driver for the network card , you ’ re using the UNK ? Response 1 helper 0.2312 helper 0.8582 ok , so you ’ re not using the right driver , right ? Response 2 helper 0.1381 helper 0.8582 ok , so you are you using the UNK ?
Context 0 asker NA NA NA anyone had problems with the kernel update from today? giving me a kernel panic Context 1 helper NA NA NA you can select previous kernels at the bootloader (grub) menu on booth. Response 0 asker 0.3431 asker 0.8126 ok , so i ’ ll have to reinstall the new kernel , i ’ ll try that . Response 1 asker 0.2518 asker 0.8126 ok , so i ’ just reinstall the ubuntu version ? Response 2 asker 0.1005 asker 0.8126 ok , thanks :)
Context 0 asker NA NA NA how do I install Ubuntu? Response 0 helper 0.4306 helper 0.8540 ok , so you have to reinstall the kernel from the CD , and you can ’ t install the iso to the CD Response 1 helper 0.3783 helper 0.8540 ok , so you have to go to the ubuntu site and see if you have the same version ? Response 2 helper 0.1618 helper 0.8540 ok , so are you using the ubuntu version ? ?