分类目录归档：algorithm
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）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
遗传算法的关键要素：
核心过程：
在统计学中，最小角回归(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
坐标下降法（英语：coordinate descent）是一种非梯度优化算法。算法在每次迭代中，在当前点处沿一个坐标方向进行一维搜索以求得一个函数的局部极小值。在整个过程中循环使用不同的坐标方向。对于不可拆分的函数而言，算法可能无法在较小的迭代步数中求得最优解。
为了加速收敛，可以采用一个适当的坐标系，例如通过主成分分析获得一个坐标间尽可能不相互关联的新坐标系，即自适应坐标下降法。
面对$N$个形式为$(x_i,y_i)$样本组成的样本集，线性回归就是为了寻找形式为$y_{N\times1}=X_{N \times d}\theta_{d\times 1}$的线性方程，使其能最大程度拟合样本，而第一步便是建立线性回归的损失函数/目标函数： $$Loss(\theta)= (y-X\theta)^T(y-X\theta) $$
其中$y$表示真实值，$X\theta$表示的预测值，所以损失函数$Loss(\theta)$表示的便是真实
大部分机器学习模型的构建都是寻找最小损失函数的过程，而梯度下降法（Gradient Descent）便是一种常见迭代优化算法，用于寻找损失最小的参数解。
以简单二次函数为例进行算法的简单说明，模型形式