Bloom Filter Encoding for Machine Learning

技术摘要：用于机器学习的布隆过滤器编码

问题陈述
本文针对机器学习领域缺乏能够同时实现内存效率和数据混淆的通用预处理方法这一问题。现有方法通常仅优化紧凑性或隐私性，很少将两者统一于单一表示中。作者提出了一种方法，利用布隆过滤器变换将原始数据编码为固定长度的位数组，从而在不过度降低预测性能的前提下，减少内存使用并混淆敏感特征值。

方法论
所提出方法的核心是布隆过滤器变换，它将原始样本数据映射为紧凑的固定长度二进制表示（$m$ 位）。该过程包含以下步骤：

1. 分词与量化：连续特征值被量化为离散表示。每个特征被转换为形式为 (特征名，量化值) 的标记（token）。
2. 基于哈希的编码：每个标记使用 $k$ 个确定性哈希函数插入到一个 $m$ 位数组中。哈希函数定义为 $h_i(f, v) = H(f \parallel v \parallel i) \mod m$，其中 $H$ 是确定性哈希（实验中使用了 HMAC-SHA256）。虽然为了可复现性可选用带密钥的哈希，但该方法并不严格依赖于此。
3. 表示：生成的输出是一个固定长度的二进制向量 $b \in \{0, 1\}^m$，独立于原始输入维度。这种编码依赖于布隆过滤器的概率特性，其中碰撞是固有的，但通过管理碰撞来保留近似的相似性结构，而非精确的距离。

作者在六个多样化的数据集（SMS 垃圾邮件、ECG200、Adult 50K、CDC 糖尿病、MNIST、Fashion MNIST）上，使用四种分类器（逻辑回归 LR、极端梯度提升 XGB、深度神经网络 DNN 和卷积神经网络 CNN）评估了该变换。

主要贡献

• 统一表示：本文引入了一种通用预处理表示，通过哈希和碰撞减少内存使用并提供数据混淆，适用于文本、时间序列、表格和图像领域。
• 相似性保留：与显式优化方差或类别可分性的传统降维技术（如 PCA、LDA）不同，布隆过滤器变换保留了近似的相似性结构。具有重叠特征的输入映射到重叠的位模式，使模型能够基于编码空间中的一致模式学习决策边界。
• 灵活的权衡：该方法允许调整过滤器大小（$m$）和哈希函数数量（$k$），以平衡预测性能、压缩比和表示特性（熵和位占用率）。

结果
评估表明，布隆过滤器编码能够实现与原始数据及标准降维技术相当的性能，具体结果因数据模态而异：

• 表格和时间序列数据：该方法通常能达到或略高于原始数据的性能。
  • 在ECG200数据集上，使用 XGBoost 时，准确率从 81.0%（原始数据）提升至 82.9%（+1.9%）。
  • 在Adult 50K数据集上，DNN 准确率从 88.1% 上升至 88.9%（+0.8%）。
  • 在这些领域，在相似的内存约束下比较时，布隆过滤器通常优于 PCA 和 LDA。
• 图像数据：观察到性能下降，这归因于将图像映射到哈希表示时空间结构的丢失。
  • MNIST 准确率从 98.1% 降至 95.1%（-3.0%）。
  • Fashion MNIST 准确率从 90.5% 降至 85.3%（-5.2%）。
• 压缩与效率：该变换提供了持续的内存节省，与原始数据相比，表示大小减少了约 2–4 倍。虽然像 LDA 这样的线性变换实现了更高的压缩比（高达 16.67 倍），但它们带来了更大的性能损失。布隆过滤器提供了一个平衡的折衷方案，实现了适度的压缩（例如在 Adult 50K 上为 2.63 倍），同时在多种情况下保持了比 PCA 或 LDA 更高的准确率。
• 信息密度：熵值范围在 0.38 到 0.68 之间，位占用率范围在 0.13 到 0.60 之间，表明信息密度与碰撞效应之间取得了平衡。

意义与主张
本文主张布隆过滤器编码是一种高效、通用的预处理表示。其意义在于能够：

1. 保留效用：保留足够的结构信息，以便在各种数据类型（特别是表格和时间序列数据）上进行准确的学习。
2. 混淆数据：通过将特征信息分布在位数组中并通过碰撞引入歧义，提供一定程度的数据混淆，尽管作者明确指出这并不构成正式的隐私保证（例如差分隐私）。
3. 实现权衡：提供一种实用的机制，用于平衡预测性能、表示大小和数据混淆，而无需复杂的模型重新训练或特定的领域适应。

作者总结道，虽然该方法需要参数调整，并且可能会降低具有强空间依赖性（如图像）数据的性能，但它为那些在预测准确性之外优先考虑内存效率和数据混淆的场景提供了一种灵活且有效的替代方案。