Shallow Thought ←

不动点迭代和优化方法

机器学习中的很多问题都可以形式化成目标函数的最优化求解问题。梯度下降法和牛顿法是用来求解无约束优化的基本方法,本文尝试以不动点迭代的角度来探讨一下这两种方法。

Fixed Point Iteration

在数值分析中,函数的不动点是指被这个函数映射到其自身的一个点。也就是说,$c$是函数$f(x)$的不动点,当且仅当$f(c)=c$。有些函数可能不止一个不动点,如$f(x)=\frac{4}{x}$的不动点是$\pm2$;有些函数则没有不动点,如$f(x)=x+1$。

对于简单的函数,可以直接解方程$f(x)=x$来求解不动点。对于复杂的函数,方程的求解则是个很困难的过程,能不能用数值方法来迭代逼近这个点呢?答案对于具有某些性质的函数是肯定的,有如下定理:

If a function $f$ defined on the real line with real values is Lipschitz continuous with Lipschitz constant $L<1$, then this function has precisely one fixed point, and the fixed-point iteration converges towards that fixed point for any initial guess $x_{0}$. 此定理可以推广到任意的度量空间,只要满足映射是压缩映射,有兴趣的可以参看Banach fixed-point theorem

举个最简单的例子,对于单变量可导函数来说,只要导数绝对值在任意处小于1,那么总能通过迭代逼近这个不动点。注意上述定理只是充分条件,不一定必要。比如求平方根$\sqrt{a}$,可以随意选择一个正数$x_0$,然后迭代$\frac{1}{2}(x_0+\frac{a}{x_0})$来求解,显然迭代式的导数绝对值并非处处小于1。

Read On


Regularization on GBDT

之前一篇文章简单地讲了XGBoost的实现与普通GBDT实现的不同之处,本文尝试总结一下GBDT运用的正则化技巧。

Early Stopping

Early Stopping是机器学习迭代式训练模型中很常见的防止过拟合技巧,维基百科里如下描述:

In machine learning, early stopping is a form of regularization used to avoid overfitting when training a learner with an iterative method, such as gradient descent.

具体的做法是选择一部分样本作为验证集,在迭代拟合训练集的过程中,如果模型在验证集里错误率不再下降,就停止训练,也就是说控制迭代的轮数(树的个数)。

XGBoost Python关于early stopping的参数设置文档非常清晰,API如下:

# code snippets from xgboost python-package training.py
def train(..., evals=(), early_stopping_rounds=None)
    """Train a booster with given parameters.
    Parameters
    ----------
    early_stopping_rounds: int
        Activates early stopping. Validation error needs to decrease at least
        every <early_stopping_rounds> round(s) to continue training.
    """

Read On


近期好书推荐

推荐几本近期阅读的好书。

Fluent Python

Python进阶书,2015年8月份出版,在亚马逊,豆瓣上基本都是五星好评。从data model开篇,讲述如何让你的代码更pythonic。每章结尾会有一篇称为soapbox的短文,像博文一样发表自己对于Python和其他编程语言的评论,很多观点十分有趣。这本书让我找到了当年读《C专家编程》的感觉,绝对不容错过。 P.S. 此书的样例代码是Python3.4,这也让我下定决心迁移到Py3。

Read On


XGBOOST和GBDT的不同

知乎上有个人问xgboost与gbdt的不同,这里记录一下我的简单回复。首先xgboost是Gradient Boosting的一种高效系统实现,并不是一种单一算法。xgboost里面的基学习器除了用tree(gbtree),也可用线性分类器(gblinear),而GBDT则特指梯度提升决策树算法。xgboost相对于普通gbm的实现,可能具有以下的一些优势:

  1. 显式地将树模型的复杂度作为正则项加在优化目标
  2. 公式推导里用到了二阶导数信息,而普通的GBDT只用到一阶
  3. 允许使用column(feature) sampling来防止过拟合,借鉴了Random Forest的思想,sklearn里的gbm好像也有类似实现
  4. 实现了一种分裂节点寻找的近似算法,用于加速和减小内存消耗
  5. 节点分裂算法能自动利用特征的稀疏性。
  6. data事先排好序并以block的形式存储,利于并行计算
  7. cache-aware, out-of-core computation
  8. 支持分布式计算可以运行在MPI,YARN上,得益于底层支持容错的分布式通信框架rabit

Read On


MATLAB里的bsxfun, cellfun和arrayfun

MATLAB作为科学计算领域里比较流行的一门语言,天然地和向量化思维联系在一起。这篇文章简单讲一下bsxfun,cellfun和arrayfun。

1. bsxfun

MATLAB的官方doc里如下描述:

bsxfun: apply element-by-element binary operation to two arrays with singleton expansion enabled.
C = bsxfun(fun,A,B)

Singleton expansion的意思是若A或B的某一个维度的size为1,那么就沿着这一维度复制,使它和另一个矩阵的对应维度size一样。和repmat不同,bsxfun的复制是虚拟的;且是多线程实现,所以速度很快。另一方面,使用bsxfun的代码更简洁美观,符合MATLAB的表达方式。

下面的例子是对数据进行中心化处理

% each row in A is an example.
A = [1 2 10; 1 4 20;1 6 15] ;
C = bsxfun(@minus, A, mean(A))

更厉害的的是用bsxfun计算距离矩阵

Read On