蘑菇街增量学习番外篇一：动态正则之 tensorflow 中 div 转 mod 设计（含代码实现）
作者：美丽联合集团 算法工程师 琦琦 ，
公众号关注：诗品算法
本文经作者授权转载，转载请联系原作者
文本相关性在蘑菇街搜索推荐排序系统中的应用
蘑菇街首页推荐视频流——增量学习与 wide&deepFM 实践（工程 + 算法）
蘑菇街首页推荐多目标优化之 reweight 实践：一把双刃剑？
0、引言
大家还记得那篇增量学习实践相关的文章吗？很多小伙伴私信我，想要进一步了解流程和设计细节等。感谢大家的信任，我愿将这些干货无私分享。从这篇文章开始，我会将增量学习的设计细节陆续拆分成几篇技术文章分享给大家。美名其曰——增量学习的番外篇系列。对于增量学习整体框架尚不了解的童鞋，建议去翻我的历史文章咯！
1、动态正则
在增量学习中，特征频次的阈值选取十分关键。原因在之前的文章中也有提到过，在此不再赘述。我们设计了一种动态正则方案，通过结合特征在本次增量样本以及历史样本中的出现次数，动态调整模型对该维特征的正则力度。
我们使用特征频次影响L1正则系数，使得不同频次的特征有不同的lasso效果。特征频次和参数估计的置信度相关，特征出现的频次越低，置信度也越低。因此在纯频率统计的基础上增加一个先验分布（正则项），当频率统计置信度越低的时候，越倾向于先验分布，相应的正则系数会更大。
在样本构建流程中，我们会记录每一维特征在当前样本和历史样本中的出现频次，并生成hdfs文件提供给模型训练流程。
2、为何要div转mod？
我们的wide／deep特征在tensorflow中是按照mod方式进行embedding_lookup的，因此Weight tensor对应的L1正则参数矩阵也需要按照mod方式重新排序，保证传给优化器的Weight参数矩阵和L1正则参数矩阵是一一对应的。其中，wide matrix：(feature_size, 1)；deep matrix：(feature_size, embedding_size)。
贴心地将tf中embedding_lookup函数的参数解释摘录给大家：
tf.nn.embedding_lookup函数用于在embedding张量列表中查找ids。此函数用于在 params 的张量列表中执行并行查找。
tf.nn.embedding_lookup(
params,
ids,
partition_strategy='mod',
name=None,
validate_indices=True,
max_norm=None
)
如果输入参数len(params) > 1，ids 的每个元素 id 根据 partition_strategy 在 params 元素之间被分区。在所有策略中，如果 id 空间不均匀地划分分区数，则前(max_id + 1)％ len(params)个分区中的每个分区将再分配一个id。
partition_strategy 是 "mod"：我们将每个 id 分配给分区 p = id % len(params)。例如，13个 id 分为5个分区：[[0, 5, 10], [1, 6, 11], [2, 7, 12], [3, 8], [4, 9]]
partition_strategy 是 "div"：我们以连续的方式将 id 分配给分区.在这种情况下,13 个 id 分为5个分区：[[0, 1, 2], [3, 4, 5], [6, 7, 8], [9, 10], [11, 12]]
查询的结果被连接成一个密集的张量.返回的张量的 shape 为 shape(ids) + shape(params)[1:].
3、div转mod代码
我们先给出暴力解法（无代码），再给出优雅的解法。
顺便提一句，我们会按照模型训练时使用的ps_num（ps个数）来决定需要将参数分成几个分区。比如，13个待训练参数，5个ps，则分成5个分区。feature_size表示特征数量。
- 暴力解法：
将特征对应的L1正则系数按照div方式存储起来：O(n)，然后将上述list存储到二维数组（ps_num * feature_size）中：O(m * n)，二维数组中的第一维表示按照mod方式切分的桶，第二维存储每个桶内的特征index；整体时间和空间复杂度均为O(m * n)。m为ps_num。
- 优雅解法：
思考：我们是否可以只使用一个list存储feature信息呢？
我们需要先计算出，按照mod方式进行分割时，每个分区内应该存储的特征数量，形成一个数组，接着在读取特征频次文件时，将每一维特征按照所设计的mod算法规则，直接映射到数组中的某一位置。这个方案只需要维护一个ps_num维度的list和一个feature_size维度的list即可。所以整体时间和空间复杂度均为O(n)，且无需进行二次遍历。
talk is cheap，show you the code。
- 首先，若将13维特征分成5个分区，那么，每个分区内的特征数量应该为：[3,3,3,2,2]。代码如下：
import random
# 如何将div方式分配的index使用mod方式重新分配
# 将feature index按照mod的方式分到n个ps上
"""
如果 partition_strategy 是 "mod",我们将每个 id 分配给分区 p = id % 分区数.
例如,13个 id 分为5个分区：[[0, 5, 10], [1, 6, 11], [2, 7, 12], [3, 8], [4, 9]]
"""
feature_size = 13
partition_num = 5
bucket_total_num_list = [int(feature_size / partition_num)] * partition_num
for remainder in range(feature_size % partition_num):
bucket_total_num_list[remainder] += 1
print("bucket_total_num_list: ")
print('\n'.join('{}: {}'.format(*k) for k in enumerate(bucket_total_num_list)))
结果：
bucket_total_num_list:
0: 3
1: 3
2: 3
3: 2
4: 2
- 然后，我们得到，每个桶的边界，即，在该桶之前，已经分配了多少维特征，方便后续计算。比如，对于第三个分区来说，前两个分区已经分配了6维特征。代码：
bucket_reduce_sum_list = bucket_total_num_list[:]
bucket_reduce_sum_list[0] = 0
for i in range(1, len(bucket_reduce_sum_list)):
bucket_reduce_sum_list[i] = bucket_reduce_sum_list[i-1] + bucket_total_num_list[i-1]
print("bucket_reduce_sum_list: ")
print('\n'.join('{}: {}'.format(*k) for k in enumerate(bucket_reduce_sum_list)))
结果：
bucket_reduce_sum_list:
0: 0
1: 3
2: 6
3: 9
4: 11
- 最后，我们根据div模式下的feature index，通过index % partition_num得到特征应该被分配到的桶，通过index / partition_num 得到其在桶内的位置。
feat_ret_list = [0] * feature_size
print("div_index -> mod_index")
for index in range(feature_size):
p_assignments = index % partition_num
mod_index = bucket_reduce_sum_list[p_assignments] + int(index / partition_num)
print('{}: {}'.format(index, mod_index))
feat_ret_list[mod_index] = index
print("mod_index -> div_index")
print('\n'.join('{}: {}'.format(*k) for k in enumerate(feat_ret_list)))
结果：
div_index -> mod_index
0: 0
1: 3
2: 6
3: 9
4: 11
5: 1
6: 4
7: 7
8: 10
9: 12
10: 2
11: 5
12: 8
mod_index -> div_index
0: 0
1: 5
2: 10
3: 1
4: 6
5: 11
6: 2
7: 7
8: 12
9: 3
10: 8
11: 4
12: 9
哈哈，算法真是妙不可尽之于言！
4、PS内存优化
这小节跑题了，想提一句ps内存优化的工作，避免小伙伴们未来踩坑。
由于样本构建会产出feature_name（原始特征名）->特征频次的映射关系，而我们做embedding_lookup时，显然是需要使用feature_index去查找的，因此在训练时，需要将feature_name映射为feature_index，feature_name->feature_index这个映射关系存储在另一张表里。我们在模型热启动时，需要同时加载这两张表，非常耗费内存资源。每一张表至少5G，两张表就需要占用10G+的内存资源。因此我们进行了如下优化：
由于我们的特征频次和L1正则参数矩阵等需要在build graph之前计算，因此我将这类计算放在了构造函数中。在流程初始化时，默认所有的PS／chief／worker／evaluator全部都会调用该构造函数进行计算。其实PS和evaluator（用于评估AUC的）显然不需要计算特征频次和L1正则参数矩阵。优化后，我们不再对PS和evaluator调用正则参数矩阵计算方法。这个策略极大地节省了PS的内存。
优化前：20G的PS内存打满；优化后：20G的PS内存利用率10%。
后续增量学习番外篇还将继续更新，关于动态正则以及优化器设计细节，欢迎持续关注 。
原创不易，动动手指双击屏幕点个赞哦！❤️️️
参考：
