2011年4月24日,星期日

半监督的LDA:第三部分

在我的 以前的帖子 我讨论了半监督LDA的想法:在语料库上构建主题模型,其中一些文档具有关联的标签,但大多数文档没有关联的标签。目的是提取主题,该主题由语料库中的所有文本告知(例如,无监督的LDA),但也可以预测观察到的标签(如有监督的LDA)。

监督结果

在我以前的文章中,我没有说明如何计算$ p(y | w)$,即给定文档文本的文档标签的分布。继 光盘LDA论文 我使用了谐波均值估算器( 最糟糕的蒙托卡罗方法),但我只使用了1个样本量(有史以来最差的样本量)。实际上,这意味着:
  1. 对于每个标签$ y $
    1. 使用以标签为条件的Gibbs采样器绘制$ z \ sim p(\ cdot | w,y)$。
    2. 计算$ p(w | z,y)= \ prod_i \ frac {n ^ {(w_i)} _ {-d,u ^ k_ {z_i}} + \ beta} {n ^ {(\ cdot)} _ { -d,u ^ k_ {z_i}} + W \ beta}。$
    3. 估计$ p(w | y)\大约p(w | z,y)$。
  2. 计算未归一化的后验$ p(y | w)\ propto p(w | y)p(y)$并归一化。
在完全标记的数据集(即监督学习)上,这可以提供良好的结果。这是经过监督的跑步的结果,
这里没有其他分类器:给定由LDA程序生成的文档文本,将根据标签的后验分布确定0/1丢失。

您可能会问:为什么分类器不会将训练集上的损失设为零?通过(临时)从训练集中删除文档,然后运行推理算法来获取标签后验,可以评估此​​处的井损失。这仍然是泛化性能的有偏估计,但有些保守。测试集上的实际0/1损失约为0.23(即77%的准确度)。

接下来,您可能会问:只有77%?正如我在 以前的帖子,从用户的关注者集中预测性别具有挑战性,主要是因为我仅标记了数据的一小部分,而受欢迎的Twitter帐户(即最有可能被关注的Twitter帐户)往往不会具有性别歧视性。我能够相当准确地预测Twitter用户的性别,但是我必须在Twitter帐户中组合多种信息来源,社交图仅是其中的一个组成部分。以我的经验,相对于我尝试过的其他事情,仅使用关注者信息的准确性为77%,这确实非常好。特别是在所有社交图边缘集上执行无监督的LDA,然后对标记的子集(通过Vowpal Wabbit)进行有监督的分类,可以达到72%的准确性。请注意,准确率是72%并不是草率的:这是一系列实验的最佳结果,在这些实验中,我改变了LDA模型中主题的数量和其他参数。

我的直觉是,在标记的子集上进行监督的LDA不会比在整个集合上进行无监督的LDA做得好,然后在标记的子集上进行监督的分类,因为后者技术使用了所有数据。现在我必须更新我的直觉!

半监督结果

不幸的是,当我添加无人监督的数据时,情况变得很糟糕。这是测试集上的准确度图,它是未标记的训练数据所占比例的函数。
这很不幸,因为我想将此图中的x轴设为0.99(即,仅标记了我总体数据的1%),而且趋势不是我的朋友。

仍然有很多调优和错误查找功能,因此我不必沉没。但是,也没有很好的理论结果来推动事情:我不知道由于基于生成模型向分类器添加无监督数据而导致的分类改进的任何保证,尤其是当已知生成模型不正确时(例如,文档实际上不是以这种方式生成的)。所以在某个时候,我将不得不举起白旗。

2011年4月17日,星期日

半监督的LDA:第二部分

在我的 以前的帖子 我提出了半监督LDA的想法:在语料库上构建主题模型,其中一些文档具有关联的标签,但大多数文档没有关联的标签。目的是提取主题,该主题由语料库中的所有文本告知(例如,无监督的LDA),但也可以预测观察到的标签(如有监督的LDA)。我的一些初步结果看起来很有希望。

该方法

我的方法是基于 光盘LDA (及其表弟 标有LDA)。 光盘LDA修改了原始LDA,以便文档类标签$ y_d $可以将原始文档主题$ z $重新映射为转换后的主题$ u $,然后控制单词发射概率。这是DiscLDA论文中的板岩表示,
对于那些代数思考的人,这是生成模型的描述。
  1. 绘制主题比例$ \ theta | \ alpha \ sim \ mbox {Dir}(\ alpha)$。
  2. 绘制单词发射向量$ \ phi | \ beta \ sim \ mbox {Dir}(\ beta)$。
  3. 绘制类标签$ y | \ pi \ sim p(y | \ pi)$来自某些先前的分发。
  4. 每个字
    1. 绘制主题分配$ z_n | \ theta \ sim \ mbox {Mult}(\ theta)$。
    2. 绘制转换后的主题分配$ u_n | z_n,T,y \ sim \ mbox {Mult}(T ^ y_ {u_n,z_n})$。
    3. 画字$ w_n | z_n,\ phi_ {1:K} \ sim \ mbox {Mult}(\ phi_ {z_n})$。
接下来的$ T $矩阵固定为块零和块对角线的混合,基本上是为1)一些在所有类标签上共享的主题$ k_1 $和2)一些$ | Y | k_0 $个主题,每个类别标签会获得$ k_0 $个主题,该主题保留与该特定类别标签\ [
T ^ y = \ begin {pmatrix}
0&I_ {k_0} 1_ {y = 1} \\
\ vdots和\ vdots \\
0&I_ {k_0} 1_ {y = | Y |} \\
I_ {k_1}&0
\ end {pmatrix}。
\]请注意,存在$(k_0 + k_1)$可能的$ z $和$(| Y | k_0 + k_1)$可能的$ u $。此外,单个$ z_i $会与一个独立于$ y $的单个$ u $或由$ y $索引的一组$ | Y | $可能的$ u $关联。实施时,我发现根据映射\ [
u ^ y_z = \ begin {cases} z& z <k_1 \\ z + k_0(y-1)&z \ geq k_1 \ end {cases},
\]机械地暗示更改$ y $会导致一组$ k_0 $主题被“切换”。

尽管就学习算法的速度和可扩展性而言,在线变式贝叶斯算法目前是山丘之王,但我发现Gibbs采样相对容易推理和实现,因此我继续这样做。假设观察到文档$ d_i $的标签$ y_ {d_i} $,Gibbs采样器与无监督LDA基本上相同,\ [
p(z_i = j | w,z _ {-i},y)\ propto \ frac {n ^ {(w_i)} _ {-i,u ^ {y_ {d_i}} _ j} + \ beta} {n ^ {(\ cdot)} _ {-i,u ^ {y_ {d_i}} _ j} + W \ beta} \ frac {n ^ {(d_i)} _ {-i,u ^ {y_ {d_i}} _ j } + \ alpha} {n ^ {(d_i)} _ {-i,\ cdot} +(k_0 + k_1)\ alpha}。
\]如果在$ u $变量上将抽样概念化,则这是单标签情况下标签LDA的结果:Gibbs抽样器与原始LDA相同,只是只允许在给定的可行主题之间进行转换文件标签。

如果未观察到$ y_ {d_i} $,我可以将其集成。但是为了便于实施,我决定也对Gibbs进行抽样,\ [
p(y_d = k | w,z,y _ {-d})\ propto p(w_d | w _ {-d},y_d = k,z,y _ {-d})p(y_d = k | z,y_ { -d})。
\]第一项是给定所有文档的所有主题和标签分配以及其他文档中所有单词的文档$ d $的单词序列的可能性。这是由\ [
p(w_d | w _ {-d},y_d = k,z,y _ {-d})\ propto \ prod _ {\ {i | d_i = d,z_i \ geq k_1 \}} \ frac {n ^ {(w_i)} _ {-d,u ^ k_ {z_i}} + \ beta} {n ^ {(\ cdot)} _ {-d ,u ^ k_ {z_i}} + W \ beta}。
\]内容如下:对于文档$ d $中的每个单词,计算在所有其他文档$ n ^ {(w_i)} _ {-d,u中将其分配给主题$ u ^ k_ {z_i} $的次数^ k_ {z_i}} $,计算在所有其他文档$ n ^ {(\ cdot)} _ {-d,u ^ k_ {z_i中,将任何单词分配给主题$ u ^ k _ {z_i} $的次数}} $,并应用Dirichlet-多项式共轭。基本上,就$ u $变量而言:每组基于标签的主题对文档中单词的解释程度如何?请注意,共同的主题会给可能性带来相同的因素,因此,优化产品只能取代特定于标签的主题。特别是如果文档仅使用常见主题,则在此术语中不会偏爱任何标签。

第二项$ p(y_d = k | z,y _ {-d})= p(y_d = k | y _ {-d})$是文档标签的先前(观察文档文本)分布。在在线设置中,文档标签上的先前分布取决于先前观察到的文档标签是合理的,但是在批处理Gibbs采样器中,要求用户在类标签上指定固定的多项式分布即$ p( y_ {d_i} = k | y _ {-d_i})= p_k $。

它行得通吗?

最初的动机是提取特征以构建更好的分类器,因此表达此问题的最佳方法是:``使用半监督的LDA所产生的特征比通过运行无监督的LDA所获得的特征(1)都更适合分类在所有数据上或2)在标记的数据子集上运行受监督的LDA。''我仍在努力回答这个问题。

然而,技术``运作''还有另一种感觉。由于无标签数据大大超过了有标签数据,因此我担心的是半监督方法实际上会退化为无监督方法。我有一些数据表明情况并非如此。

设置如下:我大约有200万个``文档'',其中每个文档都是特定Twitter个人资料所关注的一组人。根据Mechanical Turk的结果,我大约将这些文件中的1%标记为男性或女性。如上所述,我已经有了一个初步的Gibbs采样器实现,同时查看了两个统计信息:每个采样主题的平均对数概率和每个观察到的文档标签的平均对数概率。通常,我希望随着系统学习单词的连贯性,话题概率会随着时间的推移而提高。但是,标签概率发生了什么?如果解释文档文本的压力压倒了符合观察标签的压力,则随着时间的推移,观察到的标签可能会变得不太可能。我特别担心这一点,因为我选择了Gibbs的捷径,对未观察到的标签进行采样,而不是将它们整合在一起。

这是我的数据的典型运行结果。 (可悲的是,在笔记本电脑上花了半天时间才能生成此输出。)
在第一次遍历数据时,标签基本上是随机分配给未标签的数据,并且文档似乎相互抵消,因此观察到的标签非常适合(平均$ \ log(p)\ approx -0.02 $类似于$ p \大约98 \%$)。平均标签对数概率仅在观察到的标签上计算;因此,在这一点上,这些主题并不擅长预测文档中的标记,但它们却擅长预测观察到的标签。随着采样器最初进行,主题概率增加,但标签概率降低。当我第一次观看大批量生产的产品时,我发现自己被弄砸了,最终标签被完全洗掉了。但是最终,采样器开始很好地解释标记和观察到的标签。经过100次通过后,我最终观察到的标签仍能很好地解释,平均$ \ log(p)\ approx -0.08 $,就像$ p \ approx 92 \%$。虽然无监督的数据已经降低了模型对观察到的标签的解释能力,但从泛化的角度来看这可能是一件好事(即``内置于正则化'')。

因此,下一步是在我最初的分类问题的情况下,将此半监督的LDA与非监督的LDA和监督的LDA进行比较,以了解除我自己的娱乐之外,所有这一切是否有意义。

2011年4月8日,星期五

半监督的LDA:想法

我当前的问题域的特征是大量的未标记数据和少量的标记数据。最近我 经历了一些成功 通过将LDA应用于未标记的数据以创建社交图的表示形式,并在我的监督分类器中使用所得特征。

数篇论文指出,同时提取主题和估计分类器比上述过程具有更好的性能:1)提取主题而不考虑分类问题,然后2)在监督分类器中使用主题。不幸的是,我读过的论文都假定始终遵循文档类。我的案例是更经典的半监督:我想利用所有未标记和标记的数据来构建最佳分类器。出乎意料的是,尽管我觉得这是很典型的,但我在文献中没有看到这种情况。

LDA是一个生成模型,因此从直觉上看,应该感觉很容易将其适应于仅部分观察到关联文档信息的情况:在实践中存在一些陷阱。我将深入研究LDA的两个扩展的推理策略,这些扩展旨在与(充分观察到的)关联文档标签一起使用,以查看是否可以找到一种方法来使它们适应半监督数据的情况。

监督的LDA

首先是 有监督的LDA方法 来自“教父”本人(Blei)和乔恩·麦考利夫(Jon McAuliffe)。在进入细节之前,我将重复本文的总体结果:联合评估主题和分类器比先评估主题然后再评估主题更好。让我再次想起,当每个文档都与受监管信息相关联时,便证明了这一结果。

这是本文图1中模型的平板显示。


该模型与原始LDA相似,但具有额外的标签发射步骤。
  1. 绘制主题比例$ \ theta | \ alpha \ sim \ mbox {Dir}(\ alpha)$。
  2. 每个字
    1. 绘制主题分配$ z_n | \ theta \ sim \ mbox {Mult}(\ theta)$。
    2. 画字$ w_n | z_n,\ beta_ {1:K} \ sim \ mbox {Mult}(\ beta_ {z_n})$。
  3. 绘制响应变量$ y | z_ {1:N},\ eta,\ delta \ sim \ mbox {GLM}(\ tilde z,\ eta,\ delta)$。
其中$ \ tilde z = \ frac {1} {N} \ sum_n z_n $是文档中的经验主题频率,并且 GLM 是广义线性模型。

在监督的LDA论文中,通过变数EM进行推理。辅助函数$ \ mathcal {L} $是使用变化分布$ q $派生的,其中每个主题向量是从每个文档$ \ gamma $参数化的Dirichlet分布中提取的,而每个单词是从每个文档位置$ \ phi_n $参数化多项式分布。对于单个文档,它看起来像\ [
\ begin {aligned}
\ log p(w_ {1:N},y | \ alpha,\ beta_ {1:K},\ eta,\ delta)
&\geq \mathcal{L} (\gamma, \phi_{1:N};\ alpha,\ beta_ {1:K},\ eta,\ delta)\\
&= E_q [\ log p(\ theta | \ alpha)] + \ sum_ {n = 1} ^ N E_q [\ log p(Z_n | \ theta)] \\
&\;\; \; \; + E_q [\ log p(y | Z_ {1:N},\ eta,\ delta)] + H(q)。
\ end {aligned}
\]好吧,适应半监督情况没问题,对吧?在这种情况下,对于所讨论的文档,不会观察到$ y $,因此,在该函数的辅助函数中,$ E_q [\ log p(y | Z_ {1:N},\ eta,\ delta)] $项不存在。文档,基本上没有标签的文档的变体参数遵循原始LDA的更新规则。所以基本上我需要 sLDA的公开实施 并对其进行修改以接受隐藏了目标函数的相应部分的``未观察到''类标签。

正如马特·霍夫曼(Matt Hoffman)向我指出的那样,这可能不符合我的期望。由于未标记的数据大大超过了标记的数据,因此大多数$ \ phi_n $不会承受任何压力来解释已知的标签,并且这些将主导$ \ beta_ {1:K}的最终估算$。这是因为$ \ beta_ {1:K} $的M步由\ [
\ hat \ beta_ {k,w} \ propto \ sum_ {d = 1} ^ D \ sum_ {n = 1} ^ {N_d} 1_ {w_ {d,n} = w} \ phi ^ k_ {d,n }。
\]因此预测是,随着我使用这种技术抛出更多未标记的数据,它会退化为等同于首先运行主题估计器,然后运行分类器的东西。坏度10000?

也许不是。给定一组$ D_s = \ {(d,l)\} $带标签的文档,以及较大的一组$ D_u = \ {d \} $无标签的文档,哪个更好?
  1. 在$ D_s $上运行受监督的LDA,而忽略$ D_u $。
  2. 在$ D_s \ cup D_u $上运行无监督的LDA,然后对$ D_s $进行分类。
直觉表明第二种方法更好:毕竟,第一种是忽略大多数数据。生成模型也许在说,当无监督数据量巨大时,单独的特征提取和分类步骤将接近最优。

情况仍然不能令人满意。一种想法是重视文件上带有标签的重量,以使它们不会被未标签的数据所淹没。这具有实际的优点,那就是希望对公开可用的sLDA实现进行直接的修改(基本上,将每个带标签的文档都视为多次出现;因此在上面的$ -beta_ {1:K} $ M步骤,则加重了带有标签的文档的$ \ phi $)。但是,感觉很脏。

另一个想法是从 转导支持向量机。在二进制情况下,基本思想是,尽管未标记数据上的标记是未知的,但它们被认为是0或1;因此,可以将它们视为0。因此,实际上,决策边界应避免未标记分布中的高密度区域。另外,还可以使用标签的经验分布来偏爱决策边界,这些决策边界会在未标记的数据中创建相似的标签分布。类似地,对于二进制情况下的``传导性LDA'',我需要$ y $上的先验值,该值更喜欢未标记点的极值,可能会偏向于促进未标记数据上的某些标签分布。最终,这意味着在变化范围内,$ E_q [\ log p(y | Z_ {1:N},\ eta,\ delta)] $项对于未标记的点变为$ E_q [E_ \ zeta(\ log p(y | Z_ {1:N},\ eta,\ delta)] $项,其中$ \ zeta $是在$ y $上优先使用的极值,因为粉碎未标记数据的一种简单方法是设置$ || \ eta || \\ infty $或$ \ delta \ to 0 $这些参数的一些先前分布对于保持事物的控制是必要的。

虽然我对``传导性LDA''感到非常兴奋,但实际上,我认为要花很长时间才能使它工作。

光盘LDA

接下来是 光盘LDA 来自莎莉(Julien)和《统计迈克尔·乔丹(Michael Jordan of statistics)》。这是本文图1至图3中模型的平板显示。


该模型修改原始LDA,以使文档类标签$ y_d $可以将原始文档主题$ z_d $重新映射为转换后的主题$ u_d $,从而控制单词发射概率。
  1. 绘制主题比例$ \ theta | \ alpha \ sim \ mbox {Dir}(\ alpha)$。
  2. 绘制单词发射向量$ \ phi | \ beta \ sim \ mbox {Dir}(\ beta)$。
  3. 绘制类标签$ y | \ pi \ sim p(y | \ pi)$来自某些先前的分发。
  4. 每个字
    1. 绘制主题分配$ z_n | \ theta \ sim \ mbox {Mult}(\ theta)$。
    2. 绘制转换后的主题分配$ u_n | z_n,T,y \ sim \ mbox {Mult}(T ^ y_ {u_n,z_n})$。
    3. 画字$ w_n | z_n,\ phi_ {1:K} \ sim \ mbox {Mult}(\ phi_ {z_n})$。
在实践中,$ T $矩阵固定为块零和块对角线的混合体,它们的基本排列方式是1)一些类别的主题$ K_1 $在所有类标签上共享; 2)一些数字$ | Y |。 K_0 $个主题,每个类别标签会获得$ K_0 $个主题,该主题保留与该特定类别标签\ [
T ^ y = \ begin {pmatrix}
0&I_ {K_0} 1_ {y = 1} \\
\ vdots和\ vdots \\
0&I_ {K_0} 1_ {y = | Y |} \\
I_ {K_1}&0
\ end {pmatrix}。
\]以这种方式使用,生成的模型非常类似于 标有LDA;实际上,我建议阅读Labeled LDA论文以了解这种情况下的情况(快速摘要:折叠的Gibbs采样器与香草LDA相同,只是根据类标签仅允许在可行主题之间进行转换。 )

对于半监督情况,我们可以说不是总是观察到$ y $。但是,在DiscLDA生成模型中很明显,我们需要对$ y $进行边际化。换句话说,未标记的文档将不限于仅使用在所有类标签之间共享的$ K_1 $主题。相反,他们也将被允许使用每个类别标签主题的某种混合,这些主题与未观察到的类别标签的后验分布$ p(y_d | \ cdot)$有关。

那么当未标记的数据量大大超过标记的数据量时会发生什么呢?我最终可能会退化为等同于香草LDA的东西,例如,在二进制情况下,大多数未观察到的标签将最终以$ p(y_d = 1 | \ cdot)\ approx 1/2 $结束,这意味着实际上所有每个班级的主题都被``淘汰''了。所以再次,我可能需要一个``传导先验'',这实际上是$ y $分布的先验,它比类标签更喜欢低熵分布。

在实践中,我将使用DiscLDA(标签LDA)作为起点。这基本上是因为折叠的Gibbs采样器在受限转换矩阵的情况下易于实现。在半监督情况下使此方法起作用可能会很有挑战性,因为该模型可能倾向于让未标记数据上的发明类别标签主导已标记数据上实际观察到的类别标签。