搭建L2TP/IPSec VPN

之前曾经介绍过SoftEthern VPN的搭建,最近换了新的VPS,需要重新搭建VPN,由于除了iOS以外的其他平台都可以用ShadowSocks的梯子,就想搭建一个最简单的无需安装第三方App的VPN给iOS使用。想到系统自带的VPN可以连接L2TP over IPSec,就决定搭一个L2TP的VPN。

由于新VPS装的是CentOS 6,所以CentOS 7风格的命令就写在注释里了。

安装

先安装openswanxl2tpd

yum install openswan xl2tpd

如果没有ppp也要安装。

配置IPSec

/etc/ipsec.d中新建一个vpn.conf文件,内容如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
conn L2TP-PSK-NAT
rightsubnet=vhost:%priv
also=L2TP-PSK-noNAT
conn L2TP-PSK-noNAT
authby=secret
pfs=no
auto=add
keyingtries=3
rekey=no
ikelifetime=8h
keylife=1h
type=transport
left=YOUR_PUBLIC_IP_ADDRESS
leftprotoport=17/1701
right=%any
rightprotoport=17/%any

其中left的值改为VPS的公网IP。

再新建一个vpn.secrets文件,里面写一行:

1
YOUR_PUBLIC_IP_ADDRESS %any: PSK "YOUR_PRE_SHARED_KEY"

前面还是公网IP,后面引号里面是自己设置的预共享密钥。

更改系统参数

编辑/etc/sysctl.conf文件,修改或添加成以下配置:

1
2
3
4
5
6
7
8
9
10
net.ipv4.ip_forward = 1
net.ipv4.conf.default.rp_filter = 0
net.ipv4.conf.all.send_redirects = 0
net.ipv4.conf.default.send_redirects = 0
net.ipv4.conf.all.log_martians = 0
net.ipv4.conf.default.log_martians = 0
net.ipv4.conf.default.accept_source_route = 0
net.ipv4.conf.all.accept_redirects = 0
net.ipv4.conf.default.accept_redirects = 0
net.ipv4.icmp_ignore_bogus_error_responses = 1

sysctl -p命令使更改生效。

然后用以下脚本将/proc/sys/net/ipv4/conf下配置的值都改为0

1
2
3
4
5
for each in /proc/sys/net/ipv4/conf/*
do
echo 0 > $each/accept_redirects
echo 0 > $each/send_redirects
done

启动IPSec

启动IPSec并加入开机启动:

service ipsec start        #systemctl start ipsec
chkconfig ipsec on        #systemctl enable ipsec

然后用ipsec verify检查一下是否配置正确,正常如下:

Version check and ipsec on-path                           [OK]
Libreswan 3.15 (netkey) on 4.12.9-1.el6.elrepo.x86_64
Checking for IPsec support in kernel                      [OK]
 NETKEY: Testing XFRM related proc values
     ICMP default/send_redirects                          [OK]
     ICMP default/accept_redirects                        [OK]
     XFRM larval drop                                     [OK]
Pluto ipsec.conf syntax                                   [OK]
Hardware random device                                    [N/A]
Two or more interfaces found, checking IP forwarding      [OK]
Checking rp_filter                                        [OK]
Checking that pluto is running                            [OK]
 Pluto listening for IKE on udp 500                       [OK]
 Pluto listening for IKE/NAT-T on udp 4500                [OK]
 Pluto ipsec.secret syntax                                [OK]
Checking 'ip' command                                     [OK]
Checking 'iptables' command                               [OK]
Checking 'prelink' command does not interfere with FIPSChecking for obsolete ipsec.conf options                  [OK]
Opportunistic Encryption                                  [DISABLED]

如果有异常请检查之前的配置。

配置xl2tpd

编辑/etc/xl2tpd/xl2tpd.conf配置如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[global]
listen-addr = YOUR_PUBLIC_IP_ADDRESS
ipsec saref = yes
[lns default]
ip range = 192.168.1.128-192.168.1.254
local ip = 192.168.1.99
require chap = yes
refuse pap = yes
require authentication = yes
name = LinuxVPNserver
ppp debug = yes
pppoptfile = /etc/ppp/options.xl2tpd
length bit = yes

其实主要注意监听地址和几个yes就行了,其他基本不用动。

然后编辑/etc/ppp/options.xl2tpd配置如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ipcp-accept-local
ipcp-accept-remote
ms-dns 8.8.8.8
ms-dns 8.8.4.4
noccp
auth
crtscts
idle 1800
mtu 1410
mru 1410
nodefaultroute
debug
lock
proxyarp
connect-delay 5000

/etc/ppp/chap-secrets里添加帐号密码:

1
2
3
# client server secret IP addresses
username1 * password1 *
username2 * password2 *

按照对应格式填上帐号密码即可。

启动xl2tpd并加入开机启动:

service xl2tpd start        #systemctl start xl2tpd
chkconfig xl2tpd on        #systemctl enable xl2tpd

最后在本地设备上填上地址、预共享密钥、用户名、密码就可以连接了。

Read More +

Let's Encrypt SSL证书配置

certbot.eff.org

安装certbot

yum install epel-release
yum install certbot

获取证书

certbot certonly --webroot --email user@domain.com -w /usr/share/nginx/blog -d www.shintaku.cc -w /usr/share/nginx/info -d info.shintaku.cc

然后在/etc/letsencrypt/live/下就会生成存放证书链接的目录,将它们配置到Web服务器就可以了。

配置Nginx

编辑/etc/nginx/conf.d/ssl.conf文件:

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
46
47
48
49
50
51
52
53
54
server {
listen 443;
server_name www.shintaku.cc;
ssl on;
ssl_certificate /etc/letsencrypt/live/www.shintaku.cc/fullchain.pem;
ssl_certificate_key /etc/letsencrypt/live/www.shintaku.cc/privkey.pem;
ssl_session_cache shared:le_nginx_SSL:1m;
ssl_session_timeout 1440m;
ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
ssl_prefer_server_ciphers on;
ssl_ciphers "ECDHE-ECDSA-CHACHA20-POLY1305:ECDHE-RSA-CHACHA20-POLY1305:ECDHE-ECDSA-AES128-GCM-SHA256:ECDHE-RSA-AES128-GCM-SHA256:ECDHE-ECDSA-AES256-GCM-SHA384:ECDHE-RSA-AES256-GCM-SHA384:DHE-RSA-AES128-GCM-SHA256:DHE-RSA-AES256-GCM-SHA384:ECDHE-ECDSA-AES128-SHA256:ECDHE-RSA-AES128-SHA256:ECDHE-ECDSA-AES128-SHA:ECDHE-RSA-AES256-SHA384:ECDHE-RSA-AES128-SHA:ECDHE-ECDSA-AES256-SHA384:ECDHE-ECDSA-AES256-SHA:ECDHE-RSA-AES256-SHA:DHE-RSA-AES128-SHA256:DHE-RSA-AES128-SHA:DHE-RSA-AES256-SHA256:DHE-RSA-AES256-SHA:ECDHE-ECDSA-DES-CBC3-SHA:ECDHE-RSA-DES-CBC3-SHA:EDH-RSA-DES-CBC3-SHA:AES128-GCM-SHA256:AES256-GCM-SHA384:AES128-SHA256:AES256-SHA256:AES128-SHA:AES256-SHA:DES-CBC3-SHA:!DSS";
location / {
root /usr/share/nginx/blog;
index index.html;
}
error_page 404 /404.html;
location = /404.html {
root /usr/share/nginx/blog;
}
}
server {
listen 443;
server_name info.shintaku.cc;
autoindex on;
ssl on;
ssl_certificate /etc/letsencrypt/live/www.shintaku.cc/fullchain.pem;
ssl_certificate_key /etc/letsencrypt/live/www.shintaku.cc/privkey.pem;
ssl_session_cache shared:le_nginx_SSL:1m;
ssl_session_timeout 1440m;
ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
ssl_prefer_server_ciphers on;
ssl_ciphers "ECDHE-ECDSA-CHACHA20-POLY1305:ECDHE-RSA-CHACHA20-POLY1305:ECDHE-ECDSA-AES128-GCM-SHA256:ECDHE-RSA-AES128-GCM-SHA256:ECDHE-ECDSA-AES256-GCM-SHA384:ECDHE-RSA-AES256-GCM-SHA384:DHE-RSA-AES128-GCM-SHA256:DHE-RSA-AES256-GCM-SHA384:ECDHE-ECDSA-AES128-SHA256:ECDHE-RSA-AES128-SHA256:ECDHE-ECDSA-AES128-SHA:ECDHE-RSA-AES256-SHA384:ECDHE-RSA-AES128-SHA:ECDHE-ECDSA-AES256-SHA384:ECDHE-ECDSA-AES256-SHA:ECDHE-RSA-AES256-SHA:DHE-RSA-AES128-SHA256:DHE-RSA-AES128-SHA:DHE-RSA-AES256-SHA256:DHE-RSA-AES256-SHA:ECDHE-ECDSA-DES-CBC3-SHA:ECDHE-RSA-DES-CBC3-SHA:EDH-RSA-DES-CBC3-SHA:AES128-GCM-SHA256:AES256-GCM-SHA384:AES128-SHA256:AES256-SHA256:AES128-SHA:AES256-SHA:DES-CBC3-SHA:!DSS";
root /usr/share/nginx/info;
location / {
index index.html index.htm index.php;
}
location ~ \.php$ {
fastcgi_pass 127.0.0.1:9000;
fastcgi_index index.php;
fastcgi_param SCRIPT_FILENAME $document_root$fastcgi_script_name;
include fastcgi_params;
}
}

最后重载Nginx配置就可以了。

证书续期

certbot renew && nginx -s reload
Read More +

向量空间中词表征的有效估计

原文:Efficient Estimation of Word Representations in Vector Space
源码:word2vec

摘要

本文提出了两种新的模型结构,用于计算大型数据集中单词的连续向量表征。这些表征的质量是在单词相似性任务中衡量出来的,并将结果与​​之前基于不同类型神经网络(neural network)的最佳效果进行比较。我们观测到在低计算成本的精度上有大幅提高,只用不到一天的时间从16亿单词中学到高质量的词向量。此外,我们展示了这些向量在衡量句法和词义相似性上保证了最先进的性能。

绪论

当今先进的自然语言处理系统与技术都把词作为原子单元。总是被用作词表的索引,而不去考虑词间的相似性。这样做的好处在于简单且健壮,而且观察到简单模型在大量数据上训练的性能优于复杂模型在少量数据上的训练。统计语言模型中的N-gram就是这样的典型例子,几乎可以在所有可用数据上训练(万亿词量)。

然而简单的技术在很多领域都有其局限性。例如相关领域内的自动语音识别数据是有限的,简单模型的性能通常取决于转录的高质量的语音数据的大小,通常只有几百万的词。在机器翻译中,很多语音的已有的语料库的大小也只有几十亿。因此,对这些基本技术的简单升级并不会带来很大的性能提升,我们不得不考虑更复杂的高级技术。

随着机器学习技术的发展,训练更大规模数据上的复杂模型成为可能,它们要远远超过那些简单模型。可能最成功的概念就是使用分布式词表征(distributed representations of words),例如基于神经网络的语言模型远优于N-gram模型。

本文目标

本文的主要目标是介绍一种能从几十亿的语料库与几百万的词表的巨大数据集中学习高质量词表征的技术。据我们所知,迄今为止没有任何一个框架能以50~100维的词向量成功训练上亿的词表。

使用最近提出的一项技术来衡量得到的向量表征的质量,该度量指标不但期望意思相近的词表征相近,而且还能表示词的多种相似性程度(multiple degrees of similarity)。这常见于屈折语(inflectional language)中,例如名词可能有多种词尾(后缀),如果在原始的向量子空间中搜索相似词,可能找到的是具有相似词尾的词。

令人惊讶的是词表征的相似性远远超出了简单的语法规则。使用词偏置技术时,对词向量进行简单的代数操作,例如vector(“King”)-vector(“Man”)+vector(“Woman”)得到的向量与Queen比较近。

本文通过开发新的模型结构来最大化向量操作的精度,从而保留词间的线性规则。我们设计了一个综合的测试集从语法和语义规则两方面衡量,以此来展示该模型可以以很高的精度学习到许多规则,并进一步讨论了模型的训练时间和精度取决于词向量的维度和训练数据集的大小。

前期工作

将词表示为连续的向量的思想由来已久。一个很受欢迎的模型结构称为神经网络语言模型(neural network language model, NNLM),采用一个线性投影层加上一个非线性隐藏层来同时学习到词向量表征和统计语言模型。该工作得到后续很多工作的参考。

另一个有趣的NNLM结构是先用一个隐藏层的神经网络来学习词向量,再使用这些词向量来训练NNLM。因此,词向量的学习不需要构建完整的NNLM。本文对这个结构进一步扩展,致力于使用一个简单的模型来学习词向量表征。

后续会展示词向量表征可以用来显著改善和简化许多NLP应用。词向量本身的估计可以采用多种模型结构,在多种语料库上训练,其中一些学习到的词向量表征可以用作进一步的研究和对比。然而,据我们所知,这些模型的计算代价要远远高于最早的模型,一个例外是mnih2007three中提出的采用对角权重矩阵的log-bilinear模型。

模型结构

许多已经提出的不同的模型可以用来估计词的连续向量表征,包括广为人知的潜在语义分析(Latent Semantic Analysis, LSA)以及隐含狄利克雷分布(Latent Dirichlet Allocation, LDA)。本文着重于用神经网络学习词的分布式表征,已有的工作表明,与LSA相比分布式表征可以更好的保留词间的线性规则。而LDA最大的缺点在于大数据集上的计算复杂度高。

比较不同模型结构,首先用完整的训练模型所需要的参数的数量来定义模型计算的复杂度。接下来试图最大化精度,同时最小化计算复杂度。对于下面所有模型,训练复杂度遵循:$$O=E\times T\times Q$$
其中\(E\)表示训练次数,\(T\)表示训练集单词数,\(Q\)表示模型结构进一步定义。通常\(E\)在3~50之间,\(T\)高达十亿。所有的模型采用随机梯度下降反向传播

前馈NNLM

概率前馈神经网络语言模型(Feedforward NNLM)包括输入(input)、投影(projection)、隐藏(hidden)、输出(output)四层。输入层中,前\(N\)个词编码为1-of-\(V\),\(V\)为词表大小。输入层映射到\(N\times D\)维的投影层\(P\)。由于在任何时刻,仅\(N\)个输入是激活的,因此投影层的组合是相对简单的操作。

NNLM结构的复杂计算在于投影层和隐藏层之间的计算,主要原因是投影层是稠密的。对于一个常见的选择\(N=10\),投影层\(P\)的大小可能为500~2000,而隐藏层\(H\)的大小通常为500~1000。更进一步讲,隐藏层通常用来计算在整个词表上的概率分布,输出层的结果是\(V\)维的。因此每个训练实例的计算复杂度为:$$Q=N\times D+N\times D\times H+H\times V$$

其中\(H\times V\)起决定作用。然而为了避免如此提出了一些实际的解决方案:使用Hierarchical Softmax,或者在训练的时候使用未归一化的模型来避免对模型的归一化。采用词表的二叉树表示,可以将输出单元的数量降低到\(\log_2(V)\)。这样模型的主要复杂度就在\(N\times D\times H\)了。

本文的模型采用Hierarchical Softmax,其中词表表示为霍夫曼树。这样做主要是基于之前观测到的一个现象:词频对于在NNLM上获取分类非常有效。霍夫曼树给频繁出现的词以较短的编码,这样进一步减少了输出单元的数量。而平衡二叉树需要\(\log_2(V)\)输出来评估,基于霍夫曼树的Hierarchical Softmax仅仅需要\(\log_2(Unigram_perplexity(V))\)。例如当词表大小为100万时计算效率得到了两倍的加速。虽然对于NNLM来讲不是最关键的加速,因为主要的计算瓶颈在于\(N\times D\times H\),后续提出的模型结构并没有隐藏层,而是主要取决于Softmax正则化。

递归NNLM

递归神经网络语言模型(Recurrent NNLM)的提出是为了克服前馈NNLM的一些局限性,例如需要指定上下文的长度(模型阶数N),因此理论上讲递归神经网络(recurrent neural network)可以比浅层神经网络(shallow neural networks)更高效的表示更复杂的模式。RNN并没有投影层,只有输入、隐藏、输出三层。这类模型的特殊性在于递归矩阵,该矩阵用时间延迟将隐藏层与自身连接起来。这就允许递归模型形式化某种短时记忆,因为之前的信息能够表示为隐藏层中的状态,该状态可以根据当前的输入以及上个时间步的状态进行更新。

RNN模型对于一个训练实例的时间复杂度是:$$Q=H\times H+H\times V$$

其中词表征\(D\)具有与隐藏层\(H\)相同的维度。我们同样可以使用Hierarchical Softmax将\(H\times V\)有效降低为\(H\times\log_2(V)\)。主要计算复杂度在于\(H\times H\)。

神经网络的并行训练

在大规模数据集上训练模型时,已经基于大规模分布式框架DistBlief实现了几个模型包括前馈NNLM以及本文中提出的新模型。该框架支持并行运行一个模型的多个副本,每个副本通过保持参数一致的中央服务器来同步梯度更新。对于并行训练,我们采用自适应的学习速率下的mini-batch异步梯度下降,整个过程称为Adagrad。在这种框架下,通常一个数据中心使用100多个模型副本,每个副本使用不同机器的多核。

对数线性模型

本节提出两个以最小化计算复杂度来学习分布式词表征的模型结构。前文观测结果表明:模型计算的主要复杂度来自于非线性隐藏层。尽管这些隐藏层使神经网络更优雅,本文还是决定使用可能没有神经网络数据精确的更为简单的模型,但是至少能够高效的训练更多的数据。

新结构的提出主要基于之前发现的NNLM可以通过两步进行训练:

  • 使用简单模型学习连续词向量表征
  • 基于分布式词表征训练N-gram神经网络语言模型

连续Bag-of-Words模型

CBOW

首先提出的结构类似于前馈NNLM,去掉了其中的非线性隐层,所有词共享投影层(不只是投影矩阵);所有的词投影到相同的位置(向量平均)。因为历史词序并不能影响投影,所以把这个结构称为词袋模型(bag-of-words)。更何况也使用了未来的词。在下节提到的任务中,使用4个未来词和4个历史词作为输入取得了最优的性能,其中优化目标是能准确对当前词分类。训练复杂度为:$$Q=N\times D+D\times\log_2(V)$$
将这个模型记为CBOW。与标准词袋模型不同,它使用上下文的连续分布式表征。注意输入层与投影层之间的权重矩阵与NNLM一样是所有词位置共享的。

连续Skip-Gram模型

Skip-gram

第二个结构与CBOW类似,不同的是CBOW基于上下文预测当前词,这个模型尝试根据同一句子中的另外一个词来最大化一个词的分类。更准确的说法,使用当前词作为有连续投影层的对数线性分类器的输入,来预测词语所在当前词的前后范围。发现增加窗口的大小可以提高学习到的词向量的质量,但也增加了计算复杂度。因为离得越远的词通常与当前词越不相关,所以给那些离得较远的词较小的权重使得其被采样的概率变小。该结构的训练复杂度正比于:$$Q=C\times(D+D\times\log_2(V))$$
其中\(C\)为词间的最大距离,对于每个训练词从\(<1;c>\)范围内选择随机数\(R\),使用\(R\)个历史词与\(R\)个未来词作为当前词的标签。这就需要做\(R\times2\)个词分类,将当前词作为输入,\(R+R\)中的每个词作为输出。

Read More +

VPS开启TCP-BBR拥塞控制

早就听说Google又搞出了BBR这样的黑科技,能在有一定丢包率的网络链路上充分利用带宽并降低延迟,起到了玄学般的加速效果,比锐速不知道高到哪里去了,简直是梯子用户的福音。由于需要升级内核,有影响VPS上服务的风险,就一直没动。现在机器闲下来了,又赶上余额快用完了,就趁机乱搞一发。

更新内核

首先更新一下系统:

yum update -y

然后添加ELRepo源来更新4.9及以上版本的内核:

rpm --import https://www.elrepo.org/RPM-GPG-KEY-elrepo.org
rpm -Uvh http://www.elrepo.org/elrepo-release-7.0-2.el7.elrepo.noarch.rpm
yum --enablerepo=elrepo-kernel install kernel-ml -y

安装完后检查一下是否安装成功:

awk -F\' '$1=="menuentry " {print i++ " : " $2}' /etc/grub2.cfg

如果没有其他问题一般来说新安装的内核会出现在第一行:

0 : CentOS Linux (4.11.0-1.el7.elrepo.x86_64) 7 (Core)
1 : CentOS Linux 7 Rescue f4cdc05ef89d44228e2623a70209bbce (3.10.0-327.28.3.el7.x86_64)
2 : CentOS Linux (3.10.0-327.28.3.el7.x86_64) 7 (Core)
3 : CentOS Linux (3.10.0-327.28.2.el7.x86_64) 7 (Core)
4 : CentOS Linux (0-rescue-3839f3a1ba354857903e239a272e6cec) 7 (Core)

然后将最新的内核(编号为0的)设为默认内核:

grub2-set-default 0

然后reboot重启就可以了;如果是DigitalOcean的VPS建议先poweroff关机,然后到控制台把Kernel改成DigitalOcean GrubLoader v0.2,然后再开机:

开启BBR

开机后先uname -r确认一下内核是否更换成功,如果没问题就编辑/etc/sysctl.conf加入以下内容:

1
2
net.core.default_qdisc = fq
net.ipv4.tcp_congestion_control = bbr

保存后执行sysctl -p生效。然后查看TCP配置:

sysctl net.ipv4.tcp_available_congestion_control
sysctl net.ipv4.tcp_congestion_control

如果=后面都有bbr出现则说明设置成功。执行:

lsmod | grep tcp_bbr

如果有tcp_bbr则说明已开启。

Read More +

大型属性网络的语义社团识别

原文:Semantic community identification in large attribute networks

摘要

网络的模块或社团结构的识别是理解网络语义和功能的关键。虽然已经开发了许多主要探索网络拓扑的社区检测方法,但它们只提供了少量语义信息的社团发现。尽管结构和语义密切相关,但在一起发现并分析这两个基本网络属性上只做了很少的工作。通过在节点上整合网络拓扑和语义信息,如节点属性,研究了社团检测并同时推断其语义的问题。本文提出了一种具有两组参数,社团成员矩阵和社团属性矩阵的新型非负矩阵因式分解(NMF)模型,并提出了有效的更新规则保证收敛地评估参数。节点属性的使用改进了社团检测,并为所得到的网络社团提供了语义解释。在人造和真实的世界网络上的广泛实验结果不仅显示了新方法较先进方法的优越性能,而且还展示了其对社团的语义注释能力。

SCI模型

考虑一个有\(n\)个节点\(V\)和\(e\)条边\(E\)的无向网络\(G=(V,E)\),用二值邻接矩阵\(\mathbf{A}\in\mathbb{R}^{n\times n}\)表示。与每个节点\(i\)相关联的是其属性\(\mathbf{S}_i\),其可以是节点的语义特征。节点的属性是\(m\)维二值向量形式的,所有节点的属性可以由节点属性矩阵\(\mathbf{S}\in\mathbb{R}^{n\times m}\)表示。社团识别的问题是将网络\(G\)划分为\(k\)个社团,并推断每个社团的相关属性或语义。

建模网络拓扑

将属于社团\(j\)的节点\(i\)的先验定义为\(U_{ij}\)。网络中所有节点的社团成员为\(\mathbf{U}=(U_{ij})\),其中\(i=1,2,\ldots,n\)且\(j=1,2,\ldots,k\)。因此\(U_{ir}U_{pr}\)表示社团\(r\)中节点\(i\)和\(p\)之间边数的期望。对所有社团求和,\(i\)和\(p\)之间边数的期望是\(\sum_{r=1}^kU_{ir}U_{pr}\)。 这种生成边的过程意味着如果两个节点具有相似的社团关系,则它们具有更高的连接倾向。节点对之间的期望边数应尽可能与由\(\mathbf{A}\)表示的网络拓扑一致,在矩阵行列式上产生以下函数:$$\min\limits_{\mathbf{U}\ge0}|\mathbf{A}-\mathbf{UU}^T|_F^2$$

建模节点属性

定义社团\(r\)具有属性\(q\)的倾向为\(C_{qr}\)。因此对于所有社团,有一个社团属性矩阵\(\mathbf{C}=(C_{qr})\),对于\(q=1,2,\ldots,m\)和\(r=1,2,\ldots,k\),其中第\(r\)列\(\mathbf{C}_r\)是社团\(r\)的属性成员。如果节点的属性与社团的属性高度相似,那么该节点可能更倾向于在这个社团中。 因此,在\(S_i\)中描述的具有相似属性的节点可能形成一个社团,其可由节点的一般属性来描述。特别地,节点\(i\)属于社团\(r\)的倾向可表示为\(U_{ir}=\mathbf{S}_i\mathbf{C}_r\)。注意如果节点\(i\)和社团\(r\)的属性完全不一致,则节点\(i\)一定不属于社团\(r\),即\(U_{ir}=0\)。由于所有节点\(mathbf{U}\)的社团成员为结合节点和社团的属性提供了指导,有以下优化函数:$$\min\limits_{\mathbf{C}\ge0}|\mathbf{U}-\mathbf{SC}|_F^2$$
为了给每个社团选择最相关的属性,为矩阵\(\mathbf{C}\)的每列添加一个\(l_1\)稀疏范数。另外为了防止\(\mathbf{C}\)的一些列的值过大(每个社团都有一些有意义的属性),对\(\mathbf{C}\)有约束\(\sum_{j=1}^k|\mathbf{C}(:,j)|_1^2\),产生以下目标函数:$$\min\limits_{\mathbf{C}\ge0}|\mathbf{U}-\mathbf{SC}|_F^2+\alpha\sum_{j=1}^k|\mathbf{C}(:,j)|_1^2$$
其中\(\alpha\)是权衡第一误差项和第二稀疏项的非负参数。

统一模型

通过结合网络拓扑模型和节点属性模型的目标函数,有以下完整函数:$$\min\limits_{\mathbf{U}\ge0,\mathbf{C}\ge0}L=|\mathbf{U}-\mathbf{SC}|_F^2+\alpha\sum_{j=1}^k|\mathbf{C}(:,j)|_1^2+\beta|\mathbf{A}-\mathbf{UU}^T|_F^2$$
其中\(\beta\)是调整网络拓扑权重的正参数。

优化

由于上面的目标函数不是凸的,所以获得最优解不切实际。局部最小值可以使用专门化-最小化框架来实现。这里描述一个固定\(\mathbf{C}\)迭代更新\(\mathbf{U}\)然后固定\(\mathbf{U}\)迭代更新\(\mathbf{C}\)的算法,这保证在每次迭代之后不增加目标函数。具体公式展示为如下两个子问题。

U问题

当固定\(\mathbf{C}\)更新\(\mathbf{U}\)时,需要解决以下问题:$$\min\limits_{\mathbf{U}\ge0}L(\mathbf{U})=|\mathbf{U}-\mathbf{SC}|_F^2+\beta|\mathbf{A}-\mathbf{UU}^T|_F^2$$
为此为\(\mathbf{U}\)上的非负约束引入拉格朗日乘数矩阵\(\mathbf{\Theta}=(\Theta_{ij})\),得到以下等价目标函数:$$L(\mathbf{U})=tr(\mathbf{UU}^T-\mathbf{UC}^T\mathbf{S}^T-\mathbf{SCU}^T+\mathbf{SCC}^T\mathbf{S}^T)+\beta tr(\mathbf{AA}-\mathbf{AUU}^T-\mathbf{UU}^T\mathbf{A}+\mathbf{UU}^T\mathbf{UU}^T)+tr(\mathbf{\Theta U}^T)$$
将对\(\mathbf{U}\)的导数\(L(\mathbf{U})\)设为0,有:$$\mathbf{\Theta}=-2\mathbf{U}+2\mathbf{SC}+4\beta\mathbf{AU}-4\beta\mathbf{UU}^T\mathbf{U}$$
根据对非负\(\mathbf{U}\)的卡罗需-库恩-塔克条件(KKT条件)有如下等式:$$(-2\mathbf{U}+2\mathbf{SC}+4\beta\mathbf{AU}-4\beta\mathbf{UU}^T\mathbf{U})_{ij}U_{ij}=\Theta_{ij}U_{ij}=0$$
这是解收敛时必须满足的固定点方程。给定\(\mathbf{U}\)的初始值,\(\mathbf{U}\)的连续更新为:$$U_{ij}\gets U_{ij}\big(\frac{(\mathbf{SC}+2\beta\mathbf{AU}-\mathbf{U})_{ij}}{2\beta(\mathbf{UU}^T\mathbf{U})_{ij}}\big)^\frac{1}{4}$$
为了保证\(\mathbf{U}\)非负的属性,将\(\mathbf{A}\)中的对角元素设置为大于\(\frac{1}{2\beta}\)。\(\mathbf{U}\)的更新规则满足以下定理以保证规则的正确性。

  • 定理1

    如果U的更新规则收敛,则最终解满足KKT最优条件。

  • 定义1

    当函数\(Q(\mathbf{U},\mathbf{U}’)\ge L(\mathbf{U})\),\(Q(\mathbf{U},\mathbf{U})=L(\mathbf{U})\)时,\(Q(\mathbf{U},\mathbf{U}’)\)是\(L(\mathbf{U})\)的辅助函数。

  • 引理1

    如果\(Q\)是\(L\)的辅助函数,则\(L\)在更新规则\(\mathbf{U}^{(t+1)}=arg\min_\mathbf{U}Q(\mathbf{U},\mathbf{U}^{(t)})\)下不增加。

  • 引理2

    函数$$Q(\mathbf{U},\mathbf{U}’)=tr(\mathbf{SCC}^T\mathbf{S}^T+\beta\mathbf{AA})-\beta tr(\mathbf{RU’}^T\mathbf{U’U’}^T)-tr(\mathbf{U’}^T\mathbf{A’Z})\\\quad\quad\quad\quad\quad-tr(\mathbf{Z}^T\mathbf{A’U’})-tr(\mathbf{U’}^T\mathbf{A’U’})-2tr(\mathbf{C}^T\mathbf{S}^T\mathbf{Z})-2tr(\mathbf{C}^T\mathbf{S}^T\mathbf{U’})$$
    是\(L(\mathbf{U})\)的辅助函数,其中\(R_{ij}=\frac{U_{ij}^4}{U_{ij}’^3}\),\(Z_{ij}=U’_{ij}\ln\frac{U_{ij}}{U’_{ij}}\),\(\mathbf{A}’=2\beta\mathbf{A}-\mathbf{I}\),且\(\mathbf{I}\)是单位矩阵。

  • 定理2

    在\(\mathbf{U}\)的迭代更新下U问题是非增的。

C问题

当固定\(\mathbf{U}\)更新\(\mathbf{C}\)时,需要解决以下问题:$$\min\limits_{\mathbf{C}\ge0}L(\mathbf{C})=|\mathbf{U}-\mathbf{SC}|_F^2+\alpha\sum_{j=1}^k|\mathbf{C}(:,j)|_1^2$$
它等价于如下优化问题:$$\min\limits_{\mathbf{C}\ge0}L(\mathbf{C})=|\dbinom{\mathbf{S}}{\sqrt{\alpha}\mathbf{e}_{1\times m}}\mathbf{C}-\dbinom{\mathbf{U}}{\mathbf{0}_{1\times k}}|_F^2$$
其中\(\mathbf{e}_{1\times m}\)是一个所有分量为1行向量,\(\mathbf{0}_{1\times k}\)是0向量。因此对上面的问题有以下规则:$$\mathbf{C}_{ij}\gets\mathbf{C}_{ij}\frac{(\mathbf{S’}^T\mathbf{U’})_{ij}}{(\mathbf{S’}^T\mathbf{S’C})_{ij}}$$
其中\(\mathbf{S’}=\dbinom{\mathbf{S}}{\sqrt{\alpha}\mathbf{e}_{1\times m}}\)且\(\mathbf{U’}=\dbinom{\mathbf{U}}{\mathbf{0}_{1\times k}}\)。

在融合中,由于\(\mathbf{U}\)表达了社团成员软关系分布,可以直接使用\(\mathbf{U}\)或\(\mathbf{U}=\mathbf{SC}\)来获得最终的不相交或重叠的社团。每列\(\mathbf{C}\)表示社团与属性之间的关系,值越大表示与社团对应的属性越相关。

Read More +

LINE:大规模信息网络嵌入

原文:LINE: Large-scale Information Network Embedding
源码:tangjianpku/LINE

摘要

这篇论文提出了一种将大规模信息网络嵌入到低维向量空间中的方法,适用于有向、无向、有权、无权图。该方法用了精心设计的目标函数,保留了局部和全局网络结构。边采样方法克服了传统梯度下降法的局限性,提高了效率和效果。

问题定义

信息网络

信息网络定义为\(G=(V, E)\),\(V\)是点集,\(E\)是边集。每条边是有序对\(e=(u, v)\)且有大于0的权重\(w_{u,v}\)来表示关系强度(该问题中不考虑负权)。无向图认为双向边相等。
把信息网络嵌入到低维空间非常有用,但要执行嵌入必须先保留网络结构。

一阶接近度

网络中的一阶接近度是指两点间的局部成对相似度。连接点对的边之权重表示两点间的一阶接近度,若无边则一阶接近度是0。
一阶接近度通常暗含真实网络中两点的相似度,但被观测到的边只占很小一部分,未观测到的一阶接近度被视作0,因此一阶接近度不足以保留网络结构。

二阶接近度

点对间的二阶接近度是它们邻居网络结构的相似度。用\(p_u=(w_{u,1},\ldots,w_{u,|V|})\)表示\(u\)到其他节点的一阶接近度,二阶接近度就是\(p_u\)和\(p_v\)(一阶接近度)的相似度。如果没有节点与\(u\)和\(v\)相连,则二阶接近度为0。

大规模信息网络嵌入

给出大型网络\(G=(V, E)\),信息网络嵌入旨在把每个节点\(v\)表示到低维空间\(R^d\)中,学习一个函数\(f_G:V\to R^d\)其中\(d\ll |V|\)。在空间\(R^d\)中一阶接近度和二阶接近度都保留着。

LINE模型

合格的真实世界信息网络嵌入模型要满足以下条件:

  • 保留节点间的一阶接近度和二阶接近度
  • 可用于大型网络
  • 可以处理有向/无向/有权/无权图

模型描述

一阶接近度的LINE

对于每条无向边\((i, j)\),定义\(v_i\)和\(v_j\)的连接概率为:$$p_1(v_i, v_j)=\frac{1}{1+\exp(-\overrightarrow{u_i}^T\cdot\overrightarrow{u_j})}$$
其中\(\overrightarrow{u_i}\)是\(v_i\)的低维向量表示。上式定义的\(V \times V\)空间内的分布,经验分布\(\hat{p_1}(i, j)=\frac{w_{ij}}{W}\),其中\(W=\sum_{(i,j)\in{E}}{w_{ij}}\)。为了保留一阶接近度,简单的方法是减小以下目标函数:$$O_1=d(\hat{p_1}(\cdot, \cdot), {p_1}(\cdot, \cdot))$$

其中\(d(\cdot, \cdot)\)是两个分布之间的距离。减小两个概率分布的KL散度,用KL散度替换距离函数并去掉常量后得到:$$O_1=-\sum_{(i,j)\in{E}}{w_{ij}\log{p_1(v_i,v_j)}}$$
注意一阶接近度仅适用于无向图。找到减小上式的\(\left\{\overrightarrow{u_i}\right\}_{i=1..|V|}\)就可以表示d维空间内的每个点。

二阶接近度的LINE

二阶接近度适用于有向图和无向图。给出一般网络,假设其有向。二阶接近度假设节点与其他节点共享多条连接,这种情况下每个节点都有独特的环境(context)且在环境上分布相似的节点被假设为相似的。因此每个节点扮演两种角色:节点本身和其他节点的外部环境。引入两个向量\(\overrightarrow{u_i}\)和\(\overrightarrow{u_i}’\),其中\(\overrightarrow{u_i}\)表示作为节点的\(v_i\),\(\overrightarrow{u_i}’\)表示作为环境的\(v_i\)。对于每个有向边\((i,j)\)首先定义环境\(v_j\)生成节点\(v_i\)的概率:$$p_2(v_j\mid v_i)=\frac{\exp({\overrightarrow{u_j}’}^T\cdot\overrightarrow{u_i})}{\sum_{k=1}^{|V|}\exp({\overrightarrow{u_k}’^T\cdot\overrightarrow{u_i})}}$$
其中\(|V|\)是节点或环境的数量。对于每个节点\(v_i\),上式确定了环境上的条件分布。为保留二阶接近度,应当由低维表示确定条件分布来接近经验分布\(\hat{p_2}(\cdot|v_i)\),因此减小以下目标函数:$$O_2=\sum_{i\in{V}}\lambda_{i}d(\hat{p_2}(\cdot\mid v_i),p_2(\cdot\mid v_i))$$

其中\(d(\cdot, \cdot)\)是两个分布之间的距离,由于网络中节点的重要性可能不同,引入\(\lambda_i\)来表示网络中节点\(i\)可通过算法用度或相似度来衡量的重要性。经验分布\(\hat{p_2}(\cdot\mid v_i)\)定义为\(\hat{p_2}(v_j\mid v_i)=\frac{w_{ij}}{d_i}\),其中\(w_{ij}\)是边\((i, j)\)的权重,\(d_i\)是节点\(i\)的出度。为了简化,引入KL散度作为距离函数,将\(\lambda_i\)设为度\(d_i\)并去掉常量后得到:$$O_2=-\sum_{(i,j)\in{E}}w_{ij}\log{p_2(v_j\mid v_i)}$$

通过学习\(\left\{\overrightarrow{u_i}\right\}_{i=1..|V|}\)和\(\left\{\overrightarrow{u_i}’\right\}_{i=1..|V|}\)减小这项,就可以用d维向量\(\overrightarrow{u_i}\)表示每个节点\(v_i\)。

结合一阶二阶接近度

简单有效的方法是分别求出一阶二阶接近度,然后对每个节点把两种方法的嵌入训练组合起来。更正规的方法是结合两个接近度联合训练两个目标函数。

模型优化

优化\(O_2\)计算代价很高,因为在计算条件概率\(p_2\)时要累加全部节点。于是引入mikolov2013distributed中提出的负采样(negative sampling),根据每个边\((i, j)\)的噪声分布取样多个负边,特别对每个边指定了以下函数:$$\log\sigma(\overrightarrow{u_j}’^T\cdot\overrightarrow{u_i})+\sum_{i=1}^K E_{v_n\sim P_n(v)}[\log\sigma(-\overrightarrow{u_n}’^T\cdot\overrightarrow{u_i})]$$

其中\(\sigma(x)=1/(1+\exp(-x))\)。第一项构造观测边,第二项构造由噪声分布画出的负边,\(K\)是负边数。令\(P_n(v)\propto d_v^{3/4}\),其中\(d_v\)是节点\(v\)的出度。
对于\(O_1\)存在平凡解:当\(i\)取\(1,\ldots,|V|\),\(k\)取\(1,\ldots,d\)时\(u_{ik}=\infty\)。为了避免平凡解可以使用把\(\overrightarrow{u_j}’^T\)改为\(\overrightarrow{u_i}\)的负采样方法。
引用recht2011hogwild中提出的异步随机梯度算法(ASGD)来优化上式。每一步算法采样少量边然后更新模型参数。如果边\((i, j)\)被采样了,节点\(i\)的嵌入向量\(\overrightarrow{u_i}\)是:$$\frac{\partial O_2}{\partial \overrightarrow{u_i}}=w_{ij}\cdot\frac{\partial\log{p_2}(v_j\mid v_i)}{\partial \overrightarrow{u_i}}$$

注意梯度要乘边权,当边权差距很大时会难以找到好的学习速率。如果根据小权边确定了大的学习速率,会造成大权边的梯度爆炸,因为在根据大权边选择学习速率时梯度会变得很小。

通过边采样优化

简单的解决方案是将权为\(w\)的边展开成\(w\)个二元边(binary edges),但是会显著提高内存需求,尤其是当边权非常大时。解决这种问题的一种方法是从原始边进行采样并转换为二元边,通过采样率按比例还原原始边。然后问题就退化成了如何根据权重采样边。
令\(W=(w_1,\ldots,w_{|E|})\)表示边权序列,边权和\(w_{sum}=\sum_{i=1}^{|E|}w_i\),然后在\(\left[0,w_{sum}\right]\)取随机数,看它落在\(\left[\sum_{j=0}^{i-1}w_j,\sum_{j=0}^iw_j\right)\)的哪个区间内。这种方法用\(O(|E|)\)的复杂度,当边数非常大时会很耗时。所以引用li2014reducing中提出的别名法(alias method)只用\(O(1)\)的复杂度就能从同一离散分布中刻画样本。用负采样可以将常数时间优化到\(O(d(K+1))\)次,其中\(K\)是负采样数量,因此每步要做\(O(dK)\)次。在实践中发现优化步数和边数是成比例的,所以LINE的总体复杂度是\(O(dK|E|)\),和边数是线性相关并与节点数无关。这种边采样方法提高了随机梯度下降法的效率。

讨论

低度节点

一个实际问题是如何准确嵌入度很小的节点。由于其邻居节点很少,难以推断其表达式,特别是依赖其环境的二阶接近度。于是这里考虑对每个节点扩张其二阶邻居节点,也就是邻居的邻居。节点\(i\)和其二阶邻居\(j\)间的权重是:$$w_{ij}=\sum_{k\in N(i)}w_{ik}\frac{w_{kj}}{d_k}$$

在实践中只能增加与低度节点\(i\)有最大相似度\(w_{ij}\)的节点\({j}\)的子集。

新节点

另一个实际问题是如何表示新加节点。对于新节点\(i\),如果所连节点已知就可以获得已知节点经验分布\(\hat{p_1}(\cdot, v_i)\)和\(\hat{p_2}(\cdot\mid v_i)\)。为了获得新节点的嵌入,根据\(O_1\)和\(O_2\)通过更新新节点嵌入并保持已有节点的嵌入来直接减小$$-\sum_{j\in{N(i)}}{w_{ji}\log{p_1(v_j,v_i)}},\quad或\quad -\sum_{j\in{N(i)}}{w_{ji}\log{p_2(v_j,v_i)}},$$

如果没有观测到新节点和已有节点的连接就需要其他信息,比如节点的文本信息。

Read More +

DeepWalk:社会表征的在线学习

原文:DeepWalk: Online Learning of Social Representations
源码:phanein/deepwalk

摘要

DeepWalk是一种学习网络中节点的隐式表征的新颖方法。这些隐式表征把社会关系编码到统计模型易于使用的连续的向量空间中。DeepWalk使用从删减的随机游走获得的局部信息,通过游走等价句子学习出隐式表征。DeepWalk还是可扩张的,它是一个构建增量结果的在线学习算法,并且是并行的。这些特性使其广泛适用于实际应用,如网络分类或异常检测。

问题定义

考虑将社会网络成员分成若干类,令\(G=(V, E)\),其中\(V\)代表网络中的成员,\(E\)代表它们的连接,\(E\in(V\times V)\)且\(G_L=(V, E, X, Y)\)是部分标注的社会网络,满足\(X\in\mathbb{R}^{|V|\times S}\),\(S\)是每个特征向量空间的大小,\(Y\in\mathbb{R}^{|V|\times |\mathcal{Y}|}\),\(\mathcal{Y}\)是标签集。
在传统机器学习分类环境中,目标是学习一个从\(X\)的元素到标签集\(\mathcal{Y}\)的假定映射\(H\)。在这种情况下,可以利用有关嵌入到结构\(G\)的实例依赖的重要信息来取得较好的效果。
本文提出一种捕获网络拓扑信息的方法,在不把标签空间作为特征空间的一部分的情况下,使用无监督方法学习独立于标签分布的图结构特征。这种将结构表征和标签任务的分离避免了发生在迭代方法上的级联错误。此外相同的表征还可以用于考虑网络的多分类问题。
本文目标是学习\(X_E\in\mathbb{R}^{|V|\times d}\),其中\(d\)是潜在的维数。这些低维表示是分散的,表示每个社会现象在维度子集的压缩,并且每个维度贡献一个在空间上压缩的社会概念的子集。使用这些结构特征将增加属性空间来帮助确定分类。这些特征是普遍的,并可以用于任何分类算法(包括迭代法)。

学习社会表征

尝试根据以下特点学习社会表征:

  • 普适性:真实社会网络是不断进化的,新的社会关系不需要再次重复学习过程。
  • 团体性:隐式维度间的距离应当表示网络中相关成员的社会相似性。这样可以在网络中实现普遍化。
  • 低维性:当标记数据很少时用低维模型能更好地概括、加快收敛和推断。
  • 连续性:需要隐式表征在连续空间上建模部分社团关系。为了发现社团关系的细微差别,连续表征有健壮的社团间的平滑边界。

随机游走

把以节点\(v_i\)为起点的随机游走记作\(\mathcal{W}_{v_i}\)。随机游走是一个由随机变量\(\mathcal{W}_{v_i}^1,\mathcal{W}_{v_i}^2,\ldots,\mathcal{W}_{v_i}^k\)决定的随机过程,使得\(\mathcal{W}_{v_i}^{k+1}\)是从节点\(v_k\)的相邻节点中随机选择的。随机游走在内容推荐和社团发现中被用于衡量相似度。它们也是在输入图的大小的次线性时间内计算局部社团结构信息的一类输出敏感算法的基础。
由于这种与局部结构的联系,于是使用一个随机游走流(stream)作为从网络中提取信息的基本工具。除了捕获社团信息,使用随机游走作为算法的基础也提供了两个不错的属性:首先,局部探索容易并行化。许多随机游走(在不同的线程、处理器或机器上)可以同时探索一个图的不同部分。其次,依靠从短随机游走获得的信息,可以适应图形结构的小变化而不需要全局重新计算。可以用次线性时间在变化的区域进行新的随机游走来迭代更新学习的模型。

连接:幂定律

之前用在线随机游走作为捕获图结构的雏形,现在需要一种合适的方法来捕获这些信息。如果连通图的度分布遵循幂定律(即无尺度),观测到在节点出现在短随机游走中的频率也将遵循幂定律分布。
自然语言中的词频遵循类似的分布,语言建模技术可以解释这种分布行为。本文核心贡献在于可以重新设计用于建模自然语言的技术来建模网络中的社团结构。

语言建模

语言建模的目的是估计特定词序列出现在语料库的可能性。给定一个词序列:$$W_1^n=(w_0,w_1,\ldots,w_n)$$
其中\(w_i\in\mathcal{V}\)(词表),要在语料库上最大化\({\rm Pr} (w_n\mid w_0,w_1,\ldots,w_{n-1})\)。最近在表征学习中的工作集中在使用概率神经网络来构建超过原始目标的语言模型一般表征。
本文中提出了一种通过短随机游走来探索图的语言模型。这些游走可以被认为是一种特殊语言的短句和短语;直接模拟是估计在随机游走中访问过观测点\(v_i\)之前所有节点的可能性:$${\rm Pr}\big(v_i\mid (v_1,v_2,\ldots,v_{i-1})\big)$$
目标是学习隐式表征,不只是节点共现的概率分布,因此我们引入映射函数\(\Phi:v\in V\mapsto\mathbb{R}^{|V|\times d}\)。映射\(\Phi\)表示与图中每个节点\(v\)相关的隐式社会表征。实际上用自由参数的矩阵\(|V|\times d\)来表示\(\Phi\)。于是问题变成了估计可能性:$${\rm Pr}\bigg(v_i\mid\big(\Phi(v_1),\Phi(v_2),\ldots,\Phi(v_{i-1})\big)\bigg)$$
然而随着游走距离的增长,计算这种条件概率变得不可行。于是在节点表征建模上产生了优化问题:$$\min\limits_{\Phi}\quad-\log{\rm Pr}\big(\{v_{i-w},\ldots,v_{i+w}\}\setminus v_i\mid\Phi(v_{i})\big)$$
用这个目标函数构建捕获节点间在局部图结构中共享相似性的表征。具有相似邻居的顶点将获得相似的表征,可以在机器学习任务上进行一般化。
结合缩短的随机游走和语言模型,制定了一种满足所有期望属性的方法。该方法生成存在于连续向量空间中的低维社会网络表征。它的表征编码了社团成员的隐含形式,并且由于该方法输出有用的中间表征,它可以适应变化的网络拓扑。

方法

概述

在任何语言建模算法中,唯一需要的输入是语料库和词表\(\mathcal{V}\)。DeepWalk考虑一组在自身语料库中减短的随机游走,且图节点作为自己的词表(\(\mathcal{V} = V\))。尽管在训练前已知\(V\)和随机游走节点的频率分布是有益的,但对于算法而言并不是必要的。

算法:DeepWalk

该算法由两个主要部分组成:随机游走生成器更新过程。随机游走生成器在图\(G\)上均匀采样一个随机节点\(v_i\)作为随机游走\(\mathcal{W}_i\)的起点。每次游走都对上一个访问到的节点均匀随机采样一个邻节点,直到达到最大长度(\(t\))。尽管将实验中的随机游走的长度设为定值,但对于相同长度的随机游走来说没有任何限制。这些游走可能会重新开始(回到起点),但是初步结果没有显示重新开始的任何优势。在实践中对每个起始节点指定了一些长度为\(t\)的随机游走\(\gamma\)。

DeepWalk

算法1中的3~9行是方法的核心。外层循环指定循环次数\(\gamma\),从每个顶点开始随机游走。每次迭代都会在数据中形成一个pass,并且对pass上的每个节点采样一个游走。在每次pass开始时先生成一个随机排序来遍历节点。虽不是严格要求的,但能加速随机梯度下降的收敛。
在内层循环迭代图上的所有节点。对每个节点\(v_i\)生成一个随机游走\(|\mathcal{W}_{v_i}|=t\),然后使用mikolov2013efficient中提出的SkipGram算法按照上面的目标函数更新表征。

SkipGram

SkipGram

SkipGram是一种可以使句子中出现在窗口\(w\)中的单词之间共现率最大化的语言模型。它使用独立假设近似目标函数的条件概率:$${\rm Pr}\big(\{v_{i-w},\ldots,v_{i+w}\}\setminus v_i\mid\Phi(v_{i})\big)=\prod_{j=i-w\atop j\neq i}^{i+w}{\rm Pr}\big(v_j\mid\Phi(v_i)\big)$$
算法2迭代窗口\(w\)(1~2行)内随机游走中的所有可能组合。映射每个顶点\(v_j\)到其当前表征向量\(\Phi(v_j)\in\mathbb{R}^d\)。

给定\(v_j\)的表征,要最大化游走中邻节点的概率(第3行),可以使用几种选择分类器来学习这种后验分布。例如使用逻辑回归建模前面的问题将导致大量的标签。这种模型需要跨集群的庞大的计算资源。为了避免这种必要性并加快训练时间,用Hierarchical Softmax来逼近概率分布。

Hierarchical Softmax

给定\(u_k\in V\),计算第3行的\({\rm Pr}\big(u_k\mid \Phi(v_j)\big)\)是不可行的。计算配分函数(归一化因子)代价很高,所以使用Hierarchical Softmax分解条件概率。将节点分配到二叉树的叶子,把预测问题转化为最大化层次结构中特定路径的概率。

如果把到节点\(u_k\)的路径看作树节点序列\((b_0,b_1,\ldots,b_{\lceil\log|V|\rceil})\),\((b_0=root,b_{\lceil\log|V|\rceil}=u_k)\),那么:$${\rm Pr}\big(u_k\mid\Phi(v_j)\big)=\prod_{l=1}^{\lceil\log|V|\rceil}{\rm Pr}\big(b_l\mid\Phi(v_j)\big)$$
现在\({\rm Pr}\big(b_l\mid\Phi(v_j)\big)\)可用分配给节点\(b_l\)的父节点二项分类器建模:$${\rm Pr}\big(b_l\mid\Phi(v_j)\big)=1/(1+e^{-\Phi(v_j)\cdot\Psi(b_l)})$$
其中\(\Psi(b_l)\in\mathbb{R}^d\)是分配给\(b_l\)父节点的表征。这样就把计算\({\rm Pr}\big(u_k\mid\Phi(v_j)\big)\)的复杂度从\(O(|V|)\)降到了\(O(\log|V|)\)。
可以通过在随机游走中为高频节点分配较短的路径来加快训练过程。霍夫曼编码就用于减少树中高频元素的访问时间。

优化

模型参数集是\(\theta=\{\Phi,\Psi\}\),其中每个大小都是\(O(d|V|)\)。用随机梯度下降法(SGD)来优化这些参数(算法2第4行)。使用反向传播算法估计导数。SGD的学习率\(\alpha\)在训练开始时初始设置为\(2.5%\),然后根据节点数线性下降。

并行性

社会网络随机游走的节点和语言中的词汇频率分布都遵循幂定律,导致低频节点距离较长,因此影响\(\Phi\)的更新在本质上是稀疏的。于是在多协作的情况下使用异步随机梯度下降(ASGD)。鉴于更新是稀疏的,且没有加访问模型共享参数的锁,ASGD将达到最佳收敛率。尽管实验是在一台机器上用多线程进行,但已经证明这种技术具有高度可扩展性,并可用于超大规模的机器学习。

算法变型

该方法的一个有趣的变型是流式(streaming)方法,可以在不了解整个图的情况下实现。在这种变型中图中的小游走直接传递到表征学习代码并且直接更新模型。还需要对学习过程进行一些修改。首先,使用衰减学习率可能不再可行,因为假设了对总语料库大小的认知。相反可以将学习率\(\alpha\)初始化为一个小常量。这将需要更长时间去学习,但在某些应用中可能更有价值。其次,不一定要再建立一个参数树。如果\(V\)的基数已知(或有界),可以为其最大值构建Hierarchical Softmax树。首次看到节点可以为其分配一个叶。如果能够先验估计节点频率,还可以使用霍夫曼编码来降低高频元素的访问时间。

非随机游走

一些图被作为与一系列元素交互的代理而创建(如页面导航)。当通过这种非随机游走的流建图时,可以使用此过程直接提供建模。以这种方式采样的图不仅捕获与网络结构相关的信息,还有遍历路径的频率。
这种变型还包括语言模型。句子可被看作在经过适当设计的语言网络进行有目的地游走,并且像SkipGram这样的语言模型是为捕获这种行为而设计的。
这种方法可以与流式方法结合,在不断进化的网络上无需构建全图而训练特征。用这种技术维护表征可以无需处理网络规模图而实现网络规模分类。

Read More +

PandoraBox路由器的IPv6穿透

2015年年底的时候学校升级了校园网的计费系统,当时用的路由器(大概由于配置姿势不对)一直获取不到IPv6地址。好在之后每人每月给了免费5G流量,电脑直接使用IPv6的代理,免费流量只给手机用还算熬的过去,所以就一直没再折腾。直到前些天入手了一个斐讯K2,所以想碰碰运气,结果乱搞了一通就成功了。

最开始拿到学校插上网线总是未连接状态,刷了好几种固件都没用,最后发现是网线水晶头接触不良。由于OpenWrt对K2的支持还不是很好,可能出现WiFi不稳定的状况,最后我还是刷了一个PandoraBox,但方法是和OpenWrt通用的。

获取IPv6地址

首先更改网络-接口设置。WAN选用DHCP客户端即可,WAN6要用默认的DHCPv6客户端,但是要改成强制请求IPv6地址并禁用请求指定长度的IPv6前缀:

WAN6

这时可以重新连接一下看看WAN6是否出现了IPv6地址,如果依旧没有,可以按照官方文档所说将wanipv6选项设为1

uci set network.wan.ipv6='1'
uci commit network

再重新连接应当就能获取到IPv6地址了:

接口总览

安装NAT6

最早的时候使用6relayd来实现IPv6网络穿透的,但是这个软件很早之前就被弃用了,现在当然不能再使用这么古老的方法了,所以就在网上寻找新的方法,最后根据官方文档发现了通过NAT6使设备获取IPv6地址的方法。

首先安装必要的软件:

opkg update
opkg install kmod-ipt-nat6

然后把IPv6 ULA前缀改成d开头的:

uci set network.globals.ula_prefix="$(uci get network.globals.ula_prefix | sed 's/^./d/')"
uci commit network

官方文档对这个操作的解释是默认前缀是非全局路由的地址,大多路客户端在没有全局IPv6地址的情况下只有IPv4地址,所以需要将前缀改成未使用过的全局地址的样子

接下来更改DHCP服务器的设置:

uci set dhcp.lan.ra_default='1'
uci commit dhcp

之后修改/etc/sysctl.conf,将以下内容加进去:

1
2
3
4
net.ipv6.conf.default.forwarding=2
net.ipv6.conf.all.forwarding=2
net.ipv6.conf.default.accept_ra=2
net.ipv6.conf.all.accept_ra=2

最后在/etc/firewall.user添加防火墙规则:

1
ip6tables -t nat -I POSTROUTING -s $(uci get network.globals.ula_prefix) -j MASQUERADE

重启路由器后再次连接看电脑是否已经得到路由器分配的IPv6地址了:

Network

安装ShadowSocks

安装ShadowSocks和luci界面:

opkg update
opkg install shadowsocks-libev
opkg install luci-app-shadowsocks

然后在服务-ShadowSocks中配置服务器信息并启用ss-redir模式即可:

ShadowSocks

Read More +

路由器刷breed引导第三方固件

之前早就听说斐讯路由器有个0元购活动,一直没往心里去;直到昨天看到XForce大神也撸了一台,于是江信江疑跟风在二手东下了一单,结果今天就上船了,但愿30天内别翻船,才算真的免费拿到手啊。

收货后先别急刮K码,刮开了万一有毛病就不给退换了。先登192.168.2.1配置一下网络,发现原厂固件功能还算齐全,一般情况都够用了。但是据说有人发现路由器暗地里在给某些服务器传送着数据,恐怕有信息泄露的风险,当然刷一个第三方固件更保险一些了。

我拿到的斐讯K2硬件版本是A2,固件版本是22.4.5.42。听闻说更高版本的固件刷Breed非常麻烦,我还比较庆幸原厂版本比较低,然而依然要降级。

刷入breed

下载工具

首先下载huzibbs大神制作的路由器刷breed Web助手通用版城通网盘),可以实现一键刷telnet、ssh、breed。

然后将路由器LAN口(推荐使用LAN4口)与Windows电脑用网线相连(一定不要使用WiFi),然后长按路由器Reset键5秒恢复出厂设置。之后可以再访问一下192.168.2.1看是不是初始状态。

开始刷机

如果一切正常就以管理员身份运行路由器刷breed Web助手通用版

路由器刷breed Web助手通用版

配置如图即可,注意其中刷机方案一定要选择斐讯k1,k1s,k2全自动方案,然后点击开始刷机即可。

开始刷机前工具作者建议先手动禁用除以太网以外的其他网络连接。由于工具中途会调用另外几个程序,所以中途如果系统弹出了提示框允许即可,顺便设成不再提醒;如果弹窗导致刷机失败了重新再来一遍基本就可以了。成功后请忽略下面的步骤,直接进入下一小节。

如果一直失败,出现类似ssh无法连接的错误,因为此时固件应当已经降级到有ssh的测试版本了,也可以手动ssh进去(用户名和密码都是root)执行刷机步骤,但此时操作一定要谨慎,否则极有可能变砖!

下载路由器对应的breed包(如breed-mt7620-phicomm-psg1208.bin)下载到路由器,切记一定不要选错,然后执行:

mtd unlock Bootloader
mtd -r write breed-mt7620-phicomm-psg1208.bin Bootloader

执行完后应当会自动重启。这种方法理论上可行,具体细节有待验证,请谨慎使用。

重启路由器

几分钟之后刷机自动完成,按照工具提示等待2分钟以后再断电。在重新通电前先按住Reset键再接通电源,持续按住Reset键约5秒钟再松手。不出意外此时路由器应该进入了breed引导,这时访问192.168.1.1应当就进入了Breed Web 恢复控制台

Breed Web 恢复控制台

刷入第三方固件

固件备份

进入控制台后,先到固件备份里将EEPROM编程器固件备份一下:

固件备份

恢复出厂设置

然后到恢复出厂设置将固件恢复Config区(公版)

恢复出厂设置

固件更新

最后到固件更新选择要刷的固件上传即可:

固件更新

目前K2可刷的固件有很多,包括OpenWrtPandoraBox等等。虽然OpenWrt还没有放出针对K2的Release版本,但由于它用的是ramips架构的mt7620芯片,所以一般mt7620芯片的路由器固件是通用的,于是我就刷了个小米路由器的固件

OpenWrt

而潘多拉盒子已经有了K2的稳定版固件。另外给K2装软件时记得下载ramips架构的ipk包。

Read More +

树莓派SPI驱动OLED屏幕

曾经在B站看到过有人用树莓派连接OLED屏幕播放Bad Apple(有屏幕的地方就有Bad Apple),想到前些年在智能车打酱油时遗留下的一块128*64的OLED屏幕,就想给树莓派加一个monitor。

连接引脚

物理编号

屏幕上有7个引脚,与树莓派用母对母杜邦线连接,接法如下表:

OLED引脚 功能 树莓派引脚 编号
GND GND 25
VCC 3.3V PWR 17
D0 SCLK GPIO 11 23
D1 MOSI GPIO 10 19
RST GPIO 17 11
DC GPIO 27 13
CS CS0 GPIO 8 24

安装依赖

在驱动屏幕之前要先启用SPI:

sudo raspi-config

然后选择Advanced Options里的SPI并启用它,然后执行sudo reboot重启。重启后执行ls /dev | grep spi,如果显示:

spidev0.0
spidev0.1

就说明设置生效了。

先安装一些要用到的Python模块:

sudo apt-get install build-essential python-dev python-pip
sudo apt-get install python-imaging python-smbus
sudo pip install RPi.GPIO

然后克隆SPI的驱动模块并安装:

git clone https://github.com/adafruit/Adafruit_Python_SSD1306.git
cd Adafruit_Python_SSD1306
sudo python setup.py install

编写脚本

网上有人给出了Python版的测试Demo:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#!/usr/bin/python/
# coding: utf-8
import time
import Adafruit_GPIO.SPI as SPI
import Adafruit_SSD1306
import Image
import ImageDraw
import ImageFont
# Raspberry Pi pin configuration:
RST = 17
# Note the following are only used with SPI:
DC = 27
SPI_PORT = 0
SPI_DEVICE = 0
# 128x64 display with hardware SPI:
disp = Adafruit_SSD1306.SSD1306_128_64(rst=RST, dc=DC, spi=SPI.SpiDev(SPI_PORT, SPI_DEVICE, max_speed_hz=8000000))
# Initialize library.
disp.begin()
# Clear display.
disp.clear()
disp.display()
# Create blank image for drawing.
# Make sure to create image with mode '1' for 1-bit color.
width = disp.width
height = disp.height
image = Image.new('1', (width, height))
# Get drawing object to draw on image.
draw = ImageDraw.Draw(image)
# Draw a black filled box to clear the image.
draw.rectangle((0,0,width,height), outline=0, fill=0)
# Draw some shapes.
# First define some constants to allow easy resizing of shapes.
padding = 1
top = padding
x = padding
# Load default font.
font = ImageFont.load_default()
# Alternatively load a TTF font.
# Some other nice fonts to try: http://www.dafont.com/bitmap.php
#font = ImageFont.truetype('Minecraftia.ttf', 8)
draw.text((x, top), 'This is first line', font=font, fill=255)
draw.text((x, top+10), 'This is second line', font=font, fill=255)
draw.text((x, top+20), 'This is third line', font=font, fill=255)
draw.text((x, top+30), 'This is fourth line', font=font, fill=255)
draw.text((x, top+40), 'This is fifth line', font=font, fill=255)
draw.text((x, top+50), 'This is last line', font=font, fill=255)
# Display image.
disp.image(image)
disp.display()

如果运行它能正常显示就可以编写自己的脚本了。参考这个Demo我又撸了一个显示系统实时信息的脚本:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#!/usr/bin/python/
# coding: utf-8
import os
import time
import socket
import fcntl
import struct
import requests
import Adafruit_GPIO.SPI as SPI
import Adafruit_SSD1306
import Image
import ImageDraw
import ImageFont
def raminfo():
with open('/proc/meminfo') as f:
total = float(f.readline().split()[1])
free = float(f.readline().split()[1])
return format((total-free)/total, '.1%')
def diskinfo():
st = os.statvfs('/')
total = float(st.f_blocks * st.f_frsize)
used = float(st.f_blocks - st.f_bfree) * st.f_frsize
return format(used/total, '.1%')
def cpuinfo():
with open('/proc/stat') as f:
info = f.readline().split()
t0 = float(info[1]) + float(info[2]) + float(info[3])
s0 = t0 + float(info[4]) + float(info[5]) + float(info[6]) + float(info[7])
time.sleep(0.033)
with open('/proc/stat') as f:
info = f.readline().split()
t1 = float(info[1]) + float(info[2]) + float(info[3])
s1 = t1 + float(info[4]) + float(info[5]) + float(info[6]) + float(info[7])
return format((t1-t0)/(s1-s0), '.1%')
def cputemp():
with open('/sys/class/thermal/thermal_zone0/temp') as f:
temp = float(f.readline())
return format(temp/1000, '.1f')
def wifiinfo():
with open('/proc/net/wireless') as f:
f.readline()
f.readline()
info = f.readline().split()
return info[3][:-1]
def get_ip_address(ifname):
s = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
return socket.inet_ntoa(fcntl.ioctl(
s.fileno(),
0x8915, # SIOCGIFADDR
struct.pack('256s', ifname[:15])
)[20:24])
IP = requests.get('http://ip.3322.net').text
# Raspberry Pi pin configuration:
RST = 17
DC = 27
SPI_PORT = 0
SPI_DEVICE = 0
# 128x64 display with hardware SPI:
disp = Adafruit_SSD1306.SSD1306_128_64(rst=RST, dc=DC, spi=SPI.SpiDev(SPI_PORT, SPI_DEVICE, max_speed_hz=8000000))
# Initialize library.
disp.begin()
# Clear display.
disp.clear()
while True:
disp.display()
# Create blank image for drawing.
width = disp.width
height = disp.height
image = Image.new('1', (width, height))
# Get drawing object to draw on image.
draw = ImageDraw.Draw(image)
# Initialize background.
draw.rectangle((0,0,width,height), outline=0, fill=0)
padding = 1
top = padding
x = padding
font = ImageFont.load_default()
draw.text((x, top), time.strftime(" %Y-%m-%d %H:%M:%S ",time.localtime(time.time())), font=font, fill=255)
draw.text((x, top+14), 'disk:' + diskinfo() + ' RAM:' + raminfo(), font=font, fill=255)
draw.text((x, top+24), 'temp:' + cputemp() + 'C CPU:' + cpuinfo(), font=font, fill=255)
draw.text((x, top+34), 'signal:' + wifiinfo() + 'dBm', font=font, fill=255)
draw.text((x, top+44), 'LAN:' + get_ip_address('wlan0'), font=font, fill=255)
draw.text((x, top+54), 'WAN:' + IP, font=font, fill=255)
# Display image.
disp.image(image)
disp.display()

效果如下:

开机启动

先新建一个Unit配置文件:

sudo vim /etc/systemd/system/oled.service

内容如下:

1
2
3
4
5
6
7
8
9
10
[Unit]
Description=oled autostart
[Service]
Type=idle
ExecStart=/usr/bin/python /home/pi/oled.py
Restart=always
[Install]
WantedBy=multi-user.target

然后启动并加入启动项:

sudo systemctl daemon-reload
sudo systemctl start oled
sudo systemctl enable oled
Read More +