新浪-自然语言处理工程师-第2轮面试
面试概况
面试形式：QQ语音
面试时间：2016／3／11 20:30-21:40
面试岗位：新浪－产品技术部－自然语言处理工程师
面试时间较长，问题较多较杂，so，应该遗漏了一些。
面试内容
（1）个人简介
（2）项目
Q：怎么用N元模型做事件抽取的？
A：N元模型用来将细粒度的词合并为语块或短语，然后根据规则抽取事件。
Q：怎么用隐马模型做事件抽取的？
A：把事件抽取问题转化为标注问题，给分词过后的序列打标签。
Q：改进隐马模型有哪些改进的方面？
A：隐马模型有两个序列：一个状态序列，一个观测序列。
改进包括三个方面：
《1》第一个方面就是，HMM有一个假设是齐次马尔科夫性假设，t时刻的状态只与t－1时刻的状态有关，这会导致很多条件概率的缺失，为了降低条件概率的损失，对其进行扩展，令t时刻的状态与t－1和t－2时刻的状态有关，也就是将转移概率aij扩展为aijk，将观测值生成概率bi(k)扩展为bij(k)。原来的话是2-gram，现在将其扩展为3-gram；
《2》第二个改进就是采用多个观测序列，原始HMM是一个状态序列和一个观测序列，用观测序列去推测状态序列，使用多个观测序列的方法就是用多个观测序列去预测状态序列，这样可以考虑多维特征；
《3》第三个改进就是利用统计与规则相结合的思想，对先用HMM对训练数据进行预测，然后使用预测之后结果中有正确的，有错误的，对那些错误的实例，使用K－means方法进行聚类分析，得到一系列的错误纠正规则，然后用这些规则对HMM的预测结果进行修正。
Q：HMM是自己写代码实现的吗？
A：是，因为对HMM进行了改进，所以要自己实现。
Q：有编码实现前向－后向算法吗？
A：在改进的HMM中没有使用前向－后向算法拟合参数，而是采用的极大似然估计MLE，因为我使用的语料是标注过的，也就是有监督的，前向－后向算法是采用EM算法思想来进行无监督参数拟合，而且我在原始HMM中对比过两种算法，在有监督的情况下，MLE的效果优于前向－后向算法。
Q：假设现在有10个点，要你分成3类，讲一讲K－means算法流程？
A：。。。balabala。。。
Q：什么时候结束？
A：我知道的有两种方法：
《1》设置迭代次数；
《2》相邻的两次迭代结果的簇中心偏移程度——误差平方和小于某个阈值；
（3）面向对象语言
Q：你熟悉Java或C++吗？
A：本科时候主要使用C／C++，研究生期间主要用Python，研一的时候有用过Java。
Q：你听说过拷贝构造函数吗？【C++，面向对象程序设计】
A：听说过
Q：解释一下你对拷贝构造函数的理解？
A：比如有一个类Car，然后new 了一个对象是BMW，现在又需要一辆BMW，我们就可以重新new一个对象，然后用这个BMW作为参数用来初始化这个新的Car，这样我们就得到2个BMW。
（4）SVM
Q：讲讲你对SVM的理解？【SVM的理解】
A：2分类；最大间隔；
Q：这个最大间隔是什么？
A：点到分割超平面的最大间隔。
Q：谁到谁的最大间隔？
A：到分隔超平面最近的点到分割超平面的最大间隔。
举个例子，有4个样例点，是正方形的4个顶点，左边两个正例，右边两个负例，在中间划一条线把它们分开，这样的线有无数条，但是最大间隔的一条线就是正中间的那条，把正方形均分为两半的线，这条线到顶点的间隔就是最大间隔。
Q：SVM的目标函数是什么样子的？
A：w＊x＋b ＝ 0（这个不是面试官想要的答案）
Q：这是线性可分模型，非线性的呢？
A：函数间隔》几何间隔》原始问题》对偶问题》拉格朗日函数》拉格朗日因子向量》最后的形式是：sum sum aiajyiyjxixj＋sum ai（推导了半天，这个是拟合参数时候的公式，不是最后的目标函数，正确的应该是sum aiyiK(x,xi)＋b）
Q：如果有成千上万个样例，该怎么求解SVM目标函数？
A：SMO
Q：讲一讲SMO的原理？【SMO原理】
A：把大问题分解为小问题，如果求解成千上万个a难以求解的话，那么每次优化2个a，这样一步一步的完成整体优化。
Q：不用SMO方法，直接求解，应该如何解拉格朗日目标函数？
A：这个，不会。
（5）机器学习【过拟合，欠拟合】
Q：你知道过拟合和欠拟合吧？
A：知道。
Q：讲一下你对过拟合和欠拟合的理解？
A：过拟合就是对训练数据拟合的很好，对测试数据拟合的不好；欠拟合就是对训练数据的拟合程度不是很好，对测试数据的拟合程度稍微好些；
Q：为什么会导致过拟合？
A：数据量太少，特征太多（导致模型过于复杂，却又没有很好的泛化能力）
Q：有什么方法可以避免过拟合？
A：获取更多的数据，使用较少的特征
Q：逻辑回归的目标函数是什么？
A：y ＝ a＊x ＋ b，很久以前看过，一直没有用，所以记不清了
Q：逻辑回归是如何训练的？【逻辑回归与正则化】
A：不知道
Q：逻辑回归里的正则项是什么样子的？
A：记不得了
Q：逻辑回归是怎么样计算误差的？
A：真实值和预测值的误差平方和
Q：决策树中是如何选择选择特征的？
A：信息增益（ID3）信息增益比（C4.5）基尼指数（CART）
Q：信息增益和信息增益比的区别？
A：网上的资料显示，信息增益更倾向于选择属性值较多的特征，而信息增益比可以在一定程度上避免；
我自己的理解是，通过信息增益的值的大小很难评估一个特征的好坏，而信息增益比可以理解为熵减少的程度。
Q：BPNN的BP过程是做什么的？【BP神经网络】
A：是用来调整某个参数，记不清了。
Q：神经网络和SVM的联系和区别？【BP神经网络与SVM的关系】
A：SVM的函数是凸二次规划问题，这就相当于对问题做了一个存在最优解的假设，但是实际情况是谁也不知道是否有最优解；
神经网络就是有很多局部最优解，并没有全局最优解，更接近事实。
Q：你知道机器学习中哪些最优化方法？例如梯度下降等。【最优化】
A：以前知道梯度下降，现在记不清了。
（6）大数据
Q：有亿万个分好的词，找出出现次数最多的top k个词。【大数据】
A：一台机器？还是很多台？
Q：有足够的集群，你要怎么做？
A：用分布式方法，每个机器处理一部分，统计词频，然后汇总到一台机器上，得到最终的统计数据；
Q：怎么找到top k？
A：排序，然后找到前k
Q：用什么排序？
A：堆排序，这样只需要用很少的空间就可以完成排序＋查询了。
（7）数据结构
Q：二叉树排序树的查找时间复杂度？【二叉排序树】
A：O（log2N）
Q：最差情况的时间复杂度？
A：O(N)（一直没听明白面试官的意思，“最坏”，“最快”听不清。。。）
Q：怎么保持二叉树平衡？
A：构建平衡二叉树（具体怎么操作记不清了）
Q：你知道哪些平衡二叉树？【平衡二叉树】
A：平衡二叉树，红黑树（其他还有几个，记不清了）
（8）其他
Q：手上有其他offer吗？
A：没
