デンソーアイティーラボラトリの佐藤育郎（@ikuro_s）です．初めて投稿します．よろしくお願いします．

つい先日，Computer Vision分野の国内会議で口頭発表を行い，ありがたい賞を頂きました．この発表についてちょっと書いてみます．

参加した会議はMIRU2013，発表論文のタイトルは”Sparse Isotropic Hashing”，頂いた賞はMIRU長尾賞（ながおしょう）です．

■ MIRU (http://cvim.ipsj.or.jp/miru2013/index.php)とは

Meeting on Image Recognition and Understandingの略で，Computer Visionの分野では，国内で最もアカデミックよりの発表が行われる会議です．大学の先生の参加率が高く，学生さんにとっては良い発表練習の場，企業研究者にとっては良い情報収集の場となっています（「学生さん」と「企業研究者」を入れ替えてもいいとは思いますが）．ぼくも毎年参加しています．

■ 発表論文 “Sparse Isotropic Hashing” (https://www.jstage.jst.go.jp/browse/ipsjtcva)

前提知識として，実数の特徴量をバイナリコード化する理由を説明します．バイナリコード化の最大の理由は，データ点間の類似度計算の高速化にあります．フムフム．ではなぜ高速になるかというと，バイナリコード間の類似度（ハミング距離）は論理演算とビットカウントのみで求められるためです．

こういった恩恵は（てきとうな）バイナリコード化によって大なり小なり得られます．では我々の論文のさらなるねらいは何かというと，

① 元の特徴量間の類似度をできるだけ保存しつつビット長を短くする

② バイナリコーディング自体を高速化する

です．①の研究は世の中にたくさんあります．例えばITQ (Gong et al, 2011)やIsotropic Hashing (Kong et al, 2012)といった手法があって，マッチング性能が良いことが知られています．②については，例えばVery Sparse Random Projection (Li et al, 2006)といった手法があって，計算負荷がとても低くなっています．しかし，①と②を両方とも高いレベルで，となるとそうなかなか良い手法は見当たりません．

なんとか両者を高いレベルで実現する手段はないものでしょうか？ヒントは，性能が良いと言われているIsotropic Hashing (IsoHash)が内包する本質的な問題に気付いた時に見つかりました．その問題とは

“underconstrainedness” = 「制約不足」

です．つまり，IsoHashが解いている問題は未知パラメタの個数に対して方程式の個数が少ないのです．したがってIsoHashの厳密解は無限個存在し，そのアルゴリズムは無限個存在する解のうちのひとつを無作為に選択しているのにすぎないわけです．

しめた！と思いました．IsoHashに②に関する条件を追加してやればよいのです．②の条件には変換行列のスパース化（L1正則化）が妥当でした．IsoHashは著しく制約が不足しているので，IsoHashの解でありながら変換行列のL1ノルムを充分に低くする解が見つかると考えるのは自然です．探索空間はとてもとても広いのですから．

実験結果はこの仮説を補うものでした．これによって，我々はビット長が充分短いながらもマッチング性能が良く，かつバイナリコーディングが高速なハッシュ関数を手にすることが出来ました．

テクニカルな部分では，回転群のパラメタ空間でコスト関数を定式化し，一次微分を計算して微小角の更新を行うという方法をとっています．これはIsoHashの提案している方法とは次元が異なります（っていうと偉そうに聞こえますね．けどまあ探索空間は全く別物です）．また，我々の方法を使えばIsoHash自体を解くことも容易になります．受賞の理由は，理論的にすっきりした定式化／解法にあるとぼくは思っています．

■ 賞について

MIRU長尾賞はMIRUの最優秀論文賞です．MIRU長尾賞を受賞したことについて，何よりもまず第一に，とてもとても嬉しいです．次に，本当に畏れ多いです．正直，ぼくの現在の実力はこの賞に遠く届いていないと思います．今回の受賞は運の要素が例年よりもかなり高かったように思います．

一発屋と言われないように今後も精進したいと思います．面白い問題を見つけて，同僚と無心に語り合い，理論を組み立て，定式化し，実装し，実験し，卵白がきれいなメレンゲに変化するごとく，アイデアを良い方向に膨らませていきたいと思います．

（p19のムービは再生できないっぽいです）

記事一覧へ