Repository: pgmpy/pgmpy

Issue:
Transient exception when using exact inference
### Subject of the issue
Transient exception when using exact inference
I am trying to perform exact inference in a Bayesian network using the Junction Tree algporithm.
However I encounter a transient error when performing the infer.query() call, apparently showing that the subtrees do not have a correct mapping between state name -> state index. Sometime it works, sometimes not, with a rate of about 50% for me. Both pgmpy=0.1.24 and pgmpy==0.1.23

### Your environment
* pgmpy version: both pgmpy=0.1.24 and pgmpy==0.1.23
* Python version: 3.8, 3.9, 3.10
* Operating System: Ubuntu 22.04

### Steps to reproduce
The code is taken from the example notebook and is provided below for reproduction. 

```
from pgmpy.inference import BeliefPropagation
from pgmpy.utils import get_example_model

if __name__ == '__main__':
    asia_model = get_example_model('asia')
    algo =BeliefPropagation
    asia_infer = algo(asia_model)
    # Computing the probability of bronc given smoke=no.
    q = asia_infer.query(variables=["bronc", "asia"], evidence={"smoke": "yes"})
    print(q)
    pass

```

### Expected behaviour
proper return giving the result of the query
+------------+---------+-------------------+
| bronc      | asia    |   phi(bronc,asia) |
+============+=========+===================+
| bronc(yes) | asia(0) |            0.0060 |
+------------+---------+-------------------+
| bronc(yes) | asia(1) |            0.5940 |
+------------+---------+-------------------+
| bronc(no)  | asia(0) |            0.0040 |
+------------+---------+-------------------+
| bronc(no)  | asia(1) |            0.3960 |
+------------+---------+-------------------+

### Actual behaviour
Not systematically but frequently (about 25% of the attempt) I get the following exception. Note that this happens with various forms of query, but seems to get more frequent with more query variables and can reach up to 75%. Note that the example exception is obtained with  pgmpy==0.1.24 but is the same with 0.1.23 and also with other python versions

```
/home/franckm/WORKSPACE/WK_PYPGM_TEST/pypgm_test2/myenv3_8_pgmpy24/lib/python3.8/site-packages/pgmpy/factors/discrete/DiscreteFactor.py:799: RuntimeWarning: invalid value encountered in divide
  phi.values = phi.values / phi1.values
Traceback (most recent call last):
  File "./inference_basic.py", line 14, in <module>
    q = asia_infer.query(variables=["bronc", "asia"], evidence={"smoke": "yes"})
  File "/home/franckm/WORKSPACE/WK_PYPGM_TEST/pypgm_test2/myenv3_8_pgmpy24/lib/python3.8/site-packages/pgmpy/inference/ExactInference.py", line 1121, in query
    result = self._query(
  File "/home/franckm/WORKSPACE/WK_PYPGM_TEST/pypgm_test2/myenv3_8_pgmpy24/lib/python3.8/site-packages/pgmpy/inference/ExactInference.py", line 1022, in _query
    return variable_elimination.query(
  File "/home/franckm/WORKSPACE/WK_PYPGM_TEST/pypgm_test2/myenv3_8_pgmpy24/lib/python3.8/site-packages/pgmpy/inference/ExactInference.py", line 338, in query
    indexer[index] = phi.get_state_no(
  File "/home/franckm/WORKSPACE/WK_PYPGM_TEST/pypgm_test2/myenv3_8_pgmpy24/lib/python3.8/site-packages/pgmpy/utils/state_name.py", line 72, in get_state_no
    return self.name_to_no[var][state_name]
KeyError: 'yes'
```

Discussion:
@ankurankan: @fcmwork Thanks for reporting this. This does seem like a bug; I will have a look at it. In the meantime, you could also use Variable Elimination for inference.@fcmwork: @ankurankan  thank you for your prompt answer. **Have you been able to reproduce it?** I am wondering if you are willing to share a full pipdeptree of your testing environment I could try to figure out if there are any differences.@ankurankan: @fcmwork I am using the latest versions of all the dependencies. I have been able to reproduce it, the issue seems to be in the initialization of factors of the JunctionTree. The DiscreteFactors in the JunctionTree seem to not have all the state names. 
```python
In [4]: asia_infer.junction_tree
Out[4]: <pgmpy.models.JunctionTree.JunctionTree at 0x7f3111e1eb00>

In [5]: asia_infer.junction_tree.nodes()
Out[5]: NodeView((('bronc', 'dysp', 'either'), ('bronc', 'xray', 'lung', 'either', 'tub'), ('bronc', 'xray', 'lung', 'asia', 'tub'), ('bronc', 'xray', 'lung', 'asia', 'smoke')))

In [7]: asia_infer.junction_tree.factors
Out[7]: 
[<DiscreteFactor representing phi(bronc:2, dysp:2, either:2) at 0x7f3111e5d660>,
 <DiscreteFactor representing phi(lung:2, bronc:2, xray:2, either:2, tub:2) at 0x7f3111e5c040>,
 <DiscreteFactor representing phi(lung:2, bronc:2, asia:2, xray:2, tub:2) at 0x7f3111e5c160>,
 <DiscreteFactor representing phi(lung:2, bronc:2, asia:2, xray:2, smoke:2) at 0x7f3111e5cee0>]

In [8]: asia_infer.junction_tree.factors[0]
Out[8]: <DiscreteFactor representing phi(bronc:2, dysp:2, either:2) at 0x7f3111e5d660>

In [9]: asia_infer.junction_tree.factors[0].state_names
Out[9]: {'bronc': ['yes', 'no'], 'dysp': ['yes', 'no'], 'either': ['yes', 'no']}

In [10]: asia_infer.junction_tree.factors[1].state_names
Out[10]: 
{'bronc': [0, 1],
 'xray': ['yes', 'no'],
 'lung': ['yes', 'no'],
 'either': ['yes', 'no'],
 'tub': ['yes', 'no']}

In [11]: asia_infer.junction_tree.factors[2].state_names
Out[11]: 
{'bronc': [0, 1],
 'xray': [0, 1],
 'lung': [0, 1],
 'asia': ['yes', 'no'],
 'tub': ['yes', 'no']}

In [12]: asia_infer.junction_tree.factors[3].state_names
Out[12]: 
{'bronc': ['yes', 'no'],
 'xray': [0, 1],
 'lung': ['yes', 'no'],
 'asia': [0, 1],
 'smoke': ['yes', 'no']}

```@lalala1139: @ankurankan I also encountered this problem in development. Do you have a solution now?@FSSlijkhuis: I have been able to fix this bug, here's the analysis of the bug and my fix:

First of all, the bug is non-deterministic, sometimes causing queries to fail with `KeyErrors`. This happens when using string-based evidence, such as `{"smoke": "yes"}`. The main issue here is that variable state names are inconsistently transformed between string representations `(["yes", "no"])` and numerical representations `([0, 1])` when constructing a junction tree. The Asia model has string representations of variable state names and calling `BeliefPropagation` with the Asia model causes the junction tree to be constructed.

### Root Cause
The issue originates in MarkovNetwork.to_junction_tree() when creating the initial clique potentials:
```
# Current problematic code in MarkovNetwork.py (lines 573-575)
clique_potential = DiscreteFactor(
    node, var_card, np.ones(np.prod(var_card))
)
```

This creates a `DicreteFactor` object without explicitly providing the `state_names`, which causes the factor to default to numerical state names `([0, 1])`. Later, when this factor is multiplied with original factors that have string-based state names `(["yes", "no"])`, the `add_state_names()` method in `state_name.py` blindly updates dictionaries without checking for conflicts:

```
# Current problematic code in state_name.py
def add_state_names(self, phi1):
    self.state_names.update(phi1.state_names)
    self.name_to_no.update(phi1.name_to_no)
    self.no_to_name.update(phi1.no_to_name)
```

Depending on the dictionary update order, sometimes the string representation wins, and sometimes the numerical representation wins. When the numerical representation wins, queries with string-based evidence (like `{"smoke": "yes"}` and `{"lung": "no"}`) raise a `KeyError`. The dictionary update order is non-deterministic because the order in which factors are multiplied during the construction of the junction tree depends mainly on the traversal order of cliques in the graph and the order in which the factors are matched to these cliques. These traversal orders are influenced by graph traversal algorithms (networkx) and the model structure, which vary between runs. So, even in Python versions where dictionary ordering is deterministic (Python 3.7+), the traversal and update order variability leads to inconsistent behavior. 

### Minimal reproducible example
The following example shows how factors with inconsistent state name representations can cause problems when combined (switching `phi1` and `phi2` does not raise a `KeyError`, whilst the following code does):
```
import numpy as np
from pgmpy.factors.discrete import DiscreteFactor
from pgmpy.factors import factor_product

# Factor 1: String-based state names
phi1 = DiscreteFactor(
    variables=["smoke", "either"],
    cardinality=[2, 2],
    values=np.ones(4),
    state_names={"smoke": ["yes", "no"], "either": ["yes", "no"]}
)

# Factor 2: Numeric state names (simulating what happens in junction tree conversion)
phi2 = DiscreteFactor(
    variables=["smoke", "lung"],
    cardinality=[2, 2],
    values=np.ones(4),
    state_names={"smoke": [0, 1], "lung": ["yes", "no"]}
)

# When multiplied, one will overwrite the other's state names
phi_product = phi1 * phi2
print(f"State names in product: {phi_product.state_names}")

# Try to use the factor with string evidence
# This will sometimes fail depending on which state name representation won
try:
    state_no = phi_product.get_state_no("smoke", "yes")
    print(f"State number for 'yes': {state_no}")
except KeyError:
    print("KeyError: 'yes' not found in state names")
```

### Fix

1. **Root cause fix:** The main fix is in fact quite simple. We can simply fix the source of the issue by ensuring proper `state_names` are passed when creating the clique potentials in `MarkovNetwork.py` (`MarkovNetwork.to_junction_tree()`):
```
# Add this at the beginning of to_junction_tree()
all_state_names = {}
for factor in self.factors:
    all_state_names.update(factor.state_names)

# Then modify the clique_potential declaration:
clique_potential = DiscreteFactor(
    node, 
    var_card, 
    np.ones(np.prod(var_card)),
    state_names={var: all_state_names.get(var, list(range(self.get_cardinality()[var]))) 
                for var in node}
)
```
With this fix, all clique potentials will start with consistent state names from the original model.

2. **Validation fix:** We can also add validation to `add_state_names()` to prevent silent overwriting of conflicting state names in `state_name.py`:
```
def add_state_names(self, phi1):
    """
    Updates the attributes of this class with another factor `phi1`.
    Ensures state name consistency.
    """
    # Check for conflicts
    for var in phi1.state_names:
        if var in self.state_names and self.state_names[var] != phi1.state_names[var]:
            # One has strings and the other has numeric values - prioritize strings
            self_has_strings = any(isinstance(s, str) and not s.isdigit() 
                                for s in self.state_names[var])
            phi1_has_strings = any(isinstance(s, str) and not s.isdigit() 
                               for s in phi1.state_names[var])
            
            # Keep string-based state names over numeric ones
            if self_has_strings and not phi1_has_strings:
                continue  # Keep current string-based state names
            elif not self_has_strings and phi1_has_strings:
                self.state_names[var] = phi1.state_names[var]
                if var in phi1.name_to_no:
                    self.name_to_no[var] = phi1.name_to_no[var]
                if var in phi1.no_to_name:
                    self.no_to_name[var] = phi1.no_to_name[var]
                continue
            # Both are similar type but different - raise error
            else:
                raise ValueError(
                    f"Conflict in state names for variable '{var}': "
                    f"{self.state_names[var]} vs {phi1.state_names[var]}"
                )
    
    # Update state names for non-conflicting variables
    for var in phi1.state_names:
        if var not in self.state_names:
            self.state_names[var] = phi1.state_names[var]
            if var in phi1.name_to_no:
                self.name_to_no[var] = phi1.name_to_no[var]
            if var in phi1.no_to_name:
                self.no_to_name[var] = phi1.no_to_name[var]
```
With this fix, it is ensured that string-based state names are prioritized and therefore preventing silent overwriting of state names.

### Verification
Let's verify that the fixes work. For this, I am using the original script:
```
from pgmpy.inference import BeliefPropagation
from pgmpy.utils import get_example_model

if __name__ == '__main__':
    # Computing the probability of bronc given smoke=no.
    asia_model = get_example_model('asia')
    algo = BeliefPropagation
    asia_infer = algo(asia_model)
    q = asia_infer.query(variables=["bronc", "asia"], evidence={"smoke": "no"})
```

Let's run the original script 20 times and see how often it fails with the original code and with the fixes:
Without the fix:
```
==================================================
EXECUTION SUMMARY:
Script:            reproduction_code.py
Total runs:        20
Elapsed time:      177.17 seconds
--------------------------------------------------
Success:   16/20 (80.0%)
Failed (non-zero exit):   4/20 (20.0%)
==================================================
```

With only the `MarkovNetwork.py` fix:
```
==================================================
EXECUTION SUMMARY:
Script:            reproduction_code.py
Total runs:        20
Elapsed time:      180.54 seconds
--------------------------------------------------
Success:   20/20 (100.0%)
==================================================
```

With only the `state_name.py` fix:
```
==================================================
EXECUTION SUMMARY:
Script:            reproduction_code.py
Total runs:        20
Elapsed time:      179.36 seconds
--------------------------------------------------
Success:   20/20 (100.0%)
==================================================
```

With both the `MarkovNetwork.py` and the `state_name.py` fix:
```
==================================================
EXECUTION SUMMARY:
Script:            reproduction_code.py
Total runs:        20
Elapsed time:      186.25 seconds
--------------------------------------------------
Success:   20/20 (100.0%)
==================================================
```@ankurankan: @FSSlijkhuis Thank you for having a look at the bug and the detailed analysis. If you would like please feel free to create a pull request with your fixes :)@FSSlijkhuis: Hi @ankurankan , I've added a new pull request with the above mentioned fixes. 

Solution patch:
diff --git a/pgmpy/models/MarkovNetwork.py b/pgmpy/models/MarkovNetwork.py
index c6abfc82..57c47abf 100644
--- a/pgmpy/models/MarkovNetwork.py
+++ b/pgmpy/models/MarkovNetwork.py
@@ -519,6 +519,11 @@ class MarkovNetwork(UndirectedGraph):
         """
         from pgmpy.models import JunctionTree
 
+        # Get all the state names of the random variables
+        all_state_names = {}
+        for factor in self.factors:
+            all_state_names.update(factor.state_names)
+
         # Check whether the model is valid or not
         self.check_model()
 
@@ -572,7 +577,15 @@ class MarkovNetwork(UndirectedGraph):
             # To compute clique potential, initially set it as unity factor
             var_card = [self.get_cardinality()[x] for x in node]
             clique_potential = DiscreteFactor(
-                node, var_card, np.ones(np.prod(var_card))
+                node,
+                var_card,
+                np.ones(np.prod(var_card)),
+                state_names={
+                    var: all_state_names.get(
+                        var, list(range(self.get_cardinality()[var]))
+                    )
+                    for var in node
+                },
             )
             # multiply it with the factors associated with the variables present
             # in the clique (or node)
diff --git a/pgmpy/utils/state_name.py b/pgmpy/utils/state_name.py
index 3f782bc5..6a1135ab 100644
--- a/pgmpy/utils/state_name.py
+++ b/pgmpy/utils/state_name.py
@@ -81,15 +81,54 @@ class StateNameMixin:
     def add_state_names(self, phi1):
         """
         Updates the attributes of this class with another factor `phi1`.
+        Ensures state name consistency.
 
         Parameters
         ----------
         phi1: Instance of pgmpy.factors.DiscreteFactor
             The factor whose states and variables need to be added.
         """
-        self.state_names.update(phi1.state_names)
-        self.name_to_no.update(phi1.name_to_no)
-        self.no_to_name.update(phi1.no_to_name)
+        # Process all state names in a single loop
+        for var in phi1.state_names:
+            if var in self.state_names:
+                # Check for conflicts between existing state names
+                if self.state_names[var] != phi1.state_names[var]:
+                    # One has strings and the other has numeric values - prioritize strings
+                    self_has_strings = any(
+                        isinstance(s, str) and not s.isdigit()
+                        for s in self.state_names[var]
+                    )
+                    phi1_has_strings = any(
+                        isinstance(s, str) and not s.isdigit()
+                        for s in phi1.state_names[var]
+                    )
+
+                    # Keep string-based state names over numeric ones
+                    if self_has_strings and not phi1_has_strings:
+                        continue  # Keep current string-based state names
+                    elif not self_has_strings and phi1_has_strings:
+                        self.state_names[var] = phi1.state_names[var]
+                        if var in phi1.name_to_no:
+                            self.name_to_no[var] = phi1.name_to_no[var]
+                        if var in phi1.no_to_name:
+                            self.no_to_name[var] = phi1.no_to_name[var]
+                    else:
+                        # Both have similar types but different values - raise error
+                        raise ValueError(
+                            f"State name conflict detected for variable '{var}'.\n"
+                            f"First factor has states: {self.state_names[var]}\n"
+                            f"Second factor has states: {phi1.state_names[var]}\n"
+                            f"When the same variable appears in multiple factors, "
+                            f"the state names must be identical. Please ensure consistent "
+                            f"state naming across your model."
+                        )
+            else:
+                # No conflict - add the new state names
+                self.state_names[var] = phi1.state_names[var]
+                if var in phi1.name_to_no:
+                    self.name_to_no[var] = phi1.name_to_no[var]
+                if var in phi1.no_to_name:
+                    self.no_to_name[var] = phi1.no_to_name[var]
 
     def del_state_names(self, var_list):
         """


Test patch:
diff --git a/pgmpy/tests/test_models/test_MarkovNetwork.py b/pgmpy/tests/test_models/test_MarkovNetwork.py
index 597bc509..5f9c53d4 100644
--- a/pgmpy/tests/test_models/test_MarkovNetwork.py
+++ b/pgmpy/tests/test_models/test_MarkovNetwork.py
@@ -640,5 +640,56 @@ class TestUndirectedGraphTriangulation(unittest.TestCase):
         self.assertEqual(len(self.graph.get_factors()), 1)
         self.assertEqual(len(copy.get_factors()), 0)
 
+    def test_junction_tree_with_state_names(self):
+        """
+        Test that junction tree correctly maintains state names from the original factors.
+        """
+        self.graph.add_edges_from([("A", "B"), ("B", "C"), ("C", "A")])
+
+        # Create factors with string-based state names
+        state_names = {"A": ["a0", "a1"], "B": ["b0", "b1", "b2"], "C": ["c0", "c1"]}
+
+        phi1 = DiscreteFactor(
+            ["A", "B"],
+            [2, 3],
+            np.random.rand(6),
+            state_names={"A": state_names["A"], "B": state_names["B"]},
+        )
+
+        phi2 = DiscreteFactor(
+            ["B", "C"],
+            [3, 2],
+            np.random.rand(6),
+            state_names={"B": state_names["B"], "C": state_names["C"]},
+        )
+
+        phi3 = DiscreteFactor(
+            ["C", "A"],
+            [2, 2],
+            np.random.rand(4),
+            state_names={"C": state_names["C"], "A": state_names["A"]},
+        )
+
+        self.graph.add_factors(phi1, phi2, phi3)
+
+        # Convert to junction tree
+        junction_tree = self.graph.to_junction_tree()
+
+        # Check that the factors in the junction tree have the correct state names
+        for factor in junction_tree.factors:
+            for var in factor.variables:
+                self.assertEqual(factor.state_names[var], state_names[var])
+
+        # Verify state names were correctly passed to clique potentials
+        for clique_potential in junction_tree.factors:
+            for var in clique_potential.variables:
+                self.assertIn(var, state_names)
+                self.assertEqual(clique_potential.state_names[var], state_names[var])
+
+                # Verify the name_to_no and no_to_name mappings are correct
+                for i, state in enumerate(state_names[var]):
+                    self.assertEqual(clique_potential.name_to_no[var][state], i)
+                    self.assertEqual(clique_potential.no_to_name[var][i], state)
+
     def tearDown(self):
         del self.graph
diff --git a/pgmpy/tests/test_utils/test_state_name.py b/pgmpy/tests/test_utils/test_state_name.py
index 2fb6a8c2..e7d459e6 100644
--- a/pgmpy/tests/test_utils/test_state_name.py
+++ b/pgmpy/tests/test_utils/test_state_name.py
@@ -305,3 +305,50 @@ class StateNameDecorator(unittest.TestCase):
 
         self.assertEqual(inf_op1, req_op1)
         self.assertEqual(inf_op2, req_op2)
+
+    def test_add_state_names(self):
+        # Test string state names taking precedence over numeric ones
+        numeric_states = DiscreteFactor(
+            ["speed"], [3], np.ones(3), state_names={"speed": [0, 1, 2]}
+        )
+        string_states = DiscreteFactor(
+            ["speed"], [3], np.ones(3), state_names={"speed": ["low", "medium", "high"]}
+        )
+
+        # Make a copy to test in both directions
+        numeric_states_copy = DiscreteFactor(
+            ["speed"], [3], np.ones(3), state_names={"speed": [0, 1, 2]}
+        )
+
+        # String states should take precedence
+        numeric_states.add_state_names(string_states)
+        self.assertEqual(numeric_states.state_names["speed"], ["low", "medium", "high"])
+
+        # Test the opposite direction - string states should still take precedence
+        string_states.add_state_names(numeric_states_copy)
+        self.assertEqual(string_states.state_names["speed"], ["low", "medium", "high"])
+
+        # Test conflicting string state names
+        states1 = DiscreteFactor(
+            ["switch"], [2], np.ones(2), state_names={"switch": ["on", "off"]}
+        )
+        states2 = DiscreteFactor(
+            ["switch"], [2], np.ones(2), state_names={"switch": ["high", "low"]}
+        )
+
+        # Should raise a ValueError due to conflict
+        with self.assertRaises(ValueError):
+            states1.add_state_names(states2)
+
+        # Test merging non-conflicting state names for different variables
+        factor1 = DiscreteFactor(
+            ["speed"], [3], np.ones(3), state_names={"speed": ["low", "medium", "high"]}
+        )
+        factor2 = DiscreteFactor(
+            ["switch"], [2], np.ones(2), state_names={"switch": ["on", "off"]}
+        )
+
+        # Should merge without conflict
+        factor1.add_state_names(factor2)
+        self.assertEqual(factor1.state_names["speed"], ["low", "medium", "high"])
+        self.assertEqual(factor1.state_names["switch"], ["on", "off"])