twitterの推薦アルゴリズムの概要について

概要

ツイッター社がTwitterのレコメンドの仕組みを公開して話題になっている。
以下が公式に公開された技術ブログとGiuHub上のソースコードである。

技術ブログ：https://blog.twitter.com/engineering/en_us/topics/open-source/2023/twitter-recommendation-algorithm
GitHub：https://github.com/twitter/the-algorithm

TwitterのUIは「Following」と「For You」の2つあり、「Following」は従来からある自分がフォローしているユーザーのツィートが時系列に流れてくるものであり、今回公開されたアルゴリズムは「for you(あなたへおすすめ)」に表示される部分のアルゴリズムとなる。

Twitterでは毎日5億ものツイートが投稿されており、その中から好みのツイートを選んで表示するのは大変骨の折れる作業となる。それらを実現するアルゴリズムの概要は以下のようになる。

上図の流れとしてはData(データ取得)→Feature(特徴量作成)→Home Mixer(推薦ステップ)となっている。ここで最後のHome Mixerに関しては、上述のtwitter社の技術ブログでは3つのステップ(Candidate Sourcing、Ranking、Heuristics & Filtering)からなるとされている。以下にそれらについて述べる。

Data(データ取得)について

<概要>

使用するデータに関しては主に以下の3つからなるとされている。

• Social graph
• Tweet engagement
• User data

以下にそれらの詳細について述べる。

<Social graph>

まずSocial graphについて。Social graphは、ユーザー間の相互関係を表すグラフ構造となる。このグラフは、ユーザーとそのフォロワーやフォローしているユーザーの関係を示すものとなり、フォロワーは、特定のユーザーのアカウントをフォローしているユーザーで、フォローしているユーザーは、特定のユーザーのアカウントをフォローしているユーザーとなる。

TwitterのSocial graphは、ユーザー間のつながりや関係性を分析するために使用される。これは例えば、あるユーザーのフォロワーの状況を把握することで、そのユーザーの影響力や人気度を測ることができ、また、特定のトピックに関心を持つユーザーや特定のユーザーグループを特定するためにも利用されることもある。

Social graphは、TwitterのAPIを使用してアクセスできる情報の一部であり、Twitter APIを使用すると、特定のユーザーのフォロワーやフォローしているユーザーのリストを取得したり、特定のユーザーと他のユーザーとの関係を調査したりすることができる。ただし、最近のプライバシーの考慮やセキュリティ上の理由から、TwitterはAPIの利用に制限を設けている場合があるため、一般のユーザーがSocial graphの完全なビューを取得することは難しい場合がある。

<Tweet engagement>

次にTweet engagementについて。Tweet engagementは、ツイートがどれだけの関心や相互作用を引き起こしたかを示す指標となる。Tweet engagementは、以下のようないくつかの要素に基づいて計算される。

• リツイート(Retweets): リツイートは、ツイートが他のユーザーによってリツイートされた回数で、ユーザーが興味を持ったツイートを自分のフォロワーと共有する方法となる。
• いいね(Likes): いいねは、ツイートがいいねされた回数で、ユーザーがツイートに対して好意的な反応を示す方法となる。
• 返信(Replies): 返信は、ツイートに対する返信の数で、ユーザーがツイートにコメントや応答をする方法となる。
• メンション(Mentions): メンションは、ツイート内で他のユーザーをメンションした回数で、ユーザーが他のユーザーに対してツイートで言及する方法となる。

これらの要素を総合的に考慮して、Tweet engagement数が計算されます。エンゲージメント数が高いほど、ツイートが多くの人々によってリツイートやいいねされ、話題を引き起こしたことを示す。

Tweet engagement数は、ツイートのパフォーマンスや影響力を測るために使用されます。また、マーケティングキャンペーンやソーシャルメディア戦略の評価にも役立つ。企業や個人がTweet engagementを増やすためには、興味を引くコンテンツの提供やフォロワーとの対話の促進などが重要となる。

<User data>

最後にUser dataについて。TwitterのUser dataは、Twitterのユーザーアカウントに関連する情報を指す。以下にいくつかの一般的なUser dataについて述べる。

• プロフィール情報: ユーザーが自己紹介や興味関心、場所などを記載するためのプロフィール情報が含まれる。これには、ユーザー名、表示名、バイオグラフィ、プロフィール写真、ヘッダー画像などが含まれる。
• ツイート: ユーザーが投稿したツイートのデータが含まれる。ツイートには、本文、画像、動画、URLなどが含まれる場合があり、ツイートの投稿日時やいいね数、リツイート数などの統計情報も含まれることがある。
• フォロワーとフォローしているユーザー: ユーザーがフォローしている他のユーザーやユーザーのフォロワーの情報が含まれる。これにより、ユーザー間の関係やつながりを分析することができる。
• メンションや返信: ユーザーが他のユーザーをメンションしたり、他のユーザーから返信を受けたりした情報が含まれる。これにより、ユーザー間のコミュニケーションや対話のパターンを把握することができる。
• ユーザーアクティビティ: ユーザーのアカウント上のアクティビティ情報が含まれる。これには、ログイン日時、ツイートの閲覧、いいねやリツイートの履歴などが含まれる。

TwitterのUser dataは、一般のUser dataには制限されており、APIを通じて一部のデータにアクセスできるが、APIの利用には一定の制限や認証が必要となる。また、プライバシーポリシーや利用規約に基づいて、ユーザーデータの取得や使用に制約があることに留意する必要がある。

Feature(特徴量作成)について

<概要>

上記のデータを利用し、twitterでは以下の6種類のコンポーネントでFeatureを作成している。

• GraphJet
• SimClusters
• TwHIN
• RealGraph
• TweepCred
• Trust & Safety (T&S)

以下にそれらについて詳細に述べる。

<GraphJet>

GraphJetは、ソーシャルネットワーク上のリアルタイムグラフ検索およびランキングエンジンとなる。Facebookが開発したGraphJetは、大規模なソーシャルグラフ内で高速で効率的なデータ検索、推薦、およびランキングを可能にしている。

GraphJetの特徴的な機能の1つは、逆リンク索引（Inverse Link Indexing）を使用していることで、逆リンク索引は、あるノードが別のノードにリンクされている回数を追跡し、この情報を使用してネットワーク内のノードを高速に検索およびランキングすることができる。これにより、ソーシャルネットワーク上で人々のつながりを分析し、関連するコンテンツやユーザーを特定することが可能になる。

GraphJetは、以下のようなシナリオで有用となる。

• コンテンツの検索とフィルタリング: GraphJetは、ソーシャルグラフ内のコンテンツを効率的に検索できる。例えば、特定のトピックやキーワードに関連する最も人気のある投稿やユーザーを検索することができる。
• フィードのパーソナライズ: GraphJetは、ユーザーのソーシャルグラフや関心を分析し、最適なフィードの表示順序や推薦コンテンツを決定するために使用される。ユーザーにとって最も関連性の高い情報を提供することができる。
• ユーザーランキング: GraphJetは、ソーシャルグラフ内のユーザーをランキングすることができる。この機能は、インフルエンサーの特定、トレンドの発見、または特定の属性を持つユーザーのグループを特定するために使用されることがある。

GraphJetは、リアルタイムのデータ処理と高速な検索を実現するために、効率的なアルゴリズムとデータ構造を使用しており、大規模なソーシャルネットワーク上での高いパフォーマンスとスケーラビリティが実現されている。

<SimClusters>

SimClustersは、Facebookが開発したオープンソースの類似性クラスタリングツールとなる。SimClustersは、特徴ベクトルを使用してデータをクラスタリングを行うものとなる。入力となるデータセットは、たとえば、文章の埋め込み表現や画像の特徴ベクトルなどのような、各データポイントが数値ベクトルで表される場合に適している。SimClustersを用いることで、大規模なデータセットに対して高速で効率的なクラスタリングを行うことができるようになる。

SimClustersの主な特徴は以下となる。

• 高速なクラスタリング: SimClustersは、非常に大規模なデータセットに対しても高速なクラスタリングを実行できる。これは、効率的なアルゴリズムと並列処理を組み合わせることによって実現される。
• スケーラビリティ: SimClustersは、水平方向にスケールアウトすることができる。つまり、複数のマシンやクラスタを使用して処理を並列化し、高速かつ大規模なデータセットに対応することができる。
• カスタマイズ可能な類似度メトリック: SimClustersでは、類似度メトリックをカスタマイズすることができる。異なるタイプのデータに対して適切な類似度メトリックを使用することで、より正確なクラスタリング結果を得ることができる。

SimClustersは、例えば、自然言語処理での、文章の類似性に基づいた文書のクラスタリングや、画像処理での、画像の特徴ベクトルを使用して似たような画像をグループ化するなど、さまざまな応用分野で利用されている。SimClustersはオープンソースのプロジェクトとして公開されており、FacebookのGitHubリポジトリから利用することができる。

<TwHIN>

TwHINは複数種類のインタラクションをまとめて推薦に活用するアルゴリズムであり、Twitterで可能なインタラクション（いいね、RT、follow、など）の単位で、個別にユーザーやTweetのEmbeddingを計算している。 個別の種類のEmbeddingが求められたら、インタラクションの種類ごとにk-meansでクラスタリングを行い、クラスタのEmbeddingを計算する。 最後に、ユーザーやTweetについて、それらとインタラクションが発生しているクラスタの寄与度に応じてEmbeddingに荷重を掛けることで、複数のインタラクションを考慮した1つのEmbeddingを計算している。こうして複数種類のインタラクションに基づいて計算されたembeddingが得られ、これを用いてFRSが行われている。

以下添付の論文のabstractを転記する。「Twitterなどのソーシャルネットワークは、ノードがドメインエンティティ（ユーザー、コンテンツ、広告主など）を表し、エッジが多くのエンティティ相互作用（例えば、ユーザーがコンテンツを再共有したり、他の人を「フォロー」したりする）のうちの1つを表す、異種情報ネットワーク（HIN）を形成する。複数の関係タイプからの相互作用は、単一の関係では完全に捕らえられないソーシャルネットワークエンティティに関する貴重な情報をコード化することができる。例えば、ユーザーがフォローするアカウントの好みは、ユーザーとコンテンツのエンゲージメント相互作用と彼らがフォローする他のユーザーの両方に依存する場合がある。この研究では、Twitter HIN（TwHIN）のエンティティの知識グラフ埋め込みを研究している。これらの事前訓練された表現が、パーソナライズされた広告ランキング、アカウントフォロー推薦、攻撃的コンテンツ検出、検索ランキングといった多様な下流推薦および分類タスクにおいてオフラインおよびオンラインで大きな改善をもたらすことを示している。また、エンドツーエンドでのモデル遅延を低減するための圧縮や、バージョン間のパラメータドリフトへの対応など、業界規模のHINエンベッディングを展開する際の設計上の選択と実用上の課題についても対応している。」

<RealGraph>

おすすめを見るユーザーとおすすめに表示されうるTweetしたユーザーとの関係性もスコア影響を与えるため、RealGraphというアルゴリズムが適用されている。

ユーザーがフォローしているユーザーの中でも、直近のインタラクション数などによって関係性の強さには強弱があると考えられ、 RealGraphではその関係性の強さを推定し、近い将来インタラクションが発生しそうなユーザーに高いスコアを割り当てている。

内部では、直近のユーザーの行動の情報をもとに、近い将来ユーザー間のインタラクション（いいね、replyなど）が発生しそうかをロジスティック回帰によって確率を予測することで、ユーザー間の関係性を推定している。

<TweepCred>

Twitter内でのユーザーの評判を計算するためのPage-Rankとなる。PageRankの詳細は”ページランクアルゴリズムの概要と実装“を参照のこと。

<Trust & Safety (T&S)>

推薦アルゴリズムにおけるTrust & Safety (T&S) は、ユーザーに対して安全で信頼性の高い推薦を提供するための概念となる。T&Sは、プラットフォームやサービスの利用者にとって害やリスクを最小限に抑えることを目指しており、以下のような具体的な取り組みがある。

• ユーザーエクスペリエンスの向上: T&Sは、ユーザーがサービスを利用する際に安心感を持てるようにするために重要となる。推薦アルゴリズムは、ユーザーの過去の行動や好みに基づいてパーソナライズされたコンテンツを提供するため、その過程で不適切なコンテンツや有害な情報が混入する可能性がある。T&Sの考え方を取り入れることで、ユーザーが不快や危険を感じるようなコンテンツが表示されるリスクを低減することができる。
• プラットフォームの信頼性向上: T&Sは、プラットフォームの信頼性を高めるためにも重要となる。適切なT&S対策を講じない場合、ユーザーが有害なコンテンツや詐欺、スパムなどに遭遇する可能性が高まる。これにより、プラットフォームの評判が損なわれ、ユーザーの離反や悪影響が広がる可能性がある。T&S対策を実施することで、プラットフォームの信頼性を高め、ユーザーのロイヤルティを維持することができる。

Home Mixer(推薦ステップ)

<概要>

Twitterの推薦では、一般的な推薦のアルゴリズムであるTwo-stage recommendation(二段階推薦)が用いられている。Two-stage recommendation(二段階推薦)は、推薦システムのアプローチの一つとなる。

通常の推薦システムは、ユーザーに個別のアイテムを推薦するだけでなく、そのユーザーが興味を持つ可能性のある関連アイテムをも推薦することを目的としているのに対して、Two-stage recommendationでは、第一段階として、ユーザーの興味や嗜好をモデル化するための特徴やフィードバックを収集し、ユーザーの過去の行動やプロフィール情報、評価などが考慮され、ユーザーの好みや関心を理解し、ユーザーの個別のニーズに対応した推薦が行う。

次に、初段階で得られた情報を基にして、関連アイテムや推薦リストを生成するため処理が行われている。この処理では、ユーザーの特徴に基づいて、より具体的な推薦が行われることとなる。これらにより、初段階ではユーザーの一般的な嗜好をモデル化するのに対し、二段階目では個別のコンテキストや要求を考慮して、よりパーソナライズされた推薦が可能となる。

Two-stage recommendationの利点は、個別のユーザーの嗜好を考慮したパーソナライズされた推薦が行えることとなる。Two-stage recommendationは、一段階のアプローチに比べて、より詳細な情報を用いて推薦を行うことができ、また初段階での情報収集により、データスパースネス（データが不十分な状況）の問題にも対処できる可能性がある。ただし、Two-stage recommendationはより複雑な処理を必要とするという注意点がある。

このアプローチを用いてtwitterでは以下のステップでの推薦を行なっている。

• Candidate Sourcing (1st stage)
• Raking (2nd stage)
• Heuristics & Filtering

以下にそれらに対する詳細について述べる。

<Candidate Sourcing(候補アイテムの収集)>

推薦アルゴリズムにおけるCandidate Sourcing(候補アイテムの収集)は、推薦システムがユーザーに対して推薦するための候補アイテムを収集するプロセスや手法となる。このステップは、ユーザーに関連性の高いアイテムを提供するために重要な役割を果たしている。Candidate Sourcingの方法は、特定の推薦システムの設計や目的に応じて異なる場合があるが、以下のようないくつか一般的な手法が存在する。

• ユーザーの履歴データを利用する: このアプローチでは、ユーザーの過去の行動履歴や購買履歴を分析し、その情報に基づいて関連性の高いアイテムを収集するものとなる。これは例えば、ユーザーが過去に購入した商品や閲覧したコンテンツと似たアイテムを推薦するなどになる。
• コンテンツベースのフィルタリング: このアプローチでは、アイテム自体の特徴や属性に基づいて、ユーザーの好みに合ったアイテムを収集するものとなる。これは例えば、映画のジャンルや書籍のカテゴリに基づいて関連性の高いアイテムを選択するなどになる。
• 協調フィルタリング: このアプローチでは、ユーザー間の類似性や共通の嗜好を利用して、他の類似したユーザーが好むであろうアイテムを収集するものとなる。これにより、ユーザーがまだ評価していないアイテムを推薦することができる。
• リアルタイムなデータフィード: このアプローチでは、最新のトレンドや人気のあるアイテム、新着アイテムなどをリアルタイムに収集し、推薦候補として提供するものとなる。

これらの手法は単独で使用されることもあるが、通常は複数の手法を組み合わせることでより精度の高い候補アイテムの収集を可能としている。推薦アルゴリズムの目的や制約、データの特性に応じて、最適なCandidate Sourcingの手法を選択することが重要となる。

twitterの場合は、Candidate Sourcingとして各ユーザーに対して1500件の「おすすめ候補」のTweetが選定される。Candidate Sourcingでは、自分がFollowしているところから（InNetwork）とFollowしている外（Out-of-Network Sources）からの両方から推薦候補を選定しており、これらは、それぞれおおよそ50%ずつとなっている。

Candidate Sourcingを処理するコンポーネントとして以下の4種類がある。

• search-index
• cr-mixer
• user-tweet-entity-graph (UTEG)
• follow-recommendation-service (FRS)

以下にそれらについて述べる。

<search-index>

検索インデックス(search index)とは、データの高速な検索をサポートするために使用されるデータ構造であり、主にテキスト検索エンジンやデータベースなどのシステムで使用されるものとなる。検索インデックスの種類としては、キーと値のペアを格納するデータ構造であるハッシュテーブル、各ノードが最大2つの子ノードを持つツリー構造であるバイナリツリー、複数の子を持つ多分岐の平衡木であるB木、ハッシュ関数を使用してデータを格納するデータ構造であるハッシュインデックス等がある。

twitterのアルゴリズムの中では、検索インデックスを使用して検索された推薦候補であり、ユーザーがフォローしているユーザーのリストに基づいて、フォロー中のユーザーのTweetを取得することで候補集合を作成するものとなる。

この検索はEarlyBirdというTwitter内のTweet検索システムを使ったlight rankerによって優先順位付けされています。 フォロー中のユーザーのTweetに限定されるといってもそれでも数が多いので、ここから更に静的・動的特徴に基づいてスコアリングが行われ、上位のTweetが選ばれるものとなる。

<cr-mixer>

cr-mixerは、たくさんのアルゴリズムによるCandidateを統合することでCandidateを作成するコンポーネントになっている。

<user-tweet-entity-graph (UTEG)>

User-Tweet-Entity Graph(UTEG)は、Twitterのデータから生成されるグラフ構造であり、このグラフは、ユーザー、ツイート、およびツイート内のエンティティ（キーワード、ハッシュタグ、メンションなど）の関係性を表現しているものとなる。

User-Tweet-Entity Graphでは、ユーザーが作成したツイートにさまざまなエンティティが含まれる形となっている。グラフのノードは、ユーザー、ツイート、およびエンティティを表し、エッジはそれらの間の関係性を示す。これはたとえば、ユーザーノードからツイートノードにエッジがあり、ツイートノードからエンティティノードにエッジがあるといった形式となる。

このUser-Tweet-Entity Graphは、Twitter上の情報の関連性をモデル化し、ユーザー間のつながりやトピックの傾向を分析するために使用される。これは例えば以下のような洞察を得ることができるものとなる。

• ユーザーの関係性の分析: グラフを通じて、ユーザー間のフォロー関係や相互のつながりを可視化し、ユーザーの社会的ネットワークを理解することができる。
• トピックの識別と分析: エンティティノードを使用して、特定のトピックやキーワードに関連するツイートを抽出し、トピックの傾向や話題の拡散を分析することができる。
• イベントの検出: ツイート間の関係性やエンティティの共起を分析して、特定のイベントやトレンドの検出を行うことができる。

<follow-recommendation-service (FRS)>

Follow Recommendation Service(フォロー推薦サービス)は、ソーシャルメディアプラットフォームやソーシャルネットワーキングサイトで利用される推薦システムの一種であり、このサービスは、ユーザーが興味を持つ可能性のある他のユーザーを推薦することを目的としたものとなる。

フォロー推薦サービスは、以下のような手法やアルゴリズムを使用して実装される。

• ユーザーの行動履歴: ユーザーが過去にフォローしたユーザーや関連アカウントを分析し、その情報に基づいて類似した興味を持つユーザーを推薦している。これは例えば、共通のフォロー関係を持つユーザーや類似した興味関心を持つユーザーを推薦するなどがある。
• コンテンツベースの推薦: ユーザーのプロフィール情報や投稿内容、興味関心に基づいて、類似した属性を持つ他のユーザーを推薦する。これにより、ユーザー同士が共通の関心事や活動を共有できる可能性がある。
• ソーシャルグラフ分析: ユーザー間のフォローグラフやソーシャルネットワークを分析し、ユーザーの関係性やつながりを考慮して推薦を行う。これは例えば、友人やつながりの強いユーザーがフォローしているユーザーを推薦するなどになる。
• リアルタイムなデータ: 最新のトレンドや人気のあるユーザーをリアルタイムに収集し、その情報を基に推薦を行う。

twitterの場合は、フォローすべきアカウント・そのアカウントからのツイートを取得すねものとなる。 Twitterには、Who to followというまだフォローしていないユーザーをおすすめする仕組みがあり、それを用いてユーザー及びそのユーザーによるツイートを取得している。

内部的にはおすすめユーザーに関するCandidate Generation -> Filtering -> Ranking -> Transform -> Truncationといった一連の処理が行われるようで、GraphJetの他にはSimClustersやTwHINといったアルゴリズムが利用されている。

<Raking>

推薦候補が得られたら今度はこれらを改めて優先順位付けしてくことになる。 コンポーネントとしてはheavy-rankerと呼ばれているものとなる。

Rankingに使用している特徴量としてはAggregate/NonAggregate/Embedding Featuresの3つに大別されており、そのなかで更に細かく特徴量定義されて使用されている。詳細の説明は以下にある。

ランキングに使用しているアルゴリズムとしては、そのほかにMaskNetと呼ばれるCTR予測モデルを使用している。Click-Through Rate(CTR)は、オンライン広告やウェブコンテンツのパフォーマンスを測定するための指標の一つであり、広告やコンテンツを表示した回数に対して実際にクリックされた回数の割合を表すものとなる。一般的に、CTRは以下のような形式で表される。

\[CTR\ =\ (\ クリックされた回数\  ÷\  広告やコンテンツの表示回数\ )\  ×\ 100\]

CTRは、広告やコンテンツの効果や関心を測定するために重要な指標であり、高いCTRは、広告やコンテンツがユーザーの関心を引き付け、クリックアクションを促すことを示唆する。一般的に、高いCTRを持つ広告やコンテンツは、より効果的なマーケティングやコンテンツ戦略の指標とされている。

CTRは、デジタルマーケティングやオンライン広告におけるキャンペーンのパフォーマンス評価や広告収益の評価に利用されており、また、A/Bテストやマーケティングキャンペーンの最適化においても重要な指標となっている。

このCTR予測モデルを用いたMaskNetの特徴的な点は、instance-guided maskと呼ばれる特徴量ごとの重要度を抽出する層が使用されていることで、このinstance-guided maskにより、重要視する特徴量を自動で調整し、特徴量の相互作用を効率よく学習している。

<Heuristics & Filtering>

Heuristics & Filteringで作られたランキングに対して、バランス良く多様なフィードを作成するために、調整を入れるものとなり、以下のような機能が含まれている。

• ブロックやミュートしたツイートの除外
• 一人の人が連続してFeedに登場しないように、ユーザーの多様性の確保
• In/Out of Networkのバランスを取るように調整
• Feedbackに基づいて、一部のツイートのスコアを下げる
• フォローしている誰かがそのツイートに関与しているか、ツイート主をフォローしているかを保証する（推薦の品質保証の意図）
• スレッドになっているツイートは、もとのツイートからつなげる(文脈の可視化)
• 編集済みのツイートは最新のものに変える

以上、twitterの推薦アルゴリズムについて述べた。これらからわかるように、非常に沢山の推薦アルゴリズムを利用していることがわかる。尚、上述に現れた推薦技術の基本的な理論や具体的な実装に関しては”推薦技術“を参照のこと。