AND/OR abstraction sampling
Algorithms AIMech:ANDORAbstractionSampling DRAFT
Aliases: Unrestricted AND/OR abstraction sampling
An importance-sampling algorithm for partition functions of discrete graphical models that samples representatives in a pseudo-tree-guided AND/OR search space, allowing abstractions across branching-ancestor contexts through interleaved ancestor pruning and relative-weight value backup.
Identity Notes & Concept Scope
Compared all 442 pinned AIO and 647 native IDs, names, aliases and scoped synonyms; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 5, 1, 1 lines. All candidate-relevant passages and the windows around ambiguous acronym hits were inspected; the older-checkout AOAS hits are statistics-journal URLs, not algorithm identities. Semantic matching covered 56 AIO and 316 native definitions, with every matched definition read. 12 full annotated AIO node/edge/generated contexts and 5 full native records were inspected. Retain the 2020 AOAS algorithm, which permits abstractions across different closest branching-ancestor assignments by interleaving variable-level sampling with pruning and relative-weight backup. The 2018 proper AND/OR variant restricts those merges; it is not an alias for this method. Chen GS and HS estimate additive functionals of ordinary trees; this algorithm operates on a decomposed graphical-model AND/OR space with products over independent sibling subproblems. Knuth follows single paths, Gibbs constructs conditional Markov transitions, and MRF denotes a model family. Bare AOAS is not an alias because the acronym also denotes a statistics journal.
Claims & Grounded Evidence
5 Claims
Mechanism
#sibling-aware-proposal
Traverse pseudo-tree variables depth first and expand the current AND-node frontier to the next variable. Partition its generated nodes into abstract states and retain one representative per state. In the stated heuristic proposal, its probability is proportional to w*g*h*r: inherited importance weight, accumulated path cost, a heuristic for the remaining subtree, and estimates of off-path sibling subproblem values. Update the selected weight to w/p using its actual selection probability; initialize its backed-up subtree value to one.
Mechanism
#pruning-and-relative-backup
After completing a child-variable subtree, remove ancestor assignments without retained descendants in that subtree before processing later siblings. For each surviving parent AND node, multiply its accumulated value by the sum over retained child AND nodes of child value times arc cost times child weight divided by parent weight. The relative weights avoid repeatedly applying the same inherited ancestral sampling correction. This traversal maintains complete solution subtrees even when an abstract state crosses the closest branching-ancestor contexts that the earlier proper variant kept separate.
Scope
#finite-supported-expectation
The source states unbiased partition-function estimation for AOAS and sketches a correspondence to equivalent OR abstraction-sampling traces. Curated scope is a finite discrete model with nonnegative finite factors, valid pseudo-tree decomposition and actual proposal support for all potentially positive contributions, together with the stated inverse-probability updates and pruning. Correspondence to an equivalent OR construction does not mean that the same fixed abstraction on a depth-first OR tree generates the same probes. Unbiasedness does not provide a finite-run error guarantee.
Scope
#probe-size-and-cutsets
With n variables and at most m abstract states per variable, the source bounds retained AOAS probe size by O(n*m). This is a retained-node bound, not a bound on all generated children, heuristic preprocessing or runtime. AND/OR factorization can compactly represent multiple complete configurations within one probe. The cutset option stops below a node only when its heuristic is known to equal the exact subtree value; a stronger approximate bound alone does not establish that condition.
Limitation
#reported-evaluation-scope
The reported comparison uses five benchmark families, over 480 graphical-model problems, weighted mini-bucket heuristics with i-bound 10, and runs up to one hour. For problems without exact partition functions, error uses an empirical reference obtained from repeated long abstraction-sampling runs. Outcomes depend on family, abstraction and parameters; solved-instance counts also differ between settings. The tables and selected convergence curves do not establish a universal accuracy or runtime advantage over proper AND/OR sampling, OR sampling or dynamic importance sampling.
⚠️ Curated Limitations & Negative Results
- This record denotes the 2020 AOAS procedure, not every algorithm that samples an AND/OR tree. The separately described 2018 proper variant and the later 2024 abstraction-function catalog are not asserted aliases.
- Zero proposal mass must not discard a positive contribution. All-zero states, division by zero and termination at the dummy root require implementation conventions. Algorithm 1’s terminal pop/top sequence is not certified as literal executable pseudocode; the prose specifies return of the backed-up dummy-root value.
- In a constructed three-variable model the exact partition is 2478. Approximate sibling bounds give mean 2478 and variance 54432; exact sibling values give variance 0 in that example. These are finite checks, not a general proof or an available exact heuristic for hard instances.
- With inherited parent weight 2 and child weights 4 on two sibling branches, relative backup gives the correct unit-model partition 8; applying both absolute child weights gives 32. A different naive unrestricted scheme has invalid probes with probability 1/2 yet is unbiased in the constructed case. Invalidity is therefore not claimed to prove bias in every possible variant.
- The proceedings proof is a sketch and the inspected supplement supplies additional traces and results. No full general proof certification, author-code execution, confidence guarantee or benchmark replication is claimed. A separate partial reading of later author code informs the discovery ledger, not an asserted implementation identity for the 2020 paper.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:ProbabilisticGraphicalModel
Probabilistic Graphical Model
|
related_match | The algorithm estimates the partition function of a factorized discrete graphical model and uses that model’s conditional-independence structure. The pinned AIO target denotes graphical-model terminology and is exported as a machine-learning task. This is an algorithm-to-model/task related match, not equivalence or an is-a assertion. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
kask2020aoas
|
Kalev Kask, Bobak Pezeshki, Filjor Broka, Alexander Ihler, Rina Dechter
|
primary paper
full_text
|
ID: doi:10.24963/ijcai.2020/589
sha256:5ad89392088b…
|
kask2020supplement
|
Kalev Kask, Bobak Pezeshki, Filjor Broka, Alexander Ihler, Rina Dechter
|
primary paper
full_text
|
sha256:4ebfc3007315…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-13T20:08:22Z
Updated: 2026-10-13T20:10:58Z
Source File:
data/curated/ANDORAbstractionSampling.yaml