分类目录归档:学习

启发式算法总结

1 启发式算法

启发式算法(Heuristic Algorithms)通常是以问题为导向的(Problem Specific),没有一个通用的框架,每个不同的问题通常设计一个不同的启发式算法,通常被用来解组合优化问题

普通启发式算法一般是一种贪婪算法,需要根据特定问题进行特定设计

贪婪算法,也叫贪心算法

其基本思想是:每一步都采取当前状态下最好的选择,而不考虑全局最优解是否已经达到。在每一步中,贪心算法都会做出一个贪心决策,即选择当前状态下最优的解决方案,并且不考虑这个决策可能会导致的未来后果

以经典的装包问

Read more

蚁群算法

1 基本概念

蚁群算法(Ant Colony Algorithm,ACA)由Marco Dorigo于1992年在他的博士论文中首次提出,该算法模拟了自然界中蚂蚁的觅食行为。

蚂蚁寻径的生物过程:

  • 蚂蚁在寻找食物源时,会在其经过的路径上释放一种信息素,并能够感知其它蚂蚁释放的信息素。信息素浓度的大小表征路径的远近,信息素浓度越高,表示对应的路径距离越短
  • 通常,蚂蚁会以较大的概率优先选择信息素浓度较高的路径,并释放一定量的信息素,以增强该条路径上的信息素浓度,这样,会形成一个正反馈
  • 最终,蚂蚁能够找到一条从巢穴到食物源的最佳路径,

Read more

NP-Hard问题

1 基本概念

P问题:能在多项式时间内解决的问题,比如快速排序/冒泡排序

NP问题:能在多项式时间内验证得出一个正确解的问题(不确保在多项式时间内找到答案)

NP-Complete(NPC)问题:属于NP问题,其他所有属于NP的问题都可以规约成它

规约(Reduction):将问题A转化为问题B,使用问题B的解来解问题A

如果问题A可规约为问题B,说明问题B的时间复杂度要大于或等于问题A的时间复杂度,即问题B的难度一般要比问题A大(毕竟B答案能解A,A不一定能解

Read more

时序聚类

本文中大部分算法都可通过R语言的latend包复现

1 GBTM

轨迹分组算法(Group-based trajectory model,GBTM)

  • 最早由 Daniel Nagin 于 1999 年在知名心理学方法学杂志「Psychological Methods」开始推展
  • 接着由 Bobby Jones 与 Daniel Nagin 于 2001 年发表了 SAS procedure2,于是此方法慢慢

Read more

医院信息系统入门

HIS:医院信息系统(Hospital Information System),为各部门提供病人诊疗/行政管理信息的收集/存储/处理/提取/交换

LIS:实验室信息管理系统(Laboratory Information Management System),专为医院检验科设计的一套信息管理系统

PACS:医学影像存档与通讯系统(Picture archiving and communication systems),医学图像的获取/显示/存贮/传送/管理的综合系统

RIS:放射信息管理系统(Radioiogy information system),是优化医院放射科工作流程管理的软件系统,

Read more

最速下降法

首先,理解梯度向量是指向函数值增长最快的方向的: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 傅里叶变换

1.1 基本定义

传统傅里叶变换的定义为(积分形式):$F(\omega)=\mathcal{F}{f(t)}=\int f(t)e^{-i\omega t}dt$

传统逆傅里叶变换的定义为(积分形式):$f(t)=\mathcal{F}^{-1}{F(\omega)}=\frac{1}{2\pi}\int F(\omega)e^{i\omega t}d\omega$

卷积定理:函数卷积的傅里叶变换是函数傅立叶变换的乘积 $$f\ast g=\mathcal{F}^{

Read more

ART-对抗性鲁棒性工具集

1 基本介绍

对抗性鲁棒性工具集(Adversarial Robustness Toolbox,ART)是用于机器学习安全性的Python库

  • 从逃逸,数据污染,模型提取和推断的对抗性威胁等方面捍卫和评估模型
  • 适用广泛,支持所有常见的数据类型、机器学习任务、机器学习框架

本项目由IBM团队在2019年开源。项目文档不是特别完善,但是示例丰富,API设计

Read more

回归内生性问题

1 内生性问题

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

内生性问题的产生原因:

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

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

Read more