The Quantum Version of Random Forest Model for Binary Classification Problem

Abstract

We suggest the quantum version of prediction using random forest model for binary classification problem. The idea of the paper is to combine quantum amplitude amplification algorithm and the probabilistic aggregation of the results of different decision trees in the forest. Quantum amplitude amplification algorithm is used as a subroutine and helps us to quadratically speed up a prediction. In the classical case, a random forest model works in , where is a number of trees in a forest and is a running time of prediction on one tree. The running time of our version is (√ ).

Keywords

• 1 Quantum Random Forest
• Random Algorithms
• Binary Classification

1. Introduction

Random forest is an ensemble of decision trees model of machine learning [ 4, 17 ] that is used for classification and regression problems. It is based on the bagging (bootstrap aggregation) method [ 7, 26 ]. To construct each decision, tree the random forest randomly chooses input data and attributes. Decision tree [ 9, 13, 20, 23 ] is a simple and intuitive method for solving classification problems, but it is also used for regression problems. Each non-leaf node of a tree is a rule for going to a particular child node. The result is in a leaf of the tree.

Let be a number of trees in a forest. It is used for predictions of each tree and getting a result. We get results from each tree. Random forest averages a result for regression problem. A result of a random forest model is obtained by voting of all trees for classification problems.

To construct decision trees random forest uses such famous algorithms as Id3, C4.5 [ 24 ], C5.0 [1], CART [ 10 ]. We propose to create a random forest model using our quantum version of constructing decision tree algorithm [ 19 ]. It allows us to build a tree for ( √ ), is the size of a training data set, is a number of attributes of each element, is a tree height (a given parameter). In classical case the running time is equal to for binary classification problem. The variables and are different for each tree and selected by bagging method. In addition, in this work [ 5 ] the authors consider the problems where they note an influence of pseudorandom and quantum-random number generators also for quantum random forest. We can also use other quantum decision tree constructing algorithms [ 22 ] or use classical version of random forest [ 14 ].

Let be the running time of a prediction on one tree. Thus the running time of a prediction on random forest model is .

Quantum machine learning [ 2, 3, 21 ] is a new direction in artificial intelligence sphere. Quantum computing and the known quantum algorithms let speed up classical machine learning algorithms that use big data or to increase accuracy.

In this paper we present a quantum version of prediction a result for some input object. Our algorithm is based on quantum amplitude amplification algorithm [ 6 ] and has a running time equal to (√ ).

We can consider a random forest model as one classifier from big classification metamodel. In this case, the model should return a probability of belonging to a class. Due to large datasets this method, combination of big models, is needed high computing capabilities and becomes popular only recent. This method is named a stacked generalization [ 8, 27 ]. For example, in works [ 12, 18 ] the authors use a random forest model as a one classifier.

Quantum computing can be useful with this approach. In work [ 25 ] the authors offer the quantum algorithm to construct an ensemble of quantum classifiers also for binary classification problem. They suggest use any quantum machine learning algorithm as classifier. Results of classifiers are computed in parallel. An answer for some input object is evaluated from a single qubit measurement. In the algorithm the authors use some abstract classifier, therefore, the paper does not have a running time analysis of the algorithm.

The paper has the following structure. Section 2 contains brief information about random forest model. We present our probabilistic algorithm for prediction a result for binary classification problem in Section 3. 2. 2.1.

Random Forest

Decision Trees

A decision tree [ 23, 9, 20 ] is simple, fast and intuitive the machine learning method. It uses for classification, regression and clustering problems. Decision trees consist of inner nodes, which contain a simple rule as , and leaf nodes that contain an answer. The disadvantage of a decision tree is overfitting [ 11 ].

Random forest [ 16 ] uses an ensemble of decision trees. It is based on bootstrap aggregation method. A random forest model creates a new training dataset by randomly selecting data or attributes from a given dataset for each tree. It allows us avoid such problem as overfitting.

Let be a number of trees in the learned random forest. A number of trees is a given parameter of fitting the random forest model. It is selected by minimizing errors in the test sample. 2.2.

Prediction

In prediction process an input object step by step passes through the rules written in tree nodes. It works in , where is a height of a tree. Heights of trees from forest can be different because height is a given parameter, and we can construct trees with different heights to increase accuracy. Let us take as a running time of prediction on one tree.

This process is repeated on each tree from a forest. The running time of prediction of random forest model is equal to . An answer is obtained by voting or averaging the result.

Let us present most popular formula for averaging a result.

Let be a result of -th tree. The general result of random forest can be presented: for regression problem, for example.

For classification problem we use the voiting method. It can be presented by formula: where

∑ { ∑ is a number of classes.

Bellow we suggest another version to compute the answer for binary classification. 2.3.

Probabilistic Algorithm

Let us consider the next problem. There are two classes: and , a learned random forest model for binary classification problem. The model should determinate a result class for an input object . It can return an answer ( or ) or a probability of belonging of for the first class.

Let each tree of a forest returns a probability of belonging to the first class. Let be a probability of an input object belongs to the first class and be obtained by -th tree. Then, is a probability of the second class for -th tree.

Let us consider the following probabilistic algorithm. We randomly select any tree from the random forest. We choose a tree with a number . All trees can be selected with equal probability. We classifier an object by the -th tree and get , it is a probability of belongs to the first class. Thus a probability of the -th tree is selected and returns a probability of the first class for an input object is equal to , where is a number of trees in the forest. Then, the general probability of the forest will return the first class is ∑ ∑ where is a probability of the first class getting by -th tree.

We propose the quantum algorithm for computing the value .

3. The Quantum Version of Random Forest Prediction

Our quantum version of prediction a result for binary classification problem uses quantum amplitude amplification algorithm based on Grover's search quantum algorithm [ 15 ].

Let us consider the idea of quantum amplitude amplification algorithm. There is some probabilistic algorithm that can find an element with probability . Let a set of elements be given. Let be a probability to find a marked element . The sum of probabilities of all elements in is ∑ . We repeat the finding process

( )times on the average before we find .

The quantum amplitude amplification allows us to find the marked element in for ( ). √ Each tree of a forest returns a number of class (1 or 2) with some probability. Then, we find the with the probability ∑ . If we know , we can repeat a search process of the first class (

√ amplification algorithm. Let us consider our approach to compute .

)times on the average to get the first class in set . This is the idea of quantum amplitude Let be , where . The variable changes until the amplitude amplification returns the first class.

Let the subroutine be the quantum amplitude amplification algorithm. It gets such parameters as:  is a set of learned trees,  is an input object,  is a probability of belonging to the first class.

The function uses trained trees of the random forest. The quantum procedure allows us test in parallel an input object on each tree in .

Lemma 1 The works in ( √ ). 3.1.

The Running Time

estimation to return only an answer ( or ) for

Let us consider the running time of our quantum version of prediction a result by a random forest model. The running time of Algorithm 1 and Algorithm 2, presented in Figure 1 and Figure 2 correspondingly, is the same and is showed bellow.

Theorem 1

The running time of the our quantum version of prediction a result for some input object binary classification problem is (√ ) for where is a number of trees in forest and

Proof.

Let , where , returns the second class. We can say

The running time of the algorithm is

We can compute as follow. Let and We get

is the running time of prediction on one tree.

changes while the (∑ √ ) (√ ) ( √

) for ∑ ∑

. Then, ( ) (√ )

√ Moreover in Algorithm 2 (presented in Figure 2) we can stop the loop when will be 2, because follows . It means the probability of the second class is more than the probability of the first class. In this case the algorithm can return the answer .

4. Conclusion

We have considered a method for finding the probability of an input object belonging to the first class for a binary classification problem by a random forest model. The forest contains trees constructed by any method: quantum or classical algorithms. A new input object passes through the conditions contained in the tree nodes. To predict a result on one tree it needs running time.

Our method of prediction is based on the quantum amplitude amplification algorithm and uses the idea of probabilistic solution. As an answer, we used the arithmetic mean of the probabilities of belonging to the first class of an input object of all trees ∑ . Our algorithm can return or as an answer or the value . It allows us quadratically speed up a prediction.

In classical case a prediction works in . We propose the quantum version of a prediction that works in (√ ), where is the running time of a prediction of one tree.

In the further we plan to implement our algorithm on quantum simulator and to test it on some machine learning problem.

5. Acknowledgements

6. References

The research is funded by the subsidy allocated to Kazan Federal University for the state assignment in the sphere of scientific activities, project No. 0671-2020-0065.

[1] C5.0: An informal tutorial (2019), URL: https://www.rulequest.com/see5-unix.html

References

[2] F. Ablayev , Ablayev M. , Huang J ., K. Khadiev , N. Salikhova , D. Wu , On quantum methods for machine learning problems part i: Quantum tools . Big Data Mining and Analytics pp. 41 - 55 ( 2019 )

[3] F. Ablayev , Ablayev M. , Huang J ., K. Khadiev , N. Salikhova , D. Wu , On quantum methods for machine learning problems part ii: Quantum classification algorithm . Big Data Mining and Analytics pp. 56 - 67 ( 2019 )

[4] E. Alpaydin , Introduction to machine learning . MIT press ( 2020 )

[5] J. Bird , A. Ekart , D. Faria , On the effects of pseudorandom and quantum-random number generators in soft computing . Soft Comput 24 ( 2020 )

[6] G. Brassard , P. Hoyer , M. Mosca , A. Tapp , Quantum amplitude amplification and estimation . Contemporary Mathematics pp. 53 - 74 ( 2002 )

[7] L. Breiman , Bagging predictors . Mach Learn , 24 pp. 123 - 140 ( 1996 )

[8] L. Breiman , Stacked regressions . Neural Networks pp. 49 - 64 ( 1996 )

[9] L. Breiman , Random forests . Machine Learning , 45 pp. 5 - 32 ( 2001 )

[10] L. Breiman , J. Friedman , R. Olshen , C. Stone , Classification and regression trees ( 1984 )

[11] C. Brian , T. Griffiths , "Chapter 7: Overfitting" , Algorithms To Live By: The computer science of human decisions . William Collins ( 2017 )

[12] N. P. M. Chand , C.R. Krishna , E.S. Pill , M.C. Govil , A comparative analysis of svm and its stacking with other classification algorithm for intrusion detection . International Conference on Advances in Computing, Communication , Automation, (ICACCA)(Spring) pp. 1 - 6 ( 2016 )

[13] scikit-learn developers: Decision trees , https://scikitlearn.org/stable/modules/tree.html

[14] scikit-learn developers: Random forest classifier , https://scikitlearn.org/stable/modules/generated/sklearn.ensemble.RandomForestClassifier.html

[15] L. Grover , A fast quantum mechanical algorithm for database search . In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , pp. 212 - 219 ( 1996 )

[16] T. Hastie , R. Tibshirani , J. Friedman, The elements of statistical learning: Data mining, inference, and prediction . Springer-Verlag p. 746 ( 2009 )

[17] T. Hastie , R. Tibshirani , J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Second Edition ( 2009 )

[18] R. Hansch , O. Hellwich , Classification of polsar images by stacked random forests . ISPRS International Journal of Geo-Information p. 74 ( 2018 )

[19] K. Khadiev , I. Mannapov , L. Safina, The quantum version of classification decision tree constructing algorithm c5. 0 . //arXiv preprint arXiv: 1907 . 06840 ( 2019 )

[20] Kohavi , R. , J. Quinlan , Data mining tasks and methods: Classification: decision tree discovery, Handbook of data mining and knowledge discovery . Oxford University Press ( 2002 )

[21] D. Kopczyk, Quantum machine learning for data scientists . arXiv preprint arXiv: 1804 . 10068 ( 2018 )

[22] S. Lu , S. Braunstein , Quantum decision tree classifier . Quantum Inf Process 13 , pp. 757 - 770 ( 2014 )

[23] J. Quinlan , Induction of decision trees ( 1986 )

[24] J. Quinlan , Improved use of continuous attributes in c4.5 . Journal of Artificial Intelligence Research , pp. 77 - 90 ( 1996 )

[25] M. Schuld , F. Petruccione , Quantum ensembles of quantum classifiers . Sci Rep 8 ( 2018 )

[26] D. Windridge , R. Nagarajan , Quantum bootstrap aggregation . Quantum Interaction. QI 2016. Lecture Notes in Computer Science , vol 10106 . Springer, Cham ( 2017 )

[27] D. Wolpert , Stacked generalization . Neural Networks , pp. 241 - 259 ( 1992 )