Brains


Algorithm、Machine Learning、Search、cloud computing
on Docker, Dockerfile

Dockerfile简介

Dockerfile类似于Linux中的Makefile,Docker用它来快速便捷的创建一个镜像。本文介绍一下Dockerfile的编写规则,以及一些常见的Dockerfile样例。 Dockerfile的基本结构 Dockerfile指令是不区分大小写的,为了便于区分建议使用大写,它使用'#'作为注释。Dockerfile由一条条指令构成的,一般来说它由基础镜像信息、维护者信息、镜像操作指令和容器启动指令(可选)构成的。例如: # FROM说明此镜像是来源于centos这个基础镜像的 FROM centos # MAINTAINER指明了这个镜像的维护者的信息 MAINTAINER liuchang liuchang31@baidu.com # RUN代表要在该基础镜像centos上添加一些操作 RUN mkdir -p /time_server/log/ && mkdir -p /time_server/bin/ # COPY 表明要把主机当前目录下的文件复制一份到镜像的/time_server/bin/目录中 COPY . /time_server/bin/ # WORKDIR 指明当前镜像的工作目录 WORKDIR
Read More
on NLP, LDA主题模型的实现及思考

LDA 的实现

参考LDA数学八卦和GibbsLDA++实现的LDA模型,以及自己对这个模型的理解 LDA的Gibbs抽样 在上一篇文章中提到了Gibbs抽样的推导最终结果,根据这个推导公式可以在计算机上模拟文档集的生成过程。Gibbs抽样的推导结果如下: 实现思路: 1:先随机为每个单词赋予一个主题 2:根据抽样公式计算当前单词生成每个主题的概率 3:利用掷骰子算法生成下一个主题 4:一直迭代下去,最后计算文档——主题、主题——单词的概率分布 代码放在了Github - LDA上了 数据结构的设计 根据抽样公式公式可知,需要保存的东西有 1:每个主题对应单词的个数 2:每个单词对应某个主题的单词个数 3:每篇文章单词的个数 4:每篇文章的每个主题对应的单词总数 用Python定义的数据结构如下: # 单词到ID的映射表 self.word_map = {} # ID到单词的映射 self.id2word = [] # 保存每篇文章的词数 self.doc_word_num = [] # 保存每篇文章 self.doc
Read More
on NLP, LDA主题模型的理解

Latent Dirichlet Allocation

LDA在机器学习领域是一个应用很广泛的主题模型,这几天一直在学习这个模型,现在很勉强的对这个模型有了整体的把握,并且用Python简要的实现了一下,打算把自己对LDA的理解暂且记录一下,以后继续完善~ 主题模型 LDA是一个主题模型,关于主题模型的解释有个很通俗的例子: 第一个是:“乔布斯离我们而去了。” 第二个是:“苹果价格会不会降?” 我们一眼就可以看出这两句是有关联的,第一句里面有了“乔布斯”,我们会很自然的把“苹果”理解为苹果公司的产品,它们属于了同一个主题:苹果公司。 而像我之前那种计算关联度的时候,即文档之间重复的词语越多越可能相似,是无法达到这个效果的。文档之间重复的词语越多越可能相似,这一点在实际中并不尽然。很多时候相关程度取决于背后的语义联系——主题描述,而非表面的词语重复。 LDA的与上述方法不同之处在于:上述方法直接处理单词与文章的关系,而LDA过程在单词与文章之间加了一层主题,即文档——主题,主题——单词的路径计算。 LDA的概要 很多关于介绍LDA的文章大多以学术、理科学生的思维出发的,即用数学公式的严谨性来推导整个LDA的过程。我看了好久才理清了这个流程,因为它涉及到的数学推导很多,很容易陷入公式推导的怪圈里,无法对整个LDA的思想有个整体把握。。。 JULY博主说LDA分为五个部分: 一个函数:gamma函数 四个分布:二项分布、多项分布、
Read More
on Algorithm, 启发式搜索

启发式搜索

最近为了解决一个问题,粗略的学习了一些搜索算法,我真正动手实现的只有里面的2种,忽然感觉饶了一大圈又跑到机器学习的领域上去了。。。 写在前面 为了解决一个关于查找最短路径的问题,我查找了很多资料,学习到了一些新的算法。这篇文章我打算叙述两个部分,一个关于局部最优问题,一个关于启发式搜索问题。 问题的引入 这个问题来源于某公司的一个挑战赛中,是一个NP-hard问题,类似于旅行商问题和邮递员问题。其主要解决的问题就是在指定拓扑图G(V, E)中,找到一条尽量最优的路径,且这条路径不存在回路,且经过指定顶点集。 最短路径问题 想到最短路径问题,立马想到了Dijkstra算法了。。。这是一个非常高效的算法,它是基于贪心的算法思想。但上述题目并不具有贪心选择性质,会陷入局部最优。好的的情况下,会生成一条不是最优的路径;但差的情况下,甚至找不到一条有效路径。。 局部最优的情况 我第一次接触局部最优问题是在机器学习中的,比如逻辑回归在训练的过程中,采用梯度下降法对一些参数的优化的时候,会产生一些局部最优解。这是因为它的损失函数不是凸函数的缘故,因为这个函数有多个极值嘛。 在这个问题中,直接使用Dijkstra算法也会陷入局部最优的情况,如何跳出这个局部最优呢?比较典型的算法,哦不对应该是算法思想吧,模拟退火。这一题我之前就是用这个算法求解的,但效果不太理想。模拟退火算法属于一种启发式的搜素算法。 启发式的搜索
Read More
on Algorithm, 图的基础算法

图的常用算法

纸上得来终觉浅,绝知此事要躬行。打算把图的常用算法梳理一遍,加深一下记忆和理解。 简介 前面写了一遍关于图的存储结构和遍历算法的文章,这一篇打算回顾一下图的一些常用算法,包括最小生成树、最短路径算法。这些算法很基础,在生活中经常用到,打算自己动手实现一下,加深理解~~ 最小生成树 生成树的概念:r若图是连通的无向图或强连通的有向图,则从任何一个顶点出发调用一次BFS或者DFS便可访问图中所有的顶点,这种情况下,图中所有顶点加上遍历过程中经历的边构成的子图成为原图的生成树。对于不连通和不是强连通的有向图,这样得到的是生成森林。 最小生成树:对于加权图,权值最小的生成树成为最小生成树。可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出,这两种算法依据的思想是贪心思想。 prim(普利姆)算法 第一步:选择一个初始顶点V1,设置一个访问数组visit[]和最小距离数组distance[]。最小距离数组保存当前已访问顶点的生成树中到每个顶点最小的距离。 第二步:根据初始顶点V1,初始化visit和distance数组。 第三步:选择distance中权重最小的那个顶点,以此顶点为起始点更新distance数组,直至所有顶点都已访问。 未优化的prim算法时间复杂度为O(N^2),其C语言描述如下,: /* 输入分别为:
Read More
on 朴素贝叶斯分类器的实现, NLP

朴素贝叶斯分类器

因为工程实践里需要实现语义分析的功能,关于如何语义分析,我也是一头雾水。最近花了点时间,依据贝叶斯原理,针对工程实践,写了一个分类器,效果还阔以~~ 哈哈 写在前头 在研一上学期的时候,学院里分配了一个工程实践项目,我所在的4人组选了基于语义的搜索引擎这个课题,项目主页:https://github.com/willstudy/SearchEngine。目前项目进展到语义分析模块了,我就查阅了相关资料,然后根据项目的数据集,定制了一个贝叶斯分类器。 贝叶斯定理 老是说我第一眼看到这个定理的时候,完全没有任何印象。其实这个定理最早出现在本科所学的概率论中的,好惭愧,竟然被我忘光了。。。 贝叶斯定理主要是:当知道A发生的情况下,B发生的概率* P( B | A) 时, 求 B发生的条件下,A发生的概率 P( A | B ) *,其公式为: 这个公式在生活很有用,我们在不知不觉中可能就用到了它。比如说,在街上看到一个黑种人,我们很自然的联想到,他可能来自非洲。在得出判断的过程中,
Read More