发表于   |   更新于

  1. 统计文件夹下面文件个数 

    1
    ls -l | grep "^-" | wc -l

  2. vim下计算字符串出现次数 

    1
    :%s/pattern//gn

  3. Linux下载命令 

    1
    wget url

  4. Linux解压命令 

    1
    tar -zxvf  **.tar.gz

发表于   |   更新于 | 分类于

本笔记为凸优化学习笔记，学习书籍为《凸优化》Stephen Boyd 中文版
B站视频参考：《中科大-凸优化-凌青》
中文版PDF：

0. 引言

数学优化问题定义

线性函数

凸函数

线性规划：$f_0, f_1, … , f_m $ 均为线性函数；

凸优化：$f_0, f_1, … , f_m $ 均为凸函数。

1. 凸集

发表于   |   更新于

test
test

发表于   |   更新于 | 分类于

1. 自我介绍

我是*

2. 项目经历

我做了*

3. 手撕代码

  • 0-100的N个数(数的值范围为0~100 1 < N <= 1000),分成两组A、B:怎样分|meanA-meanB|最大? 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    Solution:
    1. 排序
    2. meanB = nums[0]
    3. meanA = nums[1:] / (n-1)
    4. res = meanA - meanB

    面试官提示：
    1. 排序
    2. 排序优化

  • 最长不超过k个字符的子序列

    1
    2
    Leetcode 原题
    滑动窗口

发表于   |   更新于 | 分类于

1. 决策树

  • 信息熵

  • 信息增益

  • 信息增益率

  • 基尼指数

  • 剪枝

  • 连续值处理

  • 缺失值处理

2. 随机森林

  • 自助采样

  • 简单投票

  • 包外估计

  • 随机属性

3. 提升树

4. 梯度提升树

5. GBDT

6. XGBboost

7. GBDT、XGBoost对比

  • XGBoost 是 GBDT的工程实现

  • XGBoost 加入正则项控制模型复杂度

  • XGBoost 使用泰勒二阶展开，梯度下降更快更准

  • XGBoost 支持多种基分类器

  • XGBoost 采用随机森林相似策略，对训练数据进行列抽样

  • XGBoost 自动学习缺失值的处理

  • XGBoost 缩减 Shringe，类似学习率，削弱每棵树的影响

  • XGBoost 特征粒度的并行化，特征预排序，保存为block，寻找最佳分割点

8. LGB特点

  • 直方图寻找特征分裂点
  • leaf-wise 对比 XGBoost level-wise 容易长出较深的决策树，加入最大深度限制

发表于   |   更新于 | 分类于

1. 概念及原理

从入度为0的节点入手，使用队列存入度为0的节点，并广度遍历下去

2. 应用

3. 实现

发表于   |   更新于 | 分类于

1. 矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[[“a”,”b”,”c”,”e”],
[“s”,”f”,”c”,”s”],
[“a”,”d”,”e”,”e”]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例1：

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

2. 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
            if k == len(word) - 1: return True
            tmp, board[i][j] = board[i][j], '#'
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = tmp
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0): return True
        return False

发表于   |   更新于 | 分类于

1. 旋转数组最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例1：

1
2
输入：[3,4,5,1,2]
输出：1

示例2：

1
2
输入：[2,2,2,0,1]
输出：0

2. 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minArray(self, numbers: List[int]) -> int:

        left = 0
        right = len(numbers)-1
        while left < right:
            mid = (left+right)//2

            if numbers[mid] > numbers[right]:
                left = mid+1
            elif numbers[mid] == numbers[right]:
                # 除了这里就是一个普通的二分，记忆这个技巧
                right -= 1
            else:
                right = mid
            # print(left,right)
        return numbers[left]

发表于   |   更新于 | 分类于

1. Attention 计算方法

1.1 点乘

$score = a^T * b$

1.2 权值网络映射

$score = a^T W b$

1.3 拼接映射

$score = v^T tanh(W[a, b])$

2 Attention 种类

2.1 Soft Attention And Hard Attention

  • soft attention： 加权平均
  • hard attention： 取最大的一个或者抽样

2.2 Global Attention And Local Attention

  • Global Attention： 全局
  • Local Attention：预测中心点

发表于   |   更新于 | 分类于

1. BGD（Batch Gradient Descent）

思想：使用整个数据训练集计算损失函数

缺点：计算过程很慢

2. SGD（Stochastic Gradient Descent）

和 BGD 的一次用所有数据计算梯度相比，SGD 每次更新时对每个样本进行梯度更新，对于很大的数据集来说，可能会有相似的样本，这样 BGD 在计算梯度时会出现冗余，而 SGD 一次只进行一次更新，就没有冗余，而且比较快，并且可以新增样本。

优点：收敛快

缺点：引入噪声，存在局部最优

3. MBGD（Mini-Batch Gradient Descent）

MBGD 每一次利用一小批样本，即 n 个样本进行计算

以上三个算法的缺点：

  • Learning Rate 如果选择的太小，收敛速度会很慢，如果太大，Loss Function 就会在极小值处不停地震荡甚至偏离。
  • SGD对所有参数更新时应用同样的 Learning Rate，如果我们的数据是稀疏的，我们更希望对出现频率低的特征进行大一点的更新。Learning Rate会随着更新的次数逐渐变小。

4. Momentum

其中$\beta_1 取0.9$

一阶动量：各个时刻梯度方向的指数移动平均值，约最近 $\frac{1}{1-\beta}$个时刻的梯度向量的平均值。

优点：使得梯度方向不变的维度上速度变快，梯度方向有所改变的维度上的更新速度变慢，这样就可以加快收敛并减小震荡。

5. Adagrad（Adaptive gradient algorithm）

二阶动量$vt = \sum{\tau=1}^{t}g_\tau^2$ ：所有梯度值的平方和。

思想：

  • 对经常更新的参数，学习率慢一些；
  • 对偶尔更新的参数，学习率快一些。

优点：自适应，不需要人调节

缺点：学习率越来越小，趋于0

6. Adam

结合Momentum及自适应

具有一阶动量及二阶动量

7. AdamW

加入了Weight Decay

8. 参考

1 优化算法Optimizer比较和总结