帕累托最优指的是这样一种社会状态：当且仅当不减少其他人的效用就无法增加任何一个人的效用时，这种社会状态就称之为帕累托最优。 1导引 1.1推荐系统基本架构 在介绍多目标融合模块之前，我们先来回顾一下推荐系统的基础架构，以及多目标融合模块在推荐系统中所处的基本位置。一种在各大厂（如快手[1]、美团[2]、阿里飞猪[3]等）中常见的“多层漏斗型”推荐系统架构如下： 上述过程中，召回、粗排、精排+多目标融合、序列/多样性重排、异构混排是在服务端进行（其中异构混排亦有放在移动端的[4]），端上重排[4]是在移动端进行。下面大致介绍一下这些步骤的作用： 召回召回是推荐系统的第一步，负责快速从大量...

1导引 图对比学习（GraphContrastiveLearning,GCL）[1][2][3]旨在以自监督的方式学习图的节点表征，其流程如下图所示： 具体而言，先以特定方式对原图\(\mathbf{A}\)进行增广，得到两个增广后的视图（view）\(\mathbf{V}_1\)和\(\mathbf{V_2}\)做为对比对（也可以是原图和增广后的视图做为对比对），并经由GCN进行编码得到两个增广视图中的节点embeddings。接着，对于某个目标节点\(i\)，我们需要使其在某个增广视图中的embedding去接近在另一个增广视图中的正样本embedding，而远离负样本embedding...

1Laplacian算子 给定无向图\(G=(V,E)\)，我们在上一篇博客《谱图论：Laplacian二次型和Markov转移算子》中介绍了其对应的Laplacian二次型： \[\mathcal{E}[f]=\frac{1}{2}\cdot\mathbb{E}_{u\simv}\left[(f(u)-f(v))^2\right]\] 这里\(f:V\rightarrow\mathbb{R}\)为图的顶点标签，\(u\simv\)表示服从均匀分布的随机无向边\((u,v)\inE\)。直观地理解，Laplacian二次型刻画了图的“能量”（energy）。\(\mathcal{E}[...

1.对整个程序的性能分析 如果只是想简单地对整个程序做计算统计，通常使用UNIX下的time命令就足够了。 (base)➜Learn-Pythontimepythonsomeprogram.py pythonsomeprogram.py0.10suser0.01ssystem98%cpu0.117total 由于我用的是Mac系统，和Linux系统的输出可能有不同，不过关键都是这三个时间： user:运行用户态代码所花费的时间，也即CPU实际用于执行该进程的时间，其他进程和进程阻塞的时间不计入此数字。 system:在内核中执行系统调用（如I/O调用）所花费的CPU时间。 total(Li...

示例代码我已经上传到了GitHub仓库：SICP-Python（包括本书其它章节的示例代码），感兴趣的童鞋可以前往查看。 即使在变化中，它也丝毫未变。 ——赫拉克利特 吾犹昔人，非昔人也。 ——僧肇 前面我们介绍了组成程序的各种基本元素，看到了如何把基本过程和基本数据组合起来，构造出复合的实体。不过对于设计程序而言，这些手段还不够，我们还需要一些能够帮助我们构造起模块化（modular）的大型系统的策略。所谓模块化，也即使这些系统能够“自然地”划分为一些内聚（coherent）的部分，使这些部分可以分别进行开发和维护。 在哲学上，组织程序的方式与我们对被模拟系统的认识息息相关。接下来我...

示例代码我已经上传到了GitHub仓库：SICP-Python（包括本书其它章节的示例代码），感兴趣的童鞋可以前往查看。 绪论 我们在第一章引进复合过程时，采用了求值的代换模型定义了将过程应用于实参（arguments）的意义： 将一个复合过程应用于一些实参，也就意味着用实参替换过程体里对应的形参（formalparameters）之后，求值这个过程体。 但正如我们在上一章博客《SICP：赋值和局部状态（Python实现）》中所讲的，一旦我们把赋值引入程序设计语言之后，这一定义就不再合适了。由于赋值的存在，变量已经不能再看作仅仅是某个值的名字，此时的变量必须以某种方式指定了一个“位置”（p...

求值器完整实现代码我已经上传到了GitHub仓库：TinySCM，感兴趣的童鞋可以前往查看。这里顺便强烈推荐UCBerkeley的同名课程CS61A。 在这个层次结构的最底层是对象语言。对象语言只涉及特定的域，而不涉及对象语言本身（比如它们的文法规则，或其中的其体句子）。如要涉及它们，则要有一种元语言。对于语言的两个层次这一经验，所有学习外国语的人都是很熟悉的。然后，就要有一种元元语言来讨论元语言，以此类推。 ——侯世达《哥德尔、埃舍尔、巴赫：集异璧之大成》 绪论 到目前为止，我们探讨的都是通过过程抽象、数据抽象以及模块化等手段来控制系统的复杂性。为了阐释这些技术，我们一直使用的是同一种编...

求值器完整实现代码我已经上传到了GitHub仓库：TinySCM，感兴趣的童鞋可以前往查看。这里顺便强烈推荐UCBerkeley的同名课程CS61A。 即使在变化中，它也丝毫未变。 ——赫拉克利特 吾犹昔人，非昔人也。 ——僧肇 绪论 在上一篇博客《SICP：元循环求值器（Python实现）》中，我们介绍了用Python对来实现一个Scheme求值器。然而，我们跳过了部分特殊形式（specialforms）和基本过程（primitiveprocedures）实现的介绍，如特殊形式中的delay、cons-stream，基本过程中的force、streawn-car、stream-map...

示例代码我已经上传到了GitHub仓库：SICP-Python（包括本书其它章节的示例代码），感兴趣的童鞋可以前往查看。 绪论 到目前为止，我们已经使用过的所有复合数据，最终都是从数值出发构造起来的（比如我们在上一篇博客《SICP2.2:层次性数据和闭包性质(Python实现)》所介绍的链表和树就基于数来进行层次化构造）。在这一节里，我们要扩充所用语言的表达能力，引进将任意符号作为数据的功能。 2.3.1Scheme语言中的引号 在《SICP》原书采用的Scheme语言（Lisp的一种方言）中，要想表示诸如(abcd)这种包含着符号的表非常简单，可以直接对数据对象加引号。例如在Scheme语言...

示例代码我已经上传到了GitHub仓库：SICP-Python（包括本书其它章节的示例代码），感兴趣的童鞋可以前往查看。 绪论 我们已经介绍过数据抽象，这是一种构造系统的方法学，它能够使程序中的大部分描述与其所操作的数据对象的具体表示无关，比如一个有理数程序的设计与有理数的实现相分离。这里的关键是构筑数据抽象屏障——在有理数的例子中即有理数的构造函数（make_rat）和获取有理数分子分母的选择函数（numer、denom）——它能将有理数的使用方式与其借助于表结构的具体表示形式隔离开。 数据抽象屏障是控制复杂性的强有力工具，然而这种类型的数据抽象还不够强大有力。从一个另一个角度看，对于一个数...

1直接改Hosts文件（现在不太管用了） 如果你是Linux或Mac系统，那么可以通过命令sudovim/etc/hosts打开Hosts文件，并加入以下内容： 140.82.114.25alive.github.com 140.82.112.25live.github.com 185.199.108.154github.githubassets.com 140.82.112.22central.github.com 185.199.108.133desktop.githubusercontent.com 185.199.108.153assets-cdn.github.com 185.199...

1进程与程序 在Linux系统中，执行一个程序或命令就可以触发一个进程，系统会给予这个进程一个ID，称为PID，同时根据触发这个进程的用户与相关属性关系，基于这个PID一组有效的权限设置。如下图所示（图片来自《鸟哥的Linux私房菜》[1]）： 举个常见的例子，我们要操作系统的时候通常是利用ssh连接程序或直接在主机上登录，然后获取shell。默认的shell是bash，对应的路径为/bin/bash，那么同时间的每个人登录都是执行/bin/bash，不过每个人获取的权限不同，如下图所示： 也就是说，当我们的登录并执行/bin/bash程序时，系统已经给了我们一个PID，这个PID就是根据...

1管道命令（pipe）介绍 众所周知，bash命令执行的时候会输出信息，但有时这些信息必须要经过几次处理之后才能得到我们想要的格式，此时应该如何处置？这就牵涉到管道命令(pipe)了。管道命令使用的是|这个界定符号。另外，管道命令与连续执行命令是不一样的，这点下面我们会说明。 我们先来看一个管道命令的例子。假设我们需要看/etc目录下有多少文件，那么可以利用ls/etc来查看，不过由于文件数量太多，导致一口气就将屏幕塞满了，而不知道前面输出的内容是啥： root@orion-orion:ls-al/etc total944 drwxr-xr-x1rootroot4096Feb1911:38. ...

1导引 在机器学习，尤其是涉及异构数据的迁移学习/联邦学习中，我们常常会涉及互信息相关的优化项，我上半年的第一份工作也是致力于此（ArXiv论文链接：FedDCSR，GitHub源码链接：FedDCSR）。其思想虽然简单，但其具体的估计与优化手段而言却大有门道，我们今天来好好总结一下，也算是对我研一下学期一个收尾。 我们知道，随机变量\(X\)和\(Y\)的互信息定义为其联合分布（joint）\(p(x,y)\)和其边缘分布（marginal）的乘积\(p(x)p(y)\)之间的KL散度（相对熵）[1]： \[\begin{aligned}I(X;Y)&=D_{\text{KL}}...

以下部分是我学习CMU15-751:TCSToolkit的课堂笔记。由于只是个人笔记，因此许多地方在推导上可能不那么严谨，还望理论大佬多多包涵。 1问题定义 1.1无向图\(G\) 在本文中，我们将研究对象限定在无向图（undirectedgraph）\(G=(V,E)\)，且满足： 有限（finite）； 允许重边和自环； 不允许度为0的顶点（即孤立，isolated顶点），但允许有多个连通分量； 此外，我们在某些情况下可能会假设\(G\)是正则的。 正则图：指各顶点的度均相同的无向简单图。 1.2顶点标签\(f\) 定义设函数 \[f:V\rightarrow\mathbb{R...

知识图谱实体对齐2：基于GNN嵌入的方法 1导引 我们在上一篇博客《知识图谱实体对齐1：基于平移(translation)嵌入的方法》中介绍了如何对基于平移嵌入+对齐损失来完成知识图谱中的实体对齐。这些方法都是通过两个平移嵌入模型来将知识图谱\(\mathcal{G}_1\)和\(\mathcal{G}_2\)的重叠实体分别进行嵌入，并加上一个对齐损失来完成对齐。不过，除了基于平移的嵌入模型之外，是否还有其它方式呢？ 答案是肯定的。目前已经提出了许多基于GNN的实体对齐方法[1]，这些方法不仅采用GNN捕捉更多的实体结构化信息，还通过诸如参数共享、参数交换等方式在embedding模块中就使实...

1导引 我们在博客《知识图谱实体对齐1：基于平移(translation)嵌入的方法》和博客《知识图谱实体对齐2：基于GNN嵌入的方法》中介绍的都是有监督的知识图谱对齐方法，它们都需要需要已经对齐好的实体做为种子（锚点），但是在实际场景下可能并没有那么多种子给我们使用。为了解决这个问题，有许多无监督/自监督的知识图谱对齐方法被提出。 2一些常见无监督和自监督方法 2.1基于GAN的方法 首先我们来看一个基于GAN的方法[1]，虽然该方法是用于解决NLP中无监督跨语言词向量对齐操作的，但是我觉得在知识图谱领域也很有借鉴意义。 在最原始的有监督跨语言词向量的对齐任务中，给定已经对齐好的字典（锚点）...

关于联邦异构知识图谱算法的完整实现代码我已经上传到了GitHub仓库：FedHKG，感兴趣的童鞋可以前往查看。 1导引 我们在博客《联邦学习：联邦场景下的多源知识图谱嵌入》中介绍了联邦场景下的知识图谱嵌入，现在让我们回顾一下其中关于数据部分的细节。在联邦场景下，\(C\)个知识图谱\(\left\{\mathcal{G}_c\right\}_{c=1}^C=\left\{\left\{\mathcal{E}_c,\mathcal{R}_c,\mathcal{T}_c\right\}\right\}_{c=1}^C\)位于不同的客户端上。知识图谱拥的实体集合\(\mathcal{E}_c\)之间...

最近《复杂网络建模》这门课要考试了，正好也在跟Stanford的《CS224W：MachineLearningWithGraphs》这门课，这里就一边整理笔记一边复习了。 1.网络的定义 网络(network)是一些通过链接(links)连接起来的对象集合，它包含以下成分： 对象：节点(nodes)/顶点(vertices)，用\(N\)表示； 交互：链接(links)/边(edges)，用\(E\)表示； 对象和交互组成的系统我们就称为网络(或图，graph)，用\(G(N,E)\)表示。 一般而言，我们用术语网络来称呼一个真实的系统，如Web、社交网络、代谢网络等，此时伴随着术语节点和...

1度分布 网络的度分布\(p(k)\)表示了一个随机选择的节点拥有度\(k\)的概率。我们设度为\(k\)的节点数目\(N_k=\sharp\text{nodeswithdegree}k\)，除以节点数量\(N\)则可得到归一化后的概率质量分布： \[P(k)=N_k/N(k\in\mathbb{N})\] 我们有：\(\sum_{k\in\mathbb{\mathbb{N}}}P(k)=1\)。对于下面这个网络： 其归一化后的度分布直方图可表示如下： 2路径 2.1图的路径 图的路径(path)指一个节点序列，使得序列中的每个节点都链接到序列中的下一个节点(注意：这里的术语不同教...