Let's recall our Bayesian classifiers for figuring out whether a query or a comment
had positive or negative sentiment. Our Bayesian classifier looks something
like this. We wanted to figure out whether somebody
was a buyer or a browser depending on the words that they used in their query.
Trouble is, if the word cheap and gift are not independent, that is the probability
that somebody uses the word gift depends on the probability that they use the word
cheap. That means, the probability of using the word gift given that they use
the word cheap and that they are a buyer is not the same as the probability of gift
independently. As a result, there, we actually have a
dependence between cheap and gift which is exhibited in this network by an arc
between these two nodes. In the language of Bayesian networks, what
this means is to compute the, a posterior probability of a buy given any of these
occurances. Our expansion needs to include the
probability of a gift given C and B. Or alternatively, the probability of cheap
given G and B. Depending on the order in which we expand
the joint probability of G, C, and B. We've seen this in the last segment.
Another example could be the sentiment from comments.
A comment like, I don't like the course, and I like the course, don't complain,
both contain the word don't and like, but they are clearly different sentiments.
So, at first, we might include don't in our list of features along with other
nega, negatives like not, etc. But that doesn't quite do the work because
we also need to deal with the positional order in which these words occur.
Just including negatives doesn't allow us to disambiguate between I don't like the
course, and I like the course, don't complain.
So, the graphical model which might help us here is that we have the class
variable, which is a sentiment, having observed i elements of the comment, and
the class variable, which is the sentiment after observing i + one variables, or
words in the comment. And we have the probability of Xi + one
given probability of Xi, and S for every position i.
In this case, it's Si + one, In this case it is Si. The appropriate S is used for
this likelihood. If we use these likelihoods and try to
compute the most likely estimate for the probability of S being yes or no at the
n-th position, we get what is called a hidden Markov model, which is another type
of Bayesian network. It's especially use, useful when dealing
with sequences like sentences or spoken words, and trying to figure out what
actual text you are, one is trying to speak, trying to extract phonemes from
speech, and other sequences. In such situations, we may also need to
accommodate holes, For example, P probability of Xi + kk
given the probability of X and i. So, whatever is in between, you might have
a don't before a like, It might give you a positive or a negative
sentiment. Whereas, if the don't comes after the
like, we might get a positive sentiment as more likely.
So, this is one example of how Bayesian networks allow us to go beyond
independence features while building classifers.
There's another application of probabilistic networks, like Bayesian
networks and graphical models in general. We ask the question, how do these facts
like Obama is the president of USA, or Manmohan Singh is the leader of India
arise after learning from large volumes of text?
How do we get those individual facts and rules so critical to be semantic web
vision? Suppose we want to learn facts of the
forum subject group object from text. We might use a Baysian network of the
following form where we have subject, verb, object, which processes triples in
the text and might come up with, with a situation like antibiotics kill bacteria.
The single class variable is clearly not enough, since we need to have subject,
verb and object in the language of the unified formulation of learning that we
did last time. We have many y's in the Y, X data.
In the, when we looked at learning from the perspective of f of x, if you remember
that. In addition, one needs to deal with
positional order so we can use a different graphical model like, the hierarchical
Markov models or other types of models that look like this.
We need to know the probability of X sub i,
That means, any particular word occurring, given a, the previous word, the class of
the previous word, and the class of the present word.
For example, the probability that kill following antibiotics is a verb will
depend on whether antibiotics is the subject.
Situation is probably more apparent for the example, person gains weight, where
the word gains can be a verb or a noun. So, whether or not gains is a verb would
depend on whether or not person is classified as a subject.
Now remember, this is all supervised learning.
So, what we have is a whole bunch of text labeled as subject, verb, object from
which we compute these likelihoods or probabilities.
And using that, we figure out the a-posterior probabilities of subject,
verb, and object for every word in the text. And where we have a high combination
of S, V, and O, we can assert the fact that subject, verb, object has been
learned from this piece of text. We also have to alive, allow for holes
such as, so that we have to deal with things like subjected i minus k, verb at
i, and object at i plus P. Now, this gets very complicated especially
since we can have a large number of words and a large number of possible places,
ways of including holes, so the Bayesian network models are not necessarily the
most efficient. And other models, such as conditional random fields or Markov
networks turn out to be more efficient in this kind of situation.
Once we have found many facts, like Obama is President of USA, etc., and many
instances of such facts, We cull from all these facts using this
support and confidence. So, we'll disregard facts which we learn
only once or twice and keep those facts which we have learned many times from
different independent pieces of text. And this is how large volumes of facts
are, in fact, learned from the many millions and billions of documents on the
web. This whole exercise of learning from the
web is called information extraction, or open information extraction,
And there are many examples of such efforts.
One of the oldest efforts is called Cyc. It's a semi-automated technique and has so
far accumulated about two billion such facts.
Yago is more recent and is the largest to date.
It's run out of the Max Planck Institute in Germany, and has uncovered more than
six billion facts, and they're all linked together as a graph.
So, now Obama is president of USA, USA lies in North America, etc. etc. etc.,
They're all linked together. Albert Einstein was born in Ulm, for
example, Is, is a fact that Watson could've learned
from a database like Yago. And, Watson actually uses facts culled
from the web internally. It doesn't use Yago or Cyc but it uses
many, many webpages and textual documents and rules,
And this is another example of open information extraction.
Reverb is by the same group as Yago It's more recent, it's lightweight, it's only
got fifteen million S, V, O triple so far. For example, it has things like potatoes
are also rich in Vitamin C, so that the verbs are also verb phrases, that's sort
of less useful than Yago in this sense but it's much more diverse in the sense of the
kind of phrases that it actually includes. The way REVERB works just to give you a
flavor for how such systems work is, first it tags each piece of text using natural
language processing classifiers to say which is a noun-phrase, which is a
word-phrase, which is a preposition, etc. And then, it focuses only on the verb
phrases and figures out what are the nearby non-phrases using classifiers just
as we have discussed. It prefers proper nouns, especially if
they occur often in other facts so that, you know, Ein, words like Einstein are
preferred rather than person or scientist. And, wherever possible, it manages to
extract more than one fact from a piece of text.
So, from a text like, Mozart was born in Salzburg, but moved to Vienna in 1781,
yields two facts. Mozart moved to Vienna in addition to, in
addition to Mozart was born in Salzburg. Now, I admit we have gone through this
section fairly quickly. The point I wanted to make is that, the
ability to extract facts is significantly enhanced by the fact that we have so many,
many documents available on the web Using a combination of supervised learning and
unsupervised extraction like, REVERB, which is unsupervised in the sense that
one is not actually labeling any small fraction of text as S,
V, O. We're just using lower level classifiers for part of speech tagging.
By using a combination of these supervised and unsupervised learning techniques, one
can actually extract large volumes of facts and rules from text, and then use
the reasoning techniques that we started with in this lecture this week to actually
move towards the semantic web vision. Along the way, of course, we have to deal
with the situation that we have the limits of logic, which are fundamental, as well
as those limits which come from uncertainty.