美团：2022 秋招【北斗】搜索推荐广告高级算法工程师

一面

项目与论文
算法题

面试题 10.09. 排序矩阵查找 sorted-matrix-search-lcci
54 螺旋矩阵 spiral-matrix

LR（线性回归）
- 公式
  $\begin{align} \mbox{LR}(x) &= \text{sigmoid}(\text{linear(x)}) \\ &= \frac{1}{1+e^{-wx+b}} \end{align}$
- 设计的意义与目的
  
  通过一个超平面对数据进行划分。
二分类问题损失函数
- 交叉熵公式
  $\text{CrossEntropy}(y,\hat{y}) = -\frac{1}{K}\sum^K_i\left(y_i\cdot\log \hat y_i + (1-y_i)\cdot\log(1-\hat y_i)\right)$
  其中， $K$ 为类别数。
- 交叉熵设计原理
  
  交叉熵的公式中包含两项信息熵的计算，通过 Logits 和标签的信息熵，衡量判断输出与类别之间的关联性（二者分布上的差异）。
  
  $y\cdot \log y$ 和 $(1-y)\cdot\log(1-\hat y)$ 分别衡量了输出值 $\hat y$ 与当前样本“属于类别 $y$ ”和“不属于类别 $y$ ”这两种情况的关联性，使得在 y=0 或 y=1 时（对于各个类别而言）都能衡量输出的 Logits 与具体类别的关联。
- 是否可以使用 MSE，为什么
  
  不可以。主要原因如下：
  1. 物理意义上，MSE 衡量的是几何空间的欧氏距离，而分类问题中每个类别的标签是离散的 $0$ 和 $1$ ，本身不具备几何空间的意义；
    
    信息学中，交叉熵衡量的是两个分布之间的差异，可用于衡量模型预测的概率分布和真实标签的类别分布是否相似。
  2. 计算上，分类模型输出的概率一般会经过 softmax 归一化，归一化后的值使用 MSE 会导致不符合预期的梯度，而使用交叉熵则无此问题。
    
    如三分类问题中，标签为 $(1,0,0)$ ，模型输出为 $(a,b,c)$ ，此时的损失值为：
    $\begin{align} \mbox{MSE} &= (a-1)^2+(b-0)^2+(c-0)^2 \\ &= (a-1)^2+b^2+c^2 \\ \mbox{CrossEntropy} &= - (1\cdot\log a + 0\cdot\log b + 0\cdot\log c) \\ &= -\log a \end{align}$
    可以看到，MSE 会考虑各个类别的概率，其最小化的目标除了让正确类别的概率最大化外，还会让错误类别的概率平均（这一步是不必要的，可能会导致梯度不符合预期，这也是其优化函数非凸的难以优化的直接表现）；
    
    而交叉熵则只针对正确的类别进行计算，就没存在 MSE 中的问题。
梯度更新
- 如何更新（公式）
  
  对于第 $t$ 个时间步，其参数为时间步 $t-1$ 的参数减去梯度乘以学习率： $w_t = w_{t-1} - lr \cdot grad$ 。
- 其他的更新方法
  
  带动量的优化器，如动量 SGD 或者 Adam。
- 动量 SGD 公式
  
  参考 https://pytorch.org/docs/stable/generated/torch.optim.SGD.html#torch.optim.SGD 。
- Adam 公式
  
  参考 https://pytorch.org/docs/stable/generated/torch.optim.Adam.html#torch.optim.Adam 。
特征/参数初始化
- 常用的初始化方法
  
  Random、xavier/kaiming Normal、xavier/kaiming Uniform。
- 是否可以初始化为 0
  
  不可以。
  
  特征初始化为零会导致后续所有的网络中的权重 $W$ 失效，只保留偏差 $b$ 生效，相当于严重降低了模型的复杂度，从而降低了其学习能力。
  
  参数初始化为零虽然经过非线性的激活函数后能更新参数，但是同一层所有参数的梯度都是相同的，使得更新后的同一层参数值是相同的，最终导致模型虽然能训练但整体是无效的。

二面

项目
概率分析：给定 1 个骰子，假设抛掷 300 次，如何判定这个骰子是否公平；

卡方检验？
coding：输出字符串所有的顺序子串

输入："ABC"

输出：[["A","B","C"],["AB","C"],["A","BC"],["ABC"]]

思路：递归枚举即可。