Hexo博客使用MathJax公式

最近手贱将Hexo的博客的版本升到了3.8.0,顺便将npm组件也都升级了。一开始没有发现什么问题,后来打开一篇带公式的文章发现里面的部分MathJax公式渲染失败了。想到之前曾经因为Markdown里面的下划线_表示斜体,和MathJax里的下标冲突了,之前改过的node_modules被更新覆盖了,这次索性重新搞一遍。

更换渲染引擎

卸载原来的hexo-renderer-marked,换成专门对MathJax魔改过的hexo-renderer-kramed(注意kram这个单词的拼写):

npm uninstall hexo-renderer-marked --save
npm install hexo-renderer-kramed --save

再安装hexo-renderer-mathjax渲染器:

npm install hexo-renderer-mathjax --save

更改字符集

为了避免语义冲突,修改node_modules/kramed/lib/rules/inline.js文件的escapeem

1
2
//escape: /^\\([\\`*{}\[\]()#$+\-.!_>])/,
escape: /^\\([`*\[\]()#$+\-.!_>])/,

1
2
//em: /^\b_((?:__|[\s\S])+?)_\b|^\*((?:\*\*|[\s\S])+?)\*(?!\*)/,
em: /^\*((?:\*\*|[\s\S])+?)\*(?!\*)/,

更改cdn链接

修改node_modules/hexo-renderer-mathjax/mathjax.html的最后一行,将http改成https

1
2
<!--script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script-->
<script src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>

这样是为了避免在网站为https协议时请求http的内容时被浏览器block。使用hexo s预览是否已生效。

Read More +

路由器TTL刷机救砖

之前偶然拿到一台大麦DW22D路由器,应该是之前的租客办长城宽带赠送的,登入管理界面发现里面是基于长城宽带深度定制的系统。

上了恩山查了一下发现这个机器的硬件还可以,并且可以无拆机刷入padavan固件,所以就开始按照教程刷机。

无拆机刷机

以下步骤参考恩山的教程

开启ssh

本方法主要依靠后门页面的命令注入漏洞,步骤如下:

注入新密码

电脑连上路由器(最好有线方式),访问http://192.168.10.1/upgrade.html,在页面上打开ssh的选项,密码框内输入:

123 | echo 6c216b27c8c9b051106c969e2077d4e9 > /ezwrt/bin/upgrade_passwd 

注意末尾有空格。这里的md5值是echo dfc643 | md5算出来的,里面的dfc643是发现这个方法大佬的用户名,此处的密码是可以随便改的。然后点确定提交,此时会提示密码错误,可以忽略。

注入ssh公钥

再次访问http://192.168.10.1/upgrade.html,同样选择打开ssh,密码框内输入:

123 | echo YOUR_ID_RSA_PUB > /etc/dropbear/authorized_keys 

同样注意末尾有空格。其中YOUR_ID_RSA_PUB替换为自己的公钥,即电脑上~/.ssh/id_rsa.pub的内容。再次点确定提交,此时还会提示密码错误,也可以忽略。

开启ssh

最后一次访问http://192.168.10.1/upgrade.html,选择打开ssh,密码为dfc643(如果在第一步注入密码时用了别的密码,此处输入相应的密码),最后点确定提交,提示start ssh success表示已经开启ssh。

这样就可以ssh [email protected]登录路由器了。

刷入breed

breed是hackpascal独立开发的一个全新的 Bootloader。DW22D路由器对应的版本是breed-mt7620-reset13.bin

下载好后将其传入路由器的/tmp目录下备用:

scp breed-mt7620-reset13.bin [email protected]:/tmp

然后在路由器上执行:

mtd_write -x mIp2osnRG3qZGdIlQPh1 -r write /tmp/breed-mt7620-reset13.bin bootloader

这样应该就能将breed刷入bootloader,然后就可以随意刷firmware了。

然而我手残将最后的bootloader打成了firmware,也就是将breed刷入了firmware分区,导致路由器进不去系统了,也才有了后面的ttl救砖。

TTL刷机

以下步骤参考恩山的教程

USB转TTL

为了让路由器硬件和电脑相连,需要一个USB转TTl模块,随便在马云家买一个最便宜的就能用,我就买了一个ch340g芯片的模块。

TTL驱动

然后在github找了驱动安装上(这里给的是Mac电脑的驱动,Windows的驱动一般卖家都会提供,网上找找也都有)。

重启后打开网络偏好可以看见多了一个串行接口:

将USB转TTL模块插在电脑上,在/dev目录下会出现名字类似cu.usbserial-1410的设备,说明识别成功。

TTL连接

在如图位置焊上引脚(GND那个孔不用焊):

然后用杜邦线将三个引脚和USB转TTL模块相连。

开启TFTP

将电脑用网线和路由器lan口连接,设置有线连接为手动模式,按图修改参数:

参考macOS启用TFTP服务,将breed-mt7620-reset13.bin放到TFTP目录下,将TFTP的地址选择有线ip(即上面设置的10.10.10.3)。

刷机

一切就绪后,可以连接路由器开始刷机。

登录路由器

使用screen连接未通电的路由器,波特率为57600:

screen /dev/cu.usbserial-1410 57600

此时终端里什么也没有。然后给路由器通电,此时会打印出很多东西,最后出现一些选项,立刻(5秒内)按数字键9选择TFTP刷机。

刷入breed

之后会让确认device IP(路由器地址)和server IP(电脑地址),确认无误后会提示输入要刷入的文件名,输入breed-mt7620-reset13.bin回车就开始刷入了。

刷完后断电按住复位键通电并长按5秒即可进入breed:

Read More +

macOS启用TFTP服务

TFTP在路由器刷机中被普遍使用,因为其协议简单,可以通过少量存储器实现。在PC上打开Windows功能就可启用。其实macOS也自带TFTP,只不过是没有自动启用。

TFTP默认使用的目录是/private/tftpboot,首先给其增加权限:

sudo chmod -R 777 /private/tftpboot

然后启用服务:

sudo launchctl load -F /System/Library/LaunchDaemons/tftp.plist
sudo launchctl start com.apple.tftpd

如果觉得命令行方式不直观,macOS上也有类似Windows上的Tftpd32的应用TFTP Server,直接下载安装即可:

TFTP的目录也可以在应用中修改。

Read More +

搭建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证书配置

Let’s Encrypt是一个于2015年三季度推出的数字证书认证机构,旨在以自动化流程消除手动创建和安装证书的复杂流程,并推广使万维网服务器的加密连接无所不在,为安全网站提供免费的SSL/TLS证书。

官方建议用EFF开发的Certbot ACME客户端签发证书。

安装certbot

CentOS可以通过yum直接安装:

yum install certbot

如果yum找不到certbot,建议安装或重装epel-release

获取证书

用以下命令对相应的若干域名生成证书:

certbot certonly --webroot --email [email protected] -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
55
56
57
58
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";

add_header Strict-Transport-Security max-age=31536000;

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";

add_header Strict-Transport-Security max-age=31536000;

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配置就可以了。可以到SSL Labs检测一下SSL状态。使用上述配置一般可以获得A+评分,也可以使用Mozilla SSL Configuration Generator生成配置。

评分

证书续期

Let’s Encrypt的证书有效期为90天,所以需要定期更新,离过期30天以内可以续期:

certbot renew && nginx -s reload
Read More +

Hexo博客部署到VPS

Hexo的博客本身之前是挂在github.io的,但是想用自己的域名,本来配一个CNAME就可以了,但是再想使用https就很麻烦了,索性就在VPS上也部署一份,自己运行维护。

服务器hook配置

首先要装好Nginx,然后在/usr/share/nginx下新建一个临时目录:

mkdir blog.git

然后在里面创建git裸库:

cd blog.git
git init --bare
cd hooks

之后就可以在hooks目录里配置自动执行的脚本了,编辑post-receive

1
2
3
4
5
6
#!/bin/bash -l
GIT_REPO=/usr/share/nginx/blog.git
PUBLIC_WWW=/usr/share/nginx/blog
rm -rf $PUBLIC_WWW
git clone $GIT_REPO $PUBLIC_WWW
rm -rf $PUBLIC_WWW/.git

记得给这个脚本添加执行权限:

chmod +x post-receive

通过这个hook就可以将新生成的博客放到/usr/share/nginx/blog下了。

修改部署配置

编辑本地Hexo仓库的_config.yml,在deploy下面增加一个新的配置,参考官方文档

1
2
3
- type: git
repo: [email protected]_VPS_IP:/usr/share/nginx/blog.git
branch: master

保存后使用hexo d命令重新部署,在这之前确认一下是否已经配置过VPS的公私钥登录。部署完成后到VPS的/usr/share/nginx下看是否出现blog目录,且里面是Hexo生成的页面内容。

服务器Nginx配置

进入/etc/nginx/conf.d目录新建一个配置文件blog.conf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
server {
listen 80;
server_name www.shintaku.cc;

location / {
root /usr/share/nginx/blog;
index index.html;
}

error_page 404 /404.html;

error_page 500 502 503 504 /50x.html;
location = /50x.html {
root /usr/share/nginx/html;
}
}

保存后用nginx -s reload重载配置,打开上面配置的域名(首先应该配置过解析)应该就能访问Hexo博客了。这样只是http访问,之后可以按需配置https,这里不再赘述。

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最大的缺点在于大数据集上的计算复杂度高。

比较不同模型结构,首先用完整的训练模型所需要的参数的数量来定义模型计算的复杂度。接下来试图最大化精度,同时最小化计算复杂度。对于下面所有模型,训练复杂度遵循:

其中\(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\)维的。因此每个训练实例的计算复杂度为:

其中\(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模型对于一个训练实例的时间复杂度是:

其中词表征\(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个历史词作为输入取得了最优的性能,其中优化目标是能准确对当前词分类。训练复杂度为:

将这个模型记为CBOW。与标准词袋模型不同,它使用上下文的连续分布式表征。注意输入层与投影层之间的权重矩阵与NNLM一样是所有词位置共享的。

连续Skip-Gram模型

Skip-gram

第二个结构与CBOW类似,不同的是CBOW基于上下文预测当前词,这个模型尝试根据同一句子中的另外一个词来最大化一个词的分类。更准确的说法,使用当前词作为有连续投影层的对数线性分类器的输入,来预测词语所在当前词的前后范围。发现增加窗口的大小可以提高学习到的词向量的质量,但也增加了计算复杂度。因为离得越远的词通常与当前词越不相关,所以给那些离得较远的词较小的权重使得其被采样的概率变小。该结构的训练复杂度正比于:

其中\(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}\)表示的网络拓扑一致,在矩阵行列式上产生以下函数:

建模节点属性

定义社团\(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}\)的社团成员为结合节点和社团的属性提供了指导,有以下优化函数:

为了给每个社团选择最相关的属性,为矩阵\(\mathbf{C}\)的每列添加一个\(l_1\)稀疏范数。另外为了防止\(\mathbf{C}\)的一些列的值过大(每个社团都有一些有意义的属性),对\(\mathbf{C}\)有约束\(\sum_{j=1}^k|\mathbf{C}(:,j)|_1^2\),产生以下目标函数:

其中\(\alpha\)是权衡第一误差项和第二稀疏项的非负参数。

统一模型

通过结合网络拓扑模型和节点属性模型的目标函数,有以下完整函数:

其中\(\beta\)是调整网络拓扑权重的正参数。

优化

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

U问题

当固定\(\mathbf{C}\)更新\(\mathbf{U}\)时,需要解决以下问题:

为此为\(\mathbf{U}\)上的非负约束引入拉格朗日乘数矩阵\(\mathbf{\Theta}=(\Theta_{ij})\),得到以下等价目标函数:

将对\(\mathbf{U}\)的导数\(L(\mathbf{U})\)设为0,有:

根据对非负\(\mathbf{U}\)的卡罗需-库恩-塔克条件(KKT条件)有如下等式:

这是解收敛时必须满足的固定点方程。给定\(\mathbf{U}\)的初始值,\(\mathbf{U}\)的连续更新为:

为了保证\(\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

    函数

    是\(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}\)时,需要解决以下问题:

它等价于如下优化问题:

其中\(\mathbf{e}_{1\times m}\)是一个所有分量为1行向量,\(\mathbf{0}_{1\times k}\)是0向量。因此对上面的问题有以下规则:

其中\(\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\)的连接概率为:

其中\(\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}}\)。为了保留一阶接近度,简单的方法是减小以下目标函数:

其中\(d(\cdot, \cdot)\)是两个分布之间的距离。减小两个概率分布的KL散度,用KL散度替换距离函数并去掉常量后得到:

注意一阶接近度仅适用于无向图。找到减小上式的\(\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\)的概率:

其中\(|V|\)是节点或环境的数量。对于每个节点\(v_i\),上式确定了环境上的条件分布。为保留二阶接近度,应当由低维表示确定条件分布来接近经验分布\(\hat{p_2}(\cdot|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\)并去掉常量后得到:

通过学习\(\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)\)的噪声分布取样多个负边,特别对每个边指定了以下函数:

其中\(\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}\)是:

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

通过边采样优化

简单的解决方案是将权为\(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\)间的权重是:

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

新节点

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

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

Read More +