字节｜算法岗｜挂经｜2021｜

21905

2020.10.26

2021.08.27

发布于未知归属地

字节跳动机器学习深度学习 Deep Learning 求职面试

记录一次失败的字节跳动面试「算法」

简介
神经网络参数如何初始化
1. Xavier 初始化
2. He 初始化
Dropout在forward里面怎么做
L1和L2正则化的区别
AUC是什么，写一下代码
编程题，类似实现 ndarray.shape

简介

字节跳动面崩了，记录一下。看大家都在发面经，发个挂经反馈一下。

字节想了想面试了5次。挂了2次，也是有点惨。

大多数内容来源自网络搜集的答案，如果有没有附上的出处可以提醒我

祝愿大家都找到满意的offer

神经网络参数如何初始化

Deeplearning.ai的教程Initializing neural networks :

首先神经网络参数不能初始化为0或者任意相同的常量。如果网络参数都是相同常量，那个每个隐层节点对最终节点的贡献度一致，导致各个节点按照相同的方式更新。不能使不同神经元学习不同的东西。

考虑线性模型，初始权重过小导致梯度消失，过大梯度爆炸。需要寻找合适的参数，有两个假设为

激活函数输出后的均值为0
每激活函数输出的方差应该在层与层间保持相同

假设某层的前传播公式为

a^{[l - 1]} z^{[l]} a^{[l]} = g^{[l - a]} (z^{[l - 1]}) = W^{[l]} a^{[l - 1]} + b^{[l]} = g^{[l]} (z^{[l]})

对应假设为

E [a^{[l - 1]}] Va r (a^{[l - 1]}) = E [a^{[l]}] = Va r (a^{[l]})

Xavier 初始化

一般建议使用 Xavier 初始化:

W^{[l]} b^{[l]} \sim N (μ = 0, σ^{2} = \frac{1}{n ^{[l - 1]}}) = 0

权重通过正态分布采样， $n^{[l - 1]}$ 是上层神经元的个数。偏置初始化为0. 推导过程如下，假设网络激活函数为 $t anh$

z^{[l]} a^{[l]} = W^{[l]} a^{[l - 1]} + b^{[l]} = t anh (z^{[l]})

其中:

t anh (x) = \frac{1 - e ^{- 2 x}}{1 + e ^{- 2 x}}

目的需要找到两层间方差的对应关系，即 $Va r (a^{[l - 1]})$ 和 $Va r (a^{[l]})$ 。首先注意tanh的性质： $t anh (- x) = - t anh (x)$ 另外就是在接近0的时候 $t anh (x) \approx x$ 。在初始化后，参数都是很小的值，有

Va r (a^{[l]}) = Va r (t anh (z^{[l]})) \approx Va r (z^{[l]})

考虑 $z^{[l]} = W^{[l]} a^{[l - 1]} + b^{[l]} = v ec t or (z_{1}^{[l]}, z_{2}^{[l]}, \dots, z_{3}^{[l]})$ ，对应的关系可以推导为

z_{k}^{[l]} = j = 1 \sum n^{[l - 1]} w_{kj}^{[l]} a_{j}^{[l - 1]} + b_{k}^{[l]}

考虑每个元素的方差, 注意偏置项都是0，可以省略掉

Va r (a_{k}^{[l]}) = Va r (z_{k}^{[l]}) = Va r ⎝ ⎛ j = 1 \sum n^{[l - 1]} w_{kj}^{[l]} a_{j}^{[l - 1]} ⎠ ⎞

先使用3个假设：

权重独立同分布
输入独立同分布
权重和输入相互独立

继续展开：

Va r (a_{k}^{[l]}) = Va r (z_{k}^{[l]}) = Va r ⎝ ⎛ j = 1 \sum n^{[l - 1]} w_{kj}^{[l]} a_{j}^{[l - 1]} ⎠ ⎞ = j = 1 \sum n^{[l - 1]} Va r (w_{kj}^{[l]} a_{j}^{[l - 1]})

考虑方差展开式

Va r (w_{i} x_{i}) = E [w_{i}]^{2} Va r (x_{i}) + E [x_{i}]^{2} Va r (w_{i}) + Va r (w_{i}) Va r (x_{i})

注意输入和权重的期望是0，代入可以得到下个公式，这个公式是方差缩放公式。

Va r (z_{k}^{[l]}) = j = 1 \sum n^{[l - 1]} Va r (w_{kj}^{[l]}) Va r (a_{j}^{[l - 1]}) = n^{[l - 1]} Va r (W^{[l]}) Va r (a^{[l - 1]})

上述等式成立的时候，需要有下列假设成立

Va r (w_{kj}^{[l]}) = Va r (w_{11}^{[l]}) = Va r (w_{12}^{[l]}) = \dots = Va r (W^{[l]})

同理要满足

Va r (z^{[l]}) = Va r (z_{k}^{[l]})

那么要满足开始的假设

Va r (a^{[l]}) = n^{[l - 1]} Va r (W^{[l]}) Va r (a^{[l - 1]}) = Va r (a^{[l - 1]})

需要有

Va r (W^{[l]}) = \frac{1}{n ^{[l - 1]}}

在实际过过程中，Xavier初始化方式有两种方差，如下

W^{[l]} W^{[l]} \sim N (0, \frac{1}{n ^{[l - 1]}}) \sim N (0, \frac{2}{n ^{[l - 1]} + n ^{[l]}})

He 初始化

使用ReLu通常一般神经元输出为0，此时分布的方差为恒等函数时候的一半，此时考虑前向传播，理想方差为

Va r (w^{[l]}) = \frac{2}{n ^{[l - 1]}}

采用高斯分布方差如上，如果采用区间为 $[- r, r]$ 均匀分布初始化参数，那么 $r = \frac{6}{n ^{[l - 1]}}$

Dropout在forward里面怎么做

Dropout来自论文「Dropout: A Simple Way to Prevent Neural Networks from Overfitting」

在前向传播过程中，公式为

r_{j}^{(l)} y^{(l)} z_{i}^{(l + 1)} y_{i}^{(l + 1)} \sim Bernoulli (p) = r^{(l)} * y^{(l)} = w_{i}^{(l + 1)} y^{(l)} + b_{i}^{(l + 1)} = f (z_{i}^{(l + 1)})

$r$ 是概率1为 $p$ 的伯努利分布生成的向量。在前向传播过程中，训练得到参数被更新 $W_{t es t}^{(l)} = p W^{(l)}$

L1和L2正则化的区别

参考「百面机器学习」

L1 正则化使模型参数具有稀疏性。即很多权重参数都是0. 优点是可以自动做特征选择。 L2正则化对防止模型过拟合效果更好，因为网络倾向去使用所有的输入特征而不是严重依赖小部分特征。

考虑L1正则

J (w) = \frac{1}{n} ∥ y - Xw ∥^{2} + λ ∥ w ∥

最小化代价函数等价于

w min \frac{1}{n} ∥ y - Xw ∥^{2} s . t . ∥ w ∥ \leq C

函数空间和解空间已经有了，最有参数为解空间和函数空间的交集中使得函数最小的点。「百面机器学习」绘制出了下图

百面机器学习

最优解是解空间边缘和函数等高线的交点。L1棱形解空间更容易在尖角处与等高线碰撞得到稀疏解。

AUC是什么，写一下代码

Probabilistic interpretation of AUC

The Probabilistic Interpretation of AUC

AUC时ROC曲线下的面积。 ROC通过FP(假阳性)和TP(真阳性)计算。对于二分类需要考虑混淆矩阵

			预测
		$\overset{y}{^} = c$	$\overset{y}{^} \neq = c$
真实类别	$y = c$	TP	FN
	$y \neq = c$	FP	TN

ROC(receiver operating characteristic curve) 通过 TPR 和 FPR得到

TPR = \frac{TP}{TP + FN}

FPR = \frac{FP}{FP + TN}

通过FPR为横轴， TPR为纵轴，在不同分类置信度阈值下，可以绘制ROC曲线。如下图，ROC一定会经过(0, 0), (1, 1)：

ROC曲线

AUC是ROC曲线下的面积。ROC曲线有一个很好的性质，在测试集正负样本分布变化的时候，ROC曲线保持不变。AUC计算方式主要有两种：

从预测的置信度排序，按照排序后由高到低选择选择阈值，计算对应TPR和 FPR 绘制曲线
AUC具有概率学上的意义：随机选取一个正样本和一个负样本，分类器给正样本打分大于分类器给负样本打分的概率。使用组合数学求解

A U C = \frac{\sum _{i \in p os i t i v e Cl a ss} r an k _{i} - \frac{M ( 1 + M )}{2}}{M \times N}

公式中 $M$ 和 $N$ 分别为正负样本个数。 $r ank$ 是将样本按照置信度排序后，置信度最高的样本 $r ank = M + N$

python 代码如下, 来自AUC曲线计算方法及代码实现

import numpy as np
from sklearn.metrics import roc_auc_score


def calc_auc(y_labels, y_scores):
    f = list(zip(y_scores, y_labels))
    rank = [values2 for values1, values2 in sorted(f, key=lambda x: x[0])]
    rankList = [i + 1 for i in range(len(rank)) if rank[i] == 1]
    pos_cnt = np.sum(y_labels == 1)
    neg_cnt = np.sum(y_labels == 0)
    auc = (np.sum(rankList) - pos_cnt * (pos_cnt + 1) / 2) / (pos_cnt * neg_cnt)
    return auc


def get_score():
    # 随机生成100组label和score
    y_labels = np.zeros(100)
    y_scores = np.zeros(100)
    for i in range(100):
        y_labels[i] = np.random.choice([0, 1])
        y_scores[i] = np.random.random()
    return y_labels, y_scores


if __name__ == '__main__':
    y_labels, y_scores = get_score()
    print('sklearn AUC:', roc_auc_score(y_labels, y_scores))
    print(calc_auc(y_labels, y_scores))

编程题，类似实现 ndarray.shape

以字符串形式给出一个 ndarray，如 "[[[7,7,7],[8,8,8]]]"，请写一个程序，输出它的 shape，以上面的例子为例，输出：(1,2,3)。

输入："[[[0.7,7,7],[8,8,8]]]"，输出：(1,2,3).
输入："[[[7],[7],[7]],[[8],[8],[8]]]”, 输出：(2,3,1)
输入："[[[7],[7],[]]]”, 输出：error

代码如下，面试没写出来，递归来统计，从内层到外层一次统计。

def _count_shape(strs):
    cnt = 0
    for idx, c in enumerate(strs):
        if c == '[':
            cnt += 1
        else:
            break
    if cnt == 0:
        return False, [-1]
    if cnt == 1:
        nums = strs[1:-1].split(',')
        try:
            nums = list(map(float, nums))
        except Exception as E:
            return False, [-1]
        if len(nums) == 0:
            return False, [-1]
        return True, [len(nums)]
    else:
        splits = []
        pre = ''
        cur_cnt = 0
        idx = 1
        while idx < len(strs) - 1:
            c = strs[idx]
            if c == '[':
                cur_cnt += 1
            elif c == ']':
                cur_cnt -= 1
            pre += c
            idx += 1
            if cur_cnt == 0:
                splits.append(pre)
                pre = ''
                while idx < len(strs) - 1 and strs[idx] != '[':
                    idx += 1
        ret = [_count_shape(_strs) for _strs in splits]
        if not ret:
            return False, [-1]
        isvalid, r = ret[0]
        if not isvalid:
            return False, [-1]
        for ci, cr in ret[1:]:
            if not ci or r != cr:
                return False, [-1]
        return True, r + [len(ret)]


def shape(strs):
    ret, shape = _count_shape(strs)
    if ret:
        return shape[::-1]
    else:
        print('error')
        return -1


if __name__ == '__main__':
    print(shape("[[[0.7,7,7],[8,8,8]]]"))
    print(shape("[[[7],[7],[7]],[[8],[8],[8]]]"))
    print(shape("[[[7],[7],[]]]"))

运行结果

[1, 2, 3]
[2, 3, 1]
error
-1