3.相关知识

最优化Optimization

什么是最优化问题

  • 无约束最优化问题:
    $$ minf(x) $$
  • 带约束最优化问题:
    $$ min f(x) \s.t. \textbf{g}(x)\leqslant 0,\textbf{h}(x)=0 $$

无约束优化问题一般思路

  • 目标函数不可/不易求导
    • 下降单纯形法(Ameoba变形虫法)
  • 目标函数易求导
    • 梯度下降法
    • 批处理模式:训练集上的梯度分解为各个样本梯度的和,可以并行实现。
    • 串行模式:随机梯度下降法(Stochastic Gradient Descent,SGD)【好用】

批处理梯度法的问题与拟牛顿法

  • 梯度法zigzag更新过程
    • 等高线和梯度垂直,因为等高线的形状是压扁的形状,所以会来回的跳,性能不好。
  • 牛顿法:
    • 不仅考虑一阶导,还考虑二阶导。但是Hession阵可能不正定。
  • 拟牛顿法
    • 用近似但正定的Hession阵确保稳定求解

BFGS和L-BFGS方法

  • BFGS(Broyden,Fletcher,Oldfarb,and Shanno)
    • 拟牛顿法是一种,用函数值和特征的变化量来近似Hession矩阵,以保证正定性,并减少计算量。
    • Hession集合公式(空间复杂度为N方)
  • L(Limited memory)- BFGS
    • 将Hession逆用{n*k}*{k*k}*{k*n}的方式近似【矩阵分解】
    • 空间复杂度为n*k

Trust-Region方法

  • 方法思想
    • 不近似Hession阵,但每次迭代将自变量限制在临域内
    • 先步长,后方向
  • 上述子问题虽非凸优化,但是满足KKT条件
  • 对于LR模型收敛速度经常好于L-BFGS

带约束优化:拉格朗日法

原问题(Primary Problem)==> 拉格朗日对偶函数(Lagrangian dual function) ==> 对偶问题(Dual problem)

信息检索Information Retrieval

文档的表示与相似度量

  • 词袋(Bag of Words,BoW)表示
    • 用关键词TFIDF组成的矢量来表示文档。
  • TF-IDF
    • TF(term frequency): 某文档中词出现的次数
    • IDF(inverse document frequency):总文档数/某个词出现的文档数,然后取log
  • 向量空间模型
    • 用余弦距离来衡量两个文档的相似度

倒排索引

  • 文档集
    • D1=“谷歌地图之父跳槽Facebook”
    • D2=“谷歌地图创始人拉斯离开谷歌加盟Facebook”
    • D3=“谷歌地图创始人跳槽Facebook与Wave项目取消有关”
    • D4=“谷歌地图创始人拉斯加盟社交网络Facebook”
  • 关键词(Term)
    • {谷歌,地图,之父,跳槽,Facebook,……}
  • 倒排链
    • 谷歌->{D1,D2,D3,D4},地图->{D1,D2,D3,D4},之父->{D1,D3,D4},跳槽->{D1,D3},Facebook->{D1,D2,D3,D4},……

统计机器学习Statistical Machine Learning

贝叶斯学习

  • 贝叶斯公式
    $$P(\Theta | X ) = \frac{P(X | \Theta)P(\Theta)}{P(X)}$$
    • 统计机器学习最核心的概念和公式。
    • 频率学派 VS 贝叶斯学派
    • X是观测的变量,Theta是要估计的参数。
    • $P(\Theta | X ) $ 是后验概率Posterior,所有的分类都是追求后验概率最大的原则。
    • $P(X | \Theta)$是likelihood(已知是黑人,黑人拥有黑色皮肤的概率),$P(\Theta)$是prior(黑人在中国出现的概率).
    • $P(X)$ 是evidence
    • 贝叶斯的核心是认为所有参数都是不确定的。
  • 若干模型估计方法

指数族分布

  • 归一化形式:$P(x|\Theta)=h(x)g(\Theta)exp\left { \Theta^Tu(x) \right }$
  • 若干重要指数族分布

指数族贝叶斯学习

  • 共轭先验:使先验分布与后验分布形式一致的先验分布
  • 指数族分布共轭先验
    • 一般形式:
      $$p(\Theta|\eta)=exp\left { \chi ^{T} \Theta-vg(\Theta)-b(\chi ,v))) \right }$$
    • 其中$\eta=\left { \chi, v \right }$为超参数(hyperperameter)
  • 指数族后验部分的超参数:
    $$\tilde{\chi} = \chi + \sum_{N}^{i=1}u(x_i)$$
    $$\tilde{v} = v + N$$

指数族分布(二)

  • 最大似然估计:$-\triangledown ln \textbf{g}(\theta_{ML} )=\frac{1}{N}\sum_{i=1}^{N}u(x_i)$
  • 混合模型:$P(x|\omega , \Theta)=\sum_{k=1}^{K}w_kh(x)g(\Theta_k)exp\left { \Theta_{k}^{T}u(x) \right }$
    • EM算法

深度学习Deep Learning

深度学习是什么?

  • 基于规则的系统
    • img of 8 –> 人工设计程序 –> num of 8
  • 传统机器学习
    • img of 8 –> 人工设计特征 –> 将特征映射到结果 –> num of 8
  • 深度学习(表示学习)
    • img of 8 –> 自动提取特征 –> 将特征映射到结果 –> num of 8
    • img of 8 –> 原始特征 –> 额外的层和抽象特征 –> 将特征映射到结果 –> num of 8

全连接多层感知机(Multi-layer Perceptron, MLP)

深度学习的工程本质

  • 浅层模型与深度模型
    • 深度模型比浅层模型表示能力更强
  • 优化方法是关键
    • 找到了GPU这条优化方法
  • 数据的作用
    • 深度学习和大数据关系非常紧密

几种重要的神经网络结构

  • CNN(Convolutional Neural Networks, 卷积神经网络)
    • 采样层->卷积层->采样层->全连接层MLP
    • 参数共享
    • 图像领域
  • RNN(Recurrent Neural Networks,递归神经网络)
    • 用递归的方式设计网络结构
    • sequence到sequence的学习
    • 语言领域
    • LSTM(Long-Short Term Memory,长短期记忆)是一种时间递归神经网络(RNN)
  • GAN(Generative Adversarial Network,生成对抗网络)

深度学习优化基础设施

  • GPU方案
    • 并行渲染屏幕上每个像素点,与并行计算各神经元很相似
    • 与CPU方案相比,可以加速数倍乃至十数倍
  • 并行计算方法
    • SGD过程可以分解到多台机器上进行,分别更新参数
    • 可以采用parameter server的计算框架,水平扩展性强
  • 开源框架
    • Tensorflow,Caffe,Mxnet,可以一定程度上忽略硬件

数据运营三板斧 – 用户增长

用户增长的基础:用户转化漏斗

  • 用户转化漏斗示例
    • 移动用户获取:下载->激活->留存->时长
    • 电商用户转化:到达商品页->加入购物车->完成订单->交易确认
  • 漏斗的设计原则与作用
    • 原则:整个漏斗过程用于优化一个唯一的目标
    • 作用:将该目标分解为若干比率的乘积,便于发现问题并优化
    • 示例:总用户时长 = 下载量 X 激活率 X 留存率 X 平均用户时长
  • 转化漏斗相关常见度量
    • 转化率 - 激活数与点击数的比
    • 「次日/七日/月」留存率 - 某日激活的用户中,「次日/七日/月」后活跃的用户占比
    • 「日/月」活跃用户(DAU,MAU)- 每「日/月」活跃的独立用户数
    • 用户时长 - 每个活跃用户平均消耗的时间

找到增长的障碍:多维度报表分析

  • 通过漏斗发现问题
    • 某页游用户转化漏斗:
    • 到达(5130)–19.1%–>注册(980)–14.0%–> 参与(431)–83.0%–> 充值
      • 注册率偏低,应该进一步分析?
  • 在多维度报表中找到症结
    • 注册率19.1% – IE(25.1%),Chrome(3.5%),FireFox(22.7%)
  • 数据魔方(Data Cube)
    • 什么是数据魔方? 1)用户可以较灵活选择维度组合,得到定制化报表。2)为人工决策提供便利
    • 技术方案:OLAP数据库
    • 开源方案:Saiku+MySQL

驱动新产品特征:利用A/B测试

  • 为什么需要A/B测试?
    • 多维情况下,魔方里大部分区域数据非常稀疏。极端情形:对于新Feature,需要主动分配测试流量
    • 某维度上的两个选项(例如两个不同的模型),数据并不是完全可比
    • 因此,我们需要一个主动的A/B测试框架,以便:1)主动分配流量给新的产品特征;2)保证对比实验的各组在数据上完全可比;3)尽可能在同样的流量规模上容纳更多的实验。
  • A/B测试并不是万能的
    • 用户产品过于依赖数据会丧失对关键创新的把握。- 汽车无法从“跑得更快的马”进化而来
    • 多数情况下,需要测试的可行组合太多,必须先经过人的筛选,或更复杂的E&E策略。- 每天数十万的新闻,那些有可能最受用户欢迎?
    • 博弈性场景无法通过A/B测试获得可靠性结论
    • A/B测试最适合的场景:理性产品、被动反应场景