  We provide simple schemes to build Bayesian Neural Networks (BNNs), block by
block, inspired by a recent idea of computation skeletons. We show how by
adjusting the types of blocks that are used within the computation skeleton, we
can identify interesting relationships with Deep Gaussian Processes (DGPs),
deep kernel learning (DKL), random features type approximation and other
topics. We give strategies to approximate the posterior via doubly stochastic
variational inference for such models which yield uncertainty estimates. We
give a detailed theoretical analysis and point out extensions that may be of
independent interest. As a special case, we instantiate our procedure to define
a Bayesian {\em additive} Neural network -- a promising strategy to identify
statistical interactions and has direct benefits for obtaining interpretable
models.
