学习中碰到的一些优化工具包和库

时间:2023-01-28 09:33:17

各种优化请参考

http://www.mat.univie.ac.at/~neum/glopt.html

1.linear svm

这个工具包目前用的比较多。例如面部特征点的回归方法中,学习线性回归的权重,例如:Face Alignment at 3000 FPS中:
minWti=1N||s^tiWtΦt(Ii,St1i)||22+λ||Wt||22
权重 Wt 的学习,其也可以闭合形式的求解,即关于 Wt 求导,另其等于0.

2.Matlab自带的优化工具包。

进入Matlab帮助文档,Optimization Toolbox目录下,可看到Matlab提供了:
(1)非线性优化。

求解有约束的或者无约束的、带有一个或者多个目标的非线性问题.。可采用串行或者并行。(有约束的优化
,无约束的优化,多目标优化,额外的接口)

(2)线性规划和混合整数线性规划。

求解连续变量或者整变量的线性规划问题。

(3)二次规划。

说明:求解二次目标函数,线性约束的问题。

(4)最小二乘。

求解最小二次(曲线拟合)问题。(线性最小二乘问题,非线性最小二乘问题(曲线拟合))。

(5)非线性方程组。

找到非线性方法组的根。

3.CVX

CVX User’Guide.
伴随课程:EE364A和进阶版EE364b,
凸优化最重要的书籍:Convex Optimization. Stephen Boyd
Help:CVX 论坛
(1)支持一些标准问题类型。

线性规划(LPs),二次规划(QPs),二阶锥规划(SOCPs),和半正定规划(SDPs)

(2)可以解决一些更复杂的凸优化问题。

包括不可微的函数,例如 l1 范数。可以使用CVX很方便的表示和求解约束的范数最优化,熵最大化,行列式最大化,以及许多其他凸规划问题。

(3)可以求解混合整数的disciplined 凸规划。

混合整数的disciplined凸规划(MIDCPs),就是其中的一个或者多个变量的取值约束为整数。一个混合整数的问题不是凸的。找到全局最优值,需要组合传统的凸优化算和穷举搜索算法(例如branch-and-bound)算法。

(4)提供了特定的模式能够简化两种特殊类型问题的构造。即半正定规划模式和几何规划模式。

(5)CVX不是一个检查你的问题是否为凸的工具。
(6)CVX不能处理非常大规模的问题。

例如你的问题规划很大(例如一个巨大的图像处理或者机器学习问题),CVX效果不好,或者根本没有效果。
但是CVXy也同样扮演者重要的着色,例如开始开发一个特定的大规模的方法,你可以使用CVX求解该问题小尺度的或者简化的版本,来快速精确的实验你想解决的问题。例如对于图像的重构,你可能在50*50像素的图像上,使用CVX进行不同问题表示的实验。

(7)如果问题有可利用的结构(例如稀疏),并且你可以避免for循环(Maltab中很慢),并且也可以避免像函数log和exp(它们需逐次的逼近),那么CVX将可以解决中和大规模的问题。

4.SPAMS

SPAMS的全称为:Sparse Modeling Software,即稀疏建模软件。SPAMS是一个可以求解各种稀疏估计问题的优化工具包。

词典学习,矩阵的因式分解(NMF,sparse PCA,…)
使用LARS,坐标下降,OMP,SOMP,proximal method(近端算法)求解稀疏分解问题。
求解有结构的稀疏分解问题( l1/l2 , l1/l ,稀疏组lasso,树结构的正则化,带有组重叠的有结构的稀疏(structured sparsity with overlapping groups,…)

简介:
算法的实现用来求解带有稀疏正则项的机器学习和信号处理问题。
库采用C++编写,兼容Linux,Mac,Win 32和64bit。接口有Matlab,R,Python,C++、、。软件包需要BLAS和LAPACK的实现,进行线性代数的操作。
SPAMS可以分成几个工具箱并且包含了额外混杂的功能。
(1)词典学习和矩阵因式分解工具箱。包含了[20,21]的在线学习技术和其用来求解各种矩阵因式分解的变种。

稀疏编码的词典学习
稀疏主成分分析(sparse PCA,可以看作是一个稀疏的矩阵因式分解问题)
非负矩阵因式分解。
非负稀疏编码
dictionary learning with structured sparsity
原型分析(archetypal analysis)

(2) 稀疏分解工具。

正交匹配追踪(OMP,或者前向选择)
LARS/同论算法。(求解Lasso 和弹性网问题的变体)
LARS一个有权重的版本.
当数据带有一个二值掩码时的OMP和LARS.
坐标下降法算法求解 l1 分解问题。
贪婪方法求解同时信号近似[34,35]
基于块坐标下降方法求解带有 l1/l2 正则化的同时信号近似。
同论方法求解Fused-Lasso信号近似。
有效地投影到一些能够诱导稀疏的凸集,例如 l1 ball,弹性网或者Fused Lasso 约束集。
有效集算法(active-set algorithm)求解单纯性分解问题。

(3)近似工具箱(近端工具箱,Proximal toolbox)。实现的近似方法能够求解带有不同loss和正则化组合的一大类的稀疏近似问题。这个工具箱的主要特征是,提供了一个基于duality gaps的鲁棒性的停止准则来控制优化的质量。也可以处理大规模问题的稀疏特征矩阵。主要实现了:
正则项:

Tikhonov regularization( l2 范数的平方)
l1 范数, l2,l 范数
弹性网
Fused Lasso
树结构的 l2 范数的和
树结构的 l 范数的和
一般的 l 范数的和
mixed l1/l2 -norms on matrices
mixed l1/l -norms on matrices
mixed l1/l2 -norms on matrices plus l1
mixed l1/l -norms on matrices plus l1
带有 l2 或者 l 范数的group-lasso
group-lasso+ l1
多任务的树结构的 l 范数的和
迹范数
l0 伪范数(only with ISTA)
树结构的 l0 范数(only with ISTA)
矩阵秩的正则化(only with ISTA)
[24]中的路径编码惩罚

损失函数:

平方损失
缺省值的平方损失
logistic损失,带权重的logistic loss
多类的logistic

该工具箱也可以带有非负约束,处理截距和稀疏矩阵。也有一些未公开的功能,可以在源代码中看到。例如损失函数和正则项的一些组合,随机近似梯度方法和增量近似梯度方法。

5.SLEP

SLEP的全称为:Sparse Learning with Efficient Projections.
其网站首页列出了该算法库的四大优点:
(1) 一阶方法。每次迭代过程中,我们仅需要计算函数值和梯度,这样算法可以处理大规模的稀疏数据。
(2)最优收敛率。通过一阶黑箱子方法,针对平滑的凸优化问题,收敛速率为 O(1/k2)
(3)高效的投影。投影问题(近似操作,近端操作)可以有效地解决。
(4)Pathwise Solutions。SLEP软件包提供的函数可以通过热启动技术有效地计算pathwise solutions(相对应于一系列的正则化参数)。

简介:
许多真实世界的过程的基础表示通常是稀疏的。例如在疾病的诊断中,虽然人类有大量的基因,但是仅有少量的基因对某种疾病有贡献。在图像处理中,许多自然的信号是稀疏的,因为当在一个合适的基下进行表示时,它们拥有精确的表示。
l1
许多现有的关于稀疏学习的工作都是基于 l1 范数正则化的一个变体。因为 l1 正则化拥有:稀疏-诱导属性,凸的,和很强的理论保证,以及在各种应用中伟大的成功经验。
l1/l 范数正则化$
其属于复合的绝对惩罚家族,其实 l1 范数正则化的推广。
Fused Lasso Regularization
融合的Lasso正则化产生的解在系数和逐次差分(successive differences),都是稀疏的。其中特征通常以某种有意义的方式进行排序。所以要注意应用场合
Sparse Group Lasso
Lasso 和Group Lasso的扩展。稀疏组Lasso惩罚产生的解,可以达到组间和组内同时稀疏。也就是说许多特征组正好为零(这样就不用选择),并且在非零特征组的组内,一些特征也正好为0。因此可以应用于鉴别重要的组以及已选择组内的重要特征。稀疏组Lasso是树结构的组Lasso的一个特列。
Tree Structured Group Lasso
在树结构的组Lasso中,特征上的结构表示为一颗树,叶子节点为特征,内部节点为特征的簇。
Overlapping Group Lasso
可以利用Group Lasso,Sparse group Lasso,tree structured group Lasso达到组稀疏。但是组Lasso,和稀疏组Lasso仅限制于预先定义的不重叠的特征组上。并且树结构的组Lasso限制在树结构组上。因此在许多应用中,期望一个更灵活的(重叠)组结构。
Ordered Tree-Nonegative Max-Heap
在许多回归/分类问题中,特征呈现出某种分层或者有结构的关系,使用这些关系可以产生带有改善的回归/分类性能的性能的模型。在有序的凸结构中,假定:对于给定的回归/分类任务,只要父节点被选中,那么该节点就被选中。为了整合这样的有序的树结构,假定模型的参数服从非负最大堆(non-negative Max-heap)结构。这样的非负最大堆可以诱导所谓的”遗传原理’,人们已经证明了这对于高维变量的选择是有效的。
Trace-Norm Regularization
在机器学习,自动控制和图像压缩领域,最小化一个矩阵变量的秩,s.t.某些约束。例如,在协同过滤中,给定一个部分填充的评分矩阵,并且任务是预测缺失的项。因为,人们普遍认为,少量的因素对一个人的品味有贡献,很自然的,通过一个低秩矩阵近似的表示给定的平方矩阵。然而,矩阵秩的最小化问题是一个NPhard问题,一般来说是因为秩函数的组合性质。秩函数的一个常用的凸松弛是迹范数(核范数),定义为矩阵奇异值的和),因为迹范数是关于单位球的谱范数上的秩函数的凸包络。最近的一些工作已经表明,低秩解可以通过在某些条件下,最小化迹范数精确的得到。迹范数正则化 问题也可以认为是一种形式的稀疏学习,因为迹范数等价于由奇异值组合的矢量的 l1 范数。

6.mexopencv

可以在Matlab中调用OpenCV函数(并不是全部)。其也实现了Matlab个数据类型到OpenCV Mat对象的转换,因此可以在混合编程的时候,使用mexopencv作为数据传输的接口。

数据的转换:

int i = MxArray(prhs[0]).toInt();
double d = MxArray(prhs[0]).toDouble();
bool b = MxArray(prhs[0]).toBool();
std::string s = MxArray(prhs[0]).toString();
cv::Mat mat = MxArray(prhs[0]).toMat(); // For pixels
cv::Mat ndmat = MxArray(prhs[0]).toMatND(); // For N-D array
cv::Point pt = MxArray(prhs[0]).toPoint();
cv::Size siz = MxArray(prhs[0]).toSize();
cv::Rect rct = MxArray(prhs[0]).toRect();
cv::Scalar sc = MxArray(prhs[0]).toScalar();
cv::SparseMat s = MxArray(prhs[0]).toSparseMat(); // Only double to float
plhs[0] = MxArray(i);
plhs[0] = MxArray(d);
plhs[0] = MxArray(b);
plhs[0] = MxArray(s);
plhs[0] = MxArray(mat);
plhs[0] = MxArray(ndmat);
plhs[0] = MxArray(pt);
plhs[0] = MxArray(siz);
plhs[0] = MxArray(rct);
plhs[0] = MxArray(sc);
plhs[0] = MxArray(sp); // Only 2D float to double

7.VLFeat

VLFeat开源库实现了流行的机器视觉算法,特别是图像理解和局部特征的抽取,匹配。算法包括:
Fisher Vector,VLAD,SIFT,MSER,k-mean,分层的K-mean,凝聚式信息瓶颈算法,SLIC超像素,快速转变超像素,大规模SVM训练和其他的一些算法。为了高效性和兼容性,才用C语言编写,提供了Matlab接口。
其给出了一些特征的可视化,如Hog,SIFT等。
更详细的内容可以参考在线手册:
http://www.vlfeat.org/overview/tut.html
2013,CVPR,Supervised Descent Method and its Applications to Face Alignment中计算SIFT特征就是使用了该库。

8.Matlab自带的机器视觉工具

在Matlab控制台,输入help vision。或者进入help帮助文档,找到Computer Vision System Toolbox,就可以看到一些机器视觉算法。例如:特征检测,抽取和匹配,目标的检测和识别,运动分析和跟踪,相机标定,立体视觉,滤波,几何变换,形态学操作,统计,文本和图,转换(如DCT)等。
例如:
抽取HOG特征:extractHOGFeature,
人脸检测:faceDetector=vision.CascadeObjectDetector;….

9.flandmark/clandmark

基准点检测的开源代码。是一个很好的学习“图形结构检测特征点”的代码。
使用图形结构(Pictorial Structures)进行基准点的检测有两个开源的代码,一个是:2012,CVPR,Face Detection, Pose Estimation, and Landmark Localization in the Wildface.其使用的数据库是MultiPIE数据集,并不免费。带有13个视角(mixture)和68个特征点的数据集好像很难找。因此要学习其代码的实现就有点难。因此为了能够运行代码,需要自己简单的标定Pointing04的数据集,还需要注意特征点的标定顺序。其模型参数的求解使用了Dual Coordinate Descent Solvers for Large Structured Prediction Problems中的求解,代码读起来是相当的费劲。
另外一个就是flandmark/clandmark,其配置过程还不算复杂,需要使用如VS编译生成lib共Matlab调用。因此在程序调试的时候就比较棘手,还好有C++版本的。
通过这两个代码的学习,可以了解到如何使用广义距离变换求解最大化(最小化问题)。还可以学习到两种大规模的优化学习算法
(1)Bundle methods for regularized risk minimization.
(2)Dual Coordinate Descent Solvers for Large Structured Prediction Problems.
上面的两篇文章很不错,非常值得读。

10.CImg

CImg Library是一个小的,开源的,现代C++的,图像处理工具包。
有用: CImg定义管理图像的类和方法。可以使用CImg加载/保存各种文件类型,访问像素值,显示/转换/滤波图像,可以画基本元素(文本,人脸,曲线,3D目标),计算统计学,管理用户与图像的交互,等待。
通用性: CImg定义了简单的图像类,能够表示4维数据(1维标量信号,3维超分辨率的体积图像),模板的像素类型(bool,char,in float)。也可以处理图像集合和序列。
便携性: CImg是一个独立的,线程安全,高度可便携的。它可以工作子不同操作系统上(Unix,Window,MacOS X,*BSD,…),并且兼容各种C++编译器(VC++,g++,clang++,icc,…).
简单: CImg属于轻量级,仅需要包含单个头文件CImg.h到你的C++源文件中。其只定义了四种不等的类型,压缩进命名空间clim_library下,仅需要少量的标准C++和系统库。不需要依赖外来的或者复制的项。
扩展性: CImg可以使用额外的工具/库,例如Board,FFMPEG,FFTW3,GraphicsMagick,ImageMagick,Lapack,libcurl,libjpeg,libpng,libtiff,Magick++,OpenEXR OpenCV OpenMP或者XMedCon。而且使用简单的插件式的机制允许用户直接地根据自己的需要加强库的能力。
*:CImg是免费的,开源的库。可以使用在商业的应用中。

11.STPRtool

STPRtoo全称为:Statistical Pattern Recognition Toolbox
统计模式识别工具箱。
包含如贝叶斯分类,线性判别函数,广义的安德森任务,线性特征抽取,AdaBoost算法,核机器,核特征抽取,优化方法,RBF核的预图像问题,支持向量机,概率分布函数和估计,二次判别函数,可视化等。

12.Libqp

Libqp的全称为:Library for quadratic programming.求解二次规划的库。Libqp是c语言写的库,其实现了两种特定类型的凸二次规划(QP).

带有单纯性约束的二次规划
定义如下:
minimize12xTHx+xTfsubject toiIkxi=bk,kSequiIkxi=bk,kSneqxi0,iI
其中 x=(x1,...,xn)Rn 是优化矢量, HRn×n 是对称半正定矩阵, fRn 是一个矢量。 I=1,...,n 是一个索引集, I1,...,Im I 的子集,满足 I1...=I ,并且 I1...Ik=ϕ Sequ Sneq 是满足 SequSneg=1,...,m 的索引集,并且 SequSneq=ϕ(b1,...,bm)Rm 是正数。
实现的解决器libqp_splex.c是[1,2]提出的方法的一个广义化。它是基于带有一个改进的工作集选择策略的序列最小化算法(SMO)。例如应用在有结构的SVM学习,Bundle Method for Risk Minization ,带有L2软边界的二类SVM等。
例如在文章《Bundle Methods for Regularized Risk Minimizaition》中:
推论三:对于二次正则化即 Ω(w)=12||w||22 ,公式(10)变成:
αt=argmaxαRt{12λαTATAα+αTb|α0,||α||1=1} .
因为 ATA 是半正定矩阵:
xTATAx=(Ax)TAx=||Ax||220
并且满足上面的解决器的输入条件,因此可以调用。
带有边界约束(box constraints)和简单的线性等式约束的QP任务:
定义如下:
minimize12xTHx+xTfsubject toxTα=b,lixiui,i=1,...,n
其中 x=(x1,...,xn)Rn 是优化矢量。 HRn×n 是一个对称半正定矩阵, fRn 是一个矢量, aRn 是一个非零矢量, bR 是一个标量, (l1,...,ln)(R)n (u1,...,un)(R)n 分别表示下界和上界。

解决器libqp_gsmo.c精确的实现了文献[3]提出的广义的SMO。例如在训练带有L1软边界的二类SVM是需要求解这样的QP.

Matlab中的二次规划求解器
标准形式:
minx12xTHx+fTxAxbAeqx=beqlbxub
从标准形式来看,Matlab能够求解的二次规划问题看似更广泛。其使用的函数是quadprog。通过在控制台使用edit quadprog我们可以看到Matlab实现了三种求解二次规划的方法:
1.active set 有效集法
2.interior-point-convex 内点法
3.trust-region-reflective 置信域反射法

Libqp有两个优点
1.求解大规模的优化问题。
2.采用C实现,其运行速度是Malab的十几倍或者几十倍。

13.bmrm

bmrm的全称是Bundle Methods for Regularized Risk Minimization。其求解下面的无约束的优化问题:
minwJ(w)=λr(w)+l(w)
其中 λ>0 是正则化常数, r(w) 是一个凸的正则化项, l(w) 是经验风险函数,也就是说损失函数和的平均。例如给定m个特征-标签对 (xi,yi) ,线性支持向量机可以转换为下面的形式:
r(w)=12wTw
l(w)=1mi=1mmax(0,1yiwTxi)
这个库是模块化的,也就是说正则项和损失函数的实现不耦合,因此新的问题可以很容易地通过实现新的正则化项或者新的损失函数来进行建模。
此外该库提供了并行的框架。当损失函数可以分解时,也就是说实例 xi,yi) 可以分解成一些不相交的集,那么可以在这些集上独立的完成 l(w) 的计算。
实现的正则项和损失函数有:
正则项:L2,L1范数,(有不同的实现方法)
损失函数:
1.二类分类器,

Hinge
Squred Hinge
Huber hinge
Logistic regression
F-beta
ROC-score
Exponential
Novelty detection

2.一元回归

ϵ -insensitive
Least squares 最小二乘
Least absolute 最小一乘
Quantile regression 分位数回归
Poisson regression 泊松回归
Huber’s robust regression

3.多类分类器
4.多标签分类器
5.秩,线性搜索加强的损失函数,图匹配,半马尔科夫模型等

14.minConf

minConf是一组Matlab函数,其最优化可微的实值多元函数,并且优化参数存在简单的约束(s.t. simple constraints on the parameters)。在许多问题上,minConf中的这些函数比Matlab的fmincon函数求解问题更有效。同时minConf中的函数可以求解更大数量变量的问题,并且它使用的直线搜索对一些常见的函数病态具有鲁棒性。
函数:minConf_TMP(funObj,x,LB,UB,options)
即最小化下面的函数:
minxf(x)suject to LBxUB
例如

1.非负最小二乘 minw12||(Xwy)||2,s.t.w0
2.L1正则化的最下二乘 minw12||Xwy||2+λ||w||1 ,其可以转换为 minw12||Xwy||2+λiw,s.t.w0 ,
3.带有边界约束的Logistic 回归 minwilog(1+exp(y(i)wX(i,:)),s.t.1w1
4.对称支持向量机(no bias或者正则化的bias): minα12αTAαα,s.t.0αC,Ai,j=yiyjK(xi,xj)使σ=1RBF
5.顺序逻辑回归 minw,γ(log(F(γ(y+1)Xw)F(γ(y)Xw)))
其中 F(x)=1/(e+exp(x)),<0<γ(1)<γ(2)<...<
6.核顺序逻辑回归
7.Graphical LASSO: minWlog|σ+W|,s.t.Wijλ ,其中W是正定矩阵。
8.关联的条件随机场(训练使用伪似然):使用lsing势能优化伪似然,s.t.边是子模块(并且因此最优的MAP可以通过graph cuts方法找到)
函数minConf_SPG(funObj,x,funProj,options)和
函数minConf_PQN(funObj,x,funProj,options)
求解下面的最小化问题:
minxf(x)suject to xX
例如
1. 单纯性上的线性回归: minW|Xwy|2,s.t.w0,w=1
2. Lasso回归: minw|Xwy|2,s.t.iwitau
3.Lasso with Complex Variables: minw|Xzy|2,s.t.izitau ,其中z和y是复数,z表示复数模量。
4.Group-Sparse Linear Regression with Categorical Features: minw|Xwy|2,s.t.g|wg|tau ,其中X使用二值指示变量来表示一组分类特征,并且我们使用’groups’g依据最初的类别变量引诱稀疏。
5.Group-Sparse Simultaneous Regression: minW|XWY|2+λg|Wg|
6.Group-Sparse Multinomial Logistic Regression
7.Group-Sparse Multi-Task Classification
8.Low-Rank Multi-Task Classification
9.L_1,inf Blockwise-Sparse Graphical Lasso
10.L_1,2 Blockwise-Sparse Graphical Lasso
11.Linear Regression with the Over-Lasso
12.Kernelized dual form of support vector machines
13.Smooth (Primal) Support Vector Machine with Multiple Kernel Learning
14.Conditional Random Field Feature Selection
15.Approximating node marginals in undirected graphical models with variational mean field
16.Multi-State Markov Random Field Structure Learning
17.Conditional Random Field Structure Learning with Pseudo-Likelihood

13.rapidxml

快速的xml读写。使用方法参考博客:http://blog.csdn.net/wqvbjhc/article/details/7662931
或者rapidxml的帮助文档

14 Eigen

Eigen是求解线性代数:矩阵,矢量,数值求解和相关算法的一个C++模板库。目前版本为:3.3(2016,9,22)。
优点:通用,速度快,可靠性好,代码优雅,良好的编译器的支持。

15 minFunc

minFunc 是一个matlab函数,使用直线搜索方法(line-search method)求解可微的实值多元函数的无约束的优化问题。它使用的接口和Matlab优化工具箱中的函数fminunc很相似,并且可以替代这个函数的调用。在许多问题上,与fminunc(或者minimize.m)相比,minFunc需要更少的函数计算达到收敛。而且它可以优化更大数量变量的问题(fminunc受限于几个百个变量),并且使用直线搜索,对几种常见函数的病症具有鲁棒性。
minFunc的默认参数是拟牛顿法,其中在计算步进方向的时候,有限内存BFGS(limited-memory BFGS)的更新使用Shanno-Phua scaling,并且为了找到一个满足强Wolfe条件的点。 bracketing line-search 用于计算步进方向。在线性搜索中,使用三次插值产生试验值,并且方法切换到 an Armijo back-tracking line search on iteration.其中目标函数进入一个区域(其中参数不能产生一个实值的输出,也就是复数,Nan,or Inf)

特征:

  1. 下降方向(步进方向)的计算基于:Exact Newton(需要用户提供海森矩阵),full quasi-Newton approximation(使用一个稠密函数近似),limited-memory BFGS(使用一个低秩海森近似-默认),(预处理)Hession-free Newton(使用Hession-vector products),(预处理)共轭梯度(仅使用上一步和一个矢量beta),Barzilai and Borwein(仅使用上一步),或者(周期的)steepest descend.
  2. 步长的计算可以基于(非单调的)Armijo 或者Wolfe条件,试验值可以通过回溯法或者二分法或者多项式插值。存在一些可利用的策略来选择初始试验值。
  3. 数值微分和导数检查是可用的,包括一个选项,使用complex-step differentials自动的微分.(如果目标函数的代码能输出复数的输入)
  4. 大多数的方法用户可以修改参数。例如存储L-BFGS的修正数量,在纯牛顿方法中,海森矩阵非正定的修改选项,预处理的选择和Hession-free方法的Hessian-vector product 函数,更新方法选择,缩放比例,非线性共轭梯度法的预处理,在拟牛顿迭代中使用的海森近似的类型,线性搜索算法的参数,终止准则参数,等等。