Inverse Feature Learning: Feature learning based on Representation Learning of Error

The objective of the inverse feature learning method is to learn a set of additional features per sample by trial to extract the relations between the sample and the classes. This process is performed during two phases for the training and test sets. In each phase, the samples are assigned to the set of samples of the available classes one at a time and the changes in the characteristics of data before and after adding each sample are analyzed. Here, we provide an overview of the proposed method.

First, in inner folding phase, we partition the training instances to inner-training and inner-test sets during each fold in such a way that each training instance is considered as inner-test instance once. Then, in layer 1 of the proposed inverse feature learning, the inner-training samples with the same labels are grouped together. Next, the groups of samples (i.e., the samples with the same label) are clustered to a pre-determined number of clusters. The representation of these clusters for each label are calculated in the form of several intermediate features. In layer 2, each inner-test sample is intentionally assigned to all available classes, and then one of two described strategies are performed to extract and analyze a notation of error as a means to learn a new set of high-level features. In layer 3, regardless of the fact that the sample has been assigned to the right or wrong classes, we measure two sets of metrics per sample for each class. These two sets of learned metrics are then added to the original data as the learned features. Since these features are learned per class, the features belonging to different classes need to be separated from one another. Therefore, we embed the corresponding classes of these feature sets in them by multiplying the corresponding features of each class to a different large number. The model is trained and evaluated by adding the learned features per instance to the set of the primary features of the corresponding instance for both of training and test instances, respectively. In the feature learning for training instances, the features are only learned for inner-test samples, in which their labels are not considered in the process. The reason is because we aim to develop a unified framework for feature learning during the training and test phases in classification, where the test instances do not have labels.

To formulate the problem, the input training data set is presented with $D=\langle X^{Train},Y^{Train}\rangle$, in which $X^{Train}=\{x_{1},\cdots,x_{n}\}$ indicates the set of input training instances and $n$ shows the number of input instances in the training partition. Each instance $x_{i}=\langle x_{i,1},\cdots,x_{i,h}\rangle$ consists of $h$ features. The label set is denoted by $Y^{Train}$, where $Y^{Train}=\{y_{1},\cdots,y_{n}\}$ is a vector corresponded with data set $X^{Train}$. Thus, $y_{i}$ shows the corresponding label for $x_{i}$. Since we focus on classification, the labels are categorical. $\mathcal{Z}$= $\langle z_{1},\cdots,z_{m}\rangle$ shows the set of classes, in which $m$ indicates the number of classes. $X^{\text{Test}}=\langle x^{{}^{\prime}}_{1},\cdots,x^{{}^{\prime}}_{f}\rangle$ denotes the test set in which $f$ refers to the number of test instances. Notation $|b|$ indicates the number of instances in set $b$. In continue, we describe the building blocks of this method with more details, as depicted in Figure 2.

The first step is to find the representation of samples belonging to different classes for both training and test sets. It is simple to obtain the representation of each class for the test samples as we can simply partition the training samples to different classes in order to obtain the representation of each class. However, the equivalent process of partitioning is more computationally complex for training samples, since each sample of the training set should be considered against all remaining samples with a strategy similar to leave-one-out cross-validation. In each case, the number of remaining samples to learn the class representation is $n-1$, in which $n$ denotes the number of training instances. Hence, this process involves a large number of repetitions of the feature learning process (i.e., $n$ times) that is not scalable to large data sets. Therefore, we instead apply a folding mechanism, here called as inner folding to only perform the feature learning process for a limited number of runs (i.e., $r$-runs, where $r\ll n$). During each round of inner folding, the training samples are divided into two partitions of inner-training and inner-test samples.

We introduce inner folding as a partitioning mechanism that works similar to $k$-fold cross-validation in terms of partitioning data, but the objective of this inner folding is different from typical cross-validation folding methods. Inner folding is a framework that partitions $\langle X^{\text{train}},Y^{\text{train}}\rangle$ to $r$ folds. It runs $r$ times, wherein each run, $r-1$ folds are used for training and 1 fold is used for test. Here, each fold is considered as a test fold only one time. The training and test partitions in each run are called as inner-training and inner-test, respectively. Thus, inner folding is different from cross-validation since it is used as a mechanism to evaluate the characteristics of one test sample of inner-test against the inner-training samples in each run.

The inner-training and inner-test sets of the $j^{\text{th}}$-run of the inner folding are shown with $\langle X^{\text{Inner\_train}}_{j},Y^{\text{Inner\_train}}_{j}\rangle$, and $\langle X^{\text{Inner\_test}}_{j}\rangle$, respectively. Clearly, $X^{\text{Train}}=X^{\text{Inner\_test}}_{j}\bigcup X^{\text{Inner\_train}}_{j}$ for each $j$. The trail process involves assigning each test instance, $\forall x_{f}^{{}^{\prime}}\in X^{\text{Inner\_test}}_{j}$, to each available label, $z_{i}$, $z_{i}\in\mathcal{Z}$ that exists in $Y^{\text{Inner\_train}}_{j}$. In continue, we describe the three layers of error representation for each run of the inner-folding process.

As mentioned before, the proposed inverse feature learning method is designed based on the analysis of error representation. The error is measured using different metrics after assignment of the inner-test samples to different classes in order to investigate the variations in the relative relations among the samples. To do that, first, the instances of each class are clustered to a pre-determined number of clusters using $K$-means algorithm as an unsupervised learning method. K-means algorithm is selected as the clustering technique since it is very fast and can be scaled to high-dimensional data sets [23]. However, we understand that $K$-means algorithm does not perform well in cases, where the instances have different densities or the instances are distributed in non-spherical forms. We should note that the proposed inverse feature learning method is generic and can be implemented with other clustering techniques.

During each round $j$ of the inner-folding process, the instances of $X^{Inner\_train}_{j}$ are first categorized based on their labels, $Y^{Inner\_train}_{j}$, to $G_{j}=\langle G^{1}_{j},\cdots,G^{q_{j}}_{j}\rangle$, in which $q_{j}$ shows the number of labels in $Y^{Inner\_train}_{j}$. The corresponding input instances and labels of group $i$ during round $j$, $G^{i}_{j}$, are shown with $X^{Inner\_train,i}_{j}$. Then, the samples of each class $i$, $G^{i}_{j}$, are clustered to $k$ clusters. These clusters are ordered based on the number of their member instances and shown with $C_{G^{i}_{j}}=\langle C^{1}_{G^{i}_{j}},\cdots,C^{k}_{G^{i}_{j}}\rangle$.

During the clustering, each object is assigned to the cluster that has the nearest centroid as a mean of its instances based on a distance metric. The objective function of K-means is considered to find the $\text{centroid}_{1},...,\text{centroid}_{k}$ in order to minimize the objective function, $O$, as described in (1).

where $s$ denotes the number of instances in group $G_{j}^{i}$ with label $i$, and $x_{l}^{t}$ denotes the instance $x_{l}$ that belongs to cluster $t$.

Mean-group is a metric defined as the mean of each group, $G^{i}_{j}$. This metric, as described in algorithm 1, is a vector denoted by $\mu^{i}_{j}$ that its $l^{\text{th}}$-element is calculated as the average of $l^{\text{th}}$ features of all instances that belong to this group.

In order to evaluate the characteristics of the clusters of each class, we define three other metrics of confidence, mean, and centroid, as described in algorithm 1. These measures act similar to kernel functions of ConvNets to extract the representation of each cluster. The centroid indicates the center of a cluster that is obtained by the clustering method. The Confidence is a singular scalar value and defined as the ratio of the number of instances of each cluster to the number of all instances of that class. In other words, the confidence metric is a membership value that shows the probability that an instance belongs to a particular class. The mean is a vector with length $h$ that calculates the average of $l^{\text{th}}$ features of all instances that belong to a cluster. The calculation of these measures in layer 1 captures the baselines to learn the error as defined in layer 2.

In machine learning methods, error is the result of differences between the predicted output and true output that is measured by loss functions and used to train the model. In a simple case, the error is “one” when a predicted label is incorrect, and the error is “zero” when the predicted label is correct. In the proposed inverse feature learning method, instead of using this traditional notion of error, the error is measured based on resultant representation of assigning the instances to different classes in a trail approach.

As mentioned earlier, the instances that belong to each group $G^{i}_{j}$ of $G^{j}$= $\langle G^{1}_{j},\cdots,G^{q_{j}}_{j}\rangle$ have the same label. In layer 1, the representation of each class and its clusters were measured using several intermediate features (e.g. the mean of a class, and the centroid, the mean, and the confidence of the clusters). The goal of layer 2 is to evaluate the changes in these intermediate features, and in a more general sense, the representation of each class using the formed clusters by adding the test samples of inner-test. In other words, we assign the samples of the inner-test set to the existing labels one at a time. Therefore, the term trail refers to the process of inserting a new inner-test sample, $x^{{}^{\prime}}_{l}\in X^{Inner\_test}_{j}$, to a group of samples with the same label, $G_{j}^{i}$ and generating a new set of ($X^{Inner\_training,i}_{j}\bigcup x^{\prime}_{l}$).

We have considered two strategies to evaluate the characteristics of data after addition of new inner-test samples. In the first strategy, the similarity between the instance and the centers of clusters of each class is measured to find the closest one in order to assign that instance to this closest cluster. In other words, this sample is added to the closest cluster. Thus, in the first strategy, which is the simpler option, is to calculate the distances between the sample of inner-test, $x_{p}^{{}^{\prime}}$, ($x_{p}^{{}^{\prime}}\in X^{Inner_{{test}_{j}}}$) and the centers of all clusters in $C_{G_{j}}=\langle C^{1}_{G^{i}_{j}},\cdots,C^{k}_{G^{i}_{j}}\rangle$ (obtained in algorithm 1), and then assign $x_{p}^{{}^{\prime}}$ to the closest cluster of the class $i$. This cluster is denoted by $C^{*}_{G^{i}_{j}}$. After that the confidence, centroid, and mean are only calculated for the nearest cluster. This strategy is described in Algorithm 2.

In the second strategy, the formed clusters of layer 1, $C_{G^{i}_{j}}$, are no longer used. Instead, in the this strategy, the set of instances in each class including the primary and new instances are clustered again. The first strategy involves less computations, however, it does not necessarily perform as well as the the second strategy of re-clustering when the density of clusters are considerably different. For instance, when there exists several outliers in the original groups.

The purpose of layer 1 was to capture the representation of classes in the form of clusters before the trial process. In layer 2, the representation of each inner-test instance and classes after the trial was captured when each inner-test instance is added to a cluster of each class. Now in layer 3, the representation of error is learned through several high-level features by non-linear modules as described in following. These features capture the relationships between the inner-test samples and the clusters through two feature sets. The definition of these features are summarized in Algorithm 3.

Feature Set 1: The distances between the new instance and the clusters of each label
This feature set captures the representation of error inside of each class including the distance of this instance to its closest adjacent instance in the class ($feature_{1.0}$), the distance of the instance with the mean-group ($feature_{1.1}$) as well as the distance of the inner-test sample with the centers of all clusters for each class (feature set: $feature_{1.2}$), the distance of the inner-test sample with the means of all clusters of each class (feature set: $feature_{1.3}$).

Feature Set 2: The changes in class representations before and after inserting the new inner-test sample

To capture the effects of error in the level of classes, the distances between the means and confidences of the clusters of each class, formed in layer 1 and layer 2, are calculated. Also, the distances between the centers and means of clusters that were formed in layer 1 and layer 2 within each class are measured. We also measure the difference between the confidence metric of original cluster formed in layer 1 and the cluster including the sample in layer 2 that represents the membership value denoted by $feature_{2.3}$.

Each instance in the training is considered as the inner-test instance for one time and then these features are calculated for this sample. The learned features in layer 3 are added to the set of the primary features of that inner-test instance. Thus, the output of the inner folding is a set of features per instance of the training. Since these features are calculated per class, they need to be differentiated from each other. Therefore, the features of each class are multiplied by the class ID to be separated from each other. For example, if we have three classes, a, b, and c, the learned features of these classes are multiplied to 1, 10, and 20, respectively to be distinguished from each other. Such separation of learned features of different classes cannot be easily handled by some classification methods, therefore, we utilized ensemble decision tree as the classifier for our approach to best treat this proposed embedded distance mechanism. In the following section, the process of feature learning for the test instances $X^{Test}$ has been described.

In this phase, as is shown in Figure 1, the entire training set along with its additional learned features can be used as the training instances in the feature learning method (i.e., the inner folding process is no longer required). Therefore, the training and test instances are fed to the three-layer feature learning method to learn corresponding features for the test instances. We would like to note that the training instances are grouped based on their labels and then clustered. The test instances, which their labels are not available, are assigned to the proper cluster of each label and then the features are learned for each test instance. Hence, this step does not require the labels of test instances. Finally, the extended training and test data sets with the learned features are fed to the classifier.