C++多态

发表于 2018-08-30 | 分类于编程语言， C++

虚函数

虚函数是在基类中使用关键字 virtual 声明的函数。在派生类中重新定义基类中定义的虚函数时，会告诉编译器不要静态链接到该函数。

我们想要的是在程序中任意点可以根据所调用的对象类型来选择调用的函数，这种操作被称为动态链接，或后期绑定。

多态

父类调用子类的函数需要用到虚函数

#include <iostream>
using namespace std;

class Shape {
protected:
	int width, height;
public:
	Shape(int a = 0, int b = 0)
	{
		width = a;
		height = b;
	}
	virtual int area()
	{
		cout << "Parent class area :" << endl;
		return 0;
	}
};
class Rectangle : public Shape{
public:
	Rectangle(int a = 0, int b = 0) :Shape(a, b) { }
	int area()
	{
		cout << "Rectangle class area :" << endl;
		return (width * height);
	}
};
class Triangle : public Shape{
public:
	Triangle(int a = 0, int b = 0) :Shape(a, b) { }
	int area()
	{
		cout << "Triangle class area :" << endl;
		return (width * height / 2);
	}
};
// 程序的主函数
int main()
{
	Shape *shape;
	Rectangle rec(10, 7);
	Triangle  tri(10, 5);

	// 存储矩形的地址
	shape = &rec;
	// 调用矩形的求面积函数 area
	shape->area();

	// 存储三角形的地址
	shape = &tri;
	// 调用三角形的求面积函数 area
	shape->area();

	return 0;
}

双循环链表

发表于 2018-08-28 | 分类于数据结构

静态链表

发表于 2018-08-28 | 分类于数据结构

LDA线性判别分析

发表于 2018-08-13 | 分类于人工智能，特征工程

欲使同类样本的投影点尽可能接近，可以让同类样本的投影点的协方差尽可能小；而欲使异类样本的投影点尽可能远离，可以让异类样本的类中心之间的距离尽可能大

LDA思想

LDA是一种监督学习的降维技术，也就是说它的数据集的每个样本是有类别输出的。这点和PCA不同。PCA是不考虑样本类别输出的无监督降维技术。LDA的思想可以用一句话概括，就是“投影后类内方差最小，类间方差最大”。什么意思呢？我们要将数据在低维度上进行投影，投影后希望每一种类别数据的投影点尽可能的接近，而不同类别的数据的类别中心之间的距离尽可能的大。
可能还是有点抽象，我们先看看最简单的情况。假设我们有两类数据分别为红色和蓝色，如下图所示，这些数据特征是二维的，我们希望将这些数据投影到一维的一条直线，让每一种类别数据的投影点尽可能的接近，而红色和蓝色数据中心之间的距离尽可能的大。

阅读全文 »

xgboost

发表于 2018-08-13 | 分类于人工智能，机器学习

简介

下图就是CART树和一堆CART树的示例，用来判断一个人是否会喜欢计算机游戏

阅读全文 »

GBDT

发表于 2017-10-20 | 分类于人工智能，机器学习

简介

GBDT也是集成学习Boosting家族的成员,由梯度提升方法与回归树结合而成。
分类|损失函数
回归|$(y-\hat y)^2$
分类|$p_K log_2 \; p_K$

阅读全文 »

SVM支持向量机

发表于 2017-10-18 | 分类于人工智能，机器学习

简介

支持向量机（support vector machines，SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机。构建一个超平面将数据点分开,使所有数据距离超平面的距离最大。其中红色与蓝色的数据点成为支持向量

阅读全文 »

神经元-感知器梯度下降

发表于 2017-09-04 | 分类于人工智能，深度学习

感知器-神经元

输入权值 一个感知器可以接收多个输$(x_1, x_2,…,x_n\mid x_i\in R)$(特征)，每个输入上有一个权值$w_i\in R$。此外还有一个偏置项$b$,就是上图中的$w_0$
激活函数 感知器的激活函数可以有很多选择，比如我们可以选择下面这个阶跃函数$f$来作为激活函数： $f(z)=\left\{\begin{matrix} 1&\: \, z>0\\ 0&\: \,otherwise \end{matrix}\right.$
输出感知器的输出由下面这个公式来计算 $y=f(\mathrm{w}\bullet\mathrm{x}+b)\qquad$ 偏置项$b$,就是上图中的$w_0$ $y=f(\mathrm{w}\bullet\mathrm{x})$
线性单元和梯度下降
当感知器为线性函数时候 $y=\mathrm{w}\bullet\mathrm{x}+b$ 偏置项$b$,就是上图中的$w_0$，$y=\mathrm{w}\bullet\mathrm{x}$其优化如下所示
梯度下降法
在监督学习下，对于一个样本，我们知道它的特征$x$，以及标记$y$。同时，我们还可以根据模型 $y=\mathrm{w}\bullet\mathrm{x}+b$ 计算得到输出 $\bar{y}$。注意这里面我们用$y$表示训练样本里面的标记，也就是实际值；用带上划线的 $\bar{y}$ 表示模型计算的出来的预测值。我们当然希望模型计算出来的和越接近越好。则损失函数为 $loss = \frac{1}{2}\sum_{i=1}^{n}(y^{(i)}-\bar{y}^{(i)})^2$

$\frac{\partial loss}{\partial w}=\sum_{i=1}^{n}(y^{(i)}-\bar{y}^{(i)})\mathrm{x}^{(i)}$ $\mathrm{w}_{new}=\mathrm{w}_{old}+\eta\sum_{i=1}^{n}(y^{(i)}-\bar{y}^{(i)})\mathrm{x}^{(i)}$ $\begin{bmatrix} w_0 \\ w_1 \\ w_2 \\ ... \\ w_m \\ \end{bmatrix}_{new}= \begin{bmatrix} w_0 \\ w_1 \\ w_2 \\ ... \\ w_m \\ \end{bmatrix}_{old}+\eta\sum_{i=1}^{n}(y^{(i)}-\bar{y}^{(i)}) \begin{bmatrix} 1 \\ x_1^{(i)} \\ x_2^{(i)} \\ ... \\ x_m^{(i)} \\ \end{bmatrix}$

牛顿法和拟牛顿法

发表于 2017-09-03 | 分类于人工智能，优化算法

牛顿法（Newton method）和拟牛顿法（quasi Newton method）也是求解无约束最优化问题的常用方法。方法使用函数 $f(x)$的一二阶导数。具有收敛速度快、迭代次数少、计算量大的特点。

问题描述

考虑如下无约束极小化问题：

$\min_{x\in R^n} \; f(x)$

最优点记为$x^\ast$

牛顿法

输入：目标函数$f(x)$，梯度$g(x)=\bigtriangledown f(x)$，海森矩阵$H(x)$，精度要求$\varepsilon $
输出：$f(x)$的极小点$x^\ast$
1. 确定初始点$x_0$，置$k=0$。
2. 计算 $g_k=g(x^{(k)})$
3. 若$\left | g_k \right |<\varepsilon $，则停止计算，得近似解$x^\ast=x^{(k)}$
4. 计算$H_k=H(x^{(k)})$
5. 置$x^{(k+1)}=x^{(k)}-H_k^{-1}g_k$
6. 置$k=k+1$，转第二步骤

其中$g_k=\bigtriangledown f(x^{(k)})$，$H_k=\bigtriangledown^2 f(x^{(k)})=\left [\frac{\partial^2 f}{\partial x_i\partial x_j} \right ]_{n\times n}$。$H_{k}^{-1}$为$x^{(k)}$的Hessian的逆矩阵,

$g(f)=\bigtriangledown f=\begin{bmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \\ \vdots \\ \frac{\partial f}{\partial x_n} \\ \end{bmatrix} \; \; \; \; \; H(f)= \bigtriangledown^2 f= \begin{bmatrix} \frac{\partial^2 f}{\partial x^2_1} & \frac{\partial^2 f}{\partial x_1 \partial x_2} \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \\\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x^2_2} \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\\ \vdots & \ddots & \vdots \\\ \frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} \cdots & \frac{\partial^2 f}{\partial x^2_n} \end{bmatrix}$

代数推导

假设函数 $f(x)$ 二次可微，则在当前第$k$次迭代点 $x^{(k)}$ 对 $f(x)$ 进行二阶泰勒展开

$f \left ( x \right ) \approx f \left ( x^{(k)} \right )+{f}'\left ( x^{(k)} \right )\left ( x-x^{(k)} \right )+\frac{1}{2}{f}''\left ( x^{(k)} \right )\left ( x-x^{(k)} \right )^2$

求函数 $f(x)$ 极值则可以转化为对 $f(x)$ 求导并令其为0，

$\frac{\partial f}{\partial x} \approx f'\left ( x^{(k)} \right )+{f}''\left ( x^{(k)} \right )\left ( x-x^{(k)} \right )=0$

得到

$\begin{align*} x&=x^{(k)}-\frac{f'\left ( x^{(k)} \right )}{f''\left ( x^{(k)} \right )} \\ &= x^{(k)}-H_{k}^{-1}g_k \\ x^{(k+1)} &= x^{(k)}-H_{k}^{-1}g_k \end{align*}$

阻尼牛顿法

原始牛顿法由于迭代公式中没有步长因子，而是固定步长，有时会使迭代超过极值点，即$f(x^{(k+1)})>f(x^k)$，在牛顿方向上附加了步长因子，每次调整时会在搜索空间，在该方向找到最优步长，然后调整

$\lambda _k=arg\; \underset{\lambda \in \mathbb{R}}{min}\; f(x_k+\lambda H_k^{-1}g_k)\;\;\;\;\;\;\; \tag 2$

输入：目标函数$f(x)$，梯度$g(x)=\bigtriangledown f(x)$，海森矩阵$H(x)$，精度要求$\varepsilon $
输出：$f(x)$的极小点$x^\ast$
1. 确定初始点$x_0$，置$k=0$。
2. 计算 $g_k=g(x^{(k)})$
3. 若$\left | g_k \right |<\varepsilon $，则停止计算，得近似解$x^\ast=x^{(k)}$
4. 计算$H_k=H(x^{(k)})$
5. 利用$(2)$式子得到步长$\lambda_k$置$x^{(k+1)}=x^{(k)}-\lambda_k H_k^{-1}g_k$
6. 置$k=k+1$，转第二步骤

拟牛顿算法

拟牛顿思路

因为Hessian矩阵的计算量大而且无法保持正定所以采用拟牛顿算法。拟牛顿算法的基本思想是不用二阶偏导数而构造出可以近似Hessian矩阵(或者Hessian矩阵的逆矩阵)的正定对称矩阵，在拟牛顿的条件下优化目标函数

拟牛顿条件

$\begin{align*} \frac{\partial f}{\partial x} &\approx f'\left ( x^{(k)} \right )+{f}''\left ( x^{(k)} \right )\left ( x-x^{(k)} \right )\\ f'\left ( x^{(k+1)} \right ) &\approx f'\left ( x^{(k)} \right )+{f}''\left ( x^{(k)} \right )\left ( x^{(k+1)}-x^{(k)} \right ) \\ g_{k+1}-g_k &\approx H_k\left ( x^{(k+1)}-x^{(k)} \right ) \end{align*}$

拟牛顿法对$H_k$或$H_k^{-1}$取近似值，可减少计算量。记$B\approx H$，$D\approx H^{-1}$，$y_k=g_{k+1}-g_k$，$s_k=x_{k+1}-x_k$。根据拟牛顿条件，可得近似公式：

$\color{red}{B_{k+1}=\frac{y_k}{s_k} \;\;\;\;\;\;\;\;D_{k+1}=\frac{s_k}{y_k}}$

DFP算法

DFP算法采用的是$D$，但并不直接计算$D$，而是计算每一步DD的增量$ΔD$来间接的求出$D$。这也是很多优化算法的做法，因为一般上一步的中间结果对下一步的计算仍有价值，若直接抛弃重新计算耗时耗力耗内存，重新发明了轮子。

$D_{k+1}=D_k+\Delta D_k$

$D_0$通常取单位矩阵I，关键导出每一步的$ΔD_k$。
通过一系列艰苦而又卓绝的推导计算假设取便，最终的导出结果为：

$\color{red}{\begin{align*} D_{k+1}&=D_k+\Delta D_k\; \; \; \; k=0,1,2,\cdots \\ \Delta D_k &=\frac{s_ks_k^T}{s_k^Ty_k} -\frac{D_ky_ky_k^TD_k}{y_k^TD_ky_k} \end{align*}}$

一般来说，在进行中间增量计算时，都要经过这一步艰苦而又卓绝的推导计算。

BFGS算法

BFGS算法与DFP算法类似，只是采用的BB来近似HH。最终的公式为：

$\color{red}{\begin{align*} \Delta B_k &=\frac{y_ky_k^T}{s_k^Ty_k} -\frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k} \end{align*}}$

L-BFGS

L-BFGS算法对BFGS算法进行改进，不再存储矩阵$D_k$，因为$D_k$有时候比较大，计算机的肚子盛不下。但是我们用到$D_k$的时候怎么办呢？答案是根据公式求出来。

从上面的算法推导可知，$D_k$只跟$D_0$和序列$\{s_k\}$和$\{y_k\}$有关。即我们知道了后者，即可以求得前者。进一步近似，我们只需要序列$\{s_k\}$和$\{y_k\}$的最近$m$个值即可。这样说来，我们的计算机内存中只需要存储这两个序列即可，瞬间卸掉了很多东西，正是春风得意马蹄轻。当然，这样cpu的计算量也会相应的增加，这是可以接受的，马，也是可以接受的。

最终的递推关系为

$D_{k+1}=V^T_kD_kV_k+\rho_k s_ks^T_k$

其中

$\rho_k=\frac{1}{y^T_ks_k},V_k=I-\rho_ky_ks^T_k$

拉格朗日

发表于 2017-09-02 | 分类于人工智能，优化算法

拉格朗日对偶性是解决带约束的最优化问题的方法，在实际应用中，通过拉格朗日对偶原理将原始问题转换成对偶问题，将原来不容易解决的问题转化为一个容易解决的问题，如支持向量机，最大熵模型。

原始问题

假设$f(x)，c_i(x),h_j(x)$是定义在$\mathbb{R}^{n}$上的连续可微函数。我们需要求解约束最优化问题：

$\underset{x\in \mathbb{R}^n}{min} f(x)$ $\begin{align} \mathbb{s.t.}\quad &c_i(x) \le 0,\quad i=1,2,\cdots,k\\ &h_j(x)=0,\quad j=1,2,\cdots,l \end{align}$

广义拉格朗日函数

为了求解原始问题，我们首先引入广义拉格朗日函数(generalized Lagrange function)：

$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^k \alpha_ic_i(x) + \sum_{j=1}^l\beta_jh_j(x) \tag{4}$

其中，$x=(x_1,x_2,\cdots,x_n)^T \in \mathbb{R}^n$，$\alpha_i$和$\beta_j$是拉格朗日乘子，特别要求$\alpha_i\geqslant 0$

原始问题的等价转换：极小极大问题

如果把$L(x,\alpha,\beta)$看作是$\alpha、\beta$的函数，求其最大值，即 $\theta_p(x)=\max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta) \tag 5$

确定$\alpha、\beta$使$L(x,\alpha,\beta)$取得最大值，（此过程中把$x$看做常量）下面通过$x$是否满足约束条件两方面来分析这个函数

如果$x$ 满足原始问题中约束，
由(2)、(3)、(4)、(5)可知 $θ(x)=f(x)$。（少的两项一个是非正的，一个是0，要取最大值的话当然得令两者都为0
如果 $x$ 不满足原始问题中的约束，那么 $θ(x)=+∞$。若某个$i$使约束$c_i(x)>0$，则可令则可令$\alpha \rightarrow +∞$，若某个$j$使得$h_j(x)\neq 0,$,则可令$\beta_j h_j(x) \rightarrow +∞$，而将其余各$\alpha _i、\beta_j$均取为0。

综上：

$\theta_p(x)=\left\{\begin{matrix} f(x),&x 满足原始问题约束\\ +\infty,&其他 \end{matrix}\right.$

求解原问题的最小值与原始问题等价

$\color{red}{\underset{x\in \mathbb{R}^n}{min}\; \theta_p(x)= \underset{x\in \mathbb{R}^n}{min}\; f(x)= \underset{x\in \mathbb{R}^n}{min}\;\max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta) }$

原始问题和对偶问题的关系

弱对偶关系：弱对偶关系一定存在，
若原始问题和对偶问题都有最优值，则 $\color{red}{\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta) \leqslant \underset{x\in \mathbb{R}^n}{min}\;\max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta) ={min}\; f(x)}$

强对偶关系
设$x^\ast$和$a^\ast$,$β^\ast$分别是原始问题$\underset{x\in \mathbb{R}^n}{min}\;\underset{\alpha,\beta:\alpha_i\ge0}{max}\; L(x,\alpha,\beta)$和对偶问题$\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta)$的可行解，并且 $\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta) = \underset{x\in \mathbb{R}^n}{min}\;\max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta) ={min}\; f(x)$ $\color{red}{\underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha^\ast ,\beta^\ast ) = \max_{\alpha,\beta:\alpha_i\ge0}L(x^\ast ,\alpha,\beta)={min}\; f(x^\ast )}$ 则$x^\ast$和$a^\ast$,$β^\ast$分别是原始问题和对偶问题的最优解。

弱对偶关系

若原始问题和对偶问题都有最优值，则

$\underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta) \leqslant L(x,\alpha,\beta) \leqslant \max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta)$ $\color{red}{\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta) \leqslant \underset{x\in \mathbb{R}^n}{min}\;\max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta) ={min}\; f(x)}$

推论：设$x^\ast$和$a^\ast$,$β^\ast$分别是原始问题$\underset{x\in \mathbb{R}^n}{min}\;\underset{\alpha,\beta:\alpha_i\ge0}{max}\; L(x,\alpha,\beta) $和对偶问题$\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta) $的可行解，并且$\underset{x\in \mathbb{R}^n}{min}\;\underset{\alpha,\beta:\alpha_i\ge0}{max}L(x,\alpha,\beta) =\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta) $，则$x^\ast$和$a^\ast$,$β^\ast$分别是原始问题和对偶问题的最优解。

强对偶关系

定理1：判断强对偶关系
假设函数$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，并且不等式约束$c_i(x)$是严格可行的，即存在$x$,对所有$i$有$c_i(x)<0$，则存在$x^\ast$和$a^\ast,β^\ast$分别是原始问题和对偶问题的解,并且满足
$\color{red}{\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha^\ast ,\beta^\ast ) =L(x^\ast,\alpha^\ast ,\beta^\ast )= \underset{x\in \mathbb{R}^n}{min}\;\max_{\alpha,\beta:\alpha_i\ge0}L(x^\ast ,\alpha,\beta) ={min}\; f(x^\ast )}$
定理2：KKT条件(求最优解)
假设函数$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，并且不等式约束$c_i(x)$是严格可行的，则$x^\ast$和$a^\ast,β^\ast$分别是原始问题和对偶问题的解的充分必要条件是$x^\ast,a^\ast,β^\ast$满足下面的Karush-Kuhn-Tucker(KKT)条件：（判断极值、其余项为0）

当原问题是凸优化问题时，满足KKT条件的点也是原、对偶问题的最优解。
- 仿射函数 $f(x)=A\cdot x+b$ 仿射函数就是一个线性函数，其输入是$n$ 维向量，参数 $A$ 可以是常数，也可以是 $m×n$ 的矩阵，$b$可以是常数，也可以是 $m$ 维的列向量，输出是一个 $m $维的列向量。在几何上，仿射函数是一个线性空间到另一个线性空间的变换。

路西法

不忘初心，方得始终

GitHub E-Mail

虚函数

多态

LDA思想

简介

梯度下降法

问题描述

牛顿法

代数推导

阻尼牛顿法

拟牛顿算法

拟牛顿思路

拟牛顿条件

DFP算法

BFGS算法

L-BFGS

原始问题

广义拉格朗日函数

原始问题的等价转换：极小极大问题

原始问题和对偶问题的关系

弱对偶关系

强对偶关系