    \documentclass[english]{jnlp_1.4}

\usepackage{jnlpbbl_1.3}
\usepackage[dvipdfmx]{graphicx}
\usepackage{amsmath}
\usepackage{hangcaption_jnlp}
\usepackage{array}

\usepackage{algorithm}
\usepackage{algpseudocode}


\Volume{24}
\Number{3}
\Month{June}
\Year{2017}

\received{2016}{9}{17}
\revised{2016}{12}{7}
\rerevised{2017}{2}{13}
\accepted{2017}{3}{31}

\setcounter{page}{395}

\etitle{Generalized Hierarchical Word Sequence Framework for Language Modeling}
\eauthor{Xiaoyi Wu\affiref{Author_1} \and Kevin Duh\affiref{Author_2}  \and Yuji Matsumoto\affiref{Author_1}} 
\eabstract{
Language modeling is a fundamental research problem that has wide application for many NLP tasks. For estimating probabilities of natural language sentences, most research on language modeling use n-gram based approaches to factor sentence probabilities. However, the assumption under n-gram models is not robust enough to cope with the data sparseness problem, which affects the final performance of language models. In this paper, we propose a generalized hierarchical word sequence framework, where different word association scores can be adopted to rearrange word sequences in a totally unsupervised fashion. Unlike the n-gram which factors sentence probability from left-to-right, our model factors using a more flexible strategy. For evaluation, we compare our rearranged word sequences to normal n-gram word sequences. Both intrinsic and extrinsic experiments verify that our language model can achieve better performance, proving that our method can be considered as a better alternative for n-gram language models.
}
\ekeywords{Language Modeling, Sparseness Problem, Cognitive Grammar, Hierarchical Word Sequence (HWS), Word Association Measures}

\headauthor{Wu, Duh, Matsumoto}
\headtitle{Generalized HWS Framework for Language Modeling}

\affilabel{Author_1}{}{NARA Institute of Science and Technology}
\affilabel{Author_2}{}{Johns Hopkins University}


\begin{document}

\maketitle

\vspace{0.3\Cvs}
\section{Introduction}
\label{sec:Introduction}

Probabilistic Language Modeling is a fundamental research direction of Natural Language Processing. It is widely used in various application such as machine translation \cite{brown1990}, spelling correction \cite{mays1991}, speech recognition \cite{rabiner1993}, word prediction \cite{bickel2005} and so on.

Most research about Probabilistic Language Modeling, such as Katz back-off \cite{katz1987}, Kneser-Ney \cite{kneser1995}, and modified Kneser-Ney \cite{chen1999}, only focus on smoothing methods because they all take the n-gram approach \cite{shannon1948} as a default setting for modeling word sequences in a sentence. Yet even with 30
years worth of newswire text, more than one third of all trigrams are still unseen \cite{allison2005}, which cannot be distinguished accurately even using a high-performance smoothing method such as modified Kneser-Ney (abbreviated as MKN). 

An alternative solution is to factor the language model probabilities such that the number of unseen sequences are reduced. It is necessary to extract them in another way, instead of only using the information of left-to-right continuous word order.

In \cite{guthrie2006}, skip-gram \cite{huang1993}\footnote{The k-skip-n-grams for a sentence $w_{1},...w_{m}$ is defined as the set $\{w_{i_{1}},w_{i_{2}},...w_{i_{n}}|\Sigma_{j=1}^{n}i_{j}-i_{j-1}<k\}$.} is proposed to overcome the data sparseness problem. For each n-gram word sequence, the skip-gram model enumerates all possible word combinations to increase valid sequences. This has truly helped to decrease the unseen sequences, but we should not neglect the fact that it also brings a greatly increase of processing time and redundant contexts. 

In \cite{wu2014}, we propose a heuristic approach to convert any raw sentence into a hierarchical word sequence (abbreviated as HWS) structure, by which much more valid word sequences can be modeled while remaining the model size as small as that of n-gram. In \cite{wu2015a,wu2015b}, instead of only using the information of word frequency, we also use the information of direction and word association to construct higher quality HWS structures. However, they are all specific methods based on certain heuristic assumptions. For the purpose of further improvements, it is also necessary to generalize those models into one unified framework under an integrated theory.

In this paper, inspired by the view point of sentence generation process from cognitive grammar, proposed by Langacker \cite{langacker1986,langacker1999,langacker2008}, we propose a generalized hierarchical word sequence framework, by which various word association scores can be used for rearranging word sequences for language modeling. Then we use both intrinsic and extrinsic experiments to verify the effectiveness of these strategies.

The paper makes the following scientific contributions:

1) We present a generalized hierarchical word sequence framework, extending our previous work on specific HWS methods. 

2) We adopt various association scores for rearranging word sequences  and empirically verify their better performance in comparison to n-grams (including skip-n-grams) in language modeling. 

This paper is organized as follows. In Section \ref{sec:cg_adv}, we introduce the basic idea of cognitive grammar structure and convert it into a special dependency structure. We also discuss its advantage in language modeling. Then inspired by this idea, we propose the HWS language model and present a generalized framework in Section \ref{sec:framework}. In Sections \ref{sec:inteva} and \ref{sec:exteva}, we show the effectiveness of our model by both intrinsic experiments and extrinsic experiments. Finally, we summarize our findings in Section \ref{sec:conclusion}.


\section{Cognitive Grammar Structure and Its Advantage}
\label{sec:cg_adv}

\subsection{Cognitive Grammar Structure and CG-based Dependency Structure}
\label{sec:review_cg}

The structure of cognitive grammar is proposed by Langacker \cite{langacker1986,langacker1999,langacker2008}. In cognitive grammar, it is presumed that complex expressions are formed from schematic patterns, such as `$V_{s}$ $X$ in the $N_{b}$' \footnote{$V_{s}$ represents `strike motion', while $N_{b}$ represents `body part'.} and `$a$ $N_{1}$+less $N_{2}$', which are called `{\em schemas}'.

\begin{quote}
``They\footnote{Schemas.} are not themselves full-fledged expressions but patterns abstracted from them and potentially used in forming new ones. To this extent they are grammar-like, since grammar by definition comprises the patterns used in forming complex expressions.'' \cite[p.~20]{langacker2008}
\end{quote}

This quote not only means that schemas are the core units of cognitive grammar, but also indicates that schemas are relative concepts. From a schema, a more specific expression can be instantiated, while a more schematic expression can also be abstracted.

An example is given in \cite[p.~21]{langacker2008} as $\langle V_s$ $X$ in the $N_b \rangle$$\rightarrow$$\langle$kick $X$ in the shin$\rangle$$\rightarrow$$\langle$kick my pet giraffe in the shin$\rangle$\footnote{In this example, Langacker regards `my pet giraffe' as one whole unit. In fact, it can also be further abstracted as schema `my $N_{possession}$' on the principle of cognitive grammar.}. In this example, $\langle$$V_s$ $X$ in the $N_b$$\rangle$ is the schema with the highest schematicity, while the schema $\langle$kick $X$ in the shin$\rangle$ is a more specific one. The structure of cognitive grammar is shown in Figure \ref{fig:st_cg}.

\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia4f1.eps}
\end{center}
\caption{An example of structure of cognitive grammar}
\label{fig:st_cg}
\end{figure}

For the purpose of applying this structure to language modeling, we use following processing to simplify and convert it into a special dependency structure.

In the cognitive grammar structure, schemas are gradually specified from more schematic patterns to less schematic ones. Locally, constituencies are hierarchically generated from certain positions of patterns. Taking Figure \ref{fig:st_cg} as the example, `shin' depends on the category `$N_{b}$', which is a part of schema $\langle V_s$ $X$ in the $N_b \rangle$. Since $N_{b}$ is always on the certain position of schema $\langle V_s$ $X$ in the $N_b \rangle$, if we keep the word order information, then we can remove the category part from this schema and simply assume that `shin' depends on `in the'.

Further, in a categories-removed schema, such as `in the' in above step, we assume following words depends on their preceding words, then `the' depends on `in'.

Applying above processing hierarchically, the cognitive grammar structure given in the Figure \ref{fig:st_cg} can be converted into a special dependency structure as shown in Figure \ref{fig:st_fin}. We call such kind of dependency structure as {\em CG-based dependency structure} in order to distinguish it from the conventional dependency grammar structure and cognitive grammar structure.

\begin{figure}[t]
\begin{center}
\includegraphics{24-3ia4f2.eps}
\end{center}
\caption{An example of CG-based dependency structure}
\label{fig:st_fin}
\end{figure}


\subsection{The Advantages of CG-based Dependency Structure in Language Modeling}
\label{sec:advance_cg}

Due to the generativity (also called productivity) of language, it is difficult to calculate the probability of a whole sentence directly. A more practical way is to divide the sentence into some sequences of words and to compute the joint probability using the Chain Rule. Thus, the performance of language models depend largely on how to arrange those word sequences, more specifically, for each word in one sentence, how to determine its context. Theoretically, the more accurately we can determine the context for each word, the more those word sequences can reflect the real process of sentence generation, consequently, the higher performance the language models can achieve.

We take an example from WSJ corpus and convert it into different structures to demonstrate the difference among n-grams, dependency grammar and CG-based structure in arranging word sequences. In each structure of Figure \ref{fig:st_demodif}, arrows represent the sentence generation process (in n-gram model, generation process is equivalent to word order), thus, the parent nodes could be considered as the context of their child node, and word sequences can be arranged as (parent nodes, child node).

\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia4f3.eps}
\end{center}
\hangcaption{A demonstration of the difference among (a) n-gram, (b) dependency Grammar and (c) CG-based structure on sentence generation process}
\label{fig:st_demodif}
\end{figure}

As shown in Figure \ref {fig:st_demodif}~(a), n-gram language models adopt an {\bf utterance-oriented} way to determine word sequences, which assume that the preceding n-1 words are the context of each word in the sentence. In the actual utterance, signals are indeed generated one by one, however, for each word in a sentence, not all its previous n-1 words actually take part in its generation. Words can also be generated from their following words or even long-distance words. This is why n-gram models suffer from a severe sparseness problem. Taking `as important as' in this sentence as an example, the second `as' coexists with the first `as' but not generated from `important'. Thus, relative to `as...as', `important' here is quite easy to be replaced by other words, such as `fast', `high', `much' and so on. Consequently, even using 4-gram or 5-gram, sequences consisting of `important' and its nearby words tend to be low-frequent because the connection of `as...as' is interrupted.

By contrast, dependency grammar adopt a {\bf predicate-oriented} way to determine word sequences, which assumes compliments and adjuncts depend on predicate words, modifiers depend on modified words. The dependency relations are discontinuous so that long distance information can be used for predicting and generating the next word. However, the predicate-oriented assumption doesn't work accurately in every case. For example, In Figure~\ref{fig:st_demodif}~(b), the period `.' depends on predicate `is'. However, `.' appears in every declarative sentence, while not all declarative sentences use `is' as their predicate word, which indicates that period `.' is not actually generated from predicate `is'. Similar dependency problem also happens on coordinating conjunction `and'. Such kind of inaccuracy is inevitable as long as predicate-oriented assumption is adopted. 

At this point, CG-based dependency structure is based on {\bf pattern-oriented} assumption, which treats schematic patterns as grammatical units and assumes that words are hierarchically generated from certain positions of them. As a result, it can use long distance information to generate and predict words, and words which do not actually take part in the generation can be filtered out from contexts. As shown in Figure~\ref{fig:st_demodif}~(c), `is as ... as' is regarded as a pattern context to generate `important', which is closer to our linguistic intuition. Practically, even `important' is replaced by another word, the expression `is as...as' won't be affected. Furthermore, even `is' is replaced by other verbs, we can still hierarchically back-off to pattern `as ... as', which make it more flexible to the data sparseness problem.  

The pattern-oriented assumption also brings another advantage. Different from strictly-defined predicate words, a schematic pattern is a relative concept, which makes it possible to be modeled unsupervisedly. Thus, compared to other structure-based language models, such as class-based language model \cite{brown1992}, structured language model \cite{chelba1997}, factored language model (FLM) \cite{bilmes2003} and dependency tree language model \cite{shen2008,chen2012}, the pattern-oriented language model doesn't use any specific linguistic knowledge or any abstracted categories, which makes it possible to be trained in a totally unsupervised fashion. 


\section{A Generalized Framework for HWS}
\label{sec:framework}

\subsection{HWS Language Model}
\label{sec:review_hws}

As described in Section \ref{sec:review_cg}, cognitive grammar structure is a hierarchical pattern structure, in which specific expressions are hierarchically generated from more schematic patterns. Thus, in CG-based dependency structure, which is converted from cognitive grammar structure, specific words hierarchically depend on more schematic words. Since the more frequently a word is used, the more probable it becomes part of a pattern, heuristically, we can use the information of word frequency and word order to approximately construct a CG-based dependency structure.

Based on this idea, in \cite{wu2014}, we constructed the {\em HWS structure} in an unsupervised way as follows:

Step 1: Calculate word frequencies from training data and sort all these words by frequency. Then we can get a frequency-sorted list $V = \{v_{1}, v_{2}, ..., v_{m}\}$.

Step 2: According to $V$, for each sentence ${s = w_{1}, w_{2}, ..., w_{n}}$, the most frequently used word ${w_{i}\in s (1\leq i \leq n)}$ is determined.\footnote{If $w_{i}$ appears multiple times in $s$, then select the first one.} Then use $w_{i}$ to split $s$ into two substrings ${s_{l} = w_{1}, ..., w_{i-1}}$ and ${s_{r} = w_{i+1}, ..., w_{n}}$.

Step 3: Set $s' = s_{l}$ and $s'' = s_{r}$, then repeat Step 2 separately. The most frequently used words $w_{j}\in s_{l} (1\leq j \leq i-1)$ and ${w_{k}\in s_{r}(i+1\leq k \leq n)}$ can also be determined, by which $s_{l}$ and $s_{r}$ are split into two smaller substrings separately. 

Executing Step~2 and Step~3 recursively until all the substrings become empty strings, then a binary tree $T = (\{w_{i}, w_{j}, w_{k}, ...\}, \{(w_{i}, w_{j}), (w_{i}, w_{k}), ...\})$ can be constructed, which is defined as an {\em HWS structure}.

In an HWS structure $T$, assuming that each node depends on its preceding n-1 parent nodes, then special n-grams can be trained. Such kind of n-grams are defined as {\em HWS-n-grams}.

Thus, the HWS language model \cite{wu2014} is essentially a special n-gram model with a different assumption. A normal n-gram model assumes that each word depends on its {\em preceding} n-1 words, while an HWS model assumes that each word depends on its n-1 {\em nearby high-frequency} words, which can be regarded as an approximation of the pattern-oriented assumption.


\subsection{Generalized Priority List}
\label{sec:gplnst}

HWS-n-grams are extracted from HWS structures, while HWS structures are constructed by a frequency-sorted vocabulary list $V = \{v_{1},v_{2},...,v_{m}\}$. Once $V$ is given, the HWS structures and HWS-n-grams are deterministic. Thus, the performance of HWS model is totally determined by $V$. $V$ is actually a priority list for constructing HWS structures.  Given a sentence $s$, we first judge whether $v_{1}\in s$, if not, then we check whether $v_{2}\in s$, until we find $v_{i}\in s (1\leq i \leq m)$ and use it to divide $s$ into two substrings. 

Since the priorities of $V$ are only arranged by word frequency, which is independent, it is not sufficient to construct high-quality hierarchical pattern structures because the words constitute a pattern, such as `... too ... to ...', are always dependent and word-order sensitive. For the purpose of improving the construction of HWS structures, we generalize the priority list $V$ with directional context information.

Context $c$ is defined as $a^{D}$($D \in \{L,R,N\}$), where $a$ represents a word and ${L,R}$ represents the relative word-order direction (left or right) of the words generated from it (which can be discontinuous). We also use a special tag $N$ to represent that $a$ has no directional relations but only priority relations with its following words. We define $ROOT^{R}$ as the default context where every word generated and $\varepsilon$ as an empty context where no more words generated. Obviously, each priority list starts from $ROOT^{R}$ and ends with $\varepsilon$. Thus, in original HWS method, priority list $V = \{v_{1},v_{2},...,v_{m}\}$ is actually $\hat{V} = \{ROOT^{R}, v_{1}^{N},v_{2}^{N},...,v_{m}^{N}, \varepsilon\}$, which is a special case of this generalization.

Suppose word $a_{1}$ is the highest priority word under $ROOT^{R}$, then we have three new contexts $\{a_{1}^{L}, a_{1}^{R}, a_{1}^{N}\}$. Under each context, suppose the next highest priority word is $a_{2}$, $a_{3}$ and $a_{4}$ separately, then we have three branched priority lists start from $\{ROOT^{R}, a_{1}^{L},a_{2}\}$, $\{ROOT^{R}, a_{1}^{R},a_{3}\}$ and $\{ROOT^{R}, a_{1}^{N},a_{4}\}$. Hierarchically, word $a_{2}$, $a_{3}$ and $a_{4}$ can be treated as new contexts by adding $\{L, R, N\}$ and the priority lists are further branched until no more words generated. Then we can get a multiset\footnote{As the pattern `$... as ... as ...$', the same word are allowed to repeat as different nodes.} of word nodes $M = \{ROOT, a_{1}, a_{2}, a_{3}, a_{4}, ...\}$ and a set of edges $E = \{(ROOT^{R},a_{1}),(a_{1}^{L}, a_{2}),$ $(a_{1}^{R}, a_{3}),$ $(a_{1}^{N},$ $a_{4}), ...\})$. Finally, a tree $T = (M, E)$ can be constructed, which is defined as a {\em Node Selection Tree} (abbreviated as NST).

A mini NST is shown in Figure \ref{fig:dt}, given this NST and a substring between `as' and `as', which corresponds to contexts `$\{as^{R},as^{L}\}$', we first judge whether `soon' is in this substring, if not, then we check `well' in turn. Thus, NST is essentially a decision tree to decide the word priority used for constructing the HWS structures. In an NST, each branch represents the relative position to all its parent nodes, the path from root to node represents hierarchical `priority list'.

With the generalized priority list NST, The HWS framework can be generalized as following 4 steps (Figure \ref{fig:fw}):

\begin{figure}[t]
\begin{center}
\includegraphics{24-3ia4f4.eps}
\end{center}
\caption{A mini example of node selection tree}
\label{fig:dt}
\end{figure}
\begin{figure}[t]
\begin{center}
\includegraphics{24-3ia4f5.eps}
\end{center}
\caption{Generalized HWS framework}
\label{fig:fw}
\end{figure}

\textbf{Step 1: Construct an NST.} Instead of frequency-sorted word list, we construct an Node Selection Tree (NST) and use the whole tree structure as the `priority list' $V$. We will discuss how to construct an NST from a raw corpus in Section \ref{sec:dt}.

\textbf{Step 2: Construct HWS structures via NST.}  Then we use the NST constructed in Step 1 to construct HWS structures from raw sentences. We will introduce how to convert raw sentences into HWS structures by an NST in Section \ref{sec:convnst}.

\textbf{Step 3: Convert HWS structures to HWS-n-grams.}  Then we can extract HWS-n-grams from both training data and test data via HWS structures. In Section \ref{sec:cvhwsngrams}, we introduce how to extract HWS-n-grams from HWS structures.

\textbf{Step 4: Build HWS language model.} Finally, instead of conventional n-grams, we use HWS-n-grams to build language models.


\subsection{Construction of NST}
\label{sec:dt}

Suppose we are given a set of sentences $S$ for training, NST is constructed by the following steps.

\textbf{Step 1:} Adding `$\langle$ROOT$\rangle$' (which corresponds to the $ROOT^{R}$ defined in Section \ref{sec:gplnst}) to the beginning of each sentence and set it as the default context $c$ (also the root node of NST).

\textbf{Step 2:} For each word ${w\in \Omega}$ (where ${\Omega}$ is the vocabulary of ${S}$), we use a function $score(c, w)$ to decide the word priority under a context $c$.


For the purpose of constructing context-dependent hierarchical pattern structure as we described in Section \ref{sec:gplnst}, in this paper, we adopt two different word association scores as the function $score(c, w)$: Dice coefficient \cite{dice1945} (Equation (\ref{equation:was_db})) and T-score (Equation (\ref{equation:was_tb})).
\begin{gather}
score_{DB}(c, w) = \frac{2 \times C(c,w)}{C(c) + C(w)}
\label{equation:was_db} \\[1ex]
score_{TB}(c, w) = (C(c, w) - \frac{C(c) \times C(w)}{V}) \div \sqrt{C(c, w)}
\label{equation:was_tb}
\end{gather}

\textbf{Step 3:} According to these scores, we choose the word with maximum score $\hat{w}$ as the child node of the root node `$\langle$ROOT$\rangle$'. For each sentence $s\in S$, if $\hat{w}\notin s$, then we put $s$ under the `N' arc of $\hat{w}$, otherwise, we use the first $\hat{w}$ appeared in $s$ to split $s$ into 2 substrings $s_{l}$ and $s_{r}$, then put $s_{l}$ and $s_{r}$ under the `L' arc and `R' arc of $\hat{w}$ separately. Finally, all strings (or substrings) of $S$ are splitted by three types of arcs of $\hat{w}$.

\textbf{Step 4:} Since each type of arc is branched by `L', `R' and `N', which represents the relative directions from $\hat{w}$, $\hat{w}$ itself can be considered as the context $\hat{w}^L$, $\hat{w}^R$ and $\hat{w}^N$ of each arc separately. Thus, for each arc, we set $\hat{w}$ as new context $c'$, all strings (or substrings) under this arc as a new corpus $S'$. Repeating Step 2 and Step 3 recursively, an NST is constructed.


This recursive process is shown in Algorithm \ref{alg:dt}.

\begin{algorithm}[t]
\caption{Constructing an NST from given corpus $S$}
\label{alg:dt}
\input{04algo01.txt}
\end{algorithm}


\subsection{Conversion of Raw Sentences into HWS Structures by Using a Constructed NST}
\label{sec:convnst}

With the NST constructed from a corpus, any sentence can be converted into an HWS structure. 

Suppose we use the NST shown in Figure \ref{fig:dt} to convert the sentence `as soon as possible' into an HWS structure. Firstly, we start from the node `as' and check whether it exists in this sentence. Although two `as's are observed in this sentence, we use the first one to divide it and take the right substring `soon as possible' to the `R' arc. Since the child node `as' of `R' arc can also be observed in this substring, `soon' and `possible' are classified to its `L' arc and `R' arc respectively. Finally, `as soon as possible' is converted to the HWS structure as shown in Figure \ref{fig:comare}. Similarly, sentence `as fast as possible', `as well as me' can also be converted into HWS structures by this NST.

\begin{figure}[t]
\begin{center}
\includegraphics{24-3ia4f6.eps}
\end{center}
\caption{Conversion of raw sentences to HWS structure via NST}
\label{fig:comare}
\end{figure}

Notice that even a well-trained NST cannot cover all possible situations. For instance, suppose we use the above NST to convert sentence `as far as I could remember', although `I could remember' is correctly classified as `R' arc of the second `as' node, it cannot be further analyzed because this NST doesn't offer more details in this arc. In this case, we use the original HWS approach (by word frequency) to select nodes from substring `I could remember' as a covering of our method. This process is shown in Algorithm \ref{alg:cv}.


\subsection{Conversion of HWS Structures into HWS-n-grams}
\label{sec:cvhwsngrams}

For the root node of an HWS structure, we define that it depends on symbol  `$\langle s \rangle$'. We also use the symbol `$\langle /s \rangle$' to represent the end of generation. Then we can achieve special n-grams under the our framework. Taking the HWS structure of  Figure \ref{fig:comare} as the example, we can train 3-grams 
like \{($\langle s \rangle$, $\langle s \rangle$, as), ($\langle s \rangle$, as, as), (as, as, possible), (as, possible, $\langle /s \rangle$), (as, as, soon), (as, soon, $\langle /s \rangle$)\}.

In \cite{wu2015a}, we verified that the performance of hierarchical word sequence language model can be further improved by using directional information. Thus, in this paper, we defaultly use directional information to model word sequences. Then the above 3-grams should be \{($\langle s \rangle$, $\langle s \rangle$, as),   ($\langle s \rangle$, as-L, $\langle /s \rangle$), ($\langle s \rangle$,  as-R, as), (as-R, as-L, soon), (as-L, soon-L, $\langle /s \rangle$), (as-L, soon-R, $\langle /s \rangle$), (as-R, as-R, possible), (as-R, possible-L, $\langle /s \rangle$), (as-R, possible-R, $\langle /s \rangle$) and the probability of the whole sentence `as soon as possible' can be estimated by the product of conditional probabilities of all these word sequences.

\begin{algorithm}[t]
\caption{Converting a sentence $s$ into HWS structure using an NST $T$}
\label{alg:cv}
\input{04algo02.txt}
\end{algorithm}


\section{Intrinsic Evaluation}
\label{sec:inteva}

\subsection{Settings}
\label{sec:insettings}

We use two different corpus: {\bf British National Corpus} and {\bf English Gigaword Corpus}.

{\bf British National Corpus (BNC)}\footnote{http://www.natcorp.ox.ac.uk} is a 100 million word collection of samples of written and spoken English from a wide range of sources. We use all the 6,052,202 sentences (100 million words, 629,881 different types) for the training data.

{\bf English Gigaword Corpus}\footnote{https://catalog.ldc.upenn.edu/LDC2011T07} consists of over 1.7 billion words of English newswire from 4 distinct international sources. We choose the $wpb\_eng$ part (162,099 sentences, 20 million words, 181,523 different types, $\text{OOV}=\text{78,854}$) for the test data.

As preprocessing of the training data and the test data, we use the tokenizer of NLTK (Natural Language Toolkit)\footnote{http://www.nltk.org} to split raw English sentences into words. We also converted all words to lowercase. 


In \cite{wu2014}, we use {\bf coverage score} to perform evaluation. The word sequences modeled from training data are defined as TR, while that of test data as TE, then the coverage score is calculated by Equation (\ref{equation:coverage}). Obviously, the higher coverage score a language model can achieve, the more it can relieve the data sparseness problem (reduce the unseen sequences).
\begin{equation}
score_{coverage}=\frac{|TR \bigcap TE|}{|TE|}
\label{equation:coverage}
\end{equation}

If we enumerate all possible word combinations as word sequences, then we can achieve considerable coverage score. However, the processing efficiency of a model become extremely low. Thus, we also use {\bf usage score} (Equation (\ref{equation:usage})) to estimate how much redundancy is contained in a model. 
\begin{equation}
score_{usage}=\frac{|TR \bigcap TE|}{|TR|}
\label{equation:usage}
\end{equation}

A balanced measure between coverage and usage is calculated by Equation (\ref{equation:fscore}).
\begin{equation}
F\text{-}Score=\frac{2{\times}coverage{\times}usage}{coverage+usage}
\label{equation:fscore}
\end{equation}

As intrinsic evaluation of language modeling, perplexity \cite{manning1999} is also a common metric used for measuring the usefulness of a language model. In the following section, we also use perplexity to compare our models with other models.


\subsection{Results}
\label{sec:intresult}

We compare word sequences modeled under our framework with conventional n-gram sequences. 

First, we evaluate coverage and usage on unique word sequences, which means we count each word sequence only once  in spite of the amount of times it really occurs. The result is shown in Table \ref{table:unique}.

According to the results, the effectiveness and efficiency of NST-based bi-grams is nearly the same as that of normal bi-grams. But as for tri-grams, each NST-based method improves a lot on both coverage and usage.

We also execute the same experiment on total word sequences, which actually affect the final performance of language models. The result is shown in Table \ref{table:total}. The coverage and usage of NST-based unigrams are a little larger than normal unigrams because NST-based methods are not continuous and consequently has more ending symbol `$\langle /s \rangle$'s. Different from unique sequence experiment, even in bi-grams, NST-based methods have much better performance than the normal bi-gram model. As for tri-grams, the NST-based methods can even improve around 25\%.

\begin{table}[t]
\caption{Coverage and Usage on Unique Word Sequences}
\label{table:unique}
\input{04table01.txt}
\end{table}
\begin{table}[t]
\caption{Coverage and Usage on Total Word Sequences}
\label{table:total}
\input{04table02.txt}
\end{table}

We also use different portions of different sizes of BNC corpus. We gradually increase the amount of training data to examine how it affects the F-scores of word sequences. As show in Figure \ref{fig:portion}, all strategies improve along with the increasing of training data size. Also, all those methods increase at almost the same speed, even we increase the training data size to 100 million words, NST-based methods still have a great advantage over the normal n-gram models.

\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia4f7.eps}
\end{center}
\caption{The Increasing of F-scores on Total Word Sequences with the Addition of Training Data Size}
\label{fig:portion}
\end{figure}
\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia4f8.eps}
\end{center}
\caption{An example of English dependency structure (from CoNLL2007 shared task)}
\label{fig:exdanish}
\end{figure}

We also compare HWS to other models. For the purpose of comparing it with gold standard dependency grammar, we use the English part of CoNLL2007 shared task for the data set.\footnote{The types of words of training data is 26,600, while that of test data is 1,373. $\text{OOV} = 107$.} Dependency Grammar structure is compatible with HWS except it allows one-to-many dependency relations. Thus, given a English dependency structure shown in Figure \ref{fig:exdanish}, we can convert it into 3-gram word sequences with directional information as \{(has-L, date-L, a), (date-L, a-L, $\langle /s\rangle$), (date-L, a-R, $\langle /s\rangle$), (has-L, date-L, record), (date-L, record-L, $\langle /s\rangle$), (date-L, record-R, $\langle /s\rangle$), ($\langle s\rangle$, has-L date), (has-L, date-R, $\langle /s\rangle$), ($\langle s\rangle$, has), ($\langle s\rangle$, has-R n't), (has-R n't-L, $\langle /s\rangle$), (has-R n't-R, $\langle /s\rangle$), ($\langle s\rangle$, has-R, been), (has-R, been-L, $\langle /s\rangle$), (has-R, been-R, set), (been-R, set-L, $\langle /s\rangle$), (been-R, set-R, $\langle /s\rangle$), ($\langle s\rangle$, has-R, .), (has-R, .-L, $\langle /s\rangle$), (has-R, .-R, $\langle /s\rangle$)\}. The results of coverage and usage are shown in Table \ref{table:conll2007cuf}. For unique grams, our bi-gram model (db-based-bi) outperforms dependency grammar based bi-gram model, while its trigram model outperforms ours. For total grams, the results swap. We can also find that skip-gram models do improve coverage at the sacrifice of usage, but even we skip 3 words, proposed models still outperform skip-n-gram models on coverage.

Besides the coverage and usage, we also compare our model by evaluating other measures, such like occupied memory, processing time and perplexity. The results are summarized in Table~\ref{table:conll2007mtp}.

\begin{table}[b]
\caption{Coverage and Usage on English CoNLL2007 Shared Task Data Set (Unique/Total)}
\label{table:conll2007cuf}
\input{04table03.txt}
\end{table}
\begin{table}[b]
\caption{Other Performance on English CoNLL2007 Shared Task Data Set}
\label{table:conll2007mtp}
\input{04table04.txt}
\end{table}

Occupied memory: Compared to conventional trigram model, the size of skip-3-gram models grow fast
along with the increase of skip words. Since proposed model and dependency-based model adopt the directional information, which means almost each word $w$ are treated as two words $w$-L and $w$-R, their sizes are nearly the same as that of 1skip-3-gram model. But for proposed method, we have to use an extra memory to store the NST tree.

Processing time: We use a 3~GHz Intel Core i7, 16~GB 1600~MHz DDR3 computer to perform the experiment. For the time of conversion raw sentences into sequences, conventional n-gram is the fastest method, only costs 2,730~ms. Also, due to its smallest model size, its training time (MKN smoothing) only costs 10,101~ms too. Compared to skip-3-gram, proposed model performs much faster either on sequence conversion or smoothing, but additionally, it needs an extra step to train the NST from the training data, which is time-consuming.

Perplexity: Compare to conventional 3-gram model and skip-3-gram model, proposed model can reduce the perplexity largely. The dependency grammar based model outperforms our model slightly, but we use gold standard parsing results for the dependency grammar based model while using a totally unsupervised method for ours.

To clarify this, we compare our model to the generative dependency n-gram language model, which is proposed by \cite{ding2013}. In this paper, they propose an unsupervised method to construct dependency structures (generative dependency n-gram language model), by which parameters are estimated. For the datasets and the performance of their model, we use exactly the same as they described in their paper. The comparison results of perplexities are shown in Table \ref{table:ding}. Same as unsupervised methods, our model greatly outperforms the generative dependency n-gram language model. It is also verified that our model performs well on multiple languages.

\begin{table}[t]
\caption{The Perplexities of HWS Model and Generative Dependency N-gram Language Model}
\label{table:ding}
\input{04table05.txt}
\end{table}


\section{Extrinsic Evaluation}
\label{sec:exteva}

For the purpose of examining how our models work in the real world application, we also performed extrinsic experiments to evaluate our method. In this paper, we use the reranking of n-best translation candidates to examining how language models work in a statistical machine translation task.


\subsection{Settings}
\label{sec:exsettings}

We use the French-English part of TED talk parallel corpus\footnote{Which can also be downloaded at https://github.com/aisophie/HWS.} for the experiment dataset. The training data contains 139,761 sentence pairs, while the test data contains 1,617 sentence pairs. For training language models, we set English as the target language.

As for statistical machine translation toolkit, we use {\bf Moses system}\footnote{http://www.statmt.org/moses/} to train the translation model and output 50-best translation candidates for each French sentence of the test data. Then we use 139,761 English sentences to train language models. With these models, 50-best translation candidates are reranked. According to these reranking results, the performance of machine translation system is evaluated, which also means, the language models are evaluated indirectly. In this paper, we use the following measures for evaluating reranking results.

{\bf BLEU} \cite{papineni2002}: BLEU score measures how many words overlap in a given candidate translation when compared to a reference translation, which provides some insight into how good the fluency of the output from an engine will be.
 
{\bf METEOR} \cite{banerjee2005}: METEOR score computes a one-to-one alignment between matching words in a candidate translation and a reference.
 
{\bf TER} \cite{snover2006}: TER score measures the number of edits required to change a system output into one of the references, which gives an indication as to how much post-editing will be required on the translated output of an engine. 

We use open source tool {\bf multeval}\footnote{https://github.com/jhclark/multeval} to perform the evaluation.


\subsection{Results}
\label{sec:extresult}

We use various association scores to perform experiments and compared them to the normal n-gram strategy. For estimating the probabilities of translation candidates, we use the modified Kneser-Ney smoothing (MKN\footnote{The technical detail of MKN is shown in the Appendix.}) as the smoothing method of all strategies. As shown in Table~\ref{table:smt_small}, NST-based strategies outperform that of n-gram on each score.

To examine our methods on other languages, we also perform the same experiment on Spanish-English, Japanese-English and Chinese-English dataset. As shown in Table \ref{table:smt_es}, for each language pair, NST-based strategies still outperform n-gram strategy on all the three measures, especially with an obvious improvement on TER score. 

\begin{table}[t]
\caption{Performance on French-English SMT Task Using Various Word Arranging Strategies}
\label{table:smt_small}
\input{04table06.txt}
\end{table}
\begin{table}[t]
\hangcaption{Performance on Spanish-English, Japanese-English and Chinese-English SMT Task Using \mbox{Various} Word Arranging Strategies}
\label{table:smt_es}
\input{04table07.txt}
\end{table}


\subsection{Analasis}
\label{sec:smtana}

For the purpose of clarifying the effect of the proposed model, we take below example to reveal how reranking task benefits from HWS.

The best candidate outputted by n-gram model is ``and he has around 70's .'', while the result given by HWS model is ``and there are about 70 of them .'', which is a better translation.

The reason why n-gram model select ``and he has around 70's .'' is that `70' is an OOV and n-gram estimate sentence probabilities in a continuous way. Consequently, even `there are about $\langle NUMBER \rangle$ of them' is quite a  common expression, its probability is still assigned much smaller.

On the other hand, HWS estimates the probability of this sentence by the following sequences.

\{($\langle s\rangle$, .), ($\langle s\rangle$, .-L, are), (.-L, are-L, there), (are-L, there-L, and), (there-L, and-L, $\langle /s\rangle$), (there-L, and-R ,$\langle /s\rangle$), (are-L, there-R, $\langle /s\rangle$), (.-L, are-R, of), (are-R, of-L, about), (of-L, about-L, $\langle /s\rangle$), (of-L, about-R, 70), (about-R, 70-L, $\langle /s\rangle$), (about-R, 70-R, $\langle /s\rangle$), (are-R, of-R, them), (of-R, them-L, $\langle /s\rangle$), (of-R, them-R, $\langle /s\rangle$), ($\langle s\rangle$, .-R, $\langle /s\rangle$)\}

Among these sequences, patterns such like  ``... there are ... .'', ``... are ... of ... .'', which repeatedly appear in the training data, are assigned bigger possibilities. And sequences including OOV `70', such like  (of-L, about-R, 70), are actually calculated as how likely an unknown word generated from pattern ``about ... of''. Also, unlike n-gram models, this OOV won't affect `them' at all because `them' is generated from patten ``are ... of ...''.

Compare to conventional n-gram models, HWS models make it possible to take advantage of repeated patterns (including long distance ones) for word prediction and probability estimation. As a result, HWS models select more natural translation candidate as the output.


\section{Conclusion}
\label{sec:conclusion}

In this paper, inspired by the basic idea and structure of cognitive grammar, we proposed a generalized hierarchical word sequence framework for language modeling. Under this framework, we adopt different kinds of association scores for rearranging word sequences.

For evaluation, we compared our rearranged word sequences to conventional n-gram word sequences and performed intrinsic and extrinsic experiments. The intrinsic experiment proved that our methods can greatly relieve the data sparseness problem, while the extrinsic experiments proved that SMT tasks can benefit from our strategies. Both verified that language modeling can achieve better performance by using our word sequences rearranging strategies.

But on the other hand, our model needs an extra process for training NST, also an extra space for storing it, which is relatively more time-consuming and memory-consuming than conventional n-gram models. Also, since HWS structure has to be constructed after reading the whole sentence, it is not appropriate to apply it in some instant applications, such like speech recognition. Despite these two disadvantages, we recommend to replace conventional n-grams with HWS-n-grams under all kinds of NLP applications.

Further, instead of conventional n-gram word sequences, our rearranged word sequences can also be used as the features of various kinds of machine learning approaches, which is an interesting future study.


\bibliographystyle{jnlpbbl_1.5}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Allison, Guthrie, Guthrie, Liu, \BBA\ Wilks}{Allison
  et~al.}{2005}]{allison2005}
Allison, B., Guthrie, D., Guthrie, L., Liu, W., \BBA\ Wilks, Y. \BBOP
  2005\BBCP.
\newblock {\Bem Quantifying the Likelihood of Unseen Events: A further look at
  the data Sparsity problem}.
\newblock Awaiting publication.

\bibitem[\protect\BCAY{Banerjee \BBA\ Lavie}{Banerjee \BBA\
  Lavie}{2005}]{banerjee2005}
Banerjee, S.\BBACOMMA\ \BBA\ Lavie, A. \BBOP 2005\BBCP.
\newblock \BBOQ METEOR: An Automatic Metric for MT Evaluation with Improved
  Correlation with Human Judgments.\BBCQ\
\newblock In {\Bem Proceedings of the ACL Workshop on Intrinsic and Extrinsic
  Evaluation Measures for Machine Translation And/Or Summarization},
  \mbox{\BPGS\ 65--72}.

\bibitem[\protect\BCAY{Bickel, Haider, \BBA\ Scheffer}{Bickel
  et~al.}{2005}]{bickel2005}
Bickel, S., Haider, P., \BBA\ Scheffer, T. \BBOP 2005\BBCP.
\newblock \BBOQ Predicting Sentences using n-gram Language Models.\BBCQ\
\newblock In {\Bem Proceedings of the Conference on Human Language Technology
  and Empirical Methods in Natural Language Processing}, \mbox{\BPGS\
  193--200}.

\bibitem[\protect\BCAY{Bilmes \BBA\ Kirchhoff}{Bilmes \BBA\
  Kirchhoff}{2003}]{bilmes2003}
Bilmes, J.~A.\BBACOMMA\ \BBA\ Kirchhoff, K. \BBOP 2003\BBCP.
\newblock \BBOQ Factored Language Models and Generalized Parallel
  Backoff.\BBCQ\
\newblock In {\Bem Proceedings of the 2003 Conference of the North American
  Chapter of the Association for Computational Linguistics on Human Language
  Technology}, \lowercase{\BVOL}~2, \mbox{\BPGS\ 4--6}.

\bibitem[\protect\BCAY{Brown, Cocke, Pietra, Pietra, Jelinek, Lafferty, Mercer,
  \BBA\ Roossin}{Brown et~al.}{1990}]{brown1990}
Brown, P.~F., Cocke, J., Pietra, S.~A., Pietra, V.~J., Jelinek, F., Lafferty,
  J.~D., Mercer, R.~L., \BBA\ Roossin, P.~S. \BBOP 1990\BBCP.
\newblock \BBOQ A Statistical Approach to Machine Translation.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 16}  (2), \mbox{\BPGS\
  79--85}.

\bibitem[\protect\BCAY{Brown, Desouza, Mercer, Pietra, \BBA\ La}{Brown
  et~al.}{1992}]{brown1992}
Brown, P.~F., Desouza, P.~V., Mercer, R.~L., Pietra, V. J.~D., \BBA\ La, J.~C.
  \BBOP 1992\BBCP.
\newblock \BBOQ Class-based n-gram Models of Natural Language.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 18}  (4), \mbox{\BPGS\
  467--479}.

\bibitem[\protect\BCAY{Chelba}{Chelba}{1997}]{chelba1997}
Chelba, C. \BBOP 1997\BBCP.
\newblock \BBOQ A Structured Language Model.\BBCQ\
\newblock In {\Bem Proceedings of ACL-EACL}, \mbox{\BPGS\ 498--500}.

\bibitem[\protect\BCAY{Chen \BBA\ Goodman}{Chen \BBA\ Goodman}{1999}]{chen1999}
Chen, S.~F.\BBACOMMA\ \BBA\ Goodman, J. \BBOP 1999\BBCP.
\newblock \BBOQ An Empirical Study of Smoothing Techniques for Language
  Modeling.\BBCQ\
\newblock {\Bem Computer Speech and Language}, {\Bbf 13}  (4), \mbox{\BPGS\
  359--393}.

\bibitem[\protect\BCAY{Chen, Zhang, \BBA\ Li}{Chen et~al.}{2012}]{chen2012}
Chen, W., Zhang, M., \BBA\ Li, H. \BBOP 2012\BBCP.
\newblock \BBOQ Utilizing Dependency Language Models for Graph-based Dependency
  Parsing Models.\BBCQ\
\newblock In {\Bem Proceedings of the 50th Annual Meeting of the Association
  for Computational Linguistics}, \lowercase{\BVOL}~1, \mbox{\BPGS\ 213--222}.

\bibitem[\protect\BCAY{Dice}{Dice}{1945}]{dice1945}
Dice, L.~R. \BBOP 1945\BBCP.
\newblock \BBOQ Measures of the Amount of Ecologic Association Between
  Species.\BBCQ\
\newblock {\Bem Ecology}, {\Bbf 26}, \mbox{\BPGS\ 297--302}.

\bibitem[\protect\BCAY{Ding \BBA\ Yamamoto}{Ding \BBA\
  Yamamoto}{2013}]{ding2013}
Ding, C.\BBACOMMA\ \BBA\ Yamamoto, M. \BBOP 2013\BBCP.
\newblock \BBOQ An Unsupervised Parameter Estimation Algorithm for a Generative
  Dependency N-gram Language Model.\BBCQ\
\newblock In {\Bem IJCNLP}, \mbox{\BPGS\ 516--524}.

\bibitem[\protect\BCAY{Guthrie, Allison, Liu, \BBA\ Guthrie}{Guthrie
  et~al.}{2006}]{guthrie2006}
Guthrie, D., Allison, B., Liu, W., \BBA\ Guthrie, L. \BBOP 2006\BBCP.
\newblock \BBOQ A Closer Look at Skip-gram Modeling.\BBCQ\
\newblock In {\Bem Proceedings of the 5th International Conference on Language
  Resources and Evaluation}, \mbox{\BPGS\ 1--4}.

\bibitem[\protect\BCAY{Huang, Alleva, Hon, Hwang, \BBA\ Lee}{Huang
  et~al.}{1993}]{huang1993}
Huang, X., Alleva, F., Hon, H.~W., Hwang, M.~Y., \BBA\ Lee, K.~F. \BBOP
  1993\BBCP.
\newblock \BBOQ The SPHINX-II Speech Recognition System: An Overview.\BBCQ\
\newblock {\Bem Computer Speech and Language}, {\Bbf 7}  (2), \mbox{\BPGS\
  137--148}.

\bibitem[\protect\BCAY{Katz}{Katz}{1987}]{katz1987}
Katz, S. \BBOP 1987\BBCP.
\newblock \BBOQ Estimation of Probabilities from Sparse Data for the Language
  Model Component of a Speech Recognizer.\BBCQ\
\newblock {\Bem Acoustics, Speech and Signal Processing}, {\Bbf 35}  (3),
  \mbox{\BPGS\ 400--401}.

\bibitem[\protect\BCAY{Kneser \BBA\ Ney}{Kneser \BBA\ Ney}{1995}]{kneser1995}
Kneser, R.\BBACOMMA\ \BBA\ Ney, H. \BBOP 1995\BBCP.
\newblock \BBOQ Improved Backing-off for M-gram Language Modeling.\BBCQ\
\newblock {\Bem Acoustics, Speech, and Signal Processing}, {\Bbf 1},
  \mbox{\BPGS\ 181--184}.

\bibitem[\protect\BCAY{Langacker}{Langacker}{1986}]{langacker1986}
Langacker, R.~W. \BBOP 1986\BBCP.
\newblock \BBOQ An Introduction to Cognitive Grammar.\BBCQ\
\newblock {\Bem Cognitive Science}, {\Bbf 10}, \mbox{\BPGS\ 1--40}.

\bibitem[\protect\BCAY{Langacker}{Langacker}{1999}]{langacker1999}
Langacker, R.~W. \BBOP 1999\BBCP.
\newblock {\Bem Grammar and Conceptualization}.
\newblock Mouton de Gruyter, DE.

\bibitem[\protect\BCAY{Langacker}{Langacker}{2008}]{langacker2008}
Langacker, R.~W. \BBOP 2008\BBCP.
\newblock {\Bem Cognitive Grammar---A Basic Introduction}.
\newblock Oxford.

\bibitem[\protect\BCAY{Manning \BBA\ Sch{\"{u}}tze}{Manning \BBA\
  Sch{\"{u}}tze}{1999}]{manning1999}
Manning, C.~D.\BBACOMMA\ \BBA\ Sch{\"{u}}tze, H. \BBOP 1999\BBCP.
\newblock {\Bem Foundations of Statistical Natural Language Processing}.
\newblock MIT Press.

\bibitem[\protect\BCAY{Mays, Damerau, \BBA\ Mercer}{Mays
  et~al.}{1990}]{mays1991}
Mays, E., Damerau, F.~J., \BBA\ Mercer, R.~L. \BBOP 1990\BBCP.
\newblock \BBOQ Context based Spelling Correction.\BBCQ\
\newblock {\Bem Information Processing and Management}, {\Bbf 27}  (5),
  \mbox{\BPGS\ 517--522}.

\bibitem[\protect\BCAY{Papineni, Roukos, Ward, \BBA\ Zhu}{Papineni
  et~al.}{2002}]{papineni2002}
Papineni, K., Roukos, S., Ward, T., \BBA\ Zhu, W.~J. \BBOP 2002\BBCP.
\newblock \BBOQ BLEU: A Method for Automatic Evaluation of Machine
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 40th Annual Meeting on Association for
  Computational Linguistics}, \mbox{\BPGS\ 311--318}.

\bibitem[\protect\BCAY{Rabiner \BBA\ Juang}{Rabiner \BBA\
  Juang}{1993}]{rabiner1993}
Rabiner, L.\BBACOMMA\ \BBA\ Juang, B.~H. \BBOP 1993\BBCP.
\newblock {\Bem Fundamentals of Speech Recognition}.
\newblock Prentice Hall.

\bibitem[\protect\BCAY{Shannon}{Shannon}{1948}]{shannon1948}
Shannon, C.~E. \BBOP 1948\BBCP.
\newblock \BBOQ A Mathematical Theory of Communication.\BBCQ\
\newblock {\Bem The Bell System Technical Journal}, {\Bbf 27}, \mbox{\BPGS\
  379--423}.

\bibitem[\protect\BCAY{Shen, Xu, \BBA\ Weischedel}{Shen
  et~al.}{2008}]{shen2008}
Shen, L., Xu, J., \BBA\ Weischedel, R.~M. \BBOP 2008\BBCP.
\newblock \BBOQ A New String-to-Dependency Machine Translation Algorithm with a
  Target Dependency Language Model.\BBCQ\
\newblock In {\Bem ACL}, \mbox{\BPGS\ 577--585}.

\bibitem[\protect\BCAY{Snover, Dorr, Schwartz, Micciulla, \BBA\ Makhoul}{Snover
  et~al.}{2006}]{snover2006}
Snover, M., Dorr, B., Schwartz, R., Micciulla, L., \BBA\ Makhoul, J. \BBOP
  2006\BBCP.
\newblock \BBOQ A Study of Translation Edit Rate with Targeted Human
  Annotation.\BBCQ\
\newblock In {\Bem Proceedings of Association for Machine Translation in the
  Americas}, \mbox{\BPGS\ 223--231}.

\bibitem[\protect\BCAY{Wu \BBA\ Matsumoto}{Wu \BBA\ Matsumoto}{2014}]{wu2014}
Wu, X.\BBACOMMA\ \BBA\ Matsumoto, Y. \BBOP 2014\BBCP.
\newblock \BBOQ A Hierarchical Word Sequence Language Model.\BBCQ\
\newblock In {\Bem Proceedings of The 28th Pacific Asia Conference on Language,
  Information and Computation}, \mbox{\BPGS\ 489--494}.

\bibitem[\protect\BCAY{Wu \BBA\ Matsumoto}{Wu \BBA\ Matsumoto}{2015}]{wu2015a}
Wu, X.\BBACOMMA\ \BBA\ Matsumoto, Y. \BBOP 2015\BBCP.
\newblock \BBOQ An Improved Hierarchical Word Sequence Language Model Using
  Directional Information.\BBCQ\
\newblock In {\Bem Proceedings of The 29th Pacific Asia Conference on Language,
  Information and Computation}, \mbox{\BPGS\ 453--458}.

\bibitem[\protect\BCAY{Wu, Matsumoto, Duh, \BBA\ Shindo}{Wu
  et~al.}{2015}]{wu2015b}
Wu, X., Matsumoto, Y., Duh, K., \BBA\ Shindo, H. \BBOP 2015\BBCP.
\newblock \BBOQ An Improved Hierarchical Word Sequence Language Model Using
  Word Association.\BBCQ\
\newblock In {\Bem Proceedings of the 3rd International Conference on
  Statistical Language and Speech Processing}, \mbox{\BPGS\ 275--287}.

\end{thebibliography}


\appendix[Modified Kneser-Ney Smoothing]
\label{app:mkn}

The state-of-the-art method for smoothing is modified Kneser-Ney smoothing proposed in \cite{chen1999}. Based on normal Kneser-Ney smoothing, MKN uses different discount parameters for non-zero counts, whose calculation is shown as Equation (\ref{equation:mkn}).
\begin{equation}
\begin{split}
P_{MKN}(w_{i}|w_{i-n+1}^{i-1}) & = \frac{max\{C(w_{i-n+1}^{i}) - D(C(w_{i-n+1}^{i})), 0\}}{C(w_{i-n+1}^{i-1})} \\
 & \quad {} + \gamma_{high}(w_{i-n+1}^{i-1})\hat{P}_{MKN}(w_{i}|w_{i-n+2}^{i-1})
\label{equation:mkn}
\end{split}
\end{equation}

The discount value $D$ is a discount value calculate by Equation (\ref{equation:D}).\footnote{$n_{i}$ is the total number of n-grams which appear exactly i times in the training data.}
\begin{equation}
D(c) = 
\begin{cases}
0 & $if$\ c = 0\\
D_{1} = 1 - 2\frac{n_{1}}{n_{1}+n_{2}}\frac{n_{2}}{n_{1}} & $if$\ c = 1\\
D_{2} = 2 - 3\frac{n_{1}}{n_{1}+n_{2}}\frac{n_{3}}{n_{2}} & $if$\ c = 2\\
D_{3+} = 3 - 4\frac{n_{1}}{n_{1}+n_{2}}\frac{n_{4}}{n_{3}} & $if$\ c > 2
\end{cases}
\label{equation:D}
\end{equation}

And $\gamma_{high}(w_{i-n+1}^{i-1})$ is defined as Equation (\ref{equation:gamma_h}).\footnote{$N_{1}(w_{i-n+1}^{i-1}\bullet) = |\{w_{i} : C(w_{i-n+1}^{i}) = 1\}|$, and $N_{2}(w_{i-n+1}^{i-1}\bullet)$ $N_{3+}(w_{i-n+1}^{i-1}\bullet)$ are counted in a similar way.}
\begin{equation}
\label{equation:gamma_h}
\gamma_{high}(w_{i-n+1}^{i-1}) 
	= \frac{D_{1}N_{1}(w_{i-n+1}^{i-1}\bullet) + D_{2}N_{2}(w_{i-n+1}^{i-1}\bullet) + D_{3+}N_{3+}(w_{i-n+1}^{i-1}\bullet)}{C(w_{i-n+1}^{i-1})}
\end{equation}

The lower order models $\hat{P}_{MKN}(w_{i}|w_{i-n+1}^{i-1})$ are interpolated recursively as below.
\begin{equation}
\begin{split}
\hat{P}_{MKN}(w_{i}|w_{i-n+1}^{i-1}) 
 & = \frac{max\{N_{1+}(\bullet w_{i-n+1}^{i}) - D(C(w_{i-n+1}^{i})), 0\}}{N_{1+}(\bullet w_{i-n+1}^{i-1}\bullet)} \\
 & \quad {} + \gamma_{mid}(w_{i-n+1}^{i-1})\hat{P}_{MKN}(w_{i}|w_{i-n+2}^{i-1})
\label{equation:hatmkn}
\end{split}
\end{equation}

where $\gamma_{mid}(w_{i-n+1}^{i-1})$ is defined as Equation (\ref{equation:gamma_m}).
\begin{equation}
\label{equation:gamma_m}
\gamma_{mid}(w_{i-n+1}^{i-1}) 
 = \frac{D_{1}N_{1}(w_{i-n+1}^{i-1}\bullet) + D_{2}N_{2}(w_{i-n+1}^{i-1}\bullet) + D_{3+}N_{3+}(w_{i-n+1}^{i-1}\bullet)}{N_{1+}(\bullet w_{i-n+1}^{i-1}\bullet)}
\end{equation}


\clearpage
\begin{biography}

\bioauthor[:]{Xiaoyi Wu}{
received his B.S. degree from Liaoning University in 2003 and M.S. degree from Beijing Foreign Studies University in 2011. He is currently a doctoral student at NAIST. His research interests include linguistics and natural language processing.
}

\bioauthor[:]{Kevin Duh}{
received the B.S. degree from Rice University, Houston, TX, USA, in 2003, and Ph.D. from the University of Washington, Seattle, WA, USA, in 2009, both in electrical engineering. He was working as an Assistant Professor at the Nara Institute of Science and Technology (NAIST), Graduate School of Information Science, Ikoma, Japan. Before joining NAIST, from 2009 to 2012, he worked at the NTT Communication Science Laboratories. His research interests include intersection of natural language processing and machine learning, in particular, in areas relating to machine translation and deep learning.
}

\bioauthor[:]{Yuji Matsumoto}{
received his M.S. and Ph.D. degrees in information science from Kyoto University in 1979 and in 1989. He joined Machine Inference Section of Electrotechnical Laboratory in 1979. He has then experienced an academic visitor at Imperial College of Science and Technology, a deputy chief of First Laboratory at ICOT, and an associate professor at Kyoto University. He is currently a professor at the Graduate School of Information Science, Nara Institute of Science and Technology. His main research interests are natural language understanding and machine learning.
}

\end{biography}

\biodate




\end{document}
