The most simple and fundamental technique
of machine learning is called the bayesian
classifier.
And it's also called a Naive Bayesian
Classifier, because it makes the
assumption that all the futures that one
uses to learn about historical data are
independent for a particular choice of the
behavior one is trying to learn.
So, for example, if one is trying to
predict whether a given user is shopping
or just surfing using the query words that
they use to search.
We assume that the words itself are all
independent and equally likely to occur
independent of what other words are used
in the query.
It's not necessarily of valid assumptions
in most cases as we have just argued a
while back.
But that's what is assumed and that's why
it's called naive based classifiers.
Anyway, let's try to figure this out from
first principles.
The probability, of B that is, whether
some user is a buyer, or just a browser.
Given, the combination of R and C that
they use times the probability of R and C
itself.
By Bayes rule, this is nothing but the
probability of R and C, given B the
probability of B.
This is easy to see just by thinking of R,
C as one random variable, and just using
Bayes rule.
Next, we further expand the first term
over here.
Again using Bayes rule, forgetting about B
for the time being.
And, noting that the probability of R and
C given B is the probability of R given C
and B is there just because it was
earlier, times the probability of c given
b which again is there because it was
there up there.
Again, by applying Bayes rule we get this
expansion.
Now comes the independence assumption.
The probability that of R given C and B or
A or whatever else, it doesn't matter
because of independence of R and C is the
same as the probability of R given
whatever else was there on the conditional
side.
Because of this independence we can
essentially separately compute these terms
probability of R given by equal to yes,
Probability of C given by equal to yes.
And then just simply multiply by it by the
a priori, or the overall probability, of
by equal to yes.
We can do the same for by equal to know.
So given some values of R and C, that is
whether the word red occurs or the word
cheap occurs or not.
We compute the probability of R being
there given that by is yes.
C being there or not there given by equal
to yes.
And the a priori probability of B equal to
yes and divide it by the same expression
that we have here but for the other
possibility that i equal to a no.
Now, since this expression is proportional
to the conditional probability that we're
looking for.
That is whether or not the user is more
likely to be a buyer versus a browser
given the query words that they used, we
simply compute this ratio for both
possibilities buyer or browser and if this
ratio is greater than one.
In general creating some threshold we
chose the option of buy equal to yes as
being the most likely estimate.
Otherwise, we decide that buyer equal to
no.
So, congratulations.
We have just derived the most fundamental
classification mechanism on machine
learning technique called the Naive Bayes
Classifier from first principles.
And, as you can see, the derivation is
simple arithmetic and basic probability.
Given any combination of words and the
past history say you have four features
that we had earlier.
Red flower gift and cheap and in general N
features.
Arbitrary long queries for example, taking
particular values yes, no, yes, no,
etcetera, etcetera, weakens merely compute
the ratio that we had earlier.
Simply now that we have N terms in the
product as opposed to just two.
And in the end, the a priori probabilities
of the two different types of behavior
that we're trying to predict.
This ratio is called a likelihood ratio
because each of these terms in the product
is a likelihood in the sense that if x1 =
yes then the probability here is the
probability that x1 = yes for the
situation when people are buying versus
the probability that x1 = yes when people
are just browsing.
And we do that for all the possible words.
Many of them will have a, no, so xi's for
them will be, no.
But we still have to take all the possible
words into account.
And choose yes, if this likelihood ratio
is greater than a threshold and, no,
otherwise.
We also normally take logarithms to make
multiplications into additions, so you
would frequently hear the term log
likelihood.
The reason is because off these many, many
probabilities all less than one being
multiplied.
You probably will run out of decimal
points and you'll get all zeros.
So by taking logarithms you will reduce
the and of such underflow occurring and
make the computation stable.
In particular that you really need to
consider all possible features.
Even those that don't occur in the query.
So, if you have a million words, and your
query consists of four words, you need to
multiply the probabilities for a million
words.
For the four words that you have, you'll
use the probability that the word occurs
for buyers and the probability that the
word occurs for browsers.
And for the rest, you'll have to include
the probabilities that the word does not
occur for buyers and for browsers in the
denominator.
Now this makes it an extremely expensive
method, but never the less quite useful.
The expensiveness we'll figure out how to
deal with using parallel computing next
week.
But for the moment lets take a look at an
example of trying to compute sentiment
using machine learning and the Naive Bayes
Classifier.