Hive/Hivemallを利用した広告クリックスルー率(CTR)の推定

[Hadoop Advent Calendar 2013 2013](http://qiita.com/advent-calendar/2013/hadoop) 12/25のXmasエントリです。
![X'mas version of HIvemall logo](https://qiita-image-store.s3.amazonaws.com/0/32790/33b2a880-4315-b52e-a82b-4736733c68be.png)

本記事では私が開発しているHadoop/Hive上で動作する機械学習ライブラリの[Hivemall](https://github.com/myui/hivemall)について、[KDD Cup 2012, Track 2](http://www.kddcup2012.org/c/kddcup2012-track2)のデータセットを用いて利用方法を解説します。
https://github.com/myui/hivemall

基本的に[プロジェクトのWikiサイト](https://github.com/myui/hivemall/wiki/_pages)にあるKDDCup 2012 track 2 CTR predictionの説明を丁寧にしたものです。[a9a binary](https://github.com/myui/hivemall/wiki/a9a-binary-classification-(logistic-regression-with-iterations))や[news20 binary](https://github.com/myui/hivemall/wiki/news20-binary-classification-%231-(Perceptron-PA))の方がよりシンプルの例ですので、そちらも参考にして頂ければと思います。

# KDD Cup 2012, Track 2のCTR推定タスク

このタスクは与えられたセッション情報（ユーザ属性と広告の属性）をもとに、検索エンジンの広告クリック率(Click-Through Rate: CTR)を推定するタスクです。#clicks/#impressionsがCTRで目的変数になります。中国の3大検索エンジンの一つsoso.comから実検索ログが提供されています。機械学習のデータセットとして1) 実データに基づいていて、2) データセットのサイズが大きいという特徴があり、[CTR/CVR予測](http://qiita.com/fukkyy/items/b2d37b4797516d72225a)の評価目的に実用性の高いデータセットです。

データセットは、次のようなテーブル構成です。
![テーブル構成](https://raw.github.com/myui/hivemall/master/resources/examples/kddtrack2/tables.png)

データ量は次のとおり。

* 訓練データ(約10GB+2.2GB, 15億レコード）
* 評価データ（約1.3GB, 2億レコード） 学習データの1.33割が評価用データセット

なお、検索語などはHashingなどを利用してすべて数値化されています。

# データの準備

CTRをそのまま訓練時の目的変数として利用した場合、click=0, impression=2 (CTR=0)とclick=0, impression=10 (CTR=0)で差がつかないという問題があるので、impressionごとにclickのあるなしの2値分類問題としてデータを作ってあげて、ロジスティック回帰でクリック確率（CTR)を予測するものとします。

全文は長いので載せません（自明でないところだけ説明します）が、下記ページのとおりHiveで訓練データと評価データのテーブルを定義します。
[https://github.com/myui/hivemall/wiki/KDDCup-2012-track-2-CTR-prediction-dataset](https://github.com/myui/hivemall/wiki/KDDCup-2012-track-2-CTR-prediction-dataset)

## Hashing trickとバイアス項

_(追記): 最新versionのHivemallですと、[`feature_hashing`関数](https://github.com/myui/hivemall/wiki/Feature-hashing)や [`categorical_features`関数](https://github.com/myui/hivemall/wiki/Input-Format-for-classification-and-regression#preparing-training-data-table)を利用するとより簡潔に記述できます。_

```sql
create or replace view training2 as
select
  rowid,
  clicks,
  (impression - clicks) as noclick,
  mhash(concat("1_", displayurl)) as displayurl, 
  mhash(concat("2_", adid)) as adid, 
  ...
  -1 as bias
from (
   ...
```
concat関数ではadid=1とuserid=1を被らないように、文字列連結により各質的変数の値ごとに重み1の特徴を作っています。
mhash関数では[hashing trick](http://en.wikipedia.org/wiki/Feature_hashing)と呼ばれるテクニックで特徴次元数を減らしています。mhash関数は任意個の文字列を引数にとり、デフォルト設定で0～2^24-1(=16777215)のハッシュ値を生成します。[MurmurHash3](http://en.wikipedia.org/wiki/MurmurHash)をハッシュ関数として理由するのでmhashです。なお、暗号的ハッシュ関数の[Sha1](http://ja.wikipedia.org/wiki/Secure_Hash_Algorithm)もサポートしています。
_Hashing trickについては[この辺](http://www.slideshare.net/pfi/pfi-seminar-20120315)も参考にしてください。_
Hashing trickは必ずしも使わなくても良いですが、殆ど精度を落とすことなくモデルサイズを削減することができます。
バイアス項は識別関数f(x)=wx-bでの切片bのことなのですが、全ての訓練に共通な質的変数を一つ定義することで重みwを算出するときに識別関数が常に原点を通らないようにするものです。
_各学習器でバイアス項を自動的に付与する"-b"オプションも利用できます。_

## 二値分類問題への変換とランダムshuffle

_（追記）: 最新versionのHivemallですと、 [`binarize_label`関数](https://github.com/myui/hivemall/wiki/Binarize-labels-for-Positive-Negative-instances)で二値分類問題への変換が可能です。_

```sql
INSERT OVERWRITE TABLE training_rcfile 
select transform(*) 
  ROW FORMAT DELIMITED ..
using 'gawk -f kddconv.awk' 
  as (rowid BIGINT, label FLOAT, features ARRAY<INT>)
  ROW FORMAT DELIMITED ..
from training2
CLUSTER BY CAST(rand(47) * 100 as INT), CAST(rand(49) * 100 as INT), CAST(rand(50) * 100 as INT);
```
では、Hiveの[transform句](https://cwiki.apache.org/confluence/display/Hive/LanguageManual+Transform)と次のようなawkスクリプトによって二値分類問題への変換を行っています。このままの並びだと識別モデルのfittingに問題があります（ _訓練例の学習器への入力順によって偏りのある学習結果を生じる_ ）ので、CLUSTER BY句によってレコードをランダムに並び替えています。
_CLUSTER BYは[DISTRIBUTED BY+SORT BYの構文糖](https://cwiki.apache.org/confluence/display/Hive/LanguageManual+SortBy)です。_

```awk
    rowid=$1;
    positive=$2;
    negative=$3;
    features=$4;
    for(i=5;i<=NF;i++)
    {
        features = features "," $i;
    }
    for(i=0;i<positive;i++)
    {
        print rowid "\t1.0\t" features
    }
    for(i=0;i<negative;i++)
    {
        print rowid "\t0.0\t" features
    }
```

# ロジスティック回帰による学習

Hivemallではparameter mixingと言われる一種のアンサンブル学習を利用しています。
Hivemallによる学習は各mapperで独立に行われます。その上で、reducerで[バギング](http://ibisforest.org/index.php?%E3%83%90%E3%82%AE%E3%83%B3%E3%82%B0)によって各弱学習器が出力する学習モデルを合成しています。回帰ではavg()、クラス分類ではvoted_avg()を利用ください。

_（追記）: 最新versionのHivemallですと、`logress`関数の代わりに [`adadelta`](https://github.com/myui/hivemall/wiki/news20-binary-classification-AdaGradRDA-AdaGrad-AdaDelta#adadelta)を利用するとSGDの代わりにAdaDeltaを利用した最適化logistic lossの経験ロス最小化が行われます。_

```sql
set hivevar:total_steps=5000000;

create table lr_model 
as
select 
 feature,
 avg(weight) as weight -- バギング
from 
 (select 
     logress(features,label, "-total_steps ${total_steps}") as (feature,weight)
  from 
     training_rcfile
 ) t -- map-onlyの弱学習器が複数実行される
group by feature -- featureの値ごとにreducerにshuffleされる
```
_hivevar:total_stepsは機械学習の学習率を制御するパラメタです。training_rcfileのcount(1)/立ち上がるmapper数などをセットしてください。設定しない場合には学習率の自動設定が行われます。_

# Lateral Viewを使った外部結合を利用したPredict処理

Hivemallでは機械学習の予測フェーズにおけるPredict処理を次のように[LATERAL VIEW](https://cwiki.apache.org/confluence/display/Hive/LanguageManual+LateralView)と外部結合を用いて行います。
_機械学習のpredict処理を関係演算の枠組みで行うことで関係演算の並列化の恩恵を受けるためのものです。Hivemallは他のライブラリと異なり、学習モデルがメモリに乗り切らなくても動作します。_

```sql
create table testing_exploded as
select 
  rowid,
  feature
from 
  testing2 
  LATERAL VIEW explode(features) t AS feature
```
explode関数は特徴ベクトルの配列を受け取って特徴ごとに展開して行を出力します。LATERAL VIEWはこの展開を行った上でベースとなったtesting2テーブルのタプルとの1対多の対応付けを仮想的なJOIN処理により行います。

```
SELECT
  t.rowid, 
  sigmoid(sum(m.weight)) as prob
FROM
  testing_exploded t LEFT OUTER JOIN
  model m ON (t.feature = m.feature)
GROUP BY 
  t.rowid
```
はテスト事例テーブルtesting_explodedの各行ごとに学習モデルから重みを算出した上で、実際のテスト事例を意味するrowidごとに重みを集計して算出します。ここでは重みの合計を求めた上でsigmoid関数によって区間(0,1)の確率値に変換しています。

# アドバンスドな話題

一般的にイテレーションは機械学習に必要な不可欠なものとされていますが、MapReduceでは各イテレーションでHDFSを介した入出力が行われるため、イテレーションを要するプログラムの実行に不向きです。Hivemallではamplify()関数とrand_amplify()関数でタプルを増幅した上でアンサンブル学習することでイテレーションを複数回行うのと同様の効果が得られる機能を提供しています。詳しくは下記を参考にして下さい。
https://github.com/myui/hivemall/wiki/Tips-%231-use-rand_amplify()-instead-of-iterations

もっと色々な学習器をアンサンブルすることも[union allで簡単にできます](https://github.com/myui/hivemall/wiki/news20-multiclass-classification-%233-Ensemble-learning)。

他にもHivemallの利用例はプロジェクトサイトの[wikiページ](https://github.com/myui/hivemall/wiki/_pages)にあります。

# アピールタイム

Hivemallは共同研究先では月xxxGB増えていくテラバイトデータのCVR推定に使っております。[Amazon Elastic MapReduceの上でもすぐ動きます](https://github.com/myui/hivemall/wiki/news20-binary-classification-on-Amazon-Elastic-MapReduce)ので、ご興味のある方はぜひ利用して頂いてフィードバックして頂ければと思います。Mahoutよりきっと使いやすいはず(?)で、性能もよいはずです。
_Mahoutのロジスティック回帰やPassive Aggressiveの実装はMapReduceが全く利用されていないシングルプロセスの逐次処理の実装となっております。Mahoutのクラス分類で実用性があるのはRandom Forest(通称: ランダム森）だけですが、ランダム森は汎化能力が弱いという問題があります。_

# 最後に

サンタさんCTRデータ欲しい・・・（click率を0.2%としてimpressionまで採取すると500倍のストレージ要件！）。

投稿場所を[こっちの方](http://qiita.com/advent-calendar/2013/machinelearning)と間違えた気がしないでもない。