\documentclass[english]{jnlp_3.5}
\usepackage{jnlpbbl_2.2}
\usepackage[dvipdfmx]{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}
\usepackage{hangcaption_jnlp}
\usepackage{array}
%%%%\usepackage{udline}
%%%%\setulminsep{1.2ex}{0.2ex}
%%%%\let\underline=\ul
\allowdisplaybreaks

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% author's definition
\usepackage{multirow}
%%%%\usepackage{subcaption}
%%%%\usepackage{xcolor}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\Volume{29}
\Number{3}
\Month{September}
\Year{2022}
%%%%\Issuetitle{Special Issue: XXXXXXXX}

\received{2021}{11}{25}
\revised{2022}{2}{28}
%%%%\rerevised{2006}{5}{6}
\accepted{2022}{4}{13}

\setcounter{page}{785}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\esubject{General Paper}
\etitle{A Simple and Effective Usage of Word Clusters \\
	for CBOW Model}
\eauthor{Yukun Feng\affiref{Author_1} \and Chenlong Hu\affiref{Author_1} \and Hidetaka Kamigaito\affiref{Author_1} \and Hiroya Takamura\affiref{Author_2} 
\and \\ Manabu Okumura\affiref{Author_1} } 
\eabstract{%
We propose a simple and effective method for incorporating word clusters into the Continuous Bag-of-Words (CBOW) model. Specifically, we propose replacing infrequent input and output words in CBOW with their clusters. The resulting cluster-incorporated CBOW model produces embeddings of frequent words and a small amount of cluster embeddings, which will be fine-tuned in downstream tasks. We empirically demonstrate that our replacing method works well on several downstream tasks. Through our analysis, we also show that our method is potentially useful for other similar models that produce word embeddings.
}
\ekeywords{Word Embeddings, Continuous Bag-of-Words, Word Cluster, Negative Sampling}

\headauthor{Feng et al.}
\headtitle{A Simple and Effective Usage of Word Clusters for CBOW Model}

\affilabel{Author_1}{}{Tokyo Institute of Technology}
\affilabel{Author_2}{}{National Institute of Advanced Industrial Science and Technology (AIST)}


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

\maketitle

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

Word embeddings have been widely applied to various natural language processing (NLP) tasks. These embeddings can be pretrained on a large corpus and carry useful semantic information. One of the most well-known methods for obtaining word embeddings is based on Continuous Bag-of-Words (CBOW), \cite{mikolov2013efficient} and there have been many research efforts to extend it. Although current contextualized word representations such as ELMO \cite{peters-etal-2018-deep}, BERT \cite{devlin-etal-2019-bert}, and RoBERTa \cite{liu2019roberta} are known to be more powerful, these context-independent word embeddings are much faster to use and easier to train on large-scale corpora. This may be one reason that the field is still active \cite{burdick2020analyzing,du2021assessing}.

In this paper, we focus on incorporating word clusters into the CBOW model. Each word cluster consists of words that function similarly. By aggregating such words, we can alleviate data sparsity, even though each of the words is infrequent. Over the past few years, word clusters have been applied to various tasks, such as named-entity recognition \cite{ritter2011named}, machine translation \cite{wuebker2013improving}, and parsing \cite{kong2014dependency}. Many word clustering algorithms can be applied to a raw corpus with different languages to help us obtain word clusters easily without additional language resources.

In our method, we keep only very frequent words and replace the other words with their clusters for both input and output words in the CBOW model. This is motivated by the fact that word clusters are more reliable than infrequent words (\citeA{turian-etal-2010-word} drew similar conclusions from their experiments). Thus, only very frequent word embeddings and a small amount of cluster embeddings are produced as the output. We apply these learned word embeddings and cluster embeddings to the fine-tuning of downstream tasks. At the beginning, the embeddings of infrequent words within one cluster are initialized by the same embedding of their cluster and are then updated differently in accordance with their context.

For obtaining word clusters, part-of-speech (POS) tags or other supervised classes \cite{samuelsson1999class}) have typically been used in existing studies. However, finding POS taggers or other supervised classes for many languages is inconvenient. This is particularly the case in word representation learning tasks. For example, \citeA{grave-etal-2018-learning} trained word vectors on 157 languages and \citeA{heinzerling2018bpemb} trained subword vectors on 275 languages. Thus, we propose the use of a language-independent word clustering algorithm to obtain word clusters. We also consider eight typologically diverse languages in our languages to verify the effectiveness of this approach. Specifically, we obtain word clusters in this work through the ClusterCat software \cite{dehdari-etal2016},\footnote{\url{https://github.com/jonsafari/clustercat}} which is implemented using the bidirectional, interpolated, refining, and alternating (BIRA) predictive exchange algorithm. We choose this method because it is demonstrably faster than many other word clustering methods. For example, it can produce 800 clusters on one billion English tokens in just 1.4 hours while Brown clustering software,\footnote{\url{https://github.com/percyliang/brown-cluster}} mkcls software\footnote{\url{https://github.com/moses-smt/mgiza}} and Phrasal software\footnote{\url{https://github.com/stanfordnlp/phrasal}} take 12.5 hours, 48.8 hours and 5.1 hours respectively \cite{dehdari-etal2016}. When applying this word clustering algorithm, we use only the training data of a specific downstream task. In other words, we do not require an additional language corpus.

Using standard tasks (e.g., word similarity tasks) to evaluate these learned embeddings is not suitable, as many infrequent words within one cluster share the same embedding. Instead, we examine the performance for frequent words separately on five word similarity tasks. However, only a subset of word embeddings can be evaluated in this way. To evaluate all learned embeddings, we mainly focus on evaluations using downstream tasks, which involves the fine-tuning of word embeddings. For the downstream tasks, we choose language modeling (LM) tasks, which are fundamental tasks in NLP, as well as two machine translation (MT) tasks. To investigate the effect of word clusters across different languages, eight typologically diverse languages are further selected for the LM task. An analysis is also provided for our method. Finally, we show that our method can be easily applied to large-scale corpora. In summary, our method\footnote{Our code is available at \url{https://github.com/yukunfeng/cluster-cbow}} can be used to:
\begin{itemize}
\item
improve the embeddings of both frequent and infrequent words (Sec. \ref{sec:motivation_rein}, Sec. \ref{sec:word_sim}, and Sec. \ref{sec:targeted_ppl}),
\item
reduce the number of word embeddings before fine-tuning, or equivalently reduce the parameters when training word embeddings (Sec. \ref{sec:word_sim}, Sec. \ref{sec:lm_in_diverse}, and Sec. \ref{sec:large_scale_exp}), and
\item
make CBOW training more effective (Sec. \ref{sec:ablation}).
\end{itemize}



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

A number of related studies have attempted to learn better word embeddings from different aspects. For example, \citeA{neelakantan2015efficient} proposed an extension that learns multiple embeddings per word type. \citeA{ammar2016massively} proposed methods for estimating embeddings for different languages in a single shared embedding space. There has also been a lot of work that incorporates the internal information of words, such as character-level information \cite{chen2015joint,bojanowski2017enriching} and morpheme information \cite{luong2013better,qiu2014co}. Our research aims at another aspect and focuses on incorporating word clusters into the CBOW model, which has not been studied before.

There have also been previous studies that utilize word clusters for reducing the number of word embeddings. \citeA{Botha2017NaturalLP} used word clusters to reduce the network size for the part-of-speech tagging task. \citeA{shu2018compressing} attempted to compress word embeddings without losing performance by constructing the embeddings with a few basic vectors. Our goal is different in that we attempt to learn better word embeddings and do not aim at reducing the parameters when our embeddings are fine-tuned in downstream tasks. Nonetheless, the reduction of the number of word embeddings from the CBOW model before fine-tuning is still one of our goals, as we can save space to store these embeddings and reduce the time to download them. For example, Google News Vectors have around 3 million words, and we only need around 20\% of the number of the word embeddings if we choose 600K most frequent words and 10K word clusters in our method.

A similar idea of using word clusters has also been used in the LM field, and it is often referred to as the class-based language model  \cite{brown1992class,ward1996class,samuelsson1999class}. The main difference is that our task does not need to compute the probability of a word given some histories like a language model, which gives rise to two main specialties. First, for input words, our proposal does not keep infrequent words and only uses their clusters. This results in a significant reduction in the number of word embeddings to be stored. This is not possible in a class-based language model, as two input words must be distinguished if they are in the same cluster; otherwise, the model may produce the same probability given many different input words. Second, for output words, our proposal does not keep infrequent words, and their clusters are used instead, as described above. This makes the training effective, as the model does not need to learn with many infrequent words. A class-based language model must still learn with infrequent words to compute the probability over such words. Another difference with conventional approaches is that the word clusters in our work are used only in two steps: training in the CBOW model and fine-tuning in downstream tasks. After these two steps, the word clusters will not be used. For a model of a specific downstream task, there are no word clusters involved in inference time, while for a class-based language model, the word clusters are still required in inference time.

One advantage of the method's simplicity is that it can be applied to large-scale corpora to avoid huge computational cost. This is particularly advantageous in the area of word representation learning, where we can easily obtain large-scale unlabeled corpora for training word embeddings. For example, \citeA{bojanowski2017enriching} proposed encoding subword information of a word to enhance the word representations. They simply aggregated the embeddings of character n-grams instead of a more powerful encoder (e.g., long short-term memory (LSTM)), to encode words on the Wikipedia corpus. \citeA{grave-etal-2018-learning} simply added position weights in the CBOW model to better capture positional information on common crawl and Wikipedia corpus. From this aspect, our work is similar to the above mentioned works. Although the adopted strategy is simple, it can be easily applied to large-scale corpora, which is a practical setting, as we demonstrate through our experiments.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proposed Method}
\label{mode_descrip}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{CBOW Model}

Let $w_{t}$ denote the $t$-th word in a given text. 
\pagebreak
We adopt the basic CBOW model architecture for learning word embeddings. It predicts the output word $w_{t}$ given the input words in the window that precede or follow the output word. As an example, when the window size is 2, the input words are $w_{t-2}, w_{t-1}, w_{t+1}, w_{t+2}$. We respectively denote the input and output embeddings of word $w_{i}$ as $\vec{x}_{i}$ and $\vec{o}_{i}$. The CBOW model computes the hidden representation as follows:
\begin{equation}
 \vec{h} = \frac{1}{2c} \sum^{c}_{i=-c, i\neq 0} \vec{x}_{t + i},
 \label{eq:h1}
\end{equation}
where $c$ is the window size. We use negative sampling \cite{mikolov2013distributed} to train the CBOW model by maximizing the following objective function:
\begin{equation}
 \label{eq:neg}
 \textrm{log}\sigma( \vec{h}^{T} \vec{o}_{t} ) + \sum^{k}_{j=1} \textrm{log}\sigma(-\vec{h}^{T} \vec{o}^{j}),
\end{equation}
where $k$ is the size of the negative sample, $\vec{o}^{j}$ is the $j$-th noise word embedding, and $\sigma$ is the sigmoid function. Each word in the negative sample is drawn from the unigram distribution.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 1
\begin{figure}[b]
\begin{center}
\includegraphics{29-3ia2f1.pdf}
\end{center}
\hangcaption{CBOW architecture with our replacing method for input and output words trained with negative sampling. $w_{t-2}$, $w_{t+1}$, $o^{1}$, and $o^{3}$ are infrequent words.}
\label{fig:cluster_cbow}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Replacing Methods}

As a method for incorporating word clusters, we propose replacing infrequent words with their clusters for the input and output. The architecture is shown in Fig. \ref{fig:cluster_cbow}. Our approach is motivated by the intuition that the embeddings of clusters will be more reliable than those of infrequent words. We denote the embedding of the cluster for word $w_{t+i}$ as $\vec{d}_{t+i}$. We present the following two replacing methods:
\begin{itemize}
\item
\textbf{ReIn}: In the input, $\vec{x}_{t + i}$ in Eq. (\ref{eq:h1}) will be replaced with $\vec{d}_{t+i}$ if the frequency of $w_{t+i}$ is less than a threshold $f_{in}$.
\item
\textbf{ReOut}: In the output, output words whose frequency is less than $f_{out}$ are replaced with their clusters. Thus, in negative sampling, a noise word will be sampled from clusters and frequent words.
\end{itemize}

As with the standard CBOW model, we use the input word embeddings and input cluster embeddings for downstream tasks. Thresholds $f_{in}$ and $f_{out}$ are set to 100 in all experiments.\footnote{These values are different for the large-scale corpus mentioned later.} Due to this large value, each cluster contains many infrequent words that share the same embedding. We use the above two methods together, which we call \textbf{Cluster-CBOW}, in the following experiments.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Motivations of ReIn and ReOut}
\label{sec:motivation_rein}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Motivation of ReIn.}
As the embeddings of clusters are learned by aggregating many infrequent words, they are more robust than the embeddings of the infrequent words. During the fine-tuning process for a downstream task, the embeddings of infrequent words are first initialized with the embeddings of their clusters. As most of these infrequent words appear only a few times, these embeddings will not be updated far away from each other within one cluster. (The visualization of these embeddings before and after fine-tuning is discussed later in Sec. \ref{sec:visualization}.) As a result, these embeddings for infrequent words become more reliable because originally, most infrequent word embeddings are updated only several times and are not far away from where they were randomly initialized. Because the context of frequent words becomes less noisy by replacing all the infrequent words with their clusters, the learned frequent word embeddings are also better, as demonstrated later through our experimental results.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Motivation of ReOut.}
The standard CBOW model is usually trained with negative sampling, which is designed to speed up the training process. By using ReOut, infrequent words will be replaced with their clusters, which are more reliable than those used in the original CBOW model. As a result, ReOut makes the training of the CBOW model more effective, as shown later through our experiments.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Hyperparameter Settings}
\label{sec:hyperparameters}

In this section, we describe the hyperparameters for producing word clusters and word embeddings (the hyperparameters for downstream tasks will be described in a later section). As mentioned earlier, we obtained the word clusters through the ClusterCat software, and we used its default values for most of the hyperparameters. We set the number of clusters to 600 in all our experiments. Because our work involves many tasks in total, it is difficult to choose the optimal number of word clusters for each task. We experimented with several values (600, 800, and 1,000) and observed the same trend. Thus, for convenience, we simply chose 600 for all tasks. For producing word embeddings, our implementation was based on fastText.\footnote{\url{https://github.com/facebookresearch/fastText}} Our cluster-incorporated CBOW model and standard CBOW model were trained under the same hyperparameters. We set the hyperparameters as the default fastText values. For example, we set the training epochs to 5, number of negative examples to 5, window size to 5, and minimum count of word occurrence to 5.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experiments on Word Similarity Task}
\label{sec:word_sim}

The word similarity task is not necessarily suitable for our replacing method because many infrequent words share the same embedding within one cluster. Thus, we report the results of the task for three different groups of test word pairs: {\it frequent-word-pair}, consisting of frequent word pairs; {\it infrequent-word-pair}, consisting of word pairs that share a cluster embedding with other words; and {\it all-word-pair}, consisting of all test word pairs. We used the publicly available enwik8\footnote{\url{http://mattmahoney.net/dc/enwik8.zip}} corpus as the training data to obtain both word embeddings and word clusters. Note that we used this data only for the word similarity task, not for downstream tasks such as language modelling and machine translation. We preprocessed the corpus by lowercasing all words, removing words that contain non-alphabetical characters, and removing words whose frequency is less than 5. The final corpus contains approximately 12 million tokens and 60K word types. We chose MEN \cite{men3k}, MTurk287 \cite{mturk287}, MTurk771 \cite{mturk771}, RW \cite{luong2013better}, and WS353 \cite{wordsim353} as our datasets. Then, we evaluated the quality of these representations by computing Spearman's rank correlation coefficient. 

We first applied ClusterCat to the preprocessed corpus to obtain word clusters and then produced cluster-incorporated word embeddings. The results are given in Table \ref{tab_sim_res}. In Cluster-CBOW, the number of input words is 10,203, which is the sum of 9,603 frequent words and 600 clusters. This is only 16.9\% of the number of input words for the original CBOW, which maintains 60K input words. In the all-word-pair group, CBOW outperformed Cluster-CBOW on all datasets. This is because Cluster-CBOW does not perform well in the infrequent-word-pair group, as many infrequent words share exactly the same embedding in one cluster. In this experiment, each cluster had 82 words on average. However, Cluster-CBOW outperformed CBOW on the frequent-word-pair group in all datasets. This result suggests that Cluster-CBOW is effective in learning embeddings for frequent words with significantly fewer parameters. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 1
\begin{table}[t]
\input{02table01.tex}
\hangcaption{Spearman's rank correlation coefficient on word similarity datasets for different groups. The best scores in each group are in bold.}
\label{tab_sim_res}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experiments on LM and MT}

We applied our embeddings to two downstream tasks: LM and MT. For this, we only used the training data of the specific task to obtain word clusters and embeddings, without any additional data. We then used the learned embeddings to initialize the lookup table of the word embeddings for the task. We limited the applications of our model to only the LM and MT tasks in this work to demonstrate the usefulness of our method. We plan to conduct experiments on additional downstream tasks in future work. In the following tables, CBOW, Cluster-CBOW, and Random indicate the initialization methods used for specific downstream tasks. Note that the models of a specific downstream task have exactly the same hyperparameters, and only the initialization methods are different.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{LM on Standard English Datasets}

We tested Cluster-CBOW based on the recent state-of-the-art AWD-LSTM-LM codebase\footnote{\url{https://github.com/salesforce/awd-lstm-lm}} \cite{merity2018regularizing} using two standard language modeling datasets: Penn Treebank (PTB) and WikiText-2 (Wiki2). The data statistics are provided in Table \ref{tab:ptb_wiki2_data_sti}. For the hyperparameters of AWD-LSTM-LM, we followed exactly the same setting as the source code. The results are listed in Table \ref{tab:ptb_wiki2_res}. We can see that our Cluster-CBOW is effective even with the AWD-LSTM-LM, in which the models are trained for 500 epochs and 750 epochs on PTB and Wiki2, respectively.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 2
\begin{table}[b]
\input{02table02.tex}
\caption{Data statistics of PTB and Wiki2.}
\label{tab:ptb_wiki2_data_sti}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 3
\begin{table}[b]
\input{02table03.tex}
\caption{Perplexity results on PTB and Wiki2.}
\label{tab:ptb_wiki2_res}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{NMT}

We applied our method to the standard long-short term memory network (LSTM)-based sequence-to-sequence (seq2seq) model on two datasets: German-English (de-en) with 153K sentence pairs from IWSLT 2014 \citeA{cettolo2014report}, and English-Vietnamese (en-vi) with 133K sentence pairs from IWSLT 2015 \citeA{cettoloEtAl:EAMT2012}. The detailed statistics of the datasets are provided in Table \ref{tab:nmt_data_sti}. We used the opennmt-py toolkit\footnote{\url{https://github.com/OpenNMT/OpenNMT-py}} \cite{klein2017opennmt} with a 2-layer bidirectional LSTM hidden size of 500 and set the training epochs to 30. The word embedding size was set to 500 and the batch size was 64. We trained the seq2seq models by the SGD optimizer with the start learning rate of 1.0, which was set to decay by 0.5 if the perplexity did not decrease on the validation set. Other hyperparameters were kept as the default. As shown in Table \ref{tab:nmt_res}, without any extra language pair resources, the Cluster-CBOW initialization improved the BLEU score over the baseline by 1.29 and 0.51 points on de-en and en-vi, respectively.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 4
\begin{table}[b]
\input{02table04.tex}
\caption{Data statistics of two NMT datasets.}
\label{tab:nmt_data_sti}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 5
\begin{table}[b]
\input{02table05.tex}
\caption{BLEU scores on two MT datasets.}
\label{tab:nmt_res}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 8-->6
%%%%\addtocounter{table}{2}
\begin{table}[b]
\input{02table08.tex}
\hangcaption{Data statistics of 8 language modeling datasets and size of input vocabulary of our Cluster-CBOW.}
\label{tab:8_lang_data_sti}
\vspace{-0.5\Cvs}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{LM in Diverse Languages}
\label{sec:lm_in_diverse}

To determine the effect of word clusters on different languages, we selected eight datasets containing typologically diverse languages from the LM datasets released by \citeA{gerz2018language}. The data statistics are provided in Table \ref{tab:8_lang_data_sti}. We basically used standard LSTMs instead of AWD-LSTM-LM to save time and utilized the standard LSTM-LM code.\footnote{\url{https://github.com/pytorch/examples/tree/master/word_language_model}} The hyperparameters of our standard LSTM model on the language modeling tasks are listed in Table \ref{tab:hyper}. The results are shown in Table~\ref{tab:8_lang_res}. Since our LSTM-LM obtained better results than the one from \citeA{gerz2018language} on all datasets, we only use our own baseline for the comparison (the results from \citeA{gerz2018language} are not included). As we can see in the table, Cluster-CBOW is effective for typologically diverse languages and also requires a smaller input vocabulary. For example, the input vocabulary of Cluster-CBOW for the en dataset contains 1.3K words, while the full vocabulary is 50K.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 6-->7
%%%%\addtocounter{table}{-3}
\begin{table}[t]
\input{02table06.tex}
\caption{Hyperparameters of our standard LSTM model on language modeling task.}
\label{tab:hyper}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 7-->8
\begin{table}[t]
\input{02table07.tex}
\caption{Perplexity results of standard LSTM LM on 8 datasets with different initialization methods.}
\label{tab:8_lang_res}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Analysis}
\label{sec:analysis}

In this section, we analyze Cluster-CBOW on the basis of LM experiments with en and de datasets. At the end of this section, we use the English Wikipedia corpus as the training dataset for our Cluster-CBOW and then apply the learned embeddings on LM experiments with the en dataset to show our method can also be applied on large-scale corpora.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Targeted Perplexity Results}
\label{sec:targeted_ppl}

To clarify the gain for frequent and infrequent words, we measured the perplexity for frequent and infrequent words in the test data separately. Specifically, when an infrequent word was given as the current word, we calculated the perplexity of the next word. A similar analysis on language models can be found in \citeA{vania-lopez-2017-characters}. Our analysis does not contain new words in the test dataset. The results are shown in Table \ref{tab:targeted_ppl}. As we can see, Cluster-CBOW is more effective than CBOW in learning both the embeddings of frequent and infrequent words, as we explained in Sec. \ref{sec:motivation_rein}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 9
%%%%\addtocounter{table}{1}
\begin{table}[b]
\input{02table09.tex}
\caption{Targeted perplexity results of standard LSTM LM with different initializations.}
\label{tab:targeted_ppl}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 10
\begin{table}[b]
\input{02table10.tex}
\hangcaption{Perplexity results of LSTM LM by changing the number of negative samples. `+neg' represents the number of negative samples, which is 5 at default.}
\label{tab:effect_reout}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Ablation Study of ReIn and ReOut}
\label{sec:ablation}

Since ReIn and ReOut are used together in our Cluster-CBOW, we add an ablation study here to show their effects separately. The results of this ablation study are summarized in Table \ref{tab:effect_reout}. Comparing the methods ReIn and CBOW, we found that replacing only input infrequent words in CBOW also works better than the original CBOW. We can also conclude that replacing only output infrequent words in CBOW works better than the original CBOW, by comparing ReOut and CBOW. Both ReIn and ReOut work well even when they are used alone. As mentioned in our discussion about the motivation of ReOut, it makes the training more effective. To verify this, we increased the number of negative samples for ReIn and CBOW. The training will be more effective if we increase the number of negative samples, but training the model will also take longer. As we increased the size of negative samples, we obtained better results for both ReIn and CBOW. We increased it only to 30 because we did not observe improvements when we made it larger than that. This result indicates that we can use word clusters to obtain better results with only a small amount of negative samples. In reality, we can also use off-the-shelf word clusters to avoid spending time on producing word clusters. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Effect of Word Clusters}
\label{sec:effect_word_cluster}

To analyze how much the quality of the word clusters affects the effectiveness of our method, we use Brown clustering \cite{brown1992class} and a simple baseline that assigns random clusters from 1 to 600 to infrequent words. We use the available software\footnote{\url{https://github.com/percyliang/brown-cluster}} to obtain Brown clusters. We set the number of clusters as 600 which is also used by Clustercat and other hyperparameters are kept at default. The results are shown in Table \ref{tab:effect_word_cluster}.
As a result, ClusterCat clusters and Brown clusters are better than randomly produced clusters. This is because the words in a randomly produced word cluster may not be related with each other. It indicates that the quality of word clusters will impact the effectiveness of our method. In the table, we can also see that the results of using ClusterCat clusters and Brown clusters are relatively close. This suggests that we can also choose other word clustering methods for our proposal. We choose the recent ClusterCat over Brown clustering because ClusterCat is much faster than Brown clustering, as we discuss later.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 11
\begin{table}[b]
\input{02table11.tex}
\hangcaption{Perplexity results of standard LSTM LM with different initialization. The first row indicates the method to produce word clusters used in Cluster-CBOW.}
\label{tab:effect_word_cluster}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Speed and Spatial Comparison}
\label{sec:speed_spatial}

For the word clustering algorithm, we mentioned that we choose ClusterCat due to its high speed and also discussed its speed comparison with other clustering methods in  Sec. \ref{sec:intro} as reported by the authors of ClusterCat. Here, we compare the speed of ClusterCat and the above mentioned Brown clustering method on our datasets. We ensured that both algorithms were tested under the same environment and with the same number of threads. The results are listed in Table \ref{tab:clustering_time}, showing that ClusterCat is much faster.

Regarding the speed comparison between Cluster-CBOW and CBOW, it is almost the same. This is because we trained both models for the same number of epochs. As Cluster-CBOW replaces infrequent words with their clusters, the number of updates is not changed. While it takes additional time to obtain word clusters for Cluster-CBOW, the obtained word clusters can be reused at no cost to train word embeddings of different dimensions. Spatial comparison results between Cluster-CBOW and CBOW are listed in Table \ref{tab:params} for two datasets. It can be seen that our Cluster-CBOW contains much fewer parameters.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 12
\begin{table}[b]
\input{02table12.tex}
\caption{Time of two clustering algorithms on two datasets.}
\label{tab:clustering_time}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 13
\begin{table}[b]
\input{02table13.tex}
\caption{Number of parameters that the two models contain.}
\label{tab:params}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Robustness to Frequency Bias}

We used the same frequency threshold of 100 for convenience in the above experiments because we had to train our Cluster-CBOW on approximately 15 datasets. To check the robustness of our method to frequency bias, we used different frequency thresholds for our experiments on the en and de datasets. The results are listed in Table \ref{tab:frequency_change}, which indicates the perplexity scores are not changed significantly when the frequency thresholds are changed. One reason for the robustness may be that these learned word and cluster embeddings are only used as initialization, and they will be learned again in downstream tasks.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 14
\begin{table}[b]
\input{02table14.tex}
\hangcaption{Perplexity results of standard LSTM LM with different thresholds in Cluster-CBOW for obtaining word and cluster embeddings.}
\label{tab:frequency_change}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Examples of Word Clusters}

We show some examples of word clusters from the English dataset learned by ClusterCat in Table \ref{tab:cluster_example}. Note that in the table, we only select the words whose frequencies are less than our threshold so that these words will be replaced by their clusters. We observed that some medium-frequency words can usually be grouped well by their syntactic or semantic features. However, it may be difficult for some rare words to be grouped well, as shown in the table.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 15
\begin{table}[b]
\input{02table15.tex}
\hangcaption{Examples of word clusters on en dataset. The words in each row are in the same cluster and numbers in parentheses indicate word frequencies in the dataset. In each row, the words are sorted by their frequency.}
\label{tab:cluster_example}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Visualization of Word Embeddings}
\label{sec:visualization}

We visualize word embeddings using t-SNE projections. Specifically, we randomly chose 15 clusters and all frequent words from en and visualize frequent and infrequent word embeddings in these 15 clusters in Fig. \ref{fig:finetuned_emb}. The embeddings of infrequent words within one cluster are located close together after being fine-tuned. Some infrequent word embeddings are updated only a few times and are not far from where they were randomly initialized, becoming more reliable.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 2
\begin{figure}[t]
\begin{center}
\includegraphics{29-3ia2f2.pdf}
\end{center}
\hangcaption{Visualization of embeddings of frequent words and clusters before fine-tuning (upper) and the embeddings of frequent and infrequent words after fine-tuning (lower). The red dots represent frequent words, and the dots with a larger size represent word clusters.}
\label{fig:finetuned_emb}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Cluster-CBOW on Large-scale Corpus}
\label{sec:large_scale_exp}

To verify the effect when our Cluster-CBOW is applied on a large-scale corpus, we downloaded the English Wikipedia dump\footnote{\url{https://dumps.wikimedia.org/enwiki/20210801/enwiki-20210801-pages-articles.xml.bz2}} as our training dataset. We extracted only articles from the dump, tokenized these articles, and kept words that appear at least five times. After preprocessing, the corpus had 3.7 billion tokens and 2.5 million word types. We first obtained word clusters and then learned word embeddings on the preprocessed corpus. The vocabulary size of the preprocessed corpus was approximately 2.5 million. Because this training dataset is much larger than those used for word similarity and downstream tasks (where the vocabulary size is typically 100K at most), we set the number of word clusters and frequency thresholds differently for the Wikipedia corpus. ClusterCat recommends setting the number of word clusters to the square root of the vocabulary size for a large corpus, which is 1,600 in our case. For frequency thresholds, we simply used 50 for both $f_{in}$ and $f_{out}$, which is half the above settings for small datasets.

The learned embeddings will be used to initialize the lookup table of the word embeddings
of the LSTM language model, which is the same as before. In the above experiments, we only used the training dataset of specific tasks to train our clusters and embeddings, but here, we use an extra training dataset. To gauge the effect of our CBOW baseline, we also use the publicly available GloVe Vectors,\footnote{\url{https://nlp.stanford.edu/data/glove.6B.zip}} which are also trained on the English Wikipedia corpus. From Table \ref{tab:large_scale}, it can be seen that our method is still effective on this corpus. After replacing infrequent words, our Cluster-CBOW only needs to maintain a vocabulary size of 472,500 words and 1600 clusters, which is approximately 20\% of the original vocabulary size. Thus, our Cluster-CBOW requires significantly fewer parameters in training than the standard CBOW. Because our method simply replaces infrequent words, it does not increase the training time compared to the standard CBOW model under the same hyperparameters. The only additional time cost comes from training the word clusters. While using the recent algorithm, it only takes approximately one hour to train 1600 clusters on the Wikipedia corpus in our case. The trained word clusters can be reused to train word embeddings of different dimensions. We can also use off-the-shelf word clusters to save more time.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 16
\begin{table}[t]
\input{02table16.tex}
\caption{Perplexity results of standard LSTM with different initializations.}
\label{tab:large_scale}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


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

In this paper, we proposed a simple and effective method to incorporate word clusters into the CBOW model. Our method is helpful for learning embeddings of both frequent and infrequent words, reducing the parameters when training word embeddings and making negative sampling more effective. In future work, we will test our method on additional downstream tasks. We will also investigate how to combine word clusters with subword information.


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

This paper is an extended version of the paper \cite{feng-etal-2020-simple} accepted for publication by the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 10th International Joint Conference on Natural Language Processing (AACL-IJCNLP 2020). This extended version contains the following changes:
\begin{itemize}
\item
Motivation for context-independent word embeddings is added in Sec. \ref{sec:intro}.
\item
Experiments on a large-scale corpus are added in Sec. \ref{sec:large_scale_exp} to show our method is effective in a practical setting. The related motivation is also added in Sec. \ref{sec:related_work}. 
\item
More analyses of our proposal are added in Sec. \ref{sec:analysis}.
\item
Experiments on word similarity tasks in Sec. \ref{sec:word_sim} and related introduction in Sec. \ref{sec:intro} are added. They are in the appendix of the original paper.
\item
Visualization of the embeddings of frequent words and clusters before and after fine-tuning in Sec. \ref{sec:visualization} is added. It is in the appendix of the original paper.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{jnlpbbl_1.6}
\bibliography{02refs}


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

\bioauthor[:]{Yukun Feng}{He is currently a Ph.D. candidate at Department of Information and Communications Engineering, Tokyo Institute of Technology.  Before that, he received M.E. from Tokyo Institute of Technology in 2020 and B.E. from Beijing Language and Culture University in 2016. His research interests include natural language processing and machine learning, particularly word representation learning and language modeling.
}
\bioauthor[:]{Chenlong Hu}{He received his Ph.D. from 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[:]{Hidetaka Kamigaito}{He received his Ph.D. from Tokyo Institute of Technology, and is currently an associate professor in Nara Institute of Science and Technology. He worked as an assistant professor at Institute of Innovative Research, Tokyo Institute of Technology. His current research interests are in natural language processing with a specific focus on document-level text processing.
}
\bioauthor[:]{Hiroya Takamura}{
He received his Ph.D. from Nara Institute of Science and Technology. He worked as a professor at Tokyo Institute of Technology, and currently is a research team leader at AI Research Center of Advanced Industrial Science and Technology. His current research interests include natural language processing.
}
\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}

