一个特殊场景的 LR 预测优化 Trick

      推荐系统常用分类算法包括 LR、XGBoost 和最新的 Deep Learning 。libFM 可以看出是自动特征交叉和 LR 算法的结合。XGBoost 在竞赛中用得多,但在实际工业中鲜见其成功案例。Deep Learning 则是未来可能成为 CTR 预估范式的新兴算法,但现在受限于成本和性能。LR 作为老牌工业推荐系统中算法,至今活跃在一些推荐场景中。

1. LR 在推荐系统中应用

       给定实例 x, LR 算法计算该实例为正样本的概率,如下所示。

(1)   \begin{eqnarray*} p = \frac{1}{1+\exp(-wx)} \nonumber \end{eqnarray*}

其中 w 是 LR 的参数。LR 算法的训练过程是,最小化在训练数据中预测概率和真实标签之间的区别。

(2)   \begin{eqnarray*} w = argmin_{w'}\sum_{i=0}^{N}loss(p_i,t_i) \nonumber \end{eqnarray*}

其中 p 是 LR 的预测值,t是真实标签。这个无约束最小化问题,可以用一系列梯度相关的算法进行求解。

      推荐系统的职能是向用户 (u) 推荐其感兴趣的物品 (i)。转换成机器学习问题,给定 u,i 预测是否感兴趣 tag。因此 LR 输入的特征向量 x=(u的特征,i的特征, u 和 i 的交互特征),输出用户 u 对物品 i 感兴趣的概率。

      推荐系统有一种简单的架构:线下计算好所有预测结果(广告和推荐系统部署机器学习模型的两种架构)。具体过程如下所示:1)在线下,从用户和广告(物品)属性抽取用户和物品特征,将抽取的特征合并进日志生成训练数据,训练机器学习模型;将几乎所有可能的请求合并特征,进而生成预测实例,用模型得到预测结果;2)线上就很简单了,接入线下传过来的预测结果。因此物品系统的预测结果 “userid,adid1,adid2…,adidn” 上载到线上,一旦线上传一个 userid 请求展示广告,线上模块就按照一定的逻辑返回预测结果中这个用户对应的物品。

这种架构需要提前计算所有可能的情况,预测的计算量比较大。在物品特征不是很多 (小于500) 和用户特征数不是很多 (千万级) 的场景, 我们可以优化 LR 的预测,减少预测的计算量。

2. 特殊场景的 LR 预测优化

       在物品特征不是很多 (小于500) 和用户特征数不是很多 (千万级) 的场景, 我们可以优化 LR 的预测。LR 的预测公式可以进行下面的推导。

(3)   \begin{eqnarray*} &&p(u,i) \nonumber \\ &=& sgmoid(\sum_{k \in ufeat} f^{k} w^{k}  + \sum_{k \in ifeat} f^{k} w^{k} + \sum_{k1,k2 \in u\_i\_feat} f^{k}\_f^{k1} w^{f^{k}\_f^{k1}}) \nonumber \\ &=& sgmoid(\sum_{k \in ufeat} f^kw^k + \sum_{k \in ifeat} f^kw^k + \sum_{(k \in ufeat)}\sum_{(k1 \in ifeat)} f^{k}\_f^{k1} w^{f^{k}\_f^{k1}}) \nonumber \\ &=& sgmoid(\sum_{k \in ufeat} f^kw^k + a_i + \sum_{k \in ufeat} b_{k,i} )\nonumber \\ \end{eqnarray*}

其中\(a_i = \sum_{k \in ifeat} f^kw^k\) 表示物品 i 中特征加权和, \( b_{k,i} =\sum_{(k1 \in ifeat)} f^{k}\_f^{k1} w^{f^{k}\_f^{k1}}\) 表示特征用户特征 \(f^{k}\) 和物品 i 中特征的交叉特征的加权和。 这两个加权和的权重都是由 LR 模型提供。在物品特征不是很多 (小于200) 和用户特征数不是很多 (千万级) 的场景下, \(a\) 容量等于 200, \(b\) 的容量为十亿量级, 我们可以在内存保存一份 \(a\) 和 \(b\),预测的时候直接获取就可以了。经过这样优化,计算用户和物品 p 值的复杂度为从 O(num_ufeatures * num_ifeatures) 减为 O(num_ufeatures)。 当然,这个 Trick 是以牺牲空间为代价的,是典型的 “空间换时间” Trick。 针对内存使用过大的情况,我们可以做一些妥协,比如只保存高频用户特征的 b。

      我们在我们部门的业务中做实验。该业务的推荐场景,有 4 亿用户,80 个物品。如果完全展开,需要对 4*80 = 320 亿条数据进行预测。我们用 Spark 实现了程序,用了 200 cores。实验得到了如下结果。

从上面的表格,我们可以看到,优化之后性能得到了极大提升。优化前,LR 需要 20 个小时才能完成 320 亿条数据的预测;优化之后,LR 只需要 10 分钟就完成了 320 亿条数据的预测;耗时减为原来的 120 分之一。

3. 总结

      我们的业务碰到了一个很特殊的场景:用户数量巨大,上亿;物品数目比较少,不超过 500 个。针对这个特点,我们设计了一个小程序 Trick。这个程序 Trick 极大地提高了 LR 的预测性能,预测耗时减为原来的 120 分之一。

      目前我在和小伙伴们开发非完美信息游戏 AI 环境:RoomAI,所以无力保持两周一次的更新频率。向期待更新的大伙说一声对不起,希望后续稳定两周一次的更新。RoomAI 的目标是提供一些非完美信息游戏环境和一些基线模型算法,方便 AI 开发人员快速地构建、测试和对比自己的非完美信息游戏 AI 算法。目前 RoomAI 已经支持德州、梭哈和七鬼,基本流程如下所示:玩家 AI 获得游戏环境给出的信息,当前玩家 AI 选择合适的动作,游戏环境根据该动作推进游戏逻辑;重复上述过程,直到分出胜负。

      RoomAI 的用法也是简单明了,下面是一个随机玩家的示例。


from roomai.kuhn import *;
import roomai.common
import random

#### Define your player Bot ####
class KuhnPokerExamplePlayer(roomai.common.AbstractPlayer):
    def receive_info(self, info):
        if info.person_state.available_actions is not None:
            self.actions = info.person_state.available_actions
           
    def take_action(self):
        idx = int(random.random() * len(self.actions))
        return list(self.available_actions.values())[idx]
        
    def reset(self):
        pass

if __name__ == "__main__":
    #### init ####
    env     = KuhnPokerEnv()
    players = [KuhnPokerExamplePlayer() for i in range(2)]

    #### playing ####
    scores = KuhnPokerEnv.compete(env, players) 
    print (scores)      

       如果对 RoomAI 项目有兴趣,欢迎同学们关注并 Star。

       欢迎关注 AlgorithmDog 公众号,每次更新会有推送哦。

weixin_saomiao
此条目发表在编程开发分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。