1 1 How to Use Probabilities The Crash Course 600.465 – Intro to NLP – J. Eisner 2 Goals of this lecture •Probability notation like p(X | Y): – What does this expression mean? – How can I manipulate it? – How can I estimate its value in practice? • Probability models: – What is one? – Can we build one for language ID? – How do I know if my model is any good? 600.465 – Intro to NLP – J. Eisner 3 3 Kinds of Statistics • descriptive: mean Hopkins SAT (or median) • confirmatory: statistically significant? • predictive: wanna bet? this course – why? Fugue for Tinhorns • Opening number from Guys and Dolls – 1950 Broadway musical about gamblers – Words & music by Frank Loesser • Video: http://www.youtube.com/watch?v=NxAX74gM8DY • Lyrics: http://www.lyricsmania.com/fugue_for_tinhorns_lyrics_guys_and_dolls.html 600.465 – Intro to NLP – J. Eisner 4 600.465 – Intro to NLP – J. Eisner 5 probability model Notation for Greenhorns “Paul Revere” p(Paul Revere wins | weather’s clear) = 0.9 0.9 600.465 – Intro to NLP – J. Eisner 6 What does that really mean? p(Paul Revere wins | weather’s clear) = 0.9 • Past performance? – Revere’s won 90% of races with clear weather • Hypothetical performance? – If he ran the race in many parallel universes … • Subjective strength of belief? – Would pay up to 90 cents for chance to win $1 • Output of some computable formula? – Ok, but then which formulas should we trust? p(X | Y) versus q(X | Y)2 600.465 – Intro to NLP – J. Eisner 7 p is a function on sets of “outcomes” weather’s clear Paul Revere wins All Outcomes (races) p(win | clear)  p(win, clear) / p(clear) 600.465 – Intro to NLP – J. Eisner 8 p is a function on sets of “outcomes” weather’s clear Paul Revere wins All Outcomes (races) p(win | clear)  p(win, clear) / p(clear) syntactic sugar predicate selecting races where weather’s clear logical conjunction of predicates p measures total probability of a set of outcomes (an “event”). 600.465 – Intro to NLP – J. Eisner 9 Required Properties of p (axioms) weather’s clear Paul Revere wins All Outcomes (races) •p() = 0 p(all outcomes) = 1 • p(X)  p(Y) for any X  Y • p(X) + p(Y) = p(X  Y) provided X Y= e.g., p(win & clear) + p(win & ¬clear) = p(win) most of the p measures total probability of a set of outcomes (an “event”). 600.465 – Intro to NLP – J. Eisner 10 Commas denote conjunction p(Paul Revere wins, Valentine places, Epitaph shows | weather’s clear) what happens as we add conjuncts to left of bar ? • probability can only decrease • numerator of historical estimate likely to go to zero: # times Revere wins AND Val places… AND weather’s clear # times weather’s clear 600.465 – Intro to NLP – J. Eisner 11 Commas denote conjunction p(Paul Revere wins, Valentine places, Epitaph shows | weather’s clear) p(Paul Revere wins | weather’s clear, ground is dry, jockey getting over sprain, Epitaph also in race, Epitaph was recently bought by Gonzalez, race is on May 17, … ) what happens as we add conjuncts to right of bar ? • probability could increase or decrease • probability gets more relevant to our case (less bias) • probability estimate gets less reliable (more variance) # times Revere wins AND weather clear AND … it’s May 17 # times weather clear AND … it’s May 17 600.465 – Intro to NLP – J. Eisner 12 p(Paul Revere wins | weather’s clear, ground is dry, jockey getting over sprain, Epitaph also in race, Epitaph was recently bought by Gonzalez, race is on May 17, … ) Simplifying Right Side: Backing Off not exactly what we want but at least we can get a reasonable estimate of it! (i.e., more bias but less variance) try to keep the conditions that we suspect will have the most influence on whether Paul Revere wins3 600.465 – Intro to NLP – J. Eisner 13 p(Paul Revere wins, Valentine places, Epitaph shows | weather’s clear) Simplifying Left Side: Backing Off NOT ALLOWED! but we can do something similar to help … 600.465 – Intro to NLP – J. Eisner 14 p(Revere, Valentine, Epitaph | weather’s clear) = p(Revere | Valentine, Epitaph, weather’s clear) * p(Valentine | Epitaph, weather’s clear) * p(Epitaph | weather’s clear) Factoring Left Side: The Chain Rule True because numerators cancel against denominators Makes perfect sense when read from bottom to top RVEW/W = RVEW/VEW * VEW/EW * EW/W Epitaph? Valentine? Revere? no 2/3 yes 1/3 no 4/5 yes 1/5 no 3/4 yes 1/4 Revere? Valentine? Revere? Revere? Epitaph, Valentine, Revere? 1/3 * 1/5 * 1/4 600.465 – Intro to NLP – J. Eisner 15 p(Revere, Valentine, Epitaph | weather’s clear) = p(Revere | Valentine, Epitaph, weather’s clear) * p(Valentine | Epitaph, weather’s clear) * p(Epitaph | weather’s clear) Factoring Left Side: The Chain Rule True because numerators cancel against denominators Makes perfect sense when read from bottom to top Moves material to right of bar so it can be ignored RVEW/W = RVEW/VEW * VEW/EW * EW/W If this prob is unchanged by backoff, we say Revere was CONDITIONALLY INDEPENDENT of Valentine and Epitaph (conditioned on the weather’s being clear). Often we just ASSUME conditional independence to get the nice product above. 600.465 – Intro to NLP – J. Eisner 16 p(Revere | Valentine, Epitaph, weather’s clear) Factoring Left Side: The Chain Rule If this prob is unchanged by backoff, we say Revere was CONDITIONALLY INDEPENDENT of Valentine and Epitaph (conditioned on the weather’s being clear). yes clear? no 3/4 yes 1/4 no 3/4 yes 1/4 no 3/4 yes 1/4 yes Epitaph? Valentine? Revere? no yes no yes Revere? Valentine? Revere? Revere? no 3/4 yes 1/4 no irrelevant conditional independence lets us use backed-off data from all four of these cases to estimate their shared probabilities “Courses in handicapping [i.e., estimating a horse's odds] should be required, like composition and Western civilization, in our universities. For sheer complexity,