Megaee的摸鱼日记

什么是等变性

设 \(T_g:X\to X\) 是 \(g\in G\) 上的 transformation，\(\phi:X\to Y\) 是一个函数，若存在 \(S_g:Y\to Y\) 使得 \[ \phi(T_g(x))=S_g(\phi(x)) \] 则称 \(\phi\) 对于 \(g\) 等变。

若 \[ \phi(T_g(x))=\phi(x) \] 则 \(\phi\) 对于 \(g\) 不变。

为什么要有等变性

思考分子有关的问题时，我们通常将原子建模成图的节点，化学键建模为图的边。考虑几个简单的分子性质，如势能和原子受力。

主要考虑以下四种不变/等变性：

• 置换(permutation)不变/等变性。实现这个是比较简单的，保证模型不依赖输入的顺序即可。
• 平移不变性。只要模型不依赖于原子的绝对坐标就可以。
• 手性似乎影响不大，研究较少。
• 旋转不变/等变性。实际上容易出问题的就是这一部分。

一些群的名字

• 我们知道旋转矩阵是正交的，其行列式一定为 1。
• \(O(n)\) 表示 n 阶正交矩阵群(othorgonal)，那么其行列式为 1 的表示旋转矩阵，-1 的表示旋转+对称。
• \(SO(n)\) 是 \(O(n)\) 的子群，S = special，表示全体旋转矩阵。
• \(E(n)\) 表示 \(O(n)\) 中的所有元素再加上平移变换(Euclidean)，也就是旋转+平移+对称。
• \(SE(n)\) 表示任意旋转+平移。

如何保证等变性

首先可以保证所有的操作是线性的，并且是很严格的线性，即计算 \(\mathbf{y}=a\mathbf{x}+b\) 时，\(a\) 和 \(b\) 都必须是标量。

另外可以引入内积，范数等进行标量化。 \[ R\mathbf{a}\cdot R\mathbf{b}=\mathbf{a}\cdot \mathbf{b}\\\\ \]

EGNN

传统 GNN 的工作流程可以分为三步：

1. 消息传递，通过两点距离 \(a_{ij}\) 和两点的 feature/隐变量，套一个神经网络；
2. 聚合，通常是将邻居的消息相加；
3. 迭代获得新的隐变量。

\[ \mathbf{m}_{ij} = \phi_e(\mathbf{h}_i^l, \mathbf{h}_j^l, a_{ij}) \]

\[ \mathbf{m}_{i} = \sum_{j \in \mathcal{N}(i)} m_{ij} \]

\[ \mathbf{h}_{i}^{l+1} = \phi_h(\mathbf{h}_i^l,\mathbf m_i) \]

这种模型只引入节点的标量距离，导致模型并不具有旋转等变性。直接把坐标加到消息传递的每一步就可以解决。 \[ \mathbf{m}_{ij}=\phi_e(\mathbf{h}_{i}^{l},\mathbf{h}_j^{l},\lVert \mathbf{x}_i^l-\mathbf{x}_j^l\rVert_2^2,a_{ij}) \]

\[ \mathbf{m}_i=\sum_{j\neq i}\mathbf{m}_{ij} \]

\[ \mathbf{h}_i^{l+1}=\phi_h(\mathbf{h}_i^l,\mathbf m_i),\ \mathbf{x}_i^{l+1}=\mathbf{x}_i^l+C\sum_{j\neq i}\phi_x(\mathbf{m}_{ij}) \] 需要注意的是，这样得到的隐变量 \(\mathbf{h}_l\) 是不变的。

求只出现一次的数，其余数出现两次。

这个问题需要运用异或的性质。对于任意数 a，满足：

\[ \begin{align} a \oplus a = 0\\\\ a \oplus 0 = a \end{align} \]

于是算出所有数的异或就是答案。

有n个人围坐在一起，从第一个人开始报数，数到m的那个人出列，然后从出列的下一个人开始重新报数，数到m的那个人又出列，重复这个过程直到剩下最后一个人。求这个人在原队列中的位置。

1
2
3
4
5

def josephus(n, m):
    if n == 1:
        return 0
    else:
        return (josephus(n - 1, m) + m) % n

时间序列预测

时间序列预测是指使用过去的时间序列数据来预测未来的数据点。

时间序列分析的核心就是挖掘该时间序列中的自相关性。

时空序列预测

时空序列包含了时间与空间上的信息。我们在这里使用的雷达数据就是典型的时空序列。

RNN

循环神经网络(RNN)是一种简单的用于时间序列预测的神经网络模型。RNN的特点是其神经元之间存在循环连接，神经元接受输入数据以及上一个时间的隐藏状态。 \[ h_t = \sigma(W_{hh} \cdot h_{t-1} + W_{hx} \cdot x_t + b_h) y_t = W_{hy} \cdot h_t + b_y \]

梯度消失与梯度爆炸

在反向传播时，可能会经过多层的权重更新，导致梯度逐渐变小，最终趋近于零，这就是梯度消失。这种现象在 RNN 上尤其常见，因为存在循环连接时，很小的梯度会不断相乘。同样，如果梯度逐渐变大，这就是梯度爆炸。

梯度消失会导致网络的前期层几乎不更新参数，难以收敛，梯度爆炸会导致权重更新过快，破坏网络的稳定性。为了解决 RNN 中的这些问题，出现了一些改进的模型，如 LSTM。

LSTM

长短期记忆(LSTM)神经网络是一种特殊的 RNN。传统的 RNN 在捕捉长期依赖关系时通常表现不佳，容易出现梯度消失与梯度爆炸问题。

LSTM 的核心思想是引入了门控机制，允许网络选择性地更新和忽略隐藏状态中的信息，从而更好地控制信息的流动。一个标准的 LSTM 单元包括三个门控和一个记忆单元：

1. 遗忘门：\(f_t=\sigma(W_{f}\cdot[h_{t-1},x_t]+b_f)\)

   遗忘门的作用是决定在当前时间步是否要从记忆单元中移除信息。它通过一个 sigmoid 函数来生成一个介于 0 和 1 之间的值，来控制记忆单元中的信息保留程度。

2. 输入门：\(i_t=\sigma(W_{i}\cdot[h_{t-1},x_t]+b_i)\)

   \(\hat{c_t}=\tanh(W_c\cdot[h_{t-1},x_t]+b_c)\)

   输入门决定在当前时间步要从输入数据中添加多少信息到记忆单元中。它包括一个 sigmoid 层和一个 tanh 层，用于确定更新的记忆内容。

3. 更新门：\(c_t=f_t\circ c_{t-1}+i_t\circ \hat{c_t}\)

   更新门根据遗忘门和输出门的控制，计算得到更新的内容。

4. 输出门：\(o_t=\sigma(W_o\cdot[h_{t-1},x_t]+b_o)\)

   \(h_t=o_t\circ\tanh(c_t)\)

   输出门决定在当前时间步要从记忆单元中提取多少信息作为输出。它通过一个 sigmoid 层和记忆单元的内容来生成一个输出。

变种——增加peephole

为了进一步增强 LSTM 的建模能力，我们允许门控使用记忆单元中的内容作为输入： \[ \begin{align} f_t&=\sigma(W_{f}\cdot[h_{t-1},x_t,c_{t-1}]+b_f)\\\\ i_t&=\sigma(W_{i}\cdot[h_{t-1},x_t,c_{t-1}]+b_i)\\\\ \hat{c_t}&=\tanh(W_c\cdot[h_{t-1},x_t,c_{t-1}]+b_c)\\\\ c_t&=f_t\circ c_{t-1}+i_t\circ \hat{c_t}\\\\ o_t&=\sigma(W_{o}\cdot[h_{t-1},x_t,c_{t-1}]+b_o)\\\\ h_t&=o_t\circ\tanh(c_t) \end{align} \]

ConvLSTM

ConvLSTM 将矩阵相乘的操作更换为卷积。通过卷积操作，实现了对时空信息的特征提取。 \[ \begin{align} f_t&=\sigma(W_{f}\ast[h_{t-1},x_t,c_{t-1}]+b_f)\\\\ i_t&=\sigma(W_{i}\ast[h_{t-1},x_t,c_{t-1}]+b_i)\\\\ \hat{c_t}&=\tanh(W_c\ast[h_{t-1},x_t,c_{t-1}]+b_c)\\\\ c_t&=f_t\circ c_{t-1}+i_t\circ \hat{c_t}\\\\ o_t&=\sigma(W_{o}\ast[h_{t-1},x_t,c_{t-1}]+b_o)\\\\ h_t&=o_t\circ\tanh(c_t) \end{align} \]

Encoding Forecasting Structure

数据集

我们使用的数据是20230530的雷达数据，存储格式为。通过雷达回波数据，我们可以利用 Z-R 关系估计降水量： \[ Z=aR^b \] 其中 \(Z\) 为回波强度，\(R\) 为降水量。

此处的雷达数据中存放的回波强度单位为 dBZ，这意味着 \[ dBZ=10\lg a + 10b\lg R \] 其范围大致在 \([-20,70]\)。

另外，雷达存储的 dBZ 数据并不是严格的三维网格数据。我们通过插值的方法，将其转化为分辨率 2km 的三位网格数据，随后垂直方向取第一个通道的二维数据作为原始数据。

归一化

输入的雷达数据中有较多的缺测值，我们统一用 -20 替换。

由于所构建的模型的输出范围是\([0,1]\)，我们对所有的 dBZ 都进行了如下操作： \[ P=\dfrac{dBZ+10}{70}\\\\ input=\begin{cases} 0,P<0\\\\ 1,P>1\\\\ P,else \end{cases} \] 这样我们的输入被映射到 \([0,1]\) 上，同时筛除了部分异常点。

实验题目

设计并实现一个弱监督文本分类模型。

• 我们只有类的名称，类的关键词和大量无标签的文本。
• 在进阶任务中，我们删去了一些类的名称和关键词，我们需要实现识别未知类别。

实验内容

算法原理

弱监督学习

在有监督学习中，模型从带标签的数据中进行学习；在无监督学习中，模型从不带标签的数据中学习。弱监督学习可以说是结合了这两者。在弱监督学习中，我们拥有极少的带标签数据（或者是关于数据的一些先验知识）与较多的无标签数据，模型需要从这些数据中进行学习。

弱监督学习的优点是，只需要较少的标签数据，降低了人工标注的成本和工作量，并在标注数据有限的情况下仍能获得良好的学习性能。但是，这也会产生一些难以避免的问题，例如准确率较低，模型过拟合等。

本次实验就是一个弱监督学习的任务。在本次实验中，我们拥有的数据是类的名称和对应的关键词，以及大量无标签的文本数据，要求我们实现一个弱监督文本分类器。

自训练算法

自训练算法是一种半监督学习的方法，用于处理只有部分标注数据的情况。在自训练算法中，初始的标注数据集作为训练集训练一个初始模型，然后该模型用于对未标注数据进行预测，并将预测结果作为伪标签加入到训练集中，形成一个更大的训练集。接下来，使用这个扩充后的训练集集重新训练模型，重复这个过程多次。

自训练算法的基本步骤如下：

1. 使用初始标注数据集训练一个初始模型。
2. 使用该模型对未标注数据进行预测，并将预测结果作为伪标签。
3. 将已标注数据集和置信度较高的加入的伪标签组合成一个训练集。
4. 使用扩充后的训练集重新训练模型。
5. 重复步骤2至4直到满足停止条件（例如达到最大迭代次数或模型性能收敛）。

自训练算法的关键在于如何选择哪些未标注数据的预测结果可以被可靠地加入到已标注数据集中。通常使用一定的置信度阈值来筛选预测结果，并且对于置信度较高的样本才进行标记扩充，以尽量减少伪标签引入的噪声。

如何从关键词得到“伪标签”

笔者提出了三种方案：

1. 如果文本中存在某一类别的关键词，就将该文本归为此类；

2. 统计文本中某一类别的关键词数量，将其预测为关键词数量最多的类，在方案 1 的基础上做了一些补充；

3. 将关键词作为初始的训练集，直接用于训练分类器，利用该分类器对所有文本分类，将置信度较高样本的作为下一次训练的训练集。

1 与 2 都不涉及分类模型，只能标注部分词，而 3 是对所有的数据都进行了标注，但方案 3 对那些没有关键词存在的文本分类效果也是很差的。

如何选取分类器

我们尝试了不同分类器在本次任务中的分类效果。在传统的机器学习方法中，我们选择了逻辑回归；在深度学习的方法中，我们选择了 CNN。但是由于 CNN 结构复杂，参数相对较多，训练时间相对较长，我在 CNN 上花的时间相对较少。

如何扩展训练集

根据课件中介绍的算法，我们需要在“伪标签”数据中选择 M 个置信度最高的样本加入训练集。然而在实际情况中，这个 M 是不好取的。

• M 过小，会导致模型的泛化性不好，模型容易出现过拟合。
• M 过大，会导致每次选取的“伪标签”数据中，预测错误的数据增加，训练集的质量下降。
• 即使 M 在训练中的某个时刻取得了一个合适的值，它可能会随着训练集的增大而变得不合适。举例来说，向 10 个数据中加入 1 个数据，与向 1000 个数据中加入 1 个数据，所带来的影响肯定是不同的。

于是笔者考虑将 M 取为一个等差数列，在训练过程中不断增大 M 的值。

我们也可以换一种方法，用置信度作为数据是否加入训练集的指标。这时我们需要确定一个阈值，将所有预测置信度大于该阈值的数据加入到训练集。同样地，根据我们上面的讨论，这个阈值也是要随着训练不断增大的。

整个自训练过程的框架如下：

评价指标

我们介绍几种在分类任务中可以使用的评价指标。

混淆矩阵

在二分类问题中，我们将分类结果分为 4 类：

• TP（真正例）：模型正确地将正例样本分类为正例。
• TN（真负例）：模型正确地将反例样本分类为负例。
• FP（假正例）：模型错误地将反例样本分类为正例。
• FN（假负例）：模型错误地将正例样本分类为负例。

如下：

多分类问题的混淆矩阵是类似的，\(Mat[i,j]\) 上的元素表示实际属于类别 i 的样本被预测为 j 的数量。可以发现矩阵对角线上的元素就表示了模型正确分类的样本数。

准确率

准确率就是模型分类正确的比例。在混淆矩阵中，其等于对角线元素之和/所有元素之和。在二分类任务中： \[ Acc=\dfrac{TP+TN}{TP+FN+FP+TN} \]

精确率

在二分类任务中，精确率指的是模型预测为正的样本中实际为正的比例。 \[ P=\dfrac{TP}{TP+FP} \]

召回率

在二分类任务中，召回率指的是实际为正的样本中被预测为正的比例。 \[ R=\dfrac{TP}{TP+FN} \]

f1_score

在二分类任务中，f1_score 是精确率与召回率的调和平均。 \[ F_1=2\dfrac{P\times R}{P+R} \] 对于多分类任务，我们可以使用 macro-f1。对于每个类别，分别计算该类别的 F1 分数，随后求平均得到 macro-f1。

未知类型识别

在进阶任务中，我们删去了一些类的名称和关键词，需要实现识别未知类别。

课件上给出了三种方法：

• 基于置信度，将置信度小于某个值的预测为未知类别
• 若预测到每个类的概率类似，预测为未知类别
• 基于熵拒绝

这里我们在实现时，使用的是基于置信度的拒绝方法。

下面是一些关于文本分类与分类器的原理。

这一部分很多都是复用以前的报告。

文本向量

首先我们需要将文本转换为向量，作为分类器的输入。

Bag-of-Words

Bag-of-Words 考虑单词出现的次数，向量的每一维度的值表示该维度表示的单词在文档中出现的次数。

TF-IDF

我们用 \(TF\) 表示词频归一化的概率，\(IDF\) 表示逆向文档频率。\(IDF\) 的计算公式如下： \[ IDF_{x_i}=\log\dfrac{N}{1+n(x_i)} \] 其中 \(N\) 为文档总数，\(n(x_i)\) 为出现了单词 \(x_i\) 的文档总数。

于是我们的 \(TFIDF=TF\times IDF\)。

逻辑回归

在二元逻辑回归中，我们使用 sigmoid 函数： \[ y = \dfrac{1}{1+e^{-z}} \] 对 \(z=\mathbf{W}^\mathrm T\mathbf{x}\)进行激活。这样保证了输出 \(y\in(0,1)\)，我们就可以将 \(y\) 看作一个概率值。

在多元逻辑回归中，我们使用 softmax 函数： \[ y(z_i)=\dfrac{e^{z_i}}{\sum_{k=1}^{n}e^{z_k}} \] 对 \(z_i=\mathbf{W}_i^\mathrm{T}\mathbf{x}\) 进行激活。这样我们就将一个类的线性的输出转换为了其被分为这个类的概率。随后我们可以选择概率最大的类别作为预测结果。

在训练过程中，我们需要使用极大似然估计法，用负的对数似然函数作为损失函数，随后使用优化算法（如梯度下降）学习参数。

正则化

L1 正则化和 L2 正则化是逻辑回归中常用的两种正则化方法。L1 正则化通过在损失函数中增加 L1 范数来惩罚模型的系数 \(\mathbf{W}\)，而 L2 正则化选择在损失函数中增加 L2 范数。 \[ L_1=\sum|w_i|\quad L_2=\sum w_i^2 \] 这样能够在一定程度上减少过拟合现象。

CNN

一个最简单的卷积神经网络通常包含以下几层：

• 卷积层
• ReLU 层
• 池化层
• 全连接层

卷积

在 CNN 中，我们的卷积运算定义为： \[ y_{i,j}=\sum_{u=1}^m\sum_{v=1}^nw_{u,v}\times x_{i-u+1,j-v+1} \] 通过这样的卷积运算，我们可以将一个高维度的矩阵映射为一个低维度的矩阵，从而显著减少神经网络中的参数数量。

ReLU

ReLU 函数定义如下： \[ f(x)=\max(0,x) \] ReLU 函数在卷积神经网络中是一种激活函数。该函数的主要优点是收敛速度快，易于求梯度。

池化

池化操作用于对输入特征进行下采样，进一步筛选特征，减少参数数量，增强模型的鲁棒性。常用的池化操作是最大池化，该操作是在特定区域中取出特征图中的最大值作为输出，一般取池化区域为 \(2\times 2\)，步长为 \(2\)。

全连接

全连接层是一个线性层，通常出现在卷积神经网络的尾部，连接方式与其在传统的神经网络中一致，与上一层的所有神经元相连，用来综合前面提取的特征，输出分类或回归的结果。

流程图如下：

优化器

通常我们称更新参数的算法为优化器。

在这里我们使用的优化器主要是 SGD 与 Adam。

• SGD 是随机梯度下降法。我们记需要优化的参数为 \(w\)，损失函数为 \(L\)，学习率为 \(\eta\) 则 SGD 算法更新参数的公式为： \[ w=w-\eta\dfrac{\partial L}{\partial w} \] 该算法计算简单，易于实现，但是容易陷入局部最优解。

• Adam 是自适应矩估计法。在 Adam 中，我们引入动量的概念。首先是一阶动量： \[ m_t=\beta_1m_{t-1}+(1-\beta_1)g_t \] 其中 \(g_t=\dfrac{\partial L}{\partial w}\)。同样还有二阶动量： \[ v_t=\beta_2v_{t-1}+(1-\beta_2)g_t^2 \] 我们对 \(m_t\) 与 \(v_t\) 进行偏差校正： \[ \begin{aligned} \hat{m_t}&=\dfrac{m_t}{1-\beta_1^t}\\\\ \hat{v_t}&=\dfrac{v_t}{1-\beta_2^t} \end{aligned} \]

  于是 Adam 更新参数的公式如下： \[ w=w-\eta\dfrac{\hat {m_t}}{\sqrt{\hat {v_t}}+\epsilon} \]

  \(m_t\) 记录了梯度的平均，可以使算法根据历史梯度进行参数更新；\(v_t\) 记录了梯度的平方平均，实质上是在考虑过滤了震荡后的历史梯度。因此 Adam 算法实现了根据历史梯度的震荡以及过滤了震荡后的历史梯度来对变量进行更新。

损失函数

损失函数度量了模型预测值与真是值的差距。

• 交叉熵函数：\(L(p,q)=-\sum_xp(x)\log q(x)\)

• 均方误差损失函数：\(MSE(y,\hat y)=\dfrac{1}{n}\sum_{i=1}^n(y_i-\hat y_i)^2\)

• 距离损失函数，通过两个向量之间的距离来描述损失。这里的距离可以取多种距离，例如曼哈顿距离、欧氏距离、余弦相似度。

我们本次建立的 CNN 如下：

输入经过一个词嵌入层后输入卷积层，分别进行具有不同卷积核大小的卷积操作，得到的输出经过最大池化层得到输出，进入 dropout 层，通过一个线性层将输入映射为对应的分类。如果为了获取概率，我们可以对输出层做 softmax。设网络的第 i 个输出为 \(W_i\)，softmax 操作是指： \[ p(y=i)=\dfrac{e^{W_i}}{\sum_{k=1}^N e^{W_k}} \] 这样我们实现了归一化，并得到了样本被分为某一类的概率。

关键代码展示

使用逻辑回归，进行自训练算法的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

for i in range(maxiter):
    # if all texts are pseudo-labeled
    if sum(labeled) == len(labeled):
        print("Training over.")
        X_vec = vectorizer.transform(traintexts)
        y_pred = model.predict(X_vec)
        acc = accuracy_score(trainlabels, y_pred)
        f1 = f1_score(trainlabels, y_pred, average='macro')
        print(f"Final accuracy: {acc}")
        print(f"Final f1: {f1}")
        break
    # take keywords as the initial training set
    if i == 0:
        X_new = keywords.copy()
        y_new = y_train.copy()
    print(f'Iteration {i + 1}')
    # predict for all texts
    X_vec = vectorizer.transform(traintexts)
    y_pred = model.predict(X_vec)
    prob = model.predict_proba(X_vec)
    acc = accuracy_score(trainlabels, y_pred)
    f1 = f1_score(trainlabels, y_pred, average='macro')
    # print(acc)
    # print(f1)

    # take M samples with max prob    
    sorted_indices = sorted(range(len(prob)), key=lambda i : max(prob[i]) * (1 - labeled[i]), reverse=True)
    cnt = 0
    # add M samples into training set
    for j in sorted_indices[:M]:
        if labeled[j]:
            break
        X_new.append(traintexts[j])
        labeled[j] = 1
        y_new.append(y_pred[j])
    
    # train with new training set
    X_new_vec = vectorizer.fit_transform(X_new)
    model.fit(X_new_vec, y_new)
    M += K

我们每次迭代时，都取上一次迭代得到的分类器对所有的文本进行预测，取其中置信度最高的一些加入训练集，同时我们也需要保证训练集中的数据不会有重复的，因此我们开一个列表来标记所有放入训练集中的文本。当所有的文本都进入训练集时，我们结束训练。

使用 CNN 的逻辑也是差不多的，但是我们需要使用不同的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

def select(model, dataloader, device, ts, ls, labeled, trLabels):
    '''
    Select M samples and add them to training set. Return a new trainloader and accuracy.
    '''
    # ts: all texts
    # trLabels: all labels
    # labeled: a list with zeros initialy
    model.eval()
    proba = []
    traintexts = []
    trainlabels = []
    correct = 0
    predicts = []
    # predict for all texts
    with torch.no_grad():
        for inputs, labels in dataloader:
            # print(dataloader[0])
            inputs, labels = inputs.to(device), labels.to(device)
            outputs = model(inputs)

            probs = F.softmax(outputs, dim=1)
            predictedProba, predictedLabel = torch.max(probs, dim=1)

            correct += (predictedLabel == labels.squeeze()).sum().item()
            proba += predictedProba.tolist()
            predicts += predictedLabel.tolist()
            
    preLabels = [label2id[p] for p in predicts]
    test_acc = correct / len(dataloader.dataset)
    
    # take M samples
    sorted_indices = sorted(range(len(proba)), key=lambda i:proba[i]*(1-labeled[i]), reverse=True)
    
    # add into training set
    for i in sorted_indices[:M]:
        if labeled[i]:
            break
        traintexts.append(ts[i])
        trainlabels.append(preLabels[i])
        labeled[i] = 1

    # get new trainloader
    newTrainSet = DatasetMaper(traintexts, trainlabels, word2id)
    newTrainLoader = DataLoader(newTrainSet, batch_size, shuffle=True)
    return newTrainLoader, test_acc

创新点

1. 在从关键词得到文本的伪标签时，尝试将关键词作为文本向量初始化分类器，对所有文本进行伪标记，取出其中置信度较高的作为初始的训练集。但最后从结果来看，这个方法与我们提到的其他方案在效果上区别不大。
2. 在扩展训练集时，尝试在训练集增大的同时去增大加入训练集的样本个数，在一定程度上缓解了模型准确率随着自训练的进行而下降的现象。

实验结果与展示

自训练算法

在这里，我们主要调整的参数就是以上代码中的 M 和 K，也就是等差数列的首项与公差。

首先可以观察训练集。在 20ns 中，我们要实现的是一个 20 分类任务，训练集中共有 18314 个文本，文本的分布是不均匀的。而在 agnews 中，我们需要实现 4 分类任务，训练集中共有 40000 个文本，文本的分布是均匀的。

第一步，我们需要生成伪标签。使用之前提到的方案 2，对 20ns 标记结果如下：

对 agnews 标记结果如下：

我们尝试方案三，并只看在方案二中获得了伪标签的那些文本（也就是包含关键词的文本），混淆矩阵如下：

20ns：

agnews：

如果将所有文本都考虑进来，几乎所有不含关键词的文本都会被预测为某一类，这是由 Bag-of-Words/Tfidf 向量的特性决定的。对所有文本的结果如下：

20ns：

agnews：

我们还可以从生成伪标签这一步中看出，在 20ns 中包含关键词的文本是较多的，在 agnews 中包含关键词的文本是较少的。再加上两个训练集的大小不同，我们扩展训练集时当然不能对两个训练集一视同仁，而是要分别寻找合适的扩展个数与次数。

使用逻辑回归：

• 我们首先生成伪标签，具体做法是采用之前提到的方案三，也就是直接用关键词作为词向量训练分类器，然后用这个分类器去对所有的文本进行标记，在其中取出 M 个置信度较高的。
• 对 20ns，取 M = 6000，K = 6000。
• 对 agnews，取 M = 4500，K = 5500。
• Bag-of-Words模型，在20ns上准确率为 0.4866，f1_score为 0.4759（M = 4500, K = 4000）；在 agnews 上准确率为 0.7218，f1_score为 0.7126。
• Tfidf模型，在20ns上准确率为 0.5717，f1_score为0.5411（M = 6000, K = 6000）；在agnews上准确率为0.7250，f1_score为0.6965。

我们使用 Tfidf 时的混淆矩阵分别如下：

20ns：

agnews：

下面我们对结果进行分析：

• 模型在每个类上的准确率相当不均衡。以 agnews 为例，其在第 2 类上只有 26.13% 的准确率，而其他三类都达到了 80% 以上。然而在使用 Bag-of-Words 时，这个现象相对没有那么明显，如下图：

  

• 在 20 分类任务中，这种不均衡带来对准确率的影响时要比 4 分类任务要小的。

• 我们在初始利用关键词生成伪标签时，准确率分别为 61.20% 与 79.06%。整体上来看，模型最终的准确率接近这两个值，可以说明我们自训练过程的合理性。

• 我们期望在自训练过程中，准确率是能够逐步上升的，想要做到这一点就需要精确控制我们每次迭代加入训练集的数据个数。即使经过了调参，模型在最后一步增加训练集时还是出现了准确率下降的现象。笔者对此的解释是，我们终止的条件是所有数据都被加入了训练集，最后加入的数据可能预测错误的样本数相对较多。但在此之前，我们的准确率都是稳步上升的。

使用 CNN：

• 在 20ns 上准确率为 48.29%
• 在 agnews 上准确率为 69.95%

似乎 CNN 在这个任务中的表现还不如更为简单的逻辑回归。但这可能是因为我还没有花很多的时间去调参，甚至有可能是因为迭代的次数不够。

未知类别识别

这里我们使用的策略是基于置信度的拒绝。我们还是按照之前的自训练方法进行训练，将预测置信度低于某个阈值的文本预测为未知类别。

首先看这个方法在 agnews 上的结果。我们迭代 4 次停止训练，得到的准确率为 0.5908，f1_score 为 0.5816。如果我们不进行未知类别识别，准确率为 0.5711，未知类型识别带来了接近 2% 的提升。

在 20ns 上，准确率为 0.4921，f1_score 为 0.4986。如果不进行未知类别识别，准确率为 0.4838。

观察混淆矩阵，未知类别的召回率和精确率都不是很高，另外在前面提到的准确率不均衡的问题也仍然存在。总体来说，在未知类型识别任务上，此模型表现不是很好。我有一些继续优化模型的想法，但由于时间关系没有去尝试：

• 使用复杂度更高的模型，如 CNN。
• 在将数据加入训练集时，考虑将某些预测置信度低的样本标记为未知类别，一并加入训练集。
• 进一步调整阈值。如果阈值过小，会导致未知类别预测的召回率过低；如果阈值过大，会导致未知类别的精确率过低。找到一个合适的阈值是这个任务中比较困难的一个环节。

参考资料

1. 半监督学习 - 知乎 (zhihu.com)
2. Understanding Deep Learning Algorithms that Leverage Unlabeled Data, partial 1: Self-training | SAIL Blog (stanford.edu)

原理

若 \(D\) 不为完全平方数，形如 \[ x^2-Dy^2=1 \] 的方程称为为佩尔方程。

如果 \((x_1,y_1)\), \((x_2,y_2)\) 都为 \(x^2-Dy^2=1\) 的一组整数解，那么 \[ \begin{aligned} X&=x_1x_2+Dy_1y_2\\\\ Y&=x_1y_2+x_2y_1 \end{aligned} \] 也是方程的一组整数解。这可以直接代回原方程来验证。

推广：对于方程 \[ x^2-Dy^2=k \] 我们考虑与其对应的方程： \[ x^2-Dy^2=1 \] 解得该方程的解 \((r,s)\)，那么原方程的解 \((p,q)\) 形式如下： \[ (pr\pm Dqs,ps\pm qr) \]

应用

求满足 \[ \sqrt{5n^2+4}=k \]

的所有正整数解。

\[ \sqrt{5n^2+4}=k \]

对应佩尔方程 \[ x^2-5y^2=4 \] 我们要求上式中的 \(y\)。我们观察到 \[ x^2-5y^2=1 \] 的最小正整数解为 \((9,4)\)。

于是该方程中所有的解满足： \[ (x+\sqrt5y)(x-\sqrt5y)=(9^2-5\times 4^2)^n=(9+4\sqrt5)^n(9-4\sqrt5)^n=1\\ \]

\[ x_n=9x_{n-1}\pm20y_{n-1}\\\\ y_n=4x_{n-1}\pm9y_{n-1} \]

于是 \[ x_n=\dfrac{(9+4\sqrt5)^n+(9-4\sqrt5)^n}{2}\\\\ y_n=\dfrac{(9+4\sqrt5)^n-(9-4\sqrt5)^n}{2\sqrt{5}} \] 取 \(r_n=x_n,s_n=y_n\)

原方程的最小正整数解为 \((3,1)\)

于是原方程的解满足 \[ x_n=3r_n\pm 5s_n\\\\ y_n=3s_n\pm r_n \] 于是我们有 \[ y_n=3\dfrac{(9+4\sqrt5)^n+(9-4\sqrt5)^n}{2}+\dfrac{(9+4\sqrt5)^n-(9-4\sqrt5)^n}{2\sqrt{5}} \]

不想化简这个式子，但这大概是猜不出这道题最简单的解法的情况下最好的做法了。

不过可以观察得到，序列 \(y_n\) 为 \(\{1,3,8,21,...\}\)，对比斐波那契数列 \(\{1,1,2,3,5,8,13, 21\}\)，发现 \(y_n\) 就是斐波那契数列的偶数项，这题就做完了。

知识图谱与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

从最长公共子序列开始

1. 最长公共子序列

字符串 \(s\) 的子序列是从中取出若干元素而不改变其相对位置的序列，求 \(A\) 和 \(B\) 的最长子序列长度。

设f[i][j]是只考虑 \(A\) 前i个元素，\(B\) 前j个元素的最长公共子序列的长度，则

1. 若 \(A[i]=B[j]\)，可以接到公共子序列末尾；
2. 否则跳过 \(A[i]\) 或 \(B[j]\)。

\[ f[i][j]=\begin{cases} f[i-1][j-1]+1,\ A[i]=B[j],\\\\ max(f[i-1][j], f[i][j-1]),\ A[i]\neq B[j]. \end{cases} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

char a[maxn];
char b[maxn];
int dp[maxn][maxn];
int lcs(){
    int n = strlen(a);
    int m = strlen(b);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i] == b[j]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
}

2. 最长不下降子序列

\(O(n^2)\) 做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int lis(){
    dp[0] = 1;
    int ans = 1;
    for(int i = 1; i < n; i++){
        dp[i] = 1;
        for(int j = 0; j < i; j++){
            if(a[j] <= a[i]){
                dp[i] = std::max(dp[i], dp[j] + 1);
                ans = max(ans, dp[i]);
            }
        }
    }
    return ans;
}

\(O(n\log n)\) 做法：

1
2
3
4
5
6
7
8

memset(dp, 0x1f, sizeof dp);
mx = dp[0];
for (int i = 0; i < n; ++i) {
  *std::upper_bound(dp, dp + n, a[i]) = a[i];
}
ans = 0;
while (dp[ans] != mx) ++ans;

一道二分

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be \(O(\log (m+n))\).

1
2
3
4
5
6

typedef Comparable int;
Comparable find_median(const vector<Comparable> &l1, const vector<Comparable> &l2)
/*
Pre:  The ordered lists l1,l2 are not all empty.
Post: The median of the two lists combined in order is returned. If the size of the merged list is even, then the first of the two medians is returned. For exmaple, l1 =(1,2), l2=(1,3,4,5), then 2 is returned.
*/

Solution

find the \(k\)th min number, where: \[ k = \begin{cases} \dfrac{m+n}{2},\ \text{when}\ m+n\ \text{is even},\\\\ \dfrac{m+n+1}{2},\ \text{when}\ m+n\ \text{is odd}. \end{cases} \] To find the number, compare \(A[k/2-1]\) and \(B[k/2-1]\):

• if \(A[k/2-1] \leq B[k/2-1]\), remove \(A[0:k/2-1]\),
• if \(A[k/2-1] > B[k/2-1]\), remove \(B[0:k/2-1]\).

and some cases:

• if \(A[k/2-1]\) or \(B[k/2-1]\) is out of bound, choose the last element of the array.
• if an array is empty, find the kth min number in the other.
• if \(k=1\), return \(\min(A[0], B[0])\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

int getK(const vector<Comparable> &l1, const vector<Comparable> &l2, int k){
    int i1 = 0, i2 = 0;
    while(1){
        if(i1 == l1.size()){
            return l2[i2 + k - 1];
        }
        if(i2 == l2.size()){
            return l1[i1 + k - 1];
        }
        if(k == 1){
            return min(l1[i1], l2[i2]);
        }
        int p1 = min(i1 + k / 2 - 1, (int)l1.size() - 1);
        int p2 = min(i2 + k / 2 - 1, (int)l2.size() - 1);
        if(l1[p1] <= l2[p2]){
            k -= p1 - i1 + 1;
            i1 = p1 + 1;
        }
        else{
            k -= p2 - i2 + 1;
            i2 = p2 + 1;
        }
    }
}

Comparable find_median(const vector<Comparable> &l1, const vector<Comparable> &l2){
    int l = l1.size() + l2.size();
    if(l%2 == 1){
        return getK(l1, l2, (l + 1) / 2);
    }
    else{
        return getK(l1, l2, l / 2);
    }
}