text:
\section{Introduction}

As a fundamental task in syntactic analysis, dependent parsing has received constant research attention \citep{dozat2016deep,  dozat-etal-2017-stanfords, strubell-etal-2018-linguistically,ma2018stack, li2019self}. It offers useful information to a range of downstream tasks, such as relation extraction \citep{gamallo2012dependency, miwa-bansal-2016-end, guo-etal-2019-attention, zhang-etal-2018-graph} and semantic parsing \citep{hajic-etal-2009-conll,poon-domingos-2009-unsupervised,sun-etal-2018-semantic}. As shown in Figure \ref{fig:end2endparse}, the goal of syntactic dependency parsing is to build a dependency tree for a given sentence, where each arc represents a head-dependent relationship between two words.

Traditionally, Chinese dependency parsing takes word segmentation and POS tagging as preprocessing steps \citep{zhou2000block, ma2012fourth, zhangmcdonald2014enforcing}.
The pipeline method, however, suffers from error propagation as incorrect word boundaries and POS tags lead to decreases in parsing performance.
End-to-end models, which take character sequences as input and jointly perform the three task, have been investigated to address the problem \citep{hatori2012incremental, zhang2013chinese, kurita2017neural, li2018neural}.

\input{fig/end2endparse.tex}

While most existing work takes a transition-based method \citep{ Nivre:2008:CL,zhangnivre2011transition,bohnet:2010:coling,chen2014dep,andor:2016:global},
we consider a graph-based method for end-to-end parsing, adopting the bi-affine framework of  \citet{dozat2016deep}.
In particular,
our model takes a character sequence as input, using a sequence representation network to find the  representation of each character. Word segmentation, POS-tagging and parsing are performed jointly over the character representation by multi-task learning.
More specifically, both word segmentation and POS-tagging are performed as character sequence labeling tasks, where a local classifier is built on top of each character representation. Dependency parsing follows a bi-affine scoring function between characters, so that the head of each character can be found.
Both bidirectional long short-term memory networks (BiLSTMs) and self attention networks (SANs;  \citeauthor{vaswani2017attention}, \citeyear{vaswani2017attention}) are considered as the encoder network.

One salient difference of neural graph-based parsing, as compared with its transition-based counterpart, is that the representation of input is calculated first, before local outputs such as sequence labels and bi-word relation tags are predicted. In contrast, a transition-based parser builds a joint output structure using a state-transition process, the representation of which contains mixed input and output information. As a result, one advantage of neural graph-based parsing is that the representation calculation can be more parallelizable, allowing faster running speed. However, for our joint parser, since word segmentation and dependency parsing are performed jointly on characters, word information cannot be used directly to benefit parser disambiguation.

To solve this issue, we consider integrating lexicon knowledge for enriching the character sequence representation, by jointly encoding the characters and all the words in the input that match a dictionary. To this end, we use lattice LSTM \citep{zhang-etal-2019-lattice} for extending a BiLSTM character encoder, and make a novel extension to the Transformer architecture for the SAN counterpart. The latter runs over a order of magnitude faster than the former thanks to strong parallelization.
In particular, the Transformer \citep{vaswani2017attention} architecture is adopted, which can be regarded as a graph-attentional neural network \citep{velikovi2017graph} with a fully-connected character graph. We integrate information from lexicon words into this graph attentional neural network by taking them as additional vertices in the graph, adding word-character edges and word-word edges to the input graph. The standard self-attention function is further extended into a novel combination of  a semantic channel and a structural channel,
the former using semantic similarity for weight calculation, and the latter taking paths in the graph into consideration.

Experiments on three Chinese parsing datasets show that
integrating lexicon word information is useful for improving character-level end-to-end parsing.
Our graph-based parser, enriched with word-level features, outperforms all existing methods in all the datasets, achieving the best results on segmentation, POS tagging and parsing in the literature.  To our knowledge, we are the first to investigate an end-to-end Chinese parser exploiting lexicon knowledge.

\section{Related Work}
\paragraph{End-to-End Chinese Parsing.}
\citet{hatori2012incremental} pioneer research on the joint model of  word segmentation, POS tagging, and dependency parsing for Chinese using transition-based methods.  \citet{zhang2014character} exploit the manually annotated  intra-character dependencies. \citet{zhang2015randomized} consider transition-based joint word segmentation, POS tagging and dependency reranking using randomized greedy inference. \citet{kurita2017neural} first investigate transition-based models for joint Chinese lexical and syntactic analysis with neural models. We investigate the same task, but our end-to-end models are built on graph-based parsers.

Very recently, \citet{yan2019unified} consider using a BiLSTM and BERT encoder for representing character sequences for end-to-end Chinese parsing. Our work is similar in being a graph-based parser, but differs in three aspects. First, we investigate the effectiveness of word information for the task by considering a novel graph attention network with semantic and structural channels. Second, we compare BiLSTM encoding with Transformer encoding with BERT. Third, while they consider joint segmentation and parsing, we consider joint segmentation, POS-tagging and parsing.

\paragraph{Word-character Lattice Neural Networks.}
\citet{chen2017dag} and \citet{zhang-yang-2018-chinese} use lattice LSTM to deal with mixed word and character inputs.
\citet{ding-etal-2019-neural} use graph convolutional networks \citep{kipf2016semi} for entity lattice inputs. Their lattice requires named entities and their entity types as inputs. More closely related to our work, \citet{sperber-etal-2019-self} adapt Transformer \citep{vaswani2017attention} for lattice inputs. Our models are different from them in three aspects. First, their lattice is built from compressing speech hypothesis, while we build the lattice by lexicon matching. Second, there is no concept of word in their models, while we explicitly model word inputs and exploit pretrained word embeddings. Third, we differentiate semantic and structural information according to the edge types in lattice by taking inspirations from graph Transformers \citep{velikovi2017graph,zhu-etal-2019-modeling}. Existing work can be regarded as a variant of our models, which only captures semantic features.

\section{Task Description}

Formally, as shown in Figure \ref{fig:end2endparse}, given a sequence of characters $s=c_1, ..., c_n$,
the target of end-to-end parsing is to obtain a dependency tree $T=(V,E)$ together with
segmented word sequence $s_w={w_1, ..., w_k}$ and a
POS tag sequence $s_t=t_1, ..., t_k$,
where $c_i$ is the $i$-th Chinese character in the sentence, $w_j$ is the $j$-th segmented word and $t_j$ is the POS tag for $w_j$.
The node set $V$ contains all segmented words and an additional root dummy node.
The arc set $E=\left \{ (i_k, j_k) \right \}$, where the tuple $(i_k, j_k)$ represents $w_{i_k}$ is the head of $w_{j_k}$.

\section{Decoding and Training}

For word segmentation and POS tagging, we use a joint tag scheme $t_{ws}\_t_{pos}$, where $t_{ws} \in $ $ \left \{ B, M, E, S \right \}$ denotes segmentation labels \citep{xue2003chinese}, and $t_{pos}$ denotes POS. The probability $\textit{segpos}_{ij}$ for the joint tag
$\left \{t_{ws}\_t_{pos} \right \}_i$ is:
\begin{flalign*}
\mathbf{t}_i=\text{MLP}_t(\mathbf{h}_{c_i});\
\textit{posseg}_{ij}=\text{softmax}_j\left ( \mathbf{W_t} \mathbf{t}_i \right )
\end{flalign*}

For dependency parsing, following \citet{dozat2016deep}, we use two representations of each character, which can distinguish between dependents and heads in dependency relations. In particular, for the $i$-th character $c_i$, a head representation $\mathbf{h}_{c_i}$ and a dependent representation $\mathbf{d}_{c_i}$ are obtained through two multi-layered perceptrons:
\begin{flalign*}
\mathbf{h}_i=\text{MLP}_h(\mathbf{h}_{c_i});\ \mathbf{d}_i=\text{MLP}_d(\mathbf{h}_{c_i})
\end{flalign*}

The dependency confidence score $dep_{ij}$ of the dependency relation $j\rightarrow i$ is obtained by using a biaffine transformation:
\begin{flalign*}
dep_{ij}=\text{softmax}_i\left ( \mathbf{h}_j^T\mathbf{A}\mathbf{d}_i + \mathbf{b}_1^T\mathbf{h}_j + \mathbf{b}_2^T\mathbf{d}_i \right )
\end{flalign*}
where $\mathbf{A}$, $\mathbf{b}_1$ and $\mathbf{b}_2$ are the model parameters.

\textbf{Training} A negative log-likelihood loss value $\mathcal{L}$ is computed on each character $c_i$ over the head probability $dep_{ij}$ locally and accumulated along the sentence,
\begin{equation*}
    \mathcal{L} = -\sum_{i=1}^{N} \left (  \log \textit{dep}_{i,head_i} + \log \textit{segpos}_{i,tag_{i}}\right),
\end{equation*}
where $head_i$ and $tag_i$ denotes the head index and the joint segmentation-POS tag of the $i$-th character, respectively.
During training, we minimize $\mathcal{L}$ to train the model parameters.

\textbf{Decoding}
Hierarchical decoding is used for dependency parsing:
we first perform decoding to parse the internal structure of a word and find the root character, and then perform decoding for all root character for all root character in the sentence to obtain a word-level parsing results.
Given the confidence score of all potential dependency arcs $dep_{ij}$, the decoding process can be formulated as a max spanning tree (MST) problem. Specifically, we use the Tarjan implementation \citep{tarjan1977finding} of the Chu-Liu-Edmonds algorithm \citep{chu1965shortest, edmonds1967optimum} to find the MST derivation.

\section{LSTM Encoder}

\begin{figure*}[!tb]
  \centering
  \includegraphics[width=1\linewidth]{fig/biaffine4.pdf}
  \caption{End-to-end Chinese parsing. The input is a part of the sentence in Figure \ref{fig:end2endparse} with character index $i \in [7, 11]$. The output sequences are the gold labels accordingly. The output structure for the entire sentence is shown in Figure \ref{fig:end2endparse}. }
      \label{fig:biaffine}
\end{figure*}

The overall framework of our method is shown in Figure \ref{fig:biaffine}.
In particular, we adopt graph-based parsing and use biaffine transformation for dependency arc prediction. For word segmentation and POS tagging,  a  CRF is used for predicting label sequences.
We use recurrent neural networks for input representations, following \citet{dozat2016deep}, \citet{kiperwasser2016simple} and \citet{wang-chang-2016-graph}. Specifically, we obtain character embeddings through BERT:
$\mathbf{e}_{c_i}=\text{emb}(c_i)$.

A multi-layer bi-directional LSTM structure is used to calculate the character sequence representations. In particular, the initial character embedding $\mathbf{e}_{c_i}$ are denoted as $\mathbf{h}^0_{c_i}$. Subsequently, for the $k$-th layer, $\mathbf{h}^{k}_{c_1}, ..., \mathbf{h}^{k}_{c_n}$  are calculated from $\mathbf{h}^{k-1}_{c_1}, ..., \mathbf{h}^{k-1}_{c_n}$ as follows:
 \begin{flalign*}
\overrightarrow{\mathbf{h}^k_i}, \overrightarrow{\mathbf{c}^k_i} &= \overrightarrow{\textit{LSTM}^k} (\overrightarrow{\mathbf{h}^{k-1}_i}, \overrightarrow{\mathbf{h}^k_{i-1}}, \overrightarrow{\mathbf{c}^k_{i-1}}),
\end{flalign*}
 \begin{flalign*}
\overleftarrow{\mathbf{h}^k_i},
\overleftarrow{\mathbf{c}^k_i} &= \overleftarrow{\textit{LSTM}^k} (\overleftarrow{\mathbf{h}^{k-1}_i}, \overleftarrow{\mathbf{h}^k_{i+1}}, \overleftarrow{\mathbf{c}^k_{i+1}}), \\
\mathbf{h}^k_i &= \langle \overleftarrow{\mathbf{h}^k_i}, \overrightarrow{\mathbf{h}^k_i} \rangle, \ \ \ \
\mathbf{c}^k_i = \langle \overleftarrow{\mathbf{c}^k_i}, \overrightarrow{\mathbf{c}^k_i} \rangle,
\end{flalign*}
where $\textit{LSTM}^k$ is the LSTM network for the $k$-th layer,  $\mathbf{h}^k_i$ and $\mathbf{c}^k_i$ are the hidden output and the internal cell state of the $i$-th character. $\rightarrow$ and  $\leftarrow$ indicate the left and right composition directions of LSTM networks respectively. The final representation of the $i$-th character $c_i$ is the output hidden vector of the $K$-th layer: $\mathbf{h}_{c_i}=\mathbf{h}^K_{c_i}$.

We follow the lattice LSTM extension \citep{zhang-etal-2019-lattice} for integrating word features from a dictionary. Formally, the hidden states are calculated as follows:

 \begin{flalign*}
\overrightarrow{\mathbf{h}^k_i}, \overrightarrow{\mathbf{c}^k_i} &= \overrightarrow{\textit{LatticeLSTM}^k} (\overrightarrow{\mathbf{h}^{k-1}_i}, \overrightarrow{\mathbf{h}^k_{i-1}}, \overrightarrow{\mathbf{c}^k_{i-1}}, \mathbf{E}_{w_{\cdot i}} ),\\
\overleftarrow{\mathbf{h}^k_i}, \overleftarrow{\mathbf{c}^k_i} &= \overleftarrow{\textit{LatticeLSTM}^k} (\overleftarrow{\mathbf{h}^{k-1}_i}, \overleftarrow{\mathbf{h}^k_{i+1}}, \overleftarrow{\mathbf{c}^k_{i+1}}, \mathbf{E}_{w_{i \cdot}} ),
\end{flalign*}
 \begin{flalign*}
\mathbf{h}^k_i &= \langle \overleftarrow{\mathbf{h}^k_i}, \overrightarrow{\mathbf{h}^k_i} \rangle, \ \ \ \
\mathbf{c}^k_i = \langle \overleftarrow{\mathbf{c}^k_i}, \overrightarrow{\mathbf{c}^k_i} \rangle,
\end{flalign*}
where $\textit{LatticeLSTM}^k$ is the Lattice-LSTM network for the $k$-th layer. $\mathbf{E}_{w_{\cdot i}}$ and $\mathbf{E}_{w_{i \cdot}}$ are the sets of word embeddings for words ending and starting with the $i$-th character, respectively.

\section{Word-Character GAT Encoder}
\label{sec:sub:latticeatt}

We extend the standard transformer \citep{vaswani2017attention}. As shown in Figure \ref{fig:biaffine}, the word-character GAT encoder is used as one alternative encoder for the LSTM encoder component in the earlier section to model a word-char mixed sequence. The model consists of a multi-layer encoder. Each layer consists of two sub-layers, including a multi-head self-attention sublayer and a position-wise feed-forward network sublayer. Layer normalization and residual network are used for each sublayer.
Formally, denote the input character-word mixed sequence as $t=[c_1, ..., c_n, w_1, ..., w_k]$,
where $c_1, ..., c_n$ represent the input character sequence and $w_1, ..., w_k$ represent the words in the input that match a lexicon. For the convenience of notation, we represent each token in the input as $t_i (i \in [1, n+k])$, regardless of whether it is a character ($i<n+1$) or word ($i>n$).

\textbf{Position Embedding} We use static position embeddings to encode the input following \citet{vaswani2017attention}.
$e^p(i)$ represents the position embedding for the $i$-th position.
We inject position embedding to characters and word input as follows:
\begin{flalign*}
\mathbf{e}'_{c_i}=\mathbf{e}_{c_i}+\mathbf{e}^p(i);
\mathbf{e}'_{w_i}=\mathbf{e}'_{w_i} + \mathbf{e}^p(b_{w_i}).
\end{flalign*}

We take the position of the first character $b_{w_i}$ of the word $w_i$ in the original sentence to represent the position of the word.

\begin{table}[!t]
\small
\centering
\begin{tabular}{ccll}
\specialrule{.05em}{0pt} {.65ex}
\textbf{Block} & & \textbf{Relation} & \textbf{Example}    \\
\midrule
\multirow{5}{*}{\shortstack{A\\ (char)}} & 1 & word $\rightarrow$ char & - \\
& 2 & char $\leftarrow$ word &  成果(result):华(China)   \\
& 3 & char $\rightarrow$ char &  访(visit):华(China)   \\
& 4 & char $\leftarrow$ char &   成(become):华(China)  \\
& 5 & self-to-self & 华(China):华(China)   \\
\midrule
\multirow{3}{*}{\shortstack{B\\ (word)}}& 6 & char $\rightarrow$ word & 华(China):成果(result) \\
& 7 & word $\leftarrow$ char &  表(table):成果(result)   \\
& 8 & self-to-self & 成果(result):成果(result)   \\
\specialrule{.05em}{.4ex}{0pt}
\end{tabular}
\caption{Relation definitions of word-character interaction. Relation expression ``A $\rightarrow$ B'' indicates a relation from A (left) to B (right). Block A (to a character) and Block B (to a word) take the character ``华(China)'' and word ``成果(Result)'' as examples, respectively.}
\label{tab:rels}
\end{table}

\textbf{Information Integration}
For the convenience of describing both word and characters, we unify them as nodes in a graph represented using a graph attention network \cite{velikovi2017graph}.
We define two channels for capturing semantic and structural features in the graph, respectively.
In particular, the semantic channel captures interaction between characters and words in the sentence without differentiating their types, and the structural channel adds the type and relative position when considering node interaction. The detailed definitions are given later. As shown in Figure \ref{fig:biaffine}, a graph neural network works by iteratively updating the representation of each node through layers. In each layer, each node receives information from its neighbors in the input graph structure so that its representation vector can be updated. The naive transformer structure \citep{vaswani2017attention} can be viewed as a graph attentional neural network, where each input character is a node and there is a graph edge between every two nodes.

Formally, denote the input of each layer as ${x}=[x_1, ..., x_n, {x}_{n+1}, ..., {x}_{n+k}]$, where $x_i$ is the input representation of $c_i$ for $1\leq i\leq n$ and  $x_i$ is the input representation of $w_{i-n}$ for $n+1\leq i\leq n+k$.
The input for the first encoder layer is the embedding sequence
$[\mathbf{e}'_{c_1}, ..., \mathbf{e}'_{c_n}, \mathbf{e}'_{w_{1}}, ..., \mathbf{e}'_{w_{k}}]$.
For the $m$-th attention head, the similarity between two tokens  $\mathbf{x}_i$ and  $\mathbf{x}_j$ can be calculated by a vector inner product:
\begin{flalign*}
s^{sem,m}_{ji}=\left ( \mathbf{x}_i\mathbf{W}^{K,m} \right ) \cdot \left ( \mathbf{x}_j\mathbf{W}^{Q,m} \right ),
\end{flalign*}
where $\mathbf{W}^{K, m}$ and $\mathbf{W}^{Q,m}$ are the model parameters for the $m$-th attention head.

The similarity $s^{sem,m}_{ji}$ can control how much information $t_i$ can receive from $t_j$.
The key in the above information exchange process is a character-word mixed self-attention mechanism, where a weight score $s^{sem}_{ji}$  is calculated by the similarity of token $t_j$ and $t_i$. To this end, $s^{sem}_{ji}$ can be regarded as a \textbf{semantic channel}.

We further introduce a \textbf{structural channel} by taking  path structure into consideration.
As shown in Table 1, we differentiate edges according to both the word/character difference and the relative position, resulting in 7 types of edges. For example, ``word $\rightarrow$ character'' represents an edge from a word to a character at its right. ``self-to-self'' represents a self-loop over a character or a word.

We make use of rich edge types by defining structural channels.
Each token $t_i$ can receive the information from all the input according to the edges defined in Table \ref{tab:rels}.
Taking  the character ``华(China)'' as an example, it can receive information from ``成果(result)'', ``访(visit)'', ``成(become)'', ``华(China)'' through the edges $r_2$, $r_3$, $r_4$ and $r_5$ in the table, respectively. In addition, we define a special edge ``others'' for each other relation type so that ``华(China)'' can receive information from all characters and words.

Formally, denote the relation from node $o$ to node $i$ as $r_{ji}$.
We can obtain the embedding of each relation $r_{ji}$ through an  embedding lookup table:
\begin{equation*}
\mathbf{e}_{ji} = \text{emb}(r_{ji}).
\end{equation*}

We further calculate contextualized relation embeddings $\mathbf{e}_{oi}^{ct}$, which is sensitive to the  representations of the two nodes $\mathbf{x}_i$ and $\mathbf{x}_o$ for $r_{oi}$:
\begin{flalign*}
\mathbf{e}^{ct, m}_{ji} = \sigma (\mathbf{e}_{{ji}}\mathbf{W}^{E,m} + \mathbf{e}_{x_i}\mathbf{W}^{S,m} + \mathbf{e}_{x_j}\mathbf{W}^{T,m}),
\end{flalign*}
where $\mathbf{W}^{E,m}$, $\mathbf{W}^{S,m}$ and $\mathbf{W}^{T,m}$ are parameters.

The structural similarity score is calculated as:
\begin{flalign*}
s^{str,m}_{ji} = \mathbf{w}^m \cdot \mathbf{e}^{ct,m}_{ji},
\end{flalign*}
where vector  $\mathbf{w}^m$ is a model parameter for the $m$-th attention head.

The final similarity score $s_{oi}$ between token $j \in [1, n+k] $ and token $i \in [1, n+k]$  is the combined scores from semantic channels and structural channels:
\begin{flalign*}
s_{ji}^m &= s^{sem,m}_{ji} + s^{str,m}_{ji}.
\end{flalign*}

The hidden state of $t_i$ for the $m$-th head is:
\begin{flalign*}
\mathbf{h}_i^m=\sum \textup{softmax}_j (\mathbf{s}_{ji}^{m}) \cdot \left ( \mathbf{x}_j\mathbf{W}^{V,m} \right ),
\end{flalign*}
where $\mathbf{x}_j$ is the input of token $t_j$ for the current encoder layer, and $\mathbf{W}^{V,m}$ is a model parameter.

\iftrue
The final output $\mathbf{h}_i$ is the concatenation of outputs from all the $M$ attention heads:
\begin{flalign*}
\mathbf{h}_i = [\mathbf{h}_i^1, ..., \mathbf{h}_i^M].
\end{flalign*}
\fi

\input{4-2-trainanddecode.tex}

\section{Experiments}
We investigate the effect of word information and our GAT encoder to character-level graph-based Chinese parsing.

\subsection{Settings}

We use three releases of the Chinese Penn Treebank (i.e., 5.0, 6.0 and 7.0) \citep{xue2005penn},
splitting the corpora into training, development and test sets according to previous work.
CTB 5.0 is split by following \citet{zhang-clark:2010:EMNLP}, CTB 6.0 by following the official documentation, and CTB 7.0 by following \citet{wang2011improving}.

We use the head rules of \citet{zhang-clark:2008:EMNLP} to convert phrase structures in CTB into dependency structures.
Following \citet{hatori2012incremental}, the standard measures of word-level precision, recall and F1 score are used to evaluate word segmentation, POS-tagging and dependency parsing, respectively.
For a given word $w=c_1c_2...c_k$, we simply use the right branching tree $c_1 \rightarrow c_2 \rightarrow ... \rightarrow c_k$ as the intra-word dependency structure.
Following \citet{zhang-yang-2018-chinese}, we take the external Chinese lexicon dictionary from \citet{song2018directional}.
The experiments are conducted under the same hardware environment: Geforce GTX 2080Ti graph card and i7-7900 CPU.

\textbf{Hyper-parameters} We initialize character embeddings using BERT \citep{devlin2018bert}, and
word embeddings with the average pooling result of BERT character embeddings.
Neither character nor word embeddings are fine-tuned due to limitation of GPU memory. The size of hidden states is set to 400 for all models (The hidden size of each direction in biLSTM is 200).

Training is done on mini-baches via Adagrad \citep{duchi2011adaptive} with a learning rate of 0.002, $\beta_1=0.9, \beta_2=0.9$ and $\epsilon=1e-12$.
We adopt gradient clipping with a threshold of 5.0. Dropout \citep{hinton2012improving} is used on each layer, with a rate of 0.2.

\subsection{Development Experiments}

We conduct development experiments on the CTB 5.0 dev set to decide the final hyper-parameters of the two mixed model. Below we show the details of three important factors.

\textbf{Effect of Encoder Layers}
We investigate the effect of the number of encoder layers for the word-character graph attention model. The results are shown in Table \ref{tab:dev_lattice_att}. As the number of encoder layer increases from 1 to 3, performance improves for parsing, as well as word segmentation and POS tagging. We do not conduct experiments on more layers because of memory limitation. The number of encoder layers is set to 3 in the remaining experiments.

\textbf{Effect of Attention Heads} We further investigate the effect of attention head number for the word-character graph attention  model, as shown in Table \ref{tab:dev_lattice_att}.  We observe performance increases as the number of attention heads increases from 1
to 4, but adding more attention heads does not lead a further performance improvement. We thus fix the number of attention heads to 4 accordingly.

\begin{table}[t]
\small
\centering
\begin{tabular}{llll}
\specialrule{.05em}{0pt} {.65ex}
\textbf{Parameter} & \textbf{SEG}  & \textbf{POS} & \textbf{DEP}    \\
\midrule
1 head & 98.5 & 96.4 & 91.0 \\
4 heads & 98.8 & 96.5 & 91.4 \\
8 heads & 98.6 & 96.4 & 91.3 \\
16 heads & 98.7 & 96.5 & 90.9 \\ \hline
1 layer & 98.5 & 96.2 & 90.0 \\
2 layers & 98.5 & 96.3 & 91.1  \\
3 layers & 98.8 & 96.5 & 91.4  \\
\specialrule{.05em}{.4ex}{0pt}
\end{tabular}
\caption{Dev experiments for word-character graph attention model.}
\label{tab:dev_lattice_att}
\end{table}

\textbf{Effect of Word Information and Model Architectures}
We conduct a set of development experiments to verify the influence of model architecture and word information on each architecture.

The results are shown in Table \ref{tab:dev}. In particular, a character-level LSTM model gives a parsing accuracy of 90.3\%. With word-character lattice, the results are improved to 90.8\%
Using GAT, the model gives a 90.9\% development accuracy for parsing, which is improved to 91.4\% by using word information additionally.
This shows that word information is beneficial to both the LSTM architecture and the GAT architecture. In addition to dependency structures, the results for both word segmentation and POS-tagging are also improved.

In addition, LSTM models underperform their SAN counterparts regardless whether word information is combined into the character encoder.
The lattice LSTM system is much slower to train (nearly half an hour for training one epoch on CTB 5, and the total training takes several days) compared with the chracter-level BiLSTM model (145 seconds for one epoch) and  SAN models (421 seconds for one epoch).

\begin{table}[t]
\small
\centering
\begin{tabular}{llll}
\toprule
\textbf{Model} & \textbf{SEG}  & \textbf{POS} & \textbf{DEP}    \\
\midrule
Character-level LSTM &  98.4 & 96.1 & 90.3 \\
Word-char lattice LSTM  &  98.7 &	96.4  & 90.8 \\
Character-level transformer & 98.7 &	96.5  & 90.9    \\
Word-char graph attention & 98.8 &	96.5 & 91.4  \\
\specialrule{.05em}{.4ex}{0pt}
\end{tabular}
\caption{Dev experiments on different models.}
\label{tab:dev}
\end{table}

\begin{table*}[tp]
\small
  \centering
    \begin{tabular}{lccccccccc}
    \specialrule{.05em}{0pt} {.65ex}
    \multirow{2}{*}{Model}&
    \multicolumn{3}{c}{CTB 5.0}&\multicolumn{3}{c}{CTB 6.0}&\multicolumn{3}{c}{CTB 7.0}\cr
    \cmidrule(lr){2-4} \cmidrule(lr){5-7} \cmidrule(lr){8-10}
    &SEG & POS & DEP &SEG & POS & DEP & SEG & POS & DEP \cr
    \midrule
    Incremental Joint \citep{hatori2012incremental} & 96.9  & 93.0 & 76.0  & 96.2  & 92.0  & 75.8 & 96.1  & 91.3 & 74.6 \\
    Char STD \citep{zhang2014character} & 97.8 & 94.6 & 82.1  & 95.6   & 91.4 & 77.1 & 95.5 & 90.8 & 75.7 \\
    Char EAG \citet{zhang2014character} & 97.8 & 94.4 & 82.1  & 95.7 & 91.5 & 77.0 & 95.5 & 90.7 & 75.8 \\
    Joint Annotated \citep{zhang2015randomized} & 98.0 & 94.5 & 82.0 & - & - & - & - & - & - \\
    NN transition \citep{kurita2017neural} & 98.4 & 94.8 & 81.4 & - & - & - & 96.4 & 91.3 & 75.3 \\
    NN char-level \citep{li2018neural} & 96.6 & 92.9 & 79.4* & - & - & - & - & - & - \\
    Joint Multi BERT \citep{yan2019unified} & 98.5 & - & 89.6 & - &- & - & 97.1 & - & 85.1 \\
    \midrule
    Lattice-LSTM E2E BERT & 98.4 & 96.2 & 88.1 & 97.3 & 94.6 & 83.6 & 96.9 & 93.9 & 84.9 \\
    \textbf{Word-char Graph Attention} & \textbf{98.7} & \textbf{96.5} & \textbf{91.3} & \textbf{97.3} & \textbf{94.8} & \textbf{87.2} & \textbf{97.3} & \textbf{94.4} & \textbf{86.2} \\
    \specialrule{.05em}{.4ex}{0pt}
    \end{tabular}
\caption{Final Results. * indicate performance on CTB 5.1.}
\label{tab:result}
\end{table*}

\subsection{Final Results}
Table \ref{tab:result} shows the overall performances of end-to-end Chinese dependency parsing where our model is compared with the state-of-the-art methods in the literature.
We report the performances on Chinese word segmentation, POS tagging and parsing, respectively.
First, we can find that BERT pretrained models outperform neural models using traditional embeddings \citep{kurita2017neural, li2018neural} and statistical models  \citep{hatori2012incremental, zhang2014character, zhang2015randomized} by a large margin.
Compared with Joint Multi BERT \citep{yan2019unified}, the word-char graph attention model achieves better performance especially on parsing.
Note that we do not leverage on additional syntactic and lexical annotation within a word as \citet{zhang2014character} and \citet{li2018neural} do.
This demonstrates the advantage of our word-character graph attention model.

The final results on parsing of the lattice-LSTM BERT end-to-end model are 88.1\%, 83.6\% and 84.9\% on the CTB 5, 6 and 7 datasets, respectively, and the final results of the GAT model are 91.3\%, 87.2\% and 86.2\% on the three datasets, respectively. The improvements are statistically significant at $p < 0.05$ using t-test. Overall, the GAT architecture gives better segmentation, POS-tagging and parsing results compared with the LSTM model on all datasets, while running much faster. This shows the advantage of our semantic and structural channels for integrating word information. Compared with the existing methods for joint Chinese parsing, our final GAT model gives better results on all the three datasets, achieving the best reported accuracies on dependency parsing in the literature.

\textbf{Segmentation Results}
According to Table~\ref{tab:result}, word information brings the most improvements on parsing accuracies, followed by tagging accuracies. Segmentation benefits relatively less.
However, as a fully end-to-end model, POS tagging and dependency parsing information can also benefit word segmentation. Thus our joint model can be a competitive choice for the segmentation task alone.
We compare the performance of different models with BERT pretraining on the CTB6 word segmentation task in Table \ref{tab:exp:cws_test} (previous work mostly uses the CTB6 version).

The first 4 items are the segmentation models trained on the single segmentation task.  BiLSTM-CRF-BERT \citep{gan2019investigating} uses a BiLSTM network followed by CRF network with pretrained BERT as input. LSAN-CRF \citep{gan2019investigating} uses a local self-attention network instead of BiLSTM. DP-BERT \citep{huang2019toward} and Unified-BERT \citep{ke2020unified} are both multi-criteria Chinese word segmentation models, which are trained on a range of extra training sets to enhance the segmentor. DP-BERT \citep{huang2019toward} uses a domain projection for multi-criteria learning while unified BERT \citep{ke2020unified}
employs a fully shared model for all criteria.

Our model gives better performance on segmentation BiLSTM-CRF-BERT and a bit worse result than LSAN-CRF-BERT, which is optimised for segmentation.
In addition, our model gives comparable results in segmentation compared with DP-BERT and Unified-BERT,
which shows the advantage of joint parsing as compared to external segmentation datasets.
Compared with \citet{yan2019unified}, our model can give better segmentation.

\subsection{Analysis}
\label{sec:analysis}

In this section, we focus on the word-character GAT model to thoroughly investigate the effect of word information.

\begin{table}[t]
\small
\centering
\begin{tabular}{lc}
\specialrule{.05em}{0pt} {.65ex}
Model & F1-score \\  \midrule
BiLSTM-CRF-BERT \citep{gan2019investigating}  & 97.2  \\
LSAN-CRF-BERT \citep{gan2019investigating} & 97.4\\
DP-BERT \citep{huang2019toward} & 97.6 \\
Unified BERT \citep{ke2020unified}  & 97.2\\ %
Word-char Graph Attention  & 97.3  \\
\specialrule{.05em}{.4ex}{0pt}
\end{tabular}
\caption{Word Segmentation results. All results are based on BERT pretraining.}
\label{tab:exp:cws_test}
\end{table}

\begin{figure}[!tb]
   \centering
   \includegraphics[width=0.85\linewidth]{fig/lens4.pdf}
   \caption{Performance against sentence length. The F1 score for each length $l$ is calculated on the test set sentences length in the bin $[l, l+15]$.}
      \label{fig:exp:lens}
\end{figure}

\begin{figure*}[!tb]
 \setlength{\abovecaptionskip}{4pt}
  \centering
  \includegraphics[width=0.96\linewidth]{fig/samples3new.pdf}
  \caption{Sample outputs. Errors are in red.}
      \label{fig:exp:cases}
\end{figure*}

\textbf{OOV}
Table \ref{tab:exp:oov} shows the recall of out-of-vocabulary words on the CTB 5.0 test set. A word-character graph attention model enriched with word information achieves 0.9\%, 2.1\% and 4.1\% absolute improvement over the character-level model on word segmentation, POS tagging and parsing, respectively. It shows that the word-character attention model benefits transfer learning and generalization.
This is likely because lexicons help to learn better representation for OOV words.
In particular, the word-char attention model shows significant improvement on parsing. The improvement of parsing results from better segmentation (+ 0.9\%) and better head inference (+3.8\%).

\begin{table}[t]
\small
\centering
\begin{tabular}{lccc}
\specialrule{.05em}{0pt} {.65ex}
Task & Char M. & Word-char M. & Diff. \\
\midrule %
SEG & 87.4 & 88.3 & +0.9 \\
POS & 81.7 & 83.8 & +2.1 \\
DEP & 76.6 & 80.7 & +4.1 \\
DEP$'$ & 87.6 & 91.4 & +3.8 \\
\specialrule{.05em}{.4ex}{0pt} %
\end{tabular}
\caption{Recalls of OOV words. DEP$'$ indicates the parsing recall rate when the dependent word is correctly segmented.  }
\label{tab:exp:oov}
\end{table}

\textbf{Performance Against the Sentence Length}
We further analyze the performance with respect to different sentence lengths. Figure \ref{fig:exp:lens} shows the results. The performance of word segmentation and POS tagging are relatively stable against sentence length as these two tasks rely more on the local context. There is a tendency of decreasing F1 scores for parsing when the sentence length increases.
Compared with the the Transformer model without using word information, the word-character GAT model gives about the same improvements on parsing across different sentence lengths. In addition, the use of word information also makes the curve more smooth across different sentence lengths, which shows the benefit of lexicon features in enhancing the model robustness.

\textbf{Ablation Study}
We conduct ablation experiments to investigate the effect of different channels  of the word-char graph attention model showing three important factors on the CTB 5.0 test set in Table \ref{tab:exp:ablation}.
Compared with the word-char graph attention model, removing the structural channel leads to a  parsing F1 score decrease by 0.6\%. In contrast, excluding the semantic channel decreases the parsing F1 score by 0.8\%.
Compared with the structural channel, the semantic channel contains important position information besides semantic similarity, which can be the reason for its better performance. However,
the best result is achieved using both channels, from which it can be inferred that the channels can  interact with and complement each other on the final performance.
We can also observe that using word information through either channel or both channels combined can improve the parsing performance compared to a character-level attention model (``- all word info'' in the table), showing the effectiveness of word information.

\begin{table}[t]
\small
\centering
\begin{tabular}{lcc}
\hline
\textbf{Configuration} & \textbf{F1 score} & \textbf{Diff.} \\
\hline
Word-char graph attention & 91.3 & 0 \\
- structural channel & 90.8 & -0.5 \\
- semantic channel & 90.6 & -0.7 \\
- all word information & 90.5 & -0.8 \\
\hline
\end{tabular}
\caption{Ablation test of the  word-character graph attention model.}
\label{tab:exp:ablation}
\end{table}

\textbf{Case Study}
Figure \ref{fig:exp:cases} shows samples of end-to-end Chinese parsing on CTB 5.0. In the first sentence, the head word of token ``菲律宾(the Philippines)'' is incorrectly recognized as ``名字(name)'' in the vanilla LSTM model, while the word-char graph attention model identifies its correct head ``总统(president)''.
The vanilla LSTM model suffers from polysemous characters
``菲(commonly used character in names)'', ``律(law)'' and ``宾(commonly used character in names)'' .
In contrast, the word-character graph attention model taking additional word information ``菲律宾(the Philippines)'' can better understand the sentence and thus gives a correct syntactic parsing result.

In the second sentence, the expression ``麦格赛赛奖(Magsaysay Award)'' (Gold segmentation: ``麦格赛赛(Magsaysay)'', ``奖(Award)'') is incorrectly segmented into tokens ``麦格赛(Magsay)'' and ``赛奖(Competition Award)'' by the vanilla LSTM model, which results in errors in the POS tagging and parsing result. It shows that word features can help better identify word boundaries, which is important
to POS tagging and parsing. The word-char graph attention model segments the sentence correctly, and thus gives the correct result in all three tasks. In summary, the word-character graph attention model  performs better in identifying dependency heads in addition to word boundaries, thanks to the lexicon input.

\section{Conclusion}
\label{sec:con}
We investigated the effectiveness of word information for end-to-end graph-based Chinese parsing by
extending a character-level transformer encoder. Compared with LSTM-based representation learning models, our method is more feasible due to better parallelization between characters and convenience to batching.
Results on the three datasets show that word information benefits all the three tasks, and
our word-char graph attention model outperforms the lattice-LSTM model,
and achieving the best results on segmentation, POS tagging and parsing in the literature.
To our knowledge, we are the first to investigate an end-to-end Chinese parser exploiting lexicon knowledge.

redpajama_set_name: RedPajamaArXiv


text:
\section{Introduction}

Allocation of indivisible resources is one of the most fundamental problems in \emph{fair division} and \emph{multiagent resource allocation}~\citep{BrTa96a}.
Many of the fair division settings feature two agents since  disputes often concern two parties. Recently \citet{BKK12a} presented the \emph{undercut procedure} which is an elegant procedure to divide a set of contested indivisible objects fairly among two agents. A crucial assumption in the paper was that agents have a strict ranking over the objects and the preferences over \emph{sets} of objects are \emph{responsive}. Preferences over sets of objects are responsive if for any set in which an object is replaced by a more preferred object, the new set is more preferred. We first show that the assumption of responsive preferences can be somewhat restrictive. We also identify three shortcomings of the first few steps of the undercut procedure. Finally we rectify the shortcomings by simplifying the undercut procedure of  \citet{BKK12a} and showing that it returns an envy-free allocation (if it exists) under a more general preference restriction called \emph{separability}.

The setting we consider concerns two agents $1$ and $2$ and a set of objects $O$. Both agents have \emph{complete} and \emph{transitive} preferences $\succsim \xspace_1$ and $\succsim \xspace_2$ over the subsets of objects in $O$.
The goal is to identify an envy-free split $(S,-S)$ where $S$ is the allocation of agent $1$ and $-S=O\setminus S$ is the allocation of agent $2$.

\section{The undercut procedure}

The undercut procedure is a discrete generalization of the divide and choose cake cutting protocol~\citep[Chapter 1, ][]{BrTa96a}.
The elegance of the undercut procedure lies in the fact that although agents have preferences over sets of objects, it is sufficient  to only consider or query about the \emph{minimal bundles} of the agents.
A subset $S\subseteq O$ is a \emph{minimal bundle} for agent $i$ if $S\succsim \xspace_i -S$ and for any $T\subset S$, $-T\succ_i T$.
The set of minimal bundles of agent $i$ is denoted by $MB_i$.
Any envy-free split $(S,-S)$ of $O$ is \emph{trivial} if $S\sim_1 -S$ and $-S\sim_2 S$.
The main idea underlying the undercut procedure is that there exists a non-trivial envy-free allocation if the set of minimal bundles of both agents is not the same.
The undercut procedure goes through the minimal bundles of the agents to identify an envy-free allocation if it exists~\citep{BKK12a}.  We refer the reader to Algorithm~\ref{algo:undercut} for an adapted specification of the undercut procedure.

\begin{algorithm}[h!]
	  \caption{Undercut procedure of \citet{BKK12a}}
	  \label{algo:undercut}
	\footnotesize
	\renewcommand{\algorithmicrequire}{\wordbox[l]{\textbf{Input}:}{\textbf{Output}:}}
	 \renewcommand{\algorithmicensure}{\wordbox[l]{\textbf{Output}:}{\textbf{Output}:}}
	\begin{algorithmic}
		\REQUIRE $(N,O,\succsim \xspace)$
		\ENSURE Envy-free split if it is exists.
	\end{algorithmic}
	\algsetup{linenodelimiter=\,}
	  \begin{algorithmic}[1]
	\small
			\STATE \textbf{Generation Phase:} Agent $1$ and $2$'s most preferred objects are given to them if they do not coincide. If the object coincides, then it is placed in the contested pile $I_C\subset O$. The process continues until all objects have been names by at least one agent. If the contested pile is empty, the procedure ends. Otherwise, each agent $i$ identifies his  set of minimal bundles $MB_i$ of $I_C$.
			\STATE If $MB_1 \neq MB_2$, each agent $i$ provides reports to the mechanism a ranking of his  minimal bundles. An agent $i$ is chosen at random, and one of $i$'s top-ranked minimal bundle $S$ is considered. If  $S\notin MB_{-i}$ , then it becomes the proposal, and $i$ is the proposer. If  $S\in MB_{-i}$, then one of $-i$'s top-ranked minimal bundle $S'$ is considered. If $S'\notin MB_i$, then it becomes the proposal, and $-i$ the proposer. If  $S'\in MB_i$, then the process continues until a minimal bundle of one agent is found that is not a minimal bundle of the other. Then proceed to step 4.
			\STATE If $MB_1 = MB_2$, and there exists an $S$ such that $S \in  MB_i$ and $−S \in MB_i$ (and, therefore $S,-S \in MB_{-i}$ also), then $S$ becomes the proposal. If there is no minimal bundle $S$ such that $−S$ is also a minimal bundle, then a minimal bundle is chosen randomly and becomes the proposal.
				\STATE Assume that $S$ is the proposal and the proposer is $i$. Then $-i$ may respond by
	$i)$ accepting $-S$ of $I_C$
or $ii)$ undercutting $i$'s proposal, i.e., taking his most-preferred subset $T$ and giving $-T$ to $-i$.

				The procedure ends. An agent's subset of $O$ consists of all objects received in steps 1 and 2, plus the agent's share of the contested pile determined in step 4.

	 \end{algorithmic}
	\label{algo:subroutine}
	\end{algorithm}

\paragraph{Limitation of responsive preferences}

The undercut procedure was shown to find an envy-free allocation if the preferences of agents are \emph{responsive}.
\emph{Responsiveness} is a  well-established preference restriction on preferences over sets of objects which assumes that the agents have preferences over the individual objects.
Preferences over sets of objects are \emph{responsive}, if for any two sets that differ only in one object, the agent prefers the set containing the more preferred object~\citep{BBP04a}.
We first highlight that responsive preferences can be restrictive.
\begin{example}
In a divorce dispute, husband $h$ may prefer each of the two family dogs $d_1$ and $d_2$ over the car $c$:
$\{d_1\} \succ_h \{d_2\} \succ_h \{c\} \succ_h \emptyset.$ If the husband's preferences are responsive, then his preferences over the set of issues is as follows:
$\{d_1,d_2,c\}  \succ_h \{d_1,d_2\}  \succ_h \{d_1,c\} \succ_h  \{d_2,c\}.
$

However it may be the case that the husband prefers the set of a car and a dog to the set of two dogs: $\{d_1,c\}\succ_h \{d_1,d_2\}$. This way he will have both a companion and a ride. $\{d_1,d_2,c\}  \succ_h \{d_1,c\}  \succ_h \{d_2,c\} \succ_h  \{d_1,d_2\}.$
\end{example}

A preference relation $\succ$ is \emph{separable} if for all
$S\subset O$ such that $x\notin S$, the following holds:
 $\{x\}\succ \emptyset$ if and only if $S\cup \{x\} \succ S$~\citep{BBP04a}.
Informally, separability means that if an agent prefers having the object than having nothing, he would also prefer the inclusion of the object in any other set that does not include the object.
Whereas responsive preferences are separable, separable preferences are more general than responsive preferences.  Just as in \citep{BKK12a}, we will assume that all the objects are desirable. However, we will not use the restriction in  \citep{BKK12a} that preferences over objects do not admit ties.

\paragraph{Issues with the generation phase of the undercut procedure}

In the generation phase of the undercut procedure (Algorithm~\ref{algo:undercut}), each agent sequentially picks up his maximal object if it is uncontested. Otherwise each contested object goes into the \emph{``contested pile''}.
We argue that the generation phase of the undercut procedure (also referred to as the \emph{generation phase} in \citep{VeKi13a}) has some drawbacks.
\emph{Firstly},	undercut may fail to identify an envy-free split because of the generation phase.
Let us consider the following preferences of agents 1 and 2: $a \mathrel{\succ_1} b \mathrel{\succ_1} c \mathrel{\succ_1} d$ and $b \mathrel{\succ_2} c \mathrel{\succ_2} d \mathrel{\succ_2} a.$
		If  $\{a,d\} \sim_1 \{b,c\}$, we know that the assignment which allocated $\{a,d\}$ to agent $1$ and $\{b,c\}$ to agent $2$ is envy-free. However undercut fails to compute this assignment. The reason is that in the generation phase, agent $1$ takes $a$ and agent $2$ takes $b$. After this the contested pile is $\{c,d\}$. The undercut procedure ends up in a deadlock in this contested pile.
\emph{Secondly}, even if the undercut procedure works for certain responsive preferences, the generation phase hinders it from working for separable preferences.
\emph{Thirdly}, the generation phase use sequential allocation. It is well-understood that sequential allocation is highly susceptible to manipulation if at least one agent has sufficient information about the other agent's preferences~\citep{KoCh71a,VeKi13a}.
One point which goes in favour of Step 1 and 2 of the undercut procedure is that it decreases the size of the contested pile which was presumably the motivation behind the steps.
\paragraph{Simplified undercut procedure}

Next, we show that the simplified undercut procedure works for transitive and separable preferences.
We define a \textit{simplified undercut} procedure as follows.
\textbf{\emph{Simplified Undercut:}}	\emph{Treat the set of all objects as the contested pile and run the original undercut procedure while ignoring the generation phase of the original undercut procedure.}

\begin{proposition}
		For transitive and separable preferences, there is a non-trivial envy-free split if and only if the set of minimal bundles of both agents is not the same. Furthermore the simplified undercut procedure finds such an a split.
\end{proposition}
\begin{proof}
	The argument is similar to the one for the proof of \citep[Theorem 1, ][]{BKK12a}.
	We first prove that if a  non-trivial envy-free split exists it implies that the set of minimal bundles of both agents is not the same. Let us assume that a non-trivial envy-free split $(S,-S)$ exists.
Then there must be an agent $i\in \{1,2\}$ such that $S\succ_i -S$. By the definition of minimal bundle, we know that $-S\notin {MB}_i$. Without loss of generality, we can assume that $S\in {MB}_{i}$. If it were not then we argue that there exists an $S'$ such that $S'\in {MB}_{i}$, $S'\subset S$, such that $S'\succsim_{i} -S'$.
For an $S'\subset S$, by separability, we know that $S\succ_i S'$. Similarly, by separability, we know that $-S'\succ_i -S$ because $-S'$ can be obtained from $-S$ by adding those elements to $-S$ as the elements that are removed from $S$ to obtain $S'$. Since $\succsim \xspace_i$ is transitive and complete, there exists some $S'$ such that $S'\succsim_i -S'$ for which there exists no subset $S''\subset S'$ such that $S''\succsim \xspace_i -S''$.

Now if $S'\sim -S'$, then we know that $S'\in {MB}_{i}$. By separability, we also know that $-S'\succ_{-i} -S \succsim_{-i} S \succ_{-i} S'$. Hence $S'\notin {MB}_{-i}$ which means that  set of minimal bundles of both agents is not the same.
If $S\notin {MB}_{-i}$, then we have already proved that the set of minimal bundles of the two agents are different. Now let us assume that $S\in {MB}_{-i}$. Then we know that $S\succsim_{-i} -S$. Since $(S,-S)$ is envy-free, then it follows that $-S\succsim_{-i} S$. Hence $S\sim_{-i}-S$. If $-S\in {MB}_{-i}$ then we are already done. We show that $-S$ is indeed in ${MB}_{-i}$. Consider any $T\subset-S$ which implies by separability that $-S\succ_{-i} T$.
Since $S=O \setminus -S$ and since $T\subset-S$, we know that $O\setminus T = -T\supset S$. This implies by separability that $-T\succ_{-i} S$. Since $-T\succ_{-i} S$, $-S\succ_{-i} T$ and $S\sim_{-i}-S$, we get by transitivity that $-T\succ_{-i} T$.
Hence we have shown that $-S\in {MB}_{-i}$. Since we know that $-S\notin {MB}_{i}$, the set of minimal bundles of both agents is not the same.

	We now prove that if the two agents do not have the same set of minimal bundles then there exists a non-trivial envy-free split.
	Let us assume that the two agents do not have the same set of minimal bundles i.e., there exists an $S\subset O$ such that $S\in {MB}_{i}$ and $S\notin {MB}_{-i}$. If $-S\succsim_{-i} S$, then $(S,-S)$ is an envy-free split. 	When agent $i$ will propose $(S,-S)$, agent $-i$ will accept it. Therefore let us look at the other case when $S\succ_{-i} -S.$
If $S\succ_{-i} -S$,  and  $S\notin {MB}_{-i}$, then by the definition of a minimal bundle we know that there exists a $T\subset S$ such that $T\succsim_{-i}-T$. Agent $-i$ will undercut the proposal $(S,-S)$ of agent $i$ and will be ready to take $T$.
For agent $1$, we know that $S\succ_i -T \succ_i T\succ_i -S.$ Thus $(-T,T)$ is an envy-free split.
\end{proof}

The argument is similar to the one for the proof of \citep[Theorem 1, ][]{BKK12a}.
If a trivial envy-free split exists, the simplified undercut procedure will find it since it considers the minimal bundles of the two agents. If a trivial envy-free split does not exist but a non-trivial one does, even then the simplified undercut procedure will find it.
If agents have unequal claims say claim $c_i$ for agent $i$,  then the definition of envy-freeness can be easily extended as follows: $u_i(S)\geq \frac{c_i}{c_{-i}}u_i(-S)$ for an allocation where $i$ gets $S$.
If agents have unequal claims, the undercut procedure still works as follows. We simply redefine a minimal bundle $S$ for agent $i$ as a set of objects such that $u_i(S)\geq \frac{c_i}{c_{-i}}u_{i}(-S)$ and for any $T\subset S$, $u_i(T)< \frac{c_i}{c_{-i}}u_{i}(-T)$.

\section*{Acknowledgment}
NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.


text:
\section{Motivation}
\label{intro}

A belief of the overwhelming majority of scientists is that classical mathematics
(involving the notions of infinitely small/large and continuity) is fundamental while finite mathematics
is something inferior what is used only in special applications. This belief is based on the fact that
the history of mankind undoubtedly shows that classical mathematics has demonstrated its
power in many areas of science. Nevertheless a problem arises whether classical mathematics is
pertinent for constructing the ultimate quantum theory.
At present, in spite of efforts of thousands of highly qualified physicists
and mathematicians to construct such a theory on the basis of classical mathematics, this problem has not
been solved.

Historically the notions of infinitely small/large, continuity etc. have arisen from a belief based on everyday experience that any macroscopic
object can be divided into arbitrarily large number of arbitrarily small parts.
Classical physics is
based on classical mathematics developed mainly when people did not know about
existence of elementary particles. However, from the point of view of the present knowledge those notions look problematic.

For example, a glass of water contains approximately $10^{25}$ molecules.
We can divide this water by ten, million, etc. but when we reach the level of atoms and elementary particles
the division operation loses its meaning and
we cannot obtain arbitrarily small parts. So, {\it any description of macroscopic phenomena using continuity and differentiability can be only approximate}.
In nature there are no continuous
curves and surfaces. For example, if we draw a line on a sheet paper and look at this line by
a microscope then we will see that the line is strongly discontinuous because it consists of
atoms.

The official birth of quantum theory is 1925, and even the word "quantum" reflects a belief that
nature is discrete. The founders of this theory were highly educated physicists
but they knew only classical mathematics because even now mathematical education at physics departments
does not involve discrete and finite mathematics. In view of the above remarks it is reasonable to think that in
quantum theory classical mathematics
might be used for solving special problems but ultimate quantum theory should not be based on classical mathematics.

The opinion that classical mathematics is fundamental is often based on the fact
that it contains more numbers than finite mathematics. Let us consider this problem in greater details.

Classical mathematics starts from natural numbers and the famous Kronecker's expression is:
{\it "God made the natural numbers, all else is the work of man"}.
However here only addition and multiplication are always possible. In order to make addition invertible we introduce negative
integers. They do not have a direct physical meaning (e.g. the phrases "I have -2 apples" or "this computer
has -100 bits of memory" are meaningless) and their only goal is to get the ring of integers $Z$.

However, if instead of all natural numbers we consider only a set $R_p$ of
$p$ numbers 0, 1, 2, ... $p-1$ where addition and multiplication are defined
as usual but modulo $p$ then we get a ring without adding new elements.
If, for example, $p$ is odd then
one can consider $R_p$ as a set of elements $\{0,\pm i\}$ $(i=1,...(p-1)/2)$.
If elements of $Z$ are depicted as integer points on the $x$ axis of the $xy$ plane then
it is natural to depict the elements of $R_p$ as points of the circumference in Fig. 1.
\begin{figure}[!ht]
\centerline{\scalebox{0.3}{\includegraphics{image.png}}}
\caption{
  Relation between $R_p$ and $Z$
}
\label{Fig.1}
\end{figure}

Let $f$ be a function from $R_p$ to $Z$ such that
$f(a)$ has the same notation in $Z$ as $a$ in $R_p$. Then for elements $a\in R_p$ such that $|f(a)|\ll p$,
addition, subtraction and multiplication are the same as in $Z$. In other words, for
such elements we do not feel the existence of $p$. Indeed, for elements $a_j\in R_p$ ($j=1,2$)
such that $|f(a_j)|<[(p-1)/2]^{1/2}$ we have that $f(a_1\pm a_2)=f(a_1)\pm f(a_2)$ and $f(a_1a_2)=f(a_1)f(a_2)$
which shows that $f$ is a local isomorphism of some vicinities of zero in $R_p$ and $Z$.

As explained in textbooks, both $R_p$ and $Z$ are cyclic groups with respect to addition. However,
$R_p$ has a higher symmetry because, in contrast to $Z$, $R_p$ has a property which we call {\it strong cyclicity}:
for any fixed $a\in R_p$ any element of $R_p$ distinct from $a$ can be obtained from $a$ by successively adding 1.
As noted below, in quantum physics the presence or absence of strong cyclicity plays an important role.

When $p$ increases, the bigger and bigger part of $R_p$
becomes the same as $Z$. Hence $Z$ can be treated as a degenerate case of
$R_p$ in the formal limit $p\to\infty$ because in this limit operations modulo $p$ disappear
and strong cyclicity is broken. {\it Therefore, at the level of rings standard mathematics is a degenerate case of finite one when formally $p\to\infty$}.

The transition from $R_p$ to $Z$ is similar to the procedure, which in group theory is called contraction.
This notion is used when the Lie algebra of a group with a lower symmetry
can be treated as a formal limit of the Lie algebra of a group with a higher symmetry when some parameter goes to zero or infinity. Well known examples are the contraction from the de Sitter
to the Poincare group and from the Poincare to the Galilei group.

The above construction has a well-known historical analogy. For many years people believed
that the Earth was flat and infinite, and only after a long period of time they realized that
it was finite and curved. It is difficult to notice the curvature when we deal only with
distances much less than the radius of the curvature. Analogously one might think that
the set of numbers describing physics in our Universe has a "curvature" defined by a very
 large number $p$ but we do not notice it when we deal only with numbers much less than $p$.

One might argue that introducing a new fundamental constant $p$ is not justified.
However, history of physics tells us that more general theories arise when a parameter,
which in the old theory was treated as infinitely small or infinitely large, becomes finite.
For example, nonrelativistic physics is the degenerate case of relativistic one in the formal limit $c\to\infty$
and classical physics is the degenerate case of quantum one
in the formal limit $\hbar\to 0$.  Therefore, it is natural to think that
in quantum physics the quantity $p$ should be not infinitely large but finite.

The above discussion shows that when we take the formal limit $p\to\infty$ then we obtain a less
general theory, not a more general one. Therefore the fact that classical mathematics contains more
numbers than finite one does not indicate that classical mathematics is more fundamental.

From mathematical point of view standard quantum theory can be treated as a theory of
representations of special real Lie algebras in complex Hilbert spaces. In Refs. \cite{lev4,PRD} and
other publications we have
proposed an approach called FQT (Finite Quantum Theory) when Lie algebras and representation spaces are over a finite field or ring with characteristic $p$. It has been shown that in the formal limit
$p\to\infty$ FQT recovers predictions of standard continuous theory.
Therefore classical mathematics describes many experiments with a high accuracy as a
consequence of the fact that the number p is very large.

In Sec. \ref{S1} we consider several problems where it is important that the number $p$
is finite and not infinite and Sec. \ref{conclusion} is a discussion.

\section{Main results of FQT}
\label{S1}

\subsection{Particles and antiparticles in FQT}

A well-known fact of particle physics is that a particle and its antiparticle have equal masses.
The explanation of this fact in quantum field theory (QFT) follows.
Irreducible representations (IRs) of the Poincare and anti-de Sitter (AdS) algebras by Hermitian operators
used for describing elementary particles have the property that for each IR the Hamiltonian is either positive definite or negative definite. In the first case, the energy has the spectrum in the range $[m_1,\infty)$, while in the second case it has the spectrum in the range $(-\infty,-m_2]$ ($m_1,m_2\geq 0$). The quantities $m_1$ and $m_2$ are called the masses of the
particle and its antiparticle, respectively.

Hence a particle and its antiparticle are described by different IRs and the equality $m_1=m_2$ is
problematic. In standard quantum theory this equality follows from the assumption that a particle
and its antiparticle can be described by a local field satisfying a covariant equation (e.g. the Dirac equation). However, a problem arises whether this equality remains if locality is only approximate.
In addition, the meaning of locality is not quite clear because local fields do not
have probabilistic interpretation.

By analogy with standard quantum theory, it is natural to define the elementary particle in FQT as
a system described by an IR of a Lie algebra over a finite field or ring with characteristic $p$. Representations of Lie algebras in spaces with nonzero characteristic are called
modular representations and there exists a well developed theory of such representations.

To illustrate the difference between the treatment of particles and antiparticles in standard theory
and in FQT we first note how IRs for the AdS algebra are described
in standard theory. In the case of a particle one starts from the "rest" state $e_1$  where
energy equals $m_1$. When the representation operators act on $e_1$ one obtains
states with higher and higher energies and the energy spectrum is in the range $[m_1,\infty )$.
On the other hand, for describing antiparticles one starts from the state $e_2$ where
energy equals $-m_2$. When the representation operators act on $e_2$ one obtains
states with lower and lower energies and the energy spectrum is in the range $( -\infty,-m_2]$.

However, in FQT can can prove \cite{monograph} that: {\it The IR with the cyclic
vector $e_1$ and the IR with the cyclic vector $e_2$ are the same and $m_1=m_2$.}
The explanation follows. When the representation operators act on $e_1$ and increase the energy,
then, since the values of the energy now belong not to $Z$ but to $R_p$, we are moving not
in the positive direction of the $x$ axis but along the circumference in Fig. 1. Then, as a consequence of
strong cyclicity, sooner or
later we will arrive to states where the energy is "negative" (i.e. in the range $[-(p-1)/2,-1]$)
and finally we will arrive to
the state where energy equals $-m_1$. From the point of view of physics this means that one
modular IR describes a particle and its antiparticle simultaneously.

As shown in Ref. \cite{JPA}, in standard theory a particle and its antiparticle are described
by the same IR in a special case when the theory is based on de Sitter (dS) symmetry. However, in
FQT this is true for any symmetry as a consequence of strong cyclicity.

As a consequence, in FQT a particle and its antiparticle aumatically have the same masses.
Moreover, while in standard theory the existence of antiparticles depends on additional assumptions, in FQT it is inevitable. Therefore, {\it the very existence of antiparticles is a strong indication that nature
is described by a finite field or ring rather than by complex numbers.}

Since a particle and its antiparticle belong to the same IR, transitions $particle\leftrightarrow antiparticle$
are not prohibited. This means that the very notions of a particle and its antiparticle are only
approximate and the conservation of the electric charge and the baryon and lepton quantum
number is approximate too. At present the corresponding conservation laws work with a high
accuracy because $p$ is very large (see below) and the dS energies are much less than $p$.
However, a reasonable possibility is that at early stages of the Universe $p$ was not as large as now.
This might explain the problem known as the baryon asymmetry of the Universe (see Ref.
\cite{monograph} for a detailed discussion).

\subsection{Vacuum energy in FQT}

The vacuum energy problem is discussed in practically
every textbook on quantum field theory. Its essence is as follows.
After quantization the energy operator can be written in the form $E={\tilde E}+E_{vac}$
where ${\tilde E}$ has the normal form (when creation operators always precede annihilation
ones) and $E_{vac}$ is a constant. In the vacuum state, when particles are absent, the energy equals
$E_{vac}$ and therefore $E_{vac}$ should be zero. However, the actual calculation
shows that it is infinite. This is an indication
that standard theory has consistency problems.

In FQT for calculating the vacuum energy
one should break all possible states into two parts which can be treated as physical
and nonphysical ones, respectively. As explained in Ref. \cite{monograph}, this can be achieved
only for fermions with the mass $m$ and spin $s$ such that in dS units $f(m)$ and $f(s)$ are odd. Then
a direct calculation (see Ref. \cite{monograph}) gives that
\begin{equation}
E_{vac}=(m-3)(s-1)(s+1)^2(s+3)/96
\end{equation}

Our conclusion is that while in standard theory the vacuum energy is
infinite, in FQT it is not only finite (in finite mathematics it
cannot be infinite) but is exactly zero if $s=1$ (i.e. $s=1/2$ in the usual units). Note
that if $p$ is treated
only as a regulator
then the vacuum energy would be a quantity which depends on $p$ and becomes infinitely
large in the formal limit $p\to\infty$. However, since the rules of arithmetic in finite mathematics are
different from those for complex numbers the vacuum energy is exactly zero as it should be.

Existence of infinities is one
of the main problems in constructing standard quantum theory. However, in FQT infinities
cannot exist in principle and the above example is a clear demonstration of
this fact.

\subsection{Cosmological constant and gravity}
\label{gravity}

The philosophy of general relativity (GR) is that the curvature of space-time is defined by
matter in that space-time. Therefore empty space-time should be flat, i.e. the cosmological
constant (CC) $\Lambda$ should be zero. This was one of the subjects of the debates
between Einstein and
de Sitter. However, the data on the cosmological acceleration are interpreted such that
$\Lambda >0$ with the accuracy better than 5\%. To reconcile this fact with the requirement
$\Lambda=0$ the term with $\Lambda$ in the Einstein equations is moved from the
l.h.s. to the r.h.s. and is interpreted not as the curvature of empty space-time but as
dark energy.

In quantum field theory one starts from the choice of the space-time background. The background has
the symmetry group and the operators characterizing the system under consideration should
satisfy the commutation relation of the Lie algebra for this group. By analogy with GR
it is believed that the choice of the Minkowski background is more physical than the choice
of the dS one and that the goal of quantum gravity is to explain the
value of $\Lambda$. The existing quantum theory of gravity contains strong
divergencies and with a reasonable cutoff the theory gives for $\Lambda$ a value exceeding
the experimental one by 122 orders of magnitude. This is called the CC problem.

However, the physical meaning of the curvature is to describe the motions of bodies. Therefore
the curvature of empty space-time is only a mathematical notion which does not a
physical meaning. As argued in Ref. \cite{PRD}, the
approach should be opposite to the standard one. Every quantum system is described by a set of
operators which somehow commute with each other and the rules of their commutation define
the symmetry algebra. Therefore in quantum theory one should start not from the space-time
background, which is the classical notion, but from the symmetry algebra. From this
point of view the dS symmetry is more preferable than the Poincare one because
the Poincare algebra is less symmetric than the dS one and can be obtained from
the latter by contraction.

In Poincare invariant theory the mass operator of the free two-body system depends
only on relative momenta but not on relative distances. As a consequence, in semiclassical
approximation the relative acceleration of the bodies is zero. However, in dS theory the
mass operator of the FREE two-body system depends on relative momenta and distances. As
shown in Ref. \cite{JPA}, the result for
the relative acceleration is the same as in GR for the dS background. This result has been
obtained without using space-time background and Riemannian geometry
(metric tensor, connection etc.) but only in the framework of a standard quantum mechanical calculation. In this approach a nonzero value of $\Lambda$ arises not as the
curvature of the background space-time but as a consequence of dS symmetry on quantum
level in semiclassical approximation. In this approach the CC problem does not arise and
for explaining the cosmological acceleration there is no need to involve empty space-time and
dark energy.

In dS theory the spectrum of the FREE two-body mass operator is not bounded below by
$m_1+m_2$, where $m_1$ and $m_2$ are the masses of the particles, but contains
values less than $m_1+m_2$. There is no law prohibiting that in semiclassical approximation
the mean value of the FREE mass operator contains the term $-Gm_1m_2/r$ with possible
corrections. Here $r$ is the
relative distance and $G$ is not a quantity taken from the outside but a value which should
be calculated.

As shown in Ref. \cite{monograph}, for macroscopic bodies standard distance operator
is semiclassical only at cosmological distances. Therefore this operator should be
modified. We propose a new distance operator which satisfies all the required properties.
Then a detailed calculation \cite{monograph} gives that in quantum theory based on representations of
the dS algebra the mean value of the Hamiltonian for a system of two free nonrelativistic bodies is
given by
\begin{equation}
H = H_0 - \frac{Cm_1m_2}{(m_1+m_2)r}(\frac{1}{\delta_1}+\frac{1}{\delta_2})
\label{dS}
\end{equation}
where $H_0$ is the free Hamiltonian, $C$ is a constant and $\delta_i$ ($i=1,2)$
is the width of the dS momentum distribution for body $i$.
The last term in Eq. (\ref{dS}) represents the de Sitter correction to the standard expression.
We see that the correction disappears if the width of the
momentum distribution for each body becomes very large. In standard theory
there is no limitation on the width and this correction is negligible.

However, in FQT the width cannot be arbitrarily large.
Suppose that a macroscopic body
consists of $N$ components and  $\delta_j$ ($j=1,2,...N$) is the width of the momentum distribution
of the $j$th component with the mass $m_j$. Then, as shown in Ref. \cite{monograph}, a
necessary condition for a wave
function to have a probabilistic interpretation is
\begin{equation}
R\sum_{j=1}^N \delta_j lnw_j \ll lnp
\label{70}
\end{equation}
where $R$ is the dS radius (the radius of the Universe) and $w_j=4R^2m_j^2$.
This condition shows that the greater the number of components is,
the stronger is the restriction on the width of the momentum distribution for each component.
This  is a crucial difference between standard theory and FQT. A naive explanation
is that if $p$ is
finite, the same set of numbers which was used for describing one body is now shared between $N$ bodies.
In other words, if in standard theory each body in the free $N$-body system does not feel the presence of
other bodies, in FQT this is not the case.

The existing theory does not make it possible to reliably calculate the width of the total momentum
distribution for a macroscopic body and at best only a qualitative estimation of this quantity can be
given. Equation (\ref{70}) indicates that the quantities $\delta_i$ in Eq. (\ref{dS}) are inversely
proportional to the corresponding masses $m_i$ in agreement with the Newton law.
A detailed discussion in Ref. \cite{monograph} shows that  with reasonable assumptions
the result given by
Eq. (\ref{dS}) can be written in the form $H=H_0-Gm_1m_2/r$ where $G=const\, R/(m_0lnp)$
and $m_0$ is the nucleon mass. We also discuss whether relativistic corrections to
the Newton gravity law are compatible with GR.

We conclude that in FQT gravity can be treated not as an interaction but simply
as a consequence of the fact that $p$ is finite. If we assume that $const$ is of the order of unity and take for $R$ a reasonable value $R=10^{26}m$ then the comparison with
the experimental value of $G$ gives that $lnp$ is of the order of $10^{80}$. Therefore $p$ is a huge
number of the order of $exp(10^{80})$.

\subsection{Ring or field?}

In standard quantum theory states are described by elements of Hilbert spaces. Such spaces
are linear spaces over a field of complex numbers. A field is a set with four operations: addition,
subtraction, multiplication and division. In FQT linear spaces can be over either finite rings or finite
fields. A ring is a set with three operations: addition, subtraction and multiplication. Well known
facts from standard algebra are that invariance of dimension, basis and linear independence are well defined
only in spaces over a field or body. In addition, existence of division is often convenient for
calculations.

At the same time, as argued in Sec. \ref{intro}, in quantum theory division is not fundamental.
History of physics tells us that it is desirable to construct physical theories with the least required
notions. Therefore a problem arises whether ultimate quantum theory can be constructed
without using division at all. For the first time this possibility has been discussed in Ref.
\cite{Saniga}.

As shown in Ref. \cite{monograph}, modular IRs describing massive and massless particles
can be constructed only in spaces over a field. However, in Ref. \cite{DiracS} titled
"A Remarkable Representation of the 3 + 2 de Sitter group" Dirac discovered
the existence of a new type of particles - Dirac singletons. In Standard Model only massless
particles are fundamental but, as shown in Ref. \cite{FF}, massless particles can be constructed
from singletons. This poses a problem whether singletons are the only true fundamental
particles.

As discussed in Ref. \cite{monograph}, in FQT Dirac singletons are even more remarkable
than in standard theory and the singleton physics can be constructed only over a ring.
This poses a problem whether the ultimate quantum theory will be constructed over a
ring, not a field.

\section{Discussion and conclusion}
\label{conclusion}

In Sec. \ref{intro} we argue that classical mathematics is a degenerate case of finite one in the formal limit
$p\to\infty$ and that ultimate quantum theory will be based on finite mathematics. The results described in Sec. \ref{S1} can be treated as arguments in favor of this statement.

The estimation of the gravitational constant shows that at present physics in our Universe is described
by finite mathematics such that $p$ is a huge number of the order of $exp(10^{80})$. Nevertheless, gravity is
a manifestation of the fact that $p$ is finite and not infinite. The matter is that the gravitational constant
depends on $p$ as $1/lnp$. Therefore in the formal limit $p\to\infty$ this constant disappears.
The fact that $p$ is a huge number explains why in many cases classical mathematics describes natural phenomena with a very high accuracy.
At the same time, the above discussion shows that the explanation of several phenomena can be given only
in the theory where $p$ is finite.

Although classical mathematics is a degenerate case of finite one, a problem arises
whether classical mathematics can be substantiated as an abstract science.
It is well-known that, in spite of great efforts of many great mathematicians, the problem of foundation of
classical mathematics has not been solved. For example, G\"{o}del's incompleteness theorems state that no system of axioms can ensure that all facts about natural numbers can be proven and the system of axioms in classical mathematics cannot demonstrate its own consistency.

The philosophy of Cantor, Fraenkel, G\"{o}del, Hilbert, Kronecker, Russell, Zermelo and
other great mathematicians was based on macroscopic experience in which the
notions of infinitely small, infinitely large, continuity and standard division are natural.
However, as noted above, those notions contradict the existence of elementary particles and are not natural
in quantum theory. The illusion of continuity arises when one neglects the discrete structure of matter.

However, since classical mathematics is a special degenerate case of finite one,
foundational problems in this mathematics do not have a fundamental role and
classical mathematics can be treated only as a
technique which in many cases (but not all of them) describes reality with a
high accuracy.

{\bf Acknowledgments:} I am grateful to participants of the Fq12 Conference, Volodya Netchitailo
and Metod Saniga for important remarks and discussions.