^-^
知识表示与推理 课程概述
  1. BASIC CONCEPTS
    1. 什么是知识
    2. 什么是推理
  2. 基于逻辑的知识推理
    1. 谓词逻辑的永真蕴含性
  3. 问题归约法
  4. 演绎推理与归结推理
    1. 命题逻辑
    2. 谓词逻辑
      1. 前束范式
      2. Skolem 标准形
      3. 置换与合一
      4. 利用归结推理进行证明的步骤
  5. 归结过程中的控制策略
  6. 产生式规则
  7. 语义网络和框架表示
  8. Prolog
  9. Assaignment
    1. Problem 1
    2. Problem 2
    3. Problem 3
    4. Problem 4
    5. Problem 5 (optional)
  10. 不确定推理
    1. 可信度推理
      1. 题型与例题
    2. 主观贝叶斯推理
      1. 例题
    3. 证据理论
      1. 概率分配函数
      2. 匹配程度
      3. 求解 CER
      4. 例题
    4. 模糊推理
      1. 模糊推理的基本模式
    5. 基于概率的推理
      1. 贝叶斯网络
      2. Bayes 精确推理
      3. Bayes 近似推理
  • 知识图谱
  • 考试内容

    • Knowledge is justified true belief. —— Plato

    成绩构成：

    • 期末
    • 项目
    • 作业
    • 课堂表现

    期末考试形式:

    • 闭卷
    • 一页纸开卷
    • 不上网的开卷

    要求:

    • 不要作弊
    • 不要交白卷
    • 不要抄作业, 若参考则需搞懂
    • 课堂上可以带电脑
    • 玩手机要静音
    • 上课说话不要打扰周围人
    • 有听课的老师来的时候不要睡觉💤

    BASIC CONCEPTS

    什么是知识

    flourish(涌现): 模型在复杂到一定程度以后, 出现了一些我们原本以为该模型不可能具备的能力.

    什么是推理

    针对各种事务进行分析和决策, 从一直的知识出发, 通过一系列思考,找出蕴含的事实, 或者归纳出新的事实.

    知识表示: 对知识的一种描述和约定, 采用计算机可以接受的、用于描述知识的数据结构.

    知识推理: 基于现有知识, 基于一定方法, 发现新知识的过程.

    推理包括包括:

    • 演绎 (deduction) 法
    • 归纳 (induction) 证明
    • 不确定推理
    • 知识, 统计, 直觉

    总结为下面的图片:

    知识表示的形式: 客观事物的机器标识, 约定和模型, 推理的理论基础, 数据结构, 机器语言

    非单调推理: 在推理过程中, 外界会不断提供线索甚至是新的知识. 比如三门问题.

    基于逻辑的知识推理

    用一套符号系统表示人类的逻辑, 并使用这一套符号来进行推理.

    1: 命题: 具有真假意义的陈述句.

    2: 公理: 默认正确的命题.

    3: 定理: 仅从公理通过推演出来得到的命题.

    4: 谓词: , 中的元素称为个体.

    5: 全称量词 , 存在量词 .

    6:

    7: 设论域为 , 则 8: 析取/or/disjunction; 合取/and/conjunction.

    谓词逻辑的永真蕴含性

    与量词有关的四条重要推理规则 US, UG, ES, EG.

    问题归约法

    归约就是 reduction, 将问题分解为子问题, 解决较小的问题.

    分解: 如果一个问题 可以规约为一组子问题 , 并且只有 有解 有解, 无解 无解, 则称此种规约方式为问题的分解.

    等价变化: 若 归约为为 , 且 有解 有解, 无解 无解, 则称此种归约方式为问题的等价变换, 简称变换.

    用似图结构把问题规约为后继问题的替换集合, 这似图结构称为与或图. 与或图中两个没见过的定义:

    • or vertex: 某个 解决则 解决, 比如下面或图中的

    • and vertex: 所有 解决 才解决

    比如:

    与图

    以及

    或图

    规范的与或图要求每个点的后继节点只能是 or vertex 或者 and vertex 的一种, 可以增加附加节点使与或图规范化, 如下图所示:

    与或图的规范化

    可解节点: 这是一个递归的定义. 叶节点是可解的; 若 为 or vertex, 则某一个 可解 可解; 若 为 and vertex, 则所有 可解 可解;

    解树: 由若干可解结点组成且由可解节点能推出初始节点可解的子树称为解树.

    演绎推理与归结推理

    命题逻辑

    对于命题逻辑, 给定若干命题 , 要求证明某命题 , 比如 , 要证 成立, 通常的做法是使用各种逻辑等值规则, 对 进行恒等变形, 得到 .

    这种做法是所谓的演绎推理, 一般是手动操作, 当命题数目不多时还足以应付, 但是数量太多时, 手动推导就显得捉襟见肘了, 这是自然要提出一种适用于自动推理的方法.

    判断 的计算复杂性为 的, 同时 不可满足, 这类似于 SAT, 已被证明为是 的.

    通常的做法是将 化成 CNF, 可以得到其子句集 , 使用下述称之为 resolution 的手段 不断对子句集进行化简, 其中 为命题, 如果最后空子句 , 则说明 是不可满足的, 这就意味着 , 这是所谓的归结算法, 这是可靠且完备的.

    同时能够看出归结推理是反证法的一种体现, 通过否定结论, 再结合已知的前提条件, 推出矛盾的结论(互相矛盾的结论将会消解为 ), 最后得到证明.

    谓词逻辑

    对于谓词逻辑, 由于量词和变元的存在, 不能直接像上述方式与结论的否定作析取并化为 CNF 通过 resolution 做推理, 需要提出一些简化规则让我们可以不考虑量词, 以及将变元视作常量来处理.

    前束范式

    前束范式 如果公式 的一切量词都位于该公式的最左边, 且这些量词的辖域都延伸到公式的末端, 则称 是一个前束范式, 其一般形式为 , 其中 , 称为 的母式/基式, 中不含有量词.

    为什么要设计前束范式?

    前束范式的量词与母式区分得比较清楚, 这方便后续对母式 继续单独处理, 而不考虑变元时, 母式可以看作是命题逻辑.

    例子: 求 的前束范式. 反复用 De Morgan law 以及 与 的转化即可, 需要注意的是变量名的替换.

    Skolem 标准形

    Skolem 标准形 只保留全称量词的前束范式.

    Skolemization 比较好理解, 比如对于 , 直接去掉所有的 , 并令 , 即可.

    为什么要设计 Skolem 标准形消去存在量词?

    例: 求 的 Skolem 标准形.

    将 替换为某个常量 , 替换为 的函数 , 替换为 的函数 , 得到 .

    置换与合一

    表达式的置换: 表达式 的定义域为 , 置换写做 , 表示用 替换 中的 . 用置换 得到表达式的置换, 记作 . 有 , 但是没有交换律: .

    置换的合成 设 , 则两者的合成 也是一个置换. 的定义是, 对集合 做如下删除操作得到的结果:

    • 去闭环的置换: 时, 删去 , 这相当于用 替换 了
    • 去重复的元素: 若 , 删去 , ?

    其中 表示对 应用置换规则 , 因为 本身也是表达式.

    合一 (Unification) 对于表达式集 , 将置换 作用在 中的每一个元素得到 , 若置换后 中只有一个元素(置换 使多个表达式一致), 则称寻找这样的 达到此目的的操作为合一. 若存在 使 中只有一个元素, 称 是可合一的, 称为 的合一者.

    最通用的合一者 (most general unifier, mgu) 若对 的任一合一者 , 都存在 使 , 则称 为 的最通用合一者.

    置换与合一主要用在谓词逻辑的 resolution 中, 为了保证做 resolution 时不会出现不同的变元, 是如下的定理:

    设 是两个没有相同变元的子句, 是文字, 若 有mgu , 则称 为 的一个二元归结式, 是被归结的文字.

    即 其中 是 的 mgu.

    利用归结推理进行证明的步骤

    设要证 .

    1: 将 中的所有语句都转化为 Skolem 标准形, 不同辖域内的变元要使用不同的名称. 比如 , 那么子句集 就要写成 的形式.

    2: 否定结论 并于 做析取得到 .

    2: 求解 的子句集.

    3: 对于子句集 , 使用谓词逻辑的 resolution 逐一规约, 当 时, 证明完毕, 这一过程可以使用归结反演树表示.

    比如对于 : 要证 , 它的反演树如下:

    归结反演树示例

    归结过程中的控制策略

    • 删除策略
    • 语义归结策略
    • 线性归结策略
    • 输入归结策略. 输入归结策略是不完备的.
    • 单元归结策略

    产生式规则

    语义网络和框架表示

    Prolog

    1. 大写字母为变量, 小写字母为常量.
    2. Relation(X,Y) 表示 和 具有关系 relation, 但是这个关系是单向的.
    3. Attribute(X) 表示 具有属性/性质 Attribute.
    4. A :- B 等价于 , 即推理关系, 为真得到 为真, 多个表达式且用 , 隔开. friend(X,Y):-friend(Y,X).
    5. onesidelove(X,Y):-loves(X,Y), \+ loves(Y,X). \+ 表示否定.
    6. 列表. loc_list([apple, broccoli, crackers],kitchen) 表示厨房中有列表中的东西. 空表 [] 又可用 nil 表示.
    1. 已知下述Prolog程序能够发现列表中最大、最小的元素，请基于列表[3,7,4]阐述推理的过程：
    1
    2
    3
    4
    5
    6
    7
    8
    minmax(X,X,[X]).
    minmax(Min,Max,[X|L]) :- minmax(Min2,Max2,L),
        min(X,Min2,Min),
        max(X,Max2,Max).
    min(X,Y,X) :- X =< Y.
    min(X,Y,Y) :- Y =< X.
    max(X,Y,X) :- Y =< X.
    max(X,Y,Y) :- X =< Y.

    Assaignment

    第一次作业：

    提交时间：不晚于 11月30日晚23点59分

    提交方式：以课程设计小组为单位，邮箱：xzheng@uestc.edu.cn，或者QQ小窗发送

    Problem 1

    We are given the following knowledge base of travel information:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    byCar(auckland,hamilton).
    byCar(hamilton,raglan).
    byCar(valmont,saarbruecken).
    byCar(valmont,metz).
    byTrain(metz,frankfurt).
    byTrain(saarbruecken,frankfurt).
    byTrain(metz,paris).
    byTrain(saarbruecken,paris).
    byPlane(frankfurt,bangkok).
    byPlane(frankfurt,singapore).
    byPlane(paris,losAngeles).
    byPlane(bangkok,auckland).
    byPlane(losAngeles,auckland).

    Write a predicate travel/2 which determines whether it is possible to travel from one place to another by ‘chaining together’ car, train, and plane journeys. For example, your program should answer yes to the query travel(valmont,raglan).

    So, by using travel/2 to query the above database, you can find out that it is possible to go from Vamont to Raglan. In case you are planning a travel, that’s already very good information, but what you would then really want to know is how exactly to get from Valmont to Raglan.

    Write a predicate travel/3 which tells you how to travel from one place to another.

    The program should, e.g., answer yes to the query

    1
    travel(valmont,paris,go(valmont,metz,go(metz,paris)))

    and

    1
    X = go(valmont,metz,go(metz,paris,go(paris,losAngeles)))

    to the query travel(valmont,losAngeles,X).

    Answer:

    问题一:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    % travle(X,Y) 判断能否从X到达Y
    travel(X,Y) :- byCar(X,Y).
    travel(X,Y) :- byCar(Y,X).
    travel(X,Y) :- byTrain(X,Y).
    travel(X,Y) :- byTrain(Y,X).
    travel(X,Y) :- byPlane(X,Y).
    travel(X,Y) :- byPlane(Y,X).
    travel(X,Y) :-
        byCar(X,Z),
        travel(Z,Y).
    travel(X,Y) :-
        byTrain(X,Z),
        travel(Z,Y).
    travel(X,Y) :-
        byPlane(X,Z),
        travel(Z,Y).

    为什么

    1
    2
    3
    travel(X,Y) :-
        travel(X,Z),
        travel(Z,Y).

    会栈溢出呢?

    问题二:

    1
    2
    3
    4
    5
    6
    7
    8
    % 实现 go 和 travel
    % travel(X,Y,Z) 表示若可以从X到Y, 则Z是从X到Y的方式, 
    travel(X,Y,go(X,Y)):-byCar(X,Y).
    travel(X,Y,go(X,Y)):-byTrain(X,Y).
    travel(X,Y,go(X,Y)):-byPlane(X,Y).
    travel(X,Y,go(X,Z,Path)):-
        (byCar(X,Z);byTrain(X,Z);byPlane(X,Z)),
        travel(Z,Y,Path).

    对于 query travel(valmont,losAngeles,X) 的输出为

    1
    X = go(valmont,saarbruecken,go(saarbruecken,paris,go(paris,losAngeles)))

    Problem 2

    1. Write a 3-place predicate combine1 which takes three lists as arguments and combines the elements of the first two lists into the third as follows:
    1
    2
    3
    4
    5
    6
    7
    ?- combine1([a,b,c],[1,2,3],X).

    X = [a,1,b,2,c,3]

    ?- combine1([foo,bar,yip,yup],[glub,glab,glib,glob],Result).

    Result = [foo,glub,bar,glab,yip,glib,yup,glob]
    1. Now write a 3-place predicate combine2 which takes three lists as arguments and combines the elements of the first two lists into the third as follows:
    1
    2
    3
    4
    5
    6
    7
    ?- combine2([a,b,c],[1,2,3],X).

    X = [[a,1],[b,2],[c,3]]

    ?- combine2([foo,bar,yip,yup],[glub,glab,glib,glob],Result).

    Result = [[foo,glub],[bar,glab],[yip,glib],[yup,glob]]
    1. Finally, write a 3-place predicate combine3 which takes three lists as arguments and combines the elements of the first two lists into the third as follows:
    1
    2
    3
    4
    5
    6
    7
    ?- combine3([a,b,c],[1,2,3],X).

    X = [join(a,1),join(b,2),join(c,3)]

    ?- combine3([foo,bar,yip,yup],[glub,glab,glib,glob],R).

    R = [join(foo,glub),join(bar,glab),join(yip,glib),join(yup,glob)]

    Answer

    1:

    1
    2
    3
    combine1([],[],[]).
    combine1([H1|T1],[H2|T2],[H1,H2|T]):-
        combine1(T1,T2,T).

    为什么没有语句 combine1([],[],[]). 时输出为 false 呢?

    2:

    1
    2
    3
    combine2([],[],[]).
    combine2([H1|T1],[H2|T2],[[H1,H2]|T]):-
        combine2(T1,T2,T).

    3:

    1
    2
    3
    combine3([],[],[]).
    combine3([H1|T1],[H2|T2],[join(H1,H2)|T]):-
        combine3(T1,T2,T).

    Problem 3

    1. Write a predicate mysubset/2 that takes two lists (of constants) as arguments and checks, whether the first list is a subset of the second.
    2. Write a predicate mysuperset/2 that takes two lists as arguments and checks, whether the first list is a superset of the second.

    Answer

    1:

    只需要保证 .

    枚举 中的每个元素, 判断是否都在 里.

    1
    2
    3
    4
    5
    6
    7
    8
    member(H,[H|_]).
    member(X,[_|T]) :-
           member(X,T).

    mysubset([],_).
    mysubset([HY|TY],X):-
           member(HY,X),
           mysubset(TY,X).

    _ 表示任意类型的变量.

    2:

    1
    mysuperset(X,Y):- mysubset(Y,X).

    Problem 4

    Write a Prolog program to implement the predicate frequencies(L,M), which takes as input a list L and returns a list of pairs [x,n], where x is an element of L and n is the number of times x appears in L. Here are some sample runs in SWI Prolog:

    1
    2
    3
    4
    5
    6
    7
    ?- frequencies([a,b,a,c,a,c,d,a],L).
    L = [[a, 4], [b, 1], [c, 2], [d, 1]] 
    Yes

    ?- frequencies([],L).
    L = [] 
    Yes

    Answer

    求 中每个元素出现的次数.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    cnt(_,[],0).
    cnt(X,[X|T],N):-cnt(X,T,N1),N is N1+1.
    cnt(X,[_|T],N):- 
           cnt(X,T,N).

    del(_,[],[]).
    del(X,[H|T],[H|R]):-
           X \= H,
           del(X,T,R).
    del(X,[X|T],R):-
           del(X,T,R).

    frequencies([],[]).
    frequencies([X|TM],[[X,N]|T]):-
           cnt(X,[X|TM],N),
           del(X,[X|TM],M1),
           frequencies(M1,T).

    frequencies 中的 cnt 不要错写成 cnt(X,TM,N).

    cnt/3 和 del/3 应该能写一块减少码量.

    Problem 5 (optional)

    Assume that a binary tree is represented in Prolog using the function term

    1
    tree(X,LeftSubTree,RightSubTree)

    where X is the element at any node and LeftSubTree and RightSubTree are the left sub-tree and the right sub-tree for the node respectively. The term nil is used when there is no left sub-tree or right-tree. For example, the following function term:

    1
    tree(20,tree(10,nil,nil),tree(40,tree(30,nil,nil),nil))

    would represent the following binary (search) tree:

    1
    2
    3
    4
    5
      20
      / \
    10  40
        / 
       30

    Recall that a binary search tree is a binary tree in which all the elements in the left sub-tree of a node are less than the element at the node and all the elements in the right sub-tree of a node are greater than the element at the node. Assume that the binary search tree is being used to represent a set of numbers with no duplicates. Write Prolog programs for the following predicates:

    • smallest(X,T) is true if X is the smallest element in the binary search tree T.
    • member(X,T) is true if X is an element in the binary search tree T.
    • height(T,H) is true if H is the height of the binary search tree T where height is defined as the length of the longest path from root to leaf node.

    Answer

    1
    2
    3
    4
    5
    6
    7
    8
    9
    member(X,tree(X,_,_))
    member(X,tree(_,LeftSubTree,RightSubTree)):-
        member(X,LeftSubTree);
        member(X,RightSubTree).

    smallest(X,tree(X,nil,nil)).
    smallest(X,tree(_,LeftSubTree,RightSubTree)):-
        member(X,LeftSubTree),
        \+member(X,RightSubTree).

    注意这里的树的高度的定义是路径的长度, 因此空树和只有一个根节点的树的高度都是 0.

    下面的代码是错误的:

    1
    2
    3
    4
    5
    6
    7
    % WRONG
    height(nil,0).
    height(tree(_,nil,nil),0).
    height(tree(_,LeftSubTree,RightSubTree),H):-
         height(LeftSubTree,HL),
         height(RightSubTree,HR),
         H is max(HL,HR)+1.

    此时程序相当于有两个出口, 因此对于下面两个 query:

    1
    2
    3
    4
    5
    6
    7
    ?- height(tree(20,tree(10,nil,nil),tree(40,tree(30,nil,nil),nil)),2)

    true

    ?- height(tree(20,tree(10,nil,nil),tree(40,tree(30,nil,nil),nil)),3)

    true

    进行测试得到的结果都是 true, 这意味着这棵树的高度既为 2 又为 3.

    根据树的高度的定义, 空树的高度是未定义的, 因为对于空树甚至都没有路径可言, 因此不应该有出口 height(nil,0)., 但是直接删除会导致报错, 因此枚举所有高度为 1 的树, 如下

    1
    2
    3
    4
    5
    6
    7
    8
    % CORRECT
    height(tree(_,nil,nil),0).
    height(tree(_,tree(_,nil,nil),nil),1).
    height(tree(_,nil,tree(_,nil,nil)),1).
    height(tree(_,LeftSubTree,RightSubTree),H):-
         height(LeftSubTree,HL),
         height(RightSubTree,HR),
         H is max(HL,HR)+1.

    需要注意要确保高度为 1 且有一个子树为空树的树的非空子树的两个子树都是空树.

    下面的写法就是不对的:

    1
    2
    3
    4
    5
    6
    7
    8
    % WRONG
    height(tree(_,nil,nil),0).
    height(tree(_,_,nil),1).
    height(tree(_,nil,_),1).
    height(tree(_,LeftSubTree,RightSubTree),H):-
         height(LeftSubTree,HL),
         height(RightSubTree,HR),
         H is max(HL,HR)+1.

    这会将恰有一个子树为空树的树的高度也判断为 1.

    不确定推理

    可信度推理

    可信度推理模型中, 知识是由产生式规则表示的, 一般形式为

    ​ IF THEN ()

    其中 是知识的前提条件, 是知识的结论, 是知识的可信度, .

    定义 , 为 可信度信任增长度不信任增长度, 其中 以及 , 且

    • 当 时 , 的发生使 发生的概率增大.

    • 当 时 , 的发生使 发生的概率减小.

    • MB 和 MD 只能有一者为正, 另一者为 0.

    • , 即对 的信任增长度等于对 的不信任增长度.

    • 不是概率, 通过验证 即可.

    • , 其中 互斥.

    因此

    对于证据 , 可用 衡量 为真或假的程度, 有如下性质:

    • .
    • , 其中 表示 可信度.

    题型与例题

    题型: 给定知识 IF THEN , 以及 , 求解 , 其中每一个 都可能是复合命题, 同时有的 并不一定是已知的.

    方法: 根据每一个知识 求出一个 , 然后对其进行根据符号两两合成, 具体而言, 对于 , 可以进行以下合成 (略去 ) 一般优先挑选同号的进行合成.

    主观贝叶斯推理

    主观贝叶斯推理的表现形式为 IF E THEN (LS, LN) H , 其中 LS 表示充分性度量, LN 表示必要性度量.

    主观贝叶斯的推理任务如下: 对于证据 , 它有一个观察 , 给定先验 和 以及 , 要求将 更新为后验 . 证据和观察都可能是复合的, 并且证据和观察是一一对应的.

    首先 LS 和 LN 的定义如下: 利用 Bayes 公式有 定义几率函数 , 那么 和 一一对应且 , 则 LS 可以写成 , 同理得 .

    由全概率公式 , 可以求出 三个特殊的值:

    • 当 始终为真或者 时, , 由于 和 是一一对应的, 因此可以求出 .
    • 当 始终为假或者 即 时, , 同上由 求出 .
    • 当 不真不假且 即 无关时, .

    根据上述内容整理得到: 此时不出现 之类的东西.

    三个特殊点为

    由上面的全概率公式得到的结果可以知道 关于 是分段线性的, 因此可以求出区间 上 和 的关系式, 那么根据 实际的值就可以求出 .

    当有多个证据 及对应观察 , 有如下关系: 于是可以求出 .

    若 的 是复合公式满足 , 则需要求 , 且这相当于求 , 满足按照合取最小析取最大的规则对 得到 . ?

    例题

    下面的做法是错的:

    根据 算出 , 要计算 可计算 , 计算 可根据 .

    原因可能是 不直接受 的影响, 因此分开计算 是没有意义的.

    证据理论

    证据理论用于处理集合上的不确定性问题, 其推理模型为 IF THEN , 其中结论 , 是样本空间, CF 是可信度因子的集合, 是一一对应的关系即 的可信度为 , 满足 .

    任务为给定证据的确定性 求结论 的确定性 .

    首先定义 CER. 这首先需要定义概率分配函数和在证据 的条件下, 与 的匹配程度 .

    概率分配函数

    设函数 满足 , 则称函数 是 上的概率分配函数, 称为 的基本概率数.

    设 , 用 来代替 , 有下面的几个重点:

    1. 我们关注一个特殊的概率分配函数 , 满足:

      • .

      下文不做特别说明, 出现的概率分配函数都指该概率分配函数.

    2. 在上文特殊的概率分配函数的基础上, 定义信任函数 和似然函数 .

      • , . 表示对 的总体信任度.
      • ; .似然函数也称上限函数, 表示对 的非假信任度.

    3. 定义类概率函数 满足 它有如下性质:

      • .

    4. 概率分配函数的合成: Dempster 合成规则. 对于概率分配函数 , 定义两者的合成(正交和) 满足:

      • .

      • .

      其中 是归一化常数, 满足 , 最终 在确定了 之后, 也可以通过公式 来确定.

    匹配程度

    .

    求解 CER

    步骤如下:

    1. 求 的概率分配函数 . 若有两条知识 同时支持 , 则分别求概率分配函数 并进行正交和得到 的概率分配函数 .
    2. 求解 的信任函数值 和似然函数值 , 并得到类概率函数值 .
    3. 最终 .

    例题

    模糊推理

    Zadeh 创建了模糊理论, 在 Zadeh 的推理模型中, 产生式规则的表示形式为 IF is THEN is , 其中 是论域 中的变量, 表示对象; 分别是论域 上的模糊集, 表示概念.

    模糊命题 is 用于以一种不确定的方式描述 的性质, 又叫做模糊谓词, 比如 big, small, cold, old 等相对未良定义的性质.

    设 是 上的模糊集/模糊关系, 其隶属函数 用于衡量 中的元素有多么 . 若 , 则称 要比 更 . 当 是离散集时, 可以将 记作 . 现在给隶属函数的取值集合 定义一些新的运算, 设 :

    2. 可将 表示为 中的元素, 设矩阵 , 定义 为在普通的矩阵乘法的基础上将 改为上述定义的 , 将 改为上述定义的 .

    又可被模糊修饰词 作用, 其中 为全体模糊谓词的集合. 模糊修饰词用于改变模糊谓词的强弱, 也称为程度词.

    模糊知识 IF is THEN is 表示 之间存在着确定的因果关系, 设两者的论域为 , 则可以定义两者的因果关系为矩阵 , 该矩阵有下面三种常见的定义方式, 设 , 则:

    1. Zadeh 提出的 满足

    2. Mamdani 提出的 满足

    3. Mizumoto 提出的 满足 , 其中

    模糊推理的基本模式

    包括模糊假言推理, 模糊拒取式推理和模糊三段论推理.

    1. 假言推理: 

      1
      2
      3
      知识: IF x is F THEN y is G (R)
      证据: x is F'
      结论: y is G'

    2. 拒取式推理: 

      1
      2
      3
      知识: IF x is F THEN y is G (R)
      证据: y is G'
      结论: x is F'

    3. 三段论: .

      1
      2
      3
      知识: IF x is F THEN y is G (R_1)
      证据: IF y is G THEN z is H (R_2)
      结论: IF x is F THEN y is G (R_3)

    基于概率的推理

    贝叶斯网络

    给定随机变量集合 , 贝叶斯网络是二元组 , 其中

    • 为以 为节点的 DAG 且有向边表示随机变量之间的条件关系
    • 为条件概率集合, 在一个具体的贝叶斯网络中, 的体现形式为每个节点旁边的概率表.

    对于结点 , 定义其父节点集合为 , 其祖先节点集合为 .

    贝叶斯网络最重要的特性是局部化特征, 任意一个结点与其祖先节点都是条件独立的, 它与下面的规则等价:

    • 对于一个节点, 定义它的 Markov Blanket (or Markov Boundary) , 该节点条件独立于 中的结点.

    根据条件独立这一特点, 应用链规则 , 可以得到

    Bayes 精确推理

    对于具有单连通性的贝叶斯网络 , 设 是观察到的特定事件(集), 是查询变量, 是证据变量集合, 则若要查询后验概率 , 有 其中 是归一化常数, 满足 .

    Bayes 近似推理

    知识图谱

    PRA

    考试内容

    PPT: 请好好地看看我.

    命题逻辑部分考证明题, 包括的题型:

    1. 直接证明谓词逻辑和命题逻辑.

    2. 归结法证明谓词逻辑和命题逻辑. 归结推理题目会明确说要用归结推理.

      注意步骤, 每一步推导都要写出基于的事实欲推理的公式.

    产生式系统部分包括的题型:

    1. 给定规则 (prolog程序) 和一个例子, 阐述例子是如何得到一步一步得到最终的结果的.
    2. 给定任务, 写出 prolog (即相应的产生式规则), 请将 textbook 和 exercise 中的题目看一下.

    如果考试的时候的题目发现写的 prolog 超过三行 (三个逻辑), 那么大概是写错了.

    语义网络部分包括的题型:

    1. 给定知识用语义网络进行表示, 画出语义网络, 注意要尽可能地详细.

    复习的时候不用看全称量词部分, 只考到蕴含: 如果...那么...

    尽量写得稍微完整一些.

    不确定推理部分的题型:

    1. 可信度推理
    2. 主观贝叶斯推理
    3. 证据理论
    4. 模糊推理
    5. 基于概率的推理

    至少考三道题左右, 给例子算答案, 记得带计算器, 例题参考 PPT, 公式要掌握熟练. 建议抄一遍PPT.

    讲贝叶斯推理的时候把课给翘了.

    知识图谱推理部分的题型:

    1. PRA (基于路径排序的推理算法).

      第一种情况: 不管路径上的关系, 直接计算路径上的概率;

      第二种情况: 在路径上给出关系, 计算概率的加和.

    2. TransE, TrnasH, TransP, TransD 有什么共同点. 看一眼 PPT 就行.

    2023-08-30

    以上
    ©
    Too Young Too Naive 本站由Hexo驱动｜使用Hexo-theme-A4主题