Coda

論文メモ 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)) $$ と表せる。