SchiramRank - 公平にランク付けする方法を学ぶ

2023年に終了した国際学術会議AIBT 2023において、Ratidar Technologies LLCは公平性に基づくランキング学習アルゴリズムを発表し、同会議の最優秀論文報告賞を受賞しました。このアルゴリズムの名前はSkellam Rankで、統計の原理を最大限に活用し、ペアワイズランキングと行列分解を組み合わせ、推奨システムにおける正確性と公平性の問題を解決します。推薦システムにおける独自のランキング学習アルゴリズムは少なく、Schiramランキングアルゴリズムは優れた性能を示したため、カンファレンスで研究賞を受賞しました。 Schirram アルゴリズムの基本原理を紹介します。

まずポアソン分布を思い出してみましょう。

ポアソン分布のパラメータは次のように与えられます。

2 つのポアソン変数の差はシラム分布に従います。

式では次のようになります。

この関数は第一種ベッセル関数と呼ばれます。

統計学のこれらの基本的な概念を使用して、ペアワイズランキングのランキング学習推奨システムを構築しましょう。

まず、ユーザーがアイテムに与える評価はポアソン分布の概念であるとみなします。つまり、ユーザーアイテムの評価値は次の確率分布に従います。

ユーザーがアイテムを評価するプロセスをポアソン過程として説明できる理由は、ユーザーとアイテムの評価にマシュー効果があるためです。つまり、ユーザーの評価が高いほど、評価する人が増えるため、アイテムを評価した人の数を使用して、アイテムの評価の分布を概算できます。アイテムを評価する人の数はどのようなランダムプロセスに従って決まりますか?当然、ポアソン過程を考えます。ユーザーがアイテムを評価する確率は、そのアイテムを評価した人数の確率に似ているため、ユーザーがアイテムを評価するプロセスを近似するには、自然にポアソン過程を使用できます。

ここで、ポアソン過程のパラメータをサンプルデータの統計に置き換えて、次の式を取得します。

以下に、Pariwise Ranking の最大尤度関数の式を定義します。ご存知のとおり、いわゆるペアワイズランキングとは、モデルがデータサンプル内の既知のランキングペア間の関係を最大限に維持できるように、最大​​尤度関数を使用してモデルパラメータを解決することを意味します。

式の R はポアソン分布なので、その差はシラム分布になります。

変数 E は次のように定義されます。

最大尤度関数の損失関数 L に Schirram 分布式を代入すると、次の式が得られます。

変数 E に表示されるユーザー評価値 R を解決するには、行列分解を使用します。行列分解におけるユーザー特徴ベクトル U とアイテム特徴ベクトル V のパラメータは、解くべき変数として使用されます。

ここではまず行列分解の概念を確認します。行列分解の概念は、2010年頃に提案された推奨システムアルゴリズムです。このアルゴリズムは、歴史上最も成功した推奨システムアルゴリズムの1つと言えます。現在でも、行列分解アルゴリズムをオンラインシステムのベースラインとして採用しているレコメンデーションシステム企業は数多く存在します。人気の高い古典的なレコメンデーションアルゴリズムDeepFMの重要な構成要素であるFactorization Machineも、レコメンデーションシステムアルゴリズムにおける行列分解アルゴリズムの改良版であり、行列分解と密接な関係があります。 2007 年の行列分解アルゴリズムに関する画期的な論文「確率的行列分解」があります。著者は統計学習モデルを使用して線形代数における行列分解の概念を再構築し、行列分解に初めて強固な数学的理論的基礎を与えました。

行列分解の基本的な概念は、ベクトルのドット積を使用してユーザー評価行列の次元を削減し、未知のユーザー評価を効率的に予測することです。行列分解の損失関数は次のとおりです。

行列分解アルゴリズムにはさまざまなバリエーションがあり、上海交通大学が提案した SVDFeature はベクトル U と V を線形結合の形式でモデル化し、行列分解の問題を特徴エンジニアリングの問題に変換します。 SVDFeature は、行列分解の分野における画期的な論文でもあります。ペアワイズ ランキングでは、行列分解を適用して、未知のユーザー評価を置き換え、モデリングの目的を達成できます。典型的な適用例としては、ベイジアン ペアワイズ ランキングの BPR-MF アルゴリズムがあり、Schiram ソート アルゴリズムも同じ考え方に基づいています。

確率的勾配降下法を使用して Schirram ソート アルゴリズムを解きます。確率的勾配降下法は、問題を解決する目的を達成するために解決プロセス中に損失関数を大幅に簡素化できるため、損失関数は次の式になります。

確率的勾配降下法を使用して未知のパラメータ U と V を解くと、次の反復式が得られます。

で：

加えて：

で：

未知のパラメータ変数 V の解も同様で、次の式が得られます。

で：

加えて：

で：

アルゴリズムのプロセス全体を次の疑似コードに示します。

アルゴリズムの有効性を検証するために、著者らは MovieLens 1 Million Dataset と LDOS-CoMoDa Dataset でテストしました。最初のデータセットには、6040 人のユーザーと 3706 本の映画の評価が含まれています。評価データセット全体には約 100 万の評価データ ポイントが含まれており、推奨システムの分野で最もよく知られている評価データセットの 1 つです。 2 番目のデータセットはスロベニアからのものであり、インターネット上では珍しいシナリオベースの推奨システム データセットです。データセットには 121 人のユーザーと 1232 件の映画評価が含まれています。著者は、Schiram のランキングを他の 9 つの推奨システム アルゴリズムと比較しました。主な評価指標は、MAE (平均絶対誤差、精度のテストに使用) と Matthew 効果の度合い (主に公平性のテストに使用) でした。

図 1. MovieLens 100 万データセット (MAE メトリック)

図 2. MovieLens 100 万データセット (マシュー効果の度合いの指標)

図 1 および 2 から、Schirram ソートは MAE の点では優れたパフォーマンスを発揮しますが、グリッド検索実験全体を通して他のアルゴリズムよりも優れたパフォーマンスを常に保証できるとは限りません。しかし、図 2 を見ると、公平性指標の点では、Schiram のランキングが他の 9 つの推奨システム アルゴリズムよりはるかに優れていることがわかります。

LDOS-CoMoDa データセットでのアルゴリズムのパフォーマンスを見てみましょう。

図3. LDOS-CoMoDaデータセット（MAEインジケーター）

図4. LDOS-CoMoDaデータセット（マシュー効果の度合い）

図 3 と 4 から、Schiram ソートは公平性指標ではるかに優れており、精度指標でも優れたパフォーマンスを発揮していることがわかります。結論は前回の実験と同様です。

Schiram ランキングは、ポアソン分布、行列分解、ペアワイズ ランキングの概念を組み合わせたもので、推奨システム向けの珍しいランキング学習アルゴリズムです。テクノロジーの分野では、ランキング学習技術を習得している人の数は、ディープラーニングを習得している人の数の1/6に過ぎず、ランキング学習は希少な技術です。そして、レコメンデーションシステムの分野で独自のランキング学習を発明できる人はさらに少ないです。ランキング学習アルゴリズムは、人々を評価予測の狭い視点から解放し、最も重要なのはスコアではなく順位であることを人々に認識させます。公平性に基づくランキング学習は現在、情報検索の分野で非常に人気があり、特に SIGIR などのトップカンファレンスで注目されています。公平性に基づく推奨システムに関する論文は大歓迎であり、読者の注目を集めることを期待しています。

著者について

Funplus人工知能研究所の元所長、王浩氏。彼は、ThoughtWorks、Douban、Baidu、Sina などの企業で技術職および技術幹部職を歴任しました。彼はインターネット企業、金融テクノロジー、ゲーム企業などの分野で12年間働いており、人工知能、コンピューターグラフィックス、ブロックチェーンなどの分野で深い洞察力と豊富な経験を持っています。国際学術会議やジャーナルに42本の論文を発表し、IEEE SMI 2008 Best Paper Award、ICBDT 2020 / IEEE ICISCAE 2021 / AIBT 2023 Best Paper Report Awardを受賞。