Notebook

当目标函数中有不可微部分时，可使用近端梯度下降来优化（Proximal Gradient Descent） 假设目标函数如下： $$ \definecolor{energy}{RGB}{114,0,172} \definecolor{freq}{RGB}{45,177,93} \definecolor{spin}{RGB}{251,0,29} \definecolor{signal}{RGB}{18,110,213} \definecolor{circle}{RGB}{217,86,16} \definecolor{average}{RGB}{203,23,206} \definecolor{red}{RGB}{255,0,0} f(w) = g(w) + h(w) $$ 其中$g(w)$是可微凸函数，$h(w)$是不可微（或局部不可微）凸函数。 以线性回归为例， 给定$X \in \mathbb{R}^{m \times n}$, $y \in \mathbb{R}^m$， Ridge Regression的目标函数为 $$ f(\boldsymbol{w})=\underbrace{\frac{1}{2}||\boldsymbol{y}-\boldsymbol{X} \boldsymbol{w}||_{2}^{2}}_{g(\boldsymbol{w})}+\underbrace{\lambda||\boldsymbol{w}||_{2}}_{h(\boldsymbol{w})} $$ 因为$\ell_2$ norm处处可导，所以Ridge可以用SGD或GD来直接优化。但是若目标函数为Lasso，即正则化项定义为$\ell_1$ norm: $$ f(\boldsymbol{w})=\underbrace{\frac{1}{2}||\boldsymbol{y}-\boldsymbol{X} \boldsymbol{w}||_{2}^{2}}_{g(\boldsymbol{w})}+\underbrace{\lambda||\boldsymbol{w}||_{1}}_{h(\boldsymbol{w})} $$ 这里$h(w)=\lambda||\boldsymbol{w}||_{1}$在$w=0$处不可导，那么可用PGD来优化。 Proximity Operator 近端算子： 对于不可微函数$h(w)$, $h(w)$的proximity operator定义为： $$ u^* = \operatorname{prox}_{\color{signal}h}(w)=\underset{u}{\arg \min }\left(h(u)+\frac{1}{2}||u-w||_{2}^{2}\right) $$ 近端算子$\operatorname{prox}_{\color{signal}h}(w)$只和不可微凸函数$h(\cdot)$有关。 上式含义，给定一个不可微凸函数$h(\cdot)$, 给定向量$w \in \mathbb{R}^n$, 找到向量$u = u^*$, 使得公式$h(u)+\frac{1}{2}||u-w||_{2}^{2}$最小。 这个$u^* = \operatorname{prox}_{\color{signal}h}(w)$就是$h(\cdot)$在给定$w$条件下的近端算子（Proximity Operator）。$u^* = \operatorname{prox}_{\color{signal}h}(w)$要求最佳的$u^* $可以使得函数值$h(u^*)$尽可能小，同时$u^*$要尽可能接近给定的$w$。 ...

Introduction The spectral graph theory studies the properties of graphs via the eigenvalues and eigenvectors of their associated graph matrices: the adjacency matrix and the graph Laplacian and its variants. The Laplacian allows a natural link between discrete representations, such as graphs, and continuous representations, such as vector spaces and manifolds. The most important application of the Laplacian is spectral clustering that corresponds to a computationally tractable solution to the graph partitionning problem. Another application is spectral matching that solves for graph matching. ...

最大似然估计MLE 数据 $X = \{x_1, \cdots x_N\}$, 模型参数为$\theta$，Likelihood 定义为 $P(X | \theta)$：当参数为$\theta$时，观测到给定数据$X$的概率。 $$ P(X|\theta) = L(\theta | X) = P_\theta(X) \tag{1} $$ 最大似然估计 （Maximum Likelihood Estimation, MLE）: $$ \theta_{\mathrm{MLE}} = \arg \max_\theta P(X|\theta) \tag{2} $$ 最大似然估计：给定一组样本$X$，模型的参数$\theta$是研究对象。若能找到参数$\theta_{\mathrm{MLE}}$，使得样本发生的可能性最大，则此估计值$\theta_{\mathrm{MLE}}$为参数$\theta$的最大似然估计。 举例来说，如果模型是单个Gaussian Distribution下，参数为Gaussian Distribution的参数（均值$\mu$, 标准差$\Sigma$， $\theta = {\mu, \Sigma}$）. 给定一组数据$X$, 要计算$X$来自什么样的Gaussian，即：$P(\cdot | \theta) = f_\theta(\cdot) = \mathcal{N}(\cdot | \mu,\Sigma)$是一个Gaussian Distribution函数，目标为： $$ \theta_{\mathrm{MLE}} = \mu^\star, \Sigma^\star = \arg \max_{\mu,\Sigma} \sum^N_{i = 1} \log \mathcal{N}(x_i|\mu,\Sigma) \tag{3} $$ 即MLE的目标是找到最佳的高斯分布，是的从该分布中采样出数据$X$的概率最高。 ...

这篇笔记用于收藏别人的博客 Tech Blog Blog Author https://michael-bronstein.medium.com/ Michael Bronstein https://geometricdeeplearning.com/ Michael Bronstein https://www.notion.so/Paper-Notes-by-Vitaly-Kurin-97827e14e5cd4183815cfe3a5ecf2f4c Vitaly Kurin (Many Paper Notes) https://uvadlc-notebooks.readthedocs.io/en/latest/tutorial_notebooks/tutorial1/Lisa_Cluster.html UvA DL Notebooks https://graph-neural-networks.github.io/index.html GNN Books http://prob140.org/sp17/textbook/ Probability for Data Science class at UC Berkeley https://graphreason.github.io/schedule.html Learning and Reasoning with Graph-Structured Representations ICML 2019 Workshop https://chuxuzhang.github.io/KDD21_Tutorial.html KDD2021 Tutorial: Data Efficient Learning on Graphs http://songcy.net/posts/ Changyue Song (Kernel) https://www.cs.mcgill.ca/~wlh/grl_book/ William L. Hamilton https://kexue.fm/ BoJone https://danielegrattarola.github.io/blog/ Daniele Grattarola (EPFL) https://ai.googleblog.com/2022/03/robust-graph-neural-networks.html Google AI Blog https://zhiyuchen.com/blogs/ Zhiyu Chen https://andreasloukas.blog/ Andreas Loukas (EPFL) https://irhum.pubpub.org/pub/gnn/release/4 Understanding Graph Neural Networks https://lilianweng.github.io/ Lilian Weng https://www.zhihu.com/column/marlin 深度学习与图网络 https://github.com/roboticcam/machine-learning-notes Yida Xu https://www.dgl.ai/pages/index.html DGL https://www.kexinhuang.com/tech-blog Kexin Huang https://rish16.notion.site/a8c6fcb0c29c4764afa1926ad33084f8?v=bb27bb0444574fbd85f0c9d7e43b9da8 Rishabh Anand https://saashanair.com/blog Saasha Nair http://www.huaxiaozhuan.com/ 华校专 https://github.com/dglai/WWW20-Hands-on-Tutorial DGL https://blog.csdn.net/CSDNTianJi/article/details/104195306 Meng Liu https://www.chaitjo.com/post/ Chaitanya K. Joshi https://scottfreitas.medium.com/ Scott Freitas https://fabianfuchsml.github.io/ Fabian Fuchs https://medium.com/@pantelis.elinas Pantelis Elinas https://github.com/tianyicui/pack 背包9講 https://www.fenghz.xyz/ https://sakigami-yang.me/2017/08/13/about-kernel-01/ kernel https://davidham3.github.io/blog https://fenghz.github.io/index.html https://archwalker.github.io/ Awesome-Awesomes Repo Name https://github.com/naganandy/graph-based-deep-learning-literature links to conference publications in graph-based deep learning (Very, Very, Very Important) https://github.com/SherylHYX/pytorch_geometric_signed_directed PyTorch Geometric Signed Directed is a signed/directed graph neural network extension library for PyTorch Geometric. https://github.com/EdisonLeeeee/Awesome-Fair-Graph-Learning Paper Lists for Fair Graph Learning https://github.com/thunlp/PromptPapers Must-read papers on prompt-based tuning for pre-trained language models. https://github.com/zhao-tong/graph-data-augmentation-papers A curated list of graph data augmentation papers. https://github.com/Thinklab-SJTU/ThinkMatch Code & pretrained models of novel deep graph matching methods. https://github.com/FLHonker/Awesome-Knowledge-Distillation Awesome Knowledge-Distillation. 分类整理的知识蒸馏paper(2014-2021)。 https://github.com/zlpure/awesome-graph-representation-learning A curated list for awesome graph representation learning resources. https://github.com/basiralab/GNNs-in-Network-Neuroscience A review of papers proposing novel GNN methods with application to brain connectivity published in 2017-2020. https://github.com/flyingdoog/awesome-graph-explainability-papers Papers about explainability of GNNs https://github.com/yuanqidu/awesome-graph-generation A curated list of graph generation papers and resources. https://github.com/benedekrozemberczki/awesome-decision-tree-papers A collection of research papers on decision, classification and regression trees with implementations. https://github.com/AstraZeneca/awesome-explainable-graph-reasoning A collection of research papers and software related to explainability in graph machine learning. https://github.com/LirongWu/awesome-graph-self-supervised-learning Awesome Graph Self-Supervised Learning https://github.com/Chen-Cai-OSU/awesome-equivariant-network Paper list for equivariant neural network https://github.com/mengliu1998/DL4DisassortativeGraphs Papers about developing DL methods on disassortative graphs https://github.com/SunQingYun1996/Graph-Reinforcement-Learning-Papers A curated list of graph reinforcement learning papers. https://github.com/ChandlerBang/awesome-self-supervised-gnn Papers about pretraining and self-supervised learning on Graph Neural Networks (GNN). https://github.com/GRAND-Lab/Awesome-Graph-Neural-Networks Paper Lists for Graph Neural Networks https://github.com/jwzhanggy/IFMLab_GNN Graph Neural Network Models from IFM Lab https://github.com/ChandlerBang/awesome-graph-attack-papers Adversarial attacks and defenses on Graph Neural Networks. https://github.com/safe-graph/graph-adversarial-learning-literature A curated list of adversarial attacks and defenses papers on graph-structured data. https://github.com/benedekrozemberczki/awesome-graph-classification A collection of important graph embedding, classification and representation learning papers with implementations. https://github.com/benedekrozemberczki/awesome-gradient-boosting-papers A curated list of gradient boosting research papers with implementations. https://github.com/benedekrozemberczki/awesome-community-detection A curated list of community detection research papers with implementations. https://github.com/giannifranchi/awesome-uncertainty-deeplearning This repository contains a collection of surveys, datasets, papers, and codes, for predictive uncertainty estimation in deep learning models. https://sites.google.com/site/graphmatchingmethods/ Efficient Methods for Graph Matching and MAP Inference https://github.com/yueliu1999/Awesome-Deep-Graph-Clustering Awesome Deep Graph Clustering is a collection of SOTA, novel deep graph clustering methods (papers, codes, and datasets). https://github.com/jwwthu/GNN4Traffic This is the repository for the collection of Graph Neural Network for Traffic Forecasting. https://github.com/zwt233/Awesome-Auto-GNNs A paper collection about automated graph learning https://github.com/chaitjo/awesome-efficient-gnn Efficient Graph Neural Networks - a curated list of papers and projects https://github.com/Radical3-HeZhang/Awesome-Trustworthy-GNNs Awesome Resources on Trustworthy Graph Neural Networks https://github.com/EdisonLeeeee/Awesome-Masked-Autoencoders A collection of literature after or concurrent with Masked Autoencoder (MAE) (Kaiming He el al.). https://github.com/XiaoxiaoMa-MQ/Awesome-Deep-Graph-Anomaly-Detection Awesome graph anomaly detection techniques built based on deep learning frameworks. https://github.com/mengliu1998/awesome-expressive-gnn A collection of papers studying/improving the expressiveness of graph neural networks (GNNs) Useful Repo/Tools Name Info http://acronymify.com/ Model Name https://csacademy.com/app/graph_editor/ Graph Editor https://github.com/guanyingc/python_plot_utils A simple code for plotting figure, colorbar, and cropping with python https://github.com/guanyingc/latex_paper_writing_tips Tips for Writing a Research Paper using LaTeX https://github.com/JhuoW/Pytorch_Program_Templete Pytorch Program Templete GNN https://github.com/graph4ai/graph4nlp Graph4nlp is the library for the easy use of Graph Neural Networks for NLP. Welcome to visit our DLG4NLP website (https://dlg4nlp.github.io/index.html) for various learning resources! https://github.com/benedekrozemberczki/pytorch_geometric_temporal PyTorch Geometric Temporal: Spatiotemporal Signal Processing with Neural Machine Learning Models (CIKM 2021) https://github.com/ysig/GraKeL A scikit-learn compatible library for graph kernels https://github.com/jajupmochi/graphkit-learn A python package for graph kernels, graph edit distances, and graph pre-image problem. https://github.com/pliang279/awesome-phd-advice Collection of advice for prospective and current PhD students https://github.com/MLEveryday/100-Days-Of-ML-Code 100-Days-Of-ML-Code中文版 https://github.com/d2l-ai/d2l-zh 《动手学深度学习》 https://github.com/lukas-blecher/LaTeX-OCR pix2tex: Using a ViT to convert images of equations into LaTeX code. https://github.com/thunlp/OpenPrompt An Open-Source Framework for Prompt-Learning. https://github.com/snap-stanford/GraphGym Platform for designing and evaluating Graph Neural Networks (GNN) https://github.com/pygod-team/pygod A Python Library for Graph Outlier Detection (Anomaly Detection) https://github.com/MLNLP-World/Paper_Writing_Tips latex写作建议 https://github.com/dair-ai/ML-YouTube-Courses A place to discover the latest machine learning courses on YouTube. Miscellaneous Name Desc https://github.com/The-Run-Philosophy-Organization/run run学指南 https://10beasts.net/ 测评

Mean Discrepancy (MD)均值差异 判断2个分布$p$ 和$q$是否相同。 $p$分布生成一个样本空间$\mathbb{P}$ (从$p$中采样$m$个样本) $q$分布生成一个样本空间$\mathbb{Q}$（从$q$中采样$n$个样本） 函数$f$的输入为 分布生成的样本空间 如果 $$ \begin{equation} \begin{aligned} \mathrm{mean}(f(\mathbb{P})) == \mathrm{mean}(f(\mathbb{Q})) \\ i.e., \frac{1}{m}\sum^m_{i=1}f(p_i) = \frac{1}{n}\sum^n_{i=1}f(q_i) \end{aligned} \end{equation} $$ 则$p$和$q$是同一分布。 MD can be defined as $$ \begin{equation} \begin{aligned} \mathrm{MD}&=|\mathrm{mean}(f(\mathbb{P})) -\mathrm{mean}(f(\mathbb{Q})) | \\ &= |\frac{1}{m}\sum^m_{i=1}f(p_i) - \frac{1}{n}\sum^n_{i=1}f(q_i)| \end{aligned} \end{equation} $$ Maximum Mean Discrepancy (MMD) 最大均值差异 定义 MMD: 在函数集$\mathcal{F}=\{f_1, f_2, \cdots \}$中， 找到一个函数$f^*$， 使得$|\mathrm{mean}(f^*(\mathbb{P})) -\mathrm{mean}(f^*(\mathbb{Q})) |$ 最大。 这个最大值就是两个分布之间的最大均值差异（MMD）。MMD =0 表示两个分布相同。 $$ \operatorname{MMD}[\mathcal{F}, p, q]:=\sup _{f \in \mathcal{F}}\left(\mathbf{E}_{x \sim p}[f(x)]-\mathbf{E}_{y \sim q}[f(y)]\right) $$ 其中$\mathbf{E}_{x \sim p}[f(x)]$表示分布$p$在函数$f$下的均值， $\sup$为上确界直接理解为max就好。 ...

Hilbert Space Definition 1 (Norm) Let $\mathcal{F}$ be a vector space over $\mathbb{R}$ (For example $\mathcal{F}=\mathbb{R}^n$ is a vector space). A function $||\cdot||_{\mathcal{F}}: \mathcal{F} \to [0, \inf)$ is said to be a norm on $\mathcal{F}$ if ($||\cdot||_{\mathcal{F}}$ 是一个有效norm算子要满足以下条件): For $f \in \mathcal{F}$, $||f||_{\mathcal{F}}=0$ if and only if $f=0$. (norm separates points) $|\lambda f|_{\mathcal{F}}=|\lambda||f|_{\mathcal{F}}$, $\forall \lambda \in \mathbb{R}, \forall f \in \mathcal{F}$ (positive homogeneity). $|f+g|_{\mathcal{F}} \leq|f|_{\mathcal{F}}+|g|_{\mathcal{F}}, \forall f, g \in \mathcal{F}$ (triangle inequality). 向$||\cdot||_{\mathcal{F}}$中输入任意一个向量，只要满足以上条件，那么$||\cdot||_{\mathcal{F}}$是一个valid norm operator. ...

单一状态Monte Carlo规划：多臂赌博机（Multi-armed bandits） 单一状态$s$, $k$种action（$k$个摇臂）。 在摇臂赌博机问题中，$s$每次以随机采样形式采取一种行动$a$。 例如，随机拉动第$k$个赌博机，得到的reward为$R(s, a_k)$。问下一次拉动哪个赌博机，才能获得最大Reward? 多臂赌博机问题是一种序列决策问题，这种问题需要在利用（exploitation）和探索（exploration）之间保持平衡。 利用（Exploitation）： 保证在过去决策中得到最佳回报 探索（Exploration）：寄希望在未来能够得到更大的汇报 例如， $s$摇动10次赌博机，其中第5次获得最大回报，那么下一次摇动赌博机可能选第5个赌博机，即“利用”（根据过去的最佳回报来施展下一次行为），第11次摇动的action为$a_5$。 但是摇动10次后，可能有的赌博机尚未摇动，未摇动的赌博机可能会有更大回报，即“探索”。 悔值函数 如果有$k$个赌博机， 这$k$个赌博机产生的操作序列为$X_{i,1}, X_{i,2}, \cdots (i = 1,\cdots, k)$。 在时刻$t=1,2,\cdots$, 选择第$I_t$个赌博机后，可得到的奖励为$X_{I_t,t}$, 则在$n$次操作$I_1,\cdots,I_n$后，可如下定义悔值函数： $$ R_n = \max_{i=1,\cdots,k} \sum^n_{t = 1} X_{i,t}-\sum^n_{t=1}X_{I_t, t} $$ $i$: 第$i$个赌博机 $I_t$: $t$时刻选择的赌博机 $\max_{i=1,\cdots,k} \sum^n_{t = 1} X_{i,t}$: 最理想（大）的奖励 $X_{I_t, t}$: $t$时刻选择赌博机$I_t$的reward $\sum^n_{t=1}X_{I_t, t}$: $n$次选择的总奖励。 $R_n$越大，就代表$n$次决策的结果越差。 上置信区间（Upper Confidence Bound, UCB） UCB旨在探索和利用间去的平衡 在UCB方法中，使$X_{i, T_{i}(t-1)}$ 来记录第$i$个赌博机在过去$t-1$时刻内的平均奖励，则在第$t$时刻，选择使如下具有最佳上限置信区间的赌博机： $$ I_{t}=\max_{i \in{1, \ldots, k}}\left\{\overline{X_{i, T_{i}(t-1)}}+C_{t-1, T_{i}(t-1)} \right\}. $$ 其中$I_{t}$为$t$时刻要摇的赌博机， ...

最近在看GNN/GCN的时候遇到谱聚类，学了下，做了些笔记。 本文主要参考了：[1] https://www.cnblogs.com/pinard/p/6221564.html#!comments Introduction 谱聚类是图论中的算法，主要思想是空间中距离较远的两个点之间边的权重值较低， 距离较近的两个点之间边的权重值较高， 通过对所有数据点组成的图（Graph）进行切图， 使不同子图之间边的权重和尽可能低， 子图内边的权重值的和尽可能高，从而达到聚类的目的。 基础1： 无向权重图 对于边$(v_i,v_j)$, 它的权重$w_{ij} > 0$。对于没有边的节点$v_i$和$v_j$, 他们之间的权重$w_{ij}=0$。图中的节点$v_i$, 它的度$d_i$定义为和它连接的所有边的权重之和，即： $$ d_i = \sum_{j=1}^n w_{ij} $$ 根据所有节点的度值，我们可以得到一个度矩阵$D$: $$ D=\displaystyle \left(\begin{array}{ccc}{d_{1}} & {\ldots} & {\ldots} \\\ {\ldots} & {d_{2}} & {\ldots} \\\ {\vdots} & {\vdots} & {\ddots} \\\ {\ldots} & {\ldots} & {d_{n}}\end{array}\right) ^{n\times n} $$ 是一个$n \times n$的对角阵，对角元素是每个节点的度和。 定义图的邻接矩阵为$W \in \mathbb{R}^{n \times n}$， 每个元素$W_{ij}$表示节点对$(v_i,v_j)$之间的权重。 对于$V$中的一个子节点集$A \subset V$， 定义： $$|A|=A 中的节点个数 $$ $$vol(A) = \sum_{i \in A} d_i \quad 表示A中所有节点的权重之和$$ ...

最近想好好学一学Deep Learning中的优化算法（不能一直Adam了），看了一些文献，用这篇文章做个总结笔记。 Gradient Desent(梯度下降) 目标函数$f(x)$，其中$x$为模型的待优化参数，对于每个epoch $t$, $\eta_t$表示第$t$个epoch的步长。$x_t$第$t$个epoch时的参数。 (1).梯度下降的原理：目标函数（损失函数）$f(x)$关于参数$x$的梯度是损失函数上升最快的方向。所以只要让$x$沿梯度的反方向走，就可以缩小目标函数。 (2).目标函数关于参数$x$在epoch $t$时的梯度： $$g_t = \nabla_x f(x_t)$$ (3).我们要最小化$f(x)$, 所以参数$x$需要往梯度的反方向移动： $$x_{t+1} = x_t-\eta_t g_t$$ 其中$x_{t+1}$为$t+1$时刻的参数值。 Stochastic Gradient Desent(随机梯度下降) 梯度下降存在的问题有鞍点问题以及无法找到全局最优解的问题。所以引入SGD。 首先给出无偏估计的定义，稍后会用到： 无偏估计：估计量的均值等于真实值，即具体每一次估计值可能大于真实值，也可能小于真实值，而不能总是大于或小于真实值（这就产生了系统误差）。 深度学习中，目标函数通常是训练集中各个样本损失的平均，假设一个batch的大小为$n$，那么训练这个batch的损失就是$f_{batch}(x) = \frac{\displaystyle\sum_{i=1}^{n} f_i(x)}{n}$ , 所以目标函数对$x$的梯度就是： $$\nabla f_{batch}(x) = \frac{1}{n} \displaystyle\sum_{i=1}^n \nabla f_i(x)$$ 如果使用GD来优化： $$x_{t+1} = x_{t}- \eta_t \frac{1}{n} \displaystyle\sum_{i=1}^n \nabla f_i(x) \ = x_t-\eta_t \nabla f_{batch}(x)$$ 上式可以看出，当训练样本非常大时，n也将边的非常大，那么梯度计算的计算开销就比较大。 随机梯度下降（SGD）的思想是： 以一个batch为例，这个batch中有n个样本，每个样本$i \in {1, \cdots,n}$, 每次从中随机选取一个样本来更新参数$x$。 $$x_{t+1} = x_{t}-\eta_t \nabla f_i(x)$$ 这样就更新了一个batch的参数。 对比上面两个式子可以看出SGD降低了计算复杂度。上面两个式子是等价的，因为随机梯度$\nabla f_i(x)$是对梯度$\nabla f_{batch}(x)$的无偏估计，因为： $$E_i \nabla f_i(\boldsymbol{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla f_i(\boldsymbol{x}) = \nabla f_{batch}(\boldsymbol{x})$$ 符合无偏估计的定义。 ...