Keep and carry on.
post @ 2016-05-13

Introduction

事件驱动为广大的程序员所熟悉,其最为人津津乐道的是在图形化界面编程中的应用;
事实上,在网络编程中事件驱动也被广泛使用,并大规模部署在高连接数高吞吐量的服务器程序中,
如 http 服务器程序、ftp 服务器程序等。相比于传统的网络编程方式,事件驱动能够极大的降低资源占用,
增大服务接待能力,并提高网络传输效率。

本文探究了在linux系统下常用的epoll的原理及其使用方法,总结了自己学习并发服务器编程过程中遇到的问题。


阻塞式io

我们来看一个最简单的客户端/服务器交互场景:
c/s 1
除非使用fcntl显示指定,几乎所有IO接口都是阻塞型的。这给网络编程带来了很大问题,比如服务器调用send()/recv()的时候,线程会被阻塞,在此期间无法执行任何运算或响应网络请求,如果在服务器阻塞时有新的客户connect,那么新的客户将得不到响应。这时候我们会想到使用多线程/多进程模型来实现服务器。

多进程/线程服务器

应对多客户机的网络应用,最简单的解决方式是在服务器端使用多线程(或多进程)。多线程(或多进程)的目的是让每个连接都拥有独立的线程(或进程),这样任何一个连接的阻塞都不会影响其他的连接。

具体使用多进程还是多线程,并没有一个特定的模式。传统意义上,进程的开销要远远大于线程,所以,如果需要同时为较多的客户机提供服务,则不推荐使用多进程;如果单个服务执行体需要消耗较多的 CPU 资源,譬如需要进行大规模或长时间的数据运算或文件访问,则进程较为安全。通常,使用 pthread_create () 创建新线程,fork() 创建新进程。

我们假设对上述的服务器 / 客户机模型,提出更高的要求,即让服务器同时为多个客户机提供一问一答的服务。于是有了如下的模型。
2
在上述的线程 / 时间图例中,主线程持续等待客户端的连接请求,如果有连接,则创建新线程,并在新线程中提供为前例同样的问答服务。
述多线程的服务器模型似乎完美的解决了为多个客户机提供问答服务的要求,但其实并不尽然。如果要同时响应成百上千路的连接请求,由于调度的关系,无论多线程还是多进程都会严重占据系统资源,降低系统对外界响应效率,而线程与进程本身也更容易进入假死状态。

接下来我们可能会考虑使用“线程池”或“连接池”。“线程池”旨在减少创建和销毁线程的频率,其维持一定合理数量的线程,并让空闲的线程重新承担新的执行任务。“连接池”维持连接的缓存池,尽量重用已有的连接、减少创建和关闭连接的频率。这两种技术都可以很好的降低系统开销,都被广泛应用很多大型系统,如 websphere、tomcat 和各种数据库等。

但是,“线程池”和“连接池”技术也只是在一定程度上缓解了频繁调用 IO 接口带来的资源占用。而且,所谓“池”始终有其上限,当请求大大超过上限时,“池”构成的系统对外界的响应并不比没有池的时候效果好多少。所以使用“池”必须考虑其面临的响应规模,并根据响应规模调整“池”的大小。

对应上例中的所面临的可能同时出现的上千甚至上万次的客户端请求,“线程池”或“连接池”或许可以缓解部分压力,但是不能解决所有问题。

总之,多线程模型可以方便高效的解决小规模的服务请求,但面对大规模的服务请求,多线程模型并不是最佳方案。下来我将讨论用非阻塞接口来尝试解决这个问题。

非阻塞服务器程序

以上面临的很多问题,一定程度是 IO 接口的阻塞特性导致的。多线程是一个解决方案,还一个方案就是使用非阻塞的接口。

非阻塞的接口相比于阻塞型接口的显著差异在于,在被调用之后立即返回。也就是说

当进程把一个套接字设置成非阻塞是在通知内核:当所请求的I/O操作非得把本进程投入睡眠才能完成时,不要把本进程投入睡眠,而是返回一个错误 eg. EWOULDBLOCK (UNP)

使用如下的函数可以将某句柄 fd 设为非阻塞状态。

1
fcntl( fd, F_SETFL, O_NONBLOCK );

下面将给出只用一个线程,但能够同时从多个连接中检测数据是否送达,并且接受数据。
3

在非阻塞状态下,recv() 接口在被调用后立即返回,返回值代表了不同的含义。如在本例中,

  • recv() 返回值大于 0,表示接受数据完毕,返回值即是接受到的字节数;
  • recv() 返回 0,表示连接已经正常断开;
  • recv() 返回 -1,且 errno 等于 EAGAIN,或者EWOULDBLOCK,表示 recv 操作还没执行完成;
  • recv() 返回 -1,且 errno 不等于 EAGAIN,表示 recv 操作遇到错误 比如 SIGPIPE 导致errno==EPIPE,SIGINT导致errno==SIGINTR。

可以看到服务器线程可以通过循环调用 recv() 接口,可以在单个线程内实现对所有连接的数据接收工作。

但是上述模型绝不被推荐。因为,循环调用 recv() 将大幅度推高 CPU 占用率;此外,在这个方案中,recv() 更多的是起到检测“操作是否完成”的作用,由于服务器并不知道什么时候fd1,fd2,fd3的缓冲区上会有数据,所以就忙轮询,这样很耗费cpu的。所以需要一种预先告知内核的能力,当内核一旦发现进程指定的一个或多个IO条件就绪,他就通知进程,这个能力叫做 多路IO复用.

操作系统提供了更为高效的检测“操作是否完成”作用的接口,例如select()/poll()/epoll()/dev/poll / kqueue / libv等。

未完待续…


使用select()接口的基于事件驱动的服务器模型

大部分Linux都支持Select函数,该函数用于探测多个文件句柄的状态变化。Manural上是这么描述的:

select() and pselect() allow a program to monitor multiple file
descriptors, waiting until one or more of the file descriptors become
“ready” for some class of I/O operation (e.g., input possible). A file
descriptor is considered ready if it is possible to perform the corre‐
sponding I/O operation (e.g., read(2)) without blocking.

Select接口的原型:

1
2
3
4
5
FD_ZERO(int fd, fd_set* fds)
FD_SET(int fd, fd_set* fds)
FD_ISSET(int fd, fd_set* fds)
FD_CLR(int fd, fd_set* fds)
int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout)

这里,fd_set 类型可以简单的理解为按 bit 位标记句柄的队列,例如要在某 fd_set 中标记一个值为 16 的句柄,则该 fd_set 的第 16 个 bit 位被标记为 1。具体的置位、验证可使用 FD_SET、FD_ISSET 等宏实现。在 select() 函数中,readfds、writefds 和 exceptfds 同时作为输入参数和输出参数。如果输入的 readfds 标记了 16 号句柄,则 select() 将检测 16 号句柄是否可读。在 select() 返回后,可以通过检查 readfds 有否标记 16 号句柄,来判断该“可读”事件是否发生。另外,用户可以设置 timeout 时间。

下面将重新模拟上例中从多个客户端接收数据的模型。
4
上述模型只是描述了使用 select() 接口同时从多个客户端接收数据的过程;由于 select() 接口可以同时对多个句柄进行读状态、写状态和错误状态的探测,所以可以很容易构建为多个客户端提供独立问答服务的服务器系统。
5
这里需要指出的是,客户端的一个 connect() 操作,将在服务器端激发一个“可读事件”,所以 select() 也能探测来自客户端的 connect() 行为。

上述模型中,最关键的地方是如何动态维护 select() 的三个参数 readfds、writefds 和 exceptfds。作为输入参数,readfds 应该标记所有的需要探测的“可读事件”的句柄,其中永远包括那个探测 connect() 的那个“母”句柄;同时,writefds 和 exceptfds 应该标记所有需要探测的“可写事件”和“错误事件”的句柄 ( 使用 FD_SET() 标记 )。

作为输出参数,readfds、writefds 和 exceptfds 中的保存了 select() 捕捉到的所有事件的句柄值。程序员需要检查的所有的标记位 ( 使用 FD_ISSET() 检查 ),以确定到底哪些句柄发生了事件。

上述模型主要模拟的是“一问一答”的服务流程,所以,如果 select() 发现某句柄捕捉到了“可读事件”,服务器程序应及时做 recv() 操作,并根据接收到的数据准备好待发送数据,并将对应的句柄值加入 writefds,准备下一次的“可写事件”的 select() 探测。同样,如果 select() 发现某句柄捕捉到“可写事件”,则程序应及时做 send() 操作,并准备好下一次的“可读事件”探测准备。下图描述的是上述模型中的一个执行周期。
6

这种模型的特征在于每一个执行周期都会探测一次或一组事件,一个特定的事件会触发某个特定的响应。我们可以将这种模型归类为“事件驱动模型”。

相比其他模型,使用 select() 的事件驱动模型只用单线程(进程)执行,占用资源少,不消耗太多 CPU,同时能够为多客户端提供服务。如果试图建立一个简单的事件驱动的服务器程序,这个模型有一定的参考价值。

但这个模型依旧有着很多问题。

首先,select() 接口并不是实现“事件驱动”的最好选择。因为当需要探测的句柄值较大时,select() 接口本身需要消耗大量时间去轮询各个句柄。很多操作系统提供了更为高效的接口,如 linux 提供了 epoll,BSD 提供了 kqueue,Solaris 提供了 /dev/poll …。如果需要实现更高效的服务器程序,类似 epoll 这样的接口更被推荐。遗憾的是不同的操作系统特供的 epoll 接口有很大差异,所以使用类似于 epoll 的接口实现具有较好跨平台能力的服务器会比较困难。

其次,该模型将事件探测和事件响应夹杂在一起,一旦事件响应的执行体庞大,则对整个模型是灾难性的。如下例,庞大的执行体 1 的将直接导致响应事件 2 的执行体迟迟得不到执行,并在很大程度上降低了事件探测的及时性.
7

接下来就该更先进的epoll出场了。


Read More

导引

本文是由几个问题引发的:

  1. 补码是怎么来的?
  2. 为什么补码的表示范围不对称,TMin比TMax多了1?
  3. 什么是编码? 编码的本质是什么?

一、 补码是怎么产生的?

补码方法 (method of complements)

在数学和计算领域,补数方法是一种用加上一个正数的方法替代减去一个负数的技术,这种技术过去用在机械计算器上,现在依然在电子计算机里使用。因为计算机里只有加法器,没有减法器,所以要把减法操作转化为加法操作。

冯诺依曼在他的1945年的关于EDVAC的第一篇手稿里建议使用2的2进制补码,受这个思想启发,在1949年EDSAC(世界上第二台存储程序数字通用计算机)里使用了补码进行计算。

EDSAC

许多早期计算机使用了 ones’ complement(反码)表示。IBM700/7000系列科学计算机用了符号数值表示法(原码),但是寄存器下标用了补码.早期使用补码的商用计算机包括DEC的PDP-5和1963PDP-6.在1964年IBM生产并迅速主宰了市场的 System/360,使补码表示成为了计算机工业界最广泛使用的表示法。第一台微型计算机PDP-8使用了 two’s complement,以后的几乎所有微型计算机都使用了二进制补码表示。

先上几张机械计算器的图:
机械计算器
Various desktop mechanical calculators used in the office from 1851 onwards. Each one has a different user interface. This picture shows clockwise from top left: An Arithmometer, A Comptometer, A Dalton adding machine, a Sundstrand and an Odhner Arithmometer

算盘
不解释。。。

数值补码 (numeric complements)

n位数字y在以b为基数的系统里的基数补码(radix complement) 是 $b^n-y$. 这里 $b^n$ 就是模。

基数补码通常可以用 diminished radix complement(基数减一的补码,也就是课本上说的反码)来轻易的获取,即$(b^n-1)-y$,因为 $b^n-1$ 是 $b-1$重复了n次,即 [b-1,b-1,b-1,….b-1] , 基数减一的补码可以通过将每一位补满 b-1来得到(即,把y里每一位用b-1减掉).

x-y 可以像下面这样执行:

  1. 把x的 基数减一补码加到y上得到 $b^n-1-x+y$ 或者 $b^n-1-(x-y)$,而这正是 $x-y$的基数减一补码 少了$b-1$的结果 ,例如 在 $2^4$ 计算 8-3 , 即把 1000 的基数减1补码 0111加上0011得到
    1010 ,而这正是$(8-3)$ 即 5(0101)的基数减1补码(1010)少了 2-1的结果 。

  2. 把$y$的基数补码($b^n-y$)加到$x$上得到$x+b^n-y$或者$x-y+b^n$
    ,假设 $y \le x$,那么结果永远大于等于$b^n$,而且丢掉最高有效位的 ‘1’相当于减去了$b^n$,那么结果就变成了$x-y+b^n-b^n$,或者仅仅是$x-y$,这就是需要的结果;

这正好解释了把减法转换为加法后,如果产生了加法溢出,那么虽然溢出丢掉了进位,结果仍然是正确的,多奇妙!
此处输入图片的描述
当b等于2的时候,我们就得到了计算机里用的 Two’s complement.

补码建立起了 从 二进制数字向量 到 某一个范围内的数字 之间的 双射(bijection)


二、 为什么补码的负数范围 |Tmin| 比 |Tmax| 多 1?

看图说话,可以把它想象成钟表,而钟表上的刻度数量就是所能编码的数量,我们设计一套规则赋予每个刻度一个意义,建立起 意义 和 刻度 之间的 一一映射 ,这个过程就是编码的过程,用同一套规则,可以去解释意义,找到刻度本身,这就是解码的过程。

而在设计补码的时候,把钟表的12个刻度分成2部分,让一部分表示负数,另一半表示非负数,而0也是非负数,所以0把最大的正数的位置占了,于是造成了范围不对称。

此处输入图片的描述

A+B = 模,那么 A和B是互补关系
补数顾名思义就是那个能把自己补满成模的大小的数

三、为什么要有反码原码这等鸡肋概念?

上面也说过,反码(ones’ complement)的提出,只不过是因为在直观感受上,把一个二进制数01011011补满11111111再加1 , 比把它直接补成11111111要来的容易,也容易在硬件上实现。所以产生了求补码前先用
diminished radix complement(反码) 求补,再加1形成结果的步骤,于是在这个中间过程中,为了描述这个中间状态,就给它起了个名字叫反码。


四、对编码的理解


参考文献

  1. 原码、反码和补码
  2. two’s complement Representation
  3. Method of complemet
  4. 关于2的补码
Read More
post @ 2016-01-15

Solver简介

Solver执行模型的优化操作,它通过协调网络的前向推断和反向梯度传播来执行参数更新,来减少误差损失。学习职能被分配到solvernet上,sovler负责优化和产生参数更新,net负责计算loss和梯度。

Caffe包含了下面几个Solver

  • Stochastic Gradient Descent (type: “SGD”),
  • AdaDelta (type: “AdaDelta”),
  • Adaptive Gradient (type: “AdaGrad”),
  • Adam (type: “Adam”),
  • Nesterov’s Accelerated Gradient (type: “Nesterov”) and
  • RMSprop (type: “RMSProp”)

Solver的功能有:

  1. 支撑整个优化过程的簿记工作,创建训练网络和测试网络。
  2. 通过调用forward/backward来迭代优化并更新参数。
  3. 周期性的用测试网络评估学习状态。
  4. 在优化过程中创建模型和solver的状态。

每次迭代过程:

  1. 调用网络的forward来计算输出和损失
  2. 调用网络的backward来计算梯度
  3. 根据solver的具体方法用梯度进行参数更新
  4. 根据学习率,历史记录和方法来更新solver的状态

Solver把weights从初始化一直保持到模型学习结束。它也有CPU/GPU模式。


Solver的方法

Solver的method处理通用的损失函数最小化的优化问题。对于数据集$D$,优化目标是整个数据集的$|D|$条数据的平均损失:
$$L(W) = \frac{1}{|D|} \sum_i^{|D|} f_W\left(X^{(i)}\right) + \lambda r(W)$$
其中$f_W\left(X^{(i)}\right)$是数据对象$X^{(i)}$的损失,而$r(W)$是一个正则化项,$\lambda$是学习率。实际中数据集的数量$|D|$可以很大,所以每个solver迭代过程我们都使用随机逼近目标的方法,抽取小批量数据 $N <<|D|$:

$$L(W) \approx \frac{1}{N} \sum_i^N f_W\left(X^{(i)}\right) + \lambda r(W)$$

模型在forward步骤中计算$f_W$然后在backward步骤中把梯度$\nabla f_W$反传。
参数更新$\Delta W$是由solver根据误差梯度$\nabla f_W$、正则化的梯度$\nabla r(W)$、和其他和优化方法相关的参数计算的。


SGD

Stochastic gradient descent(type: “SGD”)随机梯度下降法按照负梯度$\nabla L(W)$的线型组合和前面的权重更新$V_t$更新权重$W$。学习率 $\alpha$是负梯度的权重。动量$\mu$是前面一次更新的权重。

最终,我们用如下公式用当前的权重$W_t$和上一次更新值$Vt$来计算第$t+1$次迭代的更新值$V{t+1}$和更新权重$W{t+1}$:
$$V
{t+1} = \mu V_t - \alpha \nabla L(Wt)$$
$$W
{t+1} = Wt + V{t+1}$$

学习“超参数”($\alpha$和$\mu$)可能需要一点微调技巧以便获取最佳结果。如果你不确定怎么开始的画,可以看看下面的黄金法则,了解更多的信息你可以参看Leon Bottou’s 的Stochastic Gradient Descent Tricks .

设置学习率$\alpha$和动量$\mu$的黄金法则

在深度学习中使用SGD的一个好策略是把学习率$\alpha$设置为$\alpha \approx 0.01 = 10^{-2}$,然后用一个常量因子(例如10)来在学习过程中调整它,使得损失达到一个明显的”平台”,重复这个过程几遍,通常,你可能想用一个动量$\mu = 0.9$或者相似的值。为了在迭代过程平滑权重更新,动量可以使SGD稳定且快速。
  
  
这个过程是 Krizhevsky[^1]在他们著名的ILSVRC-2012 CNN组冠军论文里采用的策略。Caffe让整个策略易于实现,就像我们在对1进行实现的时候做的那样(./examples/imagenet/alexnet_solver.prototxt)

为了这样使用学习率策略,你可以把下面这几行放在你的solver的prototxt文件里:

1
2
3
4
5
6
7
8
9
10
11
12
13
base_lr: 0.01 # begin training at a learning rate of 0.01 = 1e-2
lr_policy: "step" # learning rate policy: drop the learning rate in "steps"
# by a factor of gamma every stepsize iterations
gamma: 0.1 # drop the learning rate by a factor of 10
# (i.e., multiply it by a factor of gamma = 0.1)
stepsize: 100000 # drop the learning rate every 100K iterations
max_iter: 350000 # train for 350K iterations total
momentum: 0.9

在上面的设定中,我们总是使用momentum$\mu=0.9$。我们以基础学习率base_lr$\alpha = 0.01 = 10^{-2}$开始训练最早的100,000次迭代过程,然后将学习率乘以gamma$(\gamma)$,即用学习率 $\alpha’ = \alpha \gamma = (0.01) (0.1) = 0.001 = 10^{-3}$训练第100K~200K次迭代过程,然后用$\alpha’’ = 10^{-4}$来训练第200K~300K次迭代,最终用$\alpha’’’ = 10^{-5}$训练到第350K次迭代.

  
注意动量在很多次迭代后,把$\mu$用因子$\frac{1}{1 - \mu}$乘以你更新的次数设置,所以你如果增加了$\mu$,那么最好相应的减少$\alpha$,反之亦然。
  
  
例如,设动量$\mu=0.9$,我们得到一个有效的更新尺寸乘数$\frac{1}{1 - 0.9} = 10$,如果我们增加动量到$\mu=0.99$,那么我们就把更新大小乘数增加到了100,于是我们应该把学习率$\alpha$下调10.

注意到上面的设定仅仅是一个指导,他们肯定不能够保证是最优的,甚至都不能工作!如果学习过程误入歧途了(例如你看到很大或者NaN、inf等损失值或者输出),尝试着把base_lr减少,例如:减少到0.001,然后重训练,重复这个过程直到你找到一个合适的base_lr.

[^1]: A. Krizhevsky, I. Sutskever, and G. Hinton. ImageNet Classification with Deep Convolutional Neural Networks. Advances in Neural Information Processing Systems, 2012.


AdaDelta

AdaDelta方法(type: “AdaDelta”)是一个”robust learning rate method”.[^2].它也是一种基于梯度的优化方法(类似SGD),它的更新公式是:

$$ \begin{align}
(v_t)i &= \frac{\operatorname{RMS}((v{t-1})_i)}{\operatorname{RMS}\left( \nabla L(Wt) \right){i}} \left( \nabla L(W_{t’}) \right)_i
\
\operatorname{RMS}\left( \nabla L(Wt) \right){i} &= \sqrt{E[g^2] + \varepsilon}
\
E[g^2]t &= \delta{E[g^2]{t-1} } + (1-\delta)g{t}^2
\end{align} $$
$$(W
{t+1})_i =
(W_t)_i - \alpha
(v_t)_i.$$


AdaGrad

adaptive gradient(type: “AdaGrad”)方法(Duchi, E. Hazan, and Y. Singer. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization The Journal of Machine Learning Research, 2011.)
是一个基于梯度的方法,它尝试“在干草堆里找缝衣针”也就是找到预测能力很强但很少见的feature(find needles in haystacks in the form of very predictive but rarely seen features,),Duchi等人如是说。给出前面迭代的所有更新信息($\left( \nabla L(W) \right)_{t’}$其中($t’ \in {1, 2, …, t}$),论文中提出的更新公式如下,它给每个组件$i$指定一个权重W:

$$
(W_{t+1})_i =
(W_t)_i - \alpha
\frac{\left( \nabla L(Wt) \right){i}}{
\sqrt{\sum{t’=1}^{t} \left( \nabla L(W{t’}) \right)_i^2}
}
$$

注意在实践中,对于权重$W \in \mathcal{R}^d$,AdaGrad实现仅用了$\mathcal{O}(d)$额外的存储来保存历史梯度信息,而传统方法要用$\mathcal{O}(dt)$来保存历史梯度信息。


Scaffolding

Solver的scaffolding准备优化方法并且初始化模型,通过调用Solver::Presolve()方法调用来完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
> caffe train -solver examples/mnist/lenet_solver.prototxt
I0902 13:35:56.474978 16020 caffe.cpp:90] Starting Optimization
I0902 13:35:56.475190 16020 solver.cpp:32] Initializing solver from parameters:
test_iter: 100
test_interval: 500
base_lr: 0.01
display: 100
max_iter: 10000
lr_policy: "inv"
gamma: 0.0001
power: 0.75
momentum: 0.9
weight_decay: 0.0005
snapshot: 5000
snapshot_prefix: "examples/mnist/lenet"
solver_mode: GPU
net: "examples/mnist/lenet_train_test.prototxt"

网络初始化

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
I0902 13:35:56.655681 16020 solver.cpp:72] Creating training net from net file: examples/mnist/lenet_train_test.prototxt
[...]
I0902 13:35:56.656740 16020 net.cpp:56] Memory required for data: 0
I0902 13:35:56.656791 16020 net.cpp:67] Creating Layer mnist
I0902 13:35:56.656811 16020 net.cpp:356] mnist -> data
I0902 13:35:56.656846 16020 net.cpp:356] mnist -> label
I0902 13:35:56.656874 16020 net.cpp:96] Setting up mnist
I0902 13:35:56.694052 16020 data_layer.cpp:135] Opening lmdb examples/mnist/mnist_train_lmdb
I0902 13:35:56.701062 16020 data_layer.cpp:195] output data size: 64,1,28,28
I0902 13:35:56.701146 16020 data_layer.cpp:236] Initializing prefetch
I0902 13:35:56.701196 16020 data_layer.cpp:238] Prefetch initialized.
I0902 13:35:56.701212 16020 net.cpp:103] Top shape: 64 1 28 28 (50176)
I0902 13:35:56.701230 16020 net.cpp:103] Top shape: 64 1 1 1 (64)
[...]
I0902 13:35:56.703737 16020 net.cpp:67] Creating Layer ip1
I0902 13:35:56.703753 16020 net.cpp:394] ip1 <- pool2
I0902 13:35:56.703778 16020 net.cpp:356] ip1 -> ip1
I0902 13:35:56.703797 16020 net.cpp:96] Setting up ip1
I0902 13:35:56.728127 16020 net.cpp:103] Top shape: 64 500 1 1 (32000)
I0902 13:35:56.728142 16020 net.cpp:113] Memory required for data: 5039360
I0902 13:35:56.728175 16020 net.cpp:67] Creating Layer relu1
I0902 13:35:56.728194 16020 net.cpp:394] relu1 <- ip1
I0902 13:35:56.728219 16020 net.cpp:345] relu1 -> ip1 (in-place)
I0902 13:35:56.728240 16020 net.cpp:96] Setting up relu1
I0902 13:35:56.728256 16020 net.cpp:103] Top shape: 64 500 1 1 (32000)
I0902 13:35:56.728270 16020 net.cpp:113] Memory required for data: 5167360
I0902 13:35:56.728287 16020 net.cpp:67] Creating Layer ip2
I0902 13:35:56.728304 16020 net.cpp:394] ip2 <- ip1
I0902 13:35:56.728333 16020 net.cpp:356] ip2 -> ip2
I0902 13:35:56.728356 16020 net.cpp:96] Setting up ip2
I0902 13:35:56.728690 16020 net.cpp:103] Top shape: 64 10 1 1 (640)
I0902 13:35:56.728705 16020 net.cpp:113] Memory required for data: 5169920
I0902 13:35:56.728734 16020 net.cpp:67] Creating Layer loss
I0902 13:35:56.728747 16020 net.cpp:394] loss <- ip2
I0902 13:35:56.728767 16020 net.cpp:394] loss <- label
I0902 13:35:56.728786 16020 net.cpp:356] loss -> loss
I0902 13:35:56.728811 16020 net.cpp:96] Setting up loss
I0902 13:35:56.728837 16020 net.cpp:103] Top shape: 1 1 1 1 (1)
I0902 13:35:56.728849 16020 net.cpp:109] with loss weight 1
I0902 13:35:56.728878 16020 net.cpp:113] Memory required for data: 5169924

损失函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
I0902 13:35:56.728893 16020 net.cpp:170] loss needs backward computation.
I0902 13:35:56.728909 16020 net.cpp:170] ip2 needs backward computation.
I0902 13:35:56.728924 16020 net.cpp:170] relu1 needs backward computation.
I0902 13:35:56.728938 16020 net.cpp:170] ip1 needs backward computation.
I0902 13:35:56.728953 16020 net.cpp:170] pool2 needs backward computation.
I0902 13:35:56.728970 16020 net.cpp:170] conv2 needs backward computation.
I0902 13:35:56.728984 16020 net.cpp:170] pool1 needs backward computation.
I0902 13:35:56.728998 16020 net.cpp:170] conv1 needs backward computation.
I0902 13:35:56.729014 16020 net.cpp:172] mnist does not need backward computation.
I0902 13:35:56.729027 16020 net.cpp:208] This network produces output loss
I0902 13:35:56.729053 16020 net.cpp:467] Collecting Learning Rate and Weight Decay.
I0902 13:35:56.729071 16020 net.cpp:219] Network initialization done.
I0902 13:35:56.729085 16020 net.cpp:220] Memory required for data: 5169924
I0902 13:35:56.729277 16020 solver.cpp:156] Creating test net (#0) specified by net file: examples/mnist/lenet_train_test.prototxt

完成

1
2
I0902 13:35:56.806970 16020 solver.cpp:46] Solver scaffolding done.
I0902 13:35:56.806984 16020 solver.cpp:165] Solving LeNet


参数更新

实际的权重更新是由solver完成的,它通过把参数传递给Sovler::ComputeUpdateValue()来实现的。这个方法会整合所有权重衰减到权重梯度里(现在只包含误差梯度)来获得每个网络最终的梯度,然后这些gradients被学习率$\alpha$缩放,需要减去的更新值被存在每个参数Blobdiff属性里。最终,调用每个参数blob的Blob::Update方法,完成最终的权重更新(从它的data里减去diff).


快照和恢复

Solvor在训练过程中通过调用Solver::Snapshot()方法和Solver::SnapshotSolverState()方法分别保存权重和它自身的状态。权重快照导出了学习到的模型,solver快照相当一个断点,使得训练可以从该快照恢复。恢复是通过Solver::Restore()Solver::RestoreSolverState()方法完成的.

权重保存文件没有后缀,而状态保存文件有.solverstate的后缀。每个文件都会有一个_iter_N的前缀来指明是多少次迭代的快照。

快照是在Solver定义prototxt里这样配置的:

1
2
3
4
5
6
7
8
9
10
11
12
The snapshot interval in iterations.
snapshot: 5000
# File path prefix for snapshotting model weights and solver state.
# Note: this is relative to the invocation of the `caffe` utility, not the
# solver definition file.
snapshot_prefix: "/path/to/model"
# Snapshot the diff along with the weights. This can help debugging training
# but takes more storage.
snapshot_diff: false
# A final snapshot is saved at the end of training unless
# this flag is set to false. The default is true.
snapshot_after_train: true

[^2]: M. Zeiler ADADELTA: AN ADAPTIVE LEARNING RATE METHOD. arXiv preprint, 2012.

Read More
post @ 2016-01-14

同所有的机器学习过程一样,在Caffe里,学习是由loss function损失函数驱动的(也有叫做 error,cost,或者objective function 的)。一个损失函数通过在参数(例如网络权重)和一个衡量这些参数拟合劣度的标量值(scalar)之间建立映射,指明了学习的目标。因此,学习的目标就是找到一组能够使loss fucntion最小化的参数。

Caffe里的损失是通过forward过程计算出来的。每一层都通过bottom从下面一层获取一个blob然后产生一组输出blob给top指定的上层.一些层的输出可能会在损失函数里使用。一个典型的为1对多分类任务选择的损失函数是SoftmaxWithLoss函数,使用一个如下的网络定义:

1
2
3
4
5
6
7
layer{
name : "loss"
type : "SoftmaxWithLoss"
bottom: "pred"
bottom: "label"
top: "loss"
}

在一个SoftmaxWithLoss函数里,topblob是一个标量(empty shape),它是由整个minibatch的所有预测标签pred和实际标签label的差计算出来的平均误差.


损失权重

对于那些有多个输出层的网络(例如既使用了SoftmaxWithLoss又使用了EuclideanLoss),loss weight可以用来指明他们之间的相对重要度。

出于习惯,Caffe layer类型使用了后缀Loss来指明损失函数,但是其他层可假定为纯粹用来进行中间计算。但是,任何层可以用作损失函数,只要在layer定义中该层产生的的topblob添加一个loss_weight:<float>字段即可。带有后缀Loss的层定义有隐含的loss_weight属性,对于第一个topblobloss_weight=1,对于其他附加的top来说loss_weight=0;其他层有隐含的loss_weight=0给所有的top。于是,上面的SoftmaxWithLoss层可以等价的写成:

1
2
3
4
5
6
7
8
layer {
name: "loss"
type: "SoftmaxWithLoss"
bottom: "pred"
bottom: "label"
top: "loss"
loss_weight: 1
}

然而,任何可以反向传播的层都可以给定一个非零的loss_weigh,这样做可以允许我们做一些特定操作,比如,正则化一些中间层产生的激活值。对于关联着非零损失的非单个输出来说,损失仅仅是简单的把整个blob累积起来而已。
  
  
对于Caffe的最终损失,是把整个网络的加权损失累加起来计算的,例如下面的伪代码描述的那样:

1
2
3
4
loss := 0
for layer in layers:
for top, loss_weight in layer.tops, layer.loss_weights:
loss += loss_weight * sum(top)

Read More
post @ 2016-01-13

forwardbackward是一个Net的基本计算。

forward & backward

我们来考虑一个简单的logistic regression 分类器.

Forward计算出用来推断(inference)的输出,在forward过程中,caffe把各层的计算结果组装成模型所表达的”函数”值,这个过程是自底向上传播的。

forward logistic regression

图中数据$x$经过一个内积层成为$g(x)$,然后再经过一个softmax分类器成为h(g(x)),softmax的loss为$f_w(x)$.

Backward把顶层的损失loss向底层传播,向底层传播是通过自动求导技术生成梯度的。这个过程是自顶向下的。

backward

反向传播用顶层的损失函数的输出作为输入,通过公式$\frac{\partial f_W}{\partial h}$ 计算顶层的梯度,剩下层的梯度是利用链式法则逐层计算的。那些带有参数的层,比如INNER_PRODUCT层,通过它们的参数$\frac{\partial fW}{\partial W{\text{ip}}}$来计算梯度(其实这都是由自动求导技术在前向传播计算好的,反向传播的时候只是收集一下,和动态规划的思想类似)。

当你定义好网络的时候,这些计算就已经设置好了,caffe会自动为你做前向和后向传播计算.      

  • Net::Forward()Net::Backward()方法会在前向和后向的过程中把各层的Layer::Forward()Layer::Backward()函数执行,并把结果收集起来。
  • 每个layer类型都有一组forward_{cpu,gpu}()backward_{cpu,gpu}()方法来根据运行的mode来调用相应的方法计算本层的结果。由于条件限制或者为了方便起见,一个layer可能只实现了CPU或者GPU模式的代码。

Solver是用来对整个网络求解的,它先调用forward来产生输出和loss,然后调用backward来产生gradient,最后把梯度合并用来在优化步骤中更新权重。把功能分割成Solver,NetLayer使得Caffe高内聚低耦合,易于扩展。

有关forward和backward的详细内容请参看Layer catalogue

Read More

本文译自官方文档,权当练英语了,请各位英文好看官移步官网自行阅读

引言

深度神经网络是一种聚合模型,可以自然的表示为作用于数据块上的内部相连的网络. Caffe用自己的建模方法将网络一层一层定义出来。网络由输入数据到损失层把整个模型自底向上的定义出来。数据和偏导数在网络中前向、后向流动。Caffe使用blob存储、交换、操纵这些信息。blob是整个框架的标准的数组结构和统一存储接口。layer作为建模和计算的基础,net作为layer的集合和链接。blob的细节描述了信息是怎样在layersnets间存储和交换的.


Blob 存储和通信

Blob 是Caffe处理和传输的真实数据的包装类,同时它还隐含提供了在CPU和GPU之间同步数据的能力。在数学上,一个blob就是一个N维的数组,它是按照c语言风格存储的。(其实就是行优先还是列优先的风格,参照wiki:row-major order).

caffe使用blob存储和交换数据。blob对不同数据提供了统一的内存接口;例如:一批图片,模型参数,优化过程的偏导数等。

Blob通过在需要时将数据从CPU同步到GPU来隐藏在GPU/CPU之间进行混合操作的计算开销和精力开销.host 和device上的内存都是惰性分配的,从而能够高效使用存储空间。

传统的图片数据维数为图片数量N x 通道数K x 高度H x 宽度W。由于Blob的内存布局是行优先,所以最右边/后边的维度变化的最快。例如,在一个4D的blob里,下标(n,k,h,w)在物理内存中位于下标((nK+k)H+h)*W+w).

  • Number / N 是数据的 batch size.批处理能获得更大的在GPU设备上的吞吐量。例如,对于ImageNet数据训练一批256个图片,N=256.
  • 通道数 / K 是 feature dimension, 例如RGB图片就是3通道的 K = 3.灰度 K=1

注意,尽管Caffe样例中的大多数blob都是4D的带坐标的图片应用,在非图片应用使用Blob也是完全可以的。例如,你仅仅需要一个全连接网络(比如传统多层感知机),使用一个2D的blob(shape(N,D)),调用InnerProductLayer就可以了。

参数blob的维度随着layer的配置和类型变化。例如,对一个有96个filters,每个filter有11X11的空域维度和3个输入的卷积层,它的blob维数为: 96 x 3 x 11 x 11.
对于一个有着1000个输出和1024个输入的内积 / 全连接layer,它的参数blob1000 x 1024

对于定制的数据,可能需要自己手工编写输入数据预处理工具或者数据层。但是一旦你的数据准备好了,剩下的工作就交给Caffe了。


实现细节

由于我们经常对blob的值和梯度感兴趣,所以blob存储了2块datadiff.前者是正常的传输数据,后者是网络计算的梯度。

更进一步,由于真实数据可能存储在CPU或者GPU上,有2种方式来访问它们:const方式,不能修改值;mutable方式,可以修改值:

1
2
const Dtype* cpu_data() const;
Dtype* mutable_cpu_data();

(gpu 和 diff接口类似)。

这样设计的原因是:Blob使用了SyncedMem类来同步CPU和GPU之间的数据以便隐藏同步细节,同时最小化hostdevice之间的数据交换。第一原则是:当你不需要修改值的时候总是使用const方式,并且绝对不要在你自己的对象里存储指针。没当你使用一个blob的时候,调用上面的函数来获取数据指针,这时SyncedMem就会需要根据这个指针来判断什么时候去复制数据。(这个功能怎么实现的,很有意思,等看完代码再分析)。

在实践中如果使用了GPU,你从磁盘上吧数据读取到CPU模式的内存中的blob里,然后调用GPU的kernel来进行计算,然后把blob数据传给下一层,这一切过程都隐藏了底层的实现细节,并且获得很高的性能。只要所有层都有GPU实现,所有的中间数据和梯度都会保存在GPU中。

如果你像检查什么时候Blob会复制数据,这里有一个演示:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 假设数据初始在CPU模式下,我们有一个blob.
const Dtype* foo;
Dtype* bar;
foo = blob.gpu_data(); // 数据从 cpu 复制到 gpu
foo = blob.cpu_data(); // 没有数据拷贝,因为cpu 和gpu都有最新的数据内容
bar = blob.mutable_gpu_data(); // 没有数据拷贝
// .. 一些操作 ..
bar = blob.mutable_gpu_data(); // 没有数据拷贝,因为仍然处在 GPU上
foo = blob.cpu_data(); // 数据从gpu->cpu,因为gpu上修改了数据
foo = blob.gpu_data(); // 没有数据拷贝,因为都有最新内容
bar = blob.mutable_cpu_data(); // still no data copied
bar = blob.mutable_gpu_data(); // data copied cpu->gpu
bar = blob.mutable_cpu_data(); // 数据从gpu->cpu

层的连接和计算

layer是一个模型的精华所在,它也是计算的基本单元。layer包括了filter过滤,pool池化,进行inner product计算,应用诸如rectified-linearsigmoid等元素级的非线性变换,正则化,读取数据,计算诸如softmaxhinge等代价损失。查看Layer catalogue获取全部操作。大部分最新的深度学习任务都在那里。

一个从底层连接获取数据并从顶层连接输出的layer

每个layer都定义了3个关键的计算操作:setup,forwardbackward.

  • Setup: 在模型初始化的时候初始化layer和它的connections
  • Forward: 从底层给出输入并计算输出,然后发送给顶层
  • Backward: 给出顶层输出的梯度,计算输入的梯度,然后发送给底层。一个有参数的层会计算关于参数的梯度然后在内部存储这些梯度。

更详细的说,caffe将会实现2个Forward和Backward函数,一个给CPU,另一个给GPU.如果你没有实现GPU版本,那么layer就会退化成CPU函数作为一个后备选项。
如果你要做快速实验,这个会用起来很顺手,尽管它会造成附加的数据传输开销(它的输入会从GPU复制到CPU,并且它的输出会从CPU拷贝到GPU);

layer在把网络当做整体进行操作的时候有两个关键责任:前向传播从输入计算输出,反向传播获取输出的梯度,然后根据参数向前计算输入的梯度,这些梯度再依次向前传播。这些过程都是简单的前向传播和后向传播的组合。

开发自己定义的层需要一点很小的努力,需要学习网络的组织和代码的模块画。定义每层的setup,forward,backward,然后你定义的这个层就可以包含进一个网络了。


网络定义和操作

net通过组合和自动求导联合定义了一个函数和它的导数.把每一层output组合起来计算一个特定任务的函数,把每一层的backward组合起来从loss计算梯度来学习该任务。Caffe模型是端对端的机器学习引擎。(这个和Theano类似的)

net可以看做一个由layers组成的计算图(computation graph),确切的说是一个有向无环图。Caffe为所有层做了所有bookkeeping的工作来保证前向传播和后向传播的正确性。典型的net由一个从磁盘读取数据的数据层开始,以一个loss层结束,是计算诸如分类或者重构之类的目标任务的。

net用普通文本建模语言protocol buffer被定义为一组layer和它们之间的连接,一个简单的 logistic regression 分类器如下:

logistic regression

定义为:

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
name: "LogReg"
layer {
name: "mnist"
type: "Data"
top: "data"
top: "label"
data_param {
source: "input_leveldb"
batch_size: 64
}
}
layer {
name: "ip"
type: "InnerProduct"
bottom: "data"
top: "ip"
inner_product_param {
num_output: 2
}
}
layer {
name: "loss"
type: "SoftmaxWithLoss"
bottom: "ip"
bottom: "label"
top: "loss"
}

模型初始化由函数Net::Init()处理。初始化主要做了2件事:创建blobs和layers架起整个DAG(对c++使用者:在整个生命周期里network会持有blobs和layers的所有权),并且调用layer的Setup()函数。它同样做了一系列其他的准备工作,例如验证整个网络结构的正确性。同样,在初始化的过程中,Net会通过日志解释它的初始化工作,像这样:

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
I0902 22:52:17.931977 2079114000 net.cpp:39] Initializing net from parameters:
name: "LogReg"
[...model prototxt printout...]
# construct the network layer-by-layer
I0902 22:52:17.932152 2079114000 net.cpp:67] Creating Layer mnist
I0902 22:52:17.932165 2079114000 net.cpp:356] mnist -> data
I0902 22:52:17.932188 2079114000 net.cpp:356] mnist -> label
I0902 22:52:17.932200 2079114000 net.cpp:96] Setting up mnist
I0902 22:52:17.935807 2079114000 data_layer.cpp:135] Opening leveldb input_leveldb
I0902 22:52:17.937155 2079114000 data_layer.cpp:195] output data size: 64,1,28,28
I0902 22:52:17.938570 2079114000 net.cpp:103] Top shape: 64 1 28 28 (50176)
I0902 22:52:17.938593 2079114000 net.cpp:103] Top shape: 64 (64)
I0902 22:52:17.938611 2079114000 net.cpp:67] Creating Layer ip
I0902 22:52:17.938617 2079114000 net.cpp:394] ip <- data
I0902 22:52:17.939177 2079114000 net.cpp:356] ip -> ip
I0902 22:52:17.939196 2079114000 net.cpp:96] Setting up ip
I0902 22:52:17.940289 2079114000 net.cpp:103] Top shape: 64 2 (128)
I0902 22:52:17.941270 2079114000 net.cpp:67] Creating Layer loss
I0902 22:52:17.941305 2079114000 net.cpp:394] loss <- ip
I0902 22:52:17.941314 2079114000 net.cpp:394] loss <- label
I0902 22:52:17.941323 2079114000 net.cpp:356] loss -> loss
# set up the loss and configure the backward pass
I0902 22:52:17.941328 2079114000 net.cpp:96] Setting up loss
I0902 22:52:17.941328 2079114000 net.cpp:103] Top shape: (1)
I0902 22:52:17.941329 2079114000 net.cpp:109] with loss weight 1
I0902 22:52:17.941779 2079114000 net.cpp:170] loss needs backward computation.
I0902 22:52:17.941787 2079114000 net.cpp:170] ip needs backward computation.
I0902 22:52:17.941794 2079114000 net.cpp:172] mnist does not need backward computation.
# determine outputs
I0902 22:52:17.941800 2079114000 net.cpp:208] This network produces output loss
# finish initialization and report memory usage
I0902 22:52:17.941810 2079114000 net.cpp:467] Collecting Learning Rate and Weight Decay.
I0902 22:52:17.941818 2079114000 net.cpp:219] Network initialization done.
I0902 22:52:17.941824 2079114000 net.cpp:220] Memory required for data: 201476

注意构建网络是和设备无关的,回忆前面解释blob和layer的时候他们也在构建的时候隐藏了实现细节。构建完成之后,网络就可以在CPU或者GPU上运行,只需要调用Caffe::mode()就能切换,Caffe::set_mode()是用来设置mode的函数。在GPU或者CPU上运行的过程会产生相同的结果。CPU和GPU可以无缝切换并且和模型定义无关。对研究和部署来说,把模型和实现分离是最好的方案。


模型格式

模型是用普通文本文件存储的protocol buffer schema(存在prototxt文件里),学习到的模型是被序列化为二进制格式的protocol buffer(binaryproto),存在caffemodel文件里。

模型格式是定义在caffe.proto文件里的。这个文件基本上是自解释的,推荐初学者仔细阅读它。

Most important tip…
Don’t be afraid to read the code!


Read More
post @ 2016-01-11

##1. 维度灾难

###1.1 The curse of dimensionality
bellman
Richard E.Bellman(发明动态规划的美国应用数学家) 在1961年提出了这个术语:

The “Curse of dimensionality”, is a term coined by Bellman to describe the problem caused by the exponential increase in volume associated with adding extra dimensions to a (mathematical) space.

###1.2 用3类模式识别问题举例

  1. 一个简单的方法是:
  • 将特征空间划分为小bins
  • 计算每个bins里边每个样本对于每一类的ratio
  • 对于一个新的样本,找到它所在的bin然后将它划分到该bin里最主要的类里
    这个方法类似于k-nn算法,和桶算法类似
  1. 比如我们用单特征来划分三个类的9个实例:
     pca1
    在一维我们会注意到类之间会有太多重叠,于是我们就决定引入第二个特征试图增加可分性.
    pca2
    这时,在二维空间,如果
  • 我们选择保留样本密度,那么样本点数量就从9激增至9*3=27
  • 我们选择保留样本数量,那么2维的散点图就十分稀疏
    该怎么抉择呢?再增加一个feature?
    pca3
    在3维空间,事情变得更糟糕:
  • bins的数量增加到27
  • 维持样本密度不变,样本点的数量就增加到了81
  • 维持样本点个数不变,那么3D散点图几乎就是空的

很明显,我们用相同的bins来划分样本空间的办法是十分低效率的

1.3 我们如何打败维度灾难?

  • 引入先验知识?
  • 提高目标函数的光滑性(例如光滑核方法),可使问题的推论性增强,甚至变为解析问题.然而,这需要大量的训练样本和训练时间.
  • 减少维度!(是否和前面加入特征矛盾)

在实践中,维度灾难意味着,给定一个样本大小,存在一个维数的上限,超过了这个上线,分类器的性能就会不升反降.
pca4
很多时候,在低维空间做更准确的映射比在高维空间直接映射有更好的分类性能.

1.4 维度灾难更加深刻的含义

  • 保持样本密度需要指数级增长的样本数量
    • 给定一个密度为N的样本和D维,需要的总样本数为$N^D$
  • 密度估计的目标函数复杂性也随着维度增长呈指数增长

fredman

定义在高维空间的函数比定义在低维空间的函数复杂的多,并且那些复杂性是难以辨明的复杂.这意味着,为了更好的学习它,越复杂的函数需要越密集的样本点 –by Friedman( famous for his friedman test)

  • 如果样本的分布不是高斯分布情况会更糟糕
    - 因为在教科书里只有大量的1维分布函数,到了高维情况就只剩下了高斯分布,而且在维度很高的情况下,高斯密度函数只能在简化的形势下处理.
  • 人脑也对4维以上的特征失去了辨识能力(但是人脑为什么可以辨识复杂的模式呢)

##2. 降维

2.1 特征选择 vs. 特征提取

  • Feature extraction:从现有的特征组合中生成一个特征子集
  • Feature selection:选择包含全部特征信息的子集(新的特征由原来的一维或者多维特征映射获得)
       pca5

2.1.1 特征抽取的定义

  • 给定一个特征空间 $x_i \in R^N$ 找出一个映射: $y=f(x):R^N \rightarrow R^M$ 其中 $M \lt N$,这样,变换后的特征向量 $y_i \in R^M$ 保存了(大多数)原来特征空间 $R^N$内的信息(或结构)
  • 一个最优的映射的引入$y=f(x)$不会增加分类错误(就是对同一个算法说和原来的分类正确率一样)

2.2 最优映射 y=f(x) 

通常,一个最优映射 y=f(x)是一个非线性函数,但是,没有一个系统和成熟的方法进行非线性变换,非线性变换的数学理论还很不成熟.(对特定特征子集的选择还要结合具体问题具体分析).因此,特征抽取常常被限定为了线性变换 $y=Wx$.


2.3 信号表示 vs. 分类

选择特征抽取映射$y=f(x)$的办法是找到一个目标函数,对其进行最大化或者最小化.按照目标函数的条件,特征提取技术被分为了两类:

  • Signal representation: 目标是在更低的维度对样本信息精确的表示
  • classification:目标是在低维上增强样本的可分类性.

pca7
   
在线性特征提取的领域内,常用的技术有两个:

  • Pricipal Components Analysis主成分分析:用于信号表示
  • Linear Discriminant Analysis线性判别分析(fisher 1936):用于样本分类

##3. Principal Component Analysis(PCA)


3.1 PCA的目标

PCA的目标是在降维的同时尽可能多的保留高维空间的随机性(方差)

3.2 PCA 的推导

假设 x 是一个 N-维随机向量,表示为一组正交基向量[$\phi_1|\phi_2|….|\phiN$]的线性组合
$$
x = \sum
{i=1}^N y_i \phi_i \quad where \quad \phi_i\cdot \phi_j =
\begin{cases}
0, &\text{i $\neq$ j}\[2ex]
1, &\text{ i = j }
\end{cases}
$$

假设我们只选择了基向量中的M(M<N)维来表示x,我们可以用预先选择的常量$bj$来替换$[y{M+1},…,yN]^T$
$$
\hat x (M) = \sum
{i=1}^M y_i\phii + \sum{i=M+1}^N b_i \phii
$$
两种表示形式的方差为:
$$
\Delta x(M) = x- \hat x(M) = \sum
{i=1}^N y_i \phii - \left \lbrace \sum{i=1}^M y_i\phii + \sum{i=M+1}^N b_i\phii \right\rbrace = \sum{i=M+1}^N (y_i-b_i)\phi_i
$$
我们可以用均方差来表示这个误差的大小.   
   
我们的目标是找到使均方误差最小的参数:基向量$\phi_i$和常量$b_i$
$$
\overline \epsilon^2(M) = E [|\Delta x(M)|^2] = E \left [ \sum{i=M+1}^N \sum{j=M+1}^N (y_i-b_i)(y_j-b_j) \phi_i^T\phij \right] = \sum{i=M+1}^N E \left [ (y_i-b_i)^2 \right]
$$
这里之所以能抵消是因为,当 $i \neq j $ 时, $ \phi_i \cdot \phi_j = 0 $
当 $ i = j$ 时,$ \phi_i \cdot \phi_j = 1 $

问题现在转化成了求 $b_j$ 和 $\phi_i$,我们可以用对目标函数求偏导数并且令偏导数为0的方法来求$b_i$.
8

现在,把$b_i = E [y_i] $ 代入上边的公式,均方误差可以变换成方差的正交化形式:

9
其中 $\sum_X$ 是 x 的协方差矩阵.

现在,引入拉格朗日因子:
10
对每个 $\phi_i$ 求偏导:
11
于是,$\phi_i$和$\lambda_i$就是协方差矩阵 $\sum_X$ 的特征值和特征向量

这样,我们就能把均方差的和表示为:
12

为了最小化这个式子,$\lambda_i$ 必须是最小的特征值

  • 因此,用最小方差和来表示 x ,我们将会选择 最大的特征值$\lambda_i$对应的特征向量$\phi_i$

3.3 总结

把随机向量 X 投影到 其协方差矩阵$\Sigma_X$的最大特征值$\lambda_i$对应的特征向量$\phi_i$上,我们就可以得到N维随机向量 $x \in \mathscr R^N$ 的一个最优(有误差的最小方差和)近似: M 个独立向量的线型组合.

注意:

  • 由于PCA使用了协方差矩阵的特征向量,它能够找到单峰正态分布下数据的独立分布
    • 对于非高斯分布或者多峰正态分布数据,PCA只是简单的去相关
  • PCA的主要限制是它没有考虑类别的可分性,因为它没有考虑类标签
    • PCA只是简单的将坐标转向了有最大方差的方向
    • 而有最大方差的方向并不保证有良好的可分类特征
      例如:
      13
      用PCA的话,会降维到Y轴上,因为Y轴有最大的方差.然而降维到y轴之后,样本几乎不可分,因为都混杂在一起了.

3.4 举例

  • 计算下列2维数据集的 pricipal components:
    $ X = (x_1,x_2) = \lbrace (1,2),(3,3),(3,5),(5,4),(5,6),(6,5),(8,7),(9,8) \rbrace$
  • 求解过程
    • 协方差矩阵是:
      $$
      \Sigma_X = \begin{bmatrix} 6.25& 4.25\ 4.25 & 3.5 \end{bmatrix}
      $$
    • 求特征值:
      15
    • 特征向量:
      16

4.实现PCA算法


4.1 数据预处理

在应用PCA算法之前,我们常常要对数据进行预处理,因为PCA算法对原始数据的可靠性,一致性,以及规范性十分敏感,如果不做相应的处理,算法的效果就会大打折扣.
通常我们希望所有的特征 $x_1,x_2,…,x_n$都有相似的取值范围(并且均值接近0).在部分应用中,我们都有必要对每个特征做预处理,即通过估算每个特征$x_j$的均值和方差,而后将其取值范围规整化为零均值单位方差.

通常,预处理主要有2步:

  • feature scaling/mean normalization 均值规整化为 0
  • 白化,一些文献中也叫 sphering ,白化的目的就是降低输入的冗余性,通过白化使得学习算法的输入具有一下性质:
    • (1) 特征之间相关性较低
    • (2) 所有特征具有相同的方差(分布的离散程度相同)

4.1.1 均值规整化

假设我们有训练集: $ x^{(1)},x^{(2)},…x^{(m)}$
均值规整化过程:

  1. 求每个特征的均值 $\mui = \frac1m \sum{i=1}^m x_j^{(i)}$
  2. 把每个特征的值$x_j^{(i)}$ 替换为 $x_j-\mu_j$
  3. 如果不同的特征之间的取值范围不一样(例如: $x_1$ = size of house(大多取值 1000多) $x_2$ = number of bedrooms(取值不超过10) ), 就需要把每个特征的刻度转换成和其他特征差不多的取值范围:
    $$ x_j^{(i)} = \frac{x_j^{(i)}=\mu_j}{S_j} $$
    这里 $S_j$是某种对特征j的取值范围的度量.(常常是最大值减最小值 或者是标准差)

4.1.2 白化

  • 消除输入特征之间的相关性:

将原始样本值映射到新基上的过程 $ x{rot}^{(i)} = U^T x^{(i)} $ 实际上已经消除了输入特征 $ x^{(i)}$ 之间的相关性.因为对于映射后的样本 $ x{rot} $ 来说,它的协方差矩阵 $\Sigma_{rot}$是一个对角矩阵,而且对角线上的元素值为特征值,由于非对角线元素都为0,所以特征之间是不相关的.

  • 使所有特征具有单位方差:

为了使所有特征具有单位方差,我们可以直接使用 $ \frac1{ \sqrt{ \lambdai } }$作为缩放因子来缩放每个特征 $ x{rot,i} $.具体的,我们定义白化后的数据 $x_{PCAwhite} \in \mathscr R^N $ 如下:

$$
x{PCAwhite,i} = \frac{x{rot,i}}{ \sqrt{ \lambdai } }
$$
这样一来,白化后的数据$x
{PCAwhite} $ 的协方差矩阵就变成了 单位矩阵.我们说, $x{PCAwhite} $ 是数据经过 PCA白化后的版本,$x{PCAwhite} $ 中不同的特征之间部相关并且具有单位方差.

  • 正则化

在实践中,白化过程中,有些特征值 $ \lambda_i $ 在数值上接近于0,这样在缩放步骤时,我们除以 $ \sqrt{ \lambdai } $将导致除以一个接近0的值;这可能使数据上溢或者造成数值不稳定.因而在实践中,我们使用少量的正则化实现这个缩放过程,即在取平方根的倒数之前给特征值加上一个很小的常数 $ \epsilon $ :
$$
x
{PCAwhite,i} = \frac{x_{rot,i}}{ \sqrt{ \lambda_i } + \epsilon }
$$
当 $ x $ 在区间 $ [-1, 1] $ 上时,一般取值为 $ \epsilon \approx 10^{-5} $


4.2 PCA 算法

  1. 首先,计算 协方差矩阵
    $$
    \Sigma = \frac1m \sum_{i=1}^n (x^{(i)})(x^{(i)})^T
    $$
    其中 $\Sigma$ 是 n x n 大小的协方差矩阵 , 因为 $ x^{(i)}$ 是 n x 1 (一个样本), $(x^{(i)})^T$ 是 1 x n .
  2. 计算协方差矩阵 $ \Sigma $ 的特征向量:
    1
    2
    3
    [U,S,V] = svd(Sigma);
    //或者
    [U,S,V] = eig(Sigma);

关于这里为什么要用 svd函数,因为 PCA 根据应用领域的不同,还有很多别名:
线性代数中叫 :SVD(singular value decomposition of X ) EVD(eigenvlaue decomposition of $X^TX$) ,KLT(信号处理),POD(机械工程).

这样,我们得到了 [U,S,V],其中 U 就是 把特征向量按照对应的特征值大小从大到小排列所得到的一个 n x n 特征向量矩阵,这就是一个变换后的正交基
$$
\begin{align}
U =
\begin{bmatrix}
| & | & & | \
u_1 & u_2 & \cdots & u_n \
| & | & & |
\end{bmatrix}
\end{align}
$$
我们将要使用这个矩阵来降维,要将原来的数据 $x \in R^n$ 映射到 $z \in R^k (k<n)$,需要使用前 K 个最大的特征值对应的特征向量(因特征值大的更能代表数据特征)组生成一组新的正交基:

$$
\begin{align}
U_{reduce} =
\begin{bmatrix}
| & | & & | \
u_1 & u_2 & \cdots & u_k \
| & | & & |
\end{bmatrix}
\end{align}
$$

1
Ureduce = U(:,1:k);

这样以来,我们就可以在新基上用投影的方式表示原来的数据了:
$$
\begin{align}
Z =
\begin{bmatrix}
| & | & & | \
u_1 & u_2 & \cdots & u_k \
| & | & & |
\end{bmatrix}^T \cdot X =
\begin{bmatrix}

  • & (u^1)^T & - \
  • & (u^2)^T & - \
    & \vdots & \
  • & (u^k)^T & -
    \end{bmatrix} \cdot X =
    \begin{bmatrix}
    z^1 \
    z^2 \
    \vdots \
    z^k
    \end{bmatrix}
    \end{align}
    $$
    这样,
    $$
    \begin{align}
    \begin{bmatrix}
    x^1 \
    x^2 \
    \vdots \
    x^n
    \end{bmatrix} \Longrightarrow
    \begin{bmatrix}
    z^1 \
    z^2 \
    \vdots \
    z^k
    \end{bmatrix}
    \qquad\color{lime}{(k<n)}\quad\color{red}{高维数据被投影到低维的正交基向量组上,实现了降维}
    \end{align}
    $$
    1
    z = Ureduce'*x;

4.3 python 代码实现

数据下载地址

代码github地址

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#coding=utf-8
import numpy as np
__author__ = 'anboqing'
"""
feature scaling and mean normalization
零均值化
"""
def zeroMean(dataMat):
print("feature scaling ... ")
meanVal = np.mean(dataMat,axis=0) # axis = 0 means that calculate mean value by column(every feature)
print("mean normalization ...")
newVal = dataMat - meanVal
return newVal,meanVal
"""
求预处理之后的样本矩阵的协方差矩阵
"""
def covarianceMat(normal_data):
'''
计算协方差矩阵
:param normal_data: 零均值规范化过的数据
:return: 协方差矩阵
'''
print('calculate the covariance matrix ... ')
covMat = np.cov(normal_data,rowvar=0)
"""
numpy中的cov函数用于求协方差矩阵,
参数rowvar很重要,
若rowvar=0,说明传入的数据一行代表一个样本,
若rowvar!=0,说明一列代表一个样本
"""
return covMat
def eigenValAndVector(covMat):
"""
求协方差矩阵的特征值和特征向
:param covMat: 协方差矩阵
:return: 协方差矩阵的特征值,特征向量
"""
print('calculate eigen value and eigen vector of covariance matrix...')
eigVals,eigVects = np.linalg.eig(np.mat(covMat))
return eigVals,eigVects
def reduceDimensionality(eigVals,eigVects,dataMat,k=1):
"""
降维:保留主要成分
用前k个特征向量组成新的正交基,把原始数据映射到新的正交基上
:param eigVals: 原始数据的协方差矩阵的特征值
:param eigVects: 原始数据的协方差矩阵的特诊向量
:param dataMat: 原始数据
:param k: 要降维到多少维
:return: 降维后的数据,投影的正交基
"""
print('reduce the dimension ... ')
eigValIndices = np.argsort(eigVals) # 对特征值从小到大排序
n_eigValIndices = eigValIndices[-1:-(k+1):-1] # 最大的k个特征值的下标
data_mat_trans = eigVects[:,n_eigValIndices] # 取出前k个最大的特征向量
low_dimensional_data = dataMat * data_mat_trans # 将原始数据投影到新的向量空间的正交基上
return low_dimensional_data,data_mat_trans
def load_libsvm_data(file_path):
fin = open(file_path)
print('load data : '+file_path)
data_mat=[]
label_vec = []
for strline in fin.readlines():
line_arr = strline.strip().split()
label_vec.append(int(line_arr[0]))
line_arr = line_arr[1:]
row_arr = []
idx = 1
for pair in line_arr:
str_indice,str_val=pair.split(":")
indice = int(str_indice)
fval = float(str_val)
#print indice,fval
if indice == idx:
row_arr.append(fval)
else:
row_arr.append(0.0)
idx=idx+1
data_mat.append(row_arr)
return data_mat,label_vec
def choosePCASize(eig_vals,percentage=0.99):
'''
计算主成分个数的函数
:param eig_vals: 特征值数组
:param percentage: 要保留的方差的百分比
:return:应该降到的维数
'''
asc_eigs = np.sort(eig_vals) # 升序
desc_eigs = asc_eigs[-1::-1] # 翻转成从大到小
eig_sum = sum(desc_eigs)
tmpSum =0
num = 0
for i in desc_eigs:
tmpSum += i
num+=1
if tmpSum >= eig_sum * percentage:
return num
if __name__ == "__main__":
file_path = 'madelon'
# 读取livsvm格式的数据
data_mat,label_vec = load_libsvm_data(file_path)
# 转换成 numpy matrix 结构
dataMat = np.mat(data_mat)
# 数据零均值化
new_dat,mean_dat = zeroMean(dataMat)
# 计算协方差矩阵
cov_mat = covarianceMat(new_dat)
#print np.shape(cov_mat)
# 计算协方差矩阵的特征值和特征向量
eigen_values,eigen_vectors = eigenValAndVector(cov_mat)
# 选择要降到的维数(保存99的方差)
num_ = choosePCASize(eigen_values)
# 试着把这个数据集降维为num_2维
low_dim_mat,orth_base = reduceDimensionality(eigen_values,eigen_vectors,new_dat,num_2)
print np.shape(low_dim_mat)
print np.shape(orth_base)

4.4 选择主成分的个数

在应用PCA的时候,对于一个1000维的数据,我们怎么知道要降维到多少维才是合理的?也就是要在保留最多信息的同时取出最多的噪声.Andrew Ng的机器学习课讲的方法是:

  1. 算出 Average squared projection error: $$\frac1m \sum{i=1}^m \left\lVert x^{(i)} - x{approx}^{(i)} \right\rVert^2$$
  2. 算出 Total variation in the data: $$\frac1m \sum_{i=1}^m \left\lVert x^{(i)} \right\rVert^2$$
  3. 然后,选择满足下列条件的 k :
    $$ \frac{\frac1m \sum{i=1}^m \left\lVert x^{(i)} - x{approx}^{(i)} \right\rVert^2}{\frac1m \sum{i=1}^m \left\lVert x^{(i)} \right\rVert^2} \le 0.01 \qquad(1\%)$$
    也就是说: 保留了 99 % 的方差,其中 0.01可以根据应用的不同来自己设定
    上式也可以改成:
    $$
    1 - \frac{\sum
    {i=1}^k \lambdai}{\sum{i=1}^n \lambda_i} \le 0.01
    $$
    其中$\lambda_i$ 是协方差矩阵的特征值

自动选择维数的算法:

Automatic choice of dimensionality for PCA
Thomas P. Minka


欢迎访问我的博客


Read More

编程范式

范式

Paradigm: In science, a paradigm describes distinct concepts or thought patterns in some scientific discipline.

主要的编程范式:

  • 命令式 : c , c++ , java …
  • 函数式 : scala , haskell , Lisp …
  • logic programming : prolog …
    和这种分类方式正交的:
    面向对象编程

命令式语言 和 计算机

  1. 变量 —> 内存单元
  2. 变量解引用 —> 加载指令
  3. 变量赋值 —> 存储指令
  4. 控制结构 —> jumps 跳转命令

命令式语言的限制:

One tends to conceptualize data structures word-by-word.

我们需要其他技术来定义高层次的数据抽象:集合,多项式,几何图形…

理想情况下: 开发 theories of collections,shapes , strings…


什么是Theory
A theory consists of :

  • one or more data types
  • operations on these types
  • laws that describe the relationships between values and operations

a theory does not describe mutations ! mutations mean change the thing while keeping the identity of the thing.


Consequences for Programming

If we want to implement high-level concepts following their mathmatical theories,there’s no place for mutation.

  • Theories do not admit it
  • Mutation 会破坏Theories 里面有用的lows

因此,让我们

  • 专注于定义 theories for operators expressed as functions
  • avoid mutations
  • have powerful ways to abstract and compose functions.

函数式编程

  • 狭义的概念: 函数式编程是指没有 变量,赋值,循环 和其他命令式控制结构的编程
  • 广义上指:函数式编程enables the construction of elegant programs that focus on functions.
  • 特别的:functions can be values that are produced,consumed,and composed
    在函数式编程语言里面,函数是一等公民:
    它们可以在任何地方定义,包括在其他函数内
    像其他任何值一样,可以当做参数和返回值
    有一组运算符来compose函数
Read More
post @ 2016-01-10

什么是 protocol buffers ?

Protocol buffers 是一种灵活、高效的序列化结构数据的自动机制--想想XML,但是它更小,更快,更简单。你只需要把你需要怎样结构化你的数据定义一次,你就能使用特殊生成的代码来方便的用多种语言从一系列数据流中读写你的结构化数据。你甚至不需要中断你用”老”结构编译好的已经部署的程序来更新你的数据结构。


它是怎样工作的?

你在一个名为.proto的文件里用protocol buffer message 定义你需要序列化数据的结构。每个protocol buffer message 是一个小的信息逻辑记录,包含了一系列的name-value对。这里有一个简单的.proto例子,它定义了一个person的信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
message Person {
required string name = 1;
required int32 id = 2;
optional string email = 3;
enum PhoneType {
MOBILE = 0;
HOME = 1;
WORK = 2;
}
message PhoneNumber {
required string number = 1;
optional PhoneType type = 2 [default = HOME];
}
repeated PhoneNumber phone = 4;
}

就像你看到的,这条信息结构很简单—每条message type 都有一个或多个独特的属性,每个属性都有一个name和一个value类型,value类型可以是numbers ( 整数或浮点数),booleans,strings,raw bytes或者其他protocol buffer message types,允许你以嵌套结构组织你的结构。你可以指定optional,required、和repeated属性。你可以从 Protocol Buffer Language Guide找到更多的关于如何写.proto文件的信息。

一旦你定义了你的信息,你就可以运行protocol buffer 编译器来编译你的.proto文件来生成特定语言的数据访问类。这些类提供了简单的对属性的访问函数(例如 name()set_name() )和用来序列化整个结构到raw bytes和从raw bytes 解析出结构的函数。例如,假如你使用的是c++语言,用编译器编译上面那个person.proto文件会生成一个Person类。你可以在你的应用里用这个类来操纵Person类的对象。比如,你可能会写一些这样的代码:

1
2
3
4
5
6
Person person;
person.set_name("John Doe");
person.set_id(1234);
person.set_email("jdoe@example.com");
fstream output("myfile", ios::out | ios::binary);
person.SerializeToOstream(&output);

然后,你可以通过这样的代码来把你的message读进来:

1
2
3
4
5
fstream input("myfile", ios::in | ios::binary);
Person person;
person.ParseFromIstream(&input);
cout << "Name: " << person.name() << endl;
cout << "E-mail: " << person.email() << endl;

你可以给你的message添加新的属性而不打破向后兼容性(backwards-compatibility);旧的二进制文件仅仅在编译的时候忽略那些新的属性。这样一来,如果你有一个通信协议使用了protocol buffers当做它传输的数据格式,你可以扩展你的通信协议而不用担心破坏现有的代码。

你可以在API Reference section找到完整的文档,并且你可以在Protocol buffer encoding找出关于protocol buffer 编码的更多信息.


为什么不用XML等其他技术?

Protocol buffers相对XML在序列化数据的时候有很多优势。protocol buffers :

  • 更简单
  • 比XML小3到10倍
  • 比XML快20到100倍
  • 更少歧义
  • 可以生成方便编程的数据访问类

例如,假若你要给person建模,它有nameemail属性。在XML里,你需要:

1
2
3
4
<person>
<name>John Doe</name>
<email>jdoe@example.com</email>
</person>

用protocol buffer message(在protocol buffer 的text format)是这样的

1
2
3
4
5
6
# Textual representation of a protocol buffer.
# This is *not* the binary format used on the wire.
person {
name: "John Doe"
email: "jdoe@example.com"
}

当上面这段代码被编译成binary format(上面那段text format只是为了方便人类读写编辑的)的时候,它可能只占28字节长,仅仅需要100~200纳秒就能编译。那个XML版本即使移除所有空白也至少需要69字节,并且需要5000~10000纳秒来编译。

同样,操作protocol buffer 更容易:

1
2
cout << "Name: " << person.name() << endl;
cout << "E-mail:" << person.email() << endl;

然而如果使用XML你需要这样做:

1
2
3
4
5
6
cout << "Name: "
<< person.getElementsByTagName("name")->item(0)->innerText()
<< endl;
cout << "E-mail: "
<< person.getElementsByTagName("email")->item(0)->innerText()
<< endl;


嗯~听起来能解决我的问题!我该怎样开始呢?

下载地址–这个包包含了完整的c++,python和java语言的编译器源代码,和I/O和测试的类。安装请参阅README。

一旦你安装好了,就可以跟着入门教程来学习了。


入门教程c++版

这个教程会带你走一遍使用protocol buffer的流程,创建一个简单的实例程序,学会基本的使用方法:

  • .proto文件里定义信息格式
  • 使用protocol buffer编译器
  • 使用c++ protocol buffer API来读写信息

为什么使用protocol buffers?

在这个教程里我们要创建一个简单的“地址簿”程序来在文件里读写人们的联系人信息。每个人都有一个name,id,email address和一个联系电话。

你怎样序列化和读取这样一个结构数据呢?这里有三种方法:

  • 内存中原始的字节数据结构可以存储为2进制形式。这种方法很脆弱,因为读取代码必须用同样的内存布局编译,还要考虑使用相同的内存大小端等等。当文件积累了很多数据之后,拷贝到处都是,扩展结构就很困难了。
  • 你可以发明一个点对点的方式来把数据编码为一个简单的字符串—例如编码4个整数为”12:3:-23:67”.这是一个简单且灵活的方法,尽管它需要你编写一次性的读写代码,读取需要一些运行时间。这种方法适用于编码十分简单的数据。
  • 序列化数据到XML文件。如果你需要和其他程序共享数据,那么这将是个好方法。然而,XML占内存已经臭名昭著了,解析编码它会造成程序性能大幅下降。在XML DOM tree里巡弋也远比在类里查找属性复杂的多。

protocol buffers 灵活高效,可以解决上述问题。你只需要编写一个.proto文件来描述你要使用的数据结构。protocol buffer 编译器可以把.proto文件编译成一个类似于ORM(object relation mapping)实现类的数据访问类,这个类可以把高效的用二进制文件方式存储的数据读写出来。更多的是,它提供了一种向后兼容的扩展机制,使你可以不用担心兼容性问题来扩展你的数据格式。


定义你的protocol Format

为了创建地址簿程序,你需要首先定义一个.proto文件。定义.proto文件十分简单: 你添加一个 message 给你想序列化的每个数据结构 ,然后指定一个 name和一个typemessage的每个属性。下面是一个.proto文件,定义了地址簿数据结构,addressbook.proto:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package tutorial;
message Person {
required string name = 1;
required int32 id = 2;
optional string email = 3;
enum PhoneType {
MOBILE = 0;
HOME = 1;
WORK = 2;
}
message PhoneNumber {
required string number = 1;
optional PhoneType type = 2 [default = HOME];
}
repeated PhoneNumber phone = 4;
}
message AddressBook {
repeated Person person = 1;
}

protobuffer支持的内建数据类型包括bool,int32,float,double,string.
注意:message可以嵌套,比如 PhoneNumber 就定义在Person里。
“=1”,“=2”标记了每个元素的唯一“tag”,这是用在二进制编码里的。使用1-15可以在1个字节里表示这些tag,节省空间,一般把常用的需要大量重复的元素使用1-15来编码,把16以上的tag留给不常用的元素。

每个属性必须标记为下列修饰符之一:

  • required : 故名思议就是必须提供值的属性,当你把属性设置为required的时候要小心,因为如果以后想修改为其他类型,老的读取类就不兼容新的数据了。
  • optional: 就是可以不提供值的属性,如果没有提供值,会设置为默认值。默认值可以自己提供,如果没有自己提供默认值,会设置为系统默认值:numeric类型会置为0,字符串置为空串,bool置为false;对于内嵌类型,默认值永远是空实例。
  • repeated:就是可能重复任意次(包含0次).重复值的顺序会在二进制文件保存下来,可以把重复的属性看做动态大小的数组。注意,由于历史原因,repeated数值属性不能有效的被编码成二进制,新的代码可以使用[packed=true]来获得更好的编码效率

    例如: 

    int32 samples = 4 [packed=true];```
    1
    2
    3
    4
    5
    6
    ---
    ### 编译你的protocol buffers文件
    现在你拥有一个`.proto`文件,接下来你需要生成一个读写你的`AddressBook`类的访问类。你需要用protocol buffer编译器`protoc`来编译你的`.proto`文件:
    > ```protoc -I=\$SRC_DIR --cpp_out=\$DST_DIR \$SRC_DIR/addressbook.proto

cpp_out可以换成python_out或者java_out
编译完成后,就会在DST_DIR下面生成2个文件:

  • addressbook.pb.h
  • addressbook.pb.cc

Protocol Buffer API

我们现在来看一些生成的code是什么样的,编译器为我们生成了什么类和函数呢?
如果我们打开tutorial.pb.h,我们会看到编译器给我们在.proto文件里定义的每一个message都生成了一个class,我们再看Person类,会发现编译器给message的每个属性都生成了getters和setters,例如,对于name,id,email,和phone属性,我们可以找到这些函数:

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
// name
inline bool has_name() const;
inline void clear_name();
inline const ::std::string& name() const;
inline void set_name(const ::std::string& value);
inline void set_name(const char* value);
inline ::std::string* mutable_name();
// id
inline bool has_id() const;
inline void clear_id();
inline int32_t id() const;
inline void set_id(int32_t value);
// email
inline bool has_email() const;
inline void clear_email();
inline const ::std::string& email() const;
inline void set_email(const ::std::string& value);
inline void set_email(const char* value);
inline ::std::string* mutable_email();
// phone
inline int phone_size() const;
inline void clear_phone();
inline const ::google::protobuf::RepeatedPtrField< ::tutorial::Person_PhoneNumber >& phone() const;
inline ::google::protobuf::RepeatedPtrField< ::tutorial::Person_PhoneNumber >* mutable_phone();
inline const ::tutorial::Person_PhoneNumber& phone(int index) const;
inline ::tutorial::Person_PhoneNumber* mutable_phone(int index);
inline ::tutorial::Person_PhoneNumber* add_phone();

正如你所能看到的那样,getters和小写属性名一样,setters以set_开头。还有has_开头的判断是否设置了值的函数。还有clear_开头的函数用于清空设置的值。

不同类型的属性方法不尽相同,例如 id只有基本的getter,setter方法,而name,email等字符串类型的属性多了一个mutable_开头的getter,和一个多出来的setter。即使还没有设置email仍然可以调用mutable_email。它可以自动初始化为一个空字符串。

repeated属性同样有些特别的方法,例如phone属性:

  • 可以查看_size(这个人有多少个电话号码)
  • 可以通过index访问一个特定的值
  • 可以添加一个新值(通过add_方法)

更多关于编译器生成函数的信息请参看C++ generated code reference


枚举和嵌套类

生成的代码包含了一个PhoneType枚举对应你的.proto文件里的enum.你可以通过Person::PhoneType来使用这个枚举,和它的值Person::MOBILE,Person::HOME,Person::WORK(具体实现很复杂,但我们不需要了解它)

编译器同样生成了一个嵌套类Person::PhoneNumber。如果查看代码,会发现实际的类是叫做Person_PhoneNumber,但是使用了一个typedef来重命名了它,唯一的区别是当你想在另一个文件里前向声明这个类的时候,必须使用Person_PhoneNumber来前向声明它。


标准 Message方法

每个message类还包含了一些其他方法来使你能检查或者操作整个message,包括:

  • bool IsInitialized() const;: checks if all the required fields have been set.
  • string DebugString() const;: returns a human-readable representation of the message, particularly useful for debugging.
  • void CopyFrom(const Person& from);: overwrites the message with the given message’s values.
  • void Clear();: clears all the elements back to the empty state.

解析和序列化

最终,每个protocol buffer class使用读写方法来解析和序列化message到二进制文件里,这些方法包括:

  • bool SerializeToString(string* output) const;: 序列化一个message并且把字节文件存储到string里,这里使用string仅仅是为了把它当做一个方便的容器.
  • bool ParseFromString(const string& data);: 从指定的string里解析message
  • bool SerializeToOstream(ostream* output) const;: 把message写到指定的c++`ostream`里。
  • bool ParseFromIstream(istream* input);: 从指定的c++istream读取message

查看Message API获取更详细内容.


写一个Message

现在,让我们试着使用编译器为我们生成的类。我们让我们的地址簿程序做的第一件事情是把一个人的个人信息写到地址簿文件里。我们需要生成一个该类的实例然后把它写入到输出流里。

这里有一个实例程序:

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
#include <iostream>
#include <fstream>
#include <string>
#include "addressbook.pb.h"
using namespace std;
// This function fills in a Person message based on user input.
void PromptForAddress(tutorial::Person* person) {
cout << "Enter person ID number: ";
int id;
cin >> id;
person->set_id(id);
cin.ignore(256, '\n');
cout << "Enter name: ";
getline(cin, *person->mutable_name());
cout << "Enter email address (blank for none): ";
string email;
getline(cin, email);
if (!email.empty()) {
person->set_email(email);
}
while (true) {
cout << "Enter a phone number (or leave blank to finish): ";
string number;
getline(cin, number);
if (number.empty()) {
break;
}
tutorial::Person::PhoneNumber* phone_number = person->add_phone();
phone_number->set_number(number);
cout << "Is this a mobile, home, or work phone? ";
string type;
getline(cin, type);
if (type == "mobile") {
phone_number->set_type(tutorial::Person::MOBILE);
} else if (type == "home") {
phone_number->set_type(tutorial::Person::HOME);
} else if (type == "work") {
phone_number->set_type(tutorial::Person::WORK);
} else {
cout << "Unknown phone type. Using default." << endl;
}
}
}
// Main function: Reads the entire address book from a file,
// adds one person based on user input, then writes it back out to the same
// file.
int main(int argc, char* argv[]) {
// Verify that the version of the library that we linked against is
// compatible with the version of the headers we compiled against.
GOOGLE_PROTOBUF_VERIFY_VERSION;
if (argc != 2) {
cerr << "Usage: " << argv[0] << " ADDRESS_BOOK_FILE" << endl;
return -1;
}
tutorial::AddressBook address_book;
{
// Read the existing address book.
fstream input(argv[1], ios::in | ios::binary);
if (!input) {
cout << argv[1] << ": File not found. Creating a new file." << endl;
} else if (!address_book.ParseFromIstream(&input)) {
cerr << "Failed to parse address book." << endl;
return -1;
}
}
// Add an address.
PromptForAddress(address_book.add_person());
{
// Write the new address book back to disk.
fstream output(argv[1], ios::out | ios::trunc | ios::binary);
if (!address_book.SerializeToOstream(&output)) {
cerr << "Failed to write address book." << endl;
return -1;
}
}
// Optional: Delete all global objects allocated by libprotobuf.
google::protobuf::ShutdownProtobufLibrary();
return 0;
}

注意代码中的GOOGLE_PROTOBUF_VERIFY_VERSION宏,在使用c++ Protocol Buffer 之前执行这个宏是一个好的习惯(尽管不是强制要求的)。它会验证你是否链接了正确的库,防止你链接版本不匹配的库。

注意代码中的ShutdownProtobufLibrary(),它会清楚所有protocol buffer libarary分配的全局对象。通常这是不需要的,因为这个进程总是会退出,系统会接管剩下的内存。但是,如果你使用了一个内存泄露检查工具,比如valgrand之类的,这类工具会要求你把所有分配的内存释放掉,或者你在写一个库文件,这个库文件会被同一个进程加载和卸载多次,这两种情况你就需要清理所有东西。


读取一个Message

这是一个从二进制文件读取地址簿的例子:

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
#include <iostream>
#include <fstream>
#include <string>
#include "addressbook.pb.h"
using namespace std;
// Iterates though all people in the AddressBook and prints info about them.
void ListPeople(const tutorial::AddressBook& address_book) {
for (int i = 0; i < address_book.person_size(); i++) {
const tutorial::Person& person = address_book.person(i);
cout << "Person ID: " << person.id() << endl;
cout << " Name: " << person.name() << endl;
if (person.has_email()) {
cout << " E-mail address: " << person.email() << endl;
}
for (int j = 0; j < person.phone_size(); j++) {
const tutorial::Person::PhoneNumber& phone_number = person.phone(j);
switch (phone_number.type()) {
case tutorial::Person::MOBILE:
cout << " Mobile phone #: ";
break;
case tutorial::Person::HOME:
cout << " Home phone #: ";
break;
case tutorial::Person::WORK:
cout << " Work phone #: ";
break;
}
cout << phone_number.number() << endl;
}
}
}
// Main function: Reads the entire address book from a file and prints all
// the information inside.
int main(int argc, char* argv[]) {
// Verify that the version of the library that we linked against is
// compatible with the version of the headers we compiled against.
GOOGLE_PROTOBUF_VERIFY_VERSION;
if (argc != 2) {
cerr << "Usage: " << argv[0] << " ADDRESS_BOOK_FILE" << endl;
return -1;
}
tutorial::AddressBook address_book;
{
// Read the existing address book.
fstream input(argv[1], ios::in | ios::binary);
if (!address_book.ParseFromIstream(&input)) {
cerr << "Failed to parse address book." << endl;
return -1;
}
}
ListPeople(address_book);
// Optional: Delete all global objects allocated by libprotobuf.
google::protobuf::ShutdownProtobufLibrary();
return 0;
}

扩展一个Protocol Buffer

当一段时间之后你需要在你发布使用你的protocol buffer后改进你的protocol buffer定义。如果你希望你的新buffer能够向前兼容,而你的老buffer能向后兼容,那么你就需要遵守下面这几个规则:

  • 不要修改tag数字
  • 不要增删任何required属性
  • 可以删除repeated或者optional属性
  • 可以添加 repeated或者optional属性,但是必须使用新tag number

Read More

名字解释

梯度下降法又叫最速下降法,它只使用目标函数的一阶导数信息,从“梯度法”这个名字也可见一斑。并且,它的本意就是取目标函数值“最快下降”的方向作为搜索方向。于是我们就想知道这个问题的答案:沿着什么方向,目标函数 $f(x)$ 的值下降最快呢?

## 为什么负梯度方向下降最快

先说结论:沿着负梯度 $d=-g_k$,函数值下降最快

下面就来推导一下:

  • 由于目标函数 $f(x)$ 具有一阶连续偏导数,若第k次迭代值为 $x_k$,则可将目标函数 $f(x_k)$ 在点 $x_k$ 处 一阶泰勒展开(由于我们讨论的是: n维空间中的一个点移动到另一个点后,目标函数值的改变情况),因此我们展开的是改变后的函数值($f(x_k+ad)$)
    $$
    \begin{align} f(x_k+ad) = f(x_k) +g_k^Td +o(\alpha) \end{align}
    $$
    $d$:单位方向(一个向量),即 |d| = 1;
    $\alpha$: 步长(一个实数)。
    $g_k^T = \nabla f(x_k) $ : 目标函数在 $x_k$ 这一点的梯度(一个向量).

  • 显然,这个数学表达式用泰勒公式展开得到的,样子有点难看,所以对比一下自变量为一维的情况下的泰勒展开式:
    $$ \begin{align} f(x+h) = f(x) + f’(x)h +o(h) \end{align} $$
    就知道多维情况下的泰勒展开式是怎么回事了。

  • 在[1] 式中,高阶无穷小可以忽略,因此,要使[1]式取到最小值,应使$g_k^T d$取到最小——这是两个向量的点积(数量积),何种情况下其值最小呢?来看两向量$\vec a ,\vec b$的夹角θ的余弦是如何定义的:
    $$ cos \theta = \frac{a \cdot b}{ \vert a \vert \vert b \vert } $$
    假设向量 d 与 负梯度 $ -g_k$ 夹角为 $\theta$ , 我们便可以求出点积 $g_k^T \cdot d $ 的值为:
    $$ g_k^T \cdot d = - \vert g_k \vert \vert d \vert cos\theta $$
    可见,θ为0时,上式取得最小值。也就是说,direction取negative gradient时,目标函数值下降得最快,这就是称负梯度方向为“最速下降”方向的由来了。

Read More
⬆︎TOP