围棋之神隐退江湖

随着 AlphaGo 大胜柯洁,我想围棋这个曾经被认为是 AI 短板的智力游戏已经不再成为一个问题。不过似乎从哲学上来看,这个问题远远没有被解决。通常的棋类博弈都可以看成一个 graph 上的搜索问题,棋盘的状态对应图的顶点,而棋手选择的 move 作为连接两个顶点的边。对于象棋之类的,合法的移动较少(每个类型的子都会有不同的约束),棋盘也比较小,在往常博弈的过程中简单的评价方式已经比较准确的反应了每种子的重要程度,因此可以比较容易根据己方对方剩余棋子的价值来评估每一个 move 之后的损失或者收益。而常见的搜索方法也就是在图上进行“有限”深度的遍历,寻求一条“理性”博弈后己方收益最大的路径。

这种人类理性思维的延拓以及程序实现成为了早期 AI 的基本原理。但是很显然面对围棋这种棋子无差异,棋盘巨大,最终也并不是按照某颗子是否存活断定输赢的游戏,它导致了两个传统算法的核心问题:

  • 搜索空间过于巨大,如果不进行有效的剪枝,是不可能在有限的比赛时间里完成有意义的搜索工作的
  • 评估本身的困难,如果看职业棋手的评估,往往也只出现在某些局部逐步的明朗后,根据规则计数才成为可能,而对于早期的评估基本上没有太大的意义

本质上 AlphaGo 的成功也正是寻找到了对于这两个问题的解决方案。然而实际上这种方案的出现仍然植根于职业棋手的思维方式。与一般的棋类活动不同的是,围棋选手通常用比较“虚”的东西来描述棋局的优劣,这些东西往往来自他们过去的经验,有的可以定量化,更多的似乎是“直觉”。AlphaGo 比较有意思的做法大概也就在于使用 deep learning 这套“玄学”来复制人类的“玄学”吧。

比较有意思的大概是人类棋手对于 AlphaGo 的认知。他们经常会用情感色彩的东西来描述这个高深莫测的对手,从“棋力”的角度来看,人类在短短几小时里能够推演出来的 variations 与计算机相比还是少了太多太多,因此输棋几乎已经是必然。人类的唯一希望只是在于对于“价值”的评估上,李世石唯一赢得的那局也是因为这个;但是现在的 AlphaGo 通过自我博弈探索自己的弱点修正了“评估”上的“瑕疵”(或者还有别的瑕疵,这大概也是 DeepMind 为何年初 60 大胜之后还要再来寻找柯洁比试一次)。其实如果说 DeepMind 真希望做一次更为合理的比试的话,应该给棋手看到 AlphaGo 的评估网络的输出,这才是人类真正能够发挥自己优势的地方。至于那 50 局的棋谱怕是杯水车薪反而误导职业选手了吧。

最后说一点关于围棋本身的哲学。评判输赢在于最终占有目数多少却不在于多多少目,这与 SVM 当年给人的感觉何曾相似,与常见的最大似然不同,要的仅仅是两类的 margin。目标函数的选择往往是哲学上的区别,而哲学的区别表现为行为方式的不同,造成理解上的隔阂。不少人抱怨 AlphaGo 在收官的阶段通常下一些不那么犀利的行棋方式,特别 pair match 时落后一方古力配对的 AlphaGo 甚至被认为在自杀,其实理解了哲学上的区别就很容易理解。收官阶段很多棋尽管仍然有一定的活动空间,但是前期的差距基本已经定型,如果 AlphaGo 已经计算出来无论怎么折腾它有应对的策略,即便损失一定的优势,但是避免了更加激进策略下可能翻盘的可能性,那么选择更为稳妥的落子当然是不违背本身的哲学的;在已经知道必输无疑的情况下,避免使用激进的策略无非也是出于同一哲学思想。

人在与人的博弈策略的转换是一个额外的因素。不是每一个人在针对不同对手的时候都会使用相同的策略的。哲学决定了目标函数,策略只是实现哲学的手段。人类能够透过策略看到哲学,进而把握对方根基上的弱点而调整自己的哲学与其相抗衡。对于简单的棋局,也许只有唯一合适的哲学。有没有一个问题本身是不存在最优哲学而要求参与者必须转换自己的策略来增强自己的胜算的呢?石头剪刀布?还是说任何问题都一定存在一个最优的目标函数,只是我们无法 formulate 出来。

围棋之神隐退江湖

TensorFlow 学习(2)

准备工作

决定玩玩 docker 版本的,工作环境为 Mac

  • 安装 VirtualBox 最新版本,docker 在 Mac 上不能直接使用(依赖 Linux kernel 的 cgroup 等特性)
  • 安装 docker toolbox,这是一些在 Mac 下使用 docker 的工具,装好后会自动配置一个叫 default 的虚拟机,这个虚拟机可以用 docker-machine 命令来操纵,这个虚拟机已经配置好了 ssh,因此可以直接 ssh 到虚拟机上想干嘛干嘛
  • 在 docker quickstart terminal 里面,PATH 已经设置好了,可以直接用 docker 等命令,更多可以参考这里
  • 安装 docker 镜像,docker run -it b.gcr.io/tensorflow/tensorflow
  • 测试 TF,参看这里

运行 code 如下

$ docker run -it b.gcr.io/tensorflow/tensorflow
Unable to find image 'b.gcr.io/tensorflow/tensorflow:latest' locally
latest: Pulling from tensorflow/tensorflow

0bf056161913: Pull complete
1796d1c62d0c: Pull complete
e24428725dd6: Pull complete
89d5d8e8bafb: Pull complete
91dc2e300ec6: Pull complete
f2b205f23258: Pull complete
33c0372bafe3: Pull complete
e58fef39e1c1: Pull complete
20bc72598f11: Pull complete
d1627c65b6cf: Pull complete
f44441b29ccc: Pull complete
2b13eefb13c7: Pull complete
151aba0ce7fe: Pull complete
4ea38d2f04f0: Pull complete
74cd363304ab: Pull complete
4ac133eed955: Pull complete
Digest: sha256:bed079b6881a45cd548c319991ef79dbc17b2ec1f6d5295ca4fd5c45b180ef5a
Status: Downloaded newer image for b.gcr.io/tensorflow/tensorflow:latest
root@55f407ea0937:~# python
Python 2.7.6 (default, Jun 22 2015, 17:58:13)
[GCC 4.8.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import tensorflow as tf
>>> hello = tf.constant('Hello, TensorFlow!')
>>> sess = tf.Session()
I tensorflow/core/common_runtime/local_device.cc:40] Local device intra op parallelism threads: 1
I tensorflow/core/common_runtime/direct_session.cc:58] Direct session inter op parallelism threads: 1
>>> print(sess.run(hello))
Hello, TensorFlow!
>>> a = tf.constant(10)
>>> b = tf.constant(32)
>>> print(sess.run(a + b))
42
>>>

Hello World

我们来试试个简单的 TF 程序,参看 mnist 的例子:

from tensorflow.examples.tutorials.mnist import input_data
import tensorflow as tf

if __name__ == '__main__':
  mnist = input_data.read_data_sets("MNIST_data/", one_hot=True)
  x = tf.placeholder(tf.float32, [None, 784])
  W = tf.Variable(tf.zeros([784, 10]))
  b = tf.Variable(tf.zeros([10]))
  y = tf.nn.softmax(tf.matmul(x, W) + b)
  y_ = tf.placeholder(tf.float32, [None, 10])
  cross_entropy = -tf.reduce_sum(y_*tf.log(y))
  train_step = tf.train.GradientDescentOptimizer(0.01).minimize(cross_entropy)
  init = tf.initialize_all_variables()
  sess = tf.Session()
  sess.run(init)
  for i in range(1000):
    batch_xs, batch_ys = mnist.train.next_batch(100)
    sess.run(train_step, feed_dict={x: batch_xs, y_: batch_ys})
  correct_prediction = tf.equal(tf.argmax(y,1), tf.argmax(y_,1))
  accuracy = tf.reduce_mean(tf.cast(correct_prediction, "float"))
  print(sess.run(accuracy, feed_dict={x: mnist.test.images, y_: mnist.test.labels}))

执行之后

$ python mnist.py
Successfully downloaded train-images-idx3-ubyte.gz 9912422 bytes.
Extracting MNIST_data/train-images-idx3-ubyte.gz
Successfully downloaded train-labels-idx1-ubyte.gz 28881 bytes.
Extracting MNIST_data/train-labels-idx1-ubyte.gz
Successfully downloaded t10k-images-idx3-ubyte.gz 1648877 bytes.
Extracting MNIST_data/t10k-images-idx3-ubyte.gz
Successfully downloaded t10k-labels-idx1-ubyte.gz 4542 bytes.
Extracting MNIST_data/t10k-labels-idx1-ubyte.gz
I tensorflow/core/common_runtime/local_device.cc:40] Local device intra op parallelism threads: 1
I tensorflow/core/common_runtime/direct_session.cc:58] Direct session inter op parallelism threads: 1
0.917

看起来就这么简单。我们来想个复杂的问题试试?首先我们要理解这段程序

  • 数据用 placeholder 表示,这样 training 和 inference 阶段可以向里面填
  • 优化变量使用 variable 表示,这样 TF 在 training 的时候会使用自动求出来的导数来更新它们
  • 表达出来目标函数(cross_entropy)后我们需要通过一个 solver 来求解,那个 train_step 就是迭代的其中的一步
  • session 通过 run 方法执行一次 computation graph,这是 train_step 表示的一个更新优化变量的图
  • 后面计算 accuracy 也直接使用 TF 自己计算,然后把 test data 代入获得结果

是不是有点心动想找个实际问题来试试看了呢?

——————
And it came to pass at the end of two full years, that Pharaoh dreamed:and, behold, he stood by the river

TensorFlow 学习(2)

TensorFlow 学习(1)

Google 终于在今天开源了 TensorFlow (TF)这个号称终极 ML 神器,Jeff Dean 背书的 infra structure 怕是又会一场腥风血雨,与 Spark 系少不了一场争执。好在开源之后也可以开始公开一些这方面的体验。当然大公司的开源都是心中有鬼的,需要在各自营地耕耘的兄弟自己掂量一下 🙂

粗粗看了一下 TF 的代码,先来点准备工作。

protobuf v3

大部分公司里面的 project 还是 v2 用的比较多,之前的 blog 也有所讨论,下面是一些 v3 与 v2 的主要区别:

  • 不再有 required/optional 的区别,默认就是 optional,当然 repeated 还是要保留;据说去掉 required 是为了避免 optional 到 required 的 migration 这种情况下出现的问题
  • 通过 reserved 可以保留一些 field 的编号或者名字,这对 deprecation、提前 book 一些东西是有帮助的
  • 使用 Any 而不再使用 extension
  • 支持 JSON 的 mapping

之前讨论过 polymorphism 和 extension 的关系,通过 Any 这里不再需要 extension 那种比较诡异的用法了。proto2 里面引入的 oneof 和 map 仍然可以用。当然同时还发现 google 还开源了 gRPC,有空也要看看。

基本概念

TF 里面基本的概念其实和学习编译器原理的 parser 类似:

  • 每个节点表示或者是某种计算操作(如加法、乘法)或者某种数据获得的过程(如 IO 或者一些 utility function 用来直接生成 tensor)
  • 每条边表示节点之间的计算因果关系

这样一来计算的过程可以用所谓的 data flow graph 表达出来(是不是觉得和 parser 生成的 AST 一个意思呢?),这样一来一些 ML 的模型(loss function)就可以用 TF 表达出来,而 TF 本身并不提供诸如神经网络的实现,在 TF 之上我们可以提供这些不同模型的抽象,而他们的计算模型就被 TF 封装了起来,TF 提供了 auto-differentiation 能力,因此一旦 loss function 被描述了出来,TF 就能使用一些通用的 solver 如 SGD 完成优化。同时 TF 实现了不同 CPU/GPU 构架下的基本操作,这样高层的抽象可以在不同的物理平台上执行。

TF 提供了 python 和 C++ 的 API,说实在的这本质上就是提供了一类设计的很差的 DSL,从某种意义上来看,不明白为什么不干脆实现另外一种语言(跟 Matlab 类似),然后使用编译器的技术将执行计算的程序根据不同的目标编译出来,这样语言的 extension 就可以解决扩展性了吧。

下面我们看一些具体的例子。

——————
Yet did not the chief butler remember Joseph, but forgat him

TensorFlow 学习(1)