Probabilistic graphical models (PGMs) are a rich framework for encoding probability distributions over complex domains: joint (multivariate) distributions over large numbers of random variables that interact with each other. These representations sit at the intersection of statistics and computer science, relying on concepts from probability theory, graph algorithms, machine learning, and more. They are the basis for the state-of-the-art methods in a wide variety of applications, such as medical diagnosis, image understanding, speech recognition, natural language processing, and many, many more. They are also a foundational tool in formulating many machine learning problems. This course is the first in a sequence of three. It describes the two basic PGM representations: Bayesian Networks, which rely on a directed graph; and Markov networks, which use an undirected graph. The course discusses both the theoretical properties of these representations as well as their use in practice. The (highly recommended) honors track contains several hands-on assignments on how to represent some real-world problems. The course also presents some important extensions beyond the basic PGM representation, which allow more complex models to be encoded compactly.
Value of Perfect Information
Loading...
Do curso por Stanford University
Probabilistic Graphical Models 1: Representation
836 classificações
Na lição
Decision Making
In this module, we discuss the task of decision making under uncertainty. We describe the framework of decision theory, including some aspects of utility functions. We then talk about how decision making scenarios can be encoded as a graphical model called an Influence Diagram, and how such models provide insight both into decision making and the value of information gathering.
Conheça os instrutores
Daphne KollerProfessor
School of Engineering
We showed how influence diagrams can allow an agent to make decisions
regarding what course of action the agent should take given a set of observations.
But often we want to answer a different type of question, which is what
observations should I even make before making a decision?
For example, a doctor encountering a particular patient might have to decide
which set of tests to perform on that patient.
Tests are not free, they cause pain to the patient, they come
with a risk, and they cost money. So which ones are worthwhile and which
ones are not? The same kind of question comes up in
many other scenarios. So for example, if you're running a
sensor network, which sensors should I measure?
The sensor might require energy in order to transmit the information and that may
be something that we want to consider carefully.
And there's many other examples of that. It turns out that the same framework of
influence diagrams can also be used to answer that question using rigorous
formal foundations. But how do we provide a formal semantics
for the notion of the value of getting information or the value of making an
observation? So the, the formal definition that one
can provide for this is the value of perfect information.
So this, this stands for value of perfect information about a variable X, is the
value that we have by observing X, before choosing an action in A.
And, perfect means that we observe X with perfectly without any, without any noise.
How do we make that a formal how do we give that a formal value?
Well, if D was our original influence diagram before I had the opportunity to
observe X. We can compare the value of D to the
value of a different influence diagram, which is the one where I introduce an
edge from X to A. Because that tells me what the value of
the situation would be if if I had that, the ability to make that
observation. So we can now define the value of perfect
information to be simply a difference between the maximum expected utility that
I have in the situation where I have this observation.
Minus the value, the expected utility to the agent in a scenario where I don't.
So in this example that we've presented before, we saw that we'd compared two
decision situations. One where the agent has found the company
without any kind of additional information about the value of the
market. And the other is where the agent gets to
make an observation regarding the survey variable prior to making the decision
whether to found the company. So we can compare the value of the
decision making situation with a variable from F to F.
Minus. The value of the decision making
situation. Assuming the agent makes optimal
decisions, of the original decision making situation d.
And we can compare that and see how much the agent's gained by this.
And if you recall, we computed this to be 3.25.
And this was two. So the value of perfect information was
1.25. Which means that the agent should be
willing to pay anything up to 1.25 utility points bef- in order to conduct
the survey because doing that will increase his expected utility.
So let's look at some of. Properties of the value of perfect
information. So, the first important property of the
value of perfect information, is assuming that there's no cost of the information,
so not counting in how much it might cost say to conduct the survey.
One can show that the value of perfect information is always greater than or
equal to zero. So let's first go ahead and convince
ourselves that this is true. So lets look at this expression over here
which compares the maximum expected utility between two different influence
diagrams. And remember that each of these is
obtained by optimizing. Over a decision rule, this one is
optimized as the MU of the original decision V, is optimizing a decision rule
delta which is a CPD of A given it's current set of parents Z.
In this one the new influence diagram is optimizing a decision rule delta where A
has Z, all the original parents Z plus an additional parent X.
And the point that one, that becomes obvious when you think of it this way, is
that this is a strictly larger class of CPDs then this.
That is, any CPD. Of the form delta of A given Z is also a
CPD. Of the form delta of A given dx, which
means any decision rule that I have could implemented in my original influence
diagram I can also implement in the context of my current influence diagram
and if it had a particular value there it will still have that same expected
utility value in the original diagram. So to go back to our example for exam-
for instance. If the agent.
Has a, decision role that, found, the sides say to found the company,
regardless of the value of the survey, that is a still a legitamate decision
role, even when they get to observe the survey and it would have the same,
expected utility. And so, that means that the set of
decisions that I get to consider is, just larger in the context of the richer of
the richer influence diagram, and therefore, one cannot possibly lose, by
exploring a larger set of, a larger space over which to optimize.
Okay. So, now let's think about the second
property. Which is, when this value of perfect
information. Is equal to zero.
And this, follows from very similar reason to the one.
That, we just talked about. So if, the optimal decision rule for, D.
And for my original influence diagram B is still optimal for the exntended
influence diagram, then I've gained nothing, from the information, that is,
I, any, any decision that I could, any decision rule that I could have applied
before, I can still apply and therefore there, I have gained nothing from this
additional observation. And so this gives us a very clear notion
of when information is useful. Information is useful precisely when it
changes my decision. In at least one case.
Which thinking about this from the other perspective if there's no ability for an
observation to change my decision there's really no point in making it.
Let's see how this intuition manifests in an actual decision making scenario.
So, let's imagine that our entrepreneur has decided against founding a widget
company, and is now starting to trying to pick between two companies that he can
choose to join. For each company, there is the state that
the company is in. So, S1 is that the company is not,
doesn't have that great of a management. Things are not necessarily going so well.
So that's S1. S two is medium and s three is the
company is doing great. And the same thing holds for both
companies. We are assuming that the company funders
have access to some of the info, to this information about the company's state
because they can do some very in depth due diligence.
And so the chances of a company to get funding.
Depends on the state of the company, so you can see if the company state is poor,
S1, then the chances of getting funding are zero point one.
Where as if the company is doing great the chances of getting funding are zero
point nine. And we're seeing that the agent's utility
is one if the company that he chose, that he joins.
It's funded, and zero otherwise. So now let's think about the two
strategies that the agent can take without any information, and so if the
agent chooses to join company one one can see that company one is
that the expected utility now is 0.72, and the expected utility of company two
which is not doing as great is only 0.33. That's, you know, if you look at the
state of the company that makes perfect sense.
Now what happens if the agent now gets to make an observation?
And specifically, we're going to let the agent make the observation.
Of s2, regarding s2. Which is, in this case the weaker of the
two companies. The agent has a little mole inside the
company, and can get access to that information before making decision.
What happens then? Well
the if you look at the utility values you can see that if company one is in state,
sorry if company two is in state one. Then, which is a not unlikely scenario,
it happens with probability 40%. But chances of getting funding are 0.1.
And so the agents expected utility in this case, so the expected utility if.
The agent chooses c2, and s and the state of the second company is s1, is 0.1.
The accepted utility if C equals C, if the company, if the agent chooses the
second company and it's doing. Moderatly well in 0.4, both of these are
lower then 0.72 that the agent can guarentee on expectation if he choses
company one, even without any additional information on company one.
And so in both of these cases the agent is going to prefer.
Stick with his original. Choice of going with company one.
It is only in the one scenario that that we have where.
S, where the second company is doing really great.
Then is expected utility from going without company 0.9, because that's the
chances of getting funding in this case. And in that case he would prefer.
The changes in opinion and go with c2. But that happens with very little
probability, it only happens with probability with 0.1 and so that means
that the value of information here is going to be very low, because although
there is a situation in which the agent changes his mind, it is an unlikely
scenario. And, sure enough if you look at the
expected utility in the influence diagram with that edge that I just added.
It only goes up from 0.7 to 0.743 which means that the agent shouldn't be willing
to pay his [INAUDIBLE] company too much money in order to get information about
the detail. 'Kay, now let's look at a slightly
different situation. Where now, neither company's doing so
great. So, you can see that now company one is
also kind of this sort of rocky start-up without a very good management structure
and a, and an unclear business model. In this case, what happens?
So once again we can compute the expected utility of the two actions and now we can
see that the expected utility of choosing company one is 0.35 as compared to the
expected utility of company two which is 0.33.
So now decisions are much more finely balanced, relative to each other and so
you would think that there would be a much higher value of information to be
gained because the chances that the agent would change his mind are considerably
larger so let's work our way through that.
And see that once again if we consider adding this edge from the mole in company
two, we can now see that the agent is going to want to change his mind either
when he observes s2 or when he observes s3, because both of these, both 0.4 and
0.9 are larger than, than the expected utility he expects from sticking with
company one. And now indeed the expected utility goes
up, in the case where we have this influent diagram.
And it goes up to 0.43, which is a much more significant increase in their
expected utility relative to what we had before.
Because now there is more value to the information.
We change the agent changes their opinion in two out of three scenarios.
And that's zero. What happens with probability 0.6.
Now let's look at. Yet a third scenario where now we've
changed the probability that the company gets funded.
Now we're back in the bubble days of the Internet boom, and basically, pretty much
every company gets funded with a, pretty high probability, even if their business
model is totally dubious. And in this case, what happens.
So now we can once again compute the expected utility of C1 which is 0.788 the
expected utility of C2 which is 0.779 and we can see that again these expected
utilities are really close to each other. And intuitively what that's going to mean
is that even if the agent changes their mind.
It doesn't make much of a difference in terms of their expected utility.
So, here we see that because of. In this case, we can see that 0.8, which
is their expected utility in the case of the observed s two.
This value S2 is zero is bigger than 0.788, and so they're going to pick.
They're going to decide to change their mind.
And go from C1 to C2 and similarly for S3 but the actual utility gains in this case
are fairly small and so now the utility, the expected utility that we have in this
scenario where, where the edge didn't get observe this variable without before
making a decision is zero point. 8412, which is only a fairly small
increase over the 0.788 that they could have guaranteed themselves without making
that observation, so once again this is a case where the poor mole in company two
doesn't get that much money. So, to summarize, influence diagrams
provide a very clear and elegant interpretation for what it means to make
an observation. As simply the val-, the difference in the
expected utility values, or the NEU values, rather.
Between two influence diagrams. And this allows us to provide a concrete
intuition about when information is valuable.
And that is only and exactly when it induces a change in the action in at
least one context. And now quantitatively it means that, the
extent in which information is valuable, depends on both how much my utility
improves based on that change, and on how likely the context are in which I changed
the decision.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
