3.3 Logic and Uncertainty 3.3.1 Natural Language to Logic: Formalization and Solving

3.3 Logic and Uncertainty 3.3.1 Natural Language to Logic: Formalization and Solving

Mingming Sun
BIMSA

Logic-LM: The Vehicle Ordering Example

Paper example, Figure 2: order three vehicles by age.

Natural-language problem

A tractor, a convertible and a minivan have distinct age ranks.

The tractor ranks second-newest.
The minivan is newer than the convertible.

Question: Which vehicle is oldest?

Symbolic problem

\begin{aligned}&t,c,m\in\{1,2,3\}\\[-0.08em]&1=\text{oldest};\quad3=\text{newest}\\[-0.08em]&t=2\\[-0.08em]&m>c\\[-0.08em]&\operatorname{AllDifferent}(t,c,m)\end{aligned}

Core idea: the LLM specifies variables and constraints.
A symbolic solver searches for assignments satisfying them.

Logic-LM: Formulation and Symbolic Solving

Logic-LM Figure 2: task formulations, symbolic reasoners and result interpretation
Original Figure 2. Click to enlarge.

1. Problem formulator

The LLM uses in-context examples to generate task-specific symbols and constraints.

2. Symbolic reasoner

The CSP solver (python-constraint) returns
c=1,\quad t=2,\quad m=3.

3. Result interpreter

Map rank 1 back to the answer:
the convertible is oldest.

Logic-LM: Refinement from Solver Feedback

Step Information passed to the next component
Execute Send the generated formalization to its solver
On execution error Return the faulty form, the error message and repair demonstrations to the LLM
Revise and retry Generate a revised formalization and run the solver again
Stop No execution error, or the revision limit is reached

Paper example of an error class: an FOL variable has no binding quantifier.

Self-refinement repairs generated text at inference time.
Successful execution still requires a separate check of semantic fidelity.

Logic-LM: Results and the Remaining Bottleneck

GPT-4 accuracy (%) · original Table 2 · no self-refinement

Dataset CoT Logic-LM Δ pp
PrOntoQA 98.79 83.20 −15.59
ProofWriter 68.11 79.66 +11.55
FOLIO 70.58 78.92 +8.34
LogicalDeduction 75.25 87.63 +12.38
AR-LSAT 35.06 43.04 +7.98
Logic-LM paper Table 2, all three models and five datasets
Original Table 2 · click to enlarge.

Protocol: same in-context examples; temperature 0. Non-executable cases fall back to CoT.

Finding: solver assistance helps many tasks, but can lose when formalization fails.

Separate refinement analysis (Table 3): GPT-4 FOLIO executable rate 79.9% → 85.8%; accuracy among executable cases 80.4% → 79.9%. These are different metrics.

LINC: Semantic Parsing and Deduction

Paper example, Figures 1–2

Every rectangle has four sides.
Anything with four sides is a shape.

Query: Must every rectangle be a shape?

LLM role: translate both premises and the query into first-order logic.

Prover9 input, readable notation

\forall x:\operatorname{Rectangle}(x)\to\operatorname{FourSides}(x)
\forall x:\operatorname{FourSides}(x)\to\operatorname{Shape}(x)

Query:

\forall x:\operatorname{Rectangle}(x)\to\operatorname{Shape}(x)

Prover9 result: True.
The premises entail the query.

CoT asks the LLM to produce the deduction.
LINC assigns semantic parsing to the LLM and deduction to Prover9.

LINC: Multiple Parses and Solver Votes

LINC Figure 1: correct and faulty rectangle parses, Prover9 labels and majority voting
Original Figure 1. Click to enlarge.

Four illustrated branches

Correct parse: True

Extra parenthesis: Error

Consistent renaming: True

Mismatched predicates: Unknown

Run Prover9 on each parse, then vote over valid labels.
Experiments use K=10. Shared translation errors can survive voting.

LINC: Strong Gains, with a Dataset Boundary

LINC Figure 3: all models, FOLIO and ProofWriter; bootstrapped 10-way majority voting
Original Figure 3 · all conditions use 10-way voting · click to enlarge.

GPT-4 / ProofWriter:
CoT 72.2% → LINC 98.3% (+26.1 pp)

GPT-4 / FOLIO:
CoT 75.3% → LINC 72.5% (−2.8 pp)

FOLIO: 182 retained validation examples; ProofWriter: 360 balanced OWA examples. FOLIO difference is not significant (paper: p=0.58). Different subsets and voting protocols prevent direct comparison with Logic-LM’s table.

What Symbolic Solvers Establish

Question Support supplied by these methods Remaining requirement
What does the text mean? Explicit formulas expose variables, conditions and scope Check the translation against the source
Does the conclusion follow? A solver checks the formal problem Valid syntax, consistent premises and sufficient resources
Are the premises reliable? The derivation is conditional on the supplied premises Evidence about the underlying facts

Logic-LM and LINC address formalization and deduction.
Noisy observations and rules with exceptions require an uncertainty model.

3.3 Logic and Uncertainty 3.3.2 Uncertain Evidence and Soft Rules



原 PPT 独立图片资源

3.3 Logic and Uncertainty 3.3.2 Uncertain Evidence and Soft Rules

原 PPT 独立图片资源

Errors, Conflicts and Missing Evidence


原 PPT 独立图片资源
Errors, Conflicts and Missing Evidence
Reasoning systems combine facts and rules from documents, observations, and model predictions.
These inputs can contain errors, conflicts, and missing evidence.
We must assess evidence, reconcile constraints, and reason about unresolved facts.
Formal validity alone does not establish the reliability of the premises.

Logic and Probability: A Roadmap


原 PPT 独立图片资源
Logic and Probability: A Roadmap
We will connect logical structure with uncertainty in evidence and rules:
Statistical Relational Learning
Markov Networks, Markov Logic, and Probabilistic Soft Logic

Statistical Relational Learning



原 PPT 独立图片资源
Logic and Probability
Statistical Relational Learning
原 PPT 独立图片资源

Uncertainty in Evidence and Rules


原 PPT 独立图片资源
Uncertainty in Evidence and Rules
Evidence extraction and interpretation involve uncertainty:
Arises during entity, relation, and event extraction
Common in instance matching/entity linking steps
Machine learning algorithms produce probabilistic outputs
Thresholding is often used to convert to hard labels
Heuristic or validation-based threshold tuning

Preserving Uncertainty for Joint Inference


原 PPT 独立图片资源
Preserving Uncertainty for Joint Inference
Traditional practice: Discard uncertainty/Hard decision
New perspective: Leverage uncertainty as information
Example: Probabilistic extraction + ambiguous resolution ⇒ flag instance
Collective signals from multiple sources improve trust decisions
Cross-document or cross-task reinforcement

Cross-Algorithm and Cross-Task Challenges


原 PPT 独立图片资源
Cross-Algorithm and Cross-Task Challenges
Uncertainty varies across algorithms
Some algorithms struggle where others succeed
Cross-task interactions:
e.g., Extraction vs. Instance Matching
Ensemble learning handles intra-task variation well
SRL needed to reason across tasks and dependencies

Structured Reasoning with SRL


原 PPT 独立图片资源
Structured Reasoning with SRL
SRL offers a framework to handle:
Collective uncertainty
Domain expertise
Dependencies across evidence-processing stages
Helps integrate:
Domain-specific rules
Task-specific confidence levels
Output interdependencies

Dependencies Between Facts and Decisions


原 PPT 独立图片资源
Dependencies Between Facts and Decisions
Local models often predict facts and decisions independently.
Shared evidence and domain rules create dependencies between these predictions.
Statistical Relational Learning (SRL) models these dependencies by integrating logic and probability.
Joint inference combines local evidence with these structured dependencies.

Modeling Dependencies


原 PPT 独立图片资源
Modeling Dependencies
Relational dependencies are a key source of domain knowledge
Even simple ontologies (e.g., social networks) encode rich dependencies
Example relations: friendOf, spouseOf, votesFor
Domain rules derived from social science (e.g., spouses often vote alike)

From Intuition to Formal Rules


原 PPT 独立图片资源
From Intuition to Formal Rules
Informal rules can be:
Spouses usually vote for the same candidate
Friends sometimes vote similarly
These are not deterministic — violations are allowed
SRL frameworks formalize such probabilistic dependencies

Formalizing with Weighted First-Order Logic


原 PPT 独立图片资源
Formalizing with Weighted First-Order Logic
Rules are represented as weighted implications:
0.8: Spouse(A, B) ∧ VotesFor(A, P) → VotesFor(B, P)
0.1: Neighbors(A, B) ∧ VotesFor(A, P) → VotesFor(B, P)
0.4: Friends(A, B) ∧ VotesFor(A, P) → VotesFor(B, P)
Higher weight → stronger rule
Rules are soft constraints, not hard truths

Predicate Grounding and Domain Constraints


原 PPT 独立图片资源
Predicate Grounding and Domain Constraints
Variables (A, B, P) must be grounded to real-world entities
Predicate constraints:
𝑉𝑜𝑡𝑒𝑠𝐹𝑜𝑟(𝐴, 𝑃) → 𝐴 ∈ 𝑝𝑒𝑜𝑝𝑙𝑒, 𝑃 ∈ 𝑝𝑜𝑙𝑖𝑡𝑖𝑐𝑎𝑙 𝑝𝑎𝑟𝑡𝑖𝑒𝑠
SRL supports expressing such structured domain knowledge robustly

Statistical Relational Learning Frameworks


原 PPT 独立图片资源
Statistical Relational Learning Frameworks
Modern domains involve both:
Relational structure (dependencies between entities)
Uncertainty (confidence levels vary across rules)
Statistical learning handles uncertainty
Relational learning models structure
SRL unifies both approaches into a powerful framework

What SRL Enables


原 PPT 独立图片资源
What SRL Enables
Core tasks supported by SRL:
Classification
Link prediction
Link-based clustering
Applications span social networks, recommender systems, knowledge graphs, etc.
SRL has become a feasible and promising research area due to advances in both statistical and relational learning

Key Requirements for an SRL Framework


原 PPT 独立图片资源
Key Requirements for an SRL Framework
A successful SRL framework should:
Combine first-order logic with probabilistic graphical models
Support standard SRL tasks (e.g., link prediction, classification)
Allow incorporation of domain knowledge
Enable reuse and extension of methods from:
Statistical learning
Probabilistic and logical inference
Inductive logic programming

Weighted Logic and Probability


原 PPT 独立图片资源
Weighted Logic and Probability

Markov Logic unifies probabilistic graphical models and first-order logic.
It is the Fundamental Model for SRL
It was proposed to meet a set of desiderata for probabilistic knowledge representation.
Before diving into MLNs, we first examine Markov Networks (also called Markov Random Fields).

3.3 Logic and Uncertainty 3.3.3 Markov Random Fields: Joint Distributions and Inference

Markov Random Fields


原 PPT 独立图片资源

Markov Random Fields


A Markov Network (also called a Markov Random Field, MRF) is an undirected graphical model.
It models the joint probability distribution of a set of random variables 𝑋 = (𝑋1, …, 𝑋𝑛)∈𝒳 using a graph structure to encode their dependencies.
Key features:
Nodes represent variables
Edges represent direct probabilistic dependencies
Cliques define local compatibility functions

Conditional Independence in Markov Networks


原 PPT 独立图片资源
Conditional Independence in Markov Networks

In an undirected graphical model, we aim to express the following form of conditional independence:
Each variable is only directly dependent on its neighbors; any influence from other variables is mediated through these neighbors.
To capture this locality, we need to define local structures in the graph that encode “energy” or “compatibility.”
These local structures are exactly the cliques — fully connected subsets of nodes where every pair is directly linked.

Conditional Independence: A Graph Example


原 PPT 独立图片资源
Conditional Independence: A Graph Example


原 PPT 独立图片资源

Clique Factorization and Hammersley–Clifford


原 PPT 独立图片资源
Clique Factorization and Hammersley–Clifford

Hammersley-Clifford theorem:
For a joint probability distribution that satisfies certain conditions (e.g., being strictly positive), if it obeys the Markov properties implied by a graph, then it can be factorized as a product of potential functions over the cliques of the graph:

𝜙 𝐶(𝑥𝐶): Potential function defined over clique 𝐶
𝑥𝐶: Value assignment to the variables in clique 𝐶
𝑍: Normalization constant (partition function)
This result shows that only by defining potential functions over cliques can we fully capture the local dependencies encoded in the graph’s structure.
原 PPT 独立图片资源

Log-Linear Models: Features and Weights


原 PPT 独立图片资源
Log-Linear Models: Features and Weights

The potential function can be expressed by:


For example: 𝑓𝑗(𝑥)∈ {0, 1}, 𝑤𝑗 = log  𝜙𝐶(𝑥𝐶)
The probability can be expressed as log-linear models:


Each feature 𝑓𝑗(𝑥) is a real-valued function (often binary)
原 PPT 独立图片资源
原 PPT 独立图片资源

A Two-Variable Markov Network


原 PPT 独立图片资源
A Two-Variable Markov Network

A minimum Markov Network


Each x𝑖 is a boolean random variable
We define a potential function 𝜙(𝑥1, 𝑥2) for this clique, which captures a certain preference or compatibility between x1  and x2 .
原 PPT 独立图片资源

Potentials: Scoring Four Worlds


原 PPT 独立图片资源
Potentials: Scoring Four Worlds

We hope the probability is larger when x1=x2 , so define:
原 PPT 独立图片资源
x1x_{1}
x2x_{2}
𝝓(x1,x2){\mathbf{ϕ}}\left( x_{1},x_{2} \right)
0
0
3
0
1
1
1
0
1
1
1
3

Normalization, Marginals and MAP


原 PPT 独立图片资源
Normalization, Marginals and MAP

Probability:
x1x_{1}
x2x_{2}
p(x1,x2)p\left( x_{1},x_{2} \right)
0
0
3/8
0
1
1/8
1
0
1/8
1
1
3/8
原 PPT 独立图片资源
原 PPT 独立图片资源

From Potentials to Features and Weights


原 PPT 独立图片资源
From Potentials to Features and Weights

Define feature function :

Define potential function:
Let 𝑤 = log 3, then :
If 𝑥1 = 𝑥2: 𝑓 = 1⇒𝜙 = exp(log 3) = 3
If 𝑥1 ≠ 𝑥2: 𝑓 = 0⇒𝜙 = exp(0) = 1
Potential function → Feature function + Weight
原 PPT 独立图片资源
原 PPT 独立图片资源

Feature Representation and Learnability


原 PPT 独立图片资源
Feature Representation and Learnability

Avoid enumerating all states:
Potential functions typically assign a value to every possible state of a clique.
If a clique contains k binary variables, the total number of states is 2𝑘 , meaning the potential function must store 2𝑘 values.
Feature functions generalize through logical structure:
A feature function can be defined to activate under specific logical conditions (e.g., 𝑋 = 𝑎  ∧   𝑌 = 𝑏).
Only a limited number of meaningful features need to be defined, rather than covering all 2𝑘 combinations.
This is akin to using rules to compress the representation space.
Easier to learn and optimize:
Feature functions form a linear combination in the log-likelihood expression.
The objective function is convex, making it amenable to efficient optimization (e.g., using L-BFGS).

Markov Networks: Parameter Learning


原 PPT 独立图片资源
Markov Networks: Parameter Learning

Learn the parameters (weights) of the model from data.
Two main learning tasks:
Structure learning: Learn the graph structure and features themselves
Parameter learning: Estimate weights 𝑤𝑗 of feature functions 𝑓𝑗(𝑥), given the graph structure and feature functions.
Challenges:
Parameter learning: the computation of Z need iterate all possible value of random variables;

Markov Networks: Inference Queries


原 PPT 独立图片资源
Markov Networks: Inference Queries

Goal: Given a Markov Network and observations, compute:
Marginal probability: 𝑃(𝑋𝑖)
Conditional probability: 𝑃(𝑌 | 𝑋 = 𝑥)
MAP estimation: Find argmax𝑥 𝑃(𝑥)
Challenge: Requires summing or maximizing over exponentially many joint configurations.

3.3 Logic and Uncertainty 3.3.4 Markov Logic Networks: Weighted Logic and Inference

Markov Logic Networks


原 PPT 独立图片资源

Markov Logic Networks


A Markov Logic Network is a set of pairs (𝐹𝑖, 𝑤𝑖), where:
𝐹𝑖 is a first-order logic formula
𝑤𝑖∈𝑅 is a weight
This means: if a possible world satisfies a formula 𝐹𝑖 , it should be more probable; and the larger the weight 𝑤𝑖, the higher the penalty for violating that formula.

MLN: Weighted Logical Rules


原 PPT 独立图片资源
MLN: Weighted Logical Rules


原 PPT 独立图片资源

MLN: From Templates to Networks


原 PPT 独立图片资源
MLN: From Templates to Networks


Generating Markov Network from MLN:
Given:
A set of rules (𝐹𝑖, 𝑤𝑖)
A set of Domain Constants 𝒞
Steps:
Grounding: For each formula 𝐹𝑖  and the constant set 𝒞, perform full grounding, i.e., enumerate all possible substitutions of variables with constants to generate specific ground clauses;
Making Cliques: Each grounded formula corresponds to a potential function, connecting all the variables (i.e., grounded Boolean predicates) involved in that formula;
Building the Network: All these variable nodes and potential functions together form a large undirected graph structure, which corresponds to the Markov Network.

MLN: Grounding with Typed Domains


原 PPT 独立图片资源
MLN: Grounding with Typed Domains


Grounding is the process of replacing the variables in a first-order logic formula with concrete constants, thereby generating specific ground formulas (Boolean clauses).
Suppose you have the formula:
𝐹𝑟𝑖𝑒𝑛𝑑𝑠(𝑥, 𝑦) ∧ 𝐿𝑖𝑘𝑒𝑠(𝑥, 𝑧)⇒𝐿𝑖𝑘𝑒𝑠(𝑦, 𝑧)
And your set of constants is:
𝒞 = {𝐴𝑙𝑖𝑐𝑒, 𝐵𝑜𝑏, 𝐶ℎ𝑎𝑟𝑙𝑖𝑒}
Then the grounding process will generate all possible clauses, such as:
𝐹𝑟𝑖𝑒𝑛𝑑𝑠(𝐴𝑙𝑖𝑐𝑒, 𝐵𝑜𝑏)∧𝐿𝑖𝑘𝑒𝑠(𝐴𝑙𝑖𝑐𝑒, 𝐼𝑐𝑒𝐶𝑟𝑒𝑎𝑚)⇒𝐿𝑖𝑘𝑒𝑠(𝐵𝑜𝑏, 𝐼𝑐𝑒𝐶𝑟𝑒𝑎𝑚)
𝐹𝑟𝑖𝑒𝑛𝑑𝑠(𝐶ℎ𝑎𝑟𝑙𝑖𝑒, 𝐵𝑜𝑏)∧…                                                                                                   

MLN: Ground Formulas as Factors


原 PPT 独立图片资源
MLN: Ground Formulas as Factors


After grounding, a rule (𝐹𝑖, 𝑤𝑖)  becoms (𝐹𝑖𝑔, 𝑤𝑖) 
Each predicate (e.g., 𝐿𝑖𝑘𝑒𝑠(𝐴𝑙𝑖𝑐𝑒, 𝐼𝑐𝑒𝐶𝑟𝑒𝑎𝑚)) appearing in a ground formula becomes a variable node.
If multiple predicates appear in the same formula, they form a clique;
The feature function of the clique is defined as


𝑥 is a possible world, i.e., a complete assignment of truth values to all predicate variables.
𝑓𝑖(𝑥) indicates whether the corresponding ground formula holds true in that world.
原 PPT 独立图片资源

MLN: Shared Weights and World Probabilities


原 PPT 独立图片资源
MLN: Shared Weights and World Probabilities


Connect all cliques into a huge network, and define the probability as:


Notice that feature functions grounded from a same rule share the same weights, so:


where 𝑛𝑘(𝑥) is the times of rule 𝐹𝑘 been satisfied in the world 𝑥.
原 PPT 独立图片资源
原 PPT 独立图片资源

MLN Example: Friends, Smoking and Cancer


原 PPT 独立图片资源
MLN Example: Friends, Smoking and Cancer


原 PPT 独立图片资源

MLN: Expressive Power and Hard Constraints


原 PPT 独立图片资源
MLN: Expressive Power and Hard Constraints


General framework for probabilistic modeling:
Every probability distribution over discrete (or finite-precision numeric) variables can be represented as an MLN;
Unified Representation Framework:
unify symbolic and statistical approaches to knowledge representation
Compatibility with Other SRL Models
PRM, KBMC, SLP …

MLN: Inference and Learning Costs


原 PPT 独立图片资源
MLN: Inference and Learning Costs 


MLNs define a probability distribution over all possible worlds
Inference complexity
MAP is generally NP-hard; exact partition functions and marginals involve hard counting problems.
Learning expense:
Learning often requires inference or approximations;
Grounding Explosion:
Number of constants, Arity of predicates, Number of formulas

3.3 Logic and Uncertainty 3.3.5 Probabilistic Soft Logic: Continuous Optimization

Probabilistic Soft Logic


原 PPT 独立图片资源

Probabilistic Soft Logic


PSL is a statistical relational learning framework that combines:
Logical rules
Probabilistic reasoning
Continuous-valued variables
Designed for efficient and scalable inference in real-world systems
“Soft logic + convex optimization for structured probabilistic reasoning”

PSL: Continuous Truth Semantics


原 PPT 独立图片资源
PSL: Continuous Truth Semantics

Let a = v(A), b = v(B) ∈ [0, 1]. The last column uses a = 0.8, b = 0.6.

Operation Truth value Logical meaning Ex.
⊥   Falsity 0 Always false. 0
⊤   Truth 1 Always true. 1
¬A   Negation 1 − a “Not A”: the complement of A’s truth degree. 0.2
A ⇒ B   Implication min(1, 1 − a + b) “If A, then B”: fully true when a ≤ b. 0.8
A ∨ B   Weak OR max(a, b) “A or B”: take the larger truth degree. 0.8
A ∧ B   Weak AND min(a, b) “A and B”: take the smaller truth degree. 0.6
A ⇔ B   Equivalence 1 − |a − b| Both implications hold; fully true when a = b. 0.8
A ⊕ B   Strong OR min(1, a + b) “A or B”: add truth degrees, capped at 1. 1
A ⊙ B   Strong AND max(0, a + b − 1) “A and B”: subtract both shortfalls from 1, floor at 0. 0.4
A ⊖ B   Difference max(0, a − b) A ⊙ ¬B: how much A exceeds B; violation of A ⇒ B. 0.2

PSL rule AND/OR use the strong operations ⊙/⊕, usually written ∧/∨ in PSL.
The weak min/max rows are included for comparison; ⊕ here does not mean XOR.

PSL: Hinge-Loss Potentials and MAP


原 PPT 独立图片资源
PSL: Hinge-Loss Potentials and MAP

1. Rule truth: A ⇒ B is ¬A ⊕ B, using Łukasiewicz strong OR.

t = v(A ⇒ B) = min(1, (1 − a) + b)

2. Violation is the shortfall from full truth: d = 1 − t.

d = 1 − min(1, 1 − a + b) = max(0, a − b)

a ≤ b: fully satisfied, d = 0.
Example: a = 0.6, b = 0.8 → d = 0.

a > b: penalize the gap, d = a − b.
Example: a = 0.8, b = 0.6 → d = 0.2.

3. Multiple premises: for A ⊙ B ⇒ C, let c = v(C).

L = max(0, a + b − 1),   d = max(0, L − c) = max(0, a + b − c − 1)

4. Weighted loss and MAP:   φi(x) = di(x)p,   minimize Σi wiφi(x).

x ∈ [0, 1]n; observed values fixed. Nonnegative wi, p ∈ {1, 2}, affine hinges
and a convex feasible set give convex MAP inference. Soft truth is not P(B | A).

PSL: Learning Rule Weights


原 PPT 独立图片资源
PSL: Learning Rule Weights

Input: A set of PSL rules and ground truth predicate values (training data)
Initialize weights: Typically set to 1.0 or randomly
Iterate:
Perform inference using the current weights 𝑤
Compare the predicted values 𝑥∗(𝑤) with the labeled data 𝑥{𝑡𝑟𝑢𝑒}
Compute the loss and update the weights 𝑤

Output: The learned optimal weight parameters 𝑤
原 PPT 独立图片资源