I have been reading a paper: Wang X, Golbandi N, Bendersky M, Metzler D, Najork M. Position bias estimation for unbiased learning to rank in personal search.I am wondering how they derive the M-step in an EM algorithm that has been applied to the problem in their paper.This is the data log-likelihood function: log ⁡ P ( L ) = ∑ ( c , q , d , k ) ∈ L c log ⁡ θ k γ q , d + ( 1 − c ) log ⁡ ( 1 − θ k γ q , d ) .where observed data are (c:click, q:query, d:document, k:result position) rows, and θ k is the probability a search result at rank k is examined by the user (assumed to be independent of query-document pair), and γ q , d is the probability a search result, i.e., a query-document pair is actually relevant (assumed to be independent of result position).Here are some hidden variable probability expressions (E means examination and R means relevant, they assume that a click event implies a search result is both examined and relevant): P ( E = 1 , R = 1 ∣ C = 1 , q , d , k ) = 1 P ( E = 1 , R = 0 ∣ C = 0 , q , d , k ) = θ k ( t ) ( 1 − γ q , d ( t ) ) 1 − θ k ( t ) γ q , d ( t ) P ( E = 0 , R = 1 ∣ C = 0 , q , d , k ) = ( 1 − θ k ( t ) ) γ q , d ( t ) 1 − θ k ( t ) γ q , d ( t ) P ( E = 0 , R = 0 ∣ C = 0 , q , d , k ) = ( 1 − θ k ( t ) ) ( 1 − γ q , d ( t ) ) 1 − θ k ( t ) γ q , d ( t ) The paper has derived the M-step update formulas: θ k ( t + 1 ) = ∑ c , q , d , k ′ I k ′ = k ⋅ ( c + ( 1 − c ) P ( E = 1 ∣ c , q , d , k ) ) ∑ c , q , d , k ′ I k ′ = k γ q , d ( t + 1 ) = ∑ c , q ′ , d ′ , k I q ′ = q , d ′ = d ⋅ ( c + ( 1 − c ) P ( R = 1 ∣ c , q , d , k ) ) ∑ c , q ′ , d ′ , k , I q ′ = q , d ′ = d however, how to get these two formulas?Note: M-step is usually derived from this formula: Q ( θ ∣ θ ( t ) ) = E Z ∣ X , θ ( t ) ⁡ [ log ⁡ L ( θ ; X , Z ) ] θ ( t + 1 ) = a r g m a x θ Q ( θ ∣ θ ( t ) ) where θ are parameters (i.e., θ k and γ q , d in this case), X are data (c,q,d,k in this case), and Z are hidden variables (E and R?).

Question

I have been reading a paper: Wang X, Golbandi N, Bendersky M, Metzler D, Najork M. Position bias estimation for unbiased learning to rank in personal search.I am wondering how they derive the M-step in an EM algorithm that has been applied to the problem in their paper.This is the data log-likelihood function:  log  ⁡  P  (      L    )  =      ∑          (      c      ,      q      ,      d      ,      k      )      ∈              L              c  log  ⁡      θ          k            γ          q      ,      d        +  (  1  −  c  )  log  ⁡      (    1    −          θ              k                    γ              q        ,        d              )    .where observed data are (c:click, q:query, d:document, k:result position) rows, and       θ          k       is the probability a search result at rank k is examined by the user (assumed to be independent of query-document pair), and       γ          q      ,      d       is the probability a search result, i.e., a query-document pair is actually relevant (assumed to be independent of result position).Here are some hidden variable probability expressions (E means examination and R means relevant, they assume that a click event implies a search result is both examined and relevant):                    P        (        E        =        1        ,        R        =        1        ∣        C        =        1        ,        q        ,        d        ,        k        )        =        1                            P        (        E        =        1        ,        R        =        0        ∣        C        =        0        ,        q        ,        d        ,        k        )        =                                            θ                              k                                            (                t                )                                                    (              1              −                              γ                                  q                  ,                  d                                                  (                  t                  )                                            )                                            1            −                          θ                              k                                            (                t                )                                                    γ                              q                ,                d                                            (                t                )                                                                        P        (        E        =        0        ,        R        =        1        ∣        C        =        0        ,        q        ,        d        ,        k        )        =                                            (              1              −                              θ                                  k                                                  (                  t                  )                                            )                                      γ                              q                ,                d                                            (                t                )                                                          1            −                          θ                              k                                            (                t                )                                                    γ                              q                ,                d                                            (                t                )                                                                        P        (        E        =        0        ,        R        =        0        ∣        C        =        0        ,        q        ,        d        ,        k        )        =                                            (              1              −                              θ                                  k                                                  (                  t                  )                                            )                                      (              1              −                              γ                                  q                  ,                  d                                                  (                  t                  )                                            )                                            1            −                          θ                              k                                            (                t                )                                                    γ                              q                ,                d                                            (                t                )                                                        The paper has derived the M-step update formulas:                              θ                      k                                (            t            +            1            )                          =                                            ∑                              c                ,                q                ,                d                ,                                  k                                      ′                                                                                                      I                                                              k                                      ′                                                  =                k                                      ⋅            (            c            +            (            1            −            c            )            P            (            E            =            1            ∣            c            ,            q            ,            d            ,            k            )            )                                              ∑                              c                ,                q                ,                d                ,                                  k                                      ′                                                                                                      I                                                              k                                      ′                                                  =                k                                                                                  γ                      q            ,            d                                (            t            +            1            )                          =                                            ∑                              c                ,                                  q                                      ′                                                  ,                                  d                                      ′                                                  ,                k                                                                    I                                                              q                                      ′                                                  =                q                ,                                  d                                      ′                                                  =                d                                      ⋅            (            c            +            (            1            −            c            )            P            (            R            =            1            ∣            c            ,            q            ,            d            ,            k            )            )                                              ∑                              c                ,                                  q                                      ′                                                  ,                                  d                                      ′                                                  ,                k                ,                                                                    I                                                              q                                      ′                                                  =                q                ,                                  d                                      ′                                                  =                d                                                        however, how to get these two formulas?Note: M-step is usually derived from this formula:            Q      (              θ            ∣                        θ                          (          t          )                    )      =              E                              Z                    ∣                      X                    ,                                    θ                                      (              t              )                                          ⁡              [        log        ⁡        L        (                  θ                ;                  X                ,                  Z                )        ]                                                θ                          (          t          +          1          )                    =                                    a            r            g                        m            a            x                    θ                           Q      (              θ            ∣                        θ                          (          t          )                    )            where θ are parameters (i.e.,       θ          k       and       γ          q      ,      d       in this case), X are data (c,q,d,k in this case), and Z are hidden variables (E and R?).

Emmy Sparks · Accepted Answer

Actually, I have found how to reach those updated formulas, although the final form looks a bit different, I am happy to share here in case anyone can find out why.First, write Q function in more separated cases:  Q  (      θ    k    ,      γ          q      ,      k        ∣      θ    k          (      t      )        ,      γ          q      ,      k              (      t      )        )  =      ∑          X      =      c      ,      q      ,      d      ,      k                  [        P  (  E  =  1  ,  R  =  1  ∣  C  =  1  ,  q  ,  d  ,  k  )  ⋅  c  ⋅  log  ⁡  (      θ    k        γ          q      ,      d        )  +  P  (  E  =  1  ,  R  =  0  ∣  C  =  0  ,  q  ,  d  ,  k  )  ⋅  (  1  −  c  )  ⋅  log  ⁡  (      θ    k    (  1  −      γ          q      ,      d        )  )  +  P  (  E  =  0  ,  R  =  1  ∣  C  =  0  ,  q  ,  d  ,  k  )  ⋅  (  1  −  c  )  ⋅  log  ⁡  (  (  1  −      θ    k    )      γ          q      ,      d        )  +  P  (  E  =  0  ,  R  =  0  ∣  C  =  0  ,  q  ,  d  ,  k  )  ⋅  (  1  −  c  )  ⋅  log  ⁡  (  (  1  −      θ    k    )  (  1  −      γ          q      ,      d        )  )            ]      Then simply take the derivatives:  0  =            ∂              ∂                  θ          k                      Q  (      θ    k    ,      γ          q      ,      k        ∣      θ    k    ′    ,      γ          q      ,      k        ′    )The final theta update rule looks like      θ    k          (      t      +      1      )        =  c  +  P  (  E  =  1  ,  R  =  0  ∣  C  =  0  ,  q  ,  d  ,  k  )  ⋅  (  1  −  c  )

I have been reading a paper: Wang X, Golbandi N, Bendersky M, Metzler D, Najork M. Position bias est

Answered question

Answer & Explanation

New Questions in Pre-Algebra