Булева модель поиска информации

Эта статья может быть слишком технической для понимания большинства читателей . Пожалуйста, помогите улучшить ее, чтобы сделать ее понятной для неспециалистов , не удаляя технические детали. ( Июнь 2018 ) ( Узнайте, как и когда удалять это сообщение )

(Стандартная) Булева модель информационного поиска ( BIR ) ^[1] является классической моделью информационного поиска (IR) и, в то же время, первой и наиболее принятой. ^[2] BIR основана на булевой логике и классической теории множеств в том смысле, что и искомые документы, и запрос пользователя рассматриваются как наборы терминов ( модель мешка слов ). Поиск основан на том, содержат ли документы термины запроса и удовлетворяют ли они булевым условиям, описанным запросом.

Индексный термин — это слово или выражение , которое может быть с корнем , описывающее или характеризующее документ, например, ключевое слово, данное для журнальной статьи. Пусть будет набором всех таких индексных терминов.$${\displaystyle T=\{t_{1},t_{2},\ \ldots ,\ t_{n}\}}$$

Документ — это любое подмножество . Пусть — множество всех документов.${\displaystyle Т}$$${\displaystyle D=\{D_{1},\ \ldots \ ,D_{n}\}}$$

${\displaystyle Т}$представляет собой ряд слов или небольших фраз (индексных терминов). Каждое из этих слов или небольших фраз имеет имя , где — номер термина в ряду/списке. Вы можете думать о «Терминах» и как о «индексном термине n ».${\displaystyle t_{n}}$${\displaystyle n}$${\displaystyle Т}$${\displaystyle t_{n}}$

Слова или небольшие фразы (термины индекса ) могут существовать в документах. Затем эти документы образуют серию/список , где каждый отдельный документ называется . Эти документы ( ) могут содержать слова или небольшие фразы (термины индекса ), например, могут содержать термины и из . Пример этого приведен в следующем разделе.${\displaystyle t_{n}}$${\displaystyle D}$${\displaystyle D_{n}}$${\displaystyle D_{n}}$${\displaystyle t_{n}}$${\displaystyle D_{1}}$ ${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle Т}$

Индексные термины обычно хотят представлять слова, которые имеют большее значение для них и соответствуют тому, о чем может говорить содержание статьи или документа. Такие термины, как «the» и «like», будут появляться почти во всех документах, тогда как «Bayesian» будет только в небольшой части документов. Поэтому более редкие термины, такие как «Bayesian», являются лучшим выбором для выбора в наборах . Это относится к энтропии (теории информации) . Существует несколько типов операций, которые можно применять к индексным терминам, используемым в запросах, чтобы сделать их более общими и более релевантными. Одной из них является Stemming .${\displaystyle Т}$

Запрос представляет собой логическое выражение в нормальной форме: где истинно для когда . (Эквивалентно, может быть выражено в дизъюнктивной нормальной форме .)${\textstyle В}$$${\displaystyle Q=(W_{1}\ \lor \ W_{2}\ \lor \ \cdots )\land \ \cdots \ \land \ (W_{i}\ \lor \ W_{i+1}\ \lor \ \cdots )}$$${\textstyle W_{i}}$${\displaystyle D_{j}}$${\displaystyle t_{i}\in D_{j}}$${\textstyle В}$

Любые запросы представляют собой выборку индексных терминов ( или ), выбранных из набора терминов, которые объединяются с помощью булевых операторов для формирования набора условий.${\displaystyle Q}$${\displaystyle t_{n}}$${\displaystyle W_{n}}$${\displaystyle Т}$

Затем эти условия применяются к набору документов, содержащих те же самые индексные термины ( ) из набора .${\displaystyle D}$${\displaystyle t_{n}}$${\displaystyle Т}$

Мы стремимся найти набор документов, которые удовлетворяют . Эта операция называется поиском и состоит из следующих двух шагов:${\textstyle В}$

1. Для каждого из найдите набор документов, удовлетворяющих : 2. Тогда набор документов, удовлетворяющих Q, задается формулой: Где означает ИЛИ , а означает И как булевы операторы.${\textstyle W_{j}}$${\textstyle В}$${\textstyle S_{j}}$${\textstyle W_{j}}$$${\displaystyle S_{j}=\{D_{i}\mid W_{j}\}}$$$${\displaystyle (S_{1}\cup S_{2}\cup \cdots )\cap \cdots \cap (S_{i}\cup S_{i+1}\cup \cdots )}$$${\displaystyle \чашка}$${\displaystyle \cap}$

Пусть набор исходных (реальных) документов будет, например,

${\displaystyle D=\{D_{1},\ D_{2},\ D_{3}\}}$

где

${\textstyle D_{1}}$= "Принцип Байеса: принцип, согласно которому при оценке параметра следует изначально предположить, что каждое возможное значение имеет равную вероятность (равномерное априорное распределение)".

${\textstyle D_{2}}$= " Байесовская теория принятия решений : математическая теория принятия решений, которая предполагает функции полезности и вероятности и согласно которой выбираемым действием является действие Байеса, т. е. действие с наивысшей субъективной ожидаемой полезностью. Если бы у человека было неограниченное время и вычислительная мощность для принятия каждого решения, эта процедура была бы наилучшим способом принятия любого решения."

${\textstyle D_{3}}$= "Байесовская эпистемология : философская теория, которая утверждает, что эпистемический статус предложения (то есть насколько оно хорошо доказано или установлено) наилучшим образом измеряется вероятностью и что правильный способ пересмотра этой вероятности дается байесовской обусловленностью или аналогичными процедурами. Байесовский эпистемолог будет использовать вероятность для определения и изучения взаимосвязи между такими понятиями, как эпистемический статус, поддержка или объяснительная сила".

Пусть набор терминов будет:${\textstyle Т}$

$${\displaystyle T=\{t_{1}={\text{принцип Байеса}},t_{2}={\text{вероятность}},t_{3}={\text{принятие решений}},t_{4}={\text{байесовская эпистемология}}\}}$$

Тогда комплект документов следующий:${\textstyle D}$

$${\displaystyle D=\{D_{1},\ D_{2},\ D_{3}\}}$$

где$${\displaystyle {\begin{aligned}D_{1}&=\{{\text{probability}},\ {\text{Bayes' principle}}\}\\D_{2}&=\{{\text{probability}},\ {\text{decision-making}}\}\\D_{3}&=\{{\text{probability}},\ {\text{Bayesian epistemology}}\}\end{aligned}}}$$

Пусть запрос будет («вероятность» И «принятие решения»):${\textstyle Q}$

$${\displaystyle Q={\text{probability}}\land {\text{decision-making}}}$$Затем, чтобы получить соответствующие документы:

1. Во-первых, получаются (извлекаются) следующие наборы документов : Где соответствует документам, содержащим термин «вероятность», а также содержит термин «принятие решения».${\textstyle S_{1}}$${\textstyle S_{2}}$${\textstyle D_{i}}$$${\displaystyle {\begin{aligned}S_{1}&=\{D_{1},\ D_{2},\ D_{3}\}\\S_{2}&=\{D_{2}\}\end{aligned}}}$$${\displaystyle S_{1}}$${\displaystyle S_{2}}$
2. Наконец, в ответ на запрос извлекаются следующие документы : где запрос ищет документы, содержащиеся в обоих наборах, с использованием оператора пересечения.${\textstyle D_{i}}$${\textstyle Q}$$${\displaystyle Q:\{D_{1},\ D_{2},\ D_{3}\}\ \cap \ \{D_{2}\}\ =\ \{D_{2}\}}$$${\displaystyle S}$

Это означает, что исходный документ является ответом на .${\displaystyle D_{2}}$${\textstyle Q}$

Если существует более одного документа с одинаковым представлением (одинаковое подмножество индексных терминов ), каждый такой документ извлекается. Такие документы неразличимы в BIR (другими словами, эквивалентны).${\displaystyle t_{n}}$

• Чистый формализм
• Легко реализовать
• Интуитивно понятная концепция
• Если полученный набор документов слишком мал или слишком велик, сразу становится ясно, какие операторы создадут соответственно больший или меньший набор.
• Это дает (экспертным) пользователям ощущение контроля над системой. Сразу становится ясно, почему документ был извлечен по запросу.

• Точное совпадение может привести к извлечению слишком малого или слишком большого количества документов.
• Трудно перевести запрос в логическое выражение
• Неэффективен для концепций, устойчивых к поиску ^[3]
• Все термины имеют одинаковый вес.
• Больше похоже на поиск данных, чем на поиск информации
• Поиск на основе бинарных критериев принятия решений без понятия частичного соответствия
• Рейтинг документов не предусмотрен (отсутствие шкалы оценок)
• Необходимость в информации должна быть преобразована в логическое выражение, что большинство пользователей считают неудобным.
• Булевы запросы, формулируемые пользователями, чаще всего слишком упрощены.
• Модель часто возвращает либо слишком мало, либо слишком много документов в ответ на запрос пользователя.

С чисто формальной математической точки зрения BIR является простым. Однако с практической точки зрения необходимо решить несколько дополнительных проблем, связанных с алгоритмами и структурами данных, например, выбор терминов (ручной или автоматический выбор или оба), стемминг , хэш-таблицы , инвертированная файловая структура и т. д. ^[4]

Другая возможность — использовать хэш-наборы. Каждый документ представлен хэш-таблицей, которая содержит каждый отдельный термин этого документа. Поскольку размер хэш-таблицы увеличивается и уменьшается в реальном времени с добавлением и удалением терминов, каждый документ будет занимать гораздо меньше места в памяти. Однако это приведет к замедлению производительности, поскольку операции более сложны, чем с битовыми векторами . В худшем случае производительность может ухудшиться с O( n ) до O( n ² ). В среднем случае замедление производительности будет не намного хуже, чем у битовых векторов, а использование пространства будет намного эффективнее.

Каждый документ может быть суммирован фильтром Блума, представляющим набор слов в этом документе, сохраненный в битовой строке фиксированной длины, называемой сигнатурой. Файл сигнатуры содержит одну такую ​​суперпозиционную битовую строку кода для каждого документа в коллекции. Каждый запрос также может быть суммирован фильтром Блума, представляющим набор слов в запросе, сохраненный в битовой строке той же фиксированной длины. Битовая строка запроса проверяется по каждой сигнатуре. ^{[5] [6] [7]}

Рассматриваемый файл подписи используется в BitFunnel .

Файл инвертированного индекса состоит из двух частей: словаря, содержащего все термины, используемые в коллекции, и для каждого отдельного термина инвертированный индекс, в котором перечислены все документы, в которых упоминается этот термин. ^{[5] [6]}

• Лашкари, AH; Махдави, F.; Гоми, V. (2009), «Булевская модель в информационном поиске для поисковых систем», Международная конференция по управлению информацией и инжинирингу 2009 г. , стр.  385–389 , doi :10.1109/ICIME.2009.101, ISBN 978-0-7695-3595-1, S2CID  18147603