• • 摘要
  • 前言
  • • 信息的浪费
    • 高度依赖于`Generalization`
    • Motivation
    • 我们的贡献
  • 回顾BF与LBF
  • A Strict Generalization: 自适应学习的布隆过滤器
  • • Simplifying the Hyper-Parameters
    • 分析Ada-BF
  • Disjoint Ada-BF（分离的自适应学习BF）
  • • 简化Hyper-Parameters
    • 分析Disjoint Ada-BF
  • Experiment
  • • 恶意URL检测
    • 病毒扫描
    • Hyper-Parameters调节的敏感度
    • Sandwiched LBF和LBF
  • 阻止实时信息在实时社交媒体上的传播
  • • • Futher
  • 总结
  • 深远的影响

Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier with Application to Real-Time Information Filtering on the Web

自适应学习布隆过滤器（Ada-BF）：分类器的有效利用及其在Web实时信息过滤中的应用 source code

BF: 在允许一定的错误率的情况下，用于判断一个元素是否属于一个集合

FPR： 不存在判定为存在的概率 =p p≠0 {不存在可能判定为存在}
FNR: 存在判定为不存在的概率 =0 {存在一定判定为存在，去重}

摘要

• 起因：通过结合机器学习作为二元分类器来改善 布隆过滤器（Bloom Filter）的性能的同时 没有充分利用predicted probability scores(预测的概率分数)

• 方案：新的算法{使用全谱的分数区域？ the complete spectrum of the score regions. }来实现学习的布隆过滤器

• 优势： 更少的FPR(假阳性False Positive Rate)和内存占用

• 应用： 现实网络信息过滤

前言

approximately test whether a given element (or query) x belongs to a set S
布隆过滤器 可能存在的数据。 广泛应用特别是在内存受限的系统中，

Bloom Filter 确保 0 FNR(假阴性False Negative Rate);不能保证0 FPR{哈希碰撞—> BF的优劣判断标准}

Mitzenmacher[Mit02] 建议使用压缩的Bloom算法来解决次优的空间使用问题，在最优情况下达到了理论下界

为了以最少空间利用来获取更小的FPR，研究者们推广了BF，使用了问题以外的信息来突破理论空间使用下界

• Bruck et al. 使用了query frequency来改变hash 函数的数目

• 最近的研究使用机器学习模型来改善标准BF的表现 通过使用机器学习模型的上下文特定信息来突破FPR的下限

• Rae et al推荐使用神经网络BF,使用分布式写方案来写入内存，相较于经典BF有压缩增益

• Kraska et al使用机器学习模型作为预过滤（对每一个query x一个分数s(x);s(x)通常与x∈S的几率正相关）.

这种假定源于现实中的设置，S中的query可以由x的可观特征中计算得出，并且这些信息也可以由classifier指定的分数s(x)表示（捕获）

将分数s（x）高于预先确定的阈值τ（高置信度预测）的查询x作为正确成员的直接指标。  （设立更高置信区间，低与置信度则进行BF）

Learned Bloom Filter(LBF) 首先使用（可信的）机器学习模型对原始数据进行分类设立标准{s(x)> τ};减少了要进行Hash的数据，同时也降低了FPR。

When s(x) ≥ τ , x will be identified as a key directly without testing with the Bloom filter.

Mitzenmacher之后给出了数学模型来评估LBF的表现;同时又提出了一种广义的sandwiched LBF，在learned oracle之前添加initial filter，以优化选择参数来提高FPR

信息的浪费

does not take full advantage of the predicted probability scores.

对于已有的学习型Bloom滤波器，如果为了获得更小的FPR，分类器得分大于阈值τ的应该有更小的错误率。 (>T 应该都存在)
此外，相当一部分keys应该落在这个高阈值机制中，以确保备用过滤器很小。（>T 直接判定为keys,小于才会加入BF ， 故而为了使BF小，需要大部分数据落在>T范围内）

然而，当分数s（x）小于τ时，分数s（x）中的信息从不被使用。

For instance, consider two elements x1 and x2 with τ > s(x1) ⋙ s(x2).

x1和x2都被加入到备用过滤器中，尽管s(x1) ⋙ s(x2)

高度依赖于Generalization

Assumption: 数据分布不变时预设高置信区间以确保低的FPR

1. However, this assumption is too strong for many practical settings

网上数据流分布变化的；bursty nature with drift in distribution（突发性）

导致置信区间的设置 is not completely reliable.

2. machine learning oracles对adversarial examples的敏感性会给系统带来新的弱点

Bloom filters are commonly used in networks where such increased adversarial FPR can hurt the performance

冲突带来的延迟可能会增加DOS攻击的风险

Motivation

For a binary classifier, the density of score distribution, f(s(x)) shows a different trend for elements in the set and outside the set S.

∈渐进or otherwise

To reduce the overall FPR, we need lower FPRs for groups with a high f(s(x)|x /∈ S).
While for groups with a few non-keys, we allow higher FPRs. 

我们的贡献

不单单依赖于单一的（置信区间）阈值，我们采用了两种算法。

Ada-BF and disjoint Ada-BF, which leverage the complete spectrum of score regions by adaptively tuning Bloom filter parameters in different score regions.

1).
Ada-BF:对不同区域的hash函数数目进行不同的调整，自适应地调整FPR；
disjoint Ada-BF:为每个区域分配可变内存BF。
2).我们的理论分析揭示了一组新的权衡{Hyper-Parameters}，与现有方案相比，我们提出的方案带来更低的FPR。
3).malicious URLs, malware MD5 signatures and fake news tweets, where our methods reduce the FPR by over 80% and save 50% of the memory usage over existing learned Bloom filters.
我们评估了我们的算法在三个实时信息过滤任务上的性能：恶意URL、恶意软件MD5签名和假新闻推文，我们的方法将FPR降低了80%以上，比现有的Bloom过滤器节省了50%的内存使用。

Notations: Our paper includes some notations that need to be defined here.

Let [g] denote the index
set {1, 2, · · · , g}.
We define query x as a key if x ∈ S, or a non-key if x /∈ S.
Let n denote the size of keys (n = |S|),
and m denote the size of non-keys.
We denote K as the number of hash functions used in the Bloom filter.

回顾BF与LBF

Bloom Filter:集合S由R位组成；K个独立的hash函数 h(x)=1 x∈[0，R-1]

It can be shown that if the hash functions are independent, the expected FPR can be written as follows

E(FPR)=(1-(1-1/R)^Kn)^K

Learned Bloom Filter:二元分类模型 + BF
0 FNR； FPR可能来自于分类模型或Hash碰撞

权衡阈值的大小设置{>T的部分含有大部分keys(T小) 那么加入BF的keys就少从而 favorable FPR ;由于我们将区域s（x）≥τ确定为positive，τ的值越高越好,另外T大，增加BF的load负荷}

A Strict Generalization: 自适应学习的布隆过滤器

Ada-BF: where x is divided into g groups based on s(x), and for group j, we use K[j] hash functions to test its membership.

Simplifying the Hyper-Parameters

2g-1个Hyper-Parameters

1. the number of hash functions for each group Kj {g个}
2. the score thresholds to divide groups, τj (τ0 = 0, τg = 1). {g-1个}

E(FPR):

变化情况：。。。。

结论：当分组数j减少时，我们应该线性地增加K[j] (每组的Hash数目)，并且要令m[j] (j组的non-keys数目)呈指数式增加。

简化改变过程：

for j in range(g):
    c=p[j]/P[j+1]
    K[j+1]=K[j]-1 # K[j]-K[j+1] =1

p[j]/p[j+1]=m[j]/m[j+1]=c # ensures p[j] to grow exponentially fast with K[j]

3个Hyper-Parameters: c, Kmin(Kmin=Kg=0 default), Kmax(Kmax=K1)

引理1：
若 1.non-keys的s(x)|x not∈ S 独立同分布于f 
    2.non-keys的训练集是分布f的独立样本
那么 p[j]整体的估计率会随着m的增加而收敛于0
此外 若m> ... 有置信区间 1-@ 那么我们能 p[j]整体的误差估计 < @  <!-- 概率论 -->


意义：只要我们收集到足够多的non-keys来估计p[j]，那么估计误差可以忽略不计。

分析Ada-BF

充分利用了数据的分布密度（g groups）；减小FPR未增加内存消耗

定理1:  给定p[j]/p[j+1]>=c>1  # for j in range(g)

若存在λ>0有cɑ>= 1+λ 并且有 n[j+1] - n[j]>0  # keys numbers

当g足够大并且g<=|2K|  那么 Ada-BF就会比LBF有更小的FPR

K：the number of hash functions of LBF


分析： 此定理要求当p[j]以指数方式减少时，n[j]递增
figure 2:as score increases, f(s(x)|x /∈ S) decreases very fast while f(s(x)|x ∈ S) increases.


结论： 对数据进行更多地分组可以获得一个更好的FPR（少分组则与LBF表现基本相同）

Disjoint Ada-BF（分离的自适应学习BF）

Ada-BF： 分g组，对keys进行hash运算（不同的hash数目）后加入同一个BF
Disjointed Ada-BF 分g组，不同组保存在不同的BF{因此验证存在形式只需要在第j个BF中查询}

简化Hyper-Parameters

Hyper-Parameters:分组依据T；每组BF的长度R[j]

groups: g    m[j]/m[j+1]=c

R[j]  that optimizes the overall FPR

we refer to the idea in the previous section that
the expected number of false positives should be similar across groups.

since the estimated false positive items<estimated overall FPR formula> ,
we prefer <each group FPR formula> to be similar across groups when E (FPR) is minimized.


对于一个有R[j]bits的BF,最佳的hash函数数目 **approximately** 是K[j]=log2  R[j]/n[j]
相应的optimal FPR : E(FPR[j])=u^(R[j]/n[j]  u≈0.618)

分析Disjoint Ada-BF

两种方法的核心思想相同，都是通过降低the groups dominated by non-keys的FPR来降低整体FPR。

disjoint Ada-BF consumes less buckets.
Again, for comparison we need τ of the LBF is equal to τg−1 of the disjoint Ada-BF.

Experiment

Baselines: We test the performance of existing Bloom filter algorithms:

1. standard Bloom filter,
2. learned Bloom filter,
3. sandwiched learned Bloom filter,
4. adaptive learned Bloom filter, and
5. disjoint adaptive learned Bloom filter.

We use two datasets which have different associated tasks,
namely:

1. Malicious URLs Detection and
2. Virus Scan.

Since all the variants of Bloom filter structures ensure zero FNR, the performance is measured by their FPRs and corresponding memory usage.

恶意URL检测

实验

RESULT:机器学习模型有0.93分类的准确率

Ada-BF 和 Disjoint Ada-BF可以达到更低的FPR 和 更少的memory
查询操作都很快很小的差异：每次Hash仅需要10ms（无并行）

病毒扫描

match the file’s signature with the virus signature database

RESULT：分类模型达到了0.98的预测准确度

• 所有的机器学习的BF相比于BF都显示出了极大地优势（FPR is reduced
  by over 98%.）
• Compared with LBF, our methods reduce the FPRs
  by over 80%.
• To achieve a 0.2% FPR, the LBF and sandwiched LBF cost about 300Kb bits, while Ada-BF only needs 150Kb bits

Hyper-Parameters调节的敏感度

our algorithm does not require very accurate hyper-parameter tuning to achieve significant reduction of the FPR.

Sandwiched LBF和LBF

Sandwiched LBF is a generalization of LBF and performs no worse than LBF

一种推广 不比LBF差

how to allocate bits for the initial filter and backup filter to optimize the expected FPR,
their result is based on the a fixed FNR and FPR.

Sandwiched LBF最优化的，当T对应于小的FPR和大的FNR，其中最佳的备份滤波器大小甚至超过了位图的总大小。
Hence, we should not allocate any bits to the initial filter, and the sandwiched LBF reduces to LBF.

另外 随着bitmap大小的增加，最好给initial filter分配更多空间，来展示自己对LBF的更好表现

阻止实时信息在实时社交媒体上的传播

为了应对前所未有的社交媒体产生率，高效的信息过滤系统必须满足以下条件：

1. 一经发现快速通报所有服务器 ensure that once the source of misinformation and its content are identified, this information should propagate to all the servers within a fraction of a second, around the globe.
2. 没有任何计算开销用于处理正确的信息

自然语言处理===> machine learning

Ada-BF and disjoint Ada-BF show significant advantages over the BF and LBF.

• Under the same memory budget, BF and LBF reduce the FPRs by over 70%.
• For the same
  FPR, Ada-BF and disjoint Ada-BF needs half the space of LBF (or sandwiched LBF), effectively
  reducing the communication overhead by a factor of two.

Futher

除了识别fake news是否在集合中，还必须知道查询的新闻和假新闻库中的相似度

但是当前的设计无法处理该任务
Kirsch and Mitzenmacher提出了距离敏感BF,可能会是一种解决方案

Moreover, learned Bloom filters can be easily extended to the distance-sensitive Bloom filter

总结

通过分析和实验证明，显著降低了FPR并且节省了内存的使用

我们设想，我们的工作将有助于并激励将机器学习模型集成到概率算法中。

深远的影响

我们充分利用了二元分类模型的一个共同的观察结果，即预测得分的分布在两类中表现出不同的趋势，而这被以前学习的Bloom Filter所忽略。

我们在理论上和经验上证明了与最新的方法相比，在内存开销和FPR控制方面有显著的性能提升。
与以前的学习BF相比，我们没有提出额外的假设，额外的内存消耗几乎是不存在的。

考虑到我们假设的普遍性和我们算法结构的简单性，我们期望Ada-BF和不相交Ada-BF作为当前学习的Bloom滤波器的替代品。

bloomfilters是一种广泛应用的概率数据结构，用于解决集合成员和相关问题，涉及的领域包括但不限于web和计算生物学。

Bloom过滤器FPR的任何改进都会影响整个互联网的效率和性能。这也会直接影响互联网所有终端用户的生产力和用户体验。

• 生物学应用

在《自然》杂志的论文“所有沉积细菌和病毒基因组数据的超快搜索”中，主要目标是使用Bloom过滤器压缩数TB的DNA序列。

因此，如果正如我们的实验那样，Ada-BF可以节省50%的额外内存，这是一个显著的优势。

最近一个更重要的例子是使用Bloom过滤器进行Covid-19测试[CTV20]。

由于在相同的内存预算下，Ada-BF比标准的Bloom过滤器精确得多，因此我们设想它将有助于大规模Covid-19测试。