【机器学习】遇到的一些问题和笔记

笔记和问题

• NP问题、P问题、NPC问题
• 什么是P=NP？
• Delta规则

NP问题、P问题、NPC问题

NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。

P类问题：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。(能很快找到答案的问题)

NP类问题：指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。所有的P类问题都是NP问题。(能很快验证答案是否正确的问题)

NPC问题：一个NP问题可以使所有NP问题在多项式复杂度内归约到它。也称NP完全问题。(能很快验证答案是否正确，但无法很快找到答案的问题)

归约：也叫约化。 简单地说，一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。

什么是P=NP？

P=NP：NP完全问题能在多项式时间内解出

P≠NP：理论上根本没有多项式时间复杂度的解法

Delta规则

• 1986 年，由认知心理学家 McClelland 和 Rumellhart 在神经网络训练中引入了 δ 学习规则，该规则亦可称为连续感知器学习规则（与离散感知器学习规则相并行）。
• δ 学习规则是一种利用梯度下降法的一般连续性规则。