分类目录归档:algorithm

最速下降法

首先,理解梯度向量是指向函数值增长最快的方向的:MIT18.02笔记-梯度的定义与理解

定义函数$f(x)$,其在点$x$处沿着方向$d$的变化率可用方向导数表示,即梯度与方向的乘积: $$Df(x;d)=\nabla f(x)^Td$$ 当$d=-\frac{\nabla f(x) }{ ||\nabla f(x)|| }$时,函数$f$在点$x$处的下降速率最大,即负梯度方向为最速下降方向

最速下降算法:在迭代过程,每次都选择负梯度方向搜索(对于寻找最小值的最优化问题)

最速下降算法步骤:

  1. 初始化$x_1$,设定允许的最小误差$\epsilon$,迭代次数$k=1$
  2. 对于第$k$次迭

Read more

共轭梯度法

共轭梯度法(Conjugate Gradient)是介于最速下降法牛顿法之间的一个方法

  • 仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,
  • 避免了牛顿法需要存储和计算Hessian矩阵(占用空间大)并求逆的缺点
  • 求解大型线性方程组或非线性最优化问题时常用且高效的方法

1 共轭方向法

设$G$为对称正定矩阵,若$d^T_mGd_n=0,\ m\neq n$ ,则称$d_m$和$d_n$为“G共轭”,共轭方向是“互不相关”的方向

共轭是正交的推广,$n$个共轭向量可以作为$n$维空间的非正交基,共轭向量间是线性无关的

共轭方向法

Read more

回归内生性问题

1 内生性问题

对于回归方程$Y = a + bX + e$,当解释变量$X$和误差项$e$存在相关性时,说明回归模型存在内生性问题

内生性问题的产生原因:

  • 遗漏变量(比如在分析学历和收入的关系时,容易忽略个人能力的影响)
  • 反向因果(比如分析政策对经济影响时,要意识到经济对政策也是有影响的)
  • 选择偏误(样本选择偏误和自选择偏误)、以及测量误差等

内生性问题的后果:在小样本下,内生变量和外生变量估计系数都有偏。在大样本下,内生变量估计系数不一致。外

Read more

核密度估计

核密度估计(kernel density estimation,简称KDE)是核平滑对概率密度估计的应用,即一种以核为权重估计随机变量概率密度函数的非参数方法。由Rosenblatt (1955)和Emanuel Parzen(1962)提出,又名Parzen窗(Parzen window)

核密度估计的实现:

  • 假设$(x_1,x_2,...,x_n)$是来自同一个单变量未知分布中的独立样本
  • 核密度估计可以根据这些样本推测出该分布的概率密度函数: $$\hat{f}_h(x)=\frac{1}{n}\Sigma_{i=1}^nK_h(x-x_i)=\frac{1}{nh}\Sigma_{

Read more

贝叶斯优化

贝叶斯优化是一种通用的黑盒优化算法,不需要计算梯度便可快速解决最优化问题,贝叶斯优化适合处理目标函数计算成本高或求导困难的情况。贝叶斯优化最常用的场景是超参搜索(尤其是神经网络类算法,计算成本高,超参数还多)

1 贝叶斯优化与代理模型

贝叶斯优化(Bayesian Optimization,BO)

  • 目的是要找到一组最优的超参组合x,能使评价/目标函数f(x)达到全局最优

  • 由于评价/目标函数f(x)计算成

Read more

高斯过程回归

1 高斯过程

给定均值向量和协方差矩阵,可以唯一确定一个高斯分布(Gaussian distribution)

给定均值函数和协方差函数,可以唯一确定一个高斯过程(Gaussian Process,GP)

假设自变量为时间$t$,则每一个时刻$t$,高斯过程都对应着一个高斯分布

当时间$t$是连续型变量时,整个高斯过程便对应着无数个高斯分布,所以高斯过程可看作无限维高斯分布

高斯分布的两

Read more

中介效应分析

1 基本介绍

中介效应(mediation effect)分析能解释自变量 X 对因变量 Y 的影响是如何通过中介变量(mediator) M实现的,是多变量研究的重要统计方法。

中介效应 VS 间接效应(indirect effect)

  • 在只有一个中介变量的模型中,二者是等价的
  • 当中介变量大于1时,间接效应可以是某特定中介变量的中介效应,也可以是某几个或所有中介效应的和

中介效应 VS “遮掩效应” (suppression effects)

  • 当自变量 X

Read more

一次性密码算法

1 一次性密码OTP

一次性密码(英语:one-time password,简称OTP),又称动态密码或单次有效密码,是指计算机系统或其他数字设备上只能使用一次的密码,有效期为只有一次登录会话或交易。一次性密码一般会配合账号密码等安全登入机制,实现双因素认证(two-factor authentication)

HOTP和TOTP是两种常见的OTP算法

2 HOTP算法

基于HMAC的一次性密码算法(英语:HMAC-based One-time Password algorithm,HOTP)

HMAC 是Ke

Read more

传染病模型
  • 易感者(Susceptible):存在感染风险的正常人群,用符号$S(t)$来表示
  • 感染者(Infective):已经被感染的人群,用符号$I(t)$ 来表示
  • 免疫者(Recovered):因为隔离/疫苗/病愈等原因而具备免疫力的人群
  • 暴露者(Exposed):指接触过感染者,但暂无感染能力的人群(潜伏期)

1 SI模型

假设与定义:

  • 总人口为$N$,不考虑人口的出生与死亡(即总人口不变)
  • 不考虑无感染风险的人群,不

Read more

瑞利熵问题

1 瑞利熵函数

瑞利熵(Rayleigh quotient)函数定义如下: $$R(A,x)=\frac{x^HAx}{x^Hx}$$

  • 其中$A$为$n\times n$的$Hermitian$矩阵;$x$为非零向量;$H$表示共轭转置
  • $Hermitian$矩阵,即厄尔米特矩阵(共轭转置矩阵和自己相等的矩阵)
  • 由于现实机器学习中很少遇见复数的情况,因此$A$可考虑为实对称矩阵

瑞利熵$R(A,x)$的重要性质: $$\lambda_{min}\leq R(A,x)\leq \lambda_{max}$$

  • 其中$\la

Read more