计算复杂性计算复杂性 (Computational Complexity)是用于对一个问题求解所需的资源 (通常为空间和时间) 的度量。在评估一个算法的时候，除了算法本身的准确性以外，同时需要关注算法运行的时间以及占用的内存，从而根据实际情况选择合适的算法。函数的增长计算复杂性中的空间和时间的评估方法类似，在此我们更多的以时间复杂度为例。算法的运行时间刻画了算法的效率，对于一个输入规模为$n$的问题，定义一个算法求解该问题最坏情况下的运行时间为$T \left(n\right)$，我们可以使用一些渐进记号更加方便地对其进行描述。$\Theta$记号对于一个给定的函数$g \left(n\right)$，$\Theta \left(g \left(n\right)\right)$可以表示如下函数的集合：$$ \Theta \left(g \left(n\right)\right) = \left\{f \left(n\right): \exists c_1 > 0, c_2 > 0, n_0 > 0, s.t. \forall n \geq n_0, 0 \leq c_1 g \left(n\right) \leq f \left(n\right) \leq c_2 g \left(n\right) \right\} $$也就是说当$n$足够大时，函数$f \left(n\right ...继续阅读 (70)

本文的配套代码请参见这里，建议配合代码阅读本文。模型部署和服务调用对于做算法的同学，大家或多或少的更关心模型的性能指标多些，对于一些工程性问题考虑的较少。模型的部署是这些工程性问题中重要的一个，它直接关系到模型在生产系统的使用。一些成熟的机器学习框架会提供自己的解决方案，例如Tensorflow提供的Serving服务等。但很多情况下我们构建的工程可能不只使用了一种框架，因此一个框架自身的部署工具可能就很难满足我们的需求了。针对此类情况，本文介绍一个简单的准生产模型部署方案。简单是指除了模型相关代码之外的工程性代码量不大，这得益于将要使用的Flask框架。准生产是指这种部署方案应对一般的生产环境问题不大，对于高并发的场景可以通过横向扩容并进行负载均衡解决，但对于单次调用时效性要求较高的场景则需要另寻其他解决方案。本文方案的模型部署和服务调用框架如下图所示：其主要特性如下：服务端采用 Python 的 Flask 框架构建，无需使用其他外部服务。Flask 框架的微服务(Microframework) 特性使得服务端代码简洁高效。利用Gunicorn提供的高性能 Python WSGI HTTP UNIX Server，方便在服务端运行 Flask 应用。客户端和服务端之间采用RESTful API调用方式，尽管在性能上可能不及其他一些方案 (例如：基于 RPC 的解决方案等)，但其 ...继续阅读 (56)

Encoder-Decoder & Seq2SeqEncoder-Decoder 是一种包含两个神经网络的模型，两个网络分别扮演编码器和解码器的角色。Cho 等人1提出了一个基于 RNN 的 Encoder-Decoder 神经网络用于机器翻译。网络结构如下图所示：整个模型包含编码器 (Encoder) 和解码器 (Decoder) 两部分：Encoder 将一个可变长度的序列转换成为一个固定长度的向量表示，Decoder 再将这个固定长度的向量表示转换为一个可变长度的序列。这使得模型可以处理从一个可变长度序列到另一个可变长度序例的转换，即学习到对应的条件概率$p \left(y_1, \dotsc, y_{T'} | x_1, \dotsc, x_T\right)$，其中$T$和$T'$可以为不同的值，也就是说输入和输出的序列的长度不一定相同。在模型中，Encoder 为一个 RNN，逐次读入输入序列$\mathbf{x}$中的每个元素，其中 RNN 隐状态的更新方式如下：$$ \mathbf{h}_{\langle t \rangle} = f \left(\mathbf{h}_{\langle t-1 \rangle}, x_t\right) $$在读入序列的最后一个元素后 (通常为一个结束标记)，RNN 的隐状态则为整个输入序列的概括信息$\mathbf{c}$。Decod ...继续阅读 (53)

文本表示文本表示是计算机处理自然语言的核心，我们希望计算机能够同人类一样对自然语言能够实现语义层面的理解，但这并非易事。在中文和拉丁语系中，文本的直观表示就存在一定的差异，拉丁语系中词与词之间存在天然的分隔符，而中文则没有。I can eat glass, it doesn’t hurt me.我能吞下玻璃而不伤身体。所以，在处理中文之前我们往往需要对原始文本进行分词，在此我们不谈这部分工作，假设我们已经得到了分词完的文本，即我们后续需要处理的“词”。早期的词表示方法多采用独热编码 (One-Hot Encoding)，对于每一个不同的词都使用一个单独的向量进行表示。对于一个包含$n$个词的语料而言，一个词的向量表示$\text{word}_i \in \left\{0, 1\right\}^n$仅在第$i$的位置值为 1，其他位置的值均为 0。例如，我们可以将“父亲”表示为：$$ \left[1, 0, 0, 0, 0, 0, ...\right] \nonumber $$One-Hot Encoding 的表示方法十分简洁，但也存在着一些问题。维数灾难 (The Curse of Dimensionality)在很多现实问题中，我们仅用少数的特征是很难利用一个线性模型将数据区分开来的，也就是线性不可分问题。一个有效的方法是利用核函数实现一个非线性变换，将非线性问题转 ...继续阅读 (52)

文章部分内容参考了 Christopher 的博客Understanding LSTM Networks，内容翻译和图片重绘已得到原作者同意，重绘后的图片源文件请参见这里。发展史循环神经网络 (Recurrent Neural Network, RNN) 一般是指时间递归神经网络而非结构递归神经网络 (Recursive Neural Network)，其主要用于对序列数据进行建模。Salehinejad 等人1的一篇综述文章列举了 RNN 发展过程中的一些重大改进，如下表所示：Year1st AuthorContribution1990ElmanPopularized simple RNNs (Elman network)1993DoyaTeacher forcing for gradient descent (GD)1994BengioDifficulty in learning long term dependencies with gradient descend1997HochreiterLSTM: long-short term memory for vanishing gradients problem1997SchusterBRNN: Bidirectional recurrent neural networks1998LeCunHessian matrix app ...继续阅读 (45)

近来这大半年的工作感觉活活像一场清宫剧，对于我们这种一心只想撸代码，两耳不闻窗外事的人来说，确实太累了。从年初换了工作方向后，交接了所有之前的线上任务和系统，所以这次旅行格外的清净，没有一封报警邮件。北京已经入秋，走之前还很热，回来已凉意浓浓，去的路上天气格外的好。进去大皇宫不能衣冠不整，牛仔裤上有个洞，在门口买了条裤子套上，还挺配我的白衬衫，感觉满满的社会人气息 😎。发现中国人在外面很难 High 起来，油轮之上小姐姐唱着不同国家的歌曲，独独唱到中文歌的时候没有人上去跳。也许我们天生没有欧美人的开放，也不像中东朋友在国家内被束缚的太紧，不过感觉出来玩还是不要闷骚，把激情都释放出来才好。Pattaya 的水上市场虽然有商业景区的味道，但还是保留了很多当地的特色，水流两旁很多卖水果和小吃的小船。海边的日落很美，再来杯美酒，再来个佳人就更好了。只在金沙岛上呆了小半天，天公还算作美，早起下着小雨，上岛了雨就停了。想想上次下水游泳还是上初中时候的事情了，虽然不怎么太会游，但至少还能扑腾两下。下次再有机会来，一定直奔普吉岛，舒舒服服的在岛上呆上几天，别的啥也不干，就游游泳，晒晒太阳。To view this video please enable JavaScript, and consider upgrading to a web browser thatsupports ...继续阅读 (35)

本文为《娱乐至死》(Amusing Ourselved To Death) 的读书随想。在这本书中，作者Neil Postman的基本观点为推崇铅字文化，声讨电视文化。首先，我必须承认作者对电视文化的很多现象描述确实存在，我虽然也一直知道其存在，但却从未思考过其中的问题，这是这本书对我影响最多的地方。换言之，是书籍 (铅字文化) 能够让我更深入的思考问题，这也是作者所推崇的铅字文化的益处。同时，作者并没有否定电视文化作为娱乐本身的用途，这点我也是认同的。无论是电影，电视剧还是综艺节目，电视文化确实以一种五彩斑斓的形式丰富着我们的娱乐生活。但我认为作者对于两种不同文化的观点略微有些绝对和偏激，尤其是在书籍和电视 (不同的信息载体) 内容过剩的今天，我认为两者都存在精华和糟粕 (同时包括文化内容和娱乐内容)。我认为书籍和电视中文化和娱乐的界线也不是很明显，虽然我支持作者的不要将娱乐和一些严肃的事情 (例如：政治，宗教，教育等) 混在一起，但是我也不否能不能从电视文化中获取知识。我认为更重要的是对于信息的细粒度消化，在这个过程中比较重要的是思考和实践。作者在书的最前面提到：奥威尔担心我们憎恨的东西会毁掉我们，而赫胥黎担心的是，我们将毁于我们热爱的东西。在文末又再次呼应了这个观点：有两种方法可以让文化精神枯萎，一种是奥威尔式的 – 文化成为一个监狱，另一种是赫胥黎式的 &nda ...继续阅读 (40)

发展史卷积神经网络 (Convolutional Neural Network, CNN) 是一种目前广泛用于图像，自然语言处理等领域的深度神经网络模型。1998 年，Lecun 等人1提出了一种基于梯度的反向传播算法用于文档的识别。在这个神经网络中，卷积层 (Convolutional Layer) 扮演着至关重要的角色。随着运算能力的不断增强，一些大型的 CNN 网络开始在图像领域中展现出巨大的优势，2012 年，Krizhevsky 等人2提出了 AlexNet 网络结构，并在 ImageNet 图像分类竞赛3中以超过之前 11% 的优势取得了冠军。随后不同的学者提出了一系列的网络结构并不断刷新 ImageNet 的成绩，其中比较经典的网络包括：VGG (Visual Geometry Group)4，GoogLeNet5和 ResNet6。CNN 在图像分类问题上取得了不凡的成绩，同时一些学者也尝试将其应用在图像的其他领域，例如：物体检测789，语义分割10，图像摘要11，行为识别12等。除此之外，在非图像领域 CNN 也取得了一定的成绩13。模型原理下图为 Lecun 等人提出的 LeNet-5 的网络架构：下面我们针对 CNN 网络中的不同类型的网络层逐一进行介绍。输入层LeNet-5 解决的手写数字分类问题的输入为一张 32x32 像素的灰度图像 (Gray Sca ...继续阅读 (41)

写这么一篇主要是想自我分析一下和读书有关的毛病，写下来会让自己认识的深刻些。尤其是最近一年，书入库明显高于出库，导致未读完的书都快摆不下了。总结起来主要是两个问题：书买了，不看。书看了，看不完。买书先聊聊为啥买书，简单通俗的解释就是“想看”。我认为，这么回答一点毛病都没有，因为这是我们去探索这个未知的世界最容易的方式。古人云：“读万卷书，行万里路”，都是探索这个世界的方式，后来细查得知这句话源自于董其昌谈及绘画之道时所说1：画家六法，一曰气韵生动。气韵不可学，此生而知之，自然天授，然亦有学得处。**读万卷书，行万里路。**胸中脱去尘浊，自然丘壑内营，成立郛郭，随手写去，皆为山水传神。为什么说读书是其中最容易的方式呢？最主要就是经济实惠，你不需要太多的成本，包括财物和时间，当然是相对行万里路而言。这里谈及的书我不想把杂志和技术书籍囊括进来，于我而言，杂志是消磨零散时间的读物，例如：如厕，等车；而技术类的书籍有需要比较系统的整理和笔记，甚至需要反复去看和理解。其他书也可以反复看，有时候我会把喜欢的书再翻一遍，而且每一遍都会有新的发现。所以，想去买书至少能够说明你还有对知识的渴望和对未知探索的兴趣。这点我认为很重要，如果你连念想都没了，那就什么都没了。囤书囤书，就是买得多了，而且略微上瘾，想着可能买了就等于已经把其中的知识吃进脑子了吧。这点和我办健身卡很像，感觉卡办了，八块腹肌就有了似的 ...继续阅读 (34)

最近是看了 Youtube 上Wong Fu Productions的一个系列视频Yappie，一下子把脑子中包括很久之前的一些思考就全都串联回忆起来了，所以就写了本文，把这些凌乱的思考拼凑起来。截止到本文写完，Yappie 已经出了两集，视频可能需要梯子，为了不影响理解，简单勾勒一下剧情。主角是一个名叫 Andrew 的亚裔美国人，他和女友 (当然后面知道才没交往多久，然后就分手了) 去听了一个关于美国亚裔 (Aisan Americans) 的一些特殊的境遇问题的 Talk Show。但 Andrew 似乎对这场演讲并不感冒，中途手机中球赛的声音打断了演讲，并被演讲者问及了姓名。Andrew 告知了姓名，演讲者随即用个玩笑回应了他的不礼貌打断，说一个美国亚裔中有 1/13 的概率叫 Andrew，有 1/5 的概率会是一名工程师，会来自于 San Gabriel Valley，喜欢篮球，Boyz II Men和宝马 (然而这一系列看似玩笑的猜测，后面剧情验证，他就是这样的一个 Andrew)。演讲过后 Andrew 的女友和演讲者做着进一步的沟通，Andrew 过去为自己的不礼貌表示道歉，并想融入他们的谈话，但却完全和他们不在一个频道。然后，就没有然后了，他和女友就 OVER 了，并且女友说自己就不应该和一个 Yuppie 男约会。所以，什么是 Yuppie？其实他们的这段分手 ...继续阅读 (30)

先聊聊写界面化程序的目的，在 B/S 结构软件盛行的今天，C/S 结构的软件还有人用吗？答案是肯定的，至少你想用 B/S 结构的软件的时候你得有个 C/S 结构的浏览器，对吧？这样说显得有点抬杠，当然，我认为最重要的还是“简单”，或者说“用户友好”。再 Geek 的人应该也喜欢有的时候偷懒，虽然我称不上 Geek，但也经常在黑框框中不用鼠标敲着各种代码，但是还是希望能够有些小工具只要能够点个几下就能帮忙干些事情的。至于对于更普通的用户而言，就应该更加希望能够用最“简单，清晰，明了”的方式“快速”的完成一项任务，有点像 Windows 用户把桌面上的快捷方式拖到回收站，然后和我说：好了，程序卸载了，我只能回答说：或许你该换个 MAC。❗ 更新 ❗SciHubEVA最新版本已经采用PySide2进行改写，Windows 版本安装包构建工作迁移至Inno Setup 6，更多变更请参见CHANGELOG。跨平台 GUI 程序开发方案选型所以，写个带界面的小工具就是把你的想法更好的服务自己和别人的一个好途径，那么问题来了，对于我这做算法的种业余编程选手，怎么搞定界面化应用呢？虽然是业余编程选手，也也一路从 Logo，Basic，VB，C/C++，Java，R，Python 等等走来，当然很多都是从入门到放弃，总之对于同时需要兼顾一定美感的我，总结了几种跨平台界面 ...继续阅读 (38)

降维在之前的博客中，我们曾经介绍过 PCA 方法及其降维的作用。在原始数据中各个特征之间存在着一定的信息冗余，随着特征的不断增加就容易出现“维数灾难”的问题，因此降维的目的就是在尽可能多的保留原始信息的同时减少数据的维度。一般情况下我们将降维方法分为：线性降维方法和非线性降维方法，线性降维方法的典型算法有：主成份分析 (PCA, Principal Component Analysis)1线性判别分写 (LDA, Linear Discriminant Analysis)2多尺度变换 (MDS, Multi-Dimensional Scaling)3非线性降维方法中在此我们仅列举一些基于流行学习的算法：保距特征映射 (ISOMAP)4局部线性嵌入 (LLE, Locally Linear Embedding)5拉普拉斯特征映射 (LE, Laplacian Eigenmap)6在现实数据中，很多情况数据是无法通过线性的方法进行降维表示的，因此就需要非线性的降维算法出马了。流形在调研流形相关概念时，发现要想深一步的理解这些概念还是需要详细的了解微分几何相关的内容，鉴于本文的目的主要是介绍流形学习 (主要是降维角度) 的相关内容，因此我们对流形仅做一些粗略的介绍。“流形”是英文单词Manifold的中文译名，它源于德文术语 Mannigfaltigkeit，最早出现在 Riemann ...继续阅读 (41)

在构建神经网络模型的时候，除了网络结构设计以外，选取合适的优化算法也对网络起着至关重要的作用，本文将对神经网络中常用的优化算法进行简单的介绍和对比，本文部分参考了 Ruder 的关于梯度下降优化算法一文1。首先，我们对下文中使用的符号进行同意说明：网络中的参数同一表示为$\theta$，网络的假设函数为$h_{\boldsymbol{\theta}}\left(\boldsymbol{x}\right)$，网络的损失函数为$J\left(\boldsymbol{\theta}\right)$，学习率为$\alpha$，假设训练数据中共包含$m$个样本，网络参数个数为$n$。梯度下降在梯度下降算法中，常用的主要包含 3 种不同的形式，分别是批量梯度下降 (Batch Gradient Descent, BGD)，随机梯度下降 (Stochastic Gradient Descent, SGD) 和小批量梯度下降 (Mini-Batch Gradient Descent, MBGD)。一般情况下，我们在谈论梯度下降时，更多的是指小批量梯度下降。BGDBGD 为梯度下降算法中最基础的一个算法，其损失函数定义如下：$$ J \left(\boldsymbol{\theta}\right) = \dfrac{1}{2m} \sum_{i=1}^{m}{\left(h_{\boldsymbol ...继续阅读 (43)

Generative Adversarial Networks (GAN)生成对抗网络(Generative Adversarial Network, GAN) 是由 Goodfellow1于 2014 年提出的一种对抗网络。这个网络框架包含两个部分，一个生成模型 (generative model) 和一个判别模型 (discriminative model)。其中，生成模型可以理解为一个伪造者，试图通过构造假的数据骗过判别模型的甄别；判别模型可以理解为一个警察，尽可能甄别数据是来自于真实样本还是伪造者构造的假数据。两个模型都通过不断的学习提高自己的能力，即生成模型希望生成更真的假数据骗过判别模型，而判别模型希望能学习如何更准确的识别生成模型的假数据。网络框架GAN 由两部分构成，一个生成器(Generator) 和一个判别器(Discriminator)。对于生成器，我们需要学习关于数据$\boldsymbol{x}$的一个分布$p_g$，首先定义一个输入数据的先验分布$p_{\boldsymbol{z}} \left(\boldsymbol{z}\right)$，其次定义一个映射$G \left(\boldsymbol{z}; \theta_g\right): \boldsymbol{z} \to \boldsymbol{x}$。对于判别器，我们则需要定义一个映射$D \le ...继续阅读 (40)

Ising 模型$\renewcommand{\sign}{\operatorname{sign}}$Ising 模型最早是由物理学家威廉·冷次在 1920 年发明的，他把该模型当成是一个给他学生恩斯特·易辛的问题。易辛在他一篇 1924 年的论文1中求得了一维易辛模型的解析解，并且证明它不会产生相变。 二维方晶格易辛模型相对于一维的难出许多，因此其解析的描述在一段时间之后才在 1943 年由拉斯·昂萨格给出2。Ising 模型假设铁磁物质是由一堆规则排列的小磁针构成，每个磁针只有上下两个方向。相邻的小磁针之间通过能量约束发生相互作用，同时受到环境热噪声的干扰而发生磁性的随机转变。涨落的大小由关键的温度参数决定，温度越高，随机涨落干扰越强，小磁针越容易发生无序而剧烈地状态转变，从而让上下两个方向的磁性相互抵消，整个系统消失磁性，如果温度很低，则小磁针相对宁静，系统处于能量约束高的状态，大量的小磁针方向一致，铁磁系统展现出磁性。而当系统处于临界温度$T_C$时，Ising 模型表现出一系列幂律行为和自相似现象3。由于 Ising 模型的高度抽象，可以很容易地将它应用到其他领域之中。例如，将每个小磁针比喻为某个村落中的村民，而将小磁针上下的两种状态比喻成个体所具备的两种政治观点，相邻小磁针之间的相互作用比喻成村民之间观点的影响，环境的温度比喻成每个村民对自己意见不坚持的程度，这样 Is ...继续阅读 (38)

蒙特卡罗方法 (Monte Carlo, MC)蒙特卡罗方法 (Monte Carlo) 也称为统计模拟方法，是于 20 世纪 40 年代由冯·诺伊曼，斯塔尼斯拉夫·乌拉姆和尼古拉斯·梅特罗波利斯在洛斯阿拉莫斯国家实验室为核武器计划工作时 (曼哈顿计划) 发明。因为乌拉姆的叔叔经常在摩纳哥的蒙特卡罗赌场输钱，该方法被定名为蒙特卡罗方法。蒙特卡罗方法是以概率为基础的方法，与之对应的是确定性算法。蒙特卡罗方法最早可以追述到 18 世纪的布丰投针问题，该方法通过一个平行且等距木纹铺成的地板，随意抛一支长度比木纹之间距离小的针，求针和其中一条木纹相交的概率的方法得出了一个求$\pi$的蒙特卡罗方法。我们通过另一种方式使用蒙特卡罗方法计算圆周率$\pi$，对于一个边长为$2r$的正方形，其内切圆的半径即为$r$，因此圆形的面积$A_c$与正方形的面积$A_s$的比值为$$ \dfrac{A_c}{A_s} = \dfrac{\pi r^2}{\left(2r\right)^2} = \dfrac{\pi}{4} $$如果我们在矩形内随机的生成均匀分布的点，则在圆内的点的个数的占比即为$\dfrac{\pi}{4}$，因此通过模拟即可求出$\pi$的近似值library(tidyverse) # 圆的中心点和半径 r <- 2 center_x <- r center_y <- r # 距 ...继续阅读 (51)

准备知识向量与基$\renewcommand{\diag}{\operatorname{diag}}\renewcommand{\cov}{\operatorname{cov}}$首先，定义$\boldsymbol{\alpha}$为列向量，则维度相同的两个向量$\boldsymbol{\alpha}, \boldsymbol{\beta}$的内积可以表示为：$$\boldsymbol{\alpha} \cdot \boldsymbol{\beta} = \boldsymbol{\alpha}^T \boldsymbol{\beta} = \sum_{i=1}^{n}{\alpha_i b_i}$$后续为了便于理解，我们以二维向量为例，则$\boldsymbol{\alpha} = \left(x_1, y_1\right)^T, \boldsymbol{\beta} = \left(x_2, y_2\right)^T$，在直角座标系中可以两个向量表示如下：我们从$A$点向向量$\boldsymbol{\beta}$的方向做一条垂线，交于点$C$，则称$OC$为$OA$在$OB$方向上的投影。设向量$\boldsymbol{\alpha}$和向量$\boldsymbol{\beta}$的夹角为$\theta$，则：$$\cos \left(\theta\right) = \dfra ...继续阅读 (34)

从下了飞机到酒店，一路上体验到了我国互联网对世界各地的影响，机场巴士可以用微信和支付宝，下了巴士发现这里也有共享单车，人家还配了头盔。晚上雅拉河还是很漂亮的，天气略凉，空气不错，淡淡的云，大冷天的人们也很愿意在外面吃饭。谈到澳大利亚，最熟知的两种动物就是精壮的袋鼠和呆萌的考拉，晚上吃饭看了菜单发现居然有袋鼠肉，味道还是很不错的，没什么奇怪的味道。后来得知，在澳洲袋鼠的数量算得上略微的泛滥，所以法律是允许吃袋鼠的，如果你在路上开车不幸撞上了一只袋鼠，那么请快速的结束他的生命就好，免得痛苦，但如果你撞了一只考拉，那好吧，估计你出不去澳大利亚了……当然，本次旅程最重要的还是 IJCAI 大会，让我这个半路出家搞 AI 的人感触最多的是：未知的还有很多，要学的也还有很多。这次大会期间也再次发表了呼吁禁止自主武器的公开信，我认为有时候我们更多的关注了 AI 技术的层面，而忽略了很多其他的事情，例如伦理和道德。例如现在医学图像识别技术在一定范围内已经超越了人类，那么是否我们就可以让机器直接做决定呢，如果出了问题，将如何处理，所以这个边界到底在哪里也是值的我们仔细思考的。这边的冬天是多雨的，来的时候推算这边应该是早春，没带太厚的衣服，和当地人聊到天气，我说现在是 Early spring 怎么怎么的，结果对方说 No, No, No, still winter。尽管天 ...继续阅读 (39)