--- tags: text, nlp, ml --- Сравнительный анализ построения поиска схожих статей по программированию =================================================================== *Ключевые слова*: **NLP**, **Обработка естественного языка**, **Рекомендации**, **TF-IDF**, **Мешок слов**, **Bag-of-Words**, **Word2vec**, **Doc2vec**, **Поиск**, **WMD** *Авторы*: И.С. Ильиных ilyasyoy@gmail.com [^1]: Kusner M. et al. From word embeddings to document distances //International Conference on Machine Learning. – 2015. – С. 957-966. [^2]: Goldberg Y., Levy O. word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method //arXiv preprint arXiv:1402.3722. – 2014. [^3]: Pennington J., Socher R., Manning C. Glove: Global vectors for word representation //Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). – 2014. – С. 1532-1543. [^4]: Bojanowski P. et al. Enriching word vectors with subword information //arXiv preprint arXiv:1607.04606. – 2016. [^5]: Peters M. E. et al. Deep contextualized word representations //arXiv preprint arXiv:1802.05365. – 2018. [^6]: Le Q., Mikolov T. Distributed representations of sentences and documents //International Conference on Machine Learning. – 2014. – С. 1188-1196. [^7]: Aizawa A. An information-theoretic perspective of tf–idf measures //Information Processing & Management. – 2003. – Т. 39. – №. 1. – С. 45-65. [^8]: Zhang Y., Jin R., Zhou Z. H. Understanding bag-of-words model: a statistical framework //International Journal of Machine Learning and Cybernetics. – 2010. – Т. 1. – №. 1-4. – С. 43-52. [^9]: Tang J. et al. Arnetminer: extraction and mining of academic social networks //Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. – ACM, 2008. – С. 990-998. [^10]: Пархоменко П.А., Григорьев А.А., Астраханцев Н.А. Обзор и экспериментальное сравнение методов кластеризации текстов // Труды ИСП РАН. 2017. №2. [^11]: Mikolov T. et al. Distributed representations of words and phrases and their compositionality //Advances in neural information processing systems. – 2013. – С. 3111-3119. [^12]: Rubner Y., Tomasi C., Guibas L. J. The earth mover's distance as a metric for image retrieval //International journal of computer vision. – 2000. – Т. 40. – №. 2. – С. 99-121. ## Аннотация В данной статье был проведен сравнительный анализ алгоритмов поиска похожих текстов. Эта задача является фундаментальной и актуальной в области обработки естественного языка (NLP), решение этой задачи поспособствует продвижению других частей этой области (например классификации, кластеризации). В представленной статье сравнивались 3 базовых алгоритма: **BoW**, **TF-IDF**, **Doc2vec**, **WMD** --- для **Doc2vec**, **WMD** использовалась модель эмбеддингов **GloVe** размерности 300, обученная на словаре из 6 миллиардов слов, с размером словаря 400 тысяч слов, данная модель находится в открытом доступе. Поиск проводился на наборе англоязычных статей по темам близким к *Computer Science*, что, безусловно, повлияло на результаты данного исследования. По выводам анализа было приведено решение, какой алгоритм лучше применять для этой задачи, а также написан прототип сервиса, который размещен в хранилище GitHub под лицензией *MIT Licence*, следовательно можно посмотреть как работают алгоритмы не только со стороны результатов, которые она представляет, а также исходный код, который позволяет это сделать. ## Введение В настоящей статье рассматривается проблема выбора подходящего метода для представления статей, как векторов. Данная проблема является актуальной в данное время так как: - Увеличения наборов данных текстового вида, усложняет поиск той информации, что интересует пользователя. - Растущий объем данных усложняет поиск интересующей информации даже в одной области научного знания. - Требования к отзывчивости приложений, решающих задачу, то есть алгоритмы должны также быстро решать задачу. Статья была вызвана тем, что: - *Разнообразие решений*. Существует много подходов к решению данной задачи. - *Неоднородность дынных*. Природа данных может быть разной, а для данных разной структуры лучше подходят разные алгортмы. Данная работа сделана с целью анализа и экспериментального сравнения построенных моделей для сравнения документов. В ней будут построены как классические методы, так и современные. К современным методам относятся методы, использующие нейронные сети, их называют моделями построения эмбеддингов. Также все алгоритмы в данной статье будут сопоставлять ей вектор, то есть данные алгоритмы можно использовать не только для решения этой задачи, но также, например, для решения задачи кластеризации[^10] Построение рекомендации будет строиться по названию и аннотации статьи, так как в них содержатся все ключевые слова, которые используются в статье. Выбрана предметная область: *Computer Science* потому, что: - Данная область быстро расширяется, то есть в ней много данных. - Данные в этой области хорошо структурированы и они избавлены от шума, так как проходят предобработку. - Существуют открытые наборы с данными в этой области. Данные были взяты из [открытого источника](https://aminer.org/citation)[^9], использовался набор в котором 600 тысяч статей, также данный набор содержит информацию о ссылках между статьями, можно использовать и больший набор, данный набор был выбран, так как он дает репрезентативные рузультаты и позволяет производит все вычислелния локально, следовательно результаты, полученные в статье, являются воспроизводивыми. Было решено проверить основные алгоритмы, которые используются для решения данной задачи: - **Bag-Of-Words** - **TF-IDF** - **Doc2vec** - **WMD** ## Обзор подходов к поиску Для решения поставленной задачи можно использовать различные подходы и методы. Далее представлены основные методы, которые будут исследоваться в статье. Были выбраны методы, не использующие подходы глубокого обучения. Ниже расстоянием между векторами понимается либо **норма-L2**, либо **косинусное расстояние**. Обычно, все-таки, в задачах **NLP** используется **косинусное расстояние**. ### Мешок слов (Bag-Of-Words) **Мешок слов**[^8]. Один их фундаментальных алгоритмов. Представление статьи будет выглядеть как вектор, длиной которого является количество различных слов из словаря всех документов, по которым строится индекс. Компонентами вектора будут являться количества раз, которое повторилось слово в статье. $$ v_i = \sum_{w \in D}w $$ где $v_i$ --- это вектор статьи, $D$ --- это документ, представление которого получается, набор векторов слов, $w$ --- это вектор слова вида $w = (0 \ldots 1 \ldots 0)$, такой что $L^1(w_i)=1$, где 1 находится на позиции индекса слова в общем для всех статей словаре. Основные характеристики: - Не учитывает вес слов в контексте всех документов. - Вектор будет большой размерности ($dim(v_i) \gt\gt |D|$), размерность будет равна количеству слов в словаре статей. Методы улучшения: - Нормализация данных. Приводить слова к общей форме (**stemming**, **lemmatisation**), чтобы уменьшить словарь и улучшить результат. - Использовать алгоритмы уменьшения размерности (**SVD**), чтобы упростить сравнения векторов документов и уменьшить потребление памяти. - Брать только популярные слова, например отфильтровать слова, которые встречаются больше и/или меньше некоторого порога. ### TF-IDF (Term Frequency - Inverese Document Frequency) **TF-IDF**[^7]. Является улучшением алгоритма **Bag-Of-Words**, также позволяет получить для статьи векторное представление. Отличием будет являться то, что для каждого слова будет вычислять его индекс обратной частоты, то есть насколько редкий этот терм в корпусе статей, на которых проихводится обучение. Длина вектора будет совпадать с длиной вектора в алгоритме **Bag-Of-Words**. Составлять вектор статьи будут коэффициенты $TF \cdot IDF$, где $TF$ - это частота слова в тексте, а $IDF$ - это обратная частота слова в корпусе текстов. $$ TF(i, \: word) = \frac{\sum_{j=1}^{N_i} n_j}{N_i} $$ где $i$ --- это номер документа, $N$ --- это колличество слов в статье, $n_i$ --- сколько раз слово повторяется в статье. $$ IDF(word, C) = log \Bigg(\frac{|C|}{|C_{index(word)}|}\Bigg) $$ Основные характеристики: - Учитывает вес слов в контексте всех документов. - Вектор будет большой размерности ($dim(v_i) \gt\gt |D|$), размерность будет равна количеству слов в словаре статей. Методы улучшения: - Нормализация данных. Приводить слова к общей форме (**stemming**, **lemmatisation**), чтобы уменьшить словарь и улучшить результат. - Использовать алгоритмы уменьшения размерности (**SVD**), чтобы упростить сравнения векторов документов и уменьщить потребление памяти. - Брать только популярные слова, например отфильтровать слова, которые встречаются больше и/или меньше некоторого порога, проводить фильтрацию можно как и по **TF**, так и по **IDF**. - Нет привязки к формулам вычисления $IDF$ и $TF$, можно подобрать функцию, которая будет оптимальна для некоторой задачи, которая решается. ### Векторное представление слов *Эмбеддингами* слов называются вектора, которые сохраняют информацию о контексте, в котором употреблено слово, что позволяет получить отображение из пространства слов в пространство векторов размерности $k$ (обычно 300, 500). Слова в этом пространстве обладают таким свойством: $$ vec(Paris) - vec(France) + vec(Russian) - vec(Moscow) \rightarrow 0 $$ где '$\rightarrow$' --- показывает, что при увеличении степени обученности модели это выражение будет стремиться к 0. Примеры моделей: **Word2vec**[^2] [^11], **GloVe**[^3], **FastText**[^4], **ELMo**[^5] & etc. Впервые понятие эмбеддингов слов было введено Томасом Миколовым в статьеf[^11]. Стоит упомянуть, что обучать модели можно несколькими способами, будут выделены **Continuous Bag-Of-Words**, и **Skip-gram model**, обе модели обучают нейронную сеть со скрытым слоем, из которого получаются эмбеддинги, только в первом случае предсказывается слово по контексту, а во втором контекст по слову. **Skip-gram model** обычно обучается быстрее[^11]. Для получения более подробного описания предлагается обратиться к первоисточнику[^11], либо к одной их этих статей [^2], [^3], [^4], [^5]. ### Doc2vec **Doc2vec**[^6]. Этот метод является современным, он использует эмбеддинги, для получения которых используются нейронные сети. В данной статье **Doc2vec** рассматривается в отрыве от алгоритма построения эмбеддингов слов. Данный метод наследут подход метода **Bag-Of-Words**, то есть вектор статьи - это взвешенная сумма векторов слов, где вес вектора - это то, сколько раз он повторяется, то есть просто сумма векторов статьи, также имеет смысл провести нормализацию, если для сравнения статей используется **cosine distance** $$ vec(D, E_k) = \sum_{w \in D} E_k(w) $$ где $D$ --- это документ, $E_k$ --- это оператор из пространства слов в пространство эмбеддингов размерности $k$. Основные характеристики: - Требует дополнительную модель, которая позволяет получить векторное представление слов. - Статьи с похожими семантически словами будут обладать близкими векторами, то есть статьи и из разных слов будут близкими точками в пространстве статей, если слова, из которых они состоят употребляются в одном контесте. - Учитывает вес слов в контексте всех документов, если построить модель эмбеддингов на предоставленных данных. - Вектор обладает фиксированной размерностью. - Алгоритм зависит от модели эмбеддинга слов, так как он непосредственно её использует. - Можно не приводить слова к общей форме (**stemming**, **lemmatisation**), если используются модели **FastText**, **ELMo**. Методы улучшения: - Встречается модификация, которая использует подход **TF-IDF**. Вектора слов умножаются на их $IDF$ индекс, что также позволяет учесть контекст всех документов корпуса. - Выбрать другие эмбеддинги. - Улучшить уже используемую модель эмбеддингов. ### WMD (Word Mover's Distance) **WMD**[^1] Упомянуть этот метод стоит, так как считается он являтеся *State-of-Art* методом сравнения документов на семантическое отличие. Он для двух статей дает расстояние между ними, то есть данный алгоритм не может переводить статьи в векторное пространство, но он является метрикой между статьями. Данный метод является адаптацией другого алгоритма, называемого **EMD**[^12] (Earth Mover's Distance). В понятии алгоритма статья это набор векторов её слов. Существуют несолько вариантов этого метода: **WMD**, **WMD-relaxed** - оба эти алгоритма оперируют понятием потока. Потоком терма является сумма его расстояний до слов другого документа, либо максимум из расстояний до слов другого документа. Вектора слов умножаются на их потоки, суммируются вектора статьи, затем находится норма разности получившихся векторов. $$ WMD = \| \textbf{X}d - \textbf{X}\dot{d} \|_2 $$ где $d$, $\dot{d}$ --- это **Bag-Of-Words** представление потоков статей. $X$ - матрица стоимости перемещения, то есть $X_{i, j} = c(i, j)$, расстояние между словами. $c(i, j)$ --- это либо **cosine distance** либо некоторая норма $L^k$. Основные характеристики: - У решения задачи оптимизации **WMD** лучшая средняя сложность: $O(p^3log \: p)$. - Метод не строит вектора для статьи, что в задачи поиска рекомендации требует сравнения не векторов, а именно статей с помощью этой метрики. - Статьи с похожими семантически словами будут обладать меньшим расстоянием, то есть статьи и из разных слов будут близкими точками в пространстве статей, если слова, из которых они состоят употребляются в одном контесте. - Учитывает вес слов в контексте всех документов, если построить модель эмбеддингов на предоставленных данных. - Алгоритм зависит от модели эмбеддинга слов, так как он непосредственно её использует. - Можно не приводить слова к общей форме (**stemming**, **lemmatisation**), если используются модели **FastText**, **ELMo**. Методы улучшения: - Выбрать другие эмбеддинги. - Улучшить уже используемую модель. - Поменять метрику поиска расстояния между словами. ## Выбор метода решения Будет проведено аналитическое сравнение методов, а также будет предоставлена возможность посмотреть модели, которые были описаны выше на примере готового решения. Предоставлен сервис на [GitHub](https://github.com/IlyasYOY/similar-articles-poc), который позволяет отдать ему данные, обучить на них модели, а после построить рекомендации. Сервис написан исключительно в демонстрационных целях, реализация может быть не оптимальной. Он предназначен для того, чтобы тот, кого заинтересует более практическая сторона вопроса, то есть непосредственно результаты, мог получить к ним доступ и поэкспериментировать с ними же. Для написание реализации был выбран язык Python, так как он содержит множество библиотек для работы с NLP ([gensim](https://github.com/RaRe-Technologies/gensim), [textacy](https://github.com/chartbeat-labs/textacy/), [spaCy](https://github.com/explosion/spaCy), [NLTK](https://github.com/nltk/nltk) & etc.), также он легко позволяет предоставить к этим моделям доступ, то есть интерфейс взаимодействия с ними. Инструкция по работе с ним находится в репозитории. Алгоритм **WMD** не был реализован, так как он не позволяет в реальном времени получать похожие статьи без дополнительных данных и/или подходов. ## Описание метода решения ### Предобработка текста Перед применением алгоритмов требуется провести нормализацию входных данных. - Разбиение теста на составные части, единичные части обработки, в нашем случе это слова. - Стемматизация/Лемматизация. - Отфильтровать слова, которые не несут никакой информации о тексте. То есть текст разбивается на некоторые логические единицы, в случае этой работы это было слова. Существуют уже готоыве инструменты, которые позволяют это сделать оптимально, в случае языка Python --- это [gensim](https://github.com/RaRe-Technologies/gensim), [textacy](https://github.com/chartbeat-labs/textacy/), [spaCy](https://github.com/explosion/spaCy), [NLTK](https://github.com/nltk/nltk). ### Дополнительные модели Требуются ли для работы алгоритма дополнительные модели. - Да - Нет Некоторые алгоритмы могут требовать заранее построенные модели, в данной статье такими алгоритмами являются **WMD**, **Doc2vec**. Они трубуют заранее построенных моделей эмбеддингов (смотрите раздел *"Обзор подходов к поиску"* для более подробного описания проблемы). ### Затратность построения модели - Зависимая Требует ли модель знания данных о всех данных, для её построения на одной части данных. - Независимая Модель может строиться отдельно по частям данных. - Векторезуемость. Алгоритм приводи статью к вектору, иные случаи, например: алгоритм сравнивает 2 статьи, не будут подходить под этот критерий. ### Сравнение алгоритмов поиска. Таблица 1. Краткое описание алгоритмов. | | Предобработка текста | Дополнительные модели | Затратность построения модели | Векторезуемость | |------------------|----------------------|--------------------------|-------------------------------|-----------------| | **Bag-Of-Words** | Да | Нет | Независимая | Да | | **TF-IDF** | Да | Нет | Зависимая | Да | | **Doc2vec** | Да (иногда не вся) | Да (**Word2vec** & etc.) | Независимая | Да | | **WMD** | Да (иногда не вся) | Да (**Word2vec** & etc.) | Независимая | Нет | Таблица 1 содержит сводную информацию об используемых алгоритмах. Набор данных, их которого рассмотриватся статьи обладает следующими свойствами: - Данные структурированы Статьи проверялись до публикации, то есть там используется лексика, которая близка к теме информационных технологий. Статьи состоят из конкретных состовляющих, то еесть все статьи точно имеют информацию об авторах, названии, описании и дату публикации. - Отсутствие шума Так как статьи модерировались до публикации, то в них отсутвствуют опечатки и ошибки. ### Пример рекоммендации Данный раздел предоставт некоторые результаты рекомендации алгоритмов, которые рассматриваются. Они потребуются для построения вывода о том, какой алгоритм лучше. Под счетом будет подразумеваться то, насколько похожи статьи. #### Пример поиска для статьи "Calculus Early Transcendentals Single Variable": Таблица 2. | N | **Doc2vec** | **TF-IDF** | **Bag-Of-Words** | | - | ----------- | ---------- | ---------------- | | 1 | "Single Variable CalcLabs with the TI-89/82: For Stewart's Fourth Edition, Calculus, Single Variable Calculus, Calculus--Early Transcendentals, Single Variable Calculus--Early Transcendentals, 4th edition" со счетом 91.73% | "Single Variable CalcLabs with the TI-89/82: For Stewart's Fourth Edition, Calculus, Single Variable Calculus, Calculus--Early Transcendentals, Single Variable Calculus--Early Transcendentals, 4th edition" со счетом 83.67% | "Single Variable CalcLabs with the TI-89/82: For Stewart's Fourth Edition, Calculus, Single Variable Calculus, Calculus--Early Transcendentals, Single Variable Calculus--Early Transcendentals, 4th edition" со счетом 84.42% | | 2 | "Double integral calculus of variations on time scales" со счетом 79.20% | "Multivariable CalcLabs with Maple for Stewart's Calculus, Multivariable Calculus, Calculus: Early Transcendentals : For Stewart's Fourth Edition, Calculus, Multivariable Calculus, Calculus--Early Transcendentals, 4th edition" со счетом 60.58% | "Multivariable CalcLabs with Maple for Stewart's Calculus, Multivariable Calculus, Calculus: Early Transcendentals : For Stewart's Fourth Edition, Calculus, Multivariable Calculus, Calculus--Early Transcendentals, 4th edition" со счетом 55.47% | | 3 | "CalcLabs with Maple Single Variable Calculus, 4th edition" со счетом 78.70% | "Thomas' Calculus Early Transcendentals (11th Edition) (Thomas Series)" со счетом 52.82% | "CalcLabs with Maple Single Variable Calculus, 4th edition" со счетом 50.71% | | 4 | "Single value simulation of fuzzy variable—some further results" со счетом 76.49% | "Calculus" со счетом 39.07% | "CalcLabs with Mathematica Single Variable Calculus, 4th edition" со счетом 50.71% | | 5 | "CalcLabs with Mathematica for Stewart's Calculus: Concepts and Contexts : Single Variable, 1st edition" со счетом 76.24% | "Network calculus" со счетом 34.50% | "Calculus" со счетом 44.72% | #### Пример поиска для статьи "Type Graphics and MacIntosh": Таблица 3. | N | **Doc2vec** | **TF-IDF** | **Bag-Of-Words** | | - | ----------- | ---------- | ---------------- | | 1 | "Computer Graphics SRGP/SPHIGS for Macintosh" со счетом 86.29% | "Macintosh graphic techniques for multimedia " со счетом 72.47% | "Surfwatch Macintosh " со счетом 57.74% | | 2 | "Macintosh graphic techniques for multimedia " со счетом 82.03% | "Surfwatch Macintosh " со счетом 70.89% | "Graphic Package Macintosh/Disk " со счетом 57.74% | | 3 | "Graphic Package Macintosh/Disk " со счетом 80.23% | "Biotaapp for Macintosh " со счетом 70.89% | "Biotaapp for Macintosh " со счетом 57.74% | | 4 | "Power painting: computer graphics on the Macintosh " со счетом 79.53% | "Tripmate for Macintosh " со счетом 70.89% | "Tripmate for Macintosh " со счетом 57.74% | | 5 | "Graphic design for computer graphics " со счетом 79.45% | "MultiFinder for the Macintosh " со счетом 70.89% | "Types " со счетом 57.74% | ## Заключение Если рассмотреть алгоритмы с точки зрения предметной области статей по *Computer Science*, то выгоднее использовать алгоритм **TF-IDF**, из-за причин описанных выше, результатов Таблицы 1, а также так как он не требует дополнительных моделей, которые требуется также обучить и зависит только от слов, которые используются в статье, если сравнивать с **Doc2vec**, **WMD**. Если учитывать описанные выши особенности набора данных, то **Doc2vec**/**WMD** будут излишним для этой задачи, так как не требуется рассмотривать слова с учетом ошибок, из-за хорошей структуры, также в заголовке и описании будет использоваться тот набор слов, который используется во всей статье, то есть преимущества **Word2vec** и других эмбеддингов будут излишни. В сравнени с **BoW** **TF-IDF** лучше с той стороны, что он учитывает вес слов в контексте всех документов, то есть документы с редкими словами, но совпадающими со словами исходной статьи, будут выше в поисковой выдаче. **WMD** вовсе не позволяет получить результат за ограниченное время. Из приведенных в прошлом пункте (смотрите раздел *Пример рекоммендации*, Таблица 2, 3) результатов видно, что алгоритм отображают результаты близкие друг к другу, то есть часть выдачи совпадает. Также видно, что у **Bag-Of-Words** и **TF-IDF** функция схожести изменяется довольно резко, то есть она менее гладкая чем функция схожести для **Doc2vec**, это обусловлено дискретностью алгоритма, под дискретностью подразумевается обращения внимания алгоритмом на слова, а не их смысл. Более того, в случае **Bag-Of-Words** для статьи *"Type Graphics and MacIntosh"* алгоритм говорит, что "Types" совпадает с исходной со счетом 57.74%, хоть под types может подразумеваться что угодно, вплоть до системы типизации языков программирования, что определенно не является тепой .пересекающейся с исходной. После сравнения данных алгоритмов можно решить, что лучшим вариантом является **TF-IDF**, так как не надо учитывать синонимы, язык обладает словами такими, что они обладают четкой структурой, то есть их легко привести к базовой форме, он менее затратен, что является несомненным плюсом. Реализация **TF-IDF** входит в уже готовые фреймворки, которые позволяют распредеоить вычисления, например Spark, что является его преимуществом. Существуют готовые решения для поиска, которые используют **TF-IDF** ([ElasticSearch](https://www.elastic.co/guide/en/elasticsearch/guide/current/scoring-theory.html)). Хоть и функция схожести у него довольно не плавная, но это будет становиться лучше с ростом размера документов и с ростом кол-ва документов. Дополнительным направлением является проверка алгоритмов, с использованием некоторой дополнительной информации (информации об авторах, ссылок между документами и так далее), это может учучшить результаты других алгоритмов. Если смотреть на алоритмы в более широком контексте, то иожно придти к выводу, что выбор алгоритма зависит от решаемой задачи, так как у кадлого алгоритма есть свои плюсы и минусы.