(57)【特許請求の範囲】
【請求項１】
サポートベクトルマシンの再学習方法であって、
既知のラベルを有する初期学習用訓練サンプルの集合を用いてＳＶＭを学習する段階と、
前記初期学習用訓練サンプルを摂動処理する段階と、
該摂動処理されたサンプルを追加用訓練サンプルとする段階と、
前記初期学習用訓練サンプルと前記追加用訓練サンプルとを用いて、前記学習されたＳＶＭを再学習する段階とからなり、
前記摂動処理される初期学習用訓練サンプルが、非サポートベクトルに対応する初期学習用訓練サンプルを除去した訓練サンプルであり、ソフトマージン超平面上に存在するサポートベクトルに対応する訓練サンプルであり、かつ該ソフトマージン超平面上のサポートベクトルが他クラスに属する条件付き確率を、最尤推定で求めたロジスティック関数で求めた時の、判別性能が良くない方のソフトマージン超平面上に存在するサポートベクトルに対応する訓練サンプルであることを特徴とするサポートベクトルマシンの再学習方法。
【請求項２】
サポートベクトルマシンの再学習方法であって、
既知のラベルを有する初期学習用訓練サンプルの集合を用いてＳＶＭを学習する段階と、
前記初期学習用訓練サンプルを摂動処理する段階と、
該摂動処理されたサンプルを追加用訓練サンプルとする段階と、
前記初期学習用訓練サンプルと前記追加用訓練サンプルとを用いて、前記学習されたＳＶＭを再学習する段階とからなり、
前記摂動処理される初期学習用訓練サンプルが、非サポートベクトルに対応する初期学習用訓練サンプルを除去した訓練サンプルであり、ソフトマージン超平面上に存在するサポートベクトルに対応する訓練サンプルであり、かつ該ソフトマージン超平面上のサポートベクトルが他クラスに属する条件付き確率を、最尤推定で求めたロジスティック関数で求めた時の、判別性能が良くない方のソフトマージン超平面上に存在するサポートベクトルに対応する訓練サンプルであり、
画像処理のショット境界検出に用いられることを特徴とするサポートベクトルマシンの再学習方法。
【請求項３】
請求項２に記載のサポートベクトルマシンの再学習方法であって、
前記摂動処理が、映像の明度変換、コントラスト変換、ぼかし変換、またはエッジ強調であることを特徴とするサポートベクトルマシンの再学習方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はサポートベクトルマシンの再学習方法に関し、特に識別性能の向上と演算量の削減を図ることができるサポートベクトルマシンの再学習方法に関する。
【背景技術】
【０００２】
映像アーカイブ（動画素材集）の検索や管理を行うシステムにとって、既存の映像ファイルから編集作業で生じたショットの境界を検出するショット境界検出の機能は必須の機能である。このため、サポートベクトルマシン（以下、ＳＶＭと記す）を適用し、高性能のショット境界検出器が実現されている。
【０００３】
下記の特許文献１には、ショット境界を検出するための特徴量抽出方法が開示されている。該文献１に明示されているように、得られた特徴量はＳＶＭなどのパターン認識装置によって識別が行われる。ＳＶＭの場合、予め用意した訓練サンプルで学習を行い、識別用のＳＶＭを構築することを前提にしている。また、特許文献２には、能動学習法を用いて行われた学習結果に基づいて、サポートベクトルマシンがデータ分類を行うデータ分類装置についての発明が開示されている。
【０００４】
また、半自動学習（semi-supervised learning）と呼ばれる従来技術がある。半自動学習では、既知のラベル付サンプル集合から構築した学習器を使って、アンラベルのサンプル集合の中からラベル付与済みの事例に近いものを抽出し、抽出がほぼうまくいったことを前提にさらなる学習（「再学習」と呼ぶ）を行うことで、識別器の性能向上を目指すものである。この技術をSVMに適用する場合の拡張手法が非特許文献１で述べられている。
【特許文献１】特開２００７−１４２６３３号公報
【特許文献２】特開２００４−２１５９０号公報
【非特許文献１】日本オペレーションズ・リサーチ学会「SVMを基にしたSemi-Supervised  Learning」日本オペレーションズ・リサーチ学会秋期研究発表会アブストラクト集、Vol.2005(20050914) pp.32-33
【発明の開示】
【発明が解決しようとする課題】
【０００５】
前記特許文献１と非特許文献１の技術を組み合わせる、つまり、ショット検出用の識別器（ＳＶＭ）に半自動学習の技術を適用すれば、識別性能が向上する可能性はある。しかし、通常の半自動学習では、再学習のために追加するサンプルのラベルは、再学習前の識別器が付与するために誤っているものを含む場合も多い。誤ってラベル付けされたものを含むサンプルを学習すると、再学習後の性能は十分に向上しないという問題がある。
【０００６】
また、非特許文献１が提示した手法では、追加するサンプル数が膨大になり、再学習が非常に困難になるといった問題もある。
【０００７】
本発明の目的は、前記した従来技術の問題点に鑑み、良質で少数のサンプルを用いて再学習させることにより、ＳＶＭの精度向上と計算量の削減を達成できるサポートベクトルマシンの再学習方法を提供することにある。
【課題を解決するための手段】
【０００８】
前記した目的を達成するために、本発明は、サポートベクトルマシンの再学習方法であって、既知のラベルを有する初期学習用訓練サンプルの集合を用いてＳＶＭを学習する段階と、前記初期学習用訓練サンプルを摂動処理する段階と、該摂動処理されたサンプルを追加用訓練サンプルとする段階と、前記初期学習用訓練サンプルと前記追加用訓練サンプルとを用いて、前記学習されたＳＶＭを再学習する段階とからなり、前記摂動処理される初期学習用訓練サンプルが、非サポートベクトルに対応する初期学習用訓練サンプルを除去した訓練サンプルであり、ソフトマージン超平面上に存在するサポートベクトルに対応する訓練サンプルであり、かつ該ソフトマージン超平面上のサポートベクトルが他クラスに属する条件付き確率を、最尤推定で求めたロジスティック関数で求めた時の、判別性能が良くない方のソフトマージン超平面上に存在するサポートベクトルに対応する訓練サンプルであるようにした点に特徴がある。
【発明の効果】
【００１２】
本発明による摂動学習では，映像データに輝度変換等の画像処理を行ってもショット境界の位置は変わらないことを利用し，新たな特徴量を持った訓練用サンプルを生成する。このため、新たに追加する訓練用サンプルのラベル付与が正確である点が通常の半自動学習と大きく異なり、再学習の効果が向上する。
【００１３】
また、既存の境界面から離れているサンプルを摂動させても，非サポートベクトルとして境界面の位置に影響を与えない可能性が高い。よって、非サポートベクトルは摂動の対象外とすることで、精度向上ならびに計算量削減が達成できる。
【００１４】
また、分類境界付近にあるα=Cとなるサポートベクトルはoutlier（外れ値）である可能性が高い。このため、摂動で新規サンプルを追加した場合の効果が限定的でリスクが大きいことから、摂動対象をマージン超平面上に存在するサポートベクトルに限定することで、精度向上と計算量削減が達成できる。
【００１５】
さらに、ショット境界検出のようにクラス間でサンプル数に偏よりがある場合は、マージン超平面付近で他クラスとの分離精度がさほど良くないので、最尤推定で求めたロジスティック関数で、ソフトマージン超平面上のサポートベクトルが他クラスに属する条件付き確率を求め、判別性能が良くない方の超平面のサポートベクトルのみを摂動対象にすることで、精度向上と計算量削減が達成できる。
【発明を実施するための最良の形態】
【００１６】
以下に、図面を参照して、本発明を詳細に説明する。図１は、本発明の第１実施形態の概略の処理手順を示すフローチャートである。
【００１７】
この実施形態は、学習用に用いる映像データに対し、明度変換やコントラスト変換を施し、境界検出に使用する特徴量の値を変化させ（以下「摂動」と呼ぶ）、新たな学習用サンプルを生成するようにしたものである。
【００１８】
まずステップＳ１において、初期学習用訓練サンプルの集合を用意する。該初期学習用訓練サンプルの集合としては、既知のクラスラベル｛ｙ１，ｙ２，ｙ３，・・・・，ｙｍ｝を有するデータ｛ｘ１，ｘ２，ｘ３，・・・・，ｘｍ｝を用意する。ステップＳ２では、前記初期学習用訓練サンプルの集合を用いて、ＳＶＭを初期学習（パイロット学習）する。この処理により、初期学習されたＳＶＭ（１）が得られると共に、該初期学習用訓練サンプルに対応したパラメータ（α値）が得られる。該パラメータ（α値）の意味については後述する。ステップＳ３では、該初期学習用訓練サンプルを摂動処理する。該摂動処理の詳細は後述する。
【００１９】
摂動処理された初期学習用訓練サンプルサンプル（以下、新サンプル）の特徴量は当然初期学習用訓練サンプルの特徴量と異なるが、新サンプルのクラスラベルは初期学習用訓練サンプルのクラスラベルを引き継いでいる。ステップＳ４では、該摂動されたサンプルを追加用訓練サンプルとする。ステップＳ５では、前記初期学習用訓練サンプルと追加用訓練サンプルとを用いてＳＶＭを再学習を行い、再学習後のＳＶＭ（２）を生成する。この時、各訓練用サンプルに対応したパラメータ（α値）が得られる。ステップＳ６では、該再学習処理を終了するか否かの判断を行い、否定の場合にはステップＳ３に戻って前記した処理を繰り返す。処理を繰り返すことにより、さらに再学習されたＳＶＭ（３）、（４）、・・・を得ることができる。一方、ステップＳ６が肯定の場合には、再学習処理を終了する。
【００２０】
この実施形態によれば、前記追加用訓練サンプルは、初期学習用訓練サンプルのクラスラベルを引き継いでいるので、従来のクラスラベルなしのサンプルを用いて再学習するのに比べて、ＳＶＭの精度向上と計算量の削減を図ることができる。
【００２１】
次に、本発明の第２実施形態を図２を参照して説明する。この実施形態は、第１実施形態のように、摂動で得られる新サンプルを全てオリジナルのサンプル集合に追加して再学習を行なう方法だと、追加後のサンプル数が膨大になり、学習すなわち境界面の最適化計算が計算量の点で困難になる。 そこで、追加すべき新サンプルを選択するようにしたものである。なお、この新サンプルの選択には、多少の識別誤りを許容して線形分離を行う周知のソフトマージンが用いられる。
【００２２】
図２において、ステップＳ１とＳ２は図１と同じであるので説明を省略する。ステップＳ１０では、非サポートベクトルに対応するサンプルを除去する。この処理は、ステップＳ２の処理で得られるサポートベクトル情報、つまりパラメータ（α値）を基に実施できる。詳細は、後述する。ステップＳ１１では、前記除去後のサンプルに対して摂動処理を行い、該摂動されたサンプルを追加用訓練サンプルとして再学習する。なお、非サポートベクトルに対応するサンプルの除去については、後で詳述する。
【００２３】
非サポートベクトルのサンプルは識別の境界面から離れているサンプルであるので、該サンプルを摂動させても、境界面の位置に影響を与えない可能性が高い。よって、この実施形態によれば、非サポートベクトルを摂動の対象外とすることで、精度の向上と計算量の削減とを達成できる。
【００２４】
次に、本発明の第３実施形態を図３を参照して説明する。この実施形態は、初期学習用訓練サンプルの集合にoutlier（外れ値）が存在する現実的な状況下では、外れ値がミスラベルであった場合、その外れ値に対する摂動はSVMの再学習に悪影響を与える可能性が高い。そこで、計算量的にもメリットもあることから、摂動対象をさらにマージン超平面上に存在するサポートベクトル（non-bounded support vectors）に限定するようにしたものである。
【００２５】
図３において、ステップＳ１とＳ２は図１と同じであるので説明を省略する。ステップＳ２のサポートベクトル情報は、既知のクラスラベルの初期学習用データを初期学習して得られたものであるが、後述するように、数％例えば２％（＝０．０２）の誤分類確率がある。そこで、誤ってラベル付けされたデータを再学習に用いないようにするために、ステップＳ２１では、摂動対象を、ソフトマージン超平面上に存在するサポートベクトルに対応するサンプルとする。ステップ２２では、該選択されたサンプルを摂動処理する。前記ステップＳ２１，Ｓ２２の処理の詳細は後述する。ステップＳ１２では、該摂動処理されたサンプルを追加用訓練サンプルとし、ステップＳ１３では前記初期学習用訓練サンプルと該追加用訓練サンプル用いて再学習を行いＳＶＭ（２）を生成する。
【００２６】
本実施形態は、新たに追加する訓練用サンプルのラベル付与が正確である点で、従来および第１、第２実施形態の半自動学習と異なり、再学習の効果が高くなる。
【００２７】
前記第３の実施形態を、以下により具体的に説明する。以下では、映像の瞬時カットにおけるショット境界の検出を例にして説明するが、本発明はこれに限定されず、画面が徐々に暗くなりながら次のショットに移行するフェードアウトや、映像がオーバーラップしながら徐々に切り替わるディゾルブといった種々のショット境界の検出にも適用することができる。また、映像のショット境界の検出に限らず、他の対象の分類または識別にも応用することができる。
【００２８】
さて、通常のSVMでは、多少の識別誤りを許容して線形分離を行うソフトマージンが用いられる。ショット境界検出のデータも明らかに写像空間上で線形分離は可能ではないため、ソフトマージンによるＳＶＭで学習を行うことになる。このソフトマージン用のハイパーパラメータの値をCで表す。また、分類関数Φ（ｘ）を以下のように表記する。
【００２９】
【数１】
0005196425.tif 000002
ただし、０≦αｉ≦Cである。
【００３０】
ｘｉは学習用のサンプルデータ、ｘはサンプル、ｙｉ（＝＋１または−１）はクラスラベル、αｉは内部パラメータ、例えばラグランジェ乗数（Lagrange乗数）を表す。本実施形態の場合、ｙ＝−１のサンプルはショット境界であり、ｙ＝＋１の時はショット境界ではない。
ｋ（ｘｉ，ｘｊ）は、カーネル関数であり、ガウスカーネルだと、ｋ（ｘｉ，ｘｊ）＝exp｛−γ・‖ｘｉ−ｘｊ‖｝となる。
【００３１】
０＜αｉに対応するサンプルはサポートベクトルと呼ばれる。特に０＜αｉ＜Cのサポートベクトルは、マージン超平面Ｈ１、Ｈ２上に存在することになる。
【００３２】
学習済みSVMで得られるクラス推定結果の分布をロジスティック関数で近似すると識別性能が向上することが多い。実際、ショット境界検出では、ロジスティック関数を用いたほうが精度が向上する。
【００３３】
【数２】
0005196425.tif 000003
とすると、各クラスの条件付き確率を表すロジスティック関数Ｐは以下の式で表わされる。
【００３４】
【数３】
0005196425.tif 000004
Ａ，Ｂは訓練用のサンプルデータから最尤推定で計算される。
【００３５】
図４は、実際のカット検出（=ショット境界検出の部分問題）の訓練用データから構築したSVMのロジスティック関数のグラフである。横軸はｆ（ｘ）、縦軸は確率である。「ショット境界事例のクラス(ｙ＝−１)」のソフトマージン超平面上に存在するサンプルｘでは、ｆ(x)=−１の関係が成り立つ。よって、サンプルｘでは、Ｐ(ｙ＝＋１｜ｘ)=０．０２、Ｐ(ｙ＝−１｜ｘ) ＝０．９８であり、 Ｐ(ｙ＝−１｜ｘ)＞Ｐ(ｙ＝＋１｜ｘ)であるから、ｘのクラスは「ショット境界事例のクラス」と判定される。ただし、誤分類確率は０．０２と低くはない。なお、前記ロジスティック関数のグラフは、Ｂ／Ａの値により、左右に平行移動する。
【００３６】
ＳＶＭ学習を一回実行すると（前記ステップＳ２）、各訓練サンプルｉに対応したパラメータαｉの値が得られる。αｉ＝０となる非サポートベクトルは、原理上、識別境界面の位置に影響を与えない。図５が示すように、非サポートベクトル□、○は境界面Ｓからも比較的離れた位置にある。これらのサンプルを摂動させて、新サンプルを生成しても既存の境界面から離れているため、学習用に追加しても、非サポートベクトルとして境界面Ｓの位置に影響を与えない可能性が高い。よって、非サポートベクトルは摂動の対象外とした方が良い。サポートベクトルの数と非サポートベクトルの割合は、通常、非サポートベクトルの割合の方が大きいため、摂動対象をサポートベクトルに限定することは、計算量削減の効果も高くなる。
【００３７】
分類境界付近にあるαｉ＝Ｃとなるサポートベクトルはoutlier（外れ値）である可能性が高い。外れ値の原因がミスラベルであるか、稀有なノイズによるものかを自動的に判断することは困難である。αｉ＝Ｃとなるサポートベクトルを新規サンプルとして追加するとリスクが大きいことから、摂動対象を０＜αｉ＜Ｃとなるマージン超平面上に存在するサポートベクトル（non-bounded support vectors）■、●に限定する。この処理は、前記ステップＳ２１に相当する。
【００３８】
次に、摂動によるラベル付きサンプルの生成処理（前記ステップＳ２２）について説明する。
【００３９】
摂動の一例として、映像の画質変換が考えられる。画質変換は、輝度を全体的に上げたり下げたりする場合（明度変換）と、コントラストを強めたり弱めたりする場合（コントラスト変換）がある。それぞれの場合の輝度変換の式を以下に示す。
・明度変換の場合
【００４０】
Z´＝256.0 ×〔Z÷256.0〕δ
Z：入力輝度情報（0〜255）
Z´：出力輝度情報（0〜255）
δ：明度変換調整パラメータ
・コントラスト変換の場合
【００４１】
Z´= 256.0 ÷ ( 1.0 + exp(-η×( Z −128.0 ) ) ) 
Z：入力輝度情報（0〜255）
Z´：出力輝度情報（0〜255）
η：コントラスト変換調整パラメータ
【００４２】
図６は今回使用した画質変換の例である。中央の画像がソフトマージン超平面上の画像であり、上段の画像はコントラストが弱くされ、下段の画像はコントラストが強くされている。また、右列の画像は明度が高く、左列の画像は明度が低くされている。
【００４３】
なお、前記明度変換、コントラスト変換以外にも、ぼかし変換、エッジ強調などの摂動をしてもよい。
【００４４】
本発明の摂動学習では、映像データに輝度変換等の画像処理を行ってもショット境界の位置は変わらないことを利用し、新たな特徴量を持った訓練用サンプルを生成するようにしている。初期学習用（オリジナル）データでのクラスラベル付与に間違いがない限り、新たに追加する訓練用サンプルのクラスラベル付与が正確である点が、通常の半自動学習と大きく異なる。
【００４５】
次に、本発明の第４実施形態を説明する。本実施形態で対象としているショット境界検出の問題では、ショット境界の事例の数はショット境界でない事例の数に比べて圧倒的に少ない。このため、sigmoid training で得たロジスティック関数が示す条件付確率を求めると、「ショット境界でない事例のクラス」の側のマージン超平面上に存在するサポートベクトルにおいて「ショット境界の事例のクラス」である確率がほぼゼロであるのに対し、「ショット境界の事例のクラス」のマージン超平面上に存在するサポートベクトルでは、「ショット境界でない事例のクラス」の確率は多少大きい。このことから、本実施形態では、摂動対象として、他方のクラスの条件付確率がある閾値以上のマージン超平面上のサポートベクトルに限定する。
【００４６】
前記のように、本実施形態で対象としているショット境界検出の問題ではショット境界の事例の数はショット境界でない事例の数に比べて圧倒的に少ないため、図４のロジスティック関数での判別位置がｆ（ｘ）＝−０．５８と左側（ｙ＝−１、つまりショット境界であるクラスの側）に入り込んでいる。前述したように、ｆ（ｘ）＝−１でソフトマージン超平面上にあるサンプルですら、「ショット境界でないクラス」の条件付確率がゼロになっていない。このことは、写像空間の該当超平面付近に２つのクラスが混じっていることを示している。反対に、ショット境界でないクラスのソフトマージン超平面を表すｆ（ｘ）＝＋１では、ショット境界でないクラスの条件付き確率はほぼ１．０であることから、超平面の付近は、ショット境界でないクラスの事例だけで構成されていることになる。ｆ（ｘ）＝−１の超平面上にあるサポートベクトルは、付与されたラベルの信頼度も高く、付近の他クラス（＝ショット境界でないクラス）との分離もさほど良くないことから、付近に新サンプルを追加するのに適した位置である。よって、ショット境界検出のようにクラス間でサンプル数に偏よりがある場合は、最尤推定で求めたロジスティック関数で、ソフトマージン超平面上のサポートベクトルが他クラスに属する条件付き確率を求め、判別性能が良くない方の超平面のサポートベクトルのみを摂動対象にするとよい。
【００４７】
以上、前記した各実施形態によれば、ＳＶＭの精度向上ならびに計算量削減が達成できる。また、本発明は上記の実施形態に限定されされず、本発明を逸脱しない範囲の種々の変形も含むことは明らかである。
【図面の簡単な説明】
【００４８】
【図１】本発明の第１実施形態の概略の処理手順を示すフローチャートである。
【図２】本発明の第２実施形態の概略の処理手順を示すフローチャートである。
【図３】本発明の第３実施形態の概略の処理手順を示すフローチャートである。
【図４】瞬時カット検出の訓練データから得られる条件付き確率を示すロジスティック関数のグラフである。
【図５】ソフトマージンを表す超平面とサポートベクトルとの写像空間上での位置関係を説明する図である。
【図６】画質変換の例を示す図である。
【符号の説明】
【００４９】
Ｈ１，Ｈ２・・・超平面、Ｓ・・・境界面
【図１】
0005196425.tif 000005
【図２】
0005196425.tif 000006
【図３】
0005196425.tif 000007
【図４】
0005196425.tif 000008
【図５】
0005196425.tif 000009
【図６】
0005196425.tif 000010