Posts

阿里巴巴2022年KDD上发表一篇论文，介绍“瀑布流”推荐产品如何智能地选定请求时机的问题。这篇论文之前作为淘宝端智能的一项成果在知乎发布过，详见这篇文章。今年算是正式在KDD发表论文了。 阅读过程中我也一直将论文的方法和我们所做的类似的项目做对比，结论是思路是一致的，并不落后，但这篇论文的手段更加丰富，资源投入也更多，值得我们参考和学习。 背景 论文一开始先介绍什么事“瀑布流”推荐，这对于国内的移动用户而言司空见惯，就是无限下拉无限刷新推荐结果的产品交互形式，国内一般也叫feed信息流。所以需要解决的一个问题是分页请求时机的问题，就是确定在什么时机向后端发送新的推荐请求。一般是每浏览n个item后(也叫一刷)发起后端推荐请求。如果n变小，请求的频度增加，则后端服务请求的压力增加，而且很多用户本来也没有购买或者点击意愿，新增的推荐请求返回的结果也没有转换为最终的业务收益，最终白白浪费了算力。相反，如果n变大，请求的频度减少，则用户反馈延迟较长，用户实时的意愿（例如点击，购买转化等行为）没能及时反馈到后端，导致下一刷展现的还是之前缓存的推荐结果，体验较差而且不能提升产品收益。作者以淘宝App首页推荐为例，统计了每一刷的推荐结果CTR的变化情况，如下图所示： 可以明显看出每一刷头几条结果都是点击率很高，但后续衰减也是非常明显的。而且每次一刷更新点击率都有一次迅速提升，原因是新的一刷捕捉到了用户最新的兴趣点，但之后又回归到衰减。 问题和解决方案 因此，如何确定什么时机发起下次刷新是这篇论文需要解决的问题，作者给该解决方案定义了一个名词：IRSD（Intelligent Request Strategy Design），还大言不惭的说据他们所知，这是第一个在瀑布流推荐产品中研究IRSD的论文。 作者提出该问题主要有如下几点挑战： 捕捉用户兴趣点动态变化是一个难点，因为用户兴趣点是隐式变化的 不能同时观测到用户增加或者不增加下一刷请求，本质上这是一个反事实现象，所以uplift预估存在巨大的挑战。 这一点非常赞同，和我们遇到的难题类似， 不同策略其实无法在一个用户中同时存在，这也是反事实模型需要解决的问题 如何平衡新增下一刷请求的收益和带来的额外资源消耗非常有挑战性，尤其是用户数一直在动态变化 这一点和我们遇到的问题类似，如何保持QPS在系统可承载的范围内，同时拿到额外的业务收益，这也是效果-算力之间平衡的难题 为了解决以上调整，他们提出了一种新的范式，即基于Uplift算法的端智能请求框架（Uplift-based On-edge Smart Request Framework (AdaRequest)）。该框架部署在端上，这样可以更极致实时地收集和分析用户行为。该框架由如下几部分组成：用户行为理解模型（CUBE），反事实请求奖励估计（CREST），动态请求规划（DRP）。其中： CUBE挖掘用户稀疏的实时行为序列，长期行为序列，以及购买交互序列。通过比较用户实时意图和历史兴趣，CUBE可以评估出用户兴趣点是否有变化 CREST目标是对treatment和control组的用户分别建模，通过因果推断（causal inference）预估出增益（uplift）。 DRP动态选择新增请求的比例，用来选取最大化的请求奖励和资源消耗之比，在有限的资源约束前提下最大化请求奖励。 最终这套AdaRequest在手机淘宝的猜你喜欢页面（也就是首页推荐）落地，和固定增加请求比例对比，有GMV提升3%的额外收益。 总的来说，论文定义并调研了瀑布流推荐场景下的IRSD问题，同时提出了AdaRequest范式解决IRSD问题。同时通过在线和离线实验量化证明了AdaRequest的有效性。 问题定义 接下来论文介绍了实现的方法。首先定义问题，从形式上IRSD问题定义如下： 其中S函数代表用户的正向反馈，F函数代表决策结果(1代表请求，0代表不请求)，\(c_i^X\)代表第i个上下文环境，\(u_i^X\)代表第i个用户，\(b_i^u\)代表第i个用户的历史行为，\(X_i\)代表第i刷。R代表新增请求的资源消耗函数。因此第一个公式代表在各种上下文环境、用户、历史行为、刷次中获取的总收益大小。第二个公式代表总资源消耗约束在theta阈值以内。优化目标是找到最优的算法F，使得在满足资源消耗约束条件下，最大化业务收益。 AdaRequest框架 接下来终于一窥AdaRequest方案的整体框架，如下图所示： 虽然CUBE，CREST，DRP三大组件看起来很高级的样子，其实核心在左边的流程图中： 首先在端上实时采集用户行为，第二步CUBE将用户行为转变为用户意图变化情况，转化方式实现采用了一个神经网络来解决，产出用户浏览历史匹配度，用户当前session点击历史匹配度，用户长期点击历史匹配度，以及候选推荐item的embedding向量。第三步CREST将第二步的输出作为输入，再加上用户以及上下文特征向量，可以预估出新增请求的奖励uplift，最终交给DRP来决策是否发起新增请求。 DRP将动态选择一部分高性价比的时机发起新的请求。如果决策新增一次推荐请求，端则向后端发起请求，上传用户实时行为，后端则重新分析用户意图，返回更新的推荐item，更好地匹配用户最新的兴趣点。 因此，该论文所采用的特征体系有： 用户特征F(user) 候选item特征F(cands) 用户细粒度的历史行为特征： 用户的浏览历史F(exp) 用户当前session的点击行为F(sclk) 用户长期点击行为F(clk) 粗粒度的当前session的上下文特征F(context) 在这个特征组中，F(sclk)和F(clk)分别代表了用户实时和长期的兴趣点。F(exp)代表了上次请求曝光后用户不喜欢的item，原因是负向反馈也是一种有价值的信号。F(context)代表用户在当前session中的推荐满意程度，例如浏览的深度。论文还很贴心的把所有特征列表附在论文附录。 CUBE CUBE组件的目标是从用户实时行为中找出用户意图是否发生变化。由于推荐候选item是由后端服务根据用户历史兴趣推荐选择的，CUBE将结合用户行为，将用户刚刚交互过的item和推荐候选的item进行匹配。如果这两者不是非常匹配，意味着当前候选item并不满足用户当前意图，进一步则意味着用户意图发生了变化，因此此时如果新增一次推荐请求，能收获显著的购买uplift。 具体来说，CUBE将F(exp), F(sclk), F(clk)和F(cands)作为输入，针对特征特点做细粒度的建模。具体来说，F(sclk)特征分为用户行为序列F(sclk_beh)和item序列特征F(sclk_item)，分别通过两个GRU encoder输出向量并拼接在一起。F(exp)和F(clk)类似处理，而F(cands)采用一个GRU encoding编码，并通过mean-pooling操作做fusion融合。 最终，整个模型采用attention作为将候选item和用户以及交互行为序列匹配的算子。F(cand_emb)作为attention的query输入，用于匹配候选item是否满足用户实时意图。以F(sclk)为例，第i个item是否匹配用户意图的attention评分函数如下公式所示： 可见alpha_i即当前item的匹配率在所有匹配率中的softmax归一化值。输出向量M(sclk)定义如下： 可见M(sclk)即每个item的F(sclk_embs)的加权和，代表了当前候选item是否匹配用户实时意图的程度。 上述的Match函数代表匹配分，代表推荐候选集和用户实时交互的item序列之间的相似程度，即attetion匹配函数。论文实际采用的是内积函数作为匹配函数的实现。M(exp)和M(clk)也是类似方法产出，结果的分布代表了候选item是否匹配用户不喜欢的item以及用户长期感兴趣的item。 CREST CREST模块用于预估新增一个额外的推荐请求带来的uplift收益。由于用户无法同时存在有和没有新增推荐请求的状态，因此无法反事实地观察到收益uplift的真实值groundtruth。 为了解决这个问题，作者采用两个独立的预估网络，Control Net用于预估如果没有额外的请求，购买率是多少。以及Uplift Net，用于预估如果有额外的请求，额外的增益uplift是多少。Control Net和Uplift Net加一起，可以预估出如果有额外的请求，那么购买率是多少。 为了训练这两个预估网络，论文将实验用户随机分为两组用于数据收集：control组没有额外请求，而treatment组随机发起额外请求。Control Net用control组的数据训练，而Uplift Net用control组以及treatment组的数据训练。 ...

这篇总结并行编程的三种常见的内存管理方法，三种方法如下： Reference Counting：并行编程之内存管理(一) Hazard Pointer：并行编程之内存管理(二) RCU：并行编程之内存管理(三) 三种方法各有利弊，优缺点对比如下： 引用计数(Reference Counting) Hazard Pointer RCU 读性能 低，不可扩展 高，可扩展 高，可扩展 可保护的对象数量 可扩展 不可扩展 可扩展 保护周期 支持长周期 支持长周期 用户必须限制保护周期长度 遍历是否需要重试 如果和删除冲突需要重试 如果和删除冲突需要重试 不需要 存在性保证 复杂 保证 保证 读竞争 高 无 无 对象遍历开销 CAS原子操作，内存屏障，cache missing 内存屏障 无 读遍历机制 无锁 无锁 有限制的无等待(wait free) 读引用获取 可能失败 可能失败 不会失败 内存开销 有限 有限 无限 内存回收机制 无锁 无锁 阻塞 自动回收 是 部分 部分 已经有很多C++项目，包括开源和大厂内部项目，都开始采用Hazard Pointer和RCU来实现并发数据结构，而且C++标准委员会也已经在讨论将这两个组件加入到C++26标准中。 时代在变，并行编程技术也在突飞猛进。多线程多核(multi-core)技术，甚至甚多核(many-core)技术都在飞速发展，加上各种并行编程范式的应用，可以预见到在一段时期内，并行编程将面临百花齐放，技术爆发的局面。

RCU(Read-Copy-Update) 前述的几种内存管理方式只能同时管理一个内存对象，而RCU是一种同时管理多个对象的并发读写的方法。它实际上是提供了一种受保护的内存区域，通过RCU方法，将对象关联到受保护内存区域后，可以保证读操作完成以后才会回收对象，而且读操作开销极其低(5ns左右)，适合多个对象的批量保护，以及读多写少的场景。自从2002年RCU功能引入Linux内核以后，在内核中使用次数突飞猛进，如下图所示： 在内核中RCU API被广泛应用于网络，内存管理，文件系统等内核组件中。除了内核，RCU也有开源的user space RCU库，被广泛应用于QEMU模拟器，DPDK，Go语言的垃圾回收等项目中。 那么RCU到底是什么神秘的方法呢？其实原理正如其名：Read-Copy-Update。当需要修改对象的时候，先拷贝这个对象，修改产生新版本对下，然后变更新版本对象，等待老版本对象的reader完成读操作，再销毁老版本对象。可以明显看出，这个思想和Copy-On-Write思想一脉相承，和MVCC的思想更是极其类似。在生产环境中，按照类似原理实现的支持并行变更的数据结构也屡见不鲜，例如索引领域的hashmap，B+树等数据结构都可以按照类似思想实现并发读写。因此，思想并不新，但如果要正确实现，有三个原则需要保证，有很多细节需要处理，这也是RCU比较神秘之处。 RCU正确实现的三个原则是：宽限期保证(grace-period guarantee)，发布-订阅保证(publish-subscribe)和内存顺序保证(memory-order guarantee)。解释如下： 宽限期保证 允许所有的更新操作等待之前存在的读操作完成。之前存在的读操作其实就是还在访问修改前的内存对象的reader，因此如果不等待这些reader就销毁老版本的对象，则会导致并发错误。在一个链表的场景中，先删除一个节点的链接，然后通过宽限期保证等待所有该节点的访问结束之后，就可以安全销毁这个节点。 相关的RCU接口有rcu_read_lock，rcu_read_unlock, synchronize_rcu，其中rcu_read_lock，rcu_read_unlock用于读操作，标记当前线程正在读该内存区域，rcu_read_lock，rcu_read_unlock之间访问的所有内存对象被称为读端临界区(read-side critical section)。synchronize_rcu接口用于执行宽限期保证，等待所有还在读老版本数据的线程完成。 发布-订阅保证 该保证是说所有reader读取一个新版本对象的时候，可以保证该对象已经初始化好了。这里reader就是所谓的订阅者，RCU通过rcu_assign_pointer接口实现发布操作，RCU的这个保证可以保证订阅者看到的一定是发布者发布时刻的对象，不存在乱序等因素的干扰。实现上，发布方可以通过std::memory_order_release操作来更新对象，而读方可以通过std::memory_order_consume来读取对象，这样就可以避免乱序读取的情况发生。 内存顺序保证 该保证是宽限期保证的自然延续。读端临界区之间保护的内存对象和synchronize_rcu调用之间，存在一个严格保证的内存顺序关系。 下面几个例子说明该顺序的含义，其中X和Y的初始值都为0： 类别 图示 描述 情况1 如果按照绿色箭头的顺序执行，RCU可以保证读端临界区之后，即rcu_read_unlock发生之后才发生synchronize_rcu，这样如果r2==1，那么可以保证r1==0 情况2 如果CPU 0在读端临界区间运行时发生synchronize_rcu调用，RCU可以保证synchronize_rcu之前发生的事件一定在读端临界区中生效。在这个例子中，如果r2==1，那RCU一定保证r1==1 情况3 如果两个读端临界区并行执行，RCU是无法保证两者之间的内存顺序的。在这个例子中，CPU0和CPU2的读端临界区中对象的读取顺序是无法保证的，因此如果按照绿色箭头执行，r1==0，r3==0，是无法保证X=1和r2=X之间不乱序的 情况4 如果RCU的读端临界区和宽限期保证synchronize_rcu调用重叠，如果按照绿色箭头执行顺序，RCU可以保证读端临界区先于synchronize_rcu执行之前，即r1==1，r2==0 那么，如何实现RCU的呢？实际上，一个最简单的实现方式只需要10行代码，如下所示： static void rcu_read_lock(void) { spin_lock(&rcu_gp_lock); } static void rcu_read_unlock(void) { spin_unlock(&rcu_gp_lock); } void synchronize_rcu(void) { spin_lock(&rcu_gp_lock); spin_unlock(&rcu_gp_lock); } 可以看出rcu_read_lock和rcu_read_unlock通过一把锁来保证和synchronize_rcu之间严格的顺序关系，同时synchronize_rcu必须等待rcu_read_unlock执行完成之后才能执行。当然，这种naive的实现性能最低，而且不支持并发读，在生产环境中完全不可用。 有几种可以考虑的改进思路： 通过引用计数的方式来实现并发读； 通过TLS的方式减少读之间的竞争； 通过多版本的方式来减少锁竞争。 这样一个优化的实现如下所示： DEFINE_SPINLOCK(rcu_gp_lock); // 全局spin lock，用于保证并发只有一个写线程 DEFINE_PER_THREAD(int [2], rcu_refcnt); // 每个线程缓存一个引用计数 long rcu_idx; // 全局多版本号 DEFINE_PER_THREAD(int, rcu_nesting); // 每个线程缓存一个内嵌计数，用于支持读端临界区的重复进入 DEFINE_PER_THREAD(int, rcu_read_idx); // 每个线程缓存一个版本号 // 进入读端临界区 static void rcu_read_lock(void) { int i; int n; n = __get_thread_var(rcu_nesting); if (n == 0) { // 第一次进入的时候更新引用计数 i = atomic_read(&rcu_idx); // 获取可用的全局版本号 __get_thread_var(rcu_read_idx) = i; // 在对应版本计数 __get_thread_var(rcu_refcnt)[i]++; } __get_thread_var(rcu_nesting) = n + 1; // TLS内嵌计数++ smp_mb(); } // 退出读端临界区 static void rcu_read_unlock(void) { int i; int n; smp_mb(); n = __get_thread_var(rcu_nesting); if (n == 1) {// 最后一次退出的时候更新引用计数 i = __get_thread_var(rcu_read_idx); // 获取可用的全局版本号 __get_thread_var(rcu_refcnt)[i]--; // 在对应版本更新计数 } __get_thread_var(rcu_nesting) = n - 1; // TLS内嵌计数-- } // 反转全局版本号，保证所有读线程完成 static void flip_counter_and_wait(int i) { int t; atomic_set(&rcu_idx, !i); // 反转版本号，这样后续进入的读线程都会使用新版本号 smp_mb(); for_each_thread(t) { // 遍历所有线程TLS while (per_thread(rcu_refcnt, t)[i] != 0) { // 等待每个线程TLS缓存的引用计数为0 poll(NULL, 0, 10); } } smp_mb(); } // 宽限期保证实现 void synchronize_rcu(void) { int i; smp_mb(); spin_lock(&rcu_gp_lock); // spin lock保证只有一个写线程 i = atomic_read(&rcu_idx); // 读取全局版本号 // 先反转一次版本号，等待老版本读线程结束 // 但还是有可能会在30-31行之间，执行了flip，因此需要再反转等待一次 flip_counter_and_wait(i); flip_counter_and_wait(!i); spin_unlock(&rcu_gp_lock); smp_mb(); } 这个实现离生产可用的实现更进一步，实际上，已经开源的RCU库有user space RCU和folly RCU，都可以学习参考。 ...

Hazard Pointer Hazard Pointer的思想和引用计数恰好相反。不在数据内部存储一份引用计数，而是从外部来管理对象。流程如下：首先为每个需要管理的对象标记一个指针，放到一个全局或者per-thread的list中。在这个list中的标记指针就叫做hazard pointer。需要销毁对象的时候将hazard pointer放到一个待回收list，根据一些策略来决定是否正式销毁对象。销毁待回收的对象的方式还有主动和异步的接口，主动的方式是直接调用接口回收销毁。异步是通过异步线程定期销毁。销毁回收对象的时候，首先查看下hazard pointer list中有没有指向这个对象指针，有就不回收，没有就可以安全回收。其实本质上通过统计指向这个对象的hazard pointer数量来作为“引用计数”。将复杂性放到回收阶段，这也是为什么hazard pointer适合读多写少的场景的原因。 实现Hazard Pointer的主要复杂度在于管理正确处理被保护的hazard pointer和待回收的hazard pointer之间的关系。对于C++来说，可以通过构造/析构函数(RAII)来自动实现加入/退出hazard pointer的保护。整个流程可以见如下示意图所示： 从上图可以看出，销毁hazard pointer所管理的对象是通过延迟销毁来解决。通过对比被销毁的hazard pointer地址和当前正在被保护的hazard pointer地址，从而避免销毁掉正在使用中的指针对象，从而实现保护的目的。 作为样例，我们首先实现一个全局的hazard pointer基类，所有需要拥有hazard pointer保护功能的类都需要继承这个基类。 // 该类实现基本的hazard pointer回收方法 class HazPtrObj { using ReclaimFnPtr = void (*)(HazPtrObj*); template <typename T> friend class HazPtrObjBase; friend class HazPtrDomain; // 对象回收函数 ReclaimFnPtr reclaim_; // 下一个待回收对象。本质上是通过这个指针，将所有待回收对象连成一个链表 HazPtrObj* next_; // 将自身加入到待回收对象list中，依赖全局对象domain，domain统一管理所有已保护和待回收的hazard pointer list void push_obj(HazPtrDomain& domain) { hazptr_domain_push_retired(this, this, domain); } // 对象回收函数 ReclaimFnPtr reclaim() noexcept { return reclaim_; } // 原始指针 const void* raw_ptr() const { return this; } public: HazPtrObj() noexcept : next_(this) {} HazPtrObj(const HazPtrObj& o) noexcept : next_(this){} HazPtrObj(HazPtrObj&& o) noexcept : next_(this) {} /** Copy operator */ HazPtrObj& operator=(const HazPtrObj&) noexcept { return *this; } /** Move operator */ HazPtrObj& operator=(HazPtrObj&&) noexcept { return *this; } HazPtrObj* next() const noexcept { return next_; } void set_next(HazPtrObj* obj) noexcept { next_ = obj; } }; // hazard pointer基类，所有需要保护的类都继承该类 template <typename T> class HazPtrObjBase: public HazPtrObj { // 默认的对象回收函数 void delete_obj(T* p) { delete p; } public: // 将this放到待回收list中，准备被回收 void retire(HazPtrDomain& domain = default_hazptr_domain()) { assert(next_ == this); this->reclaim_ = [](HazPtrObj* p) { auto hobp = static_cast<HazPtrObjBase*>(p); auto obj = static_cast<T*>(hobp); hobp->delete_obj(obj); }; this->push_obj(domain); } }; 实现代码也比较直观，通过继承HazPtrObjBase类，任意一个对象都可以拥有一个retire方法，这个方法可以认为和delete等同用于销毁对象，但并不是立即回收，而是通过hazard pointer的延迟回收。 接下来需要实现一个保护HazPtrObjBase的对象，如下样例代码所示： ...

前言 随着现代处理器的发展和多核多CPU体系结构的大面积应用，C和C++编程面临着更加复杂和陡峭的学习曲线。特别是基于多线程带来的并行编程，带来了很多内存并行访问的问题。这需要非常专业的知识，深入了解CPU指令集，内存访问，CPU Cache等体系结构的底层知识，才能正确写好高性能和安全的并行程序。最近十多年，学术和工业界在并行编程方面进行了非常多创新的探索和研究，总结出一套优秀的编程实践和并行内存管理组件，并在Linux内核和大型开源软件中广泛应用。这里选取和内存对象管理有关的三个编程组件进行介绍，分别是引用计数Reference Counting，Hazard Pointer和RCU，都属于延迟处理类型的组件。本文目的一是为了个人学习的总结，另外也是给更多感兴趣的同学以启发。 引用计数 引用计数的思想很简单，通过原子变量来追踪对象的引用数量，来防止错误地销毁对象。这种思想最早可以追溯到20世纪40年代：当时工人们如果要修理危险的大型机械，他们会在进入机器之前，在机器开关上面挂一把锁，防止他在里面的时候被其他人误开机器。这也说明了引用计数的作用：通过计数来管理对象的生命周期。 以shared pointer为例，参考gcc shared_ptr实现，做了一些简化，样例代码如下： // 计数管理类 template <typename T> class RefCount { public: RefCount(T *p = nullptr) : ptr_(p), cnt_(1) {} ~RefCount() { // 如果计数为0，销毁自己 if (Release()) { delete this; } } RefCount(const RefCount<T> &rc) = delete; void operator=(const RefCount<T> &rc) = delete; // 原子++ void AddRef() { ++cnt_; } // 原子--，如果计数为0，销毁保存的对象 bool Release() { if (cnt_.fetch_sub(1, std::memory_order_acq_rel) == 1) { delete ptr_; return true; } return false; } // 返回管理的指针 T *Get() const noexcept { return ptr_; } private: T *ptr_; // 管理的对象指针 std::atomic_int32_t cnt_; // 原子计数 }; // 包装为智能指针 template <typename T> class SharedPtr { public: SharedPtr() noexcept : rc_(nullptr) {} SharedPtr(T *p) : rc_(nullptr) { rc_ = new RefCount(p); } // 创建引用计数对象 SharedPtr(const SharedPtr<T> &sp) : rc_(sp.rc_) { if (rc_ != nullptr) { rc_->AddRef(); // 增加计数 } } // 计数减一 ~SharedPtr() { rc_->Release(); } // 获取裸指针 T *Get() { return rc_->Get(); } // 拷贝操作，当前指针计数减一，被拷贝指针计数加一 SharedPtr &operator=(const SharedPtr<T> &p) { RefCount<T> *tmp = p.rc_; if (tmp != rc_) { if (tmp != nullptr) { tmp->AddRef(); // 拷贝调用也增加计数 } if (rc_ != nullptr) { rc_->Release(); // 当前管理的计数减少引用 } rc_ = tmp; } return *this; } private: RefCount<T> *rc_; // 计数对象 }; 整个代码是比较易懂的。一般来说引用计数都是采用原子变量在构造和析构的时候分别+1和-1的。当计数为0的时候，则销毁管理的对象。 ...

背景 随着互联网的逐步普及和兴起，在线A/B实验获得了越来越广泛地应用。无论是营销策略，交互样式，机器学习模型，搜索算法都依赖在线A/B实验来进行试错和迭代。 实际上，A/B实验的思想最早起源于R.A.Fisher在20世纪20年代进行的针对农业的田间实验(Field Experimentation)，之后经过近一个世纪现代统计学的蓬勃发展，逐步成熟应用到各行各业。 在最近50年，随着科技的进步，人类可获取数据量呈现指数级增长，统计学从此有了更多的研究空间，并进入了一个飞速发展的阶段，诞生了因果推断1等更深刻的思想。A/B实验不再仅限于分析平均实验效应(ATE, Average Treatment Effect)，还进入到了有条件的平均实验效应(CATE, Conditional Average Treatment Effect)，进一步深入挖掘数据内部的规律。 通俗来说，ATE只是对比不同实验版本之间指标的差异，而CATE对比的是不同维度条件下不同实验版本之间指标的差异。而这个思想以及相关的方法，能够进一步挖掘产品，模型，算法，策略的潜力，实现“物以类聚人以群分”的个性化方案，同时也能够更深入的理解实验背后的因果关系。 ATE和CATE 在介绍CATE的具体算法之前，我们先理解ATE的理论基础。这里我们采用Neyman-Rubin的潜在产出模型(potential outcome framework)的理论框架来描述ATE的基本原理。 设Wi表示个体i进入实验组与否，在实验组中取1，对照组取0 (多实验版本的可以做相应的推广)；Yi 表示个体 i 的结果变量，就是我们所观察的实验指标。另外记 \({Y_i(1),Y_i(0)}\) 表示个体 i 接受处理或者对照的潜在结果 (potential outcome)，那么 \( Y_i(1)−Y_i(0) \)表示个体 i 在实验组中的个体因果作用。不幸的是，每个个体要么接受处理，要么接受对照\({Y_i(1),Y_i(0)}\) 中必然缺失一半，个体的因果作用是不可识别的。观测的结果是： $$Y_i=W_iY_i(1)+(1–W_i)Y_i(0)$$ 但是，在 W 做随机化的前提下，我们可以识别总体的平均因果作用 (Average Treatment Effect; ATE): $$ATE = E\{Y_i(1) – Y_i(0)\}$$ 这是因为实验组是随机抽样，个体进入实验组与否和Y是独立不相关，即Wi和Yi正交，如下面推导所示： $$ ATE = E\{Y_i(1)\} -E\{Y_i(0)\} \\ = E\{Y_i(1) \mid W_i =1\} -E\{Y_i(0)\mid W_i=0\} \\ = E\{Y_i \mid W_i =1\} – E\{Y_i \mid W_i=0\} $$ 所以ATE是可以通过随机化，从由观测的数据估计出来。 ...

可视化 作为数据分析的一个重头戏，数据可视化被称为数据分析的半壁江山一点不为过，当然另外半壁就是统计学。 数据可视化将枯燥的并不直观的一维统计数字，直接通过二维甚至三维图形的方式展现给人们。图像的信息含量远大于数字，使得人们可以直接发现数据的趋势，找到异常点，甚至洞察更深层次的规律。 数据可视化并不是简单的用Excel画个线图或者柱状图就可以搞定，事实上，数据可视化属于一门严格的统计学方向「探索性数据分析」，这是由美国著名统计学家John. W. Tukey于1977年首创，借助图形对数据进行探索性分析的方法。美国统计学家Wilkinson于2005年给出了一个很好的数据可视化框架，它直接导致了R包ggplot2的发明，并影响了世界上最好的数据可视化软件之一Tableau。所有这一切历史其实想说明，数据的可视化并不是想当然地画图，而是需要对所要解决的问题和适合表达的图形有非常明确的认识和理解，才能真正发挥数据可视化的潜力，开发出统计图形的价值。 用于数据可视化的图形的种类其实有多种多样，我们需要首先了解每种分类，以及适合的分析场景。如下表所示： 变量（度量）个数 分析目标 图形名称 图形样例 使用场景 一个 不同类别下数据展示 条形图 在各类别之间比较数据，一个坐标轴是维度，另一个坐标轴是度量。表示在维度的不同维度值下，度量的大小情况。 条形图还可以叠加更多维度拆解，例如在每个类别下继续按照另一个维度类型拆解，查看更细粒度的指标情况 一个 数据的统计分布 直方图 展示连续数据分布最常用的工具，它本质上是对密度函数的一种估计。通过将连续度量的值分组为数据桶，来观察数据的分布规律 一个 数据分位点分布 箱线图 主要是从四分位数的角度出发 描述数据的分布，它通过最大值，上四分位数，中位数，下四分位数和最小值五处位置来获取一维数据的分布概况。通过每一段数据占据的长度，我们可以大致推断出数据的集中或离散趋势（长度越短，说明数据在该区间上越密集，反之则稀疏）。 一个 数据在不同类别下的占比 饼图 每一个扇形的角度与相应数据的数值大小成比例，但实际上通过饼图来查看不同类别占比的差别并不是很直观，有时还不如条形图直观 一个 数据在不同地理位置之间的分布 地图 展示和地理位置有关的数据分布关系时，最合适的工具 一个 数据随着时间的趋势变化 折线图 将视图中的各个数据点连接起来。折线图为直观显示一系列值提供了一种简单方法，适合显示数据随时间变化的趋势，或者预测未来的值。 一个 数据随着时间的趋势变化以及按维度拆解 面积图 和折线图类似，只是将折现下方的区域按照不同类别维度填色，展示各类别随时间变化的趋势 二个 两个变量之间的相关关系 散点图 散点图通常用来展示两个变量之间的关系，这种关系可能是线性或非线性的。图中每一个点的横纵坐标都分别对应两个变量各自的观测值，因此散点所反映出来的趋势也就是两个变量之间的关系。 二个 两个变量之间的相关关系 热图 热图用矩阵表示两个变量之间的相关关系，同时将单元格数值用颜色表达，如颜色深表示数值大。跟进一步，热图还可以表达聚类关系，即在颜色图的边界区域加上聚类的谱系图，这样可以同时观测数值分布和聚类的结果 二个 两个变量之间的相关关系 密度图 在散点图的基础上，通过颜色进一步突出相关关系，以及热点区域 三个 三个变量之间的关系 三维透视图 通过三维透视的形式，将三个变量变成三个维度，直接展示三者之间的关联。但三维图容易受到视角变化的影响，因此需要不断调整视角观测到真实的规律 三个 三个变量之间的关系 等高线图 将三维透视图的等高线展示在二维图像上，这样视角更广，不用担心视角的问题 多个（>=3) 三个甚至更多变量之间的关系 散点图矩阵 散点图的高维扩展，只是将多个变量的两两散点图以矩阵的形式排列起来，就构成了所谓的散点图矩阵。它从一定程度上克服了在平面上展示高维数据的困难，对于查看变量之间的两两关系非常有用。 在正式画图之前，我们还需要区分度量(变量)和维度的概念，这为我们能画出正确的图形奠定基础。 ...

背景和环境搭建 Numpy和Pandas是目前最为流行的数据分析工具之二，基于Python语言开发。Numpy偏向数值计算，Pandas偏向数据分析，底层也是基于Numpy数据结构。两者结合可以完成一系列令人眼花缭乱的数据分析任务，并在机器学习，统计分析，因果推断等领域得到广泛应用。 作为入门，首先需要搭建开发环境。这里建议直接采用miniconda+VS Code的方式搭建，简单高效，步骤如下： 打开miniconda，找到适合自己操作系统的安装包，安装miniconda 国内环境推荐使用清华的conda和pip镜像，参考pypi镜像 和anaconda镜像 打开命令行，运行conda install pandas numpy 打开vscode官网，安装VS Code 打开VS Code，安装Python，Jupyter插件 在VS Code打开Command Palette (⇧⌘P) ，运行Jupyter: Create New Jupyter Notebook 命令 然后就能看到一个Jupyter Notebook，选择Python环境为刚才安装minicoda所在的位置 一个基本Python环境已经搭建好了， 之后就可以愉快的开发了，注意保存代码 在开发之前，需要先学习下narray，Series和Dataframe这几个基本的数据结构，搞懂这几个数据结构以及对应的计算模式，开发代码就会更加高效和方便。 所有的运算就基于这三个数据结构来做运算，计算过程类似矩阵或者集合的运算。编程的范式和传统的过程式编程有区别，不再是线性的执行顺序，而是集合和集合之间的关系运算。 例如，我们经常写foreach循环遍历数组中每一个元素进行运算，但用numpy就不需要，因为它直接提供了各种数组间运算的函数。再比如我们想将数据按照维度的聚合计算，对于pandas而言直接调用groupby函数即可。 下面分别介绍这三种基础数据结构。 narray narray是numpy的基础数据结构，它本质上是有一个多维数组，1维的就是一个数组array或者向量vector，2维是一个矩阵matrix，3维甚至更高维就是一个张量tensor。所以这个“n”代表维度，narray全称也就是“N-dimensional array”。 一个narray如下所示，一个维度称为一个axis。下面这个narray有两个axes，第一个axis长度为2，第二个axis长度为3。 >>> import numpy as np >>> a = np.array([[1, 2, 3, 4], [5, 6, 7, 8]]) >>> a [[1, 2, 3, 4], [5, 6, 7, 8]] 需要时刻记住，narray对应的是一个多维数组，如下图所示： numpy提供了一系列方便创建narray的函数，如下所示： >>> np.zeros(2) array([0., 0.]) # 0数组 >>> np.ones(2) array([1., 1.]) # 1数字 >>> np.empty(2) array([ 3.14, 42. ]) # 随机值 >>> np.arange(4) array([0, 1, 2, 3]) # 等差序列 >>> np.arange(2, 9, 2) array([2, 4, 6, 8]) #等差序列 >>> np.linspace(0, 10, num=5) array([ 0. , 2.5, 5. , 7.5, 10. ]) #线性区间 >>> np.ones(2, dtype=np.int64) array([1, 1]) #将默认数据类型从float64改为int64 narray的切片选取方法有： ...

前言 随着互联网行业的不断发展，数据作为最基础的生产资料发挥了极其重要的作用。随着大数据平台的普及，针对各种数据的分析是一项非常重要的基础技能。通过数据分析，我们可以从用户数据中发现新的用户喜好，从业务数据中发现业务的优化方向，从性能数据中发现潜在的性能瓶颈，从线上日志中发现异常指标等等。熟练掌握数据分析的一些常用方法，还会让程序员的水平更上一个台阶。可以不夸张地说，数据分析是程序员除了编程以外最为重要的技能。 但很多时候，大家对数据分析产生一些误解，容易神秘化或者低估数据分析的能力。常见的误解列举如下： Q： 数据分析就是操作Excel，小学生才玩这个。 A： 实际上Excel的确是数据分析最为方便的工具，但数据分析不止于此，python，R，Matlab，Tableau甚至shell都是数据分析常用的开发语言。当然Excel如果用的好，也会产生让人叹为观止的效果。 Q： 数据分析只有做机器学习模型的程序员才需要学。 A： 严格意义上开发训练机器学习模型也是数据分析方法中的一种。数据分析不仅限于给机器学习模型使用，也可以应用到更为广泛的问题分析中，包括性能分析，线上问题排查定位等，基本涵盖了程序员的日常工作。 Q： 数据分析就是用awk，wc，sort等工具写几个脚本统计下数 A： 数据分析范围肯定不只是用工具做个统计，还有建模，实验，可视化等等都是数据分析的范围，近年来更流行的名词叫“数据科学”，很多公司也成立了数据科学团队专门做更广泛意义的数据分析。 既然数据分析这么有用，那我们怎么从哪里开始做数据分析呢？本文作为系列第一篇文章，先从数据分析的整体层次，基础方法和工具介绍开始，更深入的内容等系列后续文章。 整体来说，数据分析可以分为三个层次，分别是观察型分析，干涉型分析，以及反事实分析。篇幅所限，不再详述这三个层次是怎么回事。感兴趣的同学可以阅读参考书目1。 通常意义上所说的数据分析方法主要还是属于观察型分析，重点在于发现数据的规律，从噪声中找到有价值的信号，找到不同现象和数据之间的关联关系。这些分析方法，基本上可以满足大部分常见的数据分析需求。而更高级的“干涉型分析”和“反事实分析”，则需要更深入的工具和方法才能解决。 本文介绍5种基础的数据分析方法，包括指标，汇总，相关，检验，可视化，最后列举了常见的分析工具。 指标 为什么把“指标”作为数据分析方法的第一个方法呢？这是因为很多人在数据分析的过程中，逐渐迷失了自己分析的目标，陷入了为了分析而分析的怪圈。因此，在数据分析之前，我们必须要定义清楚我们这次分析的对象是什么。互联网产品将数据汇总后的结果定义为指标，因此一次分析本质上就是在研究这个指标的相关特性。如果指标没有定义清楚，那么分析就难以找到正确的方向。在数据分析中，需要分析的核心指标也叫“北极星”指标，因为这些指标就像北极星一样，永远固定在天球的极北点。 按照统计方法来分，互联网产品中常见的指标可以分为 计数型 统计型(加和，最大最小等函数) 比率类 聚合二级指标。 将计数型和其他统计型计算区分开的原因是，计数有一类是去重计数，它要求计数的时候做去重操作，这样就不是一个简单地统计函数可以计算的，因此需要将计数函数和其他计算函数区分开。除了一级和二级聚合计算以外，所有的指标都需要窗口范围。例如天级，周级，月级等，这里不再逻辑。指标的以及和二级计算方式分类如下表所示： 一级聚合 二级聚合 SQL样例 指标样例 计数,去重计数 SELECT COUNT(pv); SELECT COUNT(DISTINCT uid) PV(Page View) DAU(Daily Active Users) 统计类(加和，最大，最小，中位数，80分位等) SELECT SUM(dur); SELECT SUM(show); SELECT MEDIAN(time); SELECT PERCENTILE(time, 0.8) 总时长,总下发量,总展现量, 耗时中位数，80分位耗时 比率类 SELECT SUM(clicks)/SUM(shows); SELECT SUM(duration)/COUNT(pv); PV点击率，点展比，页均停留时长 计数,去重计数 平均 SELECT AVG(show) FROM (SELECT COUNT(DISTINCT sid) AS show GROUP BY uid) 人均展现次数，人均邀请人数 统计类(加和，最大，最小，中位数，80分位等) 平均 SELECT AVG(dur) FROM (SELECT SUM(dur) AS dur GROUP BY uid) ; SELECT AVG(dur) FROM (SELECT MEDIAN(dur) AS dur GROUP BY uid) ; 人均时长，人均最大停留时长，人均耗时中位数 比率类 平均 SELECT AVG(pvctr) FROM (SELECT SUM(clicks)/SUM(shows) AS pvctr GROUP BY uid) ; SELECT AVG(dur) FROM (SELECT SUM(dur)/COUNT(pages) AS dur GROUP BY uid) 人均PV点击率，人均页均停留时长 我们做任何数据分析之前，先定义清楚我们的分析目标是哪些指标。例如我们想分析展现量和哪些因素有关，那么我们可以需要先对齐展现量指标的定义公式，是人均展现量，还是总展现量，还是去重展现量。如果指标定义不清楚，那么分析很可能南辕北辙，并不是我们想要分析的方向。定义清楚问题之后，我们再开始后面的分析。 ...