ランダムフォレストアルゴリズム

Target の Automated Personalization と自動ターゲットで使用されている主要パーソナライゼーションアルゴリズムは、ランダムフォレストです。ランダムフォレストのようなアンサンブル手法は、複数の学習アルゴリズムを使用して、どの構成学習アルゴリズムを使用した場合よりも優れた予測パフォーマンスを実現します。Automated Personalization のランダムフォレストアルゴリズムは、トレーニング時に多数のデシジョンツリーを構成することで機能する分類手法または回帰手法です。

統計学の観点から見ると、結果の予測に使用される単一の回帰モデルが思い浮かぶかもしれません。データサイエンスの最新の調査では、同一のデータセットから複数のモデルが構築され、効果的に組み合わせられる「アンサンブル手法」の方が、単一のモデルだけで予測する場合よりも結果が優れていることが示されています。

ランダムフォレストアルゴリズムは、Automated Personalization および自動ターゲットアクティビティで使用されている主要パーソナライゼーションアルゴリズムです。ランダムフォレストは、多数のデシジョンツリーを組み合わせることで、1 つのデシジョンツリーよりも予測精度を高めます。

デシジョンツリーとは

デシジョンツリーは、システムが学習できる訪問データをすべて分割してから、グループ化するためのものです。この際の各グループ内の訪問は、目標指標を基準として、可能な限り類似したものになります。ただし、それぞれのグループ間では、目標指標（コンバージョン率など）を基準として、可能な限り差異が大きくなります。デシジョンツリーはトレーニングセット内の様々な変数を参照しながら、それぞれが重複することなく、全体として漏れがない形（MECE）でデータをこれらのグループ（「リーフ」）に分割し、目標値を最大化します。

簡単な例として、次の 2 つの入力変数があるとします。

性別（値は男性と女性の 2 つ）
郵便番号（小さなデータセットで、値は 11111、22222、33333、44444、55555 の 5 つ）

目標指標はコンバージョンです。この場合、デシジョンツリーはまず、2 つの変数のうち、訪問データのコンバージョン率で最も大きなバリエーションを示すのはどちらなのかを判断します。

郵便番号が最も予測的だとします。この変数がデシジョンツリーの最初の「ブランチ」を形成します。続いて、訪問データをどう分割するかを判断します。各グループ内のレコードのコンバージョン率はできる限り差異が小さく、各グループ間のコンバージョン率はできる限り差異が大きくなるようにするといった具合です。この例では 11111、22222、33333 を 1 つ目のグループ、44444、55555 を 2 つ目のグループとします。

この分割によって、デシジョンツリーの第一の層が次のように形成されます。

decsion_tree_1 image

続いて、「最も予測的な変数は何か？」という質問が考慮されます。この例では変数が 2 つしかないので、この質問の答えは性別となります。同様の処理がおこなわれ、それぞれのブランチ内のデータが分割されます。まず、11111、22222、33333 のブランチを見てみましょう。これらの郵便番号で、男性と女性でコンバージョン率に差異がある場合は、リーフは男性と女性の 2 つになり、このブランチの処理はそれで完了します。44444 と 55555 のもう一方のブランチでは、女性と男性でコンバージョン率に統計的差異はなかったとします。この場合、1 つ目のブランチが最後の分割となります。

この例のデシジョンツリーは、最終的に次のようになります。

decsion_tree_2 image

ランダムフォレストではデシジョンツリーをどのように使用しますか？

デシジョンツリーは効果的な統計ツールになりますが、デメリットもあります。最も大きなデメリットは、データの「オーバーフィッティング」が生じ、1 つのデシジョンツリーで、最初のデシジョンツリーの構築に使用されていない将来のデータの予測精度が悪くなる場合があるという点です。これは、統計学習におけるバイアス／バリアンストレードオフと呼ばれる問題です。ランダムフォレストは、このオーバーフィッティングの問題を解決するのに役立ちます。ランダムフォレストは簡単に言うと、同一のデータセットを基に、わずかに違う形で構築されたデシジョンツリーの集合で、「投票」によって単一のデシジョンツリーよりも優れたモデルを生成します。これらのデシジョンツリーは、属性の一部をランダムに選択することに加え、置換によって訪問レコードの一部をランダムに選択（バギング）することで構築されるので、ランダムフォレストはわずかに異なるデシジョンツリーで構成されることになります。この手法では、ランダムフォレストに構築されたデシジョンツリーにわずかなバリエーションが生まれます。この適度な量のバリエーションを追加することで、アルゴリズムの予測精度が高まります。

Target のパーソナライゼーションアルゴリズムでは、ランダムフォレストをどのように使用しますか？

モデルが構築される仕組み

次の図には、自動ターゲットまたは Automated Personalization アクティビティでモデルが構築される仕組みが簡単にまとめられています。

random_forest_flow 画像

Target がエクスペリエンス／オファーをランダムに配信しながら訪問者のデータを収集します。
収集データがまとまった量になると、特徴量が作成されます。
エクスペリエンス／オファーごとにランダムフォレストのモデルが作成されます。
モデルが品質スコアの基準値を満たしているかがチェックされます。
将来のトラフィックをパーソナライズするために、モデルが実稼動環境にプッシュされます。

Target は、自動収集したデータと、ユーザーが提供したカスタムデータを使用してパーソナライゼーションアルゴリズムを構築します。このモデルによって、訪問者に表示する最適なエクスペリエンスやオファーが予測されます。通常は、自動ターゲットアクティビティの場合はエクスペリエンスごとにモデルが 1 つ、Automated Personalization アクティビティの場合はオファーごとにモデルが 1 つ構築されます。Target はそのうえで、成功指標（コンバージョン率など）の推定値が最も高いエクスペリエンスまたはオファーを選んで表示します。これらのモデルは、予測に使用する前に、ランダムに割り当てられた訪問を対象にトレーニングをおこなう必要があります。そのため、アクティビティが開始されると、パーソナライゼーションアルゴリズムの準備が整うまで、パーソナライズ対象のグループに入っている訪問者にも複数のエクスペリエンスまたはオファーが配信されます。

各モデルは、アクティビティで使用される前に、訪問者の行動予測に適しているかを確認するために検証されます。この検証は AUC（曲線下面積）に基づいておこなわれます。検証をおこなう必要があるので、モデルによってエクスペリエンスのパーソナライズが開始されるタイミングは、データの詳細によって異なります。トラフィックのプランニングの観点からの目安としては、モデルが有効になるまでには、最低限のコンバージョン数が必要になるのが一般的です。

エクスペリエンスまたはオファーのモデルが有効になると、エクスペリエンスまたはオファー名の左にある時計のアイコンが緑色のチェックボックスに変わります。2 つ以上のエクスペリエンスまたはオファーの有効なモデルがあれば、一部の訪問に対してパーソナライズが開始されます。

特徴変換 

データはパーソナライゼーションアルゴリズムに送られる前に、特徴変換がおこなわれます。特徴変換は、パーソナライゼーションモデルで使用するために、トレーニングレコードの収集データを準備する処理です。

特徴変換は属性のタイプによって異なります。属性（データサイエンティストは「特徴」と呼ぶこともあります）は次の 2 種類に大別されます。

分類：分類特徴はカウントできませんが、様々なグループに分類できます。分類特徴には、国、性別、郵便番号などがあります。
数値：数値特徴は測定やカウントが可能で、年齢や収入などがあります。

分類特徴の場合、可能なすべての特徴のセットが保持され、尤度変換を使用してデータサイズが低減されます。数値特徴の場合、特徴は全体で比較可能あることが再スケーリングによって保証されます。

マルチアームバンディットによる学習とパーソナライズのバランス調整

Target によってパーソナライゼーションモデルが構築され、トラフィックのパーソナライズが開始されると、アクティビティへの以降の訪問者に関して、あるジレンマが生じます。現在のモデルですべてのトラフィックをパーソナライズするべきか、引き続きランダムにオファーを配信し、新規訪問者を対象とした学習を続けるべきかというジレンマです。パーソナライゼーションアルゴリズムによって訪問者に関する新たなトレンドを見つけ出すための学習を常におこないながら、トラフィックの大部分をパーソナライズできれば効果的です。

マルチアームバンディットは、Target でこのジレンマを解消するためのものです。マルチアームバンディットにより、モデルは常にトラフィックのごく一部を利用して、アクティビティの学習期間全体にわたって学習を続け、それまでに学習したトレンドの乱用を防止します。

データサイエンスの世界では、このマルチアームバンディット（MAB）問題は、それぞれの報酬の確率が未知のワンアームバンディットの集合となる、探索と活用のジレンマの古典的な例です。重要なのは、プレーの成功率が最も高く、受け取られる報酬の合計が最大となるアームを生む戦略を開発することです。マルチアームバンディットは、オンラインモデルの構築後のオンラインスコアリングのためにシステムで使用されます。これは、探索時のオンライン学習に役立ちます。現在のマルチアームアルゴリズムは、Epsilon（ε）- Greedy アルゴリズムです。このアルゴリズムでは、確率 1- ε の場合に、最適なアームが選択され、確率 ε の場合は、その他のアームがランダムに選択されます。