智识神工

第一面

主要是对项目的询问，解释项目的各种地方。

第二面

1. 
   

   自我介绍

   
   


2. 
   

   Double DQN与传统DQN的区别什么？

   
   
   
   
   • 最大的区别在于Q现实的计算方法，DQN中TargetQ的计算方法是
   
   
   
   
   $Y_t^{DQN}=R_{t+1}+\gamma \underset{a}{}Q(S_{t+1},a;{\theta }_t^{-})=R_{t+1}+\gamma Q(S_{t+1},\underset{a}{}Q(S_{t+1},a;{\theta }_t),{\theta }_t)Y\_t^\{DQN\}\; =R\_\{t+1\}+\backslash gamma\; \backslash max\_aQ(S\_\{t+1\},a;\backslash theta\_t^-)=R\_\{t+1\}+\backslash gamma\; Q(S\_\{t+1\},\backslash argmax\_aQ(S\_\{t+1\},a;\backslash theta\_t),\backslash theta\_t)$
   
   
   
   
   • 直接将新的状态输入到老的神经网络中，返回最大的Q值。
   
   
   • Double DQN的Target Q的计算方法是
   
   
   
   
   $Y_t^{DoubleDQN}=R_{t+1}+\gamma Q(S_{t+1},\underset{a}{}Q(S_{t+1},a;{\theta }_t),{\theta }_t^{-})Y\_t^\{Double\; DQN\}=R\_\{t+1\}+\backslash gamma\; Q(S\_\{t+1\},\backslash argmax\_aQ(S\_\{t+1\},a;\backslash theta\_t),\backslash theta\_t^-)$
   
   
   
   
   • 为了防止Q值的过高估计，将新的状态输入到新的神经网络中，得到Q值最大的actin，将此action作为旧的神经网络选择Q值的纵坐标。
   
   
   
   


3. 
   

   为什么传统DQN会出现Q值估计过高的情况？

   
   
   
   
   • 答案
     
     
     
     • 
       

       根据上面传统DQN的计算公式，每次Target Q得到的都是神经网络中当前估算的所有动作价值中的最大值。考虑到通过神经网络网络估算的Q值本身在某些时候会产生正向或负向的误差，在 DQN 的更新方式下神经网络会将正向误差累积。

       
       
     
     
     • 
       

       举例说明，情况大概是

       
       
       
       
     
     
     
     
   
   
   
   


4. 
   

   除了Double DQN以外，还有哪些模型是对DQN做的改进，并且改进地方是什么？

   
   
   
   
   • 答案
     
     
     
     • Dueling DQN：修改了网络框架，改成了两个分支，一个分支是用来输出标量V(s)，一个输出一个向量A(s,a)，两者相加可以得到Q值。实际执行中会给A网络一些约束，让网络难以更新A分支，转而更新V分支，这样的话不需要采样所有的状态行为对，，可以用高效的方法去估计Q值。
     
     
     • 优先经验回放：在采样数据训练Q网络时，不是均匀的从经验回放池中选取的，而是有侧重的选取的，也就是每个数据都有一定的优先级，重要程度不同。在优先经验回放中，不止会改变采样的过程，还会改变更新参数的方法。
     
     
     
     
   
   
   
   


5. 
   

   DQN属于强化学习中分类中的哪种？

   
   
   
   
   • DQN属于强化学习中的model-free强化学习、基于价值的强化学习以及离线策略强化学习
   
   
   
   


6. 
   

   离线策略和在线策略的关键区别是什么？

   
   
   
   
   • 两者的本质区别在于：更新Q值时使用的方法是沿用既定的策略（on-policy）还是使用新策略（off-policy）
   
   
   • on-policy只有一个策略网络，兼顾探索与利用，off-policy有两个，一个是行动网络，一个是目标网络。目标网络不需要与环境交互，学习行为网络采集回来的数据，行为网络与环境进行交互，并且采集数据。
   
   
   • off-policy 和 on-policy 的根本区别在于生成样本的 policy 和参数更新时的 policy 是否相同。对于 on-policy，行为策略和要优化的策略是一个策略，更新了策略后，就用该策略的最新版本对于数据进行采样；对于 off-policy，使用任意的一个行为策略来对于数据进行采样，并利用其更新目标策略。如果举例来说，Q-learning 在计算下一状态的预期收益时使用了 max 操作，直接选择最优动作，而当前 policy 并不一定能选择到最优的 action，因此这里生成样本的 policy 和学习时的 policy 不同，所以 Q-learning 为 off-policy 算法；相对应的SARAS 则是基于当前的 policy 直接执行一次动作选择，然后用这个样本更新当前的 policy，因此生成样本的 policy 和学习时的 policy 相同，所以SARAS 算法为 on-policy 算法。
   
   
   
   


7. 
   

   离线策略为什么能用经验回放机制？

   
   
   
   
   • 离线策略有两个策略，一个是行动策略，一个是目标策略，行动策略需要与环境交互，采样数据，并将采样得到的数据保存起来让目标策略来学习，所采取的存储机制就是经验回放机制。on-policy的策略更新函数要求使用的样本时使用当前目标策略产生的，不能使用经验回放，因为产生这些数据的策略与当前的目标策略不相同。
   
   
   
   


8. 
   

   离线策略和在线策略在计算下一个较优的行动时有什么区别

   
   
   
   
   • 
     

     答案

     
     
     
     
     • off-policy的Q值更新公式是:
     
     
     
     
     $Q(s,a)\leftarrow Q(s,a)+\alpha [r(s,a)+\gamma \underset{a^{\mathrm{\prime }}}{}Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})-Q(s,a)]Q(s,a)\; \backslash larr\; Q(s,a)+\backslash alpha[r(s,a)+\backslash gamma\; \backslash max\_\{a\text{'}\}Q(s\text{'},a\text{'})-Q(s,a)]$
     
     
     
     
     • 
       

       on-policy的Q值更新公式是：

       
       
       $Q(s,a)\leftarrow Q(s,a)+\alpha [r(s,a)+\gamma Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})-Q(s,a)]Q(s,a)\; \backslash larr\; Q(s,a)+\backslash alpha[r(s,a)+\backslash gamma\; Q(s\text{'},a\text{'})-Q(s,a)]$
       
       
     
     
     • 
       

       off-policy是使用下一时刻的最大值来更新当前的Q值，实际采取什么行动并不关心，on-policy则是需要执行两次动作才能更新一次策略，更新用的Q值使用的是下一时刻确切执行的行动来更新Q值。

       
       
     
     
     
     
   
   
   
   


9. 
   

   离线强化学习、在线强化学习、离线策略以及在线策略的关系

   
   
   
   
   • 离线强化学习：offline RL，学习过程中不与环境进行交互，只从dataset中直接学习，而dataset是采用别的策略收集的数据，并且采集数据的策略并不是近似最优策略。
   
   
   • 在线强化学习：online RL，学习过程中，智能体需要和环境进行交互，并且在线强化学习可分为on-policy RL和off-policy RL。
   
   
   
   


10. 
    

    机器学习的归纳偏置

    
    
    
    
    • 在机器学习中，需要对学习的问题做一些关于目标函数的必要假设，成为归纳偏置。或者说是当机器学习去预测其未遇到的输入结果时，所作的一些假设的集合。
    
    
    • 归纳偏置的种类：
      
      
      
      • 最大条件独立性：如果假说能够转换成贝叶斯模型架构，则试着使用最大化条件独立性，这是用于朴素贝叶斯分类器的偏置；
      
      
      • 最小交叉验证误差：当时图在家说中做选择时，挑选那个具有最低交叉验证误差的假说，虽然交叉验证看起来可能无关偏置，但是天下没有免费的午餐理论显式交叉验证是偏置的；
      
      
      • 最大边界：当要在两个类别间化一道分界线时，试图去最大化边界的宽度。这里是用于支持向量机的偏置，这个假设是不同的类别由宽界线来区分的；
      
      
      • 最小描述长度：当构成一个假设时，试图去最小化其假设的描述长度。假设越简单，越可能为真的。奥卡姆剃刀
      
      
      • 最少特征数：除非由充分的证据显式一个特征是有效的，否则它应当被删除。这是特征选择算法背后所使用的假设；
      
      
      • 最近邻居：假设在特征空间中一小区域内大部分的样本是属于一类的。给一个未知类别的样本，猜测它与它最紧接的大部分邻居是属于同一类。这是最近邻算法的偏置
      
      
      
      
    
    
    
    


11. 
    

    计算机图像是怎么被存储的

    
    
    
    
    • 图像的每个像素有RGB三种通道，每个通道的值都是0-255的值，然后整张图像就是一个长$\times \backslash times$宽$\times \backslash times$3的张量。
    
    
    
    


12. 
    

    参数模型和无参数模型

    
    
    
    
    • 参数模型通常假设总体服从某个分布，这个分布可以由一些参数确定，如正态分布由均值和标准差确定，在此基础上构建的模型称为参数模型，比如：逻辑回归（伯努利分布）、线性回归、感知机等；
    
    
    • 非参数模型对于总体的分布不做任何假设或者说数据分布假设自由，只知道其分布的存在，所以就无法得到其分布的相关参数，只能通过非参数统计的方法进行推断，比如：决策树、支持向量机、朴素贝叶斯。
    
    
    
    


13. 
    

    参数模型和无参数模型的优缺点

    
    
    
    
    • 参数模型的优点：
      
      
      
      • 理论容易理解和解释结果
      
      
      • 参数模型学习和训练的速度比较快
      
      
      • 通常不需要大量的数据，在对数据的拟合不很好时表现也不错
      
      
      
      
    
    
    • 参数模型的局限性：
      
      
      
      • 以指定的函数形式来指定学习方式
      
      
      • 通常只能应对简单的问题
      
      
      • 通常无法和潜在的目标函数完全吻合，也就是容易出现欠拟合
      
      
      
      
    
    
    • 非参数模型的优点：
      
      
      
      • 可以拟合许多不同的函数形式
      
      
      • 对于目标函数不做假设或者作出很小的假设
      
      
      • 对于训练样本数据具有良好的拟合性。
      
      
      
      
    
    
    • 非参数模型的局限性：
      
      
      
      • 对于拟合目标函数需要更多的训练数据；
      
      
      • 需要训练的参数比较多，训练速度比较慢；
      
      
      • 有较高的风险发生过拟合，对于预测的效果解释性不高
      
      
      
      
    
    
    
    


14. 
    

    SVM的非线性分类是怎么实现的

    
    
    
    
    • 通过非线性核函数的映射能够完成非线性分类
    
    
    
    


15. 
    

    训练SVM时，是如何调整核函数的超参数的，是如何搜索的？

    
    
    
    
    • $\gamma \backslash gamma$设置的太大容易导致过拟合，$\sigma \backslash sigma$会很小，导致只会作用到支持向量附近，对于未知样本分类效率很差，如果无穷小，理论上高斯核函数的SVM可以拟合任何非线性的数据
    
    
    • $\gamma \backslash gamma$越小，则往着欠拟合的方向走
    
    
    
    


16. 
    

    编程题：二叉树的底视图

    
    

• 
  

  问题

  
  

  给定一棵二叉树，打印它的底部视图。假设一个节点的左右子节点与父节点成 45 度角。

  
  

  例如，下面这棵树的底视图是 7, 5, 8, 6:

  
  

• 
  

  回答

  
  

  用一个哈希表存储结点，key值是结点所在的列，value值是树的结点，然后使用广度优先遍历来更新这个哈希表，根节点为0，左节点在父节点的基础上-1，右节点在父节点的基础上+1，如果key值相同，直接更新value值。最后遍历完结点之后，只需要遍历一遍哈希表就可以了。