The success of distributed vector representations in natural language processing (NLP) tasks has motivated their use for other areas such as biological sequence analysis [1]. Most of them rely on the distributional hypothesis [8]: "words that appear in similar context are similar". We aim to relax this constraint with a general framework to learn vector representations of non-numeric entities including text, DNA sequences, and protein sequences based on similarity functions that can be expressed as rational kernels [5]. Supported by the robust theoretical framework behind rational kernels, we obtain vector representations via kernel PCA (KPCA) [11] that, together with a simple k nearest neighbors (k NN) classifier, constitute an efficient and explainable classification pipeline showing competitive performance in two different tasks: protein family classification and Dutch spelling correction.
Our approach extends our previous work on KPCA embeddings, where we studied vector representations for words and DNA sequences via KPCA replacing the dot product by a specific similarity function [3]. There are also a myriad of previous kernel methods for NLP tasks such as text classification [6,10] and named entity recognition [7]. However, they are either restricted to a specific kernel function (i.e. to a concept of similarity) or lack in explicit vector representations.
Let X be a dataset consisting of n elements, to which we will further refer as the full vocabulary; and k a rational kernel (a particular similarity function). Computing a kernel matrix K from X may be computationally prohibitive for large datasets due to its time and space complexity (O(n 2 )). Hence, we select only the m elements considered "most representative" (in a domain-specific formulation) from X to construct our representative vocabulary V and compute a kernel matrix K V from all element pairs from V . After centering and diagonalizing K V , we construct our projection matrix P V . This is required to generate m-dimensional representations for the full vocabulary. In a last step, we assign the first d ≤ m components of each computed vector to each full vocabulary element. There are the resulting d-dimensional vector representations obtained with our approach. When k is suitable for the task, d being of a lower order of magnitude than m can lead to optimal results, as we will see in Section 4.1. The choice of m can be adjusted to fit the computational resources of the user.
The produced representations tend to cluster naturally according to the domain-specific concept of similarity applied by the selected rational kernel, as we can see in Fig. 1. This has two main advantages:
1. A simple k NN classifier (eventually 1NN) can suffice for classification tasks. 2. Learning the vector representations and k NN constitute an explainable classification pipeline: an entity is assigned to a particular class because it is similar to the labeled entities used to train the classifier.
In this task, we classify protein sequences to their corresponding families with the same Swiss-Prot dataset as in [1], containing 7,027 protein families and 324,018 protein sequences5 . The system is evaluated for each protein family by 10-fold cross-validation on a balanced dataset consisting of all amino acid sequences of the family and as many randomly sampled sequences from all other families. We produced protein representations with 25 dimensions applying our approach with bigram and trigram similarity and trained a nearest neighbor classifier (1NN). We generated our representative vocabulary by taking the shortest sequence of the 1,000 most frequent protein families. We evaluated this pipeline in the same setting as [1]. We report the weighted average accuracy results in Table 1. Also, the results of the evaluation limited to subsets of the full dataset are presented (e.g. sequences belonging to the 1,000 most frequent protein families).
The results from Table 1 show that our approach with the bigram similarity reaches the same accuracy as the baseline and or even outperforms it when we restrict the dataset to the first 3,000 or 4,000 most frequent protein families. Considering that the reported BioVec representations are four times longer than ours, our approach to encode proteins seems to be more efficient.
In contrast to [1], we do not train any support-vector machine (SVM) but a 1NN classifier. To assess the impact of the different classification algorithm, we evaluated a pretrained BioVec model6 with our setup. The results (Table 2), showing that 1NN is more suitable than SVMs for this task, are in line with our previous experiments on classification tasks using distributed vector representations, where simple algorithms such as k NN and logistic regression outperform more complex ones such as random forests or neural networks [3,4].
Table 3. Results of our system compared to Valkuil (CLIN28 shared task baseline) in terms of successful corrections (TP), wrong corrections (FN), and accuracy [2]
We also evaluated our approach by participating in the CLIN28 shared task, where our system obtained the best F1 score among the competing teams [2]. The task focused on correcting errors in extracts from Dutch Wikipedia pages. We used an older implementation of our approach that we keep for reproducibility 7 .
Spell checkers involve two steps: misspelling detection and correction. The latter generally requires ranking a set of correction candidates. Generating them implies finding all valid words differing from the detected misspelling less than a determined edit distance, which is mostly set to 1 for real-world applications to limit computation time [12]. We avoid this strong constraint with our approach.
In our RatVec framework, our full vocabulary is wdutch, a word list from the OpenTaal project, from which the 3000 most frequent words form our representative vocabulary. The applied rational kernel is the composition of the bigram similarity [9] with the homogeneous polynomial kernel of degree 2. We generated a vector representation for each full vocabulary word with 2000 dimensions.
Once a misspelling is detected, we compute its RatVec representation and search for the closest precomputed vector. Its related word (its nearest neighbor) is our correction to the misspelling. Formally, this is equivalent to training a 1NN classifier where each valid word is assigned a different label.
Our RatVec framework is only relevant during the correction phase for spelling mistakes that are related to the word form. Hence, we restrict our analysis to the correction results on the five error categories where the word form is relevant, namely those displayed in Table 3. Although the baseline system Valkuil achieves a better average accuracy than our approach for the analyzed misspellings, RatVec outperforms Valkuil in some categories where it completely fails (redundant punctuation errors) or where it cannot be even evaluated because it failed to detect any error (capitalization and archaic spelling errors). From these results, we interpret that our word vectors encode word forms in a suitable way so that similar words can be retrieved.
We showed that our approach involving rational kernels on KPCA for vector space embeddings provides rich representations for two different kinds of en-7 https://github.com/fraunhofer-iais/kpca embeddings tities: proteins and words. In the first application, we presented how to learn protein vectors from amino acid sequences and how to apply them to predict their protein family. In the second, we learned word representations that encode word form information so that they can be applied to correct misspellings once these are detected. In both tasks, our results are comparable to state-of-the-art approaches. Thanks to the simplicity of k NN classifiers and the interpretable similarity concept we apply to generate the vector representations, our approach may be advantageous for some real-world applications compared to more complex machine learning models such as deep neural networks.
In future work, we will explore possibilities of learning optimal similarity metrics (modeled as transducers) that, incorporated in our presented approach, solve a particular task.