\documentclass[english]{jnlp_3.6}
\usepackage{jnlpbbl_2.2}
\usepackage[dvipdfmx]{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}
\usepackage{hangcaption_jnlp}
\usepackage{array}
%%%%\usepackage{udline}
%%%%\setulminsep{1.2ex}{0.2ex}
%%%%\let\underline=\ul
\allowdisplaybreaks


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% author's definition
%% normal packages
%%%%\usepackage[dvipdfmx]{xcolor}
%%%%\usepackage{nccmath}
%%%%\usepackage{amssymb}
%%%%\usepackage{amsfonts}
%%%%\usepackage{float}
%%%%\usepackage{booktabs}
\usepackage{multirow}
%%%%\usepackage{subfiles}
%%%%\usepackage{xcolor}
    \usepackage[dvipdfmx]{xcolor}
%%%%\usepackage{subcaption}
%%%%\usepackage{arydshln}  % dashed line
%%%%\usepackage{footmisc}
% my commands
%%%%\newcommand{\draft}[1]{\textcolor{blue}{#1}}
%%%%\newcommand{\xdraft}[1]{\color{blue}{#1}}
%%%%\newcommand{\fix}[1]{\textcolor{orange}{#1}}
%%%%\newcommand{\xfix}[1]{\color{orange}{#1}}
%%%%\newcommand{\reply}[1]{\textcolor{red}{#1}}
%%%%\newcommand{\xreply}{\color{red}}
%%%%\newcommand{\verify}[1]{\textcolor{green}{#1}}
%%%%\makeatletter
%%%%\def\blfootnote{\xdef\@thefnmark{}\@footnotetext}
%%%%\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Volume{30}
\Number{2}
\Month{June}
\Year{2023}
%%%%\Issuetitle{Special Issue: XXXXXXXX}

\received{2022}{9}{1}
\revised{2023}{1}{5}
\accepted{2023}{2}{13}

\setcounter{page}{456}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\esubject{General Paper}
\etitle{LATTE: Lattice ATTentive Encoding for Character-based Word Segmentation }
\eauthor{Thodsaporn Chay-intr\affiref{lrlab} \and Hidetaka Kamigaito\affiref{naist} \and Kotaro Funakoshi\affiref{lrlab-fac} \and \\
	Manabu Okumura\affiref{lrlab-fac}} 
\eabstract{%
A character sequence comprises at least one or more segmentation alternatives.
This can be considered segmentation ambiguity and may weaken segmentation 
performance in word segmentation. 
 Proper handling of such ambiguity lessens ambiguous decisions on word boundaries. Previous works have achieved remarkable segmentation performance and alleviated the ambiguity problem by incorporating the lattice, owing to its ability to capture segmentation alternatives, along with graph-based and pre-trained models. However, multiple granularity information, including character and word, in a lattice that encodes with such models may not be attentively exploited. To strengthen multi-granularity representations in a lattice, we propose the \textbf{L}attice \textbf{ATT}entive \textbf{E}ncoding (\textbf{LATTE}) method for character-based word segmentation. Our model employs the lattice structure to handle segmentation alternatives and utilizes graph neural networks along with an attention mechanism to attentively extract multi-granularity representation from the lattice for complementing character representations. Our experimental results demonstrated improvements in segmentation performance on the BCCWJ, CTB6, and BEST2010 datasets in three languages, particularly Japanese, Chinese, and Thai.
}
\ekeywords{Word Segmentation, Representation Learning}

\headauthor{Chay-intr et al.}
\headtitle{LATTE: Lattice ATTentive Encoding for Character-based Word Segmentation}

\affilabel{lrlab}{}{School of Engineering, Tokyo Institute of Technology}
\affilabel{naist}{}{Division of Information Science, Nara Institute of Science and Technology}
\affilabel{lrlab-fac}{}{Institute of Innovative Research, Tokyo Institute of Technology}


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

\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

Word segmentation is a fundamental task for an understanding of natural language. 
The task is to determine word boundaries from a running text; in other words, it segments a character sequence into word units.
Inadequate segmentation causes error propagation in consequential tasks, such as Named Entity Recognition (NER), part-of-speech (POS) tagging, and parsing \cite{qian-liu-2012-joint,zhang-yang-2018-chinese}.
This indicates the priority of word information.  

Although a word unit is the most natural concept for word segmentation, word-based models suffer from significant issues such as ambiguity, data sparsity, and out-of-vocabulary (OOV) \cite{li-etal-2019-word-segmentation}.
Unlike word-based models, character-based models, which use a character unit as an essential feature, may mitigate these obstacles because word-internal structures are more focused, having a stronger word-induction ability, particularly for the induction of new words \cite{sun-2010-word}.
Character-based word segmentation can be categorized as a sequential labelling task.
It aims to assign a word-boundary label to each character from a character sequence into a fine-grained tagging scheme, such as beginning, middle, end, and singleton (BMES), as shown in Figure~\ref{fig:bmes}.\footnote{We used MeCab (\url{https://taku910.github.io/mecab}), Jieaba (\url{https://github.com/fxsjy/jieba}), and Deepcut (\url{https://github.com/rkcosmos/deepcut}) to produce segmentation results for Japanese, Chinese, and Thai, respectively.}
Recent studies on Asian languages, including Japanese, Chinese, and Thai, have strongly relied on this character-based model \cite{higashiyama-etal-2019-incorporating,ke-etal-2021-pre,seeha-etal-2020-thailmcut}. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 1
\begin{figure}[b]
\begin{center}
\includegraphics{30-2ia7f1.pdf}
\end{center}
\hangcaption{Word segmentation as a sequence-labeling task for Japanese (top), Chinese (middle), and Thai (bottom), respectively, on BMES tagging scheme.}
\label{fig:bmes}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Naturally, a character sequence consists of at least one segmentation alternative \cite{dyer-etal-2008-generalizing}.
This ambiguity is considered a problem in word segmentation.
Previous studies have successfully incorporated various types of linguistic units such as words and subwords \cite{sennrich-etal-2016-neural}, on top of the character sequence to alleviate the ambiguity problem \cite{higashiyama-etal-2019-incorporating,yang-etal-2019-subword,tian-etal-2020-joint-chinese,chay-intr-etal-2021-character}.
In particular, \citeA{higashiyama-etal-2019-incorporating,tian-etal-2020-joint-chinese} applied the attention mechanism \cite{bahdanau-etal-2015-neural} to extract context features associated with a character and its corresponding knowledge, including words and syntactic structures.
These approaches are primarily based on a recurrent neural network (RNN) architecture that handles character sequences consecutively; however, linguistics is not rigidly sequential \cite{shen-etal-2018-ordered}.
Consequently, segmentation alternatives that can be produced from character sequences based on such linguistic units are not implicitly exploited.

Lattice, a graph-based representation, is employed to capture an arbitrary number of segmentation alternatives\footnote{In sequential labelling tasks, for example, word segmentation and NER, a node is conventionally used to represent either character or word information, and an edge is used to represent a transition between nodes.} as shown in Figure~\ref{fig:lattice-intro}; in particular, they represent ambiguous decisions on word boundaries in a multi-path lattice \cite{dyer-etal-2008-generalizing}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 2
\begin{figure}[b]
\begin{center}
\includegraphics{30-2ia7f2.pdf}
\end{center}
\hangcaption{Examples of lattice structures: single-path lattice (top) and multi-path lattice (bottom), where $x$ represents a character. \textbf{s} and \textbf{e} indicate initial and ending states, respectively. While the single-path lattice merely represents a character sequence $x_{0:3}$, the multi-path lattice additionally includes a group of possible character sequences (words), that is, $x_{1}x_{2}$ and $x_{2}x_{3}$ on top of the character sequence.}
\label{fig:lattice-intro}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Various types of neural network models, such as RNN-, Transformer-, and graph-models, have been successfully applied along with lattice structure in downstream tasks besides word segmentation, including NER, Machine Reading Comprehension (MRC), and text classification \cite{zhang-yang-2018-chinese,gui-etal-2019-lexicon,li-etal-2020-flat,lai-etal-2021-lattice}.

However, using pre-trained models (PTMs) with diverse methods to fine-tune word segmentation may significantly advance segmentation performance owing to their ability to provide prior knowledge \cite{he-etal-2017-effective-neural,seeha-etal-2020-thailmcut,ke-etal-2021-pre,maimaiti-etal-2021-segment}, particularly \citeA{ke-etal-2021-pre} that introduces multi-criteria pre-training with meta-learning \cite{chen-etal-2017-adversarial,finn-etal-2017-model-agnostic} to minimize discrepancies in pre-training tasks.
However, the performance of PTMs in fine-tuning word segmentation is limited by the scale and quality of the annotated corpus \cite{huang-etal-2021-lexicon-based}.
Moreover, multi-grained linguistic units, such as unseen character combinations and ambiguous contextual information from segmentation alternatives, may not be effectively exploited in fine-tuning methods. 

To handle such information from segmentation alternatives, graph neural networks (GNNs) are exploited for their ability to preserve relational and global structure information in a graph \cite{yao-etal-2018-graph}.
They have been utilized to encode fine-grained lattice with additional multi-level linguistic features, including word-boundary nodes, n-grams, and dependency syntactic trees \cite{huang-etal-2021-lexicon-based,tang-etal-2022-cws-hete}.
Although their works performed well in segmentation, they exhibited similar results to \citeA{huang-etal-2020-towards,ke-etal-2021-pre}. These empirical approaches rely on pre-training methods and almost a dozen datasets, likely owing to discrepancies between lattice and dataset segmentation alternatives. 
It indicates that an exponential number of segmentation alternatives in lattice encoded with GNN must be handled attentively.

In this study, we propose \textbf{L}attice \textbf{ATT}entive \textbf{E}ncoding (\textbf{LATTE}), a method to strengthen multi-granularity knowledge in the lattice that captures an exponential number of segmentation alternatives\footnote{We have conducted a preliminary experiment in Appendix~A to verify the benefits of using segmentation alternatives. Our experiment indicates that applying several segmentation alternatives in word segmentation is useful.} for character-based word segmentation.
In practice, we utilize lattice to capture segmentation alternatives from a character sequence and apply GNN simultaneously with the PTM BERT \cite{devlin-etal-2019-bert} and an attention mechanism to enable neural models to attentively extract contextual features from lattice for complementing character representations.

After empirically conducting experiments towards extracting essential representations from the use of lattice, we can state our contributions as follows.
\begin{itemize}
  \item We proposed a method to strengthen multi-granularity representations, including character and word, in lattice that captures an exponential number of segmentation alternatives for complementing character representations with an attention mechanism.
  \item Incorporating the bidirectional graph attention network (BiGAT) and attention mechanism into lattice, discrepancy in an arbitrary of segmentation alternatives captured in the lattice tends to decrease, leading to an improvement in the segmentation performance.
  \item Experimental results demonstrate that our model outperforms previous models on three datasets in three languages and yields superior performance compared with baseline methods in our analysis.
  \item Our code is publicly available.\footnote{\url{https://github.com/tchayintr/latte-ws}}
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related Work}

\vspace{-0.5\Cvs}
In this section, we present an overview of prior studies analyzing sequence labeling tasks, with a special focus on word segmentation. 


\vspace{-0.25\Cvs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Lattice in Sequence Labelling Tasks}

Lattice has been successfully incorporated in sequence labelling tasks such as word segmentation and NER owing to its ability to capture sequential paths. 
Different types of linguistic knowledge such as character, word, and subword, have been employed as a feature unit in lattice. 
\citeA{zhang-yang-2018-chinese} proposed the Lattice LSTM for Chinese NER and obtained superior performance over character-based and word-based models by incorporating lattices to control information flow, including characters and words, from the beginning of the sentence to the end.
  \citeA{yang-etal-2019-subword} successfully incorporated a subword unit into lattice for Chinese NER atop a character representation, using a model similar to that of \citeA{zhang-yang-2018-chinese}.

\citeA{li-etal-2020-flat} introduced FLAT, a transformer-based model for Chinese NER that applies word-character lattice and its position information as a flat structure.
Their model exhibited good performance and efficiency.
As with various abilities of PTMs, lattice has also been employed with coarse-granularity knowledge for pre-training a model \cite{lai-etal-2021-lattice}.
 Their approach yielded satisfying performance on essential downstream tasks such as text classification, MRC, and sequence labeling. 


\vspace{-0.25\Cvs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Graph Neural Networks in Word Segmentation}

Recently, GNNs have been explored and applied along with graph structures for tasks downstream of natural language processing (NLP).
Various GNN architectures have been proposed to address particular problems, such as graph convolutional network (GCN) \cite{kipf-etal-2016-semi}, graph attention network (GAT) \cite{velickovic-etal-2017-gat}, and heterogeneous graph attention network (HAN) \cite{wang-etal-2019-hete}.

To the best of our knowledge, only \citeA{huang-etal-2021-lexicon-based,tang-etal-2022-cws-hete} utilize GNN in word segmentation; however, most of the related studies focused on sequential labeling, particularly NER. 
\citeA{huang-etal-2021-lexicon-based} used GCN to aggregate word-character node along with its additional nodes, i.e., boundary-label node.
Their work achieved high segmentation performance and alleviated the problem of insufficient training by the small-scale annotated corpus.
\citeA{tang-etal-2022-cws-hete} achieved excellent results by proposing HGNSeg, a framework that employs multi-level features including character, word, n-grams, and dependency syntactic tree, using a heterogeneous graph neural network (HGNN).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Multi-Criteria Word Segmentation}

A PTM is generally built on large-scale corpora, for example, SIGHAN2005\footnote{\label{fn:sighan2015}\url{http://sighan.cs.uchicago.edu/bakeoff2005}} that include several corpora, to acquire prior knowledge.
However, these corpora are individually annotated in different segmentation criteria, that is, they exhibit multi-criteria segmentation. 
 \citeA{he-etal-2017-effective-neural} proposed a simple model that benefits from multi-criteria segmentation across multiple corpora by adding an artificial token at the start and end of a sentence to specify the target corpus -- a corpus-name token.
Although their method is remarkably simple, it yielded good segmentation performance.
Therefore, recent state-of-the-art word segmentation research adapted this mechanism with empirical methods to boost the segmentation performance \cite{huang-etal-2020-towards,huang-etal-2020-joint-multiple,ke-etal-2021-pre}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Attention Mechanism in Word Segmentation}

An attention mechanism \cite{bahdanau-etal-2015-neural} has been demonstrated to be effective for incorporating knowledge in word segmentation \cite{tian-etal-2020-joint-chinese}.
It computes an importance score between source and target information, particularly in character-based word segmentation, which produces context features correlated with a character and its corresponding knowledge.

\citeA{higashiyama-etal-2019-incorporating} proposed two attention-based composition functions: weighted average (WAVG) and weighted concatenation (WCON). These allow a model to alternate focus between a character and its candidate words.
Both functions summarize a relationship between a character with its candidate words as a summary vector.
Their work achieved state-of-the-art performance in BCCWJ, a well-known Japanese dataset, using the WCON function, which requires more computational resources than WAVG.
\citeA{tian-etal-2020-joint-chinese} proposed two-way attentions for joint Chinese word segmentation (CWS) and POS tagging that integrates two different linguistic information, including context features and linguistic knowledge, separately, for complementing a character representation. 
\citeA{tian-etal-2020-improving-chinese} introduced a framework to properly incorporate wordhood information built from n-grams using memory networks; it also exploits the attention mechanism using several popular encoder-decoder combinations.
These approaches, i.e., \citeA{tian-etal-2020-joint-chinese} and \citeA{tian-etal-2020-improving-chinese} performed well for numerous Chinese datasets.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 3
\begin{figure}[t]
\begin{center}
\includegraphics{30-2ia7f3.pdf}
\end{center}
\caption{Proposed model integrating lattice and GNN into character-based word segmentation model.}
\label{fig:main-model}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Approach}

In this section, 
\pagebreak
we provide an overview of our LATTE framework and then discuss it in detail.
Given a sentence $s$ with $n$ characters, that is, a character sequence $x_{1:n} = (x_{1}, x_{2}, \dots, x_ {n})$, the task is to assign a segmentation label $y_{i}$ based on the BMES tagging scheme $\mathcal{T} = \{\text{B, M, E, S}\}$ (beginning, middle, end, and singleton), which is a word-boundary label, to a character $x_{i}$.
Our approach, as illustrated in Figure~\ref{fig:main-model}, utilizes either BiLSTM- or BERT-encoder to obtain \textit{a contextualized character representation} $\textbf{h}_{i}$ for each character in a character sequence.
Consequently, we construct lattice $G$ that includes nodes $v$ built from possible words based on the character sequence along with their edges.
Subsequently, we encode lattice $G$ to obtain \textit{a multi-grained contextualized node representation} $\textbf{g}_{j}$ and a \textit{lattice-attention summary vector} $\textbf{a}_{i}$ using either BiLSTM- or BERT-encoder, GNN, and attention mechanism, sequentially.
The contextualized character representation is subsequently concatenated with the lattice-attention summary vector.
Finally, a conditional random field (CRF) layer is used to conditionally estimate the label sequence score for the character sequence.

We describe three major components, which perform the above operations in detail, including character encoding, lattice attentive encoding, and inference layer. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Character Encoding}

We employ either BiLSTM \cite{hochreiter-etal-1997-lstm,gers-etal-2000-learning} or BERT \cite{devlin-etal-2019-bert}, to transform a character sequence into contextualized character vectors.

\noindent\textbf{BiLSTM}: The character sequence $x_{1:n}$ is transformed into character embeddings $\textbf{e}_{1:n}^{c}$ of $d_{c}$-dimensional feature vector.
The character embedding matrix is defined as $E_{c} \in \mathbb{R}^{\lvert\mathcal{VOC}_{c}\rvert \times d_{c}}$, where $\mathcal{VOC}_{c}$ denotes the character vocabulary.
Pre-trained word vectors such as fastText \cite{bojanowski-etal-2017-enriching} can be used to initialize character embeddings $\textbf{e}_{1:n}^{c}$.
BiLSTM layers are used to obtain contextualized character vectors $\textbf{h}_{1:n}$ by subsequently encoding the character embeddings $\textbf{e}_{1:n}^{c}$.

A current contextualized character vector $\textbf{h}_{i}^{l}$ of the $l^{th}$ BiLSTM layer can be computed bidirectionally as follows:
\begin{equation}
    \begin{split}
        \textbf{h}^{l}_{i} &= \text{BiLSTM}(\textbf{h}^{l-1}_{1:n}, i) \\
        & \equiv \text{LSTM}_f(\textbf{h}^{l-1}_{1:n}, i) \\
        & \oplus \text{LSTM}_b(\textbf{h}^{l-1}_{n:1}, n-i+1), 
    \end{split}
    \label{eq:bilstm}
\end{equation}
where $\textbf{h}^{0}_{1:n} = \textbf{e}_{1:n}^{c}$, $f$ denotes the forward direction, $b$ denotes the backward direction, $\oplus$ denotes concatenation, and $\textbf{h}_{i} \in \mathbb{R}^{d_{r}}$ and $d_{r}$ are hyperparameters.

\noindent\textbf{BERT}: Apart from the character sequence $x_{1:n}$, special tokens, namely the $\textsc{[cls]}$ and $\textsc{[sep]}$ tokens, are augmented at the beginning $x_{0}$ and end $x_{n+1}$ of the character sequence, respectively.
The character sequence that includes the special tokens $x_{0:n+1}$ is converted into a one-hot representation of characters $\textbf{u}_{0:n+1}$.
Subsequently, the one-hot representation of characters $\textbf{u}_{0:n+1}$ are transformed into contextualized character vectors $\textbf{h}_{0:n+1}$ of $d_{\text{BERT}}$-dimensional feature vector.

A current contextualized character vector $\textbf{h}_{i}$ can be computed as follows: 
\begin{gather}
    \textbf{h}_{i}^{0} = W_{e}\textbf{u}_{i} + W_{p}[i],
    \label{eq:transformer_e} \\
    \textbf{h}_{i}^{l} = \text{Transformer}(\textbf{h}_{i}^{l-1}),
    \label{eq:transformer_h}
\end{gather}
where $l = \{1, 2, \dots, L\}$, which is the number of transformer layers \cite{vaswani-etal-2017-attention}. $W_{e}$ is the weight of the BERT-embedding layer while $W_{p}[i]$ is the positional encoding at the $i^{th}$ index. $u_{i}$ is one-hot representation of the $i^{th}$ character.
The BERT-embedding matrix is determined as $\mathbb{R}^{\lvert\mathcal{VOC}_{\text{BERT}}\rvert \times d_{\text{BERT}}}$, where $\mathcal{VOC}_{\text{BERT}}$ denotes the vocabulary in BERT.
Notably, a character $x$ can become $\textsc{[unk]}$ token assuming that the character does not exist in BERT vocabulary because the one-hot representation $u_{i}$ of the $i^{th}$ character is obtained from the BERT-embedding layer.

In addition, the summation of the last four layers is used to acquire the contextualized character vector $\textbf{h}_{i}$ as in \citeA{yang-2019-bert-cws}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Lattice Attentive Encoding}

We introduce the lattice attentive encoding method to attentively acquire multi-grained knowledge representations from an arbitrary number of segmentation alternatives, that is, lattice.\footnote{Please refer to Section~\ref{sec:lattice-construction} for implementation details concerning lattice construction.}

Let $G = \left(V, E\right)$ where $G$ is a directed acyclic graph (DAG) for a character sequence $x_{1:n}$, $V = \{v_{1}, \dots, v_{\lvert V \rvert}\}$ is the set of vertices or nodes, and  $E \subseteq \{V \times V\}$ is the set of edges.
Possible words and characters are searched based on the character sequence $x_{1:n}$ to build nodes $v_{1:m} = V$, where $m$ is the number of nodes (characters and words found) for lattice $G$.
Each node preserves a character sequence within length $k$.
Lattice $G$ consists of nodes corresponding to a character or word $w$ of length $1 < | w | \leq k$ and edges between nodes of adjacent characters/words in the sentence (the character sequence).
We introduce approaches based on either BiLSTM-encoder or BERT-encoder to encode lattice $G$ by initializing feature vectors for lattice nodes, that is, character-node $V^{c}$, word-node $V^{w}$, and special-node $V^{s}$.
\begin{gather*}
    V^{c} = \{v_{j} \in V \lvert \lvert v_{j} \lvert = 1 \land v_{j} \notin S\},
    \label{eq:v_char} \\
    V^{w} = \{v_{j} \in V \lvert \lvert v_{j} \lvert > 1 \land v_{j} \notin S\}, \\
    V^{s} = \{v_{j} \in V \lvert v_{j} \in S\},
\end{gather*}
where $\lvert v_{j} \rvert$ represents the length of characters in the $j^{th}$ node. $\mathcal{S}$ denotes the set of special tokens, that is, $\textsc{[cls]}$, $\textsc{[sep]}$, $\textsc{[bos]}$, $\textsc{[eos]}$, and $\textsc{[unk]}$.

\noindent\textbf{BiLSTM}:
Character-feature vectors $\textbf{v}^{c}$ of the character-node $V^{c}$ are initialized by the contextualized character vectors $\textbf{h}_{1:n}$ from the BiLSTM encoder in Equation~(\ref{eq:bilstm}).
Word-feature vectors $\textbf{v}^{w}$ of the word-node $V^{w}$ are initially generated from word embeddings $\textbf{e}_{1:m}^{w}$ of the $d_{w}$-dimensional feature vector.
The word embedding matrix is defined as $E_{w} \in \mathbb{R}^{\lvert\mathcal{VOC}_{w}\rvert \times d_{w}}$ where $\mathcal{VOC}_{w}$ denotes the word vocabulary.
In addition, special nodes $V^{s}$, that is the \textsc{[bos]} and \textsc{[eos]} nodes, are used to specify the beginning and end of the sentence, respectively.
These special-node features are obtained from the word embeddings matrix $E_{w}$.

\noindent\textbf{BERT}:
Character-feature vectors $\textbf{v}^{c}$ of the character-node $V^{c}$ are initialized by the contextualized character vectors $\textbf{h}_{1:n}$ from the BERT encoder in Equations~(\ref{eq:transformer_e}) and (\ref{eq:transformer_h}).
Word-feature vectors $\textbf{v}^{w}$ of the word-node $V^{w}$ are individually augmented with two special tokens, the $\textsc{[cls]}$ and $\textsc{[sep]}$ tokens, that are placed in the front and the back of each word-node, respectively.
Consequently, the augmented word nodes are individually encoded using the BERT-encoder, i.e., Equations~(\ref{eq:transformer_e}) and (\ref{eq:transformer_h}), to obtain contextualized node representations $\textbf{v}^{\prime} = \textbf{v}_{0:m+1}^{\prime}$, where $\{\textbf{v}^c$, $\textbf{v}^w\} \in \textbf{v}^{\prime}$.
As for special nodes $V^{s}$ in lattice $G$, $\textsc{[cls]}$ and $\textsc{[sep]}$, are used to initialize the start and end nodes for BERT, respectively.
These approaches eventually transform lattice $G$ into lattice $G^{\prime}$, where $G^{\prime} = (\textbf{v}^{\prime}, E)$.
Notably, a single-character word is treated similarly to a character in building a lattice and obtaining its representation from either BiLSTM or BERT.

Lattice $G^\prime$ is encoded by GAT to acquire multi-grained contextualized node representations $\textbf{g} = \textbf{g}_{1:m}$.
\[
    \textbf{g} = \text{GAT}\left(G^{\prime}, \theta_{G}\right),
\]
where $\theta_{G}$ denotes parameters of GAT such as the number of GAT layers and  the number of attention heads, among others.
The multi-grained contextualized node representation $\textbf{g}_{1:m}$ can be obtained from GAT\footnote{We used a bidirectional variant of GAT (BiGAT) as described in Section~\ref{sec:bigat} (Equation~(\ref{eq:bigat})) to obtain the multi-grained contextualized node representations $\textbf{g}$.} by estimating the importance score $u^{g}_{jk}$ of node $k$ to node $j$ and their attention weight $\alpha^{g}_{jk}$ as follows:
\begin{gather*}
    u^{g}_{jk} = \text{FFNN}(W_{g}\textbf{v}^{\prime}_{j} \oplus W_{g}\textbf{v}^{\prime}_{k}), \\
    \alpha^{g}_{jk} = \frac{\exp(\text{LeakyReLU}(u^{g}_{jk}))}{\sum_{l \in O_{j}}\exp(\text{LeakyReLU}(u^{g}_{jl}))},
\end{gather*}
where $j$ and $k$ are neighbouring nodes, and FFNN is a single-layer feed-forward neural network. $W_{g}$ and $O_{j}$ denote a shared weight matrix and the set of neighbourhoods of node $j$,\footnote{When BiGAT is used if $(v_{i}, v_{j}) \in E$ and $(v_j, v_i) \notin E$, then $v_j$ is the neighbourhood of $v_i$ (i.e., $v_j \in O_i$) but $v_i$ is not in the neighbourhood of $v_j$ (i.e., $v_i \notin O_j$).} respectively. 
Finally, the multi-head attention is employed to compute the multi-grained contextualized node representations $\textbf{g}_j$.
\[
    \textbf{g}_{j} = \sigma(\frac{1}{Q}\sum^{Q}_{q=1}\sum_{k \in O_{j}} \alpha^{g, q}_{jk} W_{g}^{q} \textbf{v}^{\prime}_{k}), 
\]
where $\textbf{g}_{j} \in \mathbb{R}^{d_{g}}$, $d_{g}$ is a hyperparameter, $Q$ indicates the number of attention-head, and $\sigma$ represents a nonlinear transformation, i.e., LeakyReLU.

To attentively project a proper representation out of multi-grained contextualized node representation $\textbf{g}$, we employed a WAVG from \citeA{higashiyama-etal-2019-incorporating}, which is an attention-based composition function.
This function summarizes the relationship for each character representation and its corresponding nodes by estimating a \textit{lattice-attention summary vector} $\textbf{a}_{i}$.
Specifically, a contextualized character representation $\textbf{h}_{i}$ originated from a character $x_{i}$ corresponding to either the hidden vector of the final BiLSTM or BERT layer, are involved with a set of nodes that includes the character $x_{i}$ in lattice $G^{\prime}$.
First, based on the contextualized character vector $\textbf{h}_{i}$ and its corresponding multi-grained contextualized node representations $\textbf{g}_{1:m}$ in lattice $G^{\prime}$, the node-importance score $u^{a}_{ij}$ and lattice-attention weight $\alpha^{a}_{ij}$ are estimated accordingly.
\begin{gather*}
    u^{a}_{ij} = \textbf{h}_i^{T}W_{a}\textbf{g}_{j}, \\
\alpha^{a}_{ij} = \frac{\delta_{ij}\exp(u_{ij})}{\sum_{k=1}^{m}\delta_{ik}\exp(u_{ik})},
\end{gather*}
where $W_{a} \in \mathbb{R}^{d_{c} \times d_{g}}$ denotes a trainable weight matrix and $\delta_{ij} \in \{0,1\}$ indicates whether character $x_{i}$ is included in node $v_{j}$.
The lattice-attention summary vector $\textbf{a}_{i}$ for character $x_{i}$ can be calculated as follows:
\[
    \textbf{a}_{i} = \text{WAVG}(x_{i}, \{v_{j}\}_{j=1}^{m}) {=} \sum_{j=1}^{m}\alpha^{a}_{ij}\textbf{g}_{j},
    \label{eq:wavg}
\]
where \{$v_{j}$\} is a node in lattice $G^{\prime}$ and $\textbf{a}_{i} \in \mathbb{R}^{d_{g}}$.
Finally, a multi-grained contextualized character vector $\textbf{z}_{i}$ is produced by concatenating a contextualized character vector $\textbf{h}$ with the lattice-attention summary vector $\textbf{a}_{i}$ as,
\[
    \textbf{z}_{i} = \textbf{h}_{i} \oplus \textbf{a}_{i},
\]
where $\textbf{z}_{i} \in \mathbb{R}^{d_{c} + d_{g}}$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Inference Layer}

Projection layers are used to transform the multi-grained contextualized character vectors into a vector $\textbf{s}_{i} \in \mathbb{R}^{\lvert\mathcal{T}\rvert}$.
Considering CRF \cite{lafferty-etal-2001-conditional} has been successfully applied for sequence-labeling related tasks \cite{collobert-etal-2011-natural}, we adopted it to estimate the probability of the optimal label sequence $y = y_{1:n}$ for the character sequence $x = x_{1:n}$ by measuring the correlations between adjacent labels as in previous studies \cite{higashiyama-etal-2019-incorporating,chay-intr-etal-2021-character}.
Let $A \in \mathbb{R}^{|\mathcal{T}| \times |\mathcal{T}|}$ be a transition matrix for correlations between adjacent labels, where $\mathcal{T}$ denotes a set of all possible label sequences, for instance, $\mathcal{T} = \{\text{B}, \text{M}, \text{E}, \text{S}\}$.
The $i^{th}$ multi-grained contextualized character vector $\textbf{z}_{i}$ can be transformed into an un-normalized label score $\textbf{s}_{i} \in \mathbb{R}^{|\mathcal{T}|}$ as follows:
\[
    \textbf{s}_i = W_{s}\textbf{z}_{i} + \textbf{b}_{s},
\]
where $W_{s} \in \mathbb{R}^{|\mathcal{T}| \times \left(d_{c} + d_{g}\right)}$ is a trainable parameter matrix, and $\textbf{b}_{s} \in \mathbb{R}^{|\mathcal{T}|}$ denotes a trainable bias vector. 

Given the input sequence $x_{1:n}$, the corresponding scores for the label sequence $y_{1:n}$ can be obtained as follows:
\[
    \text{score}(x, y) = \sum_{i=1}^{n}(A_{y_{i-1},{y_i}} + \textbf{s}_i[y_{i}]),
\]
where $s[y]$ represents the dimension of a vector $s$ according to a label $y$.
The probability of the label sequence can be obtained afterwards as follows:
\[
    P(y|x) = \frac{\text{score}(x,y)}{\sum_{y' \in T^{n}}\text{score}(x,y')},
\]
To obtain the optimal label sequence $y^{\star}$, we adopt the Viterbi algorithm to maximize the sentence score:
\[
    y^{\star} = \mathop{\arg\max}_{y \in T^{n}}\ \text{score}(x,y).
\]
Finally, we adopt the negative log-likelihood as our loss function and minimize it by backpropagation during the training process:
\[
    \mathcal{L}(x,y) = - \log P(y|x).
\]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Implementation Details}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Lattice Construction}\label{sec:lattice-construction}

Lattice can be  built on the basis of three formations: character-lattice (ChL), word-lattice (WL), and word-character-lattice (WChL), as shown in Figure~\ref{fig:lattice-seg-alt}.
  We constructed a word-character-lattice to comprehensively handle segmentation alternatives, leveraging character \linebreak
knowledge as a foundation for character-based word segmentation.
We built a lattice using all possible combinations according to a character sequence from training vocabulary, including the training set and external dictionary.
Special nodes, including start node (s), ending node (e), and dataset node\footnote{Dataset node represents a feature for multi-criteria pre-training method as described in Section~\ref{sec:mc-pretrain-method}.} (criterion token), are also included in the lattice.
$\textsc{[cls]}$ and $\textsc{[sep]}$ are used as the start and end nodes, respectively, for the BERT encoder while $\textsc{[bos]}$ and $\textsc{[eos]}$ are used as the start and end nodes, respectively, for the BiLSTM encoder.
The Aho--Corasick algorithm \cite{aho-etal-1975-efficient-string} is applied to obtain the substrings of the character sequence while reducing the time complexity in lattice construction to linear time complexity. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 4
\begin{figure}[t]
\begin{center}
\includegraphics{30-2ia7f4.pdf}
\end{center}
\hangcaption{Examples of lattice formation: character-lattice (top), word-lattice (middle), and word-character-lattice (bottom), that can be built for our model.}
\label{fig:lattice-seg-alt}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Furthermore, we introduce \textit{dynamic-lattice construction} (DyL) by adapting concepts from Bagging, i.e., bootstrap aggregating \cite{breiman-1994-bagging-predictors} and Dropout \cite{srivastava-etal-2014-dropout} to minimize generalization error and overfitting.
Edges in the lattice are randomly deleted during the training step.
This means the lattice for each epoch in relation to the same character sequence can be different.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Bidirectional Graph Neural Networks}\label{sec:bigat}

As for a concept of BiLSTM architecture in sequence labelling  that considers both forward and backward information \cite{huang-2015-etal-bidirectional}, it can also be applied to a graph structure and GNN architecture.
\citeA{gui-etal-2019-lexicon} additionally built a transpose-graph from a directed graph where the graph comprises the same set of nodes but all edges in the graph are reversed. 
They concatenated the forward- and backward-state as the final result for node classification.
In this study, we build direction-aware GNN layers based on the direction information, i.e., forward-GNN and backward-GNN layers, as shown in Figure~\ref{fig:lattice-direction}.
Parameters in GNN layers such as direction-dependent and trainable parameters are separately exploited according to the direction.
\begin{equation}
    \text{BiGNN} = \text{GNN}_{f}(G_{f}, \theta_{f}) \oplus \text{GNN}_{b}(G_{b}, \theta_{b}), 
    \label{eq:bignn}
\end{equation}
where $G$ denotes lattice, $\theta_{ \boldsymbol{\cdot}}$ denotes the parameters for GNN layers, and $\oplus$ denotes concatenation. 
$f$ and $b$ represent forward- and backward-direction, respectively.
A variant of GNNs such as GAT can also be applied to Equation~(\ref{eq:bignn}).
\begin{equation}
    \text{BiGAT} = \text{GAT}_{f}(G_{f}, \theta_{f}) \oplus \text{GAT}_{b}(G_{b}, \theta_{b}).
    \label{eq:bigat}
\end{equation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 5
\begin{figure}[t]
\begin{center}
\includegraphics{30-2ia7f5.pdf}
\end{center}
\hangcaption{Examples of direction-aware lattice, including forward-lattice (top) and backward-lattice (bottom).}
\label{fig:lattice-direction}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Multi-criteria Pre-training Method}\label{sec:mc-pretrain-method}

The special tokens $\textsc{[cls]}$ and $\textsc{[sep]}$ are augmented at the beginning and end of each input sequence, respectively.
We adopted a multi-criteria pre-training method from \citeA{ke-etal-2021-pre} by adding criterion tokens after the $\textsc{[cls]}$ token to allow a model in learning criterion-dependent and criterion-independent segmentation knowledge among corpora.
The criterion tokens, including criterion-dependent tokens such as $\textsc{[ctb6]}$ and $\textsc{[bccwj]}$, and an undefined-criterion token, that is, $\textsc{[unc]}$ token, were used in this study.
Notably, the $\textsc{[unc]}$ token was used similarly as in \citeA{ke-etal-2021-pre}.
Each input sequence is augmented with the criterion-dependent token; however, it is randomly replaced with the undefined-criterion token based on a hyperparameter.

We performed the multi-criteria pre-training method on BERT architecture, namely MC-BERT.
Because the multi-criteria learning method requires more than one corpus, we additionally included accessible corpora to produce MC-BERT.
Moreover, we also applied our proposed method, that is, LATTE, as a component.\footnote{We modified the MC-BERT pre-training method from \citeA{ke-etal-2021-pre} by including LATTE (building lattice from training data and applying BiGAT to pre-train representations in MC-BERT) as a component. We released our implementation at \url{https://github.com/tchayintr/latte-ptm-ws} in pre-training MC-BERT rather than pre-training conventional MC-BERT proposed by \citeA{ke-etal-2021-pre} to pre-train MC-BERT.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experiment}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental Settings}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Dataset} 
\label{dataset}

 Three datasets in three languages, i.e., Japanese, Chinese, and Thai, were used to evaluate our model.
Table~\ref{tab:dataset} shows the statistics of the datasets, including sentences, words, vocabulary, and characters.
(1) \textbf{BCCWJ}:\footnote{\url{https://clrd.ninjal.ac.jp/bccwj/en}} A Japanese word-segmented corpus that is primarily used in word segmentation experiments. 
(2) \textbf{CTB6}:\footnote{\url{https://catalog.ldc.upenn.edu/LDC2007T36}} A Chinese Treebank corpus that is one of the most popular benchmark datasets for Chinese word segmentation.
(3) \textbf{BEST2010}:\footnote{\url{https://thailang.nectec.or.th}} A large-scale Thai word-segmented corpus in four domains, which include article, encyclopaedia, news, and novel. 
While we followed the official data splits for both BCCWJ and CTB6 as in the previous works \cite{higashiyama-etal-2019-incorporating,huang-etal-2021-lexicon-based}, we used the same data splits for BEST2010 as \citeA{chay-intr-etal-2021-character}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 1
\begin{table}[b]
\vspace{-0.5\Cvs}
\input{07table01.tex}%
\hangcaption{Data sizes, in terms of the number of sentences (S), words (W), vocabulary (V), and characters (Ch).}
\label{tab:dataset}
\vspace{-1.5\Cvs}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{External Dictionary and Pre-trained Word Vectors}

Because lattice is built on the basis of vocabulary (characters and words), to enable the coverage of vocabulary in building lattice, we also included an external dictionary on top of the datasets, where only the training data was used, for each language individually.
\textbf{Japanese}: UniDic\footnote{\url{https://clrd.ninjal.ac.jp/unidic}} and IPADic\footnote{\url{https://taku910.github.io/mecab}} for MeCab.
\textbf{Chinese}: BLCU balanced corpus,\footnote{\url{http://bcc.blcu.edu.cn}} Train data from SIGHAN2005, and Jieba.\footnote{\url{https://github.com/fxsjy/jieba}}
\textbf{Thai}: HSE Thai Corpus\footnote{\url{http://web-corpora.net/ThaiCorpus}} and LEXiTRON.\footnote{\url{https://lexitron.nectec.or.th}}
Additionally, to initialize robust word embeddings for BiLSTM-encoder, we employed fastText to produce a feature for characters and nodes, as well as freezing it during the training step.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Pre-training Models}

Owing to various  existing PTMs, we selected PTMs for use on the basis of their originality and accessibility.
(1) \textbf{Japanese BERT}:\footnote{\url{https://huggingface.co/cl-tohoku/bert-base-japanese-char-v2}} We chose character-level Japanese BERT to perform on the Japanese dataset owing to its accessibility and consistency with the character-based approach.
(2) \textbf{Chinese BERT}:\footnote{\url{https://huggingface.co/bert-base-chinese}} This pre-trained model has been effectively used in neural models on Chinese datasets. 
Thus, we selected it for use in our experiment on the Chinese dataset.
(3) \textbf{Multilingual BERT}:\footnote{\url{https://huggingface.co/bert-base-multilingual-cased}} We selected this pre-trained model to use on the Thai dataset because we could not find any Thai pre-trained model that is similar to Japanese and Chinese pre-trained models in terms of originality and accessibility.
All models are $\text{BERT}_{\text{base}}$ models.

To build MC-BERT for Japanese, Chinese, and Thai, we additionally collected two, six, and four accessible datasets, respectively, and appended these additional datasets on top of the main datasets, i.e., BCCWJ, CTB6, and BEST2010.
Two Japanese datasets, UD Japanese treebank,\footnote{\url{https://github.com/UniversalDependencies/UD_Japanese-GSD}} and Kyoto University Text Corpus\footnote{\url{https://github.com/ku-nlp/KyotoCorpus}} were added to produce Japanese MC-BERT.
%%%%Six Chinese datasets, four corpora from SIGHAN2005\footref{fn:sighan2015} (AS, CITYU, MSRA, and PKU), 
    Six Chinese datasets, four corpora from SIGHAN2005$^{5}$ (AS, CITYU, MSRA, and PKU), 
SXU from SIGHAN2008, and CNC, were appended to build Chinese MC-BERT.
Both SXU and CNC corpora are obtained from public repositories.\footnote{\url{https://github.com/hankcs/multi-criteria-cws}}
All traditional Chinese corpora, such as AS and CITYU, are converted into simplified Chinese.
Four Thai datasets, LST20,\footnote{\url{https://aiat.or.th/lst20-corpus/}} TNHC,\footnote{\url{https://attapol.github.io/tlc}} VISTEC, \footnote{\url{https://github.com/mrpeerat/OSKut/tree/main/VISTEC-TP-TH-2021}} and WS160,\footnote{\url{https://github.com/PyThaiNLP/wisesight-sentiment/tree/master/word-tokenization}} were used to construct the Thai MC-BERT.
The number of datasets used to construct MC-BERT for each language was three for Japanese, seven for Chinese, and five for Thai.
For accessibility, we perform the pre-training methods for Chinese MC-BERT on seven datasets rather than nine compared with the previous work \cite{ke-etal-2021-pre}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Hyperparameters}

We used the essential hyperparameters for models as shown in Table~\ref{tab:hyp}.
The AdamW optimizer \cite{loshchilov-etal-2017-decoupled} was used to optimize the model parameters.
 Every model was trained for 20 epochs. We selected the best model to perform on the test set based on the validation process by word-level $\text{F}_{1}$ evaluation.
Because several types of neural networks were utilized in the proposed method, the initial learning rate was set separately by the neural network type, that is, 2e-5 for BERT, 1e-3 for GNN, and 1e-3 for others.
Learning rate decay is also applied and was set to 0.9.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 2
\begin{table}[b]
\input{07table02.tex}%
\hangcaption{Common hyperparameters and BERT hyperparameters for reproduced models and our proposed model (top and middle), and essential hyperparameters for our proposed model (bottom).}
\label{tab:hyp}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

To select an optimal maximum word length for building nodes in lattice among the datasets equitably, we reversely adapted the 80/20 rule also known as the Pareto principle.\footnote{\url{https://en.wikipedia.org/wiki/Pareto_principle}}
We used only words within the optimal maximum word length in relation to the cumulative frequency of word length at 80\% to build nodes.
%%%%As shown in Figures~\ref{fig:cumulative-bccwj}, \ref{fig:cumulative-ctb6}, and \ref{fig:cumulative-best2010}, 
    As shown in Figures~\ref{fig:fig}a, \ref{fig:fig}b, and \ref{fig:fig}c, 
we selected the maximum word length of four, four, and twelve for the Japanese, Chinese, and Thai datasets, respectively.
We set the $\textsc{[unc]}$ token rate as 0.1; practically, 10\% of sentences among the corpora are augmented with the undefined-criterion token rather than the criterion-dependent tokens.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 6
\begin{figure}[t]
\begin{center}
\includegraphics{30-2ia7f6.pdf}
\end{center}
\hangcaption{Word length and its cumulative frequency on three datasets. \textcolor{red}{Red} line indicates the cumulative frequency at 80\%. \textcolor{blue}{Blue} dashed line denotes selected \textit{maximum node length} hyperparameter.}
\label{fig:fig}
\end{figure}
%%%%\label{fig:cumulative-bccwj}
%%%%\label{fig:cumulative-ctb6}
%%%%\label{fig:cumulative-best2010}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Compared Models}

We evaluated the following models:

\begin{itemize}
    \item\textbf{Baselines}:
        Character-based models with different architectures, including BiLSTM-CRF, BiLSTM-WAVG-CRF \cite{higashiyama-etal-2019-incorporating}, BERT-CRF, and BERT-MC-CRF \linebreak
(Multi-criteria BERT).
    \item\textbf{LATTE w/ BiLSTM} (BiLSTM-BiGAT-CRF):
        Our proposed model integrating a lattice attentive encoder with BiLSTM-encoder to generate features.
    \item\textbf{LATTE} (BERT-MC-BiGAT-CRF):
        Our proposed model integrating a lattice attentive encoder and using BERT-encoder, which is fine-tuned by multi-criteria BERT, to extract features, as shown in Figure~\ref{fig:main-model}.
    \item\textbf{Others}: Popular Well-known word-segmentation models \cite{neubig-etal-2011-pointwise,kitagawa-komachi-2018-long,qiu-etal-2020-concise,tian-etal-2020-improving-chinese,huang-etal-2020-towards,maimaiti-etal-2021-segment,huang-etal-2021-lexicon-based,tang-etal-2022-cws-hete,treeratpituk-2017-tws-lstm,lapjaturapit-etal-2018-multi,chormai-etal-2019-attacut,kittinaradorn-etal-2019-deepcut,seeha-etal-2020-thailmcut} and state-of-the-art word-segmentation models \cite{higashiyama-etal-2019-incorporating,ke-etal-2021-pre,chay-intr-etal-2021-character}.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Evaluation Metrics}

We selected evaluation metrics to evaluate models per language based on previous research.
Word-level-$\text{F}_{1}$ score has been used to evaluate recent Japanese word-segmentation models \linebreak
\cite{higashiyama-etal-2019-incorporating}.
However, two types of evaluation metrics, word-level-$\text{F}_{1}$ and OOV-recall score, have been used to evaluate models on Chinese word-segmentation task \cite{ke-etal-2021-pre}.
%%%%Owing to the similarity of vocabulary length in both languages as shown in Figures~\ref{fig:cumulative-bccwj} and \ref{fig:cumulative-ctb6}, 
    Owing to the similarity of vocabulary length in both languages as shown in Figures~\ref{fig:fig}a and \ref{fig:fig}b, 
we used word-level-$\text{F}_{1}$ and OOV-recall score to evaluate models on Japanese and Chinese datasets.
Previous works on Thai word-segmentation task interchangeably evaluated on the character-level-$\text{F}_{1}$ and word-level-$\text{F}_{1}$ \cite{limkonchotiwat-etal-2021-handling,chay-intr-etal-2021-character}.
Thus, we chose character-level-$\text{F}_{1}$ and word-level-$\text{F}_{1}$ to evaluate models on Thai dataset.
We evaluated word-level-$\text{F}_{1}$ and OOV-recall score as in \citeA{qiu-etal-2020-concise}, and we followed character-level-$\text{F}_{1}$ evaluation from \citeA{limkonchotiwat-etal-2021-handling,chay-intr-etal-2021-character}.
\begin{gather*}
    \textbf{Precision}_{\text{char}} = \frac{\#\text{char}_{\text{gold(B)} \cap \text{pred(B)}}}{\#\text{char}_{\text{pred(B)}}}, \\[1ex]
    \textbf{Recall}_{\text{char}} = \frac{\#\text{char}_{\text{gold(B)} \cap \text{pred(B)}}}{\#\text{char}_{\text{gold(B)}}}, \\[1ex]
    \textbf{F1}_{\text{char}} = 2 \times \frac{\textbf{Precision}_{\text{char}} \times \textbf{Recall}_{\text{char}}}{\textbf{Precision}_{\text{char}} + \textbf{Recall}_{\text{char}}},
\end{gather*}
where \#char represents the number of characters in a sequence.
gold(B) and pred(B) denote gold boundary characters from a dataset and predicted boundary characters from a model, respectively.
\begin{gather*}
    \textbf{Precision}_{\text{word}} = \frac{\#\text{word}_{\text{gold} \cap \text{pred}}}{\#\text{word}_{\text{pred}}}, \\[1ex]
    \textbf{Recall}_{\text{word}} = \frac{\#\text{word}_{\text{gold} \cap \text{pred}}}{\#\text{word}_{\text{gold}}}, \\[1ex]
     \textbf{F1}_{\text{word}} = 2 \times \frac{\textbf{Precision}_{\text{word}} \times \textbf{Recall}_{\text{word}}}{\textbf{Precision}_{\text{word}} + \textbf{Recall}_{\text{word}}},
\end{gather*}
where \#word represents the number of words found in a sequence. 
gold and pred denote a set of gold words from a dataset and a set of predicted words from a model, respectively.

$\textbf{Recall}_{\text{oov}}$ represents the recalls for OOV words that exist in inference phrase while not existing in the training phase.It can be computed as follows:  
\[
     \textbf{Recall}_{\text{oov}} = \frac{\#\text{word}_{\text{infer} \cap (\text{gold} \setminus \text{train}})}{\#\text{word}_{\text{gold} \setminus \text{train}}},
\]
where infer, train, and gold denote a set of words produced in the inference phase, a set of words from the Train set, and a set of gold words from a dataset, respectively.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Results and Analysis}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Main Results}

Tables~\ref{tab:bccwj-result}, \ref{tab:ctb6-result}, and \ref{tab:best2010-result} show comparisons of previous works, baselines, and our proposed model on the three datasets, that is, BCCWJ, CTB6, and BEST2010, respectively.
  The results indicate that LATTE outperformed previous works and Baselines in every selected evaluation metric.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 3
\begin{table}[b]
\input{07table03.tex}%
\hangcaption{Comparison among Others, Baselines, and our proposed model, on BCCWJ dataset. The best score for each metric is indicated in \textbf{bold}. $\text{F}_{\text{word}}$ and $\text{R}_{\text{OOV}}$ denote the word-level-$\text{F}_{1}$ and OOV-recall scores, respectively. $\sigma$ represents the population standard deviation. The scores were obtained from the mean of two runs.}
\label{tab:bccwj-result}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 4
\begin{table}[t]
\input{07table04.tex}%
\hangcaption{Comparison among Others, Baselines, and our proposed model, on the CTB6 dataset. The best score for each metric is indicated in \textbf{bold}. $\text{F}_{\text{word}}$ and $\text{R}_{\text{OOV}}$ denote the Word-level-$\text{F}_{1}$ and OOV-recall scores, respectively. $\sigma$ represents the population standard deviation. The scores were obtained from the mean of two runs.}
\label{tab:ctb6-result}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 5
\begin{table}[t]
\input{07table05.tex}%
\hangcaption{Comparison among Others, Baselines, and our proposed model, on the BEST2010 dataset. The best score for each metric is indicated in \textbf{bold}. $\text{F}_{\text{char}}$ and $\text{F}_{\text{word}}$ denote the character-level-$\text{F}_{1}$ and word-level-$\text{F}_{1}$ scores, respectively. $\sigma$ represents the population standard deviation. The scores were obtained from the mean of two runs.}
\label{tab:best2010-result}
\vspace{-0.75\Cvs}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

LATTE could outperform \citeA{higashiyama-etal-2019-incorporating} which integrates either the WAVG function or WCON function to estimate the relationships between a character and its candidate words.
While incorporating the WCON function with the word-segmentation model in \citeA{higashiyama-etal-2019-incorporating} achieves superior segmentation performance to the WAVG function, which is an average-based function, it is computationally intensive owing to its concatenation mechanism that logically consumes more memory and computational time.
\pagebreak
Although LATTE is incorporated with the WAVG function only, it outperformed their model that integrates the WCON function.
 Comparing our model to a similar lattice-based work \cite{huang-etal-2021-lexicon-based}, our method surpasses it through various approaches to handle, encode, and interact between a character sequence and a lattice.
For BEST2010, superb segmentation performance has been obtained on \citeA{chay-intr-etal-2021-character} by incorporating multiple attentions from word and character-cluster information, which is an exclusive Thai writing system knowledge, with a WCON function.
Although LATTE obtained comparable results on word-level-$\text{F}_{1}$ with \citeA{chay-intr-etal-2021-character}, our model outperformed it on character-level-$\text{F}_{1}$ using WAVG function which requires fewer computational resources.
In addition, while LATTE w/BiLSTM could not surpass BERT-based models, it outperformed previous works and baselines, particularly the BiLSTM-based model, on three datasets in each evaluation metric.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Segmentation Performance with Additional Datasets}

We tested our model when some unknown datasets were not included in pre-training MC-BERT.
The task is to additionally fine-tune MC-BERT with an additional dataset based on its training set along with a validation set and evaluate the fine-tuned model on the testing set.
We augmented the undefined-criterion token \textsc{[unc]} after the $\textsc{[cls]}$ token to each sentence, where the representation of the \textsc{[unc]} token was transferred from MC-BERT.
The criterion-dependent tokens, such as \textsc{[ctb6]}, were not used in this test.
We conducted this experiment on two datasets: $\text{UD}_{\text{JA}}$ (Japanese) and $\text{UD}_{\text{ZH}}$\footnote{\url{https://github.com/UniversalDependencies/UD_Chinese-GSDSimp}} (Chinese). 
Note that we pulled $\text{UD}_{\text{JA}}$ out from Japanese MC-BERT pre-training to conduct this test.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 6
\begin{table}[b]
\input{07table06.tex}%
\hangcaption{Results of segmentation performance on additional datasets, including $\text{UD}_{\text{JA}}$ (Japanese) and $\text{UD}_{\text{ZH}}$ (Chinese).}
\label{tab:unseen-dataset-result}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Table~\ref{tab:unseen-dataset-result} shows the results of segmentation performance on two additional datasets.
The results showed that our proposed model outperformed the baselines on both datasets.
MC-BERT could help in improving segmentation performance on $\text{UD}_{\text{JA}}$ and $\text{UD}_{\text{ZH}}$.
Moreover, our proposed model could further enhance segmentation performance when MC-BERT was employed while using LATTE as a component.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Ablation Study}

LATTE achieved superior segmentation performance beyond previous works by integrating three major components: BiGNN, MC-BERT, and DyL.
To analyze the effect of these components on our proposed model, we conducted an ablation study based on LATTE incorporated with BERT-encoder on the three datasets.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 7
\begin{table}[b]
\input{07table07.tex}%
\hangcaption{Results of Ablation Study on BCCWJ, CTB6, and BEST2010. MC-BERT denotes BERT with multi-criteria learning and DyL represents dynamic lattice construction. All models are the proposed model incorporated with BERT-encoder. {\checkmark} indicates whether the feature is incorporated into the word-segmentation model, and the best scores are indicated in \textbf{bold}.}
\label{tab:ablation-result}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Table~\ref{tab:ablation-result} shows the results of segmentation performance on the ablation study.
The results demonstrated that combining BiGNN, MC-BERT, and DyL advanced segmentation performance.
However, employing MC-BERT on the BCCWJ corpus did not improve segmentation performance as CTB6 and BEST2010.
Incorporating BiGNN into our model consistently improved segmentation performance on all dataset.
However, LATTE that incorporated BiGAT, MC-BERT, and DyL did not enhance segmentation performance on BCCWJ compared with LATTE that applied BiGAT and DyL; however, it could perform well on CTB6 and BEST2010.
The DyL helped boost segmentation performance on BCCWJ and CTB6; however, it lessened segmentation performance on BEST2010, which includes longer character sequences than BCCWJ and CTB6, and led to lower performance.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Case Study: Segmentation Results}

To show whether specific cases from segmentation results\footnote{A collection of segmentation results are publicly available at \url{https://github.com/tchayintr/latte-ws}} were improved or worsened by incorporating LATTE, we conducted a comparison of segmentation results between BERT-MC-CRF and LATTE. 
We selected two Chinese test samples from the CTB6 dataset to be our case study because Chinese word segmentation is the most competitive among the three languages, i.e., Chinese, Japanese, and Thai.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 7
\begin{figure}[b]
\begin{center}
\includegraphics{30-2ia7f7.pdf}
\end{center}
\hangcaption{Examples of segmentation results between BERT-MC-CRF and LATTE. Ground-truth segmentation result is indicated as ``Reference'' and incorrect segmentation results are in \textcolor{red}{red}. While LATTE completely segments the correct results, BERT-MC-CRF produces incorrect results.}
\label{fig:case-study-zh-win}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 8
\begin{figure}[b]
\begin{center}
\includegraphics{30-2ia7f8.pdf}
\end{center}
\hangcaption{Examples of segmentation results between BERT-MC-CRF and LATTE. Ground-truth segmentation result is indicated as ``Reference'' and incorrect segmentation results are in \textcolor{red}{red}. While LATTE produces incorrect results, BERT-MC-CRF completely segments the correct results.}
\label{fig:case-study-zh-lose}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Figures~\ref{fig:case-study-zh-win} and \ref{fig:case-study-zh-lose} show segmentation results between BERT-MC-CRF and the proposed \linebreak
LATTE, respectively.
Figure~\ref{fig:case-study-zh-win} illustrates a case where LATTE outperforms BERT-MC-CRF by segmenting ``省政府 (Provincial Government)'' as ``省 (Provincial) and 政府 (Government)'' while BERT-MC-CRF preserves the ``省政府'' as it is.
By considering a word category (part-of-speech) of ``省 (Provincial)'' and ``政府 (Government)'', that is, adjective and noun, respectively, it is the smallest piece of words that can be divided, where the word category is still preserved. 
  This indicates a tendency towards less ambiguity in terms of word units by segmenting them correctly into small units.
In case both words are combined into a noun phrase that produces from BERT-MC-CRF, it gathers more complex structures.
  
However, Figure~\ref{fig:case-study-zh-lose} shows other results where LATTE could not outperform BERT-MC-CRF by segmenting ``危机重重 (crisis-ridden)'' as ``危机 (crisis)'' and ``重重 (ridden)'' while BERT-MC-CRF preserves ``危机重重 (crisis-ridden)'' as it is.
``危机重重 (crisis-ridden)'' is a Chinese idiom, where its character sequence is fixed to present certain meanings with more complex structures.
Regardless of the idiom structures, it is also legitimate to segment ``危机重重 (crisis-ridden)'' into ``危机 (crisis)'' and ``重重 (ridden)'' because both words contain meanings by themselves.
Therefore, although LATTE could not recognize the idiom, it could produce results according to the meanings.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 9
\begin{figure}[b]
\begin{center}
\includegraphics{30-2ia7f9.pdf}
\end{center}
\hangcaption{Examples of segmentation results between BERT-MC-CRF and LATTE. Ground-truth segmentation result is indicated as ``Reference'' and incorrect segmentation results are in \textcolor{red}{red}. LATTE segments better results than BERT-MC-CRF.}
\label{fig:case-study-ja-win}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Additionally, we selected segmentation results from BCCWJ and BEST2010 to illustrate the cases where LATTE outperformed BERT-MC-CRF as shown in Figures~\ref{fig:case-study-ja-win} and~\ref{fig:case-study-th-win}.

In terms of meaning, the segmentation results from BCCWJ are not significantly different.
The major difference between BERT-MC-CRF and LATTE lies in the connection between the character ``着'' and ``せ''.
LATTE produced the segmentation result where ``着'' and ``せ'' are combined as ``着せ (dress up)'', which forms the verb ``着せる (to dress)'' by considering the word category.
BERT-MC-CRF segmented the sentence differently, by combining ``着'' with {\linebreak}``古'' into ``古着'' rather than forming the verb ``着せる (to dress)''.
This leaves ``せ'' by itself, which is grammatically incorrect and does not convey the intended meaning of the verb ``着せる (to dress)'', resulting in a grammatically incorrect sentence.
Although both BERT-MC-CRF and LATTE separately segmented ``お'', which is an honorific prefix, from ``古 (old)'', the overall meaning is not changed.
However, this results in a less natural expression, as the honorific {\linebreak}``お'' and the character ``古'' are not commonly separated when referring to second-hand clothes in Japanese. 
However, the segmentation results from BEST2010 could represent two different meanings.
While LATTE could accurately segment the sentence, thus producing the correct meaning, the segmentation result from BERT-MC-CRF represents the sentence with a completely different meaning. 
Ultimately, LATTE significantly outperformed BERT-MC-CRF based on this sample.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 10
\begin{figure}[t]
\begin{center}
\includegraphics{30-2ia7f10.pdf}
\end{center}
\hangcaption{Examples of segmentation results between BERT-MC-CRF and LATTE. Ground-truth segmentation result is indicated as ``Reference'' and incorrect segmentation results are in \textcolor{red}{red}. While LATTE completely segments the correct results, BERT-MC-CRF produces incorrect results.}
\label{fig:case-study-th-win}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}

In this study, we proposed a lattice attentive encoding method for character-based word segmentation that uses lattice to handle segmentation alternatives along with GNNs and attention mechanisms.
Our proposed model attentively extracts multi-granularity representations from such a lattice for complementing character representations.
Experimental results showed that our method could improve segmentation performance on three popular datasets: BCCWJ, CTB6, and BEST2010.
Moreover, pre-training a model with LATTE as a component enhanced segmentation performance as well.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{jnlpbbl_1.7}
%%%%\bibliography{07refs}
    \input{IA0300_07chay-intr_bbl.tex}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\appendix

\subsection*{A. Upper-bound Score Test}\label{apx:upperbound-test}

We hypothesised that segmentation results produced from a model may not be the best results; however, it generalizes the model to minimize the segmentation errors.
The test is performed by training a character-based BiLSTM-CRF model to predict a label sequence $\hat{y}$ for each input sequence up to $\textit{r}$ segmentation results, i.e. $\hat{\textbf{Y}} = \{\hat{y}^{1}, \hat{y}^{2}, \dots, \hat{y}^{r}\}$, where $\hat{\textbf{Y}}$ denotes a set of label sequences $\hat{y}$, and $r=\{1,2,4,8,16\}$.
The CRF layer is used along with the Viterbi algorithm to produce $\text{top-}\textit{r}$ segmentation results.
To evaluate segmentation performance in this test, we aggregated scores, including character-level-$\text{F}_{1}$ score and OOV-recall score, according to the best segmentation result that yields the highest score among the top $r$ results. 
For example, in case of $r=8$, the top $8$ possible segmented sentences $\hat{\textbf{Y}} = \{\hat{y}^{1}, \hat{y}^{2}, \dots, \hat{y}^{r}\}$ for a sentence will be produced from the model. 
Subsequently, each segmentation result $\hat{y}^{i} \in \{\hat{y}^{1}, \hat{y}^{2}, \dots, \hat{y}^{8}\}$ will be evaluated with the reference sentence $y$; the highest scores from among the top-eight sentences will be used to aggregate the scores.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 8
\begin{table}[b]
\input{07table08.tex}%
\hangcaption{Comparison of segmentation performance in upper-bound score test on the basis of character-based BiLSTM architecture (Baseline). The scores are aggregated from the best results in top-$r$ segmentation results. The numbers in parentheses represent the differences from the model where $r=1$.}
\label{tab:top-r-result}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Table~\ref{tab:top-r-result} shows a comparison of top-$r$ segmentation performance.
The results show the same tendency on three datasets; therefore, segmentation performance of the model depends on the increase of $r$.
Comparison with the segmentation performance from top-$r$ segmentation results where $r>1$ demonstrates that the best results ($r=1$) are not the truly best segmentation results.
In addition, however, the model where $r=1$ implicitly and generally considers such top-$r$ information in principle to produce the results.
On the other hand, by increasing the $r$ value to produce more segmentation results from the model to be used for the evaluation, it could obtain superior segmentation performance.
Accordingly, this indicates that if top-$r$ information is handled explicitly and properly, it could lead to the improvement of segmentation performance as in LATTE method.



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

\bioauthor[:]{Thodsaporn Chay-intr}{%
T. Chay-intr received his M. Eng. from Sirindhorn Institute of Technology, Thailand, and is currently a doctoral student at Tokyo Institute of Technology, Japan. His research interests include natural language processing, particularly text classification; computer linguistics; and text mining.
}

\bioauthor[:]{Hidetaka Kamigaito}{%
H. Kamigaito received his Dr.~Eng.\ from Tokyo Institute of Technology, Japan, and is currently an associate professor at Nara Institute of Science and Technology, Japan. His research interests include natural language processing with a specific focus on document-level text processing and knowledge graph completion.
}

\bioauthor[:]{Kotaro Funakoshi}{%
K. Funakoshi received his Dr.~Eng.\ from Tokyo Institute of Technology, Japan, and is currently an associate professor at Institute of Innovative Research, Tokyo Institute of Technology. Formerly, he was with Honda Research Institute Japan Co., Ltd. from 2006 and served a program-specific associate professor of the Cooperative Intelligence Joint Chair at Kyoto University from 2017. His research interests include natural language processing, particularly computational linguistics; multi-modal dialogue systems; and human-machine interaction.
}

\bioauthor[:]{Manabu Okumura}{%
M. Okumura received his Dr.~Eng.\ from Tokyo Institute of Technology, Japan, and is currently a professor at Institute of Innovative Research, Tokyo Institute of Technology. His research interests include natural language processing, particularly text summarising; computer-assisted language learning; sentiment analysis; and text mining.
}
\end{biography}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\biodate





\end{document}

