发表于 | 更新于 | 评论数：
本文字数： 4.6k | 阅读时长 ≈ 4 分钟

一、概述

  1. 提出一种较为通用的，去除繁杂假设的，高效的算法层次强化学习算法框架；

  2. 框架

    $High-Level \space\space\space\space\space {———>}^{auto} \space\space\space\space Goal ————> ^{supervised} \space\space\space\space Low-Level controller$

  3. 使用Off-Policy进行High-level及Low-level训练，通用化的设计，使得较好的在low-level controller中使用DDPG，TD3等确定性、off-policy的算法，兼容性强；

  4. 提出针对于High-level的Off-Policy Correction。

阅读全文 »

发表于 | 更新于 | 评论数：
本文字数： 9k | 阅读时长 ≈ 8 分钟

参考

【强化学习】确定性策略强化学习-DPG&DDPG算法推导及分析

Deep Reinforcement Learning - 1. DDPG原理和算法

一、确定性策略梯度

​ Deepmind的D.Silver等在2014年提出DPG： Deterministic Policy Gradient， 即确定性的行为策略，每一步的行为通过函数$μ$直接获得确定的值：

​ 这个函数$μ$即最优行为策略，不再是一个需要采样的随机策略。为何需要确定性的策略？简单来说，PG方法有以下缺陷：

​ 即使通过PG学习得到了随机策略之后，在每一步行为时，我们还需要对得到的最优策略概率分布进行采样，才能获得action的具体值；而action通常是高维的向量，比如25维、50维，在高维的action空间的频繁采样，无疑是很耗费计算能力的。在PG的学习过程中，每一步计算policy gradient都需要在整个action space进行积分:

​ 这个积分我们一般通过Monte Carlo 采样来进行估算，需要在高维的action空间进行采样，耗费计算能力。如果采取简单的Greedy策略，即每一步求解$ argmax_a Q(s,a)$也不可行，因为在连续的、高维度的action空间，如果每一步都求全局最优解，太耗费计算性能。
​ 将DPG算法融合进actor-critic框架，结合Q-learning或者Gradient Q-learning这些传统的Q函数学习方法，经过训练得到一个确定性的最优行为策略函数。

阅读全文 »

发表于 | 评论数：
本文字数： 3k | 阅读时长 ≈ 3 分钟

距离衡量指标

聚类效果衡量指标

  • 参考: 聚类模型评估

  • 常用评估:

    • 类别信息已知

      • 调和兰德系数 (ARI)
      • 调和互信息 (AMI)
      • 调和平均 (V-Measure)

    • 类别信息未知

      • 轮廓系数 (Silhouette Coefficient)

基于划分的聚类

层次聚类

参考

  • 自上而下的分裂层次聚类(DIANA)

  • 自下而上的凝聚层次聚类(AGNES)

密度聚类

谱聚类

  • 谱聚类基本原理: 参考 谱聚类算法(Spectral Clustering)

  • 谱聚类与PCA的异同: 参考 特征值与特征向量，PCA和谱聚类

  • 一般步骤：

    1）输入：相似度矩阵S（Rn∗n）、目标聚类数目k （在此之前需要完成两项工作： 1.选择合适的相似度函数，2.选择合适的聚类数目k）
    2）构造出相似图及其赋权的邻接矩阵（weighted adjacency matrix） （这一步需要选择：相似图的类型以及相应的参数）
    3）计算出相似图的Laplacian矩阵 （这一步需要选择：Laplacian矩阵的类型）
    4）计算Laplacian矩阵的前k个特征值对应的特征向量，以这k个特征向量为列，拼出新的矩阵Un∗k）
    5）视矩阵U的每一行为Rk中的一个点，对这n个点y1，y2，…yn进行k−means聚类，得到k个聚类C1，C2，…Ck
    6）输出聚类结果A1,A2,…Ak：yi被分到Cj中的哪一类，xi就被分到相应的Aj类

发表于 | 更新于 | 评论数：
本文字数： 24k | 阅读时长 ≈ 22 分钟

[Leetcode 198] 打家劫舍

  • 解法：一个经典的dp题，从选与不选的角度进行考虑，

    终止条件是第0个的时候只有一个可以选，有两个的时候，选二者中大的那个。

  • 参考：动态规划（第2讲 第一个demo）

  • 代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
    public:
        int rob(vector<int>& nums) {
            if(nums.empty()) return 0;
            if(nums.size()==1) return nums[0];
            vector<int > dp(nums.size(), 0); //构造dp数组
                    
            // dp终止条件
            dp[0] = nums[0];
            dp[1] = max(nums[1], nums[0]);
            
            // dp递推
            for(int i=2 ; i<nums.size(); i++){
                    dp[i] = max((dp[i-2] + nums[i]), (dp[i-1]));
            }
            return dp[nums.size()-1];
        }
    };

[Leetcode 213] 打家劫舍 II

  • 解法：由于有环，那么给他拆分成[0,n-1] 和 [1,n]两个部分进行分别dp，最后取两个区间中取值大的。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size() == 1) return nums[0];
        if(nums.size() == 2) return max(nums[0],  nums[1]);
        
        vector<int> dp_n_1(nums.size(), 0); //[0,n-1]
        vector<int> dp_n(nums.size(), 0); //[1, n]
        
        dp_n[0] = 0;
        dp_n[1] = nums[1];
        dp_n[2] = max(nums[1], nums[2]);
        
        dp_n_1[0] = nums[0];
        dp_n_1[1] = max(nums[0], nums[1]);
        dp_n_1[2] = max(dp_n_1[1], nums[2]);
        
        for(int i = 2; i<nums.size()-1; i++){
            dp_n_1[i] = max((dp_n_1[i-2] + nums[i]),(dp_n_1[i-1]));
        }
        
        for(int i = 3; i<nums.size(); i++){
            dp_n[i] = max((dp_n[i-2] + nums[i]),(dp_n[i-1]));
        }
        
        return max(dp_n_1[nums.size()-2], dp_n[nums.size()-1]);
                                               
    }
};

[Leetcode 139] 单词拆分

  • 解法(4种)

    • 解法一: DFS

    • 解法二: 记忆化DFS

    • 解法三: bottom up DP

      [子问题定义] : DP子问题是从0开始到当前位置的子串是否可分(dp[i] == true?)，当前位置总共有n个可能，所以子问题的个数是n个。

      使用hashset转储dict

      构建dp数组，默认初始空串是可分的即dp[0]=1,

      遍历初始串，验证从前面可分的子串尾部到当前位置的字符串([j为dp[j]==1, i])是否在字典中，如果在字典中则记录当前位置可分

    • 解法四: Bottom up DP + max trick

    阅读全文 »

发表于 | 更新于 | 评论数：
本文字数： 19k | 阅读时长 ≈ 17 分钟

一、 重要性采样

TRPO和PPO主要思想的数学基础是重要性采样

  • 重要性采样：$x_i $是从$p(x)$分布中采样得到的， 但是$p(x)$的值往往无法直接获得，需要通过其他分布$q(x)$进行间接采样获得。

  • 条件：

    • $p$分布与$q$分布需要相近，才能得到较好的效果。

  • 用在强化学习里面:

    • 由于策略梯度原始公式中的 新策略分布难以得到，因而使用旧策略进行间接采样，以使得未知项变成可估计的已知项进行计算。
    阅读全文 »

发表于 | 更新于 | 评论数：
本文字数： 9.4k | 阅读时长 ≈ 9 分钟

参考

  1. 令人拍案叫绝的Wasserstein GAN
  2. WGAN最新进展：从weight clipping到gradient penalty
  3. Ten paper: GAN-GP(Gradient Penalty)
  4. 深度有趣 | 16 令人拍案叫绝的WGAN
  5. 开发者自述：我是这样学习 GAN 的
  6. 推荐：生成对抗网络综述

一、 基本概念

  1. 符号定义

    $D$ 判别模型， $G$ 生成模型

    $x​$ 数据集中的数据分布，$z​$ 某种随机分布

  2. 目标函数（详细参见第四部分）(找一系列D让其对应的V最大，然后在这些最大的V里面选一个最小的)

    • D Loss (MC采样，相当于训练二分类器$x \sim P_{data}$一类，$\hat{x} \sim G(z)$一类):

    • G Loss原始 （MiniMax GAN[MMGAN]）(判别器越好，生成器梯度消失越严重)

    • G Loss改进 (Non-saturating GAN[NSGAN] )(-log trick) (其实与原始的差别不大)

  3. 释义

    $G$的目标是最大化生成数据与数据集数据的似然，减小生成数据与数据集数据之间的差距（原始GAN就是JSD）。对于生成器$ G $来说，为了尽可能欺骗$ D$，所以需要最大化生成样本的判别概率 $D(G(z))$，即最小化$ log(1-D(G(z)))$，注意：$log(D(x)) $一项与生成器$ G $无关，所以可以忽略。

    $D$要解决的问题是一个二分类问题，$V(D,G)$ 为二分类问题中常见的交叉熵损失。

阅读全文 »

发表于 | 更新于 | 评论数：
本文字数： 34k | 阅读时长 ≈ 31 分钟

参考:

Hybrid A Star 路径规划

Hybrid A* Path Planner for the KTH Research Concept Vehicle

分层有限状态机和无人车行为规划

[PAPER] : Path Planning in Unstructured Environments

Hybrid A* 的使用场景

​ 在斯坦福大学2007年参加的DARPA无人车城市挑战赛时使用的Junior，其在行为规划层提出了分层有限状态机的方式，如下图所示。

​ 其中，BAD_RNDF状态表示的是，当前道路与系统的路网图不同的时候，无人车将采用Hybrid A*来进行规划路径。

阅读全文 »

发表于 | 更新于 | 评论数：
本文字数： 3.3k | 阅读时长 ≈ 3 分钟

参考博客：反向传播算法（过程及公式推导）

1. 符号定义

  • $w_{jk}^L$ 表示第$L-1$层的第$j$个神经元到第$L$层的第$k$个神经元映射的权值。
  • $b_k^L$ 表示第$L$层的第$k$个神经元的偏置量。
  • $z_k^L=\sum_j w_{jk}^L a_j^{L-1}+b_k^L​$ 表示第$L​$层的未经激活函数的输出。
  • $a_k^{L}=\sigma(z_j^L)$ 表示第$L$层经过sigmoid函数后的输出。

阅读全文 »