论文解读：Exploring text datasets by visualizing relevant words
在做机器学习使用新数据集时，我们首先要知道它的特点，一个可以快速可靠地深入了解所选文档的内容，并区分它们类别的工具十分重要。 在这篇论文，作者从文本集合中提取“相关词”，以概括属于某个类别（或在unlabeled数据集下为聚类的组）的文档的内容，并在词云中可视化它们。 作者比较了三种提取相关单词的方法，并使用两个数据集验证了模型的可用性。论文链接：https://arxiv.org/pdf/1707.05261.pdf，论文代码：https://github.com/cod3licious/textcatvis
目标
提供一个文件数据集，输出一组词云，展示最能够区分每个文件类别的词。这里的数据集可以是标注的或是未标注的，对未标注的数据集作者先进行了聚类。
上图是作者论文中的图片，五个词云分别表示最能代表论文五个部分（Abstract, Introduction, Methods, Results, Discussion，即文件类别）的词。
方法
数据预处理和特征提取
首先对所有文件进行1.小写化 2. 删除非字母数字的字符。然后逐段用tfidf转换为bag-of-words（BOW）特征向量\(\mathbf x_k \in \mathbf R^T \forall k \in {1,\dots,N}\)，其中\(k\)是文件编号，\(T\)是该文件包含的词汇数（vocabulary，即去重词数），\(N\)是文件数。表示文件\(k\)的特征向量里对应单词\(t_i\)的值\(\mathbf x_{ki} = tf(t_i) idf(t_i)\)。
TF-IDF
Term Frequency-Inverse Document Frequency，词频-逆文件频率，是一种用于资讯检索与资讯探勘的常用加权技术。TF-IDF是一种统计方法，用以评估一单词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。即一个词语在一篇文件中出现次数越多, 同时在所有文档中出现次数越少, 越能够代表该文件。一般做归一化处理，公式如下：
$$
tf(t_i)=\frac{在某一文件中词t_i出现的次数}{该文件中所有的词数目} \
idf(t_i)=\log(\frac{数据集的文件总数}{包含词t_i的文件数})=\log\frac{|N|}{|{k\in N:t_i\in k}|}
$$
有时为了保证\(idf\)分母不为零，可以在分母上加一。
未标注数据集聚类
对于未标注的数据集，首先要聚类成多个cluster，然后针对每个cluster计算相关单词。作者采用的是DBSCAN（density-based spatial clustering of applications with noise，https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf），首先把tfidf向量用线性PCA降维到250维，然后对特征做交叉，再计算向量间的距离（1 - cosine similarity）。对于聚类时使用的距离门槛（threshold），作者经过实验推荐最低cosine similarity为0.45.
计算相关单词（relevant word）
确定相关单词分为两步，第一步是计算描述相关性的relevance score \(r_c\)，第二步时根据\(r_c\)给所有单词排序，越高代表越相关。为了计算\(r_c\)，作者比较了三种方法：
- 通过汇总组中所有文档的原始tf-idf特征；
- 通过汇总由某些分类器（SVM+LRP）加权的这些特征；
- 分别计算每个单词在该类和其他类出现的文件数量，进而求出\(r_c\)。
突出tfidf特征法（Salient tf-idf features）
最直接简单的方法，对类别\(c\)计算\(r_c\)的公式为：
$$ r_c (t_i) = \sum_{k:y_k=c}\mathbf x_{ki}=\sum_{k:y_k=c}tf_k(t_i)idf_k(t_i) $$
即将所有属于类别\(c\)的文件\(k\)中的单词\(t_i\)的tf-idf值加起来作为这个类别中该单词的relevance score。这样分数最高的单词在该类别的文件中出现频率最高，且不会在大多数其他文件里出现（否则idf值会很低）。然而，一个可能的问题是，高分词在其他类别的文件中出现频率也差不多，这对idf的值影响不大，但意味着在其他类别中该词也会被判定为relevant word，这与relevant word的定义矛盾（最能用来区分不同类别的词）。
SVM+LRP（Decomposed classifier scores）
分为两步，第一步找到一个线性分类器，利用tfidf特征将文件分类。即对类\(c\)，找到\(\mathbf w_c\)，最优化分类器：
$$ \hat y_k = \mathop{\arg \max}_{c} \ b_c + \mathbf w_c^T\mathbf x_k $$
优化好分类器后，计算relevance score：
$$ r_c(t_i) = \sum_{k:y_k=c}\left( \mathbf w_{ci} \mathbf x_{ki} + \frac{b_c}{T}\right) $$
其中\(T\)是词汇数。
在优化分类器时，作者选择了SVM，并提出，也可以用其他的线性分类器比如逻辑回归，甚至DNN。作者强调，只有在分类器精确度相当高的时候，这个方法找出来的相关词汇才有意义，所以分类器的精确度比简便更加重要。
Layerwise relevance propagation（LRP）
是一个计算相关性，并将相关性逐层向后传播的过程。首先将网络模型看成一个拓扑图结构，在计算一个节点 a 和输入的节点之间的相关性时，将 a 点的数值作为相关性，并且计算与 a 点相连的上一层节点在生成 a 点时所占的权重，将 a 的相关性逐层向后传播，直到输入层。作者用下图的例子告诉了我们：
如果要计算 \(v_1\) 和 \(u_1\) 之间的相关性，首先计算 \(v_1\)和 \(z_1\), \(z_2\) 之间的相关性，再将 \(v_1\) 和\(z_1\), \(z_2\) 的相关性传递到 \(u_1\), 从而求得 \(v_1\) 和 \(u_1\) 之间的相关性。
Support vector machine （SVM，支持向量机）
是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；SVM还包括核技巧，这使它成为实质上的非线性分类器。SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。SVM的的学习算法就是求解凸二次规划的最优化算法。
SVM学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。如下图所示，\(\mathbf w \mathbf x + b = 0\)即为分离超平面，对于线性可分的数据集来说，这样的超平面有无穷多个（即感知机），但是几何间隔最大的分离超平面却是唯一的。
SVM有一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。
算法如下：
输入：训练数据集 \(T={(\mathbf x_1,y_1),(\mathbf x_2,y_2),\dots,(\mathbf x_n,y_n)}\)其中，\(\mathbf x_i \in \mathbf R^n, y_i \in {1,-1},i = 1,2,\dots,n\)；
输出：分离超平面和分类决策函数
（1）选择惩罚参数\(C > 0\) ，构造并求解凸二次规划问题
$$
\min_\alpha \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(\mathbf x_i\mathbf x_j) - \sum_{i=1}^N\alpha_i\
s.t.\ \sum_{i=1}^N\alpha_iy_i=0\
0\le \alpha_i\le C, i=1,2,\dots,N
$$
得到最优解\(\mathbf\alpha^=(\alpha_1^,\alpha_2^,\dots,\alpha_N^)^T\)
（2）计算
$$ \mathbf {\omega} ^* = \sum_{i=1}^N\alpha_i^*y_i\mathbf x_i $$
选择\(\mathbf \alpha^\)的一个分量\(\mathbf \alpha_j^\)满足条件\(0<\mathbf \alpha_j^* < C\)，计算
$$ b^* = y_j - \sum_{i=1}^N\alpha_i^*y_i(\mathbf x_i\mathbf x_j) $$
（3）求分离超平面
$$ \mathbf \omega ^* \mathbf x + b^* = 0 $$
分类决策函数：
$$ f(\mathbf x) = sign(\mathbf\omega^\mathbf x +b^) $$
词-文件数量法（Distinctive words）
作者引入了两个概念：TPR（True Positive Rate，真阳性率）和FPR（假阳性率）。定义分别为
$$
TPR_c(t_i) = \frac{类别为c且t_i的tfidf值大于0的文件数}{类别为c的文件数}=\frac {|{k:y_k=c\ \and \ \mathbf x_{ki} > 0}|}{|{k:y_k=c}|}\
FPR_c(t_i) = mean({TPR_l(t_i):l\ne c})+std({TPR_l(t_i):l\ne c})
$$
最终目的是找出在目标类中出现频繁（TPR高），且在非目标类中出现不频繁（FPR低）的词，需要一个度量这一性质的函数。一种直接的方法是直接算差值：
$$ r_c_diff(t_i) = \max {TPR_c(t_i)-FPR_c(t_i),0} $$
这种方法存在一个问题，即只考虑了两个率的绝对差值，未考虑相对差，即如果1. TPR=0.9，FPR=0.8；2. TPR=0.2，FPR=0.1，这种量度会认为他们一样重要，但显然前者对于后者，TPR和FPR相差过近。因此引入基于除法的算法：
$$
r_c_quot(t_i) = \frac{\min{\max{z_c(t_i),1},4} -1}{3} \
where\ z_c(t_i) = \frac{TPR_c(t_i)}{\max{FPR_c(t_i),\epsilon}}, \epsilon是一个极小值，用来避免除数为零
$$
综合二者，得到既考虑相对又考虑绝对差异的度量：
$$ r_c_dist(t_i) = 0.5(r_c_diff(t_i)+r_c_quot(t_i)) $$
rc-TPR-FPR关系图：
结论
作者用scientific publications（标记的，主题、格式分类）和New York Times article（未标记的，寻找热度主题）两个数据集验证了算法的可行性。该方法快速且可靠，更重要的是，即使许多cluster仅包含很少的样本，也有可能可以识别出relevant words，而用分类算法很难达到这个效果。
