A Machine Learning Framework for Volume Prediction

Abstract

Computing the exact volume of a polytope is a #P-hard problem, which makes the computation for high dimensional polytopes computationally expensive. Due to this cost of computation, randomized approximation algorithms is an acceptable solution in practical applications. On the other hand, machine learning techniques, such as neural networks, saw a lot of success in recent years. We propose machine learning approaches to volume prediction and volume comparison. We employ various network architectures such as feed-forward networks, autoencoders and end-to-end networks. We develop different types of models with these architectures that emphasize different parts of the problem, such as representation of polytopes, volume comparison between polytopes and volume prediction. Our results have varying rate of success depending on model and experimentation parameters. This work intends to start the discussion about applying machine learning techniques to computationally hard geometric problems.