^-^
保研复习
  1. 杂项
    1. 熵相关
      1. 熵 / 信息熵
      2. 条件熵
      3. KL 散度/ 相对熵
      4. 交叉熵
  2. 线性代数
    1. 基础内容
    2. 特征值与特征向量
    3. Jordan 标准型
    4. 二次型与合同
    5. 线性空间与线性变换
  3. 矩阵分析
    1. 矩阵求导与向量求导
    2. 谱定理与谱分解
    3. Hermite 矩阵的变分特征
      1. Rayleigh 商定理
    4. 矩阵分解
      1. 奇异值分解
      2. 紧奇异值分解和截断奇异值分解
      3. 奇异值分解和谱分解的联系与区别.
    5. 矩阵范数
  4. 概率论
    1. 常见离散分布
    2. 常见连续分布
      1. 正态分布的性质
      2. 高维正态分布
    3. 期望和方差的性质
    4. 条件期望
    5. 概率不等式
  5. 凸优化
    1. 凸集
      1. 常见的保凸运算
    2. 凸函数
    3. 对偶
      1. 为何对偶如此重要
      2. 直观理解对偶
  6. 机器学习
    1. 基本概念
      1. 正则化
    2. 无监督学习
      1. PCA
        1. 总体主成分
        2. 样本主成分
    3. 监督学习
  7. 数据结构
    1. 线性表
      1. 链表
      2. 队列
    2. 串
      1. KMP 算法
    3. 排序
    4. 二叉树
      1. 基本概念
      2. 二叉排序树
      3. 平衡二叉树
      4. 哈夫曼树和哈夫曼编码
    5. 查找
    6. 图论
  8. 算法题
    1. 模板
    2. 动态规划
      1. 最长不上升/不下降子序列
        1. 做法
        2. 做法
      2. 最长公共子序列
      3. 背包
        1. 01 背包
        2. 完全背包
        3. 多重背包
        4. 混合背包
      4. KMP
      5. 图论
        1. 最短路
        2. 最小生成树
          1. Prim 算法以及正确性的证明
          2. Kruskal 算法以及正确性的证明
  9. STL 各种常见用法总结
  10. AI
  11. 操作系统
  12. 计网
  13. 计组
  14. 各种经验贴
  15. 面试准备
    1. 英文自我介绍
    2. 简历上可能会被问到的问题
  16. 关注的知乎问题

看 李航《统计学习方法》下述内容:

  • 附录 C
  • 附录 D
  • 附录 E
  • SVD
  • PCA
  • MCMC
  • HMM
  • EM
  • 条件随机场/Page Rank

杂项

1: : 表示最小的 满足 . (下确界)

2: : 表示最大的 满足 . (上确界)

3:

4:

熵相关

熵 / 信息熵

条件熵

KL 散度/ 相对熵

KL (Kullback-Leibler) 散度是描述两个概率分布 相似度的一种度量, 记作 , 定义为 具有如下性质:

  • , 当 取等, 这是利用 Jensen 不等式证明的.
  • KL 散度不具有对称性, 因此它不能看作是距离度量.

注意到

交叉熵

线性代数

重点应该是秩, 特征值与特征向量, 二次型部分.

基础内容

下面 为非方阵时, .

  1. 矩阵 可逆的等价条件:

    • 或满秩.
    • 的行向量组和列向量组都是线性无关的
    • 有唯一解
    • 只有零解
    • 不是 的特征值

  2. 秩的多种定义 ( ):

    • 存在 的子矩阵的行列式不为 0, 且所有 的子矩阵的行列式都为 0
    • 像空间 的维数为
    • 零空间 的维数为
    • 的行向量组和列向量组有且仅有 的线性无关的向量

  3. 齐次线性方程组 解的相关情况

    • 时有唯一零解 (此时隐藏了 的条件)
    • 时有非零解

  4. 非齐次线性方程组 解的相关情况:

    • 时, 无解
    • 时, 有唯一解
    • 时, 有无穷多组解

  5. Pseudo Inverse:

  6. 矩阵的一些 space, 设 , 则

    • 行空间: 的行向量组张成的线性空间, 记作

    • 列空间: 的列向量组张成的线性空间, 记作 .

    • 像空间 , 又称为值域/值空间. 有

    • 零空间 , 又称为核. 又被称为 的左零空间. 可以注意到对任意 , , , 这是因为 与 的所有行向量的内积都为 0, 且 是 的行向量的线性组合. 这一结果说明了 , 两者互为正交补.

      子空间的正交补: 若 都是 的子空间且对任意 都有 , 则称 和 是正交的. 定义正交补 当 是子空间时其正交补也是子空间.

特征值与特征向量

  1. 可以推出 (记作 ) :
    • , 因为 .
  2. 可对角化的条件:
    • 有 个线性无关的特征向量
    • 每个特征值对应的线性无关的特征向量个数/特征子空间维度/几何重数 代数重数/特征根对应的重数
    • 有 个不同的特征值
  3. 相似的条件:
    • 与 相抵.
    • 若都可对角化, 则相似当且仅当它们的相似标准型相同.
    • 若都不可对角化, 则相似当且仅当它们的 Jordan 标准型相同.
  4. 实对称矩阵, 设 是实对称矩阵:
    • , 反对称矩阵/斜 Hermite 矩阵的特征值都是纯虚数.
    • 实对称矩阵一定可以实正交对角化.
    • 两个实对称矩阵相似的充要条件是它们有相同的特征值.

Jordan 标准型

对于不可对角化的矩阵, 将其转化为 Jordan 标准型来计算.

二次型与合同

  1. 与 合同, 存在可逆矩阵 使得 .
  2. 任何一个二次型都可以通过可逆线性变换变成标准型; 任何一个实二次型都可以通过正交变换化为标准型.
  3. 惯性定理: 二次型 的标准型 不唯一, 但是 , 是确定的.
  4. 正定与下面命题等价:
    • 与 合同
    • 存在可逆矩阵 使得
    • 的特征值都为正
    • 的顺序主子式都大于 0
  5. 实对称矩阵相似必合同, 这依赖于正交矩阵 的性质.
  6. 若实对称矩阵 正定, 则存在实对称正定阵 使得 : .

线性空间与线性变换

  1. 线性空间的定义: 封闭的加法且满足交换律/结合律/存在零元/存在负元; 封闭的数乘且满足 存在数域中的单位元/结合律/分配律/数因子分配律.
  2. Kronecker 积: 得到一个分块矩阵, 第 块为 .
  3. 维数公式 , 其中 是 的子空间, .
  4. 线性相关的充要条件是它们的 Gram 矩阵的特征值为 0.
  5. Schmidt 正交化: 得到正交的 : , 以及 .

矩阵分析

矩阵求导与向量求导

最小二乘法求仿射函数的估计.

谱定理与谱分解

Hermite 矩阵的变分特征

Rayleigh 商定理

设 是 Hermite 矩阵 的按顺序排列的特征值, 则

  • 是 的所有 维子空间中 的最小值.

矩阵分解

奇异值分解

对任意复矩阵 , 它总可以分解成 的形式, 其中 , 且 其中 , , 且 和 都是酉方阵. 若 , 则 , 且 是 降序排列的非零特征值的平方根. 的对角元称为矩阵 的奇异值.

PROOF 简述证明的思路. 这是一个构造性证明, 逐步确定 来证明. 其中 和 来自 的谱分解 , 其中 是酉的, 且 的对角元按照大小排序, 相应的 的列向量也按照对应关系排序, 然后 由 和 0 矩阵形成了 的分块矩阵. 设 , 对应了非零特征值, 对应了零特征值, 然后 , 则令 , , 为 的一组标准正交基形成的矩阵, 这两点保证了 是酉的, 则 .

紧奇异值分解和截断奇异值分解

考虑秩 , 给定 , 那么紧奇异值分解为 , 其中 , 是 的前 列, , 对角元是 的前 个对角元, , 是 的前 列, 其实就是上文的 .

截断奇异值分解为 , 含义同上. 此时 .

这个 是在 Frobenius 范数意义下, 在所有秩不超过 的 的矩阵集合中, 对 的最佳近似, 即 是优化问题 的最小值点.

TODO: 简单证明思路.

奇异值分解和谱分解的联系与区别.

由于 都是酉的, 当 作用在 上时, 经历了如下的变化:

  • 在 的作用下仅进行了旋转(或者说等距变换)
  • 在 的作用下仅进行了缩放
  • 在 的作用下再次仅进行了旋转; 此外, 若 , 则这一步还额外对 做了投影.

当 是 Hermite 的或者说实对称的时, , 当它作用在它的特征向量 上时, 两次线性变换 将会相互抵消; 作用在非特征向量上时, 效果和奇异值分解是一致的, 因为 是正交矩阵.

若 是 Hermite 的, 那么 , 此时 的奇异值等于特征值, 这是因为 的谱分解 , 的对角元刚好是 的特征值也是 的奇异值.

矩阵范数

  1. 是 Frobineus 范数, 是将矩阵 拉平得到的向量
  2. , 最大列和范数.
  3. 是谱范数, 的最大特征值的绝对值, 由向量 范数诱导.
  4. 若对任意 都有 , 称 和 等价. 有限维向量范数都等价.
  5. Frobineus 范数和谱范数的关系:
    • , . 是奇异值.
    • 两者都是酉不变范数.

概率论

常见离散分布

是随机变量/随机向量.

1: 两点分布 , , .

2: 二项分布 , , , 分布

  • 独立重复地做 次伯努利实验, 取值为 1 的次数.

  • 有放回的抽样.

具有可加性

3: 多项分布 , . 其中 , . , .

独立重复地做 次 multinoulli 实验, 每个变量取值为 1 的次数.

4: 负二项分布 , , .

实例: 某种产品的次品率为 现一个一个地从若干该产品中抽取, 设抽取到第 件次品时已经检出 件合格品.

5: 几何分布 , 是负二项分布 的特例.

6: 超几何分布 , , .

  • 从有 个废品的 个产品中随机抽出 个产品, 废品数为 个.
  • 无放回抽样.

7: 泊松分布 ,

泊松分布具有可加性.

常见连续分布

1: 正态分布

正态分布具有可加性

2: 指数分布

3: 均匀分布

4: 分布

分布具有可加性.

5: 分布

6: 分布

正态分布的性质

高维正态分布

设 , 则 的联合概率密度为 当 不可逆时, 的联合概率密度无法被写出, 称其服从退化/奇异正态分布. 其特征函数为 高维正态分布有如下性质:

1: 的任一 维子向量 也服从 维正态分布 , 其中 , 是取 的 行和列的子矩阵.

2: 相互独立的充要条件是两两不相关.

相互独立的充要条件定义为 .

3: 设 , 则 . 这个性质称为正态分布的线性不变性. 注意 时 , 此时 退化; 若 不退化且 且行满秩, 则 不退化.

这个证明可以利用特征函数的反演定理以及唯一性定理来证明, 也可以直接计算 和 , 实际上 的每一维都是 的线性组合, 利用期望和方差的定义也可以直接计算, 即 , .

4: 由 的实对称性质, 则存在正交变换 使得 是相互独立的正态随机向量. 的退化与否取决于 的退化情况, 因为正交矩阵是行满秩的.

期望和方差的性质

条件期望

概率不等式

凸优化

凸集

设 若对所有的 以及 都有 则称 为凸集(convex set).

式 实际上是以点 为端点的线段, 它又被称为 的凸组合. 凸组合可做推广: 设 非负实数 满足 则 称为 的一个凸组合.

定理1 为凸集的充要条件是 中有限个点的凸组合仍然在 中.

常见的凸集包括(下面所有的 ):

  • 超平面 超平面将 分成了两部分.

  • 半空间

  • 球 是半径为 中心为 的 (Euclid) 球

  • 椭球: 对球做一线性变换 , 可得椭球为 其中

  • 多面体/单纯形: 有限个半空间和有限个超平面的交集, 即 限制有限个是因为任意凸集都可以被写成无限个半平面与无限个超平面的交集, 比如球可由其所有切平面某一侧的半空间的交集形成.

  • (半)正定锥: 定义 称 为半正定锥, 为正定锥

常见的保凸运算

保凸运算指的是对凸集做的运算, 并且在运算后得到的仍然是一个凸集.

  • 任意多个凸集的交是凸集;
  • 缩放, 平移和投影变换等(仿射变换)都是保凸运算. 这些变换可以被表述为映射

凸函数

定义2 (凸函数) 设 是凸集, 对所有 都有 成立, 则称 是 上的凸函数.

上式的 改成 得到严格凸函数的定义. 类比凸函数可以定义凹函数, 事实上凹函数可由凸函数直接定义, 即 是凹函数当且仅当 是凸函数.

定理2 设 是凸集, 则 是 上的凸函数的充要条件是: 对任意的正整数 以及不完全相同的 若非负实数 满足

对偶

给定一个凸优化问题: 其中 均为可微凸函数, 并设 .

然后引入拉格朗日函数 其中 为拉格朗日乘子.

定义 , 注意到 这是因为当 时, 首先有 , 其次由于要求 , 因此 时 才能有最大值.

因此 实际上是与原问题等价的, 于是称问题 称为广义 Lagrange 函数的极小极大问题, 并定义原始问题最优值 .

类似地, 可定义广义 Lagrange 函数的极小极大问题 并令 . 称之为原始问题的对偶问题.

弱对偶条件 .

PROOF 使用 作为桥梁即可. 首先 这对任意的 都是成立的, 那么自然就有 .

想知道什么时候可以取等, 就有所谓的强对偶条件.

强对偶条件 当原始问题满足 Slater 条件 (SCQ) 时, . 这是一个充分条件.

首先给 relative interior 的定义, 一个集合 的 relative interior 定义为 的 affine hull 的内点, 具体而言 其中 即 affine hull 是 中所有点的凸组合的集合.

对于一个凸集 , 它的 relative interior 还可以定义为 Slater 条件表述如下: 对于一个凸优化问题,

  • 为仿射函数, 可以将这个约束条件记作
  • 存在 , 使得 .

再简述证明思路.

参考:

[1] Slater's condition - Wikipedia

[2] Relative interior - Wikipedia

[3] 【中科大凸优化-10】弱对偶、强对偶、Slater条件及对偶问题的四种解释 - 知乎 (zhihu.com)

为何对偶如此重要

直观理解对偶

参考:

[1] 凸优化笔记11：对偶问题 - 知乎 (zhihu.com)

[2] 如何通俗地讲解对偶问题，尤其是拉格朗日对偶 lagrangian duality？ - 知乎 (zhihu.com)

[3] 线性空间的对偶空间和优化里的拉格朗日对偶有什么关系？ - 知乎 (zhihu.com)

机器学习

基本概念

正则化

为什么 L1 正则化可以给出稀疏解? 这是由于 1 范数球是一个多面体且顶点都在坐标轴上, object function 的等高线作为一条曲线更容易接触到 1 范数球的角所在的点, 这些点在坐标轴上, 自然就是稀疏解. 事实上也可以用 范数, 这种具有尖锐的角的特性会更加明显, 但是求导会带来更高的计算成本.

无监督学习

PCA

其实就是降维, 用少数不相关的变量来代替相关的变量来表示数据, 要求保留数据中绝大多数信息.

总体主成分

样本主成分

监督学习

数据结构

线性表

  1. 空间复杂度判断链表是否有环: 快慢指针, 定义两个指针同时出发, 其中一个指针每次移动一个结点, 另一个指针每次移动两个结点, 如果两者在有限时间内相遇则有环, 否则如果都变为空结点则无环.

链表

在只带头指针的循环链表中找尾结点的时间为 .

队列

  1. 用数组 a[n] 实现循环队列, 借助取模操作.
    • rear 指向队尾元素, front 指向队首元素的下一个元素.
    • 队列长度/队列中元素的个数 (rear+MaxSize-front)%MaxSize
    • rear==front 时队空, (rear+1)%M=front 时队满 (牺牲一个存储单元的做法).
  2. 删除操作指的是出队.
  3. A[0...n] 表示数组长度为 n+1, A[n] 表示数组长度为 n.
  4. 当有队首指针和队尾指针时, 用链表实现队列不需要循环链表; 当只有队首指针或队尾指针时, 循环链表更适合实现队列. 当单链表作为队列时, 头节点为队首结点, 便于删除操作.

串

KMP 算法

给定字符串 , .

  • 的前缀是集合 中的元素, 后缀是集合 中的元素.

  • 串 的最长相等前后缀长度为 .

  • 的部分匹配值是 的所有前缀以及自身的最长相等前后缀长度形成的序列, 也可以写成数组形式. 比如 abcac 的部分匹配值为 00010. 若 的部分匹配值为 , 则称字符 对应的部分匹配值为 .

  • next 数组: next[j] 的含义是, 在字串的第 个字符与主串发生失配时, 跳到字串的 next[j] 位置重新与主串的当前位置进行比较. 计算方法 此集合不为空

  • nextval 数组.

排序

二叉树

基本概念

  1. 完全二叉树.

    • 则 为非叶子结点, 否则为叶子节点. 叶子节点仅可能在最下面两层出现.
    • 一个结点只有一个子节点时, 这个儿子为左儿子, 且这个节点编号之后的所有节点都是叶子节点.
    • 个结点的完全二叉树的高度为 或者 . 结点 所在的深度为 .

    也不用刻意去记, 简单推导就行了.

  2. 二叉树的遍历.

    • 先序: 根-左-右.
    • 中序: 左-根-右.
    • 后续: 左-右-根.
    • 先序序列和中序序列, 后序序列和中序序列都可以唯一地确定一颗二叉树. 确定的方式是, 根据遍历顺序的特点确定根节点以及根节点的左右儿子. 比如由先序 和中序 , 首先 是根节点, 则 在左, 在右; 然后对于 和 按照相同的方式即可, 是根节点, 是根节点, etc.

  3. 线索二叉树. 利用空结点记录前驱和后继, 遍历一次二叉树以线索化.

  4. 树, 森林的存储以及二叉树的转换.

二叉排序树

平衡二叉树

哈夫曼树和哈夫曼编码

查找

图论

算法题

模板

直接抄一遍.

动态规划

挑一部分题只写思路.

最长不上升/不下降子序列

序列 .

做法

一种方法是对 排序得到 , 然后 地求 的最长公共子序列.

另一种方法: 状态设计为 表示前 个数中以 结尾的最长不上升子序列的长度, 进行状态转移, 只需要枚举 比 大的那些数即可: 且 . 每个 需要 的时间, 那么就是 的时间.

做法

在上面的基础上, 定义 为所有长度为 的不上升子序列中的末尾元素的最大值. 是单调不增的即 , 如若不然, 假设 , 那么存在长度为 的以 结尾的不上升子序列, 在这个子序列中, 可以取出长度为 的结尾仍以 的子序列, 这就意味着长度为 的不上升子序列的末尾元素的最大值应该为 , 与最大值 相矛盾.

然后现在还是要计算 , 设 , 则一定有 , 否则的话若 , 则将以 结尾的长度为 的不上升子序列的末尾元素 替换为 , 得到了一个新的长度为 以 为结尾的不上升子序列, 那么应有 , 与 矛盾.

然后 是单调不增的, 那么只需要找到 , 可以用二分, 在一个单调序列中找到下标最大的且距离某个给定的值最近的下标. 这样计算每个 只需要 的时间, 最终时间复杂度为 .

最长公共子序列

和 . 只有 做法.

记 为最长公共子序列的长度, 考虑 和 之间的关系: 空间复杂度也为 .

背包

01 背包

状态设计: 表示将前 个物品装入容量为 的背包可获得的最大价值.

状态转移: 逆序枚举 .

1
2
3
4
5
for i in range(n):
    j=T
    while j>=t[i]:
        f[j]=max(f[j],f[j-t[i]]+v[i])
        j-=1

用了滚动数组优化.

完全背包

状态设计: 表示选择前 个物品装入容量为 的背包可获得的最大价值.

状态转移: 与 01 背包一致. 顺序枚举 .

1
2
3
4
5
6
7
8
for(int i=0;i<n;i++){
    for(int j=0;j<=T;j++){
        if(j>=t[i]){
            f[j]=max(f[j],f[j-t[i]]+v[i]);
        }
    }
}
cout<<f[T];

多重背包

每种物品有 个. 将 个物品看作价值相同的不同的物品, 转化为 01 背包, 物品总个数变为 .

二进制分组优化: 令 , 当 无法完美地表示为 时, 尾项 为 , 记分拆后的项的集合为 , 这样 , 保证了正确性.

下面是分组代码.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
index = 0;
for (int i = 1; i <= m; i++)
{
    int c = 1, p, h, k;
    cin >> p >> h >> k;
    while (k > c)
    {
        k -= c;
        list[++index].w = c * p;
        list[index].v = c * h;
        c *= 2;
    }
    list[++index].w = p * k;
    list[index].v = h * k;
}

混合背包

有的物品只能取一次, 有的物品无限次, 有的物品 次. 的含义仍然是前 个物品背包容量为 时物品最大价值.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i=1;i<=N;i++) {
    if (s[i]==0) { //完全背包
        for (int j=v[i];j<=V;j++)  dp[j]=max(dp[j],dp[j-v[i]]+w[i]); // 完全背包更新公式, 正序
    } else {
        if (s[i]==-1) s[i]=1; //0-1背包就是特殊的多重背包
        for (int k=1;k<=s[i];k*=2) {//每个背包挨个拆分
            for (int j=V;j>=k*v[i];j--)  dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]); // 其实也是 01 背包更新公式, 逆序, 每个物品价值为 k*w[i], 体积为 k*v[i]
            s[i]-=k;
        }
        if(s[i]) {
            for (int j=V;j>=s[i]*v[i];j--)  dp[j]=max(dp[j],dp[j-s[i]*v[i]]+s[i]*w[i]); // 分组后无法写成2的幂次的数, 也是 01 背包的更新公式
        }
    }
}

KMP

图论

最短路

Dijkstra, Bellman-Ford, Floyd.

最小生成树

Prim, Kruskal.

Prim 算法以及正确性的证明

构造集合 , 每次选择割集 中权最小的边并将其在 中的端点放入 中. (将生成树逐渐生长的过程)

PROOF 设 Prim 算法得到的生成树为 , 是算法流程中加入的一条边, 证明不包含 的生成树 的总边权一定不会会更小. 由于 不包括 , 由生成树的性质, 之间存在路径 , 且一定有 或 , 如若不然, 在 Prim 算法执行的过程中就需要选择 或者 . 那么对于 , 只需要把 或 替换为 , 就可以得到更优或不变的生成树.

Kruskal 算法以及正确性的证明

按照边权排序, 在保证不成环的条件下从小到达选边, 直到选择了 条边. (将最小生成森林并为最小生成树的过程)

PROOF 和 Prim 类似, 证明不包含 的生成树 的总边权一定不会会更小, 仍然设 之间的路径是 . 有下面两种情况:

  • 中存在边 边权大于 , 那么将 替换为 即可, Kruskal 算法执行过程也会选择 而不是
  • 中所有边的边权都小于等于 , 那么在 Kruskal 算法执行的过程中, 中所有边都会先于 被考虑, 因此 不会包含在 中.

STL 各种常见用法总结

参考

拿出来一些更常用的在这里.

对于迭代器 v, 或长度为 首地址为 a 的数组:

  • reverse(v.begin(),v.end()) 或 reverse(a,a+n): 翻转数组或字符串.

  • nth_element(v.begin(),v.end(),cmp): 找出序列第 大的元素.

  • binary_search(v.begin(),v.end(),value): 二分查找, 其中 value 为需要查找的值, 返回 bool 类型值.

  • lower_bound(v.begin(),v.end(),x): 二分查找, 返回第一个大于等于 的元素 (以 为 lower bound) 的迭代器

  • upper_bound(v.begin(),v.end(),x): 二分查找, 返回第一个大于 的元素的迭代器

    lower_bound 和 upper_bound 默认序列是递增的, 且都是 的. 对于 set 是 , 调用 set 自身封装的, 如: s.lower_bound(val).

    而且 upper_bound 名不副实.

    1
    2
    3
    int a[10]={0,2,2,7,9,12,13,18,28,29};
    cout<<*upper_bound(a,a+10,7)<<endl;
    cout<<*lower_bound(a,a+10,7);

    分别输出 9 和 7.

AI

  1. universal approximation theorem: 描述神经网络理论上可以学习何种函数.
    • 任意宽的情况: 设 , , 且 .
  2. 计算图与反向传播

操作系统

计网

计组

各种经验贴

面试准备

英文自我介绍

一分钟版本: Hello, teachers. My name is Xu Baoduo from Henan Province. I major in Artificial Intelligence in UESTC. In the past few years, I have won the Second Prize in Finals in the Chinese Mathematics Competition. I mainly have two research experiences. The first is designing better algorithm for Maximal co--plex Enumeration in the field of Theoretical Computer Sicence. It's expected to be submitted to Journal TCS or 2025 WALCOM. The second is Post Interaction Block for Addressing Hallucination in Vision-Language Models. It is expected to be submitted to 2025 AAAI.

两分钟版本: Hello, teachers. My name is Xu Baoduo from Henan Province. I major in Artificial Intelligence in UESTC. In the past years, I have won the Second Prize in Finals of the Chinese Mathematics Competition, Second Prize in Provincial Competition of Lanqiao Cup, and Second Prize in "Shanshu Cup" Mathematical Modeling Elite Competition. I mainly have two research experiences. The first is designing better algorithm for Maximal -plex Enumeration in the field of Theoretical Computer Sicence. It's expected to be submitted to Journal TCS or 2025 WALCOM. The second is Post Interaction Block for Addressing Hallucination in Vision-Language Models. It is expected to be submitted to 2025 AAAI. My research interests primarily lie in the foundational theoretical aspects of artificial intelligence and computer science, including learnthing theory, generalization theory, optimization in deep learning, theories and applications of large language models, combinatorial optimization and so on.

计划: Firstly, I will often talk and exchange ideas with my advisor and classmates. I will also keep studying basic courses and reading a lot of literature to understand this research field better. Secondly, through many discussions and reading a lot of papers, I hope to come up with new questions on my own and focus on solving them, aiming to do impactful work. Lastly, I want to learn about more areas, especially practical ones, so that theories can be applied to benefit society. This will also help me develop my creativity and problem-solving skills.

个人兴趣:

介绍学校: UESTC

介绍专业: Artificial intelligence (AI) is a field of computer science. It focuses on creating machines and software that can think, learn, and make decisions like humans. It involves teaching computers to recognize patterns, understand language, and solve problems. AI is used in many everyday applications, such as virtual assistants like Siri, recommendation systems in many APPs, and even in self-driving cars. The goal of AI is to make our lives easier and more efficient.

家乡: My hometown is a small village in Henan Province. People there often work on farms, growing wheat, corn and other crops.

简历上可能会被问到的问题

  • -plex 有什么应用吗? 答: -plex 是一种松弛团, 团的定义是 blabla, 其中一种应用是在社交网络中检测聚集现象, 但团的定义过于苛刻, 因此放松要求, 其中一种定义是 -plex.

  • 介绍 BERT 的架构? 答: BERT 全称 Bidirectional Encoder Representations from Transformers, 有三部分, embedding 模块, 多层 transformer 模块, 以及预微调模块. embedding 模块由三种 embedding 共同组成包括 token, segment, position. (似乎一般的 LLM 都是这个基础架构了)

  • 为什么需要微调? 答: 赋予大模型更加定制化的功能.

  • 介绍 PEFT 中的微调方法?

    • Prefix Tuning. 在模型的输入前增加一个连续且任务特定的向量序列称为 prefix, 固定 PLM 的所有参数只优化特定任务的 prefix. 更具体地, prefix 添加到所有的 transformer 层, 可以将其看作 soft prompt token, 但它并不与具有实际意义的 token 相对应.
    • P-tuning: 类似于 Prefix tuning, 在输入前或其他位置增加(一段连续可微地 virtual token(但是仅限于输入层增加), 将 prompt 转化为可以学习的 embedding 层, 使用 MLP 和 LSTM (称为 prompt encoder) 对 prompt embedding 进行处理.
    • Prompt Tuning

    在这些 tuning 方法之前的工作主要是人工设计模板或者自动化搜索模板, 是离散的.

    Prompt Tuning：可学习向量（通常称为prompt tokens）旨在模仿自然语言提示的形式，它们被设计为引导模型针对特定任务生成特定类型的输出。这些向量通常被看作是任务指导信息的一部分，倾向于用更少量的向量模仿传统的自然语言提示。

    Prefix Tuning：可学习前缀则更多地用于提供输入数据的直接上下文信息，这些前缀作为模型内部表示的一部分，可以影响整个模型的行为。

    来源: 一文辨析清楚LORA、Prompt Tuning、P-Tuning、Adapter 、Prefix等大模型微调方法 - 知乎 (zhihu.com)

  • PEFT 中还有 LoRA, 介绍 LoRA? 答: 背景: 模型是过参数化的, 有内禀维度的概念, 即适配下游任务时模型权重的改变是 low rank 的. 假设微调对预训练权重 带来的权重变化是 , LoRA 的基本思想是用 low rank 的矩阵 的乘积表示 . 表现在模型是上在原模型的旁路增加一个先降维 () 再升维 () 的分支, 只训练 , 然后加到原权重上. 以高斯分布初始化 , 将 初始化为 0 矩阵. 在 Transformer 上 LoRA 表现为将低秩矩阵分别加到 上.

  • 介绍图神经网络(GCN 和 GAT)?

  • 介绍有哪些线性降维方法和非线性降维方法? 简要介绍原理?

  • 介绍 LLaVA 结构? 多模态大模型的基本架构? 大模型的基本架构? 答: tokenize 得到 token, 过 embedding 层, 经过多层 transformer block, 再过 head 得到 logit, 通过 greedy search/beam search/Top-/Top- 采样得到 token, 再 de-tokenize.

  • 怎么验证图像信息丢失的? 答: vision token 的注意力减少, 转移到了 output token 上.

  • 可信度需要做哪些实验?

  • 最近一些新的开源大模型?

  • 介绍学习理论, 泛化理论在研究什么? 答: PAC Learning 是在研究 sample complexity 的问题, 就是在 的置信度下, 以 的 acc 需要多少样本. 什么样的 (在 PAC Learning 的框架下) 是可以学习的.

非常泛泛的一些问题, 但部分内容相对来说也是很不熟悉的.

CRC 遇到的一些问题:

  • PIB 为什么放在 backbone 和 head 之间? 答: 主要参考了 HallE-Switch.
  • KL 散度与 PIB 的作用在某种程度上不是互相冲突的吗? 答: 受限于计算资源没有训练 backbone, LLM 的固有缺陷没有解决, 加上 KL 散度在一定程度上规避了固有缺陷发生时产生的幻觉.
  • 为什么不在每一层 TransformerBlock 里或者每一层 TransformerBlock 后面加一个类似的模块? 答: 受限于算力, 同时这样做大幅度地改动了 LLM 的结构, 不能最大化地利用既有的 LLM.

然后会问 Transformer 相关的比较重要的问题:

自然语言处理相关的问题:

  • Pretraining 和 Fine tuning 是 NLP 领域常用的两阶段迁移学习, 与训练是训练出一个对自然语言有一定理解的与通用模型; 然后再将该模型拿来做特征迁移或者是 fine tune下游的监督式任务. fine tune 一般是冻结大部分层的参数, 仅训练很少量的参数.

关注的知乎问题

  1. Pytorch 是如何实现对 loss 进行反向传播计算梯度的?
  2. 为什么 Transformer 需要进行 Multi-head Attention?
  3. 为什么 BERT 的三个 Embedding 可以相加?
  4. nn.Linear() 和 nn.Embedding() 有什么区别?
  5. 向 GPT 问两次相同的问题, GPT 的回答完全相同的概率可以估计吗?
  6. Transformer 为什么有利于并行计算?

概率问题请看这里.

计划找点离散概率的题目做一下.

2024-05-20 该篇文章被 Baoduo Xu 归为分类: 保研复习

以上
©
Too Young Too Naive 本站由Hexo驱动｜使用Hexo-theme-A4主题