論文メモ Zero-Shot Learning with Semantic Output Codes

May 23, 2020

学習データにないラベルを推定する問題に対してzero-shot leanringと名づけ、ラベルを推定できる確率と条件を形式化した論文である。形式化するモデルは、複数の二値分類器と1つの最近傍探索器からなる。最近傍探索は、2値分類器の出力を要素とするベクトルをうけとり、最近傍のラベルに対応するベクトルを探す。 PACフレームワークにもとづく必要な学習データの件数を示し、そのデータで訓練されたモデルが学習データにないラベルを推定できる確率を示した。

$X^d$上の$d$次元のベクトルを入力とする$p$個の二値分類器があり、ラベルの集合が$Y$として、モデル$\mathcal{H}$を次のように表記する。

$$ \begin{align} \mathcal{H} &= \mathcal{L}(\mathcal{S}(\cdot)) \\ \mathcal{S} &: X^d \rightarrow F^p \\ \mathcal{L} &: F^p \rightarrow Y \end{align} $$ 学習データには、$X^d$と$F^p$上のベクトルの組をもちいる。 $p$個の二値分類器をもちいるので、$F^p$上の任意のベクトルの要素は$0$か$1$をとる。推定時は、1対1の関係にある$F^p$と$Y$上のM個のベクトルの組$\{f, y\}_{1:M}$のうち、二値分類器の出力のベクトルに最も近い$f$の$y$をラベルとして出力する。

はじめに、$\mathcal{L}$について、$1-\gamma$の確率で$F^p$上の点に対応する真のラベルを復元できる場合を考える。 $q$を$F^p$上の点、$q$とその最近傍との距離を$\eta_q$, 距離をハミング距離として、最近傍の点との距離が$z$以下である確率分布を$G_q(z)$とおく。 $$ G_q(z)=\mathbb{P}(\eta_q\le z) $$ また、$q$の真のラベルに対応する$F^p$上の点との距離を$\tau_q$とおき、探索のときに真のラベルと異なるラベルを推定する確率を$\gamma$とおくと $$ G_q(\tau_q)\le\gamma $$ という関係がなりたつ。 $G_q(\cdot)$は単射ではないものの、累積分布関数であるため $$ G_q^{-1}(\gamma) = \text{argmax}_{\tau_q}\left[G_q(\tau_q)\le\gamma\right] $$ とおくと、$\tau_q\le G_q^{-1}(\gamma)$のとき$1-\gamma$の確率で$F^p$上の点を真のラベルに復元できる。

次に、$\tau_q\le G_q^{-1}(\gamma)$になる確率を考える。最近傍探索にはハミング距離をもちいるため、求める確率は、試行回数を$p$、エラー回数を$G_q^{-1}(\gamma)$, エラー率を$G_q^{-1}(\gamma)/p$とする累積二項分布であつかえる。したがって、予測を誤る二値分類器の数が高々$G_q^{-1}(\gamma)$になる確率は

$$ \text{BinoCDF}(G_q^{-1}(\gamma);p,G_q^{-1}(\gamma)/p) $$ となる。

最後に、各分類器のエラー率が$G_q^{-1}(\gamma)/p$となるため必要な学習データの数を求める。 PACフレームワークしたがうと、次の$M_{q,\delta}$個の学習データがあれば、求めるエラー率の条件をみたす二値分類器を$1-\delta$の確率で学習できる。 $$ M_{q, \delta}\ge \frac{p}{G_q^{-1}(\gamma)}\left[4\log(2/\delta)+8(d+1)\log(13p/G_{q}^{-1}(\gamma))\right] $$

以上より、学習データないラベルを推定できる確率は、$\gamma$と$\delta$をもちいて、 $$ (1-\gamma)^p\cdot\text{BinoCDF}(G_{q}^{-1}(\gamma);p,G_q^{-1}(\gamma)/p)\cdot (1-\gamma)) $$ と表せる。

論文をこちらからダウンロードできます。