Large Reasoning Model


原 PPT 独立图片资源
Natural Language
Understanding

Large Reasoning Model
Mingming Sun
BIMSA

Part III: Course Map


原 PPT 独立图片资源
Part III: Course Map
3.1 Reasoning Processes and Search

3.2 Learning and Scaling Reasoning

3.3 Logic and Uncertainty

3.1 Reasoning Processes and Search 3.1.1 Explicit Reasoning and Decomposition



原 PPT 独立图片资源

3.1 Reasoning Processes and Search 3.1.1 Explicit Reasoning and Decomposition

原 PPT 独立图片资源

When Direct Answers Fail

An answer without the steps

A cafeteria starts with 23 apples, uses 20 for lunch, then buys 6 more. How many remain?

Standard-prompting output in the paper:
“The answer is 27.”

Which operation went wrong?

Example from Wei et al., Figure 1; not a new model run.

Does a larger model solve it?

GSM8K · standard few-shot prompting

Model Accuracy
PaLM 540B 17.9%

The prompt supplies question–answer examples, but no intermediate reasoning.

Wei et al., Table 2. Historical benchmark setting.

What if the examples showed how to reach the answer?

Chain of Thought: Building the Prompt

Example question: Roger has 5 tennis balls and buys 2 cans with 3 balls each. How many balls does he have?

Answer-only demonstration

Answer: 11.

Question → final answer

Add the intermediate steps

Two cans add 2\times3=6 balls.
Roger now has 5+6=11 balls.
Answer: 11.

Question → reasoning steps → answer

Apply the pattern to the apples: 23-20=3;\quad3+6=9, replacing the paper’s direct answer 27.

Few-shot CoT: change the demonstrations, keep the model weights fixed. Adapted from Wei et al., Figure 1.

Chain of Thought: Worked Example


原 PPT 独立图片资源
Chain of Thought: Worked Example
An interesting phenomenon in few shot learning on Pretrained LLM
原 PPT 独立图片资源
https://arxiv.org/pdf/2201.11903
原 PPT 独立图片资源

Chain of Thought: Results


原 PPT 独立图片资源
Chain of Thought: Results
https://arxiv.org/pdf/2201.11903
原 PPT 独立图片资源
原 PPT 独立图片资源

Zero-shot CoT: Method


原 PPT 独立图片资源
Zero-shot CoT: Method
https://arxiv.org/pdf/2205.11916
原 PPT 独立图片资源

Zero-shot CoT: Results


原 PPT 独立图片资源
Zero-shot CoT: Results
https://arxiv.org/pdf/2205.11916
原 PPT 独立图片资源
原 PPT 独立图片资源

Least-to-Most Prompting

Plan subproblems; reuse their answers

  1. Decompose: identify the smaller questions needed to solve the original task.
  2. Solve in order: include earlier question–answer pairs in each later prompt.
  3. Compose: use those intermediate answers to solve the original question.
Amy’s slide
One trip: 4+1=5 minutes.
15\,\text{minutes}\div5=3 complete trips.

A missing dependency or wrong sub-answer can propagate. No interpreter is required.

Least-to-Most Figure 1: decompose Amy’s water-slide question, then append the first answer to solve the second question.
Zhou et al. · ICLR 2023 · Fig. 1, p. 2
Original figure; click to enlarge. Few-shot demonstrations are omitted in the paper figure.
Longer action instructions (SCAN)
“run and look twice” → RUN LOOK LOOK
CoT 16.2% → Least-to-Most 99.7%
Length split · code-davinci-002 · Table 8.

PAL: Program-aided Language Models

Generate a program; execute the calculation

Language model: map the story to variables, operations and executable Python.

Interpreter: run the generated program and return its computed answer.

baked = 200
sold = 93 + 39
returned = 6
answer = baked - sold + returned  # 74

“Returned” means +6 here. An interpreter also executes the wrong translation (-6) faithfully.

PAL Figure 1 lower-right panel: generated bread-inventory program, interpreter execution, and result 74.
Gao et al. · ICML 2023 · Fig. 1, p. 2
Paper screenshot, lower-right panel. Click for the full CoT / PAL comparison.
When the arithmetic gets harder
GSM-Hard: CoT 23.1% → PAL 61.2%
Word-problem quantities replaced by large numbers.
code-davinci-002 · Table 1; three prompt orders.

PoT: Program of Thoughts

Prompt supplied to the model

Write Python. Store the result in ans.
# Example: 5 balls + 2 cans, 3 per can.
balls = 5
new_balls = 2 * 3
ans = balls + new_balls

# New question: 23 apples; use 20
# for lunch, then buy 6. How many remain?
# Python:

Few-shot: question–program examples, then a new question with its program left blank.

Zero-shot: instruction + new question, without the worked examples.

Model continuation → execution

apples = 23
remaining = apples - 20
ans = remaining + 6

Python executes the code: ans = 9.

Illustrative prompt and continuation; one demonstration shown.

PoT Figure 2 upper panel: few-shot Codex results, CoT in blue and PoT in red, across seven numerical reasoning datasets.
Chen et al. · TMLR 2023 · Fig. 2, p. 3
Upper panel: few-shot Codex. GSM8K: CoT 63.1% → PoT 71.6%. Historical results under the paper’s evaluation protocol.

3.1 Reasoning Processes and Search 3.1.2 Test-Time Scaling I: Search and Feedback



原 PPT 独立图片资源

3.1 Reasoning Processes and Search 3.1.2 Test-Time Scaling I: Search and Feedback

原 PPT 独立图片资源

Reasoning Paths as a Search Space


原 PPT 独立图片资源
Reasoning Paths as a Search Space
The decoding space is huge!
It may contain the correct answer for complex problems.
The problem is: How to find them in the huge decoding space?
We’ve learned to activate the COT using carefully designed prompt;
Can we do better without controlling prompt?
Explore in the decoding phase to find logical path to the correct answer ! – Testing Time Scaling

Allocating Test-Time Compute

Breadth

How many candidate paths or branches should we explore?

Continuation
& Revision

How long should we continue a path, and how many times should we revise it?

Selection
& Stopping

Which candidates should we keep, and when should we stop?

CoT-decoding: Candidate Generation


原 PPT 独立图片资源
CoT-decoding: Candidate Generation








Pre-trained LLMs have had responses with step-by-step reasoning among the generations started with the top-k tokens;
But how can we extract the correct reasoning answers?
原 PPT 独立图片资源
Image Source: Xuezhi Wang, et. al, Chain-of-Thought Reasoning Without Prompting, arXiv, 2024

CoT-decoding: Answer Selection


原 PPT 独立图片资源
CoT-decoding: Answer Selection
When a step-by-step reasoning path is present, the final answer will have higher confidence;
Extracting the final answer and then compare the confidence, we get COT sequence with good performance.
原 PPT 独立图片资源
Image Source: Xuezhi Wang, et. al, Chain-of-Thought Reasoning Without Prompting, arXiv, 2024
原 PPT 独立图片资源

CoT-decoding: Results


原 PPT 独立图片资源
CoT-decoding: Results
When a step-by-step reasoning path is present, the final answer will have higher confidence;
Extracting the final answer and then compare the confidence, we get COT sequence with good performance.
Image Source: Xuezhi Wang, et. al, Chain-of-Thought Reasoning Without Prompting, arXiv, 2024
原 PPT 独立图片资源
原 PPT 独立图片资源

Self-Consistency: Answer Marginalization


原 PPT 独立图片资源
Self-Consistency: Answer Marginalization
With COT, LLM does following in decoding:
arg max 𝑃(𝑟𝑒𝑎𝑠𝑜𝑛𝑖𝑛𝑔 𝑝𝑎𝑡h, 𝑓𝑖𝑛𝑎𝑙 𝑎𝑛𝑠𝑤𝑒𝑟|𝑝𝑟𝑜𝑏𝑒𝑙𝑚)  
But we want:
arg max 𝑃(𝑓𝑖𝑛𝑎𝑙 𝑎𝑛𝑠𝑤𝑒𝑟|𝑝𝑟𝑜𝑏𝑒𝑙𝑚)  
We can do this by sampling:
𝑃(𝑓𝑖𝑛𝑎𝑙 𝑎𝑛𝑠𝑤𝑒𝑟|𝑝𝑟𝑜𝑏𝑒𝑙𝑚)=∑{𝑟𝑒𝑎𝑠𝑜𝑛𝑖𝑛𝑔 𝑝𝑎𝑡h}𝑃(𝑟𝑒𝑎𝑠𝑜𝑛𝑖𝑛𝑔 𝑝𝑎𝑡h, 𝑓𝑖𝑛𝑎𝑙 𝑎𝑛𝑠𝑤𝑒𝑟|𝑝𝑟𝑜𝑏𝑙𝑒𝑚)
Xuezhi Wang, et, al. Self-Consistency Improves Chain of Thought Reasoning in Language Models. ICLR 2023.

Self-Consistency: Sampling and Aggregation


原 PPT 独立图片资源
Self-Consistency: Sampling and Aggregation
Xuezhi Wang, et, al. Self-Consistency Improves Chain of Thought Reasoning in Language Models. ICLR 2023.
原 PPT 独立图片资源

Self-Consistency: Results and Agreement


原 PPT 独立图片资源
Self-Consistency: Results and Agreement
Xuezhi Wang, et, al. Self-Consistency Improves Chain of Thought Reasoning in Language Models. ICLR 2023.
原 PPT 独立图片资源
原 PPT 独立图片资源

Tree of Thoughts: Search and Pruning


原 PPT 独立图片资源
Tree of Thoughts: Search and Pruning
In each state, generate several next thought, then evaluate and prune.
Just like tree search.
原 PPT 独立图片资源
Shunyu Yao, et, al. Tree of Thoughts: Deliberate Problem Solving with Large Language Models, Arxiv, 2023

Tree of Thoughts: Game of 24


原 PPT 独立图片资源
Tree of Thoughts: Game of 24
Shunyu Yao, et, al. Tree of Thoughts: Deliberate Problem Solving with Large Language Models, Arxiv, 2023
原 PPT 独立图片资源

Self-Refine: Feedback and Revision


原 PPT 独立图片资源
Self-Refine: Feedback and Revision

原 PPT 独立图片资源
Image Source: https://selfrefine.info/

Self-Refine: A Revision Example


原 PPT 独立图片资源
Self-Refine: A Revision Example
原 PPT 独立图片资源
Image Source: https://selfrefine.info/

Self-Correction: Limits without External Feedback


原 PPT 独立图片资源
Self-Correction: Limits without External Feedback
Jie Huang, et.al, Large language models cannot self-correct reasoning yet, ICLR 2024
“Large language models cannot self-correct reasoning yet”
Question: If an LLM possesses the ability to self-correct, why doesn’t it simply offer the correct answer in its initial attempt?
The promising results of previous research is misleading;
LLMs cannot properly judge the correctness of their reasoning -- the feedback is misleading.
原 PPT 独立图片资源

Learned Feedback: Critic GPT


原 PPT 独立图片资源
Learned Feedback: Critic GPT
Nat McAleese, et.al, LLM Critics Help Catch LLM Bugs, arxiv 2024
Useful critiques still need independent checks.
原 PPT 独立图片资源

Test-Time Compute: When Is It More Efficient?


原 PPT 独立图片资源
Test-Time Compute: When Is It More Efficient?
Snell et al., Figure 1: left, inference allocation; right, FLOPs-matched pretraining versus inference, split by difficulty and total inference load.
MATH · same total FLOPs
A: pretrain a ~14× larger model;
use greedy decoding.
B: keep PaLM 2-S*;
spend more on revisions / search.
Same pretraining token count in both options.
R = total inference tokens / pretraining tokens
Medium questions · revisions
R = 0.16+27.8%R = 22−24.3%
Relative accuracy of B vs A, not percentage points.
Positive: B wins. Negative: A wins.

Test-Time Compute: A Unified Framework

Apple case: 23-20+6. A first answer says 27; the correct answer is 9.

compute overviewAt fixed model weights, a controller spends a question budget on generation, continuation and evaluation. Feedback returns to the controller; only stopping produces the final answer. This loop contains no parameter update.
Question x
Budget B
Allocate computationBranch · continue · stop
Generate with \theta
Weights stay fixed
Evaluate / selectVote · score · testfeedback or selected state → continue / stop → answer
Control What changes in this case What it buys
Candidate breadth Sample answers: 27, 9, 9 Expose alternatives
Sequential work Recheck 23-20=3; then +6 Repair the arithmetic
Selection & stopping Vote for 9; or execute the expression Return a checked answer

Learning: checked experience → update \theta → freeze \theta^{\prime} → use the same controls again.

Constructed paths, not a benchmark. A majority can still be wrong. Count all generation and checking costs.

3.2 Learning and Scaling Reasoning 3.2.1 From Search Experience to Learning



原 PPT 独立图片资源

3.2 Learning and Scaling Reasoning 3.2.1 From Search Experience to Learning

原 PPT 独立图片资源

Search Experience and Parameter Learning


原 PPT 独立图片资源
Search Experience and Parameter Learning
By perform exploration in the decoding phase:
stepwise reasoning paths are identified;
the accuracy of answers are greatly improved.
Why LLM cannot directly generate the reasoning paths?
Learning from Verifiable Feedback

Search Can Teach a Policy

A car needs repair. What should its owner order?

Turn a checked answer into training

Case: choose a machine part, rather than gas or a street crossing.

Generate a rationale connecting the repair to the required part. Keep the rationale if its answer matches the label.

Fine-tune on accepted rationale–answer pairs; repeat. A failed question can be retried with the correct answer as a hint.

Adapted from the paper’s CQA example. The answer check does not certify every rationale step.

Does the next model improve?

GPT-J · CQA dev Accuracy
Few-shot CoT 36.6%
Answer-only fine-tuning 60.0%
STaR + rationalization 72.5%

+12.5 pp over answer-only fine-tuning on this task.

Table 1 · GPT-J 6B · labeled training answers; few-shot rationale seeds. Not inference-only prompting.

Expert Iteration trains on search decisions; STaR trains on accepted rationales. Both change the policy’s parameters.

o1: Reasoning Model Overview


原 PPT 独立图片资源
o1: Reasoning Model Overview

o1: Reported Results


原 PPT 独立图片资源
o1: Reported Results
Image Source: https://www.vellum.ai/blog/analysis-openai-o1-vs-gpt-4o
原 PPT 独立图片资源
原 PPT 独立图片资源

o1: What Was Publicly Known


原 PPT 独立图片资源
o1: What Was Publicly Known
We don’t know;
Old Road Map?
Labeling amount of Supervised Thinking Data;
Supervise Finetune the Model
Apply the RLHF to improve the performance.

3.2 Learning and Scaling Reasoning 3.2.2 R1-Zero: Learning from Verifiable Rewards

R1-Zero: Learning from Verifiable Rewards


原 PPT 独立图片资源

R1-Zero: Learning from Verifiable Rewards

No supervised data needed!
Training directly on the pretrained model using RL.
https://medium.com/@lmpo/deepseek-r1-affordable-efficient-and-state-of-the-art-ai-reasoning-f293b0bd8d65
DeepSeek-R1: Affordable, Efficient, and State-of-the-Art AI Reasoning | by  LM Po | Jan, 2025 | Medium

R1-Zero: Response Structure


原 PPT 独立图片资源
R1-Zero: Response Structure
Directly prompting the pretrained model to generate the think procedure.
原 PPT 独立图片资源

R1-Zero: Accuracy and Format Rewards


原 PPT 独立图片资源
R1-Zero: Accuracy and Format Rewards
Rule based reward system:
Accuracy Rewards: Whether the response is correct. Math: rule based verification; LeetCode, complier feedback.
Format Rewards: enforces the model put thinking process between <think> and </think>;
No neural reward model:
Reward hacking;

R1-Zero: From Response to Verifiable Reward

Teaching example: solve 2x+1=2. Extract the answer before assigning credit.

r1 reward pipelineA generated response is parsed, compared with a reference or executed on tests, and assigned reward components. These become a learning signal; no gradient through the rule checker is required. Generate
Response o for task q
ExtractAnswer / code / tagsCheckReference or testsRecordReward + status
Candidate Check against x=\frac12 Recorded result
Answer: 0.5 2\times0.5+1=2 Correct value
Answer: 1.5 2\times1.5+1=4\ne2 Wrong value
0.5; missing required tags Value and format checked separately Correct value; format failure

Benefit: same credit for 0.5 and \frac12; no credit for 1.5.

R1-Zero: Math and Format Rewards

Task: solve 2x+1=2. Reference: x=\frac12.

<think>...</think><answer>1/2</answer>
Candidate Answer Tags valid? r_{\mathrm{acc}} r_{\mathrm{fmt}} r_{\mathrm{demo}}
A \frac12 Yes 1 1 1
B \frac32 Yes 0 1 0
C 0.5 Yes 1 1 1
D \frac12 No think tags 1 0 0

Classroom gate: r_{\mathrm{demo}}=r_{\mathrm{acc}}\,r_{\mathrm{fmt}}\;\longrightarrow\;[1,0,1,0].

Constructed candidates and a teaching-only scoring rule. This is not a claim about R1-Zero’s exact aggregation weights or parser. Correct final answers do not certify every reasoning step.

R1-Zero: Code Execution Rewards

Task: return \lvert a-b\rvert for two integers.

Runs, but violates the task

def distance(a, b):
    return a - b

The program runs normally.
Swapping the inputs reveals the bug.

Repair: return abs(a - b)

Tests supply concrete evidence

Input Expected Actual
(5, 2) 3 3 ✓
(2, 5) 3 −3 ✗
(2, 2) 0 0 ✓

Classroom reward: all selected tests pass → 1; wrong output, runtime error or timeout → 0. Here: 0; after repair: 1.

Illustrative binary rule, not a published R1 implementation. Keep failure statuses separate; a test-system outage should be retried or excluded, not treated as evidence of incorrect code.

R1-Zero: GRPO


原 PPT 独立图片资源
R1-Zero: GRPO
GRPO(Group Relative Policy Optimization):
No critic model
Estimate the baseline from group scores.
原 PPT 独立图片资源
原 PPT 独立图片资源
10.48550/arXiv.2501.12948

R1-Zero: Response Length during Training


原 PPT 独立图片资源
R1-Zero: Response Length during Training
10.48550/arXiv.2501.12948
原 PPT 独立图片资源

R1-Zero: A Self-Checking Trace


原 PPT 独立图片资源
R1-Zero: A Self-Checking Trace
10.48550/arXiv.2501.12948
原 PPT 独立图片资源

R1-Zero: Evaluation Results


原 PPT 独立图片资源
R1-Zero: Evaluation Results
10.48550/arXiv.2501.12948
原 PPT 独立图片资源

3.2 Learning and Scaling Reasoning 3.2.3 Test-Time Scaling II: Length Control

Test-Time Compute: Length and Stopping

Apple case: a first answer says 27. Spend the next tokens rechecking 23-20+6=9.

compute revisitAt fixed model weights, a controller spends a question budget on generation, continuation and evaluation. Feedback returns to the controller; only stopping produces the final answer. This loop contains no parameter update.
Question x
Budget B
Allocate computationBranch · continue · stop
Generate with \theta
Weights stay fixed
Evaluate / selectVote · score · testfeedback or selected state → continue / stop → answer
Illustrative allocation Generation-token cap Information use
Many shorter paths 8\times512=4{,}096 Explore alternatives, then select
One longer path 1\times4{,}096=4{,}096 Continue from earlier tokens
Combined allocation 4\times1{,}024=4{,}096 Combine breadth and continuation

s1-32B / AIME24: 50.0% → 56.7% with budget forcing (Table 1). Same trained checkpoint; extra inference computation.

Apple repair and token allocations are illustrations. s1 supplies the measured result; longer thinking can also loop.

Budget Forcing: Controlling Reasoning Length


原 PPT 独立图片资源
Budget Forcing: Controlling Reasoning Length
Specifying the length of thinking in prompts: No precise control.
Forcing a maximum and/or minimum number of thinking tokens
Forcing a Maximum Token Count: Appending the end-of-thinking token delimiter early during the thinking phase. “Final Answer:” can also be appended to provide its current best answer.
Forcing a Minimum Token Count: Suppressing the generation of the end-of-thinking token delimiter. Optionally, strings such as “Wait” can be appended to the model‘s current reasoning trace, encouraging the model to reflect on its current generation.

Budget Forcing: A Worked Example


原 PPT 独立图片资源
Budget Forcing: A Worked Example
https://arxiv.org/pdf/2501.19393
原 PPT 独立图片资源

Budget Forcing: Compute and Performance


原 PPT 独立图片资源
Budget Forcing: Compute and Performance
原 PPT 独立图片资源
https://arxiv.org/pdf/2501.19393

Compute Scaling: A Schematic


原 PPT 独立图片资源
Compute Scaling: A Schematic
原 PPT 独立图片资源
https://zhuanlan.zhihu.com/p/22658624635?utm_source=chatgpt.com

3.2 Learning and Scaling Reasoning 3.2.4 Reasoning Efficiency



原 PPT 独立图片资源

3.2 Learning and Scaling Reasoning 3.2.4 Reasoning Efficiency

原 PPT 独立图片资源

Overthinking: Redundant Computation


原 PPT 独立图片资源
Overthinking: Redundant Computation
https://arxiv.org/pdf/2503.21614
原 PPT 独立图片资源
原 PPT 独立图片资源

Overthinking: Length and Performance


原 PPT 独立图片资源
Overthinking: Length and Performance
https://arxiv.org/pdf/2503.21614
原 PPT 独立图片资源

Allocating Inference Compute


原 PPT 独立图片资源
Allocating Inference Compute
https://arxiv.org/pdf/2503.21614
原 PPT 独立图片资源

Coconut: Reasoning in Latent Space


原 PPT 独立图片资源
Coconut: Reasoning in Latent Space
原 PPT 独立图片资源
https://arxiv.org/pdf/2412.06769

3.2 Learning and Scaling Reasoning 3.2.5 Code and Proof: Learning from Verification

DeepCoder: preserve input order in code.

AlphaProof: finish a Lean proof that can be checked.

DeepCoder: The Training Loop

Return the first even value: on [8, 2], sorting returns 2; scanning in order returns 8.

deepcoder trainingCoding tasks provide prompts to a policy and tests to a separate sandbox. Candidate programs are executed, outcome rewards feed a GRPO+ update, and the updated policy produces the next group. Training tasksProblem + testsChecked dataCoder policySample a groupof candidate programsCode sandboxExecute selected testsCompare outputsOutcome rewardAll pass: 1Otherwise: 0promptcodelogstests go to the runnerGRPO+ updateGroup-relative learningrewardsupdated parameters

Measured benefit: LiveCodeBench 53.0% → 60.6% Pass@1 at a 64K cap.
DeepSeek-R1-Distill-Qwen-14B → DeepCoder-14B-Preview. Task above is illustrative; benchmark window: Aug 2024–Feb 2025.

DeepCoder: Execution Feedback and Learning

Task: return the first even value in the original input order; otherwise None.

Wrong: sort before scanning

for x in sorted(xs): changes the order.

Input Required Wrong candidate
[8, 2] 8 2 ✗
[] None None ✓
[1, 3] None None ✓
[1, 4, 2] 4 2 ✗

Sorted candidate: 2 / 4 pass → reward 0.

Correct: scan in input order

def first_even(xs):
    for x in xs:
        if x % 2 == 0:
            return x
    return None

No sorting: 4 / 4 pass → reward 1.

All selected tests must pass for reward 1.
GRPO+ compares rewards to update the model.

Classroom illustration. Passing these tests is finite evidence.

DeepCoder: Compare Matching Token Caps

From one repaired function to a coding benchmark: does the trained policy solve more new tasks?

Max tokens Starting model DeepCoder Change (pp)
16K 50.2 45.6 −4.6
32K 53.0 57.9 +4.9
64K 53.0 60.6 +7.6

Training comparison: +4.9 points at 32K; +7.6 at 64K.
Inference comparison: DeepCoder gains 2.7 points from 32K to 64K.

LiveCodeBench Pass@1 (%), paper’s evaluation window. Matching token caps does not equal matching actual compute. Gains belong to the complete training recipe.

AlphaProof: The Learning and Search System

From b=a\cdot k and c=b\cdot l, prove a divides c: verified search produces learning data.

alphaproof trainingInformal mathematics is auto-formalized into a Lean problem curriculum. A proof network guides search in Lean; search experience trains the policy and value, improving subsequent search. Auto-formalizationInformal mathematics→ Lean statementsLean task poolFormal problemsfor trainingProver + searchPolicy / value network↔ Lean environmentSearch experienceChecked proofs+ search outcomesTrain policy & valueAlphaZero-style learninglearning targetsupdated network

Case: construct a witness m with c=a\cdot m. Which candidate works: k+l or k\cdot l?
Teaching proof. System result: three IMO 2024 problems solved; manual formalization, multi-day computation.

Lean: Proof Names and the Goal State

Divisibility: b=a\cdot k and c=b\cdot l. Find m such that c=a\cdot m.

Names and types

Notation Meaning
a b c k l : Nat Natural numbers.
hk : b = a * k A proof of this equality.
∃ m, c = a * m A witness m and its equality proof.

hk and hl are chosen proof names.

State S_2: witnesses unpacked

a b c k l : Nat
hk : b = a * k
hl : c = b * l
⊢ ∃ m, c = a * m

Above ⊢: available facts.
After ⊢: the goal still to prove.

A state display, not a standalone program.

⟨k * l, ?_⟩ supplies m=k\cdot l and leaves an equality to prove.

AlphaProof: Inside the Proof Search

alphaproof searchA Lean state contains hypotheses and goals. The policy suggests tactics, value-guided tree search chooses a branch, and Lean checks each move. Valid moves create new goals, invalid moves are rejected, and a complete proof is checked. Proof stateHypotheses + goalsNetwork + searchPropose / rank tacticsLean checksApply a valid tacticNew state / proofSubgoals or finishedvalidinvalid → another tacticremaining goals → continue

A complete Lean 4 proof

example (a b c : Nat)
    (hab : ∃ k, b = a * k)
    (hbc : ∃ l, c = b * l) :
    ∃ m, c = a * m := by
  rcases hab with ⟨k, hk⟩
  rcases hbc with ⟨l, hl⟩
  refine ⟨k * l, ?_⟩
  rw [hl, hk, Nat.mul_assoc]

Follow the construction

S_0\to S_1\to S_2: extract k and l.

S_2\to S_3: propose m=k\cdot l.
New goal: c = a * (k * l).

S_3 → complete:
c=b\cdot l=(a\cdot k)\cdot l=a\cdot(k\cdot l).

Lean 4 core. Checked classroom proof.

AlphaProof: Candidates and Lean Feedback

Same state S_2: \mathrm{hk}:b=a\cdot k, \mathrm{hl}:c=b\cdot l; goal ∃ m, c = a * m.

Model-generated candidate Lean feedback Search consequence
exact hk Type mismatch: an equality
is not the required existential proof.
Invalid action.
Discard this candidate.
refine ⟨k + l, ?_⟩ Valid move. New goal:
c = a * (k + l)
Rewriting leaves
a*(k*l) = a*(k+l).
refine ⟨k * l, ?_⟩ Valid move. New goal:
c = a * (k * l)
rw [hl, hk,
Nat.mul_assoc] closes it.

Another verified candidate:
exact ⟨k * l, by rw [hl, hk, Nat.mul_assoc]⟩

Constructed candidates, each starting from S_2. A valid move can leave an unprovable goal.

AlphaProof: From Verified Proofs to Learning

Search finds a checked proof. Its state–tactic pairs train the next proof network.

Training targets from this path

State Target tactic Return
S_0 rcases hab with ⟨k, hk⟩ −4
S_1 rcases hbc with ⟨l, hl⟩ −3
S_2 refine ⟨k * l, ?_⟩ −2
S_3 rw [hl, hk, Nat.mul_assoc] −1

−1 per submitted tactic. Values refer to this verified path; the one-action alternative at S_2 has return −1.

Why better candidates become likelier

Policy: token cross-entropy on the target tactic.
Value: predict the observed remaining-step return.

\mathcal L_{\mathrm{policy}}=-\sum_j\log\pi_\theta(a_j\mid s,a_{<j})
\theta\leftarrow\theta-\eta\nabla_\theta\!\left(\mathcal L_{\mathrm{policy}}+\lambda\mathcal L_{\mathrm{value}}\right)

At the token prefix refine ⟨k:
target * has logit gradient p(\mathtt{*})-1;
alternative + has gradient p(\mathtt{+}).

Verified: the proof of the formal statement. Learned: tactic generation and proof difficulty.
Failed proof attempts are filtered from updates. The checker itself stays fixed.

AlphaProof: Learning Gains and IMO Results

Original AlphaProof Figure 3: training outcomes, held-out solving rates and proof-finding efficiency
miniF2F-valid · fixed 4,000 simulations≈65% → 96.7%
Formal IMO · fixed ≈30% solve rate3,497 → 308 simulations · ≈11.35× fewer
IMO 2024

AlphaProof: 3 problems. With AlphaGeometry 2: 4 / 6 · 28 / 42, silver-medal level.

Manual formalization; some solutions took days. Proofs are relative to the formal statements.

Learning from Verifiable Feedback

Learning loop R1-Zero DeepCoder AlphaProof
Generates Reasoning + answer Programs Proof tactics
Checks Answer correctness /
test outcomes
Selected tests Lean: valid steps
and complete proof
Signal Accuracy + format All pass: 1
Otherwise: 0
Verified proofs
−1 per tactic
Update GRPO GRPO+ Policy cross-entropy
+ value learning

Independent verification provides the learning signal.

What Code and Math Verifiers Check

So far: verifiable feedback for code and mathematics.

Verifier What it checks What must already be specified
Code tests Outputs on selected inputs Expected behavior and test coverage
Math answer checker Agreement with an answer criterion The correct answer and equivalence rules
Proof assistant A proof of a formal statement The statement and its assumptions

Natural-language reasoning adds a missing interface:
Which facts, relations and constraints does the text express?

Next: formalize the text and delegate deduction to a symbolic solver.
Later: model uncertain facts and rules with exceptions.

Further Reading: Reasoning Models



原 PPT 独立图片资源
Further Reading: Reasoning Models
原 PPT 独立图片资源

Reference Paper: DeepSeek-R1


原 PPT 独立图片资源
Reference Paper: DeepSeek-R1
Deepseek-AI, et, al. DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning, 2025

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 独立图片资源