In this talk, we present our recent theoretical and practical results.

(i) An autoencoder is a layered neural network consisting of an encoder and a decoder, where the former transforms an input vector to a low-dimensional vector and the latter transforms the low-dimensional vector to an output vector, which should be the same as or similar to the input. We study the compressive power of autoencoders with linear threshold activation functions. In particular, we analyze the relations between the architecture (e.g., the numbers of nodes and layers) of networks and their compression ratios (arXiv:2112.10933).

(ii) We focus on the prediction phase of a random forest and study the problem of representing a bag of decision trees using a smaller bag of decision trees, where we focus on binary decision problems on the binary domain. We show that in some cases, an exponential number of nodes are required to express a given random forest by a random forest with a much fewer number of trees, whereas a polynomial number of nodes are enough if some errors are allowed and the difference of the number of trees is bounded by a constant (arXiv:2312.11540).

(iii) We have been studying discrete pre-image problem, which is to infer the original structural data from their feature vectors. In particular, we have been developing integer linear programming-based methods to infer chemical graphs from their features. Although this problem is theoretically intractable (NP-hard) in general, we show that by appropriately giving constraints, it is possible to infer moderate size chemical graphs from their features (arXiv:2108.10266).