知识图谱与FOIL算法

Posted on In

知识图谱与FOIL

实验题目

  • 编写程序，实现 FOIL（First Order Inductive Learner）算法，对如下给定的知识图谱和目标谓词进行规则学习，并得到新的以目标谓词为关系的事实（用一阶逻辑表示）。
    • 给定的知识图谱所有三元组的一阶逻辑如下：
      • \(Father(Jack,Dell)\)
      • \(Father(Dell,Stephen)\)
      • \(Grandfather(Jack,Stephen)\)
      • \(Father(Dell,Seth)\)
    • 目标谓词：
      • \(Grandfather(x,y)\)
  • 要求的输入输出模式如下：
    • 输入格式
      • 第 \(1\) 行：知识图谱的三元组数目 \(n\)
      • 第 \(2 \sim (n+1)\)行：三元组的一阶逻辑表示，例如 \(L(David,Mike)\)
      • 第 \((n+2)\) 行：目标谓词，即 \(Grandfather(x,y)\)
    • 输出格式
      • 第 \(1\) 行：以目标谓词和前提约束谓词组成的规则推理，例如： \(Mother(z, y) \wedge Couple(x,z)\rightarrow Father(x, y)\)
      • 第2行及以后：每一行输出一条推理所得事实，用一阶逻辑表示，例如 \(H(David,Ann)\)

算法原理

知识图谱

知识图谱是一种包含多种关系的图。任一节点是一个实体，任一条边表示两个节点之间的关系。

对于知识图谱的任意两个相连节点以及连接的边，可以用三元组表示为一阶逻辑。

从知识图谱中，可以归纳推理得到新的知识。

归纳学习 - FOIL

我们使用 FOIL (First Order Inductive Learning) 算法来进行归纳推理。

根据给定的目标谓词，我们可以从知识图谱中提取出：

  • 正例，也就是目标谓词的实例化结果
  • 反例，若两个实体的关系一定与目标谓词相悖
  • 背景知识，目标谓词以外的其他谓词实例化结果

我们给目标谓词加上若干前提约束谓词，直到推理规则不覆盖任何反例。增加前提后，对目标谓词或前提约束谓词中的变量依 据背景知识赋予具体值，可以得到其正例与反例数量。

我们引入信息量的概念： \[ I(x)=-\log p(x) \] 其中 \(p(x)\) 为取事件 \(x\) 的概率。

在增加前提约束谓词中，由信息量的公式，可以计算 FOIL 信息增益 \[ \text{FOIL_Gain}=\hat{m}_{+}(\log_2\dfrac{\hat{m}_+}{\hat{m}_++\hat{m}_-}-\log_2\dfrac{m_+}{m_++m_-}) \] 其中 \(\hat{m}_+\) 与 \(\hat{m}_-\) 为增加前提约束谓词的规则后所覆盖的正例与反例数量，\(m_+\) 与 \(m_-\) 是原推理规则所覆盖的正例与反例数量。

选取使信息增益最大的前提约束谓词，并重复该过程，直到推理规则覆盖训练样本集合中正例，不覆盖任意反例。

整个算法的流程如下：

  1. 从知识图谱中提取正例，反例，背景知识。
  2. 依次将谓词加入到推理规则中作为前提约束谓词。
  3. 计算加入前提后的 FOIL 信息增益。
  4. 选取使信息增益最大的前提约束谓词，加入推理规则。
  5. 重复 2~4，直到推理规则覆盖训练样本集合中正例，不覆盖任意反例。

下面的代码是实现 FOIL 算法的主要代码。对于每个前提约束谓词，尝试将其加入到现有规则中，并计算 \(\text{FOIL_GAIN}\)，选择使信息增益最大的前提约束谓词，将其加入现有规则，并重复这一过程直到规则覆盖所有正例，并不覆盖任何负例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def getPres(res, sentences, prem, added):
    # get the reasoning result
    while True:
        maxgain = -float('inf')
        maxprem = sentence('', 'x', 'y')
        mpos, mneg = getPosAndNeg(res, sentences, added)
        for i in prem:
            # find the premise with largest FOIL_GAIN
            added.append(i) # add i into premises
            newpos, newneg = getPosAndNeg(res, sentences, added) # get \hat{m}_+ and \hat{m}_-
            gain = informationGain(mpos, mneg, newpos, newneg) # calculate FOIL_GAIN
            if gain > maxgain:
                maxgain = gain
                maxprem = i
            added.remove(i)
        added.append(maxprem)
        prem.remove(maxprem)
        newpos, newneg = getPosAndNeg(res, sentences, added)
        if newpos == mpos and newneg == 0:
            # if any negative example is not covered and all positive examples are covered
            return added          
    return added