发表于 | 更新于 | 评论数：

本文主要节选自：http://izhaoyi.top/2017/09/23/sklearn-xgboost/

adaboost

adaboost 解决二分类问题$y\in{0,1}$，算法针对同一训练集训练出许多不同的弱分类器，将训练的分类器以某种方式组合起来，组合成一个强分类器。算法每次训练分类器时，会将前一个分类器分错的样本给与更大地权重，加强后的全体样本会用于下一次分类器的训练，每一轮加入一个新的弱分类器，知道达到某个预定的足够小的的错误率或达到预定的最大迭代次数。

参考资料

  1. https://www.cnblogs.com/en-heng/p/5974371.html

GBDT

GBDT 模型也是基于boosting的集成学习算法的变种，GB这边，就是Gradient Boost，通过在梯度上进行boost，每一次的计算是为了减少上一次的残差(residual)，在Gradient Boost中，每个新的模型的遍历是为了使得之前模型的残差往梯度方向减少。与传统Boost对错误的样本进行加权有着很大的区别。从公式上，就是下一个函数等于上一个函数+拟合了残差的函数（实际上这个残差函数会乘以一个乘数，是让目标函数最小化，这个乘数怎么来不作展开）。

XGBoost

XGBoost 是GBDT的一个变种，最大的区别是xgboost通过对目标函数做二阶泰勒展开，从而求出下一步要拟合的树的叶子节点权重（需要先确定树的结构），从而根据分裂损失选择合适的属性进行分裂。

一些特性

  1. GBDT无显式正则化，xgboost对每棵树的叶子节点个数和权重都做了惩罚，避免过拟合
  2. 类似于随机森林，XGBoost在构建树的过程中，加入了行采样与列采样，防止过拟合
  3. GBDT仅使用了目标函数一阶泰勒展开，而XGBoost使用了二阶的泰勒展开值
    1. 为什么二阶展开？加快收敛速度，另外有说本身模型训练的学习率shrinkage可以通过二阶导数做一个逼近，而原始的GBDT没有计算这个，所以一般是通过预设的超参数eta人为指定
  4. 分裂算法有两种，一种是精确的分裂，一种是近似分裂算法，精确分裂算法就是把每个属性的每个取值都当作一次阈值进行遍历，采用的决策树是CART。近似分裂算法是对每个属性的所有取值进行分桶，按照各个桶之间的值作为划分阈值，xgboost提出了一个特殊的分桶策略，一般的分桶策略是每个样本的权重都是相同的，但是xgboost使每个样本的权重为损失函数在该样本点的二阶导(泰勒展开不应该是损失函数关于模型的展开吗？为什么会有在该样本点的二阶导这种说法？ 因为模型是对所有样本点都通用的，把该样本输入到二阶导公式中就可以得到了)。
  5. xgboost加入了对缺失值的处理，xgboost分别将缺失样本放置到左子树和右子树，比较两者分裂增益，选择增益较大的那一边作为该样本的分裂方向。
  6. XGBoost通过预排序的方法来实现特征并行，提高模型训练效率
  7. xgboost 在实现时，需要将所有数据导入内存，做一次pre-sort（exact algorithm），这样在选择分裂节点时比较迅速。
阅读全文 »

发表于 | 更新于 | 评论数：

简介

深度优先与广度优先算法，从名字上便很好理解，以在二叉树结构中搜索某一值为例：

  1. 深度优先算法将从顶点V开始，沿着一个路径一直走到底（叶子节点），如果搜索到目标值则退出，否则返回上一个还有子节点未被搜索的节点继续搜索。
  2. 广度优先算法将从顶点V开始，依次访问当前节点未被访问过的子节点，再从子节出发，继续访问他们的子节点，直到所有节点被访问。（相当于树的层次遍历）
  3. 一般说来，能用DFS解决的问题都能用BFS解决。DFS通过递归实现，易于实现，DFS的常数时间开销会比较少，所以大多数情况下优先考虑DFS实现。然后就是，DFS容易栈溢出，而BFS可以自己控制队列的长度。

BFS

基本实现思想：

​ （1）顶点v入队列。

​ （2）当队列非空时则继续执行，否则算法结束。

​ （3）出队列取得队头顶点v；

​ （4）查找顶点v的所以子节点，并依次进入队列；

​ （5）转到步骤（2）。

树的层次遍历

  • 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
  • 这里使用2个数组保存节点，也可以使用queue这一数据结构。
阅读全文 »

发表于 | 更新于 | 评论数：

简介

循环神经网络（RNN）是一类用于处理序列数据的神经网络。每一个神经元除了当前信息的输入外还接受上一个隐藏神经元的输入（这就是所谓的记忆信息），保留序列依赖型。

基本原理

循环神经网络结构如下图，其中左边为循环图，右边为展开图。

对于如上图所示的RNN网络，每个时间步都有输出，并且隐藏单元之间有循环连接的网络结构。且有以下特性：

  1. 权值共享，图中的W全是相同的，U和V也一样。
  2. 每一个输入值都只与它本身的那条路线建立权连接，不会和别的神经元连接。

所谓循环，即指隐层h的循环连接，隐层神经元除了接受输入X，还需要接受上一个隐层的输出，因此对第t个隐层神经元有：
$$
h^{(t)}=f(h^{(t-1)},x;\theta)
$$

阅读全文 »

发表于 | 更新于 | 评论数：

本文为《推荐系统实战》（项亮编著）的阅读笔记。

推荐算法的评价指标

  1. 用户满意度：用户满意度没有办法离线计算，只能通过用户调查或者在线实验获得
  2. 预测准确度：
    1. 评分预测：一般通过均方根误差（RMSE）和平均绝对误差（MAE）计算。
    2. TopN 推荐：TopN 推荐的预测准确率一般通过准确率（ precision ） / 召回率（ recall ）度量。
  3. 覆盖率：覆盖率（ coverage ）描述一个推荐系统对物品长尾的发掘能力。也可使用基尼指数。
  4. 多样性：多样性描述了推荐列表中物品两两之间的不相似性。
  5. 新颖性：新颖的推荐是指给用户推荐那些他们以前没有听说过的物品。
  6. 惊喜度：目前并没有什么公认的惊喜度指标定义方式，这里只给出一种定性的度量方式。上面提到，
    令用户惊喜的推荐结果是和用户历史上喜欢的物品不相似，但用户却觉得满意的推荐。
  7. 信任度：用户对推荐系统的信任程度。（以让用户信任的方式推荐给用户就更能让用户产生购买欲）
  8. 实时性：推荐系统需要实时地更新推荐列表来满足用户新的行为变化；推荐系统需要能够将新加入系统的物品推荐给用户。
  9. 健壮性：任何一个能带来利益的算法系统都会被人攻击，这方面最典型的例子就是搜索引擎。健壮性可以通过以下方法提高：
    1. 设计推荐系统时尽量使用代价比较高的用户行为。如购买的代价远高于浏览
    2. 在使用数据前，进行攻击检测，从而对数据进行清理。
  10. 商业目标：网站评测推荐系统更加注重网站的商业目标是否达成，而商业目标和网站的盈利模式是息息相关的。

基于用户行为分析的推荐算法

基于用户行为分析的推荐算法是个性化推荐系统的重要算法，学术界一般将这种类型的算法称为协同过滤算法。顾名思义，协同过滤就是指用户可以齐心协力，通过不断地和网站互动，使自己的推荐列表能够不断过滤掉自己不感兴趣的物品，从而越来越满足自己的需求。

阅读全文 »

发表于 | 更新于 | 评论数：

简介

卷积神经网络（convolutional neural network，CNN），是一种专门用来处理具有类似网格结构的数据的神经网络。例如时间序列数据（可以认为是在时间轴上有规律地采样形成的一维网格）和图像数据（可以看作是二维的像素网格）。卷积网络在诸多应用领域都表现优异。“卷积神经网络”一词表明该网络使用了卷积（convolution）这种数学运算。卷积是一种特殊的线性运算。卷积网络是指那些至少在网络的一层中使用卷积运算来替代一般的矩阵乘法运算的神经网络。

卷积

卷积的定义如下：
$$
s(t)=(X*W)(t)
$$
上式中，$X$代表输入层输入，$W$叫做核函数（卷积核）。

对于二维（图像）情况，则有：
$$
s(i,j)=(X*W)(i,j) = \sum\limits_m \sum\limits_n x(i+m,j+n) w(m,n)
$$
上式与二维卷积的定义稍有不同，但许多机器学习的库都是使用此运算。

如下图为一个$3\times 4$的矩阵经过$2\times 2$的核映射得到$2\times 3$的输出矩阵，具体计算方式是在左上角初始化一个$2\times 2$的窗口，将窗口内元素分别与核函数对应位置相乘并求和，得到$aw+bx+cy+fz$（不是矩阵乘法哦！），再将窗口向右移动一位，再计算一次输出，依次类推。

在斯坦福大学的cs231n的课程上，有一个动态的例子，链接在这。 如下图，可以方便理解。

阅读全文 »

发表于 | 更新于 | 评论数：

阅读本文需要有一定的深度学习、神经网络基础

Keras 顺序 (Sequential) 模型

顺序模型是多个网络层的线性堆叠。 使用顺序模型的基本步骤如下：

  1. 初始化顺序模型并指定网络结构
  2. 编译：通过 compile 方法指定优化器、损失函数、评估标准
  3. 训练模型：使用 fit 函数

模型的初始化

建立方式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 样例1，使用层的列表初始化
from keras.models import Sequential
from keras.layers import Dense, Activation
model = Sequential([
    Dense(32, input_shape=(784,)),
    Activation('relu'),
    Dense(10),
    Activation('softmax'),
])
# 样例2，初始化后使用 .add() 方法将各层添加到模型中
model = Sequential()
model.add(Dense(32, input_dim=784))
model.add(Activation('relu'))

以上2种方式是等价的，以下将进行基本解释：

  1. model.add(Dense(32, input_dim=784))：Dense代表核心网络层（即普通的全连接层），其中32代表输出空间的维度，input_dim则表示输入数据的维度，类似的还有Conv2D（卷积层），MaxPooling2D （MaxPooling层），lstm（循环层）等。
  2. model.add(Activation('relu'))：Activation代表激活函数，可以配置单独的激活层（也可统称位隐层层）实现，也可在构造层对象时通过传递activation参数实现 ，常用的有tanh relu softmax等，一般深层模型使用多用relu ，对于多分类的情况，最后一层是softmax，二分类问题最后一层用sigmoid 。类似的隐藏层有Dropout层、池化层。
阅读全文 »

发表于 | 更新于 | 评论数：

之前的章节说到使用计算图可以很方便地计算偏导数，可大大加快神经网络逆传播地速度，tensorflow作为常用地深度学习库，本质上来说也是一个构建计算图与执行计算图的过程，下面我们将来学习在tensorflow中如何构建计算图。

图的节点

节点的初始化

计算图分为节点与操作2部分，其中节点对应为变量（如常量、矢量、矩阵、张量等），而在tensorflow中，我们可以通过 constant 或 variable 来建立节点。（注意：节点中并不保存数据，而是保存运算结果的引用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 节点的初始化
tf.constant(
    value,
    dtype=None,
    shape=None,
    name='Const',
    verify_shape=False
)
tf.Variable(
    initial_value=None,
    trainable=True,
    collections=None,
    validate_shape=True,
    caching_device=None,
    name=None,
    variable_def=None,
    dtype=None,
    expected_shape=None,
    import_scope=None,
    constraint=None
)

其中constant用于生成常数张量，而Variable生成变量张量，Variable()时需要指定初始值（也可指定初始形状），初始化后变量的形状和类型是固定的，如要更改形状，则必须使用assign操作且validate_shape=False，在运行其他操作前，必须对变量初始化，最简单的操作是使用tf.global_variables_initializer()进行全局初始化。

阅读全文 »

发表于 | 更新于 | 评论数：

星际穿越

题目描述

航天飞行器是一项复杂而又精密的仪器，飞行器的损耗主要集中在发射和降落的过程，科学家根据实验数据估计，如果在发射过程中，产生了 x 程度的损耗，那么在降落的过程中就会产生 x2 程度的损耗，如果飞船的总损耗超过了它的耐久度，飞行器就会爆炸坠毁。问一艘耐久度为 h 的飞行器，假设在飞行过程中不产生损耗，那么为了保证其可以安全的到达目的地，只考虑整数解，至多发射过程中可以承受多少程度的损耗？

输入输出:

输入描述:

每个输入包含一个测试用例。每个测试用例包含一行一个整数 h （1 <= h <= 10^18）。

输出描述:

输出一行一个整数表示结果。

示例1

输入

10

输出

2

题解

二分法，很简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def loss(n):
    return n*(n+1)
while(True):
    try:
        n=int(input())
        left=0
        right=n+1
        mid=(left+right)//2
        while(True):
            if(loss(mid)>n and loss(mid+1)>n):
                right=mid-1
                mid=(left+right)//2
            elif(loss(mid)<=n and loss(mid+1)<=n):
                left=mid+1
                mid=(left+right)//2
            elif(loss(mid)<=n and loss(mid+1)>n):
                break
        print(mid)
    except:
        break

阅读全文 »

发表于 | 更新于 | 评论数：

前馈网络与普通机器学习里的神经网络比较类似，因此本博客没做深入总结，具体可以参考之前博客。

简介

之前我们已经学习过了基础的神经网络模型，深度学习的深层神经网络所谓的深度，就是相较于普通神经网络的单隐层，深层神经网络模型往往有着更加复杂、更多的隐层关系，我们知道单隐层神经网络相当于一次非线性变换，而深层模型则相当于使用到三个或更多次非线性变换的更复杂的非线性回归模型，而前馈则意味着模型的输出与模型的本市没有反馈连接（如果有反馈，则次网络称为循环神经网络）。假设第一、第二、第三隐层对应的非线性变换为$f^{(1)},f^{(2)},f^{(3)}$，则这3层隐层相互连接将形成$f(x)=f^{(3)}(f^{(2)}(f^{(1)}(x)))$，为了书写、计算的方便，之后我们将学习如何用有向图来表示这个网络。

代价函数

大多数现代神经网络采用极大似然训练，代价函数为负的对数似然。
$$J(\theta) = -\mathbb{E} _ {\mathbf{x, y} \sim \hat{p} _ \text{data}} \log p _ \text{model}(y \mid x)$$

输出单元

  1. 线性单元
  2. softmax单元
  3. sigmoid单元

隐层单元

  1. 整流线性单元
  2. logistic sigmoid与双曲正切函数

架构设计

架构（architecture）一词是指网络的整体结构：它应该具有多少单元，以及这些单元应该如何连接。

  1. 网络越深，泛化能力越强，但越难优化
  2. 深度和宽度折中
  3. 理想的架构需要不断实验
阅读全文 »

发表于 | 更新于 | 评论数：

本文使用的数据库来自https://www.yiibai.com/mysql/sample-database.html ，

连接SQL

1
2
3
4
5
6
7
8
# 打开 MySQL 服务
sudo service mysql start
#连接SQL服务器，参数-h为sql服务器地址，-u为用户名，默认为root，-p为密码
mysql -h host -u root -p password
# 退出SQL
exit

数据库与数据表

显示-SHOW

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
SHOW DATABASES;
SHOW TABLES;
--# eg.数据表概览
mysql> show tables;
+--------------------+
| Tables_in_yiibaidb |
+--------------------+
| customers          |
| employees          |
| items              |
| offices            |
| orderdetails       |
| orders             |
| payments           |
| productlines       |
| products           |
| tokens             |
+--------------------+
10 rows in set (0.00 sec)
阅读全文 »