机器学习笔记
（第一节introduction）
1. 就搜索应用而言，目前规则和机器学习都被广泛采用，一个基本原则是：机器学习对长尾Query处理，而规则对top
Query有效。
&个人理解：长尾Query很难人工发觉合适它的规则，因此要依赖于模型预估的结果。
2. 机器学习三个关键点：data、model、algorithm
&data很重要，一定程度上高于model，好的data往往得到好的结果，这也是互联网对优质流量渴求的原因
& &model是对data分布规律的假设
&algorithm是得到model中参数的方法
&其实，最重要的可能是需求，只有需求很给力，才能够获得足够的资源去把事情做好
（第二节linear
1. 简单线性模型y=a0 +
a1*x，通常采用最小二乘准则进行求解模型参数a0和a1，从统计的角度看，线性模型为
& & y=a0 + a1*x + e
其中e为噪声（0均值高斯分布），噪声的引入为最小二乘准则和概率模型建立了桥梁。
& & data -》 model -》
2. 如果实际值y0与模型预估值之间的residual的分布仍然符合某种分布，那么模型就可以继续优化，即
& & y=a0 + a1*x1 +
以此类推，这种方法可以优化模型，此时，模型(特征)虽然是非线性的（e.g.
x^2），但参数是线性的，仍然可以用最小二乘求解。
3. 求解线性模型的参数，可以通过矩阵伪逆求解得到。
对于一组数据，首先假设一个模型，并认为该模型是正确的，然后通过residual验证模型是否真的正确（residual是否符合高斯分布），并基于此觉得模型是否需要继续优化。
5. overfitting的一个体现是模型预估得到的residual小于数据真实的噪声。
6. 特征有效性验证：加/减一个特征，模型是否更精确，residual是否降低（RSS：residuals sum of
squares）(t检验)。
& & （CTR预估中，可以参考这一课程第40分钟-45分钟的介绍，优化特征，去掉非重要的特征，开发一个工具）
regularization）
训练数据的模型误差可能很小了，但在测试数据上表现一般，一方面是由于训练数据和测试数据分布特性不同导致的，另一方面是由于模型在训练数据上存在overfitting的情况导致的。
通常情况下：模型越复杂，则模型在测试数据和训练数据上表现的差异性就越大(训练数据过拟合)，反之，模型越简单，则模型在测试数据和训练数据上表现的差异性会约小（underfitting）。现实情况是，模型往往是overfitting一点点。
模型的复杂程度可以用特征参数的数量来度量，减少特征数可以使模型变的简单，但这不是通常的做法，通常的做法是缩小特征空间，通过regularization来实现，e.g.
& &min{|y-y0|^2} s.t.
sum(|a_i|) & A
& &引入拉格兰日表达式，以便于求解，如下，
& &min{|y-y0|^2 +
lmada*sum(|a_i|)}
&lmada*sum{|a_i|}就是regularizaiton项,lmada越大，则要求sum|a_i|越小，反之亦然。lmada越小，对应sum(|a_i|)越大，则模型越复杂，越有可能出现overfitting。
&调整lmada，就等效于调整参数个数的效果，以优化模型复杂度。
&引入regularizaiton后，仍然可以通过求违逆求解模型参数，细节可参考相关文献，或视频的第40分钟-43分钟。
&注：训练样本通常是一个数据集合，因此，实际求解是，min{|y-y0|^2}表示这组数据的误差和。
（第四节 linear
classification）
1. 很多非线性问题可以用线性分类器解决，实际应用中，线性分类器是最被广泛应用的模型之一。
2. 感知器perceptron algorithm（可抽空了解）-》 神经网络
3. SVM， better generalization = less overfitting, 通过kernel
function将低维空间映射到高位空间。
4. 对于简单的二分类问题，可以存在多个分类超平面，哪一个是最优的？svm就是回答这个问题=
-》最大margin对应的分类超平面。
5. 关于SVM的详细介绍：
6. 一般意义而言，SVM和Logistic没有大的区别，Logistic模型的输出是概率。
7. 模型训练过程中，建议在输入中尝试尽可能多的特征，在regularizaion项中通过L1范数求解稀疏解。
8. 多类问题可以分解为一系列两类问题进行实现。
（第五节 non-linear
classification）
1. 线性模型: g(x)=sign{w*x + b}
2. 非线性模型: g(x)=sign{w*h(x) + b}
3. 模型参数通常是训练样本的线性组合，以梯度下降法为例：w_i = w_i - (h(x) -
y)*x_i，即w_i与x_i相关。
注：模型参数w在训练样本组成的线性子空间中。
& & 基于此，线性模型参数w=sum(a_i *
x_i)，非线性模型参数w=sum(a_i * h(x_i))
4. h(x_i)就对应kernel函数
SVM的kernel函数详解：
5. regularization使得函数（模型参数）趋向于我们所希望的形式，e.g. 平滑性、稀疏性。
6. kernel和regularization之间存在直接的关系，视频的第30分钟-35分钟。
7. Logistic和SVM本质没有很大区别，但是Logistic输出的是一个概率，可用的场景更广泛。
8. kernel函数定义为两个非线性函数的内积k(x1,x2)=h(x1)^T *
h(x2)就是为了将kernel与regularization关联起来，e.g. ||w||^2 = sum(a_i *
k(x1,x2) * a_j)
（第六节 model selection）
选择不同的模型拟合数据，如果是通过参数(特征数)的增加来实现，那么需要注意overfitting和underfitting的问题。
selection要解决的问题就是在不知道真实数据是怎样的情况下，如果选择最优model。
好的model不是说在训练数据上表现怎样，而是关注在未来要处理的数据上表现怎样。
具体的模型选择方法：已知的数据被分为两份，一份是training data，用于训练模型；另一份设定为validation
data，用于模拟未来数据，用于选择模型。在validation data上表现好的model用于预测未来的testing
通常模型训练的时候，数据越多，那么得到的模型就会越靠谱，但是为了选择模型，需要从有限的训练数据中抽取一部分作为validation
data。同时，如果只选择一份数据作为validation
data，可能验证的结果也不是很精确。基于此，可以将数据分成多分，每次选择一份作为validation
data，剩下的作为training
data，如此交叉进行循环训练和验证。最后，对多次验证的结果求平均，确定模型的好坏。
6. 值得注意的是，上述问题现在已经不存在了，作为大数据时代的现在，数据非常丰富，因此实际没有必要那么做了。
（第七节 model combination）
机器学习的前提是假设训练数据符合某种分布，训练得到的模型参数就是对这种分布的描述，并且假设测试数据与训练数据具有相近的分布。
selection是指从很多模型训练算法（Logistic、SVM）中寻则一个最好的，而model
combination则是对多个模型求均衡(平均)，以求获得更好的效果。
selection的简单方法：equally weighted averaging（平均）、exponentially
weighted average（各模型的权重取决于其带来的误差(表示成指数) 参见视频25分钟-28分钟）、各模型的加权系数通过最效果validation
data的最小误差求解得到（stacking）。
当models效果之间的差异比较大时，则选用model
selection得到最好的一个；当models效果之间没有明显差异时，则采用model
combination。
combination要求models之间具有差异性，这种差异性表现在：模型训练算法、特征设计等。
boosting）
1. linear feature -& linear combination
2. weak learner, e.g. shallow tree，在所有训练数据集上比随机分类稍微好一点。
3. adaptive boosting：reweighting and compute
w，adaboost的一个优点是不容易overfitting。
TreeLink：
（第九节 learning theory）
1. 怎么度量一个算法的好坏：oracle
inequality、estimate test error from training error。
& training error与最好的分类结果相比怎样，testing
error与training error的比较。
2. uniform convergence
&这一节过分偏理论，自己感觉有点虚，快速浏览了。
3. 用处：给定一个算法，怎么度量这个算法的好坏。
（第十节 Optimization）
1. gradient descent
2. proximal projection method
(很不了解)
3. coordinate descent
6. 优化目标min_w{f(w)},i.e. 则优化解为w，for
all w', f(w)&f(w')
7. 对于convex
problem，局部最优解就是全局最优解
8. 损失函数l2为smooth，l1为非smooth。
这一节需要参阅很多的参考文献，感兴趣的需要根据视频中提到的算法找资料了。
LBFGS是目前非常popular的方法，开源代码：
（第十一节 online learning）
基本思想：用t-1时刻的数据生成预测函数f_t-1，并用f预测t时刻的结果，即f_t-1(x_t)。
oracle最好的算法通常得不到，只是事后诸葛统计得到，用于作为衡量算法好坏的标准。
learning是否可以用来做实时模型更新？后续调研！
视频的41分钟-42分钟给出了开源代码，感兴趣可以下载看看。
（第十二节 sparsity model）
现在是大数据时代，数据都是高维的，而通常只有少部分有用，因此大家就对sparsity model感兴趣了
2. sparsity
model可以通过减少变量数以降低模型复杂度
优化目标函数中加入l1范数就是为了解具有sparsity
在统计学领域，通常数据是高维的，但是能够观察到的数据是很有限的，因此sparsity model关注的相对比较多
5. 常见的sparsity优化目标是min_x{||y -
a*x||^2} s.t. |||x|_0 &=
k,即稀疏度为k(x中有不多于k个非0元素)
sparsity的重点就是feature选择，相当于保留少数几个重要的特征
7. lasso and group lasso算法
8. KKT 和 RPI condition
9.Matrix Completion
-& 协同推荐
（第十三节 graphical model）
1. what is the graphical
model：模型用来干什么
模型概率、联合分布
2.inference:推理，什么样的数据需要什么样的模型，以解决什么样的问题，即怎么用模型
3. structure
learning：从数据中学习模型参数
4. graphic model名词
& 节点：observed or
unobserved variables
边：variables之间的相关关系(条件)
& 箭头：方向，因果关系
5. structure &and
&parameters：通过挖掘条件独立以精致地表示概率分布
（第十四节 structure learning）
1. 字符、图像具有内在的结构性
2. structure可以考虑的角度：input data，
output data，model
3. structure
output的应用：语音、生物学DNA......
4. structure model: HMM......
（第十五节 deep learning and feature
learning）
1. 除了model，feature非常重要
model里面通常有正则项，这里面就有feature选择的影子
3. feature也是数据structure的一种体现
learning是现在非常hot的一个模型，它在语音和图像方面取得的效果远优于传统方法
相对于语音和图像，信息是完整的，而CTR预估很多信息是确实的（e.g. 用户当前的心情），这也是导致CTR预估困难的原因。
Feature，feature通过不具有通用性，在一个模型/场景下好，在另一个未必好，所以需要feature
7. deep learning
去学习feature，是的feature有意义，可理解
（第十六节 transfer learning and semi-supervised
learning）
1. transfer learning，learning to
learn，授人以鱼，不如授人以渔
2. consider a set of learning
tasks, solve them jointly.
应用场景，某一个task的训练样本很少，不够，那么transfer learning就可以通过共用样本，提高效果。
4. 感觉这个和压缩感知Compressed
Sensing的思想比较相近
15分钟左右有一个关于推荐的介绍，可以学习一下：user对movie的打分可以看做一个函数，不同的user的打分函数具有相关性，这就能够和transfer
learning结合起来
6. feature transfer or model
7. semi-supervised
learning的意义：label数据是很有意思的，但得到label数据的代价很大，所以semi-supvised
learning是一个折中。
（第十七节 recommendation system）
1. 推荐：得人心者得天下
2. 推荐系统两种方式：
& 协同过滤-买了这个产品的人还买了...
& 相关推荐-和这个产品相似的产品
3. amazon 三分之一的销量来自于推荐
4. Netflix 百分之六十的电影租赁来自于推荐
协同过滤：以user和item组成二维矩阵，基于协同过滤的推荐就是计算出矩阵中缺省的值。
6. 由于存在user 打分的bias，e.g.
user1打分区间为[1,3],user2的打分区间为[3,5],去除这种偏差很有必要，这就是data
preprocessing，具体细节可查阅相关文档。
7. CF as supervised
learning：为每一个user建模，目标就是该user的打分，特征可以是其他user的打分，这个与图像多为特征相似(不同尺度、频率的图像本身作为特征)
最近临方法，关键是相似度similarity计算，具体算法可参考相关资料，计算到相似度后就可以以相似度为权重加权求解得到打分值。
矩阵分解求解缺省打分，一个假设是low-rank矩阵，即假设各个打分之间具有一定的相关性，具体算法SVD。
（第十八节 learning on image， 十九节 learning on
1. computer vision
2. 主要是给出了一些应用例子，e.g 3D街景
3. learning on
web应用：classification、 ranking、 community analysis、 recommendation、
user behavior modeling、quality assessment
weight：越低频词、weight越大(信息熵)
5. Query信息挖掘：一个query
通常只有2-3个词，字面的信息量非常有限，一种有效的方法就是用query去搜索引擎里面搜索，返回的top结果作为Query的辅助信息，这样信息就非常丰富了。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。Matrix Completion}