ProbabilisticGraphical ModelsLecture 1 – IntroductionCS/CNS/EE 155Andreas Krause22One of the most exciting advances in machine learning (AI, signal processing, coding, control, …) in the last decades33How can we gainglobal insight based onlocal observations?4Key idea:Represent the world as a collection of random variables X1, … Xnwith joint distribution P(X1,…,Xn)Learn the distribution from dataPerform “inference” (compute conditional distributions P(Xi| X1= x1, …, Xm= xm)45ApplicationsNatural Language Processing56Speech recognitionInfer spoken words from audio signals“Hidden Markov Models”6Y1Y2Y3Y4Y5Y6PhonemeX1X2X3X4X5X6Words“He ate the cookies on the couch”7Natural language processing7“He ate the cookies on the couch”X1X2X3X4X5X6X78Natural language processingNeed to deal with ambiguity!Infer grammatical function from sentence structure“Probabilistic Grammars”8“He ate the cookies on the couch”X1X2X3X4X5X6X79Evolutionary biologyReconstruct phylogenetic tree from current species (and their DNA samples)9ACCGTA.. CCGAA.. CCGTA.. GCGGCT.. GCAATT.. GCAGTT..[Friedman et al.]10ApplicationsComputer Vision101111Image denoising1212Image denoisingX1X4X7X2X5X8X3X6X9Y1Y4Y7Y2Y5Y8Y3Y6Y9Markov Random FieldXi: noisy pixelsYi: “true” pixels13Make3DInfer depth from 2D images“Conditional random fields”1314ApplicationsState estimation1415Robot localization & mapping15Infer both location and map from noisy sensor dataParticle filtersD. Haehnel, W. Burgard, D. Fox, and S. Thrun. IROS-03.16Activity recognition16Predict “goals” from raw GPS data“Hierarchical Dynamical Bayesian networks”L. Liao, D. Fox, and H. Kautz. AAAI-041717Traffic monitoringDeployedsensors,high accuracyspeed dataWhat about148thAve?How can we get accurate road speed estimates everywhere?Detector loopsTraffic cameras1818s1s2s3s4s5s7s6s11s12s9s10s8Cars as a sensor network[Krause, Horvitz et al.](Normalized) speeds as random variablesJoint distribution allows modeling correlationsCan predict unmonitoredspeeds from monitored speeds using P(S5| S1, S9)s1s3s12s919ApplicationsStructure Prediction1920Collaborative Filtering and Link PredictionPredict “missing links”, ratings…“Collective matrix factorization”, Relational models20L. BrouwerT. Riley21Analyzing fMRI dataPredict activation patterns for nounsPredict connectivity(Pittsburgh Brain Competition)21Mitchell et al.,Science, 200822Other applicationsCoding (LDPC codes, …)Medical diagnosisIdentifying gene regulatory networksDistributed controlComputer musicProbabilistic logicGraphical games….MANY MORE!!2223Key challenges:How do we… represent such probabilistic models?(distributions over vectors, maps, shapes, trees, graphs, functions…)… perform inference in such models?… learn such models from data?2324Syllabus overviewWe will study Representation, Inference & LearningFirst in the simplest caseOnly discrete variablesFully observed modelsExact inference & learningThen generalizeContinuous distributionsPartially observed models (hidden variables)Approximate inference & learningLearn about algorithms, theory & applications242525OverviewCourse webpagehttp://www.cs.caltech.edu/courses/cs155/Teaching assistant: Pete Trautman([email protected])Administrative assistant: Sheri Garcia([email protected])2626Background & PrerequisitesBasic probability and statisticsAlgorithmsCS 156a or permission by instructorPlease fill out the questionnaire about background (not graded ☺ )Programming assignments in MATLAB.Do we need a MATLAB review recitation?2727CourseworkGrading based on4 homework assignments (one per topic) (40%)Course project (40%)Final take home exam (20%)3 late daysDiscussing assignments allowed, but everybody must turn in their own solutionsStart early! ☺2828Course project“Get your hands dirty” with the course materialImplement an algorithm from the course or a paper you read and apply it to some data setIdeas on the course website (soon)Application of techniques you learnt to your own research is encouragedMust be something new (e.g., not work done last term)2929Project: Timeline and gradingSmall groups (2-3 students)October 19: Project proposals due (1-2 pages); feedback by instructor and TANovember 9: Project milestoneDecember 4: Project report due; poster sessionGrading based on quality of poster (20%), milestone report (20%) and final report (60%)303131Review: ProbabilityThis should be familiar to you…Probability Space (Ω, F, P)Ω: set of “atomic events”F ⊆ 2Ω: set of all (non-atomic) eventsF is a σ-Algebra (closed under complements and countable unions)P: F→ [0,1] probability measureFor ω ∈ F, P(ω) is the probability that event ω happens32Interpretation of probabilitiesPhilosophical debate..Frequentist interpretationP(α) is relative frequency of α in repeated experimentsOften difficult to assess with limited dataBayesian interpretationP(α) is “degree of belief” that α will occurWhere does this belief come from?Many different flavors (subjective, pragmatic, …)Most techniques in this class can be interpreted either way.33Independence of eventsTwo events α,β ∈ F are independent ifA collection S of events is independent, if for any subset α,…,αn∈ S it holds that3334Conditional probabilityLet α, β be events, P(β)>0Then:35Most important rule #1:Let α,…,αnbe events, P(αi)>0Then36Most important rule #2:Let α, β be events with prob. P(α) > 0, P(β) > 0ThenP(α | β) =37Random variablesEvents are cumbersome to work with.Let D be some set (e.g., the integers)A random variable X is a mapping X: Ω → DFor some x ∈ D, we sayP(X = x) = P({ω ∈ Ω: X(ω) = x})“probability that variable X assumes state x”Notation: Val(X) = set D of all values assumed by X.3738ExamplesBernoulli distribution: “(biased) coin flips”D = {H,T}Specify P(X = H) = p. Then P(X = T) = 1-p.Write: X ~ Ber(p);Multinomial distribution: “(biased) m-sided dice”D = {1,…,m}Specify P(X = i) = pi, s.t. ∑ιpi= 1Write: X ~ Mult(p1,…,pm)3839Multivariate distributionsInstead of random variable, have random vectorX(ω) = [X1(ω),…,Xn(ω)]Specify P(X1=x1,…,Xn=xn)Suppose all Xiare Bernoulli variables.How many parameters do we need to specify?3940Rules for random variablesChain ruleBayes’ rule41Marginal distributionsSuppose, X and Y are RVs with distribution P(X,Y)42Marginal distributionsSuppose we have joint distribution P(X1,…,Xn)ThenIf all Xibinary: How many