Решить задачу информационного поиска это значит найти не реальные
объекты, а объекты в некоторой информационной системе: страницы в
интернете, записи в базе данных или файлы на компьютере. Какие
методы позволяют делать это быстрее и эффективнее, рассказывает
специалист помашинномуобучениюСтанислав Протасов.Инвертированный
индекс и поиск по вторичным ключамПеред нами стоит задача
обнаружить конкретный объект, чей идентификатор нам известен, или
выполнить поиск по некоторым ограничениям: например, задать в
интернет-магазине диапазон цен от 3000 до 5000 рублей или взять
некоторый объект и поставить условие, что все искомое должно быть
на него похоже. Тогда это называется задачей ранжирования:
поисковик будет выдавать по степени убывания похожести объекты до
тех пор, пока мы не посчитаем, что дальше идут уже
неподходящие.Одним из старых подходов к решению задачи
информационного поиска является построение инвертированного
индекса. В научно-популярных книгах или учебниках часто встречается
такое необычное оглавление: вместо по порядку идущих глав написаны
термины из предметной области, а рядом с ними проставлены номера
страниц, на которых эти термины встречаются. Почему такой подход
удобен? Потому что вы можете открыть книгу и посмотреть, что в ней
рассказывают о каком-то явлении. Этот подход в одном из томов
Искусства программирования Дональд Кнут описывал еще в 1970-е годы,
и он назвал его поиском по вторичным ключам.С первичным ключом мы
имеем дело, когда каждому объекту сопоставлено только единственное
значение, как, например, номер паспорта у человека. А вторичный
ключ в терминологии Дональда Кнута значит, что мы можем обладать
некоторым важным дифференцирующим свойством, но не гарантируем его
уникальность. В случае с людьми это, скажем, имя: могут совпадать
имена, хотя в небольшой компании имя все же является
идентификатором.Дональд Кнут предлагает следующий способ решения
задачи информационного поиска. Нам нужно найти какой-то объект, и
мы ищем его по набору ограничений, то есть набору параметров, и эти
параметры дискретные, как наши имена, или категориальные, благодаря
которым можно сократить количество объектов, которые подпадают под
определенную категорию. Если поиск осуществляется по таким ключам,
то здравой идеей было бы не искать по всей коллекции объектов,
проверяя каждый на наличие этого ключа, а взять уже некоторую
выборку.Суть построения инвертированного индекса заключается в том,
что берется некоторое значение ключа, например имя человека, и все,
что обладает этим свойством, собирается в список (posting list) в
нашем случае это некоторая коллекция объектов: всех Андреев относим
в одну группу, всех Станиславов в другую и так далее. И когда мы
будем искать объекты, которых зовут Станислав Протасов, мы возьмем
корзинку со Станиславами и будем прочесывать только ее. Это очень
сильно сокращает время поиска.Наиболее понятная постановка задачи
поиска по вторичным ключам полнотекстовый поиск. Представьте себе,
что у вас есть очень большая коллекция текстов и вы ищете не по
метаинформации, то есть заголовкам, авторам или длине этих текстов,
а по содержимому. Это значит, что вам нужна или конкретная
подстрока в этом тексте, или конкретное слово: вы ищете те тексты,
в которых заданная подстрока встречается.Можно использовать простой
перебор: берете текст и проверяете его на вхождения. Для этого
существуют алгоритмы Кнута Морриса Пратта, Ахо Корасик, Бойера
Мура, но они линейно зависят от длины коллекции. И если у вас 100
текстов и вы можете проверить их за 100 миллисекунд, то миллион
текстов вы будете проверять уже миллион миллисекунд. К сожалению, с
этим поделать ничего нельзя. Вам нужен подход, который будет
быстрее, чем простая проверка всей коллекции текстов.Что с этим
можно сделать? Слова используются в качестве вторичных ключей. Мы
собираем все слова, которые используются в нашей коллекции текстов,
это будет называться лексиконом, и, что удивительно, таких слов
будет довольно мало в рамках компьютерных систем, порядка десятков
тысяч объектов (например, когда я делал это для романа Война и мир,
там было порядка 30 000 уникальных слов, как русских, так и
французских). Для каждого из этих слов мы сможем составить
коллекцию, где они встречаются. В случае с романом Война и мир это
будет страница, а если мы имеем дело с базой данных, то это будет
номер записи, в которой есть упоминание конкретного
слова.Лемматизация и стеммингЕсть такое понятие, как стоп-слова
(stop-word) слова, которые встречаются в любом тексте. Чаще всего
это предлоги, союзы, указательные местоимения. Они никак не
помогают уменьшить пространство поиска: если мы составим коллекцию
всех документов, содержащих это слово, то в ней будут все документы
вашей базы данных. Такие слова обычно выбрасывают, обычно их
несколько десятков в интернете можно найти наиболее популярные
подборки, которые используются учеными и программистами.Существует
также подход, касающийся вариативности языка. В русском языке есть
род, падеж, время, и все эти вещи влияют на форму слова. Часто
бывает так, что запрос пользователей на самом деле не очень точный,
и поэтому иногда хорошей практикой было бы избавиться от
вариативности. Это делают двумя способами. Первый из них называется
лемматизация (lemmatisation): слово приводится к начальной форме.
Если у нас была фраза мама мыла раму, то в начальной форме это
будет мама мыть рама. Второй способ стемминг (stemming; англ. stem
основа), то есть оставление только основы слова, и для
словосочетания мама мыла раму это будет мам мыл рам. Оба варианта
убирают вариативность и оставляют только сущностную часть слова.
Теперь слов становится еще меньше, даже Война и мир начинает
схлопываться на глазах.Теперь мы берем сочетание мама мыла раму,
которое будет поисковым запросом для нашей коллекции текстов,
приведем его к уменьшенной форме, для каждого слова выберем
коллекции документов, в которых оно встречается, и построим их
пересечение. Получается очень быстро, но дело в том, что такой
подход хорошо работает, когда у нас сопоставимое число слов и
объектов в каждой из корзинок, то есть атрибутированных к каждому
из слов документов, в которых встречается это слово. Но
представьте, что у нас 100 миллиардов объектов (например,
количество страниц в интернете), есть очень редкое слово, которое
встречается только в миллиарде документов, и есть слово, которое
встречается в 10 миллиардах документов, и нужно посчитать
пересечения этих двух корзинок. Это очень сложная операция, и
проблема здесь состоит в том, что размер лексикона не растет с
размером коллекции: вы набираете все больше и больше документов,
соответствующих конкретным словам, но размер словаря остается
прежним.Векторное представление текстаЧто можно сделать, чтобы
лексикон рос пропорционально размеру коллекций? Начиная с 1910-х
годов популярным стал подход к представлению текстов в виде
векторов некоторого набора чисел, описывающего объект. В таком
случае вектор будет такой же длины, что и наш лексикон, допустим,
30 тысяч нулей подряд. Мы заменяем нули единицами, если нужное нам
слово в тексте встречается. Но этот подход очень неэкономный,
поскольку представление текста может быть больше, чем оригинальный
документ.Однако благодаря модели Word2vec стало ясно, что многие
задачи, касающиеся текстов, можно решать с векторами размерности
порядка сотни: текст подается на вход нейронной сети Word2vec, и на
выходе получаем вектор длиной 100200 значений. Текст размером в
мегабайт теперь может весить 400 байт. Это гораздо удобнее и
компактнее. Самое интересное, что такие векторы часто имеют
различные алгебраические свойства, то есть тексты, которые
семантически между собой похожи, будут иметь похожие в некотором
метрическом пространстве значения. И то, что показывали авторы
модели Word2vec, это возможность кодировать отношения. Например,
отношение столицы и государства тоже описывается фиксированным
вектором: Москва относится к России так же, как Вашингтон к США.
Это очень полезное свойство, потому что получившиеся векторы лежат
в метрическом пространстве смыслов, и документ, который похож на
другой документ, имеет похожее векторное представление.Это свойство
позволило нам научиться использовать векторы для представления
документов. Что же делать с этим дальше? Введем такое понятие, как
кластеризация это разбиение множества объектов на непересекающиеся
подмножества. Алгоритмов кластеризации бывает очень много, но нас
интересуют те, что будут строить структуру, похожую на пчелиные
соты, то есть разбивать пространство на одинаковые, компактные,
стремящиеся к сферической форме подпространства, в которые будут
попадать примерно одинаковое количество документов. Один из
алгоритмов, который используется наиболее часто, это алгоритм
k-средних. Допустим, нам нужно k кластеров, и на выходе алгоритм
даст k кластеров, которые будут примерно одинаковые по размеру и в
идеале стремиться к сферичности, то есть иметь выпуклую форму и
описывать некоторое соседство объектов внутри этого кластера.Таким
образом, у нас есть векторное представление и кластеризованные
векторы. Теперь введем понятие кодового слова (code word) это
середина каждого кластера, и кодовой книгой (code book) будет
являться совокупность всех середин кластеров. Итак, у нас теперь
вместо слова есть кодовое слово, а вместо лексикона кодовая книга.
Но количество кодовых слов мы можем варьировать самостоятельно:
просто задаем некоторый параметр алгоритму и просим нагенерировать
50 тысяч слов, или миллион, или миллиард слов в зависимости от
поставленной задачи. После этого алгоритм сводится к следующему. Мы
берем фразу мама мыла раму, даем ей некоторое векторное
представление, состоящее, например, из 100 чисел. Затем находим
ближайшее к этому векторному представлению кодовое слово, и теперь
все фразы, что находятся внутри этой ячейки, являются соседними
исходной фразы соседними чаще всего в семантическом смысле, то есть
мы будем искать фразы, похожие по смыслу. Здесь у нас уже не точное
совпадение по подстроке, а именно семантическое совпадение. И
оказывается, что сейчас это даже более актуальная задача, нежели
просто поиск по подстроке.Чем хороши такие подходы? В них гораздо
больше параметров. Мы можем варьировать алгоритм кластеризации,
количество кодовых слов, комбинировать их с другими подходами,
разбивать многомерные векторы пополам и говорить, что каждый из них
будет в своем подпространстве, строить два индекса. Этот подход в
2010-х годах предлагали разработчики из Яндекса. Такие структуры
данных сейчас используются в передовых компаниях.
