In this application note we revisit previous work on the exploratory analysis of Multilabel Classification (MLC) tasks in Machine Learning. We combine Information Theory and Formal Concept Analysis (FCA) to formalize the intuition that inference of classifiers in MLC tasks can only proceed when the training and testing data concerning the labels define the same Concept Lattice. We instantiate our procedure on the emotions dataset, but the procedure is independent of the dataset being explored. An R language interactive notebook carrying out the procedure is available upon request.
1.1
Y
PY
PX observe transform
PZ classify
PYb ˆ Y
The following way of solving the problem is based on the theory of Statistical
Learning [
The usual way to solve the problem in the simpler, supervised setting is: 1. Model the source of labelsets as random label vectors Y ∼ PY and their observations as the feature vectors X ∼ PX over their respective spaces. 2. Collect a (task) dataset with s samples, D = {(⃗xi, ⃗yi)}js=1 of labelsets and their observed features to induce a classifier from observations to labelsets h : X → Y . 3. Choose the classifier type and induction scheme for it. 4. In order to assess the classifiers, choose an adequate measure of performance, and implement (any of a number of) schemes of iterated re-sampling of the data into sT a set of training examples DT = {(⃗xj , ⃗yj )}j=1 and a set of test examples DE = {(⃗xk, ⃗yk) sE
}k=1 so that the training data are used to induce the classifiers and the
testing data to test them, and validate these results, e.g. using k-fold validation [
Note that only 27 of the 26 = 64 possible labelsets occur, and as many as 4 of
them are hapaxes—they occur only once—while at least one of the labelsets appears
81 times. This wildly imbalanced behaviour is typical of MLC datasets [
Note that in the standard approach above FCA is all but absent. However, it is easy to see that FCA and its variants are relevant in modelling this ML task.
First, with the labelsets {⃗yi}is=1 of the task dataset we can build a formal context using the set of labels L as attributes, with |L| = mY , and taking for each sample— considered as a formal object i ∈ G with |G| = s—its labelset as a row of the incidence matrix Ii· = ⃗yi, whence DL = (G, L, I) is the binary formal context of samples and their labels. This context captures the information in the stochastic source Y .
i s
Secondly, for observation vectors {⃗x }i=1 their context DF = (G, F, R)—with F the set of features—will not be binary, in general, but many-valued Ri· = ⃗xi. This context captures the information in the observations X 2.
With the previous modelling, relevant notions in MLC correspond to relevant notions in FCA. For instance, labelsets are object intents, and they can be found through the polars ⃗yi = {i}↑ . In this way, we can reason about the sampling of the stochastic variables Y and X—the dataset—in terms of the contexts above, and vice-versa.
For instance, each labelset present in the dataset—that is, each object-extent—may
appear with different samples (formal objects). Recall that the concept-forming function
γ induces a partition ker γ on G by equality of labelsets: (i1, i2) ∈ ker γ ⇐⇒ {i1}↑ =
{i2}↑ = ⃗yi1 . This partition is crucial for defining the entropy of the label source (see
§ 2). In the other direction, we expect the sampling to be good enough mY ≪ s so it is
2 Note that Fig. 1 suggests another context formed by the transformed observations captured by
the random vector Z, but this will not be dealt with here.
safe to suppose that no two labels are predicated of the same set of objects. Therefore
we expect the partition on labels induced by µ to be the identity ker µ = ι L, which
holds on standard testing datasets (see e.g. those in [
The following problem and its theoretical solution were proposed in [
Since the data are a formal context we know that an important part of the information contained in it comes from the concept lattice, hence: Hypothesis 1. 1. (FCA intuition) A necessary condition for the resampling of the data D into training part DT and testing part DE to be meaningful for the MLC task, is that the concept lattices of all of these be isomorphic:
B(D) ∼= B(DT ) ∼= B(DE ) 2. (ML intuition) Not only the labelsets but also their ocurrence frequencies as quantified by the cardinalities of the blocks of ker γ are important.
The last consideration follows because if we only retained the meet- and joinirreducibles to obtain these concept lattices, then the labelsets of reducible attributes would be lost so the relative importance of the samples—both labels and observations— would change, impacting the induction scheme of the classifiers.
The above proposition suggests that the analogue of stratified sampling in MLC is a procedure in which the stratification must proceed on a block-by-block basis with respect to ker γ . However this comes at a price, when there are hapaxes in the data. If we choose, for instance, to maintain 80% of the data for training and 20% for testing, regardless of these proportions, stratified sampling will force us to include all hapaxes with the following deleterious consequences: – The relative frequency of the hapaxes will be distorted wrt to other labelsets. – We will be using some data (the hapaxes) both for training and testing, which is known to obtain too optimistic performance results in whichever measure of it.
Furthermore, if we use, e.g. k-fold validation we have to repeat this procedure and ensure that the resamplings are somehow different. A usual procedure is to distribute the original dataset into k blocks in order to aggregate k − 1 of them into the training dataset DT and use the leftover as the testing dataset DE . It is common to use k = 5 or k = 10. This can only compound the previous problem, therefore FCA allows us to spot possible problems with the classifier induction and validation schemes using resampling.
In this paper we will use side-by-side FCA-based and Information Theory-based devices to support the claim that they improve the understanding of the task when used in synergy. For that purpose we first review an Exploratory Data Analysis (EDA) technique in Sec. 2 to help in interpreting the experimental results in Sec. 3. 2
The Source Multivariate Entropy Triangle (SMET, [
Due to space limitations, we will only describe the graphic approach to the SMET.
We refer the reader to [
To assess the effectiveness of stratified sampling schemes for MLC, this paper proposes to use the visualization of the information balance of a formal context of labels DL using the SMET. 3
SW resources. The following analysis is carried out on the Example 1 emotions
dataset [
To dispose of hapaxes without disposing of samples we must re-assign each to a more frequent labelset. The rationale for this decision is because we consider hapaxes errors in label codification, and assume that the “real” labelset is the closest non-hapax in Hamming distance3. However, this re-assignment changes the histogram of labelsets what results in an impoverishment of the information balance of the labels and the dataset in general.
To explore this trade-off, at each threshold nT , a labelset ⃗y was considered a generalized hapax if ny⃗ < nT . For each threshold nT we calculated the Hamming distance between each generalized hapax ⃗ynT and the non-hapaxes, and found the set of those closest to it. Then we re-assigned ⃗ynT to one of them uniformly at random (allowing for repetitions) 4. 3 Recall that the Hamming distance between two sequences of bits of identical length is the number of positions in which they differ. 4 Note that an alternative strategy would have been a scheme considering the original frequencies in the histogram, to simulate a rich-get-richer phenomenon. But such a procedure would decrease the source entropy more than the one we have chosen.
This reassignment defined a new dataset whose information balance was represented by the SMET, as suggested in Section 2, whence Fig. 4 ensued. What we can see is a general tendency to the increment of the total correlation as the thresholds increase. But this entails that the individual distinctiveness of each label is diminished. See, for instance, the case for angry-aggressive that can actually be predicted from the other labels when n = 25, confirming that too aggressive a threshold will substantively change the relative information content of the labels in the dataset. Choosing the adequate threshold. Note that a threshold of n is needed to request an (n + 1)-fold cross-validation of any magnitude about the dataset, since all labelset will have at least (n + 1) representatives for the stratified sampling requested by the cross validation procedure. Is it possible to balance the identical sampling property on train and test, yet avoid too much loss of information content?
Figure 5 depicst a choice of thresholds typically used in validation—1, 4 and 9, corresponding to 2-, 5- and 10-fold validation—for three differently behaving labels— angry-aggressive, quiet-still and relaxing-calm—and the average of the dataset, both for the ensembles of training and testing folds.
– As applied to the estimation of the entropies, the (n + 1)-fold validation yields the
same result in train and test, the sought-for result.
– We can see the general drift towards increased correlation in all labels, but much
more in, say, angry-aggressive than in quiet-still.
– For this particular dataset, a threshold of nT = 4 with 5-fold validation seems to
be a good compromise for attaining statistical validity vs. dataset fidelity.
FCA confirmation. To strengthen the validity of the last two conclusions, we
calculated the number of concepts of all of the train and test label contexts using the fcaR
package [
As expected, for nT = 0 the difference in number of concepts between the nonsampled and sampled versions of the dataset make it non-adequate for appropriate sampling5. The training and test splits had the same number of concepts for every other threshold. For nT ∈ {1, 4, 16}, the number of concepts was constant among folds, but due to the randomness inherent in sampling for nT ∈ {9, 25} one of the folds was different (not shown explicitly). 4
We have tested and strengthened a data hypothesis put forward in previous work [
We first explored the influence of carrying out different degrees of smoothing of the labelset frequencies and found a balance between it and the increase in total correlation of the labels, leading to a loss of their individual information content.
We also checked that the recipe for defining an appropriate threshold n to carry out an (n+1)-fold cross validation actually works by comparing the informational balances of training and testing splits of the dataset as random estimates of their actual values.
Further work should start applying this rationale to solving of the MLC task.
Preliminary work on using both FCA- and information theoretic-approaches suggest that
present-day solutions are far from satisfactory in this respect. In the future, we plan to
use more FCA-induced techniques from [