Vowpal Wabbit：具体使用了什么哈希函数？

Question

我真的很想知道 Vowpal Wabbit 中使用哪个哈希函数进行特征哈希。

我知道底层算法是 Murmurhash 3，但我无法通过查看 github 上的 VW 代码来了解详细信息。

有谁知道VW到底用的是哪个哈希函数？

Answer 1

核心哈希函数是 Austin Appleby 的 32 位 Murmur Hash v 3.0。

但是，它与原始 uniform_hash 相比略有 API 变化，以适应 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 函数）

正如你所看到的，当你深入细节时，事情并不那么简单。它不简单的原因是，在某些地方，当特征和名称-spaces 在交互和一些缩减算法中结合时，需要付出额外的努力来改善分散。

这是一份（可能不是 100% 完整的）详细信息列表：

散列后总是有一个基于当前位值（-b bits，默认为 18）的模运算，以便适合权重向量，因此您从散列中获得的值可以小于straight/naive哈希。
vowpal wabbit 支持（SVMlight 样式）数字特征名称，您可以在其中直接使用数字 "final" 值而不是散列。默认情况下 (--hash strings)，以数字开头的特征名称最初按原样使用（无散列），但如果它们继续使用一些非数字，则到目前为止计算的当前值用作种子，并且名称的其余部分是 murmur-32-hashed
当名称-space 存在时，被散列的完整字符串是 namespace^featurename
当使用名称-space 交互选项（--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)
#

Vowpal Wabbit：具体使用了什么哈希函数？

Vowpal Wabbit: What hash function is used exactly?

hash

vowpalwabbit