优化算法-BFGS

优化算法-BFGS

BGFS是一种准牛顿算法, 所谓的"准"是指牛顿算法会使用Hessian矩阵来进行优化, 但是直接计算Hessian矩阵比较麻烦, 所以很多算法会使用近似的Hessian, 这些算法就称作准牛顿算法(Quasi Newton Algorithm).

1. 牛顿算法(Newton Algorithm)

牛顿算法考虑了函数的二阶单数, 是一种二阶优化方法, 并且是所有其他二阶优化方法的鼻祖. 作为对比, 梯度下降(Gradient Descent)只考虑了函数的一阶导数, 是一阶优化方法.

推导过程：

我们考虑函数的二阶泰勒展开式: fquad(θ)=fk+gTk(θ−θk)+12(θ−θk)THk(θ−θk), 其中θ为需要优化的参数, gk为∇f(θk)

上式可以重写作:

fquad(θ)=θTAθ+bTθ+c

其中

  式子-1

二次函数的最小值取为x=−b2a

所以式子-1在θ取以下值时达到最小

亦即Newton算法每次迭代时只需要对θk加上以下项

牛顿方法的步骤为

2. BFGS算法

Newton算法在计算时需要用到Hessian矩阵H, 计算Hessian矩阵非常费时, 所以研究者提出了很多使用方法来近似Hessian矩阵, 这些方法都称作准牛顿算法, BFGS就是其中的一种, 以其发明者Broyden, Fletcher, Goldfarb和Shanno命名.

BFGS算法使用以下方法来近似Hessian矩阵, Bk≈Hk:

初始时可以取B0=I

因为Hessian矩阵的大小为O(D2), 其中D为参数的个数, 所以有时Hessian矩阵会比较大, 可以使用L-BFGS(Limited-memory BFGS)算法来进行优化.

参考文献:

[1]. Machine Learning: A Probabilistic Perspective. p249-p252.

[2]. Wekipedia: L-BFGS

顺手的Linux发行版及其工具推荐

从Windows切换到Linux已经有半年多的时间了，简单给大家推荐一些个人感觉不错的软件，主要都是和开发相关的通用软件～～～

0.archlinux 

挑一个比较顺手的linux发行版当然是首要任务了，我的开发硬件平台是笔记本，所以我主要看重这几个方面（以我用过的ubuntu/debian/centos/fedora/opensuse/archlinux/gentoo为例）：

1.社区支持

　　其实，上面列举的几个linx distribution，社区支持都比较好，差别不是特别大，在国内都有一定基数的用户

　　ubuntu的中文社区应该是最好的（不过对于programmer或geek来说，英文真的不应该是问题）

　　debian，因为ubuntu基于debian，所以问题也很好解决，社区很强大

　　centos是rhel的源代码重编译的版本之一（rhel是Red Hat付费提供服务，centos则是纯社区支持），因为很多企业用的是centos，所以有问题很好解决，社区也很强大

　　fedora和opensuse用的不是很多，fedora在中国的用户基数也很大，fedora背后是Red Hat。opensuse的kde界面确实不错，suse的背后是Novell，两家都有企业版，都有认证

　　archlinux的社区很强大，aur很好用，问题也很好解决，wiki中英文都有，安装文档handbook都很方便

　　gentoo，最近一直在做测试，打算下一个可能是gentoo，社区依然很强大，google问题依然很好解决，wiki也很好用，handbook什么的都有

2.更新升级

　　分为两种，一种滚动升级，一种是版本升级，没有好坏之分，个人倾向于archlinux，服务器的话还是版本升级

　　1.滚动升级，就像是滚雪球，不断更新最新的包，没有固定的版本号。

　　(1)archlinux的更新速度超快，快赶上自己去github上clone下源代码自己编译了，我现在的内核已经是3.11.4，现在kernel.org上的stable就是3.11.4。据说不经常滚容易滚挂了，但我貌似还没有滚挂过。

　　　 archlinux的包管理器pacman用起来很方便，国内更新源的速度也很赞，pacman的具体使用就不介绍了，下同。

　　(2)gentoo的更新没有这么激进，社区还是很负责的，基本都是测试过才放进去，kernel到了3.10

　　　 gentoo的一个特点就是他的包管理器emerge，默认是down下来源代码在本机编译，再加上通过USE，可以最大化性能和极高的可选择余地。目前我还在测试中，不过要是本机性能不济的话，编译安装确实很慢。

　　2.版本升级，好比windows升级方式（xp 7 8）

　　(1)ubuntu每4月和10月的中下旬出来，分为两个版本，桌面版和服务器版，最新到13.04，LTS（长期支持版）最新是12.04.3（每半年小版本号更新一下）

　　　ubuntu和debian都用一个包管理器，就是apt-get，使用起来很方便，源的速度很快，适合新手

　　(2)debian一般来说每两年出一个版本，期间有小版本号的更新，最新版本是7.1(内核版本是3.2)，ubuntu是debian的unstable分支。

　　　软件包都比较旧，不过很稳定，源的速度很快

　　(3)centos一般来说每三年一个大版本，每六个月一个小版本，最新的是6.4（内核版本是2.6.32）

　　     yum包管理器也很好用，也很简单，个人感觉不及apt，源的速度很快

　　(4)fedora一般来说每半年一个版本，最新是18，用的不是太多，用的没有ubuntu顺手，但是用户也很多很多，源也很快

3.轻量级

　　判断轻量级的概念，一般来说就是预装的包的数量、可定制余地以及系统性能占用

　　简单一下，排个名，从快到慢，archlinux>gentoo>debian>centos>ubuntu≈fedora>opensuse

　　但是换句话说，每个发行版都安装成很轻量级的，因为都可以选择自己所要安装的包。

4.性能

　　差距不是很大，通常来说，内核越新，越轻量级，性能越快。

　　这里archlinux就比较突出，gentoo也不错，因为可以自定义编译

5.稳定性

　　排个名：centos>debian>archlinux>ubuntu

　　要检验稳定性，肯定是要有长时间使用过，才有发言权，其他发行版没有长时间的系统的使用过，所以就不列上了

　　debian很稳定，目前我的VPS上运行的就是Debian 7.1 x64，uptime最长到了30多天（不过被我手动重启了），不过debian 7在我的电脑上（t420）有个bug，就是gnome3经常假死，有时候死的很彻底，archlinux就没有这个问题（无论3.8  3.10）。

　　centos的某些驱动比debian上要稳定，默认debian只安装*软件。

　　ubuntu在我印象中，就是很不稳定～～～

6.其他

　　推荐路线ubuntu(fedora)->debian(centos)->archlinux->gentoo->lfs(额～～～)

　　再推荐一个很好用的PE盘（姑且这么称呼吧），就是GRML，是一个LIVE版的GRML（就是说可以在U盘或者光盘中运行的Linux），我用他替代了老毛桃（我目前所有的系统全部都是Linux，哪怕是移动硬盘的分区EXT4）～～～

　　BTW：FreeBSD作为服务器也是很不错的，正在测试（gentoo的Portal概念就来自freebsd）

7.总结一下

　　新手用ubuntu或fedora

　　熟练之后，想要稳定用debian或centos（貌似服务器上用更好），要更新速度，用archlinux或gentoo

1.zsh

　　首先是Shell，虽然bash很常见，但是这里推荐的是zsh，zsh兼容bash，zsh自动补全真的是太顺手了，无论是目录，pacman，kill，git下的命令都可以补全。

　　比如说我输入kill s后，再按tab就可以列出所有s开头的进程，不断按tab就可以直接在这些列出来的进程中直接选择，不用手动输入。

　　配置文件可以先用oh-my-zsh(详见github)。

　　可以先sudo pacman -S zsh 尝试一下，估计不到30分钟就chsh了

2.guake

　　很像tilda，只需要按下快捷键，就可以弹出全屏的Terminal，可以调节大小和透明度，不需要Alt+CTRL+FX了，支持多标签，archlinux的源里自带

　　稳定性比tilda要好不少

3.vim

　　神一样的编辑器，不多说了，本人采用了一年多，正式使用才俩月，可以先用大神的配置文件和插件，后期再慢慢修改。

4.tmux

　　可以将一个屏幕（一个Terminal）分割成几个Panel，在每个Panel中运行一个Terminal，极大的提高了屏幕利用率

　　比如说在上半屏幕vim，左下连着ssh，右下git push

　　也支持多标签，不过图形界面下，还是用guake的多标签比较顺手

5.virtualbox

　　虽然身边所有的设备都换成了Linux，但是有时候却不得不用Windows（双系统不太喜欢），这时候就要用到虚拟机了

　　个人比较崇拜VMware公司，但是vmware一是收费、二是有点慢（宿主计算机），但是性能真的很赞，特别是图形性能（虚拟机上的图形性能很赞）

　　virtualbox现在属于oracle，有OSE（开源版），优点：

　　1.用着还是很方便，界面简洁，配置简单，还有很方便的headless

　　2.免费开源

　　3.性能不错

　　缺点：

　　1.图形性能一般，开了2D 3D加速后，不能在虚拟机里面看百度影音～～～

　　2.图形界面中缺少某些功能，需要用vboxmanage，比如说压缩vdi文件，需要手动 vboxmanage modifyvdi compact XXX.vdi

　　3.oracle会不会把他给停了，就像opensolaris

6.sublime text

　　跟着从Windows带过来，很不错的软件，界面很不错，有众多的插件，作为在图形界面下的vim的替代吧（gvim个人感觉不太好用）

7.stardict

　　有时候看文档有什么不会的，可以直接取词，很方便，词典可以从网上下载

8.github

　　很赞～～～以下省略1000字

9.dropbox

　　国内的网盘虽然容量都很大，但是界面很乱，dropbox小清新很喜欢，并且手机/linux下都有客户端，速度也还是不错（10M网上传下载基本满速），只是容量略小(默认2G，最大19G)，但是存文档足够了 。

10.总结

　　archlinx + zsh + tmux + vim + stardict + github + dropbox + virtualbox，基本满足了在Linux开发的初级要求，vim还是有很大的研究空间的～～～

　　这篇文章只是自己的一些使用心得，有什么错误或者不同的看法，欢迎大家交流哈～～～如果有空的话，再介绍一下平时娱乐时候用的软件，或者一篇文章详细介绍上面的某一条。

 

 

分类: archlinux

 

分类: 机器学习

标签: 机器学习, 优化算法, BFGS, 牛顿方法, Newton