(57)【要約】【課題】【解決手段】距離メトリック学習のための方法およびシステムは、ｍがｄより小さいとしたとき、ｄ次元空間からｍ次元部分空間へのデータセットの２つのランダムプロジェクション行列を生成することを含む。ランダムプロジェクション行列に基づく距離メトリックを学習するためにｍ次元部分空間において最適化問題が解かれる。ｄ次元空間において距離メトリックがリカバリされる。【選択図】図１
2017504130.tif 000002
【特許請求の範囲】
【請求項１】
ｍがｄより小さいとしたとき、ｄ次元空間からｍ次元部分空間へのデータセットの２つのランダムプロジェクション行列を生成する工程と、
前記ランダムプロジェクション行列に基づく距離メトリックを学習するために前記ｍ次元部分空間において最適化問題を解く工程と、
前記ｄ次元空間において前記距離メトリックをリカバリする工程と、
を有する距離メトリック学習のための方法。
【請求項２】
前記生成する工程、前記解く工程及び前記リカバリする工程が、反復して実行される請求項１に記載の方法。
【請求項３】
各反復工程において、１エポックのみのトリプレットが選択される請求項２に記載の方法。
【請求項４】
前記最適化問題を解く工程では、前記ｍ次元部分空間において確率的勾配降下法を実行する請求項１に記載の方法。
【請求項５】
前記最適化問題を解く工程では、前記ｍ次元部分空間において双対変数を計算する請求項１に記載の方法。
【請求項６】
Ｓｍが前記ｍ次元部分空間であり、
【数１】
2017504130.tif 000020
が前記ｍ次元部分空間におけるメトリックであり、
【数２】
2017504130.tif 000021
がフロベニウスノルムであり、λが正則化項
【数３】
2017504130.tif 000022
に対する重みであり、ｌ（．）が任意の平滑化凸損失関数であり、＜・，・＞が２つの行列の内積であり、Ｎがトリプレットの数であり、
【数４】
2017504130.tif 000023
が第ｔ双対変数であるとき、前記最適化問題は、
【数５】
2017504130.tif 000024
である請求項１に記載の方法。
【請求項７】
前記距離メトリックをリカバリする工程では、元の空間におけるメトリック全体を格納することを回避するためにランダム化手法により低ランクの近似を得る請求項１に記載の方法。
【請求項８】
ｍがｄより小さいとしたとき、ｄ次元空間からｍ次元部分空間へのデータセットの２つのランダムプロジェクション行列を生成するように構成されたプロジェクションモジュールと、
前記ランダムプロジェクション行列に基づく距離メトリックを学習するために前記ｍ次元部分空間において最適化問題を解くように構成されたプロセッサと、
前記ｄ次元空間において前記距離メトリックをリカバリするように構成されたメトリックリカバリモジュールと
を有する距離メトリック学習のためのシステム。
【請求項９】
前記プロジェクションモジュール、前記プロセッサ及び前記メトリックリカバリモジュールが、反復して動作するように構成された請求項８に記載のシステム。
【請求項１０】
各反復の工程において、１エポックのみのトリプレットが選択される請求項９に記載のシステム。
【請求項１１】
前記プロセッサが、前記ｍ次元部分空間において確率的勾配降下法を用いて前記最適化問題を解くように構成された請求項８に記載のシステム。
【請求項１２】
前記プロセッサが、前記ｍ次元部分空間において双対変数を計算することで前記最適化問題を解くように構成された請求項８に記載のシステム。
【請求項１３】
Ｓｍが前記ｍ次元部分空間であり、
【数６】
2017504130.tif 000025
が前記ｍ次元部分空間におけるメトリックであり、
【数７】
2017504130.tif 000026
がフロベニウスノルムであり、λが正則化項
【数８】
2017504130.tif 000027
に対する重みであり、ｌ（．）が任意の平滑化凸損失関数であり、＜・，・＞が２つの行列の内積であり、Ｎがトリプレットの数であり、
【数９】
2017504130.tif 000028
が第ｔ双対変数であるとき、前記最適化問題が、
【数１０】
2017504130.tif 000029
である請求項８に記載のシステム。
【請求項１４】
前記メトリックリカバリモジュールが、元の空間におけるメトリック全体を格納することを回避するためにランダム化手法により低ランクの近似を得ることで、前記距離メトリックをリカバリするように構成された請求項８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この出願は、２０１３年１０月２９日に出願された米国特許仮出願第６１／８９６７００号及び２０１４年７月３０日に出願された米国特許仮出願第６２／０３０６７８号を基礎とし、その開示の全てをここに取り込む。
本発明は詳細画像識別のための効率的な距離メトリック学習に関する。
【背景技術】
【０００２】
詳細画像識別（ＦＧＶＣ：Fine-Grained Visual Categorization）は、コンピュータビジョンの研究において近年提案されたものである。ＦＧＶＣでは、従来の画像分類と比較して、クラスが互いに非常に類似しており、人の視覚でもそれらを一目見ただけでは正しく分類できるとは限らないことを想定している。この問題は、例えば猫、犬、鳥、飛行機、花等の種別を認識するための、多くの実世界の分類アプリケーションにおいて発生する。
【０００３】
ＦＧＶＣのためのほとんどの既存の手法は、従来の画像特徴ではなく、領域知識を伴う詳細クラスから与えられる具体的な特徴を抽出することに依存している。これらの方法は、全て１対全（one-vs all）の線形サポートベクターマシン（ＳＶＭ）を最終的な分類器に用いて、それらの領域における良好な性能を実現している。特徴学習（feature learning）は非常に注目されているが、線形ＳＶＭを直接用いる代わりにＦＧＶＣの方法論を発展させようとする者は実際にはほとんどいなかった。
【０００４】
線形ＳＶＭは、高次元の分類タスクには効率的であるが、カーネルＳＶＭほど効果的ではなく、よく抽出された特徴から十分に情報を探る保証ができない。さらに、線形ＳＶＭ及びカーネルＳＶＭは、共に大部分の詳細データセットが、低次元表現を意味する低ランクとなる可能性があり、該データセットに十分な特性を実現できない。それは、経済的なストレージ及び画像検索には重要であり、次元が低いほど近傍の検索が良好となる。
【発明の概要】
【０００５】
本発明の距離メトリック学習のための方法は、ｍがｄより小さいとしたとき、ｄ次元空間からｍ次元部分空間へのデータセットの２つのランダムプロジェクション（random projection）行列を生成することを含む。ランダムプロジェクション行列に基づく距離メトリックを学習するためにｍ次元部分空間において最適化問題が解かれる。また、ｄ次元空間において距離メトリックがリカバリされる。
【０００６】
本発明の距離メトリック学習のためのシステムは、ｍがｄより小さいとしたとき、ｄ次元空間からｍ次元部分空間へのデータセットの２つのランダムプロジェクション行列を生成するように構成されているプロジェクションモジュールを含む。プロセッサは、ランダムプロジェクション行列に基づく距離メトリックを学習するためにｍ次元部分空間において最適化問題を解くように構成されている。メトリックリカバリモジュールは、ｄ次元空間において距離メトリックをリカバリするように構成されている。
【図面の簡単な説明】
【０００７】
【図１】図１は、本原理による距離メトリックを学習するための方法のブロック図／流れ図である。
【０００８】
【図２】図２は、本原理による距離メトリックを学習するためのシステムのブロック図である。
【発明を実施するための形態】
【０００９】
本実施形態では、高次元な詳細画像分類のための距離メトリック学習を提供する。高次元に関する問題を扱うため、２つのランダムプロジェクションを用いてデータセットを低次元部分空間に射影する。この場合、確率的勾配降下法（ＳＧＤ：Stochastic Gradient Descent）を用いて問題を効率的に解いてもよい。低次元部分空間におけるメトリックを報告するランダムプロジェクションとは異なり、学習された距離メトリックにより双対変数が推定され、最終的なメトリックがそれらによって元の空間で再構成される。
【００１０】
本実施形態では、同じラベルの画像を近づけ、異なるラベルの画像を遠ざけるマハラノビス距離メトリックを学習する距離メトリック学習（ＤＭＬ：Distance Metric Learning）を用いる。学習されたメトリックがおよぶ新たな空間における類似度は、元の空間におけるユークリッド距離から得られる類似度よりもはるかに良好である。これにより、より良好な分類性能がもたらされ、ランク表現がデータセットにとって十分である場合に、学習されたメトリックのランクが低く維持される。本実施形態では、ＤＭＬに対してランダムプロジェクションを２度用いることで該プロジェクションを不偏にする。メトリックは、ランダムプロジェクション空間において、確率的メトリック学習法により学習される。学習されたメトリックにより双対変数を推定した後、本実施形態では元の空間において低ランクのメトリックがリカバリされる。この処理は反復的であり、トリプレット（triplet）の制約条件の数は、各反復工程におけるデータセットの数に比例する。これにより、学習処理がより効率的になる。
【００１１】
ここで図１を参照すると、高次元メトリック学習のための方法が示されている。ブロック１０２は、２つのランダムプロジェクションを示す、モデルを不偏で維持するための２つのランダム行列Ｒ１及びＲ２を生成する。これは、ランダムプロジェクションを１つしか用いないため、メトリック学習において不偏性を保つことができない従来の方法とは対照的である。ブロック１０４では、１エポック（epoch）分のトリプレットをランダムにサンプリングする。制約条件の数は、データサンプル数ｎに比例する。これもまた、最適化のためにｎ３個の制約条件を用いる従来の手法とは対照的である。
【００１２】
ブロック１０６では、ＳＧＤを実行し、２つのランダムプロジェクションを用いてランダムプロジェクションメトリックを学習する。ブロック１０８では、学習された距離メトリックにより双対変数を計算し、続いてブロック１１０では、学習されたメトリックが元の空間においてリカバリされる。ブロック１１０におけるメトリックのリカバリには、リカバリングの常套手段にしたがって低ランクの近似を得るためのランダム化手法を用いることを含む。これにより、元の空間におけるメトリック全体を保持することが回避される。
【００１３】
ブロック１１２では、各反復工程における１エポックのアクティブな制約条件をランダムに選択する。ブロック１１４では、停止基準（criteria）にしたがって処理が収束したかを判定する。収束した場合は処理を終了する。収束していない場合はブロック１０６の処理に戻って、処理をさらに繰り返す。停止基準は、アクティブな制約条件の数が訓練例（training example）の数の半分未満であるとすればよい。
【００１４】
画像データセット
【数１】
2017504130.tif 000003
が与えられると、２つの画像ｘｉとｘｊの間の２乗マハラノビス距離はｄｉｓ（ｘｉ，ｘｊ）＝（ｘｉ−ｘｊ）ＴＭ（ｘｉ−ｘｊ）と定義される。ここで
【数２】
2017504130.tif 000004
は距離メトリックである。一例を挙げれば、距離メトリックＭは、Ｍが単位行列であるとき、ユークリッド距離となる。距離メトリック学習は、任意のトリプレット（ｘｉ，ｘｊ，ｘｋ）に対して、ｘｉ及びｘｊが同じラベルを共有し、ｘｋが異なるラベルを有する場合、（ｘｉ−ｘｊ）ＴＭ（ｘｉ−ｘｊ）＋１≦（ｘｉ−ｘｋ）ＴＭ（ｘｉ−ｘｋ）となるように、良好な距離メトリックＭを学習しようとする。距離メトリック学習のターゲットは、最適化問題：
【数３】
2017504130.tif 000005
と書くことができる。ここで、Ｓｄはｄ×ｄ実対称行列を表し、
【数４】
2017504130.tif 000006
であり、
【数５】
2017504130.tif 000007
はフロベニウスノルムであり、Ｎはトリプレットの総数であり、Ａｔは第ｔトリプレットを示し、＜・，・＞は２つの行列の内積である。Ｓｄから学習された行列は、最適化の最後に半正定値（ＰＳＤ：Positive Semidefinite）錐に射影する。ｌ（．）は、任意の平滑化凸損失関数である。
【００１５】
この最適化問題は、行列のサイズが極端に大きい場合に解くのが困難である。それをメモリに格納できるとしても、勾配ベース（gradient-based）法で解くにはステップ毎にＯ（ｄ２）の計算コストを要する。
【００１６】
２つのランダムプロジェクションを用いることで、ランダムプロジェクションがおよぶ低次元空間における双対変数が推定され、双対変数を用いて元の空間において解がリカバリされる。ブロック１０２から２つのランダム行列Ｒ１及びＲ２が与えられると、Ａｔを
【数６】
2017504130.tif 000008
として低次元空間に射影する。このとき双対問題は：
【数７】
2017504130.tif 000009
となる。ここで、
【数８】
2017504130.tif 000010
であり、λは正則化項（regularizer）
【数９】
2017504130.tif 000011
の重みであり、αは全ての双対変数のベクトルであり、αｔはαの第ｔ要素であって第ｔトリプレットに対する双対変数でもあり、
【数１０】
2017504130.tif 000012
は行列であり、ｌ＊（αｔ）は平滑化凸損失関数の複素共役である。
【００１７】
この双対問題を解くことは、最適化中に全ての双対変数を保持していることを意味する。しかしながら、双対変数の数はトリプレットの数に対応し、Ｏ（ｎ３）である。そのような多数の双対変数を最適化することを回避するため、主問題をランダムプロジェクション：
【数１１】
2017504130.tif 000013
を用いて解く。この場合、低次元メトリック
【数１２】
2017504130.tif 000014
を使用し、Ｏ（ｍ２）の変数のみを最適化することになる。解を得た後、双対変数を推定し、該双対変数を用いて元の空間で解がリカバリされる。
【００１８】
大きいデータセットについてはＳＧＤでも時間がかかる。これはトリプレットの数がＯ（ｎ３）のままのためである。他方、アクティブな制約条件のみが損失関数の勾配に影響を与える。したがって、本処理をブーストするために反復手法を用いる。各反復工程において、ＰＳＤメトリックが元の空間で再構成され、アクティブな制約条件がそれにしたってサンプリングされる。この問題は、低次元部分空間において新たな制約条件で再度解かれる。第ｓ反復工程における最適化問題は：
【数１３】
2017504130.tif 000015
となる。ここで、
【数１４】
2017504130.tif 000016
は低次元空間における前回の反復工程で得られた解である。この問題はＳＧＤにより解かれ、平均結果が返される。第ｓ反復工程における最適化問題は、
【数１５】
2017504130.tif 000017
と等価である。ここで、γは定数であり、
【数１６】
2017504130.tif 000018
は、偏差を無視できるように通常はγより大きい。
【００１９】
高次元行列Ｍのリカバリは、
【数１７】
2017504130.tif 000019
で求めることができる。ここで、Ｃは各トリプレット（ｘｉ，ｘｊ，ｘｋ）に対する疎行列であり、Ｃ（ｉ，ｊ）＝−α、Ｃ（ｊ，ｉ）＝−α、Ｃ（ｊ，ｊ）＝α、Ｃ（ｉ，ｋ）＝α、Ｃ（ｋ，ｉ）＝−α、Ｃ（ｋ，ｋ）＝−αである。ｄ×ｄ行列Ｍは、ｄ×ｎ行列Ｘ及びｎ×ｎ行列Ｃで表される。大規模問題ではｎがｄを超える場合があるが、データセットを分散して保持し、効率的に並列して演算することが好都合である。疎行列Ｃの要素数はｎ×ｓである。ここで、ｓは反復回数であり、通常は６０未満である。上記の表現に基づき、Ｍの固有分解（eigen-decomposition）を実行するために、べき乗法が用いられる。
【００２０】
ここで図２を参照すると、高次元メトリック学習のためのシステム２００が示されている。ハードウェアプロセッサ２０２は、高次元分類空間にわたる詳細画像分類等のためのメトリックを学習するために使用される。メモリ２０４には、多数の次元にわたって比較される画像を特徴付けるデータセットが格納される。プロセッサ２０２は与えられた２つの画像間の距離を決定する。これを実現するため、プロジェクションモジュール２０６を用いてデータセットを低次元空間に射影することで、メトリックが学習される。ＳＧＤモジュール２０８は、プロセッサ２０２を用いて、低次元空間においてメトリックの解を決定する。また、メトリックリカバリモジュール２１０を用いて、メトリックが高次元空間でリカバリされる。
【００２１】
上記は、あらゆる観点において例示的（illustrative）かつ典型的（exemplary）であって限定的でないものと理解されるべきであり、本明細書に開示の本発明の範囲は詳細な説明から決定されるべきではなく、特許法により許容される全範囲に従って解釈される特許請求の範囲から決定されるべきである。追加情報は、本出願の付属書類Ａ（Appendix A）に与えられている。本明細書で示され説明された実施形態が本発明の原理の例示にすぎず、当業者が本発明の範囲および趣旨から逸脱することなく様々な修正を実施できることは理解されたい。当業者は、本発明の範囲および趣旨から逸脱することなく様々な他の特徴の組合せを実施できる。
【図１】
2017504130.tif 000030
【図２】
2017504130.tif 000031
【国際調査報告】
2017504130.tif 000032
2017504130.tif 000033