    \documentclass[english]{jnlp_1.4}

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

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{braket}


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

\received{2016}{7}{12}
\revised{2016}{10}{11}
\rerevised{2016}{12}{20}
\accepted{2017}{1}{12}

\setcounter{page}{323}

\etitle{Extending Various Thesauri by Finding Synonym Sets \\from a Formal Concept Lattice}
\eauthor{Madori Ikeda\affiref{Author_1} \and Akihiro Yamamoto\affiref{Author_1}}
\eabstract{
In this paper, we solve the problem of extending various thesauri using a single method. Thesauri should be extended when unregistered terms are identified. Various thesauri are available, each of which is constructed according to a unique design principle. We formalise the extension of one thesaurus as a single classification problem in machine learning, with the goal of solving different classification problems. Applying existing classification methods to each thesaurus is time consuming, particularly if many thesauri must be extended. Thus, we propose a method to reduce the time required to extend multiple thesauri. In the proposed method, we first generate clusters of terms without the thesauri that are candidates for synonym sets based on formal concept analysis using the syntactic information of terms in a corpus. Reliable syntactic parsers are easy to use; thus, syntactic information is more available for many terms than semantic information. With syntactic information, for each thesaurus and for all unregistered terms, we can search candidate clusters quickly for a correct synonym set for fast classification. Experimental results demonstrate that the proposed method is faster than existing methods and classification accuracy is comparable.
}
\ekeywords{Thesaurus Extension, Multi-label Classification, Formal Concept Analysis}

\headauthor{Ikeda and Yamamoto}
\headtitle{Extending Various Thesauri by Using a Concept Lattice}

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


\begin{document}

\maketitle

\section{Introduction}
\label{sec:intro}

Problems associated with extending thesauri must be addressed to improve various types of natural language processing (NLP).
{\it Thesauri} are semantic dictionaries of terms in which similarity and other semantic relations among terms are given.
Thesauri are required for semantic processing of natural language documents.
They are used for fundamental tasks, such as paraphrasing \cite{6470907} and word sense disambiguation \cite{Navigli:2009:WSD:1459352.1459355}, as well as more challenging tasks, such as textual entailment recognition \cite{Rus:2005} and reputation analysis \cite{Peleja:2014:RAR:2600428.2609546}.
More challenging research tasks only succeed if thesauri suited to the target texts are available.
Whether a thesaurus is suitable for a text should be determined by its coverage of terms and its design principle.
An effective {\it thesaurus extension} method can improve the coverage without distorting the design principle.

Coverage refers to the extent to which a thesaurus contains sufficient terms.
Successful semantic processing requires a thesaurus that contains all (or nearly all) terms in the text.
Many studies have investigated thesaurus construction that ensure coverage requirements are satisfied.
Various types of thesauri are currently available.
For example, well-known English thesauri include {\it WordNet} \cite{Miller90wordnet:an},\footnote{Although {\it WordNet} is generally considered an ontology, it has all properties of a thesaurus.} {\it FrameNet} \cite{Baker:1998:BFP:980845.980860} and {\it Roget's Thesaurus}.\footnote{http://www.nzdl.org/ELKB/}
Popular Japanese thesauri include {\it Japanese WordNet} \cite{jwn}, the {\it Word List by Semantic Principles} ({\it Bunrui-Goihyo} in Japanese)\footnote{https://www.ninjal.ac.jp} and {\it EDR Electronic Dictionary},\footnote{https://www2.nict.go.jp/out-promotion/techtransfer/EDR/} and many other thesauri are available in many languages.
Historically, thesauri have been constructed and maintained manually.
However, methods to construct thesauri automatically have been proposed.
For example, Lin proposed clustering terms based on their syntactic information extracted from a corpus \cite{Lin:1998:ARC:980432.980696}.
Another thesaurus was constructed by extracting link co-occurrences from a semi-structured knowledge resource, i.e., {\it Wikipedia} \cite{Ito:2008:ATC:1458082.1458191}.
In addition, {\it BabelNet} \cite{NAVIGLI2012217}, which is a huge ontology, was constructed automatically by integrating previous thesauri and {\it Wikipedia}.
{\it BabelNet} can be considered a thesaurus in the sense that it groups terms with the same meaning.

However, no thesaurus has complete coverage because new terms appear frequently.
Thus, it is impossible for manually maintained thesauri to deal with all new terms, and automatically integrated thesauri cannot keep up with the appearance of new terms because they depend on manually constructed and maintained thesauri.
Although automatically constructed thesauri may be more comprehensive, they cannot possibly include all terms.
Therefore, we must supplement coverage of thesauri for effective NLP.

The design principle for a thesaurus must consider its fitness for processing text.
A natural language text requires a thesaurus whose principle fits the meanings of terms in the text to be processed because meaning can change relative to context.
For example, a thesaurus that outputs `privilege' or `claim' as a synonym of `right' is not appropriate for processing travel guidebooks.
Such a thesaurus may be appropriate for legal texts but it is not suitable for travel guidebooks.
Meaning changes depending on context; thus, there are both generic and context-specific thesauri.
However, no `one-size-fits-all' thesaurus exists.

Thesauri can be categorised based on their design principle.
The thesauri mentioned above are generic.
Generic thesauri consider a wide range of meanings for single terms, e.g., they define `privilege', `claim', `right-hand', `correct', and `proper' as a synonym of `right'.
Generic thesauri are applicable to various types of texts: however, semantic ambiguity must be considered when using generic thesauri to process text.
Other thesauri are constructed for specific domains and their design principles limit the range of term meanings.
For example, \textit{MeSH}\footnote{https://www.nlm.nih.gov/mesh/} is a thesaurus for biomedical documents, and the \textit{NASA Thesaurus}\footnote{https://www.sti.nasa.gov/sti-tools/} is for aerospace engineering and related scientific documents.
In addition, there is a web-based thesaurus for business and management terms.\footnote{http://www.businessballs.com/business-thesaurus.htm}
When the document domain is clear, domain specific thesauri are preferable because they can reduce term ambiguity more frequently than generic thesauri.

Consequently, to process natural language text successfully, we must select a thesaurus whose design principle corresponds to the given text and supplement its coverage.
{\it Thesaurus extension}, which is a process that adds unregistered terms to a thesaurus, is a good approach to solve the problem of coverage.
Some thesaurus extension methods have been proposed \cite{Cerbah00exogenousand,Rigutini:automaticterm,Takenobu97extendinga,Uramoto:1996:PUW:993268.993333}.
However, such methods do not consider the diversity of natural language texts.
In other words, these previous studies only a single thesaurus.
In practice, for NLP, many types of texts must be processed.
Thus, many different thesauri are used, and these thesauri should be extended for effective text processing.
We refer to extending various thesauri as {\it multi-thesaurus extension} to distinguish it from the previous thesaurus extension.
The first goal of our research is to construct a flexible extension method that can be applied to various thesauri.

In this paper, we formulate a simple thesaurus extension in a manner of machine learning.
Thus, it can be considered an instance of {\it multi-label classification}.
Multi-label classification is to predict one or more labels for each test data by using given training data, which are pre-labeled.
Generally, it is difficult to achieve high accuracy with such classification, and it is also time consuming.
Therefore, applying existing multi-label classification methods repeatedly for each thesaurus is not a good solution for our task.
Accordingly, the second goal of our research is to develop an extension method that is computationally inexpensive.

The proposed method is based on corpora that contain sentences and terms with syntactic structures.
If automatic or semi-automatic techniques are used to input data, the corpora would grow rapidly.
However, this is not true for thesauri that are constructed manually.
We focus on this point, i.e., whenever thesauri must be extended, corpora that contain appropriate data must be available.

We prepare clusters of terms from such a corpus by adopting {\it formal concept analysis} (FCA) \cite{Ganter:1999:FCA:550737}.
Each clusters is a candidate set of synonyms, and, to extend a thesaurus, we construct sets of synonyms from the candidates based on the given thesaurus' design principle.
Then, we extend the thesaurus by using the synonym sets that include both registered and unregistered terms.
The same set of clusters can be used for various thesauri and extension can be performed faster than previous multi-label classification methods.
Therefore, even if preparation requires significant time, the proposed approach reduces overall run time when the number of thesauri is large.

This remainder of this paper is organised as follows.
In Section~\ref{sec:problem_formalization}, we introduce mathematical definitions of thesauri and formalise multi-thesaurus extension.
In Section~\ref{sec:related_work}, we briefly introduce related work and FCA.
The proposed method is described in Section~\ref{sec:method}.
Experimental results are discussed in Section~\ref{sec:experiments} and conclusions are presented in Section~\ref{sec:conclusion}.


\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia1f1.eps}
\end{center}
\hangcaption{Synonym sets and thesaurus extension (sets, circles; mapping $f$, solid-line arrows; mapping $g$, white arrows; extended mapping $f'$, solid and dashed arrows)}
\label{fig:thesaurus}
\end{figure}

\section{Problem Formalisation}
\label{sec:problem_formalization}

Here, we model thesauri using mathematical set theory and provide definitions of related concepts.
A {\it thesaurus} ${\cal T}$ is formulated as a triplet $(R, L, f)$ of a set $R$ of {\it registered terms}, a set $L$ of {\it semantic labels}, and a function $f: R \to 2^L$.
A meaning of term $r \in R$ is represented by semantic label $l \in f(r)$.
If $|f(r)| > 1$, $r$ is {\it polysemous}.
Different terms $r$ and $r'$ can be regarded as {\it synonyms} if $f(r) \cap f(r') \not= \emptyset$.
For a label $l \in L$, a set of terms $g(l) = \{r \in R\, |\, l \in f(r)\}$ is refered to as a set of synonyms.
For example, in the popular {\it WordNet} thesaurus \cite{Miller90wordnet:an}, the noun `boy' has three semantic labels; $f($`boy'$) = \{l_1, l_2, l_3\}$.
In Fig.~\ref{fig:thesaurus}, function $f$ is indicated by black arrows.
Here, label $l_1$ indicates that the noun is a synonym of the noun term `male child' given the synonym set $g(l_1) = \{$boy, male child$\}$, label $l_2$ indicates that `boy' is also a synonym of `son', i.e., $g(l_2) = \{$boy, son$\}$ and label $l_3$ yields a singleton $g(l_3) = \{$boy$\}$.
Note that all terms are restricted to {\it nouns} in this paper.

In practice, a thesaurus is constructed according to a specific {\it design principle}, and its label set $L$ and function $f$ are designed according to this principle.
Thesauri treat synonymy and other types of semantic relations, e.g., antonymy, hyponymy and hypernymy.
Such relations would require complicated definitions; however, we avoid such complexity and consider only synonymy, which is directory related to out research goals.

An example of incompleteness in a thesaurus is as follows.
{\it WordNet} does not list the slang term `boi', which is an alternative spelling of the registered term `boy'.\footnote{The Online Slang Dictionary http://onlineslangdictionary.com}
In {\it WordNet}, the term `boi' is {\it unregistered}.
For each thesaurus ${\cal T} = (R, L, f)$, let $U$ be a set of {\it unregistered terms} and assume that $R \cap U = \emptyset$ (clearly, $L \cap U = \emptyset$).
{\it Thesaurus extension} is to extend $R$ to $R' = R \cup U$, $f: R \to 2^L$ to $f': R \cup U \to 2^L$, and $g$ to $g'(l) = \{r \in R'\, |\, l \in f'(r)\}$.
Extension could be interpreted as conjecturing the design principle of the target thesaurus.
The extension is correct if the extended function $f'$ conforms to the design principle of ${\cal T}$.
With {\it WordNet}, a function $f'$ that is correctly extended from $f$ must assign the same set of labels to `boi' as `boy', because `boi' is an alternative spelling (Fig.~\ref{fig:thesaurus}).

In this paper, we consider the problem of {\it extending various thesauri}, i.e., to obtain extensions for all given thesauri ${\cal T}_1 = (R_1, L_1, f_1)$, ${\cal T}_2 = (R_2, L_2, f_2)$, ..., and ${\cal T}_n = (R_n, L_n, f_n)$.
As mentioned previously, we refer to this problem as {\it multi-thesaurus extension} to distinguish it from single-thesaurus extension.
In our problem, assume that the registered term sets $R_1$, $R_2$, ..., and $R_n$ differ.
Moreover, the label sets $L_1$, $L_2$, ..., and $L_n$ and functions $f_1$, $f_2$, ..., and $f_n$ also differ.
We also assume that the design principles differ.
For example, the {\it FrameNet} thesaurus \cite{Baker:1998:BFP:980845.980860} which also registers `boy' but not `boi' lists the registered term as a member of quite different synonym sets from those in {\it WordNet}.
{\it FrameNet} lists `boy' as a member of $\{$boy, bro, buddy, dude, guy, homes, kid, ma'am, miss, officer, pal, sir$\}$, and of $\{$adolescent, adult, baby, child, coot, elderly, geezer, infant, kid, neonate, newborn, spring chicken, teenager, youngster, youth$\}$.
Furthermore, assume that unregistered term sets $U_1$, $U_2$, ..., and $U_n$ for each thesauri ${\cal T}_1$, ${\cal T}_2$, ..., and ${\cal T}_n$ also differ.
Therefore, correct extensions for given thesauri differ, and an appropriate extension for a given thesaurus may not be a help to extension of another thesaurus.


\section{Related Work}
\label{sec:related_work}

In this section, we discuss previous studies into single-thesaurus extension.
Note that, to the best of out knowledge, multi-thesaurus extension has not been considered previously.
We then introduce FCA which is the core technique of the proposed solution to the problems of multi-thesaurus extension.


\subsection{Single-thesaurus Extension Methods}

Two approaches can be considered for single-thesaurus extension.
One approach uses semantic information in another resource, and the other approach uses syntactic or contextual information.
Note that some similarity among terms is introduced in both approaches.

The first approach assumes another data resource, such as a dictionary, that provides some meaning for each term.
This meaning does not lead to correct labels for unregistered terms; however, it can provide clues that can be used to evaluate semantic similarity among terms.
For example, {\it Wikipedia} states `a boy is a young male human', which indicates that the term `boy' must be a synonym of term `young male human'.
If a given thesaurus registers `boy' but not `young male human', then we can add `young male human' as a synonym of `boy'.
If a given resource provides more explicit semantic similarity, then extending the thesaurus would be easier.
However, we do not follow this approach because, as mentioned in the previous section, the design principle of a target thesaurus could differ significantly from the referenced resources.
In addition, we cannot assume that such resources contain all registered terms in and many unregistered terms in the target thesaurus because reliable semantic resources are generally constructed manually.

The second approach has been verified in some studies.
Cerbah et al. reported that contextual information is more effective than semantic information from other resources for thesaurus extension \cite{Cerbah00exogenousand}.
Multi-word terms often appear in some domains, e.g., aeronautics.
In this case, Cerbah et al. used semantic labels for the individual terms to categorise multi-word terms.
In addition, they also used contextual information for the same task for comparison.
Their experimental results showed that the semantic information is less useful than the contextual information.
Uramoto proposed using {\it predicate-argument structure}, which captures the syntactic relations among a predicate term and other terms in a sentence, in cases where limiting the scope of meanings of unregistered terms is difficult, such as thesaurus extension \cite{Uramoto:1996:PUW:993268.993333}.
Uramoto used this structure to estimate semantic similarity between two terms.
For example, from the sentences `An airplane flies.' and `A helicopter flies.', he constructed two triplets (airplane, is, to fly) and (helicopter, is, to fly) that can be easily transformed to the predicate-argument structure of the sentences.
Then, he assumed that `airplane' and `helicopter' are synonyms from the perspective that they are both fling object.
This triplet can be considered an alternative {\it IS-A} relationship obtained from the syntactic information.
He limited the variation of the middle parameter, which is called a marker, and gathered such triplets from newspaper articles.
Then, terms having relationships with the same predicates via the same markers were considered synonyms.
He reported that this method is reasonably effective; however, it did not yield high accuracy for terms that appear frequently in corpora because the wide variation in the predicate-argument structures of frequent terms is not useful for semantic categorisation.
Tokunaga et al. restricted the variation of the predicate-argument structure based on Japanese linguistic heuristics \cite{Takenobu97extendinga}.
They used the restricted structure as attributes of terms and applied $k$-NN classification to estimate similarity among Japanese terms.

We also use the predicate-argument structure to infer similarity.
However, the proposed method differs from previously proposed methods.
Uramoto constructed triplets from the predicate-argument structure and limited the middle parameter (i.e., the marker) without clearly explaining why this limitation is required.
We extract information in a similar manner, i.e., we extract a triplet from the predicate-argument structure.
However, we do not limit the variations.
Rather than limiting predicate-argument structures, we introduce a mechanism to select the predicate-argument structure using FCA.
We only use the predicate-argument structure to cluster registered and unregistered terms, i.e., we do not use semantic information from auxiliary resources.
Moreover, we represent the design principle of each thesaurus in a uniform manner without introducing additional factors.
Tokunagara et al. employed heuristics to restrict the predicate-argument structure.
The restriction should be proved to be appropriate, but has not been yet.
Moreover, this restriction cannot be applied to languages other than Japanese.
In the proposed method, appropriate predicate-argument structures are selected automatically using FCA, and are therefore applicable to various languages.
In addition, by using FCA, we do not need to fix parameters, such as $k$ for the $k$-NN method.
Generally, FCA has large time complexity when applied to dense data but is known to work efficiently with sparse data, such as syntactic data.
Therefore, the proposed method works efficiently even though FCA is time-consuming.


\subsection{Formal Concept Analysis for a Syntactic Corpus}
\label{sec:FCA}

The key idea of our solution is the application of FCA to {\it syntactic corpora} containing predicate-argument structure to cluster terms.
Various techniques to analyse relational data based on FCA have been proposed.
In our previous work \cite{Ikeda14:ALSIP14}, we demonstrated that such techniques are useful for clustering sparse data.
Because we consider multi-thesaurus extension an instance of multi-label classification and because natural language data are sparse, FCA can be applied to solve the target problem.
In this section, we introduce FCA as applied to a syntactic corpus.
Definitions for FCA accord to \cite{Ganter:1999:FCA:550737}.

\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia1f2.eps}
\end{center}
\hangcaption{Sentence with syntactic structure and attributes for the noun `boys'. Tags on terms represent their POS. Arcs represent syntactic relations among terms with tags representing their types (relation tags). Here, three sets of parts of the structure are obtained as the attributes of `boy'.}
\label{fig:parsing}
\end{figure}

Before introducing FCA, let us assume a syntactic corpus that contains sentences with their syntactic structure.
We separate the data into noun terms and their {\it predicate-argument structure} \cite{Marcus:1994:PTA:1075812.1075835,Taira:2008:JPA:1613715.1613780}, which can be transformed from the syntactic structure.
For example, Fig.~\ref{fig:parsing} shows a sentence with its syntactic structure.
The predicate-argument structure can be obtained by transforming the syntactic structure.
Generally, a part of the predicate-argument structure is defined for a predicate term.
Here, for the verb term `eating' the noun term `boys' could be selected as its subject and the term `hamburgers' as its object.
We move the centre of the structure from predicates to nouns, and then pick up `the', `eating hamburgers', and `are my friends' for the structure of the noun `boys'.
From these parts, we generate three sets of triplets for `boys', i.e., $\{$(the, DT, det)$\}$, $\{$(eating, VBG, partmod), (hamburgers, NNS, dobj)$\}$ and $\{$(are, VBP, cop), (my, PRP\$, poss), (friends, NNS, nsubj)$\}$.
Although the sets of triplets are syntactic, they indicate the meaning of `boys' indirectly.
In other words, the thing called `boys' could `eat hamburgers' and could be `my friends'.
This is why we use predicate-argument structure for the semantic classification of nouns.
More formally, such triplets for a noun term are generated as follows: trace each relation from the noun to its end, generate a set of terms found in each trace, and transform each term into a triplet in the form (term, POS tag, relation tag).
Note that the direction of the relations is ignored in each trace.
Similarly, from the same sentence, we obtain other triplets for the nouns `hamburgers' and `friends'.

Here, we introduce FCA as applied to the syntactic corpus.
Let $O$ be the set of all noun terms in the corpus and let $A$ be the set of all sets of triplets generated from the predicate-argument structure.
In FCA terminology, terms in $O$ are called {\it objects} and the triplet sets in $A$ are called {\it attributes}.
In FCA, data resources are first treated in the form of a {\it formal context}, which is mathematically defined as a triplet $K = (O, A, I)$ where $I \subseteq O \times A$ is a {\it binary relation}.
In this study, context $K$ is constructed from a given corpus and the relation $I$ represents the predicate-argument structure of each term found in the corpus.
Table~\ref{table:context} shows a context used in the running example in this paper.
Note that, for simplification, we refer to each attribute using a core predicate term in itself.
In Table~\ref{table:context}, the attribute $\{$(eating, VBG, partmod), (hamburgers, NNS, dobj)$\}$ of the noun term `boy', which is extracted from the sentence shown in Fig.~\ref{fig:parsing}, is denoted by the core predicate `eat'.

In FCA, {\it formal concepts} are defined for a context.
A concept is a pair $(X, Y)$ of subsets $X \subseteq O$ and $Y \subseteq A$ of context $K$ satisfying
\[
X = \set{o \in O | \forall a \in Y.\, (o, a) \in I} \text{ and } Y = \set{a \in A | \forall o \in X.\, (o, a) \in I}.
\]
For a concept $c = (X, Y)$, $X$ is refered to as the {\it extent} (denoted ${\rm Ex}(c)$) and $Y$ is the {\it intent} (denoted ${\rm In}(c)$).
For arbitrary concepts $c$ and $c'$, there is an order $c \le c'$ if and only if ${\rm Ex}(c) \subseteq {\rm Ex}(c')$; ${\rm In}(c) \supseteq {\rm In}(c')$ equivalently.
A {\it concept lattice} of context $K$ is a set of its concepts with order $\le$ (denoted $\underline{\mathfrak B}(K)$).
The lattice form is frequently used in FCA.
The lattice $\underline{\mathfrak B}(K)$ of context $K$ in Table~\ref{table:context} is shown in Fig.~\ref{fig:lattice}.
For example, $c_4 = ( \{$ cat, baby, girl $\}$, $\{$ cry, play $\} )$ and $c_7 = ( \{$ baby, girl $\} , \{$ cry, play, sing $\})$ in Fig.~\ref{fig:lattice} are formal concepts, and an order $c_7 \le c_4$ exists between them because $\{$ baby, girl $\} \subseteq \{$ cat, baby, girl $\}$ ( $\{$ cry, play, sing $\} \supseteq \{$ cry, play $\}$).

\begin{table}[t]
\caption{Context $K = (O, A, I)$}
\label{table:context}
\input{01table01.txt}
\end{table}
\begin{figure}[t]
\begin{center}
\includegraphics{24-3ia1f3.eps}
\end{center}
\hangcaption{Concept lattice $\underline{\mathfrak B}(K)$. Each circle represents a formal concept $c \in \underline{\mathfrak B}(K)$ with ${\rm Ex}(c)$ and ${\rm In}(c)$. The {\it scores} numbers beside concepts are explained in Section~\ref{sec:method}. Each edge represents an order $\le$ between two concepts, and the greater concept is drawn above. Transitional orders are omitted.}
\label{fig:lattice}
\end{figure}

As shown in Fig.~\ref{fig:lattice}, the extent of a concept is a cluster of terms; thus, we sometimes refer to the extent of a concept $c$ as a cluster $c$.
Then, if we consider the construction of lattice $\underline{\mathfrak B}(K)$ as clustering of terms in $O$, we can also consider each cluster $c$ as a set of the nearest neighbors of the terms in the cluster in feature space of the intent ${\rm In}(c)$.\footnote{We call this property {\it local feature selection} and introduced in our previous work \cite{Ikeda14:ALSIP14}.}
For example, the terms in cluster $c_6$ `boi', `boy', and `kid' are the nearest terms to each other in the feature space based on the attributes `play' and `eat' (Table~\ref{table:context}).
When Hamming distance is applied to the space, each distance among the terms is $0$, `cat', `baby' and `girl' are at a distance of $1$ from them and `robot' is at a distance of $2$.\footnote{A set of terms `cat', `baby', and `girl' is another set of nearest neighbors.}
This means that the terms `boi', `boy' and `kid' are similar relative to whether they `play something' and `eat hamburgers'.
This idea is important when we extend a thesaurus by registering the unregistered term `boi'.
If the design principle of a thesaurus relates to this idea, a set of nearest neighbors could be considered a set of synonyms.


\section{Extending Various Thesauri with a Concept Lattice}
\label{sec:method}

Here, we obtain a solution to the problem of multi-thesaurus extension using the following steps:
\begin{itemize}
\item clustering terms in $O$ of a given syntactic corpus by applying FCA and
\item extending each of the given thesauri ${\cal T}_1$, ${\cal T}_2$, ..., and ${\cal T}_n$ using the clusters.
\end{itemize}
These steps are shown in Fig.~\ref{fig:flow-multi}.
The clustering step constructs a single concept lattice $\underline{\mathfrak B}(K)$ by FCA, as explained in the previous section.
This is performed to prepare for the extending step.
Note that clustering is performed independent of the thesauri to be extended.
This independence is the key to reducing the total time required to extend all thesauri because, once the lattice is constructed, each thesaurus can be extended in the extending step, which uses the same lattice and is faster than the preparation step.
On the other hand, if we repeatedly apply a classification method to each thesaurus, e.g., the approach shown in Fig.~\ref{fig:flow-single}, the total time is simply multiplied by the number of given thesauri.
Moreover, many existing methods require time for feature selection or parameter tuning for each thesaurus.
This is roughly illustrated in Fig.~\ref{fig:time-idea}.
In addition, if we have already stored the corpus in lattice form, the time required for clustering can be ignored.

\begin{figure}[b]
\noindent\begin{minipage}[b]{242pt}
\setlength{\captionwidth}{242pt}
\mbox{\raisebox{-43pt}{\includegraphics{24-3ia1f4.eps}}}
\hangcaption{Flow of the proposed multi-thesaurus extension method{\vrule depth13pt width0pt}}
\label{fig:flow-multi}
\end{minipage}
\hfill
\begin{minipage}[b]{149pt}
\setlength{\captionwidth}{149pt}
\begin{center}
\includegraphics{24-3ia1f5.eps}
\end{center}
\hangcaption{Flow of simple extension repetition for multi-thesaurus extension}
\label{fig:flow-single}
\end{minipage}
\end{figure}

In the extending step, thesauri ${\cal T}_1$, ${\cal T}_2$, ..., and ${\cal T}_n$ are extended one by one.
Extension of each thesaurus ${\cal T}_i (i = 1, 2, ..., n)$ is achieved using the same lattice $\underline{\mathfrak B}(K)$.
Each thesaurus ${\cal T}_i = (R_i, L_i, f_i)$ is extended to ${\cal T}_i' = (R_i \cup O, L_i, f_i')$; thus, the set $U_i$ of unregistered terms of ${\cal T}_i$ is $O \setminus R_i$.
This extension is achieved by searching and registering every unregistered term $u \in U_i$.
The search is to find a synonym set that contains $u$ and other registered terms corresponding to the design principle of thesaurus ${\cal T}_i$.
The registration of $u$ is performed by referencing the labels of synonyms registered in the synonym set.
Note that, in each extension of ${\cal T}_i$, the method only uses $R_i$, $L_i$ and $f_i$ (technically, using only $f_i$ is sufficient).
The method does not require any other information from ${\cal T}_i$, e.g., semantic relations among synonym sets, definition text of synonym sets, etc.
This means that the proposed method is applicable to all thesauri that can be represented in the simple form of ${\cal T}_i$.

\begin{figure}[t]
\begin{center}
\includegraphics{24-3ia1f6.eps}
\end{center}
\caption{Key idea to reduce total time for multi-thesaurus extension}
\label{fig:time-idea}
\end{figure}
\begin{table}[t]
\hangcaption{Thesaurus ${\cal T}_i = (R_i, L_i, f_i)$ where $R_i = \{$cat, baby, girl, boy, kid, robot$\}$ and $L_i = \{l_1, l_2, l_3, l_4, l_5, l_6, l_7, l_8\}$}
\label{table:thesaurus}
\input{01table02.txt}
\end{table}

In this section, we explain the search and registration by adding `boi' to thesaurus ${\cal T}_i$ shown in Table~\ref{table:thesaurus}.
Here, thesaurus ${\cal T}_i$ already contains all terms in the context $K$ (Table~\ref{table:context}) except `boi'.


\subsection{Searching a Concept Lattice for Synonym Sets}

As mentioned in Section~\ref{sec:FCA}, each cluster $c \in \underline{\mathfrak B}(K)$ has the potential to be a set of synonyms corresponding to the design principle of thesaurus ${\cal T}_i$.
Therefore, to register the unregistered term `boi' to ${\cal T}_i$, we search lattice $\underline{\mathfrak B}(K)$ for clusters that form a synonym set ${\rm Syn}($boi$, {\cal T}_i) \subseteq R_i$ corresponding to the design principle of ${\cal T}_i$.
We construct ${\rm Syn}($boi$, {\cal T}_i)$ by combining the obtained clusters.

To obtain synonym set ${\rm Syn}(u, {\cal T}_i)$ of an unregistered term $u$, we assign a {\it score} to each concept $c \in \underline{\mathfrak B}(K)$, and a concept with a higher score is closer to one of the synonym sets under the principle of ${\cal T}_i$.
Then, we find the formal concepts $c \in \underline{\mathfrak B}(K)$ with the highest score satisfying $u \in {\rm Ex}(c)$.
In other words, $c$ is a cluster containing the unregistered term $u$ and registered terms that would be synonyms of $u$.
\pagebreak
The score is defined as follows:
\[
{\rm score}(c, {\cal T}_i) =
\begin{cases}
0 & \text{if ${\rm Ex}(c) \cap R_i = \emptyset$,}\\
1 & \text{if ${\rm Ex}(c) \cap R_i$ is a singleton, and}\\
\dfrac{\sum_{(o, o') \in {\rm Cmb}({\rm Ex}(c) \cap R_i)} {\rm jac}(f_i(o), f_i(o'))}{|{\rm Cmb}({\rm Ex}(c) \cap R_i)|} & \text{otherwise,}\\
\end{cases}
\]
where ${\rm Cmb}({\rm Ex}(c) \cap R_i)$ is the set of all combinations of two distinct elements in ${\rm Ex}(c) \cap R_i$ and ${\rm jac}(A, B) = \frac{|A \cap B|}{|A \cup B|}$ is the {\it Jaccard index} of two sets $A$ and $B$ \cite{Agirre00enrichingvery}, which was proposed to compare the similarity of two sets.

Here, $f_i(o)$ is the set of semantic labels of a registered term $o$ of ${\cal T}_i$ and the Jaccard index ${\rm jac}(f_i(o), f_i(o'))$ represents how similar the meanings of $o$ and $o'$ are.
If the meaning of $o$ coincides with the meaning of $o'$, $f_i(o) = f_i(o')$ and ${\rm jac}(f_i(o), f_i(o')) = 1$.
If the meaning of $o$ and the meaning of $o'$ are not the same, $f_i(o) \not= f_i(o')$ but $f_i(o) \cap f_i(o') \not= \emptyset$; thus, $0 \le {\rm jac}(f_i(o), f_i(o')) \le 1$.
For example, in the given thesaurus ${\cal T}_i$, $f_i($boy$) =\{l_1, l_6, l_7\}$ and $f_i($kid$) =\{l_6, l_7\}$; thus $f_i($boy$) \not= f_i($kid$)$, $f_i($boy$) \cap f_i($kid$) \not= \emptyset$ and $0 \le {\rm jac}(f_i($boy$), f_i($kid$)) \le 1$.
Considering the term `girl', $f_i($girl$) =\{l_4, l_5, l_6\}$ and ${\rm jac}(f_i($boy$), f_i($girl$)) < {\rm jac}(f_i($boy$), f_i($kid$))$.
This means that `girl' is farther from `boy' than `kid'.
Note that label $l_6$ is shared by all terms.
This means that the three terms have the same meaning in a situation where they are used for the label, which would mean `student-age people'.
Therefore, we can consider ${\rm jac}(f_i(o), f_i(o'))$ as the semantic similarity between terms $o$ and $o'$ in thesaurus ${\cal T}_i$.
The sum $\sum_{(o, o') \in {\rm Cmb}({\rm Ex}(c) \cap R_i)} {\rm jac}(f_i(o), f_i(o'))$ is normalised by division with $|{\rm Cmb}({\rm Ex}(c) \cap R_i)|$.
Then, we can consider ${\rm score}(c, {\cal T}_i)$ as the average semantic similarity between any pair of registered terms in ${\cal T}_i$ contained in cluster $c$.
In Fig.~\ref{fig:lattice}, the scores are shown beside concepts.

As mentioned previously, a formal concept $c$ consists of ${\rm Ex}(c)$ and ${\rm In}(c)$.
In our context, ${\rm Ex}(c)$ is a set of registered and unregistered terms, and ${\rm In}(c)$ is a set of parts of the predicate-argument structure.
The parts of the predicate-argument structure could be an indirect representation of term meanings.
Therefore, ${\rm Ex}(c)$ can be considered a set of synonyms if we assume that the parts in ${\rm In}(c)$ are provisional semantic labels that correspond to an imaginary design principle.
If the imaginary design principle is similar to the design principle of ${\cal T}_i$, each unregistered term in ${\rm Ex}(c)$ could be considered the same as terms registered in ${\rm Ex}(c)$.
For an unregistered term $u$, FCA generates several sets ${\rm Ex}(c)$ of synonyms such that $u \in {\rm Ex}(c)$, and each synonym set corresponds to its own imaginary design principle.
Such sets of different synonyms candidates for the set of synonyms corresponding to the principle of ${\cal T}_i$.
Therefore, we must select the most appropriate principle and its synonym set ${\rm Ex}(c)$ to register $u$ to ${\cal T}_i$.
Roughly, the function ${\rm score}(c, {\cal T}_i)$ evaluates similarity between the imaginary principle for ${\rm Ex}(c)$ and the principle of ${\cal T}_i$.
For example, we obtain five candidate sets of synonyms ${\rm Ex}(c_1)$, ${\rm Ex}(c_2)$, ${\rm Ex}(c_5)$, ${\rm Ex}(c_6)$ and ${\rm Ex}(c_8)$ for the unregistered term `boi' (Fig.~\ref{fig:lattice}), and they correspond to their own imaginary principles.
In this case, the scores show that the principle of ${\rm Ex}(c_6)$ is most similar to the principle of ${\cal T}_i$.
Then, ${\rm Ex}(c_6) = \{$boi, boy, kid$\}$ can be considered the set of synonyms of ${\cal T}_i$.

Now, let ${\rm Sel}(u, {\cal T}_i)$ be the set of clusters with the highest score.
Then, the synonym set ${\rm Syn}(u, {\cal T}_i)$ is expressed as follows:
\[
{\rm Syn}(u, {\cal T}_i) = \bigcup_{c \in {\rm Sel}(u, {\cal T}_i)}{\rm Ex}(c) \cap R_i.
\]
This is a realisation of the {\it false-negative policy}, and we only use clusters with the highest score to construct the set of synonyms.
Note that, when some clusters share the highest score, they are treated equally and combined into the synonym set.
In this study, registered terms in the synonym set are equally similar to the unregistered term according to the design principle of ${\cal T}_i$.
In the example, only cluster $c_6$ has the highest score among the candidates, and the set of synonyms of the unregistered term `boi' is ${\rm Syn}($boi$, {\cal T}_i) = \{$boy, kid$\}$.


\subsection{Registering Unregistered Terms into Thesauri}

The unregistered term $u$ is added to the registered term set $R_i$, and the target thesaurus ${\cal T}_i = (R_i, L_i, f_i)$ is extended to ${\cal T}_i' = (R_i \cup O, L_i, f_i')$, where:
\[
f_i'(o) = 
\begin{cases}
\bigcup_{o' \in {\rm Syn}(o, {\cal T}_i)} f(o') & \text{if $o$ is an unregistered term of ${\cal T}_i$,}\\
f_i(o) & \text{otherwise.}\\
\end{cases}
\]
In this example, the unregistered term `boi' is registered to ${\cal T}_i$ with the given predicted labels $f'($boi$) = \{l_1, l_6, l_7\}$ because ${\rm Syn}($boi$, {\cal T}_i) = \{$boy, kid$\}$.

Although the search follows the false-negative policy, registration take the {\it false-positive policy}.
Thus, the proposed approach provides a reasonable trade-off between precision and recall, which is why we do not introduce a threshold parameter to the score or the number of predicted labels $|f'(u)|$ for an unregistered term $u$.
It might be easy to introduce such a threshold, and this may not affect the computational efficiency of clustering.
However, the threshold value should be independent of the thesaurus extension purpose.
If the value is small, term $u$ would be very restrictive semantically.
If the value is large, it would be polysemous.
Thus, the number represents the variation of the single term $u$.
This variation should not be related to the treatment of unregistered terms.

Here, we consider the extension of a thesaurus ${\cal T}_i = (R_i, L_i, f_i)$ with context $K = (O, A, I)$ as a multi-label classification problem.
In terms of classification, pairs of attributes and labels $(\set{a \in A | (r, a) \in I}, f_i(r))$ for each registered term $r \in R_i$ are training data and unregistered terms in $U_i = O \setminus R_i$ are test data.
Therefore, this is a multi-label classification method, which we refer to as the {\it concept lattice classifier} (CLC) method.


\section{Experiment with Well-known Materials in NLP}
\label{sec:experiments}

We evaluated the proposed CLC method by performing experiments with thesauri and corpora commonly used in NLP.
In the experiments, we applied the proposed method and four existing classification methods to two types of multi-thesaurus extension, and we compared their accuracy and run times.
First, we explain the two extension tasks, the major methods, and the experimental environment.
Then, we detail and discuss the experimental results in Section~\ref{sec:result}.


\subsection{Experimental Settings}
\label{subsec:setting}

We prepared thesauri ${\cal T}_{\rm EW}$, ${\cal T}_{\rm EF}$, ${\cal T}_{\rm JW}$ and ${\cal T}_{\rm JB}$ as materials.
For each $i = {\rm EW}, {\rm EF}, {\rm JW}$ and ${\rm JB}$, ${\cal T}_i$ is generated from a true thesaurus ${\cal T}^*_i$ to evaluate the accuracy of the extension tasks.
The first task is to extend two English thesauri ${\cal T}_{\rm EW} = (R_{\rm EW}, L_{\rm EW}, f_{\rm EW})$ and ${\cal T}_{\rm EF} = (R_{\rm EF}, L_{\rm EF}, f_{\rm EF})$ using an English corpus used to generate a context $K_{\rm E} = (O_{\rm E}, A_{\rm E}, I_{\rm E})$.
The other task is to extend two Japanese thesauri ${\cal T}_{\rm JW} = (R_{\rm JW}, L_{\rm JW}, f_{\rm JW})$ and ${\cal T}_{\rm JB} = (R_{\rm JB}, L_{\rm JB}, f_{\rm JB})$ with a Japanese corpus used to generate a context $K_{\rm J} = (O_{\rm J}, A_{\rm J}, I_{\rm J})$.
Note that the materials satisfy $R^*_{\rm EW}, R^*_{\rm EF} \subseteq O_{\rm E}$ and $R^*_{\rm JW}, R^*_{\rm JB} \subseteq O_{\rm J}$.
More precisely, the tasks are to extend ${\cal T}_i = (R_i, L_i, f_i)$ to ${\cal T}'_i = (R^*_i, L_i, f'_i)$ such that $f'_i(r) \approx f^*_i(r)$ for all $r \in R^*_i$.
This differs from the formalisation given in Section~\ref{sec:problem_formalization}.
However, this difference does not affect the conclusions derived from our comparisons.
Moreover, we vary the ratio of registered terms in each extension from 0.1 to 1.0 (increment of 0.1) while maintaining the number of unregistered terms.
Equivalently, we vary the number of training data for each classification problem.
Statistics for the materials are shown in Tables~\ref{table:tripletstatistics} and \ref{table:contextstatistics}, and details about their generation are discussed in Section~\ref{subsec:resourceinexp}.

For multi-thesaurus extension, we apply the CLC method and the following four methods.
\begin{itemize}
\item $k$-neighbors classifier ($k$-NC) \cite{knn} with a ball tree structure and Manhattan distance executed for $k = 1, 5$ and $10$.
\item Support vector machine classifier (SVC) \cite{Guyon93automaticcapacity} with a linear kernel that uses squared hinge loss and the $L^2$ norm with $C = 1.0$ for penalisation.
\item Multinomial na\"ive Bayes classifier (MNB) \cite{Kibriya:2004:MNB:2146834.2146882}, where the smoothing parameter value is set to 1.0.
\item Random forest classifier (RFC) \cite{DBLP:journals/ml/Breiman01} with entropy as the criterion.
\end{itemize}
All methods, including the proposed method, were implemented in Python 2.7.5, and the four existing methods were provided by Scikit-learn 0.17,\footnote{Scikit-learn http://scikit-learn.org} which is a machine learning package for Python.
Note that these methods were originally binary or multi-class classifiers that were expanded to multi-label classification problems in a one vs. the rest manner \cite{eb}.\footnote{SVC and MNB are expanded by the one vs. rest meta-classifier class provided by Scikit-learn, and the others are applicable to multi-label classification problems as is.}

\begin{table}[t]
\caption{Statistics for thesaurus triplets}
\label{table:tripletstatistics}
\input{01table03.txt}
\end{table}
\begin{table}[t]
\caption{Statistics for contexts and their lattices}
\label{table:contextstatistics}
\input{01table04.txt}
\end{table}

One vs. the rest is a popular technique that uses a binary classifier for multi-class and multi-label classification tasks \cite{Zhang:2007,Liu:2005,Ramage:2009:LLS:1699510.1699543,doi:10.1080/01431160412331269698}.
The multi-class classification task is to classify each object $o \in O$ into a single class from a given set of $L$ class labels.
For multi-class classification task, we prepare $|L|$ classifiers, each of which is related to each class label $l \in L$.
For each object $o \in O$, the classifier of $l$ is assumed to evaluate the likelihood that $o$ belongs to $l$ rather than any other class in $L$.
Then, classification is solved by assigning each object $o \in O$ to such $l \in L$ that the likelihood is the maximum.
Multi-label classification assigns some labels in $L$ to each object $o \in O$.
For classification, a threshold is introduced, and each object $o$ is assigned labels $l \in L$ when the likelihoods of $o$ and $l$ are greater than the threshold.
In our experiments, the likelihood in the SVC is the distance between object $o$ and the boundary of class $l$, and the threshold in SVC is 0.0.
For other classifiers, the likelihood is the probability of the case that $o$ is in $l$, and the threshold is 0.5.

As other solutions to multi-label classification problems, neural network models and deep learning approaches have been proposed.
However, such classification methods can require a long time for initial parameter tuning to achieve better performance for a single classification task.
Therefore, we consider such methods unsuitable for multi-thesaurus extension and do not assess them in our comparison.

When a method does not complete extension in three hours, its execution is stopped.
Note that each applied method uses contexts $K_{\rm E}$ and $K_{\rm J}$.
Precisely, only the CLC method uses context lattices $\underline{\mathfrak B}(K_{\rm E})$ and $\underline{\mathfrak B}(K_{\rm J})$ which are constructed from the contexts.
The times required to construct each lattice are shown in Table \ref{table:contextstatistics}.\footnote{In lattice construction, the proposed method partially uses another method called the Linear-time Closed Itemset Miner \cite{Uno05lcmver}.}

The experiment was performed using the following environment.
\begin{itemize}
\item CPU: Intel(R) Xeon(R) CPU E5-2676 v3 @ 2.40~GHz
\item OS: Ubuntu 14.04.3 LTS 64-bit
\item RAM: 160~GB
\end{itemize}


\subsection{Generating Thesauri and Contexts from Original Resources}
\label{subsec:resourceinexp}

Each thesaurus ${\cal T}_i = (R_i, L_i, f_i)$ $(i = {\rm EW}, {\rm EF}, {\rm JW}, {\rm JB})$ to be extended was generated from its true thesaurus ${\cal T}^*_i = (R^*_i, L^*_i, f^*_i)$ with 10\% shrinkage.
Here, ${\cal T}_i$ satisfies $R_i \subseteq R^*_i$, $|R_i| = |R^*_i| \times 0.9$, $L_i = \bigcup_{r \in R_i} f^*_i(r)$ and $f_i(r) = f^*_i(r)$ for only $r \in R_i$.
Note that the generation method does not guarantee that $\forall r \in R^*_i.\, f^*_i(r) \subseteq L_i$ for ${\cal T}_i$ and ${\cal T}^*_i$; therefore, no classification method can extend ${\cal T}_i$ to ${\cal T}^*_i$ perfectly.
Here, we explain how we generate each true thesaurus from the original resources.
In addition, we describe how we generate contexts from their original resources.

One of the true English thesauri ${\cal T}^*_{\rm EW}$ was generated from {\it WordNet} \cite{Miller90wordnet:an}.
We use its NLTK version\footnote{Natural Language Toolkit of Python http://www.nltk.org} in which each term is represented as a {\it lemma} component and each synonym set is represented as a {\it synset} component.
For ${\cal T}^*_{\rm EW} = (R^*_{\rm EW}, L^*_{\rm EW}, f^*_{\rm EW})$, $R^*_{\rm EW}$ is formed as a set of lemmata and $L^*_{\rm EW}$ is a set of synsets.
Here, $f^*_{\rm EW}$ is constructed based on the relation between the lemmata and synsets.

The other true English thesaurus ${\cal T}^*_{\rm EF}$ was generated using {\it FrameNet} \cite{Baker:1998:BFP:980845.980860}.
It is also provided by NLTK in which terms are represented as {\it lexical units} and synonym sets are represented as {\it lexical frames}.
For ${\cal T}^*_{\rm EF} = (R^*_{\rm EF}, L^*_{\rm EF}, f^*_{\rm EF})$, $R^*_{\rm EF}$ is formed as a set of lexical units and $L^*_{\rm EF}$ is a set of lexical frames.
Here, $f^*_{\rm EF}$ is constructed based on the relation between lexical units and lexical frames.

The true Japanese thesaurus ${\cal T}^*_{\rm JW}$ was generated from {\it Japanese WordNet} \cite{jwn}.
Note that we used its XML version, where treatment of terms and synonym sets is similar to that of {\it WordNet}, i.e., {\it Japanese WordNet} also represents terms and synonym sets as lemmata and synsets, respectively.
Therefore, we form ${\cal T}^*_{\rm JW}$ in the same manner as ${\cal T}^*_{\rm EW}$.

The other true Japanese thesaurus ${\cal T}^*_{\rm JB}$ was generated from the {\it Word List by Semantic Principles} ({\it Bunrui-Goihyo} in Japanese),\footnote{Word List by Semantic Principles (Bunrui-Goihyo), National Institute for Japanese Language and Linguistics https://www.ninjal.ac.jp} which is distributed in comma-separated value format.
With this format, each record shows a pair of a term and its semantic label.
In this thesaurus, terms and labels are represented by {\it midashi-hontai} values and {\it bunrui-bango} values, respectively.
For ${\cal T}^*_{\rm JB} = (R^*_{\rm JB}, L^*_{\rm JB}, f^*_{\rm JB})$, $R^*_{\rm JB}$ is formed as a set of midashi-hontai values, and $L^*_{\rm JB}$ is a set of bunrui-bango values.
Here, $f^*_{\rm JB}$ is constructed from the records.

The English context $K_{\rm E} = (O_{\rm E}, A_{\rm E}, I_{\rm E})$ was generated from the {\it Syntactic N-gram corpus} \cite{goldberg-orwant:2013:*SEM}.
Note that we used its subset ({\it nounargs}), which consists of predicate-argument structure.
To generate the context, we extracted the 10,000 most frequent noun terms from the structure and used them as objects.
For each object, we selected the top 99\% frequent pieces of structure and extracted parts from the selected pieces to construct attributes for the object.
For example, the noun term `boy' is an object that can be extracted from the structure shown in Fig.~\ref{fig:parsing}.
In the corpus, the structure surrounding `boy' is represented in the string `the/DT/det/2, boys/NNS/nsubj/7, eating/VBG/partmod/2, hamburgers/NNS/dobj/3, are/VBP/cop/7, my/PRP\$/poss/7, friends/NNS/nsubj/0, 100'.
The last token is its frequency, and the others represent the structure in which a term, its POS tag, its syntactic relation tag, and the position of its related term are separated by a `/'.
From the structure, three triplets can be extracted for the object `boy', as discussed in the Section~\ref{sec:FCA}.
If the parts satisfy the frequency condition, they are used as attributes for the object.

The Japanese context $K_{\rm J} = (O_{\rm J}, A_{\rm J}, I_{\rm J})$ was generated from {\it Case Frame Data} \cite{caseframe-data}, which consists of Japanese predicate-argument structure.
In the corpus distributed in XML format, each tag (referred to as an {\it entry}) contains pieces of the structure for a predicate term, which is indicated by the {\it headword} attribute of the tag.
An entry tag has {\it argument} tags that represent the types of modification by the {\it case} attribute.
In addition, an argument tag has {\it component} tags that represent noun terms.
Each descending path from an entry tag to a component tag represents a part of the predicate-argument structure, and its frequency is recorded in the component tag.
To generate $K_{\rm J}$, we filtered such paths in the same way we generated $K_{\rm E}$.
Then, we generated $K_{\rm J}$ from the remaining paths such that $O_{\rm J}$ is the set of noun terms that appear in the paths, $A_{\rm J}$ is the set of pairs of a predicate and a modification type, and $I_{\rm J}$ is simply constructed from the paths.


\subsection{Results and Discussion}
\label{sec:result}

The performance of the methods compared in our experiment is shown in Fig.~\ref{fig:results}.
To compare performance, we used four types of measure, i.e., precision, recall, the number of registerable terms, and run time,\footnote{Actually, the precision and recall values in Fig.~\ref{fig:results} and Tables~\ref{table:aa5nc}--\ref{table:aarfc} are the ratios to the theoretically highest value for the given extension task.In this experiment, precision and recall never reached $1.0$ due to the way ${\cal T}_i$ was generated (Section~\ref{subsec:resourceinexp}).} which were measured via 10-fold cross validation.
Here, an unregistered term $u$ is considered {\it registerable} with a method of $f'_i$ if $f'_i(u) \not= \emptyset$
Note that some methods may not register all unregistered terms.
We define the precision ${\rm p}(u)$ of each unregistered term $u$ as ${\rm p}(u) = |f'_i(u) \cap f^*_i(u)| / |f'_i(u)| = 0$ if $f'_i(u) = \emptyset$.\footnote{In general, ${\rm p}(u) = |f'_i(u) \cap f^*_i(u)| / |f'_i(u)| = 1$ if $f'_i(u) = \emptyset$.}
This precision estimates not to classifying terms as worthless rather than incorrect, because the purpose of thesaurus extension is to register unregistered terms.

As can be seen in Fig.~\ref{fig:results}, it is obvious from a recall perspective that the CLC method demonstrates outstanding performance.
The existing methods nearly fail to assign correct labels to unregistered terms.
In contrast, the CLC method successfully assigns approximately more than half of the correct labels to the terms.
The wide margin is primarily caused by the following.

First, the existing methods were originally proposed for binary-class or multi-class classification problems.
In binary-class or multi-class classification, each object belongs to only one class, i.e., each object is assigned a single label.
To solve such problems, the assumption that an object does not have a label is equal to the assumption that the object has one of the other labels.
Therefore, methods to solve such problems are sufficient only if they find the most suitable label for each object by omitting labels that are not suitable enough for the given object.
Essentially, this mechanism tends to increase precision but reduce recall in multi-label classification problems.
This can be considered an implementation of the false-negative policy.

\begin{figure}[t]
\begin{center}
\includegraphics{24-3ia1f7.eps}
\end{center}
\hangcaption{Experimental results. Results are arranged in a matrix whose rows correspond to the measures; and columns correspond to thesauri, e.g., the left-top graph shows precision values for each method when extending ${\cal T}_{\rm EW}$. The `\#Regs' axis corresponds to the number of registerable terms and the `Time (sec.)' axis corresponds to run time. In each graph, each data point an extension result. Some data points are unobserved due to time limits. For the tun time graphs, the SVC and MNB results are beyond our scope because they were too slow.}
\label{fig:results}
\end{figure}

The second reason is that the tendency mentioned above is increased by combining one vs.~the rest expansion with thesaurus extension problems.
With this expansion technique, each method generates as many binary classifiers as the number of all labels, and each classifier is related to each label.
Then, for each unregistered term, each classifier determines whether its label can be assigned to the term.
Finally, each unregistered term is given an aggregation of labels assigned by the classifiers.
However, in thesaurus extension, it is difficult for binary classifiers to assign labels to unregistered terms because, in thesauri, registered terms are assigned a few labels although many labels are defined.
In other words, each label is rarely given to registered terms.
Therefore, each classifier is likely to determine that its label is not also assigned to unregistered terms.
It is probable that other expansion methods improve the low recall of the compared methods.
However, this is a worse choice from a time-cost perspective because such methods generate over $|L|^2$ classifiers.

These two reasons also cause another wide margin relative to the number of registerable terms (Fig.~\ref{fig:results}).
Although the CLC method classifies all unregistered terms in each extension task, the other methods (expect for $1$-NC) cannot label many unregistered terms.
The $k$-NC methods consider $k$ registered terms that are considered similar terms of an unregistered term $u$ when classifying $u$, and they assign labels shared by the majority of the $k$ similar terms to term $u$.
Therefore, greater $k$ reduces the number of labels to be assigned to each unregistered term because many registered terms infrequently share a single label.
When $k = 1$, the majority equals the only similar term, and the labels of the term assigned to $u$.
In fact, for each extension task, $1$-NC registers more unregistered terms than $5$-NC, and $5$-NC registers more than $10$-NC.

Practically, classification methods cannot avoid the trade-off between precision and recall.
In classification problems, obtaining high precision makes it difficult to obtain high recall and vice versa.
The existing methods were designed to increase precision in exchange for recall.
However, the precision values obtained by the existing methods are not particularly high compared to those of the proposed CLC method.
By sacrificing recall, only 1-NC outperforms the CLC method in many cases.
In the ${\cal T}_{\rm JW}$ and ${\cal T}_{\rm JB}$ extensions, SVC obtains better precision, and MNB is also better for the ${\cal T}_{\rm JB}$ extension.
However, these two methods have large time-cost in addition to sacrifice of high recall.
The other methods demonstrate performance that is worse or comparable to that of the CLC method.
For accuracy, the extremely low recall values of the existing methods do not contribute to increasing precision.

These results demonstrate that the existing methods attempt to obtain high precision by hesitating about giving many labels to unregistered terms (false-negative policy).
However, these methods fail to maintain high precision and classify many unregistered terms in many cases.
Additional results are shown in Tables \ref{table:aa5nc}--\ref{table:aarfc} to verify whether the existing methods can obtain high recall for all unregistered terms in exchange for precision.
For methods that could not register all unregistered terms in the previous experiment (Fig.~\ref{fig:results}), we modified their thresholds such that they could classify all unregistered terms, i.e., changed to the false-positive policy.
The results show that methods that classified a few unregistered terms prior to this modification were able to classify all unregistered terms at the cost of precision.
Note that some methods increased precision values from 0.0.
The 0.0 precision values were given expediently in the previous experiment when the methods could not classify any unregistered terms.
Therefore, increased precision does not equate to overall performance improvement.
Then, the existing methods increased recall in exchange for precision.
However, these recall values were still much lower than those of the proposed CLC method (except for MNB).
Only the modified MNB yielded large increases to recall, and the recall values were greater than those of the CLC method (Table~\ref{table:aamnb}).
Note that this cannot be considered improvement because the modified thresholds were set to nearly 0.0.
The threshold in MNB are probabilities; thus, classification by the modified MNB is equivalent to unconditionally assigning all labels to each unregistered term.
The additional results demonstrate that it is difficult for the existing methods to increase both precision and recall to the levels obtained by the proposed CLC method.

\begin{table}[t]
\hangcaption{Comparison of the number of registerable terms, precision and recall of the 5-NC, modified 5-NC (denoted 5-NC$^+$) and CLC methods}
\label{table:aa5nc}
\input{01table05.txt}
\end{table}
\begin{table}[t]
\hangcaption{Comparison for the number of registerable terms, precision and recall of the 10-NC, modified 10-NC (denoted 10-NC$^+$) and CLC methods}
\label{table:aa10nc}
\input{01table06.txt}
\end{table}

Relative to tun time, Fig.~\ref{fig:results} shows that the CLC method was the fastest for all extension problems.
Note that the CLC method requires more time to prepare concept lattices; however, we emphasise that the time required for lattice construction can be ignored because, once a single lattice is generated, it can be used for many extension problems.
For example, the English lattice $\underline{\mathfrak B}(K_{\rm E})$ generated in the experiment can be used to extend other English thesauri.
The SVC, MNB and RFC methods are too slow because thesaurus extension is a classification problem that treats many labels.
In addition, the $k$-NC methods are slow for the ${\cal T}_{\rm EW}$ and ${\cal T}_{\rm EF}$ extension tasks because context $K_{\rm E}$ has more attributes than $K_{\rm J}$.

\begin{table}[t]
\hangcaption{Comparison for the number of registerable terms, precision and recall of the SVC, modified SVC (denoted SVC$^+$) and CLC methods}
\label{table:aasvc}
\input{01table07.txt}
\end{table}
\begin{table}[t]
\hangcaption{Comparison for the number of registerable terms, precision and recall of the MNB, modified MNB (denoted MNB$^+$) and CLC methods}
\label{table:aamnb}
\input{01table08.txt}
\end{table}

From the above-mentioned observations, the proposed CLC method is better than the existing methods relative to registering more terms correctly.
Moreover, the CLC method runs faster when extending each thesaurus; thus, it is suitable for problems that extends various thesauri using a single data set.

\begin{table}[t]
\hangcaption{Comparison for the number of registerable terms, precision and recall of the RFC, modified RFC (denoted RFC$^+$) and CLC methods}
\label{table:aarfc}
\input{01table09.txt}
\end{table}


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

We have formalised the problem of extending various thesauri and proposed the CLC method as a solution.
The CLC method has been designed to reduce the total time required to extend many thesauri.
This was proved experimentally by applying the proposed and existing methods to the same materials.

The experimental results demonstrate that the CLC method performs faster than the existing methods, and that it is by far the best in terms of recall.
In some limited cases, the 1-NC, SVC, MNB methods yielded better precision values than those of the CLC method.
However, this comes at the expense of high recall values and/or long run times.
This conclusion supports the fact that the proposed CLC method is most suitable for solving such problems.

In future, we plan to improve the proposed method to obtain better precision values.
Currently, the number of incorrect labels assigned to unregistered terms is not negligible with the proposed CLC method.
This is caused by the ways in which synonyms are found and labels are assigned for each unregistered terms.
We conjecture that finding synonyms can be improved by revising or modifying the Jaccard index.
In addition, we speculate that assigning labels could be improved by applying a filter to remove labels based on label frequency in the target thesaurus to be extended.
We plan to implement these improvements such that short total run times are maintained.


\acknowledgment

This research was supported by CREST, JST.


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

\bibitem[\protect\BCAY{Agirre, Ansa, Hovy, \BBA\ Martinez}{Agirre
  et~al.}{2000}]{Agirre00enrichingvery}
Agirre, E., Ansa, O., Hovy, E., \BBA\ Martinez, D. \BBOP 2000\BBCP.
\newblock \BBOQ Enriching Very Large Ontologies Using the WWW.\BBCQ\
\newblock In {\Bem Proceedings of the ECAI 2000 Workshop Ontology Learning}.

\bibitem[\protect\BCAY{Baker, \mbox{Fillmore}, \BBA\ Lowe}{Baker
  et~al.}{1998}]{Baker:1998:BFP:980845.980860}
Baker, C.~F., \mbox{Fillmore}, C.~J., \BBA\ Lowe, J.~B. \BBOP 1998\BBCP.
\newblock \BBOQ The Berkeley FrameNet Project.\BBCQ\
\newblock In {\Bem Proceedings of the 36th Annual Meeting of the Association
  for Computational Linguistics and the 17th International Conference on
  Computational Linguistics---Volume 1}, \mbox{\BPGS\ 86--90}.

\bibitem[\protect\BCAY{Belur}{Belur}{1990}]{knn}
Belur, V.~D. \BBOP 1990\BBCP.
\newblock {\Bem Nearest Neighbor (NN) Norms: NN Pattern Classification
  Techniques}.
\newblock IEEE Computer Society Press.

\bibitem[\protect\BCAY{Bishop}{Bishop}{2006}]{eb}
Bishop, C.~M. \BBOP 2006\BBCP.
\newblock {\Bem Pattern Recognition and Machine Learning}.
\newblock Springer.

\bibitem[\protect\BCAY{Bond, Baldwin, Fothergill, \BBA\ Uchimoto}{Bond
  et~al.}{2012}]{jwn}
Bond, F., Baldwin, T., Fothergill, R., \BBA\ Uchimoto, K. \BBOP 2012\BBCP.
\newblock \BBOQ Japanese SemCor: A Sense-tagged Corpus of Japanese.\BBCQ\
\newblock In {\Bem Proceedings of the 6th International Conference of the
  Global WordNet Association}, \mbox{\BPGS\ 56--63}.

\bibitem[\protect\BCAY{Breiman}{Breiman}{2001}]{DBLP:journals/ml/Breiman01}
Breiman, L. \BBOP 2001\BBCP.
\newblock \BBOQ Random Forests.\BBCQ\
\newblock {\Bem Machine Learning}, {\Bbf 45}  (1), \mbox{\BPGS\ 5--32}.

\bibitem[\protect\BCAY{Cerbah}{Cerbah}{2000}]{Cerbah00exogenousand}
Cerbah, F. \BBOP 2000\BBCP.
\newblock \BBOQ Exogenous and Endogenous Approaches to Semantic Categorization
  of Unknown Technical Terms.\BBCQ\
\newblock In {\Bem Proceedings of the 18th International Conference on
  Computational Linguistics}, \mbox{\BPGS\ 145--151}.

\bibitem[\protect\BCAY{Ganter \BBA\ Wille}{Ganter \BBA\
  Wille}{1999}]{Ganter:1999:FCA:550737}
Ganter, B.\BBACOMMA\ \BBA\ Wille, R. \BBOP 1999\BBCP.
\newblock {\Bem Formal Concept Analysis: Mathematical Foundations}.
\newblock Springer-Verlag Berlin Heidelberg.

\bibitem[\protect\BCAY{Goldberg \BBA\ Orwant}{Goldberg \BBA\
  Orwant}{2013}]{goldberg-orwant:2013:*SEM}
Goldberg, Y.\BBACOMMA\ \BBA\ Orwant, J. \BBOP 2013\BBCP.
\newblock \BBOQ A Dataset of Syntactic-Ngrams over Time from a Very Large
  Corpus of English Books.\BBCQ\
\newblock In {\Bem Proceedings of the 2nd Joint Conference on Lexical and
  Computational Semantics}, \mbox{\BPGS\ 241--247}.

\bibitem[\protect\BCAY{Guyon, Boser, \BBA\ Vapnik}{Guyon
  et~al.}{1993}]{Guyon93automaticcapacity}
Guyon, I., Boser, B., \BBA\ Vapnik, V. \BBOP 1993\BBCP.
\newblock \BBOQ Automatic Capacity Tuning of Very Large VC-dimension
  Classifiers.\BBCQ\
\newblock In {\Bem Proceedings of Advances in Neural Information Processing
  Systems}, \mbox{\BPGS\ 147--155}.

\bibitem[\protect\BCAY{Ikeda \BBA\ Yamamoto}{Ikeda \BBA\
  Yamamoto}{2014}]{Ikeda14:ALSIP14}
Ikeda, M.\BBACOMMA\ \BBA\ Yamamoto, A. \BBOP 2014\BBCP.
\newblock \BBOQ Local Feature Selection by Formal Concept Analysis for
  Multi-class Classification.\BBCQ\
\newblock In {\Bem Proceedings of the 4th International Workshop on Algorithms
  for Large-Scale Information Processing in Knowledge Discovery (ALSIP2014)},
  \lowercase{\BVOL}\ 8643 of {\Bem LNCS}, \mbox{\BPGS\ 470--482}.

\bibitem[\protect\BCAY{Ito, Nakayama, Hara, \BBA\ Nishio}{Ito
  et~al.}{2008}]{Ito:2008:ATC:1458082.1458191}
Ito, M., Nakayama, K., Hara, T., \BBA\ Nishio, S. \BBOP 2008\BBCP.
\newblock \BBOQ Association Thesaurus Construction Methods Based on Link
  Co-occurrence Analysis for Wikipedia.\BBCQ\
\newblock In {\Bem Proceedings of the 17th ACM Conference on Information and
  Knowledge Management}, \mbox{\BPGS\ 817--826}.

\bibitem[\protect\BCAY{Kawahara \BBA\ Kurohashi}{Kawahara \BBA\
  Kurohashi}{2006}]{caseframe-data}
Kawahara, D.\BBACOMMA\ \BBA\ Kurohashi, S. \BBOP 2006\BBCP.
\newblock \BBOQ A Fully-Lexicalized Probabilistic Model for Japanese Syntactic
  and Case Structure Analysis.\BBCQ\
\newblock In {\Bem Proceedings of the Human Language Technology Conference of
  the North American Chapter of the Association for Computational Linguistics},
  \mbox{\BPGS\ 176--183}.

\bibitem[\protect\BCAY{Kibriya, Frank, Pfanhringer, \BBA\ Holmes}{Kibriya
  et~al.}{2004}]{Kibriya:2004:MNB:2146834.2146882}
Kibriya, A.~M., Frank, E., Pfanhringer, B., \BBA\ Holmes, G. \BBOP 2004\BBCP.
\newblock \BBOQ Multinomial Naive Bayes for Text Categorization
  Revisited.\BBCQ\
\newblock In {\Bem Proceedings of the 17th Australian Joint Conference on
  Advances in Artificial Intelligence}, \mbox{\BPGS\ 488--499}.

\bibitem[\protect\BCAY{Lin}{Lin}{1998}]{Lin:1998:ARC:980432.980696}
Lin, D. \BBOP 1998\BBCP.
\newblock \BBOQ Automatic Retrieval and Clustering of Similar Words.\BBCQ\
\newblock In {\Bem Proceedings of the 17th International Conference on
  Computational Linguistics---Volume 2}, \mbox{\BPGS\ 768--774}.

\bibitem[\protect\BCAY{Liu \BBA\ Zheng}{Liu \BBA\ Zheng}{2005}]{Liu:2005}
Liu, Y.\BBACOMMA\ \BBA\ Zheng, Y.~F. \BBOP 2005\BBCP.
\newblock \BBOQ One-against-all Multi-class SVM Classification Using
  Reliability Measures.\BBCQ\
\newblock In {\Bem Proceedings of 2005 IEEE International Joint Conference on
  Neural Networks}, \mbox{\BPGS\ 849--854}.

\bibitem[\protect\BCAY{Marcus, Kim, Marcinkiewicz, MacIntyre, Bies, Ferguson,
  Katz, \BBA\ Schasberger}{Marcus
  et~al.}{1994}]{Marcus:1994:PTA:1075812.1075835}
Marcus, M., Kim, G., Marcinkiewicz, M.~A., MacIntyre, R., Bies, A., Ferguson,
  M., Katz, K., \BBA\ Schasberger, B. \BBOP 1994\BBCP.
\newblock \BBOQ The Penn Treebank: Annotating Predicate Argument
  Structure.\BBCQ\
\newblock In {\Bem Proceedings of the Workshop on Human Language Technology},
  HLT '94, \mbox{\BPGS\ 114--119}.

\bibitem[\protect\BCAY{Miller, Beckwith, Fellbaum, Gross, \BBA\ Miller}{Miller
  et~al.}{1990}]{Miller90wordnet:an}
Miller, G.~A., Beckwith, R., Fellbaum, C., Gross, D., \BBA\ Miller, K. \BBOP
  1990\BBCP.
\newblock \BBOQ WordNet: An On-line Lexical Database.\BBCQ\
\newblock {\Bem International Journal of Lexicography}, {\Bbf 3}, \mbox{\BPGS\
  235--244}.

\bibitem[\protect\BCAY{Navigli}{Navigli}{2009}]{Navigli:2009:WSD:1459352.1459355}
Navigli, R. \BBOP 2009\BBCP.
\newblock \BBOQ Word Sense Disambiguation: A Survey.\BBCQ\
\newblock {\Bem ACM Computing Surveys}, {\Bbf 41}  (2), \mbox{\BPGS\
  10:1--10:69}.

\bibitem[\protect\BCAY{Navigli \BBA\ Ponzetto}{Navigli \BBA\
  Ponzetto}{2012}]{NAVIGLI2012217}
Navigli, R.\BBACOMMA\ \BBA\ Ponzetto, S.~P. \BBOP 2012\BBCP.
\newblock \BBOQ BabelNet: The Automatic Construction, Evaluation and
  Application of a Wide-coverage Multilingual Semantic Network.\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bbf 193}, \mbox{\BPGS\ 217--250}.

\bibitem[\protect\BCAY{Pal}{Pal}{2005}]{doi:10.1080/01431160412331269698}
Pal, M. \BBOP 2005\BBCP.
\newblock \BBOQ Random Forest Classifier for Remote Sensing
  Classification.\BBCQ\
\newblock {\Bem International Journal of Remote Sensing}, {\Bbf 26}  (1),
  \mbox{\BPGS\ 217--222}.

\bibitem[\protect\BCAY{Peleja, Santos, \BBA\ Magalh{\~{a}}es}{Peleja
  et~al.}{2014}]{Peleja:2014:RAR:2600428.2609546}
Peleja, F., Santos, J., \BBA\ Magalh{\~{a}}es, J. \BBOP 2014\BBCP.
\newblock \BBOQ Reputation Analysis with a Ranked Sentiment-lexicon.\BBCQ\
\newblock In {\Bem Proceedings of the 37th International ACM SIGIR Conference
  on Research \& Development in Information Retrieval}, \mbox{\BPGS\
  1207--1210}.

\bibitem[\protect\BCAY{Ramage, Hall, Nallapati, \BBA\ Manning}{Ramage
  et~al.}{2009}]{Ramage:2009:LLS:1699510.1699543}
Ramage, D., Hall, D., Nallapati, R., \BBA\ Manning, C.~D. \BBOP 2009\BBCP.
\newblock \BBOQ Labeled LDA: A Supervised Topic Model for Credit Attribution in
  Multi-labeled Corpora.\BBCQ\
\newblock In {\Bem Proceedings of the 2009 Conference on Empirical Methods in
  Natural Language Processing (EMNLP '09)}, \mbox{\BPGS\ 248--256}.

\bibitem[\protect\BCAY{Rigutini, Di~Iorio, Ern, \BBA\ Maggini}{Rigutini
  et~al.}{2006}]{Rigutini:automaticterm}
Rigutini, L., Di~Iorio, E., Ern, M., \BBA\ Maggini, M. \BBOP 2006\BBCP.
\newblock \BBOQ Automatic Term Categorization by Extracting Knowledge from the
  Web.\BBCQ\
\newblock In {\Bem Proceedings of The 17th European Conference on Artificial
  Intelligence}, \mbox{\BPGS\ 531--535}.

\bibitem[\protect\BCAY{Rus \BBA\ Graesser}{Rus \BBA\ Graesser}{2005}]{Rus:2005}
Rus, V.\BBACOMMA\ \BBA\ Graesser, A. \BBOP 2005\BBCP.
\newblock \BBOQ Lexico-Syntactic Subsumption for Textual Entailment.\BBCQ\
\newblock In {\Bem Proceedings of Recent Advances in Natural Language
  Processing IV}, \mbox{\BPGS\ 187--196}.

\bibitem[\protect\BCAY{Taira, Fujita, \BBA\ Nagata}{Taira
  et~al.}{2008}]{Taira:2008:JPA:1613715.1613780}
Taira, H., Fujita, S., \BBA\ Nagata, M. \BBOP 2008\BBCP.
\newblock \BBOQ A Japanese Predicate Argument Structure Analysis Using Decision
  Lists.\BBCQ\
\newblock In {\Bem Proceedings of the 2008 Conference on Empirical Methods in
  Natural Language Processing (EMNLP '08)}, \mbox{\BPGS\ 523--532}.

\bibitem[\protect\BCAY{Tokunaga, Fujii, \BBA\ Iwayama}{Tokunaga
  et~al.}{1997}]{Takenobu97extendinga}
Tokunaga, T., Fujii, A., \BBA\ Iwayama, M. \BBOP 1997\BBCP.
\newblock \BBOQ Extending a Thesaurus By Classifying Words.\BBCQ\
\newblock In {\Bem Proceedings of the ACL-EACL Workshop on Automatic
  Information Extraction and Building of Lexical Semantic Resources},
  \mbox{\BPGS\ 16--21}.

\bibitem[\protect\BCAY{Uno, Kiyomi, \BBA\ Arimura}{Uno
  et~al.}{2005}]{Uno05lcmver}
Uno, T., Kiyomi, M., \BBA\ Arimura, H. \BBOP 2005\BBCP.
\newblock \BBOQ LCM ver. 3: Collaboration of Array, Bitmap and Prefix Tree for
  Frequent Itemset Mining.\BBCQ\
\newblock In {\Bem Proceedings of the ACM SIGKDD Open Source Data Mining
  Workshop on Frequent Pattern Mining Implementations}, \mbox{\BPGS\ 77--86}.

\bibitem[\protect\BCAY{Uramoto}{Uramoto}{1996}]{Uramoto:1996:PUW:993268.993333}
Uramoto, N. \BBOP 1996\BBCP.
\newblock \BBOQ Positioning Unknown Words in a Thesaurus by Using Information
  Extracted from a Corpus.\BBCQ\
\newblock In {\Bem Proceedings of the 16th Conference on Computational
  Linguistics}, \lowercase{\BVOL}~2, \mbox{\BPGS\ 956--961}.

\bibitem[\protect\BCAY{Ykhlef \BBA\ Al~Dayel}{Ykhlef \BBA\
  Al~Dayel}{2012}]{6470907}
Ykhlef, M.\BBACOMMA\ \BBA\ Al~Dayel, A. \BBOP 2012\BBCP.
\newblock \BBOQ Query Paraphrasing Using Genetic Approach for Intelligent
  Information Retrieval.\BBCQ\
\newblock In {\Bem Proceedings of International Conference for Internet
  Technology And Secured Transactions 2012}, \mbox{\BPGS\ 699--703}.

\bibitem[\protect\BCAY{Zhang \BBA\ Zhou}{Zhang \BBA\ Zhou}{2007}]{Zhang:2007}
Zhang, M.\BBACOMMA\ \BBA\ Zhou, Z. \BBOP 2007\BBCP.
\newblock \BBOQ ML-KNN: A Lazy Learning Approach to Multi-label Learning.\BBCQ\
\newblock {\Bem Pattern Recognition}, {\Bbf 40}  (7), \mbox{\BPGS\ 2038--2048}.

\end{thebibliography}

\begin{biography}

\bioauthor[:]{Madori Ikeda}{
Currently a Ph.D. student at Graduate School of Informatics, Kyoto University, Japan.
Received a bachelor's degree in engineering from Nagoya Institute of Technology, Japan, in 2008, and a master's degree in informatics from Graduate School of Informatics, Kyoto University in 2010.
}

\bioauthor[:]{Akihiro Yamamoto}{
Completed a doctoral program of Kyushu University in 1990.
Doctor of Science. Currently a professor at Kyoto University.
Involved with research on machine learning of formal languages and data
mining from structured data.
}
\end{biography}



\biodate




\end{document}
