Hadoop Advent Calendar 2013 2013 12/25のXmasエントリです。
本記事では私が開発しているHadoop/Hive上で動作する機械学習ライブラリのHivemallについて、KDD Cup 2012, Track 2のデータセットを用いて利用方法を解説します。
https://github.com/myui/hivemall
基本的にプロジェクトのWikiサイトにあるKDDCup 2012 track 2 CTR predictionの説明を丁寧にしたものです。a9a binaryやnews20 binaryの方がよりシンプルの例ですので、そちらも参考にして頂ければと思います。
KDD Cup 2012, Track 2のCTR推定タスク
このタスクは与えられたセッション情報（ユーザ属性と広告の属性）をもとに、検索エンジンの広告クリック率(Click-Through Rate: CTR)を推定するタスクです。#clicks/#impressionsがCTRで目的変数になります。中国の3大検索エンジンの一つsoso.comから実検索ログが提供されています。機械学習のデータセットとして1) 実データに基づいていて、2) データセットのサイズが大きいという特徴があり、CTR/CVR予測の評価目的に実用性の高いデータセットです。
データセットは、次のようなテーブル構成です。
データ量は次のとおり。
- 訓練データ(約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
Hashing trickとバイアス項
(追記): 最新versionのHivemallですと、feature_hashing関数や categorical_features関数を利用するとより簡潔に記述できます。
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と呼ばれるテクニックで特徴次元数を減らしています。mhash関数は任意個の文字列を引数にとり、デフォルト設定で0～2^24-1(=16777215)のハッシュ値を生成します。MurmurHash3をハッシュ関数として理由するのでmhashです。なお、暗号的ハッシュ関数のSha1もサポートしています。
Hashing trickについてはこの辺も参考にしてください。
Hashing trickは必ずしも使わなくても良いですが、殆ど精度を落とすことなくモデルサイズを削減することができます。
バイアス項は識別関数f(x)=wx-bでの切片bのことなのですが、全ての訓練に共通な質的変数を一つ定義することで重みwを算出するときに識別関数が常に原点を通らないようにするものです。
各学習器でバイアス項を自動的に付与する"-b"オプションも利用できます。
二値分類問題への変換とランダムshuffle
（追記）: 最新versionのHivemallですと、 binarize_label関数で二値分類問題への変換が可能です。
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句と次のようなawkスクリプトによって二値分類問題への変換を行っています。このままの並びだと識別モデルのfittingに問題があります（ 訓練例の学習器への入力順によって偏りのある学習結果を生じる ）ので、CLUSTER BY句によってレコードをランダムに並び替えています。
CLUSTER BYはDISTRIBUTED BY+SORT BYの構文糖です。
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でバギングによって各弱学習器が出力する学習モデルを合成しています。回帰ではavg()、クラス分類ではvoted_avg()を利用ください。
（追記）: 最新versionのHivemallですと、logress関数の代わりに adadeltaを利用するとSGDの代わりにAdaDeltaを利用した最適化logistic lossの経験ロス最小化が行われます。
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と外部結合を用いて行います。
機械学習のpredict処理を関係演算の枠組みで行うことで関係演算の並列化の恩恵を受けるためのものです。Hivemallは他のライブラリと異なり、学習モデルがメモリに乗り切らなくても動作します。
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で簡単にできます。
他にもHivemallの利用例はプロジェクトサイトのwikiページにあります。
アピールタイム
Hivemallは共同研究先では月xxxGB増えていくテラバイトデータのCVR推定に使っております。Amazon Elastic MapReduceの上でもすぐ動きますので、ご興味のある方はぜひ利用して頂いてフィードバックして頂ければと思います。Mahoutよりきっと使いやすいはず(?)で、性能もよいはずです。
Mahoutのロジスティック回帰やPassive Aggressiveの実装はMapReduceが全く利用されていないシングルプロセスの逐次処理の実装となっております。Mahoutのクラス分類で実用性があるのはRandom Forest(通称: ランダム森）だけですが、ランダム森は汎化能力が弱いという問題があります。
最後に
サンタさんCTRデータ欲しい・・・（click率を0.2%としてimpressionまで採取すると500倍のストレージ要件！）。
投稿場所をこっちの方と間違えた気がしないでもない。