machine-learning - Vowpal Wabbit 可能存在哈希冲突

Question

我在 VW 中生成了一个模型，并且还在相同的数据上生成了两个可读模型(第一个带有“--read_model”arg，第二个带有“--invert_hash”)。当我在测试数据集上运行模型并使用 --audit 选项时，某些功能的报告权重与上述可读模型中报告的权重相比略有不同。例如，这是在 train.data 上训练的可读模型的一部分:

213006:-0.19007
213008:-0.692261
213009:-0.203193

如您所见，索引为 213008 的特征的权重为 -0.692261但是，当我在 test.data 上使用 -t 选项和 --audit 选项运行模型时，审计输出中的一些权重会有所不同:

-3.962444   q^featureXY:213008:1:-0.756017

什么可能导致这种情况？我有超过 300k 个特征，这是否可能是由某些哈希冲突引起的？但如果存在哈希冲突，Vowpal Wabbit 不应该报告这一点吗？正如您所看到的，测试时使用了选项 -t，因此模型应该是“稳定的”。

Answer 1

vw允许哈希冲突(故意)

这在文献中被称为“哈希技巧”。

从大量特征中学习时，特征哈希冲突不会被视为错误，因为少量冲突很少会对学习产生不利影响。在许多情况下，较小的冲突率甚至可能有助于降低泛化误差。

忽略碰撞有什么好处？

由于不需要以特殊方式处理冲突，因此哈希技巧的一个明显优点是学习速度更快。

碰撞不会让学习变得更糟吗？

哈希冲突只是创建冲突特征子集的(随机)混合。只要冲突子集是完整特征集的一小部分(当哈希空间足够大时可以预期)，这些冲突充当正则化的随机形式，并且通常(尽管并非总是)有助于避免过度-配件。

如果我的哈希空间太小(冲突太多)怎么办？

如果你有超过 300k 的特征，那确实是一个极端的情况。 300k 大于默认哈希空间大小 (2^18 = 262144)所以碰撞的部分已经不小了。在这种情况下，您应该通过增加 -b <bits> 来增加哈希空间。哪里<bits>高于默认18 .

我怎么知道我是否有太多冲突？

渐进验证错误，由 vw 打印随着它的学习，应该给你一个很好的提示，告诉你什么是最佳的 -b值适用于您的数据集。

您也可以尝试使用vw-hypersearch搜索最佳值。像这样:

    # find the best average loss when using between 19 and 26 bits hash-space
    vw-hypersearch 19 26 vw -b % [other-vw-options...] -d data-set