记录1
- leetcode
- 文献
leetcode
题目:530. 二叉搜索树的最小绝对差
二叉树特点是每个结点最多只能有两棵子树,且有左右之分
二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树
前序遍历(DLR) 、中序遍历(LDR)、 后序遍历(LRD)
中序遍历(LDR)首先遍历左子树,然后访问根结点,最后遍历右子树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def getMinimumDifference(self, root: TreeNode) -> int:
# 正无穷inf
res = float('inf')
pre = None
def LDR(root):
# nonlocal声明的变量不是局部变量,也不是全局变量,而是外部嵌套函数内的变量
nonlocal res, pre
if not root:
return
LDR(root.left)
if pre:
res = min(res, abs(pre.val - root.val))
pre = root
LDR(root.right)
LDR(root)
return res
文献
Article:Lee D H. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks 2013.
Data:
提出一种简单的半监督神经网络,用有标签数据和伪标签同时微调网络
大多数网络的两个阶段:1、无监督预训练 2、有标签数据反向传播微调
步骤:
1)、用降噪自编码器对网络进行预训练得到初始化参数
2)、无标签数据经过网络选用最大预测概率的标签作为伪标签
3)、用有标签数据和伪标签数据对网络进行微调,每次权重更新,伪标签重新计算
目标公式:
数据:MINST
结果:
Comments:文章解释了为什么伪标签有用。半监督的目标是用无标签数据提高生成性能,聚类假设表明决策边界在低密度区域可以提高生成性能。熵正则化通过最小化未标记数据的类概率的条件熵来实现类间的低密度分离,而不需要对密度进行建模,即测量类重叠,当类重叠下降时,在决策边界数据的密度更低。
Why:了解课题背景
Label:半监督、自训练、伪标签、
Article:Xie Q, Luong M T, Hovy E, et al. Self-training with noisy student improves imagenet classification 2020
Code:https://github.com/google-research/noisystudent
Data:
采用自训练方法,在student模型加入输入噪声(RandAugment)和模型噪声(dropout、stochastic depth),学得的模型大于或等于teacher模型
无标签数据来自JFT,采用EfficientNet-B0训练数据,选取可信度高于0.3的图片作为无标签数据,每个类别选取最高可信度前130K图片,不够的复制补充
步骤:
1)、通过有标签数据,用交差熵损失学习teacher模型的参数
2)、对没有标签的数据用teacher模型得到伪标签
3)、用无标签、有标签数据和噪声数据学习一个等大或者更大的student模型
4)、将学到的student模型做为teacher模型,迭代3次
数据:ImageNet、JFT
Comments:student模型加入噪声,模型等于优于teacher模型。
Why:了解课题背景
Label:半监督、自训练、伪标签、
Article: Hadifar A, Sterckx L, Demeester T, et al. A self-training approach for short text clustering 2019
Code: Tensorflow
Data:
采用SIF嵌入对句子进行表示,再用深度聚类DEC训练网络
self-training:根据有标签数据学得teacher模型,再根据teacher模型对无标签进行伪标签标注,用伪标签数据和有标签数据一起训练student模型
SIF:
输入:词嵌入向量,句子集,参数a和单词估计概率p(w)
输出:句子嵌入向量
- 每个词的贡献度为a/(a+p(w)), a为超参数,p(w)文本预料库的词频
- 句子的表示为,|s|句子长度,
3)以上所有句子向量按列排列组成矩阵X,求得X第一个主成分奇异向量u
4)最终每个句子表示为:
步骤:
1)用SIF嵌入得到短文SIF本嵌入
2)用深度自编码器对短文本SIF嵌入进行编码重构,来训初始化网络
3)用软聚类分配概率分布和辅助概率分布间得KL散度,交替更新网络参数和聚簇中心
软聚类分配:
辅助分配概率(强化版,提高簇纯度以及更关注高可信度得数据):
目标公式:
数据:SearchSnippets、Stackoverflow、Biomedical
Comments:结合了短文本SIF嵌入和深度聚类对短文本进行聚类,STC^2是两种不同得模型(CNN和其他模型)得到结果,进行适配得到伪标签对网络进行反向微调,再用网络得到得表示进行聚类。
Why:了解课题背景
Label:短文本聚类