「画像の認識・理解シンポジウム (MIRU2010) 」 2010 年 7 月

多クラス早期認識ブースティング法とその応用
石黒 勝彦†

澤田

宏†

坂野

鋭†

† NTT コミュニケーション科学基礎研究所
京都府相楽郡精華町光台 2-4
E-mail: †{ishiguro,sawada,keen}@cslab.kecl.ntt.co.jp
あらましジェスチャ認識のような時系列シーケンスの認識においては，応用によりシーケンスの終了を待たずにできるだけ早く認識結果を出すことが要求される．この問題は早期認識の問題と呼ばれ，内田らによって提案された
ブースティング的解法が効果的であることが知られている．しかし ，内田らの方法は 2 クラス識別手法であるため，
例えば音声語彙認識などの多クラス識別問題への応用が困難であった．そこで我々は内田らの手法を多クラスへと拡張した多クラス早期認識ブースティング法を考案した．提案手法は簡潔に定式化可能であり，さらにその計算量はクラス数に対して線形で抑えることが可能である．自動車内の運転者行動認識および手書き数字認識をタスクとした実験を行い，提案手法の有効性を示した．
キーワード

早期認識，時系列解析，ブースティング，多クラス識別問題

Multiclass Boosting for Sequence Early Classification and its Applications
Katsuhiko ISHIGURO† , Hiroshi SAWADA† , and Hitoshi SAKANO†† NTT Communication Science Laboratories
2-4 Hikari-dai, Seika-cho, Soraku-gun, Kyoto, Japan
E-mail: †{ishiguro,sawada,keen}@cslab.kecl.ntt.co.jp
Abstract We propose a novel boosting method for early classification of sequences. In many practical problems, we would
like to classify a sequence into one of K classes as quickly as possible, without waiting for the end of the sequence. In thispaper, we propose a multiclass early classification model based on Adaboost, which extends the previously proposed “Earlyboost” for a binary classification to deal with many real-world problems. The formulation of the proposed multiclass earlyclassification method is straightforward, and its computational cost is small. We show the eﬀectiveness of our method throughthe classification experiments of driver behaviors and online hand writings.
Key words Early classification, time series data analysis, boosting, multiclass classification

1. は じ め にう必要がある．また，運転者がサイド ミラーを確認する
動作から車線変更の可能性を早めに予知することができ

本稿では，時系列デ ータをはじ めとするシーケン ス

れば，複数車間の運転をスムーズに協調制御することで，データの多クラス識別問題，特に早期認識と呼ばれる問例えば混雑した高速道路などでもより安全な車線変更の題について論ずる．

支援が実現できる．

例として車載カメラを用いた運転者行動の認識問題 [1]

このように，時系列シーケンスの終了をまたずにそのを考える．カーナビゲーションシステムなどに代表されクラス等を認識する識別問題は早期認識 (早期識別，early

る自動車の ICT 化は顕著であり，運転者の行動・動作・

classification) と呼ばれ，ジェスチャ認識 [2]，オンライン
手書き文字認識 [3] や音声発話認識システム [4] を始めとして多くの現実的なタスク・システムで必要となる課題である．
この課題に対して，一般に生成モデルあるいは識別モ
デルの利用による解決が考え得る．一つの解法として，
HMM [5] のような時系列生成モデルの利用が容易に想像される．しかしこれらのモデルは一般に時系列シーケン
ス x1:T を最後まで入力しシーケンス全体の情報から最適状態をカメラ等を通じて認識することで，運転者の状態に応じた，より快適で安全な運転環境を提供することが将来的に可能となると予想される．この際，運転者の役に立つ機能をシステムが発現するためには，運転者が行動を終了する前にその行動を予測・認識することが自然に要請される．たとえば運転中の携帯電話操作などの危険な行動に対しては，システム側はできるだけ早期に行動を認識してド ライバーに警告を与えるなどの処理を行

な識別結果 y を出力するという利用方法が一般である．

start (t = 1)

end (t = T)

モデルパラ メータの学習においても上記の利用方法をシーケンスデータ

想定しているため，そこで学習されたモデルパラメータがサブシーケンス x1:t (t < T ) の認識問題に対して最も優れているという保証は無い．一方，識別モデルとしてはSVM [6] や Adaboost [7] などがその高い識別能力ゆえに良く知られている．これらのモデルを利用するためには
一般にシーケンスサンプル xi , x j 間の距離等を良く表現する特徴量が必要となる．早期認識を行う場合，(部分)シーケンスの長さは一定ではないため，不確定なシーケ
ンス長の識別に有効な特徴を定義する必要がある．これは識別モデルの開発と同程度かそれ以上に困難な課題である．
この問題に対して，主にブースティング [7] の拡張モデルがいくつか提案されている．Sochman and Mates [8]は Sequential decision making problem のアイデアを組み合わせることによって，認識結果をユーザに報告するタ
イミング (できるだけ早く) と認識率 (できるだけ正確に )のトレード オフをモデル化した手法を提案している．一方，内田らは早期認識ブースティングと呼ばれる方法を提案した [9]. この手法では，複数シーケンスの時刻 t における観測量集合 {xi,t }i=1,...,N だけを識別する弱識別器 ht
を学習する．弱識別器の学習では，重み伝播法によって前時刻での弱識別器で識別に失敗したシーケンスの観測量を優先して正しく識別できるように目的関数を設計する．この手法によれば，前時刻までの情報に基づく識別器の誤りを訂正するように各時刻の弱識別器 ht を更新することによって，中途フレームまでの入力しか与えられない部分シーケンスに対してもできるだけ高い識別性能が得られるように識別器を構成することができる．
しかし，これらの既存モデルはいずれも 2 クラス識別モデルであり，より多クラスの早期認識問題への応用には課題がある．[9] においては，K > 2 クラスの識別問題( )を K2 個の 2 クラス問題に分解することによって解決した．しかし，この方法は時間・空間計算量の観点で明ら( )かに非効率的である上に，学習される識別モデルは K2
種の 2 クラス問題にそれぞれ最適化されたものにすぎず，
K クラスの識別問題として最適化されたモデルは得られない．
そこで我々は早期認識ブースティング法を多クラス識別問題へと適用可能とする新しい方法を提案する．我々の多クラス早期認識ブースティング法は K クラスの識別問題に対してその学習コストをクラス数 K に対して線形に抑えることができる．また，学習される識別モデルは個別最適化ではなく K クラス全体での識別性能を考慮して学習される．まず次節において背景となる既存手法について簡単に説明した後に，第 3 節で多クラス早期認識
ブースティング法を提案する．その後，手書き文字認識
データおよび動画像データにおける運転者動作認識を例としてその性能を実験で確認する．

1t

特徴ベクトルの

t-1

シーケンス
早期認識

Hk (x) = Σt=1:T αt ht,k (xt)識別

弱識別器を追加

ht,k (xt)

識別誤りに基づくシーケンスの誤差重みαt

最適な弱識別器の学習

重み伝播法

図 1 多クラス早期認識ブースティングの概念図．学習時には
重み伝播法を利用した誤り訂正学習により弱識別器 h と識別重み α を決定する．学習された弱識別器の集合からなる強識別器 H はシーケンスの早期認識を可能とする．

2. 既 存 手 法
2. 1 Adaboost
まず，最も基本となる 2 クラスの Adaboost [7] について簡単に説明する．観測特徴ベクトルを xi ∈ Rd ，そのクラスラベルを yi ∈ {1,− 1} とする．訓練データセット
D = {xi , yi : i = 1, . . . , N} が与えられた時，Adaboost の学
習問題では以下の強識別器 H : Rd → {1, −1} を決定する．

M

∑

(1)
yi = H(xi ) = sign  αm hm (xi ) .
m=1

ここで hm : Rd → {1, −1} は m 番目の弱識別器である．

αm ∈ R はその識別重みであり， M は弱識別器の総数である．これらの変数は m = 1 より m を一つずつインクリ
メントしながら式 (2)-(4) に従って学習される．
hm = arg min m ,h()
1
1 − mαm = log,2m∑
Dm (i).
m =

(2)
(3)
(4)

i:yi ,hm (xi )式 (4) は弱識別器 hm による識別が誤ったサンプル集合に対して，Dm (i) ∈ R を足し込んでいる．Dm (i) は m 番目の弱識別器学習におけるサンプル i の誤差重みであり，以下のように計算される．

Dm (i) ∝ Dm−1 (i) exp (−αm−1 yi hm−1 (xi )) .

(5)

式 (5) によれば，観測量 xi の hm−1 による識別結果が真のクラスラベル yi と異なると誤差重み Dm (i) が増加し，逆に正しければ誤差重みは減少する．この学習過程により，

それぞれの弱識別器は，大半の識別容易なサンプルを識た H はシーケンス長が短い (L <= T ) 部分シーケンスに対別するもの，大半のサンプルには弱いが識別困難な少数してもできうる限り正確な識別結果を与える早期認識器のサンプルの識別が得意なものなどに特化し，結果的にになっていることが期待される．

強力な強識別器を得ることが期待できる．

3. 提案法: Earlyboost.MH

2. 2 “Earlyboost”

3. 1 アルゴリズム

続いて，早期認識ブースティング法 [9] を説明する．なお，本稿ではこの手法を早期認識ブースティング法ある
いは “Earlyboost” と呼ぶこととする．

i 番目の観測時系列シーケンスデータを xi = {xi,t ∈ Rd }と表現する．シーケンス数は N であり，i ∈ {1, 2, . . . , N}でインデックスする．シーケンス長は T で一定と仮定し，t ∈ {1, 2, . . . , T } でインデックスする．yi ∈ {1, −1} はこのシーケンスサンプル xi に対するラベルを表す．
Earlyboost の学習では，以下の強識別器 H を訓練デー
タ D = {xi , yi } から学習する．
 T

∑
( )

yi = H(xi ) = sign  αt ht xi,t  .
(6)
t=1

{xi,t }i=1,...,N だけを入力とする，frame-wise の弱識別器である. 学習時には，t = 1 より t を 1 ずつインクリメント
しながら弱識別器 ht と識別重み αt ∈ R を以下のように
決定する．
(7)
(8)
(9)

i:yi ,h(xi,t )弱識別器 ht−1 と ht は，入力とする観測特徴ベクトルの集合が異なる．従って，これらを接続するためには何らかの工夫が必要である．[9] では，誤差重みを個別のサン
プル xi,t ではなく各時系列シーケンス xi 全体にかかるものと捉え，以下のように時刻 t − 1 から時刻 t へ識別情報を伝播させることを提案した．

()
Dt (i) ∝ Dt−1 (i) exp −αt−1 yi ht−1 (xi,t−1 ) .

ている．しかし，現実に早期認識を必要する課題は多クラス問題であることが多い．特に大規模語彙音声認識 [4]や手書き漢字認識などの場合には認識すべきクラス数は数百から数千と多数にのぼるため，[9] で採用されたよう( )に K2 個の 2 クラス問題に分割して対処することは識別時・認識時の双方において非効率的である．また，多数の 2 クラス識別器は独立に学習されるため，K クラス識
別器として最適化されていない．
そこで ，本節では我々が 考案し た多クラス早期認識
ブースティング法 Earlyboost.MH(図 1) を説明する．我々のモデルは Adaboost.MH [10] で提案された Adaboost のここで ht : Rd → {1, −1} は各シーケンスの時刻 t の観測量

ht = arg min t ,h()
1
1 − tαt = log
,
2
t
∑
t =
Dt (i).

このように，Earlyboost は時系列シーケンスの早期認識のために Adaboost を自然に再解釈したモデルとなっ(10)

多クラス化の試みを Earlyboost に直接適用し たものである．
与えられる学習データは D = {xi , yi }, i = 1, 2, . . . , N と表現する．xi は d 次元特徴ベクトルのシーケンスであり，

xi = {xi,t ∈ Rd }, t = 1, 2, . . . , T である．また，yi は i 番目のシーケンスのクラスラベルである．ただし，その値域はこれまでと大きく異なり，K クラス識別問題に応用するため yi ∈ {1, 2, . . . , K} と定義する．
弱識別器 ht,k (x) : Rd → {1, −1} は時刻 t の観測サンプ
ル x1:N,t のみを入力として受け取る．出力は，入力された x がクラス k に属すると識別した場合は 1, それ以外のクラスに属すると識別される場合には −1 を出力する．
また，新たに gk (y) : {1, 2, . . . , K} → {1, −1} という関数を定義する．この関数はクラスラベル y を入力として受け取り，y = k ならば 1 を，そうでなければ −1 を出力する関数である．
Earlyboost.MH では，下記の強識別器を学習する．
yi = arg max Hk (xi ) = arg max
k=1,2,...,K

この重み伝播法によって，時刻 t − 1 において誤識別されたシーケンスを優先して正しく識別するように ht を学習してゆく．
識別時は，上記で決定された強識別器 H を用いて，テスト (部分) シーケンス x j = {x j,t , t = 1, 2, . . . , L} のクラス
ラベル y j を以下のように決定する．

 L

( )
( )
∑

y j = H x j = sign  αt ht x j,t 

(11)

t=1

式 (10) で示される重み伝播法は前時刻での誤りを最小化するように弱識別器を構成している．従って，学習されk=1,2,...,KT∑

αt ht,k (xi,t ).

t=1

(12)
すなわち，弱識別器とその識別重み {ht,k , αt } を学習データ
D を用いて学習し，K 個の (2 クラス) 強識別器 Hk を生成する．そして，識別フェーズではそれらのスコアを比較することによってテストシーケンス x j を y j ∈ {1, 2, . . . , K}
へと識別する．
具 体 的 な 学 習 ア ル ゴ リ ズ ム の 説 明 を 行 う．Adaboost.MH [10] での多クラス定式化に従って，まず，式 (4)及び式 (9) における誤識別スコア  の最小化ではなく, 識
別スコア rt,k の最大化によって ht,k を決定する．以上を数式で表現すると式 (13), 式 (14) のようになる．

ht,k = arg max rt,k ,

(13)

h

rt,k =

N∑

能となる．弱識別器の構成方法として，前後数フレームから各弱識別器を学習するよう拡張することも可能であ

gk (yi )ht,k (xi,t )Dt (i, k).

(14)

り，またその拡張によってモデル全体の学習方法等は大きく変化しない事を注意しておく．

i=1

上式より明らかなように，rt,k は gk (yi ) と ht,k (xi,t ) の符号が一致した場合，すなわち与えられた観測量 xi,t がクラス k に属するか否かの識別結果が正しい場合に増加する．
各シーケンス i に対する識別結果は誤差重み Dt (i, k) ∈ Rによって重み付けされている．
この重みは Earlyboost に従って時刻 t − 1 より重み伝播に従って定義される．

(

Dt (i, k) ∝ Dt−1 (i, k) exp −αt−1 gk (yi )ht−1,k (xi,t−1 ) . (15)
式 (10) と異なり，クラス k に依存して重みを伝播させる．これは，クラス k0 とクラス k00 の識別時において，各シーケンスの重要度は自然に異なる事が想定されるか
らである．上記の誤差重み Dt (i, k) が与えられたもとで，全ての k ∈ {1, 2, . . . , K} について ht,k を rt,k に関して最適化する．
その後に，識別重みは以下のように ht,k について最大(16)以上の計算を t = 1 より t を 1 ずつインクリメントしながら t = T に到達するまで繰り返すことで学習が完了する．
識別フェーズでは，上記で決定された強識別器 Hk を用
いて，テスト (部分) シーケンス x j = {x j,t , t = 1, 2, . . . , L}のクラスラベル y j を以下のように決定する．

( )y j = arg max Hk x j = arg max
k

k

L
∑

( )
αt ht,k x j,tである．式 (15) にあるように，Earlyboost.MH では全 Kクラスの識別スコア rt,k の総和を用いて αt を決定している．従って，学習される強識別器 Hk は，各クラス k のための one vs. all の識別性能ではなく K クラス識別問題の性能を向上するように設計されていることになる．一方通常の Earlyboost [9] では「クラス k とクラス k0 」の 2)化された rt,k を用いて計算する．
()∑
1 + k rt,k1∑
αt = log.
2
1 − k rt,k

本稿で提案した Earlyboost.MH は Earlyboost に対し 2
つの点で優れている．まず第一は識別重み αt の計算方法

クラス識別に最適化された強識別器を多数用意することになる．従って，K クラス識別問題としての最適化は図
られていない．
第二に，Earlyboost.MH では必要となる学習コストがクラス数 K に対して線形に抑えられる．具体的には，長さ T の時系列シーケンスに対して K クラスの識別を行う場合，学習が必要となる弱識別器 Ht,k は T K 個であり，また計算が必要な識別重み αt の個数は T 個である．一( )方，[9] に示された方法では，弱識別器は T K2 回の学習
( )が必要であり，識別重みの個数も T K2 個必要となる．これは時間計算量，空間計算量ともに Earlyboost.MH より大幅に増加してしまうことを意味しており，特にクラス数の多い漢字認識や大規模語彙音声認識などの問題では致命的になりうる．この点でも Earlyboost.MH は多クラス識別に適した識別モデルであると言える．

4. 実

験

実験では，2 種類のタスクにおいて Earlyboost.MH の性能を確認する．一つはオンライン手書き数字認識，も

(17)

t=1

う一つは動画像を用いた運転者動作認識である．
なお，運転者動作認識実験のセットアップは [11] を参強識別器 Hk は式 (15) による学習の効果により，早期認考にした．

識のために最適化されている．従って，入力されるテス
トシーケンス x j が t = 1 ∼ L(<= T ) の範囲の観測量のみか

4. 1 実験データ

ら構成されていても，できる限り正確な多クラス識別が行われると期待できる．

3. 2 提案法の特徴
提案法では，シーケンス全体に対する” 良い” 特徴量をオンライン手書き数字認識実験では，Earlyboost の原論
文 [9] で利用されたデータと同じく Ethem Alpaydin Digit
データベースを利用した．このデータベースでは孤立数
字 (“0”-”9”) の手書き軌跡データが 800 サンプル提供されている．

開発する代わりに，各時刻固有の弱識別器を学習し，そこのデータはシーケンスの伸縮が非常に大きいため，[9]の集合を利用することでシーケンス全体の強識別器を構にならって単純な線形補間によって全てのシーケンスの成した．各弱識別器の識別能力は高くならないが，それ長さを T = 50 に揃える前処理を行った．特徴量はペンらを組み合わせることによって識別を行うアプローチは，先位置の 2 次元座標，および前フレームからの差分によシーケンスに対するブースティングの設計理念として自る速度特徴を用いた．これらの特徴を白色化した d = 4

然な発想と言える．また，式 (13), 式 (14) にあるように，次元の実数ベクトル系列が入力される特徴シーケンスで弱識別器 ht,k を各時刻ごとに定義しているので，時系列ある．

シーケンスの特徴ベクトルの分布が時刻発展に応じてダ識別する文字は数字 (“0” - “9”)，すなわち K = 10 ク

イナミックに変化する場合にも自然と追従することが可ラスの識別問題である．一つの孤立文字の軌跡を一つのシーケンスとみなす．学習では弱識別器として Dt,i,k にコアのみを計算し，その値が最も大きいクラスへと識別よる重み付きに従ってリサンプリングされた kNN(k = 5)する．このスコアの大きさは各強識別器の識別の確信度を利用した．学習および識別は 6-fold cross validation をを表している [10] ので，Earlyboost が正しく K クラス識用いて行った．

別問題に対しても適用可能であるならば，真のクラスの運転者動作認識実験では，実寸大のド ラ イビングシ

強識別器が最も高いスコアを出力するはずである．このミュレータの運転席にカメラを設置し，運転者の運転中方法によれば ，Earlyboost と Earlyboost.MH の計算量はの動作を録画，認識する実験を行う．本実験では 7 名のほぼ同等となるため公正な性能比較が可能である．

ド ライバに，それぞれ 30 回の運転シミュレーションを実

なお，[9] の論文では明確には示されていないが，より施させ，その様子をバックミラー付近に設置した一般の

正確に 2 クラスペア間識別器による K クラス問題の識単眼ビデオカメラで撮影した．フレームレートは 60FPS

別モデルを構成する場合には，誤り訂正符号にのっとっである．

たクラス分けを行う方法がより適切であると考えられ

画像より抽出する特徴量は [1] に従った．すなわち，オプティカルフローを用いて運転者の両手首，両肘，両肩の位置を追跡し，その軌跡を観測量とする．本実験では，そのうち車内の動作に大きな影響を及ぼ すと思われる
右手首，左手首および左肘の画像座標 (w, h) を特徴量とる [13]．ただし，この場合も元のクラス数 K 以上の強識別器が必要となる．

4. 3 実 験 結 果
最初に，オンライン手書き数字認識データの実験結果して採用した．従って，入力される観測ベクトル xi,t はを示す．図 2 は T = 50 フレームに正規化されたシーケ

d = 6(= 2 × 3) 次元の正数ベクトルである．
識別する動作のクラス数は K = 12 である．いずれもステアリングハンドルを握った状態から，エアコンやミラーなど K 種の車内設備を操作する，という動作を認識する．収集された時系列シーケンスは，まず 1 回の動作
ごとのシーケンス xi に分割したのち，全てのフレームについて yi = 1, 2, . . . , K のうち一つの値を付与する．以上の操作は全て人手で行った．得られたシーケンス数は運
転者ごとに異なり，またシーケンス長の正規化も行っていない．実験では弱識別器 h として decision stump 識別
器 [12] を用いた．学習および識別は同じド ライバーの時
系列シーケンスデータを 6-fold cross validation を用いて行った．
双方の実験において，識別率はシーケンス単位で計算する．全 K 種の動作それぞれについてシーケンス識別率を算出し，K クラスの平均識別率でもって学習された識別器を評価する．

ンスデータ集合に対する K = 10 クラスの平均識別率で4. 2 比 較 手 法

ある．強識別器 Hk に対して，テスト時系列シーケンス
を L(<= T ) フレーム目まで入力したときに，どれだけ正確にクラスを識別できるかを測ることで，早期認識モデル
としての性能を評価する．縦軸は平均識別率，横軸が入力されるシーケンス長，すなわち時刻フレーム数 L を表す．太青線は提案法である Earlyboost.MH による識別率の時間発展を示し ，赤細線は既存手法である Earlyboostによる識別率の推移である．
最初の 10 フレームほどでは提案法がわずかに劣る結果になっているが，その後提案法が既存手法を上回る認識率を示している．特に 40 ∼ 45 フレーム付近では，10%以上の識別率向上を記録している．これは式 (16) にある
ように多クラス間の識別スコアを利用した学習則を設計しているからであると考えられる．この結果より，K ク
ラスの間の関係を無視しない提案法のモデルの有効性が良く証明されたと考えられる．
次に，運転動作識別実験の結果を示す．図 3 は 7 人の運転者の平均識別率の時間発展のグラフである．太青線

提案法の比較対象としては，オリジナルの Earlyboost [9]は提案法である Earlyboost.MH による識別率の時間発展を用いた．Earlyboost は 2 クラス用識別器のため，本実を示し，赤細線は既存手法である Earlyboost による識別験では多クラスへの対応が必要となる．本実験では計算率の推移である．図より明らかなように，Earlyboost.MH

量の観点で公平を期すため [9] とは異なる単純な方法にによる認識率は既存法を大幅に上回っており，手書き数

よる多クラス対応を行った．すなわち K 種のクラスそ字認識実験の場合に比べてもその差は歴然としている．

れぞれに対し て one vs. all タイプ の 2 クラス強識別器

これはおそらくデータの特性によるものと思われる．

(式 (6)) を生成する方法である．
各 2 クラス識別器は時系列シーケンス x が「 クラス kに属する (y = 1) 」か「他のクラスに属する (y = −1) 」を学習する．ただし，全 K 個の強識別器はそれぞれ独立に学習する点が提案法である Earlyboost.MH との相違点となる．識別フェーズではテストシーケンス x を全ての強識別器へと入力する．ただし今回は式 (11) のように sign関数を用いず式 (17) のように弱識別器出力の重み付きスオンライン手書き数字認識の場合，書かれた数字 (クラス) によってシーケンスの始点がある程度分離されていると思われる．また，その後のペン先の移動シーケンスに関しても，例えば ”1” と “3” などはまったく相関を持たないであろう．すなわち，手書き文字認識データにおいては各クラスのシーケンスの時間発展にある程度の独立性が予想できる．従って，提案法のように K クラスの識別能力の関係をモデルにとりこまなくてもある程度良⼂೎₸䈱ᤨ㑆⊒ዷ䉫䊤䊐䋨ᚻᦠ䈐ᢥሼ䋩⼂೎₸䈱ᤨ㑆⊒ዷ䉫䊤䊐䋨ㆇォേ૞䋩

1

1

0.9

0.9

0.8

0.8

0.7

ᐔဋ⼂೎₸

ᐔဋ⼂೎₸

0.6
0.5
0.4
0.3

0.6
0.5
0.4

0.2

0.3

earlyboost.MH
earlyboost

0.1
0

0.7

0

5

10

15

20

25

30

35

40

45

Earlyboost.MH
Earlyboost

0.2
0.1
0

50

20

40

60

ᤨೞ䊐䊧䊷䊛
図 2 手書き文字データの平均識別率の時間発展グラフ．太線
は Earlyboost.MH, 細線は Earlyboost による結果．横軸は識別を行う時刻フレーム，縦軸は平均識別率を表す．

80

100

120

140

160

180

ᤨೞ䊐䊧䊷䊛
図 3 Earlyboost.MH(太実線) とオリジナルの Earlyboost(細破線) による 7 運転者の平均動作識別率の時間発展グラフ．
横軸は時刻フレ ームを，縦軸は平均識別率をそれぞれ表す．

好な識別率が得られるものと思われる．これは，とくに認識初期において Earlyboost が提案法を若干上回っていコア rt,k が単調に減少していくことを示唆する．これはることからも予想される．

ある意味で妥当である．なぜなら Earlyboost.MH は早期

一方，動画像からの運転者動作認識実験データでは，認識を実現するために前時刻の弱識別器の誤差を修正す

全てのシーケンスがステアリングを握っている状態からるように学習を進めるからである．よって，時刻が進む

始まっている．これは車内機器操作の早期認識 (予測) とごとに新しい弱識別器によって修正可能な誤りは減っていうタスクからは自然な要請であるが，このために認識

いく．これが識別スコア rt,k の減少を予想させることは

初期では全てのクラスのサンプル分布が分離不可能なほ

明らかであろう．

ど 重複する．また，例えば ” ナビゲーションの操作” と ”

以上の結果より，提案する Earlyboost.MH は，時系列

エアコンの操作” では，機器へと向かう手先位置の移動

シーケンスの早期認識，とくに多クラスの識別に有効で経路もかなり似通ってくる．すなわち，多クラス間の識あることが示された．

別において，クラスごとの分布の相関が非常に強いデー⼂೎₸䈱ᤨ㑆⊒ዷ䋨㊀䉂વ᠞䈱᦭ή䋬ㆇォേ૞䋩タである．従って，各クラスの強識別器を独立に学習す1

る Earlyboost 法では高い識別率を得られない一方，全クラスの相関を考慮して学習を行う Earlyboost.MH 法は良0.9

好な認識結果を得ることができたものと考えられる．

0.8

るようなデータにおいては非常に良好に性能を発揮できると結論できる．
次に，図 4 では重み伝播の効果の大きさを観察する．
太青線は提案した Earlyboost.MH による識別率の推移である．細赤線は式 (15) に示す重み伝播を行わず，全ての1
Dt (i, k) を等しい値 ( NK
) に固定した場合の識別率推移である．図より明らかなように，最終的な識別率，さらに少ないフレーム数における早期認識の識別率の向上率の両点において重み伝播の効果が顕著であることが見て取れる．
最後に，ある運転者のデータに対して学習された識別重み αt の時間発展を図 5 に示す．興味深いことに，識別重み αt は時間経過とともに単調に減少している．αt は∑式 (16) によって計算されるため， rt,k が減少すると αtも減少する．このことは，ht,k によって得られる識別ス

ᐔဋ⼂೎₸

すなわち，提案法は各クラスの間に相関が強く疑われ

0.7
0.6
0.5
0.4
0.3
Earlyboost.MH
Earlyboost.MH 䋨㊀䉂વ᠞ή䈚䋩

0.2
0.1

0

20

40

60

80

100

120

140

160

180

ᤨೞ䊐䊧䊷䊛

図 4 7 人の運転者による車内動作の平均動作識別率の時間発展グラフ．太実線は Earlyboost.MH, 細破線は重み伝播を行わない Earlyboost.MH による結果．横軸は識別を行う
時刻フレーム，縦軸は平均識別率を表す．

⼂೎䉴䉮䉝αt䈱ᤨ㑆ᄌൻ䋨ㆇォേ૞䋩
1.4
1.2
1

⼂೎䷸䷲䷡

0.8
0.6
0.4
0.2
0

0

20

40

60

80

100

120

140

160

180

ᤨೞ䊐䊧䊷䊛
図 5 ある運転者における識別重み αt の学習結果. 横軸は時刻
フレーム t を，縦軸は αt の値を示す．

5. 結

論

本稿では，多クラスの時系列シーケンスデータを早期認識するための新しいブースティング法を提案した．我々は [9] によって提案された重み伝播法と [10] で提案された Adaboost の多クラス拡張手法を組み合わせた Early-

boost.MH モデルを考案した．Earlyboost.MH はその定義は非常に簡潔で，また学習および識別に必要となる計算量も少なくなっている．実験では，オンライン手書き数
字認識の問題，及び動画像を利用した自動車の運転者動作の認識問題に対し，既存の Earlyboost モデルよりも高い認識性能を示すことを確認した．
提案手法は時系列シーケンスの種類を問わず，様々なデータの早期認識問題に応用可能であると考えられる．
従って，今後は手書き漢字認識データやジェスチャー認
識，音声認識など 様々な時系列データに提案法を適用していきたいと考えている．また，Adaboost は確率・統計モデルとしても研究が進んでいる [14], [15]．こういった
先行研究を参考にして，多クラス早期認識モデルとしての理論的な最適性の検証も行いたいと考えている．
運転者動作データベースを提供していただいた株式会
社デンソー様に感謝いたします．
文

献[1] Y. A. Sheikh, A. Datta and T. Kanade: “On the sustained
tracking of human motion”, Proceedings of 8th IEEE International Conference on Automatic Face and Gesture Recognition (FG) (2008).
[2] 森, 内田, 倉爪, 谷口, 長谷川, 迫江：“ジェスチャの早期認
識・予測ならびにそれらの高精度化のためのネットワー
クモデルに関する検討”, 画像の認識理解シンポジウム予
稿集 (MIRU2005), pp. IS3–106 (2005).
[3] C. Bahlmann and H. Burkhardt: “The writer independent
online handwriting recognition system frog on hand andcluster generative statistical dynamic time warping”, IEEE
Transactions on Pattern Analysis and Machine Intelligence,

26, 3, pp. 299–310 (2004).
[4] T. Hori, C. Hori and Y. Minami: “Fast on-the-fly composition for weighted finite-state transducers in 1.8 million-word
vocabulary continuous speech recognition”, Proceedings of
the 8th International Conference on Spoken Language Processing (Interspeech), Vol. 1, pp. 289–292 (2004).
[5] L. R. Rabiner: “A tutorial on hidden Markov models andselected applications in speech recognition”, Proceedings ofthe IEEE, 77, 2, pp. 257–286 (1989).
[6] V. N. Vapnik: “The Nature of Statistical Learning Theory”,
Springer (1995).
[7] Y. Freund and R. E. Schapire: “A decision-theoretic generalization of on-line learning and an application to boosting”,
Journal of Computing Systems and Science, 55, 1, pp. 119–139 (1997).
[8] J. Sochman and J. Matas: “Waldboost ― learning for time
constrained sequential detection”, Proceedings of IEEE
Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 第 2 巻, pp. 150–156 (2005).
[9] S. Uchida and K. Amamoto: “Early recognition of sequential patterns by classifier combination”, Proceedings of the
19th Internatinal Conference on Pattern Recognition (ICPR)(2008).
[10] R. Schapire and Y. Singer: “Improved boosting algorithms
using confidence-rated predictions”, Machine Learning, 37,3, pp. 297–336 (1999).
[11] 坂野, 山田, 石黒：“誤り訂正学習による動作認識の試み”,
情報処理学会論文誌: 数理モデル化と応用 (TOM), 2, 3,
pp. 153–161 (2009).
[12] C. M. Bishop: “Pattern Recognition and Machine Learning”, Springer-Verlag New York (2006).
[13] T. G. Dietterich and G. Bakiri: “Solving multiclass learning problems via error-correcting output codes”, Journal of
Artificial Intelligence Research, 2, pp. 262–286 (1995).
[14] J. Friedman, T. Hastie and R. Tibshirani: “Additive logistic
regression: A statistical view of boosting (with discussion)”,Annals of Statistics, 28, 2, pp. 337–407 (2000).
[15] H. Zou, J. Zhu and T. Hastie: “New multicategory boosting algorithms based on multicategory Fisher-consistentlosses”, The Annals of Applied Statistics, 2, 4, pp. 1290–
1306 (2008).