    \documentclass[english]{jnlp_1.4}

\usepackage{jnlpbbl_1.1}
\usepackage[dvips]{graphicx}
\usepackage{multirow}
\usepackage{hangcaption_jnlp}
\setlength{\captionwidth}{\textwidth}

\Volume{15}
\Number{1}
\Month{Jan.}
\Year{2008}
\received{2006}{10}{20}
\revised{2007}{4}{3}
\rerevised{2007}{6}{18}
\accepted{2007}{8}{1}

\setcounter{page}{3}

\etitle{Using Semi-supervised Learning for Question Classification}
\eauthor{Tri Thanh Nguyen\affiref{Isjaist} \and Le Minh Nguyen\affiref{Isjaist} 
	\and Akira Shimazu\affiref{Isjaist}} 
\eabstract{
Question classification, an important phase in question
answering systems, is the task of identifying the type of a given
question among a set of predefined types. This study uses
unlabeled questions in combination with labeled questions for
semi-supervised learning, to improve the precision of question
classification task. For semi-supervised algorithm, we selected
Tri-training because it is a simple but efficient co-training
style algorithm. However, Tri-training is not well suitable for
question data, so we give two proposals to modify Tri-training, to
make it more suitable. In order to enable its three classifiers to
have different initial hypotheses, Tri-training bootstrap-samples
the originally labeled set to get different sets for training the
three classifiers. The precisions of three classifiers are
decreased because of the bootstrap-sampling. With the purpose to
avoid this drawback by allowing each classifier to be initially
trained on the originally labeled set while still ensuring the
diversity of three classifiers, our first proposal is to use
multiple algorithms for classifiers in Tri-training; the second
proposal is to use multiple algorithms for classifiers in
combination with multiple views, and our experiments show
promising results.}
\ekeywords{Computational Linguistics, Question classification, Semi-supervised learning, Tri-training algorithm}

\headauthor{Nguyen et al.}
\headtitle{Using Semi-supervised Learning for Question Classification}

\affilabel{Isjaist}{}{
	School of Information Science, Japan Advanced Institute of Science and Technology
	
}


\begin{document}

\maketitle



\section{Introduction}

Question classification is the task of identifying the type of a given question among a predefined set of question types. The type of a question can be used as a clue to narrow down the search space to extract the answer, and used for query generation in a question-answering (QA) system \cite{Li02}. Therefore, it has a significant impact on the overall performance of QA systems.

There have been several studies to solve this problem focusing on
supervised learning~\cite{Dell03,Hacioglu03,Li02}. However, the
cost of making labeled (training) data is high, and a large
training data set is needed to make significant impact on the
performance. Also the above methods do not use unlabeled
questions, which are readily available to improve the performance
of classification. In order to utilize both labeled and unlabeled
data, we propose to use semi-supervised learning. For the
semi-supervised learning algorithm, we adopted the
Tri-training~\cite{Zhi05}, since it has a simple but efficient
method of deciding how to label an unlabeled
instance~\cite{Nguyen2006}. Tri-training uses three classifiers of
the same algorithm, and if any two classifiers of the three
classifiers predict the same label for an unlabeled instance,
while the confidence of the labelling of the classifiers are not
needed to be explicitly measured, then that instance is used for
further training the other classifier. Such simplicity gives
Tri-training advantages over other Co-training algorithms, such as
the Co-training algorithm presented by  \cite{Sally2000}, which
frequently uses 10-fold cross validation on the labeled set to
determine how to label the unlabeled instances and how to produce
the final hypothesis. If the original labeled set is rather small,
cross validation will give high variance and is not useful for
model selection.

The simplicity also makes Tri-training faster than the algorithm
of Goldman, in which the frequent use of cross validation makes
the learning process time-consuming. At the beginning,
Tri-training bootstrap-samples the labeled data to generate
different training sets for three classifiers in order to make the
three classifiers diverse enough so that the Tri-training
algorithm does not degenerate into
\emph{self-training}~\cite{Nigam2000} with a single classifier.
However, question data is sparse and imbalanced. A question class
may include only a few questions in a corpus, so if the
bootstrap-sampling procedure duplicates some questions while
omitting some  questions in the classes with few questions, then
classifiers being trained on these bootstrap-sampled sets have
higher error rates than those of classifiers being trained on the
labeled set. In order to avoid this drawback, while still keeping
classifiers diverse, we propose to use more than one classifier
with different algorithms. The original training set is initially
used by the three classifiers without bootstrap-sampling. Another
proposal is to apply more than one \emph{views} (feature spaces)
in the learning process. This allows the three classifiers to
initially be trained from the labeled set with different feature
spaces and still have diversity. In the second proposal, for the
sake of simplicity, in the experiments, we used two different
classification algorithms: Support Vector Machines~\cite{Cortes95}
and Maximum Entropy Models~\cite{Adam96} in combination with two
views: \emph{bag-of-word} and \emph{bag-of-pos}$\&$\emph{word}
features. Two classifiers which use the first algorithm are
assigned different views, i.e., the first classifier gets
bag-of-word and the other gets bag-of-pos\&word features. The
third classifier uses the second algorithm with bag-of-word
features. With this strategy, three classifiers have initially
different hypotheses. Our experiments show promising results.

The remainder of the paper is organized as follows: Section 2
gives summaries of related work; Section 3 gives details about the
Tri-training algorithm and our modifications. Section 4 describes
data sets and feature selection. The experimental results are
given in Section 5 and conclusions are given in Section 6.


\section{Related work}

There are two broad classes of approaches to question classification: rule-based and statistical. In rule-based approaches, an expert manually constructs a number of regular expressions and keywords corresponding to each type of question. Meanwhile, in statistical approaches, a model is assumed and trained on a sufficiently large set of labelled questions in order to automatically find out useful patterns for classification.

Statistical approach have advantages over rule-based approach, because they require less expert labor and are easily portable to other domains.  Thus, recent work has concentrated on the approach, especially on the supervised learning approach which is a branch of the statistical approach.

\cite{Dell03} and \cite{Li02} explored different types of features
for improving the classification accuracy. Zhang and Lee
considered \emph{bag-of-word}, \emph{bag-of-ngram} (all continuous
word sequences in a question) features. Especially, they proposed
a kernel function called \emph{tree kernel} to enable support
vector machine (SVM) to take advantage of the syntactic structures
of questions. Li and Roth focused on several features:
\emph{words}, \emph{pos tags}, \emph{chunks} (non overlapping
phrases), \emph{named entities}, \emph{head chunks} (e.g., the
first noun chunk in a question) and \emph{semantically related
words} (words that often occur in a specific question type). They
also used hierarchical classifiers, in which a question is
classified by two classifiers: the first one classifies it into a
coarse category; the second determines the fine category from the
result produced by the first classifier. \cite{Hacioglu03}
employed error correcting codes in combination with support vector
machine to improve the results of classification.


\section{Tri-training semi-supervised learning and its modifications}

In this section, we describe the original Tri-training algorithm and give two proposals to improve it.

\subsection{Semi-supervised Tri-training algorithm}


In the Tri-training algorithm ~\cite{Zhi05}, three classifiers:
$h_{1}$, $h_{2}$ and $h_{3}$ are initially trained from a set by
bootstrap-sampling the labeled set \textit{L}. For any classifier,
an unlabeled instance can be labeled as long as the other two
classifiers predict the same label. For example, if $h_{1}$ and
$h_{2}$ agree on the labelling of an instance $x$ in the unlabeled
set $U$, then $x$ can be labeled for $h_{3}$. Obviously, in this
scheme, if the prediction of $h_{1}$ and $h_{2}$ on $x$ is
correct, then $h_{3}$ will receive a valid new instance for
further training; otherwise, $h_{3}$ will get an instance with a
noisy label. Nonetheless, as claimed in \cite{Zhi05}, even in the
worse case, the increase in the classification noise rate can be
compensated for, if the number of newly labeled instances is
sufficient.

\begin{figure}[b]
\small
\centering
\begin{tabular}{|l|l|}
\hline
    1\  \textbf{tri-training}($L$,$U$,$Learn$)  & 1\ \textbf{tri-training}($L$,$U$,$Learn_{1}$, \\
    2\ \ \textbf{for} $i$ $\in \{1..3\}$ \textbf{do} &   \ \ \ \ \ \ \ \ \ \ \ \ $Learn_{2},Learn_{3}$)\\
    3\ \ \ \ \ $S_{i}$ $\leftarrow BootstrapSample$($L$) &  2\ \ \ \textbf{for} $i$ $\in \{1..3\}$ \textbf{do} \\
    4\ \ \ \ \ $h_{i}$ $\leftarrow Learn$($S_{i}$) &     3 \\
    5\ \ \ \ \ $e'_{i}$ $\leftarrow 0.5$; $l'_{i}$ $\leftarrow 0$ &    4\ \ \ \ \ \ $h_{i}$ $\leftarrow Learn_{i}(L)$ \\
    6\ \ \textbf{end for} &     5\ \ \ \ \ \ $e'_{i}$ $\leftarrow 0.5$; $l'_{i}$ $\leftarrow 0$ \\
    7\ \ \textbf{repeat until} none of $h_{i}$ ($i$ $\in \{1..3\}$) changes & 6\ \ \ \textbf{end for} \\
    8\ \ \ \ \ \textbf{for} $i$ $\in \{1..3\}$ \textbf{do} &  $\ldots$ \\
    9\ \ \ \ \ \ \ \ $L_{i}$ $\leftarrow \emptyset$;$update_{i} \leftarrow FALSE$  & 25 $h_{i}\leftarrow Learn_{i}(L\cup L_{i});$ \\
    10\ \ \ \ \ \ \ $e_{i}$ $\leftarrow MeasureError$($h_{j}$\&$h_{k}$) ($j$,$k$$\neq$$i$) & \ \ \ \ \ \ $e'_{i} \leftarrow e_{i}$;$l'_{i}\leftarrow \verb"|"L_{i}\verb"|"$ \\
    11\ \ \ \ \ \ \ \textbf{if} ($e_{i}$\verb"<"$e'_{i}$) \textbf{then} & $\ldots$ \\
    12\ \ \ \ \ \ \ \ \ \ \textbf{for} every $x$ $\in$ $U$ \textbf{do} & \textsf{b) Tri-training with multiple}  \\
    13\ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{if} $h_{j}$($x$)=$h_{k}$($x$) ($j,k \neq i$) & \textsf{learning algorithms}    \\
    14\ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{then} $L_{i}\leftarrow L_{i} \cup \{(x,h_{j}(x))\}$  & \  \\
    15\ \ \ \ \ \ \ \  \ \ \textbf{end for}  & \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ \\
    16\ \ \ \ \ \ \ \ \ \ \textbf{if} ($l'_{i}$=0) \textbf{then} $l'_{i}$ $\leftarrow \lfloor \frac{e_{i}}{e'_{i}-e_{i}}+1 \rfloor$  &   \\
    17\ \ \ \ \ \ \ \ \ \ \textbf{if} ($l'_{i}$\verb"<|"$L_{i}$\verb"|") \textbf{then} & 1\ \textbf{tri-training}($L$,$U$,$Learn_{1},$ \\
    18\ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{if}($e_{i}$\verb"|"$L_{i}$\verb"|<"$e'_{i}l'_{i}$) \textbf{then} $update_{i} \leftarrow TRUE$  & \ \ \ \ \ \ \ \ \ \ \ \ $Learn_{2},Learn_{3}$)   \\
    19\ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{else if} $l'_{i}\verb">"\frac{e_{i}}{e'_{i}-e_{i}}$  & 2\ \ \ \textbf{for} $i \in \{1..3\}$ \textbf{do} \\
    20\ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{then} $L_{i}\leftarrow Subsample(L_{i},\lceil \frac{e'_{i}l'_{i}}{e_{i}}-1 \rceil);$  & 3\  \\
    21\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $update_{i}\leftarrow TRUE$  &  4\ \ \ \ \ \ $h_{i} \leftarrow Learn_{i}(view_{i}(L))$ \\
    22\ \ \ \ \ \ \textbf{end for}  &  5\ \ \ \ \ \ $e'_{i} \leftarrow 0.5; l'_{i} \leftarrow 0$  \\
    23\ \ \ \ \ \ \textbf{for} $i \in \{1..3\}$ \textbf{do}  &  6\ \ \ \textbf{end for} \\
    24\ \ \ \ \ \ \ \ \ \textbf{if} $update_{i}=TRUE$ \textbf{then}  & $\ldots$ \\
    25\ \ \ \ \ \ \ \ \ \ $h_{i} \leftarrow Learn(L \cup L_{i})$;$e'_{i} \leftarrow e_{i}$;$l'_{i}\leftarrow \verb"|"L_{i}\verb"|"$  & 25 $h_{i}\leftarrow Learn_{i}(view_{i}(L\cup L_{i}));$    \\
    26\ \ \ \ \ \ \textbf{end for}  &  \ \ \ \ \ \ $e'_{i} \leftarrow e_{i}$;$l'_{i}\leftarrow \verb"|"L_{i}\verb"|"$  \\
    29\ \ \textbf{end repeat}  & $\ldots$ \\
    30\ \ \textbf{Output}:$h(x)\leftarrow\mathop {\arg \max}\limits_{y \in label}\sum\limits_{i:h_{i}(x)=y} 1$    & \textsf{c) Tri-training with multiple}  \\
    \ \ \ \ \ \ \ \ \ \ \textsf{a) Original Tri-training algorithm} & \textsf{learning algorithms and views}  \\
\hline
\end{tabular}
\caption{Original and modified versions of Tri-training}
\label{tab:algorithm}
\end{figure}


Also in the algorithm, each classifier is initially  trained from
a data set generated by bootstrap-sampling the original labeled
set, in order to make classifiers diverse. If all the classifiers
are identical, then for any of three classifiers, the unlabeled
instances labeled by the other two classifiers will be the same as
those labeled by itself, thus, Tri-training becomes
\emph{self-training} with a single classifier. The pseudo-code of
the algorithm is described in Fig.~\ref{tab:algorithm}a, where
$Learn$ is a classification algorithm; $S_{i}$ is a labeled set
bootstrap-sampled from the labeled set $L$. $e'_{i}$ is the error
rate of $h_{i}$ in the ($t$-1)$^{th}$ round. With the assumption
that the beginning error rate is less than 0.5, therefore $e'_{i}$
is initially set to 0.5; $e_{i}$ is the error rate of $h_{i}$ in
the $t^{th}$ round; $L_{i}$ is the set of instances that are
labeled for $h_{i}$ in the $t^{th}$ round; $l'_{i}$ is the size of
$L_{i}$ at ($t$-1)$^{th}$ round, and in the first round it is
estimated by $\lfloor \frac{e_{i}}{e'_{i}-e_{i}}+1 \rfloor$;
$Subsample(L_{i},s)$ function randomly removes
\verb"|"$L_{i}\verb"|"-s$ number of instances from $L_{i}$ in
order to make current round have better performance than that of
the previous round, as proved in \cite{Zhi05};
$MeasureError(h_{j}\&h_{k})$ function attempts to estimate the
classification error rate of the hypothesis derived from the
combination of $h_{j}$ and $h_{k}$. Because it is difficult to
estimate the classification error rate on the unlabeled instances,
the algorithm only estimates on the labeled set with the
assumption that both the labeled and unlabeled instance sets have
the same distribution. In each iteration, $L_{i}$ is not merged
with the original labeled set $L$. It is put into the unlabeled
set $U$ as unlabeled instances.

The interesting point in the Tri-training algorithm is that, in
order to ensure that the current round of training has better
performance than that of the previous round, the size of each
newly labelled set $L_{i}$ must not be greater than
$\lceil\frac{e'_{i}l'_{i}}{e_{i}}-1\rceil$. If it is greater than
this value, the function $Subsample(L_{i},s)$ is used to randomly
remove redundant instances. The three classifiers are refined in
the training process, and the final hypothesis is produced via
\emph{majority voting}. For the sake of saving space, other
details can be seen in~\cite{Zhi05}.

\begin{table}[t]
\centering \caption{Question distribution. \#Tr and \#Te are the
number of labeled and testing questions.} \label{datadistribution}
\begin{tabular}{|l|c|c|l|c|c|l|c|c|}
\hline
\hspace{0.18in}Class & \#Tr & \#Te & \hspace{0.18in}Class & \#Tr & \#Te & \hspace{0.18in}Class & \#Tr & \#Te \\
\hline
ABBREV. & \textbf{86} & \textbf{9} & letter &  9 &  0 &  country & 155 & 3 \\
abb & 16 & 1 & other &  217 &  12 & mountain & 21 & 3  \\
exp & 70 & 8 & plant &  13 &  5 & other & 464 & 50 \\
DESC. & \textbf{1162} & \textbf{138} & product &  42 &  4 & state & 66 & 7 \\
definition & 421 & 123 & religion &  4 &  0 &  NUMERIC &  \textbf{896} &  \textbf{113}   \\
description & 274 & 7 & sport &  62 &  1 & code &  9 &  0 \\
manner & 276 & 2 & substance &  41 &  15 & count &  363 &  9 \\
reason & 191 & 6 & symbol &  11 &  0 & date &  218 &  47  \\
ENTITY & \textbf{1250} & \textbf{94} & technique &  38 &  1 & distance &  34 &  16  \\
animal & 112 & 16 & term & 93 & 7 &  money &  71 &  3\\
body & 16 & 2 & vehicle & 27 & 4 &  order &  6 &  0 \\
color & 40 & 10 & word & 26 & 0 & other &  52 &  12 \\
creative & 207 & 0 & HUMAN & \textbf{1223} & \textbf{65} &  period &  27 &  8  \\
currency & 4 & 6 & group & 47 & 6 &  percent &  75 &  3 \\
dis.med. &  103 &  2 & individual & 189 & 55 &  speed &  9 &  6 \\
event &  56 &  2 & title & 962 & 1 &  temp &  8 &  5 \\
food &  103 &  4 & description & 25 & 3 & size &  13 &  0  \\
instrument &  10 &  1 & LOCATION & \textbf{835} & \textbf{81} &  weight &  11 & 4  \\
lang &  16 &  2 & city & 129 & 18 & & &  \\
\hline
\end{tabular}
\end{table}



\subsection{Modified versions of Tri-training}

Due to its nature, question data type is very sparse and
imbalanced as shown in Table~\ref{datadistribution}. As stated in
\cite{Thorsten1998}, text data type, when represented in the
vector space model, is very sparse. For each document, the
corresponding document vector contains only a few entries which
are non-zero. A question contains quite a few words in comparison
with a document, so question data is even more sparse than text
data. Because of the imbalance, after bootstrap-sampling, each
newly created labeled set misses a number of questions as compared
to the original labeled set. If the missed questions are in a
class which contains only few questions, then the initial error
rate of each classifier increases when being trained from these
data sets. The final improvement after learning sometimes does not
compensate for this problem. In order to avoid this drawback, we
propose to use more than one algorithm for the three classifiers.
Each classifier is initially trained on the labeled set. Our
experiments showed that, if the performance of one of the three
classifiers is much better (or worse) than that of the others, the
final result is not improved. For this reason, a constraint on
three classifiers is that their performances are similar. The
modified version is depicted in Fig.~\ref{tab:algorithm}b, where
$Learn_{i}$ stands for different algorithms. We omit other lines
that are identical to those of the original algorithm in
Fig.~\ref{tab:algorithm}a.

Another proposal to avoid bootstrap-sampling is to use more than one views, such as two or three views in the learning process, so that each classifier can be trained from the original labeled set with different feature spaces while still making sure that they are diverse enough. The modified algorithm seems to have the standard Co-training style in the framework of Tri-training. The modified version according to this proposal is given in Fig.~\ref{tab:algorithm}c, where $view_{i}(L)$ is the $i^{th}$ view of the data set $L$. Other lines that are the same as those in Fig.~\ref{tab:algorithm}a are ignored. One important aspect of Tri-training algorithm is the needless of redundant views, so it can be applied to problems which have only one view. In this domain, it is easy to get redundant views, that is the reason of this proposal.


\section{Question data sets and feature selection}

\vspace{-0.5\baselineskip}
\subsection{Question data sets}

The Question Answering Track in Text Retrieval Conference \pagebreak
(TREC)
\cite{Voorhees1999,Voorhees2000,Voorhees2001} defines six question
classes, namely, \emph{abbreviation}, \emph{description},
\emph{entity}, \emph{human}, \emph{location} and \emph{numeric}.
However, for a question answering system in an open domain, six
classes are not sufficient enough. The larger the number of
question classes, the better a QA system locates and extracts
answers to questions~\cite{Li02}. Hence, from six coarse classes
defined by TREC, \cite{Li02} proposed to divide questions into 50
fine-grained classes. We follow this proposal to classify
questions into these finer-grained classes. In the experiments,
the data sets were those used in~\cite{Li02} with the total of
about 6000 questions (the exact number is 5952), of which 500
questions from TREC 10~\cite{Voorhees2001} were the test set, and
4 subsets of size 1000, 2000, 3000 and 4000 were created by
randomly selecting from other 5500 questions. These data sets are
all available on http://L2R.cs.uiuc.edu/$\sim$cogcomp/. We used
the 4 subsets as labeled sets, and created 4 correspondingly
unlabeled sets by selecting questions that do not belong to the
labeled sets.

The distribution of training and testing data is shown in Table \ref{datadistribution}, where the coarse classes are in capitals, followed by the corresponding fine classes. As listed in the table, some classes consist of few questions, such as 4 questions in the \emph{currency} and \emph{religion} classes.


\subsection{Feature selection}

In experiments, we used two primitive feature types which were
automatically extracted for each question, namely, bag-of-word and
bag-of-pos\&word.

Question classification is a little different from text
classification, because a question contains a small number of
words, while a document can have a large number of words. In text
classification, common words like `what', `is', etc. are
considered to be ``\emph{stop-words}'' and omitted as a dimension
reduction step in the process of creating features. This is an
important step in improving the performance of classification as
proven in \cite{Thorsten1998}. However, these words are very
important for question classification. Also, word frequencies play
an important role in document classification, whereas those
frequencies are usually equal to 1 in a question, thus, they do
not significantly contribute to the classification precision. In
order to keep these words while still reducing the dimension
space, we used a preprocessing step: all verbs were restored into
their infinitive forms. For example, the verb forms `is', `were',
`was', `are' and `am' were converted to `be'; plural nouns were
changed to their singular forms, such as `children' was converted
to `child'; words having the CD (\emph{cardinal number})
part-of-speech were made the same value, such as `1998', `2000',
`12' were changed into `100'. Given the question:

\textit{Who was President of Afghanistan in 1994?}

After the reduction step, it becomes:

  \textit{Who be President of Afghanistan in 100?}

After the reduction step, the vector (or vocabulary) $V$ of all
distinct words of questions in the corpus was constructed. Let the
size of $V$ be N, then each question $q$ was converted into a
vector $(q_{1}, q_{2},\ldots,q_{N})$, where $q_{i}$ is 1 if the
word $w_{i}$ in $V$ appears in $q$, otherwise $q_{i}$ is 0. These
vectors of numbers were the input of classifiers.

Interestingly, this dimension reduction step makes SVM reach the
precision of 81.4\% training on 5500 questions, while the same
features with SVM used in \cite{Dell03} gives the precision of
80.2\% training on the same data set and with the same
\emph{linear} kernel.

For bag-of-pos\&word features, each $word$ in a question was
converted into the form of \emph{POS-word}, where $POS$ is the
part-of-speech tag of $word$. We also used the preprocessing step
similarly to what applied to the process to generate bag-of-word
features, for example `how' was transformed into `WRB-how', `who'
was converted to `WP-who', `are', `is', `am', `were' and `was'
were converted to `AUX-be', etc. Given the question:

\textit{Who was President of Afghanistan in 1994?}

After the reduction step, it becomes:

 \textit{WP-Who AUX-be NN-president IN-of NN-Afghanistan IN-in CD-100?}

\begin{figure}[b]
\begin{center}
    \includegraphics{15-1ia1f2.eps}
\end{center}
\caption{The difference between bag-of-word and bag-of-pos\&word
features} \label{fig:difference}
\end{figure}



The process of converting questions into vectors of numbers was
similar to that of bag-of-word features. There is a difference
between bag-of-word and bag-of-pos\&word features. A word, such as
`plan' may play different roles in different questions. It can be
a verb in this question while being a noun in another one. The
role of the word can be distinguished in bag-of-pos\&word
features, because it is converted into `VB-plan' (if it is a verb)
or `NN-plan'(if it is a noun) as depicted in
Fig.~\ref{fig:difference}. The bag-of-word features do not have
this ability, so the bag-of-pos\&word features provide a richer
set of features. Concretely, for the dataset used in our
experiments, the size of the vocabulary $V$ for bag-of-word and
bag-of-pos\&word features is 7953 and 9876, respectively. Thus,
bag-of-pos\&word features may make classification algorithms
perform better than bag-of-word features.

\begin{table}[b]
\centering \caption{Precision of classification of SVM with
bag-of-word and bag-of-pos\&word features}
\label{precisionwithfeatures}
\begin{tabular}{|l|c|c|c|c|c|l|c|c|c|c|c|}
\hline
\multicolumn{1}{|c|}{Class} & \#T & \#W & \%W & \#P & \%P & \multicolumn{1}{|c|}{Class} & \#T & \#W & \%W& \#P & \%P \\
\hline
abb & 1 & 1 & 100 & 1 & 100 & term &  7 &  7 &  100 & 7 & 100 \\
exp & 8 & 6 & 75 & 6 & 75 & vehicle &  4 &  1 &  25 & 1 & 25 \\
definition & 123 & 123 & 100 & 123 & 100 & HUM:desc & 3 &  3 &  100 & 3 & 100 \\
description & 7 & 6 & 85.7 & 6 & 85.7 & group &  6 &  3 &  50 & 3 & 50 \\
manner & 2 & 2 & 100 & 2 & 100 & individual &  55 &  52 &  94.5 & 53 & 96.7 \\
reason & 6 & 5 & 83.3 & 5 & 83.3 & title  &  1 &  0 &  0 & 0 & 0 \\
animal & 16 & 8 & 50 & 9 & 56.3 & city &  18 &  15 &  83.3 & 14 & 77.8 \\
body & 2 & 1 & 50 & 2 & 100 & country &  3 &  3 &  100 & 3 & 100 \\
color & 10 & 10 & 100 & 10 & 100 & mountain &  3 &  2 &  66.7 & 2 & 66.7 \\
currency & 6 & 0 & 0 & 0 & 0 & LOC:other &  50 &  41 &  82 & 41 & 82 \\
dis.med & 2 & 0 & 0 & 1 & 50 & state &  7 &  7 &  100 & 7 & 100 \\
event & 2 & 0 &  0 & 0 &  0 & count &  9 &  9 &  100 & 9 & 100 \\
food & 4 & 1 & 25 & 1 & 25 & date &  47 &  44 &  93.6 & 44 & 93.6 \\
instrument & 1 & 1 & 100 & 1 & 100 & distance &  16 & 9 & 56.3 & 8 & 50 \\
lang & 2 & 2 & 100 & 2 & 100 & money &  3 &  0 &  0 & 0 & 0 \\
ENT:other & 12 & 6 & 50 & 5 & 41.7 & NUM:other &  12 &  5 &  41.7 & 5 & 41.7 \\
plant & 5 & 1 & 20 & 1 & 20 & percent & 3 &  0 &  0 & 1 & 33.3 \\
product & 4 & 0 &  0 & 0 &  0 & period &  8 &  7 &  87.5 & 7 & 87.5  \\
sport & 1 & 1 & 100 & 1 & 100 & speed &  6 &  3 &  50 & 3 & 50 \\
substance & 15 & 6 & 40 & 5 & 33.3 & temp &  5 &  0 &  0 & 0 & 0 \\
technique & 1 & 1 & 100 & 1 & 100 & weight & 4 &  1 &  25 & 1 & 25 \\
\hline
\multicolumn{7}{|r|}{TOTAL} & 500 &  393 &  78.6 & 395 & 79 \\
\hline
\end{tabular}
\end{table}


We tested the supervised learning with SVM algorithm on the
labeled set of size 4000 with bag-of-word and bag-of-pos\&word
features. The statistics is recorded in
Table~\ref{precisionwithfeatures}, where \textit{\#T} shows the
number of test questions belonging to each question class;
\textit{\#W} and \textit{\#P}, respectively, show the correctly
predicted questions of each question class with bag-of-word and
bag-of-pos\&word; \textit{\%W} and \textit{\%P}, respectively, are
precisions of classification with bag-of-word and
bag-of-pos\&word. The table shows that SVM fails to classify some
question classes, such as \textit{currency}, \textit{event} or
\textit{product} with bag-of-word and bag-of-pos\&word features.
SVM fails to classify the \textit{currency} class because in the
labeled set of size 4000, there is only one question belonging to
the class \textit{currency}. Another possible reason that make SVM
fails to correctly classify other classes is the lack of semantics
of bag-of-word and bag-of-pos\&word as seen in the three questions
from the labeled set:
\begin{list}{+}{}
\item \textit{What is a fear of shadows?} in the class \textit{ENTITY:disease.medicine}.
\item \textit{What is the origin of head lice?} in the class \textit{DESCRIPTION:description}.
\item \textit{What is the nickname for the state of Mississippi?} in the class \textit{LOCATION:state}.
\end{list}
Though these three questions belong to different classes, they have relatively similar forms. This causes ambiguity for classification algorithms. For improving classification precision, semantic features should be added, such as class-specific \textit{related words} used in \cite{Li02}. For each question class, class-specific \textit{related words} are a list of words that frequently appear in this class. With this method, a word in a question may have both syntactic and semantic roles, thus the feature is better, and the classification precision is improved.




\section{Experiments}

This section gives details about our implementation and
evaluation. Because the function $Subsample(.)$ (in line 20 of
Fig.~\ref{tab:algorithm}a) uses randomness to remove redundant
questions, so the set $L_{i}$ generated for each $h_{i}$ may be
different in each run; the final result of each run may be
different, and the result of the first run is not always the best
one. Thus, in all experiments, each algorithm was run 4 times and
the best as well as the average results were recorded.


\subsection{Experiments with multiple classifiers}

In the first experiment, we developed our programs based on the
Sparse Network of Winnows (SNoW) learning
architecture\footnote{The software is freely available at
http://L2R.cs.uiuc.edu/$\sim$cogcomp/software.php}~\cite{Andrew99},
which implements three learning algorithms: Perceptron, Bayes and
Winnow. We used these three learning algorithms to apply for the
three classifiers of the Tri-training algorithm. Besides, we
implemented the original Tri-training algorithm with a single
classification algorithm, such as Bayes, Perceptron or Winnow. All
the parameters of these algorithms, such as the learning rate
$\alpha$, threshold and the initial weight of Perceptron and
Winnow were default values. The bag-of-word features were used in
the experiment.

\begin{table}[t]
\hangcaption{The best and average precision (\%) of the
original Tri-training with single algorithm (TB, TP and TW)
and the modified Tri-training with Bayes, Perceptron and Winnow
(TBPW)} \label{experiment1}
\centering 
\begin{tabular}{|c||c|c||c|c||c|c||c|c||}
  \hline
  \multicolumn{9}{|c|}{The best precision} \\
  \hline
   &  \multicolumn{2}{|c|}{Bayes} &  \multicolumn{2}{|c|}{Perceptron} &
  \multicolumn{2}{|c|}{Winnow}
  & \multicolumn{2}{|c|}{Mod. TriTraining} \\
  \hline
  \# &  Base. & TB &  Base. & TP &  Base. & TW &   TBPW & N \\
  \hline
  1000 & 59.8 & 58.0 & \textit{60.2} & 60.4 & 58.0 & 60.4 &  \textbf{65.8} & 0 \\
  2000 & 58.4 & 58.0 & \textit{67.2} & 67.8 & 67.0 & 64.8 &  \textbf{68.8} & 1 \\
  3000 & 57.2 & 56.4 & \textit{68.4} & 70.0 & 49.4  & 65.4  & \textbf{72.0} & 2 \\
  4000 & 51.8 & 51.8 & 66.4 & 65.8 & \textit{71.6} & 71.4 &  \textbf{72.0} & 6 \\
  \hline
  \hline
\multicolumn{8}{|c|}{The average precision} \\
  \cline{1-8}
   &  \multicolumn{2}{|c|}{Bayes} &  \multicolumn{2}{|c|}{Perceptron} &
  \multicolumn{2}{|c|}{Winnow}
  & Mod. TriTraining \\
    \cline{1-8}
  \# &  Base. & TB &  Base. & TP &  Base. & TW &   TBPW  \\
    \cline{1-8}
  1000 & 59.8 & 55.85 & \textit{60.2} & 60.15 & 58.0 & 59.85 &  \textbf{64.15}  \\
  2000 & 58.4 & 57.80 & \textit{67.2} & 66.80 & 67.0 & 64.15 &  \textbf{68.60}  \\
  3000 & 57.2 & 56.30 & \textit{68.4} & 69.35 & 49.4  & 65.00  & \textbf{70.35}  \\
  4000 & 51.8 & 51.65 & 66.4 & 65.50 & \textit{71.6} & 69.65 &  69.70 \\
    \cline{1-8}
\end{tabular}
\end{table}

The best and average precision (of 4 runs) of the experiment is
listed in Table \ref{experiment1}, where TB, TP and TW
respectively stand for the original Tri-training with a single
classification algorithm Bayes, Perceptron and Winnow; TBPW stands
for the modified Tri-training with Bayes, Perceptron and Winnow
following the algorithm depicted in Fig.~\ref{tab:algorithm}b. For
the original Tri-training with a single classification algorithm
Bayes, Perceptron or Winnow, we compare their precision with the
baseline produced by the correspondingly supervised learning
algorithm being trained on the same labeled set. For example, the
baseline of the original Tri-training with Bayesian algorithm is
the precision of the supervised learning of Bayes on the same
labeled set. For our modified algorithm TBPW, we compared its
precision with the best precision of individually supervised
learning of the three classifiers (values in \textit{italic}) as
the baseline. We also carried out the sign test \cite{Kanji1994}
for our modified Tri-training algorithm, with a total number of 25
subsets at the 95\% significance level (\textit{p}=0.05), in which
the corresponding critical value is 7. The column `\textit{N}'
shows the number of tests on subsets in which the precision of
semi-supervised learning is less than the baseline. According to
the sign test theory, a test is significant if the value in the
column `\textit{N}' is less than or equal the critical value. The
sign test shows that our algorithm is significant at the level of
95\% for all tests.

The results show that the precision of supervised learning of
Bayes, Perceptron and Winnow is not sensitive to the size of
labeled sets. Concretely, when the size of the labeled set
increases, the corresponding precision does not increase. Maybe,
question data type and bag-of-word features are not suitable for
these learning algorithms.






In the second experiment, we used two algorithms: Maximum Entropy
Model\footnote{We used a free open source
implementation of Maximum Entropy Model available at \\
http://homepages.inf.ed.ac.uk/s0450736/pmwiki/pmwiki.php}(MEM),
and SVM\footnote{We used a free implementation of SVM available at
http://www.csie.ntu.edu.tw/$\sim$cjlin/libsvmtools/} which has
been proven to perform well for text
classification~\cite{Thorsten1998}. The selection of MEM is based
on our investigation. It has better performance than Bayes, Winnow
and Perceptron. In this domain, SVM classifier has better
performance than that of MEM classifier, thus, we used two SVM
classifiers and one MEM classifier in the implementation with the
expectation of making two SVM classifiers to have high degree of
decision on final hypothesis. With SVM classifiers, we used
\emph{linear} kernel, and other parameters (e.g., parameter
\textit{C}) were default. In this domain, other kernels of SVM,
such as \emph{polynomial}, \emph{radial basic function} or
\emph{sigmoid}, give poor performance. For MEM classifier, we used
Gaussian smoothing, and all default values of parameters (e.g.,
L-BFGS parameter estimation). Bag-of-word features were used for
all classifiers. In this configuration, the two SVM classifiers
are identical at the beginning. In the learning loop, because of
the randomness, the $Subsample(.)$ procedure (in the line 20 of
the algorithm in Fig.~\ref{tab:algorithm}) creates different
$L_{i}$ sets for the two SVM classifiers. As the results, the two
SVM classifiers have different hypotheses when they are re-trained
(in line 25 of the algorithm in Fig.~\ref{tab:algorithm} a).

\begin{table}[b]
\hangcaption{The best and average precision (\%) of the
original Tri-training with single MEM, SVM \break algorithm 
(TMW and TSW) and the modified Tri-training with both MEM and SVM (TSSM)}
\label{experiment2}
\centering 
\begin{tabular}{|c||c|c||c|c||c|c||}
  \hline
  \multicolumn{7}{|c|}{The best precision} \\
  \hline
  &
  \multicolumn{2}{|c|}{MEM } &
  \multicolumn{2}{|c|}{SVM } &
  \multicolumn{2}{|c|}{Mod. Tritraining} \\
  \hline
  \# & Base. &  TMW &  Base. & TSW  & TSSM & N \\  \hline
   1000 & 67.6  & 68.0 & \textit{68.4}  & 67.6 & 68.4 & - \\
   2000 & 74.8  & 75.2 & \textit{75.6}  & 76.2 & \textbf{76.4} & 4 \\
   3000 & 76.8  & 76.4 & \textit{78.2} &  78.4 & \textbf{78.6} & 6 \\
   4000 & 77.2  & 78.2 & \textit{78.6} & 78.6 & \textbf{78.8} & 7 \\
  \hline
  \hline
\multicolumn{6}{|c|}{The average precision} \\
\cline{1-6}
  &
  \multicolumn{2}{|c|}{MEM } &
  \multicolumn{2}{|c|}{SVM } &
  Mod. Tritraining \\
\cline{1-6}
  \# & Base.  & TMW &  Base. &  TSW  & TSSM  \\  \cline{1-6}
   1000 & 67.6  & 67.40 & \textit{68.4} &  66.95 & 68.25  \\
   2000 & 74.8  & 74.10 & \textit{75.6} &  75.75 & \textbf{76.10}  \\
   3000 & 76.8  & 76.20 & \textit{78.2} &  78.00 & 78.20  \\
   4000 & 77.2  & 77.40 & \textit{78.6} &  78.50 & 78.50  \\
\cline{1-6}
\end{tabular}
\end{table}


Table~\ref{experiment2} shows the best and the average precision
(of 4 runs) of different algorithms, where TSW  and TMW,
respectively, stand for the original Tri-training algorithm with
SVM and MEM algorithms; TSSM stands for the modified Tri-training
with two SVM classifiers and a MEM classifier following the
algorithm described in Fig. \ref{tab:algorithm}b. We used the
precision of supervised learning with MEM and SVM on the same
labeled sets as the baseline to compare with the precision of  TMW
and TSW. For TSSM, we selected the best precision of supervised
learning with MEM and SVM on the same labeled sets (values in
\textit{italic}) as the baseline. Similar to our first experiment,
we carried out the sign test on 25 subsets and at the 95\%
significance level. The column `\textit{N}' records the number of
tests on subsets, in which the precision of semi-supervised is
less than the baseline. Except for the test on the labeled set
size of 1000 which is not improved, our other tests are
significant at the level of 95\%.

As shown in the table, MEM and SVM are sensitive to the size of
the labeled sets. The precision is increased when the size of
labeled set increases. This indicates that MEM and SVM are
suitable for question data with bag-of-word features.
\subsection{Experiments with two different algorithms and two views}
In the third experiment, we implemented the second proposal of
using more than one views following the algorithm described in
Fig.~\ref{tab:algorithm}c. In theory, we can use three different
algorithms with distinct views, however, our primary purpose is to
make the three classifiers diverse at the initial step, so two
different algorithms, two views and a suitable assignment of views
to classifiers are sufficient. Concretely, among the three
classifiers, two of them were SVM classifiers and the third one
was a MEM classifier. The first view (feature space) was
bag-of-word, and the second view was bag-of-pos\&word. We set two
SVM classifiers two different views, while the MEM classifier used
either of them. Concretely, the first SVM classifier used
bag-of-word features, the second SVM classifier used
bag-of-pos\&word features and the MEM classifier used bag-of-word
features.

\begin{table}[b]
\hangcaption{The best precision (\%) of the original
Tri-training with single algorithm (TMW, TMP, 
	TSW and TSP) and the modified Tri-training with MEM, SVM with two views (TSSM2)}
\label{twoviews}
\centering 
\begin{tabular}{|c||c|c||c|c||c|c||c|c||c|c|c||}
  \hline
   &
  \multicolumn{2}{|c|}{MEM-word} &
  \multicolumn{2}{|c|}{MEM-pos} &
  \multicolumn{2}{|c|}{SVM-word} &
  \multicolumn{2}{|c|}{SVM-pos}
  & \multicolumn{2}{|c|}{Two views} \\
  \hline
  \# &  Base. & TMW &  Base. & TMP &  Base. & TSW &  Base. & TSP &   TSSM2 & N \\
  \hline
  1000 & 67.6 & 68.0 & 68.8 & \textbf{69.0} & 68.4 & 67.6 &  \textit{69.2}  & 66.6 &  68.4 & - \\
  2000 & 74.8 & 75.2 & 75.4 & 74.2 & \textit{75.6} & 76.2 & 75.2  & 74.6 &  \textbf{76.0} & 5 \\
  3000 & 76.8 & 76.4 & 76.8 & 76.2 & \textit{78.2} & 78.4 & 77.0  & 77.0 &  \textbf{79.0} & 3 \\
  4000 & 77.2 & 78.2 & 77.8 & 77.8 & 78.6 & 78.6 & \textit{79.0}  & 78.4 &  \textbf{80.4} & 2 \\
  \hline

\end{tabular}
\end{table}



Let TMW and TMP be the original Tri-training algorithm with MEM
using bag-of-word and bag-of-pos\&word features, respectively; Let
TSW and TSP respectively be the original Tri-training with SVM
using bag-of-word and bag-of-pos\&word features; Let TSSM2 be the
modified Tri-training with two SVM and a MEM classifiers following
the algorithm described in Fig.~\ref{tab:algorithm}c using two
views: bag-of-word and bag-of-pos\&word. For TMW, TMP, TSW and
TSP, the baseline is the precision of supervised learning with
corresponding algorithm and feature space. The best precision of
the experiment is given in Table \ref{twoviews}. The sign test
similar to previous experiments is also carried out. Except for
the test with the size of 1000, the other tests are significant at
the level of 95\%.

\begin{table}[b]
\hangcaption{The average precision (\%) of the original
Tri-training with single algorithm (TMW, TMP, 
	TSW and TSP) and the modified Tri-training with MEM, SVM with two views (TSSM2)}
\label{twoviews_2}
\centering 
\begin{tabular}{|c||c|c||c|c||c|c||c|c||c|c||}
  \hline
   &
  \multicolumn{2}{|c|}{MEM-word} &
  \multicolumn{2}{|c|}{MEM-pos} &
  \multicolumn{2}{|c|}{SVM-word} &
  \multicolumn{2}{|c|}{SVM-pos}
  & Two views \\
  \hline
  \# &  Base. & TMW &  Base. & TMP &  Base. & TSW &  Base. & TSP &   TSSM2  \\
  \hline
  1000 & 67.6  & 67.40 & 68.8 & 68.55 &  68.4 &  66.95 & \textit{69.2}  & 66.30 &  67.90  \\
  2000 & 74.8  & 74.10 & 75.4 & 73.55 &  \textit{75.6} &  75.75 & 75.2  & 74.30 &  \textbf{75.85}  \\
  3000 & 76.8  & 76.20 & 76.8 & 75.90 &  \textit{78.2} &  78.00 & 77.0  & 76.85 &  \textbf{78.45}  \\
  4000 & 77.2  & 77.40 & 77.8 & 77.45 &  78.6 &  78.50 & \textit{79.0}  & 78.30 &  \textbf{79.65}  \\
  \hline
\end{tabular}
\end{table}

\begin{table}[b]
\centering \caption{The size of $L_{i}$ in each round
corresponding to the experiment in Table~\ref{twoviews}}
\label{tab:sizeLi}
\begin{tabular}{|c|c|r|r|r|r|r|r|r|r|r|}
\hline
 \raisebox{-1.50ex}[0cm][0cm]{\#} & \raisebox{-1.50ex}[0cm][0cm]{Iter.} & \multicolumn{3}{|c|}{TMW} & \multicolumn{3}{|c|}{TMP} & \multicolumn{3}{|c|}{TSW} \\
\cline{3-11} & &  $L_{1}$ & $L_{2}$ & $L_{3}$ & $L_{1}$ &  $L_{2}$ & $L_{3}$ & $L_{1}$ & $L_{2}$ &  $L_{3}$  \\
  \hline
\multirow{2}{*}{1000} &   1 & 30 & 30 & 5  & 42 & 42 & 5 &  26 & 30 & 30  \\
  & 2 & 4262 & 4262 & 4452 &  4122 & 4122 & 4452 & 489 & 492 & 496   \\
  \hline
\multirow{2}{*}{2000} &   1 & 50 & 50 & 6 & 32 & 47 & 30 & 34 & 23 & 28   \\
  & 2 & 3199 & 3199 & 3452 &  3198 & 3216 & 3309 & 489 & 486 & 493   \\
  \hline
\multirow{2}{*}{3000} &   1 & 41 & 36 & 48  & 54 & 81 & 42 & 41 & 33 & 32  \\
  & 2 & 1491 & 1486 & 1471 &  2294 & 2351 & 2316 & 748 & 732 & 734   \\
  \hline
\multirow{2}{*}{4000} &  1 & 40 & 41 & 43  & 65 & 47 & 55 &  46 & 39 & 42  \\
  & 2 & 648 & 245 & 196  & 990 & 665 & 332 & 391 & 395 & 390   \\
\hline
\multicolumn{11}{c}{} \\
 \cline{1-8}
 \raisebox{-1.50ex}[0cm][0cm]{\#} & \raisebox{-1.50ex}[0cm][0cm]{Iter.} & \multicolumn{3}{|c|}{TSP} & \multicolumn{3}{|c|}{TSSM2} & \multicolumn{3}{c}{} \\
\cline{3-8} & &  $L_{1}$ & $L_{2}$ & $L_{3}$ & $L_{1}$ &  $L_{2}$ & $L_{3}$ &  \multicolumn{3}{|c}{}   \\
\cline{1-8}
\multirow{2}{*}{1000} &   1 & 32 & 23 & 27  & 3226 & 499 & 499 &   \multicolumn{3}{|c}{}   \\
  & 2 & 4256 & 4258 & 4236 &  --- & --- & --- &  \multicolumn{3}{|c}{}   \\
\cline{1-8}
\multirow{2}{*}{2000} &   1 & 29 & 24 & 31   & 999 & 499 & 499 &  \multicolumn{3}{|c}{}     \\
  & 2 & 984 & 974 & 975 &  --- & --- & --- &  \multicolumn{3}{|c}{}  \\
\cline{1-8}
\multirow{2}{*}{3000} &   1 & 29 & 46 & 32   & 187 & 750 & 187 &  \multicolumn{3}{|c}{}   \\
  & 2 & 1497 & 1497 & 1480 & 373 & 373 & 0 &  \multicolumn{3}{|c}{}  \\
\cline{1-8}
\multirow{2}{*}{4000} &  1 & 29 & 39 & 37  & 222 & 399 & 199 &  \multicolumn{3}{|c}{}  \\
  & 2 & 993 & 997 & 986   & --- & --- & --- &  \multicolumn{3}{|c}{}  \\
\cline{1-8}
\end{tabular}
\end{table}

\begin{table}[t]
\centering \caption{The average size of $L_{i}$ in each round
corresponding to the experiments in Table \ref{twoviews_2}}
\label{tab:sizeLi_2}
\begin{tabular}{|c|c|r|r|r|r|r|r|r|r|r|}
\hline
 \raisebox{-1.50ex}[0cm][0cm]{\#} & \raisebox{-1.50ex}[0cm][0cm]{Iter.} & \multicolumn{3}{|c|}{TMW} & \multicolumn{3}{|c|}{TMP} & \multicolumn{3}{|c|}{TSW} \\
\cline{3-11} & &  $L_{1}$ & $L_{2}$ & $L_{3}$ & $L_{1}$ &  $L_{2}$ & $L_{3}$ & $L_{1}$ & $L_{2}$ &  $L_{3}$  \\
  \hline
\multirow{2}{*}{1000} &   1 &         22 &       30.5 &       13.5 &       4.75 &         22 &         22 &         24 &         33 &      28.25 \\
 &          2 &       4273 &    4212.25 &       4288 &       4018 &       3973 &     3979.5 &        490 &        494 &      488.5 \\
  \hline
\multirow{2}{*}{2000} &   1 &      32.25 &      47.25 &       31.5 &      34.25 &       45.5 &         50 &         29 &         33 &      26.75 \\
 &          2 &    3220.75 &    3203.25 &    3335.25 &     3221.5 &    3240.75 &       3225 &     488.25 &      490.5 &     488.75 \\
  \hline
\multirow{ 2}{*}{3000} &          1 &         43 &         44 &         44 &      48.25 &         60 &         42 &         36 &      33.75 &      36.75 \\
     &     2 &     1485.5 &    1480.75 &    1479.75 &    2297.75 &    2325.75 &     1904.5 &        740 &     733.75 &      741.5 \\
\hline
\multirow{ 2}{*}{4000} &          1 &       46.5 &         41 &         46 &      49.75 &         45 &         47 &      41.25 &      41.75 &         36 \\
 &          2 &     655.25 &      554.5 &     512.25 &      527.5 &     641.75 &     672.25 &      395.5 &        395 &      390.5 \\
\hline
\multicolumn{11}{c}{} \\
\cline{1-8}
 \raisebox{-1.50ex}[0cm][0cm]{\#} & \raisebox{-1.50ex}[0cm][0cm]{Iter.} & \multicolumn{3}{|c|}{TSP} & \multicolumn{3}{|c|}{TSSM2} & \multicolumn{3}{|c}{} \\
\cline{3-8} & &  $L_{1}$ & $L_{2}$ & $L_{3}$ & $L_{1}$ &  $L_{2}$ & $L_{3}$ &  \multicolumn{3}{|c}{}   \\
\cline{1-8}
\multirow{2}{*}{1000} &          1 &      30.25 & 28.75 & 25.75 &       3226 &        499 &        499 & \multicolumn{ 3}{|c}{} \\
 &          2 &    4244.25 &    4236.75 &    4233.25 &          --- &         --- &          --- &               \multicolumn{ 3}{|c}{} \\
\cline{1-8}
\multirow{ 2}{*}{2000} &          1 &      26.75 &      30.25 &         28 &        999 &        499 &        499 &               \multicolumn{ 3}{|c}{} \\
 &          2 &        980 &        980 &     986.25 &          --- &          --- &          --- &               \multicolumn{ 3}{|c}{} \\
\cline{1-8}
\multirow{ 2}{*}{3000} &          1 &      29.75 &      31.25 &         34 &        187 &        750 &        187 &               \multicolumn{ 3}{|c}{} \\
 &          2 &    1474.25 &    1485.25 &       1476 &        302 &      283.5 &          0 &               \multicolumn{ 3}{|c}{} \\
\cline{1-8}
\multirow{2}{*}{4000} &          1 &      35.75 &      36.25 &         35 &        222 &        399 &        199 &               \multicolumn{ 3}{|c}{} \\
 &          2 &        983 &      982.5 &     988.25 &          --- &          --- &          --- &               \multicolumn{ 3}{|c}{} \\
\cline{1-8}
\end{tabular}
\end{table}

We recorded the average precision (of 4 runs) of each algorithm of
the experiment in Table~\ref{twoviews_2}. Table~\ref{tab:sizeLi}
recorded the number of new questions ($L{i}$) added for each
classifier in each iteration of the experiment in
Table~\ref{twoviews}, where `Iter.' stands for iteration. The
average values (in 4 tests) of these $L{i}$ are recorded in
Table~\ref{tab:sizeLi_2}. In these experiments, TMW, TMP, TSW and
TSP took two iterations while TSSM2 took at most two iterations.
The initial classifiers were very different because of the use of
function $BootstrapSample(.)$ in Line 3 of
Fig.~\ref{tab:algorithm}a, however after having been re-trained in
Line 25 of Fig.~\ref{tab:algorithm}, the three classifiers became
very similar, and took many unlabelled questions in the second
iteration, and stopped.


\subsection{Experiments with self-training algorithm}

This section implemented a self-training algorithm to compare the
results with our modified Tri-training algorithm. In
self-training, a single classifier is used to label questions in
the unlabeled set to augment the labeled set for further training.
The pseudo-code of the self-training algorithm is depicted in
Fig.~\ref{selftrainingalg}~\cite{Nigam2000}, where $L$, $U$ are
the labeled and unlabeled sets, correspondingly; $\theta$ is a
threshold in the range of [0,1]; $m$ is the number of iterations
($m$ is 20 in our experiments); $Learn$ is a classification
algorithm; $U'$ is a subset of unlabeled questions ($U'\subseteq
U$); $L'$ is a set of questions that are labeled at each
iteration. In the training loop, we select a pool $U'$ of
unlabeled questions smaller than $U$, as suggested
by~\cite{Blum98}.

\begin{figure}[t]
\centering
\begin{tabular}{|l|l|}
\hline
\textbf{self-training}($L,U,Learn,\theta,m$) \\
1\ \ \ \ \ Create a subset $U'$ by randomly selecting examples from $U$ \\
2\ \ \ \ \ $h\leftarrow Learn(L)$ \\
3\ \ \ \ \ \textbf{repeat} $m$ times \\
4\ \ \ \ \ \ \ \ \ \ $L' \leftarrow \emptyset$ \\
5\ \ \ \ \ \ \ \ \ \ \textbf{for} every $x\in U'$  \\
6\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{if} the prediction $h(x)$ has the confidence greater than $\theta$ \textbf{then} \\
7\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $L' \leftarrow L'\cup \{(x,h(x))\}$ \\
8\ \ \ \ \ \ \ \ \ \ \textbf{end for} \\
9\ \ \ \ \ \ \ \ \ \ $h \leftarrow Learn(L\cup L')$ \\
10\ \ \ \ \ \ \ \ Re-create the subset $U'$ by randomly selecting examples from $U$ \\
11\ \ \ \ \ \textbf{end repeat} \\
12\ \ \textbf{Output}: the learned hypothesis $h$ \\
\hline
\end{tabular}
\caption{Self-training algorithm} \label{selftrainingalg}
\end{figure}

\begin{table}[t]
\centering
\caption{The precision of self-training with SVM}
\label{selftrainingresult}
\begin{tabular}{|c||c|c||c|c||c|c||c|c||c|c||}
\hline
\raisebox{-1.50ex}[0cm][0cm]{\#} & \multicolumn{2}{|c|}{1000} & \multicolumn{2}{|c|}{2000} & \multicolumn{2}{|c|}{3000} & \multicolumn{2}{|c|}{4000} \\
\cline{2-9}
 & Base. & Self. & Base. & Self. & Base. & Self. & Base. & Self. \\
 \hline
Precision & 68.4 & 65.8 & 75.6 & 73.4 & 78.2 & 76.2 & 78.6 & 78.4 \\
 \hline
\end{tabular}
\end{table}



In each iteration, a subset $U'$ of unlabeled questions is selected, and the set $L'$ is created by selecting questions from $U'$ which are predicted by the hypothesis $h$ with confidence (prediction probability) greater than a threshold $\theta$ ($\theta$ is 0.9 in our experiments). The union of $L'$ and $L$ is used to train the classifier. Note that $L'$ is not merged with $L$ in each iteration. Instead, it is regarded as unlabeled questions, and put back into the unlabeled set $U$ again. The training process terminates after $m$ iterations.




We carried out self-training on labeled sets of different size
(1000, 2000, 3000 and 4000), and the classification algorithm is
SVM with bag-of-word features. The results of our experiments are
given in Table \ref{selftrainingresult}, where `\textit{Base.}' is
the precision of supervised learning which is used as the
baseline; `\textit{Self.}' is the precision of the self-training.
The results show that most final precision of self-training is not
improved. Though only questions in the unlabeled set $U'$ with
high prediction probability are selected to form the labeled set
$L'$, it can not guarantee that those questions are correctly
predicted as our observation. Thus, in each iteration, the newly
created labeled set may contain mislabeled questions, and the
error rate may consequently increase. In general, the
self-training is not well suitable for question data type with
bag-of-word features.



\subsection{Discussion}

Through experiments we can see that self-training is not suitable
for solving this task, because its method to add unlabeled
questions for further training the classifier is not good. The
original Tri-training algorithm has a better method of adding
unlabeled questions based on the agreement of two classifiers.
However, the bootstrap-sampling step may decrease the initial
precision of each classifier and the final precision is hard to be
improved.  Our two proposals remove the bootstrap-sampling while
still ensure the three classifiers to have different hypotheses,
and the experiments have proved the proposals to be suitable.



\section{Conclusion}

This paper applied semi-supervised learning to exploit unlabeled
questions to improve the performance of question classification
task and proposed two ways of modifying the Tri-training algorithm
presented by~\cite{Zhi05} to make it more suitable for question
data type. The proposals dealt with a problem at the initial step
of Tri-training, where the original labeled set is
bootstrap-sampled to generate three different labeled sets, in
order to make the three classifiers have different hypotheses,
which may make the initial error rate of each classifier increase.
With the purpose of using the original labeled set for all
classifiers, while ensuring that they are still diverse, in the
first proposal, we used more than one learning algorithm for the
three classifiers and the second proposal is to use multiple
learning algorithms in combination with more than one views. Our
experiments indicate that the performance is improved.

In the current implementation, we have not considered to select
other better feature types, such as those used in \cite{Li02}.
This is one interesting issue to explore in future to achieve
higher precision.

Our modified versions of Tri-training algorithm do not have any
constraints on data types, therefore, one more issue which is
worth studying in the future is to apply these algorithms in other
domains, such as text classification.



\acknowledgment

This study was supported by Japan Advanced Institute of Science
and Technology, the 21$^{st}$ Century  COE Program: ``Verifiable
and Evolvable e-Society". 
We would like to express special thanks to the blind reviewer of this paper for his/her careful review as well as corrections and suggestions.


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

\bibitem[\protect\BCAY{Berger et al.}{Berger, et al.}{1996}]{Adam96}
Berger, A., Pietra, S. D., and Pietra, V. D. \BBOP 1996\BBCP.
\newblock \BBOQ A maximum entropy approach to natural language processing\BBCQ\
\newblock  \emph{Computational Linguistics}, {\Bbf 22} (1), pp. 39--71.

\bibitem[\protect\BCAY{Blum \BBA\ Mitchell}{Blum and Mitchell}{1998}]{Blum98}
Blum, A. and Mitchell, T. \BBOP 1998\BBCP.
\newblock \BBOQ Combining labeled and unlabeled data with co-training\BBCQ\
\newblock  \emph{Proceedings of the 11$^{th}$ Annual Conference on Computational Learning Theory, Madison, WI}, pp. 92--100.

\bibitem[\protect\BCAY{Carlson et al.}{Carlson, et al.}{1999}]{Andrew99}
Carlson, A., Cumby, C., and Roth, D. \BBOP 1999\BBCP.
\newblock \BBOQ The SNoW learning architecture\BBCQ\
\newblock \emph{Technical Report UIUC-DCS-R-99-2101, UIUC Computer Science Department}.

\bibitem[\protect\BCAY{Cortes and Vapnik}{Cortes and Vapnik}{1995}]{Cortes95}
Cortes, C., and Vapnik, V. \BBOP 1995\BBCP.
\newblock \BBOQ Support vector networks\BBCQ\
\newblock \emph{Machine Learning}, {\Bbf 20} (3), pp. 273--297.

\bibitem[\protect\BCAY{Goldman and Zhou}{Goldman and Zhou}{2000}]{Sally2000}
Goldman, S. and Zhou, Y.  \BBOP 2000\BBCP.
\newblock \BBOQ Enhancing supervised learning with unlabeled data\BBCQ\
\newblock \emph{Proceedings of the 17$^{th}$ International Conference on Machine Learning}, pp. 327--334.

\bibitem[\protect\BCAY{Joachims}{Joachims}{1998}]{Thorsten1998}
Joachims, T.  \BBOP 1998\BBCP.
\newblock \BBOQ Text categorization with Support vector machines: Learning with many relevant features\BBCQ\
\newblock \emph{Proceedings of ECML-98, the 10$^{th}$ European Conference on Machine Learning}, pp. 137--142.

\bibitem[\protect\BCAY{Kanji}{Kanji}{1994}]{Kanji1994}
Kanji, G. \BBOP 1994\BBCP.
\newblock \BBOQ 100 Statistical tests,''
\newblock \emph{SAGE Publications}.

\bibitem[\protect\BCAY{Kadri and Wayne}{Kadri and Wayne}{2003}]{Hacioglu03}
Kadri, H. and Wayne, W. \BBOP 2003\BBCP.
\newblock \BBOQ Question classification with Support vector machines and error correcting codes\BBCQ\
\newblock \emph{Proceedings of NAACL/Human Language Technology Conference}, pp. 28--30.

\bibitem[\protect\BCAY{Li and Roth}{Li and Roth}{2002}]{Li02}
Li, X. and Roth, D. \BBOP 2002\BBCP.
\newblock \BBOQ Learning question classifiers\BBCQ\
\newblock \emph{Proceedings of the 19$^{th}$ International Conference on Computational Linguistics}, pp. 556--562.

\bibitem[\protect\BCAY{Nguyen et~al.}{Nguyen, et al.,}{2006}]{Nguyen2006}
 Nguyen, T. T., Nguyen, L. M., and Shimazu, A. \BBOP 2006\BBCP.
\newblock \BBOQ Using semi-supervised learning for question classification\BBCQ\
\newblock \emph{Proceedings of the 21$^{st}$ International Conference on the Computer Processing of Oriental
Languages}, pp. 31--41.

\bibitem[\protect\BCAY{Nigam and Ghani}{Nigam and Ghani}{2000}]{Nigam2000}
Nigam, K. and Ghani, R.  \BBOP 2000\BBCP.
\newblock \BBOQ Analyzing the effectiveness and applicability of co-training\BBCQ\
\newblock \emph{Proceedings of the 9$^{th}$ International Conference on Information and Knowledge (CIKM-2000)}, pp. 86--93.

\bibitem[\protect\BCAY{Voorhees}{Voorhees}{1999}]{Voorhees1999}
 Voorhees, E. \BBOP 1999\BBCP.
\newblock \BBOQ The TREC-8 Question answering track report\BBCQ\
\newblock \emph{Proceedings of the 8$^{th}$ Text Retrieval Conference (TREC8)}, pp. 77--82.

\bibitem[\protect\BCAY{Voorhees}{Voorhees}{2000}]{Voorhees2000}
Voorhees, E. \BBOP 2000\BBCP.
\newblock \BBOQ The TREC-9 Question answering track\BBCQ\
\newblock \emph{Proceedings of the 9$^{th}$ Text Retrieval Conference (TREC9)}, pp. 71--80.

\bibitem[\protect\BCAY{Voorhees}{Voorhees}{2001}]{Voorhees2001}
Voorhees, E. \BBOP 2001\BBCP.
\newblock \BBOQ Overview of the TREC 2001 Question answering track\BBCQ\
\newblock \emph{Proceedings of the 10$^{th}$ Text Retrieval Conference (TREC10)}, pp. 157--165.

\bibitem[\protect\BCAY{Zhang \BBA\ Lee}{Zhang and Lee}{2003}]{Dell03}
Zhang, D. and Lee, W. S. \BBOP 2003\BBCP.
\newblock \BBOQ Question classification using Support vector machine\BBCQ\
\newblock \emph{Proceedings of the 26$^{th}$ Annual International ACM SIGIR Conference}, pp. 26--32.

\bibitem[\protect\BCAY{Zhou and Li}{Zhou and Li}{2005}]{Zhi05}
Zhou, Z. and Li, M.  \BBOP 2005\BBCP.
\newblock \BBOQ Tri-training: Exploiting unlabeled data using three classifiers\BBCQ\
\newblock  \emph{IEEE Transactions on Knowledge and Data Engineering}, {\Bbf 17} (11), pp. 1529--1541.

\end{thebibliography}


\begin{biography}


\bioauthor[:]{Tri Thanh Nguyen}{received the Bachelor degree in
Faculty of Information Technology, Vietnam National University of
Hanoi (VNUH) in 1999, and Master degree at Asian Institute of
Technology (AIT), Thailand in 2002. From February 2003, he worked
as a lecturer for Faculty of Information Technology, College of
Technology, VNUH. Since April 2005, he has been a PhD student in
Natural Language Processing Laboratory, School of Information
Science, Japan Advanced Institute of Science and Technology
(JAIST).}

\bioauthor[:]{Le Minh Nguyen}{received the Bachelor in Information
Technology from Hanoi University of Science, and Master degrees in
Information Technology from VNUH, in 1998 and 2001, respectively.
He received Doctoral degree in School of Information Science,
JAIST in 2004. Since 2005, he has been a Post-doctoral Fellow at
Natural Language Processing Laboratory, School of Information
Science, JAIST. His research interests include Text Summarization,
Natural Language Understanding, Machine Translation, and
Information Retrieval.}

\bioauthor[:]{Akira Shimazu}{received the Bachelor and Master
degrees in mathematics from Kyushu University in 1971 and 1973,
respectively, and a Doctoral degree in Natural Language Processing
from Kyushu University in 1991.  From 1973 to 1997, he worked at
Musashino Electrical Communication Laboratories of Nippon Telegram
and Telephone Public Corporation, and at Basic Research
Laboratories of Nippon Telegraph and Telephone Corporation.  From
2002 to 2004, he was the president of the Association for Natural
Language Processing. He has been a professor in the Graduate
school of Information Science, JAIST since 1997. }

\end{biography}

\biodate


\end{document}






