Extended Boolean model

Extended Boolean Model was introduced in 1983 by Salton, Fox, and Wu. The goal of Extended Boolean Model is to overcome the drawback of Boolean model used in information retrieval. Boolean model doesn't consider term weight while doing query, and the results of boolean query is often either too small or too big. The notion is to make use of partial matching and term weight as vector space model. It combines the characteristics of the Vector Space Model withe the properties of Boolean algebra. and rank the similarity between query and documents.

Definitions

A Extended Boolean model document is represent as a vector(similar as vector model). Each dimension corresponds to a separate term weight associated with document. The term x weight associated with document j can be define as:

$w_{x,j}=f_{x,j}*{\frac {Idf_{x}}{max_{i}Idf_{x}}}$

,where $Idf_{x}$ is inverse document frequency.

The weight vector associated with document j can be represent as:

$\mathbf {v} _{d}=[w_{1,j},w_{2,j},\ldots ,w_{i,j}]$

The 2 Dimensions Example

Figure 1: The similarities of $q=K_{x}\lor K_{y}$ and document Dj, Dj+1.

Considering the space composed of two terms Kx and ky only, the correspond term weights is w1,w2:

For query q=(Kx or Ky), Thus, we can use:

$sim(q_{or},d)={\sqrt {\frac {w_{1}^{2}+w_{2}^{2}}{2}}}$

to calculate the similarity.

Figure 2: The similarities of $q=K_{x}\land K_{y}$ and document Dj, Dj+1.

Considering the space composed of two terms Kx and ky only, the correspond term weights is w1,w2: For query q=(Kx and Ky), Thus, we can use:

$sim(q_{or},d)=1-{\sqrt {\frac {(1-w_{1})^{2}+(1-w_{2})^{2}}{2}}}$

Generalizing the idea and P-norms

We can generalize the previous 2D extend boolean model example to higher t-dimension of Euclidean distances.

This can be done using P-norms which extend the notion of distance to include p-distances, where $1\leq p\leq \infty$is a new parameter.

• A generalized conjunctive query is given by:

$q_{or}=k_{1}\lor ^{p}k_{2}\lor ^{p}....\lor ^{p}k_{t}$

• The similarity of $q_{or}$ and $d_{j}$ can be define:

$sim(q_{or},d_{j})={\sqrt[{p}]{\frac {w_{1}^{p}+w_{2}^{p}+....+w_{t}^{p}}{t}}}$

• A generalized disjunctive query is given by:

$q_{and}=k_{1}\land ^{p}k_{2}\land ^{p}....\land ^{p}k_{t}$

• The similarity of $q_{and}$ and $d_{j}$ can be define:

$sim(q_{and},d_{j})=1-{\sqrt[{p}]{\frac {(1-w_{1})^{p}+(1-w_{2})^{p}+....+(1-w_{t})^{p}}{t}}}$

Examples

consider the query $q=(k_{1}\land k_{2})\lor k_{3}$, The similarity between query and document d can be the following formula:

$sim(q,d)={\sqrt[{p}]{\frac {(1-{\sqrt[{p}]{({\frac {(1-w_{1})^{p}+(1-w_{2})^{p}}{2}}}}))^{p}+w_{3}^{p}}{2}}}$

Further reading

• Adaptive Feedback Methods in an Extended Boolean Model by Dr.Jongpill Choi
• Interpolation of the extended Boolean retrieval model

See also

• Information retrieval

References

• Dr. E. Garcia, The Extended Boolean Model - Weighted Queries: Term Weights, p-Norm Queries and Multiconcept Types. Boolean OR Extended? AND that is the Query