人工智能I 提纲【超级完备的没有之一】

人工智能 I

目录

书写不易，转载请注明出处——RSMX

概述

  • 人工智能概念提出： 1956 年
  • 20 世纪三大科学技术成就：空间技术、原子能技术、人工智能

人工智能体现在哪些方面？体现为什么形式？

  • 智能制造产业
  • 各类智能机器人
  • 无人驾驶、智能汽车
  • 大数据、云计算、物联网
  • 智慧城市、智慧医疗、智慧农业
  • 虚拟现实技术

自然界四大奥秘：物质的本质 、 宇宙的起源 、 生命的本质 、 智能的发生

图灵指出：“如果机器在某些现实的条件下，能够非常好地模仿人回答问题，以至提问者在相当长时间里误认它不是机器，那么机器就可以被认为是能够思维的。”

计算智能是借鉴仿生学的思想，基于人们对生物体智能机理的认识，采用数值计算的方法去模拟和实现人类的智能 。三大基本领域包括神经计算、进化计算、模糊计算

知识的表示

知识

概念

  • 是在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。
  • 是把有关信息关联在一起所形成的信息结构。

特性

  • 相对正确性：任何知识都是在一定的条件及环境下产生的，在这种条件及环境下才是正确的
  • 不确定性：缘由——随机性、模糊性、经验、不完全性
  • 可表示性与可利用性：可以用适当形式表示出来，可以被利用

一阶谓词逻辑表示法

谓词

一般形式

[P(x_1, x_2, ..., x_n) ]

  • 个体 (x_1, x_2, ..., x_n) ：某个独立存在的事物或者某个抽象的概念
    • 个体是常量：一个或者一组指定的个体 Teacher
    • 个体是变元（变量）：没有指定的一个或者一组个体Less(x, 5)
    • 个体是函数：一个个体到另一个个体的映射Teacher (father (Li) )
    • 个体是谓词Works (engineer (Smith), IBM)
  • 谓词名 (P) ：刻画个体的性质、状态或个体间的关系

谓词公式

连接词
  • ﹁（否定）“机器人不在2号房间”：﹁ Inroom (robot, r2)
  • ∨（析取）李明打篮球或踢足球：Plays(Liming,basketball)∨Plays(Liming,football)
  • ∧（合取）“我喜欢音乐和绘画”：Like(I,music)∧Like(I,painting)
  • →（蕴含）如果刘华跑得最快，那么他取得冠军：RUNS(Liuhua,faster)→WINS (Liuhua,champion)
  • ⬅→（等价）P⬅→Q: “P当且仅当Q”
量词
  • 全称量词：对个体域中的所有（或任一个）个体 x “所有的机器人都是灰色的”： ((forall)x)[ROBOT (x) → COLOR (x，GRAY)]
  • 存在量词：在个体域中存在个体 x “1号房间有个物体”：((exists)x)INROOM（x，r1）

表示知识的步骤

  1. 定义谓词及个体
  2. 变元赋值
  3. 用连接词连接各个谓词，形成谓词公式

例题——表示如下知识：
王宏是计算机系的一名学生。
王宏和李明是同班同学。
凡是计算机系的学生都喜欢编程序。

定义谓词：
COMPUTER(x)：表示x是计算机系的学生。
CLASSMATE(x,y)：表示x和y是同班同学。
LIKE(x,y)：表示x喜欢y。
表示知识：
COMPUTER(Wang Hong)
CLASSMATE(Wang Hong, Li Ming) ((forall)x)(COMPUTER(x) →LIKE(x, programming))

表示特点

优点：

  • 自然性
  • 精确性
  • 严密性
  • 容易实现

局限性：

  • 不能表示不确定的知识
  • 组合爆炸
  • 效率低

产生式表示法

产生式表示

确定性规则知识

  • IF P THEN Q：IF 动物会飞 AND 会下蛋 THEN 该动物是鸟
  • P → Q

不确定性规则知识

  • IF P THEN Q （置信度）：IF 发烧 THEN 感冒 （0.6）
  • P → Q （置信度）

产生式系统的基本结构

graph LR a[控制]-->规则库-->b["控制系统（推理机）"]-->c[综合数据库] a-->b a-->c-->b
  • 规则库：用于描述相应领域内知识的产生式集合
  • 综合数据库：一个用于存放问题求解过程中各种当前信息的数据结构
  • 控制系统（推理机构）：由一组程序组成，负责整个产生式系统的运行，实现对问题的求解。工作：
    • 从规则库中选择与综合数据库中的已知事实进行匹配
    • 匹配成功的规则可能不止一条，进行冲突消解
    • 执行某一规则时，若其右部是一个或多个结论，则把这些结论加入综合数据库中
    • 执行某一规则时，若其右部是一个或多个操作，则执行这些操作
    • 对于不确定性知识，在执行每一条规则时还要按一定的算法计算结论的不确定性
    • 检查综合数据库中是否包含了最终结论，决定是否停止系统的运行

表示特点

优点：

  • 自然性
  • 模块性
  • 有效性
  • 清晰性

缺点：

  • 效率不高
  • 不能表达结构性知识

适宜领域：

  • 领域知识间关系不密切，不存在结构关系。
  • 经验性及不确定性的知识，且相关领域中对这些知识没有严格、统一的理论。
  • 领域问题的求解过程可被表示为一系列相对独立的操作，且每个操作可被表示为一条或多条产生式规则。

框架表示法

一般结构

<框架名>
槽名1:   侧面名11   侧面值111 ，… ，侧面值11P1
  ┊	      ┊
  ┊     侧面名1m   侧面值1m1  ， … ，侧面值1mPm
  ┊
槽名n：  侧面名n1   侧面值n11 ， … ，侧面值n1P1
          ┊
        侧面名nm   侧面值nm1 ， … ，侧面值nmPm
约束：   约束条件
          ┊
        约束条件
  • 框架：一种描述所论对象（一个事物、事件或概念）属性的数据结构
    • 由若干个被称为“槽”的结构组成：
      用于描述所论对象某一方面的属性
      • 每一个槽又可根据实际情况划分为若干个“侧面”：
        用于描述相应属性的一个方面
  • 槽和侧面所具有的属性值分别被称为槽值和侧面值
  • 当把具体的信息填入槽或侧面后，就得到了相应框架的一个事例框架。

例子

教师框架

框架名: 〈教师〉
	姓名: 单位（姓、名）
	年龄: 单位（岁）
	性别: 范围（男、女）
		缺省: 男
	职称: 范围（教授，副教授，讲师，助教）
		缺省: 讲师
	部门: 单位（系，教研室）
	住址: 〈住址框架〉
	工资: 〈工资框架〉
	开始工作时间: 单位（年、月）
	截止时间: 单位（年、月）
		缺省: 现在

教师框架事例框架

框架名: 〈教师-1〉
	姓名: 夏冰
	年龄: 36
	性别: 女
	职称: 副教授
	部门: 计算机系软件教研室
	住址: 〈adr-1〉
	工资: 〈sal-1〉
	开始工作时间: 1988，9
	截止时间: 1996，7

特点

  • 结构性：便于表达结构性知识，能将知识的内部结构关系及知识间联系表示出来
  • 继承性：框架网络中，下层框架可以继承上层框架的槽值，也可以进行补充和修改
  • 自然性：框架表示法与人在观察事物时的思维活动是一致的

遗传算法

概述

  • 适用于处理传统搜索方法难以解决的复杂和非线性优化问题
  • 是一种仿生全局优化的随机搜索算法
    • 模仿生物的遗传进化原理
    • 通过选择、交叉、变异等操作机制，使种群中个体的适应性不断提高
  • 核心思想：物竞天择，适者生存

基本流程

st=>start: 开始
ed=>end: 结束
in=>inputoutput: 实际问题参数集
op1=>operation: 参数编码成为染色体
op2=>operation: 初始化群体
op3=>operation: 计算每一个体的适应度
cond=>condition: 终止条件？
op4=>subroutine: 进行遗传操作
选择/交叉/变异
op5=>operation: 群体←新群体，P(t)←P(t+1)
op6=>operation: 对染色体进行解码
out=>inputoutput: 得到问题最优解

st->in->op1->op2->op3->cond
cond(no)->op4->op5(right)->op3
cond(yes)->op6->out->ed
  1. 编码：用字符串表达所研究的问题
  2. 形成初始群体：用随机的方法产生
  3. 计算适应度
  4. 复制：从旧群体中选择优良个体予以复制，直接进入下一代群体
  5. 交叉：对染色体（字符串）的某些部分进行交叉换位。被交换的母体都选自经过复制产生的新一代个体
  6. 变异：将个体字符串某位符号进行逆变
  7. 终止：反复执行上述（3）-（6）项工作，直至得出满意的最优解

概念

  • 每个字符串称作个体
  • 每一遗传代次中个体的组合称为群体
  • 衡量字符串（染色体）好坏的指标是适应度
    • 相对适应度 (f(x_i)/overline{f})

遗传算法的基本算法

编码

位串编码：将问题空间的参数编码为一维排列的染色体的方法

  • 二进制编码：用若干二进制数表示一个个体

    • 优点：遗传操作易实现
    • 缺点：具有较大的Hamming距离

  • Gray 编码：将二进制编码通过一个变换进行转换得到的编码

    • 转换，记数为(<eta_1, eta_2,..., eta_n>)：

      • 二进制转格雷码 & 格雷码转二进制

      [gamma_k=left{ egin{aligned} eta_1 &quad k=1 \ eta_{k-1}opluseta_k &quad k>1 end{aligned} ight. ]

    • 优点：任意两个连续的两个整数的编码值之间只有一个位是不同的，克服了二进制编码的Hamming悬崖问题

实数编码

  • 优点：不必进行数制转换

多参数级联编码：把每个参数二进制编码得到子串，再将子串连成一个完整的染色体

  • 特点：有不同的串长度和参数的取值范围

群体设定

初始种群的产生

  • 把握最优解在问题空间中的分布范围，然后以此范围设定初始群体
  • 随机产生个体，挑最优个体加到初始群体中，不断迭代直到达到预定规模
  • 全局性要求初始解尽量分散

种群规模的确定：一般为20~100

  • 太小：优化性能不太好，易陷入局部最优解
  • 太大：计算复杂

模式定理：若群体规模为M，则遗传操作可从这 (M) 个个体中生成和检测 (M^3) 个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解

适应度函数

求解目标

[egin{align*} &max Fit(x)\ & egin{array}{r@{quad}r@{}l@{quad}l} s.t.quad forall xin R^n, Fit(x)geq 0 end{array} end{align*} ]

函数映射为适应度

  • (min) 转 (max)：(Fit(f(x))=frac{1}{f(x)})
  • (<0) 转 (geq 0)： (Fit(f(x))=min {f(x)-C_{min}, 0})

尺度变换

欺骗问题：在遗传算法中，将所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题，常见问题及解决方案：

  • 过早收敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。
  • 停滞现象：改变原始适应值的比例关系，以提高个体之间的竞争力。
  • 线性变换： (f'=af+b)
  • 幂函数变换：(f'=f^K)
  • 指数变换： (f'=e^{-af})

选择（复制）

目的

从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙

方法

概率确定

  • 适应度比例方法（蒙特卡罗法）：(p_{si}=frac{f_i}{sum^M_{i=1}f_i})
  • 排序方法：对于 (P(x_i)) ，满足 (forall f(x_i)geq f(x_j), P(x_i)geq P(x_j) 且 sum P(x)=1)
    • 线性排序：(p_i=frac{a-bi}{M(M+1)})
    • 非线性排序：(p_i=left{ egin{aligned} q(1-q)^{i-1} &quad i=1,2, ..., M-1 \ (1-q)^{M-1} &quad i=M end{aligned} ight.)

选择方法

  • 转盘赌选择：按选择概率产生一个轮盘， 轮盘每个区的角度与概率成比例
  • 锦标赛选择
    • 锦标赛选择方法：随机选择个体，保存最高适应度个体，迭代达到预定数量
    • 随机竞争方法：赌轮选择一对个体，保存最高适应度个体，迭代达到预定数量
  • 最佳个体保存方法：把群体中适应度最高的个体不进行交叉而直接复制到下一代

优化

  • 期望值模型
  • 排挤模型
  • 浓度控制策略
  • 共享机制
  • 截断选择

交叉

基本的交叉算子

  • 一点交叉：随机设定一个交叉点，该点前或后的两个个体的部分结构进行互换
  • 二点交叉：随机设置两个交叉点，将两个交叉点之间的码串相互交换

优化

  • 平坦交叉：二者之间均匀随机产生
  • 算术交叉：双亲的凸组合
  • 线性交叉：1：1，3：1，1：3，比较最好的两个留下
  • 混合交叉
  • 离散交叉
  • 启发式交叉
  • 模拟二进制交叉
  • 单峰正态分布交叉
  • 单纯形交叉
  • 父体中心交叉
  • 几何交叉
  • 均匀交叉
  • 基于模糊联接的交叉

变异

  • 位点变异：随机挑选一个或多个基因座，并以变异概率作变动
  • 逆转变异：随机选择两点（逆转点），将之间基因值以逆向排序插入到原位置中
  • 插入变异：随机选择一个码，插入随机选择的插入点中间
  • 互换变异：随机选取染色体的两个基因进行简单互换
  • 移动变异：随机选取一个基因，向左或者向右移动一个随机位数

优化

  • 随机变异：区间内均匀随机取
  • 非一致变异：某个区间内随机扰动
  • 边界变异：取边界值
  • 多项式变异
  • 高斯变异
  • Cauthy变异
  • 自适应变异
  • Muhlenbein变异

遗传算法参数

群体规模：

  • 太小：优化性能不太好，易陷入局部最优解
  • 太大：计算复杂

选择比例：

  • 太大：收敛速度很快，易陷入局部最优解

交叉率：

  • 太大：导致群体中的优良模式遭到破坏，走向随机化

变异率：

  • 太大：退化为随机搜索，易陷入局部最优解

示例

一元函数的最大值

  • 编码：二进制编码（串长取决于求解精度）
  • 初始种群：随机
  • 适应度函数：目标函数变换
  • 种群大小50；交叉概率0.75；变异概率0.05；最大代数200
  1. 选择：比例选择法
  2. 交叉：单点交叉
  3. 变异：小概率变异

TSP问题

  • 编码：城市编号向量（路径）
  • 初始种群：随机顺序
  • 适应度函数：(Fit(x)=1/L)
  1. 选择：适应度较大的C个个体直接替换适应度较小的C个个体
  2. 交叉：
    • 保留交叉点的中间部分，交换对应位置的子串
    • OX算子：一个子序列 + 另一个的相对次序
  3. 变异：倒置该两点的中间部分

约束最优化问题

  • 罚函数：无约束问题
    • 适应度函数：超范围适应度降低
    • 交叉/变异 ：方向梯度平移
  • 协同进化遗传算法：一个种群由问题的解组成，另一个种群由约束组成

多目标优化

  • 聚合函数法：权值加和，自适应权值
  • 向量评价遗传算法
graph TB a[下一种群] a-->|"目标1~n"|1 subgraph 子种群 1 2 n end 1-->c 2-->c n-->c c[交叉+变异]-->a

改进遗传算法

双倍体遗传算法

  • 采用显性和隐性两个染色体同时进行进化
  • 采用显性遗传

优点

  • 延长了有用基因块寿命，易于收敛能力，变异概率低时能保持一定水平的多样性

方法

  • 编码/解码：两个染色体
  • 复制算子：计算显性染色体的适应度
  • 交叉算子：显隐同时交叉
  • 变异算子：显性按正常概率；隐性按较大概率
  • 重排算子：个体中适应值较大的染色体设为显性染色体

双种群遗传算法

两个遗传算法群体，复制、交叉、变异操作后交换最优与其他个体

  • 杂交算子：选择两群体随机个个体与最优个体，交换两者

自适应遗传算法 AGA

动态的交叉概率 (P_c) 与变异概率 (P_m)

  • 适应度趋于一致或者趋于局部最优时：概率增
  • 适应度分散：概率减
  • 适应度高个体：概率减
  • 适应度低个体：概率增

[P_c=left{ egin{aligned} frac{k_1(f_{max}-f')}{f_{max}-f'} &quad f'>overline f \ k2 &quad f'leq overline f end{aligned} ight. ]

[P_m=left{ egin{aligned} frac{k_3(f_{max}-f')}{f_{max}-f'} &quad f'>overline f \ k4 &quad f'leq overline f end{aligned} ight. ]

群智能算法概述

  • 每个个体，其运动只遵循简单的规则
  • 群成员之间是平等关系，而没有主从关系

蚁群

蚁群优化算法 ACO

  • 路径概率选择机制：信息素浓度越高的路线，被选中的概率越大。
  • 信息素更新机制：路径越短，信息素的浓度增长得越快。
  • 协同工作机制：蚂蚁个体之间通过信息素进行信息传递。

鸟群

粒子群优化算法 PSO

  • 当一群鸟在随机搜寻食物时，发现某个区域内有一块食物，鸟会先后飞向食物，以及在食物最近的鸟的周围区域继续搜寻食物。
  • 数目庞大的鸟群在飞行中可以有形的改变方向，散开，或者队形的重组。

鱼群

人工鱼群算法 AFSA

  • 觅食行为：当鱼群发现食物时，会向着食物的方向快速游去
  • 追尾行为：一条鱼向其视野内的另一条游向食物的鱼游去
  • 聚群行为：为了避免被其他动物捕食，游向伙伴多的地方
  • 随机游动：无目的的游动

蚁群算法 ACO

概述

  • 1991年，M.Dorigo 以此解决了旅行商(TSP)问题
  • 正反馈机制
  • 通用型随机优化
  • 分布式优化
  • 全局优化
  • 启发式

流程

流程图

st=>start: 开始
ed=>end: 结束
op1=>operation: 初始化
op2=>operation: 迭代次数 Nc=Nc+1
op3=>operation: 蚂蚁k=1
op4=>operation: 蚂蚁k=k+1
op5=>operation: 按照状态转移概率公式
选择下一个元素
op6=>operation: 修改禁忌表
cond1=>condition: K>=蚂蚁总数m？
op7=>operation: 按照公式进行信息量更新
cond2=>condition: 结束条件？
op8=>operation: 输出程序计算结果

st->op1->op2->op3->op4->op5->op6(right)->cond1
cond1(yes)->op7(right)->cond2
cond1(no)->op4
cond2(yes)->op8->ed
cond2(no)->op2

禁忌表

体现了人工蚂蚁的记忆性，使得蚂蚁不会走重复道路，提高了效率

选择路径的转移概率

在 (t) 时刻，蚂蚁 (k) 从城市 (i) 转移到城市 (j) 的概率为

[p^k(i, j)=left{ egin{aligned} frac{[ au(i, j)]^alpha*[eta(i,j)]^eta}{sum} &quad j otin Tabu_k\ 0 &quad jin Tabu_k end{aligned} ight. ]

  • ( au(i,j))：信息素强度
  • (eta(i,j))：期望强度，TSP为 (1/L_{ij})
  • (alpha)：信息素影响程度
  • (eta)：距离影响程度

信息素更新公式

[ au_{ij}=(1- ho)* au_{ij}+sum Delta au^k_{ij}\ Delta au^k_{ij}=left{ egin{aligned} Q/L_k &quad 蚂蚁有经过\ 0 &quad 蚂蚁没有经过 end{aligned} ight. ]

  • ( ho)：信息素挥发速率
    • 防止信息素无限累积
    • 防止陷入当前最优解
  • (Delta au)：路径留下的信息素强度
  • (Delta au^k)：蚂蚁 (k) 留下的信息素强度
  • (Q)：蚂蚁所留轨迹的正常数
  • (L_k)：第 (k) 只蚂蚁周游路径总长

终止条件

  • 达到最大循环次数
  • 最优解连续 K 次
  • 达到给定精度

关键参数选取

蚂蚁数量

  • 常用：城市数目的 1.5 倍
  • 过大：信息素趋于平均
  • 过小：易使未搜索的路径信息素减少到0，早熟

信息素因子 (alpha)

  • 常用：([1,4])
  • 过大：选择已走路径概率大，搜索的随机性降低
  • 过小：等同于贪婪算法，易陷入局部最优

启发函数因子 (eta)

  • 常用：([3,4.5])
  • 过大：收敛速度快，易陷入局部最优
  • 过小：陷入随机搜索，找不到最优

信息素挥发因子 ( ho)

  • 常用：([0.2,0.5])

信息素常数

  • 常用：([10,1000])
  • 过大：信息素积累较块，快速收敛

最大迭代次数

  • 常用：([100,500])
  • 过大：导致资源浪费
  • 过小：导致算法还没有收敛就结束

一般调节策略：

  1. 确定蚂蚁数量 = 城市规模 * 1.5
  2. 参数粗调：(alpha)、(eta)、(Q) —— 取值范围较大
  3. 参数微调：( ho) —— 取值范围较小

改进算法

最优解保留策略蚂蚁系统（带精英策略的蚂蚁系统ASelite）

  • 给最优蚂蚁额外的信息素

蚁群系统（ACS）

  • 状态转移规则：伪随机比率规则，阈值 (q_0)，(q) 为随机数

    • 设 (P=[ au(i, j)]^alpha*[eta(i,j)]^eta)，有：

    [p'=left{ egin{aligned} p &quad q>q_0\ max(P) &quad qleq q_0 end{aligned} ight. ]

  • 全局更新规则：只有最优蚂蚁才允许释放信息素

  • 局部更新规则：蚂蚁途经边信息素减少

最大-最小蚂蚁系统（MMAS）

  • 每次迭代后，只对最优解所属路径上的信息素更新
  • 信息素量限制范围

基于优化排序的蚂蚁系统（ASrank）

  • 信息素更新时对 (Delta au^k_{ij}) 考虑权重的影响，权值 (propto) (1/L_k)

最优最差蚂蚁系统（BWAS）

  • 对 ACS 中最差解进行削弱

一种新的自适应蚁群算法（AACA）

  • ACS 中状态转移规则中 (q_0) 改为自适应伪随机比率规则
    • 避免出现停滞现象

基于混合行为的蚁群算法（HBACA）

  • 按蚂蚁的行为特征将蚂蚁分成4群，分开迭代，最优积累。蚂蚁行为：
    • 随机选取
    • 贪婪选取
    • 信息素强度选取
    • 信息素强度与距离选取

粒子群算法 PSO

概述

  • 1995，Kennedy和Eberhart提出

流程

流程图

st=>start: 开始
ed=>end: 结束
op1=>operation: 初始化粒子群
op2=>operation: 计算每个粒子的适应度
op3=>operation: 根据适应度更新 pBest、gBest
更新粒子位置速度
cond=>condition: 最大迭代次数
达到精度？

st->op1->op2->op3(right)->cond
cond(yes)->ed
cond(no)->op2

粒子速度更新公式

[v_{i}=wv_i+c_1r_1(pbest_i-x_i)+c_2r_2(gbest_i-x_i) ]

  • (r_1 r_2)：随机数
  • (c_1r_1(pbest_i-x_i))：自我认知部分
    • (c_1)：学习因子
      • 过小：迅速丧失群体多样性，易陷入局优而无法跳出
  • (c_2r_2(gbest_i-x_i))：社会经验部分
    • (c_2)：学习因子
      • 过小：完全没有信息的社会共享，导致算法收敛速度缓慢
  • (w)：惯性因子
    • (w=1)：基本粒子群算法
    • (w=0)：失去对粒子本身的速度的记忆
  • (V_m)：最大速度
    • 常用：维度范围 10%~20%
    • 过大：探索能力增强，容易飞过最优解
    • 过小：开发能力增强，易陷入局部最优

邻域设定

决定社会经验部分

  • 全局邻域：全局粒子群算法
  • 局部邻域：局部粒子群算法

特殊问题求解 - TSP

交换子：交换两个位置的城市编号，记为 ((SO_1, SO_2))

交换序：记为 ((SO_1, SO_2,..., SO_n))

合并计算：(oplus)

速度更新公式：

[left{ egin{aligned} &v_i'=v_ioplusalpha(p_i-x_i)opluseta(p_g-x_i)\ &x_i=x_i+v_i, 一定概率为 v_i' end{aligned} ight. ]

优化

标准PSO算法

动态权重 —— 权重递减

[w=w_{max}-(w_{max}-w_{min})*frac{run}{run_{max}} ]

收缩因子法

速度更新公式：可以有效搜索不同区域，最终收敛

[v_i'=Kv_i\ K=frac{2}{|2-c-sqrt{c^2-4c}|}\ c=c_1+c_2, varphi>4 ]

不确定推理方法

概述

区别

  • 推理：从已知事实（证据）出发，运用知识推出结论或证明成立或不成立
  • 不确定性推理：从不确定性的初始证据出发，运用不确定性的知识，推出具有不确定性的结论

基本问题

  • 不确定性知识表示
  • 不确定性证据表示
  • 不确定性算法

概率方法

  • 经典概率方法：AND OR

  • 逆概率方法：【P(B|A) A条件下B的概率】

    • 单证据

    [P(H_i|E)=frac{P(E|H_i)P(H_i)}{sumlimits_{j=1}^{n}P(E|H_j)P(H_j)} ]

    • 多证据

    [P(H_i|E_1E_2..E_m)=frac{P(E_1|H_i)P(E_2|H_i)..P(E_m|H_i)P(H_i)}{sumlimits_{j=1}^{n}P(E|H_j)P(H_j)} ]

可信度方法

概念

  • 可信度：根据经验对一个事物或现象为真的相信程度
    • 带有较大的主观性和经验性，其准确性难以把握
  • C－F 模型：基于可信度表示的不确定性推理的基本方法

C－F 模型

知识不确定性的表示

静态强度 CF（H，E）：知识的强度

IF E THEN H CF(H,E)		# CF(H,E):可信度因子，[-1, 1]
证据不确定性的表示

动态强度 CF（E）：证据 E 当前的不确定性程度

CF(E)=0.6				# E的可信度为0.6
组合证据不确定性的算法
  • AND（合取）：(min{CF_1, CF_2, ..., CF_n})
  • OR（析取）：(max{CF_1, CF_2, ..., CF_n})
不确定性的传递算法

[CF(H)=CF(H,E) imes max{0, CF(E)} ]

结论不确定性的合成算法

[CF_{1,2}=left{ egin{aligned} &CF_1(H)+CF_2(H)-CF_1(H)CF_2(H) &CF_1(H)geq 0,CF_2(H)geq 0\ &CF_1(H)+CF_2(H)+CF_1(H)CF_2(H) &CF_1(H)< 0,CF_2(H)< 0\ &frac{CF_1(H)+CF_2(H)}{1-min{|CF_1(H)|,|CF_2(H)|}} &CF_1(H) imes CF_2(H)<0 end{aligned} ight. ]

证据理论 （D－S理论）

概念

概率分配函数

函数有 (M:2^D ightarrow [0,1]) ，且

[M(empty)=0\ sumlimits_{Asubseteq D}M(A)=1 ]

信任函数

[Bel(A)=sumlimits_{Bsubseteq A}M(B)\ forall Asubseteq Dqquad Bel:2^D ightarrow [0,1] ]

似然函数

不可驳斥函数或上限函数

[Pl(A)=1-Bel( eg A)\ forall Asubseteq Dqquad Pl:2^D ightarrow [0,1] ]

信任函数与似然函数的关系：(Bel(A)leq Pl(A))

概率分配函数的正交和

对于同一空间的两个概率分配函数，其组合证据的概率分配函数为

[M(A) =frac {sumlimits_{xcap y=A}M_1(x)M_2(y)} {1-sumlimits_{xcap y= empty}M_1(x)M_2(y)} =frac {sumlimits_{xcap y=A}M_1(x)M_2(y)} {sumlimits_{xcap y eq empty}M_1(x)M_2(y)} ]

一般步骤

  1. 建立问题的样本空间D
  2. 由经验给出，或者由随机性规则和事实的信度度量算基本概率分配函数
  3. 计算所关心的子集的信任函数值、似然函数值
  4. 由信任函数值、似然函数值得出结论

机器学习之分类

机器学习概述

机器学习与传统程序设计区别

  • 传统程序：修订程序逻辑，复杂程序艺术
  • 机器学习：数据积累，同一算法

分类：根据反馈的不同

  • 监督学习
  • 非监督学习
  • 半监督学习
  • 强化学习

完整的机器学习过程

  1. 数据预处理
  2. 特征工程
  3. 数据建模
  4. 结果评估

贝叶斯分类

概念

条件概率

[P(A|B)=frac{P(AB)}{P(B)} ]

乘法定理

[P(ABC)=P(A)P(B|A)P(C|AB) ]

全概率公式

[P(A)=sumlimits^n_{i=1}P(B)P(A|B_i) ]

贝叶斯公式

[P(B_i|A)=frac{P(A|B_i)P(B_i)}{sumlimits^n_{j=1}P(A|B_j)P(B_j)} ]

朴素贝叶斯公式

假定 (C_i) 是等概率的

[P(C_i|X)=frac{P(X|C_i)P(C_i)}{P(X)} ]

特点

优点：

  • 方法简单，分类准确率高，速度快，所需估计的参数少，对于缺失数据不敏感
  • 能运用于大型数据库

缺点：

  • 独立性假设一般不成立
  • 需要知道先验概率

决策树分类

概述

常见：ID3、 C4.5、 CART

信息熵：信息的复杂程度，(entropy=sum -plog_2p)

信息增益：划分数据集前后信息熵的差值，(=sum Delta entropy_i imes 比例)

优化 - 剪枝

预剪枝更块，后剪枝更精确

  • 预剪枝干：设定一个树高度，当构建的树达到高度时，停止
  • 后剪枝：构建完成后再剪枝

特点

优点

  • 易于理解和实现
  • 数据准备简单或不必要
  • 能通过静态测试对模型评测

缺点

  • 连续性的字段比较难预测
  • 时间顺序的数据，需要很多预处理工作
  • 类别太多时，错误可能增加比较快
  • 一般算法分类，都只是根据一个字段来分类

KNN分类

思想

一个样本与数据集中的k个样本最相似， 如果这k个样本中的大多数属于某一个类别， 则该样本也属于这个类别。

参数选择 - K

通常采用交叉验证法来选取最优的K值

  • 近似误差：对现有训练集的训练误差，值小会过拟合。

  • 估计误差：对测试集的测试误差，值小说明对未知数据的预测能力好。

  • 较小：近似误差小，估计误差大

  • 较大：估计误差小，近似误差大

流程

  1. 计算已知点与当前点距离
  2. 排序
  3. 选取与当前点距离最小的k个点
  4. 统计前k个点所在的类别出现的频率
  5. 返回前k个点出现频率最高的类别作为当前点的预测分类

融合分类方法

  • Bagging：训练集子集给子学习器，投票或平均
  • Stacking：多个子学习器输出做父学习器输入

机器学习之回归

线性回归

R2 判定系数判定一个线性回归直线的拟合程度

一元线性回归

(y=eta_0+eta_1x+varepsilon)

多元线性回归

(y=b_0+b_1x_1+...+b_nx_n)

逐步回归分析

“最优”的回归方程：包含所有对Y有影响的变量, 而不包含对Y影响不显著的变量回归方程

最优选取方法：

  • 从所有组合中选择最优者
  • 从全部变量中逐次剔除不显著因子
  • 从一个变量开始，把变量逐个引入方程
  • 逐步回归分析

思想

  • 从一个自变量开始，视自变量Y作用的显著程度，从大到小地依次逐个引入回归方程
  • 当引入的自变量由于后面变量的引入而变得不显著时，要将其剔除掉
  • 引入一个自变量或从回归方程中剔除一个自变量，为逐步回归的一步
  • 每步都要进行Y值检验，以确保每次引入新的显著性变量前回归方程中只包含对Y作用显著的变量
  • 反复直至既无不显著的变量从回归方程中剔除，又无显著变量可引入回归方程

回归问题的常规步骤

  1. 寻找模型函数
  2. 构造损失函数
  3. 最小化损失求得回归参数

逻辑回归

逻辑回归不是回归，是用回归的办法做分类任务

Sigmoid函数

想参考我如何作图的可以先瞅瞅这几个：

https://www.desmos.com/calculator?lang=zh-CN
npm install -g svgo
svgo *.svg -o *.min.svg

0011

损失函数

[Cost=frac{1}{m}sumlimits_{i=1}^mcos[Y(x)*y] ]

A geek and poetry lover.
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/rsmx/p/14295677.html