BD勉強会 Modern Information Retrieval Chapter 3 3.3（勉強会後修正済み） 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 目次 3.3.1 Set-Based Model 3.3.2 Extended Boolean Model 3.3.3 Fuzzy Set Model 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 目次 3.3.1 Set-Based Model 3.3.2 Extended Boolean Model 3.3.3 Fuzzy Set Model 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 Set-Based Model 単語を使う代わりに文書中にでてくる単語のセットを処理の単位としてみる方法 定義：ある単語セット 𝑆 𝑖 ={ 𝑘 𝑎 , 𝑘 𝑏 ,⋯, 𝑘 𝑛 }は文書コレクション中の単語セットだとする。 𝑆 𝑖 が文書 𝑑 𝑗 中に現れるとき、「単語セット 𝑆 𝑖 が文書 𝑑 𝑗 に現れる(termset 𝑆 𝑖 occurs in 𝑑 𝑗 )」と呼ぶ。また、 𝑁 𝑖 を 𝑆 𝑖 が出現する文書の数とする。 定義：文書コレクション中の全単語数がtのとき、ありえるすべての単語セットの組 𝑉 𝑆 ={ 𝑆 1 , 𝑆 2 ,⋯, 𝑆 2 𝑡 }を文書コレクションの語彙セットとする 定義：n単語の単語セットをn単語セット(n-termset)と呼ぶ。ある単語セット 𝑆 𝑖 の出現する文書の数 𝑁 𝑖 が与えられた閾値より高いとき「 𝑆 𝑖 が頻出する」と呼ぶ。 ※n単語セットが頻出する時、n-1単語セットも頻出することが多い。 例は次ページ 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 Set-Based Model a b c a d a d c a b a d e f a g d h i g h g j k g h b d b d b b b b l l l m n d m n d コレクション中の全単語 𝑎= 𝑘 𝑎 to 𝑏= 𝑘 𝑏 do 𝑐= 𝑘 𝑐 is 𝑑= 𝑘 𝑑 be 𝑒= 𝑘 𝑒 or 𝑓= 𝑘 𝑓 not 𝑔= 𝑘 𝑔 I ℎ= 𝑘 ℎ am 𝑖= 𝑘 𝑖 what j= 𝑘 𝑗 think 𝑘= 𝑘 𝑘 therefore 𝑙= 𝑘 𝑙 da 𝑚= 𝑘 𝑚 let 𝑛= 𝑘 𝑛 it 文書𝑑 1 文書𝑑 2 文書𝑑 3 文書𝑑 4 語彙セット(クエリ𝑞={𝑎,𝑑,𝑛}に限定して表示) Termset Set of Terms Documents 𝑆 𝑎 {𝑎} 𝑆 𝑑 {𝑑} 𝑆 𝑛 {𝑛} 𝑆 𝑎𝑑 {𝑎,𝑑} 𝑆 𝑎𝑛 {𝑎,𝑛} 𝑆 𝑑𝑛 {𝑑,𝑛} 𝑆 𝑎𝑑𝑛 {𝑎,𝑏,𝑑} 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 Set-Based Model a b c a d a d c a b a d e f a g d h i g h g j k g h b d b d b b b b l l l m n d m n d コレクション中の全単語 𝑎= 𝑘 𝑎 to 𝑏= 𝑘 𝑏 do 𝑐= 𝑘 𝑐 is 𝑑= 𝑘 𝑑 be 𝑒= 𝑘 𝑒 or 𝑓= 𝑘 𝑓 not 𝑔= 𝑘 𝑔 I ℎ= 𝑘 ℎ am 𝑖= 𝑘 𝑖 what j= 𝑘 𝑗 think 𝑘= 𝑘 𝑘 therefore 𝑙= 𝑘 𝑙 da 𝑚= 𝑘 𝑚 let 𝑛= 𝑘 𝑛 it 文書𝑑 1 文書𝑑 2 文書𝑑 3 文書𝑑 4 語彙セット(クエリ𝑞={𝑎,𝑑,𝑛}に限定して表示) Termset Set of Terms Documents 𝑆 𝑎 {𝑎} { 𝑑 1 , 𝑑 2 } 𝑆 𝑑 {𝑑} 𝑆 𝑛 {𝑛} 𝑆 𝑎𝑑 {𝑎,𝑑} 𝑆 𝑎𝑛 {𝑎,𝑛} 𝑆 𝑑𝑛 {𝑑,𝑛} 𝑆 𝑎𝑑𝑛 {𝑎,𝑏,𝑑} 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 Set-Based Model a b c a d a d c a b a d e f a g d h i g h g j k g h b d b d b b b b l l l m n d m n d コレクション中の全単語 𝑎= 𝑘 𝑎 to 𝑏= 𝑘 𝑏 do 𝑐= 𝑘 𝑐 is 𝑑= 𝑘 𝑑 be 𝑒= 𝑘 𝑒 or 𝑓= 𝑘 𝑓 not 𝑔= 𝑘 𝑔 I ℎ= 𝑘 ℎ am 𝑖= 𝑘 𝑖 what j= 𝑘 𝑗 think 𝑘= 𝑘 𝑘 therefore 𝑙= 𝑘 𝑙 da 𝑚= 𝑘 𝑚 let 𝑛= 𝑘 𝑛 it 文書𝑑 1 文書𝑑 2 文書𝑑 3 文書𝑑 4 語彙セット(クエリ𝑞={𝑎,𝑑,𝑛}に限定して表示) Termset Set of Terms Documents 𝑆 𝑎 {𝑎} { 𝑑 1 , 𝑑 2 } 𝑆 𝑑 {𝑑} { 𝑑 1 , 𝑑 2 , 𝑑 3 , 𝑑 4 } 𝑆 𝑛 {𝑛} 𝑆 𝑎𝑑 {𝑎,𝑑} 𝑆 𝑎𝑛 {𝑎,𝑛} 𝑆 𝑑𝑛 {𝑑,𝑛} 𝑆 𝑎𝑑𝑛 {𝑎,𝑏,𝑑} 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 Set-Based Model a b c a d a d c a b a d e f a g d h i g h g j k g h b d b d b b b b l l l m n d m n d コレクション中の全単語 𝑎= 𝑘 𝑎 to 𝑏= 𝑘 𝑏 do 𝑐= 𝑘 𝑐 is 𝑑= 𝑘 𝑑 be 𝑒= 𝑘 𝑒 or 𝑓= 𝑘 𝑓 not 𝑔= 𝑘 𝑔 I ℎ= 𝑘 ℎ am 𝑖= 𝑘 𝑖 what j= 𝑘 𝑗 think 𝑘= 𝑘 𝑘 therefore 𝑙= 𝑘 𝑙 da 𝑚= 𝑘 𝑚 let 𝑛= 𝑘 𝑛 it 文書𝑑 1 文書𝑑 2 文書𝑑 3 文書𝑑 4 語彙セット(クエリ𝑞={𝑎,𝑑,𝑛}に限定して表示) Termset Set of Terms Documents 𝑆 𝑎 {𝑎} { 𝑑 1 , 𝑑 2 } 𝑆 𝑑 {𝑑} { 𝑑 1 , 𝑑 2 , 𝑑 3 , 𝑑 4 } 𝑆 𝑛 {𝑛} { 𝑑 4 } 𝑆 𝑎𝑑 {𝑎,𝑑} 𝑆 𝑎𝑛 {𝑎,𝑛} 𝑆 𝑑𝑛 {𝑑,𝑛} 𝑆 𝑎𝑑𝑛 {𝑎,𝑏,𝑑} 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 Set-Based Model a b c a d a d c a b a d e f a g d h i g h g j k g h b d b d b b b b l l l m n d m n d コレクション中の全単語 𝑎= 𝑘 𝑎 to 𝑏= 𝑘 𝑏 do 𝑐= 𝑘 𝑐 is 𝑑= 𝑘 𝑑 be 𝑒= 𝑘 𝑒 or 𝑓= 𝑘 𝑓 not 𝑔= 𝑘 𝑔 I ℎ= 𝑘 ℎ am 𝑖= 𝑘 𝑖 what j= 𝑘 𝑗 think 𝑘= 𝑘 𝑘 therefore 𝑙= 𝑘 𝑙 da 𝑚= 𝑘 𝑚 let 𝑛= 𝑘 𝑛 it 文書𝑑 1 文書𝑑 2 文書𝑑 3 文書𝑑 4 語彙セット(クエリ𝑞={𝑎,𝑑,𝑛}に限定して表示) Termset Set of Terms Documents 𝑆 𝑎 {𝑎} { 𝑑 1 , 𝑑 2 } 𝑆 𝑑 {𝑑} { 𝑑 1 , 𝑑 2 , 𝑑 3 , 𝑑 4 } 𝑆 𝑛 {𝑛} { 𝑑 4 } 𝑆 𝑎𝑑 {𝑎,𝑑} 𝑆 𝑎𝑛 {𝑎,𝑛} 𝑆 𝑑𝑛 {𝑑,𝑛} 𝑆 𝑎𝑑𝑛 {𝑎,𝑏,𝑑} 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 Set-Based Model a b c a d a d c a b a d e f a g d h i g h g j k g h b d b d b b b b l l l m n d m n d コレクション中の全単語 𝑎= 𝑘 𝑎 to 𝑏= 𝑘 𝑏 do 𝑐= 𝑘 𝑐 is 𝑑= 𝑘 𝑑 be 𝑒= 𝑘 𝑒 or 𝑓= 𝑘 𝑓 not 𝑔= 𝑘 𝑔 I ℎ= 𝑘 ℎ am 𝑖= 𝑘 𝑖 what j= 𝑘 𝑗 think 𝑘= 𝑘 𝑘 therefore 𝑙= 𝑘 𝑙 da 𝑚= 𝑘 𝑚 let 𝑛= 𝑘 𝑛 it 文書𝑑 1 文書𝑑 2 文書𝑑 3 文書𝑑 4 語彙セット(クエリ𝑞={𝑎,𝑑,𝑛}に限定して表示) Termset Set of Terms Documents 𝑆 𝑎 {𝑎} { 𝑑 1 , 𝑑 2 } 𝑆 𝑑 {𝑑} { 𝑑 1 , 𝑑 2 , 𝑑 3 , 𝑑 4 } 𝑆 𝑛 {𝑛} { 𝑑 4 } 𝑆 𝑎𝑑 {𝑎,𝑑} 𝑆 𝑎𝑛 {𝑎,𝑛} {∅} 𝑆 𝑑𝑛 {𝑑,𝑛} 𝑆 𝑎𝑑𝑛 {𝑎,𝑑,𝑛} 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 Set-Based Model a b c a d a d c a b a d e f a g d h i g h g j k g h b d b d b b b b l l l m n d m n d コレクション中の全単語 𝑎= 𝑘 𝑎 to 𝑏= 𝑘 𝑏 do 𝑐= 𝑘 𝑐 is 𝑑= 𝑘 𝑑 be 𝑒= 𝑘 𝑒 or 𝑓= 𝑘 𝑓 not 𝑔= 𝑘 𝑔 I ℎ= 𝑘 ℎ am 𝑖= 𝑘 𝑖 what j= 𝑘 𝑗 think 𝑘= 𝑘 𝑘 therefore 𝑙= 𝑘 𝑙 da 𝑚= 𝑘 𝑚 let 𝑛= 𝑘 𝑛 it 文書𝑑 1 文書𝑑 2 文書𝑑 3 文書𝑑 4 語彙セット(クエリ𝑞={𝑎,𝑑,𝑛}に限定して表示) Termset Set of Terms Documents 𝑆 𝑎 {𝑎} { 𝑑 1 , 𝑑 2 } 𝑆 𝑑 {𝑑} { 𝑑 1 , 𝑑 2 , 𝑑 3 , 𝑑 4 } 𝑆 𝑛 {𝑛} { 𝑑 4 } 𝑆 𝑎𝑑 {𝑎,𝑑} 𝑆 𝑎𝑛 {𝑎,𝑛} {∅} 𝑆 𝑑𝑛 {𝑑,𝑛} 𝑆 𝑎𝑑𝑛 {𝑎,𝑑,𝑛} 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 Set-Based Model a b c a d a d c a b a d e f a g d h i g h g j k g h b d b d b b b b l l l m n d m n d コレクション中の全単語 𝑎= 𝑘 𝑎 to 𝑏= 𝑘 𝑏 do 𝑐= 𝑘 𝑐 is 𝑑= 𝑘 𝑑 be 𝑒= 𝑘 𝑒 or 𝑓= 𝑘 𝑓 not 𝑔= 𝑘 𝑔 I ℎ= 𝑘 ℎ am 𝑖= 𝑘 𝑖 what j= 𝑘 𝑗 think 𝑘= 𝑘 𝑘 therefore 𝑙= 𝑘 𝑙 da 𝑚= 𝑘 𝑚 let 𝑛= 𝑘 𝑛 it 文書𝑑 1 文書𝑑 2 文書𝑑 3 文書𝑑 4 語彙セット(クエリ𝑞={𝑎,𝑑,𝑛}に限定して表示) Termset Set of Terms Documents 𝑆 𝑎 {𝑎} { 𝑑 1 , 𝑑 2 } 𝑆 𝑑 {𝑑} { 𝑑 1 , 𝑑 2 , 𝑑 3 , 𝑑 4 } 𝑆 𝑛 {𝑛} { 𝑑 4 } 𝑆 𝑎𝑑 {𝑎,𝑑} 𝑆 𝑎𝑛 {𝑎,𝑛} {∅} 𝑆 𝑑𝑛 {𝑑,𝑛} 𝑆 𝑎𝑑𝑛 {𝑎,𝑑,𝑛} 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 Set-Based Model a b c a d a d c a b a d e f a g d h i g h g j k g h b d b d b b b b l l l m n d m n d コレクション中の全単語 𝑎= 𝑘 𝑎 to 𝑏= 𝑘 𝑏 do 𝑐= 𝑘 𝑐 is 𝑑= 𝑘 𝑑 be 𝑒= 𝑘 𝑒 or 𝑓= 𝑘 𝑓 not 𝑔= 𝑘 𝑔 I ℎ= 𝑘 ℎ am 𝑖= 𝑘 𝑖 what j= 𝑘 𝑗 think 𝑘= 𝑘 𝑘 therefore 𝑙= 𝑘 𝑙 da 𝑚= 𝑘 𝑚 let 𝑛= 𝑘 𝑛 it 文書𝑑 1 文書𝑑 2 文書𝑑 3 文書𝑑 4 語彙セット(クエリ𝑞={𝑎,𝑑,𝑛}に限定して表示) Termset Set of Terms Documents 𝑆 𝑎 {𝑎} { 𝑑 1 , 𝑑 2 } 𝑆 𝑑 {𝑑} { 𝑑 1 , 𝑑 2 , 𝑑 3 , 𝑑 4 } 𝑆 𝑛 {𝑛} { 𝑑 4 } 𝑆 𝑎𝑑 {𝑎,𝑑} 𝑆 𝑑𝑛 {𝑑,𝑛} 理論上、語彙セットは最大 2 𝑡 個の単語セットを持つが 実際には空集合になるものが多いのでそこまで増えない 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 Set-Based Modelによるランク計算の方法 𝑞: クエリ（単語の組） { 𝑆 1 , 𝑆 2 ,⋯}: クエリから得られる単語セット 𝑁 𝑖 : 単語セット 𝑆 𝑖 の出現する文書数 𝑁: コレクション中の全文書数 ℱ 𝑖,𝑗 :単語セット 𝑆 𝑖 がある文書 𝑑 𝑗 中に出現する回数 定義：各( 𝑆 𝑖 , 𝑑 𝑗 )のペアについてTF-IDF重みを以下のように定義する 𝒲 𝑖,𝑗 = 1+ log ℱ 𝑖,𝑗 log 1+ 𝑁 𝑁 𝑖 𝑖𝑓 ℱ 𝑖,𝑗 >0 0 𝑖𝑓 ℱ 𝑖,𝑗 =0 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 Set-Based Modelによるランク計算の方法 𝑞: クエリ（単語の組） { 𝑆 1 , 𝑆 2 ,⋯}: クエリから得られる単語セット 𝑁 𝑖 : 単語セット 𝑆 𝑖 の出現する文書数 𝑁: コレクション中の全文書数 ℱ 𝑖,𝑗 :単語セット 𝑆 𝑖 がある文書 𝑑 𝑗 中に出現する回数 定義：各( 𝑆 𝑖 , 𝑑 𝑗 )のペアについてTF-IDF重みを以下のように定義する 𝒲 𝑖,𝑗 = 1+ log ℱ 𝑖,𝑗 log 1+ 𝑁 𝑁 𝑖 𝑖𝑓 ℱ 𝑖,𝑗 >0 0 𝑖𝑓 ℱ 𝑖,𝑗 =0 a b c a d a d c a b 𝑆 𝑎𝑏𝑐 が２個だから ℱ 𝑎𝑏𝑐,1 =2 は 文書𝑑 1 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

3.3.1 Set-Based Modelによるランク計算の方法 𝑞: クエリ（単語の組） { 𝑆 1 , 𝑆 2 ,⋯}: クエリから得られる単語セット 𝑁 𝑖 : 単語セット 𝑆 𝑖 の出現する文書数 𝑁: コレクション中の全文書数 ℱ 𝑖,𝑗 :単語セット 𝑆 𝑖 がある文書 𝑑 𝑗 中に出現する回数 定義：各( 𝑆 𝑖 , 𝑑 𝑗 )のペアについてTF-IDF重みを以下のように定義する 𝒲 𝑖,𝑗 = 1+ log ℱ 𝑖,𝑗 log 1+ 𝑁 𝑁 𝑖 𝑖𝑓 ℱ 𝑖,𝑗 >0 0 𝑖𝑓 ℱ 𝑖,𝑗 =0 単純なTF-IDFとの比較 uni-gramとn-gramの関係に似てる 単語セットを使うことで使える素性が増える 単語：t個，　単語セット: 2 𝑡 個 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 重みの比較を実際にやってみた例(TF vs TSF) TF d1 d2 d3 d4 df idf a 4 2 0.48 b 3 0.37 d 0.30 n 1 0.70 TF-IDF d1 d2 d3 d4 a 1.91 0.95 b 0.74 1.10 d 0.60 n 1.40 TSF d1 d2 d3 d4 df idf Sa 4 2 0.48 Sb 3 0.37 Sd 0.30 Sn 1 0.70 Sab Sad Sbd Sbn Sdn Sabd Sabn 0.00 Sadn Sbdn Sabdn TSF-IDF d1 d2 d3 d4 Sa 1.91 0.95 Sb 0.74 1.10 Sd 0.60 Sn 1.40 Sab Sad Sbd Sbn Sdn Sabd Sabn Sadn Sbdn 2.10 Sabdn 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 重みの比較を実際にやってみた例(logTF vs logTSF) logTF d1 d2 d3 d4 df idf a 1.60 1.30 2 0.48 b 1.48 3 0.37 d 4 0.30 n 1 0.70 TF-IDF d1 d2 d3 d4 a 0.76 0.62 b 0.48 0.54 d 0.39 n 0.91 logTSF d1 d2 d3 d4 df idf Sa 1.60 1.30 2 0.48 Sb 1.48 3 0.37 Sd 4 0.30 Sn 1 0.70 Sab Sad Sbd Sbn Sdn Sabd Sabn 0.00 Sadn Sbdn Sabdn TSF-IDF d1 d2 d3 d4 Sa 0.76 0.62 Sb 0.48 0.54 Sd 0.39 Sn 0.91 Sab Sad Sbd Sbn Sdn Sabd Sabn Sadn Sbdn 1.03 Sabdn 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 定義：文書 𝑑 𝑗 とクエリ𝑞はそれぞれ 2 𝑡 次元のベクトルとして表せる 𝒅 𝑗 =( 𝒲 1,𝑗 , 𝒲 2,𝑗 ,⋯, 𝒲 2 𝑡 ,𝑗 ) 𝒒=( 𝒲 1,𝑞 , 𝒲 2,𝑞 ,⋯, 𝒲 2 𝑡 ,𝑞 ) ベクトルの内積による類似度計算ができる 𝑠𝑖𝑚 𝒅 𝑗 ,𝒒 = 𝒅 𝑗 ∙𝒒 𝒅 𝑗 𝒒 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 3.3.1 closed termsetを用いたより速いランク計算の方法 問題点 　単語セットを用いる方法は素性の数が莫大に増えるので計算が遅い 解決策 　いくつかの単語セットの近さを利用して単語セットを減らし計算量を削減する Termset Set of Terms Documents 𝑆 𝑎 {𝑎} { 𝑑 1 , 𝑑 2 } 𝑆 𝑏 {𝑏} { 𝑑 1 , 𝑑 3 , 𝑑 4 } 𝑆 𝑛 {𝑛} { 𝑑 4 } 𝑆 𝑎𝑏 {𝑎,𝑏} 𝑆 𝑏𝑛 {𝑏,𝑛} 𝑆 𝑎 ⊂ 𝑆 𝑎𝑏 𝑆 𝑛 ⊂ 𝑆 𝑏𝑛 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model 定義：文書コレクション𝐶中において，単語セット 𝑆 𝑖 の近さは同じ文書のサブセット中に共起するすべての頻出する単語セットによる集合である。 𝑆 𝑖 の近さが与えられたとき，その中でもっとも近さの大きな単語セットをclosed termsetと呼び， 𝑆 Φ とする。 𝐷 𝑖 ⊆𝐶を， 𝑆 𝑖 が現れかつ頻出する文書サブセットとする 𝑆( 𝐷 𝑖 )を，文書サブセット 𝐷 𝑖 中のすべての文書で頻出する単語セットとする ∄ 𝑆 𝑗 ∈𝑆 𝐷 𝑖 | 𝑆 Φ 𝑖 ⊂ 𝑆 𝑗 frequency( 𝑺 𝒊 ) frequent termsets closed termset 4 d 3 b, bd bd 2 a, ad ad g, h, gh, ghd ghd 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.1 Set-Based Model Set-Based Modelまとめ 単語セットの考え方は重要だが， 実際の検索システムではあまり使われていない 理由：３つ以上の単語セットのクエリがないと使えないから closed set modelは同じ頻度を持っているクエリを計算量削減のためにまとめてしまう技術。だが、これをやること自体にも計算量がかかるのでやはり大きな文書集合で利用しにくくあまり使われない原因となっている 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 目次 3.3.1 Set-Based Model 3.3.2 Extended Boolean Model 3.3.3 Fuzzy Set Model 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.2 Extended Boolean Model Boolean retrieval シンプル 単語の重みづけがない，ランキングのつけようがない 出力のサイズが極端に大きかったり小さかったりする partial matching, term weightingでBoolean queryにvectorモデルと同様の性質を持たせる Extended Boolean Model 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.2 Extended Boolean Model 𝑤 𝑥,𝑗 = 𝑓 𝑥,𝑗 max 𝑥 𝑓 𝑥,𝑗 × 𝐼𝐷 𝐹 𝑥 max 𝑖 𝐼𝐷 𝐹 𝑖 𝑓 𝑥,𝑗 : 単語 𝑘 𝑥 が文書 𝑑 𝑗 　　　で出現した回数 𝐼𝐷 𝐹 𝑥 : IDF値 (0,1) sim高 (1,1) (0,1) (1,1) 𝐾 𝑦 sim高 𝑑 𝑗+1 𝑤 𝑥,𝑗 =𝑥, 𝑤 𝑦,𝑗 =𝑦 とおくと、 𝑑 𝑗 =(𝑥,𝑦) 𝑑 𝑗+1 𝑑 𝑗 𝑑 𝑗 AND OR 距離の長さだけがsimilarity sim低 (1,0) sim低 𝐾 𝑥 𝐾 𝑥 (1,0) 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.2 Extended Boolean Model 𝑠𝑖𝑚 𝑞 𝑜𝑟 ,𝑑 = 𝑥 2 + 𝑦 2 2 𝑠𝑖𝑚 𝑞 𝑎𝑛𝑑 ,𝑑 =1− 1−𝑥 2 + 1−𝑦 2 2 ユークリッド距離ではなく，p-distancesへの一般化も可能(1≤𝑝≤∞) 𝑞 𝑜𝑟 = 𝑘 1 ∨ 𝑝 𝑘 2 ∨ 𝑝 ⋯ ∨ 𝑝 𝑘 𝑚 𝑞 𝑎𝑛𝑑 = 𝑘 1 ∧ 𝑝 𝑘 2 ∧ 𝑝 ⋯ ∧ 𝑝 𝑘 𝑚 (generalized disjunctive query) (generalized conjunctive query) 𝑠𝑖𝑚 𝑞 𝑜𝑟 , 𝑑 𝑗 = 𝑥 1 𝑝 + 𝑥 2 𝑝 +⋯+ 𝑥 𝑚 𝑝 𝑚 1 𝑝 𝑠𝑖𝑚 𝑞 𝑎𝑛𝑑 , 𝑑 𝑗 =1− (1− 𝑥 1 𝑝 )+(1− 𝑥 2 𝑝 )+⋯+(1− 𝑥 𝑚 𝑝 ) 𝑚 1 𝑝 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.2 Extended Boolean Model 𝑠𝑖𝑚 𝑞 𝑜𝑟 , 𝑑 𝑗 = 𝑥 1 𝑝 + 𝑥 2 𝑝 +⋯+ 𝑥 𝑚 𝑝 𝑚 1 𝑝 𝑠𝑖𝑚 𝑞 𝑎𝑛𝑑 , 𝑑 𝑗 =1− 1− 𝑥 1 𝑝 + 1− 𝑥 2 𝑝 +⋯+ 1− 𝑥 𝑚 𝑝 𝑚 1 𝑝 𝑝=1のとき，𝑠𝑖𝑚 𝑞 𝑜𝑟 , 𝑑 𝑗 =𝑠𝑖𝑚 𝑞 𝑎𝑛𝑑 , 𝑑 𝑗 = 𝑥 1 + 𝑥 2 +⋯+ 𝑥 𝑚 𝑚 𝑝=∞のとき， 𝑠𝑖𝑚 𝑞 𝑜𝑟 , 𝑑 𝑗 = max 𝑥 𝑖 𝑠𝑖𝑚 𝑞 𝑎𝑛𝑑 , 𝑑 𝑗 = min 𝑥 𝑖 andとorの混ざった計算 例：𝑞= 𝑘 1 ∧ 𝑝 𝑘 2 ∨ 𝑝 𝑘 3 𝑠𝑖𝑚 𝑞,𝑑 = 1− 1− 𝑥 1 𝑝 + 1− 𝑥 2 𝑝 2 1 𝑝 𝑝 + 𝑥 3 𝑝 2 1 𝑝 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 計算 𝑥 1 , 𝑥 2 ,⋯, 𝑥 𝑚 のうち最大の項のみ1になる lim 𝑝→∞ 𝑥 1 𝑝 + 𝑥 2 𝑝 +⋯+ 𝑥 𝑚 𝑝 𝑚 1 𝑝 = lim 𝑝→∞ max 𝑥 𝑖 𝑥 1 𝑝 + 𝑥 2 𝑝 +⋯+ 𝑥 𝑚 𝑝 𝑚⋅ max 𝑥 𝑖 𝑝 1 𝑝 = max 𝑥 𝑖 lim 𝑝→∞ 1− 1− 𝑥 1 𝑝 + 1− 𝑥 2 𝑝 +⋯+ 1− 𝑥 𝑚 𝑝 𝑚 1 𝑝 = lim 𝑝→∞ max (1− 𝑥 𝑖 ) 1− 𝑥 1 𝑝 + 1− 𝑥 2 𝑝 +⋯+ 1− 𝑥 𝑚 𝑝 𝑚⋅ m𝑎𝑥 1−𝑥 𝑖 𝑝 1 𝑝 = max 1−𝑥 𝑖 = min ( 𝑥 𝑖 ) 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.2 Extended Boolean Model この手法はいくつand/or演算子があっても再帰的に適用できる。しかし，and演算子の中にor演算子が混ざっていてランキング計算をしなおすとランクスコアは上のもの（どの式？）と変わってしまう。そのため論理ブール演算子はランキングを保存しない。これが拡張ブーリアンモデルの難点である。 どういうことか and/orを展開するなどして計算順を変える度に結果が変わってしまう まとめ 拡張ブーリアンモデルはよく使われているので重要 難点としてはクエリをand/orの形で記号論理に落とすときにユーザは頭の中で計算することが難しい点 グーグル検索などはandとorの中間（ランクが高いのはandでランクが低いのはor）的な計算をしている 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 目次 3.3.1 Set-Based Model 3.3.2 Extended Boolean Model 3.3.3 Fuzzy Set Model 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.3 Fuzzy Set Model 3.3.3 Fuzzy Set Model キーワードのセットを用いて文書やクエリを表現するとき、文書コレクションにない単語についても考慮したいなどの動機で使われる 定義：あるfuzzy subset Aがuniverse of discourse Uの一部であるということをmembership関数 𝜇 𝐴 :𝑈→[0,1]で表す。これは，Uの各要素𝑢を用いて0≤ 𝜇 𝐴 𝑢 ≤1とかける。 定義：Uをuniverse of discourseとする。𝐴と𝐵をUの２つのfuzzy subsetとし、 𝐴 をUについての𝐴の補集合とする。uをUの要素とする。 このとき， 𝜇 𝐴 𝑢 =1− 𝜇 𝐴 𝑢 𝜇 𝐴∪𝐵 𝑢 = max 𝜇 𝐴 𝑢 , 𝜇 𝐵 (𝑢) 𝜇 𝐴∩𝐵 𝑢 = min 𝜇 𝐴 𝑢 , 𝜇 𝐵 (𝑢) 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.3 Fuzzy Set Model Fuzzy Information Retrieval シソーラスを用いた検索方法 単語 𝑘 𝑖 , 𝑘 𝑙 間の相関行列C（キーワード相関行列）を以下のように定義 𝑐 𝑖,𝑙 = 𝑛 𝑖,𝑙 𝑛 𝑖 + 𝑛 𝑙 − 𝑛 𝑖,𝑙 AND （[0,1]への正規化のため） 𝑛 𝑖 : 𝑘 𝑖 を含む文書の数 𝑛 𝑙 : 𝑘 𝑙 を含む文書の数 𝑛 𝑖,𝑙 : 𝑘 𝑖 , 𝑘 𝑙 両方を含む文書の数 OR 単語相関行列Cによってあるfuzzy setとそれぞれの単語 𝑘 𝑖 を関連づけることができる。文書 𝑑 𝑗 はmembership度 𝜇 𝑖,𝑗 を持っていて 𝜇 𝑖,𝑗 =1− 𝑘 𝑙 ∈ 𝑑 𝑗 1− 𝑐 𝑖,𝑙 𝑘 𝑖 と 𝑘 𝑙 に相関（共起頻度）がない確率 𝑘 𝑖 と 𝑑 𝑗 のすべての単語に相関がない確率 𝑘 𝑖 が 𝑑 𝑗 の少なくとも１つの単語と相関がある確率 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.3 Fuzzy Set Model [𝑞= 𝑘 𝑎 ∧( 𝑘 𝑏 ∨¬ 𝑘 𝑐 )]を[ 𝒒 𝑑𝑛𝑓 = 1,1,1 ∨ 1,1,0 ∨ 1,0,0 ]のようにOR 型になおして表すとする。ここで， 𝑘 𝑎 , 𝑘 𝑏 , 𝑘 𝑐 はバイナリ重みで [ 𝒒 𝑑𝑛𝑓 =𝑐 𝑐 1 ∨𝑐 𝑐 2 ∨⋯∨𝑐 𝑐 𝑝 ] ただし，𝑐 𝑐 𝑖 はi番目のconjunctive component?(disjunctiveの間違い?) ? 𝐷 𝑎 を，単語 𝑘 𝑎 に関連付けられた文書のfuzzy setだとする。このfuzzy setは文書 𝑑 𝑗 とそのmembership度 𝜇 𝑎,𝑗 (>閾値𝐾)で構成される 𝐷 𝑎 を 𝐷 𝑎 の補集合とする。 𝐷 𝑎 は 𝑘 𝑎 の否定 𝑘 𝑎 に関連付けられている。 同様にして 𝐷 𝑏 , 𝑘 𝑏 , 𝐷 𝑐 , 𝑘 𝑐 を考えることができて， 𝐷 𝑞 =𝑐 𝑐 1 +𝑐 𝑐 2 +𝑐 𝑐 3 𝑐 𝑐 3 𝑐 𝑐 2 [𝑞= 𝑘 𝑎 ∧( 𝑘 𝑏 ∨¬ 𝑘 𝑐 )] 𝑐 𝑐 1 𝑐 𝑐 1 = 𝜇 𝑎,𝑗 𝜇 𝑏,𝑗 𝜇 𝑐,𝑗 𝑐 𝑐 2 = 𝜇 𝑎,𝑗 𝜇 𝑏,𝑗 1− 𝜇 𝑐,𝑗 𝑐 𝑐 3 = 𝜇 𝑎,𝑗 (1−𝜇 𝑏,𝑗 ) 1− 𝜇 𝑐,𝑗 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST

2016ⒸSeitaro Shinagawa AHC-lab NAIST 3.3.3 Fuzzy Set Model 𝑐 𝑐 1 = 𝜇 𝑎,𝑗 𝜇 𝑏,𝑗 𝜇 𝑐,𝑗 𝑐 𝑐 2 = 𝜇 𝑎,𝑗 𝜇 𝑏,𝑗 1− 𝜇 𝑐,𝑗 𝑐 𝑐 3 = 𝜇 𝑎,𝑗 (1−𝜇 𝑏,𝑗 ) 1− 𝜇 𝑐,𝑗 fuzzy set 𝐷 𝑞 中の文書 𝑑 𝑗 のmembership 𝜇 𝑞,𝑗 は 𝜇 𝑞,𝑗 = 𝜇 𝑐 𝑐 1 +𝑐 𝑐 2 +𝑐 𝑐 3 ,𝑗 =1− 𝑖=1 3 1− 𝜇 𝑐𝑐,𝑗 =1− 1− 𝜇 𝑎,𝑗 𝜇 𝑏,𝑗 𝜇 𝑐,𝑗 × 1− 𝜇 𝑎,𝑗 𝜇 𝑏,𝑗 1− 𝜇 𝑐,𝑗 × 1− 𝜇 𝑎,𝑗 (1−𝜇 𝑏,𝑗 ) 1− 𝜇 𝑐,𝑗 まとめ fuzzy理論は情報検索ではマイナーな手法 大部分の実験も小さな文書コレクションについてしか適用されていない 拡張ブーリアンモデルも似ているが、0,1ではなく中間値をとることで想定されていない処理に余裕を持たせようとして研究されていた（今は流行っていないが発想は重要） 2019/5/2 2016ⒸSeitaro Shinagawa AHC-lab NAIST