zhkmxx930 blog

深度学习常见Loss推导

发表于 2019-02-16 | 更新于 2019-07-11 | 评论数：

本文字数： 3.5k | 阅读时长 ≈ 3 分钟

1. Softmax Loss 推导

(1) $N$为类别数

(2) $a$为输出向量，$a_j$为向量$a$的第$j$个值

参考：卷积神经网络系列之softmax loss对输入的求导推导

1.1 Softmax

$S_i=\frac{e^{a_i}}{\sum_{j}e^{a_j}}$

阅读全文 »

深度学习优化器

发表于 2019-02-15 | 更新于 2019-07-10 | 评论数：

本文字数： 13k | 阅读时长 ≈ 11 分钟

参考资料：深度学习最全优化方法总结比较（SGD，Adagrad，Adadelta，Adam，Adamax，Nadam）

1. 随机梯度下降

批梯度下降(Gradient Descent)
随机批梯度下降(Stotastic Gradient Descent)
- 每次梯度计算只使用一个随机样本(可能是噪声样本)
  - 避免在类似的样本上进行冗余计算
  - 增加了跳出当前局部最小值的可能
  - 可以通过减小学习率，来使其能够与GD有相同的收敛速度
小批量随机梯度下降(Mini batch SGD)
- 每次梯度计算使用小批量的样本
  - 梯度计算比单样本计算更加稳定
  - 便于使用矩阵计算
  - 适当的batch size训练效率高

def gradient_decent(_x_data, _y_data, _b, _w, _iteration, _lr):
    """
    Gradient Decent
    :param _x_data:
    :param _y_data:
    :param _b:
    :param _w:
    :param _iteration:
    :param _lr:
    :return:
    """
    _b_history = [_b]
    _w_history = [_w]

    for _i in range(_iteration):
        b_grad = 0.0
        w_grad = 0.0

        for _n in range(len(x_data)):
            b_grad = b_grad - 2.0 * (y_data[_n] - _b - _w * _x_data[_n]) * 1.0
            w_grad = w_grad - 2.0 * (y_data[_n] - _b - _w * _x_data[_n]) * _x_data[_n]

        _b = _b - _lr * b_grad
        _w = _w - _lr * w_grad

        _b_history.append(_b)
        _w_history.append(_w)
    return _b_history, _w_history

阅读全文 »

刷题-搜索

发表于 2019-02-14 | 更新于 2019-03-23 | 评论数：

本文字数： 40k | 阅读时长 ≈ 36 分钟

1. [Leetcode 200] 岛屿的个数

解法：
- DFS：一次遍历，遇到1则进行深搜，遍历过的1设为2，遇到非1或者越界则深搜停止，统计深搜的次数，即为岛屿数量。(这里采用)
- BFS: 循环遍历每个点，如果该点是0，则跳过，如果是1，岛屿数目加1，并加入队列，并将该点改为0，避免重复访问，然后进行广搜，取出队首元素，搜索该点周围四个点，如果有1就加入队列，并将1改为0，否则就跳过，当队列空时，一块岛屿搜索完毕，进入下一块搜索。(代码可参考：岛屿的个数 BFS)
- 并查集: 将二维数组重新编号，从0开始，从左到右，从上到下，直到n*m-1（其中n为行数，m为列数），对于位置(i,j)则编号为i*m+j，那么相邻（左右，上下）的为同一个值，则认为他们相通。那么最终只要统计一下father[i]==i且对应值为1的个数即可。(代码可参考: 岛屿的个数 Disjoint Set)

代码：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty()) return 0;

        int res = 0;
        
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(grid[i][j] == '1'){
                    dfs(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }
    
    void dfs(vector<vector<char>>& grid, int row, int col){
        if(row < 0 || col < 0 || row >= grid.size() || col >= grid[0].size() || grid[row][col] == '0' || grid[row][col] == '2')
            return;
        
        if(grid[row][col] == '1') grid[row][col] = '2';
        
        dfs(grid, row-1, col);
        dfs(grid, row+1, col);
        dfs(grid, row, col-1);
        dfs(grid, row, col+1);
                
    }
    
   
};

2. [Leetcode 77] 组合

模板题：重点在于dfs中的startPos=i+1

代码：

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
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> inRes;
        if(n<=0 || k<=0) return {};
        
        
        dfs(res, inRes, n, k, 1);
        return res;
    }
    
    void dfs(vector<vector<int>> &res, vector<int> &inRes, int n, int k, int startPos){
        if(inRes.size()==k){
            res.emplace_back(inRes);
            return;
        }
            
        
        for(int i = startPos; i<=n; i++){
            inRes.emplace_back(i);
            dfs(res, inRes, n, k, i+1); //重点在于i+1
            inRes.pop_back();
        }
    }
};

3. [Leetcode 39] 组合总和(可重复选取数字)

基于模板加一些改动即可，由于可重复选择数字，将startPos=i+1 改成startPos=i，判停条件满足目标和就可以了,(前提是有序数组，先拍下序)
代码：

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        if(candidates.size() <= 0) return {};
        vector<vector<int>> res;
        vector<int> tmp;
        sort(candidates.begin(), candidates.end()); //保证有序
        dfs(res, target, tmp, candidates, 0);
        return res;
    }
    
    void dfs(vector<vector<int>> &res,int target, vector<int> tmp, vector<int>& candidates, int startPos)
    {
        int sum = 0;
        for(auto i : tmp) 
            sum += i;
        
        if (sum > target)
        {
            return;
        }
        
        if (sum == target) //求和判停
        {
            res.emplace_back(tmp);
            return;
        }
        
        for(int i = startPos; i < candidates.size(); i++)
        {
            tmp.emplace_back(candidates[i]);
            dfs(res, target, tmp, candidates, i);
            tmp.pop_back();
        }
    }
};

4. [Leetcode 40] 组合总和 II (不重复)

解法：在上一题的基础上使用Set进行去重

代码:

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        if (candidates.size() <= 0) return {};
        set<vector<int>> res;
        vector<int> curr;

        
        sort(candidates.begin(), candidates.end());
        dfs(res, target, 0, curr, candidates);
        return vector<vector<int>>(res.begin(), res.end());
    }
    
    void dfs(set<vector<int>> &res, int target, int s, vector<int> curr, vector<int>& candidates)
    {
        if(target == 0) 
        {
            res.insert(curr);
            return;
        }
        
        for(int i = s; i < candidates.size(); i++)
        {
            if(target - candidates[i] < 0) break;
            curr.emplace_back(candidates[i]);
            dfs(res, target - candidates[i], i+1, curr, candidates);
            curr.pop_back();
        }
    }
};

5.[Leetcode 216] 组合总和 III

解法:
代码

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> nums;
        vector<vector<int>> res;
        vector<int> curr;
        for(int i = 0; i < 9; i++)
            nums.emplace_back(i+1);
        dfs(res, k, n, 0, 0, curr, nums);
        return res;
    }
    
    void dfs(vector<vector<int>> &res, int k, int target, int s, int depth, vector<int> curr, vector<int>& nums)
    {
        if(target == 0 && depth == k)
        {
            res.emplace_back(curr);
            return;
        }
        
        for(int i = s; i < nums.size(); i++)
        {
            if(target - nums[i] < 0) break;
            curr.emplace_back(nums[i]);
            dfs(res, k, target - nums[i], i+1 , depth+1 , curr, nums);
            curr.pop_back();
        }
    }
};

6.[Leetcode 131] 分割回文串

解法:

按解组合的方式解，解的过程中判断回文串，组合的元素集合是按照从子串的第一个元素开始，到第i个元素截断作为一个新子串进行回文判断，
代码：

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string >> res;
        vector<string> tmp;
        
        dfs(res, tmp, 0, s.length()-1, s);
        return res;
    }
    
    void dfs(vector<vector <string> >& res, vector<string >& tmp, int startPos, int endPos, string &s){
        //当原字符串都遍历完成后，结束一次搜索。
        if(startPos > endPos){
            res.emplace_back(tmp);
            return;
        }
        //遍历子串，从0~1，0~2 ... 到0~n, 递归的起始位置为截断后的第一位
        for(int i =1; i <= endPos-startPos+1; i++){
            if(isPalindrome(s.substr(startPos, i))){
                tmp.emplace_back(s.substr(startPos, i));
                //递归的起始位置为截断后的第一位
                dfs(res, tmp, startPos+i, endPos, s);
                tmp.pop_back();
            }
            
        }
    }
    
    // 判断回文串，这里用的是可解决大小写字母，数字的，过滤其他符号。
    bool isPalindrome(string s) {
        int pStart = 0;
        int pEnd = s.length()-1;
        while(pStart < pEnd){
            while (!checkChar(s[pStart]) && pStart < pEnd)
				pStart++;
			while (!checkChar(s[pEnd]) && pStart < pEnd)
				pEnd--;

			toLower(s[pStart]);
			toLower(s[pEnd]);
           
            if(s[pStart] == s[pEnd]){
                pStart ++;
                pEnd--;
            }else{
                return false;
            }
               
        }
        return true;
    }
    
    void toLower(char& s){
        if(s >= 'A' && s <= 'Z')
            s = s+32;
    }
    
	bool checkChar(const char& s){
		if ((s >= 'a' && s <= 'z') || (s >= '0' && s <= '9') || (s >= 'A' && s <= 'Z'))
			return true;
		return false;
	}
};

7.机器人运动范围

规规矩矩没啥说的, 主要注意边界条件

代码:

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        int res = 0;
        vector<vector<int>> visited (rows, vector<int>(cols, 0));
        Dfs(threshold, rows, cols, 0, 0, res, visited);
        return res;
    }
    
    void Dfs(const int& threshold, const int& rows, const int& cols, int rowIdx, int colIdx, int& res, vector<vector<int>>& visited){
        if (JudgeOverThreshold(threshold, rowIdx, colIdx) || JudgeOutside(rows, cols, rowIdx, colIdx) || visited[rowIdx][colIdx] )
            return;
        visited[rowIdx][colIdx] = 1;
        res ++;
        Dfs(threshold, rows, cols, rowIdx+1, colIdx, res, visited);
        Dfs(threshold, rows, cols, rowIdx, colIdx+1, res, visited);
        Dfs(threshold, rows, cols, rowIdx-1, colIdx, res, visited);
        Dfs(threshold, rows, cols, rowIdx, colIdx-1, res, visited);
    }
    
    bool JudgeOverThreshold(const int& threshold, int rowIdx, int colIdx){
        int sum = 0;
        while(rowIdx){
            sum += rowIdx%10;
            rowIdx /= 10;
        }
        
        while(colIdx){
            sum += colIdx%10;
            colIdx /= 10;
        }
        if(sum > threshold) return true;
        else return false;
    }
    
    bool JudgeOutside(const int& rows, const int& cols, const int& rowIdx, const int& colIdx){
        if(rowIdx < 0 || rowIdx > rows-1 || colIdx < 0  || colIdx > cols-1) return true;
        else return false;
    }
};

未命名

发表于 2019-02-12 | 更新于 2019-03-24 | 评论数：

本文字数： 20k | 阅读时长 ≈ 19 分钟

title: “[刷题]链表专题”
tags: 数据结构与算法
abbrlink: 6db30a46
date: 2019-02-12 21:23:22

[Leetcode 141, 142] 环形链表，环形链表 II （剑指Offer面试题23）

解法：(链表遍历，快慢指针)
- 判环：快慢指针，快指针+2，慢指针+1，若快指针在到达链表尾(不带环的才有链表尾)之前与慢指针相遇，则有环。
- 找入口：快慢指针第一次相遇节点与头结点之间的节点数与环中节点数相同，两个指针一个从链表头开始，一个从相遇节点开始遍历，两个指针再次相遇节点为入口节点。
阅读全文 »

[刷题]递归回溯专题

发表于 2019-02-11 | 更新于 2019-03-01 | 评论数：

本文字数： 16k | 阅读时长 ≈ 14 分钟

1. [剑指Offer 面试题17] 打印从1到最大的n位数

题目：输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，打印出1,2，…，999。
解法：
- 全排列解，这里主要用这个方式，有需要在输出时，对高位0进行截断。
- 大数加法解
代码：
阅读全文 »

刷题-栈和队列

发表于 2019-02-09 | 更新于 2019-03-02 | 评论数：

本文字数： 14k | 阅读时长 ≈ 13 分钟

1. [Leetcode 232] 用栈实现队列（剑指OFFER面试题 9）

解法：一个栈(push栈)用于接收push，一个栈(pop栈)用于top(peek)和pop
1. 当pop栈为空，且push栈不为空时，将push栈的元素转移到pop栈中
2. 当pop栈不为空时，将pop栈的数据pop出去
3. push操作只在push栈进行
注意：
- leetcode上可以不进行异常处理，能a过，但是面试时候最好还是加上空栈的异常处理。
- 泛型支持。
- 线程安全。
  阅读全文 »

[刷题]二叉树专题

发表于 2019-02-07 | 更新于 2019-03-19 | 评论数：

本文字数： 42k | 阅读时长 ≈ 38 分钟

参考几道和「二叉树」有关的算法面试题

1. [Leetcode 105] 从前序与中序遍历序列构造二叉树 (剑指OFFER面试题 7)

解法：递归，由先序序列确定子树根节点，由中序序列确定当前节点下的子树范围。
主要参数(递归函数)：先序序列的起点idx与终点idx，中序序列的起点idx与终点idx。
递归停止条件： 先序序列或中序序列的起点idx > 终点idx。
递归参数更新方法：
- 左子树更新:
  - 先序起点idx+1。 preL + 1
  - 先序终点为中序确定左子树节点数量num + 先序起点idx。 preL + num
  - 中序起点为之前递归层中的中序起点。 inL
  - 中序终点为根节点在中序序列中的idx - 1。 inRoot - 1
- 右子树更新:
  - 先序起点idx+1 + 中序确定左子树节点数量num。 preL + num + 1
  - 先序终点为之前递归层中的先序终点。 preR
  - 中序起点为根节点在中序序列中的idx + 1。 inRoot + 1
  - 中序终点为为之前递归层中的中序终点。 inR
    阅读全文 »

干货收集

发表于 2019-01-26 | 更新于 2019-02-11 | 评论数：

本文字数： 2.4k | 阅读时长 ≈ 2 分钟

2017~2019年度我在Github上面收藏的一些优质干货Repo
其中有一些很荣幸作为Repo的贡献者，在issue中也结识了不少好友，共同学习

计算机软件工程类

[强化学习笔记专题(二)]Nature DQN

发表于 2019-01-24 | 更新于 2019-02-17 | 评论数：

本文字数： 26k | 阅读时长 ≈ 24 分钟

DQN (Nature)

一、算法流程：

定义可配置参数
- episode 数量 M
- 最大仿真时间 T，$\epsilon-greedy$参数$\epsilon_{low}$,$\epsilon_{high}$
- batch size $N$
- 折扣率 $\gamma$，学习率 $\alpha$等优化器参数
- Soft update 频率 $C$
  阅读全文 »

[强化学习论文] (HDQN) Integrating Temporal Abstraction and Intrinsic Motivation

发表于 2019-01-23 | 更新于 2019-02-19 | 评论数：

本文字数： 2.9k | 阅读时长 ≈ 3 分钟

论文

题目: Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation
作者: Tejas D. Kulkarni, Karthik R. Narasimhan, Ardavan Saeedi, Joshua B. Tenenbaum
论文: https://arxiv.org/abs/1604.06057
年份: 2016
参考: https://github.com/aleju/papers/blob/master/neural-nets/Hierarchical_Deep_Reinforcement_Learning.md

总结

1.主要贡献

提出了一种分层强化学习方法
该方法使用了长期目标(long-term goal)指导短期动作(short-term choice)的选择

阅读全文 »

1. Softmax Loss 推导

1.1 Softmax

1. 随机梯度下降

1. [Leetcode 200] 岛屿的个数

2. [Leetcode 77] 组合

3. [Leetcode 39] 组合总和(可重复选取数字)

4. [Leetcode 40] 组合总和 II (不重复)

5.[Leetcode 216] 组合总和 III

6.[Leetcode 131] 分割回文串

7.机器人运动范围

[Leetcode 141, 142] 环形链表，环形链表 II （剑指Offer面试题23）

1. [剑指Offer 面试题17] 打印从1到最大的n位数

1. [Leetcode 232] 用栈实现队列 （剑指OFFER面试题 9）

1. [Leetcode 105] 从前序与中序遍历序列构造二叉树 (剑指OFFER面试题 7)

计算机软件工程类

DQN (Nature)

一、 算法流程：

定义可配置参数

论文

总结

1.主要贡献

1. [Leetcode 232] 用栈实现队列（剑指OFFER面试题 9）

一、算法流程：