作者：美丽联合集团 算法工程师 琦琦 ，

公众号关注：诗品算法

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 的张量列表中执行并行查找。

1
2
3
4
5
6
7
8

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表示特征数量。

  1. 暴力解法：

将特征对应的L1正则系数按照div方式存储起来：O(n)，然后将上述list存储到二维数组（ps_num * feature_size）中：O(m * n)，二维数组中的第一维表示按照mod方式切分的桶，第二维存储每个桶内的特征index；整体时间和空间复杂度均为O(m * n)。m为ps_num。

  1. 优雅解法：

思考：我们是否可以只使用一个list存储feature信息呢？

我们需要先计算出，按照mod方式进行分割时，每个分区内应该存储的特征数量，形成一个数组，接着在读取特征频次文件时，将每一维特征按照所设计的mod算法规则，直接映射到数组中的某一位置。这个方案只需要维护一个ps_num维度的list和一个feature_size维度的list即可。所以整体时间和空间复杂度均为O(n)，且无需进行二次遍历。

talk is cheap，show you the code。

  1. 首先，若将13维特征分成5个分区，那么，每个分区内的特征数量应该为：[3,3,3,2,2]。代码如下：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
  1. 然后，我们得到，每个桶的边界，即，在该桶之前，已经分配了多少维特征，方便后续计算。比如，对于第三个分区来说，前两个分区已经分配了6维特征。代码：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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
  1. 最后，我们根据div模式下的feature index，通过index % partition_num得到特征应该被分配到的桶，通过index / partition_num 得到其在桶内的位置。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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正则参数矩阵等需�