Abstract
This paper extends the PRISM statistical logic language to support generative models that can "fail" during execution. By introducing a three-valued semantics and a method to compile negation into failure programs, the authors enable the modeling of complex constraints and log-linear distributions. Evaluation on synthetic datasets, including a constrained Hidden Markov Model, demonstrates the framework's ability to accurately recover parameters from successful observations.
Introduction
Traditional generative modeling, such as standard Hidden Markov Models (HMMs) or Probabilistic Context-Free Grammars (PCFGs), typically assumes a "failure-free" process where every probabilistic choice leads to a valid observable outcome. In such models, the sum of all outcome probabilities is exactly one. However, real-world phenomena often involve logical constraints. For instance, in natural language processing, a sentence generated by a grammar might be rejected if it violates specific agreement rules.
In logic programming, this rejection is termed "failure." Standard PRISM struggled with failure-prone models because they result in log-linear distributions where probabilities of observable events do not sum to unity. Furthermore, handling negation in a probabilistic context is mathematically complex. This work provides a mathematical foundation and a practical learning algorithm for these failure-prone models.
Methodology
The authors introduce three technical components to bridge the gap between logic and failure-based statistics:
- Three-valued Distribution Semantics: Moving from standard two-valued logic (True/False) to a three-valued logic (True, False, Undefined) allows the system to handle programs with infinite loops or complex negation without breaking the underlying probability measure.
- First-Order Compiler (FOC): To perform Expectation-Maximization (EM) learning, the system needs to know exactly how a program fails. The FOC automatically transforms programs with negation into definite clause programs that describe failure conditions, removing the need for manual failure program specification.
- fgEM Algorithm: An "amalgamated" EM algorithm (fgEM) combines PRISM's standard graphical EM with the Failure-based Assignment of Meaning (FAM) algorithm. This enables parameter estimation even when probability mass is lost to failure.
Experimental Setup
The approach was evaluated using several simulated scenarios, most notably the Dieting Professor (a constrained HMM). In this scenario, a professor chooses lunch spots according to an HMM, but a "failure" occurs if their total weekly calorie intake exceeds a threshold (e.g., 4000 calories). The objective is to recover the professor's original preferences using only records of "successful" weeks.
Other experiments included basic Bernoulli trials and a Tic-tac-toe model where winning is defined through negative goals (i.e., the opponent cannot find a winning move).
Key Results
The framework successfully demonstrated that failure can be used as a powerful modeling tool. By allowing failure, researchers can write simple generative processes and filter them with logical constraints, which is often more intuitive than designing complex failure-free processes.
In the Dieting Professor experiment, the system estimated original probabilities with high precision. For example, an original transition probability of 0.7 was estimated as 0.697 from 500 samples, despite the calorie constraint filtering many potential paths.
Empirical verification confirmed that the sum of the probability of success and the probability of failure equals exactly 1.0, validating the three-valued semantics. Additionally, the Tic-tac-toe example showed that the system could learn strategies through "negative goals," a capability previously missing in the failure-free PRISM framework.
Discussion and Future Work
While the framework provides a robust way to handle failure, calculating the normalizing constant ($Z$) for log-linear models can become computationally expensive for very large-scale models. The current implementation also assumes programs are "terminating." Future work aims to apply this framework to complex linguistic theories like Head-driven Phrase Structure Grammar (HPSG), which rely heavily on the types of constraints enabled by this research.
Summary updated