现在有很多开源的中文分词器库,如果你的项目要选择其一来实现中文分词功能,必然要先评测它们的分词效果。如何评测?下面详细叙述。
Algorithm
[原创]拟牛顿法/Quasi-Newton,DFP算法/Davidon-Fletcher-Powell,及BFGS算法/Broyden-Fletcher-Goldfarb-Shanno
在最优化领域,有几个你绝对不能忽略的关键词:拟牛顿、DFP、BFGS。名字很怪,但是非常著名。下面会依次地说明它们分别“是什么”,“有什么用” 以及 “怎么来的”。
但是在进入正文之前,还是要先提到一个概念上的区别,否则将影响大家的理解:其实DFP算法、BFGS算法都属于拟牛顿法,即,DFP、BFGS都分别是一种拟牛顿法。
[原创]最速下降法/steepest descent,牛顿法/newton,共轭方向法/conjugate direction,共轭梯度法/conjugate gradient 及其他
在最优化的领域中,这“法”那“法”无穷多,而且还“长得像”——名字相似的多,有时让人觉得很迷惑。
在自变量为一维的情况下,也就是自变量可以视为一个标量,此时,一个实数就可以代表它了,这个时候,如果要改变自变量的值,则其要么减小,要么增加,也就是“非左即右“,所以,说到“自变量在某个方向上移动”这个概念的时候,它并不是十分明显;而在自变量为n(n≥2)维的情况下,这个概念就有用了起来:假设自变量X为3维的,即每一个X是(x1, x2, x3)这样的一个点,其中x1,x2和x3分别是一个实数,即标量。那么,如果要改变X,即将一个点移动到另一个点,你怎么移动?可以选择的方法太多了,例如,我们可以令x1,x2不变,仅使x3改变,也可以令x1,x3不变,仅使x2改变,等等。这些做法也就使得我们有了”方向“的概念,因为在3维空间中,一个点移动到另一个点,并不是像一维情况下那样“非左即右”的,而是有“方向”的。在这样的情况下,找到一个合适的”方向“,使得从一个点移动到另一个点的时候,函数值的改变最符合我们预定的要求(例如,函数值要减小到什么程度),就变得十分有必要了。
[原创]Ridders求导算法
N年前,当我还是一个在校学生的时候,有一次到工厂里实习,看到某系统上运行的一个软件中显示的一条条曲线,以及其下的一些参数值,我问旁边开发那款软件的老师:某某值是怎么求出来的?老师说,是对曲线求导算出来的。当时我就心想,一个人开发出这款软件得综合多少个领域的知识才能做得到啊。从那时起,我的心中就埋下了一颗种子。时光匆匆,一眨眼就到了今天,因为学习其他算法的原因,涉及到了一些求导算法的编程,于是,本文必须得写。
求导算法应用广泛,例如,在LM算法中,需要对函数求导(但是,使用数值求导的方法来求导数值,会不会对LM算法的整个过程的效率造成较大影响,我不清楚,还没有试验),可以考虑使用数值求导算法来实现。
Brent's method
Brief introduction:
In numerical analysis, Brent's method is a complicated but popular root-finding algorithm combining the bisection method, the secant method and inverse quadratic interpolation. It has the reliability of bisection but it can be as quick as some of the less reliable methods.
在数值分析领域,Brent方法是一个复杂的、但是却很流行的寻根算法,它结合了二分法、割线法以及反向二次插值法的特点。它具有二分法的稳定性,但是它的速度却可与一些不太稳定的方法相比拟。
[原创]关于 最优化/Optimization 的一些概念解释
以下是我曾在学习“最优化”理论与实践中遇到的一些概念,我刚开始学的时候,有些东西看了很多遍都还觉得很别扭、晦涩难懂,在比较清楚地理解了之后,我打算把它们写下来,并试图以很通俗、但可能不十分严谨的方式解释、呈现出来,以使一部分正在这些概念中挣扎的人能有所解脱。
[原创]最小二乘的理论依据
在做数据建模或者曲线拟合的时候,我们通常会用到最小二乘法。
[原创] Powell共轭方向集方法(Powell's Conjugate Direction Method)的实现
实现Powell算法的基础之一:你需要至少先掌握一种一维极值搜索算法。比较流行的是Golden Ratio Search(黄金比例搜索法),Fibonacci Search(斐波纳契搜索法),等等。
[原创] LM(Levenberg-Marquard)算法的实现
LM算法,全称为Levenberg-Marquard算法,它可用于解决非线性最小二乘问题,多用于曲线拟合等场合。
LM算法的实现并不算难,它的关键是用模型函数 对待估参数向量 在其邻域内做线性近似,忽略掉二阶以上的导数项,从而转化为线性最小二乘问题,它具有收敛速度快等优点。LM算法属于一种“信赖域法”——所谓的信赖域法,此处稍微解释一下:在最优化算法中,都是要求一个函数的极小值,每一步迭代中,都要求目标函数值是下降的,而信赖域法,顾名思义,就是从初始点开始,先假设一个可以信赖的最大位移 ,然后在以当前点为中心,以 为半径的区域内,通过寻找目标函数的一个近似函数(二次的)的最优点,来求解得到真正的位移。在得到了位移之后,再计算目标函数值,如果其使目标函数值的下降满足了一定条件,那么就说明这个位移是可靠的,则继续按此规则迭代计算下去;如果其不能使目标函数值的下降满足一定的条件,则应减小信赖域的范围,再重新求解。
事实上,你从所有可以找到的资料里看到的LM算法的说明,都可以找到类似于“如果目标函数值增大,则调整某系数再继续求解;如果目标函数值减小,则调整某系数再继续求解”的迭代过程,这种过程与上面所说的信赖域法是非常相似的,所以说LM算法是一种信赖域法。