Web-Scale Bayesian Click-Through Rate Prediction for Sponsored Search Advertising in Microsoft s Bing Search Engine Thore Graepel et al., ICML, 2010 Presented by Boyoung Kim April 25, 2018 Boyoung Kim (SNU) April 25, 2018 1 / 12
Sponsored Search Bing 에서의 컴퓨터 검색결과 Boyoung Kim (SNU) April 25, 2018 2 / 12
Sponsored Search Sponsored Search란 광고주가키워드제공하면 검색엔진은광고 ( 웹페이지 ) 를사용자 ( 탐색자 ) 에게제공, 사용자의클릭수에따라광고주에광고비청구하는과정또는구조. 정확한클릭률 (CTR) 추정의중요성 더좋은정보제공을통해사용자만족도를높임 광고주에게더나은거래제시 사용자에게높은클릭률의광고를보여줌으로써수익을올림 Boyoung Kim (SNU) April 25, 2018 3 / 12
Notation 입력변수 이산형변수 N개가있고, i {1,..., N} 번째변수는 M i 개값을갖는다하자. 입력변수는 Sparse binary feature vector로다음과같이나타냄. x := (x T 1,..., x T N ) T 이때, 모든 i {1,..., N} 에대해 x i = (x i,1,..., x i,mi ) T, x i,j {0, 1}, M i j=1 x i,j = 1. ex) 광고주, 광고카테고리, Search 키워드, display 위치, 사용자정보등. 라벨 y { 1, 1}, 여기서 -1 은 non-click, 1 은 click 을나타냄. Boyoung Kim (SNU) April 25, 2018 4 / 12
Bayesian Linear Probit Regression GLM with probit link function ( y w T ) x p(y x, w) := Φ β (1) 여기서 Φ (t) := t N (s; 0, 1)ds, β 는 Hyper parameter. Boyoung Kim (SNU) April 25, 2018 5 / 12
Bayesian Linear Probit Regression Prior : factorizing Gaussian prior distribution 가정 N M i p(w) = N (w i,j ; µ i,j, σi,j) 2 (2) i=1 j=1 Posterior p(w x, y) p(y x, w)p(w) (3) 사후분포의계산이어려워서 approximate message passing algorithm 으로추정 Boyoung Kim (SNU) April 25, 2018 6 / 12
Update Equations for Online learning 업데이트 (µ, σ 2, x, y) ( µ, σ 2 ) µ i,j = µ i,j + yx i,j σ2 i,j Σ v σ 2 i,j = σ 2 i,j [ 1 x i,j σ2 i,j Σ w ( y x T ) µ Σ (4) ( y x T ) ] µ (5) 여기서 Σ 2 := β 2 + x T σ 2 ( 전체변동 ), µ := (µ 1,1,..., µ N,MN ) T, σ 2 := (σ 2 1,1,..., σ2 N,M N ) T, Σ v(t) := N (t; 0, 1) Φ(t; 0, 1), w(t) := v(t) [v(t) + t] Boyoung Kim (SNU) April 25, 2018 7 / 12
Predictive Distribution 예측 p(y x) = ( y x T ) µ = Φ Σ p(y x, w) p(w)dw (6) (7) Boyoung Kim (SNU) April 25, 2018 8 / 12
Some Issues 입력변수 dimension 에따른메모리문제 특정 weight 에대해 pruning(prior 값으로하는것 ) 시킴. prior 분포와 posterior 분포의차이가작으면그 weight 를 prunning 함. Boyoung Kim (SNU) April 25, 2018 9 / 12
Some Issues Exploration & Exploitation Exploration : 새로운광고에대해사용자의반응필요 Exploitation : 이미알려진높은 CTR 의광고보여주길원함. weight 의평균만사용할것이아니라, uncertainty 를부여하여 CTR 을다양하게추정하여노출시킨다. Boyoung Kim (SNU) April 25, 2018 10 / 12
Experiments Display 위치에따른 weight 의사후평균, 분산 광고가 Mainline 에보여질수록, 위쪽에보여질수록평균크고분산작다. Boyoung Kim (SNU) April 25, 2018 11 / 12
Experiments 사용자 ID 에따른 weight 의사후평균, 분산 - 위쪽에있는점은 weight 의 prior 에가까운점들이고, 더아래쪽에있는것은자주관찰되서 prior 로부터멀어짐. - 오른쪽극단값들은 bot 임! Boyoung Kim (SNU) April 25, 2018 12 / 12
Personalized Click Model through Collaborative Filtering Si Shen et al., WSDM, 2013 Presented by Boyoung Kim April 25, 2018 Boyoung Kim (SNU) PCM April 25, 2018 1 / 9
PCM Introduction 목적 쿼리가주어졌을때문서 ( 검색결과 ) 클릭률예측 개인화 자연검색결과 ( 광고를제외한결과 ) 만을고려 Boyoung Kim (SNU) PCM April 25, 2018 2 / 9
PCM Notation 각각의관측값은다음과같은구성요소를갖음 C : 클릭여부. C = 1 은클릭을나타냄 u : 사용자, 총 M u 명 q : 쿼리, 총 M q 개 d : 문서 ( 검색결과 ), 총 M d 개 i : 문서위치 ( 검색결과가나타난위치 ) Boyoung Kim (SNU) PCM April 25, 2018 3 / 9
PCM Position model ( 기존모형 ) 가정 사용자의문서에대한클릭여부는문서의제목, 내용일부를검토한후이뤄진다. 사용자가문서를검토할지여부는문서의위치에의존한다. E i = 1 이사용자가 i 번째문서를검토한다는것을나타낼때모형은 P(C i = 1 q, d) = E i P(C i = 1 E i, q, d)p(e i ) (1) = P(C i = 1 E i = 1, q, d)p(e i = 1) (2) := α qd β i (3) 여기서 α qd := P(C i = 1 E i = 1, q, d) ( 문서관련성 ), β i := P(E i = 1) ( 위치편의 ) 라한다. Boyoung Kim (SNU) PCM April 25, 2018 4 / 9
PCM Matrix Factorization Click Model (MFCM) 식 (3) 의문서관련성모수 (α qd ) 에쿼리, 문서각각의특성벡터고려. P(α qdi Q q, D di, σ) N ((Q q D di ), σ 2 ) P(Q q σ Q ) N (0, σ 2 QI ) P(D di σ D ) N (0, σ 2 DI ) 여기서 d i 는 i 번째문서인덱스, Q R F Mq, D R F M d, F 는잠재요인의수이다. Q q 는 Q 의 q 번째열벡터, D d 는 D 의 d 번째열벡터를나타낸다. 쿼리, 문서의잠재벡터로부터 insight 얻을수있음 새로운쿼리, 문서조합에대해서도예측가능 Boyoung Kim (SNU) PCM April 25, 2018 5 / 9
PCM Tensor Factorization Click Model (PCM) 개인화 N i 를사용자의 i 번째문서에대한흥미여부라하자. P(C i = 1 q, d, u) = P(E i = 1, N i = 1 q, d, u) = P(N i = 1 E i = 1, q, d, u)p(e i = 1) α uqdi := P(N i = 1 E i = 1, q, d, u) 라하면 P(α uqdi U u, Q q, D di, σ) N ((U u Q q D di ), σ 2 ) (4) P(U u σ U ) N (0, σ 2 UI ) (5) P(Q q σ Q ) N (0, σ 2 QI ) (6) P(D di σ D ) N (0, σ 2 DI ) (7) 여기서 U R F Mu 이고, U u Q q D di = F f =1 U fu Q fq D fdi. Boyoung Kim (SNU) PCM April 25, 2018 6 / 9
PCM Tensor Factorization Click Model (PCM) PCM 의 Graphic representation Boyoung Kim (SNU) PCM April 25, 2018 7 / 9
PCM Hybrid Personalized Model (HPCM) 식 (4) 에서쿼리와문서사이의상호작용을강조하고, 개인화실현을위해 residual 부분만사용자의 latent factor 고려 P(α uqdi Q q, D di U u, Q q, D di, σ) N ( Q q D di + U u Q q D di, σ 2 ) 사전분포는다음과같다. P( Q q σ Q ) N (0, I ) σ2 Q P( D di σ D ) N (0, I ) σ2 D P(U u σ U ) N (0, σ 2 UI ) P(Q q σ Q ) N (0, σ 2 QI ) P(D di σ D ) N (0, σ 2 DI ) Boyoung Kim (SNU) PCM April 25, 2018 8 / 9
PCM Hybrid Personalized Model (HPCM) HPCM 의 Graphic representation Boyoung Kim (SNU) PCM April 25, 2018 9 / 9