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

Question

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

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

有谁知道 VW 中到底使用了哪个哈希函数？

Answer 1

核心散列函数是 Austin Appleby 的 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）的模运算以适应权重向量，因此您从散列中获得的值可以小于直接/朴素散列。
• vwappal wabbit 支持（SVMlight 风格）数字特征名称，您可以在其中直接使用数字“最终”值而不是哈希值。默认情况下 ( --hash strings)，以数字开头的特征名称最初按原样使用（无散列），但如果它们继续使用一些非数字，则到目前为止计算的当前值用作种子，名称的其余部分是 murmur-32-hash
• 当命名空间存在时，散列的完整字符串是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)
#