小米品牌广告引擎和算法实践

2020-02-27 348浏览

1.小米品牌广告引擎与算法实践宋强 MIUI商业产品部
2.
3.个人简介 2014-现在 2011-2014 2005-2011 移动广告平台搜索广告数据库系统架构算法策略数据平台大数据分析实时数据计算反作弊查询优化
4.大纲小米品牌广告业务简介小米品牌广告系统架构小米品牌广告引擎与算法实践 • 流量预估 • 库存分配 • 在线投放
5.小米品牌广告业务简介投放媒体：小米手机和电视全系资源浏览器视频音乐新闻资讯广告样式 ■ 开屏、锁屏、电视画报 ■ 信息流、横幅 ■ 贴片、换肤等业务规模 ■ 日曝光近百亿，年收入几十亿天气日历电视/盒子
6.小米品牌广告业务特点售卖方式 ■ CPT/CPM，提前下单 ■ 合约式，如违约需补量赔偿定向 ■ 用户属性：地域，年龄，性别等 ■ 时间：小时级 ■ 设备型号：手机，电视，盒子等 ■ 内容：视频分类，剧集，CP等 ■ 人群包：包含，排除 ■ 特殊定向：天气状况等频控 ■ 小时，日，周，月第三方监测 ■ 秒针，AdMaster，DoubleClick
7.小米品牌广告系统架构手机/电视广告检索 SSP 日志服务 MAX 效果服务品牌服务外部DSP 实时数据处理在线投放广告售卖广告主排期系统库存分配流量预估离线数据处理
8.流量预估问题描述 ■ 广告主希望购买“2016/12/25 小米视频首页焦点图北京男性”的流量  “日期+广告位+定向条件” 技术挑战 ■ 定向预估：定向条件多样，组合维度庞大 ■ 总量预估：流量随时间和季节变化衡量指标 ■ 流量预估的准确性 ■ 流量查询的效率
9.流量预估 – 系统架构查询接口在线离线定向预估总量数据 Holt-Winters 定向数据 Bitmap/MySQL 数据求和数据采样请求日志评估
10.流量预估 – 算法描述正交算法总量预估单维度分布正交求解 ■ Holt-winters ■ 地域：北京5%，上海3%，… ■ ■ 10万CPM ■ 性别：男75%，女25%，… =10万*5%*75%=3750CPM 预估量（北京，男）位图算法 Y轴：定向维度 X轴：请求 pv_1 pv_2 pv_3 pv_4 … pv_n 北京 0 1 0 1 1 上海 1 0 1 0 0 男 1 0 1 0 0 女 0 1 0 1 1 体育 1 1 0 1 1 财经 0 0 1 0 0
11.流量预估 – 算法评估正交算法 ■ 优点：简单，单维度定向预估准确 ■ 缺点：组合维度定向预估不够精确位图算法 ■ 优点：计算简单（按位与或），组合维度定向预估准确 ■ 缺点：内存占用较大（需进行数据采样） 35000 31000 27000 23000 19000 15000 20161108 20161110 20161112 20161114 20161116 20161118 20161120 20161122 20161124 真实流量正交算法位图算法
12.库存分配问题描述库存男北京 1CPM 上海订单女 1CPM 1CPM 1CPM 1CPM 订单1：北京，2CPM 订单2：女，2CPM 分配方案2：都可以满足分配方案1：订单2无法满足男北京上海男女订单1 订单1 北京订单1 女订单1 上海技术挑战：定向维度多样，订单数据量大，库存分配的最优化求解复杂衡量指标：库存的利用率，库存分配算法的求解速度订单2 订单2
13.库存分配 – 问题建模 s1 : {北京，男} 2CPM 𝑥𝑖𝑗 s2 : {北京，女} 1CPM s3 : {上海，女} 1CPM d1 : 订单1 北京，2CPM d2 : 订单2 𝑑𝑗 表示demand的量 𝑥𝑖𝑗 表示第𝑖个流量节点对第𝑗个订单的分配比例 𝑝𝑗 是订单的缺量损失系数 min 12 𝑠𝑖 𝑖∈Γ 𝑗 𝑉𝑗 𝑥 − 𝜃𝑖𝑗 𝜃𝑖𝑗 𝑖𝑗 2 + 𝑝𝑗 𝑢𝑗 𝑗 女，2CPM 𝑠𝑖 表示supply的量 𝑢𝑗 是订单的未完成量优化目标：播放的平滑程度和缺量损失约束条件需求约束 ∀𝑗 供给约束 ∀𝑖 非负约束 ∀(𝑖,𝑗)∈𝐸 𝑥𝑖𝑗 , 𝑢𝑗 ≥ 0 𝑖∈Γ(j) 𝑗∈Γ(𝑖) 𝑥𝑖𝑗 𝑠𝑖 + 𝑢𝑗 ≥ 𝑑𝑗 𝑥𝑖𝑗 ≤ 1 数学建模是库存分配的核心，问题的求解采用业界成熟的算法（HWM, SHALE）
14.库存分配 - 流程图请求日志流量预估构造二分图订单数据合并定向条件分配算法分配结果 𝑥𝑖𝑗
15.库存分配 - 合并定向条件 ■ 目标：生成最小规模的supply节点，简化分配算法 ■ 算法：为每个维度生成最小互斥散列集合，再进行维度组合订单1：{北京, 上海, 深圳} 订单数据订单2：{北京, 广州, 深圳}, {女} 订单3：{女} 最小互斥集合地域维度：{北京, 深圳}, {上海}, {广州} 性别维度：{男}, {女} {北京, 深圳, 男}, {北京, 深圳, 女} 生成候选节点 {上海, 男}, {上海, 女} {广州, 男}, {广州, 女}
16.库存分配 - 构造二分图 ■ 遍历每一个候选supply节点，检查是否被某demand节点包含 ■ 若不被任何demand包含，则丢弃 ■ 若被某demand包含，记录该supply与demand的关系候选节点 s1 : {北京, 深圳, 男} s2 : {北京, 深圳, 女} s3 : {上海, 男} s4 : {上海, 女} s5 : {广州, 男} s6 : {广州, 女} d1 : 订单1 {北京, 上海, 深圳} d2 : 订单2 {北京, 广州, 深圳}, {女} d3 : 订单3 {女} 二分图的密度=9（边的总数）/15(流量节点数*订单节点数）
17.库存分配 – 维度正交 pv_1 pv_2 pv_3 pv_4 北京 0 1 0 1 1 上海 1 0 1 0 0 男 1 0 1 0 0 女 0 1 0 1 1 体育 1 1 0 1 1 财经 0 0 1 1 1 错误的拆分：维度不正交 s1 : {体育} 4CPM s2 : {财经} 3CPM … pv_n 兴趣属性的取值不唯一正确的拆分：维度正交 d1 : 订单1 s1 : {体育 & 财经} d2 : 订单2 s2 : {体育 & 非财经} {体育} {财经} 2CPM 2CPM s2 : {非体育 & 财经} 1CPM d1 : 订单1 {体育} d2 : 订单2 {财经}
18.库存分配 – 频控问题建模 UV=100 PV=100 UV=100 PV=200 UV=100 PV=300 1 需求约束 ∀𝑗 𝑖∈Γ(j) 𝑥𝑖𝑗 𝑠𝑖 + 𝑢𝑗 ≥ 𝑑𝑗 1 d1 : 订单1 400CPM 供给约束 ∀𝑖 2 d2 : 订单2 频控约束 ∀𝑖, 𝑗 𝑠𝑖 𝑥𝑖𝑗 ≤ 𝑓𝑗 𝑢𝑣𝑖 非负约束 ∀(𝑖,𝑗)∈𝐸 𝑥𝑖𝑗 , 𝑢𝑗 ≥ 0 2 300CPM 3 关键算法 ■ 按照频次对supply节点进行拆分 ■ 在问题建模中引入频控约束 𝑗∈Γ(𝑖) 𝑥𝑖𝑗 ≤ 1 𝑠𝑖 表示supply的量，𝑑𝑗 表示demand的量 𝑥𝑖𝑗 表示第𝑖个流量节点对第𝑗个订单的分配比例 𝑓𝑗 表示第𝑗个广告限制的频次 𝑢𝑣𝑖 表示第𝑖个流量节点的UV量频控约束的含义：每个流量节点可以提供的量，不能超过广告主限制的频次乘以这个流量节点的UV
19.库存分配 – 算法描述 ■ 离线分配算法的优化目标是库存的利用率，分配算法依赖于订单优先级 ■ 多队列优先级：订单可用流量，订单时间等 s1 : {北京} 50CPM s2 : {上海} 100CPM s3 : {深圳} 50CPM d1 : 订单1 {北京, 上海}，150CPM d2 : 订单2 {北京, 深圳}，50CPM 订单优先级：订单可用流量 ( 𝑺𝒋 = 𝒔𝒊 ) 𝒊∈𝜞(𝒋) ■ 订单2优先级高于订单1（S2=100， S1=150） ■ 订单2可以满足，订单1无法满足订单优先级：订单时间 ■ 订单1优先级高于订单2 ■ 订单1和2都可以满足
20.在线投放目标：提高订单的完成率和投放的平滑程度挑战：实际流量和订单完成率偏离预期时，如何快速修正实时反馈是在线投放的核心 ■ 实时流量预估修正 ■ 实时订单完成率反馈小时级模型训练更新手机/电视品牌服务在线投放库存分配模型训练日志服务实时数据处理实时订单完成率实时流量预估
21.在线投放 – 实时反馈实时数据平台数据接入消息队列实时计算数据存储日志服务 Kafka Storm Druid 请求曝光 Druid   实时多维数据分析（OLAP）工具交互式查询，低延迟高可用
22.在线投放 – A/B实验品牌广告A/B实验的特点  在线分配按照 “订单_X_实验”进行保量控制  离线分配算法训练全流量进行，不需要分流量  局限：实验需要按天进行，无法动态调整流量
23.在线投放 – 分析平台订单投放量未完成，如何快速定位问题排期广告分析平台  流量预估问题  支持实时和历史问题排查  分配算法问题  模拟广告请求，获取广告投放关键步骤信息  其他问题  分阶段详细的counting数据
24.