В начале осени мне довелось выступить на двух конференциях - Why R? (см. также здесь) и EARL - с докладом, посвященным использованию т.н. "заголовков User-Agent" в задачах машинного обучения. Развернутую версию этого доклада на английском языке можно найти в моем новом блоге на платформе Medium. Ниже я привожу ее вариант также на русском языке.

***

Что представляют собой строки User-Agent?

Когда посетитель взаимодействует с тем или иным веб-сайтом, браузер посылает HTTP запросы серверу для получения соответствующего контента или выполнения каких-то других действий. Подобные запросы обычно содержат несколько заголовков, т.е. строковых пар "ключ-значение", которые задают параметры запроса. User-Agent (UA) - это одна из разновидностей таких HTTP заголовков (англ. "HTTP headers"), предназначенная для описания программного обеспечения,  которое действует от имени пользователя (рис. 1).


Рисунок 1. При взаимодействии с сервером браузер выполняет HTTP запросы от имени пользователя. HTTP заголовок User-Agent описывает свойства браузера.


Исходное назначение UA-строк состояло в достижении т.н. "договора о контенте" (англ. "content negotiation") - определении оптимального контента для передачи с сервера в зависимости от информации, содержащейся в соответствующей UA-строке (например, формат изображений, язык документа, кодировка текста и т.п.). Подобная информация обычно включает описание системы, в которой работает браузер (физическое устройство, операционная система и ее версия, языковые настройки), "движок" браузера и его версия, "движок" разметки страницы и его версия и т.д. (рис. 2).

 

Рисунок 2. Анатомия типичной строки User-Agent.

Хотя предоставление сервером разного контента в зависимости от особенностей браузера сегодня считается плохой практикой, UA-строки по-прежнему имеют несколько важных областей применения. Наиболее важной из таких областей является веб-аналитика, т.е. анализ характера трафика с целью оптимизации эффективности веб-сайта. Другая важная область - это управление веб-трафиком с целью блокировки вредоносных ботов и других автоматизированных приложений, снижения нагрузки на сайт от нежелательных посетителей, предотвращения "кликфрода"  и т.п. Благодаря богатой информации, содержащейся в UA-строках, их также можно использовать как источник данных в задачах машинного обучения. В этой статье рассмотрен способ эффективного представления подобной информации в векторном виде, готовом к использованию в задачах машинного обучения (например, для разработки предсказательных моделей). Приведенные в примерах данные и код можно найти в соответствующем GitHub-репозитории.


Элементы строк User-Agent как признаки в моделях машинного обучения  

Элементы UA-строк часто оказываются полезными в качестве переменных, опосредованно характеризующих образ жизни, техническую грамотность и даже достаток посетителей того или иного веб-сайта. Так, можно ожидать, что пользователь, зашедший на сайт с дорого мобильного телефона последней модели, существенно отличается от посетителя того же сайта, который пользуется Internet Explorer на настольном компьютере под управлением Windows XP. Подобные описательные признаки пользователей сайта оказываются особенно полезными в отсутствие других демографических данных (например, в случае с новыми неидентифицируемыми пользователями). 

В некоторых задачах важно также различать веб-трафик, сгенерированный настоящими пользователями (людьми) и всевозможными автоматизированными приложениями (пауки, боты, скрейперы и т.п.). Во многих случаях сделать это несложно, поскольку веб-боты и пауки имеют простые по структуре UA-строки, содержащие ключевое слово "bot" (например, Googlebot/2.1 (+http://www.google.com/bot.html)) . Однако многие пауки и боты не следуют этому правилу (например, UA-строки у ботов Facebook содержат слово "facebookexternalhit") - для их распознавания с использованием регулярных выражений требуется разработка и постоянное обновление справочника возможных ключевых слов.

На первый взгляд, самый простой способ использования UA-строк в задачах машинного обучения заключается в применении парсера для извлечения отдельных элементов строк и последующем представлении этих элементов в виде индикаторных переменных. Этот способ действительно хорошо подходит для простых случаев, когда преобразованию в признаки подлежат очевидные и легко выделяемые элементы UA-строк. Например, не представляет большого труда определить тип устройства, которое выполняет HTTP запросы (мобильные устройства vs. настольные vs. серверные и т.п.). Для этого существует несколько высококачественных парсеров, основанных на регулярных выражениях (см., например, проект ua-parser и его реализации для разных языков программирования).

Однако этот способ быстро становится неприменимым, если исследователь желает извлечь максимум информации из всех элементов, составляющих UA-строки. Это определяется двумя причинами:

  • Следование существующим официальным рекомендациям по формату UA-строк практически никак и никем не контролируется, в результате чего на практике отмечается огромное разнообразие подходов к форматированию этих строк. Это в свою очередь существенно затрудняет качественный парсинг с применением регулярных выражений. Более того, постоянно появляются новые устройства и их модели, новые версии операционных систем и браузеров и т.д., что делает задачу поддержания качественных парсеров чрезвычайно трудоемкой.
  • Число возможных элементов UA-строк и их сочетаний астрономически велико. Даже если бы стало возможным представить все эти элементы в виде индикаторных переменных, итоговая матрица оказалась бы чрезвычайно разреженной и вряд ли уместилась бы в памяти компьютера.

Для преодоления этих трудностей можно было бы воспользоваться снижением размерности исходных данных и представить каждую UA-строку в виде вектора ограниченного размера, обеспечив при этом минимальную потерю информации. Эта идея, безусловно, не является новой. Более того, поскольку UA-строки - это, в сущности, просто небольшие по длине текстовые "документы", то для их векторного представления в пространстве ограниченной размерности (операция "вложения", англ. "embedding") можно применить многие из современных методов обработки естественных языков. В своих проектах я для этого часто использую алгоритм fastText, разработанный исследователями из Facebook (Bojanowski et al. 2016).

Описание fastText не является целью этой статьи. Однако, прежде чем мы перейдем к рассмотрению примеров, стоит отметить несколько важных на практике преимуществ этого алгоритма:

  • в отличие от других методов, основанных на использовании нейронных сетей, fastText не нуждается в большом объеме данных - для построения хорошо работающих моделей обычно бывает достаточно обучающего корпуса лишь с несколькими тысячами документов;
  • этот алгоритм особенно хорошо работает на небольших документах, к числу которых принадлежат и UA-строки;
  • как следует из названия алгоритма, обучение fastText-моделей происходит быстро;
  • в силу того, как он устроен, алгоритм хорошо справляется с векторным представлением слов, которые не встречались в документах из обучающего корпуса (т.н. "out-of-vocabulary words");
  • fastText-модели можно обучать как с учителем, так и без.

Программные реализации алгоритма fastText

Официальная реализация алгоритма fastText доступна в виде C++ библиотеки, а также ее Python-"обертки". Обе эти библиотеки хорошо документированы и просты в использовании. Широко используемая Python-библиотека gensim имеет свою собственную реализацию алгоритма, несколько отличающуюся от его исходной версии.

В R существует несколько пакетов-оберток для официальной C++ библиотеки (см. fastText, fastrtext и fastTextR). Однако мне кажется, что удобнее всего в R работать с этим алгоритмом, вызывая команды из официальной Python-библиотки fasttext посредством пакета reticulate. Импорт fasttext  в среду R можно выполнить следующим образом:

# Сначала необходимо установить Python и `fasttext`
# (см. https://fasttext.cc/docs/en/support.html)

# Загрузка пакета `reticulate` (если нужно, сначала установите его):
require(reticulate)

# Убеждаемся, что модуль `fasttext` доступен R:
py_module_available("fasttext")
## [1] TRUE

# Импортирование модуля `fasttext`:
ft <- import("fasttext")

# Далее необходимые методы можно вызывать с помощью
# стандартной для R `$`-нотации. Например: 
# `ft$train_supervised()`


Пример использования алгоритма fastText

Описанные ниже примеры основаны на выборке из 200000 уникальных UA-строк, извлеченной из базы данных whatismybrowser.com (рис. 3).


Рисунок 3. Данные, использованные в примерах в этой статье. Данные хранятся в текстовом файле, где каждая строка соответствует отдельному UA-заголовку. Все символы были приведены к нижнему регистру. Никакая другая предварительная обработка данных не выполнялась.


Для обучения fastText-модели без учителя достаточно выполнить команду, подобную этой:

m_unsup <- ft$train_unsupervised(
   input = "./data/train_data_unsup.txt",
   model = "skipgram",
   lr = 0.05, 
   dim = 32L, # размер вектора
   ws = 3L, 
   minCount = 1L,
   minn = 2L, 
   maxn = 6L, 
   neg = 3L, 
   wordNgrams = 2L, 
   loss = "ns",
   epoch = 100L, 
   thread = 10L
)

Аргумент dim в приведенной команде задает размерность векторного пространства. Здесь мы запрашиваем 32-мерное пространство. Остальные аргументы контролируют процесс обучения модели (lr - скорость обучения, loss - функция потерь, epoch - количество "эпох" обучения и т.д.). Подробнее с этими и другими аргументами можно ознакомиться в официальной документации.

Полученную модель далее можно применять для вычисления векторных представлений новых документов (например, UA-строк из тестового набора данных). Ниже показано, как это можно сделать (ключевая команда здесь - m_unsup$get_sentence_vector(): она возвращает усредненный вектор для всех элементов UA-строки): 

test_data <- readLines("./data/test_data_unsup.txt")

emb_unsup <- test_data %>% 
  lapply(., function(x) {
    m_unsup$get_sentence_vector(text = x) %>%
      t(.) %>% as.data.frame(.)
  }) %>% 
  bind_rows(.) %>% 
  setNames(., paste0("f", 1:32))

# Вывод на экран первых пяти элементов векторов
# (размером 32), которые соответствуют первым
# трем UA-строкам из тестовой выборки:

emb_unsup[1:3, 1:5]
##      f1       f2    f3    f4      f5
## 1 0.197 -0.03726 0.147 0.153  0.0423
## 2 0.182  0.00307 0.147 0.101  0.0326
## 3 0.101 -0.28220 0.189 0.202 -0.1623

Переменные, обозначенные в приведенной таблице с результатами вычислений как f1, f2 ... f32, далее можно использовать в качестве признаков в других задачах машинного обучения (подобный подход носит название "transfer learning").

Но как нам понять, насколько полезна созданная нами fastText-модель? Конечно, лучшим тестом было бы использование векторных представлений UA-строк в стоящей перед исследователем основной задаче (например по оубчению некоторой предсказательной модели) и последующая оценка качества полученного решения. Однако прежде, чем тратить усилия (и, возможно, финансовые ресурсы) на обучение основной модели, мы можем сначала визуально оценить качество векторных представлений fastText. Здесь особенно полезным будет метод tSNE, широко используемый для визуализации многомерных данных (Maaten & Hinton 2008; см. также YouTube-видео).

Рисунок 4 (интерактивный). 3D tSNE график векторных представлений UA-строк. Эти представления получены с помощью fastText-модели, обученной без учителя. Каждая точка соответствует UA-строке из тестовой выборки. Цвет точек соответствует типу устройств, выполнявших соответствующие HTTP запросы (голубой - mobile, красный - computer, зеленый - server).


На рис. 4 показан 3D tSNE-график векторных представлений UA-строк из тестовой выборки, рассчитанных с помощью построенной выше fastText-модели. Хотя эта модель был обучена без учителя, она смогла "уловить" важные свойства UA-строк. В частности, на графике хорошо видно разделение точек в соответствии с типом устройств.

Обучение fastText моделей с учителем, конечно же, требует размеченных данных. Существующие парсеры UA-строк могут оказаться здесь как нельзя кстати - с их помощью можно быстро разметить тысячи строк. Алгоритм fastText поддерживает как многоклассовые модели (multiclass models), так и модели с несколькими метками на документ (multilabel documents). По умолчанию метки должны быть представлены в виде __label__<значение>. В таком формате метки добавляют в начало каждого документа (если документ имеет несколько меток, то их разделяют пробелами).

Предположим, что нас интересует векторное представление UA-строк, отражающее тип устройств, с которых выполняются HTTP запросы. На рис. 5 приведен пример размеченных данных, которые подошли бы для обучения соответствующей fastText-модели.


Рисунок 5. Данные, подготовленные для обучения модели fastText с учителем.


Команда для обучения fastText-модели с учителем похожа на ту, что мы уже видели ранее:

m_sup <- ft$train_supervised(
    input = "./data/train_data_sup.txt",
    lr = 0.05, 
    dim = 32L,
    ws = 3L, 
    minCount = 1L,
    minCountLabel = 10L,
    minn = 2L, 
    maxn = 6L, 
    neg = 3L, 
    wordNgrams = 2L, 
    loss = "softmax",
    epoch = 100L, 
    thread = 10L
)

Качество полученной модели можно оценить с помощью стандартных для задач классификации метрик (в частности, precision, recall и f1). Имеется возможность рассчитать эти метрики как для отдельных классов, так и по всем классам одновременно. Так, в приведенном ниже примере метрики качества модели вычисляются для UA-строк, относящихся к классу mobile

metrics <- m_sup$test_label("./data/test_data_sup.txt")

metrics["__label__mobile"]

## $`__label__mobile`
## $`__label__mobile`$precision
## [1] 0.998351
##
## $`__label__mobile`$recall
## [1] 0.9981159
##
## $`__label__mobile`$f1score
## [1] 0.9982334

tSNE-график (рис. 6) также подтверждает высокое качество полученной модели: хорошо видно разделение UA-строк из тестовой выборки на отдельные скопления в соответствии с типом устройств. Это закономерный результат, поскольку модель была обучена с использованием информации именно о типе устройств.

Рисунок 6 (интерактивный). 3D tSNE график векторных представлений UA-строк. Эти представления получены с помощью fastText-модели, обученной c учителем. Обозначения как на рис. 4.


Заключение

В этой статье было показано, как информацию из строк User-Agent можно эффективно представить с помощью векторов ограниченного размера. Модели для расчета таких векторных представлений можно обучать как с учителем, так и без. Модели, обученные без учителя, позволяют получать "универсальные" векторные представления, которые применимы к последующему использованию в любых других задачах машинного обучения. Однако я бы рекомендовал по возможности выполнять обучение с учителем - это даст векторные представления, специфичные для решаемой задачи. Одним из алгоритмов, хорошо подходящих для получения векторных представлений UA-строк, является fastText.

6 Комментарии

edvardoss написал(а)…
Спасибо за статью. Можно ли получить краткий комментарий: почему не "зашли" R-вские пакеты для fastext?
Sergey Mastitsky написал(а)…
С R-пакетами для fasttext приходится много писать дополнительного кода для пост-обработки данных. Но, опять-таки, это субъективное мнение.
edvardoss написал(а)…
Сергей, спасибо за ответ.
Интересует еще один момент: никак не могу найти нормальный алгоритм классификации под следующую задачу: классификация товаров, обучающий датасет - 200 тысяч вариаций наименований (длина каждой строки не более 250 символов) которые сводятся к 50 тысячам классов ("эталонных" продуктов в стандартизованных наименованиях).
Надо предсказывать классы для новых вариаций.
Я двигался по классике: свой велосипедный стэмминг учитывающий особенность задачи, далее ==>> document-term-matrix =>> подсчет TF-IDF ==>> обучение на LibSVM.
Получилось очень громоздко, модель более гигабайта, все медленно.
Насколько подойдет этот алгоритм на Ваш взгляд?
Sergey Mastitsky написал(а)…
Обучить полезную модель для 50 тыс. классов на 200 тыс. примеров у вас вряд ли получится - слишком мало данных для этого. По алгоритмам - возможно, что-то из Spacy (https://spacy.io/) окажется полезным. Можно попробовать и тот же fastText в связке с чем-то простым вроде kNN (например, с реализацией с использованием Annoy (https://github.com/spotify/annoy и https://github.com/eddelbuettel/rcppannoy) для быстрого скоринга). Последний подход на удивление часто хорошо работает - проверено неоднократно.
edvardoss написал(а)…
Спасибо за наводку.
Также нашел интересное исследование по классификации текстов с LVQ
https://scialert.net/fulltext/?doi=itj.2007.154.159&org=11
Sergey Mastitsky написал(а)…
Спасибо, edvardoss - да, интересный подход с LVQ.
Более новые Старые