Error-Correcting and Verifiable Parallel Inference in Graphical Models
Authors: Negin Karimi, Petteri Kaski, Mikko Koivisto10194-10201
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present a novel framework for parallel exact inference in graphical models. Our framework supports error-correction during inference and enables fast verification that the result of inference is correct, with probabilistic soundness. The computational complexity of inference essentially matches the cost of w-cutset conditioning, a known generalization of Pearl s classical loop-cutset conditioning for inference. Verifying the result for correctness can be done with as little as essentially the square root of the cost of inference. Our main technical contribution amounts to designing a low-degree polynomial extension of the cutset approach, and then reducing to a univariate polynomial employing techniques recently developed for noninteractive probabilistic proof systems. |
| Researcher Affiliation | Academia | Negin Karimi Department of Computer Science Aalto University negin.karimi@aalto.fi Petteri Kaski Department of Computer Science Aalto University petteri.kaski@aalto.fi Mikko Koivisto Department of Computer Science University of Helsinki mikko.koivisto@helsinki.fi |
| Pseudocode | No | The paper describes algorithms and transformations in prose and mathematical notation but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access to source code, such as a repository link or an explicit statement of code release. |
| Open Datasets | No | The paper describes a theoretical framework for inference in graphical models and does not conduct empirical studies on specific datasets that are made publicly available. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical studies that would involve training, validation, or test dataset splits. |
| Hardware Specification | No | While the paper discusses the advantages for massively parallel execution and mentions hardware reliability in a related work context, it does not specify any particular hardware used for its own research or theoretical claims. It is a theoretical paper. |
| Software Dependencies | No | The paper refers to general mathematical toolboxes (e.g., "standard fast algorithmic toolbox for computing with univariate polynomials") and arithmetic methods (e.g., "modular arithmetic using, for example, Montgomery multiplication") but does not list specific software dependencies with version numbers required for reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or system-level training settings. |