Discriminative Learning can Succeed whereGenerative Learning Fails ?
Philip M. Long, a Rocco A. Servedio, b,∗,1 Hans Ulrich Simon ca Google, Mountain View, CA, USAb Columbia University, New York, New York, USA
c Ruhr-Universität Bochum, Bochum, Germany

Abstract
Generative algorithms for learning classifiers use training data to separately estimate a probability model for each class. New items are classified by comparing theirprobabilities under these models. In contrast, discriminative learning algorithms tryto find classifiers that perform well on all the training data.
We show that there is a learning problem that can be solved by a discriminative
learning algorithm, but not by any generative learning algorithm. This statement
is formalized using a framework inspired by previous work of Goldberg [4].
Key words: algorithms, computational learning theory, discriminative learning,generative learning, machine learning

1

Introduction

If objects and their classifications are generated randomly from a joint probability distribution, then the optimal way to predict the class y of an item x
is to maximize Pr[y|x]. Applying Bayes’ rule, this is equivalent to maximizing Pr[x|y] Pr[y]. This motivates what has become known as the generative
approach to learning a classifier, in which the training data is used to learn? Reference [8] is a preliminary version of this paper but contains a flaw; see themore detailed note at the end of Section 1.
∗ Corresponding author.
Email address: rocco@cs.columbia.edu (Rocco A. Servedio,).
1 Supported in part by NSF CAREER award CCF-0347282, by NSF award CCF0523664, and by a Sloan Foundation Fellowship.

Preprint submitted to Elsevier Science

26 February 2007

Pr[·|y] and Pr[y] for the different classes y, and the results are used to approximate the behavior of the optimal predictor for the source (see [2,6]).
In the discriminative approach, the learning algorithm simply tries to find aclassifier that performs well on the training data [12,6,10,7]. Discriminative algorithms can (and usually do) process examples from several classes together
at once, e.g. maximum margin algorithms use both positive and negative examples together to find a large margin hypothesis separating the two classes.
The main result of this paper is a separation between generative and discriminative learning. We describe a learning problem and prove that it has thefollowing property: a discriminative algorithm can solve the problem, but nogenerative learning algorithm can.
Our analysis demonstrates the possible cost of largely processing the examples
from different classes separately, as generative methods do. Goldberg [4,5] was
the first to study the effect of this limitation. He studied a modification of thePAC model in which• the examples belonging to each class are analyzed separately,• each analysis results in a scoring function for that class, and• future class predictions are made by comparing the scores assigned by thedifferent scoring functions.
He designed algorithms that provably solve a number of concrete learning
problems despite the constraint of processing examples from different classes
separately, and identified conditions that allow a discriminative PAC learner
to be modified to work in the generative setting. The main open question
posed in [4] is whether there is a learning problem that can be solved by adiscriminative algorithm but cannot be solved by a generative algorithm. We
establish our main result in a framework closely related to the one proposedin [4]. The main difference between our formulation and Goldberg’s is that
we define a learning problem to be a collection of possible joint probability
distributions over items and their classifications, whereas Goldberg defined alearning problem to be a concept class as in the PAC model.
Related work. Aside from Goldberg’s paper, the most closely related work
known to us is due to Ng and Jordan [9]. They showed that Naive Bayes,
a generative algorithm, can converge to the large-sample limit of its accuracy much more quickly than a corresponding discriminative method. For
generative algorithms that work by performing maximum likelihood over restricted classes of models, they also showed, given minimal assumptions, thatthe large-sample limit of their accuracy is no better than a corresponding discriminative method. Note that these results compare a particular generativealgorithm with a particular discriminative algorithm. In contrast, the analysis in this paper exposes a fundamental limitation faced by any generative2

learning algorithm, due to the fact that it processes the two classes separately.
Note. A preliminary version of this work [8] claimed a computational separation between discriminative and generative learning based on a cryptographic
construction, but the proof was flawed. The current note deals only with theinformation-theoretic abilities and limitations of discriminative and generativealgorithms, i.e. we are only concerned with sample complexity and not withthe running time of learning algorithms.
Section 2 contains preliminaries including a detailed description and motivation of the learning model. In Section 3 we give our construction of a learning
problem that separates the two models. Section 4 gives the proof.

2Definitions and main result

Given a domain X, we say that a source is a probability distribution P overX × {−1, 1}, and a learning problem P is a set of sources.
2.1 Discriminative learning
The discriminative learning framework that we analyze is the Probably Approximately Bayes (PAB) [1] variant of the PAC [11] learning model. In thePAB model, in a learning problem P a learning algorithm A is given a set ofm labeled examples drawn from an unknown source P ∈ P. The goal is to,with probability 1 − δ, output a hypothesis function h : X → {−1, 1} whichsatisfies Pr(x,y)∼P [h(x) 6= y] ≤ Bayes(P ) + , where Bayes(P ) is the least error
rate that can be achieved on P , i.e. the minimum, over all functions h, ofPr(x,y)∼P [h(x) 6= y].
We say that P is PAB-learnable if for any , δ > 0 there is a number m =m(, δ) of examples such that A achieves the above goal for any source P ∈ P.
2.2 Generative learning
Goldberg [4] defined a restricted “generative” variant of PAC learning. Our
analysis will concern a natural extension of his ideas to the PAB model.
Roughly speaking, in the generative model studied in this paper, the algorithm
first uses only positive examples to construct a “positive scoring function”
h+ : X → R that assigns a “positiveness” score to each example in the3

input domain. It then uses only negative examples to construct (using thesame algorithm) a “negative scoring function” h− : X → R that assigns a“negativeness” score to each example. The classifier output by the algorithm
is the following: given example x, output 1 or −1 according to whether or noth+ (x) > h− (x).
We now give a precise description of our learning framework. In our model• A sample S = (x1 , y1 ),...,(xm , ym ) is drawn from the unknown source P ;• An algorithm A is given a filtered version of S in which· examples (xt , yt ) for which yt = 1 are replaced with xt , and· examples (xt , yt ) for which yt = −1 are replaced with 
and A outputs h+ : X → R.
• Next, the same algorithm A is given a filtered version of S in which· examples (xt , yt ) for which yt = 1 are replaced with , and· examples (xt , yt ) for which yt = −1 are replaced with xt
and A outputs h− : X → R.
• Finally, let h : X → {−1, 1} be defined as h(x) = sgn(h+ (x) − h− (x)). Ifh+ (x) = h− (x) then we view h(x) as outputting ⊥ (undefined).
Algorithm A is said to be a generative PAB learning algorithm for P if for allP ∈ P, for all 0 <  < 21 , 0 < δ < 1, there is a sample size m = m(, δ) suchthat, given m examples, the hypothesis h obtained as above, with probability
at least 1 − δ, satisfies Pr(x,y)∼P [h(x) 6= y] ≤ Bayes(P ) + .
It is easy to see that any learning problem that can be PAB learned in thegenerative framework we have described can also be learned in the standard
PAB framework.

2.3 Main result
With these definitions in place we can state our main result:
Theorem 2.1 There is a learning problem P that is learnable in the PAB
model, but not in the generative PAB model.

3The construction

The domain is X = {0, 1}∗ × {1, 2, 3}. With every n ≥ 1 and every r, s ∈{0, 1}n , we associate a source Pr,s with support contained in {0, 1}n × {1, 2, 3}
and given as follows:4• It assigns probability 1/3 to the pair ((r, 1), 1) (that is, item (r, 1) and class1).
• It assigns probability 1/3 to the pair ((s, 2), −1) (item (s, 2) and class −1).
1to each ((ei , 3), (−1)ri ⊕si ), where ei ∈ {0, 1}n is the• It assigns probability 3nvector that has a 1 in the ith coordinate and zeroes everywhere else. Hereri ⊕ si denotes the exclusive-or of the i-th components of r and s.
The problem P witnessing the separation of Theorem 2.1 consists of all such
Pr,s . Note that for any source Pr,s the error rate of the Bayes optimal predictor
is 0.

4

Proof of Theorem 2.1

Because r and s “give everything away,” a discriminative algorithm can succeed easily.
Lemma 4.1 Problem P can be solved using at most 2 log 2δ examples.
Proof. If (r, 1) and (s, 2) are both in the training data, a discriminative algorithm can determine the classifications of all remaining elements of the domain,as the correct classification of (ei , 3) is (−1)ri ⊕si . Consider an algorithm that
does this, and behaves arbitrarily if it has not seen both (r, 1) and (s, 2). The
probability that at least one of (r, 1), (s, 2) is not present in a sample of m
examples is at most 2 × (2/3)m . Solving for m completes the proof.
Now we show that generative algorithms must fail. Our argument uses theprobabilistic method as in [3]. We will show that any algorithm A must perform
poorly on a randomly chosen source. This implies that there is a source on
which A performs poorly.
Lemma 4.2 Fix a generative learning algorithm A. For any n ≥ 2, if• r and s are chosen uniformly at random from {0, 1}n ,• m ≤ n examples are chosen according to Pr,s ,• the positive and negative examples are separately passed to A as in the definition of the generative PAB learning framework, and• the invocations of A output h+ and h− ,then with probability at least 1/40 (over the random draw of r, s and the random draw of the m-element sample from Pr,s ,) the source Pr,s puts weight atleast 1/40 on pairs (x, y) for which sgn(h+ (x) − h− (x)) 6= y.
5Proof. Suppose that r, s ∈ {0, 1}n are chosen randomly, and that
(x1 , y1 ), ..., (xm , ym ), (x, y)
are chosen independently at random according to Pr,s .
The proof proceeds by first lower bounding the conditional probability thatthe hypotheses h+ , h− output by A collaborate to predict the class y of x
incorrectly, given that a particular event E occurs. The proof is completed bylower bounding the probability of E.
Event E is defined as follows: a draw of r, s, (x1 , y1 ), ..., (xm , ym ), (x, y) satisfies
event E if there is some i such that x = (ei , 3) and none of x1 , . . . , xm is (ei , 3).
Suppose that event E occurs. Let i be the value in {1, ..., n} such that x =(ei , 3) and none of x1 , . . . , xm is (ei , 3). Consider any fixed setting of values for
all components of r except for ri , and all components of s except si . Similarly
consider any fixed setting of values for (x1 , y1 ), ..., (xm , ym ) such that xt 6=(ei , 3) for all t ∈ {1, ..., m}. (Note that if xj is set to (r, 1) or (s, 2) then thei-th component is not yet fixed.) Let us denote this more specific event by E 0 .
Now consider the probability distribution obtained by conditioning on E 0 ;note that the only remaining randomness is the choice of ri , si ∈ {0, 1}. According to this distribution, each of the four possible pairs of values for ri , si
are equally likely, and, in each case, the corresponding class designation for
x is (−1)ri ⊕si . However, after conditioning on E 0 , the scoring function h+ iscompletely determined by the value of ri (recall that when algorithm A constructs h+ it may well receive the example (r, 1) but it does not receive theexample (s, 2)). This implies that the value h+ (x) is completely determinedby the value of the bit ri . Similarly, the value h− (x) is completely determinedby the value of the bit si . Consequently, sgn(h+ (x) − h− (x)) is a function of(ri , si ) ∈ {0, 1}2 ; further, since ri and si only affect h+ (x) and h− (x) respectively, sgn(h+ (x) − h− (x)) is in fact a linear threshold function of the variablesri and si . It is well known that a linear threshold function cannot computea parity over two boolean variables. Therefore, given event E 0 , there must beat least one combination of values for ri and si such that A predicts (−1)ri ⊕si
incorrectly. Since all combinations of values for ri and si are equally likely, theconditional probability that A predicts x incorrectly given E 0 is at least 1/4.
It follows that the conditional probability that A predicts x incorrectly given
event E is at least 1/4.
It is straightforward to lower bound (in fact, exactly compute) the probabilityof event E. Since all pairs (xi , yi ) are drawn independently, the probability ofevent E is easily seen to be
1
1× 1−
33n


6m.

If m ≤ n, this probability is at least
11× 1−
33n


n

1
≥ .
5Thus, the overall probability that sgn(h+ (x) − h− (x)) 6= y is at least 1/20.
This easily yields the lemma.
From this we can easily establish the following which proves Theorem 2.1:
Lemma 4.3 P is not learnable in the generative PAB model.
Proof. Fix algorithm A. Suppose, in Lemma 4.2, we first choose r and s from{0, 1}n , and then choose the random examples from Pr,s . Then the expectation,over r and s, ofPr

(x1 ,y1 ),...,(xm ,ym )[Pr,s puts weight at least 1/40 on (x, y) such thatsgn(h+ (x) − h− (x)) 6= y]

is at least 1/40. This means that there is a particular choice of r and s for
which
Pr

(x1 ,y1 ),...,(xm ,ym )[Pr,s puts weight at least 1/40 on (x, y) such thatsgn(h+ (x) − h− (x)) 6= y] > 1/40.

Thus, at least n examples are needed to learn Pr,s whenever  and δ are eachat most 1/40. By fixing  and δ at 1/40, and choosing n arbitrarily large, wecan see that there is no fixed sample size, as a function of  and δ, that suffices
to PAB-learn arbitrary members of P to accuracy  with probability 1 − δ.
Note that the proof does not depend on the fact that the same algorithm wasapplied to the positive and negative examples. Furthermore, a straightforward
extension of the proof generalizes Lemma 4.2 to generative learning algorithms
that are probabilistic. 2 Thus, we get the following for free.
Theorem 4.4 Suppose the generative PAB learning model is relaxed so that
separate (and possibly probabilistic) algorithms can be applied to the positive
and negative examples. Then it remains true that there is a learning problem
that can be solved in the standard PAB model, but not in the generative PABmodel.
2

Include a fixed choice of the learner’s random bits into the restricted event E 0 .

7

5Conclusions and Future WorkWe presented a learning problem in the Probably Approximately Bayes framework which has the property that a discriminative algorithm can solve theproblem, but no generative algorithm can solve the problem. One drawbackof our construction is that it is arguably somewhat artificial and contrived.
While it nevertheless serves to separate the two learning models, it would beinteresting to come up with a more natural construction that also successfullyseparates the models.
A goal for future work is to extend our separation to the Probably Approximately Correct (PAC) learning model. Another goal is to explore computational separations between discriminative and generative learning.

References[1] Svetlana Anoulova, Paul Fischer, Stefan Pölt, and Hans Ulrich Simon. Probably
almost bayes decisions. Information and Computation, 129(1):63–71, 1996.
[2] R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification (2nd ed.).
Wiley, 2000.
[3] A. Ehrenfeucht, D. Haussler, M. Kearns, and L. G. Valiant. A general lower
bound on the number of examples needed for learning. Information andComputation, 82(3):247–251, 1989.
[4] P. Goldberg. When Can Two Unsupervised Learners Achieve PAC Separation?
In Proceedings of the 14th Annual COLT, pages 303–319, 2001.
[5] P. Goldberg. Some Discriminant-Based PAC Algorithms. Journal of Machine
Learning Research, 7:283–306, 2006.
[6] T. Jaakkola and D. Haussler. Exploiting generative models in discriminativeclassifiers. In Advances in NIPS 11, pages 487–493. Morgan Kaufmann, 1998.
[7] T. Jebara. Machine learning: discriminative and generative. Kluwer, 2003.
[8] P. M. Long and R. A. Servedio. Discriminative learning can succeed wheregenerative learning fails. In Proc. 19th Conference on Computational Learning
Theory, pages 319–334, 2006.
[9] A. Y. Ng and M. I. Jordan. On discriminative vs. generative classifiers: A
comparison of logistic regression and naive bayes. NIPS, 2001.
[10] R. Raina, Y. Shen, A. Y. Ng, and A. McCallum. Classification with hybrid
generative/discriminative models. NIPS, 2004.

8

[11] L. G. Valiant. A theory of the learnable. In Proc. 16th Annual ACM Symposiumon Theory of Computing (STOC), pages 436–445. ACM Press, 1984.
[12] V. Vapnik. Estimations of dependences based on statistical data. Springer, 1982.

9