Введение в Информационный Поиск Денис Турдаков ИСП РАН / ВМиК МГУ

О чем речь? Информационный поиск (information retrieval) это область компьютерных технологий, которая ставит своей целью поиск всех документов из данного множества, отвечающих условиям запроса пользователя

План Часть 1. Векторно-пространственная модель Часть 2. Обзор стратегий извлечения информации

Часть 1

Методы информационного поиска Векторно-пространственная модель (Vector Space Model) Вероятностные методы (Probabilistic Retrieval) Языковые модели (Language Models) Сети вывода (Inference Networks) Булева индексация (Boolean Indexing) Неявное семантическое индексирование (Latent Semantic Indexing) Нейронный сети (Neural Networks) Генетические алгоритмы (Genetic Algorithms) Нечеткая логика (Fuzzy Set Retrieval)

Векторно-пространственная модель (Vector Space Model) Вероятностные методы (Probabilistic Retrieval) Языковые модели (Language Models) Сети вывода (Inference Networks) Булева индексация (Boolean Indexing) Неявное семантическое индексирование (Latent Semantic Indexing) Нейронный сети (Neural Networks) Генетические алгоритмы (Genetic Algorithms) Нечеткая логика (Fuzzy Set Retrieval) Методы извлечения информации

Векторно-пространственная модель Идея: слова используемые в документе характеризуют этот документ Для каждого документа и запроса строится вектор терминов Расстояние между документами (и запросом) вычисляется как расстояние между векторами.

Мера близости Используется величина угла между векторами (скалярное произведение) Можно использовать любую монотонную функцию от угла

Вес терминов Некоторые термины могут быть более важными чем другие Веса терминов расставляются либо вручную, либо автоматически Редкие термины имеют больший вес

Используемые обозначения t = число различных терминов в коллекции документов tf ij = число вхождений термина t j в документ D i. Частота термина (term frequency) df j = число документов содержащих T j. Частота документа (document frequency) idf j =log(d/df j ), где d число всех документов. Инвертированная частота документа (inverse document frequency)

Автоматическая генерация весов Чем больше раз встречается термин в документе тем больший он имеет вес Чем больше раз встречается термин в коллекции документов тем меньший он имеет вес d ij = tf ij x idf j Коэффициент похожести (similarity coefficient) SC(Q,D i )= t j=1 w qj x d ij

Пример Q: gold silver truck D1: Shipment of gold damaged in a fire D2: Delivery of silver arrived in a silver truck D3: Shipment of gold arrived in a truck d = 3 idf: log(3/1)=0.477; log(3/2)=0.176; log(3/3)=0 Idf a = 0 Idf arrived = Idf damaged = Idf delivery = Idf fire =0.477 Idf in = 0 Idf of = 0 Idf silver = Idf shipment = Idf truck = Idf gold =0.176

Пример docidaarriveddamageddeliveryfiregoldinOfshipmentsilvertruck D1D D2D D3D Q SC(Q, D 1 ) = (0)(0) + (0)(0) + (0)(0.477) + (0)(0) + (0)(0.477) + (0.176)(0.176) + (0)(0) + (0)(0) + (0)(0.176) + (0.477)(0) + (0.176)(0) = (0.176) SC(Q,D2) = (0.954)(0.477) + (0.176) SQ(Q,D3) = (0.176) 2 + (0.176)

Особенности реализации Реализация векторно- пространнственной модели, а так же других стратегий извлечения информации, использует инвертированный индекс, чтобы избежать многократного сканирования всех документов

Модификации алгоритма Следующая формула считается хорошей для подсчета весов: Решена проблема: Если в запросе и документе совпал один термин, с высокой частотой (tf), то результат может стать «перекошенным»

Подсчет коэффициента похожести Чаще всего для подсчета коэффициента похожести используются Косинус угла: Мера Дайса (Dice) Мера Джаккарда (Jaccard)

Часть 2

Коротко о методах Векторно-пространственная модель (Vector Space Model) Вероятностные методы (Probabilistic Retrieval) Языковые модели (Language Models) Сети вывода (Inference Networks) Булева индексация (Boolean Indexing) Неявное семантическое индексирование (Latent Semantic Indexing) Нейронный сети (Neural Networks) Генетические алгоритмы (Genetic Algorithms) Нечеткая логика (Fuzzy Set Retrieval)

Вероятностные методы Вычисляется вероятность того, что термин появится в релевантном документе Эта вероятность считается для каждого термина коллекции Мера похожести между запросом и документом вычисляется как сочетание вероятностей для каждого совпавшего термина

Коротко о методах Векторно-пространственная модель (Vector Space Model) Вероятностные методы (Probabilistic Retrieval) Языковые модели (Language Models) Сети вывода (Inference Networks) Булева индексация (Boolean Indexing) Неявное семантическое индексирование (Latent Semantic Indexing) Нейронный сети (Neural Networks) Генетические алгоритмы (Genetic Algorithms) Нечеткая логика (Fuzzy Set Retrieval)

Языковые модели Статистические языковые модели – это вероятностный механизм для генерации части текста Для каждого документа коллекции строится модель Вычисляется вероятность того, что по документу можно сгенерировать запрос

Коротко о методах Векторно-пространственная модель (Vector Space Model) Вероятностные методы (Probabilistic Retrieval) Языковые модели (Language Models) Сети вывода (Inference Networks) Булева индексация (Boolean Indexing) Неявное семантическое индексирование (Latent Semantic Indexing) Нейронный сети (Neural Networks) Генетические алгоритмы (Genetic Algorithms) Нечеткая логика (Fuzzy Set Retrieval)

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

Коротко о методах Векторно-пространственная модель (Vector Space Model) Вероятностные методы (Probabilistic Retrieval) Языковые модели (Language Models) Сети вывода (Inference Networks) Булева индексация (Boolean Indexing) Неявное семантическое индексирование (Latent Semantic Indexing) Нейронный сети (Neural Networks) Генетические алгоритмы (Genetic Algorithms) Нечеткая логика (Fuzzy Set Retrieval)

Булева индексация Для использования в запросах булевых функций необходимо расширение булевской модели Каждому термину приписывается некоторый вес Этот вес используется для вычисления коэффициента похожести и ранжирования полученных результатов

Коротко о методах Векторно-пространственная модель (Vector Space Model) Вероятностные методы (Probabilistic Retrieval) Языковые модели (Language Models) Сети вывода (Inference Networks) Булева индексация (Boolean Indexing) Неявное семантическое индексирование (Latent Semantic Indexing) Нейронный сети (Neural Networks) Генетические алгоритмы (Genetic Algorithms) Нечеткая логика (Fuzzy Set Retrieval)

Неявное семантическое индексирование Предпосылка: одна и та же идея может быть описана разными словами Основная идея: найти термины описывающие семантику лежащую в основе документа Метод: Сингулярное разложение SVD (Singular Value Decomposition) Минус: большая вычислительная сложность

Сингулярное разложение SVD Строится матрица термин-документ А элемент (i,j): какое число раз термин i появляется в документе j SVD этой матрицы: U V T, где – диагональная матрица Элементы матрицы ранжируются и выбираются k максимальных, остальные обнуляются Соответственно уменьшается размерность матриц U и V (получаются U k и V k T ) Сравнение терминов осуществляется с помощью скалярного произведения строк в U k, документов – ск. произведения столбцов V k T.

Пример Q: gold silver truck D1: Shipment of gold damaged in a fire D2: Delivery of silver arrived in a silver truck D3: Shipment of gold arrived in a truck

Пример

D1 = ( ) D2 = ( ) D3 = ( )

Коротко о методах Векторно-пространственная модель (Vector Space Model) Вероятностные методы (Probabilistic Retrieval) Языковые модели (Language Models) Сети вывода (Inference Networks) Булева индексация (Boolean Indexing) Неявное семантическое индексирование (Latent Semantic Indexing) Нейронный сети (Neural Networks) Генетические алгоритмы (Genetic Algorithms) Нечеткая логика (Fuzzy Set Retrieval)

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

Коротко о методах Векторно-пространственная модель (Vector Space Model) Вероятностные методы (Probabilistic Retrieval) Языковые модели (Language Models) Сети вывода (Inference Networks) Булева индексация (Boolean Indexing) Неявное семантическое индексирование (Latent Semantic Indexing) Нейронный сети (Neural Networks) Генетические алгоритмы (Genetic Algorithms) Нечеткая логика (Fuzzy Set Retrieval)

Генетические алгоритмы Предпосылка: если найдена часть релевантных документов, то остальные тоже будут найдены Исходная популяция: Терминам запроса приписываются некоторым образом веса Вычисляется дистанция от запроса до всех документов и выбирается х релевантных Новые запросы (хромосомы) получаются с помощью мутации и скрещивания Выживают наиболее близкие к известным документам запросы

Коротко о методах Векторно-пространственная модель (Vector Space Model) Вероятностные методы (Probabilistic Retrieval) Языковые модели (Language Models) Сети вывода (Inference Networks) Булева индексация (Boolean Indexing) Неявное семантическое индексирование (Latent Semantic Indexing) Нейронный сети (Neural Networks) Генетические алгоритмы (Genetic Algorithms) Нечеткая логика (Fuzzy Set Retrieval)

Нечеткая логика Нечеткое множество: каждому элементу назначается степень принадлежности множеству Пример: «горячий чай» - C={0/0; 0/10; 0/20; 0,15/30; 0,30/40; 0,60/50; 0,80/60; 0,90/70; 1/80; 1/90; 1/100} Документ отображается на нечеткое множество. Булевские операции отображаются в операции над нечетким множеством Вычисляется степень принадлежности документа множеству, которая затем используется как коэффициент подобия

Что не попало в презентацию Вспомогательные методы для улучшения результатов 1.Обратная связь о релевантности 2.Кластеризация 3.Извлечение, основанное на частях документа (passage-based retrieval) 4.Разбор текста (стемминг, морфологический и грамматический анализ) 5.N-граммы 6.Тезаурус 7.Семантические сети 8.Регрессионный анализ

Что не попало в презентацию Использование нескольких языков (cross-language information retrieval) Вопросы эффективности реализации Извлечение информации из структурированных данных Параллельное извлечение информации Распределенное извлечение информации

Спасибо за внимание Презентация доступна на сайте Мой