欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

***BAT机器学习面试1000题系列

程序员文章站 2022-04-18 12:47:45
...

BAT机器学习面试1000题系列



整理:July、元超、立娜、德伟、贾茹、王剑、AntZ、孟莹等众人。本系列大部分题目来源于公开网络,取之分享,用之分享,且在撰写答案过程中若引用他人解析则必注明原作者及来源链接。另,不少答案得到寒小阳、管博士、张雨石、王赟、褚博士等七月在线名师审校。
说明:本系列作为国内首个AI题库,自2017年9月28日开始,每周持续更新。首发于七月在线实验室公众号上:julyedulab,并同步更新于本博客上,且已于17年双十二当天上线七月在线官网七月在线Android APP七月在线iPhone APP题目勘误及更多题目都体现在这三端上,欢迎天天刷题。另,可以转载,注明来源链接即可。



前言

    July我又回来了。

    之前本博客整理过数千道微软等公司的面试题,侧重数据结构、算法、海量数据处理,详见:微软面试100题系列,今17年,近期和团队整理BAT机器学习面试1000题系列,侧重机器学习、深度学习。我们将通过这个系列索引绝大部分机器学习和深度学习的笔试面试题、知识点,它将更是一个足够庞大的机器学习和深度学习面试库/知识库,通俗成体系且循序渐进。

    此外,有四点得强调下:
  1. 虽然本系列主要是机器学习、深度学习相关的考题,其他类型的题不多,但不代表应聘机器学习或深度学习的岗位时,公司或面试官就只问这两项,虽说是做数据或AI相关,但基本的语言(比如Python)、编码coding能力(对于开发,编码coding能力怎么强调都不过分,比如最简单的手写快速排序、手写二分查找)、数据结构、算法、计算机体系结构、操作系统、概率统计等等也必须掌握。对于数据结构和算法,一者 重点推荐前面说的微软面试100题系列(后来这个系列整理成了新书《编程之法:面试和算法心得》),二者 多刷leetcode,看1000道题不如实际动手刷100道。
  2. 本系列会尽量让考察同一个部分(比如同是模型/算法相关的)、同一个方向(比如同是属于最优化的算法)的题整理到一块,为的是让大家做到举一反三、构建完整知识体系,在准备笔试面试的过程中,通过懂一题懂一片。
  3. 本系列每一道题的答案都会确保逻辑清晰、通俗易懂(当你学习某个知识点感觉学不懂时,十有八九不是你不够聪明,十有八九是你所看的资料不够通俗、不够易懂),如有更好意见,欢迎在评论下共同探讨。
  4. 关于如何学习机器学习,最推荐机器学习集训营系列。从Python基础、数据分析、爬虫,到数据可视化、spark大数据,最后实战机器学习、深度学习等一应俱全。
    另,本系列会长久更新,直到上千道、甚至数千道题,欢迎各位于评论下留言分享你在自己笔试面试中遇到的题,或你在网上看到或收藏的题,共同分享帮助全球更多人,thanks。


BAT机器学习面试1000题系列

  1. 请简要介绍下SVM,机器学习 ML模型 易SVM,全称是support vector machine,中文名叫支持向量机。SVM是一个面向数据的分类算法,它的目标是为确定一个分类超平面,从而将不同的数据分隔开。
    扩展:这里有篇文章详尽介绍了SVM的原理、推导,《
支持向量机通俗导论(理解SVM的三层境界)》。此外,这里有个视频也是关于SVM的推导:《纯白板手推SVM》请简要介绍下tensorflow的计算图,深度学习 DL框架 中
@寒小阳&AntZ:Tensorflow是一个通过计算图的形式来表述计算的编程系统,计算图也叫数据流图,可以把计算图看做是一种有向图,Tensorflow中的每一个节点都是计算图上的一个Tensor, 也就是张量,而节点之间的边描述了计算之间的依赖关系(定义时)和数学操作(运算时)。如下两图表示:
a=x*y; b=a+z; c=tf.reduce_sum(b);
***BAT机器学习面试1000题系列***BAT机器学习面试1000题系列
在k-means或kNN,我们常用欧氏距离来计算最近的邻居之间的距离,有时也用曼哈顿距离,请对比下这两种距离的差别。机器学习 ML模型 中
欧氏距离,最常见的两点之间或多点之间的距离表示法,又称之为欧几里得度量,它定义于欧几里得空间中,如点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为:
***BAT机器学习面试1000题系列
欧氏距离虽然很有用,但也有明显的缺点。它将样品的不同属性(即各指标或各变量量纲)之间的差别等同看待,这一点有时不能满足实际要求。例如,在教育研究中,经常遇到对人的分析和判别,个体的不同属性对于区分个体有着不同的重要性。因此,欧氏距离适用于向量各分量的度量标准统一的情况。
  • 曼哈顿距离,我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离,也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上,坐标(x1, y1)的点P1与坐标(x2, y2)的点P2的曼哈顿距离为:***BAT机器学习面试1000题系列,要注意的是,曼哈顿距离依赖座标系统的转度,而非系统在座标轴上的平移或映射。当坐标轴变动时,点间的距离就会不同。
     通俗来讲,想象你在曼哈顿要从一个十字路口开车到另外一个十字路口,驾驶距离是两点间的直线距离吗?显然不是,除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”,这也是曼哈顿距离名称的来源, 同时,曼哈顿距离也称为城市街区距离(City Block distance)。
曼哈顿距离和欧式距离一般用途不同,无相互替代性。另,关于各种距离的比较参看《从K近邻算法、距离度量谈到KD树、SIFT+BBF算法》。CNN的卷积核是单层的还是多层的?深度学习 DL模型 中
@AntZ:卷积运算的定义和理解可以看下这篇文章《CNN笔记:通俗理解卷积神经网络》,链接:http://blog.csdn.net/v_july_v/article/details/51812459,在CNN中,卷积计算属于离散卷积, 本来需要卷积核的权重矩阵旋转180度, 但我们并不需要旋转前的权重矩阵形式, 故直接用旋转后权重矩阵作为卷积核表达, 这样的好处就离散卷积运算变成了矩阵点积运算。
一般而言,深度卷积网络是一层又一层的。层的本质是特征图, 存贮输入数据或其中间表示值。一组卷积核则是联系前后两层的网络参数表达体, 训练的目标就是每个卷积核的权重参数组。
描述网络模型中某层的厚度,通常用名词通道channel数或者特征图feature map数。不过人们更习惯把作为数据输入的前层的厚度称之为通道数(比如RGB三色图层称为输入通道数为3),把作为卷积输出的后层的厚度称之为特征图数。
卷积核(filter)一般是3D多层的,除了面积参数, 比如3x3之外, 还有厚度参数H(2D的视为厚度1). 还有一个属性是卷积核的个数N。
卷积核的厚度H, 一般等于前层厚度M(输入通道数或feature map数). 特殊情况M > H。
卷积核的个数N, 一般等于后层厚度(后层feature maps数,因为相等所以也用N表示)。
卷积核通常从属于后层,为后层提供了各种查看前层特征的视角,这个视角是自动形成的。
卷积核厚度等于1时为2D卷积,也就是平面对应点分别相乘然后把结果加起来,相当于点积运算. 各种2D卷积动图可以看这里https://github.com/vdumoulin/conv_arithmetic
***BAT机器学习面试1000题系列
卷积核厚度大于1时为3D卷积(depth-wise),每片平面分别求2D卷积,然后把每片卷积结果加起来,作为3D卷积结果;1x1卷积属于3D卷积的一个特例(point-wise),有厚度无面积, 直接把每层单个点相乘再相加。
归纳之,卷积的意思就是把一个区域,不管是一维线段,二维方阵,还是三维长方块,全部按照卷积核的维度形状,从输入挖出同样维度形状, 对应逐点相乘后求和,浓缩成一个标量值也就是降到零维度,作为输出到一个特征图的一个点的值. 这个很像渔夫收网。
可以比喻一群渔夫坐一个渔船撒网打鱼,鱼塘是多层水域,每层鱼儿不同。
船每次移位一个stride到一个地方,每个渔夫撒一网,得到收获,然后换一个距离stride再撒,如此重复直到遍历鱼塘。
A渔夫盯着鱼的品种,遍历鱼塘后该渔夫描绘了鱼塘的鱼品种分布;
B渔夫盯着鱼的重量,遍历鱼塘后该渔夫描绘了鱼塘的鱼重量分布;
还有N-2个渔夫,各自兴趣各干各的;
最后得到N个特征图,描述了鱼塘的一切!
2D卷积表示渔夫的网就是带一圈浮标的渔网,只打上面一层水体的鱼;
3D卷积表示渔夫的网是多层嵌套的渔网,上中下层水体的鱼儿都跑不掉;
1x1卷积可以视为每次移位stride,甩钩钓鱼代替了撒网;
下面解释一下特殊情况的 M > H:
实际上,除了输入数据的通道数比较少之外,中间层的feature map数很多,这样中间层算卷积会累死计算机(鱼塘太深,每层鱼都打,需要的鱼网太重了)。所以很多深度卷积网络把全部通道/特征图划分一下,每个卷积核只看其中一部分(渔夫A的渔网只打捞深水段,渔夫B的渔网只打捞浅水段)。这样整个深度网络架构是横向开始分道扬镳了,到最后才又融合。这样看来,很多网络模型的架构不完全是突发奇想,而是是被参数计算量逼得。特别是现在需要在移动设备上进行AI应用计算(也叫推断), 模型参数规模必须更小, 所以出现很多减少握手规模的卷积形式, 现在主流网络架构大都如此。比如AlexNet:
***BAT机器学习面试1000题系列
另,附百度2015校招机器学习笔试题:http://www.itmian4.com/thread-7042-1-1.html
关于LR。机器学习 ML模型 难@rickjin:把LR从头到脚都给讲一遍。建模,现场数学推导,每种解法的原理,正则化,LR和maxent模型啥关系,lr为啥比线性回归好。有不少会背答案的人,问逻辑细节就糊涂了。原理都会? 那就问工程,并行化怎么做,有几种并行化方式,读过哪些开源的实现。还会,那就准备收了吧,顺便逼问LR模型发展历史。***BAT机器学习面试1000题系列
另外,这两篇文章可以做下参考:Logistic Regression 的前世今生(理论篇)机器学习算法与Python实践之(七)逻辑回归(Logistic Regression)。overfitting怎么解决?机器学习 ML基础 中
dropout、regularization、batch normalizatin
@AntZ: overfitting就是过拟合, 其直观的表现如下图所示,随着训练过程的进行,模型复杂度增加,在training data上的error渐渐减小,但是在验证集上的error却反而渐渐增大——因为训练出来的网络过拟合了训练集, 对训练集外的数据却不work, 这称之为泛化(generalization)性能不好。泛化性能是训练的效果评价中的首要目标,没有良好的泛化,就等于南辕北辙, 一切都是无用功。

***BAT机器学习面试1000题系列
过拟合是泛化的反面,好比乡下快活的刘姥姥进了大观园会各种不适应,但受过良好教育的林黛玉进贾府就不会大惊小怪。实际训练中, 降低过拟合的办法一般如下:
正则化(Regularization)
L2正则化:目标函数中增加所有权重w参数的平方之和, 逼迫所有w尽可能趋向零但不为零. 因为过拟合的时候, 拟合函数需要顾忌每一个点, 最终形成的拟合函数波动很大, 在某些很小的区间里, 函数值的变化很剧烈, 也就是某些w非常大. 为此, L2正则化的加入就惩罚了权重变大的趋势.
L1正则化:目标函数中增加所有权重w参数的绝对值之和, 逼迫更多w为零(也就是变稀疏. L2因为其导数也趋0, 奔向零的速度不如L1给力了). 大家对稀疏规则化趋之若鹜的一个关键原因在于它能实现特征的自动选择。一般来说,xi的大部分元素(也就是特征)都是和最终的输出yi没有关系或者不提供任何信息的,在最小化目标函数的时候考虑xi这些额外的特征,虽然可以获得更小的训练误差,但在预测新的样本时,这些没用的特征权重反而会被考虑,从而干扰了对正确yi的预测。稀疏规则化算子的引入就是为了完成特征自动选择的光荣使命,它会学习地去掉这些无用的特征,也就是把这些特征对应的权重置为0。
随机失活(dropout)
在训练的运行的时候,让神经元以超参数p的概率被**(也就是1-p的概率被设置为0), 每个w因此随机参与, 使得任意w都不是不可或缺的, 效果类似于数量巨大的模型集成。
逐层归一化(batch normalization)
这个方法给每层的输出都做一次归一化(网络上相当于加了一个线性变换层), 使得下一层的输入接近高斯分布. 这个方法相当于下一层的w训练时避免了其输入以偏概全, 因而泛化效果非常好. 
提前终止(early stopping)
理论上可能的局部极小值数量随参数的数量呈指数增长, 到达某个精确的最小值是不良泛化的一个来源. 实践表明, 追求细粒度极小值具有较高的泛化误差。这是直观的,因为我们通常会希望我们的误差函数是平滑的, 精确的最小值处所见相应误差曲面具有高度不规则性, 而我们的泛化要求减少精确度去获得平滑最小值, 所以很多训练方法都提出了提前终止策略. 典型的方法是根据交叉叉验证提前终止: 若每次训练前, 将训练数据划分为若干份, 取一份为测试集, 其他为训练集, 每次训练完立即拿此次选中的测试集自测. 因为每份都有一次机会当测试集, 所以此方法称之为交叉验证. 交叉验证的错误率最小时可以认为泛化性能最好, 这时候训练错误率虽然还在继续下降, 但也得终止继续训练了.  
LR和SVM的联系与区别。机器学习 ML模型 中
@朝阳在望,联系: 
1、LR和SVM都可以处理分类问题,且一般都用于处理线性二分类问题(在改进的情况下可以处理多分类问题) 
2、两个方法都可以增加不同的正则化项,如l1、l2等等。所以在很多实验中,两种算法的结果是很接近的。 
区别: 
1、LR是参数模型,SVM是非参数模型。 
2、从目标函数来看,区别在于逻辑回归采用的是logistical loss,SVM采用的是hinge loss,这两个损失函数的目的都是增加对分类影响较大的数据点的权重,减少与分类关系较小的数据点的权重。 
3、SVM的处理方法是只考虑support vectors,也就是和分类最相关的少数点,去学习分类器。而逻辑回归通过非线性映射,大大减小了离分类平面较远的点的权重,相对提升了与分类最相关的数据点的权重。 
4、逻辑回归相对来说模型更简单,好理解,特别是大规模线性分类时比较方便。而SVM的理解和优化相对来说复杂一些,SVM转化为对偶问题后,分类只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算。 
5、logic 能做的 svm能做,但可能在准确率上有问题,svm能做的logic有的做不了。
来源:http://blog.csdn.net/timcompp/article/details/62237986说说你知道的核函数。机器学习 ML基础 易

通常人们会从一些常用的核函数中选择(根据问题和数据的不同,选择不同的参数,实际上就是得到了不同的核函数),例如:

  • 多项式核,显然刚才我们举的例子是这里多项式核的一个特例(R = 1,d = 2。虽然比较麻烦,而且没有必要,不过这个核所对应的映射实际上是可以写出来的,该空间的维度是***BAT机器学习面试1000题系列,其中 ***BAT机器学习面试1000题系列 是原始空间的维度。
  • 高斯核***BAT机器学习面试1000题系列,这个核就是最开始提到过的会将原始空间映射为无穷维空间的那个家伙。不过,如果***BAT机器学习面试1000题系列选得很大的话,高次特征上的权重实际上衰减得非常快,所以实际上(数值上近似一下)相当于一个低维的子空间;反过来,如果***BAT机器学习面试1000题系列选得很小,则可以将任意的数据映射为线性可分——当然,这并不一定是好事,因为随之而来的可能是非常严重的过拟合问题。不过,总的来说,通过调控参数***BAT机器学习面试1000题系列,高斯核实际上具有相当高的灵活性,也是使用最广泛的核函数之一。下图所示的例子便是把低维线性不可分的数据通过高斯核函数映射到了高维空间:
    ***BAT机器学习面试1000题系列
  • 线性核***BAT机器学习面试1000题系列,这实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了(意思是说,咱们有的时候,写代码,或写公式的时候,只要写个模板或通用表达式,然后再代入不同的核,便可以了,于此,便在形式上统一了起来,不用再分别写一个线性的,和一个非线性的)
LR与线性回归的区别与联系。机器学习  ML模型 中等
@AntZ: LR工业上一般指Logistic Regression(逻辑回归)而不是Linear Regression(线性回归). LR在线性回归的实数范围输出值上施加sigmoid函数将值收敛到0~1范围, 其目标函数也因此从差平方和函数变为对数损失函数, 以提供最优化所需导数(sigmoid函数是softmax函数的二元特例, 其导数均为函数值的f*(1-f)形式)。请注意, LR往往是解决二元0/1分类问题的, 只是它和线性回归耦合太紧, 不自觉也冠了个回归的名字(马甲无处不在). 若要求多元分类,就要把sigmoid换成大名鼎鼎的softmax了。
@nishizhen:个人感觉逻辑回归和线性回归首先都是广义的线性回归,
其次经典线性模型的优化目标函数是最小二乘,而逻辑回归则是似然函数,
另外线性回归在整个实数域范围内进行预测,敏感度一致,而分类范围,需要在[0,1]。逻辑回归就是一种减小预测范围,将预测值限定为[0,1]间的一种回归模型,因而对于这类问题来说,逻辑回归的鲁棒性比线性回归的要好。
@乖乖癞皮狗:逻辑回归的模型本质上是一个线性回归模型,逻辑回归都是以线性回归为理论支持的。但线性回归模型无法做到sigmoid的非线性形式,sigmoid可以轻松处理0/1分类问题。
请问(决策树、Random Forest、Booting、Adaboot)GBDT和XGBoost的区别是什么?机器学习 ML模型 难
@AntZ
集成学习的集成对象是学习器. Bagging和Boosting属于集成学习的两类方法. Bagging方法有放回地采样同数量样本训练每个学习器, 然后再一起集成(简单投票); Boosting方法使用全部样本(可调权重)依次训练每个学习器, 迭代集成(平滑加权).
决策树属于最常用的学习器, 其学习过程是从根建立树, 也就是如何决策叶子节点分裂. ID3/C4.5决策树用信息熵计算最优分裂, CART决策树用基尼指数计算最优分裂, xgboost决策树使用二阶泰勒展开系数计算最优分裂.
下面所提到的学习器都是决策树:
Bagging方法: 
    学习器间不存在强依赖关系, 学习器可并行训练生成, 集成方式一般为投票;
    Random Forest属于Bagging的代表, 放回抽样, 每个学习器随机选择部分特征去优化;
Boosting方法: 
   学习器之间存在强依赖关系、必须串行生成, 集成方式为加权和;
    Adaboost属于Boosting, 采用指数损失函数替代原本分类任务的0/1损失函数;
    GBDT属于Boosting的优秀代表, 对函数残差近似值进行梯度下降, 用CART回归树做学习器, 集成为回归模型;
    xgboost属于Boosting的集大成者, 对函数残差近似值进行梯度下降, 迭代时利用了二阶梯度信息, 集成模型可分类也可回归. 由于它可在特征粒度上并行计算, 结构风险和工程实现都做了很多优化, 泛化, 性能和扩展性都比GBDT要好。
关于决策树,这里有篇《决策树算法》。而随机森林Random Forest是一个包含多个决策树的分类器。至于AdaBoost,则是英文"Adaptive Boosting"(自适应增强)的缩写,关于AdaBoost可以看下这篇文章《Adaboost 算法的原理与推导》。GBDT(Gradient Boosting Decision Tree),即梯度上升决策树算法,相当于融合决策树和梯度上升boosting算法。
@Xijun LI:xgboost类似于gbdt的优化版,不论是精度还是效率上都有了提升。与gbdt相比,具体的优点有:
1.损失函数是用泰勒展式二项逼近,而不是像gbdt里的就是一阶导数
2.对树的结构进行了正则化约束,防止模型过度复杂,降低了过拟合的可能性
3.节点分裂的方式不同,gbdt是用的gini系数,xgboost是经过优化推导后的
更多详见:https://xijunlee.github.io/2017/06/03/%E9%9B%86%E6%88%90%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93/为什么xgboost要用泰勒展开,优势在哪里?机器学习 ML模型 难
@AntZ:xgboost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了xgboost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。
xgboost如何寻找最优特征?是又放回还是无放回的呢?机器学习 ML模型 难
@AntZ:xgboost在训练的过程中给出各个特征的增益评分,最大增益的特征会被选出来作为分裂依据, 从而记忆了每个特征对在模型训练时的重要性 -- 从根到叶子中间节点涉及某特征的次数作为该特征重要性排序.
xgboost属于boosting集成学习方法, 样本是不放回的, 因而每轮计算样本不重复. 另一方面, xgboost支持子采样, 也就是每轮计算可以不使用全部样本, 以减少过拟合. 进一步地, xgboost 还有列采样, 每轮计算按百分比随机采样一部分特征, 既提高计算速度又减少过拟合。
谈谈判别式模型和生成式模型?机器学习 ML基础 易
判别方法:由数据直接学习决策函数 Y = f(X),或者由条件分布概率 P(Y|X)作为预测模型,即判别模型。
生成方法:由数据学习联合概率密度分布函数 P(X,Y),然后求出条件概率分布P(Y|X)作为预测的模型,即生成模型。
由生成模型可以得到判别模型,但由判别模型得不到生成模型。
常见的判别模型有:K近邻、SVM、决策树、感知机、线性判别分析(LDA)、线性回归、传统的神经网络、逻辑斯蒂回归、boosting、条件随机场
常见的生成模型有:朴素贝叶斯、隐马尔可夫模型、高斯混合模型、文档主题生成模型(LDA)、限制玻尔兹曼机L1和L2的区别。机器学习 ML基础 易
L1范数(L1 norm)是指向量中各个元素绝对值之和,也有个美称叫“稀疏规则算子”(Lasso regularization)。 
比如 向量A=[1,-1,3], 那么A的L1范数为 |1|+|-1|+|3|.
简单总结一下就是: 
L1范数: 为x向量各个元素绝对值之和。 
L2范数: 为x向量各个元素平方和的1/2次方,L2范数又称Euclidean范数或者Frobenius范数 
Lp范数: 为x向量各个元素绝对值p次方和的1/p次方.
在支持向量机学习过程中,L1范数实际是一种对于成本函数求解最优的过程,因此,L1范数正则化通过向成本函数中添加L1范数,使得学习得到的结果满足稀疏化,从而方便人类提取特征。 
L1范数可以使权值稀疏,方便特征提取。 
L2范数可以防止过拟合,提升模型的泛化能力。
@AntZ: L1和L2的差别,为什么一个让绝对值最小,一个让平方最小,会有那么大的差别呢?看导数一个是1一个是w便知, 在靠进零附近, L1以匀速下降到零, 而L2则完全停下来了. 这说明L1是将不重要的特征(或者说, 重要性不在一个数量级上)尽快剔除, L2则是把特征贡献尽量压缩最小但不至于为零. 两者一起作用, 就是把重要性在一个数量级(重要性最高的)的那些特征一起平等共事(简言之, 不养闲人也不要超人)。
L1和L2正则先验分别服从什么分布。机器学习 ML基础 易
@齐同学:面试中遇到的,L1和L2正则先验分别服从什么分布,L1是拉普拉斯分布,L2是高斯分布。
@AntZ: 先验就是优化的起跑线, 有先验的好处就是可以在较小的数据集中有良好的泛化性能,当然这是在先验分布是接近真实分布的情况下得到的了,从信息论的角度看,向系统加入了正确先验这个信息,肯定会提高系统的性能。
对参数引入高斯正态先验分布相当于L2正则化, 这个大家都熟悉:
***BAT机器学习面试1000题系列***BAT机器学习面试1000题系列
对参数引入拉普拉斯先验等价于 L1正则化, 如下图:
***BAT机器学习面试1000题系列***BAT机器学习面试1000题系列
从上面两图可以看出, L2先验趋向零周围, L1先验趋向零本身。
 CNN最成功的应用是在CV,那为什么NLP和Speech的很多问题也可以用CNN解出来?为什么AlphaGo里也用了CNN?这几个不相关的问题的相似性在哪里?CNN通过什么手段抓住了这个共性?深度学习 DL应用 难
@许韩,来源:https://zhuanlan.zhihu.com/p/25005808
Deep Learning -Yann LeCun, Yoshua Bengio & Geoffrey Hinton
Learn TensorFlow and deep learning, without a Ph.D.
The Unreasonable Effectiveness of Deep Learning -LeCun 16 NIPS Keynote
以上几个不相关问题的相关性在于,都存在局部与整体的关系,由低层次的特征经过组合,组成高层次的特征,并且得到不同特征之间的空间相关性。如下图:低层次的直线/曲线等特征,组合成为不同的形状,最后得到汽车的表示。***BAT机器学习面试1000题系列
CNN抓住此共性的手段主要有四个:局部连接/权值共享/池化操作/多层次结构。
局部连接使网络可以提取数据的局部特征;权值共享大大降低了网络的训练难度,一个Filter只提取一个特征,在整个图片(或者语音/文本) 中进行卷积;池化操作与多层次结构一起,实现了数据的降维,将低层次的局部特征组合成为较高层次的特征,从而对整个图片进行表示。如下图:
***BAT机器学习面试1000题系列
上图中,如果每一个点的处理使用相同的Filter,则为全卷积,如果使用不同的Filter,则为Local-Conv。
另,关于CNN,这里有篇文章《 CNN笔记:通俗理解卷积神经网络》。
   说一下Adaboost,权值更新公式。当弱分类器是Gm时,每个样本的的权重是w1,w2...,请写出最终的决策公式。机器学习 ML模型 难

给定一个训练数据集T={(x1,y1), (x2,y2)…(xN,yN)},其中实例***BAT机器学习面试1000题系列,而实例空间***BAT机器学习面试1000题系列,yi属于标记集合{-1,+1},Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器,然后将这些弱分类器组合成一个强分类器。

    Adaboost的算法流程如下:

  • 步骤1. 首先,初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权值:1/N。

***BAT机器学习面试1000题系列

  • 步骤2. 进行多轮迭代,用m = 1,2, ..., M表示迭代的第多少轮

a. 使用具有权值分布Dm的训练数据集学习,得到基本分类器(选取让误差率最低的阈值来设计基本分类器):

***BAT机器学习面试1000题系列

b. 计算Gm(x)在训练数据集上的分类误差率
***BAT机器学习面试1000题系列
由上述式子可知,Gm(x)在训练数据集上的误差率em就是被Gm(x)误分类样本的权值之和
c. 计算Gm(x)的系数,am表示Gm(x)在最终分类器中的重要程度(目的:得到基本分类器在最终分类器中所占的权重):
***BAT机器学习面试1000题系列
由上述式子可知,em <= 1/2时,am >= 0,且am随着em的减小而增大,意味着分类误差率越小的基本分类器在最终分类器中的作用越大。
d. 更新训练数据集的权值分布(目的:得到样本的新的权值分布),用于下一轮迭代

***BAT机器学习面试1000题系列

使得被基本分类器Gm(x)误分类样本的权值增大,而被正确分类样本的权值减小。就这样,通过这样的方式,AdaBoost方法能“重点关注”或“聚焦于”那些较难分的样本上。

    其中,Zm是规范化因子,使得Dm+1成为一个概率分布:

***BAT机器学习面试1000题系列

  • 步骤3. 组合各个弱分类器

***BAT机器学习面试1000题系列

从而得到最终分类器,如下:

***BAT机器学习面试1000题系列
更多请查看此文:《Adaboost 算法的原理与推导》。

LSTM结构推导,为什么比RNN好?深度学习 DL模型 难
推导forget gate,input gate,cell state, hidden information等的变化;因为LSTM有进有出且当前的cell informaton是通过input gate控制之后叠加的,RNN是叠乘,因此LSTM可以防止梯度消失或者爆炸

经常在网上搜索东西的朋友知道,当你不小心输入一个不存在的单词时,搜索引擎会提示你是不是要输入某一个正确的单词,比如当你在Google中输入“Julw”时,系统会猜测你的意图:是不是要搜索“July”,如下图所示:

***BAT机器学习面试1000题系列

    这叫做拼写检查。根据谷歌一员工写的文章显示,Google的拼写检查基于贝叶斯方法。请说说的你的理解,具体Google是怎么利用贝叶斯方法,实现"拼写检查"的功能。机器学习 ML应用 难

    用户输入一个单词时,可能拼写正确,也可能拼写错误。如果把拼写正确的情况记做c(代表correct),拼写错误的情况记做w(代表wrong),那么"拼写检查"要做的事情就是:在发生w的情况下,试图推断出c。换言之:已知w,然后在若干个备选方案中,找出可能性最大的那个c,也就是求***BAT机器学习面试1000题系列的最大值。
    而根据贝叶斯定理,有:

  ***BAT机器学习面试1000题系列

    由于对于所有备选的c来说,对应的都是同一个w,所以它们的P(w)是相同的,因此我们只要最大化

***BAT机器学习面试1000题系列

    即可。其中:

  • P(c)表示某个正确的词的出现"概率",它可以用"频率"代替。如果我们有一个足够大的文本库,那么这个文本库中每个单词的出现频率,就相当于它的发生概率。某个词的出现频率越高,P(c)就越大。比如在你输入一个错误的词“Julw”时,系统更倾向于去猜测你可能想输入的词是“July”,而不是“Jult”,因为“July”更常见。
  • P(w|c)表示在试图拼写c的情况下,出现拼写错误w的概率。为了简化问题,假定两个单词在字形上越接近,就有越可能拼错,P(w|c)就越大。举例来说,相差一个字母的拼法,就比相差两个字母的拼法,发生概率更高。你想拼写单词July,那么错误拼成Julw(相差一个字母)的可能性,就比拼成Jullw高(相差两个字母)。值得一提的是,一般把这种问题称为“编辑距离”,参见博客中的这篇文章。
    所以,我们比较所有拼写相近的词在文本库中的出现频率,再从中挑出出现频率最高的一个,即是用户最想输入的那个词。具体的计算过程及此方法的缺陷请参见这里

为什么朴素贝叶斯如此“朴素”?机器学习 ML模型 易
因为它假定所有的特征在数据集中的作用是同样重要和独立的。正如我们所知,这个假设在现实世界中是很不真实的,因此,说朴素贝叶斯真的很“朴素”。
@AntZ: 朴素贝叶斯模型(Naive Bayesian Model)的朴素(Naive)的含义是"很简单很天真"地假设样本特征彼此独立. 这个假设现实中基本上不存在, 但特征相关性很小的实际情况还是很多的, 所以这个模型仍然能够工作得很好。

请大致对比下plsa和LDA的区别。机器学习 ML模型 中等

  • pLSA中,主题分布和词分布确定后,以一定的概率(***BAT机器学习面试1000题系列***BAT机器学习面试1000题系列)分别选取具体的主题和词项,生成好文档。而后根据生成好的文档反推其主题分布、词分布时,最终用EM算法(极大似然估计思想)求解出了两个未知但固定的参数的值:***BAT机器学习面试1000题系列(由***BAT机器学习面试1000题系列转换而来)和***BAT机器学习面试1000题系列(由***BAT机器学习面试1000题系列转换而来)。
    • 文档d产生主题z的概率,主题z产生单词w的概率都是两个固定的值。
      • 举个文档d产生主题z的例子。给定一篇文档d,主题分布是一定的,比如{ P(zi|d), i = 1,2,3 }可能就是{0.4,0.5,0.1},表示z1、z2、z3,这3个主题被文档d选中的概率都是个固定的值:P(z1|d) = 0.4、P(z2|d) = 0.5、P(z3|d) = 0.1,如下图所示(图截取自沈博PPT上):
***BAT机器学习面试1000题系列
  • 但在贝叶斯框架下的LDA中,我们不再认为主题分布(各个主题在文档中出现的概率分布)和词分布(各个词语在某个主题下出现的概率分布)是唯一确定的(而是随机变量),而是有很多种可能。但一篇文档总得对应一个主题分布和一个词分布吧,怎么办呢?LDA为它们弄了两个Dirichlet先验参数,这个Dirichlet先验为某篇文档随机抽取出某个主题分布和词分布。
    • 文档d产生主题z(准确的说,其实是Dirichlet先验为文档d生成主题分布Θ,然后根据主题分布Θ产生主题z)的概率,主题z产生单词w的概率都不再是某两个确定的值,而是随机变量
      • 还是再次举下文档d具体产生主题z的例子。给定一篇文档d,现在有多个主题z1、z2、z3,它们的主题分布{ P(zi|d), i = 1,2,3 }可能是{0.4,0.5,0.1},也可能是{0.2,0.2,0.6},即这些主题被d选中的概率都不再认为是确定的值,可能是P(z1|d) = 0.4、P(z2|d) = 0.5、P(z3|d) = 0.1,也有可能是P(z1|d) = 0.2、P(z2|d) = 0.2、P(z3|d) = 0.6等等,而主题分布到底是哪个取值集合我们不确定(为什么?这就是贝叶斯派的核心思想,把未知参数当作是随机变量,不再认为是某一个确定的值),但其先验分布是dirichlet 分布,所以可以从无穷多个主题分布中按照dirichlet 先验随机抽取出某个主题分布出来。如下图所示(图截取自沈博PPT上):

***BAT机器学习面试1000题系列

    换言之,LDA在pLSA的基础上给这两参数***BAT机器学习面试1000题系列***BAT机器学习面试1000题系列加了两个先验分布的参数(贝叶斯化):一个主题分布的先验分布Dirichlet分布***BAT机器学习面试1000题系列,和一个词语分布的先验分布Dirichlet分布***BAT机器学习面试1000题系列
    综上,LDA真的只是pLSA的贝叶斯版本,文档生成后,两者都要根据文档去推断其主题分布和词语分布,只是用的参数推断方法不同,在pLSA中用极大似然估计的思想去推断两未知的固定参数,而LDA则把这两参数弄成随机变量,且加入dirichlet先验。
更多请参见:《通俗理解LDA主题模型》。

请简要说说EM算法。机器学习 ML模型 中等

@tornadomeet,本题解析来源:http://www.cnblogs.com/tornadomeet/p/3395593.html
有时候因为样本的产生和隐含变量有关(隐含变量是不能观察的),而求模型的参数时一般采用最大似然估计,由于含有了隐含变量,所以对似然函数参数求导是求不出来的,这时可以采用EM算法来求模型的参数的(对应模型参数个数可能有多个),EM算法一般分为2步:

  E步:选取一组参数,求出在该参数下隐含变量的条件概率值;

  M步:结合E步求出的隐含变量条件概率,求出似然函数下界函数(本质上是某个期望函数)的最大值。

  重复上面2步直至收敛。

  公式如下所示:

   ***BAT机器学习面试1000题系列

  M步公式中下界函数的推导过程:

   ***BAT机器学习面试1000题系列

  EM算法一个常见的例子就是GMM模型,每个样本都有可能由k个高斯产生,只不过由每个高斯产生的概率不同而已,因此每个样本都有对应的高斯分布(k个中的某一个),此时的隐含变量就是每个样本对应的某个高斯分布。

  GMM的E步公式如下(计算每个样本对应每个高斯的概率):

   ***BAT机器学习面试1000题系列

  更具体的计算公式为:

  ***BAT机器学习面试1000题系列

  M步公式如下(计算每个高斯的比重,均值,方差这3个参数):

   ***BAT机器学习面试1000题系列

KNN中的K如何选取的?机器学习 ML模型 易
关于什么是KNN,可以查看此文:《从K近邻算法、距离度量谈到KD树、SIFT+BBF算法》。KNN中的K值选取对K近邻算法的结果会产生重大影响。如李航博士的一书「统计学习方法」上所说:

  1. 如果选择较小的K值,就相当于用较小的领域中的训练实例进行预测,“学习”近似误差会减小,只有与输入实例较近或相似的训练实例才会对预测结果起作用,与此同时带来的问题是“学习”的估计误差会增大,换句话说,K值的减小就意味着整体模型变得复杂,容易发生过拟合;
  2. 如果选择较大的K值,就相当于用较大领域中的训练实例进行预测,其优点是可以减少学习的估计误差,但缺点是学习的近似误差会增大。这时候,与输入实例较远(不相似的)训练实例也会对预测器作用,使预测发生错误,且K值的增大就意味着整体的模型变得简单。
  3. K=N,则完全不足取,因为此时无论输入实例是什么,都只是简单的预测它属于在训练实例中最多的累,模型过于简单,忽略了训练实例中大量有用信息。
    在实际应用中,K值一般取一个比较小的数值,例如采用交叉验证法(简单来说,就是一部分样本做训练集,一部分做测试集)来选择最优的K值。

防止过拟合的方法。机器学习 ML基础 易
  过拟合的原因是算法的学习能力过强;一些假设条件(如样本独立同分布)可能是不成立的;训练样本过少不能对整个空间进行分布估计。 
  处理方法:

  • 早停止:如在训练中多次迭代后发现模型性能没有显著提高就停止训练
  • 数据集扩增:原有数据增加、原有数据加随机噪声、重采样
  • 正则化
  • 交叉验证
  • 特征选择/特征降维
  • 创建一个验证集是最基本的防止过拟合的方法。我们最终训练得到的模型目标是要在验证集上面有好的表现,而不训练集。
  • 正则化可以限制模型的复杂度。
机器学习中,为何要经常对数据做归一化。机器学习 ML基础 中等

@zhanlijun,本题解析来源:http://www.cnblogs.com/LBSer/p/4440590.html

    机器学习模型被互联网行业广泛应用,如排序(参见:排序学习实践)、推荐、反作弊、定位(参见:基于朴素贝叶斯的定位算法)等。一般做机器学习应用的时候大部分时间是花费在特征处理上,其中很关键的一步就是对特征数据进行归一化,为什么要归一化呢?很多同学并未搞清楚,*给出的解释:1)归一化后加快了梯度下降求最优解的速度;2)归一化有可能提高精度。下面再简单扩展解释下这两点。

1 归一化为什么能提高梯度下降法求解最优解的速度?

      斯坦福机器学习视频做了很好的解释:https://class.coursera.org/ml-003/lecture/21

      如下图所示,蓝色的圈圈图代表的是两个特征的等高线。其中左图两个特征X1和X2的区间相差非常大,X1区间是[0,2000],X2区间是[1,5],其所形成的等高线非常尖。当使用梯度下降法寻求最优解时,很有可能走“之字型”路线(垂直等高线走),从而导致需要迭代很多次才能收敛;

      而右图对两个原始特征进行了归一化,其对应的等高线显得很圆,在梯度下降进行求解时能较快的收敛。

      因此如果机器学习模型使用梯度下降法求最优解时,归一化往往非常有必要,否则很难收敛甚至不能收敛。

***BAT机器学习面试1000题系列

2 归一化有可能提高精度

     一些分类器需要计算样本之间的距离(如欧氏距离),例如KNN。如果一个特征值域范围非常大,那么距离计算就主要取决于这个特征,从而与实际情况相悖(比如这时实际情况是值域范围小的特征更重要)。

3 归一化的类型

1)线性归一化

      这种归一化方法比较适用在数值比较集中的情况。这种方法有个缺陷,如果max和min不稳定,很容易使得归一化结果不稳定,使得后续使用效果也不稳定。实际使用中可以用经验常量值来替代max和min。

2)标准差标准化

  经过处理的数据符合标准正态分布,即均值为0,标准差为1,其转化函数为:

  其中μ为所有样本数据的均值,σ为所有样本数据的标准差。

3)非线性归一化

     经常用在数据分化比较大的场景,有些数值很大,有些很小。通过一些数学函数,将原始值进行映射。该方法包括 log、指数,正切等。需要根据数据分布的情况,决定非线性函数的曲线,比如log(V, 2)还是log(V, 10)等。

谈谈深度学习中的归一化问题。深度学习 DL基础 易
***BAT机器学习面试1000题系列
详情参见此视频:《深度学习中的归一化》。

哪些机器学习算法不需要做归一化处理?机器学习 ML基础 易
概率模型不需要归一化,因为它们不关心变量的值,而是关心变量的分布和变量之间的条件概率,如决策树、rf。而像adaboost、svm、lr、KNN、KMeans之类的最优化问题就需要归一化。
@管博士:我理解归一化和标准化主要是为了使计算更方便 比如两个变量的量纲不同 可能一个的数值远大于另一个那么他们同时作为变量的时候 可能会造成数值计算的问题,比如说求矩阵的逆可能很不精确 或者梯度下降法的收敛比较困难,还有如果需要计算欧式距离的话可能 量纲也需要调整 所以我估计lr 和 knn 保准话一下应该有好处。至于其他的算法 我也觉得如果变量量纲差距很大的话 先标准化一下会有好处。
@寒小阳:一般我习惯说树形模型,这里说的概率模型可能是差不多的意思。

对于树形结构为什么不需要归一化?机器学习 ML基础 易
答:数值缩放,不影响分裂点位置。因为第一步都是按照特征值进行排序的,排序的顺序不变,那么所属的分支以及分裂点就不会有不同。对于线性模型,比如说LR,我有两个特征,一个是(0,1)的,一个是(0,10000)的,这样运用梯度下降时候,损失等高线是一个椭圆的形状,这样我想迭代到最优点,就需要很多次迭代,但是如果进行了归一化,那么等高线就是圆形的,那么SGD就会往原点迭代,需要的迭代次数较少。
另外,注意树模型是不能进行梯度下降的,因为树模型是阶跃的,阶跃点是不可导的,并且求导没意义,所以树模型(回归树)寻找最优点事通过寻找最优分裂点完成的。

数据归一化(或者标准化,注意归一化和标准化不同)的原因。机器学习 ML基础 易
@我愛大泡泡,来源:http://blog.csdn.net/woaidapaopao/article/details/77806273
  要强调:能不归一化最好不归一化,之所以进行数据归一化是因为各维度的量纲不相同。而且需要看情况进行归一化。

  • 有些模型在各维度进行了不均匀的伸缩后,最优解与原来不等价(如SVM)需要归一化。
  • 有些模型伸缩有与原来等价,如:LR则不用归一化,但是实际中往往通过迭代求解模型参数,如果目标函数太扁(想象一下很扁的高斯模型)迭代算法会发生不收敛的情况,所以最坏进行数据归一化。

补充:其实本质是由于loss函数不同造成的,SVM用了欧拉距离,如果一个特征很大就会把其他的维度dominated。而LR可以通过权重调整使得损失函数不变。

请简要说说一个完整机器学习项目的流程。机器学习 ML应用 中
@寒小阳、龙心尘
1 抽象成数学问题
明确问题是进行机器学习的第一步。机器学习的训练过程通常都是一件非常耗时的事情,胡乱尝试时间成本是非常高的。
这里的抽象成数学问题,指的我们明确我们可以获得什么样的数据,目标是一个分类还是回归或者是聚类的问题,如果都不是的话,如果划归为其中的某类问题。

2 获取数据
数据决定了机器学习结果的上限,而算法只是尽可能逼近这个上限。
数据要有代表性,否则必然会过拟合。
而且对于分类问题,数据偏斜不能过于严重,不同类别的数据数量不要有数个数量级的差距。
而且还要对数据的量级有一个评估,多少个样本,多少个特征,可以估算出其对内存的消耗程度,判断训练过程中内存是否能够放得下。如果放不下就得考虑改进算法或者使用一些降维的技巧了。如果数据量实在太大,那就要考虑分布式了。

3 特征预处理与特征选择
良好的数据要能够提取出良好的特征才能真正发挥效力。
特征预处理、数据清洗是很关键的步骤,往往能够使得算法的效果和性能得到显著提高。归一化、离散化、因子化、缺失值处理、去除共线性等,数据挖掘过程中很多时间就花在它们上面。这些工作简单可复制,收益稳定可预期,是机器学习的基础必备步骤。
筛选出显著特征、摒弃非显著特征,需要机器学习工程师反复理解业务。这对很多结果有决定性的影响。特征选择好了,非常简单的算法也能得出良好、稳定的结果。这需要运用特征有效性分析的相关技术,如相关系数、卡方检验、平均互信息、条件熵、后验概率、逻辑回归权重等方法。

4 训练模型与调优
直到这一步才用到我们上面说的算法进行训练。现在很多算法都能够封装成黑盒供人使用。但是真正考验水平的是调整这些算法的(超)参数,使得结果变得更加优良。这需要我们对算法的原理有深入的理解。理解越深入,就越能发现问题的症结,提出良好的调优方案。

5 模型诊断
如何确定模型调优的方向与思路呢?这就需要对模型进行诊断的技术。
过拟合、欠拟合 判断是模型诊断中至关重要的一步。常见的方法如交叉验证,绘制学习曲线等。过拟合的基本调优思路是增加数据量,降低模型复杂度。欠拟合的基本调优思路是提高特征数量和质量,增加模型复杂度。
误差分析 也是机器学习至关重要的步骤。通过观察误差样本,全面分析误差产生误差的原因:是参数的问题还是算法选择的问题,是特征的问题还是数据本身的问题……
诊断后的模型需要进行调优,调优后的新模型需要重新进行诊断,这是一个反复迭代不断逼近的过程,需要不断地尝试, 进而达到最优状态。

6 模型融合
一般来说,模型融合后都能使得效果有一定提升。而且效果很好。
工程上,主要提升算法准确度的方法是分别在模型的前端(特征清洗和预处理,不同的采样模式)与后端(模型融合)上下功夫。因为他们比较标准可复制,效果比较稳定。而直接调参的工作不会很多,毕竟大量数据训练起来太慢了,而且效果难以保证。

7 上线运行
这一部分内容主要跟工程实现的相关性比较大。工程上是结果导向,模型在线上运行的效果直接决定模型的成败。 不单纯包括其准确程度、误差等情况,还包括其运行的速度(时间复杂度)、资源消耗程度(空间复杂度)、稳定性是否可接受。
这些工作流程主要是工程实践上总结出的一些经验。并不是每个项目都包含完整的一个流程。这里的部分只是一个指导性的说明,只有大家自己多实践,多积累项目经验,才会有自己更深刻的认识。

故,基于此,七月在线每一期ML算法班都特此增加特征工程、模型调优等相关课。比如,这里有个公开课视频《特征处理与特征选择》。

逻辑斯特回归为什么要对特征进行离散化。机器学习 ML模型 中等
@严林,本题解析来源:https://www.zhihu.com/question/31989952

在工业界,很少直接将连续值作为逻辑回归模型的特征输入,而是将连续特征离散化为一系列0、1特征交给逻辑回归模型,这样做的优势有以下几点:

0. 离散特征的增加和减少都很容易,易于模型的快速迭代;

1. 稀疏向量内积乘法运算速度快,计算结果方便存储,容易扩展;

2. 离散化后的特征对异常数据有很强的鲁棒性:比如一个特征是年龄>30是1,否则0。如果特征没有离散化,一个异常数据“年龄300岁”会给模型造成很大的干扰;

3. 逻辑回归属于广义线性模型,表达能力受限;单变量离散化为N个后,每个变量有单独的权重,相当于为模型引入了非线性,能够提升模型表达能力,加大拟合;

4. 离散化后可以进行特征交叉,由M+N个变量变为M*N个变量,进一步引入非线性,提升表达能力;

5. 特征离散化后,模型会更稳定,比如如果对用户年龄离散化,20-30作为一个区间,不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反,所以怎么划分区间是门学问;

6. 特征离散化以后,起到了简化了逻辑回归模型的作用,降低了模型过拟合的风险。

李沐曾经说过:模型是使用离散特征还是连续特征,其实是一个“海量离散特征+简单模型” 同 “少量连续特征+复杂模型”的权衡。既可以离散化用线性模型,也可以用连续特征加深度学习。就看是喜欢折腾特征还是折腾模型了。通常来说,前者容易,而且可以n个人一起并行做,有成功经验;后者目前看很赞,能走多远还须拭目以待。

new 和 malloc的区别。编程开发 C/C++ 易
@Sommer_Xia,来源:http://blog.csdn.net/shymi1991/article/details/39432775
1. malloc与free是C++/C语言的标准库函数,new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。
2. 对于非内部数据类型的对象而言,光用maloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数,对象在消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符,不在编译器控制权限之内,不能够把执行构造函数和析构函数的任务强加于malloc/free。
3. 因此C++语言需要一个能完成动态内存分配和初始化工作的运算符new,以一个能完成清理与释放内存工作的运算符delete。注意new/delete不是库函数。
4. C++程序经常要调用C函数,而C程序只能用malloc/free管理动态内存

hash 冲突及解决办法。数据结构/算法 中等
@Sommer_Xia,来源:http://blog.csdn.net/shymi1991/article/details/39432775
关键字值不同的元素可能会映象到哈希表的同一地址上就会发生哈希冲突。解决办法:
1)开放定址法:当冲突发生时,使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找,直到找到给定 的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探查到开放的 地址则表明表中无待查的关键字,即查找失败。
2) 再哈希法:同时构造多个不同的哈希函数。
3)链地址法:将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
4)建立公共溢出区:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。

下列哪个不属于CRF模型对于HMM和MEMM模型的优势(B ) 机器学习 ML模型 中等
  A. 特征灵活  B. 速度快  C. 可容纳较多上下文信息  D. 全局最优
首先,CRF,HMM(隐马模型),MEMM(最大熵隐马模型)都常用来做序列标注的建模.
隐马模型一个最大的缺点就是由于其输出独立性假设,导致其不能考虑上下文的特征,限制了特征的选择
最大熵隐马模型则解决了隐马的问题,可以任意选择特征,但由于其在每一节点都要进行归一化,所以只能找到局部的最优值,同时也带来了标记偏见的问题,即凡是训练语料中未出现的情况全都忽略掉
条件随机场则很好的解决了这一问题,他并不在每一个节点进行归一化,而是所有特征进行全局归一化,因此可以求得全局的最优值。
此外《机器学习工程师第八期》里有讲概率图模型。

什么是熵。机器学习 ML基础 易

    从名字上来看,熵给人一种很玄乎,不知道是啥的感觉。其实,熵的定义很简单,即用来表示随机变量的不确定性。之所以给人玄乎的感觉,大概是因为为何要取这样的名字,以及怎么用。

    熵的概念最早起源于物理学,用于度量一个热力学系统的无序程度。在信息论里面,熵是对不确定性的测量。

熵的引入

    事实上,熵的英文原文为entropy,最初由德国物理学家鲁道夫·克劳修斯提出,其表达式为:

***BAT机器学习面试1000题系列

    它表示一个系系统在不受外部干扰时,其内部最稳定的状态。后来一中国学者翻译entropy时,考虑到entropy是能量Q跟温度T的商,且跟火有关,便把entropy形象的翻译成“熵”。

    我们知道,任何粒子的常态都是随机运动,也就是"无序运动",如果让粒子呈现"有序化",必须耗费能量。所以,温度(热能)可以被看作"有序化"的一种度量,而"熵"可以看作是"无序化"的度量。

    如果没有外部能量输入,封闭系统趋向越来越混乱(熵越来越大)。比如,如果房间无人打扫,不可能越来越干净(有序化),只可能越来越乱(无序化)。而要让一个系统变得更有序,必须有外部能量的输入。

    1948年,香农Claude E. Shannon引入信息(熵),将其定义为离散随机事件的出现概率。一个系统越是有序,信息熵就越低;反之,一个系统越是混乱,信息熵就越高。所以说,信息熵可以被认为是系统有序化程度的一个度量。
更多请查看《最大熵模型中的数学推导》。

熵、联合熵、条件熵、相对熵、互信息的定义。机器学习 ML基础 中等

为了更好的理解,需要了解的概率必备知识有:
  1. 大写字母X表示随机变量,小写字母x表示随机变量X的某个具体的取值;
  2. P(X)表示随机变量X的概率分布,P(X,Y)表示随机变量X、Y的联合概率分布,P(Y|X)表示已知随机变量X的情况下随机变量Y的条件概率分布;
  3. p(X = x)表示随机变量X取某个具体值的概率,简记为p(x);
  4. p(X = x, Y = y) 表示联合概率,简记为p(x,y),p(Y = y|X = x)表示条件概率,简记为p(y|x),且有:p(x,y) = p(x) * p(y|x)。
:如果一个随机变量X的可能取值为X = {x1, x2,…, xk},其概率分布为P(X = xi) = pi(i = 1,2, ..., n),则随机变量X的熵定义为:

***BAT机器学习面试1000题系列    

    把最前面的负号放到最后,便成了:

***BAT机器学习面试1000题系列

    上面两个熵的公式,无论用哪个都行,而且两者等价,一个意思(这两个公式在下文中都会用到)。

    联合熵:两个随机变量X,Y的联合分布,可以形成联合熵Joint Entropy,用H(X,Y)表示。
    条件熵:在随机变量X发生的前提下,随机变量Y发生所新带来的熵定义为Y的条件熵,用H(Y|X)表示,用来衡量在已知随机变量X的条件下随机变量Y的不确定性。

    且有此式子成立:H(Y|X) = H(X,Y) – H(X),整个式子表示(X,Y)发生所包含的熵减去X单独发生包含的熵。至于怎么得来的请看推导:

***BAT机器学习面试1000题系列

   简单解释下上面的推导过程。整个式子共6行,其中

  • 第二行推到第三行的依据是边缘分布p(x)等于联合分布p(x,y)的和;
  • 第三行推到第四行的依据是把公因子logp(x)乘进去,然后把x,y写在一起;
  • 第四行推到第五行的依据是:因为两个sigma都有p(x,y),故提取公因子p(x,y)放到外边,然后把里边的-(log p(x,y) - log p(x))写成- log (p(x,y)/p(x) ) ;
  • 第五行推到第六行的依据是:p(x,y) = p(x) * p(y|x),故p(x,y) / p(x) =  p(y|x)。

    相对熵: