DEIM Forum 2017 G4-1

部分文書検索を用いた高精度なモバイル情報検索
欅

惇志†

宮崎

純†

波多野賢治††† 東京工業大学 〒 152–8552 東京都目黒区大岡山 2-12-1†† 同志社大学文化情報学部 〒 610–0394 京都府京田辺市多々羅都谷 1–3
E-mail: †keyaki@lsc.cs.titech.ac.jp, ††miyazaki@cs.titech.ac.jp, †††khatano@mail.doshisha.ac.jp
あらまし

本研究では，モバイル端末をはじめとしたディスプレイサイズの小さな端末における情報アクセスにおいて，部分文書検索を用いた高精度化を行う．近年増大するモバイル端末からの情報検索では，従来の文書単位の検索よりも細かな粒度における情報検索の実現が期待される．その解決策の一つとして，ユーザの発行するクエリに対して適合しつつ，理解可能な最小単位のテキストの断片である iUnit を粒度とした情報検索システムである．iUnit を検索単位としたモバイル情報検索タスクである MobileClick では，検索結果を二層構造で提示することを想定している．
特に重要な iUnit のみを提示する一層目ページと，個別の意図 (intent) ごとに詳細な iUnit を提示する二層目のページによる情報提示を行うことで，ユーザのページ遷移回数を最小限に留めつつ，有用な情報の提示を行う．本稿では，
まず文中の適合箇所を発見するために部分文書検索を行い，高スコアを付与された部分文書と類似度の高い iUnit を上位にランキングすることによって高精度なモバイル情報検索手法を提案する．評価実験の結果，提案手法はベースライン手法と比較して 9.7% 高精度に検索可能であることを示した．
キーワード

モバイル検索，部分文書検索，MobileClick，iUnit

1. は じ め に

一層目 概要ページ

二層目 詳細ページ

bitcoinDefinition

Transactions areverified by network
nodes. Transaction
fees are paid by …

Bitcoin is a online
payment system. It
is peer-to-peer
system, whichmeans that users
can transact directly
without any
intermediary…

:

Google 社によれば，アメリカや日本を含む 10 ヶ国においてモバイル端末からの情報検索の件数は PC からの情報検索の件（注 1）

数を上回ったと報告されていることからも，近年，モバイ

ル端末からの情報検索の機会が増加している．そのため，モバ
イル端末において適切な情報提示手法を提案することは緊要な課題である．モバイル端末には小型のディスプレイが搭載されているため，提示できる情報は少なく，情報の取捨選択の必要性はより高い．言い換えれば，従来の文書単位による情報検索では効率的に情報検索活動を行うことが困難である．

Definition
Use
MechanismHistory

概要

検索
意図

:

詳細

国立情報学研究所主催の情報アクセス技術のための国際的図 1 二層構造によるモバイル情報検索

ワークショップである NTCIR の MobileClick [10] では，モバ
イル端末を利用するユーザに対して，適切な検索結果の提示に取り組んでいる．MobileClick では，ユーザがクエリを入力すの iUnit から構成される．

MobileClick は，さまざまなアプローチで取り組まれている

れば，検索結果を二層構造に整形して，不必要なページやサイが [4] [5] [27] [15] [3] [2] [19]，我々は部分文書検索を用いたアプ

トを遷移することなく，直接的に情報要求を満たすことを目指

ローチ [7] [14] を採用する．部分文書検索の検索単位は XMLしている．その際，図 1 に示す通り，まず一層目のページには，文書や HTML 文書などの構造化文書中の要素ノードであり，ユーザの情報要求に対して，より重要かつ概要的な内容についより厳密には，ある開始タグから終了タグの間に存在するプての情報と，意図 (intent) ごとの詳細ページ (二層目) へのリ

レーンテキストを結合したテキストを部分文書を呼ぶ．つまンクを提示する．これにより，ユーザは限られたディスプレイ

り，部分文書検索は，MobileClick と同様に，文書単位よりもサイズにおいても効率的に情報検索を行うことが可能となる．

細かな粒度である部分文書を検索単位とした情報検索である．

なお，MobileClick における情報提示では，information unit

部分文書検索では，構造化文書の文書構造を利用して，情報(iUnit) と呼ばれる，クエリに適合しており，かつ，意味を理

要求を満たす最適な箇所を文書中から特定することを目指す．

解する上での最小単位を用いる（注 2）．iUnit は，2, 3 語程度のMobileClick と 部分文書検索その検索粒度に違いはあるもの

語句，フレーズ，文といった，任意の情報粒度で構成される．

の，同じ方向性を目指す研究として流用可能な知見も多いと考

一層目の概要と二層目の詳細は，重要語の順に並べられた複数

えられる．
本研究では，下記の仮説の下に，部分文書検索を MobileClick（注 1）：https://adwords.googleblog.com/2015/05/building-for-next-moment.html (accessed: December 3rd, 2016)（注 2）：文献 [25] においては全てのクエリキーワードを含む部分グラフであると定義しているものの，MobileClick ではそのような制約は存在しない．

へ適用する手順の概要を示す．
［Hypothesis 1］ 適合箇所，すなわち，重要な iUnit は部分文

書検索によって高スコアを付与された部分文書中に含まれる．

クラスタリングされた iUnit に適切なラベルを付与することでまず既存の部分文書検索の枠組みで，文書集合に対してスコア作成されている （注 3）．なお，各 intent には重要度 (意図確率)

リングを行う．これによって，クエリごとに，ランク付けされが設定されており，そのクエリによって検索した際にその意図た部分文書リストが得られる．続いて，これらリストを用いてに興味を持つと判断した投票者の割合が設定される．なお，1

iUnit のランキング及び二層構造の検索結果の構築を行う．そ度も投票されなかった意図は除去されている．

の際，提案手法の直感的なアイデアとしては，より上位にラン

iUnit の重要度 手法の精度評価を行う際には，評価者によっキングされた部分文書と類似度の高い iUnit に対して高いスコて付与された iUnit の重要度を利用する．iUnit には各 intent

アを付与する．

ごとに意図別重要度が評価されている．また，総合的重要度は，以降，本稿の構成について述べる．まず，2. 節にて Mo-

iUnit の意図別重要度と intent の意図確率から算出される．あbileClick の概要について，3. 節にて部分文書検索の概要につる iUnit u の総合的重要度 Gu は下記の通り算出される．
∑
G(u) =
P (i|q)gi (u)(1)

いて述べる．それらを踏まえ 4. 節にて提案手法の説明を行い，その有用性検証のための評価実験を 5. 節にて行う．その後 6.

i∈Iq

節にて他の MobileClick 参加者のアプローチについてレビュー

ただし， Iq はクエリ q の intent 集合，i は Iq に含まれるを行い，最後に 7. 節にて本研究を纏める．

intent，P (i|q) は q における i の意図確率，gi は i における

2. MobileClick タスクの概要

u の意図別重要度とする．従って，ある intent においては極め

MobileClick は ，NTCIR-9 及 び NTCIR-10 に お い て 取て高い意図別重要度を持つ iUnit が，他の intent においてはり組まれた 1CLICK-1 [24] と 1CLICK-2 [8] の流れを汲み，

意図別重要度が低いため，低い総合的重要度を持つことが起こ

NTCIR-11 における MobileClick-1 [9] と，NTCIR-12 におり得る．逆に，各 intent ごとの意図別重要度は必ずしも極め

け る MobileClick-2 [10] から 構 成さ れる ．MobileClick-1 とて高くない場合でも，多くの intent において少なからず重要

MobileClick-2 では，オーガナイザから提供されるデータのと判断されれば，総合的重要度が高くなることが起こる．

種類が異なり，完全に同一のタスクではない．本稿では主に

2. 2 iUnit Ranking サブタスク

MobileClick-2 に焦点を当てた説明を行い，断りがない限り二層構造の検索結果の構築に先立ち，iUnit は重要度順にラMobileClick-2 を指すこととする．

ンキングされている必要がある．なお，iUnit Ranking サブタ

MobileClick は二つの手順から構成され，Step 1) iUnit のラ

スクでは，各 iUnit の重要度は総合的重要度から求められる．

ンキング，Step 2) ランキング結果を用いた二層構造の検索結

iUnit Ranking の評価尺度は，nDCG@K (K=3, 5, 10, 20) [1]

果の構築である．各ステップは，iUnit Ranking サブタスクとと Q-measure [21] である．nDCG は文書検索の評価に多用さ

iUnit Summarization サブタスクである．

れる，順位ベースの多段階適合性判定データのための評価尺度

2. 1 テストコレクション

である．それに対して，Q-measure は再現率ベースの多段階適MobileClick では，オーガナイザから下記のデータが提供さ

合性判定データのための評価尺度である．従って，Q-measureれる．なお，対象言語は英語及び日本語であり，本稿では英語は上位 k 件の iUnit だけでなくリスト全体の性能を評価する

データセットを利用する．

ことが可能であるため，公式尺度としては Q-measure が用い

クエリ 検索システムユーザのクエリログから，オーガナイザ

られる．

によって選別された，曖昧 · 不明瞭なクエリ 100 件を利用する．

nDCG は式 (3) によって算出される．

文書コレクション 各クエリごとに検索エンジン Bing を用いて最大上位 500 文書を取得したものを文書コレクションとして

DCGK =

k=1

利用する．

iUnit iUnit は，適合した最小単位のテキストの断片である．
従って，iUnit は，2, 3 語程度の語句，フレーズ，文といった，任意の情報粒度で構成される．例えば，クエリ “christopher

nolan” の iUnit として，“runs the production company ‘Syncopy Inc.’ ” や “married a film producer, Emma Thomas”，“Movie: ‘Interstellar’ ” などが存在する．iUnit は，オーガナ
イザによって雇用された複数名の評価者文書によって，コレク
ション中から網羅的に抽出されている．

intent intent は，NTCIR INTENT [23] や IMine [26] で用K∑

nDCGK =

GGuk
log2 (k + 1)

(2)

DCGK
iDCGK

(3)

ただし，uk は k 件目の iUnit，GG(uk ) は uk の総合的重要度とする．iDCG は理想的なランキングにおける DCG であり，正規化の役割を果たす．
また，Q-measure は式 (4) によって算出される．
∑rM(GG(ur′ ) + IsRel(ur′ ))
1 ∑
′
(4)
Q=
IsRel(ur ) r =1∑r∗R r=1r ′ =1 GG(ur ′ ) + r
ただし，R は総合的重要度が 0 より大きい iUnit の個数，M

いられてきた，ある曖昧なクエリの特定の解釈や，不明瞭なクはランク付きリスト長，u∗r′ は理想的なランク付きリストにおエリの特定の側面を表す．例えば，クエリ “jaguar ” の intent

ける r 番目の iUnit である．

は “Car ” や “Animal ” であり，クエリ “real madrid ” の in-

2. 3 iUnit Summarization サブタスク

tent は “Players” や “Achievement”，“History” などである．

iUnit Summarization サブタスクでは，最も重要かつ概要的

MobileClick において，intent は iUnit の重要度を評価する際な情報を含む iUnit と intent から構成される一層目と，一層に用いられ，また，iUnit Summarization において，二層目へ目の各 intent からリンクされ，intent に関しての詳細が記載のリンクとして設定される．intent は，評価者により，手動で（注 3）：クラスタリング結果は，intent のラベル付けにのみ利用される．

された iUnit から構成される二層目の構造へ検索結果の構築を行う (図 6 参照)．一層目と二層目の結果は，iUnit Ranking サブタスクで作成したリストを用いて構築する．二層構造の検索結果提示により，ユーザは情報要求を満たすためにページ (文書) の遷移を繰り返すことなく，最低限のページ遷移によって欲しい情報を発見することができる．

iUnit Summarization サブタスクではモバイル端末での情報検索を想定しているため，各層に表示可能な情報の文字数制限が設けられている．英語では 420 文字以下であり，記号や空白

DocID:1

DocID:1
article ElemID:1<article><sec>Bill Gates is …</sec><body><sec>Early life …</sec><sec>Windows …</sec></body></article>

ElemID:2
pbody ElemID:3
Bill Gates is ...

sec
Early life ...

図 2 XML 文書に出現した場合，二層目の iUnit の重要度は 0 と判定される．
評価尺度である M-measure [10] は下記のユーザモデルに基づき設計されている．

•

ユーザは意図確率 P (i|q) に従い，ある一つの意図に興

味を持つ．

•

ユーザは以下のルールに従い要約を読み進める．

（ 1 ） 一層目の冒頭から順番に検索結果を読み，記号や空白

ElemID:5
Windows ...

図 3 XMLは文字数に含まれない．また，同一の iUnit が一層目と二層目

ElemID: 1
Bill Gates is …
Early life …
Windows …

木

ElemID: 4
Early life …
ElemID: 5
Windows …

Early life …
Windows …
図4

ElemID:6
Books ...

ElemID: 2
Bill Gates is …

ElemID: 3

を除き L 文字を読んだ時点で中断する．

sec

sec

ElemID:4

部分文書（ 2 ） リンク li の終わりまで読んだとき，もしリンク li のリに対する適合度の降順でユーザへ提示することである．部分

intent に興味があれば，リンク先の二層目 sj を読む．

文書検索システムはクエリに適合する部分そのものをユーザに（ 3 ） 二層目 sj の終わりまで読んだ場合，リンク lj の末尾

提示するため，ユーザは文書中から情報要求を満たす部分を自から再度一層目を読み進める．

ら発見する必要がなくなり，情報検索を行う際のユーザの負担

なお，ユーザは一つの意図にのみ興味があるため，ユーザが閲を大きく軽減することが可能である．

覧する可能性のあるテキスト (トレイルテキスト) は，意図の3. 2 部分文書とその重複関係

種類数存在する．各トレイルテキストの情報利得は，iUnit の出現位置が加味される U-measure [22] によって計測される．具部分文書の概要について説明するために，図 2–図 4 を用いて具体例を示す．

体的には，重要な iUnit がトレイルテキストの冒頭に出現する

まず，図 2 は文書番号 (DocID) 1 の XML 文書の例であり，

ほど，U-measure のスコアが高くなる．また，ユーザが検索結

図 3 は図 2 の XML 文書を木構造で表現した図である．構造

果を確率的に読むことを想定し，全てのトレイルテキストを考

化文書は一般的に木構造で表現することができ，文書構造の視慮した情報利得の期待値は M-measure で計測される．

認性の向上を目的として度々木構造で表現される．このとき，上記を踏まえて，M-measure は下記の式 (5) で算出される．
∑
M=
P (i|q)Ui (ti )
(5)
i∈Iq

XML 文書のそれぞれの開始タグと終了タグが XML 木の各要素ノードのノード名に対応しており，タグの入れ子は要素ノードの親子関係によって表現されている．また，各要素ノードに

ただし，Iq はクエリ q における intent 集合，P (i|q) は q にお対して，文書順に部分文書番号 (ElemID) を割り振る．図 4 のける intent i の意図確率，Ui (ti ) は intent i のトレイルテキス

各部分文書は，図 3 の XML 木の各要素ノード以下に含まれ

ト ti の U-measure の値である．また，U-measure は下記の式るテキストノードを結合した文字列と対応する．つまり，文書(6) ，式 (7)，式 (8) によって算出される．

全体を表す article ノードと対応する部分文書は子孫に存在

Ui (t) =|t|∑

するテキストノード全てを結合した文字列であり，body ノー

gi (uj )d(uj )

(6)

j=1

post (u))d(u) = max(0, 1 −Lj∑chars(uj ′ )post (u) =(7)ドと対応する部分文書はその子ノードである三つの sec ノードに含まれるそれぞれのテキストノードを結合した文字列である．包含関係 (先祖 · 子孫関係) を持つ部分文書間においてテ(8)

j ′ =1

ただし，gi (ui ) は iUnit u の意図 i の下での重要度，d は位置依存の減価関数，chars(u) は記号や空白を除いた iUnit u の文字数である．従って，一層目の iUnit の重要度の評価は総合的重要度によって行われ，二層目の iUnit は各 intent ごとの重要度によって評価されることになる．

3. 部分文書検索の基本事項

キストノードの重複が発生するのはこのためである．なお，ある要素ノード (部分文書) に着目した際に，先祖にあたる要素
ノードを粒度の大きなノード，逆に子孫にあたる要素ノードを
粒度の小さなノードと表現する．
仮にユーザが “Early life . . . ”，“Windows. . . ” に関する情報を求める場合，部分文書検索では ElemID 3 の部分文書を提示する．これは，部分文書中にユーザが求める情報全てを含み，余分な情報を含まないためである．

本節では，部分文書検索の概要について説明する．

3. 3 部分文書検索における検索結果の提示方法

3. 1 部分文書検索技術の目標

検索結果の構築において，複数の方式が存在する．いくつか

部分文書検索における最大の関心は，構造化文書中からクエリに適合する箇所，即ち適合部分文書を抽出し，それらをクエの先行研究では重複が発生することを考慮せずに，クエリ処理

によって算出される部分文書の適合度に従ってランキングされた順位付きリストを提示していた．本論文では，このようなク
エリ処理によって得られた，重複を排除するために特別な処理を行っていないリストを重複リスト と呼ぶこととする．そして，

部分文書検索iUnits

文献 [11] において重複リストを用いた場合の検索精度の低下が報告されて以来，多くの研究ではリスト中から重複を排除した非重複リストを用いている．XML 検索のためのプロジェク
トである INEX (INitiative for Evaluation of XML retrieval)（注 4）

projectの XML 情報検索用のトラック全般 [6] においても非重複リストを使用している．

ランク付き
部分文書

部分文書

類似度算出

ランク付き
iUnits

図 5 iUnit のランキング手順

ションである INEX Wikipedia テストコレクション [7] におい

重複リストから非重複リストを作成する際には下記の三種類ては，同一 path 式を持つ部分文書は同じ属性に分類して統計の方式が存在する．

量を算出するアプローチが最も高精度と報告されている [20] もOneElem 一つの文書から文書中において最もスコアの高いのの，統計量算出に用いる文書数が十分に確保されない状況に部分文書を抽出する．

おいては path 式ベースの大域的重み算出では適切に統計量をMultiElem 重複が起こらない限り，スコアの降順に一つの算出できないということが報告されている [14]．2. 1 節で述べ文書から複数の部分文書を抽出する．

た本研究の実験で利用するテストコレクションの文書集合は大WholeDoc 文書全体を提示する．文書全体を提示すること

域的統計量を算出する上で十分の分量が確保されていない可能で，文書中の適合箇所は網羅的に抽出可能となるものの，非適性があるため，本稿では path 式ベースではなくタグベースの合箇所の抽出も行うという問題が存在する．文書検索と同義でアプローチを採用する．つまり，式 (9) の属性 a はタグとしてあるため，部分文書検索の本来の趣旨からは外れる．

統計量の算出を行う．

3. 4 高精度な部分文書検索

また，最終的に e のスコア Score(e) は，クエリキーワード

部分文書検索において利用されるスコアリング手法の多くは，文書検索用のスコアリング手法を基にしており，共通して用いられる統計量も存在する．文書検索と部分文書検索のスコアリ

集合を T として以下の式で算出される．
∑
Score(e) =w(p, e, ti )

(10)

ti ∈T

ング手法における最も大きな違いは，部分文書検索には 属性

4. 提 案 手 法の概念が導入されていることである．つまり，文書検索におい

2. 節と 3. 節より，重要な iUnit と適合部分文書はいずれては全ての文書は同じ属性を持つと見なして，全ての文書を母も文書中の適合箇所を表現する．このことを踏まえ，本研究で集団として大域的重みを算出する．それに対して部分文書におは，既存の部分文書検索技術を用いて抽出した，適合部分文書

いては，同じ属性を持つと見なす部分文書集合に分類し，それと考えられる部分文書から，重要な iUnit を特定することを目

ぞれを母集団として大域的重みの算出を行う．属性の分類は，指す．換言すれば，Hypothesis 1: “適合箇所，すなわち，重要同一タグを持つ部分文書は同じ属性を持つとするアプローチや，

な iUnit は部分文書検索によって高スコアを付与された部分文

同一 path 式を持つ部分文書は同じ属性を持つとするアプロー

書中に含まれる” に基づき，手法の提案を行う．
以降，iUnit Ranking サブタスクと iUnit Summarization サチなどが存在する．
部分文書検索用のスコリング手法としては，TF-IPF [16]，BM25E [17]，部分文書検索用クエリ尤度モデル [18] など多数
存在し，過去の研究において，BM25E が最も高精度検索に適切であるという結果が得られている [13]．従って，本稿ではブタスクそれぞれの取組みついて述べる．

4. 1 iUnit Ranking サブタスクへの取り組み
iUnit Ranking サブタスクでは，オーガナイザから提供される iUnit を総合的重要度の降順に並べる．

部分文書検索用のスコアリング手法として BM25E を用いる．

提案手法の概要を図 5 に示す．まず，文書集合である HTML

BM25E の重み付けでは，属性 a で表されるある部分文書 e 中

文書から部分文書を取り出す．続いて，クエリを用いて各部分の索引語 t の重み w(a, e, t) は以下の数式で算出される．

文書に対して部分文書検索技術によってスコアリングを行い，w(a, e, t) =(9)

(k1 + 1)tfe,tNa − afa,t + 0.5
· log
ele
pfa,t + 0.5
k1 ((1 − b) + b avel
)
+
tf
e,t
a
ただし，tfe,t を部分文書 e 中の索引語 t の出現頻度，ele を部
分文書 e の索引語数，avela を a で表される部分文書の平均
索引語数，Na を a で表される部分文書数，afa,t を a で表さ

ランキングされた部分文書のリストを取得する．更に，部分文
書と iUnit の類似度を算出し，iUnit のランキングを行う．その際，上位にランキングされた部分文書と類似した iUnit により大きなスコアを付与する．iUnit u のスコア Score(u) は下記の式で算出される．

Score(u) =∑ sim(u, e)norm(e)(11)

れ，かつ，t を含む部分文書数，k1 , b をパラメータとする．本e∈E

稿では，一般的に利用されるパラメータ値である k1 = 2.5 と

ただし，E はスコアリングに用いる部分文書集合，e は E に

b = 0.85 を設定する．

含まれる部分文書，sim(u, e) は u と e の類似度，norm(e) は部分文書検索システム評価のための大規模なテストコレク

e のランキングによる正規化とする．
以降，部分文書と iUnit の類似度算出方法 sim(u, w)，部分（注 4）： http://inex.mmci.uni-saarland.de/

文書のランキングによる正規化方法 norm(e)，スコアリングに一層目用いる部分文書 E の選別について述べる．
任意の部分文書と iUnit の類似度を算出する際に，いずれの二層目類似度算出方法が適切であるのか不明であるため，三種類の類
似度算出方法 F req (式 (12))，Ratio (式 (13))，Jaccard (式(14)) を検討する．
simF req (u, e) = count(u, e)

(12)

手順 2

iUnit

手順 3

iUnit

iUnit
iUnit

ただし，count(u, e) は部分文書 e と iUnit u に含まれる語の共起語数とする．

simRatio (u, e) =count(u, e)length(u)simJaccard (u, e) =

|u∩e|
|u∪e|

intent(13)

ただし，length(u) は u に含まれる語数とする．

(14)

・・
・

手順 1

intent

iUnit
iUnit

iUnit のスコアリングにおいて，ランキング上位の部分文書

intentの影響を大きく反映させるため，二種類の部分文書のランキン・・・

グによる正規化手法 Rank (式 (15)) と LogRank (式 (16)) を検討する．

normRank (e) = rank(e)(15)

図 6 iUnit Summarization サブタスクにおける検索結果構築

ただし，rank(e) は e のランキングとする．

normLogRank (e) = 1 + log(rank(e))

intent部分文書 ランク付き 合計 ランク付き
検索 部分文書 スコア intent(16)

Rank ではランキングが下位になるに連れて急激に正規化さ

A

80

B

B

90

A

C

70

C

れる値が大きくなるため，LogRank では正規化の値の緩やかに補正する．
スコアリングを行う際に考慮する部分文書 E は，下記の三クエリ +種類の方針で取得する．

EAllElem

リスト中全ての部分文書を用いる．

ET opP erElem

リストの上位 k パーセントの部分文書を用いる．

ET opElem

リストの上位 k 件の部分文書を用いる．

4. 2 iUnit Summarization サブタスクへの取り組み
iUnit Summarization サブタスクでは，二層構造に結果を整形する．提案手法では，iUnit と intent の配置方針においては MobileClick-1 [9] のベースライン手法の方針に準拠しつつ，各層ごとに適切なクエリを用いた iUnit のランキング手法や

intent のランキング手法を検討する．
まず，配置方針について，図 6 を用いて示す．
（ 1 ） 全ての intent を一層目の末尾に配置する．
（ 2 ） 文字数制限に達しない限り，一層目の冒頭から iUnitを配置する．
（ 3 ） 二層目の検索結果として，各 intent ごとに，文字数制
限を超えない限り iUnit を配置する．ただし，一層目に出現した iUnit は二層目には配置しない．
以降，intent のランキング手法，一層目と二層目の iUnit ラ
ンキング方法について述べる．

4. 2. 1 intent ランキング手法
評価尺度の M-measure では intent の位置も減価関数において考慮されているため，より意図確率の高い intent を上位に配置することでより高精度を実現することが可能となる．
提案する intent ランキング手法では，より多くの情報を取得できることが期待される intent に高いスコアを付与することを目指す．ランキング手法として，下記の 3 種類を提案する．

図 7 SumElemScore による intent のランキング

SumElemScore クエリに各 intent を追加した拡張クエリ
を用いて部分文書検索を行う．その後，得られたリストに含まれる部分文書の総スコアを各 intent のスコアとする．概要を
図 7 に示す．

NumResultElem SumElemScore では部分文書のスコアの和を intent のスコアとしていたのに対して，リストに含まれる部分文書の件数をスコアとする．

NumWebSearch 前述の二つの手法はいずれもテストコレ
クション内の文書集合から得られる統計量を用いて intent のランキングを行う手法であるが，文書集合に含まれる文書数が各クエリごとに上限 500 件のみであるため，限られた情報のみ
しか反映できていない可能性が存在する．そこで，外部情報として，拡張クエリを用いて Web 検索を行った際の検索結果の件数の降順に intent のランキングを行う（注 5）．

4. 2. 2 iUnit ランキングに用いるクエリ
一層目に配置されることが望ましい iUnit は，多数の intent
において重要な iUnit となる．その観点において下記の二種類の iUnit のランキングを提案する．

AllIntent クエリに全 intent を追加した全拡張クエリを用いて部分文書検索を行う．
（注 5）：文書集合の収集に用いた Web 検索エンジンと同様に Bing を利用した．

表 2 iUnit Ranking サブタスクの他の参加者との比較

表 1 iUnit Ranking サブタスクの実験結果

Team ID

Q-measure improvement

nDCG@3 nDCG@5 nDCG@10 nDCG@20 Q-measure

WholeDoc .9050

1.008

Freq

.7237

.7510

.7966

.8654

.8947

OneElem

.9047

1.008

Ratio

.7325

.7499

.7995

.8707

.8969

cuis

.9042

1.007

Jaccard

.6849

.7192

.7717

.8511

.8800

IRIT

.9036

1.007

Rank

.7443

.7632

.8060

.8748

.9005

UHYG

.9028

1.006

LogRank

.7341

.7518

.8017

.8727

.8983

IISR

.9004

1.003

TopPerElem .7453

.7627

.8065

.8751

.9007

ORG-L

.8975

1.000

TopElem

.7443

.7632

.8059

.8748

.9004

RISAR

.8972

1.000

AllIntent

.7551

.7712

.8104

.8796

.9031

ALICA

.8959

.998

EachIntent

.7511

.7688

.8112

.8776

.9025

YJST

.8953

.998

OneElem

.7641

.7764

.8140

.8815

.9047

ORG-R

.8859

.987

MultiElem

.7604

.7742

.8132

.8806

.9044

JUNLP

.8859

.987

WholeDoc

.7613

.7750

.8154

.8815

.9050

最も高精度を示した．いずれの手法も精度の向上が確認され，

EachIntent 拡張クエリを用いて部分文書検索を行い，各部分文書のスコアは各拡張クエリごとの部分文書のスコアの和とする．

Rank がより高精度という結果が得られた．
次に，スコアリングに用いる部分文書の選別結果について述べる．式 (11) の simRatio (u, e) と normRank を使用した．な

二層目の iUnit は各 intent に特化した iUnit が配置される

お事前に行った閾値調査の結果，TopPerElem において上位ことが期待される．この観点において，二種類の iUnit ランキ

33% の部分文書を選択した場合に最も高精度であり，TopElem

ングを提案する．

においては上位 2,000 件の部分文書を用いた場合に最も高精度

ExtendedQuery 拡張クエリを用いて部分文書検索を行う．

であった．TopPerElem を利用することで精度は向上したもの

IntentQuery intent の比重をより強くするため，オリジナの，TopElem では却って精度が低下した．

ルクエリは使用せず intent のみを用いて部分文書検索を行う．

なお，表 1 に掲載していない組合せの手法についても実験を

5. 評 価 実 験

行ったところ，式 (11) の類似度算出手法は simRatio (u, e)，部

本節では，iUnit Ranking サブタスクと iUnit Summariza-

分文書のランキングによる正規化は normRank ，スコアリング

tion サブタスクそれぞれにおいて，提案手法の有用性評価のに用いる部分文書は ET opP erElem ，すなわち TopPerElem がための行った評価実験について述べる．評価実験には 2. 節の最も高精度であった．従って，以降の実験では iUnit のランキ

データセットを利用し，部分文書検索手法は 3. 4 節で述べたングには TopPerElem を用いることとする．

BM25E を利用した．
5. 1 iUnit Ranking サブタスクの実験結果

5. 1. 2 追加の検証実験
次節の iUnit Summarization サブタスクにおける提案手法

4. 1 節にて，iUnit Ranking サブタスクのための，部分文書

である，AllIntent と EachIntent のポテンシャルを確認すると iUnit の類似度算出方法 (式 (11) の sim(u, e))，部分文書

ため，iUnit Ranking タスクにおいて評価を行った．その結果，のランキングによる正規化方法 (式 (11) の norm(e))，スコア

いずれも精度が向上し，AllIntent がより高精度であるというリングに用いる部分文書の選別手法 (式 (11) の E) の検討を

結果を示した（注 6）．

行った．表 1 を参照しつつ各項目に関する評価実験を行う．なお，公式尺度は Q-measure である．

また，非重複リストを用いた場合の精度の検証を AllIntent
に対して行った．その結果，いずれも重複リストを用いた場合

また，3. 3 節で述べた通り部分文書検索においては検索結果よりも精度が向上したものの，部分文書を提示する MultiElemの提示において非重複リストを用いることが一般的であるものと OneElem より，文書検索と同義である WholeDoc が最もの，現時点では iUnit のランキングにおいてはどのような挙動

高精度であることを示した．

を示すのか明らかではないため，特記しない限り以降の実験では重複リストを用いる．

なお，以前著者らが行った Web 文書の文書構造に関する調査 [12] の結果，Web 文書では物理的な文書構造が，章立てな

5. 1. 1 提案手法の評価

どの論理的な文書構造と一致していないということが示唆され類似度算出手法 Freq ，Ratio ，Jaccard の実験を行う．式ており，この状況では部分文書検索の性能が最大限発揮できな(11) において，部分文書による正規化は行わず (norm(e) = 1)，

い可能性がある．従って，Web 文書に対して，論理的な文書構

EAllElem としてスコアリングに全ての部分文書を用いた．そ造を表すように文書構造の整形を行うことで，より部分文書検の結果，Ratio が最も高精度という結果が得られた．

索の精度を向上することが期待される．

続いて，部分文書のランキングによる正規化に関する評価を続いて，MobileClick iUnit Ranking サブタスクの他の参加者行うため，Rank と LogRank の実験を行う．式 (11) において，の公式ラン結果との比較結果を表 2 に示す（注 7）．improvement

simRatio (u, e)，EAllElem を使用した．
LogRank の底として 1.1，1.5，2，ネイピア数，10 にて実（注 6）：intent の抽出においては MobileClick と同様 NTCIR のタスクであ験を行った結果，底が 2 において最も高精度を示した．また，る INTENT [23] や IMine [26] において取り組まれており，これらの研究の成

シグモイド関数においてもパラメータを調整しつつ複数の関数
において正規化を試みたものの，底が 2 の log による正規化が果を利用すれば取得可能である．
（注 7）：複数のランを提出した参加者に関しては，最も高精度のランのみ提示する．また，著者らが提出したラン (titec) は除外している．

表 3 iUnit Summarization サブタスクの実験結果

表 4 iUnit Summarization サブタスクの他の参加者との比較

M-measureTeam ID

Simple (TopPerElem)

18.105OneElem 18.530

M-measure improvement
1.097

AllIntent & ExtendedQuery

18.442

ORG-T

16.8981.000

EachIntent & ExtendedQuery 18.315

YJST

16.887.999

AllIntent & IntentQuery

18.447

IRIT

16.563.980

EachIntent & IntentQuery

18.313cuis

16.419.972

SumElemScore

18.428RISAR

16.047.950

NumResultElem

18.365

ORG-R

14.105.835

NumWebSearch

18.469UHYG

13.055.773

OneElem

18.530JUNLP

11.703.693

MultiElem

18.508

ALICA

8.497

.503

WholeDoc18.363

結果，iUnit Ranking と異なる結果が得られた．具体的には，は，ベースライン手法 (ORG-L) と比較した際の精度向上率を

OneElem ，MultiElem ，WholeDoc という順で高い精度を達成

表す．state-of-the-art の手法を提案した cuis を上回る検索精した．つまり，文書全体よりも部分文書検索を利用することで度を達成した．また，符号検定の結果，提案手法はベースライ

検索精度が向上した．iUnit Ranking サブタスクは提供される

ン手法 (ORG-L) と比較して有意な差はなかった．

iUnit 全てをランキングするタスクであるのに対して，iUnit

5. 2 iUnit Summarization サブタスクの実験結果

Summarization では 420 文字までの結果のみを提示する．こ4. 2 節にて，iUnit Summarization サブタスクにおける，一れらを鑑みると，限られた文字数においてより網羅的に適合す

層目及び二層目の iUnit のランキングで用いるクエリの検討とるテキストを提示する上では，部分文書検索の枠組みでスコア

intent のランキング手法の提案を行った．それらの評価を行っ

リングを行うことが適切であることが示唆された．

た結果を表 3 に示す．なお，公式尺度は M-measure である．

続いて，MobileClick iUnit Summarization サブタスクの5. 2. 1 提案手法の評価

他の参加者の公式ラン結果との比較結果を表 4 に示す （注 8）．

提案手法のシンプル手法として，TopPerElem の評価を行OneElem が最も高精度な手法であった．また，符号検定の結う．その際，一層目はオリジナルクエリ，二層目はオリジナル

果，他グループのランのうち最も高精度な手法であるベースラ

クエリと各 intent (拡張クエリ)，intent は初期の順序 (ランダイン手法 (ORG-T ) と比較して，提案手法 OneElem は統計的

ム) である．

に有意に高精度であった (p < 0.01)．

提案手法に関して，一層目のクエリの選択肢として AllIntent

以上より，MobleClick タスクにおいて部分文書検索を用いと EachIntent ，二層目のクエリの選択肢として ExtendedQuery

たアプローチによって，比較手法や文書検索手法と比較して高と IntentQuery が存在する．これらの全組合せ 4 通りにおい

精度な検索を実現することができた．従って，Hypothesis 1:て，AllIntent と IntentQuery が最も高精度であった．

“適合箇所，すなわち，重要な iUnit は部分文書検索によって

EachIntent に着目した場合に，IntentQuery よりも Extend-

高スコアを付与された部分文書中に含まれる” は確からしいと

edQuery と組み合わせた場合により高精度を示した．これは一いう結果が導き出された．また，文書検索アプローチは比較手

層目に EachIntent を用いた場合には，ある intent において重法よりも高精度な結果を示した．

要度の高い iUnit が上位に配置されており，その結果として一層目に配置されるべき，多数の intent において重要度の高い

iUnit の配置ができていないことを示唆する．従って，タスクの性質上，AllIntent と IntentQuery の組合せがより高精度を示したと予想される．以降の実験では，AllIntent と IntentQueryの組合せを利用する．
次に，intent のランキングに関する評価を行う．intent のランキング手法 SumElemScore ，NumResultElem ，NumWeb-

Search のうち，SumElemScore と NumResultElem は逆に精度が低下した．その一方で，NumWebSearch は精度が向上した．このことから，拡張クエリの結果の件数はその intent に
よって得られる情報利得の予想において有用であり，小規模の文書集合から得られる統計量では intent ごとの情報利得の期待値を正確に予測することは困難であると示唆された．

6. 関 連 研 究
本節では，他の MobileClick 参加者のうち，ベースライン手法，及び，公式ラン結果上位の参加者の手法をレビューする．
まず，ベースライン手法 [10] では，odds ratio を用いて iUnit
中の語の重みの算出を行う．odd ratio による語の重み付けでは，クエリ語を含むページ中に多く出現して，クエリ語を含まないページ中に出現しないほど，語の重みが大きくなる．iUnitのスコアは，iUnit に含まれる語の重みの総和で求める．
公式ランの iUnit Ranking において最も高い精度を達成した Lai ら [15] は，LDA を用いた手法を提案した．その際，ト
ピックは intent と見なす．LDA を用いてモデルが構築されれば，各クエリのトピックの確率値 (意図確率と同義) を求める．
次に，各文書を最も類似度の高いトピックに割り振る．トピッ
クごとに文書のリストが構築されれば，ラウンドロビン方式で，以上より，一層目は AllIntent ，二層目は IntentQuery ，in-

各トピックから一つずつ文書抽出してランキングを行う．全ト

tent ランキング手法は NumWebSearch の組合せがもっとも高ピックから文書の抽出終われば，またはじめからトピックごと精度であるという結果が得られた．

5. 2. 2 追加の検証実験
非重複リストを用いた場合の精度の検証を，AllIntent ，In-

tentQuery ，NumWebSearch の組合せに対して行った．そのに文書の抽出を行う．文書のランキング完了すれば，iUnit と（注 8）：複数のランを提出した参加者に関しては，最も高精度のランのみ提示する．また，著者らが提出したラン (titec) は除外している．

文書の共起語の数をスコアとして iUnit に付与する．その際，文書のランキングで正規化を行う．

[6]

Chellal ら [2] は，シャノンのエントロピーをベースに語の出現頻度や文書頻度，Word2vec などを用いて拡張して語の重み[7]を算出する．また，iUnit のスコアは，iUnit に含まれる語の重みの総和で表す．

[8]

Lai ら [15] の手法が高精度であったことからも，iUnit を直接重み付けするアプローチよりも，まずは文書 (提案手法では部分文書) に対してスコアリングを行い，その結果を踏まえて[9]

iUnit のスコアリングを行うことがより適切であると考えられる．その理由として，iUnit の中には 2, 3 語しか含まないもの[10]も多く存在し，これらの iUnit に対しては適切に語の重み付けを行うことが困難であるためと考えられる．

[11]

また，Chellal ら [2] は odds ratio のように単語の出現の有無だけでなく，出現頻度やより複雑な統計量を利用している[12]

ため，他の odd ratio を利用する研究と比較して高精度を実現できたと考えられる．その点において，我々の採用している[13]

BM25E も多数の統計量を用いて語の重み付けを行っている．

7. お わ り に
本稿では，モバイル環境における情報検索において高精度を[14]実現するため，部分文書検索のアプローチを利用した．提案手法では，まず文書集合に対して部分文書検索を行い，部分文
書のランキングを行う．次に部分文書と iUnit の類似度を計測[15]

し，より上位にランキングされた部分文書とより類似度の高い

iUnit に高いスコアを付与する．

[16]

iUnit Ranking サブタスクにおいて，類似度算出手法，部分文書による正規化，スコアリングに用いる部分文書の選別を[17]行うことで，state-of-the-art の手法を上回る精度を達成した．

iUnit Summarization サブタスクでは，より高い情報利得が期[18]待される intent を上位に配置したり，各層ごとに適切なクエリを用いた部分文書を行うことで，ベースラインの手法と比較して 9.7% の精度向上を達成した．

[19]

[20]

今後の課題として，本研究では提供された iUnit を利用したが，より実用的なモバイル検索システム実現のためには，部分文書から iUnit を自動抽出する手法の提案を行う必要がある．

[21]

論理構造と合致するように Web 文書の構造整形も今後の課題[22]の一つである．

謝辞本研究の一部は，JSPS 科研費 JP15K20990，JP26280115，[23]

JP15H02701, JP16H02908 の助成を受けたものである．ここに記して謝意を表す．

[24]

文

献

[1] Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt
Deeds, Nicole Hamilton, and Greg Hullender. Learning to Rank
using Gradient Descent. In Proc. of the 22th ICML, pp. 89–96,
2005.
[2] Abdelhamid Chellal and Mohand Boughanem. IRIT at the
NTCIR-12 MobileClick-2 Task. In Proc. of the 12th NTCIR,
pp. 143–146, 2016.
[3] Monalisa Dey, Anupam Mondal, and Dipankar Das. NTCIR12 MOBILECLICK: Sense-based Ranking and Summarizationof English Queries. In Proc. of the 12th NTCIR, pp. 138–142,
2016.
[4] Wen-Bin Han, Hung-Hsiang Wang, and Richard Tzong-Han
Tsai. NCU IISR System for NTCIR-12 MobileClick2. In Proc.
of the 12th NTCIR, pp. 115–117, 2016.
[5] Sho Iizuka, Takayuki Yumoto, Manabu Nii, and Naotake
Kamiura. UHYG at the NTCIR-12 MobileClick Task: Link-

[25]

[26]

[27]

based Ranking on iUnit-Page Bipartite Graph. In Proc. of the
12th NTCIR, pp. 118–125, 2016.
Jaap Kamps, Shlomo Geva, Andrew Trotman, Alan Woodley,
and Marijn Koolen. Overview of the INEX 2008 Ad Hoc Track.
In INEX 2008 Workshop Pre-proceedings, pp. 1–28, 2008.
Jaap Kamps, Shlomo Geva, Andrew Trotman, Alan Woodley,
and Marijn Koolen. Overview of the INEX 2008 Ad Hoc Track.
In Formal Proc. of INEX 2008 Workshop, pp. 1–28, 2009.
Makoto P. Kato, Matthew Ekstrand-Abueg, Virgil Pavlu, Tetsuya Sakai, Takehiro Yamamoto, and Mayu Iwata. Overview of
the NTCIR-10 1CLICK-2 Task. In Proc. of the 10th NTCIR,
pp. 182–211, 2013.
Makoto P. Kato, Matthew Ekstrand-Abueg, Virgil Pavlu Tetsuya Sakai, Takehiro Yamamoto, and Mayu Iwata. Overview of
the NTCIR-11 MobileClick Task. In Proc. of the 11th NTCIR,
pp. 195–207, 2014.
Makoto P. Kato, Tetsuya Sakai, Takehiro Yamamoto, Virgil
Pavlu, Hajime Morita, and Sumio Fujita. Overview of the
NTCIR-12 MobileClick Task. In Proc. of the 12th NTCIR, pp.
104–114, 2016.
Gabriella Kazai, Mounia Lalmas, and Arjen P. de Vries. The
Overlap Problem in Content-Oriented XML Retrieval Evaluation. In Proc. of the 27th ACM SIGIR, pp. 72–79, 2004.
Atsushi Keyaki, Jun Miyazaki, and Kenji Hatano. Applying
XML Element Retrieval Techniques to Web Documents. DBSJ
Journal, Vol. 13, No. 1, pp. 64–70, 2015.
Atsushi Keyaki, Jun Miyazaki, Kenji Hatano, Goshiro Yamamoto, Takafumi Taketomi, , and Hirokazu Kato. A Path
expression-Based Smoothing of Query Likelihood Model for
XML Element Retrieval. In Proc. of the 1st ACIT, pp. 296–
300, 2013.
Atsushi Keyaki, Jun Miyazaki, Kenji Hatano, Goshiro Yamamoto, Takafumi Taketomi, and Hirokazu Kato. Fast Incremental Indexing with Eﬀective and Eﬃcient Searching in XML
Element Retrieval. International Journal of Web Information
Systems (IJWIS), Vol. 9, pp. 142–164, 2013.
Kwun Ping Lai, Wai Lam, and Lidong Bing. CUIS at the
NTCIR-12 MobileClick2 Task. In Proc. of the 12th NTCIR,
pp. 134–137, 2016.
Fang Liu, Clement Yu, Weiyi Meng, and Abdur Chowdhury. Effective Keyword search in Relational Databases. In Proc. of
ACM SIGMOD, pp. 563–574, 2006.
Wei Liu, Stephen Robertson, and Andrew Macfarlane. FieldWeighted XML Retrieval Based on BM25. In Formal Proc. of
INEX 2005 Workshop, pp. 161–171, 2006.
Paul Ogilvie and Jamie Callan. Parameter Estimation for a Simple Hierarchical Generative Model for XML Retrieval. In Formal
Proc. of INEX 2005 Workshop, pp. 211–224, 2006.
Kevin Ong, Ruey-Cheng Chen, and Falk Scholer. RMIT at the
NTCIR-12 MobileClick-2: iUnit Ranking and Summarization
Subtasks. In Proc. of the 12th NTCIR, pp. 104–114, 2016.
Benjamin Piwowarski and Patrick Gallinari. A Bayesian Framework for XML Information Retrieval: Searching and Learningwith the INEX Collection. Journal of Information Retrieval,Vol. 8, No. 4, pp. 655–681, 2005.
Testuya Sakai. The Reliability of Metrics Based on Graded Relevance. Journal of Information Processing and Management,
Vol. 43, No. 2, pp. 531–548, 2007.
Testuya Sakai and Zhicheng Dou. Summaries, Ranked Retrieval
and Sessions: a Unified Framework for Information Access Evaluation. In Proc. of the 36th SIGIR, pp. 473–482, 2013.
Tetsuya Sakai, Zhicheng Dou, Takehiro Yamamoto, Yiqun Liu,Min Zhang, and Ruihua Song. Overview of the NTCIR-10
INTENT-2 Task. In Proc. of the 10th NTCIR, pp. 94–123,
2013.
Tetsuya Sakai, Makoto P. Kato, and Young-In Song. Overview
of NTCIR-9 1CLICK. In Proc. of the 9th NTCIR, pp. 180–201,
2011.
Keishi Tajima, Kenji Hatano, Takeshi Matsukura, Ryouichi
Sano, and Katsumi Tanaka. Discovery and Retrieval of Logical
Information Units in Web. In Proc. of WOWS in conjunction
with the 4th DL, pp. 180–201, 1999.
Takehiro Yamamoto, Yiqun Liu, Min Zhang, Zhicheng Dou,Ke Zhou, Ilya Markov, Makoto. P. Kato, Hiroaki Ohshima, andSumio Fujita. Overview of the NTCIR-12 IMine-2 Task. In Proc.
of the 12th NTCIR, pp. 8–26, 2016.
Tatsunori Yoshioka and Takashi Yukawa. NUTKS at NTCIR-12
MobileClick2: iUnit Ranking Subtask Using Topic Model. In
Proc. of the 12th NTCIR, pp. 131–133, 2016.