机器学习和生物信息学实验室联盟

标题: 网络数据的无监督特征选择:一种生成式观点 [打印本页]

作者: sndnyangd 时间: 2016-7-4 18:53
标题: 网络数据的无监督特征选择:一种生成式观点
本帖最后由 sndnyangd 于 2016-7-4 18:54 编辑

论文标题： Unsupervised Feature Selection on Networks: A Generative View

作者： Xiaokai Wei∗, Bokai Cao∗ and Philip S. Yu

论文链接：链接
我在博客上的总结：博客总结

摘要

现在的网络数据（社交网络或信息网络），不单纯是个图Graph，每个点还可能有若干个特性、属性。而那些对网络数据进行机器学习的任务，比如社区发现和链接预测，如果能够利用上这些附加信息，想必准确度上能得到一定提升。但这些点的属性或特征往往是高维度数据，对效率上影响比较大。

所以，本文的目标就两个zhi：

降维

也就是对点的特征进行选取 (feature selection)

作者们发现前人工作中的主要有以下两个问题：

1. 选取特征时没考虑数据的网络、图特性（存在边、连接）。
2. 网络数据没有标准的标签（label)，一般不适合监督学习的方法。但却用聚类等方法强行给标签，强行使用监督学习，准确性很差。

所以本文提出了一个特征选取方法：

1. 非监督的
2. 用生成模型（generative model)来整合连接和内容信息（即边和属性）

---------------------------------------------------------------------------------分隔图片怎么找不到了？
导论

和摘要差不多，重复的不提。

主要思想：

   从点的所有特征中，选取重要的、关键的特征，记为预特征（oracle features，叫圣特征、神谕特征都不好吧）

1. 对于边来说

边不是边~~~而是由两个点在预特征上的亲密度（就相似度）来决定两个点是不是该相连。

首先，非预特征对边没有影响。就像自然语言处理里肯定要把停用词过滤掉，这种数据没有作用。
其次，想说什么来着？忘了。

2. 对于点的属性特征来说

首先，很多属性也是没用、没影响的，只占空间不干活。
其次，还有很多的属性或特征本质上是重复的。就像线性方程组消元，发现一些方程可能是另外方程的线性组合。

所以，原本比较大的点属性集合就可以用比较小的预特征集合来代替（还可以存在映射关系）

结论：
   可以用点的预特征集合来同时表示连接和内容信息。

---------------------------------------------------------------------------------分隔图片怎么找不到了？

于是我们就得到了一个模型，类似于线性回归的那个线性方程的模型，后面会写到模型具体的形式
然后，再去定义这个模型对应的：
1. 策略。即损失函数，要优化的目标。
2. 算法。如何进行优化。

*模型、策略、算法，机器学习三要素，《统计学习方法》的描述方法

---------------------------------------------------------------------------------分隔图片怎么找不到了？

正文
定义

Attributed Network 属性网络：G = (V; E; X)， X是n个点的D维属性、特征向量

s 是D维01向量， 1代表该位置是预特征， 0则否。
diag(s) 则是把s 拉成对角矩阵，后面计算用得到--光点积不够用

目标是求出预特征集合

模型分为两部分：

1.  对连接信息建模

如之前所说：

probability of a link is determined by the oracle affinity between two nodes

所以要定义 Oracle Affinity

Oracle Affinity
dot product of oracle features of two nodes, 如下：

$$
a_{ij}=x^T_i diag(s) x_j
$$

再用某个转换函数F_g（比如sigmoid）将上面的 $a_{ij}$转成个概率值

最后，概率值再用伯努利分布来决定边是生成还是不生成，如下：
$$
p_{ij}=F_g(a_{ij}) \\
E_{ij} \sim Bernoulli(p_{ij})
$$

所以，得到整个图的概率定义，在给定预特征 oracle features时，整个网络的概率为：

$$
P(G|s) = \prod_{(i,j)\in E}p_{ij} \cdot \prod_{(i,j)\notin E}(1-p_{ij})
$$

最终式

把$a_{ij},F_g$代入上式，求个-log, 化简得：

$\cal{L_G}=xxxx$

公式太长，省略~~~

---------------------------------------------------------------------------------分隔图片怎么找不到了？

2. 对内容建模
关键就是得到一个预特征向量和原特征向量的映射关系。

所以可以是：（也可以使用和边相似的建模）

$$
\mu_i = F_c(diag(s)x_i) \\
x_i \sim \cal{N}(\mu_i, \sigma^2\bf{I}_D)
$$

为简便， Fc就等于左乘个 D行D列的投影矩阵 $\bf{W}$

使用以上模型的话，那对内容的最大似然值优化其实也就等效于最小化误差平方和，再加个控制项得：

$$
\cal{L}_C=||X^Tdiag(s)W - X^T||^2_F + \beta||W||^2_F
$$

---------------------------------------------------------------------------------分隔图片怎么找不到了？

3. 边和内容二者结合
就是

$$
\min \limits_{s,b,W} \cal{L}_G + \cal{L}_C
$$

限制条件有， s向量里取值0或1，长度D，向量和=d

---------------------------------------------------------------------------------分隔图片怎么找不到了？

优化
出于优化难度，改写优化式：

$$
\begin{eqnarray}
& \min \limits_{s,b,W} & \cal{L}_G + \cal{L}_C + \lambda||s||_1 \\
& s.t. & 0 \leq s_p \leq 1, \forall p=1,...,D
\end{eqnarray}
$$

优化过程并不特殊，貌似和SVM的优化过程SMO是一样的。

先固定W，优化方程的s和b

再固定s和b，优化方程的W

偏导方程就不写了。

总结
本文定义、概念描述准确，逻辑清晰，没有太复杂的东西。
总结不太会写，还不敢评价论文质量。

不过本文的实验部分写得比较简略~~~别的很多论文都3、5页的。本文将将一页出头。

欢迎光临机器学习和生物信息学实验室联盟 (http://123.57.240.48/)