cs229 斯坦福机器学习笔记（二）-- LR回顾与svm算法idea理解
LR回顾
Linear Regression（LR）作为机器学习领域的基础算法之一，在初学者的学习过程中常常被视为一道难以逾越的门槛。值得注意的是，Linear Regression（LR）和Logistic Regression（LGR）都属于广义线性模型（Generalized Linear Model, GLM）。具体来说，在应用Logistic函数进行变换后，默认输出结果即为事件发生的概率值。其损失函数与似然函数取对数后存在相似的关系，并均可作为优化的目标函数。然而，在理论支撑上更为严谨的是似然函数这一概念。对于Linear Regression而言，默认采用残差平方和的形式构建损失函数具有一定的直观合理性；但对于Logistic Regression而言，则需要将预测结果转换至概率空间更为合理。这种差异的根本原因在于后者涉及非凸优化问题，在实际求解过程中更具挑战性。
该课程机器学习（ML）配套习题文档质量较高
Typically, it is common to observe that the coefficient w_0 is omitted from the regularizer, as a result of including w_0. This omission can lead to results being influenced by the choice of origin for the target variable (Hastie et al., 2001). Alternatively, it may be included, though with its own separate regularization coefficient. We will delve into this topic in more detail in Section 5.5.1.]
在prml中提到了两个要点。相对容易理解地说，也就是说你可以选择对y进行线性变换，或者对w0单独施加一个正则化系数。
一个值得注意的问题是，在工作中讨论到的LR模型具体指的是哪一种？通常情况下指的是Logistic Regression而非Linear Regression。其输出结果可以直接表示为一个分数值，在实际应用中通常用于 ctr（PV/CTR）预测等场景。Logistic Regression具有显著特点：通过对"发生比"（odd ratio）取自然对数后与特征向量进行线性组合（w*x），能够建立线性关系。（参考李航《统计学习方法》的相关内容）
另一个需要关注的问题是正则项。它主要用于防止过拟合。那么L1和L2正则化具体指的是什么？这确实让人有些困惑。从概率统计的角度来看, 正则项属于贝叶斯规则化方法（"我们会在参数中引入高斯先验概率并计算MAP估计（而不是MLE），如ufldl平台上的讨论指出"），随后可以通过查阅知乎回答 http://www.zhihu.com/question/20700829 来进一步了解这一概念。
后来我在查看scikit-learn文档时，注意到其中有一些新的术语出现让我感到有些震惊的是这些新名词其实并没有太多复杂的含义原来它不过就是换了种包装而已并不需要深入学习就明白了
L2 regularization -> ridge
L1 regularization -> lasso
mix L1 and L2 -> elastic Net
LR是一种基于线性的模型。尽管具有简洁明了的优势，但也基于较强的假设。值得注意的是，在这种情况下，权重的参数依然是可加的。为了拟合复杂的非线性问题，在实际应用中通常会采用特征工程来扩展输入空间。
离散化：例如，在教育领域中进行分类教学时会遇到这种情况：两名学生参加高考后分别获得98分和95分的成绩，在分数上存在差异；然而从综合能力来看，则没有太大的差别；这样的细化反而容易导致不必要的复杂性。因此我们建议将成绩进行分段处理并采用四类评价指标（A、B、C、D），具体可采用四位二进制编码的方式表示每个类别：A=0001,B=0010,C=0100,D=1000.举个例子来说,年龄划分如18岁及以下为青年阶段,...
在数据预处理阶段中进行特征工程：数值属性与ID属性通过特定方法进行整合成一系列新特征。例如，在服装分类任务中，“query品类”中将男性服装赋值为"0"或"1"（即男装=0、女装=1），而其他属性如用户的购买能力（x）和等级（y）则通过计算其笛卡尔积的方式生成四个新的特征指标：即分别计算"购买能力与男装品类"、"购买能力与女装品类"、"用户等级与男装品类"以及"用户等级与女装品类"等四者的交集结果。通过这种非线性拟合方式实际上实现了对原始特征进行“AND”操作的扩展。
开始svm
第二个障碍是SVM的学习。尽管SVM看似复杂难懂，在实际应用中其核心思想较为简单易懂。在课程学习过程中建议优先掌握凸优化的基础知识（根据session notes提供的两份简明教材：cs229-cvxopt.pdf和cs229-cvxopt2.pdf）。从知识体系来看，在深入了解SVM之前，请确保已经掌握了凸优化的基本概念。然而，在实际学习中发现纯粹地研究这些数学理论可能会让人感到枯燥。或许可以从SVM入手，在深入理解其内部机制后（特别是对偶问题的概念），再回过头来系统性地复习凸优化理论会更加高效有趣。在这门课程的学习过程中估计能迅速掌握这一技术的核心要义。最初的学习阶段容易陷入纯数学推导的陷阱而难以自拔地深入研究下去。而真正有趣的部分往往是在深入理解算法本质之后才会激发兴趣去探索更深层次的内容
对比分析LR与SVM。SVM在分类时将焦点集中在决策边界上（更具体地说，则是由支持向量支撑这一过程），而Logistic Regression则综合考虑所有样本特征进行建模。这让我想起了Photoshop中的一个边缘检测滤镜工具。再三思考后发现，在分类任务中我们是否应该特别关注位于边界附近的区域？离边界太远的数据点是否有必要进行深入分析？
以数学语言表述，则SVM的损失函数被定义为Hinge损失函数[http://en.wikipedia.org/wiki/Hinge_loss]。
svm其实就这么简单！
l(y) = max ( 0, 1 - t*y ) 。
一个神奇的max操作，就把离边界太远的点丢掉了（loss=0了，直接丢掉）。
因此cs229的教材中关于SVM的部分让我感到十分吃力且难以掌握；而Coursera上的课程则仅仅是绘制了一个简图。
尽管从图像上看两者较为接近；然而在计算层面还需要应用拉格朗日对偶原理来剔除那些远离边界的点；这样一来显得处理起来有些繁琐。
或者，我们可以从另外一个角度来理解svm。svm训练完的模型也是wTx + b，
而其中
我们可以理解为给每个样本x(i)，我们赋予了α_i以指示其是否属于support vector。通过不断迭代优化过程，在边缘区域外侧的点会逐渐被置零地排除在外。与此同时我们还可以观察到w^T x本身等同于由支持向量所张成的空间即线性生成空间。进一步比较与逻辑回归方法相比在假设输入特征位于二维空间(xi ∈ R^2)时逻辑回归模型仅包含三个参数而支持向量机则依赖于被赋予非零值的支持向量数量这可能远超两个从而构建出一个更为复杂的分类器结构
对比LR，正则化项C=1/λ
模型分析结果表明：通过逻辑回归方法得到的参数向量为w，在支持向量机中，则参数向量由以下公式定义：在支持向量机中，参数向量w由各个样本点的拉格朗日乘子α_i、类别标签y_i以及样本特征x_i共同决定。若采用核函数处理，则需将原始特征映射到更高维的空间中以捕捉复杂的非线性关系。仅保存参数向量w将无法捕捉复杂的非线性模式。
简单小结一下：
- SVM重视边界区域，在训练时会剔除远离边界的样本点。当输入数据质量不高时（即精度较低），模型的预测结果通常仅限于-1或+1类别。
- LR综合所有样本进行分析，在分类时会计算每个样本的概率得分（较为精细）。
动手实践svm
先前购买了《机器学习实战》这本书。我也感觉用书中的代码进行实践应用SVM是一个非常有效的方法。
分类战车有一个简明扼要的总结不错。用的就是《机器学习实战》的例子，在代码实现的过程中有一些公式需要进行简单的推导。在书中指出一下子豁然开朗了呢？一开始还不太明白。
【分类战车SVM】这个系列终于写完了，第一话：开题话http://t.cn/RAl1Qou；第二话：线性分类http://t.cn/RAl1QoT；第三话：拉格朗日对偶http://t.cn/RAl1Qom；第四话：核函数http://t.cn/RAl1QoE；第五话：SMOhttp://t.cn/RAl1Qon；第六话：编程http://t.cn/RAl1QoQ；附录：http://t.cn/RAl1QoR若想构建SVM模型及其实现细节（包括拉格朗日乘子法与KKT条件），扎实掌握相关数学原理是必不可少的前提。\n\n过去我对这些关键理论仅皮毛了解时，在编写伪代码模拟SVM的过程中并没有获得实质性的提升。\n\n经过实际操作后才逐渐体会到其中奥妙所在。\n\n《机器学习实战》用的是Python语言实现了相关内容；完成Coursera课程后的实践作业后发现使用Octave编写程序更为顺手且与数学理论紧密契合。
function model=svm(X, y, C, max_iter, Kernel)
y( y==0 ) = -1;
%m: # of sample
%n: # of feature dimension
[m,n] = size(X);
alphas = zeros(m,1);
b=0;
toler=1e-3;
K = zeros(m);
for i = 1:m
for j = i:m
K(i,j) = Kernel(X(i,:)', X(j,:)');
K(j,i) = K(i,j); %the matrix is symmetric
end
end
iter = 0;
while iter < max_iter
alphaPairsChanged = 0;
for i = 1:m
fXi = f (alphas, y, X, b , i, K);
Ei = fXi - y(i);
if ( y(i) * Ei < -toler & alphas(i) < C ) ...
|| ( y(i)* Ei > toler & alphas(i) > 0 )
j = randSelectJ ( i, m );
#j = mod(i + 1 , m ) + 1;
fXj = f (alphas, y, X, b , j, K);
Ej = fXj - y(j);
alpha_i_old = alphas(i);
alpha_j_old = alphas(j);
if ( y(i) ~= y(j) )
L=max( 0, alphas(j) -alphas(i) );
H=min( C, C + alphas(j) -alphas(i) );
else
L=max(0, alphas(j) + alphas(i) - C);
H=min(C, alphas(j) + alphas(i) );
end
if L == H
fprintf("L==H!\n");
continue;
end
eta = 2 * K(i,j ) - K(i,i) - K(j, j);
if ( eta >= 0 )
fprintf("eta>=0\n");
continue;
end
alphas(j) -= y(j) * (Ei -Ej) /eta;
tmp_j= clipAlpha( alphas(j), H, L );
alphas(j) = tmp_j;
if ( abs( alphas(j) - alpha_j_old ) < 0.00001 )
continue;
end
alphas(i) += y(j) * y(i) * (alpha_j_old - alphas(j) );
b1 = b - Ei - y(i) * ( alphas(i) - alpha_i_old) * K( i, i ) ...
- y(j) * ( alphas(j) - alpha_j_old ) * K( i, j );
b2 = b - Ej - y(i) * ( alphas(i) - alpha_i_old) * K( i, j ) ...
- y(j) * ( alphas(j) - alpha_j_old ) * K( j, j );
if ( 0 < alphas(i) ) & ( C > alphas(i) )
b = b1;
elseif ( 0 < alphas(j) ) & ( C > alphas(j) )
b = b2;
else
b = (b1+b2)/2;
end
alphaPairsChanged += 1;
fprintf("iter: %d, i:%d, pairs changed %d\n", iter, i, alphaPairsChanged);
if exist('OCTAVE_VERSION')
fflush(stdout);
end
end %END OF IF
end %END OF FOR
if alphaPairsChanged == 0
iter += 1;
else
iter =0;
end
fprintf( "iteration number : %d\n", iter);
end
idx = alphas > 0;
model.idx=idx;
model.X= X(idx,:);
model.y= y(idx);
model.kernelFunction = Kernel;
model.b= b;
model.alphas= alphas(idx);
model.w = ((alphas.*y)'*X)';
end
体会：
| svm | LR |
|---|
模型中也包括原始输入向量X及其对应的标签y；（例如，在支持向量存在的情况下），如果不使用核函数，则可以直接计算最终参数向量w
y的取值为\{-1, 1\}；然而，在实现过程中遇到了问题；未意识到输入数据中y的真实取值为\{0, 1\}；通过查看调试信息才意识到。
最初我认为SVM厉害的原因是因为它支持核函数。那么核函数仅仅是SVM独有的吗？ 不是。为何逻辑回归不采用核函数？ 视频中指出其求解效率较低。目前对此问题也未深入探究。