《EmFore: Online Learning of Email Folder Classification Rules》论文阅读

此篇论文是算法课需要汇报的论文，虽然汇报时常只有8分钟，但论文肯定是需要精读一遍的，于是就有了下面的内容：

ABSTRACT

现代电子邮件客户端支持基于谓词的文件夹分配规则，可以自动组织电子邮件。不幸的是，用户仍然需要手动编写这些规则。

以前的机器学习方法将自动将电子邮件分配到文件夹视为分类任务，并且不产生符号规则。
以前的归纳逻辑编程（ILP）方法可以生成符号规则，但在电子邮件管理所需的在线环境中学习效率不高。

为了弥补这一差距，我们提出了EmFore，这是一个在线系统，它通过观察来学习电子邮件分类的符号规则。我们成功实现这一目标的关键见解是：

（1）在支持快速确定候选谓词以添加或替换规则中术语的文件夹抽象上学习规则
（2）确保规则与历史分配保持一致
（3）根据现有谓词和文件夹名称的相似性对规则更新进行排名，
（4）构建一个规则抑制模型，以避免表面上低信心的文件夹预测，同时保留规则以供将来使用。

我们在两个流行的公共电子邮件语料库上进行评估，并与13个基线进行比较，包括最先进的文件夹分配系统、增量机器学习、ILP和基于变换器的方法。我们发现EmFore的表现显著更好，更新速度快四个数量级，且比现有方法和基线更为稳健。

1. INTRODUCTION

电子邮件仍然是最重要的数字通信形式之一。专业用户平均每天接收超过100封电子邮件。随着存储成本变得更加便宜，这些电子邮件很少被删除。因此，管理收件箱中的未读和已读电子邮件成为一项耗时的任务。此外，研究发现，花费更多时间在电子邮件上与专业人士感知到的生产力降低和压力指标升高有关。

大多数电子邮件服务提供了经过研究支持的工具，帮助用户管理他们的收件箱。垃圾邮件预测减少了收件箱的混乱。估计电子邮件的重要性帮助用户在Outlook的Focused收件箱和Gmail的Priority收件箱中专注于重要的电子邮件。搜索功能帮助用户快速找到特定的电子邮件。

为了实现更高效的文件夹管理，现代电子邮件客户端允许用户根据简单属性创建规则，将电子邮件移动到文件夹中，例如，主题包含特定短语。这些规则是电子邮件管理的强大工具，但手动编写这些规则对于新手来说可能很困难，对于高级用户来说可能很乏味。

自动将电子邮件分类到文件夹中的研究已经引起了研究界的关注。早期系统基于在训练集上学习，并冻结模型以进行推断。更近期的系统允许更新规则，但这些更新是在大批量数据上进行的，并非实时。这些方法中的许多将分类视为分类任务，并未生成用户可以检查并集成到他们的电子邮件客户端中的符号规则，也就是说用户并不能显示地能看到规则。另一方面，基于归纳逻辑编程的方法确实支持符号规则的生成，但它们并未支持在线学习（即在每封进来的电子邮件后更新规则），这在电子邮件管理设置中是必需的。我们假设这些限制导致了电子邮件客户端中缺乏此类功能。

在本文中，我们介绍了第一个在线系统，该系统通过示范学习电子邮件文件夹分类的规则。我们的系统名为EmFore，它观察用户将电子邮件移动到文件夹中，并为每个文件夹学习一条规则。EmFore可以实时更新规则，以适应每一封新进来的电子邮件，从而允许性能逐步提升。这种方法的灵感来自于在商业产品中成功应用的示例编程范式，如Excel 和Visual Studio。

受到流行电子邮件客户端中规则语言的启发，EmFore学习的规则包含描述电子邮件属性的命题。EmFore使用概括和专门化的方法，通过归纳推理在每封新电子邮件之后更新这些规则。为了高效地做到这一点，我们

（1）创建了一个关于收件箱状态的抽象

（2）设计了一个基于贪婪排名候选谓词的更新算法

（3）使用规则抑制来减少误报的数量

除了生成符号规则和支持在线规则更新之外，EmFore还解决了最近一项关于自动电子邮件分类的调查中突出的以下差距：

(1) 特征空间的动态更新。我们不使用固定的电子邮件特征表示。每封新进来的电子邮件都会生成新的命题，因此在必要时自动扩展特征空间。在传统的电子邮件分类系统中，通常会预先定义一组特征（如发件人、主题、邮件内容中的关键词等），并始终使用这些特征来分类邮件，而EmFore不这样做，而是对每封新邮件都可能生成新的特征（或命题）。这意味着系统能够根据收到的邮件内容动态调整和扩展用于分类的特征集合，使其更加灵活和适应性强。

(2) 降低误报率。误报是指错误地将邮件分类到不应该去的文件夹，EmFore通过分析规则的长度（即规则中包含的条件数量）来判断是否应该应用某个规则。如果一个规则很短，可能意味着它不够具体，因此可能会导致误报。EmFore利用这一点来避免使用可能导致误报的规则。

(3) 概念漂移。用户可以随着时间的推移改变文件夹的范围，这会导致概念漂移。一旦用户检测到错误分类，EmFore会立即更新相关规则，使其与文件夹中的所有邮件保持一致。因此，我们解决了概念漂移的情况，其中范围变得更加广泛。随着时间的推移，用户可能会改变他们使用文件夹的方式，这就是所谓的概念漂移。例如，一个最初用于工作邮件的文件夹可能逐渐开始包含个人邮件。EmFore能够检测到用户的这种行为变化，并立即更新分类规则，以确保规则与用户当前的使用方式保持一致。

(4) 深度学习。我们引入了四种基于深度学习的变换器模型作为基线，这是电子邮件分类任务文献中缺失的方法，并展示了我们的符号规则学习器如何胜过这些基线。变换器是一种强大的神经网络架构，通常用于处理自然语言。EmFore展示了其符号规则学习器在分类准确性上超过了这些基于深度学习的方法。

本文核心贡献：

我们提出了一种新颖的在线算法，用于从少量电子邮件示例中学习电子邮件文件夹分类规则。
我们在两个数据集上对EmFore进行了广泛的评估，包括在线和离线设置。我们发现它在在线设置中的正确决策率比下一个最好的系统（Alecsa）高出多达9个百分点，同时学习速度快达3个数量级。我们在https://github.com/microsoft/prosebenchmarks/tree/main/Emfore发布了EmFore标记的结果，供将来使用。
除了与现有方法进行比较之外，我们还解决了文献中存在的差距，并实现了基于相关任务的四种神经方法。EmFore在正确决策率方面比这些方法高出10 - 15个百分点，同时学习速度快达4个数量级。
我们展示了我们可以在EmFore中配置规则抑制和邮件保留，以降低误报率并适应概念漂移。此外，EmFore可以根据规则的表现力适应不同的电子邮件客户端。

2. PROBLEM STATEMENT

考虑在线环境下，一个有序的邮件流以及所关联的文件夹$(m_1,f_1)…(m_t,f_t)$, 当$m_{t+1}$到达的时候，需要预测与之关联的文件夹$f_{t+1}$，若预测结果不对，则模型允许被重新学习，任何方法都允许在预测错误后从头开始学习模型来再此环境中进行评估。为了支持集成到流行的邮件客户端中，我们考虑模型由这些客户端支持的规则组成。规则是命题逻辑中的一个公式，在这个公式中，命题是根据电子邮件来解释的。如果一个电子邮件满足规则$R$，那么可以写作$m|=R$。

示例1. InFrom("straw") V InTo("straw")，就包含了两个命题，发件人或收件人字段中至少有一个包含straw的电子邮件就满足该规则。

通过对不同文件夹的不同规则进行排序，每封电子邮件都被准确地放入一个文件夹中。设$\mathcal{R}=[R_i,f_i]$，是一个有序的规则-文件夹对列表，其中𝑅𝑖表示文件夹𝑓𝑖的规则，并写作$\mathcal{R}(m_i)=f_i$。如果没有规则适用于一封邮件，那么会默认进入一个特殊的收件箱文件夹。因此，$\mathcal{R}$的最后一个元素总是[true, inbox]。如果$\mathcal{R}$可以准确地将每封电子邮件都分配到正确的文件夹，那么就说明这个规则列表和邮件集合是一致的。

3. APPROACH

我们的系统从数学归纳法中汲取灵感。设 $\mathcal{R}$ 是与当前电子邮件一致的规则集。如果对新电子邮件$m_{★}$的预测 $\mathcal{R}(m_{★})=f$是错误的，然后用户手动将此电子邮件移动到文件夹$f^★$，我们就需要更新规则使其与所有之前的电子邮件以及新电子邮件保持一致。为此，我们引入了三个组件：一个状态$\mathcal{S}$，用于跟踪每个文件夹可能适用的规则或条件；学习$\mathcal{R}$的规则空间；以及一个用于更新$\mathcal{R}$的算法。在接下来的小节中，我们将详细描述每个组件。

3.1 State

状态(State)跟踪每个文件夹$f$的候选命题集合$S_f$，并确保当且仅当$f_i=f$，邮件$m_i$满足所有命题$p\in S_f$，其中$(𝑚_i, 𝑓_i)$表示邮件$m_i$属于文件夹$f_i$。命题由一系列可以匹配邮件的逻辑谓词组成，它们构成了规则的基本构建块。并不是每个命题都必须满足文件夹中的所有邮件，只需要这些命题的组合可以满足文件夹中的邮件就好了。如果某个文件夹的候选命题集合为空，这意味着没有任何命题可以涵盖该文件夹如果系统无法为某个文件夹找到任何有效的候选命题，这意味着没有任何规则可以用来区分应该进入该文件夹的邮件。这可能发生在文件夹的邮件没有明显的共同特征，或者邮件的分类标准太过复杂，以至于系统无法从中提取出有用的规则。所有构造出来但不属于状态的命题（因为它们被多个文件夹中的邮件满足）都保存在一个称为$P_{all}$的有状态变量中。

候选命题是通过用字符串常量替换模板中的占位符$𝑒$来为邮件生成的。表1展示了支持的模板列表以及它们如何生成命题。这些模板是通过选择不同流行电子邮件客户端支持的模板的并集来选定的。

对表格的一些解释：EmFore所支持的命题模板，其中e这个占位符代表的实际上是一个字符串，这个字符串是从邮件中使用一个分词器提取出来的，它会分割所有非字母数字的字符。分数那一列表明了这个命题的重要性，比如例如，具有分数5的命题类型被视为非常重要，而分数为1的则不那么重要。这可能反映了在电子邮件分类时，某些特征（如发件人、收件人、主题）比邮件正文中的内容更加重要。

一些命题举例：这些命题是根据电子邮件的特定属性（如接收者地址）生成的，它们可以作为规则的构建块，用于电子邮件分类系统中。系统会使用这些命题来判断哪些规则适用于当前的电子邮件，并据此将电子邮件分类到相应的文件夹中。

当构建规则时，为了贪婪选择最有希望的候选命题，对每个文件夹的候选命题都进行了排名。这个排名考虑了：

（1）命题中字符串常量与文件夹名称之间的相似性
（2）与该文件夹当前规则的字符串常量的平均相似度
（3）命题的类型。

相似度是通过Jaro-Winkler字符串相似度计算的。每个属性都会产生一个分数，这些分数加起来得到最终的分数。命题模板的启发式分数显示在表1中。最后，我们计算最终命题分数作为个别分数的加权和。第4.5节解释了这些权重是如何学习的。学习到的权重显示，文件夹名称的相似性是最重要的特征，其次是规则常量的相似性。模板分数对最终的谓词排名贡献最少。

举例：Example 3. Given the rule in Example 1 for a folder “straw” the candidates from Example 2 are ranked as follows (from better to worse).

每当一封电子邮件$(m_i, f_i)$进来时，会生成详细的命题$P_i$，我们将这些命题添加到$S_{fi}$中同时保持排名，并从$S_{fj}$中移除它们，其中$𝑓_i ≠ 𝑓_j$，如果一个命题被添加到了文件夹𝑓𝑖的集合中，这意味着它与该文件夹的邮件相匹配。如果这个命题也适用于其他文件夹的邮件，那么它就不能用来区分邮件应该归类到哪个文件夹。因此，为了保持规则的准确性和分类的清晰性，需要从其他文件夹的候选命题集合中移除这些不具区分性的命题。。这个过程发生在我们的规则更新之前，规则更新在下一节中描述，然后处理对现有规则的必要更改。

3.2 Rule Space

我们将每个文件夹f限制到一个单一的规则$R_f$，该规则必须是析取范式（DNF = disjunctive normal form）析取范式（Disjunctive Normal Form，简称DNF）是逻辑学中的一种标准化或规范化的形式，它是用来表示逻辑公式的一种方式。在这种形式中，一个逻辑公式由一个或多个“合取子句”（conjunctive clauses）组成，每个合取子句是一个或多个文字（literals，即原子命题或其否定）的合取（AND操作），而整个公式是这些合取子句的析取（OR操作）,也就是离散数学里头学的那些命题逻辑。由于每个逻辑公式都可以写成DNF，我们并不会失去表达能力。然而，一些电子邮件客户端不能表示所有逻辑公式，因此也无法表示所有规则。我们的算法可以很容易地适应其他形式，例如，我们可以不允许使用否定。我们在评估中研究了表达性（研究问题5）。

为了学习这些DNF规则，EmFore依赖于泛化和特化。假设有一个规则$c_1 ∧ c_2$，其中$𝑐1 = 𝑝1 ∧ 𝑝2，𝑐2 = 𝑝3$。添加析取子句$c_i$会使规则泛化，因为这样可以匹配更多邮件；而添加合取命题$p_i$则会使规则特化，因为它会匹配更少的邮件。在一个与文件夹中所有邮件都一致的最少析取子句的规则中，每个析取子句都有唯一满足它的邮件。我们用$𝑢(𝑐_i)$来表示这些邮件。

请注意，这意味着$𝑢(𝑐_𝑖) / ∪_{𝑗≠𝑖}𝑢(𝑐_𝑗)$是非空的，否则我们可以移除$c_i$，从而为文件夹得到一个更简短的规则。

3.3 Updating Rules

当一封新邮件$(m_★,f^★)$到达时，规则集$\mathcal{R}$中的每条规则$𝑅_𝑓$可能需要更新。完整的算法展示在图2中。如果$𝑚_★$不满足规则$𝑅{𝑓^★}$，即这封邮件不符合文件夹$𝑓^★$当前的规则，那么就需要对规则进行泛化（cover函数，第12-28行）。任何规则$𝑅_𝑓$，其中$𝑓≠𝑓^★$且$𝑚_★$满足$𝑅_𝑓$，意味着不同文件夹$𝑓$的规则错误地覆盖了新邮件，这就需要对规则进行特化（uncover函数，第30-51行）。基于示例学习规则的特化和泛化的思想已经在归纳逻辑程序设计中被探索过。我们将这些思想扩展到电子邮件领域的在线学习系统中工作。

这两个步骤遵循相同的模式：首先尝试替换现有的命题（第15-23行和第36-43行），如果替换失败，才会添加析取（泛化规则）或合取（特化规则）（第24-28行和第45-51行）。候选命题的选择是基于状态中存储的排名，采用贪心算法进行选择。由于替换可以保证规则具有最小数量的析取，因此在泛化一个析取时，我们只需要考虑那些对于所有属于该析取的邮件$𝑚$都满足$𝑚 |= 𝑝$，并且新邮件$𝑚_★$也满足$𝑚_★|= 𝑝$的候选命题$𝑝$（第16行），或者只是新邮件$𝑚_★$满足$𝑚_★|= 𝑝$的情况（第25行）。在特化一个合取时，我们只需要考虑那些对于所有属于该合取的邮件$𝑚$都满足$𝑚|=𝑝$，并且新邮件$𝑚_★$不满足$𝑚_★ ̸ |= 𝑝$的命题$𝑝$（第36行和第46行）。

示例4: 泛化和特化的概览展示在图1中。新邮件被分配到了folder3，但用户纠正了这个错误，它本应该在folder1中。图中展示了替换和扩展步骤，但我们只在找不到替换项时进行扩展。

图1: 对于一封本应满足folder1但实际分配到了folder3的邮件的泛化和特化步骤。首先，我们尝试用状态中的候选命题替换现有命题，使得folder1满足该邮件（泛化）而folder3不满足（特化）。如果没有找到可以替换的命题，我们就通过添加新的析取（泛化）或合取（特化）来扩展规则。

在更新规则的过程中，EmFore尽可能地确保规则与所有过去的预测结果保持一致。如果无法确保一致性，比如因为概念发生了漂移或用户操作失误，那么规则就不会被更新。设计上接受过去预测的过度拟合风险——这样做是为了减少误判的数量，而且如果下一封邮件被移动到文件夹中，规则可以进行泛化处理。规则更新算法在文件夹数量（𝑓）和规则长度（𝑅）上的复杂度是线性的，在谓词数量（𝑃）上的复杂度是指数级的。从理论上讲，这可能导致指数级的复杂性，但由于幂集的构建是按需进行的，实际观察到的复杂性要低得多，这一点在我们的延迟实验（第5.1节）中得到了证明。

3.4 Suppressing Rules

为了缓解那些置信度不高的预测问题，对于每一封新进的邮件，我们会明确预测是否应该抑制对应的文件夹分配。我们的抑制模型使用五个特征的线性组合，并应用sigmoid激活函数来做出预测。这些模型特征包括：

规则的长度
规则连续做出正确预测的次数
文件夹的实时准确率
邮件满足的特定析取的平均实时准确率
以及文件夹的大小

这些权重是通过梯度下降法来优化的。抑制与带有拒绝选项的学习有关，但在我们的应用场景中，我们使用描述的模型来抑制那些由规则生成的预测。算法3详细描述了EmFore如何为新邮件预测文件夹分配。

4. EVALUATION SETUP

在这一部分，我们将描述用于评估EmFore的数据集和设置，以及各种现有的和适应性的基线系统。

4.1 System Specifications

所有实验和研究都是使用Python（版本3.8.7）在一个英特尔酷睿i7处理器（基础频率1.8 GHz）和K80 GPU上进行的，操作系统是64位的，内存为32 GB。

4.2 Datasets

我们在评估中使用了两个数据集。第一个（也是最流行的）是Enron数据集。在删除重复邮件和文件夹后，我们得到了150个用户的2,612个文件夹中的46,096封邮件。第二个是Avocado数据集，在进行了类似的处理后，我们得到了277个用户的3,423个文件夹中的88,172封邮件。

以前的研究常常在Enron–Bekkerman（EB）子集上进行评估，该子集由Enron语料库中邮件数量较多的七个用户组成。为了完整性，我们将报告在这个子集上的一个结果，但我们的方法对于有大量示例的依赖性较小，并且不会因邮件数量的多少而有所区别。

4.3 Setup

我们在以前工作中使用的离线设置和在线设置中评估EmFore。在这两种情况下，每个用户的所有邮件都按时间顺序排列。在离线设置中，使用𝑘%的邮件进行训练，剩余的所有邮件或接下来的10%的邮件用于测试。在前一种情况下，𝑘被设置为不同的值（30, 60和90），并将结果平均以得到单一分数。后一种设置是与Alecsa一起引入的，以便在评估过程中考虑概念漂移。

我们的在线设置旨在更准确地反映用户体验系统的方式。对于每封邮件，系统要么正确地将其放入一个文件夹，要么错误地将其放入一个文件夹，或者中立地将其留在收件箱中，而它本应该在一个文件夹中。记录正确决策（+）和错误决策（−）的比例——其他一切都是中立决策。每当做出错误或中立决策时，系统被允许使用真实标签重新训练。为了避免大文件夹偏见，我们首先按文件夹平均结果，然后跨文件夹平均。

离线设置比较容易理解，就是传统的训练模型，然后预测，在线设置则试图模拟实际用户使用系统时的情况，也就是说系统必须对每封邮件即时做出分类决策。这种设置更能反映系统在实际使用中的表现，包括它如何处理新邮件以及如何随着时间的推移适应用户行为的变化。

4.4 Baseline

我们将EmFore与一系列已发表的系统进行比较，这些系统执行文件夹分类，并使用我们为这项任务适配的流行自然语言处理和分类方法的自定义基线。

决策树、支持向量机、朴素贝叶斯和Winnow是早期应用于电子邮件文件夹分类问题的方法。
Alecsa和ABC-DynF是专为电子邮件文件夹分类设计的最新系统。与EmFore不同，这些系统不为文件夹生成规则。我们按照作者描述实现这些系统。对于Alecsa，由于作者使用的咨询成本、奖励和惩罚超参数不可用，我们进行了网格搜索，并报告了测试的所有参数值中的最佳性能。这些系统在第7节中有更详细的描述。
Popper是一种最先进的归纳逻辑编程系统。我们使用Popper学习每个文件夹的谓词规则。Popper采用了我们在EmFore中扩展的用于在线学习的泛化和专门化的思想。
增量决策树是一种在数据的顺序批次上逐步学习的决策树。与EmFore类似，它也是一个在线学习系统。
约束聚类是一种半监督聚类技术，它使用标记数据生成链接约束，后续指导未标记样本的聚类。我们使用基于K-Means的流行约束聚类技术COP-KMeans。
SentenceBERT是一个流行的句子嵌入模型，针对多个下游语言任务进行训练。我们在其上添加一个分类层，并进行端到端的微调。
KNN-BERT是一种使用KNN分类器优化BERT嵌入以使用端到端模型进行文本分类的最新方法。我们为我们的分类任务微调KNN-BERT模型。我们设置𝜙=0.5，平衡最终预测中的线性和KNN组件。我们测试了3、5和10个邻居，并报告了最佳性能。
对比学习优化不同类别样本之间的分离。我们按照中的描述实现对比损失，并训练BERT嵌入后进行分类。正样本是来自一个文件夹的电子邮件，负样本则取自其他文件夹。
T5是一个在语言上预训练的编解码器变换器。我们微调T5，根据电子邮件的头部、正文和可用的文件夹名称生成目标文件夹名称。
GPT-3.5是最先进的语言模型。像T5一样，我们使用头部、正文和可用的文件夹名称提示模型，并生成目标文件夹名称。

5. RESULTS

我们进行了广泛的评估，以回答以下研究问题。

Q1. EmFore能否快速准确地学习文件夹规则？
Q2. EmFore能否为包含多样化电子邮件的文件夹学习规则？
Q3. EmFore的抑制功能能否减少误报？
Q4. 规则的表达能力如何影响性能？
Q5. 每个文件夹需要存储多少封电子邮件才能在不牺牲性能的情况下更新规则？

5.1 Performance(Q1)

我们的符号学习器在在线评估中做出了更多正确的决策（+）和更少错误的决策（−），如表2所示。在以前工作中使用的离线评估中，EmFore获得了比基线更高的正确决策率。我们强调了EmFore的设计如何实现这一性能。

表2：系统比较。Rules表示系统是否能产生符号文件夹规则。在在线设置中，EmFore做出的正确决策（+）比基线多，错误决策（−）比基线少。为了完整性，我们还展示了在Enron和Avocado数据集上聚合的五种离线设置的正确决策率，如之前工作[10, 17]所做的那样。EmFore在离线设置中也胜过所有基线。星号（*）表示每个用户在五分钟后超时。

EmFore确保规则在所有历史邮件上保持一致。这种一致性，结合抑制功能，即使在学习噪声文件夹的规则时，也保持了低误判率。通过首先执行替换步骤来偏向于简短的规则，并对候选命题进行排名，EmFore防止了对这些历史分配的过度拟合。具有强大泛化能力的方法（如神经网络）或过于贪婪的方法（如决策树）未能保持低误判率。

因为EmFore设计上偏好精确度而非召回率，所以能够从每个错误中学习，导致其正确决策率高于基线。专注于每个错误也有助于解决概念漂移问题，图4展示了一个例子。当用户决定将文件夹的范围从FedEx扩展到一般的快递时，一封邮件就足以让EmFore更新其规则。图5显示了在1、2、5或10封邮件后更新时累积正确决策率（+）。特别是当邮件数量少且用户正在决定文件夹范围时，更频繁地更新规则显著影响未来分类的性能。

EmFore足够快，可以在每次迭代后进行此类规则更新。图6显示了EmFore、最佳神经基线和最佳现有方法的学习时间作为邮件数量的函数。由于EmFore是一个在线系统，我们展示了累积时间和每次迭代所花费的时间。更新规则只需要几分之一秒——比在Alecsa中重新学习快四个数量级。即使是累积的，EmFore也比Alecsa快一个数量级。

表3展示了EmFore为Enron语料库中的用户arnold-j学习的一些简单且易于解释的规则示例。规则的可解释性对于部署至关重要，因为用户应该能够轻松验证和编辑由EmFore生成的文件夹规则。

表3：为Enron用户“arnold-j”的前5个文件夹提供的简单、可检查、易于理解的EmFore规则的示例。

5.2 Variety in Emails

神经方法的一个优势是能够进行语义分类，即用户有明确的意图，但没有规则能够捕捉到它。例如，KNN-BERT在命名为“个人”的文件夹上的文件夹准确率达到68%，而EmFore为61%，Alecsa为54%。这些文件夹的平均命题数量为13，这提供了一些迹象表明EmFore没有捕捉到正确的意图。图7a显示，随着规则中命题数量的增加，正确决策率会下降。

图7：EmFore规则长度与正确决策率和轮廓分数的关系。性能较低和轮廓分数较低的文件夹拥有更长的规则。

我们通过将文件夹视为用户内的簇，并计算它们的轮廓分数（Silhouette score）来估计文件夹中电子邮件的多样性。我们定义两封电子邮件之间的相似性为它们为其生成的所有命题之间的汉明距离。图7b显示，随着学习到的规则变长，轮廓分数下降。

然而，图8显示，与每个文件夹的次优基线相比，EmFore在不同质量的文件夹上更为稳健——在包含大多数文件夹的轮廓分数范围内，得分高出10到15个绝对百分点。

图8：将EmFore和每个文件夹的最佳基线系统根据轮廓分数进行比较。在极端情况下性能相当，但总体上EmFore的表现更好。

图9显示了基于轮廓分数的干净用户（williams-w3）和嘈杂用户（beck-s）的正确决策率。每条红线代表创建了一个新文件夹。对于干净的用户，EmFore迅速学习到了一个好的表示。对于嘈杂的用户，EmFore迅速为一些文件夹学习到合理的规则，但随着用户添加没有一致主题的文件夹，性能下降。

图9：根据轮廓分数，EmFore在Enron-Bekkerman数据集中对于干净用户和噪声用户的累积正确决策率。干净用户和噪声用户之间的性能差距是明显的。

5.3 Supression

为了降低误报率，EmFore能够抑制不可靠的分类是非常重要的。除了我们训练的抑制模型之外，我们还评估了以下抑制策略：

无抑制：不应用任何抑制策略，所有的分类都会被预测出来。
仅预测长度小于特定值的规则：这种策略只接受那些规则较短的分类预测，基于规则长度来过滤可能的误报。
仅预测前𝑘次预测都正确的规则：这种策略只接受那些连续𝑘次预测都正确的规则，利用历史准确性来过滤预测。
神经网络抑制：这种方法使用T5模型对即将到来的邮件和最后10封邮件进行编码，通过交叉注意力机制结合它们，然后将手动特征与结果连接起来，并通过带有sigmoid激活函数的线性层进行处理。

这些策略的目的是在不牺牲太多准确性的情况下，减少错误地将邮件分类到错误文件夹的情况。通过比较这些不同的抑制策略，研究人员可以确定哪种方法最有效地减少误报，同时保持系统的整体性能。

表4显示，基于规则特征训练的抑制模型明显减少了错误移动的数量（-），而没有显著牺牲正确移动的数量（+）。只允许每个规则有一个命题可以减少错误移动的比例（-4.5%），但对正确移动的影响更大（-18%）。在移动邮件之前等待正确的分类会导致错误移动的比例大幅下降，但正确决策率也显著下降。神经网络抑制模型减少了错误移动的比例（-0.3%），但它依赖于一个庞大的模型（6000万参数），这使得推理速度比EmFore慢20倍。

表4：不同规则抑制策略的平均抑制时间、正确（+）和错误（-）决策率。EmFore的抑制模型几乎不影响正确的决策，并且在速度上可以与神经网络模型相媲美，同时显著更快。

图10展示了随着更多邮件的处理，不同抑制方法的正确、中立和错误决策率的变化情况。我们可以看到，EmFore预测中立（无移动）的邮件相对较少（7.3％），因此不像其他变体那样为了减少误报（错误移动）而牺牲覆盖率。要求上一次移动是正确的，以及只允许三个或更少命题的规则，这两者都能保持低错误决策率，但也牺牲了很多正确决策。我们的抑制模型降低了错误决策率，而没有减少正确决策或增加推理时间。基于最后移动的抑制突出显示了EmFore有效地利用了每一个错误，因为无抑制的正确决策率要高得多（+13％）。

图 10: 不同抑制方法下正确、中立和错误决策率的演变。EmFore的抑制策略在保持高正确决策率的同时减少了错误决策的数量。要求之前的分类是正确的（c）以及限制规则长度（d）可以进一步减少错误决策的数量，但这样做会显著减少正确预测的数量。

5.4 Expressivity

不同的电子邮件客户端支持不同的规则，所有这些规则都可以转换成在谓词空间上的析取范式（DNF）。表 5 显示了 EmFore 在受限语法下的正确（+）和错误（-）决策率，以及支持这些规则集的客户端示例。

负面规则很少需要，不允许使用它们并不会显著影响性能（-1.2%）。不使用合取会导致更糟糕的命题被用作析取（-3.5%）。当不允许使用析取时，EmFore 在处理范围更广的文件夹方面变得更糟（-7%）。实际上，所有客户端通过为每个文件夹创建多个规则来支持析取。

表5：EmFore在不同规则语法下的正确（+）和错误（-）决策率，以及使用这些规则语法的流行邮件客户端。完整语法表现最佳。总的来说，这个表格展示了EmFore在不同规则语法限制下的适应性，并且指出了完整语法提供了最好的性能，这表明了在邮件分类任务中灵活的规则语法的重要性。

5.5 Information Retention

我们调查了仅存储文件夹邮件子集的影响。实际上，由于空间限制，邮件客户端不会本地存储所有邮件，而只有一部分邮件在任何时刻可本地访问。为了在客户端部署EmFore，它需要在更新规则时无需访问整个历史记录的情况下保持性能。

在这个实验中，我们将EmFore与最佳基线（Alecsa）进行比较，并限制两个系统只能访问最新的𝑘封邮件。图11显示了随着保留邮件数量的增加，正确和中立决策率的演变情况。我们发现EmFore在正确决策率上始终比Alecsa高出10个百分点。此外，EmFore从存储更多邮件中获得的收益递减得更快（20比40）。这些结果表明EmFore可以在不访问整个邮件历史的情况下有效地更新规则。在现实世界中，由于存储空间的限制，邮件客户端通常不会存储所有邮件的历史记录。因此，EmFore需要能够在不完全依赖历史邮件的情况下，有效地更新和维护其分类规则。

6 RESULT

不幸的是，许多关于电子邮件分类的研究是在私有的工业数据集上进行的。我们的实验是在两个公共数据集上进行的：Enron和Avocado，据我们所知，它们仍然是唯一在研究中广泛使用的公共电子邮件语料库。因此，在具有显著不同特征的语料库上的性能可能会有所不同。

如同在示例编程（PBE）中常见的，EmFore假设用户提供准确的示例以供学习。先前关于PBE的神经方法的研究已经探索了从噪声样本中学习的问题。最近，加权有限树自动机已经被应用于从噪声样本中（符号化地）学习程序。将这些想法扩展并在电子邮件分类规则学习的背景下评估它们仍然是未来的工作。

EmFore背后的方法可能适用于其他领域。具体来说，需要

（1）以在线方式学习简单规则的领域
（2）可以基于元数据或内容的简单句法谓词生成规则的领域。

探索这些领域（例如文档/文件夹分类）仍然是未来的工作。

7 CONLUSION

EmFore是一个在线系统，用于通过观察来学习电子邮件文件夹分类规则。与之前将此任务视为纯粹分类任务的机器学习方法不同，EmFore生成的是现代电子邮件客户端所支持的符号规则。与之前的归纳逻辑编程（ILP）方法不同，EmFore通过使用文件夹状态的抽象来有效更新规则，以在线方式学习规则。为了减少低置信度预测，EmFore使用了一个抑制模型。我们在两个数据集上进行了广泛的实验，并展示了EmFore在性能上超越了14个代表最先进的电子邮件分类系统、机器学习方法、增量学习方法、ILP方法和神经模型的基线。我们的结果表明，EmFore在学习速度上比竞争基线快数个数量级，同时生成的规则能更准确地分类电子邮件。

小结：EmFore本质上是利用了离散数学中的概念和算法来构建电子邮件分类规则。它使用逻辑表达式（特别是以析取范式（Disjunctive Normal Form, DNF）表示的规则）来描述和分类电子邮件。这些逻辑表达式由一系列的命题构成，这些命题是基于电子邮件的元数据或内容的简单语法谓词。

EmFore的工作方式涉及到了以下几个离散数学和计算机科学的关键领域：

逻辑和布尔代数：使用逻辑运算符（如AND、OR和NOT）来构建分类规则。
集合理论：管理和操作电子邮件集合，以及它们与文件夹规则的关系。
算法设计：开发高效的算法来在线更新规则，同时保持对历史数据的一致性。
优化：使用贪心算法和启发式方法来选择和排列命题，以便构建有效的分类规则。
机器学习：虽然EmFore不是一个纯粹的机器学习系统，但它在更新规则时使用了一些机器学习的概念，例如在线学习和概念漂移的处理。

EmFore的创新之处在于它结合了这些离散数学的原理，并将它们应用于在线学习环境中，以生成用户可以理解和验证的符号规则，这些规则可以直接在现代电子邮件客户端中使用。