分类目录归档:algorithm

贝叶斯优化

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

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

拉普拉斯特征映射 LE

拉普拉斯特征映射(Laplacian Eigenmaps,简称LE)是一种基于图的降维算法

前置知识:图论基础概念拉普拉斯矩阵谱聚类

LE算法核心思想:在低维空间内,尽可能保证局部样本间的结构不变

LE算法步骤:

  • 构建近邻图,方法可参考谱聚类一文中的数据转图
  • 根据已构建的图计算邻接矩阵$W$、度矩阵$D$和拉普拉斯矩阵$L$
  • 求解拉普拉斯矩阵,得到最小的$k$个特征值对应特征向量
  • 特征向量组成矩阵$H$,每一行都对应每个样本的降维后的稠密表示

LE算法分析:

  • 谱聚类相当于先经过LE(拉普拉斯特征映射)算法降维后的K-means聚类算法,因此谱聚类的核心推导过程就是LE算法。所以L

Read more

谱聚类

1 算法概况

谱聚类(spectral clustering):一种基于图的聚类算法

前置知识:图论基础概念图论基础#3.1 理解拉普拉斯矩阵

核心思想:将数据转化为图的形式,距离近的数据间对应的边权重高,距离远的数据间对应的边权重低。之后通过切图的方式,使得不同子图间的边权值和尽可能低,子图内部的边权值和尽可能高,从而达到聚类的目的

2 算法细节

2.1 数据转图

核心思想:把每个样本看作一个节点,然后构建任意两点$(x_i,x_j)$间权重边$w_{ij}$

方法1

Read more

拟牛顿类算法

在最优化问题的求解过程中常利用到函数梯度及其高阶信息

  • 这类算法最常见的就是梯度下降法和牛顿迭代法
  • 梯度下降考虑了函数的一阶导数, 是一种一阶优化方法
  • 牛顿算法考虑了函数的二阶偏导, 是一种二阶优化方法

1 牛顿迭代法

牛顿法(Newton's method)又称为牛顿-拉弗森方法(Newton-Raphson method)

牛顿法借助泰勒级数的低阶展开,寻找方程$f(x)=0$的根(因此也被称为切线法)

牛顿法计算步骤:

  • 随机初始化$x=x

Read more

图像几何变换

1 图像几何变换

将一幅图像中的坐标位置映射到另一幅图像中的新坐标位置

2D几何变换分类:

  1. 刚体变换:主要操作包括平移+旋转,变换前后的欧式距离不变,自由度为3
  2. 相似变换:主要操作包括平移+旋转+缩放,具有保角性,不同点之间的距离比保持不变,自由度为

Read more