The code in this repo is for the paper: "Learning to sample fibers for goodness-of-fit testing". (https://arxiv.org/abs/2405.13950)
We consider the problem of constructing exact goodness-of-fit tests for discrete exponential family models. This classical problem remains practically unsolved for many types of structured or sparse data, as it rests on a computationally difficult core task: to produce a reliable sample from lattice points in a high-dimensional polytope. We translate the problem into a Markov decision process and demonstrate a reinforcement learning approach for learning `good moves' for sampling. We illustrate the approach on data sets and models for which traditional MCMC samplers converge too slowly due to problem size, sparsity structure, and the requirement to use prohibitive non-linear algebra computations in the process. The differentiating factor is the use of scalable tools from \emph{linear} algebra in the context of theoretical guarantees provided by \emph{non-linear} algebra. Our algorithm is based on an actor-critic sampling scheme, with provable convergence. The discovered moves can be used to efficiently obtain an exchangeable sample, significantly cutting computational times with regards to statistical testing.
One of the examples we consider is the coauthorship dataset. This dataset is given in the form a graph where each node is an author and there exists an edge between two nodes if the two corresponding authors worked on a paper together. We are interested in verifying whether the data follows the beta model.
GaussianAC/
├── DeepFiberSamplingGaussianENV.py# RL environment
├── Gaussian A2C Fiber Sampling.ipynb # Main notebook from where to run the code.
├── GaussianA2C.py # Model code, model initialization and training.
├── helper_functions.py # Helper functions for the data preparation.
├── reward_functions.py # Different reward functions.
├── stats_functions.py # Functions for processing the design matrix and moves.
├── stats_problems.py # Different statistical problems and fibers.
└── README.md
- Clone the whole repository.
git clone <repo http>
- Run the notebook:
Gaussian A2C Fiber Sampling notebook.ipynb
- In this notebook you can define sampling for 4 different problems. For custome problems, you need to define the design matrix
$A$ , initial solution$x_0$ and margin$Ax = b$ . Then extract the lattice basis. - After computing the lattice basis, simply run the trainig cell and the RL will start training.
- In the end of the notebook, you can load the trained policy, rerun it on the same fiber and compute the random sample from the fiber.
- Finally, the code computes the emprical chi-square distribution for the given sample.