View source for Compact Lie algebra

The '''Extended Boolean model''' was described in a Communications of the ACM article appearing in 1983, by Gerard Salton, Edward A. Fox, and Harry Wu. The goal of the Extended Boolean model is to overcome the drawbacks of the Boolean model that has been used in [[information retrieval]]. The Boolean model doesn't consider term weights in queries, and the result set of a Boolean query is often either too small or too big. The idea of the extended model is to make use of partial matching and term weights as in the vector space model. It combines the characteristics of the [[Vector Space Model]] with the properties of [[Boolean algebra (logic)|Boolean algebra]] and ranks the similarity between queries and documents. This way a document may be somewhat relevant if it matches some of the queried terms and will be returned as a result, whereas in the [[Standard Boolean model]] it wasn't.<ref>	
{{citation | url=http://portal.acm.org/citation.cfm?id=358466 | last=Salton | first=Gerard | coauthors=Edward A. Fox, Harry Wu | title=Extended Boolean information retrieval | publisher=Communications of the ACM, Volume 26,  Issue 11 | year=1983 }}</ref>

Thus, the extended Boolean model can be considered as a generalization of both the Boolean and vector space models; those two are special cases if suitable settings and definitions are employed. Further, research has shown effectiveness improves relative to that for Boolean query processing.  Other research has shown that [[relevance feedback]] and [[query expansion]] can be integrated with extended Boolean query processing.

==Definitions==
In the '''Extended Boolean model''', a document is represented as a vector (similarly to in the vector model). Each ''i'' [[Dimension (vector space)|dimension]] corresponds to a separate term associated with the document.

The weight of term {{math|''K<sub>x</sub>''}} associated with document {{math|''d<sub>j</sub>''}} is measured by its normalized [[Term frequency]] and can be defined as:

<math>
w_{x,j}=f_{x,j}*\frac{Idf_{x}}{max_{i}Idf_{i}}
</math>

where {{math|''Idf<sub>x</sub>''}} is [[inverse document frequency]].

The weight vector associated with document {{math|''d<sub>j</sub>''}} can be represented as:

<math>\mathbf{v}_{d_j} = [w_{1,j}, w_{2,j}, \ldots, w_{i,j}]</math>

==The 2 Dimensions Example==
{{multiple image
 | width     = 150
 | image1    = 2D_Extended_Boolean_model_OR_example.png
 | alt1      = Figure 1
 | caption1  = '''Figure 1:''' The similarities of {{math|''q'' {{=}} (''K<sub>x</sub>'' &or; ''K<sub>y</sub>'')}} with documents {{math|''d<sub>j</sub>''}} and {{math|''d''<sub>''j''+1</sub>}}.
 | image2    = 2D_Extended_Boolean_model_AND_example.png
 | alt2      = Figure 2
 | caption2  = '''Figure 2:''' The similarities of {{math|''q'' {{=}} (''K<sub>x</sub>'' &and; ''K<sub>y</sub>'')}} with documents {{math|''d<sub>j</sub>''}} and {{math|''d''<sub>''j''+1</sub>}}.
}}

Considering the space composed of two terms {{math|''K<sub>x</sub>''}} and {{math|''K<sub>y</sub>''}} only, the corresponding term weights are {{math|''w''<sub>1</sub>}} and {{math|''w''<sub>2</sub>}}.<ref>[http://www.cs.cityu.edu.hk/~cs5286/Lectures/Lwang.ppt Lusheng Wang]</ref>  Thus, for query {{math|''q<sub>or</sub>'' {{=}} (''K<sub>x</sub>'' &or; ''K<sub>y</sub>'')}}, we can calculate the similarity with the following formula:
 
<math>sim(q_{or},d)=\sqrt{\frac{w_1^2+w_2^2}{2}}</math>

For query {{math|''q<sub>and</sub>'' {{=}} (''K<sub>x</sub>'' &and; ''K<sub>y</sub>'')}}, we can use:

<math>sim(q_{and},d)=1-\sqrt{\frac{(1-w_1)^2+(1-w_2)^2}{2}}</math>

==Generalizing the idea and P-norms==
We can generalize the previous 2D extended Boolean model example to higher t-dimensional space using Euclidean distances.

This can be done using [[P-norm]]s which extends the notion of distance to include p-distances, where {{math|1 &le; ''p'' &le; &infin;}} is a new parameter.<ref>{{ citation | last=Garcia | first= Dr. E. | url=http://www.miislita.com/term-vector/term-vector-6-boolean-model.html | title=The Extended Boolean Model - Weighted Queries: Term Weights, p-Norm Queries and Multiconcept Types. Boolean OR Extended? AND that is the Query }}</ref>

*A generalized conjunctive query is given by:
:<math>q_{or}=k_1 \lor^p k_2 \lor^p .... \lor^p k_t  </math>

*The similarity of <math>q_{or}</math> and <math>d_j</math> can be defined as:
''':<math>sim(q_{or},d_j)=\sqrt[p]{\frac{w_1^p+w_2^p+....+w_t^p}{t}}</math>'''

*A generalized disjunctive query is given by:
:<math>q_{and}=k_1 \land^p k_2 \land^p .... \land^p k_t  </math>

*The similarity of <math>q_{and}</math> and <math>d_j</math> can be defined as:
:<math>sim(q_{and},d_j)=1-\sqrt[p]{\frac{(1-w_1)^p+(1-w_2)^p+....+(1-w_t)^p}{t}}</math>

==Examples==
Consider the query {{math|''q'' {{=}} (''K''<sub>1</sub> &and; ''K''<sub>2</sub>) &or; ''K''<sub>3</sub>}}. The similarity between query {{math|''q''}} and document {{math|''d''}} can be computed using the formula:

<math>sim(q,d)=\sqrt[p]{\frac{(1-\sqrt[p]{(\frac{(1-w_1)^p+(1-w_2)^p}{2}}))^p+w_3^p}{2}}</math>

==Improvements over the Standard Boolean Model==

Lee and Fox<ref>{{citation | last=Lee | first=W. C. | coauthors=E. A. Fox | year=1988 | title=Experimental Comparison of Schemes for Interpreting Boolean Queries}}</ref> compared the Standard and Extended Boolean models with three test collections, CISI, CACM and INSPEC.
Using P-norms they obtained an average precision improvement of 79%, 106% and 210% over the Standard model, for the CISI, CACM and INSPEC collections, respectively.<br>
The P-norm model is computationally expensive because of the number of exponentiation operations that it requires but it achieves much better results than the Standard model and even [[Fuzzy retrieval]] techniques. The [[Standard Boolean model]] is still the most efficient.

==Further reading==
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.1997 Adaptive Feedback Methods in an Extended Boolean Model  by Dr.Jongpill Choi]
* [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6VC8-454T5MS-2&_user=513551&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1117914301&_rerunOrigin=google&_acct=C000025338&_version=1&_urlVersion=0&_userid=513551&md5=4eab0da46bfe361afa883e48f2060feb Interpolation of the extended Boolean retrieval model ]
* {{citation | title=Information Retrieval: Algorithms and Data structures; Extended Boolean model | last=Fox | first=E. | coauthors=S. Betrabet , M. Koushik , W. Lee | year=1992 | publisher=Prentice-Hall, Inc. | url=http://www.scribd.com/doc/13742235/Information-Retrieval-Data-Structures-Algorithms-William-B-Frakes}}
* {{citation | title=Experiments with Automatic Query Formulation in the Extended Boolean Model | url=http://www.springerlink.com/content/tk1t141253257613/ | first= Lucie | last= Skorkovská | coauthors=Pavel Ircing | year=2009 | publisher= Springer Berlin / Heidelberg}}

==See also==
*[[Information retrieval]]

==References==
{{reflist}}

{{DEFAULTSORT:Extended Boolean Model}}
[[Category:Information retrieval]]