实施PEGASOS：用于SVM，逻辑回归和在情感分类中的应用的原始估计子GrAdient求解器（Python）
虽然支持向量机模型（二进制分类器）通常是通过解决对偶空间中的二次规划问题来构建的，但也可以通过解决原始优化问题来快速构建。在本文中，将通过使用随机梯度适当的子梯度求解器解决原始优化问题，来描述支持向量机的实现。如Shai Shalev-Shwartz等人在其原始论文中所述，该算法称为Pegasos算法 。         
首先将描述Pegasos算法的原始版本，然后是内核版本，以及一些数据集上的一些应用程序。   
接下来，SVM的铰链损失函数将被Logistic回归的对数损失函数所替代，并且原始SVM问题将被转换为正则Logistic回归。      
最后，通过首先在语料库上训练Perceptron，SVM（使用Pegasos）和Logistic回归分类器，然后在语料库中看不见的部分对其进行测试，来完成文档情感分类。
将计算训练分类器的时间以及在保留的数据集上获得的准确性。
1.通过使用带有PEGASOS的SGD将具有铰链损耗的主要目标最小化来实现SVM
如幻灯片中的下图所示，Soft-SVM Primal Lagrangian可以表示如下：  
f31
或如果舍弃显式偏差项，则如下所示：
f32
其中0-1损耗由铰链损耗估算。   
f29
将正则化常数更改为λ，可以如下所示使用铰接损耗等效表示，如下图所示（取自Pegasos论文）。     
下图还描述了Pegasos算法，该算法通过精心选择的步骤对原始物镜（拉格朗日）执行SGD。      
由于铰链损耗不是连续的，因此 将目标的次梯度考虑为使用SGD的单个更新步骤进行梯度计算。   
学习率η随着迭代而逐渐降低。
f25
下图显示了该算法的简化版本：
f33.png
f34.png
f35.png
以下python代码实现了该算法：
1个
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18岁
19
20
21
22
23
24
25
26
27
class SVMPegasos(LinearClassifier):
"Implementation of SVM with SGD with PEGASOS Algorithm"
def __init__(self
self.n_iter = n_iter
self.lambda1 = lambda1
def fit(self
Y = list(Y)
self.find_classes(Y)
# convert all output values to +1 or -1
Yn = [sign(y
X = X.toarray()
m
self.w = numpy.zeros( n_features )
#print(m)
for i in range(self.n_iter):
eta = 1. / (self.lambda1*(i+1))
j = numpy.random.choice(m
x
score = self.w.dot(x)
if y*score /code> 1:
self.w = (1 - eta*self.lambda1)*self.w + eta*y*x
else:
self.w = (1 - eta*self.lambda1)*self.w
一些注意事项
省略了可选的投影步骤（纸张方括号中的线）。
与往常一样，对于正例，输出（在列表Y中）编码为+1，对于负例，编码为-1。
η是梯度下降的步长。
如果步长η设置不正确，则梯度下降算法可能无法找到最小值。为了避免这种困难，Pegasos 使用了可变的步长：η= 1 /（λ·t）。
由于我们通过除以t来计算步长，因此步长将逐渐变小。这样做的目的是避免“反弹”问题接近最佳情况。
尽管在此实现中放弃了目标函数中的偏置变量b，但本文也提出了几种学习偏置项（非正则化）的方法，最快的实现可能是在PEGASOS算法返回后的实际间隔内进行二进制搜索最佳w。   
使用PEGASOS SVM实现对以下线性可分离的数据集进行分类，并增加一些噪声（重叠）
卵?w=150&h=128 150w，https : //sandipanweb.files.wordpress.com/2018/04/ov.png ? w = 300 & h = 255 300w“ size =”（最大宽度：765px）100vw，765px“ />
以下动画和图分别显示了最终决策面以及针对主要SVM分类器的PGEASOS实现，使用SGD的单点更新步骤如何改变决策面（边界）。
与往常一样，来自数据集的80％随机样本用于训练，而20％用于测试。使用固定种子可获得可重复的结果。
数据集很小（仅包含200行），使用PEGASOS SVM实现的训练阶段运行非常快，仅需24毫秒。
在测试拆分中获得的分类精度为95％。
pov  svm_ovHTTPS：//sandipanweb.files.wordpress.com/2018/04/svm_ov.png W = 150点? 150W，?w= 300＆am ... 300w“ size =”（最大宽度：845px）100vw，845px“ />
2.内核化的PEGASOS
来自同一篇论文的下一张图显示了该算法如何适应内核SVM。
f26?w=95&h=150 95w，https : //sandipanweb.files.wordpress.com/2018/04/f26.png ? w = 190 & h ... 190w“ size =”（最大宽度：846px）100vw，846px“ />
使用PEGASOS实现对以下线性不可分离的数据集进行分类
数据集1 火焰
下面的动画和图形分别显示了最终决策面以及针对原始SVM分类器的内核化PGEASOS实现，使用SGD的单点更新步骤的决策面（边界）如何变化，分别用于两个不同的线性不可分离的数据集。  
与往常一样，来自数据集的80％随机样本用于训练，而20％用于测试。使用固定种子可获得可重复的结果。
数据集很小（仅包含240行），并且使用内核化PEGASOS SVM实现（使用高斯内核）的训练阶段 运行非常快，仅花费了2.09秒。
在测试拆分中获得的分类精度为95.8％。
发炎  svm_flameHTTPS：//sandipanweb.files.wordpress.com/2018/04/svm_flame.png W = 150 ...... 150W，?w= 300 ... 300w“ size =”（最大宽度：883px）100vw，883px“ />
数据集2
in那教HTTPS：//sandipanweb.files.wordpress.com/2018/04/jain.png W = 150＆... 150W，?w= 300＆... 300w“ size =”（最大宽度：783px）100vw，783px“ />
下面的动画和图形分别显示了最终决策面以及针对原始SVM分类器的内核化PGEASOS实现，使用SGD的单点更新步骤的决策面（边界）如何变化，分别用于两个不同的线性不可分离的数据集。  
与往常一样，来自数据集的80％随机样本用于训练，而20％用于测试。使用固定种子可获得可重复的结果。
数据集很小（仅包含373行），并且使用Kernelized PEGASOS SVM实现（使用Gaussian Kernel ）的训练阶段运行非常快，仅需5.1秒。
在测试拆分中获得的分类精度为100％。
ja  svm_jainHTTPS：//sandipanweb.files.wordpress.com/2018/04/svm_jain.png W = 150＆... 150W，?w= 300＆... 300w“ size =”（最大宽度：1079px）100vw，1079px“ />
3.从SVM到逻辑回归
下图显示了如何通过改变PEGASOS算法中的损失函数（从铰链损耗到对数损耗）来训练逻辑回归模型。     
f30?w=71 71w，https : //sandipanweb.files.wordpress.com/2018/04/f30.png ? w = 142 142w， 690w“ size =”（最大宽度：676px）100vw，676px“ />   f36.pnghttps://sandipanweb.files.wordpress.com/2018 /04/f36.png?w=150 150w，https: //sandipanweb.files.wordpress.com/2018/04/f36.png?w = 300 300w，https: //sandipanweb.files.wordpress.com/2018 /04/f36.png 754w“ size =”（最大宽度：688px）100vw，688px“ />   f27?w=150&h=62 150w ，https：//sandipanweb.files.wordpress.com/2018/04/f27.png？w = 300＆h ...300w“ size =”（最大宽度：721px）100vw，721px“ />   f28.pnghttps：//sandipanweb.files.wordpress.com/2018/04/f28.png？w = 150＆h ... 150w，https：// sandipanweb.files.wordpress.com/2018/04/f28.png?w=300&h ... 300w“ Size =”（最大宽度：682px）100vw，682px“ />
使用PEGASOS Logistic回归实现对具有某些附加噪声（重叠）的同一线性可分离数据集进行分类
以下动画和图形分别显示了最终决策面以及Logistic回归分类器的PGEASOS实现的单点更新步骤（SGD）如何随着单点更新步骤改变决策面（边界）。  
与往常一样，来自数据集的80％随机样本用于训练，而20％用于测试。使用固定种子可获得可重复的结果。
数据集很小（仅包含200行），使用PEGASOS LR实施的训练阶段运行非常快，仅需27毫秒。
在测试拆分中获得的分类精度为97.5％。
povl.gif  lr_ovHTTPS：//sandipanweb.files.wordpress.com/2018/04/lr_ov.png W = 150＆... 150W，?w= 300＆... 300w“ size =”（最大宽度：635px）100vw，635px“ />
4.使用线性分类器（SGD实现）对文本进行情感分类：感知器，SVM和PEGASOS的逻辑回归
给定以下包含11914个文本的数据集，让我们在80％的样本上将Perceptron模型与采用PEGASOS算法的SVM / LR模型进行拟合，并预测对20％保留文本的情感进行分类，然后计算准确性。下图显示了语料库的前几行以及正面和负面情绪示例的数量。
f37.png?w=150&h=96 150w，https : //sandipanweb.files.wordpress.com/2018/04/f37.png ? w = 300 & h ... 300w“ size =”（最大宽度：518px）100vw，518px“ />
f39?w=150&h=74 150w“ size =”（最大宽度：202px）100vw，202px“ />
下图显示了不同情感下文本的字长分布。
f38.png?w=150 150w，https: //sandipanweb.files.wordpress.com/2018/04/f38.png ? w = 300 300w，?w=768 768w，https: //sandipanweb.files.wordpress.com/2018/04/f38.png 935w“ size =”（最大宽度：676px）100vw，676px“ />
脚步
创建sklearn管道以  
计算简单BOW设有（CountVectorizer 从sklearn）：得到51063列与弓。
使用sklearn SelectKBest选择前5000个功能  
训练/测试模型
在数据集的80％上训练分类器（Perceptron或带有PEGASOS的SVM / LR）。
根据数据集的20％预测情感，并通过与基本事实进行比较来计算准确性。
还记录训练分类器所花费的时间。
查找分类器找到的最上面的正词和负词（分别对应于最高和最低值的系数）。
以下python代码显示了如何使用SVMPegasos实现文本分类管道。   
1个
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18岁
19
20
def classify_with_svm():
# read all the documents
X
# split into training and test parts
Xtrain
random_state=0)
classifier = Pipeline( [('vec'
tokenizer = lambda x: x))
('fs'
('cls'
t0 = time.time()
classifier.fit(Xtrain
t1 = time.time()
print('Training time:'
Yguess = classifier.predict(Xtest)
print('accuracy:'
一些注意事项
可以通过应用更多的文本挖掘技术（例如预处理，包括语言模型/ tf-idf功能）来提高分类器的准确性。
该实验只是为了测试/比较具有Perceptron的SVM / LR PEGASOS。
PEGASOS模型的准确性也可以通过调整超参数来提高（例如，PEGASOS LR / SVM的正则化参数λ，要训练的迭代次数等）。
对于Perceptron，整个训练数据在训练时会传递给模型10次。
对于正则化SVM和逻辑回归的PEGASOS SGD实现，使用的迭代次数为10 * size_of_training_dataset。另外，使用的λ值为0.01。
结果
可以看出，即使具有非常简单的功能，所有分类器在测试集上的预测准确性和训练模型所花费的时间方面的性能也很好，并且彼此可比。
题库