\documentclass[english]{jnlp_3.8}
\usepackage{jnlpbbl_2.2}
\usepackage[dvipdfmx]{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}
\usepackage{array}
\allowdisplaybreaks

\usepackage{hangcaption_jnlp}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% author's definition

\usepackage{multirow}

%%%%%\usepackage{CJKutf8}
%%%%%\usepackage{xcolor}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage[noend]{algpseudocode}
\usepackage{booktabs} 
%%%%%\usepackage{comment}
%%%%%\usepackage{soul}

%%%%%\usepackage{fancyhdr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Volume{32}
\Number{1}
\Month{March}
\Year{2025}
%%%%\Issuetitle{「　　　　」特集号}

\received{2024}{7}{25}
\revised{2024}{11}{1}
\accepted{2024}{12}{4}




\setcounter{page}{219}


%%%%   Title, Author, etc.            %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\esubject{General Paper}
\etitle{Data Augmentation for Low-Resource Languages \\ in Multilingual Dependency Parsing}
\eauthor{Jiannan Mao\affiref{Author_1} \and Chenchen Ding\affiref{Author_2} \and Hour Kaing\affiref{Author_2} \and Hideki Tanaka\affiref{Author_2} \and Masao Utiyama\affiref{Author_2} \and Tadahiro Matsumoto\affiref{Author_1}} 
\eabstract{
UDify \cite{kondratyuk-straka-2019-75} is a multilingual, multi-task  parser fine-tuned on mBERT that achieves remarkable performance on high-resource languages. However, on some low-resource languages, its performance saturates early and decreases gradually as training proceeds. To address this issue, this study applies a data augmentation method to improve parsing performance. We conducted experiments on five few-shot and three zero-shot languages to test the effectiveness of this approach. The unlabeled attachment scores were improved on the zero-shot language dependency parsing tasks, with the average score increasing from $55.6\%$ to $59.0\%$. Meanwhile, dependency parsing tasks in high-resource languages and other Universal Dependencies tasks were almost unaffected. The experimental results demonstrate that the data augmentation method is effective for low-resource languages in multilingual dependency parsing. Furthermore, our experiments confirm that continuously increasing the quantity of synthetic data enhances UDify's performance. This improvement was particularly effective for zero-shot target languages.\footnotetext{A part of this work was done during the first author's internship at National Institute of Information and Communications Technology, Kyoto, Japan. Parts of this paper were published at PACLIC 2023 \protect\cite{mao-etal-2023-improving} and MWE-UD 2024 \protect\cite{mao-etal-2024-overcoming}.}
}
\ekeywords{Dependency Parsing, Multilingual Processing, Low-Resource Languages, Data Augmentation, Unsupervised Learning}

\headauthor{Mao et al.}
\headtitle{Data Augmentation for Low-Resource Languages in Multilingual Dependency Parsing}


%%%%     Affiliation     %%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\affilabel{Author_1}{}{Gifu University}
\affilabel{Author_2}{}{National Institute of Information and Communications Technology (NICT)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S1
\section{Introduction}
\label{sec:intro}

Dependency parsers are tools used in computational linguistics to analyze the grammatical structure of sentences. They identify the relationships between words and highlight the dependencies that define grammatical meaning. Such insights are crucial for understanding syntactic roles and relationships within sentences and are essential for various language processing tasks. Efficiently training dependency parsers requires large treebanks \cite{DBLP:conf/iclr/DozatM17,qi-etal-2020-stanza,straka-strakova-2020-udpipe}, which are structured datasets that annotate grammatical dependencies between words for specific languages. However, for low-resource languages that have no (zero-shot) or limited (few-shot) data available in treebanks, the challenge of training effective dependency parsers becomes significant. Multilingual modeling has emerged as an efficient solution in these cases, leveraging cross-lingual information to compensate for the lack of data on specific languages. Studies have demonstrated that performance on multilingual tasks can be boosted by pairing languages with similarities \cite{scholivet-etal-2019-typological,ustun-etal-2022-udapter}. Furthermore, multilingualism also reduces the expense of training multiple models for a group of languages  \cite{johnson-etal-2017-googles,aharoni-etal-2019-massively,muennighoff-etal-2023-crosslingual}.

UDify \cite{kondratyuk-straka-2019-75} exemplifies the effectiveness of this multilingual modeling approach. A multi-task model fine-tuned on multilingual BERT embeddings \cite{devlin-etal-2019-bert}, UDify has been trained using Universal Dependencies (UD) v2.3 \cite{zeman-etal-2018-conll}, which enables it to generate annotations for any treebank included in v2.3. It exhibits strong and consistent performance across all 124 UD treebanks for 75 languages, efficiently handling tasks such as part-of-speech (POS) tagging, lemmatization and dependency parsing. Despite its robust performance, an overlooked issue is the early saturation problem of the model in zero-shot languages, particularly evident in dependency parsing tasks, as illustrated in Figure \ref{fig:udify-train}, which shows the training process unlabeled attachment score (UAS) for example high-resource, few-shot, and zero-shot languages. In this figure, high-resource and few-shot languages demonstrate stable growth, while zero-shot languages show a gradual decline. This causes substantial discrepancies in the performance of methods such as UDify  in zero-shot language scenarios, even when using almost identical training strategies, datasets, models, and evaluation methods, as reported in \citeA{ustun-etal-2020-udapter,choudhary-2021-improving,ustun-etal-2022-udapter,effland-collins-2023-improving}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F1
\begin{figure}[b]
\begin{center}
\includegraphics{32-1ia8f1.eps}
\end{center}
\hangcaption{UAS performance trends during training for the \texttt{English-GUM} (high-resource), \texttt{Upper Sorbian-UFAL} (few-shot), and \texttt{Breton-KEB} (zero-shot) treebanks.}
\label{fig:udify-train}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

While data augmentation methods have proven effective for high-resource languages \cite{el-kurdi-etal-2020-scalable}, they typically rely on existing annotated data and are thus not applicable to zero-shot languages, which lack such resources. To address the early saturation of dependency parsing in zero-shot languages, we propose a novel data augmentation strategy tailored specifically for these languages. Our approach begins by employing the trained UDify model to parse raw sentences from zero-shot languages, obtaining initial probabilities for dependency arcs. We then apply unsupervised learning techniques to refine these probabilities without the need for annotated data. The refined probabilities are then used to generate synthetic structured dependency data for the zero-shot languages. By integrating this synthetic data into UDify's training set, we expand the dataset's diversity and size, thereby enhancing UDify's performance and stability on zero-shot languages.

In this work, we conducted comprehensive experiments on low-resource languages using data augmentation methods, expanding (for few-shot languages) and creating (for zero-shot languages) synthetic treebanks for five few-shot and three zero-shot languages. By combining these synthetic treebanks with the UD treebanks and using the UDify framework, we trained a multilingual parser. As a result, increases in the UAS for zero-shot languages in the UD v2.13 were observed, with the average value increasing from $55.6\%$ to $59.0\%$. In the best case, the UAS increased substantially from $52.7\%$ to $61.0\%$. Similarly, few-shot languages experienced a UAS increase of $0.2\%$. By contrast, the UAS results for other languages and evaluation scores for other tasks did not show significant negative changes, suggesting that the overall robustness of the multilingual and multi-task processing was retained.

The remainder of this paper is organized as follows. In Section \ref{sec:back}, we first introduce UD, UDify, and unsupervised dependency learning algorithms as the background of this study. Section \ref{sec:prop} describes the performance of UDify on low-resource language scenarios, particularly on zero-shot languages, as well as a data augmentation method based on UDify and unsupervised learning algorithms. The experimental results of the case study are provided in Section \ref{sec:exp}. In addition, we discussed the impact of synthetic data quantity on the model and the enhancements made to single language data synthesis in Section \ref{sec:discuss}. Section \ref{sec:concl} concludes the paper and outlines future directions for this research.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S2
\section{Background}
\label{sec:back}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S2.1
\subsection{Universal Dependencies}
\label{sec:ud_treebank}

Universal Dependencies (UD) are initiatives aimed at creating consistently annotated treebanks for numerous languages. Contributors from around the world have supplied treebanks for hundreds of languages, thereby enhancing global linguistic analysis and comparison globally.

Some languages in the UD are represented by multiple treebanks. These treebanks are named using a structured format that combines the language name with an identifier for the data source or the creators. For example, the name \texttt{English-GUM} \cite{Zeldes2017} consists of \texttt{English} denoting the language and \texttt{GUM} indicating the Georgetown University Multilayer corpus project.\footnote{\url{gucorpling.org/gum/index.html}} This systematic naming method ensures clarity and facilitates easy identification and comparison across different languages and sources.

We classify languages into high-resource and low-resource groups based on the available quantity of annotated data in the UD treebanks. High-resource languages have extensive annotated data, providing robust resources for linguistic analysis and computational tasks. Low-resource languages are further refined by \citeA{yang-etal-2022-low} into two groups: few-shot languages, which have only a small amount of training data from the UD treebanks, and zero-shot languages, which lack any training data and exist only in test datasets. This categorization facilitates a more systematic examination of UDify's performance across different linguistic resources, thereby providing crucial insights that guide our research.

Each treebank in the UD encompasses a rich array of grammatical annotations that characterize the linguistic features of sentences \cite{nivre-etal-2007-conll}. These include POS, which categorizes words according to their grammatical roles, lemmas that provide the base forms of words, morphological features describing inflectional properties, and dependency structures that map out the relationships between words. Figure \ref{fig:treebank_example} illustrates the directional arcs with relationships between words, with a key focus on the arcs in this study. UAS is a key evaluation metric to measure the accuracy of these arcs.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F2
\begin{figure}[b]
\begin{center}
\includegraphics{32-1ia8f2.eps}
\end{center}
\hangcaption{Visualization of ``Otto Jespersen was born in Randers in Jutland.'' with POS tags, dependency arcs and relations from the \texttt{English-GUM} test set, using UD Annotatrix \protect\cite{tyers-etal:2018}.}
\label{fig:treebank_example}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S2.2
\subsection{UDify}

UDify is composed of a pre-trained mBERT model, which is a self-attention network with 12 transformer encoder layers \cite{NIPS2017_3f5ee243}, and a multi-task network for processing POS tags, lemmas, morphological features, and dependency structures, as illustrated in Figure \ref{fig:udify}. Unlike traditional models that require training specifically for each language, UDify uses mBERT's subword tokenization mechanism to jointly train across all UD treebanks. Note that for words tokenized into multiple subword units, only the first subword unit is input into the neural network designed for specific tasks.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F3
\begin{figure}[t]
\begin{center}
\includegraphics{32-1ia8f3.eps}
\end{center}
\hangcaption{UDify model structure, which has a task-specific layer that processes word tokens and delivers UD annotations for each token, using the example from Figure \ref{fig:treebank_example}. This figure is a redrawn adaptation based on illustrations from \protect\citeA{kondratyuk-straka-2019-75}.}
\label{fig:udify}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


The main focus of this study is dependency parsing, for which UDify uses a graph-based bi-affine attention classifier \cite{DBLP:conf/iclr/DozatM17}. This classifier processes embeddings through specific neural layers, generating probability distributions that are crucial for accurate dependency parsing. The resulting dependency structures are decoded using the Chu--Liu/Edmonds algorithm \cite{chu1965shortest,edmonds1967optimum}. To optimize its use with mBERT for multilingual tasks, UDify is fine-tuned using an adapted version of the ULMFiT strategy \cite{howard-ruder-2018-universal}, specifically modified for seamless integration with mBERT parameters.

Integrating these robust strategies enables UDify to excel in UD tasks across a variety of languages. Its effectiveness is especially notable in contexts involving dependency parsing for low-resource languages, where it delivers a reliable performance despite the limited data availability.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S2.3
\subsection{Unsupervised Dependency Learning}

Using the properties of dependency syntax \cite{abdff794-6f5f-3ad0-aeb8-18e02c589209}, a general unsupervised algorithm for projective N-gram dependency learning (Unsupervised-Dep) was described in \citeA{ding-yamamoto-2013-unsupervised,ding2014generative}. This method constructs the optimal dependency arcs using a dynamic programming method with a CKY table based on the concepts of complete-link and complete-sequence non-constituents. However, considering the time complexity of this approach for arbitrary N-gram dependency learning, which may not be ideal for practical applications, we chose to focus on the bi-gram case in this study.

In the case of bi-grams, the directionality of a complete-link is determined by the outermost dependency direction, where ($w_{i} \rightarrow w_{j}$) indicates a rightward link and ($w_{i} \leftarrow w_{j}$) indicates a leftward link. The basic complete-link is an adjacent word dependency link.

A complete-sequence represents a null or sequential set of adjacent complete-links with identical directionality. It begins as a null sequence of complete-links based on a single word, its smallest constituent. The direction of a complete-sequence matches that of its component complete-links.

Unsupervised learning first constructs complete-links and complete-sequences for a substring, then incrementally merges the complete-links into larger complete-sequences and complete-{\linebreak}sequences into larger complete-links. The recursion can be defined as follows:
\begin{equation}
\begin{array}{c}
Link_{r}(i,j) \equiv \{(w_{i}\rightarrow w_{j}),Seq_{r}(i,k),Seq_{l}(k+1,j)\}
\\[10pt]
Link_{l}(i,j)\equiv \{(w_{i}\leftarrow w_{j}),Seq_{r}(i,k),Seq_{l}(k+1,j)\}
\\[10pt]
Seq_{r}(i,j)\equiv \{Seq_{r}(i,k),Link_{r}(k,j)\}
\\[10pt]
Seq_{l}(i,j)\equiv \{Link_{l}(i,k),Seq_{l}(k,j)\} \notag
\end{array}
\end{equation}
In these equations, $Link$ and $Seq$ denote a complete-link and complete-sequence, respectively, while $r$ and $l$ indicate the direction (right or left). Furthermore, $i$ and $j$ represent the starting and ending indices of a word sequence in the sentence. This establishes the structural framework of the Unsupervised-Dep for complete-links and complete-sequences. The subsequent step applies the Inside--Outside algorithm \cite{lari1990estimation,DBLP:conf/acl-vlc/LeeC97} to quantitatively determine the probabilities associated with each link and sequence. We divide the computational process of the Inside--Outside algorithm into three parts: \texttt{Inside}, \texttt{Outside}, and \texttt{Probability Updates}. The details of this process are provided in Appendix \ref{sec:io}.

During the computation of Unsupervised-Dep across the entire corpus, the initial random probabilities $P(w_{i}\rightarrow w_{j})$ and $P(w_{i}\leftarrow w_{j})$ are continuously trained and refined. Ultimately, this process results in the refined probabilities $P^{'}(w_{i}\rightarrow w_{j})$ and $P^{'}(w_{i}\leftarrow w_{j})$. The Viterbi algorithm \cite{forney1973viterbi} determines the most probable tree structure within the inside portion of the input sentence $sent(1, n)$, generating the following optimal dependency arcs:
\begin{equation}
\begin{array}{c}
DEP_{arc} = Viterbi(CKY_{Inside}(sent(1, n), P^{'}(w_{i}\rightarrow w_{j}), P^{'}(w_{i}\leftarrow w_{j}))) 
\label{ex:viterbi}
\end{array}
\end{equation}
Here, $CKY_{Inside}$ represents the results in the CKY table obtained from the inside portion of the calculations. Using the above method, it is possible to learn from  the corpus of a specific language and generate a dependency treebank containing only dependency arcs without human intervention.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S3
\section{Proposed Method}
\label{sec:prop}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S3.1
\subsection{Motivation}

To ensure a comprehensive analysis, we initially used the UD v2.3 based on the original UDify training setup. However, recognizing the outdated nature of the UD v2.3, and ensuring the relevance and applicability of our findings, we incorporated the latest UD v2.13 treebanks into our study. This dual-dataset approach is crucial to rigorously evaluating the consistency of the early saturation phenomenon across different versions, affirming that our conclusions are robust and widely applicable.

Despite the original recommendation of 80 training epochs for UDify, our reproduction studies across both treebanks reveal that achieving results comparable to those reported in the literature typically required extending the training to approximately 200 epochs.\footnote{\url{lindat.mff.cuni.cz/repository/xmlui/handle/11234/1-3042}} This extension is crucial not only for verifying the robustness of the early saturation effect but also for observing performance changes in few- and zero-shot languages as defined in Section \ref{sec:ud_treebank}. These changes are further analyzed in the subsequent sections.

\subparagraph{Few-Shot Languages}

UDify demonstrates robust performance even on few-shot languages not included in the mBERT training set. For example, the Upper Sorbian language, which is absent from mBERT's training corpora, is notably under-resourced, with only 23 sentences in its \ \verb|Upper_Sorbian-UFAL| treebank training set. Despite these limitations, UDify achieves impressive parsing accuracy in Upper Sorbian. The training process shows a consistent increase in parsing accuracy on the test set, as depicted in Figure \ref{fig:few-shot}.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F4
\begin{figure}[t]
\begin{center}
\includegraphics{32-1ia8f4.eps}
\end{center}
\hangcaption{UAS performance trends during training for several few-shot languages: (left) results on UD v2.3, (right) results on UD v2.13.}
\label{fig:few-shot}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subparagraph{Zero-Shot Languages}

For UD v2.3, the treebanks of 13 languages used for training UDify lack both training and development datasets. In contrast, for UD v2.13, there are 65 zero-shot languages. Notably, three of these languages---Breton, Tagalog, and Yoruba---are included in mBERT's training data. These languages have zero-shot treebanks in both UD v2.3 and v2.13, and UDify learns their dependency structures through transfer learning. Unlike high-resource and few-shot languages, the dependency parsing accuracy for zero-shot languages tends to decline after the initial few epochs of training. The optimal performance for any version of the treebank is typically observed around the 8th epoch, as depicted in Figure \ref{fig:zero-shot}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F5
\begin{figure}[t]
\begin{center}
\includegraphics{32-1ia8f5.eps}
\end{center}
\hangcaption{UAS performance trends during training for zero-shot languages: (left) results for UD v2.3, (right) results for UD v2.13. Note that \texttt{Tagalog-Ugnayan} appears only in UD v2.13.}
\label{fig:zero-shot}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



While the literature does not explicitly report a decrease in accuracy for zero-shot languages with extended training, our detailed analysis of results from multiple studies \cite{ustun-etal-2020-udapter,choudhary-2021-improving,langedijk-etal-2022-meta,ustun-etal-2022-udapter} suggests such a trend. Given these disparities in training outcomes, where high-resource and few-shot languages show gradual improvements in contrast to the significant drops experienced by zero-shot languages, there is a pressing need for tailored strategies.

To address this issue, we have developed a data augmentation technique using Unsupervised-Dep specifically designed for multilingual parsers. This method is particularly crucial for zero-shot languages, as it extends their learning curve and stabilizes performance within multilingual parsers. Additionally, our decision to include few-shot languages is motivated by the potential of data augmentation to enhance performance on specific tasks for languages with limited data resources \cite{ding-etal-2020-daga}.

This strategy involves enriching the training dataset with refined dependency structures generated through Unsupervised-Dep. The approach is designed not only to mitigate the early saturation problem in zero-shot languages but also to enhance performance consistency across both few- and zero-shot languages. By improving the stability and effectiveness of UDify's dependency parsing capabilities, this technique addresses the immediate challenges and broadens the applicability and impact of our method. Furthermore, it has the potential to lead to significant improvements in dependency parsing accuracy for both few- and zero-shot languages.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%3.2
\subsection{UDify with Unsupervised Augmentation}

When applying the Unsupervised-Dep method to augment the data of UD treebanks, it is crucial to ensure that the generated data conform to the UD format. This approach, which we refer to as ``Unsupervised Augmentation,'' requires not only generating dependency arcs but also producing other types of data. These additional data types must then be integrated with the results from Unsupervised-Dep. We divide the Unsupervised Augmentation into two main components, training and generation, and provide a detailed explanation of each.

\subparagraph{Training}

Unsupervised-Dep has a high time complexity of $O(n^3)$, which makes the common practice in the original methods that start training from a random probability somewhat inefficient. To circumvent this, we leverage the parsing results from UDify to initialize the probabilities. Despite the potential decrease in UDify's accuracy on zero-shot languages during its training, the final results consistently outperform those from other parsing models \cite{qi-etal-2018-universal,zeman-etal-2018-conll,tran-bisazza-2019-zero}, providing a robust foundation for our initialization approach.

Our approach commences by feeding the raw corpus for a specific language $lang$, denoted as $D_{train}^{lang}$, into $trained\text{-}UDify$ and generating dependency arcs represented by $DEP_{arc}^{lang}$. Subsequently, statistical computations are performed specifically on the $DEP_{arc}^{lang}$ elements. The results, $P(w_{i}\rightarrow w_{j})^{lang}$ and $P(w_{i}\leftarrow w_{j})^{lang}$, serve as the initial probabilities for Unsupervised-Dep. Note that although the UDify parsing results include other types of information, such as POS, lemma, and dependecy relations (denoted as $other$), these are disregarded in the parsing results of $D_{train}^{lang}$ because they do not participate in our subsequent computations, as depicted in Figure \ref{fig:train}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F6
\begin{figure}[t!]
\begin{center}
\includegraphics{32-1ia8f6.eps}
\end{center}
\hangcaption{Integration of the parsing results from UDify with the training outcomes from Unsupervised-Dep for new UDify model training. The UDify model is a simplified diagram of that shown in Figure \ref{fig:udify}.}
\label{fig:train}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



The input for Unsupervised-Dep consists of $D_{train}^{lang}$ and the initial probabilities $P(w_{i}\rightarrow w_{j})^{lang}$ and $P(w_{i}\leftarrow w_{j})^{lang}$. After undergoing a set number of iterations, we obtain the {\linebreak}re-estimated probabilities $P^{'}(w_{i}\rightarrow w_{j})^{lang}$ and $P^{'}(w_{i}\leftarrow w_{j})^{lang}$. This process adheres to the principles of the expectation--maximization algorithm, as Algorithm \ref{alg:un} confirms. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Alg1
\begin{algorithm}[t!]
\caption{Unsupervised-Dep in multilingual corpora}\label{alg:un}
\input{08algorithm01.tex}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\subparagraph{Generation}
To construct optimal dependency arcs for a sentence $sent(1,n)$ from $D_{gen}^{lang}$ in the raw corpora, we utilize the re-estimated probabilities $P^{'}(w_{i}\rightarrow w_{j})^{lang}$ and $P^{'}(w_{i}\leftarrow w_{j})^{lang}$. The $Viterbi$ algorithm is employed to traverse the internal calculation results, as outlined in Eq. (\ref{ex:viterbi}).

Following this, we use $trained\text{-}UDify$ to parse $D_{gen}^{lang}$. The parsing results, termed  $DEP_{arc}^{lang}$ and $other^{'}$, are meticulously preserved. These data are illustrated in Figure \ref{fig:train} and play a crucial role in constructing the new UD format data, denoted as $UD^{'}$.

Subsequently, $UD^{'}$, which incorporates synthetic data for zero-shot languages, is integrated with the existing UD treebanks. This integration is specifically designed to train a new instance of UDify optimized for these languages. Notably, when a dependency arc exists between a word and the root, the relationship of this arc must be modified to ``root.'' Dependency relationships between other words as parsed by $trained\text{-}UDify$ remain unchanged. This selective adjustment ensures compliance with the ``single root principle'' of the dependency structure, which dictates that every sentence must have exactly one root, as cited in \cite{abdff794-6f5f-3ad0-aeb8-18e02c589209}. Modifying the dependency relationship to root for arcs that connect to the ``root'' reinforces this principle, maintaining the structural integrity necessary for clear syntactic analysis.

The Unsupervised Augmentation approach not only generates synthetic data for zero-shot languages but also transitions them from relying solely on transfer learning to a blend of supervised and transfer learning. Consequently, this significantly enhances the performance of the multilingual model in zero-shot languages.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S4
\section{Experiments}
\label{sec:exp}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S4.1
\subsection{Dataset}

In this experiment, the data were divided into two categories: treebank data for training UDify and raw data for Unsupervised Augmentation. To validate the effectiveness of our method, we conducted experiments using both UD v2.3 and v2.13 treebanks. The two versions are compared in Table \ref{tab:ud_data}. Notably, UD v2.13 includes significantly more data than UD v2.3, which is the original version of the UD treebank used by UDify. Specifically, v2.13 has added 72 languages, of which 51 are zero-shot languages, further emphasizing the necessity of this study.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%T1
\begin{table}[b]
\input{08table01.tex}
\hangcaption{Comparison of different versions of treebanks, where the numbers in parentheses indicate the number of languages/treebanks for which only test data are provided.}
\label{tab:ud_data}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

For the low-resource languages used in Unsupervised Augmentation, we selected eight languages that can be primarily tokenized using spaces, and we have detailed the analysis of their similarity to other high-resource languages in Appendix \ref{sec:lang2vec}. While our methodology is applicable to non-space-tokenized languages, we prioritized languages that facilitate a focused analysis on dependency structures without the complexities of tokenization, and are present in both versions of the UD treebanks. These include five few-shot languages and three zero-shot languages. We exhaustively collected data for these languages from publicly available corpora \cite{TIEDEMANN12.463,el-kishky-etal-2020-ccaligned,reimers-2020-multilingual-sentence-bert,schwenk-etal-2021-wikimatrix}, and divided the raw data for each language into parts $D_{train}$ and $D_{gen}$. We set $D_{gen}$ to 1,000, a decision that sets the stage for exploration of synthetic data quantity across multiple low-resource languages and its impact on UAS in subsequent experiments. The details and statistics of the collected data are organized and presented in Table \ref{tab:data} and referred to as ``OPUS-mult'' in subsequent sections.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%T2
\begin{table}[b]
\input{08table02.tex}
\hangcaption{Raw data collected from various corpora and the treebanks of the collected languages in UD v2.13. The top five languages are few-shot languages and the bottom three languages are the zero-shot languages. \#$D_{train}^{lang}$ indicates the number of raw sentences (in thousands) used for training in Unsupervised Augmentation, and \#$D_{gen}^{lang}$ indicates the raw sentences used for generating in Unsupervised Augmentation. \#train and \#test are the number of sentences in the training and test sets, respectively. The code represents the abbreviated name of the treebank, facilitating the display of the experimental results in subsequent sections. Treebanks marked with an ``*'' indicate that they exist in both versions, but those in UD v2.13 have with changes including but not limited to the number of test sets and error corrections. Treebanks marked with a ``+'' indicates that they are exclusive to UD v2.13.}
\label{tab:data}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S4.2
\subsection{Setup}

To minimize the impact of potential experimental environment changes, as discussed in \citeA{DBLP:journals/pbml/PopelB18}, we adhered to the parameter settings outlined in \citeA{kondratyuk-straka-2019-75} and reimplemented the model as UDify(our) across different versions of the treebanks. Additionally, to expedite the experimental process, we employed Horovod \cite{DBLP:journals/corr/abs-1802-05799} to modify UDify and AllenNLP \cite{gardner-etal-2018-allennlp} for multi-GPU parallel training.\footnote{When replicated across 16 V100s in parallel, replicating UDify takes close to 9 days on UD v2.3 and close to 18 days on UD v2.13.} During the training of the Unsupervised Augmentation, we used the UDify(our) model to parse each language present in the OPUS-mult dataset. The statistical results derived from the parsing outcomes of each language were adopted as their initial probabilities, which were continuously re-estimated throughout the unsupervised learning process. After the 10th training iteration, we used the newly estimated probabilities to parse sentences from the OPUS-mult dataset, generating data that align with the UD format.

To explore the impact of expanding and creating training data for low-resource languages on parsing accuracy, we conducted methodological experiments. In these experiments, we randomly selected 300 sentences for each language from $D_{gen}$ in OPUS-mult, processed them through the generation part of Unsupervised Augmentation, and integrated them into the UD treebanks to form the ``Unsup'' training dataset. Inspired by the work of \citeA{DBLP:journals/kais/TrigueroGH15,rybak-wroblewska-2018-semi}, we conducted an experiment using a comparative method called ``Self.'' In this approach, we used the same raw sentences as Unsup and applied the parsing results from the UDify(org) model. These results were merged with the original training set to train the Self model.

During training, following \citeA{mcdonald-etal-2011-multi}, we merged training sets, randomized the sentence order in each epoch, and fed the network diverse batches of original and synthetic data from multiple languages. Additionally, we controlled the amount of data in each epoch to ensure that each experiment used the same quantity of training data.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S4.3
\subsection{Result}

A comparison with the experimental results reported in \citeA{kondratyuk-straka-2019-75} confirms that UDify(our) was successfully reimplemented, as shown in Table \ref{tab:result}. Although no single method yielded significant improvements for few-shot languages, the results for zero-shot languages, analyzed using bootstrap resampling \cite{efron1992bootstrap}, demonstrate a consistent and significant enhancement in UDify's dependency arc accuracy through the Unsup strategy during training on different versions of the treebanks. This is reflected in the combined test set results, where the UAS for UD v2.3 increases from $63.8\%$ to $67.2\%$ and the UAS for UD v2.13 increases from $55.6\%$ to $59.0\%$. Since our study primarily focuses on the parsing accuracy of dependency arcs (measured by UAS), and given that the LAS has also shown improvement, we have included the LAS results in Appendix \ref{sec:las}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%T3
\begin{table}[t]
\input{08table03.tex}
\hangcaption{UAS (\%) for few- and zero-shot languages obtained using different methods on UD v2.3 and v2.13. The last two rows display the combined test set results for few- (Few) and for zero-shot (Zero) languages. We denote the treebank names using the codes from Table 1. The UDify(org) result for the v2.3 was reported in \protect\citeA{kondratyuk-straka-2019-75}. The best result in each group is highlighted in \textbf{bold}. Additionally, we conducted significance tests on the experimental results, comparing UDify(our) with Unsup, where ``$\ddagger$'' indicates a significance level of $p \leq 0.01$  and ``$\dagger$'' indicates $p \leq 0.05$, both showing where Unsup outperforms UDify(our).}
\label{tab:result}
{\vskip 10pt}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



To the best of our knowledge, this is the state-of-the-art result for Tagalog \cite{aquino-de-leon-2020-parsing,choudhary-2021-improving}. In UD v2.13, the UAS for treebanks \texttt{Tagalog-TRG} and \texttt{Tagalog-{\linebreak}Ugnayan} showed remarkable increases from 75.3\% and 52.7\% to 82.6\% and 61.0\%. Using Breton from the zero-shot languages in UD v2.3 and v2.13 as an example, we illustrate the changes in UAS during the training process under different methods in Figure \ref{fig:Breton_mult}. The figure reveals that incorporating data generated through Unsupervised Augmentation significantly mitigates the decline in UAS accuracy during the training of zero-shot languages, thereby improving outcomes. In the experimental results for UD v2.13, the performance of Unsup was better than that of UDify(our), but it still remains significantly lower than the accuracy at the start of training.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F7
\begin{figure}[t]
\begin{center}
\includegraphics{32-1ia8f7.eps}
\end{center}
\hangcaption{UAS performance trends during training are shown for the \texttt{Breton-KEB} test set, comparing two baselines, UDify(our) and Self, with the proposed method, Unsup. (Left) Results for UD v2.3, (right) results for UD v2.13.}
\label{fig:Breton_mult}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



Given that UDify is a multilingual dependency parser, it is essential to assess the impact of our proposed method on other languages. To further investigate the differences in UAS results between UDify(org) and Unsup, we tested all treebanks in UD v2.3 and v2.13. As shown in Figure \ref{fig:7}, the results indicate that using Unsupervised Augmentation to create synthetic data effectively enhances the UAS for zero-shot languages, particularly for Breton and Tagalog. However, considering that UD v2.13 contains a larger proportion of zero-shot treebanks (approximately 41.3\%), the Unsup method shows unstable results on these treebanks. This includes instances in which the UAS significantly increased for certain languages without data augmentation. Despite these fluctuations, the method's negative impact on the parsing precision of dependency structures in other languages remains minimal.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F8
\begin{figure}[t]
\begin{center}
\includegraphics{32-1ia8f8.eps}
\end{center}
\hangcaption{Difference in UAS (\%) across the test treebanks UD v2.3 (top) and UD v2.13 (bottom). The gray bars above the X-axis indicate Unsup $>$ UDify(our), and those below the X-axis indicate Unsup $<$ UDify(our) (left Y-axis). The black line (right Y-axis) shows treebank training set sizes. Zero-shot languages are to the left of the black dashed line. Note that because Tamil is represented by both treebanks \texttt{Tamil-MWTT} (ta-m) and \texttt{Tamil-TTB} (ta-t), we classify ta-m as few-shot.}
\label{fig:7}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


For a comprehensive comparison, the UD scores of the zero-shot and other languages have been compiled in Table \ref{tab:full_data}.\footnote{Except for \texttt{UD\_Chukchi-HSE}, the format of this treebank is not supported by the script used to calculate the UD scores.} Although our primary research objective was to improve the parsing accuracy of dependency arcs, we have also enhanced UDify's performance in other tasks for low-resource languages. UDify must balance the loss produced by multiple decoders during training, and as noted in the work of \citeA{rybak-wroblewska-2018-semi}, these variations in evaluation metrics are considered reasonable. Broadly, our method does not negatively impact other languages or tasks, maintaining their performance levels.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%T4
\begin{table}[t]
\input{08table04.tex}
\hangcaption{UD scores on selected zero-shot and other languages obtained by different methods. Rest(\%) refers to the average scores of UPOS, UFeats, Lemmas, and LAS in the UD scores. The best result in each group is in highlighted in \textbf{bold}.}
\vspace{-0.5cm}
\label{tab:full_data}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



Considering the current results, we believe that using Unsupervised Augmentation to synthesize training data for zero-shot languages is necessary and effective in a multilingual modeling context. In the following sections, we focus on UD v2.13 to discuss how the number of zero-shot languages synthesized by Unsupervised Augmentation impacts the UAS and its performance when applied to a single language exclusively.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S5
\section{Discussion}
\label{sec:discuss}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S5.1
\subsection{Quantity of Synthetic Data in Multiple Low-Resource Languages}

To further investigate the effectiveness of Unsupervised Augmentation, we conducted experiments on the impact of generating different quantities of synthetic data for low-resource languages on UAS. These experiments were carried out using UD v2.13. Maintaining the same experimental setup and parameters as in the previous chapter, we set a fixed amount of data for the input per epoch. To ensure the same number of model updates in each epoch and to avoid variations in the final UAS values due to update frequencies differences, we randomly discarded some data during each epoch. We set the number of synthetic data points to 100, 300, 500, and 1,000, representing sentences randomly selected from $D_{gen}$, producing a total of 800, 2,400, 4,000, and 8,000 synthetic data points for each of the eight languages listed in Table \ref{tab:data}, named Unsup${100}$, Unsup${300}$, Unsup${500}$, and Unsup${1000}$. The results of the experiments are presented in Table \ref{tab:data_quantity}, and the specific changes in UAS for zero-shot languages during the training process are illustrated in Figures \ref{fig:br_yo} and \ref{fig:tl_t-tl_u}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%T5
\begin{table*}[b]
\input{08table05.tex}
\hangcaption{UAS for few- and zero-shot languages obtained using different quantities of synthetic data. The best result in each group is in highlighted in \textbf{bold}.}
\label{tab:data_quantity}
\end{table*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F9
\begin{figure}[t]
\begin{center}
\includegraphics{32-1ia8f9.eps}
\end{center}
\hangcaption{UAS performance trends during training: (left) results for \texttt{Breton-KEB}, (right) results for \texttt{Yoruba-YTB}.}
\label{fig:br_yo}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F10
\begin{figure}[t]
\begin{center}
\includegraphics{32-1ia8f10.eps}
\end{center}
\hangcaption{UAS performance trends during training: (left) results for \texttt{Tagalog-TRG}, (right) results for \texttt{Tagalog-Ugnayan}.}
\label{fig:tl_t-tl_u}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



The experimental results and observed changes in UAS during the training process reveal that increasing the synthetic data quantity enhances both the stability during training and the final outcomes. Additionally, increasing synthetic data quantity can mitigate or suppress the downward trends observed during training. Specifically for \texttt{Tagalog-TRG} and \texttt{Tagalog-Ugnayan}, setting the synthetic data quantity to 1k significantly suppresses this downward trend. Although a decrease is still observed in \texttt{Breton-KEB} and \texttt{Yoruba-YTB}, the final results are superior to those obtained with smaller amounts of synthetic data. Moreover, for \texttt{Breton-KEB}, increasing the synthetic data quantity to 500 resulted in final UAS values that surpass those at the start of training. The performance metrics for selected zero-shot languages and other data not using Unsupervised Augmentation in UD tasks are shown in Table \ref{tab:full_data_quantity}, with no significant impact observed on other languages or tasks.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%T6
\begin{table}[t]
\input{08table06.tex}
\hangcaption{UD scores on selected zero-shot and other languages obtained by different methods. Rest(\%) indicates the average score of UPOS, UFeats, Lemma, and LAS in the UD scores. The best result in each group is in highlighted in \textbf{bold}.}
\label{tab:full_data_quantity}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S5.2
\subsection{Quantity of Synthetic Data in a Single Low-Resource Language}

When data augmentation is simultaneously performed on multilingual language models, it may lead to unexpected effects on other languages \cite{wang-etal-2020-negative}. Considering the benefits of targeted data augmentation in a multilingual environment \cite{choi2024optimizing}, we conducted experiments focusing on data augmentation for a single language treebank. This experiment evaluated the specific improvements in model performance attributable to augmenting the data for one language at a time.

Because \texttt{Breton-KEB} is the largest treebank of zero-shot language in our experiments, it allows for a more effective evaluation of Unsupervised Augmentation's performance on a single language. Therefore, we selected Breton as our target for Unsupervised Augmentation. Regarding the synthetic data quantity, we maintained the same parameters as in other experiments: 100, 300, 500, and 1,000, labeled as br$_{100}$, br$_{300}$, br$_{500}$, and br$_{1000}$, respectively. The results of these experiments are presented in Table \ref{tab:breton_mono}, and the specific changes in UAS during the training process for the \texttt{Breton-KEB} are illustrated in Figure \ref{fig:breton_mono-train}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%T7
\begin{table}[t]
\input{08table07.tex}
\hangcaption{UD scores on \texttt{Breton-KEB} obtained by different amounts of synthetic data . Rest(\%) indicates the average score of UPOS, UFeats, Lemma, and LAS in the UD scores. The best result in each group is in highlighted in \textbf{bold}.}
\label{tab:breton_mono}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F11
\begin{figure}[t]
\begin{center}
\includegraphics{32-1ia8f11.eps}
\end{center}
\hangcaption{(Left) UAS performance trends during training for the \texttt{Breton-KEB} test set. (Right) When the synthetic data quantity is set to 1000, the changes in UAS during the training process for the \texttt{Breton-KEB} test set are observed, both when using Unsupervised Augmentation on multiple languages simultaneously and when applying it to a single language only.}
\label{fig:breton_mono-train}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



For a visual comparison, we plotted the changes during the training process using the best-performing parameters in Figure \ref{fig:breton_mono-train}. The graph shows that, in a multilingual model scenario, whether synthetic data are produced for multiple languages simultaneously or only for a single language, the results are similar and do not exhibit significant changes, such as suppressing the decreasing UAS trend.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S6
\section{Conclusion and Future Work}
\label{sec:concl}

This study focuses on the phenomenon by which the dependency-parsing accuracy of UDify in low-resource language scenarios declines during the training process. We observed that maintaining the number of training epochs was essential to preserve the overall performance of the multilingual parser, as its accuracy on the entire test set continued to improve gradually with extended training. Recognizing the need to separately optimize the parsing capabilities of zero-shot languages within a multilingual parser, we propose a data augmentation method based on unsupervised learning, specifically tailored to enhance the final performance in zero-shot languages. The effectiveness of our approach in zero-shot languages was confirmed by multilingual experimental results, demonstrating significant improvements in dependency parsing accuracy without adversely affecting UDify's performance on other languages and tasks. Furthermore, we examined the impact of synthetic data quantity and the use of synthetic data for individual zero-shot languages. The experimental results indicate that increasing the quantity of synthetic data can effectively improve the UAS during training with UDify. However, using synthetic data exclusively for a single language does not significantly enhance its accuracy at the end of training.

In terms of future work, our research objectives include: 1) further investigating the potential positive correlation between the volume of unsupervised generated data included in the training set and the improvement in UDify's performance on low-resource languages and 2) exploring additional factors and considerations that may enhance UDify's performance in low-resource language scenarios.



% Start Acknowledgment
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\acknowledgment
This work builds upon the Introduction and Proposed Method sections of two papers accepted by \textit{Proceedings of the 37th Pacific Asia Conference on Language, Information and Computation} (PACLIC 2023) \cite{mao-etal-2023-improving} and \textit{Proceedings of the Joint Workshop on Multiword Expressions and Universal Dependencies} (MWE-UD 2024) \cite{mao-etal-2024-overcoming}. We have carefully extended the background section of this study. For the experiments in Section \ref{sec:exp}, we primarily use UD v2.13. Additionally, in Section \ref{sec:discuss}, we analyzed the impact of the synthetic data quantity on the experimental outcomes and a comparison of results between multilingual and monolingual applications. We would like to express our gratitude to the anonymous reviewers for their valuable comments and suggestions. This work was financially supported by JST SPRING, Grant Number JPMJSP2125. The author (Initial) would like to take this opportunity to thank the ``THERS Make New Standards Program for the Next Generation Researchers.''


% Start bibliography
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{jnlpbbl_1.7}
    \bibliography{08refs}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\appendix
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%A
\section{Inside--Outside Algorithm}
\label{sec:io}
The algorithm begins by calculating the inside probabilities from bottom to top and left to right across the CKY table, and then it computes the outside probabilities from top to bottom and right to left, utilizing the previously calculated inside probabilities.
\subparagraph{Inside} The inside probability of a complete-link reflects the likelihood of generating a word sequence  w$_{i,j}$ when there is a dependency relation between w$_{i}$ and w$_{j}$ as follows:
\begin{equation}
\begin{array}{c}
\alpha _{r}^{Link}(i,j)=\sum _{m=i}^{j-1}p(w_{i}\rightarrow w_{j})\alpha _{r}^{Seq}(i,m)\alpha _{r}^{Seq}(m+1,j)
\\[10pt]
\alpha _{l}^{Link}(i,j)=\sum _{m=i}^{j-1}p(w_{i}\leftarrow w_{j})\alpha _{r}^{Seq}(i,m)\alpha _{l}^{Seq}(m+1,j)
\end{array}
\end{equation}
The inside probability for a complete-sequence represents the likelihood that the word sequence w$_{i,j}$ originates from either $Seq_{l}(i,j)$ or $Seq_{r}(i,j)$ as follows: 
\begin{equation}
\begin{array}{c}
\alpha _{r}^{Seq}(i,j)=\sum _{m=i}^{j-1}\alpha _{r}^{Seq}(i,m)\alpha _{r}^{Link}(m,j)
\\[10pt]
\alpha _{l}^{Seq}(i,j)=\sum _{m=i+1}^{j}\alpha _{l}^{Link}(i,m)\alpha _{l}^{Seq}(m,j)
\end{array}
\end{equation}
\subparagraph{Outside}
The following probabilities measure the generation of word sequences w$_{1,i-1}$ and w$_{j+1,n}$ as words from $i$ to $j$ form a complete-sequence:
\clearpage
\begin{align}
\beta_{r}^{Seq}(i,j) &= \sum_{h=j+1}^{n} \beta_{r}^{Seq}(i,h)\alpha_{r}^{Link}(j,h)  \\ \notag
&\quad + \beta_{r}^{Link}(i,h)\alpha_{l}^{Seq}(j+1,h)p(w_{i}\rightarrow w_{h}) \\ 
&\quad  + \beta_{l}^{Link}(i,h)\alpha_{l}^{Seq}(j+1,h)p(w_{i}\leftarrow w_{h})  \notag
\\[10pt]
\beta _{l}^{Seq}(i,j) &= \sum _{v=1}^{i-1}\beta _{l}^{Seq}(v,j)\alpha _{l}^{Link}(v,i) \\ \notag
&\quad +\beta _{r}^{Link}(v,j)\alpha _{r}^{Seq}(v,i-1)p(w_{v}\rightarrow w_{j}) \\ 
&\quad +\beta _{l}^{Link}(v,j)\alpha _{r}^{Seq}(v,i-1)p(w_{v}\leftarrow w_{j})  \notag
\end{align}
These probabilities calculate the formation of words preceding $i$ and following $j$ in a sentence when complete-link$(i,j)$ results in w$_{i,j}$:
\begin{equation}
\begin{array}{c}
\beta _{r}^{Link}(i,j)=\sum _{v=1}^{i}\beta _{r}^{Seq}(v,j)\alpha _{r}^{Seq}(v,i)
\\[10pt]
\beta _{l}^{Link}(i,j)=\sum _{h=j}^{n}\beta _{l}^{Seq}(i,h)\alpha _{l}^{Seq}(j,h)
\end{array}
\end{equation}
\subparagraph{Probability Updates} 
The iterative construction process for complete-links and complete-sequences continues until the dependency structure of the entire sentence, denoted as $Link_{r}(1, n)$, is built. Here, $1$ and $n$ respectively signify the positions of the first and last words, marking the beginning and end of the sentence. At this point, the dependency probabilities for $w_{i}$ and $w_{j}$ within the sentence can be determined as follows:
\begin{equation}
\begin{array}{c}
P(w_{i}\rightarrow w_{j})=\dfrac{\alpha _{r}^{Link}(i,j)\beta _{r}^{Link}(i,j)}{P(Link_{r}(1, n))}
\\[10pt]
P(w_{i}\leftarrow w_{j})=\dfrac{\alpha _{l}^{Link}(i,j)\beta _{l}^{Alnk}(i,j)}{P(Link_{r}(1, n))}
\end{array}
\end{equation}
When the calculations for each sentence in a corpus are complete, the resulting dependency probabilities between word pair $(i, j)$  must be normalized as follows:
\begin{equation}
\begin{array}{c}
P^{'}(w_{i}\rightarrow w_{j})=\dfrac{P(w_{i}\rightarrow w_{j})}{\sum _{k\in vocab} P(w_{i}\rightarrow w_{k})}
\\[10pt]
P^{'}(w_{i}\leftarrow w_{j})=\dfrac{P(w_{i}\leftarrow w_{j})}{\sum _{k\in vocab} P(w_{i}\leftarrow w_{k})}
\end{array}
\end{equation}
Here, $vocab$ represents the whole vocabulary of the corpus. This ensures that the total sum of all potential link probabilities from word $i$ to every other word in the vocabulary, whether leftward or rightward, equals 1.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%B
\section{Similarity Analysis of Selected Low- and High-Resource Languages}
\label{sec:lang2vec}

Due to the inherent similarities in vocabulary, grammar, and phonetics among languages from the same family, and the enhancement of performance across various tasks through shared cross-lingual information during multilingual model training \cite{kong-etal-2021-multilingual,ustun-etal-2022-udapter,chronopoulou-etal-2023-language}, this section will analyze the similarity between the eight low-resource languages selected in Section \ref{sec:exp} and other languages for which training data are available.

To facilitate this analysis, we employ lang2vec \cite{littell2017uriel}, a powerful tool in natural language processing that offers standardized vectors. These vectors represent various language information types, providing detailed identifications for languages drawn from typological and phylogenetic databases. In our study, we utilize lang2vec to calculate the similarity between all languages involved in the training, and then visualize these similarities after dimensionality reduction with t-SNE \cite{JMLR:v9:vandermaaten08a}, as demonstrated in Figure \ref{fig:similarity}. Visual analysis reveals that each selected low-resource language, which enables potential cross-lingual learning opportunities for these languages.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F12
\begin{figure}[b]
\begin{center}
\includegraphics{32-1ia8f12.eps}
\end{center}
\hangcaption{Visualize the language vectors for the languages used in UD v2.13 experiments. ``$\blacksquare$'' represents the selected zero-shot languages, ``$\scalebox{1.1}{$+$}$'' represents the selected few-shot languages, and ``{\LARGE $\circ$}'' represents other languages involved in the training. Selected low-resource languages are marked in red with abbreviations following the ISO 639-3. Note that there are 65 languages with training data in UD v2.13, but not every language is represented in the lang2vec language vectors, so the figure does not include all languages with training data.}
\label{fig:similarity}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



Beyond linguistic features, the extent of similarities in the surface vocabulary between languages is crucial. UDify uses the mBERT tokenizer to process input sentences, thereby allowing sentences from various languages to share common tokens. To visually demonstrate the similarity in token usage among different languages, we use Breton, which employs the Latin alphabet, as an example. We calculated the token coverage rate between Breton and high-resource language treebanks by analyzing the proportion of shared tokens in their respective datasets. This method assessed their similarity, with results displayed in Figure \ref{fig:hot}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%F13
\begin{figure}[b]
\vspace{-10pt}
\begin{center}
\includegraphics{32-1ia8f13.eps}
\end{center}
\hangcaption{Bidirectional token coverage rates between train and test sets of different treebanks. Higher values indicate greater coverage and similarity between the datasets. The coverage is calculated using the formula $C(y,x) = \frac{|y \cap x|}{|y|}$, where $|y \cap x|$ represents the number of common tokens, and $|y|$ is the total number of tokens in the reference set.}
\label{fig:hot}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



The figure illustrates that Breton shares considerable similarity with other high-resource languages, which also use the Latin script. This similarity further supports the potential for cross-lingual learning. Additionally, the coverage rates of training sets from other high-resource language treebanks over their respective test sets range from 0.18 to 0.55, with an average of 0.31. Our constructed dataset $D^{Breton}_{gen}$ achieves a coverage rate of 0.39 over Breton-KEB$_{test}$, effectively enhancing the parsing accuracy for Breton, as demonstrated in our experimental results.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%C
\section{Experimental Results for LAS}
\label{sec:las}
We have placed the LAS results in Table \ref{tab:las_result}, and conducted significance tests. In the UD v2.13 version for the eight languages involved in the experiment, 9 out of 11 treebanks showed improvement in LAS, with three zero-shot languages achieving significant enhancements.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%T8
\begin{table}[b]
\input{08table08.tex}
\hangcaption{LAS (\%) for few- and zero-shot languages obtained using different methods on UD v2.3 and v2.13. The UDify(org) result for the v2.3 was reported in \protect\citeA{kondratyuk-straka-2019-75}. In the table, ``$\ddagger$'' indicates a significance level of $p \leq 0.01$  and ``$\dagger$'' indicates $p \leq 0.05$, both marks show instances where Unsup outperforms UDify(our).}
\label{tab:las_result}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



For the \texttt{Tagalog-TRG} in the UD v2.3, the dataset was quite small, encompassing only 55 sentences. In the UD v2.13, the size of the test set was expanded to 128 sentences, resulting in significant differences in the improvement of the LAS between the two versions.

Experimental results indicate that Unsupervised Augmentation not only enhances the parsing accuracy of dependency arcs but also improves the parsing accuracy of dependency relations. However, because our proposed method focuses on generating dependency arc data through unsupervised learning, it does not specifically optimize or enhance the data for dependency relations. Consequently, despite the overall improvement in accuracy, there remains room for improvement in the fine-grained identification of dependency relation types. Future research could consider developing more detailed data augmentation techniques, particularly targeted enhancements for dependency relation types, to further improve the model's parsing accuracy.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{biography}

\bioauthor[:]{Jiannan Mao}
{Jiannan Mao received his B.S. degree in Information Management and Systems from Gansu University of Political Science and Law, China, in 2019, and his M.S. degree in Intelligence Science and Engineering from Gifu University, Japan, in 2022. He is currently pursuing a Ph.D. at Gifu University. His research interests include natural language processing, with a focus on neural machine translation and dependency parsing.}

\bioauthor[:]{Chenchen Ding}
{Chenchen Ding is a senior researcher with the Advanced Translation Technology Laboratory, the National Institute of Information and Communications Technology (NICT), Japan, from 2022. He is also an associate professor with the Multilingual Natural Language Processing Laboratory, a collaborative laboratory between NICT and Nara Institute of Science and Technology, from 2024. He received an M.E. and Ph.D. from the University of Tsukuba in 2012 and 2015, respectively.}

\bioauthor[:]{Hour Kaing}
{Hour Kaing is a researcher at the Advanced Translation Technology Laboratory, National Institute of Information and Communications Technology (NICT), Japan, since 2022. He received his M.Sc. from the University of Grenoble 1, France, in 2014, and his Ph.D. from the NARA Institute of Science and Technology, Japan, in 2022.}

\bioauthor[:]{Hideki Tanaka}
{Hideki Tanaka is a Research Executive Director of the Advanced Translation Technology Laboratory of the National Institute of {\linebreak}Information and Communications Technology (NICT) in Japan. Before NICT, he was with the Science and Technology Research Laboratories of NHK and Advanced Telecommunications Research Institute International (ATR). His research interest lies in Natural Language Processing and Machine Learning. He received a BS., MS., and Ph.D. from Kyushu University in 1982, 1984, and 1995 respectively.}

\bioauthor[:]{Masao Utiyama}
{Masao Utiyama is the director with Advanced Translation Technology Laboratory, the National Institute of Information and Communi cations Technology, Japan from 2023. He completed his doctoral dissertation with the University of Tsukuba, in 1997. His main research field is machine translation.}

\bioauthor[:]{Tadahiro Matsumoto}
{Tadahiro Matsumoto is an associate professor of the faculty of engineering at Gifu University. He received his B.E., M.E. and Ph.D. degrees in engineering from Gifu University in 1985, 1987 and 2008, respectively. His research interests include natural language processing and machine translation of sign languages.}

\end{biography}

\biodate

\end{document}







