经典算法与深度学习 在外卖物流调度中的应用 SPEAKER / 徐明泉 百度外卖首席架构师 引言：外卖配送的背后 2 引言：外卖订单调度系统要考虑的因素 3 订单相关 骑士相关 • 商户、用户位置 • 用户期望时间 • 预计出餐时间.. • 现有订单的配送路线 • 新增订单后配送路线的改变情况 • 历史取送餐速度 • 完成每个订单的预计时间 • 熟悉的区域 • 配送工具 外卖订单的智能 调度系统 一. 智能调度系统的 大数据分析监控 二. 智能调度系统中 的人工智能 三. 提纲 5 外卖订单的智能 调度系统 一. 智能调度系统的 大数据分析监控 二. 智能调度系统中 的人工智能 三. 外卖订单智能调度系统发展历程 6 人工派单模式 • 调度员根据订单地址和骑士 位置来进行订单分配 • 人力调度派单峰值为每人 800单/天 调度 系统 3 整体最优分配 调度 系统 4.0 深度学习智能模式 • 出餐时间估算更准，缩短 骑士到店等待时间，节省 运力，提升用户等餐体验 出餐时间预估 深度学习智能 调度 系统 2.0 系统派单模式 • 系统综合考虑配送距离、 骑士运力、期望送达时间 等因素来自动派单 配送距离 期望送达时间 骑士运力 订单相似度 调度 系统 1.0 外卖订单智能调度要解决的核心问题 7 调度系统算法

3 在线机器学习-参数服务器 • 参数规模 • 支持百亿特征维度，千亿参数 • 模型版本 • 多模型多版本：多组实验并行执行，提高实验迭代效率 • 在线版本切换：基于ZK的版本感知机制，动态进行版本切换，实现BASE模型的热更新，实时训练与离线训练周期模型融合 • 模型结构训练与推理兼容：在线PS与离线PS模型结构兼容，自动模型参数转换 • 稳定性优化 • 模型快照：基于ps-s kubernetes/ol-submit RPC服务框架 LR/GBDT DNN/DeepFM/W&D 负载均衡/统一版本管理/动态加载/批量化机制 特征映射 Embedding 数据处理 异构GPU集群 CNN 业务应用 模型服务 框架 排序模型服务 多媒体分析服务 自然语言分析服务 集群调度层 核心架构层 算法模型层 4 深度学习-分布式模型推理 • 推理性能优化 • 减少计算量： operator batching/TensorRT/MPS/SSE/AVX/Neon • operator fusion • 针对特定场景重写耗时算子 • 重构tensorflow计算引擎 • batching • 批量调度请求到GPU，增大并发和吞吐量 4 深度学习-分布式模型推理 • 深度特征效果对比 • 文本Embedding特征，相比于文本标签，相关指标提升约3+% • 基于word2vec、bert等

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 9.4.1 隐马尔可夫模型中的动态规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 9.4.2 双向模型 . . . . . . . . . . 4.1 随机梯度更新 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451 11.4.2 动态学习率 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453 11.4.3 凸目标的收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491 11.11 学习率调度器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493 11.11.1

TensorFlow使用现状及痛点 • ⼿动分发训练样本� • ⼿动拉取训练模型� TensorFlow使用现状及痛点 • 多⼈多服务器使用混乱，计算资源如何划分？� • 没有GPUs集群资源管理和调度（内存、CPU、GPU、 端⼝），集群资源负载不均� • 训练数据⼿动分发，训练模型⼿动保存� • 进程遗留问题，需要⼿动杀死� • 缺乏作业统⼀管理，不便对作业运⾏状态跟踪� • 日志查看不⽅便� 序� • 支持GPU资源管理和调度� • 不再需要⼿动配置CluserSpec信息，仅需要设置work 和ps的数量� • 训练数据和训练模型基于HDFS统⼀存储� • 作业训练结束自动回收work、ps和Tensorboard进程� • 训练效果和性能没有损失� 基本目标：� TensorFlow on Yarn设计 • 支持GPU亲和性调度（提⾼通信效率）� • Web的⽅式查看作业的运⾏状况和作业日志� ：� TensorFlow on Yarn技术细节揭秘 TensorFlow on Yarn系统架构图：� TensorFlow on Yarn技术细节揭秘 Yarn支持CPU调度 vs GPU调度：� CPU GPU 每个NodeManager配置可用CPU核心 数量 每个NodeManager配置可用GPU卡数 量 ResourceManager统计计数并按数量 分配

*示意图来自互联网 Kubernetes在异构系统调度中的挑战 • Kubernetes版本发布快，新特性更新频繁，对异构调度的支持不断加强；但配套设施落后（e.g. Spark on K8s, GitlabCI) • 容器系统调用栈深，需要仔细验证操作系统，内核及异构设备驱动的兼容性 • Kubernetes对NUMA、异构计算、存储设备的调度能力待加强 1.6 nvidia/gpu custom

agent App 2 PS Job 1 App 2 App 3 SSH Job 1 Train Job 1 Val Job 2 WK Job 2 WK Job 3 监控/启停 任务调度/资源管理 监控上报 cephfs存储集 群 本地文件系统 数据 模型/日志 client 管理数据 提取模型、 查看日志 提交/管理任务 用户 docker.oa.co m 自动拉取镜像 运维工具化，快速屏蔽/启动异常机器 • 灵活的资源分配 • 支持以 GPU 或节点为粒度进行资源分配 • 用户配置任务所需最小资源 • 自动扩缩容，最大化资源使用率 • 支持不同计算框架 • 调度与任务松耦合，用户可以灵活定义任务 • 支持配置 docker 镜像，完全自定义运行环 境 • 良好的用户体验 • 完善的客户端工具 • 任务进度微信提醒 SACC2017 proto

3 1. 相关概念 01 认识Python 01 相关概念 02 特征构建 03 特征提取 04 特征选择 4 许永洪,吴林颖.中国各地区人口特征和房价波动的动态关系[J].统计研究,2019,36(01) 文献解读 定义 目的 作用 是把原始数据转变为模型的训练数据的过程 获取更好的训练数据特征，使得机器学习模型逼 近这个上限 ➢ 使模型的性能得到提升 度。于是诞生了机器学习界的 名言： 成功的机器学习应用不是 拥有最好的算法，而是拥 有最多的数据！ 数据决定一切 数据大小 准 确 率 1. 相关概念 6 许永洪,吴林颖.中国各地区人口特征和房价波动的动态关系[J].统计研究,2019,36(01) 项目 特征提取 特征选择 共同点 都从原始特征中找出最有效的特征 都能帮助减少特征的维度、数据冗余 区别 ➢ 强调通过特征转换的方式得 到一组具有明显物理或统计 特征提取VS特征选择 1. 相关概念 7 2. 特征构建 01 相关概念 02 特征构建 03 特征提取 04 特征选择 8 许永洪,吴林颖.中国各地区人口特征和房价波动的动态关系[J].统计研究,2019,36(01) 特征构建：是指从原始数 据中人工的找出一些具有 物理意义的特征。 方法：经验、属性分割和 结合 操作：使用混合属性或者 组合属性来创建新的特征 ，或是分解或切分原有的

?? = 1 20 3.静态图与动态图 •动态图：运算与搭建同时进行 •静态图：先搭建图，后运算 根据计算图搭建方式，可将计算图分为动态图和静态图 PyTorch 是支持动态图的，可以在进行运算的同时进行 TensorFlow 是支持静态图的，需要在计算之前，先进行搭 建（ TensorFlow 2.X引入了动态图 ） 21 4.静态图与动态图 TensorFlow:先搭建所有的计 TensorFlow:先搭建所有的计 算图之后，再把数据输入进去 PyTorch:动态图的搭建是根据 每一步的计算搭建的 创建图 运行每次迭代 每次迭代中创建图 22 4.静态图与动态图 23 4.向量化 02 梯度下降 01 二分类与逻辑回归 03 计算图 04 向量化 24 4.向量化 非向量化版本的for循环花费了大约718 毫秒，向量化版本花费了大约33毫秒。 举例：如果你想计算向量

如何高效高精度地处理大尺度场景？ • 如何处理动态场景？ • 如何处理快速运动和强旋转？ 复杂环境下的主要挑战 我们课题组的工作 • 面向大尺度场景的运动恢复结构 • ENFT-SFM：能够高效地处理大尺度场景下拍摄的循环回路和多 视频序列。 • 单目视觉的同时定位与地图构建 • ENFT-SLAM：能在大尺度场景下实时稳定工作、在线回路闭合； • RDSLAM：能在动态场景下稳定工作； • RK Segment-based BA Bag-of-words Place Recognition Pose Graph Optimization + Traditional BA 动态场景SLAM的主要问题（1） 场景逐渐在改变 可能有大量的错误匹配 动态场景SLAM的主要问题（2） 视点改变造成的遮挡 运动物体造成的遮挡 RDSLAM框架 结果与比较 RKSLAM: Robust Keyframe-based

进⽔平 推荐系统的核⼼特点 � Feature 1（基本特点） 1.1 User与推荐系统交互，7*24⼩时 流式学习 1.2 Item和User新增，离开/遗忘， Embedding空间动态变化。 短期命中的⾼频key随时间缓慢变化 少量的⾼频key占据了主要访问需求 ⼀段时间样 本命中的 unique key ID/tag/交叉特征 (全量为：亿，千亿) ⼩特征 （个） 2（数据的时空 特点） � Feature3（机器学习 的特点） 训练框架—基于参数服务器架构的分布式训练框架 TB级模型 分⽚ 存储/更新 百TB数据 分⽚训练 Feature 1: 动态空间 Feature 2.1:短时间内只有部分item和user 被命中，只有部分参数被⽤到 参数按需 获取/更新 Storage 异步训练流⽔线和多级存储：提升性能，降低内存成本 � the Communication Bandwidth for Distributed Training Dense参数，每次 都⽤，快速收敛 Sparse参数，随数 据变化，收敛度差 异⼤ 基于动态阈值 的稀疏化压缩 float16压缩 特点 混合压缩 ⽅案 效果 ～-90% -50% 训练速度提升 10%-30% 在线推理服务成本⾼，上线模型可以变⼩么？---模型压缩 模型的⼤⼩由什么决定？