复盘｜天堂硅谷·数字经济算法编程大赛
复盘｜天堂硅谷·数字经济算法编程大赛题目-01 化学反应【模拟】按题意模拟（可以用大根堆或者平衡树），每次找两个最大的出来，直到没有剩余或只剩一个。 1 2 3 4 5 6 7 8 9 #平衡树 from sortedcontainers import SortedList class Solution: def lastMaterial(self, material: List[int]) -> int: s = SortedList(material) while len(s) > 1: a, b = s.pop(), s.pop() if a != b: s.add(a - b) return s[0] if s else 0 1 2 3 4 5 6 7 8 9 #大根堆 class Solution: def lastMaterial(self, material: List[int]) -> int: ...
李宏毅机器学习——神经网络设计技巧
李宏毅机器学习——神经网络设计技巧1 鞍点(Saddle Point)神经网络中，Gradient为0(或不存在)的点称为临界点(critical point)，其有两种可能性：局部极小(local minima)和鞍点(saddle point)。 长期以来，人们普遍认为，神经网络优化问题困难是因为较大的神经网络中包含很多局部极小值，使得算法容易陷入到其中某些点。2014年的一篇论文中提出高维非凸优化问题之所以困难，是因为存在大量的鞍点而不是局部极值。 鞍点： 一个维度向上倾斜且另一维度向下倾斜的点。这些鞍点通常被相同误差值的平面所包围，这使得算法陷入其中很难脱离出来，因为梯度在所有维度上接近于零 梯度等于零，在其附近Hessian矩阵有正的和负的特征值，行列式小于0，即是不定的。 在鞍点附近，基于梯度的优化算法会遇到较为严重的问题：鞍点处的梯度为零，鞍点通常被相同误差值的平面所包围（这个平面称为Plateaus，Plateaus是梯度接近于零的平缓区域，会降低神经网络学习速度），在高维的情形，这个鞍点附近的平坦区域范围可能非常大，这使得SGD算法很难脱离区域，即可能...
李宏毅机器学习——反向传播
李宏毅机器学习——反向传播1 反向传播原理神经网络中求解权重W的算法，分为信号的前向传播（Forward propagation，FP）和反向传播（Back propagation，BP）。前向传播得到预测值，计算输出误差，然后计算每个神经元节点对误差的贡献；反向传播根据前向传播的误差来求梯度，然后根据贡献调整原来的权重，最终达到最小化损失函数的目的。 假设只有一个隐含层，设L为损失函数。在输出层上的误差（这里$O_{k}$就是输出值$y_{out}$。）：$$L_{total}=\frac{1}{2}(d-O)^{2}=\frac{1}{2} \sum_{k=1}^{\ell}\left(d_{k}-O_{k}\right)^{2}$$ 在隐含层上的误差（这里$net_{k}=\sum(w_i*O_{k})+b$。）：$$L_{total}=\frac{1}{2} \sum_{k=1}^{c}(d_{k}-f[\sum_{j=0}^{m} w_{j k} f(n e t_{j})])^{2}=\fr...
李宏毅机器学习——梯度下降
李宏毅机器学习——梯度下降1 偏差与方差使用样本数据拟合函数，由于样本数据使采样而并非真实值本身，采样本身会带来误差。经过研究发现，其误差的期望值可以分解为三个部分：样本噪音、模型预测值的方差、预测值相对真实值的偏差，公式为：$$E\left((y-\hat{f}(x))^{2}\right)=\sigma^{2}+\operatorname{Var}[\hat{f}(x)]+(\operatorname{Bias}[\hat{f}(x)])^{2}$$其中$Bias[\hat{f}(x)] = E[\hat{f}(x) - f(x)]$，即误差的期望值 = 噪音的方差 + 模型预测值的方差 + 预测值相对真实值的偏差的平方，如下图所示。 靶心（红点）是测试样本的真实值，测试样本的y（橙色点）是真实值加上噪音，特定模型重复多次训练会得到多个具体的模型，每一个具体模型对测试样本进行一次预测，就在靶上打出一个预测值（图上蓝色的点）。所有预测值的平均就是预测值的期望（较大的浅蓝色点），浅蓝色的圆圈表示预测值的离散程度，即预测值的方差。 2 调整梯度下降的...
李宏毅机器学习——回归
李宏毅机器学习——回归回归大致可以理解为根据数据集$D$，拟合出近似的曲线，所以回归也常称为拟合（Fit）。按照自变量的数量可以分为一元回归和多元回归，按照自变量与因变量之间的函数表达式可以分为线性回归(Linear Regression)和非线性回归(Non-linear Regression)。 1 模型步骤 Step1：模型假设，选择模型框架（线性模型） Step2：模型评估，如何判断众多模型的好坏（损失函数） Step3：模型优化，如何筛选最优的模型（梯度下降） 1.1 模型假设（多元线性模型）多元线性模型就是特征x的线性组合的函数，可以表示为$y=\sum{w_ix_i}+b$，$x_i$为特征，$w_i$为权重，b为偏移量。 1.2 模型评估（损失函数）常用的损失函数是均方误差（mean-square error, MSE），也被称为最小二乘法 (least square method)，其几何意义就是欧氏距离。 不同的loss函数，具有不同的拟合特性：Hinge Loss——SVM；exp-Loss ——Boosting；log-Loss——Logis...
李宏毅机器学习——机器学习介绍
李宏毅机器学习——机器学习介绍1. 机器学习简介机器学习是人工智能的一部分, 研究如何让计算机从数据学习某种规律。机器学习的目的是通过计算机程序根据数据去优化某一个评价指标，自动的从数据发现规律, 使用这些规律做出预测。如图，机器学习可以简化为三个步骤，一、找一个function，二、让machine评价这个function，三、让machine自动地挑出最好的function。 2. 机器学习分类机器学习可大致分为监督学习、无监督学习、半监督学习、迁移学习和强化学习。 2.1 监督学习监督学习是机器学习任务的一种。它从有标签的训练数据中推导出预测函数。有标签的训练数据是指每个训练实例都包括输入和期望的输出。简单来说就是给定数据，预测标签。监督学习包括分类和回归。 2.2 无监督学习无监督学习是机器学习任务的一种。它从无标签的训练数据中推断结论。它可以在探索性数据分析阶段用于发现隐藏的模式或者对数据进行分组。简单来说就是给定数据，寻找隐藏的结构。无监督学习包括聚类和降维。 2.3 半监督学习半监督学习介于监督学习与无监督学习之间。半监督学习的任务与监督学习一致，任务中包含有明确的...
图神经网络——基本图论与PyG库
图神经网络——超大规模数据集类的创建和图预测任务实践当数据集规模超级大时，很难有足够大的内存完全存下所有数据。因此需要一个按需加载样本到内存的数据集类。 1 Dataset基类1.1 Dataset基类介绍在PyG中，通过继承torch_geometric.data.Dataset基类来自定义一个按需加载样本到内存的数据集类。继承此基类相比较继承torch_geometric.data.InMemoryDataset基类要多实现以下方法： len()：返回数据集中的样本的数量。 get()：实现加载单个图的操作。注意：在内部，getitem()返回通过调用get()来获取Data对象，并根据transform参数对它们进行选择性转换。 1.2 继承torch_geometric.data.Dataset基类的代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 impo...
图神经网络——基本图论与PyG库
图神经网络——基于图神经网络的图表征学习方法图表征学习要求在输入节点属性、边和边的属性（如果有的话）得到一个向量作为图的表征，基于图表征进一步的我们可以做图的预测，而图同构网络（Graph Isomorphism Network, GIN）的图表征网络是当前最经典的图表征学习网络。 1.GNN的邻域聚合(消息传递)GNN的目标是以图结构数据和节点特征作为输入，以学习到节点（或图）的embedding，用于分类任务。基于邻域聚合的GNN可以拆分为以下三个模块： Aggregate：聚合一阶邻域特征。 Combine：将邻居聚合的特征 与 当前节点特征合并， 以更新当前节点特征。 Readout（可选）：如果是对graph分类，需要将graph中所有节点特征转变成graph特征。 但是Aggregate的三种方式sum、mean、max的表征能力不够强大。 如上图，节点v和v’为中心节点，通过聚合邻居特征生成embedding来分析不同aggregate设置下是否能区分不同的结构。设红绿蓝色节点特征值分别为r,g,b，不考虑combine。 图a中：mean：左$\frac{1...
图神经网络——超大图上的节点表征学习
图卷积网络(GCN)已经成功地应用于许多基于图形的应用，然而大规模的GCN的训练仍然具有挑战性。目前基于SGD的算法要么面临着随GCN层数呈指数增长的高计算成本，要么面临着保存整个图形和每个节点的embedding到内存的巨大空间(显存)需求。于是论文Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Network提出了Cluster-GCN方法来解决超大图的训练问题。 1.Cluster-GCN方法简单概括 利用图节点聚类算法将一个图的节点划分为$c$个簇，每一次选择几个簇的节点和这些节点对应的边构成一个子图，然后对子图做训练。 由于是利用图节点聚类算法将节点划分为多个簇，所以簇内边的数量要比簇间边的数量多得多，所以可以提高表征利用率，并提高图神经网络的训练效率。 每一次随机选择多个簇来组成一个batch，这样不会丢失簇间的边，同时也不会有batch内类别分布偏差过大的问题。 基于小图进行训练，不会消耗很多内存空间，于是我们可以训练更深的神经网络，进而可以达到更...
图神经网络——节点分类与边预测
1.InMemoryDataset基类在PyG中，可以通过继承InMemoryDataset类来自定义一个数据可全部存储到内存的数据集类。(继承Dataset是分次加载到内存，继承InMemoryDataset是一次性加载所有数据到内存) 1 class InMemoryDataset(root: Optional[str] = None, transform: Optional[Callable] = None, pre_transform: Optional[Callable] = None, pre_filter: Optional[Callable] = None) 参数说明： transform：数据转换函数，用于转换Data对象，每一次数据获取过程中都会被执行。pre_transform：数据转换函数，用于转换Data对象，在Data对象被保存到文件前调用。pre_filter：检查数据是否要保留的函数，接收一个Data对象，返回此Data对象是否应该被包含在最终的数据集中，在Data对象被保存到文件前调用。 2.Sequential容器nn....