个人面试数据结构与算法

1 介绍一下逻辑回归
2介绍一下HMM**
3主动学习中有哪些算法是应用在图像方面的？
4dropout的原理，和在tensorflow 中在是怎么写的
Dropout简单来说，我们在前向传播的时候，让某个神经元的激活值以一定的概率p停止工作，这样可以使模型的泛化能力更强，因为它不会它太依赖于某些局部特征。
Dropout具体工作流程：
没有Dropout的工作过程：(输入x,输出y)首先把x通过网络前向传播，然后在通过误差反向传播决定如何经行参数更新，‘
使用Dropout后：
（1）首先随机删掉网络中一半的隐藏神经元，输入输出神经元保持不变。
（2）把x通过修改后的网络进行前向传播，一小批训练样本执行完这个过程后，在没有被删除的神经元上按随机梯度下降法经行参数更新。
不断重复这一过程。
Tensorflow中的过程。

importnumpy as np a= np.array([[1,2,3,4,5]]) #输入a keep_prob = 0.5#keep_prob对原数据保留多少， uniform_data = https://www.it610.com/article/np.random.uniform(0,1,5)#产生一个与输入一样形状的随机数 print("uniform_data",uniform_data) binary_data= https://www.it610.com/article/np.floor(keep_prob+uniform_data)#将keep和随机数相加，向下取整。得到一些0，1的数值 print("binart_data",binary_data) a = (a/keep_prob)*binary_data print("a",a)

5梯度消失和爆炸，以及一些解决的方法
梯度消失常常在两种情况中出现：
（1）是在深层网络中，（2）采用了不合适的激活函数，比如sigmoid
当进行反向传播算法经行参数更新时，根据链式求导法则，可以看出激活函数的导数会呈指数的方式经行增长，如果对激活函数求导，激活函数的导数大于1，则产生梯度爆炸，如果激活函数的导数小于1，产生梯度消失。
解决:
(1)梯度剪切（解决梯度爆炸）：其思想是设置一个梯度剪切阈值，然后更新梯度的时候，如果梯度超过这个阈值，那么就将其强制限制在这个范围之内。这可以防止梯度爆炸。
(2)换激活函数; relu,leak_relu
(3)残差结构。
6 bagging 和boosting的区别
Bagging 的思想比较简单，即每次从原始数据集中根据均匀概率分布有放回的抽取和原始数据大小相同的集合，样本点可能重复，然后对每一次产生的训练集构造一个分类器，再对分类器经行组合。
boosting的每一次抽样样本分布都是不一样的，每一次迭代都是根据上次迭代的结果，增加被错误分类的样本权重，使得这个模型能够在之后的迭代中更加注意到难以分类的样本，这是一个不断学习的过程，迭代之后，将每次迭代的基本分类器集成。
GBDT：gbdt的核心在于每一棵树学的是之前所有树的结论和残差，比如A的真是年龄是18，但是第一颗树的预测年龄是12，差了6岁，即残差为6岁。那么在第二棵树里，我们把A的年龄设为6去学习，如果第二棵树真能把A分到6岁的叶子节点，哪累加两棵树的结论就是A的真实年龄，
推导损失函数用到了一阶泰勒展开式，最后得到的loss函数，计算划分前的loss和划分后左右子树的总loss，如果能使得loss减小就进行划分
xgboost:相比GBDT来说，更加有效的应用了数值优化，重要的是对损失函数变的更复杂，xgboost的损失函数进行了二阶泰勒展开，同时用到了一阶导数和二阶导数，xgboost在损失函数中加入了正则项，用于控制模型的复杂度。
7KNN
8HMM
9SVM
支持向量机是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大线性分类器。
对于线性可分二分类SVM
给定一个特征空间上的训练数据集,包含N个样本(X,Y),Y只有两种情况+1和-1，
学习的目标是在特征空间上找到一个分离超平面，能将实例分到不同的类，分离超平面对应于w*x+b = 0,
一般来说，一个点距离分类超平面的远近可以表示分类预测的确信程度，在超平面wx+b = 0确定的情况下，|wx+b|能够表示点x距离超平面的远近。而wx+b 的符号与类标记y的符号是否一致能够表示分类的正确性，也可以用有y（wx+b）表示函数间隔。
函数间隔和几何间隔
函数间隔可以表示表示分类预测的正确性以及确信度，但是在选择分类超平面只有函数间隔还不够，因为只要成比例的改变2w,2b，超平面并没有改变，但是函数间隔变成原来的2倍。从而引出了几何间隔，几何间隔（函数间隔/|w|）,如果|w|=1，函数间隔和几何间隔相等，此时成比例的改变w，b,函数间隔发生变换，几何间隔没有变。
间隔最大化：
支持向量机学习的基本想法就是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。
求几何间隔最大分离超平面可以转化成一个约束优化问题，
9fastercnn过程，和损失函数的组成部分
10EM算法
EM算法是一种迭代算法，用于含有隐变量的概率模型的极大释然估计。EM算法每次迭代由两部组成，E步：求期望，M步：求极大。所以这一算法称为期望极大算法。
核心思想：EM算法是通过不断求解下届的极大化逼近求解对数似然函数的极大化。
L(&) = logp(X|&)
= ELBO+KL(q||p)
所以L>ELBO,通过ELBO取极大，不断逼近L极大，
一般的，用X表示观测随机变量的数据，Z表示隐随机变量的数据，X,Z连在一起称为完全数据。假设给定观测数据X，其概率的分布是P(X|&),其中&是需要估计模型的参数，那么X的似然函数是P(X|&)
,对数似然函数L(&) = logp(X|&)。
EM算法通过迭代求L(&) = logp(X|&)的似然估计，每迭代包含两步，E步，求期望，M步求极大化。
EM算法不能保证找到全局最优解，因为EM算法与初值选择有关，选择不同的初值可能得到不同的参数估计。
11SSD中的多尺度特征图预测：
再SSD中随着卷积和池化的进行，特征图的尺度在逐渐减小，此时用小的特征图预测大的目标，用大的特征图检测小的目标
因为较大的特征图分辨高，而且可以划分为更多较小的单元，每个小单元的先验框尺度比较小，正好用来检测小物体，而小的特征图语义信息更加丰富，感受野更大，负责检测大的物体。
12随机森林**
组合分类器：将多个分类器的结果进行多票表决或者是取平均值。以此作为最终的结果。‘
随机森林是一个典型的多个决策树的组合分类器。主要包括两个方面：数据的随机性选取以及待选特征的随机性选取。
（1）数据的随机性选取：
第一，从原始数据集中采取有放回的抽样，构造子数据集，子数据集的数量和原始数据集的数量是相同的。不同子数据集的元素可以重复，同一子数据的元素也可以重复。
第二，利用子数据来构建子决策树，将这个数据放到每个决策树中，每个子决策树输出一个结果。最后，如果有了新的数据需要通过随机森林得到分类结果，就可以通过对子决策树的判断结果进行投票，得到随机森林的输出结果。
（2）待选特征的随机性选取：
与数据集的随机选取类似，随机森林中的子树的每一个分裂过程并未用到所有特征，而是从所有特征中随机选取一定特征，之后在随机选取的特征中选择最优的特征，这样就能够使得随机森林中的决策树都能够彼此不同。
13BN(批量归一化)
BN主要解决的一个问题是空间协变量转移( Internal Covariate Shift)
背景：我们一般在神经网络训开始之前都会对数据做一个归一化处理，因为神经网络学习的本质就是学习数据的分布，一但训练数据和测试数据分布不一致，就会使得网络的泛化能力大大减小。另一方面，每一层数据分布发生变换之后使得学习速度变慢。
空间协变量：假设在一个深度神经网络中，输入数据是经过归一化的，第二层网络的输入是由第一层网络的input和weight得到的，那么在训练过程中第一层网络的weights在不断更新，那么第二层网络的输入数据分布在不断变化,(后几层网络的输入分布一样都在不断变化)这个就叫空间协变量转移。
BN原理：BN要对每一层的数据经行一个归一化，但是又不能丢到上一层所学到的分布，对数据经行一个”变换重构“，引入两个可学习的参数 gamma 和 beta.
(1)对数据求均值
(2)对数据求方差
(3)对数据经行归一化
(4)利用学习到的两个参数经行变换重构
【个人面试】BN在CNN中的应用：CNN的每一输出为[N,C,W,H],N为一批样本的个数，C为滤波器的个数，WH为特征图的大小。每个BN去作用在每个滤波器上。因此就是对每个C（i = range(0,C)），求BW*H个特征的均值方差，所以最后均值和方差的个数就各有C个
14Faster rcnn算法的详细过程
Faste r -cNN算法的基本网络结构，主要是由基础网络，RPN网络和检测子网络三部分组成。该算法的核心思想是，首先利用基础网络实现对图像目标特征的有效提取，并且基础网络参数均被RPN网络和检测子网络所共享。然后将基础网络所提取的特征图分别传入RPN网络和检测子网络中，RPN网络负责生成目标初始建议框并将初步预测为前景目标最高得分的前N（300）个建议候选框通过Roi Pooling层统一成为固定尺寸后传入目标检测子网络中，实现最终特定的目标类别检测。
（1）基础网络
目前基于Faster R-CNN目标加测算法的主流基础网络主要有VGG,Inception和EesNet,基础网络主要用于对输入图像经行特征提取，提取的特征不仅包括图像颜色，边缘，纹理等底层特征。还包括能表达目标完整组件，语义等信息的高层全局特征，并且一般随着网络加深，提取到的目标特征的可区分性也强，但同时保留的原始图像信息也会越少。
（2）RPN网络是一个全卷积网络，主要目的是给目标加测子网络提供可能包含前景目标的高质量建议框。RPN网络首先利用3x3大小的卷积核，按从左到右，从上到下依次遍历整张特征图，并且每个滑动窗口中心所在的位置在输入图像映射区域中心上对应产生9个初始建议框，为了方便起见，命名每个初始建议框为锚框（anchor）,9种锚框分别由3种比例1：1，1：2，2：1和三种尺度面积为128128，256256，512512组成。然后将这个结果分别送入RPN的分类卷积层和回归卷积层中实现对目标的类别判断和边界框的位置回归。
这里RPN网络只负责实现目标的前景与背景的二分类判断，因此对于RPN将建议的K个锚框分类层共输出2K个类别的概率，每个锚框需要4个位置参数，所以回归层共输出4k个坐标值。回归的目标是为了实现对目标初始框位置的粗休正。qiu
（3）检测子网络，
检测子网一般由PoI pooling层和两层全连接层构成。首先使用Roi Pooling将候选框统一池化为77*512（VGG）固定大小的特征向量，然后通过两层全连接层处理完之后分别送入检测子网络的分类层和回归层，其中分类层负责实现对目标候选框的类别判断，回归层负责实现对目标候选框位置的精调，
15：随机森林，GBDT，XGBoost的对比
随机森林的学习方法是Bagging,但是和Bagging不同的是bagging只采用boostarp有放回的抽样，但是随机森林包括随机采取样本和随机进行特征选择。因此防止过拟合的能力更强。
GBDT是一种Boosting的方法，其与传统的Boosting的区别是，每一次的计算是为了减少上一次的残差(residual)，而为了消除残差，可以在残差减少的梯度(Gradient)方向上建立一个新的模型。所以说，在Gradient Boosting中，每个新的模型的建立是为了使得之前模型的残差往梯度方向减少，与传统Boosting对正确、错误样本进行加权有着很大的区别。这个梯度代表上一轮学习器损失函数对预测值求导。()
XGBoost比GBDT好的地方：二阶泰勒展开节点分数惩罚正则
传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
假如给你15个样本和4个特征去构建一颗决策树？
假设我们用ID3去构建决策树，ID3主要用的方法是信息增益，也就是经验熵H(D)-条件经验熵H(D|A),首先计算这4个特征的信息增益，哪个特征的信息增益最大，就选择哪个特征为根节点特征，假如该特征有两个属性，且其中一个属性的样本都划为同一类，则该属性当作叶子节点，另一个属性根据递归方法继续此过程，直到所有样本都划为叶子节点，即可停止。
3数据结构算法：
1怎么判断一个链表是一个环形链表
2给定一个数组，怎么求最长递增序列（非连续）
3给定一个数组，和一个目标值，求数组中两个元素的和为给定目标值的下标。