光与影的个人博客

实用ML-1.学什么

发表于 2022-03-08 更新于 2023-02-09 分类于 AI理论，实用机器学习

学什么

主要是从机器学习的工作流出发，每个阶段主要的工作和工业界流行的技术和概念

主要包括四个学习模块：

数据数据获取、存储、清洗
模型训练、迁移、多模态
部署
监控可视化

学习计划

基本学习计划：

数据模块
- 一天一个视频，慢慢学
模型模块
- 机器学习、深度学习模块部分，快速过一遍
- 模型验证，调优部分慢慢学，基础较差
部署 + 监控部分
- 慢慢学

大概一共30多个视频，三周内学完（无意外的情况下），deadline 3-15

前缀（字典）树总结

发表于 2021-11-21 更新于 2023-02-09 分类于算法相关，算法整理

什么是前缀树（Trie）

In computer science, a trie, also called digital tree or prefix tree, is a type of search tree, a tree) data structure used for locating specific keys from within a set. These keys are most often strings), with links between nodes defined not by the entire key, but by individual characters). - wikepidea

前缀树（又叫做字典树）是一种特殊类型的多叉树，每条边代表一个一个字母，每个节点代表一个字符串（前缀），该字符串由从根节点到当前节点路径字母组成，由于节点间的父子关系，父节点字符串就相当于子节点字符串的前缀，因此称为前缀树。

需要特殊注意的是前缀树的根节点由于没有父节点，代表空字符串

阅读全文 »

cs224n-12.自然语言生成

发表于 2021-11-21 更新于 2023-02-09 分类于 AI理论， cs224n

内容回顾

Beam Search：不同K的区别

小K值可能导致生成序列效果较差（语法上、语义上、流畅度上）
大K值虽然能够解决以上问题，但是会带来更多的计算成本，一定程度上减低NMT任务中的BLUE分数
- 开放式问答任务中，更大的K可能导致回答更加的宽泛（与原问题的关联度更低）

其他的解决方案

Sampling-based decoding（与Beam search不同在于decoder每一步只需要追踪一个词）
- Pure Sampling：每次随机选择概率分布中的某一个词，作为decoder输出词
- Top-n Sampling：每次从前N个概率大小词语中选择某一个词，作为decoder输出词

Softmax temperature: 带温度系数的Softmax方法

$\tau$解释

在原始的Softmax函数中添加 temperature hyperparameter: $\tau$ .

$\tau$ 起到一种平滑作用， $\tau$ 越大softmax计算得到的概率分布越平滑，t越小分布越不均匀
在训练开始将 $\tau$ 值设置较大，概率分布较为平滑，loss较大可以避免模型落入局部最优解，随着训练的进行，不断增大 $\tau$ 值，从而提升模型的效果。（某一个 $\tau$ 值并不影响模型的结果）

总结

阅读全文 »

lc869.重新排序得到2的幂

发表于 2021-11-21 更新于 2023-02-09 分类于算法相关，力扣刷题

869.重新排序得到 2 的幂

关键点是意识到2的幂次是有限

解法1-暴力回溯法

看到重排序就想到回溯法中的排列树问题，按照排列树的标准模板求解即可,注意排除出现前导零的情况,与

复杂度分析：

时间复杂度：由于第i层共有N- i个选择，时间复杂度为O(N!)
空间复杂度：递归深度为数字的长度，空间复杂度为O(N)

代码：

public boolean backTrace(int depth, int nLength, Long curNumber, int[] visited, int[] digits){
        //所有情况选取完毕
        if(depth == nLength){
            return isTwoPower(curNumber);
        }
        for(int i = 0;i < nLength;i++){
            //未选用过当前位置数字,前导数字不能为0
            if(visited[i] == 0 && (depth != 0 || digits[i] != 0)){
                visited[i] = 1;
                if(backTrace(depth + 1, nLength, curNumber * 10 + digits[i] , visited, digits))
                    return true;
                visited[i] = 0;
            }
        }
}

阅读全文 »

lc59.两数相除

发表于 2021-10-17 更新于 2023-02-09 分类于算法相关，力扣刷题

29. 两数相除

难点在于处理不能用long解决溢出问题

思路1：“二进制”减法(没有满足越界要求)

不能用除法，最简单的思路就是被除数(dividend)不断地减除数(divisor)，直到减到剩余余数，相减的次数就是结果。该方法的问题就是时间复杂度太高，

二进制优化，首先找到最大的n使得 $divisor 2^n < dividend$，每次减去 $ divisor 2^n， divisor 2^{n-1} ，divisor 2^{n-2} ……$,直到减到 $ divisor $
实际上就是将原来的逐个减去，变为二进制减去（找商的二进制表示），由于任何数都能由二进制表示，所以该方法必定有解
我的实现方法越界无法规避，只能用Long

复杂度分析：

没有分析的必要，由于只有32位整数，二进制一共只需要移动32次，时间复杂度与空间复杂度均为O(1)

代码实现：

public int divide(int dividend, int divisor) {
    long result  = 0;
    boolean isNegative = (dividend < 0 & divisor > 0) || (dividend > 0 & divisor < 0);
    long temp = 1;
    
    //首先绝对值求解
    long denominator = (long)Math.abs((long)dividend);
    long numerator = (long)Math.abs((long)divisor);
    //首先找到最大元素
    while(numerator << 1 <= denominator){
        temp = temp << 1;
        numerator = numerator << 1;
    }
    while(numerator >= Math.abs((long)divisor)){
        if(denominator >= numerator){
            denominator -= numerator;
            if(isNegative)
                result -= temp;
            else
                result += temp;
        }
        numerator = numerator >> 1;
        temp = temp >> 1;
    }
    if(result > Integer.MAX_VALUE){
        result = Integer.MAX_VALUE;
    }
    return (int)result;
}