他山之玉——神经网络包分类

数据包的分类是互联网的基础。本文一反盲目追随深度学习的热潮，将深度学习用于改良传统的决策树生成，获得了显著的成效。

包分类是从一族给定的规则中选出匹配规则。传统方案分为 TCAM等硬件方案（速度快，价格昂贵，难以推广）和决策树生成算法。软件实现灵活且成本低廉，但依赖于手工调试，普适性差。由于内部多基于贪心算法，无法显式的实现全局最优化，故效率往往不尽如人意。

近年来，大批研究者开始应用学习类算法来革新各自的领域。本文的亮点在于，作者没有生搬硬套，通过挖掘共通点，在传统算法的基础上，利用学习算法优化决策树的生成，最大程度发挥了强化学习的威力。强化学习可以看作人与自然的互动中逐步进化的过程。表示环境，表示人的动作，表示反馈。如图，通过设置，可以显式地设置最优化的目标函数。通过定义不同的，可将传统的算法嵌入到强化学习框架中。

保留决策树算法，首先是因为传统算法已有大量研究，可以利用已有成果。决策树作为确定性算法准确率高，可以满足分类的需求。

在实现上，作者面临三个挑战。一是编码问题，即如何将动态变化的决策树转化成合法输入。由于子树的生成仅依赖于其根节点，因此只需要对当前节点进行编码。二是回馈的延迟性导致树的生成过慢。利用树的递归特性，即树的时间复杂度取决于根节点和子树中的极值，将不定长的决策链简化成单步决策来加快收敛。三是算法的超大规模部署，这里采用成熟的函数库RLlib。

本文通过分析新方法的特点和本领域的痛点，将两者合并成一个系统。作者仅设计了一套框架，将具体算法的选择权交给了使用者，提升了系统的潜力和生命力。对于如何将深度学习和传统算法集成起来，提供了很好的示范方案。

更多技术细节参见论文：Eric Liang, Hang Zhu, Xin Jin, and Ion Stoica. Neural Packet Classifcation. In ACM SIGCOMM 2019.

编辑：王晓宇