【ML Tech RPT. 】第2回 Zero Shot Learning を学ぶ (2)

f:id:ssatsuki040508:20181210005017p:plain
Sansan DSOC研究員の吉村です。前回からMachine Learning技術についての連載をはじめました。今回から、弊社のデザイナーに連載用のヘッダ画像を作っていただき、以前にも増してやる気が出ています。
本記事では前回に引き続きZero Shot Learning (ZSL) を紹介します。今回はZSLで利用される手法についていくつかをピックアップして説明していきます。問題設定やZSLを利用するモチベーションなどについては、下記の第1回の記事で説明したので、先に読んでいただくとより理解しやすいかと思います。
buildersbox.corp-sansan.com

Notation

まずは、本記事で利用する各種記号についての説明をします。なお、今後の説明を容易にするため今回は画像に対して適切なラベルを予測する画像分類のみを対象にすることとします。

画像空間を $\mathcal{X}$ 、ラベル空間を $\mathcal{Y}$ とします。このうち、訓練時に観測されるラベルの空間を $\mathcal{Y}^{\text{train}}$ 、予測対象となるラベルの空間を $\mathcal{Y}^{\text{target}}$ とします。今回は (狭義の) ZSL の問題設定を前提におくため、これらは次の二つの式を満たすこととします。$$\mathcal{Y}^{\text{train}} \cup \mathcal{Y}^{\text{target}}=\mathcal{Y}, \ \ \mathcal{Y}^{\text{train}} \cap \mathcal{Y}^{\text{target}}=\emptyset $$ある画像を $x \in \mathcal{X}$ 、それに対応するラベルを $y \in \mathcal{Y}$ で表現します。この $x$ と $y$ それぞれに対するある分散表現をそれぞれ $D$ 次元の列ベクトル $\theta(x)$ と $E$ 次元の列ベクトル $\phi(y)$ と表現します。ここで述べている「ある分散表現」として、どの分散表現を利用するかについては各手法によるためここでは詳細は述べません。訓練時には訓練データセット $\mathcal{S} = \{(x_i, y_i),\ \ i=1,\cdots, N\}$ が与えられます。ただし、 $N$ は訓練データサンプル数を表します。当然、この各ラベル $y_i$ は $y_i \in \mathcal{Y}^{\text{train}}$ を満たします。

ZSL の各種手法について

ZSLの問題設定では、学習時に観測されなかったラベルを予測時に適切に予測するためのアプローチがいくつかあります。今回はその中でもCompatibility Functionと呼ばれる「画像の分散表現とラベルの分散表現を結びつけるための線形写像」を学習するアプローチを採る手法について説明していきます。このアプローチをとる手法のうち SOC [*1], DeViCE [*2], SAE [*3] の3つについて今回は紹介します。

SOC (Semantic Output Codes)

SOC では各ラベルを表現する意味空間 $\mathcal{F}$ を考えます。この意味空間は何らかのナレッジベースから構成されます。この意味空間上のベクトルは例えば「このラベルが表現するものの色は何か」、「このラベルが表現するものは動物であるかどうか」などの情報を各要素に持ちます。

SOC では $f : \mathcal{X} \rightarrow \mathcal{Y}^{\text{target}}$ となる分類器 $f$ を2段階の最適化問題に分けることで学習します。First Stage では画像 $x$ を入力として、意味空間上のベクトルを出力する分類器 $\mathcal{f_1} : \mathcal{X} \rightarrow \mathcal{F}$ を学習します。Second Stage では意味空間上のベクトルを入力として、Fisrt Stage で入力した画像 $x$ に対応するラベル $y$ を出力する分類器 $\mathcal{f_2} : \mathcal{F} \rightarrow \mathcal{Y}$ を学習します。これら二つの分類器 $f_1$ と $f_2$ を組み合わせることで分類器 $f$ が得られます。 [M. Palatucci et al., 2009] では $f_1$ に線形変換を用い、 $f_2$ に1-NN (k近傍法のk=1の場合) を利用しています。First Stage と Second Stage とはいずれも訓練データセット $\mathcal{S}$ と各ラベルに対応する意味空間上のベクトルが与えられているものとして学習されます。

[M. Palatucci et al., 2009] では意味空間上の属性表現ベクトルを得る方法を2通り提案しています。一方が Google Trillion-Word Corpus を基に頻出単語の共起関係を利用して分散表現を学習する方法で、もう一方が全てのラベルに対して「そのラベルが表現するものは(手に)持てるか否か」、「そのラベルが表現するものは人工物か否か」などの特徴を人力により付与する方法です。後者は、特徴を付与するタスクを Amazon Mechanical Turk でクラウドワーカに依頼しています。

DeViSE (Deep Visual-Semantic Embedding)

f:id:ssatsuki040508:20181213105640p:plain — DeViSE Model の説明図

DeViSE は画像の分散表現と単語の分散表現を組み合わせることで ZSL に対応する手法です。

画像の分散表現は事前に学習しておく必要があり、訓練データ $\mathcal{S}$ を用いて画像分類用にニューラルネットワークを学習した後、出力層を取り除くことで画像から埋め込み空間への写像 $\theta$ を得ます。単語の分散表現としてはword2vec を利用します。[A. Frome et. al., 2013] の中では wikipedia.org から抽出したコーパスを用いて単語 (ラベル) から埋め込み空間への写像 $\phi$ を学習しています。

次に、こうして得られた二つの写像をそれぞれ画像とラベルに適用することで得られる分散表現 $\theta(x)$ と $\phi(y)$ とを同じ埋め込み空間で比較できるようにするために $E \times D$ の線形写像 $W$ を考えます。この線形写像を用いて画像の分散表現を単語の埋め込み空間へ写像した $W\theta(x)$ と単語の分散表現 $\phi(y)$ との類似度をドット積 $\phi(y)^{\top}W\theta(x)$ で定義します。ただしこの時、 $\phi(y)$ は単位ベクトルになるように事前に正規化がなされていることに注意してください。学習時には画像の分散表現と対応するラベルの分散表現との類似度が大きくなり、誤ったラベルの分散表現との類似度が小さくなるように最適化を行います。そのための損失関数 $loss(x, y)$ が次のものになります。$$loss(x, y) = \sum_{y_j \neq y} \max[0, M - \phi(y)^{\top}W\theta(x)+\phi(y_j)^{\top}W\theta(x)]$$予測時には新たな入力画像 $x$ の分散表現を単語の埋め込み空間へ写像した $W\theta(x)$ にk近傍法を適用し、最適な $y \in \mathcal{Y}^{\text{target}}$ を選択することでラベルの予測を行います。

SAE (Semantic AutoEncoder)

f:id:ssatsuki040508:20181213142437p:plain — SAE Model の説明図

SAEは画像に対して潜在変数がラベルの分散表現と一致するようなAutoEncoderを学習する手法です。SAEでは入力層と出力層の他に潜在変数の層が一つのみのオートエンコーダを想定しています。画像 $x$ から何らかの方法 (e.g. GoogLeNetの最終プーリング層の出力からなど) で抽出した visual features を表す列ベクトルを $\bf{x}$ で表します。この時、SAEの Encoder 部分はある射影 $W$ による変換として表すことができ、Decoder 部分はある射影 $W^*$ によって $W^*\bf{x}$ の変換として表すことができます。 [E. Kodirov et al., 2017] ではモデルの簡略化のため $W^* = W^{\top}$ という制約を課しています。

この Encoder 部分の射影先がラベルの潜在意味空間 (e.g. $k$ 次元の属性ベクトル空間) となるように学習をします。また、当然 AutoEncoder であるため、Encoder で射影したものを Decoder で再び射影して元に戻す必要があるため、最終的に学習時に解くべき目的関数は下記のようになります。$$\min_{W}\|X-W^{\top}S\|^2_F + \lambda \|WX - S\|^2_F$$ただし、 $X$ は各訓練画像に対応する visual features を表す列ベクトルを並べた行列を、 $S$ は各画像に対応するラベルを表す潜在意味空間上の列ベクトル $\bf{s}$ を並べた行列を表します。この目的関数は $W$ による微分が容易であり、微分した値が0となるような等式を立てると最終的に次の等式が得られます。$$(SS^{\top})W+W(\lambda XX^{\top})=(1+\lambda) SX^{\top}$$この等式は $SS^{\top}=A$ 、 $\lambda XX^{\top}=B$ 、 $(1+\lambda) SX^{\top}=C$ とすれば、Sylvester 方程式としてよく知られる $$AW+WB=C$$の形にすることができるため、効率的に解を求めることができます。こうして元の目的関数の最適解を求めます。

予測時には、入力として与えられる画像 $x$ の visual features を表す列ベクトル $\bf{x}$ を学習によって得られた射影 $W$ で、ラベルの潜在意味空間上の点として表すことで、その点の近傍のラベルを予測ラベルとして得ることができます。

まとめ

今回は、SOC, DeViSE, SAE の三つについて紹介しました。この他にも似たアプローチの手法として SJE [*4] や ALE [*5]、そして、ESZSL [*6] などがあります。今回紹介した手法は、いずれも画像の分散表現とラベルの分散表現を線形変換で同じ埋め込み空間上で扱えるようにするというアイデアに基づくものでした。今回の記事で、読者のみなさまの ZSL に対する基本的なアプローチについての理解が深まっていれば幸いです。また、私としては (公開するかどうかは別としても) 学んだ手法については時間を見つけて少しずつ実装してみようと思います。

次回は今回とは異なるアプローチの手法について紹介します。

*1:M. Palatucci, D. Pomerleau, G. Hinton, and T. M. Mitchell, "Zero-Shot Learning with Semantic Output Codes," in NIPS, 2009.

*2:A. Frome, G. S. Corrado, J. Shlens, S. Bengio, J. Dean, M. A. Ranzato and T. Mikolov, "DeViSE: A Deep Visual-Semantic Embedding Model," in NIPS, 2013.

*3:E. Kodirov, T. Xiang, and S. Gong, "Semantic autoencoder for zero-shot learning," in CVPR, 2017.

*4:A. Akata, S. Reed, D. Walter, H. Lee, and B. Schiele, "Evaluation of Output Embeddings for Fine-Grained Image Classification," in CVPR, 2015.

*5:Z. Akata, F. Perronnin, Z. Harchaoui, and C. Schmid, "Label-Embedding for Attribute-Based Classification," in CVPR, 2013.

*6:B. Romera-Paredes and P. H. Torr, "An embarrassingly simple approach to zero-shot learning," in ICML, 2015.