extfieldsofstudy:
Computer Science
Mathematics

text:
Reliable Post hoc Explanations: Modeling Uncertainty in Explainability

As black box explanations are increasingly being employed to establish model credibility in high-stakes settings, it is important to ensure that these explanations are accurate and reliable. However, prior work demonstrates that explanations generated by state-of-the-art techniques are inconsistent, unstable, and provide very little insight into their correctness and reliability. In addition, these methods are also computationally inefficient, and require significant hyper-parameter tuning. In this paper, we address the aforementioned challenges by developing a novel Bayesian framework for generating local explanations along with their associated uncertainty. We instantiate this framework to obtain Bayesian versions of LIME and KernelSHAP which output credible intervals for the feature importances, capturing the associated uncertainty. The resulting explanations not only enable us to make concrete inferences about their quality (e.g., there is a 95% chance that the feature importance lies within the given range), but are also highly consistent and stable. We carry out a detailed theoretical analysis that leverages the aforementioned uncertainty to estimate how many perturbations to sample, and how to sample for faster convergence. This work makes the first attempt at addressing several critical issues with popular explanation methods in one shot, thereby generating consistent, stable, and reliable explanations with guarantees in a computationally efficient manner. Experimental evaluation with multiple real world datasets and user studies demonstrate that the efficacy of the proposed framework.

Introduction
As machine learning (ML) models get increasingly deployed in domains such as healthcare and criminal justice, it is important to ensure that decision makers have a clear understanding of the behavior of these models. However, ML models that achieve state-of-the-art accuracy are typically complex black boxes that are hard to understand. As a consequence, there has been a surge in post hoc techniques for explaining black box models [1][2][3][4][5][6][7][8][9][10]. Most popular among these techniques are local explanation methods which explain complex black box models by constructing interpretable local approximations (e.g., LIME [2], SHAP [4], MAPLE [11], Anchors [1]). Due to their generality, these methods are being leveraged to explain a number of classifiers including deep neural networks and ensemble models in a variety of domains such as law, medicine, and finance [12,13].
Existing local explanation methods, however, suffer from several drawbacks. Explanations generated using these methods may be unstable [14][15][16][17][18], i.e., negligibly small perturbations to an instance can result in substantially different explanations. These methods are also inconsistent [19] i.e., multiple runs on the same input instance with the same parameter settings may result in vastly different explanations. There are also no reliable metrics to ascertain the quality of the explanations  Figure 1: Example explanations on for an instance from the COMPAS dataset, where vertical lines indicate the feature importance by LIME (red is negative effect, green is positive) and the shaded region visualizes the uncertainty estimated by BayesLIME. While LIME produces very different and contradictory feature importance for different number of perturbations (1a and 1b), BayesLIME provides more context. The overlapping uncertainty intervals in the explanation computed with 100 perturbations (1a) indicate that it is unclear which feature is the most important. However, the tighter uncertainty intervals in the explanation computed with 2K perturbations (1b) clearly indicates that Female is the most important. output by these methods. Commonly used metrics such as explanation fidelity rely heavily on the implementation details of the explanation method (e.g., the perturbation function used in LIME) and do not provide a true picture of the explanation quality [20]. Furthermore, there exists little to no guidance on determining the values of certain hyperparameters that are critical to the quality of the resulting local explanations (e.g., number of perturbations in case of LIME). Local explanation methods are also computationally inefficient i.e., they typically require a large number of black box model queries to construct local approximations [21]. This can be prohibitively slow especially in case of complex neural models.
In this paper, we identify that modeling uncertainty in black box explanations is the key to addressing all the aforementioned challenges. To this end, we propose a novel Bayesian framework for generating local explanations along with their associated uncertainty. We instantiate this framework to obtain Bayesian versions of LIME and KernelSHAP, namely BayesLIME and BayesSHAP, that not only output point-wise estimates of feature importance but also their associated uncertainty in the form of credible intervals (See Figure 1). We derive closed form expressions for the posteriors of the explanations thereby eliminating the need for any additional computational complexity. The credible intervals produced by our framework not only allow us to make concrete inferences about the quality of the resulting explanations but also produce explanations that satisfy user specified levels of uncertainty (e.g., an end user may request for explanations that satisfy a certain 95% confidence level). In addition, the resulting explanations are also highly consistent and stable. To the best of our knowledge, this work makes the first attempt at addressing several critical challenges in popular explanation methods in one-shots, thereby generating consistent, stable, and reliable explanations with guarantees in a computationally efficient manner.
We carry out theoretical analysis that leverages the measures of uncertainty (credible intervals) produced by our framework to estimate the values of critical hyperparameters. More specifically, we derive a closed form expression for the number of perturbations required to generate explanations that satisfy desired levels of confidence. We also propose a novel sampling technique called focused sampling that leverages uncertainty to determine how to sample perturbations for faster convergence, thereby enabling our framework to generate explanations in a computationally efficient manner.
We evaluate the efficacy of the proposed framework on a variety of datasets including COMPAS, German Credit, ImageNet, and MNIST. Our results demonstrate that the explanations output by our framework are not only highly reliable, but also very consistent and stable (53% more stable than LIME/SHAP on an average). Our experimental results also confirm that we can accurately estimate the number of perturbations needed to generate explanations with a desired level of uncertainty, and that our uncertainty sampling technique speeds up the process of generating explanations by up to a factor of 2 relative to random sampling of perturbations. Lastly, we carry out a user study with 31 human subjects to evaluate the quality of the explanations generated by our framework, demonstrating that our explanations accurately capture the importance of the most influential features.

Notation & Background
Here we introduce notation and discuss two relevant prior approaches, LIME and KernelSHAP.
Notation Let f : R d → [0, 1] denote a black box classifier that takes a data point x with d features, and returns the probability that x belongs to a certain class. Our goal is to explain individual predictions of f . Let φ ∈ R d denote the explanation in terms of feature importances for the prediction f (x), i.e. coefficients φ are treated as the feature contributions to the black box prediction. Note that φ captures the coefficients of a linear model. Let Z be a set of N randomly sampled instances (perturbations) around x. The proximity between x and any z ∈ Z is given by π x (z) ∈ R. We denote the vector of these distances over the N perturbations in Z as Π x (Z) ∈ R N . Let Y ∈ [0, 1] be the vector of the black box predictions f (z) corresponding to each of the N instances in Z. LIME [2] and KernelSHAP [4] are popular model-agnostic local explanation approaches that explain predictions of a classifier f by learning a linear model φ locally around each prediction (i.e. y ∼ φ T z). The objective function for both LIME and KernelSHAP constructs an explanation that approximates the behavior of the black box accurately in the vicinity (neighborhood) of x.
The above objective function has the following closed form solution: The main difference between LIME and KernelSHAP lies in how π x (z) is chosen. In LIME, it is chosen heuristically: π x (z) is computed as the cosine or l 2 distance. KernelSHAP leverages game theoretic principles to compute π x (z), guaranteeing that explanations satisfy certain properties.

Our Framework: Bayesian Local Explanations
In this section, we introduce our Bayesian framework which is designed to capture the uncertainty associated with local explanations of black box models. First, we discuss the generative process and inference procedure for the framework. Then, we highlight how our framework can be instantiated to obtain Bayesian versions of LIME and SHAP. Lastly, we present detailed theoretical analysis for estimating the values of critical hyperparameters, and discuss how to efficiently construct highly accurate explanations with uncertainty guarantees using our framework.

Constructing Bayesian Local Explanations
Our goal here is to explain the behavior of a given black box model f in the vicinity of an instance x while also capturing the uncertainty associated with the explanation. To this end, we propose a Bayesian framework for constructing local linear model based explanations and capturing their associated uncertainty. We model the black box prediction of each perturbation z as a linear combination of the corresponding feature values (φ T z) plus an error term ( ) as shown in Eqn (4). While the weights of the linear combination φ capture the feature importances and thereby constitute our explanation, captures the error that arises due to the mismatch between our explanation φ and the local decision surface of the black box model f . Our complete generative process is shown below: The error term is modeled as a Gaussian whose variance relies on the proximity function π x (z) i.e., ∼ N (0, σ 2 πx(z) ). This proximity function ensures that perturbations closer to the data point x are modeled accurately, while allowing more room for error in case of perturbations that are farther away. π x (z) can be computed using cosine or l 2 distance or other game theoretic principles similar to that of LIME and KernelSHAP (see Section 2). The conjugate priors on φ and σ 2 are shown in Eqn (4). Note that, the distributions on error and feature importance φ both consider the parameter σ 2 . The fact that the prior on the feature importances considers σ 2 has an intuitive interpretation: if we have prior knowledge that the error of the explanation is small, we expect to be more confident about the feature importances. Similarly, if we have prior knowledge the error is large, we expect to be less confident about the feature importances.
Thus, our generative process corresponds to the Bayesian version of the weighted least squares formulation of LIME and KernelSHAP outlined in Eqn. (1), with additional terms to model uncertainty. As in Eqns. (4), the process captures two sources of uncertainty in local explanations: 1) feature importance uncertainty: the uncertainty associated with the feature importances φ, and (2) error uncertainty: the uncertainty associated with the error term which captures how well our explanation φ models the local decision surface of the underlying black box.
Inference Our inference process involves estimating the values of two key parameters: φ and σ 2 . By doing so, we can compute the local explanation as well as the uncertainties associated with feature importances and the error term. Posterior distributions on φ and σ 2 are normal and scaled Inv-χ 2 , respectively, due to the corresponding conjugate priors [22]: Further,φ, V φ , and s 2 can be directly computed: Details of the complete inference procedure including derivations of Eqns. (5)(6)(7) are provided in the Appendix A. Note that our estimate of the posterior mean feature importancesφ (Eqn. (6)) is the same as that of the feature importances computed in case of LIME and KernelSHAP (Eqn. (2)). Remark 3.1. If we use the same proximity function π x (z) in our framework as in LIME or Ker-nelSHAP, the posterior mean of the feature importanceφ output by our framework (Eq (6)) will be equivalent to the feature importances output by LIME or KernelSHAP, respectively.
Feature Importance Uncertainty To obtain the local feature importances and their associated uncertainty, we first compute the posterior mean of the local feature importancesφ using the closed form expression in Eqn. (7). We then estimate the credible interval (measure of uncertainty) around the mean feature importances by repeatedly sampling from the posterior distribution of φ (Eq (5)).

Error Uncertainty
The error term can serve as a proxy for explanation quality because it captures the mismatch between the constructed explanation and the local decision surface of the underlying black box. We first calculate the marginal posterior distribution of by leveraging Eqn (4) and integrating out σ 2 . This results in a three parameter Student's t distribution (derivation in appendix A): We then evaluate the probability density function (PDF) of the above posterior at 0, i.e., P ( = 0) by substituting the value of s 2 computed using Eqn. (7) into the Student's t distribution above (Eqn. (8)). The resulting expression gives us the probability density that the explanation output by our framework perfectly captures the local decision surface underlying the black box. This operation is performed in constant time, adding minimal overhead to non-Bayesian LIME and SHAP. We illustrate how these computed intervals capture the variance in the explanations in Figure 9. BayesLIME and BayesSHAP Our framework can be instantiated to obtain the Bayesian version of LIME by setting the proximity function to π x (z) = exp(−D(x, z) 2 /σ 2 ) where D is a distance metric (e.g. cosine or l 2 distance), and n 0 and σ 2 0 to small values (10 −6 ) so that the prior is uninformative. We compute feature importance uncertainty and error uncertainty for LIME's feature importances.
Our framework can also be instantiated to obtain the Bayesian version of KernelSHAP by setting uninformative prior on σ 2 and π x (z) = where |z| denotes the number of the variables in the variable combination represented by the data point z i.e., the number of non-zero valued features in the vector representation of z. Note that the original SHAP method views the problem of constructing a local linear model as estimating the Shapley values corresponding to each of the features [4]. These Shapley values represent the contribution of each of the features to the black box prediction i.e., f (x) = φ 0 + φ i . Therefore, the measures of uncertainty output by our method BayesSHAP capture the reliability of the estimated variable contributions.
To encourage BayesLIME and BayesSHAP explanations to be sparse, we can use dimensionality reduction or feature selection techniques as used by LIME and SHAP to obtain the top K features [2,4,23]. We can then construct our explanations using the data corresponding to these top K features.

Estimating the Number of Perturbations
One of the major drawbacks of approaches such as LIME and KernelSHAP is that they do not provide any guidance on how to choose the number of perturbations, a key factor in obtaining reliable explanations in an efficient manner. To address this, we leverage the uncertainty estimates output by our framework to compute perturbations-to-go (G), an estimate of how many more perturbations are required to obtain explanations that satisfy a desired level of certainty. This estimate thus predicts the computational cost of generating an explanation with a desired level of certainty and can help determine whether it is even worthwhile to do so. The user specifies the confidence level of the credible interval (denoted as α) and the maximum width of the credible interval (W ), e.g. "width of 95% credible interval should be less than 0.1" corresponds to α = 0.95 and W = 0.1. To estimate G for the local explanation of a data point x, we first generate S perturbations around x (where S is small and chosen by the user) and fit a local linear model using our method 2 . This provides initial estimates of various parameters shown in Eqns (5)-(7) which can then be used to compute G. Theorem 3.3. Given S seed perturbations, the number of additional perturbations required (G) to achieve a credible interval width W of feature importance for a data point x at user-specified confidence level α can be computed as: whereπ S is the average proximity π x (z) for the S perturbations, s 2 S is the empirical sum of squared errors (SSE) between the black box and local linear model predictions, weighted by π x (z), as in (7), and Φ −1 (α) is the two-tailed inverse normal CDF at confidence level α.
Proof (Sketch). To estimate G, we first relate W and α to Var(φ i ), the marginal variance of the feature importance 3 for any feature i, obtained by integrating out σ 2 . Because Student's t can be approximated by a Normal distribution for large degrees of freedom (here, S should be large enough), we use the inverse normal CDF to calculate credible interval width at level α. We compute V φ from (6) using Z, treating its entries as Bernoulli distributed with probability 0.5. Due to the covariance structure of this sampling procedure, the resulting variance estimate after N samples is the sample SSE s 2 S scaled by ≈ 4 π S N (derivation in appendix B). If we assume SSE scales linearly with S, we can take this to be a reasonable estimate of s 2 N at any N . We can then estimate G as

Focused Sampling of Perturbations
Perturbations-to-go (G) provides us with an estimate of how many samples are required to achieve reliable explanations. However, if G is large, querying the black-box model for its predictions on a large number of perturbations can be computationally expensive for larger models [24,25]. To reduce this cost, we develop an alternative sampling procedure called focused sampling which leverages uncertainty estimates to query the black box in a more targeted fashion (instead of querying randomly), thereby reducing the computational cost associated with generating reliable explanations. Inspired by active learning [26], focused sampling strategically prioritizes perturbations whose predictions the explanation is most uncertain about, when querying the black box. This enables the focused sampling procedure to query the black box only for the predictions of the most informative perturbations and thereby learn an accurate explanation with far fewer queries to the black box.
To determine how uncertain our explanation φ is about the black box label for any given instance z, we first compute the posterior predictive distribution for z (derivation in Appendix A), given We refer to this variance as the predictive variance var(ŷ(z)), and it captures how uncertain our explanation φ is about the black box prediction.
The focus sampling procedure first fits the explanation with an initial S perturbations (where S is a small number). We then iterate the following procedure until the desired explanation certainty level is reached. We draw a batch of A candidate perturbations, compute their predictive variance with the Bayesian explanation, and induce a distribution over the perturbations by running softmax on the variances with tempurature parameter τ . We draw a batch of B perturbations from this distribution and query the black box model for their labels. Finally, we refit the Bayesian explanation on all the labeled perturbations collected so far. We provide pseudocode for the uncertainty sampling procedure in Algorithm 1.

Algorithm 1 Focused sampling for local explanations
Require Initialize Z with S seed perturbations.

Experiments
We evaluate the proposed framework by first analyzing the quality of our uncertainty estimates i.e., feature importance uncertainty and error uncertainty. We also assess our estimates of required perturbations (G), and evaluate the computational efficiency of focused sampling. Last, we describe a user study with 31 subjects to assess the informativeness of the explanations output by our framework.
Setup We experiment with a variety of real world datasets spanning multiple applications (e.g., criminal justice, credit scoring) as well as modalities (e.g., structured data, images). Our first structured dataset is COMPAS [27], containing criminal history, jail and prison time, and demographic attributes of 6172 defendants, with class labels that represent whether each defendant was rearrested  [2,4]. For images, we construct super pixels as described in [2] and use them as features (number of super pixels is fixed to 20 per image). For our framework, the desired level of certainty is expressed as the width of the 95% credible interval.
Quality of Uncertainty Estimates A critical component of our explanations is the feature importance uncertainty. To evaluate the correctness of these estimates, we compute how often true feature importances lie within the 95% credible intervals estimated by BayesLIME and BayesSHAP. Note, that by true feature importance, we refer to the best fit linear model output using either the LIME or SHAP kernels. We evaluate the quality of our credible interval estimates by running our methods with 100 perturbations to estimate feature importances and taking the corresponding 95% credible intervals for each test instance. We compute what fraction of the true feature importances fall within our 95% credible intervals. Note, because there are no methods to provide uncertainty estimates for LIME and SHAP, we do not provide further baselines. Since we do not have access to the true feature importances of the complex black box models, following Prop 3.2, we use feature importances computed using a large value of N (N = 10, 000), and treat the resulting estimates as ground truth.
Results for BayesLIME in Table 1 indicate that the true feature importances are close to ideal and indicate the estimates are well calibrated. While the estimates by BayesSHAP are somewhat less calibrated (true feature importances fall within our estimated 95% credible intervals about 89.2 to 98.4% of the time), they still are quite close to ideal. All in all, these results confirm that the credible intervals learned by our methods are well calibrated and therefore highly reliable in capturing the uncertainty of the feature importances. Lastly, though we set our priors to be uninformative in general, we also investigate how sensitive our uncertainty estimates are to hyperparameter choices in Figure 5 in the Appendix. We find that the explanation uncertainty becomes uncalibrated with strong priors. However, our explanations seem to be robust to hyperparameter choices in general.

Correctness of Estimated Number of Perturbations
We assess whether our estimate of perturbations-to-go (G; Section 3.2) is an accurate estimate of the additional number of perturbations needed to reach a desired level of feature importance certainty. We carry out this experiment on MNIST data for the digit "4" (additional datasets explored in Appendix C) and use S = 200 as the initial number of perturbations to obtain a preliminary explanation and its associated uncertainty estimates. We then leverage these estimates to compute G for 6 different certainty levels. First, we observe significant differences in G estimates across instances (details in appendix C) i.e. number of perturbations needed to obtain a particular level of certainty varied significantly across instances-5e-3 6e-3 7e-3 8e-3 9e-3 1e-2 Desired W   Figure 2 show that the observed and desired levels of certainty are well calibrated, demonstrating that G estimates are reliable approximations of the additional number of perturbations needed.
Efficiency of Focused Sampling Focused sampling uses the predictive variance to strategically choose perturbations that will reduce uncertainty in order to be labeled by the black box (section 3.3).
Here, we will evaluate the efficiency of the focused sampling procedure. First, we assess whether focused sampling converges (as measured by error uncertainty (P ( = 0))) more efficiently than random sampling. To this end, we experiment with BayesLIME on Imagenet data for the "French bulldog" class to carry out this analysis. This setting replicates scenarios where LIME is applied to a computationally expensive black box model, making it highly desirable to limit the number of perturbations to reduce total running time. We run each sampling strategy for 2,000 perturbations and plot the number of model queries versus error uncertainty. During focused sampling, we set the batch size B to 50. The results in Figure 3 show that focused sampling results in faster convergence to reliable and high quality explanations; focused sampling stabilizes within a couple hundred model queries while random sampling takes over 1,000. Note, as the inefficiency of querying the black box model increases, the advantages of focused sampling decreasing total running time of the explanations will only become more pronounced. These results clearly demonstrate that focused sampling can significantly speed up the process of generating high quality local explanations. Additionally, in Appendix C, we also check if focused sampling causes any bias (due to sampling based on uncertainty estimates) that results in convergence to a different/wrong explanation, however our results clearly indicate that this is not the case.

Stability of BayesLIME & BayesSHAP
Recall that LIME & SHAP are not stable: small changes to instances can produce substantially different explanations. We consider whether BayesLIME & BayesSHAP produce more stable explanations than their LIME & SHAP counterparts. To perform this analysis, we use the local Lipschitz metric for explanation stability [18]: where x i refers to an instance, N (x i ) is the -ball centered at x i , and φ i and φ j are the explanation parameters for x i and x j . Lower values indicate more stable explanations. We follow the setup outline by Alvarez-Melis and Jaakkola [18] and compute the local Lipschitz values, comparing both LIME & BayesLIME and SHAP & BayesSHAP across Compas, German Credit, MNIST digit "4", and Imagenet "French Bulldog." We perform the comparison using the default number of perturbations in Focused Sampling Random Sampling Figure 3: Efficiency of focused sampling for 100 Imagenet "French bulldog" images, with random sampling as a baseline. We provide mean and standard error. We assess the efficiency of focused sampling by comparing error uncertainty over model queries and show quicker convergence than random sampling.  Figure 4: Assessing the % increase in stability of BayesLIME and BayesSHAP over LIME and SHAP respectively. Our Bayesian methods are significant more stable (ρ < 1e-2 according to Wilcoxon signed-rank test) except for BayesSHAP on German Credit, where there is not a significant difference between the methods (ρ > 0.05).
both LIME & SHAP, and use this same number in the respective Bayesian variants and set the batch size B to half this value. We use focused sampling for BayesLIME and BayesSHAP, and report the % increase in stability of these approaches over LIME and SHAP for 40 test points. The results given in Figure 4 show a clear improvement (on average 53%) in stability in all cases except German Credit for BayesSHAP. Further, we run a Wilcoxon signed-rank test and find our results are statistically significant in all cases (ρ < 1e-2) except for BayesSHAP for German Credit, where there is not a significant difference between the methods (ρ > 0.05). These results demonstrate BayesLIME and BayesSHAP are more stable than previous methods.

User Study
We perform a user study with 31 subjects to compare BayesLIME and LIME explanations on MNIST. We evaluate the following: are explanations with low levels of uncertainty (i.e., most confident explanations) more meaningful to humans? To answer this question, we follow prior work and mask the most important features selected by BayesLIME and LIME [32,4]. We ask users to guess the digit of the masked images. The better the explanation, the more difficult it should be for the users to get it right. Further, the choice to mask the important features is motivated by its success in prior work. We randomly select 15 correctly predicted test images, generate explanations by sweeping over a range of perturbation amounts [10 .5 , ..., 10 3.5 ] incremented by 0.5. We choose the top explanation for each image based on either fidelity (for LIME) or P ( = 0) (for BayesLIME). We sent the user study out to students and researchers with background in computer science. A screen shot of the task is shown in Figure 7 in the Appendix. We find that the explanations output by our methods focus on more informative parts of the image, since hiding them makes it difficult for humans to guess the digit. Users had an error rate of 25.7% for LIME, while it was 30.7% for BayesLIME, both with standard error 0.003 (ρ = 0.028 through a one-tailed two sample t-test). This result indicates that our method BayesLIME and the associated measure of explanation uncertainty result in more high quality and reliable explanations compared to LIME and its associated fidelity metric.

Related Work
Interpretability Methods A variety of interpretability methods have been proposed. Some methods that are inherently interpretable include additive models [33,34], decision lists and sets [35,36], and instance-based explanations [37]. However, black-box models are often more flexible, accurate, and easier to use; thus, there has been a lot of interest in constructing post hoc explanations [38]. These include LIME [2] and SHAP [4,39], which are among the most popular due to their broad applicability and code availability, but saliency maps [5][6][7][8], permutation feature importance [40], and partial dependency plots [41] also follow this paradigm. Other approaches to post hoc explanations focus on rule-based models [1,3], counterfactuals [42,43], and influence functions [9].

Vulnerabilities of Post hoc Explanations
Recent work has shed light on the downsides of post hoc explanation techniques. These methods are often highly sensitive to small changes in inputs [14], are susceptible to manipulation [15,16,44,45], and are not faithful to the underlying black boxes [46]. Perturbation-based explanation methods such as LIME and SHAP are subject to additional criticisms: results vary between runs of the algorithms [18-20, 47, 21], and hyperparameters used to select the perturbations can greatly influence the resulting explanation [20]. Prior work has attempted to tackle the problem of instability in perturbation-based explanations by averaging over several explanations [48,19], however, this is computationally expensive. Other works related to creating more trustworthy explanations include development of sanity checks for explainers [49,17,50]. These techniques represent an important step towards improved usability, given experimental evidence that humans are often too eager to accept inaccurate machine explanations [51][52][53][54]. Recent works theoretically analyze the sources of non-robustness in black box explanations [55][56][57].
Logical and Formal Reasoning Additional related works have considered explaining classifiers through identifying a subset of features that are "sufficient" to explain a prediction [58][59][60][61][62]. Though these methods offer strong guarantees surrounding which features ensure a prediction is achieved, they are not model agnostic. Further, they do not define feature importances associated with the local explanations nor consider ways to improve locally weighted explanations, such as LIME and SHAP.
Bayesian Methods in Explainable ML Few recent works have adopted Bayesian formulations to explain black box models [63][64][65]. Guo et al. [63] introduce a Bayesian non-parametric approach to fit a global surrogate model. Their formulation seeks to fit a mixture of generalizable explanations across instances. Zhao et al. [64] study whether incorporating informative priors improves the stability of the resulting explanations. However, neither of these works focus on modeling the uncertainty of local explanations. Further, these approaches also do not tackle the critical problems of estimating key hyperparameters or improving efficiency of computing explanations.

Conclusion
We developed a Bayesian framework for generating local explanations along with their associated uncertainty. We instantiated this framework to obtain Bayesian versions of LIME and SHAP that output pointwise estimates of feature importances as well as their associated credible intervals. These intervals enabled us to infer the quality of the explanations and output explanations that satisfied user specified levels of uncertainty. We carried out theoretical analysis that leverages these uncertainty measures (credible intervals) to estimate the values of critical hyperparameters (e.g., the number of perturbations). We also proposed a novel sampling technique called focused sampling that leverages uncertainty estimates to determine how to sample perturbations for faster convergence.
While the Bayesian framework addresses several critical challenges (i.e., consistency, stability, modeling uncertainty) associated with LIME and SHAP, there are still certain aspects where it would exhibit the same shortcomings as LIME and SHAP [4,66]. For instance, if the local decision surface of a given black box classifier is highly non-linear, our framework, which relies on local linear approximations, may not be able to capture this non-linear decision surface accurately. In addition, if the perturbation sampling procedures used in LIME and SHAP are used in BayesLIME and BayesSHAP, they will likely be vulnerable to the attacks proposed by Slack et al. [15]. In the future, it would be interesting to extend our framework to produce global explanations with uncertainty guarantees and explore how uncertainty quantification can help calibrate user trust in model explanations.

Acknowledgments
We would like to thank the anonymous reviewers for their insightful feedback. This work is supported in part by the NSF awards #IIS

A Derivations
Model Derivation We write the joint posterior as Lettingφ = (Z T diag(Π x (Z))Z + I) −1 Z T diag(Π x (Z))Y , we group terms in the exponentials according to φ. The intermediate steps can be found in [67]. Supressing dependence on Y and Z, we can write down the conditional posterior of φ as So, we can see that our estimates for the mean and variance of ρ(φ|σ 2 , Y, Z) areφ and σ 2 (Z T diag(Π x (Z))Z + I) −1 . Next, we derive the conditional posterior for σ 2 . We identify the form of the scaled inverse-χ 2 distribution in the joint posterior as in [22] and write where s 2 is defined as in equation 7.

B Proof of Theorems
In these derivations, the perturbation matrices Z have elements Z ij ∈ {0, 1} where each Z ij ∼ Bernoulli(0.5). Note, in these proofs, we take take the priors to be set as in BayesLIME and BayesSHAP, i.e., they have hyperparameter values close to 0.

B.1 Proof of Theorem 3.3
Note that we use N to denote the total perturbations while S denotes the perturabtions collected so far. We use three assumptions stated as follows. First,π N 2 is sufficiently large such atπ N 2 + 1 is equivalent toπ N 2 . Second, N is sufficiently large such that N + 1 is equivalent to N and N N −2 is equivalent to 1. Third, the product of Z T diag(Π x (Z))Z within V φ can be taken at its expected value. First, we state the marginal distribution over feature importance φ i where i is an arbitrary feature importance i ∈ d. This given as where V φ = (Z T diag(Π x (Z))Z + I) −1 . Recall each Z ij is given ∼ Bern(.5) we use the third assumption to write V φ isπ N 2 + 1 for the on diagonal elements andπ N 4 for the off diagonal elements.
We can see this is the case considering that each element in Z is a Bern(.5) draw. We drop the 1 s due to the first assumption.
Let k =π N 2 . It follows directly from Sherman Morrison that the i-th and j-th entries of V φ are given as We see that the diagonals are the same. Thus, we take the P T G estimate in terms of a single marginal φ i . Substituting in the s 2 estimate s 2 S and using the second assumption, we write the variance of marginal φ i as Because feature importance uncertainty is in the form of a credible interval, we use the normal approximation of Var(φ i ) and write where W is the desired width, α is the desired confidence level, and Φ −1 (α) is the two-tailed inverse normal CDF. Finally, we subtract the initial S samples.

B.2 Proposition 3.2
Before providing a proof for proposition 3.2, we note to readers that the claims are related to well known results in bayesian inference (e.g. similar results are proved in [68]). We provide the proofs here to lend formal clarity to the properties of our explanations. Consistency ofφ Recall the mean of φ, denotedφ given in equation 6. To establish consistency, we must show thatφ converges in probability to the trueφ as N → ∞. To avoid confusing trueφ with the distribution over φ, we denote the trueφ as φ * . Thus, we must showφ → p φ * as N → ∞. We writeφ Considering mean of is 0 and using law of large numbers, Convergence of Var( ) Assume we have N → ∞ soφ converges to φ * . The uncertainty over the error term is given as the variance of the distribution in equation 8. The variance of this generalized student's t distribution is given as converges to s 2 for large N . Recalling its definition, s 2 reduces to the local error of the model as N → ∞. which is equivalent to the squared bias of the local model.

C Detailed Results
In this appendix, we provide extended experimental results.

C.1 Explanation Uncertainty Hyperparameter Sensitivity
In the main paper, we assume the priors are set to be uninformative. Though this is the advised configuration for BayesLIME and BayesSHAP because prior information about the local surface is not likely available, we assess the calibration sensitivity of BayesLIME to different choices in the hyperparameters. In figure 5, we perform a grid search over the uncertainty hyperparameters n 0 and σ 2 0 for the MNIST digit "4" class. We find the explanation uncertainty is robust to the choice of hyperparameters. These results indicate BayesLIME calibration is not very sensitive to choices in the hyperparameter values.

C.2 PTG Estimate Results
In the main paper, we provided PTG results for BayesLIME on MNIST. In this appendix, we show the number of perturbations estimated by PTG and additional PTG results on the Imagenet "French bulldog" class.

Number of Perturbations Estimated by PTG
In section 4, we assessed if G produces good estimates of the number of additional samples needed to reach the desired level of feature importance certainty. In figure 6, we show the desired level of certainty (desired width of credible interval W ) versus the actual G estimate (i.e. the estimated number of perturbations) for figure 2 in the main paper. We see the estimated number of perturbations is highly variable depending on desired W .

Further PTG Estimate Results
We provide results for the PTG estimate on Imagenet in Figure 8. We limit the range of uncertainty values compared to MNIST because the Imagenet data is more complex and consequently the required number of perturbations becomes very high. These results further indicate the effectiveness of the PTG estimate.

C.3 User Study
Participate Consent We sent out an email to students and researchers with a background in computer science inviting them to take our user study. At the beginning of the user study, we stated that no Figure 6: Desired CI w versus the actual number of perturbations estimated by P T G in figure 2 of the main paper. We plot mean and standard deviation of G.
personal information would be asked during the study, their answers would be used in a research project, and whether they consented to take the study.

Image of interface
We give an example screen shot from the user study in Figure 7. BayesLIME Toy Example To show how our bayesian methods capture the uncertainty of local explanations, we provide an illustrative example in Figure 9. Rerunning LIME explanations on a toy decision surface (blue lines in the figure), we see LIME has high variance and produces many different explanations. This behavior is particularly sever in the nonlinear surfaces. With a single explanation, BayesLIME captures the uncertainty associated with generating local explanations (black lines in the figure).

C.4 Focused Sampling Results
In this appendix, we provide additional focused sampling results. We include a comparison of focused sampling to random sampling in terms of wall clock time. We also provide results demonstrating the focused sampling procedure is not biased.
Wall Clock Time of Focused Sampling In figure 10, we plot wall clock time versus P ( = 0). This experiment is analogous to figure 3 Figure 9: Rerunning LIME local explanations 1000 times and BayesLIME once for linear and nonlinear toy surfaces using few (25) and many (250) perturbations. The linear surface is given as p(y) ∝ x 1 and the non linear surface is defined as p(y) ∝ sin(x 1 /2) * 10 + cos(10 + (x 1 * x 2 )/2) * cos(x 1 ). We plot each run of LIME in blue and the BayesLIME 95% credible region of the feature importance φ in black. We see that LIME variance is higher with fewer samples and a less linear surface. BayesLIME captures the relative difficulty of explaining each surface through the width the credible region. For instance, BayesLIME is most uncertain in the nonlinear, few samples case because this surface is the most difficult to explain. Uncertainty Sampling Random Sampling Figure 10: Wall clock time needed to converge to a high quality explanation by BayesLIME (analogous to figure 3 in the paper). We use both random sampling and focused sampling over 100 Imagenet images. We provide the mean and standard error for binned estimates of these values. This result demonstrates that focused sampling leads to improved convergence over random sampling in terms of wall clock time.
model queries on the x-axis. We see that uncertainty sampling is more time efficient than random sampling for BayesLIME.

Bias of Focused Sampling
In the main text, we saw that focused sampling converges faster than random sampling. However, it is possible that focused sampling introduces bias into the process due to sampling based on uncertainty estimates, leading to convergence to a different/wrong explanation. To assess whether this occurs in practice, we evaluate the convergence of both focused sampling and random sampling to the "true" explanation on Imagenet (computed with the number of perturbations N = 10, 000 using random sampling). To measure convergence, we compare the L 1 distance of the explanation with the ground truth explanation. The result provided in Figure 11 demonstrates that focused sampling converges to the ground truth explanation with significantly fewer model queries than random sampling. Focused sampling reaches a L 1 distance of 0.1 at 300 queries while it takes upwards of 450 queries for random sampling, indicating improved query efficiency of 30 − 40%. Lastly, as the number of model queries increases (∼1000), we observe an L 1 distance of around 0.06 which is extremely small and the explanations are practically the same as the ground truth. Overall, these results show that focused sampling does not suffer from biases in practice and further demonstrate that focused sampling can lead to significant speedups. Figure 11: Convergence of both focused sampling and random sampling to the ground truth explanation. We see that uncertainty sampling converges more quickly to the ground truth than random sampling, demonstrating that there is minimal bias in the focused sampling procedure and focused sampling converges more efficiently.

C.5 Benchmarking
We also benchmark the efficiency of BayesLIME and BayesSHAP against Guo et al. [63], a related Bayesian explanation method that uses a Bayesian non parametric mixture regression and MCMC for parameter inference. Fixing their mixture regression to a single component results in a similar model to ours and thus is a useful point of comparison. To explain a single instance on ImageNet using VGG16, their approach takes 139.2 seconds, while BayesLIME and BayesSHAP take 20.3 seconds and 21.1 seconds respectively, under the same conditions, demonstrating that the closed form solution is very efficient.

D Explaining a Ground Truth Function
We consider a synthetic experiment in which we observe an underlying ground truth function and verify that lower values of feature importance uncertainty indicate higher proximity between the feature importance estimates and the underlying ground truth function. To this end, we constructed a piecewise linear function of two variables, where each quadrant in the x,y-plane corresponds to a different linear model. We consider the regression coefficients of the quadrant as the ground truth explanation. The piecewise function is given as: f (x, y) = 0.3x + 0.2y if x > 0, y > 0 (26) 0.2x − 0.1y if x > 0, y ≤ 0 − x − 0.05y if x ≤ 0, y ≤ 0 − .8x + 0.2y if x ≤ 0, y > 0 We plot the 1 distance between the BayesLIME feature importance mean and ground truth explanation versus the maximum credible interval width of the BayesLIME explanation. The results given in Figure 12 indicate that tighter credible intervals lead to explanations that are closer to the ground truth, demonstrating that the feature importance uncertainties are meaningful in regards to a ground truth function.

E Compute Used
In this work, we ran all experiments on a single NVIDIA 2080TI & a single NVIDIA Titan RTX GPU.

F Dataset licenses
German Credit is in the public domain, COMPAS uses the MIT license, MNIST uses the Creative Commons Attribution-Share Alike 3.0 license, and Imagenet does not hold copyright of images. Figure 12: Assessing whether tighter credible intervals lead to convergence with ground truth, on an example where the ground truth feature importances are known. Here, we plot The 1 distance between the feature importances menas for BayesLIME and ground truth explanation versus the maximum credible interval width across the explanation.


End-to-end style-conditioned poetry generation: What does it take to learn from examples alone?

In this work, we design an end-to-end model for poetry generation based on conditioned recurrent neural network (RNN) language models whose goal is to learn stylistic features (poem length, sentiment, alliteration, and rhyming) from examples alone. We show this model successfully learns the ‘meaning’ of length and sentiment, as we can control it to generate longer or shorter as well as more positive or more negative poems. However, the model does not grasp sound phenomena like alliteration and rhyming, but instead exploits low-level statistical cues. Possible reasons include the size of the training data, the relatively low frequency and difficulty of these sublexical phenomena as well as model biases. We show that more recent GPT-2 models also have problems learning sublexical phenomena such as rhyming from examples alone.

Introduction
Poetry is a very old form of human language use which is deeply embedded in the heritage of many cultures (Beissinger, 2012;Fabb and Halle, 2010). It is characterized by refined, creative, and sublime expressions and linguistic structure. Thus, it comes as little surprise that automatic poetry generation has long captivated artificial intelligence (AI) researchers (Gervás, 2001;Gonçalo Oliveira et al., 2017), for any general solution to this task will have assuredly brought us a step closer to understanding human creativity.
Poetry generation systems may have manifold applications. For example, an AI tool that could assist songwriters in composing lyrics to a given tune, or even generate them entirely automatically, would have commercial potential. Besides such entertainment-oriented applications, producing tools for poetry generation will necessarily involve the development of poetry analysis tools -since generation and analysis are complementary aspects of poetry (Jhamtani et al., 2019) which may prove useful in their own right. And the production and application of these analysis tools could result in insights into the structural and aesthetic features that distinguish humanpenned poetry from its artificially produced counterpart. Figure 1: Example of alliteration (red), a (near) rhyme (blue), and metre (black/grey). This is the first stanza of 'I felt a Funeral, in my Brain' by Emily Dickinson. The rhyme scheme is 'abcb', the overall lexical sentiment of the stanza is negative (many words are associated with negative sentiment), and the time period is the 19th century.
A crucial factor when producing poetry (either by humans or automatically) is style. While definitions of style have varied considerably over time, space, and fields of study (Herrmann et al., 2015), there is widespread agreement that the study of literary form, not (just) content, is what allows us to determine the criteria for aesthetic appreciation and impact. That is, it is formal or stylistic features that often distinguish sophisticated, effectual, or simply 'good' poetry from poetry that is pedestrian, mundane, or just plain 'bad' (Jakobson, 1960;Shlovsky, 1965;Ganjigunte Ashok et al., 2013;Kao and Jurafsky, 2015;Menninghaus et al., 2017).
In this work, we consider the problem of styleconditioned poetry generation, where the user may specify stylistic factors that the generated text has to fulfil. Our stylistic factors include rhyme, alliteration, sentiment, text length, and time period. Examples of some of our stylistic features (particularly rhyme and alliteration) can be found in Figure 1. (We include metre in the example, but do not consider it in the experiments.) In generating poetry conditioned upon stylistic factors, we explore a theme in the automatic gen-eration of poetry that we believe will dominate the field in the upcoming years: end-to-end generation of formal poetry from examples alone, without the need for human involvement in designing the model or filtering its output (e.g., via hard-coded stylistic constraints on rhyme, alliteration, etc.). We believe advances in this task serve as an indicator of the maturity of natural language processing (NLP) systems as they progress towards true AI. Indeed, the recent success of GPT-3 (Brown et al., 2020) with its focus on few-shot learning (i.e., learning from a few illustrative examples, even without model updating) is inspiration for our work to design poetry generation models that learn relevant stylistic features without any other form of human intervention.
We find that, while our models can capture sentiment, time epoch, and text length, they have trouble learning intricate phonetic stylistic features from examples alone, instead learning low-level statistical cues that are weakly correlated with these target features. This holds both for a classical RNN language model and more recent transformer models (GPT-2). We take this as a negative result and as a challenge for future poetry generation systems, viz., to be able to produce typical relevant stylistic factors of poetry without hard-coding them into the model architecture.

Poetry generation.
In the era of statistical NLP, text generation has evolved along the path of -gram language models (Kneser and Ney, 1995), whose inherent modelling limitations allow them to consider only a finite amount of history when generating next output symbols, to recurrent neural network (RNN) language models (Sutskever et al., 2011), which can take an infinite history into account but suffer from vanishing and exploding gradients, to transformer models (Vaswani et al., 2017), which have constant path lengths between inputs and outputs. Transformers are feed-forward networks that use self-attention between consecutive layers. Their shorter paths between inputs and outputs make it easier to learn long-range dependencies. They can also be parallelized easier. As a consequence, they can be pre-trained on massive amounts of data, where they acquire general text generation abilities (Radford et al., 2019).
Approaches to poetry generation can be categorized into pre-and post-deep learning era approaches. Pre-deep learning approaches were highly handengineered and 'top-down', using specific grammar formalisms and linguistic resources to generate poetry; they typically built stylistic aspects such as rhyme and rhythm into their model architectures (Manurung et al., 2000;Gervás, 2001;Gonçalo Oliveira, 2013;Colton et al., 2012).
Neural approaches to poetry generation learn from collections of real poetry data. Most of them use RNN language models (Zhang and Lapata, 2014;Lau et al., 2018). This framework has also been extended to related tasks such as generating poetry from images (Liu et al., 2018), translating poetry (Ghazvininejad et al., 2018), and generating song lyrics given an input melody (Watanabe et al., 2018). A drawback shared by most poetry generation systems, including even very recent ones (Van de Cruys, 2020; Agarwal and Kann, 2020), is that they require hard-and hand-coded rules to generate poetry with specific properties, such as rhyming and alliteration, or to filter output not having these properties. For example, to ensure rhyming, Lau et al. (2018) exploit the fact that their data (sonnets) has a particular structure from which they can infer that certain word pairs must rhyme, which they incorporate in the modelling. Hämäläinen and Alnajjar (2019) define rules for style features. Agarwal and Kann (2020) tell the model when a rhyming word is required and then modify the prediction process. This means that the models themselves lack the ability to discover elementary properties of poetry themselves, but instead rely on the modeller's intention and ingenuity to do so.
Recently, Jhamtani et al. (2019) introduced an intriguing approach to poetry generation that learns rhyming constraints using an adversarial model: an RNN language model (the generator) generates poetry and a discriminator (the adversary) decides whether the line endings of the generated text are plausible for poetry. The generator and the discriminator compete against each other: the generator tries to generate poetry that the discriminator misclassifies and the discriminator aims at distinguishing generated poetry from human-authored poetry. The authors show that this competition leads to models learning rhyming with higher probability. While this model comes close to our envisioned ideal of a poetry generation system learning from examples alone, it still has the drawback that the modellers need to make the model aware of what to pay attention to (i.e., character information of ending words). This is unsatisfactory given the large space of possible features to consider in generated poetry.
Formally similar approaches to ours are those of Ficler and Goldberg (2017) (2017) conditioned RNN language models on stylistic features such as length and whether the text appears to be professionally written, and on sentiment and theme. They showed this approach to be successful for the given conditions in the movie reviews domain, though they did not deal with the much more challenging case of poetry. Manjavacas et al. (2019) generate hip-hop lyrics conditional upon rhythm and rhyme. To enforce rhyming, they feed phonetic rhyme representations to the model, and thus also encode relevant knowledge top-down into the model.

Poetry evaluation
Evaluation of generated poetry is usually done either automatically or manually. Zhang and Lapata (2014) compare generated lines to manually produced 'gold-standard' lines using BLEU (Papineni et al., 2002), a metric borrowed from machine translation, for the task of continuing an initial line of poetry. They also report perplexity, a widely used metric for language model evaluation. For manual evaluation, they ask human annotators to rate the generated poems for fluency, coherence, meaning, and poeticness. Hopkins and Kiela (2017) and Lau et al. (2018) use a sort of Turing test where they ask human participants to distinguish between human-and computer-generated poems. Lau et al. (2018) additionally have an expert rate generated poetry with respect to metre, rhyme, readability, and emotion. Ghazvininejad et al. (2017) ask crowd-workers to give star ratings for the general quality of the generated poems, and then investigate whether users give higher scores to style-adjusted poems compared to the default poems.
In our work, we choose a simple evaluation scheme that measures whether the generated poetry satisfies user constraints. We do not measure other qualities of the generated poetry as we are mostly interested in whether end-to-end systems can successfully generate poetry from examples alone, without human intervention.

Models
Our goal is to design an end-to-end poetry generation model that learns to associate a desired style feature vector with poetic content and form purely inductively, using examples rather than hand-coded knowledge about what rhyming, alliteration, metre, and sentiment are. To do so, we implement a conditioned language model that samples the next word +1 to be generated conditioned on the history of past words 0 , . . . , and a style constraint . That is, it samples +1 from the conditional distribution ( +1 | 0 , 1 , . . . , , ). We implement the model in this formula by a unidirectional RNN language model. At every time step, the RNN predicts the next word to be generated by sampling from a softmax distribution over the whole vocabulary, taking the current word vector w as well as the current history vector h , which summarizes all past inputs, into account. The model starts generation from a special input token, 'SOS', and generates until it encounters an end-of-sentence token 'EOS'. To take the context into account, we encode it as a feature vector c and concatenate it to every input representation. While there are other possible ways of including c, our way constantly 'reminds' the model of the style context, which we hope better enforces that style in the output. The model is illustrated in Figure 2. Our RNN language model also uses character-level information to build input representations, which may help it to generalize to rare words or sublexical phenomena, such as rhyming. Our implementation is taken from that of Reimers and Gurevych (2017).
For the conditions , we consider the following: Rhyming: How much rhyming is present in a base unit (e.g., a stanza or full poem) of poetry?
We measure the degree of rhyming by using a https://github.com/UKPLab/ emnlp2017-bilstm-cnn-crf supervised rhyme model based on character-level Siamese bidirectional long short-term memory (Bi-LSTM) networks (Haider and Kuhn, 2018), available for English and German. We count both internal and end rhymes as contributing to the rhyme level of a base unit of poetry.
Alliteration: Alliteration is a device, often associated with humour (Mihalcea and Strapparava, 2006), where consecutive words begin with the same sound or sounds. As a character does not uniquely specify a sound in most writing systems (cf. cat and chase), it is not sufficient to compare the first characters of the words. Instead, we use the CMU Sphinx Sequence-to-Sequence graphemeto-phoneme toolkit for converting words into a phonemic representation and then check whether subsequent words start with the same phoneme. We measure the degree of alliteration by counting how many alliterating word sequences occur within a base unit of poetry.

Sentiment:
To determine the sentiment of a base unit of poetry, we use a lexicon lookup approach. For English, we use the opinion lexicon developed by Hu and Liu (2004) and for German, we use the German polarity clues word lists by Waltinger (2010). The English lexicon consists of 2,007 positive and 4,782 negative words and the German lexicon consists of 17,627 positive and 19,962 negative words. In each base unit of poetry, we count the number of words that appear in the positive and negative lists of the lexicon, respectively, and then calculate the difference between these two numbers. The final result is normalized by dividing by the number of total matches for this unit, resulting in the formula = − + , where is the number of positive words found and is the number of negative words found. For instance, if four words of the unit were found in the positive list and six words in the negative list, the final rating is −2/10 = −0.2. https://github.com/cmusphinx/g2p-seq2seq

Training and testing mode
In training mode, we extract sentiment, rhyme, and alliteration levels of poems (or stanzas) and pair them with the poems themselves. The model then predicts the text of poems (next words) based on the previous text and the context vector c. The model is end to end and has no built-in understanding of rhyme, sentiment, nor alliteration, except for what it gleans from its input examples. In testing mode, the user may select a context specification in terms of rhyme, alliteration, and sentiment, which is fed into the RNN language model. The model starts generating from the SOS token and terminates when it has produced the EOS token.

Experimental setup
For training data, we use two small corpora, one English and one German. The English corpus, the Chicago Rhyming Poetry Corpus, has 15,672 training and 1,979 development quatrains, and the German corpus is a small curated subset of Textgrid with 67,054 training and 6,697 development quatrains. We generate quatrain stanzas instead of full poems for speed reasons. As our network architecture, we use a single hidden layer RNN with 64 hidden units, a dropout of 0.2 and input word embeddings of 300 (trained on poetry data using word2vec (Mikolov et al., 2013)) with an additional character-level word representation of dimensionality 25. As optimizer, we use Adam (Kingma and Ba, 2014) with a learning rate of 0.001; we set the batch size to 25.
In general, we obtained very similar results across our two English and German datasets. We report results only for one language per experimental condition.

Results
Text length. As a sanity check, we test whether we can generate stanzas of a desired length. We select lines that have between 4 and 14 tokens from the English Chicago corpus. We then calculate a normalized condition which divides the number of tokens in a line by the maximum number available in the subcorpus, which is 14. The values for thus range from 4 /14 to 1 in the training data. For evaluation, we let the condition range from 0 to 1 in steps of 1 /10; we also include the value 2. Note https://github.com/sravanareddy/rhymedata https://textgrid.de that all values below 4 /14 ≈ 0.2857 as well as 2 were not seen during training. Figure 3 (top) shows average line length per condition , averaged over 100 generated lines for any value of . We see that the value of and the length of the generated output lines correlate strongly. The average line length for = 0.3 is 4, which matches the length of training lines with that value. The model can even extrapolate to unseen values, at least to a certain degree -with a value of 2, the line length exceeds the limit of 100 tokens, indicating overgeneralization, while values smaller than 4 /14 are smoothly extrapolated.

Sentiment.
We infer sentiment from the corpus with the help of word lists: each quatrain receives a rating as previously defined which we then divide by the maximum sentiment rating of the corpus, normalizing the values to a range of −1 (for very negative sentiment) to 1 (for very positive sentiment). After training, we generate 100 quatrains for each ranging from −1 to +1 in steps of 1 /10. Additionally, we add the extreme values of −2 and +2, which were never seen during training. Figure 3 (right) shows the average sentiment rating value in the generated test data as a function of the condition. The average rating of the sentiment in the test data increases linearly with . The model can even extrapolate to the unseen extreme values. Table 1 shows examples of quatrains generated with positive and negative . With a positive , the model tends to sample stanzas containing positively connotated words like 'himmels' (heaven), 'liebe' (love), and 'kuesst' (kisses), while a negative increases the selection of negatively connotated words like 'schwache' (weak), 'angst' (fear), and 'heuchler' (hypocrite). Apparently, the model has understood the semantics of positive and negative sentiment on the sole basis of examples.
Alliteration. In order to control the alliteration level in the generated quatrains, we count how many alliterating sequences there are in a quatrain, as described in Section 3. To normalize these values, we divide them by the maximum number of alliterating sequences in the quatrains of the corpus and add the normalized values as conditional information . We then generate 100 quatrains for each ranging from 0 to 1 in steps of 1 /10. Figure 4 (left) shows that the alliteration level in the test data indeed increases as increases. However, Figure 4 (right) shows that increasing for the test poems has the effect that the model generates longer stanzas; when we further normalize the degree of alliteration measured in the output by the number of tokens in the output, then the correlation between the input condition and the measured normalized alliteration degree in the output disappears. Thus, the model apparently does not understand the phenomenon of alliteration, but instead increases the number of words generated: the longer a poem, the more likely it is to (coincidentally) contain instances of alliteration. We also experimented with the input condition norm , which measures the degree of alliteration per token in a poem, to see if the models would understand the phenomenon of alliteration when they cannot rely on length. Figure 5 (left) shows that this is not the case. There is no clearly visible effect of the input condition on the measured normalized alliteration degree in the generated test data.

Rhyme.
We similarly experiment with internal rhymes within a verse and end rhymes within a quatrain. We consider all possible pairs of distinct ein zeuge o der schoenen du schwerer streit und weinend flehn fuer die schuldlos buch bluehend vom letzten wort mit farb ergeben hirn dein schoenstes und noch sieht ein licht und bluete in die der natur jedwedes blatt zum joche ein tor ist freude ist des ihm thut in liebe die streng umgekehret komm doch er sey der heuchler eins sei mein ewig zugethan sei nicht dann im spott erfuelle des himmels wieder du solltest eh mir geschrieben dass das mit kuesst den lauf die schwache angst Table 1: Examples of automatically generated sentiment-conditioned quatrains using the sentiment conditions = +1 (left) and = −1 (right).
words in a verse and feed them into the rhyme classifier described in Section 3, which returns a cosine distance for each pair. If the distance is smaller than a threshold of 0.2, the pair is classified as rhyming. The number of rhyming word pairs in a quatrain is normalized by division by the maximum number of rhyming word pairs found in the quatrains of the corpus. The results are values between 0 (for no rhyming word pair) and 1 (for quatrains with the most rhyming word pairs). Since also the degree of rhyming is positively correlated with the number of tokens in a stanza, we further divide these values by the number of tokens of the respective quatrain, then scale them again to a range between 0 and 1. We denote this rhyme level as norm . As before, we let norm range from 0 to 1 in steps of 1 /10 and generate 100 quatrains for each value. Figure 5 (right) shows the fraction of rhyming words among all generated words in the output as a function of norm . Similar to the results of conditioning on alliterations, there is no positive correlation of the measured output rhyme level and the input rhyme degree condition when stanza length is accounted for.

Discussion
In our experiments, we found that end-to-end learning of word-level properties such as sentiment and poem length works -the models successfully learn to generate longer or shorter, and more positive or negative poems, when we condition them on these variables. This means that they have understood the semantics of these conditions on the sole basis of examples -i.e., without the need to explicitly encode the conditions into the model architecture. In contrast, conditioning on sublexical phenomena such as rhyming and alliteration was not successful. Instead, we found that the models learned dataset artifacts and biases -in particular, they learned to generate longer stanzas, which coincidentally have higher degrees of rhyming and alliteration. When controlling for this factor, we could not find evidence that the models learn rhyming or alliteration from examples alone. There are several possible explanations for this finding: Dataset size. All our datasets were relatively small in size. It is unclear how model results depend on dataset size in terms of the conditioning variables considered here. In terms of the fluency, coherence, etc. of the generated texts, there is clear evidence that size improves model output -see our discussion of GPT-2 in Section 4.4.
Frequency of phenomena. On a per-token level, very few words rhyme or alliterate: for example, less than 3% of tokens in our datasets are part of an alliteration. This makes it harder to detect the meaning of these phenomena from examples alone. Also, very few stanzas have alliteration or rhyming levels that exceed 0.5, meaning that the model is in 'extrapolation mode' for most of them. A possible remedy for this would be to artificially augment the training data with stanzas having large degrees of alliteration or rhyming.
Word-level vs. sublexical phenomena. We note that sentiment is mostly expressed on the word level and rhyme and alliteration are expressed sublexically (i.e., on the sub-word-level). As RNNs (and other text generation models) produce lexical tokens (one after the other), they may be more naturally suited for the former types of phenomena.
Size of character-level representation. For computational reasons, we kept our RNN language models small, with few hidden units (64) and a small dimensionality of character-level representations for words (25). It is possible that the model simply did not have enough capacity to store the relevant information about the sublexical phenomena of interest. However, it must also be said that increasing model capacity runs the risk of severe overfitting when the training data size is small, as is the case for our datasets.
Heterogeneity of poetry data. It is possible that the heterogeneity of the poetry data (with some stanzas having high and others very low degrees of rhyming and alliteration) confuses the models (Hopkins and Kiela, 2017), particularly when some of these phenomena are very infrequent. While the explanations above are specific to our task of style-conditioned poetry generation, the more general problem of deep models learning dataset artifacts or shortcuts that exploit low-level statistical regularities has often been remarked upon in recent years: Such observations have been made for natural language inference (Poliak et al., 2018) and argumentation mining (Niven and Kao, 2019), among many other tasks. In the following subsection, we re-evaluate our findings using a different model architecture trained on more data.

Using GPT-2 instead of an RNN
In order to explore the capabilities of a transformer model over a generic RNN, we also tuned styleconditioned GPT-2 models on poetry. The main advantage of GPT-2 (based on transformer networks) over standardly trained RNNs is their transfer learning ability: While a standardly trained RNN needs to learn language modelling capabilities only from small amounts of poetry data, GPT-2 is already equipped with general language modelling abilities, obtained from having seen billions of tokens of written English. This makes the output of GPT-2 much more semantically coherent, fluent, and grammatically correct. Nevertheless, we believe that even GPT-2 may have the same problems learning poetry-specific characteristics such as rhyme, metre, and alliteration that our RNN And much, in fact, this lesser world can show Of grief and crime that in the greater grow "You saw," said George, "in that still-hated school How the meek suffer, how the haughty rule Table 2: Example pseudo-quatrain in our data for GPT-2, with (predicted) rhyme scheme 'aabb', negative sentiment, and 18th-century time period. had, presumably because these characteristics have low statistical support in the pre-trained data (e.g., Wikipedia) and for the other reasons named above. We therefore conducted two sets of experiments concerning the generation of style-conditioned poetry where the conditions include rhyme, sentiment, and the time epoch of the poetry to be produced, in English poetry.
Rhyme, sentiment, time epoch. We used a GPT-2 model trained on a larger English poetry corpus that additionally contains information about the time period in which the poems were written; we used pseudo-quatrains (any consecutive sequence of four lines), amounting to over 770K unique examples. A sample pseudo-quatrain from the data is shown in Table 2.
Since GPT-2 can more naturally be run with discrete input text, we trained the model on the 24 different rhyming patterns ('abab', 'abcd', etc.) that we found in the corpus, three sentiment values (positive, negative, neutral), and five different time periods (16th to 20th centuries). We determine the sentiment of a newly generated poem as above but using thresholding (e.g., a poem has a positive sentiment if it has more positive than negative terms), rhyming is predicted as for the RNN, and the time period is learned on the annotated data using a multi-layer perceptron. We tested various hyperparameter configurations and in all cases observed the same result: the model has great difficulty learning rhyming, but can capture the other two stylistic features. The last two phenomena are informed largely by lexical choice while rhyming is informed by sublexical information. To illustrate, with the default configuration, we see accuracy of 7.5% for rhyming (with a random baseline performance of 4.2%), 63% for sentiment (random baseline https://huggingface.co/gpt2 https://github.com/tnhaider/ english-gutenberg-poetry Our model is available at https://github.com/ thekhangnguyen/poetry-gen. of 33%) and 63% for time period (random performance of 20%) when generating about 5,000 poems with the desired styles. Even though the model is not entirely at the random guessing baseline for rhyming, it does not perform much above it and is considerably below the majority baseline of 22% (always producing a poem with 'aabb' rhyme style). Also, the rhyme scheme predicted best by far is 'abcd' involving no rhyming. This requires the model not to rhyme, which the model then also satisfies. Here, the model satisfies 53% of all such user constraints, while it satisfies only 0.4% of more complex constraints such as 'aabb'.

Concluding remarks
Traditional, 'formal' poetry is characterized by intricate form that often expresses itself on the sound level: among the key features are rhyme, metre, and alliteration. Computational treatments typically handle these phenomena by hard-coding them as in purely symbolic AI, by exploiting datasetspecific properties (Lau et al., 2018), or by having models pay special attention to the phenomena in question (e.g., making the models concentrate on the character-level structure of line-ending words) (Jhamtani et al., 2019). However, as we show, current models still seem unable to learn sound-level stylistic aspects from examples alone, without priming them, and even when we specifically condition on such features. This raises the question of where this discrepancy between human and machine text processing  comes from and how it can be addressed in the general case. We envision several solutions for future work: It is possible that end-to-end modelling of phonetic stylistic features is an emergent phenomenon that appears once dataset sizes are large enough; it is also possible that datasets need to be sufficiently clean (e.g., containing only very few different rhyming schemes); or that new model architectures, which do not operate on words or sublexical units, are required (Xue et al., 2021).