Achieving More with Less: A Tensor-Optimization-Powered Ensemble Method

Assuming we are addressing a $c$-class classification problem, where $x_{i}$ represents the $i$-th sample before ensemble training with $k$ classifiers $G_{1},...,G_{k}$, each basic classifier inputs $x_{i}$ and outputs a c-dimensional indicator column vector $G_{j}(x_{i})=(0,...,1,...,0)^{T}\in\mathbb{R}^{c\times 1}$. Suppose the true labels are represented by $y\in\mathbb{R}^{c\times 1}$, and each element of $y$ is one-hot encoded, where $m_{i}$ is the class of the $i$-th sample, forming the indicator matrix $Y\in\mathbb{R}^{c\times n}$. If $g_{i}$ is a column vector satisfying $g_{i}=(G_{1}^{T}(x_{i}),...,G_{k}^{T}(x_{i}))^{T}$, the $g_{i}\in\mathbb{R}^{kc\times 1}$ combining all of $g_{i}$ gives matrix $G=(g_{1}^{T},...,g_{n}^{T})^{T}$ , and matrix $G\in\mathbb{R}^{kc\times n}$

Margin represents the distance from data points to the decision boundary. First, let’s introduce how predictions are made using the confidence tensor $\tilde{\mathbf{\Theta}}$. The tensor $\tilde{\mathbf{\Theta}}$ has three dimensions: $c$ dimensions, $c$ dimensions, and $k$ dimensions. Here, $\tilde{\mathbf{\Theta}}_{rst}$ signifies that the $t$-th base classifier assigns the sample to class $r$ while it actually belongs to class $s$ . The probabilities for all classes are combined into this confidence tensor $\tilde{\mathbf{\Theta}}$. However, tensors are not straightforward to handle in matrix computations. Therefore, we split it into matrix $\Theta$ using forward slicing, as illustrated in the diagram below, so $\Theta\in\mathbb{R}^{c\times kc}$.

Define $\mathcal{S}$ as the softmax function. When $\mathcal{S}$ is applied to a column vector, it performs softmax normalization on the column vector. When $\mathcal{S}$ is applied to a matrix, it applies the softmax function to each column of the matrix. Based on this, the prediction for the $i$-th sample can be expressed as

A suitable definition of the margin for multi-class classification is the difference between the predicted value at the true label position and the second largest predicted value. This can be expressed as formula

with the symbol $max_{2}(v)$ representing the second largest element in vector $v$, $Y_{i}$ is the $i$-th column of $Y$, additionally, the symbol $\odot$ represents the Hadamard product of matrices. This definition is reasonable as it reflects the confidence in classifying into the true class.

However, both the maximum function and the $max_{2}$ function are non-smooth, and non-smooth functions can significantly affect the convergence and convergence speed of the algorithm. A reasonable solution is to approximate these functions using the log-sum-exp function. For a vector $v$, by choosing a suitable $\alpha$, the log-sum-exp function can effectively approximate the largest element in $v$. The expression for the log-sum-exp function is given by Eq.(3).

The choice of parameter $\alpha$ is straightforward and does not significantly affect the degree of approximation (Calafiore, Gaubert, and Possieri 2020). Through extensive experiments, we found that when $\alpha$ is set to 10, it can already extract the maximum value with considerable accuracy.

Using the log-sum-exp function, the $max_{2}$ function can be easily represented. To extract the second largest value, we only need to set the maximum position to 0 and then retrieve the maximum value again. We assume that the predicted value at the true class is the largest, which is reasonable, and we will explain this later. This can be expressed using the following formula:

Thus, the margin contributed by the $i$-th item can be expressed as Eq.(5),

and the total margin can be expressed as:

Now let’s return to consider the assumptions made at Eq.(4). In the previous margin calculation, the actual $max_{2}(\mathcal{S}\left(\Theta g_{i}\right))$ should be the maximum of

where $\mu$ is $\underset{j=1...c}{argmax}(\mathcal{S}\left(\Theta g_{i}\right))_{j}$. $Y^{\mu}$ represent the column vector where $\mu$-th element is 1 and others are 0. but we calculate the maximum of

this is because subtracting the linear term results in a margin function with better smoothness and convexity. In fact, we make the following assumption:

This essentially assumes correct classification. To ensure this, we need to incorporate a penalty for misclassification in the constraints. Cross-entropy can effectively measure accuracy in the classification process. Therefore, we add the accuracy function as follows:

The final optimization objective is a negative confidenceed combination of both

where the confidence $\gamma$ is a hyperparameter. A larger $\gamma$ indicates a greater preference for higher confidence in classification, thus larger margin. Specifically, when $\gamma$ equals 0, it reverts to the standard cross-entropy loss function used for classification. Therefore, the cross-entropy function is a special case of the loss function we are using.

In this section, we will introduce the final optimization problem. Actually, the accuracy of each base classifier varies, so naturally, the confidences of each base classifier should also differ. Let’s denote the accuracy of the $i$-th base classifier as $w_{i}$, where $w=(w_{1},...,w_{k})^{T}$, $\tilde{w}$ expands $w$ to $kc$ dimensions , expressed in formula as:

Assigning confidences to each classifier can be seen as imposing constraints on $\Theta$’s columns, with the constraint being $\Theta^{T}1=\tilde{w}$.

In summary, the final optimization problem can be formulated as:

and the loss function $\mathcal{L}$ is

In this section, we will analyze the time complexity of the algorithm. The algorithm computes gradients by selecting a batch of samples at a time. Note that while $g_{i}$ is a vector of dimension $kc$, according to the definition, $g_{i}$ is a vector composed of predictions from each classifier, meaning $g_{i}$ is sparse. Computing the matrix multiplication $\Theta$ with $g_{i}$ involves adding corresponding positions of $\Theta$ together, without needing multiplication.

In other words, computing the gradient for each element according to Eq.(22) has a time complexity of $\mathcal{O}(kc)$. During the computation, there are many common terms that can be retained to simplify calculations. With $\mathcal{O}(kc^{2})$ parameters, the time complexity for updating once will not exceed $\mathcal{O}(k^{2}c^{3})$. Assuming convergence after $N$ iterations, the total time complexity will not exceed $\mathcal{O}(Nk^{2}c^{3})$.

However, in practice, $k$ and $c$ are usually very small, and there are a lot of direct additions in calculations. Moreover, hardware acceleration with tools like PyTorch enables automatic differentiation, making the actual runtime very fast.

We conducte extensive experiments on ten datasets, including TR41, warpPIE10P, Movement, Ecoil, Arcene, REUT, GLI85, Carcinom, Lung and Isolet. The Table 2 lists the number of samples and clusters for each dataset:

Our experimental results are recorded in Tables 3, 4, and 5. Table 3 presents the accuracy of various algorithms on the training set, Table 4 records the accuracy of the algorithms on the test set, and Table 5 shows the accuracy of the algorithms on the entire dataset.

From the experiments, we can see that for the Random Forest algorithm, the larger the number of base classifiers, i.e., decision trees, the higher the accuracy. On the vast majority of datasets, our algorithm outperforms other algorithms in terms of accuracy on the training set, test set, and the entire dataset. It even surpasses the Random Forest algorithm with ten times the number of base classifiers as our algorithm, achieving the goal of outperforming large-scale ensemble classifiers with a smaller ensemble.

To verify that our algorithm indeed has very good convergence properties, we select several datasets and plot the iteration curves of our algorithm on these datasets, as shown in Figure 4. Because the gradient descent method is very fast, we used full gradient descent in the experiments, i.e. computing the gradient using all samples.

Our objective function possesses partially convex properties, the algorithm typically converges quickly. As observed in the experiments, convergence is usually achieved within no more than 10 iterations.

In this section, we will discuss the relationship between our algorithm and the classic random forest, assuming that decision trees are used as base classifiers.

In this section, we will explain why our algorithm performs better using a simple example.

Our algorithm seems to learn a set of confidences for bagging, but in fact, it can be easily extended to a stacking algorithm. We do not enforce that base classifiers must be of the same type; instead, we can combine and learn confidences for different base classifiers such as decision trees, support vector machines, and logistic regression. Furthermore, a potential extension is to analyze the performance of heterogeneous base classifiers on different types of datasets.