DeepFM

wide & deep

Wide & Deep Learning for Recommender Systems. 2016

wide指的是形如LR的这种特征较为稀疏的比较“宽”的模型,这类模型的特点是计算简单、可解释性优秀(有比较好的记忆能力);deep指的是各种NN类型的,将“宽”的输入转化为embedding,然后对embedding做处理,优点是不需要手工处理特征,且有较强的泛化能力

wide&deep模型就是要将wide和deep联合起来,取各自的长处,其图示如下:

wide&deep model

模型的输出为:

实现中,wide部分可以考虑人工加入组合特征,以提升模型效果。

两部分模型需要联合在一起进行训练

  • wide部分用FTRL进行优化,辅以L1正则项
  • deep部分用了adagrad,当然也可以用adam这些方法

DeepFM

DeepFM: A Factorization-Machine based Neural Network for CTR Prediction. 2017

在推荐系统中,轻量模型一般用FM而不用LR,因为FM中考虑了特征交叉且对稀疏数据比较友好。DeepFM就从这个角度出发,将wide&deep模型中的LR换成了FM,其主要结构如下图

deepfm model

可以看到FM有两部分,加法是一阶特征的加权求和,乘法是利用隐向量内积计算出来的组合特征的部分;

deep网络部分则是使用特征的embedding作为输入,对于每个field,将其转化为一个dense embedding(这里搞个field的概念是防止映射矩阵太大,按field进行映射可以有效降低参数数量),然后将所有的embedding作为深度网络的输入。那么embedding怎么来的呢,embedding是由原始特征通过以FM的隐向量为参数的映射得到,如下图所示。

deepfm embedding

多说一句,数值类特征直接使用数值,非数值类特征转成one-hot。模型输出公示如下:

最后输出的结果可以作为ctr预估的结果。

因为FM、DEEP两个部分共享参数,也就是特征的隐向量,所以这部分可以一起训练。

实际应用中,这种混合模型可能会出现问题,因为两边的训练速度不一致,所以收敛速度不一致。应用中可能需要调整两边的学习率。


分享到

Monotonous Sequence

单调序列结构,这里不仅仅指的是数组,指的是用于加速检索结果的线性数据结构(vector、队列、栈等)。
用例题解释~

Minimum Number in Sliding Window

有一个长为 n 的序列 nums,以及一个大小为 k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最小值

这里介绍一个O(n)复杂度的算法。

我们可以把关键的数据存储起来,利用第 i 个位置的信息计算第 i+1 位置的任务。方法如下:

  • 建立一个队列,这个队列需要满足:
    • 新进入队列的数要大于等于队尾的数字,也就是说任何时刻队列都是单调递增
    • 所以如果当前数小于等于队尾的数据,队尾的数据就不可能是窗口最小值。【等于是考虑了位置,位置约靠后越好】
  • 对于当前的位置,如果大于k,需要将队列中不满足窗口位置的从队头去掉
    • 所以队列中存储的应该是下标志,而不是元素本身
  • 然后将队尾大于当前数字的元素pop出去
  • 这时候队头的元素就是当前窗口中的最小值

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// #include <deque>

vector<int> function(const vector<int>& nums, int k) {
vector<int> ret;
if (nums.size() == 0 || k < 1) {
return ret;
}
deque<int> qu; // monotonous queue
for (int i = 0; i < nums.size(); ++i) {
if (qu.size() > 0 && i - qu.front() == k) { // window size
qu.pop_front();
}
while(qu.size() > 0) {
// 队尾大于当前数字的元素pop出去, 保持递增
if (nums[i] <= nums[qu.back()]) {
qu.pop_back();
}
}
qu.push_back(i); // 入队
ret.push_back(nums[qu.front()]); // 对头是最小值
}
return ret;
}

时间复杂度:因为每个元素入队、出队只有一次,所以整体的复杂度是O(N).

右侧大数

有一个长为 n 的整数序列 nums,对于每个元素找到这个元素右侧第一个大于它的值(不存在就-1),返回这个值序列

如果当前元素小于下一个,那么直接就有结果了。如果不是,将当前元素的位置存到栈里面,所以在搜索到新位置时也需要看栈顶元素。所以整体的步骤如下:

  • 初始化结果数组ret,新建一个栈stack
  • 对于位置i
    • while(nums[i] > nums[stack.top()]):
      • 更新stack.top()位置的值: ret[stack.top()] < nums[i]
      • 栈顶pop:这能保证堆栈从上到下是递增的(栈顶最小)
      • i入栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// #include<stack>

vector<int> function(const vector<int>& nums) {
vector<int> ret(nums.size(), -1);
if (nums.size() < 2) {
return ret;
}
stack<int> st;
st.push(nums[0])
for (int i = 1; i < nums.size(); ++i) {
while(!st.empty() && nums[st.top()] < nums[i]) {
ret[st.top()] = nums[i];
st.pop();
}
}
return ret;
}

最长递增子序列

有一个长为 n 的整数序列 nums,找到这个序列中最长的递增序列,返回长度

DP思路的复杂度为O(N^2),下面介绍一个复杂度为O(N*logN)的算法

维护一个数组vec,位置i的元素表示长度为i的递增子序列最后一个元素值的最小值,也就是子序列最大值中的最小值。这样一个数组有一个特点:数组的元素是递增的,证明就反证法就好

对于nums中的一个新元素num,我们可以找到vec中m的位置k满足

  • vec[k] < num <= vec[k+1],表示最优子序列中,长度k子序列的最大值小于num,但是长度k+1子序列的最大值不小于num,所以我们更新k+1子序列的最大值为num,但是k+2及以后的不行
  • 上述操作可以线性搜索,但是因为vec数组是有序的,所以可以通过二分搜索的思想来做
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int function(const vector<int>& nums) {
if (nums.size() < 2) {
return nums.size();
}
vector<int> vec;
for (int i = 0; i < nums.size(); ++i) {
// vec[k] < num <= vec[k+1],找到位置
auto idx = upper_bound(vec.begin(), vec.end(), nums[i]);
if (idx == vec.end()) {
vec.push_back(nums[i]);
} else {
*idx = nums[i];
}
}
return vec.size();
}

Largest Rectangle in Histogram

Largest Rectangle in Histogram

分享到

Factorization Machines

FM

Factorization Machines. 2010

FM(Factorization Machine)是推荐系统常用典算法之一

LR(或者线性回归)是个简单的线性模型,可解释性好。LR假设所有的特征都是独立存在的,所以一个其明显的缺陷是不能的考虑组合特征。SVM的核函数(多项式函数$K(x_i,x_j)=(\gamma x_i^Tx_j+d)^n$可以考虑到特征组合的情况),但是

LR也可以显示地加入组合特征,会导致要学习的参数数量增大。特征多的时候,总有部分特征是比较稀疏的,这时候组合特征就更稀疏了,在有限训练数据的条件下,组合特征的参数很可能学习得不充分。

FM解决了这个问题,下面介绍这个算法:

形式:

这里,我们给每个特征一个隐向量(长度为$k<n$),交叉特征的权重由对应特征的隐向量内积表示,这样我们需要学习的参数就是$w,v$了,因为交叉特征的权重不再独立,参数学习也简单了许多,泛化能力也变强了(比如$x_i,x_k$的组合在训练数据这没出现过,依旧可以表示其系数$v_i^Tv_k$,如果赋予组合特征独立的参数,且就训练数据中不存在这样的的组合,那么其参数就学不到了)。

关于特征处理:

  • 数值特征:对应一个隐向量
  • 非数值特征:换成one-hot形式,对应多个隐向量

公式(1)的计算复杂度是比LR要高的,为平方复杂度,考虑隐向量的长度,复杂度为O(kn^2),可以通过变换降低其复杂度:

复杂度降为O(kn)。

训练就采用SGD即可,训练和预测都可以在线性时间完成。

FM中的隐向量可以看成是深度模型中的embedding,也就是每个特征的embedding,可以和NN结合构建深层网络。

FFM

Field-aware Factorization Machine. 2014

FFM(Field-aware Factorization Machine)是FM的进阶,通过引入field的概念,FFM把相同性质的特征归于同一个field。比如商品的末级品类编码生成了550个特征,这550个特征都是说明商品所属的品类,因此它们也可以放到同一个field中。

实现上,每一维特征$xi$,针对其它特征的每一种field$f_j$,都会学习一个隐向量$v_{i,fj}$,其中$f_j$是$j$个特征的field。因此,隐向量不仅与特征相关,也与field相关!算法形式如下:

从上式可以看出来,较FM而言FFM参数数量变大,训练也更加耗时。

FFM将问题定义为分类问题,使用的是logistic loss(label为1、-1),同时加入了正则项,训练优化目标为:

部分开源实现的FFM忽略了一次项,只保留了二次项。


分享到

Python Functions

常用的python函数

sort

python的sort函数有两种

L.sort

原地排序

1
2
l=[3, 2, 4, 1, 5]
l.sort(comp, key, reverse=False)

其中

  • comp是列表元素的比较函数
  • key指定排序的键值,可以是一个函数。指定key的方法比comp快
  • dict没有这个函数,需要通过items()方法转换为list才行
sorted

返回一个排好序的列表,这是稳定排序方法

1
2
3
new_list = sorted(iterable, cmp=None, key=None, reverse=False)

sorted(dict.items(), key=lambda d: d[0], reverse=True)

其中

  • iterable是可迭代的类型,比如list,dict等

python3中,去掉了自定义比较函数cmp,这时可以将比较函数转化为key

1
sorted(iterable, cmp_to_key(my_comp))

enumerate

enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列,同时列出数据和数据下标,一般用在 for 循环当中

定义
1
enumerate(sequence, [start=0])
  • sequence — 一个序列、迭代器或其他支持迭代对象。
  • start — 下标起始位置
示例
1
2
3
4
5
6
7
8
9
seasons = ['Spring', 'Summer', 'Fall', 'Winter']
list(enumerate(seasons))
> [(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]

list(enumerate(seasons, start=1)) # 下标从1开始
> [(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]

for i, season in enumerate(seasons):
print(i, season)

groupby

itertools.groupby函数用于对按照key排好序多字段列表进行分组,返回一个分组后的key和一个迭代器对象,迭代器对象包含对应key值的所有对象

定义
1
groupby(sequence, key=itemgetter())
  • sequence是列表:其元素可以是列表、或者字典
  • key是分组的key,列表需要指示是哪个,dict需要指出是哪个属性。可以用itemgetter指定
示例
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
from operator import itemgetter
from itertools import groupby

x = [[1, 'b', 3], [2, 'a', 4], [1, 'b', 5]]
# sort first
x.sort(key=itemgetter(1))
for key, iter in groupby(x, itemgetter(1)):
for lst in iter:
print(key, lst)

> ('a', [2, 'a', 4])
('b', [1, 'b', 3])
('b', [1, 'b', 5])


# apply for dict
y = [{'a': 'm', 'b': 2}, {'a': 'n', 'b': 1}, {'a': 'm', 'b': 3}]
y.sort(key=itemgetter('a'))
for key, iter in groupby(y, itemgetter('a')):
for dict in iter:
print(key, dict)

> ('m', {'a': 'm', 'b': 2})
('m', {'a': 'm', 'b': 3})
('n', {'a': 'n', 'b': 1})
分享到

Bounds in Binary Search

二叉搜索的理念比较简单,不赘述,这里说的是在循环处理、边界条件上的内容。

  • 循环条件:包含的是有必要继续进行搜索的区间,如果没有必要继续计算了,把循环条件放开
  • 边界处理:初始的范围应该覆盖所有可能的取值
  • 边界缩进:判断时,把可能找到最终结果的条件放在一起;缩进边界的时候要保证可能的结果依旧在新的边界范围中,也就是考虑要不要多移一位

naive

先从原始的二叉搜素开始;

  • 边界范围:就是数组的序号边界
  • 循环条件:算法需要精确到单个长度的区间(l=r),即l<=r,因为查询目标可能不存在
  • 边界缩进:比较明显
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int binarySearch(int[] nums, int l, int r, int target) {
    while (l <= r) {//[l....r]闭区间查询,l > r 时候形成不了闭区间了,说明没有找到
    int mid = l + (r - l) / 2;
    if (nums[mid] == target) {//找到
    return mid;
    } else if (nums[mid]target){
    //说明中间位置太大了,所以要在[l.....mid-1]中继续查找
    r = mid - 1;
    } else {
    //说明中间位置太小了,所以要在[mid+1 ....r]中继续查找
    l = mid + 1;
    }
    }
    return -1; //跳出循环了没有找到 返回-1
    }

upper bound和lower bound

upper bound是要找有序序列中第一个大于target的值,而lower bound是要找有序序列中第一个不小于target的值。

在STL中,基本定义如下

1
2
Iterator lower_bound(Iterator first, ForwardIterator last, const T& val, Compare comp);
Iterator upper_bound(Iterator first, ForwardIterator last, const T& val, Compare comp);

其中,右边界是序列最后一个的下一个位置,因为target可能比最后一个元素还大

upper bound
  • 边界范围:因为target可能比最后一个元素还大,所以合理的边界是[0, n],假设n是序列长度
  • 循环条件:并不要求元素一定要存在,不需要判断这个元素是否存在,就算是不存在,我们只需要知道“假设target存在,它应该在的位置”,当l=r时候(最终肯定有l=r),[l,r]正好能够得到一个唯一的位置,就是我们需要的结果,所以满足l<r让循环一直执行即可
  • 边界缩进:当中间值大于target,则当前这个中间值可能就是结果,所以r变化时要保留mid;中间值小于等于target的情况则可以放在一起,因为都没可能是结果,l变化时不用保留mid值
1
2
3
4
5
6
7
8
9
10
11
int upperBound(int[] num, int l, int r,int target) {
while (l < r) {
int mid = l + (r - l) / 2;
if (num[mid] > target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
lower bound
  • 边界范围:因为target可能比最后一个元素还大,所以合理的边界是[0, n],假设n是序列长度
  • 循环条件:同upper bound
  • 边界缩进:当中间值大于等于target(大于等于都可能是最终结果),则当前这个中间值可能就是结果,所以r变化时要保留mid;中间值小于target的情况下,因为都没可能是结果,所以l变化时不用保留mid值
1
2
3
4
5
6
7
8
9
10
11
int lowerBound(int[] nums, int l, int r, int target) {
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
分享到

BM25

BM25是一种经典的搜索基础相关性算法,用以计算query和doc的相关性

对于用户query $q$和doc $d$,BM25操作如下:

  • 对$q$分词,得到分词token:$t_1, t_2, …, t_k$
  • 令$R(t_i,d)$是$t_i, d$之间的相关性,$w_i$是token$t_i$的权重

则基于BM25的相关性分数为:

首先看一下$w_i$,其计算方式可以是多种多样,一般是基于idf的思想

其中$N(t_i)$表示包含$t_i$的文档数量,$N$表示所有文档的数量。

再看$R(t_i,d)$,计算方法如下:

其中$f_d(t_i)$表示$t_i$在$d$中出现的频率,$f_q(t_i)$表示$t_i$在$q$中的频率,$l_d$表示文档$d$的长度,$l_{avg}$表示文档集合的平均长度;$k_1,k_2,d$则是可以调节的参数。

参数$b$用来控制文档长度敏感度,一般有$f_q(t_i)=1$,如果取$k_2=0$则有$R(t_i,d)=(k_1+1)\frac{f_d(t_i)}{f_d(t_i)+K}$。通常会设置


分享到

Similarity and Relativity Metrics

相似度度量出现在很多机器学习应用中,比如query-query相似度、排序等等,今天介绍一下常用的几个相似度衡量标准

闵可夫斯基距离

定义如下

根据p值的不同,可以是

  • $p=1$: $d=\sum_i|A_i-B_i|$,曼哈顿距离
  • $p=2$: $d=\sqrt{\sum_i|A_i-B_i|^2}$,欧几里得距离
  • $p\to\infty$: $d=\max_i|A_i-B_i|$,切比雪夫距离

汉明距离

对比对象二进制表示的差异,即二进制表示对应位不同的个数

编辑距离

允许增、删、改操作的序列距离,可用动态规划的方式求解,动态方程为

余弦相似度

Jaccard系数

给定两个集合$A,B$,Jaccard系数定义为

也就是集合的交集大小比上集合的并集大小。Jaccard系数的取值范围是[0, 1],两个集合都是空集,Jaccard系数=1。

与Jaccard系数对应的是Jaccard距离,其计算方式是: Jaccard距离=1-Jaccard系数,距离越大,样本相似度越低

pearson系数

两个连续变量$(X,Y)$的pearson相关性系数$(Px,y)$定义如下:

pearson系数取值总是在-1.0到1.0之间,越靠近0表示相关性越低,数值的正负表示正相关还是负相关.

注意公示1可以发现,pearson相关性系数也就是把数据先正规化到均值为0、方差为1,然后求这两组数据的cosine夹角


分享到

Entropy and Related Metrics

首先说香农信息量(也叫自信息self-information),其定义为

熵的本质是香农信息量的期望,即

表示混乱程度,熵越大越混乱。


交叉熵

现有关于样本集的2个概率分布$p$和$q$,其中$p$为真实分布,$q$非真实分布。用分布$q$来表示来自分布$p$的平均编码长度的期望(即平均编码长度)为:

其中,$H(p,q)$就叫做交叉熵

举个例子,有集合$S=(A,B,C,D)$,真实分布$p=(1/2,1/2,0,0)$,即$A,B$出现的概率都是1/2。现在用分布$q$来编码分布$p$,则有:

  • 假设$q=(1/2,1/2,0,0)$,即真实分布,根据上式计算$H(p,q)=1$,即只需要1位编码就可以识别$A,B$
  • 假设$q=(1/4,1/4,1/4,1/4)$,计算得$H(p,q)=2$,则需要2位编码就可以识别集合$S=(A,B,C,D)$

非真实分布编码所需长度大于真实分布编码所需长度,即存在

当且仅当$p=q$时等号成立。所以交叉熵作为损失函数时,可以表示两个分布之间的相似性,越相似交叉熵越小。


KL散度(相对熵)

定义:设真实分布为$p$,由分布$q$得到的平均编码长度比由$p$得到的平均编码长度多出的bit数称为“相对熵”,写作

相对熵也叫KL散度(Kullback–Leibler divergence),表示2个函数或概率分布的差异性,差异越大则相对熵越大,相同时KL散度为0。注意,KL散度是非对称的。

TD-IDF算法就可以理解为相对熵的应用:词频在整个语料库的分布与词频在具体文档中分布($\log \frac{|N|}{|N_t|}$)之间的差异性


JS散度

KL散度的一种变形,定义如下:

JS散度有如下特性:

  • 对称性
  • 值域范围是[0,1],相同则是0,相反为1
分享到

TextGCN

GNN在NLP上的应用

Text GCN

Graph Convolutional Networks for Text Classification. AAAI. 2019

给定文章若干,目标是基于GCN搞一个分类器。

图的构建方法,邻接矩阵为

其中PMI是point-wise mutual information,计算方式如下

概率的计算可以使用滑动窗口统计出现次数,分母是corpus中所有的滑动窗口数量。PMI反应了节点之间的关系,负数表示相关度低,所以只把PMI>0的节点添加边。这里,doc和doc之间没有边相连,但是在图上通过一跳就可以达到,所以网络层数应该大于1,论文的实验也说明了这点,layer=2明显好于1.

以这个图为基础,构建一个2层的GCN,最后的结果经过softmax做分类

损失函数就用交叉熵即可。

试验结果显示,TextGCN表现优秀,但是在短文本和情感分析等这种对word-order比较敏感或者可建模的边数量较少的任务上不够好

本方法还有一个固然的缺陷:无法处理未见过的文档,因为不在图里

分享到

Graph Convolutional Networks

GCN是GNN中比较常用的一种网络结构,其主要思想是将卷积操作迁移到图结构上以提取图的结构特征。

研究GCN的原因如下:

  • 图是一种定义拓扑关系的广义结构,可以表达丰富的结构特征
  • CNN的方法不能对图做卷积,图中每个顶点的相邻顶点数目都可能不同,无法用一个同样尺寸的卷积核来进行卷积运算

网络结构

图上的卷积操作大体上有如下两种思路

spatial domain

这里是将卷积做了一个概念上的泛化。这里有两个概念

  • aggregation:用邻居的特征更新当前节点下一层的hidden state
  • readout
    • 单个节点的表征
    • 聚合所有节点的特征,得到整个图的表征

根据aggregation和readout的不同,就有不同的算法

NN4G(Neural Networks for Graph. 2009)

aggregation:节点$v$的第$k$隐层节点值为

其中,$x_v$为节点$v$的原始特征。

readout:将每一层的hidden state求均值,然后加权求和作为整个图的表征

DCNN(Diffusion-Convolution Neural Network. 2016)

DCNN将迭代看成是图上的扩散过程,每一层相当于在上一层的基础上再进行一跳。
aggregation:

其中,$MEAN(d(v,.)=k)$表示与点$v$距离为$k$的节点的原始特征$x$)的均值,这里注意不是用$k-1$层的hidden state,而是原始特征。

readout:将每一层的hidden state拼成矩阵,所有的矩阵就是图的表征;单个节点对应的所有hidden state拼一起就是单个节点的表征

DGC(Diffusion Graph Convolution)

整体上与DCNN类似,唯一不同的是在readout阶段,表征不再用各个hidden state拼接的结果,而是用相加的结果

MoNet(Mixture Model Network. 2017)

aggregation:

  • 考虑了邻居的权重,不再使用邻居的简单相加,而是使用加权求和
  • 节点$x,y$的边权重定义为:$u(x,y)=(\frac{1}{\sqrt{\deg(x)}},\frac{1}{\sqrt{\deg(y)}})^T$,其中$\deg()$表示节点的度函数

readout:-

GAT(Graph Attention Network. 2017)

MoNet将权重写死了,GAT通过attention机制计算出邻居节点的权重。这是较为常用的一种方法

GIN(Graph Isomorphism Network. How Powerful are Graph Neural Networks?. 2019)

主要思想如下

  • aggregation的时候不要使用mean或者max pooling操作,而是使用sum。因为max、mean操作会丢失掉一些图的结构信息,比如3个2和4个2的均值、最大值都是2,但是和不一样
  • aggregation按如下公示计算
spectrum domain

结论:

信号在时域上的卷积等价于其在频域上的乘法

所以,这种方法的思想是将图信号上的卷积操作转换到频域上的乘法操作,最后再逆转回去

谱图理论(vertex domain -> spectral domain)

给定包含$N$个节点的图,定义$A,D$分别为图的邻接矩阵和度矩阵。
定义图上的拉普拉斯矩阵:$L=D-A$,对称,半正定。有如下特性

  • 对称矩阵一定N个线性无关的特征向量
  • 半正定矩阵的特征值一定非负
  • 对阵矩阵的特征向量相互正交

对这个矩阵做SVD分解得到$L=U\Lambda U^T$(这里$U^T=U^{-1}$且$UU^T=E$),其中$\Lambda=diag(\lambda_0,…,\lambda_{N-1})$,$U=[u_0,…,u_{N-1}]$为包含正交向量(列向量)的特征矩阵。$\lambda_l$可以看成频率概念,而$u_l$则是对应的基(basis)。[这里频率概念的解释可以参考文献1中的视频解释]

图傅立叶变换:给定信号$x$,经过图傅立叶变换后得到(这里其实和PCA很像了)

其中$U$是上述的特征矩阵。图傅立叶逆变换则如下:

有了经过图傅立叶变换的信号$\hat{x}$后,我们可以在频域上对信号做一个变换(滤波),简单的做法是做对应位相乘,引入参数$\theta$。为了表述统一,令$g_{\theta}(\Lambda)$为对角矩阵的对角$\theta$(参数写成$\Lambda$只是为了和频率对上)。所以有

再将频域信号转换到时域(或者说vertex domain),有

所以,要学$g_{\theta}()$函数。这个函数的选取需要考虑两个方面

  • 参数规模:上述推导的参数规模是$N$,不希望这么大
  • 局部视野特性:我们不希望当前节点能看到所有节点,所以函数不能分解成无限多项(因为矩阵$L$的$N$次方表示当前节点可以看到任何连通节点的信息)

ChebNet

优点:

  • 参数规模:O(K)
  • 局部视野特性:K-localized
    缺陷:
  • 复杂度问题:矩阵乘法复杂度为O(N^2),K次方下计算量大

根据Chebyshev多项式,满足

其中$\hat{\Lambda}=\frac{2\Lambda}{\lambda_{max}}-I, \hat{\lambda}\in[-1, 1]$。这个公式可以利用推倒结构,以

代替原来的计算方式,降低计算复杂度。
每组$\theta$等价于一个filter,可以有多个filter,当作多个特征提取工具。


GCN是在公示1的基础上再做简化

  • 令K=1,即只考虑两项
  • $\hat{L}\approx L-I$,如果$L$是normalized laplacian,有$\lambda_{max} \approx2$,又$\hat{L}=\frac{2L}{\lambda_{max}}-I$
  • 根据Symmetric normalized Laplacian定义有$L=I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$
  • 再次简化模型,令:$\theta=\theta’_0=-\theta’_1$
    • $y=\theta(I+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x$
  • 再次trick,$I+D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \to \hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}$
    • $\hat{A}=A+I$
    • $\hat{D}_{ii}=\sum_j\hat{A}_{ij}$,参考原paper
    • $H^{(l+1)}=\sigma(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H^{(l)}W^{(l)})$,这里$W$对应$\theta$

上面重写一下(邻域要包含自己):


[1]. https://www.bilibili.com/video/BV1G54y1971S?p=2

[2]. SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

分享到