Ubuntu下PDF编辑工具使用经验

最近需要帮别人校对文档,没有拿到原始latex文本,所以得在pdf上直接修改。在Windows系统中,adobe是有编辑功能的,可以在pdf上做很多备注和修改,但是ubuntu系统下只能尝试其他方法。

我搜到比较好的一个中文资料是:http://blog.chinaunix.net/uid-25789104-id-3968982.html ,但里面列举的7个常用pdf编辑器,并不都能很好地满足我自己的使用需求。

在实际使用中,我是结合Inkscape和Pdftk来完成pdf修改的!

Continue reading

Apply LDA to Generate User Interest Topics

We generate training dataset following these steps:
1) Select "UserID, Query" from 1 year image search logs and then reduce the items by UserID and merge all DISTINCT Query
2) Filter the dataset for heavy users
then we got ~1.5M users.

For model selection, we use LDA model, and set numtopics = 200, iteration = 200, then we can get 200 dimensional vectors for each users. Also, the model returns some keywords of each latent topics.
Continue reading

SVD++ Model in Recommender System

It's very interesting to share my recently reading of Koren's paper "Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model", which is well known for Netflix Prize.
Actually, my industry experience on Recommender System was APPs Recommendation for Android Chinese Market in Wandou Lab. Considered we have to handle 30M+ users and 300K+ Apps with a very cheap machine, only ItemCF & Content Based K-nearest neighbors algorithms are used in our model in the first beginning, later LDA and topic clustering methods are applied to improve some categories.
Continue reading

Stochastic Gradient Descent (SGD)- Singular Value Decomposition (SVD) Algorithms Notes

In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It has many useful applications in signal processing and statistics. Linear Algebra provides several numerical methods, such as Householder reduction, Golub–Reinsch SVD, High Relative Accuracy Bidiagonal SVD and etc., to solve SVD accurately. Details can be found in the paper of http://www.cs.utexas.edu/users/inderjit/public_papers/HLA_SVD.pdf .

In Machine Learning, SVD is widely used to do predictions. Thinking about KDD cup of Yahoo music recommendation, user-item rating matrix can be decomposed according to non-zero ratings and reconstructed to predict ratings in empty positions. From this angle, accurate SVD algorithms are no longer suitable because those methods treat empty positions as real zero ratings, which will lead bad prediction results.
Continue reading

湾区找工作小记

14年7月校招加入微软Bing,原打算满一年后找transfer到总部的机会,但进展不如预期顺利,加之Dora在加州工作并强烈不喜欢西雅图天气,所以15年初我就开始找湾区的工作了。

投出10多份简历,职位都是Software Engineer(有的公司也许title有所不同,但仍然是SE本质),地点大多在Google总部附近。我都是找人内推的,同事、朋友以及linkedin好友,仍然无法阻止接踵而至的拒信。值得一提的是,我很感兴趣Netflix公司,觉得自己的背景比较合适,于是找到比我大两届的师兄帮我投简历。在他们公司的career页面上,我看到最低title是sensior xxx,以为他们公司喜欢把title起得很高,最后发现...人家真的只是招senior,而我简直不能再junior~尽管师兄非常热心地为我推荐了好几个组,我还是被拒了。

简历阶段后,HR理我的只有Google,Facebook, Palantir, RocketFuel.
Continue reading

An Incremental Sampling Method

Sampling K points out of total N is trivial and we always use random number to determine sample current points or not.
However, during our daily work, the total points size increases day by day, then how to sample K points in an incremental way is a challenge. The following algorithm introduces a smart and efficient sampling method and proof is also given after it.

Incremental Sampling Method
- step 1: Add first k points to the select set \mathcal{S};
- step 2: For index N = k+1, \cdots, generate a random number r, if (r > \frac{k}{N}), continue; else replace one of points in \mathcal{S} with same possibility.

How to prove for any N > k, each point is selected with the possibility \frac{k}{N}:

The index starts from 1, these points can be divided into two parts due to the selected number k:
1. Index 1\le i \le k, the possibility to select the i-th point in the \mathcal{S} is
p_i = (1-\frac{k}{k+1}\cdot \frac{1}{k})\cdot(1-\frac{k}{k+2}\cdot \frac{1}{k})\cdots(1-\frac{k}{N}\cdot \frac{1}{k}) = \frac{k}{N}.

2. Index i > k, the possibility to select it as final points is
p_i = \frac{k}{i}\cdot(1-\frac{k}{i+1}\cdot\frac{1}{k})\cdots(1-\frac{k}{N}\cdot \frac{1}{k}) = \frac{k}{N} = \frac{k}{N}.

This method is of course can be used in 1-pass large-scale data loading and sampling.

Clustering Methods Review

Reference: Zhou Z H. Ensemble methods: foundations and algorithms[M]. CRC Press, 2012.

Clustering aims to find the inherent structure of the unlabeled data by grouping them into clusters of objects. A satisfactory clustering method should increase the intra-cluster similarity while decrease inter-cluster similarity meanwhile. Define the sample sets D = \{\bf{x_1}, \bf{x_2}, \cdots, \bf{x_m}\}, then the clusters can be defined as \{C_j | j = 1, \cdots, k\} with \cup_{j=1}^k C_j = D and C_i\cap_{i \neq j} C_j = \varnothing.
Continue reading

Logistic Regression - Mathematics Related

Reference: http://www.cnblogs.com/sparkwen/p/3441197.html

逻辑回归(Logistic Regression, LR)模型其实仅在线性回归的基础上,套用了一个逻辑函数。这主要是由于线性回归在整个实数域内敏感度一致,而分类范围,需要在[0,1]。逻辑回归就是一种减小预测范围,将预测值限定为[0,1]间的一种回归模型,其回归方程为:
h(z) = \frac{1}{1+e^{-z}}
与回归曲线如下图所示。逻辑曲线在z=0时,十分敏感,在z>>0或z<<0处,都不敏感,将预测值限定为(0,1).

\bf{x}=\{x_1, x_2, \cdots, x_n\}为样本数据,\bf{y}=\{y_1, y_2, \cdots, y_n\}为各个样本分类结果。那么对于二分类问题,我们可以构建逻辑回归模型如下。
首先,样本被分类为1的概率可以写作:
P\{y=1|x,\theta\} = \frac{1}{1+e^{-\theta^Tx}}
那么被分类为0的概率则可以写成:
P\{y=0|x,\theta\} = \frac{1}{1+e^{\theta^Tx}} = 1-P\{y=1|x,\theta\}

h_{\theta}(x) = \frac{1}{1+e^{-\theta^Tx}}, 则对于单个样本来说,它的后验概率是:
p(y|x,\theta) = h_{\theta}(x)^y(1-h_{\theta}(x))^{1-y},
其中y = 1 或者 0;

那么所有样本的似然函数是:
L(\theta|x,y) = \Pi_{i=1}^n h_{\theta}(x_i)^{y_i}(1-h_{\theta}(x_i))^{1-y_i}

为了极大化这个似然函数,我们可以极大化这个函数(因为每一项都小于1,所有log后是负数):
l(\theta) = -\text{log}L(\theta|x,y)

我们可以求l(\theta)关于\theta的偏导数,这就是它的负梯度方向。我们可以采用梯度下降法作迭代策略, 求解\theta^* = \text{arg}\max_{\theta}(l(\theta)).

\frac{\partial}{\partial\theta}(l(\theta)) = \sum_{i=1}^n y_i\text{log}h_{\theta}(x_i) + (1-y_i)\text{log}(1-h_{\theta}(x_i))
\qquad = \sum_i\bigg( \frac{y_i}{h_{\theta}(x_i)} - \frac{1-y_i}{1-h_{\theta}(x_i)}\bigg)\frac{\partial}{\partial\theta}(\frac{1}{1+e^{-\theta^Tx_i}})
\qquad = \sum_i\bigg( \frac{y_i}{h_{\theta}(x_i)} - \frac{1-y_i}{1-h_{\theta}(x_i)}\bigg)\frac{e^{-\theta^Tx_i}}{(1+e^{-\theta^Tx_i})^2}x_i
\qquad = \sum_i\bigg( \frac{y_i}{h_{\theta}(x_i)} - \frac{1-y_i}{1-h_{\theta}(x_i)}\bigg) h_{\theta}(x_i)(1-h_{\theta}(x_i))x_i
\qquad = \sum_i(y_i-h_{\theta}(x_i))x_i

所以,迭代可写成: \theta_j = \theta_j + \alpha \sum_i(y_i-h_{\theta}(x_i))x_{i}.

Quick Start of Gnuplot

Gnuplot 快速使用指南

在Linux下的开源软件中画图最好的应该是Gnuplot了,虽然octave下可以运行matlab的.m文件来画图,但是有些语法不兼容,而且出来的图很丑,scilab出的图亦然。其中scilab是带界面的,octave和gnuplot都是用命令行画图~

以下是一张由gnuplot画出来的图,在图之后我会给出画这张图的命令和数据。

Step 1: 数据准备
准备好四个文本文件,文件名分别为"speedup_1", "speedup_2","speedup_3","speedup_4", 他们的内容分别为:
speedup_1:
4 4
8 8.44
16 9.65
32 13.6
64 26.2
speedup_2:
4 4
8 5.909417545
16 7.055328586
32 7.102585194
64 7.373120673
(省略其他2个文件)

Step 2: vi Speedup.gnu, 在文本中写入内容:
plot "speedup_1" t "Mesh Refinement" with linespoint lw 2, "speedup_2" t "Modify Region Marks" with linespoint lw 2, "speedup_3" t "Overall" with linespoint lw 2, "speedup_4" t "Ideal" with lines ls 0
set xlabel "Number of Processors" font "Times-Roman,20"
set ylabel "Speed Up" font "Times-Roman,20"
set xrange [0:64]
set xtics 16
set yrange [0:64]
set ytics 16
#set size 0.65,0.65

set key box
set key left top

set terminal png
set out 'speedup.png'
#set terminal postscript eps
#set terminal postscript color
#set terminal postscript solid
#set output 'speedup.eps'
replot

Step 3: gnuplot Speedup.gnu
之后你可以在本地目录中得到speedup.png
如果把set terminal png 和下一句.png都用#注释掉,去掉set terminal postcript *这些语句前面的#,则可以得到speedup.eps, 这在Latex中插入图片的格式中更常见。

以下是对于Speedup.gnu更详细的解释:
plot "speedup_1" t "Mesh Refinement" with linespoint lw 2, "speedup_2" t "Modify Region Marks" with linespoint lw 2, "speedup_3" t "Overall" with linespoint lw 2, "speedup_4" t "Ideal" with lines ls 0
# 这一句是把数据文件读入并命名,linespoint表示点线方式,lines表示线方式,lw是线宽度, ls是线颜色,我发现取ls 6时是黄色实线,0是黑色虚线.

set xlabel "Number of Processors" font "Times-Roman,20"
set ylabel "Speed Up" font "Times-Roman,20"
# 设置x,y轴标签,font后的部分是字体

set xrange [0:64]
set xtics 16
set yrange [0:64]
set ytics 16
# 设置x,y轴坐标范围和刻度

set size 0.65,0.65
#设置图占默认值的大小,如果是png,把这句可以注释掉,如果是eps,这样加上更好,因为会使得字体相对变大

set key box
#legend加框
set key left top
#legend位置为左上, left bottom是左下

set terminal png
set out 'speedup.png'
#输出成png格式

#set terminal postscript eps
#set terminal postscript color
#set terminal postscript solid
#set output 'speedup.eps'
#以上是在linux下输出成eps格式,如果在windows下,将postscript去掉 (未测试,你可以试试)

replot
#画图

找工作总结

今天决定签哪家了,至此,找工作全部结束,所以把过程总结一下。

面过的公司包括:

1. 笔试之后无下文的:
有道 -- 内推也要笔试,估计笔得不怎么样,确实我基础题做得不行。
雅虎 -- 笔试时特别奇葩,我本来内推的是 research engineer职位,结果笔试时傻眼,大题完全没法编。果断把试卷右上角的职位改成SDE(软件开发工程师), 后来竟然接到面试通知了,可是后来面试日期要延后,我也不等了。

2. 等不起的:
hulu -- 因为听朋友说这家公司的bar比google高,所以我才考虑去试试的(看有多难)。经历一次电面,3次现场面,后来加了一面,最后终面。因为不是数据挖掘和机器学习背景,我想投研发被HR劝说可能不合适,然后我投的开发。据说开发是要做产品线上的东西,和做网站有关,具体做啥我也不太清楚。我是上周二面完的,由于这周三就要给微软答复,所以催了hulu尽快给结果。HR很nice,看起来还是挺认真负责的,但是很抱歉我每次满怀期待地接电话,得到的通知都是“还不能做出决定,要再等等”。今天仍然如此,我觉得这是soft reject,和HR说那就算了,我得签微软。听说很多人都被pending了,直接收到拒信的应该也有,那我就不是特别清楚了。待遇方面,听说是开发比research要低。基本没有户口。然后应该普通offer也没有给非常高,绝对不像梁斌在weibo里说的那么夸张。P.S. 特别牛的人也许可以拿到那个数。

google -- 10月份电面过1次,现场面了2次,因为现场面那天给我安排的是9:00第一场,9:45第二场,然后我那天手机出毛病,闹钟没 响,直接睡过,风风火火地赶上第二场。又在中午补上了第一面。遇到的都是google 美国的面试官,一个老外,一个中国人,一个考算法题,一个考设计题。我好像答得都不怎么样,程序写得也一般,聊得还可以(那有个什么用呢)。不过竟然还给我安排3,4面了,我还挺感动的,虽然前2面反馈不咋的吧。面试日期本来是上周,可是有突然状况,推迟了,我估计这两天就会发信过去说我已经决定签哪了,不去面了。说多了都是泪,因为J1 2-year rules,我只能申请国内职位。google北京这里一堆人排着,轮到我的机会渺茫,几乎是0吧。google的HR很nice,非常认真负责。

JP MORGAN -- 投的QUANT职位,就是凑个热闹,听说global pay,不过其实也没有那么吓人。10月份电面过一次,问了我常微题,C++面向对象的题,感觉就是有那么几个方向,你会什么他问什么。我觉得他们对于写程序的考察,侧重点和IT大牛公司不一样,貌似不会问算法题,某人的解释是,他们更希望你代码写得规范,而不是注重创造性。认识也有其他人电面了,都是还没有接到面试通知,估计是会等电面全部结束后集中onsite interview。我个人感觉那个面试官GG对我印象应该不错,不过就算过了电面,我应该也是说我不会去onsite interview了吧。

3. 有口头offer的
华为 -- 博士特招项目,8月底就面完了。就面了2次,也没问太技术的问题,就是聊了聊之前的一些经历和一些想法。怎么说呢,觉得华为给我留下的印象不错,感觉还是一个很不错的公司。面试官大概都是40左右的leader,态度都非常谦逊,他们说特别希望招到清华北大中科院的最优秀的学生,以前给不了这些人理想的待遇,现在他们博士特招项目的待遇和发展都非常优厚。(待遇确实很不错了,和本科硕士不是一个level。)给我分到的是做数据库方向,我对这个方向没有任何背景,也不太想做这个方向。重申一次,华为是个好公司,比起很多国内互联网公司的虚假繁荣,它毕竟是个认认真真干实事的公司,你有时觉得他做事口号喊得有点大,但是能够做到就是很强的。

阿里 -- 准确地说,是阿里妈妈搜索广告。我比较曲折,先是暑假和我BF去提前批,面了2轮后,面了ZWS大牛老师,终面评价不好,不过终面不挂人。(后来听说,终面过的人就有资格参加阿里星面试了。)然后就是发实习offer了,但是我实习有地方去了,所以就这样了。之后,校招的时候,我们又被当实习生转正,面了终面,当时也有HR在场,面试感觉还比较愉快。面完回家路上,被HR叫回去补了个交叉面,是阿里云的一个人面我的,我当时抽风了最后问他的问题让氛围好尴尬,好在他没往心里去。最后拿到A类口头offer,不过我对于package不是很满意,但是他们觉得这个价格不低了,而且要我看以后的薪资涨幅。我觉得他们说得很有道理,去阿里还是很有前途的,但是第一年package实在远低于我预期。

微软 -- 实习生转正,也拖到现在才有正式offer的眉目。实习的时候,是好朋友内推的,当时错过大规模招暑期实习生的时间,所以我和head count斗争了很久。期间我还找了Intel 工程院。最后在大家的共同努力以及STC老大的special approval下,才拿到那个来之不易的实习生名额。我实习期间真的算很拼了,因为想转正,并且知道今年STC招人少很多,而且大部分在苏州。后来我mentor力挺我,给了我很多鼓励和支持,真是太感激她了。好人有好报,前不久她终于升职了,而且连升了2级。实习生转正的面试我被安排在9月下旬2面,10月中旬三四面,给我三,四面的都是principle manager。都是面算法题,程序题以及问项目,没有谈人生和理想。四面的时候,我遇到的面试官很tough,感觉不是很友好,一开始还不是很适应,不过脸皮厚的人总是能够战胜自尊,最后我们聊得还可以。反正当时我面完后我和我mentor都觉得我可能完蛋了,我还难过了几天,结果发现竟然还面试通过了。我突然开始觉得第四面面试官好有爱啊,在他严冬的外表下有颗盛夏的心(我太恶心了有木有)。微软给博士入职的level比硕士要多一级,package符合我预期,IT公司里面应该只比google的博士起薪少那么一点点吧,我还比较满意。

4. 没有面试但要感谢的公司
豌豆荚 -- 我2012年去实习的公司,如今规模是我去时的3-4倍。一家非常有爱,有品味的公司,所有显摆自己公司零食,午餐,甜点的公司,我还没有见过一个比得上这家的,甚至我认为都超过google的奢侈程度了。我今年找实习和工作没有那么顺的时候,他们是我最坚强的后盾,我很爱我的小伙伴们,一直想的就是如果微软没有转正的话,我最有可能就是回豌豆荚。(不是因为觉得微软比豌豆荚好,而是别的原因,也就不啥都说那么清楚了)

渣打 -- 我和BF还有来神之前参加过一个渣打的比赛,成绩还不错,然后就接到他们一个senior manager的电话,意思是让我考虑一下他们的职位。好吧,其实我写渣打不是很合适,应该是渣打科营,实在拎不清他们的组织结构。无论他有些关于行业的观点我是否同意,我都还是很感谢他能在周末抽出自己宝贵的休息时间给我电话和我聊聊。但是我比较想在北京,不想去天津塘沽,所以没有考虑那里。

最后,还要加上个内推后无下文的:网易游戏数据挖掘研究员,真是一点消息都木有啊,不过听说研发都给信了,估计今年是我投这个方向提前招到合适的人了。

说了那么多,其实仔细想想,面了也没几家公司。找工作是特别辛苦的过程,希望现在还没有拿到offer的XDJM们继续加油,会有大offer在后面等着你们。

Dora总是在鼓励我,有时候特别不喜欢听他说我这没问题,那也行,因为做不成的时候感觉更难受。之后也许还有四处求职的日子,这种不安定感总是时刻伴随着自己,有时候想着如果在一个稳当的环境下搞科研或者教书挺好的,但真那样又会受不了。作为一个矛盾综合体,也只能走一步看一步了,未来完全out of control.