算法工程师考点知识整理

来自一个可怜程序员~

计算机网络

http响应状态

100 - 继续。 101 - 切换协议。 110 重新启动标记答复。 120 服务已就绪，在 nnn 分钟后开始。 125 数据连接已打开，正在开始传输。 150 文件状态正常，准备打开数据连接。 200 - 确定。客户端请求已成功。 201 - 已创建。 202 - 已接受。 203 - 非权威性信息。 204 - 无内容。 205 - 重置内容。 206 - 部分内容。 211 系统状态，或系统帮助答复。 332 需要登录帐户。 350 请求的文件操作正在等待进一步的信息。 400 - 错误的请求。 401 - 访问被拒绝。 401.2 - 服务器配置导致登录失败。 401.3 - 由于 ACL 对资源的限制而未获得授权。 401.4 - 筛选器授权失败。 401.5 - ISAPI/CGI 应用程序授权失败。 401.7 – 访问被 Web 服务器上的 URL 授权策略拒绝。这个错误代码为 IIS 6.0 所专用。 403 - 禁止访问。** 404 - 未找到。** 405 - 用来访问本页面的 HTTP 谓词不被允许（方法不被允许） 406 - 客户端浏览器不接受所请求页面的 MIME 类型。 415 – 不支持的媒体类型。 417 – 执行失败。 423 – 锁定的错误。 425 无法打开数据连接。 450 未执行请求的文件操作。文件不可用（例如，文件繁忙）。 451 请求的操作异常终止：正在处理本地错误。 452 未执行请求的操作。系统存储空间不够。 500 - 内部服务器错误。

机器学习

距离

1、欧氏距离
d = sqrt(x1-x2)²+ (y1-y2)²)
2、余弦距离
算法工程师考点知识整理
余弦相速度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。
3、曼哈顿距离
d=abs(x1-x2)+abs(y1-y2)
两个点在标准坐标系上的绝对轴距总和
4、切比雪夫距离
dis=max(abs(x1-x2),abs(y1-y2))
各坐标数值差的最大值

聚类

KNN

1、一般使用投票法进行分类任务
2、KNN属于慵懒学习
3、KNN有训练集做标签但无需训练过程
4、距离计算方法不同，效果也可能也有显著差别

数据预处理

不平衡训练样本的处理

1、负采样、过采样
2、权重损失

优化算法

梯度下降

BGD 批量梯度下降：θ=θ−η⋅∇θJ(θ)
批量梯度下降每次学习都使用整个训练集，因此其优点在于每次更新都会朝着正确的方向进行，最后能够保证收敛于极值点(凸函数收敛于全局极值点，非凸函数可能会收敛于局部极值点)，但是其缺点在于每次学习时间过长，并且如果训练集很大以至于需要消耗大量的内存，并且全量梯度下降不能进行在线模型参数更新。
SGD随机梯度下降： θ=θ−η⋅∇θJ(θ;xi;yi)
批量梯度下降算法每次都会使用全部训练样本，因此这些计算是冗余的，因为每次都使用完全相同的样本集。而随机梯度下降算法每次只随机选择一个样本来更新模型参数，因此每次的学习是非常快速的，并且可以进行在线更新。
随机梯度下降最大的缺点在于每次更新可能并不会按照正确的方向进行，因此可以带来优化波动(扰动)。所带来的波动有个好处就是，对于类似盆地区域（即很多局部极小值点）那么这个波动的特点可能会使得优化的方向从当前的局部极小值点跳到另一个更好的局部极小值点，这样便可能对于非凸函数，最终收敛于一个较好的局部极值点，甚至全局极值点。
Mini-batch小批量梯度下降：θ=θ−η⋅∇θJ(θ;xi:i+m;yi:i+m
Mini-batch 梯度下降综合了 batch 梯度下降与 stochastic 梯度下降，在每次更新速度与更新次数中间取得一个平衡，其每次更新从训练集中随机选择 m,m<n 个样本进行学习

梯度下降优化算法
Adagrad：
一种基于梯度的优化算法，它能够对每个参数自适应不同的学习速率，对稀疏特征，得到大的学习更新，对非稀疏特征，得到较小的学习更新，因此该优化算法适合处理稀疏特征数据。
Adam：
它计算历史梯度衰减方式不同，不使用历史平方衰减，其衰减方式类似动量

拟牛顿法

概率图模型

概率图模型：用图的形式表示随机变量之间条件依赖关系的概率模型。
将随机变量作为结点，若两个随机变量相关或者不独立，则将二者连接一条边；若给定若干随机变量，则形成一个有向图，即构成一个网络。
如果该网络是有向无环图，则这个网络称为贝叶斯网络。
如果这个图退化成线性链的方式，则得到马尔可夫模型；因为每个结点都是随机变量，将其看成各个时刻(或空间)的相关变化，以随机过程的视角，则可以看成是马尔可夫过程。
若上述网络是无向的，则是无向图模型，又称马尔可夫随机场或者马尔可夫网络。
如果在给定某些条件的前提下，研究这个马尔可夫随机场，则得到条件随机场。
如果使用条件随机场解决标注问题，并且进一步将条件随机场中的网络拓扑变成线性的，则得到线性链条件随机场。

HMM和CRF

图像处理

颜色空间

RGB是以三基色相加组合而成的颜色系统：红、绿、蓝
HSV：基于感知的颜色系统。分为色调、饱和度、亮度。亮度分量与图像的色彩信息无关。
YCbCr：亮度、蓝色分量和红色分类。在通用的图像压缩算法中（如JPEG算法），首要的步骤就是将图像的颜色空间转换为YCbCr空间。
LAB空间是基于人眼识别的颜色系统。在LAB空间中，颜色距离更合理，距离大小能更好的反映颜色是否相近。由于Lab的色彩空间要比RGB模式和CMYK模式的色彩空间大。这就意味着RGB以及CMYK所能描述的色彩信息在Lab空间中都能得以映射。
YUV：亮度信号、色差信号。所谓色差是指基色信号中的三个分量信号(即R、G、B)与亮度信号之差。

自然语言处理

文本表示分类

一、离散表示
1）one-hot表示
2）词袋模型
优缺点：
1、计算简单、快速
2、在语料充足的前提下，对于简单的自然语言处理任务效果不错
3、凡是出现在文本中的词一视同仁，不能体现不同词在一句话中的不同的重要性。
4、无法关注词语之间的顺序关系，这是词袋子模型最大的缺点。
3）TF-IDF
不仅考虑这个词在当下文本的出现的概率，还考虑出现该词语的文档占总文档出现的频率
公示：TF-IDF = TF*IDF
算法工程师考点知识整理
逆向文件频率 (inverse document frequency, IDF) IDF的主要思想是：如果包含词条t的文档越少, IDF越大，则说明词条具有很好的类别区分能力。某一特定词语的IDF，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到。
算法工程师考点知识整理
某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。因此，TF-IDF倾向于过滤掉常见的词语，保留重要的词语。
二、文本分布式表示
1）基于矩阵的SVD降维
这是一种词向量的方法，我们首先会遍历所有的文本数据集，然后统计词出现的次数，接着用一个矩阵X来表示所有的次数情况，紧接着对X进行奇异值分解得到一个USV^{T}的分解。然后用U的行（rows）作为所有词表中词的词向量。
优缺点：能够充分地编码语义和句法的信息；然而存在矩阵非常稀疏、维度大、训练计算复杂等情况。
2）基于神经网络的表示方法
word2vec模型
主要有skip-gram和CBOW两种模型
Skip-Gram是给定input word（中间的词）来预测上下文。CBOW是给定上下文，来预测input word（中间的词）
存在的问题：对每个局部上下文窗口单独训练，没有利用全局共现矩阵中的统计信息；对多义词无法很好的表示和处理，因为使用了唯一的词向量
Glove模型

数学逻辑题

斐波那契数列

F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）
其中，F(1)=1，F(2)=1
经典题目：有10层台阶，小明每次可以爬一台阶或者两台阶，请问，爬到10层台阶，小明一共有（）种爬法

排列组合问题之隔板法

隔板法就是在n个元素间的（n-1）个空中插入k个板，可以把n个元素分成k+1组的方法。
应用隔板法必须满足3个条件：1）这n个元素必须互不相异 2）所分成的每一组至少分得1个元素 3）分成的组别彼此相异
公示：C(n-1,k-1)
12个糖果分给3个人，每人至少的一个，有几种不同分法：
使用挡板法来解决此类问题。把12个糖果排成一排，可以得知中间有11个空位，在其中任一空位插入两个挡板即可。故此题的答案为C(11,2) = 55

算法工程师考点知识整理

笔试面试笔记

分类

计算机网络

http响应状态

机器学习

距离