Как я создал поисковую систему на основе глубокого обучения

Мы пользуемся поисковыми системами каждый день. Без них мы бы пользовались Интернетом совсем по-другому, и я даже не могу представить, каким бы он был.

Я решил попробовать создать свою собственную небольшую поисковую систему, используя глубокое обучение для получения результатов поиска.

Разбивка проблемы на части

Поскольку создание полноценной поисковой системы — очень долгая и дорогая задача, я решил, что моя поисковая система будет предназначена только для страниц Википедии (т.е. если задать поисковый запрос, она вернет все соответствующие ему страницы Википедии).

Создание поисковой системы состояло из 3 основных этапов:

  • Найти/создать базу данных страниц Википедии
  • Индексировать базу данных страниц
  • Эффективно сопоставить поисковые запросы со страницами в индексе.

Создание базы данных

Вместо того чтобы пытаться найти базу данных страниц Википедии в Интернете, я решил создать свою собственную, просто потому, что я хотел создать веб-гусеницу!

Что такое веб-краулер?

Вначале веб-краулеру дается несколько начальных URL-адресов для посещения. Затем они посещают эти URL и анализируют HTML, чтобы найти другие URL, которые они могут посетить. Все URL, которые они находят, добавляются в очередь, чтобы они могли посетить их позже.

Поисковые системы, такие как Google и Bing, используют веб-краулеры для пополнения своего индекса ссылок на сайты, чтобы они могли появляться в результатах поиска.

Поскольку большинство URL-адресов на страницах Википедии — это URL-адреса других страниц Википедии, все, что мне нужно было сделать, это написать простой, универсальный веб-краулер и скормить ему несколько начальных страниц Википедии.

import requests
import os
from tinydb import TinyDB
from html.parser import HTMLParser


db = TinyDB("results.json")

def get_host(url):
    while os.path.dirname(url) not in ["http:", "https:"]:
        url = os.path.dirname(url)

    return url

class Parser(HTMLParser):
    def __init__(self):
        super(Parser, self).__init__(convert_charrefs=True)
        self.url = ""
        self.urls = []
        self.meta_description = ""
        self.title = ""
        self.paragraph_content = ""
        self.paragraph = False
        self.set_description = False
        self.set_title = False


    def set_url(self, url):
        if url[-1] == "/":
            if os.path.dirname(url[:-1]) not in ["http:", "https:"]:
                url = url[:-1]
        self.url = url

    def handle_starttag(self, tag, attrs):
        if tag == "meta":
            for attr in attrs:
                if attr[0] == "name" and attr[1] == "description":
                    self.set_description = True

                if self.set_description:
                    if attr[0] == "content":
                        self.meta_description = attr[1]
                        self.set_description = False

        elif tag == "a":
            for attr in attrs:
                if attr[0] == "href":
                    link = attr[1]

                    if link:
                        if link[0] == "/":
                            link = get_host(self.url) + link
                            self.urls.append(link)
                        elif "http://" in link and link.index("http://") == 0:
                            self.urls.append(link)
                        elif "https://" in link and link.index("https://") == 0:
                            self.urls.append(link)

        elif tag == "p" and len(self.paragraph_content) < 100:
            self.paragraph = True

        elif tag == "title":
            self.set_title = True

    def handle_endtag(self, tag):
        if tag == "p":
            self.paragraph = False

    def handle_data(self, data):
        if self.set_title:
            self.title = data
            self.set_title = False
        elif self.paragraph:
            self.paragraph_content += data

    def clear(self):
        self.urls = []
        self.meta_description = ""
        self.title = ""
        self.paragraph_content = ""
        self.paragraph = False
        self.set_description = False
        self.set_title = False


def crawl(start_queue):
    parser = Parser()

    queue = start_queue
    seen_urls = []
    while len(queue) > 0:
        if queue[0] not in seen_urls:
            try:
                print (queue[0])

                page = requests.get(queue[0])
                parser.set_url(queue[0])
                parser.feed(page.text)


                db.insert({
                    "title": parser.title,
                    "description": parser.meta_description,
                    "content": parser.paragraph_content,
                    "url": queue[0]
                })

                seen_urls.append(queue[0])
                queue = queue + parser.urls
                parser.clear()
            except:
                pass

        queue = queue[1:]


crawl(["https://en.wikipedia.org/wiki/Music", "https://en.wikipedia.org/wiki/Cricket", "https://en.wikipedia.org/wiki/Football"])
Вход в полноэкранный режим Выход из полноэкранного режима

Каждый раз, когда краулер посещает страницу, он просматривает HTML на наличие тегов a и добавляет атрибут href в очередь.

Он также записывает заголовок страницы, находящийся между тегами title, первые 100 символов статьи страницы, просматривая содержимое тегов p и метаописание страницы (однако после просмотра я обнаружил, что ни одна из страниц Википедии не имеет метаописания!)

После сканирования страницы ее URL и записанные детали сохраняются в локальном JSON-файле с помощью TinyDB.

Я запускал краулер в течение нескольких минут и смог отсканировать около 1000 страниц.

Индексирование базы данных

Для возврата релевантных страниц по поисковому запросу пользователя я планировал использовать алгоритм KNN для сравнения векторных кодировок поискового запроса и векторных кодировок содержимого страниц, хранящихся в базе данных.

Векторные кодировки естественного языка имеют решающее значение, когда речь идет о понимании того, что говорит пользователь. Как вы увидите позже, я решил использовать модель Transformer для кодирования предложений в векторное представление.

С тем, что у меня было на данный момент, можно было построить работающую поисковую систему с использованием вышеописанного метода, но это было бы крайне неэффективно, поскольку потребовалось бы просматривать КАЖДУЮ запись в базе данных, векторизировать содержание статьи и сравнивать его с вектором запроса.

Повышение эффективности поиска

Чтобы повысить эффективность поиска, у меня возникла идея проиндексировать/обработать базу данных, чтобы уменьшить пространство поиска для алгоритма KNN.

Первым шагом была векторизация содержимого всех страниц, которые я отсканировал и сохранил в своей базе данных.

from tinydb import TinyDB
from sentence_transformers import SentenceTransformer
from sklearn.cluster import KMeans

model = SentenceTransformer('sentence-transformers/stsb-roberta-base-v2')
db = TinyDB("results.json")

contents = []

for record in db:
    content = record["content"]
    contents.append(content)

embeddings = model.encode(contents)
Вход в полноэкранный режим Выход из полноэкранного режима

Как видите, для векторизации предложений я использовал библиотеку SentenceTransformer и модель трансформации «stsb-roberta-base-v2», которая была настроена для задач типа нейронного поиска, где запрос должен быть сопоставлен с соответствующими документами (именно такая задача стояла передо мной).

Теперь, когда у меня были все векторные представления страниц, я решил объединить семантически похожие страницы в кластер, используя алгоритм кластеризации K-Means.

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

kmeans = KMeans(n_clusters=3)
kmeans.fit(embeddings)
buckets = {}

for record, label in zip(db, kmeans.labels_):
    if label not in buckets:
        buckets[label] = []

    buckets[label].append(dict(record)) 

import pickle

pickle.dump(kmeans, open("kmeans-model.save", "wb"))
pickle.dump(buckets, open("buckets.save","wb"))
Вход в полноэкранный режим Выход из полноэкранного режима

Кластеризация страниц

from sentence_transformers import SentenceTransformer
import pickle
import numpy as np
from sklearn.neighbors import NearestNeighbors

model = SentenceTransformer('sentence-transformers/stsb-roberta-base-v2')

kmeans = pickle.load(open("cluster.save", 'rb'))
buckets = pickle.load(open("buckets.save", 'rb'))

while True:
    query = input("Search: ")
    encoded_query = model.encode(query)
    encoded_query = np.expand_dims(encoded_query, axis=0)
    bucket = kmeans.predict(encoded_query)
    bucket = int(bucket.squeeze())
    embeddings = []

    for result in buckets[bucket]:
        embeddings.append(result["content"])
    embeddings = model.encode(embeddings)
    neigh = NearestNeighbors(n_neighbors=10)
    neigh.fit(embeddings)
    indexes = neigh.kneighbors(encoded_query, return_distance=False)

    for index in indexes.T:
      doc = buckets[bucket][int(index.squeeze())]
      print (doc["title"], doc["url"])
      print ("")
Вход в полноэкранный режим Выход из полноэкранного режима

Сопоставление запроса пользователя с 10 наиболее релевантными страницами

В приведенном выше коде видно, что я разбил базу данных на 3 кластера.

Однако я много возился с количеством кластеров.

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

Я обнаружил, что при 3 кластерах точность результатов действительно высока, однако результаты возвращаются крайне медленно (~7 секунд на каждый поиск, но худший результат — 32 секунды).

Search: how do i compose music

Musical instrument - Wikipedia https://en.wikipedia.org/wiki/Musical_instrument

Elements of music - Wikipedia https://en.wikipedia.org/wiki/Elements_of_music

Music criticism - Wikipedia https://en.wikipedia.org/wiki/Music_criticism

Contemporary classical music - Wikipedia https://en.wikipedia.org/wiki/Contemporary_music

Accompaniment - Wikipedia https://en.wikipedia.org/wiki/Accompaniment

Musical improvisation - Wikipedia https://en.wikipedia.org/wiki/Musical_improvisation

Musique concrète - Wikipedia https://en.wikipedia.org/wiki/Musique_concr%C3%A8te

Programming (music) - Wikipedia https://en.wikipedia.org/wiki/Programming_(music)

Film score - Wikipedia https://en.wikipedia.org/wiki/Film_score

Song - Wikipedia https://en.wikipedia.org/wiki/Song

Harpsichord - Wikipedia https://en.wikipedia.org/wiki/Harpsichord

Music theory - Wikipedia https://en.wikipedia.org/wiki/Music_theory

Music industry - Wikipedia https://en.wikipedia.org/wiki/Music_industry

Definition of music - Wikipedia https://en.wikipedia.org/wiki/Definitions_of_music

Wolfgang Amadeus Mozart - Wikipedia https://en.wikipedia.org/wiki/Wolfgang_Amadeus_Mozart

Invention (musical composition) - Wikipedia https://en.wikipedia.org/wiki/Invention_(musical_composition)

Music - Wikipedia https://en.wikipedia.org/wiki/Music

Music - Wikipedia https://en.wikipedia.org/wiki/Music

Aesthetics of music - Wikipedia https://en.wikipedia.org/wiki/Aesthetics_of_music

Musicology - Wikipedia https://en.wikipedia.org/wiki/Musicology
Вход в полноэкранный режим Выход из полноэкранного режима

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

При использовании более 6 кластеров я обнаружил, что результаты выдаются с высокой скоростью, однако точность была низкой. Например, я искал что-то простое, такое как «Liverpool Football», но система не возвращала страницу Liverpool F.C, несмотря на то, что она присутствовала в базе данных.

Лучшее решение

Поскольку компромисс между скоростью и точностью в приведенном выше решении был слишком чувствительным, мне нужно было найти лучшее решение.

Проведя небольшое исследование, я наткнулся на ANNOY.

ANNOY означает «Approximate Nearest Neighbours Oh Yeah» и является небольшой библиотекой, предоставленной Spotify, для поиска точек в пространстве, которые близки к заданной точке запроса.

Spotify сам использует ANNOY для своих музыкальных рекомендаций пользователям!

Приблизительные ближайшие соседи?

Вы можете подумать, зачем нам приблизительная алогрифма ближайших соседей? Почему не точный?

Для того чтобы KNN был точным, ему приходится перебирать каждую точку данных, что крайне неэффективно.

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

Как работает ANNOY

Вот хорошая статья, объясняющая, как работает ANNOY (написанная человеком, который сам создал ANNOY!).

ANNOY работает путем построения бинарных деревьев (леса) из предоставленного ему набора данных.

Чтобы построить дерево, он выбирает две случайные точки в векторном пространстве и делит пространство на два подпространства гиперплоскостью, эквидистантной двум случайным точкам.

Процесс повторяется снова, в новых подпространствах, которые только что были созданы.

Так продолжается до тех пор, пока в каждом подпространстве не будет определенное n количество точек.

Точки, находящиеся рядом друг с другом, должны находиться в одном подпространстве, так как маловероятно, что существует гиперплоскость, разделяющая их на отдельные подпространства.

Теперь, когда у нас есть все подпространства, можно построить двоичное дерево.

Узлы дерева представляют собой гиперплоскости. Таким образом, когда нам задан вектор запроса, мы можем спуститься по дереву, указывающему нам, к каким гиперплоскостям мы должны спуститься, чтобы найти некоторые x наиболее релевантных точек в векторном пространстве.

ANNOY строит множество таких деревьев, чтобы построить лес. Количество деревьев в лесу задается программистом.

Когда задается вектор запроса, ANNOY использует очередь приоритетов для поиска этого запроса среди двоичных деревьев в своем лесу. Очередь приоритетов позволяет сосредоточить поиск на деревьях, которые лучше всего подходят для запроса (деревья, гиперплоскости которых находятся далеко от вектора запроса).

После завершения поиска ANNOY просматривает все найденные деревьями общие точки, которые образуют «соседей» вектора запроса.

Теперь k ближайших соседей могут быть ранжированы и возвращены.

Рефакторинг кода индексирования и поиска

Изменение кода для использования ANNOY не заняло много времени благодаря его простому API.

from tinydb import TinyDB
from sentence_transformers import SentenceTransformer
from annoy import AnnoyIndex

model = SentenceTransformer('sentence-transformers/stsb-roberta-base-v2')
db = TinyDB("results.json")

descriptions = []

for record in db:
    description = record["content"]
    descriptions.append(description)

embeddings = model.encode(descriptions)

index = AnnoyIndex(embeddings.shape[-1], "euclidean")

vec_idx = 0
for vec in embeddings:
    index.add_item(vec_idx, vec)
    vec_idx += 1

index.build(10)
index.save("index.ann") #stores the results of the indexing
Вход в полноэкранный режим Выход из полноэкранного режима

Код индексирования

from tinydb import TinyDB
from sentence_transformers import SentenceTransformer
from annoy import AnnoyIndex

model = SentenceTransformer('sentence-transformers/stsb-roberta-base-v2')
db = TinyDB("results.json")

index = AnnoyIndex(768, "euclidean")
index.load("index.ann")

while True:
    query = input("Search: ")

    vec = model.encode(query)
    indexes = (index.get_nns_by_vector(vec, 20))
    all_db = db.all()

    for i in indexes:
        print (all_db[i]["title"], all_db[i]["url"])
        print ("")
Вход в полноэкранный режим Выход из полноэкранного режима

код поиска пользователя

Теперь давайте посмотрим результаты…

Search: great composers
Igor Stravinsky - Wikipedia https://en.wikipedia.org/wiki/Igor_Stravinsky

Contemporary classical music - Wikipedia https://en.wikipedia.org/wiki/Contemporary_music

Gustav Mahler - Wikipedia https://en.wikipedia.org/wiki/Gustav_Mahler

Symphony - Wikipedia https://en.wikipedia.org/wiki/Symphony

Art music - Wikipedia https://en.wikipedia.org/wiki/Art_music

Symphony No. 5 (Beethoven) - Wikipedia https://en.wikipedia.org/wiki/Symphony_No._5_(Beethoven)

Wolfgang Amadeus Mozart - Wikipedia https://en.wikipedia.org/wiki/Wolfgang_Amadeus_Mozart

Ludwig van Beethoven - Wikipedia https://en.wikipedia.org/wiki/Ludwig_van_Beethoven

Music of Central Asia - Wikipedia https://en.wikipedia.org/wiki/Central_Asian_music

Big band - Wikipedia https://en.wikipedia.org/wiki/Big_band

Program music - Wikipedia https://en.wikipedia.org/wiki/Program_music

Cello Suites (Bach) - Wikipedia https://en.wikipedia.org/wiki/Bach_cello_suites

Film score - Wikipedia https://en.wikipedia.org/wiki/Film_score

Johann Sebastian Bach - Wikipedia https://en.wikipedia.org/wiki/Johann_Sebastian_Bach

Elements of music - Wikipedia https://en.wikipedia.org/wiki/Elements_of_music

Music of China - Wikipedia https://en.wikipedia.org/wiki/Chinese_classical_music

Organ (music) - Wikipedia https://en.wikipedia.org/wiki/Organ_(music)

Toccata and Fugue in D minor, BWV 565 - Wikipedia https://en.wikipedia.org/wiki/Toccata_and_Fugue_in_D_minor,_BWV_565

Georg Philipp Telemann - Wikipedia https://en.wikipedia.org/wiki/Georg_Philipp_Telemann

Sonata form - Wikipedia https://en.wikipedia.org/wiki/Sonata_form


Search: what are the rules of cricket
No-ball - Wikipedia https://en.wikipedia.org/wiki/No-ball

International cricket - Wikipedia https://en.wikipedia.org/wiki/International_cricket

Toss (cricket) - Wikipedia https://en.wikipedia.org/wiki/Toss_(cricket)

Match referee - Wikipedia https://en.wikipedia.org/wiki/Match_referee

Cricket ball - Wikipedia https://en.wikipedia.org/wiki/Cricket_ball

Board of Control for Cricket in India - Wikipedia https://en.wikipedia.org/wiki/Board_of_Control_for_Cricket_in_India

India national cricket team - Wikipedia https://en.wikipedia.org/wiki/India_national_cricket_team

Caught - Wikipedia https://en.wikipedia.org/wiki/Caught

Substitute (cricket) - Wikipedia https://en.wikipedia.org/wiki/Substitute_(cricket)

International Cricket Council - Wikipedia https://en.wikipedia.org/wiki/International_Cricket_Council

Portal:Cricket - Wikipedia https://en.wikipedia.org/wiki/Portal:Cricket

Delivery (cricket) - Wikipedia https://en.wikipedia.org/wiki/Delivery_(cricket)

Cricketer (disambiguation) - Wikipedia https://en.wikipedia.org/wiki/Cricketer_(disambiguation)

Cricket (disambiguation) - Wikipedia https://en.wikipedia.org/wiki/Cricket_(disambiguation)

Cricket West Indies - Wikipedia https://en.wikipedia.org/wiki/Cricket_West_Indies

Zimbabwe Cricket - Wikipedia https://en.wikipedia.org/wiki/Zimbabwe_Cricket

Bowled - Wikipedia https://en.wikipedia.org/wiki/Bowled

Pakistan Cricket Board - Wikipedia https://en.wikipedia.org/wiki/Pakistan_Cricket_Board

World Cricket League - Wikipedia https://en.wikipedia.org/wiki/World_Cricket_League

West Indies cricket team - Wikipedia https://en.wikipedia.org/wiki/West_Indies_cricket_team
Вход в полноэкранный режим Выход из полноэкранного режима

Как вы можете видеть, результаты довольно точные! Очевидно, не помогло то, что база данных у меня была довольно маленькая, но, несмотря на это, результаты получились неплохие!

Кроме того, эти результаты были получены практически мгновенно, гораздо быстрее, чем предыдущее решение.

Заключение

Единственное, что помешало улучшить результаты поиска, — это размер базы данных. Если бы в будущем я решил создать более крупную поисковую систему, я бы использовал такие базы данных, как Firebase или MongoDB, и рассмотрел бы, как ANNOY может взаимодействовать с ними.

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

Спасибо, что прочитали, и надеюсь, что вы тоже чему-то научились!

Оцените статью
Procodings.ru
Добавить комментарий