電子情報通信学会論文誌 2010/4 Vol. J93–D No. 4

多数決型アルゴリズムと呼ぶ）を考えることもできる．
相互制約付き多数決型アルゴリズムによる時系列パ
ターン認識福冨正弘†（学生員）

小川原光一††

馮尭楷†††内田

上述の従来手法では，あるサンプル点において，標準パターンとの間に非常に大きな差異が発生した場合，そのサンプル点の悪影響が非常に大きくなり，その結誠一†††（正員）

果誤認識となる可能性がある．これに対し，多数決型

Recognition of Sequential Patterns by Combining Mutually

アルゴリズムでは，標準パターンとの差異が非常に大Constrained Local Classifiers

きいサンプル点が存在しても，それが全体に与える悪Masahiro FUKUTOMI† , Student Member,
Koichi OGAWARA†††††, Yaokai FENG

Seiichi UCHIDA††† , Member†, Nonmembers, and総サンプル点数），多数決により正しい認識結果が得られるという利点がある．更に，冒頭数点の時点で認

九州大学大学院システム情報科学府，福岡市

Graduate School of Information Science and Electrical Engi††

neering, Kyushu University, Fukuoka-shi, 819–0395 Japan

識結果を与えたいような問題設定 [4]（いわゆる早期認

九州大学高等研究院，福岡市識）との相性もよい．

Faculty of Institute for Advanced Study, Kyushu University,
Fukuoka-shi, 819–0395 Japan†††

影響はその差異の大きさによらず 1/N であり（N は

ただし単純に各サンプル点で独立した識別を行って九州大学大学院システム情報科学研究院，福岡市

クラスラベルを割り当てると，いくつかのサンプル点

Faculty of Information Science and Electrical Engineering,において散発的に誤認識が発生し，結果的に全体としKyushu University, Fukuoka-shi, 819–0395 Japanても誤認識となるおそれがある．そこで本手法では，複数のサンプル点対について，それらのクラスラベル
あらまし 本論文では，時系列パターンの認識手法が異なる場合にペナルティ（平滑化項）を与え，なるとして，各サンプル点（各時刻）で認識すなわちクラべく同じクラスにラベリングするという相互制約を設

スラベルの決定を行い，最終的にクラスラベル数の多けることにより，散発的な誤認識を抑制する．

数決によってクラスを確定する手法を検討する．その更に，各サンプル点における識別器の出力（識別コ一つの特徴として，必要に応じて複数サンプル点間にスト）と平滑化項の和が最小となるクラスラベルの割相互制約を設け，それらをできるだけ同じクラスにラ当方をグラフの最小切断（グラフカット）問題 [5] にベリングする点が挙げられる．これにより，クラスラ帰着させて解く．グラフカットは大局的最適化法の一ベルの割当方を制御でき，自由度の高い識別が可能と種であり，画像修復 [6], [7]，領域分割 [8]，物体認識 [9]なる．クラスラベルの割当の組合せは総サンプル点数等に多く利用されている．グラフカットにより，N にに対し指数関数的に増加する．そこで，グラフの最小対して多項式時間での計算が可能となる．

切断アルゴリズムいわゆるグラフカットを用いること

2. 多数決型アルゴリズム

で，総サンプル点数に対して多項式時間での計算を実

2. 1 多数決型アルゴリズムによる認識現する．オンライン文字データを対象とした認識実験

多数決型アルゴリズムでは，サンプル点ごとに 2 クを行い，本手法の有効性を検証した．
キーワード 時系列パターン認識，多数決型アルゴリズム，オンライン文字，グラフカットラス識別を行う．このクラス識別は，第 v サンプル点(v = 1, . . . , N ) におけるクラスラベルを Xv ∈ {0, 1}，識別器の出力（識別コスト）を gv (Xv ) とすると（注 1），1. ま え が き

次式の J(X) を割り当て X = (X1 , . . . , XN ) につい

本論文では，時系列パターンの 2 クラス識別手法て最小化する問題と考えることができる．

について検討する．時系列パターン認識手法 [1] として，動的計画法 (DP) を用いたマッチング法 [2] や，

Hidden Markov Model (HMM) を用いた手法 [3] など多数の方法が提案されている．これら従来の方法では，パターン全体をいわば一つのベクトルのように見て一括して識別するというアプローチがとられている．
これに対し，パターンの各サンプル点ごとに認識すなわちクラスラベルの決定を行い，最終的にクラスラベル数の多数決によってクラスを確定する手法（以下，548

電子情報通信学会論文誌

J(X) =Ngv (Xv )(1)

v=1

2. 2 相互制約としての平滑化項の導入
サンプル点 u と v 間の平滑化項を huv (Xu , Xv ) とすると，式 (1) は次式のように拡張される．
（注 1）：正確には gv (Xv |yv ) と表記すべきであるが（ここで yv は第 v サン
プル点の特徴値），gv (Xv ) と略記する．

c （社）電子情報通信学会 2010
D Vol. J93–D No. 4 pp. 548–551 レターJ(X) =N

gv (Xv ) +v=1

huv (Xu , Xv ) (2)(u,v)∈E

により多項式時間で解くことができる．最後に，S 側の頂点に 0，T 側の頂点には 1 のラベルを割り当て，ラベルの多数決により入力パターンのクラスを決定

ここで，E は 2 点対を表す集合で，(u, v) ∈ E のと
き u と v 間に平滑化項が存在している．また，以下のする．

4. 平滑化項の学習法

とおり，平滑化項は非負の値を取り，2 サンプル点の平滑化項 huv (Xu , Xv ) の値は認識対象に応じて適クラスラベルが同じであれば零になるように定める．

切に設定される必要がある．これまでに，平滑化項をhuv (Xu , Xv )学習データから学習する手法 [6], [7], [9] が提案されて=0

if Xu = Xv

≥0otherwise(3)

3. グラフカットによる解法
式 (2) の J(X) を最小化することを考える．クラス
ラベルの割当方は，総サンプル点数 N に対して 2Nいるが，一般的な手法は確立されていない．本手法では，図 2 の反復改善による学習法に従って決定する．
ただし同図で平滑化項とは非負になるように制約された huv (0, 1) 及び huv (1, 0) を指し，常に 0 に固定されている huv (0, 0) 及び huv (1, 1) は含めない．また，誤認識の単調減少性を保証できないため，反復のうち通り存在するため，総当り的な方式では膨大な計算で誤認識数が最小となったターンの平滑化項の値を学時間を要する．ところで，式 (2) の平滑化項が sub-習結果とする．初期値 h0 は経験的に与えている．

modularity と呼ばれる条件 huv (0, 0) + huv (1, 1) ≤huv (0, 1) + huv (1, 0) を満たす場合には，グラフカットによって N に対する多項式時間で大局的最適解を

5. オンライン文字の認識実験
5. 1 実 験 条 件
提案手法の効果を検証するために，オンライン文字得られることが知られており [5]，式 (3) はこの条件をに対する 2 クラス認識実験を行った．実験には Ethem満たすため，本研究ではグラフカットを用いる．

Alpaydin Digit の 0–9 のオンライン文字データを使グラフカットでは，まず有向グラフ G = (V, E) を準備する．V は頂点の集合であり，N 個のサンプル点それぞれに対応した頂点 v と，2 頂点 s，t から構成される．E ⊂ V × V は辺の集合であり，s からv への辺と v から t への辺及び頂点間の辺から構成される．また，辺 (s, v), (v, t), (u, v) には，それぞれ用し，学習用に各数字 700 パターン，テスト用に各数字 300 パターンを用いた．各サンプル点における特徴値にはそのサンプル点の座標特徴（x，y 座標）を用いた．前処理として一画化，文字の大きさ（外接方形の大きさ）が一定となるよう正規化を施し，また総サンプル数 N が 49 になるようリサンプリングを行った．

gv (1), gv (0), huv (0, 1) を重みとして付与する．図 1 に各サンプル点での識別には学習パターンの分布によるグラフの例を示す．

マハラノビス距離を用いた．

次に，s ∈ S ，t ∈ T ，V = S ∪ T ，S ∩ T = φ を満たすように，頂点集合 V を S と T に分割（切断）する．関数 J(X) の最小化問題は，切断された辺の重み

5. 2 実 験 結 果
4. で述べた手法を用いて平滑化項を学習し，学習しの和が最小となる最小切断を求める問題に帰着し，最大流最小切断定理に基づくグラフカットアルゴリズム

図 1 (a) 平滑化項が存在する点対（実線），(b) グラフ
Fig. 1 (a) Sample point pairs that have smoothnessterms (solid line), (b) Graph.

1. 初期値として，(u, v) が隣接サンプル点であれば，その平滑化項を非負定数 h0 に初期化し，そうでなければ零とする．
ここでは，u と v が時間的に隣り合うサンプル点すなわちv = u + 1 のとき，(u, v) を隣接サンプル点とする．
2. すべての学習パターンに対し最適ラベル割当並びに多数決認識を行う．
3. 各 (u, v) について・(u, v) が切断されており，認識結果は正しい・(u, v) が切断されており，認識結果は誤りとなった学習パターン数 C1 , C2 を求める．
4. 各 (u, v) について
・C1 > C2 の場合，平滑化項を −．
・C1 < C2 の場合，平滑化項を +．
5. 誤認識数の変化がなくなるまで，若しくは一定回数繰り返す．
Fig. 2図 2 平滑化項の学習アルゴリズム
Algorithm for learning smoothness terms.

549

電子情報通信学会論文誌 2010/4 Vol. J93–D No. 4

図 3 学習後に平滑化項が非零となったサンプル点対
Fig. 3 Sample point pairs that have non-zerosmoothness terms.

Table 1

表 1 オンライン文字の認識率 [%]Recognition rate for online characters [%].

平滑化項なし“6”–“9”“5”–“8”
全体平均

90.2
94.3
91.6

隣接点のみ
（一定値） （無限大）
95.8
94.2
97.5
97.5
93.8
93.9

学習により最適化
97.8
97.5
94.3

図 4

クラス対 “6”–“9” の認識例 (a) 平滑化項なしの場
合，(b) 学習した平滑化項を用いた場合
Fig. 4 Recognition of the class pair “6”–“9” (a) Without smoothness term, (b) With smoothnessterm.

項を適切な一定値に設定した場合や学習により最適化した場合の結果が優位であることは，平滑化項を導入した多数決型アルゴリズムの有用性を示している．

6. む す び
た平滑化項を用いて認識実験を行った．クラス “0”–“9”のうちの二つからなる組合せ 45 組全部の認識に要した時間，すなわち 300(サンプル) × 2(クラス) × 45(対) =2.7 × 104 回のラベル割当処理に要した時間は，民生用 PC を用いて 30 s 以下であった．したがって 1 回当りおよそ 1 ms であり，十分高速といえる．
図 3 に，平滑化項が非零である 2 点の組をプロットしたものを示す．学習の結果，多くの 2 点間で平滑化項が非零であるクラス対と，平滑化項が隣接サンプル点間以外で零となるクラス対が見られた．図 3 には，前者の代表としてクラス対 “6”–“9” を，後者の代表としてクラス対 “5”–“8” を示している．
認識実験の結果を表 1 に示す．多くの平滑化項が非零であるクラス対 “6”–“9” では認識率が向上しているが，平滑化項が隣接サンプル点間以外で零であるクラス対 “5”–“8” では認識率に大きな変化は見られない．
クラス “6” と “9” では後半の形状が大きく異なるため，図 4 (a) に示すとおり，不正解ラベルが割り当てられたサンプル点（×印）より正解ラベルが割り当てられたサンプル点（○印）の方が多い．そのため，認識が容易であるサンプル点間に平滑化項を導入することで，図 4 (b) のように正解ラベルがより多く割り当てられると考えられる．また，形状が類似している前時系列パターンの認識のために，多数決型アルゴリズムを提案した．これは各サンプル点において 2 クラス識別すなわちクラスラベルの決定を行い，最終的にクラスラベル数の多数決により認識を行う手法である．
サンプル点間に平滑化項を導入することにより，任意のサンプル点対をできるだけ同じクラスにラベリングするという制約を設けた．また，グラフカットを用いて各サンプル点へのクラスラベル割当の最適化を行い，非常に高速に大局的最適解が求まることを示した．本
手法の有効性を検証するため，オンライン文字データを対象として認識実験を行い有効性を確認した．
今後の課題として，平滑化項の学習法の検討，画像のような二次元的なパターンへの拡張，時間伸縮への対応がある．他に，多クラス同時識別への対応が挙げられる．単純には多クラス識別は，2 クラス識別の組合せを行う方法があるが，いわゆる三すくみの問題が残る．より本質的な対応として，α-expansion 等に基づくグラフカットの多値化も考えられよう．また各サンプル点における識別器の構成法も一考の余地がある．
時間的拘束付きの boosting [10] による学習などが参考になるであろう．
文

川嶋宏彰，西村拓一，“コンピュータビジョンにおける” 情処学研報，2006-CVIM-154,
時系列パターン認識，pp.197–209, 2006.

[2]

内田誠一，“DP マッチング概説—基本と様々な拡張，”信学技報，PRMU2006-166, 2006.
L.R. Rabiner and B.H. Juang, “An introduction to

半部分では，不正解ラベルが多く割り当てられており，平滑化項は隣接サンプル点間以外零となっている．
全体平均では平滑化項により認識率の向上が見られ

献

[1]

[3]

る．特に単純多数決（平滑化項なし）並びに，従来のhidden markov models,” IEEE ASSP Mag., vol.3,

マッチング型識別（平滑化項無限大）に比べ，平滑化

no.1, pp.4–16, 1986.

550

レ[4]

ター

S. Uchida and K. Amamoto, “Early recognition ofsequential patterns by classifier combination,” Proc.

Proc. ECCV, pp.263–274, 2006.
[8]

ICPR, ThAT4.6, 2008.
[5]

[6]

n-d images,” Proc. ICCV, pp.105–112, 2001.
[9]

D. Anguelov, B. Taskar, V. Chatalbashev, D. Koller,

Trans. Pattern Anal. Mach. Intell., vol.26, no.2,

D. Gupta, G. Heitz, and A. Ng, “Discriminative

pp.147–159, 2004.

learning of markov random fields for segmentation

S. Kumar and M. Hebert, “Discriminative fields formodeling spatial dependencies in natural images,”[7]

optimal boundary region segmentation of objects in

V. Kolmogorov and R. Zabih, “What energy functions can be minimized via graph cuts?,” IEEE

Y. Boykov and M.P. Jolly, “Interactive graph cuts forof 3d scan data,” Proc. CVPR, pp.169–176, 2005.
[10]

R. Vidal and P. Favaro, “Dynamicboost: Boosting

Advance in Neural Information Processing Systems

time series generated by dynamical systems,” Proc.

16 (Proc. NIPS, 2003), pp.1531–1538, 2004.

ICCV, pp.1–6, 2007.

D. Cremers and L. Grady, “Statistical priors for ef-（平成 21 年 7 月 17 日受付，12 月 18 日再受付）

ficient combinatorial optimization via graph cuts,”

551