Exact Maximum Likelihood Estimation for Word Mixtures.ppt

Carnegie Mellon Exact Maximum Likelihood Estimation for Word Mixtures Yi Zhang & Jamie Callan Carnegie Mellon University {yiz, callan }@ cs. cmu . edu Wei Xu NEC C&C Research Lab xw@ ccrl . sj. nec .com Carnegie Mellon Outline u Introduction 1. Why this problems? some retrieval applications 2. Traditional solutions: EM algorithm u New algorithm: exact MLE estimation u Experimental Results Carnegie Mellon Query Q D?) ||( DQD?? Document D Results Feedback Docs F={d 1, d 2 , …, d n} ),(' FQQf???? Q? F? Example 1: Model-based Feedback in the Language Modeling Approach to IR Based on Zhai &Lafferty ’ s slides in CIKM 2001 Carnegie Mellon ? F Estimation based on Generative Mixture Model ww F={d 1,…,d n} ))|()|() log(( );()|( logCwpwpdwcFp iw i????????? 1)|( log max arg???Fp F? Maximum Likelihood P(w| ?) P(w| C) ?1-? P(source) Background words Topic words Based on Zhai &Lafferty ’ s slides in CIKM 2001 Given: F, P(w|c) and ? Find: MLE of ? Carnegie Mellon M T : ? Topic M E : ? general English M I : ? new ? E? T? new Example 2: Model-based Approach for Novelty Detection in Adaptive Information Filtering Based on Zhang& Callan ’s paper in SIGIR 2002 Given: ? general English, ? Topic ? E ? T ? new Find: MLE of ? new Carnegie Mellon Problem Setting and Traditional Solution Using EM u Observe : data generated by a mixture multinomial distribution r=(r 1, r 2, r 3, …, r k) u Given: interpolation weights ? and ?, another multinomial distribution p =(p 1, p 2, p 3, …, p k) u Find: the maximum likelihood estimation (MLE) of multinomial distribution q =(q 1, q 2, q 3, …, q k) u Traditional solution: EM algorithm l Iterative process which can putationally expensive l Only provide approximate solution qpr???? Carnegie Mellon Finding q (1) ????? ki iiiqqq qqqqpf LL q k k1 ) ,..., ,( ) ,..., ,() log( max arg max arg 21 21?? Under the constraints: 0 and 1 1???? i ki iqq Where: f i is observed frequency of word i Carnegi