Random Forest (RF) is a popular tree-ensemble method for supervised learning,
prized for its ease of use and flexibility. Online RF models require to account
for new training data to maintain model accuracy. This is particularly
important in applications were data is periodically and sequentially generated
over time in data streams, such as auto-driving systems, and credit card
payments. In this setting, performing periodic model retraining with the old
and new data accumulated is beneficial as it fully captures possible drifts in
the data distribution over time. However, this is unpractical with
state-of-the-art classical algorithms for RF as they scale linearly with the
accumulated number of samples. We propose QC-Forest, a classical-quantum
algorithm designed to time-efficiently retrain RF models in the streaming
setting for multi-class classification and regression, achieving a runtime
poly-logarithmic in the total number of accumulated samples. QC-Forest
leverages Des-q, a quantum algorithm for single tree construction and
retraining proposed by Kumar et al. by expanding to multi-class classification,
as the original proposal was limited to binary classes, and introducing an
exact classical method to replace an underlying quantum subroutine incurring a
finite error, while maintaining the same poly-logarithmic dependence. Finally,
we showcase that QC-Forest achieves competitive accuracy in comparison to
state-of-the-art RF methods on widely used benchmark datasets with up to 80,000
samples, while significantly speeding up the model retrain.

QC-Forest 是一种经典 - 量子算法，用于在流式设置中高效地重新训练随机森林模型，实现多类分类和回归，其运行时间与累积样本总数的对数成倍数关系。