Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич
Миколов и его коллеги придумали, как можно уменьшить количество параметров в выходном слое сети, для чего ими было предложено два альтернативных метода: отрицательное семплирование [negative sampling] и иерархический softmax [hierarchical softmax].
Рассмотрим их подробнее.
Традиционно выходной слой нейронных сетей, используемых в задачах классификации с более чем двумя классами, применяет функцию softmax для нормализации выходных значений. Поскольку каждое выходное значение мы интерпретируем как вероятность принадлежности объекта одному из классов, то сумма выходных значений сети должна быть равна единице. Функция softmax является обобщением логистической функции для многомерного случая и рассчитывается по следующей нехитрой формуле:
То есть фактически мы делим экспоненту каждого из выходов слоя на сумму экспонент всех таких выходов. Как несложно заметить, для вычисления этой функции нам нужны значения всех выходов слоя. Получается, что при обучении подобных сетей надо вычислить экспоненту для каждого из громадного числа выходов, что весьма затратно. Поэтому при использовании отрицательного семплирования мы отказываемся от нормализации выходов сети, а просто пропускаем каждый из выходов через логистическую функцию. При этом, разумеется, сумма выходов сети перестаёт быть строго равной единице, но, как выясняется, это не влияет на качество полученных векторов признаков.
Далее, вместо расчёта ошибок и последующего обновления весов для всех выходов сети мы выбираем для этого лишь их часть: выход, соответствующий истинной метке класса (т. е. слову, действительно встретившемуся в тексте), и несколько других отобранных выходов, для которых мы хотим, чтобы сеть выдавала 0 (так называемых отрицательных примеров, отсюда и название метода). В статье говорится, что для маленьких датасетов достаточно 5−20 отрицательных примеров, а для больших и вовсе 2–5. Таким образом, при использовании отрицательного семплирования обновлению на каждом шаге подвергается лишь крошечная доля синаптических весов модели.
Отрицательные примеры отбирают случайным образом, но с вероятностями, зависящими от частоты соответствующих им слов в используемом корпусе (т. е. часто встречающиеся слова имеют больший шанс оказаться выбранными как отрицательные примеры, чем редкие). В результате экспериментов Миколов и его коллеги пришли к выводу, что наилучшие результаты получаются при использовании вероятностей, пропорциональных частотам слов, возведённым в степень ¾. Такого рода константы (как и метод отрицательного семплирования) являются характерным примером экспериментальной алхимии в духе школы «грязнуль», которым в значительной мере пропитан весь современный коннекционизм.
Впрочем, прежде чем перейти к столь радикальным мерам, команда Миколова опробовала более математически строгий способ решения проблемы большого количества параметров в выходном слое, получивший название «иерархический softmax». Для этого выходной слой сети был реорганизован весьма оригинальным образом. Для начала словарь был представлен в виде двоичного дерева. Рассмотрим алгоритм, применявшийся для его построения.
Предположим, что наш словарь содержит всего восемь слов: the, of, have, not, hobbit, dandelion, immodest и besieged. Для начала подсчитаем количество вхождений каждого из слов в наш корпус. Допустим, в итоге мы получили следующий набор пар вида (слово; число вхождений): (the; 123), (of; 119), (have; 61), (not; 57), (hobbit; 27), (dandelion; 25), (immodest; 22), (besieged; 19). Возьмём теперь две пары с самым маленьким числом вхождений, в нашем случае это будут пары (immodest; 22), (besieged; 19). Объединим эти пары в единый узел дерева, пусть это будет узел «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, решала обратную задачу, а именно: пыталась по одному слову предсказывать слова окружающего его контекста.
