1 Introduction↩︎

Computing the co-occurrence strength between two linguistic expressions is a fundamental task in natural language processing (NLP). For example, in collocation extraction [1], word bigrams are collected from corpora and then strongly co-occurring bigrams (e.g., “New York”) are found. In dialogue response selection [2], pairs comprising a context and its response sentence are collected from dialogue corpora and the goal is to rank the candidate responses for each given context sentence. In either case, a set of linguistic expression pairs \(\mathcal{D} = \{(x_i,y_i)\}_{i=1}^n\) is first collected and then the co-occurrence strength of a (new) pair \((x,y)\) is computed.

Pointwise mutual information (PMI) [3] is frequently used to model the co-occurrence strength of linguistic expression pairs. There are two typical types of PMI estimation (computation) method.

One is a counting-based estimator using maximum likelihood estimation, sometimes with smoothing techniques, for example, \[\begin{align} \widehat{\mathrm{PMI}}_{\mathrm{MLE}}(x,y;\mathcal{D}) &\!=\! \tikz[baseline] \node[fill=lightgray!45, rounded corners=3pt, anchor=base] () {\displaystyle \!\log \frac{n \cdot c(x,y)}{\sum_{y'}\!c(x,y')\sum_{x'}\!c(x'\!,y)} \!}; \,\text{,}\!\label{eq:pmi95mle} \end{align}\tag{1}\] where \(c(x,y)\) denotes the frequency of the pair \((x,y)\) in given data \(\mathcal{D}\). This is easy to compute and is commonly used to measure co-occurrence between words, such as in collocation extraction¹; however, when data \(\mathcal{D}\) is sparse, i.e., when \(x\) or \(y\) is a phrase or sentence, this approach is unrealistic. The second method uses recurrent neural networks (RNNs). [4] proposed to employ PMI to suppress dull responses for utterance generation in dialogue systems². They estimated \(\mathbf{P}(y)\) and \(\mathbf{P}(y|x)\) using RNN language models and estimated PMI as follows: \[\begin{align} \widehat{\mathrm{PMI}}_{\mathrm{RNN}}^{}(x,y;\mathcal{D}) = \tikz[baseline] \node[fill=lightgray!45, rounded corners=3pt, anchor=base] () {\displaystyle\! \log \frac{\widehat{\mathbf{P}}_{\mathrm{RNN}}(y|x)}{\widehat{\mathbf{P}}_{\mathrm{RNN}}(y)} \!}; \,\text{.} \label{eq:pmi95rnn} \end{align}\tag{2}\] This way of estimating PMI is applicable to sparse language expressions; however, learning RNN language models is computationally costly.

To eliminate this trade-off between robustness to data sparsity and learning time, in this study we propose a new kernel-based co-occurrence measure, which we call the pointwise Hilbert–Schmidt independence criterion (PHSIC) (see Table 1). Our contributions are as follows:

• We formalize PHSIC, which is derived from HSIC [5], a kernel-based dependence measure, in the same way that PMI is derived from mutual information (Section 3).

• We give an intuitive explanation why PHSIC is robust to data sparsity. PHSIC is a “smoothed variant of PMI”, which allows various similarity metrics to be plugged in as kernels (Section 4).

• We propose fast estimators of PHSIC, which are reduced to a simple and fast matrix calculation regardless of whether we use linear or nonlinear kernels (Section 5).

• We empirically confirmed the effectiveness of PHSIC, i.e., its robustness to data sparsity and learning time, in two different types of experiment, a dialogue response selection task and a data selection task for machine translation (Section 6).

2 Problem Setting↩︎

Let \(X\) and \(Y\) denote random variables on \(\mathcal{X}\) and \(\mathcal{Y}\), respectively. In this paper, we deal with the tasks of taking a set of linguistic expression pairs \[\begin{align} \mathcal{D} = \{(x_i,y_i)\}_{i=1}^n \underset{\text{i.i.d.}}{\sim} \Prob{XY} \text{,} \end{align}\] which is regarded as a set of i.i.d.samples drawn from a joint distribution \(\Prob{XY}\), and then measuring the “co-occurrence strength” for each given pair \((x,y) \in \mathcal{X}\times\mathcal{Y}\). Such tasks include collocation extraction and dialogue response selection (Section 1).

3 Pointwise HSIC↩︎

In this section, we give the formal definition of PHSIC, a new kernel-based co-occurrence measure. We show a summary of this section in Table 2. Intuitively, PHSIC is a “kernelized variant of PMI.”

0.9em

3.1 Dependence Measure↩︎

As a preliminary step, we introduce the simple concept of dependence (see Dependence Measure in Table 2). Recall that random variables \(X\) and \(Y\) are independent if and only if the joint probability density \(\Prob{XY}\) and the product of the marginals \(\Prob{X}\Prob{Y}\) are equivalent. Therefore, we can measure the dependence between random variables \(X\) and \(Y\) via the difference between \(\Prob{XY}\) and \(\Prob{X}\Prob{Y}\).

Both the mutual information and the Hilbert–Schmidt independence criterion, to be described below, are such dependence measures.

3.2 MI and PMI↩︎

We briefly review the well-known mutual information and PMI (see MI & PMI in Table 2).

The mutual information (MI)³ between two random variables \(X\) and \(Y\) is defined by \[\begin{align} \mathrm{MI}(X,Y) := \mathrm{KL}[\Prob{XY} \| \Prob{X}\Prob{Y}] \label{eq:mi95kl} \end{align}\tag{3}\] [6], where \(\mathrm{KL}[\cdot\|\cdot]\) denotes the Kullback–Leibler (KL) divergence. Thus, \(\mathrm{MI}(X,Y)\) is the degree of dependence between \(X\) and \(Y\) measured by the KL divergence between \(\Prob{XY}\) and \(\Prob{X}\Prob{Y}\).

Here, by definition of the KL divergence, MI can be represented in the form of the expectation over \(\Prob{XY}\), i.e., the summation over all possible pairs \((x,y)\in \mathcal{X}\!\times\!\mathcal{Y}\): \[\begin{align} \mathrm{MI}(X,Y) &= \underset{(x,y)}{\mathbf{E}}\Biggl[ \tikz[baseline] \node[fill=lightgray!45, rounded corners=3pt, anchor=base] () {\displaystyle \log\frac{\Prob{XY}[x,y]}{\Prob{X}[x]\Prob{Y}[y]} }; \Biggr]\label{eq:mi95as95expectation95of95pmi} \text{.} \end{align}\tag{4}\] The shaded part in Equation 4 is actually the pointwise mutual information (PMI) [3]: \[\begin{align} \mathrm{PMI}(x,y;X,Y) := \tikz[baseline] \node[fill=lightgray!45, rounded corners=3pt, anchor=base] () {\displaystyle \log\frac{\Prob{XY}[x,y]}{\Prob{X}[x]\Prob{Y}[y]} };\label{eq:pmi95as95contribution95of95mi} \,\text{.} \end{align}\tag{5}\] Therefore, \(\mathrm{PMI}(x,y)\) can be thought of as the contribution of \((x,y)\) to \(\mathrm{MI}(X,Y)\).

3.3 HSIC and PHSIC↩︎

As seen in the previous section, PMI can be derived from MI. Here, we consider replacing MI with the Hilbert–Schmidt independence criterion (HSIC). Then, in analogy with the relationship between PMI and MI, we derive PHSIC from HSIC (see HSIC & PHSIC in Table 2).

Let \(k\colon\mathcal{X}\times\mathcal{X}\to \mathbb{R}\) and \(\ell\colon\mathcal{Y}\times\mathcal{Y}\to \mathbb{R}\) denote positive definite kernels on \(\mathcal{X}\) and \(\mathcal{Y}\), respectively (intuitively, they are similarity functions between linguistic expressions). The Hilbert–Schmidt independence criterion (HSIC) [5], a kernel-based dependence measure, is defined by \[\begin{align} \mathrm{HSIC}(X,Y\!;k,\ell) & \textstyle \!:=\! \mathrm{MMD}_{k,\ell}^2[\Prob{XY} , \Prob{X}\Prob{Y}]_{}\label{eq:hsic95definition95mmd} \text{,}\! \end{align}\tag{6}\] where \(\mathrm{MMD}[\cdot, \cdot]\) denotes the maximum mean discrepancy (MMD) [7], which measures the difference between random variables on a kernel-induced feature space. Thus, \(\mathrm{HSIC}(X,Y;k,\ell)\) is the degree of dependence between \(X\) and \(Y\) measured by the MMD between \(\Prob{XY}\) and \(\Prob{X}\Prob{Y}\), while MI is measured by the KL divergence (Equation 3 ).

Analogous to MI in Equation 4 , HSIC can be represented in the form of the expectation on \(\Prob{XY}\) by a simple deformation: \[\begin{align} &\mathrm{HSIC}(X,Y;k,\ell)\nonumber\\ &= \underset{\mathclap{(x,y)}}{\mathbf{E}}\Bigl[ \tikz[baseline] \node[fill=LimeGreen!45, rounded corners=3pt, anchor=base] () {\displaystyle \!(\phi(x) \!-\! m_X^{})^{\!\top\!} C_{XY}^{} (\psi(y) \!-\! m_Y^{}) }; \Bigr]\tag{7} \\[-4.5pt] &= \underset{\mathclap{(x,y)}}{\mathbf{E}} \Bigl[ \tikz[baseline] \node[fill=LimeGreen!45, rounded corners=3pt, anchor=base] () {\displaystyle \underset{(x',y')}{\mathbf{E}}[ \widetilde{k}(x,x')\widetilde{\ell}(y,y') ] }; \Bigr]\tag{8} \text{,} \end{align}\] where \[\begin{align} & \phi(x) := k(x,\cdot) \text{,} \quad \psi(y) := \ell(y,\cdot) \text{,} \\ & m_X^{} := \mathbf{E}_x[\phi(x)] \text{,} \quad m_Y^{} := \mathbf{E}_y[\psi(y)] \text{,} \\ & C_{XY}^{} := \underset{\mathclap{(x,y)}}{\mathbf{E}}\Bigl[ (\phi(x) - m_X^{} ) (\psi(y) - m_Y^{} )^{\!\top}\! \Bigr] \text{,}\! \\[-2pt] & \widetilde{k}(x,x') := k(x,x') - \mathbf{E}_{x'}[k(x,x')]\nonumber\\ &\qquad\quad\, - \mathbf{E}_{x}[k(x,x')] + \mathbf{E}_{x,x'}[k(x,x')] \text{.}\!\label{eq:centered95kernel} \end{align}\tag{9}\] At first glance, these equations are somewhat complicated; however, the estimators of PHSIC we actually use are reduced to a simple matrix calculation in Section 5. Unlike MI in Equation 4 , HSIC has two representations: Equation 7 is the representation in feature space and Equation 8 is the representation in data space.

Similar to the relationship between MI and PMI (Section 3.2), we define the pointwise Hilbert–Schmidt independence criterion (PHSIC) by the shaded parts in Equations 7 and 8 : \[\begin{align} &\mathrm{PHSIC}(x,y;X,Y,k,\ell)\nonumber\\ &:= \tikz[baseline] \node[fill=LimeGreen!45, rounded corners=3pt, anchor=base] () {\displaystyle (\phi(x) - m_X^{})^\top C_{XY} (\psi(y) - m_Y^{}) };\tag{10} \\ &= \tikz[baseline] \node[fill=LimeGreen!45, rounded corners=3pt, anchor=base] () {\displaystyle \underset{(x',y')}{\mathbf{E}}[\widetilde{k}(x,x')\widetilde{\ell}(y,y')] };\tag{11} \,\text{.}\! \end{align}\] Namely, \(\mathrm{PHSIC}(x,y)\) is defined as the contribution of \((x,y)\) to \(\mathrm{HSIC}(X,Y)\).

In summary, we define PHSIC such that “MI:PMI = HSIC:PHSIC” holds (see Table 2).

4 PHSIC as Smoothed PMI↩︎

This section gives an intuitive explanation for the first feature of PHSIC, i.e., the robustness to data sparsity, using Table 1. In short, we show that PHSIC is a “smoothed variant of PMI.”

First, the maximum likelihood estimator of PMI in Equation 1 can be rewritten as \[\begin{align} \!\!\!\!\widehat{\mathrm{PMI}}(x,y;\!\mathcal{D}) \!=\! \tikz[baseline] \node[fill=lightgray!45, rounded corners=3pt, anchor=base] () {\displaystyle\! \log\!\frac{n\cdot \sum_i \!\mathbb{I}[x\!=\!x_i \land y\!=\!y_i]}{\sum_i \!\mathbb{I}[x\!=\!x_i] \sum_i \!\mathbb{I}[y\!=\!y_i]}\!}; \,\text{,}\!\!\label{eq:pmi95mle95compare} \end{align}\tag{12}\] where \(\mathbb{I}[\text{condition}] = 1\) if the condition is true and \(\mathbb{I}[\text{condition}] = 0\) otherwise. According to Equation 12 , \(\widehat{\mathrm{PMI}}(x,y)\) is the amount computed by repeating the following operation (see the first row in Table 1):

collate the given \((x,y)\) and the observed \((x_i,y_i)\) in \(\mathcal{D}\) in order, and add the scores if \((x,y)\) and \((x_i,y_i)\) match exactly or deduct the scores if either the \(x\) side or the \(y\) side (but nor both) matches.

Moreover, an estimator of PHSIC in data space (Equation 11 ) is \[\begin{align} \!\widehat{\mathrm{PHSIC}}(x,y;\mathcal{D},k,\ell) \!=\! \tikz[baseline] \node[fill=LimeGreen!45, rounded corners=3pt, anchor=base] () {\! \frac{1}{n} \!\sum_i \widehat{\widetilde{k}}(x,x_i)\widehat{\widetilde{\ell}}(y,y_i)\!}; \,\text{,}\!\!\label{eq:phsic95mle95compare} \end{align}\tag{13}\] where \(\widehat{\widetilde{k}}(\cdot,\cdot)\) and \(\widehat{\widetilde{\ell}}(\cdot,\cdot)\) are similarity functions centered on the data⁴. According to Equation 13 , \(\widehat{\mathrm{PHSIC}}(x,y)\) is the amount computed by repeating the following operation (see the second row in Table 1):

collate the given \((x,y)\) and the observed \((x_i,y_i)\) in \(\mathcal{D}\) in order, and add the scores if the similarities on the \(x\) and \(y\) sides are both higher (both \(\widehat{\widetilde{k}}(x,x_i)>0\) and \(\widehat{\widetilde{\ell}}(y,y_i)>0\) hold)⁵ or deduct the scores if the similarities on either the \(x\) or \(y\) sides are similar but those on the other side are not similar.

As described above, when comparing the estimators of PMI and PHSIC from the viewpoint of “methods of matching the given \((x,y)\) and the observed \((x_i,y_i)\),” it is understood that PMI matches them in an exact manner, while PHSIC smooths the matching using kernels (similarity functions).

With this mechanism, even for completely unknown pairs, it is possible to estimate the co-occurrence strength by referring to observed pairs through the kernels. Therefore, PHSIC is expected to be robust to data sparsity and can be applied to phrases and sentences.

4.0.0.1 Available Kernels for PHSIC

In NLP, a variety of similarity functions (i.e., positive definite kernels) are available. We can freely utilize such resources, such as cosine similarity between sentence embeddings. For a more detailed discussion, see Appendix 9.

5 Empirical Estimators of PHSIC↩︎

Recall that we have two types of empirical estimator of PMI, the maximum likelihood estimator (Equation 1 ) and the RNN-based estimator (Equation 2 ). In this section, we describe how to rapidly estimate PHSIC from data. When using the linear kernel or cosine similarity (e.g., cosine similarity between sentence embeddings), PHSIC can be efficiently estimated in feature space (Section 5.1). When using a nonlinear kernel such as the Gaussian kernel, PHSIC can also be estimated efficiently in data space via a simple matrix decomposition (Section 5.2).

5.1 Estimation Using Linear Kernel or Cosine↩︎

When using the linear kernel or cosine similarity, the estimator of PHSIC in feature space 10 is as follows: \[\begin{align} &\!\!\widehat{\mathrm{PHSIC}}_{\mathrm{feature}}(x,y;\mathcal{D},k,\ell)\nonumber\\ &\!\!\hphantom{\widehat{C}_{XY}^{}} \!\,=\! \tikz[baseline] \node[fill=LimeGreen!45, rounded corners=3pt, anchor=base] () {\! (\phi(x) \!-\! \overline{\phi(x)})^{\!\top}\widehat{C}_{\!XY}^{}(\psi(y) \!-\! \overline{\psi(y)}) \!}; \,\text{,}\!\label{eq:phsic95RKHS} \end{align}\tag{14}\] where \[\begin{align} &\phi(x) = \!\begin{cases} x &\text{(k(x,x') = x^\top x')}\\ x/\lVert x\rVert &\text{(k(x,x') = \cos(x,x'))} \end{cases}\label{eq:feature95maps95linear95cosine}\!\text{,}\! \\ &\overline{\phi(x)} \!:=\! \frac{1}{n} \!\sum_{i=1}^n \phi(x_i) \text{,} \quad\!\overline{\psi(y)} \!:=\! \frac{1}{n} \!\sum_{i=1}^n \psi(y_i) \text{,} \\ &\widehat{C}_{XY}^{}\!:=\! \frac{1}{n} \sum_{i=1}^n \phi(x_i)\psi(y_i)^{\!\top} \!- \overline{\phi(x)} \,\overline{\psi(y)}^{\top\!} \text{.} \end{align}\tag{15}\] Generally in kernel methods, a feature map \(\phi(\cdot)\) induced by a kernel \(k(\cdot,\cdot)\) is unknown or high-dimensional and it is difficult to compute estimated values in feature space⁶. However, when we use the linear kernel or cosine similarity, feature maps can be explicitly determined (Equation 15 ).

5.1.0.1 Computational Cost

When learning Equation 14 with feature maps \(\phi\colon\mathcal{X}\to\mathbb{R}^d\) and \(\psi\colon\mathcal{Y}\to\mathbb{R}^d\), computing the vectors \(\overline{\phi(x)}, \overline{\psi(y)}\in\mathbb{R}^d\) and the matrix \(\widehat{C}_{XY}^{}\in\mathbb{R}^{d\times d}\) takes \(\mathcal{O}(nd^2)\) time and \(\mathcal{O}(nd)\) space (linear in the size of the input, \(n\)). When estimating \(\mathrm{PHSIC}(x,y)\), computing \(\phi(x),\psi(y)\in\mathbb{R}^d\) and Equation 14 takes \(\mathcal{O}(d^2)\) time (constant; does not depend on the size of the input, \(n\)).

5.2 Estimation Using Nonlinear Kernels↩︎

When using a nonlinear kernel such as the Gaussian kernel, it is necessary to estimate PHSIC in data space. Using a simple matrix decomposition, this can be achieved with the same computational cost as the estimation in feature space. See Appendix 10 for a detailed derivation.

6 Experiments↩︎

In this section, we provide empirical evidence for the greater effectiveness of PHSIC than PMI, i.e., a very short learning time and robustness to data sparsity. Among the many potential applications of PHSIC, we choose two fundamental scenarios, (re-)ranking/classification and data selection.

• In the ranking/classification scenario (measuring the co-occurrence strength of new data pairs with reference to observed pairs), PHSIC is applied as a criterion for the dialogue response selection task (Section 6.2).

• In the data selection/filtering scenario (ordering the entire set of observed data pairs according to the co-occurrence strength), PHSIC is also applied as a criterion for data selection in the context of machine translation (Section 6.3).

6.1 PHSIC Settings↩︎

To take advantage of recent developments in representation learning, we used several pre-trained models for encoding sentences into vectors and several kernels between these vectors for PHSIC.

6.1.0.1 Encoders

As sentence encorders, we used two pre-trained models without fine-tuning. First, the sum of the word vectors effectively represents a sentence [8]: \[\begin{align} \textstyle \boldsymbol{x} \!=\! \sum_{w\in x}\!\mathrm{vec}(w), \quad \boldsymbol{y} \!=\! \sum_{w\in y}\!\mathrm{vec}(w) \text{.} \end{align}\] For \(\mathrm{vec}(\cdot)\), we used the pre-trained fastText model⁷, which is a high-accuracy and popular word embedding model [9]; models in 157 languages are publicly distributed [10]. Second, we also used a DNN-based sentence encoder, called the universal sentence encoder [11], which utilizes the deep averaging network (DAN) [12]. The pre-trained model for English sentences we used is publicly available⁸.

6.1.0.2 Kernels

As kernels between these vectors, we used cosine similarity (cos) \[\begin{align} k(\boldsymbol{x},\boldsymbol{x}') = \cos(\boldsymbol{x},\boldsymbol{x}') \end{align}\] and the Gaussian kernel (also known as the radial basis function kernel; RBF kernel) \[\begin{align} k(\boldsymbol{x},\boldsymbol{x}') &= \exp\left(- \frac{\lVert \boldsymbol{x} -\boldsymbol{x}' \rVert_2^2}{2\sigma^2} \right) \text{,} \end{align}\] and similarly for \(\ell(\boldsymbol{y},\boldsymbol{y}')\). The experiments are ran with hyperparameter \(\sigma = 1.0\) for the RBF kernel, and \(d = 100\) for incomplete Cholesky decomposition (for more detail, see Section 10).

6.2 Ranking: Dialogue Response Selection↩︎

In the first experiment, we applied PHSIC as a ranking criterion of the task of dialogue response selection [2]; in the task, pairs comprising a context (previous utterance sequence) and its response are collected from dialogue corpora and the goal is to rank the candidate responses for each given context sentence.

The task entails sentence sequences (very sparse linguistic expressions); moreover, [4] pointed out that (RNN-based) PMI has a positive impact on suppressing dull responses (e.g., “I don’t know.”) in dialogue systems. Therefore, PHSIC, another co-occurrence measure, is also expected to be effective for this. With this setting, where the validity of PMI is confirmed, we investigate whether PHSIC can replace RNN-based PMI in terms of both learning time and robustness to data sparsity.

Experimental Settings↩︎

6.2.0.1 Dataset

For the training data, we gathered approximately \(5\times 10^5\) reply chains from Twitter, following [13]⁹. In addition, we randomly selected \(\{10^3, 10^4, 10^5\}\) reply chains from that dataset. Using these small subsets, we confirmed the effect of the difference in the size of the training set (data sparseness) on the learning time and predictive performance.

For validation and test data, we used a small (approximately \(2000\) pairs each) but highly reliable dataset created by [13]¹⁰, which consists only of conversations given high scores by human annotators. Therefore, this set was not expected to include dull responses.

For each dataset, we converted each context-message-response triple into a context-response pair by concatenating the context and message following [4]. In addition, to convert the test set (positive examples) to ten-choice multiple-choice questions, we shuffled the combinations of context and response to generate pseudo-negative examples.

6.2.0.2 Evaluation Metrics

We adopted the following evaluation metrics for the task: (i) ROC-AUC (the area under the receiver operating characteristic curve), (ii) MRR (the mean reciprocal rank), and (iii) Recall@{1,2}.

6.2.0.3 Experimental Procedure

We used the following procedure: (i) train the model with a set of context-response pairs \(\mathcal{D} = \{(x_i,y_i)\}_{i=1}^n\); (ii) for each context sentence \(x\) in the test data, rank the candidate responses \(\{y_j\}_{j=1}^{10}\) by the model; and (iii) report three evaluation metrics.

6.2.0.4 Baseline Measures

As baseline measures, both (1) an RNN language model \(\widehat{\mathbf{P}}_{\mathrm{RNN}}(y)\) [14] and (2) a conditional RNN language model \(\widehat{\mathbf{P}}_{\mathrm{RNN}}(y|x)\) [15] were trained, and (3) PMI based on these language models, RNN-PMI, was also used for experiments (see Equation 2 ). We trained these models with all combinations of the following settings: (a) the number of dimensions of the hidden layers being \(300\) or \(1200\) and (b) the initialization of the embedding layer being random (uniform on \([-0.1,0.1]\)) or fastText. For more detailed settings, see Appendix 11.

Experimental Results↩︎

6.2.0.5 Learning Time

Table 3 shows the experimental results of the learning time¹¹.

Regardless of the size of the training set \(n\), the learning time for PHSIC is much shorter than that of the RNN-based method. For example, even when the size of the training set \(n\) is \(5\times 10^5\), PHSIC is approximately \(1400\)–\(4000\) times faster than RNN-based PMI. This is because the estimators of PHSIC are reduced to a deterministic and efficient matrix calculation (Section 5), whereas neural network-based models involve the sequential optimization of parameters via gradient descent methods.

6.2.0.6 Robustness to Data Sparsity

Table 4 shows the experimental results of the predictive performance. When the size of the training data is small (\(n\!=\!10^3, 10^4\)), that is, when the data is extremely sparse, the predictive performance of PHSIC hardly deteriorates while that of PMI rapidly decays as the number of data decreases. This indicates that PHSIC is more robust to data sparsity than RNN-based PMI owing to the effect of kernels. Moreover, PHSIC with the simple cosine kernel outperforms the RNN-based model regardless of the number of data, while the learning time of PHSIC is thousands of times shorter than those of the baseline methods (Section 6.2.0.5).

Additionally we report Spearman’s rank correlation coefficient between models to verify whether PHSIC shows similar behavior to PMI. See Appendix 12 for more detail.

6.3 Data Selection for Machine Translation↩︎

The aim of our second experiment was to demonstrate that PHSIC is also beneficial as a criterion of data selection. To achieve this, we attempted to apply PHSIC to a parallel corpus filtering task that has been intensively discussed in recent (neural) machine translation (MT, NMT) studies. This task was first adopted as a shared task in the third conference on machine translation (WMT 2018)¹².

Several existing parallel corpora, especially those automatically gathered from large-scale text data, such as the Web, contain unacceptable amounts of noisy (low-quality) sentence pairs that greatly affect the translation quality. Therefore, the development of an effective method for parallel corpus filtering would potentially have a large influence on the MT community; discarding such noisy pairs may improve the translation quality and shorten the training time.

We expect PHSIC to give low scores to exceptional sentence pairs (misalignments or missing translations) during the selection process because PHSIC assigns low scores to pairs that are highly inconsistent with other pairs (see Section 4). Note that applying RNN-based PMI to a parallel corpus selection task is unprofitable since obtaining RNN-based PMI also has an identical computational cost for training a sequence-to-sequence model for MT, and thus, we cannot expect a reduction of the total training time.

Experimental Settings↩︎

6.3.0.1 Dataset

We used the ASPEC-JE corpus¹³, which is an official dataset used for the MT-evaluation shared task held in the fourth workshop on Asian translation (WAT 2017)¹⁴ [16]. ASPEC-JE consists of approximately three million (3M) Japanese–English parallel sentences from scientific paper abstracts. As discussed by [17], ASPEC-JE contains many low-quality parallel sentences that have the potential to significantly degrade the MT quality. In fact, they empirically revealed that using only the reliable part of the training parallel corpus significantly improved the translation quality. Therefore, ASPEC-JE is a suitable dataset for evaluating the data selection ability.

6.3.0.2 Model

For our data selection evaluation, we selected the Transformer architecture [18] as our baseline NMT model, which is widely-used in the NMT community and known as one of the current state-of-the-art architectures. We utilized fairseq¹⁵, a publicly available tool for neural sequence-to-sequence models, for building our models.

6.3.0.3 Experimental Procedure

We used the following procedure for this evaluation: (1) rank all parallel sentences in a given parallel corpus according to each criterion, (2) extract the top \(K\) ranked parallel sentences, (3) train the NMT model using the extracted parallel sentences, and (4) evaluate the translation quality of the test data using a typical MT automatic evaluation measure, i.e., BLEU [19]¹⁶. In our experiments we evaluated PHSIC with \(K=\) 0.5M and 1M.

6.3.0.4 Baseline Measure

As a baseline measure, we utilize a publicly available script¹⁷ of fast_align [20], which is one of the state-of-the-art word aligner. We firstly used the fast_align for the training set \(\mathcal{D} = \{(x_i,y_i)\}_i\) to obtain the word alignment between each sentence pair \((x_i,y_i)\), i.e., a set of aligned word pairs with its probabilities. We then computed the co-occurrence score of \((x_i,y_i)\) with sentence-length normalization, i.e., the average log probability of aligned word pairs.

Experimental Results↩︎

Table 5 shows the results of our data selection evaluation. It is common knowledge in NMT that more data gives better performance in general. However, we observed that PHSIC successfully extracted beneficial parallel sentences from the noisy parallel corpus; the result using 1M data extracted from the 3M corpus by PHSIC was almost the same as that using 3M data (the decrease in the BLEU score was only \(0.07\)), whereas that by random extraction reduced the BLEU score by \(1.20\).

This was actually a surprising result because PHSIC utilizes only monolingual similarity measures (kernels) without any other language resources. This indicates that PHSIC can be applied to a language pair poor in parallel resources. In addition, the surface form and grammatical characteristics between English and Japanese are extremely different¹⁸; therefore, we expect that PHSIC will work well regardless of the similarity of the language pair.

7 Related Work↩︎

7.0.0.1 Dependence Measures

Measuring independence or dependence (correlation) between two random variables, i.e., estimating dependence from a set of paired data, is a fundamental task in statistics and a very wide area of data science. To measure the complex nonlinear dependence that real data has, we have several choices.

First, information-theoretic MI [6] and its variants [21], [22] are the most commonly used dependence measures. However, to the best of our knowledge, there is no practical method of computing MIs for large-multi class high-dimensional (having a complex generative model) discrete data, such as sparse linguistic data.

Second, several kernel-based dependence measures have been proposed for measuring nonlinear dependence [5], [23], [24]. The reason why kernel-based dependence measures work well for real data is that they do not explicitly estimate densities, which is difficult for high-dimensional data. Among them, HSIC [5] is popular because it has a simple estimation method, which is used for various tasks such as feature selection [25], dimensionality reduction [26], and unsupervised object matching [27], [28]. We follow this line.

7.0.0.2 Co-occurrence Measures

First, In NLP, PMI [3] and its variants [29] are the de facto co-occurrence measures between dense linguistic expressions, such as words [29] and simple narrative-event expressions [30]. In recent years, positive PMI (PPMI) has played an important role as a component of word vectors [31].

Second, there are several studies in which the pairwise ranking problem has been solved by using deep neural networks (DNNs) in NLP. [4] proposed a PMI estimation using RNN language models; this was used as a baseline model in our experiments (see Section 6.2). Several studies have used DNN-based binary classifiers modeling \(\mathbf{P}(C=\text{positive}\mid(x,y))\) to solve the given ranking problem directly [32]–[34] (these networks are sometimes called Siamese neural networks). Our study focuses on comparing co-occurrence measures. It is unknown whether Siamese NNs capture the co-occurrence strength; therefore we did not deal with Siamese NNs in this paper.

Finally, to the best of our knowledge, [35]’s paper is the first study that suggested converting HSIC to a pointwise measure. The present study was inspired by their suggestion; here, we have (i) provided a formal definition (population) of PHSIC; (ii) analyzed the relationship between PHSIC and PMI; (iii) proposed linear-time estimation methods; and (iv) experimentally verified the computation speed and robustness to data sparsity of PHSIC for practical applications.

8 Conclusion↩︎

The NLP community has commonly employed PMI to estimate the co-occurrence strength between linguistic expressions; however, existing PMI estimators have a high computational cost when applied to sparse linguistic expressions (Section 1). We proposed a new kernel-based co-occurrence measure, the pointwise Hilbert–Schmidt independent criterion (PHSIC). As well as defining PMI as the contribution to mutual information, PHSIC is defined as the contribution to HSIC; PHSIC is intuitively a “kernelized variant of PMI” (Section 3). PHSIC can be applied to sparse linguistic expressions owing to the mechanism of smoothing by kernels. Comparing the estimators of PMI and PHSIC, PHSIC can be interpreted as a smoothed variant of PMI, which allows various similarity metrics to be plugged in as kernels (Section 4). In addition, PHSIC can be estimated in linear time owing to the efficient matrix calculation, regardless of whether we use linear or nonlinear kernels (Section 5). We conducted a ranking task for dialogue systems and a data selection task for machine translation (Section 6). The experimental results show that (i) the learning of PHSIC was completed thousands of times faster than that of the RNN-based PMI while outperforming it in ranking accuracy (Section 6.2); and (ii) even when using a nonlinear kernel, PHSIC can be applied to a large dataset. Moreover, PHSIC reduces the amount of training data to one third without sacrificing the output translation quality (Section 6.3).

8.0.0.1 Future Work

Using the PHSIC estimator in feature space (Equation 14 ), we can generate the most appropriate \(\psi(y)\) for a given \(\phi(x)\) (uniquely, up to scale). That is, if a DNN-based sentence decoder is used, \(y\) (a sentence) can be restored from \(\psi(y)\) (a feature vector) so that generative models of strong co-occurring sentences can be realized.

Acknowledgments↩︎

We are grateful to anonymous reviewers for their helpful comments. We also thank Weihua Hu for useful discussions, Kenshi Yamaguchi for collecting data, and Paul Reisert for proofreading. This work was supported in part by JSPS KAKENHI Grant Number JP15H01702 and JST CREST Grant Number JPMJCR1513, Japan.

9 Available Kernels for PHSIC↩︎

9.0.0.1 Similarity between Sentence Vectors

A variety of vector representations of phrases and sentences based on the distributional hypothesis have recently been proposed, including sentence encoders [11], [12], [36]–[38] and the sum of word embeddings; it is known as additive compositionality [8], [39], [40] that we can express the meaning of phrases and sentences well with the sum of word vectors (e.g., word2vec [41], GloVe [42], and fastText [9]). Note that various pre-trained models of sentence encoders and word embeddings have also been made available.

The cosine of these vectors, which is a positive definite kernel, can be used as a convenient and highly accurate similarity function between phrases or sentences. Other major kernels can also be used, such as the RBF kernel, the Laplacian kernel, and polynomial kernels.

9.0.0.2 Structured Kernels

Various structured kernels for NLP, such as tree kernels, which capture fine structure of sentences such as syntax, were devised in the support vector machine era [43]–[45].

9.0.0.3 Combinations

We can freely combine the previously mentioned kernels because the sum and the product of positive definite kernels are also positive definite kernels [46].

10 Derivation of Fast PHSIC Estimation in Data Space↩︎

Although estimators of HSIC and PHSIC depend on kernels \(k, \ell\) and data \(\mathcal{D}\), hereinafter, we use the following notation for the sake of simplicity: \[\begin{align} & \widehat{\mathrm{HSIC}}(X,Y) := \widehat{\mathrm{HSIC}}(X,Y;\mathcal{D},k,\ell) \text{,} \\ & \widehat{\mathrm{PHSIC}}(x,y) := \widehat{\mathrm{PHSIC}}(x,y;\mathcal{D},k,\ell) \text{.} \end{align}\]

10.0.0.1 Naïve Estimation

Fist, an estimator of PHSIC in the data space 11 is \[\begin{align} \!\widehat{\mathrm{PHSIC}}_{\mathrm{kernel}}(x,y) \!=\! \textstyle (\boldsymbol{k} - \overline{\boldsymbol{k}})^{\!\top\!} (\frac{1}{n} H) (\boldsymbol{\ell} - \overline{\boldsymbol{\ell}})\label{eq:phsic95kernel} \text{,}\!\! \end{align}\tag{16}\] where \(\boldsymbol{k} := (k(x,x_1),\dots,k(x,x_n))^\top\in\mathbb{R}^n\), so as \(\boldsymbol{\ell}\); and vector \(\overline{\boldsymbol{k}} := \frac{1}{n} K \boldsymbol{1}\) denotes empirical mean of \(\{\boldsymbol{k}_i\}_{i=1}^n\), so as \(\overline{\boldsymbol{\ell}}\). This estimation has a large computational cost. When learning, computing the vectors \(\overline{\boldsymbol{k}}, \overline{\boldsymbol{\ell}}\) takes \(\mathcal{O}(n^2)\) time and \(\mathcal{O}(n)\) space. When estimating PHSIC, computing \(\boldsymbol{k},\boldsymbol{\ell}\) and multiplying the matrix \(\frac{1}{n} H\) takes \(\mathcal{O}(n)\) time.

10.0.0.2 Fast Estimation via Incomplete Cholesky Decomposition

Equation 16 has a large computational cost because it is necessary to construct the Gram matrices \(K\) and \(L\in\mathbb{R}^{n\times n}\). In kernel methods, several methods have been proposed for approximating Gram matrices at low cost without constructing them explicitly, such as incomplete Cholesky decomposition [47].

By incomplete Cholesky decomposition, from data points \(\{x_1,\dots,x_n\}\subseteq \mathcal{X}\) and a positive definite kernel \(k\colon\mathcal{X}\times\mathcal{X}\to\mathbb{R}\), a matrix \(A = (\boldsymbol{a}_1,\dots,\boldsymbol{a}_n)^\top\in\mathbb{R}^{n\times d}\) (\(d\ll n\)) can be obtained with \(\mathcal{O}(nd^2)\) time complexity. This makes it possible to approximate the Gram matrix \(K\) by vectors \(\boldsymbol{a}_i\in\mathbb{R}^d\) without configuring the entire of \(K\): \[\begin{align} \boldsymbol{a}_i^\top\boldsymbol{a}_j &\approx k(x_i,x_j)\\ AA^\top &\approx K\text{.} \end{align}\]

Also, for HSIC, an efficient approximation method utilizing incomplete Cholesky decomposition has been proposed [5]: \[\begin{align} \widehat{\mathrm{HSIC}}_{\mathrm{ICD}}(X,Y) &= \frac{1}{n^2} \lVert(HA)^\top B\rVert_{\mathrm{F}}^2\label{eq:hsic95icd} \text{,} \end{align}\tag{17}\] where \(A = (\boldsymbol{a}_1,\dots,\boldsymbol{a}_n)^\top\in\mathbb{R}^{n\times d}\) is a matrix satisfying \(AA^\top\approx K\) computed via incomplete Cholesky decomposition, so as \(B\) (\(BB^\top\approx L\)). Equation 17 can be represented in the form of the expectation on data points: \[\begin{align} & \widehat{\mathrm{HSIC}}_{\mathrm{ICD}}(X,Y) \!=\! \frac{1}{n} \!\sum_{i=1}^n \Bigl[ \tikz[baseline] \node[fill=LimeGreen!45, rounded corners=3pt, anchor=base] () {\! \textstyle (\boldsymbol{a}_i \!-\! \overline{\boldsymbol{a}})^{\!\top} \widehat C_{\mathrm{ICD}}^{} (\boldsymbol{b}_i \!-\! \overline{\boldsymbol{b}}) \!}; \Bigr] \label{eq:hsic95icd95bilinear}\\[-8pt] & \widehat C_{\mathrm{ICD}}^{} := \frac{1}{n} (HA)^\top B \in \mathbb{R}^{d\times d} \text{,} \end{align}\tag{18}\] where vector \(\overline{\boldsymbol{a}} := \frac{1}{n} A^\top\boldsymbol{1} \in\mathbb{R}^d\) denotes empirical mean of \(\{\boldsymbol{a}_i\}_{i=1}^n\), so as \(\overline{\boldsymbol{b}} := \frac{1}{n} B^\top\boldsymbol{1}\).

Recall that \(\mathrm{PHSIC}(x,y)\) is the contribution of \((x,y)\) to \(\mathrm{HSIC}(X,Y)\) (see Section 3.3); PHSIC then can be efficiently estimated by the shaded part of Equation 18 : \[\begin{align} \textstyle \widehat{\mathrm{PHSIC}}_{\mathrm{ICD}}(x,y) \!=\! \tikz[baseline] \node[fill=LimeGreen!45, rounded corners=3pt, anchor=base] () {\! (\boldsymbol{a} \!-\! \overline{\boldsymbol{a}})^\top \widehat C_{\mathrm{ICD}}^{} (\boldsymbol{b} \!-\! \overline{\boldsymbol{b}}) \!};\label{eq:phsic95icd} \,\text{.}\! \end{align}\tag{19}\] Here, the vector \(\boldsymbol{a}\in\mathbb{R}^d\) corresponding to the new \(x\) can be calculated by “performing from halfway” on the incomplete Cholesky decomposition algorithm. Let \(x^{(1)},\dots,x^{(d)}\) denote the dominant \(x_i\)s adopted during decomposition algorithm. The \(j\)th element of \(\boldsymbol{a}\) can be computed as follows: \[\begin{align} \boldsymbol{a}[j] \!=\! \Bigl[ k(x,x^{(j)}) - \sum_{m=1}^{j-1}\boldsymbol{a}[m] A_{jm} \Bigr] \,/\, A_{jj} \text{,} \end{align}\] so as \(\boldsymbol{b} \in \mathbb{R}^d\) corresponding to the new \(y\). The estimation via incomplete Cholesky decomposition 19 is extremely efficient compared to the naive estimation 16 ; Equation 19 ’s computational complexity is equivalent to the estimation in the feature space 14 .

11 Detailed Settings for Learning RNNs↩︎

Detailed settings for learning RNNs used in this research are as follows.

• Hidden layers: single layer LSTMs [48]

• Vocabulary: words with a frequency: \(10\) or more (\(n=5\times 10^5\)), \(2\) or more (otherwise)

• Dropout rate: \(0.1\) (\(300\)-dim), \(0.3\) (\(1200\)-dim)

• Batch size: \(64\)

• Max epoch number: \(5\) (\(n=5\times 10^5\)), \(30\) (otherwise)

• Deep learning framework: Chainer [49]

12 Correlation Between Models in Dialogue Response Selection Task↩︎

Table 6 shows Spearman’s rank correlation coefficient (Spearman’s \(\rho\)) between the co-occurrence scores on the test set computed by the models in the dialogue response selection task (Section 6.2).

This shows that the behavior of RNN-based PMI and PHSIC are considerably different. Furthermore, interestingly, the behavior of PHSICs using different kernels is also different. Possible reasons for these observations are as follows: (1) the difference in the dependence measures (MI or HSIC) on which each model is based; (2) the validity or numerical stability of estimating PMI with RNN language models; and (3) differences in the behavior of PHSIC originating from differences in the plugged in kernels. A more detailed analysis of the compatibility between tasks and measures (or kernels) is attractive future work.

References↩︎