# Estimation of the Conditional Probability Using a Stochastic Gradient Process

Authors: Ali Labriji; Abdelkrim Bennar; Mostafa Rachik
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The use of conditional probabilities has gained in popularity in various fields such as medicine, finance, and imaging processing. This has occurred especially with the availability of large datasets that allow us to extract the full potential of the available estimation algorithms. Nevertheless, such a large volume of data is often accompanied by a significant need for computational capacity as well as a consequent compilation time. In this article, we propose a low-cost estimation method: we first demonstrate analytically the convergence of our method to the desired probability and then we perform a simulation to support our point.


---

## Body

## 1. Introduction

The likelihood that an eventB will occur knowing that event A has already occurred is called the conditional probability, denoted by PB|A or PAB. For example, if a card is randomly drawn from a deck, there is a one in four chance of getting a heart suit, but if a red reflection is seen on the table, there is now a one in two chance of getting it. If events A and B have nonzero probabilities, then Bayes theorem states that PB|A=PA∩B/PA. That was for the scientific part, but in daily life also conditional probability is useful in various fields and is even gaining more and more interest. For example, banks estimate the probability of default of a borrower or bond issuer using conditional probability estimation methods based on Basel II regulations (see [1] for more information). The estimation of this probability is crucial since it allows the banks to compute the expected losses and therefore to cover the consequences. Another area where the estimation of conditional probabilities is important is marketing, where it is used to estimate the interest of a customer in a given product or service. Therefore, they are able to focus on the most attractive population in order to optimize the marketing costs [2]. The estimation of this probability is also frequently used in the field of medicine, as doctors need to estimate the likelihood of a patient being affected by a given disease based on the symptoms the patient presents [3] and many more areas, such as drug discovery, computer vision, speech recognition, handwriting recognition, biometric identification, document classification, Internet search engines, pattern recognition, and recommender system [4–11].In practice, we can divide conditional probability estimation methods into two categories, linear and nonlinear classifiers. The linear classifiers can be split into two subcategories, the generative and discriminative models [12, 13], and the most commonly used are(i)
Fisher’s linear discriminant(ii)
Logistic regression(iii)
Naive Bayes classifierNonlinear classifiers can be grouped into the following groups of methods:(i)
Linear classifier with transformed data such as a discretization of continuous variables(ii)
Support vector machines(iii)
Quadratic classifiers(iv)
K-nearest neighbor(v)
Decision trees(vi)
Neural networks(vii)
Learning vector quantizationTo learn more about these different algorithms, see [14–20].Let us consider an observable random binary variableU and a random variable V. We define U such that(1)U=1,if the studied event occured,0,if not.We are willing to estimate the vectorθ such that the conditional probability PU=1|V is written in the form:(2)PU=1|V=11+exp−θ′V.We are looking for a simple method of estimating the parameterθ that will be less demanding in terms of computational capacity. This is useful especially in the Big Data era, where the datasets can be massive and any common iterative estimation can take a lot of time. To do this, we use the stochastic approximation, which has been introduced by Herbert Robbins and Sutton Monro in 1951 [21]. The goal is to find the unique root θ∗ of a function Mθ=α, while Mθ cannot be directly observed. Yet, we assume that we can observe a variable Yθ such that EYθ=Mθ. According to [21], there exists a sequence an that satisfies(3)∑n=1∞an=∞,∑n=1∞an2<∞,such as the process θn defined by(4)θn+1=θn−anMθn−α,converges to the unique root of Mθ=α. In our case, we start from the work of Bennar et al. [22] who established the conditions for almost sure convergence, as well as the quadratic mean convergence of a stochastic gradient process θn to the parameter θ that allows us to estimate EU|V. Here, we are interested in the case of binary random variables, where EU|V is equivalent to PU=1|V, as we can see in the following:(5)EU|V=∑i=12uiPU=ui|V=PU=1|V.We also chose these results as the basis of our work since the stochastic gradient process performs a sampling at each iteration in order to achieve the estimates without relying on all the available data.In this article, we first present the convergence results elaborated by Bennar et al., then we show that these results are also valid in the framework of estimating the conditional probability. We also present a simulation to highlight the obtained results, and finally, we conclude our work by addressing development perspectives.


## 2. Preliminaries

Let us consider an observable random variableU and a random variable V, both have values in ℝk of law μ. We try to estimate the parameter θ in ℝp such that ϕV,θ approaches EU|V in the least squares sense. It should also be noted that the estimation of the parameters of a logistic regression in the sense of least squares is already achieved through the iterative weighted least squares method [23] which, unlike our purpose, is heavy and employs huge computing capacities in the case of large dataset.Letf be the real positive function defined in ℝp by(6)fθ=EEU|V−ϕV,θ2,we are looking for the value of θ that minimizes the function f.Let us define the real positive functiong in ℝp by(7)gθ=EU−ϕV,θ2.We have(8)gθ=fθ+EU−EU|V2,thus the problem reduces to looking for θ that minimizes the function g. We have(9)∇θgθ=2E∇θϕV,θϕV,θ−U.To estimateθ in a sequential way, we use a stochastic gradient algorithm. We consider a random θn in ℝp defined by(10)θn+1=θn−an∇θϕVn,θnϕVn,θn−Un,with(i)
an is a sequence of positive real numbers(ii)
U1,V1,U2,V2,…,Un,Vn is a sample of independent random variable couples with the same probability law that U,V(iii)
ϕ.,. is a real known measurable function in ℝk×ℝpIn the following, the abbreviationa.s means almost sure convergence and q.m means quadratic mean convergence.


### 2.1. Almost Sure Convergence

Bennar et al. have considered the following assumptions:H1an>0,∑n=1∞an2<∞,H1′an>0,∑n=1∞an=∞,∑n=1∞an2<∞,H2: there exist a and b such that for all θ=θ1,θ2,…,θp′∈ℝp,(11)Var∂ϕV,θ∂θiϕV,θ−U<agθ+b,for alli=1,2,…,p,H3: there exists K>0 such that for all θ=θ1,θ2,…,θp′∈ℝp,(12)∂2gθ∂θi∂θj<K,for alli=1,2,…,p,H4θ∗ is a local minimum of g:(13)∃α>0:θ≠θ∗,θ−θ∗<α⇒gθ∗<gθ.H5θ∗ is the unique stationary point of g:(14)∀θ∈ℝp,θ≠θ∗⇔∇θgθ≠0.Lemma 1.
Under the assumptionsH1′,H2,H3,H4,H5, we have(15)θn⟶θ∗a.s orθn⟶+∞a.s.Proof.
See [22].


### 2.2. Quadratic Mean Convergence

Bennar et al. have considered the following assumptions:H6ϕV,θ and ∇θϕV,θ are uniformly bounded in V and θ.H7: there exist two real positive functions h and h′ defined in ℝp such that∀θ,θ′∈ℝp,∀V∈ℝp,(16)ϕV,θ−ϕV,θ′≤hVθ−θ′,∇θϕV,θ−∇θ′ϕV,θ′≤h′Vθ−θ′,EhV<∞,Eh′V<∞.H8U is a real random bounded variable.Lemma 2.
Under the assumptionsH1′,H3,H6,H7,H8, we have(17)∇θgθn⟶0a.s and∇θgθn⟶0q.m.Proof.
See [22].


## 2.1. Almost Sure Convergence

Bennar et al. have considered the following assumptions:H1an>0,∑n=1∞an2<∞,H1′an>0,∑n=1∞an=∞,∑n=1∞an2<∞,H2: there exist a and b such that for all θ=θ1,θ2,…,θp′∈ℝp,(11)Var∂ϕV,θ∂θiϕV,θ−U<agθ+b,for alli=1,2,…,p,H3: there exists K>0 such that for all θ=θ1,θ2,…,θp′∈ℝp,(12)∂2gθ∂θi∂θj<K,for alli=1,2,…,p,H4θ∗ is a local minimum of g:(13)∃α>0:θ≠θ∗,θ−θ∗<α⇒gθ∗<gθ.H5θ∗ is the unique stationary point of g:(14)∀θ∈ℝp,θ≠θ∗⇔∇θgθ≠0.Lemma 1.
Under the assumptionsH1′,H2,H3,H4,H5, we have(15)θn⟶θ∗a.s orθn⟶+∞a.s.Proof.
See [22].


## 2.2. Quadratic Mean Convergence

Bennar et al. have considered the following assumptions:H6ϕV,θ and ∇θϕV,θ are uniformly bounded in V and θ.H7: there exist two real positive functions h and h′ defined in ℝp such that∀θ,θ′∈ℝp,∀V∈ℝp,(16)ϕV,θ−ϕV,θ′≤hVθ−θ′,∇θϕV,θ−∇θ′ϕV,θ′≤h′Vθ−θ′,EhV<∞,Eh′V<∞.H8U is a real random bounded variable.Lemma 2.
Under the assumptionsH1′,H3,H6,H7,H8, we have(17)∇θgθn⟶0a.s and∇θgθn⟶0q.m.Proof.
See [22].


## 3. Application

### 3.1. Proof of Process Convergence

Let us assumeρ1,ρ2,…,ρp be p functions of q measurable real variables. We note(18)ρ=ρ1,ρ2,…,ρp′.In order to estimate the value ofθ that minimizes EEU|V−1/1+exp−ρV′θ2, we consider the following stochastic approximation process θn in ℝp defined by(19)θn+1=θn−anρVnexp−ρVn′θn1+exp−ρVn′θn211+exp−ρVn′θn−Un,with(20)ρVnexp−ρVn′θn1+exp−ρVn′θn2=ρ1V1,nexp−ρVn′θn1+exp−ρVn′θn2⋮ρpVp,nexp−ρVn′θn1+exp−ρVn′θn2,where U1,V1,U2,V2,…,Un,Vn is a sample of U,V formed of independent random variable and distributed identically.We assume the following assertions:H9ρ1V1,ρ2V2,…,ρpVp are observed in a finite wayH10θ1 is a random variable such that Eθ12<∞Theorem 3.
Under the assumptionsH1′,H9,H10, we have(21)∇θgθn⟶0a.sand∇θgθn⟶0q.m.Proof.
Letϕ be the real function of ℝp×ℝp defined by(22)ϕV,θ=11+exp−ρV′θ=11+exp−∑j=1pθjρjV.
Let us prove that the assumption 3 is true.
We have(23)gθ=EU−11+exp−ρV′θ2.
Fori=1,2,…,p, we have(24)∂gθ∂θi=−2EρiViexp−ρV′θ1+exp−ρV′θ2U−11+exp−ρV′θ,=−2EρiVi2+expρV′θ+exp−ρV′θU−11+exp−ρV′θ.
Thus, fori,j=1,2,…,p, we have(25)∂2gθ∂θi∂θj=2EρiViρjVjexpρV′θ−exp−ρV′θ2+expρV′θ+exp−ρV′θ2U−11+exp−ρV′θ+2EρiVi2+expρV′θ+exp−ρV′θρjVj2+expρV′θ+exp−ρV′θ∂2gθ∂θi∂θj≤2EρiViρjVjU−11+exp−ρV′θ+2EρiViρjVj12+expρV′θ+exp−ρV′θ,as the ρ1V1,ρ2V2,…,ρpVp are observed in a finite way, and(26)0<11+exp−ρV′θ<1,0<12+expρV′θ+exp−ρV′θ<1.
Then, there existsK>0 such that for all θ=θ1,θ2,…,θp′∈ℝp,(27)∂2gθ∂θi∂θj<K,for alli=1,2,…,p.
Let us prove that the assumption 6 is true.
We have(28)ϕV,θ=11+exp−ρV′θ,∇θϕV,θ=ρV2+expρV′θ+exp−ρV′θ,with ρV/2+expρV′θ+exp−ρV′θ=ρ1V1/2+expρV′θ+exp−ρV′θ⋮ρpVp/2+expρV′θ+exp−ρV′θ;
then,ϕV,θ<1 and ∇θϕV,θ<ρV, and since ρ1V1,ρ2V2,…,ρpVp are observed in a finite way, then there exists K2>0 such that for all θ=θ1,θ2,…,θp′∈ℝp and V=V1,V2,…,Vp′∈ℝp, ∇θϕV,θ<K2. Then, ϕV,θ and ∇θϕV,θ are uniformly bounded in V and θ.
Let us prove that the assumption 7 is true. To do this, we use the following result.Lemma 4 (mean value inequalities).
LetE and F be two real normed vector spaces, U an open of E, and f:U⟶F a differentiable application. For any segment a,b included in U, we have(29)fb−faF≤supx∈a,bf′xb−aE,where, for any point x of U, f′x is the operator norm of the differential of f at point x.Proof.
See [24], p. 31.
Then, there exist two real positive functionsh and h′ defined in ℝp such that
∀θ,θ′∈ℝp,∀V∈ℝp,(30)ϕV,θ−ϕV,θ′≤hVθ−θ′,∇θϕV,θ−∇θ′ϕV,θ′≤h′Vθ−θ′.
Let us prove thatEhV<∞, and Eh′V<∞.
We have already seen that∇θϕV,θ≤ρV and since
ρ1V1,ρ2V2,…,ρpVp are observed in a finite way, then EhV<∞.
Furthermore, we have that∂2ϕV,θ/∂θi∂θj=−ρiViρjVjexpρV′θ−exp−ρV′θ/2+expρV′θ+exp−ρV′θ2, then ∂2ϕV,θ/∂θi∂θj≤ρiViρjVj, and since ρ1V1,ρ2V2,…,ρpVp are observed in a finite way, then Eh′V<∞.
Moreover, sinceU is a binary random variable, then assumption 8 is true.
Then, under assumptionsH1′,H9,H10, we have(31)∇θgθn⟶0a.sand∇θgθn⟶0q.m.


### 3.2. Simulation

In order to illustrate our work, we perform a simulation in which we estimate the different parameters of a logistic regression. Our simulations are performed using the programming language “R.” We simulate10000 observations of the random variable V\leads toN3,10, and we define U such that(32)U=1,ifV+ϵ>0,0,if not,with ε\leads toN0,3, to avoid having a perfectly fitted model. Then, we fitted a classical logistic regression with the Fisher scoring algorithm, which converged in 12 iterations. We define the accuracy rate as the number of correctly classified observations over the total number of our observations, and the classic model has an accuracy of 90.34%. Table 1 shows all the remaining outputs of the model.Table 1
Fisher scoring algorithm outputs.
Dependent variableUθ0.567∗∗∗(0.013)Constant0.012(0.040)ObservationsObservations10,000Log likelihood−2,091.211Akaike Inf. Crit.4,186.422Note:∗p<0.1; ∗∗p<0.05; ∗∗∗p<0.01.Regarding the proposed process, we initiate it with the following randomly chosen values,Intercept=−3,θ=−3, and we choose an=1+exp−ρV′θ/n; as ρV and θ are finite, we can see that assumption H1′ is verified, and we also randomly draw a sample of one observation to perform our calculations at each iteration. Finally, we have set an accuracy of 10−12. Following simulations, we obtain the results as follows.We can see through Figures1 and 2, as well as Figure 3, that the process converged in 10 iterations. Therefore, we only needed 10 samples of one observation to obtain a robust estimation of the coefficients. Moreover, we can see in Figure 3 as well as in the summary of the process, in Table 2, that the latter records a prediction accuracy on the set of simulated observations of 89%, hence a loss of 1% in accuracy, but, in return, we gained greatly in terms of computing capacity.Figure 1
Intercept estimation process.Figure 2
θ estimation process.Figure 3
Accuracy of forecasts during iterations.Table 2
Summary of the iterations.
IterationAccuracyθIntercept10.097 9−3.000 000−3.000 00020.099 1−3.166 397−2.827 98130.883 3−3.166 3971.467 52740.883 3−3.166 3961.467 53450.883 3−3.166 3961.467 53460.883 3−3.166 3951.467 53870.887 4−3.039 2161.547 54480.890 7−2.987 5311.648 30090.890 7−2.987 5311.648 300100.890 7−2.987 5311.648 300


## 3.1. Proof of Process Convergence

Let us assumeρ1,ρ2,…,ρp be p functions of q measurable real variables. We note(18)ρ=ρ1,ρ2,…,ρp′.In order to estimate the value ofθ that minimizes EEU|V−1/1+exp−ρV′θ2, we consider the following stochastic approximation process θn in ℝp defined by(19)θn+1=θn−anρVnexp−ρVn′θn1+exp−ρVn′θn211+exp−ρVn′θn−Un,with(20)ρVnexp−ρVn′θn1+exp−ρVn′θn2=ρ1V1,nexp−ρVn′θn1+exp−ρVn′θn2⋮ρpVp,nexp−ρVn′θn1+exp−ρVn′θn2,where U1,V1,U2,V2,…,Un,Vn is a sample of U,V formed of independent random variable and distributed identically.We assume the following assertions:H9ρ1V1,ρ2V2,…,ρpVp are observed in a finite wayH10θ1 is a random variable such that Eθ12<∞Theorem 3.
Under the assumptionsH1′,H9,H10, we have(21)∇θgθn⟶0a.sand∇θgθn⟶0q.m.Proof.
Letϕ be the real function of ℝp×ℝp defined by(22)ϕV,θ=11+exp−ρV′θ=11+exp−∑j=1pθjρjV.
Let us prove that the assumption 3 is true.
We have(23)gθ=EU−11+exp−ρV′θ2.
Fori=1,2,…,p, we have(24)∂gθ∂θi=−2EρiViexp−ρV′θ1+exp−ρV′θ2U−11+exp−ρV′θ,=−2EρiVi2+expρV′θ+exp−ρV′θU−11+exp−ρV′θ.
Thus, fori,j=1,2,…,p, we have(25)∂2gθ∂θi∂θj=2EρiViρjVjexpρV′θ−exp−ρV′θ2+expρV′θ+exp−ρV′θ2U−11+exp−ρV′θ+2EρiVi2+expρV′θ+exp−ρV′θρjVj2+expρV′θ+exp−ρV′θ∂2gθ∂θi∂θj≤2EρiViρjVjU−11+exp−ρV′θ+2EρiViρjVj12+expρV′θ+exp−ρV′θ,as the ρ1V1,ρ2V2,…,ρpVp are observed in a finite way, and(26)0<11+exp−ρV′θ<1,0<12+expρV′θ+exp−ρV′θ<1.
Then, there existsK>0 such that for all θ=θ1,θ2,…,θp′∈ℝp,(27)∂2gθ∂θi∂θj<K,for alli=1,2,…,p.
Let us prove that the assumption 6 is true.
We have(28)ϕV,θ=11+exp−ρV′θ,∇θϕV,θ=ρV2+expρV′θ+exp−ρV′θ,with ρV/2+expρV′θ+exp−ρV′θ=ρ1V1/2+expρV′θ+exp−ρV′θ⋮ρpVp/2+expρV′θ+exp−ρV′θ;
then,ϕV,θ<1 and ∇θϕV,θ<ρV, and since ρ1V1,ρ2V2,…,ρpVp are observed in a finite way, then there exists K2>0 such that for all θ=θ1,θ2,…,θp′∈ℝp and V=V1,V2,…,Vp′∈ℝp, ∇θϕV,θ<K2. Then, ϕV,θ and ∇θϕV,θ are uniformly bounded in V and θ.
Let us prove that the assumption 7 is true. To do this, we use the following result.Lemma 4 (mean value inequalities).
LetE and F be two real normed vector spaces, U an open of E, and f:U⟶F a differentiable application. For any segment a,b included in U, we have(29)fb−faF≤supx∈a,bf′xb−aE,where, for any point x of U, f′x is the operator norm of the differential of f at point x.Proof.
See [24], p. 31.
Then, there exist two real positive functionsh and h′ defined in ℝp such that
∀θ,θ′∈ℝp,∀V∈ℝp,(30)ϕV,θ−ϕV,θ′≤hVθ−θ′,∇θϕV,θ−∇θ′ϕV,θ′≤h′Vθ−θ′.
Let us prove thatEhV<∞, and Eh′V<∞.
We have already seen that∇θϕV,θ≤ρV and since
ρ1V1,ρ2V2,…,ρpVp are observed in a finite way, then EhV<∞.
Furthermore, we have that∂2ϕV,θ/∂θi∂θj=−ρiViρjVjexpρV′θ−exp−ρV′θ/2+expρV′θ+exp−ρV′θ2, then ∂2ϕV,θ/∂θi∂θj≤ρiViρjVj, and since ρ1V1,ρ2V2,…,ρpVp are observed in a finite way, then Eh′V<∞.
Moreover, sinceU is a binary random variable, then assumption 8 is true.
Then, under assumptionsH1′,H9,H10, we have(31)∇θgθn⟶0a.sand∇θgθn⟶0q.m.


## 3.2. Simulation

In order to illustrate our work, we perform a simulation in which we estimate the different parameters of a logistic regression. Our simulations are performed using the programming language “R.” We simulate10000 observations of the random variable V\leads toN3,10, and we define U such that(32)U=1,ifV+ϵ>0,0,if not,with ε\leads toN0,3, to avoid having a perfectly fitted model. Then, we fitted a classical logistic regression with the Fisher scoring algorithm, which converged in 12 iterations. We define the accuracy rate as the number of correctly classified observations over the total number of our observations, and the classic model has an accuracy of 90.34%. Table 1 shows all the remaining outputs of the model.Table 1
Fisher scoring algorithm outputs.
Dependent variableUθ0.567∗∗∗(0.013)Constant0.012(0.040)ObservationsObservations10,000Log likelihood−2,091.211Akaike Inf. Crit.4,186.422Note:∗p<0.1; ∗∗p<0.05; ∗∗∗p<0.01.Regarding the proposed process, we initiate it with the following randomly chosen values,Intercept=−3,θ=−3, and we choose an=1+exp−ρV′θ/n; as ρV and θ are finite, we can see that assumption H1′ is verified, and we also randomly draw a sample of one observation to perform our calculations at each iteration. Finally, we have set an accuracy of 10−12. Following simulations, we obtain the results as follows.We can see through Figures1 and 2, as well as Figure 3, that the process converged in 10 iterations. Therefore, we only needed 10 samples of one observation to obtain a robust estimation of the coefficients. Moreover, we can see in Figure 3 as well as in the summary of the process, in Table 2, that the latter records a prediction accuracy on the set of simulated observations of 89%, hence a loss of 1% in accuracy, but, in return, we gained greatly in terms of computing capacity.Figure 1
Intercept estimation process.Figure 2
θ estimation process.Figure 3
Accuracy of forecasts during iterations.Table 2
Summary of the iterations.
IterationAccuracyθIntercept10.097 9−3.000 000−3.000 00020.099 1−3.166 397−2.827 98130.883 3−3.166 3971.467 52740.883 3−3.166 3961.467 53450.883 3−3.166 3961.467 53460.883 3−3.166 3951.467 53870.887 4−3.039 2161.547 54480.890 7−2.987 5311.648 30090.890 7−2.987 5311.648 300100.890 7−2.987 5311.648 300


## 4. Conclusion

In this work, we have demonstrated the convergence of the process studied towards the values that minimize the functiongθ, and following our simulations, we can see that this theoretical result is also valid on the empirical level. Nevertheless, this simulation required that we arbitrarily set a starting point, which leads to a possible slow convergence of the process in case the initial point is far from the targeted value. Moreover, the speed of convergence is also greatly affected by the choice of the an. Thus, a possible improvement would be to find the optimal sequence an that provides the fastest convergence.



---

*Source: 7660113-2021-12-06.xml*