Bitcoin address: bc1pvd4selnseakwz5eljgj4d99mka25mk8pp3k7v7hc6uxw8txy6lgsf7lmtg
SHOWING: First 60
feel the AGI#68,272,122textthink "large language models" but "logical"#66,599,531textAGI has been achieved externally#62,377,617text\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}#60,549,642text\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{A Logical Graphical Model
\thanks{The self-contained source code for this article was published as a {\em Bitcoin Ordinal NFT} to the Bitcoin address {\em bc1pvd4selnseakwz5eljgj4d99mka25mk8pp3k7v7hc6uxw8txy6lgsf7lmtg} on {\em February 4, 2024}.
}}
\vspace{25pt}
}
\author{
{\Large Greg Coppola}
\\
{\em coppola.ai} \\
Research. Develop. Meme.
}
\date{\today}
\begin{document}
\maketitle
\tableofcontents
% sections
\section{Contributions}
We introduce the {\bf Quantified Boolean Bayesian Network}, {\em QBBN} for short, a model from the {\em Bayesian Network} family \cite{pearl1988probabilistic, neapolitan2003learning}, constructed and analyzed to provide a {\em unified theory} of {\em logical} and {\em statistical} {\em reasoning}.
In particular, our work makes the following contributions:
\begin{itemize}
\item {\bf Unified Model of Logical and Probabilistic Reasoning} \\
We provide a single data structure, the {\em QBBN}, which can do both:
\begin{itemize}
\item {\bf statistical reasoning} -- The {\em QBBN} is a {\em graphical model} that can answer {\em probabilistic queries} \cite{koller2009probabilistic} for {\em information-retrieval}.
\item {\bf logical reasoning} -- We show how the {\em QBBN} fits precisely into a larger {\em consistent} and {\em complete} {\em logical deduction system} \cite{Gentzen1934} for the {\em first-order} calculus.
\end{itemize}
The completeness proof is outlined in \cite{Coppola2024}.
\item {\bf A Generative Model Without Hallucinations} \\
The {\em QBBN} shows how to create a {\em generative} model of the ({\em latent logical forms} underlying) unlabeled text.
Like the {\em large language model} \cite{Bahdanau2014NeuralMT, vaswani2017attention, radford2018improving}, the {\em QBBN} is generative, and so can be used to {\em compress} the data \cite{SutskeverObservation}.
But, the {\em QBBN} does {\em not} {\em hallucinate}.
It reasons consistently (i.e., ensuring that $P(x) + P(\neg x) = 1$ for all questions $x$), and can {\em explain} its reasoning in terms of {\em causality}, like any Bayesian Network can.
\item {\bf Very Efficient Bayesian Inference} \\
In general, inference in a Bayesian Network is intractable, i.e. $\Omega(2^N)$ for $N$ random variables \cite{neapolitan2003learning}.
Our division of Bayesian Network nodes into \opand\ and \opor\ {\em boolean gates}, along with our use of the unguaranteed but empirically converging {\em iterative belief propagation} \cite{murphy1999loopy, smith2008dependency} means that {\em inference} can now be not only tractable, but {\em very efficient}, with one full pass of approximate belief propagation requiring only time $O(N2^n)$, where $N$ is the number of network variables involved, and $n$ bounds the number of incoming connections in any \opand\ or \opor\ gate. Moreover, we discuss why it may be possible to bring the factor computation cost to $O(n)$ instead of $O(2^n)$ for each of \opand\ and \opor.
\item {\bf Fast Versus Slow Thinking} \\
We give, to our knowledge, the first mathematical {\em explanation} of the distinction between what has come to be known as {\em fast} versus {\em slow} thinking \cite{Kahneman2011ThinkingFast}.
This explanation is based on {\em proof theory} of the {\em natural deduction calculus}, and accords both with our graphical formulation, as well human experience.
As a special case of general reasoning, we analyze {\em planning}, which task \cite{Lecun2023} has argued {\em LLM}'s do not properly support.
\item {\bf Calculus Over Dependency Trees} \\
Empirically, {\em labeled dependnecy trees} are the easiest {\em syntactic formalism} to parse to.
Traditionally, parsing language to a {\em complete} and {\em consistent} calculus required using the {\em first-order logic} calculus \cite{Steedman1996}, but translation to {\em literally} first-order calculus, requires an unecessary imposition of {\em positional order} on arguments that is not helpful for knowledge encoding.
By defining a complete calculus closer to the key-value {\em labeled dependency structure}, it is {\em easier} to encode knowledge, and we {\em minimize} the distance between the {\em surface form} and the {\em interpretation}.
\end{itemize}
\section{Background}
\subsection{First-Order Logic}
\subsubsection*{Explanatory Power}
In the {\em philosophy of science} it is by now taken for granted that all of {\em mathematics} and {\em science} can be expressed in terms of {\em first-order logic} (or its {\em extensions}) (see, e.g., \cite{Pelletier2000}, and the references therein).
Thus, we say that {\em first-order logic} is {\em sufficient} to model {\em human reasoning}.
Extensions include {\em second-order logic} and {\em modal logic} \cite{Prawitz1965}, but we leave this for future work, and focus on the {\em first-order logic} for simplicity.
\subsubsection*{Language and Deduction Rules}
\paragraph{Universal Quantification and Implication}
The method of {\em universal quantification} is represented by $\forall$, and {\em implication} is represented by the $\rightarrow$ symbol.
These work together as in:
\begin{equation} \forall [\variable{jack}, \variable{jill}], date(\variable{jack}, \variable{jill}) \rightarrow date(\variable{jill}, \variable{jack}) \end{equation}
This says that {\em for all} entities of type $\xvariable_{jack}$ and {\em all} entities of type $\xvariable_{jill}$, if $\xvariable_{jack}$ is dating $\xvariable_{jill}$, then $\xvariable_{jill}$ is also dating $\xvariable_{jack}$.
Universal quantification is essential for making sense of an infinite world with a finite theory, because it allows us to make statements about an unbounded number of entities, in relation to one another, with a finite number of universally quantified statements.
\paragraph{Logical Connectives}
There are two logical connectives designated as {\em boolean} in our system, corresponding to the two operations generally in a {\em boolean algebra}.
\paragraph{\opand}
The first connective is {\em and}, represented with $\wedge$, as in:
\begin{equation} date(\constant{jack}, \constant{jill}) \wedge date(\constant{jack}, \constant{jill}) \end{equation}
This means that {\em both} $date(\constant{jack}, \constant{jill})$ {\em and} $date(\constant{jack}, \constant{jill})$ are true.
\paragraph{\opor}
The second connective is {\em or}, represented with $\vee$, as in:
\begin{equation} date(\constant{jack}, \constant{jill}) \vee date(\constant{jack}, \constant{jill}) \end{equation}
This means that {\em at least one of} the {\em terms} is true, maybe {\em both}.
\paragraph{Unused Symbols}
There are two other logical symbols, $\exists$ and $\bot$, which we can implement for the {\em completeness} proof, but do not use for practical statistical inference at this time.
\subsubsection*{Completeness and Consistency}
For any logical calculus, we have a notion of what is {\em provable} in that calculus.
This is evaluated against a {\em model interpretation}, that says what is {\em true}.
A logic is {\em consistent} if whatever is {\em provable} is {\em true}.
A logic is {\em completeness} if whatever is {\em true} is {\em provable}.
\cite{Godel1930} proved the consistency and completeness of first-order calculus.
A fundamental insight of this work is that, we are free to work in a more practical formalism, i.e. a {\em graphical statistical model} over {\em semantic roles}, than the {\em first-order logic} if we will only prove the {\em consistency} and {\em completeness} of this new logic, which we outline in \cite{Coppola2024}.
\subsection{Bayesian Networks}
\subsubsection*{Markov Graphical Models}
A distribution \( P([\pvariable_1, ..., \pvariable_N]) \) \textit{factorizes according to a factor graph \( G_F \)} if there exists a set of {\em factors} $\left\{\alpha\right\}_F$ and {\em factor functions} \( \Psi_\alpha \) such that \( P([\pvariable_1, ..., \pvariable_N]) \) can be written as:
\begin{equation}
P([\pvariable_1, ..., \pvariable_N]) = Z^{-1} \prod_{\alpha \in F} \Psi_\alpha(\left\{\pvariable\right\}_\alpha)
\end{equation}
Here, $\left\{\pvariable\right\}_\alpha$ are the set of all {\em variables} $\pvariable$ in the factor $\alpha$ and \( Z \) is a {\em normalization} constant that ensures that the probabilities sum to one.
Doing {\em normalization}, and relatedly {\em marginalization}, in a general graphical model takes time $\Omega(2^N)$.
\subsubsection*{Boolean Network}
The {\em QBBN} is deliberately formulated as a {\em boolean} network, in which all propositional variables $\pvariable$ are modeled as either taking the value {\em true}, represented by $1$, or {\em false}, represented by $0$.
Note that, while $P(\pvariable = z)$ is a probability, for $z \in \left\{0, 1\right\}$, the possible {\em values} that $\pvariable$ can take are boolean.
\subsubsection*{Markov Logic Network}
\cite{richardson2006markov} use a graphical boolean statistical network to score sentences constrained by the deductions of the first-order calculus.
Inference in {\em Markov Networks} in general is {\em \#P-complete} \cite{Roth1996HardnessApproxReasoning}, which is $\Omega(2^N)$.
Because exact inference is intractable, \cite{richardson2006markov} use approximate inference via {\em Markov Chain Monte Carlo} \cite{gilks1996markov} sampling.
\subsubsection*{Traditional Bayesian Networks}
\paragraph{Directed Acyclic Graph}
A traditional {\em Bayesian Network} is a {\em directed} graphical model, where each factor maps $\alpha$ {\em input variables} $\avariable_i$ to an {\em output variable} $\zvariable$:
\begin{equation} \Psi(\zvariable \condsep \avariable_1, ..., \avariable_n) \end{equation}
For each pair $(\zvariable, \avariable)$, we will refer to $\zvariable$ as the {\em child} (or {\em conclusion}), and to $\avariable$ a the {\em parent} (or {\em assumption}).
The directed nature of the factor gives rise to two clear inference directions: {\em forwards}, in which information passes from {\em causes} to {\em effects}, and {\em backwards}, in which information passes from {\em effects} (the {\em observations}), backwards to {\em causes} (a {\em hypothesis}).
\paragraph{Complexity}
Inference in general Bayesian Networks is also {\em \#P-complete} \cite{Cooper1990}, and even {\em NP-hard} to {\em provably approximate} \cite{Roth1996HardnessApproxReasoning}.
The difficulty is owing to the difficulty of marginalizing over {\em undirected cycles} in the factor graph \cite{neapolitan2003learning,koller2009probabilistic}.
Nevertheless, {\em loopy belief propagation}, which we will henceforth call {\em iterative belief propagation}, while {\em not} provably convergent, has been found to empirically to converge in many situations \cite{murphy1999loopy, Smith2008}.
\subsubsection*{Quantification in Bayesian Networks}
An analog of {\em universal quantification} has been studied under the rubric of {\em plate models} \cite{koller2009probabilistic}, in which nodes sharing a {\em template} structure can share weights.
We also employ this {\em parameter sharing}, but view it instead from a logical perspective as {\em quantification}.
\section{A Novel Calculus Over Semantic Roles}
\subsection{Motivation}
We have said that the calculus of {\em first-order logic} is {\em complete}, {\em consistent}, and {\em sufficient} for expressing {\em mathematics} and {\em science}.
However, the {\em language} of the {\em first-order logic} logic is quite far from the {\em labeled dependency parses} that are most easily parsed to \cite{eisner1996bilexical, mcdonald2005non, zhang2011transition}.
For example, \cite{Lewis2013} shows how the sentence {\em Shakespeare wrote Macbeth} can be translated via a system of {\em functional categories} to a {\em first-order language} formula:
\begin{equation}
wrote_{arg_0:\textsc{per}, arg_1:\textsc{book}}(\cvariable_{Shakespare}, \cvariable_{Macbeth})
\end{equation}
Our observation is that it would be both easier to {\em parse to} and easier to {\em represent knowledge in} a formalism like:
\begin{equation}
(wrote, \left\{ arg_0: \cvariable_{Shakespare}, arg_1:\cvariable_{Macbeth}\right\})
\end{equation}
That is, it is easier to {\em ignore the order} of the arguments, and use a {\em key-value} map to index the arguments.
In practice, as we will see, it is easier to encode implications if we ignore the order, and only use the {\em function name} and the {\em labeled key-value} pairs.
Also, this formulation matches the way that an {\em attention node} works, in that an attention function can be described as mapping a query and a set of key-value pairs to an output \cite{Vaswani2017}.
In the attention network, these objects are all {\em vectors}, while here they are {\em symbols}.
To be clear, we are not claiming there is {\em no} book-keeping to do to get from {\em surface structure} to {\em logical} structure.
We can associate each of the {\em labeled dependencies} each with a {\em function application} fom {\em categorial grammar} \cite{BarHillel1953}.
However, the pipeline can be greatly simplified on the {\em parsing side} and also on the {\em knowledge representation} side if we {\em feel free} to invent more {\em flexible} logical calculi, so long as we prove {\em consistency}, {\em completeness} and {\em sufficiency}.
\subsection{Language Definition}
\paragraph{A Key-Value Calculus}
Assume we have access to a {\em labeled dependency parse} as in Figure \ref{fig:dependency}.
\begin{figure}[h!]
\centering
\begin{dependency}[theme = simple]
\begin{deptext}[column sep=1em]
John \& sent \& a \& letter \& to \& Sally \\
\end{deptext}
\deproot{2}{ROOT}
\depedge{2}{1}{subj}
\depedge{4}{3}{det}
\depedge{2}{4}{dobj}
\depedge{6}{5}{case}
\depedge{2}{6}{iobj}
\end{dependency}
\caption{A labeled dependency parse. Without labels, we could not do semantics, so this is the most simple structure that can support semantics.}
\label{fig:dependency}
\end{figure}
From this parse we can through some {\em syntactic analysis} extract a {\em proposition} of the {\em rough form}:
\begin{equation}
(\textsc{send}, \left\{
\begin{aligned}
&\textsc{subj}: \text{John}, \\
&\textsc{dobj}: \text{a letter}, \\
&\textsc{iobj}: \text{Sally}
\end{aligned}
\right\})
\label{eq:dep-semantics}
\end{equation}
By defining a predicate as close to the bare dependency structure as possible, we obviate the need to manage the book-keeping to enforce an {\em arbitrary linear order} on the arguments as in:
\begin{equation}
send_{subj,dobj,iobj}(\text{John}, \text{a letter}, \text{Sally})
\end{equation}
\paragraph{Truth Values}
There are two {\em boolean truth values}, {\em true}, which we write as $1$ and {\em false}, which we write as $0$.
The {\em nodes} of primary interest in {\em queries} to our {\em graphical model} are about the {\em values} of {\em propositions}, usually denoted $\pvariable$.
We can {\em query} the probabilities $P(\pvariable = 1)$ and $P(\pvariable = 0)$.
That is, we assume that each {\em proposition} is either definitely {\em true} or {\em false}, and we do not know which, but we can assign a probability in $[0, 1]$.
\paragraph{Entities}
An {\em entity} is identified by a {\em string} $e$ and corresponds to an object in our {\em information retrieval} database, e.g., {\em Taylor Swift}, {\em Beyonce}, {\em USA}, {\em China}.
\paragraph{Types} A {\em type} $\tau$ is identified by a {\em string}.
We will assume that each {\em entity} {\em exhibits} a non-negative number of {\em types}.
In {\em information retrieval} some relevant types are {\em business}, {\em individual}, {\em group}, {\em book}, or {\em product}.
Usually the type is clear from context and we will usually not write $\tau$.
\paragraph{Constants}
A {\em constant} (or {\em constant reference}) is a pair $(e, \tau)$ of {\em entity identifier} and {\em type}.
The constant refers to a specific entity.
For example, the entity \textsc{usa} exhibits the type \textsc{country}, so its constant reference would be:
\begin{equation} \constant{usa} = \textbf{constant}(\textsc{usa}, \textsc{country})\end{equation}
\paragraph{Variables}
A {\em variable} is defined by a type $\tau$.
\begin{equation} \variable{country} = \textbf{variable}(\textsc{country})\end{equation}
A {\em variable} can be {\em instantiated} by any {\em constant} of the same type.
\paragraph{Function Names}
A {\em function name} $f$ is a {\em string}, e.g., $\textsc{like}$ or $\textsc{date}$.
\paragraph{Arguments}
An {\em argument} $a$ is an object that wraps {\em either} a {\em constant} $\cvariable_\tau$ or a {\em variable} $\xvariable_\tau$.
Given an argument, we can tell which type of object it wraps ($\cvariable_\tau$ or $\xvariable_\tau$), and also recover the wrapped object.
\paragraph{Role Labels}
Each {\em role label} $r$ is a {\em string} from a {\em bounded set}, e.g. \textsc{subj}, \textsc{dobj} or \textsc{iobj}.
The role label indexes the {\em argument position} that an {\em argument} plays for a {\em function}.
A {\em labeled argument} is a pair $(r, a)$ of {\em role} and {\em argument}.
\paragraph{Role Sets and Maps}
A set of {\em roles} $\rvariable = \left\{r\right\}_{r \in \rvariable}$ is called a {\em role set}.
A {\em role-argument mapping} is a map $\mvariable = \left\{(r, a)\right\}_{r \in \rvariable}$.
The {\em open roles} in $\mvariable$ are those pair $(r, a)$ where $a$ wraps a {\em variable}.
The {\em filled roles} are those where $a$ wraps a {\em constant}.
\paragraph{Predicates}
A {\em predicate}'s {\em type} is {\em defined} by pair of a {\em function name} and a set of {\em roles labels}.
\begin{equation} \tau(\qvariable) = (f, \rvariable)\end{equation}
A {\em predicate instance} is a pair of a {\em function name} and a {\em role-argument mapping}:
\begin{equation} \qvariable = (f, \mvariable)\end{equation}
An example of a predicate is:
\begin{equation} \qvariable = (\textsc{like}, \left\{\textsc{sub}: \variable{jack}, \textsc{obj}: \variable{jill} \right\})\end{equation}
$\qvariable$ does {\em not} have a truth value, and we {\em cannot} ask $P(\qvariable = 1)$, because of the presence of {\em open roles} and so {\em unbound variables} $\variable{jack}$ and $\variable{jill}$.
Only when these variables are replaced by {\em constants}, referring to {\em specific entities}, will we have a truth value to estimate a probability for.
\paragraph{Propositions}
A {\em predicate} with {\em zero} open roles is called a {\em proposition}, usually denoted $\pvariable$, e.g.
\begin{equation} \pvariable = (\textsc{like}, \left\{\textsc{sub}: \constant{jack1}, \textsc{obj}: \constant{jill1} \right\})\end{equation}
Having no {\em open roles}, a {\em proposition} is {\em fully grounded} and so has a {\em probability}, and we can ask $P(\pvariable = 1)$.
E.g., in this case, we can ask whether $\constant{jack1}$ in particular likes $\constant{jill1}$ in particular.
\subsection{Quantification and Implication}
\subsubsection{Statistical Inference}
In the traditional first-order calculus $\forall A\rightarrow B$ means that $B$ {\em always} follows $A$.
We want to generalize $\forall$ with a {\em statistical} notion $\Psi A\rightarrow B$, which means, {\em more generally}, that $B$ follows $A$ {\em with some probability}.
Then, we have the option to {\em estimate} $\Psi$ from {\em data}.
\subsubsection{Predicate Implication Links}
\paragraph{Example}
We will introduce the running example of {\em binary dating}, in which we have a {\em bipartite graph} with {\em two} types of entities, those of type $\xjack$ and those of type $\xjill$, and we have a predicate of interest:
\begin{equation} (\textsc{date}, \left\{ \textsc{subj}: \xjack, \textsc{dobj}:\xjill\right\}) \end{equation}
This returns true if $\xjack$ is dating $\xjill$.
Now if $\xjack$ {\em likes} $\xjill$, they are more likely to {\em date}.
We can represent this in our key-value calculus as:
\begin{equation}
\Psi[\xjack, \xjill]\left(\textsc{like}, \left\{
\begin{aligned}
&\textsc{subj}: \xjack, \\
&\textsc{dobj}: \xjill, \\
\end{aligned}
\right\} \right)
\rightarrow \left(
\textsc{date}
\left\{
\begin{aligned}
&\textsc{subj}: \xjack, \\
&\textsc{dobj}: \xjill, \\
\end{aligned}
\right\}
\right)
\label{eq:like-date-same}
\end{equation}
We can also represent the related link that $\xjack$ and $\xjill$ are more likely to date if $\xjill$ {\em likes} $\xjack$:
\begin{equation}
\Psi[\xjack, \xjill]\left(\textsc{like}, \left\{
\begin{aligned}
&\textsc{subj}: \xjill, \\
&\textsc{dobj}: \xjack, \\
\end{aligned}
\right\} \right)
\rightarrow \left(
\textsc{date}
\left\{
\begin{aligned}
&\textsc{subj}: \xjack, \\
&\textsc{dobj}: \xjill, \\
\end{aligned}
\right\}
\right)
\label{eq:like-date-change}
\end{equation}
\paragraph{Role Set Mapping}
Comparing \ref{eq:like-date-same} to \ref{eq:like-date-change}, we see that \ref{eq:like-date-same} maintains the same role-argument assignments in premise as conclusion:
\begin{equation}
\left\{\textsc{nsubj} : \textsc{nsubj}, \textsc{dobj} : \textsc{dobj} \right\}
\end{equation}
In \ref{eq:like-date-change}, the roles are reversed:
\begin{equation}
\left\{\textsc{nsubj} : \textsc{dobj}, \textsc{dobj} : \textsc{nsubj} \right\}
\end{equation}
In order to allow both possibilities, between any conclusion $\qvariable_c$ and premise $\qvariable_a$, we introduce the {\em role set mapping}, which is a map $\left\{r, s\right\}$, where each entry $(r, s)$ indicates that the argument for role $r$ in $\qvariable_a$ should be used to fill role $s$ in $\qvariable_c$.
\paragraph{Predicate Implication Link}
A single {\em predicate implication link} is a triple:
\begin{equation}
\Psi(\qvariable_a, \qvariable_c, \left\{r, s\right\})
\end{equation}
where $\qvariable_a$ and $\qvariable_c$ are predicates, and where $\left\{r, s\right\}$ is an appropriate role mapping between the two.
In our current implementation, we require that all open roles in each of $\qvariable_a$ and $\qvariable_c$ be filled, and that $\qvariable_a$ have less than or equal to the number of open roles of $\qvariable_c$.
\subsubsection{Conjoined Predicate Implication}
\paragraph{Motivation}
At a high level, the {\em implication links} correspond to patterns of {\em features} that we can {\em train} and {\em reuse} over {\em proposition factors}.
Suppose we want to use a {\em linear} model for these features, either because it is interpretable or because it is faster.
The problem with linear models, in general, is that they cannot separate all functions.
For example, \opxor\ cannot be separated, if the problem is interpreted naively \cite{minsky1969perceptrons}.
However, e.g., \opxor\ {\em can} be separated if we are allowed to {\em conjoin} (or {\em combine}, or {\em take a boolean combination of}) the input features.
In the case of {\em dating}, $\xjack$ and $\xjill$ will in a modern context only date if they {\em both} like {\em each other}.
To represent this, we want a feature that only fires if {\em both} $like(\xjack, \xjill)$ {\em and} $like(\xjill, \xjack)$, i.e.:
\begin{equation}
\Psi[\xjack, \xjill]\left( \left\{like(\xjack, \xjill) \wedge like(\xjill, \xjack)\right\} \rightarrow date(\xjack, \xjill)\right)
\label{eq:jack_and_jill}
\end{equation}
\paragraph{Formulation}
Where $\qvariable_{a_i}$ are each {\em predicates}, we use $\hvariable$ as short-hand for a {\em group} ({\em ordered list}) of predicates,
\[ \hvariable_a = [\qvariable_{a_1}, ..., \qvariable_{a_n}]\]
Where $\qvariable_c$ is a {\em conclusion} predicate define the {\em conjoined implication} $\Psi(\hvariable_a, \qvariable_c)$ as:
\begin{equation}
\Psi(\hvariable_a, \qvariable_c) = \left[ (\hvariable_{a_1}, \qvariable_c, \left\{r, s\right\}_{a_1}) \wedge ... \wedge (\hvariable_n, \qvariable_c, \left\{r, s\right\}_{a_n})\right]
\label{eq:conjoined_predicate}
\end{equation}
Here, we assume that each $\left\{r, s\right\}_{a_i}$ is appropriate to match the open roles of $\hvariable_{a_i}$ to $\qvariable_c$.
The form \ref{eq:conjoined_predicate} allows us to state an inferential like like \ref{eq:jack_and_jill}.
\section{The Proposition Graph}
\subsection{Lazy Graph}
For an unbounded set of {\em entities}, there are an unbounded number of {\em possible propositions} $\pvariable$, many of which will never be relevant.
For example, consider the predicate of {\em is President of the United States}.
This only applies in practice to one person, but could, in principle, apply to billions.
Thus, storing all {\em possible} propositions in memory is a waste of disk space, so we only store those propositions that are relevant.
In this sense, the graph is {\em lazy}.
During training of $\Psi_\opor$, we only train {\em local factors}, which do not require a full proposition graph to be created.
During inference, we create the proposition graph {\em dynamically} at run time from the {\em implication graph}, described in Section \ref{s:predgraph}.
\subsection{Boolean Algebra}
For reasons of logical completeness, and also computational efficiency, we split the graph into two kinds of {\em junctions}, or {\em factor types}:
\begin{enumerate}
\item {\em conjunction} factors, denoted $\Psi_\opand$
\item {\em disjunction factors}, denoted $\Psi_\opor$.
\end{enumerate}
The computation in the graph alternates between these: a {\em conjunction} factor $\Psi_\opand$ feeds into a {\em disjunction} factor $\Psi_\opor$, and vice versa, as depicted in Figure \ref{fig:alternating_network}.
\begin{figure}[t]
\centering
\begin{tikzpicture}
\def\levelOne{2}
\def\levelTwo{0.5}
\def\levelThree{-1}
\def\levelFour{-2.5}
\def\levelFive{-4}
\node (lonely) at (0,\levelOne) {$\Psi_\opor$[boy lonely]};
\node (exciting) at (6,\levelOne) {$\Psi_\opor$[girl exciting]};
\node (interLonely) at (0,\levelTwo) {$\Psi_\opand$};
\node (interExciting) at (6,\levelTwo) {$\Psi_\opand$};
\node (boyLikesGirl) at (1.5,\levelThree) {$\Psi_\opor$[boy likes girl]};
\node (girlLikesBoy) at (4.5,\levelThree) {$\Psi_\opor$[girl likes boy]};
\node (conjunction) at (3,\levelFour) {$\Psi_\opand$};
\node (dates) at (3,\levelFive) {$\Psi_\opor$[boy dates girl]};
\draw[->] (lonely) -- (interLonely);
\draw[->] (exciting) -- (interExciting);
\draw[->] (interLonely) -- (boyLikesGirl);
\draw[->] (interExciting) -- (girlLikesBoy);
\draw[->] (boyLikesGirl) -- (conjunction);
\draw[->] (girlLikesBoy) -- (conjunction);
\draw[->] (conjunction) -- (dates);
\end{tikzpicture}
\caption{A {\em boolean network} that {\em alternates} between \opand\ and \opor\ gates.}
\label{fig:alternating_network}
\end{figure}
\paragraph{Bipartite Graph}
Because the factor types $\Psi_\opand$ and $\Psi_\opor$ always alternate, we have a {\em bipartite graph}.
Suppose $\pvariable_1, ..., \pvariable_n$ are each {\em propositions}.
Then we say
\begin{equation} \gvariable = \left\{\pvariable_1 \wedge ... \wedge \pvariable_n\right\} \end{equation}
is a {\em proposition group}, which are interpreted as {\em conjoined}.
Then, the two types of variables in the graph then are:
\begin{enumerate}
\item $\pvariable$, which represents a {\em single proposition}
\item $\gvariable$, which represents a {\em conjoined proposition group}
\end{enumerate}
For many purposes in the graphical model (e.g., {\em message passing} calculuations), we can abstract over whether a node is $\gvariable$ and $\pvariable$, and we refer to {\em generic graphical nodes} as $\zvariable$.
It is to be understood that each $\zvariable$ actually {\em wraps} a $\gvariable$ or a $\pvariable$, and that we can get either the underlying type or underlying value from any $\zvariable$ at any time.
\paragraph{Conjunction Nodes}
The {\em conjunctive} factor $\Psi_\opand$ is defined in terms of the {\em \opand\ gate}:
\begin{equation} \opand(\pvariable_1, ..., \pvariable_n) = \pvariable_1 \wedge ... \wedge \pvariable_n \end{equation}
Then:
\begin{equation}
\Psi_{\opand}(\gvariable \condsep \pvariable_1, \ldots, \pvariable_n) =
\begin{cases}
1 & \text{if } \gvariable == \opand(\pvariable_1, \ldots, \pvariable_n), \\
0 & \text{otherwise}
\end{cases}
\end{equation}
It must be stressed that in all cases the $\Psi_\opand$ factor is {\em deterministic}, i.e., we do not train this even when we are interested in statistical inference.
This is owing to the fact that \opand's role is to create {\em higher-level features}, between which we can learn relationships.
\paragraph{Disjunction Nodes}
The deterministic {\em disjunctive} factor $\Psi_{\opor}$ used for the {\em completeness proof} \cite{Coppola2024}, is defined in terms of the {\em \opor\ gate}:
\begin{equation}
\opor(\pvariable_1, \ldots, \pvariable_n) = \pvariable_1 \vee \ldots \vee \pvariable_n
\end{equation}
The {\em deterministic} version of \opor, used in the {\em completeness} proof, and can be used any time we want exact logical \opor, is defined as:
\begin{equation}
\Psi_{\opor}(\gvariable \condsep \pvariable_1, \ldots, \pvariable_n) =
\begin{cases}
1 & \text{if } \gvariable == \opor(\pvariable_1, \ldots, \pvariable_n), \\
0 & \text{otherwise}
\end{cases}
\end{equation}
When interested in {\em statistical inference}, we {\em learn} this model, as discussed in Section \ref{sec:learned_model}.
\subsection{Markov Assumption}
The essential feature of a graphical model is that it makes a {\em Markov assumption}, in which each variable in the graph is independent of all nodes, given the values of its {\em neighbors}.
Because the edges are {\em directed}, the {\em neighbors} of a node are its {\em parents} and its {\em childen}.
In our Bayesian Network, each factor in the graph has the form:
\begin{equation} \Psi(\zvariable \condsep \zvariable_{a_1}, ..., \zvariable_{a_n}) \end{equation}
In this case, we would say that $\zvariable$ is the {\em child} of each $\zvariable_{a_i}$ and each $\zvariable_{a_i}$ is a {\em parent} of $\zvariable$.
Conversely, $\zvariable$ can also have effects on {\em its} children as in:
\begin{equation} \Psi(\zvariable_c \condsep \zvariable, \zvariable_{b_1}, ..., \zvariable_{b_{n-1}}) \end{equation}
Here, the $\zvariable_{b_i}$ are other parents of $\zvariable_c$.
The {\em Markov} assumption says that we can know everything we need to know about $\zvariable$ if we know the values of its {\em parents} and its {\em children}, i.e., $\zvariable$ is {\em independent} of all other nodes in the network, given its neighbors.
\subsection{Learned Disjunctive Model}
\label{sec:learned_model}
For the {\em learned model}, $\Psi_\opor$ is {\em learned} from {\em data}.
\paragraph{Linear Exponential Model}
For $\Psi_\opor$ we train a {\em linear exponential} model.
For a boolean variable \( \pvariable \) with boolean features \( \gvariable_1, ..., \gvariable_n \), the {\em factor potential} has the form:
\begin{equation}
\Psi_{\opor} (\pvariable \condsep \gvariable_1, ..., \gvariable_n) = \exp{ \left\{\sum_{i=1}^{n} {\wvariable \cdot \phi(\pvariable, \gvariable_i)}\right\}}
\label{e_linear_exponential}
\end{equation}
Here, \( \wvariable \) is a weight vector, and \( \phi(\pvariable, \gvariable_i) \) is a feature discussed in Section \ref{s:feature_function}.
The probability \( P(\pvariable \condsep \gvariable_1, ..., \gvariable_n) \) is obtained by normalization over the two possible values for \( \pvariable \in \left\{0, 1\right\} \):
\begin{equation}
P(\pvariable = p \condsep \gvariable_1, ..., \gvariable_n) = \frac{\Psi_{\opor} (p \condsep \gvariable_1, ..., \gvariable_n)}{\Psi_{\opor} (1 \condsep \gvariable_1, ..., \gvariable_n) + \Psi_{\opor} (0 \condsep \gvariable_1, ..., \gvariable_n)}
\end{equation}
\paragraph{On the Use of a Linear Model}
One might ask whether it is {\em simplistic} to use a {\em linear} model for any reason when we have availble advanced networks like {\em multi-layer networks} and {\em attention}, etc.
The use of non-linear networks in this context can be investigated.
However, it is the role of the {\em conjunction} gates to create the {\em higher-level} features that are accomplished currently with {\em multi-layer networks}.
Linear weights are easily {\em interpretable}, which is good for {\em human-computer alignment}.
Also, for certain definitions of $\Psi_\opor$, like the {\em Noisy Or} gate discussed in Section \ref{sec:noisy_or}, updates can be {\em fast}, i.e. $O(n)$ instead of $O(2^n)$, because of the independence of inputs.
We leave it to future work to decide whether any $O(n)$ models for $\Psi_\opor$ are useful in practice.
\section{The Implication Graph}
\label{s:predgraph}
\subsection{Infinite Use of Finite Means}
Chomsky was famously fond of quoting Humboldt's aphorism that language makes {\em infinite use of finite means} \cite{Chomsky1965Aspects}.
The {\em implication graph} allows us to estimate probabilities for an {\em unbounded} number of {\em propositions} $\pvariable$ based on finite parameters $\Psi$, by defining weights over {\em predicate patterns}, rather than relationships between {\em concrete entities}.
That is, we learn a general link between $\xjack$ {\em liking} $\xjill$ and $\xjack$ {\em dating} $\xjill$, and this can apply to $\cvariable_{jack1}$ or $\cvariable_{jack2}$ or $\cvariable_{jill1}$ or $\cvariable_{jill2}$, etc., and so make {\em infinite use} of {\em finite means}.
\subsection{Graph Operations}
\paragraph{Construction}
The {\em implication graph} is constructed from the set of all relevant {\em conjoined predicate implications} that we want to train weights for in our model:
\begin{equation}
\mathcal{K} = \left\{\Psi(\hvariable, \qvariable)\right\}
\end{equation}
\paragraph{Backwards Links for a Predicate}
From this, we can recover the {\em backwards} set of all {\em predicate implication links} for a predicate $\qvariable$:
\begin{equation}
B_\Psi(\qvariable) = \left\{\Psi(\hvariable, \qvariable') \in \mathcal{K} \condsep \qvariable' = \qvariable \right\}
\end{equation}
It is also possible to define a {\em forwards} set but we do not need to here.
\subsection{Abstraction and Backwards Substitution}
\paragraph{Abstraction}
For any {\em proposition} \pvariable, whose role set is $\rvariable$, we can {\em abstract} any subset of the roles in $\rvariable$ to reveal a predicate $\qvariable$.
For example, for the proposition:
\begin{equation} \pvariable = (\textsc{like}, \left\{\textsc{subj}: \constant{jack1}, \textsc{dobj}: \constant{jill1} \right\})\end{equation}
Abstracting $\left\{\textsc{subj}, \textsc{dobj}\right\}$ would leave:
\begin{equation}
\qvariable = (\textsc{like}, \left\{\textsc{subj}: \xjack, \textsc{dobj}: \xjill \right\})
\label{eq:}
\end{equation}
Though {\em abstracting} over all variables at once can be considered the {\em standard abstraction}, we can abstract partially
in $2^n - 1$ different ways, as $\pvariable$ is not included as an {\em abstraction} of itself, because it has no open roles.
We will write that $\qvariable \in \pvariable$ if $\qvariable$ is an abstraction of $\pvariable$.
\paragraph{Backwards Substitution}
Suppose that $\qvariable$ is an abstraction of $\pvariable$, i.e. $\qvariable \in \pvariable$.
And, suppose that $\Psi(\hvariable, \qvariable)$ is an implication link.
We can define:
\begin{equation}
backfill(\pvariable, \Psi(\hvariable, \qvariable)) = \text{unique }\gvariable\text{ such that }\Psi(\hvariable, \qvariable)\text{ links $\gvariable$ to } \pvariable
\end{equation}
This function can be computed because we stored the {\em role mapping pair} for each $\qvariable_a \in \hvariable$ and $\qvariable$, for each $\Psi(\hvariable, \qvariable)$ in the implication graph.
\subsection{Proposition Factors and Contexts}
\paragraph{Proposition Factor}
Suppose we have a proposition $\pvariable$, which contains the predicate $\qvariable$, which matches an implication link $\Psi(\hvariable, \qvariable)$.
We can call
$backfill(\pvariable, \Psi(\hvariable, \qvariable))$ to obtain some $\gvariable$, an instance of $\hvariable$, obtained by following backwards an instance of the link $\Psi(\hvariable, \qvariable)$.
$\gvariable = \pvariable_1 \land ... \land \pvariable_n$ is a conjunction of propositions, and so has a {\em probability}, unlike $\hvariable$, which is a predicate. These objects are all bundled up in a {\em factor} defined as:
\begin{equation}
factor(\pvariable, \Psi(\hvariable, \qvariable)) = (\pvariable, \Psi(\hvariable, \qvariable), \gvariable)
\end{equation}
The {\em factor} contains both the causally related proposition group $\gvariable$, and also the {\em implication link} $\Psi(\hvariable, \qvariable)$ used to link $\gvariable$ and $\pvariable$.
\paragraph{Proposition Factor Context}
For a given proposition $\pvariable$, its {\em factor context} is:
\begin{equation}
\textsc{context}(\pvariable) =
\bigcup_{\substack{\qvariable \in \pvariable}}\
\bigcup_{\substack{\hvariable \in \backlinks (\qvariable)}}
factor(\pvariable, \Psi(\hvariable, \qvariable))
\end{equation}
This is the set of all {\em factors} created from taking all {\em backwards implication links} from all {\em abstracted predicates} $\qvariable \in \pvariable$.
The factor context is the input to the learned {\em linear exponential} model used to score the \opor\ gates, $\Psi_\opor$.
\paragraph{Markov Assumption}
In terms of the {\em Markov assumption}, the node $\pvariable$ is independent of all its ancestors given its {\em factor context}.
That is, the {\em factor context} contains the set of all {\em direct causes} for $\pvariable$, according to the current {\em theory}.
\subsection{Inference-Time Proposition Graph Creation}
When we are interested in a query $\pvariable$, we have to construct the graph of relevant proprositions {\em on the fly} at inference time, because we cannot store all propositions.
Suppose we are interested in a certain target query $\pvariable$, which for simplicity for now assume has only ancestors, and no descendents in the graph.
We can determine $context(\pvariable)$, which will get all of the conjoined nodes $\gvariable$ that are {\em parents} of $\pvariable$.
Each $\gvariable_z = \pvariable_{z_1} \wedge ... \wedge \pvariable_{z_n}$ is a conjunction of $\pvariable_{z_i}$, and for each of these we can recursively call $factor(\pvariable_{z_i})$, and so on, until we have created a {\em proposition graph} of all propositions {\em relevant to} $\pvariable$.
Because of the {\em Markov assumption}, any node not reached through this traversal is not relevant to $\pvariable$.
During the construction of this graph, we can do book-keeping to store, for each $\pvariable$ and $\gvariable$ discovered, the {\em forward} and {\em backward} links for each node of each type.
\subsection{Feature Function}
\label{s:feature_function}
The feature function $\phi(\pvariable, \gvariable)$ characterizes the {\em implication link} between the conclusion $\pvariable$ and the assumption $\gvariable$:
\begin{equation}
\phi(\pvariable = p, \gvariable = g) = (p, \Psi(\hvariable, \qvariable), g)
\end{equation}
That is, the feature $\phi(\pvariable = p, \gvariable = g)$ is a {\em triple} indicating:
\begin{enumerate}
\item The value $p \in \left\{0, 1\right\}$ that $\pvariable$ takes in $\phi(\pvariable = p, \gvariable = g)$.
\item The implication link $\Psi(\hvariable, \qvariable)$ used to arrive at $\pvariable$ from $\gvariable$.
\item The value $g \in \left\{0, 1\right\}$ that $\gvariable$ takes on in $\phi(\pvariable = p, \gvariable = g)$.
\end{enumerate}
We usually just write $\phi(\pvariable, \gvariable)$, and assume that the $\Psi(\hvariable, \qvariable)$ is implied.
It {\em is} possible for the same $\pvariable$ and $\gvariable$ to have more than one link, which would result in more than one feature.
The {\em feature vector} for the entire {\em factor context} is the union over each of the individual {\em proposition factors}.
\section{Inference}
\label{sec:inference}
\subsection{The Probability Query}
We are interested in the \textit{probability query}, which consists of two parts:
\begin{itemize}
\item The {\em query variables}: a subset \( \pvariableset_Q \) of all variables in the network.
\item The {\em evidence}: a subset \( \pvariableset_E \) of random variables in the network, {\em observed} to have the values \( \left\{p\right\}_E\).
\end{itemize}
The task is to compute the {\em posterior distribution}:
\begin{equation}
P( \pvariableset_Q \mid \pvariableset_E = \left\{p\right\}_E)
\end{equation}
\subsection{Marginalization}
In the presence of unobserved variables \( \pvariableset_U \), not part of the query or evidence, marginalization is used to sum out these variables from the joint probability distribution. The marginalization process is represented by the following equation:
\begin{equation}
P(\pvariableset_Q \mid \pvariableset_E) = \sum_{\pvariableset_U} P(\pvariableset_Q, \pvariableset_U \mid \pvariableset_E)
\end{equation}
In general, in a Bayesian Network, this process if $\Omega(2^N)$ to compute {\em exactly}, or even to {\em provably approximate} \cite{Cooper1990,Roth1996HardnessApproxReasoning}.
\subsection{Iterative Belief Propagation}
Inference can be performed in a graphical model using {\em belief propagation} \cite{koller2009probabilistic,neapolitan2003learning,bishop2006pattern}, if the graph contains even {\em undirected cycles}, which it often would, {\em exact} belief propagation is not tractable.
However, empirical results suggest that {\em loopy belief propagation}, which we will call {\em iterative belief propagation}, does converge well empirically, even though there are no theoretical guarantees \cite{Murphy2013, Smith2008}.
We discuss the complexity of this operation in detail in Section \ref{sec:complexity}.
\subsection{Message Passing Calculations}
\paragraph{Notation}
We implement the variant of \cite{pearl1988probabilistic}'s {\em belief propagation} algorithm presented in \cite{neapolitan2003learning}.
In this formulation, we have $\pi$ {\em values} and $\lambda$ {\em values}, and $\pi$ {\em messages} and $\lambda$ {\em messages}.
For factor computations, we distinguished between {\em single propositions} $\pvariable$ and {\em proposition groups} $\gvariable$.
However, for the message passing calculations we adopt a unified notation, where both $\pvariable$ and $\gvariable$ nodes can be viewed as a unified node $\zvariable$ that can wrap either type, and the message passing calculations are agnostic to the type.
We use $\cvariable$ to canonically refer to a {\em child} of $\zvariable$ and $\avariable$ for a {\em parent} of $\zvariable$.
\paragraph{Computations}
The version we present here involves exponential cost $O(2^n)$ sums over either the parents or children of $z$.
In Section \ref{sec:complexity}, we discuss how the {\em independence} of $\Psi_\opor$ factors can, for some distributions like {\em Noisy Or}, allow the $O(2^n)$ update to be done in {\em linear} $O(n)$ time.
\paragraph{Values}
$\pi(z)\in \mathbb{R}$, called the $\pi$ {\em value} for $\zvariable = z$, represents beliefs flowing {\em forward} in the network, from {\em causes} to {\em effects}, and is:
\begin{equation}
\pi(z) = \sum_{a_1, \ldots, a_n} \left( P(z \mid a_1, \ldots, a_n) \prod_{a_i} \pi_\zvariable(a_i) \right).
\label{eq:slow_pi_calc}
\end{equation}
$\lambda(z)\in \mathbb{R}$, called the $\lambda$ {\em value} for $\zvariable = z$, represents beliefs flowing {\em backward} in the network, from {\em effects} to {\em causes}, and is:
\begin{equation}
\lambda(z) = \prod_{\cvariable} \lambda_{\cvariable}(z)
\end{equation}
These two values are normalized and combined to compute the {\em posterior} probability:
\begin{equation}P(z \condsep \left\{p\right\}_E) = \alpha\lambda(z)\pi(z) \end{equation}
\paragraph{Messages}
$\pi_\zvariable(a) \in \mathbb{R}$ is $\avariable$'s message to a {\em child} $\zvariable$:
\begin{equation}
\pi_\zvariable(a) = \pi(a) \prod_{(\yvariable \in \zvariable) - \avariable} \lambda_\yvariable(z)
\end{equation}
$\lambda_\cvariable(z) \in \mathbb{R}$ is $\cvariable$'s message to a {\em parent} $\zvariable$, where the ${\bf b}_i$ are the other parents of $\cvariable$:
\begin{equation}
\lambda_\cvariable(z) = \sum_{c} \left[ \sum_{b_1, b_2, \ldots, b_n} \left( P(c \mid z, b_1, b_2, \ldots, b_n) \prod_{b_i} \pi_\cvariable(b_i) \right) \lambda(c) \right]
\label{eq_slow_lambda_calc}
\end{equation}
\section{Complexity of Inference}
\label{sec:complexity}
\subsection{Provably Exact Inference}
Inference in a general Bayesian Network is $\Omega(2^N)$ for $N$ variables, and is even $\Omega(2^N)$ to {\em provably} approximate \cite{Cooper1990, Roth1996HardnessApproxReasoning}.
\subsection{Empirically Successful Iterative Belief Propagation}
The {\em iterative belief propagation} ({\em loopy belief propagation} in the literature) is {\em not} guaranteed to converge \cite{neapolitan2003learning, koller2009probabilistic}, but {\em has been found} to converge in practice in a range of studies \cite{Smith2008, Murphy2013, Gormley2015}.
And, we have found it to converge in our experiments, which so far are small, but exhibit a recursive structure, and so thus may scale.
The primary cost of {\em inference} in this case is the computation of the {\em messages and values} of the $\pi$ and $\lambda$ tables (see Section \ref{sec:inference})
Using a perhaps {\em naive} implementation, in which the marginalization is exact (see \ref{eq:slow_pi_calc} and \ref{eq_slow_lambda_calc}), runs in time $O(2^n)$ in $n$ the number of {\em inputs} to the {\em factor}.
Then, a single pass of belief propagation visits each of the $N$ nodes once, taking total time $O(N2^n)$, and empirically $k$ rounds are needed to converge.
We remark that it may be possible to make both $\Psi_\opand$ and $\Psi_\opor$ gates faster $O(n)$, but future work must investigate.
\subsection{Faster Disjunction}
\label{sec:noisy_or}
\paragraph{Overview}
The $\Psi_\opor$ factor is {\em learned} when we want to do statistical inference, and the factor
\[\Psi_\opor(\pvariable \condsep \gvariable_1, ..., \gvariable_n)\]
has one input $n$ per {\em modeled cause} $\gvariable_i$ of $\pvariable$.
Conceptually, outcomes have an unbounded number of potential causes, and we would ideally not need to restrict $n$ solely because of message passing complexity.
\paragraph{Importance Sampling}
One option is to {\em learn} an unbounded number $n$ of weights, but only {\em consider at inference} a {\em subset} of the inputs that are most {\em relevant}.
That is, in the {\em linear exponential} model \ref{e_linear_exponential}, we can detect which of $m < n$ linear contributions will have the biggest effect, and only marginalize over those, costing $O(2^m) < O(2^n)$.
This strategy would be a variant of {\em importance sampling} \cite{wilkinson2005grammar}.
\paragraph{Linear Time Disjunction}
\cite{neapolitan2003learning} lists at least one disjunction model, the {\em Noisy Or} model, whose message passing calculations are $O(n)$, instead of $O(2^n)$ in $n$ the number of inputs to the factor.
We leave it to future work to determine whether this model, or another model with similar scaling properties, can be useful in practice.
\subsection{Faster Conjunction}
The complexity of {\em message updates} in a {\em conjunction} $\Psi_\opand$ gate is $O(2^n)$ in the number of inputs $n$.
However, an \opand\ gate can be arranged into a {\em binary tree} of \opand\ gates each of size $2$, with the tree height $\log_2(n)$, in which case there would be only $O(n)$ work in total to evaluate the $n$ inputs.
However, this would increase the amount of message passing, so we leave it to future work to evaluate whether this is beneficial.
\section{Future Work}
\paragraph{Learning from Unlabeled Text}
We have said that the {\em QBBN} can encode knowledge, and do so {\em without hallucinating}, which compares favorably with the {\em LLM} \cite{Bahdanau2014NeuralMT, vaswani2017attention, radford2018improving}.
However, the difficulty compared to the {\em LLM} is that the {\em QBBN} {\em cannot} be learned in the same {\em direct} {\em $n$-gram language model} way as the {\em LLM}, but instead must refer to {\em logical forms} which are {\em not observed} but viewed as {\em latent} and must be learned through {\em expectation maximization} \cite{dempster1977maximum}.
\paragraph{Belief Propagation}
We have used {\em loopy belief propagation}, calling it {\em iterative belief propagation}, which is not guaranteed to converge but has been studied somewhat extensively \cite{Murphy2013, Smith2008, Gormley2015}, and our experiments also find convergence.
However, convergence for larger graphs should be studied, as well as strategies to speed up belief propagation.
\paragraph{Logical Language Features}
We have shown enough about the underlying logical language of the {\em QBBN} to encode {\em basic} first-order sentences.
But, there remain the topics of {\em compositional semantics} \cite{montague1970universal}, which shows how the meanings of {\em larger parts} are made from {\em smaller parts}, and {\em intensional} semantics \cite{montague1973proper}, which shows how {\em the concept} behind a sentence can itself be an argument.
% bibliography
% \bibliographystyle{apalike}
% \bibliography{bibtex}
\begin{thebibliography}{}
\bibitem[Bahdanau et~al., 2014]{Bahdanau2014NeuralMT}
Bahdanau, D., Cho, K., and Bengio, Y. (2014).
\newblock Neural machine translation by jointly learning to align and
translate.
\newblock {\em CoRR}, abs/1409.0473.
\bibitem[Bar-Hillel, 1953]{BarHillel1953}
Bar-Hillel, Y. (1953).
\newblock A quasi-arithmetical notation for syntactic description.
\newblock {\em Language}, 29(1):47--58.
\bibitem[Bishop, 2006]{bishop2006pattern}
Bishop, C.~M. (2006).
\newblock {\em Pattern Recognition and Machine Learning}.
\newblock Springer.
\bibitem[Chomsky, 1965]{Chomsky1965Aspects}
Chomsky, N. (1965).
\newblock {\em Aspects of the Theory of Syntax}.
\newblock MIT Press, Cambridge, MA.
\newblock Available online: \url{https://mitpress.mit.edu}.
\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, 2024]{Coppola2024}
Coppola, G. (2024).
\newblock A mathematical explanation for ``{Thinking Fast and Slow}''.
\newblock Bitcoin Ordinal NFT.
\newblock 72494446539c7fcb73becde763fc4bbbf0686b9c30cd8188e50861ccde0a5c83i0.
\bibitem[Dempster et~al., 1977]{dempster1977maximum}
Dempster, A.~P., Laird, N.~M., and Rubin, D.~B. (1977).
\newblock Maximum likelihood from incomplete data via the em algorithm.
\newblock {\em Journal of the Royal Statistical Society: Series B
(Methodological)}, 39(1):1--38.
\bibitem[Eisner, 2000]{eisner1996bilexical}
Eisner, J. (2000).
\newblock Bilexical grammars and their cubic-time parsing algorithms.
\newblock In {\em Advances in probabilistic and other parsing technologies},
pages 29--62. Springer.
\bibitem[Gentzen, 1934]{Gentzen1934}
Gentzen, G. (1934).
\newblock Untersuchungen {\"u}ber das logische schlie{\ss}en.
\newblock {\em Mathematische Zeitschrift}, 39:176--210, 405--431.
\bibitem[Gilks et~al., 1996]{gilks1996markov}
Gilks, W.~R., Richardson, S., and Spiegelhalter, D.~J., editors (1996).
\newblock {\em Markov Chain Monte Carlo in Practice}.
\newblock Chapman and Hall/CRC.
\bibitem[G{\"o}del, 1930]{Godel1930}
G{\"o}del, K. (1930).
\newblock On the completeness of the calculus of logic.
\newblock {\em Monatshefte f{\"u}r Mathematik und Physik}, 37:349--360.
\bibitem[Gormley et~al., 2015]{Gormley2015}
Gormley, M.~R., Dredze, M., and Eisner, J. (2015).
\newblock Approximation-aware dependency parsing by belief propagation.
\newblock {\em Transactions of the Association for Computational Linguistics},
3:489--501.
\bibitem[Kahneman, 2011]{Kahneman2011ThinkingFast}
Kahneman, D. (2011).
\newblock {\em Thinking, Fast and Slow}.
\newblock Farrar, Straus and Giroux, New York.
\bibitem[Koller and Friedman, 2009]{koller2009probabilistic}
Koller, D. and Friedman, N. (2009).
\newblock {\em Probabilistic Graphical Models: Principles and Techniques}.
\newblock MIT Press.
\bibitem[LeCun, 2023]{Lecun2023}
LeCun, Y. (2023).
\newblock From machine learning to autonomous intelligence.
\newblock Ludwig-Maximilians-Universität München, YouTube.
\newblock Accessed: 2024-01-29.
\bibitem[Lewis and Steedman, 2013]{Lewis2013}
Lewis, M. and Steedman, M. (2013).
\newblock Combined distributional and logical semantics.
\newblock {\em Transactions of the Association for Computational Linguistics},
1:179--192.
\bibitem[McDonald et~al., 2005]{mcdonald2005non}
McDonald, R., Pereira, F., Ribarov, K., and Haji{\v{c}}, J. (2005).
\newblock Non-projective dependency parsing using spanning tree algorithms.
\newblock In {\em Proceedings of the conference on Human Language Technology
and Empirical Methods in Natural Language Processing}, pages 523--530.
\bibitem[Minsky and Papert, 1969]{minsky1969perceptrons}
Minsky, M. and Papert, S. (1969).
\newblock {\em Perceptrons: An Introduction to Computational Geometry}.
\newblock MIT Press.
\bibitem[Montague, 1970]{montague1970universal}
Montague, R. (1970).
\newblock Universal grammar.
\newblock {\em Theoria}, 36:373--398.
\newblock Reprinted in Thomason, Richmond H. (ed.), Formal Philosophy: Selected
Papers of Richard Montague, pp. 7--27, Yale University Press, 1974.
\bibitem[Montague, 1973]{montague1973proper}
Montague, R. (1973).
\newblock The proper treatment of quantification in ordinary english.
\newblock In Hintikka, J., Moravcsik, J. M.~E., and Suppes, P., editors, {\em
Approaches to Natural Language}, pages 221--242, Dordrecht. D. Reidel.
\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[Murphy et~al., 2013]{Murphy2013}
Murphy, K.~P., Weiss, Y., and Jordan, M.~I. (2013).
\newblock Loopy belief propagation for approximate inference: An empirical
study.
\newblock {\em CoRR}, abs/1301.6725.
\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[Pelletier, 2000]{Pelletier2000}
Pelletier, F.~J. (2000).
\newblock A history of natural deduction and elementary logic textbooks.
\newblock {\em Logical consequence: Rival approaches}, 1:105--138.
\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[Richardson and Domingos, 2006]{richardson2006markov}
Richardson, M. and Domingos, P. (2006).
\newblock Markov logic networks.
\newblock {\em Machine learning}, 62:107--136.
\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, 2008a]{Smith2008}
Smith, D. and Eisner, J. (2008a).
\newblock Dependency parsing by belief propagation.
\newblock In Lapata, M. and Ng, H.~T., editors, {\em Proceedings of the 2008
Conference on Empirical Methods in Natural Language Processing}, pages
145--156, Honolulu, Hawaii. Association for Computational Linguistics.
\bibitem[Smith and Eisner, 2008b]{smith2008dependency}
Smith, D.~A. and Eisner, J. (2008b).
\newblock Dependency parsing by belief propagation.
\newblock In {\em Proceedings of the 2008 Conference on Empirical Methods in
Natural Language Processing}, pages 145--156.
\bibitem[Steedman, 1996]{Steedman1996}
Steedman, M. (1996).
\newblock {\em Surface Structure and Interpretation}.
\newblock The MIT Press.
\bibitem[Sutskever, 2023]{SutskeverObservation}
Sutskever, I. (2023).
\newblock An observation on generalization.
\newblock Simons Institute, YouTube.
\newblock Accessed: 2024-01-29.
\bibitem[Vaswani et~al., 2017a]{vaswani2017attention}
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.~N.,
Kaiser, L., and Polosukhin, I. (2017a).
\newblock Attention is all you need.
\newblock In {\em Advances in Neural Information Processing Systems},
volume~30.
\bibitem[Vaswani et~al., 2017b]{Vaswani2017}
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.~N.,
Kaiser, L., and Polosukhin, I. (2017b).
\newblock Attention is all you need.
\newblock In {\em Advances in Neural Information Processing Systems},
volume~30.
\bibitem[Wilkinson, 2005]{wilkinson2005grammar}
Wilkinson, L. (2005).
\newblock {\em The Grammar of Graphics}.
\newblock Springer, 2 edition.
\bibitem[Zhang and Nivre, 2011]{zhang2011transition}
Zhang, Y. and Nivre, J. (2011).
\newblock Transition-based dependency parsing with rich non-local features.
\newblock In {\em Proceedings of the 49th Annual Meeting of the Association for
Computational Linguistics: Human Language Technologies}, pages 188--193.
\end{thebibliography}
% end
\end{document}#59,925,880text\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}
\begin{document}
\newcommand{\aset}{{\bf A}}
\newcommand{\cset}{{\bf C}}
\newcommand{\dset}{{\bf d}}
\title{\bf A Mathematical Explanation for\\
{\em Thinking Fast and Slow}
\thanks{The self-contained source code for this article was published as a {\em Bitcoin Ordinal NFT} to the Bitcoin address {\em bc1pvd4selnseakwz5eljgj4d99mka25mk8pp3k7v7hc6uxw8txy6lgsf7lmtg} on {\em February 1, 2024}.}
}
\author{
{\Large Greg Coppola}
\\
{\em coppola.ai} \\
Research. Develop. Meme.
}
\date{\today}
\maketitle
\section*{Overview}
\paragraph{Thinking Fast and Slow}
\cite{Kahneman2011ThinkingFast} introduces an influential distinction between {\em fast} and {\em slow} forms of {\em thinking},
in which {\em fast} thinking is {\em effortless} and {\em automatic}, and {\em slow} thinking {\em requires effort}, or involves {\em complex calculations}.
\paragraph{No Current Explanation}
To our knowledge, there is no {\em explanation} of this distinction based on {\em computer science}.
We present a possible explanation for the distinction between {\em fast} and {\em slow} thinking based on the formulation of \cite{Gentzen1934}'s {\em natural deduction calculus} given in \cite{PrawitzNaturalDeduction}.
\paragraph{A Hypothesis Based on Formal Logic}
\cite{PrawitzNaturalDeduction} distinguishes between {\em proper} and {\em improper} deduction rules, which we, for clarity in the modern context, call instead {\em simple} and {\em complex} deduction rules.
We propose the following {\em hypothesis}: the {\em fast} thoughts of \cite{Kahneman2011ThinkingFast} correspond to those consisting only of proofs using the {\em simple} deduction rules of \cite{PrawitzNaturalDeduction}, which correspond to those deductions we can implement in a single {\em probability query} through {\em forward pass} (see \cite{koller2009probabilistic}) in the {\em Quantified Boolean Bayesian Network} \cite{Coppola2024}.
\section*{First-Order Theorem-Proving}
\paragraph{Overview}
A {\em theorem} is a pair $\dset = \left( \aset, \cset \right)$, where $\aset$ is set of {\em assumptions} and $\cset$ is a set of {\em conclusions}, such that each $\aset$ and $\cset$ is a subset of the possible {\em sentences} in a {\em logical language} $\ell$ of interest.
A {\em proof} of $\dset$ in the calculus $\Gamma_\ell$ is a {\em sequence} of {\em deduction steps} $\gamma_\dset = [d_1, ..., d_n]$, that {\em derive} $\dset$.
Given a theorem $\dset$ and a sequence $\gamma_\dset$, we can trivially verify whether $\gamma_\dset$ {\em constitutes a valid proof} of $\dset$.
In such a case, we say that $\left(\aset, \cset\right)$ is {\em provable} in $\Gamma_\ell$.
\paragraph{Consistency and Completeness}
We say that a set $\cset$ is {\em true} given $\aset$, if {\em every model satisfying} $\aset$, that honors the meaning of the {\em logical connectives} ($\land$, $\lor$, $\rightarrow$, $\forall$, $\exists$ and $\bot$), must also satisfy $\cset$.
The {\em first-order} calculus is so useful because it is {\em consistent}, meaning that everything {\em provable} is {\em true} and {\em complete}, meaning that everything {\em true} is {\em provable} \cite{Godel1931, Gentzen1934}.
\paragraph{Undecidability of First-Order Theorem-Proving}
While the task of {\em verifying} whether $\gamma_\dset$ is a valid proof of $\dset$ is trivial, the task of {\em deciding} whether $\dset$ {\em has} a proof is related to the {\em halting problem}, and is undecidable in general \cite{Turing1936, Church1936}.
That is, there is no universal program that can take an {\em arbitrary theorem} $\left( \aset, \cset \right)$ and say whether it has a proof.
\paragraph{NP-Hardness of Propositional Theorem-Proving}
If we remove the quantifiers $\forall$ and $\exists$, we are left with the {\em propositional calculus}.
Proving a theorem in this calculus corresponds to deciding {\em boolean satisfiability}, and this {\em is decidable}, but is {\em NP-hard} in general \cite{Cook1971}, which is to say $\Omega(2^N)$ where $N$ is the number of boolean variables.
\paragraph{Commentary}
As some {\em theorem-proving} classes are {\em undecidable}, and others are {\em NP-hard}, we should {\em expect} that some {\em thinking} is {\em slow}.
However, the existince of {\em fast} thinking is evident {\em empirically} \cite{Kahneman2011ThinkingFast}.
So, our task is to {\em theoretically} draw a line between the two.
\section*{Prawitz's Natural Deduction}
\subsection*{Overview}
\cite{PrawitzNaturalDeduction} examines {\em twelve} inference rules, one {\em Introduction rule} and one {\em Elimination rule} for each of the six {\em logical connectives} ($\land$, $\lor$, $\rightarrow$, $\forall$, $\exists$ and $\bot$).
An {\em inference rule} $R$ licenses a {\em conclusion} $(\aset_c, \cset_c)$ based on a set of {\em premises} $\left\{(\aset_p, \cset_p)\right\}_{p\in R}$, whose form is determined by $R$.
\cite{PrawitzNaturalDeduction} introduces a distinction between what he called {\em proper} and {\em improper} deduction rules.
We will refer to the same distinction, but call them {\em simple} and {\em complex} deduction rules.
The {\em simple} rules are those for which $\aset_c = \aset_p$ for all $p \in R$.
That is, the {\em simple} inferences are those in which the assumptions are the same $\aset_c = \aset_p = \aset$ for each of the {\em premises} and the {\em conclusion} of the {\em deduction rule}.
The deduction rules which are not {\em simple} are called {\em complex}.
In the {\em complex} inferences, the assumptions {\em change}, and this requires {\em book-keeping} to keep track of.
We will consider some {\em illustrative examples}.
\subsection*{Examples}
Overall, there are {\em six} connectives ($\land$, $\lor$, $\rightarrow$, $\forall$, $\exists$ and $\bot$), each with an {\em Introduction} and an {\em Elimination} rule in \cite{PrawitzNaturalDeduction}'s calculus.
We will review {\em three} of the connectives that highlight the properties of interest, and save a longer discussion for future work.
\subsubsection*{$\land$ Rules}
The operator $\land$ is pronounced {\em and}, and the rules of {\em $\land$-Introduction} and {\em $\land$-Elimination} are depicted intuitively as:
\begin{equation}
\begin{tabular}{c c}
$\land$-Introduction &
\begin{minipage}{.5\textwidth}
\begin{prooftree}
\AxiomC{$A$}
\AxiomC{$B$}
\BinaryInfC{$A \land B$}
\end{prooftree}
\end{minipage}
\\
\vspace{10pt}
\\
$\land$-Elimination &
\begin{minipage}{.5\textwidth}
\begin{prooftree}
\AxiomC{$A \land B$}
\UnaryInfC{$A, B$}
\end{prooftree}
\end{minipage}
\end{tabular}
\end{equation}
Expressed formally, {\em $\wedge$-Introduction} says:
\begin{equation}
\left\{\left(\aset_0 \cup \left\{A, B\right\}, \cset_0\right)\right\} \rightarrow \left(\aset_0 \cup \left\{A, B\right\}, \cset_0 \cup \left\{A \wedge B\right\}\right)
\end{equation}
That is, if we have concluded $A$ and $B$, we can conclude $A \wedge B$.
This inference rule is {\em simple} because the $\aset$ in both premise and conclusion is the same, i.e. $\aset_0 \cup \left\{A, B\right\}$.
Conversely, {\em $\wedge$-Elimination} says:
\begin{equation}
\left\{\left(\aset_0 \cup \left\{A \wedge B\right\}, \cset_0\right)\right\} \rightarrow \left(\aset_0 \cup \left\{A \wedge B\right\}, \cset_0 \cup \left\{A, B\right\}\right)
\end{equation}
That is, if we have concluded $A \wedge B$, we can conclude both $A$ and $B$.
This inference rule is {\em simple} because the $\aset$ in both premise and conclusion is the same, i.e. $\aset_0 \cup \left\{A \wedge B\right\}$.
$\land$ is unique for being the only of the {\em six} rules whose {\em Introduction} and {\em Elimination} rules are both {\em simple}, and in this sense $\land$ may be viewed as the ``simplest'' logical connective.
\subsection*{$\rightarrow$ Rules}
The symbol $\rightarrow$ is pronounced {\em implies} and the rules for $\rightarrow$ are more typical, in that one is {\em simple} and one is {\em complex}:
\begin{equation}
\begin{tabular}{c c}
$\rightarrow$-Introduction &
\begin{minipage}{.5\textwidth}
% Implication Introduction
\begin{prooftree}
\AxiomC{[A]}
\noLine
\UnaryInfC{$\vdots$}
\noLine
\UnaryInfC{$B$}
\UnaryInfC{$A \rightarrow B$}
\end{prooftree}
\end{minipage}
\\
\vspace{10pt} % Adjust the 10pt to the amount of space you need
\\
$\rightarrow$-Elimination &
\begin{minipage}{.5\textwidth}
% Implication Elimination (Modus Ponens)
\begin{prooftree}
\AxiomC{$A$}
\AxiomC{$A \rightarrow B$}
\BinaryInfC{$B$}
\end{prooftree}
\end{minipage}
\end{tabular}
\end{equation}
Starting with the {\em simple} {\em $\rightarrow$-Elimination}, we have:
\begin{equation}
\left\{\left(\aset_0 \cup \left\{A, A \rightarrow B\right\}, \cset_0\right)\right\} \rightarrow \left(\aset_0 \cup \left\{A, A \rightarrow B\right\}, \cset_0 \cup \left\{B\right\}\right)
\end{equation}
That is, if we have concluded $A$ and $A \rightarrow B$, we can conclude $B$.
This is simple because the $\aset$ does not change between premises and conclusion, i.e. $\aset_0 \cup \left\{A, A \rightarrow B\right\}$.
{\em $\rightarrow$-Introduction} is {\em complex} and says:
\begin{equation}
\left\{\left(\aset_0 \cup \left\{A\right\}, \cset_0 \cup \left\{B\right\}\right)\right\} \rightarrow \left(\aset_0 \cup \left\{\right\}, \cset_0 \cup \left\{A \rightarrow B\right\}\right)
\end{equation}
That is, if assuming $A$ lets us prove $B$, then we can {\em discharge} the assumption $A$ and conclude $A \rightarrow B$.
This is {\em complex} because it involves a change of assumptions between {\em premise} and {\em conclusion}.
We remark that this rule is used more by {\em professional mathematicians} engaged in thoretical {\em theorem proving}, whereas in {\em everday life} people are usually content to just conlude $B$, without {\em proving} that they {\em necessarily} did so.
This again corresponds to the difference between {\em simple} inferences, that we make routinely, and {\em complex} inferences, that require {\em specialists} and even expensive {\em research programs} to arrive at.
\subsection*{$\lor$ Rules}
The operator $\lor$ is pronounced {\em or}, and, like $\rightarrow$, $\lor$ rules include one {\em simple} and one {\em complex} rule.
While $\lor$ is more complicated than $\wedge$, there is a sense in which it is relatively {\em simple} compared to the other {\em complex} rules.
$\lor$ rules are depicted intuively as:
\begin{equation}
\begin{tabular}{c c}
$\lor$-Introduction &
\begin{minipage}{.5\textwidth}
\begin{minipage}{.5\textwidth}
\begin{prooftree}
\AxiomC{$A$}
\UnaryInfC{$A \lor B$}
\end{prooftree}
\end{minipage}%
\begin{minipage}{.5\textwidth}
\begin{prooftree}
\AxiomC{$B$}
\UnaryInfC{$A \lor B$}
\end{prooftree}
\end{minipage}
\end{minipage}
\\
\vspace{10pt} % Adjust the 10pt to the amount of space you need
\\
$\lor$-Elimination &
\begin{minipage}{.5\textwidth}
% Or Elimination
\begin{prooftree}
\AxiomC{$A \lor B$}
\AxiomC{[A]}
\noLine
\UnaryInfC{$\vdots$}
\noLine
\UnaryInfC{$C$}
\AxiomC{[B]}
\noLine
\UnaryInfC{$\vdots$}
\noLine
\UnaryInfC{$C$}
\TrinaryInfC{$C$}
\end{prooftree}
\end{minipage}
\end{tabular}
\end{equation}
Expressed formally, {\em $\lor$-Introduction} says:
\begin{equation}
\left\{\left(\aset_0 \cup \left\{A\right\}, \cset_0\right)\right\} \rightarrow \left(\aset_0 \cup \left\{A\right\}, \cset_0 \cup \left\{A \lor B\right\}\right)
\end{equation}
Intuitively, if we have concluded $A$ (alternatively, $B$), we can conclude $A \lor B$.
This corresponds to a {\em disjunction} gate in the {\em QBBN}.
{\em $\lor$-Elimination} says:
\begin{equation}
\left\{
\begin{aligned}
&\left(\aset_0 \cup \left\{\right\}, \cset_0 \cup \left\{A \lor B\right\}\right) \\
&\left(\aset_0 \cup \left\{A\right\}, \cset_0 \cup \left\{C\right\}\right) \\
&\left(\aset_0 \cup \left\{B\right\}, \cset_0 \cup \left\{C\right\}\right)
\end{aligned}
\right\}
\rightarrow \left(\aset_0, \cset_0 \cup \left\{C\right\}\right)
\end{equation}
This amounts to a {\em proof by cases}, in which we can {\em discharge} $A \lor B$ in a proof of $C$ if we can prove both $A$ and $B$ hold.
This step is {\em complex}, because it requires a changing of assumptions.
However, unlike the even more complex {\em complex} rules, {\em reasoning by cases} does {\em not} require creative application of the rules, because the disjunction $A \lor B$ tells us which proofs we need to look for, i.e. $A\rightarrow C$ and $B \rightarrow C$.
A proof system comprising only the {\em simple} inferences, along with {\em $\lor$-disjunction} would correspond to \cite{Cook1971}'s {\em NP-hardness} result about the {\em propositional calculus}, in which a proof can always be found, but may require exhaustive search, which would be {\em slow}.
\section*{Commentary}
\paragraph{Linear-Time Inference in a Bayesian Network}
In contrast to the {\em undecidability} of {\em general} first-order theorem-proving, and the {\em NP-hardness} of {\em propositional calculus} theorem-proving, we have implemented in the {\em Quantified Boolean Bayesian Network} \cite{Coppola2024} the most empirically useful rules in practice of the {\em simple deduction} rules (and could implement the others if there were a reason to do so).
In this network, with the theoretically unguaranteed but empirically successful {\em iterative belief propagation} algorithm (called {\em loopy} belief propagation in the literature \cite{koller2009probabilistic}), we can do one pass of {\em forwards} (and even {\em backwards}) inference in time bounded by $O(N2^n)$, where $N$ is the number of variables, and $n$ is the maximum incoming size for any {\em junction node}, whether {\em conjunction} ($\land$) or {\em disjunction} ($\lor$).
Given that $n$ is much smaller than $N$, this is linear in $N$, which is {\em fast}.
Thus, we can say that this class of inferences models {\em fast} thinking.
\paragraph{A Hypothesis}
We propose that the following {\em three} classes of {\em inferences} are equivalent:
\begin{enumerate}
\item Those inferences called {\em simple} by \cite{PrawitzNaturalDeduction}, i.e., those in which the {\em deduction rule} does {\em not} involve {\em changes in assumptions}.
\item Those inferences that can be modeled in a single {\em forward} pass in the {\em Quantified Boolean Bayesian Network} \cite{Coppola2024}.
\item Those human inferences that \cite{Kahneman2011ThinkingFast} proposed to call {\em fast}.
\end{enumerate}
Conversely, the inferences that are not {\em fast}, the same in each case, are {\em slow}.
% \bibliographystyle{apalike}
% \bibliography{bibtex}
\begin{thebibliography}{9}
\bibitem[Church, 1936]{Church1936}
Church, A. (1936).
\newblock An unsolvable problem of elementary number theory.
\newblock {\em American Journal of Mathematics}, 58(2):345--363.
\bibitem[Cook, 1971]{Cook1971}
Cook, S. (1971).
\newblock The complexity of theorem-proving procedures.
\newblock In {\em Proceedings of the Third Annual ACM Symposium on Theory of
Computing}, pages 151--158, Shaker Heights, Ohio, USA. Association for
Computing Machinery.
\bibitem[Coppola, 2024]{Coppola2024}
Coppola, G. (2024).
\newblock Bayes {S}tar: An implementation of a {Q}uantified {B}oolean
{B}ayesian {N}etwork.
\newblock \url{https://github.com/gregorycoppola/bayes-star}.
\newblock GitHub repository.
\bibitem[Gentzen, 1934]{Gentzen1934}
Gentzen, G. (1934).
\newblock Investigations on logical reasoning.
\newblock {\em Mathematische Zeitschrift}, 39:176--210, 405--431.
\bibitem[Gödel, 1931]{Godel1931}
Gödel, K. (1931).
\newblock On formally undecidable propositions of principia mathematica and
related systems i.
\newblock {\em Monatshefte für Mathematik}, 38(1):173--198.
\bibitem[Kahneman, 2011]{Kahneman2011ThinkingFast}
Kahneman, D. (2011).
\newblock {\em Thinking, Fast and Slow}.
\newblock Farrar, Straus and Giroux, New York.
\bibitem[Koller and Friedman, 2009]{koller2009probabilistic}
Koller, D. and Friedman, N. (2009).
\newblock {\em Probabilistic Graphical Models: Principles and Techniques}.
\newblock MIT Press.
\bibitem[Prawitz, 1965]{PrawitzNaturalDeduction}
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[Turing, 1936]{Turing1936}
Turing, A. (1936).
\newblock On computable numbers, with an application to the
entscheidungsproblem.
\newblock {\em Proceedings of the London Mathematical Society}, 42(1):230--265.
\end{thebibliography}
\end{document}#59,367,837text/// model/objects.rs, BAYES STAR, (c) coppola.ai 2024
use serde::{Deserialize, Serialize};
use std::collections::HashMap;
use std::collections::hash_map::DefaultHasher;
use std::fmt;
use std::hash::{Hash, Hasher};
#[derive(Serialize, Deserialize, Debug, Clone, PartialEq, Eq, Hash)]
pub enum ArgumentType {
Constant,
Variable,
}
#[derive(Serialize, Deserialize, Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Domain {
Jack,
Jill,
}
impl Domain {
pub fn from_str(s: &str) -> Option<Domain> {
match s {
"Jack" => Some(Domain::Jack),
"Jill" => Some(Domain::Jill),
_ => None,
}
}
}
impl fmt::Display for Domain {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let domain_str = match self {
Domain::Jack => "Jack",
Domain::Jill => "Jill",
};
write!(f, "{}", domain_str)
}
}
#[derive(Serialize, Deserialize, Debug, Clone, PartialEq, Eq, Hash)]
pub enum Argument {
Constant(ConstantArgument),
Variable(VariableArgument),
}
#[derive(Serialize, Deserialize, Debug, Clone, PartialEq, Eq, Hash)]
pub struct ConstantArgument {
pub domain: Domain,
pub entity_id: String,
}
#[derive(Serialize, Deserialize, Debug, Clone, PartialEq, Eq, Hash)]
pub struct VariableArgument {
pub domain: Domain,
}
impl ConstantArgument {
pub fn new(domain: Domain, entity_id: String) -> Self {
ConstantArgument { domain, entity_id }
}
pub fn hash_string(&self) -> String {
self.entity_id.clone()
}
}
impl VariableArgument {
pub fn new(domain: Domain) -> Self {
VariableArgument { domain }
}
pub fn hash_string(&self) -> String {
format!("?{}", self.domain)
}
}
impl Argument {
pub fn hash_string(&self) -> String {
match self {
Argument::Constant(arg) => arg.hash_string(),
Argument::Variable(arg) => arg.hash_string(),
}
}
pub fn convert_to_quantified(&self) -> Argument {
match self {
Argument::Constant(arg) => {
Argument::Variable(VariableArgument::new(arg.domain.clone()))
}
Argument::Variable(arg) => Argument::Variable(arg.clone()),
}
}
pub fn is_constant(&self) -> bool {
match self {
Argument::Constant(_) => true,
Argument::Variable(_) => false,
}
}
pub fn is_variable(&self) -> bool {
!self.is_constant()
}
}
impl fmt::Display for ConstantArgument {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
// Customize the formatting as needed
write!(f, "{:?}", self) // For example, you can use Debug formatting here
}
}
impl fmt::Display for VariableArgument {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
// Customize the formatting as needed
write!(f, "{:?}", self) // For example, you can use Debug formatting here
}
}
impl fmt::Display for Argument {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Argument::Constant(arg) => write!(f, "Constant({})", arg), // Update as needed
Argument::Variable(arg) => write!(f, "Variable({})", arg), // Update as needed
// Add cases for other variants if they exist
}
}
}
#[derive(Serialize, Deserialize, Debug, Clone, PartialEq, Eq, Hash)]
pub struct LabeledArgument {
pub role_name: String,
pub argument: Argument,
}
impl LabeledArgument {
pub fn new(role_name: String, argument: Argument) -> Self {
LabeledArgument {
role_name,
argument,
}
}
pub fn hash_string(&self) -> String {
format!("{}={}", self.role_name, self.argument.hash_string())
}
pub fn convert_to_quantified(&self) -> LabeledArgument {
LabeledArgument::new(
self.role_name.clone(),
self.argument.convert_to_quantified(),
)
}
pub fn do_substitution(&self, value: Argument) -> LabeledArgument {
LabeledArgument::new(self.role_name.clone(), value)
}
}
pub const EXISTENCE_FUNCTION: &str = "exist";
#[derive(Serialize, Deserialize, Clone, PartialEq, Eq, Hash)]
pub struct Predicate {
pub function: String,
roles: Vec<LabeledArgument>,
}
impl fmt::Debug for Predicate {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.debug_string())
}
}
impl Predicate {
pub fn new(function: String, roles: Vec<LabeledArgument>) -> Self {
let mut buffer = roles.clone();
buffer.sort_by(|a, b| a.role_name.cmp(&b.role_name));
Predicate { function, roles: buffer }
}
pub fn debug_string(&self) -> String {
self.hash_string()
}
pub fn hash_string(&self) -> String {
let role_strings: Vec<String> = self
.roles
.iter()
.map(|role| role.hash_string())
.collect();
format!("{}[{}]", &self.function, role_strings.join(","))
}
pub fn role_names(&self) -> Vec<String> {
self.roles
.iter()
.map(|role| role.role_name.clone())
.collect()
}
pub fn is_fact(&self) -> bool {
self.roles.iter().all(|role| role.argument.is_constant())
}
pub fn roles(&self) -> Vec<LabeledArgument> {
self.roles.clone()
}
}
#[derive(Serialize, Deserialize, Clone, PartialEq, Eq, Hash)]
pub struct Proposition {
pub predicate: Predicate,
}
impl fmt::Debug for Proposition {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.debug_string())
}
}
fn hash_proposition(proposition: &Proposition) -> u64 {
let mut hasher = DefaultHasher::new();
proposition.hash(&mut hasher);
hasher.finish()
}
impl Proposition {
pub fn from(predicate: Predicate) -> Self {
if !predicate.is_fact() {
panic!(
"This predicate is not a fact {:?}.",
predicate.hash_string()
);
}
Proposition { predicate }
}
pub fn hash_string(&self) -> String {
self.predicate.hash_string()
}
pub fn debug_string(&self) -> String {
self.predicate.hash_string()
}
}
#[derive(Serialize, Deserialize, Clone, PartialEq, Eq, Hash)]
pub struct PredicateGroup {
pub terms: Vec<Predicate>,
}
impl fmt::Debug for PredicateGroup {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.debug_string())
}
}
impl PredicateGroup {
pub fn new(terms: Vec<Predicate>) -> Self {
PredicateGroup { terms }
}
pub fn hash_string(&self) -> String {
let mut hash_strings: Vec<String> = self
.terms
.iter()
.map(|term| term.hash_string()) // Map each term to its search string
.collect();
hash_strings.sort(); // Sort the search strings in ascending order
hash_strings.join(";") // Join the sorted strings, separated by a comma and a space
}
pub fn debug_string(&self) -> String {
self.hash_string()
}
}
#[derive(Serialize, Deserialize, Clone, PartialEq, Eq, Hash)]
pub struct PropositionGroup {
pub terms: Vec<Proposition>,
}
impl fmt::Debug for PropositionGroup {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.debug_string())
}
}
impl PropositionGroup {
pub fn new(terms: Vec<Proposition>) -> Self {
let mut buffer = terms.clone();
buffer.sort_by(|a, b| a.predicate.function.cmp(&b.predicate.function));
PropositionGroup { terms }
}
pub fn hash_string(&self) -> String {
let hash_strings: Vec<String> = self
.terms
.iter()
.map(|term| term.predicate.hash_string()) // Map each term to its search string
.collect();
let join = hash_strings.join("&"); // Join the sorted strings, separated by a comma and a space
format!("{{{}}}", &join)
}
pub fn debug_string(&self) -> String {
self.hash_string()
}
}
#[derive(Serialize, Deserialize, Debug, Clone)]
pub struct PredicateFactor {
pub premise: PredicateGroup,
pub role_maps: GroupRoleMap,
pub conclusion: Predicate,
}
impl PredicateFactor {
// Generate a unique key for the implication
pub fn unique_key(&self) -> String {
format!(
"{}->{}{}",
self.premise.hash_string(),
self.conclusion.hash_string(),
self.mapping_string()
)
}
// Generate a feature string based on the premise and the role map
pub fn feature_string(&self) -> String {
format!("{}{}", self.premise.hash_string(), self.mapping_string())
}
// Convert the role map to a string
fn mapping_string(&self) -> String {
self.role_maps.to_string() // Assuming RoleMap has a ToString implementation
}
}
#[derive(Debug, Clone)]
pub struct Entity {
pub domain: Domain,
pub name: String,
}
#[derive(Serialize, Deserialize, Debug, Clone)]
pub struct RoleMap {
pub role_map: Vec<(String, String)>,
}
impl RoleMap {
pub fn new(role_map: HashMap<String, String>) -> Self {
let mut sorted_vec: Vec<(String, String)> = role_map.into_iter().collect();
sorted_vec.sort_by(|a, b| a.0.cmp(&b.0));
RoleMap { role_map: sorted_vec }
}
pub fn get(&self, role_name: &str) -> Option<&String> {
for (from, to) in &self.role_map {
if role_name == from {
return Some(to);
}
}
None
}
}
impl fmt::Display for RoleMap {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let mut entries: Vec<_> = self.role_map.iter().collect();
// Sort the entries by key
entries.sort_by(|(a_key, _), (b_key, _)| a_key.cmp(b_key));
let entries_str: Vec<String> = entries
.into_iter()
.map(|(key, value)| format!("{}: {}", key, value))
.collect();
write!(f, "{{{}}}", entries_str.join(", "))
}
}
#[derive(Serialize, Deserialize, Debug, Clone)]
pub struct GroupRoleMap {
pub role_maps: Vec<RoleMap>,
}
impl GroupRoleMap {
pub fn new(role_maps: Vec<RoleMap>) -> Self {
GroupRoleMap { role_maps }
}
}
impl fmt::Display for GroupRoleMap {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let role_maps_str = self
.role_maps
.iter()
.map(|role_map| role_map.to_string()) // Convert each RoleMap to a String using its Display implementation
.collect::<Vec<String>>()
.join(", "); // Concatenate all the string representations with a comma separator
write!(f, "[{}]", role_maps_str)
}
}#56,252,777text/// inference/inference.rs, BAYES STAR, (c) coppola.ai 2024
use super::{
graph::{PropositionFactor, PropositionGraph},
table::{HashMapBeliefTable, InferenceResult, PropositionNode},
};
use crate::{
common::{
interface::PropositionDB,
model::{FactorContext, InferenceModel},
proposition_db,
},
inference::table::{GenericNodeType, HashMapInferenceResult},
model::{
objects::{Predicate, PredicateGroup, Proposition, PropositionGroup, EXISTENCE_FUNCTION},
weights::CLASS_LABELS,
},
print_blue, print_green, print_red, print_yellow,
};
use redis::Connection;
use std::{
borrow::Borrow,
collections::{HashMap, HashSet, VecDeque},
error::Error,
rc::Rc,
};
struct Inferencer {
model: Rc<InferenceModel>,
proposition_graph: Rc<PropositionGraph>,
pub data: HashMapBeliefTable,
bfs_order: Vec<PropositionNode>,
}
fn reverse_prune_duplicates(raw_order: &Vec<(i32, PropositionNode)>) -> Vec<PropositionNode> {
let mut seen = HashSet::new();
let mut result = vec![];
for (depth, node) in raw_order.iter().rev() {
if !seen.contains(node) {
result.push(node.clone());
}
seen.insert(node);
}
result.reverse();
result
}
fn create_bfs_order(proposition_graph: &PropositionGraph) -> Vec<PropositionNode> {
let mut queue = VecDeque::new();
let mut buffer = vec![];
for root in &proposition_graph.roots {
queue.push_back((0, PropositionNode::from_single(&root)));
}
print_yellow!("create_bfs_order initial: queue {:?}", &queue);
while let Some((depth, node)) = queue.pop_front() {
buffer.push((depth, node.clone()));
let forward = proposition_graph.get_all_forward(&node);
for child in &forward {
queue.push_back((depth + 1, child.clone()));
}
print_yellow!("create_bfs_order initial: queue {:?}", &queue);
print_yellow!("create_bfs_order initial: buffer {:?}", &buffer);
}
let result = reverse_prune_duplicates(&buffer);
print_yellow!("create_bfs_order result: {:?}", &result);
result
}
impl Inferencer {
// Initialize new Storage with a Redis connection
pub fn new_mutable(
model: Rc<InferenceModel>,
proposition_graph: Rc<PropositionGraph>,
) -> Result<Box<Self>, redis::RedisError> {
let bfs_order = create_bfs_order(&proposition_graph);
Ok(Box::new(Inferencer {
model,
proposition_graph,
data: HashMapBeliefTable::new(),
bfs_order,
}))
}
pub fn initialize(&mut self, proposition: &Proposition) -> Result<(), Box<dyn Error>> {
print_red!("initialize: proposition {:?}", proposition.hash_string());
// self.initialize_pi()?;
self.initialize_lambda()?;
self.send_pi_messages()?;
self.update_marginals()?;
Ok(())
}
pub fn update_marginals(&mut self) -> Result<(), Box<dyn Error>> {
print_red!("update_marginals over {:?}", &self.bfs_order);
for node in &self.bfs_order {
let pi0 = self.data.get_pi_value(node, 0).unwrap();
let pi1 = self.data.get_pi_value(node, 1).unwrap();
let lambda0 = self.data.get_lambda_value(node, 0).unwrap();
let lambda1 = self.data.get_lambda_value(node, 1).unwrap();
let potential0 = pi0 * lambda0;
let potential1 = pi1 * lambda1;
let norm = potential0 + potential1;
let probability0 = potential0 / norm;
let probability1 = potential1 / norm;
print_red!("node {:?} p0 {} p1 {}", node, probability0, probability1);
}
Ok(())
}
pub fn initialize_lambda(&mut self) -> Result<(), Box<dyn Error>> {
print_red!("initialize_lambda: proposition");
for node in &self.proposition_graph.all_nodes {
print_red!("initializing: {}", node.debug_string());
for outcome in CLASS_LABELS {
self.data.set_lambda_value(node, outcome, 1f64);
}
for parent in &self.proposition_graph.get_all_backward(node) {
print_red!(
"initializing lambda link from {} to {}",
node.debug_string(),
parent.debug_string()
);
for outcome in CLASS_LABELS {
self.data.set_lambda_message(node, parent, outcome, 1f64);
}
}
}
Ok(())
}
pub fn send_pi_messages(&mut self) -> Result<(), Box<dyn Error>> {
let bfs_order = self.bfs_order.clone();
print_red!("send_pi_messages bfs_order: {:?}", &bfs_order);
for node in &bfs_order {
print_yellow!("send pi bfs selects {:?}", node);
self.pi_visit_node(node)?;
}
Ok(())
}
fn pi_compute_root(&mut self, node: &PropositionNode) -> Result<(), Box<dyn Error>> {
let root = node.extract_single();
assert_eq!(root.predicate.function, EXISTENCE_FUNCTION.to_string());
self.data
.set_pi_value(&PropositionNode::from_single(&root), 1, 1.0f64);
self.data
.set_pi_value(&PropositionNode::from_single(&root), 0, 0.0f64);
Ok(())
}
pub fn pi_set_from_evidence(&mut self, node: &PropositionNode) -> Result<(), Box<dyn Error>> {
let as_single = node.extract_single();
let probability = self
.model
.proposition_db
.get_proposition_probability(&as_single)?
.unwrap();
self.data
.set_pi_value(node, 1, probability);
self.data
.set_pi_value(node, 0, 1f64 - probability);
Ok(())
}
pub fn pi_visit_node(&mut self, from_node: &PropositionNode) -> Result<(), Box<dyn Error>> {
// Part 1: Compute pi for this node.
if !self.is_root(from_node) {
let is_observed = self.is_observed(from_node)?;
if is_observed {
self.pi_set_from_evidence(from_node)?;
} else {
self.pi_compute_generic(&from_node)?;
}
} else {
self.pi_compute_root(from_node)?;
}
// Part 2: For each value of z, compute pi_X(z)
let forward_groups = self.proposition_graph.get_all_forward(from_node);
for (this_index, to_node) in forward_groups.iter().enumerate() {
for class_label in &CLASS_LABELS {
let mut lambda_part = 1f64;
for (other_index, other_node) in forward_groups.iter().enumerate() {
if other_index != this_index {
let this_lambda = self
.data
.get_lambda_value(&other_node, *class_label)
.unwrap();
lambda_part *= this_lambda;
}
}
let pi_part = self.data.get_pi_value(&from_node, *class_label).unwrap();
let message = pi_part * lambda_part;
self.data
.set_pi_message(&from_node, &to_node, *class_label, message);
}
}
// Success.
Ok(())
}
fn is_root(&self, node: &PropositionNode) -> bool {
if node.is_single() {
let as_single = node.extract_single();
let is_root = self.proposition_graph.roots.contains(&as_single);
is_root
} else {
false
}
}
fn is_observed(&self, node: &PropositionNode) -> Result<bool, Box<dyn Error>> {
if node.is_single() {
let as_single = node.extract_single();
let has_evidence = self
.model
.proposition_db
.get_proposition_probability(&as_single)?
.is_some();
print_green!(
"is_observed? node {:?}, has_evidence {}",
&as_single,
has_evidence
);
Ok(has_evidence)
} else {
Ok(false)
}
}
pub fn pi_compute_generic(&mut self, node: &PropositionNode) -> Result<(), Box<dyn Error>> {
match &node.node {
GenericNodeType::Single(proposition) => {
self.pi_compute_single(node)?;
}
GenericNodeType::Group(group) => {
self.pi_compute_group(node)?;
}
}
Ok(())
}
// from_node is a single.. compute it from the group
pub fn pi_compute_single(&mut self, node: &PropositionNode) -> Result<(), Box<dyn Error>> {
let conclusion = node.extract_single();
let parent_nodes = self.proposition_graph.get_all_backward(node);
let premise_groups = groups_from_backlinks(&parent_nodes);
let all_combinations = compute_each_combination(&parent_nodes);
let mut sum_true = 0f64;
let mut sum_false = 0f64;
for combination in &all_combinations {
let mut product = 1f64;
for (index, parent_node) in parent_nodes.iter().enumerate() {
let boolean_outcome = combination.get(parent_node).unwrap();
let usize_outcome = if *boolean_outcome { 1 } else { 0 };
let pi_x_z = self
.data
.get_pi_message(parent_node, node, usize_outcome)
.unwrap();
print_red!(
"getting pi message parent_node {:?}, node {:?}, usize_outcome {}, pi_x_z {}",
&parent_node,
&node,
usize_outcome,
pi_x_z,
);
product *= pi_x_z;
}
let factor =
self.build_factor_context_for_assignment(&premise_groups, combination, &conclusion);
let prediction = self.model.model.predict(&factor)?;
print_yellow!("local probability {} for factor {:?}", &prediction.marginal, &factor);
let true_marginal = &prediction.marginal;
let false_marginal = 1f64 - true_marginal;
sum_true += true_marginal * product;
sum_false += false_marginal * product;
}
self.data.set_pi_value(node, 1, sum_true);
self.data.set_pi_value(node, 0, sum_false);
Ok(())
}
pub fn pi_compute_group(&mut self, node: &PropositionNode) -> Result<(), Box<dyn Error>> {
let parent_nodes = self.proposition_graph.get_all_backward(node);
print_yellow!("pi_compute_group {:?}", &parent_nodes);
let all_combinations = compute_each_combination(&parent_nodes);
let mut sum_true = 0f64;
let mut sum_false = 0f64;
for combination in &all_combinations {
let mut product = 1f64;
let mut condition = true;
for (index, parent_node) in parent_nodes.iter().enumerate() {
let boolean_outcome = combination.get(parent_node).unwrap();
let usize_outcome = if *boolean_outcome { 1 } else { 0 };
print_green!(
"get pi message: parent_node {:?}, node {:?}, outcome: {}",
parent_node,
node,
usize_outcome
);
let pi_x_z = self
.data
.get_pi_message(parent_node, node, usize_outcome)
.unwrap();
print_yellow!(
"boolean_outcome {} usize_outcome {} pi_x_z {}",
boolean_outcome,
usize_outcome,
pi_x_z
);
product *= pi_x_z;
let combination_val = combination[parent_node];
condition = condition && combination_val;
print_yellow!(
"combination_val {} condition {}",
combination_val,
condition
);
}
if condition {
print_blue!("true combination: {:?}, product {}", &combination, product);
sum_true += product;
} else {
print_blue!("false combination: {:?}, product {}", &combination, product);
sum_false += product;
}
}
self.data.set_pi_value(node, 1, sum_true);
self.data.set_pi_value(node, 0, sum_false);
Ok(())
}
// TODO: move this out of the class
fn build_factor_context_for_assignment(
&self,
premises: &Vec<PropositionGroup>,
premise_assignment: &HashMap<PropositionNode, bool>,
conclusion: &Proposition,
) -> FactorContext {
let mut probabilities = vec![];
let mut factors = vec![];
for proposition_group in premises {
let node = PropositionNode::from_group(proposition_group);
let assignment = *premise_assignment.get(&node).unwrap();
if assignment {
probabilities.push(1f64);
} else {
probabilities.push(0f64);
}
let inference = self
.proposition_graph
.get_inference_used(proposition_group, conclusion);
let factor = PropositionFactor {
premise: proposition_group.clone(),
conclusion: conclusion.clone(),
inference,
};
factors.push(factor);
}
let context = FactorContext {
factor: factors,
probabilities,
};
context
}
}
// Return 1 HashMap for each of the 2^N ways to assign each of the N memebers of `propositions` to either true or false.
fn compute_each_combination(
propositions: &Vec<PropositionNode>,
) -> Vec<HashMap<PropositionNode, bool>> {
print_yellow!("compute_each_combination: propositions={:?}", &propositions);
let n = propositions.len();
let mut all_combinations = Vec::new();
for i in 0..(1 << n) {
let mut current_combination = HashMap::new();
for j in 0..n {
let prop = &propositions[j];
let state = i & (1 << j) != 0;
current_combination.insert(prop.clone(), state);
}
all_combinations.push(current_combination);
}
all_combinations
}
// Note: GraphicalModel contains PropositionDB, which contains the "evidence".
pub fn inference_compute_marginals(
model: Rc<InferenceModel>,
target: &Proposition,
) -> Result<Rc<dyn InferenceResult>, Box<dyn Error>> {
let proposition_graph = PropositionGraph::new_shared(model.graph.clone(), target)?;
// proposition_graph.visualize();
let mut inferencer = Inferencer::new_mutable(model.clone(), proposition_graph.clone())?;
inferencer.initialize(target)?;
inferencer.data.print_debug();
HashMapInferenceResult::new_shared(inferencer.data)
}
fn groups_from_backlinks(backlinks: &Vec<PropositionNode>) -> Vec<PropositionGroup> {
let mut result = vec![];
for backlink in backlinks {
let group = backlink.extract_group();
result.push(group);
}
result
}#56,252,769text/// model/exponential.rs, BAYES STAR, (c) coppola.ai 2024
use super::choose::extract_backimplications_from_proposition;
use super::config::ConfigurationOptions;
use super::objects::PredicateFactor;
use super::weights::{negative_feature, positive_feature, ExponentialWeights};
use crate::common::interface::{PropositionDB, PredictStatistics, TrainStatistics};
use crate::common::model::InferenceModel;
use crate::common::model::{FactorContext, FactorModel};
use crate::common::redis::RedisManager;
use crate::common::resources::FactoryResources;
use crate::model::objects::Predicate;
use crate::model::weights::CLASS_LABELS;
use crate::{print_yellow, print_blue};
use redis::Connection;
use std::cell::RefCell;
use std::collections::HashMap;
use std::error::Error;
use std::rc::Rc;
pub struct ExponentialModel {
config: ConfigurationOptions,
weights: ExponentialWeights,
}
impl ExponentialModel {
pub fn new_mutable(resources: &FactoryResources) -> Result<Box<dyn FactorModel>, Box<dyn Error>> {
let connection = resources.redis.get_connection()?;
let weights = ExponentialWeights::new(connection);
Ok(Box::new(ExponentialModel {
config: resources.config.clone(),
weights,
}))
}
pub fn new_shared(resources: &FactoryResources) -> Result<Rc<dyn FactorModel>, Box<dyn Error>> {
let connection = resources.redis.get_connection()?;
let weights = ExponentialWeights::new(connection);
Ok(Rc::new(ExponentialModel {
config: resources.config.clone(),
weights,
}))
}
}
fn dot_product(dict1: &HashMap<String, f64>, dict2: &HashMap<String, f64>) -> f64 {
let mut result = 0.0;
for (key, &v1) in dict1 {
if let Some(&v2) = dict2.get(key) {
let product = v1 * v2;
print_blue!("dot_product: key {}, v1 {}, v2 {}, product {}", key, v1, v2, product);
result += product;
}
// In case of null (None), we skip the key as per the original JavaScript logic.
}
result
}
pub fn compute_potential(weights: &HashMap<String, f64>, features: &HashMap<String, f64>) -> f64 {
let dot = dot_product(weights, features);
dot.exp()
}
pub fn features_from_factor(
factor: &FactorContext,
) -> Result<Vec<HashMap<String, f64>>, Box<dyn Error>> {
let mut vec_result = vec![];
for class_label in CLASS_LABELS {
let mut result = HashMap::new();
for (i, premise) in factor.factor.iter().enumerate() {
debug!("Processing backimplication {}", i);
let feature = premise.inference.unique_key();
debug!("Generated unique key for feature: {}", feature);
let probability = factor.probabilities[i];
debug!(
"Conjunction probability for backimplication {}: {}",
i, probability
);
let posf = positive_feature(&feature, class_label);
let negf = negative_feature(&feature, class_label);
result.insert(posf.clone(), probability);
result.insert(negf.clone(), 1.0 - probability);
debug!(
"Inserted features for backimplication {}: positive - {}, negative - {}",
i, posf, negf
);
}
vec_result.push(result);
}
trace!("features_from_backimplications completed successfully");
Ok(vec_result)
}
pub fn compute_expected_features(
probability: f64,
features: &HashMap<String, f64>,
) -> HashMap<String, f64> {
let mut result = HashMap::new();
for (key, &value) in features {
result.insert(key.clone(), value * probability);
}
result
}
const LEARNING_RATE: f64 = 0.025;
pub fn do_sgd_update(
weights: &HashMap<String, f64>,
gold_features: &HashMap<String, f64>,
expected_features: &HashMap<String, f64>,
print_training_loss: bool,
) -> HashMap<String, f64> {
let mut new_weights = HashMap::new();
for (feature, &wv) in weights {
let gv = gold_features.get(feature).unwrap_or(&0.0);
let ev = expected_features.get(feature).unwrap_or(&0.0);
let new_weight = wv + LEARNING_RATE * (gv - ev);
let loss = (gv - ev).abs();
if print_training_loss {
info!(
"feature: {}, gv: {}, ev: {}, loss: {}, old_weight: {}, new_weight: {}",
feature, gv, ev, loss, wv, new_weight
);
}
new_weights.insert(feature.clone(), new_weight);
}
new_weights
}
impl FactorModel for ExponentialModel {
fn initialize_connection(
&mut self,
implication: &PredicateFactor,
) -> Result<(), Box<dyn Error>> {
self.weights.initialize_weights(implication)?;
Ok(())
}
fn train(
&mut self,
factor: &FactorContext,
gold_probability: f64,
) -> Result<TrainStatistics, Box<dyn Error>> {
trace!("train_on_example - Getting features from backimplications");
let features = match features_from_factor(factor) {
Ok(f) => f,
Err(e) => {
trace!(
"train_on_example - Error in features_from_backimplications: {:?}",
e
);
return Err(e);
}
};
let mut weight_vectors = vec![];
let mut potentials = vec![];
for class_label in CLASS_LABELS {
for (feature, weight) in &features[class_label] {
trace!("feature {:?} {}", feature, weight);
}
trace!(
"train_on_example - Reading weights for class {}",
class_label
);
let weight_vector = match self
.weights
.read_weights(&features[class_label].keys().cloned().collect::<Vec<_>>())
{
Ok(w) => w,
Err(e) => {
trace!("train_on_example - Error in read_weights: {:?}", e);
return Err(e);
}
};
trace!("train_on_example - Computing probability");
let potential = compute_potential(&weight_vector, &features[class_label]);
trace!("train_on_example - Computed probability: {}", potential);
potentials.push(potential);
weight_vectors.push(weight_vector);
}
let normalization = potentials[0] + potentials[1];
for class_label in CLASS_LABELS {
let probability = potentials[class_label] / normalization;
trace!("train_on_example - Computing expected features");
let this_true_prob = if class_label == 0 {
1f64 - gold_probability
} else {
gold_probability
};
let gold = compute_expected_features(this_true_prob, &features[class_label]);
let expected = compute_expected_features(probability, &features[class_label]);
trace!("train_on_example - Performing SGD update");
let new_weight = do_sgd_update(
&weight_vectors[class_label],
&gold,
&expected,
self.config.print_training_loss,
);
trace!("train_on_example - Saving new weights");
self.weights.save_weights(&new_weight)?;
}
trace!("train_on_example - End");
Ok(TrainStatistics { loss: 1f64 })
}
fn predict(&self, factor: &FactorContext) -> Result<PredictStatistics, Box<dyn Error>> {
let features = match features_from_factor(factor) {
Ok(f) => f,
Err(e) => {
print_yellow!(
"inference_probability - Error in features_from_backimplications: {:?}",
e
);
return Err(e);
}
};
let mut potentials = vec![];
for class_label in CLASS_LABELS {
let this_features = &features[class_label];
for (feature, weight) in this_features.iter() {
print_yellow!("feature {:?} {}", &feature, weight);
}
print_yellow!("inference_probability - Reading weights");
let weight_vector = match self
.weights
.read_weights(&this_features.keys().cloned().collect::<Vec<_>>())
{
Ok(w) => w,
Err(e) => {
print_yellow!("inference_probability - Error in read_weights: {:?}", e);
return Err(e);
}
};
for (feature, weight) in weight_vector.iter() {
print_yellow!("weight {:?} {}", &feature, weight);
}
let potential = compute_potential(&weight_vector, &this_features);
print_yellow!("potential for {} {} {:?}", class_label, potential, &factor);
potentials.push(potential);
}
let normalization = potentials[0] + potentials[1];
let marginal = potentials[1] / normalization;
print_yellow!("dot_product: normalization {}, marginal {}", normalization, marginal);
Ok(PredictStatistics { marginal })
}
}#56,252,357text/// inference/graph.rs, BAYES STAR, (c) coppola.ai 2024
use std::{
collections::{HashMap, HashSet},
error::Error,
rc::Rc,
};
use env_logger::init;
use serde::{Deserialize, Serialize};
use crate::{
common::{graph::InferenceGraph, redis::RedisManager},
model::{
choose::{compute_search_predicates, extract_backimplications_from_proposition},
objects::{GroupRoleMap, PredicateFactor, Proposition, PropositionGroup},
}, print_green,
};
use super::table::{GenericNodeType, PropositionNode};
#[derive(Serialize, Deserialize, Debug, Clone)]
pub struct PropositionFactor {
pub premise: PropositionGroup,
pub conclusion: Proposition,
pub inference: PredicateFactor,
}
impl PropositionFactor {
pub fn debug_string(&self) -> String {
format!(
"{} -> {}",
self.premise.hash_string(),
self.conclusion.hash_string()
)
}
}
pub struct PropositionGraph {
pub predicate_graph: Rc<InferenceGraph>,
pub single_forward: HashMap<Proposition, HashSet<PropositionGroup>>,
pub single_backward: HashMap<Proposition, HashSet<PropositionGroup>>,
pub group_forward: HashMap<PropositionGroup, HashSet<Proposition>>,
pub inference_used: HashMap<(PropositionGroup, Proposition), PredicateFactor>,
pub roots: HashSet<Proposition>,
pub all_nodes: HashSet<PropositionNode>,
}
fn initialize_visit_single(
graph: &mut PropositionGraph,
single: &Proposition,
) -> Result<(), Box<dyn Error>> {
// Green for starting a new operation
info!(
"\x1b[32mInitializing visit for proposition: {:?}\x1b[0m",
single.hash_string()
);
graph
.all_nodes
.insert(PropositionNode::from_single(single));
let inference_factors =
extract_backimplications_from_proposition(&graph.predicate_graph, single)?;
// Yellow for showing counts or lengths
info!(
"\x1b[33mInference factors count: {}\x1b[0m",
inference_factors.len()
);
if inference_factors.is_empty() {
// Blue for specific condition-related messages
info!("\x1b[34mNo inference factors. Adding to roots.\x1b[0m");
graph.roots.insert(single.clone());
} else {
for inference_factor in &inference_factors {
// Cyan for loop iteration
info!(
"\x1b[36mProcessing inference factor: {:?}\x1b[0m",
inference_factor.debug_string()
);
let inference_used_key = (inference_factor.premise.clone(), inference_factor.conclusion.clone());
graph.inference_used.insert(inference_used_key, inference_factor.inference.clone());
info!(
"\x1b[36mUpdating single_backward for conclusion: {:?}\x1b[0m",
inference_factor.conclusion.hash_string()
);
graph
.single_backward
.entry(inference_factor.conclusion.clone())
.or_insert_with(HashSet::new)
.insert(inference_factor.premise.clone());
info!(
"\x1b[36mUpdating group_forward for premise: {:?}\x1b[0m",
inference_factor.premise.hash_string()
);
graph
.group_forward
.entry(inference_factor.premise.clone())
.or_insert_with(HashSet::new)
.insert(inference_factor.conclusion.clone());
graph
.all_nodes
.insert(PropositionNode::from_group(&inference_factor.premise));
for term in &inference_factor.premise.terms {
info!("\x1b[35mProcessing term: {:?}\x1b[0m", term.hash_string());
graph
.single_forward
.entry(term.clone())
.or_insert_with(HashSet::new)
.insert(inference_factor.premise.clone());
info!(
"\x1b[35mRecursively initializing visit for term: {:?}\x1b[0m",
term.hash_string()
);
initialize_visit_single(graph, term)?;
}
}
}
// Green for completion messages
info!(
"\x1b[32mFinished initializing visit for proposition: {:?}\x1b[0m",
single.hash_string()
);
Ok(())
}
impl PropositionGraph {
pub fn new_shared(
predicate_graph: Rc<InferenceGraph>,
target: &Proposition,
) -> Result<Rc<PropositionGraph>, Box<dyn Error>> {
let mut graph = PropositionGraph {
predicate_graph,
single_forward: HashMap::new(),
single_backward: HashMap::new(),
group_forward: HashMap::new(),
inference_used: HashMap::new(),
roots: HashSet::new(),
all_nodes: HashSet::new(),
};
initialize_visit_single(&mut graph, target)?;
Ok(Rc::new(graph))
}
pub fn get_inference_used(&self, premise:&PropositionGroup, conclusion: &Proposition) -> PredicateFactor {
let key = (premise.clone(), conclusion.clone());
self.inference_used
.get(&key).unwrap().clone()
}
pub fn get_single_forward(&self, key: &Proposition) -> HashSet<PropositionGroup> {
self.single_forward
.get(key)
.cloned()
.unwrap_or_else(HashSet::new)
}
pub fn get_single_backward(&self, key: &Proposition) -> HashSet<PropositionGroup> {
self.single_backward
.get(key)
.cloned()
.unwrap_or_else(HashSet::new)
}
pub fn get_group_forward(&self, key: &PropositionGroup) -> HashSet<Proposition> {
self.group_forward.get(key).unwrap().clone()
}
pub fn get_group_backward(&self, key: &PropositionGroup) -> Vec<Proposition> {
key.terms.clone()
}
pub fn get_all_backward(&self, node: &PropositionNode) -> Vec<PropositionNode> {
print_green!("get_all_backward called for node: {:?}", node.debug_string());
let mut r = vec![];
match &node.node {
GenericNodeType::Single(proposition) => {
print_green!("Processing as Single: {:?}", proposition.debug_string());
let initial = self.get_single_backward(proposition);
print_green!("Initial singles: {}", initial.len());
for group in &initial {
print_green!("Adding group from initial singles: {:?}", group.debug_string());
r.push(PropositionNode::from_group(group));
}
}
GenericNodeType::Group(group) => {
print_green!("Processing as Group: {:?}", group.debug_string());
let initial = self.get_group_backward(group);
print_green!("Initial groups: {}", initial.len());
for single in &initial {
print_green!("Adding single from initial groups: {:?}", single.debug_string());
r.push(PropositionNode::from_single(single));
}
}
}
info!("Resulting vector: {:?}", r);
r
}
pub fn get_all_forward(&self, node: &PropositionNode) -> Vec<PropositionNode> {
print_green!("get_all_backward called for node: {:?}", node.debug_string());
let mut r = vec![];
match &node.node {
GenericNodeType::Single(proposition) => {
print_green!("Processing as Single: {:?}", proposition.debug_string());
let initial = self.get_single_forward(proposition);
print_green!("Initial singles: {}", initial.len());
for group in &initial {
print_green!("Adding group from initial singles: {:?}", group.debug_string());
r.push(PropositionNode::from_group(group));
}
}
GenericNodeType::Group(group) => {
print_green!("Processing as Group: {:?}", group.debug_string());
let initial = self.get_group_forward(group);
print_green!("Initial groups: {}", initial.len());
for single in &initial {
print_green!("Adding single from initial groups: {:?}", single.debug_string());
r.push(PropositionNode::from_single(single));
}
}
}
info!("Resulting vector: {:?}", r);
r
}
pub fn get_roots(&self) -> HashSet<Proposition> {
self.roots.clone()
}
}#56,252,325texthallucination and causality are two sides of the same coin
in order to prove you are NOT hallucinating, you have to explain WHY you think something
explaining WHY implies understanding CAUSALITY
greg coppola#51,272,172textfrom roughly fastest to slowest, the kinds of thinking are:
* forward computation in a fixed network (fast thinking)
* backward computation in a fixed network (Bayes Rule)
* updating a fixed network based on an example (stochastic training)
* reasoning in the presence of and OR conclusion (proof by cases)
* changing the structure of the graph (creativity)
greg coppola#51,262,403text# BAYES STAR
## Why Should I Care About This?
This **BAYES STAR** software package implements a "QBN" which will allow **AGI**.
So, if you are interested in **AGI** you should be interested in this.
## The Quantified Bayesian Network
This software package introduces the **Quantified Bayesian Network** (**QBN**).
The QBN generalizes 1) traditional generative Bayesian Networks, and 2) First-Order Logic.
The end result, I claim, is that:
* the QBN allows a *generative* model of logical (i.e., linguistic) knowledge **that does not hallucinate**
## How Does the QBN Avoid Hallucinations?
The QBN avoids hallucinations by:
1. using logic
2. understanding how to explain its argument
3. understands that there are things it does not know
How does it do this?
1. using logic -- the QBN generalizes (though in a complex way) first-order logic
2. using ideas from classical Bayesian Networks -- allows us to create a generative story based on "causality"
## Did you Literally Build AGI?
The QBN as I am presented it is trained on **artificial data**.
It will be AGI when the QBN is trained on **real web-scale data**.
Right now, the QBN only "thinks about" very simple worlds that I encoded by hand.
But, if we assume that the LLM has "world knowledge", then the only problem to get full AGI is to transfer the knowledge from the LLM to the QBN.
That, I claim would be full AGI. Right now, I repeat, the QBN is trained on "toy universes" that I made up programmatically.
## Is it Trivial to Transfer Knowledge from LLM to QBN?
No. This is not trivial. It will require that the LLM model be re-written to generate a **tree-structured** analysis of a sentence, mapping the **surface form** of the sentence to its **logical form**.
This **logical form** is **latent**--meaning we can't observe it, and neither can actual people (this is why misunderstandings arise).
So, the following new abilities need to be developed before "full AGI" exists:
1. parse to logical forms, which are:
a. latent (not observed)
b. structured (recursively tree-structured)
2. concretize the continuous knowledge of the LLM into the discrete knowledge of the QBN
## Does the QBN Help us Understand the LLM?
Yes, I believe so. The QBN uses "semantic roles", which might explain why the "key-value" nature of the attention mechanism can learn world knowledge:
that is, the **key-value** knowledge of the LLM is actually learning the **semantic role** knowledge of linguistics.
## Documentation
I have the notes for a paper, but have to clean them up. So, the paper is coming.
I will be adding the informal documentation (markdown, tweets and videos) starting now. This is a "developing in public" process.
Find me online at:
* twitter: [@coppola_ai](https://twitter.com/coppola_ai)
## License
This project is licensed under the ISC License - see the [LICENSE.txt](LICENSE.txt) file for details.#50,445,039text// train.js BAYES STAR (c) coppola.ai
const mongoose = require("mongoose")
const { CreateStorage, ConnectDB } = require("./storage")
const { ComputeBacklinks } = require("./choose")
const { InitializeWeights, TrainOnExample, DumpWeights } = require("./maxent")
async function main() {
await ConnectDB()
const storage = await CreateStorage("testdb1")
const implications = await storage.GetAllImplications()
for (const implication of implications) {
await InitializeWeights(implication)
}
const propositions = await storage.GetAllPropositions()
for (const proposition of propositions) {
const backlinks = await ComputeBacklinks(storage, proposition)
await TrainOnExample(proposition, backlinks)
}
await DumpWeights()
await mongoose.disconnect();
}
main()#47,342,226text// predicate.js BAYES STAR (c) coppola.ai
class FirstOrderArgument {
constructor(type, domain) {
this.type = type;
this.domain = domain;
}
IsVariable() {
return this.type == 'variable'
}
static FromTuple(tuple) {
switch (tuple.type) {
case "constant":
return ConstantArgument.FromTuple(tuple)
case "variable":
return VariableArgument.FromTuple(tuple)
default:
throw new Error("not found!")
}
}
}
class ConstantArgument extends FirstOrderArgument {
constructor(domain, entity_id) {
super("constant", domain);
this.entity_id = entity_id;
}
SearchString() {
const cstring = `${this.entity_id}`
return cstring
}
ConvertToQuantified() {
return new VariableArgument(this.domain)
}
static FromTuple(tuple) {
return new ConstantArgument(tuple.domain, tuple.entity_id)
}
}
const BOUND_VARIABLE = '?'
class VariableArgument extends FirstOrderArgument {
constructor(domain) {
super("variable", domain);
}
SearchString() {
return `${BOUND_VARIABLE}${this.domain}`
}
static FromTuple(tuple) {
return new VariableArgument(tuple.domain)
}
}
class FilledRole {
constructor(role_name, argument) {
this.role_name = role_name
this.argument = argument
}
SearchString() {
const roleString = `${this.role_name}=${this.argument.SearchString()}`
return roleString
}
ConvertToQuantified() {
return new FilledRole(this.role_name, this.argument.ConvertToQuantified())
}
DoSubstitution(value) {
return new FilledRole(this.role_name, value)
}
static FromTuple(tuple) {
const role_name = tuple.role_name
const argument = FirstOrderArgument.FromTuple(tuple.argument)
return new FilledRole(role_name, argument)
}
}
class Proposition {
constructor(roles) {
roles.sort((a, b) => {
if (a.role_name < b.role_name) {
return -1;
}
if (a.role_name > b.role_name) {
return 1;
}
return 0;
});
this.roles = roles
}
RoleNames() {
var result = []
for (const role of this.roles) {
result.push(role.role_name)
}
return result
}
SearchString() {
var result = '['
var started = false
for (const column of this.roles) {
if (started) {
result += ', '
}
result += column.SearchString()
started = true
}
result += ']'
return result
}
IsFact() {
this.roles.forEach((column) => {
if (column.argument.type == 'variable') {
return false
} else {
// console.log('not quantified', {column})
}
})
return true
}
ToString() {
return JSON.stringify(this.roles)
}
static FromString(record) {
const parsedObj = JSON.parse(record);
var roles = []
for (const rolePart of parsedObj) {
const newRole = FilledRole.FromTuple(rolePart)
roles.push(newRole)
}
return new Proposition(roles)
}
}
function ToStringObjectCanonical(obj) {
const sortedObj = {};
Object.keys(obj).sort().forEach(function(key) {
sortedObj[key] = obj[key];
});
return JSON.stringify(sortedObj);
}
class Implication {
constructor(premise, conclusion, roleMap) {
this.premise = premise
this.conclusion = conclusion
this.roleMap = roleMap
}
SearchString() {
return this.conclusion.SearchString()
}
UniqueKey() {
return `${this.premise.SearchString()}->${this.conclusion.SearchString()}${this.MappingString()}`
}
FeatureString() {
return `${this.premise.SearchString()}${this.MappingString()}`
}
MappingString() {
return this.roleMap.ToString()
}
static FromRecord(record) {
const {premiseRecord, conclusionRecord, mappingRecord} = record;
const premise = Proposition.FromString(premiseRecord)
const conclusion = Proposition.FromString(conclusionRecord)
const roleMap = RoleMap.FromRecord(mappingRecord)
return new Implication(premise, conclusion, roleMap)
}
}
class Entity {
constructor(domain, name) {
this.domain = domain
this.name = name
}
}
class RoleMap {
constructor(roleMap) {
this.roleMap = roleMap
}
Get(role_name) {
const rval = this.roleMap[role_name]
return rval
}
ToString() {
return ToStringObjectCanonical(this.roleMap)
}
static FromRecord(record) {
const roleMap = JSON.parse(record)
return new RoleMap(roleMap)
}
}
class BackLink {
constructor(implication, proposition) {
this.implication = implication
this.proposition = proposition
}
}
module.exports = { ConstantArgument, VariableArgument, Proposition, Implication, FilledRole, Entity, RoleMap, BackLink }#47,327,675text// models.js BAYES STAR (c) coppola.ai
const mongoose = require("mongoose")
const factSchema = new mongoose.Schema({
searchString: { type: String, required: true, unique: true },
record: { type: String, required: true },
probability: { type: Number, required: true },
});
const PropositionRecord = mongoose.model('Proposition', factSchema);
const implicationSchema = new mongoose.Schema({
UniqueKey: { type: String, required: true, unique: true },
searchString: { type: String, required: true },
featureString: { type: String, required: true },
premiseRecord: { type: String, required: true },
conclusionRecord: { type: String, required: true },
mappingRecord: { type: String, required: true },
});
const ImplicationRecord = mongoose.model('Implication', implicationSchema);
const entitySchema = new mongoose.Schema({
name: { type: String, required: true, unique: true },
domain: { type: String, required: true },
})
const EntityRecord = mongoose.model('Entity', entitySchema);
module.exports = {PropositionRecord, ImplicationRecord, EntityRecord}#47,309,211text// choose.js BAYES STAR (c) coppola.ai
const { Proposition, BackLink } = require("./predicate");
const { Storage } = require("./storage");
const { ConvertToQuantified, ExtractPremiseRoleMap, ConvertToProposition } = require("./ops");
function Combine(inputArray, k) {
var result = [];
function run(level, start, currentArray) {
if (currentArray.length === k) {
result.push(currentArray.slice());
return;
}
for (var i = start; i < inputArray.length; i++) {
currentArray.push(inputArray[i]);
run(level + 1, i + 1, currentArray);
currentArray.pop();
}
}
run(0, 0, []);
return result;
}
function ComputeChooseConfigurations(N, K) {
var inputArray = Array.from({ length: N }, (_, i) => i);
return Combine(inputArray, K);
}
function ExtractRolesFromIndices(roles, indices) {
var result = []
const indexSet = new Set(indices)
for (var i = 0; i < roles.length; i++) {
if (indexSet.has(i)) {
result.push(roles[i])
}
}
return result
}
function ComputeSearchKeys(proposition) {
const num_roles = proposition.roles.length
const configurations1 = ComputeChooseConfigurations(num_roles, 1)
const configurations2 = ComputeChooseConfigurations(num_roles, 2)
const configurations = [...configurations1, ...configurations2];
const roles = proposition.RoleNames()
var result = []
for (const configuration of configurations) {
const quantifiedRoles = ExtractRolesFromIndices(roles, configuration)
const quantified = ConvertToQuantified(proposition, quantifiedRoles)
const searchString = quantified.SearchString()
result.push(searchString)
}
return result
}
async function ComputeBacklinks(storage, proposition) {
const searchKeys = ComputeSearchKeys(proposition)
var buffer = []
for (const searchKey of searchKeys) {
const implications = await storage.FindPremises(searchKey)
for (const implication of implications) {
const extractedMapping = ExtractPremiseRoleMap(proposition, implication.roleMap)
const quantifiedPremise = implication.premise
const extractedProposition = ConvertToProposition(quantifiedPremise, extractedMapping)
buffer.push(new BackLink(implication, extractedProposition));
}
}
return buffer
}
async function ComputeMatchingPremises(storage, premise) {
return []
}
module.exports = { ComputeSearchKeys, ComputeBacklinks, ComputeMatchingPremises }#47,306,009text// maxent.js BAYES STAR (c) coppola.ai
const mongoose = require("mongoose")
const models = require("./models")
const weightSchema = new mongoose.Schema({
feature: { type: String, required: true },
weight: { type: Number, required: true },
})
const WeightRecord = mongoose.model('Weight', weightSchema);
function RandomWeight() {
return (Math.random() - Math.random()) / 5
}
function PositiveFeature(feature) {
return '+++' + feature + '+++'
}
function NegativeFeature(feature) {
return '---' + feature + '---'
}
async function InitializeWeights(implication) {
const weight = RandomWeight()
const feature = implication.UniqueKey()
const pwr = WeightRecord({ feature: PositiveFeature(feature), weight })
await pwr.save()
const nwr = WeightRecord({ feature: NegativeFeature(feature), weight })
await nwr.save()
}
async function GetPropositionProbability(searchString) {
const record = await models.PropositionRecord.find({ searchString })
const r = record[0].probability
return r
}
function Sigmoid(x) {
return 1 / (1 + Math.exp(-x));
}
function DotProduct(dict1, dict2) {
let result = 0;
for (const key of Object.keys(dict1)) {
const v1 = dict1[key]
const v2 = dict2[key]
if (v1 == null || v2 == null) {
} else {
result += v1 * v2
}
}
return result;
}
async function FeaturesFromBacklinks(backlinks) {
var result = {}
for (var i = 0; i < backlinks.length; i++) {
const backlink = backlinks[i]
const feature = backlink.implication.UniqueKey()
const searchString = backlink.proposition.SearchString()
const probability = await GetPropositionProbability(searchString)
result[PositiveFeature(feature)] = probability
result[NegativeFeature(feature)] = 1 - probability
}
return result
}
function ComputeProbability(weights, features) {
const dot = DotProduct(weights, features);
const probability = Sigmoid(dot);
return probability;
}
async function ReadWeights(features) {
var r = {}
for (const feature of Object.keys(features)) {
const record = await WeightRecord.findOne({ feature })
if (record) {
r[feature] = record.weight
}
}
return r
}
async function SaveWeights(weights) {
for (const feature of Object.keys(weights)) {
const updated = await WeightRecord.findOneAndUpdate({ feature }, { weight: weights[feature] }, { new: true, runValidators: true });
}
}
function ComputeExpectedFeatures(probability, features) {
let r = {};
for (let key in features) {
r[key] = features[key] * probability;
}
return r;
}
const LEARNING_RATE = 0.1
function DoSGDUpdate(weights, goldFeatures, expectedFeatures) {
var r = {}
for (const feature of Object.keys(weights)) {
const wv = weights[feature]
const gv = goldFeatures[feature]
const ev = expectedFeatures[feature]
const newWeight = wv + LEARNING_RATE * (gv - ev)
console.log({ feature, wv, gv, ev, newWeight }, DoSGDUpdate)
r[feature] = newWeight
}
return r
}
async function TrainOnExample(proposition, backlinks) {
const features = await FeaturesFromBacklinks(backlinks)
const weightVector = await ReadWeights(features)
const probability = ComputeProbability(weightVector, features);
const expected = ComputeExpectedFeatures(probability, features)
const newWeight = DoSGDUpdate(weightVector, features, expected)
await SaveWeights(newWeight)
}
async function DumpWeights() {
const records = await WeightRecord.find({})
console.log({ records }, DumpWeights)
}
module.exports = { InitializeWeights, TrainOnExample, DumpWeights }#47,305,690textA problem that users report in working with automated productivity applications is that they capture so many goals and tasks that the dashboard of tasks strains the user's attentional capacity, making it hard to identify the highest ROI activity.
The Greg Coppola Method#42,915,370textA person's wealth is a function of what the *produce*, not of how much *effort* they put in over time.
The way to optimize **value produced** over time is to always select the highest **Return-On-Investment** (*ROI*) task, to work on in any given context.
The Greg Coppola Method#42,681,712textThe central insight of the Greg Coppola Method is that human-readable **principles** constitute a central part of the optimal **interface layer** between the human user and the A.I. assistant.
The A.I. assistant can leverage its superior storage and analysis capabilities to aid the human user in *learning* the relationship between identified principles and past outcomes, given the *experiential* data that the user supplies.
At the same time, the user's ability to intervene and choose their own principles for action guarantees they retain control over their own karma.
The Greg Coppola Method#42,666,183textA decision-making **principle** is a rule that prescribes a certain action in a certain *general class* of contexts.
Principles can conflict in a concrete situation. For example, a man might have one principle that he never misses a scheduled gym day, and a second that emergencies must be handled immediately. If an emergency arises on gym day, he might decide to prioritize the handling of that emergency over not missing the gym. The contradiction can be resolved by making a principle that one should never miss gym day, except in case of an emergency.
The Greg Coppola Method#42,650,971text**Karma** comes from the **intentions** behind **actions**, and all actions are **decisions**. Thus, in order to control their own karma, a person must make their own decisions.
The Greg Coppola Method#42,642,482textImagine the creation of an A.I. tool that could tell a human user exactly what action to take for every decision, without any input from the human user. Would this be desirable?
The Greg Coppola Method#42,630,773textA.I. has a natural advantage over humans in terms of learning to make decisions. Recent advances have shown that computers programmed with A.I. can store, retrieve and analyze the entire Internet's worth of data.
Thus, A.I. is already surpassing humans in its:
1. ability to precisely store information
2. ability to precisely retrieve information
3. ability to analyze and extract patterns from information#42,628,060textThe four **crucial skills** of decision-making and execution are:
1. **Decision-Making**
2. **Discipline**
3. **Organization**
4. **Automation**
The Greg Coppola Method#41,132,506textThe four **iterating stages** of decision-making and execution are:
1. **Study**
2. **Plan**
3. **Do**
4. **Review**
The Greg Coppola Method#41,129,974text**Decisions** are made based on a weighting of a non-zero number of general but perhaps contradictory decision-making **principles**.
Principles are extracted during prior **learning**.
Learning is based on previously observed **outcome** events.
Outcomes are determined jointly by 1) the **world**, and 2) the agent's past **actions**. All actions are decisions.
Outcomes can be either *desirable* (which we call **success**), or *undesirable* (which we call **failure**).
Successes *reinforce* the principles behind the decisions that led to them. Failures *discourage* the principles behind the decisions that led to them, and invite the invention of new principles, created as **takeaways** from the experience.
The Greg Coppola Method#41,125,048textWealth is a kind of outcome. All outcomes depend on actions. And, all actions are decisions.
Thus, all wealth depends on decisions.
The Greg Coppola Method#41,116,199textThe seven dimensions (money, network, women, body, mind, soul, wisdom) form what we will call a *wealth network*.
In a **wealth network**, improvements in some dimension A can be leveraged to improve dimensions B, C, D, etc. Then, the improvements in B, C, D, etc., can be leveraged to create improvements in A, greater than what could have been achieved by optimizing A alone.
For example, improving your network improves your money by getting access to more information. But, improving your money gets you access to a better network, by having something to offer. Having more money leads to more success with women. But, having success with women leads to a better network, which leads to more money.
The Greg Coppola Method#40,985,699textThe wealth of a man can be measured by the following seven dimensions:
1. Money
2. Network
3. Women
4. Body
5. Mind
6. Soul
7. Wisdom
The Greg Coppola Method#40,865,437textThe Greg Coppola Method for Learning to Create Wealth#40,315,143text