効率的な整数計画法ソリューション、Kuaishouは多変量因果森林モデルを提案し、インテリジェントなマーケティング効果が顕著です

一定額以上の購入に対する Meituan のクーポンや Taobao のショッピング紅包などのスマートなマーケティング シナリオでは、体系的なマーケティング決定を行う必要があります。このようなシナリオに基づいて、Kuaishou は、よりきめ細かいマーケティングの意思決定を実行するための新しい多変量因果フォレスト モデルを提案しました。 Kuaishou のコミュニティ サイエンス部門は、数億人の Kuaishou ユーザーに基づいて、リソース割り当ての並列アルゴリズムを設計し、効率的にインテリジェントなマーケティング決定を下せるようにしました。本研究では、多変量因果モデルの評価問題を解決するために、ランダムマッチングの考え方を採用し、業界が参考にできる手法を提供しました。最後に、オフラインシミュレーション実験とオンラインの実際のA/B実験を通じて、LBCFアルゴリズムの有効性が検証されました。この技術は中国の発明特許に申請されており、Kuaishouのインテリジェントマーケティングビジネスで広く使用されています。

異質因果効果（HTE）は因果推論理論で取り組むべき中核的な問題であり、その概念はもともと医療分野に由来しています。 HTE とは、同じ介入であっても、対象者に対する影響は人によって異なることを意味します。これは、計算広告、パーソナライズされた治療、パーソナライズされた教育、公共政策など、幅広い分野で応用されています。この概念を理解するために、スマートマーケティングの分野から例を挙げてみましょう。同じ補助金の強度を持つマーケティング手法では、すぐにコンバージョンするオーディエンスもいれば、まったくコンバージョンしないオーディエンスもいます。これらのオーディエンスをどのように正確に区別するかが、HTE が解決しなければならない問題です。近年、学術界では新たなHTE手法が次々と登場しており、その中でもスタンフォード大学経済学教授スーザン・アシーらが提唱する因果森林モデル[1]は、その優れた解釈性と優れた結果から産業界でも徐々に認知されつつあります。

• 論文リンク: https://arxiv.org/abs/2201.12585
• 論文コード: https://github.com/www2022paper/WWW-2022-PAPER-SUPPLEMENTARY-MATERIALS

大規模なインテリジェントマーケティングアルゴリズム

多変量因果フォレストモデル

スマートマーケティングが研究する必要がある中心的な問題は、補助金の額が異なるとユーザー間のコンバージョン効果にどれほどの違いがあるかということです。これらの異なる補助金の額は因果推論における処置とみなすことができるため、このシナリオでは研究者がさまざまな処置下でのユーザーのコンバージョン効果を研究することになり、多変量因果モデルが必要になります。ツリーベースのモデルは解釈性に優れ、機械学習において良好な結果を示しています。本研究では、主にツリーモデルに基づくHTE推定法について検討します。この方法は、HTE 推定を必要とするあらゆる分野に適用できます。この記事では、説明のためにインテリジェント マーケティング シナリオのみを例として使用します。

本論文で提案する多変量因果フォレスト モデルは、図 2 (説明例) に示すようなモデル構造を持っています。このモデル構造には 2 つの利点があります。第 1 に、単一のモデルで同時にあらゆる種類の介入手段を処理できることです。そうでない場合、複数の介入手段が対応する数のバイナリ因果フォレスト モデルを維持する必要があります。第 2 に、HTE の定義では、各介入手段が一貫した特徴サブスペースに対応している必要があります。このモデル構造はこれを保証します。これは HTE を正確に推定するために重要です。

図 2 多変量因果フォレスト モデル (注: 図 2 の Age や Inc. などのデータは説明のみを目的としています)

この目的のために、本研究では因果フォレストの分割基準を再設計しました。ツリーノードが分割されるたびに、異なるノード間の異質性、すなわちノード間分割（Inter Split）が強調されるだけでなく、ノード内の異なる介入方法の異質性、すなわちノード内分割（Intra Split）も強調されます。計算の複雑さの点では、ツリー ノードの特徴分割ポイントを探すときに、Inter Split は分割に必要なデータを一度にすばやく事前計算できますが、Intra Split はツリー ノード間の分割結果に依存します。そのため、Intra Split では分割データを毎回再計算する必要があり、非常に非効率的です。アルゴリズムの効率性と有効性のバランスをとるために、本研究では 2 段階の分割アルゴリズムを採用しました。

• 最初のステップは、Inter Split を通じて上位 N 個の候補特徴分割ポイントを選択することです。
• 2 番目のステップは、Intra Split を通じて N 個の候補から最終的な特徴分割ポイントを選択することです。

リソース割り当てのための並列アルゴリズム

ユーザーの弾力性を推定する問題を解決した後、インテリジェント マーケティングの分野でマーケティングの意思決定を出力するときは、限られたリソースの制約下で最適な割り当てを達成する方法を答える必要があることがよくあります。この目的のために、本研究では、図 3 に示すように、インテリジェント マーケティングにおけるリソース割り当て問題を制約付き整数計画数学モデルにモデル化しました。しかし、Kuaishou のユーザーベースは数億に上り、決定変数の数が膨大になります。現在のオープンソース ソルバーの多くはパフォーマンス要件を満たすことができず、メモリ オーバーフローなどの問題が発生する可能性があります。

図3 整数計画法の数学的モデル

この目的のために、本研究では、図 4 に示すように、並列の Dual Gradient Bisection (DGB) アルゴリズムを設計しました。このアルゴリズムは、ソリューションの品質を犠牲にすることなく、数分で何億人ものユーザーにソリューションを提供できます。スペースの制限により、ここではソリューションについて簡単に説明します。詳細については、論文および付録コードを参照してください。

• 最初のステップでは、図 3 の整数計画数学モデルを、線形緩和技術を使用して簡単に解決できる線形計画問題に簡略化します。緩和された線形計画問題の解集合には、予算臨界点で最大 1 つの非整数解が存在することが証明できます。
• 2 番目のステップは、ラグランジュ乗数を使用して制約付き問題を制約なしの問題に変換することです。
• 3 番目のステップでは、問題が強い双対性条件を満たしているため、研究者は問題に対して双対変換を実行し、それによってラグランジュ乗数の単変量区分関数を取得し、区分関数が閉区間上の凸関数であることを証明できます。
• 4 番目のステップでは、図 4 の DGB アルゴリズムを使用して、研究者は並列システム上で効率的に問題を解決できます。
• 5 番目のステップは、双対問題を元に戻して、すべての決定変数の値を順番に解決することです。

図4 並列DGBアルゴリズム

多変量因果モデル評価

因果モデルの反事実的結果は観察できないため、因果モデルのオフライン効果をどのように評価するかは、業界で解決すべき緊急の問題となっています。一般的に使用される評価方法には AUUC/Qini 曲線などがありますが、これらはバイナリ因果モデルの評価に適しています。多変量因果モデルの推定結果については、最初に多変量の結果を多数のバイナリ結果に分解し、次にそれらを個別に評価するしかありません。

この論文では、ランダム化比較試験 (RCT) データを使用し、治療マッチングの考え方に基づいて全体的な利益を比較する方法を示します。中心となる方法は、ポリシー処理と RCT 処理に一致する RCT データ内のサンプルを見つけることです。これらの一致するサンプルについては、その真の結果を観察できることを指摘しておく必要があります。第二に、これらの一致したサンプルの平均は、その列の期待値の良好な推定値であることが示されます。最後に、各列の期待値を使用して、多変量因果モデルの全体的な利点を計算できます。利点が高いほど、モデルは優れています。

エフェクト表示

アルゴリズムの効果を公平に比較​​するために、まず本研究では、Ye TuらがWWW 2021で発表したシミュレーションデータセット[2]を用いて、業界で主流となっているツリーベースの因果モデルとのオフライン比較を行った。図5に示す通り、横軸はデータセットのノイズの強さ、縦軸は研究者が懸念するコア指標のメリットである。LBCFが最も効果が高く、次いでCT.ST、CF.DTとなっていることがわかる。

図5 オフラインシミュレーション実験

さらに、この研究では、LBCF アルゴリズムを Kuaishou の実際のインテリジェント マーケティング シナリオに導入し、2 週間の A/B 実験を実施しました。図 6 に示すように、結果もアルゴリズムの有効性を証明しました。CT.ST アルゴリズムと CF.DT アルゴリズムと比較して、メリットはそれぞれ 0.92 パーセント ポイントと 2.48 パーセント ポイント増加しました。

図6 オンラインA/B実験

要約する

この論文では、Kuaishou の研究者が新しい HTE 予測方法である多変量因果フォレスト モデルを提案し、これを効率的な整数計画法ソリューション アルゴリズムと組み合わせたところ、その効果は業界で一般的に使用されているいくつかのツリー モデル方法よりも大幅に向上しました。同時に、研究者らは、因果効果のオフライン評価という業界の厄介な問題に対して、革新的な実現可能な解決策も提供しました。研究者たちは、この研究が機械学習愛好家の注目を集め、因果推論技術がそれぞれの実務ビジネスに広く応用されるようになることを期待している。