Extreme entropy machines: robust information theoretic classification

There is no one, universal, perfect optimization criterion that can be used to train machine learning model. Even for linear classifiers, one can find multiple objective functions, error measures to minimize, regularization methods to include [15]. Most existing classification methods are aimed at minimization of empirical risk (through some simple point-based error measured with loss function) with added regularization. We propose to approach this problem in more information theoretic way by investigating applicability of entropy measures as a classification model objective function. We focus on quadratic Renyi’s entropy and connected Cauchy–Schwarz Divergence.

One of the information theoretic concepts which has been found very effective in machine learning is the entropy measure. In particular, the rule of maximum entropy modeling led to the construction of MaxEnt model and its structural generalization—Conditional Random Fields which are considered state of the art in many applications. In this paper, we propose to use Renyi’s quadratic cross entropy as the measure of two densities’ estimations divergence to find the best linear classifier. It is a conceptually different approach than typical entropy models as it works in the input space instead of decisions distribution. As a result, we obtain a model closely related to the Fisher Discriminant (or more generally Linear Discriminant Analysis) which deepens the understanding of this classical approach. Together with a powerful extreme data transformation, we obtain a robust, nonlinear model competitive with the state of the art models not based on information theory such as Support Vector Machines (SVM [4]), Extreme Learning Machines (ELM [11]) or Least Squares Support Vector Machines (LS-SVM [23]). We also show that under some simplifying assumptions ELM and LS-SVM can be seen through a perspective of information theory as their solutions are (up to some constants) identical to the ones obtained by proposed method.

To draw the general idea of proposed method, we shortly summarize it here. Figure 1 is provided for better intuition. We begin with data in the input space \(\mathcal {X}\), transform it randomly into Hilbert space \(\mathcal {H}\) where we model them as Gaussians, then perform optimization leading to the projection on \(\mathbb {R}\) through \(\varvec{\beta }\) and perform density-based classification leading to nonlinear decision boundary in \(\mathcal {X}\). It is worth noting that as a result we obtain model that:Paper is structured as follows: first, we recall some preliminary information regarding ELMs and Support Vector Machines, including Least Squares Support Vector Machines. Next, we introduce extreme entropy machine (EEM) together with its kernelized extreme counterpart—extreme entropy kernel machine (EEKM). We show some connections with existing models and some different perspectives for looking at proposed model. In particular, we show how learning capabilities of EEMs (and EEKM) resemble those of ELM (and LS-SVM, respectively). During evaluation on over 20 binary datasets (of various sizes and characteristics), we analyze generalization capabilities and learning speed. We show that it can be a valuable, robust alternative for existing methods. In particular, we show that it achieves analogous of ELM stability in terms of the hidden layer size. We conclude with future development plans and open problems.

Let us begin with recalling some basic information regarding extreme learning machines [12] and Support Vector Machines [4] which are further used as a competing models for proposed solution. We focus here on the optimization problems being solved to underline some basic differences between these methods and EEMs.

Let us first recall the formulation of the linear classification problem in the highly dimensional feature spaces, i.e., when number of samples N is equal (or less) than dimension of the data space, \(\mathrm {dim}(\mathcal {H})\). In particular, we formulate the problem in the limiting case² when \(\mathrm {dim}(\mathcal {H})=\infty\):

Observe that in itself (without additional regularization) the problem is not well posed as, by applying the linear independence of the data, for arbitrary \(m_+ \ne m_-\) in \(\mathbb {R}\) we can easily construct \(\varvec{\beta }\in \mathcal {H}\) such thatHowever, this leads to a model case of overfitting, which typically yields suboptimal results on the testing set (different from the original training samples).

To make the problem well posed, we typically need to:Popular choices of the objective function include per-point classification loss (like square loss in neural networks or hinge loss in SVM) with a regularization term added, often expressed as the square of the norm of our operator \(\varvec{\beta }\) (like in SVM or in weight decay regularization of neural networks). In general, one can divide objective functions derivations into following categories:We focus on the last group of approaches, and investigate the applicability of the Cauchy–Schwarz Divergence [13], which for two densities f and g is given byCauchy–Schwarz Divergence is connected to Renyi’s quadratic cross entropy (\(H_2^\times\) [21]) and Renyi’s quadratic entropy (\(H_2\)), defined for densities f, g asconsequentlyand as showed in [7], it is well suited as a discrimination measure which allows the construction of multi-threshold linear classifiers. In general, increase of the value of Cauchy–Schwarz Divergence results in better sets’ (densities’) discrimination. Unfortunately, there are a few problems with such an approach:There are basically two approaches which help us recover underlying densities from the samples. First one is performing some kind of density estimation, like the well-known Kernel Density Estimation (KDE) technique, which is based on the observation that any arbitrary continuous distribution can be approximated arbitrarily closely by the convex combination of Gaussians [26]. The other approach is to assume some density model (distribution’s family) and fit its parameters to maximize the data generation probability. In statistics, it is known as maximum likelihood estimation (MLE) approach. MLE has an advantage that in general it produces much simpler densities descriptions than KDE as the second one’s description scales linearly in terms of sample size.

A common choice of density models are Gaussian distributions due to their nice theoretical and practical (computational) capabilities. As mentioned earlier, the convex combination of Gaussians can approximate the given continuous distribution f with arbitrary precision. To fit a Gaussian mixture model (GMM) to given dataset, one needs an algorithm such as Expectation Maximization [8] or conceptually similar Cross-entropy clustering [25]. However, for simplicity and strong regularization, we propose to model f as one big Gaussian \(\mathcal {N}({{\mathbf{m}}},{\mathbf{\Sigma }})\). One of the biggest advantages of such an approach is closed-form MLE parameter estimation, as we simply put \({\mathbf{m}}\) equal to the empirical mean of the data, and \({\mathbf{\Sigma }}\) as some data covariance estimator. Second, this way we introduce an error to the data which has an important regularizing role and leads to better posed optimization problem.

Let us recall that the Shannon’s differential entropy (expressed in nits) of the continuous distribution f isWe will show that choice of normal distributions is not arbitrary but supported by the assumptions of the entropy maximization. Following result is known [5], but we include the whole reasoning for completeness.

There appears nontrivial question how to find/estimate the desired Gaussian as the covariance can be singular. In this case, to regularize the covariance, we apply the well-known Ledoit–Wolf approach [16]where \(\mathrm {cov}(\cdot )\) is an empirical covariance and \(\varepsilon ^\pm\,\) is a shrinkage coefficient given in closed form by Ledoit and Wolf [16]. We would like to underline that this estimator is parameterless and is optimal in the sense that it minimizes the expected quadratic loss between true covariance matrix and the estimator under general asymptotics (meaning that both dataset size and its dimension grow to infinity, but their ratio converges to a constant).

Thus, our optimization problem can be stated as follows:

Because \({\mathbf{H}}^\pm\,\) has density \(\mathcal {N}({\mathbf{m}}^\pm\,,{\mathbf{\Sigma }}^\pm\,)\), we know that \(\varvec{\beta }^\mathrm{T}\mathbf{X}^\pm\,\) has the density \(\mathcal {N}(\varvec{\beta }^\mathrm{T}{\mathbf{m}}^\pm\,,\varvec{\beta }^\mathrm{T}{\mathbf{\Sigma }}^\pm\,\varvec{\beta }).\) We putSince, as one can easily compute [6],we obtain thatObserve that in the above equation the first term is constant, the second is the logarithm of the quotient of arithmetical and geometrical means and therefore in the typical cases is bounded and close to zero. However, in some singular cases, when \(S_+\) and \(S_-\) are of different order of magnitude the above term can blow up, and thus more precisely here we are maximizing a lower bound of \({D}_\mathrm{CS}\). As we will see in further sections, this simplification leads to the closed-form solution, which in particular means that learning process is extremely simple. In general, one could maximize the whole function using gradient methods, but this would lead to the need of introducing optimization procedure hyperparameters (such as learning rate, momentum, stopping condition, etc.) which we are trying to avoid.

Consequently, crucial information is given by the last term. To confirm this claim, we perform experiments on over 20 datasets used in further evaluation (more details are located in the Evaluation section). We compute the Spearman’s rank correlation coefficient between the \({D}_\mathrm{CS}(\mathcal {N}(m_+,S_+),\mathcal {N}(m_-,S_-))\) and \(\frac{(m_+-m_-)^2}{S_++S_-}\) for hundred random projections to \(\mathcal {H}\) and hundred random linear operators \(\varvec{\beta }\). As one can see in Table 1, in small datasets (first part of the table) the correlation is generally high, with some exceptions (like sonar, splice, liver disorders and diabetes). However, for bigger datasets (consisting of thousands examples), this correlation is nearly perfect (up to the randomization process it is nearly 1.0 for all cases) which is a very strong empirical confirmation of our claim that maximization of the \(\frac{(m_+-m_-)^2}{S_++S_-}\) is generally equivalent to the maximization of \({D}_\mathrm{CS}(\mathcal {N}(m_+,S_+),\mathcal {N}(m_-,S_-))\) as correlation coefficient captures if \({D}_\mathrm{CS}\) and its lower bound have similar monotonicity. Number of dimensions of the Hilbert space does not affect the result in a significant manner for large datasets, while in the case of small ones it seems that results vary significantly when it is changed. This might be the consequence of less reliable covariance estimations for small datasets, especially with higher number of dimensions.

This means that, after the above reductions, and application of (2) our final problem can be stated as follows:

To illustrate our reasoning, we consider a typical basic problem concerning the density estimation.

Since the problem in itself is infinite dimensional, typically the data would be linearly independent [20]. Moreover, one usually cannot obtain reliable density estimation—the most we can hope is that after transformation by a linear functional into \(\mathbb {R}\), the resulting density will be well estimated.

The generalization of the above problem is given by the following problem:

In general, \(\text {dim}(\mathcal {H}) \gg N\)which means that we have very sparse data in terms of Hilbert space. As a result, classical kernel density estimation (KDE) is not reliable source of information [18]. In the absence of different tools, we can however use KDE with very big kernel width to cover at least some general shape of the whole density.

Proof of this remark is given by Czarnecki and Tabor [7] and means that if we perform a Gaussian kernel density estimation of our data with big kernel width (which is reasonable for small amount of data in highly dimensional space) then for big enough \(\hat{\sigma }\) EEM is nearly optimal linear classifier in terms of estimated densitiesLet us now investigate the probabilistic interpretation of EEM. Under the assumption that \({\mathbf{H}}^\pm\,\sim \mathcal {N}({\mathbf{m}}^\pm\,, {\mathbf{\Sigma }}^\pm\,)\), we have the conditional probabilitiesso from Bayes rule we conclude thatwhere \(p(\pm\,)\) is a prior classes’ distribution. In our case, due to the balanced nature (meaning that despite classes imbalance we maximize the balanced quality measure such as Balanced Accuracy), we have \(p(\pm\,)=1/2\).

ButsoFurthermore, it is easy to show that under the normality assumption, the resulting classifier is optimal in the Bayesian sense.

First, we show that under some simplifying assumptions, proposed method behaves as Extreme Learning Machine (or Weighted Extreme Learning Machine [30]).

Before proceeding further, we would like to remark that there are two popular notations for projecting data onto hyperplanes. One, used in ELM model, assume that \({\mathbf{H}}\) is a row matrix and \(\varvec{\beta }\) is a column vector, which results in the projection’s equation \({\mathbf{H}}\varvec{\beta }\). Second one, used in SVM and in our paper, assumes that both \({\mathbf{H}}\) and \(\varvec{\beta }\) are column oriented, which results in the \(\beta ^\mathrm{T}{\mathbf{H}}\) projection. In the following theorem, we will show some duality between \(\varvec{\beta }\) found by ELM and by EEM. To do so, we will need to change the notation during the proof, which will be indicated.

Similar result holds for EEKM and Least Squares Support Vector Machine.

Both theorems can be extended to non-balanced datasets if we consider a Weighted ELM and Balanced LS-SVM. Proposed method has a balanced nature, so it internally assumes that classes priors are equal to 1/2. In the proofs, we show that when this is a true assumption, ELM and LS-SVM lead (under some assumptions) to the same solution. If one includes the same assumption in these two methods (through Weighted ELM and Balanced LS-SVM), then they again will solve the same problem despite true classes priors. We omit the exact proof as they are analogous to the above.

In previous sections, we investigated the limiting case when \(\mathrm {dim}(\mathcal {H}) =\infty\). However, in practice, we choose h random nonlinear projections which embed data in a high-dimensional space (with dimension at least h, but we can still consider it as an image in higher dimensional space, analogously to how Gaussian kernel actually maps to infinitely dimensional space by projecting through just N functions). As we show in further evaluation, it is sufficient to use h which is much smaller than N, so resulting computational complexities, cubic in h, are acceptable.

We can formulate the whole EEM training as a very simple algorithm (see Algorithms 1, 2).

Resulting model consists of three elements:As described before, \(\mathrm {F}\) can be further compressed to just one or two thresholds \(t_\pm\,\) using equations from previous sections. Either way, complexity of the resulting model is linear in terms of hidden units and classification of the new point takes \(\mathcal {O}(dh)\) time.

During EEM training, the most expensive part of the algorithm is the computation of the covariance estimators and inversion of the sum of covariances. Even computation of the empirical covariance takes \(\mathcal {O}(Nh^2)\) time so the total complexity of training, equal to \(\mathcal {O}(h^3 + Nh^2) = \mathcal {O}(Nh^2)\), is acceptable. It is worth noting that training of the ELM also takes exactly \(\mathcal {O}(Nh^2)\) time as it requires computation of \({\mathbf{H}}^\mathrm{T}{\mathbf{H}}\) for \({\mathbf{H}}\in \mathbb {R}^{N \times h}\). Training of EEMK requires additional computation of the square root of the sampled kernel matrix inverse \(\mathrm {K}(\mathbf{X}^{[h]},\mathbf{X}^{[h]})^{-1/2}\) but as \(\mathrm {K}(\mathbf{X}^{[h]},\mathbf{X}^{[h]}) \in \mathbb {R}^{h \times h}\) can be computed in \(\mathcal {O}(dh^2)\) and both inverting and square rooting can be done in \(\mathcal {O}(h^3)\) we obtain exact same asymptotical computational complexity as the one of EEM. Procedure of square rooting and inverting are both always possible as assuming that \(\mathrm {K}\) is a valid kernel in the Mercer’s sense yields that \(\mathrm {K}(\mathbf{X}^{[h]},\mathbf{X}^{[h]})\) is strictly positive definite and thus invertible. Further comparison of EEM, ELM and SVM is summarized in Table 2.

Next aspect we would like to discuss is the cost-sensitive learning. EEMs are balanced models in the sense that they are trying to maximize the balanced quality measures (like Balanced Accuracy or GMean). However, in practical applications, it might be the case that we are actually more interested in the positive class than the negative one (like in the medical applications). Proposed model gives a direct probability estimates of \(p(\varvec{\beta }^\mathrm{T}{\mathbf{h}}|t)\), which we can easily convert to the cost-sensitive classifier by introducing the prior probabilities of each class. Directly from Bayes Theorem, given \(p(+)\) and \(p(-)\), we can label our new sample \({\mathbf{h}}\) according toso if we are given costs \(C_+, C_- \in \mathbb {R}_+\) we can use them as weighting of priorsLet us now investigate the possible efficiency bottleneck. In EEKM, the classification of the new point \({\mathbf{h}}\) is based onOne can convert EEKM to the SLFN by putting:so the classification rule becomesThis way complexity of the new point’s classification is exactly the same as in the case of EEM and ELM (or any other SLFN).

For the evaluation purposes, we implemented five methods, namely: Weighted Extreme Learning Machine (WELM [30]), Extreme Entropy Machine (EEM), Extreme Entropy Kernel Machine (EEKM), Least Squares Support Vector Machines (LS-SVM [23]) and Support Vector Machines (SVM [4]). All experiments were performed using machine with Intel Xeon 2.8Ghz processors with enough RAM to fit any required computations.

All methods with the exception of SVM were implemented using Python with use of numpy [27] and scipy [14] libraries included in anaconda ⁴ for fair comparison. For SVM, we used highly efficient libSVM [3] library with bindings available in scikit-learn [19]. Random projection-based methods (WELM, EEM) were tested using following three generalized activation functions \(\mathrm {G}({\mathbf{x}} ,{\mathbf{w}} ,b)\) Random parameters (weights and biases) were selected from uniform distributions on [0, 1]. Training of WELM was performed using Moore–Penrose pseudoinverse and of EEM using Ledoit–Wolf covariance estimator, as both are parameterless, closed-form estimators of required objects. For kernel methods (EEKM, LS-SVM, SVM), we used the Gaussian kernel (rbf) \(\mathrm {K}_\gamma ({\mathbf{x}} _i,{\mathbf{x}} _j)=\exp (-\gamma \Vert {\mathbf{x}} _i-{\mathbf{x}} _j \Vert ^2 )\). In all methods requiring class balancing schemes (WELM, LS-SVM, SVM), we used balance weights \(w_i\) equal to the ratio of bigger class and current class (so \(\sum _{i=1}^N w_i t_i = 0\), which is equivalent to having \(w_i=({\max _{t\in \{-,+\}} N_t})/{N_{t_i}}\)).

Hyperparameters of each model were fitted, performed grid search included: hidden layer size \(h=50,100,250,500,1000\) (WELM, EEM, EEKM), Gaussian Kernel width \(\gamma =10^{-10},\ldots ,10^0\) (EEKM, LS-SVM, SVM), SVM regularization parameter \(C=10^{-1},\ldots ,10^{10}\) (LS-SVM, SVM).

Datasets’ features were linearly scaled (per feature) to have each feature in the interval [0, 1]. No other data whitening/filtering was performed. All experiments were conducted in repeated tenfold stratified cross-validation.

We use following evaluation metricwhere TP represents true positives, TN true negatives, FP false positives, FN false negatives. We choose it due to the balanced nature and usage in previous works regarding Weighted Extreme Learning Machines [30], however very similar results can be obtained for Balanced Accuracy (which is an arithmetic mean of accuracies over each class).

In this paper, we have presented Extreme Entropy Machines, models derived from the information theoretic measures and applied to the classification problems. Proposed methods are strongly related to the concepts of Extreme Learning Machines (in terms of general workflow, rapid training and randomization) as well as Support Vector Machines (in terms of margin maximization interpretation as well as LS-SVM duality).

Main characteristics of EEMs are:Performed evaluation showed that, similar to ELM, proposed EEM is a very stable model in terms of the size of the hidden layer and achieves comparable classification results to the ones obtained by SVMs and ELMs. Furthermore, we showed that our method scales better to truly big datasets (consisting of hundreds of thousands of examples) without sacrificing results quality.

During our considerations, we pointed out some open problems and issues, which are worth investigation: