scmmm's blog

CF1804C 题目大意：你有个 nnn 面体骰子(面上的数字是 000 到n−1n-1n−1 )，初始1的数字是 xxx ，定义一种操作 f(x)f(x)f(x) 是让骰子走 n∗(n+1)2\frac{n*(n+1)}{2}2n∗(n+1)​ 步（例如五面的初始在 333，走 f(2)f(2)f(2) 是走 3→0→13 \to 0 \to 13→0→1） 手推一下发现最多执行到 f(2n)f(2n)f(2n) 因为考虑 $0\to 2n $ 这个过程，n∣f(2n)n|f(2n)n∣f(2n) ，因此 2n2n2n 步是循环的 1234567891011121314151617181920212223242526272829#include<bits/stdc++.h>using namespace std;int n,x,T,p;int main(){ ios::sync_with_stdio(false); cin>>T; while(T--) { int flg=0; cin>>n>>x>> ...

余弦退火函数 123from torch.optim.lr_scheduler import CosineAnnealingLR,CosineAnnealingWarmRestarts,StepLRscheduler = CosineAnnealingWarmRestarts(optimizer,T_0=2,T_mult=2) 上古先贤的智慧 如果 T_mult=1 就在 T_0,2T_0,...,NT_0 取得 lr 最大值 否则，在 T_0+n*T_mult , n in [0,N] 取得 lr 最大值 BN Batch Normalization 名词：convariate shift 协变量便宜，由于网络是 deep 的，每一层的输出变化会导致下一层输入数据的偏移，因此后面的网络需要不断适应这个变化，导致训练效率降低。 Internal Covariate Shift=ICS 解决方式： 白化（Whitening） 白化（Whitening）是机器学习里面常用的一种规范化数据分布的方法，主要是PCA白化与ZCA白化。白化是对输入数据分布进行变换，进而达到以下两个目的： 使得 ...

ER 网络 由 wiki 上面的说法，存在两种 ER 网络，分别为 G(n,p)G(n,p)G(n,p) 与 G(n,M)G(n,M)G(n,M) G(n,p)G(n,p)G(n,p) 每个点对按照 ppp 的概率连接 12345678910111213141516171819202122void ernp(){ cin>>n>>p; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { double k=1.0*rand()/RAND_MAX; if(k<=p) { a[i][j]=1; a[j][i]=1; m++; } } cout<<n<<" "<<m<<'\n'; for(int i=1;i<=n;i++) cout<<i<<'\n'; for(int i=1;i<=n;i++) for ...

2023-2-23 ICA,Gibbs抽样 选修-复杂网络与数据挖掘 2023-3-15 首先是短期内学完本学期的数分和高代，然后是多写几个pytorch模型

General GNN Framework 通用GNN框架 图增强 之前的假设是输入图=计算图，但是有可能遇到图缺少特征性或者图的结构不利于计算。 例如，图过于稀疏（sparse），那就导致无效的消息传递，如果过于稠密（dense），就会消耗大量时间，如果过大（large），GPU就很难算。 解决方案就是 对于图缺少特诊：使用图特征性增强。 对于稀疏图，增加虚点虚边。 对于稠密图，Sample neighbors when doing message passing 对于大的图，对子图采样后嵌入 为什么要增强 图缺少特征 做法 1.为节点分配一个常量 2.把节点编号转化成一个one-hot vector 两种方案的对比 一些图的结构在GNN上跑的不好 例如 CnC_nCn​ 这样的环，这样训练就是一个无限长度的循环 做法 1.增加虚边，例如对2-hop的邻居，此时邻接矩阵变成了 A+Az2A+Az^2A+Az2 举例，二分图的一种情况 2.增加虚节点

GNN 层 Idea 1.将一组向量压缩成单个向量 2.两部处理，包括获得信息以及聚合 消息计算 mu(l)=MSG(l)(hu(l−1))m_u^{(l)}=\text{MSG}^{(l)}(h_u^{(l-1)})mu(l)​=MSG(l)(hu(l−1)​) MSG 可以是权重指数 W(l)W^{(l)}W(l) 消息聚合 hu(l)=AGG(l)(mu(l−1)),u∈N(v)h_u^{(l)}=\text{AGG}^{(l)}(m_u^{(l-1)}) ,u\in N(v)hu(l)​=AGG(l)(mu(l−1)​),u∈N(v) AGG 函数可以是求和，平均值（mean），最大值函数等。 问题 hvlh_v^{l}hvl​ 与 hvl−1h_v^{l-1}hvl−1​ 并无直接关联 解决这个问题，可以加一个自环（考虑自身影响） mu(l)=W(l)hu(l−1)m_u{(l)}=W^{(l)}h_u^{(l-1)}mu​(l)=W(l)hu(l−1)​ mv(l)=B(l)hv(l−1)m_v{(l)}=B^{(l)}h_v^{(l-1)}mv​(l)=B(l)hv( ...

我们已经学会了一种 O(V)O(V)O(V) 的根据节点关系的 Embedding ，但是它的缺点也很显然: 节点之间不共享参数 每个节点嵌入不同 只能从样本中学习，不能处理其他的情况 有些节点自身的特性无法被利用 于是提出了 graph neural networks ，这样一个节点的嵌入 ENC(v)\text{ENC}(v)ENC(v) 基于图的多层非线性转换（multiple layers of non-linear transformations based on graph structure） Basics of deep learning 优化参数 处理一个监督式学习的时候，我们需要优化这个问题，我们要最小化这个公式 min⁡ΘL(y,f(x))\min_{\Theta}\limits \mathcal{L}(y,f(x))Θmin​L(y,f(x)) 其中 θ\thetaθ 为我们要优化的参数， L(y,f(x))\mathcal{L}(y,f(x))L(y,f(x)) 为目标函数（损失函数） 损失函数有几种 L2: ∣∣y−f(x)∣∣2||y-f(x)| ...

前言 已知一部分节点的标签，利用节点之间的关系预测节点的属性（半监督学习） Intuition: Correlations (dependencies) exist in networks 三种方法： Relational classification Iterative classification Correct & Smooth 定义 Homophily The tendency of individuals to associate and bond with similar others 大概就是趋向性的意思，个体与周围的相关性趋势。 Influence Social connections can influence the individual characteristics of a person 节点之间的关系（边）能影响一个节点性质 预测节点标签 原理 Similar nodes are typically close together or directly connected in the network 因此预测节点 vvv 的标签，只需要知 ...

Link Analysis: PageRank (Graph as Matrix) 由于每章都有很多芝士点，所以我打算改成一章一章来了 前言 用邻接矩阵的形式来看这张图 目标 定义图上节点的重要性，比如互联网上每个网站的重要性（node:网站,edge=hyperlink，directed） 有些情况暂时不需要考虑： 1.pages created on the fly 大概是随手生成的 2.dark matter 有密码这样的 应用场景 网页内，网页间，引用，百科等。 PageRank Link Analysis approaches 主要是三种 PageRank , Personalized PageRank (PPR) 和 Random Walk with Restarts 方法就是把超链接视为权重，如果自己被重要的网站挂了重要的网站（权重）有一个指向该网站的超链接，那显然这个网站权重也很高，我们通过这个方式计算每个网站的权重，显然这是一个递归问题。 计算权重 假设第 iii 点权重为 rir_iri​ ， 度数为 did_idi​ （出度） ,我们可以让 iii 连接的 ...