VKontakteメトリックの因果関係を分析します

みなさん、こんにちは。私の名前はアンバーです。CoreMLVKチームで働いています。私たちのタスクの1つは、ニュースフィードのランキングアルゴリズムを作成して改善することです。この記事では、原因と結果の分析を使用して、サービスをユーザーにとってより興味深いものにする方法を紹介します。相関分析に対するこのアプローチの利点について話しましょう。既存のアルゴリズムへの変更を提案します。

短いメトリックと長いメトリックとは何ですか？

ランキングモデルは、ユーザーがニュース（投稿）を操作する可能性を推定しようとします。ユーザーはそれに注意を払い、「いいね」のマークを付け、コメントを書き込みます。次に、モデルはこの確率の降順でレコードを配布します。したがって、ランキングを向上させることで、ユーザーアクション（いいね、コメントなど）のクリック率（クリックスルー率）を上げることができます。これらのメトリックは、ランキングモデルの変更に非常に敏感です。私はそれらを短く呼びます。



しかし、別のタイプのメトリックがあります。たとえば、アプリケーションで費やされた時間、またはユーザーセッションの数は、サービスに対する彼の態度をはるかによく反映していると考えられています。このようなメトリックをlongと呼びます。



ランキングアルゴリズムを使用して長いメトリックを直接最適化することは、簡単な作業ではありません。指標が短い場合、これははるかに簡単です。たとえば、いいねのCTRは、その可能性をどれだけうまく推定できるかに直接関係します。ただし、短いメトリックと長いメトリックの間の因果関係（または因果関係）がわかっている場合は、長いメトリックに予想どおりに影響を与えるはずの短いメトリックのみを最適化することに集中できます。私はそのような因果関係を抽出しようとしました-そしてそれについて私の仕事に書きました、それは私がITMOの科学の学士号（CT）で卒業証書として完成しました。ITMOの機械学習研究所でVKontakteと共同で研究を行いました。

コード、データセット、サンドボックスへのリンク

ここですべてのコードを見つけることができます：AnverK。



メトリック間の関係を分析するために、VKチームがさまざまな時点で実施した6,000を超える実際のA / Bテストの結果を含むデータセットを使用しました。データセットはリポジトリでも利用できます。



サンドボックスでは、提案されたラッパーの使用方法を確認できます：合成データ。

そしてここで-データセットにアルゴリズムを適用する方法：提案されたデータセット上。

誤った相関関係への対処

私たちの問題を解決するには、メトリック間の相関関係を計算するだけで十分であるように思われるかもしれません。しかし、これは完全に真実ではありません。相関関係は必ずしも原因ではありません。 4つのメトリックのみを測定し、それらの因果関係が次のようになっている





としましょう。一般性を失うことなく、矢印の方向にプラスの影響があると仮定します。いいねが多いほど、SPUが多くなります。この場合、写真へのコメントがSPUにプラスの影響を与えることを立証することが可能になります。そして、このメトリックを「増加」させると、SPUが増加することを決定します。この現象は誤相関と呼ばれます。：相関係数はかなり高いですが、因果関係はありません。誤った相関関係は、同じ原因の2つの影響に限定されません。同じコラムから、いいねが写真の開口部の数にプラスの影響を与えるという誤った結論を下す可能性があります。



このような単純な例でも、相関関係の単純な分析が多くの誤った結論につながることが明らかになります。因果推論（関係の推論方法）を使用すると、データから因果関係を復元できます。それらをタスクに適用するために、最も適切な因果推論アルゴリズムを選択し、それらにpythonインターフェイスを実装し、さらに、条件でより適切に機能する既知のアルゴリズムの変更を追加しました。

推論リンクの古典的なアルゴリズム

因果推論のいくつかの方法を検討しました：PC（Peter and Clark）、FCI（Fast Causal Inference）、およびFCI +（理論的な観点からはFCIに似ていますが、はるかに高速です）。あなたはこれらの情報源でそれらについて詳細に読むことができます：

• 因果関係（J.パール、2009年）、
• 原因、予測および検索（P. Spirtes et al。、2000）、
• スパース因果モデルの学習はNPハードではありません（T. Claassen et al。、2013）。

ただし、最初の方法（PC）は、2つ以上のメトリックに影響を与えるすべての量を観察することを前提としていることを理解することが重要です。この仮説は因果的充足度と呼ばれます。他の2つのアルゴリズムは、監視対象のメトリックに影響を与える観測不可能な要因が存在する可能性があることを考慮に入れています。つまり、2番目のケースでは、原因となる表現がより自然であると見なされ、観察できない要因の存在が可能になります。$$$U_1, \dots U_k$：







これらのアルゴリズムのすべての実装は、pcalgライブラリで提供されます。それは美しく柔軟性がありますが、1つの「欠点」があります-それはRで書かれています（最も計算量の多い関数を開発するときは、RCPPパッケージが使用されます）。したがって、上記のメソッドでは、CausalGraphBuilderクラスにラッパーを記述し、その使用例を追加しました。



リンクを導出する機能の契約、つまりインターフェースと出力で得られる結果について説明します。条件付き独立性のテスト関数に合格できます。これはこのようなテストであり、$$$p_{value}$ 量がというヌル仮説の下で $$$X$ そして $$$Y$ 既知の量のセットに対して条件付きで独立 $$$Z$..。デフォルトは部分相関テストです。このテストで関数を選択したのは、これがpcalgのデフォルトであり、RCPPで実装されているためです。これにより、実際には高速になります。転送することもできます$$$p_{value}$、そこから頂点が依存していると見なされます。PCおよびFCIアルゴリズムの場合、ライブラリ操作のログを書き込む必要がない場合は、CPUコアの数を設定することもできます。FCI +にはそのようなオプションはありませんが、この特定のアルゴリズムを使用することをお勧めします。もう1つの注意点：FCI +は現在、提案されているエッジ方向アルゴリズムをサポートしていません。ポイントは、pcalgライブラリの制限にあります。



すべてのアルゴリズムの作業の結果に基づいて、PAG（部分的な祖先グラフ）がエッジのリストの形式で作成されます。PCアルゴリズムでは、古典的な意味での因果グラフ（またはベイジアンネットワーク）として解釈する必要があります。$$$A$ で $$$B$、影響力を意味します $$$A$ オン $$$B$..。エッジが無指向性または双方向の場合、一意に方向付けることはできません。つまり、次のようになります。

• または、利用可能なデータが方向性を確立するには不十分です。
• または、観察可能なデータのみを使用する真の因果グラフは、同等クラスまでしか確立できないため、不可能です。

FCIアルゴリズムもPAGになりますが、新しいタイプのエッジが表示されます。末尾に「o」が付いています。これは、矢印がそこにある場合とない場合があることを意味します。この場合、FCIアルゴリズムとPCの最も重要な違いは、双方向（2つの矢印）のエッジにより、それによって接続された頂点が観察できない頂点の結果であることが明確になることです。したがって、PCアルゴリズムのダブルエッジは、2つの「o」端を持つエッジのようになります。このような場合の図は、合成例を含むサンドボックスにあります。

エッジ方向アルゴリズムの変更

古典的な方法には1つの重大な欠点があります。彼らは未知の要因があるかもしれないことを認めますが、同時に彼らは別の過度に深刻な仮定に依存しています。その本質は、条件付き独立性をテストする機能が完全でなければならないということです。それ以外の場合、アルゴリズムはそれ自体に責任を負わず、グラフの正確性または完全性を保証しません（正確性に違反せずに、より多くのエッジを方向付けることができないという事実）。理想的な有限サンプルの条件付き独立性テストをいくつ知っていますか？私ではありません。



この欠点にもかかわらず、グラフスケルトンは非常に説得力のある方法で構築されていますが、方向性が強すぎます。そこで、エッジ方向アルゴリズムの変更を提案しました。ボーナス：方向付けられたエッジの数を暗黙的に調整できます。その本質を明確に説明するために、因果関係の導出のためのアルゴリズムについてここで詳細に話す必要があるでしょう。したがって、このアルゴリズムの理論と提案された修正を別々に添付します-資料へのリンクは投稿の最後にあります。

モデルの比較-1：グラフの可能性の推定

奇妙なことに、因果関係を導き出す上での深刻な問題の1つは、モデルの比較と評価です。どうやってそうなった？重要なのは、通常、実際のデータの真の因果的表現は不明であるということです。さらに、それから実際のデータを生成するほど正確に分布の観点からそれを知ることはできません。つまり、ほとんどのデータセットでグラウンドトゥルースは不明です。したがって、ジレンマが発生します。既知のグラウンドトゥルースを持つ（半）合成データを使用するか、グラウンドトゥルースなしで実行しようとしますが、実際のデータでテストします。私の仕事では、テストに2つのアプローチを実装しようとしました。



最初のものはグラフの可能性の見積もりです：







ここに$$$PA_G(X)$ -多くの頂点の親 $$$X$、 $$$I(X, Y)$ -数量の共同情報 $$$X$ そして $$$Y$、および $$$H(X)$ 量のエントロピーです $$$X$..。実際、第2項はグラフの構造に依存しないため、原則として第1項のみが考慮されます。ただし、新しいエッジを追加しても可能性が低下しないことがわかります。これは、比較するときに考慮する必要があります。



実際のPAG（FCI、FCI +アルゴリズムの出力）では、ダブルエッジのセマンティクスが完全に異なるため、このような評価はベイジアンネットワーク（PCアルゴリズムの出力）を比較する場合にのみ機能することを理解することが重要です。



したがって、エッジの向きを自分のアルゴリズムと従来のPC







と比較しました。エッジの向きを変更すると、従来のアルゴリズムと比較して可能性が大幅に向上しました。ただし、エッジの数を比較することが重要です。







それらの数はさらに少なくなります-これは予想されます。したがって、エッジが少なくても、より妥当なグラフ構造を復元することができます。ここで、エッジの数に応じて可能性が低下しないと主張するかもしれません。重要なのは、一般的な場合に得られるグラフは、古典的なPCアルゴリズムによって得られたグラフのサブグラフではないということです。シングルエッジの代わりにダブルエッジが表示され、シングルエッジの方向が変わる場合があります。だから手工芸品はありません！

モデルの比較-2：分類アプローチの使用

比較の2番目の方法に移りましょう。PCアルゴリズムを使用して因果グラフを作成し、そこからランダムな非周期グラフを選択します。その後、親頂点の値と係数の線形の組み合わせとして、各頂点のデータを生成します$$$\pm[0,2, 0,8]$ガウスノイズが追加されています。このような世代のアイデアは、「ビジネスアプリケーションの堅牢で用途の広い原因の発見に向けて」（Borboudakis et al。、2016）の記事から引用しました。親を持たない頂点は、対応する頂点のデータセットと同様のパラメーターを使用して、正規分布から生成されました。



データを受信すると、評価したいアルゴリズムを適用します。さらに、私たちはすでに真の因果関係のグラフを持っています。結果のグラフを実際のグラフと比較する方法を理解することだけが残っています。 「条件付き2点および3点情報に基づく因果的グラフィカルモデルのロバストな再構築」（Affeldt et al。、2015）では、分類用語を使用することが提案されました。描画されたエッジはPositiveクラスであり、描画されていないエッジはNegativeであると想定します。次にTruePositive（$$$TP$）真の因果関係グラフと同じエッジを描画し、False Positive（$$$FP$）-真の因果グラフにないエッジが描画された場合。これらの値をスケルトンの観点から評価します。



方向性を考慮して、$$$TP_{misorient}$正しく表示されているが方向が間違っているエッジの場合。その後、次のように検討します。

• $$$TP' = TP - TP_{misorient}$
• $$$FP' = FP + TP_{misorient}$

その後、あなたは読むことができます $$$F_1$-スケルトンのサイズと方向を考慮したサイズの両方（この場合、明らかに、スケルトンのサイズより大きくなることはありません）。ただし、PCアルゴリズムの場合、ダブルエッジが追加されます$$$TP_{misorient}$ のみ $$$0.5$、 だがしかし $$$1$、実際のエッジの1つがまだ推定されているため（因果関係がなければ、これは間違っています）。



最後に、アルゴリズムを比較してみましょう







。最初の2つのグラフは、PCアルゴリズムのスケルトンの比較です。従来のグラフと新しいエッジの向きです。上部の境界線を表示するために必要です$$$F_1$-対策。次の2つは、方向に関してこれらのアルゴリズムを比較しています。ご覧のとおり、勝利はありません。

モデルの比較-3：原因となる十分性をオフにします

次に、生成後の実際のグラフと合成データのいくつかの変数を「閉じ」ましょう。これにより、CausalSufficiencyがオフになります。ただし、結果を実際のグラフではなく、次のように取得したグラフと比較する必要があります。

• 非表示の頂点の親からのエッジは、その子に描画されます。
• 非表示の頂点のすべての子をダブルエッジで接続します。

FCI +アルゴリズム（変更されたエッジ方向と従来のアルゴリズム）をすでに比較します。







そして、因果的十分性が満たされない場合、新しい方向の結果ははるかに良くなります。



もう1つの重要な観察結果が現れました。PCアルゴリズムとFCIアルゴリズムは、実際にはほぼ同じスケルトンを構築します。したがって、私はそれらの出力を、私の作業で提案したエッジの方向と比較しました。







アルゴリズムの品質は実質的に異ならないことが判明しました。この場合、PCはFCI内のスケルトン構築アルゴリズムのステップです。したがって、FCIアルゴリズムのようにオリエンテーションPCアルゴリズムを使用することは、リンク推論の速度を上げるための優れたソリューションです。

出力

この記事で話したことを簡単に要約します。

1. 大規模なIT企業で因果関係を導き出すタスクがどのように発生する可能性があるか。
2. スプリアス相関とは何ですか？また、それらが機能選択にどのように干渉する可能性がありますか。
3. 推論リンクのどのアルゴリズムが存在し、最も頻繁に使用されますか。
4. 原因グラフを導出するときにどのような問題が発生する可能性がありますか？
5. 原因グラフの比較とその対処方法は何ですか。

因果推論のトピックに興味がある場合は、私の他の記事を見てください-それにはもっと理論があります。そこで、リンクの推論に使用される基本的な用語、および古典的なアルゴリズムがどのように機能するか、そして私が提案したエッジの方向について詳しく説明します。