发表于 | | 阅读次数:

Abstract

  1. 输入的训练数据是图结构数据，使用masked self-attentional层解决先前图卷积的缺点
  2. 通过叠加层扩展邻居的范围(我记得GCN也有这个特性)
  3. 在邻居范围内，可以隐式地赋予不同节点不同权重，代表了他们的重要性。
  4. 不需要知道矩阵操作或者知道图的结构
  5. 主要是解决了图的谱方法的缺点，适用于inductive和transductive问题。

Introduction

  1. 前面主要是说CNN在图像等结构化数据上表现良好，但是针对图这样的非结构化数据目前没有什么好的解决方案，于是有了很多相关工作。

  2. 然后分别介绍了谱方法(spectral)和非谱方法，这里没有看得很明白，主要是有太多的相关工作。

  3. 介绍了注意力机制attention。有几点好处：

      3.1 可并行
  3.2 可处理不同度的点，通过赋予邻居不同的权重
  3.3 可直接用于处理inductive问题

GAT architecture

  1. 只介绍一层，通过堆叠该层可以展示任意结构。GAT只使用了这一个结构。

  2. 自己归纳一下整体流程(其实论文里很清晰)：

     2.1 通过一个全连接层，是一个W矩阵
 2.2 首先确定该点的邻居节点(只有直接相连的才是邻居)，然后通过一个attention机制，最后计算一下softmax(是为了normalize化)。此时每个点都有自己的alpha。
 2.3 再次汇聚邻居节点，将综合后的结果通过一个激活函数。

  3. 为了稳定效果，还使用了multi-head机制。就是独立进行上述进程，然后进行拼接或者求平均。（最后一层肯定是求平均）

比较相关工作

  1. 可并行计算，没有高代价的矩阵操作。
  2. 和GCN不同，可以为邻居节点隐式设置不同权重(这里没有想明白，是如何设置的？)
  3. attention机制使得我们不必关注整个图，只需要看局部结构就可以
  4. 最新的inductive工作是固定邻居数目，看不到所有邻居，并且对节点顺序有要求。GAT没有这些问题
  5. GAT可以被看作是MoNet的一个特例

问题和未来工作

  1. 他们应该是基于tensorflow写的，TensorFlow只支持rank=2的tensor进行稀疏矩阵乘法，这限制了batching的能力，比如针对多图结构。
  2. 由于是稀疏的，因此GPU不能显著加速。
  3. receptive field的上限就是层的深度
  4. 并行计算可能涉及到冗余计算，因为邻居可能是高度重叠的。(这个也没有看懂)

实验

没有细看。结论就是要么和最先进的技术持平，要么就是超过了最先进的技术。

结论

发表于 | | 阅读次数:

  1. 很有用的资料

  2. 整体思路如下：

    1. 卷积本质上就是利用周围节点的输出对中心节点进行求值。
    2. 卷积可以在规则图形上很有效，但是对于拓扑图这样的结构无法使用(例如每个节点的邻居节点的个数都不相同)。
    3. GCN研究的就是如何将卷积应用到拓扑图上。换句话说，就是如何有效利用周围节点进行求中心节点的值（既要模型效果好，又不需要大量参数参与到运算）。

  3. GCN的输入由两部分组成，一是拓扑结构(邻接矩阵)，二是每个节点的特征向量。

发表于 | | 阅读次数:

DATASET CLASS

  1. 自定义的dataset类需要继承torch.utils.data.Dataset。并且实现两个函数：len、getitem。
  2. 注意FaceLandmarksDataset只将landmarks存储到内存中，image是lazy-loading的机制。

TRANSFORMS

ITERATING THROUGH THE DATASET

  1. torch.utils.data.DataLoader可以补充三个功能：batch the data、shuffling the data、load the data in parallel using multiprocessing workers.它是一个iterator。

AFTERWORD: TORCHVISION

发表于 | | 阅读次数:

命令附录：

  1. torch.empty 没有初始化
  2. torch.rand 随机初始化
  3. torch.zeros 0初始化
  4. torch.tensor 使用数据进行初始化
  5. x.new_ones new_*可以指定size
  6. torch.randn_like 使用既有的tensor进行初始化
  7. x+y、torch.add(x, y)、torch.add(x, y, out=result)
  8. y.add_(x) 原地加 命令后面带上“_”的都是原地操作。
  9. torch.view 可以resize/reshape tensor
  10. 参数为-1，是说该值可以从其他维度推算出来
  11. tensor.item() 得到python的数值
  12. tensor.numpy() 可以得到对应的numpy形式，注意共享内存
  13. torch.from_numpy(a) a是是numpy类型，将numpy转化为tensor
  14. device = torch.device(“cuda”) 返回一个CUDA device object
  15. y = torch.ones_like(x, device=device) 直接创建一个GPU-Tensor
  16. x = x.to(device) cpu-tensor转化为gpu-tensor
  17. z.to(“cpu”, torch.double) to除了可以转换设备，也可以转换类型。

WHAT IS PYTORCH?

  1. pytorch基于python，有两点优势：可以代替numpy使用GPU进行科学计算；是一个深度学习的研究平台，提供了最大的灵活性和速度。

GETTING STARTED

Tensors

  1. torch.Size 是一个tuple。

Operations

  1. 同一个操作可能有多个语法。
  2. Numpy的索引操作都适用于Tensor。

NUMPY BRIDGE

  1. Tensor可以与Numpy array轻易转换，但要注意两者共享内存，双向转换都是共享内存。
  2. 除了char类型的tensor,cpu上的tensor都可以和numpy相互转化。根据这句话，我推断gpu上的tensor不可以。

CUDA TENSORS

  1. 使用to,可以将tensor在设备之间进行转化。

AUTOGRAD: AUTOMATIC DIFFERENTIATION

autograd包提供自动微分。

TENSOR

  1. 只要将tensor的属性.requires_grad设置为true，就可以追踪到在它上面执行的操作。
  2. 完成前向计算后，执行.backward()，就可以自动计算梯度，然后梯度被保存在.grad属性中。
  3. detach()解释1、detach()解释2 我理解就是新拷贝了一个tensor,并且该tensor不会影响到老的计算图的梯度计算。如果对它更改了数值，会报错。
  4. torch.no_grad()的范围内，不会对requires_grad=True的tensor进行梯度计算。
  5. Tensor和Function交互，并且组成了一个无环图。如果一个tensor是由function产生的，则它.grad_fn的属性就会指向这个function。用户自定义tensor的.grad_fn是None。
  6. tensor是标量，则调用.backward()不需要参数，否则需要。

GRADIENTS

  1. torch.autograd计算的是Jacobian-vector product。如果一个表达式的结果是向量，则梯度是Jacobian matrix，因此需要提供一个vector相乘，才能得到autograd的计算结果。

NEURAL NETWORKS

  1. nn.Module包含layer,并且提供一个返回output的forward函数。

DEFINE THE NETWORK

  1. init初始化各个layer。forward定义网路结构，将各层联结起来。无需backward。
  2. torch.nn只支持mini-batche，不支持单个训练样本。
  3. 每一个Function节点都连接着一个Function，并编码该Function创建的Tensor的历史。

LOSS FUNCTION

BACKPROP

  1. 别忘了使用zero_grad清除梯度的历史累积量。

UPDATE THE WEIGHTS

  1. 为了使用各种优化器，则使用optimizer.step()，对模型进行更新。
  2. optimizer的初始化用到了net.parameters和learning rate。

TRAINING A CLASSIFIER

WHAT ABOUT DATA?

  1. torchvision.datasets包提供公开数据集，torch.utils.data.DataLoader提供对数据的转换。
  2. 本章教程的源代码比较多，可以参考，是规范的。但是我的学习笔记没有列出，没有必要，代码结构很清晰了。

TRAINING AN IMAGE CLASSIFIER

  1. 加载、转换数据，划分训练集和测试集。
  2. 定义CNN的网络结构。
  3. 定义损失函数。
  4. 使用训练集训练网络。
  5. 使用测试集测试模型。

TRAINING ON GPU

  1. 模型和数据都要使用to，从cpu迁移到gpu上。其中，数据要进行覆盖。

OPTIONAL: DATA PARALLELISM

  1. pytorch默认值使用单个GPU。因此如果使用数据并行，需要对模型进行封装：model = nn.DataParallel(model)。

IMPORTS AND PARAMETERS

DUMMY DATASET

SIMPLE MODEL

CREATE MODEL AND DATAPARALLEL

RUN THE MODEL

RESULTS

SUMMARY

发表于 | | 阅读次数:

链接

WHAT IS A STATE_DICT?

  1. 模型参数(weights and biases)都存储在model.parameters()。
  2. state_dict应该是以layer为单位进行表示(weights和biases分开)，字典形式。
  3. torch.nn.Module(模型)和torch.optim(优化器)都有state_dict。
  4. state_dict的组织形式参见example。

SAVING & LOADING MODEL FOR INFERENCE

  1. save:只存储参数，灵活性最大，文件后缀(.pt或者.pth)。
  2. load:加载顺序：先初始化模型，然后加载。如果是为了验证模型，别忘了使用model.eval()使得dropout和batch normalization切换为验证模式，而不是训练模式。
  3. load_state_dict()函数的参数是一个字典，不是模型路径。

Save/Load Entire Model

  1. 调用了python的pickle模块。因为pickle不存储模型类本身，只是存储“包含了模型类的文件”的路径。所以，该方法依赖于特定的类和文件路径。
  2. 这个方法很容易出现异常。

SAVING & LOADING A GENERAL CHECKPOINT FOR INFERENCE AND/OR RESUMING TRAINING

  1. 存储／加载checkpoint，用来推断或者恢复训练。
  2. 这个不止要存储state_dict，其他信息也应该放到字典里（比如optimizer的state_dict）。
  3. 存储的文件后缀一般是.tar。
  4. 加载顺序：先初始化model和optimizer吗，然后使用load方法进行加载。
  5. 如果checkpoint是为了恢复训练，则在最后要调用model.train()方法，保证模型是处于训练的状态。

SAVING MULTIPLE MODELS IN ONE FILE

  1. 一个文件存储多个模型，方法和checkpoint类似。

WARMSTARTING MODEL USING PARAMETERS FROM A DIFFERENT MODEL

  1. 新模型的一部分load老模型，或者新模型load老模型的一部分。属于迁移学习的场景。可以加速收敛。
  2. 因为新老模型的部分key是不一致的，因此load_state_dict的strict参数要设置为false，这样可以忽略不匹配的部分。
  3. 如果要将一个layer要load另一个layer的参数，并且有的参数key不匹配的时候，可以更改state_dict的key。

SAVING & LOADING MODEL ACROSS DEVICES

  1. gpu存，cpu取。load的方法要这么调用：map_location=torch.device(‘cpu’)。
  2. gpu存，gpu取。模型最后要调用model.to(torch.device(‘cuda’))。同时注意喂给模型的训练数据也应该转化为gpu的形式，并且要覆盖转化my_tensor.to(torch.device(‘cuda’))。
  3. cpu存，gpu取。首先torch.load()的参数map_location要设置为cuda:device_id。然后调用model.to(torch.device(‘cuda’))，使得模型参数转化为CUDA tensors。我猜，之所以有这步骤，是因为model里面除了有state_dict，还有其他参数需要转化为gpu形式吧。
  4. 存储数据并行训练的模型。save方法有区别，存储的是model.module.state_dict()。这样增加了load的灵活性。

发表于 | | 阅读次数:

TENSORS

Warm-up: numpy

手工计算梯度

PyTorch: Tensors

  1. pytorch可以使用GPU进行加速，50倍以上。
  2. pytorch-Tensor:n维数组，提供个各种操作,并且追踪计算图和梯度。
  3. h.clamp(min=0)。help(torch.clamp)对Tensor进行上下限的截断。
  4. h_relu.mm(w2)。 torch.mm与torch.matmul都是矩阵相乘的操作，但是mm不支持broadcast。

AUTOGRAD

PyTorch: Tensors and autograd

  1. 如果使用autograd，则在前向计算中会定义一个计算图，其中Tensor是节点，functions是边(输入、输出)。
  2. 只要定义x.requires_grad=True，就会产生另外一个Tensor(x.grad)来存储对应的梯度。
  3. autograd只需要定义前向计算就好，后面的是自动求导。
  4. 调用loss.backward()就开始自动求导了，但是没有实际进行更新。
  5. 在不必追踪梯度历史的时候，或者使用torch.no_grad，或者使用weight.grad.data。

PyTorch: Defining new autograd functions

  1. 继承torch.autograd.Function类，然后实现forward和backward函数。定义它的实例，进行调用。
  2. 感觉这个自定义autograd就是自定义graph中的layer。
  3. forward中可以使用save_for_backward对(backward需要的)中间变量进行存储。

TensorFlow: Static Graphs

  1. pytorch使用动态图，易用但是不易于优化(比如对图进行并行化的优化)。
  2. 动态图和静态图的区别是control flow，比如对于循环，tensorflow要把loop作为图的一部分，而对于pytorch,loop和图可以分离开

NN MODULE

PyTorch: nn

  1. autograd过于简陋，我们要使用nn。nn使得我们可以把计算流程抽象为一个具有多个层的图。
  2. nn中包含多个Modules，相当于neural network中的layers。nn还包含了loss functions。
  3. nn.Sequential可以对Modules进行顺序组合。
  4. 经典代码摘抄,注意torch.no_grad和model.parameters():
1
2
3
with torch.no_grad():
       for param in model.parameters():
           param -= learning_rate * param.grad

PyTorch: optim

  1. 使用目的：可以使用多种优化器，并且简化对模型权重的更新步骤。(因为autograd只是自动计算了梯度，如果使用adam,还需要手动维护一阶矩和二阶矩)。
  2. 要将模型参数传递给optimizer。并且是使用optimizer.zero_grad()来清除历史梯度的。

PyTorch: Custom nn Modules

  1. 继承nn.Module，并且定义forward。（不再需要自定义backward）注意对于forward是有要求的，比如要返回一个Tensor。

PyTorch: Control Flow + Weight Sharing

  1. 这个应该是和前面的”TensorFlow: Static Graphs”相对应，我们可以直接将torch.Module和python的控制流结合起来，而不必将loop定义在图里面，这样就很灵活，比如可以随机loop的个数。
  2. Pytorch可以重复使用同一个Module，但是Lua Torch不可以。
  3. 这个例子还包含了权重共享(Weight Sharing
    )的概念。

发表于 | | 阅读次数:

1.wuliang相对于其他框架来说，增加了一步对特征的压缩，目前能想到两个好处：

1.减少通信量。只push\pull一部分参数即可，不需要的参数不需要exchange。
2.由于是稀疏数据，并且使用了eigen库进行加速运算。重索引的话，避免了构建值为0的特征参与运算，这样减少了内存消耗，同时加快了运算速度。

2.SGC的优势：

 1.我们在实现优化器的时候，最直观的想法是把优化器放到server。DGC证明了在实现关于动量的梯度压缩时，应该把优化器放到worker,这样避免了信息的丢失。
 2.DGC增加了worker的内存存储量，因此首先SGC通过一步动量近似，减少了内存需求，同时避免了丢失重要信息。
 3.第二步。DGC有一步momentum factor masking，是为了缓解参数陈旧问题，但是这个操作在极端情况下，会使Momentum算法退化为SGD。我们在动量近似的基础上，再在server端启用动量优化器，它的作用是补偿momentum factor masking带来的信息损失，这一步显著提升了收敛速度。
 4.对于稀疏模型来说，梯度压缩带来的参数陈旧问题更加严重，因为每个特征被遍历到几率更小，因此被延迟的周期更长。我们的第三步就是为了解决参数陈旧问题。延迟更新和全局模型的不一致，影响了模型效果。我们在pull到最新全局模型的时候，先用worker端的梯度累积量对模型进行更新再计算梯度，这样最新的梯度其实是考虑了延迟信息的影响的，这样减少了全局模型和延迟信息的不一致性，加快了收敛速度。

发表于 | | 阅读次数:
  1. 处理substring search problem的模版1
  2. 处理substring search problem的模版1
  3. [位运算](https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary:-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently
  4. DFS问题，都是迭代求解。我目前侧重于什么时候需要记录起始位置，什么时候需要使用visit数组标记是否访问过。
1
2
3
4
这三个的代码里我都写了自己的心得，体会一下。
1.https://leetcode.com/problems/combinations/description/
2.https://leetcode.com/problems/permutations/description/
3.https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/

  1. 二分查找模版，直接看最后一个

  2. 单调栈的题，可以先确定while循环，再去想是单调递增栈还是单调递减栈。

  3. 计数排序：

    https://mp.weixin.qq.com/s/vn3KiV-ez79FmbZ36SX9lg
    https://zh.wikipedia.org/wiki/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F
    https://www.cnblogs.com/freedom314/p/5847092.html
    https://www.acwing.com/solution/LeetCode/content/371/

发表于 | | 阅读次数:

背景

  1. 动机：将图中的节点以低维向量进行表示。这些向量可以作为其他算法的输入特征进行训练。
  2. 方法：通过在图中进行采样得到多个“节点序列”，该序列类似于NLP中的句子，因此可以使用NLP中的技术对节点进行embedding训练。
  3. 应用：多标签分类任务、异常检测、语言网络、社交网络、引用网络、链接预测任务。
  4. 优势：模型效果好、对内存开销要求小、更加适应稀疏数据、可并行化、可增量学习。
  5. 相关工作：
    • 科研方面：之前已经有了很多论文，但是大多是基于python的demo(使用多线程进行训练),清华大学刘知远的团队也集成了工具包。但目前没有看到真正的分布式实现，在真实场景中，由于图规模巨大(e.g.社交网络)，需要分布式训练。
    • 工业界：2017年阿里凑单算法公布了其Graph Embedding细节。2018.6月Tencent-Angel在Spark on Angel上实现了LINE算法，千亿级网络。
  6. 相关综述资料：1 2
  7. 对象：本次主要对DeepWalk(2014)、LINE(2015)、node2vec(2016)进行简述，这三篇文章是递进关系,时间较早并且思想比较简单，各自的细节描述见其他三个PDF文件。

具体方法

  1. DeepWalk：总体分为两个步骤，首先通过随机游走得到节点序列，然后使用word2vec进行训练。
  2. LINE: 设计了新的边采样方法和损失函数。首先采样图中的边，然后使用每一个边对模型参数进行更新。
  3. node2vec：基于DeepWalk，只是设计了灵活的随机游走策略(DFS和BFS结合)。

对比

  1. 适用范围：DeepWalk只适用无向、无权重的图；LINE和node2vec适用任意类型的图。
  2. 模型效果：按照论文的说法，三个模型呈递进关系。
  3. 网络规模：DeepWalk(百万的点和百万的边)；LINE(百万的点和十亿的边)；node2vec(百万的点，每个点平均出度为10，它使用的数据集比较小)。

实现

  1. 框架：
    • 基于Tencent-wuliang(C++、PS)进行实现。
    • 三种方法实现步骤类似：对图进行采样，使用word2vec进行训练。因此初步计划首先实现DeepWalk，然后逐步优化为LINE和node2vec。
    • 后续计划设计一个通用的Network Embedding框架,类似于OpenNE。
  2. 实现步骤：
    • 为方便调试，首先实现word2vec。PS框架下word2vec对网络开销大，Yahoo2016论文专门针对PS架构设计了新的word2vec训练方法。
    • 实现随机游走策略。
    • 公开数据集评测，Tencent内部数据集评测。
    • 预计时间：一个月(2018.10.10)