Modelling the Outlier Detection Problem in QASP
summary
The paper models outlier detection as a second-level PH problem using Quantified Answer Set Programming, encoding the two witness conditions as an exists/for-all pair of ASP programs. It implements a solver via rewriting to QPF and executes encodings like ordinary ASP, then benchmarks on synthetic network data and reports scalability gains of about three orders of magnitude over the 2007 Angiulli et al. ASP saturation encoding. The implementation is available and the QASP encoding runs markedly faster and is much more compact.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 0:42Presentation
- 3:42Modeling Beyond NP
- 9:34Outlier Definition
- 10:15Example
- 13:15Encoding
- 16:08Results
- 16:57Conclusion
- 17:50Questions
- 19:35Applications
- 21:45Further Questions
related talks
24mAnswer Set Programming for Egg Extraction and More
20mFunction synthesis for maximizing model counting
20mStatic Posterior Inference of Bayesian Probabilistic Programming via Polynomial Solving
44mAutomated Scientific Discovery Using Insights from Problem Structure
14mGeneralizable Synthesis Through Unification
17mAlgebro-geometric Algorithms for Template-Based Synthesis of Polynomial Program...
15mOn Abstraction Refinement for Bayesian Program Analysis
17mTowards Practical Algorithms for Outlier-Robust Estimation