ウェーブレット木を用いたN-gram IDFの近似計算手法

(1)

DEIM Forum 2016 A1-1

ウェーブレット木を用いた N-gram IDF の近似計算手法

白川真澄

†

原

隆浩

†

大阪大学大学院情報科学研究科〒 565–0871 大阪府吹田市山田丘 1-5

E-mail:

†{

shirakawa.masumi,hara

}

@ist.osaka-u.ac.jp

あらまし

N-gram IDF は，語の大域的重みである IDF を単語 N-gram に理論的に拡張したものであり，異なる長さ

の単語 N-gram 間で重みを比較できるという特長を持つ．また，単語 N-gram の新たな特徴量として，幅広い応用が期

待できる．しかし，N-gram IDF の算出には，N-gram を構成する単語の論理積に対する文書頻度が必要であるため，

計算量が大きいという問題があった．そこで本稿では，ウェーブレット木を用いて N-gram IDF の近似値を算出する

手法を提案する．提案手法は，各 N-gram に対し，構成単語の論理積に対する文書頻度が指定した値に一致するような

部分文書集合をウェーブレット木上で動的に構築する．これにより，部分文書集合において計算した N-gram IDF の

誤差がポアソン分布により推測可能となる．評価実験において，提案手法が，特徴語抽出および Web 検索クエリ分割

のアプリケーションにおける性能を維持しつつ，英語版 Wikipedia 全体を 100 倍程度高速に処理できることを示した．

キーワード

N-gram IDF，ウェーブレット木，ポアソン分布

1. はじめに

Inverse Document Frequency（IDF）[9]は，単語の大域的

重みとして最も広く用いられており，実際にTF-IDF [16]や Okapi BM25 [14]など，代表的な重み付け手法の大域的重みとして採用されている．その理由として，IDFの簡潔さと頑健性が挙げられる．IDFは，対象の単語が出現する文書の数（文書頻度）を算出するだけで重みが求まるという簡潔さにも関わらず，様々な文献[2], [10], [12], [13]において頑健性が示されている．一方で，IDFは複合語あるいは単語N-gramに対してうまく機能しないという問題がある．これは，単語N-gramとしては文書頻度が大きいほどその単語の並びが特別な意味を持つ傾向があるのに対し，語の重みは文書頻度が小さいほど大きくなるという，相反する性質によるものである．この問題に対処するため，これまで自己相互情報量（PMI）や名詞句抽出など，単語N-gramを処理するための手法をヒューリスティックに組み合わせる必要があった．筆者らはこの問題に対し，単語N-gramに適用可能な重みと

してN-gram IDFを提案した[17], [18]．N-gram IDFは，コル

モゴロフ複雑性により定義される情報距離に基づく，単語

N-gramに対する理論的な重みである．具体的には，単語N-gram

を構成する単語が全て含まれる文書の数（構成単語の論理積に対する文書頻度）を算出することにより重みが求まる．異なる

長さの単語N-gram間でN-gram IDFの大小関係を比較する

ことにより，テキスト中の重要な語句を検出できる．また，単語N-gramの新たな特徴量として，様々なアプリケーションにおいてN-gram IDFを利用できる．

N-gram IDFは，重みの計算式自体は簡潔であるが，計算量は大きい．これは，複数の単語が全て含まれる文書を列挙する

処理が，論理積の条件を含むクエリ（intersection query，AND

クエリ）に該当するためである．文献[17], [18]では，ウェーブレット木によるアルゴリズム[6]を用いてANDクエリを処理していた．しかしこのアルゴリズムは，理論的な下限[3]に近い計算量でありながら，英語版Wikipediaを文書集合として出現頻度5回以上の全ての単語N-gramの重みを計算するのに（推測値で）1年以上要することが明らかとなった．そのため，近似手法により，N-gram IDFの重みをより高速に計算することが課題であった．本研究では，ウェーブレット木によるアルゴリズムを拡張し， N-gram IDFの重みを近似的に計算する手法を提案する．提案手法の基本的なアイデアは，部分文書集合を用いて文書集合全体における文書頻度を推定するというものである．ここで，単純に部分文書集合を抽出してN-gram IDFを算出した場合，文書集合全体から得られるべき本来の重みとの誤差にばらつきが生じる．本研究ではまず，ポアソン分布に基づく分析により， N-gram IDFの誤差の分布が，部分文書集合の大きさではなく，観測した文書頻度によって決まることを明らかにする．上記の事実に基づき，ウェーブレット木上で，指定した文書頻度がちょうど観測されるような部分文書集合を動的に構築する手法を提案する．提案した近似計算手法が，厳密計算手法と比べて100倍程度高速に英語版Wikipediaを処理できることを示す．また，特徴語抽出やWeb検索クエリ分割のアプリケーションにおいて，性能の低下が発生しないことを実証する．

2. N-gram IDF

N-gram IDF [17], [18]は，コルモゴロフ複雑性により定義される情報距離に基づき，単語の重みとして用いられているIDF を，単語間結合度を表す理論的な距離であるMED [4]と組み合わせて単語N-gramに拡張したものである．単語N-gram gに対するN-gram IDFは以下のように計算される． N IDFd(g) = log |D| df (w1,· · · , wN) (1) N IDFi(g) = log |D| · df(g) df (w1,· · · , wN)2 (2)

(2)

䝔䜻䝇䝖: “to be or not to be to live or to die”

be

or

to

die

live

not

or

not

to

be

or

to

die

live

ฟ⌧఩⨨:

͢ ͦ ͢͡ ͨ ͤ ͣ ͩ ͡ ͥ ͪ ͧ

┤๓䛾༢ㄒ: to to to to or be live

not or

be

図 1 テキスト「to be or not to be to live or to die」に対する拡張接尾辞配列（接尾辞木と同等）の例．式(1)，(2)はそれぞれ直接的および間接的なN-gram IDFの重みとして定義される．なお，|D|は文書集合Dのサイズ（文書数），df (g)はDにおけるgの文書頻度，df (w1,· · · , wN)は Dにおけるgの構成単語w1,· · · , wNの論理積に対する文書頻度である．文献[17], [18]では，式(2)が単語N-gramの長さに依らない公平な重みとして利用できることが示されている．また，式(1)，(2)ともに単語N-gramの特徴量として利用できる．

3. 厳密計算手法

本研究の提案手法は，先行研究[17], [18]で用いられている N-gram IDFの厳密計算手法の拡張であるため，本章では厳密計算手法について詳しく説明する．厳密計算手法では，文書集合Dを入力とし，Dに出現する全ての有効な単語N-gram g についてdf (w1,· · · , wN)（およびdf (g)）を計算する．ここで，有効な単語N-gramを，文書集合における出現頻度（注1）_が_δ_以上の極大部分文字列と定義する．極大部分文字列[11]とは，自身を含み自身より長い単語N-gramの中で出現頻度が一致するものが存在しない単語N-gram（注 2）_{である．文書集合中の有効} な単語N-gramを列挙するため，拡張接尾辞配列[1]を用いる．図1は拡張接尾辞配列の例を表している．拡張接尾辞配列において，子ノード（直後の単語）と直前の単語がそれぞれ複数存在するノードが極大部分文字列となる．図1において，そのようなノードはルートノードを除いて「or」「to」「to be」の三種類である．「be」は直前の単語が全て「to」であるため，極大部分文字列とはならない．極大部分文字列の数は，入力テキストの長さ（単語数）の二倍を超えないことが保証されている．有効な単語N-gramを列挙した後，厳密計算手法の重要な処理である ANDクエリを各単語N-gramに対して実行し， df (w1,· · · , wN)を得る．ANDクエリの実行にはウェーブレット木を利用する．ウェーブレット木[7]は，様々な操作に対して高速に処理可能なデータ構造であり，近年，ANDクエリに対する文書検索に対しても高速に処理できることが示されている[6]．N 個の単語を条件として文書集合Dを検索したとき，計算量はO(N· α · log|D|_α )となり，これは理論的な下限値[3] に近い．なお，αはalternation complexity [6]と呼ばれ，少なくとも文書頻度以上となる．近似計算手法はウェーブレット木を用いたアルゴリズムの拡張であるため，ここでウェーブレット木について詳述する．シ（注1）：文書頻度とは異なることに注意．（注2）：単語を最小単位とした場合，任意の文字列は単語 N-gram となる． ͤͣͤͤͣ͢͢͢͢͡͡ ͢͢͢͢͢͡͡͡͡͡͡ 0 1 ͢͢͢͢͡͡ ͢͢͢͢͡͡ ͤͣͤͤͣ ͢͢͢͡͡ 0 1 0 1 ͡͡ ͢͢͢͢ ͣͣ ͤͤͤ 䝅䞁䝪䝹䝸䝇䝖㻦㻌䛾ୖ఩㻞␒┠䛾䝡䝑䝖䛿䜘䜚図 2 ウェーブレット木の例．アルゴリズム1: Access Input: 位置 i Output: シンボル s = L[i] 1 j = i, s = B1[j], ps= 0, pe= n; 2 for k = 1 to⌈log |S|⌉ − 1 do 3 pb= ps+ rank0(Bk, pe)− rank0(Bk, ps); 4 if Bk[ps+ j] == 0 then 5 j = rank0(Bk, ps+ j)− rank0(Bk, ps); 6 pe= p_b; 7 else 8 j = rank1(Bk, ps+ j) - rank1(Bk, ps); 9 ps= pb; 10 end 11 s = s << 1; 12 s = s + Bk+1[ps+ j]; 13 end ンボルs ∈ S = {0, 1, 2, · · · , |S| − 1}のリストL[0, n− 1]を考える．ウェーブレット木は，Lを⌈log |S|⌉個のビットのリストBk[0, n− 1]（k = 1,· · · , ⌈log |S|⌉）として表現する．B1 はLの上位1番目のビットを格納する．B2はLの上位2番目のビットを格納するが，その順番は上位1番目のビットによりソートされる．すなわち，上位1番目のビットが0のシンボル， 1のシンボルがそれぞセグメントとして順番に格納される．また，同じセグメント内ではB1における順番が保持される．これにより，下記のO(1)のrank関数を用いて，B1から対応するB2のビットを一意に特定できる． rankb(B, i) =    0 (i = 0) ビットbのB[0, i− 1]中の数 (0 < i <_{= n)} k > 2のBkについても同様に，上位k番目のビットが，Bk−1 の各セグメントにおけるビットによってソートされた後に格納される．結果的にウェーブレット木は，各シンボルの上位k番目のビットにしたがって上位k + 1番目のビットをノード0あるいは1に分類する二分木となる．図2にウェーブレット木の例を示す．図2において，L[8] = 1（ビット表現で01）の上位 2番目のビットは，ビットB1[8] = 0のB1[0, 7]中の数が5であるため，B2[5] = 1であるとわかる．アルゴリズム1は位置iに対応するシンボルL[i]をウェーブレット木B1,· · · , B_{⌈log |S|⌉}上で参照する関数である．深さkの各ノード（セグメント）は，Bk中の開始位置psと終了位置pe，すなわちBk[ps, pe− 1]によって表現される．このとき，深さ

(3)

ᩥ᭩㞟ྜ㻦

“to be”, “or not to be”, “to live”, “or to die”

༢ㄒ䝸䝇䝖: “to be or not to be to live or to die” ᥋ᑿ㎡㓄ิ: ᩥ᭩䝸䝇䝖: ͤͣͤͤͣ͢͢͢͢͡͡ ͢͢͢͢͢͡͡͡͡͡͡ 0 1 ͢͢͢͢͡͡ ͢͢͢͢͡͡ ͤͣͤͤͣ ͢͢͢͡͡ 0 1 0 1 ͡͡ ͢͢͢͢ ͣͣ ͤͤͤ 図 3 文書リストに対するウェーブレット木の例． k + 1の子ノード0および1は，境界位置pb（ps<_{= p}b<_{= p}e）によって分けられる．具体的には，子ノード0はBk+1[ps, pb−1]，子ノード1はBk+1[pb, pe− 1]となる．各子ノードの長さはそれぞれBk[ps, pe− 1]中のビット0および1の数に一致する．アルゴリズム1は，Bk中のセグメント中の位置j（初期位置 i），ps（初期位置0），pe（初期位置n）をそれぞれrank関数を用いて変更しながら，ウェーブレット木をB1からB⌈log |S|⌉ まで順にたどっていく．次のjは，Bk[ps+ j]が0（あるいは 1）のとき，Bk[ps, j− 1]におけるビット0（あるいは1）の数を計算することで得られる．また，Bk[ps+ j]が0のときは次の終了位置をpbに，1のときは次の開始位置をpbに設定する．最終的に，各kにおいて対応するビットBk[ps+ j]をつなげたビット列がL[i]となる．ウェーブレット木を用いた文書頻度の算出[6]は，アルゴリズム1を拡張することで実現できる．文書集合Dを単語のリストLW[0, n− 1]として表現する．LW から拡張接尾辞配列を構築することにより，有効な単語N-gramの集合Gvが得られる．また，この処理の過程で，LW を接尾辞によりソートした接尾辞配列LSA[0, n− 1]が生成される．その後，単語

LW[LSA[i]]の出現する文書がLD[i]となるような文書リスト

LD[0, n− 1]を作成する．LSA[i]はソートされているため，任意の単語N-gram gv∈ Gvが出現する文書をLD中のセグメントとして表現できる．そして，LDに対してウェーブレット木を構築する．図3は文書リストに対するウェーブレット木の例を表している．LW は図1と同じであるため，LSAは図1の出現位置の順番に一致する．また，LDは図2のシンボルリストと同一であるため，構築されたウェーブレット木は図2と等しくなる．ここで，単語N-gram gv ∈ Gvを含む文書集合は LD中の連続した区間として表されるため，図4のように単語 N-gramあるいは単語を表す区間の開始位置と終了位置についてウェーブレット木をたどることで文書頻度を算出できる．このとき，ANDクエリ（図4右）であっても，全ての開始位置と終了位置の組について同時にウェーブレット木をたどり，到達できた葉ノードの数をみることで文書頻度が得られる．アルゴリズム2はウェーブレット木上で文書頻度を算出する再帰関数である．初期の引数は単語N-gramを構成するm個の単語であり，それぞれ開始位置is[j]，終了位置ie[j]，出現回数o[j]の三つ組に変換される．なお，通常o[j] = 1であるが， ͤͣͤͤͣ͢͢͢͢͡͡ ͢͢͢͢͢͡͡͡͡͡͡ 0 1 ͢͢͢͢͡͡ ͢͢͢͢͡͡ ͤͣͤͤͣ ͢͢͢͡͡ 0 1 0 1 ͡͡ ͢͢͢͢ ͣͣ ͤͤͤ “be” “to” ͤͣͤͤͣ͢͢͢͢͡͡ ͢͢͢͢͢͡͡͡͡͡͡ 0 1 ͢͢͢͢͡͡ ͢͢͢͢͡͡ ͤͣͤͤͣ ͢͢͢͡͡ 0 1 0 1 ͡͡ ͢͢͢͢ ͣͣ ͤͤͤ “to be” 䜽䜶䝸㻦 “to be” 㐺ྜᩥ᭩㻦㻌͑͢͡͝ 䜽䜶䝸㻦㻌“to” “be” 㐺ྜᩥ᭩㻦㻌͑͢͡͝ 図 4 図 3 のウェーブレット木における文書頻度の算出の例．左の図は単語 2-gram「to be」，右の図は二単語「to」「be」の例である．アルゴリズム2: CountDF Input: 単語の開始位置 is[0, m− 1], 単語の終了位置 ie[0, m− 1], 単語の出現回数 o[0, m − 1], 深さ k = 1, 開 始位置 ps= 0, 終了位置 pe= n Output: 文書頻度 df 1 if k >⌈log |D|⌉ then // 葉ノードに到達 2 return 1; 3 end 4 df = 0, f0= true, f1= true; 5 p_b= ps+ rank0(Bk, pe)− rank0(Bk, ps);

6 init is0[0, m− 1], ie0[0, m− 1], is1[0, m− 1], ie1[0, m− 1]; 7 for j = 0 to m− 1 do

8 is0[j] = rank0(Bk, ps+ is[j])− rank0(Bk, ps);

9 ie0[j] = rank0(Bk, ps+ ie[j])− rank0(Bk, ps);

12 if ie0[j]− is0[j] < o[j] then 13 f0 = false;

14 end

17 end 18 end

19 if f0then // 子ノード 0 を探索

20 df = CountDF (is0, ie0, o, ps, p_b, k + 1); 21 end

23 df = df + CountDF (is1, ie1, o, pb, pe, k + 1); 24 end 同じ単語が一つの単語N-gramの中に複数回出現する場合のみ 2以上となる．また，深さk，セグメントの開始位置psおよび終了位置peはそれぞれ1，0，n（すなわちB1[0, n− 1]）として初期化される．j + 1番目の単語について，深さk + 1の子ノード0における開始位置is0[j]と終了位置ie0[j]，子ノード1

における開始位置is1[j]と終了位置ie1[j]をそれぞれrank関

数によって計算する．このとき，子ノードにおける長さ（開始位置と終了位置の差）がo[j]より小さい場合，その子ノードでの単語の出現回数は必ずo[j]未満となるため，これ以上子ノードをたどる必要がない．アルゴリズム2は再帰的に子ノードをたどり，葉ノードに到達した回数を数えることで，文書頻度を算出する．

(4)

4. 近似計算手法

3.章で説明した厳密計算手法は，下限[3]に近い計算量を達成しているが，依然としてサイズの大きいコーパス（英語版 Wikipediaなど）に対しては現実的な処理時間を達成できないという問題がある．これは，多くの単語N-gramについて，構成単語の論理積に対する文書頻度df (w1,· · · , wN)が|D|に近くなるためである．このとき，α（alternation complexity）は_|D| として近似できるため，厳密計算手法の計算量O(N·α·log|D|_α ) はO(N· |D|)となる．これは単一の単語N-gramの重みを計算するときの計算量であり，有効な単語N-gramの数がO(|D|) であることを考慮すると，全体の計算量はコーパスサイズ_|D| に対してO(|D|2)で増加する．本研究では計算量を削減するため，近似計算手法を提案する．提案手法は，コーパスサイズ|D|に対してO(|D| · log |D|)程度の計算量を達成しつつ，N-gram IDFの誤差分布を一つのパラメータにより制御可能とする．これにより，厳密値を用いた場合と比べてアプリケーションにおける性能を低下させない程度の誤差を許容するよう手法を調整できる．以下ではまず，ポアソン分布による誤差の分析を行い，その後，ウェーブレット木を用いた近似計算手法について説明する． 4. 1 ポアソン分布による誤差の分析提案手法のアプローチは，部分文書集合を用いて文書集合全体における文書頻度を推定するというものである．本節ではまず，部分文書集合で観測した文書頻度と，文書集合全体における文書頻度の関係性を明らかにする．無作為に抽出された部分文書集合Ds⊂ Dが与えられたとき，Dsにおける単語N-gram gの文書頻度の期待値⟨dfs(g)⟩は以下のとおりである． ⟨dfs(g)⟩ = |Ds| |D| · df(g) 一方，文書集合Dsで文書頻度dfs(g)を観測したとき, Dにおける文書頻度の期待値⟨df(g)⟩は ⟨df(g)⟩ = |_|Ds|D| · dfs(g) となるため，dfs(g)から推測されるIDF値は以下のようになる． ⟨IDF (g)⟩ = log |D| ⟨df(g)⟩= log |Ds| dfs(g) (3) 本節における問題は，推測された重み_{⟨IDF (g)⟩}が実際の重みIDF (g)とどの程度異なるかを分析することである．本研究では，ポアソン分布を用いてこの問題を解決する．ポアソン分布[8]は，一定の時間あるいは空間内（単位間隔）である事象が発生する回数の確率を表す離散確率分布である．単位間隔での平均発生回数が既知で，かつ各事象が独立である場合，その事象はポアソン分布に従う．ポアソン分布のパラメータλは，単位間隔での平均発生回数であり，同時に分散でもある．パラメータλのポアソン分布に従う確率変数X（x = 0, 1, 2,· · ·）は，以下の式を満たす． Pλ(X = x) =λ x e−λ x! 表 1 ポアソン分布のパラメータ（平均値）に対する信頼区間． k 95%信頼区間 99%信頼区間下限値上限値下限値上限値 1 0.03 5.57 0.01 7.43 5 1.62 11.67 1.08 14.15 10 4.80 18.39 3.72 21.40 20 12.22 30.89 10.35 34.67 50 37.11 65.92 33.66 71.27 100 81.36 121.63 76.12 128.76 なお，数値安定性のため，一般にガンマ関数の自然対数log Γ を用いて以下のように計算される．

Pλ(X = x) = exp(x log λ− λ − log Γ(x + 1))

部分文書集合Dsで観測される文書頻度dfs(g)は，Dsの抽出が無作為であるとき，λs=⟨dfs(g)⟩のパラメータを持つポアソン分布に従う．このとき，dfs(g)と_⟨dfs(g)⟩の誤差の分布はポアソン分布の信頼区間を用いて推定できる．表1にポアソン分布の信頼区間の一例を示す[20]．単位間隔において事象をk 回観測したとき，ポアソン分布のパラメータλは，指定した信頼水準（表1では95%または99%）で下限値と上限値の間にある．たとえば，部分文書集合Dsにおいて文書頻度dfs(g) = 20 を観測したとき，パラメータλsが10.35から34.67の間である確率が99%となる． IDFの誤差は，文書頻度の期待値と観測した文書頻度との差によって決まる．λ(L)s とλ(U )s をそれぞれ文書頻度dfsを観測したときのλsの下限値および上限値とする．このとき，単語

N-gram gのIDFの下限値IDF(L)(g)と上限値IDF(U )(g)はそれぞれ以下のようになる． IDF(L)(g) = log|Ds| λ(U )s (4) IDF(U )(g) = log|Ds| λ(L)s (5) 式(3)，(4)，(5)より，IDFの誤差の下限値および上限値は以下のように計算できる． ⟨IDF (g)⟩ − IDF(U ) (g) = log |Ds| dfs(g)− log | Ds| λ(L)s = log λ (L) s dfs(g) ⟨IDF (g)⟩ − IDF(L) (g) = log |Ds| dfs(g)− log | Ds| λ(U )s = log λ (U ) s dfs(g) λ(L)s とλ (U ) s は観測した文書頻度dfs(g)によって決まるため，結果的にIDFの誤差はdfs(g)のみに影響を受ける．すなわち，部分文書集合の大きさ|Ds|はIDFの誤差に影響しない．上記の誤差は N IDFd(g) についても同様にいえる． N IDFi(g)の場合，誤差は2倍になる．df (g)が既知であるとして，期待値_⟨NIDFi(g)⟩は以下のように計算される． ⟨NIDFi(g)⟩ = log |D| · df(g) ⟨df(w1,· · · , wN)⟩2 = log₍ |D| · df(g) |D| |Ds|· dfs(w1,· · · , wN) )2 = log |Ds| 2_{· df(g)} |D| · dfs(w1,· · · , wN)2

(5)

なお，dfs(w1,· · · , wN)は部分文書集合DsにおけるN-gram gの構成単語w1,· · · , wNの論理積に対する文書頻度である． ⟨dfs(w1,· · · , wN)⟩をDsにおける文書頻度の期待値とすると， dfs(w1,· · · , wN)はλs = ⟨dfs(w1,· · · , wN)⟩のパラメータを持つポアソン分布のサンプルとみなせる．λ(L)s およびλ(U )s を， dfs(w1,· · · , wN)を観測したときのλsの下限値および上限値とすると，N IDFi(g)の下限値および上限値は以下のようになる． N IDFi(L)(g) = log |Ds|2_{· df(g)} |D| ·(λ(U )s )2 N IDF_i(U )(g) = log|Ds| 2_{· df(g)} |D| ·(λ(L)s )2 最終的に，N IDFi(g)の誤差の下限値と上限値は以下のように計算される．

⟨NIDFi(g)⟩ − NIDF_i(U )(g) = log ( λ(L)s )2 dfs(w1,· · · , wN)2 = 2 log λ (L) s dfs(w1,· · · , wN) ⟨NIDFi(g)⟩ − NIDFi(L)(g) = log

( λ(U )s )2 dfs(w1,· · · , wN)2 = 2 log λ (U ) s dfs(w1,· · · , wN) したがって，部分文書集合において観測した文書頻度が同じで

ある場合，N IDFi(g)はIDF (g)やN IDFd(g)と比較して誤

差が2倍になる． 4. 2 ウェーブレット木を用いた近似計算手法部分文書集合を用いた近似計算手法として，部分文書集合に対して構築されたウェーブレット木において文書頻度を計算する方法が考えられる．しかし，前節より，部分文書集合から計算したN-gram IDFの誤差の分布は部分文書集合において観測した文書頻度によって決まるため，単語N-gramごとの重みの誤差を予測できないという問題がある．また，部分文書集合における文書頻度が0となる場合も少なくない．全ての有効な単

語N-gramについてN-gram IDFの誤差を制御するためには，

観測される文書頻度が一定となるように単語N-gramごとに調整された部分文書集合を構築する必要がある．そこで，単語N-gramごとに指定した数の文書頻度が得られるような部分文書集合をウェーブレット木上で動的に構築する手法を提案する．提案手法の重要なアイデアは，アルゴリズム 2の再帰呼び出しを規定の文書頻度dfpが観測された段階で止めるというものである．これを実現するため，ウェーブレット木における文書頻度の計算において，非文書頻度dfs（対象の語を含まない文書の数）を導入し，サイズが|Ds| = dfs+ dfs となるように部分文書集合Ds={0, 1, 2, · · · , |Ds| − 1}を構築していく．計算量は，O(N· α · log|D|_α )におけるαがdfpに近くなるため，全体としてO(|D|2 )からO(|D| · dfp· log|D| dfp)程度に削減できる．dfpは自由に指定できるため，誤差の大きさと処理速度のトレードオフを調整できる．提案手法の再帰関数をアルゴリズム3に示す．アルゴリズム 3はアルゴリズム2を修正したものである．アルゴリズム2にアルゴリズム3: CountSubsetDF Input: 単語の開始位置 is[0, m− 1], 単語の終了位置 ie[0, m− 1], 単語の出現回数 o[0, m − 1], 規定の文書頻度 dfp, 観測した文書頻度 dfo = 0, 深さ k = 1, 開始位置 ps = 0, 終了位置 pe = n Output: 文書頻度 dfs, 非文書頻度 dfs 1 if k >⌈log |D|⌉ then // 葉ノードに到達 2 return 1; 3 end 4 dfs= 0, dfs= 0, f0 = true, f1= true; 5 pb= ps+ rank0(Bk, pe)− rank0(Bk, ps);

6 init is0[0, m− 1], ie0[0, m− 1], is1[0, m− 1], ie1[0, m− 1]; 7 for j = 0 to m− 1 do

8 is0[j] = rank0(Bk, ps+ is[j])− rank0(Bk, ps); 9 ie0[j] = rank0(Bk, ps+ ie[j])− rank0(Bk, ps);

14 end

17 end

18 end

20 (dfs, dfs) =

CountSubsetDF (is0, ie0, o, dfp, dfo, ps, pb, k + 1); 21 else // 子ノード 0 の非文書頻度を計算 22 if dfo== dfpthen 23 dfs= 2⌈log |D|⌉−k−1; 24 else 25 dfs= 2⌈log |D|⌉−k; 26 end 27 end 28 if dfo+ dfs<= dfpthen 29 if f1 then // 子ノード 1 を探索 30 (dfs, dfs) = (dfs, dfs) +

CountSubsetDF (is1, ie1, o, dfp, dfo+ dfs, pb, pe, k + 1); 31 else // 子ノード 1 の非文書頻度を計算 32 if dfo+ dfs == dfpthen 33 dfs= dfs+ 2⌈log |D|⌉−k−1; 34 else 35 dfs= dfs+ 2⌈log |D|⌉−k; 36 end 37 end 38 end 39 if k == 1 then 40 if dfs<= dfpthen 41 dfs=|D| − dfs; 42 else 43 dfs= dfs− 1; 44 end 45 end

(6)

加えて，初期の引数に規定の文書頻度dfpを要する．また，各時点で観測した文書頻度dfoを引数として渡すことで，いつ再帰を止めるか，すなわち，dfpがすでに観測されたかどうかを判断する．出力は，文書頻度dfsと非文書頻度dfsの二種類であり，部分文書集合を意味する．アルゴリズム2との大きな違いは，子ノード0あるいは1をこれ以上探索する必要がないとわかった場合（f0あるいはf1 がfalseである場合），その子ノード以下の非文書頻度dfsを計算する点である．ウェーブレット木が高さ_{⌈log |D|⌉ + 1}の完全二分木であるとすると，深さk + 1以下にある文書の数は2⌈log |D|⌉−kとなるため，子ノードを探索することなく非文書頻度を計算できる．しかし実際には，文書数がちょうど2のべき乗でない限りはウェーブレット木は完全二分木とはならない．そのため，子ノード以下が完全二分木となっていない場合について考慮する必要がある．ここで，文書集合をインクリメンタルな整数，すなわち D ={0, 1, 2, · · · , |D| − 1}として考える．ウェーブレット木は，上位k番目のビットに基づいて整数を深さk + 1の0あるいは1のノードに割り振るため，深さ_{⌈log |D|⌉ + 1}に位置する葉ノードは，左から右の順に作成される．結果として得られるウェーブレット木は，各深さの最も右にあるノード以外は完全二分木となることが保証される．また，ウェーブレット木を左から順番に探索していくと，最も右にあるノードを探索するときには全てのノードをチェックしていることになるため，この場合は最後にdfsを|D| − dfsとして再設定することで正しい値になる．なお，これは全体の文書集合Dにおける文書頻度がdfp以下である場合にのみ起こる．アルゴリズム3は現時点までに観測した文書頻度dfo（とノード0において追加で観測した文書頻度dfsの和）がdfpを超えたときに再帰を止める．言い換えれば，dfo+ dfs= dfpのときは再帰を続ける．これは，部分文書集合のサイズ|Ds|を正規化するためである．dfo+ dfsがdfpに到達した時点ですぐに再帰を終了した場合，ちょうどdfpを観測するような部分文書集合としては_|Ds|が最も小さくなる．提案手法では，dfo+ dfs がdfpを超えるまで再帰を継続し，ちょうどdfpを観測するような部分文書集合のサイズの平均を|Ds|として採用する．具体的には，dfo+ dfs= dfpのとき，dfsを1₂ として加えることでこれを実現する．dfo+ dfsがdfpを超えた場合に再帰を終了し，最後にdfsから1減算する（dfs= dfpとなる）．アルゴリズム3は，部分文書集合Ds={0, 1, 2, · · · , |Ds|−1} で観測した文書頻度がポアソン分布に従うように，文書集合 Dの文書の順番がランダムであることを想定している．s しかし実際には，作成日時などの基準に基づいて文書が整列されていることが多い．そこで提案手法は，ランダム置換リスト LR[0,|D| − 1]を用いて事前に文書集合の順番をランダムに入れ替える．具体的には，文書番号i（0 <_{= i < |D|}）に対して LR[i]（0 <_{= L}R[i] <|D|）がユニークかつランダムな番号となるようにする．なお，ランダムな置換はFisher-Yatesシャッフル[5]などのアルゴリズムを用いて線形時間で可能である．そして，文書リストLDにおける文書番号iをLR[i]に置き換えてから，LDに対してウェーブレット木を構築する． Exact Approx5 Approx10 Approx20 Approx50 Approx100 1 10 100 1,000 10,000 100,000 1,000,000 10,000,000 100,000,000 㻿㼡㼎㼟㼑㼠㻝㻛㻝㻜㻜㻜㻿㼡㼎㼟㼑㼠㻝㻛㻝㻜㻜㻿㼡㼎㼟㼑㼠㻝㻛㻝㻜 ඲య ฎ⌮᫬㛫䠄⛊䠅䝁䞊䝟䝇図 5 厳密計算手法と近似計算手法の処理時間の比較．

5. 評価実験

提案手法の処理時間，提案手法を用いて得られたN-gram IDFの近似値の誤差分布，および近似値を用いた場合のアプリケーションにおける性能評価を行った． 5. 1 処理時間厳密計算手法と比較して，提案した近似計算手法がどの程度高速にN-gram IDFを計算できるかを評価した．コーパスとして，2013年10月1日の英語版Wikipediaのダンプデータ（4,379,810記事）を用いた．また，コーパスサイズに対する処理時間の比較を行うため，英語版Wikipedia全体の 1 1000， 1 100， 1 10 の大きさのコーパスを作成した．以降では上記のコーパス

をそれぞれSubset1/1000，Subset1/100，Subset1/10と呼ぶ．

dfpを5，10，20，50，100と変化させ，それぞれについて近

似計算手法の処理時間を計測した．上記のdfpのときの提案

手法をそれぞれApprox5，Approx10，Approx20，Approx50，

Approx100と呼ぶ．また，厳密計算手法をExactとする．図5は各コーパス中の全ての有効な単語N-gram（δ = 5）についてN-gram IDFを計算したときの厳密計算手法および近似計算手法の処理時間を表す．なお，有効な単語N-gramの数はそれぞれ108,261（Subset1/1000），920,378（Subset1/100）， 8,694,915（Subset1/10），87,491,762（全体）であった．厳密計算手法の処理時間は，コーパスサイズ|D|に対しO(|D|2 )で増加していることがわかる．また，厳密計算手法ではWikipedia 全体を処理することができなかった．そのため先行研究[17], [18] では，単語N-gramに含まれる単語の文書頻度に対して文書頻度が 1 2000 に満たないものを省くという足切り処理を行った上で，メモリを60GB以上搭載した計算機（Intel(R) Xeon(R) E5-2643 v2 @ 3.50GHz）を2台用いて12日かけて重みを計算した．その結果，約半数となる39,610,779の有効な単語 N-gramについて重みを得た．計算量がO(|D|2)であることから，厳密計算手法によってWikipedia全体を処理するためには，1 年以上かかることが予測される．提案した近似計算手法についてみると，厳密計算手法と比較して大幅に処理時間を短縮できていることがわかる．特に，コーパスサイズが大きい場合，処理時間は厳密計算手法の 1 100 程度に短縮できている．Approx10（dfp= 10）のとき，上記の計算機1台で，Wikipedia全体に含まれる全ての有効な単語

N-gramについてN-gram IDFを1日以内に計算できた．また，Approx100でも，5日以内に処理を終えることができた．

(7)

0 1,000 2,000 3,000 4,000 5,000 6,000 -4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 ༢ㄒ㻺㻙㼓㼞㼍㼙䛾ᩘ ㄗᕪ Subset1/1000，Approx20 0 2,000 4,000 6,000 8,000 -4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 ༢ㄒ㻺㻙㼓㼞㼍㼙䛾ᩘ ㄗᕪ Subset1/1000，Approx100 0 10,000 20,000 30,000 40,000 50,000 60,000 -4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 ༢ㄒ㻺㻙㼓㼞㼍㼙䛾ᩘ ㄗᕪ Subset1/100，Approx20 0 20,000 40,000 60,000 80,000 100,000 120,000 -4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 ༢ㄒ㻺㻙㼓㼞㼍㼙䛾ᩘ ㄗᕪ Subset1/100，Approx100 0 100,000 200,000 300,000 400,000 500,000 600,000 -4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 ༢ㄒ㻺㻙㼓㼞㼍㼙䛾ᩘ ㄗᕪ Subset1/10，Approx20 0 200,000 400,000 600,000 800,000 1,000,000 1,200,000 -4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 ༢ㄒ㻺㻙㼓㼞㼍㼙䛾ᩘ ㄗᕪ Subset1/10，Approx100 図 6 N-gram IDF の厳密値と近似値の誤差の分布．近似計算手法の計算量はO(|D| · α · log|D|_α )であり，このα は大まかにdfpとして見積ることができる．しかし実際には，図5において，コーパスサイズ|D|に対して見積った計算量よりも少し長い時間がかかっている．その理由の一つとして，小さいコーパスにおいては，より多くの割合の単語N-gramについて，構成単語の論理積に対する文書頻度がdfpよりも小さくなる（すなわちdfs< dfp）ことが挙げられる．たとえば， Sub-set1/1000では72%の単語N-gramがdfs< 100であるのに対し，Wikipedia全体では11%の単語N-gramのみがdfs< 100 となっていた．dfs< dfpのとき，一つの単語N-gramについて重みを計算するときの処理時間がO(N· dfp· log|D|_df p)ではなくO(N· dfs· log|D|_df s)となる．より多くの単語N-gramについてdfs< dfpとなる場合，全体としての処理時間が短縮される．また別の理由として，単語N-gramの平均の長さ（Nの平均）がコーパスサイズに伴って大きくなることが挙げられる．単語 N-gramの平均の長さはそれぞれ1.87（Subset1/1000），2.39 （Subset1/100），2.93（Subset1/10），3.50（全体）であった．

単一の単語N-gramの処理にかかる時間がO(N· dfp· log|D|_df

p) であることから，単語N-gramの平均の長さが全体の処理時間に影響していると考えられる． 5. 2 誤差の分布 5. 1節で計算したN-gram IDFについて，厳密値と近似値の誤差を検証した．図6は厳密値と近似値の誤差をヒストグラムとして表したものである．図6では，Approx20（dfp= 20）お

よびApprox100（dfp= 100）について，Subset1/1000， Sub-set1/100，Subset1/10のそれぞれのコーパスにおける厳密値との誤差を計算している．なお，dfs<_{= df}_pを満たす単語N-gram は，近似計算手法においても厳密値が得られるため，ヒストグラムから除外した．図6より，誤差の分布がdfpのみによって決まっていることがわかる．これは4. 1節における分析と一致する．また，Approx20の誤差は，表1を用いると，99%の確率で2 log10.35 20 ≈ −1.90から2 log 34.67 20 ≈ 1.58までの間となり，図6と一致する．Approx100の場合，それらの誤差は表 2 特徴語抽出における性能評価．手法 R-Prec Approx5 ••0.358 Approx10 ••0.367 Approx20 ••0.376 Approx50 0.382 Approx100 0.384 Exact 0.386 「••」は両側 t 検定において有意水準 99%で Exact より性能が低いことを表す． 2 log76.12 100 ≈ −0.79，2 log 128.76 100 ≈ 0.73と大幅に小さくなる．以上の結果より，提案手法による誤差が制御可能であることを，実際のデータを用いて実証できた． 5. 3 アプリケーションにおける性能評価 N-gram IDFの近似値がどの程度の誤差であればアプリケーションにおける性能が低下しないのかを検証する．先行研究[17], [18]と同様に，特徴語抽出およびWeb検索クエリ分割のアプリケーションにおいて評価を行った． 5. 3. 1 特徴語抽出特徴語抽出では，英語版Wikipediaを用いて実験を行った． Wikipediaでは，各ページにおける特徴的な語がアンカーテキストとして別のWikipediaのページにリンクされているため，これを正解データとして利用した．Wikipediaから選んだランダムな1,678記事の第一段落をテストセットとし，テキストに含まれるアンカーテキストおよび太字の語（主に記事のタイトルが太字で表記される）を正解の特徴語とした．第一段落のみをテキストとして利用することで，多くの語の出現頻度が1となる状況が発生するため[19]，大域的重みであるN-gram IDF をより直接的に評価できる．第一段落から作成したデータセットは，平均して60.2の単語（最大291，最小8），6.7の特徴語（最大30，最小3）を含む．それぞれの手法を用いて特徴語のランク付きリストを生成した後，各記事の正解数Rに対して上位Rの出力の適合率であるR-Precを計測した．表2は特徴語抽出タスクにおける評価結果である（注 3）_． dfp が50あるいは100のとき，厳密値を用いた場合とほぼ同等の性能を近似値を用いて達成できている．また，厳密計算手法において足切りされた単語N-gramのうち，近似計算手法によってうまく抽出できたものも存在していた．たとえば，「anglo

american playing cards」という特徴語は，それ自体の出現回

数が，全ての構成単語の出現回数に対して 1

2000未満であった

ため，厳密計算手法では足切りされていた．近似計算手法では

全ての有効な単語N-gramについてN-gram IDFを計算可能

であるため，上記の特徴語を抽出できていた．一方で，dfpが小さい場合（20以下），R-Precは有意に低下していた．以上より，特徴語抽出においては，dfpをある程度大きく（50以上）することで，計算量を削減しつつ性能を維持できる． 5. 3. 2 Web検索クエリ分割 Web検索クエリ分割では，Royらの情報検索ベースのデータセット[15]を用いた．このデータセットは13,959のWeb （注3）：文献 [17], [18] と数値が異なるが，これは括弧などの特定の記号を除去する処理を導入したためである．

(8)

表 3 Web 検索クエリ分割における性能評価．手法 nDCG nDCG MAP MAP MRR MRR @5 @10 @5 @10 @5 @10 Approx5 •0.725 •0.739 0.899 0.892 0.580 0.590 Approx10 0.728 0.741 0.899 0.892 0.577 0.587 Approx20 0.730 0.742 0.901 0.894 0.583 0.592 Approx50 0.730 0.743 0.900 0.893 0.587 0.596 Approx100 0.729 0.741 0.899 0.893 0.580 0.589 Exact 0.730 0.742 0.900 0.893 0.582 0.593 「•」は両側 t 検定において有意水準 95%で Exact より性能が低いことを表す． ページ，500のクエリ，クエリに対するWebページの関連性のスコア（Qrel）を含む．Qrelは3人の被験者が3段階（2：強く関連がある，1：関連がある，0：関連がない）でクエリ中の全単語を含むWebページを評価したものである．情報検索ベースのクエリ分割では，与えられたクエリ（例：「larry

the lawnmower tv show」）に対し，クエリを語句に分割（例：「larry the lawnmower」「tv show」）し，それらの語句が出現

するWebページのみを出力に含める（すなわちWeb検索における引用符を利用する）ことによって情報検索の性能がどの程度向上するかを測定する．なお，クエリに対する文書の関連度はTF-IDFを用いて測る．分割された語句のうち，どの語句に引用符を付けるかを決めるのは難しい問題であるため，Roy ら[15]はその中で最適な組合せをとった場合のスコアを測定している．本研究では，Royらの評価方法に従う．評価尺度も Royらと同様に，nDCG，MAP，MRRを上位5および10の

Webページに対して測定した．MAPとMRRはQrelを二値

（関連がある，関連がない）に変換する必要があるため，MAP では2と1を，MRRでは2のみを関連があるとみなした．表3はWeb検索クエリ分割タスクにおける評価結果である． dfp= 5の場合を除いて，厳密値を用いた場合と同等の性能を近似値を用いて達成できている．特筆すべき点として，特徴語抽出タスクと比べて，小さいdfpで十分な性能を達成できた点が挙げられる．これは，クエリ分割タスクにおいては，特徴語として一つの意味を表現するユニットを完全に抽出する必要がないためである．クエリ分割タスクでは，特徴語の一部あるいは特徴語を含む長い単語N-gramであっても，検索結果を絞り込むのに有効な単語N-gramであればよい．また，別の理由として，Web検索クエリは複数の不連続な語句によって成り立っていることが挙げられる．自然文からの特徴語抽出とは異なり，語句の切れ目がより明確であることが多いため，抽出すべき単語N-gramの候補を絞り込みやすい．上記の理由から，dfpが小さい場合，すなわち，近似値の誤差が大きい場合でも，クエリ分割において性能を維持できたと考えられる．

6. おわりに

本研究では，単語N-gramの大域的重みであるN-gram IDF

の近似計算手法を提案した．提案手法は，部分文書集合を用いて重みを近似的に算出するというアイデアに基づき，ウェーブレット木において指定した文書頻度をちょうど観測するような部分文書集合を動的に構築する．これは，部分文書集合から得られたN-gram IDFの誤差は，部分文書集合のサイズではなく，部分文書集合で観測した文書頻度によって決まるためである．評価実験により，提案手法が厳密計算手法よりも100倍程度高速に英語版Wikipedia全体を処理できることを示した．また，提案手法によるN-gram IDFの近似値を用いても特徴語抽出やWeb検索クエリ分割の性能が低下しないことを実証した．今後の課題として，さらなる高速化のため，単語N-gramの足切り手法の考案が挙げられる．本研究では，出現回数が閾

値以上の全ての単語N-gramを候補としてN-gram IDFを計

算したが，実際には多くの単語N-gramは重複する他の単語 N-gramに完全に被覆され，最終的なアプリケーションの性能に寄与しない．そのため，不要な単語N-gramを正確に足切りする手法を用いることで，アプリケーションの性能を維持しつつ，処理時間をさらに短縮できると考えられる．

謝

辞

本研究の一部は，文部科学省科学研究費補助金・基盤研究 (A)(26240013)，JST国際科学技術共同研究推進事業（戦略的国際共同研究プログラム），文部科学省国家課題対応型研究開発推進事業−次世代IT基盤構築のための研究開発−「社会システム・サービスの最適化のためのIT統合システムの構築」の研究助成によるものである．ここに記して謝意を表す．文献

[1] M. I. Abouelhoda, S. Kurtz, and E. Ohlebusch. Replacing Suﬃx Trees with Enhanced Suﬃx Arrays. Journal of Discrete Algorithms, 2(1):53–86, 2004.

[2] A. Aizawa. An Information-Theoretic Perspective of TF-IDF Mea-sures. Information Processing and Management, 39(1):45–65, 2003. [3] J. Barbay and C. Kenyon. Adaptive Intersection and t-Threshold

Problems. In SODA, pages 390–399, 2002.

[4] F. Bu, X. Zhu, and M. Li. Measuring the Non-compositionality of Multiword Expressions. In COLING, pages 116–124, 2010. [5] R. Durstenfeld. Algorithm 235: Random Permutation.

Communica-tions of the ACM, 7(7):420, 1964.

[6] T. Gagie, G. Navarro, and S. J. Puglisi. New Algorithms on Wavelet Trees and Applications to Information Retrieval. Theoretical Com-puter Science, 426–427:25–41, 2012.

[7] R. Grossi, A. Gupta, and J. S. Vitter. High-Order Entropy-Compressed Text Indexes. In SODA, pages 841–850, 2003. [8] F. A. Haight. Handbook of the Poisson Distribution. Wiley, New York,

1967.

[9] K. S. Jones. A Statistical Interpretation of Term Specificity and its Application in Retrieval. Journal of Documentation, 28:11–21, 1972. [10] D. Metzler. Generalized Inverse Document Frequency. In CIKM,

pages 399–408, 2008.

[11] D. Okanohara and J. Tsujii. Text Categorization with All Substring Features. In SDM, pages 838–846, 2009.

[12] K. Papineni. Why Inverse Document Frequency? In NAACL, pages 1–8, 2001.

[13] S. Robertson. Understanding Inverse Document Frequency: On theo-retical arguments for IDF. Journal of Documentation, 60(5):503–520, 2004.

[14] S. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, and M. Gat-ford. Okapi at TREC-3. In TREC, pages 109–126, 1994.

[15] R. S. Roy, N. Ganguly, M. Choudhury, and S. Laxman. An IR-based Evaluation Framework for Web Search Query Segmentation. In SI-GIR, pages 881–890, 2012.

[16] G. Salton, A. Wong, and C.-S. Yang. A Vector Space Model for Automatic Indexing. Communications of the ACM, 18(11):613–620, 1975.

[17] 白川真澄, 原隆浩, 西尾章治郎. コルモゴロフ複雑性に基づく IDF の単語 N-gram への適用. 第 7 回データ工学と情報マネジメントに関するフォーラム, 2015. [18] M. Shirakawa, T. Hara, and S. Nishio. N-gram IDF: A Global Term

Weighting Scheme Based on Information Distance. In WWW, pages 960–970, 2015.

[19] M. Timonen. Term Weighting in Short Documents for Document Cat-egorization, Keyword Extraction and Query Expansion. PhD thesis, University of Helsinki, 2013.

[20] G. van Belle, L. D. Fisher, P. J. Heagerty, and T. Lumley. Biostatis-tics: A Methodology For the Health Sciences. Wiley, New York, 2nd edition, 2004.

ウェーブレット木を用いたN-gram IDFの近似計算手法

DEIM Forum 2016 A1-1