基本信息

文献名称：Collective Decision for Open Set Recognition
出版期刊：IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
发表日期：04 March 2020
作者：Chuanxing Geng and Songcan Chen

摘要

在开集识别（OSR）中，几乎所有现有的方法都是专门为识别单个实例而设计的，即使这些实例是集体地成批出现的。识别者在决策中要么拒绝它们，要么使用经验设定的阈值将它们归类到某个已知的类。因此，决策阈值起着关键作用。然而，其选择往往依赖于已知类的知识，不可避免地会因缺乏未知类的可用信息而带来风险。另一方面，一个更现实的OSR系统不应该仅仅依赖于拒绝决策，而应该更进一步，特别是在发现拒绝实例中隐藏的未知类方面，而现有的OSR方法没有特别注意。提出了一种新的集体/批量决策策略，扩展了已有的OSR算法，并考虑了测试实例之间的相关性，实现了新类的发现.通过对层次狄利克雷过程（HDP）的改进，提出了一种基于集体决策的OSR框架（CD-OSR）。由于HDP的存在，我们的CD-OSR不需要定义判决阈值，可以同时实现开集识别和新类发现。最后，在基准数据集上的实验验证了CDOSR算法的有效性。

现在主要的方法

1.1-vs-Set Machine

核心思想：
基于支持向量机（SVM），通过引入“开放空间风险”（Open Space Risk）概念，限制已知类在特征空间的覆盖范围。
实现方式：
1.对每个已知类训练一个二元SVM，生成两个平行超平面（“A”和“B”），形成一个有限的“板层”（slab）区域。
2.测试实例若位于板层内，则分类为已知类；若位于板层外，则被拒绝为未知类。

在训练1-vs-Set机器之后，出现在两个超平面之间的测试实例将被标记为适当的类。否则，它将被视为非目标类或被拒绝，具体取决于它位于板的哪一侧。如第1节所述，1-vs-Set机器在一定程度上降低了开放空间风险。然而，它仍然占据着无限的空间，这意味着开放空间的风险仍然存在。

传统OSR方法的共同局限

阈值依赖：
分类边界依赖经验设定的阈值，缺乏对未知类分布的适应能力。
孤立决策：
逐个处理测试实例，忽略批次数据中的相关性信息。
无法发现新类：
仅能拒绝未知类，需额外步骤（如人工标注或后处理）才能发现新类。
静态模型：
训练后模型固定，无法动态适应新出现的类别。

COLLECTIVE DECISION FOR OPEN SET RECOGNITION（CD-OSR）

大概介绍

如前所述，当前现有的OSR方法是专门为识别单个实例而设计的，即使这些实例都是成批到达的。因此，决策中的识别器要么拒绝它们，要么使用预先设置的阈值将它们分类到某个已知的类实例中，其中这样的决策阈值起着关键作用。然而，它的选择通常是基于已知类的知识，不可避免地会产生风险，因为没有可用的信息从未知类。另一方面，一个更现实的OSR系统不应该仅仅停留在拒绝决策上，而应该更进一步，特别是在发现拒绝实例中隐藏的未知类方面。遗憾的是，现有的OSR方法没有给予太多关注。

为了克服这些局限性，我们引入了一种新的集体决策策略OSR问题的目的是扩展现有的开集识别新的类发现。具体地说，一个集体决策为基础的OSR框架（CD-OSR）提出了略有修改HDP。由于HDP的特性，我们的CD-OSR不需要定义决策阈值，可以自动为测试中的未知类预留空间，自然导致新的类发现功能。有趣的是，这也使得它能够同时处理OSR和新类发现。此外，对测试实例进行批量处理，使得CD-OSR考虑了现有方法明显忽略的实例之间的相关性。请注意，CD-OSR实际上可以处理批实例和单个实例。

接下来，我们首先简要回顾HDP，它广泛用于通过在组之间共享混合成分来对多组数据进行联合聚类。在HDP中，常用的术语是“组”或“组件”。然而，我们在这里适应HDP与轻微的修改OSR问题。在OSR场景下，“class”实际上对应于“group”，而“subclass”对应于“component”。

分层狄利克雷过程（HDP）的原理与公式推导

1.HDP的生成模型

HDP是一种层次化的贝叶斯非参数模型，用于建模多个组（groups）之间的共享结构。其核心思想是通过两个层次的Dirichlet过程（DP）实现组间子类的共享：
$x_{ji}$的含义是观测数据，从参数${\theta }_{ji}$对应的分布$F({\theta }_{ji})$中采样,然后，HDP框架完成如下：
$G_0$是全局基分布（Global Base Distribution），由Dirichlet过程（DP）生成，参数为浓度参数$\gamma$和基分布$H$
$$G_0\mid \gamma ,H\sim \mathrm{DP}(\gamma ,H)$$
其作用是所有组（如不同类别）共享的全局子类分布。$G_0$是所有组中子类的“母版菜单”。

$G_j$是组内分布，每个组$j$的分布$G_j$由另一个Dirichlet过程生成，参数为浓度参数${\alpha }_0$和基分布$G_0$
$$G_j\mid {\alpha }_0,G_0\sim \mathrm{DP}({\alpha }_0,G_0)$$
$G_j$决定了组$j$中子类的分布。$G_j$可以看做是从$G_0$中“继承”子类，但允许组内子类的个性化调整。

实例生成：
组$j$中的实例$x_{ji}$的参数${\theta }_{ji}$从$G_j$中采样，数据$x_{ji}$由分布$F({\theta }_{ji})$生成
$${\theta }_{ji}\mid G_j\sim G_j,x_{ji}\mid {\theta }_{ji}\sim F({\theta }_{ji})$$
下图是其图示结构

2. 中国餐馆特许经营Chinese Restaurant Franchise（CRF）

CRF实际上是在中国餐馆流程（CRP）的基础上扩展的，允许多个餐馆共享一套菜肴。
HDP的生成过程可以通过CRF直观解释：

• 餐馆（组）：每个组对应一个餐馆$j$。
• 桌子（子类）：每个餐馆中的桌子对应组内的子类$t_{ji}$。
• 菜品（全局子类参数）：所有餐馆共享一个全局菜单，菜品对应全局子类的参数${\varphi }_k\sim H$
  顾客（实例$x_{ji}$）进入餐馆$j$,选择一个桌子$t_{ji}$，桌子上提供菜品${\varphi }_{kjt}$。若桌子是新创建的，则从全局菜单中选择新菜品。

3.条件分布的推导

组内子类分布：
通过积分掉$G_j$和$G_0$，可以得到实例分配的条件分布：
$${\theta }_{ji}\mid {\theta }_{j1},...,{\theta }_{j,i-1},{\alpha }_0,G_0\sim \sum _{t=1}^{m_j.}\frac{n_{jt}}{i-1+{\alpha }_0}{\delta }_{{\psi }_{jt}}+\frac{{\alpha }_0}{i-1+{\alpha }_0}{G}_0$$
其中$n_{jt}$是组$j$中桌子$t$的顾客数，${\psi }_{jt}$是桌子的参数。
公式含义：实例$x_{jt}$以概率$\frac{njt}{i-1+{\alpha }_0}$分配到已有桌子，或以概率$\frac{{\alpha }_0}{i-1+{\alpha }_0}$创建新桌子。
全局子类分布：
$${\psi }_{jt}\mid {\psi }_{11},...,{\psi }_{j-1},\gamma ,H\sim \sum _{k=1}^K\frac{m_{.k}}{m_{..}+\gamma }{\delta }_{{\varphi }_k}+\frac{\gamma }{m_{..}+\gamma }H$$

其中$m_{.k}$是所有组中分配到菜品${\varphi }_k$的桌子数，$m..={\sum }_{k}m{.}_k$。${\delta }_{{\varphi }_k}$表示${\varphi }_k$处的狄拉克测度。
其表达的含义是，新桌子以概率$\frac{m\cdot k}{m..+\gamma }$选择已有菜品，或以概率$\frac{\gamma }{m...+\gamma }$生成新菜品${\varphi }_{K+1}\sim H$

Gibbs Sampling

在CD-OSR框架中，公式（10）和（11）是Gibbs采样过程的核心

论文中公式(10)的物理意义

物理意义：
分配到已有桌子：
概率与当前桌子的“人气”（顾客数$n_{jt}$）和生成该实例的似然成正比。
举例：若桌子$t$上已有许多相似实例（高$n_{jt}$和高似然），新实例更可能加入该桌子。

（10）的第2行的公式表达的是，等号右边第一项是新的餐桌，点已有顾客点过的菜的概率之和。第二项是该新的餐桌点一道新的菜的概率。

公式(11)的物理意义

物理意义：
选择已有菜品：
概率与全局中该菜品的“流行度”（被选次数$m_{.k}$）和生成数据的似然成正比。
举例：若菜品$k$已被多个组使用（高$m_{.k}$），新桌子更可能选择它。
在实际应用中：

由于上述分层狄利克雷过程（HDP）的性质适合我们的问题，我们在这里调整HDP略有修改，以解决OSR问题。因此，一个集体决策为基础的OSR框架（CD-OSR）的建议作为一个初步的解决方案，对集体决策的开集识别。具体地，CD-OSR如下工作。

中国餐馆特许经营（CRF）模型与HDP符号的对应关系

(1) 餐馆（Restaurant） ↔ 组（Group）

• 每个餐馆对应HDP中的一个组（Group），例如一个已知类（如“猫”）或测试集。
• 组$j$的分布$G_j\sim \mathrm{DP}({\alpha }_0,G_0)$。

(2) 顾客（Customer） ↔ 实例$x_{ji}$

• 顾客是进入餐馆的个体，对应数据实例$x_{ji}$(组$j$中的第$i$个实例)。
• $x_{ji}\sim F({\theta }_{ji})$，其中${\theta }_{ji}$是子参数。

(3) 桌子（Table） ↔ 子类分配$t_{ji}$

• 桌子是组内的子类（Component），实例$x_{ji}$​被分配到某个桌子$t_{ji}$，对应子类归属。
• ${\theta }_{ji}={\psi }_{j{t}_{ji}}$（桌子参数）。

(4) 菜品（Dish） ↔ 全局子类参数${\varphi }_k$

• 菜品是全局共享的子类参数${\varphi }_k$ ，所有餐馆的桌子从同一份菜单选择菜品。
• ${\psi }_{jt}={\varphi }_{kjt}$(桌子$t$的菜品参数)。

(5) 菜单（Menu） ↔ 全局基分布 $G_0$

• 菜单是所有餐馆共享的全局子类分布$G_0$ ，由基分布$H$生成。
• $G_0\sim \mathrm{DP}(\gamma ,H)$，菜单中的菜品是${\varphi }_1，{\varphi }_2,....$。

(6) 厨师长（Chef） ↔ 基分布$H$

• 厨师长决定菜品的生成规则，对应基分布$H$ ，由基分布$H$（如高斯-威沙特分布）。
• ${\varphi }_k\sim H$,每个菜品参数从$H$中采样。

CD-OSR的实现与公式推导

CD-OSR原理

CD-OSR通过改进的HDP框架，将开放集识别转化为动态聚类问题，具体原理如下：

层次化子类共享

全局基分布$G_0$
所有组（已知类和测试集）共享一个全局子类分布$G_0$,由Dirichlet过程生成：
$$G_0\mid \gamma ,H\sim \mathrm{DP}(\gamma ,H)$$
其中$H$是基分布（如高斯-威沙特分布）,$\gamma$控制全局子类数量。
全局子类数量$G_j$
每个组$j$已知类或测试集）的子类分布由$G_0$继承
$$G_j\mid {\alpha }_0,G_0\sim \mathrm{DP}({\alpha }_0,G_0)$$
${\alpha }_0$控制组内子类的生成频率，值越大，组内子类越多。

动态子类分配

通过Gibbs采样迭代更新以下变量：
1.测试实例的桌子分配$t_{ji}$:
决定实例属于已有子类还是新子类（公式10）。
2.桌子的菜品分配$k_{jt}$
决定子类继承全局参数还是生成新参数（公式11）。

无需阈值的开放集识别

已知类判定：若测试实例分配到已知类的子类（对应某个${\varphi }_k$），则分类为已知类。
新类发现：若分配到新子类（从$H$生成${\varphi }_{K+1}$），则标记为未知类，并扩展全局子类集合。

1.CD-OSR的核心

CD-OSR将HDP适配到开放集识别场景，主要修改如下：
组定义：每个已知类是一个组，测试集整体作为另一个组。
子类过滤：剔除占比过低的子类，防止过拟合。
分类规则：测试实例分配到已知类的子类则分类为已知类，否则标记为未知类。

2. 训练阶段

1.数据划分：
训练集分为拟合集$\mathcal{F}$和验证集 $\mathcal{V}$，用于参数调优。
训练集：
已知类别的实例集合，每个类别单独分组。 X t r = { X 1 , X 2 , . . . , X J } X_{\mathrm{tr}}=\{X_1,X_2,...,X_J\} Xtr​={X1​,X2​,...,XJ​}，其中$X_j$表示第$j$个已知类的实例集。
测试集：
待分类的实例集合，可能包含已知类和未知类。
X t s = { x 1 , x 2 , . . . , x N } X_{\mathrm{ts}}=\{x_1,x_2,...,x_N\} Xts​={x1​,x2​,...,xN​}
超参数：
HDP的浓度参数：${\alpha }_0$（控制组内子类数量）,$\gamma$(控制全局子类共享程度）。
基分布$H$的参数（如高斯-威沙特分布的${\mu }_0,{\Sigma }_0,\beta ,\nu )$
子类过滤阈值$ϵ$(如$ϵ=0.01$，过滤占比过低的子类)

2.参数初始化：
基分布$H$设为高斯-威沙特分布：
$$H=\mathcal{N}(\mu \mid {\mu }_0,(\beta \Sigma {)}^{-1})\cdot \mathcal{W}(\Sigma \mid {\Sigma }_0,\nu )$$

3.测试阶段

1.测试集作为新组输入
输入形式：
测试集整体被视为一个新的组（称为“Testing-set组”），与训练集的已知类组（如Class 1-4）共同参与共聚类。
作用：
将测试实例的分布与已知类分布对齐，利用全局子类共享机制实现分类。
2.共聚类（Co-clustering）
过程：
使用Gibbs采样对测试集和已知类组进行联合建模，动态分配实例到子类。具体操作包括：
更新桌子分配（公式10）：测试实例可能分配到已知类的子类（已有桌子）或创建新子类（新桌子）。
更新菜品分配（公式11）：新子类继承全局参数或生成新参数。
输出：
测试实例的子类归属，以及全局子类参数的更新。
3.分类决策
规则：
若测试实例分配到已知类组的子类，则分类为该已知类。
若分配到测试集组的新子类（从基分布$H$生成），则标记为未知类
4.新类发现
统计新子类数目：
测试集中新子类的数量反映潜在未知类的存在。例如，若测试集组有5个新子类，可能对应1个未知类（假设每个类有多个子类）。
估计公式：
$$\Delta =\lceil \frac{|S_{\mathrm{unknown}}|}{|S_{\mathrm{known}}|/(J-1)}\rceil$$
其中$|S_{\mathrm{unknown}}|$是测试集的新子类数，$|S_{\mathrm{known}}|$是已知类的子类总数，$J-1$是已知类数量。

图2直观展示了CD-OSR框架在测试阶段的共聚类过程，具体元素如下：

组（Groups）：
已知类组：如Class 1-4，每个类作为独立组，内部包含若干子类（如Class 1有子类A、B）。
测试集组（Testing-set）：作为新组参与聚类，其子类可能部分与已知类共享，部分为新生成。
子类（Subclasses）：
已知子类（Known subclasses）：用实心圆表示，颜色与已知类对应（如Class 1为蓝色）。
新子类（New subclasses）：用不同颜色的圆表示，属于测试集组独有的子类。
共享关系：
无连线的新子类：表示测试集中的未知类（如子类D仅属于Testing-set）。
分类结果示例：
测试实例分配到子类A（属于Class 1）→ 分类为已知类。
测试实例分配到子类D（新子类）→ 标记为未知类。

CD-OSR的伪代码

1.首先对参数进行初始化

1. 输入训练集 X_tr 和测试集 X_ts，按实验协议划分（如Section 4.1.1）。
2. 按类别标签将训练集 X_tr 划分为组：X_tr = [X_tr1, X_tr2, ...]（每个组对应一个已知类）。
3. 初始化参数：
   - 基分布 H 的参数：μ0（训练集均值），Σ0（缩放后的协方差矩阵，公式13），β=1，ν通过网格搜索选择。
   - 浓度参数：α0 ~ Gamma(10,1)，γ ~ Gamma(100,1)。
   - 迭代次数 T = 30，初始子类数 InS = 30。
   - 子类过滤阈值 ε = 0.01。

2.然后进行共聚类

 - 将训练集和测试集合并为输入数据：Data = [X_tr; X_ts]
 - 调用HDP软件包（如Teh的代码）进行共聚类：
   Results = HDP(Data, α0, γ, H, InS, T)
   其中：
 - HDP框架对每个组（已知类和测试集）建模。
 - 迭代T次Gibbs采样，更新子类分配。

Gibbs采样迭代：

• 对每个实例$x_{ji}$，按公式（10）更新桌子分配$t_{ji}$。
• 对每个新桌子$t^{new}$,按公式（11）更新菜品分配。
• 更新全局子类参数${\varphi }_k$ (如高斯分布的均值和协方差)。

作用：
训练集和测试集共同参与聚类，动态分配子类。

测试集的新子类反映潜在未知类。
3.确定子类（Determining the Subclasses）

6. 后处理共聚类结果：
   for 每个组 j 的每个子类 s：
      计算子类 s 在组 j 中的占比 ρ = (子类s的实例数) / (组j的总实例数)
      if ρ < ε：
          移除该子类 s

作用：
过滤掉占比过低的子类（如噪声或离群点），提升模型鲁棒性。

例如，若某子类仅占0.5%的实例（ε=0.01），则被剔除。
4.预测

7. 对新实例 x_new 进行分类：
   a. 将 x_new 加入测试集组，重新运行共聚类（仅更新局部分配）。
   b. 根据分配结果：
      if x_new 的子类属于某个已知类 j 的子类 s：
          标记为类 j
      else：
          标记为未知类，并记录新子类参数
8. 估计未知类数目 Δ（公式14）：
   Δ = ceil(|S_unknown| / (|S_known| / (J-1)))

作用：

新实例的分类基于其子类归属，无需人工设定阈值。

新子类的数量通过全局子类比例估计未知类数目。

结论

本文的主要贡献是提出了一种集体/分批决策的开集识别策略，旨在将现有的开集识别扩展到新的类发现中，同时考虑测试实例之间的相关性。为了实现这一目标，我们将HDP稍作修改以解决OSR问题，从而为OSR中的集体决策提供了初步解决方案。需要强调的是，我们的CD-OSR并不过分依赖于训练数据，并且能够随着数据的变化而实现自适应变化。更准确地说，CD-OSR可以为测试中出现的未知类提供显式建模。这自然会导致新的类发现功能，即使它只是在子类级别。此外，与现有方法从判别模型的角度处理OSR问题不同，CD-OSR实际上是从生成模型的角度来解决这一问题的，这是由于使用了HDP。最后，在一组标准数据集上的实验结果表明了该学习框架的有效性.

此外，应该注意的是，建模未知类只在我们的CD-OSR的测试阶段进行，而在训练阶段没有利用未知类的可用知识。这在某种程度上似乎带有懒惰的味道。因此，克服这一局限性将是未来一个很有前途的研究方向。此外，由于CDOSR目前没有充分利用来自已知类别标签的判别信息，因此更有效地嵌入此类信息也值得进一步探索。此外，用可扩展的确定性推理技术取代Gibbs采样器也是未来工作的一个很有前途的方向。总之，CDOSR只是目前对开集识别向集体决策发展的一个概念性证明。因此，更有效的OSR集体决策方法值得在未来的工作中进一步探索。