We introduce a novel discrete optimization method for training in the context of a boosting framework for large scale binary classifiers. The motivation is to cast the training problem into the format required by existing adiabatic quantum hardware. First we provide theoretical arguments concerning the transformation of an originally continuous optimization problem into one with discrete variables of low bit depth. Next we propose QBoost as an iterative training algorithm in which a subset of weak classifiers is selected by solving a hard optimization problem in each iteration. A strong classifier is incrementally constructed by concatenating the subsets of weak classifiers. We supplement the findings with experiments on one synthetic and two natural data sets and compare against the performance of existing boosting algorithms. Finally, by conducting a quantum Monte Carlo simulation we gather evidence that adiabatic quantum optimization is able to handle the discrete optimization problems generated by QBoost.
We introduce a novel discrete optimization method for training in the context of a boosting framework for large scale binary classifiers. The motivation is to cast the training problem into the format required by existing adiabatic quantum hardware. First we provide theoretical arguments concerning the transformation of an originally continuous optimization problem into one with discrete variables of low bit depth. Next we propose QBoost as an iterative training algorithm in which a subset of weak classifiers is selected by solving a hard optimization problem in each iteration. A strong classifier is incrementally constructed by concatenating the subsets of weak classifiers. We supplement the findings with experiments on one synthetic and two natural data sets and compare against the performance of existing boosting algorithms. Finally, by conducting a quantum Monte Carlo simulation we gather evidence that adiabatic quantum optimization is able to handle the discrete optimization problems generated by QBoost.
We study the problem of supervised binary classification from the perspective of deploying adiabatic quantum optimization in training. A vast body of prior academic work consisting of both theoretical and numerical studies has indicated that quantum technology promises to provide computational power that may be fundamentally superior to any classical computing methods. Given the abundance of NP-hard optimization problems that naturally arise in learning, it is clear that machine learning can immensely benefit from such an optimization tool. We describe a series of increasingly complex designs that result in computationally hard training problems of combinatorial nature. In return for accepting classical computational hardness, we retain theoretical properties such as maximal sparsity and robustness to label noise, which are otherwise sacrificed by convex methods for the sake of computational efficiency and sound theoretical footing. In order to be compatible with emerging quantum hardware technology, we formalize the training problem as quadratic unconstrained binary optimization. Our initial investigations focus on a simple training formulation with non-convex regularization that conforms to the architecture of existing quantum hardware and makes frugal use of a limited number of available physical qubits. Next, we extend this baseline formulation to a scalable algorithm, QBoost, which is able to train incrementally large-scale classifiers on data sets of practical interest. Further, we derive another algorithm, TotalQBoost, as a theoretically motivated totally corrective boosting algorithm with cardinality penalization that also makes use of quantum optimization. Both QBoost and TotalQBoost perform explicit cardinality regularization, which is the only known way of achieving maximal sparsity in the trained classifiers. We apply QBoost and TotalQBoost to three different real-world computer vision problems and make use of a quantum processor for solving the sequence of discrete optimization problems generated by one of them. Finally, we study a learning formulation with convex regularization and a non-convex loss function, q-loss, specifically designed for robust supervised learning in the presence of label noise as it occurs in practice. For compatibility with quantum hardware we derive the corresponding quadratic binary problem via variational approximation. For all proposed algorithms we compare results on a variety of popular synthetic and natural data sets against a rich selection of existing rival learning formulations.
In a previous publication we proposed discrete global optimization as a method to train a strong binary classifier constructed as a thresholded sum over weak classifiers. Our motivation was to cast the training of a classifier into a format amenable to solution by the quantum adiabatic algorithm. Applying adiabatic quantum computing (AQC) promises to yield solutions that are superior to those which can be achieved with classical heuristic solvers. Interestingly we found that by using heuristic solvers to obtain approximate solutions we could already gain an advantage over the standard method AdaBoost. In this communication we generalize the baseline method to large scale classifier training. By large scale we mean that either the cardinality of the dictionary of candidate weak classifiers or the number of weak learners used in the strong classifier exceed the number of variables that can be handled effectively in a single global optimization. For such situations we propose an iterative and piecewise approach in which a subset of weak classifiers is selected in each iteration via global optimization. The strong classifier is then constructed by concatenating the subsets of weak classifiers. We show in numerical studies that the generalized method again successfully competes with AdaBoost. We also provide theoretical arguments as to why the proposed optimization method, which does not only minimize the empirical loss but also adds L0-norm regularization, is superior to versions of boosting that only minimize the empirical loss. By conducting a Quantum Monte Carlo simulation we gather evidence that the quantum adiabatic algorithm is able to handle a generic training problem efficiently.
This paper describes how to make the problem of binary classification amenable to quantum computing. A formulation is employed in which the binary classifier is constructed as a thresholded linear superposition of a set of weak classifiers. The weights in the superposition are optimized in a learning process that strives to minimize the training error as well as the number of weak classifiers used. No efficient solution to this problem is known. To bring it into a format that allows the application of adiabatic quantum computing (AQC), we first show that the bit-precision with which the weights need to be represented only grows logarithmically with the ratio of the number of training examples to the number of weak classifiers. This allows to effectively formulate the training process as a binary optimization problem. Solving it with heuristic solvers such as tabu search, we find that the resulting classifier outperforms a widely used state-of-the-art method, AdaBoost, on a variety of benchmark problems. Moreover, we discovered the interesting fact that bit-constrained learning machines often exhibit lower generalization error rates. Changing the loss function that measures the training error from 0-1 loss to least squares maps the training to quadratic unconstrained binary optimization. This corresponds to the format required by D-Wave's implementation of AQC. Simulations with heuristic solvers again yield results better than those obtained with boosting approaches. Since the resulting quadratic binary program is NP-hard, additional gains can be expected from applying the actual quantum processor.
Ensemble learning algorithms, especially Boosting, have achieved remarkable success in classification tasks by combining multiple weak classifiers-you know, the sort that aren’t all that strong by themselves but work real well when you put them together-though traditional methods like AdaBoost? They’re prone to overfitting in noisy datasets, see? Like when a few labels are off or the data has random little glitches, they end up fitting that noise too hard instead of the real pattern, and methods like QBoost-the ones that use quantuminspired optimization, right?-they usually run into two problems: picking the right weak classifiers and just not being very fast computationally, so this study? We propose an optimized QBoost version plus a new way to build weak classifiers, just to fix those issues we mentioned, and the weak classifiers here? We made them based on decision stumps but added adaptive feature weighting, and that weighting part, by the way, helps make the weak classifiers more diverse and better at telling different classes apart, while as for the QBoost framework itself? We tweaked the objective function-threw in a regularization term, yeah?-to balance two things: getting solid classification accuracy and not letting the model get too complex, and we also used a gradient-based optimization algorithm to speed up convergence so the model doesn’t take forever to train; now, the experimental results?We tested on MNIST, CIFAR-10, and UCI Credit. The method shows 3.2% higher accuracy than AdaBoost.It cuts training time by 28%. In label-noise settings, the error rate falls by 5.7%.
QBoost, a quantum-inspired ensemble learning algorithm, has performance that depends on the quality of weak classifiers and efficiency of the optimization process. Existing methods suffer from insufficient diversity among weak classifiers and low efficiency in handling nonlinear data patterns, leading to unsatisfactory generalization ability. This study proposes a new weak classifier construction method based on pruned random decision trees-combined with a multi-objective optimized QBoost model-to fix these problems. Weak classifiers are constructed using random subspaces with adaptive tree pruning; this enhances diversity while cutting overfitting. For QBoost, the study introduces a multi-objective optimization framework to minimize classification loss and maximize weak classifier diversity at the same time, and uses an improved AdamW algorithm to speed up convergence. Experiments on KDD Cup 99, IMDb, and Covertype datasets show the proposed method hits 96.8% classification accuracy on KDD Cup 99- 3.3% higher than Gradient Boosting (93.5%) and 2.6% higher than standard QBoost (94.2%). Compared with standard QBoost, its training time drops by 37%, and it keeps 89.7% accuracy under 15% feature noise-proving better robustness. These findings confirm the proposed method effectively improves classification performance, efficiency, and diversity.
We propose a non-convex training objective for robust binary classification of data sets in which label noise is present. The design is guided by the intention of solving the resulting problem by adiabatic quantum optimization. Two requirements are imposed by the engineering constraints of existing quantum hardware: training problems are formulated as quadratic unconstrained binary optimization; and model parameters are represented as binary expansions of low bit-depth. In the present work we validate this approach by using a heuristic classical solver as a stand-in for quantum hardware. Testing on several popular data sets and comparing with a number of existing losses we find substantial advantages in robustness as measured by test error under increasing label noise. Robustness is enabled by the non-convexity of our hardware-compatible loss function, which we name q-loss.