Logical Credal Networks (LCNs) is an expressive probabilistic logic that generalizes prior formalisms that combine logic and probability. Given imprecise information represented by probability bounds and conditional probability bounds on logic formulas, an LCN specifies a set of probability distributions over all its interpretations. LCNs allow propositional logic formulas with few restrictions, e.g., without requiring acyclicity and are endowed with a generalized Markov condition that allows us to identify implicit independence relationships between propositions. The package provides novel exact and approximate inference algorithms for computing posterior probability bounds on given query formulas as well as for generating most probable (partial) explanations of observed evidence in the network.
An LCN program consists of two types of probability-labeled sentences:
where
For example the following two sentences represent a valid LCN program defined
over propositions A, B and C.
0.3 <= P(A) <= 0.5
0.4 <= P(!B or C | A) <= 0.7
The LCN solver requires Python 3.10 or newer together with its dependencies; Python 3.12 is the recommended version. The package is built with the hatchling backend and is installable with the uv toolchain (recommended) or with plain pip.
git clone git@github.com:IBM/LCN.git
cd LCN
uv sync
This creates a virtual environment and installs lcn together with all its dependencies from the locked uv.lock file. Commands can then be run inside the environment with uv run, for example uv run pytest tests/.
Alternatively, create a conda environment with the recommended Python 3.12 and install the package in editable mode:
git clone git@github.com:IBM/LCN.git
cd LCN
conda create -n lcn python=3.12
conda activate lcn
pip install -e .
The LCN inference algorithms require the non-linear solver ipopt. To install
the solver, follow the instructions below for Linux and MacOS. Unfortunately,
the LCN package is currently not supported on Windows systems.
To install the ipopt solver on Linux, you can use the coinbrew tool. Simply download the coinbrew script from https://coin-or.github.io/coinbrew/ (make sure to also run chmod u+x coinbrew). coinbrew automates the download of the source code for ASL, MUMPS, and Ipopt and the sequential build and installation of these three packages. The
Linux installation requires the following dependencies before running the coinbrew tool.
- Ubuntu:
sudo apt-get install gcc g++ gfortran git cmake liblapack-dev pkg-config --install-recommends - Fedora:
sudo yum install gcc gcc-c++ gcc-gfortran git cmake lapack-devel
After obtaining the coinbrew script, run:
/path/to/coinbrew fetch Ipopt --no-prompt
/path/to/coinbrew build Ipopt --prefix=/dir/to/install --test --no-prompt --verbosity=3
/path/to/coinbrew install Ipopt --no-prompt
Also, add the following to your .bashrc file:
export LD_LIBRARY_PATH=/dir/to/install/lib
export PATH="/dir/to/install/bin:$PATH"
Install ipopt on MacOS is straightforward by just running brew install ipopt.
A subset of the inference engines can optionally use the SCIP spatial branch-and-bound solver to compute globally certified probability bounds (as opposed to the local bounds returned by ipopt). SCIP is used by:
- the exact marginal inference engine
ExactInferencewhen called withsolver="global"(see below); - the credal-network factorization pipeline
CredalNetworkVertices.from_lcn(..., solver="scip"); - the cross-check verifier
lcn.inference.marginal.verify_scip.
SCIP is not required for the default (ipopt-bas
10BC8
ed) inference. If you do not install it, simply leave the SCIP-related options at their defaults.
In all cases the LCN package drives SCIP through Pyomo's AMPL/NL interface (SolverFactory('scip')), so all that is required is that the scip command-line binary is on your PATH. The local install used during development is SCIP 10.0.2.
brew install scip
The easiest option is a conda environment:
conda install -c conda-forge scip
Alternatively, download one of the official precompiled installers (the SCIPOptSuite-*-Linux.sh script) or the source archive from https://www.scipopt.org/ and follow the bundled instructions. After installing, make sure the scip binary is reachable on your PATH, for example:
export PATH="/path/to/scip/bin:$PATH"
You can confirm that SCIP is visible to the package by running scip --version in the same shell.
The LCN package supports the following basic syntax for LCN programs. An LCN program can be easily specified in a .lcn file.
-
An LCN proposition can be specified by any string as long as it starts with a letter and does not contain spaces. For example
A,x1orAbc12are valid LCN propositions. -
An LCN formula can be specified by a set of propositions connected by logical connectors. The following connectors can be used:
and,or,xor,nand, andnot. The connectors can be specified by the following char symbols:&,|,^,/and!, respectively. In addition, it is possible to use paranthesis()for a more readable formula. Furthermore, for increased readability we recommend using the long form logical connectors instead of their short form counterparts (i.e., useandinstead of&).
The two types of LCN sentences can be specified as follows:
label: lb <= P(formula) <= ub
label: lb <= P(formula | formula) <= ub
where label is any string that starts with a letter and does not contain spaces. Note that each LCN sentence must have a unique label.
The LCN below encodes the following simple example: Bronchitis (B) is more likely than Smoking (S); Smoking may cause Cancer (C) or Bronchitis; Dyspnea (D) or shortness of breadth is a common symptom for Cancer and Bronchitis; in case of Cancer we have either a positive X-Ray result (X) and Dyspnea, or a negative X-Ray and no Dyspnea.
# This line is a comment
# ... and so is this line :)
s1: 0.05 <= P(B) <= 0.1
s2: 0.3 <= P(S) <= 0.4
s3: 0.1 <= P((B or C) | S) <= 0.2
s4: 0.6 <= P(D | B and C) <= 0.7
s5: 0.7 <= P(!(X xor D) | C) <= 0.8
The folder examples contains additional LCN examples specified in the .lcn
file format described above.
Given an LCN file and a query formula ExactInference class (located in the lcn.inference.marginal.exact module) and can be used to compute the probability bounds on the query formula.
ExactInference exposes two solver backends through the solver= argument of its run() method:
solver="local"(default) —ipoptbacked by a two-phase SLSQP fallback. The underlying marginal NLP is nonconvex (conditional-probability ratios plus quadratic Local Markov Condition equalities), so this is a local method and the returned bounds may be loose.solver="global"— the optional SCIP spatial branch-and-bound solver, which either certifies the global optimum or, on a time-out, returns the best bound found together with the optimality gap. This requires the SCIP binary onPATH(see the installation section above). After a global run, the per-atom verdicts are available inalgo.status.
Both backends share the same controls: a per-solve time_limit (seconds), a lightning speed preset, a progress_bar toggle, and a verbosity level (2 streams the solver log). The accuracy mode ("slow" / "fast") applies to the local backend only.
We give next a small example using the default local solver:
ExactInference.run() computes the posterior lower/upper bounds for all singleton variables at once (optionally conditioned on evidence) and returns a dictionary mapping each variable to its (lower, upper) bound arrays [P(=0), P(=1)].
from lcn.core.model import LCN
from lcn.inference.marginal.exact import ExactInference
# Specify the LCN program
file_name = "examples/asia.lcn"
# Create the LCN instance from the .lcn file
l = LCN()
l.from_lcn(file_name)
# Run exact marginal inference (local solver, no evidence)
algo = ExactInference(lcn=l)
results = algo.run(evidence={}, verbosity=1, solver="local", mode="slow")
# Inspect the bounds for a particular variable
lo, hi = results["B"]
print(f"P(B=1) in [{lo[1]:.6f}, {hi[1]:.6f}]")To condition on observed truth values, pass them in evidence, e.g. algo.run(evidence={"S": 1}). To request globally certified bounds via SCIP, pass solver="global" (see the SCIP installation section above).
The output of the exact algorithm is shown below:
Parsed LCN format with 5 sentences.
Build the LCN's primal graph.
Build the LCN's structure graph.
Build the LCN's independence assumptions (LMC).
[ExactInference] Computing all marginals (solver=local)
[ExactInference] Evidence: {}
[ExactInference] Local Markov Condition: 4 independencies
[ExactInference] Singleton variable marginals:
P(B=0): [0.900036, 0.919595]
P(B=1): [0.080405, 0.099964]
P(C=0): [0.729078, 1.000000]
P(C=1): [0.000000, 0.270922]
P(D=0): [0.000000, 1.000000]
P(D=1): [0.000000, 1.000000]
P(S=0): [0.600119, 0.645158]
P(S=1): [0.354842, 0.399881]
P(X=0): [0.000000, 1.000000]
P(X=1): [0.000000, 1.000000]
[ExactInference] Feasible: True
[ExactInference] Atoms solved: 5 | SLSQP fallback used: 5 | infeasible: 0 | vacuous: 2
[ExactInference] Time elapsed: 40.4743 sec
P(B=1) in [0.080405, 0.099964]
For approximate marginal inference, we can use the ARIEL message-passing scheme implemented in the ArielInference class available in the lcn.inference.marginal.ariel module. The algorithm computes approximate lower and upper probability bounds on the posterior probability of the LCN's propositions. As before, we can use the following example:
from lcn.core.model import LCN
from lcn.inference.marginal.ariel import ArielInference
# Specify the LCN program
file_name = "examples/asia.lcn"
# Create the LCN instance from the .lcn file
l = LCN()
l.from_lcn(file_name)
# Run approximate marginal inference
algo = ArielInference(l)
algo.run(n_iters=10, threshold=0.000001, debug=False)The output of the approximate inference algorithm is shown below:
Parsed LCN format with 5 sentences.
Build the LCN's primal graph.
Build the LCN's structure graph.
Build the LCN's independence assumptions (LMC).
LCN
s2: 0.05 <= P(B) <= 0.1
s3: 0.3 <= P(S) <= 0.4
s4: 0.1 <= P((B or C) | S) <= 0.2
s5: 0.6 <= P(D | B and C) <= 0.7
s6: 0.7 <= P(!(X xor D) | C) <= 0.8
Local Markov Condition yields 2 independencies.
independence: (D ⟂ S | B, X, C)
independence: (X ⟂ S, B | D, C)
Solver status: ok
[Ipopt] objective=1.0, optimal=True
CONSISTENT
[ApproximateInference] Running marginal inference...
Iteration 0 ...
### Variable to factor messages ###
### Factor to variable messages ###
After iteration 0 average change in messages is 0.1156250431563193
Elapsed time per iteration: 0.3842339515686035 sec
Iteration 1 ...
### Variable to factor messages ###
### Factor to variable messages ###
After iteration 1 average change in messages is 0.06238024828227323
Elapsed time per iteration: 0.36359095573425293 sec
Iteration 2 ...
### Variable to factor messages ###
### Factor to variable messages ###
After iteration 2 average change in messages is 0.003005215647402235
Elapsed time per iteration: 0.37595176696777344 sec
Iteration 3 ...
### Variable to factor messages ###
### Factor to variable messages ###
After iteration 3 average change in messages is 5.561350752403057e-11
Elapsed time per iteration: 0.3729119300842285 sec
Converged after 3 iterations with delta=5.561350752403057e-11
[ApproximateInference] Marginals:
B: [0.04999999249186405, 0.10000000738802459]
S: [0.29999999253112253, 0.400000007458209]
C: [7.203050475106924e-08, 0.9541665925512998]
D: [0.0015000852157267832, 0.9992499145950501]
X: [6.919372188563531e-08, 0.9999999356848208]
[ApproximateInference] Time elapsed: 1.4968690872192383 sec
In addition to ARIEL, the package provides a family of marginal inference algorithms that operate on the chain-graph factorization of an LCN by first compiling it into a credal network and then enumerating the extreme points of its local credal sets. These algorithms live in the lcn.inference.marginal.cn package.
The chain-graph factorization pipeline is split into focused, decoupled stages (all of the core stages are free of any pyAgrum coupling):
ChainGraphFactorization(cn.factorization) — the purely symbolic factorization. For each family of the chain graph it records the child, its parents and the constraining LCN sentences, but computes no probabilities.LocalCredalSetSolver(cn.local_credal_sets) — solves the per-family optimization problem to obtain the lower/upper bounds of each local credal set. Two factorizationmethods are supported:"linear"(each family solved in isolation as an LP / linear-fractional program) and"nlp"(additionally imposing pairwise marginal independence between parents, which makes the program nonconvex).CredalNetwork(cn.credal_network) — pairs the directed chain graph with the interval local credal sets produced by the solver above. Pure data, nopyAgrum.CredalNetworkVertices(cn.vertices) — builds thepyAgrumcredal net and enumerates the extreme points (vertices) of every local credal set. This is the common input consumed by all of the inference algorithms below.Potentialandmin_fill_order(cn.potentials) — shared data structures and the elimination-ordering heuristic used by the elimination-based engines.
The inference algorithms themselves all consume a built CredalNetworkVertices:
CredalVE(cn.cve) — Credal Variable Elimination (the exact engine over the extreme points).IntervalBP(cn.ibp) — Interval Belief Propagation.CredalIJGP(cn.ijgp) — Interval Iterative Join-Graph Propagation.CredalCTE(cn.ccte) — Credal Cluster Tree Elimination.ApproxLP(cn.approxlp) — ApproxLP iterative linearization.
The typical workflow is to build the CredalNetworkVertices once with CredalNetworkVertices.from_lcn(...) (which runs the whole factorization + enumeration pipeline) and then pass it to one or more algorithms. For example, using Interval Belief Propagation:
from lcn.core.model import LCN
from lcn.inference.marginal.cn.vertices import CredalNetworkVertices
from lcn.inference.marginal.cn.ibp import IntervalBP
# Create the LCN instance from the .lcn file
l = LCN()
l.from_lcn("examples/asia.lcn")
# Build the credal network and enumerate the extreme points of the
# local credal sets (the shared input for all cn algorithms).
# method="linear"|"nlp"; solver="ipopt" (default) or "scip" (global).
cnv = CredalNetworkVertices.from_lcn(l, method="linear", solver="ipopt")
# Run Interval Belief Propagation over the credal network
algo = IntervalBP(cnv=cnv)
marginals = algo.run(evidence={}, n_iters=100, threshold=1e-6)The other algorithms follow the same pattern — CredalVE(cnv=cnv), CredalIJGP(cnv=cnv), CredalCTE(cnv=cnv), ApproxLP(cnv=cnv) — each with its own run() parameters.
These algorithms are also exposed end-to-end through the experiment driver in experiments/run_algorithm.py, which can run any of them on the benchmark instances under benchmarks/.
In addition to marginal inference, the LCN package implements exact and approximate algorithms for computing complete or partial most probable explanations of evidence (i.e., observed truth values of a set of propositions) in a given LCN. The algorithms are based on depth-first search, limited discrepancy search or simulated annealing. We also provide an extension called AMAP of the ARIEL scheme for computing MAP and Marginal MAP explanations.
For exact MAP/MMAP inference, we can use the following example:
from lcn.core.model import LCN
from lcn.inference.map.exact_map import ExactMAPInference
# Specify the LCN program
file_name = "examples/asia.lcn"
# Create the LCN instance from the .lcn file
l = LCN()
l.from_lcn(file_name)
evidence = {'D': 1, 'X': 0, 'S': 1}
query = ['B', 'C']
# Run exact MAP inference
algo = ExactMAPInference(
lcn=l,
method="maximin",
eps=0.,
max_discrepancy=3,
num_iterations=5,
max_flips=10
)
algo.run(algo="dfs", query=query, evidence=evidence)The solver supports the following search strategies to traverse the search space defined by the MAP propositions. These options can be passed to the algo= argument of the run() method. In addition, the ExactMAPInference class allows initializing the parameters of these algorithms, especially the maximum discrepancy value used by limited discrepancy search, as well as the initial temperature, cooling schedule, number of iterarations and maximum number of flips allowed per iteration for simulated annealing, respectively.
dfs- Depth-First Searchlds- Limited Discrepancy Searchsa- Simulated Annealing
The output of the exact MAP inference algorithm is the following:
Parsed LCN format with 5 sentences.
Build the LCN's primal graph.
Build the LCN's structure graph.
Build the LCN's independence assumptions (LMC).
LCN
s2: 0.05 <= P(B) <= 0.1
s3: 0.3 <= P(S) <= 0.4
s4: 0.1 <= P((B or C) | S) <= 0.2
s5: 0.6 <= P(D | B and C) <= 0.7
s6: 0.7 <= P(!(X xor D) | C) <= 0.8
Local Markov Condition yields 2 independencies.
independence: (D ⟂ S | X, B, C)
independence: (X ⟂ S, B | D, C)
Solver status: ok
[Ipopt] objective=1.0, optimal=True
CONSISTENT
[DFS] Searching over MAP variables: ['B', 'C']
[DFS] Query: MMAP
[DFS] MAP method: maximin
[DFS] Start search...
interpretation: [1, 1] bounds: [(9.95999416335017e-09, 0.05600005199307257)]
interpretation: [1, 0] bounds: [(9.989995877191735e-09, 0.08000006834240411)]
interpretation: [0, 1] bounds: [(1.0749823917382889e-10, 0.03085707335332656)]
interpretation: [0, 0] bounds: [(3.7193155332895576e-14, 0.3600000383341209)]
[DFS] Search terminated successfully.
[DFS] Time elapsed (sec): 0.986320972442627
[DFS] Search timeout: False
[DFS] MAXIMIN-MAP score: 9.989995877191735e-09
[DFS] MAXIMIN-MAP solution: {'B': 1, 'C': 0, 'D': 1, 'X': 0, 'S': 1}
For approximate MAP/MMAP inference, we can use the following example:
from lcn.core.model import LCN
from lcn.inference.map.approx_map import ApproximateMAPInference
# Specify the LCN program
file_name = "examples/asia.lcn"
# Create the LCN instance from the .lcn file
l = LCN()
l.from_lcn(file_name)
evidence = {'D': 1, 'X': 0, 'S': 1}
query = ['B', 'C']
# Run approximate MAP inference
algo = ApproximateMAPInference(
lcn=l,
method="maximax",
eps=0.,
max_discrepancy=3,
ariel_threshold=0.000001,
ariel_iterations=5,
num_iterations=5,
max_flips=10,
eval_iterations=5,
eval_threshold=0.00001,
)
algo.run(algo="ariel", query=query, evidence=evidence)In this case, the selected approximate MAP inference algorithm is the AMAP message-passing scheme (based on ARIEL for approximate marginal inference). The ApproximateMAPInference class allows initializing the parameters of the MAP inference algorithms. In addition to the ARIEL scheme for MAP, the solver supports two additional search algorithms based on limited discrepancy search and simulated annealing, respectively. Therefore, the possible options for the algo= argument of the run() method are the following:
ariel- the AMAP message-passing scheme based on ARIEL for marginal inferencealds- Limited Discrepancy Search with approximate evaluation of MAP configurationsasa- Simulated Annealing with approximate evaluation of MAP configurations
The output of the selected algorithm (ariel) is the following:
Parsed LCN format with 5 sentences.
Build the LCN's primal graph.
Build the LCN's structure graph.
Build the LCN's independence assumptions (LMC).
LCN
s2: 0.05 <= P(B) <= 0.1
s3: 0.3 <= P(S) <= 0.4
s4: 0.1 <= P((B or C) | S) <= 0.2
s5: 0.6 <= P(D | B and C) <= 0.7
s6: 0.7 <= P(!(X xor D) | C) <= 0.8
Local Markov Condition yields 2 independencies.
independence: (D ⟂ S | C, B, X)
independence: (X ⟂ B, S | C, D)
Solver status: ok
[Ipopt] objective=1.0, optimal=True
CONSISTENT
[ARIEL] Running marginal inference...
[ARIEL] MAP variables: ['B', 'C']
[ARIEL] Query: MMAP
Iteration 0 ...
### Variable to factor messages ###
### Factor to variable messages ###
[ARIEL] After iteration 0 average change in messages is 0.19750003399076127
[ARIEL] Elapsed time per iteration: 0.5284631252288818 sec
Iteration 1 ...
### Variable to factor messages ###
### Factor to variable messages ###
[ARIEL] After iteration 1 average change in messages is 0.21940529895579672
[ARIEL] Elapsed time per iteration: 0.5052711963653564 sec
Iteration 2 ...
### Variable to factor messages ###
### Factor to variable messages ###
[ARIEL] After iteration 2 average change in messages is 0.021905252501707433
[ARIEL] Elapsed time per iteration: 0.49897289276123047 sec
Iteration 3 ...
### Variable to factor messages ###
### Factor to variable messages ###
[ARIEL] After iteration 3 average change in messages is 2.830615592529453e-10
[ARIEL] Elapsed time per iteration: 0.499556303024292 sec
[ARIEL] Converged after 3 iterations with delta=2.830615592529453e-10
[ARIEL] Marginals:
B: [0.04999999249186405, 0.10000000738802459]
S: [0.9999999914623433, 1.0]
C: [2.139483013933878e-08, 0.5618949748067975]
D: [0.9999999914623433, 0.999999856035422]
X: [5.028558867647727e-08, 8.537656733267566e-09]
[ARIEL] Time elapsed (sec): 2.0327508449554443
[ARIEL] MAXIMAX-MAP score: 0.5057054731748238
[ARIEL] MAXIMAX-MAP solution: {'B': 0, 'C': 1, 'D': 1, 'X': 0, 'S': 1}
If you found the LCN package useful, please cite the following papers:
@inproceedings{ lcn2022neurips,
title={ Logical Credal Networks },
author={ Marinescu, Radu and Qian, Haifeng and Gray, Alexander and Bhattacharjya, Debarun and Barahona, Francisco and Gao, Tian and Riegel, Ryan and Sahu, Pravinda },
year={ 2022 },
booktitle = { Thirty-Seventh Annual Conference on Neural Information Processing Systems (NeurIPS) },
url= {https://proceedings.neurips.cc/paper_files/paper/2022/file/62891522c00cf7323cbacb500e6cfc8d-Paper-Conference.pdf}
}
@inproceedings{ lcn2023ijcai,
title={ Approximate Inference in Logical Credal Networks },
author={ Marinescu, Radu and Qian, Haifeng and Gray, Alexander and Bhattacharjya, Debarun and Barahona, Francisco and Gao, Tian and Riegel, Ryan },
year={ 2023 },
booktitle = { Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI) },
url= {https://proceedings.neurips.cc/paper_files/paper/2022/file/62891522c00cf7323cbacb500e6cfc8d-Paper-Conference.pdf}
}
@article{ lcn2024ijar,
title = {Markov Conditions and Factorization in Logical Credal Networks},
journal = {International Journal of Approximate Reasoning},
volume = {172},
pages = {109237},
year = {2024},
doi = {https://doi.org/10.1016/j.ijar.2024.109237},
url = {https://www.sciencedirect.com/science/article/pii/S0888613X24001245},
author = {Fabio G. Cozman and Radu Marinescu and Junkyu Lee and Alexander Gray and Ryan Riegel and Debarun Bhattacharjya}
}
@inproceedings{ lcn2024neurips,
title={ Abductive Reasoning in Logical Credal Networks },
author={ Marinescu, Radu and Lee, Junkyu and Bhattacharjya, Debarun and Cozman, Fabio and Gray, Alexander },
year={ 2024 },
booktitle = { Thirty-Eighth Annual Conference on Neural Information Processing Systems (NeurIPS) },
}
Radu Marinescu (radu.marinescu at ie dot ibm dot com)