11School of Computer ScienceApplications in IR⎯ Probabilistic Topic Models Probabilistic Graphical Models (10Probabilistic Graphical Models (10--708)708)Lecture 22, Dec 3, 2007Eric XingEric XingReceptor AKinase CTF FGene GGene HKinase EKinase DReceptor BX1X2X3X4X5X6X7X8Receptor AKinase CTF FGene GGene HKinase EKinase DReceptor BX1X2X3X4X5X6X7X8X1X2X3X4X5X6X7X8Reading: Eric Xing 2NLP and Data MiningWe want:z Semantic-based search z infer topics and categorize documentsz Multimedia inferencez Automatic translation z Predict how topics evolvez …Researchtopics19002000Researchtopics190020002Eric Xing 3This Talkz A graphical model primerz Two families of probabilistic topics models and approximate inferencez Bayesian admixture modelsz Random modelsz Three applicationsz Topic evolutionz Machine translationz Multimedia inference Eric Xing 4How to Model Semantic?z Q: What is it about?z A: Mainly MT, with syntax, some learningA Hierarchical Phrase-Based Model for Statistical Machine TranslationWe present a statistical phrase-based Translation model that uses hierarchical phrases—phrases that contain sub-phrases. The model is formally a synchronous context-free grammar but is learned from a bitext without any syntactic information. Thus it can be seen as a shift to the formal machinery of syntaxbased translation systems without any linguistic commitment. In our experimentsusing BLEU as a metric, the hierarchical Phrase based model achieves a relative Improvement of 7.5% over Pharaoh, a state-of-the-art phrase-based system.SourceTargetSMTAlignmentScoreBLEUParseTreeNounPhraseGrammarCFGlikelihoodEMHiddenParametersEstimationargMaxMT Syntax Learning0.6 0.3 0.1 Unigram over vocabularyTopicsMixing ProportionTopic Models3Eric Xing 5Why this is Useful?z Q: What is it about?z A: Mainly MT, with syntax, some learningA Hierarchical Phrase-Based Model for Statistical Machine TranslationWe present a statistical phrase-based Translation model that uses hierarchical phrases—phrases that contain sub-phrases. The model is formally a synchronous context-free grammar but is learned from a bitext without any syntactic information. Thus it can be seen as a shift to the formal machinery of syntaxbased translation systems without any linguistic commitment. In our experimentsusing BLEU as a metric, the hierarchical Phrase based model achieves a relative Improvement of 7.5% over Pharaoh, a state-of-the-art phrase-based system.MT Syntax LearningMixing Proportion0.6 0.3 0.1 z Q: give me similar document?z Structured way of browsing the collectionz Other tasksz Dimensionality reduction z TF-IDF vs. topic mixing proportionz Classification, clustering, and more …Eric Xing 6Words in Contextsz “It was a nice shot. ”4Eric Xing 7Words in Contexts (con'd)z the opposition Labor Party fared even worse, with a predicted 35 seats, seven less than last election.Eric Xing 8"Words" in Contexts (con'd)Sivic et al. ICCV 20055Eric Xing 9Topic Models: The Big PictureUnstructured CollectionStructured Topic NetworkTopic DiscoveryDimensionality Reductionw1w2wnxxxxT1TkT2xxxxWord SimplexTopic Space (e.g, a Simplex)Eric Xing 10Method One:zzHierarchical Bayesian AdmixtureHierarchical Bayesian AdmixtureA. Ahmed and E.P. XingA. Ahmed and E.P. XingAISTAT 2007AISTAT 20076Eric Xing 11z Objects are bags of elementsz Mixtures are distributions over elementsz Objects have mixing vector θz Represents each mixtures’ contributionsz Object is generated as follows:z Pick a mixture component from θz Pick an element from that componentAdmixture Modelsmoney1 bank1 bank1 loan1 river2 stream2 bank1 money1 river2 bank1 money1 bank1 loan1 money1 stream2 bank1 money1 bank1 bank1 loan1 river2 stream2 bank1 money1 river2 bank1 money1 bank1 loan1 bank1 money1 stream2 money1 bank1 bank1 loan1 river2 stream2 bank1 money1 river2 bank1 money1 bank1 loan1 money1 stream2 bank1 money1 bank1 bank1 loan1 river2 stream2 bank1 money1 river2 bank1 money1 bank1 loan1 bank1 money1 stream2 money1 bank1 bank1 loan1 river2 stream2 bank1 money1 river2 bank1 money1 bank1 loan1 money1 stream2 bank1 money1 bank1 bank1 loan1 river2 stream2 bank1 money1 river2 bank1 money1 bank1 loan1 bank1 money1 stream2 …0.1 0.10.5…..0.1 0.50.1…..0.5 0.10.1…..money1 bank1 bank1 loan1 river2 stream2 bank1 money1 river2 bank1 money1 bank1 loan1 money1 stream2 bank1 money1 bank1 bank1 loan1 river2 stream2 bank1 money1 river2 bank1 money1 bank1 loan1 bank1 money1 stream2 Eric Xing 12Topic Models =Admixture ModelsGenerating a documentPriorθz w βNdN K (){}() from ,| Draw - from Draw- each wordFor prior thefrom :1nzknnnlmultinomiazwlmultinomiaznDrawββθθ−Which prior to use?7Eric Xing 13Prior Comparisonz Dirichlet (LDA) (Blei et al. 2003)z Conjugate prior means efficient inferencez Can only capture variations in each topic’s intensity independentlyz Logistic Normal (CTM=LoNTAM) (Blei & Lafferty 2005, Ahmed & Xing 2006)z Capture the intuition that some topics are highly correlated and can rise up in intensity togetherz Not a conjugate prior implies hard inferenceEric Xing 14)|}{,( DzPθβθzwµ ΣLog Partition Function 1log11⎟⎠⎞⎜⎝⎛+∑−=Kiieγ()() ()∏Σ=nnnzqqzqφµγγ**,,:1γzwµ* Σ* φβAhmed&XingΣ* is full matrixMultivariateQuadratic Approx.Closed Form Solution for µ*, Σ*Blei&LaffertyΣ* is assumed to be diagonalTangent Approx.Numerical Optimization to fit µ*, Diag(Σ*)Approximate Inference (e.g., MF, Jordan et al 1999, GMF, Xing et al 2004)8Eric Xing 15Variational Inference)|,(:1DzPnγβγzwµΣ()pqKLnminarg**,*,:1φµΣOptimization ProblemApproximate the PosteriorApproximate the IntegralSolveµ*,Σ*,φ1:n* ()() ()∏Σ=nnnzqqzqφµγγ**,,:1γzwµ* Σ* Φ* βEric Xing 16Variational Inference With no Tearsz Pretend you know E[Z1:n]z P(γ|E[z1:n], µ, Σ)z Now you know E[γ]z P(z1:n|E[γ], w1:n, β1:k))|}{,( DzPγβγzwµ ΣIterate until ConvergenceMessage Passing Scheme (GMF)Equivalent to previous method (Xing et. al.2003)z More Formally:()⎟⎠⎞⎜⎝⎛∈∀=MBqYCCXySXPXqy:*9Eric Xing 17LoNTAM Variations Inference()() ()∏=nnzqqzqγγ:1,z Fully Factored Distribution()()()∏=nnzqqzqγγ:1,)|}{,( DzPγβγzwµ Σz Two clusters: λ and Z1:n()⎟⎠⎞⎜⎝⎛∈∀=MBqYCCXySXPXqy:*z Fixed Point
View Full Document