# $\frac{P(x_1 \mid y, s = 1) \dots P(x_n \mid y, s = 1) P(y \mid s = 1)}{P(x \mid s = 1)}$ indicates that naive Bayes learners are global learners?

I am currently studying the paper Learning and Evaluating Classifiers under Sample Selection Bias by Bianca Zadrozny. In section 3. Learning under sample selection bias, the author says the following:

We can separate classifier learners into two categories:

• local: the output of the learner depends asymptotically only on $$P(y \mid x)$$
• global: the output of the learner depends asymptotically both on $$P(x)$$ and on $$P(y \mid x)$$.

The term "asymptotically" refers to the behavior of the learner as the number of training examples grows. The names "local" and "global" were chosen because $$P(x)$$ is a global distribution over the entire input space, while $$P(y \mid x)$$ refers to many local distributions, one for each value of $$x$$. Local learners are not affected by sample selection bias because, by definition $$P(y \mid x, s = 1) = P(y \mid x)$$ while global learners are affected because the bias changes $$P(x)$$.

Then, in section 3.1.1. Naive Bayes, the author says the following:

In practical Bayesian learning, we often make the assumption that the features are independent given the label $$y$$, that is, we assume that $$P(x_1, x_2, \dots, x_n \mid y) = P(x_1 \mid y) P(x_2 \mid y) \dots P(x_n \mid y).$$ This is the so-called naive Bayes assumption. With naive Bayes, unfortunately, the estimates of $$P(y \mid x)$$ obtained from the biased sample are incorrect. The posterior probability $$P(y \mid x)$$ is estimated as $$\dfrac{P(x_1 \mid y, s = 1) \dots P(x_n \mid y, s = 1) P(y \mid s = 1)}{P(x \mid s = 1)} ,$$ which is different (even asymptotically) from the estimate of $$P(y \mid x)$$ obtained with naive Bayes without sample selection bias. We cannot simplify this further because there are no independence relationships between each $$x_i$$, $$y$$, and $$s$$. Therefore, naive Bayes learners are global learners.

Since it is said that, for global learners, the output of the learner depends asymptotically both on $$P(x)$$ and on $$P(y \mid x)$$, what is it about $$\dfrac{P(x_1 \mid y, s = 1) \dots P(x_n \mid y, s = 1) P(y \mid s = 1)}{P(x \mid s = 1)}$$ that indicates that naive Bayes learners are global learners?

EDIT: To be clear, if we take the example given for the local learner case (section 3.1. Bayesian classifiers), then it is evident:

Bayesian classifiers compute posterior probabilities $$P(y \mid x)$$ using Bayes' rule: $$P(y \mid x) = \dfrac{P(x \mid y)P(y)}{P(x)}$$ where $$P(x \mid y)$$, $$P(y)$$ and $$P(x)$$ are estimated from the training data. An example $$x$$ is classified by choosing the label $$y$$ with the highest posterior $$P(y \mid x)$$.

We can easily show that bayesian classifiers are not affected by sample selection bias. By using the biased sample as training data, we are effectively estimating $$P(x \mid y, s = 1)$$, $$P(x \mid s = 1)$$ and $$P(y \mid s = 1)$$ instead of estimating $$P(x \mid y)$$, $$P(y)$$ and $$P(x)$$. However, when we substitute these estimates into the equation above and apply Bayes' rule again, we see that we still obtain the desired posterior probability $$P(y \mid x)$$: $$\dfrac{P(x \mid y, s = 1) P(y \mid s = 1)}{P(x \mid s = 1)} = P(y \mid x, s = 1) = P(y \mid x)$$ since we are assuming that $$y$$ and $$s$$ are independent given $$x$$. Note that even though the estimates of $$P(x \mid y, s = 1)$$, $$P(x \mid s = 1)$$ and $$P(y \mid s = 1)$$ are different from the estimates of $$P(x \mid y)$$, $$P(x)$$ and $$P(y)$$, the differences cancel out. Therefore, bayesian learners are local learners.

Note that we get $$P(y \mid x)$$. However, in the global case, it is not clear how we get $$P(x)$$ and $$P(y \mid x)$$ (as is required for global leaners) from $$\dfrac{P(x_1 \mid y, s = 1) \dots P(x_n \mid y, s = 1) P(y \mid s = 1)}{P(x \mid s = 1)}$$.

To give a concrete example, assume that $$n = 2$$, our two features are whether a job applicant is qualified and whether they are charismatic, and we are trying to predict whether they will be hired.

Suppose that the conditional probabilities $$P(y|x_1, x_2)$$ follow this table:

P(hired | qualified, charismatic) = 0.4
P(hired | qualified, uncharismatic) = 0.2
P(hired | unqualified, charismatic) = 0.1
P(hired | unqualified, uncharismatic) = 0


Consider the Naive Bayes calculation that estimates the probability that a qualified charismatic person will be hired. To show that the Naive Bayes learner is global, we need to show that the result of this calculation depends not just on the conditional probabilities in the table above, but also on the makeup of our sample. To do this we consider asymptotic behaviour for two possible samples where $$P(x)$$ differs, and check that our calculation returns different answers.

Case 1: our sample has equal proportions of all 4 types of applicant.

P(qualified, charismatic) = 0.25
P(qualified, uncharismatic) = 0.25
P(unqualified, charismatic) = 0.25
P(unqualified, uncharismatic) = 0.25

P(hired) = 0.1 + 0.05 + 0.025 = 0.175
P(qualified|hired) = 0.6/0.7 = 0.857
P(charismatic|hired) = 0.5/0.7 = 0.714

P(qualified|hired)P(charismatic|hired)P(hired)/P(qualified, charismatic) = 0.429


Case 2: our sample mostly consists of qualified charismatic applicants and unqualified uncharismatic applicants.

P(qualified, charismatic) = 0.4
P(qualified, uncharismatic) = 0.1
P(unqualified, charismatic) = 0.1
P(unqualified, uncharismatic) = 0.4

P(hired) = 0.16 + 0.02 + 0.01 = 0.19
P(qualified|hired) = (0.16 + 0.02)/0.19 = 0.947
P(charismatic|hired) = (0.16 + 0.01)/0.19 = 0.895

P(qualified|hired)P(charismatic|hired)P(hired)/P(qualified, charismatic) = 0.403


Changing $$P(x)$$ resulted in a different answer despite the fact that the true conditional probabilities $$P(y|x)$$ didn't change. So the output of our learner depends on $$P(x)$$. (And it also obviously depends on $$P(y|x)$$ - if you change the conditional probabilities in the first table, that affects all the subsequent calculations.) So our learner is global.

• Thanks for the answer. So $P(x)$ would be the "makeup of our sample" in this example? Dec 16, 2020 at 13:33
• @ThePointer yes that's right. Dec 16, 2020 at 13:52
• How did you get the values for P(hired) = 0.1 + 0.05 + 0.025 = 0.175 P(qualified|hired) = 0.6/0.7 = 0.857 P(charismatic|hired) = 0.5/0.7 = 0.714 ? For instance, wouldn't we have $$P(\text{charismatic} \mid \text{hired}) = \dfrac{P(\text{hired} \mid \text{charismatic})P(\text{charismatic})}{P(\text{hired})}$$? I'm probably calculating these values incorrectly. Dec 16, 2020 at 14:11
• P(hired) = P(qualified,charismatic,hired) + P(qualified,uncharismatic,hired) + P(unqualified,charismatic,hired) = P(hired|qualified,charismatic)P(qualified,charismatic) + P(hired|qualified,uncharismatic)P(qualified,uncharismatic) + P(hired|unqualified,charismatic)P(unqualified,charismatic) = 0.4*0.25 + 0.2*0.25 + 0.1*0.25 = 0.1 + 0.05 + 0.025 = 0.175 Dec 16, 2020 at 14:28
• P(qualified|hired) = P(qualified,hired)/P(hired) = (P(qualified,charismatic,hired)+P(qualified,uncharismatic,hired))/P(hired) = (0.4*0.25 +0.2*0.25)/0.175 = 0.15/0.175 = 0.857, and P(charismatic|hired) can be calculated similarly Dec 16, 2020 at 14:28