DEIM Forum 2019 B2-4

ユーザとトピックを指定する Twitter 検索における最適な擬似適合フィードバック文書数の動的決定
片岡

大祐†

山肩

洋子†

田島

敬史†

† 京都大学大学院情報学研究科 〒 606–8301 京都府京都市左京区吉田本町
E-mail: †{kataoka@dl.soc.i.kyoto-u.ac.jp, yamakata@dl.soc.i.kyoto-u.ac.jp, tajima@i.kyoto-u.ac.jp}
あらまし

本論文では，Twitter 検索において「学生」による「就活」に関する投稿のように指定したタイプのユー

ザによる任意のトピックに関する投稿をユーザプロファイル推定を用いて検索する手法を提案する．従来の擬似適合
フィードバックでは，検索結果の上位の文書を適合文書と仮定するため，フィードバックの質はクエリと初期検索結果に依存してしまう．そのため，本研究ではユーザプロファイル推定のために，「学生」などのユーザ種別を表す語をクエリとした検索による検索結果の擬似適合フィードバックを用いて修正したクエリを用いて，指定したユーザタイ
プに対する適合度に基づいて初期検索結果をリランキングする．さらに，擬似適合フィードバックのための最適な文書数を検索結果をクラスタに分割することで動的に決定する．
キーワード マイクロブログ検索 擬似適合フィードバック テキストマイニング
P2 の具体例を挙げると，例えば自分が学生や社会人であると

1. は じ め にいった情報を各投稿中に記載することは少ない．また，ソフト（注 1）

近年，Facebook（注 2）などのソーシャルネット

ウェアエンジニアや京都大学といった具体的な所属名と比べ，ワーキングサービス（SNS）の普及により，誰もが気軽に情報をや Instagram

学生や社会人といった情報はプロファイル中に記述されにくい（注 3）

発信したり，共有できるようになった．その中でも，Twitter

は代表的な SNS の 1 つであり，3 億人を超えるアクティブユー
ザ数を有している．

ため，プロファイルの検索から得ることも難しい．
本論文では，片岡 [1] らが提案した手法から構想を得て，フィードバックのための最適な文書数の決定手法を組み込んだユーザ

Twitter は情報拡散が早いという特徴があるため，企業はイ

タイプを表すクエリによる検索結果からの擬似適合フィード

ベントや新商品のプロモーションを Twitter 上で行うことがよ

バックを用いた Twitter 検索を提案する．片岡 [1] らの手法でくある．また，Twitter では，日記のように日常の体験・経験

は，対象のユーザタイプとその逆のユーザタイプを表す 2 つのを投稿することが多く，実際にそのイベントに参加した人や新クエリによる検索を用いて作成したデータセットをもとにモデ商品を購入した人の生の声を Twitter 上で収集することがでル学習を行い，トピックを表すクエリを用いた Twitter 検索にきるため，Twitter はマーケティングにも使用されている．一より得られた検索結果をクラス分類の信頼度をもとにリランキ

方，同じ商品やコンテンツに対する評判が年代や性別，職業なングした．本手法では，ユーザプロファイル推定方法として，

どのプロファイルによって異なるため，収集した投稿をユーザ

ベクトル空間モデルを用いて「学生」といった対象のユーザタ

タイプごとにカテゴライズすることに対しても需要がある．例

イプを表すクエリと Twitter の各投稿から計算されるベクトル

えば，新しく発売された iPhone X が，若者は「使いやすい」ととの類似度を計算し，そのスコアの降順にトピックを表すクエ

好評だったとしても，年配者には「使いにくい」という感想がリを用いた Twitter 検索により得られた検索結果をリランキ多い場合がある．そこで，本論文では，投稿者の属性を指定しングする．ユーザタイプを表すクエリは，「学生」と「社会人」

た検索・ランキングを可能とする手法を提案する．

のように，対象のユーザタイプとその対となるキーワードによしかし，既存の Twitter の検索では以下の問題点が存在する．

P1: 投稿文がショートテキストのため，キーワードを追加した場合，適合率は増加するが，再現率が通常の Web 検索よりる検索を行い，それらの検索結果の擬似適合フィードバックに
よって得られる．

Montgomery ら [2] は，異なる重み付け手法を用いる 9 つのも低くなってしまうシステムを用いて実験を行い，擬似適合フィードバックにおいP2: 投稿者の性別や年代，所属などの情報が投稿文中に記述てフィードバックに用いる最適な文書数はシステム依存で異なされることは稀であるため，属性を表すキーワードを追加してることを示した．そこで本手法では，フィードバックに用いるも適合率・再現率の向上は難しい

文書集合と，用いない文書集合それぞれの単語の出現分布を比較することで，擬似適合フィードバックに用いる文書数を動的（注 1）：https://www.facebook.com（注 2）：https://www.instagram.com（注 3）：https://twitter.comに決定する．具体的には，各集合内の平均ベクトルを計算し，内積をとることでスコアを算出し，そのスコアが最小になるような文書数を決定する．

で，正例・負例を付与する適合フィードバックを導入した．

提案手法の有効性を評価するために，5 種類のトピックを表

擬似適合フィードバックの文書数のようなパラメータのすクエリと 6 種類のユーザタイプを表すクエリの計 30 件からチューニングを試みた研究も数多く存在する．擬似適合フィーなるテストコレクションを作成した．

ドバックにおいて最適な文書数がシステムごとに異なることは我々の主な貢献を以下にまとめる．1) Twitter で任意の検索

Montgomery ら [2] によって示されている．Tao ら [?] は，統計結果から，特定のユーザタイプに該当する投稿を上位にランキ

的言語モデルに基づいて元のクエリモデルからフィードバック

ングする手法を提案した．2) 上記の条件下において，擬似適

言語モデルを推定し，EM アルゴリズムを用いてパラメータを合フィードバックの際に用いる文書数をクラスタ分割の考え方推定した．Sakai ら [15] は，擬似適合フィードバックにおいてを用いて動的に決定する手法を提案した．3) テストコレクショ

単に上位の文書をフィードバックに用いるのではなく，関連度

ン，および，提案手法の評価の枠組みを構築し，提案手法の有が高いと予測される文書をサンプリングする手法を提案した．

用性を示した．

また，Sakai らはフィードバック文書が適合文書であったとし

本論文の構成は以下のとおりである．2 節では，関連研究をても，その文書によるクエリ拡張が必ずしも良い検索性能をも紹介する．3 節では，本研究で扱う問題の定義を行う．4 節でたらさないことにも示唆している．Lee ら [16] は，良い文書をは，提案手法について述べる．5 節では，提案手法に対する実選択するのに，検索結果の上位文書をクラスタリングし，クラ験と評価について述べる．6 節では，今後の課題及び本論文でスタから主要な文書を見つけて反復的にクエリを拡張した．

の結論について述べる．

2. 関 連 研 究
本節では，本研究と関連する研究について言及し，本研究の位置づけについて述べる．

Web 上のデータの検索においても異種ドメイン間での検索に関する研究が行われている．片岡ら [1] は，Web 検索で取得したデータセットを用いて分類モデルを学習し，分類の予測の信頼度をもとに Twitter の投稿が対象とする属性に合致するかを判定し，リランキングした検索結果を出力する手法を提案

マイクロブログにおいては，投稿文の語彙が少なく投稿者した．Halpin ら [17] は Semantic Web の検索とハイパーテキの意図が不明瞭なことがしばしば起こりうる．フォロワーやストの Web データの検索において一方の検索結果のフィード

リプライ，ハッシュタグといった SNS 特有の特徴を用いてマバックを他方の検索に用いることで検索精度を向上させること

イクロブログの検索性能を向上させた研究が存在する．[3]?[7]ができることを示した．Herzig ら [18] は，1 つのデータセット

Luo ら [4] は，ハッシュタグやメンションといった Twitter 特有の語彙のみを用いてクエリを拡張することで，RDF で記述さの情報が Twitter の検索性能を向上させることを示した一方，れた Web 上の異なるデータセット間の検索を行う手法を提案

Nagmoti ら [3] らは，フォロワー数とフォロー・フォロワーのした．Shekarpour ら [19] は，検索者が与えたキーワードを適割合をユーザの著名度合いを測る指標として用いて，Twitter

切に解釈するために，予め定義された基本グラフパターンテンの検索性能を向上させた．

プレートを用いて，SPARQL クエリを生成する手法を提案しユーザや投稿自身の属性推定に関しても多くの研究がなさた．Su ら [20] は，自然言語で記述されたクエリをグラフデー

れている [8], [9]．Pochampally らは Twitter ユーザの過去のツタに変換し，Knowledge Graph での検索により得られたデーイート等を用いて興味のあるトピックを決定する手法を提案しタに対し適合フィードバックを行うことで検索性能が向上する

た．Lu [10] らは SNS 上で複数のユーザ間によるメンション中ことを示した．

で間接的に言及されている属性を特定する手法を提案した．彼

同様の問題設定に取り組むという点で，片岡ら [1], [14] に類らの手法では，字数制限のある投稿中の不十分な情報を補うた似している．片岡ら [14] の研究では，検索者が明示的なフィー

めに，メンション情報だけでなく，Wikipedia の記事から取得

ドバックを行うことで検索性能を向上させているが，インタラした語彙を利用している．我々の研究においても同様に，ユークションが増えるという点で検索者への負担となりうる．また，ザタイプを表すクエリによる検索結果の記事を利用するため，

片岡ら [1] の研究では，モデル学習を行う際の文書数は事前に検索結果の上位に含まれる Wikipedia の情報を用いている．

決定する必要があり，全てのモデルを作成した後で，最適な文

適合フィードバック [11] や擬似適合フィードバックはクエリ書数を決定する必要があるため，学習に時間を要してしまう．

拡張の手法であり，その有効性は，SNS 検索においても示され本研究では，この問題を解決するアプローチとして，ユーザタている．．Miyanishi ら [12] は，検索者が検索結果のマイクロイプをクエリとする検索により得られた検索結果から，用いる

ブログ文書の中から 1 つ正解文書を選択し，その文書をクエリ

文書数を動的に決定する擬似適合フィードバックを用いて投稿拡張に用いて再検索した検索に対し擬似適合フィードバックを

文とその周辺情報から投稿者が対象とするユーザ像に合致する

適用することで検索精度の向上を図った．Whiting ら [13] はマかを判定し，検索結果のリランキングを行う．

イクロブログの文書に対し，PageRank を用いて文書中の単語に時間性を考慮した重み付けを行い，時間性を考慮した疑似適合フィードバックを行うことで検索性能が向上することを示し

3. 問 題 定 義
本節では，我々が取り組む問題の詳細について述べる．

た．我々の以前の研究 [14] では，本研究と同様の問題設定に取3. 1 問 題 設 定

り組んだ際に，検索者自身が投稿者の周辺情報を確認すること

本節では，本研究が取り組む問題設定について述べる．本研

究では，トピッククエリとプロファイルクエリの 2 つのクエリを用いる．トピッククエリは，検索対象の文書に対する問い合
わせに用いるためのクエリであり，プロファイルクエリは，擬似適合フィードバックによってクエリを拡張するのに用いる．
例えば，新発売の商品 X に対する学生の評判を知りたいという検索欲求に対しては，「X」がトピッククエリ，「学生」がプ
ロファイルクエリである．この場合，X で検索し得られた検索結果に対し「学生」というプロファイルクエリを入力すること!"#$%&'()
Entity Query

4) Modify Entity query bypositive and negative
search results

adult3) Retrieve

Search Result/0（man, woman）（Tokyo, Osaka）（student, adult）

student
1) Input Topic queryand Entity query
Topic Query

student…

修正したクエリを用いて初期検索結果のリランキングを行う．

2) Choose words
describing the
opposite types

5) Calculate
similarity

Search Result

iPhoneAtsushi

5m

Takehiro

1h

Toru

2y

iPhone …
…

*+(,,"-.
$%&'()

student …
… iPhone …
iPhone …
… …

で，事前に学習したモデルを用いて「学生」による投稿である可能性が高い検索結果を上位にリランキングする．その際，投

0.6
0.8
0.3

!"#$%&"

'()

*$#+"

,-(.

#&/0%1!/"2

-('

3+*!!

)(4

!*+*12,)(.

6) Reranking
Search Result
Takehiro
1hstudent …
… iPhone …

Atsushi

5m

Toru

2y

iPhone …
…
iPhone …
… …

図 1 手法概念図

稿者のプロフィール，過去のツイートや，フォロワー・フォロ
イーのプロフィールから，各ユーザごとに生成した文書ベクト

4. 1 手 法 概 要ルを用いて，分類器にかけ，投稿者が「学生」であるかの推定

この節では，我々の研究の手法の全体の流れを説明する．我々

値を出力する．出力した推定値をもとに検索結果をリランキン
グする．

の手法は以下の 6 ステップから構成される．
（ 1 ） トピッククエリとプロファイルクエリを入力し，ト3. 2 ベクトル空間

ピッククエリをもとに Twitter 検索を実行

本研究の検索を実現するにあたって，文書の表現にはベク（ 2 ） プロファイルクエリと対になる語句を選択

トル空間モデルを用いる．本研究で扱うコーパスは，Twitter，（ 3 ） プロファイルクエリとその対となるクエリそれぞれをWeb それぞれに出現する語を合わせたものからなる．コーパス

用いて検索を実行の全ての語集合を V とすると，ある文書 d の特徴ベクトル xの次元数は |V | であり，x ∈ R|V | である．

4. 提 案 手 法（ 4 ） 検索結果をもとに，クエリを修正し，クエリベクトルを生成（ 5 ） クエリベクトルと 1) で得られた検索結果から生成されるベクトルの類似度を計算

本研究の目的は，SNS の任意のクエリを投入し得られた検索結果に対して検索者が属性を指定することで，検索者の求め（ 6 ） 類似度をもとに検索結果をリランキング
提案手法の概念図を図 4. 1 に示す．

るユーザ像に合致する投稿を上位にリランキングすることであ

4. 2 フィードバック文書の重み付ける．従来の擬似適合フィードバックでは，初期クエリの投入に

本節では，クエリベクトルの生成のための単語の重み付け方

より得られた検索結果の上位 n 件を正例とみなし，正例によっ法を述べる．クエリに関連した語彙が出現するという仮定をおて修正したクエリを用いて検索結果のリランキングを行う．

いているため，単語の重みは，検索結果の文書集合ごとに計算

一方，本研究では，以下の 3 点において従来の適合フィード

される．つまり，プロファイルクエリと対になるクエリのそれ

バックと異なる．1 点目は，クエリ修正にトピッククエリではぞれの検索により得られる文書集合のうち，両方に同じ単語がなく，プロファイルクエリを入力し得られた検索結果の語彙を出現したとしても，別々の重みをとる．コーパス内の全ての語用いる点である．片岡ら [1] の実験結果に基づき，プロファイル

集合を V ，フィードバックに用いる文書数を n 件とすると，あクエリを用いた擬似適合フィードバックにより，ユーザタイプ

るクエリが与えられたときの，検索結果の文書集合中のある単の関連語を取得し，本研究の問題設定における検索性能を改善

語 t の重み wt は以下のようにして計算される．

できることを示した．2 点目は，正例しか用いない通常の PRF

wt = (1 − α)tf t + αdf tと異なり，プロファイルクエリと対になるクエリによる検索結果を負例とみなし，フィードバックに用いる点である．あるク
エリによる検索結果には，そのクエリに関連する語彙が含まれているという仮定に基づいており，「学生」による投稿を取得したい場合，「学生」の検索結果を用いて，「学生」に関連する語
彙の重みを上昇させ，対となる「社会人」に関連する語彙の重みを減少させることが可能となる．3 点目は，類似度計算に用(1)

ただし，α は 2 つの重み付け方法の割合を調節するパラメータであり，0 <
= 1 を満たす．2 つの重み付け方法はそれぞれ=α<
以下のように定義される．

tf t =

ft
f
max1<
=n tk
=k <

df t =ntn(2)

いるベクトルは，Twitter の投稿から辿ることのできる，投稿

た だ し ，ft は D 内 で の 単 語 t の 総 出 現 回 数 ，nt は D

者のプロフィールやフォロワーのプロフィール，過去のツイー

内 で 単 語 t が 出 現 し た 文 書 の 総 数 を 表 す ．ft ，nt と も に ，トといった投稿の文脈を用いる点である．これは，我々の以前

0 <= 1 を満たすように正規化してある．
= nt <= 1, 0 <= ft <の研究 [14] と同様，投稿の文脈には投稿者に関連する語彙が出

tf を用いる理由は，検索結果内に多く出現する単語は，その検現するという仮定に基づく．

索結果をもたらしたクエリに対する関連度が高いと考えられるからであり，df を用いた理由は，tf のみだと 1 文書に偶然頻出した単語にも高い重みが与えられるが，検索結果の文書集合に位の文書は入力したクエリに対する関連度が高いと考えられる

共通して現れる単語は，クエリに対する関連度がより高いと考ため，上位の文書に類似度の高い文書のみから構成されていれえられるからである．

ば，クラスタ内の各文書の類似度は高くなる．2 つ目は，上記

4. 3 ユーザごとのベクトルの生成の条件が満たされていれば，クラスタ内とクラスタ外，すなわ

トピッククエリを用いて得られる検索結果から生成される各

ちクラスタ間の文書の類似度は低くなるという仮定である．ク

ユーザごとのベクトルは片岡ら [14] が以前に提案したベクトラスタ内に良い文書をもれなく取得できていれば，クラスタ外

ルを用いる．ツイート本文とそこからリンクで辿ることのできにクラスタ内の文書と類似度の高い文書は少ないためである．

る投稿者のプロファイル，過去のツイート，フォロワーのプロ

本手法のアルゴリズムを Algorithm 1 に示す．提案手法は以下ファイルをエッジで接続し，それらの文書中の語彙の重みをグの手順からなる．初めに「学生」といったクエリで Web 検索を行

ラフ上を伝搬させ，減衰させることで生成する．

い，初期検索結果を得る．この文書集合内で正規化した TF によ4. 4 擬似適合フィードバック

り検索結果内の n 件の文書ベクトル集合 Dn = {d1 , d2 , . . . , dn }本節では，4. 2 節で重み付けした単語を用いたクエリの修正を計算する．さらに，検索結果の文書集合 D はプロファイル

方法について述べる．プロファイルクエリと逆プロファイルク

クエリの関連語の出現頻度が高いコーパスであるため，より一+−から得られた検索結果の般的な語彙からなる Wikipedia コーパスから生成された辞書

単語をもとに生成した文書ベクトルをそれぞれ d+ , d− とするを用いて IDF を計算する．次に intrak と記述されるクラスタ

エリそれぞれのベクトル表現 q , q′−−と，q = q − q + d − d++となる．一般的な擬似適合フィー内類似度を計算する．intrak はクラスタ内の任意の 2 つの文

ドバックでは，文書ベクトルの平均をクエリに加えるが，本手書を非復元抽出し，計算した類似度の平均をとることで求め

法では，k 件の検索結果の文書集合から計算した単語とその重る．一方，interk は 2 つのクラスタ Dk = {d1 , d2 , . . . , dk } とみから文書ベクトルを生成する．このように単語の重み付けを

D2k \Dk = {dk+1 , dk+2 , . . . , d2k } から 1 つずつ文書ベクトル行うことで，以下のような利点が得られる．

を選び全ての組み合わせの類似度を計算した平均をとることで•プロファイルクエリに関連する「授業」といった単語は求める．すなわち，Dk の全ての文書ベクトルの平均ベクトル

正例には頻出するが，負例には出現しにくいので正の重みが与と D2k \Dk の全ての文書ベクトルの平均ベクトルとの類似度とえられる等価である．全体数を n にしてしまうと k が極端に大きい場合•

プロファイルクエリに関連度の低い「今日」といった単と小さい場合に interk が著しく低くなってしまうため，各文語は，正例・負例の双方に頻出するので重みが 0 付近の値を書集合の要素数が k 個になるように調整した．次に，全ての文

とる

書数 k において intrak /interk の比を計算し，その比が最大と•プロファイルクエリとは反対の関連性をもつ「会社」といった単語は負例には頻出するが，正例には出現しにくいので

なる k を選択する．
さらに，手法の拡張として順位による減衰を導入する．k 個

負の重みが与えられると n − k 個の文書に分割した際に，k 番目と k + 1 番目の文書に以上から，4. 2 節での重み付け手法と本節で提案したクエリ修

はクエリとの関連度に大差がないことが想定される．そのため，正を行うことで，既存の適合フィードバックや擬似適合フィー

2 つのクラスタの中で検索順位が低くなるにつれてペナルティ

ドバックと同様の効果をもつクエリベクトルが生成できると考を与えるような重み付け方法を考える．具体的には，文書集合えられる．

の平均をとる関数 average を次のような式 decayed average

最終的な類似度はコサイン類似度により次のように計算さで更新する．

∑kdi /idecayed average(Dk ) = ∑kii=1 1/iれる．
+−

f (q, q , q, x′0,i ) = cos(q′ , xi )(3)

ただし，xi は 4. 3 節で述べた，初期検索結果の i 番目の文書か

5. 実

(4)

験

ら生成されるベクトルである．類似度の高い順に初期検索結果
をリランキングする．

4. 5 フィードバック文書数の動的決定法
本節では，4. 2 節で述べた手法において，擬似適合フィード

本節では，提案手法を用いて行った実験とその評価について述べ，結果についての考察を行う．本実験の目的は提案手法の有効性について検証することである．“学生” や “社会人” とバックに用いる文書数をプロファイルクエリごとに動的に決定いったユーザタイプごとに動的に決定した検索結果の上位 k 件する手法を述べる．一般的に，関連度に順位付けを行う検索エを用いた PRF が，平均的なベースラインよりも検索性能を向ンジンにおいては，上位にクエリに対する適合文書が並び，下位の文書は適合度の低い文書が並ぶ．本研究では，決定した文書
数を k 件とした際に，上位 k 件までの検索結果をフィードバッ
クに用いる．この k 件の文書集合をクラスタと見なし，次の 2つの仮定を置く．1 つ目は，クラスタ内の各文書の類似度が高
いほど，良いクラスタであるという仮定である．検索結果の上上させることを示す．

5. 1 概要本研究では，予備実験，本実験 2 つの評価実験を行なった．
予備実験の目的は，PRF のための文書を 1 件ずつ増やした際に，検索性能が変化することを示すことである．本実験では，予備実験で得られた文書数 k を 1 件ずつ増やした場合の結果をもとに，提案手法で選択した文書数 k における検索性能とベーStudent nDCG@10

Algorithm 1 Determining the optimal k
Input A set of vectors Dn = {d1 , . . . , dn }Output The number of documents used for feedback kmax ,and a set of vectors Dk = {d1 , . . . , dk }Ensure:a function for calculating similarity sim()a function for calculating the average ofthe vector or scalar set average()a function expressed by Eq 4 decayed average()

q19
q1
q21
q3
q5
total

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0

1: for k = 1 to n do
2:

S = {}

3:for i = 1 to k do

4:

Sk = {}

5:for j = 1 to (k − i) do

6:

si,j = sim(di , di+j )7:

Sk = Sk ∪ {si,j }8:

end for9:

end for10:

intrak = average(Sk )11:interk = sim(decayeda verage(Dk ), decayeda verage(D2k \Dk ))12:

S = S ∪ {intrak /interk }

0

50

100

150

200

250

300

図 2 プロファイルクエリ「学生」に対して PRF を用いた結果のnDCG@10
Woman nDCG@10
1.0

q10
q16
q18
q24
q8
total

0.8
0.6

13: end for
14: kmax = arg max S

0.4
0.2
0.0

k

0

15: return kmax , Dk

50

100

150

200

250

300

図 3 プロファイルクエリ「女性」に対して PRF を用いた結果のスラインの手法により求まる検索性能を比較する．
（ 1 ） ProfAvg(Baseline): あるプロファイルクエリにおいて k を変化させた中で，全ての nDCG の平均をとる．ランダ
ムに k を選んだ場合と等しいとみなすことができる．
（ 2 ） BestFix(Baseline): k を固定した上で，全ての検索課
題の平均の nDCG を取り，その中で平均が最も高くなる k を選択する．本研究の検索課題に手法を適用した結果，k = 158
で固定すると平均的に最も良い nDCG となることが判明した．
（ 3 ） Cluster(Proposed Method): 提案手法．
（ 4 ） Cluster+Decay(Proposed Method): 式 4 により順位
による減衰を導入した提案手法

5. 2 実 験 設 定
本節では，実験に用いたデータセットやパラメータの設定，用いた評価指標などについて述べる．
初めに，データセットについて述べる．プロファイルクエリ
として，学生と社会人，男性と女性，東京と大阪の 3 つのペアを用意した．これらは年代，性別，地域といった主要な 3 つのユーザのデモグラフィックなタイプをと合致する．プロファイ
ルクエリの各々に対し，5 つのトピッククエリを用意し，計 30件からなる検索課題を設定した．Twitter REST API（注 4）を用いて各プロファイルクエリに対し 320 件のツイート，各トピッ
ククエリに対し 100 件のツイートを取得し，プロファイルク
エリに対する適合性を手動で判定した．また，各ユーザのプロファイルと過去のツイートを最大 100 件ずつ取得し，そのフォロワーのプロファイルを取得した．

（注 4）：https://dev.twitter.com/rest/public

nDCG@10

検索課題の例を表 1 に示す．各列はそれぞれ実験に用いたトピッククエリとプロファイルクエリ，判定した 100 件のツイー
ト中の正例の数，検索者がクエリを入力する状況の想定を表す．
評価指標には nDCG(normalized Discounted CumulativeGain) を用いた．nDCG は情報検索における一般的な評価指標であり，多値適合性に基づき，検索順位を考慮した性能を比較できる．順位付けを k 位まで行う場合の nDCG は

DCG@k [21] を理想的な順位で適合文書が並んだと仮定した
DCG’@k で正規化した指標であり，DCG@k は次の式で定義∑
2reli −1
される: DCG@k = ki=1 log．ただし，reli は i 番目の(i+1)
2

検索結果の関連度であり，今回の実験においては i 位の文書が適合文書の場合は reli = 1，不適合文書の場合は reli = 0 とした．

5. 3 予 備 実 験
予備実験では，文書数 k を 1 から 320 件まで変化させた場
合に，PRF を用いる提案手法を検索課題に適応した結果のnDCG@10 がどのように変化するかを調べる．ここでは Twitter 検索を用いる提案手法を PRF と記述する．一方，手法の簡単な拡張として Web 検索に用いるプロファイルクエリを「学生 -社会人」「社会人 -学生」のように否定演算子を付与した対のユーザタイプを付与する提案手法を導入し，Neg+PRF と記述する．否定演算子を付与した理由は，「学生」というクエリで検索した場合に検索結果中に「学生」だけでなく「社会人」に関連する語彙を含む文書も出現しうるので，対のユーザタイ
プのプロファイルの影響を抑えることを期待したためである．

表 1 実験に使用したクエリ例
トピッククエリプロファイルクエリ

正例の数想定した検索意図

学生

19

興味のある層を知りたい

社会人

52

購入者の層を知りたい
男女別に人気のある歌手を知りたい

今年の漢字

1

2 スマートスピーカー
3

紅白

男性

29

4

スターウォーズ

女性

35

男女の人気の差を知りたい

5

浅草

東京

31

地元の人々の呟きがどの程度あるか知りたい

6

甲子園

大阪

16

(同上)

実験結果の一部として，プロファイルクエリ「学生」「女8 種のプロファイルクエリにおいて BestFix が，それぞれ 3 種性」に PRF を適用した結果を図 2 と図 3 に示す．図の縦軸はのプロファイルクエリにおいて Cluster と Cluster+Decay

nDCG@10 を表しており，横軸はフィードバックの文書数を表が最も良い nDCG をもたらした．部分的に比較すると，Clus-

す．青色から紫色までの 5 色のグラフはそれぞれ異なるトピッ

ter と Cluster+Decay が，それぞれ 12 種のプロファイルク

ククエリを適用した結果であり，その平均を茶色のグラフで示

エリのうち 3 件のクエリで ProfAvg と BestFix を上回った．

す．文書数を 1 増やすごとに nDCG の値が大きく変動するこ

BestFix が常に 4 手法の中で良い検索性能を示さなかったことが表から読み取れる．特に文書数が少ない段階で変動が大きとからも，プロファイルクエリごとに動的にフィードバックの

く，文書数を増やすにつれて変動の幅が小さくなる．また，他文書数を決定する必要性が示される．

のプロファイルクエリにおいても同様の傾向が見られ，手法ごと，クエリごとに平均のグラフの形状は異なった．以上の結果
から，フィードバックに用いる最適な文書数を決定する必要性

6. 考

察

実験の結果，本手法は多くのプロファイルクエリにおいて提案手法を下回った．本節では，その原因について考察し，改が示された．

5. 4 本 実 験

善策を検討する．提案手法のスコアの分布と PRF を適用した

本実験では，節で示す 4 手法を検索課題に適用した結果の場合の nDCG を比較するために，図 4 から図 6 に示す．「学nDCG を比較した．表 2 に実験結果を示す．表中の Category

生」「社会人」のプロファイルクエリの場合，4 つ並んだ図のうち左から順に，「学生」に対して Web+PRF，「学生」に対し

表 2 nDCG@10 for pre-determined k

Categoryて Neg+PRF，「社会人」に対して PRF，「社会人」に対して

ProfAvg BestFix Cluster Cluster+Decay

Neg+PRF を適用した結果となる．他の「男性」と「女性」，「東student

0.257

0.264

0.246

0.229

京」と「大阪」の場合も同様である．青色のグラフは Cluster，

student -adult

0.280

0.304

0.316

0.278

橙色のグラフは Cluster+Decay，緑色のグラフはそれぞれ

adult

0.694

0.706

0.652

0.664

のプロファイルクエリに PRF，Neg+PRF を適用した結果のadult -student

0.710

0.730

0.662

0.662

man

0.472

0.511

0.323

0.334

man -woman

0.430

0.470

0.320

0.334

案手法においては intrak /interk のスコアを，nDCG において

woman

0.471

0.522

0.469

0.537

はその値を示している．前者は比のため，そのスコアが 1 を超

woman -man

0.539

0.563

0.563

0.501

える場合もあるが，k を変えたときの提案手法のスコアの分布

Tokyo

0.311

0.310

0.296

0.313

と nDCG@10 の値の分布の差を捉えることが目的のため，グTokyo -Osaka

0.308

0.305

0.313

0.313

ラフとして同時に図に表現した．灰色の点線は 3 種のグラフが

Osaka

0.381

0.394

0.337

0.366

それぞれ最大値をとる k の値を表している．図から，Cluster

Osaka -Tokyo

0.395

0.416

0.362

0.374

nDCG@10 を示す．横軸は文書数 k を表しており，縦軸は提と Cluster+Decay を比較すると，後者の方が 1 文書増加した場合のスコアの変動が小さいことが分かる．これは減衰を導はそれぞれのプロファイルクエリを示しており，その各行は否入したことにより，順位による文書の重要度が k によって変定演算子がない場合は記載されているプロファイルクエリに対化し，interk の値が大きく変化したためであると考えられる．

して PRF を適用した結果，否定演算子が付与されたクエリは，

Cluster と比べて，Cluster+Decay のスコアが急激に増加

記載されているプロファイルクエリに対して Neg+PRF を適した k においては，interk の値が低くなり，良いクラスタ分割用した結果である．各セルの値は ProfAvg に関しては，予めができたと考えられる．

5 件のトピッククエリに PRF，Neg+PRF を適用した平均のさらに，検討の材料として，表 3 に intrak ，interk とそのnDCG を示す．他の 3 手法に関しては，同様に 5 件のトピック

比，値を表した．この値は全プロファイルクエリの平均の値でクエリに予め PRF，Neg+PRF を適用し，手法により求めた

ある．k は文書数を表し，5,10,100,200,320 件とした場合の値

文書数 k における nDCG を示してある．各プロファイルクエ

を掲載した．また，interk は減衰の有無で値が異なるため手法

リに対して 4 手法の中で最も nDCG が高かった手法を太字でごとに掲載し，intrak は手法間で共通のためまとめて 1 つの示してある．

列に記述した．表から，intrak は文書数が増えると減少する

表 3 提案手法の k における intrak , interk とその比Clusterkintrakinterk比Cluster+Decayinterk

比

5

0.418

0.685

0.610

0.651

0.642

10

0.398

0.674

0.591

0.627

0.635

100

0.298

0.959

0.311

0.860

0.347

200

0.287

0.961

0.299

0.824

0.349

320

0.263

0.985

0.266

0.823

0.319

とみなし文書のベクトルをフィードバックする通常の Web 検索における PRF では，同様の手法を適用した場合に本手法が有効である可能性がある．そこで，今後の展望として，TREC等のデータセットを用いて通常の Web 検索の PRF において本手法の有効性を検討する予定である．

7. 終 わ り に本手法では，ユーザとトピックをそれぞれ指定する SNS 検索において，動的にフィードバックのための文書数を決定する

ことがわかる．この原因は，文書が増える場合に検索結果の下位の文書が追加されるため，元々クラスタ内にあった文書との類似度が低くなるからだと考えられる．一方，interk は文書数が増えると増加する．interk は同じ数の文書の平均ベクトル同士の類似度のため，k が増えるとその平均は偏った特徴が少な
くなるという点と，上位の文書だけで構成されているクラスタに下位の類似度が低い文書が混入することが原因だと考えられる．また，表から k の増加に対する intrak の減少する速度よ
りも interk の増加する速度の方が早く，分母の方が大きくなるため，結果として k の増加に伴い比が減少していくことが考えられる．

手法を組み込んだ擬似適合フィードバック手法を提案した．文
書数を変化させる中で，文書集合のクラスタ内の類似度と同数のクラスタ外の文書集合との類似度を比較し，クラスタ内にクエリとの関連度が高い文書がより多く存在するようなクラスタを生成する手法を提案した．実験の結果，12 種類のクエリのうち，7 種類のクエリでベースラインが提案手法を上回ったため，
本研究の問題設定下においては，現状ではベースラインの経験的に良いとされる文書数を用いた方が良いという結論となった．
しかし，Web 検索結果のフィードバックにより同じ検索結果をリランキングする PRF においては，手法が有効である可能性があるため，今後は問題設定を変更して実験を行う予定である．

本手法が有効であるかどうかの直感的な判断材料として，実謝辞 本研究は，JST CREST (JPMJCR16E3)，JSPS 科研

際の nDCG の分布の形に沿って提案手法のスコアが分布して

費 18H03245，JSPS 科研費 16K12430，JSPS 科研費 18K11425

いることが挙げられる．しかし，図と表から分かるように，提の支援を受けたものである．

案手法のスコアは下がり方に差はあるが k の増加と共に減少す
る傾向のあるグラフであるのに対し，実際の nDCG は k の増加に対して値が大きくなる場合と小さくなる場合がある．例えば，プロファイルクエリ「女性」の PRF では，nDCG が 50 件までの間にピークがあり，その後緩やかに減少していく．一方，
プロファイルクエリ「社会人」の PRF では，nDCG が 50 件までの間に大きく変動した後，文書数が増え続けても高い値を保ち続けている．「女性」のように，一定の文書数を超えると

nDCG が減少するような検索課題であれば，k の増加に伴い減少する傾向のある本手法が有効である場合がある可能性はあるが，「社会人」のような文書数の増加に伴い nDCG が増加する
場合には手法の改善による精度の向上が見込めない．本研究における PRF の手法は文書集合が与えられたときに上位数件を正例とみなし，平均ベクトルをクエリにフィードバックする通常の PRF とは異なり，大量の文書集合から出現する語に対して重みを計算する．さらに，同じクエリを修正して再検索するのではなく，トピッククエリで検索した結果を検索結果以外の情報も含めて再検索するという条件下における手法である．その特殊な問題設定のために，大量の文書をフィードバックした
場合に nDCG が良い値を示す例が存在し，最適な k を求める
ことができなかった可能性が考えられる．一方，Montgomery
ら [2] は通常の Web 検索において異なる 9 つのシステムにおいて PRF のフィードバックの文書数を変更した場合の検索性能の変化を検証したが，その結果，少ない文書数の際にピークが存在した後，文書数が増えるにつれて検索性能が低下することを示した．そのため，クエリ 1 種類を用いて上位の文書を正例

文献[1] D. Kataoka and K. Tajima. Sns retrieval based on user profile estimation using transfer learning from web search. In
Proceedings of the International Conference on Web Intelligence. ACM, 2018.
[2] Jesse Montgomery, Luo Si, Jamie Callan, and David A
Evans. Eﬀect of varying number of documents in blind feedback: analysis of the 2003 nrrc ria workshop bf numdocs
experiment suite. In Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, pages 476–477. ACM, 2004.
[3] Rinkesh Nagmoti, Ankur Teredesai, and Martine De Cock.
Ranking approaches for microblog search. In Web Intelligence and Intelligent Agent Technology (WI-IAT), 2010
IEEE/WIC/ACM International Conference on, pages 153–
157, 2010.
[4] Z. Luo, M. Osborne, S. Petrovic, and T. Wang. Improving
twitter retrieval by exploiting structural information. In
AAAI, 2012.
[5] M. Efron. Hashtag retrieval in a microblogging environment. In Proceedings of the 33rd international ACM SIGIR
conference on Research and development in information retrieval, pages 787–788, 2010.
[6] D. Metzler, C. Cai, and E. Hovy. Structured event retrieval over microblog archives. In Proceedings of the 2012
Conference of the North American Chapter of the Association for Computational Linguistics: Human Language
Technologies, pages 646–655, 2012.
[7] C. H. Lau, Y. Li, and D. Tjondronegoro. Microblog retrieval
using topical features and query expansion. In TREC, 2011.
[8] R. Pochampally and V. Varma. User context as a source of
topic retrieval in twitter. In Workshop on Enriching Information Retrieval (with ACM SIGIR), pages 1–3, 2011.
[9] M. Albakour, C. Macdonald, I. Ounis, et al. Identifying

Student -adult

0.7
0.6
0.5
0.4

0.8

Score / nDCG@10

Score / nDCG@10

Score / nDCG@10

0.8

0.6
0.4

0.3
0.2

Adult

1.0
Cluster
Cluster+Decay
nDCG@100.9

1.0Cluster
Cluster+Decay
nDCG@10Adult -student
Cluster
Cluster+Decay
0.9nDCG@10
Score / nDCG@10

Student
0.9

0.8
0.7

Cluster
Cluster+Decay
nDCG@10

0.8
0.7
0.6

0.6

0.2
0

50

100

150
k

200

250

300

0

50

100

150
k

200

250

300

0

50

100

150
k

200

250

300

0

50

100

150
k

200

250

300

図 4 プロファイル「学生」「社会人」に対する PRF 手法の nDCG@10 と提案手法のスコア
man -woman
1.0Cluster
Cluster+Decay
0.9nDCG@10

0.7
0.6
0.5
0.4
50

100

150
k

200

250

図5

0.4
0.3
200

250

図6

[12]

[13]

[14]

[15]

[16]

[17]

0.5
0.4

50

100

150
k

200

250

300

0.7
0.6
0.5

0

50

100

150
k

200

250

0.4

300

Osaka

Cluster
0.8Cluster+Decay
nDCG@10
0.7
0.6
0.5
0.4

0

50

300

1.0Cluster
Cluster+Decay
0.9nDCG@10

1.0
Cluster
0.9Cluster+Decay
nDCG@10

0.8

0.8

0.7
0.6
0.5

100

150
k

200

250

300

0.3
0

50

100

150
k

200

250

300

Osaka -Tokyo
Cluster
Cluster+Decay
nDCG@10

0.7
0.6
0.5
0.4

0.4

0.3
150
k

0.6

0.3
0

Score / nDCG@10

Score / nDCG@10

0.5

100

0.7

Tokyo -Osaka

0.6

50

0.8

Cluster
Cluster+Decay
nDCG@10

プロファイル「男性」「女性」に対する PRF 手法の nDCG@10 と提案手法のスコア

0.7

0

0.9

0.4
300

0.8

[11]

0.5

Tokyo

0.9

[10]

0.6

woman -man
Cluster
Cluster+Decay
0.8nDCG@10

Score / nDCG@1000.7

Score / nDCG@10

0.3

0.8

Score / nDCG@10

Score / nDCG@10

Score / nDCG@10

0.8

woman

1.2Cluster
1.1Cluster+Decay
nDCG@101.0

Score / nDCG@10

Man
0.9

0.3
0

50

100

150
k

200

250

300

0

50

100

150
k

200

250

300

プロファイル「東京」「大阪」に対する PRF 手法の nDCG@10 と提案手法のスコア

local events by using microblogs as social sensors. In Proceedings of the 10th Conference on Open Research Areas inInformation Retrieval, pages 173–180, 2013.
J-L Lu, M. P. Kato, T. Yamamoto, and K. Tanaka. Entity
identification on microblogs by CRF model with adaptive
dependency. The Institute of Electronics, Information andCommunication Engineers Transactions, pages 2295–2305,
2016.
J. J. Rocchio. Relevance feedback in information retrieval.
In The Smart system-experiments in automatic document
processing, 1971.
T. Miyanishi, K. Seki, and K. Uehara. Improving pseudorelevance feedback via tweet selection. In Proceedings of the
22nd ACM international conference on Information andKnowledge Management, pages 439–448, 2013.
S. Whiting, I. A. Klampanos, and J. M. Jose. Temporal
pseudo-relevance feedback in microblog retrieval. In ECIR,
pages 522–526, 2012.
D. Kataoka, M. P. Kato, T. Yamamoto, O. Hiroaki, andK. Tanaka. Context-aware relevance feedback over sns
graph data. In Proceedings of the International Conferenceon Web Intelligence, pages 823–830. ACM, 2017.
Tetsuya Sakai, Toshihiko Manabe, and Makoto Koyama.
Flexible pseudo-relevance feedback via selective sampling.
ACM Transactions on Asian Language Information Processing (TALIP), 4(2):111–135, 2005.
Kyung Soon Lee, W Bruce Croft, and James Allan. A
cluster-based resampling method for pseudo-relevance feedback. In Proceedings of the 31st annual international ACM
SIGIR conference on Research and development in information retrieval, pages 235–242. ACM, 2008.
H. Halpin and V. Lavrenko. Relevance feedback between
web search and the semantic web. In IJCAI, pages 2250–

2255, 2011.
[18] D. M. Herzig and T. Tran. Heterogeneous web data searchusing relevance-based on the fly data integration. In WWW,
pages 141–150, 2012.
[19] S. Shekarpour, S. Auer, A. C. Ngonga Ngomo, D. Gerber,
S. Hellmann, and C. Stadler. Generating sparql queries using templates. An International Journal Web Intelligenceand Agent Systems, pages 283–295, 2013.
[20] Y. Su, S. Yang, H. Sun, M. Srivatsa, S. Kase, M. Vanni, andX. Yan. Exploiting relevance feedback in knowledge graphsearch. In KDD, pages 1135–1144, 2015.
[21] K. Järvelin and J. Kekäläinen. Cumulated gain-based evaluation of ir techniques. ACM TOIS, pages 422–446, 2002.