Redditのランキングアルゴリズムの仕組み

これは、「Hacker News のランキングアルゴリズムの仕組み」に続く、ランキングアルゴリズムに関する別の記事です。今回は、Reddit の記事ランキングアルゴリズムとコメントランキングアルゴリズムがどのように機能するかについて説明します。 Reddit が使用するアルゴリズムも非常にシンプルで、理解しやすく実装も簡単です。この記事ではそれを詳細に分析します。

[[83916]]

まず、記事のランキングアルゴリズムに焦点を当てます。 2 番目のパートでは、コメントのランキングアルゴリズムに焦点を当てます。Reddit のコメントランキングは、記事のランキングと同じアルゴリズムではありません (これは Hacker News とは異なります)。Reddit のコメントランキングアルゴリズムは非常に興味深いものです。これは、xkcd の作者である Randall Munroe によって発明されました。

記事ランキングアルゴリズムのコードを調べる

Reddit のソースコードはオープンソースであり、どのコードでもダウンロードできます。これは Python で書かれており、コードはここから入手できます。ランキングアルゴリズムは、Python の C 拡張機能を開発するためのプログラミング言語である Pyrex で部分的に実装されています。ここでは主に速度を考慮して Pyrex が使用されています。読みやすくなるように、Pyrex の実装を純粋な Python で書き直しました。

Reddit のデフォルトのランキングは「ホット」ランキングであり、実装コードは次のとおりです。

 #/r2/r2/lib/db/_sorts.pyx から書き直したコード
 
 datetime からdatetime、timedelta をインポート
数学インポートログから
 
エポック = datetime( 1970 , 1 , 1 ) 
 
 epoch_seconds(日付)を定義します: 
     "" "エポックから現在までの秒数を返します。" ""  
    td = 日付 - エポック
     td.days * 86400 + td.seconds + ( float (td.microseconds) / 1000000 )を返します。 
 
 defスコア(アップ、ダウン): 
    上昇と下降を返す
 
 def hot(上昇、下降、日付): 
     "" "ホットな数式。Postgres の同等の関数と一致するはずです。" ""  
    s = スコア(アップ、ダウン)
    順序 = log(max(abs(s), 1 ), 10 )
    符号 = 1   s > 0の場合 それ以外- 1   s < 0の場合 それ以外  0  
    秒 = epoch_seconds(日付) - 1134028003  
    ラウンドを返す(順序 + 符号 * 秒 / 45000 , 7 )

この「ホット」ランキングアルゴリズムの数式は次のようになります (SEOmoz から見つけたものですが、彼らがオリジナルの作者であるかどうかは疑わしいです)。

記事投稿時間がランキングに与える影響

記事の投稿時間がランキングに与える影響は、次のようにまとめられます。

投稿時間はランキングに大きな影響を与えます。新しい記事ほどランキングが高くなります。
記事のランキングスコアは時間の経過とともに低下することはありませんが、新しい記事は古い記事よりも高いスコアを受け取ります。これは、時間の経過とともにスコアが下がる Hacker News のランキングアルゴリズムとは大きく異なります。

以下は、賛成票と反対票が同じ数の記事のランキングスコアを、異なる時期に表示した画像です。

対数強調

Reddit は、最初の数票を重視して「人気」ランキングを作成するために対数関数を使用しています。基本的な原則は次のとおりです。

最初の 10 票の賛成票は、次の 100 票、さらに次の 1,000 票と同様にカウントされます。

効果図は次のとおりです。

対数ブースティングを行わない場合、スコアは次のようになります。

否定的な投票がランキングに与える影響

Reddit は、何かに反対票を投じることができる数少ないサイトの 1 つです。コードからわかるように、記事の「スコア」は次のように定義されています。

アップ投票 – ダウン投票

つまり、次の図のように表すことができます。

この計算方法は、賛成票と反対票の両方が多い記事（非常に物議を醸している記事など）に大きな影響を与え、賛成票が少ない記事よりも低いスコアが付けられる可能性があります。これは、子猫や子犬に関する投稿（およびその他の物議を醸さない記事）が非常に高い評価を受ける理由を説明しています。

#p#

Redditの記事ランキングアルゴリズムの概要

投稿時間は非常に重要な指標であり、新しい記事は古い記事よりも高いスコアが付けられます。
最初の 10 件の賛成票は、次の 100 件と同じようにカウントされます。 10の賛成票と50の賛成票は順位が非常に近い
賛成票と反対票が同程度である物議を醸す記事は、賛成票のみである記事よりも低いランクになります。

Redditのコメントランキングアルゴリズムの仕組み

xkcd の Randall Munroe 氏は、Reddit の「ベスト投稿」ランキングアルゴリズムの発明者です。彼はそれを説明する素晴らしい記事を書きました。

Redditの新しいコメントソートシステム

この記事を読んでみてください。アルゴリズムが非常に簡単に説明されています。この記事の主なポイントは次のとおりです。

「人気」ランキングアルゴリズムはレビューのランキング付けにはあまり効果的ではなく、初期のレビューを過度に優先する傾向があります。
レビューシステムでは、いつ送信されたかに関係なく、最良のレビューを見つけることが目標です。
1927年、エドウィン・B・ウィルソンは「ウィルソンスコア間隔」と呼ばれる優れたアルゴリズムを発見しました。これは「信頼度ソート」に使用できます。
信頼度ランキングでは、記事が受け取った投票数を、世論調査のようにすべての読者のサンプルとして扱います。
「平均評価で並べ替えない方法」という記事では、この信頼性評価アルゴリズムについて詳しく説明されており、ぜひ読んでみる価値があります。

コメントソートコードの詳細な分析

Reddit の信頼ソートアルゴリズムは、ファイル _sorts.pyx に実装されています。私は、Pyrex 実装を純粋な Python で書き直しました (キャッシュ最適化コードは削除しました)。

 #/r2/r2/lib/db/_sorts.pyx から書き直したコード
 
数学からインポートsqrt 
 
 def _confidence(上昇、下降):
    n = 上昇 + 下降
 
     n == 0 の場合: 
        戻る  0  
 
    z = 1.0 # 1.0 = 85 %、 1.6 = 95 %
    phat = float (ups) / n 
     sqrt(phat+z*z/( 2 *n)-z*((phat*( 1 -phat)+z*z/( 4 *n))/n))/( 1 +z*z/n)を返します。 
 
自信(アップ、ダウン): 
    上昇 + 下降 == 0 の場合: 
        戻る  0  
    それ以外： 
         _confidence(上昇、下降)を返す

信頼度ランキングではウィルソンスコア間隔アルゴリズムが使用され、その数式は次のようになります。

上記の式では、さまざまなパラメータの定義は次のとおりです。

pは支持票の割合である
投票総数
z _α/2は正規分布の(1-α/2)分位数である。

上記の紹介を要約すると次のようになります。

信頼度ランキングでは、投票をすべての読者に対するサンプル調査として扱います。
信頼度ランキングでは、レビューの信頼性を暫定的に 85% と評価します。
投票数が増えるほど信頼性が高まる
ウィルソンの区間アルゴリズムは、投票数が少ない場合や確率が低い場合にも適切に対応できます。

Randall 氏は記事の中で、信頼ランキングがどのように機能するかについて、優れた例を挙げています。

コメントに賛成票が 1 つしかなく、反対票が 0 個しかない場合、そのコメントは 100% 承認されますが、投票数が少なすぎるため、システムによってランキングの最下位に配置されます。しかし、賛成票が 10 票で反対票が 1 票しかない場合、システムはそのコメントを、賛成票が 40 票で反対票が 20 票のコメントよりも高いランクにします。つまり、このコメントの賛成票が 40 票の場合、反対票は 20 票未満である可能性が非常に高いと推測できます。このアルゴリズムの最も優れた点は、推論が間違っていたとしても、すでに上位にランク付けされているため、それを証明するためのデータがすぐに得られることです。

公開時間のランキングへの影響: なし!

信頼ソートの利点の 1 つは、コメントが公開された時間が影響を及ぼさないことです (これは、「ホットソート」や Hacker News のランキングアルゴリズムとは異なります)。コメントは信頼性に基づいて評価され、データサンプリングによって計算されます。コメントの投票数が多いほど、その評価は実際のスコアに近くなります。

チャートビュー

信頼ランキングをグラフ化し、それがレビューランキングにどのように影響するかを見てみましょう。 Randall の例を見てみましょう。

ご覧のとおり、信頼ランキングではコメントが何票獲得したかは考慮されず、支持率とデータサンプルサイズに重点が置かれます。

ソート以外の用途

Evan Miller 氏が述べたように、Wilson のスコア間隔アルゴリズムはランキング以外のアプリケーションでも使用できます。彼は 3 つの例を挙げています。