问题总结

1. 了解过哪些损失函数。

   • 对数损失函数：$\mathcal{L}=-y(\log{f(x)})-(1-y)(1-\log{f(x)})$

   • 平方损失函数：$\mathcal{L}=(y-f(x))^2$

   • 指数损失函数：$\mathcal{L}=\exp{(-yf(x))}$

   • Hinge损失函数：$\mathcal{L}=max(0,1-yf(x))$

   • 绝对值损失函数：$\mathcal{L}=|y-f(x)|$

2. 从一组数组中找出和最大的最长连续子串。

解决思路：利用动态规划方法，每次找出以第i个元素为末尾组成的子串的最大和。如果前一最大和小于等于零，则当前dp等于当前元素值；如果大于零，则当前dp等于当前值加上前一最大和。每次循环都判断一次前i个元素中子串的最大和，即maxSum。

public int largestSubarray(int[] nums) {
    /**
     * @Description: Find the largest continuous subarray in the array.
     * @Params: [nums] Array.
     * @Return: int The largest sum.
     * @Date: 2019-03-26
     */
    if(nums.length == 0) {
        return 0;
    }
   
    int maxSum = 0;
    int[] dp = new int[nums.length];
    for(int i = 0; i < nums.length; i++) {
        if(i == 0 || dp[i-1] <= 0) {
            dp[i] = nums[i];
        }
        else {
            dp[i] = dp[i-1] + nums[i];
        }
        maxSum = max(dp[i], maxSum);
    }
    return maxSum;
}

1. 写一下逻辑回归的损失函数。

   $$J(\theta)=-\frac{1}{m}[\sum^m_{i=1}(y^{(i)}\log{h_\theta(x^{(i)})+(1-y^{(i)})\log{(1-h_\theta(x^{(i)})})})]$$

2. PCA用代码实现。

a. 将数据中心化，即使其均值为零

b. 计算数据的协方差矩阵

c. 计算协方差矩阵的特征值和特征向量

d. 将特征值进行排序，取前k个特征值，并将其对应的特征向量组合起来形成矩阵P

e. 将矩阵P与原数据矩阵相乘，得到降维后的数据

1. K-Means用代码实现。

a. 从数据中随机选择k个值作为初始均值点

b. 计算其它数据与均值点的距离，将其分配到离它最近的均值点区域，成为某一类别，每个数据点只能被分配到一个聚类中心上

c. 重新计算每一类别的均值点，作为新的聚类中心点

d. 重复以上两步，直到迭代结束

1. 了解过哪些梯度下降的优化方法？有什么区别？

   • Batch Gradient Descent（批梯度下降）
   $$\theta=\theta-\eta\cdot\nabla_\theta J(\theta)$$

   此方法对所有样本计算梯度后求平均，并更新参数。由于每次执行更新操作时，都需要在整个数据集上计算所有梯度，会导致速度较慢，且容易造成内存溢出。对于凸误差函数，此方法能够保证收敛到全局最小值；而对于非凸函数，就可能会收敛到一个局部最小值。

   • SGD（随机梯度下降）
   $$\theta=\theta-\eta\cdot\nabla_\theta J(\theta;x^{(i)};y^{(i)})$$

   此方法每次计算一个样本的梯度后就更新参数，运行速度较快，可用于在线学习。由于高频率的更新操作，导致目标函数容易出现剧烈波动。当学习率较小时，可以达到与批梯度下降一样的结果。

   • Mini-Batch GD（小批量梯度下降）

   此方法结合了上述两种方法的优点，在更新时使用较小批量训练样本的平均梯度，可以减小参数更新的方法，提升收敛的稳定性。

   • Momentum（动量）

   上述梯度下降方法存在着某些问题，如在梯度平缓时下降非常慢，在梯度陡峭时容易抖动；容易陷入局部极小值或者马鞍点；对学习率的设置较为敏感；整体过程若采用一个学习率性能会下降，因为如果特征是稀疏且频率差异很大时，相同的学习率对于不同稀疏或频率的特征学习差异很大，造成不好的效果。

   $$v_t=\gamma v_{t-1}+\eta\nabla_\theta J(\theta)$$ $$\theta = \theta-v_t$$

   为了解决上述问题，提出了动量法。此方法在每次梯度下降时都加上之前运动方向上的动量，在梯度平缓时下降更快，在梯度陡峭时减少抖动。同时，在某个点处梯度方向与运动方向一致，则动量参数增大，若不一致，则动量参数减小。这样就可以得到更快的收敛速度，并可以减少抖动影响。

   • Nesterov（梯度加速法）
   $$v_t=\gamma v_{t-1}+\eta\nabla_\theta J(\theta-\gamma v_{t-1})$$ $$\theta=\theta-v_t$$

   若根据动量进行大步的跳跃，会使得梯度盲目的进行下降，缺少一个合理的限制。此方法能够根据之前的动量进行跳跃，然后计算梯度进行校正，从而实现参数更新，防止大幅震荡，错过最优点。此方法使参数更新与误差函数的斜率相适应，并根据每个参数的重要性来调整和更新参数。

   • Adagrad

   此方法是通过参数来调整合适的学习率，使得下降的过程对特征的稀疏性不敏感，非常适合树立稀疏的特征。

   $$\theta=\theta-\frac{\eta}{\sqrt{grad_{save}+\epsilon}}J(\theta)$$

   grad_save = 0
   while True:
     dx = compute_gradient(x)
     grad_save += dx * dx
     x -= lr / (np.sqrt(grad_save)+1e-7) * dx

   此方法将每一维度的梯度平方都保存下来，并在更新参数的时候，将学习率除以这个参数，使每一维度的学习率不一样，在梯度大时减小下降速度，梯度小时加快下降速度，无需手动调整学习率。

   • Adadelta

   此方法是上一个方法的扩展版本，主要处理学习速率只能单调递减的问题。此方法不是积累所有之前的梯度平方，而是将累积之前梯度的窗口限制到某个固定大小。

   $$E_g^2=\gamma E_g^2+(1-\gamma)J(\theta)^2$$ $$\theta=\theta-\frac{\eta}{\sqrt{E_g^2+\epsilon}} J(\theta)$$
   • RMSprop

   此方法是对上一个方法的改进，主要增加了一个延迟因子平衡梯度平方和上一个参数。

   $$\theta=\theta-\frac{\eta}{\sqrt{decay\cdot grad_{save}+(1-decay)J(\theta)^2}}J(\theta)$$

   grad_save = 0
   while True:
     dx = compute_gradient(x)
     grad_save = decay * grad_save + (1-decay) * dx * dx
     x -= lr / (np.sqrt(grad_save)+1e-7) * dx

   • Adam

   此方法结合了动量法和RMSprop的特征，增加了自适应学习率。

2. 写一下Adam的优化公式。

   first_moment = 0
   second_moment = 0
   while True:
     # beta1=0.9 beta2=0.999
     dx = compute_gradient(x)
     # Momentum
     first_moment = beta1 * first_moment + (1-beta1) * dx
     # RMSProp
     second_moment = beta2 * second_moment + (1-beta2) * dx * dx
     # Bias correction
     first_unbias = first_moment / (1-beta1**2)
     second_unbias = second_moment / (1-beta2**2)
     # RMSProp
     x -= lr * first_unbias / (np.sqrt(second_unbias)+1e-7)

3. 写一下逻辑回归的损失函数。

   $$Loss=y_{label}\log{y}+(1-y_{label})\log{(1-y)}$$ $$J(\theta)=\frac{1}{2m}\sum^m_{i=1}(y^{(i)}-y_{label}^{(i)})^2$$

4. 如何理解卷积和池化这两个过程？

   卷积：一维信号的卷积：$ y[n]=x[n]*h[n]=\sum_kx[k]\cdot h[n-k] $，其中$x[n]$为输入信号，$h[n]$为单位响应。所以输出即为输入的延迟相应叠加，即本质为加权积分。

   二维信号的卷积：$ y[m,n]=x[m,n]*h[m,n]=\sum_i\sum_jx[i,j]\cdot h[m-i,n-j] $，引入了卷积核的概念，对应于一维卷积中的单位响应。因此，二维卷积也是加权积分，但是其中卷积核进行了水平和竖直方向的翻转，可以定义为转置卷积。

   卷积核具有局部性的属性，它仅关注于局部特征，局部的范围取决于卷积核的大小。图像与卷积核卷积的过程即为对图像的频域信息进行选择的过程。图像中边缘和轮廓属于高频信息，区域强度属于低频信息，这种理论指导了如何设计卷积核。

   在卷积神经网络中，每一层之间的卷积核参数是固定的，且会多一个偏置参数，提升非线性因素，所以在卷积网络中由于卷积核和偏置是固定的，相比于神经网络大大降低了参数数量。卷积核中的参数是通过梯度优化得到的，所以参数的初始化就显得尤为重要。

   池化：池化的本质就是采样，选择某种方式对特征进行压缩。可以减少参数数量，降低特征维度，有效减少后续网络层所需要的参数。其次可以增强特征的旋转或者位移不变性，增强网络的鲁棒性。

5. ResNet和GoogleNet的原理。

   ResNet的本质就是降低了数据中信息的冗余度。具体说来，就是对非冗余信息采用了线性激活（通过skip connection获得无冗余的identity部分），然后对冗余信息采用了非线性激活（通过ReLU对identity之外的其余部分进行信息提取/过滤，提取出的有用信息即是残差）。其中，提取identity这一步，就是ResNet思想的核心。 由于identity之外的其余部分的信息冗余度较高，因此在对其使用ReLU进行非线性激活时，丢失的有用信息也会较少，ReLU层输出为0的可能性也会较低。这就降低了在反向传播时ReLU的梯度消失的概率，从而便于网络的加深，以大大地发挥深度网络的潜能。 其次，特征复用能加快模型的学习速度，因为参数的优化收敛得快（从identity的基础上直接学习残差，总比从头学习全部来得快）。

   GoogleNet以降低参数为目的，利用全局平均池化层代替了全连接层，其次大量使用了$1\times1$的卷积核。Inception结构中，每一层中拥有多个卷积核，但在同一位置中不同通道下的卷积核输出结果相关性极高。$1\times1$的卷积核可以把这些相关性高、同一位置、不同通道下的特征结合起来。$3\times3$，$5\times5$的卷积核可以保证特征多样性。$1\times1$卷积核在实现多个特征图的结合，整合不同通道间的信息的同时，可以实现升维和降维的效果。

6. 一个二维数组中每一行和每一列都是以升序排列，用最快的方法找出某个值。

   vector<int> searchMatrix(vector<vector<int>> &matrix, int target)
   {
     vector<int> res;
     if (matrix.empty() || matrix[0].empty())
       return res;
     int rows = matrix.size();
     int cols = matrix[0].size();
     int row = 0, col = cols-1;
     while (row < rows && col >= 0)
     {
       if (matrix[row][col] == target)
       {
         res.push_back(row);
         res.push_back(col);
         return res;
       }
       else if (matrix[row][col] > target)
       {
         col--;
       }
       else
       {
         row++;
       }
     }
     return res;
   }

1. A字符串中含有大量字符，B字符串中含有不超过100的少量字符，C字符串中也包含不超过100的少量字符，B字符串的长度与C的长度不一定相等。问题：从A中找出所有与B相同的子串，并将其替换为C。

KMP算法

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void GetNext(string p, vector<int> &next)
{
    /**
     * kmp算法中，先建立匹配字符串的next数组
     * 即找数组中以某个点为终止的子字符串的前缀后缀最大公共长度
     * 而next数组就是将最大公共长度的数值向右移一位
     * 第一个元素为-1
     * ABCDABD
     * ->
     * 0,0,0,0,1,2,0（最大公共长度数组）
     * ->
     * -1,0,0,0,0,1,2（next数组）
     */

    int p_len = p.length();
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < p_len-1)
    {
        if (k == -1 || p[j] == p[k])
        {
            k++;
            j++;
            if (p[j] != p[k])
                next[j] = k;
            else
                next[j] = next[k];
        }
        else
        {
            k = next[k];
        }
    }
}

vector<int> KmpSearch(string a, string b)
{
    /**
     * kmp算法去找匹配字符串在原字符串的起点位置
     */

    vector<int> index;
    int big_len = a.length();
    int small_len = b.length();
    int i = 0, j = 0;
    vector<int> next(b.length(), 0);
    GetNext(b, next);
    while (i < big_len && j < small_len)
    {   
        if (j == -1 || a[i] == b[j])
        {
            i++;
            j++;
        }
        else
        {
            //如果当前元素不匹配，将匹配字符串的位置回退到前一子字符串的公共前缀的后一个元素
            j = next[j];
        }

        if (j == small_len)
        {
            index.push_back(i-j);
            j = 0;
        }
    }
    return index;
}

vector<int> NormalSearch(string a, string b)
{
    /**
     * 传统方法去找匹配字符串在原字符串的起点位置
     */

    vector<int> index;
    int big_len = a.length();
    int small_len = b.length();
    int i = 0, j = 0;
    while (i < big_len && j < small_len)
    {
        if (a[i] == b[j])
        {
            i++;
            j++;
        }
        else
        {
            i++;
            j = 0;
        }

        if (j == small_len)
        {
            index.push_back(i-j);
            j = 0;
        }
    }
    return index;
}

string Kmp(string a, string b, string c)
{
    vector<int> index = KmpSearch(a, b);
    // vector<int> index = NormalSearch(a, b);
    string res = "";
    int change_index = 0;
    int i = 0;
    for ( ; i < a.length(); i++)
    {
        if (i == index[change_index])
        {
            for (int j = 0; j < c.length(); j++)
            {
                res += c[j];
            }
            i += b.length()-1;
            change_index++;
            if (change_index == index.size())
                break;
        }
        else
        {
            res += a[i];
        }
    }
    while (i < a.length())
    {
        res += a[i++];
    }
    return res;
}

int main(int argc, char const *argv[])
{
    string a = "eiqwuhfiqwheofsalknfa*yanganzhe*ashifeqwnfanzhejfoiaejwor*yanganzhe*idasho";
    string b = "yanganzhe";
    string c = "Avery";

    cout << "原字符串: " << a << endl;

    string res = Kmp(a, b, c);
    cout << "新字符串: " << res;
    return 0;
}

1. 说一下对反向传播的理解。

神经网络的目的就是拟合，即给定一些样本点，通过合适的函数曲线去拟合关系变化。学习的目的就是通过调整函数中的参数，使得最终所得的结果与预想的结果之间的差距越来越小。大多数的实际问题都是非凸的，即存在很多局部最小值，通过简单的梯度下降方法就可以有效求解出最优结果。其中链式法则在高维情况时就变成了Jacobian矩阵乘法。

1. 介绍下Adam优化方法。

结合了动量法和RMSprop的特征，增加了自适应学习率

1. 如何防止过拟合效应？有哪些方法。

引入正则化、Dropout使神经元随机失活、增加样本数量、提前终止训练、加入BN层。

1. 如何防止梯度爆炸和梯度消失？

预训练加微调、权重正则化、ReLU激活函数、加入BN层、引入残差结构。

梯度剪切（设置一个梯度剪切阈值，更新梯度时如果超过这个阈值，那么就限制在这个范围之内，防止梯度爆炸）

LSTM（每次更新参数时，单元会保存前几次训练的残留记忆，会对当前更新过程产生影响）

1. ResNet中是如何防止梯度爆炸或消失的问题的？

使用ReLU激活函数、使用跳跃连接。

1. $1*1$卷积核的作用。

可以起到一个跨通道聚合特征的作用，同时可以起升维和降维的作用。

1. 在实验中是如何解决损失值不收敛的问题？

对数据做归一化、检查梯度、对数据进行预处理、使用正则化、Batch Size太大、学习率太大或太小、激活函数不适合、梯度消失问题、参数初始化问题（面试官和我讨论了很久，他说权重初始化并不影响损失的收敛）、网络太深。

1. 有三个球筒A、B、C，每个筒都包含三种不同颜色的球，分别为红色、蓝色、白色，每个筒中每个颜色球的个数为$r_i,b_i,w_i(i=1,2,3)$，问题：从所有筒中抽取一个球，结果为红色，求其属于A筒的概率。

所有颜色球的总数为：$ sum=\sum r_i+\sum b_i+\sum w_i $

红色球的概率为：$ p_r=\sum r_i/sum $

蓝色球的概率为：$ p_b=\sum b_i/sum $

白色球的概率为：$ p_w=\sum w_i/sum $

球属于A筒的概率为：$ p_A=(r_1+b_1+w_1)/sum $

球属于B筒的概率为：$ p_B=(r_2+b_2+w_2)/sum $

球属于C筒的概率为：$ p_C=(r_3+b_3+w_3)/sum $

第i个筒中红球的概率为：$ p(r|i)=r_i/(r_i+b_i+w_i) $

第i个筒中蓝球的概率为：$ p(b|i)=b_i/(r_i+b_i+w_i) $

第i个筒中白球的概率为：$ p(w|i)=w_i/(r_i+b_i+w_i) $

从所有筒中抽取一个球，结果为红色，对应于A筒的概率为：（贝叶斯公式）

$$p(A_i|B)=\frac{p(B|A_i)p(A_i)}{\sum_ip(B|A_i)p(A_i)}$$ $$p(tube=A|ball=red)=\frac{P_{ball=red|tube=A}\cdot P_{tube=A}}{\sum_{A,B,C}P_{ball=red|tude=i}\cdot P_{tude=i}}=\frac{p(r|A)\cdot p(A)}{p(r|A)\cdot p(A)+p(r|B)\cdot p(B)+p(r|C)\cdot p(C)}$$

即结果为：$ \frac{r_1}{r_1+r_2+r_3}$

1. 了解过哪些机器学习方法。

逻辑回归、支持向量机、决策树、主成分分析。

赞赏