Algorithm

题目链接

二叉树的最小深度

描述：

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

解析

两种方法实现：

第一种，递归寻找左右子树，并且比较左右子树的深度，返回较小的一个，然后+1 返回，直至找到叶子节点（需要注意，和最大深度不同，最小子树需要判断左右子树是否同时为空，如果只有一个子树为空，则该分支不能计入最小深度，因为该节点不是子树，如果计入，则空的那边一定是 0 了，就会导致该节点被误记为叶子节点）

第二种，采用广度优先算法，从根节点寻找，直到找到第一个叶子节点，因为是广度优先，最先找到的节点一定是最小深度的叶子节点

实现

递归寻找的方案实现

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    int minDepth(TreeNode* root) {        if(root == nullptr){            return 0;        }        if(root->left == nullptr && root->right == nullptr){            return 1;        }        int currMinDepth = INT_MAX;        if(root->left != nullptr){            currMinDepth = min(minDepth(root->left), currMinDepth);        }        if(root->right != nullptr){            currMinDepth = min(minDepth(root->right), currMinDepth);        }        return currMinDepth + 1;    }};

广度优先搜索算法实现

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    int minDepth(TreeNode* root) {        queue<pair<TreeNode *, int>>  que; // queue of node with depth info        if(root == nullptr){            return 0;        }        que.emplace(root, 1);        while(!que.empty()){            TreeNode* curr_node = que.front().first;            int depth_val = que.front().second;            que.pop();            if(curr_node->left == nullptr && curr_node->right == nullptr){                return depth_val;            }            if(curr_node->left != nullptr){                que.emplace(curr_node->left, depth_val + 1);            }            if(curr_node->right != nullptr){                que.emplace(curr_node->right, depth_val + 1);            }        }        return 0;    }};

Review

（正常字体为原文中我觉得比较好的内容，斜粗体为本人观点）

https://amitness.com/2020/02/illustrated-self-supervised-learning/ 自监督学习的一篇 blog,介绍的很全面，也列出了参考文章，非常值得一读，整篇文章是参考"self-supervised visual feature learning with deep neural networks: A survey" https://arxiv.org/abs/1902.06162 ，主要是计算机视觉领域的自监督学习，并且集中在分类和生成领域，检测和分割任务涉及很少。讲的深入浅出，配图清晰，适合阅读。

什么是自监督学习

利用现有的数据和已知，生成大量 label，作为有监督学习的 label,通过训练模型学习这个任务，来获得很好的特征（representations), 该模型可以用于真正任务的预训练模型（finetune)。整体流程如下所示：

自监督学习重要性

1. 有监督学习所需大量数据的标注时间和成本，分类，检测，分割任务标注周期和成本越来越高，医疗图像标注成本尤其高

2. open-world intellegence 本身更加需要自监督模式，这样算法才能够很快进化（快速迭代，强适应性），学习到的特征也能够快速应用于下游任务

3. 自监督学习是通向通用人工智能（AGI）的基座，Yann Lecun 关于自监督学习（self-supervised learning) 有一个很好的蛋糕比喻，中文大意如下“如果智能是一个蛋糕，那么蛋糕的大部分是自监督学习，蛋糕的糖衣是监督学习，蛋糕上的樱桃是强化学习”

4. 自监督学习结合主动学习，可以减少数据标注的前期依赖，减少数据标注时间

自监督学习用到的方法举例

生成类模型训练

这类自监督学习任务比较直观，自监督本身就可以作为一个任务，直接将原图进行一系列操作，训练出的模型即可应用，甚至不用 finetune

1. 图片上色模型训练：通过将彩图转变为灰度图（无 label 成本），训练模型给输入的灰度图上色，同原图进行比较，获得 loss;

2. 超分辨率模型： 将原始图片缩小，作为输入图片，训练超分模型，原始图片作为 real image,输入判别器

3. 图片填充：crop 掉一部分图像，训练生成器，并且将原图作为 real image, 同 generated image 进行比较，训练判别器

通过图片内部 patch 信息进行特征提取

该类型训练的模型不能直接应用，主要目的是通过学习任务，获取特征，用于后续有监督模型的预训练

1. 图片拼图，类似拼图游戏，将图片切分为 9 个 patch, 分别作为单独输入输入特征提取层，在通过 dense 层判断相对排布关系，因为 9 个图片先后顺序排列顺序很多（$A_9^9$=362880）种，为了训练效果，仅挑选 hamming distance 最大的 64 种参与训练；

2. 上下文信息预测：给定图片，按 9 宫格方式将其切分为 9 份，输入 center patch 和 周边 patch, 输入周边 patch 相对 center patch 的位置（上，左上，右下等）共 8 个 label

3. 通过旋转角度来获取信息，给定图片，进行（0，90，180，270）四个角度旋转，训练模型预测旋转角度

4. 相对位置不仅可以用于图像空间信息，也可以用于视频里面的时序信息，例如预测几帧之间的先后顺序，从而强迫模型学习时许信息；

通过聚类方式获取 raw label 进行特征提取模型训练

主要介绍的方法来自论文“Deep Clustering for Unsupervised Learning of Visual Features”https://arxiv.org/abs/1807.05520. 其主要方法是将原始图像进行聚类，然后将聚类的 cluster 作为分类目标，进行模型训练，期望模型能够获得比较好的初始权值，作为下游任务的预训练模型。在论文原文中，作者设计了一个迭代式的过程，进行聚类和分类，期望获得良性循环，模型特征提取器能够不断提升（提取器好-->聚类效果好-->分类任务监督信息更准确-->提取器好），本文并没有介绍到着里，但是核心方法介绍的很清晰了。关于聚类方式进行模型训练的整体流程如下所示

图片进行聚类

用聚类图片进行分类，获取初始模型

Tips

windows 下查看 md5sum 命令

certutil -hashfile <filename> MD5

linux 下查看 md5sum

md5sum <fielname>

Share

这是分享的第一篇文章，关于选定研究方向的，格雷准则，本来写了一个初稿，按照 arts 原则，加上一些自己的思考，写了以下文章，详见链接 https://www.jianshu.com/p/78ac42a4317f