Deep-Learning-for-NLP-LSTM

Background

提到LSTM,首先要了解的是“递归神经网络”,也就是不可思议的RNN(Recurrent Neural Network),它是神经网络的一种。人工神经网络,与其他机器学习算法相比的优势很明显,简称神经网络,是仿照生物神经网络的结构和功能的数学模型。神经网络由大量的人工神经元联结进行计算,可以对外界信息抽象改变结构,是一种自适应系统。深度学习,就是一个多层的神经网络,而“递归神经网络”就是一个深度学习的算法。RNN与其他神经网络的不同在于,它比普通的feed-forward网络多了一层循环

rnn-structure

了解word2vec

image

一、什么是word2vec

word2vec是Google在2013年中开元的一款将词表征为实数值向量的高效工具,采用的模型有CBOW(Continuous Bag-Of-Words,即连续的词袋模型)和Skip-Gram两种。word2vec项目主页地址点击,它遵循Apache License 2.0 开源协议,是一种对商业友好的许可,需要充分尊重原作者的著作权。
word2vec一般被外界认为是一个Deep Learning(深度学习)的模型,究其原因,可能和作者Tomas Mikolov的Deep Learning背景以及word2vec是一种神经网络模型相关,但我们认为该模型层次较浅,严格来讲还不能算是深层模型。当然如果word2vec上层再套一层与具体应用相关的输出层,比如Softmax,此时更像是一个深层模型。
word2vec通过训练,可以把对文本内容处理简化为K维向量空间中的向量运算,而向量空间上的相似度可以用来表示文本语义上的相似度。因此,word2vec输出的词向量可以被用来做很多NLP相关的工作,比如聚类、找同义词、词性分析等。而word2vec被人广为传颂的地方是其他向量的假发组合运算(Additive Compositionality),官网上的例子是:vector(‘Paris’) - vector(‘France’) + vector(‘Italy’) ≈ vector(‘Rome’)。但我们认为这个多少有点被过度炒作了,很多其他降维或主题模型在一定程度也能达到类似效果,而word2vec也只是少量的例子完美符合这种加减法操作,并不是所有的case都满足。
word2vec大受欢迎的另一个原因是其高效性,Mikolov在论文中支出优化的单机版本一天可训练上千亿词。

二、快速入门

  1. 代码下载
  2. 针对个人需求修改makefile文件,也可以不做修改
  3. 运行“make”编译word2vec工具
  4. 运行demo脚本,查看效果

三、背景知识

1.One-hot Representation
NLP相关任务中最常见的第一步是创建一个词表库并把每个词顺序编号。

百度面试题总结—03(操作系统)

查看原题

1.SSH

问题描述:linux/unix远程登陆都用到了ssh服务,当网络出现错误时服务会中断,linux/unix端的程序会停止。为什么会这样?说下ssh的原理,解释中断的原理。
首先解释一下SSH原理。这里有一篇文章,对SSH讲的很好,点击查看。下面我再对SSH做一个简单的介绍。简单地说,SSH就是一种网络协议,用于计算机之间加密登陆。

  • 最基本的用法:ssh -p 端口号 username@host,其中端口号默认为22;
  • 整个过程:(1)远程主机收到用户的登陆请求,把自己的公钥发给用户,(2)用户使用远程主机的公钥加密密码,将加密后的密码发送过来,(3)远程主机用自己的私钥解密密码,判断能否让远程用户登录。
  • 存在隐患:如果登陆请求被截获,冒充远程主机,将伪造的公钥发给用户,那么用户很难辨别真伪。
    下面解释一下为何网络出现错误时服务会中断,参考原文。网络出错,相当于程序的控制台关闭。
    中断的原理:所谓中断,是指CPU在正常运行程序时,由于程序预先安排或内外部事件,引起CPU中断正在运行的程序,而转到发生中断事件程序中。

2.进程与线程的区别

概念:

  • 进程:一个程序对一个数据集的动态执行的过程,是分配资源的基本单位;
  • 线程:一个进程内的基本调度单位;
  • 线程的划分尺度小于进程,一个进程可以包含一个或更多的线程。

执行过程:

  • 进程:拥有独立的内存单元,而多个线程共享内存,从而提高了应用程序的运行效率;
  • 线程:不能独立运行,必须依赖于线程中的共享资源;

百度面试题总结—02(语言知识)

查看原题

1.解释下面ptr不同含义

1
2
3
4
5
6
7
8
double* ptr = &value;
//ptr是一个指向double类型的指针,ptr的值可以改变,ptr所指向的value的值也可以改变
const double* ptr = &value
//ptr是一个指向const double类型的指针,ptr的值可以改变,ptr所指向的value的值不可以改变
double* const ptr=&value
//ptr是一个指向double类型的指针,ptr的值不可以改变,ptr所指向的value的值可以改变
const double* const ptr=&value
//ptr是一个指向const double类型的指针,ptr的值不可以改变,ptr所指向的value的值也不可以改变

2.去掉const属性

例: const double value = 0.0f; double* ptr = NULL;怎么才能让ptr指向value?
强制类型转换,去掉const属性,如

1
ptr = <const_cast double *>(&value)

3.动态链接库与静态链接库的区别

静态链接库是.lib格式的文件,一般在工程的设置界面加入工程中,程序编译时会把lib文件的代码加入你的程序中因此会增加代码大小,你的程序一运行lib代码强制被装入你程序的运行空间,不能手动移除lib代码。动态链接库是程序运行时动态装入内存的模块,格式*.dll,在程序运行时可以随意加载和移除,节省内存空间。在大型的软件项目中一般要实现很多功能,如果把所有单独的功能写成一个个lib文件的话,程序运行的时候要占用很大的内存空间,导致运行缓慢;但是如果将功能写成dll文件,就可以在用到该功能的时候调用功能对应的dll文件,不用这个功能时将dll文件移除内存,这样可以节省内存空间。

4.指针与引用的区别

相同点:都是地址的概念,指针指向一块内存,它的内容是所指内存的地址,引用是某块内存的别名。
不同点:

  • 指针是一个实体,而引用是一个别名;
  • 指针使用时需要加(*);
  • 引用只能在定义时被初始化一次,之后不可改变,指针可变;
  • 引用没有const,指针有const;
  • 引用不能为空,指针能为空;
  • sizeof引用得到的是所指的变量的大小,sizeof指针得到的是指针本身的大小;
  • 自增含义不同;
  • 内存分配上来看:程序为指针分配内存区域,不为引用分配内存区域。

5.c++对象模型与虚表

  • C++中对象模型:语言中直接支持”面向对象程序设计“的部分,对于各种支持的低层实现机制;
  • 在C++中有两种成员数据:static、nonstatic,三种成员函数:static、nonstatic和virtual;
  • 虚函数:虚函数就是C++语言中,那些被virtual关键字修饰的成员函数。虚函数的作用就是实现多态,多态是将接口与实现进行分离,通俗来讲,就是实现以共同的方法,但因个体差异而采用不同策略。

百度面试题总结—01(算法)

查看原题

1.用C语言实现一个revert函数,它的功能是将输入的字符串在原串上倒序后返回。

思路:重新定义一个字符串,反向取出原字符串的值

1
2
3
4
5
6
7
8
9
10
11
12
char *revert(char *str)
{

int lenght = strlen(str);
char *ret = new char(lenght);
int left = 0, right = lenght - 1;
for (int i = lenght - 1; i >= 0; i--)
{
ret[lenght - i - 1] = str[i];
}
ret[lenght] = '\0';
return ret;
}

2.用C语言实现函数void memmove(void dest, const void *src, size_t n),memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。

思路:主要解决内存重叠的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void *memmove(void *dest, const void *src, size_t n)
{

if (NULL == dest || NULL == src)
{
cerr << "NULL pointers";
return NULL;
}
int step;
char *p, *q;
if ((char *)src == (char *)dest)
return dest;
else if ((char *)src > (char *)dest)
{
step = 1;
p = (char *)src;
q = (char *)dest;
}
else
{
step = -1;
p = (char *)src + n - 1;
q = (char *)dest + n - 1;
}
for (int i = 0; i != n; i++)
{
*q = *p;
p += step;
q += step;
}
return dest;
}

3.蚂蚁与木杆

描述:有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过一只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。
思路:蚂蚁相遇掉头,可以看作蚂蚁还在继续往各自的前方走。

4.给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。

思路:取左右两个指针,分别从头部和尾部遍历,交换不和谐元素。

5.在一维坐标轴上有n个区间段,求重合区间最长的两个区间段。

思路:根据每个区段左坐标排序,每次记录最大重合距离和最远有坐标。
备注:贪心问题,类似不同时间段任务安排。

6.现在有1千万个随机数,随机数的范围在1到1亿之间。现在要求写出一种算法,将1到1亿之间没有在随机数中的数求出来。

思路:利用位图,即开一个1亿位的bitset,内存为100m/8== 12.5m, 然后如果一个数有出现,对应的bitset上标记为1,最后统计bitset上为0的即可。

7.循环有序数组的二分查找。

对已排好序的数组A,一般来说可用二分查找可以很快找到。现有一特殊数组A[],它是循环递增的,如A[]={ 17 19 20 25 1 4 7 9},试在这样的数组中找一元素x,看看是否存在。
LeetCode原题,查看请点击LeetCode-num033

8.如何解决Hash冲突等问题

(1)哈希函数的构造方法:数字分析方法,平方取中法,分段叠加法,除留取余法,伪随机数法
(2)处理冲突的方法:开放定址法,再哈希法,链地址法,建立公共溢出区。

9.判断一个数的所有因数的个数是偶数还是奇数

开始每太理解,仔细看一下答案,才理解题意。答案是这样的,如果这个数是平方数,那么结果为奇数,否则为偶数。
那么顺着这个思路可以继续思考,如果这个数所有质因数都是偶数个,那么这个数就是平方数,结果为奇;否则只要有质因数个数是一个,结果就是偶。

10.

问题描述:写一个C的函数,输入整数N,输出整数M,M满足:M是2的n次方,且是不大于N中最大的2的n次方。例如,输入4,5,6,7,都是输出4。
思路:平均时间复杂度可以达到O(logN),遍历从一到给定数之间所有的2的倍数。找到最大不大于给定数的值。
但是这是最好的答案了吗?我觉得不是,可以寻找更好的办法。
优化:我们都知道位运算,2的次方数的二进制有个特点,就是首位为1,而其他所有的位都是0。那么从这个角度出发。那么我们只要得到最二进制中最高位的值就可以了。那么我们可以直接通过位运算求得输入数字的二进制最高位就可以了。
那么问题又来了,怎么获得最高位的值呢,可以不断移位,计数数位数,但这样做的其实和最开始的方法效率是一样的。
优化:其实再想一下的话,我们可以先获得除了二进制首位剩余位的值,然后与原数异或运算,就可以直接得到结果。时间复杂度降到O(1)。

Lucene01-简介

Lucene到底是什么?它并不是一门语言,不是一个工具,它是搜索引擎领域一个重要组成部分,是实现提供高性能,进行全文索引和搜索等功能的开源库。

Lucene的优点

  • 索引文件格式独立于平台,使得不同的平台能够共享到索引文件;
  • 它具有优秀的面向对象的系统架构;
  • 它默认了一套强大的查询引擎,包括模糊查询,分组查询等。

Lucene的适用范围

  • 文本检索;
  • 网站的信息搜索;
  • 数据库的搜索

Lucene的架构

Lucene秉承了开源代码的一贯的架构优良的优势,设计了一个合理而极具扩充能力的面向对象架构,程序员可以在Lucene的基础上扩充各种功能,而且由于Lucene恰当合理地对系统设备做了程序上的抽象,扩展的功能也能轻易地达到跨平台的能力。
架构
组件
在上图中,Document对象表示被索引的文档,IndexWriter会通过函数AddDocument将文档添加到索引中,从而实现穿件索引的过程。又因为Lucene的Index是应用反向索引,当用户发出请求时,Query代表着用户的查询语句,IndexSearch通过函数search搜索Lucene的Index,同时计算term weight和score,并将结果及时地返回给用户,TOPDocsCllector则实现对返回给用户的文档集合展示,这样就将整个Lucene组建紧密地联系在了一起。