跬步 2019-07-13 平时还是有些零星的idea休要记录下来，所以开一个跬步的系列，不积跬步，无以至千里。 出行的“聚合模式” 最近各家都在搞聚合模式，在以前滴滴一家独大的时候，的确是不怎么需要聚合模式的，毕竟离开了滴滴就打不到车了，现在入场的玩家越来越多了，大公司搞起了聚合模式，把自己做成一个真的平台。目前市面上有三家在做聚合平台，高德、滴滴、美团。对于高德来说，如何对流量变现一直是成为“ ...

Bandit Note（进行中） Introduction 基本术语： learner、player，决策者、玩家 environment，环境 horizon，决策周期 action，动作、决策、选择 reward，奖励 policy，策略 regret，悔恨 玩家在\(n\)轮决策周期内进行游戏，在每一轮\(t\in[n]\)中，玩家从给定动作集合\(\mathcal{A}\)中选择动作\ ...

Scalable Training of L1-Regularized Log-Linear Models 最近重读了一下之前阿里的MLR，又仔细研究了一下里面的优化算法，然后发现也是对之前的一个叫Orthant- Wise Limited-memory Quasi-Newton（下文中称OWL-QN，这个owl让我想起了哈利波特的Ordinary Wizarding Level...）的方法进行 ...

这篇文章是今年年初时候发在sigkdd上的一篇关于eta的文章，《Learning to Estimate the Travel Time》。 背景 车辆行驶时间估计是重要的位置服务的之一，而且在滴滴的服务中占有比较重要的一环，这篇文章提出了一个新的ETA的模型，并应用于滴滴出行的线上服务。传统的ETA主要分为两类，第一类就是基于路径的方法，整条路径的行驶时间等于其中每一段路径时间的和： \[ \ ...

这篇文章是用MDP方式去考虑车辆调度的分单算法，发表在KDD2018上，《Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach》。 这篇文章给我感觉真的是十分精彩，从解决方案到后面实验部分都写的很充实，而且方法朴实却又新颖，作为RL或者说是MDP的一个非游戏类 ...

最近要写几个滴滴相关的论文的笔记，顺便解读一下目前的拼车算法等策略，顺带着科普。今天这篇是KDD2017的《A Taxi Order Dispatch Model based On Combinatorial Optimization》，这篇文章是比较早时候的分单算法的文章，跟现在的算法略有差异。 简介 传统的拼车算法是一种顺序的分配策略，在乘客周围选择最近的车辆，最大化每个司机对每个订单的接受概 ...

python类笔记 私有属性和方法 命名前加两个下划线 1from module import * 这样做无法直接调用module中的__func()方法，但直接import却是可以的 1from module import __func 抽象方法 用@abstractmethod。 __new__和__init__ __init__() 方法用于给属性赋值，不可以有返回值，__new__()多用 ...

Online Subgradient Descent 在线梯度下降算法如下图所示 OGD 其中，每一步迭代的时候，根据梯度（或次梯度）更新后，将新得到的权重投影到权重的可行域上。 定理1：如果\(w'\in\mathcal{W}\)，\(w=\prod_{\mathcal{W}}(w')\)，\(w^*\in\mathcal{W}\)，那么\((w'-w)(w^*- ...

Follow the Leader Against Quadratics 某些情况下，FTL是非常好的算法，比如一维的线性回归的情况，很容易推广到高维 每一轮选择\(w_t\in[-1,1]\) 对手选择\(y_t\in[-1,+1]\) 计算\(f_t(w)=\frac{1}{2}(w-y_t)^2\) 使用FTL算法： $$ \[\begin{aligned} w_{t+1}&=\ ...

Example Online Optimizers 对于FTL（Follow-The-Leader）算法， \[ \mathbf{w}_{t+1}=\underset{\mathbf{w}\in\mathcal{W}}{\arg\min}\sum^t_{s=1}f_s(\mathbf{w}) \equiv=\underset{\mathbf{w}}{\arg\min}f_{1:t}(\mathbf ...