Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
122 Таким образом, если в нескольких первых тактах, при не очень больших значениях индекса t процесс (5.62) действительно улучшает качество поиска (так как наряду с пользовательским запросом учитывается также фактор среды), то дальнейшее продолжение этого процесса при чрезмерно больших значениях индекса t приводит к резкому ухудшению качества поиска, так как результаты поиска при этом перестают зависеть от пользовательского запроса.
Чтобы не предать забвению пользовательский запрос ?((l), можно было рассматривать процесс
Л(0) = C?(0)
(0)
Q^ = CtAw+Q Am = CQw
A^=CQi0, qU+D _ cTAu)+Q(0)
который отличается от процесса (5.62) наличием слагаемого Qm собственно, и предотвращает забвение этого вектора, т.е. пользовательского запроса. Из (5.69) следует, что
! + CrC-I-(CrC)2+ ... + {стс)' |?'
(5.69)
что,
O'
,(Г)
.(О
С
(Ccyj
\ + стс+(стс)2 + ... +(сгс)'
,(O)
Формулу (5.71) можно переписать также как
і + ссг + (ссг)2+ ... +(CCr)'
1С) -
Q
1(0)
(0)
(5.70)
(5.71)
(5.72)
Рассмотрим функцию f(x) = (1- х). Для этой функции ряд Тейлора в окрестности точки л' = 0 (ряд Маклорена) имеет вид бесконечной суммы геометрической прогрессии:
Р(х) =} + X + X1 + ..., (5.73)
которая сходится к функции f(x) тогда и только тогда, когда имеет место Ul < 1. В силу теоремы Кэлли - Гамильтона отсюда следует, что если в (5.73) скалярную величину х заменить матрицей Z, то для сходимости уже матричного ряда
P(Z) = 1 +Z +Z2 + ... (5.74)
к функции /(Z) = (l -Z) необходимо и достаточно, чтобы все корни характеристического многочлена матрицы Z по модулю были меньше единицы [3, 9].
123
ГЛАВА 5 І'аким обра нім, соблюдение условия IXnI < 1
(5.75)
является необходимым и достаточным для того, чтобы и з формул (5.70) и (5.71) следовало
Q = lim Qu' = (I - С' cj G"", А = Iini Л1" = С( 1 - C7 с] ' Qa)
S-^tOQ \ I
(5.76)
(5.77)
Обратим внимание, что соблюдение условия (5.75) одновременно гарантирует отсу тствие у матрицы (1 - СТС) нулевого собственного значення, т.е. обратимость этой матрицы. Заметим также, что при соблюдении (5.75) из (5.72) следует
А
Iim Л'" = II
Il - CC
rY CQi"'
(5.78)
Из (5.76) 4- (5.77) следует, что при достаточно больших значениях t матрицы Q и Л являю тся решением системы уравнений
A = CQ
Q = CT A +Qm' которую можно переписать в виде матричного уравнения
'/0 и о '/0 + Г о N
?) I cr Oj я. Qm,
(5.79)
(5.80)
К этому уравнению мы пришли путем изучения поведения процесса (5.69) при достаточно больших г. Именно такое уравнение постулируется Сэлтоном Г. при рассмотрении линейного ассоциативного поиска, где в качестве предположения приводится матричное уравнение [14J
(5.81)
Здесь DwT матрицы, учитывающие ассоциации тина "документ -документ'' и ' термин - термин". Если в (5.81) принять D=On T = 0. т.е. априори пренебречь ассоциациями этих типов, то придем к полученной нами системе (5.80).
Следуе т особо подчеркнуть, что переход от системы (5.69) к (5.79) (как и, впрочем, от (5.79) к (5.69)) возможен лишь при соблюдении условия (5.75).
fA) Г D сЛ А ) о 1
— 1 +
?) C1 T У /
124 В заключение настоящего параграфа попробуем оценить правомочность использования матричных моделей документального поиска в том виде, в каком они существуют в настоящее время.
Выше мы уже говорили о том, что в матричных моделях документального поиска, включающих операцию умножения матриц, в качестве критерия подобия (близости) двух векторов фактически принимается значение пх скалярного произведения. Например, для оценки степени близости двух ш-мерных векторов, один из которых представляет пользовательский запрос, а другой - некоторый документ, но величине их скалярного произведения судят о степени соответствия (релевантности) данного документа пользовательскому запросу. Здесь т - число элементов во множестве терминов, т.е. рассматриваемые векторы по сути представляют соответствующие (в общем случае нечеткие) подмножества этого множества.
В другом случае речь идет об оценке степени близости двух /i-мерных векторов, представляющих соответствующие подмножества множества из п документов. Например, речь может идти о скалярном произведении двух векторов, один из которых представляет пользовательский запрос, сформулированный как нечеткое подмножество множества документов, а другой - некоторый термин, также представленный как некоторое подмножество этого множества.
Таким образом, когда говорят о стенени близости двух векторов размерности 2, подразумевается, что речь идет о близости двух подмножеств некоторого множества из z элементов. Этим обстоятельством мы будем пользоваться для оценки (там, где это возможно) правомерности, корректности тех или иных интуитивных соображений, лежащих в основе построения различных моделей документального поиска. В простейшем случае, когда осуществляется оценка близости двух бинарных z-мерных векторов, речь идет о степени близости двух обычных подмножеств, определенных на множестве из г элементов. Данный случай полностью характеризуется матрицей сопряженности этих подмножеств (рис. 5.3), где
