marginparsep has been altered.
topmargin has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Estimating Test Performance for AI Medical Devices under Distribution Shift
with Conformal Prediction

Anonymous Authors1

††footnotetext:  1Anonymous Institution, Anonymous City, Anonymous Region,
Anonymous Country. Correspondence to: Anonymous Author
<EMAIL_ADDRESS>
Preliminary work. Under review at ICML Workshop on Principles of Distribution
Shift 2022. Do not distribute.

###### Abstract

Estimating the test performance of software AI-based medical devices under
distribution shifts is crucial for evaluating the safety, efficiency, and
usability prior to clinical deployment. Due to the nature of regulated medical
device software and the difficulty in acquiring large amounts of labeled
medical datasets, we consider the task of predicting the test accuracy of an
arbitrary black-box model on an unlabeled target domain without modification
to the original training process or any distributional assumptions of the
original source data (i.e. we treat the model as a “black-box” and only use
the predicted output responses). We propose a “black-box” test estimation
technique based on conformal prediction and evaluate it against other methods
on three medical imaging datasets (mammography, dermatology, and
histopathology) under several clinically relevant types of distribution shift
(institution, hardware scanner, atlas, hospital). We hope that by promoting
practical and effective estimation techniques for black-box models,
manufacturers of medical devices will develop more standardized and realistic
evaluation procedures to improve the robustness and trustworthiness of
clinical AI tools.

##  1 Introduction

Developing and evaluating AI healthcare software is extremely expensive due to
the collection and curation of large amounts of medical data by clinical
specialists. Even more costly is the process of submitting medical device
software for regulatory approval, integrating it into existing clinical data
infrastructure, training clinicians on appropriate usage, and continual post-
deployment monitoring for failures.

Thus, it would be extremely valuable to be able to accurately estimate the
prediction performance of models at new hospitals, patient populations,
medical scanner equipment, etc. before actual clinical deployment. From a
regulatory point of view, unusually low (or high) test performance could
indicate unidentified or unmitigated risks that could degrade the quality of
AI medical devices in different scenarios. For example, drift in disease
prevalence over time might be quantified and necessitate periodic re-
calibration of the AI algorithm by the device manufacturer.

This problem of trying to identify and rectify performance degradation under
new data populations has been extensively studied as distribution shift, out-
of-distribution detection, and domain generalization Yang et al. (2021); Zhou
et al. (2021). Recent works have begun to investigate techniques and
frameworks for estimating test performance on unlabeled, domain-shifted
distribution.

Deng & Zheng (2020) introduced the notion of predicting performance on an
unlabeled test set and, for this task, evaluated a regression approach using
feature vectors from models trained under different distribution shifts. A
simpler and more practical technique for estimating accuracy on an unlabeled
target distribution was proposed by Garg et al. (2022), which selects a
confidence threshold using accuracy on a source dataset.

In this paper, we propose a novel estimation technique based on conformal
prediction and evaluate it against other “black-box” test estimation methods
on several medical imaging datasets.

##  2 Estimating “Black-box” Test Performance

We make the assumption that the model of a software medical device will be
“static” and not directly accessible. Therefore, for an estimation test method
to be valid for an arbitrary black-box model, we assume only access to
predicted outputs from the model from which to estimate performance. For
example, for a multi-class classification model, $F$, we might only receive a
predicted response of probability scores, $\Delta^{\lvert\mathcal{Y}\rvert}$,
where ${\lvert\mathcal{Y}\rvert}$ is the number of classes and $\Delta$ is the
probability simplex. Additionally, we assume we can access to a portion of the
source distribution’s labeled test set,
$\\{(x,y)\\}_{i=1}^{m}\sim\mathcal{D}^{S}$, to use to estimate the target
distribution unlabeled test set $\\{x\\}_{i=1}^{n}\sim\mathcal{D}^{T}$.

While there are existing techniques for domain adaption and distribution
shift, they necessarily assume a modifiable training procedure or preexisting
knowledge of the type or character of distribution shift (e.g. label shift,
covariate shift, etc.) Lipton et al. (2018). Absent these restrictions, our
objective is to empirically evaluate arbitrary black-box models for medical
applications that might be easily implemented into current deployment
practices for AI medical devices or otherwise useful in informing regulatory
testing and monitoring of machine learning algorithms.

A first intuitive approach to estimating test performance on target data would
be to use the maximum softmax probability as an estimate of accuracy Hendrycks
& Gimpel (2016). While deep learning models have been found to be poorly
calibrated Guo et al. (2017), more recent work finds newer architectures to be
better calibrated than previously thought Minderer et al. (2021). Therefore,
one method to estimate test accuracy is to calculate the average confidence
(AC) score on the unlabeled target test dataset:

$\text{AC}(X^{T})=\mathbb{E}_{x\sim\mathcal{D}^{T}}\left[{\max}_{j\in\mathcal{Y}}F(x)_{j}\right],$
(1)

where $j$ is the index of a particular label’s softmax score.

Another general approach involves computing the difference between source and
target distributions. Guillory et al. (2021) proposes one method, which does
not require model access, that estimates target accuracy with the source
accuracy plus the difference in confidence (DOC) between source and target
datasets:

$\begin{split}DOC(X^{S},Y^{S},X^{T})=\mathbb{E}_{(x,y)\sim\mathcal{D}^{S}}\left[\mathbb{I}\left[{\arg\max}_{y\in\mathcal{Y}}F(x)_{j}=y\right]\right]\\\
+\left|\mathbb{E}_{x\sim\mathcal{D}^{T}}\left[\max_{j\in\mathcal{Y}}F(x)_{j}\right]-\mathbb{E}_{x\sim\mathcal{D}^{S}}\left[\max_{j\in\mathcal{Y}}F(x)_{j}\right]\right|,\end{split}$
(2)

where $\mathbb{I}$ is the indicator function.

A third approach is to choose a score threshold on the source distribution to
estimate the test accuracy on the target distribution. Average threshold
confidence (ATC) is a technique that estimates test accuracy as the expected
number of target data points above a threshold:

$ATC(X^{T})=\mathbb{E}_{x\sim\mathcal{D}^{T}}\left[\mathbb{I}\left[\max_{j\in\mathcal{Y}}s(x)_{j}>t\right]\right],$
(3)

where $t$ is a threshold estimated on some score function,
$s:\Delta^{k}\rightarrow\mathbb{R}$ function. Garg et al. (2022) proposes to
choose $t$ such that the percentage of data points with a score above the
threshold is equal to the accuracy on the source dataset:
$\mathbb{E}_{x\sim\mathcal{D}^{S}}\left[\mathbb{I}\left[s(x)>t\right]\right]=\mathbb{E}_{(x,y)\sim\mathcal{D}^{S}}\left[\mathbb{I}\left[{\arg\max}_{j\in\mathcal{Y}}F(x)_{j}=y\right]\right]$.

###  2.1 Estimating Test Accuracy with Conformal Prediction

Conformal prediction is an approach to distribution-free uncertainty
quantification that provides marginal coverage guarantees on arbitrary models,
such as deep convolutional neural networks Angelopoulos & Bates (2021). In
conformal prediction, a score threshold, $\hat{t}$, is estimated such that the
prediction set, $\mathcal{T}(x)=\\{j\in\mathcal{Y}\mid s(x)_{j}>\hat{t}\\}$,
contains the true label on average, $P\left(Y\in\mathcal{T}(X)\right)\geq
1-\alpha$, where $\alpha$ is some user-specified confidence level. Vovk et al.
(2005). Therefore a prediction on a specific data point will be a set of
plausible classes instead of only that class with the highest softmax score.
The marginal coverage guarantee of conformal prediction assumes that $t$ is
calibrated on a held-out set drawn exchangeably from the test distribution.
Naturally, this assumption is violated under distribution shift. While
conformal prediction can be modified if the type of shift is known Tibshirani
et al. (2019); Podkopaev & Ramdas (2021), we find that base conformal
prediction by itself to be a useful measure of uncertainty by which to
estimate test accuracy on the target distribution. The basic intuition is that
the more data points with large prediction set sizes, the more difficult for
the model to classify these points, and subsequently produce a lower estimated
test performance.

We propose conformal prediction confidence (CPC) to estimate test accuracy on
unlabeled target datasets. We use the conformal prediction method by Sadinle
et al. (2019) and estimate $\hat{t}$ using a small subset of source data and
evaluate two methods of conformal prediction confidence by setting $\alpha$ to
be the source accuracy (CPC-ACC) or the average confidence of the target
dataset (CPC-AC). To estimate test accuracy on target distribution, we take
the expected value of the average softmax score of each prediction set in the
target dataset to be the estimated test accuracy.

$CPC(X^{T})=\mathbb{E}_{x\sim\mathcal{D}^{T}}\left[\mathbb{E}\left[\\{s(x)_{j}\mid
j\in\mathcal{T}(x)\\}\right]\right]$ (4)

See Algorithm 1 for implementation details of CPC-ACC.

Intuitively, more confident prediction will have smaller set sizes and vice
versa. A highly confident prediction may have only one element in its set with
a high score while a less confident prediction may have many elements in the
prediction set. Thus, we would expect the average softmax score for low
confidence predictions (sets with many items) to be less than high confidence
predictions (sets with few items with high scores). Then the average of these
low and high confidence scores can be taken as an estimate of overall accuracy
(in the special case of every prediction set only having one item, namely the
maximum score, CPC-AC is equivalent to AC).

##  3 Experiments

Figure 1: Comparison of test estimation methods using four different architectures on Fitzpatrick dataset (atlas 1 $\rightarrow$ atlas 2); left if without temperature scaling; right is with temperature scaling. Table 1: Comparison by dataset and distribution shift using EfficientNet-B0 averaged over 5 training runs. dataset |  source $\rightarrow$ target (accuracy %) | method | absolute target error
---|---|---|---
|  | no scaling | with scaling
CIFAR-10 | original $(83\%)$ $\rightarrow$ CIFAR-10.1 $(71\%)$ | ATC-MC | $19.8\%\pm 1.4\%$ | $1.6\%\pm 0.7\%$
ATC-NE | $25.3\%\pm 1.2\%$ | $\bf{0.7\%\pm 0.7\%}$
AC | $19.7\%\pm 0.9\%$ | $6.0\%\pm 0.5\%$
DOC | $18.4\%\pm 1.2\%$ | $4.8\%\pm 0.7\%$
CPC-ACC | $19.9\%\pm 0.8\%$ | $8.6\%\pm 0.6\%$
CPC-AC | $\bf{16.2\%\pm 1.0\%}$ | $15.7\%\pm 1.5\%$
Fitzpatrick17K | atlas 1 $(37\%)$ $\rightarrow$ atlas 2 $(51\%)$ | ATC-MC | $35.9\%\pm 0.7\%$ | $2.2\%\pm 2.3\%$
ATC-NE | $44.5\%\pm 0.6\%$ | $2.7\%\pm 2.3\%$
AC | $21.4\%\pm 1.0\%$ | $3.7\%\pm 1.7\%$
DOC | $23.2\%\pm 0.8\%$ | $2.4\%\pm 1.1\%$
CPC-ACC | $17.3\%\pm 1.1\%$ | $\bf{0.8\%\pm 0.5\%}$
CPC-AC | $\bf{1.1\%\pm 0.7\%}$ | $8.7\%\pm 1.0\%$
DMIST | scan. 1 $(70\%$) $\rightarrow$ scan. 2 $(58\%)$ | ATC-MC | $26.8\%\pm 6.5\%$ | $\bf{4.8\%\pm 2.0\%}$
ATC-NE | $33.5\%\pm 9.6\%$ | $4.9\%\pm 1.7\%$
AC | $25.7\%\pm 3.6\%$ | $11.8\%\pm 12.1\%$
DOC | $22.7\%\pm 8.9\%$ | $8.8\%\pm 0.5\%$
CPC-ACC | $26.0\%\pm 3.8\%$ | $13.2\%\pm 11.6\%$
CPC-AC | $\bf{21.4\%\pm 3.3\%}$ | $9.3\%\pm 0.6\%$
scan. 1 $(70\%)$ $\rightarrow$ scan. 3 $(68\%)$ | ATC-MC | $22.5\%\pm 1.8\%$ | $3.2\%\pm 1.6\%$
ATC-NE | $28.7\%\pm 4.4\%$ | $3.9\%\pm 1.3\%$
AC | $19.2\%\pm 3.6\%$ | $6.7\%\pm 11.3\%$
DOC | $\bf{16.7\%\pm 7.8\%}$ | $\bf{2.4\%\pm 1.0\%}$
CPC-ACC | $19.4\%\pm 3.9\%$ | $6.9\%\pm 11.5\%$
CPC-AC | $17.1\%\pm 2.2\%$ | $3.8\%\pm 5.1\%$
scan. 1 $(70\%)$ $\rightarrow$ scan. 4 $(51\%)$ | ATC-MC | $32.1\%\pm 7.2\%$ | $5.6\%\pm 2.6\%$
ATC-NE | $37.4\%\pm 9.5\%$ | $\bf{3.6\%\pm 4.0\%}$
AC | $31.8\%\pm 4.1\%$ | $17.3\%\pm 12.5\%$
DOC | $28.8\%\pm 9.8\%$ | $14.3\%\pm 2.2\%$
CPC-ACC | $32.7\%\pm 4.3\%$ | $20.1\%\pm 11.6\%$
CPC-AC | $\bf{24.4\%\pm 11.0\%}$ | $14.4\%\pm 7.5\%$
DMIST $(67\%)$ $\rightarrow$ external inst. $(52\%)$ | ATC-MC | $35.8\%\pm 5.6\%$ | $9.6\%\pm 5.3\%$
ATC-NE | $38.8\%\pm 6.2\%$ | $15.8\%\pm 5.6\%$
AC | $36.8\%\pm 2.0\%$ | $15.7\%\pm 12.9\%$
DOC | $\bf{20.5\%\pm 15.6\%}$ | $\bf{8.2\%\pm 4.2\%}$
CPC-ACC | $26.3\%\pm 2.7\%$ | $16.8\%\pm 11.2\%$
CPC-AC | $21.1\%\pm 7.3\%$ | $11.7\%\pm 4.1\%$
Camelyon17 | hospital 1 $(99\%)$ $\rightarrow$ hospital 2 $(85\%)$ | ATC-MC | $12.9\%\pm 3.0\%$ | $8.0\%\pm 5.3\%$
ATC-NE | $12.9\%\pm 3.0\%$ | $8.0\%\pm 5.6\%$
AC | $9.8\%\pm 2.8\%$ | $7.7\%\pm 12.9\%$
DOC | $20.9\%\pm 7.5\%$ | $\bf{4.1\%\pm 1.6\%}$
CPC-ACC | $\bf{8.8\%\pm 2.8\%}$ | $7.9\%\pm 4.2\%$
CPC-AC | $11.8\%\pm 1.3\%$ | $4.2\%\pm 3.5\%$

We conduct experiments with four datasets with the associated distribution
shifts:

  * •

CIFAR-10 Krizhevsky (2009) – The source dataset is the original CIFAR-10
(25,000 train / 25,000 validation / 10,000 test), while the target dataset is
CIFAR-10.1 Recht et al. (2018) (2,000 test, 10 classes of 62,000 natural
images)

  * •

Fitzpatrick17K Groh et al. (2021) – The source dataset is the DermaAmin atlas
(7295 train / 811 validation / 3474 test), while the target dataset is Atlas
Dermatologico (3889 test, 114 lesion classes in dermatology images)

  * •

DMIST Pisano et al. (2005) – Distribution shift is evaluated between four
scanner types (1: 12421, 2: 47896, 3: 41311, 4: 6562) and from DMIST (33
institutions) to an external healthcare institution (10,819 test) in a multi-
class breast density rating task of mammograms.

  * •

WILDS-Camelyon17 Sagawa et al. (2021); Bandi et al. (2018) – Distribution
shift is evaluated under source hospitals (302,436 train / 34,904 validation /
33,560 test) to target hospital (85,054 test) for metastases detection
(binary) from histopathology.

We evaluate a variety of network architectures and perform five training runs
for each model. Additionally, we compare results with and without temperature
scaling (TS) to study the effects of softmax calibration on test estimation
methods (although access to the original logits will not likely be available
in most commercial models) Guo et al. (2017).

We report state-of-the-art test accuracy prediction using CPC on several
medical imaging datasets without TS and competitive performance post-TS,
summarized in Table 1. The performance gains with CPC are especially
noticeable on the Fitzpatrick17K dataset, which contains a much larger number
of classes compared to other datasets.

Interestingly, we observe that TS moderates the effect of overestimation of
predicted test accuracy across methods and architectures, as can be seen in
Figures 1– 3. We hypothesize that further analysis of the effect of model
architecture on different medical datasets and tasks will be crucial in
developing robust and reliable performance estimation techniques for medical
applications. Other follow-up work might extend test estimation methods to
other clinically relevant tasks such as semantic segmentation, medical image
registration, and automatic medical report classification.

##  4 Clinical Relevance

When considering clinical deployment, the majority of work incorporating AI
for clinical classification tasks has traditionally focused on model accuracy
and classification performance on in-distribution (ID) data; these models tend
to break down when inferring on out-of-distribution (OOD) data, which could be
images acquired from different cameras, scanners, and/or institutions that may
have different inherent modality, view, and/or quality. This brittleness of
models is evidenced by examples of one-pixel attacks Su et al. (2019) and
pose-perturbed images Alcorn et al. (2019) fooling neural networks. In the
clinical realm, this imposes considerable concern and distress: “black-box”
models that misclassify OOD data can incorrectly disqualify patients from
clinical trials or result in unnecessary procedures. This is particularly
relevant for models designed for radiogenomic prediction in tumors, where
incorrect classification of a tumor-specific genetic marker status could, at
worst, prevent patients from accessing the appropriate targeted therapy.

A second concern is the lack of definitive ground truth and uncertainty with
labeling data in specific clinical domains. Prominent examples of this include
the significant inter-rater variability in ascertaining the pre-neoplastic or
neoplastic status of cervical lesions and the possible presence of
intra/inter-lesional genetic heterogeneity for brain tumors, both of which can
cause “black-box” AI models to fail on external data. Approaches that create
site-specific or dataset-specific models are often unfeasible for these
clinical tasks since this adds to the complexity of having to train and deploy
multiple models for the same task; multiple networks also pose additional
logistical concerns when seeking FDA approval for deployment.

## References

  * Alcorn et al. (2019) Alcorn, M. A., Li, Q., Gong, Z., Wang, C., Mai, L., Ku, W.-S., and Nguyen, A.  Strike (with) a pose: Neural networks are easily fooled by strange poses of familiar objects.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 4845–4854, 2019.
  * Angelopoulos & Bates (2021) Angelopoulos, A. N. and Bates, S.  A gentle introduction to conformal prediction and distribution-free uncertainty quantification.  _CoRR_ , abs/2107.07511, 2021.  URL https://arxiv.org/abs/2107.07511.
  * Bandi et al. (2018) Bandi, P., Geessink, O., Manson, Q., Van Dijk, M., Balkenhol, M., Hermsen, M., Bejnordi, B. E., Lee, B., Paeng, K., Zhong, A., et al.  From detection of individual metastases to classification of lymph node status at the patient level: the camelyon17 challenge.  _IEEE Transactions on Medical Imaging_ , 2018.
  * Deng & Zheng (2020) Deng, W. and Zheng, L.  Are labels necessary for classifier accuracy evaluation?  _CoRR_ , abs/2007.02915, 2020.  URL https://arxiv.org/abs/2007.02915.
  * Garg et al. (2022) Garg, S., Balakrishnan, S., Lipton, Z. C., Neyshabur, B., and Sedghi, H.  Leveraging unlabeled data to predict out-of-distribution performance.  _CoRR_ , abs/2201.04234, 2022.  URL https://arxiv.org/abs/2201.04234.
  * Groh et al. (2021) Groh, M., Harris, C., Soenksen, L., Lau, F., Han, R., Kim, A., Koochek, A., and Badri, O.  Evaluating deep neural networks trained on clinical images in dermatology with the fitzpatrick 17k dataset.  _arXiv preprint arXiv:2104.09957_ , 2021.
  * Guillory et al. (2021) Guillory, D., Shankar, V., Ebrahimi, S., Darrell, T., and Schmidt, L.  Predicting with confidence on unseen distributions.  _CoRR_ , abs/2107.03315, 2021.  URL https://arxiv.org/abs/2107.03315.
  * Guo et al. (2017) Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q.  On calibration of modern neural networks.  _CoRR_ , abs/1706.04599, 2017.  URL http://arxiv.org/abs/1706.04599.
  * Hendrycks & Gimpel (2016) Hendrycks, D. and Gimpel, K.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  _CoRR_ , abs/1610.02136, 2016.  URL http://arxiv.org/abs/1610.02136.
  * Krizhevsky (2009) Krizhevsky, A.  Learning multiple layers of features from tiny images.  Technical report, 2009.
  * Lipton et al. (2018) Lipton, Z. C., Wang, Y., and Smola, A. J.  Detecting and correcting for label shift with black box predictors.  _CoRR_ , abs/1802.03916, 2018.  URL http://arxiv.org/abs/1802.03916.
  * Minderer et al. (2021) Minderer, M., Djolonga, J., Romijnders, R., Hubis, F., Zhai, X., Houlsby, N., Tran, D., and Lucic, M.  Revisiting the calibration of modern neural networks.  _CoRR_ , abs/2106.07998, 2021.  URL https://arxiv.org/abs/2106.07998.
  * Pisano et al. (2005) Pisano, E. D., Gatsonis, C., Hendrick, E., Yaffe, M., Baum, J. K., Acharyya, S., Conant, E. F., Fajardo, L. L., Bassett, L., D’Orsi, C., Jong, R., and Rebner, M.  Diagnostic performance of digital versus film mammography for breast-cancer screening.  _New England Journal of Medicine_ , 353(17):1773–1783, 2005.  doi: 10.1056/NEJMoa052911.  URL https://doi.org/10.1056/NEJMoa052911.  PMID: 16169887.
  * Podkopaev & Ramdas (2021) Podkopaev, A. and Ramdas, A.  Distribution-free uncertainty quantification for classification under label shift, 2021.
  * Recht et al. (2018) Recht, B., Roelofs, R., Schmidt, L., and Shankar, V.  Do cifar-10 classifiers generalize to cifar-10?  2018\.  https://arxiv.org/abs/1806.00451.
  * Sadinle et al. (2019) Sadinle, M., Lei, J., and Wasserman, L.  Least ambiguous set-valued classifiers with bounded error levels.  _Journal of the American Statistical Association_ , 114(525):223–234, 2019.  doi: 10.1080/01621459.2017.1395341.  URL https://doi.org/10.1080/01621459.2017.1395341.
  * Sagawa et al. (2021) Sagawa, S., Koh, P. W., Lee, T., Gao, I., Xie, S. M., Shen, K., Kumar, A., Hu, W., Yasunaga, M., Marklund, H., Beery, S., David, E., Stavness, I., Guo, W., Leskovec, J., Saenko, K., Hashimoto, T., Levine, S., Finn, C., and Liang, P.  Extending the WILDS benchmark for unsupervised adaptation.  _CoRR_ , abs/2112.05090, 2021.  URL https://arxiv.org/abs/2112.05090.
  * Su et al. (2019) Su, J., Vargas, D. V., and Sakurai, K.  One pixel attack for fooling deep neural networks.  _IEEE Transactions on Evolutionary Computation_ , 23(5):828–841, 2019.
  * Tibshirani et al. (2019) Tibshirani, R. J., Barber, R. F., Candes, E. J., and Ramdas, A.  Conformal prediction under covariate shift, 2019.  URL https://arxiv.org/abs/1904.06019.
  * Vovk et al. (2005) Vovk, V., Gammerman, A., and Shafer, G.  _Algorithmic Learning in a Random World_.  Springer-Verlag, Berlin, Heidelberg, 2005.  ISBN 0387001522.
  * Yang et al. (2021) Yang, J., Zhou, K., Li, Y., and Liu, Z.  Generalized out-of-distribution detection: A survey.  _CoRR_ , abs/2110.11334, 2021.  URL https://arxiv.org/abs/2110.11334.
  * Zhou et al. (2021) Zhou, K., Liu, Z., Qiao, Y., Xiang, T., and Loy, C. C.  Domain generalization: A survey.  _CoRR_ , abs/2103.02503, 2021.  URL https://arxiv.org/abs/2103.02503.

##  Appendix A Appendix

Figure 2: Comparison of test estimation methods using four different
architectures on CIFAR-10 dataset (original test set $\rightarrow$ CIFAR-10-1
test set); left if without temperature scaling; right is with temperature
scaling. Figure 3: Comparison of test estimation methods using four different
architectures on DMIST dataset (internal institutions $\rightarrow$ external
institution); left if without temperature scaling; right is with temperature
scaling. Figure 4: Comparison of test estimation methods using four different
architectures on Camelyon dataset (hospital 1 $\rightarrow$ hospital 2); left
if without temperature scaling; right is with temperature scaling. Algorithm 1
Conformal prediction confidence using source accuracy (CPC-ACC)

Input:
source calibration set $\\{(x_{i},y_{i})\\}_{i=1}^{k}\sim\mathcal{D}^{S}$,
target test set $\\{(x_{i},y_{i})\\}_{i=1}^{n}\sim\mathcal{D}^{T}$,
confidence level
$\alpha=\mathbb{E}_{(x,y)\sim\mathcal{D}^{S}}\left[\mathbb{I}\left[{\arg\max}_{j\in\mathcal{Y}}f(x)_{j}=y\right]\right]$,
model $F:X\rightarrow\Delta^{\lvert\mathcal{Y}\rvert}$,
quantile function $Q:\\{\mathbb{R}\\}^{m}\times[0,1]\rightarrow\mathbb{R}$

1: $c\leftarrow\\{\\}$

2: for $i\in\\{1,2,\ldots m\\}$ do

3: $s_{\text{cal}}\leftarrow s_{\text{cal}}\cap\max F(x_{i})$

4: end for

5: $\hat{t}\leftarrow Q(s,\frac{\lceil\alpha\cdot(m+1)\rceil}{m})$

6: $p\leftarrow 0$

7: for $i\in\\{1,2,\ldots n\\}$ do

8: $s\leftarrow F(X_{i})$

9: $\tau\leftarrow\\{j\in\mathcal{Y}\mid s_{j}>\hat{t}\\}$

10: $p\leftarrow p+\frac{1}{\lvert\tau\rvert}\sum_{j\in\tau}s_{j}$

11: end for

12: $p\leftarrow p/n$

Output: estimated target accuracy $p$


# Non-Parametric Learning of
Lifted Restricted Boltzmann Machines

Navdeep Kaur<EMAIL_ADDRESS>Gautam Kunapuli  Sriraam Natarajan
The University of Texas at Dallas

###### Abstract

We consider the problem of discriminatively learning restricted Boltzmann
machines in the presence of relational data. Unlike previous approaches that
employ a rule learner (for structure learning) and a weight learner (for
parameter learning) sequentially, we develop a gradient-boosted approach that
performs both simultaneously. Our approach learns a set of weak relational
regression trees, whose paths from root to leaf are conjunctive clauses and
represent the structure, and whose leaf values represent the parameters. When
the learned relational regression trees are transformed into a lifted RBM, its
hidden nodes are precisely the conjunctive clauses derived from the relational
regression trees. This leads to a more interpretable and explainable model.
Our empirical evaluations clearly demonstrate this aspect, while displaying no
loss in effectiveness of the learned models.

###### keywords:

Restricted Boltzmann Machines, Learning Lifted Models, Functional Gradient
Boosting

††journal: Journal of Approximate Reasoning

##  1 Introduction

Restricted Boltzmann Machines (RBMs, [1]) have emerged as one of the most
popular probabilistic learning methods. Coupled with advances in theory of
learning RBMs: contrastive divergence (CD, [2]), persistent CD [3], and
parallel tempering [4] to name a few, their applicability has been extended to
a variety of tasks [5]. While successful, most of these models have been
typically used with a flat feature representation (vectors, matrices, tensors)
and not necessarily in the context of relational data. In problems where data
is relational, these approaches typically flatten the data by either
propositionalizing them or constructing embeddings that allowed them to employ
standard RBMs. This results in the loss of “natural” interpretability that is
inherent to relational representations, as well as a possible decline in
performance due to imperfect propositionalization/embedding.

Consequently, there has been recent interest in developing neural models that
directly operate on relational data. Specifically, significant research has
been conducted on developing graph convolutional neural networks [6] that
model graph data (a restricted form of relational data). Most traditional
truly relational/logical learning methods [7, 8] are capable of learning with
data of significantly greater complexity, including hypergraphs. Such
representations have also been recently adapted to learning neural models [9,
10, 11]. One recent approach in this direction is Lifted RBMs [12], where
relational random walks were learned over data (effectively, randomized
compound relational features) and then employed as input layer to an RBM.

While reasonably successful, this method still propositionalized relational
features by constructing two forms of data aggregates: counts and
existentials. Motivated by this limitation, we propose a full, lifted RBM
(LRBM), where the inherent representation is relational. Additionally, the
LRBM can be learned without significant feature engineering, that is, a key
component of our approach is discovering the structure of lifted RBMs. We
propose a gradient-boosting approach for learning both the structure and
parameters of LRBMs simultaneously. The resulting hidden nodes are newly
discovered features, represented as conjunctions of logical predicates.

These hidden layers are learned using the machinery of functional-gradient
boosting [13] on relational data. The idea is to learn a sequence of
relational regression trees (RRTs) and then transform them to an LRBM by
identifying appropriate transformations. There are a few salient features of
our approach: (1) in addition to being well-studied and widely used [14, 15,
16, 17], RRTs can be parallelized and adapted easily to new, real-world
domains; (2) our approach can handle hybrid data easily, which is an issue for
many logical learners; (3) perhaps most important, our approach is
explainable, unlike other neural models. This is due to the fact that the
hidden layers of the LRBM are simple conjunctions (paths in a tree), and can
be easily interpreted as opposed to complex embeddings111Embedding approaches
transform data from the input space to a feature space. A familiar example of
this is Principal Components Analysis, which transforms input features to
compound features via linear combination; the new features are no longer
naturally interpretable. This is also the case with deep learning, which
diminish interpretability by chaining increasingly complex feature
combinations across successive layers (for example, autoencoders).. Finally,
(4) due to the nature of our learning method, we learn sparser LRBMs compared
to employing random walks.

We make a few key contributions in this work: (1) as far as we are aware, this
is the first principled approach to learning truly lifted RBMs from relational
data; (2) our representation ensures that the resulting RBM is interpretable
and explainable (due to the hidden layer being simple conjunctions of logical
predicates). We present (3) a gradient-boosting algorithm for simultaneously
learning the structure and parameters of LRBMs as well as (4) a transformation
process to construct a sparse LRBM from an ensemble of relational regression
trees produced by gradient boosting. Finally, (5) our empirical evaluation
clearly demonstrates three aspects: efficacy, efficiency and explainability of
our approach compared to the state-of-the-art on several data sets.

##  2 Background and Related Work

Scalars are denoted in lower-case ($y$, $w$), vectors in bold face
($\mathbf{y}$, $\mathbf{w}$), and matrices in upper case ($Y$, $W$).
$\mathbf{u}^{\intercal}\mathbf{v}$ denotes the dot product between
$\mathbf{u}$ and $\mathbf{v}$.

#### Restricted Boltzmann Machines

RBMs are stochastic neural networks

Figure 1: A discriminative RBMs has a dense set of connections between the
visible and hidden layers. This figure illustrates a discriminative RBM for a
binary classification problem, though this model can naturally handle multi-
class problems by adding additional output nodes (corresponding to the one-hot
vectorization of the label).

consisting of a hidden layer of neurons that model the probability
distribution of a visible layer of neurons. Specifically, discriminative RBMs
[18] (Figure 1) have a Bernoulli input layer (also known as the visible layer,
$\mathbf{v}$), a Bernoulli hidden layer ($\mathbf{h}$) and a softmax output
layer ($\mathbf{y}$). The joint configuration
($\mathbf{y},\mathbf{v},\mathbf{h}$) of the model has the following energy:

$E(\mathbf{y},\mathbf{v},\mathbf{h})=-\mathbf{h}^{\intercal}W\mathbf{v}-\mathbf{b}^{\intercal}\mathbf{v}-\mathbf{c}^{\intercal}\mathbf{h}-\mathbf{d}^{\intercal}\mathbf{y}-\mathbf{h}^{\intercal}U\mathbf{y},$
(1)

where $W$ are the weights between the visible and hidden layer, $U$ are the
weights between the hidden and the output layer, and $\mathbf{b}$,
$\mathbf{c}$, $\mathbf{d}$ are the biases in the visible, hidden and output
layers respectively. Given a (multi-class) label $y=\ell$,
$\ell\in\\{1,\,\ldots,\,C\\}$, the output is a one-hot vector
$\mathbf{y}=(I_{c=\ell})_{c=1}^{C}$. With a slight abuse of notation, we
denote the multi-class label of a training example as $y$, with its
corresponding vectorization in bold as $\mathbf{y}$. The joint probability
distribution of the RBM can be written as:
$P(\mathbf{y},\mathbf{v},\mathbf{h})=\frac{1}{Z}e^{-E(\mathbf{y},\mathbf{v},\mathbf{h})}$,
where $Z$ is normalization constant. While computing
$P(\mathbf{y},\mathbf{v},\mathbf{h})$ is generally intractable, the
conditional, $P(y\mid\mathbf{v})$, can be computed exactly:

$p(y\mid\mathbf{v})=\frac{\exp\left(d_{y}+\sum_{j}\,\zeta(c_{j}+U_{jy}+\sum_{k}W_{jk}v_{k})\right)}{\displaystyle{\sum_{y*\in\\{1,2,..C\\}}}\,\exp\left(d_{y*}+\textstyle{\sum_{j}}\,\zeta(c_{j}+U_{jy*}+\sum_{k}W_{jk}v_{k})\right)},$
(2)

where $\zeta(a)=\log(1+e^{a})$, the softplus function. Our goal is to extend
this formulation to relational domains and learn the resulting Lifted
Restricted Boltzmann Machines (LRBMs) using functional gradient boosting.

#### Functional Gradient Boosting

Functional gradient boosting (FGB), introduced by Friedman [13] in 2001, has
recently emerged as a state-of-the-art ensemble method. Functional gradient
boosting aims to learn a model $f(\cdot)$ by optimizing a loss function
$\mathcal{L}[f]$ by emulating gradient descent. At iteration $m$, however,
instead of explicitly computing the gradient $\partial
L[f_{m-1}](\mathbf{x}_{i},y_{i})$, FGB approximates the gradient using a weak
regression tree222A weak base estimator is any model that is “simple” and
underfits (hence, weak). From a machine-learning standpoint, such weak
learners are high bias, low variance and easy to learn. Shallow decision trees
are an exceptionally popular choice for weak base estimators for ensemble
learning, owing to their algorithmic efficiency and interpretability.,
$\Delta_{m}$.

For a probabilistic model, the loss function is replaced by a (log-)likelihood
function ($L[\psi]$), which is described in terms of a potential function
$\psi(\cdot)$, which FGB aims to learn. FGB begins with an initial potential
$\psi_{0}$; intuitively, $\psi_{0}$ represents the prior of the probability
distribution of target atom. This initial potential can be any function: a
constant, a prior probability distribution or any function that incorporates
background knowledge available prior to learning.

At iteration $m$, FGB approximates the true gradient by a functional gradient
$\Delta_{m}$. That is, gradient boosting will attempt to identify an
approximate gradient $\Delta_{m}$ that corrects the errors of the current
potential, $\psi_{m-1}$. This ensures that the new potential
$\psi_{m}=\psi_{m-1}+\Delta_{m}$ continues to improve. Like most boosting
algorithms, FGB learns $\Delta_{m}$ as a weak regression tree, and ensembles
several such weak trees to learn a final potential function (see Figure 2).
Thus, the final model is a sum of regression trees
$\psi_{m}=\psi_{0}+\Delta_{1}+\ldots+\Delta_{m}$ (Figure 2).

Figure 2: Functional Gradient Boosting, where the loss function is mean
squared error.

In relational models, regression trees are replaced by relational regression
trees (RRTs, [19]). This allows us to learn relational conditional models such
as Relational Dependency Networks [16], Relational Logistic Regression [20],
relational policies [14], discriminative training of undirected models [15]
and even temporal models [21]. Inspired by these methods, we propose to learn
the hidden layer of an LRBM using gradient boosting.

#### Relational Neural Models

Relational Embeddings [22, 23, 24, 25, 26, 27] have gained popularity
recently. A common theme among current approaches is to learn a vector
representation, that is, an embedding for each relation and each entity
present in the knowledge base. Most of these approaches also assume binary
relations, which is a rather restrictive assumption that cannot capture the
richness of real-world relational domains. Further, they need a large number
of embeddings for training, especially the deep-learning-based approaches.
Finally, and possibly most concerning: many embedding approaches cannot easily
generalize to new data, and the entire set of embeddings has to be relearned
with new data, or for every new task.

Approaches closest to our proposed work are relational neural networks [10,
11, 28, 29, 30]; these approaches also represent the structure of a neural
network as first-order clauses as we do. The key difference however, is that
in all these models, clauses have already been obtained either from an expert
or an independent ILP system. That is to say, domain rules that make up its
structure and the resulting neural network architectures are manually
specified, and these approaches typically only perform parameter learning.

Recently, relational neural networks have been proposed for vision tasks [31,
32, 33]. While promising, these networks have fixed, manually-specified
structures and the nature of the relations captured between objects is also
not interpretable or explainable. In contrast, our model learns the structure
and parameters of neural network simultaneously. One common theme among all
these models is that they learn latent features of relational data in their
hidden layers, but our model, being still in its nascent stage, cannot do so
yet.

A few approaches for learning neural network on graphs exist. Graph
convolutional networks [34] enable graph data to be trained directly on
convolutional networks. Another set of popular approaches [35] train a
recurrent neural network on each node of the graph by accepting the input from
neighboring nodes until a fixed point is reached. The work of Scarcelli et al.
[35] extends this by learning embeddings for entities and relations in the
relational graph.

Recently, Pham et al. [9] proposed a neural network architecture where
connections in the different nodes of network are encoded according to given
graph structure. RBMs have also been considered in the context of relational
data. For instance, two tensor based models [36, 37] proposed to lift RBMs by
incorporating a four-order tensor into their architecture that captures
interaction between quartet consisting of two objects, relation existing
between them and hidden layer. Finally, our recent approach [12] learns
relational random walks and uses the counts of the groundings as observed
layer of an RBM.

##  3 Boosting of Lifted RBMs

Recall that our goal is to learn a truly lifted RBM. Consequently, both the
hidden and observed layers of the RBM should be lifted (parameterized as
against propositional RBMs). This is to say that, the observed layers are the
predicates (logical relations describing interactions) in the domain, while
the hidden layer consists of conjunctions of predicates (logical rules)
learned from data. Instead of a complete network, connections exist only
between predicates and hidden nodes that are present in the conjunction. We
illustrate RBM lifting with the following example.

######  Example.

Consider a movie domain that contains the entity types (variables)
$\fol{Person}(\fol{P})$, $\fol{Movie}(\fol{M})$ and $\fol{Genre}(\fol{G})$.
Predicates in this domain describe relationships between the various entities,
such as $\fol{DirectedBy(\fol{M},\fol{P})}$, $\fol{ActedIn(\fol{P},\fol{M})}$,
$\fol{InGenre(M,G)}$ and entity resolution predicates such as
$\fol{SamePerson(P_{1},P_{2})}$ and $\fol{SameGenre(G_{1},G_{2})}$. These
predicates are the atomic domain features, $f_{i}$. The task is to predict the
nature of the collaboration between two persons $\fol{P_{1}}$ and
$\fol{P_{2}}$; this task can be represented via the target predicate:

$\fol{Collaborated(P_{1},P_{2})}\,=\,\left\\{\begin{array}[]{cl}0,&\fol{P_{1}},\fol{P_{2}}\,\,\textrm{never
collaborated},\\\ 1,&\fol{P_{1}}\,\,\textrm{worked under}\,\,\fol{P_{2}},\\\
2,&\fol{P_{2}}\,\,\textrm{worked under}\,\,\fol{P_{1}},\\\
3,&\fol{P_{1}},\fol{P_{2}}\,\,\textrm{collaborated at the same
level}.\end{array}\right.$

To perform this $4$-class classification task, we can construct more complex
lifted features through conjunctions of the atomic domain features. For
example, consider the following lifted feature, $h_{1}$:

$\left(\begin{array}[]{r}\fol{DirectedBy(M_{1},P_{1})\wedge
InGenre(M_{1},G_{1})\,\wedge}\\\ \fol{ActedIn(P_{2},M_{2})\wedge
InGenre(M_{2},G_{2})\,\wedge}\\\ \neg\,\fol{SameGenre(G_{1},G_{2})}\\\
\end{array}\right)\,\Rightarrow\,\fol{\left(\,Collab(P_{1},P_{2})=0\,\right)}.$
($h_{1}$)

This lifted feature is a compound domain rule (essentially a typical
conjunction in logic models) made up of several atomic domain features that
describes one possible classification condition of the target predicate.
Specifically, the lifted feature $h_{1}$ expresses the situation where two
persons $\fol{P_{1}}$ and $\fol{P_{2}}$ are unlikely to have collaborated if
they work in different genres. Every such compound domain rule becomes lifted
feature with a corresponding hidden node. In this example, we introduce two
others:

$\begin{array}[]{lc}\fol{DirBy(M_{1},P_{1})\wedge ActedIn(P_{3},M_{1})\wedge
SamePer(P_{3},P_{2})}\Rightarrow\fol{\left(\,Collab(P_{1},P_{2})=1\,\right),}&(h_{2})\\\
\fol{ActedIn(P_{1},M)\wedge
ActedIn(P_{2},M)}\Rightarrow\fol{\left(\,Collab(P_{1},P_{2})=3\,\right)}.&(h_{3})\end{array}$

Figure 3: An example of a lifted RBM. The atomic predicates each have a
corresponding node in the visible layer ($f_{i}$). Atomic predicates can be
used to create richer features as conjunctions, which are represented as
hidden nodes ($h_{j}$); the connections between the visible and hidden layers
are sparse and only exist when the predicate corresponding to $f_{i}$ appears
in the compound feature $h_{j}$. The output layer is a one-hot vectorization
of a multi-class label $\mathbf{y}$, and has one node for each class $y_{k}$.
The connections between the hidden and output layers are dense and allow all
features to contribute to reasoning over all the classes.

The key intuition is that these rules, or lifted features, capture the latent
structure of the domain and are a critical component of lifting RBMs. The
layers of the lifted RBM are as follows (Figure 3):

  * •

Visible layer, atomic domain predicates: We create a visible node $v_{i}$ for
each lifted atomic domain predicate $f_{i}$. Thus, we can express any possible
structure that can be enumerated as conjunction of these atomic features. In
Figure 3, the visible layer consists of the five atomic predicates introduced
above, $f_{1},\,\ldots,\,f_{5}$.

  * •

Hidden layer, compound domain rule: Each of the compound features can be
represented as a node in the hidden layer, $h_{i}$. In this manner, the lifted
RBM is able to construct and use complex structural rules to reason over the
domain. This is similar to classical neural networks, propositional RBMs and
deep learning, where the hidden layer neurons represent rich and complex
feature combinations.

The key difference from existing architectures is that the connections between
the visible and hidden layers are not dense; rather, they are extremely sparse
and depend only on the atomic predicates that appear in the corresponding
lifted compound features. In Figure 3, the hidden node $h_{1}$ is connected to
the atomic predicate nodes $f_{1}$, $f_{2}$, $f_{3}$ and $f_{5}$, while the
hidden node $h_{3}$ is connected to only the atomic predicate node $f_{2}$.
This allows the lifted RBM to represent the domain structure in a compact
manner. Furthermore, such “compression” can enable acceleration of weight
learning as unnecessary edges are not introduced into the structure.

  * •

Output layer, one-hot vectorization: As mentioned above, the lifted RBM
formulation can easily handle multi-class classification. In this example, the
target predicate can take $4$ values as it corresponds to a $4$-class
classification problem. This can be modelled with four output nodes
$y_{1},\ldots,\,y_{4}$ through one-hot vectorization of the labels. Note that
the connections between the hidden and output layers are dense. This is to
ensure that all features can contribute to the classification of all the
labels.

Furthermore, this enables the lifted RBM to reason with uncertainty. For
example, consider the compound domain feature $h_{1}$, which describes a
condition for two persons to have never collaborated. By ensuring that the
hidden-to-output connections are dense, we allow for the contribution of this
rule to the final prediction to be soft rather than hard. This is similar to
how Markov logic networks learn different rule weights to quantify the
relative importance of the domain rules/lifted features. In a similar manner,
the lifted RBM allows for reasoning under uncertainty by learning the network
weights to reflect the relative significance of various features to different
labels.

Our task now is to learn such lifted RBMs. Specifically, we propose to learn
the structure (compound features as hidden nodes) as well as the parameters
(weights on all the edges and biases within the nodes). This is a key novelty
as our approach uses gradient boosting to learn sparser LRBMs, unlike the
fully connected propositional ones. To learn an LRBM, we need to (1) formulate
the (lifted) potential definitions, (2) derive the functional gradients, (3)
transform the gradients to explainable hidden units of the RBM, and (4) learn
the parameters of the RBM. We now present each of these steps in detail.

###  3.1 Functional Gradient Boosting of Lifted RBMs

The conditional equation (2) which is the basis of an RBM, is formulated for
propositional data, where each feature of a training example $\mathbf{x}_{i}$
is modeled as a node in the input layer $\mathbf{v}$. We now extend this
definition of the RBM to handle logical predicates (i.e., parameterized
relations).

Note that these lifted features (conjunctions) can be obtained in several
different ways: (i) as with many existing work on neuro-symbolic reasoning,
these could be provided by a domain expert, or (ii) can be learned from data
similar to the research inside Inductive Logic Programming [38] or, (iii)
performing random walks in the domain that result in rule structures [12], to
name a few. Any rule induction technique could be employed in this context. In
this work, we adapt a gradient-boosting technique. Given such lifted features
(or rules) $f_{k}(\mathbf{x})$ on training examples $\mathbf{x}$, we can
rewrite equation (2) as

$p(y\mid\mathbf{x})=\frac{\exp\left(d_{y}+\sum_{j}\,\zeta(c_{j}+U_{jy}+\sum_{k}W_{jk}f_{k}(\mathbf{x}))\right)}{\displaystyle{\sum_{y*\in\\{1,2,..C\\}}}\,\exp\left(d_{y*}+\textstyle{\sum_{j}}\,\zeta(c_{j}+U_{jy*}+\sum_{k}W_{jk}f_{k}(\mathbf{x}))\right)}.$
(3)

Contrast this expression to the propositional discriminative RBM (equation 2),
which models $p(y\mid\mathbf{v})$. The key difference is that the
propositional features $\sum_{k}W_{jk}v_{k}$ are replaced with lifted features
$\sum_{k}W_{jk}f_{k}(\mathbf{x})$; while features in a propositional data set
are just the data columns/attributes, the features in a relational data set
are typically represented in predicate logic (as shown in the example above)
and are rich and expressive conjunctions of objects, their attributes and
relations between them.

We now introduce some additional functional notation to simplify (equation 3).
Without loss of generality, we restrict our discussion to the case of binary
targets (with labels $\ell\in\\{0,\,1\\}$) and note that this exposition can
easily be extended to the case of multiple classes. For each label $\ell$, we
define functional

$E(\mathbf{x}_{i}\mid\mathbf{c},W,\mathbf{d}_{\ell},U_{\ell})\,\coloneqq\,d_{\ell}\,+\,\sum_{j}\,\zeta\left(c_{j}+U_{j\ell}+\sum_{k}W_{jk}f_{k}(\mathbf{x}_{i})\right).$

This functional represents the “energy” of the combination
$(\mathbf{x}_{i},\,y_{i}=\ell)$. For binary classification, (equation 3) is
further simplified to

$p(y_{i}=1\mid\mathbf{x}_{i})\,=\,\frac{e^{E(\mathbf{x}_{i}\mid\mathbf{c},W,d_{1},U_{1})}}{e^{E(\mathbf{x}_{i}\mid\mathbf{c},W,d_{0},U_{0})}+e^{E(\mathbf{x}_{i}\mid\mathbf{c},W,d_{1},U_{1})}}.$
(4)

This reformulation is critical for the extension of the discriminative RBM
framework to relational domains as it allows us to rewrite the probability
$p(y_{i}=1\mid\mathbf{x}_{i})$ in terms of a functional that represents the
potential and $\textsf{OF}(\mathbf{x}_{i})$, the observed features of the
training example $\mathbf{x}_{i}$. One of our goals is to learn lifted
features from the set of all possible features. In simpler terms, if
$\mathbf{x}$ is the set of all predicates in the domain and $x$ is the current
target, then the goal is to identify the set of features $\textsf{OF}(x)$ s.t,
$P(x\mid\mathbf{x})=P(x\mid\textsf{OF}(x))$. In Markov network terminology,
this refers to the Markov blanket of the corresponding variable. In a
discriminative MLN framework, $\textsf{OF}(x)$ is the set of weighted clauses
in which the predicate $x$ appears. We can now define the probability in
(equation 4) as

$\displaystyle
p_{\psi}\left(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i})\right)=\frac{e^{\psi(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i}))}}{1+e^{\psi(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i}))}},\,\,\,\
\textrm{where}$ (5)
$\displaystyle\psi(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i}))\,=\,E(\mathbf{x}_{i}\mid\mathbf{c},W,d_{1},U_{1})-E(\mathbf{x}_{i}\mid\mathbf{c},W,d_{0},U_{0}).$
(6)

Note that $\textsf{OF}(\mathbf{x}_{i})$ does not include all the features in
the domain, but only the specific features that are present in the hidden
layer. An example of this can be observed in Figure 3. This LRBM consists of
three lifted features $\langle h_{1},h_{2},h_{3}\rangle$ that correspond to
the three rules mentioned earlier. We can thus explicitly write the potential
function for a lifted RBM (equation 6) in functional form as

$\psi(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i}))=d+\sum_{j}\,\log\left(\frac{1+\exp{\left(c_{j}+U_{j1}+\sum_{k}W_{jk}f_{k}(\mathbf{x}_{i})\right)}}{1+\exp{\left(c_{j}+U_{j0}+\sum_{k}W_{jk}f_{k}(\mathbf{x}_{i})\right)}}\right),$
(7)

Figure 4: Weights in a lifted RBM.

where $d=d_{1}-d_{0}$. This potential functional is parameterized by
$\bm{\theta}\,=\,\\{d,\mathbf{c},W,U_{0},U_{1}\\}$, consisting of (see Figure
4) edge weights and biases. The edge weights to be learned are $W_{jk}$
(between visible node corresponding to feature $f_{k}(\mathbf{x}_{i})$ and
hidden node $h_{j}$) and $U_{j\ell}$ (between hidden node $h_{j}$ and output
node $y_{\ell}$). The biases to be learned are $c_{j}$ on the hidden nodes and
$d_{\ell}$ on the output nodes. However, instead of learning two biases
$d_{1}$ and $d_{0}$, we can learn a single bias $d=d_{1}-d_{0}$ as the
functional $\psi$ only depends on the difference (see equation 7). Given this
functional form, we can now derive a functional gradient that maximizes the
overall log-likelihood of the data

$L(\\{\mathbf{x}_{i},\,y_{i}\\}_{i=1}^{n}\mid\psi)\,=\,\log\prod_{i=1}^{n}p_{\psi}\left(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i})\right)\,=\,\sum_{i=1}^{n}\,\log
p_{\psi}\left(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i})\right).$

The (pointwise) functional gradient of
$L(\\{\mathbf{x}_{i},\,y_{i}\\}_{i=1}^{n}\mid\psi)$ with respect to
$\psi(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i}))$ can be computed as follows,

$\frac{\partial\log
p_{\psi}(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i}))}{\partial\psi(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i}))}\,=\,\mathbb{I}(y_{i}=1)-P(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i}))\,\coloneqq\,\Delta_{i},$

where $\mathbb{I}(y_{i}=1)$ is an indicator function. The pointwise functional
gradient has an elegant interpretation. For a positive example
($\mathbb{I}(y_{i}=1)=1$), the functional gradient $\Delta_{i}$ aims to
improve the model such that $1-P(y_{i}=1)$ is as small as possible, in effect
pushing $P(y_{i}=1)\rightarrow 1$. For a negative example,
($\mathbb{I}(y_{i}=1)=0$), the functional gradient $\Delta_{i}$ aims to
improve the model such that $0-P(y_{i}=1)$ is as small as possible, in effect
pushing $P(y_{i}=1)\rightarrow 0$. Thus, the gradient of each training example
$\mathbf{x}_{i}$ is simply the adjustment required for the probabilities to
match the true observed labels $y_{i}$. The functional gradient derived here
has a similar form to the functional gradients in other relational tasks such
as boosting relational dependency networks [16] Markov logic networks [15] and
relational policies [14] to specify a few.

###  3.2 Representation of Functional Gradients for LRBMs

Our goal now is to approximate the true functional gradient by fitting a
regression function $\hat{\psi}(\mathbf{x})$ that minimizes the squared error
over the pointwise gradients of all the individual training examples:

$\hat{\psi}(\mathbf{x})\,=\,\arg\min_{\psi}\,\sum_{i=1}^{n}(\psi(\mathbf{x}_{i}\mid\textsf{OF}(\mathbf{x}_{i}))-\Delta_{i})^{2}.$
(8)

We consider learning the representation of $\hat{\psi}$ as a sum of relational
regression trees. The key advantage is that a relational tree can be easily
interpreted and explained. To learn a tree to model the functional gradients,
we need to change the typical tree learner. Specifically, the splitting
criteria of the tree at each node is modified; to identify the next literal to
add to the tree, $\fol{r(x)}$, we greedily search for the literal that
minimizes the squared error (equation 8).

Figure 5: A general relational regression tree for lifted RBMs when learning a
target predicate $\fol{t(x)}$. Each path from root to leaf is a compound
feature (also a logical clause $\mathtt{Clause}_{r}$) that enters the RBM as a
hidden node $h_{r}$. The leaf node contains the weights
$\bm{\theta}_{r}\,=\,\\{d^{r},\mathbf{c}^{r},W^{r},U^{r}_{0},U^{r}_{1}\\}$ of
all edges introduced into the lifted RBM when this hidden node/discovered
feature is introduced into the RBM structure.

For a tree-based representation, we employ a relational regression-tree (RRT)
learner [19] to learn a function to approximately fit the gradients on each
example. If we learn an RRT to fit
$\psi(\mathbf{x}_{i}\mid\mathsf{OF}(\mathbf{x}_{i}))$ in equation (7), each
path from the root to a leaf can be viewed as a clause, and the leaf nodes
correspond to an RBM that evaluates to the weight of the clause for that
training example. Figure 5 shows an RRT when learning a lifted RBM via
gradient boosting for some target predicate $\fol{t(x)}$. The node
$\fol{q(x)}$ can be any subtree that has been learned thusfar, and a new
predicate $\fol{r(x)}$ has been identified as a viable candidate for
splitting. On splitting, we obtain two new compound features as evidenced by
two distinct paths from root to the two new leaf nodes. These clauses (paths)
along with their corresponding leaf nodes identify a new structural component
of the RBM, along with corresponding parameters

$\begin{array}[]{cl}(\fol{Clause_{1}})&\bm{\theta}_{1}:\fol{q(x)\wedge
r(x)\Rightarrow t(x)},\\\
(\fol{Clause_{2}})&\bm{\theta}_{2}:\fol{q(x)\wedge\neg r(x)\Rightarrow
t(x)}.\end{array}$

Note that the clause $\fol{q(\cdot)}$ and the predicate $\fol{r(\cdot)}$ are
expressed generally, and their arguments are denoted broadly as $\fol{x}$. In
practice, $\fol{q(\cdot)}$ and $\fol{r(\cdot)}$ can be of different arities
and take any possible entity types in the domain.

###  3.3 Learning Relational Regression Trees

Let us assume that we have learned a relational regression tree till
$\fol{q(x)}$ in Figure 5. Now assume that, we are adding a literal
$\fol{r(x)}$ to the tree at the left-most node of the subtree $\fol{q(x)}$.

Let the feature corresponding to the left branch ($\fol{Clause_{1}}$) be
$f_{1}(\mathbf{x})=\mathbb{I}(\fol{q(x)\wedge r(x)})$, that is, feature
$f_{1}(\mathbf{x})=1$ for all training examples $\mathbf{x}$ that end up at
the leaf $\bm{\theta}_{1}$ and zero otherwise. Similarly, let the feature
corresponding to the right branch ($\fol{Clause_{2}}$) be
$f_{2}(\mathbf{x})=\mathbb{I}(\fol{q(x)\wedge\neg r(x)})$. The potential
function $\psi(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i}))$ can be written using
(equation 7) as:

$\psi(y_{i}=1\mid\textsf{OF}(\mathbf{x}_{i}))\,=\prod_{k=1,2}\left[d^{k}+\log\left(\frac{1+\exp{\left(c^{k}+U_{1}^{k}+W^{k}f_{k}(\mathbf{x}_{i})\right)}}{1+\exp{\left(c^{k}+U_{0}^{k}+W^{k}f_{k}(\mathbf{x}_{i})\right)}}\right)\right]^{f_{k}(\mathbf{x}_{i})}.$
(9)

In this expression, when a training example $\mathbf{x}_{i}$ satisfies
$\fol{Clause_{1}}$, it reaches leaf node $\bm{\theta}_{1}$ and consequently,
we have $f_{1}(\mathbf{x}_{i})=1$ and $f_{2}(\mathbf{x}_{i})=0$. When a
training example $\mathbf{x}_{i}$ satisfies $\fol{Clause_{2}}$, the converse
is true and we have $f_{1}(\mathbf{x}_{i})=0$ and $f_{2}(\mathbf{x}_{i})=1$.
Thus, only one term is active in the expression above and delivers the
potential corresponding to whether the training example $\mathbf{x}_{i}$ is
classified to the left leaf $\bm{\theta}_{1}$ or the right leaf
$\bm{\theta}_{2}$. We can now substitute this expression for the potential in
equation (9) into the loss function (8).

The loss function is used in two ways to grow the RRTs:

  1. 1.

First, we identify the next literal to add to the tree, $\fol{r(x)}$, by
greedily searching for the atomic domain predicate that minimizes the squared
error. This is similar to the splitting criterion used in other lifted
gradient boosting models such as MLN-boosting [15].

  2. 2.

Next, after splitting, we learn parameters for the newly introduced leaf
nodes. That is, for each split of the tree at $\fol{r(x)}$, we learn
$\bm{\theta}_{1}=[d^{1},c^{1},W^{1},$ $U^{1}_{0},U^{1}_{1}]$ for the left
subtree and $\bm{\theta}_{2}=[d^{2},c^{2},W^{2},U^{2}_{0},U^{2}_{1}]$ for the
right subtree. We perform parameter learning via coordinate descent [39].

###  3.4 LRBM-Boost Algorithm:

Algorithm 1 LRBM-Boost: Relational FGB for Lifted RBMs

1:function LRBM-Boost($Data$, $T$, $N$)

2: F0 = $\psi_{0}$ $\triangleright$ set prior of potential function

3: for $1\leq n\leq N$ do

4: S := $\textsc{GenerateExamples}(F_{n-1},Data,T)$ $\triangleright$ examples
for next tree

5: $F_{n}$ := $\textsc{FitRegressionTree}(S,L,T)$ $\triangleright$ learn
regression tree

6: $F_{n}$ = $F_{n}$ \+ $F_{n-1}$ $\triangleright$ add new tree to existing
set

7: end for

8: P(yi = 1 $|$ OF($\textbf{x}_{i}$)) $\propto$ exp($\psi(y_{i}$ = 1$|$
OF($\textbf{x}_{i}$)))

9:end function

10:function FitRegressionTree($S$, $L$, $T$)

11: $Tree$ := $\textsc{CreateTree}(T(X))$ $\triangleright$ create empty Tree

12: $Beam$ := $\\{Root(Tree)\\}$

13: while ($i\leq L$) do $\triangleright$ till max clauses $L$ is reached

14: $N$ := $\textsc{CurrentNodeToExpand}(Beam)$

15: $C$ := $\textsc{GeneratePotentialChildren}(N)$

16: for each $c$ in $C$ do $\triangleright$ greedily search best child

17: $[$ SL, $\Delta_{L}$ $]$ := $\textsc{ExampleSatisfaction}(N\wedge c,S)$
$\triangleright$ left subtree

18: $\Theta_{L}^{c}$ := $\textsc{CoordinateDescent}([S_{L},\Delta_{L}])$
$\triangleright$ learn LRBM params

19: $[$ SR, $\Delta_{R}$ $]$ := $\textsc{ExampleSatisfaction}(N\wedge\neg
c,S)$ $\triangleright$ right subtree

20: $\Theta_{R}^{c}$ := $\textsc{CoordinateDescent}([S_{R},\Delta_{R}])$
$\triangleright$ learn LRBM params

21: $score_{c}$ :=
$\textsc{ComputeSSE}(\Theta_{L}^{c},\Theta_{R}^{c},\Delta_{L},\Delta_{R})$
$\triangleright$ using eq.(8)

22: end for

23: $\hat{c}$ := $\underset{c}{argmin}$($score_{c}$)

24: $\textsc{AddChild}(Tree,N,\hat{c})$

25: $\textsc{Insert}(Beam,\hat{c}.left,\hat{c}.left.score)$

26: $\textsc{Insert}(Beam,\hat{c}.right,\hat{c}.right.score)$

27: end while

28: return Tree

29:end function

We now describe LRBM-Boost algorithm (Algorithm 1) to learn structure and
parameters of LRBM. The algorithm takes instantiated ground facts ($Data$) and
training examples of target $T$ as input and learns $N$ regression trees that
fits the example gradients to set of trees. The algorithm starts by
considering prior potential value $\psi_{0}$ in $F_{0}$, and in order to learn
a new tree, it first generates the regression examples,
$S$=$[$($\mathbf{x}_{i}$,$y_{i}$), $\Delta_{i}]$, in (line 4) where regression
value $\Delta_{i}$ ($I$-$P$) is computed by performing inference of previously
learned trees. These regression examples $S$ serve as input to
FitRegressionTree function (line 5) along with the maximum number of leaves
($L$) in the tree. The next tree $F_{n}$ is then added to set of existing tree
(line 6). The final probability of LRBM can be computed by performing
inference on all $N$ trees in order to obtain $\psi$.

FitRegressionTree function (line 10) generates a relational regression tree
with $L$ leaf nodes. It starts with an empty tree and greedily adds one node
at a time to the tree. In order to add next node to the tree, it first
considers the current node $N$ to expand as the one that has the best score in
the beam (line 14). The potential children $C$ of this node $N$ (line 15) are
constructed by greedily considering and scoring clauses where the parameters
are learned using coordinate descent. Once the $\hat{c}$ is determined, it is
added as the leaf to the tree and the process is repeated.

##  4 Experimental Section

We aim to answer the following questions in our experiments:

  * Q1

How does $\mathtt{LRBM}$-$\mathtt{Boost}$333
https://github.com/navdeepkjohal/LRBM-Boost compare to other relational neural
models?

  * Q2

How does $\mathtt{LRBM}$-$\mathtt{Boost}$ compare to other relational
functional gradient boosting models?

  * Q3

Is an ensemble of weak relational regression trees more effective than a
single strong relational regression tree for constructing Lifted RBMs?

  * Q4

Can we generate an interpretable lifted RBM from the ensemble of weak
relational regression trees learned by LRBM-Boost?

###  4.1 Experimental setup

To answer these questions, we employ seven standard SRL data sets:

UW-CSE [40] contains information about five university domains and the goal is
to predict whether a student is $\fol{AdvisedBy}$ a professor.

IMDB [41] is a data set from movies domain that contains information about
actors, directors and movies. The goal is to predict whether an actor
$\fol{WorkedUnder}$ a director.

CORA [42] is a standard data set for citation matching that contains eight
predicates about details of papers, their venues, and the authors. The aim is
to predict whether two venues represent the $\fol{SameVenue}$.

SPORTS is a data set garnered by crawling facts from NELL [43] containing
details about sports teams and their players. We aim to predict whether a team
plays a particular sport (i.e. $\fol{TeamPlaysSport}$) in this domain.

MUTAGENESIS [44] is data set that consists of information about molecules,
their constituent atoms and their properties. The aim with this data set is to
predict whether an atom is constituent in a molecule (i.e.
$\fol{MoleculeContainsAtom}$).

YEAST2 [45] contains facts about papers published between 1950 and 2012 about
the yeast organism Saccharomyces cerevisiae. The target is whether a paper
$\fol{Cites}$ another paper. Since this data is temporal, a recursive rule
could potentially use the data from the future to predict the past. This
requires restricting the data provided to the learning system from exposing
any future data when predicting at the current time-step.

WEBKB [41] contains information about webpages of students, professors,
courses etc. from four universities. We aim to predict whether a person is
$\fol{CourseTA}$ of a given course.

For all data sets, we generate positive and negative examples in $1:2$ ratio,
perform $5$-fold cross validation for every method being compared, and report
AUC-ROC and AUC-PR on the resulting folds respectively.

For all baseline methods, we use default settings provided by their respective
authors. For our model, we learn $20$ RRTs, each with a maximum number of 4
leaf nodes. The learning rate of online coordinate descent was $0.05$.

###  4.2 Comparison of LRBM-Boost to other relational neural models

To answer Q1, we compare our model to two recent relational neural models. The
first baseline is Relational RBM ($\mathtt{RRBM}$-$\mathtt{C}$) [12]; this
approach uses relational random walks to generate relational features that
describe the structure of the domain. In fact, it propositionalizes and
aggregates counts on these relational random walks as features to describe
each training example. It should be noted that a key limitation of RRBM-C is
that it can only handle binary predicates; our approach LRBM-Boost on the
other hand, can handle any arity.

The second baseline is Lifted Relational Neural Networks ($\mathtt{LRNN})$
[11]. $\mathtt{LRNN}$ mainly focuses on parameter optimization; the structure
of the network is identified using a clause learner: $\mathtt{PROGOL}$ [46].
$\mathtt{PROGOL}$ generated four, eight, six, three, ten, five rules for Cora,
Imdb, Mutagenesis, Sports, Uw-Cse and WebKB respectively. As LRNN cannot
handle the temporal restrictions of Yeast2, we do not evaluate LRNN on it.

Figure 6: Comparing $\mathtt{LRNN}$, $\mathtt{RRBM}$-$\mathtt{C}$,
$\mathtt{MLN}$-$\mathtt{Boost}$ and $\mathtt{LRBM}$-$\mathtt{Boost}$ on AUC-
ROC. Figure 7: Comparing $\mathtt{LRNN}$, $\mathtt{RRBM}$-$\mathtt{C}$,
$\mathtt{MLN}$-$\mathtt{Boost}$ and $\mathtt{LRBM}$-$\mathtt{Boost}$ on AUC-
PR.

Figures 6 and 7 present the results of this comparison on AUC-ROC and AUC-PR.
$\mathtt{LRBM}$-$\mathtt{Boost}$ is significantly better than $\mathtt{LRNN}$
for Mutagenesis and Cora on both AUC-ROC and AUC-PR. Further, it also achieves
better AUC-ROC and AUC-PR than $\mathtt{LRNN}$ on Sports and Uw-Cse data set.
Compared to $\mathtt{RRBM}$-$\mathtt{C}$, $\mathtt{LRBM}$-$\mathtt{Boost}$
performs better for Sports and WebKB on both AUC-ROC and AUC-PR. Also, our
proposed model performs better on Yeast2 on AUC-ROC. Q1 can be now be answered
affirmatively: $\mathtt{LRBM}$-$\mathtt{Boost}$ either performs comparably to
or outperforms state-of-the-art relational neural networks.

###  4.3 Comparison of LRBM-Boost to other relational gradient-boosting models

Since LRBM-Boost is a relational neural network as well as a relational
boosting model, we next compare it to two state-of-the-art relational
functional gradient-boosting baselines: $\mathtt{MLN}$-$\mathtt{Boost}$ [15]
and RDN-Boost [7]. Figures 6 and 7 compare LRBM-Boost to MLN-Boost.
$\mathtt{LRBM}$-$\mathtt{Boost}$ performs better than
$\mathtt{MLN}$-$\mathtt{Boost}$ for Cora and WebKB on AUC-ROC metric. Further,
it performs better than $\mathtt{MLN}$-$\mathtt{Boost}$ for Imdb, Uw-Cse,
Sports and WebKB on AUC-PR. For all the other data sets, both the models have
comparable performance.

We compare LRBM-Boost to RDN-Boost in a separate experiment, owing to a key
difference in experimental setting. We do not convert the arity of predicates
to binary; rather, we compare RDN-Boost and LRBM-Boost by maintaining the
original arity of all the predicates. The results of this experiment on four
domains are reported in Table 1. LRBM-Boost outperforms RDN-Boost in across
the board, and substantially so on larger domains such as Cora. These
comparisons allow us to answer Q2 affirmatively: LRBM-Boost performs
comparably or outperforms state-of-the-art SRL boosting baselines.

Table 1: Comparison of $\mathtt{LRBM}$-$\mathtt{Boost}$ and $\mathtt{RDN}$-$\mathtt{Boost}$. Data Set |  Target |  Measure |  $\mathtt{LRBM}$-$\mathtt{Boost}$ |  $\mathtt{RDN}$-$\mathtt{Boost}$
---|---|---|---|---
Uw$-$Cse |  advisedBy |  AUC-ROC |  0.9719 |  0.9731
AUC-PR |  0.9158 |  0.9049
Imdb |  workedUnder |  AUC-ROC |  0.9610 |  0.9499
AUC-PR |  0.8789 |  0.8537
Cora |  SameVenue |  AUC-ROC |  0.9469 |  0.8985
AUC-PR |  0.9207 |  0.8451
WebKB |  courseTA |  AUC-ROC |  0.6142 |  0.6057
AUC-PR |  0.4553 |  0.4490
|  |  |  |

###  4.4 Effectiveness of boosting relational ensembles

To understand the importance of boosting trees to construct an LRBM, we
compared the performance of the ensemble of relational trees learned by LRBM-
Boost to a single relational tree, similar to trees produced by the TILDE tree
learner [19, 47]. For the latter, we learn a large lifted tree (of depth
$10$), construct an RBM with the hidden layer being every path from root to
leaf of this tree and refer to it as LRBM-NoBoost.

Table 4.4 compares the performance of an ensemble (first row) vs. a single
large tree (last row). LRBM-Boost is statistically superior on Sports, Yeast2
and Cora on both AUC-ROC and AUC-PR and is comparable on others. This asserts
the efficacy of learning ensembles of relational trees by LRBM-Boost rather
than learning a single tree, thus affirmatively answering Q3.

Table 2: Comparison of (a) an ensemble of trees learned by
$\mathtt{LRBM}$-$\mathtt{Boost}$, (b) an explainable Lifted RBM constructed
from the ensemble of trees learned by LRBM-Boost and (c) learning a single,
large, relational probability tree (LRBM-NoBoost).

Model |  AUC |  Sports |  IMDB |  UW-CSE |  Yeast2 |  Cora |  WebKB
---|---|---|---|---|---|---|---
Ensemble LRBM |  ROC |  0.78$\pm$0.03 |  0.95$\pm$0.05 |  0.98$\pm$0.02 |  0.77$\pm$0.02 |  0.86$\pm$0.14 |  0.63$\pm$0.05
PR |  0.64$\pm$0.03 |  0.86$\pm$0.11 |  0.94$\pm$0.06 |  0.64$\pm$0.03 |  0.82$\pm$0.21 |  0.46$\pm$0.08
Explainable LRBM |  ROC |  0.75$\pm$0.01 |  0.95$\pm$0.05 |  0.95$\pm$0.04 |  0.65$\pm$0.05 |  0.80$\pm$0.19 |  0.61$\pm$0.13
PR |  0.57$\pm$0.01 |  0.85$\pm$0.14 |  0.89$\pm$0.06 |  0.53$\pm$0.06 |  0.70$\pm$0.29 |  0.46$\pm$0.10
NoBoost LRBM |  ROC |  0.75$\pm$0.03 |  0.95$\pm$0.05 |  0.98$\pm$0.02 |  0.64$\pm$0.12 |  0.75$\pm$0.21 |  0.66$\pm$0.09
PR |  0.61$\pm$0.01 |  0.86$\pm$0.11 |  0.94$\pm$0.05 |  0.50$\pm$0.14 |  0.61$\pm$0.30 |  0.48$\pm$0.07
|  |  |  |  |  |  |

###  4.5 Interpretability of LRBM-Boost

While Q1–Q3 can be answered quantitatively, Q4 requires a qualitative
analysis. It should be noted that boosted relational models (here, boosted
LRBMs) learn and represent the underlying relational model as a sum of
relational trees. When performing inference, this ensemble of trees is not
converted to a large SRL model as it is far more efficient to aggregate the
predictions of the individual relational trees in the ensemble.

For LRBM-Boost, however, it is possible to convert the ensemble-of-trees
representation into a single LRBM. This step is typically performed to endow
the model with interpretability, explainability or for relationship discovery.
For LRBM-Boost, this procedure is not exact, and the resulting single large
LRBM is almost, but not exactly, equivalent to the ensemble of trees
representation. The procedure itself is fairly straightforward:

  * •

learn a single RRT from the set of boosted RRTs [48] that make up the LRBM,
that is, we empirically learn a single RRT by overfitting it to the
predictions of the weak RRTs (Figure 8).

  * •

transform this single RRT to a lifted RBM (Figure 9); each path from root to
leaf is a conjunction of relational features and enters the LRBM as a hidden
node, with connections to all the output nodes and to the input nodes
corresponding to the predicates that appear in that path.

Figure 8: An example of a combined lifted tree learned from ensemble of trees.
To construct this tree, we compute the regression value of each training
example by traversing through all the boosted trees. Now a single large tree
is overfit to this (modified) training set to generate a single tree. Figure
9: Lifted RBM obtained from the combined tree in Figure 8. Each path along the
tree in that figure represents the corresponding hidden node of LRBM.

This construction leads to sparsity as it allows for only one hidden node to
be activated for each example. Of course, using clauses instead of trees as
with boosting MLNs [15], could relax this sparsity as needed. For our current
domains, this restriction does not significantly affect the performance as
seen in Table 4.4 showing the quantitative results of comparing the
explainable LRBM with the original ensemble LRBM. There is no noticeable loss
in performance as the AUC values decrease marginally, if at all.

Figure 10: Ensemble of trees learned during training of LRBM-Boost. The
ensemble of trees is generated in Sports domain where predicate $\fol{P}$,
$\fol{T}$, $\fol{Z}$ represent $\fol{plays(sports,team)}$,
$\fol{teamplaysagainstteam(team,team)}$ and
$\fol{athleteplaysforteam(athlete,team)}$ respectively and target $R$
represents $\fol{teamplayssport(team,sports)}$. Figure 11: Demonstration of
the conversion of two lifted trees in Figure 10 to LRBM. We create one hidden
node for each path in each regression tree.

A simpler approach to constructing an explainable LRBM to skip aggregating the
RRTs into a large tree and directly map every path in every tree to a hidden
node in the LRBM. For instance, if the ensemble learned 20 balanced trees with
$4$ paths in each of them, the resulting LRBM has $80$ lifted features. An
example transformation is shown in Figure 11 from two trees in Figure 10. Note
that corresponding LRBM has $8$ hidden features which are conjunctions of the
original trees. While in principle it results in an interpretable LRBM, this
can result in a large number of hidden units and thus pruning strategies need
to be employed, a direction that we will explore in the near future. In
summary, it can be said that our LRBM is effective and explainable allowing
when compared to the state-of-the-art approaches in several tasks.

##  5 Conclusion

We presented the first learning algorithm for learning the structure of a
lifted RBM from data. Motivated by the success of gradient-boosting, our
method learns a set of RRTs using boosting and then transforms them to a
lifted RBM. The advantage of this approach is that it leads to learning a
fully lifted model that is not propositionalized using any standard
approaches. We also demonstrated how to induce a single explainable RBM from
the ensemble of trees. Experiments on several data sets demonstrated the
efficacy and effectiveness along with the explainability of the proposed
approach. Combining the different trees in an analytical fashion is an
interesting future direction. Enhancing the ability of the model to handle
incomplete information is essential to adapt to real problems. Learning other
distributions to learn truly hybrid models can lead to several adaptations on
real data. Scaling to very large data sets (in the lines of relational
embeddings) remains an exciting research direction.

##  6 Acknowledgement

The authors gratefully acknowledge the support of AFOSR award
FA9550-18-1-0462. Any opinions, findings, and conclusion or recommendations
expressed in this material are those of the authors and do not necessarily
reflect the view of the AFOSR or the United States government.

## References

## References

  * [1] D. E. Rumelhart, J. L. McClelland, Information Processing in Dynamical Systems: Foundations of Harmony Theory, MIT Press, 1987, Ch. Parallel Distributed Processing: Explorations in the Microstructure of Cognition: Foundations.
  * [2] G. E. Hinton, Training products of experts by minimizing contrastive divergence, Neural Computation 14 (8).
  * [3] T. Tieleman, Training restricted boltzmann machines using approximations to the likelihood gradient, in: ICML, 2008.
  * [4] G. Desjardins, A. Courville, Y. Bengio, P. Vincent, O. Delalleau, Parallel tempering for training of restricted boltzmann machines, in: AISTATS, 2010.
  * [5] G. W. Taylor, G. E. Hinton, S. T. Roweis, Modeling human motion using binary latent variables, in: NeurIPS, 2007.
  * [6] M. Schlichtkrull, T. N. Kipf, P. Bloem, R. van den Berg, I. Titov, M. Welling, Modeling relational data with graph convolutional networks, in: ESWC, 2018.
  * [7] L. De Raedt, K. Kersting, S. Natarajan, D. Poole, Statistical Relational Artificial Intelligence: Logic, Probability, and Computation, Morgan & Claypool, 2016.
  * [8] L. Getoor, B. Taskar, Introduction to Statistical Relational Learning, MIT Press, 2007.
  * [9] T. Pham, T. Tran, D. Phung, S. Venkatesh, Column networks for collective classification, in: AAAI, 2017.
  * [10] S. M. Kazemi, D. Poole, Relnn: A deep neural model for relational learning, in: AAAI, 2018.
  * [11] G. Šourek, V. Aschenbrenner, F. Železny, O. Kuželka, Lifted relational neural networks, in: COCO, 2015.
  * [12] N. Kaur, G. Kunapuli, T. Khot, K. Kersting, W. Cohen, S. Natarajan, Relational restricted boltzmann machines: A probabilistic logic learning approach, in: ILP, 2017.
  * [13] J. Friedman, Greedy function approximation: A gradient boosting machine, Annals of Statistics.
  * [14] S. Natarajan, S. Joshi, P. Tadepalli, K. Kersting, J. Shavlik, Imitation learning in relational domains: A functional-gradient boosting approach, in: IJCAI, 2011.
  * [15] T. Khot, S. Natarajan, K. Kersting, J. Shavlik, Learning Markov logic networks via functional gradient boosting, in: ICDM, 2011.
  * [16] S. Natarajan, T. Khot, K. Kersting, B. Guttmann, J. Shavlik, Gradient-based boosting for statistical relational learning: The relational dependency network case, MLJ.
  * [17] B. Gutmann, K. Kersting, Tildecrf: Conditional random fields for logical sequences, in: ECML, 2006.
  * [18] H. Larochelle, M. Mandel, R. Pascanu, Y. Bengio, Learning algorithms for classification restricted boltzmann machines, JMLR.
  * [19] H. Blockeel, L. De Raedt, Top-down induction of first-order logical decision trees, Artificial Intelligence 101.
  * [20] N. Ramanan, G. Kunapuli, T. Khot, B. Fatemi, S. M. Kazemi, D. Poole, K. Kersting, S. Natarajan, Structure learning for relational logistic regression: An ensemble approach, in: KR, 2018.
  * [21] S. Yang, T. Khot, K. Kersting, S. Natarajan, Learning continuous-time Bayesian networks in relational domains: A non-parametric approach, in: AAAI, 2016.
  * [22] M. Nickel, V. Tresp, H.-P. Kriegel, A three-way model for collective learning on multi-relational data, in: ICML, 2011.
  * [23] A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, O. Yakhnenko, Translating embeddings for modeling multi-relational data, in: NeurIPS, 2013.
  * [24] R. Socher, D. Chen, C. D. Manning, A. Ng, Reasoning with neural tensor networks for knowledge base completion, in: NeuRIPS, 2013.
  * [25] B. Yang, W. Yih, X. He, J. Gao, L. Deng, Embedding entities and relations for learning and inference in knowledge bases, in: ICLR, 2015.
  * [26] M. Nickel, L. Rosasco, T. Poggio, Holographic embeddings of knowledge graphs, in: AAAI, 2016.
  * [27] T. Trouillon, J. Welbl, S. Riedel, E. Gaussier, G. Bouchard, Complex embeddings for simple link prediction, in: ICML, 2016.
  * [28] M. V. França, G. Zaverucha, A. S. D’avila Garcez, Fast relational learning using bottom clause propositionalization with artificial neural networks, MLJ 94 (1).
  * [29] F. DiMaio, J. Shavlik, Learning approximation to inductive logic programming clause evaluation, in: ILP, 2004.
  * [30] H. Lodhi, Deep relational machines, in: ICONIP, 2013.
  * [31] A. Santoro, et al., A simple neural network module for relational reasoning, in: NeurIPS, 2017.
  * [32] F. Sung, Y. Yang, L. Zhang, T. Xiang, P. H. S. Torr, T. M. Hospedales, Learning to compare: Relation network for few-shot learning, in: CVPR, 2018.
  * [33] H. Hu, J. Gu, Z. Zhang, J. Dai, Y. Wei, Relation networks for object detection, in: CVPR, 2018.
  * [34] M. Niepert, M. Ahmed, K. Kutzkov, Learning convolutional neural networks for graphs, in: ICML, 2016.
  * [35] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, G. Monfardini, The graph neural network model, IEEE Transactions.
  * [36] Y. Huang, W. Wang, L. Wang, Conditional high-order boltzmann machine: A supervised learning model for relation learning, in: ICCV, 2015.
  * [37] K. Li, J. Gao, S. Guo, N. Du, X. Li, A. Zhang, LRBM: A restricted boltzmann machine based approach for representation learning on linked data, in: ICDM, 2014\.
  * [38] S. Muggleton, L. D. Raedt, Inductive logic programming: Theory and methods, Journal Of Logic Programming 19.
  * [39] S. J. Wright, Coordinate descent algorithms, Mathematical Programming 151 (1) (2015) 3–34.
  * [40] M. Richardson, P. Domingos, Markov logic networks, MLJ.
  * [41] L. Mihalkova, R. Mooney, Bottom-up learning of Markov logic network structure, in: ICML, 2007.
  * [42] H. Poon, P. Domingos, Joint inference in information extraction, in: AAAI, 2007\.
  * [43] A. Carlson, J. Betteridge, B. Kisiel, B. Settles, E. R. Hruschka, Jr., T. M. Mitchell, Toward an architecture for never-ending language learning, in: AAAI, 2010.
  * [44] H. Lodhi, S. Muggleton, Is mutagenesis still challenging ?, in: ILP, 2005.
  * [45] N. Lao, W. Cohen, Relational retrieval using a combination of path-constrained random walks, JMLR 81.
  * [46] S. Muggleton, Learning from positive data, in: ILP, 1997.
  * [47] J. Neville, D. Jensen, L. Friedland, M. Hay, Learning relational probability trees, in: KDD, 2003.
  * [48] M. W. Craven, J. W. Shavlik, Extracting tree-structured representations of trained networks, in: NeurIPS, 1995.

## Appendix: Inference in a Lifted RBM

The lifted RBM is a template that is grounded for each example during
inference. We first unify the example with the head of the clause (present at
the output layer of LRBM), to obtain a partial grounding of the body of the
clause. The full grounding is then obtained by unifying the partially-ground
clause with evidence to find at least one instantiation of the body of the
clause. We illustrate the inference procedure for a Lifted RBM with three
hidden nodes, and each hidden node corresponding to the rules
($h_{1}$)–($h_{3}$).

#### Example 1

We are given facts: $\fol{ActedIn(p1,m1)}$, $\fol{ActedIn(p1,m2)}$,
$\fol{ActedIn(p2,}$ $\fol{m1)}$, $\fol{ActetdIn(p2,m2)}$. The number of
substitutions depends on the query. Let us assume that the query is
$\fol{Collab(p1,p2)}$ (did $\fol{p1}$ and $\fol{p2}$ collaborate?), which
results in the partial substitution: $\theta=\\{\fol{P_{1}/p1,P_{2}/p2}\\}$.
The inference procedure will proceed as follows:

  * •

The bodies of the clauses ($h_{1}$)–($h_{3}$) are partially grounded using
$\theta=\\{\fol{P_{1}/p1,P_{2}/p2}\\}$:

$\begin{array}[]{l@{\hspace{0.35in}}c}\left(\begin{array}[]{r}\fol{DirectedBy(M_{1},p1)\wedge
InGenre(M_{1},G_{1})\,\wedge}\\\ \fol{ActedIn(p2,M_{2})\wedge
InGenre(M_{2},G_{2})\,\wedge}\\\ \neg\,\fol{SameGenre(G_{1},G_{2})}\\\
\end{array}\right)\hfil\hskip 25.29494pt&(h_{1})\\\ \fol{DirBy(M_{1},p1)\wedge
ActedIn(P_{3},M_{1})\wedge SamePerson(P_{3},p2)}\hfil\hskip
25.29494pt&(h_{2})\\\ \fol{ActedIn(p1,M)\wedge ActedIn(p2,M)}.\hfil\hskip
25.29494pt&(h_{3})\end{array}$

  * •

Next, since the facts do not contain any information about $\fol{DirectedBy}$
or $\fol{SamePerson}$, $h_{1}$ and $h_{2}$ will not be satisfied.

  * •

In order to prove the satisfiability of $h_{3}$, we look at all the available
facts as we attempt to unify each fact with the partially-grounded clause. Say
we first unify $\fol{ActedIn}$($\fol{p1}$, $\fol{m1}$) with $h_{3}$ that gives
us:

$\fol{ActedIn}(\fol{p1},\fol{m1}),\fol{ActedIn}(\fol{p2},\fol{M}),\hskip
18.06749pt(h_{3})$

resulting in the grounding: $\theta=\\{\fol{P_{1}/p1,M/m1,P_{2}/p2}\\}$. The
second fact $\fol{ActedIn}$($\fol{p1}$, $\fol{m2}$) does not unify with this
partially-grounded clause. However, the third fact $\fol{ActedIn}(\fol{p2}$,
$\fol{m1})$ unifies with $h_{3}$ giving us a fully-grounded clause:

$\fol{ActedIn}(\fol{p1},\fol{m1}),\fol{ActedIn}(\fol{p2},\fol{m1}).\hskip
18.06749pt(h_{3})$

The input nodes corresponding to the unified facts
$\fol{ActedIn(p1,m1),Acted}$ $\fol{In(p2,m1)}$ are activated. As soon as this
clause is satisfied the search terminates. The main conclusion to be drawn is
that as soon as the clause is satisfied once, model does not check for another
satisfaction and terminates the search by returning true.

  * •

The inputs are then propagated through the RBM, and the class output
probabilities are computed based on the RBM edge parameters/weights. The
activation paths for inference given this query and facts are shown in Figure
12.

Figure 12: LRBM inference for Example 1.

#### Example 2

We are given facts: $\fol{DirectedBy(m1,p1)}$, $\fol{InGenre(m1,g1)}$,
$\fol{ActedIn}$ $\fol{(p2,m2)}$, $\fol{InGenre(m2,g2)}$,
$\fol{DirectedBy(m01,p01)}$, $\fol{ActedIn(p03,m01)}$,
$\fol{SamePerson(p03,p02)}$. Recall that the number of substitutions depends
on the query. Let us assume that the query is $\fol{Collab(p01,p02)}$ (did
$\fol{p01}$ and $\fol{p02}$ collaborate?), which results in the partial
substitution: $\theta=\\{\fol{P_{1}/p01,P_{2}/p02}\\}$. The inference
procedure will proceed as follows:

  * •

The bodies of the clauses ($h_{1}$)–($h_{3}$) are partially grounded using
$\theta=\\{\fol{P_{1}/p01,P_{2}/p02}\\}$:

$\begin{array}[]{l@{\hspace{0.35in}}c}\left(\begin{array}[]{r}\fol{DirectedBy(M_{1},p01)\wedge
InGenre(M_{1},G_{1})\,\wedge}\\\ \fol{ActedIn(p02,M_{2})\wedge
InGenre(M_{2},G_{2})\,\wedge}\\\ \neg\,\fol{SameGenre(G_{1},G_{2})}\\\
\end{array}\right)\hfil\hskip 25.29494pt&(h_{1})\\\
\fol{DirBy(M_{1},p01)\wedge ActedIn(P_{3},M_{1})\wedge
SamePerson(P_{3},p02)}\hfil\hskip 25.29494pt&(h_{2})\\\
\fol{ActedIn(p01,M)\wedge ActedIn(p02,M)}.\hfil\hskip
25.29494pt&(h_{3})\end{array}$

  * •

Unifying the partially-grounded clauses with the facts, we will have that
$h_{1}$ and $h_{3}$ will not be satisfied. However, unification yields one
fully-grounded $h_{2}$ will:

$\fol{DirBy(m01,p01)\wedge ActedIn(p03,m01)\wedge SamePerson(p03,p02)},\hskip
21.68121pt(h_{2})$

which has the substitution:
$\theta=\\{\fol{P_{1}/p01,M/m01,P_{2}/p02,P_{3}/p03}\\}$. As before, once a
satisfied grounding is obtained, the search is terminated.

  * •

The RBM is unrolled as in Example 1, and the appropriate facts that appear in
this grounding are activated in the input layer. The prediction is obtained by
propagating these inputs through the network.