Vowpal Wabbit: Какая именно хэш-функция используется?

Основной хэш-функцией является 32-битный Murmur Hash v 3.0 от Остина Эпплби.

Однако он включен с небольшим изменением API по сравнению с исходным uniform_hash, чтобы адаптировать его к различным сценариям использования в vw.

Вы можете посмотреть исходник по адресу:

• https://github.com/JohnLangford/vowpal_wabbit/blob/master/vowpalwabbit/hash.cc
• https://github.com/JohnLangford/vowpal_wabbit/blob/master/vowpalwabbit/hash.h
• https://github.com/JohnLangford/vowpal_wabbit/blob/master/vowpalwabbit/parse_primitives.cc (ищите функции hashstrings и hashall)

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

Вот (возможно, не на 100% полный) список деталей:

• После хеширования всегда есть операция по модулю, основанная на текущем значении битов (-b bits, по умолчанию 18), чтобы соответствовать вектору веса, поэтому значение, которое вы получаете из хэша, может быть меньше, чем прямой/наивный хэш.
• vowpal wabbit поддерживает (стиль SVMlight) числовые имена функций, где вы можете использовать числовые «конечные» значения напрямую, а не хэш. По умолчанию (--hash strings) имена функций, начинающиеся с цифры, изначально используются как есть (без хэша), но если они продолжаются с некоторыми нецифрами, текущее вычисленное значение используется в качестве начального значения, а остальная часть имя мурмур-32-хэш
• Когда пространство имен существует, хэшируется полная строка: namespace^featurename
• Когда используются параметры взаимодействия с пространством имен (--redefine, -q, --cubic и т. д.), два результата хеширования объединяются с другим более простым хэшем.
• В некоторых редукциях, таких как --search, при подаче murmur-hash используется конкретное (не нулевое) начальное число (см.: vowpalwabbit/search.cc), поэтому вы можете получить значение хеш-функции, отличное от ожидаемого.

В случае сомнений вы можете использовать опцию --audit, и vw выведет точное хэш-значение каждой функции в каждом примере. Формат такой (пример):

#
#    UserJack1^mean_karma:3864409:0.12345:0.919323[@3.8964]
#    ^^^^+^^^^ ^^^^^+^^^^ ^^^+^^^ ^^^+^^^ ^^^^+^^^ ^^^+^^^
#        |          |        |       |        |       |
#    namespace featurename hashval value   weight Sum(gradients)
#