AI/机器学习（计算机视觉/NLP）方向面试复习3

1. Pooling 有哪些方式？pytorch的实现？

Pooling可以分成：最大池化，平均池化，全局平均池化，随机池化，空间金字塔池化。

1. 最大池化（Max Pooling）

最大池化是最常用的池化技术之一。它将输入图像划分为若干非重叠的矩形区域，然后对每个区域输出最大值。这种方法在实践中非常有效，能够很好地捕捉图像中的显著特征。

2. 平均池化（Average Pooling）

平均池化也将输入划分为多个区域，但它输出的是这些区域内的平均值。相较于最大池化，平均池化更平滑，但可能会丢失一些细节信息，因为它不像最大池化那样能突出显著特征。

3. 全局平均池化（Global Average Pooling）

全局平均池化是一种极端形式的平均池化，它计算整个特征图的平均值，通常用于卷积神经网络的最后阶段，直接输出用于分类的特征。这种方法能够显著减少模型的参数数量。

4. 随机池化（Stochastic Pooling）

随机池化是一种概率论的池化方法，不是简单地取最大值或平均值，而是根据预定义的概率分布（通常基于输入特征的大小）来选择池化区域内的元素。这种方法有助于增加模型的泛化能力，因为它引入了随机性。

6. 空间金字塔池化（Spatial Pyramid Pooling）

空间金字塔池化（SPP）是一种灵活的池化策略，它可以保持空间层次结构，允许网络接收任意大小的输入。SPP 通过在多个尺度上实现池化来捕获多层次的特征，这在一些特定的场景中非常有用，比如在需要处理不同分辨率的图像时。

2. attention的各种变形

self-attention里存在的问题是，当序列长度N非常大时，通过query(N,S) key(S,N) 相乘得到的Attention matrix(N,N)矩阵非常大。这里的计算过程非常复杂，就需要对self-attention进行简化。

而且这种简化经常会用在图像处理上，因为图像输入256×256的patch时，按像素为1个单位，N=256*256，过于大了。

一个方法是用感受野。把Attention matrix除了感受野以外的值设为0：（local attention）

但是这样设置感受野后，就和CNN没什么区别了。所以不太好。

Stride Attention：类似空洞卷积。每次看多几格的内容，例如空两格看三格以外的内容。

Local Attention：在原来的sequence里加上一个特殊的token。只有global token能获取所有的信息，其他token之间就不有attention了。Longformer用到了Global attention和striding attention， Big Bird用了global attention+striding attention和random attention。

Reformer：如何在Attention Matrix里，判断哪些地方有比较大的attention value，哪些地方的attention value比较小？然后把value比较大的取出来，当成attention。

这样做的方式是对query和key进行clustering聚类。clustering的加速方法有很多，可以快速将相近的query和key放在一起。只计算同类的query和key的attention，不同类的query和key的attention位为0，可以加速。

但这样是人类判断方式，根据任务判断两者之间是否相近。同样，也可以实现一个神经网络来判断key，value之间是否相近：Sinkhorn Sorting Network。

Linformer：本质在说attention matrix是一个低秩矩阵，列之间相关性很大，根本不需要构建这么大的attention matrix。就对列进行压缩。具体做法是从key中找到representative keys。

具体的压缩方法有：（1）对key做卷积进行压缩，（2）key是N维的，直接乘一个(N×K)的矩阵

k,q first -> v,k first 最后一个点是，当matrix相乘的顺序不同时，计算的效率也不一样。KQ先相乘再乘V比下面：先V乘K再乘Q的效率大很多。

3. 如何输入数据同时包括float类型的数据和文本数据，如何将它们都输入到网络里？

首先分别处理：

（1）对浮点数进行归一化和标准化处理

（2）对文本数据进行向量化处理，如使用词袋模型（BOW）、TF-IDF、词向量（如Word2Vec、GloVe）或更高级的BERT等方式。

然后进行特征合并:

将预处理后的浮点数和文本数据连接起来

可以用一个embedding层提取文本数据，再用一个dense层处理浮点型数据，然后用concatenate层连接起来。

4. 如何判断两个句子之间的相似性？

（1）余弦相似度。将两个向量之间的夹角。可以用来比较两个句子在向量之间的相似性。首先把句子转成TF-IDF向量，计算余弦相似度。

（2）Jaccard相似度：比较两个句子的词的集合的相似性。它是度量两个集合交集和并集的比率。

（3）基于词向量的方法：word2vec，转成向量后计算词向量的平均值。

（4）基于深度学习的方法：BERT

5. 如何去除噪声或异常点？

（1）统计方法，可以用均值和标准差来计算。

均值去除方法：计算数据的均值，减去均值来中心化数据。

标准化方法：将数据减去均值后除以标准差，使得数据具有零均值和单位标准差。

Z-Score：利用zscore检测异常值，通常设定一个阈值，超出这个阈值的点被视为异常点。

四分位数计算法：（IQR）计算数据的四分位数和四分位距，低于Q1-1.5*IQR或者高于Q3+1.5*IQR的点被视为异常。

（2）滤波方法：

简单移动平均（SMA）：计算一个窗口内数据点的平均值，并且用这个平均值平滑数据。

找一个滤波核，无论是一维二维都可以通过移动窗口进行平滑。

卡尔曼滤波：一种递归滤波器。

（3）机器学习方法：

聚类 K-means方法：检查哪些数据点不属于任何聚类中心。

孤立森林：基于决策树的方法，构建树并且根据树的深度检测异常点。

（4）小波变换：

将数据转换到频域，根据频域计算

6. cross attention是什么，python实现

cross attention与selfattention的区别在于，cross attention是针对两个序列的。两个相同维度的序列，一个作为输入的Q，另一个提供K和V。

算法基本上与self attention一致，就是输入的两个序列x1,x2,序列长度不一样，可是维度一样（embed size），所以输出的是x2的序列长度。

class crossAttention(nn.Module):
    def __init__(self,input_size): # (Batchsize, sequencelength, embedsize)
        super(crossAttention,self).__init__()
        self.queryl = nn.Linear(input_size, input_size)
        self.keyl = nn.Linear(input_size, input_size)
        self.valuel = nn.Linear(input_size, input_size)
 
    def forward(self,x1, x2):
        batch_size, seq_len, embed_size = x1.shape # B,T,C
        batch_size, seq_len2, embed_size = x2.shape # B, T2,C
        Q = self.queryl(x1)
        K = self.keyl(x2)
        V = self.valuel(x2)
        mask = torch.tril(torch.ones(seq_len, seq_len)).unsqueeze(0)
        QK = Q@K.transpose(-2,-1)/torch.sqrt(seq_len)
        mask_QK = QK.masked_fill(mask, float("-inf"))
        attention_weights = F.softmax(mask_QK, dim = -1) # (B,T,C)@(B,C,T2) = (B,T,T2)
        output = attention_weights @V # (B,T,T2)@(B,T2,C) = (B,T,C) # 最后的序列长度是x1的T
        return output #(B,T,C)

7. c++一些记不起来的用法（先写在这，后面汇总）

（1）unordered_map 和set 自定义比较函数

优先队列是放一组数据并且根据某个值排序，unordered map是不能直接排序的，要取出来放在vector里再做排序：

bool cmp(pair<int, vector<int>> a, pair<int, vector<int>> b) {
	return a.first > b.first;
}
int main() {
	vector<pair<int, vector<int>>> a;
	sort(a.begin(), a.end(), cmp);
}

（2）vector初始化

	vector<vector<int>> n = vector<vector<int>>(n, vector<int>(m, 0));

（3）int二维数组初始化

int** array = new int*[rows];

（4）int怎么转long

强制类型转换：

// int -》 long
int a = 1000;
long b = a;
// long -》 int
long a = 1000;
int b = (int) a;

（5）vector判断一个元素是否在里面

	// 查找是否有5这个元素
	vector<int>::iterator it;
	it = find(v.begin(), v.end(), 5);
    if (it == v.end()){
        return false;
    }else{
        return true;
    }

（6）unordered_map迭代

unordered_map<int,int> mp;
for(auto::iterator it = mp.begin();it!=mp.end();it++){
    cout<<it->first<<it->second<<endl;
}

8. python的ACM输入形式

一直没理解该怎么搞，当python输入是line，但是题目规定多个输入，第一行输入m表示样例个数，后面m行表示输入数据

一般题目里给这些：

import sys
 
for line in sys.stdin:
    a = line.split()
    print(int(a[0]) + int(a[1]))

但是这个输入是没法处理的，要自己写输入：用readline().strip()

import sys
 
# 读取第一行,获取case的数量
num_cases = int(sys.stdin.readline().strip())
print(num_cases)
# # 循环处理每个case
for _ in range(num_cases):
    # 读取一行输入并拆分
    line = sys.stdin.readline().strip()
    x = int(line[0])
    print(x)

9. 焊点题（文远知行笔试）

题目大意是，给一个n*m的焊板，和两个焊头的起始位置(x1,y1),(x2,y2), 两个焊头只能朝着同一个方向移动，并且任意一个焊头都不能出界，求最后焊板上有几个位置焊不到。

这题给我的感觉就是一定要想好了再动笔，我以为很简单就是个dfs，结果dfs超时，并且矩阵构建内存也不够，改了链表还是超时。

理一下思路：

根据两个点的坐标，找到它们离上下左右四个点的距离，然后求出两个正方形，分别是它们两个焊头能移动的范围。最后的结果是总面积-（两个矩阵的面积-两个矩阵重合的面积）

重点是两个重合的面积怎么求。

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
 
int area(int x1, int y1, int x2, int y2) {
	int width = abs(x1 - x2) +1;
	int height = abs(y1 - y2) +1;
	return width * height;
}
int main() {
	int n, m, x1, x2, y1, y2;
	//cin >> n >> m >> x1 >> y1 >> x2 >> y2;
	n = 4, m = 4, x1 = 0, y1 = 0, x2 = 2, y2 = 2;
	int minw1 = min(x1, x2);
	int minw2 = min(n-1 - x1, n-1 - x2);
	int minh1 = min(y1, y2);
	int minh2 = min(m - 1 - y1, m - 1 - y2);
 
 
	int A1 = area(x1-minw1, y1-minh1, x1+minw2, y1+minh2);
	int A2 = area(x2 - minw1, y2 - minh1, x2 + minw2, y2 + minh2);
	cout << x1 - minw1 << " " << y1 - minh1 << " " << x1 + minw2 << " " << y1 + minh2 << endl;
	cout << x2 - minw1 << " " << y2 - minh1 << " " << x2 + minw2 << " " << y2 + minh2 << endl;
	int x1_L = x1 - minw1,y1_L = y1 - minh1, x1_R = x1 + minw2, y1_R = y1 + minh2;
	int x2_L = x2 - minw1, y2_L = y2 - minh1, x2_R = x2 + minw2, y2_R = y2 + minh2;
	if ((x1_R <= x2_L && y1_R <= y2_L)) {
		// 没重叠
		cout<< n * m - (A1 + A2) << endl;
	}
	else {
		int overlap = area(max(x1 - minw1, x2 - minw1), max(y1 - minh1, y2 - minh1), min(x1 + minw2, x2 + minw2), min(y1 + minh2, y2 + minh2));
		cout << overlap << endl;
		cout << n * m - (A1 + A2 - overlap) - 2 << endl;
 
	}
}

10. 手写一个tensorflow的训练和测试