The explanation of the 'naive' part of Naive Bayes isn't quite right, though. Throwing out the possibility of the animal being human based on the datapoint "four legs" is orthogonal to naivety. A more sophisticated Naive Bayes system could reject classifying an animal as human based on having four legs, and conversely a non-naive system i.e. one that used joint probabilities of the features, might not be more likely to.
I guess the most rational way to do that would be to express and calculate the conditional probabilities with some statistical distance, like the # of standard deviations. So 100k examples of humans without a single one having the "four legs" feature would make that a very strong indicator of being non-human. And that'd work just as well with a naive algorithm as any other.
Is there a name for this?