How Inference Works¶

This guide explains FuzzyInfer's forward-chaining inference engine in detail, covering the algorithm, pattern matching, and optimization strategies.

Forward-Chaining Algorithm¶

Forward chaining starts with known facts and derives new facts by repeatedly applying rules until no new knowledge can be inferred.

The Inference Loop¶

def run(self):
    """Forward-chaining inference until fixpoint."""
    iteration = 0
    while iteration < self.max_iterations:
        new_facts_found = False

        # Try each rule (sorted by priority)
        for rule in self.rules:
            if self._fire_rule(rule):
                new_facts_found = True

        if not new_facts_found:
            break  # Fixpoint reached

        iteration += 1

    return self

Phases¶

Match Phase: Find all facts that satisfy rule conditions
Fire Phase: Execute rule actions with variable bindings
Update Phase: Add new facts to knowledge base
Termination Check: Stop if no new facts or max iterations reached

Pattern Matching¶

Pattern matching binds variables to concrete values from facts.

Simple Pattern¶

# Rule condition: is-bird(?x)
# Fact: is-bird(tweety, 0.9)
# Binding: {?x: "tweety"}

Multiple Variables¶

# Condition: parent(?x, ?y)
# Facts:
#   parent(alice, bob)
#   parent(bob, charlie)
# Bindings:
#   {?x: "alice", ?y: "bob"}
#   {?x: "bob", ?y: "charlie"}

Chained Patterns¶

Rule(
    conditions=[
        {"pred": "parent", "args": ["?x", "?y"]},
        {"pred": "parent", "args": ["?y", "?z"]}
    ],
    actions=[
        {"action": "add", "fact": {"pred": "grandparent", "args": ["?x", "?z"]}}
    ]
)

# Given: parent(alice, bob), parent(bob, charlie)
# ?y binds to "bob" in both conditions
# Result: grandparent(alice, charlie)

Match All Results¶

Key Fix in v2.0: The engine now collects all matching facts, not just the first:

# Facts: is-bird(robin), is-bird(eagle), is-bird(sparrow)
# Condition: is-bird(?x)
# Results: 3 matches (previously returned only 1)

This ensures rules apply to every applicable fact.

Variable Binding¶

Binding Propagation¶

Bindings accumulate across conditions:

# Condition 1: is-bird(?x, ?d1)
#   Bindings: {?x: "robin", ?d1: 0.9}
# Condition 2: has-wings(?x, ?d2)
#   Must use ?x="robin" from condition 1
#   Bindings: {?x: "robin", ?d1: 0.9, ?d2: 1.0}

Degree Variables¶

Bind degree values to variables:

{
    "pred": "is-mammal",
    "args": ["?x"],
    "deg": "?d"  # Bind degree to ?d
}

# If is-mammal(dog, 0.95)
# Bindings: {?x: "dog", ?d: 0.95}

Degree Constraints¶

Add predicates on degree variables:

{
    "pred": "confidence",
    "args": ["?x"],
    "deg": "?d",
    "deg-pred": [">", "?d", 0.7]  # Only match if degree > 0.7
}

Supported operators: >, >=, <, <=, ==, !=

Degree Calculations¶

Arithmetic Expressions¶

Compute degrees using expressions:

# Multiply by constant
{"deg": ["*", "?d", 0.9]}

# Add two degrees
{"deg": ["+", "?d1", "?d2"]}

# Subtract
{"deg": ["-", 1.0, "?d"]}  # Negation

# Divide
{"deg": ["/", "?d", 2.0]}

Fuzzy Operations¶

# Fuzzy AND (minimum)
{"deg": ["min", "?d1", "?d2"]}

# Fuzzy OR (maximum)
{"deg": ["max", "?d1", "?d2"]}

# Bounded sum (algebraic sum)
{"deg": ["+", "?d1", "?d2", ["-", ["*", "?d1", "?d2"]]]}

Complex Expressions¶

Nest operations:

# (d1 * 0.8) + (d2 * 0.2)
{"deg": ["+", ["*", "?d1", 0.8], ["*", "?d2", 0.2]]}

# min(d1, d2) * 0.9
{"deg": ["*", ["min", "?d1", "?d2"], 0.9]}

Rule Priority¶

Rules execute in priority order (higher first):

# General rule: birds fly
Rule(name="birds-fly", priority=50, ...)

# Exception: penguins don't fly (higher priority)
Rule(name="penguin-exception", priority=100, ...)

Priority Strategy¶

Exceptions first: High priority for special cases
General rules: Medium priority for common patterns
Default rules: Low priority for fallback logic

Example:

inf = FuzzyInfer()

# Add facts
inf.add_fact(Fact("is-bird", ["penguin"], 0.95))
inf.add_fact(Fact("is-penguin", ["penguin"], 1.0))

# General rule (priority=50)
inf.add_rule(Rule(
    name="birds-fly",
    priority=50,
    conditions=[{"pred": "is-bird", "args": ["?x"]}],
    actions=[{"action": "add", "fact": {"pred": "can-fly", "args": ["?x"], "deg": 0.9}}]
))

# Exception (priority=100) - fires first
inf.add_rule(Rule(
    name="penguins-dont-fly",
    priority=100,
    conditions=[{"pred": "is-penguin", "args": ["?x"]}],
    actions=[{"action": "add", "fact": {"pred": "can-fly", "args": ["?x"], "deg": 0.1}}]
))

inf.run()
# Result: can-fly(penguin, 0.1) because exception fired first
# Then general rule tries to add can-fly(penguin, 0.9)
# Fuzzy OR: max(0.1, 0.9) = 0.9
# Final: can-fly(penguin, 0.9)

Note: Fuzzy OR still applies if both rules fire. For true exceptions, use degree constraints or modify actions.

Fuzzy OR Semantics¶

When multiple rules derive the same fact, FuzzyInfer applies fuzzy OR (maximum):

# Rule 1 derives: is-mammal(dog, 0.8)
# Rule 2 derives: is-mammal(dog, 0.95)
# Result: is-mammal(dog, 0.95)  ← max(0.8, 0.95)

Why Maximum?¶

Multiple independent sources of evidence should increase confidence, not decrease it:

Source 1 says "dog is mammal" (0.8 confidence)
Source 2 says "dog is mammal" (0.95 confidence)
Combined: Take the most confident source (0.95)

Implementation¶

def add_fact(self, fact: Fact) -> 'FuzzyInfer':
    """Add fact with fuzzy OR for duplicates."""
    key = (fact.predicate, tuple(fact.args))

    if key in self.facts:
        # Apply fuzzy OR (maximum)
        existing = self.facts[key]
        fact.degree = max(existing.degree, fact.degree)

    self.facts[key] = fact
    return self

Action Execution¶

Add Action¶

Most common - adds new facts:

{
    "action": "add",
    "fact": {
        "pred": "can-fly",
        "args": ["?x"],
        "deg": ["*", "?d", 0.9]
    }
}

# With bindings {?x: "robin", ?d: 0.9}
# Adds: can-fly(robin, 0.81)

Modify Action¶

Update existing fact degrees:

{
    "action": "modify",
    "fact": {
        "pred": "confidence",
        "args": ["?x"],
        "deg": ["*", "?d", 1.1]  # Boost by 10%
    }
}

Retract Action¶

Remove facts:

{
    "action": "retract",
    "pred": "temporary",
    "args": ["?x"]
}

Termination Conditions¶

Inference stops when:

Fixpoint reached: No new facts generated in iteration
Max iterations: Exceeded max_iterations limit (default: 100)

inf = FuzzyInfer(max_iterations=50)
result = inf.run()

if result._iteration_count >= 50:
    print("Warning: Hit iteration limit!")

Performance Characteristics¶

Time Complexity¶

Per iteration: O(R × F^C) where:
R = number of rules
F = number of facts
C = conditions per rule
Total: O(I × R × F^C) where I = iterations

Space Complexity¶

Facts: O(F) - stored in dictionary
Rules: O(R) - stored in list
Bindings: O(R × V) where V = variables per rule

Optimization Strategies¶

Current implementation uses brute-force matching:

# Check all facts for each condition
for fact in self.facts.values():
    if matches_condition(fact, condition, bindings):
        # Found match

Future optimizations:

Rete-like algorithm: Build discrimination network
Fact indexing: Hash by predicate for O(1) lookup
Incremental matching: Only check changed facts
Lazy evaluation: Defer degree calculations

Debugging Inference¶

Enable Logging¶

import logging

logging.basicConfig(level=logging.DEBUG)
logger = logging.getLogger('fuzzy_infer')

inf = FuzzyInfer()
# ... add facts and rules
inf.run()

# Shows:
# DEBUG: Iteration 1
# DEBUG: Fired rule: birds-fly with bindings {?x: "tweety"}
# DEBUG: Added fact: can-fly(tweety, 0.81)

Inference Log¶

inf.run()

# Check what happened
for entry in inf.inference_log:
    print(entry)

# Output:
# "Iteration 1: Fired rule 'birds-fly'"
# "Added fact: can-fly(tweety, 0.81)"
# "Iteration 2: No new facts"

Query Step-by-Step¶

inf = FuzzyInfer()
inf.add_fact(Fact("is-bird", ["robin"], 0.9))
inf.add_rule(birds_fly_rule)

# Before inference
print("Before:", inf.query("can-fly"))  # []

# Run one iteration
inf.run()

# After inference
print("After:", inf.query("can-fly"))  # [Fact(can-fly, [robin], 0.81)]

Complete Example¶

Comprehensive inference with multiple rules:

from fuzzy_infer import FuzzyInfer, Fact, Rule

# Create engine
inf = FuzzyInfer(max_iterations=100)

# Add observations
inf.add_fact(Fact("has-fur", ["rex"], 1.0))
inf.add_fact(Fact("has-four-legs", ["rex"], 1.0))
inf.add_fact(Fact("barks", ["rex"], 0.95))
inf.add_fact(Fact("chases-cats", ["rex"], 0.8))

# Rule 1: Animals with fur and four legs are mammals
inf.add_rule(Rule(
    name="mammal-classification",
    priority=100,
    conditions=[
        {"pred": "has-fur", "args": ["?x"], "deg": "?d1"},
        {"pred": "has-four-legs", "args": ["?x"], "deg": "?d2"},
        {"deg-pred": [">", ["min", "?d1", "?d2"], 0.7]}
    ],
    actions=[
        {"action": "add", "fact": {
            "pred": "is-mammal",
            "args": ["?x"],
            "deg": ["*", ["min", "?d1", "?d2"], 0.9]
        }}
    ]
))

# Rule 2: Mammals that bark are likely dogs
inf.add_rule(Rule(
    name="dog-classification",
    priority=50,
    conditions=[
        {"pred": "is-mammal", "args": ["?x"], "deg": "?d1"},
        {"pred": "barks", "args": ["?x"], "deg": "?d2"},
        {"deg-pred": [">", "?d2", 0.7]}
    ],
    actions=[
        {"action": "add", "fact": {
            "pred": "is-dog",
            "args": ["?x"],
            "deg": ["*", ["min", "?d1", "?d2"], 0.85]
        }}
    ]
))

# Rule 3: Dogs that chase cats are playful
inf.add_rule(Rule(
    name="playful-trait",
    priority=10,
    conditions=[
        {"pred": "is-dog", "args": ["?x"], "deg": "?d1"},
        {"pred": "chases-cats", "args": ["?x"], "deg": "?d2"}
    ],
    actions=[
        {"action": "add", "fact": {
            "pred": "is-playful",
            "args": ["?x"],
            "deg": ["*", ["min", "?d1", "?d2"], 0.9]
        }}
    ]
))

# Run inference
result = inf.run()

# Print results
print("Iterations:", result._iteration_count)
print("\nInferred facts:")
print("  is-mammal:", inf.query("is-mammal", ["rex"]))
print("  is-dog:", inf.query("is-dog", ["rex"]))
print("  is-playful:", inf.query("is-playful", ["rex"]))

# Output:
# Iterations: 3
# Inferred facts:
#   is-mammal: [Fact(is-mammal, [rex], 0.9)]
#   is-dog: [Fact(is-dog, [rex], 0.765)]
#   is-playful: [Fact(is-playful, [rex], 0.5508)]

Best Practices¶

1. Set Appropriate Iteration Limits¶

# For complex domains
inf = FuzzyInfer(max_iterations=200)

# For simple rules
inf = FuzzyInfer(max_iterations=50)

2. Use Rule Priorities¶

# High priority for exceptions
Rule(name="exception", priority=100, ...)

# Medium for general rules
Rule(name="general", priority=50, ...)

# Low for defaults
Rule(name="fallback", priority=10, ...)

3. Add Degree Constraints¶

Prevent low-confidence propagation:

{"deg-pred": [">", "?d", 0.6]}  # Only process if > 60% confidence

4. Use Conservative Degree Calculations¶

# Conservative: multiply to reduce overconfidence
{"deg": ["*", "?d", 0.8]}

# Optimistic: use original degree
{"deg": "?d"}

# Very conservative: minimum
{"deg": ["min", "?d", 0.7]}

5. Monitor Iterations¶

result = inf.run()
if result._iteration_count >= inf.max_iterations:
    logger.warning("Hit iteration limit - may need more iterations")

Summary¶

Forward chaining repeatedly applies rules until fixpoint
Pattern matching binds variables to fact values
Multiple results are now properly collected (v2.0 fix)
Rules execute in priority order (high to low)
Fuzzy OR (maximum) combines duplicate facts
Degree calculations support arithmetic and fuzzy operations
Termination occurs at fixpoint or iteration limit
Brute-force matching is simple but can be optimized

Next: Fluent API - Modern Pythonic interface