时光真是转瞬即逝，五月了，即将找工作，亚历山大呀。
书单里那么多书，C++ primer和effective c++算是大部分看了一遍（模板定义、内存分配平时是在用得太少，看了忘得好快，哎）。剩下的还有好多，在这写个计划吧。
五月：算法导论 + STL源码剖析看一部分吧
六月：编程之美 + 编程珠玑
七月：网上资料 + 设计模式看一部分吧
八月：网上资料 + 复习
加油！
五月的天，梦开始要鲜艳，前方蜿蜒，一长串的心愿~
最近在看stanford的machine learning课程，觉得非常适合我这种初学者，讲得很清楚。打算在博客里写下学习的收获。
1.一元线性回归
回归就是根据空间中已经存在的点的信息，拟合一个方程（可以是直线、曲线、面等等），重而来进行预测。
首先来看看一元线性回归。一元代表只有一个变量，即方程中的x，我们需要拟合一条直线
，根据训练数据，求出θ值，使得平方误差函数最小。
因此，我们的工作就是：
（拟合的预测函数）
（使得平方误差函数最小）
其中，我们有m条训练数据。
2.计算
现在我们的问题就是如何求得θ值了。这里介绍梯度下降法(gradient descent)。
repeate until convergence{
//其中，α后面的部分代表了这一轮的梯度。
}
其中J代表了1中的平法误差函数，α代表learning rate。对于一元线性回归，平方误差函数是一个二次方程，二次方程肯定存在一个全局最优解。关于θ的求解如下图所示：
（图片来自Andrew Ng老师的课件）
注意：如果α过小，会使得收敛得速度非常慢，如果α过大，可能又导致最后数据无法收敛。在实际的计算过程中，我们可以选择α的值0.001、0.003、0.01、0.03、0.1，先选择一个较小的α，观察两轮迭代之间的J是否有减小，如果两轮迭代之间的J增大了，则表明α过大，可以选择更小的α进行计算，如果两轮迭代之间的J变小速度非常慢，则可以选择大一点的α，使得收敛的速度可以加快。
（图片来自Andrew Ng老师的课件）
上图便是learning rate较小的情况。
（图片来自Andrew Ng老师的课件）
上图便是learning rate较大的情况，无法converge。
3.总结
ok，到此，我们已经知道一元线性回归如何求解了，总而言之，就是首先假设一条直线，然后通过训练数据求得最优的θ值，使得J（θ）最小。
最终拟合出来的直线大约如下图所示：
（图片来自Andrew Ng老师的课件）
得到拟合直线后，如果要预测size = 1250，通过该直线，得到price = 250。~~~
5.参考资料
http://www.ml-class.org （Linear regression with one variable）
http://s3.amazonaws.com/mlclass-resources/docs/slides/Lecture2.pdf
Linux 32位
sizeof(char)=1
sizeof(short)=2
sizeof(int)=4
sizeof(long)=4
sizeof(long long)=8
sizeof(float)=4
sizeof(double)=8
sizeof(long double)=12
Linux 64位
sizeof(char)=1
sizeof(short)=2
sizeof(int)=4
sizeof(long)=8
sizeof(long long)=8
sizeof(float)=4
sizeof(double)=8
sizeof(long double)=16
1.Introduction
在向量模型中，将查询和文档均表示成同一空间下的向量，可以使用余弦相似度进行评分计算。但是，向量空间表示方法没有能力处理自然语言理解中的两个经典问题：一词多义（polysemy）和一义多词（synonymy）。使用LSI可以利用词项的共现情况，将词和文档映射到潜在语义空间，从而去除了原始向量空间中的一些“噪音”，提高了信息检索的精确度。
2.SVD分解
文档集可以转换成词项-文档矩阵，每一行代表一个词项，每一列代表一个文档，矩阵元素(t,d)代表词项t在文档d中出现的次数。将词项-文档矩阵进行SVD分解，可以得到：
其中，r是WW^T的秩，Σ是W矩阵的奇异值（按降序排列），T的每一列都是WW^T的正交特征向量，D的每一列都是W^TW的正交特征向量，W^T代表W的转置。
接着，我们将低秩逼近应用到词项-文档矩阵的逼近问题上来。对于Σ，把对角线上r-k个最小奇异值置为0，从而得到Σ’，从新计算W’可以作为W的逼近。
3.LSI在检索应用
从原始的词项-文档矩阵W, 我们计算得到它的近似W’。在W’ 中，依然是每行对应一个词项，每列对应一个文档，区别是文档在新的空间，它的维度 k << r。
比较两个词项：
比较两个文档：
LSI检索：
对于新的查询或者文档，可以将之映射到LSI的空间中。对于q，映射到LSI空间后表示为q’，（q为列向量）：
(注：由于T是正交归一化矩阵，因此T^-1 = T^T)
得到LSI空间中的q’后，则可以通过计算D及q’的cosine值得到查询与每个文档的距离。
4.总结
使用SVD分解以及低秩逼近，可以通过文档的上下文信息来部分解决一义多词的问题。如果减低k值，召回率将提高，当d取几百之内的数目时，某些查询的正确率实际上也会得到提高。但LSI仍然延续了向量空间检索的两个缺点：无法表示否定查询及无法完成布尔条件查询，并且LSI的计算开销很大。
5.参考文献
Indexing by Latent Semantic Analysis
原创文章，转载请注明：Shall的博客
本文链接：http://www.ifshall.com/2011/10/26/隐性语义索引lsi学习笔记/
在MapReduce框架下计算PageRank（上）中已经简单介绍了PageRank的计算方法，为了使PageRank计算满足现实需求，本文继续讨论。
1、状态转移矩阵计算
在冲浪模型中，PageRank要考虑直接随机选中的概率以及顺着链接浏览的概率。
首先看看如何计算状态转移矩阵：
（1）根据网页的链接关系可以得到Web图的邻接矩阵。（Shall：很简答的~如果page1链接page2则临界矩阵中的p12=1）
（2）对邻接矩阵的每一行进行归一化。
（3）上面处理后的结果矩阵乘以d。
（4）对上面得到的矩阵中的每个元素都加上（1-d）/N
说了这么多，看一个例子吧~
如果有3个网页，链接关系式1->2,3->2,2->1,2->3，假设d是0.5~
到第（2）步结束的时候（介个时候相当于不带随机跳转），得到的矩阵是：
最后得到的矩阵（带随机跳转）：
2.PageRank计算
上面的公式中，π是最终冲浪者在网页间的概率分布，它是一个稳态概率分布。π则是我们要计算的所有网页的PageRank值。
现在计算PageRank的问题被转化成了一个计算左特征向量的问题。
解这个问题最简单的方法便是幂迭代法。
仍然是上面的例子，假设冲浪者的初始状态概率分布向量是x0（1,0,0），于是一步之后的概率是：x1 = x0•p=（1/6,2/3,1/6）。迭代下去，最后得到稳态的概率：（5/18,4/9,5/18）。
3、MapReduce框架下PageRank计算
在MapReduce框架下可以通过一次MapReduce得到状态转移矩阵P，并选择一个初始状态π。
在迭代计算PageRank时，每个map都载入上一轮的计算结果π，以及状态转移矩阵P中的一列。每个map会计算得到新一轮的π中的一列。在Reduce阶段，合并所有map结果得到新一轮的π的计算结果。
每一轮的π计算结果可以放在固定的位置，当两轮计算结果只差小于某个阈值，则可以认为π已经达到稳定值，得到最终的PageRank值。
这个方法里MapReduce中都只是进行了简单的迭代，在shufle阶段每个Map只将π中的一维（也就是一个数）传递给了Reduce，网络传输量小、计算简单，优于上一篇文章中的方法。
4、增量计算
PageRank的增量计算仍然需要所有的网页参与迭代计算。这种情况下对于已经存在的网页可以将之前计算得到的PageRank值作为初始值，而新采集的网页PageRank值设置为0，开始迭代计算。这样，迭代较少的轮数便能得到稳定的PR值。
5、参考资料
《信息检索导论》 （美）曼宁，（美）拉哈万，（德）舒策 著 王斌 译
原创文章，转载请注明：Shall的博客
本文链接：http://www.ifshall.com/2011/09/05/mapreduce框架下计算pagerank（下）
1、PageRank介绍
PageRank是一种由搜索引擎根据网页之间相互的超链接计算的技术，而作为网页排名的要素之一，PageRank是网页的一个静态属性。一个页面的“得票数”由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。
2、PageRank计算
一个网页的PageRank等于所有指向它的网页的PageRank的分量之和，计算公式如下图所示，其中C为归一化参数。
看一个灰常简单的例子：
R(A)=R(C)
R(B)=0.5R(A)
R(C)=R(B)+0.5R(A)
R(A)+R(B)+R(C)=1
解上述方程得：
R(A)=R(C)=0.4
R(B)=0.2
在实际的PageRank计算中，采用的是随机冲浪模型，即到达u的概率由两部分组成：一部分是直接随机选中的概率(1-d)或(1-d)/N，d通常取0.85，另一部分是从指向它的网页顺着链接浏览的概率，则PageRank的计算方法如下图所示：
通常网页总量大，不会通过解析方程来计算PageRank的值，通常是通过迭代的方式来求得PageRank的收敛值。
3、MapReduce框架下迭代计算PageRank（上）
根据上面介绍的方法，可以得到MapReduce框架下计算PageRank的方法：
在Map阶段，根据每个网页的outlink数以及该网页的PageRank值可以得到该网页对其每个链接到的网页的PageRank付出的“票数”。
在Reduce阶段，使用随机冲浪模型的公式统计每个网页得到的总“票数”，便得到新一轮每个网页的PageRank值。
迭代以上的MapReduce，最终将得到稳定的PageRank值。
4.小结
以上便是最naive的方法。但是这种方法存在着很大的缺陷，每当有新的网页加入时，就需要对所有的网页进行重新的迭代。对于搜索引擎来说，网页的数据量及增长量都是非常大的，这种方法不可取。之后将介绍改进的方法。
5、参考资料
http://en.wikipedia.org/wiki/PageRank
中国科学院现代信息检索课程2009版第11章课件（By王斌老师）
原创文章，转载请注明：Shall的博客
本文链接：http://www.ifshall.com/2011/09/04/mapreduce框架下计算pagerank（上）
大家好，我是韩小猴，来自中科院计算所网络数据中心，方向是大规模数据处理、信息检索，欢迎大家与我交流。业余时间喜欢音乐、游泳、tbbt以及各种宫斗剧（囧）。
Email : ifshall.han#gmail.com
本文主要是测试了Hive中行存储和列存储(RCFile)之间的优劣。
1.TPCH
可以在http://www.tpc.org/tpch/ 获得源码，我下载的版本是2.14.0。
下载源码后，根据自己的系统修改makefile文件，比如我修改成如下形式：
CC =gcc
DATABASE= DB2
MACHINE = LINUX
WORKLOAD = TPCH
TPCH默认生成的数据格式是col1|col2|col3|，然而有的数据库的输入格式是col1|col2|col3，想要得到该种数据格式，修改tpch的源码dss.h文件：
/*#define PR_END(fp) fprintf(fp, ”\n”)*/ /* finish the record here */
#define PR_END(fp) {fseek(fp,-1,SEEK_CUR); fprintf(fp,”\n”);}
然后make，则可以得到dbgen的可执行程序了。
使用./dbgen -h可以看到命令行的帮助信息。
2. HIVE
接下来说一下HIVE的配置。由于我想比较Hive中行存储数据及列存储数据的优劣，同时希望行列数据都是使用ZLIB压缩后的，因此需要修改一下Hadoop和Hive的配置。
Hadoop中需要修改的配置文件是mapred-site.xml：
同时Hive中也需要修改：
OK，配置好了，重启Hadoop，进入Hive，正式测试。
3.测试
加载100G TPC-H数据集的磁盘空间测试：
用于测试的SQL:
RCFile的查询比行式存储查询快的原因主要是在Map阶段，由于每个Map读入的数据量更小，IO开销小，因此能在更短的时间内完成Map。
使用Bzip2的压缩方式，压缩率较高，但是解压过程较慢，因此还是选用gzip较好。
4.总结
根据以上测试可见，RCFile的优势还是很大的，它在不降低查询性能的前提下比开源数据仓库系统（Hive）中的行存储技术节省磁盘存储空间。