Поиск текстовой информации с помощью векторных представлений
Рассматриваются векторные представления текстовой информации на основе частот встречаемости слов и их последовательности, а также распределенные векторные представления, учитывающие семантическую близость слов. Представлены архитектура программной системы, разработанной для экспериментального исслед...
Збережено в:
| Дата: | 2005 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут програмних систем НАН України
2005
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/1311 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Поиск текстовой информации с помощью векторных представлений /И.С. Мисуно, Д.А. Рачковский, С.В. Слипченко, А.М. Соколов // Проблеми програмування. — 2005. — N 4. — С. 50-59. — Бібліогр.: 21 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859667571582697472 |
|---|---|
| author | Мисуно, И.С. Рачковский, Д.А. Слипченко, С.В. Соколов, А.М. |
| author_facet | Мисуно, И.С. Рачковский, Д.А. Слипченко, С.В. Соколов, А.М. |
| citation_txt | Поиск текстовой информации с помощью векторных представлений /И.С. Мисуно, Д.А. Рачковский, С.В. Слипченко, А.М. Соколов // Проблеми програмування. — 2005. — N 4. — С. 50-59. — Бібліогр.: 21 назв. — рос. |
| collection | DSpace DC |
| description | Рассматриваются векторные представления текстовой информации на основе частот встречаемости слов и их последовательности, а также распределенные векторные представления, учитывающие семантическую близость слов. Представлены архитектура программной системы, разработанной для экспериментального исследования алгоритмов поиска с помощью векторных представлений, и прототип системы поиска на базе веб-серверного подхода. Приводятся результаты сравнительного тестирования.
|
| first_indexed | 2025-11-30T11:36:08Z |
| format | Article |
| fulltext |
Інформаційні системи
© И.С. Мисуно, Д.А. Рачковский, С.В. Слипченко, А.М. Соколов, 2005
ISSN 1727-4907. Проблеми програмування. 2005. № 4 50
УДК 004.912 + 004.738.52
И.С. Мисуно, Д.А. Рачковский, С.В. Слипченко, А.М. Соколов
ПОИСК ТЕКСТОВОЙ ИНФОРМАЦИИ С ПОМОЩЬЮ
ВЕКТОРНЫХ ПРЕДСТАВЛЕНИЙ
Рассматриваются векторные представления текстовой информации на основе частот встречаемости
слов и их последовательности, а также распределенные векторные представления, учитывающие се-
мантическую близость слов. Представлены архитектура программной системы, разработанной для экс-
периментального исследования алгоритмов поиска с помощью векторных представлений, и прототип
системы поиска на базе веб-серверного подхода. Приводятся результаты сравнительного тестирования.
Введение
Интеллектуализация систем поиска
текстовой информации требует учета ее
смыслового содержания. Классические про-
блемы поиска документов – это синонимия
(одно и то же понятие может быть выра-
жено с использованием разных терминов –
синонимов) и полисемия (один и тот же тер-
мин может иметь различные значения в раз-
личных контекстах). Традиционно эти про-
блемы решают путем расширения запроса
семантически близкими словами из тезауру-
сов или из документов, возвращенных сис-
темой в ответ на запрос и помеченных поль-
зователем как релевантные [1].
Ручное конструирование лингвисти-
ческих ресурсов типа тезаурусов и онтоло-
гий (например, WordNet [2]) очень трудо-
емко. Поэтому привлекательны автоматиче-
ские методы получения и представления
семантической информации. Ряд таких ме-
тодов основан на использовании векторных
моделей [3 – 6], где информация о совмест-
ной встречаемости слов извлекается из
больших коллекций (корпусов) текстов и
фиксируется в так называемых семантиче-
ских или контекстных векторах. Сходство
контекстных векторов, вычисляемое как
скалярное произведение или расстояние,
принимают за меру семантической близости
слов. Из контекстных векторов формиру-
ются представления документов и запросов,
которые отражают не только набор состав-
ляющих их слов, но и их семантику (смысл).
Сходство таких представлений позволяет
системе найти документы, которые могут и
не содержать слов запроса, но соответст-
вуют запрашиваемой теме.
Векторные подходы близки к мето-
дам распределенного представления ин-
формации, развиваемым нами в рамках па-
радигмы ассоциативно-проективных ней-
ронных сетей (АПНС) [7]. Получение рас-
пределенных семантических представлений
текстовой информации, разработка систем и
сравнительное исследование таких пред-
ставлений в задаче поиска текстовых доку-
ментов позволят расширить спектр приме-
нений АПНС и создать более эффективные
поисковые системы вследствие учета се-
мантики.
1. Векторные и распределенные
представления текстовой информации
1.1. Векторные представления. Со-
временные методы векторного представле-
ния текстовой информации являются разви-
тием моделей векторных пространств VSM
(Vector Space Models), предложенных в [8].
В этих моделях компоненты текстов, такие
как слова, словосочетания, фрагменты тек-
стов, целые документы, представлены мно-
гомерными векторами. Элементы векторов
есть значения некоторой функции от час-
тоты совместной встречаемости компонен-
тов текстов и их контекстов. Степень сход-
ства между компонентами текстов q и d оп-
ределяется величиной сходства между их
векторами q и d. Обычно используется не-
которая монотонная функция угла между
векторами, например косинус cos(q,d), ко-
торый для нормированных векторов совпа-
дает со скалярным произведением (q,d).
Рассмотрим в качестве компонентов
текста слова, а в качестве контекстов – до-
кументы. Введем следующие обозначения:
w – количество уникальных слов в коллек-
ции документов;
Інформаційні системи
51
t – общее количество документов в коллек-
ции;
tfij – частота встречаемости слова wi в доку-
менте dj;
dfi – количество документов, содержащих
слово wi;
idfi = log(t/dfi) – обратная частота докумен-
тов, содержащих слово wi.
Построим матрицу A (размерностью
w×t) встречаемости слов в документах кол-
лекции. Элементы матрицы aij – "веса" слов
в документах. Часто полагают aij=tfij·idfi.
Ряд векторных представлений ком-
понентов текстов (документов и запросов)
можно рассматривать как проекции (транс-
формацию) векторов документов d или век-
торов запросов q в другое пространство.
Трансформация осуществляется с помощью
некоторой матрицы P, а сходство векторов в
новом пространстве также определяется как
скалярное произведение
simP (d,q) = (PTd)(PTq) = dT PPT q. (1)
Оригинальная модель VSM [1, 8] ос-
нована на предположении, что смысл всего
документа выражается смыслом используе-
мых в нем слов. Документы представлены
векторами – столбцами матрицы A, запросы
– векторами, составленными из слов за-
проса. Таким образом, для VSM модели
P=I, а сходство вычисляется как
simVSM(d,q) = (ITd)(ITq) = dTIIT q = dTq. (2)
Критика VSM (например, [4]) осно-
вывается на том, что в качестве ортогональ-
ного базиса векторного пространства ис-
пользуются слова, которые на самом деле
часто семантически зависимы. Для преодо-
ления этого недостатка была предложена
альтернатива в виде метода GVSM (Gener-
alized Vector Space Model – обобщенной мо-
дели векторного пространства [9]. Она ос-
нована на том, что A рассматривается не
только как представление документов с по-
мощью слов, как в VSM, но и как представ-
ление слов с помощью документов. Каждая
строка A отражает распределение слов по
документам. Два слова считают семантиче-
ски связанными друг с другом, если похожи
их распределения по документам. Сходство
запроса и документа в методе GVSM можно
представить как (P = A)
simGVSM(d,q) = (ATd)(ATq) = dTAATq. (3)
В схеме LSI (Latent Semantic Indexing
– латентное семантическое индексирование
[3]) полагается, что пространство с умень-
шенной размерностью, содержащее наибо-
лее значимые линейные комбинации изме-
рений первоначального пространства, дает
лучший базис для представления содержа-
ния документов. В основе LSI лежит проце-
дура SVD (singular value decomposition – де-
композиция по сингулярным значениям),
которая позволяет представить A как
A = UDVT, (4)
где D=diag(σ1,...,σr) – диагональная матрица
сингулярных значений, U=(u1,...,ur) и
V=(v1,...,vr) – матрицы w×r и t×r с ортонор-
мированными столбцами левых и правых
сингулярных векторов соответственно.
В LSI в качестве нового базиса для
редуцированного векторного пространства
выбираются k столбцов Uk (ортогональных
сингулярных векторов), соответствующих k
наибольшим сингулярным значениям.
Столбцы Uk являются линейными комбина-
циями документов. В [3] представлениями
слов предлагается считать соответствующие
строки матрицы UΣΣΣΣk. Сходство компонен-
тов текста находится после их проецирова-
ния в k-мерное пространство векторов-
столбцов матрицы Uk ≡ IkU
T (P = UIk,) как
simLSI (d, q) = (IkU
Td) (IkU
Tq) =
= dTUIk
2UTq = dTUIkU
Tq.
(5)
1.2. Распределенные представле-
ния. Для больших коллекций документов
полноразмерная матрица А оказывается
слишком большой для обработки и даже
хранения в оперативной памяти компью-
тера. Один из подходов к решению этой
проблемы основан на применении распре-
деленных представлений. В отличие от ло-
кальных представлений, где каждый ин-
формационный компонент данных пред-
ставлен элементом кодвектора, т.е. одним из
ортогональных измерений входного про-
странства, в распределенных представле-
ниях каждому компоненту данных соответ-
ствует N-мерный вектор со случайно сгене-
рированными элементами (см. [7]). В мно-
гомерном пространстве «почти ортогональ-
ных» измерений гораздо больше, чем орто-
гональных. Для ряда распределений эле-
ментов случайные векторы близки к орто-
гональным и достаточно хорошо аппрокси-
Інформаційні системи
52
мируют исходный базис. Если в качестве
текстовых компонентов рассматривать до-
кументы и N<t, то размерность w×N новой
матрицы S меньше исходной w×t:
S = AR, (6)
где R – матрица случайных векторов t×N.
Попарные углы между строками S (пред-
ставления слов) аппроксимируют углы ме-
жду строками A (см. также [10 – 13].
Матрицу S можно сформировать без
A в процессе последовательного пословного
прохода корпуса текстов (метод случайного
индексирования RI – Random Indexing, [5]).
При этом к строкам si матрицы S прибавля-
ются индексные векторы документов rj
(строки матрицы R), когда слово i встреча-
ется в документе j:
si = ∑j:w(i)∈t(j) rj aij, (7)
где aij – частота встречаемости слова i в до-
кументе j. Вычислительная сложность фор-
мирования S сравнима со сложностью фор-
мирования A и равна O(LM) или O(L), где L
– количество слов в корпусе; M – количе-
ство ненулевых элементов в r (обычно M
постоянно и составляет малую долю N).
Аналогично можно сформировать контек-
стные векторы, в которых в качестве кон-
текстов используются не документы, а сло-
ва в некоторой окрестности целевого слова
[6, 14, 15].
Получаемые таким образом распре-
деленные контекстные векторы имеют дей-
ствительные элементы, что усложняет их
обработку. Обработка векторов с дискрет-
ными (бинарными или тернарными) эле-
ментами намного более эффективна, а их
формат соответствует формату АПНС [7].
Поэтому предлагается использовать дис-
кретные контекстные векторы, которые мо-
гут быть получены применением пороговых
операций к элементам действительных век-
торов – как "исходной локальной" матрицы
А, так и матрицы распределенных контек-
стных векторов S. Пороговая операция
τ (x, θ+, θ–) над скаляром x дает скаляр y:
y =1, если x > θ+ ≥ 0;
y = –1, если x <θ– ≤ 0,
иначе y = 0.
(8)
Такая операция выполняется над
всеми элементами контекстных векторов,
образующих матрицы A или S. Значения
элементов вектора порогов θθθθ могут быть
одинаковыми для всех элементов вектора
(например, 0 при тернаризации c нулевым
порогом или подобранное значение порога
для обеспечения заданного числа ненулевых
элементов), или индивидуальными (напри-
мер, зависящими от среднего значения
E(xi)). Регулирование плотности ненулевых
элементов может также осуществляться с
использованием процедур контекстно-зави-
симого прореживания CDT [16].
Дискретные контекстные векторы
могут конструироваться и непосредственно
из частей индексных векторов:
ci = ∑j:w(i)∈t(j) qj ( rj , f(j)), (9)
где t(j) – контексты, в которых встречается
слово; rj – дискретные индексные векторы,
имеющие по M ненулевых элементов;
qj(rj,n) – вектор с n ненулевыми элементами,
полученный из rj с помощью процедуры
CDT [16]; f(j) – функция, регулирующая
представительство rj в ci. Например, её
можно определить как
f (j) = ent(ϕ (j)) + 1 при y < ϕ (j) – ent(ϕ (j)),
f (j) = ent(ϕ (j)) иначе.
(10)
Здесь ϕ (j) – действительная функция "важ-
ности" контекста; y – псевдослучайное чис-
ло из диапазона (0,1), фиксированное для
данного j. Например, ϕ (j) = M/L (где L –
общее количество контекстов) или с нели-
нейным учетом частот встречаемости слов
ϕ (j) = M(1+log aij) idfj / Σi ϕ (i). (11)
На заключительном этапе к с применяется
пороговая операция ci = τ (ci,θθθθ). При θθθθ = 0
суммирование в (9) эквивалентно дизъюнк-
ции.
Векторы документов и запроса для
поиска формируются суммированием кон-
текстных векторов слов. Возможно взвеши-
вание и нормирование, а также формирова-
ние дискретных векторов документов с по-
мощью операций, аналогичных (8) и CDT
[16]. Сходство документа и запроса нахо-
дится как (нормированное) скалярное про-
изведение их контекстных векторов.
2. Прототип поисковой системы
Для разработки и тестирования алго-
ритмов поиска на основе векторных пред-
ставлений создана экспериментальная поис-
ковая система. При ее разработке особое
внимание уделялось обеспечению гибкости
архитектуры, позволяющей легко добав-
Інформаційні системи
53
лять, модифицировать и сравнивать различ-
ные варианты алгоритмов. На основе объ-
ектно-ориентированного подхода разрабо-
таны библиотека классов С++ и набор мо-
дулей, выполняющих последовательность
обработки текстовой информации.
Система состоит из модулей форми-
рования контекстных векторов и собственно
модуля поиска. Обобщенная архитектура
приведена на рис. 1.
Процесс формирования контекстных
векторов можно разбить на 4 этапа:
(I) индексирование корпуса, (II) формиро-
вание матриц слова×документы и/или сло-
ва×слова, (III) формирование контекстных
векторов слов и матрицы скалярных произ-
ведений контекстных векторов слов. По
сформированной матрице производится по-
иск либо в режиме тестирования (IV), либо
в режиме он-лайн поиска.
Индексирование корпуса включает
формирование словаря и индексированного
файла корпуса, в котором слова заменены
на их индексы. Словарь может быть под-
вергнут фильтрации: удалению малоинфор-
мативных слов или слишком редких/частых
слов (and, or, …); обрезке слов по длине
(основой слова считаются первые 4,6,8…
букв) или выделению основ (например,
библиотекой morph А. Курсина).
На основе словаря и индексирован-
ного корпуса формируются матрицы слова×
документы и/или слова×слова, которые в
последующем используются для формиро-
вания контекстных векторов слов (см. разд.
1.2). Из контекстных векторов слов, с ис-
пользованием матрицы слова×документы
взвешенным суммированием и нормирова-
нием строятся векторы документов.
Несмотря на то что векторы доку-
ментов в большинстве случаев разрежен-
ные, нахождение сходства вектора запроса с
векторами всех документов является трудо-
емкой задачей (t>>w). Для ускорения пред-
варительно вычисляется матрица скалярных
произведений каждого слова с каждым до-
кументом. Тогда сходство запроса с каждым
из документов можно получить как сумму
ее строк, соответствующих словам запроса
(с выбранным взвешиванием и нормирова-
нием). Матрица не является разреженной и
требует большого объема дискового про-
странства для хранения. Однако создание
такой матрицы и организация эффективного
доступа к ее строкам позволяют значи-
тельно ускорить последующий процесс по-
иска.
Рис. 1. Архитектура поисковой системы
Реализован также прототип системы поиска
документов в режиме взаимодействия с
пользователем (режим он-лайн). Эта систе-
ма выполняет поиск по предварительно
проиндексированным коллекциям докумен-
тов. Система работает под управлением веб-
сервера MS IIS (Internet Information
Services), интерфейс пользователя реа-
лизован на Dynamic HTML с отображением
в веб-браузере.
Работа с контекстными векторами на
серверной стороне осуществляется с помо-
щью технологии программирования ASP
(Active Server Pages) и JScript, а также
СОМ-объектов, реализованных на С++.
СОМ-объекты осуществляют чтение сло-
варя, индексированный поиск вектора по
Інформаційні системи
54
слову, вычисление контекстного вектора
нескольких слов и коэффициента сходства
между двумя текстовыми фрагментами, по-
иск наиболее близких запросу документов,
произвольный доступ к документам в кол-
лекции. Диаграмма последовательности вы-
зовов, осуществляемых при взаимодействии
пользователя с системой поиска, приведена
на рис. 2.
Пользователь вводит запрос в окно
веб-браузера, который обращается к веб-
серверу MS IIS. Сервер выполняет про-
грамму на языке ASP/JScript, обрабаты-
вающую запрос с помощью вызовов COM-
объектов. Результаты поиска в виде HTML
передаются пользователю, который про-
сматривает их в браузере. Внешний вид ок-
на веб-браузера при работе с системой по-
иска представлен на рис. 3.
3. Экспериментальное исследование
3.1. Коллекции документов. В экс-
периментах по поиску использовались кол-
лекции MEDLARS, Cranfield, Time Maga-
zine [17], которые предназначены для ис-
следования поисковых систем и имеют
сформированные экспертами списки запро-
сов и документов, соответствующих каж-
дому запросу. Это позволяет численно оце-
нивать качество поиска по стандартным ме-
рам полнота-точность (см. разд. 3.2).
MEDLARS (Medical Literature Analy-
sis and Retrieval System) – коллекция анно-
таций к статьям биомедицинской направ-
ленности. Содержит 1033 документа сред-
ней длиной порядка 50 слов. Объем словаря
составляет порядка 12 тыс. слов. Заданы 30
поисковых запросов, содержащих в среднем
Сервер
IIS, ASP
СОМ-объект
поиска
запрос
результаты
Ранжиро-
вание
вывод
Пользо-
ватель
Рис. 2. Диаграмма последовательности вызовов при
работе системы поиска
Рис. 3. Пример работы макета программы поиска текстов
Інформаційні системи
55
по 10 слов, каждому запросу в среднем со-
ответствуют около 20 документов.
Cranfield (Cranfield University UK) –
коллекция аннотаций к статьям по аэроди-
намике. Содержит порядка 1400 документов
и 225 запросов.
Time Magazine – коллекция статей из
«Time Magazine». Содержит 425 документов
и 83 запроса.
Кроме того, использовалась коллек-
ция TASA (Touchstone Applied Sciences Asso-
ciation) [18] – тексты по литературе, биоло-
гии, экономике, промышленности, науке,
искусству, социологии и бизнесу, рекомен-
дованные для чтения в колледжах США.
Более чем 37 600 текстов, каждый из кото-
рых состоит примерно из 166 слов из сло-
варя в 94 000 слов, в сумме содержат более
чем 10 млн слов. Для этой коллекции нет
списка запросов с ответами.
3.2. Методика оценки результатов
поиска. Для численной оценки качества ра-
боты систем поиска применялась средняя
(интерполированная) точность (11-pt aver-
age precision) [8]. Определим полноту
recall=d/d1, точность precision=d/d2, где d –
количество найденных релевантных запросу
документов; d1 – количество релевантных
запросу документов; d2 – общее количество
возвращенных по запросу документов. Ме-
тодика вычисления 11-pt average precision
включает в себя следующие этапы:
(i) для каждого запроса получить ранжиро-
ванный список документов и для каждого
J=1,..., d2 из этого списка вычислить значе-
ние точности и полноты;
(ii) в каждом из 10 интервалов полноты ме-
жду 0%,10%,…,100% выбрать наибольшее
значение точности в качестве репрезента-
тивного значения левой границы интервала.
Для полноты 100% репрезентативной точ-
ностью будет либо точное значение, если
оно существует, либо ближайшее имею-
щееся. Если интервал пуст, «репрезентатив-
ная» точность равна нулю;
(iii) выполнить интерполяцию – в каждом
интервале в качестве репрезентативной точ-
ки выбрать максимальное значение точ-
ности в данном интервале или в интервале с
большим значением полноты;
(iv) построить (в соответствии с пп. i,ii,iii)
индивидуальные характеристики для всех
запросов, после чего усреднить репрезента-
тивные значения в точках с одинаковой
полнотой. Это и есть результирующая 11-
точечная характеристика системы поиска;
(v) усреднить все 11 значений и получить
число "11-pt average precision".
3.3. Поиск текстовой информации.
Ниже приведены примеры поиска с учетом
семантики слов, выполненного на коллек-
ции TASA.
Пример 1. Запрос: «hiroshima». Возвращен-
ные в результате VSM-поиска документы
содержат искомое слово, в то время как тек-
сты, возвращенные другими методами, не
содержат слова “hiroshima”, хотя в них речь
идет об атомной бомбардировке Хиросимы
и Нагасаки 1945 года и их последствиях.
Пример 2. Запрос: «vessel» (судно, посу-
дина, кровеносный сосуд). Возвращенные в
результате поиска по методам GVSM, RI и
RL тексты используют это слово в разных
значениях. Некоторые возвращенные тек-
сты не содержат «vessel», но в них гово-
рится о кровеносной системе и давлении
крови.
Пример 3. Запрос: "america". Результаты
поиска содержат несколько текстов, в кото-
рых это слово не встречается, но речь идет о
гражданской войне в Америке 1830 г., упо-
минается Thomas Jefferson и т.д.
Приведенные примеры показывают,
что поиск при учете семантической связи
слов посредством использования контекст-
ных векторов позволяет найти тексты на
тему запроса, не содержащие слов запроса.
В ряде случаев это также улучшает качество
поиска.
Средняя точность (см. разд. 3.2) по-
иска в разных коллекциях приведена в
табл. 1, а зависимость средней точности от
полноты для разных методов на коллекции
Medlars – на рис. 4. Применялись норми-
ровки матрицы частот A в позиционной но-
тации SMART [8]: l означает логарифмиро-
вание частоты (1+log tf); t – умножение на
idf; с – нормирование векторов документов
(строк матрицы A) к L2; n – отсутствие со-
ответствующего взвешивания или норми-
ровки. Например, nnn означает, что никаких
действий ни с матрицей, ни с векторами не
осуществлялось; ltc – использованы все три
процедуры. В экспериментах применялся
Інформаційні системи
56
единственный способ морфологической об-
работки – выделение первых 8 букв слова в
качестве базовой словоформы (tr=8).
Контекстные векторы RI формирова-
лись по (7) при N=2000, количестве ненуле-
вых элементов в индексных векторах n=p=5
(p и n, соответственно плюс и минус еди-
ниц), а векторы документов – суммирова-
нием полученных контекстных векторов.
Результаты по VSM/GVSM получены нахо-
ждением сходства запроса и документа ска-
лярным произведением их векторов (dotp), а
по контекстным векторам (CONTEXT) –
скалярным произведением (dotp) с возмож-
ным нормированием контекстных векторов
по L1, L2. Нотация lt2, lt3 означает, что к
контекстным векторам слов применялась,
соответственно, бинаризация и тернариза-
ция (8). Результаты с дискретизацией кон-
текстных векторов приведены в табл 2.
Поиск по GVSM превосходит VSM (улуч-
шение до 20%) для коллекции MED, пока-
зывая сравнимые результаты на TIME и
CRAN. Применение представлений, учиты-
вающих семантику посредством контекст-
ных векторов, дает результаты на уровне
GVSM (или на несколько процентов выше)
на всех трех коллекциях. Применение кон-
текстных представлений с дискретными
элементами дает результаты, сравнимые с
контекстными представлениями с действи-
тельными элементами, но обеспечивает
большие возможности повышения эффек-
тивности обработки вследствие сокращения
объема памяти и упрощения применяемых
операций.
Кривые средней точности поиска по
методам GVSM-ltc и RI-ltc с действитель-
ными векторами находятся рядом и выше
кривых других методов. Кривая средней
точности поиска по контекстным векторам
RI с дискретизацией проходит немного ни-
же, но также над кривыми других методов
при полноте больше 15%.
Исследовался также поиск с исполь-
зованием q-граммного представления тек-
Таблица 1. Средняя точность поиска в коллекциях MED, TIME, CRAN
MED TIME CRAN
VSM GVSM CONTEXT VSM GVSM CONTEXT VSM GVSM CONTEXT
tr=8 dotp dotp dotp L1 L2 dotp dotp dotp L1 L2 dotp dotp dotp L1 L2
nnn 0.45 0.54 0.23 0.55 0.54 0.42 0.39 0.14 0.36 0.48 0.26 0.21 0.03 0.27 0.28
ntn 0.51 0.68 0.36 0.66 0.67 0.58 0.62 0.20 0.55 0.64 0.35 — 0.08 — 0.42
lnn 0.50 0.53 0.20 0.56 0.56 0.51 0.46 0.10 0.49 0.53 0.34 0.25 0.03 0.28 0.29
ltn 0.54 0.69 0.32 0.66 0.68 0.62 0.67 0.16 0.67 0.69 0.40 0.42 0.06 0.44 0.46
nnc 0.50 0.55 0.26 0.57 0.55 0.57 0.43 0.14 0.47 0.52 0.37 0.23 0.04 0.27 0.28
ntc 0.54 0.69 0.42 0.67 0.67 0.68 0.66 0.25 0.63 0.67 0.41 0.41 0.08 0.41 0.43
lnc 0.53 0.54 0.23 0.56 0.56 0.64 0.45 0.11 0.52 0.55 0.40 0.26 0.03 0.29 0.29
ltc 0.55 0.70 0.37 0.67 0.69 0.68 0.66 0.18 0.65 0.69 0.42 0.42 0.06 0.44 0.45
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
0 1 2 3 4 5 6 7 8 9 10
Полнота
С
р
.
т
о
ч
н
о
с
ть
VSM nnn
VSM ltc
GVSM nnn
GVSM ltc
RI2000p5n5 ltc L2
RI2000p5n5 lt3c L2
VSM ql6 nnn
Рис. 4. Зависимость средней точности поиска от полноты для Medlars
Інформаційні системи
57
стовой информации. При таком представле-
нии в качестве признаков используются по-
следовательности из q элементов алфавита.
В отличие от обсуждавшихся выше методов
поиска VSM, GVSM, RI это позволяет
учесть не только наличие, но и последова-
тельность признаков (например, слов в тек-
стах).
При использовании в качестве эле-
ментов алфавита слов, при q=1 q-граммное
представление является аналогом представ-
ления bag-of-words (традиционный VSM).
Использовались комбинированные q-
граммные представления текстов, где век-
тор признаков содержал q-граммы длиной
от 1 до qmax с разными весами. Для схемы 1
взвешивание не применялось, для схемы 2
q-граммы длиной q∈{1, qmax} входили с ве-
сом wq=qmax–q+1, а для схемы 3 – с весом
wq=q. В табл 3 приведены результаты VSM-
поиска в трех коллекциях по ненормиро-
ванным (nnn) q-граммным векторам, полу-
ченным для tr=8.
Результаты показывают, что добав-
ление в представления текстов последова-
тельностей слов позволяет несколько улуч-
шить результаты поиска (на 6–15% при
qmax=2,3) по сравнению с VSM-nnn без учета
последовательности. Наилучший результат
наблюдается, когда последовательности
большей длины имеют больший вес в век-
торных представлениях (столбцы qwc3 для
всех коллекций).
Заключение
Проведено исследование векторных
и распределенных представлений слов в за-
даче поиска текстовых документов. Исполь-
зовались как "традиционные" представле-
ния (векторы, составленные из слов тексто-
вого фрагмента – запроса или документа),
так и представления, отражающие семанти-
ческую близость слов и текстов (основан-
ные на контекстных векторах).
Исследования показали, что приме-
нение распределенных представлений по-
зволяет сократить размерность контекстных
векторов и обойти сложности конструиро-
вания и обработки полной матрицы слова-
контексты, размер которой может быть
очень велик для больших текстовых масси-
вов. Использование бинарных и тернарных
контекстных векторов позволяет значи-
тельно сократить затраты памяти и вычис-
лительных ресурсов на их хранение и обра-
ботку на обычных компьютерах. Такие рас-
пределенные представления совместимы с
форматом данных в ассоциативно-проек-
тивных нейронных сетях [7]. Это позволяет
Таблица 2. Средняя точность поиска с дискретными контекстными векторами
MED TIME CRAN
CONTEXT CONTEXT CONTEXT
tr=8 dotp L1 L2 dotp L1 L2 dotp L1 L2
lt2n 0.05 0.60 0.61 0.07 0.61 0.70 0.02 0.25 0.43
lt2c 0.08 0.52 0.61 0.08 0.63 0.64 0.02 0.31 0.41
lt3n 0.21 0.61 0.63 0.09 0.65 0.70 0.03 0.38 0.40
lt3c 0.32 0.61 0.63 0.13 0.66 0.66 0.07 0.44 0.45
Таблица 3. Средняя точность поиска по q-грамным векторам
MED TIME CRAN
qmax словарь qwc1 qwc2 qwc3 словарь qwc1 qwc2 qwc3 словарь qwc1 qwc2 qwc3
1 10144 0,449 0,449 0,449 18247 0,417 0,417 0,417 6715 0,261 0,261 0,261
2 77329 0,466 0,454 0,477 129186 0,435 0,421 0,447 81883 0,296 0,272 0,306
3 157895 0,465 0,460 0,460 252613 0,437 0,425 0,460 194665 0,300 0,278 0,280
4 241687 0,461 0,461 0,445 378283 0,436 0,432 0,459 320562 0,298 0,285 0,242
5 327049 0,461 0,461 0,430 504914 0,436 0,433 0,449 452472 0,295 0,289 0,210
6 413618 0,459 0,461 0,429 632157 0,436 0,433 0,437 588197 0,289 0,291 0,198
7 501279 0,456 0,459 0,429 759907 0,436 0,433 0,435 726833 0,285 0,291 0,184
10 770557 0,450 0,457 0,431 1145820 0,436 0,433 0,434 1156554 0,275 0,292 0,176
15 1240027 0,446 — — 1797585 0,441 — — 1908175 0,256 — —
Інформаційні системи
58
использовать методы, предложенные для
обработки таких представлений в АПНС,
пополнить арсенал АПНС семантическими
представлениями, а также обеспечить эф-
фективную аппаратную поддержку в виде
специализированных вычислителей и ней-
рокомпьютеров [19].
Разреженные варианты представле-
ний с малым количеством ненулевых эле-
ментов являются нейробиологически реле-
вантными и дают возможность дальнейшего
повышения эффективности обработки (на-
пример, путем использования процедур, по-
строенных на обратном индексе). Рост эф-
фективности сильно зависит от формы
представления информации, применяемых
алгоритмов и аппаратных средств. Для
обычных компьютеров экономия памяти и
повышение быстродействия достигается за
счет использования 1–2 бит памяти для хра-
нения содержимого элемента дискретного
вектора вместо 64 бит для действительного.
При эффективной реализации специализи-
рованными аппаратными средствами логи-
ческих битовых операций, требующихся для
дискретных векторов, возможно дополни-
тельное повышение быстродействия по
сравнению с арифметическими операциями
с плавающей точкой, требующихся для дей-
ствительных векторов.
Разработан и реализован ряд прото-
типов систем формирования векторных
представлений текстовой информации, а
также поисковых систем, основанных на
них. Результаты, полученные с помощью
распределенных представлений, находятся
на уровне результатов локальных представ-
лений, но превосходят их по эффективности
и масштабируемости. Использование разра-
ботанных представлений текстовой инфор-
мации показало улучшение результатов до
20% по сравнению с обычным VSM-поис-
ком по словам запроса вследствие примене-
ния контекстных векторов слов и докумен-
тов.
В описанных схемах учитывалась
информация об относительном расположе-
нии слов. Это лишь малая часть структур-
ной информации, доступной в больших
коллекциях текстов. Для более полного вы-
явления семантики текста важно использо-
вать и другие структурные отношения, при-
сущие естественному языку. Выбранный
метод построения поисковой системы и
гибкость разработанной архитектуры по-
зволяют в дальнейшем перейти к более глу-
бокому смысловому анализу в процессе по-
иска (см. [20]).
Таким образом, проведенные иссле-
дования и полученные результаты создают
предпосылки и открывают перспективы для
создания новых информационных техноло-
гий и прикладных систем поиска информа-
ции с элементами учета семантики. По-
строение такого рода систем предполагается
осуществлять на основании компонентно-
ориентированного подхода [21].
1. Grossman D., Frieder O. Information Retrieval: Algo-
rithms and Heuristics. – Boston: Kluwer, 1998. – 255 p.
2. Miller G. Wordnet: a lexical database for english //
Communications of the ACM. – 1995. – № 11. – P. 39-
41.
3. Indexing by latent semantic analisys / S. Deerwester,
S. Dumais, G. Furnas, T. Landauer, R. Harshman. – J. of
American Society for Information Sciences. – 1990. – №
1(6). – P. 391-407.
4. Translingual information retrieval: learning from bi-
lingual corpora / Y. Yang, J. Carbonell, R. Brown,
R. Frederking. – Artificial Intelligence. – 1998. – № 103.
– P. 323-345.
5. Kanerva P., Kristoferson J., Holst A. Random index-
ing of text samples for Latent Semantic Analysis // 22nd
Ann. Conf. of the Cognitive Science Society. – U Penn-
sylvania: Erlbaum, 2000. – P. 1036.
6. Karlgren J., Sahlgren, M. From Words to Under-
standing // Foundations of Real-World Intelligence /
Y. Uesaka, P. Kanerva, H. Asoh (eds.) – Stanford: CSLI
Publications, 2001. – P. 294-308.
7. Куссуль Э.М. Ассоциативные нейроподобные
структуры. – Киев: Наук. думка, 1991. – 144 с.
8. Salton G. Automatic Text Processing: The Transfor-
mation, Analisys, and Retrieval of Information by Com-
puter. – Addison-Wesley, Reading, MA. – 1989. – 530
p.
9. Wong S., Ziarko W., Raghavan V., Wong P. On mod-
eling of information retrieval concepts in vector space //
ACM Transactions of Database Systems. – 1987. – № 2.
– P. 299-321.
10. Kaski S. Dimensionality Reduction by Random
Mapping: Fast Similarity Computation for Clustering //
IJCNN'98, Intern. J. Conf. on Neural Networks. – Pis-
cataway, NJ. – 1998. – 1. – P. 413-418.
11. Johnson W., Lindenstrauss J. Extensions of Lipshitz
mapping into Hilbert space // Contemporary Mathemat-
ics. – 1984. – № 26. – P. 189-206.
12. Indyk P. Algorithmic Applications of Geometric
Embeddings // FOCS-01. IEEE. – 2001.– P.10-35.
13. Charikar M. Similarity estimation techniques from
rounding algorithms // ACM Symp. on Theory of Com-
puting. – 2002. – P. 380-388.
14. Burgess C., Lund K. The dynamics of meaning in
Інформаційні системи
59
memory // Cognitive Dynamics / E. Dietrich,
A.B. Markman (eds.). – Mahwah, NJ: Lawrence Erl-
baum Associates. – 2000. – P. 117-156.
15. Caid W., Dumais S., Gallant S. Learned vector-space
models for document retrieval // Information Processing
and Management. – 1995. – 31(3). – P. 419-429.
16. Процедура связывания для бинарного распреде-
ленного представления данных / Д.А. Рачковский,
С.В. Слипченко, Э.М. Куссуль, Т.Н. Байдык. – Ки-
бернетика и системный анализ. – 2005. – № 3 –
С. 3-18.
17. Cornell University SMART text collections. –
ftp://ftp.cs.cornell.edu/pub/smart/
18. TASA text collection. –
http://lsa.colorado.edu/spaces.html
19. Нейрокомпьютеры и интеллектуальные роботы /
Н. Амосов, Т. Байдык, А. Гольцев, А. Касаткин,
Л. Касаткина, Э. Куссуль, Д. Рачковский. – Киев:
Наук. думка, 1991. – 272 p.
20. Гладун В., Величко В. Конспектирование естест-
венноязыковых текстов // 10 Intern. Conf, "Knowledge
– Dialogue – Solution" KDS'05. – 2005. – № 2. –
C.344-347.
21. Грищенко В.Н., Лаврищева Е.М. Компонентно-
ориентированное программирование. Состояние,
направления и перспективы развития // Пробл. про-
граммирования. – 2002. – № 1-2. – P. 80-90.
Об авторах
Рачковский Дмитрий Андреевич,
канд. техн. наук, ст. научн. сотр.
Мисуно Иван Семенович,
вед. инж.-программист
Слипченко Сергей Витальевич,
вед. инж.-программист
Соколов Артем Михайлович,
мл. науч. сотр.
Место работы авторов:
Международный научно-учебный центр ин-
формационных технологий и систем НАН Ук-
раины и МОН Украины
Просп. Акад. Глушкова, 40, Киев, Украина
Тел. +38 (044) 502 6341
E-mail: dar@infrm.kiev.ua
i.misuno@longbow.kiev.ua
slipchenko_serg@ukr.net
sokolov@ukr.net
|
| id | nasplib_isofts_kiev_ua-123456789-1311 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-11-30T11:36:08Z |
| publishDate | 2005 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Мисуно, И.С. Рачковский, Д.А. Слипченко, С.В. Соколов, А.М. 2008-07-25T15:24:32Z 2008-07-25T15:24:32Z 2005 Поиск текстовой информации с помощью векторных представлений /И.С. Мисуно, Д.А. Рачковский, С.В. Слипченко, А.М. Соколов // Проблеми програмування. — 2005. — N 4. — С. 50-59. — Бібліогр.: 21 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1311 004.912 004.738.52 Рассматриваются векторные представления текстовой информации на основе частот встречаемости слов и их последовательности, а также распределенные векторные представления, учитывающие семантическую близость слов. Представлены архитектура программной системы, разработанной для экспериментального исследования алгоритмов поиска с помощью векторных представлений, и прототип системы поиска на базе веб-серверного подхода. Приводятся результаты сравнительного тестирования. ru Інститут програмних систем НАН України Інформаційні системи Поиск текстовой информации с помощью векторных представлений Information retrieval with vector representations Article published earlier |
| spellingShingle | Поиск текстовой информации с помощью векторных представлений Мисуно, И.С. Рачковский, Д.А. Слипченко, С.В. Соколов, А.М. Інформаційні системи |
| title | Поиск текстовой информации с помощью векторных представлений |
| title_alt | Information retrieval with vector representations |
| title_full | Поиск текстовой информации с помощью векторных представлений |
| title_fullStr | Поиск текстовой информации с помощью векторных представлений |
| title_full_unstemmed | Поиск текстовой информации с помощью векторных представлений |
| title_short | Поиск текстовой информации с помощью векторных представлений |
| title_sort | поиск текстовой информации с помощью векторных представлений |
| topic | Інформаційні системи |
| topic_facet | Інформаційні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/1311 |
| work_keys_str_mv | AT misunois poisktekstovoiinformaciispomoŝʹûvektornyhpredstavlenii AT račkovskiida poisktekstovoiinformaciispomoŝʹûvektornyhpredstavlenii AT slipčenkosv poisktekstovoiinformaciispomoŝʹûvektornyhpredstavlenii AT sokolovam poisktekstovoiinformaciispomoŝʹûvektornyhpredstavlenii AT misunois informationretrievalwithvectorrepresentations AT račkovskiida informationretrievalwithvectorrepresentations AT slipčenkosv informationretrievalwithvectorrepresentations AT sokolovam informationretrievalwithvectorrepresentations |