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

目录

1. GNN graph neural network

2. 0-1背包问题

3. 0-1背包问题（一维dp）

4. 螺旋矩阵 按顺时针顺序返回所有数

5. fasttext与glove

---

1. GNN graph neural network

（1）图的基本定义

GNN的Roadmap：其中用的最常见的还是GAT和GCN这两个model。

一般用到的tasks:

（1）半监督Node 分类

（2）回归

（3）图分类

（4）图表示学习

（5）链接预测

例子：NN4G的结构。先做embedding，再conv两次，最后readout也就是得到一个值，这个值就用来做分类。

李宏毅的课不知道在说什么。找了下其他的课件。图神经网络是一种图嵌入的方法，图嵌入除了图神经网络，还有矩阵分解和随机游走。常见模型是DeepWalk， Node2Vec。但是直接嵌入的方法缺乏泛化能力，无法处理动态图或者泛化到新的图。

2. 0-1背包问题

平时只会考01背包和完全背包，但重点还是写出状态转移方程。

01背包：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

这里要构造二维数组。dp[i][j]表示的是：当物品为i个，最大重量为j时的最大价值。

状态转移方程为: dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]) 分别表示放这个物品和不放这个物品

dp初始化：第一列都为0，因为重量为0放不了东西，第一行从重量能包含第一个物品开始，价值都为物品1的价值。因为物品1只有一个，放进去了就是它的价值。

遍历顺序先行后列，先列后行都可以。

写完代码发现坑还是很多。dp的维度，长为n，包含0到n-1个物品，宽为weight+1，包含0到weight个重量选择。

在每次迭代之前，要判断j的重量是不是小于这个物品重量，小于就肯定放不了。

int main(){
    int M,N;
    //m:物品数量，n：行李空间
    cin>>M>>N;
    vector<int> weights(M), value(M);
    for(int i =0;i<M;i++) cin>>weights[i];
    for(int i =0;i<M;i++) cin>>value[i];
    vector<vector<int>> dp(M,vector<int>(N+1,0));
    // init
    for(int j=weights[0];j<=N;j++){
        dp[0][j] = value[0];
    }
    // iter
    for(int i =1; i<M;i++){
        for(int j = 0;j<=N;j++){
            if (j<weights[i]) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + value[i]);
        }
    }
    cout<<dp[M-1][N] << endl;
    
}

3. 0-1背包问题（一维dp）

dp[i][j] = dp[i-1][j] + dp[i-1][j-weight[i]] + value[i]

简化为：

dp[j] = dp[j] + dp[j-weight[i]] + value[i]

初始化：整个数组初始化为0

要注意！一个是j是从大到小遍历的，另一点是j的限制条件，必须大于weights[i] 才可能把物品i放进去

int main(){
    int m,n;
    cin>>m>>n;
    vector<int> weights(m), values(m);
    for(int i=0;i<m;i++){
        cin>>weights[i];
    }
    for(int i=0;i<m;i++){
        cin>>values[i];
    }
    vector<int> dp(n+1,0);
    for(int i = 0;i<m;i++){
        for(int j = n;j>=weights[i];j--){
            dp[j] = max(dp[j], dp[j-weights[i]]+values[i]);
        }
    }
    cout<<dp[n]<<endl;
    return 0;
    
}

4. 螺旋矩阵 按顺时针顺序返回所有数

    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int top = 0,bot = n-1,left = 0, right = m-1;
        vector<int> res;
        while(true){
            for(int i = left;i<=right;i++ ) res.push_back(matrix[top][i]);
            top++;
            if(top > bot) break;
            for(int i = top;i<=bot;i++) res.push_back(matrix[i][right]);
            right--;
            if(right < left) break;
            for(int i = right;i>=left;i--) res.push_back(matrix[bot][i]);
            bot--;
            if(bot < top) break;
            for(int i = bot;i>=top ;i--) res.push_back(matrix[i][left]);
            left++;
            if(left > right) break;
        }
        return res;
 
    }

这题挺难搞，最好直接背这个思路，不然边界条件太麻烦了。

思路就是，设置上下左右边界，遍历一遍后更新边界，并判断边界是否有交错，有交错就说明到结尾了。

5. fasttext与glove

这两个是除了word embedding以外其他的词转向量的算法。

（1）fasttext

fastText是一个快速文本分类算法。非神经网络，用的应该是机器学习算法。和CBOW很像。但fastText预测标签，而CBOW预测的是中间词。用上下文来预测连接词。输入的是x的n-gram形式，输出的是类别。

它使用了分层softmax，也就是根据类别频率的霍夫曼树来代替softmax。原本是对所有类别做归一化，复杂度就是N，构造树后复杂度就是Log（N）

霍夫曼树就是把所有节点按权重排列

n-gram的具体实现，是文本内容按照子节顺序进行大小为N的窗口滑动操作，最终形成窗口为N的字节片段序列。

从上面来看，使用n-gram有如下优点：
1、为罕见的单词生成更好的单词向量：根据上面的字符级别的n-gram来说，即是这个单词出现的次数很少，但是组成单词的字符和其他单词有共享的部分，因此这一点可以优化生成的单词向量
2、在词汇单词中，即使单词没有出现在训练语料库中，仍然可以从字符级n-gram中构造单词的词向量
3、n-gram可以让模型学习到局部单词顺序的部分信息, 如果不考虑n-gram则便是取每个单词，这样无法考虑到词序所包含的信息，即也可理解为上下文信息，因此通过n-gram的方式关联相邻的几个词，这样会让模型在训练的时候保持词序信息

但正如上面提到过，随着语料库的增加，内存需求也会不断增加，严重影响模型构建速度，针对这个有以下几种解决方案：
1、过滤掉出现次数少的单词
2、使用hash存储
3、由采用字粒度变化为采用词粒度

（2）glove 带有全局向量的词嵌入

是一种无监督学习算法，用聚合全局词-词共现统计数据

所以fasttext用的是ngram，glove用的是共现矩阵。

GloVe的优点在于，与Word2vec不同，GloVe不仅依赖于局部统计信息（单词的本地上下文信息），而是结合全局统计信息（单词共现）来获得单词向量。

GloVe可以从共现矩阵（co-occurrence probabilities matrix）中派生单词之间了解语义关系。

共现矩阵是一个方阵，第i行j列表示单词i与单词j之间的关系。判断方式是看这两个词是否出现在上下文中，也就是同一个句子或者同一个窗口。

6. 只出现一次的数组

给一个数组，判断哪个数只出现一次，保证其余的数都出现两次。

做法就是异或，相同的数异或为0，都消掉了，不同的数异或结果就等于他本身。注意异或符号是^。（python也是）

    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int num:nums){
            res =res ^ num;
        }
        return res;
    }

7. 分割等和子集

我这辈子都想不到这题会用01背包做。反正题解解释的思路大概也能懂，但是换个题我肯定就不会了。。

从一个数组里找到一些数加起来能刚好等于总和/2

做法就是01背包，让weights=values=数。重点在于，如果刚好有一组数加起来能等于target，那么dp[target]=target. 否则，dp[target]肯定小于dptarget。

状态转移方程和01背包一模一样，没啥好说的

    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int n:nums){
            sum += n;
        }
        if (sum%2 != 0) return false;
        int total = int(sum/2);
        cout<<total<<endl;
        vector<int>dp(total+1,0); 
        for(int i =0;i<nums.size();i++){
            for(int j = total;j>=nums[i];j--){
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if (dp[total] == total) return true;
        return false; 
    }