一个特殊场景的 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 的预测。ID 类用户特征不考虑的话，如果离散化和 dummy 化平均分十桶，十万用户特征相当于一万个用户属性（相当于用户表有一万列）。这已经很大了。一般我们说千万甚至上亿特征，大量来自于用户和物品特征的交叉，就是我们下面要处理的。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*}

其中ai=∑k∈ifeatfkwkai=∑k∈ifeatfkwka_i = \sum_{k \in ifeat} f^kw^k 表示物品 i 中特征加权和， bk,i=∑(k1∈ifeat)fk_fk1wfk_fk1bk,i=∑(k1∈ifeat)fk_fk1wfk_fk1 b_{k,i} =\sum_{(k1 \in ifeat)} f^{k}\_f^{k1} w^{f^{k}\_f^{k1}} 表示特征用户特征 fkfkf^{k} 和物品 i 中特征的交叉特征的加权和。 这两个加权和的权重都是由 LR 模型提供。在物品特征不是很多 (小于500) 和用户特征数不是很多 (十万级) 的场景下, aaa 容量等于 500, bbb 的容量为千万量级, 我们可以在内存保存一份 aaa 和 bbb，预测的时候直接获取就可以了。经过这样优化，计算用户和物品 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)]