единый узел дерева, пусть это будет узел «0». Теперь удалим из списка объединённые нами пары и вместо них добавим пару, соответствующую вновь созданному узлу. В качестве числа вхождений будем использовать сумму соответствующих значений для объединённых нами пар. В результате мы получим следующий список: (the; 123), (of; 119), (have; 61), (not; 57), (hobbit; 27), (dandelion; 25), («0», 41). Будем повторять эту процедуру, пока в списке не останется единственная пара, соответствующая корню построенного двоичного дерева:

шаг 1: (the; 123), (of; 119), (have; 61), (not; 57), (hobbit; 27), (dandelion; 25), («0», 41)

шаг 2: (the; 123), (of; 119), (have; 61), (not; 57), («1», 52), («0», 41)

шаг 3: (the; 123), (of; 119), (have; 61), (not; 57), («2», 93)

шаг 4: (the; 123), (of; 119), («3», 118), («2», 93)

шаг 5: (the; 123), (of; 119), («4», 211)

шаг 6: («5»; 242), («4», 211)

шаг 7: («6»; 453)

Использованный нами алгоритм был разработан в 1952 г. и носит название «алгоритм Хаффмана», в честь его создателя Дэвида Хаффмана. Он относится к числу алгоритмов так называемого частотного кодирования и обычно применяется в задачах, связанных со сжатием данных. Дело в том, что дерево, построенное при помощи алгоритма Хаффмана, является визуализацией двоичного кода, позволяющего компактно представлять последовательности, состоящие из элементов, из которых было построено данное дерево. Двоичный код — это последовательность нулей и единиц. В случае дерева Хаффмана для кодирования каждого элемента мы будем использовать код, соответствующий пути, который следует пройти от корня дерева до нашего элемента. При этом 0 будет означать шаг влево, а 1 — шаг вправо. В нашем случае словам из словаря будут поставлены в соответствие следующие коды:

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

При использовании иерархической версии softmax выходной вектор сети имеет размерность, равную числу внутренних узлов дерева Хаффмана, построенного для используемого словаря. В нашем случае таких узлов семь («0», «1», …, «6»). Для каждого компонента вектора мы используем логистическую функцию активации, при этом сопоставление узлов и слов идёт следующим образом: значения в узлах меньше или равные 0,5 интерпретируются как шаги влево в них, а значения больше 0,5 — как шаги вправо. Например, слову hobbit будут соответствовать значения больше 0,5 у узлов «6» и «4» и значения меньше 0,5 у узлов «2» и «1» (здесь сумма компонентов выходного вектора вовсе не обязана быть равна единице). Кроме того, при каждом шаге мы будем обновлять веса только части выходов (узлов) — тех, через которые проходит путь в дереве, соответствующий правильной метке класса. При таком подходе обновления на каждом шаге обычно будут затрагивать не более чем log2N выходов сети, то есть при миллионе слов в словаре среднее число обновляемых выходов не будет превышать 20.

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

Хотя в чистом виде иерархический softmax и проиграл отрицательному семплированию в экспериментах по точности, но благодаря применению алгоритмического трюка под названием «прореживание частых слов» (Subsampling of Frequent Words) ему удалось продемонстрировать наилучшие результаты по сравнению с другими методами[2130].

Однако на этом эксперименты по сокращению вычислительной сложности модели не окончились. Следующая модель, «непрерывный мешок слов» (CBOW), лишилась скрытого слоя. В качестве контекста теперь использовалось восемь слов — четыре предшествующих тому слову, для которого строился прогноз, и четыре следующих в тексте за ним. Кроме того, если раньше на вход сети попадала конкатенация векторов признаков различных слов контекста, то теперь на вход поступал усреднённый вектор признаков для всех слов контекста. Именно из-за этой особенности модель и получила своё название, поскольку порядок слов контекста в ней игнорировался так же, как он игнорируется при использовании классического «мешка слов». Вторая модель, получившая название Skip-gram, решала обратную задачу, а именно: пыталась по одному слову предсказывать слова окружающего его контекста.

Благодаря относительной легковесности модели CBOW и Skip-gram оказались способны обучаться на гигантском корпусе Google News (около 6 млрд слов) при размере словаря в миллион слов. При использовании одного CPU на одну эпоху обучения уходило при этом не более суток.

Миколов и его коллеги опробовали различные размерности эмбеддингов (размерностью эмбеддингов часто для простоты называют число компонентов векторов признаков) — 50, 100, 300, 600 и даже 1000. Обучив несколько моделей, авторы исследования сравнили свойства полученных векторов с векторами, построенными в экспериментах других исследователей, а также с векторами из более ранней работы[2131] Миколова. Дело в том, что ещё за год до рассматриваемых нами исследований Миколов предложил усовершенствовать сеть Бенджио, сделав её рекуррентной, чтобы в дополнение к поступающему на вход на каждом шаге вектору, соответствующему очередному слову текста, сеть использовала также информацию из своих предыдущих состояний. Для обозначения модели Бенджио (в том числе её различных усовершенствованных версий) Миколов и его коллеги используют аббревиатуру NNLM (Neural network language mode, Нейросетевая языковая модель), а для обозначения её рекуррентной версии — аббревиатуру RNNLM (Recurrent neural network language model, Рекуррентная нейросетевая языковая модель).

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

Весьма занимателен вопрос о том, почему авторы word2vec использовали косинусное расстояние, а, например, не обычное евклидово. Дело в том, что косинусное расстояние игнорирует длину векторов, то есть если мы умножим любой из векторов, для которых рассчитывается расстояние, на некоторый скаляр, то косинусное расстояние между этими векторами не изменится. Именно поэтому косинусное расстояние часто используется в ситуациях, когда компонентой вектора является, например, число вхождений слова в некоторое множество документов; как раз такие векторы применяются в латентном семантическом анализе. Не исключено, что Миколов и его коллеги просто взяли привычную метрику, по крайней мере в их статьях нет объяснения использованию именно косинусного расстояния. Впрочем, более поздние исследования[2132], [2133], [2134] показали, что длина вектора признаков слова в word2vec связана с частотой слова, поэтому при использовании евклидова расстояния синонимы, значительно разнящиеся по числу вхождений в обучающую выборку, могут оказаться достаточно далёкими