\documentclass[12pt]{article}
\usepackage{pstricks}
\usepackage{pst-all}
\newcommand{\wgt}{\boldsymbol{\bar{w}}}
\usepackage{amsmath,amssymb}
\usepackage{verbatim}
\usepackage{color}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{tikz}
\usepackage{float}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}{Proposition}
\renewcommand{\qedsymbol}{$\blacksquare$}
\DeclareMathOperator{\E}{\mathbb{E}}
\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\newtheorem{statement}{Statement}[section]
\newenvironment{claim}[1]{\par\noindent\underline{Claim:}\space#1}{}
\newenvironment{claimproof}[1]{\par\noindent\underline{Proof:}\space#1}{\hfill $\blacksquare$}
\definecolor{orange}{RGB}{255,57,0}
\title{Three-level scheme for Gaussian Belief Propagation}
\usepackage{natbib}
\usepackage{graphicx}
\date{}
\begin{document}
\maketitle
\section{Introduction:}
Consider next three-level hierarchy:
\begin{enumerate}
\item Node
\item Edge
\item Star: neighborhood of node of degree $\geq$ 2 + node itself. Each star has a central node, neighborhood of which forms a star.
\end{enumerate}
Parent-child relations: Star can be parent of edge, edge can be parent of node.
Star can be an ancestor of node, but star can't be a parent of node (parent is a direct ancestor). \\
Each edge has one or two parent stars.\\
Therefore we have a region graph with edges only from stars to edges and from edges to nodes.\\
($\text{Star} \rightarrow \text{Edge} \rightarrow \text{Node}$, but $\text{Star} \not \rightarrow \text{Node}$)\\
We will denote vertices by small Latin letters $i, j, \text{etc.}$ and stars by small Greek letters $\alpha, \beta, \text{etc.}$\\
%Process of message sending from node $i$ to node $j$ can be considered as a sending of message from %edge $(i, j)$ to node $j$ so we will denote $m_{(ij) \rightarrow j} \equiv m_{i \rightarrow j}$.\\
Define $\mathcal{E}(R) = R \cup D(R)$, where $D(R)$ - is a set of all descendants (not only direct) of some region R.
In general case of region graph and parent-to-child model messages are calculated through equation:
\begin{equation}
\label{GBP}
m_{P \rightarrow R}(X_{R}) = \int_{x_{P \backslash R}} \frac{\prod_{a \in F_{P \backslash R}} f_{a}(x_{a}) \prod_{(I,J) \in N(P, R)} m_{I \rightarrow J}(x_J) }{\prod_{(I, J) \in D(P, R)}{m_{I \rightarrow J}(x_J)}}
\end{equation}
Where
\begin{enumerate}
\item $N(P,R)$ is a set of all connected pairs of regions $(I, J)$ such that $J \in \mathcal{E}(P) \backslash \mathcal{E}(R)$, while $I \notin \mathcal{E}(P)$
\item $D(P,R)$ is a set of all connected pairs of regions $(I, J)$ such that $I \in \mathcal{E}(P) \backslash \mathcal{E}(R)$, and $J \in \mathcal{E}(R)$
\item $F_{P \backslash R}$ - set of all factors related to $\mathcal{E}(P) \backslash \mathcal{E}(R)$
\end{enumerate}
\section{Gaussian ansatz for three-level hierarchy}
Let messages have next Gaussian form:
\begin{enumerate}
\item Message from edge $(i,j)$ to node $j$ (can be viewed as a message from node $i$ to node $j$):
\begin{equation}
m_{i \rightarrow j} \propto exp(\Delta J_{i \rightarrow j} x^2_j + \Delta h_{i \rightarrow j} x_j)
\end{equation}
\item Message from star $\alpha$ to edge $(i,j)$:
\begin{equation}
\begin{split}
m_{\alpha \rightarrow (i,j)} \propto exp(\Delta A_{\alpha \rightarrow (i,j)} x^2_i + \Delta B_{\alpha \rightarrow (i,j)} x_i x_j + \Delta C_{\alpha \rightarrow (i,j)} x^2_j +\\
\Delta D_{\alpha \rightarrow (i,j)} x_i + \Delta E_{\alpha \rightarrow (i,j)} x_j)
\end{split}
\end{equation}
\end{enumerate}
\subsection{From star to edge}
Let us investigate the structure of message from star to one of it's descendent edges.\\
Consider message $m_{\alpha \rightarrow (i,j)}$ from star $\alpha$ to edge $(i, j) \in \alpha$. Assume node $i$ is the central node for star $\alpha$.
According to ($\ref{GBP}$) next messages are built into message $m_{\alpha \rightarrow (i,j)}$:\\
1) In Numerator: Messages from outer (not in $\alpha$) nodes to node $k \in \alpha, k \neq i, k \neq j$.
\begin{figure}[H]
\begin{center}
\begin{tikzpicture}[scale = 0.15]
\draw [red, fill = orange, ultra thick] (-1.6, 25.1) circle [radius=1.5];
\draw [red, fill = orange, ultra thick] (-7.9, 21.8) circle [radius=1.5];
\draw [red, fill = orange, ultra thick] (-14.3, 16.4) circle [radius=1.5];
\draw [red, fill = orange, ultra thick] (-17.6, 9.1) circle [radius=1.5];
\draw [line width = 2, >->] (-1.6, 25.1) -- (-1.6, 9.1) ;
\draw [line width = 2, >->](-7.9, 21.8) -- (-1.6, 9.1) ;
\draw [line width = 2, >->] (-14.3, 16.4) --(-1.6, 9.1) ;
\draw [line width = 2, >->](-17.6, 9.1)-- (-1.6, 9.1) ;
\draw (7.5,0) -- (7.5,13);
\draw[line width = 4, yellow] (7.5,0) -- (16.6,9.1);
\draw (7.5,0) -- (20.5,0);
\draw (7.5,0) -- (16.6,-9.1);
\draw (7.5,0) -- (-5.5,0);
\draw (7.5,0) -- (-1.6,-9.1);
\draw (7.5,0) -- (7.5, -13.0);
\draw (7.5,0) -- (-1.6, 9.1);
\draw [black, thick] (7.5,0) circle [radius=16];
\draw [red, fill = yellow, ultra thick] (7.5,0) circle [radius=2.5];
\draw [red, fill = gray, ultra thick] (7.5,13) circle [radius=1.5];
\draw [red, fill = yellow, ultra thick] (16.6,9.1) circle [radius=2.5];
\draw [red, fill = gray, ultra thick] (20.5,0) circle [radius=1.5];
\draw [red, fill = gray, ultra thick] (16.6,-9.1) circle [radius=1.5];
\draw [red, fill = gray, ultra thick] (-1.6,-9.1) circle [radius=1.5];
\draw [red, fill = gray, ultra thick] (-5.5,0) circle [radius=1.5];
\draw [red, fill = pink, line width = 3] (-1.6, 9.1) circle [radius=2.5];
\draw [red, fill = gray, ultra thick] (7.5, -13.0) circle [radius=1.5];
\node at (-1.6, 9.1) {\Large{K}};
\node at (7.5,0) {\Large{I}};
\node at (16.6,9.1) {\Large{J}};
\end{tikzpicture}
\end{center}
\caption{Messages from outer neighbors into $K$}
\end{figure}
2) In Numerator: Messages from outer stars to edges $(k,i) \in \alpha, k \neq j$.
\begin{figure}[H]
\begin{center}
\begin{tikzpicture}[scale = 0.15]
\draw [red, fill = gray, ultra thick] (-1.6, 25.1) circle [radius=1.5];
\draw [red, fill = gray, ultra thick] (-7.9, 21.8) circle [radius=1.5];
\draw [red, fill = gray, ultra thick] (-14.3, 16.4) circle [radius=1.5];
\draw [red, fill = gray, ultra thick] (-17.6, 9.1) circle [radius=1.5];
\draw (-1.6, 25.1) -- (-1.6, 9.1) ;
\draw (-7.9, 21.8) -- (-1.6, 9.1) ;
\draw (-14.3, 16.4) --(-1.6, 9.1) ;
\draw (-17.6, 9.1)-- (-1.6, 9.1) ;
\draw (7.5,0) -- (7.5,13);
\draw[line width = 4, yellow] (7.5,0) -- (16.6,9.1);
\draw (7.5,0) -- (20.5,0);
\draw (7.5,0) -- (16.6,-9.1);
\draw (7.5,0) -- (-5.5,0);
\draw (7.5,0) -- (-1.6,-9.1);
\draw (7.5,0) -- (7.5, -13.0);
\draw[line width = 2, color = black](-27.6, 11.1) -- (13.5,-6) -- (-3.6, 35.1) -- (-27.6, 11.1);
\draw[line width = 4, color = red] (7.5,0) -- (-1.6, 9.1);
\draw [black, thick] (7.5,0) circle [radius=16];
\draw [red, fill = pink, line width = 3] (7.5,0) circle [radius=2.5];
\draw [red, fill = gray, ultra thick] (7.5,13) circle [radius=1.5];
\draw [red, fill = yellow, ultra thick] (16.6,9.1) circle [radius=2.5];
\draw [red, fill = gray, ultra thick] (20.5,0) circle [radius=1.5];
\draw [red, fill = gray, ultra thick] (16.6,-9.1) circle [radius=1.5];
\draw [red, fill = gray, ultra thick] (-1.6,-9.1) circle [radius=1.5];
\draw [red, fill = gray, ultra thick] (-5.5,0) circle [radius=1.5];
\draw [red, fill = pink, line width = 3] (-1.6, 9.1) circle [radius=2.5];
\draw [red, fill = gray, ultra thick] (7.5, -13.0) circle [radius=1.5];
\node at (-6.6, 14.1) {\Huge{$\pmb{\beta}$}};
\node at (-1.6, 9.1) {\Large{K}};
\node at (7.5,0) {\Large{I}};
\node at (16.6,9.1) {\Large{J}};
\end{tikzpicture}
\end{center}
\caption{Messages from outer star $\beta$ into edge $(k,i)$}
\end{figure}
\vspace{20 pt}
3) In Denominator: Messages from inner (in $\alpha$) nodes to central node $i \in \alpha$, except message from $j$ to $i$.
4) In Denominator: Message from star $\alpha$ to edge $(i,j) \in \alpha$, from previous iteration.
After integration we will obtain next equations:
\begin{equation}
\begin{split}
m^{(t + 1)}_{\alpha \rightarrow (i,j)} \propto \frac{1}{exp(\sum_{k \in N(i), k\neq j}{ \Delta J^{(t)}_{k \rightarrow i} x_i^2 + \Delta h^{(t)}_{k \rightarrow i}} x_i)} \times \\
\frac{1}{exp(\Delta A^{(t)}_{\alpha \rightarrow (i,j)} x^2_i + \Delta B^{(t)}_{\alpha \rightarrow (i,j)} x_i x_j + \Delta C^{(t)}_{\alpha \rightarrow (i,j)} x^2_j +
\Delta D^{(t)}_{\alpha \rightarrow (i,j)} x_i + \Delta E^{(t)}_{\alpha \rightarrow (i,j)} x_j)} \times \\
\sum_{k \in N(i), k \neq i,j} exp \Big [\frac{1}{4(\frac{1}{2}J_{kk} - \sum_{l \in N(k) \backslash i} \Delta J^{(t)}_{l \rightarrow k} - \Delta A^{(t)}_{\beta_k \rightarrow (k, i)})} \times\\
\big ( x_i^2(\frac{1}{4}J^{(t)}_{ik}^2-J^{(t)}_{ik} \Delta B^{(t)}_{\beta_k \rightarrow (k,i)} + (\Delta B^{(t)}_{\beta_k \rightarrow (k,i)})^2) +\\
+ x_i(-J_{ik} + 2 \Delta B^{(t)}_{\beta_k \rightarrow (k,i)}) \cdot (h_k + \sum_{l \in N(k) \backslash i} \Delta h^{(t)}_{l \rightarrow k} + \Delta D^{(t)}_{\beta_k \rightarrow (k,i)}) \big )
\Big ]
\end{split}
\end{equation}
Where $\beta_{k}$ is a star such that $(k,i) \in \beta_{k}, \beta_{k} \neq \alpha$
%\bibliographystyle{plain}
\bibliography{references}
\end{document}
[ @taylorswift ]* 💜💜♾️♾️ PIZZA 30
0 notes