Most of the well-known word embeddings from the last few years rely on a prede ned vocabulary so that out-of-vocabulary words are usually skipped when they need to be processed. This may cause a signi cant quality drop in document representations that are built upon them. Additionally, most of these models do not incorporate information about the morphology of the words within the word vectors or if they do, they require labeled data. We propose an unsupervised method to generate continuous vector representations that can be applied to any sequence of nite domain (such as text or DNA sequences) by means of kernel principal component analysis (KPCA). We also show that, apart from their potential value as a preprocessing step within a more complex natural language processing system, our KPCA embeddings also can capture valuable linguistic information without any supervision, in particular word morphology of German verbs. When they are applied to DNA sequences, they also encode enough information to detect splice junctions.
Machine learning approaches for natural language processing (NLP) generally demand a numeric vector representation for words. We can distinguish any two di erent words from a xed vocabulary by assigning them a one-hot vector, where all entries of the vector are zero-valued but in a single position that identi es the word. This is a very sparse representation that encodes no information about the words but their position in the vocabulary.
A more information-rich alternative to one-hot vectors are the so-called word embeddings. They are distributed vector representations, which are dense, lowdimensional, real-valued and can capture latent features of the word [13]. Based on the distributional hypothesis [5] (words that appear in similar contexts have similar meanings), they exploit word co-occurrence so that similar words are mapped close to each other in the word vector space. Part of the success of the word embeddings is due to their e cient shallow neural network architectures such as the continuous skip-gram model and the continuous bag of words model [9], widely popularized after the release of word2vec1. Word embeddings also inspired research in other areas di erent from NLP to learn vector representations such as node representations from a graph [4].
Although syntax and semantics can be encoded with word2vec embeddings, they do not incorporate morphological information about the word. As a consequence, morphologically similar words may not be nearby in the word vector space. Some approaches make use of existing linguistic resources so that the word embeddings capture not only contextual information but also morphological information[3, 7]. Due to the their dependence on language-speci c resources, they will not work for languages whose available linguistic resources are scarce.
The subword-based models such as FastText [1, 6] learn indirectly morphology by learning not only word vectors but also n-gram vectors. This enables not only complete unsupervised learning but also the possibility of inferring out-ofvocabulary (OOV) words, which is an important issue for all other approaches mentioned, notably when noisy informal text needs to be processed. Despite these advantages of subword-based models, some morphologically rich languages (where these models are supposed to perform specially well) may contain very long words. This leads to a dramatic increase of the number of necessary n-gram representations, increasing time and space complexity as well.
We propose an alternative unsupervised method by means of kernel principal component analysis (KPCA) that encodes morphology while learning word representations and that generate new vectors for OOV words after training. In addition, our approach is general enough to learn vector representations for any sequence whose elements belong to a xed prede ned nite set. In particular, we test our KPCA embeddings in two di erent tasks: classifying the verb category for German verbs and detecting splice junctions in DNA sequences. 2
KPCA indirectly maps vectors to a feature space (of higher dimension) in order
to obtain the principal components from that space [12]. No explicit calculation
in the feature space is required since we only need to be able to compute the
inner product in the feature space and this can be achieved by using kernel
functions. We can exploit the freedom to select any inner product of our choice
so that we can also perform KPCA to non-numeric entities. Formally, given a
zero-mean column data matrix X = [x1; x2; : : : ; xn] containing n m-dimensional
data points, principal component analysis (PCA) deals with representing the
data through principal components maximizing the variance in X by solving
Cv =
v;
(
=
XTX : 1 n
KK =
K : and eliminating K as 1
K = ; (
For the particular case of words and DNA sequences, the inner product can be any string similarity. For our experiments, we adapt the the S rensen-Dice coe cient by considering not only bigrams, but n-grams of any length in general. Let V a vocabulary of words, Gn(w) the n-grams of a word w 2 V. We de ne our similarity function s of two words x; y 2 V as follows: s(x; y) = X n2N+ n 2jGn(x) \ Gn(y))j ; jGn(x) [ Gn(y)j
X n n = 1 where
2 Rm. Substituting (
XXTv = X
= v;
=
X ; Sij = s(wi; wj ) 8wi; wj 2 V: Then, we calculate the kernel matrix K by applying a non-linear kernel function (for instance RBF kernel or polynomial kernel) to the similarity matrix S. After computing the eigenvectors and eigenvalues of the resulting matrix K, we construct our projection matrix P by selecting d eigenvectors v1; : : : ; vd and dividing them by their respective eigenvalues 1; : : : ; d:
P = [ v1 ; : : : ; vd ]:
1 d
We can now generate a KPCA embedding for any word wt. We only need to
compute the similarity function of the word against all the words processed from
(
austeigen steige einusmtesitgeeige austeige gestiegen umgestiegen eingestaieugsegneusmtieggeezongen eingezogaeunsgezogen ein
um aus geboren
gelesen gebore
geliebtlesen gegdeamcahctht denken lieben denke lesemachen liebe
gesehen mache
umziehen
einziehenausziehen
sehen
sehe
einziehe auszieuhmeziehe
0.20
0.15
0.10
0.05
0.00
0.05
the vocabulary V and apply the kernel function k to the resulting vector. This
results in a kernelized distance vector rt. The product of rt with the projection
matrix P constitutes the d-dimensional KPCA embedding ut of the word wt.
rt = k(s(wt; V))
and
ut = P>rt:
(
We show how our KPCA embeddings can be used for di erent kinds of sequential data. In particular, we apply our approach to represent words to classify di erent types of verb forms and to represent DNA sequences to recognize splice junctions. 3.Sg.Pres.Ind
Psp
Inf 3.Sg.Past.Ind 3.Pl.Pres.Ind 3.Sg.Pres.Subj
3.Pl.Past.Ind 3.Pl.Past.Subj 3.Sg.Past.Subj
Infzu 1.Pl.Pres.Ind 3.Pl.Pres.Subj 1.Sg.Pres.Ind 1.Sg.Past.Ind
2.Sg.Imp 1.Pl.Past.Ind 2.Sg.Pres.Ind 1.Pl.Past.Subj
2.Pl.Imp 2.Pl.Pres.Ind 1.Sg.Past.Subj
Pos 2.Sg.Pres.Subj 1.Sg.Pres.Subj
Pl.3.Pres.Ind 2.Sg.Past.Ind
Prp 2.Pl.Past.Ind 1.Pl.Pres.Subj 2.Sg.Past.Subj
Pl.1.Pres.Ind 0.00 0.05 0.10
0.15 Ratio 0.20 0.25 We test how our KPCA embeddings can encode morphology with a ne-grain POS tagging task. We restrict our vocabulary to the tokens tagged as verbs from the TIGER treebank [2]. This simpli es the problem to classify the correct morphological tag (consisting of grammatical person, number, tense and mode when they apply) of a German verb only from its KPCA embedding.
First, we extract all tokens tagged as verb (corresponding to the TIGER tags VVFIN, VAFIN, VMFIN, VVIMP, VAIMP, VVINF, VVIZU, VAINF, VMINF, VVPP, VMPP, VAPP) and remove all duplicates. This leads to 13370 unique verbs with 31 di erent morphological tags, whose distribution is showed in gure 2. Then, we apply the approach described in section 2. We build a training set consisting of 80% of the verbs and a test set with the remaining 20%. We consider only bigrams and trigrams to compute the similarity function for each pair of verbs by selecting ve di erent weight distributions (di erent values for 2 and 3 in equation 7). We also incorporate an additional character at the beginning and at the end of each verb when producing the n-grams. After running KPCA on the training set, we infer vector representations of the verbs from the test set. By using the KPCA embeddings as a features and the morphological tag as label, we train k-nearest neighbors classi ers to predict the morphological tag of a word from only the KPCA embedding. As baseline representations, we also learn a word2vec [10, 9] model for each di erent vector size. These word vectors were learned applying the default hyperparameter values.
From Table 1 we can observe that a mean accuracy above 77% can be
achieved by classi ers taking only the nearest neighbor (k = 1). This can be
interpreted as a high accuracy considering the extremely unbalanced label
distribution (see gure 2). Among the trained classi ers, we can also nd some
improvement when the trigram similarity weight (
Splice junction recognition on DNA sequences We encode DNA sequences from the dataset \Molecular Biology (Splice-junction Gene Sequences) Data Set" from UCI Machine Learning Repository [8]2. This dataset consists of DNA subsequences represented as 30 characters out of the four nucleobases (A, T, C, G) plus other four characters (D, N, S, R) which mark ambiguity. The sequences may contain a spline junction between the 30 rst and the 30 last characters. They are thus labeled with three di erent categories depending if they contain exon/intron boundary (EI class), intron/exon boundary (IE class) or neither (N). The distribution of the classes is displayed in Table 2.
We compute the similarity function considering all n-grams, giving all terms
from (
Nr. sequences Ratio
We showed that our KPCA embedding approach to learn vector word representations can encode the morphology of the words in an unsupervised fashion, at least for the particular case of German verbs. The learned KPCA embeddings could beat by far any word2vec model in the task of predicting the grammatical tag. The highest accuracy was achieved by taking the nearest neighbor to predict the verb category. Due to this fact, we suspect that our proposed word representations tend to form clusters according to their word form, from which predicting a grammatical tag is a feasible task with simple classi ers such as k-nearest neighbors classi ers.
Since many NLP applications require also syntactic and semantic information about the words, good word embeddings should also incorporate information not only from the form of the represented word but also about the context in which they appear. In this direction, we will enhance our approach by adapting our similarity function so that it also considers the frequency of each evaluated word pair appearing in the same context or, alternatively, by taking our KPCA representations as input representation of a neural network architecture. For the latter, our KPCA would \just" substitute the one-hot encoding of most of neural EI IE
N language models. Additionally, we will also extend our research evaluating the same approach on other morphologically rich in ected languages (like any of the Romance languages) or agglutinative languages (such as Turkish). We assume they may pro t the most from our approach since their word forms reveal more grammatical information than word forms from more analytic languages such as English. To this extent, KPCA embeddings may also help to overcome the lack of linguistic resources of some of these non-English languages.
Furthermore, we presented how we can learn KPCA embeddings for DNA sequences. These representations proved to be useful in the task of predicting splice junctions. It would be also interesting to generalize our method to encode other types of discrete sequential data where also n-grams could be extracted, for instance text paragraphs (word n-grams), protein sequences (amino acid ngrams) or even sheet music (note n-grams).