工作概述
本次阅读学习了三篇论文，均来自KDD2018，分别是”Discovering Non-Redundant K-means Clusterings in Optimal”,”Learning Adversarial Networks for Semi-Supervised Text Classification via Policy Gradient”和”Model-based Clustering of Short Text Streams”。
在第一篇论文中，作者提出了Nr-Kmeans，作为经典K均值聚类算法的一种扩展，可以在数据集中找到多个无冗余划分，即每一个对象被分配给不同子空间的不同簇。它为每一种划分同时定位最优的，任意方向的，相互正交的子空间。噪声空间的引入令其可以移除不能很好被任意一种划分表征的特征。在论文中，作者将经典K均值聚类的代价函数转换为一个迹最小化问题，再将其转换为特征值分解问题，因为迹等于特征值之和。在特殊情况下,即仅两个子空间的情况下，对矩阵作特征值分解，负的特征值相应的特征向量可将数据投影到第一个子空间，这时对应的迹最小。接着作者将一般情况$S>2$下所有子空间的组合当作特殊情况来处理，因为所有子空间是成对正交的因此对它们做优化不影响其余子空间内的代价函数。
在第二篇论文中，其将半监督学习重新制定为一个基于模型的强化学习问题并提出一种新的对抗学习框架。由于之前的对抗学习框架不能直接扩展到半监督文本分类，因为GAN被设计为产生连续数据，自然不能用于离散数据生成。另外自我训练基于启发式方法，其从自己的高置信预测中获得额外的有标签数据，这样其表现是不稳定的，因为糟糕的预测可能得到加强。作者结合自我训练和对抗网络来克服上述问题。具体说来，基于自我训练建立的模型不需要通过重建输入实例来近似数据分布，另一方面，受对抗网络的启发，一个判断网络被引进自我训练来判断某实例数据的标签是不是真的，因此减少了加强糟糕预测的风险并令自我训练变得更稳定和更鲁棒。
在第三篇论文中，作者第一次提出一种基于迪利克雷过程多项式混合(DPMM)模型的短文本流聚类算法，称为MStream，该算法可以自然得处理概念漂移问题和特征稀疏问题。因为基于DPMM可以直接计算一个文档属于某个现存的簇还是新簇的概率，因此就可以解决概率漂移问题。作者假设每个文档只与一个主题（簇）相关联，而不是假设文档分布在主题上。按照这种方法，MStream算法可以解决短文本的稀疏性问题。另外作者提出簇特征向量，本质是该簇中文档的一个大文档，利用其可加可删除性质，可以高效的更新聚类结果。
另外作者提出改进了的带有遗忘规则的MStreamF算法，该算法直觉地将距离当前批次一定批次间隔的旧批次中的文档从其所属的簇特征向量中删除(得益于簇的表征方式)，可以解决簇数量过多的问题。
Discovering Non-Redundant K-means Clusterings in Optimal
导读
在该论文中，作者提出了Nr-Kmeans，作为经典K均值聚类算法的一种扩张，可以在数据集中找到多个无冗余划分，即每一个对象被分配给不同子空间的不同簇。它为每一种划分同时定位最优的，任意方向的，相互正交的子空间。噪声空间的引入令其可以移除不能很好被任意一种划分表征的特征。在论文中，作者将经典K均值聚类的代价函数转换为一个迹最小化问题，再将其转换为特征值分解问题，因为迹等于特征值之和。在特殊情况下,即仅两个子空间的情况下，对矩阵作特征值分解，负的特征值相应的特征向量可将数据投影到第一个子空间，这时对应的迹最小。接着作者将一般情况$S>2$下所有子空间的组合当作特殊情况来处理，因为所有子空间是成对正交的因此对它们做优化不影响其余子空间内的代价函数。
论文地址。
ABSTRACT
高维空间中的大量对象集合通常可用多种方式聚类，比如，对象可以按照它们的形状或者它们的颜色进行聚类。每一个分组代表数据集的不同视角。无冗余聚类这一新研究领域解决了这类问题。在本文中，作者遵循这样的方法：不同的，非冗余的类K均值类簇可能存在高维空间的不同的、任意方向的子空间中。作者假设这些子空间(另外一个可选的无聚类结构的噪声空间)相互正交(两个子空间正交即两个子空间的任意两个向量正交。ps:我理解是两个子空间不共享原空间的某一维度。)该假设能够对非冗余聚类聚类问题进行特别严格的数学处理，因此是一种特别有效的算法，作者将其称为Nr-Kmeans(For non-redundant k-means)。该算法的优越性通过理论和实验两个部分的阐释。
INTRODUCTION
聚类或者找到大量对象集合的一个自然的分组深深根植于人类认知。我们的大脑一直聚类感官刺激，以识，监控和解释它们。来自认知心理学的实验表明一岁左右的儿童早已能够可靠的发现一系列物体中的类簇。他们解决图1所示的任务并没有困难。给定一些对象的图片————来自ALOI数据集，我们直觉性地将它们聚类，分别按照红色，绿色，圆地和圆柱形的聚类规则。
对于刚会走路的孩子而言，这是一个简单的任务，但它已将最先经的聚类和降维技术推到了它们的极限，出于以下两个原因：（1）图像由包含总计611个特征的高维特征向量所表征。经典的聚类算法，比如K均值由于维度诅咒问题往往会失败。稀疏高维特征空间不包含任何聚类结构。（2）有两种同样有意义的方法可以将图1中的对象分组。在数学上，有两个不同的低维子空间，每个子空间都展现出一种重要的聚类结构。在这些子空间中的类簇是相互无冗余的，也就是，每一个对象属于不同子空间中的不同簇。
受维度诅咒的启发，许多将特征选取和降维整合在一起的精心设计的算法被提出来。这些技术旨在为每一个簇定位一个子空间，在该子空间中，该簇被最好地表征。对每一个簇一个单独的子空间有助于对抗维度诅咒，但令结果解释更困难。没有可以可视化所有簇的公共子空间。因此，很难说哪些聚类是，比如，彼此最相似或者存在异常值，或者存在聚类层次结构。受该缺点的启发，17提出了一种技术，该技术对单个K均值聚类可以找到最好的子空间。其他一些方法聚焦于挑战(2)，也就是定位在不同的子空间中的多个非冗余类簇。允许类簇存在任意子空间中，并且允许对象被赋予给不同子空间中的不同簇，以此来建立一个更大的解决空间。现存的非冗余子空间聚类方法有以下一个到多个的缺点：要求许多输入参数，导致大量的运行时间或者产生大量难以解释的结果。
作者研究发现在不同子空间的多个K均值聚类这一挑战。基本的思想是寻找多个相互正交的子空间，使得经典K均值聚类的目标函数在所有子空间中得到优化。另外，该论文提出的技术引入了一个噪声子空间，该噪声子空间正交于其他子空间，其数据分布被假设为是单峰的。图1展示了Nr-Kmeans的结果。该算法发现相关的子空间和相应的累类簇，和比较方法相比，在一系列任务上表现更佳。该论文的贡献如下：
- 在最优子空间上的多个重要的K均值聚类。Nr-Kmeans在正交子空间上发现多个非冗余的K均值聚类。该方法为每个聚类找到根据k均值的目标函数优化聚类分离的子空间。对每一个聚类子空间，Nr-Kmeans构造最相关的基本向量。子空间之间的正交性保证发现的聚类表示提供相互非冗余信息的数据的不同视图。这些子空间适合可视化和进一步分析，因为它们揭示了一个聚类中簇之间的关系。从K均值聚类继承而来，NR-KMEANS的结果包括可解释的簇中心，正如图1所示。
- 高效。该优化算法，Nr-Kmeans，容易实现，兼容K均值的许多扩展。即使没有其他精心设计的性能优化，该算法也很快速。
- 轻量参数。Nr-Kmeans的输入仅仅是子空间数目，及每个子空间中有多少簇。
- 噪声处理。与现有的非冗余子空间聚类方法相比，Nr-Kmeans模型包括噪声子空间的思想。该噪声子空间捕获数据中所有单峰变量，其对于聚类来说并不重要。此性质有助于Nr-Kmeans优于现有方法，尤其是在高维数据上。
NON-REDUNDANT K-MEANS
在该部分，作者阐述提出的方法Nr-Kmeans。该算法的实现和补充材料可以在这里下载。
作者将他们的算法作为著名的Lloy’d算法的一种简单扩展来描述，具有交替的分配和更新步骤。然而，有可能将Nr-Kmeans和其他提出来的K均值扩展以一种简单的方法进行扩展。
表 1显示了接下来使用的必需的符号和定义。
Cost Function
在K均值算法的经典版本中，我们希望寻找到K个簇$C_i$的集合，使得欧几里得距离平方距离的和最小化。作者在Nr-Kmeans扩展了这一基本思想，通过假设数据集可以被S种不同的方法划分。每一个聚类$j$包含$k_j$个簇并且驻留在一个任意方向的子空间中，该子空间和其余$S-1$个子空间相互正交。
更进一步，作者假设存在一个正交变化矩阵$V$(样本之间的距离不变),该矩阵可以将数据空间旋转到一个所有子空间都是轴平行(axis-parallel)的变换空间中。进一步，作者使用掩子矩阵$P_j$将数据投影到相应的轴平行子空间上。因为这些子空间并不重叠，因此旋转数据空间的每个维度都专门映射到单个子空间。一个数据点$x$可以通过${P_j}^TV^Tx$被投影到$j^th$个子空间。结合这些假设，作者得到下面的损失函数，希望最小化它：
通过优化该目标函数，我们将原来空间中特征的每一线性组合赋给子空间，该子空间通过相应的聚类最佳地表示包含的结构信息。因此，我们对$S$个K均值聚类划分中每一个划分可以找到最佳子空间。
掩子矩阵$P_J \in R^{m_j \times d}$是这样建立的，如果旋转数据空间的$a$维应该被映射到子空间的$b$维，则元素$P_j[a,b]$就被设置为1，其余的元素都被设为0。为了清楚和易于解释，作者假设子空间维度可以不必在旋转空间的特征向量内相邻。然而，如果确实需要，可以使用置换矩阵将子空间在旋转空间中对齐。
作者证明该损失函数和其理论，即他们的算法从理论角度通过与具有统计独立空间的高斯混合模型的关系找到非冗余聚类。标准K均值损失函数是具有概率分布$p(x) = \prod_{i}^k \Pi_iN(\mu_i|\sigma I)$的高斯混合模型的极限。
按照相同的方法，可以很容易地证明Nr-Kmeans的代价函数可以被视为下面具有$S$个独立子空间的高斯混合模型的对数似然函数的极限($w.r.t \sigma \longrightarrow 0$):
该混合模型的统计独立分量在极限时变为Nr-Kmeans模型的正交非冗余子空间。
Optimization Algorithm
作者通过一个Lloyd’s algorithm的修改版本来优化目标函数，如Algorithm 1所示。该算法使用如下描述的更新和分配步骤直到收敛。
第一步，先使用随机正交矩阵初始化$V$。接着，初始化每一个子空间的维度$m_j$，其中$m_1 + … + m_S = d$。为了简化，作者将维度在所有子空间上平均分配。每一个子空间维度的最优值，在接下来的优化过程得到。最后但并非最不重要的，簇中心的初始化可以使用随机或者使用k-mean++设置。
分配步骤几乎和经典K均值聚类算发一样。我们将参数$V,m_j,u_{j,i}$固定住，将每一个数据点分配给相应子空间中的簇均值与该数据点的平方距离最小的簇：${|{P_j}^TV^Tx-{P_j}^TV^Tu_i|}^2$。
对于更新步骤，我们将数据点分配固定住，并且决定最优的参数值。接下的部分讨论需要的优化步骤的细节和每一步的正确性。
Estimation of the cluster centers$u_{j,i}$。 我们可以通过设置相对于$u_{j,i}$的偏导数等于零来确定聚类中心的估计量（不太懂）。这一计算结果显示了人们的直觉期望：在该子空间中的聚类均值${P_j}^TV^Tu_{j,i}$只是在原始空间中分配给该簇的所有数据点的变换平均值。它可以通过下面这个著名公式来计算：$\frac{1}{|C_{j,i}|} \sum_{x \in C_{j,i}} x$。
Estimation of $V$ in the case of subspaces $S$ = 2。接下来，我们需要估计$V$的最优值。在展示一般情况下$V$的优化策略之前，我们先考虑只有两个子空间$S = 2$的特殊情况。这些结果接下来将帮助我们优化一般情况：$S > 2$。
让我们假设现在$m_i和m_2$都是固定的，是随机的正整数，并且$d = m_i + m_2$。接下来，我们假设投影矩阵$P_1$将数据向量最前面的$m$个特征投影到第一个子空间，投影矩阵$P_2$将随后的$m_2$特征投影到第二个子空间：
对该特殊情况，损失函数如下：
我们可以将该损失函数转换为一个迹最小化的问题，通过利用一个$1 \times 1-matrix$的标量和$Tr(P_2 {P_2}^TA) = Tr(A)-Tr(P_1 {P_1}^TA)$,其中$A \in R^{d \times d}$这一事实。
转换后的目标函数如下：
其中$\Sigma_{j}$是子空间$j$所有簇的分散矩阵的和：
在公式(3)中第二项对于任意$V$来说是个常数，因为迹函数的循环性质，还因为$V$是正交矩阵，因此$Tr(V^T\Sigma_2V) = Tr(\Sigma_2)$。
接下来，我们应该注意到$P_1{P_1}^T$是对角矩阵，其前$m_1$个对角元素是1，随后的$m_2$个对角元素是0。因此，如果我们将其与$V^T[\Sigma_1-\Sigma_2]V$右乘，它让$V^T[\Sigma_1-\Sigma_2]V$左上角的$m_1 \times m_1$个元素不变，让其他所有元素都为零。进一步，我们注意到迹函数产生了特征值之和(特征值之和等于迹，所以最小化特征值和也就最小化迹)。因此，对于固定但是任意的$m_1,m_2$,有可能最小化公式(2)的函数，通过放置$[\Sigma_1-\Sigma_2]$的特征向量到$V$的列，令对应最小的$m_1$个特征值的$m_1$个特征向量将数据投影到第一个$m_1$维的子空间，余下的$m_2$个特征向量将数据投影到第二个子空间。因此，我们使用$[\Sigma_1-\Sigma_2]$的特征值分解和作为$V$列向量的特征向量————对应于按升序排列的特征值。我们应该注意到$[\Sigma_1-\Sigma_2]$是对称，因此是可以正交对角化的，并且它的所有特征值都是实数。
因为我们将$V$中的向量对应于按升序排列的特征值排序并且公式(3)中的常数项并不依赖于$m_1$和$m_2$,$V$的最佳值独立于每一个子空间的维度。这一性质给了我们在每一更新步骤中额外的能力去优化关于$m_1$和$m_2$的代价。公式(2)中的代价函数仅仅通过投影矩阵$P_1,P_2$依赖于$m_1,m_2$。因为迹是特征值的和并且我们希望最小化这个和，所以我们可以仅仅最小化这个和，如果我们将$[\Sigma_1-\Sigma_2]$的所有负特征值求和。因此，我们将和负特征值对应的特征向量分配给第一个子空间，将大于零的特征值对应的特征向量分配给第二个子空间。如果特征值是零，其对代价函数无关紧要，我们可以这些特征放到任意一个子空间。
因此，对于给定$V$，我们可以优化代价函数，通过设置$m_1$为$[\Sigma_1-\Sigma_2]$负特征值的个数，$m_2 = d-m_1$。
我们应该注意到$[\Sigma_1-\Sigma_2]$的特征值也显示了其相应的特征向量和结果特征对于聚类结构的重要性。但我们将$m_1$设置为1的时候很容易看出来，我们只能使用对应于最小的特征值的特征向量将数据投影到第一个子空间的向量来最小化代价函数。因此，该特征向量对于该聚类来说是最重要的，对于$m_1 = 2$，我们同样需要和最小的两个特征值对应的特征向量来投影数据。对于第二个聚类和最大的特征值来说，该结论同样成立。因此，将$V$的列向量对应于升序的特征值来排列，意味着我们按照这些特征向量的重要性排列它们，对第一个子空间来说是降序，对第二个子空间来说是升序。
Estimation of $V$ and $m_j$ in the general case S > 2 。在一般情况$S>2$优化$V$的问题并不像特殊情况$S=2$时拥有闭式解。这就是为什么我们不能通过单一特征值分解步骤来直接优化$V$的值。但是，我们可以使用这一事实，即所有子空间都是彼此成对正交的并且旋转这两个子空间的组合空间并不影响其余子空间内的代价。因此，在一般情况下优化的技巧就是考虑将旋转空间内的两个聚类的所有组合当作特殊情况$S=2$来按上小节方法来处理。一个解释的例子如图2所示。
让我们假设我们早已更新了所有的$\mu_{j,i}$，但是现在关于早已固定的参数的$V$和$m_j$还没有达到最优。我们考虑两个聚类$s$和$t$及它们对应的在旋转空间中的两个子空间$S_s$（对应图2红色块）和$S_t$(对应图2蓝色块)。我们可以使用投影矩阵$P_{s,t} = [P_s, P_t]$将整个数据集投影到组合空间$S_{s,t}$，该投影矩阵将组合空间$S_{s,t}$的前$m_s$个维度投影到$S_s$子空间，将后面的$m_t$个维度投影到$S_t$子空间。这时我们就可以将聚类$s$和$t$及它们的组合空间$S_{s,t}$当作特殊情况$S = 2$来处理，初始化这个子空间的旋转矩阵${V_{s,t}}^{< c >} = I_{m_s+m_t}$。但是，我们假设这个旋转矩阵关于公式(2)的代价函数来说不是最优的并且对于$s$和$t$的最优子空间也许是任意方向的(在图2中最优子空间$S_s$和$S_t$分别对应黄色和紫色)。但上一节讨论的结果，让我们能够找到旋转矩阵${V_{s,t}}^{< c >}$更好的值并且让我们能够调整两个子空间的维度以使代价函数最小化。接下来，我们描述子空间$S_{s,t}$中的旋转矩阵${V_{s,t}}^{< c >}$在满空间中对应的旋转矩阵${V_{s,t}}^{< f >}$:
这个满空间中的转换矩阵可以使用$V \gets V \times{V_{s,t}}^{< c >}$来更新。另外我们也需要更新$P_s,P_t$，因为$m_s,m_t$可能发生变化并且旋转空间的一些维度可能分配给其他子空间了。我们应该记住，我们希望根据它们对聚类的重要性来排序每个子空间中的特征。对每对子空间执行此过程，我们优化变换矩阵$V$和关于每个子空间的维度$m_j$ ，因此进一步最小化我们的一般代价函数。
Accelerating the general case $S>2$。上面描述的程序有一个缺点，他将整个数据集都投影到每一个组合子空间。对于大数据集来说，这样代价很大。
但我们可以规避这个问题，因为我们只需要计算每一聚类$j$在组合子空间内的分散矩阵${\Sigma_j}^{< c >}$的和。这些矩阵可以通过$V$和$P_{s,t}$在原始空间中计算的分散矩阵${\Sigma_j}^{< f >}$的和得到。我们可以轻易的预计算原始空间中的${\Sigma_j}^{< f >}$并且对于每一个组合子空间将它们转换为${\Sigma_j}^{< c >}$。因此，${V_{s,t}}^{< c >}，m_s,m_t$可以由$eig({P_{s,t}}^TV^T|{\Sigma_s}^{< f >}-{\Sigma_t}^{< f >}|VP_{s,t})$轻易决定。
Noise-Space as a Special Subspace
作者观察到聚类结果可以通过增加一个额外的包含单一簇的子空间来得到改善。作者将该子空间称为噪声空间，其余子空间为结果聚类空间。和该噪声空间有关的特征并不建立在其他聚类空间中的任何簇的结构并且在该子空间内的所有数据点的值来自相同的单峰分布或者均匀分布。因此，根据k均值聚类假设，我们通过单个聚类描述该空间。
CONCLUSION
在该论文中，作者提出了Nr-Kmeans，作为经典K均值聚类算法的一种扩张，可以在数据集中找到多个无冗余划分。它为每一种划分同时定位最优的，任意方向的，相互垂直的子空间。噪声空间的引入令其可以移除不能很好被任意一种划分表征的特征。这可以解释为数据降维步骤。Nr-Kmeans具有许多理想的特性。 最基本的非优化版本易于实现，仅使用所有线性代数框架提供的标准功能。即使在最基本的实现中，它也非常快。
此外，Nr-Kmeans可以简单的与经典k-means的许多其他扩展相结合。
方式。
未来的努力可以针对其中的子空间和簇的数量的全自动选择过程。 其他研究方向可能在于近似扩展的发展。
REFERENCES
17 Dominik Mautz, Wei Ye, Claudia Plant, and Christian Böhm. 2017. Towards
an Optimal Subspace for K-Means. In Proceedings of the 23rd ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining, Halifax, NS,
Canada, August 13 - 17, 2017. 365–373. https://doi.org/10.1145/3097983.3097989
Learning Adversarial Networks for Semi-Supervised Text Classification via Policy Gradient
导读
本论文将半监督学习重新制定为一个基于模型的强化学习问题并提出一种新的对抗学习框架。由于之前的对抗学习框架不能直接扩展到半监督文本分类，因为GAN被设计为产生连续数据，自然不能用于离散数据生成。另外自我训练基于启发式方法，其从自己的高置信预测中获得额外的有标签数据，这样其表现是不稳定的，因为糟糕的预测可能得到加强。作者结合自我训练和对抗网络来克服上述问题。具体说来，基于自我训练建立的模型不需要通过重建输入实例来近似数据分布，另一方面，受对抗网络的启发，一个判断网络被引进自我训练来判断某实例数据的标签是不是真的，因此减少了加强糟糕预测的风险并令自我训练变得更稳定和更鲁棒。
论文地址。
ABSTRACT
半监督学习是机器学习技术的分支，其目标是充分利用有标签和无标签数据来改善预测性能。现代真实世界的数据集以前所未有的速度扩大，令为它们建立标签很困难和成本巨大。因此，深度半监督学习变得越来越流行。许多现在的深度半监督方法建立在基于生成模型的方案上，该方案通过重建输入数据近似输入数据的分布。但这种方案对离散数据不起作用，比如文本。另外，学习一个好的数据表征有时会直接和学习一个优秀的预测模型的目标对立。为了解决这些方法的上述问题，作者将半监督学习重新制定为一种基于模型的强化学习问题，并提出一种基于对抗网络的框架。该框架包括两个网络：一个用于目标估计的预测网络和一个用于评估的判断网络（judge network）。判断网络迭代地生成合适的奖励，来指引预测网络的训练，并且预测网络通过策略梯度(policy gradient)训练。基于刚刚提及的框架，作者提出了一个基于循环神经网络的模型用于半监督文本分类。作者在几个真实世界的基准文本数据集上进行了全面的实验分析，评估结果显示了其方法优于其他竞争的最先进的方法。
INTRODUCTION
在许多真实世界应用中，为一个学习问题标注数据常常需要来自经过训练的专家的大量努力。因此，获取大量的标注数据是非常昂贵甚至是不可能的。但是，获取大量未标注数据相对简单和低廉。半监督学习是机器学习方法的一个分支，其旨在利用少量标记数据来利用剩余的未标记数据，以提高预测模型的准确性。
深度学习最新的进展提供了新的精心设计的范例从复杂数据中获得端到端学习的模型。在深度学习背景下，大多数半监督学习算法都基于生成模型方案。在该方法下，深度生成模型作为数据分布的估计器，并且将学得的数据分布作为辅助信息来增强分类模型的学习过程。Goodfellow et al.提出生成对抗网络框架，其中两个网络被训练来相互对抗。这种对抗学习框架在计算视觉任务上取得了很大的成功，并被成功的扩展到半监督图像分类。但是这种框架不能被直接扩展到半监督文本分类，因为GAN被设计用于生成连续数据，这自然不会对离散数据生成起作用。
为了克服GAN自然的限制并且在半监督文本分类中利用对抗训练框架的优点，作者提出了一种基于判别对抗网路(discriminative adversarial networks,DAN)的模型，该模型深植于自我训练(Self-training)。自我训练对于半监督学习来说是最直接的方案。它基于一种启发式方法建立，在这种方法中，模型使用从其高置信预测中获得的额外的标注数据训练。因此，该方法的表现不稳定，因为糟糕预测可能被加强。在本论文中，作者将自我训练和对抗学习网络的思想结合起来克服它们的问题。具体来说，基于自我训练建立的模型不需要通过重建输入实例来近似数据分布，因此就克服了基于GAN的半监督学习方法的限制，另一方面，受对抗网络的启发，一个判断网络被引进自我训练来判断某实例数据的标签是不是真的，因此减少了加强糟糕预测的风险并令自我训练变得更稳定和更鲁棒。
将上述两个学习框架联合起来并结合它们的优点，在该论文中，作者提出RLANS框架，即Reinforcement Learning based Adversarial Network for Semi-supervised learning。该框架将半监督学习的预测网络 P 重新制定为一个强化学习代理(agent)，其中状态是输入数据，动作是标签预测。因此，学习问题的首要目标被转换为 P 学习一个好的策略的问题，使得生成的预测标签可以最大化期望的总奖励。预测网络 P 通过策略梯度(policy gradient)学得。判断网络 J 用来评估预测的标签和提供评估的反馈来引导预测器的学习。采用 J 的反馈作为奖励可以迭代地改进预测网络 P ，因为奖励是动态更新的。具体来说，令$D_L =
\{(x_1,y_1),…,(x_l,x_l)|x_i \in \mathcal{X},y_i \in \mathcal{Y}\}$是一组$l$个标注实例，令$D_
U = \{x_{l+1},…x_{l+u}|x_i \in \mathcal{X}\}$是一组$u$个未标注的实例。该论文提出的模型总体结构如Figure 1所示。
强化学习是不稳定的甚至是发散的，当行动值函数(action-value function)是由非线性函数表征时。在模型实现中，为了缓解不稳定性，预测器 P 在$D_L$上使用最大似然估计预训练几个迭代，并且当预测器预训练结束时，判断器 J 也要预训练几次迭代。
论文主要的贡献总结如下:
- 受自我训练的启发，为了同时考虑有标签和无标签实例，作者将半监督学习问题重新制定为基于模型的强化学习问题。
- 作者为半监督学习提出一种基于对抗网络的框架。不像大多数其他基于GAN的半监督学习方法，该框架不需要重建输入数据，因此可以应用于半监督文本分类。
- 基于提出的RLANS框架，作者为半监督文本分类提出一种具体模型，另外，在几种基准数据集上进行了全面的实验分析。
RELATED WORK
半监督学习可以朔源到1970s，并且从1990s起，它引起了极大的关注。现在的半监督学习方法可以大概的归为如下几类：self-training，transductive leaning based，co-training，graph-based，和generative model based。在本部分，我们先简短的描述以上每个类别最重要的工作，然后重点讲述这些方法和作者提出的方法的关系和主要区别。
在前面提及的所有半监督学习方案中，最直截了当的方法是自我训练方案，其中预测模型使用标签数据和最置信的预测迭代的重新训练。转换支持向量机TSVM是用于半监督学习著名的转换方法。它将支持向量机作扩展，旨在找到处在低密度区域的判别决策边界，因此使其到原始标签数据和无标签数据都为最大间隔。共同训练是多视图学习的一个特殊例子，其假设数据拥有两个视图并且每个视图都能够训练一个好的预测器。最初，对每一种视图，一个独立的分类器使用标注数据训练。接着每一个训练器对未标注数据的最置信的预测联合标注数据迭代的重新训练其他的分类器。基于图的半监督方法为标注实例和未标注实例构建一个相似图，并且相似的实例别假设为同一类。其他方法比如Gaussian fields和隐马尔可夫随机域被引入基于图的半监督学习在图内建模标签传播。
基于生成模型的半监督学习方案可以被看作是联合数据分布辅助信息的监督学习的扩展，数据分布通过重建输入数据学得。在之前的十年，一些传统生成混合模型被用于半监督学习。随着深度学习方法的发展，深度神经网络被用作密度估计器(ps:概率密度)并且比传统生成模型更有弹性和更强大。深度生成模型比如VAE和GAN在近些年取得令人印象深刻的成功。在这类基于重建的半监督学习方法中，生成器被训练学习能够保留输入样本所有信息的表征，以此实现完美重建数据。生成器常被用来预训练分类网络。但是，分类器的学习是一个最小化对标签预测有价值的信息的过程，这就成为了完美数据重建的对立面（ps：最小化有价值的信息，是指其是一种消耗品吗？），因此有时学得的表征甚至可能损害预测模型的性能。
基于重建的半监督学习方案，在8用于半监督学习的两阶段方法被提出来。首先，在预训练阶段，一个传统的无监督语言模型2被构建用来学习序列的向量表征，该模型预测在序列中下一个是什么。其次，从预训练阶段获得模型参数，作为在文本分类中有监督训练模型的出发点。基于这种方案，在工作20中，作者引入对抗扰动增强了第二阶段。在这些论文中，无标签数据并未直接用于第二阶段训练分类器。最近28，基于DAN的方法被提出来用于半监督学习。但是，标注数据仅用来训练判断网络，并不用于训练预测网络。
在该论文中，不同于上述所有的深度半监督学习模型，作者们将半监督学习重新制定为基于模型的强化学习问题，并且提出一种基于对抗网络的框架来改进训练过程。该论文提出的RLANS与上述深度半监督学习方法的主要不同总结如下：
- 不同于深度生成半监督学习模型，RLANS框架不需要执行实例重建来近似数据分布。因此，该框架可以轻松的用在半监督文本分类。
- 不同于现有的深度半监督文本分类算法，RLANS框架采用了强化学习和对抗网络的优点。因此，可以迭代更新，并且标注数据和未标注数据可以直接用于训练分类器。
METHODS
在该部分，我们详细介绍为半监督学习提出的对抗学习框架。我们先描述RLANS框架的总体架构，接着描述为半监督文本分类提出来的一种具体的模型。
Model Overview
半监督学习的首要目标是从标注数据$D_L$和未标注数据$D_U$中学习一个参数为$\theta$的预测模型$P_\theta$，使得预测标签尽可能接近真实标签。因为未标注实例的标注信息是未知的，基于常用的最大似然估计来训练预测器$P_\theta$并不是一种直截了当的方法。取而代之，在本论文中，作者将半监督学习重新制定为强化学习问题。
训练预测模型$P_\theta$。作者基于强化学习解释预测问题，其中输入数据$x$可以被视为是状态，并且相应的预测标签$\hat{y}$被看作动作。预测器$P_\theta(\hat{y}|x)$可以被视为策略模型，给定状态$x$,决定行动$\hat{y}$的概率。该策略模型的目标是生成合适的预测标签以最大化期望奖励：
其中$\mathcal{Y}$是可行动作空间，$V(\cdot)$是选择$\hat{y}$作为行动的行动值函数。在半监督学习中，给定输入数据，一个好的预测器应该生成尽可能接近真实标签的预测标签。因此，行动值函数在该问题中被定义为预测标签$\hat{y}$和真实标签$y$的相似度。
现在关键的问题就是如何为$\hat{y}$和$y$定义一个合适的相似度函数，特别是未标注实例的真实标签是未知的。为了解决这个问题，受对抗学习框架GAN的启发，作者训练一个判别模型$J_\phi$作评判，为改进预测器$P_\theta$提供引导。$J_\phi(x,\hat{y})$是指示$(x,\hat{y})$被认为是真实数据-标签对的概率。因此，在RLANS中，行动值函数可以被定义如下：
在行动值函数中使用$J_\phi(x,\hat{y})$的主要优点是$J_\phi$是动态更新的，因此它可以迭代地改进预测器$P_\theta$。值得注意，上面定义的行动值函数在每次迭代中提供即时的奖励，因此并不需要使用额外的技术，比如蒙特卡洛树搜索，Temporal-Difference (TD) learning 来近似长期奖励。
最大化公式(1)中的目标需要计算关于模型参数$\theta$的梯度：
使用似然比技巧公式(3)可以被重写为：
公式(4)是公式(3)的无偏估计。在实际中，作者使用m个标注实例和m个未标注实例作为一个小批量来训练模型，近似梯度可以计算如下：
接下来预测模型的参数$\theta$可以按照如下更新：
训练判断模型$J_\phi$。在该框架中，$J_\phi$是这样训练的，将一组真实标注实例$\{(x_i,y_i) \in D_L \}$作为正样本，一组未标注数据和相应的预测标签$\{(x_i,\hat{y}_i) |x_i \in D_U,\hat{y}_i \in P_\theta(x_i)\}$作为负样本。判断模型$J_\phi$应该尽可能清楚的判别正样本和负样本。因此，判断模型的训练需要最小化交叉熵：
Algorithm 1总结了RLANS总体的训练过程。在对抗学习前，在第一行预测器使用最大似然估计在标注数据$D_L$上先预训练。在第三行判读模型$J_\phi$通过最小化交叉熵在真实标注实例和假的和预测标注数据上预训练。在每次对抗训练循环中，预测器$P_\theta$为m个未标注数据预测标签。判断模型$J_\phi$使用真实数据-标签对和预测数据-标签对进行训练。每次新的判断模型获得时，就按照公式(5)计算更新行动值函数，然后通过策略梯度更新预测器。
RLANS For Semi-supervised Text Classification
基于上述提及的RLANS框架，作者提出为半监督文本分类提出了一个具体的模型。
用于文本的预测器网络。在该论文中，作者使用基于标准LSTM网络的模型作为预测器，如图Figure 2所示：
令一个实例$x = \{w^{(1)},\cdot \cdot \cdot,w^{(T)}|w^{(t)} \in {\{0,1\}}^k\}$是T个单词的独热编码序列，其对应的目标$\mathcal{y} \in {\{0,1\}}^c$是c个类标签的独热编码，其中k是单词表中不同的单词的数目。一个嵌入矩阵$E \in R^{(k+1)\times p}$用来将原始的独热编码表征为相应的p维连续向量$\{v^{(1)},\cdot \cdot \cdot,v^{(T)}\}$，其中词向量的第k+1维被用作指示序列结束标志$V_{eos}$。给定输入单词$w^{(t)}$，在第$t-1$步，长期单元状态$c^{(t-1)} \in R^{1 \times q}$，隐藏状态$h^{(t-1)} \in R^{1 \times q}$，在第$t$步，$c^{(t)}，h^{(t)}$被计算。在最后一步，给定最后隐藏状态$h_{eos}$，该模型先通过带有Relu的全连接网络计算隐藏向量$h_c \in R^{1 \times d}$，然后使用softmax output layer计算相应的估计标签的分布：
用于文本的判断网络。在该论文中，作者使用基于LSTM的模型作为其判断网络，如Figure 3所示：
在第t步，一个目前估计的标签向量$o(t) \in R^{1 \times c}$通过一个子网络生成，该子网络的结构和之前的预测网络的输出部分是一样的。接着将$o^{( t )}$，独热编码目标向量$y$（或者未标注数据的估计目标向量$\hat{y}$）拼接起来。一旦所有拼接向量都生成了，一个权重联合如下：
该值作为判断模型输出部分的输入，其中$\beta \in R^T$是可训练的权重向量。
判断模型的目标是估计$(y;w^{(1)},\cdot \cdot \cdot,w^{(T)})$来自标注数据$D_L$可能性的概率，其在${[o,y]}_\beta$是两个成分的联合概率。一个单层的神经网络单独的处理所有输入特征，因此不能进行特征提取。因此，设计的输出网络应该具有多层。在作者的模型中，输出网络具有两层，分别如下是：
CONCLUSION
在该论文中，作者将半监督学习重新制定为基于模型的强化学习问题，并且提出一种新的对抗学习框架RLANS。该框架包含两个网络：一个预测网络和一个判断网络。判断网络用来动态地评估预测网络的表现并提供反馈作为奖励动态地引导预测器地学习过程。RLANS框架并不要求数据生成，因此可以轻易的用于离散数据。基于该框架，作者提出一种用于半监督文本分类的具体模型。作者广泛地比较了所提算法的性能与一些最先进的深度半监督文本分类算法的性能，在几个基准文本数据集上。
将来，基于提出的框架，作者计划为不同类型的数据精心设计更具体的预测和判断网络。然后，作者计划基于强化学习方案开发更先进的深度半监督学习方法。作者还计划进行一些相应的理论分析，以进一步提高拟议框架的稳定性。
REFERENCES
2 oshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Jauvin. 2003. A neural probabilistic language model. Journal of machine
learning research 3, Feb (2003), 1137–1155.
8 Andrew M Dai and Quoc V Le. 2015. Semi-supervised sequence learning. In Advances in Neural Information Processing Systems. 3079–3087.
[20] Takeru Miyato, Andrew M Dai, and Ian Goodfellow. 2016. Adversarial Training Methods for Semi-Supervised Text Classification. arXiv
preprint arXiv:1605.07725 (2016).
[28] Cicero Nogueira dos Santos, Kahini Wadhawan, and Bowen Zhou. 2017. Learning Loss Functions for Semi-supervised Learning via Discriminative Adversarial Networks. arXiv preprint arXiv:1707.02198
(2017).
Model-based Clustering of Short Text Streams
导读
在本论文中，作者第一次提出一种基于迪利克雷过程多项式混合(DPMM)模型的短文本流聚类算法，称为MStream，该算法可以自然得处理概念漂移问题和特征稀疏问题。因为基于DPMM可以直接计算一个文档属于某个现存的簇还是新簇的概率，因此就可以解决概率漂移问题。作者假设每个文档只与一个主题（簇）相关联，而不是假设文档分布在主题上。按照这种方法，MStream算法可以解决短文本的稀疏性问题。另外作者提出簇特征向量，本质是该簇中文档的一个大文档，利用其可加可删除性质，可以高效的更新聚类结果。
另外作者提出改进了的带有遗忘规则的MStreamF算法，该算法直觉地将距离当前批次一定批次间隔的旧批次中的文档从其所属的簇特征向量中删除(得益于簇的表征方式)，可以解决簇数量过多的问题。
论文地址。
ABSTRACT
短文本流聚类由于多种社交媒体中短文本的爆炸增长，已经成为一个日益重要的问题。在该论文中，作者提出一种基于模型的短文本聚类算法(MStream)，该算法可以自然得处理概念漂移问题和特征稀疏问题。(MStream)算法只需对流一次通过(one pass of the stream)即可实现最先进的性能，并且当允许每批次多次迭代时，可以获得更好的性能。作者们进一步提出具有遗忘规则的(MStream)的改进算法(MStreamF)，该算法能够通过高效地删除过时批次的簇，来删除过时的文档。作者们的扩展实验显示上述两种算法可以在一些真实数据集上取得比三种基准更好的表现。
INTRODUCTION
短文本流聚类比如网上流行的微博帖子经常围绕真实生活事件或者故事形成簇。聚类短文本流的任务是在文档按时间顺序到达时将文档分组到各个簇，该任务有许多应用，比如搜索结果多样化，事件检测和追踪，文本摘要。短文本流聚类问题面对如下两个挑战：（1）短文本的稀疏性（特征稀疏）。（2）文本连续到达，导致存储所有文档和像静态文本聚类方法那样迭代多次处理文档是不可能的。（3）文本流的主题可能随着时间连续改变，因此我们需要自动地检测新的簇并且移除过时的簇。
通常，短文本流聚类问题有两种方案：一次通过方案和批量方案。一次通过方案假设流文档一个接一个地到来，我们只能对每一个文档进行一次处理。批量方案假设流文档是批量到来的，我们可以对一个批次中的文档多次处理。在真实应用中，批量方案可能更加合理，因为我们能够对一个文档批次进行预处理然后将它们发送流聚类算法。在批量方案中，我们可以多次迭代现在批次中的文档，并当新的批次到达时就丢弃它们。当我们允许每一批次多次迭代时，流聚类算法的表现就得到明显的改善。
在本论文中，作者们提出两种基于模型的短文本流聚类算法，其在上述两种方案中都表现的很好。作者第一次提出基于Dirichlet process multinational mixture（DPMM）model的短文本流聚类算法，取名为(MStream)。该算法具有一次通过聚类处理和在每一批次更新聚类的处理。作者假设每个文档只与一个主题（簇）相关联，而不是假设文档分布在主题上。按照这种方法，MStream算法可以解决短文本的稀疏性问题。更进一步，该算法决定将一个文档赋予新的簇时并需要一个相似度阈值，因为我们可以计算一个文档选择一个新簇的概率，该概率可直接从DPMM modle得到，因此MStream可以自然地处理概念漂移问题。
随着更过文档到来，簇数量逐渐增加，MStream算法的空间和时间复杂度会增长到很大的地步，如果我们不将过时的簇删除的话。另外，和整个数据流相比，我们常常对一段特定时期的信息感兴趣。然而，检测和删除过时的簇常常是困难和低效的，因为我们在内存中不能存储所有簇的文档。作者提出MStream算法的改进算法MStreamF，其具有遗忘规则，可以通过删除过时批次的簇来删除过时的文档。在MStreamF算法中，作者依然只存储当前批次的文档，同时存储几个批次的簇。因为一个批次的簇包含用于删除该批次中文档的所有必需信息，并且记住一个批次的簇不需要太多内存。当一个批次的文档过时，我们可以使用减法操作高效地从现在的簇特征向量中直接删除这些文档。MStreamF算法能够在硬盘上存储每一个批次地簇，作为文本流的离线分析。
该论文的贡献可以总结如下。
- 作者提出一种基于模型的短文本聚类算法（MStream），其可以自然地处理概念漂移问题。MStream在一次通过方案下可以达到当前最佳表现，如果对每一批次允许迭代多次处理，其表现会更好。
- 作者提出MStream的带有遗忘规则的改进算法MStreamF，其可以高效地通过删除过时批次地簇来删除过时的文档。
- 作者在几个真实数据集上进行了扩展实验，证明了其方法的高效性和有效性。源代码和数据集传送门在此。
RELATED WORK
文本流聚类方法可以被归类为如下两种：基于相似度的流聚类和基于模型的流聚类。
Similarity-based Stream Clustering
基于相似度的文本流聚类方法大多数使用向量空间模型来表征文档并且需要选择一个相似度度量比如余弦相似度来衡量文档或者簇之间的相似度。
CluStream是最经典的流聚类方法之一，其由一个在线微聚类成分和一个离线宏聚类成分组成。CluStream使用金字塔时间框架存储不同时刻的历史的微簇，以供后面分析。DenStream联合微聚类和一个密度估计过程来进行流聚类，其可以形成任何形状的数据簇并且处理异常点。Yoo et.al.提出一种流光谱聚类方法，其可以随着时间维持数据流的规范拉普拉斯的近似并且可以高效地更新流时尚的拉普拉斯的变化的特征向量。
Zhong et.al.提出一种高效的流文本聚类算法，其基于著名的赢者通吃竞争学习在线更新簇质心。(后面还有几种，我认为没必要写了，短短几句我也搞不懂究竟是怎么一回事)
基于相似度的文本聚类方法的一个限制是它们需要选择一个相似度阈值来手动的决定是将一个文档赋予新的簇还是不。作者提出的MStream算法计算一个文档属于现有簇的或者新簇的概率，并且根据这些概率来决定文档的归属。通过这种方式，MStream可以更自然的检测新的簇并且能够处理概漂移问题。
Model-based Stream Clustering
基于模型的文本流聚类方法假设文档是由一个混合模型产生的，然后使用像Gibbs Sampling和Sequential Monte Carlo等技术来估计混合模型的参数，这样就可以获得聚类结果。
许多模型扩展Latent Dirichlet Allocation（LDA），来建模文本流，比如动态主题模型（DTM），主题随着时间推移模型（TOT），动态混合模型（DMM），主题追踪模型（TTM），temporal-LDA(TM-LDA)，streaming LDA(ST-LDA)和Dirichlet-Hawkes topic model。这些方法假设文档内容足够丰富，可以推断出每个主题的每个文档的多项分布。该假设对短文本并不成立，导致这些方法在短文本流上不能取得很好的表现。Liang et.al。提出动态聚类主题模型（DCT），其基于迪利克雷多项混合分布模型。DCT通过将单个主题赋予每个短文本并且使用在特定时间推断的分布作为下一批推断的先验可以处理短文本流。
上述的大部分方法假设簇的数量是一个固定的数，这意味着它们不能高效处理文本流聚类中的概念漂移问题。Ahmed and Xing提出temporal Dirichlet process mixture model (TDPM)可以自动的在数据上增长簇的数量。然而TDPM是离线框架，需要整个文本流的序列。该论文提出的文本聚类方法可以在一次通过和批量方案下工作的很好。另外该方法可以处理短文本的挑战和概念漂移问题。
BACKGROUND
这一部分，作者简短的介绍了迪利克雷过程（一种随机过程），和迪利克雷过程多项式混合(DPMM)模型。
可以参考这两篇博客Dirichlet Process and Stick-Breaking和DPMM的理解、公式推导及抽样。
APPROACH
在这部分，作者先介绍其方法中文本和簇的表征，然后介绍提出的MStream算法和MStreamF算法。
Representation
作者使用一个文档中的单词和其在文档中相应的频率来表征一份文档。基于向量空间模型的方法假设文档是由高斯分布产生的，而本论文作者假设文档是由多项式分布产生的。
基于相似度的聚类方法比如K均值，使用一个簇的所有文档向量的均值来表征一个向量。相反，本论文作者使用簇特征（CF）向量来表征一个簇，这本质上是一个结合其文档的大文件。一个簇的CF特征向量定义如下。
簇特征向量提供重要的可加可删除性质，如下所示。
这里，${N_d}^w$和$N_d$分别是在文档 d 中单词 w 出现的次数和在文档 d 中总的单词数，并且$N_d = \sum_{w \in d} {N_d}^w$。另外${N_z}^w$是簇 z 中单词 w 出现的频率。将一个文档添加到一个簇和将一个文档从簇中删除的复杂度均为$O(\overline{L})$,其中$\overline{L}$是文档的平均长度，通常少于100。在本论文提出的算法中，簇特征向量的可加可删除性质十分有用。
The MStream Algorithm
聚类文本流的一个最重要的考虑是如何定义文本和簇之间的关系。基于相似度的流聚类方法使用度量比如余弦相似度来衡量一个文档和一个簇之间的相似度。为了处理概念漂移问题，这些方法通常选择一个相似度阈值。当聚类一个文档时，如果它和最近的簇的相似度大于该阈值，就将其赋予该簇，否则就将其赋予一个新簇。然而，在真实应用中很难手动的选择一个合适的阈值。
与此不同，本文作者假设文档是由迪利克雷过程多项式混合(DPMM)模型生成的。Yin and Wang为静态文本聚类的DPMM提出了一种collapsed Gibbs sampling算法。更近一步，本文作者提出基于DPMM的短文本聚类算法。该算法可以基于DPMM可以直接计算文档 d 选择一个存在的簇的概率，如下所示：
¬d 表示文档 d 从现在的簇特征向量中移除，这对于MStream的聚类更新处理很有用。对于一个新到来的文档，¬d并不影响 CF 向量。不同于静态文本聚类31，D 是现在记录的文本(所有簇中的文档数量)的数量，V 是现在记录的文本的单词表中单词数。
我们可以得到文档 d 选择一个新簇的概率，如下所示：
不同于静态文本聚类31，作者设置$\gamma = \alpha D$，因为对于文本流聚类的混合权重$\theta ~ GEM(\gamma)$，超参数$\gamma$应该是动态的。$\alpha D$是新簇中文档的伪数量(ps:这个数目是指估计的簇成型后的文档数量)，超参数$\beta$是新簇中每个单词伪的出现次数。
公式(4)和(5)的第一部分表示一个文档选择一个簇的概率和该簇含有的文档数量成比例。一个新到的文档选择具有更多文档的簇的概率更高，因此不会超过一定数量的簇将会创建，即使簇的数量可以是无限的。这也被称为富者更富现象，大型簇很吸引更多的文档。
公式(4)和(5)的第二部分实际上定义了文档和该簇之间的相似性。这部分是$N_d$个部分的乘积，对应于文档 d 中的$N_d$个单词。对于文档 d 中的每一个单词 w，对应的部分测度单词 w 在簇 z 中的频率。当一个簇具有更多的文档，这些文档和文档 d享有同样的单词，公式第二部分会更大，文档 d 也更可能选择该簇。
MStream算法的细节见Algorithm 1。该算法具有一次通过聚类处理和批量更新聚类过程。
The one pass clustering process of MStream可用于处理一次通过方案的文本流，该情况下假设流文本一个接一个地到来，并且我们只能处理每一个文档一次。对第一个文档，该算法会为其选择一个新簇。这个新簇的簇特征向量使用第一个文档初始化。接着，新到来的文档会选择一个现存的簇或者一个新簇，根据公式(4)和(5)计算出来的概率。当新簇被选中，我们创建要给新簇来存储相应的文档。否则，就将对应的文档添加到选中的存在的簇，根据其可加性质。
The update clustering process of MStream可用于处理批量方案的文本流，其假设流文档一个批次地到来，我们可以多次处理每一批次中的文档。当一个新的文档批次到来时，我们最先使用一次通过聚类处理来获得一个该批文档一次迭代的聚类结果。然后我们使用更新聚类处理来更新聚类结果。对每一文档，我们先将其从归属的簇中删除。然后，我们根据它归属于K个簇和一个新簇的概率将其重新赋予概率最高的簇（簇特征向量并不对这文档进行更新）。对最后一次迭代，我们将每一个文档赋予最高概率对应的簇。
MStream算法需要记录当前的K个簇的特征向量和当前批次的文档。其空间复杂度是$O(KV+M\overline{L})$，其中K是簇数量，V是单词表的尺寸，M是每一批次中文档数量，$\overline{L}$是一个批次中文档的平均长度。计算一个文档属于某个簇的概率的时间复杂度是和文档的平均长度线性相关的。一次通过聚类过程的时间复杂度是$O(KN\overline{L})$,其中N是流中文档总数。具有一次通过聚类处理和更新聚类处理的算法的时间复杂度是$O(IKN\overline{L})$，其中I是每一个批次的迭代数量。
The MStreamF Algorithm
随着越来越多的文档到啦，簇的数量也会增加，MStream的空间和时间复杂度会增加到很大的地步，如果我们不删除过时的批次的话。另外，和整个数据流相比，我们常常对一段特定时期的信息感兴趣。和检测然后删除过时的簇相比，另一种选择是直接删除过时的文档，该方法更简单和高效。然而，本论文作者只存储当前批次中的文档，过去批次中的文档被丢弃。一个直觉是簇可以被视为与其文档相结合的大文档，我们可以存储没有过时的批次的簇。当批次 b 中的文档过时，我们可以直接从当前簇特征向量中删除掉批次 b 中的文档，减法操作定义如下。
基于上面的直觉，作者提出MStream算法改进了的带有遗忘规则的版本，称为MStreamF。该算法的细节见Algorithm 2。MStreamF具有一个超参数$B_s$，代表存储的批次的最大数量，当存储的批次数目大于$B_s$时，该算法在聚类新批次文档前将过时批次的文档从其所属簇特征向量中删除，这步操作使用可删除性质。
随着更多文档批次到达，我们可以检测新的簇和删除旧批次中的文档。一些簇会被置为空，因为过时的文档被删除了。当一个簇变为空时，其后的文档选择这个簇的概率为零。为了方便进一步分析，作者并不服用过去的簇的编号。
CONCLUSION
在本论文中，作者第一次提出一种基于迪利克雷过程多项式混合(DPMM)模型的短文本流聚类聚类算法，称为MStream，该算法可以自然得处理概念漂移问题和特征稀疏问题。(MStream)算法只需对流一次通过(one pass of the stream)即可实现最先进的性能，并且当允许每批次多次迭代时，可以获得更好的性能。作者们进一步提出具有遗忘规则的(MStream)的改进算法(MStreamF)，该算法能够通过高效地删除过时批次的簇，来删除过时的文档。作者们的扩展实验显示上述两种算法可以在一些真实数据集上取得比三种基准更好的表现。
作为将来的工作，作者打算使用提出的方法来改进其他相关应用的表现，比如搜索结果多样化，事件检测和追踪，文本摘要。
REFERENCES
31 Jianhua Yin and JianyongWang. 2016. A model-based approach for text clustering with outlier detection. In ICDE. IEEE, 625–636.