LRアルゴリズムとそのCTR推定上のエンジニアリング実践

yangliang @ Maan Coffee
人を离れる时、2篇の文章を书いたことがあって、仕事の総括とLRアルゴリズムの総括.今周末に占空とLRを交流して、いくつかの新しいものが自分で前に知らないと感じて、再び総括する必要があると思って、そこでこの文章がありました.
本文では,広告クリック率推定におけるLRアルゴリズムの使用について,オフラインデータ処理,モデルトレーニング,オンラインサービスなどを詳しく紹介する.まずDSPの背景からお話しします.
0 DSP背景紹介
中小広告主が広告を投入し、Ad Exchangeに接続してトラフィックを取得し、リアルタイムの競売に参加し、そこから差額を稼ぐのを助ける.
広告エンジンは、Ad Exchangeを直接接続し、広告ライブラリから広告リストを初歩的に選択します.その後、ポリシーグループの各広告の競売価格をリアルタイムで尋ねます.
ポリシーグループは、ユーザ情報、広告情報、コンテキストシーン情報に基づいて価格を設定します.価格は主に2つの方面に関連しています:競売戦略とCTRの見積り、今回私たちが主に討論したのはCTRの見積りです.
1データ／フィーチャー抽出
1.1データ準備
元のデータ:要求/競売/展示/クリック/変換などのデータ
データclean/merge:汚いデータのclean/およびデータチェーンのmerge、いくつかのidフィールド(cookie mappingなどの技術)に基づいて
1.2特徴抽出(単一特徴／組合せ特徴／変換特徴)
単特徴模範:ユーザー性別組合せ特徴模範:広告id+広告ビットid転化特徴模範:urlドメイン名転換;年齢フィーチャーセグメント

       ／  ／       [    url]

    ／    ：LR       ，   y(CTR) x        ，  x     ／   。         ，             。

     
－            ，      ：         >30 1，  0。         ，      “  300 ”           ；
－                 ，        ，    
－          ，          ，    

  ＋     
      ：               ，     “      +    ”   “      +    ”   。           ，             。                。    ，    ，    n       ，     
https://www.zhihu.com/question/31989952/answer/54184582

1.3サンプリング
時間による再サンプリング:近距離ポイントデータの再サンプリング
実際のデータ規模

  ：  pv/click＋       
  ：      （     ：    ／   ／IP；  id／     ；   id）
     ：  1/2  ；   5-8  
click  w  ；pv  kw  ；bind  ：    

2フィーチャーの選択
特徴選択評価指標:モデルAUC
一般的なフィーチャーの選択方法

L 1正則

ピルソン係数と相互情報係数(情報利得)

を計算する.

訓練特徴を採点できる予選モデル:RandomForestとLogistic Regressionなどはモデルの特徴を採点し、採点によって相関性を得た後、最終モデルを訓練する.https://www.zhihu.com/question/28641663

以前に採用した方法:前のフィーチャークラスタ選択
3 LRアルゴリズム
3.1 LRモデル構築
極めて似ているようにモデルを構築する.最適化目標関数誤差がGauss分布を満たす前提を得る:極大尤度等価最小二乗法
3.2 LRモデルの解
LRモデルのターゲット関数は凸関数であり,凸問題を解くには多くの汎用的な方法がある.大規模なLRに対しても,的確なアルゴリズムがある.
種々の最適化アルゴリズムの基本構想は, の探索と の計算である.勾配法ニュートン法BFGS／L-BFGS;OWLQN(LRバンドL 1正則)勾配法:勾配情報を用いて最速降下方向を探す.平面を用いて元の関数に近づき,一次収束Newton法:Hessian行列を用いて下降方向を探す.二次曲面を用いて元の関数に近づき,二次収束した.-Hessian逆行列,計算コスト大BFGS(最良の擬ニュートンアルゴリズム):反復の最近のkステップ情報(関数値,勾配情報)に基づいてHessian行列を構築する逆L−BFGS:BFGSの空間的複雑度はo(n^2)であり,このアルゴリズムは空間的複雑度をo(n*k)OWLQN(LRバンドL 1正則):L 1に勾配がないため,二次勾配の概念を提案する
擬ニュートン法:Hessian行列に似た正定行列を構築するために一定の方法を採用するが,この構造法の計算量はニュートン法より小さい
5 L 1/L 2正則を深く理解する

1.   ：     ；L1     

2.   
       p（y|x,w)，       p(w)，          ，       
L(w) ＝ p(y|X;w) * p(w)

                   
    w       -> L2  
    w        -> L1  

    ：            ，               

       ：
Least Square         Gaussian             
Ridge       Gaussian            
LASSO       Laplace            
https://www.zhihu.com/question/35322351

    LR       sigmoid   ？
               ， paper        。
                ，                        。
https://www.zhihu.com/question/35322351

6その他

1. log loss    ／auc     
logloss             ，AUC   rank order
https://www.zhihu.com/question/54009615

AUC：              ；
MAE（Mean Absolute Error）/MSE（Mean Squared Error），               ；
Loss：                  ；
http://www.flickering.cn/uncategorized/2014/10/%E8%BD%AC%E5%8C%96%E7%8E%87%E9%A2%84%E4%BC%B0-2%E9%80%BB%E8%BE%91%E5%9B%9E%E5%BD%92%E6%8A%80%E6%9C%AF/


2.      /    
    ：  id：  ／    (  )
    －ctr    
    
    

3.    ：FM／NB／SVM
LR NB    Discriminative and Generative Algorithm   ，      ，         ，        。               LR       ，LR                             。
  ：          
  ：       （       ）
     ：          ，            

Ref