Posts

文本分类 文本分类是很多业务问题中广泛使用到的NLP/监督机器学习（ML）。文本分类的目标是自动将文本/文档分类为一个或多个预定义类别。目前的成熟思路是用词向量解码文本，然后使用传统机器学习模型或者深度神经网络模型来做分类。 文本分类是学术界和工业界非常活跃的研究领域。本文主要介绍用于文本分类的几种神经网络模型方法，并比较它们的性能，代码实现主要基于Keras。文中代码都在这个DeepTextGitHub项目中. 文本分类的一些示例包括： 从社交媒体中了解受众情绪（😁 😐 😥） 检测垃圾邮件和非垃圾邮件 自动标记客户查询 将新闻文章📰分类为预定义主题 端到端文本分类流水线 端到端文本分类流水线由以下组件组成： 训练文本：输入文本，有监督模型能够通过已标注数据来学习和预测所需的类。 特征向量：特征向量是用于解码输入数据特征的信息的向量。 标签：预定义的类别/类，作为模型预测的目标。 算法模型：能够处理文本分类的算法（在我们的例子中：CNN，RNN，HAN, Fasttext） 预测：已经在历史数据集上训练过的模型，可以用于执行标签预测。 这里使用汽车消费者的评测数据集，在tsv文件中, 第一列是序号对我们没用, 第二列是label(0, 1)，分别代表（消极，积极）评价，第三列是文本. 1 操控性舒服、油耗低，性价比高 0 动力的确有点点让我相信了up的确是个代步车而已! 1 1。车的外观很喜欢。2。省油，现在磨合期7.3，相信以后还会下降。 1 内饰的做工和用料同级别同价位最厚道的 0 减震系统太硬！ 数据处理使用的类，具体见代码链接 class DataProcessor(object): """ Base class for data converters for sequence classification data sets. helper funcitons [read_tsv, read_text, read_json] """ ... class SampleProcessor(DataProcessor): """ Sample processor for the classification data set. Tranform the text to tensor for training if use pre-train model, need vocabulary file usage: process data files >>> processer = SampleProcessor(config, ) provide your own data in list format [train_X, train_Y, test_X, test_Y] >>> processer = SampleProcessor(config, data) """ 词向量 使用包含外部知识的embedding表达字词是目前的主流方法，经典的如word2vec，GLoVe，较新进的 ELMo，BERT，等预训练向量，集成了关于单词的新信息（词汇和语义），这些信息已经在非常大的数据集上进行了训练和提炼。 ...

信息抽取 1997年MUC会议（MUC-7） 召开时，评测任务已经增加到5个： ① 场景模板（scenario template, ST）填充：定义了描述场景的模板及槽填充规范； ② 命名实体（named entity, NE）识别：识别出文本中出现的专有名称和有意义的数量短语， 并加以归类； ③ 共指（coreference, CR）关系确定：识别出给定文本中的参照表达（ referring expressions），并确定这些表达之间的共指关系； ④ 模板元素（template element, TE）填充：类似于人名和组织机构名识别，但是要求系统必须识别出实体的描述和名字，如果一个实体在文本中被提到了多次，使用了几种可能的描述和不同的名字形式，要求系统都要把它们识别出来，一个文本中的每个实体只有一个模板元素［Grishman and Sundheim, 1996］； ⑤ 模板关系（template relation, TR）：确定实体之间与特定领域无关的关系。 1999年起美国NIST组织了自动内容抽取（automatic content extraction, ACE）评测会议，旨在研究和 开发自动内容技术以支持对三种不同来源文本（普通文本、经语音识别后得到的文本、 由OCR识别得到的文本）的自动处理，以实现新闻语料中出现的实体、关系、事件等内容的自动抽取。评测任务设计: 实体检测与跟踪（entity detection and tracking, EDT）、数值检测与识别（value detection and recognition, VDR）、时间识别和规范化（time expression recognition and normalization, TERN）、关系检测与描述（relation detection and characterization, RDC）、事件检测与描述（event detection and characterization, EDC）和实体翻译（entity translation, ET）等。 TF-IDF 关键词抽取 import jieba.analyse jieba.analyse.extract_tags(sentence, topK=20, withWeight=False, allowPOS=()) sentence 为待提取的文本 topK 为返回几个 TF/IDF 权重最大的关键词，默认值为 20 withWeight 为是否一并返回关键词权重值，默认值为 False allowPOS 仅包括指定词性的词，默认值为空，即不筛选. 如电商评论指定要形容词 ...

Algorithms, Part I, https://online.princeton.edu/course/algorithms-part-i Algorithms, Part II, https://online.princeton.edu/course/algorithms-part-ii Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne https://algs4.cs.princeton.edu/ Union−Find Considering the dynamic connectivity problem, modeling of multiple objects connected in a space/network. Applications involve manipulating objects of all types. ・Pixels in a digital photo. ・Computers in a network. ・Friends in a social network. ・Transistors in a computer chip. Given a set of N objects. union(a, b): connect two objects. connected(p, q): is two objects connected? find(p): Find component identifier for p (0 to N – 1) Modeling the objects: array. ...

程序员或者其他需要码字多的人，经常要使用编辑器如sublime、atom 和 Typora等。如果每次都要用鼠标点击才能用sublime打开文件，或者在编辑器中新建文件，那么就会有点麻烦！但你可以用一句命令解决！ 配置在Git Bash中用各种文本编辑器打开文件或者直接新建文件。这里以atom为例。 常规步骤 打开Git Bash并cd到你的目标文件夹, 或者直接在目标文件中右键打开Git Bash. atom xxx.md 就会在弹出的atom窗口中打开名为xxx.md的markdown文件, 如果没有这个文件, 会自动创建一个. 适用于其他类型文件, 如.java等. 如果想用sublime, 可以用subl xxx.java, 同理notepad++ 可以用 notepad++ xxx.java等。 (若出现错误,看下面) 若系统无法识别命令 一般使用sublime或者notepad++的用户, 可能会出现error: 系统无法识别命令...之类的, 可以这么解决: 方法1 新建一个文件命名为subl（注意不能有后缀名），内容： #!/bin/sh "D:\Sublime Text 3\sublime_text.exe" $1 & 第一行指明这是个 shell 脚本. 第二行的字符串是sublime的安装目录, 示例只是我电脑的目录, 注意这里要改为你自己的目录, 第二行的$1 是取的命令之后输入的参数 第二行的&是此命令在后台打开，这样sublime打开之后，就不会阻塞你的git bash 文件保存到 C:\Program Files (x86)\Git\mingW32\bin 目录下(你的git目录可能与我的不一样，注意改成你自己的) 同理适用于其他编辑器，比如用chrome打开.html文件等。如果不想每次都新建一个文件，可以用下面的方法2。 方法2 找到 C:\Users\你的计算机名目录，如果你的计算机名是Administrator，那么你就要去C:\Users\Administrator目录下, 这里一般存放着windows系统的我的文档, 桌面等文件夹. 在该目录下用Git Bash输入notepad .bashrc, 这会用windows记事本新建并打开一个文件.bashrc，这个文件没有名称只有后缀名。.bashrc里面可以给Git Bash设置命令的别名, 设置路径等。 在.bashrc文件加入下面一行文本alias notepad++="/D/Notepad++/notepad++.exe", 这里你需要修改为你电脑的安装路径。alias就是别名的意思，当我们执行notepad++的时候，实际执行的是=后面的语句. 重新打开Git Bash, 设置才能生效，如果不想关掉在打开的话，可以直接在bash下输入source ~/.bashrc就可以立刻加载修改后的设置，设置立即生效。 现在在bash下输入notepad++ test.py, 就直接打开了notepad++并创建了这个叫test的Python文件。这里的别名不一定非要取notepad++，随你想叫什么都行。 同理也可以扩展到别的文本编辑器，alias atom="atom的路径", alias sublime="sublime的路径"等. 最后还要注意一点，上面所说的路径最好不要有空格，括号等，否则会造成命令无效. ...

本篇介绍 topic modeling, 以及一个经典的算法Latent Dirichlet allocation, 文本挖掘与语义理解的集大成者(至少在深度学习统治之前). 当然LDA不仅仅局限于文本, 还可应用于涉及大量数据集的各种问题，包括协同过滤，基于内容的图像检索和生物信息学等领域的数据。 Topic Modelling 大规模文本挖掘的核心问题, 就是用数学模型代替人力来理解文本语义，目标是找到对集合成员（如一堆文本）的数学/统计描述，以便能够对这些大型集合进行高效处理，同时保留对基本任务（如分类，检测，摘要以及相似性和相关性判断）有用的基本统计关系。 在这方面的研究方法很多，特别是信息检索(IR)领域. 一个基本方法是将语料库中的每个文档向量化，向量中的每个实数代表计数率。比如经典的tf-idf方法，用Document-Term Matrix来表达不同词在不同文档出现的情况差异, 一般term就是word作为features, 所以在这里我们表示document-word matrix(DWM), 就是DWM[i][j] = The number of occurrences of word_j in document_i. Doc 1: I have a fluffy cat. Doc 2: I see a fluffy dog. DWM I have a fluffy cat see dog doc1 1 1 1 1 1 0 0 doc2 1 0 1 1 0 1 1 然后进行normalization, 去和 inverse document frequency count(IDF)进行比较. IDF统计每个词在整个文档集合中出现的总次数, 通常转化为log scale, 并进行适当的normalization. ...

参考 CS229: Machine Learning, Stanford 什么是机器学习？目前有两个定义。 亚瑟·塞缪尔（Arthur Samuel）将其描述为：“不需要通过具体的编程，使计算机能够学习”。这是一个较老的，非正式的定义。 汤姆·米切尔（Tom Mitchell）提供了一个更现代的定义： E：经验，即历史的数据集。 T：某类任务。 P：任务的绩效衡量。 若该计算机程序通过利用经验E在任务T上获得了性能P的改善，则称该程序对E进行了学习 “如果计算机程序能够利用经验E，提升实现任务T的成绩P，则可以认为这个计算机程序能够从经验E中学习任务T”。 例如：玩跳棋。E =玩许多棋子游戏的经验，T = 玩跳棋的任务。P = 程序将赢得下一场比赛的概率。 Supervised Learning Linear Regression Weights(parameters) θ: parameterizing the space of linear functions mapping from X to Y Intercept term: to simplify notation, introduce the convention of letting x0 = 1 Cost function J(θ): a function that measures, for each value of the θ’s, how close the h(x(i))’s are to the corresponding y(i)’s Purpose: to choose θ so as to minimize J(θ). Implementation: By using a search algorithm that starts with some “initial guess” for θ, and that repeatedly changes θ to make J(θ) smaller, until hopefully we converge to a value of θ that minimizes J(θ). LMS(least mean squares) algorithm: gradient descent learning rate error term batch gradient descent：looks at every example in the entire training set on every step stochastic gradient descent(incremental gradient descent)：repeatedly run through the training set, and each time we encounter a training example, we update the parameters according to the gradient of the error with respect to that single training example only. particularly when the training set is large, stochastic gradient descent is often preferred over batch gradient descent. The normal equations performing the minimization explicitly and without resorting to an iterative algorithm. In this method, we will minimize J by explicitly taking its derivatives with respect to the θj’s, and setting them to zero. To enable us to do this without having to write reams of algebra and pages full of matrices of derivatives, let’s introduce some notation for doing calculus with matrices ...

Scikit-learn 提供一套实用的工具，用于解决机器学习中的实际问题，并配合适当的方法来制定解决方案。 涉及数据和模型简介，决策树，误差的作用，最小化误差，回归拟合，逻辑回归，神经网络，感知器，支持向量机，朴素贝叶斯，降维，K均值，简单高斯混合模型，分层聚类，模型评估。 实验和代码在GitHub; 练习作业答案可以参考GitHub

语言模型 语言模型Language modeling（LM）最初是针对语音识别问题而开发的, 现在广泛用于其他NLP应用中, 比如机器翻译需要利用LM来给翻译出的句子打分. 假设我们有一个语料库 - 某种语言的句子的无限集合$\mathcal{V^+}$（这些句子是由有限的词$\mathcal{V}$组成的）。例如，我们可能从网上获得大量文本。给定了此语料库，我们想估计LM的参数。这些参数包含语料库中所有单词的有限集合$\mathcal{V}$, 以及句子的概率分布函数$p(x_1, x_2, ..., x_n)$，必须满足 For any $\langle x_1...x_n \rangle \in \mathcal{V^+}$, $p(x_1, x_2, ..., x_n) ≥ 0$ $\sum_{\langle x_1...x_n \rangle \in \mathcal{V^+}}p(x_1, x_2, ..., x_n) = 1$ 比如，当$\mathcal{V}$只有cat, eat, fish, 那么它组合成的句子按照人类的评价标准, 通顺程度从高到低是: cat eat fish, fish eat cat, cat fish eat, eat cat fish, eat fish cat, fish cat eat. 这些是可能出现的句子(还没出现的不代表未来不会出现), 从概率分布的角度看待, 这些句子的概率之和是1, 因为这三个词只能组成这几个句子. 而LM的意义就在于能够赋予cat eat fish最大的概率, 代替人来判断句子是否准确, 通俗的说是一个句子通顺打分机器. ...

Bit Map Bit-map用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。 假设我们要对0-7内的5个元素4,7,2,5,3排序（假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes）， 首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0，0 0 0 0 0 0 0 0. 然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置设为1, p+(i/8)|(0x01<<(i%8)), 这里默认为Big-ending, 0 0 0 0 1 0 0 0. 然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态0 0 1 1 1 1 0 1 遍历一遍Bit区域，把1的索引依次输出（2，3，4，5，7），这样就达到了排序的目的。 算法的关键是如何确定十进制的数映射到二进制bit位的map图。算法占用很少内存，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。缺点是不能有重复数据。 Map映射表 假设需要排序或者查找的总数N=10000000，那么我们需要申请内存空间的大小为int a[1 + N/32]，其中：a[0]在内存中占32位, 可以对应十进制数0-31，依次类推： bitmap表为： a[0]--------->0-31 a[1]--------->32-63 a[2]--------->64-95 a[3]--------->96-127 .......... 十进制数需要转换为对应的bit位 位移转换 将十进制数转换为对应的bit位, 申请一个int一维数组，作为32列的二维数组， int a[0] |0000000000000000000000000000000000000| int a[1] |0000000000000000000000000000000000000| ……………… int a[N] |0000000000000000000000000000000000000| 例如十进制0，对应在a[0]第一位： 00000000000000000000000000000001 求十进制0-N对应在数组a的索引：十进制0-31，对应a[0]，先由十进制数n转换为与32的余可转化为对应在数组a中的索引0。比如n=24,那么 n/32=0，则24对应a[0]。又比如n=60, 那么n/32=1，则60对应a[1]。 求0-N对应0-31中的数：十进制0-31就对应0-31，而32-63则对应也是0-31，即给定一个数n可以通过模32求得对应0-31中的数。 利用移位0-31使得对应32bit位为1. 找到对应0-31的数为M, 左移M位：即2 ^ M, 置1. Bloom Filter 为了降低键值冲突的概率，Bloom Filter使用了多个哈希函数：创建一个m位BitSet，先将所有位初始化为0，然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h(i, str)，且h(i, str)的范围是0到m-1 。 ...

避免歧义的编码 在构建压缩编码的对应关系时，我们使用不同的数量的位来编码不同的字符. 比如摩斯密码. 如果单纯使用这种对应关系，会出现一些问题， 如•••−−−•••会产生歧义: SOS? V7? IAMIE? EEWNI? 所以在实际使用中, 密码使用一些间隔来分隔代码字。 那么对于不同的压缩编码, 有什么常用方法来避免歧义？ 方法是确保没有一个编码是另一个编码的前缀。比如 使用固定长度编码。 为每个编码添加特殊的stop char。 使用一种具备广泛使用性的prefix-free编码。 用什么数据结构来设计prefix-free编码? 用Trie构造编码 一个二叉(0, 1)Trie: 叶节点是字符, 根节点到叶节点的路径就是编码. 压缩: 方法1：从叶开始; 按照路径到达根; 反向打印bits。 方法2：创建键-值对的符号表。 解压: 从根节点开始, 根据位值是0还是1在Trie图上游走, 直到走到叶节点，则解压出一个字符 返回根节点, 继续第一步, 直到跑完所有编码. private static class Node implements Comparable<Node> { private final char ch; // used only for leaf nodes private final int freq; // used only for compress private final Node left, right; public Node(char ch, int freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } public boolean isLeaf() { return left == null && right == null; } // compare Nodes by frequency public int compareTo(Node that) { return this.freq - that.freq; } // Runtime - Linear in input size N public void expand() { Node root = readTrie(); // read in encoding trie int N = BinaryStdIn.readInt(); // read in number of chars for (int i = 0; i < N; i++) { Node x = root; while (!x.isLeaf()) { if (!BinaryStdIn.readBoolean()) x = x.left; else x = x.right; } BinaryStdOut.write(x.ch, 8); } BinaryStdOut.close(); } } 如何读取一个Trie：根据Trie的前序遍历序列重构. ...