You might recall the "Deep Forest" paper published earlier this year by Professor Zhihua Zhou and his student Ji Feng of Nanjing University's LAMDA program. They argued that decision tree ensemble methods could also be used to build deep learning models and proposed the Deep Forest gcForst, exploring deep models beyond neural networks. Now, building on Deep Forest, they have proposed eForest, an autoencoder based on decision tree ensemble methods. Experimental results show that eForest outperforms DNN-based autoencoders in both speed and accuracy.
Autoencoding is an important task, typically implemented by deep neural networks (DNNs) such as convolutional neural networks (CNNs). In this paper, we propose EncoderForest (eForest), the first tree-ensemble-based autoencoder . We present a method that allows forests to utilize equivalent classes defined by the decision paths of trees for backward reconstruction, and demonstrate its use in both supervised and unsupervised environments. Experimental results show that, compared to DNN autoencoders, eForest achieves lower reconstruction errors with faster training speeds, while also exhibiting reusability and loss tolerance.
If the above passage seems familiar, for example, the keywords "tree-based", "eForest", and the statement "compared to DNN, tree-based methods are more...", then you're not mistaken, Professor Zhou Zhihua of Nanjing University's LAMDA and his student Feng Ji have struck again.
Earlier this year, their paper, "Deep Forest: Exploring Approaches Beyond Deep Neural Networks," generated considerable buzz in the industry. In that paper, Zhou Zhihua and Feng Ji proposed a tree-based method, gcForest—a "multi-Grained Cascadeforest"—that uses a novel decision tree ensemble approach with a cascaded structure to enable representation learning. In experiments, gcForest achieved excellent performance across different domains using the same parameter settings, performing well on both large and small datasets. Furthermore, due to its tree-based structure, gcForest is easier to analyze compared to neural networks.
In the gcForest paper, the authors wrote: "We believe that to solve complex problems, learning models also need to go deeper. However, current deep models are all neural networks. This paper demonstrates how to build deep forests, opening a door to using methods other than deep neural networks for many tasks."
Now, building on gcForest, they are continuing to explore methods beyond DNNs, this time targeting autoencoders .
Continuing to explore methods beyond neural networks, this time targeting autoencoders.
In their latest paper, " AutoEncoderbyForest ," Zhou Zhihua and Feng Ji proposed EncoderForest, also known as "eForest," which integrates a decision tree to perform forward and backward encoding operations in both supervised and unsupervised environments. Experimental results show that the eForest method has the following advantages:
Accuracy: Experimental reconstruction error is lower than that of autoencoders based on MLP or CNN.
High efficiency: Training eForest on a single KNL (multi-core CPU) is faster than training a CNN autoencoder on a Titan-X GPU.
Loss tolerance: A well-trained model can still function well even when partially damaged.
Reusable: A model trained on one dataset can be directly applied to another dataset in the same domain.
Below is a translated introduction to the latest paper. To view the complete paper, please see the link at the end of the article.
eForest, the first tree ensemble-based autoencoder model
This time, we'll start with the conclusions, then revisit the proposal and experimental results of the eForest model. In the conclusion section, the authors write,
In this paper, we propose the first tree ensemble-based autoencoder model, EncoderForest (eForest). We devise an efficient method that enables forests to reconstruct original patterns using the maximum compatibility rule (MCR) defined by the decision paths of the trees. Experiments demonstrate that eForest performs well in terms of accuracy and speed, and exhibits loss tolerance and model reusability. Particularly with text data, the model is able to reconstruct the original data with high accuracy using only 10% of the input bits.
Another advantage of eForest is that it can be used directly with data of symbolic or mixed attributes without converting symbolic attributes to numeric attributes. This is especially important when information is often lost or additional biases are introduced during the conversion process.
It's important to note that supervised and unsupervised eForests are actually two components used simultaneously at each level of a deep forest built from multi-granularity cascaded forests like gcForst. Therefore, this work may also deepen our understanding of gcForst. Constructing deep eForest models is also an interesting problem worthy of future research.
Method Proposed: A potentially simplest forest backward reconstruction strategy
Autoencoders have two basic functions: encoding and decoding. Encoding is easy for forests because leaf node information alone can be considered an encoding method, while subsets of nodes or even branch paths can provide more information for encoding.
Encoding process
First, we propose the encoding process of EncoderForest. Given a trained tree ensemble model containing T trees, the forward encoding process receives input data and sends it to each root node of the trees in the ensemble. After the data has traversed all the leaf nodes of the trees, the process returns a T-dimensional vector, where each element t is an integer index of a leaf node in tree t.
Algorithm 1 presents a more specific forward encoding algorithm. Note that this encoding process is independent of the specific learning rule for how to split the tree nodes. For example, decision rules can be learned in a supervised environment of a random forest, or in an unsupervised environment (such as a fully random tree).
Decoding process
The decoding process is less obvious. In fact, forests are typically used for forward prediction from each tree root to the leaves, but how to perform backward reconstruction, that is, to deduce the original sample from the information obtained from the leaves, is not clear.
Here, we propose an effective and simple (and likely the simplest) strategy for backward reconstruction of forests. First, each leaf node actually corresponds to a path from the root, and we can determine this path based on the leaf nodes, such as the path highlighted in red in the figure below.
Secondly, each path corresponds to a symbol rule. The highlighted paths in the above diagram can correspond to the following rule set, where RULEi corresponds to the path of the i-th tree in the forest, and the symbol ":" represents a negative judgment:
Then, we can derive the Maximum Compatibility Rule (MCR). From the rule set above, we can obtain the following MCR:
Each component of this MCR must not have an excessively large coverage area, otherwise it will conflict with other conditions. Therefore, the original sample must not exceed the input region defined by the MCR. Algorithm2 provides a more detailed description of this rule.
After obtaining the MCR, the original samples can be reconstructed. Specifically, given a trained forest with T trees and specific data with forward encoding, backward decoding first locates individual leaf nodes for each element in the MCR, and then obtains the corresponding T decision rules based on the corresponding decision paths. By calculating the MCR, we can return the MCR to the input region. Algorithm 3 provides the specific algorithm.
eForest can perform self-encoding tasks through forward and backward encoding operations.
Furthermore, the eForest model may provide some theoretical insights into the representation learning capabilities of decision tree ensemble models, which could help in designing new deep forest models.
Experimental results
The authors evaluated the performance of eForest under supervised and unsupervised conditions. Here, the subscripts 500 and 1000 represent forests with 500 and 1000 trees, respectively, and the superscripts s and u represent supervised and unsupervised conditions, respectively. eForestN represents the input instances as N-dimensional vectors.
Compared to DNN-based autoencoders, eForest performs better in image reconstruction, computational efficiency, model reusability, and loss tolerance experiments. Furthermore, unsupervised eForest sometimes outperforms supervised eForest. Additionally, eForest can be used for text-based data.
Image Reconstruction
Text Reconstruction
Since CNN- and MLP-based autoencoders cannot be used for text-type data, only the performance of eForest is compared here. It is also shown that eForest can be used for text data.
computational efficiency
Tolerance
Model is reusable
Paper link: https://arxiv.org/pdf/1709.09018.pdf
