So it appears that mutual information
tells us which features, words in our
example earlier, are good predictors of
the behavior we want to predict, should we
not use those with the highest mutual
information, as our features.
The trouble is the actual mutual
information from the formula is very
difficult to compute exhaustively.
There are so many different possibilities
with large numbers of features.
So in practice we use proxies.
Well, a good proxy that we've seen earlier
is the Universe Document Frequency.
There are other techniques.
Adaboost, in particular, is an important
algorithm.
But we won't go into that in detail in
this course.
For the moment, think about using those
words with high English document frequency
as a proxy for words which are likely to
be good features.
Another question we might ask is, are more
features always good?
The Y axis here is measuring the error in
the classification, that is how often
naive base gets the wrong answer.
This error improves as we add features,
but after some time it starts to degrade
again.
Why might this be happening?
What do you think?
Perhaps we are using the wrong features to
start with.
It turns out that, that's not the whole
story either.
In this example the features having the
lowest, mutual information, or information
gain which is another term for the same
idea.
It's those bad features which are used
first and then the good features come
later still the classifier goes a wire.
So what's going on?
Can you guess?
Remember that there is a reason why naive
base is called naive.
It doesn't like redundant features.
It assumes that features are independent.
It likes the fact that features have very
small mutual information amongst
themselves.
The trouble is that's not always the case.
And this is one reason why the technique
can fail.
It gets confused because it assumes that
features are independent.
Well, in principle, one should be able to
compute the best features, either by
computing the mutual information directly
or using a proxy, as well as somehow
figuring out which features are dependent.
And choose those best features which are
also dependent.
Many, many machine learning techniques do
exactly this.
We don't have time to go into the
techniques in detail.
But, the idea should be clear by now.
Let's return now to looking at machine
learning from the perspective of
information theory.
We have a machine learning algorithm which
takes the sequence of observations such as
comments and classifies them as positive
or negative.
In a manner so as to maximize the mutual
information between the observations and
their actual classifications versus the
ones that the algorithm manages to
predict.
Relating this to what Shannon defined as
the capacity of a communication channel in
his this was an actual communication
channel if you remember like a telephone
channel or a radio channel.
He, Luke, was worried about how fast you
could transmit information on such
channel.
So, he defined the capacity of a channel
as the maximum information that could be
transferred between the sender and
receiver per second.
So, the element of speed comes in when you
talk about capacity.
What does this mean in the context of
machine learning?
Is there an equivalent, notion of
capacity?
How, fast can a machine algorithm actually
learn?
Or what does it mean to be fast?
It turns out that there have been a lot of
work on the theory of machine learning.
The pioneer on this is Leslie Valiant who
won the touring award in 2011.
And other important papers defined
something called the VC dimension using
which it was shown in this paper the right
bayesian classifier will eventually learn
any concept, or any distinction between
plus and minus, yin and yang.
The trouble is it need not run as fast.
What does that mean?
How many training examples does a
classifier require to learn a concept?
That's the equivalent of speed in the
world of machine learning.
And how fast depends on the concept
itself, and the VC dimension or the Vapnik
Chervonenkis Dimension of a concept can be
measured.
Using which, this paper showed that
Bayesian learning can eventually learn any
concept.
And the speed depends on the VC dimension
of the concept.
Well, that's all we're going to do
regarding machine learning theory for the
moment.
Let's return now to the question of
whether sentiment analysis is actually
measuring an opinion about a product, a
course or anything else.
Remember there are hundreds of millions of
tweets a day, we can listen to the voice
of the consumer like never before, we can
figure out the sentiments and all these
things, just as we've discussed in our
example.
But how do we figure out what consumers
are saying or complaining about, not just
whether or not they are complaining?
What is the object of their complaint, or
for that matter their request or demand?
Consider a comment such as, 'Book me an
American flight to New York.' What does
the word American mean?
Does it mean the airline, American
Airlines?
Or does it mean the nationality of the
airline, so that any airline of American
origin will do.
Obviously, this is an ambiguous sentence
and language is full of such vagueness and
ambiguities.
Suppose the writer also said, 'I hate
British food.' Maybe the guess is now it's
probability American Airline because
British Airways is also another airline
and maybe they're talking about the food
on British Airways.
But suppose the comment was, 'I hate
English food', well suddenly you change
your decision and now he is thinking of
any American carrier, not just American
airlines, because American versus English
clearly distinguishes the fact that he is
talking about the nationality versus
American versus British means that is more
likely to be talking about the carriers
themselves.
Consider this sentence, 'I only eat
Kellogg cereals' verses only 'I eat
Kellogg cereals.' Two very different
things.
What can you say about this home's
breakfast stockpile?
Clearly in the first case it's possibly
saying that, that person really wants to
eat only Kellogg's.
In the second case, he's saying, maybe he
wants to eat Kellogg's, but the rest of
his family just doesn't like it.
Two very different meanings.
'Took the new car on terribly bumpy road.'
It did well though.
Is this family happy with their new car?
Just looking at sentiment, it has so many
negative words - terrible, bumpy.
It does have this positive word well, but
would the basin classifier guess that this
is a positive or a negative comment
properly?
Probably not.
The point we're trying to get at is
Beijing learning using a bag of words,
just features being words themselves.
Is it enough?
And more deeply we're trying to ask the
issue of Richard Montague and Nomchansky
how do we actually discern the meaning of
a sentence versus just classifying it as
positive, negative, good or bad, yin or