# Forgetful Forests: Data Structures for Machine Learning on Streaming Data under Concept Drift
## Appendix A Algorithms for Forgetful Decision Trees  
The forgetful decision tree main routine (Figure 11) is called on the initial data and each time a new batch (an incremental batch) of data is received. The routine will make predictions with the tree before the batch and then update the batch. To avoid measuring accuracy during cold start, accuracy results are recorded only after the accuracy flattens out (i.e., when the accuracy changes 10% or less between the last 500 data items and the previous 500 data items). \(BuildSubTree(\cdot)\) and \(UpdateSubTree(\cdot)\) are called by the main routine. The \(BuildSubTree(\cdot)\) (not shown) is essentially the original CART build algorithm, and the \(UpdateSubTree(\cdot)\) is designed as follows:  
* The stopping criteria \(E(\cdot)\) may combine one or more factors, such as maximum tree height, minimum samples to split, and minimum impurity decrease. If the criteria holds, then the node will not further split. In addition, if all data points in the node have the same label, that node will not be split further. \(maxHeight\) controls \(E(\cdot)\) and is computed in \(AdaptParameters(. )\) below. * The evaluation function \(G(\cdot)\) evaluates the splitting score for each feature and each splitting value. It will typically be a Gini Impurity [17] score or an entropy reduction coefficient. As we discuss below, the functions \(minG\) and \(minGInc\) find split points that minimize the weighted sum of scores of each subset of the data after splitting. Thus, the score must be evaluated on many split points (e.g., if the input attributeis \(age\), then possible splitting criteria could be \(age>30\), \(age>32\),... ) to find the optimal splitting values. * \(rSize\) determines the size of \(X_{n}^{retained}\cup X_{n}^{i}\) and \(Y_{n}^{retained}\cup Y_{n}^{i}\) to be retained when new data for \(X\) and \(Y\) arrives. For example, suppose \(rSize=100\). Then \(|\,|X_{n}^{i}\,|\,|+|\,|X_{n}^{retained}\,|\,|-100\) of the oldest of \(X_{n}^{retained}\) and \(Y_{n}^{retained}\) (the data present before the incoming batch) will be discarded. The algorithm then appends \(X_{n}^{i}\) and \(Y_{n}^{i}\) to what remains of \(X_{n}^{retained}\) and \(Y_{n}^{retained}\). All nodes in the subtrees will discard the same data items as the root node. In this way, the tree is trained with only the newest \(rSize\) of data in the tree. Discarding old data helps to overcome concept drift, because the newer data better reflects the mapping from \(X\) to \(Y\) after concept drift. \(rSize\) should never be less than \(|\,|X_{n}^{i}\,|\,|\), to avoid forgetting any new incoming data. As mentioned above, upon initialization, new data will be continually added to the structure without forgetting until accuracy flattens out, which is controlled by \(coldStartup\). \(rSize\) and \(coldStartup\) are computed in \(AdaptParameters(. )\) below. ```
Input : \(n\), the node to be updated \(X_{n}^{i}\), \(Y_{n}^{i}\), incoming batch of training data for node \(n\) Globals: \(X_{n}^{retained},Y_{n}^{retained}\), the data retained in previous update for node \(n\) \(gRecord_{n}\), the sorted data retained in previous update for node \(n\)\(spillingValues_{n}\), the splitting values for splitting retained data in previous update for node \(n\)\(class_{n}\), the prediction label for node \(n\)\(children_{n}\), the child nodes of node \(n\)\(rSize\), the size of data retained \(G(. )\), the function to score the fitness of a feature for splitting \(E(. )\), the stopping criteria
1 begin
2 Discard oldest rows in \(X_{n}^{retained},Y_{n}^{retained}\) until \(\|X_{n}^{retained}\cup X_{n}^{i}\|-\|Y_{n}^{retained}\cup Y_{n}^{i}\|-rSize\). \((X_{n}^{retained},Y_{n}^{retained})\leftarrow(X_{n}^{retained}\cup X_{n}^{i},Y_{n }^{retained}\cup Y_{n}^{i})\);
3 if\(E(n)\) is True then
4// don't split subtree more \(class_{n}\leftarrow\) the class having the highest probability;
5 else
6\(newSpillingValues,gRecord_{n}\gets minGIInc(X_{n}^{i},Y_{n}^{i},G(.