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

AlgorithmDog 2017-12-15

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


1. LR 在推荐系统中应用



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

 

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

 

其中 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 的预测公式可以进行下面的推导。

其中ai表示物品 i 中特征加权和, b(k,i) 表示特征用户特征 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:
      person_state = info.person_state
      self.actions = person_state.available_actions
           
def take_action(self):
    rand = random.random()     idx = int(rand * 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 公众号,每次更新会有推送哦。



    本站仅按申请收录文章,版权归原作者所有
    如若侵权,请联系本站删除
    觉得不错,分享给更多人看到

    AlgorithmDog 微信二维码

    AlgorithmDog 微信二维码