本文参考了博文Online Learning in Clojure和论文Pegasos: Primal Estimated sub-GrAdient SOlver for SVM(PDF)

online learning

Online learning的算法结构是非常简单的，下面的描述是监督的online learning算法框架，其中有经验损失函数\(L\)，样本流\(S\)，样本的格式为\((x,y)\):

Initialise a starting model w
While there are more examples in S
    Get the next feature vector x
    Predict the label y' for x using the model w
    Get the true label y for x and incur a penaly L(y,y')
    Update the model w if y ≠ y'

一般来是，训练出来的模型都是一个与样本相同维度的向量。对应二分的分类器，往往涉及到的是计算内积\(\langle w,x \rangle\)，模型的更新是沿着损失函数的梯度下降方向的。

Pegasos

论文Pegasos: Primal Estimated sub-GrAdient SOlver for SVM是一种svm的online learning算法。

Read More

ZooKeeper 简介

ZooKeeper是Hadoop的正式子项目，它是一个针对大型分布式系统的可靠协调系统，提供的功能包括：配置维护、名字服务、分布式同步、组服务等。ZooKeeper的目标就是封装好复杂易出错的关键服务，将简单易用的接口和性能高效、功能稳定的系统提供给用户。¹

Zookeeper是Google的Chubby一个开源的实现，关于Chubby，可以google一下，有论文介绍的。zookeeper是高有效和可靠的协同工作系统。Zookeeper能够用来leader选举，配置信息维护等。在一个分布式的环境中，我们需要一个Master实例或存储一些配置信息，确保文件写入的一致性等。

ZooKeeper是一个分布式的，开放源码的分布式应用程序协调服务，包含一个简单的原语集，是Hadoop和Hbase的重要组件。目前提供Java和C的接口。

在Zookeeper中，znode是一个跟Unix文件系统路径相似的节点,可以往这个节点存储或获取数据.如果在创建znode时Flag设置为EPHEMERAL,那么当这个创建这个znode的节点和Zookeeper失去连接后,这个znode将不再存在在Zookeeper 里.Zookeeper使用Watcher察觉事件信息,当客户端接收到事件信息,比如连接超时,节点数据改变,子节点改变,可以调用相应的行为来处理数 据.Zookeeper的Wiki页面展示了如何使用Zookeeper来处理事件通知,队列,优先队列,锁,共享锁,可撤销的共享锁,两阶段提交.

znodes与Unix文件系统路径相似相似，但是还是不同的，znode的中间节点是可以保存数据的，对应于文件系统，就即是文件又是目录。为了达到高吞吐的能力，znode在zookeeper中是放在内存中的。

ZooKeeper是以Fast Paxos算法为基础的，paxos算法存在活锁的问题，即当有多个proposer交错提交时，有可能互相排斥导致没有一个proposer能提交成功，而Fast Paxos作了一些优化，通过选举产生一个leader，只有leader才能提交propose，具体算法可见Fast Paxos。因此，要想弄懂ZooKeeper首先得对Fast Paxos有所了解。

ZooKeeper的基本运转流程：

1、选举Leader。
2、同步数据。
3、选举Leader过程中算法有很多，但要达到的选举标准是一致的。
4、Leader要具有最高的zxid。
5、集群中大多数的机器得到响应并follow选出的Leader。

Read More

火车票插件拖垮github的事件的结果，就是github被悲催地墙掉了。愤慨啊。Fuck GFW!

不过有了goagent的代理，github的网站是可以上了，但是命令行上面pull，push就不灵了。新浪微博上[@蒋伟](http://www.weibo.com/neilxp)找到了一个通过https连接github的办法，总结一下如下：

1. 安装goagent

2. 导入ca.crt证书 导入goagent目录下的local/CA.crt
   ubuntu导入证书
   http://askubuntu.com/questions/73287/how-do-i-install-a-root-certificate

3. 启动代理 python proxy.py
4. 设置代理： export HTTPS_PROXY=“http://127.0.0.1:8087”
5. github配置，关键一步是remote add的时候，方法是：
   git remote add origin https://liuhongjiang@github.com/liuhongjiang/tech.git
   这样就可以正常地pull和push了，麻烦的是，每次都要输入秘密。
   

6. 接下来就是octopress的rake deploy了： 需要修改Rakefile：

   # user = repo_url.match(/:([^\/]+)/)[1]
   user = repo_url.match(/github\.com.([^\/]+)/)[1]
   # branch = (repo_url.match(/\/[\w-]+.github.com/).nil?) ? 'gh-pages' : 'master'
   branch = (repo_url.match(/\/[\w-]+\.github\.com$/).nil?) ? 'gh-pages' : 'master'
   # project = (branch == 'gh-pages') ? repo_url.match(/\/([^\.]+)/)[1] : ''
   project = (branch == 'gh-pages') ? repo_url.match(/\/([^\/^\.]+)$/)[1] : ''

   然后在rake setup_github_pages命令中填https的url地址：
   https://liuhongjiang@github.com/liuhongjiang/tech
   同样在部署的时候，还是要输入密码

一直说写一篇2012年的总结，但元旦以来的这段时间忙东忙西，再加上自己的拖延症，始终没有写。今天终于鼓起勇气，下定决心，要把这篇总结写完，在旁边放了一把菜刀，写不完，不自刎谢罪，也要卸下一只胳膊。

2012年多多少少也是特别的一年，最主要的是那部有名的《2012》。现在庆幸时间没有终结在2012年12月21日，劫后余生。《2012》对我的影响不是那震撼的场面，也不是世界终结的恐慌，而是对人生的认识。也许明天世界就终结了，那我们应该怎么办，今天还有什么意义？12月20日那天，网上、微博上各种调侃，各种问题，五花八门。其中有个问题是这样的：明天世界都要结束了，今天晚上怎么过？各种答案，去酒吧疯狂一晚上，或者喝个天昏地暗，处男就去花点钱。我当时想的是回家早点洗洗睡了，明天还要上班啊。

把最后一天当成每一天度过，没有什么特别的，做自己该做的，完成该完成的，一步一步地往前走。这也许就是我2012年的寄语吧。

Read More

现在主流的分布式集群一致性问题大多都吸收了PAXOS算法¹的思想。然而，如果完全按照Leslie Lamport的论文²，实现复杂度比较高。因此，大多数实现都采用PAXOS的某种变形。Lamport的重要贡献，献是把分布式一致性的问题，形式化并给出了证明，给出了理论指导。³

关于Paxos算法，在网上看到了一个Fast Paxos算法，见淘宝核心系统团队博客, paxos 实现

Paxos算法看起来还是很复杂的，没有仔细研究，倒是在网上另外找到了两个简单的master选举算法。

霸道算法

Garcia-Monila 在 1982 年的一篇论文中发明了所谓的霸道选举算法（Bully Algorithm）⁴。当一个进程 P 发现协调者进程不再响应时，这个进程就召集选举。由于进程的独立性，在同一个时刻，系统中可能有多个召集选举的过程。假设 P 是召集选举的进程，每个召集选举的过程如下：

1. P 向所有比自己编号大的进程发送一条 ELECTION（选举）消息。
2. 如果 P 得不到任何回复，则 P 赢得选举，P 向所有进程发送 COORDINATOR（协调者）消息，宣布自己的胜利。
3. 如果 P 得到任何一个回复，回复一定来自于比自己编号大的进程。P 的召集选举的工作结束，因为 P 此时已经不可能赢得选举。

Read More

linux下shell提示符可以任意配置的。

首先看看bash的配置文件，一般在用户的HOME目录下有这样几个文件¹：

• .bash_history ：记录了您以前输入的命令，
• .bash_logout ：当您退出 shell 时，要执行的命令，
• .bash_profile ：当您登入 shell 时，要执行的命令，
• .bashrc ：每次打开新的 shell 时，要执行的命令。

这些文件是每一位用户的设置。系统级的设置存储在’/etc/profile’、‘/etc/bashrc’及目录’/etc/profile.d’下的文件中。但您得习惯用各自的配置文件：编辑不需要’root’权限，还可以使您的设置更有个性。当系统级与用户级的设置发生冲突时，将采用用户的设置。

每次当您打开一个控制台(console)或 xterm 时，最先看到的就是提示符(prompt)，类似于：

1

account@hostname ~ $

在默认设置下，提示符将显示您的用户名、主机名（默认是’localhost’）、当前所在目录（在Unix中，‘~’表示您的home目录）。 按照传统，最后一个字符可以标识您是普通用户（$），还是’root’（#）。 您可以通过 $PS1, $PS2 变量来设置提示符，$PS2是当在多行内输入一个命令时，换行后，出现的提示符。命令

Read More

elasticsearch是一个是开源的（Apache2协议），分布式的，RESTful的，构建在Apache Lucene之上的的搜索引擎。

它有很多特点例如Schema Free，Document Oriented。它是#nosql的，基于JSON，同时支持多种API，包括HTTP, thrift, memcached。支持HTTP,是比较爽的一点，因为基本上所有的应用都可以用ES了，页面上的js脚本都可以去查询。

安装

启动和安装特别简单，在ES下载页面下载zip或者tar包后，解压，然后到elasticsearch的目录下，运行下面的命令就可以了。

1

bin/elasticsearch -f

搭建集群也非常简单，在同网段的机器上，启动es后，它们会自动组建成一个集群，并完成数据的分布式存储，查询时也会按照分布式的方式去查找。

好了恭喜你，现在你已经可以搭建ES单机版和ES集群了，一切都这么简单。

Read More

前面两篇blog介绍了支持向量机SVM和SMO算法，这一篇就讲讲SVM的一个简单实际应用：使用svm实现一个简单的数字手写识别软件。首先要解决如何使用svm进行多类分类。

svm与多类分类¹

svm是一个二类的分类器，即它只回答属于正类还是负类的问题。而现实中要解决的问题，往往是多类的问题，比如文本分类，比如数字识别。如何由两类分类器得到多类分类器, 一般有三种方法：

一对多（一对其余）

比如我们有5个类别，第一次就把类别1的样本定为正样本，其余2，3，4，5的样本合起来定为负样本，这样得到一个两类分类器。 通过类似的方法构造类别2、3、4、5的分类器，对于测试数据，每一个分类器都过一次，在那个分类器中，被判定为正，那么就认识它属于那个分类。 但有两个问题还没有解决：一是被多个分类器判定为正，二是被所有分类器判定为负。第一种情况，可以简单地选择第一个被判定为正的分类，对二种情况，可以视为分类失败了。另外一个问题是，“其余”的那一类样本数总是要数倍于正类（因为它是除正类以外其他类别的样本之和嘛），这就人为的造成了的“数据集偏斜”问题。

Read More

上一篇blog讲到了svm的原理，最后将需要解决问题抽象成了数学公式，但如何利用计算机，解出这些数学公式的答案。换句话说，就是怎么通过计算机算出我们的svm模型的参数呢？方法就是序列最小最优化(sequential minimal optimization, SMO)算法。

首先回顾一下SVM模型的数学表达，即svm的对偶问题:

\[ \begin{array}{l} \mathop {\min }\limits_a \qquad \frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N { {a_i}{a_j}{y_i}{y_j}K({x_i},{x_j}) - \sum\limits_{i = 1}^N { {a_i}} } } \\ {\rm{s.t.}}\qquad\sum\limits_{i = 1}^N { {a_i}{y_i} = 0} \\ \qquad\qquad 0 \le {a_i} \le C, \qquad i = 1,2,\cdot\cdot\cdot,N \end{array} \]

选择一个 $ {a^*} $ 的正分量 $ 0 C $ , 计算（或者通过所有解求平均值）：

\[ {b^*} = {y_j} - \sum\limits_{i = 1}^N {a_i^*{y_i}K({x_i} \cdot {x_j})} \]

决策函数为

\[ f(x) = sign(\sum\limits_{i=1}^N {a_i^*{y_i}K({x_i}, {x_j})} + {b^*}) \]

svm的学习，就是通过训练数据计算出\({a^*}\)和\({b^*}\)，然后通过决策函数判定\({x_j}\)的分类。其中\({a^*}\)是一个向量，长度与训练数据的样本数相同，如果训练数据很大，那么这个向量会很长，不过绝大部分的分量值都是0，只有支持向量的对应的分量值大于0 。

SMO是一种启发式算法，其基本思想是：如果所有变量的解都满足了此最优化问题的KKT条件，那么这个最优化问题的解就得到了。否则，选择两个变量，固定其它变量，针对这两个变量构建一个二次规划问题，然后关于这个二次规划的问题的解就更接近原始的二次归还问题的解，因为这个解使得需要优化的问题的函数值更小。

翻译一下：对于svm我们要求解\({a^\*}\)，如果 \({a^\*}\) 的所有分量满足svm对偶问题的KKT条件，那么这个问题的解就求出来了，我们svm模型学习也就完成了。如果没有满足KKT，那么我们就在 \({a^\*}\) 中找两个分量 \({a_i}\) 和 \({a_j}\)，其中 \({a_i}\) 是违反KKT条件最严重的分量，通过计算，使得 \({a_i}\) 和 \({a_j}\) 满足KKT条件，直到\({a^\*}\) 的所有分量都满足KKT条件。而且这个计算过程是收敛的，因为每次计算出来的新的两个分量，使得对偶问题中要优化的目标函数（就是min对应的那个函数）值更小。至于为什么是收敛的，是因为，每次求解的那两个分量，是要优化问题在这两个分量上的极小值，所以每一次优化，都会使目标函数比上一次的优化结果的值变小。

Read More

是今年工作中才开始接触机器学习的，之前有所听说，但是也没有深入了解过。其实所谓的接触主要是照着李航的这本《统计学习方法》学习。当时我们是几个同事每人学习一章，学完了，然后给大家办个讲座。我想既然学习了，就应该写博客把这些内容记录下来。于是，就开始写了。

机器学习是最近十年兴起的一门学科。人工智能是计算机学界的一个公认的难题，而机器学习被认为是最有可能解决这个难题的一门学科。当然机器学习在其它很多领域都有应用，比如数据挖掘，信息检索，语言识别，图像识别等很多领域。对于机器学习的基本概念，可以看《统计学习方法》的第一章，发展历史可以看wikipedia的Machine learning。我这里就不罗嗦了。等以后再写一篇机器学习的综述文章吧。

按照《统计学习方法》的划分，机器学习可以分为监督学习，无监督学习和半监督学习、强化学习等。该书讲了监督学习，总共讲了这些学习模型：感知机、k近邻法、朴素贝叶斯法、决策树、逻辑斯谛回归、最大熵、支持向量机、EM算法、隐马尔科夫模型、条件随机场。我先把我们学习过的模型写成博客吧。但其实每个模型都有很多内容，以我一个初学者的水平估计也讲不了什么，我就按照我的理解讲，每个模型争取能实现一个例子，供大家参考。

今天第一篇，SVM（support vector machine, 支持向量机）。

Read More