(57)【要約】      （修正有）【課題】ＳＶＭの性能を低下させることなくサポートベクトルを削減できる方法を提供する。【解決手段】既知のラベルを有する初期学習用訓練サンプルの集合を用いてＳＶＭを学習する段階と、前記ＳＶＭの学習により得られたパラメータα値を基に外れ値（０より大きくＣ以下の値）に対応する初期学習用訓練サンプルを求める段階と、該外れ値に対応する初期学習用訓練サンプルを当初の初期学習用訓練サンプルの集合から除去する段階とからなる。【選択図】図１
2009211648.tif 000002
【特許請求の範囲】
【請求項１】
サポートベクトルの削減方法であって、
既知のラベルを有する初期学習用訓練サンプルの集合を用いてＳＶＭを学習する段階と、
前記ＳＶＭの学習により得られたパラメータα値を基に外れ値に対応する初期学習用訓練サンプルを求める段階と、
該外れ値に対応する初期学習用訓練サンプルを当初の初期学習用訓練サンプルの集合から除去する段階とからなるサポートベクトルの削減方法。
【請求項２】
請求項１に記載のサポートベクトルの削減方法であって、
前記外れ値に対応する初期学習用訓練サンプルが、一方のソフトマージン超平面付近のサンプルであることを特徴とするサポートベクトルの削減方法。
【請求項３】
請求項１に記載のサポートベクトルの削減方法であって、
前記外れ値に対応する初期学習用訓練サンプルが、パラメータα値の値がソフトマージン用のハイパーパラメータＣの値に等しいサンプルであることを特徴とするサポートベクトルの削減方法。
【請求項４】
請求項１ないし３のいずれかに記載のサポートベクトルの削減方法であって、
前記外れ値に対応する初期学習用訓練サンプルが除去された訓練サンプルを用いてＳＶＭを再学習する段階と、
該再学習により得られたパラメータα値を基にサポートベクトルを求め、同じクラスに属する２個の最も近いサポートベクトルから１個の新しいベクトルを作り、該２個のサポートベクトルを該新しい１個のサポートベクトルに置換する段階とをさらに備えたサポートベクトルの削減方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はサポートベクトルの削減方法に関し、特に、サポートベクトルマシン（ＳＶＭ）の再学習に使用して好適なサポートベクトルを削減する方法に関する。
【背景技術】
【０００２】
特許文献１ならびに該特許文献１で従来技術として引用されている既存文献では、ショット境界を検出するための特徴量抽出手法が開示されている。特許文献１が明示するように、得られた特徴量はサポートベクトルマシン（ＳＶＭ）等のパターン認識装置によって識別が行われる。ＳＶＭの場合、識別処理に先立ち、あらかじめ用意した訓練サンプルで学習を行ない、サポートベクトルとよぶ、識別用のモデルデータを構築しておく。
【０００３】
一方、ＳＶＭによる識別処理の場合、モデルとして使用されるサポートベクトルの数に比例して、識別処理の時間がかかる。このため、識別精度を犠牲にしても処理を高速化する必要がある場合、サポートベクトルの数を減らしモデルを簡約化しなければいけない。そこで、非特許文献１には、構築した識別器の識別性能をあまり低下させずにサポートベクトルの数を減らすための具体的な手法が開示されている。
【特許文献１】特開２００７−１４２６３３号公報
【非特許文献１】“An Efficient Method for Simplifying Support Vector Machines”, Proc. of 22nd Int. Conf. Machine learning, Bonn, Germany, 2005, Aug. pp.617-624
【発明の開示】
【発明が解決しようとする課題】
【０００４】
特許文献１と非特許文献１の技術を組み合わせる、つまり、ショット検出用の識別器（ＳＶＭ）を一旦、学習によって構築し、その後、サポートベクトルを削減すれば、精度をあまり落とさずに、高速なＳＶＭによる識別器を構築できる可能性がある。しかし、非特許文献１では、outlier（外れ値）の存在を考慮していないため、サポートベクトル削減前の本来の識別境界近辺に外れ値が存在した場合、外れ値は削減対象にならず、最適な簡略化が行えない。この結果、サポートベクトル削除後の識別器の性能が当初に比べ急激に悪くなる現象が発生することがある。
【０００５】
本発明は、前記した従来技術に鑑みてなされたものであり、その目的は、ＳＶＭの性能を低下させることなくサポートベクトルを削減できる方法を提供することにある。
【課題を解決するための手段】
【０００６】
前記した目的を達成するために、本発明は、サポートベクトルの削減方法であって、既知のラベルを有する初期学習用訓練サンプルの集合を用いてＳＶＭを学習する段階と、前記ＳＶＭの学習により得られたパラメータα値を基に外れ値に対応する初期学習用訓練サンプルを求める段階と、該外れ値に対応する初期学習用訓練サンプルを当初の初期学習用訓練サンプルの集合から除去する段階とからなる点に第１の特徴がある。
【０００７】
また、本発明は、前記外れ値に対応する初期学習用訓練サンプルが、一方のソフトマージン超平面付近のサンプルである点に第２の特徴がある。
【発明の効果】
【０００８】
本発明によれば、外れ値を除去した後に再学習を行なって得られるＳＶＭ（識別器）のサポートベクトル数は、再学習前の初期学習用サポートベクトルの数より小さくなるに関わらず、殆ど識別精度は低下しないか、逆に汎化性が高まったことで識別精度が向上することが実験で確かめられている。
【０００９】
また、一方のソフトマージン超平面付近の外れ値を除去することにより、画像のショット境界検出に好適なＳＶＭの再学習を高速で行えるようになる。
【００１０】
さらに、外れ値除去によるサポートベクトルの削減後に、非特許文献１の手法でサポートベクトル数を削減することにより、非特許文献１の手法のみで削減した場合に比べ、識別性能を損なうことなく、サポートベクトルの削減効果が大きくなる。
【発明を実施するための最良の形態】
【００１１】
以下に、図面を参照して、本発明を詳細に説明する。本発明の概要は次の通りである。まず、訓練用データ（訓練サンプルの集合）で初期学習（パイロット）学習を行ない、一旦サポートベクトルの集合を生成する。次に、サポートベクトルに対応した内部パラメータ（α値）が閾値以上のものに対応する訓練サンプルを除去する処理、すなわち外れ値の除去処理をする。次に、残った訓練サンプルデータで再学習を行ない、サポートベクトル集合を生成する。次に、前記非特許文献１に記されている手法でサポートベクトルを最終的に削減する。
【００１２】
次に、本発明の一実施形態を、図１のフローチャートを参照して説明する。  
【００１３】
まずステップＳ１において、初期学習用訓練サンプルｉ（ｉ＝１，２，・・・，ｍ）の集合を用意する。該初期学習用訓練サンプルの集合としては、既知のクラスラベル｛ｙ１，ｙ２，ｙ３，・・・・，ｙｍ｝を有するデータ｛ｘ１，ｘ２，ｘ３，・・・・，ｘｍ｝を用意する。ステップＳ２では、前記初期学習用訓練サンプルの集合を用いて、ＳＶＭを初期学習する。この処理により、初期学習されたＳＶＭ（１）が得られると共に、該初期学習用訓練サンプルｉに対応したパラメータ（αｉ値）が得られる。
【００１４】
ステップＳ３では、該パラメータαｉを基に、外れ値に対応する初期学習用訓練サンプルｉ’を求め、当初の初期学習用訓練サンプルｉの集合から、該外れ値に対応する初期学習用訓練サンプルｉ’を削除する。外れ値については、後で詳述する。
【００１５】
ステップＳ４では、削減後の訓練サンプルを用いて、ＳＶＭ（１）を再学習する。これにより、各訓練サンプルに対応したパラメータα値を得る。ステップＳ５では、非特許文献１の方法を用いて、訓練サポートベクトルをさらに削減する。なお、該非特許文献１のサポートベクトル削減方法の詳細は該非特許文献１に詳細に記されているので説明を省略するが、その原理は、同じクラスに属する２個の最も近いサポートベクトルから１個の新しいベクトルを作り、該２個のサポートベクトルを該新しい１個のサポートベクトルに置換することにより、サポートベクトルを削減するものである。
【００１６】
さて、通常のSVMでは、多少の識別誤りを許容して線形分離を行うソフトマージンが用いられる。ショット境界検出のデータも明らかに写像空間上で線形分離は可能ではないため、ソフトマージンによるＳＶＭで学習を行うことになる。このソフトマージン用のハイパーパラメータの値をCで表す。また、分類関数Φ（ｘ）を以下のように表記する。
【００１７】
【数１】
2009211648.tif 000003
ただし、０≦αｉ≦Cである。
【００１８】
ｘｉは学習用のサンプルデータ、ｘはサンプル、ｙｉ（＝＋１または−１）はクラスラベル、αｉは内部パラメータ、例えばラグランジェ（Lagrange）乗数を表す。本実施形態の場合、ｙ＝−１のサンプルはショット境界であり、ｙ＝＋１の時はショット境界ではない。
ｋ（ｘｉ，ｘｊ）は、カーネル関数であり、ガウスカーネルだと、ｋ（ｘｉ，ｘｊ）＝exp｛−γ・‖ｘｉ−ｘｊ‖｝となる。
【００１９】
０＜αｉに対応するサンプルはサポートベクトルと呼ばれる。特に０＜αｉ＜Cのサポートベクトルは、マージン超平面Ｈ１、Ｈ２上に存在することになる。この詳細は、図３を参照して後述する。
【００２０】
学習済みSVMで得られるクラス推定結果の分布をロジスティック関数で近似すると識別性能が向上することが多い。実際、ショット境界検出では、ロジスティック関数を用いたほうが精度が向上する。
【００２１】
【数２】
2009211648.tif 000004
とすると、各クラスの条件付き確率を表すロジスティック関数Ｐは以下の式で表わされる。
【００２２】
【数３】
2009211648.tif 000005
Ａ，Ｂは訓練用のサンプルデータから最尤推定で計算される。
【００２３】
図２は、実際のカット検出（=ショット境界検出の部分問題）の訓練用データから構築したSVMのロジスティック関数のグラフである。
【００２４】
ＳＶＭ学習を一回実行すると（前記ステップＳ２）、各訓練サンプルｉに対応したαｉの値が得られる。図３に示されているように、αｉ＝０となるベクトル□、○は非サポートベクトル、０＜αｉ≦Ｃとなるベクトルはサポートベクトルであり、０＜αｉ＜Ｃのサポートベクトル■、●は、マージンＨ１，Ｈ２上にある。また、αｉ＝Ｃのサポートベクトルは、マージンを越えるサポートベクトルである。
【００２５】
また、前記αｉの値がある閾値以上である時、対応する訓練サンプルは外れ値と判定する。この閾値は、必要に応じて適当な大きさの値（ただし、０より大きくＣ以下の値）に設定することができる。好ましい一例として、該閾値をＣとして、前記外れ値に対応する初期学習用訓練サンプルが、パラメータα値の値がソフトマージン用のハイパーパラメータＣの値に等しいサンプルであるようにすることができる。
【００２６】
外れ値であるサポートベクトルは、分類境界面Ｓの付近にある可能性が高く、ミスラベルされている可能性がある。このため、該外れ値であるサポートベクトルを新規サンプルとして追加すると、ＳＶＭの性能を劣化させる可能性が生ずる。
【００２７】
したがって、本実施形態によれば、外れ値であるサポートベクトルを除去した分だけＳＶＭの再学習に使用されるサポートベクトルの数は少なくなるが、それにもかかわらず、ＳＶＭの識別精度は殆ど劣化しない。一方、サポートベクトルの数が少なくなった分、再学習速度が向上する。
【００２８】
次に、本発明の第２実施形態を説明する。本実施形態で対象としているショット境界検出の問題では、ショット境界の事例の数はショット境界でない事例の数に比べて圧倒的に少ない。このため、sigmoid training で得たロジスティック関数が示す条件付確率を求めると、「ショット境界でない事例のクラス」の側のマージン超平面上に存在するサポートベクトルにおいて「ショット境界の事例のクラス」である確率がほぼゼロであるのに対し、「ショット境界の事例のクラス」のマージン超平面上に存在するサポートベクトルでは、「ショット境界でない事例のクラス」の確率は多少大きい。
【００２９】
前記のように、本実施形態で対象としているショット境界検出の問題ではショット境界の事例の数はショット境界でない事例の数に比べて圧倒的に少ないため、図２のロジスティック関数での判別位置がｆ（ｘ）＝−０．５８と左側（ｙ＝−１、つまりショット境界であるクラスの側）に入り込んでいる。前述したように、ｆ（ｘ）＝−１でソフトマージン超平面上にあるサンプルですら、「ショット境界でないクラス」の条件付確率がゼロになっていない。このことは、写像空間の該当超平面付近に２つのクラスが混じっていることを示している。
【００３０】
反対に、ショット境界でないクラスのソフトマージン超平面を表すｆ（ｘ）＝＋１では、ショット境界でないクラスの条件付き確率はほぼ１．０であることから、超平面の付近は、ショット境界でないクラスの事例だけで構成されていることになる。ｆ（ｘ）＝−１の超平面上にあるサポートベクトルは、付与されたラベルの信頼度も高く、付近の他クラス（＝ショット境界でないクラス）との分離もさほど良くない。
【００３１】
このことから、本実施形態では、「ショット境界の事例のクラス」のマージン超平面上に存在する外れ値を除去する。
【図面の簡単な説明】
【００３２】
【図１】本発明の概略の処理手順を示すフローチャートである。
【図２】瞬時カット検出の訓練データから得られる条件付き確率を示すロジスティック関数のグラフである。
【図３】ソフトマージンを表す超平面とサポートベクトルとの写像空間上での位置関係を説明する図である。
【符号の説明】
【００３３】
Ｈ１，Ｈ２・・・超平面、Ｓ・・・境界面
【図１】
2009211648.tif 000006
【図２】
2009211648.tif 000007
【図３】
2009211648.tif 000008