Full “Laplacianised” posterior naive Bayesian algorithm

Abstract

Background

In the last decade the standard Naive Bayes (SNB) algorithm has been widely employed in multi–class classification problems in cheminformatics. This popularity is mainly due to the fact that the algorithm is simple to implement and in many cases yields respectable classification results. Using clever heuristic arguments “anchored” by insightful cheminformatics knowledge, Xia et al. have simplified the SNB algorithm further and termed it the Laplacian Corrected Modified Naive Bayes (LCMNB) approach, which has been widely used in cheminformatics since its publication.

In this note we mathematically illustrate the conditions under which Xia et al.’s simplification holds. It is our hope that this clarification could help Naive Bayes practitioners in deciding when it is appropriate to employ the LCMNB algorithm to classify large chemical datasets.

Results

A general formulation that subsumes the simplified Naive Bayes version is presented. Unlike the widely used NB method, the Standard Naive Bayes description presented in this work is discriminative (not generative) in nature, which may lead to possible further applications of the SNB method.

Conclusions

Starting from a standard Naive Bayes (SNB) algorithm, we have derived mathematically the relationship between Xia et al.’s ingenious, but heuristic algorithm, and the SNB approach. We have also demonstrated the conditions under which Xia et al.’s crucial assumptions hold. We therefore hope that the new insight and recommendations provided can be found useful by the cheminformatics community.

Background

Broadly speaking there are two conceptually different ways to solve statistical problems: the frequentist and the Bayesian approaches. On the pros and cons of each method there are numerous excellent review articles and text books, such as the recent book by Murphy [1]. Unlike the frequentist approach, in the Bayesian approach any a priori knowledge about the probability distribution function that one assumes might have generated the given data (in the first place) can be taken into account when estimating this distribution function from the data at hand. If the data are noise–free and “complete”, the role of the a priori information in estimating the distribution function diminishes drastically. However, the a priori information can be crucial when the data are noisy and sparse. The latter scenario is typical in realistic large chemical datasets, which, arguably, makes Bayesian based statistics a powerful data analysis tool.

Unfortunately, Bayesian statistics in its fullest form is not computationally feasible in realistic cheminformatics data analyses. However, in recent years, a simplified version of the Bayesian approach, which is commonly known as the “Naive” Bayesian algorithm, has been found to be a useful classification tool in multi–class classification problems in cheminformactics. To this end a Naive Bayesian classifier is built on binary descriptor space. The descriptors/features x _j , representing the compounds to be classified, assume binary values 0 or 1, where (j = 1,2,...,L) and L can typically be more than 1,000. Thus for some cheminformatics practitioners even the Naive Bayesian algorithm in its standard form is computationally prohibitive when the dataset is large. In this regard, Xia et al. [2] proposed a simpler version of the standard Naive Bayesian algorithm, albeit for binary classification problems; slight variants of this algorithm for multi–class classification can also be found in [3, 4]. According to Rogers et al.[5], Rogers being a co–author of the work presented in [2], “the standard Naive Bayes was modified by considering only the effect of the presence of a feature and not its absence”. There are also a few more noticeable aspects of this proposed simplification: (a) the authors cleverly estimate directly – albeit heuristically – the a posteriori class probability for the present feature; (b) these authors (rather ingeniously) incorporate a Laplacian–correction into the estimated posterior class probability; and (c) the authors deem absent features not discriminating enough and therefore discard their contributions to the estimation of the posterior class. More than anything else it is this omission of the absent features from the Standard Naive Bayes (SNB) algorithm that makes Xia et al.’s proposed Naive Bayes Algorithm, termed Laplacian Corrected Modified Naive Bayes (LCMNB), (and its variants by different groups) computationally fast.

It is these three points, (a), (b) and (c), that we expound on in a mathematical setting to demonstrate under which conditions they hold – not only in an abstract sense, but also in the practical sense for a NB practitioner to make an informed decision as to when it is appropriate to employ SNB or LCMNB, in the cheminformatics context.

Methods

Naive Bayes

From Bayes’ theorem recall that [6]:

$$\frac{p({\omega }_i|\mathbf{\text{x}})}{p({\omega }_i)}=\frac{p(\mathbf{\text{x}}|{\omega }_i)}{p(\mathbf{\text{x}})}$$

(1)

where x = (x₁,x₂,...,x _L ) and ω _i denote the feature vectors and class labels, respectively; x _j and L being as described before, whereas i is just an index for the class labels. The terms p(ω _i |x), p(x|ω _i ), p(ω _i ), and p(x) refer to the posterior probability for ω _i given x, the descriptor vector distribution conditioned on class ω _i , the a priori probability of class ω _i occurring, and the descriptor vector density function, respectively – for more details, see ref. [3, 4, 6].

The left hand side of Eq. 1 can be expressed as follows [1, 7]

$$\frac{p({\omega }_i|\mathbf{\text{x}})}{p({\omega }_i)}=\frac{p({\omega }_i|x_1,x_2,\mathrm{...},x_L)}{p({\omega }_i)}$$

(2)

By virtue of Bayes’ theorem p(ω _i |x₁,x₂,...,x _L ) can be rewritten as

$$p({\omega }_i|x_1,x_2,\mathrm{...},x_L)=\frac{p(x_1,x_2,\mathrm{...},x_L|{\omega }_i)p({\omega }_i)}{p(x_1,x_2,\mathrm{...},x_L)}$$

(3)

which in turn allows us to rewrite Eq. 2 as

$$\frac{p({\omega }_i|\mathbf{\text{x}})}{p({\omega }_i)}=\frac{p({\omega }_i)p(x_1,x_2,\mathrm{...},x_L|{\omega }_i)}{p({\omega }_i)p(x_1,x_2,\mathrm{...},x_L)}=\frac{p(x_1,x_2,\mathrm{...},x_L|{\omega }_i)}{p(x_1,x_2,\mathrm{...},x_L)}$$

(4)

Making use of the chain rule of probability [1, 8], we can express p(x₁,x₂,...,x _L |ω _i ) as

$$\begin{array}{l}p(x_1,x_2,\mathrm{...},x_L|{\omega }_i)=p(x_1|{\omega }_i)p(x_2|{\omega }_i,x_1)\mathrm{.....}\\ p(x_L|{\omega }_i,x_1,x_2,\mathrm{...},x_{L-1})\end{array}$$

(5)

Plugging the right hand side of the equation above into Eq. 4 results in

$$\frac{p({\omega }_i|\mathbf{\text{x}})}{p({\omega }_i)}=\frac{p(x_1|{\omega }_i)p(x_2|{\omega }_i,x_1)\mathrm{.....p}(x_L|{\omega }_i,x_1,x_2,\mathrm{...},x_{L-1})}{p(x_1,x_2,\mathrm{...},x_L)}$$

(6)

In practice, it is extremely difficult to estimate p(ω _i |x) or p(x|ω _i ). This reality inevitably forces one to make concessions over the degree of accuracy the estimated p(ω _i |x) or p(x|ω _i ) can deliver. One widely employed scheme to obtain these probability distributions with compromised accuracy is to assume that individual descriptors x _j , j = 1,2,...,L, are independent conditional on ω _i . It is this naive assumption of independence among features to which the term “Naive” in “Naive Bayesian” refers.

Under this naive assumption, in Eq. 6, p(x₂|ω _i ) = p(x₂|ω _i ,x₁), p(x₃|ω _i ) = p(x₃|ω _i ,x₁,x₂),..., p(x _L |ω _i ) = p(x _L |ω _i ,x₁,x₂...,x_L−1). Thus, Eq. 6 modifies to

$$\frac{p({\omega }_i|\mathbf{\text{x}})}{p({\omega }_i)}=\frac{p(x_1|{\omega }_i)p(x_2|{\omega }_i)\mathrm{...}p(x_L|{\omega }_i)}{p(x_1,x_2,\mathrm{...},x_L)}$$

(7)

Multiplying top and bottom of Eq. 7 by $p^L({\omega }_i){\mathrm{\Pi }}_{j=1}^{L}p(x_j)$ yields

$$\begin{array}{ll}\frac{p({\omega }_i|\mathbf{\text{x}})}{p({\omega }_i)}& =\frac{p^L({\omega }_i)p(x_1|{\omega }_i)p(x_2|{\omega }_i)\mathrm{...}p(x_L|{\omega }_i){\mathrm{\Pi }}_{j=1}^{L}p(x_j)}{p^L({\omega }_i)p(x_1,x_2,\mathrm{...},x_L){\mathrm{\Pi }}_{j=1}^{L}p(x_j)}\end{array}$$

(8)

$$\begin{array}{l}=\frac{p^L({\omega }_i)p(x_1|{\omega }_i)p(x_2|{\omega }_i)\mathrm{...}p(x_L|{\omega }_i){\mathrm{\Pi }}_{j=1}^{L}p(x_j)}{{\mathrm{\Pi }}_{j=1}^{L}p(x_j)p^L({\omega }_i)p(x_1,x_2,\mathrm{...},x_L)}\end{array}$$

(9)

Then making use of the fact that $p({\omega }_i|x_1)=\frac{p({\omega }_i)p(x_1|{\omega }_i)}{p(x_1)}$, $p({\omega }_i|x_2)=\frac{p({\omega }_i)p(x_2|{\omega }_i)}{p(x_2)}$,..., $p({\omega }_i|x_L)=\frac{p({\omega }_i)p(x_L|{\omega }_i)}{p(x_1)}$, we can rewrite Eq. 9 as

$$\begin{array}{l}\frac{p({\omega }_i|\mathbf{\text{x}})}{p({\omega }_i)}=\frac{p({\omega }_i|x_1)p({\omega }_i|x_2)\mathrm{...}p({\omega }_i|x_L){\mathrm{\Pi }}_{j=1}^{L}p(x_j)}{p^L({\omega }_i)p(x_1,x_2,\mathrm{...},x_L)}\end{array}$$

(10)

or more compactly as

$$\frac{p({\omega }_i|\mathbf{\text{x}})}{p({\omega }_i)}=\frac{{\mathrm{\Pi }}_{j=1}^{L}p({\omega }_i|x_j)}{p^L({\omega }_i)}\times \frac{{\mathrm{\Pi }}_{j=1}^{L}p(x_j)}{p(x_1,x_2,\mathrm{....},x_L)}$$

(11)

Clearly $\frac{{\mathrm{\Pi }}_{j=1}^{L}p(x_j)}{p(x_1,x_2,\mathrm{....},x_L)}$ is common to all classes and therefore plays no role in classification. Thus, in practice (in the Naive Bayes context with which this work is concerned) one is required to estimate p(ω _i |x _j ) and p(ω _i ).

Since generative approaches can be informative and “simpler” than their discriminative counterparts [9], we make use of Bayes’ theorem again, i.e., $p({\omega }_i|x_j)=\frac{p({\omega }_i)p(x_j|{\omega }_i)}{p(x_j)}$ and then estimate p(ω _i |x _j ) through $\frac{p({\omega }_i)p(x_j|{\omega }_i)}{p(x_j)}$, where $p(x_j)=\sum _{i=1}^{C}p(x_j|{\omega }_i)p({\omega }_i)$ with C referring to the number of classes. p(ω _i ) denotes the a priori class probability, which is relatively easy to estimate. Thus, in our Bayesian context, the estimation of p(ω _j |x _j ) boils down in practice to estimating p(x _j |ω _i ).

Estimation of p(x _j |ω _i ), with x _j  = 1 and0

p(x _j |ω _i ) can be estimated using the given data and assuming a Beta distribution as an a priori distribution for p(x _j |ω _i ) [10]. (There are other possible prior distributions from which one can choose, but we select the Beta distribution for reasons that will transpire later). As described in Appedix A, a Beta a priori distribution Beta(α _i ,β _i ) for p(x _j |ω _i ) results in a p(x _j |ω _i ) estimator in the form [11]:

$$p(x_j=1|{\omega }_i)=\frac{N_{\mathit{\text{ij}}}+{\alpha }_i}{N_{{\omega }_i}+{\beta }_i+{\alpha }_i}$$

(12)

and of course

$$p(x_j=0|{\omega }_i)=1-\frac{N_{\mathit{\text{ij}}}+{\alpha }_i}{N_{{\omega }_i}+{\beta }_i+{\alpha }_i}$$

(13)

where $N_{{\omega }_i}$ and N _ij , respectively, denote the number compounds in class ω _i , and number of compounds in this class with descriptor x _j assuming value 1. β _i and α _i are Beta distribution hyper–parameters per class and the valid range of values that these hyper–parameter can assume are as defined in Appendix A. When α _i and β _i equal 1, α _i and β _i  + α _i in Eqs. 12–13 can be viewed as a “Laplacian correction”.

Results and discussion

Estimation of p(ω _i |x _j  = 1) and p(ω _i |x _j  = 0)

Estimation of p(ω _i |x _j  = 1): In Our Approach

Remark 1

Assume that we have N chemical compounds (and their activity labels) available for training, where $N_{{\omega }_i}$ of these compounds belong to class ω _i .

Remark 2

Assume that the class a priori distribution is taken as $p({\omega }_i)=\frac{N_{{\omega }_i}}{N}$, where $N_{{\omega }_i}>>{\alpha }_i+{\beta }_i$ (which is a valid assumption as found in any realistic large chemical dataset).

By virtue of Remark 1 and Eq. 12, the estimate of p(ω _i |x _j  = 1) becomes

$$p({\omega }_i|x_j=1)=\frac{p(x_j=1|{\omega }_i)p({\omega }_i)}{p(x_j=1)}=\frac{\frac{N_{\mathit{\text{ij}}}+{\alpha }_i}{N_{{\omega }_i}+{\alpha }_i+{\beta }_i}\times \frac{N_{{\omega }_i}}{N}}{\sum _{i=1}^C\frac{N_{\mathit{\text{ij}}}+{\alpha }_i}{N_{{\omega }_i}+{\alpha }_i+{\beta }_i}\times \frac{N_{{\omega }_i}}{N}}$$

(14)

(recall that $p(x_j)=\sum _{i=1}^{C}p(x_j|{\omega }_i)p({\omega }_i)$).

Because of Remark 2, Eq. 14 can be simplified to

$$p({\omega }_i|x_j=1)=\frac{N_{\mathit{\text{ij}}}+{\alpha }_i}{\sum _{i=1}^C{N}_{\mathit{\text{ij}}}+\sum _{i=1}^C{\alpha }_i}=\frac{N_{\mathit{\text{ij}}}+{\alpha }_i}{N_j^{+}+\sum _{i=1}^C{\alpha }_i}$$

(15)

where $N_j^{+}$ is the number of times x _j assumes the value 1.

Estimation of p(ω _i |x _j  = 1): In Xia et al.’s Formulation

In the approach of Xia et al., p(ω _i |x _j  = 1) is estimated as

$$p({\omega }_i|x_j=1)=\frac{N_{\mathit{\text{ij}}}+A_i}{N_j^{+}+K}$$

(16)

where K is as defined in Xia et al. and in their paper A _i is given as

$$A_i=p({\omega }_i)\times K,\mathit{\text{with}}K=\sum _{i=1}^C{A}_i\mathit{\text{as}}\sum _{i=1}^{C}p({\omega }_i)=1$$

Eq. 16 constitutes what Xia et al. term “the Laplacian–Corrected Modified Naive Bayes (LCMNB)” estimator for p(ω _i |x _j  = 1).

If α _i in Eq. 15 is set to A _i , Eq. 15 is exactly equivalent to Xia et al.’s estimator for p(ω _i |x _j  = 1) as can be seen in Eq. 16.

We note in passing that in Xia et al.’s case, C = 2 and $p({\omega }_2)=\frac{1}{K}$, which in their nomenclature denoted by p(Active) – that is, A₂ = 1 while A₁ = K − 1.

Initially we employed the Beta a priori distribution for the class conditional distribution to ascertain the equivalence of Eqs. 15 and 16. Fortunately, however, we have ended up with the general equations (Eqs. 14 – 15) that not only encapsulate the LCMNB scheme of Xia et al., but also subsume the other various variants of LCMNB, such as those discussed in Nidhi et al. and Nigsch et al.’s papers [3, 4].

At any rate, let us proceed to the nub of this work: Identifying the conditions under which the LCMNB algorithm holds with respect to the SNB algorithm. But first we need to describe the estimation of p(ω _i |x _j  = 0).

Estimation of p(ω _i |x _j  = 0): In Our Approach

In regard to the case of x _j  = 0, we make use of Remark 1, Remark 2 and Eq. 13, which yield an estimator for p(ω _i |x _j  = 0) as

$$p({\omega }_i|x_j=0)=\frac{N_{{\omega }_i}-(N_{\mathit{\text{ij}}}+{\alpha }_i)}{N-(N_j^{+}+\sum _{i=1}^C{\alpha }_i)}$$

(17)

Naive Bayes: scoring function from

For notational convenience let us denote $\frac{N_{\mathit{\text{ij}}}+{\alpha }_i}{N_j^{+}+\sum _{i=1}^C{\alpha }_i}$ in Eq. 15 and $\frac{N_{{\omega }_i}-(N_{\mathit{\text{ij}}}+{\alpha }_i)}{N-(N_j^{+}+\sum _{i=1}^C{\alpha }_i)}$ in Eq. 17 by ξ _ij and ν _ij , respectively.

Thus, p(ω _i |x _j  = 1) and p(ω _i |x _j  = 0) may be written more succinctly as $p({\omega }_i|x_j)={\xi }_{\mathit{\text{ij}}}^{x_j}{\nu }_{\mathit{\text{ij}}}^{(1-x_j)}$, which allows us to express Eq. 11 more compactly as

$$\begin{array}{ll}\frac{p({\omega }_i|\mathbf{\text{x}})}{p({\omega }_i)}& =\frac{{\mathrm{\Pi }}_{j}p({\omega }_i|x_j)}{p^L({\omega }_i)}\times \frac{{\mathrm{\Pi }}_{j}p(x_j)}{p(x_1,x_2,\mathrm{....},x_L)}\\ =\frac{{\mathrm{\Pi }}_j{\xi }_{\mathit{\text{ij}}}^{x_j}{\nu }_{\mathit{\text{ij}}}^{(1-x_j)}}{p^L({\omega }_i)}\times \frac{{\mathrm{\Pi }}_{j}p(x_j)}{p(x_1,x_2,\mathrm{....},x_L)}\end{array}$$

(18)

Now we come to the core of this work, under which conditions does the LCMNB algorithm hold with respect to the SNB algorithm? Before we answer this question, we deem it instructive and more insightful to map Eq. 18 monotonically to a discriminant function, a “scoring function” (so to speak).

To this end, taking the logarithm of Eq. 18 results in

$$\begin{array}{l}{S}_{{\omega }_i}(\mathbf{\text{x}})=\text{ln}\frac{p({\omega }_i|\mathbf{\text{x}})}{p({\omega }_i)}=\text{ln}\frac{{\mathrm{\Pi }}_j{\xi }_{\mathit{\text{ij}}}^{x_j}{\nu }_{\mathit{\text{ij}}}^{(1-x_j)}}{p^L({\omega }_i)}\times \frac{{\mathrm{\Pi }}_{j}p(x_j)}{p(x_1,x_2,\mathrm{...},x_L)}\end{array}$$

(19)

$$\begin{array}{l}=\sum _j{x}_j\text{ln}{\xi }_{\mathit{\text{ij}}}+\sum _j(1-x_j)\text{ln}{\nu }_{\mathit{\text{ij}}}-L\times \text{ln}p({\omega }_i)\\ +\sum _j\text{ln}p(x_j)-\text{ln}p(x_1,x_2,\mathrm{...},x_L)\end{array}$$

(20)

Self–evidently, the term $\left[\sum _j\text{ln}p(x_j)-\text{ln}p(x_1,x_2,\mathrm{...},x_L)\right]$ is common to all classes and therefore does not play any role in classifying a given new compound. In other words, for practical classification purposes we are only interested in class dependent terms, i.e.,

$$D_{{\omega }_i}(\mathbf{\text{x}})=\sum _j{x}_j\text{ln}{\xi }_{\mathit{\text{ij}}}-\text{ln}p({\omega }_i)+\sum _j(1-x_j)\text{ln}{\nu }_{\mathit{\text{ij}}}-(L-1)\times \text{ln}p({\omega }_i)$$

(21)

where $S_{{\omega }_i}(\mathbf{\text{x}})=D_{{\omega }_i}(\mathbf{\text{x}})+\left[\sum _j\text{ln}p(x_j)-\text{ln}p(x_1,x_2,\mathrm{...},x_L)\right]$

Conditions

In Xia et al.’s approach, the LCMNB algorithm, is none other than ${\sum }_j{x}_j\text{ln}{\xi }_{\mathit{\text{ij}}}-\text{ln}p({\omega }_i)$ in Eq. 21. This means that in Xia et al.’s scheme the contributions from the terms depending on x _j  = 0 for a given class, i.e.,

$$\sum _j(1-x_j)\text{ln}{\nu }_{\mathit{\text{ij}}}-(L-1)\times \text{ln}p({\omega }_i),\forall i,i=1,2,\mathrm{..},C$$

(22)

are discarded. To the best of our knowledge, neither in Xia et al. nor in any other paper on the LCMNB approach has it been demonstrated that (i) the contribution of Eq. 22 is zero, i.e.,

$$\sum _j(1-x_j)\text{ln}{\nu }_{\mathit{\text{ij}}}-(L-1)\times \text{ln}p({\omega }_i)=0,\forall i,i=1,2,\mathrm{..},C$$

(23)

equally, in these papers, it has not been shown that (ii)

$$\begin{array}{ll}|\sum _j{x}_j\text{ln}{\xi }_{\mathit{\text{ij}}}& -\text{ln}p({\omega }_i)|>>|\sum _j(1-x_j)\text{ln}{\nu }_{\mathit{\text{ij}}}-(L-1)\\ \times \text{ln}p({\omega }_i)|,\forall i,i=1,2,\mathrm{..},C\end{array}$$

(24)

nor has it been established that (iii)

$$\sum _j(1-x_j)\text{ln}{\nu }_{\mathit{\text{ij}}}-(L-1)\times \text{ln}p({\omega }_i)=\mathit{\text{constant}},\forall i,i=1,2,\mathrm{..},C$$

(25)

Thus unless one (or more) of the above – (i), (ii) and (iii) – is (are) met, the assumption on which the Modified Naive Bayesian algorithm is based is questionable and therefore its practitioners should pay attention to this discrepancy; clearly it is not justifiable to discard from the onset the contribution of $\sum _j(1-x_j)\text{ln}{\nu }_{\mathit{\text{ij}}}-(L-1)\times \text{ln}p({\omega }_i)$ simply because features x _j are absent, i.e. x _j  = 0.

For completeness, we consider also the case of the highly popular class prior distribution, $p({\omega }_i)=\frac{1}{C}$, i.e. p(ω₁) = p(ω₂) = ... = p(ω _C ). We hasten to add that this option was not included in the LCMNB scheme. At any rate, by simply repeating the arguments in the preceding sections, it is straightforward to show that one ends up with Eq. 21. In this scenario, though, L × lnp(ω _i ) is common to all classes and therefore does not play a role in classifying a new compound, i.e., $D_{{\omega }_i}(\mathbf{\text{x}})$ reduces to

$$D_{{\omega }_i}(\mathbf{\text{x}})=\sum _j{x}_j\text{ln}{\xi }_{\mathit{\text{ij}}}+\sum _j(1-x_j)\text{ln}{\nu }_{\mathit{\text{ij}}}$$

(26)

Conclusions

Starting from a standard Naive Bayes (SNB) algorithm, we have derived mathematically the relationship between Xia et al.’s ingenious, but heuristic algorithm, and the standard Naive Bayes approach. We also describe the conditions on which Xia et al.’s crucial assumption – contributions from absent feature can be discarded – holds. It is our hope that, with this new insight, cheminformaticians may now be able to efficiently use the Modified version of the standard Naive Bayes algorithm, as proposed by Xia et al., and subsequently by Nidhi et al. and Nigsch et al.

Appendix

Appendix A: Estimator of p(x _j |ω _i )

Here we give for completeness the proof that a priori Beta distribution leads to Eqs. 12 and 13 in the text.

For bookkeeping:

ω _i : class label indexed by i, i = 1,2,...,C.

C: Number of classes.

$N_{{\omega }_i}$: Number of samples in class ω _i .

N _ij : Number of samples in class ω _i with feature x _j  = 1, j = 1,2,...,L.

L: Number of features.

We state from the onset, in the following derivation we follow closely the descriptions given in ref. [10]. We also note, for clarity’s sake, in the following analyses we abuse notation and use x _jk for both the random variable and its realization.

In this work, x ∈ {0,1}^L, i.e. x _j  ∈ {0,1} and suppose that x _j are independent Bernoulli random variables (and this is in fact the assumption made in the Naive Bayesian approach). Thus, in the Naive Bayesian setting p(x|ω _i ) can be given as

$$p(\mathbf{\text{x}}|{\omega }_i)={\mathrm{\Pi }}_{j=1}^L\mathit{\text{Ber}}(x_j|{\mu }_{\mathit{\text{ij}}})={\mathrm{\Pi }}_{j=1}^L{\mu }_{\mathit{\text{ij}}}^{x_j}{(1-{\mu }_{\mathit{\text{ij}}})}^{1-x_j}$$

(27)

where μ _ij is an estimate for the conditional probability that feature j occurs in class ω _i , and is what we are trying to estimate given a set of compounds assumed to belong to class ω _i . (In our context, μ _ij is an estimator for p(x _j |ω _i ), where p(x _j |ω _i )is as defined in the text.)

To estimate μ _ij in a Bayesian framework, we first view μ _ij as a random variable, then choose an “appropriate” prior and likelihood for the random variable μ _ij .

Let us suppose that our a priori knowledge about the random variable μ _ij indicates that μ _ij is described by a Beta distribution, i.e.,

$$\begin{array}{ll}\pi ({\mu }_{\mathit{\text{ij}}})=& \frac{1}{B({\alpha }_i,{\beta }_i)}{\mu }_{\mathit{\text{ij}}}^{{\alpha }_i-1}{(1-{\mu }_{\mathit{\text{ij}}})}^{{\beta }_i-1},0\le {\mu }_{\mathit{\text{ij}}}\le 1,{\alpha }_i,\\ {\beta }_i>0,i=1,2,\mathrm{...}C\end{array}$$

(28)

where B(α _i ,β _i ) ensures that the Beta distribution is normalised

Using the Bayes’ theorem, then the posterior probability for μ _ij on the training data can be given by

$$\begin{array}{l}\pi ({\mu }_{\mathit{\text{ij}}}|x_{j1},x_{j2},\mathrm{...},x_{{\mathit{\text{jN}}}_{{\omega }_i}})=\frac{f(x_{j1},x_{j2},\mathrm{...},x_{{\mathit{\text{jN}}}_{{\omega }_i}}|{\mu }_{\mathit{\text{ij}}})\pi ({\mu }_{\mathit{\text{ij}}})}{{\int }_0^{1}f(x_{j1},x_{j2},\mathrm{...},x_{{\mathit{\text{jN}}}_{{\omega }_i}}|{\mu }_{\mathit{\text{ij}}})\pi ({\mu }_{\mathit{\text{ij}}})d{\mu }_{\mathit{\text{ij}}}}\end{array}$$

(29)

where $f(x_{j1},x_{j2},\mathrm{...},x_{{\mathit{\text{jN}}}_{{\omega }_i}}|{\mu }_{\mathit{\text{ij}}})$refers to the likelihood, and x_j1,x_j2,... and $x_{{\mathit{\text{jN}}}_{{\omega }_i}}$ denote the j^th feature of the $N_{{\omega }_i}$ samples/compounds from class ω _i . As the samples are assumed independent, then $f(x_{j1},x_{j2},\mathrm{...},x_{{\mathit{\text{jN}}}_{{\omega }_i}}|{\mu }_{\mathit{\text{ij}}})$ becomes ${\mathrm{\Pi }}_{k=1}^{N_{{\omega }_i}}f(x_{\mathit{\text{jk}}}|{\mu }_{\mathit{\text{ij}}})={\mathrm{\Pi }}_{k=1}^{N_{{\omega }_i}}{\mu }_{\mathit{\text{ij}}}^{x_{\mathit{\text{jk}}}}{(1-{\mu }_{\mathit{\text{ij}}})}^{1-x_{\mathit{\text{jk}}}}$, i.e.

$${\mathrm{\Pi }}_{k=1}^{N_{{\omega }_i}}f(x_{\mathit{\text{jk}}}|{\mu }_{\mathit{\text{ij}}})={\mu }_{\mathit{\text{ij}}}^{{\sum }_{k=1}^m{x}_{\mathit{\text{jk}}}}{(1-{\mu }_{\mathit{\text{ij}}})}^{N_{{\omega }_i}-{\sum }_{k=1}^{N_{{\omega }_i}}{x}_{\mathit{\text{jk}}}}$$

(30)

Thus, the posterior π(μ _ij |x_j1,x_j2,...,x _jM ) in Eq. 29 modifies to

$$\begin{array}{l}\pi ({\mu }_{\mathit{\text{ij}}}|x_{j1},x_{j2},\mathrm{...},x_{{\mathit{\text{jN}}}_{{\omega }_i}})\\ =\frac{{\mu }_{\mathit{\text{ij}}}^{{\sum }_{k=1}^{N_{{\omega }_i}}{x}_{\mathit{\text{jk}}}}{(1-{\mu }_{\mathit{\text{ij}}})}^{N_{{\omega }_i}-{\sum }_{k=1}^{N_{{\omega }_i}}{x}_{\mathit{\text{jk}}}}\pi ({\mu }_{\mathit{\text{ij}}})}{{\int }_0^1{\mu }_{\mathit{\text{ij}}}^{{\sum }_{k=1}^{N_{{\omega }_i}}{x}_{\mathit{\text{jk}}}}{(1-{\mu }_{\mathit{\text{ij}}})}^{N_{{\omega }_i}-{\sum }_{k=1}^{N_{{\omega }_i}}{x}_{\mathit{\text{jk}}}}\pi ({\mu }_{\mathit{\text{ij}}})d{\mu }_{\mathit{\text{ij}}}}\end{array}$$

(31)

i.e.,

$$\begin{array}{l}\pi ({\mu }_{\mathit{\text{ij}}}|x_{j1},x_{j2},\mathrm{...},x_{{\mathit{\text{jN}}}_{{\omega }_i}})\propto {\mu }_{\mathit{\text{ij}}}^{{\sum }_{k=1}^{N_{{\omega }_i}}{x}_{\mathit{\text{jk}}}}{(1-{\mu }_{\mathit{\text{ij}}})}^{N_{{\omega }_i}-{\sum }_{k=1}^{N_{{\omega }_i}}{x}_{\mathit{\text{jk}}}}\pi ({\mu }_{\mathit{\text{ij}}})\end{array}$$

(32)

$$\begin{array}{l}={\mu }_{\mathit{\text{ij}}}^{{\sum }_{k=1}^{N_{{\omega }_i}}{x}_{\mathit{\text{jk}}}}{(1-{\mu }_{\mathit{\text{ij}}})}^{N_{{\omega }_i}-{\sum }_{k=1}^{N_{{\omega }_i}}{x}_{\mathit{\text{jk}}}}\\ \times {\mu }_{\mathit{\text{ij}}}^{{\alpha }_i-1}{(1-{\mu }_{\mathit{\text{ij}}})}^{{\beta }_i-1}\end{array}$$

(33)

$$\begin{array}{l}={\mu }_{\mathit{\text{ij}}}^{N_{\mathit{\text{ij}}}+{\alpha }_i-1}{(1-{\mu }_{\mathit{\text{ij}}})}^{N_{{\omega }_i}-N_{\mathit{\text{ij}}}+{\beta }_i-1}\end{array}$$

(34)

Clearly, in Eq. 34, the posterior density for μ _ij given the samples $x_{j1},x_{j2},\mathrm{...},x_{{\mathit{\text{jN}}}_{{\omega }_i}}$ has the same form as the prior for μ _ij [11], i.e.,

$$\begin{array}{l}\pi ({\mu }_{\mathit{\text{ij}}}|x_{j1},x_{j2},\mathrm{...},x_{{\mathit{\text{jN}}}_{{\omega }_i}})\\ =\frac{1}{B(N_{\mathit{\text{ij}}}+{\alpha }_i,N_{{\omega }_i}-N_{\mathit{\text{ij}}}+{\beta }_i)}{\mu }_{\mathit{\text{ij}}}^{N_{\mathit{\text{ij}}}+{\alpha }_i-1}{(1-{\mu }_{\mathit{\text{ij}}})}^{N_{{\omega }_i}-N_{\mathit{\text{ij}}}+{\beta }_i-1}\end{array}$$

(35)

which is none other than another Beta distribution. This means that the Bayes estimator of μ _ij , which is the estimate we are interested in, is the mean of the posterior distribution obtained [11]:

$$E[{\mu }_{\mathit{\text{ij}}}|x_{j1},x_{j2},\mathrm{...},x_{{\mathit{\text{jN}}}_{{\omega }_i}}]=\frac{N_{\mathit{\text{ij}}}+{\alpha }_i}{N_{{\omega }_i}+{\alpha }_i+{\beta }_i}$$

(36)

In other words,

$$p(x_j|{\omega }_i)=\frac{N_{\mathit{\text{ij}}}+{\alpha }_i}{N_{{\omega }_i}+{\alpha }_i+{\beta }_i}$$

(37)

QED.

An accessible description of the derivation of Eq. 37 can be found in ref. [10].