Coding-Zuo

快速排序模板 先确定分界点：$q[l] 、 q[(l+r)/2]、 q[r]$ 或随机 调整区间：小于等于x的在左半边，大于等于x的在右半边 (如何去调整) 递归处理左右两段 由数据反推算法复杂度和算法内容 实现暴力： 声明两个数组 a[] 、b[] 将$q[l~r]$ 遍历 如果 $q[i] \le x$ 放到a[]中 如果 $q[i] \ge x$ 放到b[]中 再将a、b数组放回q中 优美： 用两个指针，swap 关于JAVA中IO流类：BufferredReader的简单用法 bufferreader要比scanner快 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748package code;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Collections;p ...

DP分析——石子合并设有 NN 堆石子排成一排，其编号为 1，2，3，…，N。 每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。 例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2堆，代价为 4，得到 4 5 2， 又合并 1，2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=244+9+11=24； 如果第二步是先合并 2，3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。 问题是：找出一种合理的方法，使总的代价最小，输出最小代价。 输入格式第一行一个数 N 表示石子的堆数 N。 第二行 N 个数，表示每堆石子的质量(均不超过 1000)。 输出格式输出一个整数，表示最小代价。 数据范围1≤N≤300 1≤N≤300 输入样例：1241 3 5 2 输出样例：122 解 12345678910111213141 ...

Select, Answer and Explain: Interpretable Multi-hop Reading Comprehension over Multiple Documents摘要选择、回答和解释(SAE)系统解决多文档RC问题。 首先主要创新，用文档分类器过滤掉与答案无关的文档，从而减少分散注意力的信息量。 然后将所选择的答案相关文档输入到模型以联合预测答案和支持句子。 该模型在答案预测的表征层和支持句子预测的句子层都设置了多任务学习目标， 并在这两个任务之间进行了基于注意力的交互，对模型进行了优化。 关键词：过滤无关文档、多任务学习、混合注意力交互 在HotpotQA中什么是gold docHotpotQA通过为答案提供支持句来鼓励可解释的QA模型，这些支持句通常来自多个文档，如果文档包含答案或包含对答案的支持句，则称为“黄金文档”。 应答文本，它可以是一段文本或“是/否”。 作者从答案和支持句标签导出GOLD文档标签。我们使用 $D_i$ 表示文档 i：如果Di是黄金文档，则标记为1，否则标记为0。还将答案类型标记为以下注释之一：“Span”、“Yes”和“N ...

DP分析法—01背包问题从集合角度来分析DP问题，DP问题的题目一般都是从有限集中求得最值的问题。 01背包问题 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 $v_i$，价值是 $w_i$。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。 输入格式第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 $v_i,w_i$，用空格隔开，分别表示第 i 件物品的体积和价值。 输出格式输出一个整数，表示最大价值。 数据范围0<N,V≤10000<N,V≤10000<vi,wi≤10000<vi,wi≤1000 输入样例123454 51 22 43 44 5 输出样例：18 解最多$2^N$, 从$2^N$ 个方案里找总价值最大的方案。——有限集合的最值问题 状态表示： 选择问题一般$f(i,j)$ 第一维表示前i个物品,第二维是限制 (经验) 集合：所有只考虑前i个物品，且总体积不超过j的选法的集合。 属性：集合中每一个方案的最大价 ...

LongFormer:The Long-Document Transformer主要记录一些Longfromer的原理和使用时的细节。 摘要针对的问题： 基于Transformer的模型，由于self-attention的操作，导致不能处理很长的序列。 self-attention的处理规模和序列长度是成二次关系的。 因为self-attention对于每个token都要计算打分，也就是缩放点积中的$QK^T$ 矩阵运算。 这相当于对每个token之间都照顾到了注意信息。 每个token代表一个小格，自注意力机制的QK都是自己，所以是个正方形。 为解决这个问题，作者引入了三种具有随序列长度线性缩放的注意机制，将规模缩减成线性。 分别是局部窗口注意和任务激活的全局注意力。 并且还提供了LongFormer的预训练模型。 定义了生成结构为Long-Forward-Encoding-Decoder(LED) 引入&相关工作熟知的Bert等预训练模型，最大长度为512，多的就要截断，这样可能会潜在地导致重要的跨分区信息丢失问题。 然而当时已有的针对解决长文本的方法，都是基于自回 ...

Kaggle快速上传dataset的方法原理从国内上传到有cdn的地方(如GitHub), 再在kaggle的kernel上下载下来，直接上传dataset。 方法首先需要掌握kaggle-api的使用，kaggle-api是kaggle官方提供的命令行工具，可以从命理完成比赛数据的下载、dataset下载上传，获取榜单等操作。 https://github.com/Kaggle/kaggle-api 本地安装：pip install kaggle Kaggle已经安装好了，不用再安装 步骤1：下载账户API json https://www.kaggle.com/me/account 步骤2：在页面创建一个dataset https://www.kaggle.com/datasets 步骤3：下载dataset的metadata 运行：kaggle datasets metadata shopee-models 步骤4：下载数据集并上传到dataset 完整代码： 1234567891011121314151617181920212223# 将API json文件写到这里!mkdir ...

DUMA: Reading Comprehension with Transposition ThinkingDUMA：DUal Multi-head Co-Attention model 这是一篇针对解决多项选择任务的MRC网络结构。题目中的Transposition Think，被作者赋义为分别从文章和问题的角度来考虑对方的关注点。 主要特点： 基于预训练语言模型(得到表示编码，替代复杂的匹配网络) 衔接多层co-attention(从三元组中捕捉关系) 多项选择任务可以抽象为(文章P，问题q，选项a) 三元组。 针对多项选择的特点多项选择MRC尤其依赖于匹配网络的设计，它被认为是有效地捕捉文章、问题和答案三元组之间的关系。(不能只考虑推理如何做的更好，还要考虑答案出现的关键位置也就是匹配网络的作用) 文中总结的人在做阅读理解题时的特点： 快速通读文章的整体内容，问题和回答选项，以建立全局印象，然后进行换角度思考过程。 根据问答选项的特有信息，重新考虑文章的细节，收集问答选项的支持证据。 根据文章中的特有信息，重新考虑问题和答案选项，以确定正确的选项，排除错误的选项。 当人 ...

FreeLB: Enhanced Adversarial Training For Natural Language Understandingnlp中的对抗训练 承接上文，上文主要讲对抗训练的原理与物理意义与发展，对抗性训练是创建健壮神经网络的一种方法。在对抗性训练期间，小批次的训练样本受到对抗性扰动的污染，然后用于更新网络参数，直到得到的模型学会抵抗此类攻击，并且对模型起到了正则化的效果，提高模型泛化能力并且防止过拟合。 这篇论文结合现在流行的预训练模型或transformer模型只能结合到下游任务的embedding中。 提出FreeLB算法在GLUE上结合Roberta达到了当时的SOTA，是基于Transformer的自然语言理解和常识推理任务模型来做对抗。 摘要对抗性训练可以最小化标签保留输入扰动的最大风险，已被证明对提高语言模型的泛化能力是有效的。 FreeLB (Free Large-Batch)，通过在单词嵌入中添加对抗性扰动，并最小化输入样本周围不同区域内的对抗性风险，从而提高了嵌入空间的不变性。 在GLUE基准上的实验表明，当仅应用于精调阶段时，它能够将BERT- ...

图神经网络的对抗攻击最近要汇报一个关于安全方面的研究。本来打算讲一些和安全擦边的关于nlp对抗训练提升模型鲁棒性的内容，正好和最近学习的阅读理解比赛相关，可以作为一个提分trick。 但老师强调要和安全相关少讲过程。而nlp中的对抗样本不可以加在原始样本中，只能在embedding中加入扰动，这样就没法攻击，多数用来提升模型鲁棒性。所以就拍马研究了一下图网络的对抗攻击。 刚开始了解，希望可以从中找出可以和我研究方向结合的地方。 如有不对的地方还希望联系我指点一下。 nlp中的对抗训练&与bert结合 在上一篇文章中主要介绍的是对抗训练，其实是一种防御的策略，对提高模型而言FGM相当于加了一个正则项。 图网络攻击难点 离散的结构/特征，难以直接利用现有的基于梯度的方法。 对于“无法感知”的扰动如何定义。 节点分类往往属于直推式学习，训练数据和测试数据联合使用以学习模型，这就使得攻击方法注定是与poisoning/causative attack相关，而非仅是evasion attack。 参考文献图对抗攻击 Graph Adversarial Attack

nlp中的对抗训练学习PPT : https://coding-zuo.github.io/adversary/index.html 由于深度神经网络强大的表示学习能力，在许多领域都取得了很大的成功，包括计算机视觉、自然语言处理、语音识别等。然而，在其卓越性能的背后，深度神经网络作为一个黑箱，缺乏可解释性与鲁棒性，使得它易受到对抗攻击而对抗性攻击的存在可能是深度学习模型的一个固有弱点。 深度学习的对抗一般有两种含义： 一是生成对抗网络(Generative Adversarial Network,GAN) 代表一大类先进的生成模型。(这方面我不是很了解) 另一个则是跟对抗攻击、对抗样本相关的领域。(主要关心模型在小扰动下的稳健性) 方法介绍在CV领域，我们需要通过对模型的对抗攻击和防御来增强模型的稳健型，比如在自动驾驶系统中，要防止模型因为一些随机噪声就将红灯识别为绿灯。 在NLP领域，类似的对抗训练也是存在的，不过NLP中的对抗训练更多是作为一种正则化手段来提高模型的泛化能力！ 这使得对抗训练成为了NLP刷榜的“神器”之一，前有微软通过RoBERTa+对抗训练在GLUE上超过了原 ...