国科大《高级人工智能》吴老师部分——联结主义笔记

• 吴老师上课dddd，上课东西太多太杂，听不太懂比较煎熬，但是课后花点时间理解理解，还是挺有帮助的
• 考试按照重点复习即可，虽然答疑时提到的传教士野人没考😅，但是知识点基本都在最后一节ppt里
• 听说下一届就不会用原题了

一、搜索

1.概念

形式化描述

搜索问题的形式化描述：

• 状态空间
• 后继函数
• 初始状态
• 目标测试
• => 解：一个行动序列，将初始状态转换成目标状态

野人与传教士问题

• 状态空间：{(左岸传教士数量, 左岸野人数量, 船状态[1在左岸，0在右岸])}
• 后继函数：{ P01, P10, P02, P20, P11, Q01, Q10,Q02, Q20, Q11}（船向左/右, 船上传教士数量, 船上野人数量）
• 耗散函数：当前状态下船从一侧划到另外一侧耗散值为1个单位
• 初始状态：(3, 3, 1)
• 目标状态：(0, 0, 0)
  

搜索算法特性

• 完备性(问题有解且能找到一个)
• 最优性(保证找到最优解[最小损耗])
• 时间、空间复杂度

2.树搜索

扩展出潜在行动，维护行动的边缘节点，扩展尽可能少的树节点。

深度优先DFS

• 描述：回溯，每次从边缘集合选最深的[栈]
• 不保证完备性(有环层数无限大)与最优性(无视深度损失)
• m层b叉：时O(b^m) 空O(b^m)
• 迭代深入搜索：结合DFS空间优势+BFS时间优势

广度优先BFS

• 描述：对每个相邻节点再访问其相邻但是未被访问过的节点[队列]
• 保证完备性+最优性
• m层b叉：时O(bm) 空O(bm)
• 代价一致搜索：总是扩展路径消耗最小的节点

3.启发式搜索

• 描述：利用问题拥有的启发信息引导搜索
• 启发策略：估计一个状态到目标距离的函数
• 贪婪搜索：扩展离目标最近的节点，不具完备性、最优性
  • 评价节点：启发函数f(n)=h(n)(当前节点到终点的开销)
• A*搜索：代价一致搜索 + Greedy，
  • 评价：f(n)=代价函数g(n) +启发函数h(n) 启发函数可采纳->最优性

4.图搜索

• 描述：避免重复状态，不扩展一个状态两次：树搜索+扩展过的状态集(closed set)
• A*图搜索：启发式的一致性 => A*图最优
  • 一致性：沿路径的节点估计耗散 f 值单调递增：h(A) ≤ cost(A to C) + h©

5.局部搜索

• 描述：改进单一选项直到不能再改善为止；新的后继函数: 局部改变；不完备，不最优
• 爬山法：任意位置起始，重复直到移动到最好的相邻状态（可能局部最优解）
• 模拟退火搜索：引入随机因素，避免局部极大（允许向山下移动）
• 遗传算法：适应度函数，每步保留N个最好状态

二、人工神经网络

1.神经网络

• 神经元模型：二值神经元模型、模拟神经元模型、二值随机神经元
• 网络结构：前馈结构、反馈/循环结构
• 学习方法：通过神经网络所在环境的模拟过程，调整网络中的自由参数

2.感知机

单层感知机：

• 二值神经元模型+单神经元网络
• 基于超平面判别分类，不能处理非线性分类问题

多层感知机：

• 模拟神经元模型+三层前馈网络
• BP算法：链式规则，从前往后计算结果，从后往前误差反传调整参数（梯度求导），结果评价：最小二乘法
• 梯度消失：BP网络中，由于激活函数的原因，误差反向传播时，样本梯度越来越小，基本上接近于0，意味着初始层的权重和偏差不会在训练中得到有效更新，可能导致网络整体不准确，得不到良好的解

3.深度神经网络

• 学习方法：自下向上的非监督学习 or 自顶向下的监督学习
• 自动编码器：非监督方法得到每层神经元的结果累加，通过端对端的训练调参
• 深度玻尔兹曼机DBM：浅层网络是双向的，最小化能量函数
• 受限玻尔兹曼机RBM：层间全连接，层内无连接，随机神经元，限定模型为二分图，学习目标是极大似然
• 深度置信网络DBN：非监督的预学习+监督微调，多个RBM堆叠
  
  
  

4.CNN卷积网络

• 特点：局部链接、参数共享、子采样（选择题）
• BP算法
  • 输出层：代价函数的确定及求导
  • Pooling：数据的下采样及残差的上采样，降低数据空间尺寸，减少网络参数
  • 卷积层：数据的卷积运算及残差的反卷积运算，对输入图像降维和特征抽取
  • 全连接层：整个网络分类器的作用
• 举例：
  • GoogleLeNet：模块叠加实现深层网络搭建
  • 残差网络：解决深度网络退化问题，深层网络的后面若干层学习成恒等映射，模型就退化成浅层网络
• 图像数据应用
  • 目标检测：卷积的滑动窗口实现+人像识别

5.RNN

• 描述：对序列数据建模，存储过去信息+非线性动态更新隐藏状态
• 结构：隐层有时回有连向下一时间Hidden Layer的边
• 学习算法BPTT：实现权值一致，前向网络，所有时刻损失相加=总损失
• 长序列神经网络：解决梯度膨胀或消散问题
  • GRU：重置门、更新门(计算速度快、容易创建较大的网络)
  • LSTM：遗忘门、信息增加门和输出门
  • BRNN：双向
  • DRNN：深层循环神经网络
    
    
    序列模型：
• 机器翻译：条件语言模型 — 集束搜索
  • 例子：Encoder、Decoder为RNN：
    • Encoder：每个输入的词向量会经过线性变换
    • Decoder：可以是预先训练好的语言模型，能预测合理的English短语
    • 训练encoder、decoder的weights，使所有单词的交叉熵达到最小，每次得到一个最有可能的翻译结果
• 注意力模型：在生成每个翻译结果时只考虑部分提取到的特征
  

6.GAN生成式对抗网络

• 描述：生成器C(生成一个数据，会被判定结果优化)+判别器(判断是否是生成器生成的)

• 核心思想：纳什均衡
  - 生成器：尽量学习真实的数据分布。把噪声数据Z通过生成模型G，伪装成真实数据x
  - 判别器：尽量正确判别输入数据是真实数据还是来自生成器数据
  - 各自提高自己生成能力和判别能力，这个学习优化的过程是寻找生成器和判别器之间的纳什均衡
  

• 训练过程：

  • 1. 固定G，训练D，D希望V(G,D)越大越好，所以需要加上梯度（判断能力越来越好）
  • 2. 固定D，训练G，G希望V(G,D)越小越好，所以要减去梯度（让判别模糊，生成欺骗能力越来越好)
  • 3. 整个训练过程由上面两步交替进行，直至两者平衡

• 类型：

  • 普通GAN：生成real的图像
  • 条件GAN：生成符合条件的数据/图像，判断是否real + match
  • 非监督条件GAN：产生相同风格的图像

考试回忆

• 选择题：
  • A*树搜索最优条件
  • tanh函数图像
  • CNN特点
  • 神经网络在哪一项引入非线性
  • 感知机特点
  • GAN特点
• 简答题：
  • 启发式算法：什么时候算法保证完备 or 保证最优？
• 应用题：
  • 感知机实现布尔函数
  • 卷积神经网络的各层神经元数量和可训练参数数量
  • RNN设计翻译器