space. In general, a covariant derivative, also known as a linear connection,
is a bilinear mapping $(X,Y)\mapsto\nabla_{X}Y$ that maps two vector fields
$X,Y$ to a third vector field $\nabla_{X}Y$ in such a way that it can be
interpreted as the directional derivative of $Y$ in the direction of $X$, [36,
§4, §5]. Of importance is the Riemannian connection or Levi-Civita connection
that is compatible with a Riemannian metric [3, Thm 5.3.1], [36, Thm 5.10]. It
is determined uniquely by the Koszul formula

$\displaystyle 2\langle\nabla_{X}Y,Z\rangle$ $\displaystyle=$ $\displaystyle
X(\langle Y,Z\rangle)+Y(\langle Z,X\rangle)-Z(\langle X,Y\rangle)$
$\displaystyle-\langle X,[Y,Z]\rangle-\langle
Y,[X,Z]\rangle+\langle{Z},{[X,Y]}\rangle$

and is used to define the Riemannian curvature tensor

$(X,Y,Z)\mapsto
R(X,Y)Z=\nabla_{X}\nabla_{Y}Z-\nabla_{Y}\nabla_{X}Z-\nabla_{[X,Y]}Z.$

A Riemannian manifold is flat if and only if it is locally isometric to the
Euclidean space, which holds if and only if the Riemannian curvature tensor
vanishes identically [36, Thm. 7.10].

#### Lie Groups and Orbits

A _Lie group_ is a smooth manifold that is also a group with smooth
multiplication and inversion. A matrix Lie group $G$ is a subgroup of the
general linear group $GL(n,\mathbb{C})$ that is closed in $GL(n,\mathbb{C})$
(but not necessarily in the ambient space $\mathbb{C}^{n\times n}$). Basic
examples include $GL(n,\mathbb{R})$ and the orthogonal group $\mathrm{O}(n)$.
Any matrix Lie group $G$ is automatically an embedded submanifold of
$\mathbb{C}^{n\times n}$ [24, Corollary 3.45]. The tangent space $T_{I}G$ of
$G$ at the identity $I\in G$ has a special role. When endowed with the bracket
operator or matrix commutator $[V,W]=VW-WV$ for $V,W\in T_{I}G$, the tangent
space becomes an algebra, called the Lie algebra associated with the Lie group
$G$, see [24, §3]. As such, it is denoted by $\mathfrak{g}=T_{I}G$. For any
$A\in G$, the function “left-multiplication with $A$” is a diffeomorphism
$L_{A}\colon G\to G,\ L_{A}(B)=AB$; its differential at a point $B\in G$ is
the isomorphism $\mathrm{d}(L_{A})_{B}\colon T_{B}G\to T_{L_{A}(B)}G,\
\mathrm{d}(L_{A})_{B}(V)=AV$. Using this observation at $B=I$ shows that the
tangent space at an arbitrary location $A\in G$ is given by the translates (by
left-multiplication) of the tangent space at the identity [22, §5.6, p. 160],

$T_{A}G=T_{L_{A}(I)}G=A\mathfrak{g}=\left\\{\Delta=AV\in\mathbb{R}^{n\times
n}|\hskip 5.69046ptV\in\mathfrak{g}\right\\}.$ (A.3)

A _smooth left action_ of a Lie group $G$ on a manifold $M$ is a smooth map
$\phi\colon G\times M\to M$ fulfilling
$\phi(g_{1},\phi(g_{2},p))=\phi(g_{1}g_{2},p)$ and $\phi(e,p)=p$ for all
$g_{1},g_{2}\in G$ and all $p\in M$, where $e\in G$ denotes the identity
element. One often writes $\phi(g,p)=g\cdot p$. For each $p\in M$, the _orbit
of $p$_ is defined as

$G\cdot p:=\\{g\cdot p\mid g\in G\\},$ (A.4)

and the _stabilizer of $p$_ is defined as

$G_{p}:=\\{g\in G\mid g\cdot p=p\\}.$ (A.5)

For a detailed introduction see for example [35]. We need the following well
known result, see for example [28, Section 2.1], where the quotient manifold
$G/G_{p}$ refers to the set $\\{gG_{p}\mid g\in G\\}$ endowed with the unique
manifold structure that turns the quotient map $g\mapsto gG_{p}$ into a
submersion.

######  Proposition 2.

Let $G$ be a compact Lie group acting smoothly on a manifold $M$. Then for any
$p\in M$, the orbit $G\cdot p$ is an embedded submanifold of $M$ that is
diffeomorphic to the quotient manifold $G/G_{p}$.

###### Proof.

The continuous action of a compact Lie group is always proper, [35, Corollary
21.6]. Therefore [4, Proposition 3.41] shows the claim. ∎

##  Appendix B Matrix Analysis Necessities

Throughout, we consider the matrix space $\mathbb{R}^{m\times n}$ as a
Euclidean vector space with the standard metric

$\langle A,B\rangle_{0}=\operatorname{tr}(A^{T}B).$ (B.1)

Unless noted otherwise, the singular value decomposition (SVD) of a matrix
$X\in\mathbb{R}^{m\times n}$ is understood to be the compact SVD

$X=U\Sigma V^{T},\quad U\in\mathbb{R}^{m\times
n},\Sigma,V\in\mathbb{R}^{n\times n}.$

The SVD is not unique.

######  Proposition 1 (Ambiguity of the Singular Value Decomposition).

[30, Theorem 3.1.1’] Let $X\in\mathbb{R}^{m\times n}$ have a (full) SVD
$X=U\Sigma V^{T}$ with singular values in descending order and
$\operatorname{rank}(X)=r$. Let $\sigma_{1}>\dots>\sigma_{k}>0$ be the
distinct nonzero singular values with respective multiplicity
$\mu_{1},\dots,\mu_{k}$. Then $X=\tilde{U}\Sigma\tilde{V}^{T}$ is another SVD
if and only if $\tilde{U}=U\operatorname{diag}(D_{1},\dots,D_{k},W_{1})$ and
$\tilde{V}=V\operatorname{diag}(D_{1},\dots,D_{k},W_{2})$, with
$D_{i}\in\mathrm{O}(\mu_{i})$, $W_{1}\in\mathrm{O}(m-r)$, and
$W_{2}\in\mathrm{O}(n-r)$ arbitrary.

#### Differentiating the Singular Value Decomposition

Let $p\leq n\in\mathbb{N}$ and suppose that $t\mapsto
Y(t)\in\mathbb{R}^{n\times p}$ is a differentiable matrix curve around
$t_{0}\in\mathbb{R}$. If the singular values of $Y(t_{0})$ are mutually
distinct and non-zero, then the singular values and both the left and the
right singular vectors depend differentiable on $t\in[t_{0}-\delta
t,t_{0}+\delta t]$ for $\delta t$ small enough.

Let $t\mapsto Y(t)=U(t)\Sigma(t)V(t)^{T}\in\mathbb{R}^{n\times p}$, where
$U(t)\in\mathrm{St}(n,p)$, $V(t)\in O(p)$ and $\Sigma(t)\in\mathbb{R}^{p\times
p}$ diagonal and positive definite. Let $u_{j}$ and $v_{j}$, $j=1,\ldots,p$
denote the columns of $U(t_{0})$ and $V(t_{0})$, respectively. For brevity,
write
$Y=Y(t_{0}),\dot{Y}=\frac{\mathrm{d}}{\mathrm{d}t}\big{|}_{t=t_{0}}Y(t)$,
likewise for the other matrices that feature in the SVD. The derivatives of
the matrix factors of the SVD can be calculated with Alg. 2. A proof can for
example be found in [25, 16].

Algorithm 2 Differentiating the SVD

1:Matrices $Y,\dot{Y}\in\mathbb{R}^{n\times p}$, (compact) SVD $Y=U\Sigma
V^{T}$.

2: $\dot{\sigma}_{j}=(u_{j})^{T}\dot{Y}v_{j}\mbox{ for }j=1,\ldots,p$

3: $\dot{V}=V\Gamma,\mbox{ where
}\Gamma_{ij}=\left\\{\begin{array}[]{ll}\frac{\sigma_{i}(u_{i}^{T}\dot{Y}v_{j})+\sigma_{j}(u_{j}^{T}\dot{Y}v_{i})}{(\sigma_{j}+\sigma_{i})(\sigma_{j}-\sigma_{i})},&i\neq
j\\\ 0,&i=j\end{array}\right.\mbox{ for }i,j=1,\ldots,p$

4: $\dot{U}=\left(\dot{Y}V+U(\Sigma\Gamma-\dot{\Sigma})\right)\Sigma^{-1}.$

5:$\dot{U},\dot{\Sigma}=\operatorname{diag}(\dot{\sigma}_{1},\ldots,\dot{\sigma}_{m}),\dot{V}$

#### Differentiating the QR-Decomposition

Let $t\mapsto Y(t)\in\mathbb{R}^{n\times r}$ be a differentiable matrix
function with Taylor expansion
$Y(t_{0}+h)=Y(t_{0})+h\dot{Y}(t_{0})+\mathcal{O}(h^{2})$. Following [54,
Proposition 2.2], the QR-decomposition is characterized via the following set
of matrix equations.

$Y(t)=Q(t)R(t),\quad Q^{T}(t)Q(t)=I_{r},\quad 0=P_{L}\odot R(t).$

In the latter, $P_{L}=\begin{pmatrix}0&\cdots&\cdots&0\\\ 1&\ddots&&\vdots\\\
\vdots&\ddots&\ddots&\vdots\\\ 1&\cdots&1&0\end{pmatrix}$ and ‘$\odot$’ is the
element-wise matrix product so that $P_{L}\odot R$ selects the strictly lower
triangle of the square matrix $R$. For brevity, we write $Y=Y(t_{0}),\
\dot{Y}=\frac{\mathrm{d}}{\mathrm{d}t}\big{|}_{t=t_{0}}Y(t)$, likewise for
$Q(t)$, $R(t)$. By the product rule

$\dot{Y}=\dot{Q}R+Q\dot{R},\quad 0=\dot{Q}^{T}Q+Q^{T}\dot{Q},\quad
0=P_{L}\odot\dot{R}.$

According to [54, Proposition 2.2], the derivatives $\dot{Q},\dot{R}$ can be
obtained from Alg. 3. The trick is to compute $X=Q^{T}\dot{Q}$ first and then
use this to compute $\dot{Q}=QQ^{T}\dot{Q}+(I_{n}-QQ^{T})\dot{Q}$ by
exploiting that $Q^{T}\dot{Q}$ is skew-symmetric and that $\dot{R}R^{-1}$ is
upper triangular.

Algorithm 3 Differentiating the QR-decomposition, [54, Proposition 2.2]

1:matrices $T,\dot{T}\in\mathbb{R}^{n\times r}$, (compact) QR-decomposition
$T=QR$.

2: $L:=P_{L}\odot(Q^{T}\dot{T}R^{-1})$

3: $X=L-L^{T}$ $\triangleright$ Now, $X=Q^{T}\dot{Q}$

4: $\dot{R}=Q^{T}\dot{T}-XR$

5: $\dot{Q}=(I_{n}-QQ^{T})\dot{T}R^{-1}+QX$

6:$\dot{Q},\dot{R}$

#### Matrix Exponential and the Principal Matrix Logarithm

The matrix exponential and the principal matrix logarithm are defined by

$\exp_{m}(X):=\sum_{j=0}^{\infty}{\frac{X^{j}}{j!}},\quad\log_{m}(I+X):=\sum_{j=1}^{\infty}{(-1)^{j+1}\frac{X^{j}}{j}}.$
(B.2)

The latter is well-defined for matrices that have no eigenvalues on
$\mathbb{R}^{-}$.

## Acknowledgments

This work was initiated when the first author was at UCLouvain for a research
visit, hosted by the third author. The third author was supported by the Fonds
de la Recherche Scientifique – FNRS and the Fonds Wetenschappelijk Onderzoek –
Vlaanderen under EOS Project no 30468160.

## References

  * [1] P.-A. Absil, A. Edelman, and P. Koev.  On the largest principal angle between random subspaces.  Linear Algebra and its Applications, 414(1):288 – 294, 2006.  doi:doi.org/10.1016/j.laa.2005.10.004.
  * [2] P.-A. Absil, R. Mahony, and R. Sepulchre.  Riemannian geometry of Grassmann manifolds with a view on algorithmic computation.  Acta Applicandae Mathematica, 80(2):199–220, 2004.  doi:10.1023/B:ACAP.0000013855.14971.91.
  * [3] P.-A. Absil, R. Mahony, and R. Sepulchre.  Optimization Algorithms on Matrix Manifolds.  Princeton University Press, Princeton, New Jersey, 2008.  URL: http://press.princeton.edu/titles/8586.html.
  * [4] M. M. Alexandrino and R. G. Bettiol.  Lie Groups and Geometric Aspects of Isometric Actions.  Springer International Publishing, Cham, 2015.  doi:10.1007/978-3-319-16613-1_2.
  * [5] D. Amsallem and C. Farhat.  Interpolation method for adapting reduced-order models and application to aeroelasticity.  AIAA Journal, 46(7):1803–1813, 2008.  doi:10.2514/1.35374.
  * [6] L. Balzano and S. J. Wright.  Local convergence of an algorithm for subspace identification from partial data.  Foundations of Computational Mathematics, 15(5):1279–1314, 2015\.  doi:10.1007/s10208-014-9227-7.
  * [7] E. Batzies, K. Hüper, L. Machado, and F. Silva Leite.  Geometric mean and geodesic regression on Grassmannians.  Linear Algebra Appl., 466:83–101, 2015.  doi:10.1016/j.laa.2014.10.003.
  * [8] E. Begelfor and M. Werman.  Affine invariance revisited.  IEEE Conference on Computer Vision and Pattern Recognition, 2:2087–2094, 2006.  doi:10.1109/CVPR.2006.50.
  * [9] S. Berceanu.  On the geometry of complex Grassmann manifold, its noncompact dual and coherent states.  Bull. Belg. Math. Soc. Simon Stevin, 4(2):205–243, 1997.  doi:10.36045/bbms/1105731655.
  * [10] R. Bergmann and P.-Y. Gousenbourger.  A Variational Model for Data Fitting on Manifolds by Minimizing the Acceleration of a Bézier Curve.  Frontiers in Applied Mathematics and Statistics, 4:59, 2018.  doi:10.3389/fams.2018.00059.
  * [11] A. A. Borisenko and Yu. A. Nikolaevskiĭ.  Grassmann manifolds and Grassmann image of submanifolds.  Uspekhi Mat. Nauk, 46(2(278)):41–83, 240, 1991.  doi:10.1070/RM1991v046n02ABEH002742.
  * [12] N. Boumal.  Optimization and estimation on manifolds.  PhD thesis, Université catholique de Louvain, 2014.
  * [13] N. Boumal and P.-A. Absil.  Low-rank matrix completion via preconditioned optimization on the Grassmann manifold.  Linear Algebra and its Applications, 475:200–239, 2015.  doi:10.1016/j.laa.2015.02.027.
  * [14] E. Cancès, G. Kemlin, and A. Levitt.  Convergence analysis of direct minimization and self-consistent iterations, 2020.  arXiv:2004.09088.
  * [15] S. Chandrasekaran, B. S. Manjunath, Y. F. Wang, J. Winkeler, and H. Zhang.  An eigenspace update algorithm for image analysis.  Graphical Models and Image Processing, 59(5), 1997.  doi:10.1006/gmip.1997.0425.
  * [16] L. Dieci and T. Eirola.  On smooth decompositions of matrices.  SIAM Journal on Matrix Analysis and Applications, 20(3):800–819, 1999.  doi:10.1137/S0895479897330182.
  * [17] M. P. do Carmo.  Riemannian Geometry.  Mathematics: Theory & Applications. Birkhäuser Boston, 1992.
  * [18] A. Edelman, T. A. Arias, and S. T. Smith.  The geometry of algorithms with orthogonality constraints.  SIAM Journal on Matrix Analysis and Applications, 20(2):303–353, April 1998.  doi:10.1137/S0895479895290954.
  * [19] P T. Fletcher.  Geodesic regression and the theory of least squares on Riemannian manifolds.  International journal of computer vision, 105(2):171–185, 2013\.  doi:10.1007/s11263-012-0591-y.
  * [20] J. H. Gallier.  Geometric Methods and Applications: For Computer Science and Engineering.  Texts in Applied Mathematics. Springer, New York, 2011.  doi:10.1007/978-1-4419-9961-0.
  * [21] K. A. Gallivan, A. Srivastava, X. Liu, and P. Van Dooren.  Efficient algorithms for inferences on Grassmann manifolds.  In IEEE Workshop on Statistical Signal Processing, pages 315–318, 2003.  doi:10.1109/SSP.2003.1289408.
  * [22] R. Godement and U. Ray.  Introduction to the Theory of Lie Groups.  Universitext. Springer International Publishing, 2017.  doi:10.1007/978-3-319-54375-8.
  * [23] E. Hairer, C. Lubich, and G. Wanner.  Geometric numerical integration, volume 31 of Springer Series in Computational Mathematics.  Springer-Verlag, Berlin, second edition, 2006.  doi:10.1007/3-540-30666-8.
  * [24] B. C. Hall.  Lie Groups, Lie Algebras, and Representations: An Elementary Introduction.  Springer Graduate texts in Mathematics. Springer–Verlag, New York – Berlin – Heidelberg, 2nd edition, 2015.  doi:10.1007/978-3-319-13467-3.
  * [25] A. Hay, J. T. Borggaard, and D. Pelletier.  Local improvements to reduced-order models using sensitivity analysis of the proper orthogonal decomposition.  Journal of Fluid Mechanics, 629:41–72, 2009.  doi:10.1017/S0022112009006363.
  * [26] S. Helgason.  Differential Geometry, Lie Groups, and Symmetric Spaces.  Crm Proceedings & Lecture Notes. American Mathematical Society, 2001\.
  * [27] U. Helmke, K. Hüper, and J. Trumpf.  Newton’s method on Graßmann manifolds, 2007.  arXiv:0709.2205.
  * [28] U. Helmke and J. B. Moore.  Optimization and Dynamical Systems.  Communications & Control Engineering. Springer–Verlag, London, 1994\.  doi:10.1007/978-1-4471-3467-1.
  * [29] N. J. Higham.  Functions of Matrices: Theory and Computation.  Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008.  doi:10.1137/1.9780898717778.
  * [30] R. A. Horn and C. R. Johnson.  Topics in matrix analysis.  Cambridge University Press, Cambridge, 1991.  doi:10.1017/CBO9780511840371.
  * [31] S. Kobayashi and K. Nomizu.  Foundations of differential geometry. Vol. I & II.  Wiley Classics Library. John Wiley & Sons, Inc., New York, 1996.  Reprint of the 1963 original.
  * [32] O. Koch and C. Lubich.  Dynamical low‐rank approximation.  SIAM J. Matrix Analysis Applications, 29:434–454, 2007.  doi:10.1137/050639703.
  * [33] E. S. Kozlov.  Geometry of real Grassmann manifolds. Part I - VI.  Journal of Mathematical Sciences, 2000 – 2001.
  * [34] Z. Lai, L.-H. Lim, and K. Ye.  Simpler Grassmannian optimization, 2020.  arXiv:2009.13502.
  * [35] J. M. Lee.  Introduction to Smooth Manifolds.  Graduate Texts in Mathematics. Springer New York, 2012.  doi:10.1007/978-1-4419-9982-5.
  * [36] J. M. Lee.  Introduction to Riemannian Manifolds, volume 176 of Graduate Texts in Mathematics.  Springer, Cham, 2018.  doi:10.1007/978-3-319-91755-9.
  * [37] K. Leichtweiss.  Zur Riemannschen Geometrie in Grassmannschen Mannigfaltigkeiten.  Math. Z., 76:334–366, 1961.  doi:10.1007/BF01210982.
  * [38] C. Li, X. Wang, J. Wang, and J.-C. Yao.  Convergence Analysis of Gradient Algorithms on Riemannian Manifolds Without Curvature Constraints and Application to Riemannian Mass, 2019.  arXiv:1910.02280.
  * [39] A. Machado and I. Salavessa.  Grassmannian manifolds as subsets of Euclidean spaces.  In Differential geometry (Santiago de Compostela, 1984), volume 131 of Res. Notes in Math., pages 85–102. Pitman, Boston, MA, 1985\.
  * [40] Y. Man Lui.  Advances in matrix manifolds for computer vision.  Image and Vision Computing, 30(6–7):380–388, 2012.  doi:10.1016/j.imavis.2011.08.002.
  * [41] H. Q. Minh and V. Murino.  Algorithmic Advances in Riemannian Geometry and Applications: For Machine Learning, Computer Vision, Statistics, and Optimization.  Advances in Computer Vision and Pattern Recognition. Springer International Publishing, Cham, 2016.  doi:10.1007/978-3-319-45026-1.
  * [42] M. Moonen, P. Van Dooren, and J. Vandewalle.  A singular value decomposition updating algorithm for subspace tracking.  SIAM Journal on Matrix Analysis and Applications, 13(4):1015–1038, 1992.  doi:10.1137/0613061.
  * [43] T. S. Nguyen.  A real time procedure for affinely dependent parametric model order reduction using interpolation on Grassmann manifolds.  International Journal for Numerical Methods in Engineering, 93(8):818–833, 2013.  doi:10.1002/nme.4408.
  * [44] B. O’Neill.  Semi-Riemannian geometry - With applications to relativity, volume 103 of Pure and Applied Mathematics.  Academic Press, New York, 1983.
  * [45] L. Qiu, Y. Zhang, and C.-K. Li.  Unitarily Invariant Metrics on the Grassmann Space.  SIAM Journal on Matrix Analysis and Applications, 27(2):507–25, 2005.  doi:10.1137/040607605.
  * [46] I. U. Rahman, I. Drori, V. C. Stodden, D. L. Donoho, and P. Schröder.  Multiscale representations for manifold-valued data.  SIAM Journal on Multiscale Modeling and Simulation, 4(4):1201–1232, 2005.  doi:10.1137/050622729.
  * [47] Q. Rentmeesters.  Algorithms for data fitting on some common homogeneous spaces.  PhD thesis, Université Catholique de Louvain, Louvain, Belgium, 2013\.  URL: http://hdl.handle.net/2078.1/132587.
  * [48] Y. Saad.  Numerical Methods for Large Eigenvalue Problems.  Algortihms and Architectures for Advanced Scientific Computing. Manchester University Press, Manchester, UK, 1992.
  * [49] T. Sakai.  On cut loci of compact symmetric spaces.  Hokkaido Math. J., 6(1):136–161, 1977.  doi:10.14492/hokmj/1381758555.
  * [50] T. Sakai.  Riemannian Geometry.  Fields Institute Communications. American Mathematical Soc., 1996.  doi:10.1090/mmono/149.
  * [51] A. Srivastava and X. Liu.  Tools for application-driven linear dimension reduction.  Neurocomputing, 67:136 – 160, 2005.  Geometrical Methods in Neural Networks and Learning.  doi:10.1016/j.neucom.2004.11.036.
  * [52] A. Srivastava and P. K. Turaga.  Riemannian computing in computer vision.  Springer International Publishing, 2015.  doi:10.1007/978-3-319-22957-7.
  * [53] K. Usevich and I. Markovsky.  Optimization on a Grassmann manifold with application to system identification.  Automatica, 50(6):1656 – 1662, 2014.  doi:10.1016/j.automatica.2014.04.010.
  * [54] S. F. Walter, L. Lehmann, and R. Lamour.  On evaluating higher-order derivatives of the QR decomposition of tall matrices with full column rank in forward and reverse mode algorithmic differentiation.  Optimization Methods and Software, 27(2):391–403, 2012.  doi:10.1080/10556788.2011.610454.
  * [55] Y.-C. Wong.  Differential geometry of Grassmann manifolds.  Proceedings of the National Academy of Sciences of the United States of America, 57:589–594, 1967.  doi:10.1073/pnas.57.3.589.
  * [56] Y.-C. Wong.  Conjugate loci in Grassmann manifolds.  Bull. Amer. Math. Soc., 74:240–245, 1968.  doi:10.1090/S0002-9904-1968-11903-2.
  * [57] Y.-C. Wong.  Sectional curvatures of Grassmann manifolds.  Proceedings of the National Academy of Sciences of the United States of America, 60(1):75–79, 1968.  doi:10.1073/pnas.60.1.75.
  * [58] G. L. Wu and W. H. Chen.  A matrix inequality and its geometric applications.  Acta Math. Sinica, 31(3):348–355, 1988.
  * [59] K. Ye and L.-H. Lim.  Schubert varieties and distances between subspaces of different dimensions.  SIAM J. Matrix Anal. Appl., 37(3):1176–1197, 2016.  doi:10.1137/15M1054201.
  * [60] D. Zhang and L. Balzano.  Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation, pages 1460–1468.  Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, AISTATS, Cadiz, Spain, May 2016.
  * [61] R. Zimmermann.  A locally parametrized reduced order model for the linear frequency domain approach to time-accurate computational fluid dynamics.  SIAM Journal on Scientific Computing, 36(3):B508–B537, 2014.  doi:10.1137/130942462.
  * [62] R. Zimmermann.  Hermite interpolation and data processing errors on Riemannian matrix manifolds.  SIAM Journal on Scientific Computing, 2020.  (accepted).
  * [63] R. Zimmermann, B. Peherstorfer, and K. Willcox.  Geometric subspace updates with applications to online adaptive nonlinear model reduction.  SIAM Journal on Matrix Analysis and Application, 39(1):234–261, 2018.  doi:10.1137/17M1123286.
  * [64] Ralf Zimmermann.  Manifold interpolation and model reduction, 2019.  arXiv:1902.06502.


# Exploring the Compositional Generalization in Context Dependent Text-to-SQL
Parsing

Aiwei Liu∗, Wei Liu∗, Xuming Hu, Shu’ang Li, Fukun Ma,
Yawen Yang, Lijie Wen†
Tsinghua University
{liuaw20,liu-w21,hxm19,lisa18, mafk19<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

In the context-dependent Text-to-SQL task, the generated SQL statements are
refined iteratively based on the user input utterance from each interaction.
The input text from each interaction can be viewed as component modifications
to the previous SQL statements, which could be further extracted as the
modification patterns. Since these modification patterns could also be
combined with other SQL statements, the models are supposed to have the
compositional generalization to these novel combinations. This work is the
first exploration of compositional generalization in context-dependent Text-
to-SQL scenarios. To facilitate related studies, we constructed two
challenging benchmarks named CoSQL-CG and SParC-CG by recombining the
modification patterns and existing SQL statements. The following experiments
show that all current models struggle on our proposed benchmarks. Furthermore,
we found that better aligning the previous SQL statements with the input
utterance could give models better compositional generalization ability. Based
on these observations, we propose a method named p-align to improve the
compositional generalization of Text-to-SQL models. Further experiments
validate the effectiveness of our method. Source code and data are available
111https://github.com/THU-BPM/CD-Text2SQL-CG
00 ∗Equally Contributed.
00 † Corresponding author.

##  1 Introduction

Recently, the poor generalization of semantic parsing models to out-of-
distribution samples is under increasing attention Keysers et al. (2020);
hupkes2020compositionality. These examples are usually obtained by recombining
existing structures. For example, in the SCAN dataset Lake and Baroni (2018a),
models may fail to parse "jump twice and walk" even though "jump twice" and
"walk" could be parsed successfully. The ability to generalize to novel
combinations is also known as compositional generalization. Text-to-SQL Yu et
al. (2018) allows non-expert users to access the information from the database
by converting the user input text into SQL statements executed in the
database. As a typical semantic parsing task, the study of its compositional
generalization is of great importance.

Existing works explore the compositional generalization of Text-to-SQL only in
the scenario that precisely maps stand-alone utterances to SQL queries. Shaw
et al. (2021) define the atom and compound for SQL statements and propose the
TMCD split to repartition the dataset. Gan et al. (2022) annotate the
alignment of sub-sentence and sub-SQL in the spider dataset Yu et al. (2018)
and then recombine these sub-SQLs and sub-sentences. In these settings, the
SQL statements and user questions in the constructed test split tend to be
much more complex. However, it is difficult for users to express complex
queries in a stand-alone sentence. In real scenarios, users often start with a
simple query and continuously combine additional query conditions with
subsequent questions.

Figure 1:  During the inference phase, the base queries and their
modifications could be re-combined. Models with compositional generalization
ability should successfully parse these novel combinations.

In this work, we focus on the study of compositional generalization in
context-dependent Text-to-SQL tasks, which is more natural and applicable. In
the context-dependent Text-to-SQL task Yu et al. (2019b), the generated SQL
statements are refined based on the user input text during each interaction.
The input text from each interaction can be viewed as component modifications
to the previous SQL statement, which could be further extracted as the
modification patterns. Since these modification patterns could also be
combined with other SQL statements, the models are supposed to have the
compositional generalization to these novel combinations. For example, in
Figure 1, the modifications and the queries of the first turn in the training
phrase could be re-combined in the inference phrase. Applicable models are
supposed to successfully parse these novel combinations.

To better investigate compositional generalization in the context-dependent
Text-to-SQL, we first construct compositional generalization benchmarks based
on the existing datasets. First, we extract the modification patterns from the
training dataset and then recombine them with the existing SQL statements in
the development set. Note that in the compositional generalization setting,
only the recombination results not existing in the training set are kept. To
generate the corresponding utterances, we use a semi-automatic approach. The
utterances are initially generated by a pre-trained model fine-tuned on the
training data, and then reviewed and verified by human experts. As a result,
we create two benchmarks, CoSQL-CG and Sparc-CG, specifically for the datasets
CoSQLYu et al. (2019a) and SParCYu et al. (2019b). Our experiments reveal that
current state-of-the-art models perform poorly on these benchmarks,
emphasizing the significance of enhancing compositional generalization
capabilities.

We further explore how to improve the compositional generalization in context-
dependent Text-to-SQL tasks. Inspired by the previous works to improve
compositional generalization by fine-grained alignment of inputs and outputs
Zheng and Lapata (2022); Akyürek and Andreas (2021), we propose a method to
better align the current text with the previous SQL statements. We follow the
common practice of most competitive Text-to-SQL models which take the
concatenation of all utterances as input. Specifically, our proposed p-align
method extracts the embedding of the text from each interaction after the
encoding process and then decodes them into the corresponding SQL statements
separately. Further experiment results show that our p-align method could
effectively improve the compositional generalization of current models, which
also demonstrates that better alignment of text and SQL statements and the
introduction of previous SQL statements are of great importance.

To summarize, the main contributions of our paper are as follows:

  * •

To the best of our knowledge, we are the first to explore compositional
generalization in context-dependent Text-to-SQL.

  * •

We construct two benchmarks named CoSQL-CG and Sparc-CG to better facilitate
the relevant research.

  * •

We propose a simple and effective method named p-align to improve the
compositional generalization ability of models.

##  2 Related Work

###  2.1 Context dependent Text-to-SQL

Most current research on Text-to-SQL is conducted under the context-
independent setting, with many recent methods achieving excellent results on
the Spider dataset Yu et al. (2018), including graph-based methods such as
LGESQLCao et al. (2021a), RAT-SQL Wang et al. (2020) and ISESL-SQL Liu et al.
(2022a), as well as sequence-to-sequence-based methods like PICARD Scholak et
al. (2021). Recently, with the presentation of two datasets CoSQLYu et al.
(2019a) and SParCYu et al. (2019b), the Text-to-SQL parsing under the context-
dependent setting has attracted much attention, which is more realistic and
applicable. Subsequently, various methods have been proposed. Among them,
SCoReYu et al. (2021) and STaRCai et al. (2022) aim to train better pre-
trained models to improve the parsing ability of models. Also, many sequence-
to-sequence methods based on T5 pre-trained model like PICARD Scholak et al.
(2021) and RASAT Qi et al. (2022) have achieved great success. Meanwhile, more
methods pay more attention to contextual information or conversation history
during encoding, including IGSQLCai and Wan (2020), HIE-SQLZheng et al.
(2022), and IST-SQLWang et al. (2021). Meanwhile, other rewriting-based
methods like DELTAChen et al. (2021) and CQR-SQLXiao et al. (2022) reformulate
the current and the historical texts into an individual sentence. Different
from the previous works, we mainly focus on exploring compositional
generalization under context-dependent text-to-SQL settings.

###  2.2 Compositional Generalization

Compositional Generalization is an important metric for evaluating the
robustness of the model Liu et al. (2022b) in the field of natural language
processing. For semantic parsing tasks, the ability to generalize to
structures generated by systematically combining known atomic components is of
vital importance. Lake and Baroni (2018b) propose the SCAN dataset, which maps
word sequences into navigation command sequences (e.g., jump twice → JUMP
JUMP). Their training/evaluation split are constructed in a compositional
generalization way. Keysers et al. (2020), introduce CFQ dataset and propose
distribution-based compositionality assessment to measure compositional
generalization. Hupkes et al. (2020) summerize five different compositionally
generalization splits and combine them to generate PCFG SET. Many works focus
on improving the compositional generalization of models. This is usually
achieved by introducing more detailed lexicon or lexicon-style alignments
Zheng and Lapata (2022); Akyürek and Andreas (2021) or adopting a grammar-
based decoder Herzig and Berant (2021); Qiu et al. (2022b); Guo et al. (2020).
Another line of work attempts to synthesize examples utilizing grammar and
generative models for data augmentation Qiu et al. (2022a); Andreas (2020);
Jia and Liang (2016).

Recently, the compositional generalization of Text-to-SQL parsing has gained
more and more interest. Shaw et al. (2021) define the atom and compound for
SQL statements and propose the TMCD split to repartition the dataset. Gan et
al. (2022) annotate the alignment of sub-sentence and sub-SQL in the spider
dataset Yu et al. (2018) and then recombine these sub-SQLs and sub-sentences.
The above works only focus on the Text-to-SQL parsing in the context-
independent setting, which precisely maps stand-alone utterances to SQL
queries. However, it is difficult for users to express complex queries in a
stand-alone sentence. In this work, we first explore the compositional
generalization for context-dependent Text-to-SQL Parsing.

##  3 Compositional Generalization in Context-dependent Text-to-SQL

To facilitate the understanding of the following sections, we provide a more
detailed explanation of compositional generalization in context-dependent
Text-to-SQL parsing in this section.

The template split is a typical compositional generalization setting, where
the structure templates in the training and test set are completely separated.
Our compositional generalization scenario can be viewed as an extension of the
template split, where the combination of basic SQL templates and modification
templates in the training and test set are separated. Note that basic SQL and
modification templates in the test set all appear in the training set
individually. For instance, in figure 1, in the inference phrase, although all
the templates are seen during training, their combinations are novel.

From another point of view, our compositional generalization scenario could
also be viewed as a special case of TMCD split Shaw et al. (2021), where the
SQL templates and modification templates could be seen as atoms and their
combination results are the compounds. Note the utterance to the SQL templates
(first atom) are provided during training, which could be further utilized to
improve the compositional generalization (Section 5).

##  4 Benchmark construction

Since there are few data satisfying the compositional generalization setting
in the origin SParC and CoSQL development set. We first construct new
benchmarks to facilitate the related research.

As illustrated in Figure 2, the benchmark construction process can be divided
into four steps. The first step is to filter out context-independent examples;
next, modification patterns are extracted from the remaining examples; after
that, these modification patterns are combined with other SQL statements, and
finally, corresponding utterances are generated.

Figure 2: The benchmark construction process can be divided into four steps.
The first step is to filter the context-independent data; then the next step
is to generate modification patterns from the remained examples; after that,
the modification patterns are recombined with other queries and the last step
is to generate the corresponding utterances.

###  4.1 Filter out context-independent examples

It is observed that a significant number of examples in the SParC or CoSQL
datasets are context-independent, meaning that no context information is
needed to generate the current queries. In this work, we propose a schema-
linking-based method to filter out these context-independent examples.

Schema linking is a common technique in Text-to-SQL which links the exact or
partial occurrences of the column/table names in the question such as the
ARILINES and Abbreviation in Figure 2(a). Our main motivation is that if
current data is context-dependent, there are some column/table names not
linked to the current question but linked to history questions (context), such
as the first example in Figure 2(a). Specifically, the schemas in the target
query are represented as $\mathrm{S}$. We use the n-gram matching method to
find occurrences $\mathrm{S}$ in the current question, where the matched
schemas could be represented as $\mathrm{S_{c}}$. Similarly, the matched
schemas in the history questions are represented as $\mathrm{S_{p}}$. The
current example is context-dependent only if
$\mathrm{S_{p}}-\mathrm{S_{c}}\neq\emptyset$. Finally, we keep 4270 and 2347
context-dependent examples in SParC and CoSQL training set respectively.

###  4.2 Generate Modification Pattern

After filtering out context-independent data, the next step is to generate
modification patterns from the remaining context-dependent examples.

As shown in Figure 2(b), we first parse current and previous SQL statements
into abstract syntax trees and then compare the tree structures to get the
modified components. Specifically, a top-down traversal algorithm is adopted
to find the different nodes. The nodes along with their children constitute
the modified component. Then the generated modification component is
anonymized to generate the modification template. Finally, we generate 409 and
191 modification templates for SparC and CoSQL respectively.

###  4.3 Re-combine SQL statements

With the generated modification patterns, the next step is to re-combine these
patterns with other SQL statements to generate new SQL statements.

First, modification patterns are filled with new table/column names sampled
from target database schemas to generate new modifications. Then the
modifications are directly combined with the other SQL statements. Note that
in the previous modification pattern generation process, the relationship of
the schema is kept (e.g. primary key and foreign key relationships) and the
table/column name sampling results must conform to the above relationship
constraints. As mentioned in Section 3, the combination process requires that
the base SQL templates and modification templates are all shown in the
training set but their combinations are novel. Finally, we generate 5958 and
2594 combination results in SparC and CoSQL respectively.

###  4.4 Utterance generation

The final step of our benchmark construction is to generate the context-
dependent utterance for the generated SQL statements. Since pre-trained
language models have shown great ability in text generation, we first utilize
a fine-tuned T5 model Raffel et al. (2020) to generate the context-dependent
utterance. More specifically, the input to the T5 model is the concatenation
of the modification, previous SQL statement, and previous utterance.

For the utterance generated by the T5 model may be noisy, we further invite
human experts to filter and revise the generated data. The first task of human
experts is to remove SQL statements that don’t fit realistic scenarios. For
example, the statement SELECT Count(loser_entry) FROM matches ORDER BY
matches.winner_age is invalid because the function Count() and the clause
ORDER BY usually do not appear together. The second task of the human experts
is to revise the utterances generated by the T5 model as shown in Figure 2(d).
To ensure annotation consistency, we introduce two experts to double-check the
annotated results. Finally, after the filtering and revising process, we get
372 and 267 questions for SParC and CoSQL datasets respectively, which further
construct our SParC-CG and CoSQL-CG benchmarks. More detailed statistics of
the benchmarks will be described in the experiment section.

##  5 Methods

After constructing the SParC-CG and CoSQL-CG, we further explore how to
improve the compositional generalization in context-dependent Text-to-SQL
parsing. According to the previous works Zheng and Lapata (2022); Akyürek and
Andreas (2021), the key to improving the compositional generalization is to
construct better component alignment between inputs and outputs. In the
context-dependent Text-to-SQL settings, the utterance-query pair of previous
interactions could be utilized to align input utterances and output queries.
Based on this motivation, we propose p-align to improve the compositional
generalization of existing Text-to-SQL models. Note that our method follows
the common practice of most competitive Text-to-SQL models which take the
concatenation of all utterances as input.

Figure 3: The whole process of our p-align method. The input to the encoding
process is the concatenation of the utterance from all interactions. In the
decoding process, the utterance embeddings of each interaction are extracted
to decode the corresponding SQL.

Specifically, given the input utterances $X=[X_{1},X_{2},...,X_{n}]$ at the
n-th interaction, where $X_{n}=[x_{1},....x_{j}]$ is an utterance with j
words, the encoder aims to generate embeddings for each word such that
$\mathbf{X}=\mathbf{H}(X)$. In the origin decoding process, the result query y
could be represented as an action sequence $[a_{1},...a_{t}]$ and the whole
decoding process could be represented as the product of probabilities for each
generation step as follows:

$\prod_{t=1}^{T}p\left(a_{t}\mid\left\\{a_{1},\ldots,a_{t-1}\right\\},\textbf{X}\right).$
(1)

In our p-align method, the utterance embeddings of each interaction are
extracted to decode the corresponding SQL statements. As shown in Figure 3,
the decoder process of our p-align could be represented as:

$\sum_{i=1}^{n}\prod_{t=1}^{T_{i}}p\left(a_{t}^{i}\mid\left\\{a_{1}^{i},\ldots,a_{t-1}^{i}\right\\},\textbf{X}_{\leq
i}\right).$ (2)

In this way, our p-align method aligns corresponding parts of the input
utterance to the previous queries and thus improves the compositional
generalization ability of models.

##  6 Experiment

| # Questions | # Non-CG Questions | # CG Questions
---|---|---|---
SParC | 1625 | 491 | 31
SParC-CG | 921 | 491 | 372
CoSQL | 1300 | 207 | 14
CoSQL-CG | 471 | 207 | 167

Table 1: The detailed statistics of SParC-CG and CoSQL-CG benchmark. Figure 4:
Distributions of different modification patterns in SParC-CG and CoSQL-CG
benchmark.

In this section, we first perform more detailed statistics on our constructed
SParC-CG and CoSQL-CG. Then we further analyze our benchmarks with current
competitive Text-to-SQL models. Finally, several experiments are conducted to
verify the effectiveness of our p-align method.

###  6.1 Benchmark statistics

Methods / Datasets | SParC | CoSQL
---|---|---
Dev | Non-CG | CG | Dev | Non-CG | CG
SPiC (Concat) + BERT-Large Liu et al. (2020) | 55.3 | 63.4 | 18.9(36.4$\downarrow$) | 45.2 | 52.3 | 13.3(31.9$\downarrow$)
SPiC (Turn) + BERT-Large Liu et al. (2020) | 54.6 | 62.1 | 18.2(36.4$\downarrow$) | 44.8 | 51.3 | 12.2(32.6$\downarrow$)
SPiC (Gate) + BERT-Large Liu et al. (2020) | 54.3 | 62.4 | 17.3(37.0$\downarrow$) | 44.2 | 51.8 | 12.4(31.8$\downarrow$)
RAT-SQL + SCoRe Yu et al. (2021) | 60.4 | 69.6 | 22.4(38.0$\downarrow$) | 52.1 | 55.6 | 20.4(31.7$\downarrow$)
LGESQL + ELECTRA-Large Cao et al. (2021b) | 65.0 | 73.4 | 25.3(39.7$\downarrow$) | 54.4 | 62.4 | 21.0(33.4$\downarrow$)
LGESQL + STaR Cai et al. (2022) | 66.9 | 75.4 | 25.8(41.1$\downarrow$) | 59.7 | 68.4 | 26.3(33.4$\downarrow$)
PICARD + T5-3B Scholak et al. (2021) | - | - | - | 56.9 | 58.1 | 21.5(35.4$\downarrow$)
RASAT + T5-3B Qi et al. (2022) | 66.7 | 75.8 | 22.0(44.7$\downarrow$) | 58.8 | 67.9 | 20.4(38.4$\downarrow$)

Table 2: Question match accuracy of current competitive models on three
different benchmarks: Dev, Non-CG, and CG. For all the models, we adopt the
given parameters.

The detailed statistics of SParC-CG and CoSQL-CG are shown in Table 1. We
mainly count three metrics here: # Question, # Non-CG Questions, and # CG
Questions, where # Question is the total number of questions, # CG Questions
is the number of questions that meet the definition of compositional
generalization in Section 3 and # Non-CG Questions is the number of in-domain
questions (the templates and combination of templates are both seen in
training). The Non-CG questions in SParC-CG and CoSQL-CG are obtained directly
from the SParC and CoSQL datasets. The number of CG questions in our
benchmarks is far more than in that SParC and CoSQL. Note that a large portion
of the data in the SParC and CoSQL datasets is context-independent or has no
context, which makes the sum of # Non-CG Questions and # CG Questions
relatively small.

We present the components distributions of modification patterns of SParC-CG
and CoSQL-CG in Figure 4. The most common component in modification patterns
is where. Orderby and groupby also take a large proportion. There are also
many modification patterns that include multiple components, such as where-
groupby and where-orderby. Finally, the distributions of modification patterns
in SParC-CG and CoSQL-CG are similar, which illustrates our benchmark
construction’s consistency. Note that the select components are not counted,
as they are included in almost all modifications.

###  6.2 Experiment Setup

Models. We adopt many current competitive Text-to-SQL models to explore the
impact of compositional generalization. SPiC Liu et al. (2020) is a simple
model which explores different methods to incorporate context questions, where
SPiC (Concat) concatenates context questions with current questions, SPiC
(Turn) employs a turn-level encoder to capture the inter-dependencies among
questions in different turns and SPiC (Gate) uses a gate mechanism to compute
the importance of each question. SCoRe and STaR Cai et al. (2022) are two
specialized pre-trained models for RATSQL and LGESQLCao et al. (2021b)
respectively. PICARD Scholak et al. (2021) and RASAT Qi et al. (2022) are two
seq2seq based models based on pre-trained T5 model Raffel et al. (2020).

Evaluation Metric. We mainly use the question match (QM) Yu et al. (2019b) as
our evaluation metric, which is the exact set matching score Yu et al. (2018)
over all questions. The exact set matching score decomposes predicted queries
into SQL components such as SELECT and WHERE and then computes scores for each
component. For each model, we report the QM on the origin SParC/CoSQL
development set as well as the Non-CG and CG benchmarks. Note that the
interaction match Yu et al. (2019b) is not reported in our paper because we
are only interested in the scores of the model on questions satisfying the
compositional generalization condition.

###  6.3 Evaluation on SParC-CG/CoSQL-CG

We report the question match accuracy on SParC and CoSQL datasets under three
benchmarks: Dev, Non-CG, and CG in Table 2.

Based on the above results, we summarize the following observations. (1) The
accuracy of all models significantly decreases under the compositional
generalization setting. Specifically, the QM on SParC-CG and CoSQL-CG
decreases 39.3 and 33.6 on average compared to the origin development set,
which indicates current models lack the compositional generalization ability.
(2) The models perform better on the Non-CG benchmarks than the origin
development set (8.4 and 6.5 on average for SParC and CoSQL respectively),
which demonstrates that in-domain data are easily generalized. (3) Concat
could better incorporate context questions than Turn and Gate. Therefore, our
p-align is only designed for the Concat method. (4) The grammar tree-based
decoder (LGESQL) and the larger language model (T5-3B) could help improve the
compositional generalization ability.

###  6.4 Detailed Evaluation

Figure 5: The results on different benchmarks by varying the difficulty levels
of the data (a-b) and by varying the conversation turns(c-d). We use the STaR
model here as an example.

Evaluation ay Different Levels of Difficulty. The SQL queries could be divided
into four difficulty levels based on the complexity of SQL statements: easy,
medium, hard and extra hard. To better demonstrate the performance in the
compositional generalization setting, we conduct further evaluations on
different levels of difficulties. As shown in Figure 5a-b, the STaR model
performs worse on the CG benchmark than on the original development set at all
difficulties, which further indicates the model’s compositional generalization
ability requires further improvement. Meanwhile, there is an obvious
improvement in the Non-CG benchmark compared to the original development set.

Evaluation at Different Turns. We further illustrate the question match
accuracy on three benchmarks with the increase of conversation turns in Figure
5c-d. The accuracy decreases sharply on the CG benchmark and the origin
development set while staying stable on the non-CG benchmark. This suggests
that the compositional generalization ability of models decreases with the
increase of conversation turns.

SQL Components | DEV | Non-CG | CG
---|---|---|---
SELECT | 84.6 | 88.2 | 60.2
SELECT (no AGG) | 86.3 | 89.3 | 62.9
WHERE | 80.6 | 91.8 | 62.5
WHERE(no OP) | 85.1 | 95.3 | 69.2
GROUP BY (no HAVING) | 81.1 | 85.7 | 66.4
GROUP BY | 76.9 | 81.6 | 54.5
ORDER BY | 78.2 | 82.0 | 58.3
AND/OR | 99.0 | 99.3 | 91.2
KEYWORDS | 86.3 | 92.8 | 67.1

Table 3: Accuracy on the different SQL components. The reported results are
the average results over STaR and RASAT on three benchmarks of SParC.

Evaluation on different components. To better investigate the poor performance
of the current competitive models under the compositional generalization
setting, we further report the question match accuracy on different detailed
SQL components in Table 3. The reported results are the average results over
STaR and RASAT on three benchmarks of SParC. As demonstrated in the table,
nearly all components’ accuracy significantly decreases under the
compositional generalization setting, which illustrates the impact of
compositional generalization on the models is balanced.

###  6.5 Evaluation of p-align method

Methods | DEV | Non-CG | CG
---|---|---|---
SParC
SPiC (Concat) + BERT-Base | 47.6 | 53.5 | 8.9
w. p-align | 50.6 | 54.1 | 16.4(7.5$\uparrow$)
SPiC (Concat) + BERT-Large | 55.3 | 63.4 | 19.5
w. p-align | 56.1 | 63.8 | 20.6(1.1$\uparrow$)
LGESQL + ELECTRA-Large | 65.0 | 73.4 | 25.3
w. p-align | 64.8 | 73.0 | 26.2(0.9$\uparrow$)
CoSQL
SPiC (Concat) + BERT-Base | 39.2 | 35.0 | 5.2
w. p-align | 40.5 | 36.2 | 9.6(4.4$\uparrow$)
SPiC (Concat) + BERT-Large | 45.2 | 52.3 | 12.2
w. p-align | 45.5 | 52.7 | 14.4(2.2$\uparrow$)
LGESQL + ELECTRA-Large | 54.4 | 62.4 | 21.0
w. p-align | 53.8 | 62.3 | 21.2(0.2$\uparrow$)

Table 4: The results of different models w. & w/o p-align on three benchmarks
of SParC and CoSQL. Figure 6: Four examples from SParC-CG benchmark and the
corresponding wrong prediction results of STaR and RASAT. These examples are
categorized according to the different errors.

Table 4 shows the results of different models with & without p-align on three
benchmarks of SParC and CoSQL. We choose SPiC (Concat) + BERT-Base, SPiC
(Concat) + BERT-large and LGESQL+ELECTRA-Large as our base models because
other models are either customized pre-trained models (STaR and SCoRe) or with
a too large model(T5-3B). All the hyperparameters are the same as the original
model.

Overall, our p-align method significantly improves the performance of the
model on the CG benchmarks, with an average improvement of 3.2 and 2.3 on the
SParC-CG and CoSQL-CG benchmarks respectively. While the improvement on DEV
and Non-CG benchmarks is relatively small, at 0.77 and 0.35 on average
respectively, this suggests that our method is particularly effective in
compositional generalization settings. These results support our hypothesis
that improving alignment between utterances and queries can enhance the
model’s compositional generalization abilities, and should be considered as a
potential direction for future research.

Error component | STaR | RASAT | LGESQL
---|---|---|---
Context Info | 24 | 15 | 25
Modification Info | 149 | 136 | 139
Context & Modification Info | 112 | 128 | 127

Table 5: Statistical analysis of different error types on SParC-CG benchmark.

###  6.6 Error analysis

To evaluate the compositional generalization ability of current models, we
selected four incorrect prediction results from the SParC-CG benchmark. For
each example, we provided the context, the current question, the correct
query, and the prediction results from STaR and RASAT.

As illustrated in Figure 6, in the first two scenarios, the models struggle to
accurately interpret the changes brought about by current questions, despite
maintaining a grasp of the context information. Conversely, in the third case,
the models are able to interpret the modifications of the current question,
but fail to take into account the context information. The fourth case
represents the worst-case scenario, with the models unable to correctly parse
either the modifications or the context information. Note that the incorrect
results predicted by both models in the first three cases are similar,
indicating that the failure of the current models to perform well in a
compositional generalization setting is a widespread issue, not an isolated
incident.

The presented case study categorizes three scenarios where current models make
incorrect predictions, which include: failing to consider contextual
information, inability to interpret modifications, and failing to understand
both modifications and context. We further conduct statistical analysis on the
SParC-CG benchmark in Table 5 and found that the majority of errors occur when
models cannot interpret modifications. Additionally, when models neglect
context, they also tend to misinterpret modifications. Interestingly, the
proportion of errors for the different models evaluated in the study is quite
similar, indicating that the compositional generalization challenges faced by
these models are consistent across them.

##  7 Conclusion

In this study, we conduct the first exploration of compositional
generalization in context-dependent Text-to-SQL scenarios. To support further
research in this area, we construct two benchmarks named SParC-CG and CoSQL-CG
composed of out-of-distribution examples. Additionally, we introduce the
p-align method to enhance the compositional generalization capabilities of
existing models. Further experiments show that current models perform poorly
on our constructed benchmarks and demonstrate the effectiveness of our p-align
method. Also, with the recent advancements in generative language models, such
as GPT3.5 and GPT4 OpenAI (2023), explorations into these models Liu et al.
(2023) should also constitute a significant part of future work.

## Acknowledgement

The work was supported by the National Key Research and Development Program of
China (No. 2019YFB1704003), the National Nature Science Foundation of China
(No. 62021002), Tsinghua BNRist and Beijing Key Laboratory of Industrial
Bigdata System and Application.

##  8 Limitations

In this paper, the approach to improve the compositional generalization under
the context-dependent setting is insufficient. We only construct a better
component alignment between inputs and outputs for models taking the
concatenation of all utterances as input. However, it is important to note
that other methods, such as using a turn-level encoder or implementing a gate
mechanism, should also be considered. Additionally, other types of methods are
also ignored. Future research could explore data augmentation techniques Hu et
al. (2022) and enhanced training objectives, such as meta-learning Hu et al.
(2021) and contrastive learningLiu et al. (2022c); Li et al. (2023); Hu et al.
(2020), as potential avenues for improvement.

## References

  * Akyürek and Andreas (2021) Ekin Akyürek and Jacob Andreas. 2021.  Lexicon learning for few-shot neural sequence modeling.  _CoRR_ , abs/2106.03993.
  * Andreas (2020) Jacob Andreas. 2020.  Good-enough compositional data augmentation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7556–7566, Online. Association for Computational Linguistics.
  * Cai and Wan (2020) Yitao Cai and Xiaojun Wan. 2020.  IGSQL: Database schema interaction graph based neural model for context-dependent text-to-SQL generation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6903–6912, Online. Association for Computational Linguistics.
  * Cai et al. (2022) Zefeng Cai, Xiangyu Li, Binyuan Hui, Min Yang, Bowen Li, Binhua Li, Zheng Cao, Weijie Li, Fei Huang, Luo Si, et al. 2022.  Star: Sql guided pre-training for context-dependent text-to-sql parsing.  _arXiv preprint arXiv:2210.11888_.
  * Cao et al. (2021a) Ruisheng Cao, Lu Chen, Zhi Chen, Yanbin Zhao, Su Zhu, and Kai Yu. 2021a.  LGESQL: Line graph enhanced text-to-SQL model with mixed local and non-local relations.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 2541–2555, Online. Association for Computational Linguistics.
  * Cao et al. (2021b) Ruisheng Cao, Lu Chen, Zhi Chen, Yanbin Zhao, Su Zhu, and Kai Yu. 2021b.  LGESQL: line graph enhanced text-to-sql model with mixed local and non-local relations.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/IJCNLP 2021, (Volume 1: Long Papers), Virtual Event, August 1-6, 2021_ , pages 2541–2555. Association for Computational Linguistics.
  * Chen et al. (2021) Zhi Chen, Lu Chen, Hanqi Li, Ruisheng Cao, Da Ma, Mengyue Wu, and Kai Yu. 2021.  Decoupled dialogue modeling and semantic parsing for multi-turn text-to-SQL.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 3063–3074, Online. Association for Computational Linguistics.
  * Gan et al. (2022) Yujian Gan, Xinyun Chen, Qiuping Huang, and Matthew Purver. 2022.  Measuring and improving compositional generalization in text-to-SQL via component alignment.  In _Findings of the Association for Computational Linguistics: NAACL 2022_ , pages 831–843, Seattle, United States. Association for Computational Linguistics.
  * Guo et al. (2020) Yinuo Guo, Zeqi Lin, Jian-Guang Lou, and Dongmei Zhang. 2020.  Hierarchical poset decoding for compositional generalization in language.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Herzig and Berant (2021) Jonathan Herzig and Jonathan Berant. 2021.  Span-based semantic parsing for compositional generalization.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/IJCNLP 2021, (Volume 1: Long Papers), Virtual Event, August 1-6, 2021_ , pages 908–921. Association for Computational Linguistics.
  * Hu et al. (2022) Xuming Hu, Yong Jiang, Aiwei Liu, Zhongqiang Huang, Pengjun Xie, Fei Huang, Lijie Wen, and Philip S Yu. 2022.  Entda: Entity-to-text based data augmentation approach for named entity recognition tasks.  _arXiv preprint arXiv:2210.10343_.
  * Hu et al. (2020) Xuming Hu, Lijie Wen, Yusong Xu, Chenwei Zhang, and Philip S. Yu. 2020.  Selfore: Self-supervised relational feature learning for open relation extraction.  In _Proc. of EMNLP_ , pages 3673–3682.
  * Hu et al. (2021) Xuming Hu, Chenwei Zhang, Fukun Ma, Chenyao Liu, Lijie Wen, and Philip S. Yu. 2021\.  Semi-supervised relation extraction via incremental meta self-training.  In _Findings of EMNLP_ , pages 487–496.
  * Hupkes et al. (2020) Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. 2020.  Compositionality decomposed: How do neural networks generalise? _J. Artif. Intell. Res._ , 67:757–795.
  * Jia and Liang (2016) Robin Jia and Percy Liang. 2016.  Data recombination for neural semantic parsing.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 12–22, Berlin, Germany. Association for Computational Linguistics.
  * Keysers et al. (2020) Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Marc van Zee, and Olivier Bousquet. 2020.  Measuring compositional generalization: A comprehensive method on realistic data.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Lake and Baroni (2018a) Brenden Lake and Marco Baroni. 2018a.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _International conference on machine learning_ , pages 2873–2882. PMLR.
  * Lake and Baroni (2018b) Brenden M. Lake and Marco Baroni. 2018b.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 2879–2888. PMLR.
  * Li et al. (2023) Shu’ang Li, Xuming Hu, Li Lin, Aiwei Liu, Lijie Wen, and Philip S. Yu. 2023.  A multi-level supervised contrastive learning framework for low-resource natural language inference.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 31:1771–1783.
  * Liu et al. (2022a) Aiwei Liu, Xuming Hu, Li Lin, and Lijie Wen. 2022a.  Semantic enhanced text-to-sql parsing via iteratively learning schema linking graph.  In _Proc. of KDD_ , pages 1021–1030.
  * Liu et al. (2023) Aiwei Liu, Xuming Hu, Lijie Wen, and Philip S Yu. 2023.  A comprehensive evaluation of chatgpt’s zero-shot text-to-sql capability.  _arXiv preprint arXiv:2303.13547_.
  * Liu et al. (2022b) Aiwei Liu, Honghai Yu, Xuming Hu, Shu’ang Li, Li Lin, Fukun Ma, Yawen Yang, and Lijie Wen. 2022b.  Character-level white-box adversarial attacks against transformers via attachable subwords substitution.  In _Proc. of EMNLP_.
  * Liu et al. (2020) Qian Liu, Bei Chen, Jiaqi Guo, Jian-Guang Lou, Bin Zhou, and Dongmei Zhang. 2020\.  How far are we from effective context modeling? an exploratory study on semantic parsing in context.  In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020_ , pages 3580–3586. ijcai.org.
  * Liu et al. (2022c) Shuliang Liu, Xuming Hu, Chenwei Zhang, Shu’ang Li, Lijie Wen, and Philip S. Yu. 2022c.  Hiure: Hierarchical exemplar contrastive learning for unsupervised relation extraction.  In _Proc. of NAACL-HLT_ , pages 5970–5980.
  * OpenAI (2023) OpenAI. 2023.  Gpt-4 technical report.  _ArXiv_ , abs/2303.08774.
  * Qi et al. (2022) Jiexing Qi, Jingyao Tang, Ziwei He, Xiangpeng Wan, Chenghu Zhou, Xinbing Wang, Quanshi Zhang, and Zhouhan Lin. 2022.  RASAT: integrating relational structures into pretrained seq2seq model for text-to-sql.  _CoRR_ , abs/2205.06983.
  * Qiu et al. (2022a) Linlu Qiu, Peter Shaw, Panupong Pasupat, Pawel Nowak, Tal Linzen, Fei Sha, and Kristina Toutanova. 2022a.  Improving compositional generalization with latent structure and data augmentation.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 4341–4362, Seattle, United States. Association for Computational Linguistics.
  * Qiu et al. (2022b) Linlu Qiu, Peter Shaw, Panupong Pasupat, Pawel Krzysztof Nowak, Tal Linzen, Fei Sha, and Kristina Toutanova. 2022b.  Improving compositional generalization with latent structure and data augmentation.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL 2022, Seattle, WA, United States, July 10-15, 2022_ , pages 4341–4362. Association for Computational Linguistics.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21:140:1–140:67.
  * Scholak et al. (2021) Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. 2021.  PICARD: Parsing incrementally for constrained auto-regressive decoding from language models.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 9895–9901, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Shaw et al. (2021) Peter Shaw, Ming-Wei Chang, Panupong Pasupat, and Kristina Toutanova. 2021.  Compositional generalization and natural language variation: Can a semantic parsing approach handle both? In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 922–938, Online. Association for Computational Linguistics.
  * Wang et al. (2020) Bailin Wang, Richard Shin, Xiaodong Liu, Oleksandr Polozov, and Matthew Richardson. 2020.  RAT-SQL: Relation-aware schema encoding and linking for text-to-SQL parsers.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7567–7578, Online. Association for Computational Linguistics.
  * Wang et al. (2021) Runze Wang, Zhen-Hua Ling, Jingbo Zhou, and Yu Hu. 2021.  Tracking interaction states for multi-turn text-to-sql semantic parsing.  In _Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021_ , pages 13979–13987. AAAI Press.
  * Xiao et al. (2022) Dongling Xiao, Linzheng Chai, Qian-Wen Zhang, Zhao Yan, Zhoujun Li, and Yunbo Cao. 2022.  CQR-SQL: conversational question reformulation enhanced context-dependent text-to-sql parsers.  _CoRR_ , abs/2205.07686.
  * Yu et al. (2019a) Tao Yu, Rui Zhang, Heyang Er, Suyi Li, Eric Xue, Bo Pang, Xi Victoria Lin, Yi Chern Tan, Tianze Shi, Zihan Li, Youxuan Jiang, Michihiro Yasunaga, Sungrok Shim, Tao Chen, Alexander Fabbri, Zifan Li, Luyao Chen, Yuwen Zhang, Shreya Dixit, Vincent Zhang, Caiming Xiong, Richard Socher, Walter Lasecki, and Dragomir Radev. 2019a.  CoSQL: A conversational text-to-SQL challenge towards cross-domain natural language interfaces to databases.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 1962–1979, Hong Kong, China. Association for Computational Linguistics.
  * Yu et al. (2021) Tao Yu, Rui Zhang, Alex Polozov, Christopher Meek, and Ahmed Hassan Awadallah. 2021\.  Score: Pre-training for context representation in conversational semantic parsing.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. 2018\.  Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-SQL task.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3911–3921, Brussels, Belgium. Association for Computational Linguistics.
  * Yu et al. (2019b) Tao Yu, Rui Zhang, Michihiro Yasunaga, Yi Chern Tan, Xi Victoria Lin, Suyi Li, Heyang Er, Irene Li, Bo Pang, Tao Chen, Emily Ji, Shreya Dixit, David Proctor, Sungrok Shim, Jonathan Kraft, Vincent Zhang, Caiming Xiong, Richard Socher, and Dragomir Radev. 2019b.  SParC: Cross-domain semantic parsing in context.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4511–4523, Florence, Italy. Association for Computational Linguistics.
  * Zheng and Lapata (2022) Hao Zheng and Mirella Lapata. 2022.  Disentangled sequence to sequence learning for compositional generalization.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022_ , pages 4256–4268. Association for Computational Linguistics.
  * Zheng et al. (2022) Yanzhao Zheng, Haibin Wang, Baohua Dong, Xingjun Wang, and Changshan Li. 2022.  HIE-SQL: History information enhanced network for context-dependent text-to-SQL semantic parsing.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pages 2997–3007, Dublin, Ireland. Association for Computational Linguistics.