This paper presents our approach to the PAN 2012 Traditional Authorship Attribution tasks and the Sexual Predator Identification task. We approached these tasks with machine learning methods that work at the character level. More precisely, we treated texts as just sequences of symbols (strings) and used string kernels in conjunction with different kernel-based learning methods: supervised and unsupervised. The results were extremely good, we ranked first in most problem and overall in the traditional authorship attribution task, according to the evaluation provided by the organizers.
This paper presents our approach to the PAN 2012 Traditional Authorship Attribution tasks: closed-class / open-class attribution, authorship clustering / intrinsic plagiarism and Sexual Predator Identification task. We approached these tasks with machine learning methods that work at the character level. More precisely, we treated texts as just sequences of symbols (strings) and used string kernels in conjunction with different kernel-based learning methods: supervised and unsupervised.
Using words is natural in text analysis tasks like text categorization (by topic),
authorship identification and plagiarism detection. Perhaps surprisingly, recent results
have proved that methods handling the text at character level can also be very effective
in text analysis tasks [
Even more interesting is the fact that two methods that obtained very good results
for text categorization (by topic) [
Using string kernels will make the corresponding learning method completely
language independent because the texts will be treated as sequences of symbols (strings).
Methods working at the word level or above very often restrict their feature space
according to theoretical or empirical principles. For example, they select only features
that reflect various types of spelling errors or only some type of words (function words)
[
A method that uses words as features can not be language independent. Even a method that uses as features only function words is not completely language independent because it needs a list of function words (specific to a language) and a way to segment a text into words which is not an easy task for some languages, like Chinese.
The rest of the paper is organized as follows: the next section presents the string kernels used, the following three sections: Authorship Attribution, Authorship Clustering and Sexual Predator Identification correspond to each major sub-task and describe for each of those the specific kernel method used, how it was applied and what were the results obtained. The paper ends with a conclusions section. 2
Kernel-based learning algorithms work by embedding the data into a feature space (mathematically a Hilbert space), and searching for linear relations in that space. The embedding is performed implicitly, that is by specifying the inner product between each pair of points rather than by giving their coordinates explicitly.
Given an input set X (the space of examples), and an embedding vector space F (feature space), let : X ! F be an embedding map called feature map.
A kernel is a function k, such that for all x; z 2 X ; k(x; z) =< (x); (z) >, where < :; : > denotes the inner product in F .
The kernel function offers to the kernel methods the power to naturally handle
input data that are not in the form of numerical vectors, for example strings. The kernel
function captures the intuitive notion of similarity between objects in a specific domain
and can be any function defined on the respective domain that is symmetric and
positive definite. For strings, many such kernel functions exist with various applications in
computational biology and computational linguistics [
Perhaps one of the most natural ways to measure the similarity of two strings is to count how many substrings of length p the two strings have in common. This gives rise to the p-spectrum kernel. Formally, for two strings over an alphabet , s; t 2 , the p-spectrum kernel is defined as: kp(s; t) = X numv(s)numv(t)
v2 p where numv(s) is the number of occurrences of string v as a substring in s 3. The feature map defined by this kernel associates to each string a vector of dimension j jp containing the histogram of frequencies of all its substrings of length p (p-grams).
A variant of this kernel can be obtained if the embedding feature map is modified to associate to each string a vector of dimension j jp containing the presence bits (instead of frequencies) of all its substrings of length p. Thus the character p-grams presence bits kernel is obtained: kp0=1(s; t) =
X inv(s)inv(t) v2 p where inv(s) is 1 if string v occurs as a substring in s and 0 otherwise.
Normalized versions of these kernels k^p(s; t) =
kp(s; t) pkp(s; s)kp(t; t) k^0=1(s; t) = p
kp0=1(s; t) qkp0=1(s; s)kp0=1(t; t) ensure a fair comparison of strings of different lengths.
For the traditional authorship attribution tasks we have used a p-spectrum
normalized kernel of length 5 (k^5). We have chosen the length 5 because it was reported to
work well in the case of document categorization [
Because the p-spectrum kernel works at the character level, we didn’t need to split the texts into words, or to do any NLP-specific preprocessing. The only editing done to the texts was the replacing of sequences of consecutive space characters (space, tab, new line, etc.) with a single space character. This normalization was needed in order to not artificially increase or decrease the similarity between texts as a result of different spacing. Also all uppercase letters were converted to the corresponding lowercase ones.
For sexual predator identification task the character p-grams presence bits kernel
(normalized) of length 5 (k^50=1) was used. The motivations for this choice are given in
Section 5.
3 Note that the notion of substring requires contiguity. See [
Closed-class attribution sub-task is a typical instance of a multiclass classification problem, the main particularity in this challenge being the small number of training examples available (2 per class).
In the area of kernel methods the dominant approach for classification is based on support vector machines (SVM). SVM was designed for binary classification problems. Nevertheless, SVM can be applied to multiclass classification problems by decomposing the multiclass problem into multiple binary classification problems using common decomposing schemes such as: one-versus-all and one-versus-one.
In our opinion these approaches to multiclass classification can turn the low number of training examples only into a deeper problem. For instance, applying the one-versusone scheme in our case will generate binary classification problems with only 4 training examples. Over-fitting is then not only possible, but highly probable. For this reason we decided to use a kernel method that takes directly into account the multiclass nature of the problem.
We have chosen the kernel partial least squares (PLS) regression as the learning
method [
The method has one parameter which must be tuned, the number of latent components to be extracted (the number of iterations). The use of too small or too large dimensional models (number of components) can cause under-fitting respectively overfitting. The number of components must be at most the rank of the training data matrix, so it must be smaller or equal to the number of training examples. Because the number of training examples was very small (2 examples per author) in all attribution problems we chose to use the maximum possible number of components, that is, in all classification problems we have set the number of components to be equal with the number of the training examples.
For closed-class attribution problems we have applied the PLS regression in the standard way (one-vs-all encoding): the output variable Y encodes the class of an example by a vector of -1 and +1, with +1 on the position corresponding to the example’s class and for a new example the predicted label will be the position of the maximum of the predicted output Y^ .
The decision of using kernel PLS regression for closed-class attribution problems was made after an empirical evaluation of the performance of the method and comparison of the results obtained by kernel PLS regression with that obtained by one-versus-all SVM and one-versus-one SVM.
A B C D E F G H I J K L M Overall
The very small number of training examples available for each competition problem
made impossible a cross-validation evaluation and comparison. Fortunately, there is a
data set very similar with the competition problems. This data set is "Ad-hoc Authorship
Attribution Competition" (AAAC) data set [
We have used AAAC problems for an empirical evaluation of the performance of the kernel PLS regression, one-versus-all SVM and one-versus-one SVM. For all three methods we have used as kernel the p-spectrum normalized kernel of length 5 (k^5). In the case of kernel PLS regression the number of latent components was set as described above to be equal with the number of training examples. The variant of SVM we have used was a hard margin SVM. Because problems have a small number of examples and a high dimensional feature space induced by the p-spectrum kernel, the data set is separable and the best working SVM is a hard margin SVM that finds the maximal margin hyperplane. Hard margin SVM has no parameter to be set.
The results obtained by kernel PLS regression, one-versus-all SVM, and one-versusone SVM on the AAAC problems are given In Table 1. For reference, in the last column for each problem is listed the best result obtained for that problem by a system participating to the competition. Note that no single system obtained the best results for all problems. The best overall result obtained in the AAAC competition is that of the highest scoring participant.
These results motivated our choice of kernel PLS regression as our entry in the competition for closed-class attribution sub-task. In the competition, kernel PLS regression obtained the highest accuracy for all problems of the closed-class attribution sub-task. Table 2 presents the results obtained by our method for each problem in the closedclass attribution sub-task. For comparison in the table are also given the results that one-versus-all SVM and one-versus-one SVM would have obtained in the competition (the evaluation was made possible by the release of ground truth data). SVM with the encoding one-vs-all was better than SVM with one-vs-one, but PLS was better than both, as predicted. For open-class attribution problems we need to decide when to predict a label and when not. What the kernel PLS regression returns is a vector Y^ of real values. In the closedclass case the predicted label was the position of the maximum of Y^ . Starting with Y^ , a standard way to decide when to predict is to establish a threshold and predict a label only when the corresponding maximum value of Y^ is above the threshold. This procedure can be problematic in our case because the very small number of training example imply a small number of latent components which can cause under-fitting phenomena. Indeed, there are cases when all values of Y^ are less than 0, but the maximum of Y^ still indicates correctly the label.
We have considered that what is important is the structure of Y^ not the actual values of Y^ . If maximum of Y^ is far enough from the rest of the values of Y^ a prediction can be made, otherwise not. We have modeled "far enough" by the condition that the difference between the maximum of Y^ and the mean of the rest of the values of Y^ to be greater than a fixed threshold. To establish best value for this threshold we have computed the above statistic for all testing examples of the closed-class problems and have taken the value of the 20% quantile, 0.3333. Of course, it was possible to establish a separate threshold for each open-class problem based on the corresponding closed-class problem, but we preferred a unique threshold because in real life situations not every open-class task have a closed-class variant – so the approach we took is more realistic.
The results obtained with this procedure were good: 80% accuracy on the problem B, 76.47% accuracy on the problem D and 81.25% accuracy on the problem J.
These results suggest that the method deserves further investigation, especially of its connection with the outliers detection techniques.
For this subtask we have chosen the spectral clustering [
There are a number of details that one must take care of when applying spectral clustering in practice. One must choose how to compute the similarity between observations and how to transform these similarities into a similarity graph. As similarity between observations we have used the p-spectrum normalized kernel of length 5 (k^5), the same as in the case of attribution. An important point in spectral clustering is to construct similarity graphs that reflect the local neighborhood relationships between observations. Starting from a similarity matrix, there are many ways to define a similarity graph that reflects local behavior. One of the most popular and the one that we have used is the mutual k-nearest-neighbor graph. In the case of the mutual k-nearestneighbor graph, the parameter k, representing the number of nearest neighbors, must be set. We have built problems similar to E and F, and by examining the performance of spectral clustering on those with different values of k, we have eventually chosen k = 12.
We have focused our efforts to solving the problem in its initial formulation, as still given on the website of the competition: in this problem you are given a text (which, for simplicity, is segmented into a sequence of "paragraphs") and are asked to cluster the paragraphs into exactly two clusters: one that includes paragraphs written by the "main" author of the text and another that includes all paragraphs written by anybody else.
For each problem our method clusters the paragraphs into exactly two clusters, even though later when the test data were released some problems consisted of paragraphs written by more than two authors and the performance of a method on these problems is measured according to the respective number of clusters.
The method behaves very well on the problems having two clusters. The results obtained on these problems are given in Table 3.
Etest01 Ftest01 Ftest02 Ftest03 Ftest04
30 20 20 20 20
30 (100.00%) 20 (100.00%) 19 (95.00%) 16 (80.00%) 20 (100.00%)
We have treated the sexual predator identification problem as a classification problem in which each chat participant contributes with precisely one example labeled as predator on not depending on how participant is considered. The contributions of each chat participant are joined into a single text, with line separators, all uppercase letters are converted to the corresponding lowercase ones, and consecutive white spaces are converted to a single space.
The resulted classification problem have been approached as in the previous cases with kernel based learning methods.
This time the kernel used was the character p-grams presence bits kernel (normalized) of length 5 (k^50=1).
We have used 5-grams as an educated guess, as 5 is long enough to catch the ubiquitous “ asl ”, in general long enough to capture word stems in English, and short enough to warrant frequent-enough matches between related same-stem words. We have used this string kernel out of all possible alternatives again as an educated guess: it can be argued that identifying the predators based on the content of their chat logs is a semantic problem, therefore we have used the kernel that we know it works very well on a somewhat-related n-grams based semantic analysis problem, the network anomaly detection (often aimed at network intrusion detection). There the “signatures” are exposing the presence of the network attacks, here we hoped similarly something from what the predators write will act as a signature of their exploiting attempt. Using presence bits brings resilience to attempts of hiding the important part, the signature, by adding large quantities of normal content. Another shared feature of the predators identification problem and of network intrusion detection is the severe class unbalance (here only 142 out of the 100,000 chatters were predators).
Choosing the kernel methods and evaluating them was a difficult task taking into account the dimensions of the problem.
The resources we had at our disposal were: a 4 GB RAM dual-core machine and a 6 GB 4-core machine Note 1. While we thank here without naming them to the ones who promised us help in getting access to better computational resources, those promises failed to ever materialize – in one case, and materialized much too late – in the other case. Therefore the major technical difficulty we had was processing 80 GB kernel matrices in 4 to 6 GB RAM computers. The solution we have found for this is blocking, using matrix chunks, blocks of 5,000x5,000 elements written as independent units on disk. While this works, it works as expected very slowly, therefore we were severely limited in the set of machine learning algorithms that we could attempt.
We have computed the nearest 10 labeled neighbors for each element, by computing the top 10 labeled neighbors in each row of 5000x5000-sized blocks, then doing a postprocessing sort of the top 10 in each block. This procedure is guaranteed to produce at least 10 correct nearest neighbors. 10 was chosen as a compromise between our need to analyze the data and our limited resources.
We have experimented with two methods: one based on k-Nearest Neighbors and the other based on random forests.
Method 1: k-NN (k-Nearest Neighbors) Simple statistics indicate that k-NN [
Method 2: Random forests After exploratory data analysis, consisting in examining
plots of the data after various processing, we have used for our second (and better)
submission random forests [
The plot of the data in Figure 1 shows that this representation not only separates fairly nicely the predators from the normal population, but suggests also the existence of a structure / clusters in the set of predators.
Random forests method provides on the training dataset a different balance of about the same recall (0.67) and higher precision (0.77), for seemingly even higher F-measure 0.68 0.67 0.66 lca0.65 eR 0.64 0.63
Multiple RF runs
The run submit ed (0.72). The results on the test dataset were close to that: recall=0.64, precision=0.74, Fmeasure=0.69. As a note concerning the use of random forest on this classification, we look here at the variability of the prediction accuracy due to the implied in the building of the random forests model. As shown in Figure 2 the performance to be expected on the test set is fairly stable, despite the randomness implied in the random forests training.
To convince the reader that the n-grams binary embedding (with bits of presence) leads to a better kernel for this problem than the spectrum kernel, for n-grams of the same length (5), we have recomputed after the competition the kernel matrix, using the normalized spectrum kernel (which, we remind, uses the frequency of the n-grams in embedding, instead of their mere presence). The 5-fold cross-validation results for the same 100 trees random-forest model were as we had expected, considerably worse: recall=0.49, precision=0.76, and thus F-measure=0.60.
Interestingly, when raising the number of neighbors considered from 8 (used in our solution because of the very limited computing resources available to us at the time of this competition) to 16, there is a slight increase in the performance: recall=0.52, precision=0.79, F-measure=0.63.
One could conclude here that indeed the binary kernel is simply better than the spectrum kernel for this type of problems. Still, there is something interesting about the recall achievable with k-NN when using the spectrum kernel. As shown in figure 3, when deciding only on the first neighbor (1-NN), the recall is close to 0.9
Leveraging the capability of random forests to employ just the information contained in the useful inputs and to a large extent to ignore the useless / noise-containing ones, we have tried also to combine the two kernels instead of deciding which one is the best and selecting one. And indeed, by using as inputs to the machine learning problem the similarities to the predators in the first 8 neighbors for each of the two kernels, the 5-fold cross-validation performance increased sensibly over our best so far, show0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 01
Recal Precision
F−measure k5 2 3 4 6 7 8 9 ing once again the benefits of multiple kernel learning: recall=0.75, precision=0.83, F-measure=0.79. There was also a second sub-task, where the very lines that prove the sexual predator’s quality were to be found. As this was compulsory, we had to send something. A cursory examination of some of the training examples has shown us that there was no word wasted in their attempt to get alone with the future victim as soon as possible. Even the apparently innocent parts of the chat served a purpose. Therefore, we chose to simply mark as suspect all chat lines of the users we have identified (correctly or wrongly) as predators. Surprisingly this brought us a very good position (2nd!) with very high recall and poor accuracy, position that eventually turned into 1st after more after-thefact tinkering with the scoring functions by the organizers (see the authorship clustering issue as well). 6
We have presented in this article our approaches to a rather diverse set of problems: the style-oriented closed-class and open-class attribution, authorship clustering / intrinsic plagiarism and the semantically-oriented sexual predators identification. As a result, we have used a variety of machine learning methods: kernel partial least squares (PLS), spectral clustering and random forests. What is shared in all these is our languageindependent NLP-techniques light approach of building string kernels based on characterlevel n-grams (either spectrum or its binary embedding correspondent, where the frequencies are replaced by presence bits), followed by the application of state of the art machine learning techniques. It is interesting to note that we have chosen the ML techniques not as much through extensive evaluation on the few data available for training as by their intrinsic qualities in what concerns the probability of over-fitting and the known success in parallel fields (such as chemometrics or computer networks security). The results were extremely good, we ranked first in most problems and overall in the traditional authorship attribution task, according to the evaluation provided by the organizers.