COMP30024 Artificial Intelligence
Week 10 Problem Sheet
Weekly Topic Review
Note: The problems for this week require no specialized knowledge beyond what you have learnt in COMP30024 – the tutorial questions are designed to help you learn how to identify the underlying probabilistic structure of a range of different problems from different domains.
Copyright By PowCoder代写 加微信 powcoder
Conditional Probability
Recall the conditional probability of event A given event B with P(B) > 0 is:
P(A|B) = P(A,B) (1) P(B)
Conditional probability shares the same properties as probability, but P(·|B) updates our uncer- tainty about events to incorporate the information provided (if any) that the event B has occurred – in effect treating B as ”observed data”. Importantly, all probabilities can be thought of as con- ditional probabilities – whenever a statement about probability is made, there is always some prior information we condition on, even if it is so obvious we do not write it down explicitly.
Bayes’ Theorem
In the context of applications to artificial intelligence, Bayes’ Theorem is useful to understand
our uncertainty surrounding some uncertain hypothesis H, given observed data/information X.
P(H|X) = P(X|H)P(H) (2) P(X)
• The likelihood P(X|H) is the conditional probability of the data X given fixed H.
• The prior P(H) represents information we have that is not part of the collected data X –
consider this our pre-existing degree of belief in the hypothesis H before observing any data. 1
• The evidence P(H) is the average over all possible values of H, calculated using the law of total probability:
P(X) = P(X|H = h)P(H = h) h
P(H|X) is the posterior distribution, which represents our updated beliefs around the hypothesis now we have observed the data X. Bayes’ Theorem may also be conveniently expressed in terms of the posterior odds, which circumvents calculation of the evidence p(H):
p(H|X) = P(X|H) · P(H) . (3) p(Hc|X) P (X|Hc) P (Hc)
Note Hc may be replaced with ¬H for binary random variables. Conditional probabilities are prob- abilities as well, so it is straightforward to extend Bayes’ Theorem to incorporate extra conditioning on another event Y , provided P (H |Y ), P (X |Y ) > 0:
P(H|X,Y)= P(X|H,Y)P(H|Y) (4) P(X|Y)
Bayes’ Theorem is an apparently simple consequence of the definition of conditional probability, but has deep consequences. The basic intuition here is that going in one direction e.g. P(X|H) is easier than finding the probability P(H|X) in the other direction1.
1. Under oath [T] You are a witness to a night-time hit-and-run accident involving a taxi in Athens. All taxis in Athens are blue or green. You swear under oath that the taxi was blue. Extensive testing shows that under the dim lighting conditions, discrimination between blue and green is 75% reliable.
(a) Is it possible to calculate the most likely colour for the taxi? (Hint: distinguish carefully between the proposition that the taxi is blue and the proposition that it appears blue.)
(b) What if you are given the extra information that 9 out of 10 Athenian taxis are green?
2. Counterespionage [T] During the Cold War, the United States developed a speech-to-text algorithm to detect hidden dialects of Russian sleeper agents, who were trained to speak English with an American accent in Russia, and sent to the US to gather intelligence.
The method was based on the acoustic properties of Russian pronunciation of the word voksal (Russian for railway), borrowed from the English Vauxhall. The Americans postulated that
1It is usually easier to reason probabilistically about the diagnostic X|H direction as opposed to the causal H|X direction, because X is directly observed.
it was impossible for any Russian to completely hide their accent – when a Russian would say ”Vauxhall”, the speech-to-text algorithm would detect this as ”voksal”.
This method was tested at a diplomatic gala where 20% of the guests were Russian sleeper agents and the remainder Americans. A counterespionage officer uniformly randomly chooses a guest and asks them to say ”Vauxhall”. A single letter is chosen uniformly randomly from the word generated by the speech-to-text algorithm, which is observed to be ”l”. Under these assumptions, what is the probability that the person is a Russian sleeper agent?
3. [T] (Based on Mackay 3.8/3.9 (Mackay, 2003)) On a game show2, the rules are as follows:
There are three doors, labelled 1, 2, 3. A single prize is hidden behind one of them, and goats behind the other two. You get to select one door. Initially your chosen door will not be opened. Instead the gameshow host will open one of the other two doors, and he will do so in a such a way as not to reveal the prize. For example, if you first choose door 1, the host will open either door 2 or door 3, depending on which one does not have the prize behind it.
At this point you will be given a new choice of door – you may either stick with your original choice, or you can switch to the other closed door. All doors will then be opened and you will receive whatever is behind your final choice of door.
(a) Imagine you choose door 1 first, then the host opens door 3, revealing nothing behind the door, as promised. Assuming you want the prize and not the goat, should you (a) stick with door 1, (b) switch to door 2, or (c) does it make no difference?
(b) You are playing the same game as above, but just you have made your choice and the host is about to open one of the doors, a rather violent earthquake rattles the building and one of the three doors flies open. It happens to be door 3, and it happens not to have the prize behind it. You had initially chosen door 1.
Repositioning his toup ́ee, the host suggests, ‘OK, since you chose door 1 initially, door 3 is a valid door for me to open, according to the rules of the game; I’ll let door 3 stay open. Let’s carry on as if nothing happened.’
Should you stick with door 1, switch to door 2, or does it make no difference? Assume that the prize was placed randomly, that the host does not know where it is, and that the door flew open because its latch was broken by the earthquake. Hint: consider carefully whether your optimal decision is based on how the other door to be revealed is selected.
(c) You are again playing the same game as above, but now with N = 1000 doors instead of three. When you pick your initial choice of door, the host opens N − 2 = 998 of the other N − 1 = 999 doors in such a way as to not reveal the prize. Assuming you want the prize, should you stick with your first choice, or switch to the other unopened door?
(d) You are again(!) playing the N doors variant, but just as the host is about to open one of the doors a violent earthquake rattles the building and N − 2 of the other N − 1 doors
2This classic problem derives its name from a game played on Let’s make a deal, hosted by . 3
fly open to reveal N − 1 goats – i.e. the prize is behind either your initial choice of door or the other unopened door. This time, should you stick with your first choice, or switch to the other unopened door? Find an expression for the probability that the prize is behind your initial choice of door as N → ∞.
4. The Prosecutor’s Fallacy [T] In 1998, was tried for murder after two of her sons
died shortly after birth3. During the trial, an expert witness for the prosecution testified that
the probability of a newborn dying of sudden infant death syndrome (SIDS) was 1 , so the 8500
probability of two deaths due to SIDS in one family was 1 2, or about one in 73 million. 8500
Therefore, he continued, the probability of Clark’s innocence was one in 73 million. Identify the two major problems with this line of reasoning (supposing the figures are accurate).
5. The Defense Attorney’s Fallacy [T] A woman has been murdered, and her husband is put on trial for this crime. Evidence comes to light that the defendant had a history of abusing his wife. The defense attorney argues that the evidence of abuse should be excluded on grounds of irrelevance – since, statistically, only 1 in 10,000 men with wives they abuse subsequently murder their wives. Supposing the figures given are accurate4, should the judge grant the motion to bar this evidence from trial? Or is the defense attorney a slimy trickster? If the latter, what is wrong with their argument?
6. Particle physics Every fundamental particle in the universe has a property called ”spin”. This can be described as either integer in which case the particle is a boson, or half-integer, in which case the particle is a fermion. Assume that bosons and fermions occur with equal probability in our universe. A physicist is observing two particles, at least one of which has half-integer spin. Given this information, what is the probability that both particles are fermions?
7. Phone numbers You move into a new house; the phone is connected, and you’re pretty sure that the phone number is 740511, but not as sure as you would like to be. As an experiment, you pick up the phone and dial 740511; you obtain a ‘busy’ signal. Are you now more sure of your phone number? If so, how much? Report the posterior probability ratio of the two hypotheses. (Hint: assume that there are 100000 valid landline numbers in Melbourne, all of which are six digits.)
8. Maybe random Monty [T], [∗] Monty decides to change how he selects the door to be opened in response to the contestant’s initial choice of door. Before each show, Monty secretly flips a coin with probability p of Heads. If the coin lands Heads, Monty resolves to open a door with a goat (with equal probabilities if there is a choice). Otherwise, Monty will open a random door, with equal probabilities. Monty will never open the door that the contestant initially chooses. The contestant knows p but does not know the outcome of the coin flip.
When the show starts, the contestant chooses a door. Monty (who knows where the prize is) then opens a door. If the prize is revealed, the game is over; if a goat is revealed, the contestant
3 https://en.wikipedia.org/wiki/Sally_Clark
4In the USA, it is estimated that 2 million women are abused each year by their partners. In 1994, 4739 women were victims of homicide; of those, 1326 (28%) were perpetrated by male partners.
is offered the option of switching. Without loss of generality, assume that the contestant chooses door 1 and then Monty opens door 2, revealing a goat. Derive an expression in terms of p for the contestant’s probability of success if they switch to door 3. Check your answer agrees with the classic problem in the limiting cases p = 0 and p = 1.
References
David M. Mackay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com