情報論的学習理論テクニカルレポート              時系列パターンの多数決型識別器の設計

          小川原 光一 福冨 正弘

                 


 



馮 尭楷      

内田 誠一

                                                                                Æ         

                       Æ

             

時系列パターンの識別手法 !"# として，動的計画法（$%）を用いたマッチング法 !&# や，' (( （'((）を用いた手法 !)# 等が提案されている．

これら従来の手法では，パターン全体をいわば一つの特徴ベクトルと考え，一括して識別を行っている．
これに対し，本論文では，パターンの各サンプル点ごとに認識すなわちクラスラベルの決定を行い，最終的にクラスラベル数の多数決によってクラスを確定する手法（以下，多数決型アルゴリズムと呼ぶ）を提案する．多数決型アルゴリズムでは，一部のサンプル点において標準パターンとの間に予期せぬ差異が発生したとしても，それが全体に与える悪影響をその差異の大きさに因らず"  * は総サンプル点数+ に抑えられるという利点がある．さらに，例えば文献 !,# のように，冒頭数点の時点で認識結果を与たいような問題設定 *いわゆる早期認
識+ との相性もよい．
多数決型アルゴリズムを単純に実現するには，学習パ£ 九州大学大学院システム情報科学府 〒  福岡市西区
元岡 
      %"  #   " & '( )  

! $



*

 $%

+

 ,

Ý 九州大学大学院システム情報科学研究院+#  & '(     ターン（以下，全て同じサンプル点数  とする）の各はじめに !

" !

$

サンプル点における特徴量を収集し，それらの識別器を標準パターンとの最短距離法等の適当な方法を用いて構成すればよい．ただし単純に各サンプル点で完全に独立した識別を行ってクラスラベルを割り当てると，パターンの局所的な変動などにより，幾つかのサンプル点において散発的に不正解ラベルが割り当てられ，結果的に全体としても誤認識となる恐れがある．
そこで本手法では，散発的な誤認識を抑制するために，特定のサンプル点同士をできるだけ同じクラスにラベリングするという相互制約を導入する．具体的には，複数のサンプル点対について，それらのクラスラベルが異なる場合にペナルティを与え，できるだけ同じクラスにラベリングするという制約を設ける．このペナルティにより，パターン上でのクラスラベルの変化が小さくなるため，以下これを平滑化項と呼ぶ．
本手法では，各サンプル点における識別器の出力（識別コスト）と平滑化項の和が最小となるクラスラベルの割り当て方を求める．クラスラベルの割り当て方は &通り存在し，従って総サンプル点数  に対し指数関数的に増加する．そのため，ラベルの割り当て方を全通り計算し，その中から最適なものを選ぶという方法は，現実には不可能である．
そこで本論文は，最適なラベル割り当て方をグラフの

$%

%

最小切断 *グラフカット+!-# に帰着させて解く．グラフ

について最小化する問題と考えることができる．

 * + 4 * +*"+

識別コスト  * + としては任意のものを用いてよい．
例えば標準パターンとのユークリッド距離や，学習パターン分布を基準としたマハラノビス距離が考えられ
図 ". 多数決型アルゴリズムによる認識
カットは大局的最適化法の一種であり，画像修復 !/ 0#，
領域分割 !1#，物体認識 !2# 等に多く利用されている．グ
ラフカットを用いることにより，総サンプル点数  に4 + の間に特る．なお，上式において， と  *定の関係はないので， * + を最小化する  は，各サンプル点  において完全に独立に求められる．

対して多項式時間でのラベル割り当てが可能となる．本

手法が扱う問題は，パターンの各サンプル点に & つのク以上で述べた手法では，各サンプル点で独立した識別ラスラベルのうちのどちらかを割り当てる問題であり，を行うために，パターンの局所的な変形などにより，幾本質的には図3地ラベルの割り当てを行うセグメンテー

つかのサンプル点において散発的に誤認識が発生し，結ション問題の一種と捉えることもできる．従って，グラ果的に全体としても誤認識となる恐れがある．例としてフカットとの相性はよい．

6/7 と 627 の & クラス識別を考える．これらは冒頭部平滑化項の導入

本論文の構成は以下の通りである．& 節では時系列パが類似しているために，その部分では散発的な誤認識がターンの多数決型アルゴリズムによる認識および平滑化不可避である．さらにその上，後半部に局所的な位置ず項について述べる．) 節ではグラフカットを用いた高速れが生じてしまうと，パターン全体として多くのサンプ解法について述べる．, 節では平滑化項の学習について

ル点で誤認識が発生することになり，結果的に誤認識と述べる．- 節では時系列パターン認識の一種であるオンなってしまう．

ライン文字認識を実験タスクとして，実験および考察を述べる．/ 節では結論を述べる．

そこで，本手法では，例えば隣接するサンプル点はできるだけ同じクラスラベルを選ぶといった相互制約を設けることを考える．この制約を実現するには，サンプル多数決型アルゴリズム



多数決型アルゴリズムによる認識

多数決型アルゴリズムでは，" 節で述べたようにサン
プル点ごとに & クラス識別を行う．総サンプル点数を とすると， 個の識別器が存在することとなる．図 "に  4 ) の場合についてその概要を示す．同図は便宜上各サンプル点の特徴量を " 次元すなわちスカラー値
 * 4 " & )+ で表現している．同図では，ある入力パターンに対し，第 "，&，) サンプル点の識別器がそれぞれクラス "，5，" を返している．従って多数決処理によれば，この入力パターンはクラス " として識別される．
この各サンプル点におけるクラスラベル割り当ては，次のようにエネルギー最小問題として見ることができる．
すなわち，第  サンプル点 * 4 "      + におけるクラスラベルを  5 "，識別器の出力（識別コスト）を  * + とすると ，最適クラスラベル割り当て問題は次式のエネルギー  * + を割り当て  4 *       +点間のラベルが異なった場合にペナルティ（平滑化項）を加えるようにすればよい．平滑化項により，各サンプ
ル点におけるクラスラベルの選ばれやすさを制御することができ， より高精度な識別が可能になると期待される．
サンプル点と  間の平滑化項を * + 4
ここで， * + 8

 *   +¾



は & 点対を表す集合で，*   +*&+のときと  間に平滑化項が存在している．また，平滑化項について以下の仮定を置いている．

 *   +455 4  *)+

すなわち，平滑化項は正の値であり，& サンプル点のクラスラベルが同じであれば値は零である．なお上式では 4  の場合に
½ 正確にはÚ -Ú Ú . と表記すべきであるが， Ú -Ú . と略記する．

 *   + とす

ると，式 *"+ のエネルギーは次式のように拡張される．

 *   + が具体的にはどのような非負値を持つかについては規定していない．この値は，各応用において自由に定めればよく，例えばすべて

y2 (2nd sample point)y1 (1st sample point)

(a)

(b)

(c)

(d)

(e)

図 &. 多数決型アルゴリズムによる識別境界 * 4 &+．
*+ 平滑化項なし，*+*+ *5 "+

 *5 "+
55

 *" 5+

 *" 5+ 4 5，*+5， *+ *5 "+ 4 5  *" 5+ *5 "+ 4

 *" 5+ 4．

5，*+*+*+図 ). 多数決型アルゴリズムによる識別境界 * 4 )+．それぞれ ) 視点から表示．

*+ *   +  5，*+  *   + 4 正定数，*+  *   + 4   の組で異なる正定数．の *   + の組について一定値でも良いし，何らかの学習ルの割り当て方のうち， * + が最小となるものを探索法によりそれぞれの *   + について適切な値に定めてもする問題となる．総当り探索は簡単であるが， の増よい．

加を考えると現実的ではない．特にこの探索処理は事前

各サンプル点に割り当てられるラベルは & つに１つで通り存えられる毎に実施する必要があるために，この膨大な計通りのラベ算量は致命的である．以下 ) 節においては，より洗練さあるため，パターン全体としての割り当ては &在する．式 *&+ の最小化問題は，これら &に実施しておけばよいものではなく，入力パターンが与れた技法を用いれば，この探索に要する計算量を多項式オーダーに抑えられることを示す．



平滑化項の影響

以下，識別境界に与える平滑化項の影響について， 4& および ) というサンプル点数が少ない場合を用いて，より実際的に検証する．まず総サンプル点数  4 & の場
合の識別境界は図 & のようになる．ここで，各サンプル点  4 " & における認識には各サンプル点毎の最短距離法を想定している．具体的には，クラス 5 の標準パターンを *&- &-+ ，クラス " の標準パターンを *0- 0-+ と図 ,. グラフカットによる時系列パターンのためのグを以下のようにユークリッド距離で定義している．

対に無限大の平滑化項を導入すれば， * + の最適化のし，入力パターン *   + に対する識別コスト  * + *5+ 4 *  &-+   *"+ 4 *  0-+
図 & *+ は平滑化項なしの場合の識別境界である．本
手法では各サンプル点毎すなわち各軸毎の最短距離識別を行うため，このように「田」の字型の識別境界となる．
なお，識別結果が  4  となっている領域 *左上および右下の領域+ は，何かしらのタイブレイクによって，最終的な識別結果を決定する必要がある．
重要なのは同図 *+*+ に示した平滑化項を導入した場合の結果である．具体的には，これらより，平滑化項を大きくすることで異なるクラスラベルが割り当てられる領域が減少し，同じクラスラベルが割り当てられやすくなっラフ
結果は  4    4  4    4 

5 " となる場合しか許さない識別面のみが得られる．
注意すべきは，図 )*+ *+ の例において，平滑化項は全ての & 点対に導入されており，従って隣接していないサンプル点間，すなわち  *   + および  *   +にも導入されている点である．このことは，時間的に連続していない & サンプル点間についても，なるべく同じクラスラベルを持つように制約することができることを意味している．従って，例えばパターンと始点と終点が同じクラスになるように制約を課したり，時間的な近傍性ではなく各点の特徴ベクトルの類似性に基づいて制約を課するなど，多彩な制御が可能である．ただしいずれていることがわかる．極端に  *5 "+ 4  *" 5+ 4 とした *+ の場合， * + を最小化するためは，式 *)+ のの場合も，結局は上述のように識別面を制御しているこ

等号条件を満たす他無く，すなわち  4  を満たす

他無く，識別境界は対角線となる．とに帰着する．

グラフカットによる解法

次に総サンプル点数  を ) とした場合の識別境界を式 *&+ のエネルギー  * + を最小化することを考え図 ) に示す．この場合の識別コスト  * + も  4 & とる．先述のとおり，クラスラベルの割り当て方は，総サ同様である．ただし， 4 & の場合と異なり，多数決のンプル点数  に対して &タイブレークが無いために，& クラスの識別面を表示し的な素朴な方式では膨大な計算時間を要する．ところている．同図 *+ は平滑化項なしの場合，*+ は平滑化

で，式 *&+ の平滑化項が    と呼ばれる条件

項がすべて同じ非負値の場合，*+ はすべて異なる非負 *5 5+ 8  *" "+通り存在するため，総当り *5 "+ 8  *" 5+ を満た値の場合である．平滑化項により & 点間に相互制約が設す場合には，グラフカットによって  に対する多項式けられ，識別境界が変化していることがわかる．すなわ

時間で大局的最適解を得られることが知られており !-#，

ち，単純な多数決戦略 *+ に比べると，平滑化項を調整式 *)+ はこの条件を満たすため，本手法ではグラフカッすれば，*+ のように実に多様な識別境界を構成できる

トを用いる．

ことがわかる．

式 *&+ のエネルギーの最小化のために，まず図 , に示

以上をまとめると，サンプル点間に平滑化項を導入す

す有向グラフるということは，そもそも識別結果においてそれらのクの集合であり，ラスラベルをなるべく同じにするという直接的な動機に基づくものであったが，実際には，そうした識別結果が得られやすいように識別面を操作していることに他ならない．実際，図 & *+ が示すように，全てのサンプル点4 *

+ を準備する．ここで  は頂点  は辺の集合である．グラフは， 個のサンプル点それぞれに対応した頂点  と，それらに加え & 頂点 ， を持つ．頂点  のそれぞれについて， から  への辺と  から  への辺を作る．これは式 *&+ の識別コストに対応するものである．また，頂図 -. *+ 入力パターン，*+ 平滑化項が存在する点対 *実線+，および *+ 対応するグラフ点間にも辺を作る．これは式 *&+ の平滑化項に対応するできないためである．無理に $% で解こうとすれば，高ものである．そして辺 *  + * + *   + に，重みをそ

次マルコフ決定過程を扱うことになり，最悪の場合ほとれぞれ  *"+  *5+んど総当り法と変わらない計算量が必要となる．グラフ

 *5 "+ として付与する．

便宜上，図 , において平滑化項に対応する辺は，隣接カットは，基本的に & クラス最適ラベリング法であり，サンプル点間にのみ作られている．実際には，&) 節で多クラス最適ラベリングを容易に実現できる点では $%も述べたように，任意のサンプル点間に存在してもよい．に及ばないものの，& クラスでよい場合は変数間の制約

こうして，より一般化された場合のグラフの例を図 - にに対する自由度が極めて高いために，非常に有用であ示す．時間的に離れたサンプル点間に平滑化項を与える

る．この優位性は，時系列パターンから画像のような空ことで識別面の多様な制御が行えることは前述の通りで間的広がりを持ったパターンを扱う場合に絶対的なものある．となる．

最適ラベル割り当ての問題すなわち  * + の最小化問
題は，グラフに対するグラフカットアルゴリズムにより解ける．グラフカットでは， ，  ， 4   ，
  4  を満たすように，グラフ の頂点集合  を と  に分割 *いわゆる切断+ する．関数  * + の最小化問
題は，こうした切断のうちで最小切断を求める問題に帰着し，その結果，最大流最小切断定理に基づくグラフカットアルゴリズムにより多項式時間で解ける !- "5 ""#．
ここでその詳細は略する．グラフの切断の結果に応じて，サンプル点  に対し，それに対応する の頂点  が 側ならば 5， 側ならば " のラベルを割り当てる．この結果は全てのラベル割り当ての中で最適であることが保証される．
切断とクラスラベルの例を図 / に示す．図 / において，グラフの切断を破線で，切断される辺を太線で示している．下部の数はその上の頂点に割り当てられたクラスラベルである．本手法では，最適割り当てされたラベ
ルの多数決により，入力パターンのクラスを決定する．
今回の問題に対して，グラフカットアルゴリズムの利用はむしろ必然的である．総当り法はナンセンスにしても，従来より時系列パターンの最適ラベリングすなわちセグメンテーションの問題に利用されてきた $% !&# も本問題には適用できない．これは時間的に離れたサンプル点間に平滑化項が入っており，目的関数  * + の最適化が単純マルコフ的性質を満たす多段決定過程に分解平滑化項の学習法

以上の議論で強調してきたように，平滑化項  *  + は本手法において極めて重要な要素であり，その値は対象とする問題に応じて適切に設定される必要がある．これまでに，平滑化項を学習データから学習する方
法 !/ 0 2# が提案されているが，一般的な手法は確立されていない．そこで本節では，平滑化項の単純な学習法を与える．
この学習法の基本的な考え方は以下の通りである．ある学習パターンについて本手法を用いて最適クラスラベル割り当てならびに多数決認識を行ったとする．その結果，ある & 点 *   + に異なるクラスラベルが割り当てられ，かつ認識結果が誤りであったとする．このような場合，それら & 点 *   + には同じクラスラベルを割り当てたほうがよいと考え，平滑化項  *5 "+ および
 *" 5+ の値を増加させる．また，ある & 点 * ¼  ¼ + に異なるクラスラベルが割り当てられているものの，正しい認識結果が得られているとする．この場合，その & 点は必ずしも同じクラスラベルを割り当てる必要はないと考え，平滑化項  *5 "+ および  *" 5+ の値を減少させる．
この平滑化項学習法を図 0 にまとめる．ただし同図で平滑化項とは  *5 "+ および  *" 5+ を指し，常に 5

数としたのは，多数決におけるタイブレークを避けるためである．各サンプル点での識別には学習パターンの分布によるマハラノビス距離を用いた．

実験結果, 節で述べた手法を用いて平滑化項の学習を行い，学習した平滑化項を用いて認識実験を行った．,- 組全部の認識に要した時間，すなわち )55*サンプル+,-*対+ 4 &0

図 /. グラフの切断と割り当てられるクラスラベル"

初期値として，*   + が隣接サンプル点であれば，その平滑化項を非負定数  に初期化し，そうでなければ零とする．

&)

ラフカットアルゴリズム " 回あたりはおよそ " であり，十分高速と言える．
平滑化項の学習結果を図 1 に示す．図 1 は，平滑化項が非零である & 点の組をプロットしたものである．すな

すべての学習パターンに対し最適ラベル割り当てならびに多数決認識を行う．の結果，多くの & 点間で平滑化項が非零であるクラス対

各 *   + についてと，平滑化項が隣接サンプル点間以外で零となるクラス5 であることを意味している．学習・*   + が切断されており，認識結果は正しい対が見られた．図 1 には，前者の代表としてクラス対・*   + が切断されており，認識結果は誤り

6/7627 を，後者の代表としてクラス対 6-7617 を示し

各 *   + について

 の場合，平滑化項を ．
・   の場合，平滑化項を 8．
誤認識数の変化がなくなるまで，もしくは一定回数繰り返し．
・-間は，民生用 %; を用いて )5 以下であった．従ってグわち，  *5 "+となった学習パターン数    を求める．
,&*クラス+

"5 回のラベル割り当て処理に要した時ている．
認識実験の結果を表 " に示す．同表より，学習により多くの平滑化項が非零であるクラス対 6/7627 では認識率が向上している．平滑化項が隣接サンプル点間以外で零であるクラス対 6-7617 では，認識率の大きな変化は見られない．また，図 2 に平滑化項が隣接サンプル点間のみの場合と学習により最適化された場合の各クラス対

図 0. 平滑化項の学習アルゴリズムにおける認識率を示す．横軸は隣接サンプル点間のみの *5 5+ および  *" "+ は含めない．

場合の認識率，縦軸は学習により最適化された場合の認また平滑化項の値は，負にはならないように制約されて識率を示しており，よって点が左上に寄るほど学習の効いるものとする．この単純な学習過程では誤認識の単調果があることを示している．同図より，いくつかのクラ減少性を保証できないため，反復のうちで誤認識数が最ス対について，学習による認識率の向上が見られる．こ小となったターンの平滑化項の値を学習結果とする．初うした結果が得られた理由については，次節 -) で考察

期値  については経験的に与えている．

する．に固定されている

全体平均では平滑化項により認識率の向上が見られオンライン文字の認識実験



実験条件

以上で述べた多数決型アルゴリズムによる時系列パターンの認識法の効果を検証するために，オンライン文字に対する & クラス認識実験を行った．実験に使用したデータは 9 : $ の 52 のオンライン文る．特に単純多数決 *平滑化項なし+ ならびに，従来のマッチング型識別 *平滑化項無限大+ に比べ，平滑化項を学習により最適化した場合の結果が優位であることは，平滑化項を導入した多数決型アルゴリズムの有用性を示している．

 考察字データである．学習用に各数字 055 サンプル，テスト平滑化項により認識率が向上した理由について，クラ用に各数字 )55 サンプルを用いた．クラス 657627 のうス対 6/7627 から考察する．図 1*+ より，平滑化項がちの & つからなる組合せは全部で ,- 通り存在する．前非零であるのは，隣接サンプル点間を除くと後半のサン処理として一画化，正規化を施し，また総サンプル数 が ,2 になるようリサンプリングを行った．点数  を奇プル点間である．クラス対 6/7627 の認識の例を図 "5に示す．同図では，正解ラベルが割り当てられたサンプ

recog. rate[%]with learned huv

100959085807570

表 ". オンライン文字の認識率 !<#平滑化項なし

隣接点のみ

学習によ

*一定値+*無限大+り最適化

6/762725&2-12,&2016-76172,)20-20-20-

全体平均2"/2)12)22,)

70 75 80 85 90 95 100

recog. rate[%]with constant huv
図 2. 平滑化項の学習の有無による各クラス対の認識率v

v

3030

2020101040の比較

40

00010 20 30 40*+ 6/7627

u010 20 30 40

u*+ 6-7617

図 1. 学習後に平滑化項が非零となったサンプル点対ル点を緑丸で，不正解ラベルが割り当てられたサンプル点を赤丸で示している．同図 *+ は平滑化項なしの場合，*+ は学習により平滑化項を最適化した場合である．*+*+*+において，平滑化項が非零であるサンプル点間を青線で結んでいる．
平滑化項が非零である後半のサンプル点において，クラス 6/7 と 627 の形状は大きく異なる．そのため後半のサンプル点において分布が大きく異なり，認識が容易であると考えられる．図 "5 *+ より，平滑化項が非零である後半のサンプル点では，不正解ラベルが割り当てられたサンプル点より正解ラベルが割り当てられたサンプル点のほうが多い．認識が容易であるサンプル点間に平滑化項を導入することで，図 "5 *+ のように正解ラベルがより多く割り当てられると考えられる．また，前半部分においては，形状が類似しているため不正解ラベルが多く割り当てられている．このような部分では平滑化項は隣接サンプル点間以外零となっている．
以上をまとめると，次の & 点が言える．

図 "5. クラス対 6/7627 の認識の例．*+ 平滑化項なしの場合．*+ 学習により最適化した平滑化項を用いた場合．
滑化を行うことはしない．
次に，クラス対 6-7617 のように，平滑化項が隣接サンプル点間以外で零のままであり，結果的に認識率が向上しなかった場合の理由について考察する．表 " の結果より，クラス対 6-7617 は平滑化項が隣接サンプル点間のみの場合でも高い認識率である．図 0 のアルゴリズム
より明らかなように，平滑化項が増加するのは誤認識が多く，識別が困難な場合である．よって，平滑化項が隣接サンプル点間のみでも元々認識率が高ければ，学習によって平滑化項は増加しない．一方，表 " からもわかる
ように，平滑化項なしの場合より隣接サンプル点間に平" 形状が明らかに異なり混同しにくい部分について滑化項を導入した場合 *初期化後の状態+ のほうが認識は，もともと正解しているサンプル点が優勢であ率が高い．そのため，隣接サンプル点間の平滑化項は減ると考えられるので，積極的に平滑化を行うこと少しない．以上を要するに，学習によって平滑化項の増で，その部分に散在するであろう不正解部分を削減はなく，その結果，認識率も初期化後の状態すなわち減できる．

隣接サンプル点間のみに平滑化項を入れた場合と比べて& 形状が類似し混同しやすい部分については，無理にクラスラベルを統一してしまうと，場合によっては不正解を増やしてしまう可能性がある．そのため，混同しやすい部分については，積極的に平改善も改悪もなかった．



まとめと今後の課題!)# @ > >  A ' B 6: 

時系列パターンの認識のために，多数決型アルゴリズ

 (!,# C ?  E : 

ラベル数の多数決により認識を行う手法である．サンプ
ル点間に平滑化項を導入することにより，任意のサンプル点対をできるだけ同じクラスにラベリングするという制約を設けた．この平滑化項の値を操作することは，識別面を操作することに相当することを，簡単な例を通して確認した．
多数決を行うに前に，各サンプル点へのクラスラベル%!-# = E    %:(!/# C E

性は総サンプル点数に対し指数関数的に増加するため， 7 %大局的最適解が求まる手法を提案した．本手法の有効性を検証するため，オンライン文字データを対象として認識実験を行い有効性を確認した．

   7

 > F 6G          H 7

999

&/  & ",0"-2 &55,

 ( ' 6$           I %C &55)

!0# $ ;    @ J   

 ;%> :,/ &551

で，グラフカットアルゴリズムを導入し，非常に高速に69      

割り当ての最適化を行う必要があるが，割り当ての可能素朴な総当り的な最適化は用いることができない．そこ

999 :CC% ( )  ,D"/ "21/ムを提案した．これは各サンプル点において & クラス識別すなわちクラスラベルの決定を行い，最終的にクラス  7 Æ  

 7 %6C      9;;=  &/)&0, &55/

!1# K A (% B  6       

今後の課題として，第一に，平滑化項の学習法の検討   が挙げられる．最急降下法のように，誤認識が減少する

 I$  7 %方向へ平滑化項を更新するといった手法が考えられる．

&55"   
 ;;=



 "  "5-""&第二に，時系列パターンのような " 次元的なパターンのみではなく，画像のような & 次元的なパターンに適用することが挙げられる．この場合，画像セグメンテーションの問題を一種の認識と捉えていることになる．実際そうした試みは既に多数なされているが，平滑化項をどのように設定すれば & クラスの差別化が図れるかといった，識別面構成の視点からの研究については，検討の余地が!2# $ :
E A  $ J     = ;

J '  : I
 

$
6$

    )$   7 % ;=%>

 "/2"0/ &55-
!"5#  ; ; @   > >  著

浅野哲夫

あると考えている．第三に，多クラスの同時識別がある

岩野和夫 梅尾博司 山下雅史 和田幸一 訳 アルが，これはグラフカットアルゴリズムの改良版を参照す

ゴリズムイントロダクション 第 & 巻 近代科学社

れば実現できるだろう．第四に，時間伸縮への対応とい"22-

う興味深い課題が残されている．この場合，従来では主として動的計画法が扱ってきた最適点対応 *最適時間伸縮+ の問題と，今回グラフカットで対処した最適ラベル割り当ての問題が混在することになり，それらをどのように解くのか，特に統一的に解けるのかについて，今後検討が必要と思われる．

参考文献!"# 川嶋宏彰

西村拓一

6コンピュータビジョンにおける時系列パターン認識 7 情報処理学会研究報告&55/;= ("-,*&0+ &55/
!&#

内田誠一 6$% マッチング概説〜 基本と様々な拡張 〜 7 信学技報 %>(?&55/"// &55/

!""# 永持仁 6グラフの最小分割問題に対するアルゴリ

ズム 7 信学論 B1/$  &  -)/1 &55)