Лекция 13. Эффективность информационных систем На прошедших лекциях мы рассматривали принципы действия информационных систем. Теперь сосредоточимся на вопросах оценки эффективности этого действия

Вид материалаЛекция

Содержание


2. Критерии и эшелоны выдачи
3. Полнота и точность поиска
Подобный материал:

Лекция 13. Эффективность информационных систем



На прошедших лекциях мы рассматривали принципы действия информационных систем. Теперь сосредоточимся на вопросах оценки эффективности этого действия.

1. Пертинентность и релевантность


Функция информационной системы состоит в выделении из поискового массива таких документов, которые содержат информацию, удовлетворяющую информационную потребность пользователя. Но информационная потребность выражается в информационном запросе, формулировка которого может лишь более или менее приблизительно выражать действительную информационную потребность. («Мысль изреченная есть ложь»). Информационный запрос представляется поисковой системе в виде поискового образа запроса (ПОЗ), т.е. формализованного перечня терминов. Кроме того задаётся формальный критерий соответствия (КС) документа запросу. Поисковый образ запроса вместе с критерием соответствия составляют поисковое предписание: ПП = ПОЗ + КС. Информационная система в ответ на запрос, выполняя поисковое предписание, выдаёт некоторую совокупность документов. (См. рис. 15.1).


Информационная потребность

Информационный запрос

Поисковый образ запроса

Поисковое предписание

Процедура поиска

Поисковый образ документа

техническая релевантность

семантическая релевантность

пертинентность





Критерий соответствия


системная релевантность






Выдача документа




Рис. 15.1. Соотношение информационной потребности и документной выдачи


Однако не все документы в выдаче удовлетворяют информационной потребности. Как правило, они лишь формально соответствуют поисковому предписанию. Документы, действительно соответствующие потребности пользователя, называются пертинентными. А сама информационная потребность представляет собой весьма сложное психическое явление, и проблема повышения степени пертинентности выдачи оказывается не только трудной для достижения, но её даже трудно чётко поставить как практическую задачу. Определить соответствие выдачи документированному запросу проще. Документы, соответствующие запросу, называются релевантными. Однако суждение о релевантности будет зависеть от того, кто это суждение выносит. Если автор запроса, то он будет оценивать не столько релевантность, сколько пертинентность, в той мере, в которой ему удастся ознакомиться с документом. Если же релевантность будет оценивать работник системы, то он сможет объективно учитывать только формальное вхождение элементов поискового предписания в документ, не задаваясь вопросом о соответствии запроса потребности пользователя («Каков запрос, таков и ответ»). Но именно последняя характеристика определяет эффективность самой системы. Таким образом, надо различать техническую релевантность и семантическую релевантность (соответствие смыслу, а не форме запроса).

Для организации выдачи документов система должна уметь оценивать релевантность априори, до выдачи, чтобы выдать именно релевантные документы. А для определения качества работы системы оценку релевантности выданных документов производят апостериори, после выдачи. Конечно апостериорная релевантность сильно зависит от априорной, но эти характеристики различны по своей природе. Так, при автоматическом поиске система не имеет ничего, кроме поискового предписания и поисковых образов документов. Это значит, что система может устанавливать соответствие только этих объектов, что влечёт введение ещё одного параметра – системной релевантности.

2. Критерии и эшелоны выдачи


Простейший и весьма распространённый критерий релевантности состоит в требовании полного совпадения поискового образа документа с поисковым предписанием. Но этот критерий применим только к ограниченным видам запросов, например к поиску по полному библиографическому описанию, или к поиску всех документов в некотором тематическом классе по принятой классификации знаний. А в реальных поисковых системах при всестороннем координатном индексировании вероятность полного совпадения предписания с поисковым образом документа крайне низка. Поэтому необходимо как-то оценивать не абсолютную, а относительную релевантность – степень релевантности – на основе частичного совпадения поискового предписания с поисковым образом документа. При этом система должна выдавать документ, если степень его релевантности запросу превзошёл некоторый достаточно высокий порог. Методов вычисления степени системной релевантности было предложено довольно много, и многие из них имеют весьма изощрённый характер в попытке по формальным признаками промоделировать человеческое восприятие сходства и различия смысла текстов. Рассмотрим некоторые из них.

Начнём с простых оценок. Степень релевантности можно оценивать отношением числа дескрипторов запроса, найденных в документе, А к общему числу N дескрипторов в запросе: R1 = А/N. Требование полного совпадения запроса с документом соответствует R1 = 1 и A = N = M, где М – полное число дескрипторов в поисковом образе документа. В практических поисковых системах порог релевантности задают установлением допустимой разницы (d) между общим числом дескрипторов в запросе N и числом их, найденных в документе. Величина R1 = (N–d)/N при этом меньше 1. Отсутствие в документе некоторых дескрипторов запроса означает, что в этом документе дана неполная информация на запрос, но имеются достаточно полезные сведения. Если поиск на полное совпадение даёт неудовлетворительный результат, проводят поиск на совпадение всех, кроме одного дескриптора запроса (d = 1), кроме двух (d = 2) и т. д. Если же запрос состоит всего из одного термина, то можно вести поиск только на полное совпадение. Присутствие в документе дескрипторов, отсутствующих в запросе, обычно не учитывается при поиске, но оно может означать, что не весь документ важен для пользователя, и это снижает степень его фактической релевантности.

Последнее соображение учитывается в более сложном случае, когда за критерий релевантности принимается величина R2 = А/М – отношение числа найденных дескрипторов в документе к числу всех дескрипторов в поисковом образе документа. Требование полного совпадения документа с запросом здесь также соответствует R2 = 1, а при частичном совпадении значение R2 находится в пределах от 1 до 0. Как показала практика, для систем с таким критерием релевантности удовлетворительная выдача наблюдается при установлении порога выдачи в интервале от R2=0,25 до R2 = 0,4. Очевидно, что R2 зависит от принятой глубины и разносторонности индексирования документов, от среднего числа М дескрипторов в поисковом образе документа. При многословном поисковом образе документа и запрос также должен быть многословным. Если М = 10, то поиск по одному понятию никогда не даст R2 > 0,1 и система ничего не выдаст. В запрос придётся добавлять новые термины, как бы объясняя системе свою потребность. Если в предыдущем случае для увеличения количества выданных документов нужно удалять дескрипторы из запроса, то при критерии R2 наоборот следует запрос расширять.

Эти два описанных критерия релевантности можно усложнить учётом значимости дескрипторов для документа и для запроса, если этим дескрипторам в процессе индексирования присвоены весовые коэффициенты. Пусть в документе совпали дескрипторы № 1, 2, 3, …, k. Пусть этим дескрипторам пользователь присвоил веса n1, n2, n3, …, nk, а в документе они имеют веса m1, m2, m3, …, mk. Тогда в качестве критерия релевантности можно принять сумму произведений этих весовых коэффициентов: m1n1+ m2n2 + m3n3 + …+ mknk, или как кратко пишут математики:

k

mi ni

i=1

Однако для того чтобы релевантность не зависела от масштабов присвоения коэффициентов, эту величину следует взять относительно общей суммы всех коэффициентов дескрипторов в запросе ni и в документе ∑ mi:

k k k

R3 = (∑ mi ni) ( ∑ mi · ni ) ,

i=1 i=1 i=1

где в знаменателе суммы берутся по всем дескрипторам поискового образа документа (ПОД) и поискового образа запроса (ПОЗ) соответственно.

Для учёта того, что наличие в поисковых образах документа и запроса свидетельствует об определённой степени рассогласования тематики документа и информационной потребности пользователя, в формулу критерия выдачи следует ввести члены, уменьшающие его при наличии несовпадающих терминов:

k k k

R4 = (∑ mi ni — ∑ mk · nk ) ( ∑ mi · ni ) ,

i=1 i=1 i=1 ПОД ПОЗ

где индексами k обозначаются веса дескрипторов документа mk, которые не находят соответствия в запросе и веса дескрипторов запроса nk, которые не находят соответствия в документе. Величина R3 всегда находится в пределах от 0 до 1, а R4 изменяется от +1 до –1. Естественной границей релевантности можно считать R4 = 0, т. е. суммарный вес отсутствующих дескрипторов не превосходит суммарный вес совпадающих дескрипторов.

Снижение релевантности может также выражаться не путём вычитания весов несовпадающих дескрипторов, а путём деления суммы весов совпадающих на сумму весов несовпадающих дескрипторов. При этом формула может быть упрощена, так как при этом она автоматически приобретает форму, не зависящую от масштабов присвоения весов и глубины индексирования:

k

R5 = (∑ mi ni) ( ∑ mk · nk ) .

i=1 ПОД ПОЗ

Величина R5 может быть как меньше, так и больше 1. Значение R5 = 1 является естественной границей релевантности.

От конкретной формулы расчёта релевантности, принятой в информационной системе, эффективность поиска зависит в сильной степени.

В одной из американских информационных систем Министерства обороны ещё в 50-х годах прошлого века была реализована изощрённая процедура расчета релевантности, при которой для каждого термина запроса просматривался весь имеющийся массив документов (ПОД) и подсчитывалась частота совместной встречаемости данного термина со всеми другими. Далее для каждого термина составлялся упорядоченный список (профиль) терминов совместно встречающихся чаще, чем в среднем (связанные термины). Далее из всех профилей терминов запроса выбираются общие для всех них. С отобранными терминами процедура повторяется. На основе частоты совместной встречаемости терминов этого списка вычисляется их вес (чем больше связанность, тем выше вес). Наконец на основе этих весов рассчитывался показатель релевантности аналогичный R3.

Подобные сложные расчёты статистики распределения терминов в документах имеют назначение как-то выявить смысловые связи слов. Однако возникает вопрос: «Зачем заставлять машину выяснять то, что человеку ясно заранее?». Смысловые связи слов можно прямо заложить в машину в виде информационно-поискового тезауруса, о чём мы уже говорили. Эта идея впервые была реализована в практической информационно-поисковой системе, видимо, в нашей стране в ИПС «Пусто–непусто», разработанной ВИНИТИ и внедрённой в ЦНТИ «Информэлектро». Ведущие разработчики – В. М. Чернявский, Э. С. Берншнейн и Д. Г. Лахути1.

Такое, довольно странное название системы «Пусто–непусто» обусловлено принятым в ней критерием релевантности. Он определялся соотношением наполненности четырёх множеств:

М1 - множество дескрипторов, совпадающих в ПОД и ПОЗ;

М2 - множество дескрипторов ПОД, родовых для дескрипторов ПОЗ.

М3 - множество дескрипторов ПОД, видовых для дескрипторов ПОЗ;

М4 - множество дескрипторов ПОД, не связанных с дескрипторами ПОЗ (поискового образа запроса).

По соотношению пустоты и наполненности этих множеств можно ранжировать и выбирать конкретный критерий выдачи документов. Наиболее вероятна релевантность документа, если все его дескрипторы совпадают с запросом:

М1

М2

М3

М4

совпадающие

родовые

видовые

посторонние

+

0

0

0

Столь же вероятна релевантность, если в документе есть также видовые дескрипторы (может быть наряду с родовыми):

+

0

0

0

+

+

0

0

Эти документы составляют первый эшелон выдачи. Если же в документе есть только видовые дескрипторы, то это может значить, что в нём идет речь только о части понятий, интересующих пользователя. Документы с заполненным только М3

0

0

+

0

составят второй эшелон выдачи.

В том случае, когда в документе представлены обобщающие (родовые) понятия, это может означать, что речь там идёт об общих вещах, а конкретно интересующее пользователя понятие упоминается только как частность. Документы с заполненным М2 составляют третью очередь выдачи.

+

+

0

0

0

+

0

0

0

+

+

0

Документы, содержащие посторонние дескрипторы (М4 ≠ 0) в той системе решено было не выдавать вовсе, хотя и они могли содержать полезную информацию.

Общая таблица эшелонов выдачи такова:

Эшелон

М1

М2

М3

М4




совпадающие

родовые

видовые

посторонние




+

0

0

0

Первый

+

0

0

0




+

+

0

0

Второй

0

0

+

0




+

+

0

0

Третий

0

+

0

0




0

+

+

0


Важно в этом примере не то, какой именно был выбран показатель соответствия, а то, что для его определения использованы знания логических связей понятий, заложенные в систему и представляющие там некоторую модель предметной области, в которой действует система. Наличие такой модели является необходимым условием интеллектуального подхода системы к своей задаче. На пути развития этой идеи прогнозируется дальнейший прогресс в разработке автоматизированных систем вообще, и информационных систем в частности.

Характерной особенностью системы «Пусто-непусто» является эшелонированная выдача: сначала выдаётся документ с наивысшей релевантностью, а затем документы в порядке снижения вычисленного для них критерия релевантности. Это стало стандартом для современных информационных систем; они не отсекают документы с малой степенью релевантности, а предлагают пользователю сначала получить высокорелевантные документы и продолжать знакомство с выдачей, пока он не удовлетворить информационную потребность или пока не обнаружит, что в последующих документах нет пертинентной информации. При этом пользователь как бы сам устанавливает требуемый критерий релевантности в процессе диалога с системой.

3. Полнота и точность поиска


До сих пор мы говорили о том, как система оценивает полезность того или иного документа для пользователя, а теперь остановимся на том, как пользователь может оценить полезность системы для себя. Вообще-то эффективность системы для заказчика определяется как её техническим качеством, так и экономическим – стоимостью, в обратно пропорциональной зависимости. Но мы здесь будем говорить чисто о технической эффективности.

Степень технической эффективности может быть определена сравнением реальной действующей системы с идеальной моделью. Идеальная модель может быть определена (как это было сделано основоположником научно-технической информатики К. Муэрсом) так: Это система, которая из документального фонда выдаёт ровно те и все те документы, которые бы отобрал сам пользователь, если бы он мог внимательно прочитать каждый из них. В этом определении, казалось бы абсолютно ясном, при внимательном обсуждении оказывается не ясным главное слово: «Что значит отобрал бы»? Отбирают документ для того, чтобы ознакомиться с ним. Но если пользователь «их внимательно прочитал», то значит он их уже всех «отобрал». А если считают, что «отбор» имеет целью получение полезной для дела информации, то это зависит от конкретного дела, и заранее определено быть не может. Это сильно снижает ценность определения эффективности систем, которое как раз и нужно определять прежде «дела», когда идёт речь о приобретении, внедрении или разработке системы. «До дела» можно определить только эффективность относительно технической релевантности, а «в ходе дела» пользователь судит о системе по её реальной пертинентности, которая заведомо ниже.

Так или иначе, соотношение множества реально выданных документов Мр с множеством идеальной выдачи Ми характеризуется следующими подмножествами (см. рис. 15.2):

А – документы, реально выданные системой и входящие в желаемую выдачу

А = Мр ∩ Ми

В – документы, выданные системой, не входящие в желаемую выдачу

В = Мр ∩  Ми

С – документы, не выданные системой, но входящие в желаемую выдачу

С =  Мр ∩ Ми

D – документы, не входящие ни в реальную, ни в желаемую выдачу

D =  Мр ∩  Ми

(Знак  здесь означает дополнение множества до полного объёма документов и читается как отрицание «не»).

В идеальном случае Мр= Ми = А, В = С = Д = 0


Рис. 15.2. Соотношение реальной и идеальной выдачи





Мр(выдано) Ми(релевантно)



Реальный случай может характеризоваться соотношением числа документов в этих множествах. na - число документов во множестве А, nb - число документов в В, nc - число документов в С, nd - число документов в D.

Наиболее популярны два отношения, это:

- Коэффициент точности Т = na/(na+nb) - отношение числа релевантных документов в выдаче к общему объёму выдачи.

- Коэффициент полноты П = na/(na+nc) - отношение числа релевантных документов в выдаче к общему числу релевантных документов в массиве.

Множество В, содержащее документы выдачи, не соответствующие запросу, называется шумом (информационный шум). Относительное количество шумовых документов в выдаче Ш = nb/(na+nb) называется коэффициентом шума. Ш + Т = 1.

Множество С, содержащее релевантные документы, не выданные пользователю, называется потерями. Отношение числа «потерянных» документов nc к общему числу релевантных документов в массиве может быть названо коэффициентом потерь, или коэффициентом молчания М = nс/(na+nc).

Коэффициенты потерь и шума не являются самостоятельными показателями эффективности поиска. Они однозначно связаны с коэффициентами полноты и точности: Ш = 1 – Т , М = 1 – П .

Очевидно, что чем выше коэффициенты полноты и точности, тем эффективность поиска выше. При работе с какой-либо информационной системой мы можем получать в разных случаях выдачи с разными значениями этих показателей. На один запрос система может ответить лучше, на другой – хуже. В случае, когда в выдаче окажутся все релевантные документы поискового массива и в ней не будет ни одного шумового документа, полнота и точность достигают своего наивысшего значения равного 1. В противоположном случае, когда в выдаче не будет ни одного релевантного документа, а выданные документы окажутся шумовыми, коэффициенты П и Т будут равны 0. В остальных случаях значения коэффициентов полноты и точности находятся в диапазоне от 0 до 1. Но конкретные величины П и Т в каждом акте поиска могут быть различными. Поэтому по одному поиску нельзя судить об эффективности системы в целом. Для этого вычисляют среднее арифметическое показателей П и Т для большого числа поисков по типичным запросам. Такие усреднённые коэффициенты П и Т колеблются между 0 и 1, никогда не достигая своих предельных значений. Коэффициент полноты П характеризует вероятность того, что некоторый релевантный документ в массиве будет выдан в ответ на запрос. Коэффициент точности Т характеризует вероятность того, что некоторый документ в выдаче окажется релевантным. Часто величину коэффициентов выражают в процентах, умножая их расчётные относительные величины на 100.

Следует заметить, что полнота и точность поиска зависит не только от системы, но и от типа запросов. По одним типам запросов система может проводить поиск лучше, а по другим – хуже. Также эффективность может зависеть от представления о реальной потребности в получении той или иной информации. Так что при указании характеристик системы следует указывать условия проведения испытаний и характер запросов, на основании которых эти характеристики были вычислены.

Полнота и точность являются независимыми характеристиками информационной системы. Невозможно найти метод расчёта коэффициента П по заданному Т и наоборот. Тем не менее существует эмпирически выявленные ограничения на эти показатели у практически работающих систем. Если система плохо сконструирована, то её полнота и точность могут быть как угодно малыми; здесь никакого ограничения нет. Если же искусственно сформировать такую систему, которая будет содержать только документы, релевантные относительно всех запросов определённого типа, и которая будет грубо выдавать весь свой массив в ответ на каждый запрос, то мы обнаружим в этом случае стопроцентную полноту и точность: П = Т = 1. Но в практически интересных случаях такое положение не возможно. Ни полнота, ни точность реальной информационной системы никогда не достигают 100%. Более того, если в имеющейся информационной системе путём изменения условий её работы или критерия выдачи стараемся повысить один из этих показателей, то другой неизбежно падает. Это наглядно видно в случае эшелонирования выдачи. Если мы ограничиваем выдачу первым эшелоном, содержащим документы с наибольшим априорным показателем релевантности, то среди них действительно окажется достаточно много реально релевантных и достаточно мало фактически шумовых документов, т. е. точность Т будет высокой. Но в этом эшелоне не будет ряда документов с меньшим показателем релевантности, но реально полезные пользователю. Попытка получить эти документы, приняв в выдачу следующие эшелоны документов, приведёт к повышению полноты П, но при этом в выдачу попадёт много низкорелевантных документов, которые пользователем будут отсеяны как шумовые, т. е. снизится показатель точности Т.

Соотношение полноты и точности характеризуется обратной зависимостью; оно может быть показано на следующем типичном для известных систем графике.

П(%)

90




70


1 2 3 4

50



Т1 а1

П1
30


10

0


0 10 30 50 70 90 Т (%)

Рис 15.3. Зависимость между достижимыми показателями П и Т.

Здесь на координатных осях отложены значения коэффициентов полноты П и точности Т в процентах, а точки четырех кривых показывают значения коэффициентов П и Т, свойственные четырём разным информационным системам. Так точка а1 показывает, что система «1» в режиме, обеспечивающем 40% точности выдаёт только 30% релевантных документов. Это считается не очень хорошим показателем. Система «2» при той же точности выдаёт около 80%, а система «3» - около 90% релевантных документов, имеющихся в поисковом массиве. Чем выше проходит график показателей системы, тем её эффективность выше. Но крайние точки этих графиков практически недостижимы; реальные системы не выходят за пределы, приблизительно указанные на рис. 15.3 пунктирным квадратом.

И полнота и точность поиска показывают степень удовлетворённости пользователя работой системы. Но эти коэффициенты не могут ответить на вопрос, какая система лучше – та, что обеспечивает большую полноту, или та, что обеспечивает большую точность. Для интегральной оценки пользуется популярностью показатель эффективности Э+ = П + Т, равный сумме коэффициентов полноты и точности. Считается, что система показывает неплохие результаты, если этот показатель приближается к 1, а если он превосходит 1, то система – превосходная. При настройке информационной системы на максимальную полноту или на максимальную точность величина Э+ определяется в основном тем коэффициентом, на максимум которого система настраивается. На основании показателя Э+ можно сделать вывод, что система «1» не очень хороша, поскольку в средней части диапазона работы он принимает значение около 70%, в то время как для остальных систем «2», «3», «4» достигает значений около 100% … 115% … 130% соответственно.

Имеет смысл и показатель эффективности Э = П  Т, равный произведению коэффициентов полноты и точности. Он позволяет оценить действие системы в центре диапазона работы, где для эффективной системы он должен принимать значения около 0,5. В нашем примере это выполняется для системы «4». Для систем «1», «2», «3» показатель Э равняется примерно 0,1 … 0,2 … 0,3 соответственно.

Показатели полноты и точности информационной системы не учитывают одно важное обстоятельство – объём поискового массива. Очевидно, что отыскать необходимые документы среди большого числа ненужных гораздо труднее, чем в том случае, когда их в массиве большинство. Для оценки способности системы отсеивать ненужные документы вводят коэффициент селективности (специфичности) S, равный отношению числа невыданных нерелевантных документов к общему числу нерелевантных документов в массиве.

S = nd / (nd + nb),

где nd - число документов в незакрашенной области множества D на рис. 15.2.

Коэффициент S принимает максимальное значение S = 1 при отсутствии в выдаче шумовых документов, т. е. когда Т = 1, а Ш = 0. В этом он сходен с коэффициентом точности, но его величина зависит также от характера поискового массива. При одной и той же точности S тем выше, чем меньше в массиве релевантных документов. По-видимому коэффициент селективности наиболее объективно оценивает работу самого механизма информационной системы.

Недостатком коэффициента селективности, а также коэффициента полноты является то, что в практически важных случаях мы их не можем определить с достаточной уверенностью, поскольку мы без сплошного просмотра огромных массивов не знаем числа невыданных релевантных документов nc. С неизбежной погрешностью нам может быть известно лишь относительное содержание релевантных документов в массиве t = (na+nc)/N = (na+nc)/(na+nb+nc+nd), которое можно опытным путём определить как вероятность получения релевантного документа при выборе наудачу документов из массива. Тогда величина nc может быть определена через вероятность t:

nc = N t – na,

где величина поискового массива N часто бывает известна, и интересующие нас коэффициенты принимают вид:

S = (N (1–t)– na – nb) / (N(1–t) – na),

П = na / N t.

К сожалению и этот способ вычисления показателей эффективности не всегда срабатывает. Так, мы не можем оценить объём поискового массива Интернета. Поэтому для поисковых машин в сетях показатели полноты и селективности поиска остаются неопределёнными.

Что же касается показателя точности, то и он требует соотнесения с общим характером поискового массива. Работу информационной системы характеризует не столько сама точность, сколько улучшение точности по сравнению со случайным выбором документов. Для оценки этого можно воспользоваться «коэффициентом уточнения» У = Т/t , равным отношению коэффициента точности к вероятности случайного документа в массиве оказаться релевантным. Иными словами, У показывает насколько концентрация релевантных документов в выдаче превосходит концентрацию их в исходном массиве.

Применяются и другие коэффициенты, учитывающие относительную важность выдачи релевантных и нерелевантных документов, но они имеют сугубо субъективный характер и применимы только к конкретным системам в заранее оговоренных ситуациях. Мы их здесь рассматривать не будем.


1 Бернштейн Э., Лахути Д., Чернявский В. Вопросы теории поисковых систем. – М.: ВНИИЭМ, 1962.