11Machine LearningCS6375 --- Spring 2015aBayesian Learning (I)2Uncertainty• Most real-world problems deal with uncertain information– Diagnosis: Likely disease given observed symptoms– Equipment repair: Likely component failure given sensor reading– Cannot be represented by deterministic rulesHeadache => Fever• Correct framework for representing uncertainty: Probability23Probability• P(A) = Probability of event A = fraction of all possibleworlds in which A is true.4Probability35Probability• Immediately derived propertiesMore generally:IF we know that exactly one of B1, B2..., Bnare true (i.e., P(B1or B2or ... Bn) = 1, and for all i, j unequal, P(Biand Bj) = 0) THEN we know:P(A) = P(A, B1) + P(A, B2) + ... P(A, Bn)6Probability• A random variable is a variable X that can take valuesx1,..,xnwith a probability P(X= xi) attached to each i = 1,..,n47ExampleMy mood can take one of two values: Happy, Sad.The weather can take one of three values: Rainy, Sunny Cloudy.GivenP(Mood=Happy ^ Weather=Rainy ) = 0.2P(Mood=Happy ^ Weather=Sunny ) = 0.1P(Mood=Happy ^ Weather=Cloudy ) = 0.4Can I compute P(Mood=Happy)?Can I compute P(Mood=Sad)?Can I compute P(Weather=Rainy) ?8Conditional Probability• P(A|B) = Fraction of those worlds in which B is true for which A is also true.59Conditional Probability Example• H = Headache P(H) = 1/2• F = Flu P(F) = 1/8P(H|F) = (Area of “H and F” region)(Area of F region)P(H|F) = P(H,F)/P(F)P(H|F) = 1/210Conditional Probability• Definition:• Chain rule:Can you prove that P(A, B) <= P(A) for any events A and B?What can you say about P(A|B) comparing to P(A)?611Conditional Probability• Other useful relations:12Probabilistic Inference• What is the probability that F is true given H is true? Given• P(H) = 1/2• P(F) = 1/8• P(H|F) = 0.5713Probabilistic Inference• Correct reasoning:• We know P(H), P(F), P(H|F) and the two chain rules:• Substituting the values:14Bayes Rule815Bayes Rule16Bayes Rule• What if we do not know P(A)???• Use the relation:• More general Bayes rule:917Bayes Rule• Same rule for a non-binary random variable, except we need to sum over all the possible events18Generalizing Bayes RuleIf we know that exactly one of A1, A2, ..., Anare true, then:P(B) = P(B|A1)P(A1) + P(B|A2)P(A2) + ... + P(B|An) P(An)and in generalP(B|X) = P(B|A1,X)P(A1|X) + ... + P(B|An,X) P(An|X)So∑=iiikkkXABPXAPXABPXAPXBAP),|()|(),|()|(),|(1019Medical DiagnosisA doctor knows that meningitis causes a stiff neck 50% of the time.The doctor knows that if a person is randomly selected from the US population, there’s a 1/50,000 chance the person will have meningitis.The doctor knows that if a person is randomly selected from the US population, there’s a 5% chance the person will have a stiff neck.You walk into the doctor complaining of the symptom of a stiff neck. What’s the probability that the underlying cause is meningitis?20Joint DistributionJoint Distribution Table• Given a set of variables A,B,C,….• Generate a table with all the possible combinations ofassignments to the variables in the rows• For each row, list the corresponding joint probability• For M binary variables size 2M1121Using the Joint DistributionCompute the probabilityof event E:22Inference Using the Joint DistributionGiven that event E1occurs,what is the probability that E2occurs:1223Inference Using the Joint Distribution24Inference• General view: I have some evidence (Headache) how likely is a particular conclusion (Fever)1325Generating the Joint Distribution• Three possible ways of generating the joint distribution:1. Human experts 2. Using known conditional probabilities (e.g.,if we know P(C|A,B), P(B|A), and P(A), weknow P(A,B,C) = P(C|A,B)P(B|A)P(A) ….)3. Learning from data26Learning the Joint DistributionSuppose that we have recorded a lot of training data:The entry for P(A,B,~C) in the table is:1427Learning the Joint DistributionSuppose that we have recorded a lot of training data:More generally, the entry for P(E) in the table is:28Real-Life Joint Distribution• UCI Census DatabaseP(Male|Poor) = 0.4654/0.7604 = 0.6121529So Far …• Basic probability concepts• Bayes rule• What are joint distributions• Inference using joint distributions• Learning joint distributions from data• Problem: If we have M variables, we need 2Mentries inthe joint distribution table An independence assumption leads to an efficient way to learn and to do inference• Problem: estimate probabilities30Independence• A and B are independent iff:• In words: Knowing B does not affect how likely we thinkthat A is true1631Key Properties• Symmetry:• Joint distribution:• Independence of complements:32Independence• Suppose that A, B, C are independent• Then any value of the joint distribution can be computed easily:• In fact, we need only M numbers instead of 2Mfor binary variables!!1733Independence: General Case• If X1,..,XMare independent variables:• Under the independence assumption, we can compute any value of the joint distribution• We can answer any inference query• How do we learn the distributions? Similar to earlier slides on joint distributions34Learning with the Independence Assumption• Learning the distributions from data is simple and efficient• In practice, the independence assumption may not be met but it is often a very useful approximation1835So Far …• Basic probability concepts• Bayes rule• What are joint distributions• Inference using joint distributions• Learning joint distributions from data• Independence assumption• Problem: We now have the joint distribution.How can we use it to make decision Bayes Classifier36Note about Probability EstimationSo far we have been using relative frequencies to approximate probability of an event We will discuss more probability estimation laterNuCfu)(=1937Three Prisoner ProblemThree prisoners, A, B, and C, are locked in their cells. One of them will be executed the next day and others will be released. Only the governor knows which one will be executed. Prisoner A asked the governor to tell him which one of B and C will be released, and got the answer of B. Now what is the chance that A thinks he will be executed? 38Monty Hall ProblemSuppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another
View Full Document
Unlocking...