タスク

更新情報

  • Nov. 4, 2015: The file encoding was specified:

    Note that the file encoding must be "UTF-8".

  • Nov. 2, 2015: The way to generate a trailtext was modified:

    Let \({\mathbf f} = (\ldots, u_{j-1}, l_{k}, u_{j}, \ldots)\) where \(l_{k}\) is a link of intent \(i\).

  • Nov. 1, 2015: A sentence was added:

    Also note that only the first appearance of the same iUnit is relevant, while the other appearances are regarded as non-relevant.

  • Oct. 5, 2015: Several updates on the task definition (they are highlighted)

概要

現在のWeb検索エンジンは与えられたクエリに対して順位付けされたWebページのリストを返すことが一般的である. クエリを入力し検索ボタンを押した後に,ユーザは大抵これらのWebページを1つずつ訪れ自力で適合する箇所を見つけ出さなくてはならない. これらの作業は特にモバイル検索ユーザにとっては大きな労力となるが, もしシステムがクエリに適合する情報の簡潔な要約を返すのであれば,この手間を回避することが出来るだろう1

NTCIR-12 MobileClickタスク (と先行する類似タスク: NTCIR-9 1CLICK-12とNTCIR-10 1CLICK-23,NTCIR-11 MobileClick-14) は,ユーザがモバイル機器と多くのインタラクションを行わなくても即座に適合情報を手に入れられるように, 適合する情報の要約を生成しそれを直接提示することを目指すタスクである. これまで行われてきた1CLICKタスクとは異なり,参加者は2層の要約を出力することが求められる. 1層目は最も重要で,かつ,概要的な情報を含むように, 2層目はより詳細な情報を含み,1層目からリンクを辿ることによってアクセスされることを想定している. 以下の出力例では,クエリ"NTCIR-11"に対して, 1層目にNTCIR-11の一般的な情報とコアタスクの一覧を提示している. もし"MobileClick"というリンクがクリックされた場合, システムは2層目の"MobileClick"に関する情報を提示する.

Interface

MobileClickタスクのテキスト出力は,文書の適合度ではなく,iUnit (information unit)に基づいて評価される. 提出されたシステム出力の評価値はより重要なiUnitを含むほど高くなる. さらに,ユーザが読まなくてはならないテキスト量を少なくするほど,または,適合情報を手に入れるまでにかかる時間を少なくするほど, 高い評価を得ることができる. これらの考えは1CLICKタスクでも採用されてきたが, 今回は2層の要約であるため,ユーザが様々な方法で要約を読むことを仮定している. 我々は自らの意図に従って2層の要約の異なる箇所を閲覧するユーザモデルを仮定し, このユーザが閲覧する箇所のiUnitの重要度,および,iUnitを閲覧するのにかかる時間を考慮した評価を行う.

Back to the top

サブタスク

MobileClickタスクの目的は「与えられたクエリに対して構造化されたテキスト出力を返却する」ことであり, これは iUnitランキングサブタスクiUnit要約サブタスクという2つのサブタスクによって達成される.

iUnitランキングサブタスク

iUnitランキングサブタスクは,与えられたクエリに対してiUnits (information units)をそれらの重要度によってランキングするタスクである. このサブタスクはより細かいレベルの評価を可能にし, 重要なiUnitを推定する技術とそれらを2層に要約する技術を分けて評価するために考案された.

このサブタスクでは,クエリ集合,iUnit集合,および,iUnitの抽出元文書集合が提供される. 参加者は各クエリに対してiUnitを重要度順に並べたリストを提出する. より具体的には,iUnitランキングのランはTSVファイルであり, 最初の行はシステムの簡単な説明を含み, 以降の各行は1つのiUnitを表現する必要がある. そのため,提出するランファイルは以下のようなものになる:

This is an example run file
[qid]	[uid]	[score]
[qid]	[uid]	[score]
...

ここで[qid]はクエリID,[uid]はiUnit ID,[score]は推定された重要度スコアである. ファイルはUTF-8でエンコーディングされている必要がある. 多くの点で,iUnitランキングランはTRECのアドホックランと類似しており, 基本的には検索されたオブジェクトの順序付きリストである. iUnitsは評価者によって適合性判定が行われ,ランはランキング指標によって評価される. ただし,[score]の値は評価では用いられず,ランファイル中のiUnitの順序のみが評価に用いられる.

iUnit要約サブタスク

iUnit要約サブタスクは 「クエリ,iUnit集合,意図集合が与えられた時に,構造化されたテキスト出力を返却する」タスクである. より厳密には,MobileClickのテキスト出力は2層から構成されている必要がある. 1層目はiUnitおよび2層目へのリンクで構成され, 2層目はiUnitのみから構成される. 各リンクは与えられた意図のいずれかであり,2層目のiUnitリストのいずれかにリンクしている必要がある. 1層目と2層目の各iUnitリストは一般的なモバイル画面のサイズに収める必要があるため,\(X\)文字までしか含むことができない. リンクの文字数はカウントされるが,記号や空白などは文字数として考慮されない. MobileClick-2では,\(X\)を英語・日本語それぞれに対して,420および280と設定する. ただし,ランファイル中でiUnitリストが\(X\)文字以上含む場合には評価時に切り詰められる.

各ランファイルはXMLファイルであり,以下のDTDを満たす必要がある:

<!ELEMENT results (sysdesc, result*)>
<!ELEMENT sysdesc (#PCDATA)>
<!ELEMENT result (first, second*)>
<!ELEMENT first (iunit | link)*>
<!ELEMENT second (iunit)*>
<!ELEMENT iunit EMPTY>
<!ELEMENT link EMPTY>
<!ATTLIST result qid NMTOKEN #REQUIRED>
<!ATTLIST iunit uid NMTOKEN #REQUIRED>
<!ATTLIST link iid NMTOKEN #REQUIRED>
<!ATTLIST second iid NMTOKEN #REQUIRED>

ここで,

  • XMLファイルは[results]要素をルート要素として含む
  • [results]要素は1つの[sysdesc]要素を含む
  • [results]要素は[result]要素を複数含み,それぞれが1つの要約に対応し[qid]属性を持つ
  • [result]要素は1つの[first]要素と複数の[second]要素を含む
  • [first]要素は[iunit]要素と[link]要素を含む
  • [second]要素は[iid]属性を持ち,[iunit]要素を含む
  • [iunit]要素は[uid] (iUnit ID)属性を持つ
  • [link]要素は,1つの[second]要素をリンク先として特定する[iid] (意図ID)属性を持つ
ただし,同一の[iunit]要素は複数回出現してもよい. 例えば,あるiUnitが[first]要素と[second]要素に現れていてもよい.

上記のDTDを満たすXMLファイルを以下に示す:

<?xml version="1.0" encoding="UTF-8" ?>

  
  Organizers' Baseline
  
  
    
      <iunit uid="MC-E-0001-U001" />
      <iunit uid="MC-E-0001-U003" />
      <link iid="MC-E-0001-I006" />
      <iunit uid="MC-E-0001-U004" />
      <link iid="MC-E-0001-I002" />
    
    
      <iunit uid="MC-E-0001-U011" />
      <iunit uid="MC-E-0001-U019" />
    
    
      <iunit uid="MC-E-0001-U029" />
      <iunit uid="MC-E-0001-U021" />
    
  

XMLの検証はW3C Markup Validation Serviceにて"Validate by direct input"を用いて行うことができる. ファイルはUTF-8でエンコーディングされている必要がある.

Back to the top

テストコレクション

NTCIR-12 MobileClickテストコレクションはクエリ,iUnit,意図,および,文書コレクションを含む.

クエリ

NTCIR-12 MobileClickテストコレクションは英語および日本語クエリを含む. MobileClick-1タスクとは異なり,我々はより曖昧/不明瞭な,過去のNTCIRにおける1CLICKタスクで用いられたような短いクエリを選定した. これは,モバイル機器にて頻繁に用いられるようなクエリに焦点を当て,検索者の多様な意図に関する問題に取り組むためである.

我々は2014年4月-7月の間に得られた韓国のブラウザツールバーのログから実ユーザのクエリを入手し, それらを英語と日本語に翻訳することによってクエリの選定を行った.

文書コレクション

各クエリに対してiUnit集合を事前に用意するため, Bing検索エンジンによって各クエリに対し得られた上位500件のWebページをダウンロードし, 次節にて詳しく述べるように,iUnitをこれらのページから抽出した. ただし,いくつかのWebページは入手できなかったため,各クエリに対してダウンロードされた文書数は500以下となっている. NTCIRの参加者はこの文書コレクションを登録後に入手することが可能であり, iUnitの重要度や意図確率を推定するためなどに利用することができる. もしNTCIR参加者以外でこの文書コレクションが必要な場合にはオーガナイザに問い合わせる必要がある.

iUnit

過去のNTCIRにて企画された1CLICKタスクのように,MobileClickタスクにおいてもiUnitを情報の単位として用いている. iUnitは「適合した」,「極小の」,「互いに依存しうる」情報の断片と定義される. ここで,

  • 「適合した」とは,iUnitが有用な事実に基づく情報をユーザに与えることを意味する
  • 「極小の」とは,iUnitが元の意味を保持した上で複数のiUnitに分解できないことを意味する
  • 「互いに依存しうる」とは,あるiUnitが適合であるために他のiUnitに依存しうることを意味する
より詳しい定義については,1CLICK-2の概要論文を参照して欲しい1click2

上記の定義によりiUnitは互いに依存しうるが,今回は簡略化のため他に依存するようなiUnitは除いている.

iUnitの抽出には長時間に渡り3つの要件に関する判断を含んだ慎重な作業が必要であるため, コントロールが難しく,教育的コストの高いクラウドソーシングの利用は行わないことにした. 我々はiUnitを人手で抽出するために数名の作業者を雇用し, 適宜結果に対してフィードバックを与えることによって抽出されたiUnitの質を担保した.

NTCIR-11 MobileClickタスクの英語クエリに対するiUnitの例. クエリMC-E-0020は"stevia safety"である.
Query ID iUnit Source
MC-E-0020There are some dangers and side effects when using stevia.MC-E-0020-008.html
MC-E-0020refined stevia preparations allowed in food and drinksMC-E-0020-001.html
MC-E-0020Stevia does interact with some other drugs.MC-E-0020-009.html
MC-E-0020Stevia may have an anti-inflammatory effect.MC-E-0020-011.html
MC-E-0020Stevia may help diarrhea.MC-E-0020-011.html

意図

MobileClick-2では,NTCIR INTENTタスクやIMineタスクで用いられてきた,「意図」という考えを利用する. 意図は「ある曖昧なクエリの特定の解釈 (ジャガーに対するMac OSや車のブランド)」, あるいは,「ある不明瞭なクエリの特定の側面 (Windowsに対するWindows 8やWindows 10)」であると定義される. 今回,意図はiUnitの重要度を評価する際に用いられ, また,iUnit要約サブタスクにおいて2層目へのリンクの候補としても利用される.

我々は以下のように意図を作成した:

  1. iUnitsをクラスタリングし
  2. 含まれるiUnitを良く表すラベルを各クラスタに付与し
  3. 各ラベルを意図として抽出した

我々は評価者を雇用しクラスタリング作業を行ってもらった.この作業の中で,2つのiUnitは以下の条件を満たした時に同じクラスタに入れられた:

  • それらが曖昧なクエリと同一の解釈に関する情報,もしくは,不明瞭なクエリの同一の側面に関する情報であり
  • それらが同一のユーザによって興味が持たれる可能性が高い

ラベルの選定には以下の基準が用いられた:

  • あるクラスタのラベルはユーザがそのクラスタ中のiUnitの概要を理解するのに十分なほどで説明的でなくてはならない
  • あるクラスタのラベルは含まれるiUnitに対するクエリ,もしくは,アンカーテキストとしてよく用いられるものでなくてはならない

意図を抽出した後,我々は評価者に各意図が重要であるかどうかを投票してもらった. この作業は,NTCIR INTENTおよびIMineタスクでも行われており, 特定のクエリを入力したユーザの意図の確率,意図確率 (intent probability)を推定するために行われた. 評価者は,もし自身がそのクエリによって検索した際にその意図に興味を持つと思った場合には, その意図に投票をするように指示を与えた. 1度も投票されなかった意図は,その意図に興味を持つユーザがあまりいないと考えられるため除去された. 各クエリについて,総投票数によって各意図が得た投票数を正規化したものを\(P(i|q)\)によって表現し, これを意図確率と呼ぶ.

iUnit重要度

各iUnitの重要度は各意図の側面から評価され, 「総合的重要度」は意図ごとの重要度と意図確率から算出される.

我々は評価者に各意図の側面から各iUnitを 0 (重要でない), 1, 2 (やや重要), 3, 4 (非常に重要)の5段階で評価してもらった. 評価者には自分がその意図に興味を持っていることを仮定しながら評価することが求められた. 我々はある意図におけるiUnitの重要度を 「iUnitはその意図に興味を持つより多くのユーザにとってより必要不可欠であるほど重要である」 と定義した. 例えば,「ジャガー」というクエリの「Mac OS」という意図の場合, 「イギリスの車会社」というiUnitは「重要ではない」. 一方で,「車のブランド」という意図の下では,「非常に重要」と判断される. 評価においては複数人の評価者が与えたスコアの平均値を意図ごとの重要度として用いた.

iUnitランキングサブタスクでは,各iUnitの総合的重要度が評価に用いられている. \(P(i|q)\)をクエリ\(q\)に対する意図確率としたとき, iUnit \(u\)の総合的重要度は以下のように定義される: $$GG(u) = \sum_{i \in I_q} P(i|q)g_i(u),$$ ただし,\(I_q\)はクエリ\(q\)の意図集合であり,\(g_i(u)\)はiUnit \(u\)の意図\(i\)の下での重要度を表す.

Back to the top

評価指標

iUnitランキングサブタスク

参加者より提出されたランは各クエリに対するランク付きのiUnit IDリストを含んでおり, アドホック検索の評価と同じような方法で評価することができる. したがって,このサブタスクではアドホック検索のための一般的な評価指標を評価に用いる.

iUnitランキングサブタスクの評価指標の1つとして,「Normalized discounted cumulative gain (nDCG)」を用いる. Discounted cumulative gain (DCG)は以下のように定義される: $${\rm nDCG}@K = \sum^{K}_{r=1} \frac{GG(u_r)}{\log_2(r+1)},$$ ただし,\(K\)はカットオフパラメータであり,\(u_r\) は提出されたランク付きリストの\(r\)番目のiUnitを表している. 正規化されたDCG,すなわち,nDCGは以下のように定義される: $${\rm nDCG}@K = \frac{{\rm DCG}@K}{{\rm iDCG}@K},$$ ここで,\({\rm iDCG}\)は理想的なランク付きリストであり,総合的重要度の降順にiUnitをソートすることによって得られる.

もう1つのiUnitランキングサブタスクの評価指標はSakaiによるQ-measure6である: $$Q = \frac{1}{R}\sum^{M}_{r=1} {\rm IsRel}(u_r)\frac{\sum^{r}_{r'=1}(\beta GG(u_{r'})+{\rm IsRel}(u_{r'}))}{\beta\sum^{r}_{r'=1}GG(u^{*}_{r'})+r},$$ ただし,\({\rm IsRel}(u)\)は\(GG(u) > 0\)ならば1,そうでなければ0を返す指示関数であり, \(R\)は総合的重要度が0でないiUnitの数 (i.e. \(\sum_{u}{\rm IsRel}(u)\)), \(M\)はランク付きリストの長さ,\(u^{*}_r\)は理想的なランク付きリストにおける\(r\)番目のiUnit, \(\beta\)は持久パラメータである (今回の評価では確立されたスタンダードな値7,すなわち,\(\beta=1\)とした).

Q-measureは再現率ベースの多段階適合度向けの指標であるのに対し,nDCGはランクベースの多段階適合度向けの指標である. そのため,これら双方の指標によって,異なる観点から性能評価を行うことができると考えている. さらに,両指標とも信頼性が高いことが示されているqmeasure. ランキング全体の質を評価することができるため,Q-measureが提出されたランを順位付けるのに用いられている.

iUnit要約サブタスク

iUnit要約サブタスクに提出されたランは1層目\({\mathbf f}\)および 2層目\(S = \{{\mathbf s}_1, {\mathbf s}_2, \ldots, {\mathbf s}_n\}\)によって構成されている. 1層目\({\mathbf f}\)はiUnitとリンクを含んでいる (e.g. \({\mathbf f}=(u_1, u_2, l_1, u_3)\) ただし,\(u_j\)はiUnitで\(l_j\)はリンクである). 各リンク\(l_j\)は2層目\({\mathbf s}_j\)へのリンクとなっている. 2層目\({\mathbf s}_j\)はiUnitから成っている (e.g. \({\mathbf s}_1=(u_{1, 1}, u_{1, 2}, u_{1, 3})\)).

iUnit要約のための評価指標の原則は以下のように要約される:

  1. 評価指標はある要約を確率的に読むユーザの期待利得である
  2. ユーザは意図確率\(P(i|q)\)に従い,ある1つの意図に興味がある
  3. ユーザは以下のルールに従い要約を読む:
    1. 1層目の頭から順番に要約を読み,記号や空白を除き\(L\)文字を読んだ時点で読むのを止める
    2. リンク\(l_i\)の終わりまで読んだとき,もしリンク\(l_i\)の意図に興味があれば,そのリンクをクリックし2層目\(s_j\)を読み始める
    3. 2層目\(s_j\)の終わりまで読んだ場合,リンク\(l_j\)の終わりから1層目を読むのを再開する
  4. 利得はSakaiおよびDouによるU-measure9によって計測される

ここで説明したユーザモデルに従い,可能なユーザの軌跡 (もしくは,トレイルテキスト)を求め, 各トレイルテキストについてU-measureを計算し, 最終的に異なるトレイルテキストのU-measureを集約することでU-measureの期待値を推定することができる. iUnit要約のための評価指標,M-measureは以下のように定義される: \begin{eqnarray} M = \sum_{t \in T} P({\mathbf t})U({\mathbf t}), \label{eq:mmeasure} \end{eqnarray} ここで,\(T\)はすべての可能なトレイルテキストの集合,\(P({\mathbf t})\)はあるトレイルテキスト\({\mathbf t}\)を閲覧する確率であり,\(U({\mathbf t})\)はトレイルテキスト\({\mathbf t}\)のU-measureの値である.

トレイルテキストはあるユーザが読んだすべてのテキストを結合したものであり, 今回の場合にはiUnitとリンクのリストとして定義される. 上記で説明したユーザモデルによれば, 意図\(i\)に興味を持ったユーザのトレイルテキストは. 意図\(i\)から作られたリンクが指す2層目のiUnitを,そのリンクの後方に挿入することによって得られる. より正確に言えば,ある意図に対するトレイルテキストは以下のように得られる:

  1. \( {\mathbf f} = (\ldots, u_{j-1}, l_{k}, u_{j}, \ldots)\)とする. ただし,\(l_{k}\)は意図\(i\)のリンクである
  2. 2層目\({\mathbf s}_{k} = (s_{k,1}, \ldots, s_{k, |{\mathbf s}_k|})\)に対して,トレイルテキスト\({\mathbf t} = (\ldots, u_{j-1}, l_{k}, u_{k,1}, \ldots, u_{k, |{\mathbf s}_k|}, u_{j}, \ldots)\)を生成する
ただし,トレイルテキスト中のリンクは簡単のため「重要度が0のiUnit」として扱う. また,同じiUnitが複数回現れる場合には,最初に出現したもののみをそのまま評価し, 以降に現れる場合には重要度が0のiUnitとして扱う.

上述の通り,各意図に対して1つのトレイルテキストを作ることができ,要約の読み方はただユーザの意図にのみ依存するため,他のトレイルテキストを考える必要はない. 加えて,トレイルテキストの確率はその意図の確率と等しい. したがって,M-measureは以下のように簡潔に再定義することができる: \begin{eqnarray} M = \sum_{i \in I_q} P(i|q)U_i({\mathbf t}_i). \end{eqnarray} トレイルテキスト\({\mathbf t}_i\)を読むユーザは意図\(i\)に興味があることを仮定しているため, ここでUは意図\(i\)の下で評価されていることに注意せよ.

利得はSakaiおよびDouによるU-measureumeasureによって計測され, この指標はiUnitの重要度とトレイルテキスト中のオフセットによって計算される. あるトレイルテキスト中のiUnit\(u\)のオフセットは トレイルテキストの先頭から\(u\)の末尾までの文字数と定義される. より正確には,トレイルテキスト\({\mathbf t}\)中の\(j\)番目のiUnitのオフセットは \({\rm pos}_{\mathbf t}(u) = \sum^{j}_{j'=1}{\rm chars}(u_{j'})\)と定義される. ただし,\({\rm chars}(u)\)は記号や空白を除いたiUnit \(u\)の文字数である. トレイルテキスト中のリンクは,重要度が0のiUnitであるため,オフセットの計算にのみ寄与することに注意せよ. SakaiおよびDouの論文によれば,U-measureは以下のように定義される: \begin{eqnarray} U_i({\mathbf t}) = \frac{1}{\mathcal N}\sum^{|{\mathbf t}|}_{j = 1} g_i(u_j)d(u_j), \label{eq:umeasure} \end{eqnarray} ここで,\(d\)は位置依存の減価関数であり, \({\mathcal N}\)は正規化係数である (今回は単に1とする). 位置依存の減価関数は以下のように定義される: \begin{eqnarray} d(u)=\max\left(0, 1-\frac{{\rm pos}_{\mathbf t}(u)}{L}\right), \end{eqnarray} ただし,\(L\)はユーザの耐久パラメータである. U-measureでは\(L\)文字読んだ後は追加の利得が得られず(\(d(u) = 0\)), これは\(L\)文字読んだ後読むのを止める上述のユーザモデルと一貫している. MobileClick-2では,\(L\)を\(X\)の2倍に設定している: つまり,英語では840,日本語では560である. これは日本語において\(L = 500\) (または250)がS-measureの研究で推奨されているためである11

Back to the top

  1. T. Sakai, M. P. Kato, and Y.-I. Song. Click the search button and be happy: Evaluating direct and immediate information access. In Proc. of CIKM 2011, pages 621–630, 2011.

  2. T. Sakai, M. P. Kato, and Y.-I. Song. Overview of NTCIR-9 1CLICK. In Proceedings of NTCIR-9, pages 180–201, 2011.

  3. M. P. Kato, M. Ekstrand-Abueg, V. Pavlu, T. Sakai, T. Yamamoto, and M. Iwata. Overview of the NTCIR-10 1CLICK-2 Task. In NTCIR-10 Conference, pages 243–249, 2013.

  4. M. P. Kato, M. Ekstrand-Abueg, V. Pavlu, T. Sakai, T. Yamamoto, and M. Iwata. Overview of the NTCIR-11 MobileClick Task. In NTCIR-11 Conference, pages 195–207, 2014.

  5. M. P. Kato, M. Ekstrand-Abueg, V. Pavlu, T. Sakai, T. Yamamoto, and M. Iwata. Overview of the NTCIR-10 1CLICK-2 Task. In NTCIR-10 Conference, pages 243–249, 2013.

  6. T. Sakai. On the reliability of information retrieval metrics based on graded relevance. Information processing & management, 43(2):531–548, 2007.

  7. T. Sakai. On penalising late arrival of relevant documents in information retrieval evaluation with graded relevance. In Proceedings of the First Workshop on Evaluating Information Access (EVIA 2007), pages 32–43, 2007.

  8. T. Sakai. On the reliability of information retrieval metrics based on graded relevance. Information processing & management, 43(2):531–548, 2007.

  9. T. Sakai and Z. Dou. Summaries, ranked retrieval and sessions: a unified framework for information access evaluation. In Proc. of SIGIR 2013, pages 473–482, 2013.

  10. T. Sakai and Z. Dou. Summaries, ranked retrieval and sessions: a unified framework for information access evaluation. In Proc. of SIGIR 2013, pages 473–482, 2013.

  11. T. Sakai, M. P. Kato. One Click One Revisited: Enhancing Evaluation based on Information Units, In Proc. of the 8th Asia Information Retrieval Societies Conference (AIRS 2012), pages 39-51, 2012.