The Tree Autoencoder Model, with Application to Hierarchical Data Visualization

W e propose a new model for dimensionality reduction, the PCA tree, which works like a regular autoencoder, having explicit projection and reconstruction mappings. The projection is effected by a sparse oblique tree, having h ard, hyperplane splits using few features and linear leaves. The reconstruction ma pping is a set of local linear mappings. Thus, rather than producing a global ma p as in t-SNE and other methods, which often leads to distortions, it produce s a hierarchical set of local PCAs. The use of a sparse oblique tree and of PCA in its le aves makes the overall model interpretable and very fast to project or r econstruct new points. Joint optimization of all the parameters in the tree is a nonc onvex nondifferen-tiable problem. W e propose an algorithm that is guaranteed t o decrease the error monotonically and which scales to large datasets without an y approximation. In experiments, we show PCA trees are able to identify a wealth o f low-dimensional and cluster structure in image and document datasets.