Learning Abductive Reasoning Using Random Examples
Authors: Brendan Juba
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We specifically consider the question of which syntactic classes of formulas have efficient algorithms for abduction. We find that the class of k-DNF explanations can be found in polynomial time for any fixed k; but, we also find evidence that even weak versions of our abduction task are intractable for the usual class of conjunctions. This evidence is provided by a connection to the usual, inductive PAC-learning model proposed by Valiant. |
| Researcher Affiliation | Academia | Brendan Juba Washington University in St. Louis bjuba@wustl.edu Work partially performed while the author was affiliated with Harvard University and supported by ONR grant number N000141210358. |
| Pseudocode | Yes | Algorithm 1: Elimination algorithm |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not describe empirical experiments with real datasets, therefore no training dataset access information is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments, thus no training/test/validation splits are mentioned. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments, thus no software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, thus no specific experimental setup details or hyperparameters are mentioned. |