Comments
Description
Transcript
情報源を再構成できる独立成分の抽出とその工学的応用
04―01029 情報源を再構成できる独立成分の抽出とその工学的応用 代表研究者 松 山 泰 男 早稲田大学理工学部教授 共同研究者 勝 又 尚 人 早稲田大学理工学部助手 あらまし この研究は，情報源を独立成分の合成として表す方式を開発し，情報処理を主体とした工学的諸問題に応用す ることを目指したものである。今回の研究助成により，次のような成果が得られた。 ¸ 時系列として表せる任意の情報源を独立な成分に分解する方法として，一般化された尤度に基づく手法を 確立した。 ¹ 静止画像を主成分分析により前処理した後，独立成分分析を行うと，少ない情報量で良好な画像再生を行 える。このとき，独立成分による基底は特徴量として扱えるので，類似画像の検索が可能となる。これによ り，画像圧縮と検索の両者に役立つ方式とフォーマットを得ることができ，これを RIM（Retrievable Image format）と名付けた。 º 離散記号からなる系列に対して，独立成分への分解を適用する方式を開発した。離散記号系列として "A, T, G, C, の４記号からなる DNA 配列は，生命情報を保持していて特に高い価値をもっており，この分 野に独立成分分析を導入できたことは意義深い。方法としては，相同配列を用いて記号の頻度をとり，それ を独立成分に分解するという方式をとっている。性能としては，ヒトのプロモーターの検出において，従来 手法をしのぐスコアを得ている。 1 はじめに 順序系列として表させる情報源，すなわち観測信号は，実はいくつかの隠れた信号の合成であるという場合が 多い。例えば，静止画像はラスタースキャンにより順序系列になるが，そのほとんどは本当の画像の部分とそう でない雑音の重ね合わせである。時系列になっている音声や音楽はもちろんそのようになっている。このように， われわれが観測できる情報源は常に何かの混成物になっている。この研究では，その混成を作り上げる素はいく つかの隠れた成分であり，それらは単なる雑音の他に意味のあるパターンとなっている場合を想定している。そ して，このような各成分は互いに無相関であるか，さらには独立であるという仮定を置くことにする。各成分が 無相関であると仮定する場合は主成分分析（PCA, Principal Component Analysis）とよばれ，さらに独立であ るという仮定を置く場合は独立成分分析（ICA, Independent Component Analysis）とよばれている。この研究 では，両者を用いている。この，ICA においては，研究代表者が開発した一般化尤度に基づく方法を用いてい る。 PCA や ICA は対象とする情報源の物質的実態に依存しないアルゴリズムであり，広汎適用性を有している。 この研究では，静止画像と DNA 配列と主な対象とした。その結果，次のような新規な結果を得ることができた。 ¸ 静止画像を成分分解して情報圧縮することにより，JPEG よりも高い圧縮率を得ることができた。そして さ ら に ， JPEG よ り 優 れ た 性 能 を 保 っ た ま ま ， 類 似 画 像 検 索 を 行 え る 形 式 を 作 成 し ， こ れ を RIM （Retrievable IMage format）と命名した。 ¹ 今までに PCA や ICA の対象となった順序系列は，すべて連続値である。そこで，この研究では，離散 記号からなる配列についての手法を開発した。そして，検査対象としては，"A, T, G, C, の配列となってい るヒトゲノム中のプロモーター検出を行った。その検出性能は，従来法をしのいでいる。 ― 426 ― 2 2.1 主成分分析と独立成分分析 主成分分析 この研究で用いた PCA は次のようなものである。まず，分解の対象とするデータをベクトル x とする。モノ クロ画像の場合，これは，m×m のピクセルからなるパッチであり，カラー画像の場合には 3×m×m 次元とな る。 正規化の第一段として，データは次のようにして平均値を引いておく。 x ! x - E 5 x? = x - n ¸ このとき，平均値 n は，サンプル値を用いて，次のように近似される。 n= 1 N ! N i = 1 X 5i? ¹ 次に，共分散行列を計算し，その固有値を求める。 C = E 8 xx T B º そして，大きい順に最初の L 個の固有値を選び，対角行列 D を作る。また，各固有値に対応する固有ベクトル を求め，それを並べて E 行列を作る。これにより，PCA 圧縮行列を次のように構成できる。 V = D- 1 2 » ET そうすると， ¼ z = Vx が PCA による次元圧縮済みデータとなる。このとき， E 8 zz T B = I ½ が成り立つので，白色化が行われている。そして，圧縮された情報源からの原データの回復は，次のようになる。 ¾ xr = V - 1 z = U PCA z このとき，U PCA 中の各縦ベクトルは，PCA の基底ベクトルとみなされる。そして， xr を単に x と再表現し，記 号の煩雑化を避けることにする。 2.2 独立成分分析 独立成分分析においては，情報源 x は ¿ x = As = j h であり，行列 A も未知である。 と表される。ここに s は未知の成分ベクトルであり，s i と s j は互いに独立 ^i Y 独立成分分析の目的は，次のような分解行列 W を， A - 1 の推定値として得ることである。 sr = Wz À xr = U ICA sr Á これを， と表し，U ICA の縦ベクトルを ICA の基底とみなす。そしてこの場合においても， xr を単に x と再表現し，記号 の煩雑化を避けることにする。 U ICA を得るための独立成分分析には，いくつかの方法があるが，この研究では次の二つを用いた。 ¸ 繰り返しにより不動点を求める方法[1] ― 427 ― ¹ 凸ダイバージェンスの最小化を行う方法[2] 画像の圧縮と検索については方法¸を，そして DNA 配列のパターン認識については方法¹を用いた。これは， 方法¸はスピードにおいて優れ，そして方法¹は基底への多様な情報の注入性において優れているためである。 3 画像圧縮と検索の同時確立 3.1 基底を用いた画像圧縮 まず，この研究において開発した画像圧縮・検索のためのフォーマットを説明しておく。 図１ PCA と ICA 基底を用いた画像圧縮 各静止画像は，8×8 ピクセルからなるパッチごとに，第2章で説明した方法により前処理され，図１にあるよ うに圧縮されたデータとなる。この図において，基底とは，PCA 基底あるいは ICA 基底のどちらかを表す。符 号化とある部分はエントロピー符号化を意味し，この研究では JPEG との比較のために，run-length ハフマン 符号を用いた。 3.2 開発した画像フォーマット 次に，開発したフォーマットを説明する。このフォーマットは図２にあるように，ヘッダ部分と画像を構成す る部品が格納されたブロックからなっている。 図２ 検索性能を有する圧縮フォーマット この図にあるように，平均色，基底，係数の各ブロックには，ブロックの圧縮情報などが格納されたブロック ヘッダがついている。このフォーマットが，ブロックに分けた圧縮方式となっているのは，各情報を容易に取り 出せることを旨としているためである。画像を構成する各ブロックは，以下の通りである。 ¸ ファイルヘッダは，画像の大きさやファイルのバージョン，そしてそれぞれのブロックへのオフセットと いった，最も基本的な情報を含んでいる。 ¹ File information header：このブロックは画像圧縮と直接の関連しない追加情報を含めるために用意され ― 428 ― ている。たとえば，画像製作者や，著作権の情報などである。 º 平均色は色情報を使った検索に利用される。これは，サムネイルとして利用したり，プログレッシブ表示 に利用したりすることができる。 » 基底：この部分は，PCA 基底や ICA 基底が納められる。基底情報は，画像同士の類似性に対する基準と して使うことができる。 ¼ 係数：これは，上の基底を用いて画像を変換符号化した後の係数である。 このフォーマットは，次節で説明する類似画像検索に用いることができるので，RIM（Retrievable Image format）と名付けられている。 3.3 類似画像検索 次に，類似画像の検索について説明する。性能評価用の画像には，ワシントン大学が公開している Ground Truth データベース[3]を使用した。このデータベースには，1,100枚を超える数の木，山，海，草原，建物などの 多様な自然画像が含まれている。検索対象となるデータベース中の画像を，図２のように RIF に変換しておい た。 類似画像検索とは，一枚のクエリ画像を与えたとき，それに類似した画像を見つけ出すことである。このとき， 次の二点が問題となる。 ¸ 何をもって“似ている”とみなすのかは，各個人の感性に依存する。そこで，オピニオンテストに基づく 性能評価が必要となる。 ¹ オピニオンテストの被験者は，自分の感性に基づいてすべての画像に対して類似・非類似の判定をしてお かなければならない。従って，オピニオンテストはかなりの労苦を強いることになる。また，一般ユーザに とっても使い勝手のよい GUI が必要である。 そこでまず，以下において上記の¹に関するシステムを提示しておく。 図３ Wisvi による類似画像検索のスクリーンショット 図３は，Wisvi（Waseda image searchable viewer）と名付けた類似画像検索用 GUI のスクリーンショット である。この Wisvi は，基底の類似度を使って，画像同士を比較する機能をもった viewer である。検索の際は フォルダを指定するだけで，データベースを介さずに検索を行うことが可能である。図３は，次元96の PCA 基 底で，パッチサイズ 8×8 の場合の検索結果である。左側の大きな画像が質問画像，右側に出ているサムネイル 画像が検索画像である。一番左上の画像が最も類似度が高く，右下に行くほど低くなっていく。この様な画像検 ― 429 ― 索システムの性能は，ユーザが「似ている」と判断できる画像が上位に含まれているかによって決められる。 検索速度については，Pentium 4 2.8 GHz の PC を使って実験をおこなったところ，1100＋ の画像を最初に 検索するのにかかった時間は約25秒であった。二回目以降の検索は，メモリ上にデータが残るため，ほぼ半分の 時間で終了する。 次に，画像の基底を用いた類似度と人間の感性による類似性とを定義しておく。 ［画像の基底を用いた類似度］ ¸ 基底に関する類似度 S basis を，次のように定義する。 for (k = 1; k < = n; k + +) ｛ I1 I1 I1 I2 I2 I2 a k = a k / a k ; a k = a k / a k ; ｝ S basis = 0 ; for (k = 1; k < = n; k + +) ｛ S basis + = (n - k + 1) # max i, j b a k : a k l ; I1 I1 I2 I2 a k = a k = 0 ; ｝ S basis # = 2/( n # (n + 1)); Ij ここに，a k は基底ベクトルである。 ¹ 色情報に関する類似度 S color を，次のように定義する。 (1) (2) (1) (2) S color = 1 = !i, j I i, j : I i, j / I i, j : I i, j NB (k) ここに，I i, j はブロックの平均色であり，N B はブロックの総数である。 º 最後に，総合類似度を次のように定義する。 Â S = aS basis + (1 - a) S color ［被験者が定義する類似性］ ¸ 各被験者は，全画像から質問画像と対象画像のペアを100組選び出す。 ¹ 上で選択された100組のペア50組は，性能を評価するためのテストデータとする。 º トレーニングデータを使い，各被験者にとって検索成功率が最大となる類似度結合加重 a を 0.01 刻みで 求める。ここで，検索成功率とは，対象画像が全画像の上位１％に位置付けられることとする。 » 上で得られた加重 a とテストデータを使い，検索成功率を調べる。 ¼ 以上の¹∼»の手順を1セットとし，これを100回繰り返して平均成功率を出す。 3.4 性能評価 まず，図２による RIM 圧縮が，どの程度の画像圧縮性能をもつのかを調べてみる。図４は，圧縮性能の一例 として，標準画像の peppers に対して，PCA 圧縮と ICA 圧縮を行った結果を，JPEG と比較したものである。 この図において，“ICA with weak guidance”[4]とは，基底の導出過程において低周波成分が中央に固まるよ うに付加項を付けたものである。この図は一例であるが，他の画像からも次のようなことがいえる。 >PCA や ICA による画像圧縮は，高精度領域で JPEG をしのいでいる。高精度領域は，ピクセル数の増加 により，ますます重要になっている。 >“weak guidance”を付けた ICA は，最も性能がよい。 次に，Â式による類似度が，被験者の感性とどの程度一致しているのかを調べるために，上で述べたようなオ ピニオンテストを，20代の男女10人に対しておこなった。 図５は，検索性能を示したものである。この図の見方は，次の通りである。いま，クエリ画像に対する目的画 像が，上位１%以内に入っているべきだとすると，横軸の１％の位置で縦線を引いてみる。そのときにできる各 曲線との交点が成功率（success rate）を表している。この図にあるように，PCA，ICA，そして ICA の変形 ― 430 ― 版はどれも優れた検索成功率を有している。ただし，検索速度しては，PCA，ICA，変形 ICA の順である。 図４ PCA, ICA, JPEG の圧縮性能比較 4 4.1 図５ 検索性能の評価 離散系列の分解とその応用 離散系列を扱う意義 離散系列とは，有限個の記号の連鎖を意味する。これはただの系列ではなくて，その記号の現れ方に何らかの パターンが存在することが重要である。そしてそのパターンも，計算機科学におけるストリングマッチングで検 出できるような単純なものではなくて，記号ずれや相対位置ずれが存在するようなものである。このような離散 記号列において，きわめて重要なものが， ｛A，T，C，C｝からなる DNA 配列である[5]。 図６ ヒト遺伝子のプロモーター付近における保存領域 図７ 離散記号からなる系列の分解 ― 431 ― 図６は，重要な DNA 配列であるヒト遺伝子のプロモーター付近における保存領域を図示したものである。プ ロモーターは遺伝子の転写を制御する部位であり，その解析はポストゲノム時代の重要なテーマになっている。 遺伝子配列中のパターンには，まさしく記号ずれと位置ずれがある。そこで，この研究では，図７左部にある ように，離散記号配列は隠れた n 個の成分の合成であると考えた。このような成分への分解は，記号頻度を とった後，À式の形で推定した結果となっている。 図８ ICA によるヒト遺伝子のプロモーター検出 図８は，ICA により隠れたモードを発見した後，それを用いてヒトのプロモーターを検出するアルゴリズム をブロック図として表したものである。ヒトのプロモーター検出は非常に困難な問題であるが，この手法により (PREC, SPEC, SENS)＝(0.632, 0.573, 0.824) の性能を得ており，これは報告書の時点において最高の性能となって いる。 5 おわりに この研究では，情報源を再生できる成分への分解法に関する理論とその応用を行った。ここで特徴的なことは 次の通りである。 ¸ 理論面においては，一般化された尤度の最小化や weak force の導入といった独自の方法を与えた。 ¹ 連続信号系への応用として，静止画像の圧縮と検索の同時実行を可能にする RIM を提示して，良好な性 能を得た。 º 離散記号列への応用として，ヒトゲノム中のプロモーター検出を行い，最高性能を得た。 以上はこの先へもつながっているテーマであり，今回の助成は非常に有意義に用いられたといえる。 文献 [１] A. Hyvarinen, Fast and robust fixed-point algorithms for independent component analysis, IEEE Trans. Neural Networks, 10, 626-639, 1999. [２] Y. Matsuyama, N. Katsumata and R. Kawamura, Independent component analysis minimizing convex divergence, Lecture Notes in Computer Science 2714, pp. 27-34, 2003. [３] Washington University, Ground Truth Database http://www.cs.washington.edu/research/imageda tabase/groundtruth/ [４] Y. Matsuyama, H. Kataoka, N. Katsumata and K. Shimoda, ICA photographic encoding gear: Image bases towards IPEG, Proc. Int. Joint Conf. on Neural Networks, 3, pp. 2129-2134, 2004. [５] D.W. Mount, Bioinformatics: Sequence and genome analysis, Cold Spring Harbor Laboratory Press, 2001. ― 432 ― 〈発 表 資 料〉 題 名 掲 載 誌 ・ 学 会 名 等 発 表 年 月 Database retrieval for similar images using ICA and PCA bases Engineering Applications of Artificial Intelligence, Vol. 18, pp. 705-717. 2005年４月 Decomposition of Discrete-symbol biosequences to hidden components: Independent component analysis for DNA promoter recognition Proceedings of International Conference on Neural Information Processing, Vol. 1, pp. 538-543. 2005年11月 Network communication strategies for cooperative physical agents Proceedings of Asia-Pacific Symposium on Information and Telecommunication Technologies, Vol. 1, pp. 148-153. 2005年11月 ― 433 ―