← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 9842.f · 生成模型:Hunyuan

确定性与非确定性算法

理解等级:高级

确定性是针对自动机模型而言的:根据当前状态和输入,若状态转移唯一,则每步结果唯一、最终返回也唯一;若每一时刻有多个状态可选并并行尝试,就称为非确定性,只要有一条路径返回结果算法便结束。自动机是把算法看作基于状态变化迭代的机器,图灵机、有限状态自动机以及后续的玻尔兹曼机、支持向量机都属此类。非确定性算法的关键局限在于:某条并行路径率先达到最优,算法就终止,但此时返回的不一定是全局最优解。这正解释了求解NP类问题的机器学习算法为何常常陷入局部最优、只能给出允许误差范围内的结果,而非精确的最优解。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第5章 梯度寻优 · 查看原书依据

      非确定性算法可能会陷入局部最优,因为所有并行的路径中某个执行路径运行达到最优,算法就会结束,但此时返回的不一定是全局最优解。

    参考来源

    - 位置:《机器学习算法原理与编程实践》第5章 梯度寻优(源文件:extracted/机器学习算法原理与编程实践/_epub-src/OEBPS/text00019.html) - 结论依据:原文用自动机状态转移定义确定性与非确定性,并明确指认非确定性算法某路径最优即结束、返回未必全局最优的局限。 - 原始内容:非确定性算法可能会陷入局部最优,因为所有并行的路径中某个执行路径运行达到最优,算法就会结束,但此时返回的不一定是全局最优解。