Intelligente Systeme 课程总结

智能系统课程考试之前做的总结,教授喜欢出各种简答题,所以本文主要是各种算法的优缺点、使用场景、复杂度。另外因为是德语考试,所以除了中文以外的内容大多是德语。

1. 不带权搜索

算法 BS 广度优先搜索 TS 深度优先搜索 TBS 深度限制搜索 IV 迭代加深搜索
完整性 否(树高有限时“是”) 是(t \ge d
最优
时间复杂度 b^d b^m b^t b^d
空间复杂度 b^d bm bt bd

b:分支因数

d:解的深度

m:树高

t:限制深度

完整性和最优性条件

  • 可解
  • 有限分支因数
  • 所有路径代价相同

树高有限则深度优先搜索完整,否则不具有完整性。

IV具有BS的时间复杂度,同时又有更好的空间复杂度。

继续阅读“Intelligente Systeme 课程总结”

神经网络:线性回归

智能系统课程关于神经网络的第一部分,讲解了权重优化问题,介绍了线性函数的闭式解和梯度下降法。

线性回归模型

对于线性函数

f_{w_0, w_1}(x) = w_1x + w_0 = y

确定w_0w_1,使得f_{w_0, w_1}(x)更好地拟合已有的数据。

损失函数(Loss Function)

损失函数可以采用和方差或均方差的形式,教授在课件中使用的是和方差形式,在代码中用了均方差。

和方差:

Loss(f_w) = \sum\limits_{i = 1}^N (y_i - f_w(x_i))^2

均方差:

Loss(f_w) = \frac{1}{n} \sum\limits_{i = 1}^N (y_i - f_w(x_i))^2

另外通常引入常系数\frac{1}{2}来抵消求导之后的系数2,方便计算。教授在课件中使用了该常系数但代码中没有,导致代码中带有一项2.0/n。

带有系数\frac{1}{2}的和方差损失函数:

Loss(f_w) = \frac{1}{2} \sum\limits_{i = 1}^N (y_i - f_w(x_i))^2

带有系数\frac{1}{2}的均方差损失函数:

Loss(f_w) = \frac{1}{2n} \sum\limits_{i = 1}^N (y_i - f_w(x_i))^2

继续阅读“神经网络:线性回归”