正文
优化算法-BFGS
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
优化算法-BFGSBGFS是一种准牛顿算法, 所谓的"准"是指牛顿算法会使用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
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
