    \documentclass[english]{jnlp_1.2.0}
\usepackage[dvips]{graphicx}


\Volume{14}
\Number{1}
\Month{Jan.}
\Year{2007}
\received{2006}{7}{1}
\revised{2006}{9}{1}
\accepted{2006}{10}{6}

\setcounter{page}{139}

\etitle{Text Generation for Intermediate Non-native Speakers \\of English}
\eauthor{Xinyu Deng\affiref{KyotoUniv} \and Jun-ichi Nakamura} 
\eabstract{
This paper describes the microplanner of the SILK system
which can generate texts appropriate for intermediate 
non-native users on discourse level. Four factors 
(i.e. nucleus position, between-text-span punctuation, 
embedded discourse markers and punctuation pattern) 
are regarded to affect the readability at discourse level. 
It is the preferences among these factors that decide the 
readability. Since the number of possible combinations of the
preferences is huge, we use Genetic Algorithm to solve such a problem. 
We adopt two methods to evaluate the system: one is evaluating 
the reliability of the SILK system by analysing how often 
it re-generates corpus texts, another is judging readability 
by human subjects. The evaluation results show that the
system is reliable and the generation results are appropriate 
for intermediate non-native speakers on discourse level.
}
\ekeywords{text generation, discourse level, Genetic Algorithm, 
	intermediate non-native speakers of English}

\headauthor{Deng and Nakamura}
\headtitle{Text generation for intermediate non-native speakers of English}

\affilabel{KyotoUniv}{}{Kyoto University, Graduate School of Informatics}


\begin{document}

\maketitle





\section{Background} 

At present, the population of non-native speakers is twice that 
of native speakers of English. In natural language generation (NLG), 
although some text generation systems \cite{McKeown85,Goldberg94,Bateman97} 
had been developed, their target users were native speakers. Since 
the population of non-native speakers is huge, text generation
for non-native speakers whose English level is lower is a promising 
application area. At present, we are developing a text generation
system which is called SILK (text generation System for Intermediate Level non-native
speaKers\footnote{Generally speaking, non-native speakers are divided into three levels: primary (middle school level), intermediate (high school level) and advanced (university level). The users of this study are assumed to be at intermediate level.}). This paper 
describes the microplanner of the SILK system. The domain of the
generated texts is \textit{natural and pure science}.


At the beginning of this study, we created two corpora. One corpus is 
SUB-BNC\footnote{SUB-BNC is a sub-corpus of British National Corpus. See http://www.natcorp.ox.ac.uk/}, which contains texts whose target audience was native speakers. 
Another is TANN, which contains texts whose target audience was 
intermediate non-native speakers\footnote{The texts within TANN were selected from the high school students' textbooks published in China and in Japan.}. The two corpora are comparable, 
because their size (200,000 words each), domain 
(\textit{natural and pure science}) and medium (book) are consistent with
each other. The results of corpus analysis show that the usage of some words is 
different between the two corpora. For example, within SUB-BNC, 48\% 
of subordinate clauses beginning with \textit{if} occur in the first span, 
while within TANN, about 80\% occur in the first span. Within SUB-BNC, 
20\% of subordinate clauses beginning with \textit{although} occur in 
the first span, while within TANN, 70\% occur in the first span. 
Moreover, for the subordinate clauses beginning with \textit{because}, within 
SUB-BNC, 8\% occur in the first span, while within TANN, 29\% 
occur in the first span. Therefore, we realized that although some 
text generation systems had been developed for native speakers, 
we ought to explore the generation strategies for non-native 
users independently without taking into account the case of native speakers.

In this study, four factors (i.e. nucleus position, 
between-text-span punctuation, embedded discourse markers 
and punctuation pattern) are regarded to affect the 
readability on discourse level. We claim that it is the preferences 
among these factors rather than the factors themselves that decide 
the readability. That is, capturing these preferences properly can 
generate a text which is appropriate for intermediate non-native 
speakers on discourse level. We use Genetic Algorithm\footnote{The framework of Simple Genetic Algorithm used in this study was obtained from \cite{Hirano03}.} to realize 
this consideration. The rest of the paper is arranged as follows. 
Section 2 describes the microplanner. Section 3 introduces the 
preferences among the four factors. Section 4 illustrates how to 
generate texts by Genetic Algorithm. Section 5 describes the 
evaluation methods. Section 6 introduces the related work. In 
Section 7, we draw a conclusion. 


\section{An introduction to the microplanner}

This study focuses on the microplanner of the SILK system. The 
task of the microplanner is to transform text representations from 
hierarchical tree structures into ordered individual sentences. 
In other words, the microplanner decides how the sentences from the 
tree will be ordered and punctuated, and selects one text appropriate 
for intermediate non-native users. 

The input of the microplanner is the text structure represented by 
Rhetorical Structure Theory (RST) \cite{Mann88}, 
for example, the RST-tree shown in Fig. 1. In an RST-tree, 
non-terminal nodes represent discourse relations, while 
terminal nodes represent sentences. In Fig. 1, Node 0 
represents ``elaboration'' relation, and Node 1 represents sentence 
``plant at the right time of year''. We have the following two reasons 
to use RST.

\begin{enumerate}
  \item RST is suitable to represent the discourse structure of any genre of texts.
Therefore, there is no problem to use RST to represent the structure of the text 
whose domain is \textit{natural and pure science}.
  \item In RST, the discourse relations initially defined is an open set.
That is, the researchers can add or modify relations according to their 
needs. In this study, we defined 12 discourse relations: background, condition, contrast, 
elaboration, evaluation, example, list, purpose, reason, restatement, summary, time.
\end{enumerate}

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.65]{fig-1.eps}
\caption{Input of the microplanner}
\vspace{20pt}
\includegraphics[scale=0.9]{fig-2.eps}
\end{center}
\caption{Output of the microplanner}
\end{figure}


The output of the microplanner is a coherent text that contains individual 
sentences which are ordered and punctuated, for example, the text shown 
in Fig. 2.


\section{Preferences among factors affecting the readability on discourse \\\hspace{18pt}level}

As mentioned in Section 1, we think that four factors affect the
readability on discourse level. In this section, we introduce the
preferences among these factors.

In an RST-tree, each non-terminal node is the root of a sub-tree. 
We assume that a candidate generation result of 
each sub-tree has two kinds of structures. One is called 
\textit{local structure}, in which the nucleus and the satellite 
are regarded as nodes. The \textit{local structure} can be 
represented as ``node + between-text-span punctuation + node''. 
Another is called \textit{linear structure}, which is linear 
ordered sentences. For example, in Fig. 1, the sub-tree 
whose root is Node 3 has two child nodes: Node 5 and Node 6. 
If the \textit{local structure} of a candidate generation result 
is ``Node 6 + comma + Node 5'', the \textit{linear structure} 
of this candidate generation result is ``If you do things at the
wrong time of year, the results will not be so good.''.


\subsection{Preferences for nucleus position in the \textit{local structure}}

In the field of NLG, the usage of discourse markers has been regarded as an 
important problem \cite{Elhadad90,Moser95,Eugenio97}. 
At present, the SILK system can generate six discourse relations, namely, 
``condition'' relation, ``contrast'' relation, ``example'' relation, 
``reason'' relation, ``elaboration'' relation and ``list'' relation. 
We use discourse markers \textit{if}, \textit{but}, \textit{for example} and
\textit{because} to signal the first four relations. No discourse marker is
used to signal the later two. Moreover, ``list'' relation only has
two child nodes. We explored the preferences for the nucleus position of each
relation by using machine learning program C4.5 (see Appendix) and analysing 
corpus TANN. We divided the nucleus position into the following three states. 

\begin{enumerate}
   \item Good position. It refers to the position which is the result
   of machine learning. For example, for ``condition'' relation signaled 
   by \textit{if}, the results of machine learning show that nuclei occur 
   in the second span, such as ``If you do not go to bed early, 
    \underline{you cannot have enough} \linebreak\underline{sleep}.''. 
   Therefore, the second span 
   is the ``good position''. 
   \item Normal position. It refers to a position which is not the result 
   of machine learning but that of corpus analysis. For example, 
   for ``condition'' relation signaled by \textit{if}, although machine 
   learning results show that the nuclei occur in the second span, 
   corpus analysis results show that about 20\% of nuclei occur in the first 
   span, such as ``\underline{In general, intelligence is not connected well with age},
   especially if a person is healthy and active.''.
   Therefore, the first span is a ``normal position''.
   \item Bad position. It refers to the position which is neither the
   result of machine learning nor that of corpus analysis. 
   For example, for ``elaboration'' relation, nuclei never occur in the 
   second span. Therefore, the second span is a ``bad position''.
\end{enumerate}

The three states of the nucleus position for six relations are shown in Table 1. 

\begin{table}[t]
\caption{Three states of nucleus position for six discourse relations}
\begin{center}
 \begin{tabular}{|c||c|c|c|}               \hline
                   & \multicolumn{3}{|c|}{Nucleus position} \\ \cline{2-4}                 
                   & Good & Normal & Bad   \\ \hline \hline
                   & second span      & first span           &   \\
                   & (if \textsf{R} is ``contrast'', & (if \textsf{R} is ``contrast'',  &        \\ 
Reason             & ``example'', or ``reason'') & ``example'' or ``reason'') & none \\ \cline{2-3}
(\textit{because}) & first span       & second span           &          \\
                   & (if \textsf{R} is not ``contrast'',  & (if \textsf{R} is not ``contrast'', &    \\
                   & ``example'' or ``reason'')  & ``example'', or ``reason'') & \\ \hline \hline
Contrast           & second span        & none       & first span   \\ 
(\textit{but})     & & &  \\ \hline \hline
Example            & first span         & none       & second span  \\
(\textit{for example}) &  &  &  \\ \hline \hline
Condition          & second span     & first span   & none  \\
(\textit{if})      &  &  &  \\ \hline \hline
Elaboration        & first span   & none  & second span        \\  
 (no cue)          &  &  &  \\ \hline \hline
List               & first span & none  & second span     \\ 
 (no cue)          &  &  &  \\ \hline 
\end{tabular}
\end{center}
\end{table}

\textsf{Heuristic 1}~~Preferences among states for nucleus position: good position $>$ normal position $>$ bad position


\subsection{Preferences for between-text-span punctuation in the \textit{local structure}}

We explore the preferences for between-text-span punctuation in
the \textit{local structure} by using C4.5 and analysing corpus TANN.
The method is same as that mentioned in Section 3.1. We divided the
between-text-span punctuation into the following three states.

\begin{table}[b]
\caption{Three states of between-text-span punctuation for six discourse relations}
\begin{center}
 \begin{tabular}{|c||c||c|c|c|}               \hline
         & Nucleus & \multicolumn{3}{|c|}{Between-text-span punctuation} \\ \cline{3-5}
         & position & Good         & Normal      & Bad  \\ \hline \hline
                   &                & space  & comma &  \\
  Reason           & first span     & (\textsf{Eg} $\leq$ 21) & (\textsf{Eg} $\leq$ 21) & full stop   \\ \cline{3-4}
 (\textit{because}) &                & comma             & space          &   \\              
                    &                & (\textsf{Eg} $>$ 21)   & (\textsf{Eg} $>$ 21)  &   \\ \cline{2-5}
                   & second span       & comma  & none               & space, full stop\\ \hline \hline
                   &    first span  & none              & none  & space, comma, full stop \\ \cline{2-5}
 Contrast          &                & comma             & space, full stop &   \\ 
(\textit{but})     &  second span   & (\textsf{Eg} $\leq$ 29)  & (\textsf{Eg} $\leq$ 29) & none \\ \cline{3-4} 
                   &                & full stop         & space, comma    & \\
                   &          & (\textsf{Eg} $>$ 29)  & (\textsf{Eg} $>$ 29) & \\ \hline \hline
 Example           & first span     & full stop         & none   & space, comma\\ \cline{2-5}
(\textit{for example}) & second span    & none              & none   & space, comma, full stop \\ \hline \hline
Condition          & second span    & comma             & none   & space, full stop    \\ \cline{2-5}
(\textit{if})      & first span     & space             & comma  & full stop \\ \hline \hline
 Elaboration       & first span     & full stop         & none & space, comma \\ \cline{2-5}
 (no cue)          & second span    & none              & none & space, comma, full stop \\ \hline \hline
 List              & first span     & full stop         & none & space, comma      \\ \cline{2-5}
 (no cue)          & second span    & none              & none & space, comma, full stop \\ \hline
\end{tabular}
\end{center}
\end{table}

\begin{enumerate}
   \item Good punctuation. It refers to the punctuation which is the 
   result of C4.5. For example, for ``condition'' relation 
   signaled by \textit{if}, when the nucleus occurs in the second span, 
   the between-text-span punctuation is a comma, such as ``If 
   you do not go to bed early\underline{, }you cannot have enough sleep.''.
   Therefore, comma is the ``good punctuation''. 
   \item Normal punctuation. It refers to a punctuation which is not the 
   result of machine learning but that of corpus analysis. 
   For example, for ``condition'' relation signaled by \textit{if}, 
   the machine learning results show that when the nucleus occurs in the 
   first span, the between-text-span punctuation is a space. 
   However, within TANN, the punctuation sometimes is a comma, 
   such as ``In general, intelligence is not connected well with 
   age\underline{, } especially if a person is healthy and active.''.
   Therefore, comma is a ``normal punctuation''.
   \item Bad punctuation. It refers to the punctuation which is neither
   the result of machine learning nor that of corpus analysis. For example, for
   ``condition'' relation signaled by \textit{if}, when the nucleus occurs
   in the second span, a full stop is never used as the between-text-span 
   punctuation, such as ``If you do not go to bed early\underline{. }
   You cannot have enough sleep.''. Therefore, full stop is a ``bad punctuation''.
\end{enumerate}

The three states of between-text-span punctuation for six relations 
are shown in Table 2. The results of machine learning and corpus analysis
show that between-text-span punctuation is determined by the nucleus position
(see the second column of Table 2).

\textsf{Heuristic 2}~~Preferences among states for between-text-span punctuation: good punctuation $>$ normal punctuation $>$ bad punctuation


\subsection{Preferences for embedded discourse markers in the \textit{linear structure}}

In an embedded structure, two discourse markers are sometimes used 
to signal two discourse relations. This kind of discourse markers 
are called \textit{embedded discourse markers} (EDMs). An embedded 
structure in which EDMs occur has two discourse markers 
and three propositions. We divided EDMs into two patterns. \textit{Pattern 1} 
represents the embedded structure in which the 
first discourse marker immediately precedes the second one and 
both discourse markers are attached to the second proposition, 
for example, Text (1). \textit{Pattern 2} represents the embedded 
structure in which discourse markers precede the second and the 
third proposition respectively, for example, Text (2). 
~\\
~~~~~1. You failed the exam. \textit{But if} you study hard, you can master English.\\
~~~~~2. You failed the exam. \textit{But} you can master English \textit{if} you study hard.
~\\  
The research of \cite{Power99} explored the problem of how to 
generate embedded discourse markers from rhetorical structure. 
However, it discussed the case of native speakers. 
In \cite{Biber99}, the authors point out 
that \textit{Pattern 1} is more difficult to understand,
because placing the subordinate clause in the initial position of the
embedded structure can create problems for processing. In \cite{Williams03},
the author also claims that it is better not use \textit{Pattern 1} while 
generating a text for native speakers. The results of corpus analysis 
proved their opinion, because within SUB-BNC, the frequency of 
\textit{Pattern 1} and \textit{Pattern 2} is 65 and 93. That is, 
\textit{Pattern 2} is more often used. On the contrary, we found 
that within TANN, the frequency of \textit{Pattern 1} and 
\textit{Pattern 2} is 119 and 87. That is, \textit{Pattern 1}
is more often used. So we can infer that compared 
with \textit{Pattern 2}, \textit{Pattern 1} is easier to read 
for intermediate non-native speakers. According to psycholinguistics, 
one possible explanation is that embedded structures are not easy 
to understand, so it is necessary to put two discourse markers 
together to attract the attention of intermediate non-native audiences. 
Based on the results of corpus analysis, we divided EDMs into the 
following three states:

\begin{enumerate}
   \item Good EDMs. They refer to \textit{Pattern 1} of EDMs, 
   such as ``\textit{but if}'' and ``\textit{for example, because}''.
   \item Normal EDMs. They refer to \textit{Pattern 2} of EDMs, 
   such as ``\textit{for example,}...\textit{if}''.
   \item Bad EDMs. They refer to the EDMs which could not be found within 
   TANN, such as ``\textit{for example, but}''. Actually, if such 
   EDMs were used, the cohesion, naturalness and logicality of the text 
   would be destroyed.
\end{enumerate}

Some examples of the three states of EDMs are shown in Table 3.

\begin{table}[t]
\caption{Examples of three states of EDMs}
\begin{center}
 \begin{tabular}{|l|l|l|}               \hline
 ~~~~~ Good EDMs &~~~~ Normal EDMs  &~~~~ Bad EDMs  \\ \hline \hline
  because if           & because...if            & because but    \\
  but because          & but...because           & because for example,   \\
  but if               & but...if                & but for example,   \\
  for example, because & but...for example,      & for example, but  \\
  for example, if      & for example,...because  & if because  \\ \hline
\end{tabular}
\end{center}
\end{table}

\textsf{Heuristic 3}~~Preferences among states for EDMs: good EDMs $>$ normal EDMs $>$ bad EDMs  


\subsection{Preferences for punctuation pattern in the \textit{linear structure}}

Punctuation is an indispensable component of written language. 
During the last decade, researches like \cite{Hovy91,Dale91,White95,Briscoe96,Jones96} 
mention the importance of punctuation and explore this problem 
from the viewpoint of NLP. 

At the beginning of this study, we did not realize that 
punctuation pattern affects readability. When we asked the intermediate non-native 
speakers to assess the generation result such as Text (3), almost 
all human subjects pointed out that they did not like the text
because it had too many commas. Some subjects suggested that 
if substituted a full stop for the comma at the 
end of the second clause, the generated text would be easy to read. 
At that time, we realized that not only the between-text-span 
punctuation in the \textit{local structure} but also the punctuations 
in the \textit{linear structure} affect the readability. 
~\\
~~~~~3. If a liquid metal is cooled quickly, the crystals in it have little time to grow, but if\\
~~~~~~~~it is cooled slowly, large crystals can grow.
~\\
Since comma and full stop are more often used than any other punctuation
marks, we analysed the first 900 sentences within TANN to find the punctuation
patterns of these sentences. Moreover, comma is used to delimit a sentence into more 
than one part, which may be words, phrases, or clauses. 
For example, in Text (4) and Text (5), comma delimits words and 
phrases. However, in Text (6), comma delimits clauses. In this study, 
we only consider the comma which is used to delimit clauses. 
~\\
~~~~~4. Bill can speak French, English, Spanish and German.\\
~~~~~5. Rebuilding that school, Mr. Brown predicted, will take another 2 years.\\
~~~~~6. Small winds can cause ripples, while strong winds create large hurricane waves. 
~\\
Table 4 shows the investigation results of punctuation patterns. 
It is obvious that Pattern 1, 2 and 3 often occur, while Pattern 4, 
5 and 6 seldom occur. So we can infer that Pattern 4, 5 and 6 can not 
improve the readability of texts.

\begin{table}[b]
\caption{Punctuation patterns within TANN}
\begin{center}
 \begin{tabular}{|c|l|c|}      \hline
    & \multicolumn{1}{c|}{Patterns}          & Frequency   \\ \hline \hline
 1  & $\langle$sentence$\rangle$.                         & 653         \\ 
 2  & $\langle$clause$\rangle$, $\langle$clause$\rangle$.               & 143         \\ 
 3  & $\langle$clause$\rangle$ $\langle$clause$\rangle$.                & 73          \\ 
 4  & $\langle$clause$\rangle$, $\langle$clause$\rangle$, $\langle$clause$\rangle$.   & 18          \\ 
 5  & $\langle$clause$\rangle$, $\langle$clause$\rangle$ $\langle$clause$\rangle$.    & 10          \\ 
 6  & $\langle$clause$\rangle$ $\langle$clause$\rangle$, $\langle$clause$\rangle$.    & 3           \\ \hline \hline 
  \multicolumn{2}{|c|}{Total}               & 900 \\   \hline 
\end{tabular}
\end{center}
\end{table}

We divided the punctuation pattern into three states: 

\begin{enumerate}
   \item Good pattern. It refers to a \textit{linear structure} which 
   contains Pattern 1, 2, or 3. For example, ``The coal burned 
   in power stations contains sulphur as an impurity. When the coal is 
   burnt, the sulphur is burnt too.''. Its punctuation pattern can be 
   represented as ``$\langle$sentence$\rangle$. $\langle$clause$\rangle$, $\langle$clause$\rangle$.''. That is, the text 
   contains Pattern 1 and 2. Therefore, this is the ``good pattern''. 
   \item Normal pattern. It refers to a \textit{linear structure} which contains
   Pattern 4, 5, or 6, besides (or without) Pattern 1, 2 or 3. For example,
   ``The shape of metals can be changed because the layers of atoms can
   slide past or over each other. When they do this, some bonds are
   broken, but an equal number are made.''. Its punctuation pattern
   can be represented as ``$\langle$clause$\rangle$$\langle$clause$\rangle$.$\langle$clause$\rangle$, $\langle$clause$\rangle$, $\langle$clause$\rangle$.''.
   That is, the text contains Pattern 3 and 4. Therefore, this is a 
   ``normal pattern''.
   \item Bad pattern. It refers to a \textit{linear structure} which
   contains none of the patterns shown in Table 4, for example, 
   the punctuation pattern of Text (3).
\end{enumerate}

\textsf{Heuristic 4}~~Preferences among states for punctuation pattern: good pattern $>$ normal pattern $>$ bad pattern 


\section{Text generation using a GA}

The task of microplanner is to decide how the sentences from 
the tree will be ordered and punctuated, and selects one text 
whose readability is appropriate for intermediate non-native 
users. For an RST-tree, such as the one shown in Fig. 1, 
the number of possible combinations of span order and between-text-span 
punctuation is very huge and the search space is not perfectly 
smooth. Therefore, the task of generation does not necessarily require a 
global optimum. A combination that could be understood by 
non-native users without difficulties would be enough. Based 
on this consideration, we think a Genetic Algorithm is suitable 
for solving such a problem. 

Fig. 3 illustrates the flow diagram of Simple Genetic Algorithm.
It shows that the GA analyses the input RST-tree and then
generates an optimized text. In this section, we focus on
introducing chromosome decoding (Section 4.1) and fitness evaluation 
(Section 4.2).

\begin{figure}[b]
\begin{center}
\includegraphics[scale=0.8]{fig-3.eps}
\end{center}
\caption{Flow diagram of Simple Genetic Algorithm applied to the microplanner}
\end{figure}


\subsection{Using 3 genes to represent the \textit{local structure} of 
a candidate generation result}

In a \textit{local structure}, the position of its child nodes
has two choices: ``nucleus -- satellite'' and 
``satellite -- nucleus''. The between-text-span 
punctuation has three choices: space (i.e. no punctuation), 
comma, and full stop. Therefore, the position of child nodes and
between-text-span punctuation have 6 combinations.

For each sub-tree, we use 3 genes to represent the \textit{local structure} 
of a candidate generation result (Fig. 4). Each gene has 
two scores: 0 and 1. The first gene represents the nucleus position: 
``0'' means the nucleus is placed in the first span, i.e. 
``nucleus -- satellite''; ``1'' means the nucleus is placed
in the second span, i.e. ``satellite -- nucleus''. The 
second and the third genes represent the 
between-text-span punctuation: ``00'' means space; ``01'' means comma; 
``10'' means full stop; ``11'' means beginning of the next paragraph. 
Since we do not consider the problem of generating a text with more 
than one paragraph, ``11'' is not desirable, so its score is negative 
in the experiments. Table 5 shows the eight combinations of the three 
genes and their representations. 

\begin{figure}[t]
\includegraphics[scale=0.8]{fig-4.eps}
\caption{Using 3 genes to represent the \textit{local structure} of a candidate generation result}
\end{figure}

\begin{table}[t]
\caption{Genes and their representations}
\begin{center}
 \begin{tabular}{|c|c|l|}      \hline
    & Genes   &~~~~~~~~~~~~~~~~~~~~~~~~Representations  \\ \hline \hline
 1  & 000    &     nucleus + space + satellite   \\ \hline        
 2  & 001    &     nucleus + comma + satellite \\ \hline
 3  & 010    &     nucleus + full stop + satellite \\ \hline
 4  & 011    &     nucleus + beginning of the next paragraph + satellite \\ \hline
 5  & 100    &     satellite + space + nucleus \\ \hline
 6  & 101    &     satellite + comma + nucleus \\ \hline
 7  & 110    &     satellite + full stop + nucleus \\ \hline
 8  & 111    &     satellite + beginning of the next paragraph + nucleus \\ \hline
\end{tabular}
\end{center}
\end{table}


\subsection{Evaluating a candidate generation result}

A key requirement of the GA approach is the ability to evaluate the
quality of a possible solution. We assign one candidate generation 
result of a sub-tree a score which is the sum of scores of the 
preferences for the four factors. For a whole RST-tree, the fitness 
of the candidate generation result is the sum of the scores of all 
sub-trees it has. We use the RST-tree shown in Fig. 1 to illustrate 
how the microplanner works. 

In order to justify our opinion that it is the preferences among 
the factors that determine the readability of the texts on discourse 
level, we fed the four heuristics mentioned in Section 3 into a 
constraint-based program. The program then randomly selects 
a number for each preference of the factors according to the 
heuristics. Table 6 shows a value generated from the program. 
The negative scores are given to unfavourable preferences and 
positive scores to favourable ones. Using this value, we ran 
the GA on the RST-tree shown in Fig. 1. 

\begin{table}[t]
\caption{A value used in the experiment}
\begin{center}
 \begin{tabular}{|c|l|c|}               \hline
  Factors  &~~~~~~Preferences  & Value    \\ \hline \hline
                       & good position      & 15 \\
Nucleus position       & normal position    & 1  \\
                       & bad position       & -3 \\ \hline
                       & good punctuation   & 6  \\
Between-text-span punctuation & normal punctuation & 2  \\
                       & bad punctuation    & -9 \\ \hline
                       & good EDMs          & 7  \\ 
EDMs                   & normal EDMs        & 5  \\
                       & bad EDMs           & -2 \\  \hline
                       & good pattern       & 14 \\ 
Punctuation pattern    & normal pattern     & 11 \\
                       & bad pattern        & -7 \\ \hline 
\end{tabular}
\end{center}
\end{table}

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.8]{fig-5.eps}
\end{center}
\caption{Scores of the best texts for 2000 iterations}
\end{figure}

Fig. 5 shows the scores of the best texts (2000 iterations). 
We can see that the scores keep on improving and gets stable 
at around 1600 iterations. At this moment, the best text 
(see Fig. 2) is scored at 164. The scoring is summarised 
in Table 7. In the first column, the root, gene representation and 
\textit{local structure} of each sub-tree are shown. In the third column, 
N, B, E, P represent the value of nucleus position, between-text-span punctuation, EDMs 
and punctuation pattern.


\begin{table}[t]
\caption{Summary of the scores of the best text}
\begin{center}
 \begin{tabular}{|l|l|c|}               \hline
~~~~~~~~~~~~~~~Sub-tree                       &~~~~~~~~~~~~~~~Linear structure & Scores \\ \hline \hline
\underline{Root:} Node 3                      & If you do things at the wrong time of &     40 \\ 
\underline{Genes:} 101                        & year, the results will not be so good. & (N: 15, B: 6  \\ 
\underline{Local structure:}                  &                                        & E: 5, P: 14) \\
satellite + comma + nucleus                   &                                        & \\ \hline
\underline{Root:} Node 4                      & If you grow seeds in the fields at the & 40 \\
\underline{Genes:} 101                        & correct time of year, the results will & (N: 15, B: 6\\ 
\underline{Local structure:}                  & be better.                             & E: 5, P: 14)\\
satellite + comma + nucleus                   &                                        & \\ \hline
\underline{Root:} Node 2                      & If you grow seeds in the fields at the & 42 \\  
\underline{Genes:} 110                        & correct time of year, the results will & (N: 15, B: 6 \\
\underline{Local structure:}                  & be better. But if you do things at the & E: 7, P: 14) \\
satellite + full stop + nucleus               & wrong time of year, the results will   & \\
                                              & not be so good. & \\ \hline
\underline{Root:} Node 0                      & Plant at the right time of year. If   & 42 \\ 
\underline{Genes:} 010                        & you grow seeds in the fields at the  & (N: 15, B: 6 \\
\underline{Local structure:}                  & correct time of year, the results will & E: 7, P: 14) \\
nucleus + full stop + satellite               & be better. But if you do things at the &  \\
                                              & wrong time of year, the results will & \\
                                              & not be so good. & \\ \hline \hline
\multicolumn{2}{|c|}{Fitness} & 164 \\ \hline
\end{tabular}
\end{center}
\end{table}


\section{Evaluation}

Since evaluation is an important issue in NLG, researchers have been 
trying to find valid and widely accepted methods. In
\cite{Coch96}, the author used a black-box methodology to assess three
techniques for producing multisentential texts. The research of \cite{Yeh97}
compared human-created results and computer-generated results.
Moreover, in \cite{Will03,Williams04}, the authors evaluated readability of the output
texts by measuring reading speed and reading errors. However, we do not think
this method is appropriate for our study, because many intermediate
(even advanced) non-native speakers do not know how to pronounce
English words. In China and Japan, the reality is many graduate school
students can not hold a conversation with a person in English even if they can write 
technical papers in English without difficulties. Therefore,
we adopt the following two evaluation methods: evaluating 
the reliability of the SILK system by analysing how often 
it re-generates corpus texts, and judging readability by human subjects.

\subsection{Evaluating the reliability of the SILK system}

In order to evaluate the reliability of the SILK system, 
we analyse how often it re-generates corpus texts.
Generally, the higher the frequency of re-generating corpus texts is,
the more reliable a text generation system is.

\begin{table}[b]
\caption{Frequency of re-generating corpus texts} 
\begin{center}
 \begin{tabular}{|c|c|c||c|c|c|}               \hline
      & Number of &           &      & Number of &           \\ 
 Text & discourse & Frequency & Text & discourse & Frequency \\  
      & relations &           &      & relations &           \\ \hline \hline
1        &    2      &    74     & 12   &  4        & 47        \\ \hline
2        &    2      &    86     & 13   &  4        & 42        \\ \hline
3        &    2      &    79     & 14   &  4        & 50        \\ \hline
4        &    2      &    83     & 15   &  5        & 40        \\ \hline 
5        &    2      &    81     & 16   &  5        & 33        \\ \hline
6        &    3      &    67     & 17   &  5        & 36        \\ \hline 
7        &    3      &    55     & 18   &  6        & 30        \\ \hline
8        &    3      &    58     & 19   &  6        & 25        \\ \hline
9        &    3      &    63     & 20   &  7        & 28        \\ \hline
10       &    3      &    60     & 21   &  7        & 22        \\ \hline
11       &    4      &    52     & 22   &  10       & 11        \\ \hline 
\end{tabular}
\end{center}
\end{table}

We selected 30 texts from corpus TANN, and asked two trained coders to
annotate the structure of these texts by RST. Then we compared the 
annotation results of the two coders. Of the 30 texts, the annotation
results of 22 texts were consistent with each other. Therefore, 
we used the 22 texts in the experiments. 

Using the value shown in Table 6, we ran the GA for 5000 
iterations on the RST-tree of each text for 100 times. 
For each tree structure, we counted how often the system re-generates 
TANN text (i.e. how often the output text is same as the 
original TANN text). The experimental results are shown in Table 8. 
In the table, the second column and the fifth column represent the number 
of discourse relations the texts contain. The third column and the 
sixth column represent the frequency of re-generating corpus texts. 

We can see that the frequency of re-generating corpus texts 
is dependent on the number of discourse relations the texts contain,
i.e. the more relations a text contains, the lower the 
frequency of re-generating corpus text is. In Table 8, for the
texts containing 2 relations, the frequency ranges from 74 to 86, 
but for the text containing 10 relations, the frequency is 11. 

We take Text 11 as an example to illustrate the experiment results. 
Fig. 1 shows the RST-tree of Text 11, and the text shown in 
Fig. 2 is same as its original TANN text. We found that the 
frequency of re-generating corpus texts is 52 after we ran the GA for
100 times. There are another 41 output texts can be understood,
though they are not consistent with 
the original TANN text. For example, ``Plant at the right time of year. 
The results will be better if you grow seeds in the fields 
at the correct time of year. But if you do things at the wrong 
time of year, the results will not be so good.'' and ``Plant at the right 
time of year. If you grow seeds in the fields at the
correct time of year, the results will be better. But 
the results will not be so good if you do things at the wrong 
time of year.'' Moreover, there are only 7 output texts 
that can not be completely understood. For example, 
``Plant at the right time of year if you grow seeds 
in the fields at the correct time of year, the results will be better. But if 
you do things at the wrong time of year. The results will not 
be so good.'' and ``The results will be better. If you grow 
seeds in the fields at the correct time of year, but 
the results will not be so good if you do things at the wrong 
time of year. Plant at the right time of year.''.

Actually, within TANN, the average sentences that per paragraph 
contains is 3.1, which means that intermediate non-native audience
prefers shorter texts. Therefore, we can say that so long as a text 
does not contain too many discourse relations (e.g. less than 5 relations), 
most of the generated texts can be understood. The experiment results
show that the SILK is a high-reliability text generation system. 

\subsection{Judging readability by human subjects}

To prove the GA method could simplify the English
text on discourse level, we designed a questionnaire
and asked human subjects to compare the RST-DTC\footnote{RST-DTC is the largest publicly available discourse-annotated corpus using the framework of RST. It can be obtained from the Linguistic Data Consortium (USA). The corpus contains articles of the Wall Street Journal.} texts to the output texts produced by SILK using the tree structures of 
the RST-DTC texts. 

We selected 20 texts from RST-DTC. Using the value shown in Table 6, 
we ran the GA for 5000 iterations on the tree structure of each RST-DTC 
text for five times, and chose the best result 
(i.e. the one with the highest score). In the questionnaire, we place 
the best text (i.e. SILK text) and its original RST-DTC text on 
the same page so that the subjects can compare them easily. 
And then we asked the subjects to choose a text they prefer. 

52 intermediate non-native subjects took part in the experiment. 
In this study, a person whose school background is lower than university
is regarded to be an intermediate non-native speaker. Of the subjects,
27 are high school students, 9 are junior college students, 16 
graduated from junior college. Moreover, 23 are male, 29 are female.
The age of the subjects ranges from 17 to 62; the mean is 31. 
We contacted with the human subjects by Internet and asked them 
to finish the questionnaire in their spare time.

\begin{table}[b]
\caption{The questionnaire results} 
\begin{center}
 \begin{tabular}{|c|c|c||c|c|c|}               \hline
 Question   & \multicolumn{2}{|c|}{Percentage} & Question & \multicolumn{2}{|c|}{Percentage} \\ \cline{2-3} \cline{5-6} 
           & SILK text & RST-DTC text         & & SILK text & RST-DTC text \\ \hline \hline
1         &   88     &  12       & 11   &  83    &  17   \\ \hline 
2         &   81     &  19       & 12   &  94    &   6   \\ \hline 
3         &   96     &   4       & 13   &  81    &  19   \\ \hline 
4         &   90     &  10       & 14   &  92    &   8   \\ \hline 
5         &   83     &  17       & 15   &  94    &   6   \\ \hline 
6         &   90     &  10       & 16   &   6    &  94   \\ \hline 
7         &   88     &  12       & 17   &  96    &   4   \\ \hline 
8         &   92     &   8       & 18   &  88    &  12   \\ \hline 
9         &   85     &  15       & 19   &  81    &  19   \\ \hline 
10        &   94     &   6       & 20   &  88    &  12   \\ \hline 
\end{tabular}
\end{center}
\end{table}

Table 9 shows the results of the questionnaire. The second column 
and the fifth column represent the percentage of the subjects who 
prefer the SILK texts. The third column and the sixth column represent the 
percentage of the subjects who prefer the RST-DTC texts. We can 
see that most of the subjects prefer SILK texts (except the one 
in Question 16). This shows that the GA method can simplify English 
texts on discourse level and the generated texts are easy to read 
for intermediate non-native speakers. 

Further analysis shows that the RST-tree used in Question 16 is a 
complicated one, which contains 11 discourse relations. The
SILK text in Question 16 begins with ``For example, but its greatest drawback 
may be its 3-inch thickness, big enough for one consultant to describe 
it as ``clunky.''''. It is obvious that ``For example, but'' are bad EDMs, 
which are unfavourable preference. It is the beginning 
of the text that makes the human subjects confused. Moreover,
in the experiment, we only ran the GA on the RST-tree
of each text for five times. For a text containing 11 relations, 
since the number of possible combinations is huge (i.e. $2^3$$^3$), 
we can not guarantee the best one of the five generation results is appropriate
for intermediate non-native audience. Actually, we will not 
generate longer texts for intermediate non-native users, so 
the generation result such as the SILK text in Question 16 can be avoided. 


\section{Related work}

The aim of this study is to simplify English text for intermediate
non-native speakers. In NLG, simplification of 
English document is a relatively new research field. The first 
study for ease of comprehension in NLG output was \cite{Scott90}. 
The authors point out that generating discourse markers whenever 
possible could make a text easier to comprehend. Moreover, several 
other methods were used to simplify texts. The study of \cite{Devlin98} 
substituted common words for uncommon words. In \cite{Chandrasekar97},
the authors reduced multiple-clause sentences to single-clause 
sentences. In \cite{Devlin00}, the authors simplified newspaper articles for 
aphasic readers. Their research focused on the simplification of
syntactic structures and lexical simplification. 

Until now, there exists a research focusing on simplification
of English texts on discourse level. The GIRL system \cite{Will04}
can generate texts for native speakers who have poor reading skills
due to a number of reasons, such as missed school, poor eyesight,
short-term memory, etc. Williams (2004) claims that length and 
ordering of the text spans, position of discourse marker, 
between-text-span punctuation and selection of discourse 
marker affect the readability on discourse level. In GIRL, 
the inputs to the microplanner are a model of a user's reading 
ability and a discourse plan containing the discourse relation
tree. The user model is built from user's answers to up to 
ninety questions from a literacy test. Based on the user models,
GIRL can adapt the generated texts to the reading level of individual 
users.


\section{Conclusion}

In this study, we applied GA to develop the microplanner of the 
SILK system which can generate texts appropriate for intermediate 
non-native speakers on discourse level. We think that four
factors affect the readability, i.e. nucleus position, between-text-span 
punctuation, embedded discourse markers and punctuation pattern. 
We claim that it is the preferences among these factors that 
determine the readability. We adopt two methods to evaluate the
system: one is evaluating the reliability of the SILK system by
analysing how often it re-generates corpus texts, another is
judging readability by human subjects. The evaluation results
show that the system is reliable and the generated texts are
appropriate for intermediate non-native users.  

The GA method introduced in this paper could be extended in generating
other types of texts, for example, world affairs, arts, etc. Moreover, 
the architecture based on the Genetic Algorithm can also be applied to
text generation for users with different levels, such as children and
middle school students. To realize these aims, it is necessary to do
more research to explore the influence of the factors mentioned above 
on the reading ability of the users. 

This study is the first stage of developing the SILK system. Future work 
will focus on simplification of syntactic structures and lexical 
simplification. Our aim is to make the SILK system generate texts 
appropriate for intermediate non-native speakers not only on discourse
level but also on sentence level.

\acknowledgment

I would like to thank Ehud Reiter, Sandra Williams and an anonymous
JNLP reviewer for their helpful comments on this paper.

\appendix

    \section*{Appendix}
    \subsection*{The nucleus position}

We used machine learning program C4.5 \cite{Eugenio97}
to induce the classification model of the nucleus position for each relation 
used in this study. The examples of each relation were obtained from corpus 
TANN. Here, we use ``reason'' relation signaled by \textit{because} to 
illustrate the method of investigating the nucleus position.

\begin{figure}[b]
\begin{center}
    \includegraphics[width=\textwidth]{fig-6.eps}
\end{center}
\caption{An annotation result}
\end{figure}

We selected the first 120 examples of ``reason'' relation signaled by
\textit{because}. Before the experiments, two trained coders took
part in annotating the examples. An annotation result is shown in 
Fig. 6, in which the portion annotated in round brackets is 
called \textit{embedded structure} and the one annotated in angle 
brackets is called \textit{whole structure}. We can see that the 
\textit{embedded structure} is contained in the nucleus of ``condition'' 
relation signaled by \textit{when}, i.e. the \textit{whole structure} 
includes the \textit{embedded structure}. Moreover, the 
\textit{embedded structure} contains the ``reason'' relation
signaled by \textit{because}.

In the experiments, each data point in our dataset is characterized 
by 18 features. These features are divided into the following two groups.
~\\
1. Embedded structure features
   \begin{enumerate}
    \item Mt. Tense of the main clause: past, present, future.  
    \item Mv. Voice of the main clause: active, passive.
    \item Mg. Length of the main clause (in words): integer.
    \item Ms. Structure of the main clause: simple, other.  
    \item Mi. Information contained in the main clause: new, old.
    \item St. Tense of the subordinate clause: past, present, future.
    \item Sv. Voice of the subordinate clause: active, passive.
    \item Sg. Length of the subordinate clause (in words): integer.
    \item Ss. Structure of the subordinate clause: simple, other.
    \item Si. Information contained in the subordinate clause: new, old.
  \end{enumerate}
~\\
2. Whole structure features
   \begin{enumerate}
   \item R. Discourse relation: background, condition, contrast, elaboration, evaluation, example, list, purpose, reason, restatement, summary, time.
   \item X. Whether the discourse relation is signaled by discourse marker: yes, no.
   \item E. Role of the \textit{embedded structure}: nucleus, satellite.
   \item P. Position of the \textit{embedded structure}: first span, second span.
   \item Eg. Length of the span containing the \textit{embedded structure}: integer.
   \item Es. Structure of the span containing the \textit{embedded structure}: complex sentence, other. 
   \item Og. Length of the span not containing the \textit{embedded structure}: integer.
   \item Os. Structure of the span not containing the \textit{embedded structure}: simple sentence, other.
  \end{enumerate}

We used the 120 annotated examples to induce the classification models 
of the nucleus position of ``reason'' relation. Within the 120
examples, 70.8\% (85/120) of nuclei occur in the first span. Therefore, 
the error rate of the baseline model is 29.2\%. We did 38 experiments 
using different models represented by subsets of the 18 features. 
The first 18 experiments used the models represented 
by individual features, corresponding to each feature mentioned above. 
Another 20 experiments used the models represented by the combinations 
of these features. We identify the best learned model(s) by comparing 
it (their) error rate(s) with the error rates of the other learned 
models and with the error rate of the baseline model. That is, if 
the upper bound of the 95\% confidence interval for error 
rate $\varepsilon$1 is lower than the lower bound of the 95\% 
confidence interval for error rate $\varepsilon$2, then the 
difference between $\varepsilon$1 and $\varepsilon$2 is considered 
to be significant. 

\begin{table}[b]
\caption{\setlength{\leftskip}{40pt}\setlength{\rightskip}{40pt}
95\%-confidence intervals for the error rates for four classification models \hbox to48pt{}of ``reason'' relation signaled by \textit{because}}
\begin{center}
 \begin{tabular}{|c|c|c|c|c|} \hline
    & \multicolumn{4}{|c|}{Models} \\ \hline \hline
Mt  &   &   & x & x   \\ 
Mv  &   &   & x & x   \\   
Mg  &   &   & x & x   \\   
Ms  &   &   & x & x   \\ 
Mi  &   &   & x &     \\
St  &   &   & x & x   \\
Sv  &   &   & x & x   \\
Sg  &   &   & x & x   \\
Ss  &   &   & x & x   \\
Si  &   &   & x &     \\
R   & x & x & x & x   \\
X   &   & x & x & x   \\
E   &   & x & x & x   \\
P   &   & x & x & x   \\
Eg  &   & x & x & x   \\
Es  &   & x & x & x   \\
Og  &   & x & x & x   \\
Os  &   & x & x & x   \\ \hline \hline
Results & 15.8 $\pm$ 2.66 & 24.2 $\pm$ 2.62 & 23.3 $\pm$ 3.80 & 22.5 $\pm$ 4.01  \\ \hline
\end{tabular}
\end{center}
\end{table}

Table 10 shows the error rates of four classification models which
perform better than the baseline model. Of these models, the one 
learned from feature R is the best model because it performs better 
than the three others. The model says that if the discourse relation 
of the \textit{whole structure} is ``contrast'', ``example'' or 
``reason'', then in the \textit{embedded structure}, the nucleus 
of ``reason'' relation signaled by \textit{because} occurs in the 
second span; otherwise occurs in the first span. 

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

\bibitem[\protect\BCAY{Bateman}{Bateman}{1997}]{Bateman97}
Bateman, J. \BBOP 1997\BBCP.
\newblock \BBOQ Enabling technology for multilingual natural language
  generation: The KPML development environment\BBCQ\
\newblock {\Bem Natural Language Engineering}, {\Bbf 3}  (1), \mbox{\BPGS\
  15--55}.

\bibitem[\protect\BCAY{Biber, Johansson, Leech, Conrad, \BBA\ Finegan}{Biber
  et~al.}{1999}]{Biber99}
Biber, D., Johansson, S., Leech, G., Conrad, S., \BBA\ Finegan, E. \BBOP
  1999\BBCP.
\newblock {\Bem Longman grammar of spoken and written English}.
\newblock Pearson Education Limited, England.

\bibitem[\protect\BCAY{Briscoe}{Briscoe}{1996}]{Briscoe96}
Briscoe, T. \BBOP 1996\BBCP.
\newblock \BBOQ The Syntax and Semantics of Punctuation and its Use in
  Interpretation\BBCQ\
\newblock In {\Bem Proc. of the Association for Computational Linguistics
  Workshop on Punctuation}, \mbox{\BPGS\ 1--7}.

\bibitem[\protect\BCAY{Chandrasekar \BBA\ Srinivas}{Chandrasekar \BBA\
  Srinivas}{1997}]{Chandrasekar97}
Chandrasekar, R.\BBACOMMA\ \BBA\ Srinivas, B. \BBOP 1997\BBCP.
\newblock \BBOQ Automatic induction of rules for text simplification\BBCQ\
\newblock {\Bem Knowledge-Based System}, {\Bbf 10}  (3), \mbox{\BPGS\
  183--190}.

\bibitem[\protect\BCAY{Coch}{Coch}{1996}]{Coch96}
Coch, H. \BBOP 1996\BBCP.
\newblock \BBOQ Evaluating and Comparing Three Text-production Techniques\BBCQ\
\newblock In {\Bem Proc. of the 16th International Conference on Computational
  Linguistics}, \mbox{\BPGS\ 249--254}.

\bibitem[\protect\BCAY{Dale}{Dale}{1991}]{Dale91}
Dale, R. \BBOP 1991\BBCP.
\newblock \BBOQ Exploring the Role of Punctuation in the Signaling of Discourse
  Structure\BBCQ\
\newblock In {\Bem Proc. of Workshop on Text Representation and Domain
  Modeling: Ideas from Linguistics and AI}, \mbox{\BPGS\ 110--120}.

\bibitem[\protect\BCAY{Devlin, Canning, Tait, Carrol, Minnen, \BBA\
  Pearce}{Devlin et~al.}{2000}]{Devlin00}
Devlin, S., Canning, Y., Tait, J., Carrol, J., Minnen, G., \BBA\ Pearce, D.
  \BBOP 2000\BBCP.
\newblock \BBOQ Making accessible international communication for people with
  language comprehension difficulties\BBCQ\
\newblock In {\Bem Proc. of The 7th International Conference on Computers
  Helping People with Special Needs}, \mbox{\BPGS\ 135--142}.

\bibitem[\protect\BCAY{Devlin \BBA\ Tait}{Devlin \BBA\ Tait}{1998}]{Devlin98}
Devlin, S.\BBACOMMA\ \BBA\ Tait, J. \BBOP 1998\BBCP.
\newblock \BBOQ The use of a psycholinguistic database in the simplification of
  text for aphasic readers\BBCQ\
\newblock In Nerbonne, J.\BED, {\Bem Linguistic Databases}, \mbox{\BPGS\
  161--173}. CSLI, New York.

\bibitem[\protect\BCAY{Elhadad \BBA\ McKeown}{Elhadad \BBA\
  McKeown}{1990}]{Elhadad90}
Elhadad, M.\BBACOMMA\ \BBA\ McKeown, K. \BBOP 1990\BBCP.
\newblock \BBOQ Generating connectives\BBCQ\
\newblock In {\Bem Proc. of the Thirteenth International Conference on
  Computational Linguistics}, \mbox{\BPGS\ 97--101}.

\bibitem[\protect\BCAY{Eugenio, Moore, \BBA\ Paolucci}{Eugenio
  et~al.}{1997}]{Eugenio97}
Eugenio, B., Moore, J., \BBA\ Paolucci, M. \BBOP 1997\BBCP.
\newblock \BBOQ Learning Features that Predict Cue Usage\BBCQ\
\newblock In {\Bem Proc. of the 35th Annual Meeting of the Association for
  Computational Linguistics}, \mbox{\BPGS\ 80--87}.

\bibitem[\protect\BCAY{Goldberg, Driedger, \BBA\ Kittredge}{Goldberg
  et~al.}{1994}]{Goldberg94}
Goldberg, E., Driedger, N., \BBA\ Kittredge, R. \BBOP 1994\BBCP.
\newblock \BBOQ Using natural language processing to produce weather
  forecasts\BBCQ\
\newblock {\Bem IEEE Expert}, {\Bbf 9}  (2), \mbox{\BPGS\ 45--53}.

\bibitem[\protect\BCAY{Hirano}{Hirano}{2003}]{Hirano03}
Hirano, H. \BBOP 2003\BBCP.
\newblock {\Bem Genetic Algorithms and Genetic Programming}.
\newblock Personal Media, Tokyo.

\bibitem[\protect\BCAY{Hovy \BBA\ Arens}{Hovy \BBA\ Arens}{1991}]{Hovy91}
Hovy, E.\BBACOMMA\ \BBA\ Arens, Y. \BBOP 1991\BBCP.
\newblock \BBOQ Automatic Generation of Formatted Text\BBCQ\
\newblock In {\Bem Proc. of AAAI-91}, \mbox{\BPGS\ 92--97}.

\bibitem[\protect\BCAY{Jones}{Jones}{1996}]{Jones96}
Jones, B. \BBOP 1996\BBCP.
\newblock \BBOQ Towards a Syntactic Account of Punctuation\BBCQ\
\newblock In {\Bem Proc. of the 16th International Conference on Computational
  Linguistics}, \mbox{\BPGS\ 604--609}.

\bibitem[\protect\BCAY{Mann \BBA\ Thompson}{Mann \BBA\ Thompson}{1988}]{Mann88}
Mann, W.\BBACOMMA\ \BBA\ Thompson, S. \BBOP 1988\BBCP.
\newblock \BBOQ Rhetorical structure theory: Toward a functional theory of text
  organization\BBCQ\
\newblock {\Bem Text}, {\Bbf 8}  (3), \mbox{\BPGS\ 243--281}.

\bibitem[\protect\BCAY{McKeown}{McKeown}{1985}]{McKeown85}
McKeown, K. \BBOP 1985\BBCP.
\newblock {\Bem Text Generation}.
\newblock Cambridge University Press.

\bibitem[\protect\BCAY{Moser \BBA\ Moore}{Moser \BBA\ Moore}{1995}]{Moser95}
Moser, M.\BBACOMMA\ \BBA\ Moore, J. \BBOP 1995\BBCP.
\newblock \BBOQ Investigating cue selection and placement in tutorial
  discourse\BBCQ\
\newblock In {\Bem Proc. of the 33rd Annual Meeting of the Association for
  Computational Linguistics}, \mbox{\BPGS\ 130--135}.

\bibitem[\protect\BCAY{Power, Doran, \BBA\ Scott}{Power et~al.}{1999}]{Power99}
Power, R., Doran, C., \BBA\ Scott, D. \BBOP 1999\BBCP.
\newblock \BBOQ Generating embedded discourse markers from rhetorical
  structure\BBCQ\
\newblock In {\Bem Proc. of the 7th European Workshop for Natural Language
  Generation}, \mbox{\BPGS\ 33--38}.

\bibitem[\protect\BCAY{Scott \BBA\ Souza}{Scott \BBA\ Souza}{1990}]{Scott90}
Scott, D.\BBACOMMA\ \BBA\ Souza, C. \BBOP 1990\BBCP.
\newblock \BBOQ Getting the Message Across in RST-based Text Generation\BBCQ\
\newblock In Dale, R., Mellish, C., \BBA\ M., Z.\BEDS, {\Bem Current Research
  in Natural Language Generation}, \mbox{\BPGS\ 47--73}. Academic Press.

\bibitem[\protect\BCAY{White}{White}{1995}]{White95}
White, M. \BBOP 1995\BBCP.
\newblock \BBOQ Presenting Punctuation\BBCQ\
\newblock In {\Bem Proc. of the Fifth European Workshop on Natural Language
  Generation}, \mbox{\BPGS\ 107--125}.

\bibitem[\protect\BCAY{Williams}{Williams}{2003}]{Williams03}
Williams, S. \BBOP 2003\BBCP.
\newblock \BBOQ Language choice models for microplanning and readability\BBCQ\
\newblock In {\Bem Proc. of the Student Workshop of the Human Language
  Technology and North American Chapter of the Association for Computational
  Linguistics Conference}, \mbox{\BPGS\ 13--18}.

\bibitem[\protect\BCAY{Williams}{Williams}{2004}]{Will04}
Williams, S. \BBOP 2004\BBCP.
\newblock {\Bem Natural language generation (NLG) of discourse relations for
  different reading levels}.
\newblock Ph.D.\ thesis, University of Aberdeen.

\bibitem[\protect\BCAY{Williams \BBA\ Reiter}{Williams \BBA\
  Reiter}{2004}]{Williams04}
Williams, S.\BBACOMMA\ \BBA\ Reiter, E. \BBOP 2004\BBCP.
\newblock \BBOQ Reading errors made skilled and unskilled readers: evaluating a
  system that generates reports for people with poor literacy\BBCQ\
\newblock \BTR, University of Aberdeen Department of Computer Science Technical
  Report AUCS/TR0407.

\bibitem[\protect\BCAY{Williams, Reiter, \BBA\ Osman}{Williams
  et~al.}{2003}]{Will03}
Williams, S., Reiter, E., \BBA\ Osman, L. \BBOP 2003\BBCP.
\newblock \BBOQ Experiments with discourse-level choices and readability\BBCQ\
\newblock In {\Bem Proc. of the 9th European Workshop on Natural Language
  Generation}, \mbox{\BPGS\ 127--134}.

\bibitem[\protect\BCAY{Yeh \BBA\ Mellish}{Yeh \BBA\ Mellish}{1997}]{Yeh97}
Yeh, C.\BBACOMMA\ \BBA\ Mellish, C. \BBOP 1997\BBCP.
\newblock \BBOQ An Empirical Study on the Generation of Anaphora in
  Chinese\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 23}  (1), \mbox{\BPGS\
  171--190}.

\end{thebibliography}

\begin{biography}

\bioauthor{Xinyu Deng}
{Xinyu Deng received her B.E. and M.A. from Harbin Institute of Technology, 
China. From 2001 to 2003 she worked for R\&D center of Toshiba, Tokyo, Japan. 
She completed her Ph.D. course of Kyoto University in 2006. She is currently 
doing research at Kyoto University. Her research interests include natural 
language processing, machine translation and corpus linguistics. 
}

\bioauthor{Jun-ichi Nakamura}
{(1956 -- 2001) Jun-ichi Nakamura received his BSc, MSc and DSc in electrical engineering from Kyoto University in 1979, 1981, and 1989. From 1997 to 2001 he was a professor in Kyoto University.
}

\end{biography}




\biodate

\end{document}
