Binary Independence Model

BIM (Binary Independence Model, 二項独立モデル)^[1] ^[2]は、簡単な仮定をおくことで，文書/クエリの類似性確率の推定を可能にする確率的情報検索手法である。

定義[編集]

Binary Independence Assumptionとは、文書をBinary Vectorとしてみなす仮定である。つまり、文書内の用語の有無のみが文書情報として利用される。用語は関係のある文書の集合の中に独立して分布していて、また無関係な文書集合の中にも独立して分布していると仮定される。その文書表現はordered set of Boolean variablesです。つまり、文書またはクエリは考慮中の各用語ごとに1つのブール要素を持つベクトルとして表現される。より具体的には、文書はベクトル $d = (x 1, ..., x m)$ によって表される．ただしここで、用語tが文書dに存在する場合は $x t =1$ であり、存在しない場合は $x t =0$ となる。この単純化により、多くの文書が同じベクトル表現を持つことが可能となる。クエリも同様に表現することができる。 BIMにおける"Independence"とは、文書中の用語が互いに独立して考慮され、用語間の関連がモデル化されていないことを意味する。この仮定は非常に限定的ですが、多くの状況で十分な結果が得られることが証明されています。この独立性は、 Naive Bayes分類器の"naive"な仮定と同様のものである。つまり，互いに暗黙的に関係するプロパティは、単純化のために独立しているとして扱われる。この仮定により、各項を他の項に使用される次元に直交する次元に沿った0または1の値と見なすことで、文書あるいはクエリのベクトル表現をVector空間モデルのベクトルとして扱うことが可能となる

確率 $P(R|d,q)$ 文書が関連性があるということは、その文書の用語ベクトルの関連性の可能性に由来します。 $P(R|x,q)$ 。ベイズの法則を使用すると、次のようになります。

P(R|x,q)={\frac {P(x|R,q)*P(R|q)}{P(x|q)}}

ここで $P(x|R=1,q)$ と $P(x|R=0,q)$ はそれぞれ関連・非関連文書を検索する確率である。そのときその文書の表現はxです。正確な確率を事前に知ることはできないので、文書の集合に関する統計からの推定値を使用する必要がある。

$P(R=1|q)$ と $P(R=0|q)$ はクエリqに関して、それぞれ関連文書または非関連文書を検索する前の確率を示している。たとえば、コレクション内の関連文書の割合がわかっている場合は、この割合を使用してこれらの確率を推定できます。文書はクエリに関連しているか関連していないため、次のような式が成立する。

P(R=1|x,q)+P(R=0|x,q)=1

クエリ用語の重み付け[編集]

バイナリクエリおよび，文書とクエリとの間の類似性関数としてドット積が与えられたとする．このとき検索効率が高くなるようにクエリ内の用語に重みを割り当てることが問題となる。 $p_{i}$ が関連文書がi番目の語句を持つ確率であり， $q_{i}$ は同様に非関連文書がi番目の語句を持つ確率であるとする．最初にBIMを紹介したYu and Salton ^[1]は、 i番目の単語の重みを $Y_{i}={\frac {p_{i}*(1-q_{i})}{(1-p_{i})*q_{i}}}$ $p_{i}$ に対して単調増加し， $q_{i}$ に対して単調に増加する関数として定義した．したがって、 $Y_{i}$ より高い $Y_{j}$ 、用語の重み $i$ ターム $j$ のそれよりも高くなります。 YuとSalton ^[1]は、クエリ用語へのそのような重み割り当てが、クエリ用語が等しく重み付けされている場合よりも優れた検索効率をもたらすことを明らかにした。 RobertsonとSpärckJones ^[2]は、 i番目の単語が $logY_{i}$ の重みを割り当てられている場合、 $\log Y_{i}$ Binary Independence Assumptionの下で最適な検索効果が得られることを明らかにした。