Dependency Parsing is More Parameter-Efficient with Normalization

Q.1: Although this research question is very detailed and easily overlooked, I don't think this contribution meets the acceptance bar of NeurIPS.

A.1: We agree with the reviewer that the topic of our contribution is indeed overlooked. Thus, our work is novel in terms of improving dependency parsing as an application. Furthermore, our contribution involves analyzing normalization phenomena in architectures used broadly in graph inference tasks (i.e., modeling edges as fully connected weighted graphs via attention mechanisms, such as biaffine transformations, see [1,2,3] for reference). To show this, we have repeated the experiment using Graph Attention Networks (GAT), using a stack of biaffine/GAT pairs to encode higher-order dependencies before the final biaffine layer. The results with this new architecture are consistent, as shown in the table below. Moreover, we have expanded the experiments to six multilingual settings as reported in our answer to the reviewer's next comment.

Score normalization improves performance also when using GATs, showing that our method generalizes to other architectures, besides Transformers and BiLSTMS. We have included these results to the paper.

In addition to our technical contribution, we believe that our work contributes to the broad NeurIPS community, by suggesting the importance of peculiar settings such as normalization in the training of neural network models. Moreover, we would like to respectfully point out that the NeurIPS guideline of acceptance suggests a work with "high impact on at least one sub-area of AI" (per grade 5), meaning that broad impact is not strictly required for acceptance. We appreciate the reviewer's consideration in this regard.

*[1] Kazi et al. "Differentiable Graph Module (DGM) for Graph Convolutional Networks". 2023.

*[2] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, "Graph attention networks". 2017.

*[3] J. Zhang, X. Shi, J. Xie, H. Ma, I. King, and D.-Y. Yeung, "GAAN: Gated attention networks for learning on large and spatiotemporal graphs". 2018.

Q.2: Are there consistent experimental results on other language datasets? Experimental conclusion should be verified on more languages.

A.2: We thank the reviewer for pointing this out. We performed multilingual experiments using six non-English UD datasets (UD_Arabic-PADT, UD_Chinese-GSD, UD_Italian-ISDT, UD_Japanese-GSD, UD_Spanish-AnCora, UD_Wolof-WTB) and verified that our finding is consistent, as shown in the table below.

Q.3: What are experimental results if add a Normal Layer?

A.3: As regards the addition of LayerNorm, experimental results on the effect of adding normalization layers were present in the original manuscript. We refer the reviewer to Appendix B.5 for our analysis. In Table 8, we show that the addition of LayerNorm layers in between the BiLSTM layers is detrimental on average, over all datasets.

Q.1: While Claim 1 provides intuition, the proof is somewhat informal. The connection between rank reduction and variance reduction could be more rigorously established.

A.1: We thank the reviewer for pointing out that our proof (and claim) could be made more rigorous. We have restated the claim and proof formally with a more standard analysis of covariance using the trace. Please see below:

Claim 1 (Monotonic Increase of Output Variance with Rank)

Let $X \in \mathbb{R}^n$ be a random vector with covariance matrix $\mathbf{K_{xx}} := \text{Cov}(X) \in \mathbb{R}^{n \times n}$, and let $\mathbf{A} \in \mathbb{R}^{m \times n}$ be a fixed matrix with singular value decomposition (SVD):

$\mathbf{A} = \sum_{i=1}^{min(m, n)} \sigma_i \mathbf{u}_i \mathbf{v}_t^{\top}$

where $\sigma_1 \geq \sigma_2 \geq ... \geq 0$. Define the best rank-$r$ approximation of $\mathbf{A}$ by truncated SVD as:

$\mathbf{A_r} := \sum_{i=1}^r \sigma_i \mathbf{u}_i \mathbf{v}_t^{\top}$

Let $Y_r = \mathbf{A}_rX \in \mathbb{R}^m$ denote the image of $X$ under the rank-$r$ linear map. Then, the total variance of $Y_r$, as measured by the trace of its covariance matrix, increases monotonically with $r$:

$\text{tr}(\text{Cov}(Y_r)) \leq \text{tr}(\text{Cov}(Y_{r + 1}))$

Proof. Let $\mathbf{K_{xx}} := \text{Cov}(X) \in \mathbb{R}^{n \times n}$ denote the covariance matrix of the random vector $X$. Since covariance matrices are symmetric and positive semi-definite (PSD), we have $\mathbf{K_{xx}} \succeq 0$. Let $\mathbf{A_r} := \sum_{i=1}^r \sigma_i \mathbf{u}_i \mathbf{v}_t^{\top}$ be the rank-$r$ truncated SVD of $\mathbf{A}$. Then the covariance matrix of $Y_r := \mathbf{A_r} X$ is:

$\text{Cov}(Y_r) = \mathbf{A_r} \mathbf{K_{xx}} \mathbf{A_r}^{\top}.$

To evaluate the total variance we compute the trace:

$\text{tr}\left(\text{Cov}(Y_r)\right) = \text{tr}\left(\mathbf{A_r}\mathbf{K_{xx}} \mathbf{A_r}^{\top}\right).$

Using the cyclic property of the trace $\left(\text{tr}(ABC) = \text{tr}(BCA)\right)$ and symmetry of $\mathbf{K_{xx}}$ we get:

$\text{tr}\left(\mathbf{A_r}\mathbf{K_{xx}} \mathbf{A_r}^{\top}\right) = \text{tr}\left(\mathbf{K_{xx}} \mathbf{A_r}^{\top} \mathbf{A_r} \right).$

Now define the matrix $\mathbf{M_r} := \mathbf{A_r}^{\top} \mathbf{A} \in \mathbb{R}^{n \times n}$, which is PSD. As $r$ increases, $\mathbf{A_r}$ includes more terms in its truncated SVD, so we have:

$\mathbf{M_{r}} = \sum_{i=1}^r \sigma^2_i \mathbf{v_i} \mathbf{v_i}^{\top}, \quad \mathbf{M_{r+1}} = \mathbf{M_r} + \sigma^2_{r+1} \mathbf{v_{r+1}} \mathbf{v_{r+1}}^{\top}.$

Thus:

$\mathbf{M}_{r+1} \succeq \mathbf{M}_r.$

Since $\mathbf{K_{xx}} \succeq 0$, and since the trace of a product of PSD matrices respects Loewner order (i.e., if $A \preceq B$, then $\text{tr}(CA) \leq \text{tr}(CB)$ for all $C \succeq 0$), we conclude:

$\text{tr}(\mathbf{K_{xx}} \mathbf{M_r}) \leq \text{tr}(\mathbf{K_{xx}}\mathbf{M_{r+1}}),$

which implies:

$\text{tr}\left(\text{Cov}(Y_r)\right) \leq \text{tr}\left(\text{Cov}(Y_{r+1})\right).$

Therefore, as the rank $r$ increases, the total variance $Y_r$ increases. $\square$

Q.2.1: The normalization benefits vary significantly across datasets.

A.2.1: Thank you for raising this point. In order to show the generalizability of our results, we have carried out six additional experiments on multilingual syntactic dependency parsing, showing consistent results for a wide variety of languages.

Furthermore, we believe it is important to keep into account that we found the difference in performance to be statistically significant on all datasets, as mentioned in Figure 3.

Q.2.2: In addition, the main focus of the paper on BiLSTM-based architectures may limit applicability to modern Transformer-based parsers.

A.2.2: We would like to point out that the parser with which we experiment is Transformer-based, with the Dozat and Manning biaffine layer still being the standard for dependency parsing. Even without using BiLSTM layers and fully fine-tuning the Transformer, we have found that normalization provides statistically significant benefits, as shown in Figure 4 for the SciERC dataset. In Appendix B.6, we also show this more generally on all four SemDP datasets with BERT-base, BERT-large, DeBERTa-base, and DeBERTa-large. The effect is particularly pronounced for DeBERTa-base.

Q.1: I wonder whether this finding is still effective in other languages, especially low-resource languages.

A.1: We thank the reviewer for suggesting multilingual settings. We have run the model on six non-English UD datasets (UD_Arabic-PADT, UD_Chinese-GSD, UD_Italian-ISDT, UD_Japanese-GSD, UD_Spanish-AnCora, UD_Wolof-WTB) and verified that our findings are consistent. In the following we summarized the multilingual results. We have added them to the paper.

Q.2: This research question is too minor to have a significant impact on the broad research community. I think the main research content of this paper is not suitable for publication in NeurIPS. I recommend that the author pay attention to more targeted venues, so that researchers in specific sub-community can pay attention to this work.

A.2: While it is true that semantic and syntactic dependency parsing are specific to communities in NLP, our paper contributes towards analyzing normalization phenomena in architectures used broadly in graph inference tasks (modeling edges as fully connected weighted graphs via attention mechanisms such as biaffine transformations, see [1,2,3] for reference). To further demonstrate this, we have conducted an experiment using Graph Attention Networks (GAT) by adding a stack of biaffine/GAT pairs. The purpose of this is to encode higher-order dependencies before the final biaffine layer. The results with this new architecture are consistent, as shown in the table below.

Similar to BiLSTMs, the normalization improves the scores in the case of GATs as well, showing that our method generalizes to other architectures, besides Transformers and BiLSTMS. We have included these results to the paper.

In addition to our technical contribution, we believe that our work contributes to the broad NeurIPS community, by suggesting the importance of peculiar settings such as normalization in the training of neural network models. Moreover, we would like to respectfully point out that the NeurIPS guideline of acceptance suggests a work with "high impact on at least one sub-area of AI" (per grade 5), meaning that broad impact is not strictly required for acceptance. We appreciate the reviewer's consideration in this regard.

• [1] Kazi et al. "Differentiable Graph Module (DGM) for Graph Convolutional Networks". 2023.

• [2] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, "Graph attention networks". 2017.

• [3] J. Zhang, X. Shi, J. Xie, H. Ma, I. King, and D.-Y. Yeung, "GAAN: Gated attention networks for learning on large and spatiotemporal graphs". 2018.

Q.3: Please change eh, ed, rh, and rd in figure 2 to the format of mathematical vector (i.e., $e^h$, $e^d$, $r^h$, and $r^d$), so they are consistent with the text and equation.

A.3: We have amended the formatting oversight as requested.

We thank the reviewer for their insightful review.

Q.1: for now only seen for dependency parsing task

A.1: We acknowledge that our work targets semantic and syntactic dependency parsing tasks only. This was purposeful because this variant (Dozat and Manning) of biaffine scoring is widespread on these tasks in particular. While we plan to extend our normalization analysis to graph inference broadly (e.g. using QM9 for small molecules or citation networks), we believe that the current work presents a solid and focused contribution using one of the most common and SOTA architectures. Moreover, extending our analysis to non-linguistic tasks would involve many architectural variants (e.g. GNN types) that we feel are necessary to cover in a separate work built on the contribution of the current work. As an initial step towards using Graph Attention Networks (GAT), we have repeated the experiment by adding a stack of biaffine/GAT pairs to encode higher-order dependencies before the final biaffine layer. We achieve consistent results as shown in the table below. The performance increases for $L_\phi \in \{1, 2\}$, compared to $L_\phi = 0$, but drops again at $L_\phi = 3$:

The normalization improves the scores in the case of GATs as well, showing that our method generalizes to other architectures, besides Transformers and BiLSTMS. We have included these results to the paper.

Q.2: while a possible reason for raw version performing okay with higher number of layers is discussed, it is not known why in some cases the performance of normalized version drops and exhibits high variance when number of layers is increased

A.2: We have repeated the experiment with $L_\psi > 3$ over three seeds and increased the amount of training steps to 20,000. All of the models made it to at least 6k steps (but not all of them made it to 8k or further, due to early stopping). We show the results at 2k, 4k, and 6k steps below (rows with no high variances removed due to character limit):

2000 steps:

4000 steps:

6000 steps:

The results show that once a model fails to find a good trajectory at the start, it likely remains on a poor trajectory. For example, the model with $L_\psi \in \{7, 8\}$ and norm = n does fine on CoNNL04 at 2,000 steps; however, one of the seeds then fails randomly at 4,000 steps and the performance remains poor past that point. For ADE, we can see that model performance with $L_\psi = 10$ and norm = n is fine at 2k and 4k steps, but suddenly drops with higher variance at 6k steps. Once again, this is because the model suddenly breaks and then remains broken for a specific seed. The table below does not show some of the poor performances because it reports the results of each seed at the best validation performance, up to 20k steps:

Despite the random crashes, increasing the number of steps increased the performance and reduced the Std for deeper stacks, compared to the original manuscript. While we still see instability for CoNLL04 and SciERC, it is reduced compared to the results shown in the original manuscript in Figure 5. Furthermore, the high variance almost disappears for ADE and ERFGC when training for a higher number of steps. Even more importantly, the results are identical for enEWT and SciDTB, with and without normalization, hinting at the fact that this is not inherently a problem of the model, but has to do with the nature of the datasets. More specifically, we also see some instability for ERFGC without score normalization at $L_\psi = 10$, and at $L_\psi = 9$ with score normalization. Similarly high variance can be seen for ADE with normalization at $L_\psi = 9$ (but not 10). Given that the high variances are produced by a few zero or near-zero scores, the instability seems to mostly be a product of the higher number of layers.

We have also analyzed the behavior of the gradients w.r.t. the depth of the layers. For SciERC (highest Std at $L_\psi = 10$ in the original manuscript), the table below shows the head and tail for 14k steps of norm of the gradient for the 10 layers:

Since the gradient evens out, we reckon it not to be the issue at hand here. It is likely that the higher parameter count of 10 layers simply necessitates more training steps.

Formatting:

We commit to fix the issues raised by the reviewer w.r.t. line 38, line 208, and commit to improving the readability of Figs. 6 and 7.