(hamner's answer is great, so just cross-posting my answer from MetaOptimize for completeness.)
I think of generative algorithms as providing a model of how the data is actually generated (I think of them as giving you a model of both $P(X|Y)$ and $P(Y)$, rather than of $P(X, Y)$, though I guess it's equivalent), and discriminative algorithms as simply providing classification splits (and not necessarily in a probabilistic manner).
Compare, for instance, Gaussian mixture models and k-mean clustering. In the former, we have a nice probabilistic model for how points are generated (pick a component with some probability, and then emit a point by sampling from the component's Gaussian distribution), but there's nothing we can really say about the latter.
Note that generative algorithms have discriminative properties, since you can get $P(Y|X)$ once you have $P(X|Y)$ and $P(Y)$ (by Bayes' Theorem), though discriminative algorithms don't really have generative properties.
1: Discriminative algorithms allow you to classify points, without providing a model of how the points are actually generated. So these could be either:
- probabilistic algorithms try to learn $P(Y|X)$ (e.g., logistic regression);
- or non-probabilistic algorithms that try to learn the mappings directly from the points to the classes (e.g., perceptron and SVMs simply give you a separating hyperplane, but no model of generating new points).
So yes, discriminative classifiers are any classifiers that aren't generative.
Another way of thinking about this is that generative algorithms make some kind of structure assumptions on your model, but discriminative algorithms make fewer assumptions. For example, Naive Bayes assumes conditional independence of your features, while logistic regression (the discriminative "counterpart" of Naive Bayes) does not.
2: Yes, Naive Bayes is generative because it captures $P(X|Y)$ and $P(Y)$. For example, if we know that $P(Y = English) = 0.7$ and $P(Y = French) = 0.3$, along with English and French word probabilities, then we can now generate a new document by first choosing the language of the document (English with probability 0.7, French with probability 0.3), and then generating words according to the chosen language's word probabilities.
Yes, I guess you could make logistic regression generative in that fashion, but it's only because you're adding something to logistic regression that's not already there. That is, when you're performing a Naive Bayes classification, you're directly computing $P(Y|X) \propto P(X|Y) P(Y)$ (the terms on the right, $P(X|Y)$ and $P(Y)$, are what allow you to generate a new document); but when you're computing $P(Y|X)$ in logistic regression, you're not computing these two things, you're just applying a logistic function to a dot product.
3: Generative models often outperform discriminative models on smaller datasets because their generative assumptions place some structure on your model that prevent overfitting. For example, let's consider Naive Bayes vs. Logistic Regression. The Naive Bayes assumption is of course rarely satisfied, so logistic regression will tend to outperform Naive Bayes as your dataset grows (since it can capture dependencies that Naive Bayes can't). But when you only have a small data set, logistic regression might pick up on spurious patterns that don't really exist, so the Naive Bayes acts as a kind of regularizer on your model that prevents overfitting. There's a paper by Andrew Ng and Michael Jordan on discriminative vs. generative classifiers that talks about this more.
4: I think what it means is that generative models can actually learn the underlying structure of the data if you specify your model correctly and the model actually holds, but discriminative models can outperform in case your generative assumptions are not satisfied (since discriminative algorithms are less tied to a particular structure, and the real world is messy and assumptions are rarely perfectly satisfied anyways). (I'd probably just ignore these quotes if they're confusing.)