2L

第三章 linear model for regression
首先总结下看之前的一些疑问
（1.1）优化目标是RSS时，和MLE之间的等价转化
（1.2）优化目标的图形化解释
（2.1）正则化在数学表达式上的解释
（2.2）正则化图形化的解释
（2.3）LASSO 的selection是如何实现的
（2.4）正则化参数lambda选择所造成的影响

=（2.1）正则化在数学表达式上的解释
没有带上正则项的优化函数求梯度后得到Xw=y，X不一定是方阵，所以求伪逆X* = （XTX）^-1 XT，得到w = X*y
由于当X有线性相关列时，XTX接近奇异，产生的w波动比较大（数值较大）？？？（TODO）造成overfit？？？
当然数据集足够大的时候就不会有这样的问题？？？
带上正则项的优化函数求梯度后得到w =（aI + XTX）^-1 XTy，a是惩罚项系数，可以求逆？？？

=（2.2）正则化图形化的解释
首先正则化就是为了防止overfit，防止参数过于贴合训练数据，而不能泛化未知数据。
也就是说，目标函数在最优化的同时不能只是考虑数据如何减少RSS，对于w参数来说，应该距离RSS的最低值有一些距离。
为了使得参数偏离最低值，有不同正则化项的选择，例如LASSO（L1-norm）和Ridge（L2-norm）等。
解释：由拉格朗日乘数法可以将 带正则项的优化问题转化为 【带正则项约束的 原问题】。那么通过这个约束和原问题的作图，可以看到正则项起的作用就是防止过拟合overfit。
[math stackexchange why-are-additional-constraint-and-penalty-term-equivalent-in-ridge-regression]
具体的，假设一共就两个参数w1 w2，作原问题的优化函数的contour，因为优化问题是2次函数（RSS），所以这个contour的所有等值线是一圈一圈的椭圆，中心就是最有值（达到minimum RSS），现在要增加约束使得参数偏离这个点。
再画约束，转化后得到的约束实际上是使得正则项小于某个常数，这个常数和最有值w1，w2有关，也和正则项的惩罚度lambda有关。但既然是一个常数，可以先画出正则项关于某个常数的函数。（k实际上通过两个问题的等价转换可以得到就是正则化项在最优值w*取到的值，例如原问题的最优值是w*，那么对于ridge来说k=l2-norm(w*)）
Ridge是个圆w1^2+w2^2 <= k
lasso是一个正菱形| w1| + |w2| <= k
现在优化函数从中心（min）一圈一圈往外扩散，越往外扩产生RSS就越大，overfit的程度就越低（也可以说限制模型复杂度的程度就越大），直到碰到约束（即满足了约束），那么也就找到正则化优化问题的最优解。

=（2.3）LASSO 的selection是如何实现的
Lasso可以选择feature的原因在于，在优化过程中某些参数变成0了，从图中看
[stats stackexchange geometric-interpretation-of-penalized-linear-regression]
确实可以变为0，而ridge就只能逼近0
也就是说中心点不会落在坐标轴上？？？（TODO）
=（2.4）正则化参数lambda选择所造成的影响
首先lambda选为0，那么就等价于没有正则化
当lambda越大，说明在整个优化函数中占的比重就越大，优化时会更多考虑使得正则化项变得更小，也就是w1，w2的最优值会相对更接近0的位置，那么从（2.3）来看就是两个contours相碰的位置更接近0的位置，自然原问题的RSS也就相对更大，overfit程度就缓解更多（当然也可能underfit）

正好开始看scikit的tutorial，一开始就是regression
包括
ordinary least squares 原始优化问题，优化目标是最小化RSS residue sum of squares
ridge 岭回归，正则项 wTw = w1^2 + w2^2 + ...
lasso Least Absolute Shrinkage and Selection Operator，|w1|+|w2|+...
按名字来看，正则项就是参数绝对值求和，还包括feature selection的功能，也就是某几项参数会变成0
【所有正则项都不包括intercept w0】？？？？？TODO
如果没有正则项，那么目标函数就会向着最小误差去调整参数
在curve fitting的例子里面，就是使得曲线去贴合所有样本点
然而在样本点不够多的情况下，就会导致overfit
（理解：这个例子里features x^0, x^1, x^2, ...并不是线性相关的，overfit形成的原因是维数？？？）

在逻辑回归之前，先要回顾一下感知机
统计学习方法【ch2】
Perceptron
所谓感知机，就是给定带有2种label的点，假设全部线性可分，寻找任意一个超平面将其切分。
上面就是几何解释，具体说就是
wx+b = 0， w是法向量
根据寻找目的，可以看到整个寻找过程是根据误分类点进行的
那么定义损失函数就是误分类点到超平面的距离1/|w| * (-y * [ wx + b] )，由于前面的系数可以转化为等价的最优解，所以直接优化-y * [w x + b]
由于是误分类点驱动的，所以无法直接求导求最小值
用SGD迭代算，可以看到w每次更新都是w=w+a y x, b=b+ay
那么说明最后的w会是 sum ai yi xi的形式
====================================
于是就引出了【对偶形式】的感知机模型
将w参数的求解转化为对a参数的求解，最后通过a来求w

统计学习 就是从训练数据X中学习到决策函数f(X)或者条件概率分布P(Y|X)
学习到的模型可以分为判别discriminative 和生成 generative模型
判别指的是直接学习到决策函数或者条件概率
而生成模型是学习联合分布P(X,Y)后再推导出P(Y|X)
=====================
学习策略
统计学习方法 ch1 p7-9
按照什么准则选择最优模型？
1、损失函数 loss function （TODO）
预测值f(X) 和 真实值Y
0-1损失、平方损失、绝对损失、
对数损失
L(Y[true], P(Y|X) ) = - log P(Y[true] | X)，也就是如果在X前提下输出Y[true]的概率是1，那么损失为0
反之，如果这个概率很小，则损失很大
2、风险函数，期望损失
也就是基于联合分布P(X,Y)的损失函数的期望值
3、经验损失
由于联合分布本来就是要求的内容，所以上面的期望值不能计算
但是对于给定的训练集，可以求这些数据集X上的损失函数的期望
这样的期望值就称为经验损失，N无穷的时候可以看成是期望损失
所以就有了经验风险损失最小化这样的准则，例如MLE
但是由于数据集有限，容易overfit
所以又有了结构风险最小化这样的准则，例如MAP（正则项为prior）。
结构风险最小化就是正则化，添加参数模型复杂度的约束。

最大熵模型
就是要从符合约束条件的模型（概率分布）中，找到熵最大的模型。
在机器学习中，最大熵模型学习的是P（Y|X），所以找到的是条件熵最大的模型。
===============
这里约束条件是从训练数据和XY变量之间的约束关系得到。
1、首先是XY变量之间的约束关系。
例如：在POS中，X可能就是连续的几个单词，Y就是词性，给定约束当单词为固定搭配的时候，词性也会固定，这个时候就存在（X，Y）的约束
用特征函数fi(x,y)【对所有x属于X，y属于Y】表示是否存在第i个约束（=1）
2、模型是从训练数据学习得到，所以可以从训练数据中计算得到经验联合分布和X的经验分布
然后对于所有的特征函数，关于经验分布的期望值应该和关于最大熵模型的期望值相等。
=================
所以最后的最大熵模型的目标函数就是
max 模型的条件熵
s.t. 对于所有的模型，满足特征函数的期望值=其关于经验分布的期望值
=================
由拉格朗日乘数法可以转化为min max L 的原问题，等价于求解其对偶问题max min_P L，
这里记Pw = minL，可以看到最后要求max_w Pw
其实这是和MLE等价的（这里的ML就是用基于联合经验分布的形式表示后进行推导）

GLM
h_theta(x): prediction func
theta: params
==========
general linear model:
0) 模型 p(y|x) ~ exponential family p(y; eta) = b(y) exp(eta^T T(y) - a(eta))
1) h_theta(x) predict E(y|x)
2) eta = theta^T x
1、线性回归，linear regression，lms，sgd，ols，prob-interpretation
模型 p(y|x) ~ N(mu,sigma2), h_theta(x) = theta^T X
2、逻辑回归，logistic regression，（y的取值为0，1）
模型 p(y|x) ~ Bernouril(phi), h_theta(x) = g(theta^Tx), g --- sigmoid fn
[3*、感知机，perceptron，---> relate to svm]
no explicit explain from prob, MLE, h_thata(x) = g2(theta^T x) g2 --- 1 when > 0, otherwise 0
4、softmax，（y的取值为1，2，...，k）
模型p(y|x) ~ Multinomial(phi1，phi2， ...，phik)，h_theta(x) = [ ... ]

primal = dual
min_w f(w,x) s.t. gi(w,x) <= 0
L(w,x,a) = f(w,x) + sum aigi(w,x)
primal: min_w max_a L 原始问题等价于优化问题 p*
dual: max_a min_w L ----- d*
max min <= min max 等号成立有条件 f,g convex ... TODO
即p* = d*，同时对应的最有参数w*满足KKT条件
梯度w = 0
aigi = 0 <--- 互补条件
gi <= 0 <--- 约束条件
ai >=0
=====================
带入SVM的优化目标即可，
软间隔附上1-ei, c*sum ei
=====================
Kernel K（x,z）
由于训练、预测可以用内积表示，假设x是d维
那么把x扩展到高维的线性无关数据可以丰富特征？
即用K（x，z）=phi(x) dot phi(z)
不一定要显式找到phi，例如K（x,z） = (xz)^2 ....
gaussian kernel / rbf 映射到无限维 => similarity
===================
ova/ ava/ weston
===================
hinge loss 合页损失 max(0, ---) 只有当输出大于一定值时损失才为0
优化函数可以写成hinge loss的形式+L2正则化项