カーネルCF: 推薦システムのための最適リコール戦略

著者 | 王昊

レビュー | Chonglou

レコメンデーションシステムは誕生以来、特にインターネット分野で幅広い注目を集めており、企業にとって金の卵を産む白鳥となっています。計算してみましょう。自社のおすすめ商品の1日あたりのPVが500万だとすると、レコメンドシステムによってユーザーのクリック率が1％上昇し、1日あたり5万PVの増加となります。 Google 広告の平均 CPC は 2 ドルです。この計算によると、推奨システムにより、ウェブサイトの顧客獲得コストが毎日 10 万ドル節約され、年間では 3,650 万ドルになります。これは実に膨大な数であり、大規模なウェブサイトやアプリが推奨システムに集まっている理由がわかります。

推奨システムが中国に導入されて以来、多くのエンジニアは推奨システムをリコールランキングとその他の段階に分割することを好んでいます。実際、いわゆるリコールとは、アルゴリズムまたはルールを使用して、推奨アルゴリズムを実行するために最初にデータのサブセットをフィルタリングし、次にアルゴリズム実行の次の段階に進むことを指します。著者は大手インターネット企業に勤務していた頃、まずリコールに協調フィルタリングを使用し、次にソートにランキング学習（ベイジアン・パーソナル・ランキング/協調的 Less is More フィルタリング）を使用して、良好な結果を達成しました。

リコール戦略は何千種類もあり、「最善のリコール戦略はあるのだろうか」と疑問に思う人もいるかもしれません。最適化理論を通じて最適なリコール戦略を計算する方法はあるでしょうか?答えはイエスです。 Ratidar Technologies LLCは、国際学術会議CAIBDA 2022で「Kernel-CF: ソーシャルネットワーク分析とカーネルスムージングによる適切な協調フィルタリング」と題する論文を発表し、データ視覚化アルゴリズムとノンパラメトリック統計手法を使用して推奨システムの最適なリコール戦略を計算する方法を紹介しました。以下に関連コンテンツを詳しく紹介します。

まず、ForceAtlas-2 アルゴリズムとは何かを紹介します。 ForceAtlas-2 は 2014 年に PLoS の論文に掲載されました。論文のタイトルは「ForceAtlas2、Gephi ソフトウェア用に設計された便利なネットワーク可視化のための連続グラフ レイアウト アルゴリズム」です。この論文では、物理学の概念を借用して複雑なネットワークの可視化を実現する方法について説明します。関連するアルゴリズムは、一般的に使用されているソーシャル ネットワーク分析ソフトウェア Gephi に統合されています。

ForceAtlas-2 は、ソーシャル ネットワーク内のポイント間の相互作用には、引力と反発の 2 種類があると考えています。アトラクションの定義は次のとおりです。

反発力は次のように定義されます。

ここで、d は距離関数であり、deg はビュー内のノードの次数です。観察すると、距離が近いほど引力は小さくなり、距離が遠いほど引力は大きくなることがわかります。ノードの次数が大きいほど反発力は大きくなり、ノード間の距離が大きいほど反発力は小さくなります。 ForceAtlas-2 は、ソーシャル ネットワークにおけるこれら 2 つの力の相互作用をシミュレートし、複雑なソーシャル ネットワークをシンプルで美しい 2 次元空間で表現します。

では本題に入りましょう。協調フィルタリング アルゴリズムに最適なリコール戦略を設計する方法について説明します。ここでは、ユーザーベースの協調フィルタリングを例に挙げます。アイテムベースの協調フィルタリングアルゴリズムモデルの分析はこれと同様です。ユーザーベースの協調フィルタリング アルゴリズムの式は次のとおりです。

ユーザーベースの協調フィルタリングの基本的な考え方は、ユーザーに類似したユーザーの好みリストに基づいて、現在のユーザーが見たことのないアイテムを推奨することです。ここで問題があります。計算のために、ユーザーに類似するどのユーザーを選択すればよいのでしょうか?すべてのユーザーですか?あるいは、最適なリコール戦略はあるのでしょうか?これは、Kernel-CF アルゴリズムで議論される問題です。 Kernel-CF アルゴリズムの論文のダウンロード アドレスは、こちらです: https://arxiv.org/ftp/arxiv/papers/2303/2303.04561.pdf 。以下ではこのアルゴリズムを詳しく紹介します。

まず、すべてのユーザー ペア間の類似度を計算し、類似度マトリックスを距離マトリックスに変換し、ForceAtlas-2 を使用して距離マトリックスを 2 次元空間にマッピングします。新しいソーシャル ネットワークでは、ユーザーベースの協調フィルタリングは実際にはノンパラメトリック統計における Nadaraya-Watson カーネル回帰問題であり、必要なのは最適なカーネル半径を計算することであることがわかりました。これは、学者たちがプラグイン方式で解決した問題です。 1 次元の Nadaraya-Watson カーネル回帰では、最適なカーネル半径は次のように計算されます。

ここで、2 次元の場合を考えてみましょう (X 軸と Y 軸の両方に変数があります)。

で：

プラグイン方式を使用して、協調フィルタリングにおける最適リコール問題を完全に解決できることがわかります。次の図は、ForceAtlas-2 に基づいて次元削減された協調フィルタリング入力データ (LDOS-CoMoDa データセット) の部分表示です。最適なリコール戦略により、多くのコンピューティング リソースを節約できることがわかります。

現在、まだ 1 つの問題が残っています。つまり、プラグイン方式を使用して協調フィルタリング アルゴリズムの最適リコールを解決するプロセスでは、r や f など、統計的手法で近似する必要がある未知の量がいくつか存在します。 r 関数の定義は次のとおりです。

r は最小二乗法の一般的な形式で近似できます。私たちは次のような仮定を立てました。

f をデータによって生じる確率分布として定義します。確率密度推定によってfを推定します。

ここでHは次のように推定されます。

ここで共分散行列です。上で説明した結果を組み合わせると、次のアルゴリズム フロー (疑似コード) が得られます。

この論文では、情報視覚化とノンパラメトリック統計手法を使用して、協調フィルタリングにおける最適リコール問題を計算する方法について詳しく説明します。アルゴリズム内の式の導出は複雑ですが、全体的なプロセスは非常に実現可能です。読者が記事内のアルゴリズムの詳細に精通すれば、そのアルゴリズムを適切に実装できるようになります。このアルゴリズムの名前は Kernel-CF です。これは、カーネル回帰の知識を活用し、また、解決する問題が協調フィルタリングであるためです。

Kernel-CF アルゴリズムは、実用的な機械学習の問題を解決する際には、知恵を結集し、幅広く読書し、他の分野の主題知識を最大限に活用して、推奨システムにおける長年の問題を包括的に解決する必要があることを示しています。ノンパラメトリック統計は、統計学を専攻する上級生や統計学の大学院生が学ぶものです。アルゴリズム エンジニアである私たちは、日常的に関連知識に触れる機会はないかもしれませんが、頻繁に図書館に行って本を借りたり (中国国立図書館には何百万人ものカード所有者がいます)、本を買って読んだりすることを妨げるものではありません。数学のしっかりした基礎があれば、アルゴリズム作業に翼を与え、山や尾根を飛び越えることができます。

著者について

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