这些天的work和循环单元很相关
于是看了这篇很早就想看的IndRNN
不得不说work很好看
简单but略完美
传统循环单元一般只能坚持到几百步长
而他能坚持到5000!!!!!!

emmm
还有前天和鹏哥在微博上吹逼,吹错了
今天细看文章的时候发现的,真是尴尬hh

IndRNN介绍

IndRNN和传统RNN的定义式区别见下图

RNN

IndRNN

整个区别真的只有矩阵乘法转为hadamard积(对应元素相乘)
其中每个h_t使用的是不同的u向量权重
然后IndRNN一般采用relu激活
改动虽小,作用却大

梯度分析传统RNN和IndRNN

由梯度计算式可知传统RNN的连乘,由于这个原因导致了梯度爆炸和消失…
而再来观察IndRNN梯度的表达式

如果采用relu激活,后面部分的梯度连乘不会造成梯度爆炸
而u_n的大小不会影响到h其他时间步的梯度
即由矩阵乘法转为hadamard积将梯度计算在一定程度上隔离开来了
u_n是h_n,t-1的权重而不会影响到其他时间步

而u只需约束到一个范围即可完美解决梯度消失与爆炸
见下图(其实我觉得没屁用,RNN不也可以这样吗)

这篇文章主要使用了FlowNet和注意力机制利用了当前帧的上下文信息
里面的trick还是很多的

Historical branch

FlowNet

详见我这篇文章
https://qrfaction.github.io/2018/05/14/%E5%85%89%E6%B5%81%E4%BB%8B%E7%BB%8D%E4%B8%8EFlowNet/

Wrap操作

1.光流场的插值使用法

由光流定义可知 I_t+1(x₂,y₂) = I_t(x₁+v_x,y₁+v_y)
于是我们得到了一个像素间一一对应的关系
由于 (x₁+v_x,y₁+v_y) 可能是小数
所以需要使用双线性插值进行近似计算

2.双线性插值嵌入layer

f(p) = ∑ W(p + δp) * f(p + δp)    p为位置(x,y)

其中 W(p + δp) 需要满足以下条件

1. 若 δp < (1,1) , W(p + δp) = (1-δx) * (1-δy)
2. 否则为0
   这样就满足了双线性插值使用最近的四个点以及其权重两个条件

W(p,q) = max(0,1-|p_x-q_x|) * max(0,1-|p_y-q_y|) = max(0,1 - δp_x) * max(0,1 - δp_y)

3.历史信息封装

将 I_i 封装到 I_t-1 操作的定义如下

δp 是FlowNet输出的坐标偏移
K 是双线性插值权重函数
φ_i 是第i帧图片经过FeatureNet后的特征图
m是φ_i的第m个通道

这样即可利用双线性插值将 I_i 的信息融入 I_t-1 得到 φ_i→t-1

Spatial-temporal attention

Spatial attention

该注意力计算公式如下

使用余弦相似度得出了每个特征图中每个位置p的注意力权重
然后再使用softmax对所有历史帧中的p位置的注意力权重进行规范化

temporal attention

该注意力则是利用了类似SEnet中的模块的结构对时序轴进行加权
RASnet中的tracking也有用它

计算φ(x)

定义如下

加权求和

CFnet框架

一个将相关滤波end2end实现的结构
使用siamese fc的框架,不过效果并没有比siamese fc好多少
把他当做 siamese fc也完全没问题的,这里就不细讲了

other details

1. 使用6帧的历史信息
2. 使用5个尺度的尺度搜索以及尺度缩放比例为1.025
3. 使用Gaussian Label
4. 使用PNR指标和响应图(reponse map)进行选择性更新模型(稀疏更新)

稀疏更新策略

PNR (peak-versus-noise ratio)定义见下图

其中R是跟踪模型输出的reponse map
当这两个指标超过阈值时更新模型参数
其中阈值定义见下图

主要由于需求原因,需要了解一些Optical Flow相关知识
于是写下这篇入门介绍文章

Optical Flow(光流) 介绍

segmentation  : 像素级的分类
光流估计     : 像素级的回归

光流估计   预测连续图片序列中每个像素的速度(大小与方向)

例如给定第t帧与t+1帧,求每个像素的运动速度与方向
I_t(x₁,y₁) = I_t+1(x₂,y₂) = I_t(x₁ + v_x,y₁ + v_y)
(v_x,v_y)即为我们要预测的

光流场 (Optical Flow Field) : 整张图片的光流

光流场是个双通道图像,尺寸与原图相等

FlowNet

FlowNetCorr

如图,网络整体还是很容易理解的
灰色箭头是给了一条支路用于concat操作,U-net,densenet等网络中已经屡见不鲜
conv_redir是1*1卷积用于压缩至32维

corr定义如下
其实就是拿第二个feature map去卷积 (其实是相关运算) 第一个feature map

f1:第一个特征图  f2:第二个特征图
x1,x2是位置
卷积核尺寸 : 以x₂为中心的 (2k+1)*(2k+1) 的区域 , 通道与原feature map一致
卷积核个数 : 即x₂可选位置的个数
      x₂可取x₁为中心周围 (2k+1)*(2k+1) 的所有位置
      论文中k取10,即(2*10+1)*(2*10+1)=441个通道

refinement

主要为堆叠deconv和concat操作
其实这部分加上Corr运算之后的部分合起来和Unet没啥区别

其中 flow5/4/3 等是把concat起来的feature map进行预测光流场(conv成双通道再deconv)
再和下一个feature map 进行 concat

final

总而言之就是 Corr + U-net + flow
模型以实验得出为主
也是较早的一个模型,好像flow net 2.0也出来了,主要用于我粗略了解这方面的知识

2018的CVPR
浏览过五六篇的2018CVPR tracking的工作介绍
个人感觉这篇质量还不错
自己其实也有很多想法
这篇文章让我的想法有了另一种实现方式

注意力机制

本质就是给相关运算进行加权运算

而加权运算被分解成了三个attention mechanisms进行参数剪枝
参数从mnd减少为m*n+d

高性能CUDA应用设计与开发第五章阅读笔记

GPU存储器层次结构

在GPU高速计算的过程中,GPU的性能极大受限于存储器的带宽
只有流多处理器的寄存器带宽满足流多处理器全速运转需求

不同类型GPU存储器的带宽如下

寄存器   约8T/s
共享内存  约1.6T/s
全局内存  约而0.1 - 0.2T/s
内存映射  约0.01T/s   (主机内存映射到GPU显存)

实现程序的高性能必须在流多处理器内实现数据重用
因为经常访问的数据会被放入高速缓存之中
从而减少了从全局内存中读取数据的次数

L2缓存

• 由图知由各SM共享
• L2缓存采用LRU(least recently used)调度方式
• 由L2缓存调度方式可知,L2对非规则内存的访问具有良好的加速效果
• 所有数据的加载与存储都经过L2缓存(包括GPU与CPU之间的数据互传)
  所以GPU与CPU之间的数据传输会影响缓存命中率与程序性能

L1缓存

• L1缓存基于空间重用而非像L2的时间
• L1缓存并不影响全局内存的写操作,这些操作会越过L1
• L1缓存用于两种作用
  1.动态缓存
    (1)记录线程的局部数据结构,如线程栈(栈最多占用1KB的内存)
    (2)局域内存(用于存放从寄存器溢出的局部数据)
  2.用于共享内存
• 广播数据
  condition1: 一致访问 (同一个 线程块 内的线程均访问 同一地址)
  condition2: 若使用的指针是const类型的
  编译器将会识别出一致访问并生成LDU指令访问L1缓存,实现数据广播

局域内存

对自动变量的操作会访问到局域内存
所谓自动变量就是设备端代码中申请的,不包含device,shared,constant限定符的变量
通常自动变量会存放于寄存器中,但以下情况除外

1. 编译器无法通过常量索引元素的数组
2. 体积较大,导致寄存器资源消耗过多的数组或结构体
3. 寄存器溢出
4. 全局内存和L1缓存都有用做局域内存的部分

共享内存

bank冲突

如图,当申请一块共享内存时,共享内存会被组织成32/16个bank(早期的GPU是16个)
不同的线程访问同一个bank会产生bank冲突,会被串行执行
早期double双精度数据也会引起bank冲突,因为他是分成两个32位数据放于共享内存中

在共享内存中填充空数据,可以避免bank冲突
如 __share__ tile[32][33]
这样即可使得一个warp访问同一列数据时发生错位,使得避免了bank冲突

共享内存的多播能力

若一个wrap内的多个线程同时访问同一个字,则硬件上只产生一次共享内存的读取操作

线程通信的注意事项

若共享内存用于线程块内的wrap通信,则共享内存声明时必须使用volatile前缀
避免误读缓存数据带来的错误 (否则,如数据被缓存到寄存器中,将读入旧数据)

常量内存

1. 只有64KB,使用专用的常量缓存(per-SM)
2. 具有数据广播能力
3. 线程间并发访问常量内存不同地址时,采用串行执行

L1的一致访问其实也可以多播,不过当数据过多时,广播数据或许会被挤出缓存
这时候常量内存仍可利用

纹理内存

1. 纹理内存驻留在显存中，并且使用一个只读cache（per-SM）,访问显存数据需经过cache
2. 当访问一个数据时,该数据的周围局部数据也会被加载到缓存中,这对数据访问具有局部相关性的模式具有加速效果
3. 每个流多处理器仅含8KB缓存空间
4. 具有一定数据存储能力,高效拆解和广播数据
5. 当数据的访问发生越界时,支持各种插值算法处理越界数据 (这个是指卷积/滤波时发生矩阵越界访问?)

全局内存

全局内存的读取方式

1. 缓存读取
     内存逻辑首先从L1缓存中寻找数据,接着是L2缓存,若都没找到再从全局内存读取
     全局内存的读取粒度其中一次读取128字节
     这个应该是考虑到减少IO请求的次数,可能存在冗余读取的情况
     这个时候内存对齐是十分重要的东西 (cudaMalloc申请的空间保证了至少256字节的对齐)
2. 非缓存读取
     当读取大量数据且又不存在于连续地址时,建议使用nvcc的命令行参数 -Xptxas-dlcm=gc关闭L1缓存
     这时SM不会从L1中寻找数据,全局内存的读取粒度由128变为32减少冗余读取

内存对齐与冗余读取详细请看该博客
https://blog.csdn.net/qq_17239003/article/details/79038333

鉴于讨论班的需要
给大家介绍一下tracking的方向
于是拿了这个很经典的模型开讲

以及我的csdn上的博客写的太烂了
借这个机会详细写一次…

直接把做好的ppt放这里吧

本文于本人在2017.12.19于csdn首发
现在修改重新复盘回顾

比赛介绍

给定用户人口统计特征，歌曲信息，预测用户听了某歌后未来一个月内是否会重新聆听

数据集

约三四万的用户
约两百多万首歌
用户-歌曲对 测试集和训练集共有约一千万个

时间分配

时间上的分配:印象中开始打了两周左右就丢那里了吧,结尾一周多又去打了…
中间没去搞犯懒癌
不过最后还是拿到了一个比较满意的成绩，13名。
不过差一点就金牌了呀!!! emmmm…

自己的trick

挑一些比较重要的

1. 计数特征 : 比如歌曲被播放次数，用户听歌次数，歌手被听次数等等,就是一些热度特征 活跃度等等重要指标
2. 条件概率特征 : 批量生成 P(歌曲|用户） P（用户|歌曲） P（作词人|用户） 等等等等
3. 相似度 : 将用户，歌曲，歌手的网络结构拓扑图丢给node2vec对用户，歌曲，歌手进行编码，再计算他们的皮尔森相关系数作为他们的相似度
4. 按时间轴加权,离当前时间越近的权重越高
5. 依赖时间的计数/条件概率特征依照时间窗口滑窗生成
6. 试过神经网络embedding，歌手歌曲用户进行词嵌入来学习，搭了一个1D的类DesnseNet结构，分数最高也就68点多。于是乎放弃(其实现在看来初始化不行,那时候应该先node2vec预训练的,无论对树和神经网络效果都应该很bug
7. 尝试过数据集分历史数据和当前两部分，lgbm对历史数据进行训练再对当前数据预测输出样本的叶子节点信息，一般般

top1,top3的做法

1. 生成用户歌曲对特征，SVD分解获得用户歌曲对向量，将向量整个作为特征显著提升
   这个当时没做,那时候好像因为最后一两周才回来搞没啥时间了,也不敢svd直接分内存太大了
   讲道理node2vec也可以替代的不是
2. top1使用了样本的上下文信息(过去与未来的log)
   现在看来无论top1还是top3上下文信息的利用的不够干脆
   样本非独立,除了用户上下文信息可以用,歌曲上个时间点被谁听了,下个时间点等…
   神经网络讲道理也可以用的
3. top1尝试了伪标签但效果不好
   话说这里那次比赛就有人用伪标签…居然被我忽略了,我那时候眼神不好吧…
   这里效果不好很显然,上次毒性分类比赛效果好是因为模型生成的伪标签质量高噪声小
   这里平均只有七十多的正确率的标签噪声太多…
4. top3数据全转为数字保存为hdf这种图片格式，貌似比csv读写快？
5. top3也将数据分成了历史信息和当前信息,将数据索引作为时间轴
   (1)上下文信息
   (2)统计了一堆历史信息中和label相关的特征放到当前信息中,最终将当前的数据样本放进去训练
   现在感觉这种操作比较冗余

其他体会

高性能编程超级超级超级重要,从那次和之后的比赛看出多核,GPU的优势必须用出来
有些复杂的特征必须要快速造出来

没干的事

集成最后也比较草草的直接加权，毕竟没啥时间了。
调参也没调，不过正好说明了老生常谈的论特征的重要性
恩，最后….以后一定得大胆想大胆试，人有多大胆地有多大产hh

2018.07.15
就打了五天的就放弃的比赛,最后居然排名有128/2522 ???
我都以为跌开top10%了
…… 意外收货

该博文于本人在2018.01.11在csdn首发
https://blog.csdn.net/qrfaction/article/details/79039283

现在看过去还有有一部分可改的方式
比如概率密度等… 不过就不加上去了
现在看几个月前的还没形成个初步方法论的自己感觉想法怪嫩的hh

血糖值预测从开始到放弃

这次开开心心的和师兄们组了个队一起去打比赛，开始成绩不错后来成绩真是风云变幻。。。


在比赛官方交流群里一个人无意间透露了一个trick被我注意到了
在我一番尝试后发现了这个trick
然后发现了排名从浮动高潮逐渐走向低潮又转向高潮的原因
然后我愤愤不平的揭露了这个作弊方式
详见
https://tianchi.aliyun.com/competition/rankingList.htm?spm=5176.100067.5678.4.13b54520outEjm&raceId=231638


我最开始是在钉钉交流群揭露这个的
然后莫名其妙被怼 ？？？？？？？？？？
我怕是得罪了一些既得利益者
简直莫名其妙

正题

就打了五天 做的事不多

1. 批量生成加减乘除组合特征扔给树 选择权重前几名的
2. 根据上述筛选的特征重复更复杂的组合筛选(效果超显著)
3. 一个全是连续值的比赛 区间按分位数分段两两组合 效果不咋样于是乎没筛选
4. Box-Cox将血糖值变为正态分布,重新定义xgb && lgb的损失和评估函数效果不咋样
5. 模型对高血糖值预测无能
    将均方误差改为三/四次项 尝试扩大大样本值预测不准的loss加大模型对他们的关注度(效果不显著）
6. 高值样本加权,效果不显著

还未实现的idea

1. 实现特征运算的表达式求值计算器,便于高效率的批量生成特征和筛选
2. 用线性模型优化特征的组合权重,从而优化树模型
3. 线性模型拟合Box-Cox后的血糖值,或者将CNN配合Box-Cox逆变换做激活函数拟合血糖值
4. 树的叶子节点,模型预测值 配合stacking生成一批新特征
5. LFM尝试拟合乙肝的缺失值(感觉肯定效果不好,因为确实的特征是一列缺大半)
6. 修改borderline-smote来生成高血糖样本
7. 大多数特征偏正态,将其概率密度作为特征
8. 度量学习获取一个不错的距离度量然后聚类特征

比赛中出现的小事故
代码去量纲做错了。。。
特征四则运算组合效果肯定差了很多。。。因此错失了很多强特征 可惜可惜
还有个难点是特征异常值是不能去的，那个决定了能否预测到高血糖值的糖尿病人
很多看似是异常值实际是模型预测高血糖的关键
而且不能z-score标准化 因为会造成数据正负问题
提出初步方案

1. 特征除以三倍标准差加均值
2. 特征除以Q3 + 1.5(Q3-Q1)
   已经弃赛了自然懒得修这个bug了

强强的师兄的几个idea
发现比赛方的数据貌似来自北京的某医院…
于是乎把训练集测试集里的日期相关温度全部爬了过来
原因是温度会影响血糖值的大小…
这也是体检日期是一个还不错的特征的原因…
虽然线上效果不明显
但线下略有提升 我相信这肯定是测试集太小的缘故

高性能CUDA应用设计与开发第四章阅读笔记

CUDA调度层次结构

千兆全局调度器 -> 流式处理器(SM) -> wrap调度器 -> SIMD处理器核心 -> 线程

以GF100流多处理器距离为例

2个wrap调度器:给SIMD核心分配任务
32个SIMD核心:单指令多线程调度,并发执行一个或半个wrap(32)的线程
16个存取单元(LD/ST)
4个特殊运算单元(SFU)

wrap指令分配

GF100有两个wrap调度器和两个指令分配单元
这使得两个wrap调度器可以并行执行
wrap调度器的大部分指令都可以双发射并行处理
如整型,浮点型,加载,存储的混合与SFU混合的指令(双精度不支持)

SFU,LD/ST以及SIMD核心都是彼此独立的,所以他们可以并行执行

wrap分歧

一个wrap内的线程各条件分支子句间是串行执行的,例如

if p:
    ...
else:
    ...

其中进入第一个分支的线程会首先执行,非这个分支的线程会挂起
之后第二个分支的线程执行,其他线程挂起
毕竟SIMD要求的是单指令多线程
所以条件分支过多,会导致运行速度成倍减少…

Fermi架构GPU的分支预测技术:

在使用分支预测时,所有分支会并行执行
但条件为假的指令不会被写回结果,计算地址或读取操作数(这些开销没了)


只有条件分支的数量小于一个阈值的时候才会使用分支预测(分支太多并行开销也会比较大)
编译器在推断条件会导致产生许多有分歧的wrap时阈值为7,否则阈值为4

wrap表决

分支中代码过长,nvcc编译器还会插入代码执行wrap表决,检查wrap内所有线程是否执行相同的分支


all(int predicate)：如果当前线程所在的Wrap所有线程的predicate不为0，则返回1。 any(int predicate)：如果当前线程所在的Wrap有一个线程的predicate值不为0，则返回1。
__ballot(int predicate)：Wrap中第N个线程的predicate值不为0，则将整数0的第N位进行置位。


通过此方式决定是否要进行分支预测
某些情况编译器能够在编译时确定wrap内所有分支是否会执行相同路径
例如将一个共享变量作为分支变量,此时所有线程将进入同一分支没有开销

线程级并行(TLP)

书上说了很多…其实就一个意思,多添线程块提高占用率,保持各种单元(存储,执行,特殊运算)繁忙

指令级并行(ILP)

高占用率不一定是最佳应用性能
使用ILP的原因:使用较少的线程意味着每个线程可以使用更多的寄存器
为每个线程多分配一点寄存器可以防止寄存器溢出并保持高性能

pragma unroll 预编译指令

pragma unroll 16可以将for循环内的代码展开16次
这样就减少了for循环中的比较与分支操作
更多的独立指令可以提高ILP并隐藏流水线与内存访问的延迟

总而言之言而总之
所有的存储器中只有寄存器能够满足GPU数以万计的计算要求的存储带宽需求
寄存器很重要!!!
然后wrap分歧问题需要十分重视!!!
尽量以等价形式的代码减少wrap分歧!!!

多线程编程需要考虑的资源竞争问题而引入互斥与同步
为提高并行率而需要任务调度分配

互斥

critical指令

#include "omp.h"
#include "iostream"
#include <stdlib.h> 

using namespace std;

int main(){

    int sum=0;

    #pragma omp parallel for 
    for(int i=0;i<10;++i){

        #pragma omp critical
        {
            sum +=i;
        }
    }
    cout<<"sum "<<sum<<endl;
}

critical可以将指定的代码块加锁
使得任何时候只有一个线程可访问这块区域

atomic指令(原子操作)

将上面代码中的

#pragma omp critical
           {
               sum +=i;
           }

替换为

#pragma omp atomic
           sum +=i;

也可以实现加锁
与之不同的是atomic是对单个指令加锁

同步

barrier指令

#include "omp.h"
#include "iostream"
#include <stdio.h>

using namespace std;

int main(){

    int sum=0;

    #pragma omp parallel
    {
        for(int i=0;i<10;++i){
            sum +=i;
        }
        #pragma omp barrier
        printf("sum: %d\n",sum);
    }

}

程序输出如下

sum: 105
sum: 105
sum: 105
sum: 105

如果不加 #pragma omp parallel
输出为

sum: 73
sum: 45
sum: 90
sum: 45

barrier指令使得各线程同步访问sum变量使得输出一致

OpenMP采用的是fork-join执行模式
故在每个并行的线程块结束后都会隐式同步(等效barrier)
可以使用nowait子句取消
如(都没有parallel)

#pragma omp for nowait
#pragma omp sections nowait

ordered子句

#include "omp.h"
#include "iostream"
#include <stdio.h>

using namespace std;

int main(){

    #pragma omp parallel for ordered
    for(int i=0;i<4;++i){

        #pragma omp ordered
        printf("id: %d\n",omp_get_thread_num());
    }

}

运行结果如下

id: 0
id: 1
id: 2
id: 3

在parallel for后加上ordered子句后
就可以在代码块中使用 #pragma omp ordered 同步执行

master子句

int main(){

    #pragma omp parallel 
    {

        #pragma omp master
        {
            printf("id: %d\n",omp_get_thread_num());
        }
    }
}

程序输出如下

id: 0

这个子句保证了这块代码只由主线程执行

任务分配

schedule子句

static 静态调度

int main(){

    #pragma omp parallel for schedule(static,3)
    for(int i=0;i<8;++i)
    {
        printf("id: %d\n",omp_get_thread_num());
    }

}

输出如下

id: 0
id: 0
id: 0
id: 2
id: 2
id: 1
id: 1
id: 1

dynamic 动态调度

int main(){

    #pragma omp parallel for schedule(dynamic,2)
    for(int i=0;i<12;++i)
    {
        printf("result: %d\tid:%d\n",
                i*i*i*i*i*i,
                omp_get_thread_num());
    }

}

执行结果如下

result: 64    id:0
result: 729    id:0
result: 262144    id:0
result: 531441    id:0
result: 1000000    id:0
result: 1771561    id:0
result: 4096    id:2
result: 15625    id:2
result: 46656    id:3
result: 117649    id:3
result: 0    id:1
result: 1    id:1

(dynamic,2) 每次分配给线程2个任务
谁先完成谁继续接受任务
使得能达到核心的高占用率

guided调度

一开始给每个线程分配多于size个任务
然后分配的任务数指数级下降
直到分配任务数下降到size后不变

runtime调度

根据环境变量OMP_SCHEDULE选择调度方式
最终还是落实到上面三个的其中一个

single指令

int main(){

    #pragma omp parallel 
    {
        #pragma omp single
        {
            printf("hello world\n");
        }
        printf("nice to meet you\n");
    }
}

程序执行如下

hello world
nice to meet you
nice to meet you
nice to meet you
nice to meet you

被single指定的线程块只会被执行一次