領域代数を用いた構造化テキスト検索の頑健でスケーラブルなモデル
増田 勝也 † 二宮 崇 ‡† 宮尾祐介* 辻井 潤一*‡
† 東京大学大学院情報理工学系研究科コンピュータ科学専攻‡CREST, 科学技術振興機構 *東京大学大学院情報学環{kmasuda,ninomi,yusuke,tsujii}@is.s.u-tokyo.ac.jp

1

はじめにContaining
Not Containing
Contained In
Not Contained In
Both OfGq1 ¤q2 = Γ({a|a ∈ Gq1 ∧ ∃b ∈ Gq2 .(b < a)})Gq1 6¤q2 = Γ({a|a ∈ Gq1 ∧ 6 ∃b ∈ Gq2 .(b < a)})Gq1 ¢q2 = Γ({a|a ∈ Gq1 ∧ ∃b ∈ Gq2 .(a < b)})Gq1 6¢q2 = Γ({a|a ∈ Gq1 ∧ 6 ∃b ∈ Gq2 .(a < b)})Gq1 4q2 = Γ({c|c < (−∞, ∞) ∧ ∃a ∈ Gq1 .∃b ∈Gq2 .(a < c ∧ b < c)})Gq1 5q2 = Γ({c|c < (−∞, ∞) ∧ ∃a ∈ Gq1 .∃b ∈Gq2 .(a < c ∨ b < c)})Gq1 3q2 = Γ({c|c = (ps , p0e ) where ∃(ps , pe ) ∈Gq1 .∃(p0s , p0e ) ∈ Gq2 .(pe < p0s )})XML や領域代数を含めたテキスト検索の分野では、タグなどで示されるテキスト中の構造を指定することにより従来のキーワード検索では検索できない情報を検索One Ofする手法が研究されてきている [3, 6, 2, 7, 1]。しかしながら、それらの手法は従来のキーワード検索のような頑Followed By
健性を持たず、クエリを与えたときにそのクエリの完全一致のみを出力する手法であるかもしくは頑健ではある
表 1: 領域代数の演算が全文書に対して計算を行うために Web のような大規模文書集合に対しては適用できない手法であった。
本研究では構造化テキストに対する頑健でスケーラブルな近接構造検索モデルを提案する。頑健性を改善する で定義される。この関数 Γ を用いることで、上の演算子ためにクエリから作られるサブクエリを用いる。これに による演算の結果は表 1 のように表現される。
よりクエリに完全には一致していないが、部分的に一致
領域代数を用いたクエリは、図 1 の木構造で表現されしている文書も検索される。各サブクエリに対して重み る。このクエリ ‘[book] ¤([title] ¤ “retrieval”)’ は「タを与えることで文書とクエリとの関連度を計算しランキ イトルに “retrieval” を含む本」を表す。領域代数を用いング検索を行う。またスケーラビリティを改善するため たクエリに一致する領域を検索するアルゴリズムは、そにクエリに対する関連度の近似値を用いたフィルタリン のクエリ中に現れる単語で最も文書集合全体での頻度がグを行う。フィルタリングを行うことで関連度計算のコ 低い単語の頻度に線形の計算量であり、高速に検索を行ストが削減され、大規模文書集合に対する高速な検索が うことができる。
可能となり、スケーラビリティが改善される。
本研究ではこの領域代数を基に頑健性及びスケーラビリティを改善したモデルを提案する。

2

背景:領域代数

テキスト中の構造を指定した検索を行う枠組みとして
領域代数 [3, 6] がある。領域代数は開始位置と終了位置の組で表現される領域の集合と領域の集合に対する演算により定義される。
本研究は [3] で提案されている領域代数を基にしている。この領域代数は以下の７個の演算子からなる。

• 包含演算子 (¤, 6¤, ¢, 6¢):二領域間の包含関係• 結合演算子 (4,5):二領域の組合せ (AND, OR)• 順序演算子 (3):二領域の順序関係
二領域間の包含関係は次のように表現される。
領域 r = (pb , pe )(pb :開始位置、pe :終了位置) が領域 r0 =(p0b , p0e ) を含む ⇔ pb ≤ p0b ≤ p0e ≤ pe
この関係を r0 < r で表す。Clarke らによる領域代数 [3]では、演算結果としての領域集合の中に包含関係を満たす領域が存在する場合には最も内側の領域のみ返すように定義されている。これは領域の集合 S に対する関数 ΓΓ(S) = {r|r ∈ S∧ 6 ∃r0 ∈ S.(r0 6= r ∧ r0 < r)}3

頑健性の改善

領域代数を用いた検索ではクエリに対する完全一致のみが検索され、部分一致は検索されない。そこで頑健性を改善するために、与えられたクエリから作られるサブクエリを用い、そのサブクエリに一致する領域を含む文書も出力することで完全一致だけでなく部分一致も検索されるようにする。また文書のクエリに対する関連度を計算し、それを基にランキングを行う。関連度計算はまずサブクエリと文書の間の関連度を計算し、それらの関連度からクエリ全体とサブクエリの関連度を計算する。
サブクエリは以下のように定義する。
定義 1 (サブクエリ) クエリ q の木構造表現における各ノードを根とする部分木をサブクエリ q1 , q2 , ..., qn と定義する。
図 1 のクエリ ‘[book] ¤ ([title] ¤ “retrieval”)’ の場合、サブクエリは表 2 の q1 , ..., qq となる。
文書とサブクエリの関連度は、サブクエリのその文書  

    

 !"#%$&'  "!

 

#%$'&)(+*    

図 1: クエリ ‘[book] ¤([title] ¤ “retrieval”)’ の木構造
表現
q1q2
q3
q4
q5
q6
q7q8q9“hbooki”“h/booki”“htitlei”“h/titlei”“retrieval”‘[title]’‘[title] ¤ “retrieval”’‘[book]’‘[book] ¤ ([title] ¤ “retrieval”)’
















図 2: 適合率 (our 対 exact)  
 !#"

 $&%('*)

  

表 2: クエリ ‘[book] ¤ ([title] ¤ “retrieval”)’ に対するサブクエリ

  


での重みと、サブクエリ自身の文書集合での重みから計算される。



図 3: 適合率 (our 対 flat)

定義 2 (文書とサブクエリの関連度) サブクエリ qi の文書 d での重みを wq,d 、qi の文書集合での重みを wqi
これらの値を用いて文書とサブクエリ、およびクエリとする。qi と d の関連度 φ(qi , d) は関連度を表す関数 µ全体との関連度を以下のように定義する。
を用いて次のように定義される。

φ(qi , d) = µ(wqi ,d , wqi )文書と各サブクエリの関連度が計算された後、それらの関連度を用いて以下のように文書とクエリ全体の関連度を計算する。

φ(qi , d)=Φ(q, d)=µ(wqi ,d , wqi ) = tfqi ,d idfqi
Pni=1 φ(qi , d)qP
qPnn22tfi=1i=1 idfqi
qi ,d

定義 3 (文書とクエリ全体の関連度) サブクエリ qi と文書 d の関連度を φ(qi , d) とする。d とクエリ q の関連度 Φ(q, d) はクエリ全体との関連度を表す関数 ρ を用実験
いて以下のように定義される。
以上のモデルを実装し実験を行った。評価には情報検Φ(q, d) = ρ(φ(q1 , d), φ(q2 , d), ..., φ(qn , d))索の評価に使われる OHSUMED テストコレクション [4]これらの重みや関連度を表す関数についてはさまざま を用いた。OHSUMED は、348,566 個の医学論文のアブな重みや関数が適用できるが、ここではキーワードに対 ストラクトと、106 個のクエリからなる。各クエリに対する重み付けに用いられる TFIDF 値を以下のように構 し関連するアブストラクトの集合が与えられている。
造付クエリに拡張した値を使用する。
OHSUMED テストコレクションのクエリは自然言語で書かれているため、人手で領域代数のクエリに変換し定義 4 (クエリの TFIDF 値) 文書 d 中のクエリ q と一致する領域の数を f reqq (d)、クエリ q と一致する領域を た 12 個のクエリを用いた。使用したクエリの例を表 3 に含む文書数を dfq 、全体での文書数を N とする。クエリ 示す。一行目が領域代数に変換したクエリ、二、三行目
q の文書 d における TF 値およびクエリ q の IDF 値を以 が元の OHSUMED のクエリである。また OHSUMEDの検索対象のアブストラクトには文書構造は付与されて下のように定義する。
いるものの、意味タグは付与されていないため、専門用½
1 + log(f reqq (d)) (if f reqq (d) 6= 0)
語の最長一致を用いて意味タグを付与した。
tfq,d =0(if f reqq (d) = 0)
提案モデル (our)、領域代数 (exact)、キーワード検索½( flat) の３つのモデルについて実験を行った。提案モデ(if dfq 6= 0)log( dfNq )idfq =ルとキーワード検索については上位 100 文書、領域代数0(if dfq = 0)

1

‘ “postmenopausal” 4 ([neoplastic] ¤ (“breast” 3 “cancer”)) 4 ([therapeutic] ¤ (“replacement” 3 “therapy”)) ’
55 year old female, postmenopausal
does estrogen replacement therapy cause breast cancer

表 3: クエリ例

    !
"$#&%(' )+* %-,.'   

図 4: 再現率

function Retrieve(q): ranking list;
begin
L := ø;Q := SelectSubquery(q,v);Q0 := RemoveOverlapQuery(Q);S := EvalExact(Q0 );foreach d ∈ S
begin
r := CalcRel(d,q);
PushRanking(L,d,r);
end
return L;
end
SelectSubquery: IDF 値が v を超えるサブクエリの集合を返す
RemoveOverlapQuery: Q の中でクエリ q と q 0 が「q が q 0 のサブクエリである」という関係にあるクエリ q 、q 0 がある場合 q 0 の方を取り除き、その結果のクエリ集合を返す
EvalExact: Q 中の各サブクエリと一致する領域を含む文書の集合を返す
CalcRel: 文書 d とクエリ q の関連度を返す
PushRanking: 文書 d と関連度 r の組をランキングリスト L に加える

図 5: 検索アルゴリズム
については完全一致した文書をすべて取り出し、適合率、再現率を比較した。その結果を図 2、3、4 に示す。領域
代数 (exact) と提案モデル (our) を比べると、再現率は提案モデルのほうが高く、領域代数では検索できない文書が検索できており頑健性が改善されていることがわか サブクエリの中でも重みの高いサブクエリを含む文書はる。また適合率に関しては、領域代数での検索結果があ クエリとの関連度が高くなると考え、サブクエリの IDFる場合にはほぼ同じ適合率を示している。またキーワー 値で関連度の近似値を以下のように定義する。
ド検索 (flat) と提案モデル (our) を比較すると、クエリ
idfq (文書 d がサブクエリ qi をによって差はあるものの全体としては適合率、再現率と含む場合)
もに提案モデルが上回っている。
φ0 (qi , d) =0(
文書 d がサブクエリ qi を含まない場合)

4

スケーラビリティの改善：フィルタリング

Φ0 (q, d)=max φ0 (qi , d)i

大規模な文書集合を検索対象とする場合、全文書に対してクエリとの関連度計算を行うことは非常に高コストフィルタリングを用いた検索アルゴリズムを図 5 に示である。そこで、ある関連度の近似値を定義し、その値す。クエリが与えられた後、クエリからサブクエリを作が閾値を超える文書に対してのみ関連度計算を行う。閾
る。次に各サブクエリに対して IDF 値を無作為抽出さ値を設定することで関連度計算を行う文書数を制限し、れた文書集合において計算し、IDF 値が閾値を超えるサ高速に関連度計算およびランキングを行うことができる。
ブクエリの集合を作る。その集合の中で、クエリ q と q 0
なおこの関連度の近似値はが「クエリ q が q 0 のサブクエリである」という関係にあるクエリ q 、q 0 がある場合には、q 0 の方を取り除く。そ• 近似値が高ければ関連度も高いの結果のクエリ集合中のクエリを含む文書を全て取り出• 近似値が高い文書を高速に取り出せる
し、それらの文書に対してのみスコア計算を行い、ランといった特徴を持つことが望ましい。近似値がこれらの キングを作成する。
特徴を持つ場合にはフィルタリングの効果が高くなり、フィルタリングで関連度が高い文書を取りこぼすことなサブクエリの IDF 値の近似計算く大幅に検索時間を短縮することができる。
このようなフィルタリング手法はキーワード検索におIDF 値の計算は無作為抽出された文書集合中で近似的いてはあらかじめキーワードに対する重みを計算しておき利用する手法 [5] が提案されている。しかしながら構 に計算する。正確な IDF 値を計算するためには全ての造付のクエリの場合には、単語と演算子を組み合すこと 文書に対して各サブクエリの有無を計算しなければならでクエリを無限に考えることができるため、あらかじめ ず、時間がかかってしまう。そこで無作為抽出を用いてクエリに関する重みを計算することはできない。そこで、 高速に近似的に IDF 値を計算する。

5%'&)(%'&)( %'&)( %'&)(+*%'&)( %'&)(-,%'&)( %'&)(/.
%'&)( %'&)( 10%'&)( %'&)( $"#!
 


図 6: フィルタリングによる上位 10 文書の順位変化

関連度計算を行う文書集合の取得
各サブクエリの IDF 値が計算された後、以下で表されるサブクエリを含む文書集合を取り出す。

{qi |idfqi > v∧ 6 ∃qj .(idfqj > v ∧ qj ≺ qi )}(v:閾値、qj ≺ qi :qj が qi のサブクエリである) 例えばクエリ ‘[title] ¤ “retrieval” ’ の IDF 値が閾値を超えた場合、そのサブクエリ ‘[title]’、“retrieval” の IDF 値が閾値を超えなければ ‘[title] ¤ “retrieval” ’ を用いる。もし “retrieval” の IDF 値も閾値を超えていれば ‘[title] ¤“retrieval” ’ は用いずに “retrieval” のみを用いる。なぜならこの場合、‘[title] ¤ “retrieval” ’ を含む文書は必ず“retrieval” を含むため、‘[title] ¤ “retrieval” ’ を用いる必要はないからである。

実験
3 章の実験で用いた OHSUMED テストコレクションを用いてフィルタリングの実験を行った。無作為抽出で5000 文書を取り出し IDF 値の計算を行った。また閾値
としては 4.605 = log 500050 を用いた。すなわちフィルタリングには無作為抽出された 5000 文書中、50 文書以下で出現するサブクエリを用いた。実験はフィルタリングの有無による検索時間の違いおよび検索結果の文書の順位の変化を調べた。
検索時間は 12 クエリの平均で次のようになった。
フィルタリング有り : 0.20 秒
フィルタリング無し : 8.63 秒
フィルタリングにより、検索時間が大幅に短縮されていることがわかる。
また、フィルタリングによる文書の順位の変化を図 6に示す。無作為抽出を行ったことによる IDF 値の変化によって順位が多少変化しているものの、フィルタリング無しでの上位の文書がフィルタリングにおいて選び出されないということはなかった。

まとめと今後の課題

本論文では構造化テキストに対する頑健でスケーラブルな近接構造検索モデルを提案した。クエリから作られるサブクエリを利用することで頑健性を改善し、近似値によるフィルタリングを行うことでスケーラビリティを改善した。
今後の課題としては精度の向上が考えられる。現在はキーワード検索で使われる TFIDF 値を領域代数のクエリに拡張した値を利用して関連度計算を行っており、いくつかのクエリでキーワード検索より精度が低いという結果が出ている。この結果の原因としては、実験に用いた OHSUMED テストコレクションにはもともと簡単な文書構造以外の構造はついておらず、クエリも自然言語のクエリであり人手で構造をつけたため構造を指定することが検索結果にそれほど良い影響を与えない可能性がある、という点も考えられるが、重み付けについてはまだ改善の余地があると考えられる。またフィルタリングに関しては、今回はサブクエリの IDF 値を用いているがその計算に無作為抽出を用いているためその誤差によるIDF 値の変化が順位の変化をもたらしており、IDF 値の計算法に改善の必要があると考えられる。

参考文献[1] D. Carmel, Y. S. Maarek, M. Mandelbrod, Y. Mass,and A. Soffer. Searching XML documents via XML
fragments. In Proceedings of the 26th International
ACM SIGIR Conference, pages 151–158, 2003.
[2] T. Chinenyanga and N. Kushmerick. Expressiveand efficient ranked querying of XML data. In Proceedings of WebDB-2001, 2001.
[3] C. L. A. Clarke, G. V. Cormack, and F. J.
Burkowski. An algebra for structured text search
and a framework for its implementation. The computer Journal, 38(1):43–56, 1995.
[4] W. Hersh, C. Buckley, T. J. Leone, and D. Hickam.
OHSUMED: an interactive retrieval evaluation andnew large test collection for research. In Proceedingsof the 17th International ACM SIGIR Conference,pages 192–201, 1994.
[5] M. Persin, J. Zobel, and R. Sacks-Davis. Filtereddocument retrieval with frequency-sorted indexes.
Journal of the American Society of Information
Science, 47(10):749–764, 1996.
[6] A. Salminen and F. Tompa. Pat expressions: analgebra for text search. Acta Linguistica Hungarica,
41(1-4):277–306, 1994.
[7] T. Schlieder and H. Meuss. Querying and ranking
XML documents. JASIST, 53(6):489–503, 2002.