\pdfoutput=1
\documentclass[11pt]{article}
\usepackage{times}
\usepackage{latexsym}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{microtype}
\usepackage{inconsolata}
\usepackage{bussproofs}
\usepackage{amsmath}
\usepackage{amssymb, mathrsfs}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{subcaption}
\usepackage{tikz-dependency}
\usepackage{hyperref}
\pgfplotsset{compat=1.17}
\usetikzlibrary{positioning}
\newcommand{\singleprop}{s_{p}}
\newcommand{\singlepred}{s_{q}}
\newcommand{\grouppred}{g_{q}}
\newcommand{\groupprop}{g_{p}}
\newcommand{\inference}{\ell_{gsr}}
\newcommand{\singlepropi}[1]{s_{p,#1}}
\newcommand{\implicationpred}{(g_p, s_p, (r_g, r_p))}
\newcommand{\backlinks}{B_\Psi}
\newcommand{\forwardlinks}{\textsc{forward}_\Phi}
\newcommand{\propgraph}{\Phi}
\newcommand{\propgraphs}{\Phi(\singleprop)}
\newcommand{\fnname}{\mathscr{F}}
\newcommand{\argset}{\mathcal{A}}
\newcommand{\argmap}{\left\{(r, a)\right\}}
\newcommand{\andsign}{\textbf{\em and}}
\newcommand{\orsign}{\textsc{Or}}
\newcommand{\constant}[1]{{\bf c}_{#1}}
\newcommand{\variable}[1]{{\bf x}_{#1}}
\newcommand{\type}[1]{\tau_{#1}}
\newcommand{\xvariable}{{\bf x}}
\newcommand{\rvariable}{{\bf r}}
\newcommand{\zvariable}{{\bf z}}
\newcommand{\cvariable}{{\bf c}}
\newcommand{\avariable}{{\bf a}}
\newcommand{\yvariable}{{\bf y}}
\newcommand{\svariable}{{\bf s}}
\newcommand{\pconstant}{{\bf p}}
\newcommand{\pvariable}{{\bf p}}
\newcommand{\nvariable}{{\bf n}}
\newcommand{\pvariableset}{\left\{\pvariable\right\}}
\newcommand{\qvariable}{{\bf q}}
\newcommand{\gvariable}{{\bf g}}
\newcommand{\hvariable}{{\bf h}}
\newcommand{\wvariable}{{\bf w}}
\newcommand{\mvariable}{{\bf m}}
\newcommand{\condsep}{\ |\ }
\newcommand{\varmask}{\textsc{mask}}
\newcommand{\roleset}{\left\{r_s\right\}}
\newcommand{\rolemap}{\left\{r_{\qvariable_a}, r_{\qvariable_c}\right\}}
\newcommand{\xjack}{\xvariable_{jack}}
\newcommand{\xjill}{\xvariable_{jill}}
\newcommand{\opand}{\textbf{\em and}}
\newcommand{\opor}{\textbf{\em or}}
\newcommand{\opxor}{\textbf{\em xor}}
\newcommand{\psiand}{\Psi_\opand}
\newcommand{\psior}{\Psi_\opor}
\newcommand{\subj}{\textsc{subj}}
\newcommand{\dobj}{\textsc{dobj}}
\newcommand{\iobj}{\textsc{iobj}}

\title{\bf The Quantified Boolean Bayesian Network \\ 
\vspace{10pt}
 \Large \textmd{Experiments with a Logical Graphical Model}
\vspace{25pt}
}
\author{
    {\Large Greg Coppola}
    \\
    {\em coppola.ai} \\
    Research. Develop. Meme.
}
\date{February 11, 2024}
\begin{document}
\maketitle
\tableofcontents
% sections
\section{Introduction}
In \cite{Coppola2024Logical} we describe the {\em Quantified Boolean Bayesian Network}, which is a \emph{Bayesian Network}, 
in which every node is a \emph{proposition}, indexed by a \emph{sentence} in a \emph{key-value first-order logical language}, which has a \emph{boolean truth value} and a \emph{probability estimate}.
The Bayesian Network is formulated to have a \emph{logical structure}, which mimics the form of proof structures in the \emph{natural deduction logic}, so we can show in \cite{Coppola2024Thinking}, how the \emph{inferences} in the \emph{QBBN} relate to those that would be needed for a \emph{complete} and \emph{consistent} first-order calculus along the lines of \cite{Prawitz1965}. 
The motivation for the \emph{QBBN} is that it provides a \emph{generative model} of (the \emph{logical forms} underlying) natural language, that \emph{does not hallucinate}, unlike the \emph{large language model} \cite{radford2018improving}.
Due to limitations of space in \cite{Coppola2024Logical}, we were not yet able to present the experimental results, which we do here, keeping the same notation as there.
\section{Experiments}
\label{sec:experiments}
In general, in a Bayesian Network, inference is $\Omega(2^N)$ for a graph with $N$ variables to compute {\em exactly}, or even to {\em provably approximate} \cite{Cooper1990,Roth1996HardnessApproxReasoning}.
We implement the {\em loopy} variant of \cite{pearl1988probabilistic}'s {\em belief propagation} algorithm presented in \cite{neapolitan2003learning}.
Previous research has suggested this algorithm {\em does} converge well empirically, even though there are no theoretical guarantees \cite{murphy1999loopy, Smith2008}.
\subsection{Logical Structures}
\subsubsection{Method}
\paragraph{Synthetic Data}
We train the model with synthetic data, {\em assuming that all variables are observed during training}.
Our goal is to show that the {\em QBBN} can {\em learn} the model, and to investigate {\em inference} using {\em iterative belief propagation}.
\paragraph{Example Universe}
We investigate the problem of of our running example in which there are two variables from a bipartite set, $\xjack$ and $\xjill$, and we are interested whether $date(\xjack, \xjill)$.
% let p_jack_lonely = weighted_cointoss(0.3f64);
% let p_jill_exciting: f64 = weighted_cointoss(0.6f64);
% let p_jill_likes_jack: f64 = weighted_cointoss(0.4f64);
This is the problem discussed in  Section {\em 3.3.2} of \cite{Coppola2024Logical}, and the graphical model for our {\em theory} of this universe is depicted in Figure {\em 2} of the same.
For any $\xjack$, $lonely(\xjack) = 1$ with probability $30\%$.
For any $\xjill$, $exciting(\xjill) = 1$ with probability $60\%$.
For any $\xjack, \xjill$, $like(\xjack, \xjill)$ iff $lonely(\xjack) \lor exciting(\xjill)$.
For any $\xjill, \xjack$, $like(\xjill, \xjack) = 1$ with probability $40\%$.
For any $\xjack, \xjill$, $date(\xjack, \xjill)$ iff $like(\xjack, \xjill)$ {\em and} $like(\xjill, \xjack)$.
\paragraph{Training}
We train on 4096 randomly generated synthetic examples, in which {\em we assume that all variables are observed} for all training examples.
We use a very basic {\em stochastic gradient descent} implementation, in which the learning rate is fixed, without averaging.
There is some random error in this simplistic estimate but these experiments are primarily to check the behavior of {\em iterative belief propagation}.
\paragraph{Belief Propagation Convergence}
In each case we: 1) set some evidence (possibly nothing), 2) do $x$ rounds of {\em iterative belief propagation}, where the number of rounds is plotted on the {\em x-axis} in line graphs.
In all line graphs, iteration $0$ shows the prior probability, after which we either {\em set an observed variable} or {\em do nothing}.
If we set an observed variable, we then do {\em fan out} message passing from the observed variable, which involves doing {\em lambda} backward message passing up the graph from the changed node first, and then {\em pi} forward message passing back down the graph from the roots, with each fan out counting as one iteration.
In this case, we see how the graph changes over iterations.
If we did not set an observed variable, then we just do rounds of full {\em forward}-{\em backward} passes, to observe that the network does not change without new information.

\subsubsection{Results}
\label{sec:results}
\paragraph{No Evidence}
First, we investigate inference in the model for an example in which none of the variables are set.
Figure \ref{fig:prior} shows the baseline probabilities in the model, that match the by-hand calculations we can do to verify, with some noise due to the unsophisticated gradient descent.
$P(like(\xjack, \xjill))$ is a {\em noisy or} over $P(lonely(\xjack)) = 0.3$ and $exciting(\xjill) = 0.6$ so 
\[ P(like(\xjack, \xjill) = 1) = 1 - (1 - 0.3)(1 - 0.6) = 0.72 \]
In the network this is estimates as $0.78$, which we believe is due to the noise of the gradient descent.
$P(like(\xjack, \xjill))$ and $P(like(\xjill, \xjack))$ are {\em independent} (even in the underlying universe) so: 
\[ P(like(\xjack, \xjill) \land like(\xjill, \xjack))  = P(like(\xjack, \xjill))\cdot P(like(\xjill, \xjack)) \]
This is $0.72 \cdot 0.4 =  0.29$, while the network the estimate is $0.31$.
We reiterate that we are primarily interested in the {\em message passing} in these experiments, and there are many well understood ways to improve the {\em SGD} estimate.
\begin{figure}[htp]
    \centering
    \begin{tikzpicture}
        \begin{axis}[
            xlabel={Iteration},
            ylabel={Marginal},
            xmin=0, xmax=4,
            ymin=0, ymax=1,
            xtick={0, 1, 2, 3, 4},
            ytick={0,0.2,0.4,0.6,0.8,1},
            legend pos=south east,
            ymajorgrids=true,
            grid style=dashed,
        ]
    
    
        \addplot[
            color=red,
            mark=triangle,
            ]
            coordinates {
            (0,0.4873317609864634)(1,0.4873317609864634)(2,0.4873317609864634)(3,0.4873317609864634)(4,0.4873317609864634)
            };
        \addlegendentry{lonely boy}
    
        \addplot[
            color=green,
            mark=square,
            ]
            coordinates {
            (0,0.5788081540215597)(1,0.5788081540215597)(2,0.5788081540215597)(3,0.5788081540215597)(4,0.5788081540215597)
            };
        \addlegendentry{exciting girl}
    
        \addplot[
            color=blue,
            mark=o,
            ]
            coordinates {
            (0,0.40228172141434443)(1,0.40228172141434443)(2,0.40228172141434443)(3,0.40228172141434443)(4,0.40228172141434443)
            };
        \addlegendentry{girl likes boy}
    
        \addplot[
            color=yellow,
            mark=triangle,
            ]
            coordinates {
            (0,0.781886931114863)(1,0.781886931114863)(2,0.781886931114863)(3,0.781886931114863)(4,0.781886931114863)
            };
        \addlegendentry{boy likes girl}
    
        \addplot[
            color=orange,
            mark=square,
            ]
            coordinates {
            (0,0.3143437719355474)(1,0.3143437719355474)(2,0.3143437719355474)(3,0.3143437719355474)(4,0.3143437719355474)
            };
        \addlegendentry{boy dates girl}
    
    
        \end{axis}
    \end{tikzpicture}
    
    \caption{The {\em prior} state of the network, with no {\em observations}.}
    \label{fig:prior}
\end{figure}

\paragraph{Forward Only}
In Figure \ref{fig:jill_likes}, we assume that $like(\xjill, \xjack) = 1$, which affects $P(date(\xjack, \xjill))$, but not $P(like(\xjack, \xjill))$, which is independent, and those so are its ancestors.
\begin{figure}[htp]
    \centering
    \begin{tikzpicture}
        \begin{axis}[
            xlabel={Iteration},
            ylabel={Marginal},
            xmin=0, xmax=4,
            ymin=0, ymax=1,
            xtick={0, 1, 2, 3, 4},
            ytick={0,0.2,0.4,0.6,0.8,1},
            legend pos=south east,
            ymajorgrids=true,
            grid style=dashed,
        ]
    
    
        \addplot[
            color=red,
            mark=triangle,
            ]
            coordinates {
            (0,0.4873317609864634)(1,0.4873317609864634)(2,0.4873317609864634)(3,0.4873317609864634)(4,0.4873317609864634)
            };
        \addlegendentry{lonely boy}
    
        \addplot[
            color=green,
            mark=square,
            ]
            coordinates {
            (0,0.5788081540215597)(1,0.5788081540215597)(2,0.5788081540215597)(3,0.5788081540215597)(4,0.5788081540215597)
            };
        \addlegendentry{exciting girl}
    
        \addplot[
            color=blue,
            mark=o,
            ]
            coordinates {
            (0,0.40228172141434443)(1,1.0)(2,1.0)(3,1.0)(4,1.0)
            };
        \addlegendentry{girl likes boy}
    
        \addplot[
            color=yellow,
            mark=triangle,
            ]
            coordinates {
            (0,0.781886931114863)(1,0.781886931114863)(2,0.781886931114863)(3,0.781886931114863)(4,0.781886931114863)
            };
        \addlegendentry{boy likes girl}
    
        \addplot[
            color=orange,
            mark=square,
            ]
            coordinates {
            (0,0.3143437719355474)(1,0.7788513434668671)(2,0.7788513434668671)(3,0.7788513434668671)(4,0.7788513434668671)
            };
        \addlegendentry{boy dates girl}
    
    
        \end{axis}
    \end{tikzpicture}
    
    \caption{Assume that $like(\xjill, \xjack) = 1$. Forward inferences only.}
    \label{fig:jill_likes}
\end{figure}
\paragraph{Forward and Backward}
In Figure \ref{fig:jack_likes}, we assume that $like(\xjack, \xjill) = 1$, which affects both its parents and its children (which includes many variables), but not $like(\xjill, \xjack)$, which is independent.
\begin{figure}[htp]
    \centering
    \begin{tikzpicture}
        \begin{axis}[
            xlabel={Iteration},
            ylabel={Marginal},
            xmin=0, xmax=6,
            ymin=0, ymax=1,
            xtick={0, 1, 2, 3, 4, 5, 6},
            ytick={0,0.2,0.4,0.6,0.8,1},
            legend pos=south east,
            ymajorgrids=true,
            grid style=dashed,
        ]
    
    
        \addplot[
            color=red,
            mark=triangle,
            ]
            coordinates {
            (0,0.19468823836358745)(1,0.19468823836358745)(2,0.2483348932542051)(3,0.2483348932542051)(4,0.2483348932542051)(5,0.2483348932542051)(6,0.2483348932542051)
            };
        \addlegendentry{lonely boy}
    
        \addplot[
            color=green,
            mark=square,
            ]
            coordinates {
            (0,0.7297005266779936)(1,0.7297005266779936)(2,0.9312675861052514)(3,0.9312675861052514)(4,0.9312675861052514)(5,0.9312675861052514)(6,0.9312675861052514)
            };
        \addlegendentry{exciting girl}
    
        \addplot[
            color=blue,
            mark=o,
            ]
            coordinates {
            (0,0.36940392473312644)(1,0.36940392473312644)(2,0.36940392473312644)(3,0.36940392473312644)(4,0.36940392473312644)(5,0.36940392473312644)(6,0.36940392473312644)
            };
        \addlegendentry{girl likes boy}
    
        \addplot[
            color=yellow,
            mark=triangle,
            ]
            coordinates {
            (0,0.7807018020439974)(1,1.0)(2,1.0)(3,1.0)(4,1.0)(5,1.0)(6,1.0)
            };
        \addlegendentry{boy likes girl}
    
        \addplot[
            color=orange,
            mark=square,
            ]
            coordinates {
            (0,0.28832012639935184)(1,0.3688312119139115)(2,0.3688312119139115)(3,0.3688312119139115)(4,0.3688312119139115)(5,0.3688312119139115)(6,0.3688312119139115)
            };
        \addlegendentry{boy dates girl}
    
    
        \end{axis}
    \end{tikzpicture}
    
    \caption{Assume that $like(\xjack, \xjill) = 1$. Forward and backwards inference.}
    \label{fig:jack_likes}
\end{figure}
\paragraph{Backward Only}
In Figure \ref{fig:they_date}, we assume that $date(\xjack, \xjill) = 1$, which backwards infers through the $\Psi_\opand$ gate, to $like(\xjack, \xjill)$ and $like(\xjill, \xjack)$. The inference of $like(\xjack, \xjill)$ implies updated beliefs about its ancestors $lonely(\xjack)$ and $exciting(\xjill)$ as well.
\begin{figure}[htp]
    \centering
    \begin{tikzpicture}
        \begin{axis}[
            xlabel={Iteration},
            ylabel={Marginal},
            xmin=0, xmax=9,
            ymin=0, ymax=1,
            xtick={0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
            ytick={0,0.2,0.4,0.6,0.8,1},
            legend pos=south east,
            ymajorgrids=true,
            grid style=dashed,
        ]
    
    
        \addplot[
            color=red,
            mark=triangle,
            ]
            coordinates {
            (0,0.24881877877191566)(1,0.24881877877191566)(2,0.24881877877191566)(3,0.24881877877191566)(4,0.3491412895157568)(5,0.3491412895157568)(6,0.3491412895157568)(7,0.3491412895157568)(8,0.3491412895157568)(9,0.3491412895157568)
            };
        \addlegendentry{lonely boy}
    
        \addplot[
            color=green,
            mark=square,
            ]
            coordinates {
            (0,0.6118505817426283)(1,0.6118505817426283)(2,0.6118505817426283)(3,0.6118505817426283)(4,0.8607588124740367)(5,0.8607588124740367)(6,0.8607588124740367)(7,0.8607588124740367)(8,0.8607588124740367)(9,0.8607588124740367)
            };
        \addlegendentry{exciting girl}
    
        \addplot[
            color=blue,
            mark=o,
            ]
            coordinates {
            (0,0.5142276077495589)(1,0.5142276077495589)(2,0.9976633324933547)(3,0.9976633324933547)(4,0.9976633324933547)(5,0.9976633324933547)(6,0.9976633324933547)(7,0.9976633324933547)(8,0.9976633324933547)(9,0.9976633324933547)
            };
        \addlegendentry{girl likes boy}
    
        \addplot[
            color=yellow,
            mark=triangle,
            ]
            coordinates {
            (0,0.7074326821454369)(1,0.7074326821454369)(2,0.998592689588698)(3,0.998592689588698)(4,0.998592689588698)(5,0.998592689588698)(6,0.998592689588698)(7,0.998592689588698)(8,0.998592689588698)(9,0.998592689588698)
            };
        \addlegendentry{boy likes girl}
    
        \addplot[
            color=orange,
            mark=square,
            ]
            coordinates {
            (0,0.36338052172085666)(1,1.0)(2,1.0)(3,1.0)(4,1.0)(5,1.0)(6,1.0)(7,1.0)(8,1.0)(9,1.0)
            };
        \addlegendentry{boy dates girl}
    
    
        \end{axis}
    \end{tikzpicture}
    
    \caption{Assume that $date(\xjill, \xjack) = 1$. Backward inferences only.}
    \label{fig:they_date}
\end{figure}

\subsection{Reliability of Convergence}
We know that, in general, {\em iterative belief propagation} can fail to converge for certain networks.
We examine the {\em reliability} of convergence by examining $N=12$ different training runs, each with a different seed, producing a slightly different weight estimate.
Then, in each case, we observe that $date(\xjack, \xjill) = 1$, and we observe how many rounds of {\em fan out} are required to reach convergence.
We measure the number of the round in which a sequence first reaches the value it finishes with.
This is depicted in Figure \ref{fig:average_convergence}, in which we see that, surprisingly, the variance in the {\em convergence round} for each condition is $0$.
That is, while the probability estimates were different, the round of convergence did not change, in any case, over the $12$ different trials.


\begin{figure}
    \begin{tikzpicture}
        \begin{axis}[
        ybar,
        bar width=20pt, % Adjust the bar width if necessary
        enlargelimits=1.25, % Increase the space at the edges
        legend style={at={(0.5,-0.2)},anchor=north,legend columns=-1},
        ylabel={Convergence Round},
        xlabel={Condition},
        symbolic x coords={Jill likes Jack,Jack lonely,Jill exciting,Jack likes Jill,Jack dates Jill},
        xtick=data,
        xticklabels={,,},  % This will remove the x tick labels
        ]
        \addplot+[error bars/.cd, y dir=both, y explicit]
        coordinates {(Jill likes Jack, 2.0) +- (0,0.0)};
        \addplot+[error bars/.cd, y dir=both, y explicit]
        coordinates {(Jack lonely, 4.0) +- (0,0.0)};
        \addplot+[error bars/.cd, y dir=both, y explicit]
        coordinates {(Jill exciting, 4.0) +- (0,0.0)};
        \addplot+[error bars/.cd, y dir=both, y explicit]
        coordinates {(Jack likes Jill, 2.0) +- (0,0.0)};
        \addplot+[error bars/.cd, y dir=both, y explicit]
        coordinates {(Jack dates Jill, 1.0) +- (0,0.0)};
        \legend{Jill likes Jack,Jack lonely,Jill exciting,Jack likes Jill,Jack dates Jill}
        \end{axis}
    \end{tikzpicture}
    \caption{This shows the {\em average} {\em round of convergence} and {\em variance} for each variable. Note that the variance is always $0$.}
    \label{fig:average_convergence}
\end{figure}
        

\subsection{Message Propagation}
\paragraph{Method}
We have just seen that the {\em QBBN} with {\em iterative belief propagation} can infer over logical structures.
We now ask about the propagation of beliefs over {\em distance} in the graph.
To do this, we consider only a single variable $\xjack$, and a series of unary predicates $\alpha_0, ..., \alpha_N$, where we use $N = 10$.
Now $\alpha_0(\xjack)$ is determined by a $50\%$ cointoss.
Then, for $i \geq 1$, we deterministically set $\alpha_{i}(\xjack) = \alpha_{i-1}(\xjack)$.
That is, while $\alpha_0(\xjack)$ is random, $\alpha_i(\xjack)$ for $i \geq 1$ can be determined with certainty if we know the value of {\em either} of $\alpha_{i-1}(\xjack)$ or $\alpha_{i+1}(\xjack)$.
We examine how the beliefs change if we observe either $\alpha_0(\xjack)$ or $\alpha_N(\xjack)$ are observed to be true.

\paragraph{Results}
Figure \ref{fig:long_chain_prior} shows the {\em prior} probability of each node in the network, which is around $50\%$, with some noise, as discussed above.
Figure \ref{fig:long_chain_set_0_1} shows what happens when we observe $\alpha_0(\xjack) = 1$, the information propagates {\em forward} through the network in {\em one} iteration {\em total}.
Figure \ref{fig:long_chain_set_n_1} shows what happens when we observe $\alpha_N(\xjack) = 1$, the information propagates {\em backward} through the network, at a rate of {\em one} new node chaning per iteration, taking until iteration $20$ to converge.
Note that, for each variable $\alpha_i(\xjack)$, $i \geq 1$, there is also an intermediate ``conjoined'' node with only one element $\left\{\alpha_{i-1}(\xjack)\right\}_\land$.
We believe more efficient ways of managing belief propagation are possible than just doing repeated fan outs, but we leave this for future work.

\begin{figure}[htp]
    \centering
    \begin{tikzpicture}
        \begin{axis}[
            xlabel={Iteration},
            ylabel={Marginal},
            xmin=0, xmax=4,
            ymin=0, ymax=1,
            xtick={0, 1, 2, 3, 4},
            ytick={0,0.2,0.4,0.6,0.8,1},
            legend pos=south east,
            ymajorgrids=true,
            grid style=dashed,
        ]
    
    
        \addplot[
            color=red,
            mark=triangle,
            ]
            coordinates {
            (0,0.49119306043299993)(1,0.49119306043299993)(2,0.49119306043299993)(3,0.49119306043299993)(4,0.49119306043299993)
            };
        \addlegendentry{alpha0}
    
        \addplot[
            color=green,
            mark=triangle,
            ]
            coordinates {
            (0,0.49126892331174665)(1,0.49126892331174665)(2,0.49126892331174665)(3,0.49126892331174665)(4,0.49126892331174665)
            };
        \addlegendentry{alpha1}
    
        \addplot[
            color=blue,
            mark=triangle,
            ]
            coordinates {
            (0,0.491344933232657)(1,0.491344933232657)(2,0.491344933232657)(3,0.491344933232657)(4,0.491344933232657)
            };
        \addlegendentry{alpha2}
    
        \addplot[
            color=yellow,
            mark=triangle,
            ]
            coordinates {
            (0,0.491421055154676)(1,0.491421055154676)(2,0.491421055154676)(3,0.491421055154676)(4,0.491421055154676)
            };
        \addlegendentry{alpha3}
    
        \addplot[
            color=orange,
            mark=triangle,
            ]
            coordinates {
            (0,0.491496563275085)(1,0.491496563275085)(2,0.491496563275085)(3,0.491496563275085)(4,0.491496563275085)
            };
        \addlegendentry{alpha4}
    
        \addplot[
            color=purple,
            mark=triangle,
            ]
            coordinates {
            (0,0.49157187566454813)(1,0.49157187566454813)(2,0.49157187566454813)(3,0.49157187566454813)(4,0.49157187566454813)
            };
        \addlegendentry{alpha5}
    
        \addplot[
            color=black,
            mark=triangle,
            ]
            coordinates {
            (0,0.4916452702996028)(1,0.4916452702996028)(2,0.4916452702996028)(3,0.4916452702996028)(4,0.4916452702996028)
            };
        \addlegendentry{alpha6}
    
        \addplot[
            color=red,
            mark=square,
            ]
            coordinates {
            (0,0.49171978664559274)(1,0.49171978664559274)(2,0.49171978664559274)(3,0.49171978664559274)(4,0.49171978664559274)
            };
        \addlegendentry{alpha7}
    
        \addplot[
            color=green,
            mark=square,
            ]
            coordinates {
            (0,0.49179513743862413)(1,0.49179513743862413)(2,0.49179513743862413)(3,0.49179513743862413)(4,0.49179513743862413)
            };
        \addlegendentry{alpha8}
    
        \addplot[
            color=blue,
            mark=square,
            ]
            coordinates {
            (0,0.4918688281277979)(1,0.4918688281277979)(2,0.4918688281277979)(3,0.4918688281277979)(4,0.4918688281277979)
            };
        \addlegendentry{alpha9}
    
        \addplot[
            color=yellow,
            mark=square,
            ]
            coordinates {
            (0,0.49194452816557604)(1,0.49194452816557604)(2,0.49194452816557604)(3,0.49194452816557604)(4,0.49194452816557604)
            };
        \addlegendentry{alpha10}
    
    
        \end{axis}
    \end{tikzpicture}
    
    \caption{This shows the {\em prior} state of the $\alpha_i(\xjack)$ network. Before knowing anything at all, we expect $P(\alpha_i(\xjack)) = 0.5$ for all $i$.}
    \label{fig:long_chain_prior}
\end{figure}

\begin{figure}[htp]
    \centering
    \begin{tikzpicture}
        \begin{axis}[
            xlabel={Iteration},
            ylabel={Marginal},
            xmin=0, xmax=4,
            ymin=0, ymax=1,
            xtick={0, 1, 2, 3, 4},
            ytick={0,0.2,0.4,0.6,0.8,1},
            legend pos=south east,
            ymajorgrids=true,
            grid style=dashed,
        ]
    
    
        \addplot[
            color=red,
            mark=triangle,
            ]
            coordinates {
            (0,0.49119306043299993)(1,1.0)(2,1.0)(3,1.0)(4,1.0)
            };
        \addlegendentry{alpha0}
    
        \addplot[
            color=green,
            mark=triangle,
            ]
            coordinates {
            (0,0.49126892331174665)(1,0.9975700044433301)(2,0.9975700044433301)(3,0.9975700044433301)(4,0.9975700044433301)
            };
        \addlegendentry{alpha1}
    
        \addplot[
            color=blue,
            mark=triangle,
            ]
            coordinates {
            (0,0.491344933232657)(1,0.9951510042065193)(2,0.9951510042065193)(3,0.9951510042065193)(4,0.9951510042065193)
            };
        \addlegendentry{alpha2}
    
        \addplot[
            color=yellow,
            mark=triangle,
            ]
            coordinates {
            (0,0.491421055154676)(1,0.9927469557159797)(2,0.9927469557159797)(3,0.9927469557159797)(4,0.9927469557159797)
            };
        \addlegendentry{alpha3}
    
        \addplot[
            color=orange,
            mark=triangle,
            ]
            coordinates {
            (0,0.491496563275085)(1,0.9903518661797803)(2,0.9903518661797803)(3,0.9903518661797803)(4,0.9903518661797803)
            };
        \addlegendentry{alpha4}
    
        \addplot[
            color=purple,
            mark=triangle,
            ]
            coordinates {
            (0,0.49157187566454813)(1,0.9879704730398932)(2,0.9879704730398932)(3,0.9879704730398932)(4,0.9879704730398932)
            };
        \addlegendentry{alpha5}
    
        \addplot[
            color=black,
            mark=triangle,
            ]
            coordinates {
            (0,0.4916452702996028)(1,0.9855989979099659)(2,0.9855989979099659)(3,0.9855989979099659)(4,0.9855989979099659)
            };
        \addlegendentry{alpha6}
    
        \addplot[
            color=red,
            mark=square,
            ]
            coordinates {
            (0,0.49171978664559274)(1,0.9832399936248908)(2,0.9832399936248908)(3,0.9832399936248908)(4,0.9832399936248908)
            };
        \addlegendentry{alpha7}
    
        \addplot[
            color=green,
            mark=square,
            ]
            coordinates {
            (0,0.49179513743862413)(1,0.9808947940104048)(2,0.9808947940104048)(3,0.9808947940104048)(4,0.9808947940104048)
            };
        \addlegendentry{alpha8}
    
        \addplot[
            color=blue,
            mark=square,
            ]
            coordinates {
            (0,0.4918688281277979)(1,0.9785592284176858)(2,0.9785592284176858)(3,0.9785592284176858)(4,0.9785592284176858)
            };
        \addlegendentry{alpha9}
    
        \addplot[
            color=yellow,
            mark=square,
            ]
            coordinates {
            (0,0.49194452816557604)(1,0.9762374147028673)(2,0.9762374147028673)(3,0.9762374147028673)(4,0.9762374147028673)
            };
        \addlegendentry{alpha10}
    
    
        \end{axis}
    \end{tikzpicture}
    
    \caption{After observing $\alpha_0(\xjack) = 1$, the beliefs propagate {\em forward} in one pass.}
    \label{fig:long_chain_set_0_1}
\end{figure}

\begin{figure}[htp]
    \centering
    \begin{tikzpicture}
        \begin{axis}[
            xlabel={Iteration},
            ylabel={Marginal},
            xmin=0, xmax=24,
            ymin=0, ymax=1,
            xtick={0, 4, 8, 12, 16, 20, 24},
            ytick={0,0.2,0.4,0.6,0.8,1},
            legend pos=south east,
            ymajorgrids=true,
            grid style=dashed,
        ]
    
    
        \addplot[
            color=red,
            mark=triangle,
            ]
            coordinates {
            (0,0.5248192627359646)(1,0.5248192627359646)(2,0.5248192627359646)(3,0.5248192627359646)(4,0.5248192627359646)(5,0.5248192627359646)(6,0.5248192627359646)(7,0.5248192627359646)(8,0.5248192627359646)(9,0.5248192627359646)(10,0.5248192627359646)(11,0.5248192627359646)(12,0.5248192627359646)(13,0.5248192627359646)(14,0.5248192627359646)(15,0.5248192627359646)(16,0.5248192627359646)(17,0.5248192627359646)(18,0.5248192627359646)(19,0.5248192627359646)(20,0.9768884022241858)(21,0.9768884022241858)(22,0.9768884022241858)(23,0.9768884022241858)(24,0.9768884022241858)
            };
        \addlegendentry{alpha0}
    
        \addplot[
            color=green,
            mark=triangle,
            ]
            coordinates {
            (0,0.5248364231619441)(1,0.5248364231619441)(2,0.5248364231619441)(3,0.5248364231619441)(4,0.5248364231619441)(5,0.5248364231619441)(6,0.5248364231619441)(7,0.5248364231619441)(8,0.5248364231619441)(9,0.5248364231619441)(10,0.5248364231619441)(11,0.5248364231619441)(12,0.5248364231619441)(13,0.5248364231619441)(14,0.5248364231619441)(15,0.5248364231619441)(16,0.5248364231619441)(17,0.5248364231619441)(18,0.979149496823615)(19,0.979149496823615)(20,0.979149496823615)(21,0.979149496823615)(22,0.979149496823615)(23,0.979149496823615)(24,0.979149496823615)
            };
        \addlegendentry{alpha1}
    
        \addplot[
            color=blue,
            mark=triangle,
            ]
            coordinates {
            (0,0.5248529892359307)(1,0.5248529892359307)(2,0.5248529892359307)(3,0.5248529892359307)(4,0.5248529892359307)(5,0.5248529892359307)(6,0.5248529892359307)(7,0.5248529892359307)(8,0.5248529892359307)(9,0.5248529892359307)(10,0.5248529892359307)(11,0.5248529892359307)(12,0.5248529892359307)(13,0.5248529892359307)(14,0.5248529892359307)(15,0.5248529892359307)(16,0.9814206119585621)(17,0.9814206119585621)(18,0.9814206119585621)(19,0.9814206119585621)(20,0.9814206119585621)(21,0.9814206119585621)(22,0.9814206119585621)(23,0.9814206119585621)(24,0.9814206119585621)
            };
        \addlegendentry{alpha2}
    
        \addplot[
            color=yellow,
            mark=triangle,
            ]
            coordinates {
            (0,0.524869951417533)(1,0.524869951417533)(2,0.524869951417533)(3,0.524869951417533)(4,0.524869951417533)(5,0.524869951417533)(6,0.524869951417533)(7,0.524869951417533)(8,0.524869951417533)(9,0.524869951417533)(10,0.524869951417533)(11,0.524869951417533)(12,0.524869951417533)(13,0.524869951417533)(14,0.9837041139490732)(15,0.9837041139490732)(16,0.9837041139490732)(17,0.9837041139490732)(18,0.9837041139490732)(19,0.9837041139490732)(20,0.9837041139490732)(21,0.9837041139490732)(22,0.9837041139490732)(23,0.9837041139490732)(24,0.9837041139490732)
            };
        \addlegendentry{alpha3}
    
        \addplot[
            color=orange,
            mark=triangle,
            ]
            coordinates {
            (0,0.5248867094070616)(1,0.5248867094070616)(2,0.5248867094070616)(3,0.5248867094070616)(4,0.5248867094070616)(5,0.5248867094070616)(6,0.5248867094070616)(7,0.5248867094070616)(8,0.5248867094070616)(9,0.5248867094070616)(10,0.5248867094070616)(11,0.5248867094070616)(12,0.9859971332509343)(13,0.9859971332509343)(14,0.9859971332509343)(15,0.9859971332509343)(16,0.9859971332509343)(17,0.9859971332509343)(18,0.9859971332509343)(19,0.9859971332509343)(20,0.9859971332509343)(21,0.9859971332509343)(22,0.9859971332509343)(23,0.9859971332509343)(24,0.9859971332509343)
            };
        \addlegendentry{alpha4}
    
        \addplot[
            color=purple,
            mark=triangle,
            ]
            coordinates {
            (0,0.5249027027731392)(1,0.5249027027731392)(2,0.5249027027731392)(3,0.5249027027731392)(4,0.5249027027731392)(5,0.5249027027731392)(6,0.5249027027731392)(7,0.5249027027731392)(8,0.5249027027731392)(9,0.5249027027731392)(10,0.9883013873785309)(11,0.9883013873785309)(12,0.9883013873785309)(13,0.9883013873785309)(14,0.9883013873785309)(15,0.9883013873785309)(16,0.9883013873785309)(17,0.9883013873785309)(18,0.9883013873785309)(19,0.9883013873785309)(20,0.9883013873785309)(21,0.9883013873785309)(22,0.9883013873785309)(23,0.9883013873785309)(24,0.9883013873785309)
            };
        \addlegendentry{alpha5}
    
        \addplot[
            color=black,
            mark=triangle,
            ]
            coordinates {
            (0,0.5249186435961715)(1,0.5249186435961715)(2,0.5249186435961715)(3,0.5249186435961715)(4,0.5249186435961715)(5,0.5249186435961715)(6,0.5249186435961715)(7,0.5249186435961715)(8,0.9906167474603126)(9,0.9906167474603126)(10,0.9906167474603126)(11,0.9906167474603126)(12,0.9906167474603126)(13,0.9906167474603126)(14,0.9906167474603126)(15,0.9906167474603126)(16,0.9906167474603126)(17,0.9906167474603126)(18,0.9906167474603126)(19,0.9906167474603126)(20,0.9906167474603126)(21,0.9906167474603126)(22,0.9906167474603126)(23,0.9906167474603126)(24,0.9906167474603126)
            };
        \addlegendentry{alpha6}
    
        \addplot[
            color=red,
            mark=square,
            ]
            coordinates {
            (0,0.5249344570717788)(1,0.5249344570717788)(2,0.5249344570717788)(3,0.5249344570717788)(4,0.5249344570717788)(5,0.5249344570717788)(6,0.9929432698019474)(7,0.9929432698019474)(8,0.9929432698019474)(9,0.9929432698019474)(10,0.9929432698019474)(11,0.9929432698019474)(12,0.9929432698019474)(13,0.9929432698019474)(14,0.9929432698019474)(15,0.9929432698019474)(16,0.9929432698019474)(17,0.9929432698019474)(18,0.9929432698019474)(19,0.9929432698019474)(20,0.9929432698019474)(21,0.9929432698019474)(22,0.9929432698019474)(23,0.9929432698019474)(24,0.9929432698019474)
            };
        \addlegendentry{alpha7}
    
        \addplot[
            color=green,
            mark=square,
            ]
            coordinates {
            (0,0.5249521946674873)(1,0.5249521946674873)(2,0.5249521946674873)(3,0.5249521946674873)(4,0.9952847259370207)(5,0.9952847259370207)(6,0.9952847259370207)(7,0.9952847259370207)(8,0.9952847259370207)(9,0.9952847259370207)(10,0.9952847259370207)(11,0.9952847259370207)(12,0.9952847259370207)(13,0.9952847259370207)(14,0.9952847259370207)(15,0.9952847259370207)(16,0.9952847259370207)(17,0.9952847259370207)(18,0.9952847259370207)(19,0.9952847259370207)(20,0.9952847259370207)(21,0.9952847259370207)(22,0.9952847259370207)(23,0.9952847259370207)(24,0.9952847259370207)
            };
        \addlegendentry{alpha8}
    
        \addplot[
            color=blue,
            mark=square,
            ]
            coordinates {
            (0,0.5249699190124976)(1,0.5249699190124976)(2,0.9976374219843602)(3,0.9976374219843602)(4,0.9976374219843602)(5,0.9976374219843602)(6,0.9976374219843602)(7,0.9976374219843602)(8,0.9976374219843602)(9,0.9976374219843602)(10,0.9976374219843602)(11,0.9976374219843602)(12,0.9976374219843602)(13,0.9976374219843602)(14,0.9976374219843602)(15,0.9976374219843602)(16,0.9976374219843602)(17,0.9976374219843602)(18,0.9976374219843602)(19,0.9976374219843602)(20,0.9976374219843602)(21,0.9976374219843602)(22,0.9976374219843602)(23,0.9976374219843602)(24,0.9976374219843602)
            };
        \addlegendentry{alpha9}
    
        \addplot[
            color=yellow,
            mark=square,
            ]
            coordinates {
            (0,0.5249879755924464)(1,1.0)(2,1.0)(3,1.0)(4,1.0)(5,1.0)(6,1.0)(7,1.0)(8,1.0)(9,1.0)(10,1.0)(11,1.0)(12,1.0)(13,1.0)(14,1.0)(15,1.0)(16,1.0)(17,1.0)(18,1.0)(19,1.0)(20,1.0)(21,1.0)(22,1.0)(23,1.0)(24,1.0)
            };
        \addlegendentry{alpha10}
    
    
        \end{axis}
    \end{tikzpicture}
    
    \caption{After observing $\alpha_N(\xjack) = 1$, the beliefs propagate {\em backward} at a rate of one new node changing per iteration, and note that there are intermediate {\em conjunction} nodes, adding a constant factor to the convergence time.}
    \label{fig:long_chain_set_n_1}
\end{figure}

% bibliography
\bibliographystyle{apalike}
% \bibliography{bibtex}
\begin{thebibliography}{}

  \bibitem[Cooper, 1990]{Cooper1990}
  Cooper, G.~F. (1990).
  \newblock {The Computational Complexity of Probabilistic Inference Using
    Bayesian Belief Networks}.
  \newblock {\em Artificial Intelligence}, 42(2-3):393--405.
  
  \bibitem[Coppola, 2024a]{Coppola2024Thinking}
  Coppola, G. (2024a).
  \newblock {A Mathematical Explanation for ``Thinking Fast and Slow''}.
  \newblock Bitcoin Ordinal NFT {\em
    72494446539c7fcb73becde763fc4bbbf0686b9c30cd8188e50861ccde0a5c83i0}.
  
  \bibitem[Coppola, 2024b]{Coppola2024Logical}
  Coppola, G. (2024b).
  \newblock {The Quantified Boolean Bayesian Network: A Logical Graphical Model}.
  \newblock Bitcoin Ordinal NFT {\em
    5749e716a487c17eb9c5e27245dc23abb2432310765a46331c38e230cf8fe695i0}.
  
  \bibitem[Murphy et~al., 1999]{murphy1999loopy}
  Murphy, K., Weiss, Y., and Jordan, M.~I. (1999).
  \newblock Loopy belief propagation for approximate inference: An empirical
    study.
  \newblock In {\em Proceedings of the Fifteenth Conference on Uncertainty in
    Artificial Intelligence (UAI1999)}, pages 467--476. AUAI.
  
  \bibitem[Neapolitan, 2003]{neapolitan2003learning}
  Neapolitan, R.~E. (2003).
  \newblock {\em Learning Bayesian Networks}.
  \newblock Prentice Hall.
  
  \bibitem[Pearl, 1988]{pearl1988probabilistic}
  Pearl, J. (1988).
  \newblock {\em Probabilistic Reasoning in Intelligent Systems: Networks of
    Plausible Inference}.
  \newblock Morgan Kaufmann.
  
  \bibitem[Prawitz, 1965]{Prawitz1965}
  Prawitz, D. (1965).
  \newblock {\em Natural Deduction: A Proof-Theoretical Study}.
  \newblock Stockholm Studies in Philosophy 3. Almqvist \& Wiksell, Stockholm;
    Göteborg; Uppsala.
  \newblock Acta Universitatis Stockholmiensis.
  
  \bibitem[Radford et~al., 2018]{radford2018improving}
  Radford, A., Narasimhan, K., Salimans, T., and Sutskever, I. (2018).
  \newblock {Improving Language Understanding by Generative Pre-Training}.
  
  \bibitem[Roth, 1996]{Roth1996HardnessApproxReasoning}
  Roth, D. (1996).
  \newblock On the hardness of approximate reasoning.
  \newblock {\em Artificial Intelligence}, 82:273--302.
  
  \bibitem[Smith and Eisner, 2008]{Smith2008}
  Smith, D. and Eisner, J. (2008).
  \newblock Dependency parsing by belief propagation.
  \newblock In {\em EMNLP}, pages 145--156. Association for Computational
    Linguistics.
  
  \end{thebibliography}
  
% end
\end{document}