Question

1. 基于分歧的方法disagreement-based methods使用多个学习器，学习器之间的分歧disagreement对未标记数据的利用至关重要。

   协同训练co-traning是此类方法的重要代表。它最初是针对多视图multi-view数据设计的，因此也被视作多视图学习multi-view learning的代表。

4.1 数据视图

1. 在不少现实应用中，一个数据对象往往同时拥有多个属性集attribute-set。每个属性集就构成了一个视图。

2. 假设数据集为 $ MathJax-Element-403 $ ， 其中 $ MathJax-Element-404 $ 。属性集合 $ MathJax-Element-405 $ 。假设属性集合划分为 $ MathJax-Element-406 $ ，其中：

   $ \mathbf x^{(1)}=\{x_1, x_2,\cdots, x_{d_1}\},\quad \mathbf x^{(2)}=\{x_{d_1+1}, x_{d_1+2},\cdots, x_{d}\} $

   即将属性划分为两个属性集，前 $ MathJax-Element-407 $ 个属性为第一个属性集，后 $ MathJax-Element-408 $ 个属性属于第二个属性集。

   • 原始样本 $ MathJax-Element-548 $ 被划分为两个属性向量 $ MathJax-Element-410 $ ，它们分别属性这两个属性集。
   • $ MathJax-Element-411 $ 这样的数据就是多视图数据，每个属性集都是一个视图。

   如： <身高、体重、年龄、学历、爱好、工作> 可以划分为两个属性集： <身高、体重、年龄>以及<学历、爱好、工作> 。

3. 假设不同视图具有相容性compatibility：即其所包含的关于输出空间 $ MathJax-Element-412 $ 的信息是一致的。

   令 $ MathJax-Element-413 $ 为从第一个属性集判别的标记空间， $ MathJax-Element-414 $ 为从第二个属性集判别的标记空间，则有 $ MathJax-Element-415 $ 。

   注意：这里仅要求标记空间相同，并没有要求每个标记相同。

4.2 协同训练算法

1. 协同训练充分利用了多视图的相容互补性。

2. 假设数据拥有两个充分且条件独立视图。

   • 充分：指每个视图都包含足以产生最优学习器的信息。
   • 条件独立：指在给定类别标记条件下，两个视图独立。

   此时，可以用一个简单的办法来利用未标记数据：

   • 首先在每个视图上，基于有标记样本，分别训练出一个分类器。
   • 然后让每个分类器分别去挑选自己最有把握的未标记样本赋予伪标记，并将伪标记样本提供给另一个分类器作为新增的有标记样本用于训练更新。
   • 该“ 互相学习、共同进步”的过程不断迭代进行，直到两个分类器都不再发生变化，或者到达指定的迭代轮数为止。

   注意：

   • 如果在每轮学习中都考察分类器在所有未标记样本上的分类置信度，则会有很大的计算开销。因此在算法中使用了未标记样本缓冲池。
   • 分类置信度的估计因基学习算法而异。

3. 协同训练算法：

   • 输入：

     • 有标记样本集 $ MathJax-Element-416 $
     • 未标记样本集 $ MathJax-Element-417 $
     • 缓冲池大小 $ MathJax-Element-425 $
     • 每轮挑选的正例数量 $ MathJax-Element-455 $
     • 每轮挑选的反例数量 $ MathJax-Element-457 $
     • 基学习算法 $ MathJax-Element-451 $
     • 学习轮数 $ MathJax-Element-430 $

   • 输出：未标记样本的预测结果 $ MathJax-Element-423 $

   • 步骤：

     • 从 $ MathJax-Element-473 $ 中随机抽取 $ MathJax-Element-425 $ 个样本构建缓冲池 $ MathJax-Element-470 $

     • $ MathJax-Element-427 $

     • 从 $ MathJax-Element-428 $ 中分别构建： $ MathJax-Element-429 $ 分别表示第一视图有标记数据集、第二视图有标记数据集：

       $ \mathbb D_l^{(1)}=\{( \mathbf{\vec x}_1^{(1)} ,y_1),( \mathbf{\vec x}_2^{(1)}, y_2),\cdots,( \mathbf{\vec x}_l^{(1)} ,y_l)\}\\ \mathbb D_l^{(2)}=\{( \mathbf{\vec x}_1^{(2)} ,y_1),( \mathbf{\vec x}_2^{(2)}, y_2),\cdots,( \mathbf{\vec x}_l^{(2)} ,y_l)\} $

     • 开始迭代，迭代终止条件是：迭代收敛或者迭代次数达到 $ MathJax-Element-430 $ 。迭代过程为：

       • 从 $ MathJax-Element-470 $ 中分别构建（其中 $ MathJax-Element-432 $ 为其元素个数）： $ MathJax-Element-433 $ 分别表示第一视图缓冲数据集、第二视图缓冲数据集：

         $ \mathbb D_s^{(1)}=\{\mathbf{\vec x}_{s1}^{(1)} , \mathbf{\vec x}_{s2}^{(1)},\cdots,\mathbf{\vec x}_{sm}^{(1)} \}\\ \mathbb D_s^{(2)}=\{\mathbf{\vec x}_{s1}^{(2)} , \mathbf{\vec x}_{s2}^{(2)},\cdots, \mathbf{\vec x}_{sm}^{(2)} \} $

       • 考察视图一：

         • 利用 $ MathJax-Element-434 $ 训练 $ MathJax-Element-451 $ 得到分类器 $ MathJax-Element-437 $ 。
         • 然后考察 $ MathJax-Element-437 $ 在 $ MathJax-Element-438 $ 上的分类置信度。挑选 $ MathJax-Element-455 $ 个正例置信度最高的样本 $ MathJax-Element-440 $ 、 挑选 $ MathJax-Element-457 $ 个反例置信度最高的样本 $ MathJax-Element-442 $ 。
         • 然后将 $ MathJax-Element-445 $ 的视图二标记为正例，将 $ MathJax-Element-446 $ 的视图二标记为反例：
         $ \tilde {\mathbb D}_p^{(2)}=\{(\mathbf{\vec x}_i^{(2)},1)\mid \mathbf{\vec x}_i^{(1)} \in \mathbb D_p^{(1)} \}\\ \tilde {\mathbb D}_n^{(2)}=\{(\mathbf{\vec x}_i^{(2)},-1)\mid \mathbf{\vec x}_i^{(1)} \in \mathbb D_n^{(1)} \} $

         这里并没有简单的将 $ MathJax-Element-445 $ 标记为正例、 $ MathJax-Element-446 $ 标记为反例。而是标记它们对立的那个视图，帮助对方视图增加标记数据。

       • $ MathJax-Element-447 $ ，更新 $ MathJax-Element-454 $ 。此时 $ MathJax-Element-454 $ 会缩小，因为有部分样本从视图一中获得了标记信息。

       • 考察视图二：

         • 利用 $ MathJax-Element-450 $ 训练 $ MathJax-Element-451 $ 得到分类器 $ MathJax-Element-453 $ 。
         • 然后考察 $ MathJax-Element-453 $ 在 上 $ MathJax-Element-454 $ 的分类置信度。挑选 $ MathJax-Element-455 $ 个正例置信度最高的样本 $ MathJax-Element-456 $ 、 挑选 $ MathJax-Element-457 $ 个反例置信度最高的样本 $ MathJax-Element-458 $ 。
         • 然后将 $ MathJax-Element-459 $ 的视图一标记为正例，将 $ MathJax-Element-460 $ 的视图一标记为反例：
       $ \tilde {\mathbb D}_p^{(1)}=\{(\mathbf{\vec x}_i^{(1)},1)\mid \mathbf{\vec x}_i^{(2)} \in \mathbb D_p^{(2)} \}\\ \tilde {\mathbb D}_n^{(1)}=\{(\mathbf{\vec x}_i^{(1)},-1)\mid \mathbf{\vec x}_i^{(2)} \in \mathbb D_n^{(2)} \} $
       • $ MathJax-Element-461 $ 。
       • 如果 $ MathJax-Element-472 $ 在训练前后，均未发生改变，则迭代收敛。否则继续向下执行。

       如何判断是否发生改变？通常可以考察它们的预测结果是否一致

       • 更新 $ MathJax-Element-463 $ ：
       $ \mathbb D_l^{(1)}=\mathbb D_l^{(1)}\bigcup(\tilde {\mathbb D}_p^{(1)}\bigcup \tilde {\mathbb D}_n^{(1)})\\ \mathbb D_l^{(2)}=\mathbb D_l^{(2)}\bigcup(\tilde {\mathbb D}_p^{(2)}\bigcup \tilde {\mathbb D}_n^{(2)}) $

       • 补充 $ MathJax-Element-470 $ ：从 $ MathJax-Element-473 $ 中随机抽取 $ MathJax-Element-469 $ 个样本加入 $ MathJax-Element-470 $ ，同时 $ MathJax-Element-473 $ 中移除这 $ MathJax-Element-469 $ 个样本。

         这意味着： $ MathJax-Element-470 $ 越来越大、 $ MathJax-Element-473 $ 越来越小。

   • 最终得到分类器 $ MathJax-Element-472 $ 。将这两个分类器用于 $ MathJax-Element-473 $ 即可得到未标记样本的预测结果： $ MathJax-Element-474 $ 。

4.3 性质

1. 协同训练过程虽然简单，但是理论证明：若两个视图充分且条件独立，则可利用未标记样本通过协同训练将弱分类器的泛化性能提升到任意高。

   • 不过视图的条件独立性在现实任务中通常很难满足，因此性能提升幅度没有那么大。
   • 但研究表明，即便在更弱的条件下，协同训练仍可以有效提升弱分类器的性能。

2. 协同训练算法本身是为多试图数据而设计的，但此后出现了一些能在单视图数据上使用的变体算法。

   • 它们或是使用不同的学习算法，或是使用不同的数据采样，甚至使用不同的参数设置来产生不同的学习器，也能有效利用未标记数据来提升性能。

   • 后续理论研究表明，此类算法事实上无需数据拥有多试图，仅需弱学习器之间具有显著的分歧（或者差异），即可通过相互提供伪标记样本的方式来提升泛化性能。

     而不同视图、不同算法、不同数据采样、不同参数设置等，都是产生差异的渠道，而不是必备条件。

3. 基于分歧的方法只需要采用合适的基学习器，就能较少受到模型假设、损失函数非凸性和数据规模问题的影响，学习方法简单有效、理论基础相对坚实、使用范围较为广泛。

   • 为了使用此类方法，需要能生成具有显著分歧、性能尚可的多个学习器。
   • 但当有标记样本较少，尤其是数据不具有多试图时，要做到这一点并不容易，需要巧妙的设计。