跳转至

引论

📖 阅读信息

阅读时间：8 分钟 | 中文字符：3358 | 有效代码行数：4

人工智能概述

可计算思想

费马猜想与费马定理
地方太小，写不下（费马大定理）
英国的数学家怀尔斯证明了这个定理是成立的

如何判断一个问题是否可以计算
证明算术公理的相容性

  • 完备性
  • 一致性
  • 可判定性

图灵机的模型：程序
任何可以计算的函数都可以使用图灵机计算

计算载体 提出学者 计算角度
原始递归函数 哥德尔（Godel） 数学的形式
λ - 演算（λ - calculus） 丘奇（Church） 数理逻辑的形式
图灵机 图灵（Turing） 机械的形式

图灵测试

放入机器和人
出 20 个问题分别进行回答
收集到机器和人回答的结果
请法官进行分辨
如果能区分的话，机器不具备人的认知水平
反之通过了图灵测试，具有人类的智能水平

习题：

解题

  1. 首先对数字进行编码（12 就是 12 个 1）
  2. 初始化纸袋与状态
    1. 初始状态为 \(q_0\)
  3. 当前的符号为 1 的话，将其擦除，转移到状态 \(q_1\)，指针右移
    1. 重复操作，擦除所有的 12 的 1
    2. 指针指向+时, 擦除，转向状态 \(q_2\)，右移
  4. 在“\(q_2\)”状态下，为 1 时，保持 1 不变，转移到状态 \(q_3\)
    1. 右移，处理完成所有的 8 的 1
  5. 此后指针开始左移，将原来的 12 位置的空白转变为 1，从而实现加法的效果

智能计算方法

  • 领域人工智能：
    • 照葫芦画瓢、任务导向（alphago）
  • 通用人工智能
    • 举一反三、从经验中学习
  • 混合增强人工智能（多种智能体的混合形式）（人类是智能的总开关）
    • 外骨骼机器人
    • 人类智能＋机器智能（达芬奇外科手术机器人）
    • 人、机、物联网

主流的方法：

  • 符号主义人工智能为核心的逻辑推理
    • IBM“沃森”的推理
  • 数据驱动的机器学习：
    • 采集海量的人脸的数据，基于学习到的数据完成人脸分辨的任务（像素点的分布）
  • 探索与利用为核心的强化学习
    • 用问题牵引——>从经验中学习
学习模式 优势 不足
用规则教 与人类逻辑推理相似，解释性强 难以构建完备的知识规则库
用数据学 直接从数据中学 以深度学习为例：依赖于数据、解释性不强
用问题引导 从经验中进行能力的持续学习 非穷举式搜索而需更好策略

人工智能的历史进展

人工智能发展的三次低谷
人工智能的目的，是使机器能够具有（模拟、延伸和扩展人类智能的能力，具体可细分为感知、理解、推理、学习、决策等与人类智能相关的核心功能）。

逻辑与推理

命题逻辑

  • 定义：命题是一个能确定是真或者是假的陈述句
    • 原子命题：最简单的基本的命题
    • 复合命题：由原子命题组成的命题

通过命题连接词：

p q \(\neg p\) \(p \land q\) \(p \lor q\) \(p \to q\) \(p \leftrightarrow q\)
False False True False False True True
False True True False True True False
True False False False True False False
True True False True True True True
  • 条件命题前者为假时，无论后者是真假，命题一定为真
    • 如果 p，那么 q 是一种蕴含的关系（充分条件），也就是 p 是 q 的子集
    • p 不成立说明其是一个空集，是任何集合的子集，所以一定为真
推理规则
  • 假言推理：
  • 与消解：
  • 与导入：
  • 双重否定：推导出本身是成立的
  • 单向消解或单项归结：
  • 消解或归结：

例题：

V 是或，反过来是和，——>为条件推理

范式

  • 重要的概念，将命题公式化归为一种标准的形式，可以进行两个命题的等价判定
    • 析去范式：\(\text{假设}\alpha_\mathrm{i(i=1,2,\cdots,k)}\text{为简单的合取式,则}\alpha=\alpha_1\lor\alpha_2\lor\cdots\lor\alpha_\text{k为析取范式}\)
    • 合取范式：\(假设\alpha_i(i=1,2,\cdots,k)为简单的析取式,则\alpha=\alpha_1\wedge\alpha_2\wedge\cdots\wedge\alpha_k为合取范式\)
    • 两者合称范式
    • 析取范式由合取范式组成，合取范式由析取范式组成
  • 析取范式不成立当且仅当每个简单的合取都不成立
  • 合取范式是成立的，当且仅当每个简单的析取式是成立的
  • 任一命题的公式都有等值的析取范式和合取范式（不唯一的）

谓词逻辑

命题逻辑——>谓词逻辑

谓词逻辑中：个体、谓词和量词

  • 个体：可以独立存在的具体或者抽象的概念（x 的变元）
  • 谓词：刻画个体属性或者是描述个体之间关系存在性的元素，其值为真或者是假
    • 与函数的不同
      • 函数使用之后为因变量
      • 谓词使用之后变成了命题
  • 事实符号化：
  • 量词的引入：
    • 全称量词：所有的
    • 存在量词：存在
    • 两者统称为量词
  • 谓词 \(P(x)\)：x 能够制造工具。\(\forall x P(x)\) 表示定义域中的所有个体能够制造工具。\(P(\text{小王})\) 表示小王能够制造工具。
  • 谓词 \(P(x)\)：x 能够制造工具。\(\exists x P(x)\) 表示定义域中的存在某个 / 某些个体能够制造工具。\(P(\text{小王})\) 表示小王能够制造工具（该命题或者为真、或者为假）。
  • 约束变元：有量词的约束 (x)
  • 自由变元：没有量词的约束
  • 自由变元既可以存在于量词的约束范围之内，也可以存在量词的约束范围之外

下面的公式是成立的：

\[ \begin{gathered}(\forall x)(A(x)\lor B)\equiv(\forall x)A(x)\lor B\\(\forall x)(A(x)\wedge B)\equiv(\forall x)A(x)\wedge B\\(\exists x)(A(x)\lor B)\equiv(\exists x)A(x)\lor B\\(\exists x)(A(x)\wedge B)\equiv(\exists x)A(x)\wedge B\end{gathered} \]

在约束变元相同的情况下，量词的运算满足分配率

\[ \begin{gathered}(\forall x)(A(x)\lor B(x))\equiv(\forall x)A(x)\lor(\forall x)B(x)\\(\forall x)(A(x)\wedge B(x))\equiv(\forall x)A(x)\wedge(\forall x)B(x)\\(\exists x)(A(x)\lor B(x))\equiv(\exists x)A(x)\lor(\exists x)B(x)\\(\exists x)(A(x)\wedge B(x))\equiv(\exists x)A(x)\wedge(\exists x)B(x)\end{gathered} \]
描述以下的事实
  • 所有的国王都头戴皇冠。
  • “所有的国王都头戴皇冠” 表示的含义为 “对于所有的x，如果x是国王，那么x头戴皇冠”，符号化表示为\((\forall x)(King(x) \to Head\_On(Crown, x))\)。其中x是变量符号，由于x受到全称量词的约束，因此x是约束变元；Crown是一个常量符号，表示皇冠；\(King(x)\)是一个一元谓词，表示x是国王，\(Head\_On(Crown, x)\)是一个二元谓词，表示x头戴皇冠。
  • 公式中存在多个量词时，多个量词都是同类型的，那么量词的顺序是可以互换的
  • 反之是不可以互换的
\[ \begin{aligned}&(\forall x)(\forall y)A(x,y)\Leftrightarrow(\forall y)(\forall x)A(x,y)&&(\exists y)(\forall x)A(x,y)\Leftrightarrow(\forall x)(\exists y)A(x,y)\\&(\exists x)(\exists y)A(x,y)\Leftrightarrow(\exists y)(\exists x)A(x,y)&&(\exists x)(\forall y)A(x,y)\Leftrightarrow(\forall y)(\exists x)A(x,y)\\&(\forall x)(\forall y)A(x,y)\Rightarrow(\exists y)(\forall x)A(x,y)&&(\forall x)(\exists y)A(x,y)\Rightarrow(\exists y)(\exists x)A(x,y)\\&(\forall x)(\forall y)A(x,y)\Rightarrow(\exists x)(\forall y)A(x,y)&&(\forall y)(\exists x)A(x,y)\Rightarrow(\exists x)(\exists y)A(x,y)\end{aligned} \]

项与原子谓词公式

  • 项是描述对象的逻辑表达式
    • 常量符号和变量符号是项
    • 项组成的函数是项：\(\mathrm{f(t1,t2,\cdots,tn)}\)
    • 有限次使用上述的规则产生的符号串是项
  • 原子谓词公式：项数目等于对象的命题吗
  • 合式公式：
    • 命题常项、命题变项、原子谓词公式为合式公式
    • A 为合式公式，则非 A 也是合式公式
    • A、B 是合式公式，则 \(A\land B、A\lor B、A\to B、B\to A、A\leftrightarrow B\) 是合式公式
    • A 为合式公式，x 为个体变项、\((\exists x)A(x)\neq0(\forall x)A(x)\) 也是合式公式
    • 有限次使用上述的法则构成的表达式组成的是合式公式
使用合式公式描述

  • 解 (1) \(Like(\text{Tom}, \text{Football}) \land Like(\text{Tom}, \text{Basketball})\)。其中，\(Like(\text{Tom}, x)\)表示 Tom 喜欢x，Football 和 Basketball 分别表示踢足球和打篮球。
  • (2) \((\forall x)(Classmate(\text{Tom}, x) \to Like(x, \text{Tom}))\)。其中，\(Classmate(\text{Tom}, x)\)表示x是 Tom 的同学，\(Like(x, \text{Tom})\)表示x喜欢 Tom。
  • (3) \(\neg (\forall x)(Boy(x) \to Like(x, \text{Basketball}))\)。其中，\(Boy(x)\)表示x是男生，\(Like(x, \text{Basketball})\)表示x喜欢打篮球。

推理规则

  • 全称量词消去：
  • 全称量词引入：
  • 存在量词消去：
  • 存在量词引入：
证明

自然语言的形式化

专家系统的构成

flowchart LR
    A["问题逻辑化<br/>(机器可理解)"] --> B["推理机<br/>(专家系统)"]
    C["对某个领域的自然语言、<br/>文本语句等信息进行逻辑化<br/>(machine readable knowledge)"] --> B
    B --> D["答案输出"]
课后题：

知识图谱推理

基本概念

  • 是包含多种关系的图
  • 每个节点是一个实体，任意两个节点之间的边表示两个节点间存在的关系
  • 实体中存在的关系进行推理，可以得到新的知识

归纳

归纳逻辑程序设计算法：使用一阶谓词逻辑进行知识表示
将目标谓词作为推理的规则

  • 目标谓词：
  • 目标谓词只有一个正例
  • 反例：不会显式给出，而是从知识图谱中构建出来
  • 背景知识：

推理的思路：逐步给目标的谓词添加前提约束谓词，使得经过目标谓词之后不覆盖任何的反例
通过信息增益的方式来评判前提约束谓词的好坏
FOIL 算法

信息增益

规则

从实例（正例、反例背景知识中）出发，不断测试所得的推理规则是否包含反例、一旦不包含反例，则学习结束，充分展示了“归纳学习”的能力。则学习之后，将规则幅值

习题

解答
  • FOIL（First-Order Inductive Learner）算法通过寻找覆盖正例且不覆盖反例的规则
  • 在家庭关系中，“Mother” 的定义可结合 “Couple” 和 “Father” 推导：
  • 若 X 和 Y 是 Couple，且 Y 是 Z 的 Father，则 X 是 Z 的 Mother。
  • 带入规则
    • \(X = \text{James}\)，\(Y = \text{David}\)，\(Z = \text{Ann}\)；
    • 已知 “James 和 David 是 Couple”，且 “David 是 Ann 的 Father”；
    • 因此，满足规则条件，可推出 “James 是 Ann 的 Mother”。
  • 验证关系的一致性
    David 也是 Mike 的 Father（符合 “Sibling” 的家庭逻辑）；同时 James 作为 David 的 Couple，自然也成为 Mike 的 Mother，这与整体家庭关系的一致性相互印证，说明推导规则有效。

因果推理

因果推理基本概念

先有鸡还是先有蛋的问题
辛普森悖论

主要模型
  • 结构因果模型
  • 因果图：一个无回路的有向图
    • DAG 称为贝叶斯网络
结构因果模型
  • 有两组变量集合 U 和 V 以及一组函数 f 组成（就是因变量的意思）
  • X 变量出现在 Y 幅值的函数中，则 X 是 Y 的直接原因。X 是 Y 的直接原因或者是其他原因，均称 X 是 Y 的原因
  • U 中的成为外生变量，V 中的为内生变量（外生是原始的变量）（内生都是外生的子代）
  • 每一个结构因果模型都有一个因果图与其对应
因果图模型
  • 原因：在因果图中 Y 是 X 的孩子，则 X 是 Y 的直接原因；Y 是 X 的后代，则 X 是 Y 的潜在原因
  • 可以有效表示联合概率分布

联合概率密度

\[ P(x_1,x_2,\cdots,x_d)=\prod_{j=1}^dP(x_j|x_{pa(j)}) \]

这就是 d 个变量的联合概率密度

\[ x_{pa(j)}\text{表示节点}x_j\text{的父节点集合(所有指向}x_j\text{的节点}) \]
作业：写出联合概率形式

\[ P(X2​,X3​,X4​,X5​,X1​,X6​,Xi​,Xj​)=P(X2​)P(X3​)P(X4​∣X2​)P(X5​∣X3​)P(X1​∣X2​,X3​)P(X6​∣X1​,Xi​)P(Xj​∣X1​,X5​)​ \]

因果图结构

链结构
  • 是一种基本结构
  • 包含三个节点两条边，其中一条由第一个节点指向第二个节点，另外一条由第二个节点指向第三个节点
  • X，Y 在给定 Z 时条件独立
  • 所以有链中的条件独立性定理：
    若 X 和 Y 之间只有一条单向的路径，变量 Z 是截断 (intercept) 该路径的集合中的任一变量，则在给定 Z 时，X 和 Y 条件独立。
分连
  • 三个节点，两条边
  • 两条边分别由第一个点指向第二三个

  • \[ \begin{aligned}&P(X,Y|Z)=\frac{P(X,Y,Z)}{P(Z)}=\frac{P(Z)P(X|Z)P(Y|Z)}{P(Z)}\\&=P(X|Z)P(Y|Z)\end{aligned} \]

  • 定理：Z 是 X, Y 的共同原因，且 X->Y 只有一条路径，则在给定 Z 的条件, XY 条件独立

汇连图
  • 此时的 X, Y 是相关的，没有上面的条件独立的性质
  • 定理：上面，X, Y 是相互独立的，但是在给定 Z 和 Z 的后代时，X, Y 是相关的
D 分离
  • 定义 2.18 D - 分离：路径 p 被限定集 Z 阻塞 (block) 当且仅当：
    • (1) 路径 p 含有链结构 A→B→C 或分连结构 A←B→C 且中间节点 B 在 Z 中，或
    • (2) 路径 p 含有汇连结构 A→B←C 且汇连节点 B 及其后代都不在 Z 中。
      若 Z 阻塞了节点 X 和节点 Y 之间的每一条路径，则称给定 Z 时，X 和 Y 是 D - 分离，即给定 Z 时，X 和 Y 条件独立。（分离则独立）
题目
  1. 若限定集为∅时，X 和 T 相互独立。因为 X 和 T 之间含有一个汇连结构 X→Z←Y，且 Z 及其后代都不在限定集∅中，此时 X 和 T 是有向分离，即 X 和 T 相互独立；
  2. 若限定集为 {W} 时，X 和 T 是相关的。因为 X 和 T 之间含有一个链式结构 Y→S→T（S 不在限定集中），一个分连结构 Z←Y→S（Y 不在限定集 {W} 中），一个汇连结构 X→Z←Y（Z 的后代 W 在限定集 {W} 中），根据 D - 分离的定义，这些结构都无法阻塞 X 和 T 之间的路径，因此 X 和 T 是有向连接的，即 X 和 T 是相关的；
  3. 若限定集为{W,Y}时,X和T条件独立。因为X和T之间只有有一条路径,且这条路径含有一个分连结构Z←Y→S,且Y在限定集{W,Y}中,因此Y阻塞了X和T之间的唯一路径,X和T是有向分离,即限定集为{W,Y}时,X和T条件独立,。
题目
  • 选项 A：有向边 \(T \to Y\)，表示 T 对 Y 存在因果影响，属于因果图模型。
  • 选项 B：有向边 \(Y \to T\)，表示 Y 对 T 存在因果影响，属于因果图模型。
  • 选项 C：有向边 \(Y \to T\)，表示 Y 对 T 存在因果影响，属于因果图模型。
  • 选项 D：T 和 Y 之间没有任何有向边，无法体现变量间的因果关系，因此不属于因果图模型。

因果反事实模型

  • 干预：固定系统中的变量，然后改变系统，观察其他变量的变化
  • 引入了 do 算子（并表示固定不变，而不是条件概率）

因果效应差

\[ Pm(Y=y|X=x,Z=z)=P(Y=y|X=x,Z=z),Pm(Z=z)=P(Z=z) \]
  • 在操纵图中，X 和 Z 是 D 分离的，可以得到因果消音的表达式：
\[ \begin{aligned}P(Y=y|&do(X=x)):\\&P(Y=y|do(X=x))=P_{m}(Y=y|X=x)\\&=\sum_{z}P_{m}(Y=y|X=x,Z=z)P_{m}(Z=z|X=x)\\&=\sum_{z}P_{m}(Y=y|X=x,Z=z)P_{m}(Z=z)\end{aligned} \]

得到最后的使用正常的条件表示的因果效应：

\[ P(Y=y|do(X=x))=\sum_{z}P(Y=y|X=x,Z=z)P(Z=z) \]

右端只包含正常的情况下的概率

因果效应

定理2.8(因果效应) 给定因果图G,PA表示X的父节点集合,!则X对Y的因果效应为:

\[ P(Y=y|do(X=x))=\sum_{z}P(Y=y|X=x,PA=z)P(PA=z) \]

反事实模型
反事实描述的是个体的行为

计算的三个步骤
  • (1) 溯因 (abduction)：利用现有的证据 E 确定环境 U；
  • (2) 动作 (action)：对模型 M 进行修改，移除等式 X 中的变量并将其替换为 X = x，得到修正模型 Mx；
  • (3) 预测 (prediction)：利用修正模型 Mx 和环境 U 计算反事实 Yₓ(U) 的值。
计算干预为用药病人的因果效应