New version page

Lecture

Upgrade to remove ads

This preview shows page 1-2-16-17-18-34-35 out of 35 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

1Eric Xing, A lecture series at the Institute of Theoretical Computer Science, Tsinghua University, May 31-June 7, 20071School of Computer ScienceGraphical Models (1)Graphical Models (1)RepresentationRepresentationEric XingEric XingCarnegie Mellon UniversityMay 31, 2007Receptor AKinase CTF FGene GGene HKinaseEKinase DReceptor BX1X2X3X4X5X6X7X8Receptor AKinase CTF FGene GGene HKinaseEKinase DReceptor BX1X2X3X4X5X6X7X8X1X2X3X4X5X6X7X8Eric Xing 22Eric Xing 3What is this?z Classical AI and ML research ignored this phenomena z The Problem (an example): z you want to catch a flight at 10:00am from Beijing to Pittsburgh, can I make it if I leave at 7am and take a Taxi at the east gate of Tsinghua?z partial observability (road state, other drivers' plans, etc.)z noisy sensors (radio traffic reports)z uncertainty in action outcomes (flat tire, etc.)z immense complexity of modeling and predicting trafficz Reasoning under uncertainty!Eric Xing 4A universal task …Speech recognitionSpeech recognitionInformation retrievalInformation retrievalComputer visionComputer visionRobotic controlRobotic controlPlanningPlanningGamesGamesEvolutionEvolutionPedigreePedigree3Eric Xing 5z Representationz How to capture/model uncertainties in possible worlds?z How to encode our domain knowledge/assumptions/constraints?z Inferencez How do I answers questions/queries according to my model and/or based given data?z Learningz What model is "right" for my data?The Fundamental Questions????X1X2X3X4X5X6X7X8X9)|( :e.g. DiXP);( maxarg :e.g. MMMDFM∈=Eric Xing 6Graphical Modelsz Graphical models are a marriage between graph theory and probability theory z One of the most exciting developments in machine learning (knowledge representation, AI, EE, Stats,…) in the last two decades…z Some advantages of the graphical model point of viewz Inference and learning are treated togetherz Supervised and unsupervised learning are merged seamlesslyz Missing data handled nicely z A focus on conditional independence and computational issuesz Interpretability (if desired)z Are having significant impact in science, engineering and beyond!X1X2X3X4X5X6X7X8X94Eric Xing 7What is a Graphical Model?z The informal blurb:z It is a smart way to write/specify/compose/design exponentially-large probability distributions without paying an exponential cost, and at the same time endow the distributions with structured semanticsz A more formal description:z It refers to a family of distributions on a set of random variables that are compatible with all the probabilistic independence propositions encoded by a graph that connects these variablesACFGHEDBACFGHEDBACFGHEDBACFGHEDBACFGHEDB)( 87654321,X,X,X,X,X,X,XX P),()(),( )|()|()|()()()( :6586743625242132181XXXPXXPXXXPXXPXXPXXXPXPXPXP=Eric Xing 8probabilisticprobabilisticgenerativegenerativemodelmodelgene expression profilesgene expression profilesStatistical Inference5Eric Xing 9statisticalstatisticalinferenceinferencegene expression profilesgene expression profilesStatistical InferenceEric Xing 10Receptor AKinase CTF FGene GGene HKinase EKinase DReceptor BX1X2X3X4X5X6X7X8Multivariate Distribution in High-D Spacez A possible world for cellular signal transduction:6Eric Xing 11z Representation: what is the joint probability dist. on multiple variables?z How many state configurations in total? --- 28z Are they all needed to be represented?z Do we get any scientific/medical insight?z Learning: where do we get all this probabilities? z Maximal-likelihood estimation? but how many data do we need?z Where do we put domain knowledge in terms of plausible relationships between variables, and plausible values of the probabilities?zInference: If not all variables are observable, how to compute the conditional distribution of latent variables given evidence?z Computing p(H|A) would require summing over all 26configurations of the unobserved variables),,,,,,,,( 87654321XXXXXXXXPRecap of Basic Prob. ConceptsACFGHEDBACFGHEDBACFGHEDBACFGHEDBEric Xing 12Receptor AKinase CTF FGene GGene HKinase EKinase DReceptor BX1X2X3X4X5X6X7X8What is a Graphical Model?--- example from a signal transduction pathwayz A possible world for cellular signal transduction:7Eric Xing 13Receptor AKinase CTF FGene GGene HKinase EKinase DReceptor BMembraneCytosolNucleusX1X2X3X4X5X6X7X8GM: Structure Simplifies Representationz Dependencies among variablesEric Xing 14 If Xi's are conditionally independent (as described by a PGM), the joint can be factored to a product of simpler terms, e.g., Why we may favor a PGM? Incorporation of domain knowledge and causal (logical) structuresP(X1, X2, X3, X4, X5, X6, X7, X8)= P(X1) P(X2) P(X3| X1) P(X4| X2) P(X5| X2)P(X6| X3, X4) P(X7| X6) P(X8| X5, X6)Probabilistic Graphical ModelsReceptor AKinase CTF FGene GGene HKinase EKinase DReceptor BX1X2X3X4X5X6X7X8Receptor AKinase CTF FGene GGene HKinase EKinase DReceptor BX1X2X3X4X5X6X7X8X1X2X3X4X5X6X7X82+2+4+4+4+8+4+8=36, an 8-fold reduction from 28 in representation cost ! Stay tune for what are these independencies!8Eric Xing 15Receptor AKinase CTF FGene GGene HKinase EKinase DReceptor BXX11XX22XX33XX44XX55XX66XX77XX88Receptor AKinase CTF FGene GGene HKinase EKinase DReceptor BXX11XX22XX33XX44XX55XX66XX77XX88GM: Data IntegrationEric Xing 16 If Xi's are conditionally independent (as described by a PGM), the joint can be factored to a product of simpler terms, e.g.,  Why we may favor a PGM? Incorporation of domain knowledge and causal (logical) structures Modular combination of heterogeneous parts – data fusionProbabilistic Graphical Models2+2+4+4+4+8+4+8=36, an 8-fold reduction from 28 in representation cost ! Receptor AKinase CTF FGene GGene HKinase EKinase DReceptor BXX11XX22XX33XX44XX55XX66XX77XX88Receptor AKinase CTF FGene GGene HKinase EKinase DReceptor BXX11XX22XX33XX44XX55XX66XX77XX88XX11XX22XX33XX44XX55XX66XX77XX88P(X1, X2, X3, X4, X5, X6, X7, X8)= P(X2) P(X4| X2) P(X5| X2) P(X1) P(X3| X1) P(X6| X3, X4) P(X7| X6) P(X8| X5, X6)9Eric Xing 17∑∈′′′=Hhhphdphphdpdhp)()|()()|()|(PosteriorprobabilityLikelihoodPriorprobabilitySum over space of hypothesesRational Statistical InferencehhddThe Bayes Theorem:z This allows us to capture uncertainty about the model in a principled wayz But how can we specify and represent a complicated model?z Typically the number of genes need to be modeled are in the order of thousands!Eric Xing 18GM: MLE and Bayesian Learningz Probabilistic statements ofΘis conditioned on the values of the


Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?