{'fraction_non_alphanumeric': 0.03898569680604194, 'fraction_numerical': 0.009999578076874394, 'mean_word_length': 4.578253706754531, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Convolution Kernels with Feature Selection for Natural Language Processing Tasks

Convolution kernels, such as sequence and tree kernels, are advantageous for both the concept and accuracy of many natural language processing (NLP) tasks. Experiments have, however, shown that the over-fitting problem often arises when these kernels are used in NLP tasks. This paper discusses this issue of convolution kernels, and then proposes a new approach based on statistical feature selection that avoids this issue. To enable the proposed method to be executed efficiently, it is embedded into an original kernel calculation process by using sub-structure mining algorithms. Experiments are undertaken on real NLP tasks to confirm the problem with a conventional method and to compare its performance with that of the proposed method.


Introduction
Over the past few years, many machine learning methods have been successfully applied to tasks in natural language processing (NLP). Especially, state-of-the-art performance can be achieved with kernel methods, such as Support Vector Machine (Cortes and Vapnik, 1995).
Another feature of this kernel methodology is that it not only provides high accuracy but also allows us to design a kernel function suited to modeling the task at hand. Since natural language data take the form of sequences of words, and are generally analyzed using discrete structures, such as trees (parsed trees) and graphs (relational graphs), discrete kernels, such as sequence kernels (Lodhi et al., 2002), tree kernels (Collins and Duffy, 2001), and graph kernels (Suzuki et al., 2003a), have been shown to offer excellent results.
These discrete kernels are related to convolution kernels (Haussler, 1999), which provides the concept of kernels over discrete structures. Convolution kernels allow us to treat structural features without explicitly representing the feature vectors from the input object. That is, convolution kernels are well suited to NLP tasks in terms of both accuracy and concept.
Unfortunately, experiments have shown that in some cases there is a critical issue with convolution kernels, especially in NLP tasks (Collins and Duffy, 2001;Cancedda et al., 2003;Suzuki et al., 2003b). That is, the over-fitting problem arises if large "substructures" are used in the kernel calculations. As a result, the machine learning approach can never be trained efficiently.
To solve this issue, we generally eliminate large sub-structures from the set of features used. However, the main reason for using convolution kernels is that we aim to use structural features easily and efficiently. If use is limited to only very small structures, it negates the advantages of using convolution kernels.
This paper discusses this issue of convolution kernels, and proposes a new method based on statistical feature selection. The proposed method deals only with those features that are statistically significant for kernel calculation, large significant substructures can be used without over-fitting. Moreover, the proposed method can be executed efficiently by embedding it in an original kernel calculation process by using sub-structure mining algorithms.
In the next section, we provide a brief overview of convolution kernels. Section 3 discusses one issue of convolution kernels, the main topic of this paper, and introduces some conventional methods for solving this issue. In Section 4, we propose a new approach based on statistical feature selection to offset the issue of convolution kernels using an example consisting of sequence kernels. In Section 5, we briefly discuss the application of the proposed method to other convolution kernels. In Section 6, we compare the performance of conventional methods with that of the proposed method by using real NLP tasks: question classification and sentence modality identification. The experimental results described in Section 7 clarify the advantages of the proposed method.

Convolution Kernels
Convolution kernels have been proposed as a concept of kernels for discrete structures, such as sequences, trees and graphs. This framework defines the kernel function between input objects as the convolution of "sub-kernels", i.e. the kernels for the decompositions (parts) of the objects.
Let X and Y be discrete objects. Conceptually, convolution kernels K(X, Y ) enumerate all substructures occurring in X and Y and then calculate their inner product, which is simply written as: φ represents the feature mapping from the discrete object to the feature space; that is, φ(X) = (φ 1 (X), . . . , φ i (X), . . .). With sequence kernels (Lodhi et al., 2002), input objects X and Y are sequences, and φ i (X) is a sub-sequence. With tree kernels (Collins and Duffy, 2001), X and Y are trees, and φ i (X) is a sub-tree.
When implemented, these kernels can be efficiently calculated in quadratic time by using dynamic programming (DP).
Finally, since the size of the input objects is not constant, the kernel value is normalized using the following equation.
The value ofK(X, Y ) is from 0 to 1,K(X, Y ) = 1 if and only if X = Y .

Sequence Kernels
To simplify the discussion, we restrict ourselves hereafter to sequence kernels. Other convolution kernels are briefly addressed in Section 5. Many kinds of sequence kernels have been proposed for a variety of different tasks. This paper basically follows the framework of word sequence kernels (Cancedda et al., 2003), and so processes gapped word sequences to yield the kernel value.
Let Σ be a set of finite symbols, and Σ n be a set of possible (symbol) sequences whose sizes are n or less that are constructed by symbols in Σ. The meaning of "size" in this paper is the number of symbols in the sub-structure. Namely, in the case of sequence, size n means length n. S and T can represent any sequence. s i and t j represent the ith and jth symbols in S and T , respectively. Therefore, a b, c, aa, ab, ac, ba, bc, aba, aac, abc, bac, abac a, b, c, ab, ac, bc, abc) ( a, b, c, aa, ab, ac, ba, bc, aba, aac, abc, bac, abac)  By using the above notations, sequence kernels can be defined as: where λ is the decay factor that handles the gap present in a common sub-sequence u, and γ(i) = l(i)−|u|. In this paper, | means "such that". Figure 1 shows a simple example of the output of this kernel.
However, in general, the number of features |Σ n |, which is the dimension of the feature space, becomes very high, and it is computationally infeasible to calculate Equation (3) explicitly. The efficient recursive calculation has been introduced in (Cancedda et al., 2003). To clarify the discussion, we redefine the sequence kernels with our notation.
The sequence kernel can be written as follows: where S i and T j represent the sub-sequences S i = s 1 , s 2 , . . . , s i and T j = t 1 , t 2 , . . . , t j , respectively. Let J m (S i , T j ) be a function that returns the value of common sub-sequences if s i = t j .
Then, J m (S i , T j ) and J m (S i , T j ) are introduced to calculate the common gapped sub-sequences between S i and T j .

Problem of Applying Convolution Kernels to NLP tasks
This section discusses an issue that arises when applying convolution kernels to NLP tasks. According to the original definition of convolution kernels, all the sub-structures are enumerated and calculated for the kernels. The number of substructures in the input object usually becomes exponential against input object size. As a result, all kernel valuesK(X, Y ) are nearly 0 except the kernel value of the object itself,K(X, X), which is 1. In this situation, the machine learning process becomes almost the same as memory-based learning. This means that we obtain a result that is very precise but with very low recall.
To avoid this, most conventional methods use an approach that involves smoothing the kernel values or eliminating features based on the sub-structure size.
For sequence kernels, (Cancedda et al., 2003) use a feature elimination method based on the size of sub-sequence n. This means that the kernel calculation deals only with those sub-sequences whose size is n or less. For tree kernels, (Collins and Duffy, 2001) proposed a method that restricts the features based on sub-trees depth. These methods seem to work well on the surface, however, good results are achieved only when n is very small, i.e. n = 2.
The main reason for using convolution kernels is that they allow us to employ structural features simply and efficiently. When only small sized substructures are used (i.e. n = 2), the full benefits of convolution kernels are missed.
Moreover, these results do not mean that larger sized sub-structures are not useful. In some cases we already know that larger sub-structures are significant features as regards solving the target problem. That is, these significant larger sub-structures, which the conventional methods cannot deal with efficiently, should have a possibility of improving the performance furthermore. The aim of the work described in this paper is to be able to use any significant sub-structure efficiently, regardless of its size, to solve NLP tasks.

Proposed Feature Selection Method
Our approach is based on statistical feature selection in contrast to the conventional methods, which use sub-structure size.
For a better understanding, consider the twoclass (positive and negative) supervised classification problem. In our approach we test the statistical deviation of all the sub-structures in the training samples between the appearance of positive samples and negative samples. This allows us to select only the statistically significant sub-structures when calculating the kernel value.
Our approach, which uses a statistical metric to select features, is quite natural. We note, however, that kernels are calculated using the DP algorithm. Therefore, it is not clear how to calculate kernels efficiently with a statistical feature selection method. First, we briefly explain a statistical metric, the chisquared (χ 2 ) value, and provide an idea of how to select significant features. We then describe a method for embedding statistical feature selection into kernel calculation.

Statistical Metric: Chi-squared Value
There are many kinds of statistical metrics, such as chi-squared value, correlation coefficient and mutual information. (Rogati and Yang, 2002) reported that chi-squared feature selection is the most effective method for text classification. Following this information, we use χ 2 values as statistical feature selection criteria. Although we selected χ 2 values, any other statistical metric can be used as long as it is based on the contingency table shown in Table 1.
We briefly explain how to calculate the χ 2 value by referring to Table 1. In the table, c andc represent the names of classes, c for the positive class a, b, c, aa, ab, ac, ba, bc, aba, aac, abc, bac, abac , c, ab, ac, bc, abc) ( a, b, c, aa, ab, ac, ba, bc, aba, aac, abc, bac, abac) Since N and M are constant for (fixed) data, χ 2 can be written as a function of x and y, χ 2 expresses the normalized deviation of the observation from the expectation. We simply represent χ 2 (x, y) as χ 2 (u).

Feature Selection Criterion
The basic idea of feature selection is quite natural. First, we decide the threshold τ of the χ 2 value. If χ 2 (u) < τ holds, that is, u is not statistically significant, then u is eliminated from the features and the value of u is presumed to be 0 for the kernel value. The sequence kernel with feature selection (FSSK) can be defined as follows: The difference between Equations (3) and (9) is simply the condition of the first summation. FSSK selects significant sub-sequence u by using the condition of the statistical metric τ ≤ χ 2 (u). Figure 2 shows a simple example of what FSSK calculates for the kernel value.

Efficient χ 2 (u) Calculation Method
It is computationally infeasible to calculate χ 2 (u) for all possible u with a naive exhaustive method. In our approach, we use a sub-structure mining algorithm to calculate χ 2 (u). The basic idea comes from a sequential pattern mining technique, PrefixSpan (Pei et al., 2001), and a statistical metric pruning (SMP) method, Apriori SMP (Morishita and Sese, 2000). By using these techniques, all the significant sub-sequences u that satisfy τ ≤ χ 2 (u) can be found efficiently by depth-first search and pruning. Below, we briefly explain the concept involved in finding the significant features.
First, we denote uv, which is the concatenation of sequences u and v. Then, u is a specific sequence and uv is any sequence that is constructed by u with any suffix v. The upper bound of the χ 2 value of uv can be defined by the value of u (Morishita and Sese, 2000).
where x u and y u represent the value of x and y of u. This inequation indicates that if χ 2 (u) is less than a certain threshold τ , all sub-sequences uv can be eliminated from the features, because no subsequence uv can be a feature.
The PrefixSpan algorithm enumerates all the significant sub-sequences by using a depth-first search and constructing a TRIE structure to store the significant sequences of internal results efficiently. Specifically, PrefixSpan algorithm evaluates uw, where uw represents a concatenation of a sequence u and a symbol w, using the following three conditions.
With 1, sub-sequence uw is selected as a significant feature. With 2, sub-sequence uw and arbitrary subsequences uwv, are less than the threshold τ . Then w is pruned from the TRIE, that is, all uwv where v represents any suffix pruned from the search space. With 3, uw is not selected as a significant feature because the χ 2 value of uw is less than τ , however, uwv can be a significant feature because the upperbound χ 2 value of uwv is greater than τ , thus the search is continued to uwv. Figure 3 shows a simple example of PrefixSpan with SMP that searches for the significant features  Figure 3: Efficient search for statistically significant sub-sequences using the PrefixSpan algorithm with SMP by using a depth-first search with a TRIE representation of the significant sequences. The values of each symbol represent χ 2 (u) and χ 2 (u) that can be calculated from the number of x u and y u . The TRIE structure in the figure represents the statistically significant sub-sequences that can be shown in a path from ⊥ to the symbol.
We exploit this TRIE structure and PrefixSpan pruning method in our kernel calculation.

Embedding Feature Selection in Kernel
Calculation This section shows how to integrate statistical feature selection in the kernel calculation. Our proposed method is defined in the following equations.
Let K m (S i , T j ) be a function that returns the sum value of all statistically significant common subsequences u if s i = t j .
where Γ m (S i , T j ) represents a set of sub-sequences whose size |u| is m and that satisfy the above condition 1. The Γ m (S i , T j ) is defined in detail in Equation (15). Then, let J u (S i , T j ), J u (S i , T j ) and J u (S i , T j ) be functions that calculate the value of the common sub-sequences between S i and T j recursively, as well as equations (5) to (7) for sequence kernels. We introduce a special symbol Λ to represent an "empty sequence", and define Λw = w and |Λw| = 1. (12) where I(w) is a function that returns a matching value of w. In this paper, we define I(w) is 1.
Γ m (S i , T j ) has realized conditions 2 and 3; the details are defined in Equation (16).
The following five equations are introduced to select a set of significant sub-sequences. Γ m (S i , T j ) and Γ m (S i , T j ) are sets of sub-sequences (features) that satisfy condition 1 and 3, respectively, when calculating the value between S i and T j in Equations (11) and (12).
where F represents a set of sub-sequences. Notice that Γ m (S i , T j ) and Γ m (S i , T j ) have only subsequences u that satisfy τ ≤ χ 2 (uw) or τ ≤ χ 2 (uw), respectively, if s i = t j (= w); otherwise they become empty sets.
The following two equations are introduced for recursive set operations to calculate Γ m (S i , T j ) and In the implementation, Equations (11) to (14) can be performed in the same way as those used to calculate the original sequence kernels, if the feature selection condition of Equations (15) to (19) has been removed. Then, Equations (15) to (19), which select significant features, are performed by the Pre-fixSpan algorithm described above and the TRIE representation of statistically significant features.
The recursive calculation of Equations (12) to (14) and Equations (16) to (19) can be executed in the same way and at the same time in parallel. As a result, statistical feature selection can be embedded in oroginal sequence kernel calculation based on a dynamic programming technique.

Properties
The proposed method has several important advantages over the conventional methods.
First, the feature selection criterion is based on a statistical measure, so statistically significant features are automatically selected.
Second, according to Equations (10) to (18), the proposed method can be embedded in an original kernel calculation process, which allows us to use the same calculation procedure as the conventional methods. The only difference between the original sequence kernels and the proposed method is that the latter calculates a statistical metric χ 2 (u) by using a sub-structure mining algorithm in the kernel calculation.
Third, although the kernel calculation, which unifies our proposed method, requires a longer training time because of the feature selection, the selected sub-sequences have a TRIE data structure. This means a fast calculation technique proposed in (Kudo and Matsumoto, 2003) can be simply applied to our method, which yields classification very quickly. In the classification part, the features (subsequences) selected in the learning part must be known. Therefore, we store the TRIE of selected sub-sequences and use them during classification.

Proposed Method Applied to Other Convolution Kernels
We have insufficient space to discuss this subject in detail in relation to other convolution kernels. However, our proposals can be easily applied to tree kernels (Collins and Duffy, 2001) by using string encoding for trees. We enumerate nodes (labels) of tree in postorder traversal. After that, we can employ a sequential pattern mining technique to select statistically significant sub-trees. This is because we can convert to the original sub-tree form from the string encoding representation. As a result, we can calculate tree kernels with statistical feature selection by using the original tree kernel calculation with the sequential pattern mining technique introduced in this paper. Moreover, we can expand our proposals to hierarchically structured graph kernels (Suzuki et al., 2003a) by using a simple extension to cover hierarchical structures.

Experiments
We evaluated the performance of the proposed method in actual NLP tasks, namely English question classification (EQC), Japanese question classification (JQC) and sentence modality identification (MI) tasks.
We compared the proposed method (FSSK) with a conventional method (SK), as discussed in Section 3, and with bag-of-words (BOW) Kernel (BOW-K) (Joachims, 1998) as baseline methods. Support Vector Machine (SVM) was selected as the kernel-based classifier for training and classification. Table 2 shows some of the parameter values that we used in the comparison. We set thresholds of τ = 2.7055 (FSSK1) and τ = 3.8415 (FSSK2) for the proposed methods; these values represent the 10% and 5% level of significance in the χ 2 distribution with one degree of freedom, which used the χ 2 significant test.

Question Classification
Question classification is defined as a task similar to text categorization; it maps a given question into a question type.
We evaluated the performance by using data provided by (Li and Roth, 2002) for English and (Suzuki et al., 2003b) for Japanese question classification and followed the experimental setting used in these papers; namely we use four typical question types, LOCATION, NUMEX, ORGANI-ZATION, and TIME TOP for JQA, and "coarse" and "fine" classes for EQC. We used the one-vs-rest classifier of SVM as the multi-class classification method for EQC. Figure 4 shows examples of the question classification data used here.

Sentence Modality Identification
For example, sentence modality identification techniques are used in automatic text analysis systems that identify the modality of a sentence, such as "opinion" or "description". The data set was created from Mainichi news articles and one of three modality tags, "opinion", "decision" and "description" was applied to each sentence. The data size was 1135 sentences consisting of 123 sentences of "opinion", 326 of "decision" and 686 of "description". We evaluated the results by using 5-fold cross validation.

Results and Discussion
Tables 3 and 4 show the results of Japanese and English question classification, respectively. Table 5 shows the results of sentence modality identification. n in each table indicates the threshold of the sub-sequence size. n = ∞ means all possible subsequences are used.
First, SK was consistently superior to BOW-K. This indicates that the structural features were quite efficient in performing these tasks. In general we can say that the use of structural features can improve the performance of NLP tasks that require the details of the contents to perform the task.
Most of the results showed that SK achieves its maximum performance when n = 2. The performance deteriorates considerably once n exceeds 4. This implies that SK with larger sub-structures degrade classification performance. These results show the same tendency as the previous studies discussed in Section 3. Table 6 shows the precision and recall of SK when n = ∞. As shown in Table 6, the classifier offered high precision but low recall. This is evidence of over-fitting in learning.
As shown by the above experiments, FSSK pro- vided consistently better performance than the conventional methods. Moreover, the experiments confirmed one important fact. That is, in some cases maximum performance was achieved with n = ∞. This indicates that sub-sequences created using very large structures can be extremely effective. Of course, a larger feature space also includes the smaller feature spaces, Σ n ⊂ Σ n+1 . If the performance is improved by using a larger n, this means that significant features do exist. Thus, we can improve the performance of some classification problems by dealing with larger substructures. Even if optimum performance was not achieved with n = ∞, difference between the performance of smaller n are quite small compared to that of SK. This indicates that our method is very robust as regards substructure size; It therefore becomes unnecessary for us to decide sub-structure size carefully. This indicates our approach, using large sub-structures, is better than the conventional approach of eliminating sub-sequences based on size.

Conclusion
This paper proposed a statistical feature selection method for convolution kernels. Our approach can select significant features automatically based on a statistical significance test. Our proposed method can be embedded in the DP based kernel calculation process for convolution kernels by using substructure mining algorithms.  Experiments show that our method is superior to conventional methods. Moreover, the results indicate that complex features exist and can be effective. Our method can employ them without over-fitting problems, which yields benefits in terms of concept and performance.