Go语言——切片和数组的区别

Posted on 2018-05-12

关于切片与数组的区别，这里给出定义和传值等使用上的区别，最后给出总结

数组定义

申明类型定义

1 2	var arr [2]byte arr[0] = 10

直接赋值定义

1	arr := [2]byte{1,2}

切片定义

申明类型定义

1	var sli []byte

直接赋值定义

1	sli := make([]byte, 5)

作为参数传入

package main

import "fmt"

func changeSlicePoint(p *[]byte){
	(*p)[0] = 100
}

func changeSlice(a []byte){
	a[4] = 100
}

func changeArrayPoint(p *[5]byte){
	(*p)[0] = 100
}

func changeArray(a [5]byte){
	a[4] = 100
}

func main()  {
	array := [5]byte{1,2,3,4,5}
	var sli1 []byte
	sli1 = make([]byte, 5)
	slice := []byte{1,2,3,4,5}

	changeSlicePoint(&sli1)
	changeSlice(sli1)
	changeArray(array)
	changeArrayPoint(&array)
	changeSlicePoint(&slice)
	changeSlice(slice)

	fmt.Printf("slice[0]: %d\nslice[4]: %d\n", slice[0], slice[4])
	fmt.Printf("sli1[0]: %d\nsli1[4]: %d\n", sli1[0], sli1[4])
	fmt.Printf("array[0]: %d\narray[4]: %d\n", array[0], array[4])
}


//output: 
//slice[0]: 100
//slice[4]: 100
//sli1[0]: 100
//sli1[4]: 100
//array[0]: 100
//array[4]: 5
//

总结

切片传入时是按照引用传递的，加上指针甚至可以修改引用（内存地址）本身

比如下面的代码会是的传入的引用重新指向nil指针：

func changeSlicePoint(p *[]byte){
(*p)[0] = 100
*p = nil
}

数组的传递是按值传递的，使用了指针可实现传入地址，从而实现对数组的修改

Hello World

Posted on 2018-05-10

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment

Hexo——命令总结

Posted on 2018-05-10

Hexo命令归纳整理

init

hexo init [folder]

# 在cmd命令下，cd到你所需要建立博客的文件夹，执行此命令，其中folder为可选指令，若不写，则默认当前目录。

hexo new

hexo new [layout] \<title\>

#layout为可选项，默认使用_config.yml中的default_layout。新建文章的指令

generate

hexo generate

# 生成静态文件，

# 可选参数：

-d ,–deploy 文件生成后立即部署网站

-w , –watch 件事文件变动

deploy

hexo deploy

# 发布到网站，这里就是发布到 _config.yml中deploy中设置的网址上。

# 参数

-g , –generate 部署前生成静态文件

npm install

每一个rn项目都有一个package.json文件，里面有很多组件信息，使用npm install将按照package.json安装所需要的组件放在生成的node_modules文件夹中，rn项目下的每一个文件中都可以通过import引入node_modules的组件来加以使用

hexo clean

hexo clean 清除缓存文件(db.json)和已生成的静态文件(public)，通常更换主题后，无效时，可以运行此命令。

hexo server

hexo server

# 启动server，就可以在本地预览效果。

#参数，默认网址http://localhost:4000/

-p , –port 重设端口

-s , –static 只是用静态文件

-l , –log 启动日志记录，使用覆盖记录格式

-i , –ip 重新制定服务器ip

Hexo——项目文件目录说明

Posted on 2018-05-10

Hexo 项目文件目录说明归纳整理

./package.json

这个文件指定了hexo框架的参数和依赖插件

./package-lock.json

package.json里面定义的是版本范围（比如 1.0.0），具体跑npm install的时候安的什么版本，要解析后才能决定，这里面定义的依赖关系树，可以称之为逻辑树（logical tree）。

node_modules文件夹下才是npm实际安装的确定版本的东西，这里面的文件夹结构我们可以称之为物理树（physical tree）。安装过程中有一些去重算法，所以你会发现逻辑树结构和物理树结构不完全一样。

package-lock.json可以理解成对结合了逻辑树和物理树的一个快照（snapshot），里面有明确的各依赖版本号，实际安装的结构，也有逻辑树的结构。其最大的好处就是能获得可重复的构建（repeatable build），当你在CI（持续集成）上重复build的时候，得到的artifact是一样的，因为依赖的版本都被锁住了。在npm5以后，其内容和npm-shrinkwrap.json一模一样。

./scaffolds

scaffolds是“脚手架、骨架”的意思，当你新建一篇文章（hexo new ‘title’）的时候，hexo是根据这个目录下的文件进行构建的。scaffolds模版文件夹。Hexo的模板是指在新建的markdown文件中默认填充的内容。例如，如果您修改scaffold/post.md中的Front-matter内容，那么每次新建一篇文章时都会包含这个修改。

./source

source 资源文件夹是存放用户资源的地方。除 _posts 文件夹之外，开头命名为 _ (下划线)的文件 / 文件夹和隐藏的文件将会被忽略。Markdown 和 HTML 文件会被解析并放到 public 文件夹，而其他文件会被拷贝过去。

./source/_posts

需要新建的博文都放在 _posts 目录下。_posts 目录下是一个个 markdown 文件。你应该可以看到一个 hello-world.md 的文件，文章就在这个文件中编辑。_posts 目录下的md文件，会被编译成html文件，放到 public （此文件现在应该没有，因为你还没有编译过）文件夹下。

./themes

网站主题目录，hexo有非常好的主题拓展，支持的主题也很丰富。该目录下，每一个子目录就是一个主题。
More info: hexo主题

./_config.yml

_config.yml 采用YAML语法格式，具体语法在这里。
具体配置可以参考官方文档，_config.yml 文件中的内容，并对主要参数做简单的介绍

./public

public 生成的网站文件，发布的站点文件。

./tag

tag 标签文件夹

ML——LightGBM概述

Posted on 2018-04-28

本文介绍LightGBM的一些特性和并行实现方法

参考博客: https://www.cnblogs.com/ldt-/p/10206356.html

LightGBM vs XGBoost

树结点切分方式不同:
- XGBoost树节点切分是 Level-wise
- LightGBM树节点切分是 Leaf-wise
LightGBM直接支持类别特征，对类别特征不必进行 One-Hot 处理
实现方面:
- 直方图算法(近似切分算法)最初由LightGBM提出,后来的XGBoost算法也实现了直方图算法
XGBoost的近似搜索算法和LightGBM的直方图算法不同
- XGBoost的近似搜索算法是保存所有样本的二阶梯度,用分位数确定划分方法,他的分割点是可以直接通过计算总的样本梯度和和分位数点得到的.
  * LightGBM算法是将所有样本放进对应的桶中,并以当前桶作为划分点,计算左右桶的最大增益,它的最优点是遍历所有的桶才能得到的.
LightGBM 通信优化比 XGBoost 做得好
- 这里有亲身体验: XGBoost使用多个处理器时,有时候处理器数量增加训练速度不增加,甚至反而变慢,xgboost.XGBClassifier
LightGBM 使用了 GOSS(Gradient-based One-Side Sampling) 来做采样算法
- GOSS 是通过区分不同梯度的实例，保留较大梯度实例同时对较小梯度随机采样的方式减少计算量，从而达到提升效率的目的
- GOSS 算法流程:
  - 根据样本的梯度将样本降序排序
  - 保留前 $a \ (0 < a < 1)$ 比例大小的数据样本，作为数据子集 $Z_1$, 也就是保留 $a * len(all\_samples)$ 的数据样本
  - 对于剩下的数据的样本，随机采样获得大小为 $b \ (0 < b < 1)$ 的数据子集 $Z_2$, 也就是采样 $b * len(all\_samples)$ 的数据样本
  - 计算信息增益时对采样的 $Z_2$ 样本的梯度数据乘以 $(1-a)/b$（目的是不改变原数据的分布）
- GOSS的思想是,梯度大的实例正常使用,梯度小的实例就通过采样实现部分拟合总体的方法(拟合时不改变原来的分布,除以采样率就行了)
LightGBM 使用了 EFB (Exclusive Feature Bundling)
- EFB 通过特征捆绑的方式减少特征维度(其实是降维技术)的方式,提升计算效率
- 通常被捆绑的特征都是互斥的(一个特征值为0,一个特征值不为0), 这样两个特征捆绑起来也不会造成信息丢失
- 当两个特征不是完全互斥时,可以用一个指标对特征不互斥程度进行评估,称为冲突比率
- 冲突比率较小时,我们可以将他们捆绑而不太影响训练结果
- EFB 算法流程:
  - 将特征按照非零值的个数进行排序
  - 计算不同特征之间的冲突比率
  - 遍历每个特征并尝试合并特征，使冲突比率最小化
LightGBM 的内存优化
- XGBoost 中需要对每个特征进行预排序(注意:这里不能在算是XGBoost的缺点了,后来的XGBoost也实现了这个直方图算法,不需要预排序了)
- LightGBM使用直方图算法替代了预排序

LightGBM的优点

相对XGBoost:
- 速度快 (GOSS, EFB, Histogram等)
- 内存少 (XGBoost中排序)
- 精度高(效果不明显, 与XGBoost相当, 本人测试, 实际使用中有时候不如XGBoost, 可能是参数调节的问题)

缺点

虽然官方一再强调LightGBM的精度不比XGBoost低,而且可能超过XGBoost,但是实践中, LightGBM除了比XGBoost快以外, 精度方面没什么优势, 甚至精度还不如XGBoost(注意: 也可能是我调参技术不行)
- 问题: 为什么某些数据集上出现LightGBM比XGBoost精度差的情况?
- 回答: (个人理解)因为GOSS和EFB会带来一定的精度损失

总结

LightGBM = XGBoost + Histogram + GOSS + EFB
- XGBoost: 不同于XGBoost的, 树节点切分不同, LightGBM使用了 Leaf-wise 的生长策略
- Histogram:
  - Histogram方法牺牲了一定的精度,但是作者强调了在实验中精度降低并不多
  - 开始的XGBoost使用的是预先排序的方式, 后来在 XGBoost 中也实现了Histogram
  - LightGBM 对 Histogram 算法进一步加速
  - 一个叶子节点的Histogram可以直接由父节点的Histogram和兄弟节点的Histogram做差得到, 一般情况下，构造Histogram需要遍历该叶子上的所有数据，通过该方法，只需要遍历Histogram的k个捅, 速度提升了一倍
- GOSS: 对于梯度小的样本, 使用采样部分代替总体的方法省时间
- EFB: 互斥特征捆绑,提升计算效率
LightGBM 真正做到了把并行做到极致
- 特征并行: 在不同的机器在不同的特征集合上分别寻找最优的分割点, 然后再机器间同步最优的分割点.
- 数据并行: 让不同的机器先在本地构造直方图, 然后进行全局的合并,然后在合并的直方图上寻找最优的分割点.
LightGBM 支持类别特征
- 无需将类别特征 One-Hot
问题: 为什么XGBoost也使用了直方图,但是速度依然比较慢?
* 直方图算法的实现有两种:
- 1. 全局构造,在树的构造过程中只建立一次直方图, 每次分裂都从缓存的直方图中寻找分裂点
- 1. 局部构造, 每次树分裂到一层的时候就建立一次直方图
- XGBoost使用的是局部构造的方式, 所以速度会较慢

ML——LR-逻辑回归

Posted on 2018-04-20

手动推导流程

假设有m样本:$X = (x_{1}, x_{2}, x_{3},\dots x_{m})$
- 样本点为: $((x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}),\dots (x_{m}, y_{m}))$
假设$w, \theta, x_{i}$等所有向量都为列向量

确定分类决策函数

线性回归模型
$$f(x) = w^{T}x + b$$
令
$$
\begin{align}
\theta &= (w; b) \\
x_{i} &= (x_{i}; 1)
\end{align}
$$
有
$$f(x) = \theta^{T} x$$
逻辑回归决策函数在线性回归模型上加一个sigmoid函数
$$
\begin{align}
h_{\theta}(x) &= sigmoid(f(x)) \\
&= \frac{1}{1+e^{-f(x)}} \\
&= \frac{1}{1+e^{-\theta^{T} x}} \\
\end{align}
$$
即
$$
\begin{align}
p(y=1|x) &= h_{\theta}(x) = \frac{1}{1+e^{-\theta^{T} x}} = \frac{e^{\theta^{T} x}}{1+e^{\theta^{T} x}}\\
p(y=0|x) &= 1-h_{\theta}(x) = \frac{e^{-\theta^{T} x}}{1+e^{-\theta^{T} x}} = \frac{1}{1+e^{\theta^{T} x}} \\
\end{align}
$$
对数几率(log odds, 也称为logit)定义为: $ln \frac{p}{1-p}$ ,在LR中有:
$$
\begin{align}
ln\frac{h_{\theta}(x)}{1-h_{\theta}(x)} = \theta^T x
\end{align}
$$
分类超平面不确定,与最终的阈值有关,$\alpha$的值与最终阈值相关
$$w^{\star}x + b^{\star} = \alpha$$
- 分类超平面由$(w, b)$和阈值唯一确定,(注意: SVM的分类超平面由$(w, b)$唯一确定)
- 这一点和SVM不同,SVM的分类超平面是确定的,详情参看ML——SVM-支持向量机

确定优化目标

LR中使用极大似然法
$$
\begin{align}
L(\theta) &= p(Y|X;\theta) \\
&= \prod_{i=1}^{m}p(y_{i}|x_{i}; \theta) \\
&= \prod_{i=1}^{m}(p(y_{i} = 1|x_{i};\theta))^{y_{i}}(p(y_{i} = 0|x_{i};\theta))^{1-y_{i}}
\end{align}
$$
上面的式子不易求导优化,我们使用与上面的式子单调性和最优点等价的对数似然函数为
$$
\begin{align}
LL(\theta) &= log L(\theta) \\
&= log \prod_{i=1}^{m}(p(y_{i} = 1|x_{i};\theta))^{y_{i}}(p(y_{i} = 0|x_{i};\theta))^{1-y_{i}} \\
&= \sum_{i=1}^{m}\left (y_{i}log(p(y_{i} = 1|x_{i};\theta)) + (1-y_{i})log(p(y_{i} = 0|x_{i};\theta)) \right ) \\
&= \sum_{i=1}^{m}\left (y_{i}log\frac{p(y_{i} = 1|x_{i};\theta)}{p(y_{i} = 0|x_{i};\theta)} + log(p(y_{i} = 0|x_{i};\theta))\right ) \\
\end{align}
$$
由前面的推导有
$$
\begin{align}
log \frac{p(y_{i} = 1|x_{i};\theta)}{p(y_{i} = 0|x_{i};\theta)} = log\frac{\frac{e^{\theta^{T} x}}{1+e^{\theta^{T} x}}}{\frac{1}{1+e^{\theta^{T} x}}} = log e^{\theta^{T} x} = \theta^{T}x\\
\end{align}
$$
$$log(p(y_{i} = 0|x_{i};\theta)) = log(\frac{1}{1+e^{\theta^{T} x}}) = -log(1+e^{\theta^{T} x})$$
故而有
$$
\begin{align}
LL(\theta) &= \sum_{i=1}^{m}\left (y_{i}log\frac{p(y_{i} = 1|x_{i};\theta)}{p(y_{i} = 0|x_{i};\theta)} + log(p(y_{i} = 0|x_{i};\theta))\right )\\
&= \sum_{i=1}^{m}\left ( y_{i}\theta^{T}x - log(1+e^{\theta^{T}x}) \right)
\end{align}
$$

损失函数

最大化似然函数等价于最小化似然函数的负数
LR中使用极大似然法,所以对应的损失函数自然为对数似然损失函数
$$loss(\theta) = -LL(\theta) = \sum_{i=1}^{m}\left (- y_{i}\theta^{T}x + log(1+e^{\theta^{T}x}) \right)$$

梯度下降法优化

注意: 这里优化目标也可以用牛顿法

目标,求一个$\theta^{\star}$满足似然函数最大化或者损失函数最小化
$$\theta^{\star} = \arg\max_{\theta} LL(\theta) = \arg\min_{\theta} -LL(\theta) = \arg\min_{\theta} loss(\theta)$$
对数似然函数对参数$\theta$求导有
$$
\begin{align}
\frac{\partial loss(\theta)}{\partial\theta} &= \sum_{i=1}^{m}\left ( -y_{i}x_{i} + \frac{x_{i}e^{\theta^{T}x}}{1+e^{\theta^{T}}x}\right ) \\
&= \sum_{i=1}^{m}x_{i}\left ( -y_{i} + \frac{e^{\theta^{T}x}}{1+e^{\theta^{T}}x}\right ) \\
&= \sum_{i=1}^{m}x_{i}\left ( -y_{i} + h_{\theta}(x_{i})\right ) \\
\end{align}
$$
LR模型的梯度下降参数迭代公式
$$
\begin{align}
\theta^{t+1} &= \theta^{t} - \alpha\sum_{i=1}^{m}x_{i}\left ( -y_{i} + h_{\theta^{t}}(x_{i})\right ) \\
&= \theta^{t} + \alpha\sum_{i=1}^{m}x_{i}\left ( y_{i} - h_{\theta^{t}}(x_{i})\right )
\end{align}
$$
- 其中$\alpha$为步长
线性回归和LR模型的梯度下降法参数迭代公式表达式看似相同,但是不同的模型对应的$h_{\theta}$函数并不相同

面试总结

参考:https://www.cnblogs.com/ModifyRong/p/7739955.html

LR中使用极大似然法,所以对应的损失函数自然为对数似然损失函数(对数损失函数)
- 对数似然损失函数定义为:
  $$Loss(\theta) = -P(Y|X; \theta)$$
- <<统计学习方法>>P213中定义LR的损失函数为逻辑斯蒂损失函数,在LR模型和最大熵模型中,逻辑斯蒂损失函数本质上与对数似然损失函数等价,可推导得到
一句话概括逻辑回归:
- 逻辑回归是假设数据服从伯努利分布,通过极大似然函数的方法,运用梯度下降法或者牛顿法来求解参数,来达到将数据二分类的目的
- 逻辑回归的假设: 数据服从伯努利分布, $p(y=1|x) = 1-p(y=0|x)$
- 逻辑回归的损失函数: 对数似然损失函数(交叉熵损失函数), 也就是对数似然函数的负数
- 逻辑回归的求解方法: 梯度下降法或牛顿法
- 逻辑回归的目的: 将数据二分类
- 逻辑回归如何分类: 预测结果是连续的[0-1]的数,我们一般选择0.5作为阈值来分类,但是这个值可能是可以变化的,因为损失函数最小并不意味着0.5时分类精度最高
为什么要用极大似然法?等价于为什么要用对数似然损失函数作为损失函数?
- 损失函数一般有平方损失函数,对数损失函数,合页损失函数,绝对值损失函数等,极大似然函数取对数后等同于对数损失函数,在逻辑回归这个模型中,推导可以得到,对数损失函数训练求解参数的迭代函数只与$x_{i}, y_{i}$相关,与sigmoid函数的梯度等无关.这样的参数更新自始至终都比较稳定
- 为什么不选平方损失函数的呢？其一是因为如果你使用平方损失函数,你会发现梯度更新的速度和sigmod函数本身的梯度是很相关的,sigmod函数在它在定义域内的梯度都不大于0.25, 这样训练会非常的慢
逻辑回归中,如果某些特征高度相关,甚至某些特征完全相同,会造成什么影响?
- 损失函数收敛后,没有影响,因为特征的相关性并不影响分类器效果,重复特征会分化特征的权重(10个重复特征和单个特征训练结果差别在于前者每个特征的权重是后者的十分之一),本质上最终结果不变的
- 但是训练时由于特征重复,参数增多,模型复杂度增加,训练时长,内存等都会增加
为什么需要去掉高度相关的特征?
- 去掉高度相关的特征使得模型可解释性更好
- 提高训练时间,节约内存,减少参数数量
- 特征的提取本身也需要时间,实际工程项目中可以少提取一个特征往往能节约很多时间
logistic与logit的区别?
- logit: 又名 log adds , 指的是”对数几率”, 定义为$ln\frac{p}{1-p}$
- logistic: 又叫Sigmoid函数, 指的是”对数几率函数”, 本质上是一种”Sigmoid”函数, 定义为 $f(x) = \frac{1}{1+e^{-x}}$
简单介绍LR模型的优缺点:
- 优点:
  - 模型简单,可解释性好,(如果对数据特征进行了归一化处理的话)可以从特征的权重看到不同特征对最终结果的影响
  - 模型效果往往不错(特征工程做得好的话)
  - 训练速度快, 成熟的SGD优化方法(SGD可以分布式)等
  - 内存占用小
  - 输出结果可以作为概率值,然后可以对阈值根据实际进行划分,不一定是确定的0.5,只是一般选择0.5而已
- 缺点:
  - 难以处理非线性数据,本质上是线性分类面
  - 难以处理数据不平衡问题, 这里如果正例远远多于负例,那么全都预测为正例,整体损失函数也不会太大
  - LR本身无法筛选特征,有时候会用GBDT和XGBoost来筛选特征,然后再用LR模型
扩展:逻辑回归可像SVM一样引入核函数处理非线性分类问题吗?
- 一般来说不可以
- [存疑]理论上通过对原始样本非线性映射,似乎也可以,如果将$f(x) = \theta^{T}x$中的$f(x)$看做$\theta$看做变量,然后类比SVM的核函数,定义一个关于$x_{i}$的非线性映射
  - 这里$x_{i}$表示第$i$个样本, 用$x_{i}^{j}$表示第$i$个样本的第$j$个维度
    $$x_{i}^{j} = \phi_{j}(x_{i}^{j})$$
  - 基于上述非线性映射函数的定义,我们对每个样本都进行线性映射,每个维度用不同的映射函数(不同样本相同维度映射函数相同)
  - 这里的非线性映射与SVM的核函数不同,SVM不使用核函数的话,也可以通过相同的非线性映射的方式实现非线性分类
  - 使用核技巧后的LR模型将变得很慢,SVM与kernels是相配的,而LR与kernels会十分慢(来源SVM核技巧)

ML——XGBoost-vs-传统GBDT

Posted on 2018-04-18

本文主要介绍XGBoost和其他传统GBDT的比较的优劣
XGBoost又叫(Newton Boosting Tree)

GBDT推导: ML——GBDT-梯度提升树-推导过程
XGBoost推导: ML——XGBoost-推导过程

XGBoost的优点

参考博客: https://www.cnblogs.com/massquantity/p/9794480.html

XGBoost损失函数是二阶泰勒展开(与牛顿法对应),GBDT是一阶泰勒展开(与梯度下降法对应)
- 传统 GBDT 在优化时只用到一阶导数信息, 所以传统GBDT也叫 (Gradient Boosting)
- XGBoost 则对目标函数进行了二阶泰勒展开，同时用到了一阶和二阶导数, 所以XGBoost又叫(Newton Boosting Tree)
XGBoost加了正则项,普通的GBDT没有,所以XGBoost学出来的模型更简单,能防止过拟合,提高模型的泛化性能
XGBoost Shrinkage(缩减)
- 每次进行完一次迭代后,将叶子节点的权重乘以该系数(一般叫做eta$\eta$)
- 可以理解为这里Shrinkage是将学习速率调小,从而需要的迭代次数增多
- 减小学习率实际上是减弱了每棵树对整体的影响,从而让后面的树有更多的学习空间
- 下面的表述还有待确定:
  - 进一步惩罚决策树叶节点的值(惩罚的意思是叶节点越大,惩罚越多,损失函数越大)
  - 对叶节点的惩罚本身可以理解为一个正则化
结点分裂的增益计算公式不同
- 传统 GBDT 一般采用的是最小二乘法作为内部分裂的增益计算指标(因为用的都是回归树)
  - 注意: 这里论文中描述的最小绝对偏差回归(LAD)是第一步损失函数的定义,不是这一步中的信息增益计算
  - 查看源码: sklearn.ensemble.GradientBoostingClassifier在分裂结点时可以选择三种方式:
    - friedman_mse(默认), mean squared error with improvement score by Friedman
    - mse: mean squared error
    - mae: mean absolute error
- 而 XGBoost 使用的是经过优化推导后的式子
  $$
  \begin{align}
  Gain = \frac{G_L^2}{H_L+ \lambda} + \frac{G_R^2}{H_R+ \lambda} - \frac{(G_L + G_R)^2}{H_L+ H_R + \lambda} - \gamma
  \end{align}
  $$
  - 注意: XGBoost中的信息增益计算形式固定为上面的计算方式,但是具体的值与损失函数的定义相关(因为 $g_i$ 和 $h_i$ 的是损失函数的一阶和二阶梯度)

XGBoost支持自定义的损失函数,支持一阶和二阶可导就行

注意,这里的损失函数指的是 $l(y_i,\hat{y}_i)$, 单个样本预测值与目标值的差异, 也就是单个样本的损失函数
从ML——XGBoost-推导过程中可知:
- $g_i = l’(y_i,\hat{y}_i^{t-1})$ 为 $l(y_i,\hat{y}_i)$ 对 $\hat{y}_i$ 的一阶导数在 $\hat{y}_i = \hat{y}_i^{t-1}$ 处的值
- $h_i = l’’(y_i,\hat{y}_i^{t-1})$ 是 $l(y_i,\hat{y}_i)$ 对 $\hat{y}_i$ 的二阶导数在 $\hat{y}_i = \hat{y}_i^{t-1}$ 处的值
XGBoost中只要损失函数二次可微分即可得到 $g_i$ 和 $h_i$
- $g_i$ 和 $h_i$ 本身与损失函数的定义形式无关, 只要求损失函数二阶可微分即可
只要有了 $g_i$ 和 $h_i$ 我们即可
- 根据预先推导的叶子节点分数表达式 $w_j^{\star} = -\frac{G_j}{H_j+\lambda}$ 求得叶子结点的分数
- 根据预先推导的信息增益公式 $Gain = \frac{G_L^2}{H_L+ \lambda} + \frac{G_R^2}{H_R+ \lambda} - \frac{(G_L + G_R)^2}{H_L+ H_R + \lambda} - \gamma$ 确定分裂特征和分裂点

GBDT 损失函数关系一般选择最小二乘回归或者最小绝对偏差回归

最小方差回归: (Least-Squares Regression, LSR)
$$\begin{align} L(y,F(x)) = \frac{1}{2}(y-F(x))^{2} \end{align}$$
最小绝对偏差回归: (Least Absolute Deviation Regression, LAD)
$$\begin{align} L(y,F(x)) = |y-F(x)| \end{align}$$

查看源码: sklearn.ensemble.GradientBoostingClassifier的损失函数是定义好的, 不能自己定义, 详细如下源码

LOSS_FUNCTIONS = {'ls': LeastSquaresError,
                  'lad': LeastAbsoluteError,
                  'huber': HuberLossFunction,
                  'quantile': QuantileLossFunction,
                  'deviance': None,    # for both, multinomial and binomial
                  'exponential': ExponentialLoss,
                  }


_SUPPORTED_LOSS = ('deviance', 'exponential')
....

if (self.loss not in self._SUPPORTED_LOSS
                or self.loss not in LOSS_FUNCTIONS):
            raise ValueError("Loss '{0:s}' not supported. ".format(self.loss))

XGBoost 借鉴了随机森林的做法，支持列采样，不仅能降低过拟合，还能减少计算量，这也是 XGBoost 异于传统 GBDT 的一个特性
- 列采样: 这借鉴于随机森林中的做法,每棵树不使用所有特征,而是部分特征参与训练
- 可以减少计算量,同时还能降低过拟合,简直优秀
XGBoost 有缺失值自动处理, 在计算分裂增益时不会考虑带有缺失值的样本，这样就减少了时间开销,在分裂点确定了之后，将带有缺失值的样本分别放在左子树和右子树，比较两者分裂增益，选择增益较大的那一边作为默认分裂方向
- 进一步理解稀疏数据的支持: [待更新]
并行化处理：由于 Boosting 本身的特性，传统 GBDT 无法像随机森林那样树与树之间的并行化
- XGBoost 的并行主要体现在特征粒度上，在对结点进行分裂时，由于已预先对特征排序并保存为block 结构，每个特征的增益计算就可以开多线程进行，极大提升了训练速度
剪枝策略不同
- 传统 GBDT 在损失不再减少时会停止分裂，这是一种预剪枝的贪心策略，容易欠拟合
- XGBoost采用的是后剪枝的策略，先分裂到指定的最大深度 (max_depth) 再进行剪枝
  - 而且和一般的后剪枝不同， XGBoost 的后剪枝是不需要验证集的[待更新:XGBoost剪枝的策略是怎样的?只依赖信息增益指标吗?]
  - 和博客作者指出的一样,我这里并不是”纯粹的”后剪枝,因为提前设定了最大深度
基分类器的选择不同:
- 传统GBDT中原始论文使用树回归,论文见Firedman 1999,后来作者提出可以使用逻辑回归,论文见Friedman 2000
- XGBoost后面的各种损失计算等都包含着树模型的复杂度,叶子节点分类等,所以是只能用CART,不能使用逻辑回归的
- (从函数空间定义和后面的公式推导来看)XGBoost中基函数只使用CART回归树，不能使用逻辑回归
- 但是事实上XGBoost的实现中是支持线性分类器作为基分类器的, 参数booster[default='gbtree'],可选为booster=gblinear
  - 使用线性分类器作为基分类器时, XGBoost相当于带有L1正则化和L2正则化的:
    - Logistic回归(分类问题)
    - 线性回归(回归问题)
分桶策略算法不同
- 传统的GBDT分桶时每个样本的权重都是相同的
- XGBoost中每个样本的权重为损失函数在该样本点的二阶导数(对不同的样本,计算得到的损失函数的二阶导数是不同的), 这里优点AdaBoost的思想,重点关注某些样本的感觉
- 这里影响的是划分点的位置(我们划分划分点[桶]时都是均匀划分样本到桶里面,当不同样本的权重不同时,每个桶里面的样本数量可能会不同)
- 下图是一个示例

XGBoost的缺点

注意这里是

空间消耗大
- 因为要在训练之前先对每个特征进行预排序并将结果存储起来，所以空间消耗较大
- GBDT无需预排序,但是每次重新排序很耗时间
速度慢
- 虽然XGBoost速度比传统 GBDT 快了不少, 但是不如 LightGBM 快, 且 LightGBM 占用内存更低

XGBoost为什么能够并行?

而GBDT是不能并行的

决策树最耗时间(包括GBDT)的步骤是对特征值的排序
- 用于确定最佳分割点
XGBoost训练前,预先对数据进行了排序,称为预排序
- 将预先排序的结果保存为block结构, 后面迭代的时候重复使用这个结构,从而实现一次排序,多次使用,大大减少计算量
这个结构减少计算量的同时还为并行化提供了可能([待更新]实际上不用预排序也能并行的吧?只是每次需要先使用一个单一线程排序,然后再多个线程并行?)
- 进行结点的分裂时,需要计算每个特征的增益,然后选择增益最大的那个特征分裂
- 这里我们可以同时使用多个线程计算不同特征的增益, 从而实现并行化
总结为三方面的并行, ([待更新]但是具体实现了哪些并行不确定)
- 同一层级的结点间每个结点的分裂可以并行
- 同一个结点内部不同特征增益的计算可以并行
- 同一个结点同一个特征的不同分裂点的增益计算可以并行

GBDT为什么不能自定义损失函数?

GBDT为什么不能像XGBoost一样自定义损失函数?

查看sklearn.ensemble.GradientBoostingClassifier的源码发现, 确实不支持自定义的损失函数
[待更新],因为涉及到后面的参数更新方式?

XGBoost如何使用自定义的损失函数?

模型直接调用fit函数无法传入自定义的损失函数, 需要在模型开始定义的时候传入或者使用xgb.train函数调用

使用方法1:

1
2
3

from xgboost import XGBClassifier

clf = XGBClassifier(objective=MyLossFunction)

使用方法2:

import xgboost as xgb
from xgboost import XGBClassifier

clf = XGBClassifier()
xgb.train(xgb_model=clf, obj=MyLossFunction)

Algorithm——AVL树和红黑树等各种树结构总结

Posted on 2018-04-09

各种树的介绍

树

一个根节点,每个结点可能有多个子节点

二叉树

一个根节点,或者为空
每个结点只有两个子节点

二叉搜索树

也叫二叉查找树

首先是一棵二叉树
左边孩子结点的值都小于当前结点
右边孩子结点的值都大于当前结点

缺点

极端情况下,树模型会退化成链表,查找变成了 O(n) 复杂度的

平衡二叉搜索树(AVL树)

也叫平衡二叉查找树

首先是一棵二叉搜索树
对每个结点而言, 左右孩子结点的深度差值不能超过1, 从而保证查找是 O(log n) 的
控制平衡方法: 参考链接AVL树详解
- 左-左型: 右旋
- 右-右型: 左旋
- 左-右型: 左旋 + 右旋
  - 第一步左旋后面部分,变成左-左型
  - 第二步使用右旋修正左-左型
- 右-左型: 右旋 + 左旋
  - 第一步右旋后面部分,变成右-右型
  - 第二步使用左旋修正右-右型

缺点

每棵树的左右子树高度最多差1这个要求太严了
几乎每次插入或者删除结点时都会造成规则破坏, 也就需要频繁的通过左旋或者右旋操作来修正
插入和删除太频繁的场景中不太适合使用AVL树, 性能会因为左右子树高度最多差1这个规则频繁被打破而降低

红黑树

首先是一棵二叉搜索树
每个结点不是黑色就是红色
根节点为黑色
每个叶子结点都为黑色的空结点(NULL)
- 注意: 叶子节点不存数据
任何相邻结点不同时为红色
- 注意,相邻结点可以为黑色,且可以某条路径上全是黑色
对每个结点而言,当前结点到叶子结点的所有路径包含相同的黑色结点数

优点

能保证查找时间复杂度是 O(log n) 的, 和AVL树差不多
- 证明: [待更新]
插入和删除操作中不会频繁破坏红黑树的规则

红黑树的应用

容器集合 HashMap, TreeMap等
- HashMap是链表 + 红黑树的实现, 当冲突时就需要使用红黑树加快检索
- HashMap中链表长度太短时使用链表, 太长时使用红黑树, 这个阈值一般设置为8

二三树

红黑树是二三树的一个变形,一般用红黑树就够了
[待更新]

B树

B树在大量的数据库和文件系统场景中都有使用
[待更新]

B+树

[待更新]

总结

可以说红黑树是一种不严格的平衡树

Python——heapq模块-最大堆最小堆

Posted on 2018-03-26

由于queue不是Python标准库,所以在LeetCode等OJ上面不能直接使用,我们可以选择heapq来使用最大最小堆

使用示例

堆排序示例

import heapq

nums = [2, 3, 5, 1, 54, 23, 132]
heap = []
for num in nums:
    heapq.heappush(heap, num)
# 等价于
heapq.heapify(nums)

# heap sort by incresing
print([heapq.heappop(heap) for _ in range(len(nums))])

加入元素
1
heapq.heappush(heap, num)
弹出元素
1
num = heapq.heappop(heap)

获取最大最小值

import heapq

nums = [1, 3, 4, 5, 2]
print(heapq.nlargest(3, nums))
print(heapq.nsmallest(3, nums))

#Output:
[5, 4, 3]
[1, 2, 3]

获取堆顶元素
1
top = nums[0]

最大堆的实现

由于Python heapq模块只实现了最小堆, 最大堆需要我们自己实现
一种简单可行的实现方案:
- 在加入和弹出时,把元素取反,从而实现最大堆

Python——为什么Python中没有自增++和自减--操作?

Posted on 2018-03-26

C++和Java等语言都有++和–操作,为什么以方便自居的Python却没有这种操作呢?

Python的数值对象

a = 1
b = 1
c = 1000123
d = 1000123

print id(a)
print id(b)
print id(c)
print id(d)

# output:
94181316498840
94181316498840
94181323965720
94181323965720

Python数值对象都是不可变类型,与String一样,所以不能修改对象内部数据
C++中的i++修改内存中对象本身,数值增加1,而Python不能修改对象本身
与C++中字符串可以修改,Python中不能修改是一个道理

Joe Zhou

世界上只有一种真正的英雄主义，那就是在认清生活真相之后依然热爱生活。 ——罗曼·罗兰

GitHub E-Mail