Fast optimization of Multithreshold Entropy Linear Classifier

Many methods of speeding up the kernel density estimator's (KDE) querying process has been proposed in the literature [12, 14, 6]. As op-1 timization problem introduced in Multithreshold Entropy Linear Classifier [5] is closely related to the equations of KDE it appears natural that similar techniques can be used to simplify its computations with a bounded error. Importance of such reductions comes from the high (quadratic) complexity of the evaluation of functions required during training of this model which makes it hard to use for any dataset with more than a thousand points. In this paper we investigate two such approaches, first - sorting and discarding, which ignores computations of similarities between points that are too far away to have big impact on the function's value, second - binning, which smooths the function construction in order to heavily reduce amount of unique points. Both these methods are introduced in an adaptive manner so the optimization process have fixed error bound despite many different linear projections being analyzed during the training phase. We also show a very simple method which enables to use a wide range of optimization algorithms even though proposed model requires optimization with a specific constraints (sphere bounded).