\documentclass[english,tombow]{jnlp_3.2}
\usepackage{jnlpbbl_1.4}
\usepackage[dvipdfm]{graphicx}
\usepackage{gentombow}
\usepackage{amsmath}
\settombowbleed{5mm}
\usepackage{hangcaption_jnlp}
\usepackage{array}
%%%%\usepackage{udline}
%%%%\setulminsep{1.2ex}{0.2ex}
%%%%\let\underline=\ul
%%%%\makeatletter
%%%%\def\@{\spacefactor3000\space}
%%%%\makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% author's definition
%%%%\documentclass[english,tombow]{jnlp_2.1}
%%%%\usepackage{paralist}
%%%%\usepackage{jnlpbbl_1.3}
%%%%%\usepackage[dvipdfmx]{graphicx}
%%%%\usepackage[dvipdfmx,nosetpagesize]{graphicx}
%%%%\usepackage[dvipdfmx,nosetpagesize]{color}
%%%%\usepackage[dvipdfmx,nosetpagesize]{colortbl}
%%%%\usepackage{amsmath}
%%%%%\newtheorem{hyp}{Hypothesis}
%%%%\usepackage{multirow} 
\usepackage[linesnumbered, ruled,vlined]{algorithm2e}
\SetKwInOut{Parameter}{Parameter}
%%%%\usepackage{xcolor}
%%%%\usepackage{color}
\usepackage{multirow}
%%%%\usepackage{tabularx}
%%%%\usepackage{graphicx}
\usepackage{paralist}
%%%%%\usepackage{subcaption}
%%%%%\usepackage{caption}
%%%%%\graphicspath{ {./images/} }
%%%%\definecolor{chromeyellow}{rgb}{0.91, 0.84, 0.42}
%%%%\definecolor{burntorange}{rgb}{0.8, 0.33, 0.0}
%%%%%\definecolor{chromeyellow}{rgb}{1.0, 0.65, 0.0}
%%%%\definecolor{mypink2}{RGB}{219, 48, 122}
%%%%%\newcommand{\authorA}[1]{{\color{cincinnati-red}[A: #1]}}
%%%%\newcommand{\hu}[1]{{\color{violet}[H: #1]}}
%%%%%\newcommand{\hu}[1]{{\color{blue}[H: #1]}}
%%%%\definecolor{OliveGreen}{rgb}{0,0.6,0}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\renewcommand{\refname}{References}

\Volume{27}
\Number{3}
\Month{September}
\Year{2020}
%%%%\Issuetitle{Special Issue: XXXXXXXX}

\received{2020}{5}{25}
%%%%\revised{2006}{3}{4}
%%%%\rerevised{2006}{5}{6}
\accepted{2020}{7}{3}

\setcounter{page}{627}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\esubject{Genaral Paper}
\etitle{AutoEncoder Guided Bootstrapping of Semantic Lexicon}
\eauthor{Chenlong Hu\affiref{Author_1} \and Mikio Nakano \affiref{Author_2} \and Manabu Okumura\affiref{Author_3} } 
\eabstract{%
Mutual bootstrapping is a commonly used technique for many natural language processing tasks, including semantic lexicon induction. Among many bootstrapping methods, the \textit{Basilisk} algorithm has led to successful applications through two key iterative steps: scoring context patterns and candidate instances. In this work, we improve Basilisk by modifying its two scoring functions. By incorporating AutoEncoder in the scoring functions of patterns and candidates, we can reduce the bias problems and obtain more balanced results. The experimental results demonstrate that our proposed methods for guiding the bootstrapping of a semantic lexicon with AutoEncoder can boost overall performance. 
}
\ekeywords{Bootstrapping, AutoEncoder, Semantic Lexicon}

\headauthor{Hu, Nakano, Okumura}
\headtitle{AutoEncoder Guided Bootstrapping of Semantic Lexicon}

\affilabel{Author_1}{}{Tokyo Institute of Technology}
\affilabel{Author_2}{}{Honda Research Institute Japan Co., Ltd. \\ Currently with C4A Research Institute, Inc.}
\affilabel{Author_3}{}{Tokyo Institute of Technology}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

Acquiring large amounts of knowledge for natural language processing tasks can be costly when performed manually. 
Therefore, there is an increasing need to acquire knowledge, such as semantic lexicons, from raw text corpora. 
Such acquired knowledge, including the semantic lexicons, is beneficial for numerous application scenarios, e.g., domain-specific dialogue systems \cite{nakano:book15}.

As minimal supervision algorithms, \textit{bootstrapping} methods are efficient tools to explore knowledge from unannotated corpora with increasing text size. 
Their simple input strategy, a human-defined seed list, gets rid of the needs of complicated human-crafted rules, enormous amounts of annotated training data, which are both time-consuming and costly to construct. 
Another benefit of bootstrapping is the flexibility for different emerging tasks. 
Yarowsky showed the effectiveness of \textit{bootstrapping} learning in improving the performance of the task of word sense disambiguation \cite{Yarowsky:1995:UWS:981658.981684}.
Then, \textit{bootstrapping} techniques have been conveniently used in a variety of tasks, including relation extraction \cite{brin1998extracting,agichtein2000snowball} and semantic lexicon induction \cite{lin2003bootstrapped,thelen2002bootstrapping}. 
In addition, the most prominent characteristic of this idea, the \textit{iterative} learning process, has the potential to add more new instances as iterations progress.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 1
\begin{figure}[b]
\begin{center}
\includegraphics{27-3ia6f1.eps}
\end{center}
\hangcaption{Process of Basilisk-like bootstrapping (solid line part) and the proposed AutoEncoder guided bootstrapping method (including dashed line part)} 
\label{fig:basilisk_process}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this work, we focus on the task of acquiring semantic lexicons using the \textit{bootstrapping} technique. 
Specifically, we follow the framework of \textit{Basilisk} \cite{thelen2002bootstrapping}, an effective and commonly used bootstrapping approach for constructing semantic lexicons from text corpora. 
As one kind of bootstrapping methods, Basilisk inherits the advantages  and characteristics of bootstrapping.  
In Basilisk, it is also not necessary to label training data, and this makes it more efficient and resources-saving. 
To explore semantic lexicons, all you need is to input an initial \emph{seed list} with a limited number of initial seed words. 
Thus, it is simple to try the Basilisk algorithm to seek different types of lexicons from a text corpus. 
The process of Basilisk can be seen from Figure \ref{fig:basilisk_process}. 
Given a seed list, we can start the Basilisk process to explore an unannotated corpus.
As the bootstrapping learning process continues, the list of seed words will be expanded iteratively.  
Basilisk adds not just new words, but also \emph{patterns} indicating the context around the words.
Thus, Basilisk iteratively learns two apparently different knowledge of patterns and semantic lexicons,
i.e., two types of knowledge will be bootstrapped \emph{alternately} during each iterative process. 
Another key idea would be \emph{mutual bootstrapping}, where one type of knowledge (lexicon or pattern) is evaluated on the basis of the collective information from another type of knowledge. 
Therefore, it evaluates and learns two types of knowledge on patterns and lexicons in turn, and they then benefit each other mutually.
Three benefits of Basilisk can be summarized as:   
\begin{inparaenum}[1)]
\item flexibility, 
\item learning iteratively, and 
\item mutual bootstrapping of two knowledge.
\end{inparaenum}

Basilisk would define a framework for bootstrapping that can be developed for a variety of applications, rather than only a way of bootstrapping.
Basilisk has been modified and used in subsequent work, making it possible to bootstrap many types of knowledge.
For example, new types of lexicons including subjectivity lexicons and patient polarity verbs (PPVs) can be learned with the same Basilisk algorithm \cite{riloff2003learning,wiebe2005creating}.
To induce new lexicons from Twitter, there was the work that dropped the iterative process while keeping the part of its evaluation mechanism \cite{AAAI1510016}.
Incorporating supervised learning would be another choice; it explores the idea of inducing a contextual classifier trained on positive instances of one category and negative instances from the others \cite{huang2010inducing}.

In this paper, we would like to incorporate AutoEncoder to improve the Basilisk bootstrapping approach in an unsupervised manner. 
The key idea is to use AutoEncoder to guide the two scoring functions: \textit{candidate scoring} and \textit{pattern scoring}, which are used for two fundamental steps of evaluating patterns and candidate instances alternately.
AutoEncoder, which is usually realized with a feed forward network with a bottleneck structure and could be used to learn a compact representation of input positive samples  \cite{bourlard1988auto,hinton2006reducing}. 
This neural model consists of an encoder for computing a representation from an input, and a decoder for reconstructing the input from the representation. 
The parameters involved in the network can be optimized by reducing the loss of \emph{reconstruction} which computes the difference between the reconstructed outputs and the inputs.

Our motivation is that, while we have only a small number of seed (positive) instances, we can utilize these positive samples to complete learning.
In this setting, we do not rely on any negative samples, obtained through expensive expert knowledge or learning approaches \cite{lin2003bootstrapped,curran2007minimising,mcintosh2010unsupervised}.  
Furthermore, the learning paradigm is unsupervised such that we can follow the principle advantages of unsupervised bootstrapping. 
If we train AutoEncoder only with these positive instances generated in bootstrapping iterations, the \emph{reconstruction} score,  which measures the similarity between the original input and reconstructed input, can measure how well a candidate is reconstructed by it.  
In addition, because of the increasing number of positive samples extracted in bootstrapping iterations, AutoEncoder can be updated in an incremental manner. 
In each evaluation step of bootstrapping, AutoEncoder can be used to score and identify the better candidates. 
Besides \textit{candidates},  we also attempt to use AutoEncoder to get a new pattern scoring mechanism.  
This new metric for \textit{pattern scoring} could benefit downstream steps, resulting in boosting the results of a bootstrapping approach based on Basilisk. 
Our methods can be summarized as follows: 
\begin{itemize}
    \item We use AutoEncoder to guide the learning of bootstrapping in a totally unsupervised manner.
	\item We improve candidate evaluation by incorporating AutoEncoder, which does not rely on any additional training data. 
	\item We also present a new function to boost the scoring of patterns such that better candidates will be pooled in subsequent steps. The performance of candidate scoring can be improved by including our new pattern scoring function. 
\end{itemize}

The rest of the paper is organized as follows: 
We first summarize the related work in Section \ref{sec:related_works}.  
Section \ref{sec:preliminary_background} introduces the preliminary and background. 
Section \ref{sec:ProposedMethods} describes the proposed methods. The experimental setup and results are presented in Section \ref{sec:Experiment_section}. 
Finally, we conclude this paper. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related Work}
\label{sec:related_works}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Information extraction: }
Extracting structured knowledge has been addressed in the general area of \textit{information extraction} (IE), and more specifically, \textit{relation extraction}, which finds semantic relations, including semantic lexicons, in a text corpus \cite{moens2006information,DBLP:books/lib/JurafskyM09}.  
The extensive approaches under this topic, which share the common techniques with our task of extracting semantic lexicons, can be grouped into four categories: rule-based, supervised, distant-supervised and bootstrapping methods. 
With pioneering work by \citeA{hearst1992automatic}, who used manually-constructed lexico-syntactic patterns to identify hyponyms, \citeA{caraballo1999automatic}, \citeA{berland1999finding} and \citeA{girju2006automatic} used the similar approach for identifying part-whole relations. 
However, these rule-based methods cannot be easily applied directly to other corpora \cite{DBLP:books/lib/JurafskyM09} because each requires specific expert-designed patterns. 
A supervised algorithm, trained with human-labeled samples, is another straightforward and effective approach where classifiers trained with hand-labeled corpora are used to label different knowledge \cite{zhou2007tree,surdeanu2007robust,santos2015classifying}.
However, it is time-consuming to obtain annotated data for a sizable corpus.  
Due to the above reasons, distantly supervised or weakly-supervised approaches have attracted more attention for obtaining semantic resources from a large-scale corpus. 
These methods attempt to build an alignment between a raw corpus and a knowledge database \cite{mintz2009distant}. 
By using a database like \textit{Freebase} \cite{bollacker2008freebase}, a large number of samples with noisy labels can be used for training a supervised classifier. 
However, the use of distant supervision is limited to tasks with available knowledge databases. 
\paragraph{Bootstrapping: } Compared with the approaches described above, \textit{bootstrapping} can be considered a more effective and adaptable algorithm as it is not required to construct complex patterns and knowledge bases.  
The bootstrapping methods start with a small number of seed instances or patterns and iteratively enlarge the set of labeled instances \cite{pantel2006espresso,kiso2011hits,ravichandran2002learning}.  
The framework of \emph{Basilisk} has been used for learning new types of knowledge, including subjective nouns \cite{riloff2013sarcasm} and event-related nouns \cite{phillips2007exploiting}.
New types of patterns, even regular expressions, can be learned by using part of this bootstrapping framework \cite{stevenson-greenwood-2005-semantic,gupta2014improved,simoes2018content}.
Given a target corpus, the only difference is a new seed list for the task. 
In some subsequent work, negative samples from other categories have been incorporated in the unsupervised bootstrapping process \cite{mcintosh2010unsupervised}. 
For example, to learn lexicons of multiple categories simultaneously, the concept of \emph{mutual exclusion} was incorporated to supervise candidate words or patterns to be extracted for a single category, e.g., \emph{MEB} \cite{curran2007minimising}, \emph{WMEB} \cite{mcintosh2008weighted}.
\citeA{mcintosh2009reducing} improved the above two methods by comparing the similarity drift among iterations. 
A more effective way of using negative information was presented by the work of \citeA{huang2010inducing}, which trains contextual classifiers where each classifier decides whether a noun phrase belongs to a semantic category.
Other work has changed how they train Basilisk.
The idea of ensembling has also been considered \cite{qadir-riloff-2012-ensemble}.
Except the iterative bootstrapping work mentioned above,
\citeA{jauhar-hovy-2017-embedded} attempted to learn an embedded frame lexicon using predicate-argument structure, and  \citeA{AAAI1510016} used a non-iterative process to learn from tweets, where much non-standard content exists, while keeping part of the evaluation functions in Basilisk.  
Different from those approaches, the proposed method improves the bootstrapping of semantic lexicons by incorporating unsupervised neural networks into the framework of Basilisk and acquires knowledge in a totally unsupervised manner.   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminary and Background}
\label{sec:preliminary_background}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Problem Statement:}
The objective of this research is to acquire lexicons for a semantic domain from a general corpus.
First, consider a text corpus $\mathcal{C}$ and a list $ \mathcal{S}$ containing manually crafted seed words (e.g., ``\textit{banana,}''``\textit{spaghetti,}''...), that are intended to belong to this  \textit{food} category. 
This is the only human input to the entire learning process. 
With minimal syntactic structure information, we use only a \textit{conjunction} pattern with the form of multiple conjunctive items $( n_1, n_2,  n_3)$ (a trigram of noun phrases or nouns).  
Here, candidate words are selected irrespective of order
and can be at any position in $( n_1, n_2,  n_3)$. 
Once a word $ n \in \mathcal{S} $ is in $( n_1, n_2,  n_3)$, the pattern $( n_1, n_2,  n_3)$ will be considered as a candidate pattern in the set $\mathcal{P}$.   
An example is (\textit{penne}, \textit{spaghetti} , \textit{xyz}), where it is assumed that  ``\textit{spaghetti}''  and ``\textit{penne}'' are in the seed list and \textit{xyz} denotes a candidate word. 
If we can find a set of candidates \textit{xyz}, we can evaluate them and add some of them to the seed list and repeat the process.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Background:}
Our method, much like the previous work (e.g., Basilisk \cite{riloff1999learning,thelen2002bootstrapping}), acquires semantic lexicons in a bootstrapping manner. 
We follow the general framework and iterative process of Basilisk, illustrated in Algorithm \ref{algo:Basilisk} and Figure  \ref{fig:basilisk_process}. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% algo. 1
\begin{algorithm}[b]
\KwIn{ seed list $ \mathcal{S} $, corpus $\mathcal{C}$ }  
\KwOut{seed list $ \mathcal{S}$  (updated)}
\Parameter{$k$,  $q$}
Generate context patterns and store them in  $\mathcal{P}$, score the patterns on the basis of Equation \ref{eq:1} \\
Select top-$(k+l)$ patterns to $pattern\_pool$  \quad \# $l$ is the iteration index \\ 
Select all extractions with patterns in $pattern\_pool$ to $candidate\_instance\_pool$ \\
Score all candidate instances in  $candidate\_instance\_pool$ on the basis of Equation \ref{eq:2}   \\
Add top-$q$ candidates to seed list  $ \mathcal{S} $\\ 
$l=l+1$ \quad  \# increment the iteration index   \\
Repeat \textit{Steps $1$ to $6$ }
\caption{ Algorithm of Basilisk Bootstrapping}
\label{algo:Basilisk}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Prior to the actual iterative process,   $ \mathcal{S} $, a list of seed instances with a limited number, is inputted to the system. 
On the basis of this seed list, corresponding contextual patterns are then generated and stored in the set $\mathcal{P}$,  where the inputted seed words appear in the corpus.
The process starts with \textit{pattern scoring} as shown below: 
\begin{enumerate}
  \item \textbf{Pattern Scoring}: patterns in $\mathcal{P}$ are scored and ranked with $RlogF$: 
        \begin{equation}\label{eq:1}
            RlogF(p) = F / N * log(F), 
        \end{equation}
        where $p \in \mathcal{P}$ denotes a pattern to be evaluated. 
        $\mathcal{N}$ denotes the set of instances extracted by pattern $p$, 
        and $N = |\mathcal{N}|$ is the total number of extracted instances. 
        $\mathcal{F} $ is a set of correctly extracted words, i.e.,   $ \mathcal{F} = \mathcal{N} \cap   \, \mathcal{S} $,
        and $F$ computes the cardinality of $\mathcal{F} $. 
        This pattern score essentially represents the productivity of each pattern (the ability to extract candidates).
  \item Pattern Selection: on the basis of the score, the top-$(k+l)$ patterns are selected and placed in the $pattern\_pool$.
  \item Candidate Pool: all the instances newly extracted by the patterns in the $pattern\_pool$ are put into the $candidate\_instance\_pool$, except for those already in the seed list.  
  \item  \textbf{Candidate Scoring}:  to evaluate each candidate word $c$ in 
  the $candidate\_instance\_pool$,  
  $AvglogF$ is used as the scoring metric, as defined below,
        \begin{equation} \label{eq:2}
            AvglogF(c) = \sum_{i=1}^{P} log_2(F_i+1) / P, 
        \end{equation}
    where $i$ is used to index pattern $p_i$.  
    Assuming candidate $c$ is extracted by $P$ patterns, and $F_i$ is the corresponding number of correct instances (as explained in Equation \ref{eq:1}), 
    this function calculates the mean value of productivity for the patterns. 
    The most important step is Step $4$, where candidate instances are scored. 
    Note that the candidates are evaluated on the basis of all patterns in  $\mathcal{P}$ rather than in  $pattern\_pool$.  
  \item Top-$q$  candidate words are added to the seed list $\mathcal{S}$   for the next iteration. 
\end{enumerate}

In the work of  \cite{thelen2002bootstrapping}, rather than using $AvglogF$ (Equation \ref{eq:2}), the authors first investigated the effect  of another candidate scoring function, $AvgF$: 
\begin{equation} \label{eq:3}
AvgF(c) =  \sum_{i=1}^{P} F_i / P.
\end{equation}

However, the simple \textit{average} strategy is prone to be biased by one pattern with a large number of extractions $F_i$.
To minimize this problem, $logarithm$ was added to constrain the effect of any single pattern. 
The improved version, $AvglogF$, as shown in Equation \ref{eq:2}, was therefore adopted.
Even so, if one candidate  $ c $  is extracted by a small number of high-scored patterns (large $logF$), it is still prone to be overrated. 
Our preliminary experiments showed that this bias still occurred during candidate estimation. 
For example, totally unrelated tokens (e.g., ``\textit{kinds of}'') and  non-standard terms (e.g., ``\textit{g cone ,  }'' and ``\textit{e.g. (}'') were extracted by the same one pattern with a high value of $F_i$.
The latter error of ``\textit{g cone , }'', which may be caused by the preprocessing tools, may have existed even if we had used other text tools. 
We found that both terms were sometimes ranked higher on the basis of the evaluation by $AvglogF$ or $AvgF$.
It is easy to understand that, if the value of $P$ gets smaller while $F_i$ becomes greater, $AvglogF$ of one candidate $c$ would obtain a higher value using Equation \ref{eq:3}. 

Besides the candidate scoring function of Equation \ref{eq:3},  the pattern scoring function of Equation \ref{eq:1} may also cause the bias problem, that persists in the bootstrapping iteration.
In Step 1 of evaluating patterns, when the value of $F$ is large, the score of $p$ will also be large using Equation \ref{eq:1}.  
According to Steps 2 and 3 in Algorithm 1,  high-scored pattern $p$ is more likely to be placed into \textit{pattern\_pool} 
such that extractions from this pattern are put into \textit{candidate\_instance\_pool}. 
Then, in Step 4 of evaluating words in \textit{candidate\_instance\_pool}, the bias problem using Equation \ref{eq:3} will arise again.

Another issue caused by the bias problem would be the limited coverage of lexicons.
There are several possible reasons: 
\begin{inparaenum}[1)]
    \item the number of extraction candidates for each pattern is limited,
    \item the pattern pool has a limited increase of $l$ in each iteration, and 
    \item the candidate pool is updated with few high-scored patterns.
\end{inparaenum}
These limitations may restrict the ability of bootstrapping to explore a broad range of lexicons. 

The intuitive approach for alleviating the bias problem is to set a threshold for the number of patterns, i.e., to discard candidate words recalled by less than a specific number of patterns.  
Although several thresholds were tried in our preliminary experiments, there was no significant improvement when compared with $AvglogF$. 
Furthermore,  setting a good threshold value also has a problem. 
All in all, we can say that this intuitive method ``treats the symptoms rather than curing the disease.'' 
The above two types of candidates (``\textit{g cone}'' and  ``\textit{e.g. (}'') can essentially be seen as the \emph{noise} in pattern extraction. 
We can alleviate this bias problem by evaluating candidate words on the basis of collective evidence over a wide range of patterns rather than few high-scored patterns. 

We thus turn our attention to the related bootstrapping work. 
\textit{NoisyOR} is an effective technique used in \textit{Snowball} \cite{agichtein2000snowball} and in \textit{NOMEN} \cite{lin2003bootstrapped}, as introduced in \cite{vomlel2006noisy,DBLP:books/lib/JurafskyM09}. 
In contrast to $AvglogF$, which prefers clues from a small number of high-quality patterns, \textit{NoisyOR} considers the evidence on the quantity of patterns. 

Here,  we attempt to use \textit{NoisyOR} for candidate scoring with the following considerations: 
\begin{inparaenum}[1)]
    \item  the confidence of each pattern, $conf$, is represented in a probability form, and 
    \item  \emph{all} related patterns are considered. 
\end{inparaenum}
\begin{equation} \label{eq:4}
NoisyOR(c) = 1- \prod_{i=1}^{P}( 1- conf(p_i) ),
\end{equation}
where $p_i$ is a pattern, and $P$ is the number of patterns from which candidate $c$ is extracted. 
The confidence of each pattern, $conf$, can be described as $ conf(p_i) =  F_i/ N_i$, similar to Equation \ref{eq:1}.
Given \textit{NoisyOR}, the acceptance of candidate $c$ is based on the backing of as many patterns as possible.
This metric prevents the ranking and selection from being easily biased to the lexicon selected by high-confidence patterns, as in the cases with $AvglogF$. 
In this work, we utilize $NoisyOR$ as an alternative method for evaluating candidates, besides the baseline scoring function $AvglogF$ in Step $4$ of Algorithm \ref{algo:Basilisk}. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{\textit{AvglogF vs. NoisyOR}:}
The differences in these two candidate scoring mechanisms lie in the tendencies in their \emph{evaluation} and \emph{results}.  
In the evaluation, \textit{AvglogF} relies on the minority of patterns with higher $F$ values, while \textit{NoisyOR} depends on the majority of patterns with not lower scores. 
Consequently, the results of exploration also differ as in the following (See examples in Table \ref{table_example_extractions}): 
\begin{inparaenum}[1)]
    \item  \textit{AvglogF} mines more deeply, which results in more specific words related to one specific pattern, for example,  ``\textit{red pepper}'' and ``\textit{chili pepper}'' are connected to ``\textit{pepper}'', and     
    \item  \textit{NoisyOR} explores more broadly, producing more general words that are extracted by more patterns. 
\end{inparaenum}
These different features motivated us to combine the characteristics of both evaluation methods. 
We have tried to ensemble these two functions, but did not obtain the expected significant improvement.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 1
\begin{table}[t]
\caption{Example extractions obtained by \textit{AvglogF} and \textit{NoisyOR}.}
\label{table_example_extractions}
\input{06table01.tex}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proposed Methods}
\label{sec:ProposedMethods}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Candidate Scoring with AutoEncoder}
\label{ssec:Candidate_Scoring_with_AutoEncoder}

The above-mentioned candidate scoring methods, $NoisyOR$ and the baseline $AvglogF$, along with other bootstrapping systems, like \textit{WMEB} \cite{mcintosh2008weighted} and \textit{Espresso} \cite{pantel2006espresso}, evaluate instances by using the information from pattern confidence or co-occurrence between patterns and instances. 
These patterns can be seen as an \emph{interviewer} who judges candidates, and the above scoring mechanisms seek support from the  interviewers in the evaluation step. 
Another type of knowledge, instances acquired in previous iterations of bootstrapping, can be considered as \emph{peers} or \emph{predecessors}.
The previously extracted \emph{peer} words can also be directly used to evaluate the current patterns.

The characteristics of the acquired lexicon in the updating seed list are as follows:
\begin{enumerate}
	\item  Both the initial set of instances and the acquired instances in  the seed list can be seen as \textit{positive} samples belonging to the target semantic category.
	\item The vocabulary in the seed list is expanded over time.
	\item Seed lists from the different initial seed lists will be updated and acquired independently of each other. 
\end{enumerate}
To utilize this resource in the bootstrapping, one option would be to train a supervised classifier or regression model with the acquired lexicon.  
However, this requires   ``appropriate'' \textit{negative} labeled samples, which are hard to obtain in different bootstrapping iterations with a varying initial seed list. 
One trick is to input a \textit{negative} list as well as a \textit{positive} list \cite{agichtein2000snowball,mcintosh2010unsupervised,huang2010inducing}. 
While general negative instances (e.g., ``\textit{the}'' and ``\textit{a}'') cannot cover and reflect differences among patterns, too specific instances are only adaptive to a few patterns.  

Therefore, our motivation is to evaluate candidate instances only with positive seed instances. 
On the basis of the above motivation, we utilize a neural model called \emph{AutoEncoder} \cite{japkowicz1995novelty,hinton2006reducing}, which can be trained in an unsupervised manner. 
AutoEncoder is an unsupervised neural network that can complete training by relying only on input positive samples themselves.
The architecture of AutoEncoder is based on reconstructing the input \emph{data} at the output end through the pair of an encoder and decoder.
The difference between inputs and outputs, represented by the \emph{reconstruction} loss, can be used to measure the quality of the reconstruction. 
Given AutoEncoder and a seed list, we can take into account the first characteristic of a seed list in which its instances are all positive. 
With trained AutoEncoder, we then could examine whether a candidate new word is faithful to the original seed list, such that  the evaluation step can be completed in a totally unsupervised manner. 

The second characteristic of the lexicon is that its size is enlarged by iterations. AutoEncoder can not only boost training in an incremental mode but also acquire adaptability to different iterations. 
For the different initial seed list, we can also train independent models, such that a learned model can fit its own initial seed list.
Thus, AutoEncoder can match our objectives and the three characteristics of the seed list. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 2
\begin{figure}[b]
\begin{center}
\includegraphics{27-3ia6f2.eps}
\end{center}
\hangcaption{Architecture of AutoEncoder, represented as a bottleneck network: the encoder transforms \textit{inputs} into \textit{hidden} states in a low-dimensional space and the decoder reconstructs the inputs from the hidden states.} 
\label{fig:autoencoder}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The architecture of AutoEncoder is shown in Figure \ref{fig:autoencoder}. 
We first use feature vectors (learned from word embeddings) of instances as the \textit{input} at the bottom. 
Specifically, an input instance $c$ is transformed to one feature representation by averaging the embeddings of its words. 
Given an input instance $c$ and its reconstruction output $c'$, we use $r(c)$ and $r(c')$ to denote their feature representations, respectively. 
The input feature vector $r(c)$ is compressed into a \textit{hidden} state of a smaller number of dimensions.
Then, the \textit{output} layer tries to rebuild the input signal from the hidden state.
The network can be optimized by reducing the loss of reconstruction that computes the difference between reconstructed outputs and inputs.
After being trained with only positive instances, AutoEncoder can output positive instances with smaller reconstruction loss, which enables distinct features to be acquired from positive instances such that it is hard to reconstruct negative instances. 
The candidate scoring function with AutoEncoder can be defined as follows:
\begin{equation} \label{eq:autoencoder}
AE(c)=1- norm(reconstruct(r(c), r(c'))),
\end{equation}
where output $r(c')$ represents the reconstructed input, and the reconstruction loss is measured by  $reconstruct(,)$, for which we chose the mean squared error.
We use the $sigmoid$ function as the $ norm $ to output a probability value $AE(c)$. 
We can rank and select the better candidates with larger $AE(c)$ values using Equation \ref{eq:autoencoder}.
This value can also be used for the pattern scoring step, that we introduce in Section \ref{ssec:Pattern_Scoring} below. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Pattern Scoring with AutoEncoder}
\label{ssec:Pattern_Scoring}

As shown in Figure \ref{fig:basilisk_process} and Algorithm \ref{algo:Basilisk}, all candidates come from the candidate pool acquired on the basis of the pattern pool, which is determined during the pattern scoring step. 
Therefore, if low-quality patterns are selected, credible results are hard to obtain even when there is a better candidate assessment metric. 
We hypothesize the following:  

\textbf{Hypothesis:}  \textit{Better pattern evaluation results in better candidate selection, and so the pattern scoring function contributes to improving the performance in candidate selection.}

Therefore, our motivation is to modify the pattern scoring function for better pattern evaluation. 
Reviewing the first step of Algorithm \ref{algo:Basilisk}, the score for each pattern  $p$ is computed by Equation \ref{eq:1}. 
Here, we rewrite it as follows: 
\begin{equation}
RlogF(p) = F / N * log(F)=R * logF  \quad (Rewriting),
\end{equation}
where $ R =  F / N$ denotes the ``reliability,''  which computes the correct probability of extracting pattern $p$, while $logF = log(F)$ measures the potential ``productivity.''  
The characteristics of $RlogF$ are:
\begin{enumerate} 
	\item ``Reliability'': $R =  F / N $  assumes that all extracted instances other than previous seed instances are \textit{false positives}.
	\item ``Productivity'': $logF = log(F)$  is not a probability. 
	\item ``Combination'': $RlogF$ combines   $R$ and $logF$ by a ``multiplication.''
\end{enumerate}
First, we attempt to incorporate \emph{AutoEncoder} (See Section \ref{ssec:Candidate_Scoring_with_AutoEncoder}) to guide the calculation of  $R =  F / N$. 
As we know, $\mathcal{N}$ consists of the numbers of correctly extracted seed instances $ \mathcal{F} $ and other instances whose correctness is unknown, i.e., $ \mathcal{N}= \mathcal{F}  \cup  Unk $ ($Unk$ is unknown instances extracted by this pattern.).
It is ill-advised to regard all the unidentified ones as negative when calculating $R =  F / N $, which is the ratio between the number of correctly extracted seed instances $ F $ and  $N$.
Therefore, for each unknown candidate $c$ in $Unk$, $1 - AE(c)$ is incorporated to score the probability of the instance being a  ``\textit{false positive}.''
The formula of $R$ could be replaced by $autoR$ to evaluate the ``reliability'' of a pattern: 
\begin{equation} \label{eq:Ri}
autoR =    F / (F +    \sum\limits_{c \in  Unk} ( 1- AE(c) )  ).
\end{equation}
Second, we replace $log(F)$ with a new measure, $ L= F / |\mathcal{S}| $, where $|\mathcal{S}|$  denotes the size of the updated seed list $\mathcal{S}$.
Now, the ``productivity'' is represented as  $ L $, which is a probability that agrees with the ``reliability.'' 
Finally, we  combine the previous two metrics, $autoR$ and $L$. 
Rather than ``multiplying'' the two metrics, as $RlogF$, a more balanced combination operation called \textit{harmonic mean} can be used: 
\begin{equation}\label{eq:newpattern}
autoRL(p) = 2* autoR * L / ( autoR  + L ), 
\end{equation}
where  $ autoR $ and $L$ are defined as above. Similar to the F1 measure, the \textit{harmonic mean} is a metric for averaging two measures.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Summarizing Proposed Methods}
\label{Our_methods}

We summarize our proposed methods in accordance with the motivations presented above. 
Our methods, as shown in Figure \ref{fig:basilisk_process}, utilize the basic framework of Basilisk-like bootstrapping and modify its two key steps.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Candidate scoring}
\label{Candidate_scoring_method}

To evaluate candidate instances, we modify $AvglogF$ (Equation \ref{eq:2}) or another baseline 
\linebreak
$NoisyOR$ (Equation \ref{eq:4}), adapted in the other bootstrapping systems, to AutoEncoder ($AE$) in the candidate scoring step:
$$AE(c)=1- norm(reconstruct(r(c), r(c'))). $$ 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Pattern scoring}
\label{Patternscoring_summary}

As described in Section \ref{ssec:Pattern_Scoring}, we substitute $RlogF$ with $autoRL$ and combine the two new probabilistic metrics, $autoR$ and $L$, that represent ``reliability'' and ``productivity,'' respectively: 
$$autoRL(p) = 2* autoR  * L  / ( autoR  + L  ).$$
The above formula is used as the new pattern scoring function in Step 1 of bootstrapping. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experiments}
\label{sec:Experiment_section}

In this section, we first introduce the data, pre-processing, and evaluation metrics. We then show the experimental results and their analysis.
We also perform ablation studies to understand the behavior of each component in our methods.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Data and Preprocessing}
\label{ssec:data_process}

The objective of this work is to acquire knowledge  in an unsupervised bootstrapping manner from an unannotated text corpus.
Generally, there are three kinds of corpora that can be used:   
\begin{inparaenum}[1)]
    \item A domain specific corpus, such as a biomedical corpus \cite{emnlp-2019-bionlp} or medical text data \cite{aramaki:book}. This kind of dataset contains authoritative source of domain information, though it is expensive to obtain it.  
    \item Social  media text data, such as Twitter,  have a lot of non-standard language content and are hard to process \cite{AAAI1510016}. 
    \item  A corpus of a general domain (e.g., Wikipedia) contains diverse knowledge and standard language texts.
\end{inparaenum}
Here, we prefer to acquire semantic lexicons from the general corpus of Wikipedia, rather than the other two corpora, based on the following considerations: 
\begin{inparaenum}[1)]
    \item This general corpus has a stable text form and diverse coverage.
    \item We would like to acquire lexicons for a specific domain from a general corpus and explore other domains in the future.
\end{inparaenum}
As for the choice of the \emph{food} domain, we thought food is a good topic for a chat dialogue systems because eating food is a daily activity, and there are a variety of foods \cite{kobori-etal-2016-small}.
Furthermore, there are no comprehensive standard database for foods unlike movies. 
So if we try to build a dialogue system in the food domain, we need to create a list of foods. 
In addition, since the food domain is large \cite{nakano2019framework}, we believe a bootstrapping method that works for the food domain will also work for other domains.
Since we used a \textit{conjunction} pattern, the dataset was preprocessed by a spaCy$2$ pipeline, including a tokenizer and a noun phrase chunker \cite{spacy2}. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Evaluation Metrics}
\label{ssec:evaluation_metrics}

We evaluated the system performance in terms of Precision, Recall, and F1-measure (F1).
Precision is defined as the ratio of correct instances in all the extracted instances.   
Each extracted instance was manually evaluated by inspecting whether it was correct.   
For Recall, we calculated two different values with a small and large list of correct instances. 
The small list with 68 instances consisted of more single-token instances.
The large list with 457 instances consisted of more noun phrases.
Recall values were the ratio of the number of instances in the lists that can be acquired in the bootstrapping.
Therefore, two recall metrics were recorded: Recall (small) and Recall (large). 
As F1 considers both the precision and the recall, we have two corresponding F1s: F1 (small) and F1 (large).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental Settings}
\label{ssec:experimental_setting}

All experiments were performed using ten initial seed instances. 
In each iteration, top-$(20+l)$ patterns were added to the pattern pool. 
The top-$5$ best candidate instances were then added to the expanded seed list for the next iteration. 
For the inputs for the AutoEncoder model, we used Glove embeddings ($300$ dimensions) trained on Common Crawl \cite{pennington2014glove}.\footnote{http://nlp.stanford.edu/projects/glove/}  
We transformed each instance to an input vector by averaging the embedding vectors of its  words. 
Each input to AutoEncoder was compressed to a hidden layer of $100$ dimensions.     
Sigmoid was selected as the decoder activation to reconstruct inputs.  
The mean squared error (MSE) loss was optimized by the Adam algorithm \cite{kingma2014adam}. 
For each training phase, AutoEncoder was trained with the early stopping strategy with the maximum number of epochs ($128$).  
Because bootstrapping approaches can be easily influenced by different input seed instances \cite{mcintosh2008weighted,DBLP:journals/aim/RiloffJ18}, 
we evaluated the performance with five different initial seed lists for all compared bootstrapping systems for $20$ iterations.   
For comparison, all the results for the methods were the average over the five seed lists.   
All seeds were collected by employees in the organization to which the second author belongs. 
Table \ref{table:seed_lists} lists the seed terms we used. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 2
\begin{table}[t]
\caption{Five seed lists}
\label{table:seed_lists}
\input{06table02.tex}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 3
\begin{table}[t]
\caption{Results for candidate scoring}
\label{table:table_score_candidates}
\input{06table03.tex}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental Results and Analysis}
\label{ssec:experimental_results}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Candidate scoring}

First, we compared our AutoEncoder-guided scoring function with the two baseline methods: $AvglogF$ and $NoisyOR$. 
As shown in Table \ref{table:table_score_candidates}, $NoisyOR$ outperformed $AvglogF$ in all five metrics. 
$AE$, with AutoEncoder, outperforms both the previous baseline systems. As for F1, $AvglogF$ and $AE$ obtained higher scores for F1 (large) than for F1 (small). In contrast, $NoisyOR$  achieved higher scores for F1 (small) than for F1 (large). 
This may be due to its preference for single-token instances of which the small list consists. $NoisyOR$ evaluates candidates by collecting evidence from a larger range of patterns, and so extracts more general single-token instances. 
In Figure \ref{fig:metric_iteration}, we can track five metrics as bootstrapping progresses. 
We see that our proposed approach $AE$ significantly outperforms other methods in both F1 metrics over different iterations. 
This figure also display a continuous phenomenon of bootstrapping learning, which is the continuing decrease of precision and the increasing trend of recall. 
In summary, our AutoEncoder-based candidate scoring function improved the overall performance compared with the two baseline methods.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 3
\begin{figure}[t]
\begin{center}
\includegraphics{27-3ia6f3.eps}
\end{center}
\caption{Metrics after each bootstrapping iteration}
\label{fig:metric_iteration}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Pattern scoring}
\label{sssec:pattern_scoring}

This subsection investigates the performance of our new pattern scoring function $autoRL$, to validate \textbf{Hypothesis} and our motivation  in Section \ref{ssec:Pattern_Scoring}. In the experiments, we used the same baseline candidate scoring functions ($AvglogF$ and $NoisyOR$) and modified the pattern evaluation function. 

As shown in  Table \ref{table:score_patterns}, $autoRL$ improved the  performance, especially for F1 (small), which increased to $0.232$. 
The same scale of improvement (from $0.165$ to $0.253$) was also achieved for F1 (large) for the method with $NoisyOR$, at the cost of a slight precision drop.  
Precision was affected, especially for the $AvglogF$ method.   
In part, this is because of the bias problem, which shows that candidate instances are more likely to be extracted by few high $RlogF$ patterns with large number of extractions $\mathcal{F}$. 
When we changed $RlogF$ to $autoRL$, more patterns could contribute to the candidate pool.
Instead of having to do evaluation in a narrow range, this change brings to the candidate scoring function $AvglogF$ a larger range of candidate words. 
Thus, this is beneficial to improving recall scores. 
However, the inclination of $autoRL$ to patterns with fewer extractions caused a decrease of precision in $AvglogF$. 
For $NoisyOR$, which considers pattern supports as much as possible to alleviate the influence from few patterns, these changes had a larger impact on precision than $AvglogF$.
To summarize, Table \ref{table:score_patterns} demonstrates that the overall performance of both the baseline methods in candidate scoring could be enhanced by using $autoRL$ in pattern scoring.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 4
\begin{table}[b]
\caption{Results for Pattern Scoring}
\label{table:score_patterns}
\input{06table04.tex}
\vspace{4pt}\small
$autoRL + AvglogF$ denotes that $autoRL$ is used for pattern evaluation, and candidate scoring still uses $AvglogF$. $autoRL+NoisyOR$ represents $autoRL$ plus $NoisyOR$. Best scores are in bold. 
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 5
\begin{table}[b]
\caption{Impact of each part in pattern scoring function}
\label{table_ablation_study_large}
\input{06table05.tex}
\vspace{4pt}\small
``---'' indicates that we did not obtain any result. Bold numbers indicate the best F1 scores. 
We use the index column for clarity.
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Ablation study: Impact of each part in pattern scoring function }
\label{sssec:ablation_study_1}

To assess the contribution of each part in our new pattern scoring method, we performed an ablation study. 
Table \ref{table_ablation_study_large} summarizes the results in F1 scores. 
In Basilisk's original formula $RlogF(p) = R * logF$, $R$ represents ``reliability,'' and $logF$ measures ``productivity.'' % in the rightmost.
They are combined by the ``multiply'' operation. 
Therefore, our $autoRL$ (Equation \ref{eq:newpattern}) modifies three parts of $RlogF$. 
More specifically, we can replace $R$ with $autoR$ for ``reliability'' and  $ L= F / |\mathcal{S}|  $ for ``productivity.'' 
Finally, harmonic mean, instead of ``multiply,'' can be used to combine ``reliability'' and ``productivity.''
In this ablation study, we kept the basic \textit{Basilisk}   framework and investigated the contribution of the changes in ``productivity,'' ``reliability,'' and their combination. 
Because $R$ and $autoR$ are in the form of probability  while $logF$ is not, we do not show its score in the \textit{Harmonic} cell.

In Table \ref{table_ablation_study_large}, the numbers in the last two columns denote F1-scores for the small and large lists for different combination operations including ``multiply'' and ``harmonic mean,'' respectively.
Index $0$ denotes the initial pattern scoring function $RlogF$, while indexes 1--3 denote three ablation studies.
The first adjustment is $autoR$, % with an index of 1, 
which is a new reliability metric based on AutoEncoder. It significantly outperformed $R$, multiplied by $logF$ (index $0$). 
Specifically, F1 (small) increased from $0.119$ to $0.176$, and F1 (large) increased from $0.147$ to $0.192$. 
By changing ``productivity'' to $L$, $R*L$ also achieved a better F1 (small) score than $RlogF$, as shown in the third row (index $2$). 
However, it could not boost $logF$ in F1 (large), which remained at $0.147$. 
As for index $3$, where both parts were modified, $autoR$ multiplying $ L $  obtained a comparable F1 (small) result ($0.151$) to $R$ multiplying $ L$ ($0.149$) and a significantly higher F1 (large) result ($0.199$). 
The last four columns for F1 show that replacing ``multiply'' with ``harmonic mean''  also improved performance. 
The results for ``harmonic'' were around 0.056--0.08 in F1 (small) and 0.014--0.035 in F1 (large) higher than those for ``multiply.''
Therefore, in the combination operation, harmonic mean is a better choice than multiplying ``reliability'' and ``productivity.''
Comparing the two adjustment methods, the improvement of $autoR$ over $R$ demonstrates the benefit of AutoEncoder in improving the representation of ``reliability.'' Overall, our proposed pattern scoring method enhanced the performance on the basis of the contribution of the multiple different parts. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 6
\begin{table}[b]
\caption{Impact of  the training data size}
\label{table:ablation_study_data_augmentation_all}
\input{06table06.tex}
\vspace{4pt}\small
``Step'' indicates in which step we used augmented training data.  ``Aug\_Inst'' denotes the augmented data. ``Basic\_Inst'' denotes the basic seed list. Bold numbers denote the \textbf{better} scores in each row comparison (``Basic\_Inst'' vs ``Aug\_Inst'').
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Analysis: Impact of the size of the training data for AutoEncoder}
\label{sssec:ablation_study_2}

We performed an analysis to investigate the effect of the training data size for AutoEncoder. 
The results are reported in Table \ref{table:ablation_study_data_augmentation_all}. 
Here, $100$ additional human-crafted positive instances were added to the training set with each initial seed list.  
We report the influences on F1 (small) and F1 (large) on the basis of the two types of training data: the original data ($10$ seed instances) and the augmented seed list with extra examples ($110$ instances).
The first column, ``Step,'' denotes in which step the augmented training data was used among the two steps in Basilisk: pattern scoring and candidate scoring.  
In ``Pattern Scoring,'' we tested two baseline methods for candidate scoring: $AvglogF$ and $NoisyOR$. 

The performance was improved with the augmented data for $AvglogF$. 
Table \ref{table:ablation_study_data_augmentation_all} shows that F1 (small) increased from $0.232$ to $0.252$ and F1 (large) increased from $0.213$ to $0.235$ when the augmented data was used.
In contrast to $AvglogF$, it is more beneficial to train AutoEncoder only with Basic\_Inst than with Aug\_Inst in using with $NoisyOR$. 
The performances for $NoisyOR$ $+$ $AE$ degraded when more training instances were used, as shown in the second row from the bottom.  
This degradation makes us consider whether adding much more training examples ($110 > 10 $) will offset the influence of different initial seeds and the meaning of increasing new instances in bootstrapping \cite{mcintosh2009reducing}.  
Random selection of augmented data might cause a biased set of training instances, that resulted in a performance degradation. 
Additionally, in the original setting, the five seed lists and the corresponding AutoEncoder were trained independently. 
Here, we directly add Aug\_Inst for \textit{all} seed lists to train. This might dismiss the adaptability of AutoEncoder to each independent initial seed list, as shown in the third characteristic of a seed list (See Section \ref{ssec:Candidate_Scoring_with_AutoEncoder}). 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 7
\begin{table}[b]
\caption{Sample results of different methods}
\label{table:case_study_example}
\input{06table07.tex}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Case study}
\label{sssec:case_study}

Here, we present successful and erroneous example outputs for a case study in Table \ref{table:case_study_example}.
In each column, seven good and three bad example words extracted by one of the approaches are listed from top to bottom. 
As mentioned in Section \ref{sec:preliminary_background}, the results of $AvglogF$ and $NoisyOR$ were quite different. 
$AvglogF$ tended to choose related noun phrases from few patterns, while $NoisyOR$ preferred to explore more general words in the candidate pool, which can be observed from the columns of $AvglogF$ and $NoisyOR$.
Even though $NoisyOR$ achieved higher accuracy than $AvglogF$, its extractions have two disadvantages: 1) extractions (e.g., ``\textit{cashew}'') did not have much semantic relatedness with its seed list, and 2) it could not extract more specific words,  (e.g., ``\textit{chinese cabbage},'' ``\textit{chili pepper}''), as $AvglogF$ did. 
If we had used the method $AE$, which was introduced in Section \ref{ssec:Candidate_Scoring_with_AutoEncoder}, the results could have been more balanced by taking both general (e.g., ``\textit{food},'' ``\textit{fish}'') and specific words (e.g., ``\textit{instant noodle},'' ``\textit{tomato sauce}'') into account. 

Next, when  $autoRL$ was incorporated into the step of pattern scoring, both of $AvglogF$ and $NoisyOR$ have benefited from the diverse candidate pool. 
From the column of $autoRL+AvglogF$, it can be observed that $AvglogF$ obtained from a large range of words including stable diet (``\textit{toasted rice}''), drinks (``\textit{melon soda}''), and meat (``\textit{mince beef},'' ``\textit{fry chicken}''), rather than being restricted to the small vocabulary of  ``\textit{melon}'' and ``\textit{pepper}.''
The last column shows a similar effect for $NoisyOR$. 
Even though $autoRL+NoisyOR$ still extracted as many general words as the column for $NoisyOR$, the new pattern scoring step $autoRL$ enabled $NoisyOR$ to choose from a large vocabulary which was related to the food domain. 
For example, it contains drink-related tokens  (``\textit{milk},'' ``\textit{wine}''), seasonings (``\textit{salt}'') and specific tokens (``\textit{sugar cane}'').

Lastly, we summarize the erroneous sample outputs in the bottom of Table \ref{table:case_study_example}. 
The errors caused by pre-processing tools may appear in various methods, e.g., ``\textit{five kind},'' ``\textit{a variety}'',
``\textit{production \u013}''. 
More important errors would be erroneous tokens extracted by different methods.
As for $AvglogF$, its erroneous examples (e.g., ``\textit{e.g. (}'', ``\textit{marigold petal}'') were caused by the bias problem and its \emph{average} strategy, as mentioned in Section~\ref{sec:preliminary_background}. 
For $autoRL + AvglogF$, similar errors to $AvglogF$ may still exist, e.g.,``\textit{woolen product}'', which was also extracted by few high-scored patterns when using the \emph{average} strategy of $AvglogF$. 
As for $AE$, an example of ``\textit{peach tree}'' has semantic relatedness with several fruits (e.g., ``\textit{orange},'' ``\textit{blueberry}'') obtained in the previous bootstrapping iterations,  
while it can be more likely to be in the domain of \textit{plants} rather than \textit{food}.
``\textit{Wood}'' and ``\textit{gold}'' are similar erroneous examples in the methods of  $NoisyOR$ and $autoRL + NoisyOR$, where both words were easily extracted by more patterns when $NoisyOR$ was used.   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}

In this paper, we  presented methods for improving the bootstrapping of a semantic lexicon that uses AutoEncoder to better evaluate candidate instances.
The experimental results, including ablation studies, validated the effectiveness of the proposed methods. 
By training AutoEncoder with the updated seed lists,  we could provide a better candidate scoring function. 
Additionally, a more balanced pattern evaluation function, guided by AutoEncoder, also improved the overall performances.
This verified the hypothesis that a better candidate pool would be beneficial.
In future work, we plan to incorporate more knowledge into our methods for bootstrapping.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\acknowledgment

This paper is a revised version of \cite{hu2019autoencoder}, 
which was published in the proceedings of the 16th Pacific Rim International Conference on Artificial Intelligence (PRICAI-2019).
The revised version has been extended with at least $30\%$ extensions.
Chenlong Hu acknowledges China Scholarship Council (CSC). 
%The extensions include a rewritten introduction, an added section regarding related work, fixing writing errors, newly added materials, etc.
The authors would like to gratefully acknowledge the editors and anonymous reviewers for their helpful comments and suggestions.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{jnlpbbl_1.5}
\bibliography{06refs}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{biography}

\bioauthor[:]{Chenlong Hu}{%
From 2015, he has been a PhD candidate at  Department of Information Processing, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology. 
Before that, he received M.E. from Xidian University, Xi'an. 
His research interests include natural language processing and machine learning.
}

\bioauthor[:]{Mikio Nakano}{%
Mikio Nakano received his M.S. degree in Coordinated Sciences and Sc.D.
degree in Information Science from the University of Tokyo, respectively
in 1990 and 1998.  He joined Nippon Telegraph and Telephone Corporation
in 1990. From 2004 to 2020, He worked for Honda Research Institute Japan
Co., Ltd. In 2020, he established C4A Research Institute Inc., where he
is the Chief Executive Officer. His research interests include dialogue
systems and spoken language understanding. He is a member of JSAI, IPSJ,
IEICE, ACM, and ACL.
}
\bioauthor[:]{Manabu Okumura}{
Manabu Okumura was born in 1962. 
He received B.E., M.E. and Dr. Eng. from Tokyo Institute of Technology in 1984, 1986 and 1989 respectively. 
He was an assistant at the Department of Computer Science, Tokyo Institute of Technology from 1989 to 1992, and an associate professor at the School of Information Science, Japan Advanced Institute of Science and Technology from 1992 to 2000. 
He is currently a professor at Institute of Innovative Research, Tokyo Institute of Technology. 
His current research interests include natural language processing, especially text summarization, computer assisted language learning, sentiment analysis, and text data mining.
}
\end{biography}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\biodate



\end{document}

