自然语言处理领域的相关论文（附阅读笔记），模型重现以及数据处理等（代码包含TensorFlow 和 PyTorch 两个版本）
NLP-Paper
更新一些在我学习过程中阅读过的且感觉不错的论文，对于一些经典或思路很新奇的论文，会进行精读，并写一些阅读笔记同步上传更新。(内容同步更新到知乎、CSDN)，论文按照时间顺序排放。
注：
为了方便查找论文以及归档，提供了搜索工具，使用方式如下：
python3 search_kits.py
注：论文按时间排序，并进行分类归档，可直接在本页Ctrl+F查询，或使用上述搜索工具查询（推荐）
下述列表项格式：
[图算法-搜排] | The PageRank Citation Ranking: Bringing Order to the Web | 阅读笔记 | 经典的PageRank算法，最初是作为互联网网页的重要度计算方法，被用于谷歌搜索引擎网页排序。该算法的核心思想就是在有向图（带权）上定义一个随机游走模型（一阶马尔可夫链），在一定的条件下，使得极限情况访问每个节点的概率收敛到平稳分布，节点上的平稳概率值就是PageRank值，用于表示节点的重要度 | L Page et al, 1998
[聚类] | Accelerating exact k-means algorithms with geometric reasoning | 阅读笔记 | K-Means引入计算机中的那片论文，K-Means属于Partition-based methods，思想是初始化中心点，然后通过启发式算法，达到”类内的点都足够近，类间的点都足够远“的目标 | et al Dan Pelleg,1999
[异常检测-机器学习] | LOF: Identifying Density-Based Local Outliers | 阅读笔记 | 本文提出的LOF算法是基于密度的算法，其优势在于同时考虑了数据集的局部和全局属性（其中局部可达密度的定义其实暗含了一个假设，即不存在大于等于K个重复的点），异常值不是按绝对值确定的，而是相对于它们的领域点密度确定的。因此，当数据集中存在不同密度的不同集群时，LOF算法表现良好，比较适合中等高维的数据集 | Markus M. Breunig et al, 2000
[聚类] | Mean Shift: A Robust Approach toward Feature Space Analysis | 阅读笔记 | 实现的方法是滑动窗口的算法，在每次迭代中，通过将中心点移动到窗口内所有点的平均值位置（因此得名），将滑动窗口中心移向密度较高的区域。滑动窗口内的密度与其内部的点数成正比。通过转换到窗口内点的平均值位置，窗口将逐渐移动到有着更高点密度的区域。优点：Mean-Shift的最大优势就是可以自动发现簇的数量而不需要人工选择；簇的中心向最大密度点聚合的事实也是非常令人满意的，因为它可被非常直观地理解并很自然地契合数据驱动；可以处理任意形状的簇类；算法只需设置半径这一个参数，半径影响数据集的核密度估计；算法结果稳定，不需要进行类似K均值的样本初始化；缺点：不足就是窗口大小/半径“r”的选择可能是非平凡的；半径设置的太小，收敛太慢，簇类个数过多；半径设置的太大，一些簇类可能会丢失。对于较大的特征空间，计算量非常大 | Dorin Comaniciu et al,2002
[向量召回] | similarity estimation techniques from rounding algorithms | 阅读笔记 | 论文提出的SimHash是当年Google用来文本去重的算法。主要做法是将文档提取出一定数量的关键词，然后转换成哈希码并按列相加，1+weight，0-weight，得到的结果按照整数为1，负数为0得到最终的哈希码，然后将哈希码分为m个table，并分别记性计算检索 | Moses S. Charikar et al,2002
[图算法-文本摘要-无监督] | TextRank: Bringing Order into Texts | 阅读笔记 | 本文提出的是一种基于图的用于关键词抽取和文档摘要的排序算法，由PageRank算法改进而来，它利用一篇文档内部的词语间的共现信息(语义)便可以抽取关键词，并使用抽取式的自动文摘方法抽取出该文本的关键句，相对于TF-IDF方法，可以更充分的利用文本元素之间的关系。当然，它也同样存在受分词、停用词、文本清洗的影响 | Rada Mihalcea et al, 2004
[聚类] | k-means++: The Advantages of Careful Seeding | 阅读笔记 | 原始K-Means（随机选择簇中心）对于初始化簇中心敏感，因此k-means++进行了改进，随机选择第一个初始中心点，计算其他点与该中心点的距离，按照距离远的以较大的概率被选中来选择第二个初始中心点，一次类推 | et al David Arthur,2006
[聚类] | Clustering by Passing Messages Between Data Points | 阅读笔记 | 其基本思想是将全部样本看作网络的节点，然后通过网络中各条边的消息传递计算出各样本的聚类中心。聚类过程中，共有两种消息在各节点间传递，分别是responsibility和availability 。AP算法通过迭代过程不断更新每一个点的吸引度和归属度值，直到产生m个高质量的Exemplar。优点是无需指定聚类“数量”参数；聚类中心点由实际的样本点中产生；初始值不敏感，且对距离矩阵的对称性没要求。AP通过输入相似度矩阵来启动算法，因此允许数据呈非对称，数据适用范围非常大，鲁棒性很好；误差低；缺点是AP聚类应用中需要手动指定Preference和Damping factor，这其实是原有的聚类“数量”控制的变体，且算法复杂度较高 | Brendan J. Frey et al，2007
[聚类-社区发现-图算法] | Maps of random walks on complex networks reveal community structure | 阅读笔记1 / 阅读笔记2 | 经典的infomap算法，其属于动态社区发现算法。infoma的核心思想是通过构造转移概率，在图上进行随机游走来生成序列，再通过对序列做层次编码，最小化目标，从而完成聚类。其中有几个点需要说明的是：（1）转移概率的构造，例如在带权图的基础上，通过对权重的归一化得到概率（由于优化目标中只看相对概率，所以事实上归不归一化都行）；（2）随机游走是指在图中按照概率，从一个点跳到另一点，从而得到的路径序列（实现上不需要真的生成序列，解概率方程就行，目标就是优化到这个随机序列达到平稳）；（3）所谓最小化的目标，是使用层次编码的方案下，得到的最小信息熵（最短编码长度）目标函数；（4）节点合并到类的环节，是按顺序依次尝试将每个节点赋给邻居节点所在的类，取平均比特下降最大时的类赋给该节点，如果没有下降，该节点的类不变。infomap算法有很清晰的信息论解释，还几乎没有任何超参（唯一一个“穿越概率”参数） | M. Rosvall et al, 2007
[社区发现-聚类-图算法] | Near linear time algorithm to detect community structures in large-scale networks | 阅读笔记 | LPA是基于标签传播的社区发现算法，其核心的思想不复杂，通过给图中节点初始化唯一标签（PUSH算法），然后再每次迭代中随机选取节点，根据与其相连的节点所属的标签改变自己的标签，选择方式可以根据数量、权重等，如果存在多个相同则随机选取，直到多次迭代后稳定。LPA算法简单，且不需要指定社区个数，但是缺点在于算法过程中的更新顺序和随机选择，使得算法并不稳定，改进的切入点自然就是从这两个方面入手 | Usha Nandini Raghavan et al, 2007
[聚类] | A Tutorial on Spectral Clustering | 阅读笔记 | 不是原论文，但是这一篇对Spectral Clustering讲的非常好，谱聚类（Spectral Clustering），就是先用Laplacian eigenmaps对数据降维（简单地说，就是先将数据转换成邻接矩阵或相似性矩阵，再转换成Laplacian矩阵，再对Laplacian矩阵进行特征分解，把最小的K个特征向量排列在一起），然后再使用k-means完成聚类。谱聚类是个很好的方法，效果通常比k-means好，计算复杂度还低，这都要归功于降维的作用。优点：谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法比如K-Means很难做到；由于使用了降维，因此在处理高维数据聚类时的复杂度比传统聚类算法好。缺点：如果最终聚类的维度非常高，则由于降维的幅度不够，谱聚类的运行速度和最后的聚类效果均不好；聚类效果依赖于相似矩阵，不同的相似矩阵得到的最终聚类效果可能很不同 | Ulrike von Luxburg et al,2007
[异常检测-模型-机器学习] | Isolation Forest | 阅读笔记1 / 阅读笔记2 / 阅读笔记3 | 经典的孤立森林算法的初版paper，2012发表了扩充版本（Isolation-based anomaly detection）。孤立森林是一个基于Ensemble的快速离群点检测方法，主要针对的是连续型结构化数据中的异常点，具有线性的时间复杂度和高精准度。它的理论基础是（1）异常数据占样本量的比例很小；（2）异常点的特征值与正常点的差异很大。孤立森林简单高效，但是在一些情况下，比如说数据的分布不是沿着特征轴，而是随意分布，或者流型分布，孤立森林效果就不好，就需要考虑选择别的方式了 | Fei Tony Liu et al, 2008
[社区发现-图算法] | Fast unfolding of communities in large networks | 阅读笔记1 | 阅读笔记2 | 经典的Louvain算法，其是基于模块度优化的社区发现算法，且是一种启发式贪婪算法。流程是：（1）初始时将每个顶点当作一个社区，社区个数与顶点个数相同；（2）依次将每个顶点与之相邻顶点合并在一起，计算它们最大的模块度增益是否大于0，如果大于0，就将该结点放入模块度增量最大的相邻结点所在社区；（3）迭代第二步，直至算法稳定，即所有顶点所属社区不再变化；（4）将各个社区所有节点压缩成为一个结点，社区内点的权重转化为新结点环的权重，社区间权重转化为新结点边的权重；（5）重复步骤1-3，直至算法稳定。一般认为用于评估效果的模块化指数在0.3~0.7就有明显的社区结构出现。Louvain算法的优点是时间复杂度低（nlogn），适合大规模的网络、社区划分结果稳定且有具体指标、天然自带层次化。而缺点在于容易导致”过拟合“。 | Vincent D. Blondel et al, 2008
[对话系统-对话状态管理] | The Hidden Information State model: A practical framework for POMDP-based spoken dialogue management | 关于对话状态管理的文章，可以用来补充相关背景知识 | Young et al,2010
[向量召回] | Product quantization for nearest neighbor search | 阅读笔记 | 这篇Paper是PQ算法的成功开始，PQ是一种量化方法，本质上是数据的一种压缩表达方式（本篇论文使用了KMeans算法，得到质心的codebook），先将向量分成m段，每段分别根据codebook转换成压缩向量，然后使用SDC或ADC算法进行相似搜索。不过论文中进一步进行了改进，提出了IVFADC算法，一种基于倒排索引的ADC算法，分两步，第一步是PQ一遍（成为coarse quantizer），然后用向量减去量化后的向量得到残差，第二步就是在所有得到的残差集合上在进行一次PQ，最后用得到的向量建立倒排索引 | Herve Jegou et al,2011
[聚类] | Scalable K-Means++ | 阅读笔记 | K-Means++由于它的采样策略，所以难以并行，限制了其用于大规模数据集上。为了解决这个问题，k-means II 改变取样策略（以oversampling的方式），初始化一个中心点，然后循环log(n)次，每次按照一个概率计算公式选择多个point加入到中心集，最后得到的候选中心集再通过k-means++对候选中心集进行聚类，选出k个簇中心 | Bahman Bahmani et al,2012
[向量召回] | Fast Search in Hamming Space with Multi-Index Hashing | 阅读笔记 | 主要是解决在汉明空间上的R-Neighbors of query和KNN query，论文提出了一种多分段索引的哈希方法，查询效率达到了次线性，做法是r为查询的汉明距离，将汉明码切分成m段，快速找出每段中汉明距离小于r/m的结果，合并所有结果即为候选集 | Mohammad Norouzi et al,2012
[向量召回] | Learning Deep Structured Semantic Models for Web Search using Clickthrough Data | 阅读笔记 | 经典的DSSM语义相似度匹配模型，就是通常我们所说的双塔模型。使用Word Hashing的n-gram，在那个时候还是很独到的，其核心思想是将query和doc映射到到共同维度的语义空间中，通过最大化query和doc语义向量之间的余弦相似度，从而训练得到隐含语义模型，达到检索的目的。负采样1:4 | Po-Sen Huang et al,2013
[机器学习] | Parameter Server for Distributed Machine Learning | 阅读笔记 | 论文里说本篇所介绍的Parameter Server属于第三代PS，提供了更加通用的设计，架构上包括一个Server Group和若干个Worker Group，提供了如下几个特点：Efficient Communication、Elastic Scalability、Fault Tolerance and Durability、Ease of Use | Mu Li et al,2013
[向量召回] | Optimized Product Quantization | 阅读笔记 | PQ的做法是直接简单粗暴的分割原始特征向量，并没有去除相关性，而如果去除相关性之后再进行PQ可以使得检索效果更好，OPQ就提供了是的每个子空间信息均衡的方法，即使用一个正交矩阵来对聚类中心进行旋转，并提供了Non-Parametric和Parametric的两种算法思路 | Tiezheng Ge et al,2013
[语言模型] | Efficient Estimation of Word Representations in Vector Space | 阅读笔记 | Word2vec开山之作之一，专门讲训练中的两个trick：hierarchical softmax 和 negative sampling | Tomas Mikolov et al,2013
[语言模型] | Distributed Representations of Words and Phrases and their Compositionality | 阅读笔记 | Word2vec开山之作之一，在前人基础上提出更精简的语言模型框架并用于生成词向量，这个框架就是 Word2vec | Tomas Mikolov et al,2013
[向量召回] | Speeding Up the Xbox Recommender System Using a Euclidean Transformation for Inner-Product Spaces | 微软的Inner Product快速计算的方法，主要解决的是Inner Product Top-K Search的问题。通过各种公式证明，将问题简化到一个欧氏距离搜索问题后，使用一个PCA-Tree来求解 | Yoram Bachrach et al,2014
[机器学习] | Scaling Distributed Machine Learning with the Parameter Server | 阅读笔记 | 在PS中，每个 server 实际上都只负责分到的部分参数（servers共同维持一个全局的共享参数），而每个 work 也只分到部分数据和处理任务。较它之前一篇PS进行了更加细节的描述，并对一些细节进行了扩展，两篇结合起来看受益颇多 | Mu Li et al,2014
[向量召回] | Approximate nearest neighbor algorithm based on navigable small world graphs | 阅读笔记 | 经典的NSW算法，在构建近似DG图的基础上，加入Expressway mechanism。构建时，在朴素插入选近邻连接的思路上，使用废弃列表和动态列表提速 Yury Malkov et al,2014
[数据集] | The Second Dialog State Tracking Challenge | DSTC系列语料是专门用于对话状态跟踪的，非常经典，不过它的官网貌似无用了 | Henderson et al,2014
[向量召回] | Locally Optimized Product Quantization for Approximate Nearest Neighbor Search | LOPQ实在OPQ的基础上进一步优化，OPQ仅考虑了CodeBook的旋转问题，LOPQ考虑的是每个子空间进行不同的旋转 | Yannis Kalantidis et al,2014
[向量召回] | Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) | 阅读笔记 | 传统的MIPS问题找不到LSH函数，为此论文提出了一种“非对称LSH”的算法，其核心技巧就是通过“非对称变换”构造向量从而消除待查集合X的向量模长对MIPS结果的影响。巧妙的将问题转换为欧氏距离下，通过LSH函数求出NN的近似解的问题 | Anshumali Shrivastava et al,2014
[图算法-GNN-模型-无监督] | DeepWalk: Online Learning of Social Representations | 阅读笔记1 / 阅读笔记2 | 本文提出的DeepWalk是我们了解Graph Embedding无法绕过的一个方法。其核心思想是通过使用随机游走(RandomWalk)的方式在图中进行节点采样，从而使用图中节点与节点的共现关系来学习节点的向量表示（思想来源于Word2Vec的skip-g
暂无开放 Issues，或尚未同步最近议题。