记录一下在amazon北京的时光

今天跟经理打了电话,终于还是放弃了amazon北京的offer。amazon是个有很牛技术的低调的公司。

记录一下在amazon的时光吧。

28F的茶水间和不远处的大裤衩:



» Continue reading 记录一下在amazon北京的时光

Theano tutorial: Theano Graphs Structures

上一篇将了一个实际的例子:Logistic Regression。这一篇讲了Theano中最基本的graph的概念。

在theano中编程的第一步是要将各种数学关系和公式使用符号占位符(symbolic placeholders)来表示,所谓的符号占位符其实就是我们平时说的变量(variables)。然后我们再使用一些操作符(operations)来表示各个变量之间的运算(例如+, -, **, sum(), tanh()等等)。就像大多数编程语言中的定义函数(function definition)。在theano中编程你需要先熟悉这种概念。

graph structure

然后再来说一下theano中重要的graph概念。在上面我们已经讨论了variables和ops。其实一个graph structure就是有三部分组成:变量节点(variable nodes),操作节点(op nodes)和应用节点(apply nodes,姑且叫做应用节点吧,把某种计算操作应用于某些变量)。

下面来看一个具体的例子:

import theano.tensor as T
x = T.matrix('x')
y = T.matrix('y')
z = x + y


» Continue reading Theano tutorial: Theano Graphs Structures

Theano tutorial: A Real Example - Logistic Regression

先看代码:

import numpy
import theano
import theano.tensor as T
rng = numpy.random

N = 400
feats = 784
D = (rng.randn(N, feats), rng.randint(size=N,low=0, high=2))
training_steps = 10000

# Declare Theano symbolic variables
x = T.matrix("x")
y = T.vector("y")
w = theano.shared(rng.randn(feats), name="w")
b = theano.shared(0., name="b")
print "Initial model:"
print w.get_value(), b.get_value()

# Construct Theano expression graph
p_1 = 1 / (1 + T.exp(-T.dot(x, w) - b))   # Probability that target = 1
prediction = p_1 > 0.5                    # The prediction thresholded
xent = -y * T.log(p_1) - (1-y) * T.log(1-p_1) # Cross-entropy loss function
cost = xent.mean() + 0.01 * (w ** 2).sum()# The cost to minimize
gw,gb = T.grad(cost, [w, b])              # Compute the gradient of the cost
                                          # (we shall return to this in a
                                          # following section of this tutorial)

# Compile
train = theano.function(
          inputs=[x,y],
          outputs=[prediction, xent],
          updates=((w, w - 0.1 * gw), (b, b - 0.1 * gb)))
predict = theano.function(inputs=[x], outputs=prediction)

# Train
for i in range(training_steps):
    pred, err = train(D[0], D[1])

print "Final model:"
print w.get_value(), b.get_value()
print "target values for D:", D[1]
print "prediction on D:", predict(D[0])


» Continue reading Theano tutorial: A Real Example - Logistic Regression

Sparse Matrix

In this exercise you will practice basic C++ class construction, and memory allocation and deallocation. You are asked to implement a class that supports an extendable variant of a sparse matrix. A matrix is a two-dimensional array. A matrix is sparse when many positions in the array are not important. In usual sparse matrices entries are not important when they are 0. In our version of the saprse matrix we distinguish between existing positions and not existing positions. Existing positions in our sparse matrices could contain the entry 0. In both cases, allocating memory to the unimportant positions in the matrix is a waste of memory.

You could think about a database containing students and their grades in modules. Every row in the database corresponds to a student and every column corresponds to a module. Then, grades are to be stored only in modules that the student did take. The entry that corresponds to a module that the student did not take should not exist. In particular, 0 is a possible grade in a module that a student takes.
To summarize, you are going to implement a sparse matrix that stores integers (including 0) in some of the positions of a (relatively large) two-dimensional array.

Technically, I have created the header file for the sparse matrix. You have to complete it with additional members. You will have to submit two files: Sparse.cpp and Sparse.hpp. You will probably want to create your own main.cpp file that includes a program that actually executes your Sparse.cpp. You will not be submitting this file. I also supply a Makefile that you should (must) use for compilation. The Makefile includes a compilation of a main.cpp. The header file includes detailed descriptions of the functions that are required that you implement.

» Continue reading Sparse Matrix

区间合并

有这样一个题目:输入两组区间,输出者两组区间合并之后的区间。

假设区间的起点和终点都是由整数表示,输入的是两个数组,数组中存储的是每个区间的起点和终点:

[8, 12, 15, 17, 21, 27, 32, 34, 35, 36, 40, 60]
[0, 10, 18, 19, 23, 30, 31, 38, 43, 44]

输出为合并之后的一组区间

[0, 12, 15, 17, 18, 19, 21, 30, 31, 38, 40, 60]


» Continue reading 区间合并

蓄水池抽样

1. 在高德纳的TAoCP中有一个问题:

可否在一未知大小的集合中,随机取出一元素?不知道集合的大小,比如说你只能一个元素一个元素地读,但是不知道什么时候会终止。
例如在一很大,但未知确实行数的文字档中抽取任意一行。如果要确保每一行抽取的机率相等,即是说如果最后发现文字档共有N行,则每一行被抽取的机率均为1/N。

给出的解答为:

i = 1
while more input lines
    with probability 1.0 / i++
        choice = this input line
print choice

对于第i个输入,以1 / i的概率将当前的选择换成地i个输入(假设输入的编号从1开始)。

或者上面的算法也可以描述为:

将第1个输入直接放到choice中
对于第i个输入(i > 1):
   随机产生一个范围从1到i的整数r;
   如果r == 1,令choice = 第i个输入

如何证明这个方法是正确的,也就是每个元素被选到的概率都相等且都为1 / N:
对于第i个元素(元素的下标从1开始),以1 / i 的概率成为choice。假设最终才知道一共有N个元素,那么在这N个元素都出现之后,对于任一个元素(比如第x个元素)最终被选中的概率:

p(choice = x) = \frac{1}{x}\times\frac{x}{x+1}\times\frac{x+1}{x+2}\times\dots\times\frac{N-1}{N} = \frac{1}{N}


» Continue reading 蓄水池抽样

第 1 页,共 9 页12345...最旧 »