In this paper we present the system we submitted to the PAN 2015 competition for the author verification task. We consider the task as a supervised classification problem, where each case in a dataset is an instance. Our approach combines the output from multiple learners using basic stacked generalization. The individual learners are obtained using five distinct approaches, each trained using a generic genetic algorithm. Our system performed well on the test set: the macro-average score was 0.61 (2nd best).
In the PAN 2015 author verification task [
We consider the task as a supervised classification/regression problem4, at the dataset level; in other words, each problem is an instance and we expect to find some regularities among the instances which belong to the same dataset. It is worth noticing that this view is compatible with, for instance, unsupervised learning at the problem level: the latter can be seen as an initial answer, which is then used as input in the dataset-level supervised system.
We propose a relatively complex solution5, which consists in training a set of multiple (mostly) heterogeneous learners, later combined using a simple stacked generalization method. A genetic algorithm is used in two stages: 1. to learn an optimal combination of parameters for each of the five approaches from which the individual learners are obtained; 2. to learn the optimal way to combine the learners together.
The main difficulty in this approach is to avoid overfitting, especially with such a small number of instances. The genetic algorithm always tries to maximize the performance in any available way, because this is the criterion used to select the breeders for the next generation. But by doing so it can easily end selecting parameters which are optimal only for the set of instances seen by the algorithm, even if the performance of every individual is evaluated using cross-validation. This is why we try to minimize the risk of overfitting by using various additional techniques (see §3.2).
This paper is organized as follows: in §2 we detail the reasons why we chose this approach. In §3 we describe the architecture of our system, then in §4 we give a brief overview of each of the five approaches we take as individual learners. In §5 we present some of the techincal issues we faced with this approach. Finally in §6 we analyze the main observations that we made based on the training process. 2
We had participated in the previous edition of the author identification task of the PAN
competition [
This is why we had also prepared two distinct approaches: the fined-grained one, which contains a lot of parameters in order to maximize the performance, and the robust one, which was on the contrary a very simple method, intended to minimize the risk of overfitting. For each dataset, the final choice between the two approaches was made manually, based on the observations and statistics available to us.
Our system was ranked 4th overall, with 2nd or 3rd rank in 4 out of 6 datasets [
We also implemented two additional strategies (see §4). – Finally, because of the genetic algorithm, the previous version of our system contained most of the basic components needed to generate multiple independent learners, which made it technically easier to take this quite complex approach. 3
Our approach consists in training a set of 5 N individual learners, with N learners obtained from each of the five distinct methods (we call them strategies) that we have implemented (see §4). Every model obtained at the end of this stage is a full “authorship verification system”, in the sense that, given a set of problems as input, it provides a set of scores in [0; 1] as answers. Then the training of the meta-learner takes place, which consists in selecting the optimal subset of individual learners and the optimal way to combine their outputs together. Both training stages are carried out with a generic genetic algorithm, which evaluates models according to their performance obtained with cross-validation. 3.1
We call configuration a set of parameter-value pairs: C = fp1 7! v1; : : : ; pn 7! vng. For each strategy, we define a set of parameters in such a way that a given configuration defines exactly how a model is learned (or applied, when associated with a corresponding model). In particular the configuration describes which features are used and how they are combined (possibly using a ML model). In training mode, a configuration C and a set of instances (problems) S define a model M in a unique way6: ftrain(C; S) = M . In testing mode, a configuration C, a model M and an instance s define a unique prediction: ftest(C; M; s) = p. The space of all possible configurations can be very large, depending on the strategy. This is why we use a genetic algorithm, in order to learn the optimal configurations. 6 This is not entirely true because of the randomness in some strategies. It is however theoretically true in the limit, that is with sufficiently random runs.
Our genetic algorithm works with configurations as “individuals”: each configuration describes the meta-parameters of a strategy. A multi-configuration associates multiple values to one parameter:
M C =
p1 7! fv11; : : : ; vm11 g; : : : ; pn 7! fv1n; : : : ; vmnn g
Thus, a set of multi-configurations can be used to describe the set of meaningful combinations of parameters, in a way similar to a disjunctive normal form.7 This union of multi-configurations is the input of the genetic algorithm: – The first generation of configurations is initialized randomly: N configurations are selected among the possibilities described by the union of multi-configurations. – Then every generation is obtained based on the individual performance of the configurations from the previous generation:
The “breeders” are selected in a way such that the probability of a configuration being selected is proportional to its rank by performance.
For every new configuration, two parents are selected randomly among the breeders and every parameter is assigned the value of either one of the parents value, with the possibility of mutation.
Additionally, the algorithm allows for a proportion of the new generation to be
selected fully randomly, and for a proportion of the best previous configurations to
be cloned to the next one (elitism). We had observed in [
The convergence of the algorithm is tested by looking at the n latest windows of m generations (length), starting from the (n m)th generation: the mean of the performance is computed for every window, and the stop criterion is met if the first window obtains the maximum performance (that is, the performance didn’t improve on the last n 1 windows). This simple method offers some useful flexibility: depending on the characteristics of the process (e.g., size of the hypothesis space, time needed to compute a generation), the process can be set to favor speed or a more exhaustive exploration of the search space. 3.2
The disadvantage of using a genetic algorithm, especially with a vast set of possible configurations, is the risk of overfitting. We use cross-validation inside the genetic algorithm: in other words, each configuration generated is evaluated using k-fold crossvalidation, and the resulting performance is used as the fitness function by the genetic 7 In practice, however, we have used only one multi-configuration by strategy, leaving the selection of relevant combinations to the genetic algorithm. algorithm. It is worth noticing that k-fold cross-validation outside the genetic process is not a good option for two reasons: first, the genetic process is very long, hence hardly practicable for any decent value of k; but it is also very unlikely that two distinct genetic processes would find the same optimal configurations, given the size of the search space8 and the fact that a genetic algorithm can only return a local optimum.
We use various techniques to keep overfitting to a minimum: – The partitioning for the k-fold cross-validation is randomly (re-)generated at every generation. – The system allows to chain multiple stages of genetic learning with different parameters, in particular different values of k and different values for the size and number of windows in the stop criterion. At every new stage, the previously selected set of configuration is used as first generation, and re-evaluated under the new parameters. This allows the process to check and progressively refine the optimal configurations and/or adjusting the trade-off between the precision of the process and the required computing power. – At the end of the last stage, the N best configurations are re-evaluated using a 10x2 cross-validation setting, in order to control the influence of the cross-validation partitioning on the performance variance.
At the end of the first stage, for every dataset we obtain N strategy configurations and their corresponding models for each of the five strategies. Then the second stage of meta-learning is carried out, using the the predicted scores of the strategy configurations as features and the same genetic algorithm. A special meta-configuration is built, which contains only: – For each of the selected strategy configurations, a binary parameter which indicates whether its prediction is used or not (feature selection). – A parameter which indicates how the strategy predictions are combined. In order to avoid another potential source of overfitting (see discussion below), we restricted this combination to the safest methods: the algorithm can select only the arithmetic mean, geometric mean or the median. Of course, using a regression algorithm might provide better results. – A parameter which indicates whether to apply the C@1 optimization again on the output score (see §4).
We were hesitant as to what would be the most reliable approach regarding the use of instances: – The most simple option consists in using a first subset of the instances (e.g. 50%) for the strategy training stage, then the second one for the meta training stage. Optionally, the second set of instances can be split further in order to control for overfitting in the meta training stage with a new subset of fresh instances (e.g. 25% and 25%). – A proper nested cross-validation setting seems a methodologically more solid approach. There are, however, two major issues with that: 8 From 124; 000 (robust strategy) to 1021 (fine-grained strategy); see §4.
Training the genetic algorithm for every strategy and every dataset (5 4 = 20 cases) requires a lot of time; multiplying that by k in the case of k-fold crossvalidation is likely to be prohibitive.
In the case of an inner cross-validation process with respect to the genetic algorithm, overfitting arises because, even if a given model at generation t is tested on instances that it did not see, the instances have been seen in the previous generations and influence greatly9 the configuration from which the model was generated. The case of outer cross-validation is discarded for the reasons explained above.
This is why we opted for an hybrid (maybe somewhat unorthodox) setting which consists in doing the three stages of the first option using 2-fold cross-validation. That is, in both runs: 1. The strategy genetic training uses inner cross-validation on 50 instances. As a result we obtain the 10 best models by strategy (50 models); 2. The meta training uses 25 fresh instances, in order to avoid the overfitting issue caused by inner cross-validation. We use only unsupervised combinations methods in order to minimize overfitting, which is very likely on such a small number of instances. 3. The best meta-models are evaluated on the fresh last 25 instances (as well as the best strategy models, mostly for comparison purposes). This part of the training data is called the meta test set.
The last stage of evaluation uses bagging (bootstrap aggregation): the models are evaluated 20 times against a different random 50% subset of the instances, so that we can control for performance variance. But there are still two problems left: – The last evaluation stage is done on a small set of instances, and therefore not very reliable. – The resulting models from the two cross-validation runs are not comparable together (see above). Moreover, it is likely that one of the runs will perform better in absolute value because of the different subsets they use for training and testing.
This is why we carry out an additional stage of evaluation of all the resulting models on the whole dataset, using bagging again. The rationales for this are: (1) this is a pragmatic workaround for the two issues above, and (2) the meta-models have not seen directly the first 50 instances used for the strategy training stage; testing proved that the performance on these instances was, in general, not overevaluated compared to the actual fresh instances of the meta test set. Of course, being aware of the potential biases, we do not consider the results of this final evaluation stage as totally reliable. We rather consider these as a useful indication of the models behaviour, that we study together with the results on the meta test set. This is why the very last stage of model 9 We have tested this option and the results of the meta training stage were very bad: the resulting meta learner would expect too much reliability in the scores (“too good” scores) it uses as features, hence it performed badly on regular (“mediocre”) scores, as obtained on unseen data. selection is not currently automatic: we make the decision based on several statistics, the comparison to the other models and what we know about the possible biases.
There are probably other relevant options that we did not consider, due to lack of time or by ignorance. This naive and pragmatic approach is for us a rather reasonable first attempt at using multiple learners for this task. 4
Five distinct strategies are used to generate the individual learners. Two of them, namely
the robust and the fine-grained strategies, come from the system that we submitted at
the previous PAN task (2014). A brief summary of these approaches is given below; for
more details, see [
– The fine-grained strategy contains many possible parameters. It is intended to try as many configurations as possible, in order to maximize the performance. – The robust strategy is a simpler method which uses only a small set of parameters.
It is intended to be safer (in particular less prone to overfitting), but probably not to perform as well as the fined-grained strategy.
We also implement three new strategies: GI, Universum Inference and Topic Detection, which are described below.
Technically, every strategy takes as input a set of problems with their answers (training mode) or a set of problems and a model (testing mode), and optionally some additional resources (e.g. impostors documents). As output, the strategy returns a set of features for every problem10; these features are fed to a ML algorithm11, which is used to train a regression model (or to apply a previously trained model), using each problem as an instance (“Yes” answers are converted to 1, “No” to 0).
An additional optional step can be carried out, which consists in optimizing the answers in order to maximize the C@1 score, i.e. assign 0.5 scores to ambiguous cases. Two options are provided: the most simple option consists in finding the optimal accuracy threshold, then testing if assigning 0.5 to the instances with close scores improves the C@1 score. The second option consists in training an additional ML classification model, which tries to determine which cases are ambiguous based on the features and the predicted score.
Each application of a strategy is governed by a configuration (see §3.1) which
defines not only the specific parameters for this strategy, but also some parameters which
are common to all strategies. These include:
– some general-purpose parameters, like the kind of observations (words or
characters n-grams, POS n-grams, ...), the minimum frequency, etc. (see [
This method is described fully in [
Given a feature set of size N, a source text X, a target text Y and a set of impostors I = fZ1::::Zig , we select a random percentage of features a of N and repeat this selection n times.
We then obtain for each system run a matrix P with dimensions (i + 1) n where each cell is the value13 for a particular distance metric for a comparison (i + 1) (columns) between the source X and either the target Y or one of the set of impostors for each of n(rows), each row a randomly selected subset of N.
This distance metric employed in each run is either the cosine distance, KullbackLeibler divergence or the Average Jaccard Index between two texts using a metric subset a of the full metric set N. The distance metric is randomly selected at the beginning of each run. The metric representation N used in a run of the system is also defined in a previous step. Finally the matrix values are combined into a small set of features based on various options, including the variants used in the literature. 4.2
The topic modelling is used to exhibit topics from the underlying text in a corpus.
The intuition is that the Latent Dirichlet Allocation (LDA) [
The use of topic modelling might seem counter-intuitive in this task. However, our
idea is to let the genetic algorithm select the features used by the algorithm, hoping that
it will select features which are relevant for style distinctiveness rather than topic.
12 We actually restrict these to a very small set of possibilities.
13 To five decimal places.
This strategy follows the idea described in [
We adapted the approach to the case of smaller documents in the following way. Let
A and B be two documents, the following process is repeated N times with different
random subsets:
1. The two documents are split into three parts randomly: A1; A2; A3 and B1; B2; B3;
one of the thirds is split again into two parts: X3 = X 30; X 300.
2. The pieces of text are re-organized under three categories, each containing two
parts and all the parts being of similar size: CA = fA1; A2g; CB = fB1; B2g;
Cmixed = fA03 [ B30; A030 [ B300g.
3. The three categories are compared in the same way as [
During the development, training and testing of our system, we faced a number of practical issues. These issues probably had an impact on the quality of the results, but it is impossible to properly measure to what extent.
Of course, the most important constraint was the time schedule of the competition. We started the development quite late. For the most part, the system was coded during the time that the competition was taking place. This left relatively little time to train the 40 runs of the genetic algorithm to their best (4 datasets 5 strategies 2-fold crossvalidation). Thus, it is possible that for some complex strategies we did not reach the optimal models14; more importantly, we did not have enough time to make the models run through enough different stages of cross-validation under restrictive convergence conditions (see §3.1), which could have provided more stability in the models.
It is difficult to evaluate precisely the amount of computation that we gave to the whole training process, because we used two distinct machines and there were interruptions during the process. We evaluate it roughly between 150 and 300 CPU hours for each of the 40 genetic processes. 14 Additionally, we discovered after the competition that a bug caused a disruption in the genetic process in the case of the Dutch and English datasets.
Comparing the performance of the five strategies (see 4) shows little surprise; it confirms relatively well the differences between those strategies and their complementarity: – The GI strategy performs very well in general, and its low variance makes it especially robust. – The Universum Inference strategy performs well and is even the best individual strategy on two datasets (Dutch and English); it is however quite unstable. – The robust strategy keeps its promises: albeit low performance in general, it is practically insensitive to overfitting, showing very close performance on training instances and fresh instances. – The fine-grained strategy is vey unstable, but occasionally performs very well. – The Topic Modeling strategy does not seem to work very well in general.15 6.2
15 It has however been selected as individual learner in several cases in the meta-learning stage; thus, such models might actually bring a different kind of information which turns out to be useful to the meta-model (but we did not have time to investigate this question in more detail). 16 See §3.2 for explanations about the setting in which these performance values are obtained. only one known document for every problem and has the smallest documents (in average), and it is also the most difficult to predict for the system. On the contrary, there are always four known documents by problem and the documents are the largest for the Spanish dataset, and the system performs very well with it.
The system had the worst difficulties in the case of the English dataset. It might be because, as a strongly supervised system, it does not cope well with scarcity of information. It is also possible that a more complete training would have helped in finding the relevant clues in this more difficult case.
Finally, in most cases the results on the test set are close (within the standard deviation) to the ones obtained on the traning set. This tends to indicate that the approach is good at preventing overfitting. Even in the case of the visibly overfit Spanish model, the results do not fall drastically compared to the other participating systems; this moderation of the effect of overfitting is probably explained by the use of multiple learners, the overfit ones being partly compensated by the others. 7
There is a lot of room for improvement in our current system: improving the current strategies, adding new strategies, solving efficiency issues, etc. In our opinion, the most interesting question to study is certainly how best to combine the predictions of the individual learners, in the context of a relatively small training set which is expectable in authorship verification. In the current version, the ML setting is not entirely satisfying (see §3.2). Various options could be explored in the future: – Generating artificial instances from the existing ones, for instance by splitting original documents into multiple sub-documents. This option might not be completely safe, since artificial cases might be less useful in assessing the reliability of a model, and maybe even misleading. – Finding a way to combine the best models provided by multiple runs of the genetic algorithm. In theory, these models share some similarities, and these similarities correspond to the features that matter, those which allow the model to perform well in a reliable way (the other features can be seen as the result of statistical noise). It is however not necessarily possible to safely “merge” two distinct configurations.17
This research is supported by Science Foundation Ireland through the CNGL Programme (Grant 12/CE/I2267) in the ADAPT Centre (www.adaptcentre.ie) at Trinity College, University of Dublin. 17 This option could also be considered in the perspective of simply measuring how similar two configurations are: based on such a similarity measure, instead of “merging” heterogeneous configurations, the system could select configurations based on their similarity across different runs. The same idea could be used to maximize the diversity of the selected strategy models, which is likely to be a decisive feature in the success of the meta-learner.
Some of the calculations were performed on the Lonsdale cluster maintained by the Trinity Centre for High Performance Computing. This cluster was funded through grants from Science Foundation Ireland.
Fitting our complex and poorly efficient system to the tira.io framework proved challenging, and we are very grateful to the organizers for their patience and availability.