分类目录归档：algorithm
维特比算法（Viterbi algorithm）是一种寻找最短路径的动态规划算法。可以用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列，适应于多步骤每步多选择模型的最优选择问题，比如HMM。
维特比算法是针对暴力枚举法的优化
假设有一个长度为$l$的序列，其中$l$对应总天数
其中第$i$天的隐含状态可能情况有$n$种，第$i+1$天的隐含状态可能情况有$m$种
第$i$天的最大概率为$P_i=argmax_k({P_{ik}},k=1,...,n)$，其中$P_{
AC 算法，即 Aho-Corasick 自动机算法，是两位创始人的名称凑出来的（国际惯例起名法了属于是，但是简称和强化学习里的 Actor-Critic 算法重名，需要注意区分~）
此算法的时间复杂度为O(n)，与匹配字符串的数目无关，只跟被匹配字符串长度有关
特性：核心思想和[[1_study/algorithm/字符串类算法/单模式匹配算法 KMP]]（建议先看懂这个）是一致的，都通过寻找字符串的内部规律，达到每次失配时的高效跳转，只不过AC算使用前缀
KMP，全称为Knuth-Morria-Pratt，是三位创始人的名称凑出来的
KMP 算法是一种字符串匹配算法，时间复杂度 ：O(n+m)
特性：字符串头部和尾部会有重复的部分，利用这部分信息，减少匹配次数
理解字符串的前缀和后缀
- 把字符串切割成非空的两份，前面那份就是前缀，后面那份就是后缀
- 所有前缀的可能性组成了前缀集合，所有后缀的可能性组成了后缀集合，比如”Harry”的前缀集合是{”H”, ”Ha”, ”Har”, ”Harr”}，而”Potter”的后缀集合是{”otter”,
蒙特卡洛方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。
蒙特卡洛方法的名字来源于摩纳哥的一个城市蒙特卡洛，该城市以赌博业闻名，而蒙特卡洛方法正是以概率为基础的方法。与它对应的是确定性算法。
蒙特卡洛方法的原理是通过大量随机样本，去了解一个系统，进而得到所要计算的值。
模拟退火算法（Simulated Annealing，SA）的思想最早是由Metropolis等提出的。物理中固体物质的退火过程与一般的组合优化问题之间的相似性，SA是一种由物理退火过程启发的通用优化算法
模拟退火法的物理过程：
遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
遗传算法的关键要素：
核心过程：
支持向量机（support vector machine，简称为SVM）
SVM 算法图解：
SVM 借助核技巧将输入隐式映射到高维特征空间中，从而有效地进行非线性分类
常见的核函数：
| 核函数 | 表达式 | 备注 |
|---|---|---|
| Linear Kerne |
在统计学中，最小角回归(LARS)是一种将线性回归模型拟合到高维数据的算法
用 $T(\hat{\boldsymbol{\beta}})$ 表示 $\hat{\boldsymbol{\beta}}$ 的绝对值范数 $$T(\hat{\boldsymbol{\beta}})=\sum_{j=1}^m|\hat{\beta_j}|\tag{7}$$ 则Lasso即为下面的约束优化问题： $$\min S(\hat{\boldsymbol{\beta}}) \quad \text{s.t.} \quad T(\hat{\boldsymbol{\beta}}) \le t\tag{8}$$ Las
决策树通过树结构存储判断流程和规则，实现复杂规则的有效记录
一般来说，树的非叶节点存储了判断逻辑，并通过树分支表达多个判断结果 通过自上而下的多层逻辑判断，最终在叶节点输出预测的分类结果
决策树示例：
ID3算法主要利用信息增益进行特征的选择，并通过递归方法构建特征
核心思想：三个臭皮匠顶个诸葛亮
集成学习三步走
- 特征抽取
- 反复建模（弱学习器）
- 模型集成（强学习器）
最终的预测输出 = 若干个弱学习器的预测输出的平均
最终的预测输出 = 若干个弱学习器的预测输出的投票结果
- 常见的几种投票法
- 相对多数投票法：少数服从多数
- 绝