机器学习笔试面试题——day1_viterbi算法的面试题

选择题

1、一个二进制源X发出符号集为{-1,1}，经过离散无记忆信道传输，由于信道中噪音的存在，接收端Y收到符号集为{-1,1,0}。已知P(x=-1)=1/4，P(x=1)=3/4，P(y=-1|x=-1)=4/5，P(y=0|x=-1)=1/5，P(y=1|x=1)=3/4，P(y=0|x=1)=1/4，求条件熵H(Y|X)（ ）
A 0.2375
B 0.3275
C 0.5273
D 0.5372

$H(Y|X) = -\sum p(x)p(y|x) logp(y|x)$

2、Fisher线性判别函数的求解过程是将M维特征矢量投影在（ ）中进行求解。
A M-1维空间
B 一维空间
C 三维空间
D 二维空间

Fisher准则：两类样本在一维投影空间，类内密集（类内方差小），类间稀疏（类间均值差大）。数据服从高斯分布，分类效果更好。

3、类域界面方程法中，不能求线性不可分情况下分类问题近似或精确解的方法是（ ）
A 势函数法
B 基于二次准则的H-K算法
C 伪逆法
D 感知器算法

势函数：
    势函数用于确定分类界面，思想来源于无理方法，可以用于线性不可分的情况
伪逆法：
    RBF（Radial Basis Function）径向基函数，RBF网络需要学习的参数有3个：基函数的中心ci，方差σi以及隐含层与输出层间的权值Wi，根据径向基函数中心选取方法的不同，最常见的学习方法有：自组织选取中心法、正交最小二乘法等方法。 可以用于线性不可分的情况。
基于二次准则函数的H-K算法：
    H-K算法的思想很朴实，就是在最小均方误差准则下求得权矢量。它适用于线性可分和非线性可分的情况。
对于线性可分的情况，给出最优权矢量，对于非线性可分的情况，能够判别出来，以退出迭代过程。
感知器（Perceptron）
    只适用线性可分的情况

4、下列哪个不属于CRF模型对于HMM和MEMM模型的优势
A 特征灵活
B 速度快
C 可容纳较多上下文信息
D 全局最优

这三类都是概率图学习模型，都可以用于序列标注问题
HMM模型：
    对转移概率和表现概率直接建模，统计共现概率
MEMM模型:
    对转移概率和表现概率建立联合概率，统计条件概率
    很容易陷入局部最优，只在局部归一化
CRF(条件随机场模型)：
    在给定需要标记的观察序列的条件下，计算整个标记序列的联合概率分布。而不是在给定当前状态条件下，定义下一个状态的状态分布。
    统计了全局概率，考虑了数据在全局的分布，解决了标记偏置的问题；且没有那么严格的独立性假设条件，可以容纳任意的上下文信息，特征设计灵活；但是，CRF需要训练的参数很多，训练代价大，复杂度高。

5、Nave Bayes是一种特殊的Bayes分类器,特征变量是X,类别标签是C,它的一个假定是（）
A 各类别的先验概率P©是相等的
B 以0为均值，sqr(2)/2为标准差的正态分布
C 特征变量X的各个维度是类别条件独立随机变量
D P(X|C)是高斯分布

朴素贝叶斯的基本假设：每个变量相互独立

6、在HMM中,如果已知观察序列和产生观察序列的状态序列,那么可用以下哪种方法直接进行参数估计（）
A EM算法
B 维特比算法
C 前向后向算法
D 极大似然估计

HMM根据已知条件和所求的结果可以分为以下三类：
1）预测问题，解码问题——维特比算法
根据可见状态链得到隐含状态链
 
2）概率计算问题——前向后向算法
根据可见状态链得到某条隐含状态链的概率
 
3）学习问题，参数估计问题——Baum-welch算法
只有可见状态序列，根据序列学习模型的参数
Baum-welch算法是EM在HMM模型的具体体现
当观测序列和相应的隐含序列都存在时，用极大似然估计来估计参数

7、假定某同学使用Naive Bayesian（NB）分类模型时，不小心将训练数据的两个维度搞重复了，那么关于NB的说法中不正确的是？
A 模型效果相比无重复特征的情况下精确度会降低
B 如果所有特征都被重复一遍，得到的模型预测结果相对于不重复的情况下的模型预测结果一样
C 当两列特征高度相关时，无法用两列特征相同时所得到的结论来分析问题

朴素贝叶斯的条件：就是每个变量相互独立。
如果高度相关的特征引入两次，就增加了其重要性，性能就会下降，正确做法是评估特征的相关矩阵，并移除那些高度相关的特征。

8、以下哪些方法不可以直接来对文本分类？
A Kmeans
B 决策树
C 支持向量机
D KNN

典型分类方法：KNN,SVM,决策树
典型聚类方法：K-Means, DBSCAN、
典型回归方法：LR，Logistic
典型降维方法：PCA

9、已知一组数据的协方差矩阵P,下面关于主分量说法错误的是（）
A 主分量分析的最佳准则是对一组数据进行按一组正交基分解, 在只取相同数量分量的条件下,以均方误差计算截尾误差最小
B 在经主分量分解后,协方差矩阵成为对角矩阵
C 主分量分析就是K-L变换
D 主分量是通过求协方差矩阵的特征值得到

K-L变换与PCA变换是不同的概念，
PCA的变换矩阵是协方差矩阵
K-L变换的变换矩阵可以有很多种（二阶矩阵、协方差矩阵、总类内离散度矩阵等等）
当K-L变换矩阵为协方差矩阵时，等同于PCA

10、关于logit 回归和SVM 不正确的是（ ）
A Logit回归本质上是一种根据样本对权值进行极大似然估计的方法，而后验概率正比于先验概率和似然函数的乘积。logit仅仅是最大化似然函数，并没有最大化后验概率，更谈不上最小化后验概率。
B Logit回归的输出就是样本属于正类别的几率，可以计算出概率。
C SVM的目标是找到使得训练数据尽可能分开且分类间隔最大的超平面，应该属于结构风险最小化。
D SVM可以通过正则化系数控制模型的复杂度，避免过拟合。

Logit回归目标函数是最小化后验概率，Logit回归可以用于预测事件发生概率的大小，输出的是概率
SVM目标是结构风险最小化，SVM可以有效避免模型过拟合。

11 以下哪种方法属于判别式模型(discriminative model)（ ）
A 隐马模型(HMM)
B 朴素贝叶斯
C LDA
D 支持向量机

生成式模型：朴素贝叶斯，HMM，LDA
    生成模型（generative model）通过对观测值和标注数据计算联合概率分布P(x,y)来达到判定估算y的目的。
判别式模型：SVM，决策树，BP，LR,
    判别模型通过求解条件概率分布P(y|x)或者直接计算y的值来预测y。

12 以P(w)表示词条w的概率，假设已知P（南京）=0.8，P（市长）=0.6，P（江大桥）=0.4，P（南京市）=0.3，P（长江大桥）=0.5：如果假设前后两个词的出现是独立的，那么分词结果就是（ ）

最大概率分词是将其中概率最大的作为分词结果。通常计算各个选项的概率即可

13、基于统计的分词方法为（ ）
A 正向量最大匹配法
B 逆向量最大匹配法
C 最少切分
D 条件随机场

1）基于语法规则的方法
    在分词的同时进行句法、语义分析，利用句法信息和语义信息进行词性标注，解决歧义现象。
    但是现有的语法知识、句法规则十分笼统、复杂, 基于语法和规则的分词法所能达到的精确度远远还不能令人满意, 目前这种分词系统应用较少。
2）基于词典的方法
    可以分为最大匹配法、最大概率法、最短路径法。
    最大匹配法：按照一定顺序选取字符串中的若干字作为一个词去字典里查找；
    最大概率法：一个带切分的词可以有很多分词结果，概率最大的作为结果；
    最短路径法：词图上选择一条词数最少的路径。
3）基于统计的方法
    基于统计的分词法的基本原理是根据字符串在语料库中出现的统计频率来决定其是否构成词。词是字的组合，相邻的字同时出现的次数越多, 就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映它们成为词的可信度。常用的方法有HMM（隐马尔科夫模型），MAXENT（最大熵模型），MEMM（最大熵隐马尔科夫模型），CRF（条件随机场）。
 

14、隐马尔可夫模型（HMM），设其观察值空间为O={O1，O2，O3，...，ON},状态空间为S={S1,S2,S3,...,SK}，如果用维特比算法(Viterbi algorithm)进行解码，时间复杂度为（ ）
A O(NK)
B O(NK^2)
C O(N^2K)
D 以上都不是

15 在二分类问题中，当测试集的正例和负例数量不均衡时，以下评价方案哪个是相对不合理的（ ）（假设precision=TP/(TP+FP),recall=TP/(TP+FN)。）
A Accuracy:(TP+TN)/all
B F-value:2recallprecision/(recall+precision)
C G-mean:sqrt(precision*recall)
D AUC:ROC曲线下面积

16 下面关于ID3算法中说法错误的是（ ）
A ID3算法要求特征必须离散化
B 信息增益可以用熵，而不是GINI系数来计算
C 选取信息增益最大的特征，作为树的根节点
D ID3算法是一个二叉树模型

17、在其它条件不变的前提下，以下哪种做法容易引起机器学习中的过拟合问题（ ）
A 增加训练集数量
B 减少神经网络隐藏层节点数
C 删除稀疏的特征
D SVM算法中使用高斯核/RBF核代替

机器学习中发生过拟合的主要原因有：
（1）使用过于复杂的模型；
（2）数据噪声较大；
（3）训练数据少。
由此对应的降低过拟合的方法有：
（1）简化模型假设，或者使用惩罚项限制模型复杂度；
（2）进行数据清洗，减少噪声，删除稀疏的特征
（3）收集更多训练数据，增加训练集的数量

18、如果线性回归模型中的随机误差存在异方差性，那么参数的OLS估计量是（ ）
A 无偏的，有效的
B 无偏的，非有效的
C 有偏的，有效的
D 有偏的，非有效的

OLS即普通最小二乘法。最小方差的无偏估计量，随机误差不影响
最小二乘估计量是具有最小方差的线性无偏估计量。根据证明过程可知，随机误差中存在异方差性不会影响其无偏性，而有效性证明中涉及同方差性，即异方差会影响参数OLS估计量的有效性。

手撕代码题

1 判断删除一个能不能成为回文串/给定一个字符床，最多删除多个字符后能成为回文串

#判断删除一个字符能不能成为回文串：思路是给一个头指针h一个尾指针r，如果h!=r,那么首or尾移动一个，这种情况下已经相当于删除了一个字符
public class solution{
    public static boolean isResult(String s,int i,int j){
        while(i<j){
            if(s.charAt(i++)!=s.charAt(j--)){
                return false;
            }
        }
    }
    public static boolean Result(String s){
        int i=-1;
        int j=s.length();
        while(++i<--j){
            if(s.charAt(i)!=s.charAt(j)){
                return(isResult(s,i+1,j)||isResult(s,i,j-1));
             }
        }
        return true;
    }
}
#找到最少删除几个字符，字符串s能够变成回文串：思路是动态规划，首先将字符串反序，然后求反序和正序之间的最大公共子序列LCS,相减即为结果
public class solution{
    public class LCS(String s){
        public int getResult(){
            StringBuilder s1 = new StringBuilder(s);
            StringBuilder s2 = new StringBuilder(s).reverse();
            return(s.length - lcs(s1,s2));
    }
        public int lcs(StringBuilder s1,StringBuilder s2){
            int m = s1.length()；
            int n = s2.length();
            int[][] matrix = new int[m+1][n+1];
            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    if(s1.charAt(i) == s2.charAt(j)){
                        matrix[i][j] = matrix[i-1][j-1] +1;
                    }else{matrix[i][j] =Math.max(matrix[i][j-1] , matrix[i-1][j]);}
                }
            }
            return matrix[i][j];
        }
    }
       
    public static void main(String[] args){
		Soultion s = new Solution();
		Scanner sc = new Scanner(System.in);
		while(sc.hasNextLine()){
			System.out.println(s.getResult(sc.nextLine()));
		}
		sc.close();	
	}
}

2 反转链表 /判断链表是否有环

#反转链表，用递归
publib class ListNode{
	public int data;
	public ListNode next;
}
public ListNode reverse(ListNode pHead){
    if(pHead == null || pHead.next == null){
        return pHead;
    }
    ListNode pNext = pHead.next;
    pHead.next = null;
    ListNode reverseHead = reverse(pNext);
    pNext.next = pHead;
    return reverseHead;
}
#判断单链表是否有环：思路是遍历一个标记一个，遍历到已被标记的那么就表示有环
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
		while(head!=null) {
			if(set.contains(head)) {
				return true;
			}else {
				set.add(head);
				head = head.next;
			}
		}
		return false;
    }
}

3 TopK问题

/*topK问题可以有两种方式
1）如果数据量不是很大，那么可以用Quick Select类似于快排
2）如果数据量很大，类似于抖音10亿用户找出频繁前几的这种问题，用hashmap+小顶堆
*/
#第一种方法
public class topk_Quicksort{
	
	public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, k, 0, nums.length - 1);
	}
 
// quick select to find the kth-largest element
    public int quickSelect(int[] arr, int k, int left, int right) {
        if (left == right) return arr[right];
        int index = partition(arr, left, right);
        if (index - left + 1 > k)
            return quickSelect(arr, k, left, index - 1);
		else if (index - left + 1 == k)
			return arr[index];
		else
			return quickSelect(arr, k - index + left - 1, index + 1, right);
 
	}
//找一个基准把数据pivot，大的放左数组，小的放右边（快排）
	private int partition(int arr[], int left, int right) {
		int i = left;
		int j = right;
		int pivot = arr[left];
		while (i<j) {
			while (i<j && arr[j] < pivot)
				j--;
			while (i<j && arr[i] > pivot)
				i++;
			if(i!=j)
			swap(arr,i,j);
		}
		swap(arr, j, left);  // swap pivot and a[j]
		return j;
	}
	private void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}
#第二种方法
public class topK<E extends Comparable>{
	static String filepath ='/Users/java_workspace/algorithm/demo.txt';
	PriorityQueue<E> queue;
	static int k;
	//实现一个优先队列，最多的K个的出现次数;建立堆
	public topKwithPriorityQueue(int maxsize){
		if(maxsize<=0)
			throw new IllegalArgumentException();
			this.K = maxsize;
			this.queue = new PriorityQueue<>(maxsize,new Comparator<E>(){
				@Override
				public int compare(E o1,E o2){
					// 小根堆使用o1-o2
				return(o1.compareTo(o2));}
			});
		}
	public void add(E e){
		if(queue.size()< K)
		{queue.add(e);}
	    else{
			E peek = queue.peek();
			if(e.compareTo(peek)>0){
				queue.poll();
				queue.add(e);
		}	
	  }
    }
	//hashmap统计出现过的id及其次数
	public static HashMap<String,Integer> readAndConvert(){
		HashMap<String,Integer> map = new HashMap<String,Integer>();
		try{
			FileReader fr = new FileReader(filepath);
			BufferReader bf = new BufferReader(fr);
			String str;
			// 按行读取字符串
			while((str = bf.readLine())!=null){
				if(map.containsKey(str)){
				map.put(str,1);}
				else{
					int time = map.get(str);
					map.put(str,time+1);
				}
		}
		bf.close();
		fr.close();
    }catch(IOException e){
       e.printStackTrace();}
    return map;
	}
	//在hashmap中找到topK
	public static void main(String[] args){
		HashMap<String,Integer> map = readAndConvert();
		topKwithPriorityQueue pq = new topKwithPriorityQueue();
		for(String key:map.keySet()){
			pd.add(map.get(key));
		}
		ArrayList<String> res = new ArrayList<>();
		for(int i=0;i<pq.sortList().size();i++){
			for(String key:map.keySet()){
				if(map.get(key).equals(pq.sortList().get(i)&&!res.contains(key)){
					res.add(key);
				}
	       }
        }
		System.out.println(res);
	}
}

4 英文语句倒序输出，比如 "I love java "输出" java love I"

#仅仅反转字符串，那么就交换就好了
#假如是语句的反转，那么就整体反转一次，然后以空格为分隔，将（0-空格）内的字符再反转一次
public class character{
	public void swap(char[] arr,int begin, int end){
		if(begin<end){
			char temp = arr[begin];
			arr[begin] = arr[end];
			arr[end] = temp;
			end--;
		    begin++;	
		}		
	}
	public String swapwords(String str){
		char[] arr = str.toCharArray(); 
		swap(arr,0,arr.length-1);
		int begin =0;
		for (int i=1;i<arr.length-1;i++){
			if(arr[i] == ' '){
				swap(arr,begin,i-1);
				begin = i+1;
			}
		}
		return new String(arr);
	}
	public static void main(String[] args){
		String str = "I love java";
		System.out.println(new character().swapwords(str));
	}
}

机器学习算法

1 常用分类算法及其具体实现，他们的应用场景和区别

2 SVM多分类怎么做的

多分类主要是通过组合多个二分类器来实现多分类器的构造，常见的方法有OVO和OVR两种

1）OVO

k个类别样本构造k(k-1)/2个分类器，比如ABC三个类别样本，AB,AC,BC构造分类器，然后AB测试，如果A赢了（A=A+1,else B=B+1），其他两个分类器一样，，最后通过投票法决出最优的那个。

优点：效果好；缺点：类别多的时候，model的个数太多了

2）OVR

k个类别样本构造k个分类器，比如ABC三个类别样本，分别构造以A（B/C）样本为正BC（AC/AB）为负的分类器，然后将新样本分类输入三个分类器分类，取值最大的那个作为分类结果。

优点：只需训练k个分类器，速度快；缺点：每个分类器的训练都是以全部样本为训练集，出现新类别需要重新训练，且样本类别不均衡

3 SVM和LR的区别，SVM、LR手推