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

公众号关注:诗品算法

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